基于同源组合布鲁姆过滤器的早期流量抽样算法

Early traffic sampling algorithm based on SSCBF

提出一种同源组合布鲁姆过滤器结构,该结构包含流抽样(sample)和分组计数(packet)2个计数器向量组合,2个计数器向量宽度不同,以相同的散列源函数计算散列位置。基于该结构设计的早期流量抽样算法利用2个计数器向量将流抽样判断与分组计数检测分开,避免了早期流量抽样中大量抽样已经结束的流对分组计数过程的影响。分析和实验结果表明,通过调节2个计数器的宽度比α,在不增加内存空间的条件下,该算法有效降低了误判率。

An early traffic sampling algorithm was proposed based on same source and combination Bloom filter（SSCBF）, a structure with two Bloom filters： flow-sampling vector and packet-count vector. The hash functions of thetwo vectors were same but the counters＇ widths were different. This structure separated the sampling judgment and thepackets counting. That could avoid the interference with packet count vector by the finished sampling flows. The falsepositive rate of the algorithm and an adjustable parameter ct, ratio of the two vectors＇ widths, were analyzed. The analysisand experiments demonstrate that with suitable ct, the algorithm can achieve higher accuracy without increasing the spacecomplexity.