Volumetric Hierarchical Heavy Hitters

Hierarchical heavy hitters (HHH) identification is useful for various network utilities such as anomaly detection, DDoS mitigation, and traffic analysis. However, the increasing support for jumbo frames enables attackers to overload the system with fewer packets, avoiding detection by packet counting techniques. This paper suggests an efficient algorithm for detecting HHH based on their traffic volume that asymptotically improves the runtime of previous works. We implement our algorithm in Open vSwitch (OVS) and incur a 4-6% overhead compared to a 42% throughput reduction experienced by the state-of-the-art.

• Publication year

  2018

• Venue

  IEEE/ACM International Symposium on Modeling, Analysis, and Simulation On Computer and Telecommunication Systems

• Publication date

  2018-09-01

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1109/MASCOT.2018.8611241
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Network-Wide Heavy Hitter Detection with Commodity Switches

  2018cited by this paper
• Elastic sketch: adaptive and fast network-wide measurements

  2018cited by this paper
• Network-wide routing-oblivious heavy hitters

  2018cited by this paper
• Stroboscope: Declarative Network Monitoring on a Budget

  2018cited by this paper
• Resilient Datacenter Load Balancing in the Wild

  2017cited by this paper
• A high-performance algorithm for identifying frequent items in data streams

  2017cited by this paper
• Constant Time Weighted Frequency Estimation for Virtual Network Functionalities

  2017influential reference
• Fast Flow Volume Estimation

  2017cited by this paper
• Constant Time Updates in Hierarchical Heavy Hitters

  2017influential reference
• Optimal elephant flow detection

  2017influential reference
• Heavy hitters in streams and sliding windows

  2016cited by this paper
• Heavy-Hitter Detection Entirely in the Data Plane

  2016cited by this paper
• New Algorithms for Heavy Hitters in Data Streams (Invited Talk)

  2016cited by this paper
• Randomized admission policy for efficient top-k and frequency estimation

  2016cited by this paper
• CONGA: distributed congestion-aware load balancing for datacenters

  2015cited by this paper
• The power of slightly more than one sample in randomized load balancing

  2015cited by this paper
• The Design and Implementation of Open vSwitch

  2015cited by this paper
• TinyLFU: A Highly Efficient Cache Admission Policy

  2014cited by this paper
• MoonGen: A Scriptable High-Speed Packet Generator

  2014cited by this paper
• Hierarchical Heavy Hitters with the Space Saving Algorithm

  2011influential reference
• A comparative study of two network-based anomaly detection methods

  2011cited by this paper
• Online Measurement of Large Traffic Aggregates on Commodity Switches

  2011cited by this paper
• MicroTE: fine grained traffic engineering for data centers

  2011cited by this paper
• DevoFlow: scaling flow management for high-performance networks

  2011cited by this paper
• Methods for finding frequent items in data streams

  2010cited by this paper
• AF-QCN: Approximate Fairness with Quantized Congestion Notification for Multi-tenanted Data Centers

  2010cited by this paper
• Finding hierarchical heavy hitters in streaming data

  2008influential reference
• LADS: Large-scale Automated DDoS Detection System

  2006cited by this paper
• Space complexity of hierarchical heavy hitters in multi-dimensional data streams

  2005cited by this paper
• Efficient Computation of Frequent and Top-k Elements in Data Streams

  2005cited by this paper
• Online identification of hierarchical heavy hitters: algorithms, evaluation, and applications

  2004cited by this paper
• Diamond in the rough: finding Hierarchical Heavy Hitters in multi-dimensional data

  2004cited by this paper
• Finding Hierarchical Heavy Hitters in Data Streams

  2003cited by this paper
• Adaptive random sampling for load change detection

  2002cited by this paper

• Volumetric DDoS Attack Detection and Mitigation using P4-DPDK

  2025cites this paper
• Sketch Disaggregation Across Time and Space

  2025cites this paper
• Scalable Heavy Hitter Detection: A DPDK-based Software Approach with P4 Integration

  2024cites this paper
• Together is Better: Heavy Hitters Quantile Estimation

  2023cites this paper
• Botnet Mapping Based on Intersections of Traces

  2022cites this paper
• The White-Box Adversarial Data Stream Model

  2022cites this paper
• SQUAD: combining sketching and sampling is better than either for per-item quantile estimation

  2022cites this paper
• Cooperative Network-wide Flow Selection

  2020cites this paper
• A Black-box Method for Accelerating Measurement Algorithms with Accuracy Guarantees

  2019cites this paper
• Cheetah: Accelerating Database Queries with Switch Pruning

  2019cites this paper
• Nitrosketch: robust and general sketch-based monitoring in software switches

  2019cites this paper
• Accurate and resource-efficient monitoring for future networks

  2019cites this paper
• Stream Frequency Over Interval Queries

  2018cites this paper
• Memento: Making Sliding Windows Efficient for Heavy Hitters

  2018cites this paper
• Heavy Hitters over Interval Queries

  2018cites this paper
• Memento: Making Sliding Windows Efficient for Heavy Hitters

  year unknowncites this paper