一种基于双重Counter Bloom Filter的长流识别算法

Algorithm Based on Double Counter Bloom Filter for Large Flows Identification

提出了一种基于双层Counter Bloom Filter的长流识别算法(algorithm based on double counter bloom filter for long flows identification,简称CCBF).该算法使用两层Counter Bloom Filter结构,将长流过滤和长流存在分开处理.分析了该算法的误判率,通过模拟数据分析了算法错误率和内存资源限制的关系,并在相同内存资源限制的条件下,将该算法与类似算法的准确性进行了比较.结果表明,在数据量较大的情况下,该算法具有比现有算法更小的平均错误率;对算法的时间效率分析表明,该算法可以达到1500kpps的处理速度.各项指标反映出,该算法可以应用于大规模主干网的长流监测.

An algorithm based on double counter bloom filter for long flows identification （CCBF） is proposed in this paper. Double counter bloom filter structure is used to distinguish the process of the long flow filtration from the long flow existence. The false positive rate of the algorithm is analyzed. The relationship of the memory requirement and the error rate is analyzed through simulation. It is shown that with the same restriction of the memory resource, the average error of this algorithm is less than the existing similar algorithms. The analysis of the time performance shows this algorithm is capable of dealing with traffic up to 1 500kpps.The results reflect that this algorithm can be used to monitor the long flows on backbone network.