Dependency-Aware Task Reconfiguration and Offloading in Multi-Access Edge Cloud Networks
Chuan Feng, Pengchao Han, Xu Zhang, Qihan Zhang, Yejun Liu, Lei Guo
Abstract
Multi-access Edge Cloud (MEC) networks are powerful for providing emerging computation-intensive and latency-sensitive applications with low latency leveraging ubiquitous edge devices. These networks enable complex applications to be split into multiple components/subtasks and deployed among multiple edge servers with limited computation and communication resources. However, multiple subtasks within an application are dependent on each other. They cannot be executed in parallel, resulting in non-trivial resource waste when allocating resources to every subtask throughout the lifetime of the application. This paper investigates the multi-component task offloading problem in MEC networks that addresses the dependencies among components and three-dimensional (3D) resource allocation, i.e., computation, communication, and time slots. The problem is NP-hard and challenging to solve due to the complex task dependencies, including triangular dependencies among multiple subtasks and the routing of edges between dependent subtasks. To address the challenge, we first propose a non-destructive task reconfiguration algorithm that transforms a task call graph into multiple sequential layers, breaking out the triangular dependency. Then, we develop a de <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</b> endency-awa <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</b> e task offlo <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</b> ding algorithm w <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">I</b> th ta <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</b> k r <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</b> configuration ( <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">PRAISE</b> ) algorithm to maximize the total offloading benefit. <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">PRAISE</b> decouples the original problem into task offloading and 3D convex resource optimization. Simulation results show that <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">PRAISE</b> outperforms baselines with higher system benefits and lower resource costs.