company_banner

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

  • Tutorial


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

В этот граф, помимо сетей из списка, добавлены ещё и наибольшие общие подсети соседних сетей. О том, зачем это нужно, читайте далее.


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

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

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

Итак, постановка задачи: нужно написать скрипт, который принимает на вход список 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, то следующими следует схлопывать уже их.

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

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

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

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 из статьи про 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).

    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

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

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

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

UPD
Pochemuk в комментариях указал на ошибку в расчёте веса, я исправил её и теперь, при сжатии того же списка из примера с теми же настройками, добавляется 624925 IP адреса, не входящих в изначальный список. Это уже на 22% лучше, чем при обработке network-list-parser -ом
Новый код в ветке untested github.com/phoenix-mstu/net_list_minimizer/tree/untested
FunCorp
231,00
Разработка развлекательных сервисов
Поделиться публикацией

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

Комментарии 29

    0
    А список FDNS или URL таким образом схлопывать не пробовали?
      0
      Можно уменьшить любой список IP адресов, при условии, что вас устраивают дополнительные адреса, которые войдут в получившийся список.
        0
        Можно — то можно. Весь вопрос в том, как это реализовать?

        В случае IP-адресов мы имеем строго определенное число октетов строго определенной длины. И порядок старшинства и октетов и двоичных цифр в них совпадает — уменьшается слева направо.

        В случае FDNS начинается уже свистопляска. Зоны, домены, поддомены — имеют разную длину имен. В их иерархии старшей является зона. Но она находится справа FDNS. Но естественный порядок сортировки каждой части — сначала по левым символам. Уже заставляет задуматься.

        Возможно ли в этом случае создание подобного эффективного подхода?
          0
          Если я правильно вас понял, то наверно нет, эффективно сжать список доменов не получится. Проблема в том что мы не знаем сколько поддоменов входит в домен, с IP всё проще — если это сеть /24 тогда в ней 256 IP адресов.
        +1
        Делал для блокировки рекламы из разных список в unbound.
        Смысл такой: Если в списке присутсвует domain.com, то из списка нужно исключить subdomain.domain.com, потому что блокировка происходит по
        кусок ads.conf для unbound
        local-zone: «dimain.com» redirect
        local-data: «dimain.com A 0.0.0.0»

        Только для доменов. За код пардоньте. Писалось давно и в питоне не силен.
        ads-domain-filter.py
        #!/usr/bin/env python
        from fileinput import input
        
        data = []
        result = []
        for x in input():
            d = x[::-1]
            if d[1] != ".":
                data.append(d)
            else:
                data.append(d[2:])
        
        data.sort()
        
        i = 0
        while i < len(data)-1:
            dom = data[i]
            j = i+1
            while j < len(data)-1:
                if data[j].startswith(dom+"."):
                    data.pop(j)
                else: break
            i = i+1
        
        for y in data:
            print y[::-1]
        


        использование:
        ads-domain-filter.py input.txt | egrep -v "^$" | sort | uniq > output.txt
        


        Работает не очень шустро, но быстрее чем на bash. Другой вопрос что обновляются списки очень не часто (я раз в полгода примерно запускаю) и не всем нужно 500к рекламных доментов в блокировку.
        Проц Intel® Atom(TM) CPU D2550 @ 1.86GHz
        Заголовок спойлера
        [14:10:18] Remove duplicate entries in 509271 domains.
        [14:24:15] Generating result config. Total 292359 domains
        +4
        В статье нет ответа на главный вопрос™ завис ли роутер MikroTik hAP ac lite (кончилось ли место на его диске) после группировки адресов таким образом?
          +1
          Рутер работает прекрасно, один раз настроил и забыл. Я остановился на списке из 30 000 сетей. Список хранится на raspberry, обновляется раз в час. На роутер попадает по BGP.
          +3
          Сжимаем список IP-адресов наилучшим образом

          Первая ассоциация, пока не прочел про авторство поста — что это Роскомнадзор блог на Хабре запилил и профильный текст написал.

          Интересно, если бы РКН такое захотел сделать, ему бы предоставили скидку на оплату? А иммунитет кармы дали бы, просто чтобы люди не сбежали сразу же? *смайлик*
            0
            Печальный опыт Ksenzov показывает, что вряд ли.
            +1
            Пытаюсь разобраться с «коэффициентами выгоды»…

            Что-то не ладно в Датском королевстве с ними.

            Родительские Кв плывут потому что не учитывают, что в объединяемых записях (если они не отдельные хосты с маской 32 или изначально заданные подсети представляют, а уже «схлопнутые» ранее) уже присутствует некоторое количество фиктивных IP, попавших туда «за компанию».

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

            Может быть удастся даже таким образом вычислять родительские Кв, что они совсем не будут изменяться при схлопывании «деток».
            Но для этого надо в каждой схлопнутой записи хранить не только IP/MASK, но и число подпадающих под нее «лишних» адресов.
              0
              Любое схлопывание можно представить как операцию на исходном списке — убрали такие-то записи, вместо них добавили одну новую. Дальше мы уже работаем с новым списком, в нём нет убранных сетей а схлопнутая сеть становится одной из записей этого списка. Поэтому все коэффициенты должны быть пересчитаны.

              Пример


              Если мы сожмём сеть 192.168.20.0/29, тогда мы уберём 5 записей из списка, и охватим 2 дополнительных ip.
              Если сожмём 192.168.20.0/30 и 192.168.20.4/30, тогда мы уберём 4 записи из списка, и охватим тоже 2 дополнительных ip адреса.

              Т.е. выгоднее сжать большую сеть, поэтому у неё выше коэффициент.

                +1
                Если мы сожмём сеть 192.168.20.0/29, тогда мы уберём 5 записей из списка ...

                Корректнее было бы говорить «уберем 6 записей из списка и добавим одну». Результат тот же, но суть действий описана точнее.

                Насчет пересчета коэффициентов еще раз поясню. Возможно, пересчитывать и надо, но совсем по другому.

                Вот после схлопывания сетей 192.168.20.0/30 и 192.168.20.4/30 имеем такую структуру-кандидата на следующее схлопывание:

                192.168.20.0/29 (станет 8 IP из них 2 лишних)
                192.168.20.0/30 (4 IP из них 1 лишний)
                192.168.20.4/30 (4 IP из них 1 лишний)

                Но на самом деле при схлопывании этой структуры этих двух лишних адресов не появится — они и так уже были лишними в подсетях 192.168.20.0/30 и 192.168.20.4/30.
                И наше новое объединение позволило объединить 2 IP в один без дальнейшего увеличения числа лишних IP. Т.е. Кв такого схлопования будет Inf.

                P.S. А еще у Вас не принимается во внимание, что адреса со всеми нулями и единицами в номере хоста не надо учитывать в числе «лишних», т.к. в подсети их и так нет. Но это уже сложно и неоднозначно, т.к. наше искусственное объединение адресов в подсети далеко не всегда соответствует реально существующим подсетям.
                  0
                  Я вас понял. Отличное замечание, спасибо!

                  Тогда вес нужно считать по формуле:

                  weight = (in_list_records_count — 1) / net_extra_ip_volume_delta

                  Запилю фикс.

                  P.S. А еще у Вас не принимается во внимание, что адреса со всеми нулями и единицами в номере хоста не надо учитывать в числе «лишних», т.к. в подсети их и так нет. Но это уже сложно и неоднозначно, т.к. наше искусственное объединение адресов в подсети далеко не всегда соответствует реально существующим подсетям.

                  Можно не учитывать адреса, последний октет которых равен нулю или 255 — таких точно нет. Подумаю.
                    0
                    Можно не учитывать адреса, последний октет которых равен нулю или 255 — таких точно нет. Подумаю.

                    Не совсем так. Для этого у нас должна быть 24 маска и стандартный вариант выдачи адресов. В других случаях 0 и 255 вполне могут использоваться. Например в 23 маске (или 32/31).
                0
                Родительские Кв плывут потому что не учитывают, что в объединяемых записях… уже присутствует некоторое количество фиктивных IP, попавших туда «за компанию».

                Учитывают. На всякий случай перепроверил код. Объём фейковых IP для каждой сети вычисляется один раз и далее используется именно это значение. Коэффициенты плывут потому-что уменьшается экономия от схлопывания — т.е. если в сети 10 реальных IP адресов и 5 из них уже схлопнуты, тогда при схлопывании мы сможем сэкономить лишь 4 записи в списке.
                +1
                Ладно, ладно. Challenge accepted.
                  0
                  Буду ждать ответной статьи. У меня не решён вопрос с тем, что некоторые IP адреса на самом деле не существуют, например 192.168.0.0 — можно в эту сторону покопать. Хотя подозреваю что сильно качество это не улучшит, всё уже на пределе! Ну и на golang конечно повеселее будет работать.
                  А вообще, спасибо за утилиту, без неё не с чем было бы сравнивать.
                    0
                    Почему не существует? Хороший адрес. В зависимости от маски подсети. Так же и .255 существуют.
                      0
                      Да, все верно.

                      Если маска не /24, а, к примеру, /23, то вполне могут существовать хосты с адресами 192.168.1.0 и 192.168.0.255.

                      Так что, лучше не заморачиваться с этими адресами, а попытаться ускорить работу за счет эффективного хранения данных. Например, в виде перестраиваемого дерева.
                        0
                        Насчёт 23 маски — это любопытно. Не задумывался над этим.

                        Тут две разных задачи:
                        1. Оптимизация скорости выполнения скрипта
                        2. Уменьшение количества фейковых IP в результирующем списке

                        Первое можно существенно улучшить. Второе уже на пределе, если только не получится как-то учитывать нулевые хосты в подсетях. Даже если получится, мне кажется, это особого уменьшения количества фейковых IP не даст.
                          0
                          Вот поэтому и не стоит заморачиваться с нулевыми хостами. Все равно объединение в подсети в данной утилите является искусственным и может не соответствовать реальным подсетям. Если в реале такой подсети нет, то нулевой (или со всеми единицами в номере хоста) адрес в искусственно введенной подсети вполне допустим.

                          А вот насчет повышения скорости вполне стоит подумать. Я не разбирался с алгоритмом, но как мне кажется, при добавлении нового адреса в список происходит его сравнение со всеми адресами из этого списка на предмет выявления наилучшего совпадения. Т.е. временная сложность уже не менее O(n^2).
                          Но на самом деле список еще и пополняется псевдоподсетями, с которыми этот новый IP тоже будет сравниваться. Таким образом производительность будет еще хуже. Как бы не O(log(n)*n^2).

                          Надо подумать о структуре данных, которая бы позволила хранить коэффициенты выгодности, быстро искать максимальные и корректировать их «на лету» при схлопывании.
                            0
                            Т.е. временная сложность уже не менее O(n^2).


                            Это не так. У нас бинарное дерево (ну, нечто наподобие), причём с максимальной глубиной, равной 32. Добавление одного нового IP происходит максимум за 32 операции. При этом создаётся ровно одна псевдоподсеть. Сложность добавления нового элемента можно принять за O(n).

                            Большую часть времени работы скрипта занимает схлопывание сетей. Коэффициенты выгодности и так хранятся в каждом узле и пересчитываются только при изменении дочерних сетей.

                            При схлопывании также не нужно перебирать все сети — каждый узел имеет «стрелочку» в каком направлении находится узел с максимальным весом. Добраться до него также можно за 32 шага вглубь по дереву. Т.е. уменьшение исходного списка на n элементов выполняется за O(n) (это в худшем случае, когда одна операция схлопывания уменьшает длину списка на 1)

                            После схлопывания какой-либо сети, при движении назад происходит пересчёт весов родительских сетей.
                              0
                              Насчет вставки — пожалуй что соглашусь. Если не список, а бинарное дерево, то эффективность будет несколько выше. Но до идеала будет далеко, т.к. многие ветви будут вырожденными — просто не будет их в реестре.

                              А вот «стрелочка» внушает мне опасения…

                              Вот мы схлопнули псевдосеть с наибольшим коэффициентом выгодности… а где находится следующая по выгоде псевдосеть с наибольшим оставшимся коэффициентом? В какой ветви и подветви? Как нам эта стрелочка поможет? Она ведь знала только где находилась наибольшая, но ее уже нет.
                                0
                                Но до идеала будет далеко, т.к. многие ветви будут вырожденными — просто не будет их в реестре.


                                Ветвь создаётся только при добавлении IP из исходного списка. Наверно мы имеем что-то около log2(n) * n узлов в дереве, где n — это размер исходного списка.

                                а где находится следующая по выгоде псевдосеть с наибольшим оставшимся коэффициентом?


                                «стрелочка» (наибольший вес в поддереве) в родительских элементах тоже пересчитывается при движении назад. Более того, если при движении назад мы видим что есть ещё одна сеть с таким же весом, как только-что сжатая, мы сразу же начинаем сжимать её, не возвращаясь к корневому элементу.
                                «наибольший вес в поддереве» для корневого узла означает наибольший вес во всём дереве.
                                  0
                                  Ага… Т.е. при рекурсивном подъеме после «схлопывания» мы не только корректируем собственные коэффициенты выгодности в каждом узле, но и переписываем в них информацию о положении и величине наибольшего коэффициента выгодности в их подветвях?
                                    0
                                    Именно так. Это простая операция

                                    self.max_child_weight = 0
                                    for Child in self.children:    
                                        self.max_child_weight = max(self.max_child_weight, Child.weight, Child.max_child_weight)
                                    
                                      0
                                      Из данного фрагмента кода видно, что вычисляется наибольший вес, но не видно, какому потомку или самому узлу он принадлежит. А, следовательно, при попадании в узел все равно придется просматривать всех потомков, чтобы определить, по какой именно ветви следует продолжить поисковый спуск.

                                      Можно подумать вот над чем: Не хранить в узле его собственный вес и дополнительно лучший вес, а только лучший вес и флаг, где он лежит:

                                      0 — лучший вес принадлежит этому узлу (узел является листом и не имеет потомков);
                                      1 — лучший вес находится в левой ветви;
                                      2 — лучший вес находится в правой ветви;
                                      3 — лучший вес принадлежит этому узлу (узел не является листом и имеет 1 или 2 потомка).

                                      Надеюсь, под словами «бинарное дерево» вы понимаете именно то, что каждый узел имеет не более двух потомков, жестко разделенных на «правый» и «левый»?

                                      Тогда процедура рекурсивного подъема с корректировкой чуть усложнится, но общая структура будет проще и сам рекурсивный спуск с поиском будет проще.
                                        0
                                        Да, в каждом узле всего два потомка. Они правда не разделены на правый и левый (поэтому я и называю эту структуру «что-то вроде бинарного дерева»). Посмотреть на два числа ничуть не сложнее чем на флаг, при этом флаг сложнее обновлять — нужно точно также посмотреть на числа и выставить значение.

                                        При этом мне нужен максимальный вес в корневом элементе — т.е. всё-равно нужно пробрасывать его в корень.
                              0
                              Старое доброе бинарное дерево? Добавление элемента в дерево будет простым, а для обхода всё равно по всему списку придётся бегать в поисках коэффициентов. Но схлопывание и корректировка будут вполне быстры.
                              (на правах шутки) А если у нас есть много памяти, то можно все адреса развернуть в линейную область памяти и обращаться к нужным весам простой математической операцией!

                              ______
                              Надо было обновить комментарий. Оказалось, что так оно и есть.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое