Research On Virtual Network Function Placement Problem Based On Population-based Incremental Learning

The rapid popularity of Internet industry has brought out severe demands on network environment.Thereby,it is of importance to update network devices,enhance the variety and improve the function of network devices.However,traditional network devices deployed in specific network locations are firmly coupled with specified utility.Generally,network operators are forced to substantially increase capital and operating expenditures when they add and maintain new communication services,because of the rise of the new network function requirements and the development of the specialized network hardware.Network function virtualization(NFV)is an emerging paradigm that decouples the software from proprietary hardware and separates the network function from the dedicated network equipment.Through virtualization technology,network functions are deployed on virtual platforms that run on common physical computational resources.The key issue NVF face is how to map virtual network functions to physical resources to provide users with reliable network services,which is generally called virtual network function placement problem(VNF-P).The VNF-P problem is a combinatorial optimization problem and has been proved as a NP-hard problem.Evolutionary algorithms,inspired by biological evolution,own strong ability to search solutions and work quite effectively in solving combinatorial optimization problems.Therefore,this paper adopts evolutionary algorithms to solve the VNF-P problem,including following three aspects in detail:1)With respect to the VNF-P problem in static network scenarios,this paper proposes a modified population-based incremental learning algorithm.On one hand,this algorithm uses integer coding to accurately represent the solution of the problem,which is conducive to the evolution of the population.On the other hand,elitism preservation strategy can guide the evolution of population.Under the guidance of elite solutions,algorithms can quickly search for areas with higher quality solutions.The experimental comparison with genetic algorithm,ant colony optimization and original population-based incremental learning shows that the proposed algorithm has excellent stability and effectiveness.2)Regarding the VNF-P problem in dynamic scenes,this paper constructs a dynamic model,which employs Poisson distribution to simulate the arrival of user requests in real-world scenarios,and dynamically changes the allocation and release of physical resources in the network.For this model,this paper uses the improved population-based incremental learning algorithm with excellent effects in static scenes to carry out simulation experiment.Compared to genetic algorithm,ant colony optimization and original population-based incremental learning algorithm,as well as Service Step Search Algorithm,Greedy Assignment and Multi-stage Graph Algorithm,the proposed algorithm can achieve the highest success rate when dealing with multiple requests.3)For the multi-objective VNF-P problem with load balancing and delay as the optimization goals,this paper proposes an improved multi-objective population-based incremental learning algorithm to solve.This algorithm is coded in integers,using local search and global search strategy.The local search strategy exploits the neighborhood of excellent individuals to further enhance the quality of solution.The global search strategy can prevent algorithm from getting stuck in local search area so that it explores more unknown fields.The algorithm selects the corresponding search strategy according to the probability formula,which can balance the exploitation ability and exploration ability.Simulation experiments in multiple scenarios show that the proposed algorithm has excellent evaluation index and can provide a better solution to solve multi-objective VNF-P problems.