FAULT-TOLERANT ROUTING IN TOROIDAL NETWORKS

In this paper, we study the Following node-to-node and node-to-set rou ting problems in r-dimensional torus T-n(r) with r greater than or equ al to 2 and n greater than or equal to 4 nodes in each dimension: give n al most 2r-1 faulty nodes and non-faulty nodes s and t T-n(r), find a fault-free path s-->t; and given at most 2r-k faulty nodes and non-f aulty nodes s and t(1),...,t(k) in T-n(r), find k fault-free node-disj oint paths s-->t(i), 1(l)ess than or equal to i less than or equal to k. We give an O(r(2)) time algorithm which finds a fault-free path s-- >t of length at most d(T-n(r))+1 for the node-to-node routing, where d (T-n(r)) is the diameter of T-n(r). For node-to-set routing, we show a n O(r(3)) time algorithm which finds k fault-free node-disjoint paths s --> t(i), 1 less than or equal to i less than or equal to k, of leng th at most d(T-n(r))+1. The upper bounds on the length of the found pa ths are optimal. From this, Rabin diameter of T-n(r) is d(T-n(r))+1.