Algoritmos de Roteamento

Algoritmos de roteamento calculam os caminhos que os pacotes seguem através de uma rede, tipicamente encontrando rotas de menor custo sobre um grafo de roteadores e links, usando uma visão global do estado do link ou um cálculo distribuído de vetor de distância, vizinho por vizinho.

Definition

Um algoritmo de roteamento é um procedimento que determina os caminhos de menor custo (ou de outra forma preferidos) através de uma rede modelada como um grafo ponderado, produzindo as decisões de encaminhamento que os roteadores usam para mover pacotes em direção aos seus destinos.

Scope

Este tópico abrange os algoritmos que preenchem as tabelas de encaminhamento: o modelo de grafo de uma rede com custos de link; roteamento de estado de link usando o algoritmo de caminho mais curto de Dijkstra com uma topologia globalmente compartilhada; roteamento de vetor de distância usando o cálculo distribuído de Bellman-Ford com trocas entre vizinhos; seu comportamento de convergência e patologias, como o problema de contagem até o infinito; e roteamento hierárquico para escalabilidade. Ele trata os algoritmos de forma abstrata, deixando os protocolos concretos (OSPF, RIP, BGP) e sua organização intra/interdomínio para o tópico de protocolos de roteamento.

Core questions

• Como uma rede é modelada como um grafo ponderado para roteamento?
• Como um algoritmo de estado de link calcula os caminhos mais curtos a partir de uma visão completa da topologia?
• Como um algoritmo de vetor de distância converge usando apenas trocas entre vizinhos?
• Quais são os problemas de convergência e estabilidade, como a contagem até o infinito, e como são mitigados?
• Por que o roteamento é hierárquico e como isso afeta a otimalidade do caminho?

Key concepts

• grafo de rede ponderado
• caminhos de menor custo
• roteamento de estado de link
• algoritmo de Dijkstra
• roteamento de vetor de distância
• equação de Bellman-Ford
• problema de contagem até o infinito
• horizonte dividido e reverso envenenado
• roteamento hierárquico

Key theories

Roteamento de estado de link (Dijkstra)

Cada roteador inunda seus custos de link para que todos os roteadores compartilhem a topologia completa, então executa independentemente o algoritmo de Dijkstra para calcular os caminhos mais curtos; isso converge rápida e previsivelmente, mas requer troca de informações globais.

Roteamento de vetor de distância (Bellman-Ford)

Os roteadores trocam suas estimativas atuais de menor custo para cada destino com seus vizinhos e atualizam via equação de Bellman-Ford; o cálculo é distribuído e usa apenas informações locais, mas pode convergir lentamente e sofrer de contagem até o infinito.

Roteamento hierárquico

Como o roteamento plano não escala para toda a Internet, os roteadores são agrupados em regiões (sistemas autônomos) com roteamento tratado localmente dentro de cada região e sumarizado entre elas, trocando alguma otimalidade de caminho por escalabilidade e autonomia administrativa.

Clinical relevance

Os algoritmos de roteamento determinam a eficiência e a confiabilidade do fluxo de tráfego: algoritmos de estado de link sustentam protocolos internos como o OSPF, que convergem rapidamente após falhas, enquanto as ideias de vetor de distância aparecem no RIP e na abordagem de vetor de caminho do BGP. Compreender seu comportamento de convergência é essencial para projetar redes estáveis e diagnosticar loops de roteamento e recuperação lenta após falhas de link ou roteador.

History

Os algoritmos de caminho mais curto, no cerne do roteamento, são anteriores às redes de computadores: o trabalho de Bellman e Ford sobre problemas de roteamento no final da década de 1950 e o algoritmo de caminho mais curto de Dijkstra de 1959. À medida que as redes de pacotes cresceram, estes foram adaptados para roteamento de vetor de distância e estado de link, e a estruturação hierárquica em sistemas autônomos tornou o roteamento escalável para a Internet global.

Debates

Roteamento de estado de link versus vetor de distância

O roteamento de estado de link converge rapidamente e evita a contagem até o infinito, mas exige que cada roteador mantenha a topologia completa e faça mais cálculos, enquanto o vetor de distância é mais simples e mais local, mas pode convergir lentamente e formar loops transientes; redes reais combinam ambas as ideias em diferentes escalas.

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford

Seminal works

• dijkstra1959
• bellman1958
• kurose2021

Frequently asked questions

O que é o problema de contagem até o infinito?

É uma patologia de vetor de distância em que, após uma falha de link, os roteadores aumentam lentamente suas estimativas de distância para um destino inalcançável, trocando informações desatualizadas, acreditando erroneamente que um caminho ainda existe através um do outro. As mitigações incluem horizonte dividido, reverso envenenado e limitação da distância máxima.

Por que são usados tanto o estado de link quanto o vetor de distância?

Eles se adequam a diferentes escopos. Protocolos de estado de link como o OSPF proporcionam convergência rápida e sem loops dentro de um único domínio administrativo onde o compartilhamento da topologia completa é aceitável. Abordagens de vetor de distância e vetor de caminho escalam melhor e revelam menos detalhes internos entre domínios, razão pela qual o BGP usa um design de vetor de caminho entre redes.