A Throughput-Efficient Packet Classifier with n Bloom Filters Conference Paper uri icon


  • Packet classification is a critical data path in a highspeed router. Due to memory efficiency and fast lookup, Bloom filters (BFs) have been widely used for packet classification in a high-speed router. However, in a parallel packet classifier (PPC) of n parallel BFs, using all n BFs for a lookup is not throughput efficient in a high speed router. In this paper, we propose a multi-tiered packet classifier (MPC) for high throughput with the same memory size as a PPC. While a PPC of n BFs needs (n) BF access complexity for a lookup, our MPC is geared to have the complexity which is probabilistically far less than (n). Furthermore, by preprocessing a group of lookups in one cycle, each lookup is assigned to its associated BF at best effort, so that a higher throughput in an MPC is obtained. In simulation for flow identification with NLANR traces, we observed that, at most, 2.0 times more throughput was recorded than a PPC. 2008 IEEE.

name of conference

  • IEEE GLOBECOM 2008 - 2008 IEEE Global Telecommunications Conference

published proceedings


author list (cited authors)

  • Yu, H., & Mahapatra, R.

citation count

  • 0

complete list of authors

  • Yu, Heeyeol||Mahapatra, Rabi

publication date

  • January 2008