Link-State-Protokoll

Protokolle der Link-State-Familie, sind das Gegenstück zu den Distanzvektorprotokollen und werden auch Shortest Path First (SPF) genannt, da sie den Shortest Path First - Algorithmus von Dijkstra verwenden. Die Link-State-Protokolle verwenden eine "Karte" der Netzwerkstruktur, welche in gewissen Ständen aktualisiert wird. Diese Karte wird von jedem Knoten (z.B.Router) in einer Datenbank lokal gespeichert und aktuell gehalten.

Vertreter dieser Protokoll-Familie ist z.B. OSPF.

Link-State-Datenbank

Die Datenbank eines Link-State-Knotens entspricht einer "topologischen Karte" des Netzwerks.

So wird z.B. dieses Netzwerk als Datenbank wie folgt dargestellt:

A -- 1 -- B -- 2 -- C
|         |        /
3         4       /
|         |      /
D -- 6 -- E -- 5

Von	Nach	Verbindung	Entfernung
A	B	1	1
A	D	3	1
B	A	1	1
B	C	2	1
B	E	4	1
C	B	2	1
C	E	5	1
D	A	2	1
D	E	6	1
E	B	4	1
E	C	5	1
E	D	6	1

Eine Verbindung von einem Knoten des Netzwerks zu einem anderen Knoten entspricht hier immer einem Datensatz. Diese Datensätze können in Abhängigkeit zu dem verwendeten Protokoll auch abweichen, so ist z.B. als Metrik Kosten für eine Verbinding oder die Geschwindigkeit der Verbindung. Durch diese einfache Struktur der Daten ist es einem Computer sehr effizient möglich die Routen zu berechnen. In dem hier gegebenen Beispiel würde er z.B. für eine die Route von A nach C über B errechnen, da er hier die Gesamtkosten mit 2 hätte.

Flooding-Protokoll

Da die Datenbanken der Knoten aktuell gehalten werden müssen, müssen die Informationen über die Änderungen im Netzwerk an alle Teilnehmer des Netzwerkes gesendet werden. Für diesen Zweck wird ein sogenanntes Flooding-Protokoll verwendet. Sobald ein Knoten merkt, dass sich seine Daten geändert haben sendet er ein solches Paket um seine Nachbarn über die Änderung zu informieren. Fällt z.B. eine Verbindung weg, wird diese Strecke mit der Entfernung (Metrik) unendlich gepeichert. Diese Art der Verteilung ist sehr effizient, jedoch kann ein veraltetes Paket die kompletten Datenbanken inkonsitent machen. Um dem entgegenzuwirken wurde den Datenbanken und Paketen ein weiterer Parameter hinzugefügt, welcher durch eine Nummer oder Zeitstempel repräsentiert werden kann. Mit diesem Parameter kann erkannt werden, ob der Datensatz aus dem Paket älter oder neuer als der aus der Datenbank ist.

Wird ein Paket mit Updates erhalten wird ein relativ einfacher Algorithmus ausgeführt:

1. Daten aus dem empfangenen Paket extrahieren
2. Suchen der Daten in der Datenbank
3. Wenn die Daten nicht in der Datenbank enthalten ist, wird sie hinzugefügt
4. Wenn die Daten aktueller sind (größere Nummer der Daten als die aus der Datenbank), wird die Datenbank aktualisiert
5. Wenn die Daten nicht aktueller sind, werden sie verworfen und die Daten aus der Datenbank über die Eingangsschnittstelle versendet
6. Wenn beide Daten identisch sind, werden sie auch verworfen

Jedes mal wenn sich Änderungen in der Datenbank ergeben, werden diese mit einem Floodig-Protokoll-Paket an die Nachbarn versendet.

A   xxx   B -- 2 -- C
|         |        /
3         4       /
|         |      /
D -- 6 -- E -- 5

Wenn z.B. die Verbindung 1 zwischen A und B wegfällt, versendet A ein Paket an D:

Von A, nach B, Verbindung 1, Entfernung = unendlich, Nummer = 2

D wird dieses Paket empfangen und seine Datenbank damit abgleichen, wodurch die 1.Verbindung auf inf gesetzt wird. Anschließend sendet D die Nachricht an E, der wiederum seine Datenbank aktualisiert und die Informationen an B und C. Diese aktualisieren ihre Datenbanken auch und versenden ihre Nachrichten den jeweils anderen. Dann merken B und C jedoch, dass diese Daten schon in der Datenbank enthalten sind und verwerfen sie.

Jetzt haben sich die Informationen über die Verbindung von A nach B durch das gesamte Netzwerk verbreitet, gleichzeitig werden auch die Informationen über die zusammengebrochene Verbindung von B nach A übers Netzwerk verbreitet. Anschließend sieht die Tabelle wie folgt aus:

Von	Nach	Verbindung	Entfernung	Nummer
A	B	1	inf	2
A	D	3	1	1
B	A	1	inf	2
B	C	2	1	1
B	E	4	1	1
C	B	2	1	1
C	E	5	1	1
D	A	2	1	1
D	E	6	1	1
E	B	4	1	1
E	C	5	1	1
E	D	6	1	1

Da Netzwerke sehr lange laufen kann nicht davon ausgegangen werden, dass die Nummern der Pakete immer größere Zahlenwerte enthalten. Es muss daher eine Festlegung vorhanden sein, wann eine Nummer kleiner oder größer ist. Oftmals wird eine Nummerierung Modulo N verwendet, so ist z.B. der Wert nach 99 nicht 100 sondern 0 wenn (99+1) mod 10. Da die Nummern normalerweise relativ langsam wachsen, kann man davon ausgehen das ein Wert zudem nur sehr wenig hinzugefügt werden muss um den anderen Wert zu erreichen. Bei OSPF wurde für diesen Fall der sogenannte Lollipop-Sequenzraum eingeführt, damit die eindeutige Zuordnung der Nummern geschehen kann.

Damit die Karte immer aktuell ist, wird ein Eintrag wird aus der Datenbank entfernt, wenn er nicht nach einer bestimmten Zeit aktualisiert wurde.

Metriken

SPF-Protokolle unterstützen meistens mehrere Metriken, wodurch auch unterschiedliche Routen zustande kommen können. Mögliche Metriken sind z.B.

• Datendurchsatz
• Verzögerung
• Kosten
• Zuverlässigkeit

Je nach verwendeter Metrik kann eine Verbindung von zwei Knoten unterschiedliche Routen haben, z.B. ist eine Funkstrecke günstiger als eine Strecke über Kabel. Jedoch hat sie eine höhere Verzögerung und einen schlechteren Durchsatz. So gibt es nach der Durchsatz-Metrik eine andere Route als mit der Kosten-Metrik. Durch diese Gegebenheit muss darauf geachtet werden, dass alle Knoten die gleichen Metriken verwenden, da es sonst zu Schleifen kommen kann, wenn z.B. ein Router die Kosten und der andere den Durchsatz nimmt. Alternativ kann auch eine Vorgabe für die Pakete festgelegt werden, wie es z.B. OSPF macht.

Externe Routen

Damit die Datenbanken nicht zu groß werden, werden Netzwerke in Bereiche unterteilt die über Gateways erreichbar sind. Durch diese Abgrenzung können die Datenbanken für die internen Routen klein gehalten werden.

Vorteile

Die Vorteile eines Link-State-Routing-Protokolls gegen über eden Distanzvektorprotokollen sind:

1. Schnelle Konvergenz, ohne dass sich Schleifen bilden können
2. Unterstützung von präzisen Metriken, gegebenenfalls auch mehrerer Metriken
3. Unterstützung von mehreren Pfaden zu einem Ziel
4. Getrennte Darstellung von externen Routen

Weiterführende Artikel

• OSPF

Literatur

• Routing im Internet - Christian Huitema - Prentice Hall - ISBN 3-8272-9526-2