Mentor: An Algorithm for Mesh Network Topological Optimization and Routing

Abstract

We consider the problem of obtaining a minimum cost topology for a mesh network given matrices specifying the cost of links between all pairs of nodes and the internode requirements. We present a heuristic algorithm which works in terms of general network design principles and uses utilization as a figure of merit Thus, the procedure is applicable to a wide variety of networks, especially to the problem of obtaining starting topologies for other network design procedures. The algorithm's computational complexity is shown to be of order N², a significant improvement over currently used algorithms. Indeed, it is fast enough to be embedded in the inner loop of other more general design procedures, e.g., node selection procedures. We present computational experience which shows that although this procedure is fast and simple, it nevertheless yields solutions of a quality competitive with other much slower procedures. © 1991 IEEE