Divide-and-conquer And Coevolutionary Algorithms For Large-scale Network Resource Scheduling

With the rapid development of information technology,cutting-edge technologies such as the Internet,the Internet of Things,cloud computing,edge computing,and big data are changing with each passing day.As a computing service,network resources have penetrated into various social scenarios.The scope of services and the number of users are increasing day by day.How to achieve efficient resource scheduling of network resources and improve the efficiency of using network resources are key issues in improving the quality of network services.The virtual network mapping problem(VNE)is a classic network resource scheduling problem,and it is a challenging NP-hard problem with complex network structures.Evolutionary algorithms are effective methods to solve complex optimization problems,and the use of evolutionary algorithms to solve VNE problems has been extensively studied.With the growth of network resources,the scale of network resource scheduling problems has been further expanded,which brings new challenges to traditional evolutionary algorithms.Existing evolutionary algorithms are faced with the following challenges in large-scale VNE problems.(1)There are two related processes in VNE problems: node scheduling and link scheduling.Traditional evolutionary algorithms usually ignore the cooperation of node scheduling and link scheduling,which is difficult to meet the constraints of node scheduling and link scheduling simultaneously in a large-scale complex network structure.(2)In largescale network scenarios,the increasing dimensionality of VNE will cause the search space to grow exponentially,called the curse of dimensionality.The performance of traditional evolutionary algorithms deteriorates in large-scale VNE problems,which means the lack of scalability.(3)With the growth of network scale and user demand,centralized network resource scheduling algorithms are difficult to achieve scalability in time efficiency,and it is difficult for a single computing node to meet the concurrent requirement of multiple users.In order to solve the above-mentioned challenges,this dissertation studies divide-and-conquer and coevolutionary algorithms for large-scale network resource scheduling.The research includes the operator cooperation,decision-space cooperation,and objective-space cooperation.(1)In operator cooperation,a constructive particle swarm optimization based on the stepby-step mechanism is proposed to coordinate the node scheduling and link scheduling processes.In the process of constructing candidate solutions,the step-by-step mechanism can improve the capability of finding feasible solutions.Since the step-by-step updating mechanism can easily introduce heuristic information,heuristic information based on network paths is further designed in the algorithm to measure the quality of node scheduling.Using this heuristic information,the closely connected nodes in the network can be scheduled cooperatively,thereby improving the efficiency of network resource scheduling.(2)In decision-space cooperation,a divide-and-conquer and cooperative evolutionary algorithm for large-scale VNE is proposed.The divide-and-conquer strategy is adopted to reduce the dimensionality of large-scale network scheduling problems.Based on the theory of network partition,a large-scale network is decomposed into several small-scale networks,and small-scale network scheduling problems are solved cooperatively.Due to the connectivity of networks,no matter what network decomposition strategy is adopted,there must be connected links between the decomposed sub-networks.In order to reduce the influence of dependent subproblem optimization,an overlapping decomposition strategy for VNE is designed to deal with the dependency among sub-problems.Critical nodes in the network are overlapped in multiple sub-networks,and overlapping elements are used to collaborate optimization among subproblems.(3)In distributed cooperation,a distributed network scheduling system based on historical archives and set-based particle swarm algorithm is proposed.Through the multi-agent node mechanism and the level-based network partition strategy,multiple evolutionary optimizers are deployed in the network system to process multiple user requests in a distributed manner.While improving the optimization capability of the distributed scheduling system,it also improves the time efficiency of evolutionary algorithms.In addition,the distributed system introduces an archive mechanism to record historical scheduling information,and uses historical optimization information to enhance the optimization of repetitive tasks.Thereby the optimization capability of the distributed scheduling system can be further improved.(4)In objective-space cooperation,a nested particle swarm algorithm is designed for solving the novel cloud workflow scheduling problem with composite tasks.In order to meet the increasing demand for computing resources of users,a new cloud workflow scheduling model with composite tasks(c WFS)is designed,which models heavy computing tasks as composite tasks,and can allocate multiple service instances to execute a single composite task.The c WFS model improves the capability of resource provision for complex workflow tasks.Since c WFS is a kind of two-layer optimization problem,a nested particle swarm algorithm and its fast version are proposed.The outer population and inner population cooperatively optimize two objectives,makespan minimization and resource minimization,respectively.The proposed nested particle swarm optimization can effectively solve the complex cloud workflow scheduling problem.