We study broadcast systems that distribute a series of data updates to a large number of passive clients. The updates are sent over a broadcast channel in the form of discrete packets. We assume that clients periodically access the channel to obtain the most recent update. Such scenarios arise in many practical applications, such as distribution of traffic information and market updates to mobile wireless devices. Our goal is to design broadcast schedules that minimize the waiting time, i.e., the amount of time the client needs to wait in order to obtain the most recent update. We assume that each client has a different access pattern depending on the channel conditions, computing power, and storage capabilities. We introduce and analyze optimal universal schedules that guarantee low waiting time for any client, regardless of its behavior.
הערה ביבליוגרפיתFunding Information:
Manuscript received August 4, 2006; revised January 17, 2008. Published August 27, 2008 (projected). The work of J. Bruck was supported in part by the Caltech Lee Center for Advanced Networking and by the National Science Foundation under Grants ANI-0322475 and CCF-0346991. Part of this work was performed while M. Langberg and A. Sprintson were Postdoctoral Scholars at the California Institute of Technology, Pasadena.