Top

The Journal of Supercomputing

Published in:

22-10-2017

RePro-Active: a reactive–proactive scheduling method based on simulation in cloud computing

Authors: Noroddin Alaei, Faramarz Safi-Esfahani

Published in: The Journal of Supercomputing | Issue 2/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Cloud computing is a scalable computing infrastructure in which the number of resources and requests change dynamically. There are usually a huge number of tasks and resources in cloud computing. A scheduler does allocating resources to tasks, which is an operation with a large number of parameters that is of NP-hard problems. Approaches such as metaheuristic, simulation-based optimization (SBO), predictive algorithms, etc. are applied to mitigate the complexity of scheduling. Reactive scheduling methods are able to adapt their behavior based on a feedback loop from runtime environment, while proactive scheduling methods try to predict future events to adapt their behavior as well. These algorithms suffer from two problems: (1) they require additional information, like the execution time of tasks that are not usually available in practice and (2) they use the history of past activities that is not easy to maintain and process in order to make future decisions. To address the problems, this paper presents a reactive/proactive scheduling framework, dubbed RePro-Active that presents an iterative reactive/proactive scheduling algorithm called RePro-Active.SB runs periodically. It includes the algorithm called ReactiveScheduling to support reactive behavior, and the algorithms called ProactiveSSLB/ProactiveSSELB to reinforce proactive actions in which the algorithm called Simulate predicts future by simulating possible prospective events. First, the presented scheduling algorithms have the least dependence on prior knowledge about tasks. They are extracted from the category of round-robin methods that are more realistic and do not need extra information about the tasks that is not available in practice. Second, they also begin from current conditions (rather than relying on the history of data) and use SBO techniques that try to simulate possible prospective events to make better decisions. In order to realize the idea, RePro-Active is used to improve both task scheduling and load balancing in the cloud-computing environment. In comparison to the base methods, the results indicate that the completion time of tasks decreased by 30%, and average resource utilization ratio increased by 20%; while, throughput increased by 19%.

previous article Design and implementation of a Pedestrian recognition algorithm using trilinear interpolation based on HOG-UDP

next article Low-rank approximation of large-scale matrices via randomized methods

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Proactive simulation-based scheduling and load balancing.

Proactive simulation-based scheduling and enhanced load balancing.

First come first serve.

www.cloudbus.com.

Buyya R, Yeo CS, Venugopal S, Broberg J, Brandic I (2009) Cloud computing and emerging IT platforms: vision, hype, and reality for delivering computing as the 5th utility. Future Gener Comput Syst 25:599–616CrossRef

Calheiros RN, Ranjan R, Beloglazov A, De Rose CA, Buyya R (2011) CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Softw Pract Exp 41:3–50CrossRef

Casavant TL, Kuhl JG (1988) A taxonomy of scheduling in general-purpose distributed computing systems. IEEE Trans Softw Eng 14:141–154CrossRef

Arora M, Das SK, Biswas R (2002) A de-centralized scheduling and load balancing algorithm for heterogeneous grid environments. In: International Conference on Parallel Processing Workshops, Proceedings, pp 499–505

Tang Q, Gupta SK, Varsamopoulos G (2007) Thermal-aware task scheduling for data centers through minimizing heat recirculation. In: IEEE International Conference on Cluster Computing 2007:129–138

Van den Bossche R, Vanmechelen K, Broeckhove J (2013) Online cost-efficient scheduling of deadline-constrained workloads on hybrid clouds. Future Gener Comput Syst 29:973–985CrossRef

Pop F, Dobre C, Cristea V, Bessis N (2013) Scheduling of sporadic tasks with deadline constrains in cloud environments. In: IEEE 27th International Conference on Advanced Information Networking and Applications (AINA), 2013, pp 764–771

Zuo X, Zhang G, Tan W (2014) Self-adaptive learning PSO-based deadline constrained task scheduling for hybrid IaaS cloud. IEEE Trans Autom Sci Eng 11:564–573CrossRef

Donyadari E, Safi-Esfahani F, Nourafza N (2015) Scientific workflow scheduling based on deadline constraints in cloud environment. Int J Mechatron Electr Comput Technol (IJMEC) 5:1–15

10.

Motavaselalhagh F, Esfahani FS, Arabnia HR (2015) Knowledge-based adaptable scheduler for SaaS providers in cloud computing. Hum Centric Comput Inf Sci 5:16CrossRef

11.

Salimian L, Esfahani FS, Nadimi-Shahraki M-H (2016) An adaptive fuzzy threshold-based approach for energy and performance efficient consolidation of virtual machines. Computing 98:641–660MathSciNetCrossRef

12.

Haratian P, Safi-Esfahani F, Salimian L, Nabiollahi A (2017) An adaptive and fuzzy resource management approach in cloud computing. IEEE Trans Cloud Comput. doi:10.1109/TCC.2017.2735406

13.

Khorsand R, Safi-Esfahani F, Nematbakhsh N, Mohsenzade M (2017) ATSDS: adaptive two-stage deadline-constrained workflow scheduling considering run-time circumstances in cloud computing environments. J Supercomput 73:2430–2455CrossRef

14.

He X, Sun X, Von Laszewski G (2003) QoS guided min-min heuristic for grid task scheduling. J Comput Sci Technol 18:442–451CrossRefMATH

15.

Kamalam G, Muralibhaskaran V (2010) A new heuristic approach: Min-Mean algorithm for scheduling meta-tasks on heterogeneous computing systems. Int J Comput Sci Netw Secur 10:24–31

16.

Chauhan SS, Joshi R (2010) QoS guided heuristic algorithms for grid task scheduling. Int J Comput Appl 2:24–31

17.

Singh M, Suri P (2008) QPS Max-Min\(<>\) Min-Min: a QoS based predictive Max-Min, Min-Min switcher algorithm for job scheduling in a grid. Inf Technol J 7:1176–1181CrossRef

18.

Kokilavani T, Amalarethinam DDG (2011) Load balanced min-min algorithm for static meta-task scheduling in grid computing. Int J Comput Appl 20:43–49

19.

Zhong H, Tao K, Zhang X (2010) An approach to optimized resource scheduling algorithm for open-source cloud systems. In: Fifth Annual China Grid Conference 2010:124–129

20.

Patel G, Mehta R, Bhoi U (2015) Enhanced load balanced min-min algorithm for static meta task scheduling in cloud computing. Proc Comput Sci 57:545–553CrossRef

21.

Pandey S, Wu L, Guru SM, Buyya R (2010) A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments. In: 2010 24th IEEE International Conference on Advanced Information Networking and Applications, 2010, pp 400–407

22.

Lin C, Lu S (2011) Scheduling scientific workflows elastically for cloud computing. In: IEEE International Conference on Cloud Computing (CLOUD) 2011:746–747

23.

Sakellariou R, Zhao H (2004) A hybrid heuristic for DAG scheduling on heterogeneous systems. In: Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International, p 111

24.

Jayarani R, Sadhasivam S, Nagaveni N (2009) Design and implementation of an efficient two-level scheduler for cloud computing environment. In: International Conference on Advances in Recent Technologies in Communication and Computing, ARTCom’09. 2009, pp 884–886

25.

Calheiros RN, Ranjan R, De Rose CA, Buyya R (2009) Cloudsim: a novel framework for modeling and simulation of cloud computing infrastructures and services. arXiv preprint arXiv:0903.2525

26.

Singh J (2010) An algorithm to reduce the time complexity of earliest deadline first scheduling algorithm in real-time system. arXiv preprint arXiv:1101.0056

27.

Kuribayashi S (2011) Optimal joint multiple resource allocation method for cloud computing environments. arXiv preprint arXiv:1110.1730

28.

Avanes A, Freytag J-C (2008) Adaptive workflow scheduling under resource allocation constraints and network dynamics. Proc VLDB Endow 1:1631–1637CrossRef

29.

Menasce DA, Casalicchio E (2004) A framework for resource allocation in grid computing. In: MASCOTS, pp 259–267

30.

Borja S, Ruben M, Ignacio M (2009) An open source solution for virtual infrastructure management in private and hybrid clouds. IEEE Internet Comput 1:14–22

31.

Yu J, Buyya R (2006) Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms. Sci Program 14:217–230

32.

Chien NK, Son NH, Loc HD (2016) Load balancing algorithm based on estimating finish time of services in cloud computing. In: 2016 18th International Conference on Advanced Communication Technology (ICACT), pp 228–233

33.

Al Salami NM (2009) Ant colony optimization algorithm. UbiCC J 4:823–826

34.

Sakellariou R, Zhao H, Tsiakkouri E, Dikaiakos MD (2007) Scheduling workflows with budget constraints. In: Gorlatch S, Danelutto M (eds) Integrated research in GRID computing. Springer, Berlin, pp 189–202CrossRef

35.

Chen H, Wang F, Helian N, Akanmu G (2013) User-priority guided Min-Min scheduling algorithm for load balancing in cloud computing. In: National Conference on Parallel Computing Technologies (PARCOMPTECH) 2013:1–8

36.

Zhang F, Cao J, Tan W, Khan SU, Li K, Zomaya AY (2014) Evolutionary scheduling of dynamic multitasking workloads for big-data analytics in elastic cloud. IEEE Trans Emerg Topics Comput 2:338–351CrossRef

37.

Tsai SC, Fu SY (2014) Genetic-algorithm-based simulation optimization considering a single stochastic constraint. Eur J Oper Res 236:113–125MathSciNetCrossRefMATH

38.

Xhafa F, Abraham A (2010) Computational models and heuristic methods for Grid scheduling problems. Future Gener Comput Syst 26:608–621CrossRef

39.

El-Rewini H, Ali HH, Lewis T (1995) Task scheduling in multiprocessing systems. Computer 28:27–37CrossRef

40.

Amalarethinam DG, Muthulakshmi P (2011) An overview of the scheduling policies and algorithms in Grid Computing. Int J Res Rev Comput Sci 2:280–294

41.

Armstrong R, Hensgen D, Kidd T (1998) The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions. In: Seventh Heterogeneous Computing Workshop, 1998. (HCW 98) Proceedings, pp 79–87

42.

Singh A, Goyal P, Batra S (2010) An optimized round robin scheduling algorithm for CPU scheduling. Int J Comput Sci Eng 2:2383–2385

43.

Roy N, Dubey A, Gokhale A (2011) Efficient autoscaling in the cloud using predictive models for workload forecasting. In: IEEE International Conference on Cloud Computing (CLOUD) 2011:500–507

44.

Gong Z, Gu X, Wilkes J (2010) Press: Predictive elastic resource scaling for cloud systems. In: International Conference on Network and Service Management 2010:9–16

45.

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:1068–1077CrossRef

46.

Freund RF, Gherrity M, Ambrosius S, Campbell M, Halderman M, Hensgen D (1998) Scheduling resources in multi-user, heterogeneous, computing environments with SmartNet. In: Seventh Heterogeneous Computing Workshop (HCW 98), Proceedings 1998, pp 184–199

47.

Mohialdeen IA (2013) Comparative study of scheduling algorithms in cloud computing environment. J Comput Sci 9:252CrossRef

48.

Rasmussen RV, Trick MA (2008) Round robin scheduling-a survey. Eur J Oper Res 188:617–636MathSciNetCrossRefMATH

49.

Calheiros RN, Ranjan R, Buyya R (2011) Virtual machine provisioning based on analytical performance and QoS in cloud computing environments. In: International Conference on Parallel Processing 2011:295–304

50.

Elzeki O, Reshad M, Elsoud M (2012) Improved max-min algorithm in cloud computing. Int J Comput Appl 50:22–27

51.

Tanenbaum AS, Van Steen M (2007) Distributed systems. Prentice-Hall, Englewood CliffsMATH

52.

Lee LT, Liang CH, Chang HY, (2006) An adaptive task scheduling system for Grid Computing. In: The Sixth IEEE International Conference on Computer and Information Technology (CIT’06), pp 57–57

53.

Lim HC, Babu S, Chase JS, Parekh SS (2009) Automated control in cloud computing: challenges and opportunities. In: Proceedings of the 1st Workshop on Automated Control for Datacenters and Clouds, pp 13–18

54.

Marshall P, Keahey K, Freeman T (2010) Elastic site: using clouds to elastically extend site resources. In: Proceedings of the 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, pp 43–52

55.

Dawoud W, Takouna I, Meinel C (2011) Elastic vm for cloud resources provisioning optimization. In: International Conference on Advances in Computing and Communications, pp 431–445

56.

Meinel C, Dawoud W, Takouna I (2011) Elastic vm for dynamic virtualized resources provisioning and optimization

57.

Vasić N, Novaković D, Miučin S, Kostić D, Bianchini R (2012) Dejavu: accelerating resource allocation in virtualized environments. In: ACM SIGARCH Computer Architecture News, pp 423–436

58.

Shen Z, Subbiah S, Gu X, Wilkes J (2011) Cloudscale: elastic resource scaling for multi-tenant cloud systems. In: Proceedings of the 2nd ACM Symposium on Cloud Computing, p 5

59.

Sharma U, Shenoy P, Sahu S Shaikh A (2011) A cost-aware elasticity provisioning system for the cloud. In: 2011 31st International Conference on Distributed Computing Systems (ICDCS), pp 559–570

60.

Zhou L, Zhang L (2016) A dynamic task scheduling method based on simulation in cloud manufacturing. In: Asian Simulation Conference, pp 20–24

61.

Metropolis N, Ulam S (1949) The Monte Carlo method. J Am Stat Assoc 44:335–341CrossRefMATH

62.

Prajapati KD (2013) Comparison of virtual machine scheduling algorithms in cloud computing. Int J Comput Appl 83:12–14

Title: RePro-Active: a reactive–proactive scheduling method based on simulation in cloud computing
Authors: Noroddin Alaei
Faramarz Safi-Esfahani
Publication date: 22-10-2017
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 2/2018
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-017-2161-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 2/2018

A new clustering approach in wireless sensor networks using fuzzy system

Toward the design of a novel hybrid parallel N-body method in scope of modern cloud architectures

A deadlock-free routing algorithm for irregular 3D network-on-chips with wireless links

Large-scale simulation of a self-organizing self-management cloud computing framework

Dlog: diagnosing router events with syslogs for anomaly detection

A performance study of the time-varying cache behavior: a study on APEX, Mantevo, NAS, and PARSEC

Premium Partner