R×W: a scheduling approach for large-scale on-demand data broadcast

Broadcast is becoming an increasingly attractive data-dissemination method for large client populations. In order to effectively utilize a broadcast medium for such a service, it is necessary to have efficient on-line scheduling algorithms that can balance individual and overall performance and can scale in terms of data set sizes, client populations, and broadcast bandwidth. We propose an algorithm, called R×W, that provides good performance across all of these criteria and can be tuned to trade off average and worst-case waiting time. Unlike previous work on low overhead scheduling, the algorithm does not use estimates of the access probabilities of items, but rather, it makes scheduling decisions based on the current queue state, allowing it to easily adapt to changes in the intensity and distribution of the workload. We demonstrate the performance advantages of the algorithm under a range of scenarios using a simulation model and present analytical results that describe the intrinsic behavior of the algorithm