Windows scheduling as a paradigm for pushing information in wireless networks

摘要

Given are n positive integers w1, w2, ..., wn called windows. The windows are associated with n equal length information pages. In the windows scheduling problem, the goal is to schedule all the pages on minimum number of identical broadcasting channels such that the gap between two consecutive appearances of page i on any of the channels is at most wi time slots where a time slot is the broadcasting time of one page.Our main application for windows scheduling is the implementation of efficient push systems for cellular and satellite networks. In such systems, the window size associated with a page corresponds to the quality of service associated with the page. That is, the window size is the maximum number of time slots a client who is listening to all the broadcasting channels needs to wait until it receives a particular page. Push systems are crucial to such wireless systems due to their one-way communication nature in which mobile users cannot use (or it is tooexpensive for them to use) pull systems to receive information. Push systems are also desirable for very popular information pages that would create bottlenecks if provided only via pull systems.Windows scheduling belongs to the general class of periodic scheduling problems that has applications in many disciplines (e.g., operations research, networking). The pages can be viewed as jobs and the channels as machines. The traditional optimization goal in periodic scheduling is an "average" type goal in which a job should be scheduled 1/wi fraction of the time and the quality of an algorithm is determined by some fairness issues. On the other hand, the windows scheduling problem has a "max" type optimization goal in which the gap between two consecutive appearances of a request must be smaller than wi. Both optimization goals provide practical solutions to the many applications of periodic scheduling.We discuss recent results and open problems for windows scheduling and its variants in off-line and on-line settings.