Grundlagen des Routing

Im Folgenden werden Grundbegriffe des Routing knapp erklärt. Wem der abstrakte Stoff ungewohnt ist, der möge Muße fürs Lesen haben. Dabei hilft auch eine Visualisierung, wie sie zB auf einer passenden Wikipedia-Seite zu finden ist. Zum Vertiefen und Konkretisieren des Themas gibt’s auch hier nebenan eine Linkliste und Matrix zu Routing-Protokollen.

Forwarding <-> Routing

Forwarding meint das Weiterleiten von Datenpaketen von einem Interface auf ein anderes. Die Entscheidung, über welches Interface ein Paket ausgesandt wird, trifft der Kernel. Und zwar auf der Basis einer FIB = forwarding information base, manchmal auch KRT = kernel routing table genannt.
Bei IP erfolgt diese Entscheidung aufgrund des längsten (genauesten) Präfix in der FIB, der auf die Zieladresse eines auszusendenden Paketes passt.

Routing hingegen meint Vorgänge, die den Inhalt einer FIB bestimmen.

  • Im einfachsten Fall werden FIB-Einträge manuell konfiguriert: statisches Routing.
  • Koordinieren mehrere Router ihre FIBs automatisch, indem sie Informationen über erreichbare Ziele austauschen, spricht man von dynamischem Routing.
  • Die Informationsbasis, die ein Routingprozess zwecks Entscheidung über FIB-Einträge benutzt, nennt man RIB = routing information base.

Entsprechung im RL: an einer Kreuzung die Wegweiser zu lesen und draufhin in die angezeigte Richtung zum gewünschten Ziel weiterzugehen ist eine Sache (~ Forwarding), aber die ganzen Wegweiser so aufzustellen, dass alle Verkehrsteilnehmer (~ Datenpakete) mit ihrer Hilfe auf dem besten Weg an ihr jeweiliges Ziel gelangen können, eine andere (~ Routing).

Es lohnt sich - theoretisch und praktisch - immer sauber zwischen Forwarding und Routing zu unterscheiden, ebenso wie zwischen Layer 2 und Layer 3. (S. dazu zB “Layer 2 <-> Layer 3” in den Switching-Grundlagen).

Route

Die Erreichbarkeitsinformation über ein Ziel, die von einem Routingprozess genutzt und ggf. an andere Router weitergegeben werden kann, heißt Route.

  • Die Route umfasst neben der Angabe des Ziels (bei IP also ein Präfix) auch Informationen zur Bestimmung des Weges dorthin.
  • Der genaue Inhalt einer Route hängt vom verwendeten Routingprotokoll ab.
  • Eine sog. default route hat als Ziel “alles, wozu keine Routinginformation bekannt ist” (IPv4: 0.0.0.0/0, IPv6: ::/0).
    Im obigen Bild von den Wegweisern an der Kreuzung entspricht ihr das Schild “toutes directions / all directions / Alle Richtungen”.

Nachbarschaft

Zwei Router, die direkt Routen austauschen (und darob ggf. Traffic an den je anderen weiterleiten), werden als Nachbarn bezeichnet.

  • Routen können von einem Nachbar wiederum an dessen Nachbarn weitergegeben werden. Alle Router, die auf diese Weise - ob direkt oder indirekt - Routen von einander erfahren können, bilden einen Routingbereich, auch Routingdomäne genannt.
  • Router und ihre Nachbarschaftsbeziehungen lassen sich als Knoten und Kanten in einem (hoffentlich zusammenhängenden) Graphen darstellen.
  • Wie Nachbarschaften zwischen Routern zustandekommen, hängt vom verwendeten Routingprotokoll ab.

Route <-> Nutztraffic

Mit Routingprotokollen werden Routen über Ziele (bei IP: Präfixe, Subnetze) von den beteiligten Routern verbreitet. Aus den ihm verfügbaren Informationen berechnet jeder Router die für ihn optimale FIB, mit der jedes erreichbare Ziel mit jeweils minimalem Aufwand erreicht werden kann. Dadurch wird Traffic mit einem Ziel Z in Richtung desjenigen Routers S (source) gelenkt, der die Route bzgl. Z ins Routingprotokoll eingespeist hat.
Merksatz: Die Route bzgl. Z verbreitet sich von der Quelle (S) aus, der Nutztraffic mit Ziel Z fließt zu dieser Quelle hin.

Achtung: Daraus, dass es ein Paket von A -> S schafft, folgt bei paketvermittelten Netzen nicht automatisch, dass ein Antwortpaket auch von S -> A durchkommt. Dies jeweils sicherzustellen (damit “Internet funktioniert”), ist eine separate Aufgabe des Routings, die - anders als in leitungsvermittelten Netzen - eben nicht mit der Bestimmung des Weges “A -> S” miterledigt ist. Und so ist es im realen Internet durchaus normal, wenn der Weg A -> S über A -> B -> C -> S verläuft, aber S -> A über S -> R -> Q -> D -> A. Das ist gewöhnungsbedürftig.

Metrik

Damit Router die bestmögliche Entscheidung bei alternativen Wegen zu Z treffen können, brauchen sie Informationen über den mit einem Weg verbundenen Aufwand, auch Distanz oder Kosten genannt. Ein linear geordneter Wertebereich zum Vergleich der Aufwände und das Verfahren zur Bestimmung der konkreten Werte in einem Netz heißen Metrik.

  • Die einfachste Variante heißt hop count, wobei jede durchlaufene Verbindung zwischen zwei Routern den Metrikwert um 1 erhöht. D.h. alle Verbindungen werden bzgl. Aufwand/Distanz/Kosten gleich behandelt. Beispiele: RIP, OLSRv1 (RFC-Version), Pfadlänge bei BGP.
  • Besser - weil genauer - ist die Methode, Metrikwerte für die Verbindungen differenziert konfigurieren zu können. Dadurch können zB Verbindungen mit größerer Bandbreite einen geringeren (besseren) Metrikwert bekommen, also für den Fluß von Traffic bevorzugt werden. Beispiel: Interfacekosten bei OSPF.
  • Bei redundanten (also nicht baumförmigen) Netzen mit stark schwankenden Verbindungsqualitäten (zB WLAN-Mesh, multi-exit-Mesh über schmale DSL-uplinks) lohnt sich der Aufwand, Metrikwerte dynamisch zu bestimmen, d.h. abhängig von den aktuellen Verbindungsqualitäten. Beispiele: alle in Freifunk-Meshes gebräuchlichen Metriken. (In der Praxis ist “dynamische Metrik” nämlich eine Voraussetzung für genießbaren Mesh-Freifunk.)

Schleife <-> Spannbaum

Hat ein Router A den Weg nach Z so bestimmt, dass dieser über B verläuft, während gleichzeitig B den Weg nach Z als über A führend bestimmt hat, so spricht man von einer Routing-Schleife für Z zwischen A und B. Diese verhindert, dass Pakete über A oder B bis nach Z gelangen können - statt dessen kreisen sie zwischen A und B.

Nach der Herstellung von Erreichbarkeit überhaupt ist die Verhinderung von Schleifen die zweitwichtigste Aufgabe eines Routingverfahrens. Schleifenfreie Teilgraphen, die alle Knoten eines Graphen umfassen, heißen Spannbaum. Ein Routingverfahren muss also sicherstellen, dass die Entscheidungen der einzelnen Router über den Weg nach Z zusammengenommen einen Spannbaum mit der Wurzel S ergeben.
Wird Z von mehreren Routern (S1, S2, …) in den Routingbereich eingespeist, so ergeben sich entsprechend mehrere, jeweils verschiedene Spannbäume (mit S1, S2, … als Wurzel).

DV <-> LS

Routingverfahren können danach unterschieden werden, mit welcher Methode sie den besten Weg zu einem Ziel bestimmen.

  • Im einfachsten Fall geht das so: S erzeugt eine Route mit Ziel Z und verbreitet sie an seine Nachbarn. Diese vergrößern den Metrikwert der Route entsprechend um den Wert ihrer direkten Verbindung zu S. In ihre FIB tragen sie S als nächsten Router auf dem Weg zu Z ein (next hop). Diese neue Metrik geben sie in einer Route für Z an ihre Nachbarn weiter. Erhält ein Router von verschiedenen Routern eine Route für Z, so wählt er diejenige mit dem kleinsten Metrikwert aus (nachdem er die Verbindung, über die er die Route erhalten hat, in den Metrikwert eingerechnet hat). Dann trägt er den Router, von dem er diese Information über Z erhalten hat, als next hop für Z in die FIB ein. Nun gibt er nur noch diese Route für Z an seine Nachbarn weiter.
    Dies nennt man Distanzvektorverfahren (DV), da sich jeder Router nur Richtung (next hop) und Länge des kürzesten Weges (Metrikwert) zu einem Ziel merken muss. Beispiele: RIP, B.A.T.M.A.N., Babel, BGP.

  • Bei dem anderen üblichen Verfahren werden die Metrikwerte aller Verbindungen innerhalb des Routingbereichs an alle Router verbreitet. Dadurch ist es jedem Router möglich, den Verbindungsgraphen des gesamten Bereichs zu rekonstruieren. Und damit kann er den kürzesten Weg zu jedem der anderen Router berechnen und für jedes bekannte Ziel den berechneten next hop zum Quellrouter des Ziels in die FIB eintragen.
    Dies nennt man Link-State-Verfahren (LS), da jeder Router alle Verbindungen und ihren Metrikwert kennen muss. Beispiele: OSPF, OLSR.

In allen Fällen ergibt sich Schleifenfreiheit dann, wenn jede Verbindung auf einem Weg den Metrikwert des Weges vergrößert und ein Router immer den kürzesten Weg zum Ziel verwendet. Bei Link-State muss zusätzlich sichergestellt werden, dass alle Router immer auf der gleichen (aktuellen) Datenbasis arbeiten, damit ihre Entscheidungen untereinander konsistent sind.

Ganz grob gesagt hat das einfachere DV Vorteile bzgl. Robustheit und Flexibilität. Das kompliziertere LS hingegen konvergiert schnell und kann mit wenig Routingtraffic auskommen: denn nur die Änderung eines Verbindungszustands muss verbreitet werden, nicht die resultierenden (Metrik-)Änderungen für alle Wege, die über diese Verbindung führen - diese Werte kann jeder Router autonom berechnen.

IGP <-> EGP <-> Internet

Innerhalb eines Routingbereichs müssen sich die Router hinsichtlich Metrik, Pfadbestimmung, Kommunikation untereinander etc. kompatibel verhalten. Dies ist üblicherweise dadurch gegeben, dass eine Organisation, die ein Netzwerk mit Routing betreibt, sich darum kümmert, dass ihre Router mit kompatibler Software (für das Routingprotokoll) und passender Konfiguration ausgestattet sind. Ein hierfür, also innerhalb eines Routingbereichs, verwendetes Protokoll heißt Interior Gateway Protokoll (IGP).

Nun gibt es viele Netzwerke und (untereinander ggf. inkompatible) Routingbereiche in dieser unserer Welt. Ein Protokoll, dass zur Verbindung mehrerer (auch inkompatibler) Routingbereiche genutzt werden kann, heißt Exterior Gateway Protokoll. Nur durch ein EGP ist es möglich, dass alle Routingbereiche (die IP-Technologie verwenden) über das Internet miteinander Datenpakete austauschen können. Dies gelingt durch die Verwendung eines Routingverfahrens, das von den einzelnen (inkompatiblen) Verfahren und Details abstrahiert, und nur die globale Erreichbarkeit von einzelnen Routingbereichen zum Gegenstand hat. (Dabei hilft die global koordinierte Vergabe von IP-Adressbereichen zwecks Eindeutigkeit und Aggregierbarkeit, s. zB Regional Internet Registry (RIR).)

Die Einheiten (zusammengehörige Netzwerke), die am globalen Routing teilnehmen, nennt man Autonome Systeme (AS). Sie tauschen sich über das globale EGP über die Erreichbarkeit der Präfixe aus, die ihren Netzwerken jeweils zugeteilt sind. Details eines AS - verwendete(s) IGP(s), innere Struktur - sind global irrelevant und werden nicht kommuniziert. Empfängt ein AS ein Datenpaket aus dem Internet für eines seiner Netzwerke, so ist es für die weitere Zustellung dieses Pakets verantwortlich (mittels IGP oder sonstwie;). (Die Gegenrichtung immer mitdenken:) Umgekehrt muss ein AS in seinem Inneren dafür sorgen, dass ein Datenpaket mit Ziel im Internet auch seinen Weg aus dem AS heraus findet. (Letzteres geschieht üblicherweise dadurch, dass die Grenzrouter zwischen diesem AS und dem Internet eine default route in das/die IGP/s des AS einspeisen.)

Das de facto EGP des Internet ist BGP (Border Gateway Protocol), dessen aktuell benutzte Version 4 im Wesentlichen bereits 1995 standardisiert wurde (RFC 1771). BGP ist ein DV-Protokoll, dessen Routen den Pfad der AS verzeichnen, die diese Route weitergegeben haben - weshalb man es auch als Pfadvektor-Protokoll klassifiert (PV). Durch diese Routinginformation werden Schleifen verhindert und DV-spezifische Probleme wie Count-to-infinity vermieden.
Selbst wenn mit aktuellen Rechenkapazitäten bzw. Hardwarespezialitäten ein globales LS-Verfahren möglich wäre, könnte es sich wohl nicht gegen BGP “durchsetzen”, weil BGP dank der DV-Flexibilität die weitgehende Nutzung von Routing-policies ermöglicht. Diese wiederum sind erforderlich, um die Infrastruktur des kommerzialisierten Internet an Geldströme (der sog. Märkte) anzupassen.

Allerdings muss ein Protokoll aus der Schublade “EGP” nicht notwendig die ganze Welt verbinden. Laut obiger Definition genügt dafür die Verbindung mehrerer, auch inkompatibler Routingbereiche - es muss nicht “die ganze Welt” mitmachen:-) Insoweit können auch Routing-Suites oder die darauf aufbauende, FF-inspirierte IGP-Kopplung in die EGP-Schublade schlüpfen.