- PVSM.RU - https://www.pvsm.ru -
Как-то я прочитал на Хабре статью [1] про настройку BGP на роутере. Инструкции оттуда можно использовать для настройки домашнего роутера так, чтобы трафик на определённые IP-адреса шёл через другой канал. Однако здесь есть проблема: список IP-адресов может быть очень большим.
В этот граф, помимо сетей из списка, добавлены ещё и наибольшие общие подсети соседних сетей. О том, зачем это нужно, читайте далее.
Так выглядело дерево сетей от Роскомнадзора в мае 2018 года.
Сначала я попробовал добавить весь список через /ip route add в мой MikroTik hAP ac lite — на роутере кончилось место на диске. Затем загрузил через BGP все адреса в память — роутер немного поработал и завис. Стало очевидно, что список нужно урезать.
В статье [1] упоминается утилита [2] network-list-parser от читателя Unsacrificed [3]. Она делает то, что мне нужно, но увидел я её уже после того, как начал изобретать свой велосипед. Потом уже доделывал из интереса, потому как то, что у меня получилось, работает качественнее, хоть и существенно медленнее.
Итак, постановка задачи: нужно написать скрипт, который принимает на вход список IP-адресов и сетей и укорачивает его до указанного размера. При этом новый список должен охватывать все адреса из старого, а количество новых адресов, вынужденно в него добавленных, должно быть минимальным.
Начнём с построения графа всех исходных сетей (то, что на картинке выше). Корневым узлом будет сеть 0.0.0.0/0. При добавлении новой подсети A находим в дереве подсеть B, чтобы A и B находились в подсети C и при этом размер подсети C был минимальным (маска максимальной). Другими словами, количество общих битов подсетей A и B должно быть максимальным. Добавляем эту общую подсеть в дерево, а внутрь переносим подсети A и B. Наверное, это можно назвать бинарным деревом.
Например, построим дерево из двух подсетей (192.168.0.1/32 и 192.168.33.0/24):
Получим дерево:
Если сюда добавить, скажем, сеть 192.168.150.150/32, тогда, дерево будет выглядеть так:
Оранжевым тут отмечены общие подсети, добавленные при построении дерева. Именно эти общие подсети мы и будем «схлопывать» для уменьшения размера списка. Например, если схлопнуть узел 192.168.0.0/16, тогда мы уменьшим размер списка сетей на 2 (было 3 сети из исходного списка, стала 1), но при этом дополнительно охватим 65536-1-1-256=65278 IP-адреса, которые не входили в наш исходный список.
Удобно для каждого узла рассчитать «коэффициент выгоды от схлопывания», показывающий количество IP-адресов, которые будут дополнительно добавлены на каждую из удалённых из списка записей:
weight_reversed = net_extra_ip_volume / (in_list_records_count — 1)
Мы будем использовать weight = 1 / weight_reversed, т.к. это удобнее. Любопытно, что вес может быть равен бесконечности, если, к примеру, в списке есть две сети /32, которые вместе составляют одну большую сеть /31.
Таким образом, чем больше weight, тем выгоднее такую сеть схлопнуть.
Теперь можно посчитать вес для всех узлов в сети, отсортировать узлы по весу и схлопывать подсети до тех пор, пока не получим нужный нам размер списка. Однако тут есть сложность: в тот момент, когда мы схлопываем какую-нибудь сеть, меняются веса всех родительских сетей.
Например, у нас есть дерево с рассчитанными весами:
Схлопнем подсеть 192.168.0.0/30:
Вес родительского узла уменьшился. Если в дереве есть узлы с весом больше, чем 0.166, то следующими следует схлопывать уже их.
В итоге сжатие списка приходится выполнять рекурсивно. Алгоритм примерно такой:
Интереснее всего наблюдать за алгоритмом в движении. Вот пример для списка сетей:
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
Тут одинаковые по структуре подсети 192.168.0.0/24 и 192.168.150.0/24 — так лучше видно, как при сжатии алгоритм перепрыгивает из одной ветки в другую. Подсеть 192.168.20.0/24 добавил для того, чтобы показать, что иногда выгоднее сжимать родительскую сеть, чем дочернюю. Обратите внимание на подсеть 192.168.20.0/30: после заполнения дерева её вес меньше, чем у родительской подсети.
Заполнение дерева:
Тут чёрный шрифт — настоящие сети из исходного списка. Жёлтый — добавленные сети. Синий — вес узла. Красный — текущая сеть. Розовый — схлопнутая сеть.
Сжатие:
Была мысль ускорить алгоритм схлопывания сетей: для этого не обязательно на каждой итерации схлопывать только сети с максимальным весом. Можно заранее подобрать значение веса, которое даст нам список нужного размера. Подобрать можно бинарным поиском, т.е. сжимать с определённым весом и смотреть, какой размер списка получается на выходе. Правда, для этого нужно в два раза больше памяти и переписывать код — у меня попросту не дошли руки.
Теперь осталось сравнить с network-list-parser [2] из статьи про BGP.
Плюсы моего скрипта:
2. Запускаем
./network-list-parser-darwin-386-1.2.bin -src-file parsed.txt -dst-file parsed1.txt 2>&1
и получаем сжатый список, смотрим вывод, там есть строчка “Add 7.3% IPs coverage (798761).”
В файле parsed1.txt 16649 записей.
3. Запускаем
python3 minimize_net_list.py parsed.txt 16649.
Видим строчку ### not real ips: 718479.
У получившегося скрипта я вижу только один недостаток: он долго работает и требует много памяти. На моём MacBook список жмётся 5 секунд. На Raspberry — полторы минуты. С РyРy3 на Маке быстрее, на Raspberry PyPy3 поставить не смог. Network-list-parser летает и там, и там.
В целом эту схему имеет смысл использовать только перфекционистам, т.к. все остальные тратить столько вычислительных ресурсов ради 10% сэкономленных сетей вряд ли будут. Ну и немного удобнее, да.
Ссылка на проект в GitHub github.com/phoenix-mstu/net_list_minimizer [4]
Запускать так:
python3 minimize_net_list.py real_net_list_example.txt 30000 | grep -v ### > result.txt
Вот, собственно, и всё.
Автор: Григорий Кузовников
Источник [5]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/307169
Ссылки в тексте:
[1] статью: https://habr.com/ru/post/354282/
[2] утилита: https://github.com/unsacrificed/network-list-parser
[3] Unsacrificed: https://habr.com/ru/users/unsacrificed/
[4] github.com/phoenix-mstu/net_list_minimizer: https://github.com/phoenix-mstu/net_list_minimizer
[5] Источник: https://habr.com/ru/post/438242/?utm_source=habrahabr&utm_medium=rss&utm_campaign=438242
Нажмите здесь для печати.