Research On Virtual Network Embedding For Network Virtualization

The network virtualization solving the Internet ossification has become a trend. In recent years, Software Defined Networking (SDN) was proposed which has greatly promoted the development of network virtualization. How to embed the virtual network into the substrate network is the fundamental problem of SDN, and also is the core issue of network virtualization. After research of several years, the virtual network embedding algorithm has made great progress, but still has the following problems:for larger virtual network requests, embedding efficiency isn’t high; the traditional method of virtual network embedding can’t meet the requirements of parallel embedding across the region. To address these problems, this thesis focuses on node locality awareness and link embedding stage, and proposes "virtual network embedding based on gravitational field and locality topology-aware" and "virtual network embedding based on bi-directional searches" respectively. Finally, based on thought of locality awareness and bi-directional searches, "distributed and parallel virtual network embedding framework and algorithm" is proposed. The main contribution of this thesis is concluded as follows:(1) "Virtual network embedding based on gravitational field and locality topology-aware" that computes interaction between network nodes for network node ranking, so it is advantageous to realize the virtual network embedding selection process and cooperate node embedding and link embedding. In this algorithm, topology potential is described as the mutual influence among network nodes for node ranking; the gravitational field can represent the degree of attraction and topology attribute between the mapped node and the candidate embedding nodes, which is beneficial for quick sorting of network nodes, avoiding the frequent updating and large communication overhead of global topology iterative ranking. At the same time, this algorithm makes the underlying network links have good equilibrium, and improves the success rate of the virtual network embedding.(2) Considering the problem of high complexity and low efficiency on virtual network embedding, link-balanced bi-directional search algorithm is proposed, which is based on bandwidth-priority strategy between source node and destination node. Search layer and search space are reduced, so that the efficiency of this algorithm is improved.(3) Based on the thought of locality topology awareness and bi-directional search, the distributed and parallel virtual network embedding framework and algorithm are proposed to realize virtualization and intelligence of network nodes. Taking full advantage of the computing power of the routing nodes and MapReduce, intelligent distributed embedding framework of node autonomy and equivalence is designed, which can deploy parallel distributed online virtual network embedding algorithm based on pheromone and messages. In this framework, the virtual network request is divided into different meta-requests, and the parallel distributed algorithm is completed by substrate nodes distributing meta-request and collecting meta-request embedding result.The research outcomes provide the theoretical basis and technical support for distributed and parallel deployment of virtual network requests in substrate network, and bring the reference value to the virtual network self-healing research.