The Internet is Surprisingly Robust

The Internet is surprisingly robust, and it remains connected on a global scale even if a randomly chosen 99% of its connection points break down. However, it is relatively fragile if its most highly connected points are selectively knocked out. These are the conclusions of researchers applying physics principles and precise mathematical models to the study of the worldwide computer network.

The Internet consists of computer networks (most commonly, "local area networks") connected by various devices, known as routers and hubs. For simplicity's sake, researchers consider each connection point as a generic "node." Previous work suggests the fraction of Internet nodes having k connections is proportional to k^-a, for some number a. This is a "scale-free power law distribution," which occurs commonly in nature and appears in the frequency of earthquakes and the size distributions of clouds and mountains.

Unlike an exponential distribution, a scale-free power law distribution decays very slowly, meaning in this case that there is a large proportion of computers that still have a significant amount of connections. Recent computer simulations of scale-free networks have shown that the Internet is resilient for this reason (Albert et al., Nature, 27 July; Albert-Laszlo Barabasi, Notre Dame, 219-631-5767, alb@nd.edu; see also The Industrial Physicist, December 2000).

The latest work now puts this conclusion on a firm mathematical footing. Two independent groups (Reuven Cohen, Bar Ilan University, Israel, 011-972-8-9370131, cohenr@shosji.ph.biu.ac.il; Duncan Callaway, Cornell, 607-255-9174; dc52@cornell.edu) apply percolation theory, developed by geophysicists interested in estimating how much oil they could extract from reservoirs in a porous medium. Percolation theory deals with systems containing points ("sites") and connections between them, and it analyzes the behavior of the system when one removes some of the sites or connections. Combined with the insights from the scale-free distribution, the powerful percolation-based approach may help Internet architects to maximize resistance against Internet attacks, by controlling the distribution of nodes having certain numbers of connections. (Cohen et al, Phys. Rev. Lett, 20 Nov (Select Articles); Callaway et al., Phys. Rev. Lett., upcoming.)