VNS4PCP Optimierung von Glasfasernetzwerken - Diplomarbeit

1. Platz Bundesfinale Jugend Innovativ 2013 - Science

Preis des Joint Research Center der EU

VNS4PCG logo

Variable Neighborhood Search for the Partition Graph Coloring Problem (VNS4PCP): In den weltweiten Datennetzen steigt das zu übertragende Volumen seit Jahren kontinuierlich. Eine Änderung dieses Trends ist nicht abzusehen, insbesondere da datenhungrige Dienste wie Videoplattformen sich ungebrochener Beliebtheit erfreuen. Die Betreiber dieser Datennetze stehen nun vor dem Problem, den immer größer werdenden Datenverkehr bewältigen zu müssen.

Dies kann einerseits durch den Ausbau der Netze erreicht werden, andererseits kann auch eine effizientere Nutzung der aktuellen Infrastruktur ihren Beitrag leisten.

Letzteres bietet zunächst den Vorteil, dass kostenintensive Netzerweiterungen hinausgezögert bzw. im Idealfall sogar vermieden werden können. Aber auch aus umweltpolitischer Sicht ist eine effizientere Nutzung bestehender Netze vorzuziehen, da sowohl die Herstellung als natürlich insbesondere der Dauerbetrieb zusätzlicher Geräte eine Unmenge an Strom benötigt. Alleine der Betrieb der Internet-Infrastruktur verschlingt nach aktuellen Erhebungen bereits rund 0.8% der weltweiten Stromerzeugung, Tendenz steigend.

An diesem Punkt setzt diese Diplomarbeit an: Gegeben ist ein Glasfasernetzwerk, in dem Wellenlängenmultiplexing eingesetzt wird, d.h. über eine Leitung des Netzwerks können gleichzeitig mehrere Verbindungen transportiert werden, solange diese unterschiedliche Wellenlängen des Lichts verwenden, wobei natürlich die maximale Anzahl an parallel verwendbaren Wellenlängen pro Leitung begrenzt ist. Zusätzlich sind die grundlegenden Kommunikationsbedürfnisse der einzelnen Hosts (Computer, Server, ...) innerhalb des Netzwerkes bekannt. Um die Komplexität und den Aufwand im Netzwerk selbst gering zu halten, verwendet jede Verbindung zwischen zwei Hosts nur eine einzige Wellenlänge, d.h. die Datenpakete einer Verbindung werden am Weg zwischen den beiden Hosts für Teilstrecken nicht auf andere Wellenlängen verschoben, um Konflikten mit weiteren Verbindungen aus dem Weg zu gehen. Ziel ist es nun, die Anzahl der benötigten Wellenlängen für die Grundkommunikation zu minimieren, um auf den Leitungen Platz für zusätzliche Verbindungen zu schaffen.

Um dieses Problem lösen zu können, muss es zunächst in ein handhabbares mathematisches Modell umgewandelt werden, konkret in das Partition Graph Coloring Problem: Für jede Kommunikationsverbindung zwischen zwei Hosts stehen in einem vermaschten Netzwerk mehrere unterschiedliche Wege zur Auswahl. In einem ersten Schritt werden nun für jede Verbindung einige sinnvolle (z.B. über Shortest Path Algorithmen ermittelte) Wege ausgewählt. Im mathematische Modell entspricht jeder dieser Wege einem Knoten in einem Graph, wobei die Knoten einer Verbindung zu einem Cluster (Partition) zusammengefasst werden. In einer Lösung muss von allen Knoten eines Clusters genau einer ausgewählt werden, da pro Kommunikationsverbindung nur ein Weg durch das Netzwerk benötigt wird. Weiters werden zwei Knoten in dem Graph durch eine Kante miteinander verbunden, wenn die entsprechenden Wege eine Teilstrecke (Leitung) im Netzwerk teilen. Mit einer solchen Kante wird also ausgedrückt, dass wenn die miteinander verbundenen Knoten ausgewählt werden, dann müssen ihnen unterschiedliche Wellenlängen (Farben) zugewiesen werden, da es sonst auf der gemeinsam verwendeten Teilstrecke zu einer Kollision kommen würde.

PCP-Transformation

In dem so aufgebauten Graph ist nun folgende Aufgabe zu lösen: Der Graph soll mit der minimalen Anzahl an Farben eingefärbt werden, sodass:

  • pro Cluster genau ein Knoten ausgewählt wird (d.h. pro Cluster muss nur genau ein Knoten gefärbt werden) und

  • zwei Knoten, die ausgewählt wurden und miteinander über eine Kante verbunden sind, dürfen nicht die selbe Farbe erhalten.

Dabei handelt es sich um ein NP schwieriges Optimierungsproblem, d.h. beweisbar optimale Lösungen sind für größere Netzwerke nicht in sinnvoller Zeit berechenbar.

Diese Diplomarbeit hat sich nun zum Ziel gesetzt, ausgehend von der für dieses Problem veröffentlichten wissenschaftlichen Literatur ein neues Verfahren zur Optimierung des Partition Graph Coloring Problems zu entwickeln, das bessere und/oder schneller gute Lösungen findet als bisherige Ansätze. Bei der variablen Nachbarschaftssuche (Variable Neighborhood Search) handelt es sich um ein allgemeines Optimierungsverfahren, das, ausgehend von einer Startlösung, verschiedene Nachbarschaften koordiniert, um diese Startlösung schrittweise zu verbessern. Eine Nachbarschaft definiert dabei, wie von einer aktuellen Lösung duch eine kleine Veränderung (z.B. Auswahl eines anderen Knotens innerhalb eines Clusters, Umfärbung eines Knotens, ...) eine neue Lösung erzeugt wird, wobei mitunter Reparaturmechanismen eingesetzt werden müssen, um eine veränderte Lösung wieder gültig zu machen.

Implementiert wird diese Diplomarbeit in C++ unter Linux unter Verwendung von boost, einer C++ Bibliothek, die unter anderem Datenstrukturen und Algorithmen zur Arbeit mit Graphen zur Verfügung stellt. Die Diplomarbeit entsteht in Zusammenarbeit mit dem Institut für Computergraphik und Algorithmen der Technischen Universität Wien, Abteilung Algorithmen und Datenstrukturen (https://www.ads.tuwien.ac.at).

Klasse: 5AHITN

Betreuer: Prof. Mag. DI Dr. Martin Gruber

Team: Moritz Wanzenböck, Lorenz Leutgeb

FotoTeamVNS4PCP