research-article

Failure-resilient DAG task scheduling in edge computing

Authors:

Xiulei WangAuthors Info & Claims

Volume 198, Issue C

https://doi.org/10.1016/j.comnet.2021.108361

Published: 24 October 2021 Publication History

Abstract

Through placing computation, storage, and communications facilities near the data source, Edge Computing (EC) is anticipated to extend the intelligence from the central cloud to the network edge. The Quality of Experience (QoE) of user and energy efficiency of mobile device could be significantly improved through offloading their computation-intensive tasks to the network edge. With the increasing popularity of intelligent devices, tasks offloaded to the edge are becoming more complex, consisting of multiple sub-tasks with data dependency, which are typically modeled as a Directed Acyclic Graph (DAG). The scheduling of DAG tasks is more complex, which has been proved to be NP-hard. Traditional DAG scheduling algorithms developed in non-edge computing scenarios could not be directly applied due to their neglect of: (1) the competition of communication resources; and (2) the rescheduling requirement in case of edge server failure in dynamic edge network environment. In this backdrop, this paper presents a failure-resilient DAG task scheduling algorithm to minimize the response delay experienced by the tasks. After formulating the DAG task scheduling problem, a context-aware greedy task scheduling (CaGTS) algorithm is proposed. Then, to cope with the failure event of edge server, a dependency-aware task rescheduling (DaTR) algorithm is designed. To evaluate the performance of the proposed algorithms, extensive experiments have been conducted on a simulator developed using Python. Experimental results with diverse parameter settings have shown that CaGTS could reduce at least 10.47% average completion time than benchmarks, and DaTR can effectively avoid task scheduling interruption caused by server failure events.

References

[1]

Shi W., Jie C., Quan Z., Li Y., Xu L., Edge computing: Vision and challenges, IEEE Internet Things J. 3 (5) (2016) 637–646.

[2]

H. Tan, Z. Han, X.Y. Li, F.C.M. and Lau, Online job dispatching and scheduling in edge-clouds, in: IEEE INFOCOM 2017 - IEEE Conference on Computer Communications, 2017, pp. 1–9.

[3]

Xu Z., Liang W., Xu W., Jia M., Guo S., Efficient algorithms for capacitated cloudlet placements, IEEE Trans. Parallel Distrib. Syst. 27 (10) (2016) 2866–2880.

[4]

Meng J., Tan H., Li X.-Y., Han Z., Li B., Online deadline-aware task dispatching and scheduling in edge computing, IEEE Trans. Parallel Distrib. Syst. 31 (6) (2020) 1270–1286,.

Digital Library

[5]

C. Shi, K. Habak, P. Pandurangan, M. Ammar, M. Naik, E. Zegura, Cosmos: Computation offloading as a service for mobile devices, in: Proceedings of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2014, pp. 287–296.

[6]

B.-G. Chun, S. Ihm, P. Maniatis, M. Naik, A. Patti, Clonecloud: Elastic execution between mobile device and cloud, in: Proceedings of the Sixth Conference on Computer Systems, 2011, pp. 301–314.

[7]

Y. Zhang, J. Yan, X. Fu, Reservation-based resource scheduling and code partition in mobile cloud computing, in: international Conference on Computer Communications, 2016, pp. 962–967.

[8]

Hartmann S., Briskorn D., A survey of variants and extensions of the resource-constrained project scheduling problem, European J. Oper. Res. 207 (1) (2010) 1–14.

[9]

Coffman E.G., Computer and job-shop scheduling theory, Oral Surg. Oral Med. Oral Pathol. 5 (2) (1976) 143–149.

[10]

Adhikari M., Srirama S.N., Amgoth T., Application offloading strategy for hierarchical fog environment through swarm optimization, IEEE Internet Things J. 7 (5) (2019) 4317–4328.

[11]

T. Oo, Y. Ko, Application-aware task scheduling in heterogeneous edge cloud, in: International Conference on Information and Communication Technology Convergence, 2019.

[12]

Kwok Y.K., Ahmad I., Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors, IEEE Trans. Parallel Distrib. Syst. 7 (5) (1996) 506–521.

Digital Library

[13]

Wu M.Y., Gajski D.D., Hypertool: A programming aid for message-passing systems, IEEE Trans. Parallel Distrib. Syst. 1 (3) (1990) 330–343.

Digital Library

[14]

Sih G.C., Lee E.A., A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures, IEEE Trans. Parallel Distrib. Syst. 4 (2) (1993) 175–187.

Digital Library

[15]

Arabnejad H., Barbosa J.G., List scheduling algorithm for heterogeneous systems by an optimistic cost table, IEEE Trans. Parallel Distrib. Syst. 25 (3) (2014) 682–694.

Digital Library

[16]

Topcuoglu H., Hariri S., Wu M.Y., Performance-effective and low-complexity task scheduling for heterogeneous computing, IEEE Trans. Parallel Distrib. Syst. (2002).

[17]

Liu Y., Wang S., Zhao Q., Du S., Yang F., Dependency-aware task scheduling in vehicular edge computing, IEEE Internet Things J. PP (99) (2020) 1.

[18]

M. Wang, T. Ma, T. Wu, C. Chang, F. Yang, H. Wang, Dependency-aware dynamic task scheduling in mobile-edge computing, in: 16th International Conference on Mobility, Sensing and Networking, 2020, pp. 785–790.

[19]

L. Liu, H. Tan, H.C. Jiang, Z. Han, H. Huang, Dependent task placement and scheduling with function configuration in edge computing, in: The International Symposium, 2019.

[20]

He K., Meng X., Pan Z., Yuan L., Zhou P., A novel task-duplication based clustering algorithm for heterogeneous computing environments, IEEE Trans. Parallel Distrib. Syst. (2018).

[21]

Yu W., Najafi A., Huang Y., Garcia-Ortiz A., Combination of task allocation and approximate computing for fog architecture based IoT, IEEE Internet Things J. PP (99) (2020).

[22]

Guo S., Liu J., Yang Y., Xiao B., Li Z., Energy-efficient dynamic computation offloading and cooperative task scheduling in mobile cloud computing, IEEE Trans. Mob. Comput. (2018) 1.

[23]

Lee J., Ko H., Kim J., Pack S., DATA: Dependency-aware task allocation scheme in distributed edge clouds, IEEE Trans. Ind. Inf. PP (99) (2020) 1.

[24]

Shu C., Zhao Z., Han Y., Min G., Duan H., Multi-user offloading for edge computing networks: A dependency-aware and latency-optimal approach, IEEE Internet Things J. 7 (3) (2019) 1678–1689.

[25]

X. Fu, B. Tang, F. Guo, L. Kang, Priority and dependency-based DAG tasks offloading in fog/edge collaborative environment, in: 24th International Conference on Computer Supported Cooperative Work in Design, CSCWD, 2021, pp. 440–445.

[26]

Song F., Xing H., Luo S., Zhan D., Dai P., Qu R., A multiobjective computation offloading algorithm for mobile-edge computing, IEEE Internet Things J. 7 (9) (2020) 8780–8799.

[27]

Zhang Y., Zhou Z., Shi Z., Meng L., Zhang Z., Online scheduling optimization for dag-based requests through reinforcement learning in collaboration edge networks, IEEE Access PP (99) (2020) 1.

[28]

Qi Q., et al., Knowledge-driven service offloading decision for vehicular edge computing: A deep reinforcement learning approach, IEEE Trans. Veh. Technol. PP (5) (2019) 1.

[29]

Soualhia M., Khomh F., Tahar S., A dynamic and failure-aware task scheduling framework for hadoop, IEEE Trans. Cloud Comput. PP (99) (2018) 1.

[30]

Y. Harchol, A. Mushtaq, J. Mccauley, A. Panda, S. Shenker, CESSNA: Resilient edge-computing, in: SIGCOMM Workshop, 2018.

[31]

Wei X., Liu J., Wang Y., Tang C., Hu Y., Wireless edge caching based on content similarity in dynamic environments, J. Syst. Archit. (ISSN ) 115 (102000) (2021),.

Digital Library

[32]

Jeong S., Simeone O., Kang J., Mobile edge computing via a UAV-mounted cloudlet: Optimization of bit allocation and path planning, IEEE Trans. Veh. Technol. (2017).

[33]

McKeown S., et al., OpenFlow, ACM SIGCOMM Comput. Commun. Rev. 38 (2) (2008) 69.

[34]

Taleb T., Ksentini A., Sericola B., On service resilience in cloud-native 5G mobile systems, IEEE J. Sel. Areas Commun. 34 (3) (2016) 483–496,.

Digital Library

[35]

Kanizo Y., Rottenstreich O., Segall I., Yallouz J., Optimizing virtual backup allocation for middleboxes, IEEE/ACM Trans. Netw. (2017) 2759–2772.

[36]

Shin K.S., Cha M.J., MunSuckJang I., Jung J.H., Yoon W.O., Choi S.B., Task scheduling algorithm using minimized duplications in homogeneous systems, J. Parallel Distrib. Comput. 68 (8) (2008) 1146–1156.

Cited By

Qin BLei QWang X(2024)DGCQN: a RL and GCN combined method for DAG scheduling in edge computingThe Journal of Supercomputing10.1007/s11227-024-06140-780:13(18464-18491)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11227-024-06140-7
Li K(2024)Energy-Constrained DAG Scheduling on Edge and Cloud Servers with Overlapped Communication and ComputationJournal of Grid Computing10.1007/s10723-024-09775-122:3Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1007/s10723-024-09775-1
Khademi Dehnavi MBroumandnia AHosseini Shirvani MAhanian I(2024)A hybrid genetic-based task scheduling algorithm for cost-efficient workflow execution in heterogeneous cloud computing environmentCluster Computing10.1007/s10586-024-04468-627:8(10833-10858)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1007/s10586-024-04468-6
Show More Cited By

Index Terms

Failure-resilient DAG task scheduling in edge computing
1. Theory of computation
  1. Theory and algorithms for application domains

Index terms have been assigned to the content through auto-classification.

Recommendations

Dependent task placement and scheduling with function configuration in edge computing
IWQoS '19: Proceedings of the International Symposium on Quality of Service

In Mobile Edge Computing (MEC), each edge server can be configured with only a small number of functions due to the limited capacity of various resources. Meanwhile, mobile applications become more complicated, consisting of multiple dependent tasks ...
A Task Duplication Based Scheduling Algorithm for Heterogeneous Systems
IPDPS '00: Proceedings of the 14th International Symposium on Parallel and Distributed Processing

Optimal scheduling of tasks of a directed acyclic graph (DAG) onto a set of processors is a strong NP-hard problem. In this paper, we present a scheduling scheme called TDS to schedule tasks of a DAG onto a heterogeneous system. This models a network of ...
Scalable scheduling for symmetric multiprocessors (SMP)

We present a task duplication-based scalable scheduling algorithm for Symmetric Multiprocessors (SMP), called S3MP (Scalable Scheduling for SMP), to address the problem of task scheduling. The algorithm pre-allocates network communication resources so ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computer Networks: The International Journal of Computer and Telecommunications Networking

Computer Networks: The International Journal of Computer and Telecommunications Networking Volume 198, Issue C

Oct 2021

471 pages

ISSN:1389-1286

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 24 October 2021

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Qin BLei QWang X(2024)DGCQN: a RL and GCN combined method for DAG scheduling in edge computingThe Journal of Supercomputing10.1007/s11227-024-06140-780:13(18464-18491)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11227-024-06140-7
Li K(2024)Energy-Constrained DAG Scheduling on Edge and Cloud Servers with Overlapped Communication and ComputationJournal of Grid Computing10.1007/s10723-024-09775-122:3Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1007/s10723-024-09775-1
Khademi Dehnavi MBroumandnia AHosseini Shirvani MAhanian I(2024)A hybrid genetic-based task scheduling algorithm for cost-efficient workflow execution in heterogeneous cloud computing environmentCluster Computing10.1007/s10586-024-04468-627:8(10833-10858)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1007/s10586-024-04468-6
Luan FWang SYagati SKim SLien KOng IHong TCho SLiang EStoica ISchulzrinne HKohler EMaltz DMisra V(2023)Exoshuffle: An Extensible Shuffle ArchitectureProceedings of the ACM SIGCOMM 2023 Conference10.1145/3603269.3604848(564-577)Online publication date: 10-Sep-2023
https://dl.acm.org/doi/10.1145/3603269.3604848
Hao YWang QMa TDu JCao J(2023)Energy allocation and task scheduling in edge devices based on forecast solar energy with meteorological informationJournal of Parallel and Distributed Computing10.1016/j.jpdc.2023.03.005177:C(171-181)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.jpdc.2023.03.005
Goudarzi MPalaniswami MBuyya R(2022)Scheduling IoT Applications in Edge and Fog Computing Environments: A Taxonomy and Future DirectionsACM Computing Surveys10.1145/354483655:7(1-41)Online publication date: 22-Jun-2022
https://dl.acm.org/doi/10.1145/3544836

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents