4. Der Rip-Routing-Algorithmus

In diesem Kapitel wir der RIP-Routing-Algorithmus, der Routing-Algorithmus des Internets, allgemein beschrieben (4.1). Danach wird auf den Initialisierungsvorgang (4.1.1) und ausgewählte Probleme und deren Lösung durch den Algorithmus, wie unterbrochene Verbindungen (4.1.2), Counting to Infinity (4.1.3), Split Horizon Verfahren (4.1.4) und zeitgesteuerter Leitwegtabellenaustausch (4.1.5) eingegangen.

Im Abschnitt 4.1.6 werden dann die Besonderheiten des RIP-Routing-Algorithmus aufgezeigt.

Abschließend wird noch das zugrundeliegende objektorientierte Analysemodell und das Design (4.2) erläutert.

Als Basis für die folgenden Ausführungen diente das Kapitel "Why Is RIP So Simple?" [Hui95, S.65ff].

4.1 Allgemeine Beschreibung

Der RIP-Routing-Algorithmus ( Routing Information Protocol ) gehört zur Familie der Distance Vector Routing Algorithmen. Diese Routing Algorithmen sind sehr einfach aufgebaut und basieren auf dem Kürzeste-Wege-Algorithmus von Bellman/Ford/Ful-kerson ( Anhang H ), der dezentral ausgeführt wird. Die Teil-berechnungen werden von den Rechnern im Netzwerk ausgeführt und tauschen die benötigten Informationen untereinander aus.

Abbildung 10 - Distance Vector Routing - Cold Start

[Hui95, S.65f]

Als Basis für die Beschreibung des allgemeinen Distance Vector Routing Algorithmus dient das Beispielnetzwerk Abb.10 a).

4.1.1 Initialisierungsvorgang des Netzwerks - Cold Start

Wird ein Rechner eingeschaltet, dann hat er nur lokale Kenntnisse (Beispiel Rechner A Abb. 10 b)). Die Rechner wissen zu diesem Zeitpunkt nicht, wieviele Rechner im Netzwerk und welche Rechner an den anderen Enden ihrer Verbindungen sind.

Nun schicken die Rechner ihre Leitwegtabelle (Routingtable) in Form von Entfernungsvektoren (Distance Vector) über alle Verbindungen an die benachbarten Rechner.

Rechner A erhält z.B. von Rechner B über die Verbindung 1 mit Kosten 1 den Entfernungsvektor B = 0.

A erhöht die Entfernung nun um 1 und prüft, ob noch kein Eintrag für B in seiner Leitwegtabelle oder ein Eintrag mit höherer Entfernung vorhanden ist. Wenn ja, dann wird der Eintrag aktualisiert bzw. hinzugefügt. Wenn ein Eintrag mit niedrigerer Entfernung vorhanden ist, dann wird der Entfernungsvektor verworfen.

Jedesmal, wenn ein Rechner eine Leitwegtabelle eines benach-barten Rechners erhält, prüft er, wie oben beschrieben, ob die enthaltenen Informationen eine Änderung seiner Leitwegtabelle zur Folge haben. Wenn ja, wird die Tabelle aktualisiert und über alle Verbindungen an die Nachbarrechner geschickt. Sonst wird die Nachricht ignoriert. In Abbildung 10 c) bis f) sind einige Veränderungen in den Leitwegtabellen von Rechner A und E exemplarisch dargestellt, die beim Kaltstart des Netzwerks aus Abb. 10 a) auftreten können.

Abbildung 11 - Distance Vector Routing - Broken Link

[Hui95, S.66f]

4.1.2 Unterbrochene Verbindungen - Broken Links

Wie die Rechner ihre Leitwegtabelle berechnen, wurde im vorherigen Abschnitt dargestellt, was passiert nun, wenn eine Verbindung zusammenbricht?

Für die Beantwortung dieser Frage diene das Netzwerk in Abb. 11 a) als Beispiel.

Im ersten Schritt merken die Rechner, zwischen denen die Verbindung bestand, das diese keine Daten mehr überträgt und verändern ihre Leitwegtabelle (Abb.11 b)+c)).

Als nächstes wird die neue Leitwegtabelle versandt. Nach mehreren Schritten, wie sie beim Cold Start auch durchgeführt werden, kommt es dann zu den neuen Leitwegtabellen Abb. 11 d) und e).

Abbildung 12 - Distance Vector Routing - Counting to Infinity [Hui95, S.70f]

4.1.3 Counting to Infinity Problem

Angenommen das Netzwerk sehe nun wie in Abb. 12 c) aus (Rechner A und D siehe a) und b)). Der Rechner D merkt, daß die Verbinung zu E nicht mehr vorhanden ist und ändert seine Leitwegtabelle (Abb.12 e)). Nun gibt es zwei mögliche Fälle:

Sendet nun Rechner D seine Leitwegtabelle zu Rechner A, bevor Rechner A seine an Rechner D sendet, dann merkt Rechner A, daß die Rechner B,C,E nicht mehr erreichbar sind (Abb. 12 d)).

Falls jedoch A zuerst seine Leitwegtabelle zu D schickt, dann ändert D seine Leitwegtabelle wie in Abb. 12 f) gezeigt.

Bei jedem Austausch der Leitwegtabelle wird nun die Entfernung zu B,C und E um 2 erhöht, bis der Infinity-Wert erreicht wird, da jetzt eine Endlosschleife vorhanden ist.

4.1.4 Split Horizon Verfahren

Um ein Fehlverhalten des Netzwerks, wie in 4.1.3 gezeigt, zu verhindern, wurde das Split Horizon Verfahren entwickelt.

Dieses Verfahren basiert auf einer simplen Sicherheits-vorkehrung:

Wenn Rechner A Datenpakete, die zu Rechner X gelangen sollen, über Rechner B sendet, dann macht es keinen Sinn für Rechner B, zu versuchen, Rechner X über Rechner A zu erreichen. Also ist es unsinnig für Rechner A, Rechner B mitzuteilen, daß sich Rechner X nur in einer geringen Entfernung zu Rechner A befindet.

Daraus ergibt sich eine minimale Änderung des Distance Vector Routing Protokols:

Statt die selben Entfernungsvektoren über alle abgehenden Verbindungen zu verschicken, werden verschiedene Versionen von Entfernungsvektoren versandt, um zu berücksichtigen, daß manche

Ziele über eine bestimmte abgehende Verbindung erreicht werden.

Es gibt zwei Variationen des Split Horizon Verfahrens:

In der einfachen Version vernachlässigen die Rechner in ihren Nachrichten jegliche Informationen über die Ziele, die erreicht werden können.

Die aggressivere Strategie ist als Split Horizon mit Poisonous Reverse bekannt. Hierbei werden alle Rechner in der Entfernungsvektoren-Nachricht berücksichtigt, aber die Entfernung wird auf den Infinity-Wert gesetzt, wenn das Ziel über die Verbindung, über die die Nachricht verschickt wird, erreicht wird.

Zwei-Rechner-Schleifen werden somit sofort eliminiert, aber das Verfahren schützt nicht vor allen Formen von Schleifen.

Die Abb. 13 zeigt wie es zu einer Drei-Rechner-Schleife zwischen den Rechnern C,B und E kommen kann.

Ausgehend von der Netzwerksituation des Counting to Infinity- Abschnitts (Abb. 13 a)) wird der Vorgang nun genauer betrachtet:

Direkt nach der Störung der Verbindung zwischen D und E, beinhalten die Leitwegtabellen der Rechner B,C und E die Einträge aus Abb. 13 b), da der Rechner E den Verbindungs-abbruch bemerkt und auf den Verbindungen 4 und 5 die neue Entfernung zu D (inf) gesendet hat.

Geht man davon aus, das der Rechner B die Nachricht empfängt, aber der Rechner C z.B. wegen eines Übertragungsfehlers nicht, so finden sich in den Leitwegtabellen von B,C und E die Einträge aus Abb. 13 c).

Wenn nun Rechner C seine Leitwegtabelle mit poisonous reverse verschickt, so sendet er auf Verbindung 5 die Entfernung inf zu E und eine Entfernung von 2 auf Verbindung 2.

Dies hat zu Folge, daß Rechner B seine Leitwegtabelle so ändert, daß die Verbindung 2 die Entfernung inf und die Verbindung 4 die Entfernung 3 erhält. Diese Änderung stellt Abb. 13 d) dar.

Nun kann man eine Drei-Rechner-Schleife zwischen den Rechnern B, C und E beobachten. Bei weiterem Austausch von Leitweg-tabellen werden die Entfernungen erhöht, ohne daß sich die Route ändert, so daß das Netzwerk wieder mit dem Counting to Infinity Problem zu kämpfen hat.

Abbildung 13 - Distance Vector Routing - Entwicklung einer

Drei-Rechner-Schleife [Hui95, S.77f]

4.1.5 Zeitgesteuerter Leitwegtabellenaustausch - Triggered Updates

Bisher wurde der zeitliche Aspekt, wann die Leitwegtabellen zu den Nachbarrechnern gesendet werden, vernachlässigt.

Eine Möglichkeit, das Problem mit den Schleifen zu lösen bzw. die Zeit bis zu Erkennung (Counting to Infinity) zu verkürzen, ist nach einer bestimmten Zeit, die Leitwegtabellen mit seinen Nachbarrechnern auszutauschen, auch wenn sich das Netzwerk nicht verändert hat. Dadurch wird die Verbreitung fehlerhafter Nachrichten verringert, und falls doch einmal eine Schleife auftritt, wird die Verbindungsentfernung schneller auf den Infinity-Wert hochgezählt. Wird dieser Wert erreicht, können nun beim neuerlichen Austausch der Leitwegtabellen die Schleifen entfernt werden.

4.1.6 Besonderheiten des RIP-Routing-Algorithmus

Der RIP-Routing-Algorithmus hat gegenüber dem bisher beschriebenen Distance Vector Routing Algorithmus einige Einschränkungen bzw. Erweiterungen:

4.2 Analyse und Design

Die Simulation des RIP-Algorithmus wurde an die von Robert Denda geschriebene Simulation des DVMRP-Routing-Algorithmus [Den97] angepaßt und zusammen mit dieser zu einer Gesamt-simulation geformt.

Die Problemspezifikation weist nur einen Unterschied zu der DVMRP-Simulation [Den97] auf: Lediglich der zu simulierende Algorithmus ist ein anderer.

Das Analysemodell aus [Den97] ist in Anhang C dargestellt. Es bildet die Grundlage für die neuen Analysemodelle für die Simulationen der RIP- und DVMRP-Algorithmen, die im Anhang D abgedruckt sind. (Die Vererbungstrukturen der Klassen der beiden Simulationen lassen sich im Anhang E nachvollziehen.)

Beim Design gibt es nur eine kleine Änderung:

Bei der Bedienung des "Senden starten"-Knopfes der RIP-Simulation ist zuerst der Senderechner und dann der Emfang-rechner anzuwählen. Bei der DVMRP-Simulation braucht hingegen nur der Senderechner ausgewählt zu werden, da im Multicast-Betrieb an alle Rechner im Netz gesendet wird.

[Anfang]   [Inhaltsverzeichnis]   [Weiter]

[Abbildungsverzeichnis] [Literaturverzeichnis]