Routing in the bidirectional shufflenet

In this paper we study the bidirectional shufflenet topology, which is obta ined from the well-known (unidirectional) shufflenet by considering bidirec tional links. More specifically, we define a shortest path routing algorith m, and derive the diameter and the average distance of the topology. The bi directional shufflenet is then compared, in terms of average distance, with other variations of the perfect shuffle. Bidirectional links are very comm on in real networks. Possible applications of bidirectional shufflenets are wormhole routing electronic networks with backpressure flow control, and w avelength routing optical networks, In the last part of the paper, the form er class of networks is considered, when virtual channels are used to preve nt deadlocks, We show that four virtual channels are sufficient to avoid de adlocks in the bidirectional shufflenet, regardless of the number of nodes in the topology.