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

Civanlar M, Cash G, Haskell B: format de încărcare utilă RTP pentru MPEG la pachet, mai 1998. Internet RFC 2343.

Duffield NG, Ramakrishnan KK, Reibman AR: SAVE: Un algoritm pentru video adaptiv netezit pe rețele cu rată explicită. Tranzacții IEEE/ACM în rețea 6 (6): 717-728 (1998)

Feng W, Rexford J: Evaluarea performanței algoritmilor de netezire pentru transmiterea videoclipului cu viteză de biți variabilă preînregistrată. IEEE Trans. pe Multimedia 1 (3): 302-313 (1999)

Grosslauser M, Keshav S, Tse DNC: RCBR: Un serviciu simplu și eficient pentru trafic multiplu pe scară temporală. Tranzacții IEEE/ACM în rețea 5 (6): 741-755 (1997)

Ni TYJ, Tsang D: O tehnică de transport CBR pentru conexiuni video-la-cerere MPEG-2 prin rețele ATM. În: Proc. IEEE ICC 96, pp. 1391-1395. Iunie 1996

Jiang Z, Kleinrock L: Un algoritm video general de netezire optimă. În: Proc. IEEE INFOCOM. Mar. 1999

Keshav S: O abordare inginerească a rețelelor de calculatoare. Editura Addison-Wesley Co., 1997

Lam SS, Chow S, Yau DKY: Un algoritm pentru netezirea fără pierderi a videoclipurilor MPEG. Tranzacții IEEE/ACM în rețea 4 (5): 697-708 (1996)

Rexford J, Sen S, Dey J, Feng W, Kurose J, Stankovic J, Towsley D: Netezire online a videoclipurilor live, cu rată de biți variabilă. În: Proc. Atelier internațional de suport pentru rețea și sisteme de operare pentru audio și video digitale, pp. 249-257. Mai 1997

Rexford J, Towsley D: Netezirea videoclipului cu rată de biți variabilă într-o rețea de internet. Tranzacții IEEE/ACM în rețea, pp 202-215. aprilie 1999

Salehi J, Zhang Z, Kurose J, Towsley D: Suport video stocat: Reducerea variabilității ratei și a cerințelor de resurse end-to-end printr-o netezire optimă. Tranzacții IEEE/ACM în rețea 6 (4): 397-410 (1998)

Sen S, Dey J, Kurose J, Stankovic J, Towsley D: Transmisie CBR a videoclipului stocat VBR. În: Simpozionul SPIE privind comunicațiile video și de date vocale, nov. 1997

Sen S, Rexford J, Towsley D: Prefixarea în cache a fluxului multimedia pentru fluxuri multimedia. În: Proc. IEEE INFOCOM, mar. 1999

Comitetul tehnic al forumului ATM. Specificații de gestionare a traficului versiunea 4.0, apr. 1996. Disponibil de pe www.atmforum.com

Wrege DE, Knightly EW, Zhang H, Liebeherr J: Limite de întârziere deterministe pentru video VBR în rețelele de comutare de pachete: limite fundamentale și compromisuri practice. Tranzacții IEEE/ACM în rețea 4 (3): 352-362 (1996)

Zhang H: discipline de service pentru servicii de performanță garantate în rețele cu comutare de pachete. Lucrările IEEE 83 (10) (1995)

Zhang Z-L, Nelakuditi S, Aggarwal R, Tsang RP: Algoritmi de descărcare a cadrelor selective eficiente pentru livrarea video stocată în rețelele constrânse de resurse. În: Proc. IEEE INFOCOM, mar. 1999

Zhao W, Seth T, Kim M, Willebeek-LeMair M: Lățime de bandă optimă/compromis întârziere pentru programare multimedia scalabilă bazată pe regiuni fezabile. În: Proc. IEEE INFOCOM 98, 1998