基于sketch的网络测量方法介绍

作者简介： 周政演，福州大学数计学院2016级计算机科学与技术（实验班）本科生，目前研究方向为网络测量,邮箱vancasola @gmail.com。

一、背景

网络测量是SDN发展的重要基础。网络状态监测、网络故障分析、网络安全防御，乃至于网络智能化，都依赖于网络测量。作为网络测量前沿研究的主流，基于sketch的高速流量网络测量，是网络领域顶级会议SIGCOMM近两年的研究热点，包括SIGCOMM’17的 SketchVisor[1] 和SIGCOMM’18的SketchLearn[2]、ElasticSketch[3]等。

sketch的网络测量与SDN结合，具有天然特性。一方面，SDN云数据中心的大量部署，需要基于sketch的高速流量网络测量，因为sketch能进行大流和异常流的检测，不占用过多的计算和空间资源。另一方面，SDN 转控分离，控制器具有全局视野，能对网络进行调度、制定策略，实时提供网络信息，有利于sketch的应用实施。

当前的网络流量测量，主要有抽样技术和数据流技术两种方法。抽样技术为每条流维护一个独立的计数器，较高的抽样速率需要消耗大量的性能资源。数据流技术利用散列将庞大信息压缩到较小的空间内，目前被广泛应用的是基于 sketch 的网络测量方法。

sketch 是一种基于散列的数据结构，可以在高速网络环境中，实时地存储流量特征信息，只占用较小的空间资源，并且具备在理论上可证明的估计精度与内存的平衡特性。基于sketch的网络测量，目前主要有ReversibleSketch[4]、OpenSketch[5]、Sketchvisor[1]等相关改进及实现。

二、Sketch 的原理

sketch是基于散列的数据结构，通过设置散列函数，将具有相同散列值的键值数据存入相同的桶内，以减少空间开销。桶内的数据值作为测量结果，是真实值的近似。利用开辟二维地址空间，多重散列等技术减少散列冲突，提高测量结果的准确度。Count-Min[7] 是一种典型的 sketch ，在 2004 年被提出。实际上 Count-Min sketch 用到的是分类的思想：将具有相同哈希值的网络流归为一类，并使用同一个计数器计数。

如何处理包

当高速网络流量到来时，逐个记录所有流量的信息，会带来巨大的计算和空间资源开销。而网络测量往往也无需记录所有的信息。

Count-Min sketch由多个哈希函数（f1……fn）和一张二维表组成。二维表的每个存储空间维护了一个计数器，其中每个哈希函数分别对应表中的每一行。当一个网络流到来时，需要经过每个哈希函数 f1……fn 的处理，根据处理得到的哈希值分别存入每一行对应哈希值的计数器。有几个哈希函数，就要计算几次。算完后，取这m个计数器中的最小值，作为测量的最终值。

设计考量

测量值偏大：使用哈希的方法会产生冲突，多个网络流数据哈希到同一个桶内，那么这个桶的计数值就会偏大。

1.为什么允许有误差：在高速网络条件下，若把所有信息都准确地记录下来，要消耗大量计算和空间开销，无法满足实时性；而且在很多情况下，并不需要非常精确的测量数据，在一定程度上可靠的估计值，便足以满足需求。

2.为什么要设置多个哈希函数：如果只设置一个哈希函数，多个流数据存入同一个桶，误差就会很大。通过设计多个哈希函数，减少哈希值的冲突，以减少误差。每个流都要经过所有哈希函数的处理，存入不同的计数器中。计数器的最小值虽然还是大于等于真实值，但最接近真实值。这也是 “ Count-Min ”的由来。

3.哈希函数个数：哈希函数越多，冲突越少，测量值越精确，但计算开销大。需要权衡测量精度和准确度，来设置合适的哈希函数个数。

为了帮助理解sketch的原理，这里从一个例子讲起：
小周是全市的快递中转站的负责人（SDN控制器），他需要合理地分配人员的职责，制定分配的策略（全局调度）。他需要了解每个区的包裹数等信息（测量信息），以便完成人员分配。起初，他把每个包裹的信息都记录下来，并且让百分之八十的人负责统计每个区的包裹数量。

可是这里的包裹有成千上万之多（高速网络环境），统计人员算得满头大汗（计算资源开销大），记了几十页的纸（空间资源开销大），算得晕头转向。而另一头，快递员的数量太少，每个区的包裹，都没有送完。
他意识到，记录所有包裹的所有信息，是没有必要的（精度要求降低）。他的目标，是合理地分配每个区的快递员数量，他只需要了解每个区大致（估计）的包裹量即可（基于sketch的方法）。而且他发现，分类包裹这件事不应成为中转站的负担（减少测量开销），让快递的正常配送无法完成。

于是，他只留下几个人，让其他人负责配送包裹。相同区的包裹记在同一个区（计入同一个桶内），并且只需大致计算每个区的包裹数即可（近似）。这样一来，统计速度明显快了许多，用了一两张纸就把数据记完了。得出数据后，得知 A 区的包裹数最多，而 B 区的最少，小周将 B 区的大部分快递员分配到 A 区，不仅完成了昨天的配送，今天的配送也早早地完成（实时性）。

网络流经过网络结点时，需要制定合理的控制策略完成网络流的高效调度。网络流控制策略的制定，首先需要网络测量提供的流量信息。当流量较小时，如果将每个流的信息都记录下来，消耗计算和空间的资源并不大。

但是，当SDN 控制器进行全局调度时，有高速的流量通过。若将所有信息都一一记录下来，将大大占用网络资源，成为网络的负担。而且很多情况下，得到流量的估计值就足以满足任务的需求，记录所有信息是没有必要的。

此时，基于 sketch 的方法，利用散列技术对网络流进行粗粒度的分类，得出测量的估计值，满足高速环境下实时测量的需求，节约计算和空间的开销。

三、sketch研究热点

sketch 是网络测量研究领域的热点问题，在如 SIGCOMM 等网络领域顶级会议中，提出了一系列关于 Sketch 的解决方案 其中包括 SIGCOMM‘17 的 sketchvisor[1] 和 SIGCOMM’18 的SketchLearn[2] 和 ElasticSketch[3]，现简单介绍基于 sketch 的研究热点，主要分为sketch的数据结构和sketch的测量框架。

Sketch的数据结构

• Count-min sketch[7] 通过设置多个散列函数减少散列冲突，将计数器的最小值作为测量结果，是一种典型的 sketch。
• 基于 sketch 的方法常常被用来检测大流和异常流，但是无法根据测量信息推出信息来源。而Reversible sketch[4] 可以解决这个问题，推断出信息的来源。
• SeqHash [8]应用于入侵防御、大流检测，优点是快速精确，资源开销小。
• top-k[9] 应用于检测数据流中最常见元素，优点是空间开销小，速度快。

基于Sketch的测量框架

• NSDI’13 的 OpenSketch [5]，首次将 sketch 应用在 SDN 中，是此类论文的的开山之作。
• LD-Sketch [6]将基于计数的方法和基于 sketch 的方法结合，用于检测 heavy hitter 和 heavy changers，保持了一定的准确度和稳定性。

• SIGCOMM’17 上的 Sketchvisor [1]是基于 sketch 的测量框架，将过载流量导入 Fast Path， 完成高速环境下测量。
• SIGCOMM’18 的 SketchLearn [2]通过解耦资源配置和精确度的参数，利用自动统计推断提取流量数据。
• 在多变的环境下，测量的性能会受到到很大的影响， SIGCOMM’18 的 ElasticSketch [3]对此设计了一个可以根据环境动态调整的测量框架，保持测量的稳定性和准确率。

四、总结

• 高管理能力对网络测量的性能、准确率、资源开销提出了更高的要求。
• Sketch 是一种基于散列的数据结构，可以在高速网络环境中，实时地存储流量特征信息，只占用较小的空间资源，并且具备在理论上可证明的估计精度与内存的平衡特性。
• Count-min [7]是一种典型的 sketch ，用到的是分类的思想：将具有相同哈希值的网络流归为一类，并使用同一个计数器计数。
• 基于 Sketch 的方法是当下主流和热门的网络测量方法，有着广泛的应用和前景。

参考文献

[1] Huang Q, Jin X, P. C. Lee P, et al. SketchVisor: Robust Network Measurement for Software Packet Processing[C]//Proceedings of the 2017 ACM SIGCOMM Conference, 2017: 113-126.
[2] Huang Q , P. C. Lee P, Bao Y. SketchLearn: Relieving User Burdens in Approximate Measurement with Automated Statistical Inference[C] //Proceedins of the 2018 ACM SIGCOMM Conference, 2018: 576-590.
[3] Yang T, Jiang J, Liu P, et al. Elastic Sketch: Adaptive and Fast Network-wide Measurements[C]//Proceeding of the 2018 ACM SIGCOMM Conference, 2018:561-575
[4] SCHWELLER R, GUPTA A, PARSONS E, et al. Reversible sketches for efficient and accurate change detection over network data streams[C]//Proceeding of the 2004 ACM SIGCOMM Conference on Internet Measurement. 2004: 207-212.
[5] YU M, JOSE L, MIAO R. Software defined traffic measurement with OpenSketch[C]//Presented as Part of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). 2013: 29-42.
[6] Huang Q, P. C. Lee P. A hybrid local and distributed sketching design for accurate and scalable heavy key detection in network data. streams.[C]//Proceeding of the 2014 IEEE INFOCOMM conference. 2014: 298-315.
[7] Cormode G, Muthukrishnan S. An improved data stream summary: the count-min sketch and its applications. [J] Springer Journal of Algorithm, 2004, LNCS 2976,pp. :29-38
[8] Bu T, Cao J, Chen A, et al. Sequential hashing: A flexible approach for unveiling significant patterns in high speed networks[J] Computer Networks 54 (2010) 3309-3326.
[9] Homem N, Carvalho J P . Finding top-k elements in data streams [J] Information Sciences, 2010, 180 (2010) : 4958–4974
[10] Dai M, Cheng G. Sketch-based data plane hardware model for software-defined measurement [J] Journal on Communications, 2017, 38 (10): 20172031-20172039
[11] https://www.cnblogs.com/vancasola/p/9735989.html
[12] https://www.cnblogs.com/vancasola/p/94