DAG-based Task Orchestration for Edge Computing

Xiang Li, Mustafa Abdallah, Shikhar Suryavansh, Mung Chiang, Saurabh Bagchi

TL;DR

This paper introduces IBDASH, a novel framework for orchestrating complex, multi-stage applications on heterogeneous edge computing environments. IBDASH effectively combines personal (PEDs) and commercial (CEDs) devices to minimize both end-to-end latency and the probability of application failure, addressing key challenges in current edge computing.

What Problem Does This Paper Address?

The proliferation of personal computing devices like smartphones and laptops has created a vast pool of underutilized computational power. Edge computing aims to leverage this power by processing data closer to users, crucial for latency-sensitive applications such as augmented reality and video analytics. However, existing edge computing solutions often struggle with the inherent challenges posed by personal devices: their heterogeneity in capabilities, unpredictable availability, and the potential for interference between co-located applications. Integrating these "unmanaged" personal edge devices (PEDs) with traditional "commercial" edge devices (CEDs) into a cohesive and reliable system for complex applications, represented by Directed Acyclic Graphs (DAGs), remains a significant challenge.

Methods

IBDASH tackles this problem through a multi-faceted approach:

  • DAG-based Task Orchestration: It models applications as DAGs, explicitly handling task dependencies and enabling parallel execution of tasks within stages.
  • Heterogeneous Device Integration: IBDASH seamlessly integrates both commercial edge devices (CEDs) and personal edge devices (PEDs), leveraging the strengths of each.
  • Interference Modeling: A key innovation is the modeling of task interference. IBDASH characterizes how the execution time of a new task is affected by other tasks already running on an edge device. This is done by profiling linear interference coefficients (m and c values) for each pair of task types on each device.
  • Availability Prediction: The framework incorporates a model to predict the availability of PEDs, crucial for managing their sporadic nature.
  • Redundancy for Failure Mitigation: To combat the high probability of failure associated with PEDs, IBDASH employs task replication. If a task is assigned to a device with a high predicted failure rate, it can be replicated on another device to ensure successful execution.
  • Joint Optimization: IBDASH aims to jointly optimize for both end-to-end latency and probability of failure, using a weighted objective function that can be tuned by the user.

Datasets

The paper does not explicitly mention using pre-existing public datasets for training. Instead, it relies on:

  • Real-world device profiling: The authors collected data by profiling 7 AWS EC2 instances and a Macbook Pro to characterize their performance, interference patterns, and CPU usage.
  • Mobility trace data: Data from a previous study ([13]) on mobile device availability on a university campus was used to validate the device availability prediction model.
  • Simulated application instances: The evaluation was performed using a simulator that generated application instances based on four representative DAG applications.

Key Insights and Ideas

  • The Power of Unmanaged Devices: It's feasible and beneficial to incorporate personal, unmanaged devices (PEDs) into edge computing platforms, significantly expanding available resources.
  • Interference is Key: The performance of edge orchestration is heavily influenced by how tasks interfere with each other on a given device. Ignoring this can lead to suboptimal performance.
  • Proactive Failure Management is Essential: Unlike cloud environments, edge computing, especially with PEDs, requires proactive strategies like task replication to ensure reliability.
  • Joint Optimization is Necessary: Simply optimizing for latency or failure probability alone is insufficient. A balanced approach is needed to achieve robust and efficient edge applications.

Key Results

IBDASH demonstrated significant improvements over state-of-the-art baselines (LAVEA, Petrel, LaTS) and intuitive baselines (Random, Round Robin):

  • Latency Reduction: IBDASH achieved an average reduction of 14% in end-to-end latency compared to the best baseline.
  • Failure Probability Reduction: IBDASH achieved an average reduction of 41% in the probability of application failure.
  • Balanced Load Distribution: Visualizations show that IBDASH tends to distribute tasks more evenly across devices, avoiding the highly imbalanced loads seen in some other schemes (e.g., LaTS).
  • Effective Failure Mitigation: The framework's replication strategy effectively reduces failure probability, especially in scenarios with a high proportion of PEDs.

Limitations and Future Work

  • Orchestration Overhead: The current algorithm's per-task check against all available edge devices can incur high overhead, especially with many devices. The authors suggest edge device clustering as a solution.
  • Task Execution Latency Balancing: Long-latency tasks within a stage can delay subsequent stages. Future work could involve further task partitioning to balance these latencies.
  • Linear Interference Assumption: The assumption of linear interference might not hold for very high task loads, where non-linear effects like cache spillage could occur. Higher-order characterizations might be needed.
  • Availability Prediction Model: While validated with mobility data, the exponential availability prediction might not perfectly capture all real-world scenarios (e.g., fixed class schedules). Semi-Markov processes could offer more nuanced predictions.

Summary updated

Abstract

As we increase the number of personal computing devices that we carry (mobile devices, tablets, e-readers, and laptops) and these come equipped with increasing resources, there is a vast potential computation power that can be utilized from those devices. Edge computing promises to exploit these underlying computation resources closer to users to help run latency-sensitive applications such as augmented reality and video analytics. However, one key missing piece has been how to incorporate personally owned unmanaged devices into a usable edge computing system. The primary challenges arise due to the heterogeneity, lack of interference management, and unpredictable availability of such devices. In this paper we propose an orchestration framework IBDASH, which orchestrates application tasks on an edge system that comprises a mix of commercial and personal edge devices. IBDASH targets reducing both end-to-end latency of execution and probability of failure for applications that have dependency among tasks, captured by directed acyclic graphs (DAGs). IBDASH takes memory constraints of each edge device and network bandwidth into consideration. To assess the effectiveness of IBDASH, we run real application tasks on real edge devices with widely varying capabilities.We feed these measurements into a simulator that runs IBDASH at scale. Compared to three state-of-the-art edge orchestration schemes, LAVEA, Petrel, and LaTS, and two intuitive baselines, IBDASH reduces the end-to-end latency and probability of failure, by 14% and 41% on average respectively. The main takeaway from our work is that it is feasible to combine personal and commercial devices into a usable edge computing platform, one that delivers low latency and predictable and high availability.
BibTeX
@inproceedings{li2022dag,
  author = {Xiang Li and Mustafa Abdallah and Shikhar Suryavansh and Mung Chiang and Saurabh Bagchi},
  title = {{DAG-based Task Orchestration for Edge Computing}},
  booktitle = {SRDS},
  year = {2022},
}
Figure