Distanzvektoralgorithmus

Distanzvektoralgorithmus

Beim Distanzvektoralgorithmus handelt es sich um einen dynamischen Routing-Algorithmus, der nach dem Prinzip „Teile deinen Nachbarn mit, wie du die Welt siehst“ funktioniert und intern auf dem Bellman-Ford-Algorithmus basiert. Er wird von Routern in paketvermittelten Netzwerken eingesetzt und ist im Internet z. B. als RIP und IGRP implementiert. Distanzvektorprotokolle sind selbstorganisierend, vergleichsweise einfach zu implementieren und funktionieren nahezu ohne jede Wartung.

Inhaltsverzeichnis

Prinzip

Das prinzipielle Vorgehen eines Distanzvektorprotokolls:

  1. Erzeuge eine Kostenmatrix, welche Router über welche Nachbarn und zu welchen Kosten erreichbar sind. - Diese Matrix enthält anfangs nur die (bekannten) Kosten zu direkten Nachbarn.
  2. Erzeuge eine Aufstellung mit Informationen, welche Router wir zu welchen Kosten am besten erreichen können und schicke sie an alle Nachbarn.
  3. Warte auf Aufstellungen dieser Art von anderen Routern, rechne diese dann in die eigene Kostenmatrix ein.
  4. Ändern sich dadurch die minimalen Kosten, zu denen wir einen Router erreichen können: fahre mit Schritt 2 fort, sonst mit Schritt 3.

Beispiel

Es existieren vier Router A-D und zwischen ihnen folgende Links:

Networkabcd.svg

Im folgenden sind die Kostenmatrizen der Router zu Beginn und nach jedem vollständigen Austausch von Datenpaketen dargestellt. Dabei ist der beste Pfad zu einem anderen Router jeweils grün, ein neuer bester Pfad - der im nächsten Schritt an die Nachbarn gesendet wird - gelb hinterlegt.

T=0
von A via A via B via C via D
zu A
zu B 3
zu C 23
zu D
von B via A via B via C via D
zu A 3
zu B
zu C 2
zu D
von C via A via B via C via D
zu A 23
zu B 2
zu C
zu D 5
von D via A via B via C via D
zu A
zu B
zu C 5
zu D
T=1
von A via A via B via C via D
zu A
zu B 3 25
zu C 5 23
zu D 28
von B via A via B via C via D
zu A 3 25
zu B
zu C 26 2
zu D 7
von C via A via B via C via D
zu A 23 5
zu B 26 2
zu C
zu D 5
von D via A via B via C via D
zu A 28
zu B 7
zu C 5
zu D
T=2
von A via A via B via C via D
zu A
zu B 3 25
zu C 5 23
zu D 10 28
von B via A via B via C via D
zu A 3 7
zu B
zu C 8 2
zu D 31 7
von C via A via B via C via D
zu A 23 5 33
zu B 26 2 12
zu C
zu D 51 9 5
von D via A via B via C via D
zu A 10
zu B 7
zu C 5
zu D
T=3
von A via A via B via C via D
zu A
zu B 3 25
zu C 5 23
zu D 10 28
von B via A via B via C via D
zu A 3 7
zu B
zu C 8 2
zu D 13 7
von C via A via B via C via D
zu A 23 5 15
zu B 26 2 12
zu C
zu D 33 9 5
von D via A via B via C via D
zu A 10
zu B 7
zu C 5
zu D

Erläuterung der Vorgänge im Router A:

  • T=0: Wir erzeugen die initiale Kostenmatrix. Sie enthält nur unsere direkten Nachbarn B und C mit den uns bekannten Kosten. Wir schicken daraufhin unsere neuen besten Pfade (B mit Kosten 3, C mit Kosten 23) an unsere direkten Nachbarn
  • T=1: Wir haben von den Routern B und C Datenpakete erhalten und wissen jetzt, zu welchen Kosten wir D und wie wir C und B jeweils auch erreichen können. Im Fall der Zielrouter C und D ist das sogar ein neuer bester Pfad, den wir im nächsten Schritt an unsere Nachbarn übertragen werden
  • T=2: Wir haben von Router B ein Datenpaket erhalten und wissen jetzt, dass B den Router D günstiger erreichen kann. Wir tragen die Kosten in unsere Matrix ein und werden diesen neuen besten Pfad wieder an unsere Nachbarn verbreiten.
  • T=3: Wir haben keine neuen Informationen mehr empfangen; unsere besten Pfade haben sich nicht geändert und wir senden keine neuen Informationen an unsere Nachbarn. Denen geht es genauso - der Algorithmus terminiert.

Probleme

Ein Problem des Distanzvektoralgorithmus ist das Zählen bis Unendlich, der sogenannte Count-To-Infinity-Effekt[1]. Dieser lässt sich an folgendem Beispiel zeigen. Gehen wir davon aus, dass sich der Link von C nach D drastisch verschlechtert und betrachten die Situation aus der Sicht von Router A:

  • Wir empfangen von C die Meldung, dass D über ihn nur noch sehr schlecht zu erreichen ist. Das ändert jedoch nichts an unserem besten Pfad, der ja über B führt.
  • Bald bekommen wir aber auch von B die Meldung, dass D über ihn nur noch sehr schlecht zu erreichen sei - die Pfadkosten seien auf 13(!) angestiegen. Dass die Kosten nicht deutlich höher angesetzt wurden liegt daran, dass B ja noch eine indirekte Route kannte, die zu D führt: die Route B-A-B-C-D. Und A gab ja nach bestem Wissen an, er könne D zu den Kosten 10 erreichen.
  • Nun haben sich aber unsere Pfadkosten zu D geändert. Weil B den Router D nur noch zu Kosten von 13 erreichen kann, können auch wir D nur noch zu Kosten von 16 erreichen.
  • Dadurch ändert sich aber wieder unser bester Pfad, was wir gleich wieder B mitteilen - die Pfadkosten werden langsam hochgezählt statt sprunghaft zu steigen.

Das Zählen bis Unendlich lässt sich bei direkten Schleifen zwischen zwei Routern relativ leicht vermeiden. Eine Pfadinformation darf nicht über dasselbe Interface veröffentlicht werden, worüber sie empfangen wurde. Dieses Verfahren nennt man Split-Horizon.

Im Fall von längeren Schleifen ist eine Lösung des Problems nicht mehr trivial. In Distanzvektorprotokollen gilt allgemein, dass sich Nachrichten über die Erhöhung der Kosten nur langsam verbreiten. Um auch diesem Problem Herr zu werden, werden das Poisoned-Reverse-Verfahren und so genannte Triggered Updates verwendet: Findet ein Router heraus, dass ein Nachbar nur noch schwer oder gar nicht mehr erreichbar ist, veröffentlicht er diese Tatsache sofort aktiv im Netz.

In einer Abwandlung des Distanzvektoralgorithmus, dem sogenannten Distance-Path-Algorithmus den z. B. BGP implementiert, ließe sich das Problem von Schleifen leichter lösen. Dieser Algorithmus speichert neben dem nächsten Hop auch noch den gesamten restlichen Pfad zum Zielrouter. So lassen sich neben dem Kriterium "günstigste Route" auch leicht andere Kriterien, z. B. firmenpolitische Maßgaben, umsetzen.

RIP-Versionen

Für IPv4 liegen zwei Versionen von RIP vor: RIPv1 und RIPv2. In RIPv1 sind keine Subnetzmasken implementiert.

Für IPv6 wurde RIP angepasst und unter der Bezeichnung RIPng veröffentlicht.

Weblinks

Literatur

  • James F. Kurose, Keith W. Ross: Computernetzwerke: Der Top-Down-Ansatz, Pearson Studium, 4. aktualisierte Auflage (1. September 2008), ISBN 978-3827373304, S. 425.

Einzelnachweise

  1. Andrew S. Tanenbaum: Computernetzwerke, Pearson Studium, 4. überarbeitete Auflage (15. Juli 2003), ISBN 978-3827370464, S. 397.

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • IP-Routing — Routing [ˈruːtɪŋ] (BE) / [ˈraʊtɪŋ] (AE) (engl. „Lotsen“, „Wegewahl“, „Verkehrslenkung“) bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme bei der Nachrichtenübermittlung über vermaschte Nachrichtennetze bzw.… …   Deutsch Wikipedia

  • Leitweglenkung — Routing [ˈruːtɪŋ] (BE) / [ˈraʊtɪŋ] (AE) (engl. „Lotsen“, „Wegewahl“, „Verkehrslenkung“) bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme bei der Nachrichtenübermittlung über vermaschte Nachrichtennetze bzw.… …   Deutsch Wikipedia

  • Routing-Protokoll — Routing [ˈruːtɪŋ] (BE) / [ˈraʊtɪŋ] (AE) (engl. „Lotsen“, „Wegewahl“, „Verkehrslenkung“) bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme bei der Nachrichtenübermittlung über vermaschte Nachrichtennetze bzw.… …   Deutsch Wikipedia

  • Statisches Routing — Routing [ˈruːtɪŋ] (BE) / [ˈraʊtɪŋ] (AE) (engl. „Lotsen“, „Wegewahl“, „Verkehrslenkung“) bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme bei der Nachrichtenübermittlung über vermaschte Nachrichtennetze bzw.… …   Deutsch Wikipedia

  • Wegewahl — Routing [ˈruːtɪŋ] (BE) / [ˈraʊtɪŋ] (AE) (engl. „Lotsen“, „Wegewahl“, „Verkehrslenkung“) bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme bei der Nachrichtenübermittlung über vermaschte Nachrichtennetze bzw.… …   Deutsch Wikipedia

  • Count-To-Infinity — Beim Distanzvektoralgorithmus handelt es sich um einen dynamischen Routing Algorithmus, der nach dem Prinzip „Teile deinen Nachbarn mit, wie du die Welt siehst“ funktioniert und intern auf dem Bellman Ford Algorithmus basiert. Er wird von Routern …   Deutsch Wikipedia

  • Distance-Vector — Beim Distanzvektoralgorithmus handelt es sich um einen dynamischen Routing Algorithmus, der nach dem Prinzip „Teile deinen Nachbarn mit, wie du die Welt siehst“ funktioniert und intern auf dem Bellman Ford Algorithmus basiert. Er wird von Routern …   Deutsch Wikipedia

  • Distance-Vector-Algorithmus — Beim Distanzvektoralgorithmus handelt es sich um einen dynamischen Routing Algorithmus, der nach dem Prinzip „Teile deinen Nachbarn mit, wie du die Welt siehst“ funktioniert und intern auf dem Bellman Ford Algorithmus basiert. Er wird von Routern …   Deutsch Wikipedia

  • Distanzvektor — Beim Distanzvektoralgorithmus handelt es sich um einen dynamischen Routing Algorithmus, der nach dem Prinzip „Teile deinen Nachbarn mit, wie du die Welt siehst“ funktioniert und intern auf dem Bellman Ford Algorithmus basiert. Er wird von Routern …   Deutsch Wikipedia

  • Distanzvektorprotokoll — Beim Distanzvektoralgorithmus handelt es sich um einen dynamischen Routing Algorithmus, der nach dem Prinzip „Teile deinen Nachbarn mit, wie du die Welt siehst“ funktioniert und intern auf dem Bellman Ford Algorithmus basiert. Er wird von Routern …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”