Minimizing Average Waiting Time in Video-on-Demand Broadcasting

摘要

The waiting time for given bandwidth is considered as one of the most important performance metrics of Video-on-Demand broadcasting schemes. It is known that, if the available bandwidth is c times the display rate of a video, then 1/(e{sup}c-1) is the tight lower bound on the maximum waiting time normalized by the video duration. The best general lower bound on the normalized average waiting time known to date is 1/(4e{sup}c-1). We first derive the tight lower bound on the average waiting time for fixed start-points schemes, which is almost exactly 1/(1.123e{sup}c-1). We then introduce the Harmonic Block Windows scheme, and show that the average waiting time of Harmonic Block Windows schedules asymptotically approaches the tight lower bound.