Efficient Re-Embedding Strategies for Virtual Data Centers over Multi-Domain Substrate Networks

Abstract

Network virtualization (NV) has allowed the service providers (SPs) to logically partition the substrate resources into independent executable entities called virtual data center (VDC). Typically a VDC comprises multiple interactive virtual machines (VMs) and virtual links (VLs) reflecting their communication dependencies. NV brings about multiple benefits to the SPs, including complete service isolation, reduced security threats, higher quality-of-services (QoS) satisfaction, and better utilization of substrate resources. However, it also introduces many research challenges, such as scalability, failure tolerance, monitoring, interfacing, security, pricing, and resource management. This thesis focuses on the issue of resource management– specifically, the objective is to develop efficient complete/selective re-embedding strategies for already embedded VDC experiencing demand fluctuations. In this regard, reassigning resources to the VDC comprises two closely related sub-problems, i.e., reassigning server resources to the VMs, also termed VM re-embedding, followed by reassigning substrate paths to VLs, also termed VL re-embedding. Moreover, both the sub-problems are computationally-intensive intractable problems and are proven to be NP-Hard. Firstly, a genetic-meta-heuristic-based framework called GAMap is proposed that addresses the issue of complete re-embedding of VDC over a multi-domain substrate network catering to their dynamic resource demands. GAMap adopts improved crossover and mutation operations to obtain a re-embedding assignment with minimum re-embedding cost. Although GAMap is efficient and reduces the re-embedding cost, it has pitfalls. Firstly, it is time-consuming, computationally expensive, and not scalable. Secondly, the complete re-embedding of VDC may not always be desirable when only a few components experience a surge/drop in demands. Thirdly, re-embedding the VDC with the minimum re-embedding cost at the expense of under-utilizing substrate resources may not be favorable for the SPs. The second contribution presents a model called ReMatch addressing the shortcomings of GAMap. ReMatch adopts a one-to-many matching theory-based re-embedding strategy that generates a stable, efficient, and polynomial-time re-embedding plan. It reassigns solution components (SCs) instead of the entire VDC, where a SC comprises a VM and its attached VLs with at least the VM and/or one of the VLs experiencing a surge/drop in demands. Moreover, ReMatch adopts an analytical hierarchy process (AHP)-based ranking of servers to minimize re-embedding cost and improve utilization of substrate servers. Although ReMatch could generate stable, efficient, and polynomial-time reassignments, it has the following lacunas. Firstly, the agents’ preferences in ReMatch are static, which can often lead to inaccuracies, especially when multiple SCs of a VDC is re-embedded. Secondly, the utility computation in ReMatch is imprecise as it only considers the available resources and the VM re-embedding cost. To deal with the pitfalls of static preferences of ReMatch, the third contribution discusses a framework called CoMap based on a one-to-many matching between VMs and servers with coalition formation at the servers. Dynamic preferences of VMs are computed in CoMap, considering the substrate network’s current state and the allocation of the dependent VMs. Moreover, the utility computation is upgraded to consider the VM demands and the total re-embedding cost of the relocating SC. The former boosts the utilization of the substrate servers, whereas the latter assists in reducing the re-embedding cost.