Access Restriction

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

   Open content in new tab
Source: ACM Digital Library