[Back]

J. Inführ:
"Optimization Challenges of the Future Federated Internet";
Supervisor, Reviewer: G. Raidl, K. Tutschku; Institut für Computergraphik and Algorithmen, 2013; oral examination: 2013-11-27.

The Internet has ossified. It has lost its capability to adapt as requirements change. A fitting
practical example for ossification is the introduction of IPv6. It has been specified in 1998 to
solve, among other things, the forseeable Internet address shortage. The addresses have begun
to run out in 2011 and still IPv6 does not see any wide-spread usage; hacks like network address
translation reduce the need to switch.
A promising approach for solving this problem is the introduction of network virtualization.
Instead of directly using the single physical network, unchangeable to a large degree and working
just well enough for a limited range of applications, multiple virtual networks are embedded on
demand into the physical network, each of them perfectly adapted to a specific application class.
Compute capabilities within the network are provided to the virtual networks, enabling them to
offer their own customized topologies, routing, resource management and naming services.
There are still numerous unsolved problems regarding network virtualization, ranging from the
implementation of virtualizable routers to economic aspects. In this thesis, we focus on the
problem of resource allocation. All virtual networks, with all the resources they require (e.g.,
bandwidth), still need to fit into the available physical network. Our aim is not merely finding an
arbitrary solution, we want to fit the virtual networks in a cost-optimal way. This is the core of
the Virtual Network Mapping Problem (VNMP), an NP-complete Combinatorial Optimization
Problem.
We present several heuristic and exact approaches for solving the VNMP. As heuristic methods
we investigate Construction Heuristics, Local Search, Variable Neighborhood Descent,
Memetic Algorithms, Greedy Randomized Adaptive Search Procedures, and Variable Neighborhood
Search. The exact approaches we develop are based on Constraint Programming and
Integer Linear Programming. In addition to analyzing different solution methods and comparing
their various strengths and weaknesses, we present a strong preprocessing method for VNMP
instances. This preprocessing method can determine which parts of the physical network each
virtual network can and cannot use. We show that preprocessing is essential for solving large
VNMP instances with exact methods.
For finding a valid mapping of virtual networks into substrate networks, the preprocessing
method is powerful enough to make Integer Linear Programming the solution method of choice.
For low-cost solutions, the situation is more complex. Integer Linear Programming is the best
method for small to medium instance sizes. If run-time is a concern, our Memetic Algorithm
and Variable Neighborhood Search approaches can be used to great effect, achieving costs within
5% of the exact method. For large instances, we conclude that Variable Neighborhood Descent
performs best.

Das Internet wie wir es heute kennen hat seine Fähigkeit verloren, sich an ändernde Bedingungen
anzupassen. Es gilt als "erstarrt". Ein prägnantes Beispiel ist die Einführung von IPv6.
Dieses Protokoll wurde schon 1998 spezifiziert, um unter anderem der bevorstehenden Internet-
Adressknappheit entgegenzuwirken. Obwohl die Adressen seit 2011 zur Neige gehen, wird IPv6
noch immer nicht großflächig eingesetzt. Notlösungen wie Netzwerk-Adressübersetzung reduzieren
die Notwendigkeit eines Wechsels.
Ein vielversprechender Ansatz um wieder Flexibilität in das Internet zu bringen ist Netzwerkvirtualisierung.
Statt eines einzigen unflexiblen physischen Netzwerks, das eine Reihe von Anwendungen
gerade noch ausreichend unterstützt, werden mehrere virtuelle Netzwerke, die voll und
ganz auf verschiedene Anwendungsfälle ausgerichtet sind, in das physische Netz eingebettet.
Bevor Netzwerkvirtualisierung großflächig eingesetzt werden kann, gilt es noch eine Vielzahl
von Problemen zu lösen, von der Implementierung von virtualisierbaren Routern bis hin zu
wirtschaftlichen Aspekten. In dieser Dissertation konzentrieren wir uns auf Ressourcenverteilung
und -belegung. Die verschiedenen virtuellen Netze, samt ihren benötigten Ressourcen (z.B.
Bandbreite), müssen ein einem einzigen physischen Netz untergebracht werden. Unser Ziel ist
jedoch nicht, eine beliebige Einbettung der virtuellen Netze in das physische Netz zu finden, sondern
eine kosten-optimale. Das ist der Kern des Virtual Network Mapping Problems (VNMP),
ein NP-vollständiges kombinatorisches Optimierungsproblem.
In dieser Arbeit untersuchen wir heuristische und exakte Ansätze zur Lösung des VNMP. Die
heuristischen Methoden sind Konstruktionsheuristiken, Lokale Suche, Variable Neighborhood
Descent, Memetische Algorithmen, Greedy Randomized Adaptive Search Procedures und Variable
Neighborhood Search. Als exakte Verfahren entwickeln wir Ansätze, die auf Constraint
Programming und Integer Linear Programming basieren. Zusätzlich zur Analyse der vorgestellten
Algorithmen und des Vergleichs ihrer Stärken und Schwächen präsentieren wir auch eine
Vorverarbeitungsmethode für VNMP Instanzen. Wir zeigen, dass diese Vorverarbeitung ein essenzieller
Schritt für die Anwendung von exakten Verfahren auf große VNMP Instanzen ist.
Nur durch die Vorverarbeitung ist es möglich, dass unser Integer Linear Programming Ansatz
unabhängig von der Instanzgröße ein exzellentes Verfahren ist, wenn es um das Finden einer
beliebigen Einbettung geht. Für die Suche einer kosten-optimalen Lösung ist die Wahl der besten
Methode komplizierter. Integer Linear Programming liefert die besten Ergebnisse bis zu
mittleren Instanzgrößen, jedoch nur unter hohem Zeitaufwand. Gilt es diesen zu minimieren,
sind unsere Memetischen Algorithmen und Variable Neighborhood Search Ansätze vielversprechend.
Die damit erreichten Kosten liegen nur 5% höher als die der exakten Methode. Für große
Instanzen bietet Variable Neighborhood Descent die beste Lösungsqualität.

http://publik.tuwien.ac.at/files/PubDat_223153.pdf