A fix-and-optimize approach for efficient and large scale virtual network function placement and chaining

Network Function Virtualization (NFV) is a novel concept that is reshaping the middlebox arena, shifting network functions (e.g. firewall, gateways, proxies) from specialized hardware appliances to software images running on commodity hardware. This concept has potential to make network function provision and operation more flexible and cost-effective, paramount in a world where deployed middleboxes may easily reach the order of hundreds. In spite of recent research activity in the field, little has been done towards efficient and scalable placement & chaining of virtual network functions (VNFs) - a key feature for the effective success of NFV. More specifically, existing strategies have either neglected the chaining aspect of NFV, focusing on efficient placement only, or failed to scale to hundreds of network functions. In this paper, we approach VNF placement and chaining as an optimization problem, and propose a fix-and-optimize-based heuristic algorithm for tackling it. Our algorithm incorporates a Variable Neighborhood Search (VNS) meta-heuristic, for efficiently exploring the placement and chaining solution space. The goal is to minimize required resource allocation, while meeting network flow requirements and constraints. We provide evidence that our algorithm is able to find feasible, high quality solutions efficiently, even in scenarios scaling to hundreds of VNFs.