For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 1998/06/25
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)>>
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.