The Research On Virtual Network Embedding Algorithms For Future Network

With the continuous expansion of the network size and the development of technologies, traditional Internet can no longer meet the new network demands and the ossification becomes more and more serious. Network virtualization is considered as the key technology to overcome the current ossification of the Internet. The challenging of network virtualization is virtual network embedding, which to efficiently embed virtual network onto substrate network which can meet the demands of virtual network request. The virtual network embedding problem is considered to be a NP-hard problem.The existing solutions for VNE are almost heuristic-based algorithms. It will result in local optimal solution. To solve this defect, the existing virtual network embedding algorithms are improved and optimized in this paper, so that it is close to the global optimal solution. Firstly, three typical virtual network embedding algorithms, VNE-Greedy, D-ViNE and RW-BFS are described in detail. The simulation and analyze of the network performance lay the foundation for the improvement of subsequent algorithms. Secondly, VNE-TS based on tabu search is proposed and this algorithm is two stages embedding algorithm, tabu search introduced into node mapping and shortest path algorithm introduced into link mapping. The algorithm starts by determining an initial solution and choose the candidate which is not forbidden from the neighborhood solutions. The algorithm stops the search and gets the optimal solution until the stopping condition is met. Simulation results show that the accepted rate, revenue, R/C, utilization of resource and runtime are increased compared with the traditional virtual network embedding algorithms. Finally, a virtual network embedding algorithm based on robust mapping tree called VNE-RMT is proposed and is one stage embedding algorithm. This algorithm allowing trace-back constantly moves closer to the optimum solution through building mapping tree and comparing of heuristic function to choose candidate substrate nodes and links to map them at the same time. Simulation results suggest that the performance of VNE-RMT greatly better than traditional virtual network embedding algorithms.