A Fault-Tolerant Wormhole Routing Algorithm in Two Dimensional Mesh Networks

Jinsoo KIM  Ji-Yun KIM  Hyunsoo YOON  Seung Ryoul MAENG  Jung Wan CHO  

IEICE TRANSACTIONS on Information and Systems   Vol.E81-D   No.6   pp.532-544
Publication Date: 1998/06/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fault Tolerant Computing
fault-tolerant routing,  mesh networks,  deadlock-freedom,  virtual channels,  wormhole routing,  

Full Text: PDF(1.2MB)>>
Buy this Article

We propose a fault-tolerant routing algorithm for 2D meshes. Our routing algorithm can tolerate any number of concave fault regions. It is based on xy-routing and uses the concept of the fault ring/chain composed of fault-free elements surrounding faults. Three virtual channels per physical link are used for deadlock-free routing on a fault ring. Four virtual channels are needed for a fault chain. For a concave fault ring, fault-free nodes in the concave region have been deactivated to avoid deadlock in the previous algorithms, which results in excessive loss of the computational power. Our algorithm ensures deadlock-freedom by restricting the virtual channel usage in the concave region, and it minimizes the loss of the computational power. We also extend the proposed routing scheme for adaptive fault-tolerant routing. The adaptive version requires the same number of virtual channels as the deterministic one.