Technical Report CS-2005-04

TR#:CS-2005-04
Class:CS
Title: On Centralized Smooth Scheduling
Authors: Ami Litman, Shiri Moran-Schein
PDFCS-2005-04.pdf
Abstract: This paper studies evenly distributed sets of natural numbers and their applications to scheduling in a centralized environment. Such sets, called {\em smooth sets}, have the property that their quantity within each interval is proportional to the size of the interval, up to a bounded additive deviation; namely, for $\rho,\Delta\in\reals$ a set $A$ of natural numbers is {\em $(\rho,\Delta)$-smooth} if $\mbox{abs}(\card{I}\cdot \rho-\card{I\cap A})<\Delta$ for any interval $I\subset \naturals$. The current paper studies scheduling {\em persistent clients} on a single slot-oriented {\em resource} in a flexible and predictable manner. Each client $\gamma$ has a given {\em rate} $\rho_\gamma$ that defines the share of the resource he is entitled to receive and the goal is a {\em smooth schedule} in which, for some predefined $\Delta$, each client $\gamma$ is served in a $(\rho_\gamma,\Delta)$-smooth set of slots (natural numbers). The paper considers a centralized environment where a single algorithm computes the user of the current slot. (An accompanying paper studies a distributed environment in which each client by itself computes whether or not it owns the current slot.) An important contribution of this paper is the construction of a smooth schedule with an extremely efficient algorithm that computes the user of each slot in $O(\log\log q)$ time and $O(n)$ space, where $n$ is the number of clients and $q\eqdef \max\set{\rho_\gamma/\rho_{\gamma'}\s \gamma,\gamma'\in\Gamma}$; in many practical applications this $O(\log\log q)$ value is actually a small constant. Our scheduling technique is based on a reduction from allocation of slots to allocation of sub-intervals of the unit interval. This technique naturally extends to the problem of scheduling multiple resources, even under the restriction that a client can be served concurrently by at most one resource. This paper constructs such a schedule in which the users of each slot are computed extremely fast --- in $O(m\log\log q)$ time per slot and $O(n)$ space where $m$ is the number of resources; this result is a significant improvement on the prior fastest algorithm that produces such a schedule (actually of a special type --- a P-fair schedule) in $O(m\log n)$ time per slot and $O(n)$ space. Moreover, the paper introduces a novel approach to multi-resource scheduling in which each resource independently computes, slot after slot, what client to serve in this slot; the paper presents such a schedule computed in $O(\log\log q)$ time per slot and $O(n)$ space; prior to our work, nothing was known about such independent computation. Finally, this paper demonstrates the usefulness of smooth schedules by showing that they are highly attractive for multiplexing the links of a connection-oriented packet switching network.
CopyrightThe 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/2005/CS/CS-2005-04), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2005
To the main CS technical reports page

Computer science department, Technion
admin