Distanzvektor-Routing

Wenn du eine Webseite öffnest, reisen viele kleine Datenpakete durch Netzwerke. An jeder Abzweigung muss ein Gerät entscheiden, wohin es das Paket als Nächstes schickt. Distanzvektor-Routing hilft dabei, gute Wege zu finden, obwohl kein Router das ganze Netzwerk sehen muss.

Router finden Wege

Ein Router ist ein Netzwerkgerät, das Datenpakete zwischen Netzwerken weiterleitet. Routing bedeutet, für ein Datenpaket den nächsten Schritt auf dem Weg zum Ziel festzulegen.

Eine Routingtabelle ist die Liste, in der ein Router seine bekannten Wege notiert. Zu einem Ziel enthält sie zum Beispiel die Kosten des Weges und den Router für den nächsten Schritt.

Ein direkter Nachbar ist ein Router, der über eine unmittelbare Verbindung erreichbar ist. Stell dir Router wie Kreuzungen vor: Eine Kreuzung muss nicht den ganzen Weg kennen. Sie muss nur wissen, zu welcher nächsten Kreuzung sie ein Paket schicken soll.

Beim Distanzvektor-Routing speichert jeder Router für jedes Ziel zwei wichtige Angaben:

• die Distanz, also die bekannten Kosten bis zum Ziel,
• den nächsten Hop, also den nächsten Router auf diesem Weg.

Ein Hop ist ein einzelner Sprung von einem Router zum nächsten. Die Kosten eines Weges heißen Metrik. Sie kann zum Beispiel die Anzahl der Hops sein. Kleine Kosten bedeuten: Dieser Weg wird bevorzugt.

Der Distanzvektor

Ein Distanzvektor ist die Liste eines Routers mit seinen derzeit besten Kosten zu allen Zielen. Er ist kein genauer Stadtplan des ganzen Netzes. Er sagt nur: So teuer schätze ich den Weg zu jedem Ziel ein.

Zu Beginn kennt ein Router sich selbst und seine direkten Nachbarn. Zu unbekannten Zielen trägt er zunächst unendlich hohe Kosten ein. Unendlich bedeutet hier: Es ist noch kein Weg bekannt.

So lernen Router voneinander

Router schicken ihren Distanzvektor regelmäßig an direkte Nachbarn. Ein Router erfährt dadurch nicht den vollständigen Weg. Er erfährt nur, welche Kosten der Nachbar für ein Ziel kennt.

Für jedes Ziel vergleicht der Router die Möglichkeiten über seine Nachbarn. Dabei bedeutet \(x\): der betrachtete Router, \(y\): das Ziel und \(v\): ein möglicher direkter Nachbar von \(x\). Die Formel lautet:

\(D_x(y)\) ist die beste bekannte Distanz von Router \(x\) zu Ziel \(y\). \(c(x,v)\) sind die Kosten der direkten Verbindung von \(x\) zu Nachbar \(v\). \(D_v(y)\) sind die Kosten, die Nachbar \(v\) für das Ziel \(y\) meldet. \(\min_v\) bedeutet: Der Router nimmt von allen Nachbarn den kleinsten berechneten Wert.

Bis die Tabellen stabil sind

Nach einem Austausch können sich Routingtabellen ändern. Dann senden Router ihre neue Information weiter. Dieser Vorgang wiederholt sich, bis kein Router mehr einen günstigeren Weg findet.

Diesen stabilen Zustand nennt man Konvergenz. Konvergenz bedeutet: Die Routingtabellen haben sich nach den verfügbaren Informationen eingependelt.

Schwierigkeit: Zählen bis unendlich

Fällt eine Verbindung aus, können Router zunächst veraltete Angaben glauben. Dann kann eine Routing-Schleife entstehen. Das ist ein Kreis: Ein Paket oder eine Wegmeldung läuft zwischen Routern hin und her, statt sicher zum Ziel zu gelangen.

Beim Zählen bis unendlich erhöhen Router die Kosten zu einem nicht mehr erreichbaren Ziel in kleinen Schritten. Ein Router glaubt dann fälschlich, sein Nachbar kenne noch einen Weg. Der Nachbar hatte diesen angeblichen Weg aber ursprünglich über genau diesen Router gelernt.

Eine Gegenmaßnahme heißt Split Horizon. Ein Router meldet eine Route nicht an den Nachbarn zurück, von dem er diese Route gelernt hat. Das verringert besonders die Gefahr einer Schleife zwischen zwei Routern.

Poison Reverse ist eine strengere Variante. Der Router meldet diesem Nachbarn für den betreffenden Weg absichtlich unendliche Kosten. So soll der Nachbar den Rückweg nicht wählen.

Zusammenfassung

Distanzvektor-Routing verteilt Wegwissen von Nachbar zu Nachbar. Jeder Router speichert zu jedem Ziel die beste bekannte Metrik und den nächsten Hop. Er vergleicht eigene Wege mit den Meldungen seiner Nachbarn und übernimmt günstigere Möglichkeiten.