2008 Poster Sessions : Counter Braids: A Novel Counter Architecture

Student Name : Yi Lu
Advisor : Balaji Prabhakar
Research Areas: Computer Systems
Measuring data (packets, bytes, flows, events) accurately on a per-flow
basis in high-speed networks is hard because fast and dense memory is an 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."

Yi Lu is a Ph.D. student in the Electrical Engineering Dept, Stanford University. She is interested in algorithms for high-performance networking applications and approximate inference on graphical models. She received her B.S. and M.S. degrees in Electrical Engineering from Stanford University in 2004. Her Ph.D. study is supported by Cisco Stanford Graduate Fellowship.