NDLI: Tail asymptotics for policies favoring short jobs in a many-flows regime

Content Provider	ACM Digital Library
Author	Harchol-Balter, Mor Shakkottai, Sanjay Wierman, Adam Yang, Chang-Woo
Abstract	Scheduling policies that prioritize short jobs have received growing attention in recent years. The class of SMART policies includes many such disciplines, e.g. Shortest-Remaining-Processing-Time (SRPT) and Preemptive-Shortest-Job-First (PSJF). In this work, we study the delay distribution of SMART policies and contrast this distribution with that of the Least-Attained-Service (LAS) policy, which indirectly favors short jobs by prioritizing jobs with the least attained service (age).We study the delay distribution (rate function) of LAS and the SMART class in a discrete-time queueing system under the many sources regime. Our analysis in this regime (large capacity and large number of flows) hinges on a novel two dimensional queue representation, which creates tie-break rules. These additional rules do not alter the policies, but greatly simplify their analysis. We demonstrate that the queue evolution of all the above policies can be described under this single two dimensional framework.We prove that all SMART policies have the same delay distribution as SRPT and illustrate the improvements SMART policies make over First-Come-First-Served (FCFS). Furthermore, we show that the delay distribution of SMART policies stochastically improves upon the delay distribution of LAS. However, the delay distribution under LAS is not too bad -- the distribution of delay under LAS for most jobs sizes still provides improvement over FCFS. Our results are complementary to prior work that studies delay-tail behavior in the large buffer regime under a single flow.
Starting Page	97
Ending Page	108
Page Count	12
File Format	PDF
ISSN	01635999
DOI	10.1145/1140103.1140290
Journal	ACM SIGMETRICS Performance Evaluation Review (PERV)
Volume Number	34
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-01-10
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Srpt Many--sources Rate function Scheduling Large--deviations Smart Las
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Tail asymptotics for policies favoring short jobs in a many-flows regime

Scheduling in multi-channel wireless networks:rate function optimality in the small-buffer regime

Many Flows Asymptotics for SMART Scheduling Policies

On the optimal trade-off between SRPT and opportunistic scheduling

Many flows asymptotics for smart scheduling policies (2006).

Many flows asymptotics for SMART scheduling policies,” preprint

Nearly insensitive bounds on SMART scheduling

Scheduling despite inexact job-size information

Classifying scheduling policies with respect to unfairness in an M/GI/1

Tail asymptotics for policies favoring short jobs in a many-flows regime

Similar Documents

Tail asymptotics for policies favoring short jobs in a many-flows regime

Scheduling in multi-channel wireless networks:rate function optimality in the small-buffer regime

Many Flows Asymptotics for SMART Scheduling Policies

On the optimal trade-off between SRPT and opportunistic scheduling

Many flows asymptotics for smart scheduling policies (2006).

Many flows asymptotics for SMART scheduling policies,” preprint

Nearly insensitive bounds on SMART scheduling

Scheduling despite inexact job-size information

Classifying scheduling policies with respect to unfairness in an M/GI/1

Tail asymptotics for policies favoring short jobs in a many-flows regime