Wormhole routing in de Bruijn networks and hyper-de Bruijn networks

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, ┌2/3 log N┐, ┌1/2 log N┐ and 4 virtual channels per physical channel. The number of hops needed to route a message using the above algorithms are ≤log N, ≤log N, ≤log N and ≤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.