HIFI: A high-bandwidth flow identification algorithm and its applications

In this paper, we present a High-bandwidth Flow Identification algorithm, called HIFI, that is designed for use by routers to identify high-bandwidth flows. Rather than maintaining the bandwidth usage states of all flows, HIFI is able to identify K highest-bandwidth flows, where K greater than or equal to 1 is a constant, using O(K) space and incurring only O(1) per sample processing overheads. We show that HIFI can be used in conjunction with well-established flow testing criteria to curb improperly behaving flows in the Internet. Applications of HIFI include identifying high-bandwidth multimedia streams that do not respond to congestion and mitigating the effects of flooding denial-of-service attacks. Our simulation shows that HIFI performs the above tasks with high accuracy and low overheads.