Rechnernetze
Home Nach oben

Das Heiße-Kartoffel-Verfahren

Eines der einfachsten Verfahren ist das 1964 von Baran entwickelte sogenannte Heiße-Kartoffel-Verfahren (hot-potato-algorithm).

Das Verfahren mit diesem sehr intuitiven Namen basiert auf dem Konzept, eine weiterzuleitende Nachricht so schnell wie möglich wieder loszuwerden. Deshalb wird die Nachricht auf jene Ausgangsleitung weitergegeben, in deren Warteschlange sich die wenigsten Aufträge befinden, wobei es völlig unerheblich ist, wohin diese Ausgangsleitung führt. Da nach diesem Verfahren gelenkte Nachrichten u.U. niemals ihren Bestimmungsknoten erreichen, wird in der Regel eine Variante dieser Strategie mit einer stärkeren Zielorientierung eingesetzt. Sie ist eine Kombination aus dem Heiße-Kartoffel-Verfahren und der statischen Leitwegbestimmung. Zur Durchführung werden für die einzelnen Zielknoten die Ausgangsleitungen gemäß einer Zielrichtung angeordnet und eine Bewertung auf der Basis von Wegetabellen vorgenommen. Die Auswahl einer mehr oder weniger zum Ziel führenden Ausgangsleitung, die durch die Wegetabellen festgelegt ist, erfolgt nach der Methode des Heiße-Kartoffel-Verfahrens.

Das Heiße-Kartoffel-Verfahren bringt für den Benutzer das Problem mit sich, daß die lokale Minimierung der Knotenverweilzeit zu einer erheblichen Verlängerung der Transportzeit führen kann. Ein noch gravierenderes Problem bei Anwendung dieses Verfahrens besteht darin, daß es in Hochlastsituationen fast zwangsläufig zu Blockaden innerhalb des Netzes führt, da auch dann noch Nachrichten angenommen werden können, wenn der Weg zum Ziel bereits verstopft ist.

Eine andere Verfeinerung des Heiße-Kartoffel-Verfahrens wurde 1978 von Jolly und Adams vorgestellt. Es beruht darauf, daß für jede Ausgangsleitung eine maximale Pufferbelegung festgelegt wird; diese maximale Pufferbelegung dient als Grenzwert für die Annahme von Nachrichten. Darüber hinaus darf die eigentliche Grundidee des Heiße-Kartoffel-Verfahrens – die mehr oder weniger willkürliche Auswahl einer Verbindungsleitung – nicht mehr in den Nachbarknoten der Senke angewendet werden. Die Nachrichten sind hier solange zwischenzuspeichern, bis die direkte Verbindung zum Zielknoten wieder benutzt werden kann.