New threshold for network use
Researchers argue it's not how many links you have, but how well you use them
Have you ever been stuck on roads that were so clogged that you gave up, even knowing that you'd miss your appointment? People in Washington know this experience; the capital's Beltway can be practically unusable at times, particularly during rush hour.
That kind of impassibility ' and the question of whether alternate routes can get you there in time ' is the basis for a new system of judging network usability, derived by a team of mathematicians led by Eduardo L'pez, a researcher at the Energy Department's Los Alamos National Laboratory.
'If I'm routing something and it has to go a longer route, due to localized failures, then what are the limits of this?' L'pez asked.
'This kind of effect hasn't been taken into account in the majority of models.'
Complex networks such as the Internet gain resilience by having multiple nodes and multiple connections among the nodes, said L'pez, who works in the theoretical division of the lab's Center for Nonlinear Studies. So even if one hub is destroyed, traffic flowing through a network can travel via other hubs.
Traditional thinking assumes that as long as at least one workable path remains though a damaged network, the network is functional.
A well-known equation called percolation theory follows that thinking to calculate if a network is workable. With this approach, 'you take a network and you start removing links or nodes of the network until you reach a certain point when the network breaks down,' said co-author member Roni Parshani, a graduate student at the Bar-Ilan University, in Ramat Gan, Israel.
This model does not consider, the researchers say, how long it would take a message to get to its destination.
'The interesting point is not when the percolation threshold is reached, but rather when the network stops becoming efficient,' Parshani said.
In a paper that appeared in the Nov. 2 edition of Physical Review Letters, the researchers offer a new variant of percolation theory, called Limited Path Percolation.
This equation not only factors in all the surviving nodes, but also how much longer it would take to traverse the remaining nodes, as compared with the shortest possible paths previously available.
The longer it takes, the less likely it would be of value to a recipient, hence making the network, for all practical purposes, useless, the researchers argue.
Parshani stressed that this new point of breakdown would be based on the requirements of those relying on the network. The researchers' work offers an equation to balance the delay inherent in a damaged network against the urgency required for the mission that network serves.
The more tolerant you are of delays, the higher the threshold, he said.