Budget-Constrained Contention-Aware Workflow Scheduling in a Hybrid Cloud

Private clouds offer high controllability but lack scalability, while public clouds provide high scalability with limited controllability. The hybrid cloud paradigm combining them can well balance controllability and scalability nowadays. Increasing numbers of workflow applications are being deployed on a hybrid cloud and this paper investigates how to effectively minimize workflow makespan within a user-specified budget. It first establishes a practical communication contention-cognizant workflow scheduling model for hybrid clouds, where a queueing mode is used to handle multiple data contending for the scarce cross-cloud bandwidth resources. A Budget-constrained Contention-aware Workflow Scheduling (BCWS) heuristic is proposed to optimize the workflow makespan within a given budget. It chooses a subset of cloud instances and allocates each task from the workflow to computing resources sequentially with its data communications scheduled as well. In experiments, traditional contention-agnostic scheduling techniques such as GRP-HEFT, PSO, IPPTS etc. are adapted to the considered model before comparison with the proposed method BCWS. Experimental results verify the superiority of BCWS as it can always achieve the best makespan.