Lower bounds on average-case delay for video-on-demand broadcast protocols
Wei-Lung Dustin Tseng, David G. Kirkpatrick · Symposium on Discrete Algorithms · 2007
Video-on-demand broadcast protocols are commonly used to deliver video content to a large uncoordinated set of consumers. Since broadcast protocols are not attuned to individual user requests, some delay in service is unavoidable. The worst-case delay, expressed as a function of the available bandwidth, has been well studied; matching upper and lower bounds have been established in a very general setting. In this paper we turn our attention to average-case delay. We establish asymptotically tight lower bounds on average-case delay in the situation where receiver and sender bandwidths are equal. It follows from our results that existing worst-case-optimal broadcast protocols are, to within a small constant factor, optimal in the average case as well.