Informations- und Kommunikationssysteme · 2014-04-15 · 3 Kapitel 2.4: Netzwerkschicht • 4.1 Einführung • 4.2 Virtual Circuit und Datagram Netze • 4.3 IP: Internet Protocol

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


•  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


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


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


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







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


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


10

Forwarding Table


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




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




1. Datensenden 2. Datenempfang

13







14

Die Netzwerkschicht im Internet

Host & Router Funktionen der 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)


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


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)


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


Fragmentierung: ein: 1 großes Datagramm aus: 3 kleinere

Zusammensetzen

19







20

Internet Namen und Adressen


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)


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


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


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


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?


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:


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


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


29







30

Erinnerung: Zusammenhang Routing und Weiterleiten


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


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


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


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


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


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


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


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


39

Verteiltes Adaptives Routing

Abstraktion als Graphen: •  Graphknoten sind Router •  Graphkanten sind physische Links

•  Linkkosten: Latenz, €, Auslastung •  Pfadkosten: Summe der

Linkkosten auf dem Weg


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


Statisch oder dynamisch? Statisch: !  Routen ändern sich nur langsam Dynamisch: !  Routen ändern sich schnell

!  Periodische Aktualisierung !  u.U. wegen Änderung der

Linkkosten

41







42

Algorithmus für Distanzvektor-Routing


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


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


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


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


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


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)


X Z 1 2

7

Y

49

Distanzvektor-Routing: Beispiel (II)


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)


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)


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


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







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


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.


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


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)


58

Dijkstra�s Algorithm in Pseudocode


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)


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)


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)


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


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)


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


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)


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


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)


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


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


66

Vergleich zw. Link-State- und Distanzvektor-Verfahren


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







68

Hierarchisches Routing


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


!  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


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)


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!


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


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


Documents

Informations- und Kommunikationssysteme · 2014-04-15 · 3 Kapitel 2.4: Netzwerkschicht • 4.1 Einführung • 4.2 Virtual Circuit und Datagram Netze • 4.3 IP: Internet Protocol