1 Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Informations- und Kommunikationssysteme
Kapitel 2.4 Netzwerkschicht
Acknowledgement: Folien angelehnt an J.F. Kurose and K.W. Ross
2
Kapitel 2.4: Netzwerkschicht
• Unsere Ziele: • Verständnis für Prinzipien der Dienste der Netzwerkschicht:
• Wie funktioniert ein Router? • Wie arbeitet Routing (Pfadwahl)? • Wie wird mit der Größe von Netzen umgegangen? (Skalierbarkeit)
• Immer anhand vom Beispiel Internet
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
3
Kapitel 2.4: Netzwerkschicht
• 4.1 Einführung • 4.2 Virtual Circuit und Datagram
Netze • 4.3 IP: Internet Protocol
• Format der Datagramme • Adressierung in IPv4
• 4.4 Routing-Algorithmen • Überblick • Distanzvektor • Link State • Hierarchisches Routing
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
4
Netzwerkschicht
• Transportiert Segmente vom Sender zum Empfänger
• Auf Senderseite: Kapselung von Segmenten in Datagramme
• Auf Empfangsseite: Auslieferung von Segmenten an Transportschicht
• Protokolle der Netzwerkschicht laufen in jedem Host & Router
• Router werten Header aller weitergeleiteten IP-Pakete aus
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
network data link physical
network data link physical
network data link physical
network data link physical
network data link physical
network data link physical
network data link physical
network data link physical
application transport network data link physical
application transport network data link physical
5
Kernfunktionalität der Netzwerkschicht
• Forwarding: Weiterleitung von Paketen von Eingangs-Link zu korrektem Ausgangs-Link
• Routing: Bestimmen des Weges auf dem Pakete von Quelle zum Ziel weitergeleitet werden
• Routing-Algorithmen
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Analogie:
! Routing: Planen einer Wanderung
! Forwarding: Richtiges Abbiegen an einer Weggabelung
6 Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
1
2 3
0111
Ziel im Paket- Header
Routing-Algorithmus
Lokale Forwardingtabelle header value output link
0100 0101 0111 1001
3 2 2 1
Zusammenspiel zwischen Routing und Forwarding
7
Kapitel 2.4: Netzwerkschicht
• 4.1 Einführung • 4.2 Virtual Circuit und Datagram
Netze • 4.3 IP: Internet Protocol
• Format der Datagramme • Adressierung in IPv4
• 4.4 Routing-Algorithmen • Überblick • Distanzvektor • Link State • Hierarchisches Routing
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
8
Netzwerkschicht: Verbindungslose und –orientierte Dienste
• Datagramm-Netze stellen nur verbindungslose Dienste bereit • VC Netze bieten Verbindungen auf Netzwerkschicht • Ähnlich zu Diensten der Transportschicht, aber:
• Ebene des Dienstes: Nicht mehr Host-zu-Host • Keine Wahlmöglichkeit: Netzwerk stellt nur eine Dienstart bereit • Nicht notwendigerweise zuverlässig • Implementierung: Im Kern des Netzes
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
9
Virtuelle Kanäle (VC Virtual Channel) Implementierung
• Ein VC besteht aus: • Pfad von Quelle zum Ziel • VC Nummern, eine Nummer für jeden Link entlang des Pfades • Einträge in den Forwarding-Tabellen der Router entlang des
Pfades
• Pakete, die zu einer Verbindung gehören, enthalten eine spezifische VC-Nummer.
• Die VC-Nummer muss auf jedem Link geändert werden. • Die neue VC-Nummer wird aus der Forwarding-Tabelle
entnommen
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
10
Forwarding Table
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
12 22 32
1 2 3
VC Nummer
Interface Nummer
Eingehendes Interface Eing. VC # Ausg. Interface Ausg.VC #
1 12 3 22 2 63 1 18 3 7 2 17 1 97 3 87 … … … …
Forwarding Table im Router (links oben):
Router müssen Verbindungsinformationen vorhalten!
11
Virtuelle Verbindungen: Signalisierungsprotokolle
• Benötigt für Aufbau, Verwaltung und Abbau einer VC • z.B. verwendet für ATM, Frame-Relay, X.25 • Nicht verwendet im heutigen Internet
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
application transport network data link physical
application transport network data link physical
1. Verb.-aufbau 2. Eingehende Verb. 3. Annahme 4. Verb. aufgebaut
5. Datenfluss beginnt 6. Datenempfang
12
Datagramm Netze
• Kein Verbindungsaufbau auf Netzwerkschicht • Router: speichern keinen Zustand zu Ende-zu-Ende Verbindungen
• Es gibt auf Netzwerkschicht kein Verbindungskonzept • Pakete werden anhand der Adresse des Ziel-Hosts weitergeleitet
• Pakete zwischen zwei Hosts können bei Weiterleitung verschiedene Pfade durchlaufen
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
application transport network data link physical
application transport network data link physical
1. Datensenden 2. Datenempfang
13
Kapitel 2.4: Netzwerkschicht
• 4.1 Einführung • 4.2 Virtual Circuit und Datagram
Netze • 4.3 IP: Internet Protocol
• Format der Datagramme • Adressierung in IPv4
• 4.4 Routing-Algorithmen • Überblick • Distanzvektor • Link State • Hierarchisches Routing
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
14
Die Netzwerkschicht im Internet
Host & Router Funktionen der Netzwerkschicht:
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Forwarding Table
Routing Protokolle ! Wegewahl ! RIP, OSPF, BGP
IP Protokoll ! Adressierung ! Datagramm-Format ! Paketbehandlung
ICMP Protokoll ! Fehlerbehandlung ! Router-“Signale”
Transportschicht: TCP, UDP
Datensicherungsschicht
Bitübertragungsschicht
Netzwerk- schicht
15
IP Paketformat (I)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
ver Größe
32 Bits
Daten (Variable Länge,
z.B. TCP oder UDP Segment)
16-bit Identifier
Prüfsumme time to live
32 Bit Quelladresse
Versionsnummer
Headerlänge (4-Byteblöcke)
Max. Anzahl verbleibender Weiterleitungsschritte
(in jedem Router dekrementiert)
Für Frag- mentierung
Gesamtlänge (Bytes)
Protokoll der Transportschicht
IHL type of service
Datenklasse flgs Fragment Offset
Proto.
32 Bit Zieladresse Optionen (falls vorh.) z.B. Timestamp,
Record Route Source Route Wie viel Overhead
entsteht in TCP? ! 20 Byte TCP ! 20 Byte IP = 40 Bytes +
Steuerungsverkehr
16
IP Paketformat (II)
• Version: die Versionsnummer des IP (z.Zt. 4, irgendwann 6) • IHL: IP Header Länge in 32-Bit Blöcken • Type of Service: Informationen zur Priorität (selten genutzt) • Total Length: Gesamtlänge des Datagramms in Bytes (mit Header) • Identification: Beim Aufteilen von IP-Paketen erhalten alle Teile die
gleiche Nummer um sie korrekt zusammenzusetzen • Flags:
• DF: Don’t Fragment • MF: More Fragments; Paket ist Teil eines größeren fragmentierten
und weitere Teile folgen • Fragment Offset: Position des Fragmentes im Originalpaket (Zähler in
8 Byte-Schritten) • Time to Live: hop count, Heruntergezählt bei jeder Weiterleitung;
Paket wird verworfen wenn 0 erreicht wird
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
17
IP Paketformat (III)
• Protocol: gibt an welches Transportprotokoll verwendet wird (meistens entweder TCP oder UDP)
• Header Checksum: Prüfsumme über den IP-Header (nicht über die Daten, 1‘s complement sum)
• Quell- und Zieladressen: identifizieren Sender und Empfänger • Options: bis zu 40 Bytes Länge; genutzt um IP zu erweitern (Beispiele:
Source Routing, Record Route)
• IPv4-Adressen: • 32 Bits lang (4 Bytes) • Der Wert jedes Bytes wird dezimal in MSB Ordnung angegeben, durch
Punkte separiert (Beispiel: 128.195.1.80) • 0.0.0.0 (kleinste) bis 255.255.255.255 (höchste)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
18
IP Fragmentierung & Zusammensetzen
• Netzwerk Links besitzen unterschiedliche MTU (Max. Transfer Size)
• durch Datensicherungs-schicht bestimmte max. Paketgröße
• Je nach Link unterschiedlich • Große IP Datagramme
werden im Netz geteilt • u.U. auch mehrfach • “Reassembly” erst im
Zielsystem • IP Header genutzt um
Pakete zu ordnen und zusammenzusetzen
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Fragmentierung: ein: 1 großes Datagramm aus: 3 kleinere
Zusammensetzen
19
Kapitel 2.4: Netzwerkschicht
• 4.1 Einführung • 4.2 Virtual Circuit und Datagram
Netze • 4.3 IP: Internet Protocol
• Format der Datagramme • Adressierung in IPv4
• 4.4 Routing-Algorithmen • Überblick • Distanzvektor • Link State • Hierarchisches Routing
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
20
Internet Namen und Adressen
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
hierarchisch www.ietf.org Hostnamen
topologisch (meist) 132.151.1.35 IP-Adressen
flach, statisch 08:00:20:72:93:18 MAC-Adressen
Organisation Beispiel
IP Adresse MAC Adresse Hostname
DNS n-zu-n
ARP 1-zu-1
21
IP-Adressklassen (I)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
0 Netz
32 bits
Type of Serv. Host
10 Netz Host
110 Netz Host
1110 Multicast Adresse
11110 Reserviert
A
B
C
D
E
Klasse
22
IP-Adressklassen (II)
• Klasse A: für sehr große Organisationen; bis 16 Mio. Hosts • Klasse B: für große Organisationen; bis 65354 Hosts • Klasse C: für kleine Organisationen; 254 Hosts • Klasse D: Multicast Adressen; Keine Netzwerk/Host Hierarchie • Klasse E: Reserviert • Loopback: 127.xx.yy.zz (127.irgendwas) reserviert für Loopback
Tests; Pakete werden nicht versendet; werden lokal als eingehen Pakete behandelt; sinnvoll für Komm. auf gleichem Host
• Broadcast: 255.255.255.255 • Adresshierarchie:
• Jede Adresse hat zwei Teile einen Host- und einen Netzteil • Klasse A, Klasse B und Klasse C Adressen unterstützen eigentlich nur 2
Hierarchiestufen • „Subnetze“ erlauben jedoch ein weiteres Aufteilen durch den
Adressbesitzer
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
23
Adressierung in IP
• IP-Adresse: Identifiziert Host oder ein Router Interface
• Interface: Verbindung zwischen Host/Router und physischem Link
• Router haben typischerweise mehrere Interfaces
• u.U. können auch Hosts mehrere Interfaces besitzen
• IP-Adressen jeweils für ein Interface
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2 223.1.3.1
223.1.3.27
223.1.1.1 = 11011111 00000001 00000001 00000001
223 1 1 1
24
Subnetze
• IP-Adresse: • Subnetzteil (höhere Bits) • Hostanteil (niedrige Bits)
• Was ist ein Subnetz? • Interfaces von Geräten mit
gleichem Subnetzanteil in der IP-Adresse
• Können einander erreichen ohne einen Router zu verwenden
• Bestimmung
• Durch Router separierte Netze einzeln betrachten
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2 223.1.3.1
223.1.3.27
Netzwerk besteht aus 3 Subnetzen
LAN
25
Subnetze
F: Wie viele Subnetze werden eingerichtet?
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
223.1.1.1
223.1.1.3
223.1.1.4
223.1.2.2 223.1.2.1
223.1.2.6
223.1.3.2 223.1.3.1
223.1.3.27
223.1.1.2
223.1.7.0
223.1.7.1 223.1.8.0 223.1.8.1
223.1.9.1
223.1.9.2
26
Mehr über IP-Adressen (I)
• Nach dem wir wissen was ein “Subnetz” ist, ein weiterer Blick auf IP-Adressen:
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
0 Subnetz Host
10 Subnetz
Host
110 Subnetz Host
1110 Multicast Adresse
A
B
C
D
Klasse 0.0.0.0 bis 127.255.255.255 128.0.0.0 bis 191.255.255.255 192.0.0.0 bis 223.255.255.255
224.0.0.0 bis 239.255.255.255
32 Bits
“Klassen-behaftete” Adressierung:
27
Mehr über IP-Adressen (II)
• Adressierung mit Klassen: • Ineffiziente Nutzung des Adressraums, schnelle Erschöpfung • Bsp. Klasse B Netz bietet Raum für 65.534 Hosts, auch wenn nur 2000
Hosts im Netz sind • CIDR: Classless InterDomain Routing
• Erlaubt Netzwerkanteile der Adressen beliebiger Längen • Adressformat: a.b.c.d/x, wobei x # Bits des Subnetzanteils
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
11001000 00010111 00010000 00000000
Subnetz- anteil
Host- anteil
200.23.16.0/23
28
CIDR: Classless Interdomain Routing
• Klassengrenzen werden aufgeweicht → “Supernetting” (Zusammenfassen von Subnetzen)
• ISPs können mehre zusammenhängende Klasse C Blöcke vergeben
• “Longest match routing” bei den Adressen • Es werden immer die am Besten passenden Einträge für das Routing
verwendet; Bsp.: 192.175.132.26
Adresse/Maske Link 192.175.132.0/22 1 192.175.133.0/24 2 192.175.128.0/17 3
• Beispiel: Viele Netze in Europa haben ein gleiches Präfix → Nur ein Eintrag in vielen U.S. Routern
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
29
Kapitel 2.4: Netzwerkschicht
• 4.1 Einführung • 4.2 Virtual Circuit und Datagram
Netze • 4.3 IP: Internet Protocol
• Format der Datagramme • Adressierung in IPv4
• 4.4 Routing-Algorithmen • Überblick • Distanzvektor • Link State • Hierarchisches Routing
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
30
Erinnerung: Zusammenhang Routing und Weiterleiten
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
1
2 3
0111
Ziel im eingehenden Paket
Routing Algorithmus
local forwarding table header value output link
0100 0101 0111 1001
3 2 2 1
31
Überblick über Routing-Algorithmen (I)
• Router verwenden Routing-Algorithmen um zu bestimmen auf welche Ausgabe-Links Pakete gegeben werden:
• In verbindungsorientierten Netzen, werden Routing Algorithmen nur während des Verbindungsaufbaus benötigt
• In verbindungslosen Netzen, werden Routing-Algorithmen ausgeführt wenn ein Paket ankommt (reaktiv) oder periodisch (proaktiv, Resultate aktualisieren Forwarding Table)
• I.d.R. werden sog. Metriken bei der Wegwahl berücksichtigt: • Metriken stellen die „Kosten“ für die Nutzung von Links dar
• Erlaubt die Berechnung von „Kosten“ eines Gesamtpfades durch ein Netzwerk
• Metriken können Parameter wie Anzahl der Hops, monetäre Kosten des Links, Latenz, Füllstand der Warteschlage etc. berücksichtigen
• Der “billigste” Pfad in Bezug auf eine Metrik wird als kürzester Pfad (shortest path) bezeichnet, auch wenn er geographisch oder in Bezug auf Hops nicht kurz ist
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
32
Überblick über Routing-Algorithmen (II)
• Unterschiedliche Routing-Algorithmen: • Nicht-adaptive Routing-Algorithmen: Routing-Entscheidungen basieren
nicht auf Ziel des Paketes und Zustand des Netzes (Beispiel: Fluten) • Adaptive Routing-Algorithmen: Nutzen aktuellen Zustand des Netzes beim
Treffen von Routing-Entscheidungen (Beispiele: Distanzvektor-Verfahren, Link-State-Routing)
• Hierarchisches Routing kann verwendet werden, um Skalierbarkeit in großen Netzen zu gewährleisten
• E.g. Ein Routing-Verfahren innerhalb eines ISP und eins um Wege zwischen ISPs zu finden
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
33
Fluten
• Grundlegende Strategie: • Jedes eingehende Paket wird auf jedem Link außer dem eingehenden
versendet • Problem: Riesige Anzahl duplizierter Pakete
• Reduzieren der duplizierten Pakete: • Lösung 1:
• Nutzen eines Hop Counters im Paket-Header; Router zählen bei Weiterleitung runter; Paket wird verworfen bei Hop Count=0
• Hop Counter sollte im Optimum genau der Pfadlänge zwischen Quelle und Ziel entsprechen
• Lösung 2: • Jedes Paket erhält eine eindeutige Sequenznummer • Jeder Router hält eine Liste mit Sequenznummern von Paketen vor,
die er weitergeleitet hat • Pakete, die bereits weitergeleitet wurden, werden verworfen
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
34
Fluten: Mögliche Anwendungen
• Militärische Systeme • Große Anzahl von Routern wünschenswert (alle Systeme können
weiterleiten) • Wenn ein Router ausfällt (e.g. durch eine Bombe) erreichen geflutete
Pakete weiterhin ihr Ziel
• Verteilte Datenbanken • Simultane Aktualisierung mehrerer Datenbanken mit einer einzigen
Übertragung
• Netzwerke mit sehr schnellen Topologieänderungen • Adhoc-Netze
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
35
Adaptive Routing-Algorithmen
• Probleme nicht-adaptiver Algorithmen: • Relativ ineffizient • Kein Eingehen auf variierenden Verkehrsflüsse
Adaptive Routing-Algorithmen können darauf eingehen
• Drei Typen: • Zentralisiertes Adaptives Routing:
• Ein zentraler Routing Controller • Isoliertes Adaptives Routing:
• Basiert auf lokalen Informationen • Benötigt keinen Austausch zwischen Routern
• Verteiltes Adaptives Routing: • Routers tauschen periodisch Informationen aus und berechnen
aktualisierte Informationen für Forwarding Tables
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
36
Zentralisiertes Adaptives Routing
• Grundlegende Strategie: • Forwarding Table wird an Netzwerkzustand angepasst • Ein Routing Controller irgendwo im Netzwerk • Periodisch leiten Router Linkinformationen und –zustände an Controller
weiter • Controller bestimmt beste Routen, z.B. mit Algorithmus von Dijkstra
(Details später) • Beste Routen werden den einzelnen Routern mitgeteilt
• Probleme: • Robustheit: Wenn Routing Controller ausfällt, wird Routing statisch und
keine weitere Anpassung findet statt • Skalierbarkeit: Controller muss u.U. sehr viele Informationen verarbeiten
und weiterleiten
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
37
Isolierte Adaptive Routing-Algorithmen
• Grundlegende Strategie: • Routing-Entscheidungen werden nur auf der Basis lokalen Router-
Wissens getroffen
• Beispiel: • Hot-Potato-Routing • Backward learning
• Hot-Potato-Routing: • Wenn ein Paket ankommt leitet der Router es auf den Link mit der
kürzesten Warteschlange weiter • Hot-Potato-Algorithmus kümmert sich nicht um Ziel von Paket und Link • Sehr ineffizient
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
38
Backward Learning Routing
• Grundlegende Strategie: • Paket-Headers enthalten Ziel-, Quelladresse und Hop-Counter • → Nutzen der Information um über das Netz zu lernen • Netzwerkknoten wissen zu nächst nichts über das Netzwerk, lernen aber
das Gesamtnetz im Laufe des Verfahrens kennen
• Algorithmus: • Routing ist anfangs zufällig (oder Hot-Potato, Fluten etc.) • Ein Paket mit Hop Count 1 ist von direkten Nachbarn, Linknachbarn
können erlernt werden (Hop Counter werden hier aufwärts gezählt) • Ein Paket mit Hop Count 2 ist zwei Schritte von der Quelle entfernt usw. • Wenn ein Paket ankommt, vergleicht BLR den bekannten Weg zur Quelle
mit dem Hop Count, falls kleiner schicke die nächsten Pakete zur Quelle über den eingehenden Link
• Bemerkung: Um mit ausgefallenen Routen umgehen zu können müssen aufgebaute Informationen regelmäßig „vergessen“ werden
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
39
Verteiltes Adaptives Routing
Abstraktion als Graphen: • Graphknoten sind Router • Graphkanten sind physische Links
• Linkkosten: Latenz, €, Auslastung • Pfadkosten: Summe der
Linkkosten auf dem Weg
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Ziel: Herausfinden von “guten” Pfaden durch Netzwerk von Quelle zu Ziel
Routing-Protokoll
A
E D
C B
F 2
2 1 3
1
1 2
5 3
5
! “Guter” Pfad: ! Typisch: Pfad mit minimalen
Kosten ! Andere Definitionen selten
40
Klassifikation Verteilter Adaptiver Routing-Ansätze
Globale oder dezentrale Information? Dezentral: • Router kennt Nachbarn mit physi-
scher Verbindung & Kosten der Verbindung
• Iterativer Aufbau von Routing Tables durch Austausch mit Nachbarn
• “Distanzvektor”-Algorithmen → RIP & IGRP
→ BGP (“Pfadvektor”)
Global: • Alle Router kennen gesamte
Topologie mit Linkkosten • “Link State” Algorithmen
→ Dijkstra-Algorithmus → OSPF Protokoll
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Statisch oder dynamisch? Statisch: ! Routen ändern sich nur langsam Dynamisch: ! Routen ändern sich schnell
! Periodische Aktualisierung ! u.U. wegen Änderung der
Linkkosten
41
Kapitel 2.4: Netzwerkschicht
• 4.1 Einführung • 4.2 Virtual Circuit und Datagram
Netze • 4.3 IP: Internet Protocol
• Format der Datagramme • Adressierung in IPv4
• 4.4 Routing-Algorithmen • Überblick • Distanzvektor • Link State • Hierarchisches Routing
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
42
Algorithmus für Distanzvektor-Routing
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Iterativ: ! Wiederholt sich bis kein
Knoten Infos austauscht ! Selbstterminierend i.e.
kein Stoppsignal Asynchron: ! Knoten müssen
Informationen nicht in festen Schritten austauschen
Verteilt: ! Jeder Knoten kommuni-
ziert ausschließlich mit seinen direkten Nachbarn
Struktur der Distanztabelle ! Jeder Knoten hat eine
! Zeile für jedes mgl. Ziel ! Spalte für jeden direkten
Nachbarknoten ! Beispiel: In Knoten X, für Ziel Y
über Nachbarn Z:
D (Y,Z) X
Distanz von X zu Y, über Z
c(X,Z) + min {D (Y,w)} Z w
=
=
43
Beispiel für Distanztabelle
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
A
E D
C B 7
8 1
2
1
2 D ()
A
B
C
D
A
1
7
6
4
B
14
8
9
11
D
5
5
4
2
E Kosten zum Ziel über
Ziel
D (C,D) E
c(E,D) + min {D (C,w)} D w =
= 2+2 = 4
D (A,D) E
c(E,D) + min {D (A,w)} D w =
= 2+3 = 5
D (A,B) E
c(E,B) + min {D (A,w)} B w =
= 8+6 = 14
Schleife!
Schleife!
44
Ableiten eines Forwarding Table aus Distanztabelle
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
D ()
A
B
C
D
A
1
7
6
4
B
14
8
9
11
D
5
5
4
2
E Kosten zum Ziel über
Ziel
A
B
C
D
A,1
D,5
D,4
D,4
Genutzter Link, Kosten
Ziel
Distanztabelle Forwarding Table
45
Überblick über Distanzvektor-Routing
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Iterativ, asynchron: Jede Berechnung ausgelöst durch: ! Änderung lokaler Link-Kosten ! Nachricht von Nachbarn,
dessen kürzester Pfad sich geändert hat
Verteilt: Nachbarn informieren sich nur wenn ein kürzester Pfad sich geändert hat ! Nachbarn benachrichtigen
dann ihre Nachbarn, falls nötig
wartet bis (Änderung der Link-Kosten oder Nachricht)
berechnet Distanztabelle
Falls kürzester Pfad sich geändert hat, Nachbarn benachrichtigen
Jeder Knoten:
46
Distanzvektor-Routing: Initialisierung
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
1 Initialisierung: 2 Für alle benachbarten Knoten v: 3 D (*,v) = unendlich // * bedeutet "für alle Zeilen“ 4 D (v,v) = c(X,v) 5 Für alle Ziele y 6 Sende min D (y,w) zu jedem Nachbar // w für alle Nachbarn von X
In allen Knoten, X:
X
X
X W
47
Distanzvektor-Routing: Hauptschleife
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
8 loop 9 wait (bis Linkkosten geändert werden oder 10 Aktualisierung von Nachbar V kommt) 11 12 if (c(X,V) wird um Wert d geändert) 13 // Ändern aller Kosten von Zielen über V um d 14 // Anmerkung: d kann negativ oder positiv sein! 15 for all Ziele y: D (y,V) = D (y,V) + d 16 17 else if (Aktualisierung von V für Ziel Y) 18 // Kürzester Pfad von V zu Y hat sich geändert 19 // V hat einen neue Wert für min D (Y,w) gesendet 20 // dieser neue Wert "newval“ wird verwendet 21 D (y,V) = c(X,V) + newval 22 23 if falls sich neues min D (Y,w) für irgendein Y ergibt 24 Sende neuen Wert min D (Y,w) an alle Nachbarn 25 26 forever
X X
V W
X
X X
W W
48
Distanzvektor-Routing: Beispiel (I)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
X Z 1 2
7
Y
49
Distanzvektor-Routing: Beispiel (II)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
X Z 1 2
7
Y
D (Y,Z) X c(X,Z) + min {D (Y,w)} w=
= 7+1 = 8
Z
D (Z,Y) X c(X,Y) + min {D (Z,w)} w=
= 2+1 = 3
Y
50
Distanzvektor: Reaktion auf Kostenänderungen (I)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Link-Kostenänderungen: ! Knoten detektiert lokale
Kostenänderung ! Aktualisiert Kostentabelle (Zeile 15) ! Bei Veränderung des kürzesten Pfads
Nachbarn informieren (Zeilen 23,24)
X Z 1 4
50
Y 1
Algorithmus “terminiert” “Good
news travels fast”
51
Distanzvektor: Reaktion auf Kostenänderungen (II)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Link-Kostenänderungen: ! “Good news travels fast” ! “Bad news travels slow” – Führt
auf “Count to Infinity” Problem!
Algorithmus läuft weiter
X Z 1 4
50
Y 60
Y Y Y
52
Distanzvektor: Poisoned Reverse
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Wenn Z zu X über Y weiterleitet: ! Z informiert Y die Distanz über Z ist
unendlich (sodass Y nicht zu X via Z weiterleitet)
! Lösung für Count-to-Infinity?
Algorithmus terminiert
X Z 1 4
50
Y 60
Y Y Y Y
53
Kapitel 2.4: Netzwerkschicht
• 4.1 Einführung • 4.2 Virtual Circuit und Datagram
Netze • 4.3 IP: Internet Protocol
• Format der Datagramme • Adressierung in IPv4
• 4.4 Routing-Algorithmen • Überblick • Distanzvektor • Link State • Hierarchisches Routing
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
54
Link-State Routing
• Link State Routing basiert meistens auf dem Dijkstra’s Algorithmus: • Netzwerktopologie, Linkkosten sind allen Knoten bekannt:
• Verbreitung via “link state broadcast” ⩰ Fluten • Alle Knoten haben das gleiche Wissen
• Input: Graph (V, E) mit
• V Set von Knoten (nodes)
• E Set von Kanten (links)
• Kosten c(v, w) des Links (v, w) falls Kante existiert (d.h. (v, w) in E )
• c(v, w) = unendlichfalls Kante nicht existiert
• Ziel: Berechnung des kürzesten Pfades von einem Knoten s (“source”) zu allen anderen Knoten v:
• Wird zur Ermittlung des Forwarding Table für Knoten s verwendet
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
55
Dijkstra’s Algorithmus zur Berechnung kürzester Pfade (I)
• Grundidee des Algorithmus: • Am Anfang enthält Menge N nur den Quellknoten s. • In jedem Schritt des Verfahrens wird ein weiterer Knoten in dieses Menge
eingefügt, zu dem der kürzeste Pfad zu diesem Zeitpunkt bekannt ist. • Anfangs wird der kürzeste Pfad zu allen Knoten v auf „unendlich“
initialisiert (Ausnahme der Quellknoten s) • In jedem Schritt:
• Wähle den Knoten v aus, der vom Quellknoten s mit den geringsten Kosten erreicht werden kann, wenn der Weg nur über Knoten führt, die im Set N enthalten sind.
• Füge Knoten v in N hinzu • Ändere die Kosten für alle direkten Nachbarn w von Knoten v, falls
sich über Knoten v ein kürzerer Pfad als der bisher bekannte ergibt. • Falls sich die Kosten für einen Nachbarknoten w ändern, dann notiere
auch den Vorgängerknoten v, über den eine kürzere Route gefunden wurde.
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
56
Dijkstra’s Algorithmus zur Berechnung kürzester Pfade (II)
• Der Algorithmus verwaltet für jeden Knoten v: • Den zur Zeit bekannten kürzesten Pfad vom Quellknoten s zum Knoten v
mit der Distanz d(v) • Den Vorgängerknoten p(v) von Knoten v auf dem zur Zeit bekannten
kürzesten Pfad vom Quellknoten s zum Knoten v • Eine Liste mit allen Knoten, für die der kürzeste Pfad bereits bekannt ist
• Bemerkungen: • Wenn die Distanz d(v) endlich ist, so existiert ein Pfad vom Quellknoten s
zum Knoten v mit der Distanz d(v) • Für den Knoten v mit der kleinsten Distanz ist es der kürzeste Pfad
• Das bedeutet, dass für Knoten v der kürzeste Pfad bekannt ist • Dieser Knoten v wird nun in das Set N übernommen, in dem sich alle
Knoten befinden, für die der kürzeste Pfad bekannt ist • Der kürzeste Pfad wird für alle Nachbarknoten von v aktualisiert, die noch
nicht in N enthalten sind
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
57
Dijkstra’s Algorithmus zur Berechnung kürzester Pfade (III)
• Aktualisierungsprozedur: • Angenommen Knoten v wurde in Menge N übernommen :
• Es wird sein Nachbarknoten w betrachtet, der noch nicht in N ist • d(v) ist die kürzeste Distanz zu Knoten v • d(w) ist die kürzeste bekannte Distanz zu Knoten w • c(v, w) sind die Kosten von v nach w
if ( d(v) + c(v, w) < d(w)) { d(w) = d(v) + c(v, w); p(w) = v; }
• Begründung der Vorgehensweise: • Wenn die Distanzen d(w) und d(v) endlich sind, • existiert ein kürzester Pfad von s nach v mit der Distanz d(v) • Und auch ein Pfad von s über v nach w mit der Distanz d(v) + c(v, w) • Es existiert auch ein Pfad von s nach w mit der Distanz d(w) • Die kürzeste Distanz von s nach w kann nicht größer sein als d(w) oder
d(v) + c(v, w)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
58
Dijkstra�s Algorithm in Pseudocode
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Berechnet kürzeste Pfade von einem Knoten zu allen anderen 1 Initialization (für Knoten s): 2 N = {s} /* Menge von Knoten mit bekanntem bill. Pfad */ 3 forall Knoten v 4 if v verbunden mit s 5 then { d(v) = c(s,v); p(v) = s; } 6 else d(v) = unendlich; 7 8 Loop 9 finde v welcher nicht in N ist, sodass d(v) minimal 10 füge v zu N hinzu 11 forall w mit verbunden v und nicht in N /* aktual. d(w) */ 12 { if (d(v) + c(v, w) < d(w)) { d(w) = d(v) + c(v, w); p(w) = v; } } 13 /* neue Kosten zu w entweder alte Kosten oder kürzester 14 Pfad zu v plus Kosten von v zu w */ 15 until all nodes in N
59
Beispiel für Dijkstra-Algorithmus (I)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Schritt 0
start N A
d(B),p(B) 2,A
d(C),p(C) 5,A
d(D),p(D) 1,A
d(E),p(E) unendlich
d(F),p(F) unendlich
A
E D
C B
F 2
2 1
3
1
1 2
5 3
5
60
Beispiel für Dijkstra-Algorithmus (II)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Schritt 0 1
start N A
AD
d(B),p(B) 2,A 2,A
d(C),p(C) 5,A 4,D
d(D),p(D) 1,A
d(E),p(E) unendlich
2,D
d(F),p(F) unendlich unendlich
A
E D
C B
F 2
2 1
3
1
1 2
5 3
5
61
Beispiel für Dijkstra-Algorithmus (III)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Schritt 0 1 2
start N A
AD ADE
d(B),p(B) 2,A 2,A 2,A
d(C),p(C) 5,A 4,D 3,E
d(D),p(D) 1,A
d(E),p(E) unendlich
2,D
d(F),p(F) unendlich unendlich
4,E
A
E D
C B
F 2
2 1
3
1
1 2
5 3
5
62
Beispiel für Dijkstra-Algorithmus (IV)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Schritt 0 1 2 3
start N A
AD ADE
ADEB
d(B),p(B) 2,A 2,A 2,A
d(C),p(C) 5,A 4,D 3,E 3,E
d(D),p(D) 1,A
d(E),p(E) unendlich
2,D
d(F),p(F) unendlich unendlich
4,E 4,E
A
E D
C B
F 2
2 1
3
1
1 2
5 3
5
63
Beispiel für Dijkstra-Algorithmus (V)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Schritt 0 1 2 3 4
start N A
AD ADE
ADEB ADEBC
d(B),p(B) 2,A 2,A 2,A
d(C),p(C) 5,A 4,D 3,E 3,E
d(D),p(D) 1,A
d(E),p(E) unendlich
2,D
d(F),p(F) unendlich unendlich
4,E 4,E 4,E
A
E D
C B
F 2
2 1
3
1
1 2
5 3
5
64
Beispiel für Dijkstra-Algorithmus (VI)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Schritt 0 1 2 3 4 5
start N A
AD ADE
ADEB ADEBC
ADEBCF
d(B),p(B) 2,A 2,A 2,A
d(C),p(C) 5,A 4,D 3,E 3,E
d(D),p(D) 1,A
d(E),p(E) unendlich
2,D
d(F),p(F) unendlich unendlich
4,E 4,E 4,E
A
E D
C B
F 2
2 1
3
1
1 2
5 3
5
65
Link-State-Routing (mit Dijkstra-Algorithmus)
• Jeder Router bestimmt Link-Kosten (Latenz, Hop-Count, etc.) zwischen sich und angrenzenden Routern
• Router erstellen Pakete mit allen Distanzen zu Nachbarn • Enthält unter Anderem Seq.-Nummer und Altersinformationen
• Router verteilen diese Pakete mittels „Fluten“ • Pakete deren Sequenznummer bereits bekannt ist, werden verworfen
• Altersinformationen geben an, wie lange Informationen gültig sind
• Sobald ein Router alle relevanten Pakete des Netzes erhalten hat, kann er die Gesamttopologie rekonstruieren und Dijsktra‘s Algorithmus verwenden
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
66
Vergleich zw. Link-State- und Distanzvektor-Verfahren
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Nachrichtenkomplexität ! LS: bei n Knoten, E Links,
O(n•E) Nachrichten pro Periode
! DV: Austausch nur zwischen Nachbarn
! Konvergenzzeit variiert
Konvergenzgeschwindigkeit ! LS: O(n2) Algorithmus benötigt
O(n•E) Nachrichten ! u.U. Oszillationen
! DV: Konvergenzzeit variiert ! u.U. Routing-Schleifen ! Count-to-unendlich-Problem
Robustheit: Was passiert wenn Router ausfallen/sich falsch verhalten? LS:
! Knoten können ungültige Link-Kosten annoncieren
! Jeder Knoten berechnet eigne Tablle
DV: ! Knoten können ungültige
Pfad-Kosten annoncieren ! Tabelle von Einzelknoten
werden von anderen verwendet: ■ Fehler propagieren durch
das Netz
67
Kapitel 2.4: Netzwerkschicht
• 4.1 Einführung • 4.2 Virtual Circuit und Datagram
Netze • 4.3 IP: Internet Protocol
• Format der Datagramme • Adressierung in IPv4
• 4.4 Routing-Algorithmen • Überblick • Distanzvektor • Link State • Hierarchisches Routing
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
68
Hierarchisches Routing
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Größe (50 Millionen Ziele!): ! Einzelne Ziele können nicht
vollständig in Tabelle vorgehalten werden
! Austausch von Routing-Informationen würde Links überlasten
Administrative Autonomie: ! Internet = Netz von Netzen ! Jeder Netzwerk-Administrator
möchte Routing im eigenen Netz kontrollieren
Bisherige Betrachtungen idealisiert: ! Alle Router wurden identisch angenommen ! Netzwerk wurde als “flach” angenommen
… die Praxis sieht anders aus
69
Hierarchisches Routing: Autonome Systeme
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
! Aggregation von Routern in „Regionen“ sogenannte “Autonome Systeme” (AS)
! Router im gleichen AS verwenden gleiches Routing-Protokoll ! “Intra-AS” Routing Protokoll ! Router in unterschiedlichen AS
können unterschiedliche „Intra-AS“ Protokolle verwenden
! Spezielle Router in AS ! Nutzen Intra-AS Routing mit
anderen Routern im AS ! Zusätzlich verantwortlich um
Ziele außerhalb des AS anzusprechen
! Verwenden Inter-AS Routing-Protokoll mit anderen Gateway-Routern
Gateway-Router
70
Inter-AS- und Intra-AS-Routing
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
Gateways: ! Nutzen Inter-AS
Routing unter einander
! Nutzen Intra-AS Routing mit Routern im gleichen AS
Inter-AS, Intra-AS Routing in
Gateway A.c
network layer
link layer physical layer
a
b
b
a a C
A
B d
A.a A.c
C.b B.a
c b
c
71
Routing im Internet
• Globales Internet verbindet Autonome Systeme (AS) miteinander: • Stub AS: kleine Firmen, Behörden etc. (nur ein Link zum Internet) • Multihomed AS: große Firmen, Tier-3-Provider (Mehre Links, aber kein
Transit) • Transit AS: große Provider
• Routing auf zwei Ebenen: • Intra-AS: Administrator trifft Auswahl für Routing-Verfahren
• Routing Information Protocol (RIP): Distanzvektor • Open Shortest Path First (OSPF): Link State • Interior Gateway Routing Protocol (IGRP): Distanzvektor (Cisco
proprietär) • Inter-AS: nur ein Standard!
• Border Gateway Protocol (BGP): Pfadvektor (Distanzvektor, aber mit Pfadinformationen zur Schleifenvermeidung)
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
72
Warum ein Unterschied zwischen Intra- und Inter-Domain?
• Policy: • Inter-AS: Administrator wollen kontrollieren wer wie viel Verkehr
durch das Netz gibt • Intra-AS: Ein Admin, keine Policy-Fragen
• Größe: • Hierarchisches Routing verringert Tabellengrößen und
Aktualisierungsverkehr (immer noch 350,000 Präfixe!)
• Performanz: • Intra-AS: Fokus auf Performanz • Inter-AS: Policy-Entscheidungen gehen vor!
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
73
Netzwerkschicht: Zusammenfassung
Was behandelt wurde: • Dienste der Netzwerkschicht • IPv4 • Routing-Algorithmen & Hierarchisches Routing
Schlussfolgerungen: • Routing in großen Netzen erfordert nicht nur einfache Algorithmen für
generalisierte Graphen • Zusätzlich: hierarchische Netzwerkstruktur etc. • Optimales Routing nur „Nebenaspekt“
• Netzwerkstruktur muss in Adressstruktur berücksichtigt werden • Flache Adressen würden zu großen Overhead bedeuten
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht
74
Weiterführende Literatur
[Car03] G. Carle. Internet-Protokolle und -Komponenten. Vorlesungsfolien, Universität Tübingen, 2003. http://net.informatik.uni-tuebingen.de/teaching/ipuk/index.php
[CLR90] T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. MIT Press, MA, USA, 1990.
[KR04] J. F. Kurose, K. W. Ross. Computer Networking: A Top-Down Approach Featuring the Internet. 3rd edition, Addison Wesley, 2004.
[Sar04] S. Sarkar. Algorithms in Networking - Lecture 1. Course slides of course TCOM 799, School of Engineering & Applied Science, University of Pennsylvania, PA, USA, 2004.
[Ste95] M. Steenstrup. Routing in Communication Networks. Prentice Hall, 1995. [Sud04] T. Suda. Computer Networks. Course slides, Department of Information and
Computer Science, University of California, Irvine, USA, 2004. http://www.ics.uci.edu/~ics243a
Informations- und Kommunikationssysteme (SS 2014): 04 - Netzwerkschicht