Distance-Vector

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 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. Zu den Nachteilen gegenüber Link-State-Protokollen zählen die schlechten Konvergenzeigenschaften und die mangelhafte Skalierbarkeit.

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:

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 88
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, der sogenannte Count-To-Infinity-Effekt, lässt sich an diesem Beispiel auch zeigen. Wir gehen 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.

Der Count-to-Infinity-Effekt lässt sich bei direkten Schleifen zwischen zwei Routern durch Einsatz des Split-Horizon-Verfahrens relativ leicht vermeiden: Eine Pfadinformation darf nicht über dasselbe Interface veröffentlicht werden, worüber sie empfangen wurde.

Im Fall von längeren Schleifen ist eine Lösung des Problems nicht mehr trivial. In Distanzvektorprotokollen gilt allgemein bad news travel slowly. 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


Wikimedia Foundation.

См. также в других словарях:

  • distance vector — noun An class of routing protocol based on sending global state between neighbouring nodes. Distance vector protocols are more suited to external routing as they dont require a consistent world view. Ant: link state …   Wiktionary

  • Distance Vector Multicast Routing Protocol — Saltar a navegación, búsqueda Distance Vector Multicast Routing Protocol, abreviado comúnmente por sus siglas DVMRP, es un protocolo de ruteo multicast. Funcionamiento Resumidamente el protocolo funciona de la siguiente manera: Cuando un router… …   Wikipedia Español

  • Distance Vector Multicast Routing Protocol — (DVMRP Протокол дистанционно векторной многоадресной маршрутизации)  протокол маршрутизации групповых дейтаграмм для IP сетей. Протокол предназначен для использования внутри автономных систем, то есть является протоколом внутридоменной… …   Википедия

  • Distance Vector Multicast Routing Protocol — Distance Vector Multicast Routing Protocol, abreviado comúnmente por sus siglas DVMRP, es un protocolo para aplicaciones multimedia …   Enciclopedia Universal

  • Distance-vector routing protocol — In computer communication theory relating to packet switched networks, a distance vector routing protocol is one of the two major classes of routing protocols, the other major class being the link state protocol. Distance vector routing protocols …   Wikipedia

  • Distance Vector Multicast Routing Protocol — The Distance Vector Multicast Routing Protocol (DVMRP), defined in RFC 1075, is used to share information between routers to facilitate the transportation of IP Multicast packets among networks. It forms the basis of the Internet s multicast… …   Wikipedia

  • Distance Vector Multicast Routing Protocol — Das Distance Vector Multicast Routing Protocol (DVMRP) wird verwendet, um Multicast Pakete in einer Netzkopplung an interessierte Hosts zu verteilen. Es beruht auf dem Unicast Routing Protokoll RIP, was zur effektiven Routenberechnung um den… …   Deutsch Wikipedia

  • distance vector algorithm —    A family of routing algorithms that calculate the bestpath route to use for data transmission from information present in adjacent nodes on the network. Routing information is broadcast periodically rather than only when a change occurs, which …   Dictionary of networking

  • 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

  • Distance Vector Multicast Routing Protocol — (Computers) protocol used for sending multicast transmissions over a network or IP (allows significant savings on network bandwidth), DVMRP …   English contemporary dictionary


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»