Technische Universität Braunschweig -Informatik -Betriebssysteme und Rechnerverbund

Broadcast-Algorithmen

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

Multidestination-Routing

Mehrziel-Wegbestimmung
Dieser Algorithmus will vor allem verhindern, daß Daten (unnötigerweise) mehrfach den gleichen Knoten erreichen. Die komplette Wegbestimmung wird wie bei der direkten Übertragung durch den Sender erledigt. Er bestimmt, welches Paket über welchen Weg am besten zum Ziel kommt. Im Gegensatz zur direkten Übertragung wird aber über jeden Weg nur genau ein Paket verschickt. In dessen Kopf werden dafür aber die Adressen aller Maschinen vermerkt, die durch dieses Paket erreicht werden sollen. Jeder Knoten, der solch ein Paket erhält entfernt seine eigene Adresse aus dem Kopf des Paketes und bestimmt für die übrigen im Kopf des Paketes vermerkten Ziele, über welche Leitungen diese am besten zu erreichen sind. Er sendet daraufhin selbst - entsprechend dem Sender zu Beginn - neue Pakete, in deren Kopf eingetragen ist, welche Maschinen durch das jeweilige Paket erreicht werden sollen.

Multidest-Beispiel Bild 1

Bild 1: Beispielnetz

Im Beispiel in Bild 1 (Graph Simpel 2 im Multidestination-Applet) stellt der Sender (Knoten D) im ersten Schritt fest, daß über eine Verbindung Knoten C zu erreichen ist, über eine andere Verbindung Knoten A und B, über eine Knoten E und über eine Verbindung Knoten F, G und H zu erreichen sind.

Er sendet an Knoten C ein Paket mit nur dessen Adresse im Paketkopf. Knoten C empfängt das Paket, entfernt seine Nummer, stellt fest, daß keine weiteren Maschinen durch dieses Paket erreicht werden sollten und verwirft das Paket.

Das vom Sender an Knoten zwei gesendete Paket enthält im Kopf die Adressen von Knoten A und B. Nachdem Knoten B seine Nummer entfernt hat stellt er fest, daß noch Knoten A durch dieses Paket erreicht werden soll. Er schickt ein entsprechendes Paket auf der passenden Verbindung ab. Wenn dieses Verfahren auch auf alle weiteren Knoten angewendet wird ergibt sich der Ablaufbaum in Bild 2.

Multidest-Ablaufbaum

Bild 2: Ablaufbaum

Der große Vorteil dieses Verfahrens liegt darin, daß nur minimal Datenverkehr entsteht. Es werden im Beispiel genau siebenmal Daten versendet, was bei sieben zu erreichenden Knoten ideal ist.

Der Nachteil dieses Verfahrens ist der große Aufwand, den es macht, in jedem Knoten die Information zu verwalten, welcher Knoten über welchen Ausgang am besten zu erreichen ist. Dieses Verfahren ist relativ aufwendig zu implementieren.

Till Harbaum