This repository contains a P4 implementation of the CMSIS (Count-Min Sketch with Identifier Sampling) heavy-hitter detection / frequency estimation algorithm. The implementation was designed specifically to be run on Intel's Tofino 2 programmable switch.
The implementation (cmsis.p4) consumes 6 pipeline stages out of the 20 stages available on Tofino 2. This implementation defines 64-bit registers that store 5-tuple flow identifiers.
An alternative implementation (cmsis_32bit.p4) uses 32-bit registers instead of 64-bit registers as the latter are not available on Tofino 1. This 32-bit version needs twice the number of registers (arrays) needed by the 64-bit version to store the 5-tuple flow identifiers, therefore consuming 8 pipeline stages.
In addition, we provide an implementation (cms_threshold.p4) for a simple adaption of Count-Min sketch which performs online heavy hitter detection, but does not support offline retrieval of the heavy hitters' identifiers, as it does not store flow identifiers. This algorithm consumes only 3 pipeline stages.
CMSIS is based on a 2-way Count-Min sketch, and maintains a structure that stores identifiers of flows suspected to be heavy hitters.
CMS+Threshold is an adaption of Count-Min sketch for heavy hitter detection.