Time-Out Bloom Filter: A New Sampling Method for Recording More Flows

摘要

Packet sampling is widely deployed to generate flow records on high speed links. However, random sampling in which 1 in N packets is chosen suffers from omitting majority of flows, most of which are short flows (within N packets). Although usage-based applications work well by sampling long flows and neglecting short ones, there are many other applications which depend on nearly per-flow information. In this paper, a novel sampling method is proposed to remedy the flow loss flaw. We use a Time-out Bloom Filter to alleviate the sampling bias towards long flows. Compared with random sampling, short flows have a much greater probability to be sampled while long flows are always sampled, but with much fewer sampled packets. Experimental results show that, with the same sampling rate, our solution records several times more short flows than random sampling. Particularly, up to 99% original flows can be retrieved. Besides, we also propose an adaptive TBF system in fast SRAM to perform online sampling.