Rechnernetze
Home Nach oben

Mehrziel-Leitwegbestimmung

Das Verfahren der Mehrziel-Leitwegbestimmung (multidestination routing) überprüft im Quellknoten q, zu welchen anderen Knoten i welche seiner Ausgangsleitungen der Anfang eines optimalen Weges ist. Für alle Zielknoten, deren optimaler Weg mit einer gemeinsamen Ausgangsleitung beginnt, wird nur ein Paket erzeugt. In den Kopf dieses Pakets werden dann jeweils die Indizes der Knotennummern eingetragen, die auf dem gemeinsamen Weg liegen. Jeder Knoten, der auf dem optimalen Weg passiert wird, entfernt den Index seiner Knotennummer und leitet das Paket weiter; an einer Vergabelung der Wege werden die Pakete kopiert und nur jene Zielknotenadressen übernommen, die auf den jeweiligen Wegen liegen. Zum Schluss ist nur noch ein Index in dem Paket vorhanden, und der Knoten vernichtet das Paket.

RUNDESENDE-1.WMF (4796 Byte)

In unserem Beispiel werden vom Quellknoten 4 die folgenden vier Pakete erzeugt.

Leitung zum Knoten 2 mit Adressen für Knoten 1, 2.
Leitung zum Knoten 3 mit Adressen für Knoten 3.
Leitung zum Knoten 5 mit Adressen für Knoten 5.
Leitung zum Knoten 6 mit Adressen für Knoten 6, 7, 8.

In den Knoten 3 und 5 wird das Paket nicht weitergeleitet. Die Knoten 2 und 6 entfernen jeweils ihre Knotennummer und reichen das Paket an den Knoten 1 bzw. 8 weiter.

Leitung zum Knoten 1 mit Adressen für Knoten 1.
Leitung zum Knoten 8 mit Adressen für Knoten 7, 8.

Knoten 8 leitet schließlich das Paket an Knoten 7 weiter.

Leitung zum Knoten 7 mit Adressen für Knoten 7.

Insgesamt werden bei diesem Verfahren 7 Pakete zwischen den Nachbarknoten ausgetauscht. Dieses Verfahren ist also deutlich besser für einen Broadcast geeignet, da es offensichtlich vermieden wird, zu viele Pakete zu senden. Allerdings müssen hier zusätzliche Adressen in jedem Paket verwaltet werden, deren Anzahl von der Anzahl der über einen Pfad zu erreichenden Pakete abhängt, also für verschiedene Pfade verschieden ist. Das Verfahren erfordert also einen größeren Implementierungsaufwand.