Computationally Efficient Network Survivability Assessment

A non-transitory computer-readable medium storing instructions for assessing survivability in a network, the instructions, when executed, cause one or more processors to perform steps of:

• receiving a representation of the network comprising a plurality of nodes and links, wherein each link is associated with at least one shared risk link group (SRLG);
• constructing an undirected graph corresponding to the network, wherein vertices represent the nodes and edges represent the links;
• applying a Stoer-Wagner min-cut algorithm, extended to account for SRLGs, to identify a minimal set of edges whose simultaneous failure would disconnect at least one node from a remainder of the network, wherein links that share an SRLG are treated as a single potential failure event;
• and
• providing the minimal set as critical cuts corresponding to an SRLG-based failure scenario.

A system configured for assessing survivability in a network, the system comprising:

• one or more processors;
• and
• memory storing instructions that, when executed, cause one or more processors to
• receive a representation of the network comprising a plurality of nodes and links, wherein each link is associated with at least one shared risk link group (SRLG),
• construct an undirected graph corresponding to the network, wherein vertices represent the nodes and edges represent the links,
• apply a Stoer-Wagner min-cut algorithm, extended to account for SRLGs, to identify a minimal set of edges whose simultaneous failure would disconnect at least one node from and a remainder of the network, wherein links that share an SRLG are treated as a single potential failure event, and
• provide the minimal set of edges as critical cuts corresponding to an SRLG-based failure scenario.