3. Der Hot-Potato-Algorithmus
In diesem Kapitel wird der erste
der betrachteten Routing-Algorithmen, der Hot-Potato-Algorithmus,
betrachtet, wobei zunächst eine allgemeine Beschreibung
(3.1) und einige mögliche Varianten (3.2) beschrieben werden.
Die Ausführungen dieser beiden Abschnitte lehnen sich hierbei
eng an die Erläuterungen in [Tan88, S. 358f] an.
Daran anschließend werden nach
der Problemspezifikation (3.3.1)die zugrundeliegenden objektorientierten
Analysemodelle (3.3.2) und das Design (3.3.3) beschrieben.
3.1 Allgemeine Darstellung
Der Hot-Potato-Algorithmus von Baran
ist ein einfacher isolierter adaptiver Algorithmus aus dem
Jahre 1964.
Ein isolierter adaptiver Algorithmus
ist ein dezentraler Leit-weg-Bestimmungsalgorithmus, bei dem die
Rechner die Leitweg-bestimmung auf Grund selbstgesammelten Informationen
durch-führen, wobei Informationen über günstigste
Wege nicht mit anderen Rechnern ausgetauscht werden. Trotzdem
paßt sich ein solcher Algorithmus an Änderungen der
Topologie des Netzes und des Datenverkehrs an.
Der "Heiße-Kartoffel-Algorithmus"
(Hot-Potato-Algorithmus) geht dabei folgendermaßen vor:
Wenn ein Paket ankommt, versucht
der Knoten, es so schnell wie möglich loszuwerden, indem
er es an die kürzeste Ausgangs-warteschlange anhängt.
Genauer gesagt, zählt der Knoten bei der Ankunft jedes neuen
Datenpakets die Anzahl der Datenpakete jeder Warteschlange,
um das gerade eingetroffene Datenpaket an die kürzeste Warteschlange
anzuhängen, wobei das Ziel der Warteschlange nicht beachtet
wird. Einzige Einschränkung hierbei ist, daß das
gerade eingetroffene Datenpaket nicht an die Warteschlange zu
dem Knoten angehängt wird, von dem das Datenpaket gerade
gekommen ist.
Abb. 6 zeigt eine Momentaufnahme
des Innenlebens eines Knotens mit vier Ausgabe-Warteschlangen,
entsprechend der vier Ausgangsleitungen. In jeder Warteschlange
stehen Pakete zur Übertragung an. In diesem Beispiel ist
die Warteschlange zu I die kürzeste mit nur einem Paket.
Der Hot-Potato-Algorithmus würde das neue Datenpaket in dieser
Schlange ablegen, sofern es nicht vom Knoten I kam.
Abbildung 6 - Warteschlangen innerhalb
eines Knotens
3.2 Abwandlungen
Eine Variation des Hot-Potato-Algorithmus
ist eine Kombination mit statischer Leitwegbestimmung. Kommt ein
Datenpaket an, so betrachtet der Knoten sowohl die statische Gewichtung
als auch die Warteschlangenlänge in Betracht. Es gibt nun
mehrere Möglichkeit der Entscheidungsfindung:
Man kann die beste statische
Wahl nehmen, wenn ihre Länge nicht einen bestimmten Wert
überschreitet. Genauso gut ist die Wahl der kürzesten
Schlange denkbar, wenn ihre Gewichtung nicht zu niedrig ist. Eine
weitere andere Möglichkeit ist, die Leitungen nach ihrer
statischen Gewichtung und gleichzeitig nach ihrer Länge zu
bewerten und sich dann für die Leitung mit der besten Gesamtwertung
zu entscheiden. Auf jeden Fall sollte der ge-wählte Algorithmus
die Eigenschaft haben, bei geringerer Aus-lastung des Systems
die Leitung mit der größten statischen Gewichtung
zu wählen, bei Bildung einer Schlange an dieser Leitung,
die Daten auf weniger belastete Leitungen zu verteilen.
[Anfang]
[Inhaltsverzeichnis] [Weiter]