Routing-Algorithmen

Routing-Algorithmen berechnen die Pfade, denen Pakete durch ein Netzwerk folgen, typischerweise durch das Finden von kostengünstigsten Routen über einen Graphen von Routern und Links, entweder unter Verwendung einer globalen Link-State-Ansicht oder einer verteilten, Nachbar-für-Nachbar-Distanzvektor-Berechnung.

Definition

Ein Routing-Algorithmus ist ein Verfahren, das die kostengünstigsten (oder anderweitig bevorzugten) Pfade durch ein als gewichteter Graph modelliertes Netzwerk bestimmt und die Weiterleitungsentscheidungen erzeugt, die Router verwenden, um Pakete zu ihren Zielen zu bewegen.

Scope

Dieses Thema behandelt die Algorithmen, die Weiterleitungstabellen füllen: das Graphenmodell eines Netzwerks mit Link-Kosten; Link-State-Routing unter Verwendung von Dijkstras Algorithmus für den kürzesten Pfad mit einer global geteilten Topologie; Distanzvektor-Routing unter Verwendung der verteilten Bellman-Ford-Berechnung mit Nachbaraustausch; deren Konvergenzverhalten und Pathologien wie das Count-to-Infinity-Problem; und hierarchisches Routing für Skalierbarkeit. Es behandelt die Algorithmen abstrakt und überlässt die konkreten Protokolle (OSPF, RIP, BGP) und ihre Intra-/Inter-Domain-Organisation dem Thema Routing-Protokolle.

Core questions

• Wie wird ein Netzwerk für das Routing als gewichteter Graph modelliert?
• Wie berechnet ein Link-State-Algorithmus die kürzesten Pfade aus einer vollständigen Topologieansicht?
• Wie konvergiert ein Distanzvektor-Algorithmus nur durch Nachbaraustausch?
• Was sind die Konvergenz- und Stabilitätsprobleme, wie z.B. Count-to-Infinity, und wie werden sie gemildert?
• Warum wird Routing hierarchisch gestaltet und wie beeinflusst das die Pfadoptimierung?

Key concepts

• gewichteter Netzwerkgraph
• kostengünstigste Pfade
• Link-State-Routing
• Dijkstras Algorithmus
• Distanzvektor-Routing
• Bellman-Ford-Gleichung
• Count-to-Infinity-Problem
• Split Horizon und Poisoned Reverse
• hierarchisches Routing

Key theories

Link-State-Routing (Dijkstra)

Jeder Router flutet seine Link-Kosten, sodass alle Router die vollständige Topologie teilen, und führt dann unabhängig voneinander Dijkstras Algorithmus aus, um die kürzesten Pfade zu berechnen; dies konvergiert schnell und vorhersehbar, erfordert aber einen globalen Informationsaustausch.

Distanzvektor-Routing (Bellman-Ford)

Router tauschen ihre aktuellen Schätzungen der geringsten Kosten zu jedem Ziel mit ihren Nachbarn aus und aktualisieren über die Bellman-Ford-Gleichung; die Berechnung ist verteilt und verwendet nur lokale Informationen, kann aber langsam konvergieren und unter Count-to-Infinity leiden.

Hierarchisches Routing

Da flaches Routing nicht auf das gesamte Internet skaliert, werden Router in Regionen (autonome Systeme) gruppiert, wobei das Routing lokal innerhalb jeder Region gehandhabt und zwischen ihnen zusammengefasst wird, wodurch ein gewisser Grad an Pfadoptimierung gegen Skalierbarkeit und administrative Autonomie eingetauscht wird.

Clinical relevance

Routing-Algorithmen bestimmen, wie effizient und zuverlässig der Datenverkehr fließt: Link-State-Algorithmen liegen internen Protokollen wie OSPF zugrunde, die nach Ausfällen schnell konvergieren, während Distanzvektor-Ideen in RIP und im Pfadvektor-Ansatz von BGP erscheinen. Das Verständnis ihres Konvergenzverhaltens ist wesentlich für die Gestaltung stabiler Netzwerke und die Diagnose von Routing-Schleifen und langsamer Wiederherstellung nach Link- oder Router-Ausfällen.

History

Die Algorithmen für den kürzesten Pfad, die das Herzstück des Routings bilden, existierten bereits vor Computernetzwerken: Bellmans und Fords Arbeiten zu Routing-Problemen in den späten 1950er Jahren und Dijkstras Algorithmus für den kürzesten Pfad von 1959. Mit dem Wachstum von Paketnetzwerken wurden diese an das Distanzvektor- und Link-State-Routing angepasst, und die hierarchische Strukturierung in autonome Systeme ermöglichte es dem Routing, auf das globale Internet zu skalieren.

Debates

Link-State- versus Distanzvektor-Routing

Link-State-Routing konvergiert schnell und vermeidet Count-to-Infinity, erfordert aber, dass jeder Router die vollständige Topologie vorhält und mehr Berechnungen durchführt, während Distanzvektor einfacher und lokaler ist, aber langsam konvergieren und transiente Schleifen bilden kann; reale Netzwerke kombinieren beide Ideen in verschiedenen Maßstäben.

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford

Seminal works

• dijkstra1959
• bellman1958
• kurose2021

Frequently asked questions

Was ist das Count-to-Infinity-Problem?

Es ist eine Distanzvektor-Pathologie, bei der Router nach einem Link-Ausfall ihre Distanzschätzungen zu einem unerreichbaren Ziel langsam erhöhen, indem sie veraltete Informationen austauschen und fälschlicherweise glauben, dass ein Pfad immer noch durch sie hindurch existiert. Abhilfemaßnahmen umfassen Split Horizon, Poisoned Reverse und die Begrenzung der maximalen Distanz.

Warum werden Link-State und Distanzvektor beide verwendet?

Sie eignen sich für unterschiedliche Anwendungsbereiche. Link-State-Protokolle wie OSPF ermöglichen eine schnelle, schleifenfreie Konvergenz innerhalb einer einzigen administrativen Domäne, wo das Teilen der vollständigen Topologie akzeptabel ist. Distanzvektor- und Pfadvektor-Ansätze skalieren besser und offenbaren weniger interne Details über Domänen hinweg, weshalb BGP ein Pfadvektor-Design zwischen Netzwerken verwendet.