Survivable Probability of Network Slicing with Random Physical Link Failure

Zhili Zhou, Tachun LinarXiv 2017 · OpenReview

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

Abstract

The fifth generation of communication technology (5G) revolutionizes mobile networks and the associated ecosystems through the integration of cross-domain networks. Network slicing is an enabling technology for 5G as it provides dynamic, on-demand, and reliable logical network slices (i.e., network services) over a common physical network/infrastructure. Since a network slice is subject to failures originated from disruptions, namely node or link failures, in the physical infrastructure, our utmost interest is to evaluate the reliability of a network slice before assigning it to customers. In this paper, we propose an evaluation metric, \textit{survivable probability}, to quantify the reliability of a network slice under random physical link failure(s). We prove the existence of a \textit{base protecting spanning tree set} which has the same survivable probability as that of a network slice. We propose the necessary and sufficient conditions to identify a base protecting spanning tree set and develop corresponding mathematical formulations, which can be used to generate reliable network slices in the 5G environment. In addition to proving the viability of our approaches with simulation results, we also discuss how our problems and approaches are related to the Steiner tree problems and present their computational complexity and approximability.
BibTeX
@misc{zhou2017survivable,
  author = {Zhili Zhou and Tachun Lin},
  title = {{Survivable Probability of Network Slicing with Random Physical Link Failure}},
  year = {2017},
  eprint = {1710.05640},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1710.05640},
}
Figure