Research On Virtual Network Embedding Algorithm In Network Virtualization Environment

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 multi-dimensional resource constraint, virtual network embedding problem is NP-hard so that its solutions almost rely on heuristic-based 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 time-oriented scheduling policy. Without reducing any problem space, current virtual network embedding algorithms can be simply classified as one-stage mapping algorithm and two-stage 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 two-stage algorithm and one-stage algorithm are applied in the core network and edge network, respectively. Moreover, a time-oriented 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 topology-aware virtual network embedding algorithm based on Bayesian network analysis. Topology-aware 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 topology-aware 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 long-term 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 peer-to-peer 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 long-term average revenue and long-term average acceptance ratio.