Geekly articles weekly

Komprimieren Sie die Liste der IP-Adressen optimal



Einmal habe ich auf Habr einen Artikel über die Konfiguration von BGP auf einem Router gelesen. Die Anweisungen von dort können verwendet werden, um den Heimrouter so zu konfigurieren, dass der Datenverkehr zu bestimmten IP-Adressen über einen anderen Kanal geleitet wird. Es gibt jedoch ein Problem: Die Liste der IP-Adressen kann sehr groß sein.

Zusätzlich zu den Netzwerken aus der Liste werden diesem Diagramm die größten gemeinsamen Subnetze benachbarter Netzwerke hinzugefügt. Lesen Sie weiter, warum dies erforderlich ist.


Es sah aus wie ein Netzwerkbaum von Roskomnadzor im Mai 2018.

Zuerst habe ich versucht, die gesamte Liste über / ip route add zu meinem MikroTik hAP ac lite hinzuzufügen - dem Router ist der Speicherplatz ausgegangen. Dann habe ich alle Adressen über BGP in den Speicher geladen - der Router hat ein wenig funktioniert und ist hängen geblieben. Es wurde offensichtlich, dass die Liste gekürzt werden musste.

Der Artikel erwähnt das Dienstprogramm " Netzwerklisten-Parser" von " Unsacrificed" . Sie tut, was ich brauche, aber ich habe sie gesehen, nachdem ich angefangen habe, mein Fahrrad zu erfinden. Dann habe ich es aus Interesse beendet, weil das, was ich getan habe, besser funktioniert, wenn auch viel langsamer.

Die Aussage des Problems: Sie müssen ein Skript schreiben, das eine Liste von IP-Adressen und Netzwerken als Eingabe verwendet und auf die angegebene Größe verkürzt. In diesem Fall sollte die neue Liste alle Adressen der alten Liste abdecken, und die Anzahl der neuen Adressen, die hinzugefügt werden müssen, sollte minimal sein.

Beginnen wir mit der Erstellung eines Diagramms aller Quellnetzwerke (siehe Abbildung oben). Der Wurzelknoten ist das Netzwerk 0.0.0.0/0. Wenn Sie ein neues Subnetz A hinzufügen, finden Sie das Subnetz B im Baum, sodass sich A und B im Subnetz C befinden und die Größe des Subnetzes C minimal ist (maximale Maske). Mit anderen Worten sollte die Anzahl der gemeinsamen Bits der Subnetze A und B maximal sein. Wir fügen dieses gemeinsame Subnetz dem Baum hinzu und übertragen im Inneren die Subnetze A und B. Vielleicht kann dies als Binärbaum bezeichnet werden.

Erstellen Sie beispielsweise einen Baum aus zwei Subnetzen (192.168.0.1/32 und 192.168.33.0/24):



Holen Sie sich den Baum:



Wenn wir beispielsweise das Netzwerk 192.168.150.150/32 hinzufügen, sieht der Baum folgendermaßen aus:



Orange zeigt die allgemeinen Subnetze an, die beim Erstellen des Baums hinzugefügt wurden. Es sind diese allgemeinen Subnetze, die wir "reduzieren" werden, um die Größe der Liste zu reduzieren. Wenn Sie beispielsweise den Knoten 192.168.0.0/16 reduzieren, reduzieren wir die Größe der Netzwerkliste um 2 (es gab 3 Netze aus der ursprünglichen Liste, es wurde 1), aber gleichzeitig decken wir zusätzlich 65536-1-1-256 = 65278 IP-Adressen ab, die nicht in unserer ursprünglichen Liste enthalten.

Für jeden Knoten ist es praktisch, den "Gewinnkoeffizienten aus dem Zusammenbruch" zu berechnen und die Anzahl der IP-Adressen anzuzeigen, die zusätzlich zu jedem der aus der Liste gelöschten Einträge hinzugefügt werden:

weight_reversed = net_extra_ip_volume / (in_list_records_count - 1)

Wir werden weight = 1 / weight_reversed verwenden, as es ist bequemer. Es ist merkwürdig, dass das Gewicht gleich unendlich sein kann, wenn beispielsweise zwei / 32-Netzwerke in der Liste vorhanden sind, die zusammen ein großes / 31-Netzwerk bilden.

Je größer das Gewicht, desto rentabler ist es, ein solches Netzwerk zusammenzubrechen.

Jetzt können Sie das Gewicht für alle Knoten im Netzwerk berechnen, die Knoten nach Gewicht sortieren und die Subnetze reduzieren, bis wir die Größe der Liste erhalten, die wir benötigen. Es gibt jedoch eine Schwierigkeit: In dem Moment, in dem wir ein Netzwerk zusammenbrechen, ändern sich die Gewichte aller übergeordneten Netzwerke.

Zum Beispiel haben wir einen Baum mit berechneten Gewichten:



Lassen Sie uns das Subnetz 192.168.0.0/30 reduzieren:



Das Gewicht des übergeordneten Knotens hat abgenommen. Wenn der Baum Knoten mit einer Gewichtung von mehr als 0,166 enthält, sollte Folgendes reduziert werden.

Infolgedessen muss die Liste rekursiv komprimiert werden. Der Algorithmus ist ungefähr so:

  1. Wir berechnen die Gewichte für alle Knoten.
  2. Speichern Sie für jeden Knoten das maximale Gewicht des untergeordneten Knotens (Wmax).
  3. Es stellt sich heraus, dass Wmax des Wurzelknotens das maximale Gewicht des Knotens im gesamten Baum ist (es kann mehrere Knoten mit einer Gewichtung geben, die Wmax entspricht).
  4. Komprimieren Sie rekursiv alle Netzwerke mit einer Gewichtung, die Wmax des Stammknotens entspricht. In diesem Fall zählen wir die Gewichte nach. Wir kehren zum Wurzelknoten zurück.
  5. Wmax des Wurzelknotens hat abgenommen - wir führen Schritt 4 aus, bis wir die gewünschte Größe der Netzwerkliste erhalten.

Am interessantesten ist es, den Algorithmus in Bewegung zu beobachten. Hier ist ein Beispiel für eine Liste von Netzwerken:

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

Hier sind die Subnetze 192.168.0.0/24 und 192.168.150.0/24 identisch aufgebaut - es ist besser zu sehen, wie der Algorithmus während der Komprimierung von einem Zweig zum anderen springt. Er fügte das Subnetz 192.168.20.0/24 hinzu, um zu zeigen, dass es manchmal rentabler ist, das übergeordnete Netzwerk als das untergeordnete Netzwerk zu komprimieren. Achten Sie auf das Subnetz 192.168.20.0/30: Nach dem Füllen des Baums ist sein Gewicht geringer als das des übergeordneten Subnetzes.

Baumfüllung:



Hier ist die schwarze Schrift das eigentliche Netzwerk aus der ursprünglichen Liste. Gelb - Netzwerke hinzugefügt. Blau ist das Gewicht des Knotens. Rot ist das aktuelle Netzwerk. Pink ist ein zusammengebrochenes Netz.

Komprimierung



Es gab eine Idee, den Netzwerkkollaps-Algorithmus zu beschleunigen: Dazu ist es nicht erforderlich, bei jeder Iteration nur Netzwerke mit maximalem Gewicht zu kollabieren. Sie können den Gewichtswert vorab auswählen, wodurch wir eine Liste der gewünschten Größe erhalten. Sie können durch binäre Suche auswählen, d. H. Komprimieren Sie mit einem bestimmten Gewicht und sehen Sie, welche Größe der Liste am Ausgang erhalten wird. Dafür benötigen Sie doppelt so viel Speicher und schreiben den Code neu - ich habe ihn einfach nicht in die Hände bekommen.

Nun bleibt ein Vergleich mit dem Network-List-Parser aus dem Artikel über BGP.

Vorteile meines Skripts:

  1. Bequemere Einrichtung: Geben Sie einfach die erforderliche Größe der Netzwerkliste an, und die Ausgabe ist eine Liste mit genau dieser Größe. Der Netzwerklisten-Parser hat viele Handles, und Sie müssen eine Kombination davon finden.
  2. Das Komprimierungsverhältnis passt sich der ursprünglichen Liste an. Wenn wir einige Netzwerke aus der Liste entfernen, erhalten wir weniger zusätzliche Adressen, wenn wir mehr hinzufügen. In diesem Fall ist die Größe der resultierenden Liste konstant. Sie können die maximale Größe auswählen, die der Router verarbeiten kann, und sich keine Sorgen machen, dass die Liste irgendwann zu groß wird.
  3. Die resultierende Liste enthält die minimal mögliche Anzahl zusätzlicher Netzwerke. Auf der Testliste von GitHub gab mein Algorithmus 718479 zusätzliche IP-Adressen und den Netzwerklisten-Parser - 798761. Der Unterschied beträgt nur 10% .

    Wie habe ich das berechnet? Beobachten
    1. Starten Sie

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

    und wir bekommen eine gereinigte Liste ohne Müll und teilweise reduziert. Ich werde die Komprimierungsqualität von parsed.txt vergleichen. (Ohne diesen Schritt gab es Probleme bei der Bewertung, wie viele gefälschte IP-Adressen der Netzwerklisten-Parser hinzufügt.)

    2. Starten Sie

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

    und wir erhalten eine komprimierte Liste, sehen Sie sich die Ausgabe an, es gibt die Zeile "7,3% IPs-Abdeckung hinzufügen (798761)."

    Die Datei parsed1.txt enthält 16649 Einträge.

    3. Starten Sie

    python3 minim_net_list.py parsed.txt 16649.
    Wir sehen die Zeile ### nicht real ips: 718479.


Ich sehe nur einen Nachteil des resultierenden Skripts: Es funktioniert lange und benötigt viel Speicher. Auf meinem MacBook wird die Liste 5 Sekunden lang gedrückt. Auf Himbeere - eineinhalb Minuten . Mit RyPy3 auf dem Mac ist es schneller, ich konnte PyPy3 nicht auf Raspberry setzen. Network-List-Parser fliegt hin und her.

Im Allgemeinen ist es sinnvoll, dieses Schema nur für Perfektionisten zu verwenden, da Es ist unwahrscheinlich, dass alle anderen so viel Rechenressourcen für 10% der gespeicherten Netzwerke ausgeben. Na ja, ein bisschen bequemer, ja.

Link zum Projekt auf GitHub

Laufen Sie so:

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

Das ist in der Tat alles.

UPD
Pochemuk in den Kommentaren zeigte einen Fehler bei der Berechnung des Gewichts an. Ich habe ihn behoben. Wenn jetzt dieselbe Liste aus dem Beispiel mit denselben Einstellungen komprimiert wird, werden 624925 IP-Adressen hinzugefügt, die nicht in der ursprünglichen Liste enthalten sind. Dies ist bereits 22% besser als bei der Verarbeitung von Netzwerklisten-Parser
Neuer Code im ungetesteten Zweig github.com/phoenix-mstu/net_list_minimizer/tree/untested

Source: https://habr.com/ru/post/de438242/

More articles:


All Articles