Budget-Driven Scheduling For DAG Workflows In Clouds

With the rapid development of cloud computing,application service providers are increasingly inclined to move complex application workflows to cloud for execution.The leasing cost of the computing facility brings a new challenge to the workflow scheduling problem in the cloud.This paper studies the optimization problem of scheduling multiple DAG-based workflows(Directed Acyclic Graph)in the cloud under a limited budget.Scheduling of a DAG-based workflow onto heterogeneous processors is an NP-complete problem in general,and precedence constraints among DAG nodes make the problem more complex.This paper first formulates the problem as an integer programming problem,and then proposes a task prioritization scheme with the Markovian chain stationary probabilities as a measure of global importance.Besides,the paper designs a uniform spare budget splitting strategy,which splits the spare budget uniformly across all the tasks.The combined scheme has been simulated and tested on a wide range of workflows.Finally,the implementation of the task-level scheduling strategy is designed and implemented in Spark.The main innovations and contributions of this paper are summarized as follows:1.We formulate an integer programming model of the DAG-based workflow scheduling problem with budget constraints.This model can be solved by integer programming solvers,and the solution can be used as the performance baseline of different heuristic algorithms.2.We propose a weighted upward-rank priority scheme that assigns the scheduling priorities to the tasks.The scheme assigns priorities for those tasks without precedence constraints considering tasks' global importance in the DAG topology,and keeps the precedence order for tasks with precedence constraints.3.We design a uniform spare budget splitting strategy.The budget of subsequent tasks can be dynamically adjusted according to the actual execution of the assigned tasks.The makespan can be improved while the scheduling success rate is guaranteed.4.We preliminarily realizes task-level scheduling module with the weighted upward-rank priority scheme,and the uniform spare budget splitting strategy in Spark.This practice verifies the practicability of the algorithms.We further run some performance tests of common workflow applications with the big data benchmarks.The simulation empirical results demonstrate that the uniform spare budget splitting scheme outperforms the splitting scheme in proportion to extra demand in average for most cases,and the Markovian based prioritization further improves the workflow makespan.The benchmark results show the proposed schemes outperform the Spark's two default job-level scheduling schemes in terms of makespan,fairness and scheduling success rate.