Sketch统计方法研究  

Sketch Statistical Method Research

作　　者：乔冠杰 吕高锋[1] 王宏[1] 谭靖 莫露莎 QIAO Guan-jie;LV Gao-feng;WANG Hong;TAN Jing;MO Lu-sha(College of Computer,National University of Defense Technology,Changsha 410073,China)

机构地区：[1]国防科技大学计算机学院,长沙410073

出　　处：《小型微型计算机系统》2022年第2期393-398,共6页Journal of Chinese Computer Systems

基　　金：国家重点研发计划项目(2018YFB1800505)资助。

摘　　要：网络测量为网络运营,服务质量保证,拥塞控制,数据中心和骨干网中的异常检测提供了关键信息.为了应对日益增大的流量规模,减少流量统计的内存开销,基于Sketch的流量统计方法成为流量统计的研究热点.文章对Sketch统计方法进行研究,针对基于Sketch的Top-k流统计问题进行分析,根据Sketch的结构特点,将Sketch分为基本Sketch、面向热流的高精度统计Sketch、冷热流自适应的精确统计Sketch.另外研究了Sketch面向场景的实现方法.最后分析了Sketch算法未来的研究方向.Network measurement provides key information for network operation,quality of service assurance,congestion control,and anomaly detection in data centers and backbone networks.In order to cope with the ever-increasing traffic scale and reduce the memory overhead of traffic statistics,the traffic statistics method based on Sketch has become a research hotspot of traffic statistics.This paper studies the Sketch statistical method,analyzes the Top-k flow statistical problem based on Sketch,discusses basic Sketch,high-precision statistical Sketch for hot flow,and accurate statistical Sketch for cold and hot flow adaptation.In addition,the scene-oriented realization method of Sketch is studied.Finally,the future research direction of Sketch algorithm is analyzed.

关 键 词：Sketch统计方法 Top-k流 冷热流分离 

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