High-throughput sketch update on a low-power stream processor

Abstract

Sketch algorithms are widely used for many networking applications, such as identifying frequent items, top-k flows, and traffic anomalies. This paper explores the implementation of the Count-Min sketch update using Indexed SRF accesses on a SIMD stream processor (Imagine). Both the sketch data structure and the packet stream are modeled as streams, and in-lane accesses to the stream register file (SRF) support concurrent updates without explicit synchronization. The 500-MHz stream processor is capable of supporting sketch update at 10 Gbps throughput for minimum-sized IP packets. This is nearly the same performance as the 1.4-GHz Intel IXP2800 (13 Gbps), using significantly less power (2.89W vs. 21W).