Research On Algorithms For Dynamic Virtual Network Embedding Problems

With the rapid growth of the Internet,the current network architecture has been difficult to meet the demands of the human society,and the problem of network rigidity is becoming increasingly serious.Network virtualization technology can abstract the underlying network resources and allow multiple virtual networks to coexist in the same underlying physical network,which is an effective means to deal with network rigidity.The problem of virtual network embedding is a key issue in the field of network virtualization.Its main objective is to embed the virtual network requests with various constraints into the underlying network and maximize the profits of network operators.Using a single heuristic algorithm to solve the virtual network embedding problem has some defects,such as easy to fall into the local optimal value and slow convergence speed.This paper proposes a cellular genetic virtual network embedding algorithm with particle swarm optimization,which uses cellular automata with evolution rules to transform the selection operation of traditional genetic algorithm,so that the cross operation and mutation operation only occur in the cell neighborhood,thereby reducing the diffusion of the super solution and improving the global optimization ability of the algorithm.Aiming at the slower convergence spee,d of the cellular genetic algorithm,this paper designs a mutation operator based on the idea of particle swarm optimization.By guiding the selection of mutation points,it effectively eliminates the blindness of mutation operation and accelerates the convergence speed of the algorithm.The experimental results indicate that the algorithm can efficiently increase the acceptance rate of virtual network requests and the underlying network revenue compared with the existing virtual network embedding algorithm.In the static virtual network embedding algorithm,the scheme that the underlying network allocates resources for virtual network requests is fixed.In fact,with the continuous arrival or departure of virtual network requests,the problem of resource fragmentation in the underlying network becomes more and more serious,and the acceptance rate of virtual network requests also decreases.Therefore,it is necessary to dynamically reconfigure the virtual network.In the underlying network,nodes of different importance have different influence on the network connectivity.The existing virtual network reconfiguration algorithms do not distinguish the importance of the underlying nodes,which is easy to cause new resource bottlenecks after reconfiguration.In this paper,a virtual network reconfiguration algorithm based on node importance is proposed.The algorithm distinguishes the importance of the underlying nodes by a new node importance evaluation index which integrates multi-dimensional attributes.Periodically,some virtual nodes on the important nodes with high load are remapped into the non-important nodes with low load,and the associated virtual links are reconstructed in order to reduce the fragmentation of the underlying network resources.Simulation results show that the algorithm is superior to the existing virtual network reconfiguration algorithms in improving the virtual network request acceptance rate and reducing the cost of remapping link resources.