Robust network connectivity: when it's the big picture that matters

ABSTRACT

This work analyzes the connectivity of large diameter networks where every link has an independent probability p of failure. We give a (relatively simple) topological condition that guarantees good connectivity between regions of such a network. Good connectivity means that the regions are connected by nearly as many disjoint, fault-free paths as there are when the entire network is fault-free. The topological condition is satisfied in many cases of practical interest, even when two regions are at a distance much larger than the expected "distance between faults", 1/p. We extend this result to networks with failures on nodes, as well as geometric radio networks with random distribution of nodes in a deployment area of a given topography.A rigorous formalization of the intuitive notion of "hole" in a (not necessarily planar) graph is at the heart of our result and our proof. Holes, in the presence of faults, degrade connectivity in the region "around" them to a distance that grows with the size of the hole and the density of faults. Thus, to guarantee good connectivity between two regions even in the presence of faults, the intervening network should not only sport multiple paths, but also not too many large holes.Our result essentially characterizes networks where connectivity depends on the "big picture" structure of the network, and not on the local "noise" caused by faulty or imprecisely positioned nodes and links.

REFERENCES

• 1: B. Bollobás , F. R. K. Chung, The diameter of a cycle plus a random matching, SIAM Journal on Discrete Mathematics, v.1 n.3, p.328-333, Aug. 1988 [doi>10.1137/0401033]
• 2: L. Booth, J. Bruck, M. Franceschetti, and R. Meester. Continuum percolation and the geometry of wireless networks. Annals of Applied Probability, 13(2): 722--731, 2003.
• 3: O. Dousse and P. Thiran. Connectivity vs capacity in dense ad hoc networks. In Proceedings of IEEE INFOCOM, 2004.
• 4: O. Dousse, P. Thiran, and M. Hasler. Connectivityin ad-hoc and hybrid networks. In Proceedings of IEEE INFOCOM, 2002.
• 5: D. Dubhashi , C. Johansson , O. Häggström , A. Panconesi , M. Sozio, Irrigating ad hoc networks in constant time, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073986]
• 6: E. N. Gilbert. Random plane networks. Journal of the Society for Industrial and Applied Mathematics, 9(4): 533--543, 1961.
• 7: M. Franceschetti, J. Bruck, M. Cook, and R. Meester. Continuum percolation with unreliable and spread out connections. Journal of Statistical Physics, 2004.
• 8: P. Gupta and P. Kumar. Critical power for asymptotic connectivity in wireless networks. Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming, 1998.
• 9: P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2): 388--404, March 2000.
• 10: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 11: B. Krishnamachari, S. Wicker, and R. Bejar. Phase transition phenomena in wireless ad-hoc networks. In Proceedings of the Symposium on Ad-Hoc Wireless Networks (GlobeCom), 2001.
• 12: E. Lebhar and N. Schabanel. Almost optimal decentralized routing in long-range contact networks. In Proceedings of the 31st International Col l oquium on Automata, Languages and Programming, pages 179--188, 2004.
• 13: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 14: L. Li, J. Halpern, and Z. Haas. Gossip-based ad hoc routing. In Proceedings of IEEE INFOCOM, 2002.
• 15: Xiang-Yang Li , Kousha Moaveninejad , Ophir Frieder, Regional gossip routing for wireless ad hoc networks, Mobile Networks and Applications, v.10 n.1-2, p.61-77, February 2005 [doi>10.1145/1046430.1046436]
• 16: Chip Martel , Van Nguyen, Analyzing Kleinberg's (and other) small-world Models, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011794]
• 17: Petar Maymounkov , David Mazières, Kademlia: A Peer-to-Peer Information System Based on the XOR Metric, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.53-65, March 07-08, 2002
• 18: R. Meezer and R. Roy. Continuum Percolation. Cambridge University Press, 1996.
• 19: William J. Ouchark , Jay A. Davis , S. Lakshmivarahan , Sudarshan K. Dhall, Experiences with the Intel Hypercube, Proceedings of the 1986 workshop on Applied computing, p.2-7, October 10-10, 1986, Stillwater, Oklahoma, United States [doi>10.1145/800239.807163]
• 20: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 21: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 22: Y. Sasson, D. Cavin, and A. Schiper. Probabilistic broadcast for flooding in wireless mobile ad hoc networks. In Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), 2003.
• 23: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 24: D. Watts and S. Strogatz. Collective dynamics of small world networks. Nature, pages 393--440, 1998.
• 25: B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. Kubiatowicz. Tapestry: A resilient global-scale overlay for service deployment. IEEE Journal on Selected Areas in Communications, 22(1), January 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Reliability

Keywords:
ad hoc, connectivity, fault, network, percolation, random, resilient, topology