I-BOT: Interference-Based Orchestration of Tasks for Dynamic Unmanaged Edge Computing

Shikhar Suryavansh, Chandan Bothra, Kwang Taik Kim, Mung Chiang, Chunyi Peng, Saurabh BagchiarXiv 2020 · arXiv

Abstract

Edge computing promises low latency by decentralizing computation, yet managed infrastructure remains costly and geographically limited. I-BOT (Interference-Based Orchestration of Tasks) addresses this by utilizing "unmanaged" edge devices (UEDs)—personal electronics like laptops and tablets. I-BOT overcomes the inherent challenges of UEDs—heterogeneity, high churn, and task interference—through linear interference modeling and predictive availability analysis. Experimental results indicate that I-BOT reduces application latency by over 60% compared to existing managed edge solutions while significantly improving bandwidth efficiency.

Introduction

The proliferation of powerful personal devices offers a vast, untapped resource for edge computing. However, transitioning from stable data centers to a "serverless" unmanaged edge environment introduces three primary hurdles: extreme performance heterogeneity across devices, high churn as users move or deactivate devices, and unpredictable task interference from co-located applications. Current orchestration schemes often fail in these dynamic settings because they rely on intrusive monitoring or assume resource stability.

System Architecture and Methods

I-BOT employs a centralized orchestrator to manage task distribution across available UEDs. The core innovation lies in its interference-aware scheduling.

The I-BOT system architecture facilitates task offloading, online readjustment, and device exit management.

Interference Modeling

Rather than monitoring raw hardware metrics, I-BOT profiles how tasks affect one another's execution time. The authors established that task interference is largely linear: the execution time of a task $T_i$ increases linearly with the number of concurrent tasks $T_j$. This is modeled as $f(k) = m \cdot k + c$, where $m$ represents the interference slope and $c$ the base execution time.

To handle the "cold start" problem for new devices, I-BOT uses Singular Value Decomposition (SVD) and Matrix Completion. By measuring a minimal set of task pairs, the system can accurately predict the full interference matrix for a new UED.

Availability and Feedback

I-BOT utilizes a semi-Markov Process (SMP) to analyze historical uptime, ensuring tasks are offloaded to devices likely to remain online. Furthermore, a dynamic feedback loop uses gradient descent to update performance models in real-time if a device owner initiates local heavy-duty applications, causing unexpected slowdowns.

Key Insights and Results

A critical finding of this work is that interference patterns are not only linear but also additive. When multiple types of tasks are co-located, the total slowdown is approximately the sum of their individual interference slopes.

Experimental data confirms that task interference on UEDs is both linear and additive, allowing for predictable scheduling.

Performance Benchmarks

In simulations of autonomous driving workloads, I-BOT demonstrated superior performance:

  • Latency Reduction: Average service time was reduced by 61% compared to LAVEA and 28% compared to Petrel.
  • Bandwidth Efficiency: By intelligently grouping tasks with shared input data, I-BOT achieved 56% lower bandwidth overhead than competing schemes.
  • Robustness to Churn: In scenarios with 10% device churn, I-BOT's performance degraded by only 7%, significantly outperforming baseline schemes which saw 25-31% increases in service time.

Conclusion

I-BOT provides a robust framework for harnessing unmanaged edge resources. By prioritizing external observation over intrusive monitoring and leveraging linear interference models, it achieves significant gains in latency and efficiency. Future work will explore higher-order modeling for saturated devices and the integration of formal incentive mechanisms to encourage user participation.

Summary updated

Abstract

In recent years, edge computing has become a popular choice for latency-sensitive applications like facial recognition and augmented reality because it is closer to the end users compared to the cloud. Although infrastructure providers are working toward creating managed edge networks, personal devices such as laptops and tablets, which are widely available and are underutilized, can also be used as potential edge devices. We call such devices Unmanaged Edge Devices (UEDs). Scheduling application tasks on such an unmanaged edge system is not straightforward because of three fundamental reasons-heterogeneity in the computational capacity of the UEDs, uncertainty in the availability of the UEDs (due to devices leaving the system), and interference among multiple tasks sharing a UED. In this paper, we present I-BOT, an interference-based orchestration scheme for latency-sensitive tasks on an Unmanaged Edge Platform (UEP). It minimizes the completion time of applications and is bandwidth efficient. I-BOT brings forth three innovations. First, it profiles and predicts the interference patterns of the tasks to make scheduling decisions. Second, it uses a feedback mechanism to adjust for changes in the computational capacity of the UEDs and a prediction mechanism to handle their sporadic exits. Third, it accounts for input dependence of tasks in its scheduling decision (such as, two tasks requiring the same input data). To evaluate I-BOT, we run end-to-end simulations with applications representing autonomous driving, composed of multiple tasks. We compare to two basic baselines (random and round-robin) and two state-of-the-arts, Lavea [SEC-2017] and Petrel [MSN-2018]. Compared to these baselines, I-BOT significantly reduces the average service time of application tasks. This reduction is more pronounced in dynamic heterogeneous environments, which would be the case in a UEP.
BibTeX
@misc{suryavansh2020i,
  author = {Shikhar Suryavansh and Chandan Bothra and Kwang Taik Kim and Mung Chiang and Chunyi Peng and Saurabh Bagchi},
  title = {{I-BOT: Interference-Based Orchestration of Tasks for Dynamic Unmanaged Edge Computing}},
  year = {2020},
  eprint = {2011.05925},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.05925},
}
Figure