Precision Finding heavy hitters in the network

Project Description

PRECISION is a heavy hitter detection algorithm that uses Probabilistic Recirculation to find heavy flows on a programmable switch. By recirculating a small fraction of packets, we simplified PRECISION's access to stateful register memory and make it easier to implement on programmable switch hardware.

PRECISION maintains a list of flow ID and corresponding counters for flow size. Whenever a new packet arrives, PRECISION will check whether a counter for its flow ID already exists, and increment the counter if so. Otherwise, it will find approximately the current minimum counter c_min, and replace its flow ID with the incoming packet's flow ID with a small probability 1/(c_min+1), via packet recirculation.

• Measure heavy hitter flows in line-rate traffic
• More accurate than existing algorithms, running on data plane or general purpose computer
• Runs on real hardware with a Tofino chip

Code for BMv2

Project authors

Ran Ben Basat (ran@g.harvard.edu)
Xiaoqi Chen (xchen@cs.princeton.edu)
Gil Einziger (gilein@bgu.ac.il)
Ori Rottenstreich (or@cs.technion.ac.il)