Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Real-time workflows oriented online scheduling in uncertain cloud environment

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Workflow scheduling has become one of the hottest topics in cloud environments, and efficient scheduling approaches show promising ways to maximize the profit of cloud providers via minimizing their cost, while guaranteeing the QoS for users’ applications. However, existing scheduling approaches are inadequate for dynamic workflows with uncertain task execution times running in cloud environments, because those approaches assume that cloud computing environments are deterministic and pre-computed schedule decisions will be statically followed during schedule execution. To cover the above issue, we introduce an uncertainty-aware scheduling architecture to mitigate the impact of uncertain factors on the workflow scheduling quality. Based on this architecture, we present a scheduling algorithm, incorporating both event-driven and periodic rolling strategies (EDPRS), for scheduling dynamic workflows. Lastly, we conduct extensive experiments to compare EDPRS with two typical baseline algorithms using real-world workflow traces. The experimental results show that EDPRS performs better than those algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Armbrust M, Fox A, Griffith R, Joseph AD, Katz R, Konwinski A, Lee G, Patterson D, Rabkin A, Stoica I et al (2010) A view of cloud computing. Commun ACM 53(4):50–58

    Article  Google Scholar 

  2. Mell P, Grance T (2011) The nist definition of cloud computing (draft). NIST Spec Publ 800:145

    Google Scholar 

  3. Chen H, Zhu X, Qiu D, Liu L (2016) Uncertainty-aware real-time workflow scheduling in the cloud. In: Proceeding of the 9th International Conference on Cloud Computing, IEEE, pp 577–584

  4. Zhu X, Wang J, Guo H, Zhu D, Yang LT, Liu L (2016) Fault-tolerant scheduling for real-time scientific workflows with elastic resource provisioning in virtualized clouds. IEEE Trans Parallel Distrib Syst 27(12):3501–3517

    Article  Google Scholar 

  5. Zeng L, Veeravalli B, Li X (2015) Saba: a security-aware and budget-aware workflow scheduling strategy in clouds. J Parallel Distrib Comput 75:141–151

    Article  Google Scholar 

  6. Chen H, Liu G, Yin S, Liu X, Qiu D (2017) Erect: energy-efficient reactive scheduling for real-time tasks in heterogeneous virtualized clouds. J Comput Sci. doi:10.1016/j.jocs.2017.03.017

    Google Scholar 

  7. Chen H, Zhu X, Qiu D, Liu L, Du Z (2017) Scheduling for workflows with security-sensitive intermediate data by selective tasks duplication in clouds. IEEE Trans Parallel Distrib Syst. doi:10.1109/TPDS.2017.2678507

    Google Scholar 

  8. Hamid F, Radu P, Thomas F (2013) A truthful dynamic workflow scheduling mechanism for commercial multicloud environments. IEEE Trans Parallel Distrib Syst 24(6):1203–1213

    Article  Google Scholar 

  9. Lee YC, Zomaya AY (2013) Stretch out and compact: workflow scheduling with resource abundance. In: Proceedings of the 2013 International Symposium on Cluster Cloud and the Grid (CCGRID), IEEE, pp 367–381

  10. Zhang Q, Zhani MF, Boutaba R, Hellerstein JL (2013) Harmony: dynamic heterogeneity-aware resource provisioning in the cloud. In: IEEE 33rd International Conference on Distributed Computing Systems (ICDCS), IEEE, pp 510–519

  11. Gideon J, Ann C, Ewa D, Shishir B, Gaurang M, Karan V (2013) Characterizing and profiling scientific workflows. Futur Gener Comput Syst 29:682–692

    Article  Google Scholar 

  12. Tang X, Li K, Liao G, Fang K, Wu F (2011) A stochastic scheduling algorithm for precedence constrained tasks on grid. Futur Gener Comput Syst 27(8):1083–1091

    Article  Google Scholar 

  13. Qiu M, Sha EH-M (2009) Cost minimization while satisfying hard/soft timing constraints for heterogeneous embedded systems. ACM Trans Des Autom Electron Syst (TODAES) 14(2):25

    Google Scholar 

  14. Kong X, Lin C, Jiang Y, Yan W, Chu X (2011) Efficient dynamic task scheduling in virtualized data centers with fuzzy prediction. J Netw Comput Appl 34(4):1068–1077

    Article  Google Scholar 

  15. Chen H, Zhu X, Guo H, Zhu J, Qin X, Wu J (2015) Towards energy-efficient scheduling for real-time tasks under uncertain cloud computing environment. J Syst Softw 99:20–35

    Article  Google Scholar 

  16. Poola D, Garg SK, Buyya R, Yang Y, Ramamohanarao K (2014) Robust scheduling of scientific workflows with deadline and budget constraints in clouds. In: IEEE 28th International Conference on Advanced Information Networking and Applications (AINA), IEEE, pp 858–865

  17. Dejun J, Pierre G, Chi C-H (2010) EC2 performance analysis for resource provisioning of service-oriented applications. In: ICSOC/ServiceWave 2009 Workshops Service-Oriented Computing, Springer, pp 197–207

  18. Xu Y, Li K, Hu J, Li K (2014) A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf Sci 270:255–287

    Article  MATH  MathSciNet  Google Scholar 

  19. Jing C, Zhu Y, Li M (2013) Energy-efficient scheduling on multi-FPGA reconfigurable systems. Microprocess Microsyst 37(6):590–600

    Article  Google Scholar 

  20. Durillo JJ, Nae V, Prodan R (2014) Multi-objective energy-efficient workflow scheduling using list-based heuristics. Futur Gener Comput Syst 36:221–236

    Article  Google Scholar 

  21. Mei J, Li K, Hu J, Yin S, Sha EH-M (2013) Energy-aware preemptive scheduling algorithm for sporadic tasks on DVS platform. Microprocess Microsyst 37(1):99–112

    Article  Google Scholar 

  22. Abrishami S, Naghibzadeh M, Epema D (2012) Cost-driven scheduling of grid workflows using partial critical paths. IEEE Trans Parallel Distrib Syst 23(8):1400–1414

    Article  Google Scholar 

  23. Zhang F, Cao J, Li K, Khan SU, Hwang K (2014) Multi-objective scheduling of many tasks in cloud platforms. Futur Gener Comput Syst 37:309–320

    Article  Google Scholar 

  24. Li K, Tang X, Li K (2014) Energy-efficient stochastic task scheduling on heterogeneous computing systems. IEEE Trans Parallel Distrib Syst 25(11):2867–2876

    Article  Google Scholar 

  25. Scharbrodt M, Schickinger T, Steger A (2006) A new average case analysis for completion time scheduling. J ACM 53(1):121–146

    Article  MATH  MathSciNet  Google Scholar 

  26. Megow N, Uetz M, Vredeveld T (2006) Models and algorithms for stochastic online scheduling. Math Oper Res 31(3):513–525

    Article  MATH  MathSciNet  Google Scholar 

  27. Van de Vonder S, Demeulemeester E, Herroelen W (2008) Proactive heuristic procedures for robust project scheduling: an experimental analysis. Eur J Oper Res 189(3):723–733

    Article  MATH  Google Scholar 

  28. Rodriguez Sossa M, Buyya R (2014) Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds. IEEE Trans Cloud Comput 2(2):222–235

    Article  Google Scholar 

  29. Calheiros R N, Ranjan R, Beloglazov A, De Rose C A, Buyya R (2011) Cloudsim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Softw Pract Exp 41(1):23–50

    Article  Google Scholar 

  30. Amazon Web Service, http://aws.amazon.com/autoscaling

  31. Mao M, Humphrey M (2013) Scaling and scheduling to maximize application performance within budget constraints in cloud workflows. In: IEEE 27th International Symposium on Parallel and Distributed Processing (IPDPS), IEEE, pp 67–78

  32. Abrishami S, Naghibzadeh M, Epema DH (2013) Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds. Futur Gener Comput Syst 29(1):158–169

    Article  Google Scholar 

  33. Abrishami S, Naghibzadeh M, Epema DH (2012) Cost-driven scheduling of grid workflows using partial critical paths. IEEE Trans Parallel Distrib Syst 23(8):1400–1414

    Article  Google Scholar 

  34. https://confluence.pegasus.isi.edu/display/pegasus/WorkflowGenerator

  35. Chen H, Wu G, Huo L, Qi Y (2017) Objective space division based adaptive multiobjective optimization algorithm. J Softw. doi:10.13328/j.cnki.jos.005278

Download references

Author information

Authors and Affiliations

  1. Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha, 410073, People’s Republic of China

    Huangke Chen, Jianghan Zhu, Zhenshi Zhang & Manhao Ma

  2. State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, 430079, People’s Republic of China

    Xin Shen

Authors
  1. Huangke Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jianghan Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhenshi Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Manhao Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Xin Shen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Huangke Chen.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chen, H., Zhu, J., Zhang, Z. et al. Real-time workflows oriented online scheduling in uncertain cloud environment. J Supercomput 73, 4906–4922 (2017). https://doi.org/10.1007/s11227-017-2060-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-017-2060-4

Keywords

Search

Navigation