Rechnernetze

Barans heuristische Methode

Ein anderer Algorithmus zur Leitwegbestimmung, der ebenfalls von Baran entwickelt wurde, wird als heuristische Methode (backward learning, Rückwärtslernen) bezeichnet. Die Kernidee dieses Algorithmus besteht darin, daß jeder Knoten aus den weiterzuleitenden Nachrichten Information über den bisherigen Weg der Nachricht gewinnen sollte. Eine einfache Implementierungsmöglichkeit besteht darin, daß eine Nachricht neben der Information über ihren Quellknoten auch einen Zähler erhält, in dem die Anzahl der bereits passierten IMPs angegeben ist. Damit ist es den IMPs möglich, aus den Knotenzählern den Abstand zu dem Quellknoten zu berechnen. Besitzt ein empfangenes Paket den Wert 1, stammt das Paket von dem Nachbarknoten am anderen Ende der Verbindungsleitung, auf der das Paket eingegangen ist. Trifft eine Nachricht ein, deren Knotenzähler einen geringeren Wert als der bisher eingetragene besitzt, wird der alte Wert durch den neuen überschrieben; durch die Verarbeitung und Speicherung der so erhaltenen Information lernt ein Knoten das ganze Netz und die Entfernung zu den anderen Knoten kennen.

Dieses Verfahren funktioniert nach einer bestimmten Einschwingphase sehr gut, besitzt jedoch den Nachteil, nur Verbesserungen des Netzwerks zu erlernen. Fällt ein Knoten aus oder treten Überlastsituationen auf, so besteht keine Möglichkeit, auf diese neue Situation zu reagieren. Allerdings gibt es Ansätze, diese Nachteile des Rückwärtslernens auszugleichen, indem alle Knoten veranlaßt werden, ihre Information nach einer bestimmten Zeit zu vergessen, und die Topologie- und Abstandsinformation neu zu erlernen. Während der Einschwingphase ist der Algorithmus jedoch weit von einer optimalen Wegeermittlung entfernt, so daß eine zu häufig durchgeführte Erneuerung der Information zu völlig instabilen Routingentscheidungen führt. Werden die Tabellen hingegen nur sehr selten gelöscht, ist der Anpassungsprozeß an eine veränderte Netztopologie in der Regel zu langsam. Ein weiterer wesentlicher Nachteil dieses Verfahrens besteht darin, daß von einer symmetrischen Leitungsbelastung in beide Übertragungsrichtungen ausgegangen wird. Das kann jedoch in den meisten Fällen nicht vorausgesetzt werden.