O maior AS não existe
Duas maneiras de ranquear uma tabela BGP, ambas razoáveis, sem um único membro em comum nos doze primeiros
Michel Wijnberg
Toda visão de uma tabela BGP acaba precisando de uma lista. Na que eu medi há 79.168 AS e numa tela cabe talvez uma dúzia, então alguma coisa tem de decidir qual dúzia.
Esse controle parece trivial. É o mais consequente da visão inteira, porque o ranking escolhido não apenas reordena a resposta. Ele muda quais redes o operador acredita importarem, e duas escolhas defensáveis produzem listas sem nada em comum.
O eixo óbvio, e por que ele falha
Ranquear por quantos prefixos cada AS origina. Maior primeiro. É o que quase tudo faz, é
um GROUP BY, e está errado de duas formas separadas.
Não converge.
| Ranqueado por contagem de prefixos originados | Cobertura da tabela |
|---|---|
| Top 12 | 8,3% |
| Top 1.000 | 52,9% |
Mil redes para dar conta de metade da tabela. Isso não é um ranking, é a tabela de novo com as linhas em outra ordem. Não há dúzia alguma na frente desse eixo que explique qualquer coisa, porque a distribuição praticamente não tem cabeça.
E ele premia a desagregação.
Contagem de prefixos mede anúncios, não espaço de endereçamento, e os dois são só frouxamente relacionados. Um número diz tudo: divida os prefixos anunciados de cada rede pelo número de blocos contíguos que eles de fato cobrem e, para a tabela toda, este feed fica em 1,64 prefixo por bloco. Os doze primeiros ficam em 3,4. O caso mais extremo medido, AS18403, anuncia 4.611 prefixos em 26 blocos, um fator de 177. O AS9808 está em 86 vezes, o AS4538 em 66.
Ou seja, o placar premia quem pica seu espaço mais fino. Uma rede que anuncia um /16 limpo afunda abaixo de uma rede que anuncia esse mesmo /16 como 256 /24, e a segunda é discutivelmente a pior cidadã da internet. Ordenar por contagem de prefixos é ordenar por volume de fala.
Ranqueie a mesma tabela por espaço de endereçamento único (3.121.065.344 endereços no total) e a lista não se embaralha. Ela se desmancha:
| AS | Posição por prefixos | Posição por espaço |
|---|---|---|
| AS16509 | 1 | 2 |
| AS9808 | 2 | 12 |
| AS8151 | 3 | 32 |
| AS12479 | 4 | 71 |
| AS7545 | 5 | 141 |
| AS39891 | 8 | 308 |
O oitavo por anúncios é o 308º por espaço de endereçamento. Enquanto isso, a rede que de fato é a primeira em espaço, AS749, detém 7,17% desse total com 3.133 prefixos, e o AS4134 chega em terceiro com 729. São redes anunciando blocos grandes inteiros, que é o que se esperaria, e a contagem de prefixos as enterra.
Uma armadilha no caminho, porque errar é fácil e silencioso: isso tem de ser uma união, nunca uma soma. Somar 2^(32 − tamanho da máscara) sobre prefixos que se sobrepõem conta duas vezes cada agregado que os cobre, medido em 1,269× na tabela toda, e isso é mais que suficiente para mudar a ordem. Os prefixos têm de ser fundidos em faixas sem sobreposição antes de qualquer ranqueamento ou desenho. Nós entregamos primeiro a versão que somava. Não quebrou, os totais pareciam razoáveis, e a ordem produzida era plausível o bastante para que ninguém questionasse até uma revisão ir olhar. Esse é o modo de falha a temer numa medição: não uma resposta errada que se anuncia, mas uma crível.
O eixo que converge
Faça outra pergunta. Não “quem anuncia mais” e sim “cujo desaparecimento me custaria mais alcançabilidade”. De forma gulosa: pegue o AS que alcança mais AS de origem, tire essas origens do conjunto e repita sobre o que sobrou. Nossos próprios upstreams diretamente conectados ficam de fora, senão as primeiras escolhas são dominadas pelo próprio ponto de observação em vez de por algo da tabela.
| Passo | AS | Fatia acumulada de AS de origem alcançados |
|---|---|---|
| 1 | AS2516 | 38% |
| 2 | AS7575 | 60% |
| 3 | AS2497 | 82% |
| 4 | AS6939 | 90% |
| 5 | AS1221 | 94% |
Cinco redes alcançam 94% dos AS de origem visíveis deste ponto de observação. A mesma tabela precisou de mil para chegar a 53% no outro eixo.
Essa é a resposta que um arquiteto quer: essas cinco são o substrato de trânsito sobre o qual este ponto de observação repousa, e perder uma delas é uma classe de evento diferente de perder a rede com mais prefixos.
A imagem acima é o mesmo controle num feed diferente e bem menor, onde a resposta são três redes a 96% em vez de cinco a 94%. O número de entradas não é o ponto e não se transfere. O que se transfere é que este eixo tem cabeça, e que a faixa enuncia a cobertura dele ao lado, em vez de deixar você se perguntando se as linhas na tela são a maior parte da história ou um centésimo dela.
Precisa de uma ressalva, a que o artigo anterior conquistou. O alcance é calculado como um cone sobre a árvore dominante: cada AS é atribuído ao seu predecessor mais pesado, e a subárvore abaixo dele é somada. Isso é uma projeção em árvore de um grafo que acabei de passar um artigo provando não ser uma árvore, e o erro não é hipotético, são os 17,5% de massa de borda que não chegam pelo pai mais pesado. Então o número é uma soma de árvore sobre uma não-árvore, e é por isso que o produto o rotula como tal em vez de apresentá-lo como alcançabilidade. Serve para ranquear e não serve para citar como garantia de dependência.
Duas coisas me convenceram de que o número era sólido e não sortudo. Uma amostra 1:10 do mesmo coletor, uma origem a cada dez levada com todos os seus prefixos, caminhos e predecessores (11.136 AS, 7.854 origens, 106.900 prefixos), reproduz os mesmos cinco AS na mesma ordem em 34/62/76/86/88%. O mecanismo também não é misterioso, e é toda a diferença entre os dois eixos. Contagem de prefixos pergunta o que cada rede tem por conta própria: cada prefixo pertence a uma origem, nada é compartilhado, então o ranking é uma cauda longa de contribuições independentes. Alcance de trânsito pergunta o que depende de cada rede, e dependências se sobrepõem muito. Cada escolha absorve a maior parte do que a seguinte poderia reivindicar, e é por isso que cinco entradas esgotam a pergunta e mil entradas de contagem de prefixos não.
A parte que me fez reescrever o controle
Aqui está o achado que eu não esperava. As duas listas de doze primeiros, da mesma tabela, na mesma hora, compartilham zero membros.
Não “quase diferentes”. Nenhuma sobreposição.
Isso não é um problema de desempate, e não é algo que um bom padrão resolva. Significa que o controle não é uma ordem de classificação. É um seletor de pergunta, e as duas perguntas são:
- Quem anuncia mais prefixos? Resposta: as redes da tabela de desagregação acima.
- Sobre o que esta tabela se apoia? Resposta: um conjunto completamente diferente, nenhum dos quais aparece no primeiro.
As duas respostas estão certas. Nenhuma é “o maior AS”. A expressão não se refere a nada, e é por isso que uma visão que oferece um único ranking e o chama de importância está afirmando algo que não consegue sustentar.
Então o controle no Osprey são dois eixos explicitamente rotulados em vez de uma direção de ordenação, e o limiar ao lado diz qual papel ele está cumprindo: dobrar além de N é uma operação de layout, nomear os N primeiros é uma operação de rotulagem, e são duas coisas diferentes feitas com o mesmo número. Confundir isso foi um dos achados de revisão contra a nossa própria versão.
O que isso custa ao leitor
Um ranking que não converge tem um modo de falha específico num contexto de operação, e vale nomeá-lo porque não é óbvio.
Se os doze primeiros cobrem 8,3%, então as doze linhas na tela não representam os outros 91,7% de um jeito que a tela não sinaliza. Um operador que raciocina a partir delas está raciocinando a partir de uma amostra selecionada por uma propriedade que ninguém escolheu deliberadamente. Parecem as redes importantes. São as que anunciam nos menores pedaços.
O eixo de alcance de trânsito tem a propriedade oposta. Cinco linhas cobrindo 94% significam que a tela está mostrando quase toda a estrutura, e o que você não vê é genuinamente marginal. Essa é a diferença entre uma lista e uma explicação.
O limite
Alcance de trânsito é calculado a partir da sua tabela, então herda toda propriedade do seu ponto de observação. Não é uma medição da estrutura da internet. É uma medição do que o seu feed consegue ver dela, e o próximo artigo é sobre o quão distantes essas duas coisas estão.
Também depende do que seus upstreams escolheram lhe mandar. Um caminho filtrado antes de chegar até você não aparece no ranking, e computação nenhuma o recupera. Os números de alcance são, portanto, um limite inferior da dependência: tudo o que está listado é real, e pode haver estrutura atrás do filtro que não está.
Dizer isso é barato, e é a diferença entre um número com que se planeja e um número que vai lhe envergonhar.
O ponto
O controle que decide quais doze linhas um operador vê não é um detalhe de apresentação. Nesta tabela ele decide entre duas respostas disjuntas, ambas defensáveis, uma das quais converge e a outra não.
“O maior AS” soa como se nomeasse um fato. Nomeia qualquer que seja a pergunta que a ordenação padrão tenha codificado, e quase nenhuma ferramenta lhe diz qual foi.
Que é a regra de projeto de que este artigo realmente trata: um controle que decide o que um operador olha tem de expor a pergunta que responde. “Ordenar por: importância” não é uma conveniência. É uma escolha de modelo, feita por quem escreveu o menu suspenso, em nome de alguém a quem nunca será dito que ela aconteceu.
A seguir: aquelas cinco redes de trânsito são da Ásia-Pacífico, e isso não é um fato sobre a internet. Seu backbone não é o da internet.