Universal algorithms for store-and-forward and wormhole routing
Robert Cypher, Friedhelm Meyer auf der Heide, Christian Scheideler, Berthold Vöcking · 1996
In this paper we present routing algorithms that are tmiversal in the sense that they route messages along arbitrary (simple) paths in arbitrary networks.The algorithms are analyzed in terms of the number of messages being routed, the maximum number of messages that must cross any edge in the network (edge congestion), the maximum number of edges that a message must cross (dilation), the bufler size, and the bandwidth of the links.We present two main results, both of which have applications to ttnivexsal storeand-forwwd routing and universal wormhole routing.Our results yield significant performance improvements over all previously known universal routing algorithms for a wide range of parameters, and they even improve many time bounds for standard networks.In addition, we present adaptations of our main results for routing along shortest paths in arbitrary networks, and for routing in leveled networks, node-symmetric networks, edge-symmetric networks, expanders, butterflies, and meshes.