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

E Ganesan, D Pradhan

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

Abstract

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 contributionWormhole routing in de Bruijn networks and hyper-de Bruijn networks
Original languageEnglish
Title of host publicationUnknown
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Publication statusPublished - May 2003

Bibliographical note

Conference Proceedings/Title of Journal: International Symposium on Circuits and Systems, 2003.

Fingerprint Dive into the research topics of 'Wormhole routing in de Bruijn networks and hyper-de Bruijn networks'. Together they form a unique fingerprint.

Cite this