Desafios e Comparação de Algoritmos

Até aqui, estudamos dois paradigmas fundamentais de roteamento: Link State (Dijkstra) e Distance Vector (Bellman-Ford). Ambos resolvem o mesmo problema (encontrar caminhos mais curtos), mas com estratégias radicalmente diferentes. Este capítulo final explora os desafios práticos que emergem quando esses algoritmos encontram redes reais — enlaces falhando, métricas mudando dinamicamente, e a necessidade de escala global.

Exploraremos:

1. Oscilações de Rota no Link State — quando a métrica muda, múltiplos caminhos podem ter custo igual, criando instabilidade
2. Contagem ao Infinito no Distance Vector — o problema clássico quando enlaces falham e como mitigá-lo
3. Comparação Prática: LS vs. DV — convergência, complexidade de mensagens, robustez, e quando usar cada um
4. Protocolos Reais — OSPF (Link State), RIP (Distance Vector), e BGP (híbrido com política)
5. Implicações para Internet — por que a Internet adota LS em domínios (OSPF) e política em AS (BGP)

Oscilações de Rota no Link State

O Problema: Múltiplos Caminhos Ótimos

No Dijkstra clássico, supomos métricas estáticas (ou quase). Mas em redes reais, a métrica pode ser dinâmica — por exemplo, usar como peso o inverso da capacidade disponível de um enlace.

Quando dois ou mais caminhos têm o mesmo custo, qual roteador deve escolher?

Cenário: Rede com 3 roteadores: A (origem), B e C (intermediários), D (destino)

Se todo tráfego escolhe B→D porque foi computado primeiro, link B-D fica congestionado. Sua capacidade cai. Métrica muda dinamicamente:

• Agora: B-D = 10 (congestionado)
• Custo A → B → D = 1 + 10 = 11
• Custo A → C → D = 1 + 1 = 2 ← Melhor!

Todos mudam para C→D. Agora C-D fica congestionado...

Loop de Oscilação: Tráfego alterna infinitamente entre B→D e C→D, nunca estabilizando.

Visualizacao Interativa: Oscilacao de Rotas

Use Play/Pause para acompanhar como o custo muda em tempo real e observe a alternancia entre os dois caminhos.

Por que Link State é Vulnerável?

Soluções Práticas

1. Métricas Estáticas ou Lentamente Variáveis

OSPF típico usa:

• Capacidade (Mbps): 10^8 / largura_banda. Não muda frequentemente.
• Atraso: medição periódica (não instantânea).

Resultado: Métrica estável → Dijkstra estável → sem oscilação.

2. Damping (Amortecimento) de Mudanças

Não recomputar imediatamente quando métrica muda. Esperar interval (ex: 5 segundos) antes de re-publicar:

t=0s: Métrica muda (B-D: 1 → 10)
t=0s: Roteador B detecta, ESPERA
t=5s: Se métrica ainda está 10, publica "B-D agora custa 10"
      Todos recalculam e mudam rota
t=10s: Se métrica voltou para 1 no meio do intervalo, muda é IGNORADA (amortecida)

Resultado: Menos oscilação; mudanças legítimas levam tempo para propagar.

3. Múltiplos Caminhos (Multipath Routing)

Em vez de usar um caminho ótimo, distribuir tráfego entre vários caminhos com custo similar (ex: A→B→D com 50%, A→C→D com 50%).

Benefício: Se B-D fica congestionado, tráfego em B-D é apenas metade do total → menos pico de congestionamento.

Trade-off: Tráfego fora de ordem (chegada em diferentes tempos).

Visualizacao Interativa: Multipath Adaptativo

Alterne entre modo adaptativo e caminho unico para observar a diferenca de estabilidade.

Contagem ao Infinito no Distance Vector

Revisão: Problema Clássico

Já vimos no capítulo anterior que quando um enlace falha, DV pode levar O(N) iterações para reconhecer. Vamos aprofundar e explorar soluções.

Cenário: Rede linear R1 — R2 — R3 — R4 — R5 (cada enlace custa 1)

Evento: Enlace R4-R5 falha (quebrado fisicamente).

t=0: R4 detecta falha. Marca D_4[5] = ∞

t=1: R4 envia atualização aos vizinhos:

• Informa R3: "R5 está ∞ para mim"
• Mas R3 ainda tem D_3[5] = 2 (via R4 — informação antiga)
• R3 aplica Bellman-Ford: D_3[5] = min(D_4[5] + 1) = min(∞ + 1) = ∞
  • Wait! R3 só tem R4 como vizinho para R5 (topologia linear)
  • Então D_3[5] atualiza corretamente para ∞

Mas o problema ocorre com topologia diferente:

Cenário 2 (com loop): Rede em triângulo: R1 — R2 — R3, com R1 — R3 também.

Evento: Enlace R1-R3 falha.

t=0: R1 detecta falha. D_1[3] = ∞

t=1:

• R1 envia aos vizinhos: "R3 é ∞"
• R2 recebe de R1: D_1[3] = ∞
• R2 recalcula: D_2[3] = min(D_1[3] + custo(2,1)) = min(∞ + 1) = ∞
  • Correto! R2 já sabe que via R1 não funciona.

Problema com topologia real (rede em árvore com loops implícitos):

Suponha: R1 — R2 — R3 — R4 (linear), mas R2 também aprende de outro vizinho R1.5:

Enlace R3-R4 falha.

t=0: R3 marca D_3[4] = ∞

t=1:

• R3 informa R2 e R1.5: "R4 é ∞"
• R2 ainda tem D_2[4] = 1 (via R3) — ANTIGO
• R2 calcula: D_2[4] = min(D_3[4] + 1, ...) = ∞
• Mas se R1.5 informar primeiro: D_1.5[4] = 2 (via R3, também antigo!)
• R2 recebe de R1.5: D_1.5[4] + custo(2, 1.5) = 2 + 1 = 3
• R2 pensa: "Ótimo! Posso chegar R4 via R1.5 com custo 3" → D_2[4] = 3

t=2:

• R2 informa R1.5: "R4 é 3 para mim"
• R1.5 pensa: "Ah! Posso chegar R4 via R2 com custo 3 + 1 = 4" → D_1.5[4] = 4

t=3: R1.5 informa R2: "R4 é 4 para mim"

• R2: "Via R1.5 = 4 + 1 = 5" → D_2[4] = 5

Pattern: 3 → 4 → 5 → 6 → ... → ∞

Quantidade de Iterações: Se rede tem N nós, pode levar até N − 1 iterações (ou mais com caminhos fantasma).

Visualizacao Interativa: Count-to-Infinity

Compare os modos com e sem Split Horizon. No modo sem protecao, os custos sobem progressivamente ate inf.

Split Horizon com Poison Reverse

Ideia: Se um roteador aprendeu uma rota via um vizinho, nunca informa esse vizinho sobre essa rota (ou informa como ∞ — "poison").

Pseudocódigo:

Para cada destino d:
  Para cada vizinho v:
    Se "d foi aprendido via v":
      Informa v: D_x[d] = ∞
    Senão:
      Informa v: D_x[d] = (valor normal)

Aplicado ao Exemplo:

t=1: R3 falha na comunicação R3-R4.

• R3 marca D_3[4] = ∞
• R3 informa R2: "D_3[4] = ∞"
• R3 informa R1.5: "D_3[4] = ∞" (Mas R3 aprendeu de R1.5? Não — R4 é vizinho direto)

t=2:

• R2 recebe de R3: D_3[4] = ∞ → D_2[4] = min(∞ + 1, ...) = ∞ (corrigindo!)
• R1.5 recebe de R3: D_3[4] = ∞ → D_1.5[4] = ∞

Convergência em 1 iteração! Sem loop.

Por que funciona: Quebra loops simples. Mas não resolve loops longos (A→B→C→A) — esses ainda podem causar contagem ao infinito (mais lentamente).

RIP: Máximo de 15 Saltos

Protocolo RIP (Distance Vector legado) usa solução drástica:

D_x[d] > 15 = ∞ (destino inacessível)

Impacto: Redes maiores que 15 saltos são impossíveis em RIP — força limite.

Razão: Evitar contagem ao infinito levando anos. Com limite 15, pior caso = 15 iterações.

Comparação Prática: Link State vs. Distance Vector

Tabela Comparativa Detalhada

Cenários de Uso

1. Link State (OSPF) — Quando Usar

• Rede média a grande (>50 roteadores)
• Métricas estáveis (não mudam a cada segundo)
• Convergência rápida é crítica
• Suporte a hierarquia (OSPF areas) é necessário

Exemplo: Rede de ISP com 1000 roteadores regionais. Uma falha deve se recuperar em segundos (convergência rápida), não minutos.

2. Distance Vector (RIP) — Quando Usar

• Rede pequena (<15 roteadores)
• Simplicidade é prioridade (roteadores com recursos limitados)
• Educacional — entender conceitos distribuídos

Exemplo: Rede corporativa pequena com 5 roteadores. Implementação simples, sem necessidade de state completo.

Exemplo Prático: Recuperação após Falha

Cenário: Enlace crítico falha. Como cada algoritmo se recupera?

Topologia: R1 — R2 — R3 — R4, com R2 — R4 também (para redundância)

Visualizacao Interativa: OSPF vs RIP

A comparacao lado a lado destaca a diferenca de convergencia apos a mesma falha de enlace.

OSPF: ~300ms para convergência (rápido, prático)

RIP: ~3s para convergência (lento, perceptível para usuários)

Protocolos Reais: OSPF, RIP e BGP

OSPF (Open Shortest Path First)

Baseado em: Link State + Dijkstra

Características:

• Suporta áreas hierárquicas para escalabilidade (ex: area 0 = backbone, areas 1-65535 = periféricas)
• Métrica configurável: custo = 10^8 / largura_banda (Mbps)
• Convergência rápida (< 1 segundo típico)
• Usado em: ISPs, redes corporativas, centros de dados

Exemplo de Hierarquia (OSPF Areas):

Routers na fronteira de áreas (ABRs) correm Dijkstra por área + cálculo inter-área. Reduz overhead.

RIP (Routing Information Protocol)

Baseado em: Distance Vector + Bellman-Ford

Características:

• Máximo 15 saltos (limite forte)
• Métrica = número de saltos (cada link = 1)
• Simples, mas obsoleto (convergência lenta, falta escala)
• Usado em: Legado; laboratórios educacionais

Histórico: Usado nos primórdios da Internet (1980s-1990s). Substituído por OSPF.

BGP (Border Gateway Protocol)

Tipo: Híbrido (Policy-based, não apenas métrica)

Características:

• Roteamento entre domínios autônomos (AS) — Internet backbone
• Não é puramente Link State ou DV; é policy-driven
• Rastreia caminho completo (AS_PATH) — sequência de AS pelo qual o prefixo passou
• Permite filtragem de rotas por política (ex: "não rotear via rival, mesmo se mais curto")
• Convergência: ~15-30 segundos típico

Exemplo:

BGP é não-determinístico em relação a métrica — política administrativa prevalece.

Implicações para Internet: Por que LS Interior, Política em Exterior

A Internet é organizada em domínios autônomos (AS), cada um controlado por uma organização (ISP, universidade, etc.).

Dentro de um AS (Interior Gateway Protocol — IGP)

• Use Link State (OSPF, IS-IS) — convergência rápida, escalável
• Métrica técnica (capacidade, latência)
• Objetivo: melhor desempenho

Entre AS (Exterior Gateway Protocol — EGP)

• Use BGP — permite política comercial
• Rastreamento de caminho + filtragem manual
• Objetivo: controle político (ex: não rotear via concorrente, mesmo que mais curto)

Por que não usar Link State entre AS?

Se cada ISP publicasse sua topologia completa globalmente, seria:

1. Problema de privacidade — concorrentes conheceriam capacidade exata de cada link
2. Escalabilidade impossível — Dijkstra com 60k+ nós da Internet = impraticável
3. Perda de flexibilidade — não poderíamos aplicar política (BGP permite isso)

Resumo: Desafios e Escolhas

1. Link State Oscilação: Mitigar com métricas estáveis, damping e multipath

2. Distance Vector Contagem ao Infinito: Usar Split Horizon com Poison Reverse + máximo de saltos

3. Escolha Prática:

• Interior (um domínio): Link State (OSPF) — rápido, escalável
• Exterior (entre domínios): BGP (política-driven) — controle, privacidade

4. Internet Real: Combinação — OSPF dentro de ISP + BGP entre ISPs

Questões Desafio

1. Como oscilação de rota ocorre em Link State? Que métricas dinâmicas causam maior risco?
2. Split Horizon resolve todos os casos de contagem ao infinito? E loops de 3+ nós?
3. Por que RIP limita-se a 15 saltos, e qual é a desvantagem?
4. Se OSPF é mais rápido que RIP, por que RIP ainda é ensinado?
5. BGP não escolhe "caminho mais curto" — escolhe por política. Como isso afeta confiabilidade de rede?
6. Você implementaria um novo protocolo de roteamento hoje? Qual seria sua abordagem?