Source-Tree Adaptive Routing Protocol

Grundprinzip und Aufbau

Das Source-Tree Adaptive Routing Protocol (STAR) war das erste proaktive Routing-Protokoll, das mit Link-State-Informationen arbeitete. Ein proaktives Routing-Protokoll hält Informationen über die erreichbaren Wege bereits vor einer konkreten Datenübertragung bereit. STAR verwendet außerdem erstmals das LORA-Prinzip (Least Overhead Routing Approach). Dabei werden gefundene Pfade so lange wie möglich beibehalten, damit möglichst wenige Kontrollnachrichten entstehen.

STAR wählt deshalb nicht grundsätzlich die aller kürzesten Pfade. Der Verzicht auf unnötige Pfadänderungen soll den Austausch von Kontrollinformationen verringern. Alle Knoten besitzen feste Adressen. Dadurch müssen ihre Informationen nicht ständig durch neue Aktualisierungen angepasst werden. Eine Aktualisierung besteht aus mindestens einem LSU (Link-State Update), also einer Nachricht über den Zustand von Verbindungen.

Bei der Initialisierung des Netzes entstehen source-trees. Sie stellen die Verbindungen eines Knotens zu seinen Nachbarn dar. Anschließend sendet jeder Knoten seinen eigenen source-tree an alle benachbarten Knoten. Diese aktualisieren damit ihre gespeicherten Informationen. Aus dem eigenen source-tree und den empfangenen source-trees kann jeder Knoten einen Topologiegraphen aufbauen, der das komplette Netz enthält.

Aktualisierung von Verbindungsinformationen

Aktualisierungsinformationen werden als Broadcast, also an alle benachbarten Knoten, versandt und mit einer Nummer versehen. Den Zähler erhöht nur der Sender. Ein LSU gilt als gültig, wenn seine Nummer höher ist als die zuletzt gespeicherte Nummer für dieselbe Verbindung. Dadurch müssen LSUs nicht regelmäßig beziehungsweise periodisch erneut gesendet werden.

Eine Aktualisierung wird gesendet, wenn:

• ein Empfänger nicht mehr erreichbar ist,
• ein neuer Empfänger gefunden wurde,
• es den Anschein hat, dass sich Schleifen gebildet haben,
• die Metrik einer Verbindung den Maximalwert überschreitet.

Die Metrik ist der für eine Verbindung verwendete Bewertungswert. Ob ihr Maximalwert überschritten wurde, kann durch den Vergleich des empfangenen source-trees mit dem eigenen source-tree festgestellt werden.

Regeln zur Vermeidung von Schleifen

Für einen Router R gelten besondere Regeln, wann er Aktualisierungsinformationen senden muss. Eine Aktualisierung wird gesendet, wenn:

• ein Pfad offenbar in einer Schleife endet,
• ein neu ausgewählter Nachfolger von R eine höhere Adresse besitzt,
• die Entfernung zu einem Empfänger über den ausgewählten Nachfolger größer ist als über den alten Nachfolger.

Feste Routeradressen spielen dabei eine wichtige Rolle. Muss Router R einen neuen Nachfolger auswählen, nimmt er immer einen Router mit einer höheren Adresse als seiner eigenen. Anschließend wird eine Aktualisierung versandt. Diese Regel kann jedoch nicht angewendet werden, wenn es keinen Router mit einer höheren Nummer gibt. Dann können andere Informationen, insbesondere die Metrik oder der erkannte Schleifenverdacht, eine Aktualisierung auslösen.

Beispiel für eine entstehende Schleife

Erhält Router R eine Aktualisierung von seinem Nachbarn X, aktualisiert er zunächst seinen source-tree. Danach wird geprüft, für welche Empfänger X über R gehen muss und ob R über einen Nachbarn N gehen muss, um denselben Empfänger zu erreichen. Auf diese Weise lassen sich widersprüchliche Wege und mögliche Schleifen erkennen.

Ein Beispiel beginnt mit dem Ausfall der Verbindung (c,d). Der source-tree von c wird angepasst. Zunächst ist keine Aktualisierung aufgrund der Regel für einen neuen Nachfolger nötig, weil der Nachfolger eine niedrigere Nummer als Router c besitzt. Router c kann daher keinen Router mit einer höheren Nummer auswählen. Trotzdem wird sofort eine Aktualisierung gesendet, weil die Metrik zu f erhöht wurde.

Router a korrigiert daraufhin seinen source-tree. Fällt anschließend auch die Verbindung (b,e) aus, sendet b eine Aktualisierung mit der Metrik (b,e)=Unendlich. b weiß, dass auch (c,d) ausgefallen ist und deshalb d, e und f nicht mehr erreichbar sind. Ohne diese Korrektur versucht b, Router d über a und c zu erreichen, während c d nur über b erreichen kann. Dadurch entsteht eine Schleife: b verweist für den Weg zu d auf c, c verweist für denselben Weg auf b. Das Beispiel zeigt, dass STAR Pfade möglichst beibehält, bei erkannten Erreichbarkeits- oder Metrikänderungen aber gezielte Aktualisierungen zur Korrektur und Schleifenvermeidung verschickt.