Highly Compact Virtual Active Counters For Per-flow Traffic Measurement

You Zhou University of Florida, USA
Yian Zhou Google Inc., USA
Shigang Chen University of Florida, USA
Youlin Zhang University of Florida, USA


Per-flow traffic measurement is a fundamental problem in the era of big network data, and has been widely used in many applications, including capacity planning, anomaly detection , load balancing, traffic engineering, etc. In order to keep up with the line speed of modern network devices (e.g., routers), per-flow measurement online module is often implemented by using on-chip cache memory (such as SRAM) to minimize per-packet processing time, but on-chip SRAM is expensive and limited in size, which poses a major challenge for traffic measurement. In response, much recent research is geared towards designing highly compact data structures for approximate estimation that can provide probabilistic guarantees for per-flow measurement. The state of art, called Counter Tree (CT), requires at least 2 bits per flow in memory consumption and more than 2 memory accesses per packet in processing time. In this paper, we propose a novel design of a highly compact and efficient counter architecture, called Virtual Active Counter estimation (VAC), which achieves faster processing speed (slightly more than 1 memory access per packet on average) and provides more accurate measurement results than CT under the same allocated memory. Moreover, VAC can perform well even with a very tight memory space (less than 1 bit per flow or even one fifth of a bit per flow). Theoretical analysis and experiments based on real network traces demonstrate the superior performance of VAC.

You may want to know: