Multimedia-Systeme: Übungsblatt 7

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

(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 2: Empirical Envelope

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

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

(a)

(b)

(c)

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:

• zeitliche Hierarchisierung 1 2 3
• räumliche Hierarchisierung 1 2 3
• Hierarchisierung der Frequenzen 1 2 3

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

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

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: