Pfadvektoralgorithmus

Ein Pfadvektorprotokoll ist ein Routing-Protokoll für Computernetzwerke, welches für die einzelnen Elemente (Pfade) jeweils den Vektor mitführt, den dieses Element bei der Ausbreitung durch das Netzwerk genommen hat. Durch den Vektor kann ein Pfad leicht als Schleife erkannt werden, wenn das empfangende System bereits Bestandteil des Vektors ist. Hierdurch werden Unendlichkeitsprobleme vermieden.

Grundprinzip

Um den besten Weg zu einem bestimmten Ziel in einem Netzwerk finden zu können, müssen die Router über eine Liste der möglichen Pfade und der zugehörigen Vektoren, also Wege, verfügen. Bei den verschiedenen Techniken dieser Routingprotokolle gehören die Pfadvektorprotokolle zu den Distanzvektorprotokollen. Ein Router sendet an alle benachbarten Router die Pfade, die über ihn erreichbar sind. Hierbei wird am Anfang der Pfadvektor mit der Kennung des injizierenden Routers initialisiert. Jeder Router, der diesen Pfad empfängt, untersucht den Vektor nach seiner eigenen Kennung. Ist diese nicht enthalten, wird der Pfad mit zugehörigem Vektor der lokalen Datenbank hinzugefügt. Hierdurch hat jeder Router in seiner Datenbank die Pfade des Netzes und jeweils auch die zugehörigen Vektoren.

Arbeitsweise

Jeder Router muss zu jedem Pfadelement auch den zugehörigen Vektor speichern. Für das Beispielmodell

Beispielmodell

sieht dann die Datenbank in Router 7 als Ausschnitt so aus:

Element	Vektor
1	4 - 5 - 1
1	4 - 3 - 2 - 1
1	4 - 5 - 2 - 1
1	4 - 3 - 2 - 5 - 1
...
3	3
3	4 - 3
3	4 - 5 - 2 - 3
3	4 - 5 - 1 - 2 - 3
3	6 - 4 - 3
...
5	6 - 4 - 3 - 2 - 5
5	6 - 4 - 3 - 2 - 1 - 5

Die gesamte Tabelle enthält 42 Einträge. Dies stellt so einen Spannbaum dar. In dieser ungefilterten Form würde der Datenbestand sehr schnell sehr groß werden. Daher wird zum Beispiel bei BGP, einem Pfadvektorprotokoll, jeweils nur der Pfad mit dem kürzesten Vektor weitergegeben. Dies verkleinert die Tabelle auf die Varianten, die bestmögliche Vektoren zum Ziel darstellen.

Element	Vektor
1	4 - 5 - 1
1	3 - 2 - 1
1	6 - 4 - 5 - 1
2	3 - 2
2	4 - 3 - 2
2	6 - 4 - 3 - 2
3	3
3	4 - 3
3	6 - 4 - 3
4	4
4	3 - 4
4	6 - 4
5	3 - 2 - 5
5	4 - 5
5	6 - 4 - 5

Diese optimierte Tabelle enthält nur noch 15 Einträge.

Anwendung

Das Routing des Internet basiert auf BGP, welches ein Pfadvektorprotokoll aus der Gruppe der Distanzvektorprotokolle ist. Als Elementidentifikation wird das IP-Präfix, also die Netzadresse und die Netzmaske genommen.

Jeder Router gehört zu einem autonomen System (AS) und dieses AS wird jeweils als Identifikation in den Pfadvektor geschrieben. Zusätzlich werden auf den einzelnen Routern Richtlinien installiert, die beeinflussen, wann eine Route an benachbarte Router weitergeleitet werden soll.

Pfadvektorprotokolle tauschen die Routingdaten nicht nur bei Änderungen in der Topologie aus, sondern auch in bestimmten Zyklen um eine Konsistenz sicherzustellen. Gegenüber Linkstatusprotokollen haben sie im Allgemeinen höhere Konvergenzzeiten.

Weblinks

• RFC 1771: BGP