PeakSketch:检测网络流中的top-k流的无偏和通用草图
PeakSketch:Unbiased and Generalized Sketch for Detecting top-k Flows in Network Streams
李旭 1王超 1尹慰民 1周萍1
作者信息
- 1. 南华大学 电气工程学院,湖南 衡阳 421001
- 折叠
摘要
通过对现有Sketch结构的研究,提出一种新的Sketch结构:PeakSketch,本文将其应用于三种任务:检测top-k频繁流,检测top-k重变化流,检测top-k持久流,从理论上证明了PeakSketch可以提供无偏估计,并且给出了算法的误差界.实验结果表明,PeakSketch的各项性能优秀,在检测top-k频繁流任务中,PeakSketch的吞吐量显著提升,特别是在分配内存小于200 kB以下时,吞吐量最高提升可以达到50%,准确率最高提升一倍,PeakSketch也展现突出的性能.
Abstract
By studying existing sketch structures,this paper proposes a new sketch structure called PeakSketch,which is applied to three tasks:detecting top-k frequent flows,detecting top-k heavy change flows,and detecting top-k persistent flows.Theoreti-cally,it is proven that PeakSketch can provide unbiased estimates,and the algorithm's er-ror is analyzed.Experimental results demonstrate that PeakSketch excels in various per-formance metrics.In the task of detecting top-k frequent flows,PeakSketch's throughput is significantly enhanced,especially when the allocated memory is less than 200 kB,with throughput improvements of up to 50% and precision improvements of up to double.Peak-Sketch showcases outstanding performance.
关键词
网络流测量/Sketch/无偏估计/top-k流检测/频繁流/重变化流/持久流Key words
network flow measurement/Sketch/unbiased estimation/detecting top-k flows/frequent flows/heavy change flows/persistent flows引用本文复制引用
出版年
2024
国家科技期刊平台
NSTL
万方数据