On workflow scheduling for end-to-end performance optimization in distributed network environments

Qishi Wu, Daqing Yun, Xiangyu Lin, Yi Gu, Wuyin Lin, Yangang Liu

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

6 Scopus citations

Abstract

Next-generation computational sciences feature large-scale workflows of many computing modules that must be deployed and executed in distributed network environments. With limited computing resources, it is often unavoidable to map multiple workflow modules to the same computer node with possible concurrent module execution, whose scheduling may significantly affect the workflow's end-to-end performance in the network. We formulate this on-node workflow scheduling problem as an optimization problem and prove it to be NP-complete. We then conduct a deep investigation into workflow execution dynamics and propose a Critical Path-based Priority Scheduling (CPPS) algorithm to achieve Minimum End-to-end Delay (MED) under a given workflow mapping scheme. The performance superiority of the proposed CPPS algorithm is illustrated by extensive simulation results in comparison with a traditional fair-share (FS) scheduling policy and is further verified by proof-of-concept experiments based on a real-life scientific workflow for climate modeling deployed and executed in a testbed network.

Original languageEnglish (US)
Title of host publicationJob Scheduling Strategies for Parallel Processing - 16th International Workshop, JSSPP 2012, Revised Selected Papers
Pages76-95
Number of pages20
DOIs
StatePublished - Jan 24 2013
Externally publishedYes
Event16th Workshop on Job Scheduling Strategies for Parallel Processing, JSSPP 2012 - Shanghai, China
Duration: May 25 2012May 25 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7698 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other16th Workshop on Job Scheduling Strategies for Parallel Processing, JSSPP 2012
CountryChina
CityShanghai
Period5/25/125/25/12

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Scientific workflows
  • end-to-end delay
  • task scheduling

Fingerprint Dive into the research topics of 'On workflow scheduling for end-to-end performance optimization in distributed network environments'. Together they form a unique fingerprint.

Cite this