Source-Tree Adaptive Routing Protocol

Das Source-Tree Adaptive Routing Protocol (STAR) war das erste proaktive Routing-Protokoll, das mit Link-State Information arbeitete. Außerdem implementierte es erstmals das LORA-Prinzip (Least Overhead Routing Approach; gefundene Pfade so lange wie möglich erhalten, um Kontrollnachrichten zu vermeiden). STAR nutzt nicht die allerkürzesten Pfade, damit unnötige Kontrollnachrichten vermieden werden können. Es werden alle Knoten mit feste Adressen versehen, was den Vorteil hat, dass nicht ständig neue Aktualisierungen der Informationen nötig sind. Diese bestehen aus mindestens einem LSU (Link-State Update).

Bei der Initialisierung des Netzes entstehen source-trees, welche Verbindungen eines Knotens zu seinem Nachbarn darstellen. Der nächste Schritt (= Aktualisierung) besteht im Senden des eigenen source-trees an alle benachbarten Knoten, die den eigenen source-tree damit aktualisieren. So kann jeder Knoten mit seinen eigenen und dem erhaltenen source-tree einen Topologiegraphen aufbauen, der das komplettes Netz enthält.

Aktualisierungsinformationen

Aktualisierungsinformationen werden Broadcast versandt und nummeriert. Dabei wird der Zähler nur vom Sender erhöht. Ein LSU ist gültig, wenn die Nummer höher als die zuletzt gespeicherte Nummer für dieselbe Verbindung ist, was den Vorteil hat, dass LSUs nicht periodisch aktualisiert werden müssen.

Aktualisierungsinformationen werden gesendet, falls

• ein Empfänger nicht mehr erreichbar ist,
• ein neuer Empfänger gefunden wurde,
• es den Anschein hat, dass Schleifen gebildet wurden,
• die Metrik der Verbindungen den Maximalwert überschreitet, was durch Vergleich des empfangenen mit dem eigenen source-tree feststellbar ist.

Verhindern von Schleifen

Zum Verhindern von Schleifen müssen für einen Router [R] folgende Regeln für das Senden von Aktualisierungsinformationen gelten. Er sendet Aktualisierungen, falls

1. ein Pfad in einer Schleife zu enden scheint,
2. ein neuer ausgewählter Nachfolger des Routers [R] eine höhere Adresse hat,
3. die Distanz zum Empfänger über einen ausgewählten Nachfolger größer als zum alten Nachfolger ist.

Beispiele

1. Erhält ein Router [R] eine Aktualisierung vom Nachbarn X, wird sein source-tree aktualisiert. Nächster Schritt ist zu testen, für welche Empfänger Nachbar X über Router [R] gehen muss und ob der Router [R] über Nachbar [N] gehen muss, um denselben Empfänger zu erreichen.
2. Jeder Router hat eine fixe Adresse und wenn ein Router [R] einen neuen Nachfolger suchen muss, nimmt er immer den mit einer höheren Adresse als seiner eigenen. Danach wird eine Aktualisierung versandt.
3. Siehe Bilder.

Illustration (II)–(IV) zeigen die source-trees der gelb markierten Knoten bzw. Router. Wenn Verbindung (c,d) ausfällt, ist der source-tree von c in Abbildung V. Hier ist keine Aktualisierung nötig, da der Nachfolger eine niedrigere Nummer als Router c besitzt. In diesem Fall ist es nicht möglich Regel 2 anzuwenden, da es keinen Router mit einer höheren Nummer gibt. Jetzt fällt Verbindung (b,e) aus. Der source-tree von b ist in Abbildung VI gezeigt und abermals ist keine Aktualisierung nötig, da der Nachfolger eine niedrigere Nummer hat. Um Router d zu erreichen, versucht er über a und c zu senden. Gleichzeitig kennt Router c nur die Route zu d über b. So ist eine Schleife entstanden.

Sofort bei Ausfall von Verbindung (c,d) wird eine Aktualisierung gesendet, da die Metrik zu f erhöht wurde (Abbildung II). Router a korrigiert seinen source-tree in Abbildung III. Wenn nun wiederum Verbindung (b,e) ausfällt, sendet b eine Aktualisierung mit der Metrik (b,e)=Unendlich, da er weiß, dass (c,d) ebenfalls ausgefallen ist und deswegen d, e und f nicht mehr erreichbar sind.

Weblinks

• Quelle dieses Artikels (.pdf) (283 kB)
• englische Beschreibung
• Original-paper
• IETF Memo