Алгоритм несмежного совпадения сетевой маски - PullRequest
Новая
       21

Алгоритм несмежного совпадения сетевой маски

1 голос
/ 23 декабря 2010

Я должен написать действительно очень быстрый алгоритм, чтобы сопоставить IP-адрес со списком групп, где каждая группа определена с использованием записи типа 192.168.0.0/252.255.0.255. Как видите, битовая маска может содержать нули даже посередине, поэтому традиционные алгоритмы «совпадения с самым длинным префиксом» не будут работать. Если IP-адрес соответствует двум группам, он будет назначен группе, содержащей большинство единиц в маске сети.

Я не работаю со многими записями (скажем, <1000) и не хочу использовать структуру данных, требующую большого объема памяти (скажем,> 1-2 МБ), но она действительно должна быть быстрой (конечно я не могу позволить себе линейный поиск).

У вас есть предложения? Спасибо, ребята.

ОБНОВЛЕНИЕ: Я нашел кое-что довольно интересное в http://www.cse.usf.edu/~ligatti/papers/grouper-conf.pdf,, но это все еще слишком требовательно к памяти для моего утопического варианта использования

Ответы [ 3 ]

1 голос
/ 26 декабря 2010

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

псевдокод 

nodeCheck(bitVector, index){//  bitvector is ordering of IP address bits for bushy tree
if myVal=-2 (return -1); //mismatched bit encountered No point continuing.
lVal,Rval=-1;
if (Left !=NULL  && bitvector[index]==0) lVal=Left.nodeCheck(bitvector, index+1);
if (Right !=NULL  && bitvector[index]==1) rVal=Right.nodeCheck(bitvector, index+1);
if (lVal>rVal) return lVal;  // higher numbers have >= number of 1's in netmask.
if (rVal >-1) return rVal;
return myVal;  //the group that getting this far would place you in, -1 if none.

}

Конечно, по скорости вы хотите пропустить коэффициент OO, но концепция та же самая.
Логика немного шаткая, но идея здравая.

Но, учитывая, что у вас есть radixTree, я не хотел слишком глубоко увязнуть в нем. Обход после заказа просто позволяет получить самое длинное соответствие, не становясь слишком странным.

1 голос
/ 28 декабря 2010

Простой ответ - , чтобы ваши биты соответствовали вашему дереву .Сделайте ваше дерево как можно более густым (на самом деле коротким).

более подробный ответ:

Поскольку они имеют одинаковую длину, их порядок не должен иметь значения Позволяет звонить 0.0.0.0/255.255.0.255 A0.0.0.0/255.255.255.0 B входящий 0.0.111.0
октет 1 2 3 4, так что у нас есть правильный порядок

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

Так что это смотрит на значение и проверяет правую ветвь.Правая ветвь является другим узлом, она проверяет октет один и перемещается вниз по левой ветви к следующему узлу, который проверяет октет 2, это проверяет левый (октет 4) и получает -1 (через NULL), правый иполучает -1 (через NULL), поэтому возвращает A (мы назовем его перечислимым типом).

Таким образом, порядок октетов становится 3 1 2 4.

Как правило, вы хотите заказатьбит проверяет, чтобы ранние уровни делали какую-то проверку.В этом случае мы нажимаем 4 до конца, потому что если три попадания (были нулем), проверка октета 4 является пустой тратой и не требует выполнения.Но 1 и 2 должны быть выполнены независимо от результата первой проверки.

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

Плохо построенное действительное дерево может принять порядок 3 4 1 2, поэтому, если первая проверка проходит (0 вместо 111), вторая проверка является пустой тратой, потому что мы уже принадлежим к группе B, независимо от того,значение октета 4.

Удачи.

1 голос
/ 24 декабря 2010

Если вы знаете, со сколькими IP-адресами вы будете иметь дело изначально, я бы сказал, используйте структуру Hash Map.Для ключей этой карты преобразуйте IP в структуру целочисленного типа.Хэш-карты, при условии хорошей хэш-функции (без коллизий), дадут вам O (1) вставку и O (1) поиск.

Если вы не знаете, сколько у вас будет IP, посмотритев использовании кучи Фибоначчи (которую, я думаю, имеет лучшую сложность по времени из всех древовидных структур для вставки / удаления / поиска).

Другой тип структурыможет использовать это Radix Sort .

Есть ли у вас какие-либо конкретные требования относительно того, сколько времени должен занимать алгоритм?«Действительно, действительно, очень быстро» - это довольно расплывчато.

...