Failure-resilient DAG task scheduling in edge computing

摘要

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.