Stretch-Optimal Scheduling for On-Demand

In order to effectively utilize the broadcast bandwidth, it is necessary to have efficient on-line scheduling algorithms that can balance individual and overall performance and can scale in terms of database sizes and client populations. Moreover, the scheduling algorithm should be applicable to a heterogeneous environment where data items have different sizes. We address these issues in this paper. As stretch is widely adopted as a performance metric for variable-size data requests, we propose a broadcast scheduling algorithm to optimize the system performance in terms of stretch. We show by analysis that the proposed algorithm can indeed achieve the optimal performance in terms of stretch. Moreover, the proposed scheduling algorithm has very low decision overhead, which makes it a practical solution for on-demand broadcast scheduling. Simulation results demonstrate that our algorithm significantly outperforms existing scheduling algorithms under various scenarios