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

Double sketch:Flow Measurement Method Based on Two-layer Sketch

作　　者：吴慧敏 陈世平[1,2] 梁坤 WU Hui-min;CHEN Shi-ping;LIANG Kun(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China;Network and Information Center Office,University of Shanghai for Science and Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学光电信息与计算机工程学院,上海200093 [2]上海理工大学信息化办公室,上海200093

出　　处：《小型微型计算机系统》2023年第1期140-145,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61472256,61170277)资助;上海理工大学科技发展基金项目(16KJFZ035,2017KJFZ033)资助。

摘　　要：流数据包数量估算在网络流量测量中属于基础性的作用.数据略图是一种紧凑的数据结构,由于其具有节省内存空间的特性,被广泛运用在网络流量测量系统中.现有的多层数据略图通常由多个原子数据略图组成,有限内存需要分配给多个模块,在保证单个计数器大小的前提下,计数器个数较少,导致流数据包存储到计数器时冲突增加,最终影响准确性.为了实现有限内存下的高准确性,我们提出了新的数据略图,即Double sketch.Double sketch由两个原子数据略图组成,分别为余包记录层和满包计数层.其主要思想是将流数据包满计数器数与余包数存储在不同的数据结构,有限内存仅需分配给两个采用小计数器的原子数据略图,因此计数器的个数增加,存储冲突减少,准确性提高.实验结果表明,在有限内存大小下,我们的数据略图相较于其他4种典型的数据略图能实现更高的准确性.The estimation of the number of flow packets plays a fundamental role in traffic measurement.Sketch is a kind of compact data structure,which is widely used in network traffic measurement system because of its saving memory space.The existing multi-layer sketch is usually composed of multiple atomic sketch,and the limited memory needs to be allocated to multiple modules.Under the premise of ensuring the size of a single counter,the number of counters is small,which leads to increased conflicts when the stream packets are stored to the counter,and ultimately affects the accuracy.In order to achieve high accuracy under limited memory,we propose a new sketch,Double sketch.Double sketch consists of two atomic sketches,namely,the remaining packet recording layer and the full packet counting layer.The main idea is to store the number of full counter and the number of remaining packets in different data structures,and the limited memory only needs to be allocated to two atomic sketches with small counters,so the number of counters increases,the storage conflicts are reduced and the accuracy is improved.The experimental results show that our sketch can achieve higher accuracy than the other four typical sketches under the limited memory size.

关 键 词：流 数据包 原子数据略图 多层数据略图 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]