Loading...
Please wait, while we are loading the content...
Similar Documents
Universal Algorithms for Store-and-Forward and Wormhole Routing (1996)
| Content Provider | CiteSeerX |
|---|---|
| Author | Cypher, Robert Heide, Friedhelm Meyer Auf Der Scheideler, Christian Vöcking, Berthold |
| Description | In this paper we present routing algorithms that are universal 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 buffer size, and the bandwidth of the links. We present two main results, both of which have applications to universal storeand -forward 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 ... |
| File Format | |
| Language | English |
| Publisher Date | 1996-01-01 |
| Publisher Institution | IN PROC. OF THE 28TH ACM SYMP. ON THEORY OF COMPUTING (STOC |
| Access Restriction | Open |
| Subject Keyword | Standard Network Edge-symmetric Network Buffer Size Universal Algorithm Main Result Wide Range Wormhole Routing Universal Wormhole Routing Maximum Number Many Time Bound Node-symmetric Network Arbitrary Network Leveled Network Significant Performance Improvement |
| Content Type | Text |
| Resource Type | Article |
