论文阅读：Accurate Per-Flow Measureme

摘要：

Sketch是一种概率数据结构，广泛用于网络中的每流测量。 最常见的Sketch是CM Sketch及其几种变体。 但是，在有限的内存大小下，这些Sketch始终会大大高估一些流程，显示出较差的准确性。

为了解决这个问题，我们提出了一个名为Bloom Sketch的新颖Sketch，将其与Bloom过滤器结合使用，Bloom过滤器是另一种广泛用于成员资格查询的概率数据结构。

基于真实IP轨迹的大量实验表明，与CM Sketch相比，我们的Bloom Sketch可实现高达14.47倍的精度，同时具有可比的插入和查询速度。

背景/问题：

每流测量是指估计每个流中的数据包数量（即流大小），这是现代网络中的一个基本问题。它可以帮助检测SYN泛洪攻击，减轻网络拥塞，发现入侵检测系统中的heavy hit和heavy changer等。

由于网络流量的高速和巨大量，一个一种称为Sketch的概率数据结构被广泛用于按流测量，Sketch的目标是在有限的内存大小下以线速执行近似每流测量。

有三个典型的Sketch：CM，CU 和Count。

但是，所有常规Sketch都无法在实际的网络流量中很好地工作，因为在实际的网络流量中，流量大小的分布是不对称的：少数流量的大小较大，而大多数流量的大小则较小。

由于常规Sketch使用固定大小的计数器来执行计数，因此计数器的数量大小应由网络流量中最多的大象流来确定，大量的鼠标流无法“填满”被散列到的计数器。即，大多数计数器的高位被浪费，这导致差的存储效率。

此外，由于内存大小有限，常规Sketch还存在另一个问题：由于与大象流的严重哈希冲突，某些鼠流易于被高估，我们称此问题为大象流的高程效应。

解决办法

在本文中，我们提出了Bloom草图，以基于分层计数器数组执行内存有效计数，并通过使用多个Bloom过滤器来降低高程效应。

实现细节：

插入：

在处理具有流ID e的数据包时，我们首先通过计算d1哈希值将d1哈希计数器放在S1处，并递增最小的哈希计数器。

如果一个或多个哈希计数器在S1处溢出，那e必须使它们的d1哈希计数器同时溢出，因为我们总是增加最小的计数器。

这种保证为我们提供了在一定程度上将每个sketch或Bloom过滤器层与其他层隔离的机会。

查询：

给定流ID e时，我们首先在S1处获得d1哈希计数器的最小值V1。 然后，我们需要通过检查B1层的哈希位是否全部为1来确定e在插入过程中是否已到达较高的层：

如果哈希位不全为1，我们仅将V1报告为e的估计流量。否则，我们需要在S2和B2处执行相同的操作。 此类操作将连续执行，直到某层开始的哈希位不全为1。

然后，我们将

报告为e的估计流量。

由于sketch或Bloom过滤器层之间的隔离，因此可以并行执行查询这些层中的每一个层。

优化：

为了加快Bloom过滤器层的操作，我们采用了一个内存访问Bloom过滤器。 具体来说，我们将多个散列位限制在一个机器字内的Bloom过滤器层，将一个64位哈希值拆分为多个具有用户定义长度的位字符串，我们使用这些位串首先在一个特定的布隆过滤器层上定位一个机器字，然后在该机器字内定位多个散列位。 这样，将每次插入或查询在每个Bloom过滤器层花费的成本减少为一次内存访问和一次哈希计算。

总结：

在Bloom sketch中，每个sketch层的功能类似于一个独立的sketch，以记录每种流量大小的一小部分。 由于流量大小的偏斜分布，较少数据包访问的较高sketch层可以使用较少的内存来达到相同的精度。

通过利用合适的存储器分配方案，可以保证存储器效率，因为每个计数器的几乎所有位都得到了充分利用，Bloom过滤器层可以通过帮助检查相应sketch层的溢出状态来减少高程影响。