Research And Implementation Of Virtual Network Mapping Algorithm

Virtual network mapping is a hot issue over the past decade,which aims to map virtual networks to the underlying network as required.This is a NP-hard question,therefore many prior algorithms just impose some constraints to get the relative optimal result.In traditional research,due to the separation of the two phases,the two-phase independent algorithms have a limited solution space,and often the request acceptance ratio is low.The optimization of the running time of the two-stage coordination algorithms cannot fully meet the requirements of real-time performance.In addition,the one-stage algorithms have more calculations,which usually brings more running time.In order to solve the problem of low acceptance ratio and time consuming in traditional research,we propose two efficient virtual mapping algorithms,named as RCRGF algorithm and AEF algorithm.The RCRGF algorithm is an one-stage algorithm.This algorithm performs pre-processing operations before mapping,and executes a subtraction operation on the virtual network to make the virtual network into a tree structure,and then completes the one-stage mapping based on BFS.The AEF algorithm is a two-phase coordination algorithm,which uses some innovative strategies to improve the performance of multiple evaluation indicators.Based on proximity mapping to improve the cost to revenue ratio,we use an evaluation function that is inversely proportional to the remaining bandwidth of the underlying network to find a path that makes the underlying network resources as balanced as possible.In both algorithms,a mapping rule is introduced.This rule pre-judges whether the mapped substrate node is appropriate,thereby avoiding mapping to invalid underlying nodes,reducing the set of candidate nodes and speeding up the mapping.The main goal of the two algorithms in this paper is to speed up the mapping as much as possible,while ensuring the efficiency of other evaluation indicators.After designing and implementing the algorithms,the formulas and proofs of the time complexity of the two algorithms are given.The time complexity of the RCRGF algorithm is 0(|NS|2*log(|NS|)),and the time complexity of the AEF algorithm is O(|NS|2*|NV|*(log(|VS|)+|NV|)),which theoretically illustrates the feasibility of the algorithms.In the simulation experiment test,we can see that our algorithm basically has a more obvious advantage than most other algorithms in terms of mapping time,and it can also guarantee higher performance.