Universität Mannheim
Lehrstuhl für Praktische Informatik IV
Prof. Dr. W. Effelsberg
Jürgen Vogel
Thomas Haenselmann
Stephan Kopf

Multimedia-Systeme: Übungsblatt 9 (Musterlösung)

Übung: 20.12.2002

Aufgabe 1: Wüstenvölker

Die Wüstenbewohner Zarkotiens leben verstreut in Oasen. Da Reisende nicht in der Wüste übernachten können, müssen sie allabendlich eine Oase erreichen. Da die Oasen außerdem weit verstreut liegen, können sie in einem Tagesmarsch nur bis zu genau einer anderen Oase reisen. Die Oasen, die von A aus in einer Tagesreise erreicht werden können, heißen Nachbarn von A.

Erläutern Sie kurz, wie die örtlichen Verkehrsämter nur durch Absprache mit ihren jeweiligen Nachbarn in einem iterativen Prozeß kürzeste Reiserouten zu allen Zarkotischen Oasen ermitteln können. Lehnen Sie sich dabei an das in der Vorlesung behandelte "Routing Information Protocol - RIP" an.

In Anlehnung an RIP verwaltet jede Oase eine Tabelle mit "Distanzvektoren" zu allen anderen Oasen. Ein Distanzvektor besagt dabei, auf welchem Weg die Oase verlassen werden muß, um eine bestimmte andere Oase zu erreichen und wie viele Tagesmärsche diese entfernt ist. In regelmäßigen Abständen sendet dann jede Oase einen Boten aus, der diese Distanzvektoren den benachbarten Oasen mitteilt. Erfährt eine Oase durch den Boten von einem kürzeren Weg zu einem bestimmten Ziel, korrigiert diese ihre Tabelle, indem sie als Distanzvektor die Nachbaroase angibt, aus der der Bote kam und als Entfernung den Wert aus der Tabelle des Boten plus einem zusätzlichen Tagesmarsch annimmt.

Am Königshof Zarkotiens werden alljährlich den verdientesten Bewohnern, einem aus jeder Oase, Ehrenorden verliehen. Zum Empfang der Orden reisen die Ausgezeichneten jeweils auf dem kürzesten Weg zum Königshof. In jeder Oase auf ihrem Weg, werden diese Reisenden mit großer Ehre empfangen. Die Tore, durch die solche Reisenden eine Oase erreichen, heißen daher "Tore der Ehre". Die Tore, durch die die Reisenden am nächsten Tag Richtung Königshof weiterreisen, heißen "Königstore".

Durch welches der folgenden Verfahren können Botschaften des Königs optimal (d.h. auf dem kürzesten Weg und mit möglichst wenigen Duplikaten) an sein Volk verbreitet werden? Kreuzen Sie genau eine Alternative an!

Kopien eintreffender Botschaften werden an alle Nachbaroasen weiter gesandt, außer zu derjenigen von der man die Botschaft gerade erhalten hat.
Boten mit Kopien der Nachrichten werden über die Wege zu Nachbaroasen weiter gesandt, die nicht durch Königstore führen.
X Boten mit Kopien der Nachrichten werden über die Wege zu Nachbaroasen weiter gesandt, die durch Tore der Ehre führen.
Boten mit Kopien der Nachrichten werden über die Wege zu Nachbaroasen weiter gesandt, die durch Königstore, aber nicht durch Tore der Ehre führen.
Um überflüssige Botengänge zu vermeiden, müssen sich die Nachbaroasen absprechen, wer die Botschaften weiter verbreiten soll.
Der Königshof selbst muß die Verbreitung der Botschaften regeln, da die Oasen alleine keine optimale, vollständige Verbreitung erreichen können.

Entspricht das unter (b) ausgewählte Verfahren einem im Internet angewandten Routing-Algorithmus? Falls ja, wie heißt dieses?

Reverse Path Broadcasting

Welche Probleme kommen auf die örtlichen Verkehrsämter Zarkotiens zu, wenn man das bisherige Verfahren der Wegewahl für Reisen in Oasen anderer Reiche beibehält? Welche Lösung könnte man, in Anlehnung an das Routing im Internet, einführen? Erläutern Sie dieses kurz.

Problem: Tabelle wird unter Umständen sehr groß, es dauert lange, bis alle Wege bekannt gemacht sind. Lösung: Einrichtung eines zusätzlichen Gateway-Gateway Protokolls: Soll eine Nachricht an eine Oase ins Ausland geschickt werden, so wird diese Nachricht an ein "Default Gateway" gesendet (Beispielsweise eine Oase, die auf der Grenze liegt).

Aufgabe 2: Full Topology Routing

Das Routing Information Protocol (RIP) basiert auf einem Broadcast-Protokoll, bei dem benachbarte Gateways alle 30 sec Auszüge ihrer Routingtabellen (Netzadresse,Distanz) austauschen. Die Routingentscheidung basiert normalerweise auf dem Hopcounter (=Anzahl Zwischenstops bis zum Empfangsnetz). Ein Maximalwert von 16 wird verwendet, um anzuzeigen, daß ein Netz nicht erreichbar ist. Die Routingtabelle enthält u.a. Einträge mit Zieladresse, Kosten (1-16), nächstem Knoten im Pfad und diverse Timer. Betrachten Sie folgendes Netz aus Netzen.

netofnets

(a) Es sei momentan im Initialzustand, d.h. jedes Gateway kennt nur die Netze, mit denen es unmittelbar verbunden ist. Die Bezeichnungen an den Kanten geben die Kosten für die jeweilige Verbindung an. Wie lange braucht es, bis das Gateway G7 die Distanz zu Netz x kennt.

Die richtige Antwort ist 120 Sekunden (Nachricht geht von G6->G3->G2->G4/5->G7)

(b) Was passiert, wenn Gateway 2 kurz nachdem es die Nachricht (y,1) an G1 weitergegeben hat, die Verbindung zu Netz y verliert? Welche Nachricht schickt es 60 sec später an G1?

Hier gibt es zwei Loesungen, je nachdem wie "intelligent" RIP ist:

In der einfacheren Version 1 enthaelt die ausgetauschte Routing-Tabelle nur den Zielknoten und die Kosten. Folglich kann G2 nicht erkennen, dass der von G1 uebermittelte bessere Pfad (besser als infinity) ueber G2 laeuft und deswegen keine reale Alternative ist. G2 lernt also, daß die kürzeste Verbindung zu Netz y über G1 die Länge 3 hat und gibt diese Nachricht auch 60 sec später weiter: (y,3). Wird ein Paket dann über G1 an Netz y gesendet, kreist es zwischen G1 und G2, bis sein Hopcounter zu groß wird
Hinweis: Für die Kosten ist bei RIP nur der Hopcount relevant, nicht die tatsächlichen Kosten an den Kanten!
Die richtige Antwort ist hier also (y,3)
In Version 2 werden neben Zielknoten und Kosten auch der naechste Knoten im Pfad uebertragen. Daher kann G2 also die Schleife erkennen und behaelt wie G1 den Eintrag Infinity in seiner Routing-Tabelle.
Die richtige Antwort ist hier also (y,16)
Beide Antworten wurden als richtig gewertet, auch wenn die automatisch generierte Mail etwas anderes behaupten sollte.

Aufgabe 3: Multicast

Erklären Sie kurz, was man unter Multicast versteht. Nennen Sie zwei typische Einsatzgebiete, bei denen eine Multicastübertragung anderen Übertragungsformen vorzuziehen ist. Begründen Sie, warum.

Multicast bedeutet, daß nur eine einzige Kopie eines Datenpaketes von einem Sender an eine Gruppe von Empfängern gesendet wird. Dieses Verfahren is weitaus effizienter als mehrere Kopien des selben Datenpaketes an mehrere Empfäger zu versenden. Es wird weniger Netzlast verursacht und die Sender werden entlastet.

Einsatzgebiete:

Videoconferncing
Tele-Cooperation
near Video on Demand
Verteilte Kommunikation

vogel@informatik.uni-mannheim.de