Detailansicht
Algorithm engineering and empirical evaluation for fast rerouting with multiple failures
Philipp Zabka
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Informatik
Betreuer*in
Peter Reichl
DOI
10.25365/thesis.76527
URN
urn:nbn:at:at-ubw:1-20437.75803.653176-1
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Aufgrund des kontinuierlich steigenden Informationsverkehrs und der zunehmenden Abhängigkeit von Daten in unserer sich entwickelnden digitalen Gesellschaft, müssen moderne Kommunikationsnetzwerke nicht nur in der Größe skalieren, sondern auch eine hohe Verfügbarkeit gewährleisten und somit schnell auf unvorhergesehene Verbindungsfehler oder Ausfälle reagieren, um den Informationsfluss aufrechtzuerhalten und die Netzwerkresilienz zu sichern. Dies steht im Gegensatz zu vielen gegenwärtigen Netzwerken, die nur Routingprotokolle wie OSPF oder IS-IS verwenden. Diese Algorithmen sind für moderne Anforderungen im Falle von Verbindungsfehlern viel zu langsam, da die Neuberechnung von Routingtabellen global erfolgt. Um die langsame Reaktionszeit solcher traditionellen Protokolle zu mildern, verfügen die meisten modernen Router zusätzlich über schnelle Failover Routingalgorithmen für eine schnellere Reaktionzeits. Failover-Algorithmen bieten eine lokale Umleitung zu vorinstallierten alternativen Pfaden und daher auch eine schnellere Neuberechnung von Routingtabellen. In dieser Arbeit führen wir eine umfangreiche empirische Studie über die neuesten Entwicklungen bei hochmodernen Fast-Failover-Algorithmen SquareOne, Feigenbaum und TwoResilient durch. Das besondere an diesen Algorithmen ist, dass alle Garantien für k-simultane Verbindungsfehler bieten. Insbesondere hat SquareOne eine Widerstandsfähigkeit gegen k-1 Fehler in einem k-verbundenen Netzwerk, während Feigenbaum gegen k=1 Verbindungsfehler und TwoResilient gegen k=2 Verbindungsfehler in allgemeinen Netzwerken absichert. Für den TwoResilient-Algorithmus lag bisher nur eine abstrakte mathematische Beschreibung vor, deswegen analysieren wir die algorithmischen Details und entwickeln eine neue Implementierung, die verschiedene in der Praxis inhärente Teilprobleme des globalen Routingschemas effizient löst. Darüber hinaus entwerfen und implementieren wir Erweiterungen für den TwoResilient-Algorithmus, um seine Routingleistung heuristisch zu verbessern, und diskutieren Details sowie Herausforderungen, denen wir während dieses Prozesses begegnet sind. Unsere Simulationen, wurden an verschiedenen sowohl synthetischen als auch realen Netzwerken mit den Kantensusfallmodellen RANDOM und CLUSTER durchgeführt. Unsere Ergebnisse zeigen die Stärken und Schwächen dieser Routingalgorithmen auf und liefern interessante Einblicke zur Steigerung ihrer Wirksamkeit auf spezifischen Netzwerktopologien. In unserer Studie erweist sich der DAG-basierte Feigenbaum-Algorithmus als leistungsfähigster Algorithmus in Bezug auf Routingerfolg, Stretch und Vorberechnungsseffizienz. TwoResilient steht in Bezug auf den Routingerfolg gleichauf mit Feigenbaum und verzeichnet sogar einen leichten Vorteil auf Netzwerken wie unter anderem Erdős-Rényi. Das Schlusslicht in allen unseren Tests bildet SquareOne.
Abstract
(Englisch)
Due to the continuously increasing traffic and reliance on data in our evolving digital society, modern communication networks not only need to scale in size, but also need to ensure a high routing availability and respond swiftly to unforeseen link failures, to circumvent information flow and maintain network resilience. This stands in contrast to many contemporary networks which only feature routing protocols such as OSPF or IS-IS. These algorithms are far too slow for modern demands in the case link failures occur as recomputation of routing tables happens at a global scale. To mitigate the slow response time of such traditional protocols, most modern routing devices additionally feature fast failover routing algorithms for a swifter response. Fast failover algorithms offer local rerouting to preinstalled alternatives paths, making recomputation much quicker. In this work, we conduct an extensive empirical study of the most recent advances in state-of-the-art fast failover algorithms, namely SquareOne, Feigenbaum and TwoResilient, which all provide guarantees for k simultaneous link failures. In particular, SquareOne provides a resilience against k-1 failures in a k-connected network. Feigenbaum, promises a resilience against $k=1$ link failures and TwoResilient against k=2 link failures in general networks. For the latter algorithm, TwoResilient, so far, only an abstract mathematical description was available. We analyze the algorithmic details and design a new implementation that efficiently solves various subproblems in practice inherent to the global routing scheme. Moreover, we design and implement extensions to the TwoResilient algorithm to heuristically increase its routing performance and discuss details as well as challenges we have faced during this process. Our simulations, conducted on various synthetic and real world networks with two link failure models RANDOM and CLUSTER, reveal the strengths and weaknesses of these algorithms, which provide multiple interesting insights to increase their effectiveness on specific network topologies. In our evaluation, the DAG based Feigenbaum algorithm proves to achieve the best performance in routing success, stretch and precomputation efficiency. In terms of routing success TwoResilient is on par with Feigenbaum and on some network topologies such as Erdős–Rényi even shows a slight advantage in performance. The SquareOne algorithm shows the least effective metrics in all our tests.
Schlagwörter
Schlagwörter
(Deutsch)
Fast-Failover Routing Netzwerkresilienz Fehlertoleranz Routingalgorithmen Routingschemen
Schlagwörter
(Englisch)
Fast-Failover Routing Schemes Network Resilience Fault Tolerance Data Plane Routing Algorithms
Autor*innen
Philipp Zabka
Haupttitel (Englisch)
Algorithm engineering and empirical evaluation for fast rerouting with multiple failures
Publikationsjahr
2024
Umfangsangabe
xxi, 73 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Peter Reichl
Klassifikation
54 Informatik > 54.32 Rechnerkommunikation
AC Nummer
AC17287743
Utheses ID
71469
Studienkennzahl
UA | 066 | 921 | |