OnDisc: Optimizing Latency-Sensitive Jobs in the Edge-Cloud Wilds

TL;DR

In the world of Edge Computing, minimizing Response Time is the holy grail. OnDisc is a groundbreaking online algorithm that handles job dispatching (where to send it) and scheduling (when to run it) without needing to predict the future. It accounts for upload/download delays and proves that we can achieve near-optimal performance even when jobs arrive in a completely chaotic, arbitrary order.

Background: The Stochastic Fallacy

Most existing edge-cloud solutions are built on the "Stochastic" assumption—they assume job arrivals follow a predictable pattern (like a Poisson process). However, real-world user behavior is rarely that polite. When traffic spikes or follows unusual patterns, these models break.

The authors of OnDisc shift the focus to Online Competitiveness. This means they compare the algorithm's performance against an all-knowing "Offline Optimal" scheduler. Their goal? Ensure that even in the worst-case scenario, the algorithm performs within a constant factor of the best possible theoretical outcome.

Problem & Motivation

The challenge in edge-cloud systems is three-fold:

1. Heterogeneity: Edge servers and remote clouds have different processing powers.
2. Unrelated Machine Speeds: A job might be fast on Server A but slow on Server B due to architecture differences, not just clock speed.
3. Communication Latency: Unlike local clusters, moving data to/from the edge involves varying upload (${\Delta }^{\uparrow }$) and download (${\Delta }^{\downarrow }$) delays.

Previous classical theories (like those by Garg and Kumar) showed that without "Speed Augmentation" (giving the online algorithm a slight speed boost), a bounded competitive ratio is impossible. OnDisc tackles this head-on.

Methodology: The OnDisc Engine

OnDisc operates on two core principles:

1. The Scheduling Policy: Highest Residual Density First (HRDF)

Each server calculates the "Residual Density" of its jobs: $d_j(t)=\frac{w_{kj}}{{\hat{p}}_{kj}^{rem}(t)}$ Where $w$ is the weight (priority) and ${\hat{p}}^{rem}$ is the remaining time. By picking the job with the highest density, the server ensures that high-priority, near-completion tasks finish first, minimizing the overall "weighted" waiting time.

2. The Dispatching Policy: Predictive Greedy

When a job is released, the mobile device simulates its arrival at every possible server. It calculates $Q_{kj}(t)$, which is the projected increase in total system WRT:

• Type-I Influence: How long the new job must wait for existing high-density tasks.
• Self-Latency: The job’s own processing and transmission time.
• Type-II Influence: How much the new job will delay existing lower-density tasks.

Figure 1: Typical Edge-Cloud System architecture with mobile devices, edge servers, and remote cloud.

Performance & Experiments

The researchers tested OnDisc against "Nearest" (sending jobs to the closest server) and "Selfish" (jobs only care about their own completion time).

SOTA Comparison

Using Google cluster traces, the results were definitive. OnDisc consistently outperformed heuristics across different workloads. When the system was stressed with 5000+ jobs, the average WRT for OnDisc remained significantly lower than FCFS (First-Come-First-Serve) or Fair (WRR) models.

Figure 2: Average WRT vs. Number of Jobs. Note how OnDisc (O) maintains a lower curve compared to Nearest (N) and Selfish (S) as workload increases.

The Fairness Knob

A unique contribution is the Fairness Knob ($f$). Pure efficiency often leads to "starvation" (small, low-priority jobs never getting processed). By setting $f\in [0,1]$, administrators can trade a tiny bit of total performance to ensure every job gets at least some CPU time, achieving a balance between global optimization and individual fairness.

Critical Insight & Conclusion

OnDisc is a "Scalable" algorithm. In theoretical terms, its competitive ratio ($O(1/ϵ)$) does not grow with the number of servers or jobs. This makes it a robust candidate for massive-scale IoT and 6G edge deployments.

Limitations: The current model assumes "Clairvoyance"—that we know the processing time and network delay the moment a job starts. In highly volatile networks, these estimates might be wrong. Future extensions of OnDisc will likely need to integrate robust estimation or reinforcement learning to handle such uncertainty.

In summary, OnDisc bridges the gap between complex machine scheduling theory and the practical, latency-plagued reality of Edge Computing.