Abstract
This paper addresses the Virtual Network Function (VNF) placement problem, which involves determining the optimal deployment of software-based network functions to minimize hardware costs. We prove that the problem is NP-hard and develop three greedy algorithms: Flow Number based Greedy (FNG), Flow Rate based Greedy (FRG), and Greedy For Tree (GFT). These algorithms are mathematically guaranteed to be near-optimal. In real-world simulations, they perform within 4% of the theoretical best, while often requiring a smaller physical footprint than exact solvers.
Introduction
Modern networking is transitioning from proprietary hardware "middleboxes" (like firewalls and load balancers) to Virtual Network Functions (VNFs) running on standard servers. This shift increases flexibility but introduces a complex optimization challenge: where to place VNF instances and how much traffic each should handle to minimize resource consumption.
A key distinction of this work is the consideration of fractional processing. Unlike models requiring a flow to be processed at a single node, this paper allows partial processing across multiple datacenters, reflecting technologies like GTP tunneling.
Problem Formulation and Methods
The authors formalize the VNF placement problem as a Mixed Integer Linear Program (MILP) and prove its NP-hardness via a reduction from the Set Cover problem. To provide scalable solutions, three algorithms are proposed:
- Flow Number based Greedy (FNG): Selects nodes based on the count of unprocessed flows.
- Flow Rate based Greedy (FRG): Prioritizes nodes based on the total volume (bitrate) of unprocessed traffic.
- Greedy For Tree (GFT): A specialized bottom-up approach for tree topologies, common in CDNs.
The researchers provide a rigorous mathematical proof that FNG and FRG achieve an approximation ratio of $(1 - o(1)) \ln m + 2$, where $m$ is the number of flows, which is asymptotically optimal.
Evaluation and Results
The algorithms were tested on randomly generated topologies (40 nodes, 234 links) and the realistic InternetMCI backbone topology from the Topology Zoo. Performance was compared against the absolute optimal solution from the GNU Linear Programming Kit (GLPK).
Key findings include:
- Near-Optimality: The gap between greedy solutions and the theoretical optimum was typically less than 4%.
- Tree Optimality: GFT was proven strictly optimal for tree topologies.
- Physical Footprint: For large flow rates, greedy algorithms used nearly 50% fewer physical nodes than the MILP optimal solution, suggesting better operational efficiency despite a slightly higher instance count.
Insights and Future Work
The study reveals a "density advantage": as networks host more VNF instances, greedy algorithms approach perfect optimality. Furthermore, the GFT algorithm highlights the importance of aggregation, suggesting that processing should occur at the highest possible tree node to maximize traffic combination.
Future research will address Service Function Chaining (SFC), where traffic must pass through a sequence of functions, and dynamic traffic patterns, as the current model assumes fixed routing and constant flow rates.
Summary updated