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

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

Abstract

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

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.

Figures/Tables 16

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

数据来源	流量数据名称	持续时间/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

[1]	Dongmei YANG, Yue CHEN, Jianghong WEI, Xuexian HU. Identity-based puncturable signature scheme [J]. Journal on Communications, 2021, 42(12): 17-26.
[2]	Yong WANG,Xiao-chun YUN,ANGShu-peng WANG,Xi WANG. CBFM:cutted Bloom filter matrix for multi-dimensional membership query [J]. Journal on Communications, 2016, 37(3): 139-147.
[3]	Sheng WAN,Yuan-yuan HE,Feng-hua LI,Ben NIU,Hui LI,Xin-yu WANG. Bloom filter-based lightweight private matching scheme [J]. Journal on Communications, 2015, 36(12): 151-162.
[4]	. Early traffic sampling algorithm based on SSCBF [J]. Journal on Communications, 2014, 35(10): 14-126.
[5]	. Research on ciphertext search for the cloud environment [J]. Journal on Communications, 2013, 34(7): 16-153.
[6]	Fei XIANG,Chuan-yi LIU,Bin-xing FANG,Chun-lu WANG,HONGRui-ming Z. Research on ciphertext search for the cloud environment [J]. Journal on Communications, 2013, 34(7): 143-153.
[7]	Zhen ZHANG,Bin-qiang WANG,Feng-yu ZHANG,Ning-ning LIANG. Traffic measurement algorithm based on least recent used and Bloom filter [J]. Journal on Communications, 2013, 34(1): 111-120.
[8]	Xiao-mei TIAN,Da-fang ZHANG,Kun XIE,Can HU,Xiao-bo YANG,Chang-qiong SHI. Set reconciliation based on counting Bloom filters [J]. Journal on Communications, 2012, 33(8): 119-127.
[9]	Hai-na TANG,Xiao-la LIN,Chun-jing HAN. Duplicate elimination algorithm for data streams with SKIP Bloom filter [J]. Journal on Communications, 2012, 33(2): 7-14.
[10]	Guo-sheng ZHU,Shao-hua YU. Hish speed deep packet inspection method with low power dissipation [J]. Journal on Communications, 2011, 32(4): 158-165.
[11]	Qiong HUANG,Wen-zhu XIONG,Xiao-long YANG,Jie XU,Ke-ping LONG. Hierarchical stateless single-packet IP traceback technique [J]. Journal on Communications, 2011, 32(3): 150-157.
[12]	Peng HUANG,Yuan-bo GUO,Wei LIU. Design of a hardware-based high-speed multi-pattern matching structure for network security applications [J]. Journal on Communications, 2010, 31(9A): 190-196.
[13]	Tao ZOU,Qing MIAO,Li LIU,Cui ZHANG. Performance analyzing of data reduction in network forensics system for chinese text content [J]. Journal on Communications, 2009, 30(10A): 93-96.
[14]	Kun XIE,Zheng QIN,Ji-gang WEN,Da-fang ZHANG,Gao-gang XIE. Combine multi-dimension Bloom filter for membership queries [J]. Journal on Communications, 2008, 29(1): 56-64.
[15]	Yi SUN,Jie PAN,Hua YAN. From sender's domain trust to IPv6's client absolutely trust [J]. Journal on Communications, 2006, 27(11A): 28-30.

Early traffic sampling algorithm based on SSCBF

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 16

References 14

Related Articles 15

Metrics

Recommended 0