Robust network connectivity

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.