Robust network function virtualization

Tachun Lin, Zhili Zhou

TL;DR

This paper tackles the challenge of ensuring reliable network services in the face of unpredictable failures in Network Function Virtualization (NFV) environments. They introduce a novel metric for evaluating NFV reliability and propose algorithms to optimize the deployment of virtual network functions (VNFs) to withstand these failures, ultimately aiming for ultra-reliable 5G services.

What Problem Does This Paper Address?

The increasing reliance on Network Function Virtualization (NFV) for agile and on-demand network services, especially in the context of 5G, brings a critical challenge: ensuring service reliability when the underlying physical infrastructure is prone to failures. NFV decouples network functions from hardware, realizing them as software (VNFs) on commercial off-the-shelf hardware. While this offers flexibility, it also introduces complexity in managing VNF deployments and ensuring service continuity when NF-enabled nodes fail. Existing approaches often focus on deterministic scenarios or lack robust evaluation metrics that account for the uncertainty of node failures. This paper addresses this gap by proposing methods to quantify and achieve robust NFV reliability, specifically focusing on the problem of VNF provisioning under random NF-enabled node failures.

Methods

The authors introduce a robust NF-service evaluation metric that quantifies the minimal reliability across all network functions (NFs) for all demands, considering worst-case scenarios of node failures. To solve the robust NF provisioning problem, they construct an auxiliary NF-enabled network which acts as an intermediate layer between the logical NF forwarding graph and the physical substrate network.

Key algorithmic contributions include:

  • Pseudo-polynomial algorithms for robust NF and SFC (Service Function Chaining) s-t path problems.
  • Approximation algorithms for robust NFV with SFC-Fork as the forwarding graph, utilizing a two-step parameterized path reduction technique.
  • Exact solution approaches via Mixed-Integer Linear Programming (MILP) for the general robust NF provisioning problem.

They also leverage concepts from k-level facility location problems to develop approximation algorithms.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and simulation-based evaluation using synthetic network topologies (NSF network and CORONET network).

Key Insights and Ideas

  • Quantifying Robustness is Crucial: Simply ensuring service availability isn't enough; understanding and optimizing for the worst-case reliability under node failures is essential for ultra-reliable services like 5G.
  • Auxiliary Network Simplifies Complexity: The proposed auxiliary NF-enabled network acts as a powerful abstraction, simplifying the complex relationships between physical infrastructure, logical NF graphs, and service requirements.
  • SFCs Introduce Ordering Constraints: The sequential nature of SFCs adds significant complexity compared to non-chained NF requests, requiring specialized algorithms and considerations.
  • Trade-offs Exist: There's a clear trade-off between the number of deployed NF-enabled nodes (cost) and the achieved NF service reliability, especially under node failures.

Key Results

  • The proposed solution approaches are demonstrated to be capable of managing robust NFV in large-size networks.
  • Computational results show that increasing the number of NF-enabled nodes generally leads to higher NF service reliability, especially under higher node failure probabilities.
  • For SFC requests, different forwarding graph structures (1SFC, rFork, bFork) exhibit varying levels of survivable probability, with 1SFC generally offering higher reliability.
  • The study validates the effectiveness of the robust NF-service evaluation metric in guiding VNF deployment strategies.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Physical Node Capacity and Deployment Costs: The current work does not explicitly consider the capacity of physical nodes or the costs associated with NF deployment.
  • More NF-enabled Nodes: Investigating the cost-benefit analysis of introducing more NF-enabled nodes to enhance reliability is a potential area for future work.
  • Shared Risk Group and Physical Link Failures: The current model primarily focuses on independent NF-enabled node failures. Future research could explore the impact of shared risk group failures and physical link failures.
  • Correlation Among Node Failures: Relaxing the assumption of independent node failures and studying the impact of correlated failures on NF service reliability is another important research direction.

Summary updated

Abstract

Network function virtualization (NFV) enables on-demand network function (NF) deployment providing agile and dynamic network services. Through an evaluation metric that quantifies the minimal reliability among all NFs for all demands, service providers and operators may better facilitate flexible NF service recovery and migration, thus offer higher service reliability. In this paper, we present evaluation metrics on NFV reliability and solution approaches to solve robust NFV under random NF-enabled node failure(s). We demonstrate how to construct an auxiliary NF-enabled network and its mapping onto the physical substrate network. With constructed NF-enabled network, we develop pseudo-polynomial algorithms to solve the robust NF and SFC $s-t$ path problems -- subproblems of robust NFV. We also present approximation algorithms for robust NFV with the SFC-Fork as the NF forwarding graph. Furthermore, we propose exact solution approaches via mixed-integer linear programming (MILP) under the general setting. Computational results show that our proposed solution approaches are capable of managing robust NFV in a large-size network.
BibTeX
@inproceedings{lin2020robust,
  author = {Tachun Lin and Zhili Zhou},
  title = {{Robust network function virtualization}},
  booktitle = {Networks},
  year = {2020},
  url = {https://openreview.net/forum?id=qqSxWSx12k},
}
Figure