Добрый день! Подскажите пожалуйста оптимальный способ (по скорости) находить значенмя ip_address и ip_mask в таблице данных где 1-е поле ip_address 2-e ip_mask. (строки в таблице уникальны). на примере это выглядит так есть таблица 10.10.10.0/24 20.20.20.0/22 и так далее вот и нужно чтобы при проверке адреса 10.10.10.1/24 находилось его вхождение в таблицу. Сейчас это делается перебором всех значений таблицы, что занимает достаточно много времени :(. Может каким-то образом захешировать значения таблицы? Спасибо. ____________________________________________________________________ Anatol V.Sukhomlyn NOC ISP UkrNet +380 44 2358555 anatols@ukr.net AVS86-RIPE =================================================================== uanog mailing list. To Unsubscribe: send mail to majordomo@uanog.kiev.ua with "unsubscribe uanog" in the body of the message
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 когда-то писал перловый модуль, но оно потерялось :( CU! -- //ShaD0w =================================================================== uanog mailing list. To Unsubscribe: send mail to majordomo@uanog.kiev.ua with "unsubscribe uanog" in the body of the message
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 выдумал велосипед, но этот велосипед, по крайней мере работает. -=- Cut isInIP-alhoritm.txt -=- unsigned long sfx[] = { 0x00000000, 0x80000000, 0xc0000000, 0xe0000000, 0xf0000000, 0xf8000000, 0xfc000000, 0xfe000000, 0xff000000, 0xff800000, 0xffc00000, 0xffe00000, 0xfff00000, 0xfff80000, 0xfffc0000, 0xfffe0000, 0xffff0000, 0xffff8000, 0xffffc000, 0xffffe000, 0xfffff000, 0xfffff800, 0xfffffc00, 0xfffffe00, 0xffffff00, 0xffffff80, 0xffffffc0, 0xffffffe0, 0xfffffff0, 0xfffffff8, 0xfffffffc, 0xfffffffe, 0xffffffff }; int isInIP(char* ip, struct u_packet* pkt) { char *p; char buf[255]; char fqdn[15]; char suffix[5]; int i_suffix; int rc; struct in_addr in; unsigned long _min_; unsigned long _max_; unsigned long _sin_; unsigned long _din_; /* ip - параметр вида ipaddr[/suffix] тип char* p - ноу комментс */ /* 1. Проверяем дан ли нам один хост в строке ip */ sprintf(buf,ip); p = strtok(buf,"/"); if (p == NULL) return 0; sprintf(fqdn,ltrim(rtrim(p))); p = strtok(NULL,"\n"); if (p == NULL) // there is no suffix suffix[0] = '\0'; else sprintf(suffix,p); HOST: if (suffix[0] == '\0') { myitoa(buf,pkt->src); // альтернативная функция перевода in-addr to char* rc = strncmp(buf,fqdn,strlen(fqdn)); if (rc == 0) return 1; myitoa(buf,pkt->dst); rc = strncmp(buf,fqdn,strlen(fqdn)); if (rc == 0) return 1; return 0; } /* 2. Теперь если присутствует суффикс */ i_suffix = atoi(suffix); if (i_suffix == 32) { suffix[0] = '\0'; goto HOST; } rc = inet_aton(fqdn,&in); /* Получаем минимальное и максимальное значение адреса в указанной сети */ _min_ = ntohl(in.s_addr); _max_ = _min_ + (0xffffffff-sfx[i_suffix]); /* sprintf(buf,"min=%lx, max=%lx, pkt src=%lx pkt dst=%lx", _min_,_max_,ntohl(pkt->src),ntohl(pkt->dst)); __log__(buf); */ // И проверяем. _sin_ = ntohl(pkt->src); if ((_sin_>=_min_) && (_sin_<=_max_)) return 1; _din_ = ntohl(pkt->dst); if ((_din_>=_min_) && (_din_<=_max_)) return 1; return 0; } -=- -- Alex Radetsky AR2657-RIPE RAD-UANIC =================================================================== uanog mailing list. To Unsubscribe: send mail to majordomo@uanog.kiev.ua with "unsubscribe uanog" in the body of the message
On Mon, Dec 23, 2002 at 01:42:21PM +0200, Anatol V Sukhomlyn wrote:
Добрый день! Подскажите пожалуйста оптимальный способ (по скорости) находить значенмя ip_address и ip_mask в таблице данных где 1-е поле ip_address 2-e ip_mask. (строки в таблице уникальны). на примере это выглядит так есть таблица 10.10.10.0/24 20.20.20.0/22 и так далее вот и нужно чтобы при проверке адреса 10.10.10.1/24 находилось его вхождение в таблицу. Сейчас это делается перебором всех значений таблицы, что занимает достаточно много времени :(.
radix tree, particle tree..
Может каким-то образом захешировать значения таблицы?
Не поможет. =================================================================== uanog mailing list. To Unsubscribe: send mail to majordomo@uanog.kiev.ua with "unsubscribe uanog" in the body of the message
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 выдумал велосипед, но этот велосипед, по крайней мере работает.
Угу. Для одной сети он работает даже вполне хорошо, хотя я реализовывал такую функцию и побыстрее :)) А вот для ситуации, когда у тебя таких сетей (на вложенность в которые нужно проверять) много, и когда они сами могут быть вложенными - все становится гораздо хужее :) PS: да не почтут за сильный offtopic: очередной писанный мной flow-collector/analyzer на сейчас обрабатывает 800 flow-пакетов в секунду на хиленьком celeron'е. Больше просто на той инсталляции нет :) В freeware его, правда, не будет. Только за деньги. =================================================================== uanog mailing list. To Unsubscribe: send mail to majordomo@uanog.kiev.ua with "unsubscribe uanog" in the body of the message
On Mon, Dec 23, 2002 at 03:48:54PM +0300, Alexandre Snarskii wrote:
Угу. Для одной сети он работает даже вполне хорошо, Для чего и писалось. ;)
хотя я реализовывал такую функцию и побыстрее :)) Кардинально другой алгоритм? Или просто оптимизация похожего?
А вот для ситуации, когда у тебя таких сетей (на вложенность в которые нужно проверять) много, и когда они сами могут быть вложенными - все становится гораздо хужее :)
Ой. Тут думать надо. Кнута почитать перед сном. ;)
PS: да не почтут за сильный offtopic: очередной писанный мной flow-collector/analyzer на сейчас обрабатывает 800 flow-пакетов в секунду на хиленьком celeron'е. Больше просто на той инсталляции нет :) В freeware его, правда, не будет. Только за деньги.
(Хитро прищурив глаза) Я тебе мылом недельки через две отвечу ;))) -- Alex Radetsky AR2657-RIPE RAD-UANIC =================================================================== uanog mailing list. To Unsubscribe: send mail to majordomo@uanog.kiev.ua with "unsubscribe uanog" in the body of the message
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, то искать нужно будеть только в одной таблице).
PS: да не почтут за сильный offtopic: очередной писанный мной flow-collector/analyzer на сейчас обрабатывает 800 flow-пакетов в секунду на хиленьком celeron'е. Больше просто
"хиленький" - это как ? Мой полностью 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
On Mon, Dec 23, 2002 at 03:09:09PM +0200, Alex Radetsky wrote:
On Mon, Dec 23, 2002 at 03:48:54PM +0300, Alexandre Snarskii wrote:
Угу. Для одной сети он работает даже вполне хорошо, Для чего и писалось. ;)
хотя я реализовывал такую функцию и побыстрее :)) Кардинально другой алгоритм? Или просто оптимизация похожего?
Представим себе, что у нас есть network и masklen, на вложенность в которую нужно проверить. Тогда, /* shift на 32 разряда на 32-bit регистрах не работает */ uint32_t mask=(masklen==0)?0:htonl(0xffffffffl<<(32-masklen)); if(network!=(network&masklen)) { printf("inconsistent address&masklen\n"); return -1; }; if(src_ip&mask==network) return 1; if(dst_ip&mask==network) return 1; return 0; Это из головы, а не из рабочего кода, так что... However, работает быстрее твоего (в части сравнения, parsing не считаем) раза в два-три быстрее. =================================================================== uanog mailing list. To Unsubscribe: send mail to majordomo@uanog.kiev.ua with "unsubscribe uanog" in the body of the message
On Mon, Dec 23, 2002 at 01:49:46PM +0200, Michail Litvak wrote:
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 когда-то писал перловый модуль, но оно потерялось :(
вариант - table = set of cidr-element cidr-element = [ base-address , mask ] тогда range-table = set of [ base-address & mask , high-address ] high-address = base-address & mask + (~mask + 1) (все диапазоны адресов) или low-table = set of [ base-address ] hi-table = set of [ high-address ] теперь сортируем обе таблицы по возрастанию и ищем: low-index = minimal l : low-table [ l ] > addr high-index = minimal h : high-table [ h ] < addr теперь: addr входит во все cidr-блоки с номерами от 1..(l-1) до (h+1..N) (это утверждение надо обдумать..) =================================================================== uanog mailing list. To Unsubscribe: send mail to majordomo@uanog.kiev.ua with "unsubscribe uanog" in the body of the message
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
participants (6)
-
Alex Radetsky -
Alexandre Snarskii -
Anatol V Sukhomlyn -
bag＠ua.net -
Dmitry Kohmanyuk -
Michail Litvak