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.
Keywords: network traffic, short flow, multistage bloom filters, flow fair sampling
Author: Liu Yuanzhen, Huang Shurong, Liu Jianzhao
Journal Code: jptkomputergg160268

Artikel Terkait :