SHORTEST PATH ROUTING IN BIDIRECTIONAL SHUFFLENET

Abstract

The bidirectional shufflenet is obtained from the well-known unidirectional shufflenet by considering bidirectional links. Bidirectional shufflenet topology has several desirable features including low average hop distance, support for backpressure flow control, high throughput and deadlock-free routing. Bidirectional links are very common in real networks and they are a requirement in some applications. For example, in wormhole routing networks with backpressure flow control, links are usually bidirectional since backpressure signals must be transferred hop-by-hop from the receiver to the transmitter, i.e., in the opposite direction with respect to the corresponding data flow. In this thesis we have studied the bidirectional shufflenet and calculated the shortest path between any two given nodes using a shortest path routing algorithm. We have also calculated the diameter and average distance of a given topology. The bidirectional shufflenet is then compared in terms of average distance with other variations of the perfect shuffle. Further we have studied wormhole routing networks as an application of bidirectional links. It has been shown how routing can be made deadlock-free using the virtual channel approach, and that four virtual channels per physical link are sufficient to guarantee absence of deadlocks, regardless of the number of nodes in the topology. Dally and Seitz's algorithm has been implemented to avoid deadlocks not only for networks with store-and-forward routing but also for networks supporting other routings such as the wormhole routing The software is written in C++ and runs under Windows environment.