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

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.