Broadcasting is an efficient alternative to unicast for delivering
popular on-demand media requests. Windows scheduling algorithms
provide a way to satisfy all requests with both low bandwidth and
low latency.
Consider a system of $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 {\em windows scheduling problem} (WS) each page $i$, $1\le
i\le n$, is associated with a {\em request window} $w_i$. In a
feasible schedule for WS, page $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
{\em buffer scheme} for the windows scheduling problem such that
{\em 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 channel 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 implementing the buffer scheme using this rule, we improve the
%best known performance for instances that have importance in
%broadcasting schemes.
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 $(i)$ pages are arriving and departing
on-line, $(ii)$ the window constraint has some {\em jitter}, and
$(iii)$ different pages might have different lengths.