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