Joint VNF Placement, CPU Allocation, and Flow Routing for Traffic Changes

The emerging network-softwarization technologies, such as software-defined networking and network function virtualization play important roles in 5G communication and future networks. One of the critical challenges of the practical application of the softwarized networks is to appropriately place virtual network functions (VNFs). The underlying resources and traffic requirements are often factored in the previous works of VNF placement. However, VNFs' dynamic abilities of changing traffic are usually ignored. Resources allocated to VNFs can vary their traffic-change ratios, and the adjustment of resource volumes should be provisioned to support traffic changes. In this work, we pay attention to the joint optimization problem of VNF Placement, CPU Allocation, and flow Routing (VNFPAR) in the scenarios consisting of VNFs that can dynamically change traffic. We employ the logarithmic functions to approximate VNFs' traffic change relations and formulate VNFPAR as a mixed-integer nonlinear programming (MINLP) problem. We demonstrate that this problem is highly nonconvex and involves highly coupled variables. For small-scale VNFPAR problems, we propose an optimal algorithm based on relaxation and programming to consume the minimum bandwidth resources. Because VNFPAR is NP-hard, to quickly find near-optimal solutions for large-scale VNFPAR problems, we present heuristic algorithms based on multistage greedy and simulated annealing, respectively. Besides, to achieve a tradeoff between solution quality and execution time, we decompose VNFPAR into subproblems and design an alternating optimization-based method. We evaluate our algorithms on real-work topologies and traffic patterns. Extensive simulations show that our proposed heuristic algorithms are convergent, stable, and effective in terms of solving VNFPARs. The proposed algorithms have small optimality gaps within 7.4%-26.3%. Meanwhile, they save 39.3%-48.4% bandwidth resources compared with relevant baseline technologies.