Routing in hypercubes with large number of faulty nodes

One of the fundamental routing problems is to find a path from a source node s to a target node t in computer/communication networks. In an n-connected network, a nonfaulty path from s to t exists if there are at most n-1 faulty nodes. However, the network can be disconnected by n faulty nodes. Since the connectivity is usually a worst-case measure which is unlikely to happen in practice, it is important to develop routing algorithms for the case that more than n-1 faulty nodes present. We propose algorithms for finding the routing path from s to t in a hypercube with a large number of faulty nodes. Let H_n be the n-dimensional hypercube and H_n/F be the reduced graph obtained by removing the nodes of F from H_n. The reduced graph H_nF is called k-safe if each node of H_n/F has degree at least k. Our first algorithm, given a set F of faulty nodes in H_n such that |F|⩽2^k(n-k)-1 and H_n/F is k-safe for 0⩽k⩽n/2, and s,t ∈H_n /F, finds a nonfaulty free path s→t of length d(s,t)+O(k²) in O(|F|+n) optimal time, where d(s,t) is the distance between s and t. We show that a lower bound on the length of the nonfaulty path s→t is d(s,t)+2(k+1) for 0⩽k⩽n/2. Furthermore, for k=1 and 2, we give O(n) time algorithms which find a nonfaulty path s→t of length at most d(s,t)+4 and d(s,t)+6, respectively, which is tight to the lower bound