A Tight Analysis of Most-Requested-First for On-Demand Data Broadcast.

This paper gives a complete and tight mathematical analysis on the performance of the Most-Requested-First algorithm for on-demand data broadcast. The algorithm is natural and simple, yet its performance is surprisingly good in practice. We derive tight upper and lower bounds on MRF's competitiveness and thus reveal the exact competitive ratios of the algorithm under different system configurations. We prove that the competitive ratio of MRF is exactly $3 - \frac{\ell}{d}$ when the start-up delay d is a multiple of the page length ℓ; otherwise the ratio is 3. [ABSTRACT FROM AUTHOR]