|
|
- 2015
基于CBF-SS策略的大流识别算法
|
Abstract:
摘要 在分析大流识别算法中的散列方法和计数方法的优缺点的基础上,针对网络流的重尾分布特性,提出一种能够有效结合散列方法和计数方法优点的大流识别算法CBF-SS(counting Bloom filter & space saving).该算法首先采用改进的计数型布鲁姆过滤器(counting Bloom filter,CBF)过滤掉大部分的小流,然后通过SS(space saving)计数算法识别出网络中的大流.理论分析和实验结果表明,CBF-SS算法具有较低的时间复杂度和空间复杂度,在大流识别效果上远优于SS等算法.
| [1] | <p> Hyunsang C, Heejo L. Identifying botnets by capturing group activities in DNS traffic[J]. Computer Networks, 2012, 56(1): 20-33. |
| [2] | 裴育杰,王洪波,程时端. 基于两级LRU机制的大流检测算法[J]. 电子学报, 2009, 37(4): 684-691. |
| [3] | 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. |
| [4] | 孙昱, 夏靖波, 赵小欢, 等. 基于LEAST和CBF两级结构的大流检测算法[J]. 华中科技大学学报:自然科学版, 2014, 42(4): 40-44. |
| [5] | 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. |
| [6] | 周明中. 大规模网络IP流行为特性及其测量算法研究[D]. 南京: 东南大学, 2006. |
| [7] | 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. |
| [8] | 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. |
| [9] | 张震, 汪斌强, 陈庶樵, 等. 基于多维计数型布鲁姆过滤器的大流检测机制[J]. 电子与信息学报, 2010, 32(7): 1 608-1 613. |
| [10] | 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. |
| [11] | 王风宇, 郭山清, 李亮雄, 等. 一种高效率的大流提取方法[J]. 计算机研究与发展, 2013, 50(4): 731-740. |
| [12] | Cormode G, Hadjieleftheriou M. Finding the frequent items in streams of data[J]. Communications of ACM, 2009, 52(10): 97-105. |
| [13] | 谢冬青, 周再红, 骆嘉伟. 基于LRU和SCBF的大象流提取及其在DDoS防御中的应用[J]. 计算机研究与发展, 2011, 48(8): 1 517-1 523. |
| [14] | 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/. |
| [15] | MAWI Working Group. MAWI working group traffic archive[EB/OL]. (2013-04-26)[2014-03-01]. http://mawi.wide.ad.jp/2011.</p> |
| [16] | 周爱平, 程光, 郭晓军. 高速网络流量测量方法[J]. 软件学报, 2014, 25(1): 135-153. |
| [17] | 张玉, 方滨兴, 张永铮. 高速网络监控中大流量对象的识别[J]. 中国科学: 信息科学, 2010, 40(2): 340-355. |
| [18] | 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. |
| [19] | 吴桦, 龚俭, 杨望. 一种基于双重Counter Bloom Filter的长流识别方法[J]. 软件学报, 2010, 21(5): 1 115-1 126. |
| [20] | 王风宇,云晓春,王晓峰, 等. 高速网络监控中大流量对象的提取[J]. 软件学报,2007, 18(12): 3 060-3 070. |
| [21] | 夏靖波, 赵小欢, 柏骏, 等. 基于时间和流长约束的网络流频繁项挖掘算法[J]. 中国科学技术大学学报, 2013, 43(10): 790-798. |
| [22] | 张震, 汪斌强, 张风雨, 等. 基于LRU_BF策略的网络流量测量算法[J]. 通信学报, 2013, 34(1): 111-120. |
| [23] | 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. |
| [24] | 赵小欢, 夏靖波, 付凯. 基于散列和计数方法的网络流频繁项挖掘算法[J]. 华中科技大学学报:自然科学版, 2013, 41(9): 57-62. |
| [25] | 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. |
