乔冠杰，吕高锋，谭 靖，莫露莎

(国防科技大学计算机学院，湖南 长沙 410073)

1 引言

随着网络的发展，流量规模的不断增大，对大规模流量进行统计变得十分重要，早期的网络管理功能，如流量统计，是固化在相应的网络设备中的，基于端口对交换机或路由器连接不同网络的流量进行统计。随着网络的发展，这种方式已经不能满足网络管理的需求。

网络可视化应运而生，对网络的实时监控越来越重要。网络就像公路，需要实时掌握主干道信息，了解每条路是否堵塞，了解车流密度等等。车辆就相当于网络中的流量，只有掌握道路信息，才能更好地调度交通，保证道路畅通。网络也是一样，只有实时去监测流量，才能了解网络状态，进行流量调度、拥塞控制[1]和异常检测等等。

为了应对大规模的流量统计[2]，各种测量结构相继产生，一种典型的网络测量结构是Sketch[3]。Sketch是一种基于哈希的紧凑的数据结构，通过哈希减少流量的存储空间，同时可以对流量进行统计。针对不同流量统计的问题，基于Sketch的统计算法不断发生改变，流量统计中一个典型问题是对top-k流[4]进行统计，本质是将大象流[5]和老鼠流[6]进行分离，实现对大象流的精确统计，同时对老鼠流实现粗略统计。Elastic Sketch[7]便是将老鼠流和大象流分离进行统计的典型。使用重部存储大象流，轻部存储老鼠流，实现大象流和老鼠流的分离。

但是，Elastic Sketch在计数器更新时也存在问题，在Elastic Sketch的替换策略中，当负投票和正投票比值大于一个阈值时，就会发生替换。……