Paper by Erik D. Demaine

Reference:

Therese Biedl, Erik D. Demaine, Alexander Golynski, Joseph D. Horton, Alejandro López-Ortiz, Guillaume Poirier, and Claude-Guy Quimper, “Optimal Dynamic Video-On-Demand using Adaptive Broadcasting”, in Proceedings of the 11th Annual European Symposium on Algorithms (ESA 2003), Lecture Notes in Computer Science, volume 2832, Budapest, Hungary, September 15–20, 2003, pages 90–101.

Abstract:

We consider the transmission of a movie over a broadcast network to support several viewers who start watching at arbitrary times, after a wait of at most t_wait minutes. A recent approach called harmonic broadcasting optimally solves the case of many viewers watching a movie using a constant amount of bandwidth. We consider the more general setting in which a movie is watched by an arbitrary number v of viewers, and v changes dynamically. A natural objective is to minimize the amount of resources required to achieve this task. We introduce two natural measures of resource consumption and performance—total bandwidth usage and maximum momentary bandwidth usage—and propose strategies which are optimal for each of them. In particular, we show that an adaptive form of pyramid broadcasting is optimal for both measures simultaneously, up to constant factors. We also show that the maximum throughput for a fixed network bandwidth cannot be obtained by any online strategy.

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PostScript (363k), gzipped PostScript (157k), and PDF (160k).

See information on file formats.

[Google Scholar search]