A new look at fault tolerant network routing

Abstract

Consider a communication network G in which a limited number of link and/or node faults F might occur. A routing p for the network (a fixed path between each pair of nodes) must be chosen without any knowledge of which components might become faulty. Choosing a good routing corresponds to bounding the diameter of the surviving route graph R(G,ρ)/F, where two nonfaulty nodes are joined by an edge if there are no faults on the route between them. We prove a number of results concerning the diameter of surviving route graphs. We show that if p is a minimal length routing, then the diameter of R(G, ρ)/F can be on the order of the number of nodes of G, even if F consists of only a single node. However, if G is the n-dimensional cube, the diameter of R(G, ρ)/F<3 for any minimal length routing p and any set of faults F with IFl<n. We also show that if F consists only of edges and does not disconnect G, then the diameter of R(G, ρ)/F is < 3IFI+1, while if F consists only of nodes and does not disconnect G, then the diameter of R(G, ρ)/F is < the sum of the degrees of the nodes in F, where in both cases ρ is an arbitrary minimal length routing. We conclude with one of the most important contributions of this paper: a list of interesting and apparently difficult open problems.