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

Учитывая список 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 для динамического набора уровни детализации.

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

Любые подсказки или указатели в правильном направлении?

Ответ 1

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

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

Ответ 2

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

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

Ответ 3

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

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