Dynamic DAG-Application Scheduling for Multi-Tier Edge Computing in Heterogeneous Networks

Xiang Li, Mustafa Abdallah, Yuan-Yao Lou, Mung Chiang, Kwang Taik Kim, Saurabh BagchiarXiv 2024 · DOI · arXiv

Abstract

Edge computing enhances latency-sensitive applications by processing data near the source. However, reliance on managed edge servers limits scalability and availability. This paper introduces Multi-Tier Edge Computing (M-TEC), a framework that incorporates volatile Personal Edge Devices (PEDs)—such as smartphones and laptops—alongside managed servers and the cloud. By utilizing a greedy scheduling algorithm for Directed Acyclic Graph (DAG) applications, M-TEC optimizes for latency, reliability, and cost. Evaluation on a physical testbed shows an 8% latency reduction and a 40% improvement in reliability over state-of-the-art baselines.

Introduction

Modern applications like augmented reality and autonomous systems require low-latency processing. While edge computing addresses this, current deployments often ignore the vast, idle computational power of Personal Edge Devices (PEDs). The primary obstacle to using PEDs is their inherent unreliability; devices may disconnect or suffer from performance fluctuations. Furthermore, complex applications are often structured as Directed Acyclic Graphs (DAGs), where tasks have strict dependencies, complicating the scheduling process.

Overview of the multi-tier edge computing architecture, illustrating the latency trade-offs between cloud, edge servers, and end-devices.

M-TEC addresses these challenges by creating a three-tier hierarchy: PEDs, Commercial Edge Devices (CEDs), and the Cloud. This structure allows for "sideways" offloading to nearby peers, which can be more efficient than traditional "upward" offloading to distant servers.

The M-TEC Framework

The M-TEC system orchestrates task execution through several key components designed to handle the heterogeneity of the network.

The M-TEC system architecture, detailing the DAG pre-processing stage and the iterative optimization logic within the Initiator.

Key Technical Innovations

  • DAG Pre-processing: Applications are decomposed into stages using a modified Breadth-First Search (BFS). This ensures that task dependencies are respected while maximizing parallel execution.
  • Joint Optimization: A greedy algorithm balances three primary objectives: minimizing latency, maximizing reliability, and minimizing operational costs.
  • Failure Prediction and Redundancy: The system maintains a history of device reliability. For critical tasks assigned to high-risk devices, M-TEC employs selective replication—executing the same task on multiple devices to mitigate potential failures.
  • Interference-Aware Latency Prediction: Using linear regression, M-TEC predicts performance degradation caused by co-location interference when multiple tasks run on a single device.
  • Dynamic Network Probing: Real-time transmission speeds are monitored through active probing. This is critical as data transmission can account for up to 60% of total latency in cellular networks; M-TEC’s inclusion of a transmission speed error parameter prevents over-optimistic scheduling.

Experimental Evaluation

The researchers evaluated M-TEC using a physical testbed rather than a simulation. The setup included 14 heterogeneous devices, including NVIDIA Jetson AGX Xavier and Up Squared AI Edge boards, connected via Ethernet, Wi-Fi, and a commercial CBRS 4G network.

Four distinct DAG-based applications were tested: MapReduce Sort, LightGBM, Video Analytics, and Matrix Operations. This real-world setup is a significant departure from the simulations common in this field.

Results and Discussion

M-TEC demonstrated significant improvements across all key metrics:

  • Latency: Achieved an 8% reduction in end-to-end latency compared to baselines like LAVEA and DCC.
  • Reliability: Reduced application failure probability by over 40% by accounting for device dropouts.
  • Resilience: Under high network traffic (500 Kbit/s background noise), M-TEC's performance remained stable with less than 10% degradation, whereas competing systems saw latency spikes exceeding 80%.
  • Cost: By prioritizing reliable personal devices, the framework reduces the need for expensive cloud or managed edge resources.

Limitations and Future Work

While effective, the current "Initiator" model may face scalability issues as the number of devices grows. Future research will explore K-means clustering to manage large device groups and "partial offloading" to subdivide heavy individual tasks. Additionally, future iterations will need to address the privacy and security implications of processing data on third-party personal devices.

Conclusion

M-TEC proves that personal edge devices can be reliably integrated into a cloud-edge continuum. By treating reliability as a manageable variable rather than a binary constraint, the framework unlocks significant computational resources, providing a robust solution for the next generation of latency-sensitive applications.

Summary updated

Abstract

Edge computing is deemed a promising technique to execute latency-sensitive applications by offloading computation-intensive tasks to edge servers. Extensive research has been conducted in the field of end-device to edge server task offloading for several goals, including latency minimization, energy optimization, and resource optimization. However, few of them consider our mobile computing devices (smartphones, tablets, and laptops) to be edge devices. In this paper, we propose a novel multi-tier edge computing framework, which we refer to as M-TEC, that aims to optimize latency, reduce the probability of failure, and optimize cost while accounting for the sporadic failure of personally owned devices and the changing network conditions. We conduct experiments with a real testbed and a real commercial CBRS 4G network, and the results indicate that M-TEC is capable of reducing the end-to-end latency of applications by at least 8\% compared to the best baseline under a variety of network conditions, while providing reliable performance at an affordable cost.
BibTeX
@misc{li2024dynamic,
  author = {Xiang Li and Mustafa Abdallah and Yuan-Yao Lou and Mung Chiang and Kwang Taik Kim and Saurabh Bagchi},
  title = {{Dynamic DAG-Application Scheduling for Multi-Tier Edge Computing in Heterogeneous Networks}},
  year = {2024},
  eprint = {2409.10839},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.10839},
}
Figure