摘要：

由于对快速分组处理的严格要求和有限的资源，快速检测大量网络流量中的大流量具有挑战性。

可逆sketch是摘要数据结构，可以用较小的内存占用空间和有限的错误来恢复繁重的数据流，但是现有的可逆sketch会导致较高的内存访问开销，从而导致性能下降。

我们介绍了MV-Sketch，这是一种快速而紧凑的可逆sketch，它支持使用少量和静态内存分配进行大流量检测。 MV-Sketch通过主票选的思想跟踪sketch数据结构内部的候选heavy流，从而在更新和查询操作中都以较小的内存访问开销，同时实现了较高的检测精度。

我们对MV-Sketch的内存使用，性能和准确性进行了理论分析。跟踪驱动的评估表明，MVSketch比现有的可逆sketch具有更高的精度，吞吐增益高达3.38倍。我们还将展示如何使用SIMD指令提高MV-Sketch的性能。

背景/问题：

识别大量网络流量中流量的异常模式对于各种网络管理任务至关重要。两种特殊类型的异常流量特别令人关注：heavy hitter和heavy changer。通过识别异常流量，网络运营商可以快速响应性能异常，行为不当的使用情况和潜在的DDoS攻击，从而维护网络稳定性和QoS保证。

不幸的是，对快速分组处理的严格要求和有限的存储器可用性对实际的大流量检测提出了挑战。首先，大流量检测的数据包处理速率必须与不断提高的网络速度保持一致，特别是在流量突发或攻击发生的最坏情况下。另外，实践中限制了可用的内存占用量。

经典sketch被证明是有效的，但它们是不可逆的：尽管我们可以查询sketch特定的流量是否为重流量，但我们无法轻易地仅从sketch中恢复所有重流量数据结构本身。

我们探索可逆sketch，希望提供了与经典sketch相同的可证明误差范围，同时支持了恢复所有重流量的查询。但是，现有的可逆sketch仍然存在限制。特别是，它们要么在基于外部DRAM的数据结构中保持大量流，要么在较小尺寸的位或子密钥中跟踪流密钥。

我们认为，这两种方法都会导致大量的内存访问开销，从而导致处理性能下降。

解决办法：

我们介绍了MV-Sketch，这是一种用于大流量检测的快速紧凑的可逆sketch。它以sketch数据结构跟踪候选重流密钥和计数器，并以在线流方式基于主票选算法更新候选重流密钥。

MV-Sketch的主要设计特征是，它以较小的静态内存分配（即不需要动态内存分配）维护草图数据结构。这允许在更新和检测操作中进行轻量级的内存访问，并为硬件加速提供了可行的机会。

实现细节：

像Count-Min Sketch一样，MV-Sketch初始化为存储桶的二维数组，其中每个存储桶跟踪散列到其自身的流的值。

为了找到每个存储桶中的候选重流量，我们应用了主票选算法（MJRTY），该算法使我们能够以在线流方式跟踪候选重流量。

在任何时候，它都存储（i）流中到目前为止观察到的候选多数票，以及（ii）跟踪当前存储的投票是否仍为候选多数票的指示计数器。

最初，它存储第一票，并将指标计数器初始化为1。每当新的投票到达时，MJRTY都会将新的投票与候选多数票进行比较。如果两个投票相同（即，相同的投票键），则将指标计数器加一；否则，它会将指标计数器减一。如果指标计数器小于零，则MJRTY将当前的候选多数票替换为新票，并将计数器重置为一。

上图显示了MV-Sketch的数据结构，它由具有r行和w列的存储桶的二维阵列组成。

MV-Sketch支持两个基本操作：更新，它将每个传入数据包插入到sketch中 。查询，它返回一个时期中给定流的估计总和。