Collaborative prefetching frameworks of continuous media

Bursty continuous media streams with periodic playout deadlines (e.g., variable-bit-rate encoded video) are expected to account for a large portion of the traffic in the future Internet. Many emerging continuous media applications, such as digital libraries video-on-demand services, rely on an efficient transmission scheduling algorithm. By prefetching parts of ongoing streams into client buffers these bursty streams can be more efficiently accommodated in packet-switched networks. The problem considered in this research is to design fair and efficient transmission scheduling algorithms for prerecorded continuous media applications on two time models: one that divides time into equal discrete communication time slots, and one where no notion of allocated communication time slots exists. The former is called the discrete time model and the latter the continuous time model.; A modular algorithm-theoretic framework for the fair and efficient transmission of continuous media over a bottleneck link for the discrete time model is presented. The problem is divided into the two subproblems of (i) assuring fairness, and (ii) efficiently utilizing the available link capacity. The algorithm modules for these two subproblems are developed and analyzed. Specifically, a bin packing algorithm is devised for subproblem (i), and a "layered prefetching" algorithm is devised for subproblem (ii). The simulation results indicate that the combination of these two algorithm modules compares favorably with existing monolithic solutions. This demonstrates the competitiveness of the decoupled modular algorithm framework, which provides a foundation for the development of refined algorithms for fair and efficient prefetching.; The benefits of the decoupled approach do not carry over to the continuous time model. For the continuous time model, different priority functions are presented. These priority functions give relative priorities among the ongoing streams at the time the server selects a stream for transmission. Various algorithms based on these priority functions are proposed and analyzed. The simulation results show that a priority function plays a key role in the fairness aspect of an algorithm. The main advantage of treating time in a continuous fashion is that it eliminates the waste of bandwidth due to frames not filling into the residual bandwidth of a time slot. Hence 100% of link utilization is obtained by nature in the continuous time model. The computational complexity of the algorithms for the continuous time model is equal to O( J), where J is the number of clients in the system.