Technische Samenvatting: Queue-bewuste Taakoffloading in de Computing Continuum onder Dynamische Workloads

Probleemstelling

De computing continuum integreert lokale apparaten, edge-nodes en cloud-systemen tot een uniforme architectuur. Een centrale uitdaging in deze omgeving is taakoffloading: beslissen of een binnenkomende taak lokaal, bij de edge of in de cloud moet worden uitgevoerd. Deze beslissing moet online worden genomen onder dynamische, gedeelde omstandigheden waarbij het systeemgedrag moeilijk te voorspellen is.

Belangrijke moeilijkheden zijn onder meer:

• Queueing Effecten: Naarmate de benutting de capaciteit nadert, wordt de wachttijd de dominante component van de latentie.
• Service Variabiliteit: Servicetijden vertonen vaak heavy-tailed distributies (bijv. Pareto), waardoor standaard exponentiële modellen (M/M/c) falen en leiden tot een significante onderschatting van vertragingen.
• Dynamische Workloads: Verkeer is vaak bursty en tijdsvariërend, wat stationaire analytische modellen ontoereikend maakt voor instantane besluitvorming.
• Beperkingen van Bestaande Benaderingen:
  • Analytische Modellen: Veronderstellen stationaire condities en vaste parameters, waardoor ze niet kunnen reageren op instantane congestie.
  • Queue-State Observaties (bijv. JSQ): Reageren direct maar zijn ruizig, gevoelig voor korte termijn fluctuaties en negeren variabiliteit in de servicetijd.
  • Learning-Based Methoden (bijv. DRL): Vereisen uitgebreide training, lijden onder hoge sample complexiteit en missen formele prestatiegaranties of interpreteerbaarheid.

Methodologie

Het artikel stelt een queue-bewuste offloading methode voor die een hybride delay estimator gebruikt om per-taak beslissingen te nemen. De kerninnovatie is een adaptieve blending van analytische queueing modellen met real-time queue observaties.

1. Systeemmodel

• Tiers: Het systeem bestaat uit Local ($L$), Edge ($E$) en Cloud ($C$) tiers.
• Arrivals: Gemodelleerd als een Poisson-proces met tijdsvariërende rates. Per-tier aankomst rates ($\lambda_i$) worden online geschat met behulp van een sliding window om bias door asymmetrische verkeersverdeling te voorkomen.
• Servicetijden: Gemodelleerd met een Pareto distributie (vorm $\alpha > 2$) om heavy-tailed variabiliteit te representeren.
• Delay Componenten: De totale delay $T_i$ is de som van de wachttijd ($W_i$), de servicetijd ($1/\mu_i$) en de communicatie delay ($D_i$).

2. De Hybride Delay Estimator

De methode schat de wachttijd ($W_i$) door twee complementaire bronnen te combineren:

• Analytische Component ($W^{model}_i$): Gebruikt de Allen–Cunneen formule om de wachttijd voor een G/G/c queue te benaderen. Dit corrigeert de standaard M/M/c Erlang-C formule met de squared coefficient of variation ($C^2_s$) afgeleid van de Pareto serviceverdeling. Dit levert een stabiele, vooruitziende schatting van congestie.
• Queue-State Component ($W^{queue}_i$): Een reactieve schatting gebaseerd op het huidige aantal wachtende taken ($q_i$) ten opzichte van het aantal actieve servers ($n_i$). Dit vangt instantane congestie op, maar is ruizig.

3. Adaptief Blending Mechanisme

In plaats van een vaste mixing parameter, gebruikt de voorgestelde methode een load-dependent blending weight $\beta_i(t)$:
$$\beta_i(t) = \min\left(1, \frac{q_i(t)}{c_i}\right)$$
De uiteindelijke schatting is:
$$W_i(t) = (1 - \beta_i(t)) \cdot W^{model}_i(t) + \beta_i(t) \cdot W^{queue}_i(t)$$

• Logica: Wanneer een tier leeg is ($q_i=0$), vertrouwt de schatting volledig op het analytische model. Naarmate de queue backlog groeit ten opzichte van de capaciteit ($c_i$), verschuift het gewicht lineair naar de reactieve queue observatie. Zodra de backlog de capaciteit overschrijdt, vertrouwt de schatting volledig op de geobserveerde staat.
• Utilization Penalty: Een multiplicatieve penalty wordt toegepast als de benutting $\rho_i(t)$ een drempelwaarde (0.9) overschrijdt om routering naar bijna verzadigde tiers te ontmoedigen.

4. Beslissingsregel

Taken worden toegewezen aan de tier die de geschatte totale delay minimaliseert:
$$i^*(t) = \arg \min_{i \in T} \left[ \hat{W}_i(t) + \frac{1}{\mu_i} + D_i(t) \right]$$
Een $\epsilon$-greedy exploratiestap ($\epsilon=0.05$) is opgenomen om te voorkomen dat rate estimators instorten voor minder geselecteerde tiers.

Belangrijkste Bijdragen

1. Queue-Bewuste Delay Estimatie: Een formulering die analytische G/G/c wachttijd benaderingen (via Allen–Cunneen) voor heavy-tailed servicetijden corrigeert en deze combineert met real-time queue observaties.
2. Per-Tier Arrival Rate Estimatie: Een sliding-window estimator die aankomst rates apart voor elke tier bijhoudt, waardoor bias door een enkele globale rate proxy wordt vermeden.
3. Adaptief Predictief-Reactief Hybride Routing: Een blending mechanisme waarbij het gewicht een deterministische functie is van de huidige queue backlog, wat geen vaste mixing hyperparameter of offline tuning vereist.
4. Dubbele Validatie: Evaluatie met zowel een discrete-event simulator als een HTTP-gebaseerde emulatie testbed met echte asynchrone request dispatch, queue contention en wall-clock metingen.
5. Analyse van Estimatie Nauwkeurigheid: Demonstratie dat de hybride estimator een lagere voorspellingsfout bereikt dan enkel model-gebaseerde of enkel queue-gebaseerde componenten over alle load levels.

Experimentele Resultaten

De methode werd geëvalueerd onder toenemende belasting, bursty aankomsten en variërende edge capaciteiten, waarbij het werd vergeleken met statische baselines (Edge-First, Random), dynamische baselines (JSQ, JSQ-S) en een Oracle policy.

• Reductie in Latentie: De voorgestelde methode vermindert de gemiddelde latentie aanzienlijk vergeleken met statische (Edge-First) en analytisch naïeve (Model-Only) baselines over alle load levels.
• Tail Latency & Fairness: Terwijl greedige queue-lengte heuristieken (JSQ) goed presteren op de geaggregeerde gemiddelde latentie, demonstreert de voorgestelde methode een superieure tail latency (P95) voor grote, heavy-tailed taken. Het voorkomt de systematische uithongering van grote taken die vaak wordt gezien bij pure JSQ routing.
• Voorspellingsfout: De hybride estimator behoudt de laagste Mean Absolute Relative Error (MAPE) over alle belastingen, waarbij de degradatie bij hoge belasting (typisch voor model-only) en de instabiliteit bij lage belasting (typisch voor queue-only) worden vermeden.
• Adaptiviteit: In burst scenario's past de policy zich snel aan door taken te herverdelen naar de cloud naarmate de edge congestie toeneemt, waardoor de latentie sneller stabiliseert dan statische policies.
• Overhead: De computationele overhead voor besluitvorming ligt in de low-microsecond range (gemiddeld ~7.4 µs in simulatie), wat de geschiktheid voor resource-beperkte edge nodes bevestigt.
• Validatie: De HTTP-gebaseerde emulatie bevestigde dat de dynamiek van de simulator wordt gereproduceerd onder echte request verwerking, waarbij discrepanties worden toegeschreven aan systematische netwerk-delay kalibratie offsets in plaats van policy falen.

Betekenis en Claims

Het artikel claimt dat de voorgestelde methode een gat in de bestaande literatuur opvult door gelijktijdig drie eigenschappen te vervullen die vereist zijn voor praktische continuüm offloading:

1. Online per-taak besluitvorming zonder training.
2. Expliciete modellering van niet-exponentiële service-time variabiliteit via G/G/c benadering.
3. Lichtgewicht, training-vrije operatie met per-tier congestie bewustzijn.

De auteurs benadrukken dat de methode geen offline kalibratie of vaste hyperparameters vereist, aangezien de blending weight direct uit de systeemstaat wordt afgeleid. De resultaten suggereren dat het combineren van analytische stabiliteit met reactieve observatie robuustere beslissingen oplevert dan het vertrouwen op slechts één van beide bronnen, vooral in omgevingen met heavy-tailed servicetijden en dynamische workloads.

Erkende Beperkingen:

• De emulatie gebruikt synthetische Pareto servicetijden in plaats van productie traces.
• Taken worden verondersteld onafhankelijk en stateless te zijn (geen data locality of afhankelijkheden).
• De methode veronderstelt observeerbaarheid van service rates en queue lengtes, wat instrumentatie in gedistribueerde settings kan vereisen.
• Energieverbruik is momenteel geen onderdeel van de optimalisatie doelstelling.
• Het voordeel ten opzichte van JSQ concentreert zich op tail latency en fairness in plaats van de geaggregeerde gemiddelde latentie in de geteste configuraties.