| Title: | Memory Cache: SAM und L/MRP | ||
|---|---|---|---|
| Abstract: | SAM und L/MRP sind zwei Caching Strategien, die speziell zur ressourcenschonenden Übertragung von Datenströmen in einer Multimedia Umgebung entwickelt worden sind. Sie haben beide zum Ziel, den Clients ein hohes Maß an Interaktivität zu bieten. Um Bandbreite zu schonen, versucht SAM, individuelle Datenströme durch unterschiedliche Wiedergabegeschwindigkeiten in einen einzigen Multicast-Datenstrom zu verschmelzen. L/MRP managt die Zustellungsreihenfolge von Datenstromsegmenten, sodass zu jedem Zeitpunkt der Präsentation interaktive Befehle prompt ausgeführt werden können. | ||
| Status: | content final - to do: siehe zipf | Version: | 2005-10-10 |
| History: |
2005-10-10 (Thomas Migl): Abstract hinzugefügt 2005-09-12 (Thomas Migl): Content importiert, LOD1+ 2, Quellen eingegeben 2005-07-18 (Thomas Migl): LU angelegt |
||
| Author 1: | Thomas Migl | E-Mail: | migl@ims.tuwien.ac.at |
|---|---|---|---|
| Author 2: | (empty) | E-Mail: | (empty) |
| Author 3: | (empty) | E-Mail: | (empty) |
| Author 4: | (empty) | E-Mail: | (empty) |
| Author 5: | (empty) | E-Mail: | (empty) |
| Organization: | Technische Universität Wien; Institut für Softwaretechnik und Interaktive Systeme; Arbeitsgruppe für Interaktive Multimediale Systeme; http://www.ims.tuwien.ac.at/ | ||
Einleitung1auto
2autoIn dieser Lerneinheit werden zwei Stream-Dependent Caching Strategien vorgestellt: Die SAM und die L/MRP Caching Strategie. Beiden ist das Ziel gemeinsam, dem Benutzer während der Präsentation eines Videos einen hohen Grad an Interaktivität zu bieten, ohne dass dadurch ein exorbitanter Bedarf an zusätzlicher Bandbreite und Speicherplatz entsteht. Dazu cacht sowohl SAM als auch L/MRP fortwährend relevante Videofragmente meist nur für kurze Dauer in einen Pufferspeicher. Die Daten im Puffer können dann im Falle eines interaktiven Steuerungsbefehls zu dessen Ausführung herangezogen werden. SAM Strategie sita2000, 2321auto
2Motivation von SAMUm ein Netzwerk und die damit verbundenen Server und Speichergeräte in Bezug auf Bandbreite und Datendurchsatz nicht unnötig über zu strapazieren, ist es grundsätzlich ratsam, eine Strategie zu verfolgen, die es ermöglicht, dass trotz unterschiedlicher Wünsche möglichst viele Clients mit ein und dem selben Datenstrom (Mulitcast) bedient werden (siehe Lerneinheit Einführung und Grundlagen). Ein entscheidender Nachteil der Multicasting Technik ist allerdings, dass der einzelne Client kaum Möglichkeit auf Interaktion (z.B.die VCR Steuerungsbefehle schneller Vor- und Rücklauf, Pause, etc) hat. Die Split and Merge Strategie (SAM) arbeitet mit Multicasting, eliminiert aber mittels zusätzlichem Puffer die Beschränkungen der Interaktivität. Arbeitsweise von SAMEin Client sendet einen Request an den Multimedia-on-Demand Server. Wie in der Lerneinheit Einführung und Grundlagen für Near Video-on-Demand ausführlich beschrieben, wird der Client einer entsprechenden Multicastgruppe zugewiesen. Erteilt der Client nun während der Wiedergabe einen VCR Steuerungsbefehl, wird für ihn eigens ein vom ursprünglichen gesplitterter Datenstrom erzeugt (Split). Nach Beendigung der VCR Steuerungseingabe wird der Client mit dem gesplitterten Datenstrom aus einem Puffer versorgt. Dieser individuelle Datenstrom bedeutet natürlich für das Netzwerk eine Zusatzbelastung. Ziel muss es jetzt sein, den Client möglichst schnell in eine passende Mulitcastgruppe wieder einzuordnen, ohne dass dabei die Wiedergabekontinuität beeinträchtigt wird – das heißt, der individuelle Datenstrom soll, vom Client unbemerkt, in einen neuen Multicast Datenstrom übergehen (Merge). Dafür sucht SAM zuerst die zeitlich nächstgelegene Multicastgruppe. Ist diese zeitlich etwas zurück, so wird der Datenstrom aus dem Puffer etwas langsamer wiedergegeben, ist die Multicastgruppe etwas vorne, wird sein Wiedergabetempo erhöht. Ist Puffer- und Multicastdatenstrom synchron, wird der Kunde an die neue Gruppe übergeben, der Puffer entleert und für weitere Requests zur Verfügung gestellt. L/MRP-Strategie mose19951auto
COPU
Objekt Puffer Management
Klassifizierung der COPUs COPUs mit unterschiedlichen Relevanzwerten: / Weiß - Sind bereits bei Client eingelangt / Grau - COPUs werden im Falle eines schnellen Vorlaufs übersprungen / Schwarz - COPUs für schnellen Vorlauf notwendig Puffer Management Relevanzwerte und momentaner Pufferstatus (unterstrichene fette Werte) 2Motivation von L/MRPL/MRP steht für “Least/Most Relevant for Presentation”. Die L/MRP Caching Strategie zielt auf eine Optimierung der Interaktionseigenschaften bei kontinuierlichen Multimedia Inhalten (Video und Audiostreaming). Prinzipiell werden Daten in kleinen Paketen über ein Netzwerk verschickt, so dass eine zeitkontinuierliche Informationsübertragung ohne zusätzliche Techniken nicht möglich ist. Um empfangene Video- und Audiodaten ohne Unterbrechung präsentieren zu können, werden die Datenpakete in einem Pufferspeicher aufgefangen, aus diesem werden sie dann kontinuierlich ausgelesen. Die Art und Weise, wie und welche Daten im Puffer gemanagt werden, hat auch einen großen Einfluss auf die Interaktionseigenschaften des Benutzers/Benutzerin. Die L/MRP Caching Strategie verfolgt nun das Ziel, dass ein Benutzer, der oft mittels schnellem Vor- oder Rücklauf, variabler Wiedergabegeschwindigkeit, Wahl beliebiger Einstiegspunkte etc. im Video navigiert, unmittelbar nach Beendigung des jeweiligen Steuerbefehls ohne Zeitverzögerung die Wiedergabe fortsetzen kann. Zu diesem Zwecke berücksichtigt L/MRP präsentationsspezifische Informationen. Arbeitsweise von L/MRPCOPUIn der Absicht, den schnellen direkten Zugriff auf die unterschiedlichen Passagen eines multimedialen Dokuments zu ermöglichen, wird dieses für L/MRP in Continous Object Presentation Units (COPU) unterteilt. COPUs sind die für das Puffer Management kleinsten greifbaren Multimedialen Einheiten. Beispiele für COPUs
Objekt Puffer ManagementAbhängig vom gewählten Startpunkt (WP: Working Point) und der Stelle im Multimedia Dokument, an der sich der Benutzer gerade befindet, wird für alle COPUs des Multimedia Dokuments ein Relevanzwert angegeben: Ein sehr hoher Relevanzwert bedeutet, dass die Wahrscheinlichkeit, dass der Benutzer diese COPU in nächster Zukunft für eine kontinuierliche Präsentation benötigt, sehr hoch ist. Umgekehrt steht ein geringer Relevanzwert für eine geringe Aufrufwahrscheinlichkeit. Die Relevanzwerte hängen dabei stark von den dem Benutzer gebotenen Interaktionsmöglichkeiten ab. Basierend auf diesen Werten kann nun der Continous Object Manager (COM) den Datenbestand des Puffers fortwährend aktualisieren. Ihm stehen dazu zwei Techniken zur Verfügung:
Aus der Bewertung der COPUs in Hinsicht auf deren Relevanz für eine möglichst unterbrechungsfreie Präsentation leitet sich auch der Name L/MRP ab: COPUs mit geringster Präsentationsrelevanz (Least Relevant for Presentation) werden aus dem Puffer entfernt, COPUs mit höchster Präsentationsrelevanz (Most Relevant for Presentation) im Vorhinein geladen. Beispiel: Arbeitsweise L/MRPAls praktisches Beispiel sei hier der Zugriff auf eine Multimedia Datenbank angegeben, die Videos von Sightseeing Touren von Städten enthält. Die verschiedenen Videos sind dabei auch untereinander verlinkt (Hypermedia). Mittels applikationsspezifischen Programms kann der Kunde ein Video auswählen und starten und beliebig navigieren. Zur interaktiven Präsentation stehen ihn nun die Funktionen schneller Vor- und Rücklauf (jeweils mit doppelter Wiedergabegeschwindigkeit), Set WP, Entferne WP und Springe zu WP. Jeder interaktive Steuerungsbefehl wird an den Continous Object Manager geleitet, dieser startet dann entsprechenden Datenfluss. Klassifizierung der COPUsDas Video wird in n COPUs aufgeteilt Jede COPU wird mit einem Index von 0 bis n-1 versehen. Der Benutzer wählt einen Working Point: In unserem Beispiel wurde der Working Point auf die COPU 501 gesetzt. Die Abbildung ist ein Schnappschuss der Präsentation des Videos, die sich gerade auf der COPU 508 befindet. Die weiß eingezeichneten COPUs sind daher die bereits abgespielten. Die schwarz markierten sind jene, die im Falle eines schnellen Vorlaufs (jede zweite COPU wird ausgelassen) von hoher Relevanz sind. Die grauen sind die für eine normale Wiedergabe benötigten, für schnellen Vorlauf allerdings zu überspringenden COPUs. COPUs mit unterschiedlichen Relevanzwerten: / Weiß - Sind bereits bei Client eingelangt / Grau - COPUs werden im Falle eines schnellen Vorlaufs übersprungen / Schwarz - COPUs für schnellen Vorlauf notwendig Puffer ManagementDie Abbildung zeigt die Relevanzwerte der COPUs zum Zeitpunkt der Präsentation von COPU 508. Wir setzen nun voraus, dass zu diesem Zeitpunkt jene COPUs im Puffer gespeichert sind, deren Indizes in der Abbildung fett und unterstrichen formatiert sind. Die momentan am wenigsten relevanten COPUs sind 527, 525, 523, 528, 521, 500, 526 etc. Diese werden für das Puffer Management genau in dieser Reihenfolge als Austauschkandidaten vorgemerkt. COPUs von höchster Relevanz sind hingegen 508, 510, 512 514 etc. Diese werden daher im Vorhinein in den Puffer geladen. Relevanzwerte und momentaner Pufferstatus (unterstrichene fette Werte) |
|
Akronyme COM – Continuous Object Manager COPU – Continuous Object Presentation Unit GOP – Group of Pictures IC – Interval Caching L/MRP - Least/Most Relevant for Presentation [mose1995] MOD – Multimedia on Demand NVD – Near Video on Demand PCM - Pulse-Code Modulation SAM – Split and Merge VCR – Video Cassette Recorder WP – Working Point Glossar Datendurchsatz - Die Datenmenge, die pro Zeiteinheit verarbeitet wird Hypermedia – meist als Synonym für Hypertext verwendet, wobei die Betonung auf multimedialen Objekten liegt Hypertext - Hypertext ist eine nicht-lineare Organisation von heterogenen Objekten, deren netzartige Struktur durch logische Verbindungen (Verweise, Links) zwischen atomisierten Wissenseinheiten (Knoten, z. B. Texten oder Textteilen) hergestellt wird (Verweis-Knoten-Konzept) [wikibedia.de] Motion-JPEG – Alle Frames einer Bildfolge in einem Video werden unabhängig voneinander JPEG kodiert Multicast – Sammelsendung Puffer – Der Begriff Puffer ist hier als Synonym von Caching zu verstehen. |