Double sketch:双层计数数据略图的流测量方法

摘要

流数据包数量估算在网络流量测量中属于基础性的作用.数据略图是一种紧凑的数据结构,由于其具有节省内存空间的特性,被广泛运用在网络流量测量系统中.现有的多层数据略图通常由多个原子数据略图组成,有限内存需要分配给多个模块,在保证单个计数器大小的前提下,计数器个数较少,导致流数据包存储到计数器时冲突增加,最终影响准确性.为了实现有限内存下的高准确性,我们提出了新的数据略图,即Double sketch.Double sketch由两个原子数据略图组成,分别为余包记录层和满包计数层.其主要思想是将流数据包满计数器数与余包数存储在不同的数据结构,有限内存仅需分配给两个采用小计数器的原子数据略图,因此计数器的个数增加,存储冲突减少,准确性提高.实验结果表明,在有限内存大小下,我们的数据略图相较于其他4种典型的数据略图能实现更高的准确性.