基于自适应超时计数布鲁姆过滤器的流量测量算法
侯颖* 黄海 兰巨龙 李鹏 朱圣平
(国家数字交换系统工程技术研究中心 郑州 450002)
An Adaptive Timeout Counter Bloom Filter Algorithm for Traffic Measurement
Hou Ying Huang Hai Lan Ju-long Li Peng Zhu Sheng-ping
(National Digital Switching System Engineering & Technological R&D Center, Zhengzhou 450002, China)
摘要 针对流量测量中IP长流的检测问题，该文设计了计数布鲁姆过滤器(Count Bloom Filter, CBF)与超时布鲁姆过滤器(Timeout Bloom Filter, TBF)结合的长流检测机制。该机制动态调整布鲁姆过滤器中的超时时间，及时清理结束流，解决空间拥塞问题，从而可以适用于无结束标志IP长流检测。依据算法整体错误率与超时时间的分析，根据链路流到达强度与布鲁姆过滤器向量空间长度自适应动态调整超时时间，使得算法整体错误率保持最低。该算法的性能利用真实网络流量数据进行验证，结果表明，与现有算法相比，该算法的测量准确性更高。
关键词 ：
网络测量 ,
流量测量 ,
长流 ,
动态调整
Abstract ：A novel mechanism combining Counting Bloom Filter (CBF) and Timeout Bloom Filter (TBF) is proposed, aiming at identifying IP long flow precisely. By adjusting the timeout dynamically and deleting end flows timely, the mechanism can solve the space congestion of Bloom filter and identify heavy hitters without normal end flag. The timeout and accuracy are analyzed. When adjusting the timeout dynamically according to the traffic arrival intensity and Bloom filter vector length, the mechanism can get minimum error. The experiments are conducted based on the real network trace. The results demonstrate that the proposed method is more accurate than the existing algorithms.
Key words ：
Network measurement
Traffic measurement
Heavy hitters
Dynamic adjust
收稿日期: 2014-06-23
基金资助: 国家自然科学基金(61309019)和国家863计划项目(201101A103, 2011AA010603)资助课题
通讯作者:
侯颖：女，1973年生，副研究员，研究方向为网络测量和网络信息安全.
E-mail: ndschy@139.com
引用本文:
侯颖, 黄海, 兰巨龙, 李鹏, 朱圣平. 基于自适应超时计数布鲁姆过滤器的流量测量算法[J]. 电子与信息学报, 2015, 37(4): 887-893.
Hou Ying, Huang Hai, Lan Ju-Long, Li Peng, Zhu Sheng-Ping. An Adaptive Timeout Counter Bloom Filter Algorithm for Traffic Measurement. , 2015, 37(4): 887-893.
链接本文:
http://jeit.ie.ac.cn/CN/10.11999/JEIT140820 或 http://jeit.ie.ac.cn/CN/Y2015/V37/I4/887
[1]
潘胜利,杨析儒,张志勇,钱峰,胡光岷. 单源多径路由网络拥塞链路识别
[2]
王晶,汪斌强,张校辉. 基于可重构测量模型的网络测量任务部署算法
[3]
伊鹏,钱坤,黄万伟,王晶,张震. 基于抽样流长与完全抽样阈值的异常流自适应抽样算法
[4]
王聪, 张凤荔, 王瑞锦, 李敏, 杨晓翔. 一种网络时延矩阵分布式自适应重建算法
[5]
王晶, 汪斌强, 张震. 一种基于大小流区分计数的公平抽样算法
[6]
王聪, 张凤荔, 杨晓翔, 李敏, 王瑞锦. 支持入侵容忍的网络距离选举计算模型
[7]
顾然, 邱雪松, 乔焰, 李娟, 孟洛明. 基于非线性规划的链路丢包率推理算法
[8]
张 震; 汪斌强; 陈庶樵; 朱 珂. 基于多维计数型布鲁姆过滤器的大流检测机制
[9]
陈松,王珊,周明天. 一种新的物理网络拓扑发现算法
[10]
韦安明; 王洪波; 程时端. 基于分组抽样的P2P超级节点推测
[11]
刘世栋; 张顺颐; 邱恭安; 孙雁飞. 一种基于端到端测量的路径性能参数估计算法
[12]
王洪波; 裴育杰; 林宇; 程时端; 金跃辉. 基于LRU的大流检测算法
[13]
张登银; 乔丽霞. 卫星网络流量测量方法的研究
[14]
江昊; 晏蒲柳; 夏德麟; 陈潇. 动态权重RED网关
[15]
李彤红; 廖建新; 陈俊亮. 多业务环境中SCP过载控制研究
2015, Vol. 37 
