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

Qiaomin Xie, Yi Lu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publication2015 IEEE Conference on Computer Communications, IEEE INFOCOM 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages963-972
Number of pages10
ISBN (Electronic)9781479983810
DOIs
StatePublished - Aug 21 2015
Event34th IEEE Annual Conference on Computer Communications and Networks, IEEE INFOCOM 2015 - Hong Kong, Hong Kong
Duration: Apr 26 2015May 1 2015

Publication series

NameProceedings - IEEE INFOCOM
Volume26
ISSN (Print)0743-166X

Other

Other34th IEEE Annual Conference on Computer Communications and Networks, IEEE INFOCOM 2015
CountryHong Kong
CityHong Kong
Period4/26/155/1/15

    Fingerprint

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Cite this

Xie, Q., & Lu, Y. (2015). Priority algorithm for near-data scheduling: Throughput and heavy-traffic optimality. In 2015 IEEE Conference on Computer Communications, IEEE INFOCOM 2015 (pp. 963-972). [7218468] (Proceedings - IEEE INFOCOM; Vol. 26). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/INFOCOM.2015.7218468