Übungsblatt 2

Besprechung am 28.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) {
....
}

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   0

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

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.

d) Wie wird in RIP1/2 dieses Problem angegangen? Welche Anomalien kann es dennoch geben?
 

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?

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!

c) Was passiert nun wenn A ein Paket nach E schicken möchte!

d) Was unternimmt OSPF um dieses Problem zu verhindern?

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).

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?

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.
 

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.

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.

c) Welche Informationen gehen durch die Aggregation (s. c Teil) verloren?