Fast techniques for the optimal smoothing of stored video

Work-ahead smoothing is a technique whereby a server, transmitting stored c ompressed video to a client, utilizes client buffer space to reduce the rat e variability of the transmitted stream. The technique requires the server to compute a schedule of transfer under the constraints that the client buf fer neither overflows nor underflows. Recent work established an optimal of f-line algorithm (which minimizes peak, variance and rate variability of th e transmitted stream) under the assumptions of fixed client buffer size, kn own worst case network jitter, and strict playback of the client video. In this paper, we examine the practical considerations of heterogeneous and dy namically variable client buffer sizes, variable worst case network jitter estimates, and client interactivity. These conditions require on-line compu tation of the optimal transfer schedule. We focus on techniques for reducin g on-line computation time. Specifically, (i) we present an algorithm for p recomputing and storing the optimal schedules for all possible client buffe r sizes in a compact manner; (ii) we show that it is theoretically possible to precompute and store compactly the optimal schedules for all possible e stimates of worst case network jitter; (iii) in the context of playback res umption after client interactivity, we show convergence of the recomputed s chedule with the original schedule, implying greatly reduced on-line comput ation time; and (iv) we propose and empirically evaluate an "approximation scheme" that produces a schedule close to optimal but takes much less compu tation time.