Algorithmen zum effizienten Deployment virtueller Netzwerkservices

Beck, Michael (2017): Algorithmen zum effizienten Deployment virtueller Netzwerkservices. Dissertation, LMU München: Fakultät für Mathematik, Informatik und Statistik

Abstract

Die Virtualisierung von Netzfunktionen (NFV, Network Function Virtualization) ist ein zentrales Konzept zukünftiger Mobilfunknetze: Statt wie in klassischen Netzen rein auf Hardwarekomponenten zu setzen, deren Logik untrennbar mit der eigentlichen Hardware verwoben ist, wird die Funktionalität in NFV-Netzen innerhalb virtueller Netzwerkfunktionen gekapselt und von der eigentlichen physischen Hardware separiert. Hochspezialisierte Hardwareboxen werden durch viel flexiblere Standardhardware ersetzt, auf der nun unterschiedliche Netzwerkfunktionen installiert werden können. Ein Kernkonzept dabei ist die Integration von Cloud Computing-Technologien innerhalb der Mobilfunk-Kerninfrastruktur: Dies ermöglicht es dem Mobilfunkprovider, die Konfiguration des Netzes viel dynamischer an die sich ständig verändernden Anforderungen des Marktes anzupassen. Sollen neue Netzwerkservices installiert werden, kann dazu ein Großteil der bereits vorhandenen physischen Infrastruktur wiederverwendet werden; die vorhandene Hardware muss nicht komplett ausgetauscht werden. Die Integration neuer Services erfolgt stattdessen durch den wesentlich kosteneffizienteren Austausch von (virtuellen) Netzwerkfunktionen -- und nicht durch Austausch von Hardware. Mobilfunkprovider werden in Zukunft in der Lage sein, viel einfacher und effizienter zusätzliche Netzfunktionen dort zuzuschalten, wo sie gebraucht werden, ohne dass jedes Mal Änderungen an der eigentlichen Hardware-Konfiguration erforderlich werden. Darüber hinaus können Netzfunktionen flexibel auf andere Komponenten migriert werden, wenn Hardwarekomponenten aus wartungstechnischen Gründen temporär oder dauerhaft außer Betrieb genommen werden. Die vorliegende Arbeit befasst sich mit der Thematik, wie sich derartige virtuelle Netzwerkservices innerhalb des physischen Netzwerks der Provider einbetten lassen. Im Mittelpunkt steht die Frage, auf welchen Hardwarekomponenten die verschiedenen (virtuellen) Netzwerkfunktionen installiert werden sollen. Aus theoretischer Sicht ist die optimale Berechnung eines solchen Deployments ein NP-hartes Optimierungsproblem. Optimale Algorithmen zur Lösung dieses Problems sind daher nur in sehr kleinen Szenarien anwendbar. Für die effiziente Lösung im Zusammenhang mit Szenarien realer Größenordnung kommen aus diesem Grund nur heuristische Ansätze in Betracht, die für die Bestimmung eines guten, aber nicht zwingenderweise optimalen Deployments entworfen werden. Die vorliegende Arbeit befasst sich mit der effizienten, heuristischen Lösung dieses NP-harten Deployment-Problems. Es wird zunächst eine Simulationsumgebung beschrieben, die die umfassende Evaluation von Deploymentalgorithmen ermöglicht. Anders als bisherige Simulationstools lässt sich die hier beschriebene Umgebung sehr einfach um neue Funktionen erweitern. Daran anschließend wird ein verteilter Deployment-Algorithmus vorgestellt, der virtuelle Netze innerhalb von Cloud-Infrastrukturen effizient einbetten kann (DPVNE, Distributed and Parallel Virtual Network Embedding). Kernidee hinter diesem Ansatz ist die Aufteilung der physischen Cloud-Infrastruktur in hierarchisch organisierte Netzwerkpartitionen. Dies ermöglicht die parallele Einbettung virtueller Netze. Durch die Verteilung des Berechnungsaufwands auf mehrere Knoten lässt sich das Deployment-Problem auch in Szenarien mit sehr großen Netzwerkinfrastrukturen lösen. Darüber hinaus wird ein Backtracking-basierter Algorithmus vorgestellt, mit dem das Deployment virtueller Netzwerkservices in NFV-Szenarien durchgeführt werden kann (CoordVNF, Coordinated deployment of Virtual Network Functions). In NFV-Szenarien liegt der Fokus auf der Betrachtung der Netzwerkservices, die zur Verarbeitung von Datenströmen innerhalb der Infrastruktur des Mobilfunkproviders installiert werden. Jeder Netzwerkservice besteht dabei aus mehreren (virtuellen) Netzwerkfunktionen, die verschiedene Operationen auf empfangene Daten anwenden und diese dann zur Weiterverarbeitung an andere Netzwerkfunktionen weitergeben. Die genaue Reihenfolge, in der die Datenströme durch die einzelnen Netzwerkfunktionen geroutet werden, ist dabei nicht eindeutig vorgegeben. Anders als in Cloud-Szenarien ist die Struktur der einzubettenden virtuellen Netze also in Teilen flexibel, was zu interessanten neuen, theoretischen Aspekten bzgl. des Deployment-Problems führt. Der CoordVNF-Algorithmus ist als einer der ersten Ansätze in der Lage, solche flexiblen NFV-Netzwerkservices effizient innerhalb der Infrastruktur des Mobilfunkproviders zu platzieren. Im Gegensatz zu bisherigen Verfahren kann CoordVNF auch im Zusammenhang mit größeren Infrastrukturen verwendet werden. Abschließend wird das Deployment ausfallsicherer Netzwerkservices diskutiert. In diesem Kontext wird beschrieben, wie sich die Robustheit eingebetteter NFV-Services durch Reservierung zusätzlicher Backup-Ressourcen erhöhen lässt. Aufbauend auf CoordVNF wird dann ein Deploymentalgorithmus vorgestellt, der in der Lage ist, Einbettungen gegenüber Ausfällen abzusichern (SVNF, Survivable deployment of Virtual Network Functions).

Abstract

Network Function Virtualization (NFV) is being considered as an emerging key technology for future mobile network infrastructures. In classical networks, network functions are tightly bound to specific hardware boxes. In contrast, in NFV networks, (software) functionality is separated from hardware components. Highly specific hardware boxes are being replaced by commodity computing, networking, and storage equipment, offering resources for hosting and running more than just one specific type of network function. One of the key concepts of NFV is the integration of cloud computing technology into the network core: This enables virtual network functions to be installed and deployed where they are needed; additional resources can be dynamically provided in times of high demand, whereas virtual functions can also be consolidated on a smaller hardware setting if demand decreases. NFV enables operators to manage network functions in a much more flexible way, without having the need of instructing technicians to manually reconfigure hardware equipment on-site -- instead, network functions can be deployed and managed remotely. Additionally, for reliability reasons, virtual network functions can be easily migrated to backup resources in case of hardware or software failures. This thesis discusses the question on how those virtual network functions can be efficiently deployed within the physical network infrastructure. From a theoretical perspective, finding the optimal deployment of virtual network services (e.g., in terms of embedding cost) is known as a NP-hard optimization problem. In this context, the thesis introduces heuristic approaches for solving the deployment problem. To this end, first, an extensible simulation framework is discussed which enables researchers to thoroughly evaluate both existing and novel deployment algorithms. Second, a distributed algorithm (DPVNE) is presented for embedding virtual networks into a shared physical cloud infrastructure. Here, the main idea is to partition the physical network into several smaller, non-overlapping network regions. Embeddings in those network partitions can then be performed in parallel: Computational efforts can be spread to multiple distributed nodes. This way, solving this NP-hard optimization problem becomes feasible even in large-scale network scenarios where virtual network deployment requests arrive continuously. Third, a backtracking-based algorithm (CoordVNF) is presented in this thesis for the deployment of virtual network functions in NFV scenarios. In contrast to cloud scenarios, in NFV scenarios, the exact chaining of network functions is not always predefined: In fact, the same network service can be provided by several chainings of network functions. The first embedding algorithm presented here aims to deploy those flexible virtual network services in a cost- and time-efficient way, even in large-scale scenarios. Finally, the thesis discusses the deployment of resilient NFV services; in this context, an extension of the CoordVNF algorithm is presented that allocates additional backup resources for protecting network services from failures.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Fakultäten: Fakultät für Mathematik, Informatik und Statistik
• Sprache der Hochschulschrift: Deutsch
• Datum der mündlichen Prüfung: 7. Februar 2017
• 1. Bericht­erstatter:in: Linnhoff-Popien, Claudia