Virtual Network Deployment For Efficient Resource Allocation

In network virtualization environments, the resource demands from service providers are no longer either computing or networking resources, but evolve into structural resource combinations in the form of virtual networks. How to properly deploy virtual network requests on top of a shared physical network with resource constraints, so as to achieve efficient resource allocation, is a research problem of utmost importance and interest. We found that most of prior studies do not take dynamic resource demands of virtual networks or physical location constraints of virtual machines into account. On one hand, the randomness of end users and the dynamics of applications themselves make the amount of physical resources actually utilized by virtual networks fluctuate over time; on the other hand, service providers usually would like to restrict the physical locations of virtual machines for the pur-poses of security, backup, network coverage, etc. Based on these understandings, we conduct a comprehensive study on the methods for virtual network deployment with dynamic resource demands and physical location constraints. Besides, we improve virtual network deployment from three different yet gradual perspectives, i.e., single physical node, single physical network, and multiple physical networks. The main contributions of this dissertation are summarized as follows:(1) We propose an opportunistic resource sharing-based virtual network de-ployment framework, ORS, for embedding virtual networks with dynamic resource demands. ORS shares physical resources among multiple service providers, not only decreasing service providers’cost, but also increasing infrastructure providers’rev-enue. In ORS, the macro-level mapping adopts the greedy strategy; the micro-level resource sharing problem is formulated as a time slot assignment problem, which is proven to be NP-hard in the strong sense by a reduction from the 3-partition problem. We propose an optimal algorithm based on integer linear programming and two first-fit-based approximation algorithms. Re-arrangements are periodical-ly performed to avoid fragmenting physical resources. Simulation results show the significant performance improvement of ORS over two state-of-the-art algorithms.(2) We propose two deployment algorithms, MIPA and SAPA, which put par-ticular emphasis on optimizing physical resource utilization and providing resource allocation flexibility, respectively, for embedding virtual networks with physical loca-tion constraints. MIPA transforms the deployment problem into a multi-commodity flow problem through augmenting the physical network with shadow nodes and do- main head nodes, and adopts LP relaxation and randomized rounding in solving the problem. Simulated annealing-based SAPA allows infrastructure providers to flexi-bly control the tradeoff between performance and running time. Simulation results confirm the advantages of both algorithms.(3) We design three algorithms for optimizing virtual network deployment from three different yet gradual perspectives, namely, single node parallelization, single network topology-awareness, and multiple-network stable allocation. Through sup-porting parallelization, we design two parallelization-based algorithms, ProactiveP and LazyP; in order to force virtual machines from the same virtual network live close with each other in the physical network, we develop a Markov chain-based node ranking algorithm, MCRank; when there are multiple virtual network requests and multiple physical networks, each of which has a preference list over the opposite entities, we design a proposal-based grouping algorithm, PGA, to avoid unstable al-locations. Simulation results prove the feasibility and effectiveness of the proposed algorithms.