论文导读 | 基于Sketch的Top-k算法介绍

摘要：

网络测量在网络管理中具有重要作用。通过测量网络流的统计特性，可以优化网络，控制拥塞，检测攻击等。通常，网络测量的任务包括频数估计、大流检测、统计数据估计等。实现这些任务的挑战在于：1. 网络流吞吐量很大，而且要求低延迟，因此一般不能通过CPU进行处理，而且需要操作简单的算法。2. 可以高速读写的SRAM大小有限，因此需要设计空间高效的算法。在网络测量中，Top-k问题尤为重要，本文总结了现有的用以解决该问题的算法。

背景介绍：

网络流被描述成一个未知长度的分组向量<,,,...>。每个分组属于一条网络流，由一个ID进行标识，例如分组的源IP地址，五元组等。通常使用的硬件设备包括可编程交换机、FPGA、NPU等。设备被制成流水线的设计，因此所设计的算法应该适应硬件的特性。现有工作中最为常见的设计就是基于Sketch的算法。Sketch算法由多个哈希表构成，通过将一个分组映射到每个哈希表的一个桶中，并对其进行更新操作，Sketch可以较为精确的记录频数等信息。例如下图是一个经典的Count-Min Sketch，在每个映射到的桶中进行更新，即加上元素对应的值。在查询某个元素在向量中所有出现的值之和时只需要取其映射到的桶的最小值即可。

在网络测量任务中，Top-k问题尤为重要。Top-k问题是寻找频数最大的k条流。因为网络流中的数据偏度很大，因此统计数据往往由最大的一些流决定。而这些流的数量很少，同时也是需要重点关注的对象。因此如何找到这些流就是测量中的重要任务。Top-k的核心在于如何记录下来这些流的ID，如果直接用数组记录难以做到不重不漏，而可用的内存有限，故而需要设计空间高效而精确的算法。

算法介绍：

由于网络的不可预知性，难以在流算法中预测一条流是否是最大的k条流，因此往往简化为寻找频数超过某一阈值的流，然后在这些流中选择最大的k条流。现有工作主要通过三类方案解决Top-k问题。

1. 通过在每个桶中增加ID字段，更新频数时同时更新ID字段。如果现有出现两条流的哈希冲突，那么通过设计策略驱逐小流ID，留下大流ID。采用该方案的典型算法有Elastic Sketch, HeavyKeeper等。其中Elastic Sketch采用陶片放逐法进行ID替换策略：在每个桶中记录赞成票，反对票和ID，如果插入ID与桶中记录的ID相同，那么对赞成票加一，否则反对票加一。如果反对票对赞成票的比例超过某一阈值，就用插入的ID置换桶中记录的ID。

图表 1: Elastic Sketch

1. Invertible Bloom Lookup Table类算法。该类算法也增加了ID字段，但是并不使用驱逐策略，而是直接将不同的ID相加。该算法需要设计策略寻找纯净桶：只有一条流的桶。纯净桶中的ID字段就是一个正确的流ID，而该流的频数就是桶中记录的频数。利用ID可以找到该流在其它哈希表中映射的桶。通过将该流从所有映射的桶中提取出来，可能会有新的纯净桶产生。不断地寻找纯净桶，直到所有桶都被提取完，就可以得到所有插入的流的准确频数。例如FlowRadar就使用了该方案。下图中FlowRadar使用一个Bloom Filter检测一条流是否出现过。在更新一个桶时只有当该条流未曾出现时才同时更新FlowCount字段和FlowXOR字段，否则只更新PacketCount字段。
   该类算法可以证明，在使用三次哈希时，总桶数只需要超过流的数量的1.22倍时，就有超过99%的概率完全提取出所有的流。
   

图表 2: FlowRadar

1. 可逆Sketch算法。该类算法思想是识别属于同一大流的桶，并利用桶的位置恢复出流的ID。实际上，由于Sketch算法可以通过遍历所有可能的流ID，并查询其频数估计，得到大流。但是这样会搜索空间很大。可逆Sketch算法主要通过两个设计解决该问题，一个设计算法识别可能属于同一大流的桶的组合，另一个是设计特殊的哈希映射，使得根据哈希值可以恢复流ID。当搜索大流时，不需要遍历所有桶的组合，而只需要搜索可能为同一大流的桶的组合；对于一个可能的组合，也不需要通过遍历整个ID空间验证哈希值是否正确，而是通过哈希的逆运算恢复出ID。例如在Reversible Sketch中，采用了Modular Hashing的设计使得可以通过逆运算恢复ID。

图表 3: Modular Hashing

总结

本文介绍了现有网络测量中的一个重要问题——Top-k问题。围绕该问题将现有工作总结归类。希望本文可以让更多的人了解网络测量问题，探索更高效的算法。

参考文献

[1] Graham Cormode, S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications, Journal of Algorithms, Volume 55, Issue 1,2005,Pages 58-75,ISSN 0196-6774

[2] Tong Yang, Jie Jiang, Peng Liu, Qun Huang, Junzhi Gong, Yang Zhou, Rui Miao, Xiaoming Li, and Steve Uhlig. 2018. Elastic sketch: adaptive and fast network-wide measurements. In Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication (SIGCOMM '18).

[3] M. T. Goodrich and M. Mitzenmacher, "Invertible bloom lookup tables," 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA, 2011, pp. 792-799, doi: 10.1109/Allerton.2011.6120248.

[4] R. Schweller et al., "Reversible Sketches: Enabling Monitoring and Analysis Over High-Speed Data Streams," in IEEE/ACM Transactions on Networking, vol. 15, no. 5, pp. 1059-1072, Oct. 2007, doi: 10.1109/TNET.2007.896150.

[5] Y. Li, R. Miao, C. Kim, and M. Yu, “Flowradar: A better netflow for data centers,” in Proc. of USENIX NSDI, March 16-18, 2016, Santa Clara, CA, USA, K. J. Argyraki and R. Isaacs, Eds., pp. 311–324.

[6] T. Yang, H. Zhang, J. Li, J. Gong, S. Uhlig, S. Chen, and X. Li, “Heavykeeper: An accurate algorithm for finding top-k elephant flows,” IEEE/ACM Trans. Netw., vol. 27, no. 5, pp. 1845–1858, 2019.