Online Joint Placement and Allocation of Virtual Network Functions with Heterogeneous Servers

Yicheng Xu, Vincent Chau, Chenchen Wu, Yong Zhang, Yifei Zou

Abstract

This paper addresses the challenge of Joint Placement and Allocation (JPA) of Virtual Network Functions (VNFs) in real-time across heterogeneous server environments. We introduce OJPA-HS, a model that accounts for varying server capabilities and unpredictable online traffic. To solve this NP-hard problem, we propose a deterministic dynamic programming algorithm that achieves local optimality for each flow, alongside two randomized heuristics—Las Vegas and Monte Carlo—that significantly reduce computational overhead while maintaining high performance. Experimental results demonstrate that these randomized approaches offer a practical balance between speed and cost-efficiency in large-scale network deployments.

Introduction

In modern networking, Network Function Virtualization (NFV) allows Internet Service Providers (ISPs) to replace expensive, proprietary hardware (like firewalls and load balancers) with software running on generic servers. The primary operational challenge lies in Joint Placement and Allocation (JPA): deciding which servers should host which functions and how much capacity to allocate to specific traffic flows, often referred to as Service Function Chains (SFCs).

Illustration of VNF placement and traffic flow allocation in a network grid.

Most existing research assumes servers are identical or that the network operator knows all traffic demands in advance. In reality, data centers are heterogeneous, containing a mix of hardware generations, and traffic arrives online and unpredictably. This paper tackles the "Online JPA with Heterogeneous Servers" (OJPA-HS) problem, where placement and allocation decisions must be made instantly as flows arrive, without the possibility of reassigning previous flows.

Methodology

The authors propose three primary algorithmic approaches to navigate the trade-off between optimality and computational speed. Central to these methods is a novel mathematical abstraction:

The Capability Function ($f_i$)

The Capability Function measures a server's cost or potential relative to the demand it serves. It generalizes various cost models, including linear, concave, and step functions, allowing the OJPA-HS model to handle diverse hardware configurations seamlessly.

The capability function $f_i(u_i)$ modeled as a step function.

Algorithmic Approaches

  1. Deterministic Online Algorithm (DP): Utilizing dynamic programming, this algorithm ensures the mathematically optimal decision for each individual flow as it arrives. While it cannot achieve a bounded competitive ratio globally due to the unpredictable nature of online traffic, it serves as a "best-possible" local benchmark. Its complexity is $O(mnD^2)$.
  2. Las Vegas (LV) Randomized Heuristic: This algorithm always produces a feasible solution but employs a probabilistic approach to select servers based on their marginal cost. It reduces complexity to $O(mnD)$.
  3. Monte Carlo (MC) Randomized Heuristic: Designed for high-throughput "big data" environments, the MC version prioritizes speed by limiting sampling rounds. It introduces a controllable "FAIL rate," allowing operators to trade a small percentage of unserved flows for significant gains in processing speed.

Key Insights and Results

A critical theoretical finding of this work is that no deterministic online algorithm can have a bounded competitive ratio in a worst-case adversarial environment. Consequently, the research shifts focus toward "local optimality"—making the best possible choice given the current system state.

Performance and Scalability

Experimental evaluations using randomly generated network instances (50 nodes, up to 500 flows) revealed several key insights:

  • Efficiency: The Las Vegas (LV) algorithm provided solutions nearly as cost-effective as the Deterministic DP but in a fraction of the time. In many instances, the performance ratio hovered between 1.5x and 2x.
  • Big Data Readiness: For large-scale instances with high demand, the Monte Carlo algorithm outperformed the LV approach in running time, proving its utility for high-throughput environments.
  • Controllable Reliability: The MC algorithm's failure rate scales predictably with user-defined parameters, enabling ISPs to tune the system according to specific Service Level Agreements (SLAs).

Conclusion

The OJPA-HS framework provides a robust solution for real-time VNF management in realistic, heterogeneous environments. By combining a "best-possible" deterministic baseline with high-speed randomized heuristics, the authors offer a practical toolkit for ISPs to optimize their virtualized infrastructure. Future work may explore the integration of dynamic routing and periodic re-optimization to further enhance long-term cost efficiency.

Summary updated

BibTeX
@article{xu2020online,
  author = {Yicheng Xu and Vincent Chau and Chenchen Wu and Yong Zhang and Yifei Zou},
  title = {{Online Joint Placement and Allocation of Virtual Network Functions with Heterogeneous Servers}},
  journal = {IEEE Internet of Things Journal},
  year = {2020},
  doi = {10.1109/jiot.2020.2990412},
}
Figure