Shared Risk Link Group Enumeration of Node Excluding Disaster Failures

Current backbone networks are designed to protect a certain pre-defined list of failures, called Shared Risk Link Groups (SRLG). During network design and operation protecting a failure not part of an SRLG is ignored as they assume to be extremely rare events. The list of SRLGs must be defined very carefully, because leaving out one likely failure event will significantly degrade the observed reliability of the network. The list of SRLGs is typically composed of every single link or node failure. It has been observed that some type of failure events manifested at multiple locations of the network, which are physically close to each other. Such failure events are called regional failures, and are often caused by a natural disaster. In this study we focus on link failures only and assume nodes are never part of the failure. We provide a fast systematic approach for generating a list of SRLGs the protection of which is essential to increasing the observed reliability of the network. According to some practical assumptions this list is very short with O(|V|) SRLGs in total, and can be computed very fast, in O(|V|log|V|) time.