基于CBF-SS策略的大流识别算法  

Large flow identification based on counting Bloom filter and space saving

作　　者：赵小欢[1] 李明辉[2] 

机构地区：[1]中国人民解放军95034部队 [2]空军后勤部

出　　处：《中国科学院大学学报（中英文）》2015年第3期391-397,共7页Journal of University of Chinese Academy of Sciences

基　　金：国家自然科学基金(61201209);陕西省自然科学基金重点项目(2012JZ8005)资助

摘　　要：在分析大流识别算法中的散列方法和计数方法的优缺点的基础上,针对网络流的重尾分布特性,提出一种能够有效结合散列方法和计数方法优点的大流识别算法CBF-SS(counting Bloom filter&space saving).该算法首先采用改进的计数型布鲁姆过滤器(counting Bloom filter,CBF)过滤掉大部分的小流,然后通过SS(space saving)计数算法识别出网络中的大流.理论分析和实验结果表明,CBF-SS算法具有较低的时间复杂度和空间复杂度,在大流识别效果上远优于SS等算法.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.

关 键 词：网络流 大流 计数型布鲁姆过滤器 SPACE saving算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]