Abstract:The previous fair packet sampling algorithm of Sketch Guided Sampling (SGS) has large estimation error for mice flows. A Fair packet Sampling algorithm based on Different Counting Methods between elephant and mice flows (DCMFS) is proposed, and the quantificational influence of hash collisions on estimation error of SGS is thoroughly analyzed. The key innovation is to use an elephant and mice flows differentiating counter to count the mice flows one by one and count the elephant ones by counting sketch.[w1] The theoretical analysis and evaluation on real traffic traces show that each mice flow can be estimated accurately by DCMFS and the elephant ones’ estimation error can reach the theoretical value of SGS. Due to the unequal length counter structure, DCMFS does not introduce much more counting space than SGS and Adaptive Non-Linear Sampling (ANLS). Though the replacement of counters in DCMFS introduces more time complexity than SGS, it can still support the 10 Gbps line-speed processing.
王晶, 汪斌强, 张震. 一种基于大小流区分计数的公平抽样算法[J]. 电子与信息学报, 2014, 36(10): 2350-2356.
Wang Jing, Wang Bin-Qiang, Zhang Zhen. A Fair Packet Sampling Algorithm Based on Different Counting Methods between Elephant and Mice Flows. , 2014, 36(10): 2350-2356.