Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Сети > router

Автор: box 12.5.2014, 00:36

всем привет!
надо согласно исходный сетей раскидать пакеты по vlan
список сетей приводим к uint32_t и загоняем в массив по принцыпу lower[] upper[] что соответсвует нижней и верхней границы сети потом в цыкле определяем принадлежность ип к сети :

Код


  uint32_t ipint = IPToUInt(new_ip);
  for(int i=0; i < 19000; i++){
  targ->flag = 0;
  if( ipint >= lower[i] ){
    if( ipint <= upper[i] ){

    uint32_t lower1 = lower[i];   
    uint32_t upper1 = upper[i];
  
    if(lower1 > 0 && upper1 > 0){
        targ->count_ua_true++;    
        targ->flag = 1;
        break;
        }
    }
}

}

 if(targ->flag == 0)    
        targ->count_ua_false++;

проблема в следуещем , когда загружаеш в массив сетей ну хотя бы ua-ix (19000 сетей) получается что каждый пакет надо прогнать по 19000 элементам массива что очень тормозит работу програмы на практике выяснил что такой алгоритм поиска не выдерживает более 42000 - 43000 входящий пакетов в секунду даже при работе в 8 треадов
подскажите более быстрый алгоритм

Автор: tzirechnoy 12.5.2014, 10:14

Самое, пожалуй, быстрое -- построить perfect hash function.
Впрочем, возможно, что ты в этой математике закопаешься -- тогда можно просто hash, дажэ очень тупой (типа два средних байта номера сети), примерно в два размера таблички.

Или взять btree или какой-нибудь вариант trie (их сейчас можно найти сделанными на макросах, вполне эффективные) -- реализацыя будет во-первых довольно эффективной на любых размерах массива (в варианте с hash -- только примерно соответствующем первоначальному предположэнию), кроме того, trie обычно компактнее, что, например, позволит влезть всей структуре в L2 cache.

PS А, да, про cache: ещё, размеется, батчинг: постарайся проводить этот поиск для множэства пакетов подряд. Чтобы твои данные про сети висели таки в кэшах во время работы алгоритма. Т.е. накапливаешь тысячу или десяток тысяч пакетов -- и потОм распределяешь.

Автор: feodorv 12.5.2014, 10:44

Аналог mod_geoip? Конечно, дерево, последовательный перебор слишком затратный. Насколько я помню, в mod_geoip используется специфическое http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D0%B2%D0%B0%D0%BB%D0%BE%D0%B2_%28interval_tree%29_%D0%B8_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D1%81_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE%D0%BC_%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D0%B2%D0%B0%D0%BB%D0%BE%D0%B2.

Но если у Вас все подсети имеют "правильный" вид (то есть с масками вида /20, /24 ...), то можно обойтись простым бинарным деревом, максимальное количество сравнений тогда будет не более 30. Правда, нужно будет учесть, что для конкретного IP нужно будет выбирать как можно http://blog.selectel.ru/sistema-ucheta-ip-adresov/ (с максимальной маской).

Автор: box 12.5.2014, 22:03

речь идет о 10g ethernet а именно о 14млн пакетов в сек так что тут ни дерево ни какие хаши боюсь не справятся , надо будет попробовать перенести поиск по сетям на cuda

Автор: GremlinProg 13.5.2014, 06:29

Цитата(box @ 13.5.2014, 00:03

)

речь идет о 10g ethernet а именно о 14млн пакетов в сек так что тут ни дерево ни какие хаши боюсь не справятся

Думаю, Вы не до конца понимаете, что дают Вам деревья. Feodorv, в таком случае даже преувеличил число сравнений для поиска: на 14млн пакетов будет порядка 7 сравнений на поиск. Конечно, я имею ввиду сбалансированные деревья и бинарный поиск. Посмотрите вот для примера: http://ru.wikipedia.org/wiki/Красно-чёрное_дерево .

Автор: tzirechnoy 13.5.2014, 09:33

Цитата

А если Вы сами всё так хорошо знаете -- то зачем здесь что-то спрашываете?