Scheduling with multi-level data locality: Throughput and heavy-traffic optimality

Qiaomin Xie, Ali Yekkehkhany, Yi Lu

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

Abstract

A fundamental problem to all data-parallel applications is data locality. An example is map task scheduling in the MapReduce framework. Existing theoretical work analyzes systems with only two levels of locality, despite the existence of multiple locality levels within and across data centers. We found that going from two to three levels of locality changes the problem drastically, as a tradeoff between performance and throughput emerges. The recently proposed priority algorithm, which is throughput and heavy-traffic optimal for two locality levels, is not even throughput-optimal with three locality levels. The JSQ-MaxWeight algorithm proposed by Wang et al. is heavy-traffic optimal only for a special traffic scenario with two locality levels. We show that an extension of the JSQ-MaxWeight algorithm to three locality levels preserves its throughput-optimality, but suffers from the same lack of heavy-traffic optimality for most traffic scenarios. We propose a novel algorithm that uses Weighted-Workload (WW) routing and priority service. We establish its throughput and heavy-traffic optimality for all traffic scenarios. The main challenge is the construction of an appropriate ideal load decomposition that allows the separate treatment of different subsystems.

Original languageEnglish (US)
Title of host publicationIEEE INFOCOM 2016 - 35th Annual IEEE International Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781467399531
DOIs
StatePublished - Jul 27 2016
Event35th Annual IEEE International Conference on Computer Communications, IEEE INFOCOM 2016 - San Francisco, United States
Duration: Apr 10 2016Apr 14 2016

Publication series

NameProceedings - IEEE INFOCOM
Volume2016-July
ISSN (Print)0743-166X

Other

Other35th Annual IEEE International Conference on Computer Communications, IEEE INFOCOM 2016
CountryUnited States
CitySan Francisco
Period4/10/164/14/16

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Scheduling with multi-level data locality: Throughput and heavy-traffic optimality'. Together they form a unique fingerprint.

  • Cite this

    Xie, Q., Yekkehkhany, A., & Lu, Y. (2016). Scheduling with multi-level data locality: Throughput and heavy-traffic optimality. In IEEE INFOCOM 2016 - 35th Annual IEEE International Conference on Computer Communications [7524416] (Proceedings - IEEE INFOCOM; Vol. 2016-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/INFOCOM.2016.7524416