TL;DR
This paper introduces a novel, more efficient LP relaxation and a two-stage algorithm (LPdRR) for the complex network slicing problem. LPdRR effectively balances solution quality and computational complexity, making it suitable for large-scale network deployments.
What Problem Does This Paper Address?
The fifth generation (5G) and beyond networks rely on Network Function Virtualization (NFV) to provide flexible and on-demand services. Network slicing is a key concept in NFV, allowing the creation of customized virtual networks for diverse service requirements on a shared infrastructure. The core challenge is efficiently allocating network resources (like cloud compute and communication links) to map virtual network functions (VNFs) and route traffic for multiple services while meeting strict end-to-end (E2E) delay constraints. Existing methods often struggle with either exponential complexity (for optimal solutions) or low-quality results, hindering their application to large-scale scenarios.
Methods
The authors propose a two-stage approach:
- Novel LP Relaxation: They introduce a new, more compact, and stronger Linear Programming (LP) relaxation of the original Mixed Integer Linear Programming (MILP) formulation for network slicing. This novel relaxation provides a tighter lower bound, which is crucial for the subsequent rounding steps.
- LP Dynamic Rounding-and-Refinement (LPdRR) Algorithm:
- Stage 1 (VNF Placement): This stage uses an "LP dynamic rounding" procedure. It starts by solving the novel LP relaxation and iteratively rounds fractional VNF placements to binary decisions. Crucially, this process considers traffic routing information simultaneously, leading to a more coordinated VNF placement.
- Stage 2 (Traffic Routing): Once VNFs are placed, an "iterative LP refinement" procedure is employed to determine the traffic routing. This stage aims to satisfy the E2E delay constraints for all services by adjusting routing strategies.
Datasets
The paper uses standard network topologies from the literature, specifically the "fish network topology" from [12] and the JANOS-US, NOBEL-GERMANY, and POLSKA topologies from SNDLIB [42]. These are used to evaluate the performance of their proposed algorithm against existing methods.
Key Insights and Ideas
- The importance of a "stronger" LP relaxation: The paper demonstrates that a more compact and tighter LP relaxation (LP-II) significantly improves the efficiency and effectiveness of the overall algorithm compared to a "natural" LP relaxation (LP-I). This highlights that the quality of the relaxation is paramount for subsequent heuristic or rounding-based algorithms.
- Coordinated VNF placement and traffic routing: By incorporating traffic routing information into the VNF placement stage (unlike some prior work), the LPdRR algorithm achieves better overall solutions. This holistic approach prevents suboptimal VNF placements that might lead to routing infeasibilities or poor performance.
- Dynamic rounding for VNF placement: The dynamic rounding strategy in Stage 1, where fractional variables are iteratively rounded and the LP is re-solved, is shown to be more effective than static rounding. This allows the algorithm to adapt and find feasible solutions more reliably.
- Polynomial time complexity: A key contribution is achieving a polynomial worst-case complexity, making the algorithm scalable for large-scale network slicing problems, a significant advantage over exponential-time exact methods.
Key Results
- LP Relaxation Performance: The proposed LP relaxation (LP-II) is significantly more efficient (faster CPU time) and provides a better LP bound (stronger relaxation) than the natural LP relaxation (LP-I).
- LPdRR Algorithm Performance:
- Effectiveness: LPdRR solves a larger number of feasible problem instances, especially for a higher number of services, compared to state-of-the-art algorithms like IO, PSO, and LPoR. It also achieves a comparable or better number of activated cloud nodes and total E2E delay.
- Efficiency: LPdRR is computationally more efficient than other LP-based methods like LPsRR and LP'dRR, and significantly more efficient than exact MILP solvers (EXACT).
- Trade-off: The algorithm achieves a good balance between solution quality and computational complexity, outperforming existing heuristic methods while being much faster than exact solvers.
Limitations and Future Work
- Approximation Ratio: For certain special cases (e.g., infinite node capacities, zero link delays), the paper proves that no polynomial-time algorithm, including LPdRR, can guarantee a constant approximation ratio. However, for other specific cases, LPdRR provides a u-approximation or even a global solution.
- Future Work: The paper suggests that a modified version of LPdRR (LPsRR, which uses static rounding) can always find feasible solutions if LPoR can. However, the dynamic rounding in LPdRR is shown to be beneficial for finding solutions with fewer activated cloud nodes and improving solution efficiency. Further exploration of these dynamic aspects and their impact on resource utilization could be a future direction. The paper also notes that the problem is NP-hard, implying that finding optimal solutions for all scenarios remains a challenge.
Summary updated