Uma rota estática é uma instrução; um protocolo de roteamento dinâmico é uma conversa. Os roteadores contam uns aos outros quais redes conseguem alcançar e mudam a resposta quando um link cai ou quando aparece uma rede nova. A 1812 (junho de 1995), que reúne os requisitos para roteadores IPv4, lista o que um protocolo interno deve conseguir fazer: "(1) Respond quickly to changes in the internal topology of an AS", "(2) Provide a mechanism such that circuit flapping does not cause continuous routing updates", "(3) Provide quick convergence to loop-free routing", "(4) Utilize minimal bandwidth", "(5) Provide equal cost routes to enable load-splitting" e "(6) Provide a means for authentication of routing updates" (RFC 1812, seção 7.2.1). As famílias de protocolos que vêm a seguir são respostas diferentes para essa mesma lista, e o que cada uma ganha de um lado ela paga do outro.
Protocolos internos e externos
A RFC 1812 começa separando dois mundos: "Interior gateway protocols (IGPs) are used to distribute routing information within an AS (i.e., intra-AS routing). Exterior gateway protocols are used to exchange routing information among ASs (i.e., inter-AS routing)" (RFC 1812, seção 7.1). Um sistema autônomo (AS, autonomous system) é uma rede sob uma única administração, e o guia de BGP explica o conceito. Em 1995, a RFC reconhecia dois tipos de protocolo interno, os de distance vector (vetor de distância) e os de link state (estado de enlace): "Current IGPs used in the internet today are characterized as either being based on a distance-vector or a link-state algorithm" (como acima). Para o roteamento entre sistemas autônomos, o trouxe um terceiro tipo, o path vector (vetor de caminho); e o , da Cisco, trouxe um aperfeiçoamento do primeiro.
Distance vector: cada roteador conta aos vizinhos o que sabe
O Routing Information Protocol () é o exemplo clássico: "RIP is a routing protocol based on the Bellman-Ford (or distance vector) algorithm" (RFC 2453). Cada roteador mantém "a table with an entry for every possible destination in the system", com "the distance D to the destination, and the first router G on the route to that network"; periodicamente, manda essa tabela para todos os vizinhos; e, quando chega a atualização de um vizinho, soma o custo do link por onde ela veio e adota qualquer destino que tenha ficado mais perto (RFC 2453, seção 3.4). Ou seja, o roteador sabe a que distância está cada destino e para qual vizinho entregar o pacote, o next hop (o próximo salto). Não sabe nada do caminho depois desse vizinho.
A ideia é mais antiga que a internet. A RFC 2453 associa o método à equação de Bellman e a Ford e Fulkerson, lembra que "The basic algorithms used by this protocol were used in computer routing as early as 1969 in the " e que "the specific ancestry of this protocol is within the Xerox network protocols": o Gateway Information Protocol, do PUP da Xerox; o Routing Information Protocol, do Xerox Network Systems (); e, depois, o routed, o programa do de Berkeley de onde saíram os formatos de pacote do RIP (RFC 2453, seção 3.1). O RIP foi documentado pela primeira vez na RFC 1058, escrita por C. Hedrick, da Rutgers University, em junho de 1988 (RFC 1058); a versão 2, que transporta as máscaras de sub-rede, é a RFC 2453, de novembro de 1998, o Internet Standard 56.
Os números do RIP são pequenos e fixos. Todo roteador "sends an update message to all its neighbors once every 30 seconds"; se um vizinho fica 180 segundos em silêncio, as rotas que passam por ele são marcadas como inválidas; e "16 is used" como "infinity", ou seja, como a métrica que significa destino inalcançável, o que limita o RIP "to networks whose longest path (the network's diameter) is 15 hops" (RFC 2453, seções 3.2 e 3.4.1). A especificação é franca quanto aos próprios limites: "RIP was designed to work as an in moderate-size AS's. It is not intended for use in more complex environments" (seção 3.1).
O problema do count to infinity
O ponto fraco do distance vector é que o roteador acredita no que os vizinhos dizem sobre rotas que eles podem ter aprendido com ele mesmo. Imagine dois roteadores, B e C, com uma rede N atrás de C. C alcança N com métrica 1, e B, passando por C, com métrica 2. Então o link entre C e a rede N cai. Se a próxima atualização periódica de B chegar a C antes que C consiga avisar B da queda, C recebe de B o anúncio "N: 2" e adota essa rota com métrica 3, via B. Só que a rota de B para N passa por C, e a regra do RIP manda aceitar a atualização do roteador que a rota já usa "even if it is larger than the old one" (seção 3.4); então B vai para 4, depois C vai para 5, e assim por diante:
| Momento | Métrica de C para N | Métrica de B para N |
|---|---|---|
| Logo após a falha, antes de qualquer atualização | inalcançável | 2, via C |
| C ouve B | 3, via B | 2 |
| B ouve C | 3 | 4, via C |
| C ouve B | 5 | 4 |
| B ouve C | 5 | 6 |
| ... e assim até | 16, inalcançável | 16, inalcançável |
Enquanto isso, os pacotes para N ficam indo e voltando entre B e C. A RFC 2453 chama esse padrão de "mutual deception" (engano mútuo) e a subida lenta de "counting to infinity", a contagem até o infinito, e explica por que o infinito do RIP é só 16: "the choice of infinity is a tradeoff between network size and speed of convergence in case counting to infinity happens" (seções 3.4.2 e 3.4.3).
Três técnicas tornam o problema raro, mas não impossível. Split horizon: "The 'simple split horizon' scheme omits routes learned from one neighbor in updates sent to that neighbor", ou seja, B nunca falaria de N para C. Poisoned reverse: esse esquema "includes such routes in updates, but sets their metrics to infinity", um jeito explícito de dizer "por aqui, não". Triggered updates (atualizações disparadas): o roteador cuja métrica muda envia uma atualização "almost immediately, even if it is not yet time for one of the regular update message" (seções 3.4.3 e 3.4.4). As duas primeiras técnicas evitam loops entre dois roteadores, mas não entre três: "A may believe it has a route through B, B through C, and C through A. Split horizon cannot stop such a loop". Os triggered updates apostam corrida com as atualizações periódicas, e a palavra final da RFC é que "counting to infinity is still possible" (seção 3.4.4). A RFC 1812 tornou obrigatório o mínimo: uma implementação de RIP "MUST implement split horizon" e "SHOULD implement Split horizon with poisoned reverse" (RFC 1812, apêndice F.2).
Link state: todo roteador recebe o mapa completo
O Open Shortest Path First () seguiu de propósito pelo outro caminho: "The OSPF protocol is based on link-state or technology. This is a departure from the Bellman-Ford base used by traditional internet routing protocols" (RFC 2328, seção 1). Em vez de distâncias, cada roteador descreve apenas a si mesmo, os próprios links e os vizinhos, e "distributes its local state throughout the Autonomous System by flooding" (o flooding, a inundação da rede com essa descrição); o resultado é que "Each participating router has an identical database". Depois, "All routers run the exact same algorithm, in parallel. From the link-state database, each router constructs a tree of shortest paths with itself as root" (RFC 2328, seção 1.1). O algoritmo é o de Dijkstra, e o artigo sobre Dijkstra conta como ele foi concebido em vinte minutos, no terraço de um café.
Como cada roteador calcula as próprias rotas a partir do mapa inteiro, nenhum deles depende das conclusões de um vizinho, e o boato que alimenta o count to infinity não tem por onde começar. O OSPF "quickly detects topological changes in the AS (such as router interface failures) and calculates new loop-free routes after a period of convergence", um período que "is short and involves a minimum of routing traffic" (seção 1.1). O preço é que cada roteador guarda o mapa e faz o cálculo sozinho, e, quando a rede cresce, a saída é a hierarquia: as áreas, cuja topologia "is hidden from the rest of the Autonomous System", o que "enables a significant reduction in routing traffic" (como acima). O guia de OSPF explica as áreas e os custos.
O é da mesma família, só que vem do mundo OSI. A RFC 1812 cita o título formal dele, "Intermediate System to Intermediate System Routeing Exchange Protocol", com Routeing escrito assim mesmo, e diz que ele "is based on a link-state (SPF) routing algorithm and shares all the advantages for this class of protocols" (RFC 1812, seção 7.2.3). A RFC 1195, escrita por R. Callon, da Digital Equipment Corporation, em dezembro de 1990, adaptou o protocolo para que ele "may be used as an interior gateway protocol (IGP) to support TCP/IP as well as OSI" (RFC 1195); o guia de IS-IS explica onde ele ainda roda.
A de 1995 deixou bem clara a sua preferência: "A router that implements any routing protocol (other than static routes) MUST IMPLEMENT OSPF" (RFC 1812, seção 7.2.1). No mesmo documento, os requisitos para filtrar informação de roteamento "apply only to non-SPF-based protocols" (seção 7.5); no link state, todo roteador de uma área tem, de propósito, a mesma base de dados.
Path vector: a rota carrega o caminho, não só a distância
Entre sistemas autônomos, só a distância não basta: o operador precisa saber por redes de quem a rota passa. O Border Gateway Protocol (BGP) "uses an algorithm that is neither a pure distance vector algorithm or a pure link state algorithm. Instead, it uses a modified distance vector algorithm, referred to as a 'Path Vector' algorithm", que "uses path information to avoid traditional distance vector problems" (RFC 4274, seção 2.2). O nome foi escolhido para ecoar o do distance vector: "The term ' protocol' bears an intentional similarity to the term 'distance-vector protocol'" (RFC 1322).
Cada rota BGP carrega "the list of Autonomous Systems (ASes) that reachability information traverses", o suficiente para "constructing a graph of AS connectivity for this reachability, from which routing loops may be pruned" (RFC 4271, seção 1). O teste de loop é mecânico: "AS loop detection is done by scanning the full AS path (as specified in the AS_PATH attribute), and checking that the autonomous system number of the local system does not appear in the AS path" (RFC 4271, seção 9.1.2). Uma rota cujo AS path já contém o AS do próprio roteador fica fora da seleção, e por isso a contagem que atormenta o distance vector nem começa.
No BGP, a escolha é uma questão de política, não de distância: o processo de decisão "selects routes for subsequent advertisement by applying the policies in the local Policy Information Base (PIB)" (seção 9.1), e um AS "advertises to its neighbor ASs only those routes that it itself uses" (RFC 1812, seção 7.3.2.1). O BGP também não tem pressa, e isso é deliberado: depois da troca inicial, "a pair of BGP routers exchanges only the changes to that information" (RFC 4274, seção 2.2), e o intervalo mínimo sugerido entre anúncios para o mesmo destino é de 30 segundos para um peer externo e de 5 segundos para um interno (RFC 4271, seção 10). O guia de BGP explica os atributos, e o artigo sobre o problema de confiança do BGP mostra o que acontece quando um AS anuncia o que não é verdade.
DUAL: distance vector sem loops
O Enhanced Interior Gateway Routing Protocol (EIGRP) manteve o modelo distance vector e eliminou a falha central dele. A especificação do protocolo, a RFC informativa 7868, de maio de 2016, "Cisco's Enhanced Interior Gateway Routing Protocol (EIGRP)", descreve o EIGRP como "a routing protocol based on Distance Vector technology" cujo algoritmo é o DUAL, o Diffusing Update Algorithm, que saiu de pesquisas do SRI International (RFC 7868). A promessa do DUAL é forte: ele "guarantees that each constructed path is loop free at every instant including periods of topology changes and network reconvergence" (seção 3).
O mecanismo é um teste que o roteador aplica antes de acreditar num vizinho. Um vizinho atende à feasibility condition (condição de viabilidade) "if the neighbor's RD is less than this router's Feasible Distance": a distância que o vizinho anuncia, a reported distance (RD), é menor que a melhor distância que este roteador já teve, e por isso o caminho dele não tem como voltar passando por este roteador. Um vizinho assim é um feasible successor (sucessor viável), "providing a guaranteed loop-free path" (seção 2.2). Enquanto houver um feasible successor oferecendo o melhor caminho restante, a rota continua utilizável; só quando não houver nenhum o roteador precisa "coordinate with its neighbors in the search for the new loop-free least-total-cost path" (seção 3.2), e, mesmo assim, só participam os roteadores afetados pela mudança: "Routers that are not affected by topology changes are not involved in the recalculation" (seção 3).
Lado a lado
| Família | Protocolos | O que um roteador ouve | O que ele calcula | Como evita loops |
|---|---|---|---|---|
| Distance vector | RIP (RFC 2453) | A distância de cada vizinho até cada destino | A menor distância e o primeiro hop, somando o custo do link | Split horizon, poisoned reverse, triggered updates; o infinito em 16 limita a contagem |
| Link state | OSPF (RFC 2328), IS-IS (RFC 1195) | Os links de cada roteador, distribuídos por flooding na área | Uma shortest-path tree (árvore de caminhos mais curtos) com ele mesmo como raiz | Todos os roteadores calculam a partir da mesma base de dados |
| Path vector | BGP (RFC 4271) | Rotas acompanhadas da lista de sistemas autônomos por onde passaram | A rota preferida, pelos atributos e pela política local | A rota que traz o AS do próprio roteador na lista é rejeitada |
| DUAL | EIGRP (RFC 7868) | As distâncias informadas pelos vizinhos | Successors e feasible successors | A feasibility condition |
Quanto tempo cada um leva para perceber uma falha
Nenhum protocolo reage a uma falha que ainda não percebeu. No RIP, o padrão é lento de propósito: as implementações "MUST by default wait six times the update interval before invalidating a route" (RFC 1812, apêndice F.2), ou seja, 180 segundos com o intervalo de 30 segundos do RIP, antes que qualquer contagem comece. Nos protocolos link state, a mudança chega por flooding a todos os roteadores da área, e cada um refaz o cálculo; a especificação do EIGRP afirma que "The convergence time with DUAL rivals that of any other existing routing protocol" (RFC 7868, seção 3); e o BGP troca velocidade por estabilidade com os intervalos entre anúncios. Todos dependem, antes de mais nada, de perceber a falha, e esse é o problema de que trata o artigo sobre o BFD.
Quando um roteador roda mais de um desses protocolos, as respostas de cada um para o mesmo prefixo são comparadas pela administrative distance (distância administrativa), explicada no artigo sobre rotas estáticas e longest match; passar rotas de um protocolo para outro é a redistribuição, que tem um artigo só para ela e também os seus próprios loops.
Para lembrar
- Os protocolos internos roteiam dentro de uma mesma administração; o BGP roteia entre administrações diferentes.
- Distance vector: os roteadores trocam distâncias com os vizinhos e só conhecem o next hop; o RIP manda atualizações a cada 30 segundos e conta até 16.
- O count to infinity é o preço de acreditar nos vizinhos; split horizon, poisoned reverse e triggered updates tornam o problema raro, mas não impossível.
- Link state: cada roteador faz o flooding dos próprios links e calcula sozinho a árvore inteira; o OSPF e o IS-IS escalam com o uso de áreas e níveis.
- Path vector: o BGP carrega a lista de sistemas autônomos e rejeita as rotas em que o próprio AS já aparece.
- O DUAL, do EIGRP, só aceita um caminho de backup quando a feasibility condition prova que ele não tem loop.
Fontes
- RFC 1812, Requirements for IP Version 4 Routers, junho de 1995: seções 7.1 a 7.5 sobre protocolos internos e externos, apêndice F.2 sobre o RIP (lida em 2026-10-07)
- RFC 1058, Routing Information Protocol, C. Hedrick, junho de 1988 (lida em 2026-10-07)
- RFC 2453, RIP Version 2, novembro de 1998, STD 56: o algoritmo, a sua ascendência, os temporizadores, o infinito, o split horizon e as atualizações disparadas (lida em 2026-10-07)
- RFC 2328, OSPF Version 2, abril de 1998, STD 54: estado de enlace, inundação, a árvore de caminhos mais curtos, áreas (lida em 2026-10-07)
- RFC 1195, Use of OSI IS-IS for Routing in TCP/IP and Dual Environments, dezembro de 1990 (lida em 2026-10-07)
- RFC 4271, A Border Gateway Protocol 4 (BGP-4), janeiro de 2006: AS path, detecção de loops, processo de decisão, temporizadores (lida em 2026-10-07)
- RFC 4274, BGP-4 Protocol Analysis, janeiro de 2006: o algoritmo de vetor de caminho e as atualizações incrementais (lida em 2026-10-07)
- RFC 1322, A Unified Approach to Inter-Domain Routing, maio de 1992: o nome vetor de caminho (lida em 2026-10-07)
- RFC 7868, Cisco's Enhanced Interior Gateway Routing Protocol (EIGRP), maio de 2016: o DUAL, a condição de viabilidade, os sucessores viáveis (lida em 2026-10-07)