Slashdot Mirror

← Back to Stories (view on slashdot.org)

Snowflake-Shaped Networks Are Easiest To Mend

Posted by Soulskill on from the networks-that-make-it-feel-like-christmas dept.

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.

12 of 38 comments (clear)

  1. A spanning tree? by Livius · · Score: 2

    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.

  2. When drawn... by itzly · · Score: 4, 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.

    1. Re:When drawn... by peragrin · · Score: 4, Insightful

      And star topology doesn't look like a star either except for when you try to make them look like stars.

      --
      i thought once I was found, but it was only a dream.
    2. Re:When drawn... by aaarrrgggh · · Score: 3, 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.

  3. Based on a false premise? by Immerman · · 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.

    --
    --- Most topics have many sides worth arguing, allow me to take one opposite you.
    1. Re:Based on a false premise? by sjames · · Score: 3, 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.

    2. Re:Based on a false premise? by PPH · · Score: 2

      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 regulations or mayors and county councilmen losing the next election. Also, these redundant loops are rarely completed at the time the failure occurs. The capability to provide an alternate source is something that is planned and constructed in advance, based upon the criticality of the loads (see politics) as well as the probability of a failure in the normal path.

      --
      Have gnu, will travel.
  4. Really? by Chocolate+Teapot · · Score: 3, Funny

    Wouldn't a snowflake shaped network be susceptible to rapid meltdown?

    --
    Modest doubt is called the beacon of the wise. - William Shakespeare
  5. What redundancy? by fustakrakich · · Score: 2

    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!”
  6. Re:spider web? by khasim · · Score: 2

    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 configuration.

  7. Re:no? by ChumpusRex2003 · · Score: 4, Informative

    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.

  8. Repairs are often bottlenecks by Technician · · Score: 2

    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!