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 &rgr; 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,&rgr;)/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 &rgr; is a minimal length routing, then the diameter of R(G,&rgr;)/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,&rgr;)/F≤3 for any minimal length routing &rgr; and any set of faults F with |F|<n. We also show that if F consists only of edges and does not disconnect G, then the diameter of R(G,&rgr;)/F is ≤ 3|F|+1, while if F consists only of nodes and does not disconnect G, then the diameter of R(G,&rgr;)/F is ≤ the sum of the degrees of the nodes in F, where in both cases &rgr; 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.

REFERENCES

• 1: H. Aghili, M. Astrahan, S. Finkelstein, W. Kim, J. McPherson, M. Schkolnick, R. Strong, "A Prototype for a Highly Available Database System," IBM Research Report RJ3755, January, 1983.
• 2: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 3: A. Broder, D. Dolev, M. Fischer, B. Simons, Efficient fault tolerant routings in networks, unpublished manuscript, 1983.
• 4: F. R. K. Chung and M. R. Garey, "Diameter Bounds for Altered Graphs," unpublished manuscript, 1983.
• 5: D. Dolev and R. Strong, "Authenticated Algorithms for Byzantine Agreement," to appear in SIAM J. Comput, see also IBM Research Report RJ3416, March, 1982.
• 6: D. Dolev and R. Strong, "Byzantine Agreement," IBM Research Report RJ3714, December, 1982.
• 7: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 8: L. G. Valiant, "A Scheme for Fast Parallel Communications," SIAM J. Comput., 11, May 1982, pp. 350-361.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory