Measuring data (packets, bytes, flows, events) accurately and on a per-flow basis in high-speed networks is hard because one needs fast and dense memories which are a rare and expensive commodity. This has led to approximate schemes where the goal is to identify large "elephant" flows quickly and measure them. Thus, in network measurement, there is a gulf between what is desirable and what has been achievable. We revisit the topic of exact, per-flow measurement and propose a novel counter architecture, called "Counter Braids." We show how ideas from modern coding theory (notably Turbo codes) enable a counter architecture that is compact enough to fit into SRAMs and quite simple to implement; the essential idea is to "compress as you count." If time permits, I will briefly overview a congestion management scheme we have been developing for Ethernet as part of the IEEE 802.1 standards effort.

[slides]

Balaji Prabhakar is an Associate Professor of Electrical Engineering and Computer Science at Stanford University. He is interested in network algorithms, in scalable methods for network performance monitoring and simulation, in wireless (imaging) sensor networks, stochastic network theory and information theory. He has designed algorithms for switching, routing, bandwidth partitioning, load balancing, and web caching.

Balaji has been a Terman Fellow at Stanford University and a Fellow of the Alfred P. Sloan Foundation. He has received the CAREER award from the National Science Foundation, the Erlang Prize from the INFORMS Applied Probability Society, and the Rollo Davidson Prize from the University of Cambridge, awarded to young scientists for their contributions to probability and its applications. He has been co-recipient of best paper awards at Infocom and Hot Interconnects.