хэш-функция для порта src dest ip +

Question

Итак, я рассматриваю различные хеш-функции, которые можно использовать для хэширования 4-х IP-адресов и порта для определения потоков.

Один, с которым я столкнулся, был

((size_t)(key.src.s_addr) * 59) ^
((size_t)(key.dst.s_addr)) ^
((size_t)(key.sport) << 16) ^
((size_t)(key.dport)) ^
((size_t)(key.proto));

Теперь, для моей жизни, я не могу объяснить использованное простое число (59). почему не 31, а затем зачем все испортить, умножив вид спорта на степень 2. Есть ли лучшая хеш-функция для IP-адресов?

Answer 1

Простое число используется, потому что, когда одно значение умножается на простое число, оно имеет большую вероятность остаться уникальным, когда поверх него накапливаются другие подобные операции. Конкретное значение 59 может быть выбрано произвольно или может быть преднамеренным. Сложно сказать. Возможно, что 59 имел тенденцию генерировать лучшее распределение значений на основе наиболее вероятных входных данных.

Сдвиг на 16 может быть вызван тем, что порты ограничены диапазоном 2 ^ 16. Кажется, что функция перемещает исходный порт в верхнюю часть битового поля, оставляя порт назначения в нижней части. Я думаю, что это может быть объяснено далее в моем следующем параграфе.

Другая причина, по которой происходит умножение (и это также верно для операции сдвига), заключается в том, что оно нарушает ассоциативный характер хэш-функции. Помните, XOR является ассоциативным, поэтому IP-адреса src = 192.168.1.1 и dst = 192.168.1.254 будут хэшироваться с тем же значением, что и src = 192.168.1.254 и dst = 192.168.1.1 (поменяно местами), если умножения не было.

Answer 2

Брайан Гидеон в значительной степени подводит итог; умножение и сдвиг предназначены для нарушения симметрии. Таким образом, это улавливает гипотетический случай, когда машина А подключается к машине В, и наоборот, и они выбирают один и тот же эфемерный портнум. Не очень часто, но не невозможно. Большая часть из 5-ти кортежей довольно постоянна: протокол исходит из очень маленького домена, как и половина {address, portnum}.

При условии, что хеш-таблица простого размера, магическая константа 59 может быть заменена любым простым, IMO. (Порт << 16) также может быть заменен другим сдвигом, если биты не падают, или даже термином (порт * some_other_prime). </p>

Для хеш-таблицы размером с степень два все (минус один) члены 5-кортежа должны быть умножены на (другое) простое число. (в старые времена, когда деление было дорогим, это было бы вариантом)

Answer 3

Лично я думаю, что вам лучше прочитать четыре байта IP как длинную без знака, которая даст вам число примерно в диапазоне 0 - 2 ^ 32-1. Затем вы выясняете, сколько потоков вы хотите иметь активными одновременно, и это будет размер таблицы индекса.

Возьмите 2000, например. Это означает, что вы хотите отобразить 2 ^ 32 числа примерно на 2 ^ 11 индейцев (для передачи информации). Это не сработает, потому что хеширование почти никогда не работает, если заполнено до 100%, и даже 90% может быть трудным. Использование индексной таблицы, которую вы заполняете только до 50% (4000 унций) или даже до 25% (8000), не имеет большого значения для сегодняшней памяти.

Точный размер индексной таблицы должен быть неравномерным числом местоположений и предпочтительно простым числом. Это потому, что вам, скорее всего, понадобится некоторая обработка переполнения для обработки коллизий (два или более числа ip, которые после хэширования указывают на одно и то же место в индексной таблице) - что вы получите. Обработка переполнения должна быть на другое простое число меньше размера таблицы индекса. Все эти простые числа! Что с ними в любом случае?

Я проиллюстрирую на примере (на С):

idxsiz = prime(2000 * 2);    // 50% loading
ovfjmp = prime(idxsiz/3);

...

изначально заполнить таблицу позиций idxjmp пометкой UNUSED (-1). Подготовьте маркировку DELETED (-2).

Ваш IP-номер входит в систему, и вы ищете его запись потока (может существовать или не существовать):

stoppos = ip % idxsiz;    /* modulo (division) just this once */
i = stoppos;
do
{
  if (index[i] == UNUSED) return NULL;
  if (index[i] != DELETED)
  {
    flowrecptr = &flow_record[index[i]];
    if (!flowrecptr->in_use) {/* hash table is broken */}
    if (flowrecptr->ip == ip) return flowrecptr;
  }
  i += ovfjmp;
  if (i >= idxsiz) i -= idxsiz;
}
while (i != stoppos);
return NULL; 

UNUSED служит маркером того, что этот индекс никогда не использовался и что поиск должен быть остановлен. DELETED служит маркером того, что этот индекс использовался, но больше не используется. Это означает, что поиск должен продолжаться.

Это было, когда вы пытались получить. Вы получили NULL от get, поэтому вам нужно выполнить пут, который вы начинаете, находя первую позицию индекса, содержащую UNUSED или DELETED. Замените это значение индексом первой / следующей свободной строки в таблице flow_record. Пометить строку как in_use. Поместите исходный номер ip в член ip строки flow_record.

Это очень простой, но очень эффективный способ создания механизма хеширования. Практически каждая оптимизация в виде специальных функций, которые будут использоваться после сбоя той или иной функции, будет повышать эффективность хеширования.

Использование простых чисел гарантирует, что - в худшем случае, когда все местоположения индекса заняты - механизм будет проверять каждое местоположение. Чтобы проиллюстрировать это: предположим, что idxsiz равномерно делится на ovfjmp: вам не придется много говорить о переполнении. 35 и 7 приведет к тому, что местоположения 0,7,14,21 и 28 будут проверены, прежде чем индекс перейдет к 0, где во время проверки остановится поиск.

---------------------- OOPS!

Я пропустил, что вы также хотели номер порта. Предполагая ip V4, это означает 6 байтов адреса. Прочитайте это как 64-разрядное целое число без знака и очистите верхние 16 бит / 2 байта. Затем вы делаете расчет по модулю.

Answer 4

Проверьте вывод функции для равномерного распределения. Если вам это не нравится, вставляйте несколько простых чисел, пока не получите нужный вам дистрибутив. Хэширование может быть очень темным искусством без «правильного» ответа.