WORMHOLE ROUTING IN DE BRUIJN NETWORKS AND HYPER-DEBRUIJN NETWORKS (INVITED PAPER)

摘要

The order-(m, n) hyper-deBruijn graph HD(m, n) is the direct product of an order-m hypercube and an order-n debruijn graph. The hyper-deBruijn 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 worm-hole routing in binary de Bruijn and hyper-deBruijn networks. For an TV-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 ≤ logN, ≤ logN, ≤ logN and ≤ 2logN, respectively. We present a generalized approach to design deadlock-free wormhole routing algorithms for the hyper-deBruijn networks, based on the above algorithms.