Title :
Node-to-node cluster fault tolerant routing in hypercubes
Author :
Gu, Qian-Ping ; Peng, Shietung
Author_Institution :
Dept. of Comput. Software, Aizu Univ., Fukushima, Japan
Abstract :
In this paper, we study the node-to-node fault tolerant routing problem in the n-dimensional hypercube Hn based on the cluster fault tolerant model. For a graph G, a faulty cluster is a connected subgraph of G such that all its nodes are faulty. In cluster fault tolerant routing problems, how many faulty clusters and how large of those clusters can be tolerated are studied. It has been known that for the node-to-node routing, Hn can tolerate as many as n-1 faulty clusters of diameter at most 1 with at most 2n-3 faulty nodes in total. In this paper, we extend the above result to show the sufficient conditions on faulty clusters of arbitrary diameters that Hn can tolerate. We also give an algorithm which, given a set of faulty clusters satisfying the sufficient conditions and non-faulty nodes s and t in Hn, finds a fault-free path s→t of length d(s,t)+O(log n) in O(n+|F|) optimal time, where |F| is the total number of faulty nodes
Keywords :
fault tolerant computing; hypercube networks; network routing; cluster fault tolerant model; fault tolerant routing; fault-free path; faulty clusters; hypercubes; node-to-node; Clustering algorithms; Concurrent computing; Electronic mail; Fault tolerance; Hypercubes; Multiprocessor interconnection networks; Routing; Software;
Conference_Titel :
Parallel Architectures, Algorithms, and Networks, 1997. (I-SPAN '97) Proceedings., Third International Symposium on
Conference_Location :
Taipei
Print_ISBN :
0-8186-8259-6
DOI :
10.1109/ISPAN.1997.645127