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

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

Übung: 5.12.2003

Aufgabe 1: Flußkontrolle

Zwei Stationen sind mit einem Satellitenkanal verbunden. Die Übertragungsrate beträgt 64 kbit/s, die Ausbreitungsgeschwindigkeit ist die Lichtgeschwindigkeit (300.000 km/s), die Paketgröße beträgt 1000 Bit. Zur Flußkontrolle wird das Sliding-Window-Verfahren eingesetzt. Geostationäre Satelliten befinden sich in einer Höhe von 36.000km.

1. Welcher Anteil der Kapazität wird bei einer Fenstergröße von 10 Paketen erreicht?


Voraussetzungen:

  • Die Entfernung eines geostationären Satelliten zur Erde beträgt 36.000 km
  • Die Zeitdauer vom Beginn des Sendens eines Pakets bis zur Ankunft des Acknowledgements ist die Summe aus der eigentlichen Zeit, die für das Senden benötigt wird, sowie zweimal der Zeit, die ein Paket vom Sender zum Empfänger unterwegs ist (Paket und Ack). Die Größe des Ack-Packets wird dabei vernachlässigt.
Sendezeit und Laufzeit: Die eigentliche Sendezeit eines Paketes hängt von der Übertragungsrate ab. Ein Paket der Größe 1.000 bit wird bei 64k Bit/s = 65.536 bit/s in 1.000/65.536 Sekunden gesendet. Bei einer Entfernung von 36.000*2 zwischen den Partnern benötigt ein Bit eine Zeit von 72.000/300.000 = 0,24 Sekunden.

Gesamtzeit: Daraus ergibt sich eine Gesamtzeit von 1.000/65.536 + 2*0,24 = 0,4953 Sekunden.

Auslastung: Beträgt nun die Fenstergröße 10, dann kann der Sender insgesamt nur 10*1000/65536 = 0,1526 Sekunden lang senden. Es ergibt sich eine Auslastung von 0,1526/0,4953 = 30,8%.

2. Wie groß muß das Fenster mindestens sein, wenn die volle Kapazität genutzt werden soll?

Um die volle Kapazität nutzen zu können, muß die Fenstergröße mindestens so groß sein, daß der der Sender genau in dem Moment anfangen müßte zu warten, zu dem das erste Ack eintrifft. D.h., der Sender muß mindestens 0,4953 Sekunden senden können. Die Fenstergröße ergibt sich damit aus x*1.000/65536 = 0,4953, d.h. x = 32,45.


Aufgabe 2: Routing

Bestimmen Sie den optimalen Weg von A nach F gemäß dem Kürzester-Weg-Algorithmus in folgendem Netzwerk. Die Zahlen an den Kanten geben die Gewichte an.

Netzwerk

Dijkstra-Algorithmus

aus: Ottmann, T. und Widmayer, P. (1993). Algorithmen und Datenstrukturen.

Das Verfahren besteht darin, sukzessive für jeden Knoten $v \in V$ den kürzesten Weg vom Startknoten $s$ nach $v$ zu bestimmen. Dazu wird eine Menge $S$ von Knoten betrachtet und schrittweise vergrößert, für die der kürzeste Weg von $s$ aus bereits bekannt ist. Jedem Knoten $v \in V$ wird eine Distanz $d(v)$ zugeordnet. Falls $v \in S$ ist, ist $d(v)$ die Länge des kürzesten Weges von $s$ nach $v$. Falls $v \not\in S$ ist, so ist $d(v)$ die Länge eines kürzesten Weges der Form $s\ldots wv$, mit $w \in S$, d.h. $d(v) = \min(\{d(w)+l(wv : w \in S\})$ bzw. $d(v) = \infty$, falls ein solcher Weg nicht existiert.

Anfangs ist $d(s) = 0$, und für alle von $s$ verschiedenen Knoten $v \in V$ ist $d(v) = \infty$, und $S$ ist leer. Dann wird $S$ nach dem Prinzip ,,Knoten mit kürzester Distanz von $s$ zuerst`` schrittweise wie folgt vergrößert, bis $S$ alle Knoten $V$ des Graphen enthält:

  1. Wähle Knoten $v \in V\backslash S$ mit minimaler Distanz $d(v)$.
  2. Nimm $v$ zu $S$ hinzu.
  3. Für jede Kante $vw$ von $v$ zu einem Knoten $w \not\in S$ ersetze $d(w)$ durch $\min(\{d(w), d(v) + l(vw)\})$.

Die Ermittlung der Knoten, die zum kürzesten Weg gehören erhält man durch folgende Erweiterung: Für jeden Knoten $w$ merkt man sich zusätzlich zur Distanz $d(w)$ den ,,Elternknoten`` $P(w)$ über den dieser Knoten erreicht wurde. Analog zur Modifizierung der Distanz wird auch $P(w)$ solange verändert, bis $w$ in $S$ aufgenommen wurde. Den kürzesten Pfad erhält man, in dem man beim Zielknoten $z$ anfängt und über $P(z)$ usw. den jeweiligen Vorgänger ermittelt.

Lösung

  1. Initialisierung:
    $S = \emptyset$
    $d(A) = 0$, $d(B) = d(C) = \ldots = d(F) = \infty$
    $P(A) = P(B) = \ldots = P(F) = \Omega$
  2. Wähle Knoten $A$, da $d(A)$ minimal
    Betrachte die zu $A$ benachbarten Knoten $v \not\in S$ und modifiziere die Distanzen und Elternknoten:
    $S = \{ A \}$
    $d(B) = \min(\{\infty, 0 + 3\}) = 3, P(B) = A$
    $d(C) = \min(\{\infty, 0 + 2\}) = 2, P(C) = A$
    $d(D) = \min(\{\infty, 0 + 6\}) = 6, P(D) = A$
    $d(E) = \min(\{\infty, 0 + 4\}) = 4, P(E) = A$

  3. Wähle Knoten $C$, da $d(C)$ minimal
    Betrachte die zu $C$ benachbarten Knoten $v \not\in S$ und modifiziere die Distanzen und Elternknoten:
    $S = \{ A, C \}$
    $d(E) = \min(\{4, 2 + 1\}) = 3, P(E) = C$

  4. Wähle Knoten $E$, da $d(E)$ minimal
    Betrachte die zu $E$ benachbarten Knoten $v \not\in S$ und modifiziere die Distanzen und Elternknoten:
    $S = \{ A, C, E \}$
    $d(D) = \min(\{6, 3 + 2\}) = 5, P(D) = E$
    $d(F) = \min(\{\infty, 3 + 4\}) = 7, P(F) = E$

  5. Wähle Knoten $D$, da $d(D)$ minimal
    Betrachte die zu $D$ benachbarten Knoten $v \not\in S$ und modifiziere die Distanzen und Elternknoten:
    $S = \{ A, C, E, D \}$
    $d(B) = \min(\{3, 5 + 5\}) = 3$
    $d(F) = \min(\{7, 5 + 1\}) = 6, P(F) = D$

  6. Wähle Knoten $B$, da $d(B)$ minimal
    Betrachte die zu $B$ benachbarten Knoten $v \not\in S$ und modifiziere die Distanzen und Elternknoten:
    $S = \{ A, C, E, D, B \}$
    $d(F) = \min(\{6, 3 + 5\}) = 6$

  7. $S = \{ A, C, E, D, B, F \}$. Alle Knoten wurden betrachtet, die Distanz von $A$ zu $F$ beträgt 6. Der Weg (ermittelt durch Rückwärtsverfolgung) lautet A-C-E-D-F.


Aufgabe 3: Multimediaübertragung in klassischen Datennetzen

Welche Mechanismen in paketvermittelnden Datennetzen verhindern die Übertragung isochroner Datenströme? (mit Begründung)

Ein paar Beispiele (es gibt sicherlich noch mehr):

Schicht 2:
  • Medium Access Control bietet keine Garantien über maximales Delay. Wiederholte Kollisionen im Ethernet können das Medium im Prinzip beliebig lange blockieren.
Schicht 3:
  • Bei den im Internet verwendeteten Routingprotokollen können sich natürlich Pfade ändern, und wenn das während einer "isochronen" Übertragung passiert wird sich i.A. das Delay stark verändern.
  • Das Pufferdelay von Paketen in Routern is abhängig von der Netzlast bei dem entsprechenden Router (konkurrierender Datenverkehr).
Schicht 4:
  • Übertragungswiederholung bei Paketfehlern
  • Flußkontrolle
  • Überlastkontrolle (Congestion Control)




vogel@informatik.uni-mannheim.de