Wormhole routing in de Bruijn networks and hyper-de Bruijn networksGanesan, E., Dhiraj Pradhan, Wormhole routing in de Bruijn networks and hyper-de Bruijn networks. International Symposium on Circuits and Systems, 2003. . May 2003. PDF, 283 Kbytes.
The order-(m, n) hyper-de Bruijn graph HD(m, n) is the direct product of an order-m hypercube and an order-n de Bruijn graph. The hyper-de Bruijn graph offers flexibility in terms of connections per node and the level of fault-tolerance. These networks as well possess logarithmic diameter, simple routing algorithms and support many computationally important subgraphs and admit efficient implementation. In this paper, we present results on wormhole routing in binary de Bruijn and hyper-de Bruijn networks. For an N-node binary de Bruijn network, four deadlock-free routing algorithms are presented. These algorithms use log N, /spl lceil/2/3 log N/spl rceil/, /spl lceil/1/2 log N/spl rceil/ and 4 virtual channels per physical channel. The number of hops needed to route a message using the above algorithms are /spl les/log N, /spl les/log N, /spl les/log N and /spl les/2 log N, respectively. We present a generalized approach to design deadlock-free wormhole routing algorithms for the hyper-de Bruijn networks, based on the above algorithms.