Rechnernetze
Home Nach oben

Open Shortest Path First (OSPF)

Das OSPF ist ein von der Internet Engineering Task Force (IETF) entwickeltes Routingprotokoll, das auf einem hierarchischem Link State-Protokoll beruht. Im Gegensatz zum RIP-Protokoll unterstützt es gleichzeitig mehrere Verbindungswege gleicher Kosten zu einem Zielnetz und ist in der Lage, den auftretenden Datenverkehr über verschiedene Verbindungswege zu übertragen. Die besonderen Vorzüge des OSPF-Protokolls liegen in seiner sehr schnellen Konvergenz und in der sehr sparsamen Verwendung von Bandbreite bei der Erstellung neuer Routingtabellen. OSPF besitzt darüber hinaus einige interessante Eigenschaften, die es von anderen Verfahren zur Wegeermittlung unterscheidet. Es unterstützt die Authentisierung, das TOS-Routing (TOS = Type of Service; Routing, bei dem die Auswahl einer Metrik durch die Auswertung des TOS-Eintrags in einem Datagramm vorgenommen wird) sowie die Aufteilung des Autonomous Systems in Teilnetze, die Areas genannt werden.

Zur Beschreibung der Arbeitsweise des OSPF Protokolls soll das folgende Beispielnetz verwendet werden, das dem RFC 1247 entnommen ist. Die durchgezogenen Linien kennzeichnen Verbindungen innerhalb des Autonomous Systems; gestrichelt eingezeichnete Linien sind Verbindungen, die aus dem Autonomous System herausführen.

OSPFAREA.WMF (17934 Byte)

Die Grundlage für die Arbeitsweise des OSPF-Routingprotokolls bildet die Topologie-Datenbank, die gemeinsam von den einzelnen Routern aufgebaut wird. Dazu überträgt (flutet) jeder Knoten die Information seiner lokalen Sicht (seine Interfaces und die erreichbaren Nachbarn) zu allen anderen Knoten im Netzwerk. Mit dieser Information kann dann jedes einzelne Gateway einen Baum aufbauen, der die kürzesten Wege zu allen erreichbaren Knoten enthält. Die Wurzel des Baumes ist der Router selbst, der für den Aufbau des Baums den bereits in den vorhergehenden Abschnitten beschriebenen Shortest Path Algorithmus verwendet (im Bild ist der Shortest Path Tree des Routers 6 dargestellt).

SPFBAUMROUTERRT6.WMF (21130 Byte)

Mit Hilfe des Baums, der die kürzesten Wege zu jedem Netzwerk bzw. jedem Endsystem beschreibt, wird dann eine Tabelle erstellt, in der die Routinginformation zusammengefasst ist. Für die Weiterleitung von Datagrammen werden dabei nur das Zielnetz, der nächste Knotenrechner und die Distanz benötigt; die Beschreibung des kompletten Weges ist nicht erforderlich. Zusätzlich wird nach dem Aufbau des Baums die externe Routinginformation untersucht, die von anderen Autonomous Systems (und einem evtl. anderen IGP) stammt und von Routern, die an der Grenze zu einem anderen Autonomous System liegen, in das Autonomous System übertragen wird. Diese Information wird unverändert im bzw. durch das Autonomous System übertragen.

Generell unterscheidet OSPF zwei Arten von Routen mit externen Metriken (Metriken von anderen Autonomous Systems): Typ 1 Metriken sind externe Metriken, die äquivalent zur Link State Metrik sind; sie werden bei der Berechnung von Pfaden wie interne Metriken behandelt. Bei Typ 2 handelt es sich um Metriken, deren Kosten in jedem Fall höher sind als die Kosten innerhalb des Autonomous Systems. Aus diesem Grund wird für Typ 2 Metriken kein Vergleich der Kosten von internen Routern durchgeführt, sondern der Router mit den geringsten Kosten zum externen Netz benutzt. Für die Berechnung einer externen Route mit einer Typ 1 Metrik (z.B. der Weg zum Netz 12 über Router 5 bzw. Router 7) werden jedoch die Kosten der internen Metrik und der externen Metrik addiert; anschließend wird ein Kostenvergleich angestellt und die günstigste Route ausgewählt. Im Beispiel ergeben sich für die beiden Routen folgende Kosten für den Weg von Router 6 zum Netz 12: 7+1+2 für den Weg über Router 7 und 6+8 für den Weg über Router 5. Damit wird der Weg über Router 7 gewählt und in die Routingtabelle eingetragen.

Die folgende Tabelle zeigt interne und externe Teile der Routingtabelle von Router 6:

Destination

Next Hop

Distance

N1

RT 3

10

N2

RT 3

10

N3

RT 3

7

N4

RT 3

8

N6

RT 10

12

.

.

.

.

.

.

N12

RT 10

10

N13

RT 5

14

Bei der bisherigen Betrachtung des OSPF-Routings wurde von der Annahme ausgegangen, dass nur ein Weg zu einem Endsystem existiert. Eine OSPF-Implementierung muss jedoch in der Lage sein, mehrere Einträge zu dem gleichen Endsystem zu verwalten, die bei der Berechnung der unterschiedliche Metriken für verschiedene Type of Service-Einträge (TOS) berücksichtigt werden. In diesem Fall wird für die einzelnen TOS-Werte jeweils ein eigener Shortest Path Tree erstellt, dessen Werte in eine gemeinsame Routingtabelle aufgenommen werden. Diese zweifellos sehr nützliche Eigenschaft des Protokolls birgt jedoch die Gefahr von sehr großen Routingtabelle in sich, die für eine schnelle Auswahl eines Weges nicht mehr geeignet sind. Auf Grund dieser Problematik erlaubt das Protokoll eine Reduktion auf das sogenannte TOS-0-only-Routing, bei dem für alle TOS-Werte eine einheitliche Routingtabelle verwendet werden kann. Router, die dieses Verfahren verwenden werden als TOS-0-only-Router bezeichnet, können jedoch gemeinsam mit anderen Routern, die mehrere Einträge verwalten, in einem Autonomous System arbeiten.

Eine andere Möglichkeit, die Größe der Routingtabellen zu begrenzen, besteht in der Aufteilung des Autonomous Systems in sogenannte Areas, die aus einer Ansammlung von benachbarten Endsystemen, Netzwerken und den Routern mit Schnittstellen zu einem dieser Netzwerke bestehen. Sie verwalten in ihren Routern eine eigenständige Kopie des OSPF-Protokolls und erzeugen aus diesem Grund auch eine eigene Topologie-Datenbank sowie einen Shortest Path Tree. Diese Technik erlaubt in großen Autonomous Systems eine erhebliche Reduktion der Routingtabelle, die zusammen mit der Abgeschlossenheit dieser Bereiche gegenüber der Außenwelt zu einer höheren Konvergenz und zu sichereren Routingtabellen führt. Darüber hinaus ist es durch diese Technik möglich, daß eine Änderung der Topologie in einem Teil des Netzes nicht das Gesamtnetz belastet, und so das OSPF Protokoll mit relativ wenig Overhead arbeiten kann.

Die Übertragung von Datagrammen zwischen verschiedenen Areas verläuft in drei Schritten: Im ersten Schritt wird die Übertragung zwischen dem Endsystem und dem sogenannten Area Border Router durchgeführt, der dann die Weiterleitung der Daten über das Backbone (Verbindungsweg zwischen Areas) zur Area des Zielsystems durchführt. Die Daten werden dort von einem Area Border Router empfangen und dem Endsystem zugestellt. Die Wegewahl zwischen unterschiedlichen Areas verläuft analog zur Wegewahl zwischen verschiedenen Autonomous Systems.

AREAS.WMF (21380 Byte)

Eine andere Besonderheit des OSPF-Protokolls ist die Unterstützung von IP-Netzen mit untergliederten Subnetzen. Zu diesem Zwecke versieht das Protokoll jede Route mit einer Subnetz-Maske, die einen bestimmten Bereich von Adressen einer bestimmten Route zuordnet. So können durch das Adress-Masken-Paar [0xffff0000, 134.106.0.0] mit einem Eintrag in der Routingtabelle die Wege zu den Netzen im Bereich von 134.106.0.0 bis 134.106.255.255 propagiert werden. Ist jedoch das Netzwerk weiter unterteilt, so dass z.B. ein Router A alle Datagramme mit einer Zieladresse im Bereich von 134.106.0.0 bis 134.106.127.255 zum Router B und alle Datagramme mit der Zieladresse im Bereich von 134.106.128.0 bis 134.106.255.255 zum Router C weiterleiten muss, so kann dies durch den Eintrag der beiden Adreß-Masken-Paare [0xffff1000, 134.106.128.0] und [0xffff1000, 134.106.0.0] in der Routingtabelle realisiert werden.

Ein weiteres Merkmal von OSPF ist der Einsatz eines Authentisierungsmechanismus. Die Authentisierung erfolgt mit Hilfe eines Authentication Type Fields (AuType) sowie einem 64-Bit Datenfeld, die Bestandteile des OSPF Protokoll-Formats sind. Hier kann z.B. durch die Verwendung des AuType = 1 ein einfacher Passwort-Mechanismus als Sicherheit implementiert sein oder durch den Eintrag AuType = 0 die Authentisierung ausgeschaltet werden. Die Authentisierung stellt sicher, dass keine Routen in das Netzwerk eingebracht werden, die nicht von authorisierten Routern stammen.

Zusammenfassend kann gesagt werden, dass es sich beim OSPF-Protokoll um ein sehr komplexes und modernes Routing-Protokoll handelt, dessen Merkmale in diesem Rahmen nicht vollständig behandelt werden können. OSPF eignet sich insbesondere für den Einsatz in großen bis sehr großen Netzwerken. In kleineren Netzen sollte es aufgrund seiner Komplexität nicht angewendet werden.