Programări optime de netezire pentru fluxurile SpringerLink în timp real

Abstract.

Considerăm problema netezirii fluxurilor în timp real (cum ar fi fluxurile video), în care scopul este de a reproduce de la distanță un flux cu lățime de bandă variabilă, minimizând în același timp costul lățimii de bandă, necesarul de spațiu și întârzierea redării. Ne concentrăm asupra pierdut programări, unde datele pot fi abandonate din cauza lățimii de bandă sau a spațiului limitat. Vă prezentăm următoarele rezultate. În primul rând, determinăm compromisul optim între spațiul tampon, întârzierea netezirii și lățimea de bandă a legăturii pentru programele de netezire cu pierderi. În mod specific, acest lucru înseamnă că, dacă sunt dați doi dintre acești parametri, putem calcula cu precizie valoarea pentru al treilea, care minimizează pierderea de date, evitând în același timp risipa de resurse. Compensarea se realizează printr-un algoritm generic simplu, care permite o anumită libertate în alegerea datelor care trebuie aruncate. Acest algoritm este foarte ușor de implementat atât la server, cât și la client și se bucură de proprietatea drăguță că numai serverul decide ce date să renunțe, iar clientul are nevoie doar pentru a reconstrui fluxul.

netezire

Într-un al doilea set de rezultate, studiem cazul în care diferite părți ale datelor au o importanță diferită, modelate prin atribuirea unei „greutăți” reale fiecărui pachet din flux. Pentru această setare folosim analiza competitivă, adică comparăm greutatea livrată de algoritmi on-line cu greutatea unui program optim off-line folosind aceleași resurse. Dovedim că un algoritm lacom natural este 4-competitiv. De asemenea, dovedim o limită inferioară de 1,23 la raportul competitiv de orice algoritm determinist on-line. În cele din urmă, oferim câteva rezultate experimentale care par să indice că netezirea este foarte eficientă în practică și că algoritmul lacom funcționează foarte bine în cazul ponderat.

Descărcați pentru a citi textul complet al articolului

Referințe

Standardul MPEG-1 (ISO/IEC 11172), 1992

Standardul MPEG-2 (ISO/IEC DIS 13818), 1994

Borodin A, El-Yaniv R: Calcul online și analiză competitivă. Cambridge University Press, 1998

Chang R-I, Chen M-C, Ho J-M, Ko M-T: Un sistem eficient și eficient de netezire a traficului pentru livrarea fluxurilor media VBR online. În: Proceedings of IEEE INFOCOM, 1999