Abstract
In this paper, we study natural conditions for 2D tori with a large number of faulty nodes to remain connected. Under the suggested connectivity conditions, we develop efficient routing algorithms in 2D tori with a large number of faulty nodes. As long as a given input torus and the meshes within the torus satisfy the conditions, the routing algorithm successfully constructs a fault-free path by using only local information of the network. Also, our algorithms do not require faulty nodes and faulty blocks to be a special structure such as convex, rectangle, while each mesh in a given torus can sustain as many faulty nodes as possible, provided that non-faulty nodes of the mesh are connected and the mesh holds the connectivity conditions. Specifically, for a torus sustaining up to 22.2% faulty nodes, in linear time, our algorithm constructs a fault-free path of length bounded by six times the shortest path length between the two nodes.
Chapter PDF
Similar content being viewed by others
References
S. Chalasani and R.V. Boppana, “Communication in Multicomputers with Nonconvex faults,” Proc. Int’l Symp. Computer Architecture, pp. 268–277, 1990.
J. Chen, I. A. Kanj, and G. Wang, “Hypercube Network Fault Tolerance: A Probabilistic Approach,” Proc. Int’l Conf. Parallel Processing, pp. 65–72, 2002.
J. Chen, G. Wang, and S. Chen, “Locally Subcube-Connected Hypercube Networks: Theoretical Analysis and Experimental Results,” IEEE Trans. Computers, vol. 51, no. 5, pp. 530–540, 2002.
J. Chen, G. Wang, and S. Chen, “Routing in Hypercube Networks with A Constant Fraction of Faulty Nodes, ” Journal of Interconnection Networks, vol. 2, pp. 283–294, 2001.
J. Chen, T. Wang, and E. Oh, “Adaptive Routing: Centralized versus Distributed,” Technical Report, Texas A&M University, 2002.
A.A. Chien and J.H. Kim, “Planar-Adaptive Routing: Low-Cost Adaptive Networks for Multiprocessors,” Proc. Int’l Symp. Computer Architecture, pp. 268–277, 1990.
W.J. Dally and C.L. Seitz, “The torus Routing Chip,” Distributed Computing, pp. 187–196, 1986.
W.J. Dally and C.L. Seitz, “Deadlock-free message routing in multiprocessor interconnection network, ” IEEE Trans Comput. vol. 36, no. 5, pp. 547–553, 1987.
Q.-P. Gu and S. Peng, “k-Pairwise Cluster Fault Tolerant Routing in Hypercubes,” IEEE Trans. Computers, vol. 46, pp. 1042–1049, 1997.
Q.-P. Gu and S. Peng, “Unicast in Hypercubes with Large Number of Faulty Nodes,” IEEE Trans. Parallel and Distributed Systems, vol. 10, pp. 946–975, 1999.
S. Latiffi, M. Hedge, and M. Naraghi-Pour, “Conditional Connectivity Measures for Large Multiprocessor Systems,” IEEE Trans. Computers, vol. 43, pp. 218–222, 1994.
C.C. Su and K.G. Shin, “Adaptive Fault-Tolerant Deadlock-Free Routing in Meshes and Hypercubes,” IEEE Trans. Computers, vol. 45, no. 6, pp. 666–683, 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Oh, E., Kim, JS., Lee, HO. (2003). Fault-Tolerant Routing in Mesh-Connected 2D Tori. In: Sloot, P.M.A., Abramson, D., Bogdanov, A.V., Gorbachev, Y.E., Dongarra, J.J., Zomaya, A.Y. (eds) Computational Science — ICCS 2003. ICCS 2003. Lecture Notes in Computer Science, vol 2659. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44863-2_52
Download citation
DOI: https://doi.org/10.1007/3-540-44863-2_52
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40196-4
Online ISBN: 978-3-540-44863-1
eBook Packages: Springer Book Archive