On the Trade-Off Between Computational Load and Reliability for Network Function Virtualization

Jinkyu Kang, Osvaldo Simeone, Joonhyuk KangIEEE Communications Letters 2017 · DOI

TL;DR

This paper tackles the challenge of ensuring reliable network services in the era of Network Function Virtualization (NFV), where traditional hardware is replaced by software running on commodity servers. The authors propose a joint optimization strategy for composing virtual network functions (VNFs) and embedding them onto physical servers, demonstrating significant improvements in reliability compared to separate optimization approaches.

What Problem Does This Paper Address?

Network Function Virtualization (NFV) promises cost savings and flexibility by running network functions as software (VNFs) on standard servers. However, these commodity servers are less reliable than dedicated hardware. This unreliability poses a significant challenge for maintaining the end-to-end (e2e) reliability of network services. The paper addresses the fundamental trade-off between ensuring high e2e reliability and managing the computational load on these servers. Replicating VNFs across multiple servers can boost reliability but increases the processing burden on each server. The authors aim to find an optimal balance by jointly designing how VNFs are chained together (VNF Chain Composition - CC) and how these chains are mapped onto physical servers (VNF Forwarding Graph Embedding - FGE).

Methods

The paper proposes a novel approach to jointly optimize VNF Chain Composition (CC) and VNF Forwarding Graph Embedding (FGE). They formulate this as a complex optimization problem and tackle it using a Block Coordinate Descent (BCD) method. This iterative approach optimizes different sets of variables (VNFs and their embedding) in turns.

Key methodological contributions include:

  • Probabilistic Reliability Model: They develop a model to evaluate e2e reliability based on the probability of individual server failures and the logical connections between VNFs. This model allows for servers to host multiple VNFs, a departure from some prior work.
  • Joint Optimization Formulation: They formulate a mixed-integer linear programming (MILP) problem that captures the trade-off between reliability and computational load, considering both the logical VNF chaining and their physical embedding.
  • Block Coordinate Descent (BCD) Algorithm: To solve the complex MILP, they propose a BCD algorithm. This algorithm iteratively optimizes the CC and FGE aspects, progressively refining the solution.
  • Approximations for Tractability: To make the problem solvable, they employ approximations for non-convex terms in the objective function and use the L1 norm as a proxy for the L0 norm.

Datasets

Not discussed in the paper. The evaluation is performed using simulations with parameters representative of NFV environments.

Key Insights and Ideas

  • The Interplay is Crucial: The most significant insight is that jointly optimizing VNF chaining (CC) and server embedding (FGE) yields substantial performance gains over optimizing them separately. This highlights that the logical structure of the service and its physical deployment are deeply intertwined.
  • Reliability vs. Load Trade-off: The paper quantifies the inherent trade-off: increasing reliability (e.g., by replicating VNFs) directly increases computational load. This trade-off is particularly pronounced in resource-constrained environments.
  • Disconnected FG Simplification: For a simplified scenario (Disconnected Forwarding Graph - D-FG), the authors derive a theoretical lower bound on e2e reliability. This bound shows that unreliability decreases exponentially with the overprovisioning ratio (servers per VNF) and computational load, providing valuable analytical insight.
  • Bipartite FG Complexity: For more realistic bipartite FGs (where controller VNFs manage regular VNFs), the joint optimization is more complex. The paper shows that different CC strategies (e.g., monitoring minimum vs. maximum compatible VNFs) have varying performance depending on the physical network's connectivity.

Key Results

  • Substantial Performance Gains: Simulations demonstrate that the proposed joint CC-FGE optimization approach achieves significant improvements in e2e reliability compared to optimizing CC and FGE independently.
  • D-FG Bound Validation: The theoretical lower bound derived for D-FGs closely matches the performance of the proposed FGE-only optimization, validating the analytical insights.
  • Impact of Physical Connectivity: For bipartite FGs, the performance of different CC strategies varies with the probability of physical connectivity. CCmax-FGE (where controllers monitor more VNFs) can be advantageous with higher physical connectivity, while CCmin-FGE offers more flexibility in sparsely connected networks.
  • Advantage in Intermediate Load: The joint CC-FGE optimization shows its strongest advantage in scenarios with intermediate computational load, where resource scarcity makes efficient allocation critical.

Limitations and Future Work

  • Approximations: The paper acknowledges using approximations for non-convex terms and the L0 norm to make the problem tractable. While the BCD approach provides a heuristic solution, it may not guarantee the absolute global optimum.
  • Simplified Physical Model: The model assumes independent server failures and a fixed physical network topology. Real-world scenarios might involve correlated failures or dynamic network changes.
  • Other Resource Constraints: The current work focuses on computational load. Future work could extend the model to include other critical resources like memory and bandwidth.
  • Experimental Validation: The authors suggest that future work should include comparisons with experimental results to validate the proposed models and algorithms in real-world NFV deployments.

Summary updated

BibTeX
@article{kang2017trade,
  author = {Jinkyu Kang and Osvaldo Simeone and Joonhyuk Kang},
  title = {{On the Trade-Off Between Computational Load and Reliability for Network Function Virtualization}},
  journal = {IEEE Communications Letters},
  year = {2017},
  doi = {10.1109/lcomm.2017.2698040},
}
Figure