Traffic
model maps congestion
By
Kimberly Patch,
Technology Research NewsWhat do slime mold, airline traffic, fungi, cancer tumors, and computer networks have in common? They all transport something -- nutrients, planes, or information -- from one place to another.
Although there are many examples of systems that solve the classic problem of getting from point A to point B, the extent to which decentralized, or perimeter routes, versus centralized, or hub-like routes benefit the complicated networks of the real world remains an open question.
Researchers from Oxford University in England have tackled the problem by examining the congestion costs within a network model that combines paths that go around the perimeter of the network and central hubs that provide shorter paths through the network. Real-world networks are too complicated to describe exactly mathematically. The researchers' model is simple enough to solve exactly, yet realistic enough to provide insights into real networks.
The research is aimed at finding ways to ease bottlenecks in networks involving manufacturing, the Internet and traffic, and ways to disrupt networks like tumor blood flow and terrorist supply chains. The findings could also help design better networks.
"This general scenario of passing packets -- cars, data, food, information, documents -- between two points occurs in a wide range of systems, said Neil Johnson, Professor of Physics at Oxford University. These include roads, air traffic, the Internet and communications networks, fungi, crime networks, cancer tumors, large organizations, and supply chains, he said.
In each case, the same interplay between centralized and decentralized pathways and control arises. "Going through the center has the advantage of shorter distance but has a higher risk of congestion and hence longer overall journey-time," said Johnson. "Going around the center has a lower risk of congestion but a larger geographical distance," he said.
In the case of traffic near Boston, the best route from the town of Braintree, which lies south of Boston, to Woburn north of Boston depends on traffic. The optimal pathway could be centralized -- straight through Boston -- or decentralized -- around Boston on Route 128, or even a combination of the two, said Johnson.
In the case of fungi, which can grow to an area of many square feet in forests, its outer edges come across patches of food that it needs to distribute to keep all of its parts alive. "In particular, it needs to get things from one side to the other of the circumference of the fungus -- so it is a great example of our centralized versus decentralized traffic problem," said Johnson. But nobody knows how these nutrients pass from one side of the structure to another, he said.
In contrast to network models that examine network structure, the researchers' model focuses on congestion.
The model is a busy wheel-and-spoke road network that feeds cars into the center at a steady rate. The cars experience a bottleneck in the center which adds a delay or cost to the journey time, said Johnson. At the same time, cars that travel around the ring road typically have to travel further, but experience no cost.
"So the question is, for a given cost, what is the optimal number of roads carrying traffic into the center -- where optimal means that a driver going from A to B and free to use the ring road, the roads to the center, or some combination of the two -- will typically have the shortest journey time?" said Johnson.
The details of the roads in the city center will determine exactly what time delay drivers using the hub will experience, said Johnson. The number of roads feeding cars into the center, and hence how many cars are being fed into the center also affects the cost, he said.
In the simplest case no delay arises, the cost is zero, and it is always better to add more roads through the center. When the cost increases with the number of roads to the center, however, there is an optimal value for the number of roads, said Johnson. For a 1,000-node network with a cost-per-connection to the hub of 1, the optimal number of connections to the hub is 44.
The model showed that above a certain number of roads to the center, adding a new road always increases the bottleneck to such an extent that the added benefit of a new route is outweighed by the time delay due to increased congestion in the center. "The interesting and counter-intuitive result that we found is that in such situations we should actually reduce the number of roads connecting to the center," said Johnson.
The problem can also be turned on its head, said Johnson. "Given the number of roads which exists to the center and which we assume cannot easily be changed, what cost should be imposed for passing through the center [so] that drivers between A and B experience a minimum journey time," he said. "This charge could be an artificially induced time-delay -- lights or ramps with long waiting times -- or monetary."
The researchers' model showed that in London, where a flat fee of five pounds is charged for passing through the center, a usage-dependent cost would make the network more efficient. "These costs could be advertised on electronic boards around the ring road so that people decide ahead of time whether to use the center or not," said Johnson.
The model shows that the structure of a network is only part of the story of why systems work the way they do, said Johnson. In biological systems, and perhaps also in technological ones, it might be possible for a network to spontaneously rewire itself to respond to traffic. "Maybe this is what we are observing in nature when we see, for example, that different fungi have different types of network shapes," said Johnson.
"Taking it to a more speculative level, maybe… the network structures that we observe in nature have their structure emerging from their function rather than the other way round," said Johnson.
The researchers' next step is to build more complicated networks that can still be treated mathematically. "We will do this by embedding the exactly-solved part that we already have as a building block [of a] larger network -- like a network within a network," said Johnson.
They are planning to team up with another research group to monitor the real flow of nutrients in fungi to see if there is an identifiable biological cost of traveling through the center that nature has developed to balance nutrient flow.
"We can ask what effective cost can be deduced in a system such as a fungus by studying the flow of food around the structure," said Johnson. "We can then deduce what cost schemes biology seems to be imposing to self-regulate the nutrient flow in objects such as a fungus which don't have a centralized brain or control center," he said.
Johnson's research colleagues were Douglas J. Ashton and Timothy C. Jarritt. The work appeared in the February 11, 2005 issue of Physical Review Letters.
Timeline: > 2 years
Funding: University
TRN Categories: Physics; Networking
Story Type: News
Related Elements: Technical paper, "Effect of Congestion Costs on the Shortest Paths through Complex Networks," Physical Review Letters February 11, 2005
Advertisements:
July 27/August 3, 2005
Page One
Stories:
Traffic model maps congestion
Fingernails store data
Quantum crypto scheme doubly fast
How It Works: Internet Structure
Briefs:
Baited molecule fights cancer
Bacteria drive biochip sensor
System brightens dark video
Micro fuel cell packs power
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.
