Improved Contact Graph Routing in Delay Tolerant Networks with Capacity and Buffer Constraints

Este artigo propõe uma melhoria no algoritmo de Roteamento em Grafo de Contato (CGR) para Redes Tolerantes a Atrasos em comunicações satelitais, introduzindo operações de divisão de contatos e poda de arestas para garantir que as rotas encontradas respeitem proativamente as restrições de capacidade e buffer, minimizando colisões e atrasos enquanto asseguram a solução ótima de tempo de entrega.

O essencial

Imagine que você está tentando enviar uma carta valiosa de um ponto A para um ponto B, mas o caminho não é uma estrada contínua. Em vez disso, é como se você tivesse que passar a carta de mão em mão entre amigos que só se encontram em horários muito específicos e por curtos períodos. Além disso, cada amigo tem uma mochila (memória) com tamanho limitado e só pode carregar um certo peso de cartas por vez.

Se você tentar enviar a carta sem planejar, ela pode ficar presa em uma mochila cheia, ou o amigo pode tentar passar a carta para outro que já não tem mais espaço, causando um "engarrafamento" e fazendo a carta demorar muito para chegar ou até se perder.

Este artigo científico propõe uma nova forma de planejar essa viagem para redes de satélites (que funcionam exatamente como esses amigos com horários específicos).

Aqui está a explicação simplificada:

1. O Problema: O "Plano de Voo" Imperfeito

Antes, os satélites usavam um sistema chamado CGR (Roteamento por Gráfico de Contato). Funcionava assim:

• O satélite calculava o caminho mais rápido.
• Ele enviava a mensagem.
• O erro: O cálculo era baseado em uma ideia simplista de "espaço disponível". Era como se o satélite dissesse: "Tenho 100MB de espaço, vou enviar 50MB". Mas, na hora de enviar, ele descobria que, naquele segundo exato, outro satélite já estava usando aquele espaço ou a mochila do próximo satélite já estava cheia.
• Resultado: A mensagem ficava presa, tinha que ser desviada de última hora (o que gasta tempo e bateria) ou, pior, descartada.

2. A Solução: O "Detetive de Futuro"

Os autores propõem uma melhoria que age antes de enviar a mensagem. Eles chamam isso de "Gestão Proativa". Em vez de reagir quando o problema acontece, eles previnem o problema durante o planejamento.

Eles usam duas técnicas principais, que podemos comparar a:

A. "Cortar o Pão" (Contact Splitting)

Imagine que o contato entre dois satélites é uma fatia de pão de 10 minutos.

• Antes: O sistema via apenas "1 fatia de 10 minutos". Se dois satélites tentassem usar a mesma fatia ao mesmo tempo, haveria briga.
• Agora: O sistema "corta" a fatia de pão. Se o Satélite A já reservou os primeiros 3 minutos para uma mensagem, o sistema divide a fatia em duas: "3 minutos ocupados" e "7 minutos livres".
• O benefício: Quando o próximo satélite vai planejar sua rota, ele vê apenas os "7 minutos livres". Ele nunca vai tentar enviar algo para um horário que já está ocupado. Isso evita colisões de dados.

B. "Olhar para a Mochila do Futuro" (Buffer Management)

Imagine que você está passando uma bola de um amigo para outro.

• Antes: Você passava a bola sem saber se o próximo amigo tinha espaço na mochila. Se a mochila dele estivesse cheia, a bola caía no chão e você tinha que correr de volta para pegar outra.
• Agora: Antes de passar a bola, você olha para uma "tabela de previsão". Você sabe exatamente quando a bola vai chegar no amigo B e quanto tempo ela vai ficar lá.
  • Se a tabela diz que a mochila do amigo B vai encher naquele momento, o sistema proíbe o caminho que leva a essa mochila cheia.
  • Ele corta as "pontes" (arestas do gráfico) que levariam a um engarrafamento.
• O benefício: A mensagem só segue caminhos onde há espaço garantido na mochila de todos os intermediários.

3. O Resultado: A Rota Perfeita

Com essas duas técnicas, o algoritmo encontra o caminho mais rápido possível, mas apenas entre os caminhos que são realmente possíveis (sem esbarrar em limites de espaço ou memória).

• Menos atrasos: As mensagens não ficam presas esperando espaço.
• Menos trabalho extra: Os satélites intermediários não precisam gastar energia e tempo calculando novos caminhos de última hora porque a rota já foi validada desde o início.
• Segurança: O sistema ainda deixa um "margem de segurança" (como um espaço extra na mochila) caso algo inesperado aconteça, como um satélite ter uma falha momentânea.

Resumo da Ópera

Pense no sistema antigo como um turista que pega um táxi sem saber se o motorista vai conseguir estacionar no destino. Ele chega lá, vê que não tem vaga, e tem que correr para achar outro táxi.

O sistema novo é como um planejador de viagens inteligente que:

1. Verifica se o estacionamento está livre no horário exato da chegada.
2. Corta da rota todas as opções que levariam a um estacionamento cheio.
3. Entrega ao turista apenas o caminho que garante que ele vai chegar ao destino sem parar no meio do caminho.

Isso torna a comunicação entre satélites muito mais rápida, eficiente e confiável, especialmente em missões espaciais onde cada segundo e cada byte de memória contam.

Resumo técnico

Resumo Técnico: Roteamento Otimizado em Redes Tolerantes a Atrasos (DTN) para Comunicações Satelitais

1. Problema e Motivação

As redes de satélites enfrentam desafios únicos, como conectividade intermitente, grandes atrasos de propagação e recursos limitados (capacidade de enlace e memória de buffer). O paradigma de Redes Tolerantes a Atrasos (DTN) e o algoritmo de Roteamento por Grafo de Contato (CGR) são soluções padrão para gerenciar esses ambientes. No entanto, o CGR tradicional apresenta limitações críticas:

• Gestão Reativa: O CGR atual gerencia a capacidade do enlace e o uso do buffer apenas durante a fase de encaminhamento (forwarding), após a rota ter sido escolhida.
• Modelos Simplificados: O algoritmo utiliza uma "hipótese de volume linear" que não rastreia o uso temporal dos contatos, levando a colisões de capacidade.
• Consequências: Essa abordagem reativa causa colisões de transmissão, desperdício de recursos, atrasos adicionais e necessidade de reroteamento (retransmissão ou recálculo de rota) quando ocorrem falhas de buffer ou capacidade. Em ambientes com recursos escassos (como comunicações cislunares ou constelações LEO), isso resulta em soluções subótimas e perda de pacotes.

O objetivo do artigo é preencher essa lacuna propondo uma gestão proativa e global de capacidade e buffer, realizada antes ou durante a busca da rota, garantindo que a rota encontrada seja viável e ótima.

2. Metodologia Proposta

Os autores propõem uma extensão ao CGR baseado em roteamento de origem (Source-Routing), formalizando o problema como o FEAP-CB (Feasible Earliest-Arrival Path with Capacity and Buffer constraints). O objetivo é encontrar o caminho que minimize o tempo de chegada, respeitando estritamente as restrições de capacidade de contato e limite de buffer dos nós.

A solução baseia-se em duas operações principais aplicadas ao Grafo de Contatos (CP - Contact Plan):

A. Divisão de Contato (Contact Splitting)

• Para Capacidade: Quando um pacote é roteado, o algoritmo remove a porção do contato consumida por esse pacote do plano de contatos original. Um contato $C_j$ é dividido em novos contatos ($C_{j,1}$ e $C_{j,2}$), eliminando o intervalo de tempo onde a capacidade já está reservada. Isso garante que futuros roteamentos não tentem usar capacidade indisponível.
• Para Buffer (Temporário): Antes de rotear um pacote específico, o algoritmo simula o uso do buffer. Se o pacote causar um transbordamento (overflow) em um nó durante um intervalo de tempo específico, as porções dos contatos que entregariam o pacote a esse nó nesse intervalo são temporariamente removidas via divisão de contato.

B. Poda de Arestas (Edge Pruning)

• Além de remover porções de contatos, o algoritmo remove arestas (conexões entre contatos) que levariam a sequências problemáticas.
• Lógica: Se um pacote chega a um nó antes de um período de transbordamento previsto, mas o próximo contato na rota só começa após o início desse transbordamento, a aresta que conecta esses dois contatos é proibida. Isso impede que o pacote fique "preso" no buffer do nó durante o período de capacidade zero.

C. Tabelas de Buffer de Previsão (Forecast Buffer Tables)

• O sistema mantém tabelas que rastreiam a carga reservada do buffer em cada nó ao longo do tempo. Essas tabelas são atualizadas globalmente sempre que uma rota é validada, permitindo que o algoritmo preveja o estado do buffer antes que os pacotes fisicamente cheguem.

D. Margem de Segurança (Safety Margin)

• Para lidar com imprevistos (como falhas de hardware ou erros de apontamento de antena), o sistema reserva uma fração da capacidade de contato e do buffer que não é alocada pelo roteamento de origem. Essa "margem de segurança" permite que nós intermediários realizem reroteamento local sem causar transbordamentos ou sobrecarga.

3. Contribuições Principais

1. Formulação Matemática (FEAP-CB): Definição formal do problema de encontrar o caminho de chegada mais cedo viável sob restrições de capacidade e buffer.
2. Prova de Otimalidade: O artigo prova matematicamente que o algoritmo proposto encontra a solução ótima (menor tempo de entrega) dentro do subconjunto de soluções viáveis, garantindo que nenhuma solução válida seja descartada indevidamente.
3. Gestão Proativa: Mudança de paradigma de uma gestão reativa (após o erro) para uma gestão preventiva (durante o cálculo da rota), eliminando colisões de capacidade e transbordamentos de buffer.
4. Algoritmo de Roteamento: Implementação de um CGR modificado que utiliza divisão de contatos e poda de arestas para garantir a viabilidade da rota antes da transmissão.

4. Resultados da Simulação

Os autores compararam sua solução com um benchmark de CGR padrão (roteamento de origem com verificação reativa) em cenários de constelações de satélites (Walker-delta) com 4, 8 e 16 satélites.

• Tempo Médio na Rede: A solução proposta reduziu significativamente o tempo que os pacotes permanecem na rede, especialmente sob alta carga (grande número de pacotes) e com buffers limitados.
  • Em cenários com buffer restrito (ex: 50 pacotes), o CGR padrão sofreu aumentos de atraso de até 2000% em comparação com a capacidade infinita, enquanto a solução proposta manteve um aumento de apenas 17%.
• Redução de Reroteamento: A solução proposta eliminou quase completamente a necessidade de reroteamento durante a fase de encaminhamento devido a falhas de capacidade ou buffer. O CGR padrão exigiu milhares de chamadas de reroteamento à medida que a carga aumentava.
• Complexidade Computacional: A divisão de contatos aumenta o tamanho do Grafo de Contatos (CP), mas o impacto é considerado baixo (menos de 10% de aumento no tamanho do CP mesmo sob alta carga), mantendo a complexidade do algoritmo de busca (Dijkstra) gerenciável.
• Robustez: A abordagem demonstrou ser superior em constelações maiores, onde a diversidade de rotas permite que o algoritmo encontre caminhos que evitam gargalos de buffer e capacidade.

5. Significado e Conclusão

Este trabalho estabelece uma base teórica sólida para o roteamento em redes espaciais futuras, como as comunicações cislunares (Programa Artemis) e constelações LEO massivas.

• Impacto Prático: Ao garantir que as rotas sejam viáveis antes da transmissão, o método economiza recursos críticos de satélites (energia e memória) e melhora a confiabilidade da entrega de dados.
• Limitações e Futuro: O estudo assume um cenário ideal com conhecimento perfeito da topologia e compartilhamento instantâneo de informações (solução centralizada). O trabalho futuro deve focar em soluções distribuídas, tolerância a informações imperfeitas/atrasadas e validação em simuladores de rede realistas (como ONE ou ION).

Em resumo, a proposta transforma o CGR de um algoritmo que apenas "tenta" encontrar rotas em um sistema que garante a viabilidade e a otimalidade das rotas, resolvendo um dos principais gargalos da comunicação em redes tolerantes a atrasos.