Résumé technique : Déchargement de tâches sensible à la file d'attente dans le continuum de calcul sous des charges de travail dynamiques

Énoncé du problème

Le continuum de calcul intègre les dispositifs locaux, les nœuds de bordure (edge) et les systèmes cloud en une architecture unifiée. Un défi central dans cet environnement est le déchargement de tâches (task offloading) : décider s'il faut exécuter une tâche entrante localement, à la bordure ou dans le cloud. Cette décision doit être prise en ligne dans des conditions partagées et dynamiques où le comportement du système est difficile à prédire.

Difficultés clés :

• Effets de file d'attente : À mesure que l'utilisation approche de la capacité, le temps d'attente devient la composante dominante de la latence.
• Variabilité du service : Les temps de service présentent souvent des distributions à queue lourde (ex: Pareto), que les modèles exponentiels standards (M/M/c) ne parviennent pas à capturer, entraînant une sous-estimation significative des délais.
• Charges de travail dynamiques : Le trafic est souvent par rafales (bursty) et variable dans le temps, rendant les modèles analytiques en régime permanent insuffisants pour la prise de décision instantanée.
• Limites des approches existantes :
  • Modèles analytiques : Supposent des conditions stationnaires et des paramètres fixes, échouant à réagir à la congestion instantanée.
  • Observations de l'état de la file (ex: JSQ) : Réagissent instantanément mais sont bruyantes, sensibles aux fluctuations à court terme et ignorent la variabilité du temps de service.
  • Méthodes basées sur l'apprentissage (ex: DRL) : Nécessitent un entraînement intensif, souffrent d'une haute complexité d'échantillonnage et manquent de garanties de performance formelles ou d'interprétabilité.

Méthodologie

L'article propose une méthode de déchargement sensible à la file d'attente qui utilise un estimateur de délai hybride pour prendre des décisions par tâche. L'innovation centrale est un mélange adaptatif de modèles de file d'attente analytiques et d'observations de file en temps réel.

1. Modèle de système

• Niveaux (Tiers) : Le système se compose de niveaux Local ($L$), Bordure ($E$) et Cloud ($C$).
• Arrivées : Modélisées comme un processus de Poisson avec des taux variables dans le temps. Les taux d'arrivée par niveau ($\lambda_i$) sont estimés en ligne à l'aide d'une fenêtre glissante pour éviter le biais dû à une distribution de trafic asymétrique.
• Temps de service : Modélisés à l'aide d'une distribution de Pareto (forme $\alpha > 2$) pour représenter la variabilité à queue lourde.
• Composantes du délai : Le délai total $T_i$ est la somme du temps d'attente ($W_i$), du temps de service ($1/\mu_i$) et du délai de communication ($D_i$).

2. L'estimateur de délai hybride

La méthode estime le temps d'attente ($W_i$) en combinant deux sources complémentaires :

• Composante analytique ($W^{model}_i$) : Utilise la formule d'Allen–Cunneen pour approximer le temps d'attente d'une file G/G/c. Cela corrige la formule d'Erlang-C M/M/c standard en utilisant le coefficient de variation au carré ($C^2_s$) dérivé de la distribution de Pareto du service. Cela fournit une estimation stable et prospective de la congestion.
• Composante de l'état de la file ($W^{queue}_i$) : Une estimation réactive basée sur le nombre actuel de tâches en attente ($q_i$) par rapport au nombre de serveurs actifs ($n_i$). Cela capture la congestion instantanée mais est bruyant.

3. Mécanisme de mélange adaptatif

Au lieu d'utiliser un paramètre de mélange fixe, la méthode proposée emploie un poids de mélange dépendant de la charge $\beta_i(t)$ :
$$\beta_i(t) = \min\left(1, \frac{q_i(t)}{c_i}\right)$$
L'estimation finale est :
$$W_i(t) = (1 - \beta_i(t)) \cdot W^{model}_i(t) + \beta_i(t) \cdot W^{queue}_i(t)$$

• Logique : Lorsqu'un niveau est vide ($q_i=0$), l'estimation repose entièrement sur le modèle analytique. À mesure que l'accumulation de la file augmente par rapport à la capacité ($c_i$), le poids bascule linéairement vers l'observation réactive de la file. Une fois que l'accumulation dépasse la capacité, l'estimation repose entièrement sur l'état observé.
• Pénalité d'utilisation : Une pénalité multiplicative est appliquée si l'utilisation $\rho_i(t)$ dépasse un seuil (0,9) pour décourager l'aiguillage vers des niveaux presque saturés.

4. Règle de décision

Les tâches sont assignées au niveau minimisant le délai total estimé :
$$i^*(t) = \arg \min_{i \in T} \left[ \hat{W}_i(t) + \frac{1}{\mu_i} + D_i(t) \right]$$
Une étape d'exploration $\epsilon$-greedy ($\epsilon=0,05$) est incluse pour éviter que les estimateurs de taux ne s'effondrent pour les niveaux sous-sélectionnés.

Principales contributions

1. Estimation de délai sensible à la file : Une formulation qui corrige analytiquement les approximations du temps d'attente G/G/c (via Allen–Cunneen) pour les temps de service à queue lourde et les mélange avec des observations de file en temps réel.
2. Estimation du taux d'arrivée par niveau : Un estimateur par fenêtre glissante qui suit les taux d'arrivée séparément pour chaque niveau, évitant le biais d'un proxy de taux global unique.
3. Routage hybride prédictif-réactif adaptatif : Un mécanisme de mélange où le poids est une fonction déterministe de l'accumulation actuelle de la file, ne nécessitant aucun hyperparamètre de mélange fixe ou réglage hors ligne.
4. Double validation : Évaluation utilisant à la fois un simulateur à événements discrets et un banc d'essai d'émulation basé sur HTTP avec dispatch de requêtes asynchrones réelles, contention de file et mesures de temps réel (wall-clock).
5. Analyse de la précision de l'estimation : Démonstration que l'estimateur hybride atteint une erreur de prédiction plus faible que les composantes de modèle seul ou de file seule sur tous les niveaux de charge.

Résultats expérimentaux

La méthode a été évaluée sous une charge croissante, des arrivées par rafales et des capacités de bordure variables, en comparaison avec des bases statiques (Edge-First, Random), des bases dynamiques (JSQ, JSQ-S) et une politique Oracle.

• Réduction de la latence : La méthode proposée réduit significativement la latence moyenne par rapport aux bases statiques (Edge-First) et analytiquement naïves (Model-Only) sur tous les niveaux de charge.
• Latence de queue (Tail Latency) et équité : Bien que les heuristiques de longueur de file gourmandes (JSQ) performent bien sur la latence moyenne agrégée, la méthode proposée démontre une latence de queue (P95) supérieure pour les tâches volumineuses à queue lourde. Elle empêît la famine systématique des grandes tâches souvent observée dans le routage JSQ pur.
• Erreur de prédiction : L'estimateur hybride maintient l'erreur absolue moyenne relative (MAPE) la plus basse sur toutes les charges, évitant la dégradation à haute charge des estimateurs de modèle seul et l'instabilité à faible charge des estimateurs de file seule.
• Adaptabilité : Dans les scénarios de rafales, la politique s'adapte rapidement en redistribuant les tâches vers le cloud à mesure que la congestion de la bordure augmente, stabilisant la latence plus rapidement que les politiques statiques.
• Surcharge (Overhead) : La surcharge de calcul pour la prise de décision est dans la plage de quelques microsecondes (moyenne ~7,4 µs en simulation), confirmant l'aptitude pour les nœuds de bordure aux ressources limitées.
• Validation : L'émulation HTTP a confirmé que la dynamique du simulateur est reproduite sous des requêtes réelles, les écarts étant attribués à des décalages systématiques de calibration du délai réseau plutôt qu'à un échec de la politique.

Signification et affirmations

L'article affirme que la méthode proposée comble une lacune dans la littérature existante en satisfaisant simultanément trois propriétés requises pour le déchargement dans le continuum :

1. Une prise de décision par tâche en ligne sans entraînement.
2. Une modélisation explicite de la variabilité du temps de service non exponentielle via l'approximation G/G/c.
3. Un fonctionnement léger et sans entraînement avec une conscience de la congestion par niveau.

Les auteurs soulignent que la méthode ne nécessite ni calibration hors ligne ni hyperparamètres fixes, car le poids de mélange est dérivé directement de l'état du système. Les résultats suggèrent que la combinaison de la stabilité analytique et de l'observation réactive produit des décisions plus robustes que de compter sur une seule source, particulièrement dans les environnements avec des temps de service à queue lourde et des charges de travail dynamiques.

Limites reconnues :

• L'émulation utilise des temps de service Pareto synthétiques plutôt que des traces de production.
• Les tâches sont supposées indépendantes et sans état (pas de localité de données ou de dépendances).
• La méthode suppose l'observabilité des taux de service et des longueurs de file, ce qui peut nécessiter une instrumentation dans des contextes distribués.
• La consommation d'énergie n'est pas actuellement intégrée dans l'objectif d'optimisation.
• L'avantage sur JSQ se concentre sur la latence de queue et l'équité plutôt que sur la latence moyenne agrégée dans les configurations testées.