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

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

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