4

我需要一个简单的类来计算来自网络监控系统的 IP 地址的分布（直方图）。可能有 1 到 10 10 个数据包，具有 1 到 2 32 个地址（或者更多，如果我们有 IPv6 接口）。我理想中寻找的是一个 C++ 类，它将自动创建直方图，然后，当达到限制时，开始通过某种前缀路由组合不太受欢迎的节点。

有没有人知道这样的事情，或者我需要写吗？

谢谢！

4

4 回答 4

6

您所描述的听起来像是Count-Min 草图数据结构的完美用例。这种数据结构用于近似数据流中各种元素的频率，并且可以调整为精确地使用一定量的内存。此外，给定一个固定的内存限制，您可以调整它的准确度以及与您想要的确切答案的接近程度。我的理解是，谷歌使用这种数据结构来识别频繁的搜索，而不必使用大量的磁盘空间。

作为一个额外的好处，数据结构永远不会低估给定值的真实频率。也就是说，如果您想查询您查看给定 IP 地址的频率，Count-Min 草图将始终为您提供一个不小于真实数字的值。

Count-Min 草图非常容易实现——你只需要一堆不同的哈希函数和一个二维数组。您还可以在 Google 的数据结构页面上找到 Count-Min 草图的各种不同实现。

希望这可以帮助！

于 2013-01-08T23:05:54.907 回答
2

+1 到@templatetypedef，以获得近似解决方案。

为了完整起见，如果需要存储确切的计数，则无法存储确切的数字。但是，根据您的要求，您可能能够显着减少所需的空间（例如，10.*.*.* 和 192.68.*.* ips 永远不能公开路由；还有许多其他的，例如 25.* .*.*，目前未公开路由）。您也可以（再次取决于您的要求）能够将大量不太重要的 ips 一起计算。

如果您可以将空间需求降低到足够低，您可以使用bitset. 如果没有简单的方法将 ip-address 映射到 bitset-address，则需要使用类似简洁的 trie之类的东西来映射它们。一个简洁的 trie 将需要每个 ip-group 一个字节（不规则化）。

而且，如果您不能将其降低到足够低，您可能需要使用数据库并接受性能损失。

于 2013-01-08T23:33:53.083 回答
0

我开发了一种算法来解决这个问题。该算法将 IP 地址计数存储在基数树/前缀树中。每个节点记录地址的下一位，如果它是终端节点，则记录一个计数。如果节点太多，则从树的范围开始组合节点；首先合并具有最低计数的叶子的节点。

它非常优雅且非常快速。如果有兴趣，我可以发布 C++ 代码。

于 2013-01-11T21:04:57.853 回答
0

您可以查看边界网关协议 (BGP) 或 GRiDA 算法。

于 2013-01-08T22:47:46.013 回答