Network Function Virtualization Resource Allocation Based on Joint Benders Decomposition and ADMM

Network function virtualization (NFV) has emerged as a new technology to reduce the cost of hardware deployment. It is an architecture that using virtualized functions run on the virtual machine to achieve services instead of using specific hardware. Although NFV brings more opportunities to enhance the flexibility and efficiency of the network, resource allocation problems should be well taken into consideration. In this paper, we investigate the virtual network function (VNF) resource allocation problem to minimize the network operation cost for different services. Both setting the VNF instances for each virtual machine and allocating the traffic volume in the network are considered. The problem is formulated as a mixed integer programming problem. Although it can be solved in a centralized fashion which requires a central controller to collect information from all virtual machines, it is not practical for large-scale networks. Thus, we propose a distributed iteration algorithm to achieve the optimal solution. The proposed algorithm framework is developed based on the joint Benders decomposition and alternating direction method of multipliers (ADMM), which allows us to deal with integer variables and decompose the original problem into multiple subproblems for each virtual machine. Furthermore, we describe the detail implementation of our algorithm to run on a computer cluster using the Hadoop MapReduce software framework. Finally, the simulation results indicate the effectiveness of the algorithm.