Research On Virtual Network Mapping Algorithm In Heterogeneous Network Testbed

Network testbed is a critical infrastructure which can be used to test and verify network protocols, services and distributed systems. Heterogeneous network testbed which merges a variety of simulation mechanisms is the most important category. Allocation of substrate resources to virtual network testbed network efficiently is a key issue, called virtual network mapping problem. Virtual network mapping problem in heterogeneous network testbed is an NP-hard problem. Existing algorithms can be obtained approximate solutions for about 200 nodes scale network within tens of seconds, obviously their performance need to be improved. Therefore, this article will study the high-performance virtual network mapping algorithm in heterogeneous network testbed.First, a heterogeneous network testbed virtual network mapping model is created, a series of mapping algorithm metric and testing methods are proposed, and a simulation environment is built. Based on virtual network coarsening and mapping scheme refining, a multilevel virtual network mapping algorithm framework is proposed, virtual network mapping is divided into three stages: Coarsening, coarsening virtual network. Mapping, mapping coarsened virtual network to get a initial mapping scheme. Uncoarsening, uncoarsening and correcting mapping scheme level by level to get the final mapping scheme. Main issues in each phase are studied and three algorithms are proposed. In this article there are these achievement:A framework for multilevel virtual network mapping algorithm is proposed through studying the way to apply virtual network coarsening and mapping scheme refining in topology mapping problem, it can reduce the time overhead while ensuring mapping quality through multilevel coarsening/refine pattern.For virtual network mapping problem in mapping stage, a virtual network mapping algorithm is proposed based on estimation of distribution through applying estimation of distribution algorithm. It can improve the quality topology mapping at the cost of increasing some time overhead.For virtual network mapping refining problem in uncoarsening stage, a virtual network mapping refining algorithm based on variable neighborhood search algorithm is proposed. It can avoid excessive local optimum, enhance the effect of refining mapping scheme, through variable neighborhood mechanism and solution acceptable strategy of simulated annealing algorithm.Based on above achievements, combining the above three algorithms in the multilevel virtual network mapping algorithm framework can achieve better performance and mapping quality than the existing algorithms. On the other hand, we can also select a appropriate combination of these algorithms to get required performance and mapping quality according to the actual needs.