Efficient algorithms for optimal stream merging for media-on-demand

被引:9
作者
Bar-Noy, A
Ladner, RE
机构
[1] CUNY Brooklyn Coll, Dept Comp & Informat Sci, Brooklyn, NY 11210 USA
[2] AT&T Labs Res, Shannon Lab, Florham Pk, NJ USA
[3] Univ Washington, Dept Comp Sci & Engn, Seattle, WA 98195 USA
关键词
media-on-demand; stream merging; dynamic programming; monotonicity property;
D O I
10.1137/S0097539701389245
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We address the problem of designing optimal off-line algorithms that minimize the required bandwidth for media-on-demand systems that use stream merging. We concentrate on the case where clients can receive two media streams simultaneously and can buffer up to half of a full stream. We construct an O(nm) optimal algorithm for n arbitrary time arrivals of clients, where m is the average number of arrivals in an interval of a stream length. We then show how to adopt our algorithm to be optimal even if clients have a limited size buffer. The complexity remains the same. We also prove that using stream merging may reduce the required bandwidth by a factor of order rhoL/log(rhoL) compared to the simple batching solution where L is the length of a stream and rholess than or equal to1 is the density in time of all the n arrivals. On the other hand, we show that the bandwidth required when clients can receive an unbounded number of streams simultaneously is always at least 1/2 the bandwidth required when clients are limited to receiving at most two streams.
引用
收藏
页码:1011 / 1034
页数:24
相关论文
共 44 条
[11]   The dyadic stream merging algorithm [J].
Coffman, EG ;
Jelenkovic, P ;
Momcilovic, P .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2002, 43 (01) :120-137
[12]   Dynamic batching policies for an on-demand video server [J].
Dan, A ;
Sitaram, D ;
Shahabuddin, P .
MULTIMEDIA SYSTEMS, 1996, 4 (03) :112-121
[13]   Minimizing bandwidth requirements for on-demand data delivery [J].
Eager, D ;
Vernon, M ;
Zahorjan, J .
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2001, 13 (05) :742-757
[14]   Optimal and efficient merging schedules for video-on-demand servers [J].
Eager, D ;
Vernon, M ;
Zahorjan, J .
ACM MULTIMEDIA 99, PROCEEDINGS, 1999, :199-202
[15]  
EAGER DL, 1999, P IS T SPIE C MULT C, P301
[16]  
EAGER DL, 1998, P 4 INT WORKSH MULT, P18
[17]   Efficient schemes for broadcasting popular videos [J].
Gao, LX ;
Kurose, J ;
Towsley, D .
MULTIMEDIA SYSTEMS, 2002, 8 (04) :284-294
[18]   Adaptive piggybacking: A novel technique for data sharing in video-on-demand storage servers [J].
Golubchik, L ;
Lui, JCS ;
Muntz, RR .
MULTIMEDIA SYSTEMS, 1996, 4 (03) :140-155
[19]  
Golubchik L., 1995, P ACM SIGMETRICS JOI, P25
[20]  
Hua K. A., 1998, Proceedings ACM Multimedia 98, P191, DOI 10.1145/290747.290771