Оптимальні графіки згладжування потоків у реальному часі

Анотація.

Ми розглядаємо проблему згладжування потоків у реальному часі (таких як відеопотоки), де метою є віддалене відтворення потоку змінної пропускної здатності, мінімізуючи при цьому витрати на пропускну здатність, вимоги до місця та затримку відтворення. Ми орієнтуємось на з втратами графіки, де дані можуть бути скинуті через обмежену пропускну здатність або простір. Ми представляємо такі результати. Спочатку ми визначаємо оптимальний компроміс між буферним простором, затримкою згладжування та пропускною здатністю каналу для графіків згладжування з втратами. Зокрема, це означає, що якщо вказано два з цих параметрів, ми можемо точно розрахувати значення для третього, яке мінімізує втрату даних, уникаючи марнотратства. Компроміс здійснюється за допомогою простого загального алгоритму, який дає певну свободу у виборі даних, які потрібно відкинути. Цей алгоритм дуже легко реалізувати як на сервері, так і на клієнті, і він має приємну властивість, що лише сервер вирішує, які дані відкидати, а клієнту потрібно лише реконструювати потік.

У другому наборі результатів ми вивчаємо випадок, коли різні частини даних мають різне значення, змодельовані шляхом присвоєння реальної “ваги” кожному пакету в потоці. Для цього налаштування ми використовуємо конкурентний аналіз, тобто ми порівнюємо вагу, надану он-лайн алгоритмами, з вагою оптимального графіку роботи поза мережею, використовуючи ті самі ресурси. Ми доводимо, що природний жадібний алгоритм є 4-конкурентним. Ми також доводимо нижню межу 1,23 на конкурентний коефіцієнт будь-який детермінований он-лайн алгоритм. Нарешті, ми даємо кілька експериментальних результатів, які, здається, вказують на те, що згладжування дуже ефективно на практиці, і що жадібний алгоритм працює дуже добре у зваженому випадку.

Завантажте, щоб прочитати повний текст статті

Список літератури

Стандарт MPEG-1 (ISO/IEC 11172), 1992 р

Стандарт MPEG-2 (ISO/IEC DIS 13818), 1994 рік

Бородін А, Ель-Янів Р: Інтернет-обчислення та конкурентний аналіз. Кембриджська університетська преса, 1998

Chang R-I, Chen M-C, Ho J-M, Ko M-T: Ефективна та ефективна схема згладжування трафіку для доставки онлайн-медіапотоків VBR. В: Праці IEEE INFOCOM, 1999

Civanlar M, Cash G, Haskell B: Формат корисного навантаження RTP для пакетного MPEG, травень 1998 р. Інтернет RFC 2343.

Даффілд Н.Г., Рамакрішнан К.К., Рейбман АР: ЗБЕРЕЖИТИ: Алгоритм згладжування адаптивного відео за мережами з явною швидкістю. Транзакції IEEE/ACM у мережі 6 (6): 717-728 (1998)

Feng W, Rexford J: Оцінка продуктивності алгоритмів згладжування для передачі попередньо записаного відео із змінною швидкістю передачі. IEEE Trans. про мультимедіа 1 (3): 302-313 (1999)

Grosslauser M, Keshav S, Tse DNC: RCBR: Простий та ефективний сервіс для багаторазового трафіку. Транзакції IEEE/ACM у мережі 5 (6): 741-755 (1997)

Ni TYJ, Tsang D: Техніка CBR-транспорту для з’єднань відео на замовлення MPEG-2 через мережі ATM. У: Зб. IEEE ICC 96, с. 1391-1395. Червень 1996 р

Jiang Z, Kleinrock L: Загальний оптимальний алгоритм згладжування відео. У: Зб. IEEE INFOCOM. Березень 1999

Кешав С: Інженерний підхід до комп’ютерних мереж. Addison-Wesley Publishing Co., 1997

Lam SS, Chow S, Yau DKY: Алгоритм згладжування MPEG-відео без втрат. Транзакції IEEE/ACM у мережі 4 (5): 697-708 (1996)

Рексфорд Дж., Сен С, Дей Дж, Фен З, Куросе Дж, Станковіч Дж, Тоуслі Д: Інтернет-згладжування відео в реальному часі зі змінною швидкістю передачі. У: Зб. Міжнародний семінар з питань підтримки мережі та операційних систем для цифрового аудіо та відео, с. 249-257. Травень 1997 р

Рексфорд Дж., Тоуслі Д: Згладжування відео зі змінною швидкістю передачі даних у мережі. Транзакції IEEE/ACM у мережі, с. 202-215. Квітень 1999 р

Salehi J, Zhang Z, Kurose J, Towsley D: Підтримка збереженого відео: Зменшення змінності швидкості та наскрізних потреб у ресурсах за рахунок оптимального згладжування. Транзакції IEEE/ACM у мережі 6 (4): 397-410 (1998)

Sen S, Dey J, Kurose J, Stankovic J, Towsley D: CBR передача VBR-збереженого відео. В: Симпозіум SPIE з голосового відео та передачі даних, листопад 1997 р

Sen S, Rexford J, Towsley D: кешування префіксів проксі для мультимедійних потоків. У: Зб. IEEE INFOCOM, березень 1999

Технічний комітет Форуму банкоматів. Специфікація управління дорожнім рухом версія 4.0, квітень 1996 р. Доступно з www.atmforum.com

Wrege DE, Knightly EW, Zhang H, Liebeherr J: Детерміновані межі затримки для VBR-відео в мережах комутації пакетів: основні межі та практичні компроміси. Транзакції IEEE/ACM у мережі 4 (3): 352-362 (1996)

Чжан Х: Службові дисципліни для гарантованого обслуговування в мережах з комутацією пакетів. Праці IEEE 83 (10) (1995)

Zhang Z-L, Nelakuditi S, Aggarwal R, Tsang RP: Ефективні селективні алгоритми відкидання кадру для доставки збереженого відео через мережі, обмежені ресурсами. У: Зб. IEEE INFOCOM, березень 1999

Zhao W, Seth T, Kim M, Willebeek-LeMair M: Оптимальний компроміс смуги пропускання/затримки для масштабованого мультимедійного планування на основі можливої області. У: Зб. IEEE INFOCOM 98, 1998