Near-Optimal Resource Allocation and Virtual Network Function Placement at Network Edges

Network Functions Virtualisation (NFV) has a magnificent prospect due to its cost-efficiency, manage-convenience, and flexibility. To promote these advantages, the placement of virtual network functions (VNFs) is a key technology. In this paper, we focus on minimizing the total resources of used commercial servers to provide an optimal VNF placement scheme in edge networks. As for the NP-hard problem, we first design a Largest Fit Decreasing algorithm (LFD) with a provable constant approximation ratio of 2 and the computational complexity of O(N2), where N is the number of VNFs. Besides, we improve it and further produce the Judge and Repeated Largest Fit Decreasing algorithm (JR-LFD), which has a bit larger computational complexity O(kN2), but a smaller asymptotic approximation ratio of 32, where k is the number of different server sizes. The simulation results demonstrate that the used resources derived by JR-LFD are always smaller than those by LFD. They both are extremely close to the optimal results and much smaller than the benchmark, which implies they improve the network resource utilization dramatically.