A Caltech Library Service

Many Flows Asymptotics for SMART Scheduling Policies

Yang, Changwoo and Wierman, Adam and Shakkottai, Sanjay and Harchol-Balter, Mor (2012) Many Flows Asymptotics for SMART Scheduling Policies. IEEE Transactions on Automatic Control, 57 (2). pp. 376-391. ISSN 0018-9286.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Scheduling policies that favor small jobs have received growing attention due to their superior performance with respect to mean delay, e.g., Shortest Remaining Processing Time (SRPT) and Preemptive Shortest Job First (PSJF). In this paper, we study the delay distribution of a generalization of the class of scheduling policies called SMART (because policies in it have “SMAll Response Times”), which includes SRPT, PSJF, and a range of practical variants, in a discrete-time queueing system under the many sources large deviations regime. Our analysis of SMART in this regime (large number of flows and large capacity) hinges on a novel two-dimensional (2-D) queueing framework that employs virtual queues and total ordering of jobs. We prove that all SMART policies have the same asymptotic delay distribution as SRPT, i.e., the delay distribution has the same decay rate. In addition, we illustrate the improvements SMART policies make over First Come First Serve (FCFS) and Processor Sharing (PS). Our 2-D queueing technique is generalizable to other policies as well. As an example, we show how the Foreground-Background (FB) policy can be analyzed using a 2-D queueing framework. FB is a policy, not contained in SMART, which manages to bias towards small jobs without knowing which jobs are small in advance.

Item Type:Article
Related URLs:
URLURL TypeDescription DOIArticle
Additional Information:© 2011 IEEE. Manuscript received March 31, 2010; accepted June 26, 2011. Date of publication October 25, 2011; date of current version January 27, 2012. This paper was presented in part at the Proceedings of ACM Sigmetrics, June 2006. Recommended by Associate Editor S. Mascolo.
Subject Keywords:Foreground-background (FB); many sources large deviation; shortest remaining processing time (SRPT); two-dimensional (2-D) queueing
Issue or Number:2
Record Number:CaltechAUTHORS:20120326-084346980
Persistent URL:
Official Citation:Changwoo Yang; Wierman, A.; Shakkottai, S.; Harchol-Balter, M.; , "Many Flows Asymptotics for SMART Scheduling Policies," Automatic Control, IEEE Transactions on , vol.57, no.2, pp.376-391, Feb. 2012 doi: 10.1109/TAC.2011.2173418 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29836
Deposited By: Tony Diaz
Deposited On:17 Apr 2012 22:15
Last Modified:29 Jul 2020 23:21

Repository Staff Only: item control page