Optimization challenges of the future federated internet : heuristic and exact approaches ; Herausforderungen der Optimierung im zukünftigen Internet - heuristische und exakte Ansätze

Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers ; Zsfassung in dt. Sprache ; 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. ; 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. ; 284