基于MGCBF算法的长流信息统计

Long flows' information statistics based on MGCBF algorithm

为提高流测量系统的运行效率,减小其所需存储资源,在分析网络中流长分布特性的基础上,提出一种新的用于测量长流数量并维护其流信息的算法———多粒度计数bloom filter(MGCBF).利用较少的固定存储空间,MGCBF可以在保持较小误差比例的情况下,对所有到达的流基于报文计数.在MGCBF算法的基础上以指定报文数为阈值建立了一个长流信息统计模型,并对该模型所需的存储空间、计算复杂度和计算误差进行了分析和讨论.通过将其分别应用于来自不同网络的TRACE:CERNET和CESCAI,验证了该算法在保证测量精度的同时可以大幅度减小维护流信息所需的系统资源.

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.