Compressez la liste des adresses IP de la meilleure façon

Une fois que j'ai lu sur Habr un article sur la configuration de BGP sur un routeur. Les instructions à partir de là peuvent être utilisées pour configurer le routeur domestique afin que le trafic vers des adresses IP spécifiques passe par un autre canal. Cependant, il y a un problème: la liste des adresses IP peut être très longue.

En plus des réseaux de la liste, les plus grands sous-réseaux communs des réseaux voisins sont ajoutés à ce graphique. Lisez la suite pour savoir pourquoi cela est nécessaire.


Cela ressemblait à une arborescence de réseau de Roskomnadzor en mai 2018.

Tout d'abord, j'ai essayé d'ajouter la liste complète via / ip route add à mon MikroTik hAP ac lite - le routeur a manqué d'espace disque. Ensuite, j'ai chargé toutes les adresses en mémoire via BGP - le routeur fonctionnait un peu et se bloquait. Il est devenu évident que la liste devait être réduite.

L' article mentionne l' utilitaire network-list-parser d' Unsacrificed . Elle fait ce dont j'ai besoin, mais je l'ai vue après avoir commencé à inventer mon vélo. Ensuite, je l'ai terminé par intérêt, car ce que j'ai fait fonctionne mieux, bien que beaucoup plus lentement.

Donc, l'énoncé du problème: vous devez écrire un script qui prend une liste d'adresses IP et de réseaux en entrée et la raccourcit à la taille spécifiée. Dans ce cas, la nouvelle liste doit couvrir toutes les adresses de l'ancienne, et le nombre de nouvelles adresses forcées à y être ajoutées doit être minimal.

Commençons par construire un graphique de tous les réseaux sources (ce qui est dans l'image ci-dessus). Le nœud racine sera le réseau 0.0.0.0/0. Lors de l'ajout d'un nouveau sous-réseau A, nous trouvons le sous-réseau B dans l'arborescence afin que A et B se trouvent sur le sous-réseau C et que la taille du sous-réseau C soit minimale (masque maximal). En d'autres termes, le nombre de bits communs des sous-réseaux A et B doit être maximum. Nous ajoutons ce sous-réseau commun à l'arbre, et à l'intérieur nous transférons les sous-réseaux A et B. Peut-être que cela peut être appelé un arbre binaire.

Par exemple, créez une arborescence de deux sous-réseaux (192.168.0.1/32 et 192.168.33.0/24):



Obtenez l'arbre:



Si nous ajoutons, disons, le réseau 192.168.150.150/32, alors l'arborescence ressemblera à ceci:



L'orange indique les sous-réseaux communs ajoutés lors de la construction des arbres. Ce sont ces sous-réseaux communs que nous allons «réduire» pour réduire la taille de la liste. Par exemple, si vous réduisez le nœud 192.168.0.0/16, nous réduirons la taille de la liste des réseaux de 2 (il y avait 3 réseaux de la liste d'origine, elle est devenue 1), mais en même temps, nous couvrons également les adresses IP 65536-1-1-256 = 65278, qui non inclus dans notre liste d'origine.

Il est pratique pour chaque nœud de calculer le «coefficient de profit de l'effondrement», en indiquant le nombre d'adresses IP qui seront en outre ajoutées à chacune des entrées supprimées de la liste:

weight_reversed = net_extra_ip_volume / (in_list_records_count - 1) 

Nous utiliserons weight = 1 / weight_reversed, comme c'est plus pratique. Il est curieux que le poids puisse être égal à l'infini si, par exemple, il y a deux / 32 réseaux dans la liste, qui forment ensemble un grand réseau / 31.

Ainsi, plus le poids est important, plus il est rentable d'effondrer un tel réseau.

Vous pouvez maintenant calculer le poids de tous les nœuds du réseau, trier les nœuds par poids et réduire les sous-réseaux jusqu'à obtenir la taille de la liste dont nous avons besoin. Cependant, il y a une difficulté: au moment où nous effondrons un réseau, les poids de tous les réseaux parents changent.

Par exemple, nous avons un arbre avec des poids calculés:



Réduisons le sous-réseau 192.168.0.0/30:



Le poids du nœud parent a diminué. S'il y a des nœuds dans l'arbre avec un poids supérieur à 0,166, les éléments suivants doivent être réduits.

En conséquence, la liste doit être compressée récursivement. L'algorithme est quelque chose comme ceci:

1. Nous calculons les poids pour tous les nœuds.
2. Pour chaque nœud, stockez le poids maximal du nœud enfant (Wmax).
3. Il s'avère que Wmax du nœud racine est le poids maximum du nœud dans l'arbre entier (il peut y avoir plusieurs nœuds avec un poids égal à Wmax).
4. Compressez récursivement tous les réseaux avec un poids égal à Wmax du nœud racine. Dans ce cas, nous recomptons les poids. Nous revenons au nœud racine.
5. Wmax du nœud racine a diminué - nous effectuons l'étape 4 jusqu'à ce que nous obtenions la taille souhaitée de la liste des réseaux.

La chose la plus intéressante est d'observer l'algorithme en mouvement. Voici un exemple de liste de réseaux:

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.7

Ici, les sous-réseaux 192.168.0.0/24 et 192.168.150.0/24 ont une structure identique - il est préférable de voir comment, pendant la compression, l'algorithme saute d'une branche à l'autre. Il a ajouté le sous-réseau 192.168.20.0/24 afin de montrer qu'il est parfois plus rentable de compresser le réseau parent que le réseau enfant. Faites attention au sous-réseau 192.168.20.0/30: après avoir rempli l'arbre, son poids est inférieur à celui du sous-réseau parent.

Remplissage d'arbres:



Ici, la police noire est le véritable réseau de la liste d'origine. Jaune - réseaux ajoutés. Le bleu est le poids du nœud. Le rouge est le réseau actuel. Le rose est un filet effondré.

La compression



Il y avait une idée pour accélérer l'algorithme d'effondrement du réseau: pour cela, il n'est pas nécessaire d'effondrer uniquement les réseaux avec un poids maximum à chaque itération. Vous pouvez présélectionner la valeur de poids, qui nous donnera une liste de la taille souhaitée. Vous pouvez sélectionner par recherche binaire, c'est-à-dire compresser avec un certain poids et voir quelle taille de la liste est obtenue à la sortie. Certes, pour cela, vous avez besoin de deux fois plus de mémoire et de réécrire le code - je n'ai tout simplement pas mis la main dessus.

Il reste maintenant à comparer avec network-list-parser de l'article sur BGP.

Avantages de mon script:

1. Configuration plus pratique: spécifiez simplement la taille requise de la liste des réseaux, et la sortie sera une liste exactement de cette taille. Network-list-parser a beaucoup de descripteurs, et vous devez en trouver une combinaison.
2. Le taux de compression s'adapte à la liste d'origine. Si nous supprimons certains réseaux de la liste, nous obtiendrons moins d'adresses supplémentaires, si nous en ajoutons plus. Dans ce cas, la taille de la liste résultante sera constante. Vous pouvez choisir la taille maximale que le routeur peut gérer et ne vous inquiétez pas si la liste devient trop longue à un moment donné.
3. La liste résultante contient le nombre minimum possible de réseaux supplémentaires. Sur la liste de tests de GitHub, mon algorithme a donné 718479 adresses IP supplémentaires et analyseur de liste de réseaux - 798761. La différence n'est que de 10% .
   
   
   Comment ai-je calculé cela? Regarder

   1. Lancement
   
   

     ./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 

   
   et nous obtenons une liste nettoyée sans ordures et partiellement réduite. Je vais comparer la qualité de compression de parsed.txt. (sans cette étape, il y a eu des problèmes pour évaluer le nombre de fausses adresses réseau-liste-parseur).
   
   2. Lancement
   
   

    ./network-list-parser-darwin-386-1.2.bin -src-file parsed.txt -dst-file parsed1.txt 2>&1 

   
   et nous obtenons une liste compressée, regardez la sortie, il y a la ligne "Ajouter une couverture IP de 7,3% (798761)."
   
   Le fichier parsed1.txt contient 16649 entrées.
   
   3. Lancement
   
   python3 minimise_net_list.py parsed.txt 16649.
   Nous voyons la ligne ### pas réelle ips: 718479.
   
   
   

Je ne vois qu'un seul inconvénient du script résultant: il fonctionne depuis longtemps et nécessite beaucoup de mémoire. Sur mon MacBook, la liste est pressée pendant 5 secondes. Sur la framboise - une minute et demie . Avec RyPy3 sur Mac, c'est plus rapide, je ne pouvais pas mettre PyPy3 sur Raspberry. Network-list-parser vole ça et là.

En général, il est logique d'utiliser ce schéma uniquement pour les perfectionnistes, car il est peu probable que tous les autres dépensent autant de ressources informatiques pour 10% des réseaux enregistrés. Eh bien, un peu plus pratique, oui.

Lien vers le projet sur GitHub

Courez comme ceci:

 python3 minimize_net_list.py real_net_list_example.txt 30000 | grep -v ### > result.txt 

En fait, c'est tout.

UPD
Pochemuk dans les commentaires a indiqué une erreur dans le calcul du poids, je l'ai corrigé et maintenant, lors de la compression de la même liste de l'exemple avec les mêmes paramètres, 624925 adresses IP sont ajoutées qui ne figurent pas dans la liste d'origine. C'est déjà 22% mieux que lors du traitement de l'analyseur de liste de réseau
Nouveau code dans la branche non testée github.com/phoenix-mstu/net_list_minimizer/tree/untested