Research On Key Technology Of Virtual Network Provisioning Across Multiple Substrate Networks

With the coming of the new century, the tide of the internationalization and the impact of the market economy is oncoming. A great amount of new Internet applications appear. These applications bring great challenges to the security, scalability and QoS of substrate networks in the traditional Internet infrastructures. As a promising solution to these challenges, network virtualization can ensure resource sharing, enable heterogeneity on a substrate network, and enhance the network diversity.Substrate networks are run by different infrastructure providers(InPs) in real life. Thus it is a key problem to embed virtual networks across multiple substrate networks run by different InPs. In this paper, we focus on this problem and discuss the provisioning of virtual networks. We divide the provisioning of virtual networks into four steps, i.e., resource matching, splitting of virtual network requests, embedding of virtual networks, and resource binding. Performance of such scheme is evaluated through extensive simulations.In Chapter I, we first briefly introduce the concept of network virtualization, and then present the definition and challenges of virtual network provisioning across multiple substrate networks.In Chapter II, we first build a mathematical model to describe the provisioning of virtual networks. Then we present the concept of resource matching in the provisioning of virtual networks. Based on this concept, we propose a resource matching mechanism, which firstly organize and classify network resources using conceptual clustering techniques, and generate a dendrogram, so that resources can be matched using a similarity-based matching algorithm. The main contribution of Chapter II is to optimize the requests splitting of virtual networks across domains at minimal costs. To split the requests, we propose heuristics based on network flows, and exact algorithms as well. We build up extensive simulations to evaluate the performance of proposed algorithms. Numerical results reveal that exact algorithms perform better in small networks; while heuristics is fit for large networks.Chapter III describes the embedding process of virtual networks. We first propose an embedding algorithm which optimizes mappings of links and mappings of nodes simultaneously. The proposed algorithm can reduce the cost of virtual networks embedding and improve the request acceptance ratio. We manipulate the embedding process in two ways, i.e., SRP and PRP, to evaluate the performance of the proposed algorithm. Simulation results suggest that the proposed algorithm performs better in small networks; while more requests are accepted with fewer costs when PRP is deployed. Then we consider the embedding of virtual links between VN sub-graphs after all VN sub-graphs are embedded. Heuristics based on shortest paths and multi-commodity flows are proposed. Observations of performance evaluation show that heuristics based on multi-commodity performs better, in terms of request acceptance ratio and embedding cost. Resource binding and updating are performed in the last step.Chapter IV introduces the simulation platform used in this paper. Chapter V concludes the paper, and discuss future work of virtual network provisioning.