Study On Virtual Network Embedding Algorithms

Network virtualization is recognized as a key technology for overcoming the ossification of the current network architecture.It can adapt to the growing number of network users and business needs.One of the main problems is how to allocate the limited resources on the substrate physical network to more virtual networks which is the virtual network embedding problem.According to whether the infrastructure providers is unique,the problem can be divided into intra-domain and multi-domain embedding.In this thesis,the virtual network mapping problem is studied and a virtual network mapping algorithm based on node ranking(NR-RT)and a virtual network mapping algorithm with low delay coordinating link mapping(VNE-M)are investigated.The algorithms can effectively solve the online mapping problems in single domain virtual network mapping and virtual network request decomposition and subnetwork mapping problems in multi-domain virtual network mapping.NR-RT algorithm is based on node ranking virtual network online mapping algorithm which is a heuristic algorithm.The virtual network nodes and the underlying network nodes are ordered by importance,followed by greedy algorithm for node mapping and the shortest path algorithm for link embedding.At the same time,this thesis combines node ranking algorithm with online mapping scheme to make up for the shortcoming of the traditional node ranking algorithms which are only suitable for static virtual network mapping in the past.The simulation results show that the proposed algorithm can effectively improve the mapping performance of virtual network request acceptance rate and network resource utilization.For multi-domain virtual network mapping problem,this thesis focuses on the problem of virtual network request decomposition and sub-network embedding and proposes a network decomposition algorithm that considers the link delay.We propose an iterative downsizing algorithm coordinating intra and peering link mapping during the sub-network mapping.The simulation results show that the multi-domain virtual network mapping algorithm based on low latency and coordinated link mapping can effectively improve the mapping performance of virtual network request acceptance rate and network link utilization.It can also restrict the virtual network transmission delay,which is more suitable for the current network development requirements.