JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]


Journal of Information Science and Engineering, Vol. 14 No. 4, pp. 765-783


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

  Retrieve PDF document (JISE_199804_04.pdf)