About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IEEE Transactions on Communications
Paper
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<sup>2</sup>, 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