www.net-tex.de

Protokolle zur technischen und logischen Umsetzung der Paketverteilung (Seite ist noch in Bearbeitung!)

1 Routing Information Protocol (RIP)
    1.1 Schritte bei einem Update:
    1.2 Timer
    1.3 Subnetzmasken
    1.4 Default Route
2 Routing Information Protocol 2 (RIP2)
    2.1 Paketformat
3 Open Shortest Path First (OSPF)
    3.1 Hierarchie und Gebiete
        3.1.1 Backbone
        3.1.2 Interne Router
        3.1.3 Area Border Router (ABR)
        3.1.4 Autonomous System Boundary Router (ASBR)
        3.1.5 Stub Area
        3.1.6 Totally Stubby Areas (TSA)
        3.1.7 Not So Stubby Areas (NSSA)
    3.2 Topologische Datenbank
        3.2.1 LSA Typen
        3.2.2 Routen Typen
    3.3 OSPF Paket
    3.4 HELLO Protokoll
        3.4.1 HELLO Paket
        3.4.2 DR/DBR
    3.5 Status der Schnittstellen
    3.6 Verbindungen der Nachbarn
    3.7 Austausch der Datenbank
        3.7.1 DD Paket

1 Routing Information Protocol (RIP) (Index)

RIP ist ein dynamisches Routing Protokoll und generiert daher automatisch Routing Tabellen. RIP verwendet Distance Vector um die billigsten Pfade zu finden, d.h. in der Netzmetrik werden nur die Anzahl der Hops berechnet, nicht aber die direkten Kosten des Hops. Das heißt im Klartext, das ein Pfad über 2 32k-Modems dem über 3 T1-Router vorgezogen wird. Ist die Anzahl der Hops 16, gilt die Route als invalid (count to infinty). RIP ist an sich ein verteilter Prozess, der auf jedem Router konfiguriert werden muss. RIP Router tauschen Updates ihrer Routingtabellen mit den jeweiligen direkten Nachbarn aus. RIP Updates werden in UDP gekapselt und an Port 520 geschickt, in der Regel werden Updates automatisch alle 30 sek verschickt, können aber auch direkt per Broadcast an 255.255.255.255 angefordert werden.

0	8	16	24
Command	Version	genullt
address family identifier		genullt
IP Address
genullt
genullt
Metric

Tabelle $tab: RIP Update Paket, Format eines Routingeintrags

Inhalte der Felder:
Version 1: RIPv1 2: RIPv2
Command 1: RIP Request, 2: RIP Response
address family identifier 2: IP
Ein RIP Update Paket kann aus maximal 25 Routingeinträgen bestehen, das ergibt 512 Oktets, es wird an 255.255.255.255 adressiert.

1.1 Schritte bei einem Update: (Index)

Zieladresse bisher unbekannt -> installiere Update
Zieladresse bekannt, aber neue Metrik kleiner -> installiere Update
Zieladresse bekannt, aber neue Metrik größer -> ignoriere Update
Zieladresse bekannt, neue Metrik gleich -> laut RFC1058 ignorieren, CISCO hält bis zu 4 parallele Routen für Load Balancing vor

Um parallele Pfade zu benutzen, gibt es 2 verschiedene Balancemodi: Process Switching und Fast Switching

Process Switching:

Packet-by-Packet Load Balancing, d.h. jedes Paket wird einzeln geroutet
Jedes Paket nimmt andere Route
Jedes Paket erfordert Routing Table Lookup, daher CPU intensiv

Fast Switching:

Session-by-Session Load Balancing
jedes Paket einer Session nimmt selbe Route
Route wird nur für erstes Paket berechnet und in einem Cache gespeichert
relativ CPU-günstig
nächste Session nimmt andere Route

1.2 Timer (Index)

Da die Updates erst an die jeweiligen Nachbarn der Router propagiert werden, ergibt sich eine relativ hohe Schaltzeit durch das Netzwerk. Da dies bei Fehlern im Netz (invalide Route etc.) recht lange dauert, gibt es verschiedene Timer die die Routing Tabelle und das Updateverhalten beeinflussen:

Update Timer (30s)

wird nach jedem Update genullt und zählt wieder hoch bis 30
zählt so die Zeit zum nächsten fälligen Standardupdate

Invalid Timer (180s)

wird nach erfolgreichem Update auf 0 gesetzt
wenn die 180s erreicht werden, sind 6 Standardupdates fehlgeschlagen
Quelle der Updates gilt als nicht mehr vertrauenswürdig
Obwohl die Route invalidiert wird, werden Pakete noch über den nächsten Hop in der Tabelle geschickt

Hold Down Timer (180s)

startet, nachdem der Invalid Timer 180s erreicht hat
oder startet nach einem Update, das eine Route invalidiert
Route geht dabei automatisch in Hold Down
alle Updates der Route werden abgelehnt, Routinginformationen gelten nicht mehr als vertrauenswürdig
Netzwerk gilt momentan als nicht mehr stabil, es können instabile Routing Updates kursieren

Flush Timer (240s)

wird nach erfolgreichem Update genullt
wenn er 240s erreicht hat, wird die Route entfernt
Updates der Route werden wieder akzeptiert
Überschreibt den Hold Down Timer

Ein sofortiger Flush einer Route wird ausgelöst, wenn das entsprechende Interface des Routers down geht.
Ein Triggered Update wird sofort an die Nachbarn geschickt, wenn der Router eine Metrikänderung einer Route mitgeteilt bekommt.

Router verschicken in ihren Updates keine Änderungen von Routen, die über dieses Interface laufen. Diese Technik nennt sich "Split Horizon" und soll einen Zyklus verhindern, der sich in folgender Situation ergeben würde:

Router AA --- 192.168.1.0 >|< 192.168.2.0 --- Router BB

AA verliert die Verbindung zu 192.168.1.0, schickt aber vorher noch ein Update an BB. BB antwortet mit einem Update, das AAs Link zu 192.168.1.0 enthält, die Metrik ist hierbei 1. AA geht davon aus, das BB einen Link über einen Hop zu 192.168.1.0 hat, und installiiert diese Route nun in sich mit dem Hop 2. Die neue Route wird an BB propagiert, der daraufhin genauso reagiert und die Metrik auf 3 setzt. Nach ein paar Durchgängen ist die Metrik bei unendlich (16) angekommen und die Routen werden entfernt.
Mit Split Horizon werden die Routeninformationen über 192.168.1.0 nicht ausgesendet, da ja das Interface selbst zum versenden der Updates verwendet wurde.

Bemerkt ein Router das ein Link unterbrochen ist, propagiert er die Metrik 16 und vergiftet ("poison reverse") so die Route, da alle Empfänger des Updates die Route in hold-down schicken.

1.3 Subnetzmasken (Index)

Wie auf den ersten Blick einsichtig wird, enthält ein RIP-Paket keine Informationen zu Subnetzmasken. RIP benutzt zwei Methoden um Subnetzmasken zu vergeben.
Hat der Router ein eigenes Interface in einem Netz, das upgedated wird, verwendet er für das Netz die Subnetzmaske, die er auch an seinem Interface hat. Daraus resultiert, das RIP VLSM nicht unterstützt.
Hat der Router kein Interface in dem upzudatendem Netz, kalkuliert er eine gebräuchliche Netzmaske und verwendet diese.

1.4 Default Route (Index)

Da ein Router verständlicherweise nicht alle möglichen Pfade in einem Netzwerk kennen kann, gibt es eine Default Route. Passt ein Paket auf keine explizit vorhandene Route, schickt es der RIP Router auf die Default Route, die als 0.0.0.0 gekennzeichnet wird. Dadurch wird Bandbreite und Rechenzeit gespart, da nicht alle möglichen Routen durchgegangen und upgedated werden müssen. Problematisch ist hierbei allerdings, daß das Paket geforwarded wird, selbst wenn die Zielroute nicht passierbar ist. Außerdem ist es so möglich ein Netz mit VLSM von einem RIP Router aus erreichbar zu machen.

2 Routing Information Protocol 2 (RIP2) (Index)

RIP2 erweitert RIP1 um einige Funktionen um dessen Unzulänglichkeiten zu beheben.

Erweiterungen gegenüber RIP1

Subnetzmasken werden nun unterstützt und machen RIP2 so zu einem klassenlosen Protokoll
Die IP Adresse des nächsten Hops werden in Updatepaketen mitgeschickt.
Authentifizierungsmechanismen wurden hinzugefügt um die Authenzität eines Updates sicherzustellen
Ein RIP2 Paket enthält ein Route Tag Feld, das z. B. benutzt werden kann um die Quelle eines Update anzugeben, wenn diese nicht im RIP Netz ist

2.1 Paketformat (Index)

0	8	16	24
Command	Version	unbenutzt
address family identifier		Route Tag
IP Address
Subnetzmaske
Nächster Hop
Metric

Tabelle $tab: RIP Update Paket, Format eines Routingeintrags

Inhalte der Felder:
Version 2: RIPv2
Command 1: RIP Request, 2: RIP Response
address family identifier 2: IP
Route Tag wird nicht von RIP genutzt, kann aber Informationen wie bspw. die AS eines EGP tragen

Ein RIP Update Paket kann aus maximal 25 Routingeinträgen bestehen, das ergibt 512 Oktets, es wird an 255.255.255.255 oder an die Multicastadresse 224.0.0.9 adressiert.
Ein RIP2 Paket, dessen AFI auf 0xffff gesetzt ist, impliziert den Inhalt von Authentifizierungsmechanismen anstatt einer Route. RFC1732 definiert den Einsatz eines Passworts, das im Klartext übertragen wird. Cisco unterstützt stattdessen auch MD5 Summen als Passwort, die im ersten und letzten Paket eines Updates übertragen werden.
Da RIP2 nur die Paketfelder verwendet, die in RIP1 genullt sind, können RIP1 Router diese auch verarbeiten. Ferner kann man auf einem Router einstelen, ob er auf einem Interface RIP1 oder RIP2 senden bzw. empfangen soll. Man sollte aber beachten das RIP1 nichtsdestotrotz immer noch kein Classless Netz kennt und so evtl. das Netz in einen ungewünschten Zustand bringt.

3 Open Shortest Path First (OSPF) (Index)

OSPF ist ein hierarchisches Routingprotokoll, das mehrere Ebenen (oder Areas) eines Netzwerks erwartet. OSPF ermöglicht es so auch sehr große Netze zu verwalten, da jeder Router nur seine eigene Ebene kennen muss.
Weiterhin ist OSPF kein Distant Vector Protokoll, sondern ein Link State Protokoll, es verwendet Dijkstras SPF Algorithmus (auch bekannt als Dijkstra Algorithmus), um kürzeste Pfade im Netzwerk (dem Graphen) zu finden, hierbei sind die Kanten gewichtet.

3.1 Hierarchie und Gebiete (Index)

Da OSPF eine hierarchische Ordnung des Netzwerks vorraussetzt, wird dieses in mehrere Gebiete unterteilt. Je nach Struktur bzw. Eigenschaften der Gebiete spielen diese und ihre Router eine spezifische Rolle. Jedes Gebiet wird durch eine eineindeutige ID (0 bzw. 0.0.0.0 bis 4.294.957.295 bzw. 255.255.255.255) gekennzeichnet

3.1.1 Backbone (Index)

Jedes andere Gebiet muss mit der Backbone verbunden sein, es ist quasi das Rückgrat des Netzes. Jeder Router mit ein einem Interface in der Backbone ist ein Backbonerouter. Diese müssen die gesamte Netzwerktopologie bearbeiten, da Verkehr zwischen anderen Gebieten durch die Backbone durchgeleitet wird. Die ID der Backbone ist 0 bzw. 0.0.0.0

3.1.2 Interne Router (Index)

Ein interner Router hat nur genau ein Interface in genau einem Gebiet.

3.1.3 Area Border Router (ABR) (Index)

Ein ABR hat mehrere Interfaces in mehreren Gebieten und hält topologische Informationen für jene Gebiete vor. Ein ABR kann die topologische Datenbank eines seiner Gebiete zusammenfassen, um die Komplexität von OSPF zu reduzieren.

3.1.4 Autonomous System Boundary Router (ASBR) (Index)

Ein ASBR importiert externe Routen außerhalb des OSPF Gebiets (bspw. ein RIP-Netz)

3.1.5 Stub Area (Index)

Ein Stub Area hat keine direkte Verbindung zu externen Netzen. Daher wird jeder Verkehr, der in externe Netze geroutet werden muss über ABR geroutet und der Import von externen Routen kann durch eine einfache Defaultroute über einen ABR ersetzt werden. Stub Area Router halten die topologische Datenbank ihres Gebiets und ein ein Zusammenfassung benachbarter Gebiete, nicht jedoch externer Routen vor.

3.1.6 Totally Stubby Areas (TSA) (Index)

Erweitert ein Stub Area indem es eine neben externen Routen auch Routen in andere Gebiete über eine Defaultroute schickt.

3.1.7 Not So Stubby Areas (NSSA) (Index)

Ein NSSA ist im Prinzip ebenfalls wie ein SA, unterstützt aber externe Routen.

3.2 Topologische Datenbank (Index)

Die Topologiedatenbank besteht aus sogenannte Link State Advertisements (LSA). Ein LSA wird von einem Router generiert und beschreibt einen Subgraphen der gesamten Netzwerktopologie. Es gibt verschiedene LSA-Typen.

3.2.1 LSA Typen (Index)

Router LSA (Typ 1) Beschreibt die Links eines Routers, wird von jedem Router generiert und an alle internen Router übertragen Network LSA (Typ 2) Beschreibt ein Broadcast Netzwerk (bspw. ein Ethernet Segment) oder ein Non-Broadcast Multi-Access Netzwerk (Frame Relay). Das LSA enthält alle an das Broadcast/NBMA Segment angeschlossen Router. Es wird an alle internen Router verteilt. Summary LSA (Typ 3) Beschreibt die Topologie eines externen Gebiets. Wird von einem ABR in alle andere Gebiete (außer TSAs) gesendet. ASBR Summary LSA(Typ 4) Route zu einem ASBR, enthält die 32-bittige Adresse des ASBR. Werden von einem ASBR an alle Router (außer in einem Stub Area) gesendet. External LSA (type 5) Beschreiben Routen außerhalb des OSP Gebiets, die auch Default Route sein können. Werden von einem ASBR an alle Router (außer in einem Stub Area) gesendet. NSSA external LSA (typ 7) beschreiben Routen zu anderen externen, autonomen Systemen. Werden nur im NSSA verbreitet, können aber von einem ABR in Typ 5 LSAs übersetzt werden.

3.2.2 Routen Typen (Index)

Jeder Router verwendet die Topologiedatenbank und den OSPF Algorithmus um die kürzesten Pfade zwischen zwei Knoten zu finden. Diese Pfade werden dann in den Routingtabellen als eine der vier Routentypen verbreitet. Intra-area Route Start und Ziel liegen im selben lokalen Gebiet Inter-Area Route (auch Summary Route genannt) Ziel liegt in einem anderen Gebiet. Der Pfad traversiert dabei die Backbone, um zu einem anderen Gebiet zu kommen. Externe Route, Typ 1 Eine Route zu einem Ziel außerhalb des autonomen Systems. Die Kosten der Route setzen sich aus den Gesamtkosten des Pfades zu Ziel m externen Netzwerk und den Kosten zum Erreichen des ASBR jener Route zusammen. Externe Route, Typ 2 Wie Typ 1, enthält allerdings nicht die Kosten zum Erreichen des ASBR.

3.3 OSPF Paket (Index)

0	8	16	24
Version	Typ	Paketlänge
Router ID
Area ID
Prüfsumme		Authentifizierungstyp
Authentifizierungsdaten
Authentifizierungsdaten

Tabelle $tab: Das OSPF Paket

Version verwendete OSPF Version Area ID Typ 5 Typen sind definiert:

1: "Hello"
2: Datenbankbeschreibung
3: Linkstatus Request
4: Linkstatus Update
5: Linkstatus Bestätigung

Paketlänge Länge des Pakets inkl. Header Router ID ID-Nummer des Senders Area ID ID des Gebiets, in dem das Paket verschickt wurde Prüfsumme Prüfsumme über das ganze Paket inkl. Header Authentifizierungstyp

0 Keine Authentifizierung
1 Klartextpasswort
2 MD5

Authentifizierungsdaten Prüfsumme bzw. Passwort

3.4 HELLO Protokoll (Index)

Jeder Router verschickt auf seinen OSPF-Interfaces alle 10 (Broadcast) oder 30 (Nicht-Broadcast) Sekunden HELLO Pakete. Jeder Router erkennt seine Nachbarn anhand dieser Pakete. Beim Start des Routers erzeugt er eine eineindeutige Router ID, gelingt das Generieren nicht, bricht der OSPF Prozess ab. Es gibt zwei Methoden, eine ID zu erzeugen:

Der Router nimmt die höchste IP Adresse seiner aktiven loopback-Schnittstellen
Hat der Router keine aktiven loopbackschnittstellen, wählt er die höchste IP Adresse anderer Schnittstellen aus. Existieren derartige Schnittstellen nicht, bricht der OSPF Prozess ab.

3.4.1 HELLO Paket (Index)

0	8	16	24
Netzwerkmaske
HELLO-Interval		Optionen	Priorität
Router Tot
DR
BDR
Nachbar ID
Andere Nachbarn

Tabelle $tab: Das HELLO Paket

Hello-Interval Abstand zwischen HELLO Paketen, normalerweise 10 sek. Optionen

N/P

Es gibt verschiedene OSPF Optionen, die in einem ein Oktet langen Feld codiert werden.
DC codiert einen Router der demand circuits (Dial Up links wie ISDN oder Modem) unterstützt
N codiert NSSA-Unterstütung
E Router akzeptiert LSAs, wird von Routern in Stub Areas abgeschaltet.
T zeigt die Unterstützung mehrerer Servicetypen an
Priorität setzt die Priorität des Routers im DR Algorithmus Router Tot wenn in dieser Zeitspanne keine HELLO-Pakete mehr eintreffen, wird der Nachbar für Tot erklärt DR/Designated Router Vordefinierter Router für multi-access Netzwerke BDR/Backup DR Backup Router für multi-access Netzwerke Nachbar ID Liste der Nachbarrouter, die innerhalb des letzten "Router Tot" Intervalls ein HELLO-Paket eingesand haben. Nachbarrouter müssen dabei in folgenden Punkten übereinstimmen: Version, Authentifizierungstyp, Optionen, HELLO-Interval, Netzwerkmaske und Router Tot.

3.4.2 DR/DBR (Index)

Würde ein Router mit allen Nachbarn die topologische Datenbank austauschen, würden sich n*(n-1)/2 Verbindungen ergeben. Dies erzeugt natürlich gewaltigen Netzwerkverkehr, daher legt OSPF zwei spezielle Router in jedem Segment fest. Der Desginated Router (DR) und der Backup Designated Router (BDR) sind die einzigen Router, die mit allen Routern im Segment HELLO-Pakete austauschen und diese zu den anderen Segmenten weiterleiten. Ob ein Router als DR oder DBR fungiert, wird beim Starten des selbigen festgelegt.

Der Router startet und empfäng HELLO-Pakete. Stellt sich dabei raus, das ein DR/DBR bereits existiert, wird der DR/DBR Prozess terminiert
Existiert kein BDR, wird der Router mit der höchsten Priorität BDR. Haben mehrere Router die selbe höchste Priorität, gewinnt die höchste Router ID. Ein Router mit Priorität 0 wird kein DR/BDR.
Existiert kein DR, wird der BDR zum DR und ein neuer BDR wird gewählt

3.5 Status der Schnittstellen (Index)

Down Die Schnittstelle ist abgeschaltet und verschickt keinen OSPF Verkehr Loopback Schnittstelle ist als loopback eingestellt und wird im LSA als Hostroute propagiert Point-to-point Die Schnittstelle ist aktiviert und als serielle oder virtuelle Schnittstelle eingestellt. Im Point-to-point Modus werden die Nachbarn sofort Verbindung aufnehmen Waiting Nur in NBMA Netzen, der Router versucht gerade den DR/BDR zu identifizieren DR die Schnittstelle ist am DR Backup die Schnittstelle ist am BDR DRother Die Schnittstelle ist weder DR noch BDR. Der Router wird sofort Verbindung zum DR/BDR aufnehmen

3.6 Verbindungen der Nachbarn (Index)

Nachbarn müssen nicht zwangsläufig komplette Verbindungen aufnehmen, der Typ des Netzwerks entscheidet über die Beziehung.
point-to-point Router in point-to-point Netzen etablieren immer eine Nachbarschaft Broadcast Router in Broadcastnetzen etablieren 2-Wege-Beziehungen nur mit den DR und DBR NBMA 2-Wege-Beziehungen mit den DR und DBR werden etabliert Virtuelle Links es werden immer Verbindungen zwischen den Routern etabliert

3.7 Austausch der Datenbank (Index)

Die LS (Link State) Datenbank wird in einem DD-Paket (Database Description) propagiert. In einem DD-Paket werden hierzu zwischen den Routern die LSA-Header ausgetauscht.

3.7.1 DD Paket (Index)

0	8	16	24
Alter des Linkstatus		Optionen	Typ des Linkstatus
LS ID
Propagierender Router
LS Sequenznummer
Prüfsumme		Länge

Tabelle $tab: Der LSA Header

LS Typ	LS ID
1 Router LSA	Router ID des Absenders
2 Netzwerk LSA	IP Adresse des Netzwerkinterfaces im multi-access Netz
3 Summary	IP Adresse des Zielnetzwerks
4 ASBR Summary	Router ID des ASBR
5 externes LSA	IP Adresse des Zielnetzwerks

Tabelle $tab: LS Typ und ID

Die LSA Sequenznummer beginnt bei 0x80000001 und wird bis 0x7fffffff inkrementiert. Anhand der Nummer wird das neueste Paket identifiziert.
Empfängt ein Router ein DD Paket vergleicht er dessen Daten mit der Datenbank. Existiert der Datensatz nich oder mit einer niedrigeren Sequenz, antwortet er mit einem LS Request Packet, das den LSA Header enthält. Das LS Request Packet wird mit einem LS Update beantwortet, das den kompletten LSA beinhaltet. LS Updates werden mit einem LS ACK beantwortet.

0	8	16	24
Alter des Linkstatus		Optionen	Typ des Linkstatus
LS ID
Propagierender Router
LS Sequenznummer
Prüfsumme		Länge

Tabelle $tab: Das DD Paket

(Seite ist noch in Bearbeitung!)

net-tex.de, Index

$Id: routing.html,v 1.42 2014/08/21 09:23:55 stefan Exp $

Autor: Stefan Schumacher, stefan@net-tex.de, PGP-Key 0xB3FBAE33
für net-tex.de/cryptomancer.de
Bitte beachten Sie, das die Seite inhaltlich seit Ende 2007 nicht mehr gepflegt wird!
Aktuellere Informationen erhalten Sie auf Kaishakunin.com