Click on the following for the postscript version of:

Wu-chi Feng,"Video-On-Demand Services: Efficient Transportation and Decompression of Variable Bit Rate Video", Ph.D. Thesis, University of Michigan, April 1996.

Title Pages
Table of Contents
Chapter 1 - Introduction
Chapter 2 - Background
Chapter 3 (part 1) - Bandwidth Smoothing Techniques
Chapter 3 (part 2)
Chapter 4 - VCR Functionality in Bandwidth Smoothing Environments
Chapter 5 - Video Decompression Techniques
Chapter 6 - Conclusion and Future Work
Appendix
Bibliography


Abstract

In this dissertation, we take an in-depth look at how burstiness introduced by compression standards such as MPEG and Motion-JPEG affect the handling of video data. We concentrate on the handling of bursty prerecorded video data that may be found in an interactive educational system or an interactive video-on-demand video delivery system. Our three-fold approach looks at smoothing the requirements for network data, delivering the video data across networks, and finally how end processors can deal with the burstiness.

For the delivery of compressed prerecorded video data, we introduce the notion of critical bandwidth allocation. This bandwidth smoothing technique creates a bandwidth allocation plan for the delivery of the video data given a priori knowledge of the video data. The critical bandwidth allocation technique allows for the retrieval of stored video that does not require prefetching (and hence, delay) and results in a monotonically decreasing sequence of bandwidth allocations. Given some fixed buffer size constraint, the critical bandwidth allocation algorithm creates plans for the continuous playback of stored video that have

(1) the minimal number of bandwidth increases,
(2) the smallest peak bandwidth requirement, and
(3) the largest minimum bandwidth requirement.

We extend this idea into an optimal bandwidth allocation policy that, in addition to the critical bandwidth algorithm properties, also minimizes the total number of bandwidth changes for the continuous playback of stored video.

While the use of bandwidth smoothing techniques is effective at removing the peak bandwidth requirements of networks for a single video stream, smoothing of bandwidth through the prefetching of data makes the bandwidth plans somewhat rigid. This, in turn, makes it difficult to support VCR capabilities such as stop, pause, rewind, and fast-forward. To support these interactive functions, we introduce the notion of the VCR-window, which allows users to have full-function VCR capabilities within a limited segment of video around the playback point without having to change the level of the bandwidth reservations. For accesses outside the VCR-window re-negotiation of network resource may be necessary. To allow for these accesses, we show how the use of a "contingency channel" for stored video can be used to resynchronize the delivery of video back with the original bandwidth allocation plan. To show the applicability of the VCR-window, we introduce a resource reservation scheme that can be used in conjunction with the VCR-window. Finally, we introduce a network cost model that can be used in conjunction with the VCR-window and the resource reservation scheme for the charging of network resources.

Once the video has been delivered to the end user's machine, the video must be decompressed and played back for the user. We examine the effects that software decompression of MPEG video has on processor performance. The software decompression of MPEG video typically makes poor utilization of processor caching, because the information used across frames in MPEG reconstruction does not typically stay in the cache long enough for the processor to benefit from its reuse. To examine the issues involved with the software decompression of video data, we examine two techniques for improving processor caching: 1) reducing the effective working set size of the decompression algorithm and 2) providing a prefetch instruction and the associated circuitry to "warm" the cache for data that is anticipated to be accessed.

To reduce the working-set, we introduce the notions of vertical and horizontal striping for the decompression of MPEG video. These traversal algorithms visit (and decompress) the macroblocks of the compressed video stream using a different order than implied by the MPEG standard. As a result, the macroblocks that may be needed by other frames have a higher probability of remaining in the cache and being re-accessed. To keep caches "warm" with macroblock data for video decompression, we examine the feasibility of prefetching data that is expected to be accessed in the near future and to prefetch the data before it is needed. Software controlled prefetching is supported on some current processors.