No Access

DEADLOCK-FREE ROUTING IN IRREGULAR NETWORKS USING PREFIX ROUTING

JIE WU

Department of Computer Science and Engineering, Florida Atlantic University, Boca Raton, FL 33431, USA

Search for more papers by this author

and

LI SHENG

Department of Mathematics and Computer Science, Drexel University, Philadelphia, PA 19104, USA

Search for more papers by this author

https://doi.org/10.1142/S0129626403001616Cited by:6 (Source: Crossref)

Abstract

We propose a deadlock-free routing scheme in irregular networks using prefix routing. Prefix routing is a special type of routing with a compact routing table associated with each node (processor). Basically, each outgoing channel of a node is assigned a special label and an outgoing channel is selected if its label is a prefix of the label of the destination node. Node and channel labeling in an irregular network is done through constructing a spanning tree. The routing process follows a two-phase process of going up and then down along the spanning tree, with a possible cross channel (shortcut) between two branches of the tree between two phases. We show that the proposed routing scheme is deadlock- and livelock-free. We also compare prefix routing with the existing up*/down* routing which has been widely used in irregular networks. Possible extensions are also discussed.

This work was supported in part by NSF grants CCR 9900646, ANI 0093936, and EIA 0130806.

Keywords:

References

InfiniBand Trade Association. Infiniband architecture. specification volume 1. release 1.0. http://www.infinibandta.org . Google Scholar
E. M. Bakker, J. van Leeuwen and R. B. Tan, Computer Networks and ISDN Systems 26, 403 (1993). Crossref, Web of Science, Google Scholar
J. Duato, Proc. of the 3rd IEEE Symp. on Parallel and Distributed Processing (1991) pp. 840–847. Crossref, Google Scholar
P. Fraigniaud and C. Cavoille, Proc. of the 12th Annual Symposium on Theoretical Aspects of Computer Science, LNCS 900 (Springer-Verlag, 1995) pp. 279–290. Google Scholar
G. N. Frederickson and R. Janardan, Proc. of the 5th ACM Symp. on Principles of Distributed Computing (1986) pp. 88–97. Crossref, Google Scholar
T. C. Lee and J. P. Hayes, IEEE Transactions on Computers 41(10), 1242 (1992). Crossref, Web of Science, Google Scholar
R. Libeskind-Hadas, D. Mazzoni and R. Rajagopalan, Proc. of the First IPPS/SPDP (1998) pp. 244–249. Google Scholar
N. A. Lynch , Distributed Algorithms ( Morgan Kaufmann Publishing, Inc. , 1996 ) . Google Scholar
H. Park and D. P. Agrawal, Proc. of the 10th International Parallel Processing Symposium (1996) pp. 638–643. Google Scholar
R. Perlman, Proc. of the 9th Data Communication Symp. (1985) pp. 44–53. Google Scholar
W. Qiao and L. M. Ni, Proc. of the 1996 International Conference on Parallel Processing. Vol. I (1996) pp. 46–60. Google Scholar
M. Schroederet al., IEEE Journal of Selected Areas in Communications 9(10), 1318 (1991). Crossref, Web of Science, Google Scholar
F. Silla and J. Duato , Proc. of Workshop on Communications, Architecture, and Applications for Network-based Parallel Computing (CANPC'99) ( 1999 ) . Google Scholar
R. Sivaram , D. K. Panda and C. B. Stunkel , Proc. of the 2nd Parallel Computing, Routing, and Communication Workshop ( 1997 ) . Google Scholar
H. Wang and D. M. Blough , Journal of Parallel and Distributed Computing . Google Scholar
N. C. Wang, T. S. Chen and C. P. Chu, Proc. of ISCA International Conference on Parallel and Distributed Computing Systems (2001) pp. 13–18. Google Scholar
J. Wu , Distributed System Design ( The CRC Press , 1999 ) . Google Scholar