Resumo Técnico: Descarregamento de Tarefas Consciente de Filas no Continuum de Computação sob Cargas de Trabalho Dinâmicas

Declaração do Problema

O continuum de computação integra dispositivos locais, nós de borda (edge) e sistemas em nuvem em uma arquitetura unificada. Um desafio central neste ambiente é o descarregamento de tarefas (task offloading): decidir se uma tarefa recebida deve ser executada localmente, na borda ou na nuvem. Esta decisão deve ser tomada online sob condições compartilhadas e dinâmicas, onde o comportamento do sistema é difícil de prever.

Principais dificuldades incluem:

• Efeitos de Enfileiramento: À medida que a utilização se aproxima da capacidade, o tempo de espera torna-se o componente dominante da latência.
• Variabilidade de Serviço: Os tempos de serviço frequentemente exibem distribuições de cauda pesada (ex: Pareto), que os modelos exponenciais padrão (M/M/c) falham em capturar, levando a uma subestimação significativa dos atrasos.
• Cargas de Trabalho Dinâmicas: O tráfego é frequentemente intermitente (bursty) e variável no tempo, tornando modelos analíticos de estado estacionário insuficientes para a tomada de decisão instantânea.
• Limitações das Abordagens Existentes:
  • Modelos Analíticos: Assumem condições estacionárias e parâmetros fixos, falhando em reagir ao congestionamento instantâneo.
  • Observações de Estado de Fila (ex: JSQ): Reagem instantaneamente, mas são ruidosas, sensíveis a flutuações de curto prazo e ignoram a variabilidade do tempo de serviço.
  • Métodos Baseados em Aprendizado (ex: DRL): Exigem treinamento extensivo, sofrem com alta complexidade de amostra e carecem de garantias formais de desempenho ou interpretabilidade.

Metodologia

O artigo propõe um método de descarregamento consciente de filas que utiliza um estimador de atraso híbrido para tomar decisões por tarefa. A inovação central é uma mistura adaptativa de modelos de enfileiramento analíticos com observações de fila em tempo real.

1. Modelo do Sistema

• Camadas (Tiers): O sistema consiste nas camadas Local ($L$), Borda ($E$) e Nuvem ($C$).
• Chegadas: Modeladas como um processo de Poisson com taxas variáveis no tempo. As taxas de chegada por camada ($\lambda_i$) são estimadas online usando uma janela deslizante para evitar o viés da distribuição de tráfego assimétrica.
• Tempos de Serviço: Modelados usando uma distribuição Pareto (forma $\alpha > 2$) para representar a variabilidade de cauda pesada.
• Componentes de Atraso: O atraso total $T_i$ é a soma do tempo de espera ($W_i$), tempo de serviço ($1/\mu_i$) e atraso de comunicação ($D_i$).

2. O Estimador de Atraso Híbrido

O método estima o tempo de espera ($W_i$) combinando duas fontes complementares:

• Componente Analítico ($W^{model}_i$): Utiliza a fórmula de Allen–Cunneen para aproximar o tempo de espera para uma fila G/G/c. Isso corrige a fórmula Erlang-C M/M/c padrão usando o coeficiente de variação ao quadrado ($C^2_s$) derivado da distribuição de serviço Pareto. Isso fornece uma estimativa estável e prospectiva do congestionamento.
• Componente de Estado de Fila ($W^{queue}_i$): Uma estimativa reativa baseada no número atual de tarefas aguardando ($q_i$) em relação ao número de servidores ativos ($n_i$). Isso captura o congestionamento instantâneo, mas é ruidoso.

3. Mecanismo de Mistura Adaptativa

Em vez de usar um parâmetro de mistura fixo, o método proposto emprega um peso de mistura dependente da carga $\beta_i(t)$:
$$\beta_i(t) = \min\left(1, \frac{q_i(t)}{c_i}\right)$$
A estimativa final é:
$$W_i(t) = (1 - \beta_i(t)) \cdot W^{model}_i(t) + \beta_i(t) \cdot W^{queue}_i(t)$$

• Lógica: Quando uma camada está vazia ($q_i=0$), a estimativa depende inteiramente do modelo analítico. À medida que o acúmulo da fila cresce em relação à capacidade ($c_i$), o peso desloca-se linearmente para a observação reativa da fila. Uma vez que o acúmulo excede a capacidade, a estimativa depende inteiramente do estado observado.
• Penalidade de Utilização: Uma penalidade multiplicativa é aplicada se a utilização $\rho_i(t)$ exceder um limiar (0.9) para desencorajar o roteamento para camadas quase saturadas.

4. Regra de Decisão

As tarefas são atribuídas à camada que minimiza o atraso total estimado:
$$i^*(t) = \arg \min_{i \in T} \left[ \hat{W}_i(t) + \frac{1}{\mu_i} + D_i(t) \right]$$
Um passo de exploração $\epsilon$-greedy ($\epsilon=0.05$) é incluído para evitar que os estimadores de taxa colapsem para camadas menos selecionadas.

Principais Contribuições

1. Estimativa de Atraso Consciente de Fila: Uma formulação que corrige analiticamente as aproximações de tempo de espera G/G/c (via Allen–Cunneen) para tempos de serviço de cauda pesada e as mistura com observações de fila em tempo real.
2. Estimativa de Taxa de Chegada por Camada: Um estimador de janela deslizante que rastreia taxas de chegada separadamente para cada camada, evitando o viés de um único proxy de taxa global.
3. Roteamento Híbrido Preditivo-Reativo Adaptável: Um mecanismo de mistura onde o peso é uma função determinística do acúmulo atual da fila, exigindo nenhum hiperparâmetro de mistura fixo ou ajuste offline.
4. Validação Dupla: Avaliação usando tanto um simulador de eventos discretos quanto um testbed de emulação baseado em HTTP com despacho de requisições assíncronas real, contenção de fila e medições de tempo de relógio (wall-clock).
5. Análise de Precisão de Estimativa: Demonstração de que o estimador híbrido alcança menor erro de previsão do que os componentes de apenas modelo ou apenas fila em todas as cargas.

Resultados Experimentais

O método foi avaliado sob carga crescente, chegadas intermitentes e capacidades de borda variáveis, comparando-se contra baselines estáticas (Edge-First, Random), baselines dinâmicas (JSQ, JSQ-S) e uma política Oracle.

• Redução de Latência: O método proposto reduz significamente a latência média em comparação com as baselines estáticas (Edge-First) e analiticamente ingênuas (Model-Only) em todos os níveis de carga.
• Latência de Cauda e Equidade: Enquanto heurísticas gananciosas de comprimento de fila (JSQ) performam bem na latência média agregada, o método proposto demonstra latência de cauda (P95) superior para tarefas grandes e de cauda pesada. Ele evita a inanição sistemática de tarefas grandes frequentemente vista no roteamento puramente JSQ.
• Erro de Previsão: O estimador híbrido mantém o menor Erro Médio Absoluto Relativo (MAPE) em todas as cargas, evitando a degradação de alta carga dos estimadores de apenas modelo e a instabilidade de baixa carga dos estimadores de apenas fila.
• Adaptabilidade: Em cenários de surtos (bursts), a política adapta-se rapidamente ao redistribuir tarefas para a nuvem conforme o congestionamento da borda aumenta, estabilizando a latência mais rápido que políticas estáticas.
• Sobrecarga (Overhead): A sobrecarga computacional para tomada de decisão está na ordem de microssegundos baixos (média de ~7.4 µs em simulação), confirmando a adequação para nós de borda com recursos limitados.
• Validação: A emulação baseada em HTTP confirmou que a dinâmica do simulador é reproduzida sob processamento de requisições reais, com discrepâncias atribuídas a offsets sistemáticos de calibração de atraso de rede, em vez de falha da política.

Significância e Alegações

O artigo alega que o método proposto aborda uma lacuna na literatura existente ao satisfazer simultaneamente três propriedades necessárias para o descarregamento prático no continuum:

1. Tomada de decisão por tarefa online sem treinamento.
2. Modelagem explícita de variabilidade de tempo de serviço não-exponencial via aproximação G/G/c.
3. Operação leve e livre de treinamento com consciência de congestionamento por camada.

Os autores enfatizam que o método não requer calibração offline ou hiperparâmetros fixos, pois o peso de mistura é derivado diretamente do estado do sistema. Os resultados sugerem que combinar a estabilidade analítica com a observação reativa produz decisões mais robustas do que depender de apenas uma fonte, particularmente em ambientes com tempos de serviço de cauda pesada e cargas de trabalho dinâmicas.

Limitações Reconhecidas:

• A emulação usa tempos de serviço Pareto sintéticos em vez de traços de produção.
• Assume-se que as tarefas são independentes e sem estado (sem localidade de dados ou dependências).
• O método assume a observabilidade de taxas de serviço e comprimentos de fila, o que pode exigir instrumentação em ambientes distribuídos.
• O consumo de energia não faz parte do objetivo de otimização atualmente.
• A vantagem sobre o JSQ concentra-se na latência de cauda e equidade, em vez da latência média agregada nas configurações testadas.