Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-5072
Main Title: Dynamic aspects of network virtualization
Subtitle: algorithmic and economic opportunities
Translated Title: Dynamische Aspekte der Netzwerkvirtualisierung
Translated Subtitle: algorithmische und ökonomische Möglichkeiten
Author(s): Ludwig, Arne
Advisor(s): Feldmann, Anja
Schmid, Stefan
Referee(s): Feldmann, Anja
Schmid, Stefan
Richa, Andrea
Kellerer, Wolfgang
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: The virtualization trend decouples services from the constraints of the underlying physical infrastructure. This decoupling facilitates more flexible and efficient resource allocations: the service can be realized at any place in the substrate network which fulfills the service specification requirements. This thesis studies such flexibilities in the context of virtual networks (VNets). A VNet describes a set of virtual nodes which are connected by virtual links; both nodes and links provide certain QoS or resource guarantees. The network virtualization paradigm envisions an Internet where customers can request arbitrary VNets from one or multiple substrate providers (e.g., an ISP or even indirectly via a broker). Indeed, network virtualization not only introduces flexibilities but also economical opportunities or even VNet markets: an aspect which has hardly been studied so far. We, in the first part of this thesis, investigate opportunities and challenges of such a possible market. We identify a fundamental tradeoff between specification details given by the customer and embedding efficiency on the provider side. In particular, we introduce a formal framework, called the Price of Specificity (PoS), to reason about and quantify this tradeoff. Subsequently, we study buying and pricing strategies for VNets: taking into account the multi-resource nature of VNets as well as possible discounts for larger quantities. We observe that the problem can be seen as multi-dimensional parking permit problem and present online algorithms as well as a competitive analysis, showing that our algorithms are asymptotically optimal. Network virtualization not only introduces challenges in terms of embedding and pricing. Especially long-lived VNets also need to be adapted and reconfigured over time (e.g., due to maintenance, new specifications, or load balancing). However, we observe that changing VNets adaptively in a consistent manner is non-trivial, as changes typically need to be communicated to and implemented at different and distributed components simultaneously. At the same time, ensuring consistency during updates is critical in virtualized environments where isolation needs to be provided between users and services sharing the same resources. Hence, in the second part of the thesis we study how to dynamically update VNets in a consistent way. In particular, we present a formal model and devise efficient algorithms to update SDN (Software Defined Networking)-based VNets such that security-critical functionality (like firewalls) are always traversed and loops avoided. We formally prove the correctness and efficiency of these algorithms, but also prove computational hardness results.
Virtualisierung ermöglicht es mehreren Services gemeinsam, auf derselben physikalischen Infrastruktur bereitgestellt zu werden und diese somit effizienter zu nutzen. Nachdem die Virtualisierung von Endsystemen, beispielsweise in der Cloud, schon erfolgreich umgesetzt wird, findet dieser Trend jetzt auch vermehrt im Netzwerk statt. Virtuelle Netzwerke (VNetze) definieren ein Netzwerk aus virtuellen Knoten und Kanten mit Ressourcengarantien, welche flexibel von den Nutzern spezifiziert und direkt von Providern oder indirekt via Broker gemietet werden können. Gegenstand dieser Arbeit sind die ökonomischen und algorithmischen Herausforderungen eines solchen VNetz-Marktes. Im ersten Teil untersuchen wir den Einfluss von Anforderungen unterschiedlichen Detailgrads auf das Einbettungsproblem. Dieses beschreibt das Problem von ressourceneffizienten Abbildungen der virtuellen auf die physikalischen Netze. Als Metrik, um die Auswirkungen der Flexibilität auf die Effizienz zu bestimmen, führen wir hierzu den Price of Specificity (PoS) ein. Wir analysieren, basierend auf den flexiblen Anforderungen, verschiedene Miet- und Preismechanismen unter Berücksichtigung von möglichen Rabatten auf größere Verträge. Wir zeigen, dass das Ressourcenmietproblem bei unbekannter Nachfrage einer mehrdimensionalen Variante des Parking-Permit-Problems entspricht, für die wir einen asymptotisch optimalen Algorithmus präsentieren. VNetze bieten allerdings nicht nur Herausforderungen bezüglich der Einbettung und dem Ressourcenhandel. Insbesondere VNetze von langer Dauer müssen beispielsweise aufgrund von Anforderungsänderungen seitens des Kundens oder aufgrund von Lastverteilung seitens des Providers zur Laufzeit geändert werden. Diese Änderungen sind nicht trivial, da sie viele Netzwerkkomponenten betreffen, die jeweils individuell angepasst werden müssen. Im zweiten Teil der Arbeit untersuchen wir daher Algorithmen, um diese Netzwerkänderungen effizient und konsistent durchzuführen. Wir betrachten dabei SDN (Software Defined Networking) basierte VNetze und gehen von einem logisch zentralisierten Controller aus, der eine globale Übersicht über das Netzwerk hat. Trotz dieser globalen Sicht ist es nicht trivial, diese Netzwerkänderungen durchzuführen, da es zu Verzögerungen bei der Umsetzung der Änderungen auf den einzelnen Netzwerkkomponenten kommen kann. Wir betrachten konsistente Netzwerkänderungen mit einem Fokus auf Zyklen-Freiheit und Wegpunkt-Garantie. Zu diesem Zweck präsentieren wir eine Komplexitätsanalyse der Probleme, sowie effiziente Algorithmen zu deren Lösung.
URI: http://depositonce.tu-berlin.de/handle/11303/5397
http://dx.doi.org/10.14279/depositonce-5072
Exam Date: 4-Feb-2016
Issue Date: 2016
Date Available: 4-Apr-2016
DDC Class: DDC::000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme
Subject(s): network virtualization
SDN
network updates
embedding problem
consistency
Netzwerkvirtualisierung
Netzwerkaktualisierung
Einbettungsproblem
Konsistenz
Creative Commons License: https://creativecommons.org/licenses/by/4.0/
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Telekommunikationssysteme » Publications

Files in This Item:
File Description SizeFormat 
ludwig_arne.pdf3.05 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.