Dynamic aspects of network virtualization

dc.contributor.advisorFeldmann, Anja
dc.contributor.advisorSchmid, Stefan
dc.contributor.authorLudwig, Arne
dc.contributor.grantorTechnische Universität Berlinen
dc.contributor.refereeFeldmann, Anja
dc.contributor.refereeSchmid, Stefan
dc.contributor.refereeRicha, Andrea
dc.contributor.refereeKellerer, Wolfgang
dc.date.accepted2016-02-04
dc.date.accessioned2016-04-04T14:28:47Z
dc.date.available2016-04-04T14:28:47Z
dc.date.issued2016
dc.description.abstractThe 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.en
dc.description.abstractVirtualisierung 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.de
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/5397
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-5072
dc.language.isoenen
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subject.ddc000 Informatik, Informationswissenschaft, allgemeine Werkede
dc.subject.othernetwork virtualizationen
dc.subject.otherSDNen
dc.subject.othernetwork updatesen
dc.subject.otherembedding problemen
dc.subject.otherconsistencyen
dc.subject.otherNetzwerkvirtualisierungde
dc.subject.otherNetzwerkaktualisierungde
dc.subject.otherEinbettungsproblemde
dc.subject.otherKonsistenzde
dc.titleDynamic aspects of network virtualizationen
dc.title.subtitlealgorithmic and economic opportunitiesen
dc.title.translatedDynamische Aspekte der Netzwerkvirtualisierungde
dc.title.translatedsubtitlealgorithmische und ökonomische Möglichkeitende
dc.typeDoctoral Thesisen
dc.type.versionacceptedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 4 Elektrotechnik und Informatik::Inst. Telekommunikationssystemede
tub.affiliation.facultyFak. 4 Elektrotechnik und Informatikde
tub.affiliation.instituteInst. Telekommunikationssystemede
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
ludwig_arne.pdf
Size:
2.98 MB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
5.75 KB
Format:
Item-specific license agreed upon to submission
Description:

Collections