Source-linked AI summary
Heavy-Hitter Detection Entirely in the Data Plane
Vibhaalakshmi Sivaraman, Srinivas Narayana, Ori Rottenstreich, S. Muthukrishnan, Jennifer Rexford
TL;DR
Heavy-hitter detection is valuable for network management but must operate at line rate with limited switch memory. HashPipe uses a pipeline of hash tables to preferentially retain heavy flows in programmable data planes. In an ISP backbone trace, it identified 300 heavy hitters with less than 80KB and high accuracy.
Problem
Heavy-hitter monitoring must identify large flows at line rate despite limited processing capacity and memory in switching hardware.
Method
HashPipe uses pipelined hash tables that retain heavier flow keys and counts while evicting lighter flows over time.
Results
Less than 80KB of memory yielded less than 5% false negatives and 0.001% false positives for 300 heavy hitters in a 400,000-flow backbone trace.
Takeaways & Limitations
HashPipe provides high-accuracy heavy-flow detection within contemporary programmable-switch memory constraints.
Takeaways & Limitations
Feed-forward processing can create duplicate flow keys across pipeline tables, reducing space for heavy flows and splitting their counts.
Abstract
from arXiv · showhide
Identifying the "heavy hitter" flows or flows with large traffic volumes in the data plane is important for several applications e.g., flow-size aware routing, DoS detection, and traffic engineering. However, measurement in the data plane is constrained by the need for line-rate processing (at 10-100Gb/s) and limited memory in switching hardware. We propose HashPipe, a heavy hitter detection algorithm using emerging programmable data planes. HashPipe implements a pipeline of hash tables which retain counters for heavy flows while evicting lighter flows over time. We prototype HashPipe in P4 and evaluate it with packet traces from an ISP backbone link and a data center. On the ISP trace (which contains over 400,000 flows), we find that HashPipe identifies 95% of the 300 heaviest flows with less than 80KB of memory.
1 INTRODUCTION
Heavy-hitter monitoring matters for network management but is difficult at line rate because switches impose tight processing and memory constraints. HashPipe adapts programmable pipelines to retain heavy flows, achieving high accuracy with limited memory.
- Heavy-hitter identification supports congestion relief, capacity planning, anomaly and attack detection, forwarding-table caching, dynamic routing, and flow scheduling.
- Continuous, short-timescale detection could let switches identify heavy-flow packets as they are processed and treat them specially.
- Existing sampling and sketching approaches make accurate, low-overhead monitoring difficult, while ideal memory usage should scale with the number of heavy flows.
- Programmable switches support stateful, pipelined processing at 10-100 Gbps per port, but each stage has a deterministic time budget, limited memory accesses, and limited memory.
- HashPipe uses pipelined hash tables to retain larger-count keys while evicting lighter keys, updating or carrying state through successive stages.
- Less than 80KB identified 300 heavy hitters with less than 5% false negatives and 0.001% false positives in a 400,000-flow backbone trace.
2 BACKGROUND ON HEAVY-HITTER DETECTION
Heavy-hitter detection concerns identifying threshold-based or top-k flows while controlling false reports and size-estimation error. Existing sampling, sketches, and counter-based methods face accuracy, memory, lookup, decoding, or per-packet update constraints in programmable switches.
- Heavy hitters may be defined by exceeding fraction t of total traffic or as the top k flows by size; this paper uses the top-k definition.
- Flow granularity ranges from hosts to applications to transport connections, with finer granularity increasing key size and the number of entries needed for accurate tracking.
- Heavy-hitter systems must manage false positives, false negatives, and flow-size estimation error while operating under programmable-switch constraints.
- Aggressive packet undersampling, including 1% or even 0.01% sampling, can reduce estimation accuracy.
- Sample-and-hold requires a sufficiently large flow table, while sketches complicate flow-identifier recovery and accurate in-switch counter reading.
- Counter-based algorithms may update many counters during insertions, conflicting with the deterministic time budget for each packet.
- Space saving uses O(k) counters but requires finding the minimum counter, which emerging programmable hardware cannot directly support within its per-packet access budget.
3 HASHPIPE ALGORITHM
HashPipe adapts space saving to programmable switches by distributing state across a pipeline of hash tables and tracking a rolling minimum, enabling feed-forward processing under hardware constraints. It retains heavier keys while evicting lighter ones, but can create duplicate keys across stages.
- HashPipe design: HashPipe uses a pipeline of hash tables to track the k heaviest flows while avoiding a full-table minimum search.The design is inspired by space saving but modifies it for switch implementation.
- Accuracy basis: Space saving guarantees no underestimation and bounds overestimation by the table minimum, while guaranteeing presence for flows above the average table count.The average-count guarantee supports threshold-heavy-hitter detection but does not directly extend to top-k detection.
- Accuracy basis: Sampling only d counters can inflate the estimated minimum and affect space-saving guarantees, although evaluations found comparable minimum distributions.The sampled minimum is used because full-table minimum search is difficult in switch hardware.
- Hardware adaptation: Splitting the table into d disjoint stages enables pipelined memory accesses, avoiding the multiple same-table reads required by HashParallel.HashParallel samples d locations at once, whereas HashPipe reads exactly one slot in each stage.
- HashPipe design: Each packet accesses one slot per stage, carries the current key and count forward, and swaps with a smaller stored counter.A rolling minimum lets the pipeline compare carried and resident counters incrementally.
- Trade-offs: HashPipe can create duplicate keys across stages because incoming keys are always inserted in the first stage.Duplicates may split counts and consume slots, though the algorithm can merge many of them and evaluations found they occupy only a small portion of memory.
4 HASHPIPE PROTOTYPE IN P4
The HashPipe prototype implements the algorithm in P4 using stateful register arrays and per-stage hash functions. It was validated against a simulator and tested on a behavioral switch model.
- Validation: The P4 prototype and simulator produced identical hash tables at the end of a measurement interval on artificially generated packets.The comparison was run using the switch behavioral model and the simulator.
- Implementation: The prototype uses P4 match-action stages and register arrays to maintain flow identifiers and associated counters across packets.Each hash-table stage has its own persistent state and executes a default algorithm action for every packet.
- Implementation: Each stage hashes the flow identifier to select a table location, then reads and updates the stored key, count, and validity bit.The prototype uses customized hash functions of the form (a_i · x + b_i)%p, with co-prime coefficients across stages.
5 EVALUATION
HashPipe’s accuracy improves with additional table stages and memory, but gains diminish as duplicates and hash collisions increase. Across ISP and data center traces, it achieves low false-negative and false-positive rates and outperforms sampling and sketching baselines.
- 5.1 Tuning HashPipe: Increasing table stages above d = 4 improves accuracy, but gains diminish at d = 8 and beyond because duplicates and hash collisions increase.These trends hold across both ISP and data center scenarios, motivating the choice of d = 6 for subsequent experiments.
- 5.2 Accuracy of HashPipe: 5-10% false negatives are achieved for the top 60-300 heavy hitters using just 4500 counters on ISP traces averaging 400,000 flows.At 80KB, this corresponds to 4500 counters; in the data center trace, false negatives settle below 10% at 9KB for tested k values.
- 5.2 Accuracy of HashPipe: 0.01%-0.1% false positives occur across ISP table sizes and reported-heavy-hitter settings, while the data center rate remains under 3%.The ISP false-positive rate drops below 0.01% at a table size of 80KB.
- 5.3 HashPipe vs. Existing Solutions: HashPipe outperforms sample and hold and count-min sketch across the entire tested memory range, with a 15% smaller false-negative rate than sample and hold at 100KB.The count-min sketch remains within a 3-4% error difference from HashPipe from above.
- 5.3 HashPipe vs. Existing Solutions: HashPipe has negligible average error above 20,000 packets and 100% count-estimation accuracy for flows larger than 30,000 packets.Sample and hold has about 10% relative error above 80,000 packets, while count-min sketch can approach 20% error at 50,000 packets.
6 RELATED WORK
Prior work supports heavy-flow monitoring, per-flow measurement, and sketch-based counting, but each approach faces deployment or inversion challenges in programmable switches.
- Heavy-flow information supports traffic management, congestion reduction, capacity planning, anomaly detection, and forwarding-table caching.
- Per-flow measurement schemes and memory-efficient hashing aim to preserve flow state while enabling fast lookups.
7 CONCLUSION
The paper presents HashPipe for detecting heavy traffic flows within programmable-switch constraints and making results available as packets are processed. A P4 prototype and real-trace simulations show high accuracy within current switch memory limits.
- HashPipe detects heavy traffic flows within programmable-switch constraints and exposes them in the switch as packets are processed.
- The algorithm uses pipelined hash tables that preferentially retain heavy flows by evicting lighter flows from switch memory over time.
- A P4 prototype and simulations on real traffic traces demonstrate high accuracy within contemporary switch memory constraints.