NDLI: Priority algorithm for near-data scheduling: Throughput and heavy-traffic optimality

Content Provider	IEEE Xplore Digital Library
Author	Qiaomin Xie Yi Lu
Copyright Year	2015
Description	Author affiliation: Univ. of Illinois at Urbana-Champaign, Urbana, IL, USA (Qiaomin Xie; Yi Lu)
Abstract	The prevalence of data-parallel applications has made near-data scheduling an important problem. An example is the map task scheduling in the map-reduce framework. Wang et. al. [13] was the first to identify its capacity region and proposed a throughput-optimal algorithm based on MaxWeight. However, the study of the algorithm's delay performance revealed that it is only heavy-traffic optimal for a very special traffic scenario, where all traffic concentrates on a subset of servers. We propose a simple “local-tasks first” priority algorithm and show that it is throughput-optimal and heavy-traffic optimal for all traffic scenarios, i.e., it asymptotically minimizes the average delay as the arrival rate vector approaches the boundary of the capacity region. So far, it is the only known heavy-traffic optimal algorithm for this setting. As the algorithm is based on pre-determined priority, a direct application of the Lyapunov drift technique does not work. The main proof ideas are the construction of an ideal load decomposition and the separate treatment of two subsystems based on their ideal load. To the best of our knowledge, this is the only setup of affinity scheduling where a simple priority algorithm is shown to be heavy-traffic optimal. Simulation shows that our algorithm also significantly outperforms existing algorithms at loads away from the boundary of the capacity region.
Starting Page	963
Ending Page	972
File Size	321459
Page Count	10
File Format	PDF
ISBN	9781479983810
DOI	10.1109/INFOCOM.2015.7218468
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-04-26
Publisher Place	Hong Kong
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Servers Job shop scheduling Throughput Load modeling Conferences Computers Delays
Content Type	Text
Resource Type	Article

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

Deadline scheduling with priority for client-server systems on the grid

Map task scheduling in MapReduce with data locality: Throughput and heavy-traffic optimality

MapTask Scheduling in MapReduce With Data Locality: Throughput and Heavy-Traffic Optimality

A classification of job scheduling algorithms for balancing load on web servers.

A priority rule-based scheduling algorithm for complex manufacturing system

Traffic-aware message scheduling method for ISA100.11a

Enhancing local scheduling rules with a global benefit factor

Reducing Job Slowdown Variability for Data-Intensive Workloads

Performance evaluation and asymptotics for Content Delivery Networks

Priority algorithm for near-data scheduling: Throughput and heavy-traffic optimality

Similar Documents

Deadline scheduling with priority for client-server systems on the grid

Map task scheduling in MapReduce with data locality: Throughput and heavy-traffic optimality

MapTask Scheduling in MapReduce With Data Locality: Throughput and Heavy-Traffic Optimality

A classification of job scheduling algorithms for balancing load on web servers.

A priority rule-based scheduling algorithm for complex manufacturing system

Traffic-aware message scheduling method for ISA100.11a

Enhancing local scheduling rules with a global benefit factor

Reducing Job Slowdown Variability for Data-Intensive Workloads

Performance evaluation and asymptotics for Content Delivery Networks

Priority algorithm for near-data scheduling: Throughput and heavy-traffic optimality