Technical Summary: Queue-Aware Task Offloading in the Computing Continuum under Dynamic Workloads

Problem Statement

The computing continuum integrates local devices, edge nodes, and cloud systems into a unified architecture. A central challenge in this environment is task offloading: deciding whether to execute an incoming task locally, at the edge, or in the cloud. This decision must be made online under dynamic, shared conditions where system behavior is difficult to predict.

Key difficulties include:

• Queueing Effects: As utilization approaches capacity, waiting time becomes the dominant component of latency.
• Service Variability: Service times often exhibit heavy-tailed distributions (e.g., Pareto), which standard exponential models (M/M/c) fail to capture, leading to significant underestimation of delays.
• Dynamic Workloads: Traffic is often bursty and time-varying, rendering steady-state analytical models insufficient for instantaneous decision-making.
• Limitations of Existing Approaches:
  • Analytical Models: Assume stationary conditions and fixed parameters, failing to react to instantaneous congestion.
  • Queue-State Observations (e.g., JSQ): React instantly but are noisy, sensitive to short-term fluctuations, and ignore service-time variability.
  • Learning-Based Methods (e.g., DRL): Require extensive training, suffer from high sample complexity, and lack formal performance guarantees or interpretability.

Methodology

The paper proposes a queue-aware offloading method that uses a hybrid delay estimator to make per-task decisions. The core innovation is an adaptive blending of analytical queueing models with real-time queue observations.

1. System Model

• Tiers: The system consists of Local ($L$), Edge ($E$), and Cloud ($C$) tiers.
• Arrivals: Modeled as a Poisson process with time-varying rates. Per-tier arrival rates ($\lambda_i$) are estimated online using a sliding window to avoid bias from asymmetric traffic distribution.
• Service Times: Modeled using a Pareto distribution (shape $\alpha > 2$) to represent heavy-tailed variability.
• Delay Components: Total delay $T_i$ is the sum of waiting time ($W_i$), service time ($1/\mu_i$), and communication delay ($D_i$).

2. The Hybrid Delay Estimator

The method estimates waiting time ($W_i$) by combining two complementary sources:

• Analytical Component ($W^{model}_i$): Uses the Allen–Cunneen formula to approximate the waiting time for a G/G/c queue. This corrects the standard M/M/c Erlang-C formula using the squared coefficient of variation ($C^2_s$) derived from the Pareto service distribution. This provides a stable, forward-looking estimate of congestion.
• Queue-State Component ($W^{queue}_i$): A reactive estimate based on the current number of tasks waiting ($q_i$) relative to the number of active servers ($n_i$). This captures instantaneous congestion but is noisy.

3. Adaptive Blending Mechanism

Instead of using a fixed mixing parameter, the proposed method employs a load-dependent blending weight $\beta_i(t)$:
$$\beta_i(t) = \min\left(1, \frac{q_i(t)}{c_i}\right)$$
The final estimate is:
$$W_i(t) = (1 - \beta_i(t)) \cdot W^{model}_i(t) + \beta_i(t) \cdot W^{queue}_i(t)$$

• Logic: When a tier is empty ($q_i=0$), the estimate relies entirely on the analytical model. As the queue backlog grows relative to capacity ($c_i$), the weight shifts linearly toward the reactive queue observation. Once the backlog exceeds capacity, the estimate relies entirely on the observed state.
• Utilization Penalty: A multiplicative penalty is applied if utilization $\rho_i(t)$ exceeds a threshold (0.9) to discourage routing to nearly saturated tiers.

4. Decision Rule

Tasks are assigned to the tier minimizing the estimated total delay:
$$i^*(t) = \arg \min_{i \in T} \left[ \hat{W}_i(t) + \frac{1}{\mu_i} + D_i(t) \right]$$
An $\epsilon$-greedy exploration step ($\epsilon=0.05$) is included to prevent rate estimators from collapsing for under-selected tiers.

Key Contributions

1. Queue-Aware Delay Estimation: A formulation that analytically corrects G/G/c waiting-time approximations (via Allen–Cunneen) for heavy-tailed service times and blends them with real-time queue observations.
2. Per-Tier Arrival Rate Estimation: A sliding-window estimator that tracks arrival rates separately for each tier, avoiding the bias of a single global rate proxy.
3. Adaptive Predictive-Reactive Hybrid Routing: A blending mechanism where the weight is a deterministic function of the current queue backlog, requiring no fixed mixing hyperparameter or offline tuning.
4. Dual Validation: Evaluation using both a discrete-event simulator and an HTTP-based emulation testbed with real asynchronous request dispatch, queue contention, and wall-clock measurements.
5. Analysis of Estimation Accuracy: Demonstration that the hybrid estimator achieves lower prediction error than model-only or queue-only components across all load levels.

Experimental Results

The method was evaluated under increasing load, bursty arrivals, and varying edge capacities, comparing against static baselines (Edge-First, Random), dynamic baselines (JSQ, JSQ-S), and an Oracle policy.

• Latency Reduction: The proposed method significantly reduces mean latency compared to static (Edge-First) and analytically-naive (Model-Only) baselines across all load levels.
• Tail Latency & Fairness: While greedy queue-length heuristics (JSQ) perform well on aggregate mean latency, the proposed method demonstrates superior tail latency (P95) for large, heavy-tailed tasks. It prevents the systematic starvation of large tasks often seen in pure JSQ routing.
• Prediction Error: The hybrid estimator maintains the lowest Mean Absolute Relative Error (MAPE) across all loads, avoiding the high-load degradation of model-only estimators and the low-load instability of queue-only estimators.
• Adaptability: In burst scenarios, the policy adapts quickly by redistributing tasks to the cloud as edge congestion increases, stabilizing latency faster than static policies.
• Overhead: The computational overhead for decision-making is in the low-microsecond range (mean ~7.4 µs in simulation), confirming suitability for resource-constrained edge nodes.
• Validation: The HTTP-based emulation confirmed that the simulator's dynamics are reproduced under real request processing, with discrepancies attributed to systematic network-delay calibration offsets rather than policy failure.

Significance and Claims

The paper claims that the proposed method addresses a gap in existing literature by simultaneously satisfying three properties required for practical continuum offloading:

1. Online per-task decision making without training.
2. Explicit modeling of non-exponential service-time variability via G/G/c approximation.
3. Lightweight, training-free operation with per-tier congestion awareness.

The authors emphasize that the method does not require offline calibration or fixed hyperparameters, as the blending weight is derived directly from the system state. The results suggest that combining analytical stability with reactive observation yields more robust decisions than relying on either source alone, particularly in environments with heavy-tailed service times and dynamic workloads.

Limitations Acknowledged:

• The emulation uses synthetic Pareto service times rather than production traces.
• Tasks are assumed independent and stateless (no data locality or dependencies).
• The method assumes observability of service rates and queue lengths, which may require instrumentation in distributed settings.
• Energy consumption is not currently part of the optimization objective.
• The advantage over JSQ is concentrated in tail latency and fairness rather than aggregate mean latency in the tested configurations.