Routing

Routing [] (BE) / [], aber auch [] (AE) (engl. „Vermittlung“, „Leitweglenkung“, „Streckenführung“, „Verkehrsführung“ sowie „leiten“, „senden“, „steuern“)route: Wörterbuch / Dictionary (MACMILLAN DICTIONARY) Aus dem "Macmillan Dictionary"routing: Wörterbuch / Dictionary (BEOLINGUS, TU Chemnitz) Aus dem Beolingus Wörterbuch – einem Service der TU Chemnitz ist in der Telekommunikation der Anglizismus für 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

Mit Source Routing kann in Rechnernetzen festgelegt werden, dass die Pakete nur über bestimmte Router zwischen Quellrechner und Zielrechner transportiert werden. In diesem Fall ist der sendenden Station der vollständige Pfad zur Zielstation bekannt. Die sendende Station trägt die Adressen der auf dem Weg zum Ziel liegenden Netzknoten der bereits festgelegten Route in den Kopf der Nachricht ein, z. B. bei IPv4 in das Optionsfeld des IPv4-Headers.Tanenbaum, Feamster, Wetherall: Computer Networks. 6th EditionBadach, Hoffmann: Technik der IP-Netze. 4. Auflage, ISBN 978-3-446-46210-6 Source Routing 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 (dynamisches Routing). 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 und die betroffenen Netzbereiche weiträumig umgangen werden.

Dem Ausfall des 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 (BGPBGP routing policies in ISP networks (PDF; 164 kB). IEEE Network Magazine, special issue on Interdomain Routing, Nov/Dez 2005, Matthew Caesar and Jennifer Rexford.)).

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