Una vez que leí en Habr
un artículo sobre la configuración de BGP en un enrutador. Las instrucciones de allí se pueden usar para configurar el enrutador doméstico de modo que el tráfico a direcciones IP específicas pase por otro canal. Sin embargo, hay un problema: la lista de direcciones IP puede ser muy grande.
Además de las redes de la lista, las subredes comunes más grandes de las redes vecinas se agregan a este gráfico. Siga leyendo para saber por qué esto es necesario.
Parecía un árbol de red de Roskomnadzor en mayo de 2018.Primero, intenté agregar la lista completa a través de / ip route add a mi MikroTik hAP ac lite: el enrutador se quedó sin espacio en disco. Luego cargué todas las direcciones en la memoria a través de BGP: el enrutador funcionó un poco y se colgó. Se hizo evidente que la lista necesitaba ser recortada.
El
artículo menciona la
utilidad network-list-parser de
Unsacrificed . Ella hace lo que necesito, pero la vi después de que empecé a inventar mi bicicleta. Luego lo terminé por interés, porque lo que hice funciona mejor, aunque mucho más lento.
Entonces, la declaración del problema: debe escribir un script que tome una lista de direcciones IP y redes como entrada y la acorte al tamaño especificado. En este caso, la nueva lista debe cubrir todas las direcciones de la anterior, y el número de nuevas direcciones que se deben agregar debe ser mínimo.
Comencemos construyendo un gráfico de todas las redes de origen (lo que está en la imagen de arriba). El nodo raíz será la red 0.0.0.0/0. Al agregar una nueva subred A, encontramos la subred B en el árbol para que A y B estén en la subred C y el tamaño de la subred C sea mínimo (máscara máxima). En otras palabras, el número de bits comunes de subredes A y B debe ser máximo. Agregamos esta subred común al árbol, y dentro transferimos las subredes A y B. Quizás esto se pueda llamar un árbol binario.
Por ejemplo, cree un árbol de dos subredes (192.168.0.1/32 y 192.168.33.0/24):
Consigue el árbol:
Si agregamos, digamos, la red 192.168.150.150/32, entonces el árbol se verá así:
Naranja indica subredes comunes agregadas durante la construcción del árbol. Son estas subredes comunes las que "colapsarán" para reducir el tamaño de la lista. Por ejemplo, si contrae el nodo 192.168.0.0/16, reduciremos el tamaño de la lista de redes en 2 (había 3 redes de la lista original, se convirtió en 1), pero al mismo tiempo cubrimos adicionalmente 65536-1-1-256 = 65278 direcciones IP, que No incluido en nuestra lista original.
Es conveniente que cada nodo calcule el "coeficiente de beneficio del colapso", mostrando el número de direcciones IP que se agregarán adicionalmente a cada una de las entradas eliminadas de la lista:
weight_reversed = net_extra_ip_volume / (in_list_records_count - 1)
Usaremos weight = 1 / weight_reversed, como Es más conveniente. Es curioso que el peso puede ser igual al infinito si, por ejemplo, hay dos redes / 32 en la lista, que juntas forman una red grande / 31.
Por lo tanto, cuanto mayor es el peso, más rentable es colapsar dicha red.
Ahora puede calcular el peso de todos los nodos en la red, ordenar los nodos por peso y colapsar las subredes hasta que obtengamos el tamaño de la lista que necesitamos. Sin embargo, hay una dificultad: en el momento en que colapsamos una red, los pesos de todas las redes principales cambian.
Por ejemplo, tenemos un árbol con pesos calculados:
Vamos a colapsar la subred 192.168.0.0/30:
El peso del nodo padre ha disminuido. Si hay nodos en el árbol con un peso mayor que 0.166, entonces lo siguiente debería colapsarse.
Como resultado, la lista debe comprimirse de forma recursiva. El algoritmo es algo como esto:
- Calculamos los pesos para todos los nodos.
- Para cada nodo, almacene el peso máximo del nodo hijo (Wmax).
- Resulta que Wmax del nodo raíz es el peso máximo del nodo en todo el árbol (puede haber varios nodos con un peso igual a Wmax).
- Comprima recursivamente todas las redes con un peso igual a Wmax del nodo raíz. En este caso, recalculamos el peso. Regresamos al nodo raíz.
- La Wmáx del nodo raíz ha disminuido: realizamos el paso 4 hasta obtener el tamaño deseado de la lista de redes.
Lo más interesante es observar el algoritmo en movimiento. Aquí hay un ejemplo para una 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.7Aquí, las subredes 192.168.0.0/24 y 192.168.150.0/24 tienen una estructura idéntica; es mejor ver cómo el algoritmo salta de una rama a otra durante la compresión. Agregó la subred 192.168.20.0/24 para mostrar que a veces es más rentable comprimir la red principal que la red secundaria. Preste atención a la subred 192.168.20.0/30: después de llenar el árbol, su peso es menor que el de la subred principal.
Relleno de árbol:
Aquí la fuente negra es la red real de la lista original. Amarillo - redes agregadas. El azul es el peso del nodo. El rojo es la red actual. El rosa es una red colapsada.
Compresión
Hubo una idea para acelerar el algoritmo de colapso de la red: para esto no es necesario colapsar solo las redes con un peso máximo en cada iteración. Puede preseleccionar el valor del peso, lo que nos dará una lista del tamaño deseado. Puede seleccionar por búsqueda binaria, es decir comprimir con un peso determinado y ver qué tamaño de la lista se obtiene en la salida. Es cierto, para esto necesitas el doble de memoria y reescribir el código, simplemente no lo pude conseguir.
Ahora queda por comparar con
network-list-parser del artículo sobre BGP.
Ventajas de mi guión:
- Configuración más conveniente: solo especifique el tamaño requerido de la lista de redes, y la salida será una lista de exactamente ese tamaño. Network-list-parser tiene muchos identificadores, y necesita encontrar una combinación de ellos.
- La relación de compresión se adapta a la lista original. Si eliminamos algunas redes de la lista, obtendremos menos direcciones adicionales, si agregamos más. En este caso, el tamaño de la lista resultante será constante. Puede elegir el tamaño máximo que puede manejar el enrutador y no preocuparse de que la lista se vuelva demasiado grande en algún momento.
- La lista resultante contiene el mínimo número posible de redes adicionales. En la lista de prueba de GitHub, mi algoritmo proporcionó 718479 direcciones IP adicionales y un analizador de listas de red: 798761. La diferencia es solo del 10% .
¿Cómo calculé esto? Viendo1. Lanzamiento
./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
y obtenemos una lista limpia sin basura y parcialmente reducida. Compararé la calidad de compresión de parsed.txt. (sin este paso, hubo problemas al evaluar cuántas IP falsas agrega network-list-parser).
2. Lanzamiento
./network-list-parser-darwin-386-1.2.bin -src-file parsed.txt -dst-file parsed1.txt 2>&1
y obtenemos una lista comprimida, mira la salida, está la línea "Agregar 7.3% de cobertura de IP (798761)".
El archivo parsed1.txt tiene 16649 entradas.
3. Lanzamiento
python3 minimice_net_list.py parsed.txt 16649.
Vemos la línea ### no ips reales: 718479.
Solo veo un inconveniente del script resultante: funciona durante mucho tiempo y requiere mucha memoria. En mi MacBook, la lista se presiona durante 5 segundos. En frambuesa:
un minuto y medio . Con RyPy3 en Mac, es más rápido, no pude poner PyPy3 en Raspberry. Network-list-parser vuela de un lado a otro.
En general, tiene sentido usar este esquema solo para perfeccionistas, ya que Es poco probable que todos los demás gasten tantos recursos informáticos por el 10% de las redes guardadas. Bueno, un poco más conveniente, sí.
Enlace al proyecto en GitHubCorre así:
python3 minimize_net_list.py real_net_list_example.txt 30000 | grep -v ### > result.txt
Eso, de hecho, es todo.
UPDPochemuk en los comentarios indicó un error al calcular el peso, lo arreglé y ahora, al comprimir la misma lista del ejemplo con la misma configuración, se agregan 624925 direcciones IP que no están en la lista original. Esto ya es un
22% mejor que cuando se procesa network-list-parser
Nuevo código en
github.com/phoenix-mstu/net_list_minimizer/tree/untested branch no
probado