Fault Tolerant Routing in Toroidal Networks*

Qian-Ping GU  Shietung PENG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.8   pp.1153-1159
Publication Date: 1996/08/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Architectures, Algorithms and Networks for Massively Parallel Computing)
Category: Fault Diagnosis/Tolerance
Keyword: 
algorithms,  interconnection networks,  node-disjoint paths,  node fault tolerant routing,  

Full Text: PDF(546.3KB)>>
Buy this Article




Summary: 
In this paper, we study the following node-to-node and node-to-set routing problems in r-dimensional torus Trn with r 2 and n 4 nodes in each dimension: given at most 2r - 1 faulty nodes and non-faulty nodes s and t in Trn, find a fault-free path s t; and given at most 2r - k faulty nodes and non-faulty nodes s and t1,..., tk in Trn, find k fault-free node-disjoint paths s ti, 1 i k. We give an O(r2) time algorithm which finds a fault-free path s t of length at most d(Trn) + 1 for the node-to-node routing, where d(Trn) is the diameter of Trn. For node-to-set routing, we show an O(r3) time algorithm which finds k fault-free node-disjoint paths s ti, 1 i k, of length at most d(Trn) + 1. The upper bounds on the length of the found paths are optimal. From this, Rabin diameter of Trn is d(Trn) + 1.