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!
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 local
C ac ac
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 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.