Research On Virtual Netwoek Embedding Algorithms And Mechanisms

The ossification problem is hiding beneath the current flourishing Internet and becoming increasingly severe, which impedes further development and innovation of network services and applications. That is the reason why the next-generation network architecture has become a research hotspot in worldwide academia. As a promising technology and an essential ingredient of the next-generation network, Network Virtualization provides a promising solution, which allows multiple isolated and heterogeneous virtual networks to coexist and run on a shared substrate network, by abstracting physical network resources to slices of virtual network resources. A key challenging problem in Network Virtualization is the Virtual Network Embedding (VNE)problem, that is how to effectively and efficiently embed/map/allocate virtual nodes and links of heterogeneous virtual networks onto specific nodes and links of the shared substrate network. This thesis focuses on the VNE problem, and presents the following contributions:(1) The business roles and models, problem modelling, and research status of the VNE problem are thoroughly studied. The role decoupling vertically is happening in the horizontally converging future network, and thus a refined 5-layer business model for Network Virtualization and the VNE problem is accordingly proposed, which may better lead the general study and algorithm design of VNE. Besides, the VNE problem is reasonably modelled from the aspects of virtual networks, substrate networks, mapping functions and objectives. Existing VNE algorithms are also thoroughly studied according to different categories, and their advantages and disadvantages are analyzed in detail to find the promising directions for the design of new VNE algorithms.(2) Multiple topology-aware VNE algorithms based on different topological characteristics are proposed to improve the embedding performance of existing VNE algorithms which barely consider topological attributions of networks. The following seven complementary characteristics that reflect different topological attributes are introduced into the VNE problem: “degree",“strength","farness centrality","closeness centrality", "betweenness centrality", “eigenvector centrality"and "Katz centrality". Different topological characteristics measure the relative importance and influence of substrate nodes or virtual nodes in different ways, and thus multiple node ranking algorithms are designed by leveraging their respective advantages. In addition, a modified K-core decomposition algorithm based on two topological characteristics "degree" and"strength" is also devised, trying to better disentangle the hierarchical topological structure of virtual networks by leveraging multiple topological characteristics. Due to the overall consideration of topological attributions of substrate and virtual networks through multiple characteristics, the proposed topology-aware VNE algorithms better coordinate node and link embedding. Extensive simulations demonstrate that they significantly improve the long-term average revenue, acceptance ratio, and revenue/cost ratio compared to previous algorithms.(3) A novel VNE algorithm based on learning and dependence is proposed to replace existing VNE algorithms adopting a greedy matching strategy in node mapping and a classic node ranking metric with CPU and adjacent bandwidth, which may lead to unnecessary bandwidth consumption and increased network fragmentation. The new VNE algorithm explores not only the potential dependence between the previous mapped and unmapped virtual network requests and the mapping ones, but also the topological relationships between the mapped nodes and the mapping ones. A dependency matrix that represents the importance of substrate nodes and the topological relationships between them is well designed and generated from the collected historical data of embedding. Based on the dependence of nodes in the dependency matrix and the topological relationships between the mapped nodes and the mapping ones, Bayesian inference is also leveraged to iteratively select suitable substrate nodes and achieve the topology-aware node mapping. The proposed VNE algorithm reduces unnecessary bandwidth consumption, alleviates network fragmentation and better coordinates node and link mapping. Extensive simulations prove its effectiveness and demonstrate its better embedding performance compared to previous algorithms.(4) To unite the respective advantages and specialties of existing centralized VNE algorithms and distributed VNE algorithms, a novel cooperative VNE algorithm is proposed. The central controller with a global view is kept in the cooperative algorithm,in charge of general management and control, and at the same time detailed embedding is entrusted to autonomous substrate nodes and carried out in a distributed way. Besides a topology-aware resource evaluation mechanism and a mapping information delivery mechanism based on Bloom Filter, the cooperative algorithm devises customized mapping management policies. Substrate nodes are able to make their own independent mapping decisions, and cooperate closely with the central controller to achieve a successful embedding. The proposed cooperative algorithm inherits advantages from both traditional centralized and distributed algorithms. Extensive simulations prove its effectiveness and demonstrate that it has better acceptance ratio and average revenue than existing algorithms.