New threshold for network stability
Connecting state and local government leaders
Researchers argue it's not how many links you have, but how well you use them.
Your network may not be as robust as you may think, according to calculations by a number of government and academic researchers.
Eduardo L'pez, a researcher for the Energy Department's Los Alamos National Laboratory, led a team to further define the point at which complex networks become unstable, inefficient or even unusable. Thanks to a further refinement in a mathematical notion known as percolation theory, they found these thresholds lower than previously assumed.
Complex networks such as the Internet gain resilience by having multiple nodes and multiple connections among the nodes, said Lopez, who works in the theoretical division at the lab's Center for Nonlinear Studies. So even if one hub is destroyed, traffic flowing through a network may travel via other hubs.
Traditional thinking assumes that as long as at least one workable path remains through a damaged network, the network is reliable. This is how percolation theory is used to calculate whether a network is workable. With this theory, "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 coauthor Roni Parshani, a graduate student at Bar-Ilan University in Ramat Gan, Israel.
What this model does not take into consideration, the researchers said, is how long it would take a message to reach 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 entitled, "Limited path percolation in complex networks," which 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 to the shortest possible paths previously available. The longer it takes, the less likely it would be of value to the recipient, hence making the network, for all practical purposes, useless, the researchers said.
"The percolation threshold in many networks is not the important point," Parshani said. "When you start removing nodes, and the network becomes diluted, a path between two nodes increases significantly. If it is very, very long, it is like the two nodes are not connected any more."
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 inherit 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, Parshani said. For most cases, the cutoff point between a usable and unusable network is lower by the new calculations than that offered by standard percolation theory.
Such work may be interesting to those agencies that must keep complex networks running at a high level of reliability, or those agencies that must run networks where stability is difficult or impossible to maintain. The Defense Advanced Research Projects Agency, for instance, has been funding work in what is called Delay Tolerant Networking, a set of Internet protocols that can be used to pass messages across a set of nodes that are unstable or otherwise not always available.
The work was not limited to computer networks, but any sort of interlinked systems. The viral propagation of diseases would also fit under this model, Lopez said. Using these same calculations, however, people may find good news, as the point at which a mass infection may be contained would be lower than previously assumed, as the work that infecting agent must go through to spread would be higher than feasible.
"We're not changing the reality,' Parshani said, 'just giving you a more accurate prediction of what you need."
NEXT STORY: NIST finds nano clue to better semiconductor