Abstracts - 2006
Robust Network Connectivity: When It's The Big Picture That Matters
Enoch Peserico & Larry Rudolph
We characterize networks in which connectivity depends essentially only on the "big picture" structure of the network, and not on the inevitable "small scale noise" due to imprecisely positioned or faulty nodes or links. Crucial factors turn out to be not only the diameter and mincut of the network, but also the presence of large "holes" - holes interact with small scale noise seriously compromising the connectivity in the region surrounding them.
Connectivity = Large scale structure + Small scale noise
Connectivity between distant regions in large diameter networks depends on two main factors: large scale structure and small scale noise. The large scale structure of a network is typically linked to the topography of the area in which the network is deployed. For example, a city-wide adhoc radio network is essentially two dimensional (but could have an elongated shape in the case of a city along a river or in a narrow mountain valley) and necessarily has a large number of ``holes'' in areas, such as ponds or electromagnetically shielded buildings, that nodes cannot populate and through which information cannot flow. As another example, a SmartDust large sensor network deployed on the surface of a building, of an aircraft or of a ship to detect signs of impending structural failure has a topology essentially determined by the nature of the building - a topology that could be particularly intricate in cases such as that of the Eiffel tower. Of course, there are many examples of large scale adhoc distributed peer to peer networks whose ``large scale'' topology depends not on physical factors, but on the algorithm used to form the links.
Connectivity is also affected by a level of ``small scale noise'': in large networks a fraction of the nodes is almost inevitably faulty, the deployment process is often imprecise, and sometimes mobility can alter the position of nodes over time. The effects of this noise, even when relatively limited on short range communications, can accumulate and seriously compromise long range connectivity: if every link has a probability p of failure, then the probability that a path of h hops is entirely fault free is approximately e-hp, which becomes vanishingly small when h is much larger than the average distance between faults, 1/p. This can make long range communication problematic in large diameter networks with even a moderate level of small scale noise, such as sensor networks, large mobile radio networks, or nanotechnological ensembles.
Most of the (vast) literature on connectivity in the presence of small scale noise studies how different types and levels of small scale noise affect networks with a single, specific large scale structure - rather than how variations in large scale structure affect connectivity in the presence of a given level or range of small scale noise.
Connectivity can be independent of small scale noise: but beware of holes!
We characterize networks whose connectivity essentially depends only on their large scale structure and is independent from small scale noise. In these ``robustly linked'' networks connectivity between regions - expressed in terms of disjoint, non-faulty paths - is always, with high probability, within a small factor of the optimal.
Informally, we show that even extremely narrow strips (of width logarithmic in their length) are sufficient to guarantee good connectivity in a network with imprecisely positioned/faulty nodes and links, provided there are not too many large "holes" in the network. Large holes require larger width, since, in the presence of small scale noise, they can effectively erode connectivity in the region surrounding them to a distance that is logarithmic in the girth (informally, the ``circumference'') of the hole, and grows with the level of small scale noise.
The theoretical cornerstone of our work is a formal analysis of the notion of "hole" on graphs - an intuitive notion in two dimensions, but far more subtle in higher dimensions or on general, non-planar graphs: for example, the "hole" in a doughnut is fundamentally different from that in a piece of swiss cheese. This analysis yields insights that might be of independent interest. Our theoretical analysis is validated by extensive simulations involving up to a billion nodes.
A number of consequences
Our results have a number of consequences - some of them, perhaps, surprising.
This work was funded in part by the Singapore-MIT-Alliance (SMA).
 Enoch Peserico, Larry Rudolph. Robust network connectivity: when it's the big picture that matters. Proceedings of ACM SIGMETRICS 2006.