基于LEAST和CBF两级结构的大流检测算法

LEAST and CBF two-level architecture based algorithm for identifying and measuring large flows

为了进一步降低大流检测算法在高速网络中的漏检率并提高大流流量的测量精度,提出了一种基于LEAST淘汰策略和计数型布鲁姆过滤器(CBF)两级结构的检测算法.在该算法中,CBF只是被用来滤除网络中的小流,并不须要占用太多的缓存空间.而通过CBF的流将进入下一级过滤机构中按LEAST淘汰策略进一步地筛选.从理论上分析了该算法对大流的检测能力,并针对其不足,提出了时间窗口和预留函数两种优化机制.最后基于实际的流量数据进行了实验验证,结果表明该算法的各项评价指标均优于同类算法.

In order to reduce the large flow missed probability and improve its traffic measurement precision further, a new algorithm for identifying and measuring large flows was proposed in high- speed network. The algorithm was based on a two-level architecture that was composed of a counting Bloom filter （CBF） and an elimination strategy called LEAST. In this algorithm, the CBF was just used to filter small flows in the network, which did not take up too much cache space. Those flows passing through the CBF successfully would reach the next filtering architecture where they would be further screened according to the LEAST elimination strategy. The performance of the proposed algo- rithm was analyzed theoretically, and then two optimization mechanisms called ＂time window＂ and ＂reserve function＂ were put forward to overcome its weaknesses. Finally, the algorithm was tested with the actual traffic data. The result shows that the evaluation indicators of the new algorithm are better than those of other similar algorithms.