Real-time retrieval of multiple variable bit rate video streams

Design of high-performance video servers is a challenging problem. A video server must retrieve and deliver large number of videos concurrently in real-time. Video data are stored in compressed form to save disk storage space and network bandwidth. Unfortunately, highly compressed videos generate variable bit rate (VBR) and bursty traffics. If system bandwidth of a video server is reserved for each video stream by its peak data rate to guarantee real time delivery, the video server can only support small number of concurrent videos and its resources are mostly under-utilized. Various data retrieval mechanisms, like generalized constant data length (GCDL) or generalized constant time length (GCTL), were proposed to improve resource utilization for VBR videos. However, important problems like optimal resource allocation for multiple VBR video streams and how to retrieve maximum number of VBR video streams concurrently in real-time remain unsolved. This research studied and evaluated novel solutions to these problems. In order to support dynamic resource allocation, a prefetching data retrieval mechanism was proposed and studied. When the available system bandwidth is less than the video peak data rate, video data is prefetched into memory buffer ahead of time to guarantee real-time delivery. An efficient on-demand resource scheduling algorithm was derived. By using pre-computed information obtained from known video traffics, the algorithm determines when to do data prefetching and computes the exact amount of data to be retrieved from disk for each retrieval cycle at run time. The tradeoff between data retrieval bandwidth and prefetching buffer size was studied quantitatively. An efficient, real-time minimum bandwidth allocation algorithm for multiple concurrent video streams was derived. For a given available system buffer size, the O(n log n) algorithm computes optimum bandwidth and buffer allocation for each video stream. An optimal admission control based on dynamic resource allocation was proposed and studied. Whenever the total system bandwidth can support a new video together with all running videos, the new video is admitted instantaneously and resources are reallocated optimally among the videos without affecting real-time delivery of the running videos. The corresponding resource reallocation algorithm were derived and studied. Experiments were conducted to evaluate the proposed real-time data retrieval algorithms. Optimal data prefetching was found superior than other data retrieval methods. It could better use available memory buffer to support more video streams. It supported 150 - 250 % more video streams than conventional data retrieval methods. The optimal admission control algorithm was compared with two other admission control schemes which does not reallocate resources at run-time. Under heavy system load, the optimal admission control algorithm could admit 97% of video requests while the other two schemes could admit no more than 90% of video requests