Detailansicht
Algorithms for traffic control challenges in softwarized networks
Mahmoud Parham
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Dr.-Studium der technischen Wissenschaften (DissG: Informatik)
Betreuer*in
Stefan Schmid
DOI
10.25365/thesis.72056
URN
urn:nbn:at:at-ubw:1-10847.37971.848880-3
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Rechenzentren stehen vor wachsenden Herausforderungen hinsichtlich Skalierbarkeit und Betrieb aufgrund der rasanten Zunahme bandbreitenintensiver Anwendungen wie Remote-Zusammenarbeit und Video-Streaming-Dienste. Skalierbare Netzwerke müssen auf unvorhergesehene Ereignisse (z. B. Ausfälle) sofort reagieren und sich an Verkehrsmuster oder Richtlinienänderungen mit minimalem menschlichem Eingriff anpassen. Diese Eigenschaften lassen sich mit virtualisierten und softwaredefinierten Netzwerken erreichen. Ein virtueller Netzwerkfunktionsknoten (VNF) ist eine Netzwerkressource wie eine Firewall und ein Load Balancer, die in Software emuliert werden und logisch von der zugrunde liegenden Hardware entkoppelt sind. Auf einer anderen Ebene entkoppelt das softwaredefinierte Netzwerk (SDN) die Routing-Berechnungen von dem zugrunde liegenden Paketweiterleitungsmechanismus. Der SDN-Controller hat einen globalen Überblick über des Netzes, führt Berechnungsaufgaben aus und installiert die Routen aus der Ferne. Die Motivation für diese Arbeit liegt in erster Linie in der Flexibilität und den Möglichkeiten von virtualisierten und softwaredefinierten Netzwerken. Wir nutzen sie zur Verkehrsfluss zu beeinflussen, ohne die zugrundeliegende Netzwerkstruktur zu verändern; wir bezeichnen dieses Paradigma als Verkehrskontrolle. Diese Arbeit konzentriert sich auf mehrere Herausforderungen der Verkehrskontrolle: Verkehrstechnik. Um eine ausgewogene Bandbreitennutzung und eine geringe Überlastung zu erreichen, stellen wir einen neuen Optimierungsansatz vor, der zwei bestehende Verkehrstechniken kombiniert. Wir beweisen seine Vorzüge und liefern Algorithmen mit polynomialer Zeit. \item Schnelles Verkehrs-Rerouting. Sobald der Verkehr auf eine fehlerhafte Verbindung stößt, leitet der benachbarte Routerknoten den Verkehr über eine vorinstallierte Backup-Route um, im Idealfall unabhängig von nicht fehlerhaften Verbindungen (lokal und ``schnell''). Wir formulieren das Ausfallsicherheitsmodell, stellen Backup-Routenschemata vor und beweisen ihre Ausfallsicherheit für spezielle Netzwerke. Verkehrspartitionierung. Die Kommunikation zwischen virtualisierten Knoten kann eine erhebliche Verschwendung der Bandbreite zwischen Servern darstellen. Eine geeignete Partitionierung dieser Knoten kann den Datenverkehr zwischen den Servern reduzieren. Die Annäherung an die optimale Partitionierung ist eine rechnerische Herausforderung, da das zugrunde liegende Kommunikationsmuster nicht a priori bekannt ist. Wir stellen Online-Algorithmen vor, die proaktiv den kostspieligen Inter-Server-Verkehr in (kostengünstigen) lokalen Verkehr umwandeln, der auf der jüngsten Kommunikationshistorie basiert. Verkehrsteuerung durch Wegpunkte. Service Verkettung ist eine Technik zur Zusammenstellung benutzerdefinierter Netzwerkdienste unter Verwendung primitiver Funktionen. Ein Sicherheitsdienst kann beispielsweise aus mehreren Knoten bestehen: einer Firewall, einem DPI und einem Virenscanner. Die Berechnung kürzester Routen, die durch eine gegebene Menge von Knoten führen, ist ein NP-schweres Problem. Wir stellen Härtegrade und Algorithmen für einige spezielle Netzwerke vor, die das Problem überschaubar machen.
Abstract
(Englisch)
Data centers face growing scalability and operational challenges due to the rapid expansion of bandwidth-intensive applications such as remote collaboration and video streaming services. Scalable networks must react to unanticipated events (e.g., failures) promptly and adapt to traffic pattern or policy changes with minimal human intervention. Such qualities are achievable via virtualized and software-defined networking. A virtualized node (VN) is a network resource such as a firewall and load balancer that is emulated in software and logically decoupled from the underlying hardware. On the other hand, the software-defined networking~(SDN) decouples routing computations from the underlying packet forwarding mechanism. SDN's controller has a global view of the network, executes computational tasks, and installs routes remotely. This thesis is primarily motivated by the flexibility and potentials of virtualized and software-defined networks. We leverage them to influence traffic flow without altering the underlying network structure; we refer to this paradigm as traffic control. This thesis focuses on several traffic control challenges: Traffic Engineering. To achieve a balanced bandwidth utilization and low congestion, we introduce a new optimization approach that combines two existing traffic engineering techniques. We prove its merits and provide polynomial-time algorithms. Fast Traffic Rerouting. Once the traffic encounters a faulty link, the adjacent router node reroutes the traffic along a pre-installed backup route, ideally oblivious to non-incident faulty links (locally and "fast"). We formulate the resiliency model, present backup route schemes, and prove their resiliency for special networks. Traffic Partitioning. Communication between VNs can be significantly wasteful of the inter-server bandwidth. An appropriate partitioning of these nodes can potentially reduce the inter-server traffic. Approximating the optimal partitioning is computationally challenging as the underlying communication pattern is not known a~priori. We present online algorithms that proactively transform costly inter-server traffic into (inexpensive) local traffic based on the recent communication history. Traffic Waypoint Routing. Service chaining is a technique for composing custom network services using primitive functions. For instance, a security service may be composed of several functions: a firewall, DPI, and virus scanner. Computing shortest routes passing through a given set of nodes is an NP-hard problem. We present hardness bounds and algorithms for a few special networks that render the problem tractable.
Schlagwörter
Schlagwörter
(Deutsch)
Netzwerkalgorithmen Routing Optimierung
Schlagwörter
(Englisch)
network algorithms routing optimization
Autor*innen
Mahmoud Parham
Haupttitel (Englisch)
Algorithms for traffic control challenges in softwarized networks
Publikationsjahr
2022
Umfangsangabe
xi, 121 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*innen
Dan Raz ,
Bernard Fortz
Klassifikation
54 Informatik > 54.99 Informatik: Sonstiges
AC Nummer
AC16598492
Utheses ID
62431
Studienkennzahl
UA | 786 | 880 | |