Budget constrained dataflow scheduling for minimized completion time on the cloud

Cloud computing provides high-end computing capabilities so that users can access data and applications anywhere in the world on demand and pay for what they use. It is emerging as a promising computing paradigm for large-scale data intensive queries, which are usually modeled as complex Directed Acyclic Graph (DAG)-structured data processing 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 query 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 toward the objective of minimizing the query 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.