Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions

TLDR

Network Function Virtualization replaces hardware middleboxes with software on commodity hardware, promising flexibility and cost savings, yet efficient placement and chaining of virtual network functions remains underexplored and critical for avoiding resource misallocation and excessive end‑to‑end delays. This study formalizes the virtual network function placement and chaining problem and introduces an Integer Linear Programming model to solve it. To handle large‑scale deployments, the authors augment the ILP with a heuristic that guides the solver toward feasible, near‑optimal solutions efficiently. Experiments show the ILP reduces end‑to‑end delays by up to 25 % with only 4 % resource over‑provisioning, and the heuristic achieves near‑optimal results quickly.

Abstract

Network Function Virtualization (NFV) is a promising network architecture concept, in which virtualization technologies are employed to manage networking functions via software as opposed to having to rely on hardware to handle these functions. By shifting dedicated, hardware-based network function processing to software running on commoditized hardware, NFV has the potential to make the provisioning of network functions more flexible and cost-effective, to mention just a few anticipated benefits. Despite consistent initial efforts to make NFV a reality, little has been done towards efficiently placing virtual network functions and deploying service function chains (SFC). With respect to this particular research problem, it is important to make sure resource allocation is carefully performed and orchestrated, preventing over- or under-provisioning of resources and keeping end-to-end delays comparable to those observed in traditional middlebox-based networks. In this paper, we formalize the network function placement and chaining problem and propose an Integer Linear Programming (ILP) model to solve it. Additionally, in order to cope with large infrastructures, we propose a heuristic procedure for efficiently guiding the ILP solver towards feasible, near-optimal solutions. Results show that the proposed model leads to a reduction of up to 25% in end-to-end delays (in comparison to chainings observed in traditional infrastructures) and an acceptable resource over-provisioning limited to 4%. Further, we demonstrate that our heuristic approach is able to find solutions that are very close to optimality while delivering results in a timely manner.