ClusPR: Balancing Multiple Objectives at Scale for NFV Resource Allocation

Network function virtualization (NFV) implements network middleboxes in software, enabling them to be more flexible and dynamic. NFV resource allocation methods can exploit the capabilities of virtualization to dynamically instantiate network functions (NFs) to adapt to traffic demand and network conditions. Deploying NFs requires decisions for NF placement, and routing of flows through these NFs in accordance with the sequence of NFs required to process each flow. The challenges in developing an NFV resource allocation scheme include the need to manage the dependency between flow-level (routing) and network-level (placement) decisions and to efficiently utilize resources that may be distributed network-wide, while fulfilling the performance requirements of flows. We propose a scalable resource allocation scheme, called ClusPR, that addresses these challenges. By elegantly capturing the dependency between flow routing and NF placement, ClusPR strikes a balance between multiple objectives including minimizing path stretch , balancing the load among NF instances , while maximizing the total network utilization by accommodating the maximum number of flows possible. ClusPR addresses the offline problem of NFV resource allocation. To address the online problem of dynamically placing and routing flows upon their arrival, we propose iClusPR. iClusPR is an online algorithm that performs dynamic scaling by adjusting the number of NF instances based on the traffic demand and the network state. Our experiments show that ClusPR achieves the near-optimal solution for a practical large-sized network in reasonable time. Compared to the state-of-the-art approaches, ClusPR decreases the average normalized delay by a factor of 1.2 – 1.