
For FullText 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.

Fault Tolerant Routing in Toroidal Networks^{*}
QianPing GU Shietung PENG
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E79D
No.8
pp.11531159 Publication Date: 1996/08/25
Online ISSN:
DOI:
Print ISSN: 09168532 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, nodedisjoint paths, node fault tolerant routing,
Full Text: PDF(546.3KB)>>
Summary:
In this paper, we study the following nodetonode and nodetoset routing problems in rdimensional torus T^{r}_{n} with r 2 and n 4 nodes in each dimension: given at most 2r  1 faulty nodes and nonfaulty nodes s and t in T^{r}_{n}, find a faultfree path s t; and given at most 2r  k faulty nodes and nonfaulty nodes s and t_{1},..., t_{k} in T^{r}_{n}, find k faultfree nodedisjoint paths s t_{i}, 1 i k. We give an O(r^{2}) time algorithm which finds a faultfree path s t of length at most d(T^{r}_{n}) + 1 for the nodetonode routing, where d(T^{r}_{n}) is the diameter of T^{r}_{n}. For nodetoset routing, we show an O(r^{3}) time algorithm which finds k faultfree nodedisjoint paths s t_{i}, 1 i k, of length at most d(T^{r}_{n}) + 1. The upper bounds on the length of the found paths are optimal. From this, Rabin diameter of T^{r}_{n} is d(T^{r}_{n}) + 1.

