Übungsblatt 9

Übung: 25.06.2004

Aufgabe 1: Backward-Learning

1. Zu welcher Kategorie der Klassifikation der Vorlesung gehört dieser Algorithmus?
   statisches Routing
   zentralisiert adaptives Routing
   isoliert adaptives Routing
   verteilt adaptives Routing

2. Gegeben sei folgendes Netzwerk:

   

   In der untenstehenden Tabelle sind die Routingtabellen der einzelnen Knoten zusammengefaßt, die Eintragungen haben die Form Nachbarknoten/Kosten. Sie stellt den Initialzustand dar, in dem jeder Knoten nur von seinen direkten Nachbarn weiß. Pakete zu anderen Zielen mit noch unbekannten Kosten werden zu dem in der Tabelle angegebenen Nachbarn weitergeleitet (Eintragungen der Form Nachbar/?).

   Es werden nun folgende Pakete versandt (in dieser Reihenfolge):

   • E -> C
   • C -> A
   • E -> C
   Tragen Sie die Veränderungen, die sich durch diese Pakete in den Routingtabellen der Knoten ergeben, in die untenstehende Tabelle ein. Für jeden Knoten sind drei Spalten vorgesehen, die die chronologische Entwicklung darstellen sollen. Wenn also ein alter Wert überschrieben werden soll, streichen Sie den alten Wert bitte nicht durch, sondern setzen den neuen Wert in das unmittelbar rechts davon liegende Feld ein. Es gilt also immer das jeweils am weitesten rechts liegende Feld einer Dreiergruppe.

   
   Die resultierende Routingtabelle hat folgende Einträge (bitte Großbuchstabe, Querstrich (/), Distanz ohne Leerzeichen bzw. ? eingeben und in alle Felder einen Wert eintragen. Falls sich nichts geändert hat, wieder den ursprünglichen.):

   Routingziel	Knoten A	Knoten B	Knoten C	Knoten D	Knoten E	Knoten F
   A	--
   B		--
   C			--
   D				--
   E					--
   F						--

Aufgabe 2: RIP

1. (1 Punkt) Zu welcher Kategorie der Vorlesung eingeführten Klassifikation gehört das RIP Protokoll?
2. (5 Punkte) Im folgenden sehen Sie Ausschnitte aus einer Implementierung des RIP-Protokolls in Pseudocode. Nehmen Sie an, dass diese Implementierung auf jedem Knoten eines Netzwerks läuft.

   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, dass die Entfernung zwischen zwei benachbarten Knoten eine Kosteneinheit beträgt.

   
   // 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
   
   Feld aus Routing_Tabellen_Eintrag r_tab;
   
   
   // Funktion: Aktualisiert die Routing Tabelle eines Knotens
   Update_Routing_Tabelle(Feld aus Tabellen_Update_Eintrag r_up, Leitung l) {

3. (8 Punkte) Gegeben sei das folgende Netzwerk mit den zugehörigen Routing-Tabellen. Im Netzwerk wird das RIP-Routing-Verfahren verwendet. Die Kosten einer Leitung betragen eine Kosteneinheit.

   

   
   Knoten A

   Ziel	Leitung	Kosten
   A	lokal	0
   B	ab	1
   C	ac	1
   D	ab	2
   E	ab	2

   
   Knoten B

   Ziel	Leitung	Kosten
   A	ab	1
   B	lokal	0
   C	ab	2
   D	bd	1
   E	be	1

   
   Knoten C

   Ziel	Leitung	Kosten
   A	ac	1
   B	ac	2
   C	lokal	0
   D	ce	2
   E	ce	1

   
   Knoten D

   Ziel	Leitung	Kosten
   A	bd	2
   B	bd	1
   C	de	2
   D	lokal	0
   E	de	1

   
   Knoten E

   Ziel	Leitung	Kosten
   A	be	2
   B	be	1
   C	ce	1
   D	de	1
   E	lokal	0

   Erläutern Sie Schritt für Schritt, wie die Knoten auf den Ausfall der Verbindung "ab" reagieren. Geben Sie hierzu für jeden Schritt die Routing-Tabellen-Update-Nachrichten an, die zwischen den Knoten ausgetauscht werden. Ein Knoten verschickt immer dann eine Routing-Tabellen-Update-Nachricht, wenn sich Änderungen an seiner Routing-Tabelle ergeben haben.

   Benutzen Sie für Ihre Routing-Tabellen-Update-Nachrichten das folgende Format:
   Sender: Ziel1 - Kosten1, Ziel2 - Kosten2, ...
   Beispiel: Konten A: A - 0, B - 1, C - 1, D - 2, E - 2

4. (4 Punkte) In RIP-gerouteten Netzwerken gibt es Situationen, in denen Pakete im Kreis zirkulieren. Erklären Sie kurz wie eine solche Situation prinzipiell entstehen kann. Wie kann man verhindern, dass ein Netzwerk durch eine ständig steigende Zahl dauerhaft kreisender Pakete lahmgelegt wird.
5. (8 Punkte) Im RIP-gerouteten Netzwerk aus Aufgabenteil (3) sei die Verbindung "ab" weiterhin unterbrochen. Die Routing-Tabellen aller Knoten seien aktualisiert, so dass sie die neue Topologie ohne die Verbindung ab korrekt wiederspiegeln. Nun wird auch die Verbindung "ce" unterbrochen. Erklären Sie, welches Routing-Problem entsteht, wenn 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. Beschreiben Sie ausführlich, wie sich die Knoten A und C in dieser Situation verhalten. Machen Sie einen Vorschlag, wie man dieses Problem für die Knoten A und C lösen könnte.

Aufgabe 3: OSPF

Berechnen Sie den kürzesten Weg aus der Sicht des Knoten A nach dem Algorithmus von Dijkstra. Verwenden Sie dazu die folgende Tabelle und tragen Sie dort jeden Schritt in eine eigene Zeile ein. Tragen Sie dem im jeweiligen Schritt bestimmten kürzesten Pfad zu einem Knoten in die Spalte "kürzeste Pfade" inklusive der Kosten für diesen Pfad sowie die im jeweiligen Schritt entdeckten Pfade inklusive der Kosten für diesen Pfad in die Spalte "entdeckte Pfade". Verwenden Sie für einen Pfad die Notation "Knoten - Konten - ... : Kosten" (z.B. "A - B - C: 5"). Der erste Schritt ist in der Tabelle bereits enthalten.

kürzeste Pfade	entdeckte Pfade
A: 0	A - B : 3, A - D : 6