| TR#: | CS-2006-13 |
| Class: | CS |
| Title: | Smooth Scheduling Under Variable Rates or The Analog-Digital Confinement Game |
| Authors: | Ami Litman and Shiri Moran-Schein |
| PostScript | CS-2006-13.ps.gz - CS-2006-13.ps |
| CS-2006-13.pdf | |
| Abstract: | This work considers non-terminating scheduling problems in which a
system of multiple resources serves clients having variable needs.
The system has $m$ identical resources and $n$ clients; in each
{\em time slot} each resource may serve at most one client; in
each such slot $t$ each client $\gamma$ has a {\em rate}, a real
number $\rho_\gamma(t)$, that specifies his needs in this slot.
The rates satisfy the restriction $\sum_\gamma \rho_\gamma(t)\leq
m$ for any slot $t$. Except of this restriction, the rates can
vary in arbitrary fashion. (This contrasts most prior works in
this area in which the rates of the clients are constant.) The
schedule is required to be {\em smooth} as follows: a schedule is
{\em $\Delta$-smooth} if for all time intervals $I$ the absolute
difference between the amount of service received by each client
$\gamma$ to his nominal needs of $\sum_{t\in I}\rho_\gamma(t)$ is
less than $\Delta$. Our objective are online schedulers that
produce $\Delta$-smooth schedules where $\Delta$ is a small
constant which is independent of $m$ and $n$.
Our paper constructs such schedulers; these are the first online
$\Delta$-smooth schedulers, with a constant $\Delta$, for clients
with arbitrarily variable rates in a single or multiple resource
system. Furthermore, the paper also considers a {\em
non-concurrent} environment in which there is an additional
restriction that each client is served at most once in each time
slot; it presents the first online smooth schedulers for variable
rates under this restriction.
The above non-concurrent restriction is crucial in some
applications (e.g., CPU scheduling). It has been pointed out that
this restriction ``adds a surprising amount of difficulty'' to the
scheduling problem. However, this observation was never formalized
and, of course, was never proved. This paper formalizes and proves
some aspects of this observation.
Another contribution of this paper is the introduction of a complete information, two player game called {\em the analog-digital confinement game}. In such a game {\em pebbles} are located on the real line; the two players, the {\em analog player} and the {\em digital player}, take alternating turns and each one, in his turn, moves some of the pebbles; the digital player moves the pebbles backwards by discrete distances while the analog player moves the pebbles forward by analog distances; the aim of the {\em analog player} is to cause one pebble (or more) to escape a pre-defined real interval while the aim of the {\em digital player} is to confine the pebbles into the interval. This game is a convenient framework to study the general question of how to approximate an analog process by a digital one. All the above scheduling results are established via this game. In this derivation, the pebbles represent the clients, the analog player represents the needs of the clients and the digital player represents the scheduler. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2006/CS/CS-2006-13), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 2006
To the main CS technical reports page