24.10.2024, 13:00 Uhr
Universität Wien
Besprechungsraum 4.34, hybrid
Währinger Str. 29
1090 Wien
Titel: Algorithm Engineering and Empirical Evaluation for Fast Rerouting with Multiple Failures
Kurzfassung:
Aufgrund des kontinuierlich steigenden Informationsverkehrs und der zunehmenden Ab-
hängigkeit von Daten in unserer sich entwickelnden digitalen Gesellschaft, müssen moderne
Kommunikationsnetzwerke nicht nur in der Größe skalieren, sondern auch eine hohe Ver-
fügbarkeit gewährleisten und somit schnell auf unvorhergesehene Verbindungsfehler oder
Ausfälle reagieren, um den Informationsfluss aufrecht zuerhalten 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 zulangsam, 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 Routingalgorith-
men 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 En-
twicklungen bei hochmodernen Fast-Failover-Algorithmen SquareOne, Feigenbaum und
Two Resilient durch. Das besondere an diesen Algorithmen ist,dass alle Garantien für
k-simultane Verbindungsfehler bieten. Insbesondere hat SquareOne, diskutiert in Foerster
et al.[FPST19], eine Widerstandsfähigkeit gegen k − 1 Fehlerineinem k-verbundenen
Netzwerk, während Feigenbaum, präsentiert in Feigenbaumetal.[FGP+12], gegen k = 1
Verbindungsfehler und Two Resilient gegen k = 2 Verbindungsfehler in allgemeinen Net-
zwerken 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 verschieden ein der Praxisinhärente Teil-
probleme des globalen Routingschemas effizient löst, wie in Daietal. [DFS23], diskutiert.
Darüberhinaus entwerfen und implementieren wir Erweiterungen für den TwoResilient-
Algorithmus, um seine Routingleistung heuristisch zuverbessern, und diskutieren Details
sowie Herausforderungen, denen wir während dieses Prozesses begegnet sind.
Unsere Simulationen, wurden an verschiedenen sowohl synthetischen als auch realen Net-
zwerken 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 Netzwerktopo-
logien. In unserer Studie erweist sich der DAG-basierte Feigenbaum-Algorithmus als
leistungsfähigster Algorithmus in Bezug auf Routingerfolg, Stretch und Vorberechnungssef-
fizienz. TwoResilient steht in Bezug auf den Routingerfolg gleich auf mit Feigenbaum und
verzeichnet sogar einen leichten Vorteilauf Netzwerken wie unter anderem Erdős–Rényi.
Das Schlusslicht in allen unseren Tests bildet Square One.