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

DGCQN: a RL and GCN combined method for DAG scheduling in edge computing

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

Abstract

Edge computing is an emerging paradigm that enables low-latency and high-performance computing at the network edge. However, effectively scheduling complex and interdependent tasks on heterogeneous and dynamic edge computing nodes presents a significant challenge in meeting users' real-time response requirements. To solve this problem, a DGCQN scheduling network that leverages reinforcement learning and graph convolutional neural networks to learn an optimal scheduling strategy is proposed in this paper. The proposed method embeds the graph structure of Directed Acyclic Graph (DAG) tasks and node information of Kubernetes (K8s) clusters into a Q value function, guiding the DQN network in selecting the best action at each step. The method is evaluated across various DAG tasks and edge computing scenarios. Compared with HEFT, DQN, and GOSU, the task completion time of the proposed method is reduced by about 20, 10, and 1.5%, respectively. The results demonstrate the effectiveness of the proposed method.

Graphic abstract

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
Algorithm 1
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Availability of data and materials

The dataset analyzed during the current study is available on GitHub. https://github.com/wfcommons/pegasus-instances.

References

  1. Shi W, Cao J, Zhang Q et al (2016) Edge computing: vision and challenges. IEEE Internet Things J 3(5):637–646. https://doi.org/10.1109/JIOT.2016.2579198

    Article  Google Scholar 

  2. Sufyan F, Banerjee A (2023) Computation offloading for smart devices in fog-cloud queuing system. IETE J Res 69(3):1509–1521. https://doi.org/10.1080/03772063.2020.1870876

    Article  Google Scholar 

  3. Sufyan F, Banerjee A (2020) Computation offloading for distributed mobile edge computing network: a multiobjective approach. IEEE Access 8:149915–149930. https://doi.org/10.1109/ACCESS.2020.3016046

    Article  Google Scholar 

  4. Chishti MS, Sufyan F, Banerjee A (2021) Decentralized on-chain data access via smart contracts in Ethereum blockchain. IEEE Trans Netw Serv Manage 19(1):174–187. https://doi.org/10.1109/TNSM.2021.3120912

    Article  Google Scholar 

  5. Sufyan F, Banerjee A (2019) Comparative analysis of network libraries for offloading efficiency in mobile cloud environment. Int J Adv Comput Sci Appl, 10(2)

  6. Chiang YH, Zhang T, Ji Y (2019) Joint cotask-aware offloading and scheduling in mobile edge computing systems. IEEE Access 7:105008–105018. https://doi.org/10.1109/ACCESS.2019.2931336

    Article  Google Scholar 

  7. Li C, Tang J, Tang H et al (2019) Collaborative cache allocation and task scheduling for data-intensive applications in edge computing environment. Futur Gener Comput Syst 95:249–264. https://doi.org/10.1016/j.future.2019.01.007

    Article  Google Scholar 

  8. Khan PW, Abbas K, Shaiba H et al (2020) Energy efficient computation offloading mechanism in multi-server mobile edge computing—an integer linear optimization approach. Electronics 9(6):1010. https://doi.org/10.3390/electronics9061010

    Article  Google Scholar 

  9. Qu Y, Dai H, Wang H et al (2021) Service provisioning for UAV-enabled mobile edge computing. IEEE J Sel Areas Commun 39(11):3287–3305. https://doi.org/10.1109/JSAC.2021.3088660

    Article  Google Scholar 

  10. Xiuguo Z, Yufei L, Zhiying C et al (2021) An efficient service migration model based on improved genetic algorithm in mobile edge computing environment. 革新的コンピューティング・情報・制御に関する国際誌 17(04):1401

  11. Sheng S, Chen P, Chen Z et al (2021) Deep reinforcement learning-based task scheduling in iot edge computing. Sensors 21(5):1666. https://doi.org/10.3390/s21051666

    Article  MathSciNet  Google Scholar 

  12. Jie Y, Tang X, Choo KKR et al (2018) Online task scheduling for edge computing based on repeated Stackelberg game. J Parall Distribut Comput 122:159–172. https://doi.org/10.1016/j.jpdc.2018.07.019

    Article  Google Scholar 

  13. Gezer V, Wagner A (2021) Real-time edge framework (RTEF): task scheduling and realisation. J Intell Manuf 2021:1–17. https://doi.org/10.1007/s10845-021-01760-9

    Article  Google Scholar 

  14. Cai L, Wei X, Xing C et al (2021) Failure-resilient DAG task scheduling in edge computing. Comput Netw 198:108361. https://doi.org/10.1016/j.comnet.2021.108361

    Article  Google Scholar 

  15. Zhan W, Luo C, Wang J et al (2020) Deep-reinforcement-learning-based offloading scheduling for vehicular edge computing. IEEE Internet Things J 7(6):5449–5465. https://doi.org/10.1109/JIOT.2020.2978830

    Article  Google Scholar 

  16. Zhu A, Wen Y (2021) Computing offloading strategy using improved genetic algorithm in mobile edge computing system. J Grid Comput 19(3):38. https://doi.org/10.1007/s10723-021-09578-8

    Article  MathSciNet  Google Scholar 

  17. Zhang Y, Wang Y, Tang X et al (2018) Energy-efficient task scheduling on heterogeneous computing systems by linear programming. Concurrency Comput Pract Exp 30(19):e4731. https://doi.org/10.1002/cpe.4731

    Article  Google Scholar 

  18. Leng L, Li J, Shi H et al (2021) Graph convolutional network-based reinforcement learning for tasks offloading in multi-access edge computing. Multimedia Tools Appl 80(19):29163–29175. https://doi.org/10.1007/s11042-021-11130-5

    Article  Google Scholar 

  19. Tang Z, Jia W, Zhou X et al (2020) Representation and reinforcement learning for task scheduling in edge computing. IEEE Trans Big Data 8(3):795–808. https://doi.org/10.1109/TBDATA.2020.2990558

    Article  Google Scholar 

  20. Lee H, Cho S, Jang Y et al (2021) A global DAG task scheduler using deep reinforcement learning and graph convolution network. IEEE Access 9:158548–158561.https://doi.org/10.1109/ACCESS.2021.3130407

  21. Jing X, Yao X, Liu M et al (2024) Multi-agent reinforcement learning based on graph convolutional network for flexible job shop scheduling. J Intell Manuf 35(1):75–93. https://doi.org/10.1007/s10845-022-02037-5

    Article  Google Scholar 

  22. Lin Z, Li C, Tian L et al (2022) A scheduling algorithm based on reinforcement learning for heterogeneous environments. Appl Soft Comput 130:109707. https://doi.org/10.1016/j.asoc.2022.109707

    Article  Google Scholar 

  23. Song Y, Li C, Tian L et al (2023) A reinforcement learning based job scheduling algorithm for heterogeneous computing environment. Comput Electr Eng 107:108653. https://doi.org/10.1016/j.compeleceng.2023.108653

    Article  Google Scholar 

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

  25. Muddinagiri R, Ambavane S, Bayas S (2019) Self-hosted Kubernetes: deploying Docker containers locally with Minikube. In: 2019 IEEE International Conference on Innovative Trends and Advances in Engineering and Technology (ICITAET): 239–243.https://doi.org/10.1109/ICITAET47105.2019.9170208

  26. Kubernetes (2022) Production-Grade Container Orchestration. Available online: https://kubernetes.io/ (accessed on 15 July 2022)

  27. Mondal SK, Pan R, Kabir HMD et al (2022) Kubernetes in IT administration and serverless computing: an empirical study and research challenges. J Supercomput 2022:1–51. https://doi.org/10.1007/s11227-021-03982-3

    Article  Google Scholar 

  28. Khalil E, Dai H, Zhang Y et al. (2017) Learning combinatorial optimization algorithms over graphs. Adv Neural Inf Process Syst, 30.

Download references

Funding

Financial support was provided in part by the National Natural Science Foundation of China (62373142,62033014), Natural Science Foundation of Hunan Province (2021JJ50006, 2022JJ50074), and Hunan Engineering Research Center of Electric Drive and Regenerative Energy Storage and Utilization.

Author information

Authors and Affiliations

  1. School of Electrical and Information Engineering, Hunan University of Technology, Zhuzhou, 412007, Hunan, China

    Bin Qin & Xin Wang

  2. College of Railway Transportation, Hunan University of Technology, Zhuzhou, 412007, Hunan, China

    Qinyang Lei

Authors
  1. Bin Qin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qinyang Lei
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xin Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

BQ contributed to conceptualization, software, data curation, and writing—original draft preparation. QL contributed to software, data curation, and writing—original draft. XW contributed to conceptualization, writing—review and editing, and obtaining research funding.

Corresponding author

Correspondence to Xin Wang.

Ethics declarations

Conflict of interest

The authors have no financial or proprietary interests in any material discussed in this article. The authors declare no competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Qin, B., Lei, Q. & Wang, X. DGCQN: a RL and GCN combined method for DAG scheduling in edge computing. J Supercomput 80, 18464–18491 (2024). https://doi.org/10.1007/s11227-024-06140-7

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-024-06140-7

Keywords

Search

Navigation