网络测量是对网络行为进行特征化、对各项指标进行量化并充分理解与正确认识互联网的最基本手段，支持着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 可以在桶内保持准确的重流候选。