Research On Virtual Network Function Scheduling Problem Based On Evolutionary Algorithm

With the rise of network technologies such as 5G and the Internet of things(Io T),the network scale is gradually increasing as well as user service requests are becoming more and more diversified and complex.A new network system that supports flexible migration and upgrade has become an inevitable trend.Network functions virtualization(NFV)was born under this background and has become a hot research topic in recent years.NFV is an advanced and efficient solution,but NFV resource allocation(NFV-RA)is a problem that cannot be ignored in the implementation of NFV.The two most important stages of NFV-RA are VNF placement(VNF-P)and VNF scheduling(VNF-S).The VNF-P stage means VNF mapping and data flow routing for the existing SFC,while the VNF-S stage is scheduled for VNF based on the deployment results of VNF-P.Considering the dynamics of the network environment and aiming at minimizing the maximum completion time of the service function chain(SFC),this paper studies the VNF-S problem under the dynamic network environment.Besides,both VNF-P and VNF-S are interrelated,so one of the formidable challenges of NFV implementation is to consider the two links uniformly and seek global optimization.In this paper,VNF-P and VNF-S are considered jointly,and a joint optimization problem of the two stages is proposed.The evolutionary algorithm is designed to search the solution space iteratively to obtain the approximate global optimal solution in a limited time,which has significant advantages in solving NP-hard problems.Based on the two problems above,this paper devises two improved evolutionary algorithms:1)The VNF-S problem in a dynamic environment is constructed to minimize the completion time of SFC.For dynamic events occurring in the scheduling process,two rescheduling strategies are introduced,including event response rescheduling strategy and periodic rescheduling strategy.An improved integer coding salp swarm algorithm with elite evolution strategy(ESSA)is proposed to solve this problem.Elite evolution strategy accelerates the convergence speed and enhances the global exploitation of ESSA.The experimental results show that ESSA has significant advantages in the completion time compared with a number of state-of-the-art evolutionary algorithms.2)The joint optimization problem of VNF-P and VNF-S is constructed to minimize the completion time of SFC under satisfying relevant constraints.An improved pathfinder algorithm(IPFA)with three advanced strategies is proposed.The elite reserve strategy is also adopted in IPFA to accelerate the convergence speed.A multiple population parallel evolution strategy is introduced to enhance the global search ability and avoids falling into local optimum.The individual crossover and mutation strategy is devised which not only reduces the damage to individual solutions but also enhances the local search ability and the diversity of the population.Compared with several state-of-the-art evolutionary algorithms,the proposed algorithm has significant advantages in the evaluation index of SFC completion time.Besides,the influence of some indicators in the test environment on the experimental results is analyzed to strengthen our conclusions.