##
Optimal Smoothing Schedules for Real-Time Streams

###
Mansour, Patt-Shamir and Lapid

**To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000**

##
Abstract

We consider the problem of *smoothing* real-time streams (such as
video streams), where the goal is to reproduce a variable-bandwidth stream
remotely, while minimizing bandwidth cost, space overhead, and playback
delay. We focus on *lossy* schedules, where we are allowed to drop
some bits due to limited bandwidth or space. In this paper we present the
following results. First, we determine the optimal tradeoff between buffer
space, delay, and link bandwidth for lossy smoothing schedules . Specifically,
this means that if one of these parameters is under our control, we can
precisely calculate the optimal value which minimizes data loss while avoiding
resource wastage. The tradeoff is accomplished by a simple generic algorithm,
which allows one some freedom in choosing which data to discard. This algorithm
is very easy to implement both at the server and at the client, and it
enjoys the nice property that only the server decides which data to discard,
and the client needs only to reconstruct the stream. In a second set of
results we study the case where different parts of the data have different
importance, modeled by assigning a real ``weight'' to each byte in the
stream. For this setting we use competitive analysis, i.e., we compare
the weight delivered by on-line algorithms to the weight of an optimal
off-line schedule using the same resources. We prove that a natural greedy
algorithm is 2-competitive. We also prove a lower bound of 1.25 on the
competitive ratio of *any* on-line algorithm. Finally, we give a few
experimental results which show that smoothing is extremely effective in
practice, and that the greedy algorithm performs very well in the weighted
case.