Constant Time Updates in Hierarchical Heavy Hitters
arXiv:1707.06778 · doi:10.1145/3098822.3098832
Abstract
Monitoring tasks, such as anomaly and DDoS detection, require identifying frequent flow aggregates based on common IP prefixes. These are known as \emph{hierarchical heavy hitters} (HHH), where the hierarchy is determined based on the type of prefixes of interest in a given application. The per packet complexity of existing HHH algorithms is proportional to the size of the hierarchy, imposing significant overheads. In this paper, we propose a randomized constant time algorithm for HHH. We prove probabilistic precision bounds backed by an empirical evaluation. Using four real Internet packet traces, we demonstrate that our algorithm indeed obtains comparable accuracy and recall as previous works, while running up to 62 times faster. Finally, we extended Open vSwitch (OVS) with our algorithm and showed it is able to handle 13.8 million packets per second. In contrast, incorporating previous works in OVS only obtained 2.5 times lower throughput.
arXiv commentTo appear in ACM SIGCOMM 2017
References in corpus (2)
Cited by in corpus (13)
- ChameleMon: Shifting Measurement Attention as Network State Changes
- A survey of sketches in traffic measurement: Design, Optimization, Application and Implementation
- Exploring Network-Wide Flow Data with Flowyager
- Routing Oblivious Measurement Analytics
- Memory-Efficient Performance Monitoring on Programmable Switches with Lean Algorithms
- Locality-Sensitive Sketching for Resilient Network Flow Monitoring
- Heavy Hitters over Interval Queries
- Unleashing In-network Computing on Scientific Workloads
- Sketchy With a Chance of Adoption: Can Sketch-Based Telemetry Be Ready for Prime Time?
- Faster and More Accurate Measurement through Additive-Error Counters
- Fast Flow Volume Estimation
- MVPipe: Enabling Lightweight Updates and Fast Convergence in Hierarchical Heavy Hitter Detection
- 2FA Sketch: Two-Factor Armor Sketch for Accurate and Efficient Heavy Hitter Detection in Data Streams