空间高效的数据包公平抽样算法

• 作者: 张进 邬江兴 钮晓娜
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 网络流量监测 数据包抽样 d-left哈希
• 年，卷（期）: 2010,（10）
• 页码范围: 2642-2655
• 分类号: TP393
• 字数: 10496字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2010.03667

摘要

数据包公平抽样通过牺牲长流的包抽样率以换取更高的短流包抽样率,因而比均匀随机包抽样更能保证数据流之间的公平性.现有的公平抽样算法SGS(sketch guided sampling)存在空间效率低、短流估计误差大的问题.提出了一种空间高效的数据包公平抽样算法SEFS(space-efficient fair sampling).SEFS算法的新颖之处在于采用多解析度抽样统计器对数据流流量作近似估计,各个统计器由d-left哈希表实现.采用在OC-48和OC-192骨干网采集的真实流量数据,在数据流流量测量以及长流检测的应用背景下,对SEFS算法和SGS算法的性能进行了比较.实验结果表明,与SGS算法相比,SEFS算法在空间复杂度降低65%的前提下,仍具有更高的估计精度.特别是对于占网络数据流绝大多数的短流而言,SEFS算法估计精度高的优势更为明显.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	邬江兴		93	559	12.0	19.0
2	张进	解放军理工大学通信工程学院	9	28	3.0	5.0
3	钮晓娜		3	19	2.0	3.0