OSPF
Open Shortest Path First

Dynamisches Routing mit OSPF
Was zeichnet Link-State-Routing-Protokolle (LSR-Protokolle) aus? Fast alle basieren auf den Open-Shortest-Path-First-Algorithmus nach Dijkstra. Dijkstra ist ein Niederländischer Mathematiker, der diesen Algorithmus entwickelt hat. Es geht darum aus einem Netzwerk den kürzesten Weg zwischen zwei "Knoten" zu finden. 

Die Bezeichnung “Open” bedeutet, das der Quellcode frei verfügbar, also open-source ist. Häufig wird angenommen, dass der kürzeste Weg erst einmal geöffnet werden muss. Diese Annahme ist aber nicht richtig.

Was ist eigentlich ein Link-State


Link steht für Verbindung zwischen zwei Router-Interfaces. Jeder Link hat einen bestimmten Zustand, den der Administrator anhand seiner geplanten Netztopologie vergeben hat.
Der Zustand einer Schnittstelle eines Routers, als State bezeichnet, beinhaltet alle notwendigen Informationen der internen Konfiguration.

Dazu gehören die Informationen zum angeschlossenen Netzwerk, welches mit der Netzwerkadresse angegeben wird, genauso wie die IP-Adresse der Schnittstelle.
Die Metrik wird bei OSPF auch als Cost of Link bezeichnet. Diese ist Abhängig von z.B. der Bandbreite oder vom Typ der Verbindung. Wichtig ist darüber hinaus die Information ob es Nachbarrouter, sog. Neighbours, gibt die in diesem Netz angebunden sind bzw. die über diese Schnittstelle erreicht werden können.
Der Link-State einer Routerschnittstelle beinhaltet also das Netz, die IP-Adresse, die Cost und die Nachbarrouter.

Die Link-State-Informationen werden zu Beginn der Startphase des Routers ausgetauscht.
Das Ziel beim OSPF ist es Nachbarschaftsbeziehungen, die “Adjacency”, aufzubauen.
Bei Konvergenz werden in regelmäßigen Intervallen “Hello”-Pakete versendet um die Nachbarschaftsbeziehung zu überprüfen. Im sogenannten Hello-Intervall dienen die Hello-Pakete als Keep-Alive-Information um die Erreichbarkeit der Nachbarroutern zu sichern.
Bei drei ausbleibenden Hello Paketen wird angenommen, dass die Verbindung zum Nachbarrouter ausgefallen ist.

Beim ersten Start kennen die Router nur ihre eigenen Link-States. Mit der ersten Update Information werden die gesamten Informationen aus den Link State der Router in ein Link-State-Packet (LSP) eingetragen und auf die angeschlossenen Netze versendet. Man spricht vom floading oder fluten der Informationen.
Jeder Router baut seinen eigenen Link-State-Packet und flutet die Informationen auf das Netz an alle Nachbarn. Diese speichern diese Informationen dann in ihre eigen Link-State-Datenbank. Die neuen Informationen werden dann in weiteren LSP eingetragen und an die jeweiligen Nachbarn weitergeleitet, bis alle Router im Netz alle Informationen zu allen Routern haben.

Das führt dazu, dass alle Router im Netz aus ihren Informationen die komplette Netzwerktopologie kennen. Aus diesen Informationen kann dann der Graph der Topologie generiert werden. Mathematisch spricht man bei den Routern von Knoten, wohingegen die Verbindungen und Netzwerke am Rand des LANs als Kanten bezeichnet werden.

Shortest Path First


Mit Hilfe des Shortest-Path-First Algorithmus kann nun der kürzeste Weg zwischen Zwei Routern gesucht und in die Routing Tabelle eingetragen werden. Dieses Verfahren macht jeder Router für sich.

Dabei gilt zu beachten, dass bei OSPF der kürzeste Weg nicht von den Hops abhängt, sondern die “Cost”, also sie Kosten des Netzes berücksichtigt werden, welche wiederum von der Bandbreite zwischen den Netzen abhängig sind.

Kosten von 22 sind schlechter als Kosten von 17 obwohl der Weg, Anzahl der Hops, länger sein könnte.

Zusammenfassen wird der Ablauf wie folgt dargestellt. Zuerst werden alle Informationen der Router verteilt und Nachbarschaftsbeziehungen, Adjacencies, aufgebaut. Wenn die Router alle Informationen haben, kann der kürzeste Weg anhand der eingetragenen Informationen berechnet werden.

Wenn am Netzwerk nichts weiter passiert, dann kommt es zu einer ruhigen Kommunikation auf dem Netz, bei dem dann nur noch vereinzelnd “Hello-Pakete” ausgetauscht werden.
Von außen betrachtet befindet sich das Netzwerk nun in einem konvergenten Zustand. Dies ändert sich sobald ein Router ausfällt, eine Verbindung gestört oder das Netzwerk erweitert wird.

Bei Änderungen an der Netzwerktopologie werden neue Link-State-Protokolle versendet.
Diese Infos werden sofort weitergeleitet. Der Ablauf beginnt von vorne und ein neues Shortest-Path wird berechnet.

Ein Router hält sich streng an den Algorithmus so wie er implementiert wurde.
Bei einem Graphen den kürzesten Weg herauszufiltern ist eigentlich nicht schwer. Wenn man selber von außen auf einen Netzwerkgraphen schaut, dann erkennt man schnell den kürzesten Weg. Aber wie stellt sich das für einen Router dar?
Der Router hat nur seine Informationen aus den Update Informationen, den LSP um daraus einen Shortest-Path zu berechnen.

Das Ziel ist also, ausgehend von einem Knoten unter Zuhilfenahme von nur dem Dijkstra-Algorithmus, in einem Netzwerk den kürzesten Weg zu einem anderen Knoten zu finden.
Die Roter betrachten das Netzwerk als Graph um darauf Shortest-Path-First als “besten” Pfad anzuwenden. Aber wie ist der kürzeste Weg definiert?

Bei Rip ist das klar der "Next Hop", bei OSPF werden die Verbindungen zwischen den Routern mit betrachtet und bewertet. In die Bewertung fließen dann Bandbreite, Ausfallsicherheit und ähnliches mit ein.
Der kürzeste Weg ist demnach nicht immer der mit den wenigsten Hops. Bei OSPF spielt die Bandbreite der Kanten, also der Netze zwischen den Routern eine wesentliche Rolle.
Wenn es mehrere Möglichkeiten gibt, dann wird sich OSPF wahrscheinlich für den schnelleren Weg entscheiden und diesen als Shortest-Path auswählen.



sag es weiter...
>
Cookie Plugin von Real Cookie Banner