Computer Science ›› 2021, Vol. 48 ›› Issue (10): 334-342.doi: 10.11896/jsjkx.210300304

• Interdiscipline & Frontier • Previous Articles     Next Articles

Failure-resilient DAG Task Rescheduling in Edge Computing

CAI Ling-feng1, WEI Xiang-lin2, XING Chang-you1, ZOU Xia1, ZHANG Guo-min1   

  1. 1 The Command & Control Engineering College,Army Engineering University,Nanjing 210007,China
    2 The 63rd Research Institute,National University of Defense Technology,Nanjing 210007,China
  • Received:2021-03-31 Revised:2021-04-28 Online:2021-10-15 Published:2021-10-18
  • About author:CAI Ling-feng,born in 1995,postgra-duate.His main research interests include edge computing,cyberspace security and machine learning.
    XING Chang-you,born in 1982,Ph.D,associate professor.His main research interests include software defined network,network measurement.

Abstract: By deploying computation and storage resources at the network edge that is close to the data source,and scheduling tasks offloaded by users efficiently,edge computing can greatly improve the quality of experience (QoE) of users.However,due to the lack of the reliable infrastructure support,the failure of edge servers or communication links could easily fail the edge computing service.To handle this problem,we establish the failure models of the computing nodes and communication links in edge computing,and then propose the rescheduling algorithm DaGTR (Dependency-aware Greedy Task Rescheduling) for the scheduling of dependent user tasks in resource failure scenarios.DaGTR includes two sub-algorithms,DaGTR-N and DaGTR-L,which are responsible for handling the node and link failure events respectively.DaGTR can sense the data dependency of tasks,and reschedule the tasks affected by failure events based on greedy method to ensure the successful execution of each task.Simulation results show that the algorithm can effectively avoid the task failure caused by failure events and improve the success rate of tasks in the case of resource failure.

Key words: Directed acyclic graph, Edge computing, Resource failure, Task scheduling

CLC Number: 

  • TP398.08
[1]China Internet Network Information Center.The 45th Statistical Report on the Development of Internet in China [R/OL].Beijing,CNNIC Report,2020.http://www.cac.gov.cn/2020-04/27/c_1589535470378587.htm.
[2]SATYANARAYANAN M.A Brief History of Cloud Offload:A Personal Journey from Odyssey Through Cyber Foraging to Cloudlets [J].ACM SIGMOBILE Mobile Computing and Communications Review,2015,18(4):19-23.
[3]WANG J,PAN J,ESPOSITO F,et al.Edge cloud offloading algorithms:Issues,methods,and perspectives[J].ACM Computing Surveys (CSUR),2019,52(1):1-23.
[4]LIANG J B,ZHANG H N,JIANG C,et al.Research Progress of Task Offloading Based on Deep Reinforcement Learning in Mobile Edge Computing[J].Computer Science,2021,48(7):316-323.
[5]LIU T,FANG L,GAO H H.Survey of Task Offloading in Edge Computing[J].Computer Science,2021,48(1):11-15.
[6]HU Y C,PATEL M,SABELLA D,et al.Mobile edge computing-a key technology towards 5G[J].ETSI White Paper,2015,11(11):1-16.
[7]LI H,LI X H,XIONG Q Y,et al.Edge Computing Enabling Industrial Internet:Architecture,Applications and Challenges[J].Computer Science,2021,48(1):1-10.
[8]BHATTCHARYA A,DE P.Computation offloading from mobile devices:can edge devices perform better than the cloud?[C]//Proceedings of the Third International Workshop on Adaptive Resource Management and Scheduling for Cloud Computing.2016:1-6.
[9]SHI W S,ZHANG X Z,WANG Y F,et al.Edge Computing:State-of-the-Art and Future Directions [J].Journal of Computer Research and Development,2019,56(1):69-89.
[10]COFFMAN E G.Computer and Job-shop Scheduling Theory[J].Oral Surgery Oral Medicine Oral Pathology,1976,5(2):143-149.
[11]LIU L,TAN H S,JIANG H C,et al.Dependent task placement and scheduling with function configuration in edge computing[C]//Proceedings of the International Symposium on Quality of Service.ACM,2019.
[12]HE K,MENG X,PAN Z,et al.A Novel Task-Duplication Based Clustering Algorithm for Heterogeneous Computing Environments[J].IEEE Transactions on Parallel and Distributed Systems,2018,30(1):2-14.
[13]QI Q,WANG J,MA Z,et al.Knowledge-driven Service Offloa-ding Decision for Vehicular Edge Computing:A Deep Reinforcement Learning Approach[J].IEEE Transactions on Vehicular Technology,2019,68(5):4192-4203.
[14]OO T,KO Y B.Application-aware Task Scheduling in Heterogeneous Edge Cloud[C]//International Conference on Information and Communication Technology Convergence (ICTC).IEEE,2019:1316-1320.
[15]LIU H,JIA H,CHEN J,et al.Computing Resource Allocation of Mobile Edge Computing Networks Based on Potential Game Theory[C]//IEEE 4th International Conference on Computer and Communications (ICCC).IEEE,2018.
[16]COLMAN-MEIXNER C,DEVELDER C,TORNATORE M,et al.A Survey on Resiliency Techniques in Cloud Computing Infrastructures and Applications [J].IEEE Communications Surveys & Tutorials,2017,18(3):2244-2281.
[17]MARTINS J,AHMED M,RAICIU C,et al.ClickOS and the art of network function virtualization[C]//Proceedings of the 11th USENIX Conference on Networked Systems Design and Implementation.USENIX Association,2014.
[18]MENG J Y,TAN H S,LI X Y,et al.Online Deadline-aware Task Dispatching and Scheduling in Edge Computing[J].IEEE Transactions on Parallel and Distributed Systems,2020,31(6):1270-1286.
[19]MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.OpenFlow[J].ACM SIGCOMM Computer Communication Review,2008,38(2):69.
[20]TALEB T,KSENTINI A,SERICOLA B.On Service Resilience in Cloud-native 5G Mobile Systems[J].IEEE Journal on Selec-ted Areas in Communications,2016,34(3):1-1.
[21]KANIZO Y,ROTTENSTREICH O,SEGALL I,et al.Optimizing Virtual Backup Allocation for Middleboxes[J].IEEE/ACM Transactions on Networking,2017,25(5):2759-2772.
[1] SUN Hui-ting, FAN Yan-fang, MA Meng-xiao, CHEN Ruo-yu, CAI Ying. Dynamic Pricing-based Vehicle Collaborative Computation Offloading Scheme in VEC [J]. Computer Science, 2022, 49(9): 242-248.
[2] YU Bin, LI Xue-hua, PAN Chun-yu, LI Na. Edge-Cloud Collaborative Resource Allocation Algorithm Based on Deep Reinforcement Learning [J]. Computer Science, 2022, 49(7): 248-253.
[3] LI Meng-fei, MAO Ying-chi, TU Zi-jian, WANG Xuan, XU Shu-fang. Server-reliability Task Offloading Strategy Based on Deep Deterministic Policy Gradient [J]. Computer Science, 2022, 49(7): 271-279.
[4] YUAN Hao-nan, WANG Rui-jin, ZHENG Bo-wen, WU Bang-yan. Design and Implementation of Cross-chain Trusted EMR Sharing System Based on Fabric [J]. Computer Science, 2022, 49(6A): 490-495.
[5] FANG Tao, YANG Yang, CHEN Jia-xin. Optimization of Offloading Decisions in D2D-assisted MEC Networks [J]. Computer Science, 2022, 49(6A): 601-605.
[6] LIU Zhang-hui, ZHENG Hong-qiang, ZHANG Jian-shan, CHEN Zhe-yi. Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems [J]. Computer Science, 2022, 49(6A): 619-627.
[7] XIE Wan-cheng, LI Bin, DAI Yue-yue. PPO Based Task Offloading Scheme in Aerial Reconfigurable Intelligent Surface-assisted Edge Computing [J]. Computer Science, 2022, 49(6): 3-11.
[8] SHEN Biao, SHEN Li-wei, LI Yi. Dynamic Task Scheduling Method for Space Crowdsourcing [J]. Computer Science, 2022, 49(2): 231-240.
[9] ZHANG Hai-bo, ZHANG Yi-feng, LIU Kai-jian. Task Offloading,Migration and Caching Strategy in Internet of Vehicles Based on NOMA-MEC [J]. Computer Science, 2022, 49(2): 304-311.
[10] LIN Chao-wei, LIN Bing, CHEN Xing. Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment [J]. Computer Science, 2022, 49(2): 312-320.
[11] TAN Shuang-jie, LIN Bao-jun, LIU Ying-chun, ZHAO Shuai. Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning [J]. Computer Science, 2022, 49(2): 336-341.
[12] LIANG Jun-bin, ZHANG Hai-han, JIANG Chan, WANG Tian-shu. Research Progress of Task Offloading Based on Deep Reinforcement Learning in Mobile Edge Computing [J]. Computer Science, 2021, 48(7): 316-323.
[13] XUE Yan-fen, GAO Ji-mei, FAN Gui-sheng, YU Hui-qun, XU Ya-jie. Energy-aware Fault-tolerant Collaborative Task Execution Algorithm in Edge Computing [J]. Computer Science, 2021, 48(6A): 374-382.
[14] SONG Hai-ning, JIAO Jian, LIU Yong. Research on Mobile Edge Computing in Expressway [J]. Computer Science, 2021, 48(6A): 383-386.
[15] WANG Zheng, JIANG Chun-mao. Cloud Task Scheduling Algorithm Based on Three-way Decisions [J]. Computer Science, 2021, 48(6A): 420-426.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!