End-to-End Delay Minimization for Scientific Workflows in Clouds under Budget Constraint
Authors:
- 15 September 2014
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Cloud Computing
- Vol. 3 (2) , 169-181
Abstract
Next-generation e-Science features large-scale, compute-intensive workflows of many computing modules that are typically executed in a distributed manner. With the recent emergence of cloud computing and the rapid deployment of cloud infrastructures, an increasing number of scientific workflows have been shifted or are in active transition to cloud environments. As cloud computing makes computing a utility, scientists across different application domains are facing the same challenge of reducing financial cost in addition to meeting the traditional goal of performance optimization. We develop a prototype generic workflow system by leveraging existing technologies for a quick evaluation of scientific workflow optimization strategies. We construct analytical models to quantify the network performance of scientific workflows using cloud-based computing resources, and formulate a task scheduling problem to minimize the workflow end-to-end delay under a user-specified financial constraint. We rigorously prove that the proposed problem is not only NP-complete but also non-approximable. We design a heuristic solution to this problem, and illustrate its performance superiority over existing methods through extensive simulations and real-life workflow experiments based on proof-of-concept implementation and deployment in a local cloud testbed.Keywords
Funding Information
- U.S. Department of Energy’s Office of Science (DE-SC0010641)
- University of Memphis (DE-AC02-98CH10886)
- Brookhaven National Laboratory
- Laboratory Directed Research and Development (LDRD-13-017)
This publication has 26 references indexed in Scilit:
- A Budget Constrained Scheduling Algorithm for Workflow ApplicationsJournal of Grid Computing, 2014
- Budget-Deadline Constrained Workflow Planning for Admission ControlJournal of Grid Computing, 2013
- Deadline-constrained workflow scheduling in software as a service CloudScientia Iranica, 2012
- Optimizing end-to-end performance of data-intensive computing pipelines in heterogeneous network environmentsJournal of Parallel and Distributed Computing, 2011
- Galaxy: a comprehensive approach for supporting accessible, reproducible, and transparent computational research in the life sciencesGenome Biology, 2010
- CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithmsSoftware: Practice and Experience, 2010
- Deadline/Budget‐Based Scheduling of Workflows on Utility Grids2009
- Scheduling Workflows with Budget Constraints2007
- Improving scheduling of tasks in a heterogeneous environmentIEEE Transactions on Parallel and Distributed Systems, 2004
- Performance-effective and low-complexity task scheduling for heterogeneous computingIEEE Transactions on Parallel and Distributed Systems, 2002