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.
|Translated title of the contribution||Wormhole routing in de Bruijn networks and hyper-de Bruijn networks|
|Title of host publication||Unknown|
|Publisher||Institute of Electrical and Electronics Engineers (IEEE)|
|Publication status||Published - May 2003|