Line speed heavy hitters on sliding windows

Sliding window measurements are required by network functionalities such as load balancing, traffic engineering, and intrusion detection. Previous works suggested finding the most frequent flows, also known as heavy hitters but the suggested algorithms are too slow for modern lines. This work introduces a novel randomized algorithm named HHAWAII that accelerates update time by performing lightweight updates for most packets. HHAWAII is evaluated on three real packet traces, it achieves a similar accuracy to previous algorithms and as much as 14x higher update throughput.