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^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^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^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.