Loading…
Virtual network embeddings: theoretical foundations and provably good algorithms
Rost, Matthias Johannes
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.
Virtualisierung sowie Techniken zur Isolierung von Ressourcen haben das effiziente Teilen von vernetzten Ressourcen sowohl innerhalb wie auch zwischen Rechenzentren ermöglicht. Um eine verlässliche Qualität in der Diensterbringung für alle Beteiligten zu garantieren, während die Ressourcen effizient geteilt werden, wurden neue Allokationsprobleme für Ressourcen von Nöten. Konkret verlangt das als Virtual Network Embedding Problem bekannte Kernproblem die Einbettung mehrerer virtualisierte Netzwerke auf einem einzelnen physikalischen Netz ohne dabei Ressourcenkapazitäten zu überschreiten. Dieses Problem wurde im vergangenen Jahrzehnt intensiv studiert, es sind jedoch nur wenige theoretische Resultate bekannt.
Um ein besseres Verständnis des VNEPs zu ermöglichen sowie um neue effiziente Algorithmen für das VNEP zu entwickeln, werden in dieser Dissertation die theoretischen Grundlagen des VNEPs studiert. Insbesondere wird die Komplexität des VNEPs betrachtet und die NP-Vollständigkeit unter verschiedensten Restriktionen gezeigt. Weiterhin werden die ersten (parametrisierten) effizienten offline Approximationen gefunden. Während diese Resultate zunächst theoretischer Natur sind, verbinden wir Theorie und Praxis, und leiten, ausgehend von den theoretischen Einsichten, neuartige Algorithmen für das VNEP ab und zeigen deren Anwendbarkeit in umfangreichen Simulationsstudien.
Weiterhin verbessern wir bekannte Lösungen und schlagen neue Mechanismen vor, um Ressourcen effizienter zu nutzen und zu teilen. Spezifisch für die Abstraktion der Virtual Cluster, welche in Rechenzentren benutzt wird, geben wir den ersten optimalen polynomiellen Algorithmus und zeigen eine neuartige Methode auf, um die knappen Bandbreitenressourcen effektiver zu nutzen. Zusätzlich schlagen wir ein kontinuierliches Zeit-Modell für die Einbettung virtueller Netzwerke unter Berücksichtigung temporaler Flexibilitäten vor und validieren diesen Ansatz mittels Simulationsstudien.
