A Compromised-Time-Cost Scheduling Algorithm in SwinDeW-C for Instance-Intensive Cost-Constrained Workflows on a Cloud Computing Platform

Abstract

The concept of cloud computing continues to spread widely, as it has been accepted recently. Cloud computing has many unique advantages which can be utilized to facilitate workflow execution. Instance-intensive cost-constrained cloud workflows are workflows with a large number of workflow instances (i.e. instance intensive) bounded by a certain budget for execution (i.e. cost constrained) on a cloud computing platform (i.e. cloud workflows). However, there are, so far, no dedicated scheduling algorithms for instance-intensive cost-constrained cloud workflows. This paper presents a novel compromised-time-cost scheduling algorithm which considers the characteristics of cloud computing to accommodate instance-intensive cost-constrained workflows by compromising execution time and cost with user input enabled on the fly. The simulation performed demonstrates that the algorithm can cut down the mean execution cost by over 15% whilst meeting the user-designated deadline or shorten the mean execution time by over 20% within the user-designated execution cost.

Keywords

Cloud Workflows Workflow Scheduling Algorithms Instance-Intensive Workflows Cost-Constrained Workflows Cloud Computing

Get full access to this article

View all access options for this article.

References

Berman, F. , Chien, A. , Cooper, K. , Dongarra, J. , Foster, I. , Gannon, D. , Johnsson, L. , Kennedy, K. , Kesselman, C. , Mellor-Crummey, J. , Reed, D. , Torczon, L. and Wolski, R. ( 2001). The GrADS project: software support for high-level grid application development. International Journal of High Performance Computing Applications 15(4): 327-344.

Boss, G. , Malladi, P. , Quan, D. , Legregni, L. and Hall, H. ( 2008). Cloud computing (White Paper), IBM , October 2007, http://download.boulder.ibm.com/ibmdl/pub/software/dw/wes/hipods/Cloud_computing_wp_final_8Oct.pdf, accessed on March 19, 2009.

Broberg, J. , Buyya, R. and Tari, Z. ( 2008). MetaCDN: Harnessing ‘storage clouds’ for high performance content delivery, Technical Report, GRIDS-TR-2008-10, Grid Computing and Distributed Systems Laboratory, the University of Melbourne, Australia, Aug. 15, 2008. http://www.gridbus.org/reports/meta-cdn2008.pdf, accessed on March 19, 2009.

Buyya, R. , Giddy, J. and Abramson, D. ( 2000). An evaluation of economy based resource trading and scheduling on computational power grids for parameter sweep applications. In Proceedings of the 2nd Workshop on Active Middleware Services (AMS 2000), August, pp. 1-10, Pittsburgh, USA.

Buyya, R. and Venugopal, S. ( 2004). The Gridbus toolkit for service oriented grid and utility computing: an overview and status report. In Proceedings of the 1st IEEE International Workshop on Grid Economics and Business Models (GECON 2004), April, pp. 19-36, Seoul, Korea.

Buyya, R. , Yeo, C.S. and Venugopal, S. ( 2008). Market-oriented cloud computing: vision, hype, and reality for delivering its services as computing utilities. In Proceedings of the 10th IEEE International Conference on High Performance Computing and Communications, September, pp. 5-13, Los Alamitos, CA , USA.

Chen, J. and Yang, Y. ( 2008). Activity completion duration based checkpoint selection for dynamic verification of temporal constraints in grid workflow systems . International Journal of High Performance Computing Applications 22(3): 319-329.

Fahringer, T. , Jugravu, A. , Pllana, S. , Prodan, R. , Slovis, Jr. C. and Truong, H.L. ( 2005). ASKALON: A tool set for cluster and grid computing. Concurrency and Computation: Practice and Experience 17: 143-169.

Grossman, R.L. and Gu, Y. ( 2008). Data mining using high performance data clouds: experimental studies using sector and sphere. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August, pp. 920-927, Las Vegas, Nevada, USA.

10.

Grossman R.L. , Gu Y. , Sabala M. and Zhang W. ( 2008). Compute and storage clouds using wide area high performance networks. Future Generation Computer Systems 25: 179-183.

11.

Liu, K. , Chen, J. , Yang, Y. and Jin, H. ( 2008). A throughput maximization strategy for scheduling instance intensive workflows on SwinDeW-G. Concurrency and Computation: Practice and Experience 20(15): 1807-1820.

12.

Maheswaran, M. , Ali, S. , Siegel, H.J. , Hensgen, D. and Freund, R.F. ( 1999). Dynamic mapping of a class of independent tasks onto heterogeneous computing systems, J. Parallel and Distributed Computing, 59(2): 107-131, 1999.

13.

Menasc, D.A. and Casalicchio, E. ( 2004). A framework for resource allocation in grid computing . In Proceedings of the 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS’04), pp. 259-267.

14.

Sakellariou, R. , Zhao, H. , Tsiakkouri, E. and Dikaiakos, M.D. ( 2005). Scheduling workflows with budget constraints, CoreGRID . In Proceedings of the Workshop on Integrated research in Grid Computing, November, pp. 347-357, Pisa, Italy.

15.

Sulistio, A. and Buyya, R. ( 2004). A grid simulation infrastructure supporting advance reservation . In Proceedings of the 16th International Conference on Parallel and Distributed Computing and Systems (PDCS 2004), November, pp. 1-7, Boston, USA.

16.

Tannenbaum, T. , Wright, D. , Miller, K. and Livny, M. ( 2002). Condor - a distributed job scheduler. In Computing with Linux. MIT Press.

17.

Vaquero, L.M. , Rodero-Merino, L. , Caceres, J. and Lindner, M. ( 2008). A Break in the clouds: towards a cloud definition. ACM SIGCOMM Computer Communication Review 39(1): 50-55.

18.

Yan, J. , Yang, Y. and Raikundalia, G.K. ( 2006). SwinDeW - A peer-to-peer based decentralized workflow management system. IEEE Transactions on Systems, Man and Cybernetics, Part A 36(5): 922-935.

19.

Yang, Y. , Liu, K. , Chen, J. , Lignier, J. and Jin, H. ( 2007). Peer-to-peer based grid workflow runtime environment of SwinDeWG. In Proceedings of the 3rd IEEE International Conference on e-Science and Grid Computing (e-Science07), December, pp. 51-58, Bangalore, India.

20.

Yang, Y. , Liu, K. , Chen, J. , Liu, X. , Yuan, D. and Jin, H. ( 2008). An algorithm in SwinDeW-C for scheduling transaction-intensive cost-constrained cloud workflows. In Proceedings of the 4th IEEE International Conference on e-Science and Grid Computing (e-Science08) , December, pp. 374-375, Indianapolis, USA.

21.

Yu, J. , Buyya, R. and Tham, C.K. ( 2005). A cost-based scheduling of scientific workflow applications on utility grids. In Proceedings of the 1st IEEE International Conference on e-Science and Grid Computing, December, pp. 140-147, Melbourne, Australia.

22.

Yu, J. and Buyya, R. ( 2006). Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms. Scientific Programming Journal 14(3-4): 217-230.

23.

Yu, J. and Buyya, R. ( 2007). Workflow scheduling algorithms for grid computing. Technical Report, GRIDS-TR-2007-10, Grid Computing and Distributed Systems Laboratory, the University of Melbourne, Australia, May 2007, http://gridbus.csse.unimelb.edu.au/reports/WorkflowSchedulingAlgs2007.pdf, accessed on March 19, 2009.