nach oben

Cluster Computing

Erschienen in:

16.03.2020

Budget aware scheduling algorithm for workflow applications in IaaS clouds

verfasst von: K. Kalyan Chakravarthi, L. Shyamala, V. Vaidehi

Erschienen in: Cluster Computing | Ausgabe 4/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Cloud computing, a novel and promising model of Service-oriented computing, provides a pay-per-use framework to solve large-scale scientific and business workflow applications. Workflow scheduling in cloud is challenging due to dynamic nature of the cloud, particularly, on demand provisioning, elasticity, heterogeneous resource types, static & dynamic pricing models and virtualization. An example of workflow scheduling is mapping workflow tasks to cloud computing resources. Additionally, these workflow applications have a runtime constraint—the most typical being the cost of the computation and the time that computation requires to complete. Therefore, the focus is on two criteria: makespan and cost. This paper presents an algorithm called NBWS (Normalization based Budget constraint Workflow Scheduling) which generates a workflow schedule which minimizes the schedule length while satisfying the budget constraint. The algorithm undergoes a process of min–max normalization tailed by computing expect reasonable budget \( (erb) \) for dispatching the workflow tasks into one of the virtual machines. To minimize the execution time, NBWS algorithm maps the workflow tasks to resources which are having the earliest finish time within the allocated budget. The experimental results demonstrate that NBWS outperforms current state-of-the-art heuristics with respect to budget constraint and minimizing the makespan.

Vorheriger Artikel Bullfighting extreme scenarios in efficient hyper-scale cluster computing

Nächster Artikel An energy-efficient algorithm for virtual machine placement optimization in cloud data centers

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Patra, S.S.: Energy-efficient task consolidation for cloud data center. Int. J. Cloud Appl. Comput. 8(1), 117–142 (2018). https://doi.org/10.4018/ijcac.2018010106CrossRef

Lin, W., Xu, S., He, L., Li, J.: Multi-resource scheduling and power simulation for cloud computing. Inf. Sci. 397–398, 168–186 (2017)CrossRef

Lin, W., Xu, S., Li, J., Xu, L., Peng, Z.: Design and theoretical analysis of virtual machine placement algorithm based on peak workload characteristics. Soft. Comput. 21(5), 1301–1314 (2017). https://doi.org/10.1007/s00500-015-1862-7CrossRefMATH

Stergiou, C., Psannis, K.E., Kim, B., Gupta, B.: Secure integration of IoT and cloud computing. Futur. Gener. Comput. Syst. 78, 964–975 (2018). https://doi.org/10.1016/j.future.2016.11.031CrossRef

Wu, Z., Lin, W., Zhang, Z., Wen, A., Lin, L.: An ensemble random forest algorithm for insurance big data analysis. In: 2017 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC). (2017). https://doi.org/10.1109/cse-euc.2017.99

Wang, H., Wang, W., Cui, Z., Zhou, X., Zhao, J., Li, Y.: A new dynamic firefly algorithm for demand estimation of water resources. Inf. Sci. 438, 95–106 (2018). https://doi.org/10.1016/j.ins.2018.01.041MathSciNetCrossRef

Li, Y., Wang, G., Nie, L., Wang, Q., Tan, W.: Distance metric optimization driven convolutional neural network for age invariant face recognition. Pattern Recogn. 75, 51–62 (2018). https://doi.org/10.1016/j.patcog.2017.10.015CrossRef

Huang, Y., Li, W., Liang, Z., Xue, Y., Wang, X.: Efficient business process consolidation: combining topic features with structure matching. Soft. Comput. 22(2), 645–657 (2018). https://doi.org/10.1007/s00500-016-2364-yCrossRef

Hossain, M.S., Muhammad, G., Abdul, W., Song, B., Gupta, B.: Cloud-assisted secure video transmission and sharing framework for smart cities. Futur. Gener. Comput. Syst. 83, 596–606 (2018). https://doi.org/10.1016/j.future.2017.03.029CrossRef

10.

Wu, F., Wu, Q., Tan, Y.: Workflow scheduling in cloud: a survey. J. Supercomput. 71(9), 3373–3418 (2015). https://doi.org/10.1007/s11227-015-1438-4CrossRef

11.

Vecchiola, C., Pandey, S., Buyya, R.: High-performance cloud computing: a view of scientific applications. In: 2009 10th International Symposium on Pervasive Systems, Algorithms, and Networks. (2009). https://doi.org/10.1109/i-span.2009.150

12.

Evangelinos, C., Hill, C.: Cloud computing for parallel scientific HPC applications: feasibility of running coupled atmosphere-ocean climate models on Amazon’s EC2. In: The 1st Workshop on Cloud Computing and its Applications, pp. 2–34 (2008)

13.

Jackson, K.R., Ramakrishnan, L., Muriki, K., Canon, S., Cholia, S., Shalf, J., Wright, N.J.: Performance analysis of high-performance computing applications on the Amazon web services cloud. In: 2010 IEEE Second International Conference on Cloud Computing Technology and Science. (2010). https://doi.org/10.1109/cloudcom.2010.69

14.

Park, S.C., Ryoo, S.Y.: An empirical investigation of end-users’ switching toward cloud computing: a two factor theory perspective. Comput. Hum. Behav. 29(1), 160–170 (2013). https://doi.org/10.1016/j.chb.2012.07.032CrossRef

15.

Foster, I.T., Madduri, R.K.: Science as a service: how on demand computing can accelerate discovery. In: Proceedings of the 4th ACM Workshop on Scientific Cloud Computing - Science Cloud 13. (2013). https://doi.org/10.1145/2465848.2480345

16.

Khattar, N., Sidhu, J., Singh, J.: Toward energy-efficient cloud computing: a survey of dynamic power management and heuristics-based optimization techniques. J. Supercomput. 75(8), 4750–4810 (2019). https://doi.org/10.1007/s11227-019-02764-2CrossRef

17.

Abrishami, S., Naghibzadeh, M., Epema, D.H.: Deadline-constrained workflow scheduling algorithms for Infrastructure as a Service Clouds. Futur. Gener. Comput. Syst. 29(1), 158–169 (2013). https://doi.org/10.1016/j.future.2012.05.004CrossRef

18.

Ullman, J.: Np-complete scheduling problems. J. Comput. Syst. Sci. 10(3), 384–393 (1975)MathSciNetCrossRef

19.

Arabnejad, H., Barbosa, J.G., Suter, F.: Fair resource sharing for dynamic scheduling of workflows on heterogeneous systems. High-Perform. Comput. Complex Environ. (2014). https://doi.org/10.1002/9781118711897.ch9CrossRef

20.

Arabnejad, H., Barbosa, J.: Fairness resource sharing for dynamic workflow scheduling on heterogeneous systems. In: 2012 IEEE 10th International Symposium on Parallel and Distributed Processing with Applications. (2012). https://doi.org/10.1109/ispa.2012.94

21.

Tian, G., Xiao, C., Xu, Z., Xiao, X.: Hybrid scheduling strategy for multiple DAGs workflow in heterogeneous system. J. Softw. 23(10), 2720–2734 (2012). https://doi.org/10.3724/sp.j.1001.2012.04198CrossRef

22.

Hsu, C., Huang, K., Wang, F.: Online scheduling of workflow applications in grid environments. Future Generation Computer Systems 27(6), 860–870 (2011). https://doi.org/10.1016/j.future.2010.10.015CrossRef

23.

Yu, Z., Shi, W.: A planner-guided scheduling strategy for multiple workflow applications. In: 2008 International Conference on Parallel Processing—Workshops. (2008). https://doi.org/10.1109/icpp-w.2008.10

24.

Arabnejad, H., Barbosa, J.G.: Maximizing the completion rate of concurrent scientific applications under time and budget constraints. J. Comput. Sci. 23, 120–129 (2017). https://doi.org/10.1016/j.jocs.2016.10.013MathSciNetCrossRef

25.

. Arabnejad, H., Barbosa, J.G.: Budget constrained scheduling strategies for on-line workflow applications. In: Computational Science and Its Applications – ICCSA 2014 Lecture Notes in Computer Science, pp. 532–545. (2014). https://doi.org/10.1007/978-3-319-09153-2_40

26.

Chen, W., Deelman, E.: Workflow overhead analysis and optimizations. In: Proceedings of the 6th Workshop on Workflows in Support of Large-scale Science—WORKS 11. (2011). https://doi.org/10.1145/2110497.2110500

27.

Chen, W., Silva, R.F., Deelman, E., Sakellariou, R.: Using imbalance metrics to optimize task clustering in scientific workflow executions. Futur. Gener. Comput. Syst. 46, 69–84 (2015). https://doi.org/10.1016/j.future.2014.09.014CrossRef

28.

Verma, A., Kaushal, S.: Cost-time efficient scheduling plan for executing workflows in the cloud. J. Grid Comput. 13(4), 495–506 (2015). https://doi.org/10.1007/s10723-015-9344-9MathSciNetCrossRef

29.

Arabnejad, H., Barbosa, J.G., Prodan, R.: Low-time complexity budget–deadline constrained workflow scheduling on heterogeneous resources. Futur. Gener. Comput. Syst. 55, 29–40 (2016). https://doi.org/10.1016/j.future.2015.07.021CrossRef

30.

Malawski, M., Juve, G., Deelman, E., Nabrzyski, J.: Algorithms for cost- and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds. Futur. Gener. Comput. Syst. 48, 1–18 (2015). https://doi.org/10.1016/j.future.2015.01.004CrossRef

31.

Mao, M., Humphrey, M.: Auto-scaling to minimize cost and meet application deadlines in cloud workflows. In: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis on - SC 11, pp. 12–18. (2011). https://doi.org/10.1145/2063384.2063449

32.

Byun, E., Kee, Y., Kim, J., Maeng, S.: Cost optimized provisioning of elastic resources for application workflows. Futur. Gener. Comput. Syst. 27(8), 1011–1026 (2011). https://doi.org/10.1016/j.future.2011.05.001CrossRef

33.

Tang, Z., Liu, M., Ammar, A., Li, K., Li, K.: An optimized MapReduce workflow scheduling algorithm for heterogeneous computing. J. Supercomput. 72(6), 2059–2079 (2014). https://doi.org/10.1007/s11227-014-1335-2CrossRef

34.

Silva, R.F., Glatard, T., Desprez, F.: On-line, non-clairvoyant optimization of workflow activity granularity on grids. In: Euro-Par 2013 Parallel Processing Lecture Notes in Computer Science, pp. 255–266. (2013). https://doi.org/10.1007/978-3-642-40047-6_28

35.

Mao, M., Humphrey, M.: A performance study on the VM startup time in the cloud. In: 2012 IEEE Fifth International Conference on Cloud Computing. (2012). https://doi.org/10.1109/cloud.2012.103

36.

Calheiros, R.N., Buyya, R.: Meeting deadlines of scientific workflows in public clouds with tasks replication. IEEE Trans. Parallel Distrib. Syst. 25(7), 1787–1796 (2014). https://doi.org/10.1109/tpds.2013.238CrossRef

37.

Sakellariou, R., Zhao, H., Tsiakkouri, E., Dikaiakos, M.D.: Scheduling workflows with budget constraints. Integr. Res. GRID Comput. (2007). https://doi.org/10.1007/978-0-387-47658-2_14CrossRef

38.

Chard, K., Bubendorfer, K., Komisarczuk, P.: High occupancy resource allocation for grid and cloud systems, a study with DRIVE. In: Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing - HPDC 10. (2010). https://doi.org/10.1145/1851476.1851486

39.

Chard, R., Chard, K., Bubendorfer, K., Lacinski, L., Madduri, R., Foster, I.: Cost-aware cloud provisioning. In: 2015 IEEE 11th International Conference on E-Science. (2015). https://doi.org/10.1109/escience.2015.67

40.

Yu, J., Kirley, M., Buyya, R.: Multi-objective planning for workflow execution on Grids. In: 2007 8th IEEE/ACM International Conference on Grid Computing. (2007). https://doi.org/10.1109/grid.2007.4354110

41.

Arabnejad, H., Barbosa, J.G.: Multi-workflow QoS-constrained scheduling for utility computing. In: 2015 IEEE 18th International Conference on Computational Science and Engineering. (2015). https://doi.org/10.1109/cse.2015.29

42.

Ostermann, S., Iosup, A., Yigitbasi, N., Prodan, R., Fahringer, T., Epema, D.: A performance analysis of EC2 cloud computing services for scientific computing. In: Cloud Computing Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, pp. 115–131. (2010). https://doi.org/10.1007/978-3-642-12636-9_9

43.

Topcuoglu, H., Hariri, S., Wu, M.: Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst. 13(3), 260–274 (2002). https://doi.org/10.1109/71.993206CrossRef

44.

Arabnejad, H., Barbosa, J.G.: Multi-QoS constrained and Profit-aware scheduling approach for concurrent workflows on heterogeneous systems. Futur. Gener. Comput. Syst. 68, 211–221 (2017). https://doi.org/10.1016/j.future.2016.10.003CrossRef

45.

Xie, G., Liu, L., Yang, L., Li, R.: Scheduling trade-off of dynamic multiple parallel workflows on heterogeneous distributed computing systems. Concurr. Comput. (2016). https://doi.org/10.1002/cpe.3782CrossRef

46.

Rimal, B.P., Maier, M.: Workflow scheduling in multi-tenant cloud computing environments. IEEE Trans. Parallel Distrib. Syst. 28(1), 290–304 (2017). https://doi.org/10.1109/tpds.2016.2556668CrossRef

47.

Ghasemzadeh, M., Arabnejad, H., Barbosa, J.G.: Deadline-budget constrained scheduling algorithm for scientific workflows in a cloud environment. In: Proceedings of the 20th International Conference on Principles of Distributed Systems, vol. 70, pp. 19:1–19:16. (2017). https://doi.org/10.4230/lipics.opodis.2016.19

48.

Zhou, J., Wang, T., Cong, P., Lu, P., Wei, T., Chen, M.: Cost and makespan-aware workflow scheduling in hybrid clouds. J. Syst. Archit. 100, 101631 (2019). https://doi.org/10.1016/j.sysarc.2019.08.004CrossRef

49.

Zhou, N., Li, F., Xu, K., Qi, D.: Concurrent workflow budget- and deadline-constrained scheduling in heterogeneous distributed environments. Soft. Comput. 22(23), 7705–7718 (2018). https://doi.org/10.1007/s00500-018-3229-3CrossRef

50.

Wylie, A., Shi, W., Corriveau, J., Wang, Y.: A scheduling algorithm for hadoop mapreduce workflows with budget constraints in the heterogeneous cloud. In: 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). (2016). https://doi.org/10.1109/ipdpsw.2016.30

51.

Wu, C.Q., Cao, H: Optimizing the performance of big data workflows in multi-cloud environments under budget constraint. In: 2016 IEEE International Conference on Services Computing (SCC). (2016). https://doi.org/10.1109/scc.2016.25

52.

Wu, C.Q., Lin, X., Yu, D., Xu, W., Li, L.: End-to-end delay minimization for scientific workflows in clouds under budget constraint. IEEE Trans. Cloud Comput. 3(2), 169–181 (2015). https://doi.org/10.1109/tcc.2014.2358220CrossRef

53.

Su, S., Li, J., Huang, Q., Huang, X., Shuang, K., Wang, J.: Cost-efficient task scheduling for executing large programs in the cloud. Parallel Comput. 39(4–5), 177–188 (2013). https://doi.org/10.1016/j.parco.2013.03.002CrossRef

54.

Zheng, W., Sakellariou, R.: Budget-deadline constrained workflow planning for admission control. J. Grid Comput. 11(4), 633–651 (2013). https://doi.org/10.1007/s10723-013-9257-4CrossRef

55.

Li, J., Qiu, M., Ming, Z., Quan, G., Qin, X., Gu, Z.: Online optimization for scheduling preemptable tasks on IaaS cloud systems. J. Parallel Distrib. Comput. 72(5), 666–677 (2012). https://doi.org/10.1016/j.jpdc.2012.02.002CrossRef

56.

Panda, S.K., Jana, P.K.: Efficient task scheduling algorithms for heterogeneous multi-cloud environment. J. Supercomput. 71(4), 1505–1533 (2015). https://doi.org/10.1007/s11227-014-1376-6CrossRef

57.

Bochenina, K., Butakov, N., Boukhanovsky, A.: Static scheduling of multiple workflows with soft deadlines in non-dedicated heterogeneous environments. Futur. Gener. Comput. Syst. 55, 51–61 (2016). https://doi.org/10.1016/j.future.2015.08.009CrossRef

58.

Panda, S.K., Jana, P.K.: Normalization-based task scheduling algorithms for heterogeneous multi-cloud environment. Inf. Syst. Front. 20(2), 373–399 (2016). https://doi.org/10.1007/s10796-016-9683-5CrossRef

59.

Zhou, X., Zhang, G., Sun, J., Zhou, J., Wei, T., Hu, S.: Minimizing cost and makespan for workflow scheduling in cloud using fuzzy dominance sort based HEFT. Futur. Gener. Comput. Syst. 93, 278–289 (2019). https://doi.org/10.1016/j.future.2018.10.046CrossRef

60.

Chen, W., Xie, G., Li, R., Bai, Y., Fan, C., Li, K.: Efficient task scheduling for budget constrained parallel applications on heterogeneous cloud computing systems. Futur. Gener. Comput. Syst. 74, 1–11 (2017). https://doi.org/10.1016/j.future.2017.03.008CrossRef

61.

Han, J., Kamber, M., Pei, J.: Data Mining Concepts and Techniques. Morgan Kaufmann, Burlington (2011)MATH

62.

Calheiros, R.N., Ranjan, R., Beloglazov, A., Rose, C.A., Buyya, R.: CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Software 41(1), 23–50 (2010). https://doi.org/10.1002/spe.995CrossRef

63.

Palankar, M.R., Iamnitchi, A., Ripeanu, M., Garfinkel, S.: Amazon S3 for science grids. In: Proceedings of the 2008 International Workshop on Data-aware Distributed Computing—DADC 08. (2008) https://doi.org/10.1145/1383519.1383526

64.

Bharathi, S., Chervenak, A., Deelman, E., Mehta, G., Su, M., Vahi, K.: Characterization of scientific workflows. In: 2008 Third Workshop on Workflows in Support of Large-Scale Science. (2008). https://doi.org/10.1109/works.2008.4723958

65.

Juve, G., Chervenak, A., Deelman, E., Bharathi, S., Mehta, G., Vahi, K.: Characterizing and profiling scientific workflows. Futur. Gener. Comput. Syst. 29(3), 682–692 (2013). https://doi.org/10.1016/j.future.2012.08.015CrossRef

66.

Ghafouri, R., Movaghar, A., Mohsenzadeh, M.: A budget constrained scheduling algorithm for executing workflow application in infrastructure as a service clouds. Peer-to-Peer Netw. Appl. 12(1), 241–268 (2018). https://doi.org/10.1007/s12083-018-0662-0CrossRef

Titel: Budget aware scheduling algorithm for workflow applications in IaaS clouds
verfasst von: K. Kalyan Chakravarthi
L. Shyamala
V. Vaidehi
Publikationsdatum: 16.03.2020
Verlag: Springer US
Erschienen in: Cluster Computing / Ausgabe 4/2020
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-020-03095-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2020

Efficient VM migrations using forecasting techniques in cloud computing: a comprehensive review

Energy-efficient offloading of real-time tasks using cloud computing

Security aware index based quasi–identifier approach for privacy preservation of data sets for cloud applications

A density-based maximum margin machine classifier

Design and evaluation of a biologically-inspired cloud elasticity framework

A survey and classification of the workload forecasting methods in cloud computing

Premium Partner