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.
Can someone explain how this new 'investigation' is different from chapter two of my fifty-year-old network textbook*?
*Graph Theory with Applications, Bondy and Murty, 1976.
Interesting. I would have expected spider-web style networks to be the most resilient. Maybe ease of repair factors in the number of connections and spiderweb is overly connected?
how does zero redundancy make "the best networks"?
When drawn, they look remarkably like snowflakes, which have a similar branching structure.
Except that the there's no basis for the hexagonal outline, except when remarkably trying to make them look like snowflakes.
assuming that expense increases with the length of a rebuilt link
Sounds like a pretty unlikely assumption to me - when something breaks a power line don't they usually splice in a localized repair rather than replacing the entire length between nodes? Which suggests that all broken links would be roughly the same price to repair (barring terrain difficulties, etc) regardless of length, completely invalidating the results of the study.
--- Most topics have many sides worth arguing, allow me to take one opposite you.
Looking at the snowflake diagram with the linked to article I'm not seeing any partial loops in the snowflake diagram. In fact, it only shows single connectivity back to one core hub. Maybe it's just a poor drawing or I'm missing something in the translation. Also, there doesn't seem to be any redundancy. By not having access to the full article, maybe I'm not understanding the use-case for this.
Wouldn't a snowflake shaped network be susceptible to rapid meltdown?
Modest doubt is called the beacon of the wise. - William Shakespeare
Our network designs could learn a lot from organisms that interact over similar structures, such as mushrooms.
AT&T owns the entire pipe. "delicate" snowflakes indeed. Our networks are fragile due to their monopoly status.
“He’s not deformed, he’s just drunk!”
performance = 1 / robustness
Often the reapair is on smaller lower capacity branches that can not handle the load. On a network, this results in slow connections. On a power grid this results in cascading failures of the alternate routes. This is what blacked out the East Coast of the US some years ago. A major line failed shifting the load to smaller lines unable to sustain the load. This resulted in a large area ripping free of the rest of the grid as none of the smaller route could carry the load.
http://en.wikipedia.org/wiki/N...
http://en.wikipedia.org/wiki/N...
The truth shall set you free!
See, the special snowflakes are made of stronger stuff than you think. They can be taken to cinder gardens without worry.
And don't fuck network jacks. Unless it's a guy named Jack who builds networks.
If you even slightly criticize the performance a special snowflake type network,or expect it to work to even a fraction of its stated capacity, the network will suddenly do down and refuse to function until after a long cool down period or you make a fake apology.
Which page?
http://www.iro.umontreal.ca/~hahn/IFT3545/GTWA.pdf
After going through it, I can't find the specific snowflake patterns in it?
Increasing the number of nodes may not be cheaper, could you imagine tripling the number of power substations?
Easily repairable networks (arXiv version). Why not link to the open access paper when the authors bothers making it public?
TFA says the snowflake is a good model for networks that are inexpensive to repair, not necessarily robust. Considering that most repairs will happen at level 2 or level 3, that may be true ON AVERAGE. As the number of total nodes grows, I bet there is a point where the central node, which supports the most connections, becomes the expected common failure mode of this kind of network. Not only is the central node, by necessity, the most complex and by far the most expensive to repair (every level 1 function is down at this point), because of its complexity it may also have the shortest mean time between failures.
As soon as you see this and try to go back to a redundant central node, the next level nodes become vulnerable. And so on. Vulnerability propagates down the levels. The snowflake, er, melts down.
Maybe there needs to be a limit to the number of branches per node....but then you will have more than 3 levels.
Is this an attempt from mathematicians to try to tell engineers they have been doing it wrong?
This seems to be a very easy conclusion if you don't have to think of all the other things you need to think of when you do things in the real world.
And I can't see any problems solved with the conclusion of this paper.