Ищем алгоритм / класс для подсчета IP-адресов (гистограмма)
Мне нужен простой класс для подсчета распределения (гистограммы) IP-адресов из системы мониторинга сети. Там может быть где-то от 1 до 1010 пакеты, где угодно от 1 до 232 адреса (или больше, если у нас есть интерфейс IPv6). В идеале мне нужен класс C ++, который будет автоматически создавать гистограмму, а затем, когда будет достигнут предел, начать комбинировать менее популярные узлы с помощью некоторой префиксной маршрутизации.
Кто-нибудь знает что-то подобное или мне нужно написать это?
Спасибо!
Решение
То, что вы описываете, звучит как идеальный вариант использования для Граф Мин структура данных. Эта структура данных используется для аппроксимации частоты различных элементов из потока данных и может быть настроена для точного использования определенного объема памяти. Более того, учитывая фиксированный лимит памяти, вы можете отрегулировать, насколько он точен и близок к точному ответу, который вам нужен. Насколько я понимаю, Google использует эту структуру данных для выявления частых поисков без необходимости использовать смешное количество дискового пространства.
Как дополнительный плюс, структура данных никогда не недооценивает истинную частоту данного значения. То есть, если вы хотите узнать, как часто вы видели данный IP-адрес, скриншот Count-Min всегда даст вам значение, которое не меньше истинного числа.
Эскиз Count-Min чрезвычайно прост в реализации — вам просто нужно множество различных хеш-функций и двумерный массив. Вы также можете найти множество различных реализаций эскиза Count-Min. на странице Google о структуре данных.
Надеюсь это поможет!
Другие решения
+1 до @templatetypedef, для приблизительного решения.
Для полноты, если нужно хранить точные значения, нет способа сохранить точные значения. Тем не менее, в зависимости от ваших требований, вы можете значительно сократить необходимое пространство (например, 10. *. *. * и 192.68. *. * ips никогда не могут быть публично маршрутизированы; и многие другие, такие как 25. *. *. *, в настоящее время публично не маршрутизируются). Вы можете также (опять же в зависимости от ваших требований) быть в состоянии сосчитать большие группы менее важных ips вместе.
Если бы вы могли снизить требования к пространству достаточно далеко, вы могли бы хранить счетчики в памяти настолько компактно, насколько это возможно, используя bitset, Если не существует простого способа сопоставить IP-адрес с бит-адресом, вам нужно использовать что-то вроде лаконичный три сопоставить их. Для краткой записи потребуется один байт (амортизированный) на каждую ip-группу.
И, если вы не можете снизить его достаточно далеко, вам, вероятно, придется использовать базу данных и принять удар по производительности.
Вы можете взглянуть на алгоритмы пограничного шлюза (BGP) или GRiDA.
Я разработал алгоритм для решения этой проблемы. Алгоритм сохраняет количество IP-адресов в основополагающем дереве / дереве префиксов. Каждый узел записывает следующий бит адреса и счетчик, если это терминальный узел. Там, где слишком много узлов, узлы объединяются, начиная с экстента дерева; узлы с листьями, которые имеют наименьшее количество, объединяются первыми.
Это очень элегантно и очень быстро. Я могу опубликовать код C ++, если есть интерес.