网络流量测量是网络管理中一项重要任务。然而随着互联网的飞速发展,网络流量呈现爆炸式的增长,使得对高速网络流量的测量面临着很大的挑战。Sketch是一种可以对数据流进行存储和汇总的方法,可以对数据流进行测量和查询,它有几种典型的Sketch算法:Count-Min Sketch、CU Sketch和Count Sketch,可以将它应用到网络测量中来。但是由于网络流量自身的特点,在使用Sketch进行测量时可能会产生大量的空间浪费,造成空间利用率低等问题。此外,由于Sketch是使用散列函数对数据流进行汇总,散列冲突会造成估计值的误差,尤其是对于小流量。因此,本文的工作主要针对于空间利用率低和对小流量的过高估计这两个问题对网络流量测量的算法进行改进。本研究首先引入进位的思想,提出了将多个Sketch与Counting Bloom Filter(CBF)相结合的结构——Self-Adaption Sketch(SA Sketch)。该结构可以根据所需测量的网络流量的大小动态地申请空间、创建Sketch,并使用CBF来存储当前流量使用的Sketch的数量,从而提高空间的利用率。实验结果表明,SA Sketch在进行点查询时的误差相比于Count-Min Sketch、CU Sketch和Count Sketch有了一定的降低。在进行heavy hitter检测时,准确性也有了极大的提升。在SA Sketch与其他Sketch达到相同测量精度时,SA Sketch使用的空间更小,并且与其他Sketch算法保持了相同水平的吞吐量。负载因子越大,SA Sketch在准确性上的提升越明显。后续研究发现,由于Counting Bloom Filter使用散列函数对元素进行存储和查询,从而导致在查询时存在一定的误差。因此,在SA Sketch中对流量进行点查询时,查询的Sketch的数量可能会发生错误,导致最终的查询值存在较大误差。为了解决这一问题,本研究采用布谷鸟哈希的思想,将改进后的布谷鸟哈希表与Sketch相结合,提出Cuckoo-Based Self-Adaption Sketch(CBSA Sketch)。该结构采用布谷鸟哈希表对Sketch的数量进行存储,从而实现对Sketch数量的准确查询,进一步提高点查询的准确性。实验结果显示,在进行点查询时和heavy hitter检测时,CBSA Sketch的准确性相比于Count-Min Sketch、CU Sketch和Count Sketch有了显著的提高。在达到相同准确性的情况下,CBSA Sketch提高了平均吞吐量并且有效地节省了内存开销。综上所述,本研究提出的基于布谷鸟哈希的自适应概要数据结构(CBSA Sketch)有效地提高了空间利用率和测量的准确性,并且在一定程度上提高了吞吐量。由于它在网络负载因子越大时,相比于其他算法的提升更加明显,因此,它更适用于高速网络流量的测量,并且可以根据所需测量的网络流量大小和测量的目的,选择最优的参数来对数据流进行处理。