TL;DR
This paper introduces "survivable probability" as a new metric to quantify the reliability of 5G network slices against random physical link failures. They propose a "base protecting spanning tree set" approach that accurately reflects this survivability and can be used to design more robust network slices.
What Problem Does This Paper Address?
The advent of 5G technology relies heavily on network slicing, which allows for the creation of multiple virtual, on-demand network services (slices) over a shared physical infrastructure. A critical challenge for network operators is ensuring the reliability of these slices, as failures in the underlying physical network (like link failures) can directly impact the performance and availability of the services. Existing methods often assume deterministic failures (either 0% or 100% probability), which doesn't reflect the reality of random link failures. This paper aims to bridge this gap by providing a quantifiable measure of reliability for network slices under these more realistic, probabilistic failure scenarios.
Methods
The core of this paper is the introduction of survivable probability, a metric that measures the likelihood of a network slice remaining connected despite random physical link failures. To make this quantifiable, they introduce the concept of a protecting spanning tree set. This set of trees in the physical network mirrors the logical structure of the network slice and is designed to maintain connectivity.
The authors prove the existence of a base protecting spanning tree set, which they show has the exact same survivable probability as the network slice itself. They also develop mathematical formulations to identify these base protecting spanning tree sets. Furthermore, they establish a connection between their problem and the well-known Steiner tree problem, which allows them to leverage existing algorithms and analyze the computational complexity of their approach. For practical implementation, they propose mixed-integer programming formulations to compute survivable probability and identify optimal protecting spanning trees.
Datasets
The paper uses simulated network topologies for evaluation:
- NSF network: A small-size physical network.
- CORONET network: A medium-size physical network.
- Logical networks (LN1, LN2, CLN1, CLN2): These are generated on top of the physical networks to represent different network slices.
The paper does not introduce new benchmark datasets but rather uses these standard network topologies to test their proposed methods.
Key Insights and Ideas
- Quantifying "Survivability": Moving beyond binary (survivable/non-survivable) or deterministic failure models, "survivable probability" offers a nuanced way to assess network slice reliability.
- The Power of Spanning Trees: The insight that a specific set of spanning trees in the physical network can perfectly mirror the survivability of a complex logical network slice is crucial. This simplifies the problem significantly.
- Link to Steiner Trees: The connection to the Steiner tree problem is a significant theoretical contribution, allowing for the application of established approximation algorithms and providing a deeper understanding of the problem's complexity.
- Practical Design Tool: The proposed mathematical formulations offer a concrete way for network operators to design and evaluate network slices for desired levels of reliability.
Key Results
- The proposed survivable probability metric effectively quantifies the reliability of network slices under random physical link failures.
- The base protecting spanning tree set approach is shown to accurately reflect the survivable probability of a network slice.
- Simulations on small and medium-sized networks (NSF and CORONET) demonstrate that their approach achieves 100% survivable probability for inherently survivable network slices, regardless of failure probabilities.
- The maximal protecting spanning tree provides a lower bound for the survivable probability, which is shown to be reasonably tight.
- The computational time for their mixed-integer programming formulations was manageable, finishing within 15 minutes for medium-sized networks.
Limitations and Future Work
- Computational Complexity: While the approach is shown to be effective for medium-sized networks, the computational complexity of mixed-integer programming can still be a bottleneck for very large-scale networks.
- Approximation for Large Networks: The paper notes that for very large networks, approximation algorithms (leveraging the Steiner tree connection) might be necessary.
- Node Failures: The current work focuses primarily on physical link failures. Future work could extend the survivable probability concept to include physical node failures.
- Dynamic Scenarios: The current model assumes static network configurations. Investigating dynamic network slicing and failure scenarios would be a valuable extension.
- Real-world Validation: While simulations are presented, real-world validation with actual network deployments would further strengthen the findings.
Summary updated