Net
devices arranged fractally
By
Kimberly Patch,
Technology Research NewsScientists working to make the Internet run more smoothly often rely on simulations of the Net to see how infrastructure tweaks and changes would affect the global network before subjecting the rest of us to live changes.
The trouble is, the Internet's infrastructure is very complicated, and existing simulations tend to oversimplify things. Scientists working to divine the nature of Internet growth are looking to improve these models.
Researchers from the University of Notre Dame have found a clue about network complexity in the physical placement of the Internet's routers, which act as the network's traffic cops. While network models generally place routers at random intervals, in reality routers are physically arranged in a fractal pattern. "The fractal pattern is... the way the routers are placed in space," said Albert-László Barabási, a professor of physics at the University of Notre Dame.
Routers' physical locations are different from the virtual setup of the Net, where links from one router, or node, to the next are dictated by software protocols rather than physical communications lines. The physical router distribution pattern the researchers found is distinct from the virtual link structure, said Barabási. Previous research has already established that the link structure has a fractal pattern. The physical fractal pattern is one more variable that affects the behavior of the network as a whole.
Fractal patterns can be represented by mathematical formulas, and are present in many systems, including fluctuations in the stock market, the distribution of galaxies in the universe, the turbulent flow of liquids, biological growth, and coastlines.
The patterns repeat, and are self-similar, meaning segments of many different-size portions of a pattern look the same as the whole. For instance, the scattered pattern of Internet router locations that shows up on a map of the entire Internet is also discernible on maps of various-size portions of the Internet.
Fractal systems are also nonlinear. Linear systems react in an orderly and predictable way that reflects the magnitude of a stimulus. In contrast, nonlinear systems are much less predictable, and are often very sensitive to small changes.
The researchers found that router density correlates with population density around the world, which is fractal. There are strong, visually evident correlations between router and population density in economically developed areas of the world, according to Barabási. High population density implies a higher demand for Internet services, which results in more routers in those areas.
The pattern of routers' physical distribution comes into play in two ways. The fractal nature of router density is one, said Barabási. In addition, nodes tend not to connect to nodes that are too far away, and this "imposes certain limitations on the network topology," he said.
It takes time and resources to connect Internet routers, and network designers tend to prefer to connect to the closest node that has enough bandwidth, according to Barabási. The costs of physically linking two routers include the technical and administrative costs at the two routers, and the cost and maintenance of the physical line that must run between them. This clearly favors shorter links, according to Barabási.
The fractal pattern of router placement checks with empirical evidence about the structure of the Internet, according to Barabási. This empirical evidence includes the Internet's power-law, or scale-free nature, with a few nodes having many connections while many nodes have only a few connections.
Combined with recent research into the nature of link bandwidth and traffic, this new information could help network designers anticipate congestion resulting from the Internet's quick, decentralized growth, according to Barabási.
Understanding the impact of router placement on network topology is also important in understanding other types of networks, Barabási said. "The distance dependence is present in social networks as well -- you tend to be friends with people at work or who live in your neighborhood, and not with people across the globe," he said. It also shows up in biological networks. "Our brain cells tend to connect to cells that are nearby," said Barabási.
The study is suggestive and worth exploring, said Jon Kleinberg, an associate professor of computer science at Cornell University. It remains to be seen exactly what effect this topology has on performance, he added. "The next step would be to ask how [this] affects the function of the network -- the performance of protocols" like those that control routing, he said.
Studies that reveal the structure of networks like the Internet are important because the Net is a growing phenomenon, Kleinberg said. "That it keeps growing and everything keeps working so gracefully as it grows at this unbelievable rate is really because of a huge [amount] of hard work going on beneath the surface -- people designing new protocols, simulating them, deploying them," he said. "Working out good models of topology is one component of that."
In a separate study, a group of researchers from Boston University drew similar conclusions about the geographical properties of the Internet.
The Boston University study involved recording the locations of large inventories of Internet routers and links on two occasions two years apart. The study found a quantitative relationship between population density and router density similar to the Notre Dame study, and also showed that router density per person is higher in population centers. The Boston University study also found that 75 to 95 percent of connections between routers strongly relate to the geographical distance between them.
The fractal nature of router distribution could be taken into account in Internet network models within a few months, said Barabási.
Barabási's research colleagues were Soon-Hyung Yook, and Hawoong Jeong. They published the research in the September 30, 2002 issue of the Proceedings of the National Academy of Sciences. The research was funded by the National Science Foundation.
The Boston researchers were Anukool Lakhina, John W. Byers, Mark Crovella and Ibrahim Matta. The study was funded by the National Science Foundation.
Timeline: A few months
Funding: Government
TRN Categories: Internet; Physics
Story Type: News
Related Elements: Technical paper, "Modeling the Internet's Large-scale Topology," The Proceedings of the National Academy of Sciences, September 30, 2002; Technical paper, "On the Geographic Location of Internet Resources," Boston University computer science department technical report, May 21, 2002, www.cs.bu.edu/techreports/pdf/2002-015-internet-geography.pdf
Advertisements:
October 16/23, 2002
Page One
Chemists brew tiny wires
Voiceprints make crypto keys
Stamp corrals tiny bits
Net devices arranged fractally
Quantum scheme lightens load
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
