K-PAIRWISE CLUSTER FAULT-TOLERANT ROUTING IN HYPERCUBES

In this paper, we introduce a general fault tolerant routing problem, cluster fault tolerant routing, which is a natural extension of the we ll studied node fault tolerant routing problem. A cluster is a connect ed subgraph of a graph G, and a cluster is faulty if all nodes in it a re faulty. In cluster fault tolerant routing (abbreviated as CFT routi ng), we are interested in the number of faulty clusters and the size o f the clusters that an interconnection network can tolerate for certai n routing problems. As a case study, we investigate the following k- p airwise CFT routing in n-dimensional hypercubes H-n: Given a set of fa ulty clusters and k distinct nonfaulty node pairs (s(1), t(1)),..., (S -k,t(k)) in H-n, find k fault-free node-disjoint paths s(1) --> t(1), 1 less than or equal to i less than or equal to k. We show that H-n ca n tolerate n - 2 faulty clusters of diameter one, plus one faulty node for the k-pairwise CFT routing with k = 1, For n greater than or equa l to 4 and 2 less than or equal to k less than or equal to inverted ri ght perpendicular n/2 inverted left perpendicular, we prove that H-n c an tolerate n - 2k + 1 faulty clusters of diameter one for the k-pairw ise CFT routing. We also give an O(kn log n) time algorithm which find s the k paths for the mentioned problem. Our algorithm implies an O(n( 2) log n) time algorithm for the k-pairwise node-disjoint paths proble m in H-n, which improves the previous result of O(n(3) log n).