Maximizing Throughput of Delay-Sensitive NFV-Enabled Request Admissions via Virtualized Network Function Placement

Abstract

Network Function Virtualization (NFV) has attracted significant attention from both industry and academia as an important paradigm change in network service provisioning. Most existing studies on admissions of NFV-enabled requests focused on deploying dedicated Virtualized Network Function (VNF) instances to serve each individual request without exploring VNF instances sharing among multiple user requests. However, with every-growing user service demands, exclusive usages of VNF instances in most networks drastically degrade the network performance and largely under-utilize the VNF instance resources. In this paper, we jointly explore two different VNF instance scaling techniques to improve the network throughout while minimizing the operational cost of the network. The two techniques are: (i) horizontal scaling that migrates some existing VNF instances from their current locations to new locations to allow the VNF instances to be shared by multiple requests to reduce the resource consumption and operational cost of the network; and (ii) vertical scaling that instantiates new VNF instances to meet the demands of new request admissions if existing VNF instances sharing becomes more expensive or the end-to-end delay requirements of currently executing requests will be violated. To this end, we first propose a unified framework of maximizing the network throughput by admitting as many as NFV-enabled requests while meeting the end-to-end delay requirements of admitted requests, through jointly considering both VNF instance vertical and horizontal scalings. We then provide an Integer Linear Programming (ILP) solution for the problem when the problem size is small. Otherwise, we devise an efficient algorithm for it through a series of non-trivial reductions to reduce the problem to the minimum-weight feedback arc set problem and the generalized assignment problem (GAP). We finally conduct experiments to evaluate the performance of the proposed algorithm. Experimental results demonstrate that the proposed algorithm outperforms a baseline algorithm and achieves a performance on a par with its optimal ILP solution.