A deterministic fault-tolerant and deadlock-free routing protocol in 2-D meshes based on odd-even turn model

ABSTRACT

We propose a deterministic fault-tolerant and deadlock-free routing protocol in 2-dimensional (2-D) meshes based on dimension-order routing and the recently proposed odd-even turn model. The proposed protocol, called extended X-Y routing, does not use any virtual channels by prohibiting certain locations of faults and destinations. Faults are contained in a set of disjointed rectangular regions called faulty blocks. The number of faults to be tolerated is unbounded as long as nodes outside faulty blocks are connected in the mesh network. The extended X-Y routing can also be used under a special convex fault region called orthogonal faulty block, which can be derived from a given faulty block by activating some nonfaulty nodes in the block. Extensions to partial adaptive routing, traffic- and adaptivity-balanced using virtual networks, and routing without constraints using virtual channels and virtual networks are also discussed.

REFERENCES

• 1: Suresh Chalasani , Rajendra V. Boppana, Fault-Tolerant Wormhole Routing Algorithms for Mesh Networks, IEEE Transactions on Computers, v.44 n.7, p.848-864, July 1995 [doi>10.1109/12.392844]
• 2: Y. M. Boura and C. R. Das. Fault-tolerant routing in mesh networks. Proc. of 1995 International Conference on Parallel Processing. August 1995, I 106--I 109.
• 3: Suresh Chalasani , Rajendra V. Boppana, Communication in multicomputers with nonconvex faults, IEEE Transactions on Software Engineering, v.23 n.9, p.616-622, September 1997
• 4: Andrew A. Chien , Jae H. Kim, Planar-adaptive routing: low-cost adaptive networks for multiprocessors, Journal of the ACM (JACM), v.42 n.1, p.91-123, Jan. 1995 [doi>10.1145/200836.200856]
• 5: Ge-Ming Chiu, The Odd-Even Turn Model for Adaptive Routing, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.729-738, July 2000 [doi>10.1109/71.877831]
• 6: W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 7: José Duato, A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.6 n.10, p.1055-1067, October 1995 [doi>10.1109/71.473515]
• 8: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 9: Eric Fleury , Pierre Fraigniaud, A General Theory for Deadlock Avoidance in Wormhole-Routed Networks, IEEE Transactions on Parallel and Distributed Systems, v.9 n.7, p.626-638, July 1998 [doi>10.1109/71.707539]
• 10: Christopher J. Glass , Lionel M. Ni, Fault-Tolerant Wormhole Routing in Meshes without Virtual Channels, IEEE Transactions on Parallel and Distributed Systems, v.7 n.6, p.620-636, June 1996 [doi>10.1109/71.506701]
• 11: Christopher J. Glass , Lionel M. Ni, The turn model for adaptive routing, Journal of the ACM (JACM), v.41 n.5, p.874-902, Sept. 1994 [doi>10.1145/185675.185682]
• 12: Ran Libeskind-Hadas , Kevin Watkins , Thomas Hehre, Fault-Tolerant Multicast Routing in the Mesh with No Virtual Channels, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.180, February 03-07, 1996
• 13: Daniel H. Linder , Jim C. Harden, An Adaptive and Fault Tolerant Wormhole Routing Strategy for k-ary n-cubes, IEEE Transactions on Computers, v.40 n.1, p.2-12, January 1991 [doi>10.1109/12.67315]
• 14: Hyunmin Park , Dharma P. Agrawal, Generic Methodologies for Deadlock-Free Routing, Proceedings of the 10th International Parallel Processing Symposium, p.638-643, April 15-19, 1996
• 15: Y. J. Suh, B. V. Dao, J. Duato, and S. Yalamanchili. Software based fault-tolerant oblivious routing in pipelined networks. Proc. of the 1995 International Conference on Parallel Processing. August 1995, I 101--I 105.
• 16: Pao-Hwa Sui , Sheng-De Wang, An Improved Algorithm for Fault-Tolerant Wormhole Routing in Meshes, IEEE Transactions on Computers, v.46 n.9, p.1040-1042, September 1997 [doi>10.1109/12.620485]
• 17: D. Wang. Minimal-connected-component (MCC) - a refined fault block model for fault-tolerant minimal routing in mesh. Proc. of IASTED Int'l Conf. on Parallel and Distributed Computing and Systems. Nov. 1999, 95--100.
• 18: J. Wu. A deterministic fault-tolerant and deadlock-free routing protocol in 2-d meshes without virtual channels. Technical Report, Florida Atlantic University, TR-CSE-00-26, Nov. 2000.
• 19: Jie Wu, A Distributed Formation of Orthogonal Convex Polygons in Mesh-Connected Multicomputers, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.70, April 23-27, 2001
• 20: Jie Wu, Reliable Unicasting in Faulty Hypercubes Using Safety Levels, IEEE Transactions on Computers, v.46 n.2, p.241-247, February 1997 [doi>10.1109/12.565613]
• 21: Jipeng Zhou , Francis C. M. Lau, Adaptive Fault-tolerant Wormhole Routing in 2D Meshes, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.56, April 23-27, 2001

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.0 General

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Reliability, Theory

Keywords:
deadlock-free routing, deterministic routing, fault models, fault tolerance, turn models, virtual channels