Applications like network security, accounting/billing, and network forensics require counting packets in network connections or flows.

This problem has been studied for the past 10 years and there have been two main approaches.  The early approach sought to collect exact measurements: count every packet of every flow.  While very desirable, this approach is both expensive and not scalable.  This led to the second approach: count only the packets of the large "elephant" flows, ignore the small "mice" flows.  This approach requires quickly identifying elephants and counting their packets and is inherently approximate.

 We present a novel per-flow counting method that is scalable, simple to implement and accurate.  Our method introduces and uses two innovations:

(i) a message passing estimation algorithm derived from sparse random graph codes, and (ii) a new data structure, called "counter braids,"

which is an efficient way of saving counter space while measuring flows of widely varying sizes (e.g. elephants and mice).

 Joint work with: S. Dharmapurikar, A. Kabbani, Y. Lu and A. Montanari.

About the Speaker

Balaji Prabhakar is an Associate Professor of Electrical Engineering and Computer Science at Stanford University.  He is interested in network algorithms, in scaleable methods for network performance monitoring, and stochastic network theory.  He has worked on  algorithms for switching, routing, bandwidth partitioning, load balancing, congestion management and web caching.  He is currently on leave from Stanford at a startup where he is helping design a Data Center system.

 He has been a Terman Fellow at Stanford University and a Fellow of the Alfred P. Sloan Foundation. He has received the NSF CAREER award, the Erlang Prize from the INFORMS Applied Probability Society, and the Rollo Davidson Prize from the University of Cambridge.