PaperlayerView exact revision on arXiv

Source-linked AI summary

Constant Time Updates in Hierarchical Heavy Hitters

Ran Ben Basat, Gil Einziger, Roy Friedman, Marcelo Caggiani Luizelli, Erez Waisbard

arXiv:1707.06778v1cs.DS

TL;DR

Existing hierarchical heavy hitter algorithms scale with hierarchy size, limiting their ability to support high-speed network measurement, including anomaly and DDoS detection. The paper introduces randomized constant-time HHH updates and reports comparable solution quality with up to 62× speedup, plus 13.8 million packets per second in Open vSwitch.

  • Problem

    Existing HHH algorithms have update complexity proportional to hierarchy size, while anomaly and DDoS detection require HHH measurements beyond individual heavy hitters at rapidly increasing line rates.

  • Method

    RHHH probabilistically samples packets and updates one randomly selected prefix, replacing per-packet computation of all prefixes with constant-time updates.

  • Results

    Across four real Internet traces, RHHH achieved comparable accuracy and recall with up to 62× speedup, while its OVS implementation reached 13.8 million packets per second and 2.5× better throughput than previous approaches.

  • Takeaways & Limitations

    RHHH provides a practical approach for HHH monitoring at line speed, particularly for multidimensional and IPv6 traffic with larger hierarchies.

  • Takeaways & Limitations

    RHHH requires a minimum number of packets to converge to its formal accuracy guarantees, although the error can reach around 1% after approximately 8 million packets in the reported settings.

Abstract

from arXiv · show

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.

1 Introduction

Network measurements must handle rapid line rates and many active flows, while HHH algorithms address aggregate traffic patterns that ordinary heavy-hitter detection misses. This paper introduces RHHH, which updates one randomly selected hierarchy level per packet to achieve constant-time processing.

  • Network measurements support traffic engineering, load balancing, quality of service, caching, anomaly detection, and intrusion detection despite rapid line rates and many active flows.
  • Ordinary heavy-hitter detection misses distributed attacks because each device may contribute little traffic even when their combined volume is overwhelming.
  • Hierarchical heavy hitters identify IP prefixes responsible for large traffic shares across one or multiple source-destination dimensions.
  • Previous HHH algorithms require hierarchy-proportional updates, making them unable to handle examples such as over 10 million packets per second on a 100 Gbit link.
  • RHHH is evaluated on real traces and integrated with OVS to target fast software-based measurement at network line speeds.
  • RHHH randomly updates a single hierarchy level per packet, replacing updates to all levels and achieving O(1) worst-case update time.

2 Related Work

Prior HHH research developed streaming, TCAM, trie-based, and multidimensional approaches, but existing update costs remain too high for modern line speeds and large hierarchies. This paper instead presents a probabilistic HHH formulation with constant-time updates and a packet-volume trade-off.

  • Prior work introduced one-dimensional streaming and TCAM approximations and later extended HHH to multiple dimensions.
  • Trie-based Full Ancestry and Partial Ancestry algorithms use hierarchy-dependent space and update time, including O(H log(Nϵ)) time per update.
  • The seminal multidimensional approach maintained a separate Space Saving instance for each lattice node and updated all lattice nodes on every packet.
  • Existing methods are too slow for modern line speeds, especially in NFV environments and settings with large hierarchies.
  • The paper solves a probabilistic HHH problem with O(1) updates, trading formal accuracy guarantees for a required minimum number of packets.

3 Randomized HHH (RHHH)

RHHH formulates probabilistic approximate hierarchical heavy hitters and uses randomized sampling across hierarchy levels to reduce update cost to O(1). The relaxation supports approximate accuracy and coverage guarantees while retaining practical HHH detection across one- and two-dimensional prefix hierarchies.

  • 3.1 Basic terminology: The hierarchy can use bit or byte granularity, with one-dimensional prefix chains or two-dimensional source–destination lattices.Fully specified IP addresses are generalized by prefixes, and two-dimensional items can have separate source and destination parents.
  • 3.1 Basic terminology: HHH identifies prefixes whose conditioned frequency exceeds θ·N, excluding traffic already covered by selected HHH prefixes.Conditioned frequency subtracts traffic from fully specified items generalized by previously selected prefixes; two-dimensional cases use inclusion-exclusion to avoid double counting.
  • 3.1 Basic terminology: Probabilistic approximate HHH relaxes deterministic accuracy and coverage requirements, enabling faster algorithms.The paper defines this as a probabilistic relaxation of approximate HHH and uses it to develop a faster solution.
  • 3.2 Randomized HHH: RHHH maintains H independent heavy-hitter instances and updates at most one randomly selected instance per packet.The selected instance operates in O(1), unlike prior approaches that update every instance and require O(H) time.
  • 3.2 Randomized HHH: The randomized design trades exact per-packet processing for probabilistic guarantees and requires sufficient traffic for accuracy.Approximate HHH is motivated by the prohibitive space needed for exact heavy hitters, while the probabilistic formulation permits the randomized approach.

4 Evaluation

Evaluation on four real Internet traces compares RHHH and 10-RHHH with prior HHH algorithms across one- and two-dimensional hierarchies. The randomized methods converge toward comparable error behavior while providing substantial speedups, with 10-RHHH fastest overall.

  • 4 Evaluation: Four datasets contain 1 billion mixed UDP, TCP, and ICMP packets from Chicago and San Jose backbone routers.The evaluation uses source byte, source bit, and source/destination byte hierarchies, with repeated measurements and 95% confidence intervals.
  • 4.2 False Positives: RHHH accuracy improves as traces progress, converging near theoretical bounds after about 100 million packets for RHHH and 1 billion for 10-RHHH.The algorithms have a small probability of accuracy and coverage errors that decreases as the trace progresses.
  • 4.2 False Positives: False positive ratios for RHHH and 10-RHHH decrease as traces progress and become comparable to previous methods after reaching theoretical guarantees.In some cases, the randomized methods perform slightly better than the alternatives.
  • 4.3 Operation Speed: RHHH and 10-RHHH have similar performance across a wide range of ε values and datasets, while prior methods slow substantially as hierarchy size increases.The comparison covers 250M-packet traces in one- and two-dimensional domains.
  • 4.3 Operation Speed: 3.5x and 10x speedups are achieved for one-dimensional byte hierarchies by RHHH and 10-RHHH, respectively.The reported speedup varies with hierarchy type and algorithm configuration.
  • 4.3 Operation Speed: 21x and 62x speedups are achieved for one-dimensional bit hierarchies by RHHH and 10-RHHH, respectively.For two-dimensional byte hierarchies, the corresponding maximum speedups are 20x and 60x.

5 Virtual Switch Integration

The paper integrates approximate HHH monitoring into Open vSwitch through dataplane and distributed deployment options, then evaluates throughput under a 10 Gbit/s limit. The 10-RHHH dataplane reaches near-maximum packet rate, while larger sampling parameters improve performance and distributed deployment supports multiple traffic sources.

  • Integration methods: OVS was extended with approximate HHH monitoring in both the dataplane and a separate virtual machine.In the distributed design, OVS forwards relevant traffic to the measurement VM and can forward only sampled packets when V > H.
  • Evaluation setup: 14.88 Mpps is the maximum achievable rate on the 10 Gbit/s evaluation links.The experiment used two directly connected servers, DPDK-enabled OVS, and 1 billion 64-byte UDP packets.
  • Throughput results: 13.8 Mpps is achieved by 10-RHHH, only 4% below unmodified OVS; RHHH reaches 10.6 Mpps and Partial Ancestry reaches 5.6 Mpps.The paper reports that 10-RHHH and RHHH can cope with the cited line-speed examples.
  • Sampling parameter: Larger V values improve performance in both dataplane and distributed implementations.The improvement corresponds to fewer processed packets in the dataplane and fewer packets forwarded to the VM in the distributed design.
  • Deployment trade-off: The distributed implementation is somewhat slower but enables the measurement machine to process traffic from multiple sources.

6 Analysis

The analysis models randomized HHH updates probabilistically and establishes accuracy, coverage, correctness, and complexity guarantees. Under a sufficiently large measurement interval, RHHH solves approximate HHH with O(1) update complexity, while larger V can improve performance.

  • Probabilistic model: RHHH models packet updates as a balls-and-bins process with V bins, of which H trigger updates and V − H are ignored.The analysis approximates this process with independent Poisson variables to derive confidence intervals and then transfers the result to the original process.
  • Error decomposition: The analysis separates sampling fluctuations from the approximate heavy-hitter algorithm’s estimation error.The algorithm is configured to compensate for possible oversampling so accumulated error remains within the guarantee.
  • Accuracy: N > ψ is sufficient for the desired sample accuracy, with ε_s(N) > ε_s when N < ψ and ε_s(N) < ε_s when N > ψ.
  • Accuracy: For N > ψ, Theorem 6.6 gives δ ≥ δ_a + 2 · δ_s and ε ≥ ε_a + ε_s for frequency estimation.The analysis notes that this guarantee applies to every prefix, which is stronger than requiring accuracy only for returned HHH prefixes.
  • HHH correctness: For N > ψ, RHHH solves the (δ, ε, θ)-approximate HHH problem and satisfies coverage.The main result combines the accuracy and coverage results.
  • Complexity and tuning: RHHH has O(1) update complexity, and larger V can improve performance when the measurement interval is sufficiently long.Short measurements may require V = H, whereas longer measurements can justify V ≫ H.

7 Discussion

RHHH realizes HHH measurement in virtual network devices with O(1) worst-case processing, while preserving comparable solution quality and substantially improving performance. Its convergence requires sufficient traffic, but busy links can reduce the practical delay and error.

  • Discussion: O(1) worst-case processing replaces the traditional need to compute all prefixes for each incoming packet.RHHH samples traffic and updates one randomly selected prefix, avoiding hierarchy-sized per-packet work.
  • Discussion: X62 speedup was achieved over previous works on four real Internet traces while maintaining comparable solution quality.Each trace contained over 1 billion packets.
  • Discussion: 13.8 Mpps throughput was achieved in a DPDK-enabled OVS dataplane, only 4% below unmodified OVS and X2.5 above the fastest prior dataplane implementation.A distributed deployment processed up to 12.3 Mpps and can analyze traffic from multiple network devices.
  • Discussion: The OVS speedup was limited to X2.5 because experiments used a 10Gbps link, whereas direct processing achieved X62.The OVS implementation was only 4% below the unmodified OVS baseline, so faster or combined links could yield a larger relative advantage.
  • Discussion: RHHH requires a minimum packet volume to converge, reaching around 1% error after 8 million packets and full convergence by up to 100 million packets.At 10 million packets per second, these correspond to roughly 1 second for the lower error and 10 seconds for complete convergence.
Loading 1707.06778v1…