Routing

Routing [ˈruːtɪŋ] (BE) / [ˈruːtɪŋ], aber auch [ˈraʊtɪŋ] (AE) (engl. „Vermittlung“, „Leitweglenkung“, „Streckenführung“, „Verkehrsführung“ sowie „leiten“, „senden“, „steuern“) bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme bei der Nachrichtenübermittlung in Rechnernetzen. Insbesondere in paketvermittelten Datennetzen ist hierbei zwischen den beiden verschiedenen Prozessen Routing und Forwarding zu unterscheiden: Das Routing bestimmt den gesamten Weg eines Nachrichtenstroms durch das Netzwerk; das Forwarding beschreibt hingegen den Entscheidungsprozess eines einzelnen Netzknotens, über welchen seiner Nachbarn er eine vorliegende Nachricht weiterleiten soll.

Häufig werden jedoch Routing und Forwarding unter dem Begriff „Routing“ miteinander vermengt; in diesem Fall bezeichnet Routing ganz allgemein die Übermittlung von Nachrichten über Nachrichtennetze. Im Unterschied zu Verteilern (Hubs und Switches) arbeitet das Routing ohne Einschränkungen auch in vermaschten Netzen.

Die Vermittlungstechnik bezeichnet mit dem Begriff Verkehrslenkung (engl.: routing) die Auswahl der Wegeabschnitte beim Aufbau von Nachrichtenverbindungen, die unter Berücksichtigung von Kriterien, wie bspw. der kürzesten Entfernung, erfolgen kann. Handelt es sich um eine leitungsvermittelte Verbindung, wird ein Übertragungskanal für die gesamte Zeit der Verbindung ausgewählt, und alle Nachrichten werden über denselben Weg geleitet. Handelt es sich dagegen um eine paketvermittelte Datenübertragung, wird der Weg für jedes Paket von jedem Netzknoten neu bestimmt.

Prinzipiell werden drei Herangehensweisen unterschieden:

• statisches Routing
• alternatives Routing
• adaptives Routing

Routing von Paketen

Beim paketvermittelten Routing, wie es z. B. im Internet stattfindet, wird dafür gesorgt, dass logisch adressierte Datenpakete aus dem Ursprungsnetz herauskommen und in Richtung ihres Zielnetzes weitergeleitet werden. Routing ist die Basis des Internets – ohne Routing würde das Internet nicht existieren, und alle Netze wären autonom. Die Datenpakete können dabei viele verschiedene Zwischennetze auf dem Weg zu ihrem Ziel passieren. Im Internet wird das Routing (üblicherweise) auf der IP-Schicht durchgeführt. Im ISO/OSI-Modell ist Routing eine der wesentlichen Aufgaben der dritten Schicht.

Hubs und Switches leiten Daten nur im lokalen Netz weiter, wohingegen der Router auch benachbarte Netze kennt. Dieser Artikel beschreibt Routing auf eine hardwareunabhängige Art. Für Informationen über Router selbst siehe den Router-Artikel.

Um zu wissen, wohin Pakete gesendet werden sollen, muss man die Struktur des Netzes kennen. In kleinen Netzen kann das Routing sehr einfach sein und wird oft per Hand konfiguriert. Man spricht dann auch von statischem Routing. Große Netze können eine komplexe Topologie haben, die sich möglicherweise häufig ändert, was unter anderem das Routing zu einer komplexen Angelegenheit macht. Hier wird in der Regel ein dynamisches Routing angewandt.

Da Router die besten Routen im Verhältnis zur Anzahl der zu bewegenden Pakete nur sehr langsam bestimmen können, merken sie sich in einer oder mehreren Routingtabellen die bestmöglichen, teilweise auch weitere Routen zu bestimmten Netzen und die dazugehörigen Routing-Metriken. Der bestmögliche Weg ist oftmals der kürzeste Weg; er kann zum Beispiel mit dem Algorithmus von Dijkstra gefunden werden.

Basierend auf den Einträgen in der oder den Routingtabelle(n) berechnet ein Router eine sogenannte Forwardingtabelle; sie enthält Einträge der Form Zieladressmuster→Ausgabeschnittstelle. In seiner Forwardingtabelle schlägt ein Router dann für jedes neu eingetroffene Paket nach, über welche Schnittstelle er das Paket weiterleiten muss.

Source Routing

In lokalen Netzen wird häufig Source Routing verwendet. In diesem Fall ist der sendenden Station der vollständige Pfad zur Zielstation bekannt. Die sendende Station trägt die Adresse des nächsten Netzknotens in den Kopf der Nachricht ein. Jeder folgende Netzknoten adressiert den nächsten Knoten entlang der bereits festgelegten Route, direkt im Kopf der Nachricht. Dieses Verfahren wird z. B. im Usenet Mail Service verwendet.

Ein beliebtes Beispiel ist das Dynamic Source Routing; hierbei erfährt die sendende Station durch die Route Discovery eine gültige Route zur Zielstation. Diese Route wird in den Header eines jeden Paketes zur Zielstation eingetragen und jeder Zwischenknoten ist verpflichtet, das Paket entlang dieser Route weiterzuleiten. Die korrekte Weiterleitung kann in bidirektionalen drahtlosen Netzen auch durch den vorigen Hop-Knoten kontrolliert werden (mithören).

Routing-Protokolle

Routing-Protokolle sorgen für den Austausch von Routing-Informationen zwischen den Netzen und erlauben es den Routern, ihre Routing-Tabellen dynamisch aufzubauen. Traditionelles IP-Routing bleibt einfach, da Next-Hop-Routing benutzt wird: Der Router sendet das Paket an denjenigen Nachbar-Router, von dem er glaubt, dass er am günstigsten zum Zielnetz liegt. Um den weiteren Weg des Pakets braucht sich der Router nicht zu kümmern. Selbst wenn er falsch lag und das Paket nicht an den „optimalen“ Nachbarn gesendet hat, sollte das Paket trotzdem früher oder später am Ziel ankommen.

Obwohl dynamisches Routing sehr komplex werden kann, macht es das Internet sehr flexibel und erlaubte das exponentielle Wachstum des Internets seit der Einführung von IP im Jahre 1983. Wenn Teile der Backbones ausfallen (so geschehen z. B. im Sommer 2002, als der Carrier KPNQwest sein europaweites Glasfasernetz wegen Insolvenz abschalten musste), können innerhalb von Sekunden Alternativrouten propagiert werden und die betroffenen Netzbereiche weiträumig umgangen werden.

Dem Ausfall des sogenannten Standardgateways – das ist meist der erste Router vom Sender aus gesehen – wirkt dynamisches Routing jedoch nicht entgegen. Da ein Host im Normalfall keine Alternative zum Standardgateway hat, ist dies der wichtigste Router der Route. Zur Lösung dieses Problems wurden HSRP, VRRP und CARP entwickelt.

Routing-Algorithmen

Routing-Algorithmen benutzen zwei grundlegende Verfahrensweisen:

• Teile der Welt mit, wer deine Nachbarn sind: Link-State-Routing-Protokolle (z. B. OSPF) sorgen dafür, dass nach einiger Zeit jeder Router die vollständige Topologie des Netzwerks kennt und sich die kürzesten Wege darin selbst ausrechnen kann.
• Teile deinen Nachbarn mit, wie für dich die Welt aussieht: Distanzvektor-Protokolle (wie z. B. das Routing Information Protocol (RIP)) sorgen dafür, dass sich die Router untereinander nur mitteilen, wie „gut“ sie an verschiedene Zielknoten angebunden sind. Durch Auswahl des für ein bestimmtes Ziel optimalen Nachbarn wird die Lösung des Kürzeste-Wege-Problems somit auf mehrere Router verteilt.
  • Eine etwas verallgemeinerte Form der Distanzvektorprotokolle mit einer verbesserten Form der Schleifenerkennung sind die Pfadvektorprotokolle (wie z. B. das Border Gateway Protocol (BGP)).

Weiterhin können Routing-Algorithmen im Wesentlichen nach ihrer Zentralisation und ihrer Dynamik beurteilt werden:

• Zentralisation: Wo ist der Algorithmus lokalisiert? Zentral in einem Netzkontrollzentrum oder dezentral verteilt auf die Vermittlungsknoten?
• Dynamik: Ist das Verfahren nicht adaptiv, d. h. die Routingtabelle in dem Vermittlungsknoten bleibt über längere Zeit konstant, verglichen mit der Verkehrsänderung. Oder ist das Verfahren adaptiv, d. h. die Routingentscheidungen hängen vom Zustand des Netzes ab. (Topologie, Lastverhältnisse)

Aus diesen Punkten ergibt sich ein Zielkonflikt, da zwar zentrale, nicht adaptive Verfahren das Netz selber weniger mit Routingnachrichten belasten, aber möglicherweise veraltete und/oder unvollständige Informationen über den Zustand des Netzes benutzen. Je adaptiver und verteilter die Routingverfahren sind, desto besser sind die Informationen über das Netz verteilt. Aber desto mehr wird dieses auch durch den Austausch von Nachrichten zum Routen belastet. Hier gibt es nun eine Vielzahl von Algorithmen, die einen unterschiedlichen Grad von Zentralisation und Dynamik aufweisen:

• Statisches Routing
• Zentralisiertes Routing
• Delta Routing
• Broadcast Routing
• Hot Potato
• Backward Learning, verteiltes adaptives Routing (RIP, OSPF, IS-IS, …)

Die Verfahren im Einzelnen

Statisches Routing

Dieses Verfahren ist nicht adaptiv, sehr einfach und kommt daher häufig zum Einsatz. Jeder Knoten unterhält eine Tabelle mit einer Zeile für jeden möglichen Zielknoten. Eine Zeile enthält Einträge, welche die beste, zweitbeste usw. Übertragungsleitung für dieses Ziel ist, zusammen mit einer Gewichtung. Vor der Weiterleitung eines Paketes wird der entsprechende Eintrag aus der Tabelle gewählt und auf eine der möglichen Leitungen gegeben. Die Gewichtung spiegelt hier die Wahrscheinlichkeit wider, dass diese Leitung gewählt wird.

Zentralisiertes Routing

Zentralisiertes Routing stellt ein adaptives Verfahren dar. Es existiert im Netz ein Routing Control Center (RCC), an welches jeder Knoten periodisch Zustandsinformationen sendet. (z. B.: Liste aller aktiven Nachbarn, aktuelle Warteschlangenlänge, Umfang an Verkehr seit letzter Meldung, …) Das RCC sammelt die Zustandsinformationen und berechnet aufgrund dieser Kenntnis über das gesamte Netz die optimale Weglänge zwischen allen Knoten. Danach übermittelt das RCC jedem Knoten eine Routingtabelle, anhand welcher der Knoten seine Routing-Entscheidungen trifft.

Vorteil:

• RCC hat theoretisch die vollständige Übersicht und kann somit „perfekte“ Entscheidungen treffen
• Knoten müssen keine aufwändigen Berechnungen durchführen

Nachteil:

• Berechnung dauert für große Netze u. U. sehr lange
• Ausfall des RCC lähmt das ganze Netz (soweit kein Backup-Rechner vorhanden ist)
• globale Inkonsistenzen sind möglich, da Knoten, die nahe am RCC liegen, mitunter wesentlich früher die neuen Routingtabellen erhalten, als die weiter entfernten Knoten
• starke Belastung des RCC durch die globale Funktion

Isoliertes Routing

Bei dieser Art der Routingverfahren entscheidet jeder Knoten nur aufgrund der Informationen, die er selber sammelt. Es findet kein Austausch von Routing-Informationen statt. Die Anpassung an Änderungen des Verkehrs oder der Topologie des Netzes (z. B. durch Ausfall von Knoten) kann hier also nur mit beschränkten Informationen erfolgen. Zu den isolierten Routing-Verfahren zählen:

• Broadcast Routing
• Hot Potato
• Backward Learning
• Delta Routing

Broadcast Routing

Beim „Broadcast Routing“ wird ein Paket an alle Knoten gesendet. Hierbei unterscheiden sich zwei Varianten: Einmal, dass für jeden Knoten ein gesondertes Paket erstellt wird, und zum anderen das Fluten. Das Fluten ist hierbei das einfachste Verfahren und ist nicht adaptiv. Jedes eingehende Paket wird auf jeder Übertragungsleitung weitergegeben, außer auf derjenigen, auf welcher es eintraf. Hierbei können auch Maßnahmen zur Eindämmung der Flut getroffen werden, wie:

• Erkennung von Duplikaten von Paketen, durch Nummerierung der Pakete
• Kontrolle der Lebensdauer von Paketen durch Zählen der zurückgelegten Teilstrecke (Hops)
• Selektives Fluten (Weiterleitung nicht auf allen, sondern nur auf einigen Leitungen)
• Random Walk (zufällige Auswahl einer Leitung)

Hot Potato

Jeder Knoten versucht, eingehende Pakete so schnell wie möglich weiterzuleiten (sie behandeln das Paket wie eine heiße Kartoffel, daher der Name). Im Unterschied hierzu stehen Cold Potato-Verfahren, hier wartet der Router so lange wie nötig, bis ein Paket weitergeleitet werden kann, z. B. bis ein bevorzugter Ausgang frei ist.

Arbeitsweise: Theoretisch arbeitet das Hot Potato-Verfahren auch dann zielführend wenn keine Routinginformationen über bevorzugte Pfade usw. vorliegen (siehe Paul Baran). Da nach diesem Verfahren weitergeleitete Pakete ihren Bestimmungsknoten' möglicherweise erst spät und nach ausgiebigen Umwegen erreichen, wird in der Praxis meist eine Kombination aus dem Hot Potato Verfahren und dem statischen Routing eingesetzt. Generell gibt es dann für jedes Paket einen bevorzugten Ausgang (auch mehrere), der sich aus den statischen Einstellungen des Routers ergibt (beste Metrik, minimale Hops oder Ähnliches). Falls dieser Ausgang gerade frei ist, wird er auch durch das Hot Potato Verfahren gewählt. Wenn aber mehrere Pakete anstehen, welche den Router durch den gleichen Ausgang verlassen wollen, wird dann aber nur das erste Paket durch den gewünschten Ausgang geleitet, alle anderen Pakete werden an einen anderen, suboptimalen, gerade freien Ausgang weitergeleitet und das auch dann, wenn die anderen gerade freien Ausgänge keine bevorzugten Ausgänge darstellen (Metrik nicht minimal, Hops nicht minimal). Als alternativer Ausgang wird aber immer eine Übertragungsleitung mit einer freien Warteschlange (bzw. eine der kürzesten Warteschlangen) gewählt.

Vorteile:

• Schnelle Entscheidungsfindung
• Geringer Rechenaufwand
• Hot Potato Verfahren sorgen für eine optimale Leitungsauslastung

Nachteile:

• Mit steigender Last wird das Routing weniger optimal
• Pakete können im Kreis laufen, also einen Router mehrfach passieren

Es gibt auch Kombinationen dieses Verfahrens mit denen des statischen „Cold Potato“ Routing:

• Auswahl der besten Übertragungsleitung nach statischem Verfahren, solange deren Warteschlangenlänge unter einer bestimmten Schwelle bleibt.
• Auswahl der Übertragungsleitung mit der kürzesten Warteschlange, falls deren Gewicht zu niedrig ist (siehe stat. Routing weiter oben).

Backward Learning

Bei diesem Verfahren müssen folgende Informationen im Paket gespeichert werden:

• Identifikation des Quellknotens
• Zähler, der mit jeder zurückgelegten Teilstrecke (Hop) um eins erhöht wird

Wenn ein Knoten nun ein Paket erhält, kann er die Hopanzahl erkennen und weiß, über welchen Eingang er es erhalten hat. Damit kann jeder Knoten aus den erhaltenen Paketen schließen, über welchen Weg er die anderen Knoten mit der minimalen Anzahl an Hops erreichen kann. Ein Eintrag in der Routingtabelle wird ersetzt, wenn ein Paket mit einer niedrigeren Hopanzahl den Knoten erreicht, als in der Tabelle eingetragen ist. Die Einträge werden aber auch dann aktualisiert, wenn eine gewisse Zeit lang kein Paket mehr mit einer bestimmten Hopanzahl von dem jeweiligen Knoten erhalten wurde. Es werden also in festen Zeitabständen Lernperioden zugelassen, in denen bessere Einträge mit schlechteren überschrieben werden, wenn diese eine gewisse Zeit alt sind. (Dann muss man davon ausgehen, dass die bessere Verbindung nicht mehr existiert, und die nächstbeste wählen) Daraus ergeben sich folgende Probleme:

• während der Lernperiode ist das Routing nicht optimal
• bei kurzen Lernperioden (Einträge werden schneller zum schlechteren aktualisiert) nehmen viele Pakete Wege unbekannter Qualität
• bei langen Lernperioden ergibt sich ein schlechtes Anpassungsverhalten an die Situation im Netz

Delta Routing

Dieses Verfahren stellt eine Kombination zwischen zentralisiertem und isoliertem Routing dar. Hierbei misst jeder Knoten periodisch die Kosten jeder Übertragungsleitung (z. B.: eine Funktion der Verzögerung, Auslastung, Kapazität, …) und sendet diese an das RCC. Das RCC berechnet nun die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} besten Wege von Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} zu Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} (für alle Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} , $j$), wobei nur Wege berücksichtigt werden die sich in ihrer initialen Leitung unterscheiden. Das RCC sendet an jeden Knoten die Liste aller äquivalenten Wege für alle Bestimmungsorte. Zum aktuellen Routing kann ein Knoten einen äquivalenten Weg zufällig wählen, oder aufgrund aktuell gemessener Kosten entscheiden. Das namensgebende Delta stammt hier aus der Funktion mit der ermittelt wird, ob zwei Wege als äquivalent anzusehen sind.

Verteiltes adaptives Routing

Bei diesem Verfahren tauscht jeder Knoten periodisch Routing-Informationen mit jedem seiner Nachbarn aus. Auch hier unterhält jeder Knoten eine Routing-Tabelle, die für jeden anderen Knoten im Netz einen Eintrag enthält. In dieser Tabelle können der bevorzugte Übertragungsleitung für diesen Knoten sowie eine Schätzung zu Zeit oder Entfernung zu diesem Knoten enthalten sein:

• Anzahl Knoten ("Hops") bis zum Ziel
• geschätzte Verzögerung in Millisekunden
• geschätzte Gesamt-Anzahl von Paketen, die entlang des Weges warten

Diese Schätzungen werden gewonnen aus der Zeit/Entfernung zu den Nachbarn (z. B.: mittels speziellen Echo-Paketen mit Zeitstempel) und/oder Schätzungen der Nachbarn. Ein Austausch der Routing-Informationen kann entweder synchron in bestimmten Aktualisierungsintervallen oder asynchron bei signifikanten Änderungen erfolgen. Zu diesem Verfahren gehören unter anderem das

• Distance Vector Routing
• Link State Routing

Distance Vector Routing

→ Hauptartikel: Distanzvektoralgorithmus und Distance Vector Routing

Distance-Vector-Protokolle bestimmen die Erreichbarkeit durch einen Vektor aus Entfernung und Richtung. Die Metrik wird in der Anzahl zu passierender Knoten ausgedrückt. Für die Wegbestimmung wird üblicherweise der Bellman-Ford-Algorithmus verwendet.

Sobald Änderungen der Netzwerktopologie bekannt werden, spiegeln sich diese in Update-Nachrichten wider. Entdeckt ein Router eine unterbrochene Verbindung oder den Ausfall seines Nachbarn, berechnet er die betroffenen Wege neu und verschickt Änderungsmeldungen an alle erreichbaren Knoten. Jeder Router, der eine derartige Meldung erhält, passt seine Routingtabelle an und propagiert diese Änderung.

In der Praxis hat dieses Verfahren eine zu langsame Konvergenz zu einem konsistenten Zustand für viele Router, aufgrund der „Count-To-Infinity“-Problematik.

Zu dieser Klasse zählt beispielsweise RIP.

Link State Routing

→ Hauptartikel: Link-State

Link-State-Protokolle gelten als Alternative zu Distance-Vector-Ansätzen und versuchen demzufolge einige ihrer Schwächen auszugleichen. Im Gegensatz zu Distance-Vector-Protokollen, die nur eine eingeschränkte Sicht auf die Netztopologie haben, haben die Router bei Link-State-Protokollen einen vollständigen Überblick über den Aufbau des Netzes. Der Überblick (Topologie-Datenbank) setzt sich aus Link-State-Informationen zusammen und ist mit einem Stadtplan vergleichbar, der auf jedem Router innerhalb einer Area identisch ist.

• Netze können in Bereiche (so genannte Areas) aufgeteilt werden. Damit lässt sich die Größe der Topologie-Datenbank verringern und Änderungen in der Area wirken sich nicht zwangsläufig auf andere Areas aus.
• Alle Router innerhalb einer Area verfügen über die gleiche Datenbasis. Diese Datenbasis beschreibt die vollständige Topologie der Area (Topologie-Datenbank).
• Jeder Router benutzt diese Datenbasis, um den optimalen Pfad für ein Ziel (IP-Netz oder Host) abzuleiten und diesen in seine Routingtabelle zu stellen. Die Bestimmung des Weges beruht auf dem Shortest-Path-First-Algorithmus von Dijkstra.
• Hellopakete stellen den Kontakt zu den Nachbarroutern her. Unter Ausnutzung des Multicast-Mechanismus werden alle Nachbarrouter angesprochen.

Zur Aktualisierung der Datenbasis verwendet das Link-State-Protokoll keine periodischen Updates, sondern sendet nur bei einem Topologiewechsel ein Link-State-Update. Dieser Bedarf entsteht, wenn:

• ein neuer Router entdeckt wird
• ein Router seinen Dienst einstellt
• die Kosten einer Verbindung sich ändern
• periodisch alle 30 Minuten.

Zu dieser Klasse gehören OSPF und IS-IS.

Hierarchisches Routing

Die Grundlage des Hierarchischen Routings ist die Aufteilung großer Netze in Regionen. Die Knoten einer Region haben nur Routing-Informationen über ihre eigene Region. In jeder Region existiert ein oder mehrere ausgezeichnete Knoten, welche als Schnittstelle zu anderen Regionen dient. In sehr großen Netzen sind weitere Hierarchien aufgrund zunehmender Größe der Netze möglich (Regionen, Cluster, Zonen, Gruppen, …).

Metrik

Eine Routing-Metrik ist ein numerischer Wert, mit dessen Hilfe ein Routing-Algorithmus feststellen kann, ob eine Route im Vergleich zu einer anderen besser ist. Metriken können Informationen wie z. B. Bandbreite, Verzögerung, Hop Count, Pfadkosten, Last, MTU, Verlässlichkeit und Kommunikationskosten berücksichtigen. Falls z. B. die Distanz die ausschlaggebende Metrik bei der Bestimmung einer Route ist, wird im Falle mehrerer möglicher Routen diejenige mit dem kleinsten Wert (d. h. der niedrigsten Distanz) gewählt. Nicht immer lässt sich aber die beste Route anhand des kleinsten Werts bestimmen, da z. B. eine höhere Bandbreite durch einen höheren Metrik-Wert repräsentiert wird. In der Routing-Tabelle werden oft nur die bestmöglichen Routen gehalten, während Link-State- oder topologische Datenbanken, aus denen die Routing-Tabelle gewonnen wird, sämtliche Informationen beinhalten. Welche Metrik verwendet wird, hängt vom Routing-Protokoll ab. So verwendet RIP beispielsweise nur den Hop-Count als Unterscheidungskriterium für die Wahl des besten Weges zu einem Zielnetz und lässt damit beispielsweise die Bandbreite unberücksichtigt.

Routing im Internet

Prinzipiell unterscheidet man im Internet je nach Zweck zwei verschiedene Arten von Routing:

• Intradomain-Routing findet innerhalb eines autonomen Systems („AS“) statt;
• Interdomain-Routing bezeichnet das Routing zwischen autonomen Systemen.

Hierbei bezieht sich der Namensbestandteil „domain“ auf das autonome System; er hat also nichts mit den „DNS-Domains“ beispielsweise bei Web-Adressen zu tun.

Intradomain-Routing

Intradomain-Routing verwendet Interior Gateway-Protokolle (IGP). Der Fokus beim Intradomain-Routing liegt in den meisten Fällen auf einer technisch effizienten Nutzung des Netzwerks; ihm liegt typischerweise eine Wegewahl entlang kürzester Pfade zugrunde.

Der Administrator versucht, durch geschicktes Konfigurieren des Routings das durch das Netzwerk übertragbare Datenvolumen zu maximieren. Dieses Optimieren des Routings unter Berücksichtigung des real vorhandenen Datenübertragungsbedarfs zwischen verschiedenen Teilen des Netzwerks nennt man Traffic Engineering.

Interdomain-Routing

Interdomain-Routing verwendet sogenannte Exterior Gateway-Protokolle (EGP), und zwar (fast) immer BGP. Da Interdomain-Routing das Routing zwischen verschiedenen Providern regelt, liegt der Fokus beim Interdomain-Routing normalerweise auf einer finanziell effizienten (profitorientierten) Nutzung des Netzwerks. Die zugrundeliegende Idee hierbei ist die, dass ein autonomes System nicht allen seinen Nachbarn die gleichen Informationen (Routen) zukommen lässt. Welche Informationen ausgetauscht werden und welche nicht, wird zunächst in Verträgen festgelegt und dann in den Routern einkonfiguriert; man spricht in diesem Zusammenhang von Policy-basiertem Routing.

IP-Routing am Beispiel

Einfache Protokolle wie z. B. natives NETBIOS kennen kein Routing; hier identifizieren sich zwei Stationen ausschließlich durch die MAC-Adressen ihrer Netzwerkkarten. Das ist auch bei IP-Kommunikation innerhalb eines gemeinsamen Netzes (ohne Routing) so – zumindest, nachdem per ARP bzw. NDP die zur IP-Adresse gehörende MAC-Adresse ermittelt wurde. Dann enthält jedes Paket die MAC- und IP-Adresse des Empfängers so wie die MAC- und IP-Adresse des Absenders sowie optionale Nutzdaten.

Liegen Absender und Empfänger in verschiedenen Netzen, ist ein Router erforderlich. Möchte eine über Router angebundene Station ein Paket an einen Empfänger außerhalb ihres Netzes senden, beispielsweise an einen Telnet-Server, so funktioniert der Kommunikationsprozess (vereinfacht dargestellt) wie folgt: Zuerst ermittelt die Station den für das gewünschte Ziel nächstgelegenen Router (siehe Routingtabelle), ermittelt per ARP dessen MAC-Adresse und baut ein Paket wie folgt zusammen: Es erhält als Ziel-MAC-Adresse die MAC-Adresse des nächstgelegenen Routers, die Ziel-IP-Adresse des Empfängers, die Ziel-Portadresse 23 für den Telnet-Server sowie die MAC- und IP-Adresse des Absenders und einen Absenderport (irgendein gerade freier Port, z. B. 5387) für die gerade anfragende Telnet-Sitzung sowie andere erforderliche Daten. Der Router empfängt und verarbeitet das Paket, weil es an seine MAC-Adresse gerichtet ist. Bei der Verarbeitung im Router wird das Paket in leicht abgeänderter Form weitergeleitet: Der Router ermittelt den nächsten Router, ermittelt per ARP dessen MAC-Adresse und baut das Paket wie folgt um: Es erhält nun abweichend als Ziel-MAC-Adresse die MAC-Adresse des nächsten Routers sowie als Quell-MAC-Adresse die eigene MAC-Adresse. Die IP-Adresse des Empfängers, Ziel-Port 23 sowie die IP-Adresse des Absenders, Absender-Port 5387 und die Nutzdaten hingegen bleiben gleich. Das bedeutet: Auf Schicht 3 (IP) wird das Paket nicht verändert. Dieser Vorgang wiederholt sich, bis ein letzter Router die Zielstation in einem direkt angeschlossenen Netz findet; dann setzt sich das Paket wie folgt zusammen: es enthält die MAC-Adresse der Zielstation, die MAC-Adresse des letzten Routers – also die Daten der letzten Schicht-2-Verbindung (Ethernet) – sowie die IP-Adresse des Empfängers (= Zielstation), Ziel-Port 23 sowie die IP-Adresse des Absenders, Absender-Port 5387 und natürlich Nutzdaten.

Nach erfolgreicher Verarbeitung durch den Telnet-Server wird die Rückantwort dann wie folgt zusammengestellt: MAC-Adresse des für den Rückweg zuständigen Routers (wobei Hin- und Rückroute nicht unbedingt identisch sein müssen), die IP-Adresse des anfragenden Rechners (vormals Absender), die Ziel-Portadresse 5387 (vormals Absender-Port) sowie die MAC- und IP-Adresse des Telnet-Servers und dessen Absenderport, sowie Antwort-Daten. Nachdem alle Router durchlaufen wurden, wird daraus im letzten Router: MAC-Adresse und IP-Adresse des anfragenden Rechners, die MAC-Adresse des letzten Routers, die Ziel-Portadresse 5387 sowie die IP-Adresse des Telnet-Servers und dessen Absenderport, sowie Antwort-Daten. Wird diese Telnet-Sitzung beendet, wird auch Port 5387 wieder freigegeben.

Zusammenwirken von Protokollen

Abhängig davon, ob ein Router Teil eines autonomen Systems ist oder gar dessen Grenze bildet, verwendet er oftmals gleichzeitig Routing-Protokolle aus verschiedenen Klassen:

• Interior Gateway Protocols (IGPs) tauschen Routing-Informationen in einem einzelnen autonomen System aus. Häufig verwendet werden:
  • IGRP/EIGRP (Interior Gateway Routing Protocol/ Enhanced IGRP)
  • OSPF (Open Shortest Path First)
  • IS-IS (Intermediate System to Intermediate System)
  • RIP (Routing Information Protocol)
  • R-SMLT Routing SMLT
• Exterior Gateway Protocols (EGPs) regeln das Routing zwischen verschiedenen autonomen Systemen. Dazu gehören:
  • BGP (Border Gateway Protocol: seit 2002 in der Version BGP4) ist heute weltweit der De-facto-Standard.
  • EGP (mit dem alten Exterior Gateway Protocol wurden früher die Internet-Backbones verbunden. Es ist inzwischen veraltet.)
• Ad hoc Routing-Protokolle werden in Netzen mit wenig oder keiner Infrastruktur verwendet.
  • OLSR findet meist Verwendung im mobilen Bereich.
  • AODV findet in kleineren Netzen mit hauptsächlich statischem Traffic Verwendung.

Dabei können Routingprotokolle auch miteinander interagieren. Beispielsweise können neue Routen aus dem IGP zum EGP exportiert werden. Auch andere Fälle sind denkbar: Ändert sich, z. B. durch den Ausfall eines Links, die IGP-Metrik für einen Pfad a⇝b innerhalb des AS X, so kann X die Metrikänderung auf alle EGP-Pfade a⇝b⇝Y, a⇝b⇝Z usw. übertragen. Es ist auch denkbar, dass sich einige Routen, welche ein Router von verschiedenen Routingprotokollen gelernt hat, gegenseitig widersprechen; in solchen Fällen regelt eine vorher definierte Priorisierung (Administrative Distanz) die letztendliche Entscheidung des Routers.

Übersicht/Zusammenfassung Routing-Protokolle

Routing- Protokoll	Routing- Algorithmus	Shortest-Path- Algorithmus	Einsatz	Metrik	Anmerkungen
BGP	Path-Vector	Bellman-Ford	EGP	Policies	De-facto-Standard, verhindert Schleifen
RIP	DV	Bellman-Ford	IGP	Hop-Count	Count-to-Infinity-Problem
OSPF	LS	Dijkstra	IGP	*	hierarchisches Routing
IS-IS	LS	Dijkstra	IGP	*	ISO-Standard, vglb. mit OSPF
EIGRP	DV	DUAL	IGP	*	Cisco-Standard

* verschiedene (teilweise kombinierbare) Metriken

Siehe auch

• Multi-Path Routing
• Ad-hoc On-demand Distance Vector (AODV)
• Classless Inter-Domain Routing (CIDR)
• Dijkstra-Algorithmus
• eXtensible Open Router Platform (XORP)
• Multiprotocol Label Switching (MPLS)
• Network Address Translation (NAT)
• Optimized Link State Routing (OLSR)
• Routing Information Protocol (RIP)
• Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)

Weblinks

• Linkkatalog zum Thema Router und Routing bei curlie.org (ehemals DMOZ)
• Übersicht über Routing-Metriken (PDF-Datei; 7,09 MB)