Research On Model And Optimization Algorithm Of Virtual Network Embedding

Network virtualization is one of the most competitive technologies to effectively solve Internet Ossification.Internet Ossification refers to that,the traditional network architecture,which is subject to the inherent way of data transmission based on TCP/IP model,will not be able to satisfy the growing demand of data transmission with a variety of different quality of service(QoS).In order to break through the constraint of Internet Ossification,the solutions named network virtualization try to separate the function of the current Internet service provider(ISP)into two parts,which are infrastructure provider(InP)and service provider(SP)respectively.InP is responsible for establishing and maintaining the underlying network infrastructure providers(InP),and rent the underlying network infrastructure resources to provide data transmission services to the SP.According to the QoS requirements of data transmission,SP leases part of resources from the InP,including the underlying calculating resources(CPU)in network nodes and bandwidth resources(BW)in the underlying link bandwidth resources,to build and deploy the virtual network,After that,SP runs specified protocol to complete data transmission services.Virtual network embedding(VNE)problem is one of the difficulties in network virtualization technology.Virtual network embedding problem focuses on the efficiency of the substrate network resource allocation among multiple virtual networks.The problem of virtual network mapping involves node mapping stage and link mapping stage,Both parts of VNE can be proven to NP-hard.To solve NP-hard problems,we need to use heuristic algorithms or approximation algorithms.Between corresponding underlying nodes for mapping virtual nodes,we will search physical path to deploy virtual link in link mapping stage,in order to satisfy the demands of virtual link bandwidth and delay,etc.Link mapping can be separated into two branch,single-path mapping and multi-path mapping.Single-path mapping refers to that,a virtual link can only be placed on one substrate path between the corresponding underlying nodes,and multi-path refers to that the bandwidth traffic of one virtual link can be arranged on multiple paths between the corresponding nodes.The advantage of single-path mapping is that it reduces the cost of the link mapping of the virtual network and consumes as little of the underlying resources as possible to reserve the use of subsequent virtual requests.However,one of the possible problems is that when the shortest path is used for mapping link,local substrate links of high quality could be used frequently to form a resource bottleneck.The advantage of multi-path mapping is that multiple path resources can be fully utilized,and overcome the problem that the link of single bandwidth is too high to be completed in multiple paths through traffic segmentation.However,one of the possible problems is that the multi-path mapping cannot be completed without sufficient link resources between the underlying nodes.Both above mentioned two kinds of possible problems are attributable to improper node selection.Therefore,how to suitably complete node selection,solving the problems is the focus of this article.In addition,there are many index to evaluate underlying path,such as bandwidth,delay,hop count,etc.When a virtual link is mapped to the underlying path,the evaluation of the underlying path will affect the mapping performance of the virtual network embedding.Therefore,it is also the key point of this paper to recommend the path with high quality to be selected in the measurement environment with multiple indexes.Principle work of this paper has three aspects:We research the problem of shortest path bottleneck,using the redefined metric named path relevance,put forward an enhanced node mapping algorithm combined with intelligent ant colony algorithm,named ACO-PR.After that,we put forward a novel node mapping metric named maximum adjacency capacity to quantify the link richness between nodes and its neighbor,and put forward a greedy node mapping algorithm named MARANK with recomputation,and analyze the relation between recomputation opportunity based on real-time acceptance ratio and performance of the MARANK algorithm.In addition,we put forward a novel node mapping algorithm based on breadth-first search to measure downtrend of resources richness of neighbor nodes with increasing of hop-count between given node and its neighbor.Then,path algebra framework is introduced to link mapping stage of VNE problem to solve the problem of path quality evaluation.Simulation results show that,the algorithms proposed in our paper,ACO-PR and MARANK combine multiple commodity flow algorithm and the shortest path algorithm,and the mapping algorithm based on path algebra GBP A,all have an enhanced performance on acceptance ratio and average revenue compared with algorithms G-SP and D-ViNE.