The Taub Faculty of Computer Science Events and Talks

Programmable switches enable offloading various network functions, such as anomaly detection and traffic engineering, to the same switches that perform packet routing. A basic component in many such applications is detecting heavy hitters (largest flows).

Realizing such data plane algorithms requires taking into consideration all types of limited hardware resources of the switch, including the recirculation bandwidth, number of stages, and memory. This motivates solutions that avoid recirculation when possible and fit into a minimal number of stages, even at the cost of slightly higher memory usage, since memory is not a tight resource on modern programmable switches.

We introduce a novel sketch for heavy hitter detection, CMSIS, that supports both online detection and offline retrieval of heavy hitters and achieves high accuracy while incurring low resource consumption. In particular, CMSIS requires no recirculation and consumes 25% less pipeline stages than state-of-the-art alternatives that do not perform recirculation, while its memory consumption is competitive with prior works.