This book presents a comprehensive study covering the design and application of models and algorithms for assessing the joint device failures of telecommunication backbone networks caused by large-scale regional disasters. At first, failure models are developed to make use of the best data available; in turn, a set of fast algorithms for determining the resulting failure lists are described; further, a theoretical analysis of the complexity of the algorithms and the properties of the failure lists is presented, and relevant practical case studies are investigated. Merging concepts and tools from complexity theory, combinatorial and computational geometry, and probability theory, a comprehensive set of models is developed for translating the disaster hazard in informative yet concise data structures. The information available on the network topology and the disaster hazard is then used to calculate the possible (probabilistic) network failures. The resulting sets of resources that are expected to break down simultaneously are modeled as a collection of Shared Risk Link Groups (SRLGs), or Probabilistic SRLGs. Overall, this book presents improved theoretical methods that can help predicting disaster-caused network malfunctions, identifying vulnerable regions, and assessing precisely the availability of internet services, among other applications.
Author(s): Balázs Vass
Series: Springer Theses
Publisher: Springer
Year: 2022
Language: English
Pages: 129
City: Cham
Supervisor’s Foreword
Acknowledgements
Contents
1 Introduction
1.1 Example Use-Cases of SRLG and PSRLG Lists
1.2 Problem Statement
1.3 Overview of this Thesis
1.4 Contributions of this Thesis
References
2 Formal Problem Statement
2.1 Definition of (Probabilistic) Shared Risk Link Groups
2.2 Physical Embedding of the Network Topology
2.3 Disaster Families and Related Induced Failures
2.3.1 SRLG Enumeration: Disasters with Limited Size
2.3.2 SRLG Enumeration: Disasters for Schematic Embeddings
2.3.3 PSRLG Failure Modeling
2.4 General Practices for SRLG Enumeration
2.5 Problem Statement
2.6 Model Extensions
2.6.1 Segment Link Representation to Polylines, Polylines to Containing Polygons
2.6.2 Different Link Types
2.6.3 Mixed Link Types
2.6.4 Nodes Also Considered Vulnerable
References
3 Related Work
3.1 Charting the Landscape of (P)SRLG Enumerating Problems
3.2 (P)SRLG Enumeration or Finding Worst (P)SRLG
3.2.1 SRLG Enumeration
3.2.2 PSRLG Enumeration
3.3 (P)SRLGs as Input
3.4 Computational Geometry and Seismology
References
4 Algorithmic Background
4.1 The Big O Notation
4.2 Time and Space Complexity
4.3 Computational Geometry: Sweep Line Algorithms
References
5 Maximal SRLGs Induced by Disks with Radius r
5.1 Planar Regional Link Failures Caused by Disasters with Radius r
5.1.1 Problem Definition and Basic Results
5.1.2 Bounds on the Number of SRLGs
5.1.3 Improved Bounds and Algorithm to Enumerate the Set of SRLGs
5.1.4 Auxiliary Proofs of Section 5.1
5.2 Spherical Regional Link Failures of Disasters with Radius r
5.2.1 Model and Assumptions
5.2.2 Heuristic Algorithm for Enumerating Maximal Circular Disk Failures
5.3 Are SRLG Lists for Spherical and Planar Network Representation the Same?
5.4 Thesis Summary
References
6 Maximal SRLGs Caused by Circular Disks Hitting k Nodes
6.1 The Limited Geometric Information Failure Model - Informally
6.2 Model and Assumptions
6.3 Algorithm for Enumerating Maximal Failures
6.3.1 Basic Observations
6.3.2 Connection with the k-Delaunay Graphs
6.3.3 Data Structure Apple
6.3.4 Sweep Disk Algorithms
6.3.5 Determining Apples
6.3.6 Computing the Set of SRLGs by Sweeping Through Each Apple
6.3.7 Algorithm for Computing Maximal Failures
6.4 Parametrized Complexity Bounds for Enumerating SRLGs of Mk2
6.4.1 Parametrized Complexity Bounds for Determining Apples
6.4.2 Parametrized Bound for Determining Mku,v for Apple Aku,v
6.4.3 Parametrized Complexity Bound on Merging Lists Mku,v
6.4.4 Parametrized Complexity for Computing Mk2
6.5 Parametrized Algorithm for Enumerating SRLGs in Mk1
6.5.1 Data Structure Seesaw
6.5.2 Querying Seesaws
6.5.3 Connection Between Seesaws and Apples
6.6 Miscellaneous
6.6.1 Computational Geometry: Determining x+ (e) and x- (e) in O(γ)
6.6.2 Extreme Cases: Maximum Number of Maximal Failures
6.6.3 Protecting Regional Link 0-Node Failures Ensures Node Disjointness
6.7 Simulation Results
6.7.1 The List of SRLGs in Practice
6.7.2 Tightness of Corollary 6.3.17
6.8 Thesis Summary
References
7 PSRLGs Modeling Correlated Link Failures Caused by Disasters
7.1 Network Model and Framework to Compute Service Availability
7.1.1 Network Model
7.1.2 Framework to Compute Service Availability
7.1.3 On Availability Queries When Risk Failures Are Correlated
7.1.4 Denomination Issues of Probabilistic SRLGs
7.2 The Regional Failure Model
7.2.1 Stochastic Modeling of Regional Failures
7.2.2 The Failure Probability of a Link Set
7.2.3 Example of the Geographical Correlation of Failures
7.3 Pre-Computation to Speed up Queries
7.3.1 Precomputation of CFPs and FPs
7.4 Space and Time Complexity of Structures CFP[G] and FP[G]
7.4.1 Cardinality of Structures FP[G] and CFP[G]
7.4.2 Query Time of Structures FP[G] and CFP[G]
7.5 Implementation Issues
7.5.1 Structure CFP[G]
7.5.2 Structure FP[G]
7.6 Model Evaluation Based on Seismic Hazard Data
7.6.1 Seismic Hazard Representation
7.6.2 Simulation Results
7.7 An End Note on the Geometric Transformation of the Network
7.8 Thesis Summary
References
8 Conclusion
8.1 Summary
8.2 Open Problems
8.3 Possible Future Work
References
Appendix Afterword
Author Biography
