Fault Tolerant Routing in Toroidal Networks (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)

概要

論文の詳細を見る
In this paper, we study the following node-to-node and node-to-set routing problems in r-dimensional torus T^r_n 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 T^r_n, find a fault-free path s→t; and given at most 2r-k faulty nodes and non-faulty nodes s and t_l, ..., t_k in T^r_n, find k fault-free node-disjoint paths s→t_i, 1≦i≦k. We give an O(T^2) time algorithm which finds a fault-free path s→t of length at most d(T^r_n)+r^2 for the node-to-node routing, where d(T^r_n) is the diameter of T^r_n. For node-to-set routing, we show an O(r^3) time algorithm which finds k fault-free node-disjoint 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.
一般社団法人電子情報通信学会の論文
1996-08-25