Merlin
10-09-2002, 12:59 PM
What does the Internet look like?
----------------------------------
Another interesting article from The Economist print edition
----------------------------------
It is less random than people thought
FEW questions are simultaneously so baffling and so significant as: “what is the structure of the Internet?” Baffling, because the thing has grown without any planning or central organisation. Significant, because knowing how the routing computers that are the net's physical embodiment are interconnected is vital if it is to be used properly. At the latest count, there were 228,265 of these routers around the world. They direct the packets of data that make up Internet traffic.
Any effort to map the Internet is necessarily incomplete and out of date the moment it appears. Instead, Albert-Laslo Barabasi and his colleagues at the University of Notre Dame, in Indiana, treat the net as though it were a natural phenomenon. What scientists generally do with a natural phenomenon that they do not understand is to build a model of it. Dr Barabasi's latest paper on the matter, just published in the Proceedings of the National Academy of Sciences, presents a general framework for improving the accuracy of Internet models.
Until 1999, the standard way of modelling the Internet was to use randomly generated graphs, in which routers were represented by points and the links between them by lines. But it turns out that such random graphs are a poor approximation because they miss two important features. The first is that links in the net are “preferentially attached”: a router that has many links to it is likely to attract still more links; one that does not, will not. The second is that the Internet has more clusters of connected points than random graphs do. These two properties give the Internet a topology that is scale-free—in other words, small bits of it, when suitably magnified, resemble the whole.
Dr Barabasi noticed that the World Wide Web (the most visible bit of the Internet) was scale-free in 1999. His observation touched off a flurry of research, and others pointed out that the Internet as a whole was scale-free, too. This has several implications. On the one hand, scale-free topology is resistant to random failures—one reason the Internet, despite the lack of artifice in its design, has proved so reliable. On the other hand, because there are disproportionately many hubs (as well-connected routers are known), the net is particularly susceptible to deliberate attacks on those hubs, the sort of thing that cyberterrorists might attempt.
The goal, Dr Barabasi says, is to create models that are statistically indistinguishable from the real Internet. When and if that is achieved, the models should have predictive, as well as descriptive, power.
Already, understanding the net's scale-free structure has led to new results. For example, it had long been thought that the best way to curb the spread of a computer virus was to change the software of machines on the net so that they were less easily “infected”. Studies using random graphs had shown that changing the software on more and more machines had a cumulative effect. That is not true in a scale-free setting. There, most software changes make no difference to the rate at which a virus spreads (although they obviously protect the machines in question). However, treating a relatively small number of hubs in a scale-free system can stamp viruses out completely.
That observation may have implications beyond the virtual world. Research has shown that the network of human sexual partners seems to be scale-free, too. In other words, some people have all the luck, while others have none. So stopping the spread of a disease such as AIDS may be a comparatively simple matter of getting treatment to the right people—a strange but real corollary to a piece of research on cyberspace.
----------------------------------
Another interesting article from The Economist print edition
----------------------------------
It is less random than people thought
FEW questions are simultaneously so baffling and so significant as: “what is the structure of the Internet?” Baffling, because the thing has grown without any planning or central organisation. Significant, because knowing how the routing computers that are the net's physical embodiment are interconnected is vital if it is to be used properly. At the latest count, there were 228,265 of these routers around the world. They direct the packets of data that make up Internet traffic.
Any effort to map the Internet is necessarily incomplete and out of date the moment it appears. Instead, Albert-Laslo Barabasi and his colleagues at the University of Notre Dame, in Indiana, treat the net as though it were a natural phenomenon. What scientists generally do with a natural phenomenon that they do not understand is to build a model of it. Dr Barabasi's latest paper on the matter, just published in the Proceedings of the National Academy of Sciences, presents a general framework for improving the accuracy of Internet models.
Until 1999, the standard way of modelling the Internet was to use randomly generated graphs, in which routers were represented by points and the links between them by lines. But it turns out that such random graphs are a poor approximation because they miss two important features. The first is that links in the net are “preferentially attached”: a router that has many links to it is likely to attract still more links; one that does not, will not. The second is that the Internet has more clusters of connected points than random graphs do. These two properties give the Internet a topology that is scale-free—in other words, small bits of it, when suitably magnified, resemble the whole.
Dr Barabasi noticed that the World Wide Web (the most visible bit of the Internet) was scale-free in 1999. His observation touched off a flurry of research, and others pointed out that the Internet as a whole was scale-free, too. This has several implications. On the one hand, scale-free topology is resistant to random failures—one reason the Internet, despite the lack of artifice in its design, has proved so reliable. On the other hand, because there are disproportionately many hubs (as well-connected routers are known), the net is particularly susceptible to deliberate attacks on those hubs, the sort of thing that cyberterrorists might attempt.
The goal, Dr Barabasi says, is to create models that are statistically indistinguishable from the real Internet. When and if that is achieved, the models should have predictive, as well as descriptive, power.
Already, understanding the net's scale-free structure has led to new results. For example, it had long been thought that the best way to curb the spread of a computer virus was to change the software of machines on the net so that they were less easily “infected”. Studies using random graphs had shown that changing the software on more and more machines had a cumulative effect. That is not true in a scale-free setting. There, most software changes make no difference to the rate at which a virus spreads (although they obviously protect the machines in question). However, treating a relatively small number of hubs in a scale-free system can stamp viruses out completely.
That observation may have implications beyond the virtual world. Research has shown that the network of human sexual partners seems to be scale-free, too. In other words, some people have all the luck, while others have none. So stopping the spread of a disease such as AIDS may be a comparatively simple matter of getting treatment to the right people—a strange but real corollary to a piece of research on cyberspace.