#
Optimal Smoothing Schedules for Real-Time Streams

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
some bytes may be dropped due to limited bandwidth or space. We
present the following results.
First, we determine the optimal tradeoff between buffer space,
queuing 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, that 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 4-competitive. We also prove a lower bound of 1.25
on the competitive ratio of *any* deterministic 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.

Click here for paper (pdf).