< JISE Vol.14 No.4 #1
[Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.14 No.4, pp.765-783 (December 1998)
Fault-Tolerant Routing Algorithm for Meshes
Without Using Virtual Channels

Kuo-Hsuan Chen and Ge-Ming Chiu
Department of Electrical Engineering and Technology
National Taiwan University of Science and Technology
Taipei, Taiwan 106, R. O. C.

We present a fault-tolerant routing algorithm which requires no virtual chan-nels for mesh networks. Our method employs the concepts of fault rings and fault chains, which were previously used with virtual channels, to facilitate fault-tolerant routing. Typically, the number of faults that can be tolerated in a mesh without virtual channels is very small, or the number of nonfaulty nodes that must be disabled is large. The method tolerates any number of faults without disabling a large number of nonfaulty nodes. The proposed algorithm tolerates any number of faults without disabling a large number of nonfaulty nodes. Moreover, only the nodes on fault rings and fault chains need to maintain a small amount of routing information. The algorithm avoids the formation of the rightmost column segment of a circular waiting path to ensure the property of deadlock freedom. Simulations have been conducted to evaluate the performance of our algorithm without virtual channels.

Keywords: deadlock-free, fault tolerance, routing, virtual channel, wormhole routing

Full Text () Retrieve PDF document (199812_04.pdf : 152,035 bytes)

Received May 2, 1997; accepted February 27, 1998.
Communicated by Jang-Ping Sheu.