Flow Fair Sampling Based on Multistage Bloom Filters
Abstract: Network traffic
distribution is heavy-tailed. Most of network flows are short and carry very
few packets, and the number of large flows is small. Traditional random
sampling tends to sample more large flows than short ones. However, many
applications depend on per-flow traffic other than just large flows. A flow
fair sampling based on multistage Bloom filters is proposed. The total
measurement interval is divided into n child time intervals. In each child time
interval, employ multistage Bloom filters to query the incoming packet’s flow
whether exists in flow information table or not. If exists, sample the packet
with staticsampling rate which is inversely proportional to the estimation flow
traffic up to the previous time interval; if not, that is it’s a new flow’s
first packet, create the flow information, insert it into the multistage Bloom filters
and sample the packet with 100% probability. The results show that the proposed
algorithm is accurate especially for short flows and easy to extend.
Author: Liu Yuanzhen, Huang
Shurong, Liu Jianzhao
Journal Code: jptkomputergg160268
