Large flow identification based on counting Bloom filter and space saving

doi:10.7523/j.issn.2095-6134.2015.03.015

Abstract

Abstract:

Aiming at the characteristics of the heavy-tailed distribution of network flows, we propose a large flow identification algorithm, CBF-SS(counting Bloom filter and space saving), on the basis of analyzing advantages and deficiencies of hashing and counting methods used for large flow identification. It has the capability of combining the advantages of hashing and counting methods efficiently. The algorithm CBF-SS uses the counting Bloom filter to filter mass of small flows at first. Then, CBF-SS uses the SS (space saving) counting method to our large flows. Both theoretical and experimental results show that CBF-SS is very space-saving and time-efficient and it performs much better than the SS algorithm in the precision of large flow identification.

Key words: network flows, large flows, counting Bloom filter, space saving

CLC Number:

TP393

ZHAO Xiaohuan, LI Minghui. Large flow identification based on counting Bloom filter and space saving[J]. , 2015, 32(3): 391-397.

References

[1] Hyunsang C, Heejo L. Identifying botnets by capturing group activities in DNS traffic[J]. Computer Networks, 2012, 56(1): 20-33.

[2] 周爱平, 程光, 郭晓军. 高速网络流量测量方法[J]. 软件学报, 2014, 25(1): 135-153.

[3] 张玉, 方滨兴, 张永铮. 高速网络监控中大流量对象的识别[J]. 中国科学: 信息科学, 2010, 40(2): 340-355.

[4] Estan C, Varghese G. New directions in traffic measurement and accounting: focusing on the elephants, ignoring the mice[J]. ACM Transactions on Computer Systems, 2003, 21(3): 270-313.

[5] Manku G S, Motwani R. Approximate frequency counts over data streams[C]//Proc of the 28th International Conference on Very Large Data Bases, Hong Kong, 2002:346-357.

[6] Cormode G, Muthukrishnan S. What's hot and what's not: tracking most frequent items dynamically[J]. ACM Transactions on Database Systems, 2005, 30(1): 249-278.

[7] 张震, 汪斌强, 陈庶樵, 等. 基于多维计数型布鲁姆过滤器的大流检测机制[J]. 电子与信息学报, 2010, 32(7): 1 608-1 613.

[8] 吴桦, 龚俭, 杨望. 一种基于双重Counter Bloom Filter的长流识别方法[J]. 软件学报, 2010, 21(5): 1 115-1 126.

[9] 王风宇,云晓春,王晓峰, 等. 高速网络监控中大流量对象的提取[J]. 软件学报,2007, 18(12): 3 060-3 070.

[10] 裴育杰,王洪波,程时端. 基于两级LRU机制的大流检测算法[J]. 电子学报, 2009, 37(4): 684-691.

[11] Karp R M, Shenker S, Papadimitriou C H. A simple algorithm for finding frequent elements in streams and bags[J]. ACM Transactions on Database Systems, 2003, 28(1): 51-55.

[12] 夏靖波, 赵小欢, 柏骏, 等. 基于时间和流长约束的网络流频繁项挖掘算法[J]. 中国科学技术大学学报, 2013, 43(10): 790-798.

[13] Metwally A, Agrawal D, Abbadi A E. Efficient computation of frequent and Top-k elements in data streams //Proc. of the International Conference on Data Theory. Edinburgh: Springer-Verlag, 2005:398-412.

[14] 王风宇, 郭山清, 李亮雄, 等. 一种高效率的大流提取方法[J]. 计算机研究与发展, 2013, 50(4): 731-740.

[15] Cormode G, Hadjieleftheriou M. Finding the frequent items in streams of data[J]. Communications of ACM, 2009, 52(10): 97-105.

[16] Liu H Y, Lin Y, Han J W. Methods for mining frequent items in data streams: an overview[J]. Knowledge and Information System, 2011, 26(1): 1-30.

[17] 张震, 汪斌强, 张风雨, 等. 基于LRU_BF策略的网络流量测量算法[J]. 通信学报, 2013, 34(1): 111-120.

[18] 谢冬青, 周再红, 骆嘉伟. 基于LRU和SCBF的大象流提取及其在DDoS防御中的应用[J]. 计算机研究与发展, 2011, 48(8): 1 517-1 523.

[19] 赵小欢, 夏靖波, 付凯. 基于散列和计数方法的网络流频繁项挖掘算法[J]. 华中科技大学学报:自然科学版, 2013, 41(9): 57-62.

[20] 孙昱, 夏靖波, 赵小欢, 等. 基于LEAST和CBF两级结构的大流检测算法[J]. 华中科技大学学报:自然科学版, 2014, 42(4): 40-44.

[21] Fan L, Cao P, Almeida J, et al. Summary cache: a scalable wide-area web cache sharing protocol[J]. IEEE/ACM Transactions on Networking, 2000, 8(3): 281-293.

[22] 周明中. 大规模网络IP流行为特性及其测量算法研究[D]. 南京: 东南大学, 2006.

[23] Dainotti A, Pescape A, Ventre G. A packet-level characterization of network traffic[C]//Proc of the 11th Int Workshop on CAMAD. Piscataway: IEEE, 2006: 38-45.

[24] The Cooperative Association for Internet Data Analysis. The CAIDA anonymized OC48 Internet traces dataset[EB/OL]. (2012-11-10)[2014-03-01]. http://www.caida.org/.

[25] MAWI Working Group. MAWI working group traffic archive[EB/OL]. (2013-04-26)[2014-03-01]. http://mawi.wide.ad.jp/2011.