On Mon, Dec 23, 2002 at 03:49:45PM +0200, Andrey Blochintsev wrote:
Alexandre Snarskii wrote:
On Mon, Dec 23, 2002 at 02:05:08PM +0200, Alex Radetsky wrote:
On Mon, Dec 23, 2002 at 01:49:46PM +0200, Michail Litvak wrote:
Hello Anatol V Sukhomlyn!
Mon, Dec 23, 2002 at 01:42:21PM +0200, anatols wrote about "[uanog] match ip address!":
AVS> на примере это выглядит так AVS> есть таблица 10.10.10.0/24 AVS> 20.20.20.0/22 AVS> и так далее AVS> вот и нужно чтобы при проверке адреса 10.10.10.1/24 находилось его AVS> вхождение в таблицу. AVS> Сейчас это делается перебором всех значений таблицы, что занимает достаточно AVS> много времени :(. AVS> Может каким-то образом захешировать значения таблицы?
Если я правильно понимаю - то это делается через radix tree, реализацию смотреть внутрях linux kernel или *BSD. /me когда-то писал перловый модуль, но оно потерялось :(
Совсем недавно я размышлял на эту тему и выдумал вот что. У меня есть пакет уже сниференный libpcap. Есть строка вида x.x.x.x[/x]. Надо сверить входит ли src->addr || dst->addr в указанную сеть. И вот что получилось. Боюсь, что /me выдумал велосипед, но этот велосипед, по крайней мере работает.
Угу. Для одной сети он работает даже вполне хорошо, хотя я реализовывал такую функцию и побыстрее :)) А вот для ситуации, когда у тебя таких сетей (на вложенность в которые нужно проверять) много, и когда они сами могут быть вложенными - все становится гораздо хужее :)
Если не особо задумываться и делать самому (а не тянуть готовый код или библиотеку), и плюнуть на "non-contiguous masks" то достаточно адекватную скорость можно получить если исходную таблицу "поделить" на 33 (по /0, /1, ..., /31, /32), каждую из них просто отсортивать и проводить по ним двоичный поиск. (тем более если нужно искать строго A.B.C.D/E, то искать нужно будеть только в одной таблице).
Если у тебя в таблице есть 10.0.0.0/8, а ищется конкретный /32 (а именно это и есть задача из реальной жизни), то тебе приедтся искать его сначала в /32, потом в /31,/30../9 и только в /8 ты его найдешь.
PS: да не почтут за сильный offtopic: очередной писанный мной flow-collector/analyzer на сейчас обрабатывает 800 flow-пакетов в секунду на хиленьком celeron'е. Больше просто
"хиленький" - это как ?
Еще раз - там больше и не нужно. На stress-test'ах на cel-600 поулчалось ~10K пакетов/сек (при том, что на том же cel крутились иксы, mpg123, mozilla и прочая консоль :)) ).
Мой полностью perl-овый (!) анализатор обрабатывал на PIII-600 ~ 3000 flow-пакетов/сек (на таблице ~ 1000 записей, причем половина времени - это раскладываение результатов по ~ 500м .rrd файлам). ;) правда тоже с другим алгоритмом.
на той инсталляции нет :) В freeware его, правда, не будет. Только за деньги. =================================================================== uanog mailing list. To Unsubscribe: send mail to majordomo@uanog.kiev.ua with "unsubscribe uanog" in the body of the message =================================================================== uanog mailing list. To Unsubscribe: send mail to majordomo@uanog.kiev.ua with "unsubscribe uanog" in the body of the message