An Overview of Algorithms for Network Survivability

Network connectivity

 

  

 

  

 cut

  

   

   

   

  

   

  s-t cut

   

    

  link cut

   

network augmentation

 node augmentation

  

  unweighted node augmentation

   unweighted K node augmentation

    2 node

     Eswarn

    3 node

     watanabe

    empty graph K node

     harary

    directed tree K node

     masuzawa

    undirected tree K node

     Sun

   Summary

(unweighted K node augmentation)

  weighted node augmentation

   weighted R node augmentation

   weighted 2 node augmentation

   weighted K node augmentation

 edge augmentation

  

   

   For fixed β, the unweighted simple graph preserving problem can be solved in polynomial time

    ”Augmentation problems“

   cactus graph

if any two distinct simple cycles in G have at

most one node in common (or equivalently, any link of G

belongs to at most one cycle

    

    "A fast algorithm for optimally increasing the edge connectivity"

     a polynomial-time algorithm to augment the link connectivity of a graph G from λ to λ + β, by adding the smallest number of (possibly parallel) links

    property

   The weighted LCA problem is NP-hard

    3-dimensional matching(3DM)problem is reducible to the weighted LCA problem

   Summary

()

  unweighted

   unweighted K edge augmentation

    2 edge

     Eswarn

      

    empty graph K edge

     habib

    directed tree K node

     sun

    tree graph K node

     kajitani

  weighted

   weighted R edge

   weighted 2 edge

   weighted K edge

 connectivity theorem

  Menger theorem

Let G be a finite undirected graph and x and y two distinct vertices. Then the theorem states that the size of the minimum edge cut for x and y (the minimum number of edges whose removal disconnects x and y) is equal to the maximum number of pairwise edge-independent paths from x to y.

   

  mader theorem

   

 strong connectivity augmentation

path protection

 restoration

  it may take a longer time for recovery

 protection

  it is less efficient in terms of capacity utilization and less flexible

 how rerouting

  Path-based protection/restoration

  Link-based protection/restoration

   

 whether sharing of resources

path protection requires less capacity than

link protection, while shared protection requires less capacity

than dedicated protection. However, path protection is more

vulnerable to multiple link failures than link protection, and

so is shared protection compared to dedicated protection

  Dedicated protection

  Shared protection

 

  Min-SumDisjoint Paths Problem

   the min-sum disjoint paths problem with min-max, min-min, bounded, and widest, as secondary objectives in casemultiplemin-sum paths

  Min-Max Disjoint Paths Problem

  Min-Min Disjoint Paths Problem

  Bounded Disjoint Paths Problem

  Widest Disjoint Paths Problem

The smallest capacity over all

links in the two paths is maximized.

  maximumbandwidth maximally disjoint paths and minimizes the total weight as a secondary objective

  Multiple Failures

   (ii) In case of terrorist attacks, several targeted parts of the network could be damaged

   (i) Due to lengthy repair times of network equipment, there is a fairly long time span in which new failures could occur.

   (iii) In layered networks, for instance IP-over-WDM, one failure on the lowest-layer network, may cause multiple failures on higher-layer networks.

   (iii) In layered networks, for instance IP-over-WDM, one failure on the lowest-layer network, may cause multiple failures on higher-layer networks(SRLG)

   (iv) Natural disasters may affect all nodes and links within a certain geographical area.

 p-survivable connection

Quality of Protection (QoP),