Network failure detection and graph connectivity

ABSTRACT

We consider a model for monitoring the connectivity of a network subject to node or edge failures. In particular, we are concerned with detecting (ε, k)-failures: events in which an adversary deletes up to network elements (nodes or edges), after which there are two sets of nodes A and B, each at least an ε fraction of the network, that are disconnected from one another. We say that a set D of nodes is an (ε k)-detection set if, for any (ε k)-failure of the network, some two nodes in D are no longer able to communicate; in this way, D "witnesses" any such failure. Recent results show that for any graph G, there is an is (ε k)-detection set of size bounded by a polynomial in k and ε, independent of the size of G.In this paper, we expose some relationships between bounds on detection sets and the edge-connectivity λ and node-connectivity κ of the underlying graph. Specifically, we show that detection set bounds can be made considerably stronger when parameterized by these connectivity values. We show that for an adversary that can delete κλ edges, there is always a detection set of size O((κ/ε) log (1/ε)) which can be found by random sampling. Moreover, an (ε, &lambda)-detection set of minimum size (which is at most 1/ε) can be computed in polynomial time. A crucial point is that these bounds are independent not just of the size of G but also of the value of λ.Extending these bounds to node failures is much more challenging. The most technically difficult result of this paper is that a random sample of O((κ/ε) log (1/ε)) nodes is a detection set for adversaries that can delete a number of nodes up to κ, the node-connectivity.For the case of edge-failures we use VC-dimension techniques and the cactus representation of all minimum edge-cuts of a graph; for node failures, we develop a novel approach for working with the much more complex set of all minimum node-cuts of a graph.

REFERENCES

• 1: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 2: Joseph Cheriyan , Ramakrishna Thurimella, Fast algorithms for k-shredders and k-node connectivity augmentation (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.37-46, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237826]
• 3: B. Cherkasskij, "Solution of a Problem on Multicommodity Flows in a Network," Ekon. Mat. Metody 13:1(1977), pp. 143--151. (in Russian; the result is cited in {9}).
• 4: F. Chung, M. Garrett, R. Graham and D. Shallcross, "Distance realization problems with applications to Internet tomography," Journal of Computer and System Sciences 63(3): 432--448 (2001).
• 5: K. Claffy, T. Monk and D. McRobb, "Internet Tomography," Nature, Web Matters, Jan. 7, 1999.
• 6: E. Dinits, A. Karzanov and M. Lomonosov, "On the Structure of a Family of Minimal Weighted Cuts in a Graph", in A. Fridman, ed., Studies in Discrete Optimization, pp. 290--306, Nauka, Moscow, 1976 (in Russian).
• 7: J. Fakcharoenphol, An improved VC-dimension bound for finding network failures. Master's thesis, Dept. of EECS, UC Berkeley, 2001. Includes a result by A. Gupta.
• 8: Lisa Fleischer, Building chain and cactus representations of all minimum cuts from Hao-Orlin in the same asymptotic run time, Journal of Algorithms, v.33 n.1, p.51-72, Oct. 1999 [doi>10.1006/jagm.1999.1039]
• 9: A. Frank, "Packing paths, circuits, and cuts --- a survey," in: Paths, Flows and VLSI-Layouts, B. Korte, L. Lovász, H-J. Prömel, A. Schrijver, eds., Springer-Verlag (1990) pp. 47--100.
• 10: Harold N. Gabow, Centroids, representations, and submodular flows, Journal of Algorithms, v.18 n.3, p.586-628, May 1995
• 11: H. N. Gabow, Using expander graphs to find vertex connectivity, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.410, November 12-14, 2000
• 12: Tibor Jordán, On the optimal vertex-connectivity augmentation, Journal of Combinatorial Theory Series B, v.63 n.1, p.8-20, Jan. 1995 [doi>10.1006/jctb.1995.1002]
• 13: T. Jordán, "On the Number of Shredders," J. Graph Theory, 31 (1999), pp. 195--200.
• 14: J. Kleinberg, Detecting a network failure, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.231, November 12-14, 2000
• 15: L. Lovász, "On Some Connectivity Properties of Eulerian Graphs," Acta Math. Hung. 28 (1976), pp. 129--138.
• 16: W. Mader, " Über die Maximalzahl kantendisjunkter A-Wege," Arch. Math.30(1978), pp. 325--336.
• 17: J. Mahdavi and V. Paxson, "IPPM Metrics for Measuring Connectivity," RFC 2678, Network Working Group, Sept. 1999.
• 18: S. Muthukrishnan , Torsten Suel , Radek Vingralek, Inferring tree topologies using flow tests, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 19: V. Paxson, "Towards a Framework for Defining Internet Performance Metrics," Proc. INET 1996.
• 20: J.-C. Picard and M. Queyranne, "On the Structure of All Minimum Cuts in a Network and Applications," Mathematical Programming Study13(1980) pp. 8--16.