Slashdot Mirror
Snowflake-Shaped Networks Are Easiest To Mend
Z00L00K sends this report from New Scientist:
Networks shaped like delicate snowflakes are the ones that are easiest to fix when disaster strikes. Power grids, the internet and other networks often mitigate the effects of damage using redundancy: they build in multiple routes between nodes so that if one path is knocked out by falling trees, flooding or some other disaster, another route can take over. But that approach can make them expensive to set up and maintain. The alternative is to repair networks with new links as needed, which brings the price down – although it can also mean the network is down while it happens.
As a result, engineers tend to favor redundancy for critical infrastructure like power networks, says Robert Farr of the London Institute for Mathematical Sciences. So Farr and colleagues decided to investigate which network structures are the easiest to repair. They simulated a variety of networks, linking nodes in a regular square or triangular pattern and looked at the average cost of repairing different breaks, assuming that expense increases with the length of a rebuilt link. ... They found the best networks are made from partial loops around the units of the grid, with exactly one side of each loop missing (abstract). All of these partial loops link together, back to a central source. ... These networks have three levels of hierarchy – major arms sprouting from a central hub that branch and then branch again, but no further. When drawn, they look remarkably like snowflakes, which have a similar branching structure.
As a result, engineers tend to favor redundancy for critical infrastructure like power networks, says Robert Farr of the London Institute for Mathematical Sciences. So Farr and colleagues decided to investigate which network structures are the easiest to repair. They simulated a variety of networks, linking nodes in a regular square or triangular pattern and looked at the average cost of repairing different breaks, assuming that expense increases with the length of a rebuilt link. ... They found the best networks are made from partial loops around the units of the grid, with exactly one side of each loop missing (abstract). All of these partial loops link together, back to a central source. ... These networks have three levels of hierarchy – major arms sprouting from a central hub that branch and then branch again, but no further. When drawn, they look remarkably like snowflakes, which have a similar branching structure.
The aim was not to find the "best network", but the "best network without redundancy".
The point was that most networks are designed with redundancy in mind, but not all networks require that degree of reliability. For those networks where reliability is not necessary, it would be helpful to know what the lowest cost configurations are.
Actually, a number of analysis over the years have shown that you need to limit non-isolatable nodes in a system to a maximum of six, there is also a substantial body of evidence that N+1 redundancy only adds redundancy for less than 6 units total. It would seem their analysis also relies on the ability to limit the number of nodes post-repair.
The idea may not be new, but the expression is interesting.