Skip to main content
Erschienen in: The Journal of Supercomputing 2/2023

04.08.2022

A novel technique to optimize quality of service for directed acyclic graph (DAG) scheduling in cloud computing environment using heuristic approach

verfasst von: Ranjit Rajak, Shrawan Kumar, Shiv Prakash, Nidhi Rajak, Pratibha Dixit

Erschienen in: The Journal of Supercomputing | Ausgabe 2/2023

Einloggen

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

search-config
loading …

Abstract

At present, the cloud computing environment (CCE) has emerged as one of the significant technologies in communication, computing, and the Internet. It facilitates on-demand services of different types based on pay-per-use access such as platforms, applications and infrastructure. Because of its growing reputation, the massive requests need to be served in an efficient way which gives the researcher a challenging problem known as task scheduling. These requests are handled by method of efficient allocation of resources. In the process of resource allocation, task scheduling is accomplished where there is a dependency between tasks, which is a Directed Acyclic Graph (DAG) scheduling. DAG is one of the most important scheduling due to wide range of its applicable in different areas such as environmental technology, resources, and energy optimization. NP-complete is a renowned concern, so various models deals with NP-complete that have been suggested in the literature. However, as the Quality of Service (QoS)-aware services in the CCEplatform have turned into an attractive and prevalent way to provide computing resources emerges as a novel critical issue. Therefore, the key aim of this manuscript is to develop a novel DAG scheduling model for optimizing the QoS parameters in the CCEplatform and validation of this can be done with the help of extensive simulation technique. Each simulated result is compared with the existing results, and it is found that newly developed algorithm performs better in comparison to the state-of-the-art algorithms.

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

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!

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!

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!

Literatur
5.
Zurück zum Zitat Sharma S, Sajid M (2021) Integrated fog and cloud computing: issues and challenges. Int J Cloud Appl Comput (IGI) 11(4), Article 10 Sharma S, Sajid M (2021) Integrated fog and cloud computing: issues and challenges. Int J Cloud Appl Comput (IGI) 11(4), Article 10
6.
Zurück zum Zitat Buyya R, Pandey S, Vecchiola C (2009) Cloudbus toolkit for market-oriented cloud computing. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). pp 24–44 Buyya R, Pandey S, Vecchiola C (2009) Cloudbus toolkit for market-oriented cloud computing. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). pp 24–44
10.
Zurück zum Zitat Sahitya A (2021) Importance of Fog Computing in. Integr Cloud Comput with Internet Things Found Anal Appl, p 211 Sahitya A (2021) Importance of Fog Computing in. Integr Cloud Comput with Internet Things Found Anal Appl, p 211
11.
Zurück zum Zitat Song A, Chen W-N, Luo X-N, et al (2020) Scheduling Workflows with Composite Tasks: A Nested Particle Swarm Optimization Approach. IEEE Trans Serv Comput Song A, Chen W-N, Luo X-N, et al (2020) Scheduling Workflows with Composite Tasks: A Nested Particle Swarm Optimization Approach. IEEE Trans Serv Comput
12.
Zurück zum Zitat Jain R, Sharma N (2021) A QoS Aware Binary Salp Swarm Algorithm for Effective Task Scheduling in Cloud Computing. In: Progress in Advanced Computing and Intelligent Engineering. Springer, pp 462–473 Jain R, Sharma N (2021) A QoS Aware Binary Salp Swarm Algorithm for Effective Task Scheduling in Cloud Computing. In: Progress in Advanced Computing and Intelligent Engineering. Springer, pp 462–473
13.
Zurück zum Zitat Farid M, Latip R, Hussin M, Abdul Hamid NAW (2020) A survey on QoS requirements based on particle swarm optimization scheduling techniques for workflow scheduling in cloud computing. Symmetry (Basel) 12:551CrossRef Farid M, Latip R, Hussin M, Abdul Hamid NAW (2020) A survey on QoS requirements based on particle swarm optimization scheduling techniques for workflow scheduling in cloud computing. Symmetry (Basel) 12:551CrossRef
14.
Zurück zum Zitat da Silva EC, Gabriel PHR (2020) A Comprehensive Review of Evolutionary Algorithms for Multiprocessor DAG Scheduling. Computation 8:26CrossRef da Silva EC, Gabriel PHR (2020) A Comprehensive Review of Evolutionary Algorithms for Multiprocessor DAG Scheduling. Computation 8:26CrossRef
15.
Zurück zum Zitat Hosseinzadeh M, Ghafour MY, Hama HK, et al (2020) Multi-objective task and workflow scheduling approaches in cloud computing: a comprehensive review. J Grid Comput, pp 1–30 Hosseinzadeh M, Ghafour MY, Hama HK, et al (2020) Multi-objective task and workflow scheduling approaches in cloud computing: a comprehensive review. J Grid Comput, pp 1–30
16.
Zurück zum Zitat .Li J, Zhang X, Han L et al. (2021) OKCM: improving parallel task scheduling in high-performance computing systems using online learning. J Supercomput 77:5960–5983 .Li J, Zhang X, Han L et al. (2021) OKCM: improving parallel task scheduling in high-performance computing systems using online learning. J Supercomput 77:5960–5983
17.
Zurück zum Zitat Woeginger GJ (2003) Exact algorithms for NP-hard problems: A survey. In: Combinatorial optimization—eureka, you shrink! Springer, pp 185–207 Woeginger GJ (2003) Exact algorithms for NP-hard problems: A survey. In: Combinatorial optimization—eureka, you shrink! Springer, pp 185–207
18.
Zurück zum Zitat Hanen C (1994) Study of a NP-hard cyclic scheduling problem: The recurrent job-shop. Eur J Oper Res 72:82–101CrossRefMATH Hanen C (1994) Study of a NP-hard cyclic scheduling problem: The recurrent job-shop. Eur J Oper Res 72:82–101CrossRefMATH
19.
Zurück zum Zitat Tong Z, Chen H, Deng X et al (2020) A scheduling scheme in the cloud computing environment using deep Q-learning. Inf Sci (Ny) 512:1170–1191CrossRef Tong Z, Chen H, Deng X et al (2020) A scheduling scheme in the cloud computing environment using deep Q-learning. Inf Sci (Ny) 512:1170–1191CrossRef
21.
Zurück zum Zitat Pop F, Dobre C, Cristea V (2008) Performance analysis of grid DAG scheduling algorithms using MONARC simulation tool. In: 2008 International Symposium on Parallel and Distributed Computing, pp 131–138 Pop F, Dobre C, Cristea V (2008) Performance analysis of grid DAG scheduling algorithms using MONARC simulation tool. In: 2008 International Symposium on Parallel and Distributed Computing, pp 131–138
22.
Zurück zum Zitat Bozdag D, Ozguner F, Catalyurek UV (2008) Compaction of schedules and a two-stage approach for duplication-based DAG scheduling. IEEE Trans Parallel Distrib Syst 20:857–871CrossRef Bozdag D, Ozguner F, Catalyurek UV (2008) Compaction of schedules and a two-stage approach for duplication-based DAG scheduling. IEEE Trans Parallel Distrib Syst 20:857–871CrossRef
23.
Zurück zum Zitat Kannan R, Karpinski M (2005) Approximation algorithms for NP-hard problems. Oberwolfach Reports 1:1461–1540MathSciNetMATH Kannan R, Karpinski M (2005) Approximation algorithms for NP-hard problems. Oberwolfach Reports 1:1461–1540MathSciNetMATH
24.
Zurück zum Zitat Hochba DS (1997) Approximation algorithms for NP-hard problems. ACM SIGACT News 28:40–52CrossRef Hochba DS (1997) Approximation algorithms for NP-hard problems. ACM SIGACT News 28:40–52CrossRef
25.
Zurück zum Zitat Demirci G, Marincic I, Hoffmann H (2018) A divide and conquer algorithm for dag scheduling under power constraints. In: SC18: International Conference for High Performance Computing, Networking, Storage and Analysis, pp 466–477 Demirci G, Marincic I, Hoffmann H (2018) A divide and conquer algorithm for dag scheduling under power constraints. In: SC18: International Conference for High Performance Computing, Networking, Storage and Analysis, pp 466–477
26.
27.
Zurück zum Zitat Sulaiman M, Halim Z, Waqas M et al (2021) A hybrid list-based task scheduling scheme for heterogeneous computing. J Supercomput 77:10252–10288CrossRef Sulaiman M, Halim Z, Waqas M et al (2021) A hybrid list-based task scheduling scheme for heterogeneous computing. J Supercomput 77:10252–10288CrossRef
28.
Zurück zum Zitat Topcuoglu H, Hariri S, Wu M-Y (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans parallel Distrib Syst 13:260–274CrossRef Topcuoglu H, Hariri S, Wu M-Y (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans parallel Distrib Syst 13:260–274CrossRef
29.
Zurück zum Zitat Li J, Zhang X, Han L et al (2021) OKCM: improving parallel task scheduling in high-performance computing systems using online learning. J Supercomput 77:5960–5983CrossRef Li J, Zhang X, Han L et al (2021) OKCM: improving parallel task scheduling in high-performance computing systems using online learning. J Supercomput 77:5960–5983CrossRef
30.
Zurück zum Zitat Ramezani R (2021) Dynamic scheduling of task graphs in multi-FPGA systems using the critical path. J Supercomput 77:597–618CrossRef Ramezani R (2021) Dynamic scheduling of task graphs in multi-FPGA systems using the critical path. J Supercomput 77:597–618CrossRef
31.
Zurück zum Zitat Chowdhary SK, Rao ALN (2021) QoS Enhancement in Cloud-IoT Framework for Educational Institution with Task Allocation and Scheduling with Task-VM Matching Approach. Wireless PersCommun 121:267–286CrossRef Chowdhary SK, Rao ALN (2021) QoS Enhancement in Cloud-IoT Framework for Educational Institution with Task Allocation and Scheduling with Task-VM Matching Approach. Wireless PersCommun 121:267–286CrossRef
33.
Zurück zum Zitat 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 (Ny) 270:255–287MathSciNetCrossRefMATH 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 (Ny) 270:255–287MathSciNetCrossRefMATH
34.
Zurück zum Zitat Xu X-J, Xiao C-B, Tian G-Z, Sun T (2016) Hybrid scheduling deadline-constrained multi-DAGs based on reverse HEFT. In: 2016 International Conference on Information System and Artificial Intelligence (ISAI), pp 196–202 Xu X-J, Xiao C-B, Tian G-Z, Sun T (2016) Hybrid scheduling deadline-constrained multi-DAGs based on reverse HEFT. In: 2016 International Conference on Information System and Artificial Intelligence (ISAI), pp 196–202
35.
Zurück zum Zitat Samimi P, Teimouri Y, Mukhtar M (2016) A combinatorial double auction resource allocation model in cloud computing. Inf Sci (Ny) 357:201–216CrossRefMATH Samimi P, Teimouri Y, Mukhtar M (2016) A combinatorial double auction resource allocation model in cloud computing. Inf Sci (Ny) 357:201–216CrossRefMATH
36.
Zurück zum Zitat Rajak R, Shukla D, Alim A (2018) Modified critical path and top-level attributes (MCPTL)-based task scheduling algorithm in parallel computing. In: Soft Computing: Theories and Applications. Springer, pp 1–13 Rajak R, Shukla D, Alim A (2018) Modified critical path and top-level attributes (MCPTL)-based task scheduling algorithm in parallel computing. In: Soft Computing: Theories and Applications. Springer, pp 1–13
37.
Zurück zum Zitat Rajak R (2018) Deterministic task scheduling method in multiprocessor environment. In: International Conference on Advances in Computing and Data Sciences, pp 331–341 Rajak R (2018) Deterministic task scheduling method in multiprocessor environment. In: International Conference on Advances in Computing and Data Sciences, pp 331–341
38.
Zurück zum Zitat Rajak N, Shukla D, (2019) Performance analysis of workflow scheduling algorithm in cloud computing environment using priority attribute. Int J Adv Sci Technol Australia 28(16):1810 – 1831 Rajak N, Shukla D, (2019) Performance analysis of workflow scheduling algorithm in cloud computing environment using priority attribute. Int J Adv Sci Technol Australia 28(16):1810 – 1831
39.
Zurück zum Zitat Braun TD, Siegel HJ, Beck N et al (2001) A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J Parallel Distrib Comput 61:810–837CrossRef Braun TD, Siegel HJ, Beck N et al (2001) A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J Parallel Distrib Comput 61:810–837CrossRef
40.
Zurück zum Zitat Pop F, Dobre C, Cristea V (2009) Genetic algorithm for DAG scheduling in grid environments. In: 2009 IEEE 5th International Conference on Intelligent Computer Communication and Processing, pp 299–305 Pop F, Dobre C, Cristea V (2009) Genetic algorithm for DAG scheduling in grid environments. In: 2009 IEEE 5th International Conference on Intelligent Computer Communication and Processing, pp 299–305
41.
Zurück zum Zitat Canon L-C, Jeannot E (2009) Evaluation and optimization of the robustness of dag schedules in heterogeneous environments. IEEE Trans Parallel Distrib Syst 21:532–546CrossRef Canon L-C, Jeannot E (2009) Evaluation and optimization of the robustness of dag schedules in heterogeneous environments. IEEE Trans Parallel Distrib Syst 21:532–546CrossRef
42.
Zurück zum Zitat Raza Abbas Haidri (2020) ChittaranjanPadmanabhKatti, Prem Chandra Saxena, Cost effective deadline aware scheduling strategy for workflow applications on virtual machines in cloud computing. J King Saud Univ Comput Inf Sci 32(6):666–683 Raza Abbas Haidri (2020) ChittaranjanPadmanabhKatti, Prem Chandra Saxena, Cost effective deadline aware scheduling strategy for workflow applications on virtual machines in cloud computing. J King Saud Univ Comput Inf Sci 32(6):666–683
43.
Zurück zum Zitat Darbha S, Aggarwal DP (1994) SDBS: A task duplication based optimal scheduling algorithm. In Proceedings of IEEE scalable high performance computing conference, Knoxville, TN, pp 756_61. Darbha S, Aggarwal DP (1994) SDBS: A task duplication based optimal scheduling algorithm. In Proceedings of IEEE scalable high performance computing conference, Knoxville, TN, pp 756_61.
44.
Zurück zum Zitat Sinnen O Task scheduling for parallel systems. Wiley-Interscience Publication (2007) Sinnen O Task scheduling for parallel systems. Wiley-Interscience Publication (2007)
45.
Zurück zum Zitat Kumar MS, Gupta I (2017) Jana PK Delay-based workflow scheduling for cost optimization in heterogeneous cloud system. In: 2017 Tenth International Conference on Contemporary Computing (IC3), Noida, pp. 1–6 Kumar MS, Gupta I (2017) Jana PK Delay-based workflow scheduling for cost optimization in heterogeneous cloud system. In: 2017 Tenth International Conference on Contemporary Computing (IC3), Noida, pp. 1–6
46.
Zurück zum Zitat Gupta I, Kumar MS, Jana PK (2018) Efficient workflow scheduling algorithm for cloud computing system: a dynamic priority-based approach. Arab J Sci Eng 43(12):7945–7960CrossRef Gupta I, Kumar MS, Jana PK (2018) Efficient workflow scheduling algorithm for cloud computing system: a dynamic priority-based approach. Arab J Sci Eng 43(12):7945–7960CrossRef
47.
Zurück zum Zitat Hwang K (2005) Advanced computer architecture: parallelism,scalability, programmability, 5th reprint. New Delhi:TMH Publishing Company, pp 51_104 Hwang K (2005) Advanced computer architecture: parallelism,scalability, programmability, 5th reprint. New Delhi:TMH Publishing Company, pp 51_104
48.
Zurück zum Zitat Akbar MF, Munir EU, Rafique M M, Malik, Khan SU, Yang LT (2016)zs List-Based Task Scheduling for Cloud Computing. In: IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical And Social Computing (CPSCom) and IEEE Smart Data (SmartData), Chengdu, pp 652–659 Akbar MF, Munir EU, Rafique M M, Malik, Khan SU, Yang LT (2016)zs List-Based Task Scheduling for Cloud Computing. In: IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical And Social Computing (CPSCom) and IEEE Smart Data (SmartData), Chengdu, pp 652–659
49.
Zurück zum Zitat Kalra M, Singh S (2015) A review of metaheuristic scheduling techniques in cloud computing. Egypt informatics J 16:275–295CrossRef Kalra M, Singh S (2015) A review of metaheuristic scheduling techniques in cloud computing. Egypt informatics J 16:275–295CrossRef
50.
Zurück zum Zitat Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms. MIT press Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms. MIT press
Metadaten
Titel
A novel technique to optimize quality of service for directed acyclic graph (DAG) scheduling in cloud computing environment using heuristic approach
verfasst von
Ranjit Rajak
Shrawan Kumar
Shiv Prakash
Nidhi Rajak
Pratibha Dixit
Publikationsdatum
04.08.2022
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 2/2023
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-022-04729-4

Weitere Artikel der Ausgabe 2/2023

The Journal of Supercomputing 2/2023 Zur Ausgabe

Premium Partner