Snowflake-Shaped Networks Are Easiest To Mend 38
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.
A spanning tree? (Score:3)
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.
Re: (Score:1)
Of course it's probably all in that tome, this is all rediscovery of some very organic concepts that relate to networks when you apply them to that.
It's all geometry.
Re: (Score:2)
Rounding to integer numbers of decades is actually easier than it looks.
Re: (Score:2)
Not for you apparently.
spider web? (Score:1)
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?
Re: (Score:3)
They would be the most resilient. But they'd also be expensive.
I THINK that TFA was looking to minimize cost. Which could be why their diagram does not seem to show ANY redundant links.
In fact, I don't understand what their diagram is showing. Unless it is ancient 10base5 with vampire taps. Otherwise why are the 6 main "arms" continuing after the first connection? That doesn't look like a router diagram. Maybe it is a series of switches (or hubs) linked off of each other in a really badly designed cascaded
no? (Score:1)
how does zero redundancy make "the best networks"?
Re:no? (Score:5, Informative)
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.
When drawn... (Score:5, Funny)
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.
Re:When drawn... (Score:5, Insightful)
And star topology doesn't look like a star either except for when you try to make them look like stars.
Re: (Score:2)
Except for the chocolate star topology. It does look identical to...
a chocolate star.
Re:When drawn... (Score:4, Informative)
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.
Based on a false premise? (Score:5, Interesting)
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.
Re:Based on a false premise? (Score:4, Insightful)
They also (for some reason) assumed that repairing the link required building a new link alond a new path. I can't imagine why they believed that to be common.
They also didn't factor in that it often costs more to make a repair RIGHT NOW than it does to repair it sometime this week.
Re: (Score:3)
when something breaks a power line don't they usually splice in a localized repair
Exactly. The cost is proportional to the type of line (link) and type of damage.
The loop vs star configuration (the former providing a redundant path) is more important for timely restoration rather than repair. It is very rare that a link isn't eventually repaired. But sometimes this can take days or weeks. The value of the redundant path is to restore service to customers in a timely manner (minutes or hours). Here, the cost of the outage is harder to quantify and usually involves things like reliability
I'm not sure I understand this.... (Score:2)
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.
Really? (Score:4, Funny)
What redundancy? (Score:2)
AT&T owns the entire pipe. "delicate" snowflakes indeed. Our networks are fragile due to their monopoly status.
snowflake obvious? (Score:1)
performance = 1 / robustness
Repairs are often bottlenecks (Score:3)
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... [wikipedia.org]
http://en.wikipedia.org/wiki/N... [wikipedia.org]
arXiv version (Score:1)
Common mode failures (Score:1)
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 funct
Re: (Score:1)
Real engineering is always a compromise between different sets of bad choices..
hm? (Score:1)
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.