Cluster fault tolerant routing in hypercubes

We say a network (graph) can tolerate l faulty nodes for a specific routing problem if after removing at most l arbitrary nodes from the graph, the routing paths exist for the routing problem. However, the bound l is usually a worst-case measure and it is interesting, both practical and theoretical, to find the routing paths when more than l faulty nodes present. Cluster fault tolerant (CFT) routing has been proposed as an approach for this purpose. In CFT routing we try to 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. We show the necessary and sufficient conditions on the number and the size of faulty subgraphs that the hypercube can tolerate for the following routing problems: find a path from a source node s to a target node t; and find k node-disjoint paths from s to k nodes t₁,...,t_k. Our results imply that the hypercube can tolerate far more faulty nodes than the worst-case measures for these routing problems when the faulty nodes can be covered by certain subgraphs. We also give algorithms for finding the routing paths for the above routing problems