Rechnernetze
Home Nach oben

Delta-Leitwegbestimmung

Statt einer weitgehend zentralisierten Routingentscheidung kann auch eine dynamische Verteilung der Routingentscheidung zwischen einer Routingzentrale und den lokalen Transitsystemen vorgenommen werden; dieses kann auch als eine Kombination aus der isolierten und der zentralisierten Leitwegbestimmung angesehen werden. Das hier geschilderte Verfahren wurde 1976 von Rudin vorgestellt und ist unter dem Namen Delta-Leitwegbestimmung bekannt.

In diesem Verfahrens ermittelt jeder IMP in regelmäßigen Abständen die Kosten jeder seiner Ausgangsleitungen nach einer bestimmten Gewichtungsfunktion (Kosten, Warteschlangenlänge, Verzögerung usw.) und leitet diese Werte an ein Routing Control Center weiter, welches bei diesem Verfahren der Knoten ist, der für das gesamte Netz die Routingentscheidung trifft.

Aus der Information der einzelnen Knoten berechnet dann das RCC für alle Knoten i und j die nach der Gewichtungsfunktion besten n Wege zwischen den Knoten i und j, die sich auf der ersten Teilstrecke unterscheiden müssen, wobei n ein willkürlich gewählter Parameter ist. Die Kosten Kw,ij für zwei verschiedene Wege w1, w2 zwischen den Knoten i und j werden als äquivalent angesehen, falls

BetragKw1ij-.gif (614 Byte)

gilt, wobei d eine vom Netzwerkbetreiber festzulegende Größe ist; danach wird die Liste der äquivalenten Wege von jedem Knoten zu jedem anderen an die einzelnen Knoten im Netz verteilt; die endgültige Wegewahl aus der Menge der äquivalenten Wege wird dann von den einzelnen Knoten (evtl. zufällig) durchgeführt.

Durch die Einstellung der Werte d und n kann der Betreiber des Netzwerks die Verantwortung für die Wegewahl zwischen dem RCC und den IMPs verschieben. Wählt er für d und n einen sehr kleinen Wert wird sich gegen den besten ein anderer möglicher Weg niemals durchsetzen können und die Verantwortung für die Wegewahl wird ausschließlich im RCC getroffen. Wählt er hingegen sehr große Werte, werden den IMP's viele äquivalente Wege zur Auswahl angeboten.

Durch Simulationen konnte gezeigt werden, daß die Delta-Leitwegbestimmung bessere Ergebnisse liefert als die rein isolierte oder rein zentralisierte Leitwegbestimmung.