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

[Tan88, S.359]

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]

[Abbildungsverzeichnis] [Literaturverzeichnis]