Research On Mechanism And Algorithm For Virtual Network Embedding Problem

Internet has become one of the most important communication infrastructures in nowadays world and changed the way of working, studying and living. However, along with the rapid increasing of the network scale and the continued emerging of the multiple requirements, the inherent problems of nowadays Internet architecture have become much harder to avoid, such as scalability, management, QoS, and energy saving. To overcome these problems, there emerges a view of designing the future network architecture in a clean-slate way. In other words, the framework of current Internet could be and should be broke through.Network virtualization is one of the most important researching directions of the future network:on one hand, the future network test-bed could be constructed based on the network virtualization technology, which could support multiple innovative network architectures coexisting on a shared physical infrastructure and running without disturbing each other; on the other hand, the essence of the network virtualization, which is the deep abstraction of the network resource and actions, will become the basic attribute of the future network architecture.Virtual network embedding problem is the mechanism of embedding the virtual network requests to the substrate physical network in a parallel, effective, and fast way with multiple constraints satisfied, such as node CPU, link bandwidth and so on. The virtual network embedding problem is very important since its efficiency will directly affect the industrial prospect of the network virtualization technology. Thus, this paper will dig into the virtual network embedding problem, aim at the parallel on-line processing, efficiency of the substrate resource, and the complexity, optimize the embedding mechanisms and algorithms, try to propose a comprehensive solution, and provide reference for the future research. The main innovations proposed in this paper are as follows:1) Traditional virtual network embedding algorithms mainly focus on enhancing the efficiency of the substrate network resource with trading-off the complexity and practicality. This paper proposes a proximity two steps virtual network embedding algorithm based on the confusion of the respective optimization objectives, which could provide low complexity. Meanwhile, this algorithm exploits the inherent connection between the node embedding step and link embedding step, and greatly enhances the efficiency of the link embedding by adjusting the objective of the node embedding. The simulation results show that, compare to the classic two step algorithm, the proximity two step algorithm not only enhances the efficiency of the substrate network resource and the virtual requests acceptance ratio, but also saves runtime in most conditions, which implies a win-win solution. This is because the new solution promotes the level of the trade-off for the complexity and efficiency.2) It is important to find a way to optimize the embedding algorithm for different virtual network topologies. This paper firstly exploits the request-answer model of the virtual network service, and proposes an advanced multi-topology virtual network embedding mechanism:the user will tag the virtual network request with topology type, and the control panel will recognize the tag and employ the corresponding optimized embedding algorithm. Secondly, to overcome the diversity of the virtual network topology types, this paper proposes a principle to instruct the developing of the arbitrary topology virtual network embedding algorithm. Thirdly, this paper proposes a compound multi-topology virtual network embedding algorithm framework based on the directing principle. The framework contains four types of topology virtual network embedding algorithm, which are star, ring, tree and general. The simulation results show that, the compound multi-topology virtual network embedding algorithm framework greatly enhances the efficiency of the substrate resource, while decreases the runtime. Meanwhile, the acceptance ratio of the new algorithm framework is better than the classic two steps algorithm, while equaling the proximity two steps algorithm.3) To investigate the influence of the virtual network granularity to the embedding algorithm, this paper constructs a new definition for the virtual network embedding problem, which is called equal-scale. Then a reversed irrigation embedding method is proposed to reduce the probability of resource bottleneck. The new method can be used combining with different kinds of embedding algorithms. Moreover, this paper extends the range of the optimization objective to both equal-scale and small-scale, and proposes a bidirectional irrigation method. The simulation results show that, the reversed irrigation method could enhance the quantity of the embedding in equal-scale condition, while the bidirectional irrigation method could achieve a synthetically best embedding quantity and acceptance ratio in all scale conditions.