如何进行MV-Sketch的分析

如何进行MV-Sketch的分析，针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

网络测量是对网络行为进行特征化、对各项指标进行量化并充分理解与正确认识互联网的最基本手段，支持着SDN的发展，网络管理员可以通过网络测量掌握网络状态，进而优化网络结构、改善网络服务质量，及时诊断网络故障并进行恢复。Sketch在较小内存下对重流（heavy flow）和heavy changer（突变流））的快速检测有助于SDN云数据中心的大量部署。

既然提到了Sketch，那么我们就来介绍一下什么是Sketch。Sketch是一种紧凑的用于流量数据统计亚线性数据结构。使用Hash算法将属于映射到Sketch中，将大量网络流压缩至小部分的内存空间中，无需存储所有网络流，以达到节约内存的目的，并通过查询操作获得流量统计数据。使用Sketch的原因是其将具有相同哈希值的流存入相同的桶内，可以在保证准确度的同时大大减少存储空间。

接下来为大家介绍的是MV-SKetch，是一种高效、紧凑、可逆的Sketch，可以在小内存下实现对重流的快速检测，主要利用MJTRY算法（主票选算法）。相较于动态分配流存储空间的方式，静态分配的方式有助于降低内存管理开销，且可以利用SIMD加速MV-Sketch。

MV-Sketch的数据结构由r行 构成，每一行有w个桶，每个桶中记录三个元素Vi,j、Ki,j、 Ci,j。Vi,j表示哈希到这个桶内所有流的总和，Ki,j表示当前桶内的重流候选，Ci,j记录当前桶内重流候选的计数值，用于判断是否继续保留此重流候选。如下图所示：

当数据包到来时，MV-Sketch利用 r 个独立的哈希函数，将数据包分别映射到1 - r 行，所映射列序j由哈希值hi(x)决定。哈希到某个桶之后，根据MJRTY算法来更新重流候选。查询时，根据新流和桶内重流候选是否一致来决定估计值，最后返回所有行中估计值最小值。在一个周期结束时，MV-Sketch以是否大于设定的阈值为标准来判断重流。

MV-SKetch所使用的MJRTY算法用于确定任意数量的候选人中，哪一个获得了多数选票，所拥有票数高于总票数一半者，一定是主要候选人。举例说明：假设有三位候选人A、B和C，并假设按以下顺序对代表进行了投票：A A A C C B B C C C B C C

记录完第三张选票后，A以3票领先。在处理接下来的三张选票时，将三张A票与三张其他票（两张C票，一张B票）配对（抵消）。记录所有选票之后，C成为主要候选人。

算法 1：MV-Sketch更新算法

MV-Sketch借鉴MJRTY算法,在执行更新操作时（算法1[2])，先累加Vi,j = Vi,j + vx (Vi,j增加新流字节数)，再将新流x与当前桶内重流候选Ki,j进行比较，若相同，那么计数器Ci,j增加新流的字节数，否则相应地减少；若减少至零下（即Ci,j <0)，则x取代Ki,j，且Ci,j取绝对值。在实际中，由于少数重流所带流量在桶内所有流量中占主导地位，因而在一个周期结束时，MV-Sketch可以在桶内保持准确的重流候选。

关于如何进行MV-Sketch的分析问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注编程网行业资讯频道了解更多相关知识。