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.