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
Information and Computation
Paper
Efficient fault-tolerant routings in networks
Abstract
We analyze the problem of constructing a network with a given number of nodes which has a fixed routing and which is highly fault tolerant. A construction is presented which forms a "product route graph" from two or more constituent "route graphs." The analysis involves the surviving route graph, which consists of all nonfaulty nodes in the network with two nodes being connected by a directed edge iff the route from the first to the second is still intact after a set of component failures. The diameter of the surviving route graph is a measure of the worst-case performance degradation caused by the faults. The number of faults tolerated, the diameter, and the degree of the product graph are related in a simple way to the corresponding parameters of the constituent graphs. In addition, there is a "padding theorem" which allows one to add nodes to a graph and to extend a previous routing. © 1987.