Abstract:

The real-time streaming of bursty continuous media, such as variable-bit rate encoded video, to buffered clients over networks can be made more efficient by collaboratively prefetching parts of the ongoing streams into the client buffers. This thesis is divided in two main sections. First a modular algorithmic framework for discrete-time collaborative prefetching was developed and analyzed. In contrast to the DC scheme, where both fairness and efficiency are addressed by a single scheduling algorithm which considers a single priority index, the problem was broken into the two subproblems of ensuring fairness by avoiding continuous starvation of a client, and maximizing the bandwidth utilization. A BIN-PACKING-ROUND algorithm was developed and analyzed which computes the minimum number of slots needed to schedule at least one frame for each stream with the minimum number of transmitted frames so far. Next the LAYERED-PREFETCHING-ROUND algorithm was developed and analyzed which maximizes the number of additional frames to be transmitted (prefetched) in the residual bandwidths of the minimum number of time slots.

In the second section of this thesis the focus is on the collaborative prefetching in a continuous-time model. The existing collaborative prefetching schemes have been developed for discrete time models, where scheduling decisions for all ongoing streams are typically made for one frame period at a time. This leads to inefficiencies as the network bandwidth is not utilized for some duration at the end of the frame period when no video frame "fits" into the remaining transmission capacity in the schedule. To overcome this inefficiency, in this thesis an extensive study of collaborative prefetching in a continuous-time model is conducted. In the continuous-time model, video frames are transmitted continuously across frame periods, while making sure that frames are only transmitted if they meet their discrete playout deadlines. This thesis specifies a generic framework for continuous-time collaborative prefetching and a wide array of priority functions to be used for making scheduling decisions within the framework. Through simulations an extensive study was conducted on algorithm-theoretic study of the resulting continuous-time prefetching algorithms and evaluated their fairness and starvation probability performance through simulations. It was proven that the continuous-time prefetching algorithms give favorable fairness and starvation probability performance.