基于同源组合布鲁姆过滤器的早期流量抽样算法

doi:10.3969/j.issn.1000-436x.2014.10.014

通信学报 ›› 2014, Vol. 35 ›› Issue (10): 117-126.doi: 10.3969/j.issn.1000-436x.2014.10.014

基于同源组合布鲁姆过滤器的早期流量抽样算法

侯颖,郭云飞,黄海,王凯

国家数字交换系统工程技术研究中心，河南郑州 450002

出版日期:2014-10-25 发布日期:2017-06-14
基金资助:
国家自然科学基金资助项目;国家高技术研究发展计划(“863”计划)基金资助项目;国家高技术研究发展计划(“863”计划)基金资助项目

Early traffic sampling algorithm based on SSCBF

Ying HOU,Yun-fei GUO,Hai HUANG,Kai WANG

National Digital Switching System Engineering ＆ Technological R＆D Center,Zhengzhou,Henan，450002,China

Online:2014-10-25 Published:2017-06-14
Supported by:
The National Natural Science Foundation of China;The National High Technology Research and Development Program of China (863 Program);The National High Technology Research and Development Program of China (863 Program)

摘要/Abstract

摘要：

提出一种同源组合布鲁姆过滤器结构，该结构包含流抽样（sample）和分组计数（packet）2个计数器向量组合，2 个计数器向量宽度不同，以相同的散列源函数计算散列位置。基于该结构设计的早期流量抽样算法利用2个计数器向量将流抽样判断与分组计数检测分开，避免了早期流量抽样中大量抽样已经结束的流对分组计数过程的影响。分析和实验结果表明，通过调节2个计数器的宽度比α，在不增加内存空间的条件下，该算法有效降低了误判率。

关键词: 流量抽样, 布鲁姆过滤器, 组合布鲁姆过滤器, 长度调节因子

Abstract:

An early traffic sampling algorithm was proposed based on same source and combination Bloom filter (SSCBF),a structure with two Bloom filters:flow-sampling vector and packet-count vector.The hash functions of the two vectors were same but the counters’ widths were different.This structure separated the sampling judgment and the packets counting.That could avoid the interference with packet count vector by the finished sampling flows.The false positive rate of the algorithm and an adjustable parameter α,ratio of the two vectors’ widths,were analyzed.The analysis and experiments demonstrate that with suitable α,the algorithm can achieve higher accuracy without increasing the space complexity.

Key words: traffic sampling, Bloom filter, combinational Bloom filter, length adjustable factor

侯颖,郭云飞,黄海,王凯. 基于同源组合布鲁姆过滤器的早期流量抽样算法[J]. 通信学报, 2014, 35(10): 117-126.

Ying HOU,Yun-fei GUO,Hai HUANG,Kai WANG. Early traffic sampling algorithm based on SSCBF[J]. Journal on Communications, 2014, 35(10): 117-126.

图/表 16

图1

图2

表1

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

表2

参考文献 14

[1]	BERNAILLE L , TEIXEIRA R , AKODKENOU I . Traffic classification on the fly[A]. ACM SIGCOMM Computer Communication Review[C]. 2006,36(2): 23-26.
[2]	杨皙, 李领治, 纪其进 . 基于最短划分距离的网络流量决策树分类方法[J]. 通信学报, 2012,33(3): 90-102. YANG Z , LI L Z , JI Q J . Algorithm based on double counter bloom filter for large flows identification[J]. Journal on Communications, 2012,33(3): 90-102
[3]	张宏莉, 鲁刚 . 分类不平衡协议流的机器学习算法评估与比较[J]. 软件学报, 2012,23(6): 1500-1516. ZHANG H L , LU G . Machine learning algorithms for classifying the imbalanced protocol flows:evaluation and comparison[J]. Journal of Software, 2012,23(6): 1500-1516
[4]	CiscoRandom sampled netflow[EB/OL]..
[5]	ABHISHEK K , JUN X . Sketch guided sampling-using on-line estimates of flow size for adaptive data collection[A]. Proceedings of IEEE INFOCOM[C]. 2005. 432-445
[6]	王洪波, 裴育杰, 林宇等 . 基于LRU的大流检测算法[J]. 电子与信息学报, 2007,29(10): 2487-2492. WANG H B , PEI Y J , LIN Y ,et al. A LRU based algorithm for identi-fying and measuring large flow[J]. Journal of Electronics &Information Technology, 2007,29(10): 2487-2492.
[7]	张震, 汪斌强, 张风雨 . 基于LRU-BF策略的网络流量测量算法[J]. 通信学报, 2013,(1): 111-120. ZHANG Z , WANG B Q , ZHANG F Y . Traffic measurement algorithm based on least recent used and Bloom filter[J]. Journal on Communi-cations, 2013,(1): 111-120
[8]	ESTAN C , VARGHESE G . New directions in traffic measurement and accounting:focusing on elephants,ignoring the mice[J]. ACM Trans on Computer Systems, 2003,21(3): 270-313.
[9]	吴桦, 龚俭, 杨望 . 一种基于双重Counter Bloom Filter的长流识别算法[J]. 软件学报, 2010,21(5): 1115-1126. WU H , GONG J , YANG W . Algorithm based on double counter bloom filter for large flows identification[J]. Journal of Software, 2010,21(5): 1115-1126.
[10]	FAN L , CAO P , ALMEIDA J . Summary cache:a scalable wide-area web cache sharing protocol[J]. IEEE/ACM Trans on Networking, 2000,8(3): 281-293.
[11]	SAAR C , YOSSI M . Spectral Bloom filters[A]. Proceedings of ACM SIGMOD International Conference on Management of Data[C]. San Diego,California,USA, 2003. 241-252.
[12]	FLAVIO B , MICHAEL M , RINA P ,et al.An improved construction for counting Bloom filters[A]. Proceedings of the 14th Conference on Annual European Symposium[C]. Zurich,Germany, 2006. 684-695.
[13]	NLANRNational laboratory for applied network research[EB/OL]..
[14]	谢鲲, 文吉刚, 张大方 ,等. 布鲁姆过滤器查询算法[J]. 软件学报, 2009,20(1): 96-108. XIE K , WEN J G , ZHANG D F ,et al. Bloom filter query algo-rithm[J]. Journal of Software, 2009,20(1): 96-108.

数据来源	流量数据名称	持续时间/min	总流数	总分组数
New Zealand ISP	20090105-220000-0.dsl	30	1 037 043	21 338 813
Waikato network	20110407-000000-0	30	817 893	10 388 222

算法/(Mpacket·s^?1)	k=1	k=2	k=3	k=4	k=5	k=6	k=7
NCBF	5.825	3.883	2.504	2.084	1.780	1.542	1.393
SSCBF	5.821	3.878	2.501	2.080	1.775	1.539	1.390
LRU-BF	5.412	3.551	2.294	1.975	1.710	1.505	1.366
LRU	4.218	4.218	4.218	4.218	4.218	4.218	4.218

基于同源组合布鲁姆过滤器的早期流量抽样算法

Early traffic sampling algorithm based on SSCBF

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 16

参考文献 14

相关文章 5

Metrics

推荐阅读 0

[1]	王勇,云晓春,王树鹏,王曦. CBFM：支持属性删减的布鲁姆过滤器矩阵多维元素查询算法[J]. 通信学报, 2016, 37(3): 139-147.
[2]	侯颖，郭云飞，黄海，王凯. 基于同源组合布鲁姆过滤器的早期流量抽样算法[J]. 通信学报, 2014, 35(10): 14-126.
[3]	田小梅,张大方,谢鲲,胡灿,杨晓波,史长琼. 基于计数布鲁姆过滤器的集合调和算法[J]. 通信学报, 2012, 33(8): 119-127.
[4]	朱国胜,余少华. 高速低功耗深度报文检测方法[J]. 通信学报, 2011, 32(4): 158-165.
[5]	谢鲲,秦拯,文吉刚,张大方,谢高岗. 联合多维布鲁姆过滤器查询算法[J]. 通信学报, 2008, 29(1): 56-64.