Cluster fault-tolerant routing in star graphs

Fault-tolerant routing is a key issue in computer! communication networks. We say a network (graph) can tolerate I faulty nodes for a routing problem if after removing at most I arbitrary faulty nodes from the graph the routing paths exist for the routing problem. However, the bound lis usually a worst-case measure and it is of great interest to find the routing paths when more than I faulty nodes exist. Cluster fault-tolerant (CFT) routing was proposed as an approach for this purpose. In the CFT routing, we reduce the number of "faults" that a routing problem has to deal with using subgraphs to cover the faulty nodes. In particular, we consider the number and the size (diameter) of faulty subgraphs rather than the number of faulty nodes that a graph can tolerate. In this paper, we show that a subgraph of diameter 2 can be viewed as a single "fault" for the following routing problems in the star graph: Given a source node sand t target nodes t(1),..., t(k), find k node-disjoint paths from s to t(i) (1 less than or equal to i less than or equal to k), and given k node pairs (s(1), t(1)),..., (S-k, t(k)), find k node-disjoint paths s(i) - t(i) (1 less than or equal to i less than or equal to k). Since a subgraph of diameter 2 of the n-dimensional star graph G(n) may have n nodes, the above result implies that the number of faulty nodes that G(n) can tolerate is n times larger than the worst-case measure if the faulty nodes can be covered by certain subgraphs. We also give algorithms which find the paths for the two routing problems. (C) 2000 John Wiley & Sons, Inc.