Rechnernetze

Beispiel zur hierarchischen Leitwegbestimmung

Das folgende Beispiel soll die Vorteile dieses Ansatzes noch etwas genauer verdeutlichen. Würde für jeden Knoten die vollständige Wegetabelle aufgestellt werden, so würde die Wegetabelle für das Netzwerk im Bild die Länge 12 besitzen.

Durch den hierarchischen Aufbau des Netzes verringert sich die Anzahl der Einträge jedoch erheblich; für die Knoten in Region 1 sind sechs Einträge, für Region 2 sind fünf Einträge und für Region 3 sind sieben Einträge erforderlich. Als Beispiel soll für den Knoten 33 die Wegetabelle angegeben werden.

q\s

31

32

33

34

35

R1

R2

D33

2

2

0

2

1

3

3

Agl.

32

32

-

35

35

32

35

Allerdings ergibt sich durch die Zusammenfassung der Knoten in Regionen nicht nur der Vorteil, dass die Wegetabellen kürzer werden, sondern auch der Nachteil länger werdender Pfadlängen. Während der optimale Weg (bzgl. einer minimalen Pfadlänge) vor der Einteilung in Regionen zwischen den Knoten 34 und 11

W_34,11^opt= (34, 31, 12, 11)

die Pfadlänge drei hatte, ist nach der Einteilung in Regionen der Weg

W_34,11^opt= (34, 22 ,21, 13, 11)

und hat damit die Pfadlänge vier.

Es stellt sich also die Frage, ob bei einer Einteilung eines Netzwerkes in Hierarchiestufen die Vorteile der kürzeren Wegetabellen und des geringeren Verwaltungsaufwands die größer werdenden Pfadlängen rechtfertigt. In einer Studie, die 1979 von Khan und Kleinrock erstellt wurde, konnte gezeigt werden, dass die optimale Anzahl von Hierarchiestufen in einem Netz mit N Knoten ln N ist, und dass die durch die Einteilung in Hierarchiestufen bedingte Steigerung der durchschnittlichen Pfadlängen vernachlässigbar ist.