Technische Universität Braunschweig -Informatik -Betriebssysteme und Rechnerverbund

Broadcast-Algorithmen

Direkte Übertragung - Fluten - Multidestination Routing - Reverse Path Forwarding

Reverse-Path-Forwarding

Weiterleitung über den umgekehrten Pfad
Bei diesem Verfahren wird in jedem Knoten i geprüft, ob ein ankommendes Paket der Quelle q auf der Leitung empfangen wurde, auf der auch der Knoten i seine Pakete an q übermittelt. Falls das so ist, dann wird davon ausgegangen, daß das Paket auf dem kürzesten Weg übertragen wurde und es wird auf allen anderen Leitungen weitergesendet. Wenn ein Paket dagegen über eine andere Leitung empfangen wurde, als die, auf der Daten an den Sender übertragen werden, dann wird davon ausgegangen, daß es sich um ein Duplikat handelt, das nicht den kürzesten Weg genommen hat. Dieses Duplikat wird dann nicht weitergeschickt, sondern vernichtet.

RevPath-Beispiel Bild 1

Bild 1: Beispielnetz

In Bild 2 ist der Ablauf dieses Verfahrens für das in Bild 1 abgebildete Beispielnetz (Graph Simpel 2 im Reverse-Path-Forwarding-Applet) dargestellt. Im ersten Schritt überträgt der Sender (Knoten D) auf allen Leitungen das Broadcast-Paket. Dieses Paket erreicht die Knoten B, C, E und F direkt. Jeder dieser Knoten prüft nun, ob das Paket über die kürzeste Strecke von Quellknoten kam. Die Pakete werden nun an Knoten A, E, H und F weitergereicht. Jeder dieser Knoten prüft seinerseits, ob das Paket über den kürzesten Weg vom Sender kam. In diesem Fall trifft das nur auf Knoten H zu. Lediglich dieser Knoten sendet sein Paket weiter an Knoten G.

RevPath-Ablaufbaum

Bild 2: Ablaufbaum

Der große Vorteil dieses Algorithmus liegt in seiner einfachen Implementierung. Wenn ein Knoten davon ausgeht, daß ihn ein Paket auf dem kürzesten Weg als erstes erreicht, dann muß lediglich sichergestellt sein, daß ein Empfänger Duplikate erkennen kann. Sobald ein Duplikat empfangen wird, wird davon ausgegangen, daß das Paket nicht auf dem kürzesten Weg ampfangen wurde und es wird nicht weitergeleitet.

Der Nachteil dieses Verfahrens ist, daß einige Knoten das Paket unnötigerweise mehrfach erhalten (Knoten E und F).

Till Harbaum