AuthorsO. Lysne, T. Skeie, S. Reinemo and I. T. Theiss
TitleLayered Routing in Irregular Networks
AfilliationCommunication Systems, Communication Systems
Publication TypeJournal Article
Year of Publication2006
JournalIEEE Transactions on Parallel and Distributed Systems
Date Publishedjanuary

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.

Citation KeyLysne.2006.1