收稿日期: 2014-03-31
修回日期: 2014-07-22
网络出版日期: 2015-05-15
基金资助
国家自然科学基金(61201209)和陕西省自然科学基金重点项目(2012JZ8005)资助
Large flow identification based on counting Bloom filter and space saving
Received date: 2014-03-31
Revised date: 2014-07-22
Online published: 2015-05-15
在分析大流识别算法中的散列方法和计数方法的优缺点的基础上,针对网络流的重尾分布特性,提出一种能够有效结合散列方法和计数方法优点的大流识别算法CBF-SS(counting Bloom filter & space saving).该算法首先采用改进的计数型布鲁姆过滤器(counting Bloom filter,CBF)过滤掉大部分的小流,然后通过SS(space saving)计数算法识别出网络中的大流.理论分析和实验结果表明,CBF-SS算法具有较低的时间复杂度和空间复杂度,在大流识别效果上远优于SS等算法.
关键词： 网络流; 大流; 计数型布鲁姆过滤器; space saving算法
赵小欢 , 李明辉 . 基于CBF-SS策略的大流识别算法[J]. 中国科学院大学学报, 2015 , 32(3) : 391 -397 . DOI: 10.7523/j.issn.2095-6134.2015.03.015
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
[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.
/
| 〈 |
|
〉 |
