Индексированный алгоритм поиска в диапазоне для IP-адресов

Question

Учитывая список ACL с 10 миллиардами диапазонов IPv4 в уведомлении CIDR или между двумя IP-адресами:

x.x.x.x/y
x.x.x.x - y.y.y.y

Что такое эффективный алгоритм поиска / индексации для проверки того, что данный IP-адрес соответствует критерию одного или нескольких диапазонов ACL?

Предположим, что большинство определений диапазонов ACL охватывают большое количество блоков класса C.

Индексировать точки с помощью хеш-таблиц легко, но попробуйте, поскольку я не смог бы найти разумный метод для определения того, какие точки покрыты большим списком «линий».

Были некоторые мысли, такие как намеки на индексирование на определенном уровне детализации - скажем, предварительные вычисления на уровне класса C, каждый ACL, покрывающий эту точку, но таблица была бы слишком большой ... Или какое-то дерево KD для динамической установки уровни детализации.

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

Есть ли намеки или указатели в правильном направлении?

Answer 1

Простое Radix Tree , которое использовалось в совпадении с самым длинным префиксом Интернет-маршрутов, может быть масштабировано для хранения узлов, которые представляют большие подсети CIDR, которые перекрывают другие меньшие подсети. Самый длинный поиск совпадений будет проходить через эти узлы, которые также будут выбраны для получения всего набора подсетей CIDR, которые соответствуют IP-адресу.

Теперь, чтобы сохранить диапазоны IP-адресов в одном и том же дереве, мы можем преобразовать каждый диапазон в набор подсетей CIDR . Это всегда можно сделать, хотя в наборе может быть много подсетей (и даже некоторые IP-адреса хоста, то есть адреса CIDR типа IP / 32).

Answer 2

У вас есть 10 миллиардов правил на 4 миллиарда возможных адресов?

Составьте таблицу из 4 миллиардов адресов. Для каждого из 10 миллиардов правил «нарисуйте» адреса, к которым оно относится, и сделайте что-нибудь разумное, когда два или более правил применяются к одному и тому же адресу.

Answer 3

Вы можете просмотреть дерево интервалов , чтобы найти все интервалы, которые перекрываются с любым заданным интервалом или точкой.

Для неперекрывающихся ip-диапазонов вы можете использовать b-дерево или компактные попытки, такие как Массивы Джуди (64 бита) для индексации и поиска (Сохраните start-ip в качестве ключа и end-ip как значение).