Research On Efficient And Reliable Virtual Network Embedding Techniques

The Internet plays an increasingly important role in economic development, social progress and improvement of people’s living standard, which has become one of the most important infrastructures of modern society. Network virtualization allows multiple heterogeneous virtual networks to coexist over a shared substrate network infrastructure, which enables the deployment of new network architectures, protocols, and applications without affecting the existing network service and thus make network innovations easier. Network virtualization provides a viable way to evolve to the future network, and it also should be the key feature of the future Internet.Virtual network (VN) embedding is a major challenge faced by network virtualization. It has become a hot research topic and draws more and more attention from both academic and industrial communities. Although a large body of VN embedding algorithms has been proposed, there is still room for improvement in the following three aspects:(1) VN request acceptance ratio;(2) the utilization of the substrate network resources;(3) the reliability of the embedded VNs. Therefore, through in-depth study of the VN embedding problem from these three aspects, we made the following major contributions:(1) To increase the VN request acceptance ratio, we propose a novel topology-aware node resource ranking measure. Since this measure can reflect not only the resource quality of the node itself but also the resource quality of its neighbors, it provides better heuristic information for the construction of the VN embedding solution. Based on the topology-aware node ranking measure, we propose two new VN embedding algorithms. Both two-stage and one-stage mapping strategies are investigated. The experimental results show that the proposed topology-aware VN embedding algorithms can increase the virtual network acceptance ratio.(2) Aiming at increasing the utilization of the substrate network resource, we first model the VN embedding problem as an integer linear programming and consider the resource cost of VN request as the fitness function. Then, we propose a new VN embedding algorithm based on particle swarm optimization for solving this problem. The experimental results demonstrate that the proposed meta-heuristic based algorithm can generate near-optimal solution without consuming much running time and thus increase the utilization of the substrate network resource.(3) To improve the reliability of the embedded VNs, we introduce the survivable routing problem of VN embedding and establish a mathematical model for this problem. To address this problem, we put forward a heuristic algorithm called cut-aware VN embedding. The experimental results show that the proposed cut-aware VN embedding algorithm can effectively obtain the VN embedding solution with survivable routing. VN embedding with survivable routing provides a new and lightweight way to guarantee the reliability of the embedded VNs, which makes a complementary to the previous studies on the reliability of VN embedding.