Enumerating Shared Risk Link Groups of Circular Disk Failures Hitting k Nodes

Inhalt:
Current backbone networks are designed to protect a certain pre-defined list of failures, called Shared Risk Link Groups (SRLG). 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. The aim of the paper is to bring the conventional SRLG based pre-planned protection and regional failures closer to each other by providing a systematic approach to generate the list of SRLGs for regional failures. In our study we overestimate the regional failures with failures having a shape of circular disk; however, instead of fixing the radius we classify the regional failures according to the network elements they hit. In particular we are interested in the number of nodes the failure can hit. Formally, we focus on circular disk failures that hit exactly k nodes, where k is part of the input. According to simulation results, this list is short with O((k+1)|V|) SRLGs in total, and can be computed in O(|V|³), where V denotes the set of the nodes. Applying the obtained SRLG list network operators can design their networks to be protected against regional and random failures.