devices arranged fractally
Technology Research News
Scientists 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
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
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,"
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
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
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
Chemists brew tiny wires
Voiceprints make crypto
Stamp corrals tiny bits
Net devices arranged
Quantum scheme lightens
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link