Identifying high-rate flows with less memory

Unfairness among best-effort flows is a serious problem in the Internet. In particular, UDP flows or unresponsive flows that do not obey the TCP flow control mechanism or normal TCP flows with small RTT can consume a large share of the available bandwidth. Since they will seriously affect other flows, it is important to identify these high-rate flows and limit their throughput by selectively dropping their packets. In this paper, we propose a novel method that identifies high-rate flows using sampled packets. By reducing the timeout length for holding the flow state, the proposed method accurately identifies high-rate flows while using only a small amount of memory. We derive the identification probability for flows with arbitrary rates and obtain an identification curve that clearly reveals the identification accuracy.