Paper Info
Title
Enumerating Maximal Shared Risk Link Groups of Circular Disk Failures Hitting <italic>k</italic> Nodes
Abstract
Many recent studies shed light on the vulnerability of networks against large-scale natural disasters. The corresponding network failures, called regional failures, are manifested at failing multiple network elements that are physically close to each other. The recovery mechanisms of current backbone networks protect failures listed as Shared Risk Link Groups (SRLGs). We aim to design an algorithm for the routing engines, which can generate a reasonable list of SRLGs based on the limited geometric information available. As a first step towards this direction, in this paper, we propose a limited geographic information failure model for the network topology that enables efficient algorithms to compute the set of links that are expected to be close to each other. More precisely, we work with (1) relative node positions without knowing the real distances, (2) an area in the map defines the route of each physical cable, and (3) a regional failure is a circular disk with k=0,1, ... nodes in its interior. We describe an efficient algorithm for listing SRLGs based on our limited geographic information failure model and show that under realistic assumptions, the obtained list of SRLGs is short, having approximately 1.2 n and 2.2n elements for k=0 and k=1, respectively, where n is the number of nodes of the network.
Year
DOI
Venue
2021
10.1109/TNET.2021.3070100
IEEE/ACM Transactions on Networking
Keywords
DocType
Volume
Shared Risk Link Groups (SRLGs),SRLG enumeration,disaster resilience,survivable networks,limited geometric information model,Voronoi diagrams
Journal
29
Issue
ISSN
Citations 
4
1063-6692
1
PageRank 
References 
Authors
0.35
0
3
Name
Order
Citations
PageRank
Balazs Vass182.83
János Tapolcai236441.42
Erika R. Bérczi-Kovács3113.94