|
Abstract : |
We address the problem of designing optimal o-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 buer 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. For fully loaded arrivals, where streams must be initiated at unit intervals, we present an O(n) algorithm that is based on an elegant formula using Fibonacci numbers. We then show how to adopt our algorithms to be optimal even if clients have a limited size buer. The complexity remain the same for both arrivals cases. We also prove that using stream merging may reduce the required bandwidth by a factor of order L = log(L) compared to the simple batching solution where L is the length of a stream and 1 is the density in time of all the n arrivals. On the other hand, we show that the bandwidth required when the client 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., |
