|
|
|
| A Fair Packet Sampling Algorithm Based on Different Counting Methods between Elephant and Mice Flows |
| Wang Jing Wang Bin-qiang Zhang Zhen |
| National Digital Switching System Engineering and Technology Research Center, Zhengzhou 450002, China |
|
|
|
|
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.
|
|
Received: 14 November 2013
|
|
|
|
Corresponding Authors:
Wang Jing
E-mail: zhuwangzilz@163.com
|
|
|
|
|
|
|
2014, Vol. 36 
