Universität Mannheim
Lehrstuhl für Praktische Informatik IV
Prof. Dr. W. Effelsberg
Gerald Kühne
Christoph Kuhmünch

Multimedia-Systeme: Übungsblatt 7

Übung: 12.06.99

Die Aufgaben, die auf dieser Seite ausgefüllt werden können, werden auch über das Web ausgewertet. Dazu muß die Matrikelnummer eingegeben werden und das Ganze abgeschickt werden. Voraussetzung ist allerdings, daß der Studierende auch für die elektronische Auswertung angemeldet ist.

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.
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.
b) 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".
c) 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.
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.
d) Entspricht das unter (b) ausgewählte Verfahren einem im Internet angewandten Routing-Algorithmus? Falls ja, wie heißt dieses?
e) 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.


Aufgabe 2: 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.

60 sec
90 sec
120 sec
150 sec

(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?

(y,16)
(y,15)
(y,4)
(y,3)
(y,2)

Aufgabe 3: Empirical Envelope

Der Empirical Envelope eines Medienstroms der Länge T ist folgendermaßen definiert:

empirical_envelope

Sei a(t) die Größe des Frames t gemessen in Bytes. Geben Sie eine Definition für A[t1,t2] der obigen Formel in Abhängigkeit von a(t) an.

(a)
formel1
(b)
formel2
(c)
formel3

Aufgabe 3: Media Scaling und hierarchische Kodierung

Konventionelle Verfahren wie z.B. MPEG-1 kodieren einen eingehenden Medienstrom in einen einzigen (komprimierten) ausgehenden Strom. Bei der Hierarchischen Kodierung wird der eingehende Medienstrom in mehrere voneinander abhängige Schichten aufgeteilt.

(a) Ordnen Sie die Beispiele den Formen der hierarchischen Kodierung für Video zu!

Formen der hierarchischen Kodierung:

Beispiel:

  1. Die Frequenzen des DCT-transformierten Bildes werden nach ihrer Wichtigkeit sortiert. Auf dem Base-Layer werden die wichtigeren Frequenzen übertragen, auf dem Enhancement-Layer die weniger wichtigen Frequenzen.

  2. Die Einzelbilder des Videos werden auf auf zwei Ebenen aufgeteilt: Der Base-Layer enthält alle ungeraden Bilder, der Enhancement-Layer alle geradzahligen Bilder.

  3. Die Einzelbilder werden in ihrer Länge und Breite halbiert. Auf dem Base-Layer wird das verkleinerte Bild übertragen. Das verkleinerte Bild wird anschließend wieder auf Originalgröße skaliert und der Unterschied zwischen Originalbild und Vergrößerung auf dem Enhancement-Layer übertragen.

In der nachfolgenden Aufgabe wird ein Verfahren zur hierarchischen Kodierung von Videoströmen erarbeitet.

Layered DCT

Dieses Verfahren ist auch als "Progressive JPEG" Standard bekannt und ist von der Independent JPEG Group standardisiert worden: Jedes Einzelbild des Videostroms wird analog zum JPEG-verfahren mit Hilfe der DCT in den Frequenzraum transferiert. Anschließend werden die DC-Koeffizienten der Blöcke in einem einzigen Schritt quantisiert. Diese werden nach der Entropie-Kodierung in der ersten Schicht übertragen. Im Gegensatz dazu werden die AC-Koeffizienten in mehreren Schritten quantisiert. Jeder Quantisierungsschritt erzeugt eine Bit-Plane, die in der nächsthöhren Schicht überttragen werden. Beispielsweise wird die Bit-Plane des höchsten Bits (Most Significant Bit MSB) der AC-Koeffizienten in der zweiten Schicht übertragen, das zweithöchste Bit in der dritten Schicht usw.

(b) Welche Form der Hierarchisierung trifft das hier beschriebene Verfahren am besten?

zeitliche Hierarchisierung
räumliche Hierarchisierung
Hierarchisierung der Frequenzen

Gegeben sei nun die folgende Matrix (8 Bit, binäre Darstellung), die einen Block eines Bildes repräsentiert, der bereits DCT transformiert worden ist:

01111011 01101110 00010010 00000010
01101010 01100000 00001110 00001001
00010110 00011011 00001100 00000111
00101010 00001010 00000101 00000000

(c) Welcher Wert wird in der 1. Schicht übertragen?

00000000
01111011
10000100
00010010

(d) Geben Sie die Bitplane an, die in der 2. Schicht übertragen wird!

000000000000000
011110110101010
101101001110100
110100000000000

(e) Geben Sie die Bitplane an, die in der 3. Schicht übertragen wird!

101101001110100
000000000000000
110100000000000
011110110101010

Anmerkung: Die Matrix wird in der üblichen Reihenfolge schräg beginnend links oben in der Matrix gescannt (s. Abbildung).

dct-scan

Aufgabe 4: Hierarchische Übertragung

In der vorherigen Aufgabe wurde mittels des Layered DCT Verfahrens ein Videostrom in mehrere Schichten unterteilt. Dieser hierarchische Datenstrom soll nun per IP-Multicast zu einer Reihe von Empfängern versendet werden, die eine unterschiedlich gute Netzwerkanbindung besitzen (siehe Abbildung).

netzbsp

Unglücklicherweise bietet IP zur Zeit noch keinerlei Verfahren zur intelligenten Filterung von Datenströmen innerhalb des Netzes. D.h. im Falle eines Engpasses werden Pakete zufällig verworfen.

Entwickeln Sie ein Verfahren, das mit Hilfe mehrerer Multicast-Gruppen einen hierarchisch Kodierten Datenstrom überträgt!

(Tip: Jede Schicht wird auf einer anderen Multicast-Gruppe versendet.)

Aufgabe 5: Multicast

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

(b) Im Internet wird im sogenannten MBone (Multicast Backbone) IP-Multicast als Erweiterung zum normalen IP eingesetzt, um Multicast-Applikationen zu entwickeln und zu testen. Dabei spielt das Multicast-Routing eine entscheidenede Rolle. Erklären Sie kurz die wichtigsten Eigenschaften und Unterschiede der Multicast Routing Algorithmen:

  1. Reverse Path Broadcasting (RPB)
  2. Truncated Reverse Path Broadcasting (TRPB) und
  3. Reverse Path Multicasting (RPM)

(c) Welchen Nachteil haben alle in Aufgabenteil (b) genannten Verfahren? Nennen Sie einen Multicast-Routing-Algorithmus, der diesen Nachteil vermeidet, und erklären Sie diesen in Stichworten.



Abgabedaten:

Matrikelnummer: Password:

Universität:
Mannheim
Heidelberg
Freiburg
Karlsruhe
andere

{ cjk, kuehne}@pi4.informatik.uni-mannheim.de
Last modified: Thu Dec 7 10:29:02 CET 2000