About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 1984
Conference paper
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.