[1]周明中,龚俭,丁伟,等.基于MGCBF算法的长流信息统计[J].东南大学学报(自然科学版),2006,36(3):472-476.[doi:10.3969/j.issn.1001-0505.2006.03.029]
 Zhou Mingzhong,Gong Jian,Ding Wei,et al.Long flows’ information statistics based on MGCBF algorithm[J].Journal of Southeast University (Natural Science Edition),2006,36(3):472-476.[doi:10.3969/j.issn.1001-0505.2006.03.029]
点击复制

基于MGCBF算法的长流信息统计()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
36
期数:
2006年第3期
页码:
472-476
栏目:
计算机科学与工程
出版日期:
2006-05-20

文章信息/Info

Title:
Long flows’ information statistics based on MGCBF algorithm
作者:
周明中 龚俭 丁伟 程光
东南大学计算机科学与工程学院, 南京 210096; 江苏省计算机网络技术重点实验室, 南京 210096
Author(s):
Zhou Mingzhong Gong Jian Ding Wei Cheng Guang
School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
Key Laboratory of Computer Networking Technology of Jiangsu Province, Nanjing 210096, China
关键词:
网络流量测量 流长计数 信息维护 MGCBF
Keywords:
network traffic measurement counting flow length information maintenance multi-granularity counting bloom filter(MGCBF)
分类号:
TP393
DOI:
10.3969/j.issn.1001-0505.2006.03.029
摘要:
为提高流测量系统的运行效率,减小其所需存储资源,在分析网络中流长分布特性的基础上,提出一种新的用于测量长流数量并维护其流信息的算法——多粒度计数bloom filter(MGCBF).利用较少的固定存储空间,MGCBF可以在保持较小误差比例的情况下,对所有到达的流基于报文计数.在MGCBF算法的基础上以指定报文数为阈值建立了一个长流信息统计模型,并对该模型所需的存储空间、计算复杂度和计算误差进行了分析和讨论.通过将其分别应用于来自不同网络的TRACE:CERNET和CESCAI,验证了该算法在保证测量精度的同时可以大幅度减小维护流信息所需的系统资源.
Abstract:
In order to improve the performance and reduce the resource usage of flow-based measurement systems, a novel long flow counting and information maintenance algorithm, multi-granularity counting bloom filter(MGCBF), is presented based on the distribution and characteristics analysis of long flows in the Internet. With less fixed memory used, the MGCBF maintains the counters for all incoming flows with small error probability, and keeps long flow information identified with a fixed packet number threshold, by which a statistical model for long flow information can be built up. The space used, calculation complexity and error probability of this model are also analyzed. The experiments which applied this model on different TRACEs named CERNET and CESCAI show that the MGCBF algorithm can reduce dramatically the resource usage in flows counting and information maintenance without losing accuracy.

参考文献/References:

[1] Brownlee N,Mills C,Ruth G.RFC 2722 Traffic flow measurement:architecture[S].IETF,1999.
[2] Shaikh A,Rexford J,Shin K G.Load-sensitive routing of long-lived IP flows[C] //Proc of the Conference on Applications,Technologies,Architectures,and Protocols for Computer Communication.New York:ACM Press,1999:215-226.
[3] Kim I,Reddy A L N.Analyzing network traces to identify long term high-rate flows[R].Technical report TAMU,2001.
[4] Estan Cristian,Varghese George.New directions in traffic measurement and accounting:focusing on the elephants,ignoring the mice [J]. ACM Trans Comput Syst,2003,21(3):270-313.
[5] Kumar A,Xu J,Wang J,et al.Space-code bloom filter for efficient per-flow traffic measurement [C] //IEEE INFOCOM 2004,the Conference on Computer Communications.Hong Kong,2004:1763-1774.
[6] Bloom B.Space/time trade-offs in hash coding with allowable errors [J]. Commun of ACM,1970,13(7):422-426.
[7] 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.
[8] Cohen S,Matias Y.Spectral bloom filters[C] // Proc of the 2003 ACM SIGMOD Int’l Conf on Management of Data[C].San Diego:ACM Press,2003:241-252.
[9] Claffy K C,Braun H W,Polyzos G C.A parameterizable methodology for internet traffic flow profiling[J]. IEEE Journal on Selected Areas in Communications,1995,13(8):1481-1494.
[10] NLANR.CESCAI TRACE[EB/OL].(2004-12-21)[2005-08-15].http://pma.nlanr.net/Special/cesc1.html.

备注/Memo

备注/Memo:
基金项目: 国家重点基础研究发展计划(973计划)资助项目(2003CB314804)、江苏省网络与信息安全重点实验室资助项目(BM2003201)、教育部科学技术研究重点资助项目(105084).
作者简介: 周明中(1976—),男,博士生; 龚俭(联系人),男,博士,教授,博士生导师,jgong@njnet.edu.cn.
更新日期/Last Update: 2006-05-20