TCP / IP эффективная фильтрация пакетов

Question

Я пытаюсь создать алгоритм для фильтрации пакетов TCP / IP на основе как IP-адресов источника и назначения, так и портов назначения и источника. По сути, у меня есть набор правил, который определяет диапазон IP-адресов, например, 192.168.0.0/24, для IP-адреса назначения и источника и эквивалент для портов назначения и порта ([1:65535]).

Короче говоря, учитывая пакет, я хотел бы выяснить, какие правила актуальны для его IP-адресов и портов. В настоящее время единственная идея, которую я имею до сих пор, состоит в том, чтобы создать Trie из IP-адресов источника или назначения, которые бы быстро фильтровали любой из них, но все же потребовали бы линейного поиска для остальных параметров и привели бы к сложности * 1005. * для n правил. Есть ли лучший способ уменьшить сложность времени?

Answer 1

Если вы закодируете IP как целое число в диапазоне [0, 2 ^ 32], вы можете определить исходный и целевой диапазоны с помощью четырехмерного прямоугольника

min = [src_ip_min, src_prt_min, dst_ip_min, dst_prt_min]
max = [src_ip_max, src_prt_max, dst_ip_max, dst_prt_max]

Вы можете индексировать многомерные прямоугольники, используяструктура пространственного индекса, такая как R-Tree , для эффективного ответа на пространственные запросы.В вашем случае вам понадобится поиск по диапазону (диапазон = 0), чтобы получить все прямоугольники (= правила), которые применяются к определенному запросу.

4 измерения по-прежнему должны хорошо индексироваться, поэтому в зависимости от распределения диапазонаВы можете ожидать время запроса ближе к O(log n)