Near optimal placement of virtual network functions

TLDR

Network Function Virtualization (NFV) moves network functions onto commodity servers in distributed cloud nodes, controlled by software‑defined mechanisms, and is a major shift in networking that promises economic services but also poses significant technical challenges, especially regarding placement, which critically affects performance, reliability, and cost. The study investigates the NFV placement problem, aiming to develop near‑optimal approximation algorithms for placing virtual functions in the physical network. The authors formulate the NFV placement as a new optimization problem and design near‑optimal approximation algorithms, evaluating them against client‑function distance and setup costs. The algorithms achieve constant‑factor bi‑criteria approximations for performance and capacity constraints, and simulations confirm strong performance across realistic scenarios.

Abstract

Network Function Virtualization (NFV) is a new networking paradigm where network functions are executed on commodity servers located in small cloud nodes distributed across the network, and where software defined mechanisms are used to control the network flows. This paradigm is a major turning point in the evolution of networking, as it introduces high expectations for enhanced economical network services, as well as major technical challenges. In this paper, we address one of the main technical challenges in this domain: the actual placement of the virtual functions within the physical network. This placement has a critical impact on the performance of the network, as well as on its reliability and operation cost. We perform a thorough study of the NFV location problem, show that it introduces a new type of optimization problems, and provide near optimal approximation algorithms guaranteeing a placement with theoretically proven performance. The performance of the solution is evaluated with respect to two measures: the distance cost between the clients and the virtual functions by which they are served, as well as the setup costs of these functions. We provide bi-criteria solutions reaching constant approximation factors with respect to the overall performance, and adhering to the capacity constraints of the networking infrastructure by a constant factor as well. Finally, using extensive simulations, we show that the proposed algorithms perform well in many realistic scenarios.