Identifying high-rate flows based on Bayesian single sampling

On the Internet, high-rate flows that do not obey the TCP flow control mechanism can consume a large share of the link bandwidth and seriously affect other flows. Therefore, identifying high-rate flows is important for active queue management, traffic measurement and network security. Explicit measurement of high-rate flows is difficult because tracking the possible millions of flows needs correspondingly large high-speed memories. To reduce the measurement overhead, the deterministic 1-out-of-k sampling technique is adopted. Since the sampled packets are only a part of the whole traffic transmitted, it is critically important to identify high-rate flows correctly. However, there are no methods which are able to specify the identification accuracy. We develop a Bayesian single sampling method (BSS) which is able to identify high-rate flows with user-specified false positive rate (FPR) and false negative rate (FNR). The experimental results show that BSS can successfully identify high-rate flows with satisfied accuracy constraint.