Tomada de Decisão e Enfileiramento

Até aqui, estudamos a arquitetura interna de um roteador — suas portas, o elemento de comutação e como a informação flui entre eles. Mas a pergunta essencial permanece: quando um pacote chega em uma porta de entrada, como o roteador decide para onde enviá-lo? E quando múltiplos pacotes chegam simultaneamente para a mesma porta de saída, qual é transmitido primeiro?

Este capítulo responde essas questões explorando a tomada de decisão no roteamento (encaminhamento baseado em prefixo) e a disciplina de enfileiramento (como gerenciar pacotes que competem pelos mesmos recursos).

Encaminhamento Baseado em Destino

O roteamento na Internet é baseado no endereço IP de destino do pacote. Cada roteador mantém uma tabela de roteamento que mapeia intervalos de endereços IPs (prefixos) para portas de saída.

Correspondência de Prefixo Mais Longo (Longest Prefix Match)

Imagine um roteador com a seguinte tabela de roteamento:

Agora um pacote chega com IP de destino 10.1.1.5. Qual interface deveria usar?

• Corresponde a 10.0.0.0/8? ✓ (caminho /8 = primeiros 8 bits)
• Corresponde a 10.1.0.0/16? ✓ (caminho /16 = primeiros 16 bits)
• Corresponde a 10.1.1.0/24? ✓ (caminho /24 = primeiros 24 bits)
• Corresponde a 10.1.2.0/24? ✗

O problema: múltiplas corresponências. Qual usar?

Solução: a regra de correspondência de prefixo mais longo (Longest Prefix Match — LPM). Escolha a entrada na tabela com o maior número de bits coincidentes — ou seja, o prefixo mais específico.

Para IP 10.1.1.5:

• 10.0.0.0/8: match nos primeiros 8 bits
• 10.1.0.0/16: match nos primeiros 16 bits
• 10.1.1.0/24: match nos primeiros 24 bits ← VENCEDOR

Resultado: enviar para a interface 2.

Visualizacao: decisao por prefixo mais longo (LPM)

A simulacao abaixo alterna destinos e mostra quais prefixos batem, destacando automaticamente a rota vencedora (a mais especifica).

Algoritmo de Busca em TCAM

A consulta da tabela de roteamento é a operação mais crítica — deve completar em nanosegundos para não atrasar pacotes. É por isso que roteadores usam TCAM (Ternary Content Addressable Memory).

Comparação: busca sequencial vs. TCAM

Estrutura da Tabela de Roteamento

Um roteador típico pode ter centenas de milhares de rotas. A tabela é organizada hierarquicamente para reduzir tamanho e melhorar o LPM:

Enfileiramento nas Portas de Entrada

Um roteador recebe pacotes continuamente de links de entrada. Até que cada pacote seja processado e comuado para uma porta de saída, ele aguarda em filas de entrada.

Cenários de Formação de Filas de Entrada

Uma fila de entrada se forma quando:

1. Múltiplos pacotes chegam simultaneamente de diferentes portas de entrada e todas querem sair pela mesma porta de saída.

   • Exemplo: 3 pacotes chegam em entradas diferentes, todos destinados a 10.2.0.0/16 (saída 1). Apenas um pode ser comuado por vez — os outros esperam.

2. A taxa de chegada em uma entrada excede a taxa de comutação (raro, mas possível em comutação via barramento).

3. Bloqueio de comutação — na comutação via crossbar, o HOL blocking força pacotes a esperarem nas filas de entrada.

Gerenciamento de Buffer de Entrada

Cada porta de entrada tem um buffer (memória) limitado para armazenar pacotes enquanto esperam comutação. Se o buffer enche:

Opção 1: Drop-Tail (Descarte de Cauda)

• Quando o buffer está cheio, descartar o novo pacote que chegar.
• Simples de implementar, mas abrupto — causa perdas sincronizadas em TCP.

Opção 2: Drop-Head

• Descartar o pacote mais antigo na fila quando buffer está cheio.
• Reduz latência para pacotes novos, mas antigos já esperaram em vão.

Opção 3: RED (Random Early Detection)

• Antes da fila encher, começar a descartar aleatoriamente pacotes com probabilidade crescente.
• Evita a queda abrupta e sincroniza melhor com controle de congestionamento TCP.

Visualizacao: contencao nas filas de entrada

Observe varias entradas gerando pacotes para a mesma saida. Como apenas um fluxo atravessa o fabric por vez, as filas de entrada crescem sob contencao.

Enfileiramento nas Portas de Saída

O enfileiramento de saída é muito mais crítico que o de entrada — é onde o verdadeiro gargalo ocorre.

Por Que Filas de Saída?

Considere um roteador com 4 portas de entrada (10 Gbps cada) e 1 porta de saída (10 Gbps):

• Taxa agregada de chegada: 4 × 10 Gbps = 40 Gbps
• Taxa de saída: 10 Gbps
• Deficit: 30 Gbps — o roteador recebe 3× mais dados que consegue transmitir!

Resultado: pacotes destinados àquela saída aguardam em uma fila de saída. Se a taxa agregada permanecer alta, a fila cresce indefinidamente, levando a:

• Aumento de latência (pacotes esperando mais tempo)
• Eventual descarte (buffer de saída fica cheio)

Visualizacao: gargalo de saida (4 entradas para 1 saida)

Nesta simulacao, a chegada agregada e maior que a taxa de transmissao de saida, entao a fila cresce continuamente e surgem descartes.

Políticas de Descarte

Similar às entradas, diferentes políticas gerenciam filas de saída:

Visualizacao: Drop-Tail vs RED

Compare lado a lado o comportamento do descarte abrupto (Drop-Tail) com o descarte gradual (RED) e como isso afeta a ocupacao das filas ao longo do tempo.

Disciplinas de Escalonamento (Scheduling)

Quando múltiplos pacotes aguardam em uma fila de saída, qual é transmitido primeiro? A disciplina de escalonamento (scheduling discipline) responde isso.

1. FIFO (First-In, First-Out)

O padrão mais simples: transmitir na ordem de chegada.

Problema: um único pacote grande (ou fluxo lento) pode bloquear pacotes de alta prioridade.

2. Escalonamento por Prioridade (Priority Scheduling)

Manter múltiplas filas, cada uma com uma prioridade. Sempre servir a fila de mais alta prioridade primeiro.

Algoritmo:

while (há pacotes):
    if (fila 1 não-vazia): enviar pacote de fila 1
    else if (fila 2 não-vazia): enviar pacote de fila 2
    else if (fila 3 não-vazia): enviar pacote de fila 3
    else if (fila 4 não-vazia): enviar pacote de fila 4

Vantagem: pacotes VoIP não sofrem latência de torrents.

Problema: starvation — filas de baixa prioridade podem nunca ser servidas se filas altas estão sempre ativas.

3. Round Robin (RR)

Alternar entre as filas: serve 1 pacote da fila 1, depois 1 da fila 2, depois 1 da fila 3, etc.

Vantagem: garante que todas as filas eventualmente recebem serviço — evita starvation.

Problema: trata todas as filas como iguais — uma fila com pacotes pequenos pode dominar o link.

4. Weighted Fair Queuing (WFQ)

Versão melhorada do Round Robin: servir filas com pesos (proporções) iguais a sua prioridade.

Exemplo com 3 filas:

Algoritmo (simplificado):

Manter um contador de "desvio" para cada fila.
Para cada slot de transmissão:
    - Incrementar desvio de cada fila pelo seu peso
    - Servir a fila com maior desvio
    - Decrementar seu desvio pelo tamanho do pacote enviado

Vantagem: oferece garantias de alocação — nenhuma fila pode ser completamente starved.

Desvantagem: complexidade maior — requer lógica sofisticada.

Comparação de Disciplinas

Visualizacao: comparador de disciplinas de escalonamento

Veja em paralelo como FIFO, Prioridade, Round Robin e WFQ escolhem o proximo pacote e como cada politica impacta equilibrio e latencia entre classes.

Interação entre Entrada e Saída

Na prática, o enfileiramento de entrada e saída interagem:

1. Um pacote chega em uma porta de entrada.

2. Consulta da tabela de roteamento → determina a porta de saída.

3. Se a fila de saída está cheia, o roteador pode:

   • Descartar o pacote (drop-tail na saída)
   • Descartar um pacote anterior (drop-head)
   • Tentar armazenar na entrada (push-back)

4. Se o pacote é armazenado, aguarda na fila de entrada até que a saída tenha espaço.

5. Uma vez comuado, o pacote aguarda na fila de saída até ser transmitido.

Exemplo Prático: Congestionamento

Um roteador recebe um surto de tráfego para a mesma saída:

Visualizacao: linha do tempo do congestionamento

A simulacao reproduz as fases da tabela (crescimento, RED ativo, reducao e estabilizacao), com metricas de fila e descarte em tempo real.

Resumo: Tomada de Decisão e Enfileiramento

A combinação desses mecanismos permite que roteadores modernos ofereçam confiabilidade, eficiência e qualidade de serviço mesmo sob cargas extremas.