Research on Virtual Network Embedding Algorithm in Network Virtualization Environment 

Author  QingSuDe 
Tutor  LiaoJianXin 
School  Beijing University of Posts and Telecommunications 
Course  Computer Science and Technology 
Keywords  Network virtualization Virtual network embedding Kcore decomposition Bayesian network analysis Machine learning Bloom filter 
CLC  TP393.01 
Type  PhD thesis 
Year  2013 
Downloads  7 
Quotes  0 
Network virtualization is promoted as a powerful vehicle to solve the ossification of the Internet architecture so that it has attracted increasing attention in both academia and industry. To integrate network virtualization into the future Internet architecture, a big challenge, how to map multiple heterogenous virtual networks onto the shared substrate network, known as virtual network embedding problem, should be solved. Due to multidimensional resource constraint, virtual network embedding problem is NPhard so that its solutions almost rely on heuristicbased algorithms. Our work focuses on improving the performance of virtual network embedding algorithm. Our paper presents the following four major contributions:(1)A survey of the latest research progress of virtual network embedding algorithm is conducted in detail to divide current virtual network embedding algorithms into two categories, i.e., algorithms based on one infrastructure provider and algorithms based on multiple infrastructure providers. Within an infrastructure provider, virtual network embedding algorithms can be subdivided further in terms of whether the problem space is constrained and the number of mapping stages. Within multiple infrastructure providers, virtual network embedding algorithms can be subdivided according to the relationship among multiple infrastructure providers in the horizontal and vertical dimension. Moreover, this survey sheds light on the potential future research directions in the conclusion. (2) We propose a hybrid virtual network embedding algorithm with timeoriented scheduling policy. Without reducing any problem space, current virtual network embedding algorithms can be simply classified as onestage mapping algorithm and twostage mapping algorithm. However, every coin has two sides. To exploit the respective advantage of the two classes of algorithm, the virtual network is decomposed into core network and edge netwok, while twostage algorithm and onestage algorithm are applied in the core network and edge network, respectively. Moreover, a timeoriented scheduling policy is introduced to improve the mapping performance by leveraging the fact that the occupied substrate resource will be released after virtual network departs.(3) We propose a topologyaware virtual network embedding algorithm based on Bayesian network analysis. Topologyaware virtual network embedding algorithms efficiently improve the performance by leveraging a node ranking method based on Markov random walk model. However, as the basis of node ranking, the resource evaluation of node may be incorrect. Moreover, a greedy matching strategy is always applied in the node mapping stage, which may lead to unnecessary bandwidth consumption by ignoring the relationships between the mapped substrate nodes and the mapping one. Therefore, we rethink the topologyaware virtual network embedding from a statistical perspective. A statistical method is proposed to generate two dependency matrices, respectively representing the importance of every node and the relationships between every two nodes in the substrate network. Based on these dependency matrices, Bayesian network analysis is adapted to iteratively select the substrate node which has the closest relationship with the mapped nodes to achieve node mapping process. Extensive simulations were conducted and the results show that the longterm average performance of our proposed algorithm is better.(4) We propose a distributed virtual network embedding algorithm based on Bloom filter. Current solutions are almost provided in a centralized way within an infrastructure provider, which may have hot spot problem. In this paper, by leveraging the learning and inference technology, a novel resource evaluation method is proposed without the updated message in the substrate network and virtual network is mapped in a peertopeer way according to its own resource evaluating table. Moreover, instead of flooding which generates massive communication overhead, Bloom filter is introduced to synchronize the mapping information. Finally, explicit comparisons between the centralized algorithms and our distributed algorithm are conducted for the first time and the results show that our proposed algorithm has acceptable, even better performance in terms of longterm average revenue and longterm average acceptance ratio.