Network-Wide Heavy-Hitter Detection for Real-Time Telemetry

Abstract:

Many network monitoring tasks identify subsets of trac that stand out, e.g., top-
k
ows for a particular statistic. We can eciently determine these \heavy-hitter"

ows on individual network elements, but network operators often want to identify
interesting trac on a network-wide basis. Determining the heavy hitters on
a network-wide basis necessarily introduces a trade-o between the communication required to perform this distributed computation and the accuracy of the results. To perform distributed heavy-hitter detection in real time with high accuracy and low overhead, we extend the Continuous Distributed Monitoring (CDM) model to account for the realities of modern networks and devise practical solutions that detect heavy hitters with high accuracy and low communication overhead. We present two novel algorithms that automatically tune the set of monitoring switches in response to traffic dynamics. We implement our system using the P4 language, and evaluate it using real-world packet traces. We demonstrate that our solutions can accurately detect network-wide heavy hitters with up to 70% savings in communication overhead compared to existing approaches.