On-Demand Broadcast Scheduling
On-Demand Broadcast Scheduling
Loading...
Files
Publication or External Link
Date
1999-10-09
Authors
Aksoy, Demet
Franklin, Michael
Advisor
Citation
DRUM DOI
Abstract
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 RxW, that provides
good performance across all of these criteria and that 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.
(Also cross-referenced as UMIACS-TR-98-88)