text: Designing routing schemes is a multidimensional and complex task that depends on the objective function, the computational model (centralized vs. distributed), and the amount of uncertainty (online vs. offline). Nevertheless, there are quite a few well-studied general techniques, for a large variety of network problems. In contrast, in our view, practical techniques for designing robust routing schemes are scarce; while fault-tolerance has been studied from a number of angles, existing approaches are concerned with dealing with faults after the fact by rerouting, self-healing, or similar techniques. We argue that this comes at a high burden for the designer, as in such a system any algorithm must account for the effects of faults on communication. With the goal of initiating efforts towards addressing this issue, we showcase simple and generic transformations that can be used as a blackbox to increase resilience against (independently distributed) faults. Given a network and a routing scheme, we determine a reinforced network and corresponding routing scheme that faithfully preserves the specification and behavior of the original scheme. We show that reasonably small constant overheads in terms of size of the new network compared to the old are sufficient for substantially relaxing the reliability requirements on individual components. The main message in this paper is that the task of designing a robust routing scheme can be decoupled into (i) designing a routing scheme that meets the specification in a fault-free environment, (ii) ensuring that nodes correspond to fault-containment regions, i.e., fail (approximately) independently, and (iii) applying our transformation to obtain a reinforced network and a robust routing scheme that is fault-tolerant.
  @cite_15: The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This problem has obvious applications in the design of communication networks. Since the problem is @math -complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and @math an estimate for the failure probability that is accurate to within a relative error of @math with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of @math -connectivity, strong connectivity in directed Eulerian graphs and @math -way disconnection, and to evaluating the Tutte polynomial are also described. This version of the paper corrects several errata that appeared in the previous journal publication [D. R. Karger, SIAM J. Comput., 29 (1999), pp. 492--514].
  @cite_4: The undisrupted operation of logical structures and services is a crucial requirement in modern day communication networks. As the vertices and edges of the network may occasionally fail or malfunction, it is desirable to make those structures robust against failures. Fault-Tolerant (FT) Logical Network Structures are low cost high resilient structures, constructed on top of a given network, that satisfy certain desirable performance requirements concerning, e.g., connectivity, distance or capacity. In this survey, we review some recent results for designing FT network structures. We classify the existing construction algorithms into four classes and discuss the settings in which a given approach might become useful. We hope that this would pave the way towards the development of a more generalized theory for the design of fault-tolerant networks.
  @cite_17: Given a connected graph G and a failure probability p(e) for each edge e in G, the reliability of G is the probability that G remains connected when each edge e is removed independently with probability p(e). In this paper it is shown that every n-vertex graph contains a sparse backbone, i.e., a spanning subgraph with O(nlogn) edges whose reliability is at least (1-n^-^@W^(^1^)) times that of G. Moreover, for any pair of vertices s, t in G, the (s,t)-reliability of the backbone, namely, the probability that s and t remain connected, is also at least (1-n^-^@W^(^1^)) times that of G. Our proof is based on a polynomial time randomized algorithm for constructing the backbone. In addition, it is shown that the constructed backbone has nearly the same Tutte polynomial as the original graph (in the quarter-plane x>=1, y>1), and hence the graph and its backbone share many additional features encoded by the Tutte polynomial.
summary: The literature also considered random fault models. In the network reliability problem, the goal is to compute the probability that the (connected) input network becomes disconnected under random independent edge failures. The reliability of a network is the probability that the network remains connected after this random process. Karger @cite_15 gave a fully polynomial randomized approximation scheme for the network reliability problem. Chechik et. al @cite_17 studied a variant of the task, in which the goal is to compute a sparse sub-network that approximates the reliability of the input network. We, on the other hand, construct a reinforced network that increases the reliability of the input network; note also that our requirements are much stricter than merely preserving connectivity. For a more detailed survey on Fault-Tolerant Logical Network Structures, see @cite_4 .