Scheduling on-demand broadcasts
Swarup Acharya, Subramanian Muthukrishnan · 1998
Assatellite,wirelessand CableW-based networksspreadtheir reach, there is an increased infrastructure of high-bandwidth links into the home and on the road.Much of this enhanced infrastructure inherently reties on bmdcast tuhnology to deliver data to large user populations.This increase in broadcast capacity has been complemented by the growth of large-scale infomtion-centn.capptimtions.Many of these applications such as wireless interneta and traffic information systems are .pull-hosed, that is, they respond to on-denrarrd user requests.In this paper, we study the scheduling problems arising in such on-demand broadwt environments for applications with data requests of varying sizes, and the novel issues that arise therein.We study the problem in its generality while much of the previous work has fwusd on one speciat case or the other, such as, assuming identid-sized data requests, or static ctient a-s profiles known by the server u pm"on.,etc.Traditionally, the response time of the requ~ts has been used as a performance measure.In this paper, we additionally motivate an alternative metric -the sfretch of a request, which seems better suited to variable-sized requests.Our main contribution is an algorithm Aled ~based on the criteria of optimizing the worst ease stretch of individud requests.w is simple and effitien~firthersnore, as our experiments show, it performs well mmpared to more expensive strategies that serve as yardsticks for optimizing worstiaverage case response timdstretch m-ures.Finding a right brdancebetween the worst case ~ndividud) and the average ease Qlobd) performanceis a key challenge.Surprisingly,w seems to find such a batanu.Additionrdly, even"though it is dmignd to minimize the stretch, it performs reasonably well on the tradition response time measure too.