Sequential Zeroing: Online Heavy-Hitter Detection on Programmable Hardware

Sequential Zeroing: Online Heavy-Hitter Detection on Programmable Hardware

Turkovic, B. (TU Delft Embedded Systems)
Oostenbrink, J. (TU Delft Embedded Systems)
Kuipers, F.A. (TU Delft Embedded Systems)
Keslassy, Isaac (Technion)
Orda, Ariel (Technion)

2020

F1ows that have exceeded a given percentage of the last sliding window of N packets, denoted as heavy-hitter flows, require special handling, since they may disrupt the service of other flows or may be indicative of malicious traffic. However, even when equipped with a programmable switch, it is unclear how to detect heavy hitters on a per-packet basis, while obeying the stringent switch memory access rates. For instance, existing solutions, such as HashPipe, cannot detect heavy hitters without halving the line rate and do not support sliding windows. To the best of our knowledge, this paper is the first to present heavy-hitter detection solutions that provide per-packet granularity at line-rate performance. We realize this by introducing (1) Modulo sketching, a novel counting algorithm that reuses counters and limits the impact of smaller flows beyond early processing stages; and (2) Sequential Zeroing, a new approach to extending interval-based schemes to sliding window measurements. Our solutions are extensively evaluated, both via simulations and experiments on a Netronome SmartNIC, and demonstrate significant performance gains over the state-of-theart.

http://resolver.tudelft.nl/uuid:98d81302-8611-42e1-93a1-20ed877e6ad5

IFIP

978-3-903176-28-7

IFIP Networking 2020 Conference and Workshops, Networking 2020

19th International IFIP TC6 Networking Conference, Networking 2020, 2020-06-22 → 2020-06-25, Paris, France

IFIP Networking 2020 Conference and Workshops, Networking 2020

Virtual/online event due to COVID-19 accepted author manuscipt

Institutional Repository

conference paper

© 2020 B. Turkovic, J. Oostenbrink, F.A. Kuipers, Isaac Keslassy, Ariel Orda