Proseminar WS 21/22 (Nr. 040610)

Ausfallsicheres Routing (Resilient Routing)

Veranstalter: Klaus-Tycho Förster

Email: klaus-tycho.foerster@tu-dortmund.de

Sprechstunde: nach Vereinbarung per Mail

Aktuelles

• Die Anmeldung erfolgt in Kürze zentral, dazu wird eine Umfrage auf der Fakultätswebseite und via Mailingliste angekündigt. 
• Es gibt keinen separaten Präsentationskurs. Sie nehmen am Präsentationskurs der Fakultät teil und melden sich selbst dazu an.
• Nachdem Sie diesem Proseminar zugeteilt wurden, schicken Sie bitte bis Samstag 16.10.2021 (inklusive) eine Liste mit 5 Themenwünschen (gerankt von 1. bis 5. Priorität) per Mail.
• Als Subjekt nutzen Sie bitte "2021 Proseminar 040610 Themen". Schicken Sie diese Mail von Ihrer Universitätsadresse (...tu-dortmund.de)  und geben Sie Ihren Namen und Matr.Nr. an.
• Ohne eigene Themenwahl wird Ihnen ein übriggebliebenes Thema am 18.10.2021 zugeteilt.

Zeit und Ort

Erster Termin mit allgemeinen Informationen: Montag, 18.10.2021, 10:15 bis 12:00 [Online per Zoom, Link wird zugesandt]

Abgabe der schriftlichen Ausarbeitung an Tandempartner:in: 13.12.2021

Abgabe des Feedbacks zur Ausarbeitung an Tandempartner:in: 20.12.2021

Finale Abgabe der schriftlichen Ausarbeitung an den Veranstalter: 10.01.2022

Abgabe der Folien an Tandempartner:in: 17.01.2022

Abgabe des Feedbacks zu den Folien an Tandempartner:in: 24.01.2022

Abgabe der nahezu finalen Folien an den Veranstalter: 31.01.2022

Die Präsentation und Diskussion findet als Kompaktseminar im Februar 2022 statt. Der endgültige Termin wird in Absprache mit den Teilnehmerinnen und Teilnehmern festgelegt.  In Abhängigkeit von der dann aktuellen Lage wird das Proseminar entweder als online-Proseminar über ZOOM oder als Präsenzveranstaltung abgehalten.

Inhalt

Das Auftreten von Fehlern und Ausfällen ist die Norm in modernen Computernetzen. Hierbei ist das Warten auf die Behebung der Fehler bzw. auf eine komplette Neuberechnung von Routen jedoch nicht mehr zeitgemäß. Anwendungen im Bereich von Industrie 4.0, SmartGrids usw., aber auch Real-Time Streaming oder Onlinespiele, erwarten bzw. erfordern rapide Wiederherstellung der Konnektivität - idealerweise sofort.

In diesem Proseminar wollen wir einen Ein- und Überblick über die Thematik des ausfallsicheren Routings erhalten. Dabei wollen wir nicht durch Artikel und Kapitel behandeln die sich direkt mit ausfallsicherem Routing in Computernetzen beschäftigen, sondern auch verwandte Thematiken wie etwa Erforschung (Exploration), wenn das Netzwerk nach Fehlern unbekannt ist, wie schnell können wir zum Ziel gelangen, bzw. auch Generation von Routen, z.B. gibt es zwei Pfade, die sich nicht überschneiden, sodass wenn einer ausfällt, der andere noch funktioniert?

Literatur

Eine gute allgemeine Übersicht über ausfallsichere Netze gibt das folgende Buch:

• Guide to Disaster-Resilient Communication Networks (eds. Jacek Rak, David Hutchison), Springer, 2020 [Im TU-Netz frei verfügbar]

Eine weitere technischere Übersicht über die Thematik gibt der folgende Übersichtsartikel. Er kann für weitere Recherche genutzt werden.

• M. Chiesa et al.: A Survey of Fast-Recovery Mechanisms in Packet-Switched Networks. IEEE Commun. Surv. Tutorials 23(2): 1253-1301 (2021) [im TU-Netz frei verfügbar / PrePrint]

Bei den weiteren Themen bieten sich die Referenzen im Paper an, bzw. in Google Scholar zu prüfen, wer diese Paper zitiert,

Themen

Die jeweilige vorgegebene Literatur dient als Basisliteratur, die selbstständig durch die Studierenden durch weitere Literatur zum Thema ergänzt werden soll, z.B. aus den Referenzen in der jeweiligen Literatur.

1. Jedes der Buchkapitel aus "Guide to Disaster-Resilient Communication Networks" ist ein mögliches Thema.
   • Als direkte Empfehlungen bieten sich an:
     • Human and Organizational Issues for Resilient Communications. Tom Anderson, Jeremy Busby, Antonios Gouglidis, Karen Hough, David Hutchison, Mark Rouncefield. Pages 791-807.
     • Resilient SDN-Based Routing Against Rain Disruptions for Wireless Networks. Forough Yaghoubi, Marija Furdek, Ahmad Rostami, Peter Öhlén, Lena Wosinska. Pages 507-522
     • Bei den längeren anderen Kapiteln (und längeren selbst vorgeschlagenen Papern) kann die Auswahl auf einen Teil eingegrenzt werden, hierzu bitte einfach im Laufe des Semesters kurz eine Email schicken mit einem Eingrenzungsvorschlag.
2. Suurballes Algorithmus zur Berechnung von disjunkten Pfaden
   • J. W. Suurballe, Robert Endre Tarjan: A quick method for finding shortest pairs of disjoint paths. Networks 14(2): 325-336 (1984) [Im TU-Netz frei verfügbar]
3. Eine Analyse des Greedy-Algorithmus zur Erforschung von ungerichteten Graphen [Fokus auf den Aspekt zum Nearest Neighbor Algorithm]
   •  Rosenkrantz, Daniel J.; Stearns, Richard E.; Lewis, II, Philip M. (1977). "An Analysis of Several Heuristics for the Traveling Salesman Problem". SIAM Journal on Computing. 6 (3): 563–581 [Im TU-Netz frei verfügbar]
4. Analyse der Graph-Exploration in gerichteten Graphen [Fokus auf §1-§6]
   • Klaus-Tycho Foerster, Roger Wattenhofer: Lower and upper competitive bounds for online directed graph exploration. Theor. Comput. Sci. 655: 15-29 (2016) [Im TU-Netz frei verfügbar]
5. Ausfallsicheres Routing durch Hinzufügen von Zwischenzielen im Paket-Header
   • Klaus-Tycho Foerster, Mahmoud Parham, Marco Chiesa, Stefan Schmid: TI-MFA: Keep calm and reroute segments fast. IEEE Global Internet Symposium 2018: 415-420 [Im TU-Netz frei verfügbar]
6. Exploration mit Robotern: Entkommen aus einem Labyrinth und Finden eines Zielpunkts in unbekannter Umgebung [Pledge- und Bug-Algorithmen, §7.1 und §7.2]
   •  Rolf Klein: Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen. Springer, Heidelberg, 2nd edition, 2005 [Im TU-Netz frei verfügbar]
7. Ist eine sofortige Herstellung von Konnektivität in Computernetzen nach Link-Ausfällen immer möglich?
   • Joan Feigenbaum, Brighten Godfrey, Aurojit Panda, Michael Schapira, Scott Shenker, Ankit Singla: On the Resilience of Routing Tables. CoRR abs/1207.3732 (2012) [Link]
      

Weitere Themen und referenzierte Paper aus dem Übersichtsartikel von Chiesa et al. können gerne vorgeschlagen werden, bitte einfach in Ihre Auflistung von 1-5 dazutun. Gerne können Sie auch weitere Themen vorschlagen, bitte fragen Sie dann aber vorher nach oder packen für jeden freien Vorschlag bitte je noch ein Paper/Artikel dazu,

Ausarbeitung und Vortrag:

• Es ist ein 15-minütiger Vortrag zum bearbeiteten Thema zu halten. Im Anschluss an jeden Vortrag findet eine Diskussion von 10-15 Minuten statt. 
• Die Teilnahme an allen Vorträgen sowie die aktive Teilnahme an den Vorträgen von anderen Teilnehmenden ist verpflichtend.
• Den Teilnehmenden wird sowohl für die Folien als auch für die Ausarbeitung ein:e Tandempartner:in zugeordnet. Die Tandempartner:innen geben sich gegenseitig schriftliches Feedback zu Folien und Ausarbeitung jeweils im Umfang von 1-2 Seiten. Alle Teilnehmenden haben somit am Ende des Seminars 2-4 Seiten Feedback für Ihre:n Tandemparter:in geschrieben. Die Diskussion am Ende des Vortrags wird durch die Tandempartner:innen geleitet. Das Feedback und die Diskussionsleitung fließen in die Bewertung ein.
• Zudem ist eine Ausarbeitung im Umfang von 8-10 Seiten anzufertigen. Für die Ausarbeitungen soll LaTeX und die Vorlage der Universität verwendet werden. 

Weiteres

• Es gibt keinen separaten Präsentationskurs. Sie nehmen am Präsentationskurs der Fakultät teil.