Scheduling data processing flows under budget constraint on the cloud

Fei Cao, Dabin Ding, Dunren Che, Michelle M. Zhu, Wen Chi Hou

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

Abstract

Cloud computing is emerging as a promising paradigm for large-scale data-intensive queries modeled as complex Directed Acyclic Graph (DAG)-structured dataflows with arbitrary data operators as nodes and producer-consumer interactions as directed edges. The optimization problem of scheduling dataflows on the Cloud is a very complex and challenging task which is similar to query optimization. Optimization must satisfy a variety of objectives and constraints, while taking into account the particular characteristics of the underlying Cloud environment. In addition to achieving minimum completion time, the commercialization of Clouds requires policies to take users' economic concerns as well. In this paper, we formulate scheduling of dataflows onto Cloud resources under the objective of minimizing the completion time under certain budget constraint. A heuristic scheduling algorithm, Layer-oriented Resource Allocation within Budget constraint (LRA-B) is proposed and evaluated. Experiments are conducted on numerous dataflows and Cloud environment configurations, and the overall results are quite promising and indicate the effectiveness of our algorithm.

Original languageEnglish
Title of host publicationProceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013
Pages69-74
Number of pages6
DOIs
StatePublished - 1 Dec 2013
Event2013 Research in Adaptive and Convergent Systems, RACS 2013 - Montreal, QC, Canada
Duration: 1 Oct 20134 Oct 2013

Publication series

NameProceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013

Other

Other2013 Research in Adaptive and Convergent Systems, RACS 2013
CountryCanada
CityMontreal, QC
Period1/10/134/10/13

Fingerprint

Scheduling
Heuristic algorithms
Cloud computing
Scheduling algorithms
Resource allocation
Economics
Experiments

Keywords

  • budget constraint
  • cloud computing
  • completion time
  • dataflows
  • scheduling

Cite this

Cao, F., Ding, D., Che, D., Zhu, M. M., & Hou, W. C. (2013). Scheduling data processing flows under budget constraint on the cloud. In Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013 (pp. 69-74). (Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013). https://doi.org/10.1145/2513228.2513250
Cao, Fei ; Ding, Dabin ; Che, Dunren ; Zhu, Michelle M. ; Hou, Wen Chi. / Scheduling data processing flows under budget constraint on the cloud. Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013. 2013. pp. 69-74 (Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013).
@inproceedings{5608cbeccba44339aaa0ab58fc83c377,
title = "Scheduling data processing flows under budget constraint on the cloud",
abstract = "Cloud computing is emerging as a promising paradigm for large-scale data-intensive queries modeled as complex Directed Acyclic Graph (DAG)-structured dataflows with arbitrary data operators as nodes and producer-consumer interactions as directed edges. The optimization problem of scheduling dataflows on the Cloud is a very complex and challenging task which is similar to query optimization. Optimization must satisfy a variety of objectives and constraints, while taking into account the particular characteristics of the underlying Cloud environment. In addition to achieving minimum completion time, the commercialization of Clouds requires policies to take users' economic concerns as well. In this paper, we formulate scheduling of dataflows onto Cloud resources under the objective of minimizing the completion time under certain budget constraint. A heuristic scheduling algorithm, Layer-oriented Resource Allocation within Budget constraint (LRA-B) is proposed and evaluated. Experiments are conducted on numerous dataflows and Cloud environment configurations, and the overall results are quite promising and indicate the effectiveness of our algorithm.",
keywords = "budget constraint, cloud computing, completion time, dataflows, scheduling",
author = "Fei Cao and Dabin Ding and Dunren Che and Zhu, {Michelle M.} and Hou, {Wen Chi}",
year = "2013",
month = "12",
day = "1",
doi = "10.1145/2513228.2513250",
language = "English",
isbn = "9781450323482",
series = "Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013",
pages = "69--74",
booktitle = "Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013",

}

Cao, F, Ding, D, Che, D, Zhu, MM & Hou, WC 2013, Scheduling data processing flows under budget constraint on the cloud. in Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013. Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013, pp. 69-74, 2013 Research in Adaptive and Convergent Systems, RACS 2013, Montreal, QC, Canada, 1/10/13. https://doi.org/10.1145/2513228.2513250

Scheduling data processing flows under budget constraint on the cloud. / Cao, Fei; Ding, Dabin; Che, Dunren; Zhu, Michelle M.; Hou, Wen Chi.

Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013. 2013. p. 69-74 (Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013).

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

TY - GEN

T1 - Scheduling data processing flows under budget constraint on the cloud

AU - Cao, Fei

AU - Ding, Dabin

AU - Che, Dunren

AU - Zhu, Michelle M.

AU - Hou, Wen Chi

PY - 2013/12/1

Y1 - 2013/12/1

N2 - Cloud computing is emerging as a promising paradigm for large-scale data-intensive queries modeled as complex Directed Acyclic Graph (DAG)-structured dataflows with arbitrary data operators as nodes and producer-consumer interactions as directed edges. The optimization problem of scheduling dataflows on the Cloud is a very complex and challenging task which is similar to query optimization. Optimization must satisfy a variety of objectives and constraints, while taking into account the particular characteristics of the underlying Cloud environment. In addition to achieving minimum completion time, the commercialization of Clouds requires policies to take users' economic concerns as well. In this paper, we formulate scheduling of dataflows onto Cloud resources under the objective of minimizing the completion time under certain budget constraint. A heuristic scheduling algorithm, Layer-oriented Resource Allocation within Budget constraint (LRA-B) is proposed and evaluated. Experiments are conducted on numerous dataflows and Cloud environment configurations, and the overall results are quite promising and indicate the effectiveness of our algorithm.

AB - Cloud computing is emerging as a promising paradigm for large-scale data-intensive queries modeled as complex Directed Acyclic Graph (DAG)-structured dataflows with arbitrary data operators as nodes and producer-consumer interactions as directed edges. The optimization problem of scheduling dataflows on the Cloud is a very complex and challenging task which is similar to query optimization. Optimization must satisfy a variety of objectives and constraints, while taking into account the particular characteristics of the underlying Cloud environment. In addition to achieving minimum completion time, the commercialization of Clouds requires policies to take users' economic concerns as well. In this paper, we formulate scheduling of dataflows onto Cloud resources under the objective of minimizing the completion time under certain budget constraint. A heuristic scheduling algorithm, Layer-oriented Resource Allocation within Budget constraint (LRA-B) is proposed and evaluated. Experiments are conducted on numerous dataflows and Cloud environment configurations, and the overall results are quite promising and indicate the effectiveness of our algorithm.

KW - budget constraint

KW - cloud computing

KW - completion time

KW - dataflows

KW - scheduling

UR - http://www.scopus.com/inward/record.url?scp=84891376735&partnerID=8YFLogxK

U2 - 10.1145/2513228.2513250

DO - 10.1145/2513228.2513250

M3 - Conference contribution

AN - SCOPUS:84891376735

SN - 9781450323482

T3 - Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013

SP - 69

EP - 74

BT - Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013

ER -

Cao F, Ding D, Che D, Zhu MM, Hou WC. Scheduling data processing flows under budget constraint on the cloud. In Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013. 2013. p. 69-74. (Proceedings of the 2013 Research in Adaptive and Convergent Systems, RACS 2013). https://doi.org/10.1145/2513228.2513250