### A general buffer scheme for the windows scheduling problemA general buffer scheme for the windows scheduling problem

Access Restriction
Subscribed

 Author Bar-Noy, Amotz ♦ Ladner, Richard E. ♦ Christensen, Jacob ♦ Tamir, Tami Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Periodic scheduling ♦ Media-on-demand Abstract Broadcasting is an efficient alternative to unicast for delivering popular on-demand media requests. Broadcasting schemes that are based on windows scheduling algorithms provide a way to satisfy all requests with both low bandwidth and low latency. Consider a system of $\textit{n}$ pages that need to be scheduled (transmitted) on identical channels an infinite number of times. Time is slotted, and it takes one time slot to transmit each page. In the windows scheduling problem (WS) each page $\textit{i},$ 1 ≤ $\textit{i}$ ≤ $\textit{n},$ is associated with a request window $w_{i}.$ In a feasible schedule for WS, page $\textit{i}$ must be scheduled at least once in any window of $w_{i}$ time slots. The objective function is to minimize the number of channels required to schedule all the pages. The main contribution of this paper is the design of a general buffer scheme for the windows scheduling problem such that $\textit{any}$ algorithm for WS follows this scheme. As a result, this scheme can serve as a tool to analyze and/or exhaust all possible WS-algorithms. The buffer scheme is based on modelling the system as a nondeterministic finite state machine in which any directed cycle corresponds to a legal schedule and vice-versa. Since WS is NP-hard, we present some heuristics and pruning-rules for cycle detection that ensure reasonable cycle-search time. By introducing various rules, the buffer scheme can be transformed into deterministic scheduling algorithms. We show that a simple page-selection rule for the buffer scheme provides an optimal schedule to WS for the case where all the $w_{i}'s$ have divisible sizes, and other good schedules for some other general cases. By using an exhaustive-search, we prove impossibility results for other important instances. We also show how to extend the buffer scheme to more generalized environments in which $(\textit{i})$ pages are arriving and departing on-line, $(\textit{ii})$ the window constraint has some $\textit{jitter},$ and $(\textit{iii})$ different pages might have different lengths. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-02-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 13 Page Count 12 Starting Page 1.6 Ending Page 1.17

#### Open content in new tab

Source: ACM Digital Library