Sintesi Tecnica: Offloading di Task Sensibile alle Code nel Continuum Computazionale sotto Carichi di Lavoro Dinamici

Definizione del Problema

Il continuum computazionale integra dispositivi locali, nodi edge e sistemi cloud in un'architettura unificata. Una sfida centrale in questo ambiente è l'offloading dei task: decidere se eseguire un task in arrivo localmente, all'edge o nel cloud. Questa decisione deve essere presa online in condizioni condivise e dinamiche dove il comportamento del sistema è difficile da prevedere.

Le principali difficoltà includono:

• Effetti di Accodamento: Man mano che l'utilizzo si avvicina alla capacità, il tempo di attesa diventa la componente dominante della latenza.
• Variabilità del Servizio: I tempi di servizio spesso presentano distribuzioni a coda pesante (es. Pareto), che i modelli esponenziali standard (M/M/c) non riescono a catturare, portando a una sottostima significativa dei ritardi.
• Carichi di Lavoro Dinamici: Il traffico è spesso a raffiche (bursty) e variabile nel tempo, rendendo insufficienti i modelli analitici a regime stazionario per il processo decisionale istantaneo.
• Limitazioni degli Approcci Esistenti:
  • Modelli Analitici: Assumono condizioni stazionarie e parametri fissi, fallendo nel reagire alla congestione istantanea.
  • Osservazioni dello Stato della Coda (es. JSQ): Reagiscono istantaneamente ma sono rumorose, sensibili alle fluttuazioni a breve termine e ignorano la variabilità del tempo di servizio.
  • Metodi Basati sull'Apprendimento (es. DRL): Richiedono un addestramento esteso, soffrono di alta complessità campionaria e mancano di garanzie formali di prestazione o interpretabilità.

Metodologia

Il documento propone un metodo di offloading sensibile alle code che utilizza un estimatore di ritardo ibrido per prendere decisioni per ogni singolo task. L'innovazione principale è un blending adattivo di modelli di accodamento analitici con osservazioni delle code in tempo reale.

1. Modello di Sistema

• Tier: Il sistema è composto da tier Locali ($L$), Edge ($E$) e Cloud ($C$).
• Arrivi: Modellati come un processo di Poisson con tassi variabili nel tempo. I tassi di arrivo per ogni tier ($\lambda_i$) sono stimati online utilizzando una finestra scorrevole per evitare bias derivanti da una distribuzione del traffico asimmetrica.
• Tempi di Servizio: Modellati utilizzando una distribuzione di Pareto (forma $\alpha > 2$) per rappresentare la variabilità a coda pesante.
• Componenti del Ritardo: Il ritardo totale $T_i$ è la somma del tempo di attesa ($W_i$), del tempo di servizio ($1/\mu_i$) e del ritardo di comunicazione ($D_i$).

2. L'Estimatore di Ritardo Ibrido

Il metodo stima il tempo di attesa ($W_i$) combinando due fonti complementari:

• Componente Analitica ($W^{model}_i$): Utilizza la formula di Allen–Cunneen per approssimare il tempo di attesa per una coda G/G/c. Questa corregge la standard formula Erlang-C M/M/c utilizzando il coefficiente di variazione quadratico ($C^2_s$) derivato dalla distribuzione di Pareto del servizio. Fornisce una stima stabile e orientata al futuro della congestione.
• Componente dello Stato della Coda ($W^{queue}_i$): Una stima reattiva basata sul numero attuale di task in attesa ($q_i$) rispetto al numero di server attivi ($n_i$). Cattura la congestione istantanea ma è rumorosa.

3. Meccanismo di Blending Adattivo

Inve แทน di utilizzare un parametro di miscelazione fisso, il metodo proposto impiega un peso di blending dipendente dal carico $\beta_i(t)$:
$$\beta_i(t) = \min\left(1, \frac{q_i(t)}{c_i}\right)$$
La stima finale è:
$$W_i(t) = (1 - \beta_i(t)) \cdot W^{model}_i(t) + \beta_i(t) \cdot W^{queue}_i(t)$$

• Logica: Quando un tier è vuoto ($q_i=0$), la stima si affida interamente al modello analitico. Man mano che il backlog della coda cresce rispetto alla capacità ($c_i$), il peso si sposta linearmente verso l'osservazione reattiva della coda. Una volta che il backlog supera la capacità, la stima si affida interamente allo stato osservato.
• Penalità di Utilizzo: Viene applicata una penalità moltiplicativa se l'utilizzo $\rho_i(t)$ supera una soglia (0.9) per scoraggiare l'instradamento verso tier quasi saturi.

4. Regola Decisionale

I task vengono assegnati al tier che minimizza il ritardo totale stimato:
$$i^*(t) = \arg \min_{i \in T} \left[ \hat{W}_i(t) + \frac{1}{\mu_i} + D_i(t) \right]$$
È incluso un passaggio di esplorazione $\epsilon$-greedy ($\epsilon=0.05$) per evitare che gli stimatori di tasso collassino per i tier meno selezionati.

Contributi Chiave

1. Stima del Ritardo Sensibile alle Code: Una formulazione che corregge analiticamente le approssimazioni del tempo di attesa G/G/c (tramite Allen–Cunneen) per tempi di servizio a coda pesante e le combina con le osservazioni delle code in tempo reale.
2. Stima del Tasso di Arrivo per Tier: Un estimatore a finestra scorrevole che traccia i tassi di arrivo separatamente per ogni tier, evitando il bias di un singolo proxy di tasso globale.
3. Routing Ibrido Predittivo-Reattivo Adattivo: Un meccanismo di blending dove il peso è una funzione deterministica del backlog attuale della coda, che non richiede un hyperparametro di miscelazione fisso o una calibrazione offline.
4. Validazione Duplice: Valutazione tramite sia un simulatore a eventi discreti che un testbed di emulazione basato su HTTP con dispatch di richieste asincrone reali, contesa delle code e misurazioni di tempo di esecuzione (wall-clock).
5. Analisi dell'Accuratezza della Stima: Dimostrazione che l'estimatore ibrido raggiunge un errore di previsione inferiore rispetto ai componenti solo-modello o solo-coda in tutti i livelli di carico.

Risultati Sperimentali

Il metodo è stato valutato sotto carichi crescenti, arrivi a raffiche e capacità edge variabili, confrontandolo con baseline statiche (Edge-First, Random), baseline dinamiche (JSQ, JSQ-S) e una policy Oracle.

• Riduzione della Latenza: Il metodo proposto riduce significamente la latenza media rispetto alle baseline statiche (Edge-First) e analiticamente deboli (Model-Only) in tutti i livelli di carico.
• Latenza di Coda (Tail Latency) e Fairness: Mentre le euristiche greedy sulla lunghezza della coda (JSQ) performano bene sulla latenza media aggregata, il metodo proposto dimostra una latenza di coda (P95) superiore per i task grandi e a coda pesante. Esso previene la sistematica inedia (starvation) dei task grandi spesso osservata nelle rotazioni JSQ pure.
• Errore di Previsione: L'estimatore ibrido mantiene il Mean Absolute Relative Error (MAPE) più basso in tutti i carichi, evitando la degradazione ad alto carico degli estimatori solo-modello e l'instabilità a basso carico degli estimatori solo-coda.
• Adattabilità: Nei casi di raffiche (burst), la policy si adatta rapidamente ridistribuendo i task verso il cloud man mano che la congestione dell'edge aumenta, stabilizzando la latenza più velocemente delle policy statiche.
• Overhead: L'overhead computazionale per il processo decisionale è nell'ordine dei microsecondi bassi (media ~7.4 µs in simulazione), confermando l'idoneità per nodi edge con risorse limitate.
• Validazione: L'emulazione basata su HTTP ha confermato che la dinamica del simulatore è riprodotta sotto l'elaborazione di richieste reali, con discrepanze attribuite a offset sistematici di calibrazione del ritardo di rete piuttosto che a un fallimento della policy.

Significato e Rivendicazioni

Il documento sostiene che il metodo proposto affronta una lacuna nella letteratura esistente soddisfacendo simultaneamente tre proprietà richieste per l'offloading nel continuum pratico:

1. Processo decisionale per task online senza addestramento.
2. Modellazione esplicita della variabilità dei tempi di servizio non esponenziali tramite approssimazione G/G/c.
3. Operatività leggera e priva di addestramento con consapevolezza della congestione per ogni tier.

Gli autori sottolineano che il metodo non richiede calibrazione offline o hyperparametri fissi, poiché il peso di blending è derivato direttamente dallo stato del sistema. I risultati suggeriscono che la combinazione di stabilità analitica e osservazione reattiva produce decisioni più robuste rispetto all'uso di una sola delle due fonti, specialmente in ambienti con tempi di servizio a coda pesante e carichi di lavoro dinamici.

Limitazioni Riconosciute:

• L'emulazione utilizza tempi di servizio Pareto sintetici invece di tracce di produzione.
• Si assume che i task siano indipendenti e stateless (nessuna località dei dati o dipendenze).
• Il metodo assume l'osservabilità dei tassi di servizio e delle lunghezze delle code, il che potrebbe richiedere strumentazione in contesti distribuiti.
• Il consumo energetico non è attualmente parte dell'obiettivo di ottimizzazione.
• Il vantaggio rispetto a JSQ è concentrato nella latenza di coda e nella fairness piuttosto che nella latenza media aggregata nelle configurazioni testate.