A tabela não é uma árvore
Escrevi três regras para desenhar o grafo de AS antes de ter medido um único. Uma tabela cheia de verdade acabou com as três.
Michel Wijnberg
Os doze primeiros artigos apoiavam-se numa vantagem: dentro de um sistema autônomo, os roteadores são o oráculo. Diga o modelo o que disser, dá para ir perguntar ao equipamento. Até os caminhos entre AS do artigo três ficavam dentro de redes onde eu conseguia entrar. Esta série é sobre o que acontece quando isso deixa de estar disponível, porque o assunto são as redes dos outros.
Uma tabela BGP não é uma imagem da internet. É uma imagem da internet a partir de onde você está, e quase tudo o que um operador conclui dela é condicionado por esse ponto de observação de maneiras que ninguém rotula. Quatro artigos sobre como é de fato uma tabela real, começando pela pergunta mais básica que qualquer um que construa uma visão de AS precisa responder:
Como se desenha isso?
Respondi a essa pergunta num documento de projeto antes de ter medido coisa alguma. Três regras, escritas com confiança. As três se revelaram falsas, e o modo como falharam é mais interessante do que as regras eram.
As três regras que escrevi
A visão de fluxo de AS do Osprey põe o seu próprio AS no centro e distribui todo o resto em volta por distância. O projeto fixava três propriedades:
| # | Regra | O que ela assumia |
|---|---|---|
| 1 | O horizonte de observação é um anel | Além de certa distância, o grafo acaba |
| 2 | A largura do setor equivale à fatia de massa | Cada AS tem um predecessor, então o disco se reparte limpo |
| 3 | Origins são folhas (implícito) | O tráfego nasce na borda e transita no meio |
Primeiro uma palavra, porque ela decide como o resto se lê. “Predecessor” e “pai” são termos meus de renderização, não algo que o BGP anuncie. Um AS_PATH é uma sequência ordenada; não diz nada sobre hierarquia. O que chamo de predecessor é o AS um passo mais perto do ponto de observação ao longo de um caminho que realmente recebi. Essa relação é construída por quem olha, a partir da posição de quem olha, e é aí que está o argumento inteiro.
A regra 2 é a que sustenta a carga. Se cada AS alcança você por exatamente um predecessor, o grafo é uma árvore, e uma árvore pode ser desenhada como setores aninhados em que largura significa volume. Toda representação hierárquica de um grafo BGP que você já viu repousa sobre essa suposição, normalmente sem dizê-lo.
Então medi uma de verdade.
O que diz uma tabela cheia
Uma tabela IPv4 cheia: 1.071.538 melhores caminhos entre 79.168 AS que aparecem em algum ponto de um caminho, um ponto de observação com dois upstreams. (Os AS de origem são menos, 78.538; as duas contagens são perguntas diferentes e ambas voltam nesta série.) Ao lado, DN42, uma rede inteiramente à parte e uma ordem de grandeza menor. As duas medidas, as duas contra o mesmo código.
| Suposição | DN42 | Tabela cheia | Veredito |
|---|---|---|---|
| Um predecessor por AS | 258 de 1.138 com vários, máx. 29 | 22.371 de 79.168 (28,3%), máx. 202 predecessores | falsa |
| A massa de borda chega pelo pai mais pesado | 18,3% não | 17,5% não | falsa |
| Sem ciclos | 41–47 ciclos de dois | 240 ciclos de dois | falsa |
| Origins são folhas | 187 de 192 trânsitos (97,4%) também originam | 10.556 de 11.186 (94,4%) | falsa |
| Os caminhos são curtos | 0,0% com cinco saltos ou mais | 38,0%, o mais longo 15 | conceitualmente errada |
As duas colunas não são o mesmo tipo de número, e isso importa. A tabela cheia é um instantâneo de um feed que não consigo rodar de novo; DN42 é uma rede viva que consigo consultar outra vez, e a coluna DN42 é o que ela mediu em 2026-08-23. Seis dias antes a mesma consulta dizia 33,7% fora da árvore, 138 ciclos de dois e 8,7% da massa a cinco saltos ou mais. Nada quebrou e nenhum código mudou: peers entraram e saíram, e toda propriedade estrutural do grafo se moveu com eles.
Parte disso se move bem mais rápido. Amostrada a cada quarenta e cinco segundos durante duas horas, a contagem de ciclos de dois vagueia entre 41 e 47, e é por isso que aquela célula é uma faixa e não um número. As três cifras em que este artigo de fato se apoia, a contagem de origens, a fatia fora da árvore e o anel externo vazio, não se moveram nada nas mesmas amostras. Esse é o argumento desta série chegando cedo e sem ter sido convidado.
Leia a segunda linha de novo, porque é a que importa para qualquer coisa desenhada como hierarquia. Mais de um quarto dos AS visíveis deste ponto de observação têm mais de um predecessor, e um deles tem 202. Não existe fronteira de setor capaz de segurar esse nó. Não é um problema de layout a resolver com melhor geometria; a forma que se está desenhando não existe.
A mitigação que eu tinha anotado para a regra 2 era “colocar os nós de vários pais na fronteira do setor”. Com 202 pais espalhados pelo disco inteiro, essa instrução não significa nada.
Cada falha custa à imagem uma coisa diferente
Vários pais quebram a partição. Um layout em árvore implica que seguir um setor para dentro diz de onde veio aquele tráfego. Num grafo em que 17,5% da massa de borda não chega pelo pai mais pesado, o setor está falando de uma maioria relativa, não de uma rota. Desenhá-lo sem dizer isso transforma uma maioria em fato.
“Origins são folhas” quebra a subtração. Quase todo nó interior origina prefixos próprios. Se uma renderização mostra o volume de um AS de trânsito e deixa você inferir o espaço originado dele subtraindo o que os filhos contribuem, ela erra em 94% dos casos. A originação própria tem de ser desenhada como coisa em si, em cada posição, nunca implicada pelo que sobra.
O anel nunca foi uma distância. Essa eu errei conceitualmente, e não numericamente. Para cada caminho que entrega, o BGP entrega o AS_PATH inteiro: não existe distância a partir da qual o protocolo comece a truncar. Caminhos ficam mais curtos, sim, mas nunca por estarem longe. O que você não consegue ver não está além de um horizonte, está ausente por um motivo:
- nunca foi anunciado a você,
- sua própria política recusou,
- um agregador apagou aquilo dentro de um
AS_SET, - ou está atrás de um route server transparente que, por projeto, não deixa nenhum salto de AS_PATH (RFC 7947).
Nenhum desses tem raio. Um anel rotulado “tudo além daqui” é uma afirmação geométrica que o protocolo não sustenta. O que o Osprey desenha no lugar é distância em saltos sobre as adjacências efetivamente observadas, e a legenda diz exatamente isso, em vez de insinuar um mínimo.
É essa a visão de que este artigo trata, desenhada a partir do feed do DN42. A faixa do topo é a parte com que me importo: ela enuncia o formato do grafo que está desenhando, incluindo os 18,3% de massa que árvore nenhuma segura, em vez de deixar o leitor supor que a imagem está completa.
Dois grafos, ambos chamados “a topologia de AS”
Ponha as duas lado a lado e o interessante não é que difiram. É onde elas diferem:
| Propriedade | DN42 | Tabela cheia |
|---|---|---|
| AS com vários pais | 22,7% | 28,3% |
| Massa de borda fora do pai mais pesado | 18,3% | 17,5% |
| Trânsitos que também originam | 97,4% | 94,4% |
| Caminhos com cinco saltos ou mais | 0,0% | 38,0% |
Três dessas quatro linhas concordam o bastante para que um modelo ajustado a qualquer uma delas parecesse bom na outra. A quarta não é uma diferença de grau. No DN42 não há absolutamente nada a cinco saltos ou mais; numa tabela real é bem mais de um terço da massa. Um layout validado contra a rede pequena não estaria levemente mal ajustado para a grande: teria sido validado contra um grafo cujo anel externo está vazio e depois entregue a um em que o anel externo é onde mora a maior parte da internet.
Isso é pior que a versão deste argumento que eu esperava fazer, e é o mesmo argumento que o laboratório faz para IGPs, um nível acima: não se valida um modelo contra um ambiente incapaz de contradizê-lo. Três linhas concordarem é exatamente o que torna a quarta perigosa. O feed pequeno não anuncia quais das suas propriedades por acaso generalizam.
A recusa com que esta série começa
Vale enunciar uma consequência antes de qualquer outra coisa ser desenhada nesta série.
Uma aresta num grafo de AS é uma adjacência de caminho, nunca uma afirmação de peering. Dois AS aparecem lado a lado num AS_PATH; a observação é essa e só essa. Não significa que tenham sessão, e o route server transparente acima é exatamente o porquê: dois de seus clientes ficam adjacentes no caminho sem relação nenhuma entre si, porque a RFC 7947 diz que o servidor não deixa salto.
Então o cartão diz “uma adjacência em caminhos, não uma sessão de peering verificada”, e diz isso em cada aresta.
Há exatamente um lugar onde cabe uma afirmação mais forte: uma aresta que toca o seu próprio AS, e mesmo assim só quando um registro de sessão independente a corrobora. Esse é um anel da imagem, e a afirmação é autorizada pela segunda fonte, não pela posição. Tudo mais para fora é inferência sobre caminhos, e rotular de outro jeito seria inventar relações entre as redes dos outros.
O que a tabela realmente me entregou
Vale separar, porque toda regra que caiu acima caiu do mesmo jeito.
O feed me deu três coisas: prefixos com seus melhores caminhos, o AS_PATH de cada um, e em que sessão chegaram. A observação é essa.
Todo o resto deste artigo eu calculei. Predecessor, distância em saltos, massa de aresta, a fatia fora da árvore, se um AS também origina, o próprio grafo: tudo isso é construção, feita de uma posição, e cada número mudaria se a posição mudasse.
E três coisas não estão numa tabela BGP de jeito nenhum, a distância alguma:
- se dois AS têm sessão,
- quanto tráfego se move por tudo isso,
- e os caminhos que meus upstreams escolheram não me mandar, que não deixam rastro de terem sido retidos.
Cada uma das três regras que escrevi era uma afirmação sobre a segunda coluna vestida de afirmação sobre a primeira. “Todo AS tem um pai” soa como observação. É uma propriedade de uma renderização, e a medição foi o que tornou a diferença visível.
O ponto
Escrevi três regras e uma medição refutou as três. É um bom resultado, e só estava disponível porque as regras eram específicas o bastante para poderem estar erradas.
A afirmação mais ampla, de que trata o resto desta série: uma tabela BGP é um ponto de vista. Sua forma, seu centro, seu backbone e seu horizonte são todos artefatos de onde o feed vem. Toda ferramenta que desenha uma como se fosse geografia está afirmando algo sobre a internet quando só tem evidência sobre um ponto de observação.
A versão honesta desenha o que observou e diz que ponto de observação a produziu.
Fica a pergunta de que trata o próximo artigo. Depois de desistir de desenhar a tabela como hierarquia, ainda é preciso decidir o que colocar no topo da lista, e isso acaba sendo uma pergunta mais difícil do que parece.
A seguir: o eixo pelo qual todo mundo ordena, e por que a maior rede da internet não existe. O maior AS não existe.