Optimal buffering algorithms for client-server VBR video retrievals

Variable bit rate (VBR) videos refer to videos with varying frame sizes. When transmitted through networks in a client-server environment, their corresponding traffic is inherently bursty because of the embedded timing constraints in digital videos. In reservation based networks like ATM network, such traffic may result in considerable network under-utilization if the network has to accommodate the peak bit rate. Traffic smoothing is thus necessary to reduce the burstiness in the VBR video traffic and it can be very effective in the case of stored video. By introducing a playback delay and buffering video data on the client side, a smoother traffic can be transmitted by the server. In order for the client to restore the original timing information in the video, it is important to avoid buffer overflow or underflow during the video retrieval. This buffer constraint determines the "smoothest" traffic that can be sent out by the server and thus defines a set of optimization problems based on different traffic types.;In this thesis, several buffering and traffic smoothing methods for VBR videos are thoroughly studied and their relationships established. Among them, minimum polyline smoothing and minimum on-off smoothing are two fundamental methods and serve as the basis for other methods. For a given video service with buffer and delay constraint, minimum polyline smoothing produces smoothed traffic with multiple rate changes while minimum on-off smoothing generates a single rate traffic with transmitting (on) and idle (off) periods. We carefully choose smoothness criterion for each method and identify optimization problems based on these criteria. Novel algorithms are then presented for these problems and their correctness and effectiveness are theoretically proved and experimentally verified. These methods not only can be applied very effectively on stored VBR videos, but can serve as benchmark algorithms for real-time video smoothing.;Simulation programs based on the algorithms designed in the thesis are applied to VBR video traces to show the effectiveness of these smoothing methods.