一种基于大小流区分计数的公平抽样算法

• 作者: 张震 汪斌强 王晶
• 来源期刊: 电子与信息学报
• 学科: 工学
• 关键词: 互联网 网络流量测量 包公平抽样 哈希冲突 估计误差 大小流区分
• 年，卷（期）: 2014,（10）
• 所属期刊栏目: 论文
• 页码范围: 2350-2356
• 页数: 7页
• 分类号: TP393.4
• 字数: 6166字
• 语种: 中文
• DOI: 10.3724/SP.J.1146.2013.01786

摘要

针对一种草图指导公平抽样(SGS)算法对小流估计误差大的问题，该文提出一种基于大小流区分计数的包公平抽样算法(DCMFS)，并给出哈希冲突对SGS算法估计误差影响的定量分析结果。DCMFS采用大小流区分计数器，对小流采用逐流精确计数，对大流采用哈希计数。理论分析及实际的数据仿真结果均表明，DCMFS算法对小流能够实现逐流精确统计，对大流的估计标准差接近公平抽样估计标准差理论值上限。算法采用不等长位宽计数器结构，保证其空间复杂度较SGS和自适应非线性抽样方法(ANLS)没有增加；引入计数器置换使得算法时间复杂度略有提高，但仍能满足10 Gbps线速处理要求。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	汪斌强		131	867	14.0	22.0
2	张震		35	179	7.0	12.0
3	王晶		10	78	3.0	8.0