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.
![](https://private-user-images.githubusercontent.com/47865109/241557125-f2c48a0a-cdbe-4718-9913-dac10b7d4e56.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjE1Mjg1MDUsIm5iZiI6MTcyMTUyODIwNSwicGF0aCI6Ii80Nzg2NTEwOS8yNDE1NTcxMjUtZjJjNDhhMGEtY2RiZS00NzE4LTk5MTMtZGFjMTBiN2Q0ZTU2LnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA3MjElMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwNzIxVDAyMTY0NVomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPTNmYTkyZjZlZDZkYzFiYzQyZGFiZjM1NGUxZjdmMWNhOTU4NzA2Mzk3M2Q3MjgwZDE2ZmFmYTJhZjdkNTMzNDEmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.Z5wvfUUTqqxnzjiP_nlutRea0sszzw8k7_qxQzGVV6I)
CMSIS is based on a 2-way Count-Min sketch, and maintains a structure that stores identifiers of flows suspected to be heavy hitters.
![](https://private-user-images.githubusercontent.com/47865109/241557334-56111a53-ff30-45c9-b255-553e5b58a0d8.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjE1Mjg1MDUsIm5iZiI6MTcyMTUyODIwNSwicGF0aCI6Ii80Nzg2NTEwOS8yNDE1NTczMzQtNTYxMTFhNTMtZmYzMC00NWM5LWIyNTUtNTUzZTViNThhMGQ4LnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA3MjElMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwNzIxVDAyMTY0NVomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPTRmNTVjYjgxMzFkY2Q5YzhmODEwYTg1MDc1MmJlYjFiNWQyYWM1ZGM5OWY0MDM2NjhhZmI3MDExYTVlODMzZTUmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.2vxSWyz0hvEUCS6cmR7irWjq6kn_wyN5W3Y67202Jgs)
CMS+Threshold is an adaption of Count-Min sketch for heavy hitter detection.