Uma vez, li no Habr
um artigo sobre a configuração do BGP em um roteador. As instruções de lá podem ser usadas para configurar o roteador doméstico, para que o tráfego para endereços IP específicos passe por outro canal. No entanto, há um problema: a lista de endereços IP pode ser muito grande.
Além das redes da lista, as maiores sub-redes comuns de redes vizinhas são adicionadas a este gráfico. Leia sobre por que isso é necessário.
Parecia uma árvore de rede de Roskomnadzor em maio de 2018.Primeiro, tentei adicionar a lista inteira via / ip route add ao meu MikroTik hAP ac lite - o roteador ficou sem espaço em disco. Depois carreguei todos os endereços na memória através do BGP - o roteador funcionou um pouco e travou. Tornou-se óbvio que a lista precisava ser cortada.
O
artigo menciona o
utilitário network-list-parser de
Unsacrificed . Ela faz o que eu preciso, mas eu a vi depois que comecei a inventar minha bicicleta. Então terminei por desinteresse, porque o que fiz funciona melhor, embora muito mais devagar.
Portanto, a declaração do problema: você precisa escrever um script que use uma lista de endereços IP e redes como entrada e encurte-o para o tamanho especificado. Nesse caso, a nova lista deve abranger todos os endereços da antiga e o número de novos endereços forçados a serem adicionados a ela deve ser mínimo.
Vamos começar criando um gráfico de todas as redes de origem (o que está na figura acima). O nó raiz será a rede 0.0.0.0/0. Ao adicionar uma nova sub-rede A, encontramos a sub-rede B na árvore, para que A e B estejam na sub-rede C e o tamanho da sub-rede C seja mínimo (máscara máxima). Em outras palavras, o número de bits comuns das sub-redes A e B deve ser máximo. Adicionamos essa sub-rede comum à árvore e, por dentro, transferimos as sub-redes A e B. Talvez isso possa ser chamado de árvore binária.
Por exemplo, crie uma árvore de duas sub-redes (192.168.0.1/32 e 192.168.33.0/24):
Pegue a árvore:
Se adicionarmos, digamos, a rede 192.168.150.150/32, a árvore ficará assim:
Laranja indica sub-redes comuns adicionadas durante a construção da árvore. São essas sub-redes comuns que "recolheremos" para reduzir o tamanho da lista. Por exemplo, se você recolher o nó 192.168.0.0/16, reduziremos o tamanho da lista de redes em 2 (havia 3 redes da lista original, ela se tornou 1), mas, ao mesmo tempo, cobrimos adicionalmente 65536-1-1-256 = 65278 endereços IP, que não incluído em nossa lista original.
É conveniente que cada nó calcule o "coeficiente de lucro do colapso", mostrando o número de endereços IP que serão adicionados adicionalmente a cada uma das entradas excluídas da lista:
weight_reversed = net_extra_ip_volume / (in_list_records_count - 1)
Usaremos weight = 1 / weight_reversed, como é mais conveniente. É curioso que o peso possa ser igual ao infinito se, por exemplo, houver duas / 32 redes na lista, que juntas formam uma rede / 31 grande.
Assim, quanto maior o peso, mais lucrativo é o colapso dessa rede.
Agora você pode calcular o peso para todos os nós da rede, classificar os nós por peso e recolher as sub-redes até obtermos o tamanho da lista de que precisamos. No entanto, existe uma dificuldade: no momento em que colapsamos uma rede, os pesos de todas as redes pai mudam.
Por exemplo, temos uma árvore com pesos calculados:
Vamos recolher a sub-rede 192.168.0.0/30:
O peso do nó pai diminuiu. Se houver nós na árvore com um peso maior que 0,166, o seguinte deverá ser recolhido.
Como resultado, a lista deve ser compactada recursivamente. O algoritmo é algo como isto:
- Calculamos os pesos para todos os nós.
- Para cada nó, armazene o peso máximo do nó filho (Wmax).
- Acontece que Wmax do nó raiz é o peso máximo do nó em toda a árvore (pode haver vários nós com um peso igual a Wmax).
- Comprima recursivamente todas as redes com um peso igual a Wmax do nó raiz. Nesse caso, recalculamos o peso. Retornamos ao nó raiz.
- O Wmax do nó raiz diminuiu - realizamos a etapa 4 até obter o tamanho desejado da lista de redes.
O mais interessante é observar o algoritmo em movimento. Aqui está um exemplo para uma lista de redes:
192.168.0.1
192.168.0.2
192.168.0.8/29
192.168.150.1
192.168.150.2
192.168.150.8/29
192.168.20.1
192.168.20.2
192.168.20.3
192.168.20.4
192.168.20.5
192.168.20.6
192.168.20.7Aqui, as sub-redes 192.168.0.0/24 e 192.168.150.0/24 são idênticas na estrutura - é melhor ver como o algoritmo salta de um ramo para outro durante a compactação. Ele adicionou a sub-rede 192.168.20.0/24 para mostrar que às vezes é mais lucrativo compactar a rede pai do que a rede filha. Preste atenção à sub-rede 192.168.20.0/30: após o preenchimento da árvore, seu peso é menor que o da sub-rede pai.
Enchimento de árvore:
Aqui, a fonte preta é a rede real da lista original. Redes adicionadas em amarelo. Azul é o peso do nó. Vermelho é a rede atual. Rosa é uma rede colapsada.
Compressão
Havia uma idéia para acelerar o algoritmo de colapso da rede: para isso, não é necessário recolher apenas redes com peso máximo a cada iteração. Você pode pré-selecionar o valor do peso, o que fornecerá uma lista do tamanho desejado. Você pode selecionar por pesquisa binária, ou seja, comprima com um certo peso e veja qual tamanho da lista é obtido na saída. É verdade que, para isso, você precisa do dobro da memória e reescreve o código - eu simplesmente não consegui colocar minhas mãos nele.
Agora resta comparar com o
analisador de
lista de rede do artigo sobre BGP.
Prós do meu script:
- Configuração mais conveniente: basta especificar o tamanho necessário da lista de redes e a saída será uma lista exatamente desse tamanho. O analisador de lista de rede possui muitos identificadores, e você precisa encontrar uma combinação deles.
- A taxa de compactação se adapta à lista original. Se removermos algumas redes da lista, obteremos menos endereços adicionais, se adicionarmos mais. Nesse caso, o tamanho da lista resultante será constante. Você pode escolher o tamanho máximo que o roteador pode suportar e não se preocupar com o aumento da lista em algum momento.
- A lista resultante contém o número mínimo possível de redes adicionais. Na lista de testes do GitHub, meu algoritmo forneceu 718479 endereços IP adicionais e analisador de lista de rede - 798761. A diferença é de apenas 10% .
Como eu calculei isso? Assistindo1. Lançamento
./network-list-parser-darwin-386-1.2.bin -src-file real_net_list_example.txt -dst-file parsed.txt -aggregation-max-fake-ips 0 -intensive-aggregation-min-prefix 31 2>&1
e temos uma lista limpa sem lixo e parcialmente reduzida. Vou comparar a qualidade da compactação do parsed.txt. (sem esta etapa, houve problemas ao avaliar quantos IPs falsos adiciona o analisador de lista de rede).
2. Lançamento
./network-list-parser-darwin-386-1.2.bin -src-file parsed.txt -dst-file parsed1.txt 2>&1
e temos uma lista compactada, observe a saída, existe a linha "Adicione 7,3% de cobertura de IPs (798761)".
O arquivo parsed1.txt possui 16649 entradas.
3. Lançamento
python3 minimize_net_list.py parsed.txt 16649.
Vemos a linha ### ips não reais: 718479.
Eu vejo apenas uma desvantagem do script resultante: ele funciona por um longo tempo e requer muita memória. No meu MacBook, a lista é pressionada por 5 segundos. Em framboesa -
um minuto e meio . Com o RyPy3 no Mac, é mais rápido, não consegui colocar o PyPy3 no Raspberry. O analisador de lista de rede voa para lá e para lá.
Em geral, faz sentido usar esse esquema apenas para perfeccionistas, uma vez que é improvável que todos os outros gastem tantos recursos de computação em benefício de 10% das redes salvas. Bem, um pouco mais conveniente, sim.
Link para o projeto no GitHubExecute assim:
python3 minimize_net_list.py real_net_list_example.txt 30000 | grep -v ### > result.txt
Isso, de fato, é tudo.
UPDPochemuk nos comentários indicou um erro no cálculo do peso, eu o
corrigi e agora, ao compactar a mesma lista do exemplo com as mesmas configurações, são adicionados 624925 endereços IP que não estão na lista original. Isso já é
22% melhor do que ao processar o analisador de lista de rede
Novo código no
github.com/phoenix-mstu/net_list_minimizer/tree/untested branch