Abstract | ||
---|---|---|
Freedom from deadlock is a key issue in cut-through, wormhole, and store and forward networks, and such freedom is usually obtained through careful design of the routing algorithm. Most existing deadlock-free routing methods for irregular topologies do, however, impose severe limitations on the available routing paths. We present a method called layered routing, which gives rise to a series of routing algorithms, some of which perform considerably better than previous ones. Our method groups virtual channels into network layers and to each layer it assigns a limited set of source/destination address pairs. This separation of traffic yields a significant increase in routing efficiency. We show how the method can be used to improve the performance of irregular networks, both through load balancing and by guaranteeing shortest-path routing. The method is simple to implement, and its application does not require any features in the switches other than the existence of a modest number of virtual channels. The performance of the approach is evaluated through extensive experiments within three classes of technologies. These experiments reveal a need for virtual channels as well as an improvement in throughput for each technology class. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1109/TPDS.2006.12 | Parallel and Distributed Systems, IEEE Transactions |
Keywords | Field | DocType |
multiprocessor interconnection networks,resource allocation,telecommunication network routing,telecommunication switching,telecommunication traffic,deadlock-free routing methods,irregular networks,irregular topologies,layered routing,shortest-path routing,virtual channels,Routing functions,deadlock avoidance,interprocessor communication,irregular topologies. | Multipath routing,Equal-cost multi-path routing,Link-state routing protocol,Dynamic Source Routing,Static routing,Policy-based routing,Computer science,Computer network,Destination-Sequenced Distance Vector routing,Real-time computing,Geographic routing,Distributed computing | Journal |
Volume | Issue | ISSN |
17 | 1 | 1045-9219 |
Citations | PageRank | References |
74 | 3.66 | 20 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Olav Lysne | 1 | 797 | 54.53 |
Tor Skeie | 2 | 1103 | 74.67 |
S. -A. Reinemo | 3 | 121 | 16.81 |
Ingebjorg Theiss | 4 | 87 | 4.32 |