Хабрахабр

Сжимаем список IP-адресов наилучшим образом

Инструкции оттуда можно использовать для настройки домашнего роутера так, чтобы трафик на определённые IP-адреса шёл через другой канал. Как-то я прочитал на Хабре статью про настройку BGP на роутере. О том, зачем это нужно, читайте далее. Однако здесь есть проблема: список IP-адресов может быть очень большим.
В этот граф, помимо сетей из списка, добавлены ещё и наибольшие общие подсети соседних сетей.


Так выглядело дерево сетей от Роскомнадзора в мае 2018 года.

Затем загрузил через BGP все адреса в память — роутер немного поработал и завис. Сначала я попробовал добавить весь список через /ip route add в мой MikroTik hAP ac lite — на роутере кончилось место на диске. Стало очевидно, что список нужно урезать.

Она делает то, что мне нужно, но увидел я её уже после того, как начал изобретать свой велосипед. В статье упоминается утилита network-list-parser от хабраюзера Unsacrificed. Потом уже доделывал из интереса, потому как то, что у меня получилось, работает качественнее, хоть и существенно медленнее.

При этом новый список должен охватывать все адреса из старого, а количество новых адресов, вынужденно в него добавленных, должно быть минимальным. Итак, постановка задачи: нужно написать скрипт, который принимает на вход список IP-адресов и сетей и укорачивает его до указанного размера.

Корневым узлом будет сеть 0. Начнём с построения графа всех исходных сетей (то, что на картинке выше). 0. 0. При добавлении новой подсети A находим в дереве подсеть B, чтобы A и B находились в подсети C и при этом размер подсети C был минимальным (маска максимальной). 0/0. Добавляем эту общую подсеть в дерево, а внутрь переносим подсети A и B. Другими словами, количество общих битов подсетей A и B должно быть максимальным. Наверное, это можно назвать бинарным деревом.

168. Например, построим дерево из двух подсетей (192. 1/32 и 192. 0. 33. 168. 0/24):

Получим дерево:

168. Если сюда добавить, скажем, сеть 192. 150/32, тогда, дерево будет выглядеть так: 150.

Именно эти общие подсети мы и будем «схлопывать» для уменьшения размера списка. Оранжевым тут отмечены общие подсети, добавленные при построении дерева. 168. Например, если схлопнуть узел 192. 0/16, тогда мы уменьшим размер списка сетей на 2 (было 3 сети из исходного списка, стала 1), но при этом дополнительно охватим 65536-1-1-256=65278 IP-адреса, которые не входили в наш исходный список. 0.

Удобно для каждого узла рассчитать «коэффициент выгоды от схлопывания», показывающий количество IP-адресов, которые будут дополнительно добавлены на каждую из удалённых из списка записей:

weight_reversed = net_extra_ip_volume / (in_list_records_count — 1)

это удобнее. Мы будем использовать weight = 1 / weight_reversed, т.к. Любопытно, что вес может быть равен бесконечности, если, к примеру, в списке есть две сети /32, которые вместе составляют одну большую сеть /31.

Таким образом, чем больше weight, тем выгоднее такую сеть схлопнуть.

Однако тут есть сложность: в тот момент, когда мы схлопываем какую-нибудь сеть, меняются веса всех родительских сетей. Теперь можно посчитать вес для всех узлов в сети, отсортировать узлы по весу и схлопывать подсети до тех пор, пока не получим нужный нам размер списка.

Например, у нас есть дерево с рассчитанными весами:

168. Схлопнем подсеть 192. 0/30: 0.

Если в дереве есть узлы с весом больше, чем 0. Вес родительского узла уменьшился. 166, то следующими следует схлопывать уже их.

Алгоритм примерно такой: В итоге сжатие списка приходится выполнять рекурсивно.

  1. Рассчитываем веса для всех узлов.
  2. Для каждого узла храним максимальный вес дочернего узла (Wmax).
  3. Получается, что Wmax корневого узла — это максимальный вес узла во всём дереве (может быть несколько узлов с весом, равным Wmax).
  4. Рекурсивно сжимаем все сети с весом, равным Wmax корневого узла. При этом пересчитываем веса. Возвращаемся в корневой узел.
  5. Wmax корневого узла уменьшился — выполняем п.4 до тех пор, пока не получим нужный размер списка сетей.

Вот пример для списка сетей: Интереснее всего наблюдать за алгоритмом в движении.

168. 192. 1
192. 0. 0. 168. 168. 2
192. 8/29
192. 0. 150. 168. 168. 1
192. 2
192. 150. 150. 168. 168. 8/29
192. 1
192. 20. 20. 168. 168. 2
192. 3
192. 20. 20. 168. 168. 4
192. 5
192. 20. 20. 168. 168. 6
192. 7 20.

168. Тут одинаковые по структуре подсети 192. 0/24 и 192. 0. 150. 168. Подсеть 192. 0/24 — так лучше видно, как при сжатии алгоритм перепрыгивает из одной ветки в другую. 20. 168. Обратите внимание на подсеть 192. 0/24 добавил для того, чтобы показать, что иногда выгоднее сжимать родительскую сеть, чем дочернюю. 20. 168. 0/30: после заполнения дерева её вес меньше, чем у родительской подсети.

Заполнение дерева:

Жёлтый — добавленные сети. Тут чёрный шрифт — настоящие сети из исходного списка. Красный — текущая сеть. Синий — вес узла. Розовый — схлопнутая сеть.

Сжатие:

Можно заранее подобрать значение веса, которое даст нам список нужного размера. Была мысль ускорить алгоритм схлопывания сетей: для этого не обязательно на каждой итерации схлопывать только сети с максимальным весом. сжимать с определённым весом и смотреть, какой размер списка получается на выходе. Подобрать можно бинарным поиском, т.е. Правда, для этого нужно в два раза больше памяти и переписывать код — у меня попросту не дошли руки.

Теперь осталось сравнить с network-list-parser из статьи про BGP.

Плюсы моего скрипта:

  1. Удобнее настройка: достаточно указать требуемый размер списка сетей, и на выходе будет список именно такого размера. У network-list-parser множество ручек, и нужно подобрать их сочетание.
  2. Степень сжатия адаптируется к исходному списку. Если из списка убрать какие-то сети, то мы получим меньше дополнительных адресов, если добавить — больше. При этом размер результирующего списка будет постоянным. Можно подобрать максимальный размер, который способен обработать роутер, и не беспокоиться о том, что в какой-то момент список станет слишком большим.
  3. Полученный список содержит минимально возможное количество дополнительных сетей. На тестовом списке из GitHub мой алгоритм дал 718479 дополнительных IP-адреса, а network-list-parser — 798761. Разница всего 10%.

    Как я это рассчитал? Смотрим

    1. Запускаем
    ./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
    и получаем очищенный список без мусора и частично уменьшенный. Сравнивать буду качество сжатия parsed.txt. (без этого шага были проблемы с оценкой того, сколько фейковых IP добавляет network-list-parser).

    Запускаем
    ./network-list-parser-darwin-386-1. 2. 3% IPs coverage (798761).”
    В файле parsed1.txt 16649 записей. 2.bin -src-file parsed.txt -dst-file parsed1.txt 2>&1
    и получаем сжатый список, смотрим вывод, там есть строчка “Add 7.

    Запускаем
    python3 minimize_net_list.py parsed.txt 16649.
    Видим строчку ### not real ips: 718479.
    3.

На моём MacBook список жмётся 5 секунд. У получившегося скрипта я вижу только один недостаток: он долго работает и требует много памяти. С РyРy3 на Маке быстрее, на Raspberry PyPy3 поставить не смог. На Raspberry — полторы минуты. Network-list-parser летает и там, и там.

все остальные тратить столько вычислительных ресурсов ради 10% сэкономленных сетей вряд ли будут. В целом эту схему имеет смысл использовать только перфекционистам, т.к. Ну и немного удобнее, да.

Ссылка на проект в GitHub github.com/phoenix-mstu/net_list_minimizer

Запускать так:

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

Вот, собственно, и всё.

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»