Schedule Compaction and Deadline Constrained DAG Scheduling for IaaS Cloud

摘要

Most cloud workflow scheduling algorithms assume that resources are charged under an ideal pay-as-you-go model, which may not be the case in real production cloud systems. Currently, most IaaS cloud providers charge users on billing cycle basis. If a resource is terminated before one billing cycle, the payment is still rounded up to one cycle. To address this problem, we firstly formalized it using bin-package method. Then, we propose a DAG schedule compaction algorithm of IC-*-SC, which compacts schedules generated by already exist algorithms to reduce resource requirement. Based on the compaction idea, we also propose a deadline constrained DAG scheduling algorithm of IC-SC. We compare our algorithms with state-of-the-art algorithms of IC-PCP and IC-PCPD2, and use 2 well-known scientific workflow applications for evaluation. Experimental results show that our algorithms reduce monetary cost drastically.