Übung

Das endgültige Festlegen von Routen zu besten Pfaden durch das Netz wird Konvergenz genannt. Distanzvektoralgorithmen sind als eine einfache Technik sinnvoll, mit der Router gemeinsam kürzeste Pfade berechnen können, doch sie haben in der Praxis einen großen Nachteil:

Der Algorithmus führt zwar zur richtigen Lösung, schafft das aber nur sehr langsam. Insbesondere reagiert er zwar schnell auf gute Nachrichten, aber sehr träge auf schlechte. Nehmen wir an, der beste Weg eines Routers zu Ziel X ist lang. Meldet Nachbar A beim nächsten Informationsaustausch plötzlich eine kürzere Übertragungszeit zu X, dann schaltet der Router einfach um, indem er Leitung A verwendet, um Datenverkehr an X zu senden. Die gute Nachricht wird mit einem einzigen Austausch im Vektor verarbeitet.

Die guten Nachrichten verbreiten sich in einer Geschwindigkeit von einer Teilstrecke pro Austausch. In einem Netz, dessen längster Pfad eine Länge von N Teilstrecken hat, tauschen alle innerhalb von N die Nachricht über neu zugeschaltete Verbindungen und Router aus.

S chlechte Nachrichten:

Aus dieser Abbildung kann man ersehen, warum sich die schlechte Nachricht so langsam verbreitet: Kein Router hat je einen um mehr als 1 höheren Wert als der Minimalwert aller seiner Nachbarn. Allmählich arbeiten sich alle Router ihren Weg in Richtung Unendlichkeit, aber die Zahl der dafür erforderlichen Übertragungen hängt vom numerischen Wert, der für die Unendlichkeit verwendet wird, ab. Aus diesem Grund sollte die Unendlichkeit auf den längsten Pfad plus 1 gesetzt werden. Die Bezeichnung für dieses Problem kommt nicht völlig überraschend: Count-tolnfinity- Problem.

Keine dieser Heuristiken funktioniert jedoch - trotz der klangvollen Namen - gut in der Praxis. Das Hauptproblem ist, dass wenn X Router Y mitteilt, dass er irgendwo einen Pfad hat, Y keine Möglichkeit hat festzustellen, ob er selbst Teil dieses

Pfads ist.

——

Wenn sich Topologie verändert (z.B. Ausfall oder Blockade), passen sich die Routing- Tabellen der einzelnen Knoten an. Die Kommunikationskette kann allerdings so groß sein, dass bis jeder Knoten sich aktualisiert hat, das Problem weshalb die Aktualisierung angestoßen wurden, bereits behoben ist

→ Grund wieso das in der Netzwerktechnologie nicht mehr eingesetzt wird.

Aktualisierung zu kompliziert, dauert zu lange und viel zu viele Pakete und Berechnungen müssen durchgeführt werden.

In der Logistik ist das allerding nicht ein so großes Problem (Flexförderer) wie in der Netzwerktechnik. Weil die Topologie hier nur alle paar Wochen/Monate verändert wird. Ein Fließbandsystem wird nur selten umgebaut und selbst wenn es mal Veränderungen gibt, ist die Berechnung deutlich schneller, da die Informationskommunikation zwischen den Knoten eine ganz andere ist als was das von verschicken von Paketen bedeutet.

Das Durchkommunizieren einer Aktualisierung der Routing-Tabelle ist erledigt bevor das Paket angekommen ist. Das Netz kann dann die nächste vernünftige Entscheidung treffen.

Distanzvektoralgorithmen wurden im ARPANET bis 1979 eingesetzt, dann wurden sie durch Link-State-Routing ersetzt. Der Hauptgrund für die Ablösung war, dass der Algorithmus nach einer Änderung der Netztopologie häufig zu langsam war (aufgrund des Count-to-Infinity-Problems). Daher wurde auf einen völlig neuen Algorithmus umgestellt, der Link-State-Routing (Routing nach dem Verbindungszustand) heißt.

Das Konzept von Link-State-Routing ist ziemlich einfach und besteht aus fünf Teilen.

Jeder Router muss die folgenden Schritte ausführen, damit das Routing funktioniert:

1. Die Nachbarn und deren Netzadressen ermitteln

2. Die Entfernungs- oder die Kostenmetrik zu jedem seiner Nachbarn festlegen

3. Ein Paket zusammenstellen, in dem alles steht, was er bisher gelernt hat

4. Dieses Paket an alle anderen Router senden und von allen Routern Pakete empfangen

5. Den kürzesten Pfad zu allen anderen Routern berechnen

• Maschinengruppen werden mit Material versorgt

• Aufträge werden von Station zu Station transportiert

• FTS bzw. AGVs wickeln den Transport ab

• Zuordnung von Transportaufträgen zu Fahrzeugen muss getroffen werden

• Es kann sinnvoll sein, die Reihenfolge auf den Maschinen mit den Transportern abzustimmen

A: Das System betrachtet bei der Entscheidung nur den aktuellen Zustand und trifft die Entscheidung sofort und direkt. Einer der drei Fahrzeuge könnte eventuell in wenigen Sekunden seinen Auftrag beenden und wäre theoretisch besser für den Auftrag geeignet als einer der zwei zu Verfügung stehenden Fahrzeugen. Kein Blick in die Zukunft. Es gibt allerdings erweiterte Regeln die genau das tun (look ahead).