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
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
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:
fizierungssegment ersetzt
werden. )
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]