Efficient And Survivable Resource Allocation In Network Virtualization Environment

With the rapid development of the Internet, the scale of the network and the number of its user keep increasing. It is difficult for the traditional IP architecture to adapt to the expansion of the global network Network virtualization emerged as an important means to push the evolution and innovation of the Internet. It supports multiple virtual networks to share the substrate resources in isolation, which enables the creation of virtual networks economically and efficiently and can deploy services on the virtual networks according to users’demands.Efficient and survivable resource allocation is a key for the popularization of network virtualization. Compared to the traditional network, the operation and creation of network services in network virtualization becomes more flexible and diversified, which leads to a higher needs in manageability, cost-efficiency, real-time, and security, etc. Accordingly, resource allocation in network virtualization environment faces some new challenges. First, resource allocation is accomplished by multiple phases, hence we should provide a solution for each phase and consider the relationship between adjacent phases to generate a complete resource allocation scheme. Second, both cost-efficiency and survivability should be considered in resource allocation, hence the tradeoff between the two factors should be found for each phase from an overall perspective. To this end, we study efficient and survivable resource allocation based on the specific requirements of different phases (i.e, virtual resource matching, virtual network partitioning, virtual network mapping and remapping). The contributions are as follows:(1) A knowledge description based virtual resource matching method is proposed in this thesis. For the utility and accuracy of virtual resource matching, the new method first constructs a knowledge base for virtual resource description by the web ontology language and regulates the description of virtual network embedding constraints by a rule query language, and then designs the resource matching algorithm with the help of a rule query tool. Case study shows that our method can guarantee the matching efficiency while supporting accurate numerical attributes matching and diversified embedding constraints description, which provides a reliable input to the virtual network partitioning phase.(2) A genetic algorithm based virtual network partitioning algorithm is proposed in this thesis. For the efficiency and optimization of virtual network partitioning in multi-domain virtual network embedding, the new method codes a partition scheme as a matrix, and iteratively searches the solution space from multiple initial random partition schemes, which approaches the global optimal partition step by step. Theoretical analysis proves that our method has a termination and its searching space can include the whole solution space. Simulations show that our method increases the partitioning efficiency and the deviation of its partition from the optimal partition is less than 5%.(3) A lightweight survivable virtual network embedding method is proposed in this thesis. For the irrational resource allocation of backups in survivable virtual network embedding, we defines the recoverability of a substrate node based on the topology attributes of a substrate network and embeds the critical virtual nodes of a virtual network onto the substrate nodes with higher recoverability. Simulations show that our method effectively increases the utilization of backup resources, and improves the survivability of virtual networks affected by multiple node failures while guaranteeing the embedding efficiency.(4) A virtual network remapping method is proposed to survive multiple node failures. For the recovery of virtual networks after being affected by multiple node failures, our method considers the effect of the topology and capacity attributes of substrate networks, and presents three remapping ways using mixed integer programming with the goal of reducing the penalty incurred by disabled virtual networks, optimizing the connectivity and balancing the loads of the backup resources, separately. Simulations show that the remapping ways have different applicabilities in raising the success rate of virtual network remapping under a multiple node failure model, and can increase the long term business profit for the infrastructure providers.