Scientists say Web is inherently stable

08/14/2000

By Matthew Carr / The Dallas Morning News

Web users worried about a natural Internet disaster are surfing up the wrong tree.

The Internet would almost certainly survive even the worst imaginable breakdown of routers and other essential equipment, a new study finds. But the same structure that makes the Web resistant to this kind of random ruin also increases its vulnerability to organized attacks.

"Random day-by-day errors will not crash the system," says physicist Albert-Laszlo Barabasi. "No matter how many routers break down, those in the system will not notice it."

Routers are specialized computers that link together the Internet's smaller regional networks. They act as Internet traffic cops, deciding how best to send each packet of electronic information to its destination. At any given instant, an average of three of every 1,000 Internet routers experience a technical glitch that puts them temporarily out of commission. But even if 10 times this many routers failed, the performance of the Internet would remain unchanged, Dr. Barabasi and fellow Notre Dame physicists Reka Albert and Hawoong Jeong wrote last month in the journal Nature.

Another study, published online by Israeli researchers, suggests that up to 99.9 percent of all routers would have to fail to cause the Internet to break down completely.

But this resilience does not extend to organized attacks by hackers bent on breaking the system, the Notre Dame study found. By disabling routers with the greatest number of connections, Internet terrorists could cause a complete network collapse.

This peculiar combination of stability and vulnerability is a product of the Internet's self-organized structure, says Dr. Barabasi.

Until recently, he says, nobody really knew what the structure of the Internet was. After 1995, when the National Science Foundation relinquished its stewardship of the Internet, no one bothered to keep track of how the Internet's millions of computers were connected.

But growing interest in improving the speed, performance and security of Internet connections led to the formation in 1997 of an agency to help map the rapidly growing network. The Cooperative Association for Internet Data Analysis has now mapped enough connections to enable scientists like Dr. Barabasi to come up with mathematical equations that describe the Internet's flow of electronic information. These mathematical models can be used to study the strength of the network's structure.

The model that best represents the Internet is what mathematicians call a scale-free structure. Nodes, or points, in a scale-free network can be connected to a large number of other nodes, or to just a few.

In some networks, explains IBM mathematician Yuhai Tu, each node has roughly the same number of connections. The points of a Star of David form just such a network, with each point connected to two others.

But the connections of the Internet look more like an airline route map. A few "hub" nodes connect to a large number of other nodes, while a much larger number of spoke sites have just a handful of links. On the airline route map, cities would be nodes; on the Internet, routers are the nodes.

The Israeli study used a simplified model of this structure to assess the Internet's staying power. Reuven Cohen and three other physicists from Bar-Ilan University found – at least in mathematical theory – that the vast majority of the connections in their simplified Internet remained intact even if most of the routers failed. The study appears on the World Wide Web at xxx.lanl.gov/abs/cond-mat/0007048.

In the Nature study, Dr. Barabasi and his team confirmed that this theoretical resilience works for the real Internet as well.

Resilience, the Notre Dame scientists wrote, can be gauged using a quantity called the network diameter. It's a measure of the distance that information must travel to get to its destination: the minimum number of links between two nodes. The diameter of an airline network, for example, gives the fewest number of layovers a passenger could expect flying between two cities.

"The diameter of the Internet is around four," Dr. Barabasi says. That means that the typical e-mail message will travel through four routers before reaching its destination.

Randomly knock out 10 times the normal number of malfunctioning routers, and the distance between nodes remains unchanged. But disable the same number of the most-connected routers – the hubs – and the distance more than triples. Instead of passing through four routers, the typical e-mail message will go through more than 12.

Tripling the distance between nodes would not do much damage, says Dr. Barabasi. Since e-mail and other bits of digital data take only a few seconds to reach their destination, the delay would be small. But remove just a few more router hubs, and the main network breaks down completely in a process scientists call percolation.

"At percolation," says Dr. Cohen, "the network becomes mainly small islands of a few sites which are not connected to the rest of the network."

It's the electronic equivalent of a snowstorm striking Chicago's O'Hare and D/FW. Like travelers, information would become stranded at isolated outposts. Communication would cease.

The susceptibility of the Internet and other similarly structured networks to percolation "seriously reduce[s] their attack survivability," the Notre Dame scientists write. "This could be exploited by those seeking to damage these systems."

But not all scientists agree that such a catastrophe could occur. Duncan Callaway of Cornell University in Ithaca, N.Y., and three other scientists argue in a paper online that monitoring the Internet's diameter is not the correct way to gauge network resilience.

Using a different measure, which they call long-range connectivity, they found the Internet to be much more robust. Their results appear on the World Wide Web at xxx.lanl.gov/abs/cond- mat/0007300. Dr. Callaway and his colleagues removed the same central hubs that Dr. Barabasi's team did. But while the main network crashed according to Dr. Barabasi's measure, only about 15 percent of the nodes broke off for Dr. Callaway.

Dr. Barabasi counters that the exact timing of the mathematical crash, which he calls clustering, is not the real concern.

"The Internet would break down way before it starts clustering," he says. "If you take out the bigger nodes, then all the messages have to travel around it. All the messages would have to line up at the smaller nodes that don't have the capacity."

Changing the structure of the Internet to defend against such calculated attacks won't be easy, Dr. Barabasi says. Because the network has no centralized control, its structure, or topology, remains in the hands of the people who administer the individual routers, like Internet service providers.

"As long as you give the freedom to local managers," he says, "the topology will not change. But on the other hand, there are lots of clever people out there. Maybe they can think of ways of fixing it."

Dr. Cohen, of the Israeli study, is quick to warn that all of the recent results are based on mathematical models. These models make simplifying assumptions that might not be applicable to the real Internet, he says.

Dr. Barabasi agrees. "If you really want to simulate how the Internet breaks down, you have to simulate the dynamics," he says, referring to the technological differences between different routers, and differences in the actual jobs each router performs.

Dr. Barabasi's group plans to perform computer simulations that account for these details. But, at this point, he says, "we don't have the data to simulate an attack."

Asked what he believes is the true breaking point of the Internet, Dr. Barabasi says: "Hopefully we won't ever find out."