Virtual network embeddings: theoretical foundations and provably good algorithms
Matthias Rost · DepositOnce · 2019
Virtualization and resource isolation techniques have enabled the efficient sharing of networked resources both inside and across data centers. To guarantee reliable performance for all tenants, while efficiently sharing the available resources, novel resource allocation problems have arisen. Specifically, the core problem, coined the Virtual Network Embedding Problem (VNEP), asks for the embedding of several virtualized networks to the physical network while not exceeding resource capacities. The VNEP has been studied extensively for more than a decade, yet, few theoretic results pertaining to the VNEP are known. To facilitate a better understanding of the VNEP as well as to derive novel efficient algorithms for the VNEP, this thesis studies the theoretical underpinnings of the VNEP. In particular, the computational complexity of the VNEP is studied and the NP-completeness of the VNEP under various restrictions is proven. Furthermore, the first (fixed-parameter) tractable approxi- mations are obtained for the offline setting. While theoretic in nature, we bridge the gap between theory and practice, and, based on our theoretic insights, derive novel algorithms for the VNEP and show their practical applicability in extensive computational evaluations. Furthermore, we improve current state-of-the-art solutions and propose novel mechanisms to more efficiently use and share resources. Considering the virtual cluster abstraction for data centers, we give an optimal polynomial-time algorithm and develop a novel model to more efficiently use the scarce bandwidth resources. Additionally, we propose a novel continuous-time approach to schedule virtual networks under temporal flexibilities and validate the approach using computational studies.