Typ der Arbeit: Master-Thesis
Bearbeitungsstand: Abgeschlossene Arbeiten
Möglicher Beginn der Arbeit: 06.04.2021
Arbeit abgeschlossen am: 05.10.2021
Betreuer*in: M.Sc. Sebastian Ehmes
Student*in: Maximilian Kratz

Zurück zur Übersicht

Motivation

In Rechenzentren werden virtuelle Netzwerke zur effizienten Nutzung von Ressourcen eingesetzt, um Dienste bereitzustellen. Die Anzahl an virtuellen Netzwerken übersteigt die Anzahl an physikalischen (Substrat-)Netzwerken dabei in der Regel. Der Vorgang einer Einbettung eines virtuellen auf einem Substratnetzwerk wird Virtual Network Embedding (VNE) genannt und beinhaltet die Abbildung von virtuellen Elementen wie Servern und Switchen auf die physikalischen Gegebenheiten. Dadurch entsteht eine Entkopplung zwischen den Diensten (virtuelle Netzwerke) und der Hardware (Substratnetzwerke), wodurch es den Betreiber:innen von Rechenzentren ermöglicht wird, ihre Infrastruktur besonders wirtschaftlich und effizient betreiben zu können. Das Problem der Einbettung ist NP-hart, wodurch die Anzahl an möglichen Einbettungen exponentiell ansteigt, je größer die Netzwerke werden.

Grundsätzlich gibt es zwei verschiedene Lösungsansätze für das Einbettungsproblem: (1) Heuristiken und (2) Algorithmen, welche eine optimale Einbettung erzielen. Ob eine gewählte Einbettung optimal ist, bestimmt dabei eine Kostenfunktion, welche beispielsweise zu minimieren ist. Der MdVNE-Ansatz kombiniert Graphtransformationen mit ILP-Technologie um eine (nach aktuellem Stand optimale) Einbettung für virtuelle Netzwerke zu finden. Durch den Vorgang der Graphtransformation wird die Anzahl der möglichen Einbettungen durch Anwendung von vorher definierten Regeln reduziert. Anschließend berechnet ein ILP-Solver aus der Menge von möglichen Einbettungen jene, welche die gewählte Kostenfunktion minimiert, wodurch die optimale Lösung des Einbettungsproblems gefunden wird. Trotz der Reduktion des Suchraums aller möglichen Einbettungen leidet der MdVNE-Ansatz darunter, dass das VNE-Problem NP-hart ist. Die Laufzeit und der Speicherplatzverbrauch steigen bei immer größer werdenden Netzwerken stark an, weswegen der Ansatz aktuell nur für kleinere Netzwerke sinnvoll einsetzbar ist. In der Praxis dürfen Algorithmen zur Einbettung virtueller Netzwerke keine sehr große Ausführungszeit benötigen, da das Finden der Lösung zeitkritisch ist und Ressourcen verbraucht. Aus diesem Grund besteht großes Interesse, den MdVNE-Ansatz hinsichtlich Laufzeit und Ressourcen-Verbrauch zu optimieren, um die Skalierbarkeit zur verbessern und ihn praxistauglicher zu gestalten.

Aufgabenstellung

Der bislang verfolgte Ansatz zur modellgetriebenen Einbettung von virtuellen Netzwerken in Substratnetzwerke basiert auf einer Kombination von graphtransformationsbasierten (GT-basierten) und „Integer Linear Programming“-basierten (ILP-basierten) Technologien. Allerdings leidet dieser Ansatz stark unter der exponentiellen Explosion des Zustandsraums aller möglichen Einbettungen einer Menge virtueller Netzwerke in ein Substratnetzwerk. Dieses exponentielle Wachstum wird nicht nur durch das grundsätzlich „teure“ Aufbauen eines Zustandsraums zur ILP-basierte Auswahl einer optimalen Einbettung, aus der Menge aller potentiell zulässigen Einbettungen, durch den ILP-Solver getrieben, sondern auch stark durch die GT-basierte Identifikationsphase aller potentiell zulässigen Einbettungen beeinflusst.

Ziel dieser Arbeit ist es deshalb zuerst Stellschrauben für die Rechenzeit- und Speicherplatzkomplexität des MdVNE-Ansatzes zu untersuchen und geeignete Ansätze zur Verbesserung zu identifizieren. Im Anschluss werden dann vielversprechende Ansätze zur Verbesserung der Performance des MdVNEAnsatzes implementiert und hinsichtlich Qualität der Einbettungen und Performanz evaluiert.

Dafür bieten sich im Rahmen dieser Arbeit folgende Angriffspunkte an:

• Relaxierung der Anforderungen an die Optimalität der Lösungen, die durch den ILP-Solver geliefert werden. Man erlaubt also dem ILP-Solver in gewissen Grenzen vom Optimum, bezogen auf eine vorgegebene Kostenfunktion, abzuweichen.

• Erweiterung des Substratnetzwerk-Metamodells, um beispielsweise verschiedene Arten von Substratservern (High-Performance, Data-Server etc.), Substratswitches (Optische Switches, 10 Gbit s−1 , 100 Gbit s−1 etc.), was zur stärkeren Typisierung der Graphmuster genutzt werden kann und folglich die Kandidatenmengen reduziert. Zusätzlich könnte man Substratservern, bestimmten Substratracks zuweisen, um so spezifischerer Einbettungsregeln zu formulieren und eine signifikante Reduktion der Anzahl zulässiger Einbettungen von virtuellen Prozessen oder Kommunikationsverbindungen zu realisieren.

• Entfernung von dem Optimalitätsanspruch durch GT-basierte Einbettungsheuristiken. Mit Hilfe stärkerer Einschränkungen bei der Suche der geeigneten Einbettungskandidaten (z. B. Einbettungen dürfen nur innerhalb eines Racks stattfinden) lässt sich die Kandidatenmenge entscheidend reduzieren und damit das ILP-basierte Lösen des Problems vereinfachen. Umgekehrt ist es so möglich, dass unter Umständen keine Einbettungen gefunden werden können.

• Betrachtung etablierter VNE-Heuristiken, die möglicherweise als Vergleich herangezogen werden können oder als Inspiration für GT-basierte Heuristiken dienen können.

Zurück zur Übersicht