b) Gegeben sei das folgende Netzwerk mit den zugehörigen Routing-Tabellen. Im
Netzwerk wird das RIP2-Routing-Verfahren verwendet. Die Kosten einer Leitung betragen
eine Kosteneinheit.
Besprechung am 23.11.2000
Aufgabe 1 Distance Vector Routing / RIP
Im Folgenden sehen Sie Ausschnitte aus einer Implementierung des RIP2-Protokolls in Pseudocode. Nehmen Sie an, daß diese Implementierung auf jedem Knoten eines Netzwerks läuft.
a) Vervollständigen Sie die Funktion "Update_Routing_Tabelle" in Pseudocode. Diese Funktion soll die Routing-Tabelle des Knotens aktualisieren und wird aufgerufen, sobald ein Knoten eine Routing-Tabellen-Update-Nachricht empfängt. Als Parameter wird das Tabellen-Update selbst sowie die Leitung, auf der das Update empfangen wurde, übergeben. Die Routing-Tabelle des Knotens ist im Feld r_tab gespeichert. Zur Vereinfachung können Sie annehmen, daß die Entfernung zwischen zwei benachbarten Knoten eine Kosteneinheit beträgt. Von der Funktion soll true zurückgegeben werden, wenn die Routing Tabelle verändert wurde, sonst false.
// Datenstrukturen für die Einträge der Routing Tabelle
// und den Routing Tabellen Updates
Routing_Tabellen_Eintrag {
Zielknoten z;
Leitung l;
Kosten k;
}
Tabellen_Update_Eintrag {
Zielknoten z;
Kosten k;
}
// Routing Tabelle des Knotens - als globale Variable (nicht für
realen Einsatz geeignet!)
Feld aus Routing_Tabellen_Eintrag r_tab;
// Funktion: Aktualisiert die Routing Tabelle eines Knotens
boolean Update_Routing_Tabelle (Feld
aus Tabellen_Update_Eintrag r_up, Leitung l) {
....
}
Lösung:
boolean update = false
boolen gefunden = false
Für alle Elemente e_up von r_up führe aus {
gefunden = false
Für alle Elemente e_tab von r_tab führe aus {
Falls (e_tab.z = e_up.z) {
gefunden = true
Falls (e_tab.l = l) {// diesen Wert müssen wir auf jeden fall annehmen
Falls (e_up.k + 1 != e_tab.k) { // update nötig
Falls (e_up.k = -16 oder e_up.k = 16) { // plus/minus unendlich
e_tab.k=16
} sonst {
e_tab.k = e_up.k + 1
}
update = true
}
} sonst Falls (e_up.k + 1 < e_tab.k) {
e_tab.k = e_up.k + 1
e_tab.l = l
update = true
}
}
}
Falls (nicht gefunden) {
füge neuen Eintrag e_up in r_tab ein
update = true
}
}
b) Gegeben sei das folgende Netzwerk mit den zugehörigen Routing-Tabellen.
Im
Netzwerk wird das RIP2-Routing-Verfahren verwendet. Die Kosten einer
Leitung betragen
eine Kosteneinheit.
Knoten A: Knoten B:
Ziel Leitung Konsten Ziel Leitung Kosten
A lokal 0 A ab 1
B ab 1 B lokal 0
C ac 1 C ab 2
D ab 2 D bd 1
E ab 2 E be 1
Knoten C: Knoten D:
Ziel Leitung Konsten Ziel Leitung Kosten
A ac 1 A bd 2
B ac 2 B bd 1
C lokal 0 C de 2
D ce 2 D lokal 0
E ce 1 E de 1
Knoten E:
Ziel Leitung Konsten
A be 2
B be 1
C ce 1
D de 1
E lokal 0Erläutern Sie Schritt für Schritt, wie die Knoten auf den Ausfall der Verbindung ab reagieren.
Benutzen Sie für Ihre Routing-Tabellen-Update-Nachrichten das folgenden
Format:
Von Sender nach Empfänger: Ziel1 - Kosten1, Ziel2 - Kosten2, ...
Verwenden Sie +/-u für +/- Unendlich
Beispiel: Von A nach B: A - 0, B - -u, C - 1, D - -u, E - -u
Lösung:
Schritt 1:
Von A nach C: A - 0, B - +u, C - -u, D - +u, E +u
Von B nach D: A - +u, B - 0, C - +u, D - -u, E - 1
Von B nach E: A - +u, B - 0, C - +u, D - 1, E - -u
Schritt 2:
Von C nach A: A - -u, B - +u, C - 0, D - 2, E - 1
Von C nach E: A - 1, B - +u, C - 0, D - -u, E - -u
Von D nach B: A - +u, B - -u, C - 2, D - 0, E - 1
Von D nach E: A - +u, B - 1, C - -u, D - 0, E - -u
Von E nach B: A - +u, B - -u, C - 1, D - 1, E - 0
Von E nach C: A - +u, B - 1, C - -u, D - 1, E - 0
Von E nach D: A - +u, B - 1, C - 1, D - -u, E - 0
Schritt 3:
Von A nach C: A - 0, B - u, C - -u, D - -u, E - -u
Von B nach D: A - +u, B - 0, C - 2, D - -u, E - 1
Von B nach E: A - +u, B - 0, C - -u, D - 1, E - -u
Von C nach A: A - -u, B - 2, C - 0, D - 2, E - 1
Von C nach E: A - 1, B - -u, C - 0, D - -u, E - -u
Von E nach B: A - 2, B - -u, C - 1, D - 1, E - 0
Von E nach C: A - -u, B - 1, C - -u, D - 1, E - 0
Von E nach D: A - 2, B - 1, C - 1, D - -u, E - 0
Schritt 4:
Hier schicken A B D ihre Distannzvektoren, die aber keine
Änderungen in den Routintabellen auslösen.
Schritt 5:
- Ende
c) Bei distanz Vektor Routing Protokollen besteht die Gefahr daß
es zu Routing Schleifen
kommen kann, wenn man keine Gegenmaßnahmen ergreift. Erklären
Sie anhand des oben angegebenen
Netzes, was passieren muß, damit es zu einer 2er Routing Schleife
kommt. Gehen Sie dabei davon
aus, daß ein naives Distanz Vektor Routing Protokoll verwendet
wird und nicht RIP.
Lösung:
Zu einer Routing Schleife könnte es kommen, wenn auch die Verbindung
ce unterbrochen wird und der Knoten A (z.B. durch einen ablaufenden Timer)
direkt nach der Unterbrechung der Verbindung ce eine Routing-Tabellen-Update-Nachricht
an Knoten C schickt, noch bevor dieser ein Tabellen-Update (das die Unterbrechung
der Verbindung enthält) an Knoten A verschicken kann. Genauso kann
es auch sein, daß
die Nachricht von C nach A verloren geht und dann A irgendwann seinen
Distanzvektor zu C schickt.
d) Wie wird in RIP1/2 dieses Problem angegangen? Welche Anomalien kann es dennoch geben?
Lösung:
Mit Hilfe von Split Horizon (mit oder ohne poisonous reverse). Mit Hilfe von Triggered updates.
Trozdem kann es noch zu einer 3er Schleife kommen, bei der counting
to infinity durchgeführt werden
muß um das Problem zu lösen.
Aufgabe 2 Link State Routing / OSPF
Gegeben sei wieder das gleiche Netzwerk wie in Aufgabe 1 b). Nun fallen
die Links
ab und ce aus. Nehmen Sie an, daß aus nicht näher spezifizieren
Gründen das Fluten
der Informationen über die Topoligieänderung zwischen A und
C nicht funktioniert. D.h.
A erhält keine Informationen über den Ausfall des Links ce
und C keine über den Ausfall
des Links ab.
a) Wie sehen die Datenbanken der Netzwerktopologie in A und in C aus?
Lösung:
A C
From To Link Cost Number From To Link Cost Number
A B ab inf 2 A B ab 1 1
B A ab inf 2 B A ab 1 1
A C ac 1 1 A C ac 1 1
C A ac 1 1 C A ac 1 1
B D bd 1 1 B D bd 1 1
D B bd 1 1 D B bd 1 1
B E be 1 1 B E be 1 1
E B be 1 1 E B be 1 1
C E ce 1 1 C E ce inf 2
E C ce 1 1 E C ce inf 2
D E de 1 1 D E de 1 1
E D de 1 1 E D de 1 1
b) Verwenden sie den shortest path first Algorithmus um die Routingtabellen
für
A und C zu bestimmen, gehen Sie dabei davon aus, dass jede direkte
Verbindung
zwischen zwei Knoten die Kosten 1 hat!
Lösung:
Für die Bestimmung der Routing Tabelle von A gilt:
E={A}
R={B, C, D, E}
O={A-C-1}
Kürzeste Pfade{}
E={A, C}
R={B, D, E}
O={A-C-E-2}
Kürzeste Pfade{A-C-1}
E={A, C, E}
R={B, D}
O={A-C-E-B-3, A-C-E-D-3}
Kürzeste Pfade{A-C-1, A-C-E-2}
E={A, C, E, B}
R={D}
O={A-C-E-D-3}
Kürzeste Pfade{A-C-1, A-C-E-2, A-C-E-B-3}
E={A, C, E, B, D}
R={}
O={}
Kürzeste Pfade{A-C-1, A-C-E-2, A-C-E-B-3, A-C-E-D-3}
Die Bestimmung der Routing Tabelle von C erfolgt analog.
A C
To Link To Link
A local ac
B ac ac
C ac local
D ac ac
E ac ac
c) Was passiert nun wenn A ein Paket nach E schicken möchte!
Lösung:
Es kreist!
d) Was unternimmt OSPF um dieses Problem zu verhindern?
Lösung:
Das Fluten wird mit Bestätigungen zuverlässig gemacht.
Aufgabe 3 OSPF (alte Klausuraufgabe)
a) Bestimmund der Routingtabelle
Gegeben sei das nachstehende Netzwerk in dem OSPF verwendet wird. Die
Zahl
über einer Kanten gibt deren Kosten an. Führen Sie die Berechnung
der
Routing Tabelle in A schrittweise durch. Für jeden Schritt der
Berechnung
nennen Sie bitte die Menge der besuchten Knoten (E), die Menge der
möglichen
Pfade für den nächsten Schritt(O) und die Menge der kürzesten
Pfade (K).
Lösung:
E=A
O=A-D-1, A-C-6, A-B-10
K=leer
E=A, D
O=A-D-E-3, A-D-B-6, A-C-6, A-B-10
K=A-D-1
E=A, D, E
O=A-D-E-C-4, A-D-B-6, A-C-6, A-B-10
K=A-D-1, A-D-E-3
E=A, D, E, C
O=A-D-B-6, A-B-10
K=A-D-1, A-D-E-3, A-D-E-C-4
E=A, D, E, C, B
O=leer
K=A-D-1, A-D-E-3, A-D-E-C-4, A-D-B-6
b) Linkausfall
In dem Netz der vorhergehenden Teilaufgabe fallen nun die Links AC und
DE aus.
Danach fällt auch der Link AD aus. Wiederum eine Zeit später
fährt der Link
AC wieder hoch. Es soll weiterhin OSPF als Routing Protokoll verwendet
werden.
Welches Problem ist durch diesen Vorgang entstanden?
Lösung:
Es entstanden 2 Partitionen. Die Partition mit den Knoten A und D hat
sich
verändert, da die Kante AD ausgefallen ist. Davon wissen die Knoten
C und E
nichts, da sie zum Zeitpunkt des Ausfalls von AD nicht erreichbar waren.
c) Lösung des Problems:
Beschreiben Sie welche Art von Informationen bei OSPF zwischen A und
C
nach dem Hochfahren des Links AC ausgetauscht werden, um dieses Problem
zu beheben.
Lösung:
Zunächst werden database description packets ausgetauscht. Diese
identifizieren
die Einträge in der Datenbank und die jeweilige Nummer: z.B.
From A, to B, Number 3.
Der Austausch findet zwischen den beiden Knoten statt, zwischen denen
die Verbindung
wieder hergestellt wurde. Diese Beschreibung wird vom jeweiligen Empfänger
überprüft:
sind Einträge vorhanden, die eine höhere Nummer haben, als
in der eigenen Datenbank,
dann werden diese Einträge mit Hilfe von link state request packets
angefordert.
Aufgabe 4 Exterior Gateway Routing Protocols / BGP
a) Warum verwendet man Exterior Gateway Routing Protocols? Was ist deren
Aufgabe?
Warum benötigt man hier eigenständige Protokolle und verwendet
nicht OSPF oder RIP?
Welche wichtigen Probleme sind bei Exterior Gateway Routing zu lösen?
Dies ist eine Wissensaufgabe, wie sie auch in der Klausur vorkommen
kann - bitte beantworten
Sie die Frage BEVOR Sie in den Unterlagen nachschauen.
Lösung
Man verwendet Exterior Gateway Routing Protocols für das Routing
zwischen autonomen Systemen. Diese
Protokolle sollen es insbesondere ermöglichen eine große
Anzahl von AS miteinander zu verbinden.
Außerdem soll es möglich sein das Routing auf (Firmen-)
politischer Ebene zu beeinflussen. OSPF und RIP
sind hier nicht geeignet, da diese von einer kleinen Anzahl von Routern
ausgehen, die von einer einzigen
Administration mit einer homogenen Zielvorstellung verwaltet wird.
Dies ist für exterior gateway routing aber
nicht der Fall. Insbesondere muessen für exterior gateway routing
die folgenden drei Probleme glöst werden:
Routing nach (Firmen-)Politiken
Verhindern der Class-B exhaustion
Verhindern der Routing Table Explosion
b) Gegeben sei das folgende Netzwerk von AS:
Bestimmen Sie die das Attribut AS_PATH und Network Reachability Informationen,
die von R1 nach R3,
von R2 nach R3, von R5 nach R7, von R6 nach R7 und von R8 an R9 nach
BGP-4 übermittlen würde, wenn
die Verbindung in der genannten Reihenfolge hochfahren. Gehen Sie dabei
davon aus, daß in allen Systemen
eine maximale Aggregation als Politik für BGP-4 gewählt wurde.
Lösung:
R1 gibt an R3 den Eintrag: sequence(AS1) 24/192.12.2.0 weiter
R2 gibt an R3 den Eintrag: sequence(AS3) 24/192.12.3.0 weiter
in AS2 wird das aggregiert und
R5 gibt an R7 den Eintrag: sequence(AS2) set(AS1, AS3) 22/192.12.0.0
weiter
R6 gibt an R7 den Eintrag: sequence(AS4) set(....) 22/192.12.4.0 weiter
in AS7 wird das aggregiert und
R8 gibt an R9 den Eintrag: sequence(AS7) set(AS1, AS2, AS3, AS4, ...) 16/192.12.0.0 weiter
c) Welche Informationen gehen durch die Aggregation (s. c Teil) verloren?
Lösung:
Es gehen die Informationen darüber verloren, welche Autonomen Systeme
von einer
Route tatsächlich durchquert werden. Insbesondere weis Router
R9 nur, daß alle Adressen
16/192.12.0.0 über AS7 geroutet werden, ob dann AS2 oder AS4 oder
ein anderes AS
weiter durchquert werden ist nicht festzustellen.