Paper Info
Title
A Throughput-Efficient Packet Classifier with n Bloom filters
Abstract
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 Theta(n) BF access complexity for a lookup, our MPC is geared to have the complexity which is probabilistically far less than Theta(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 .
Year
DOI
Venue
2008
10.1109/GLOCOM.2008.ECP.449
GLOBECOM
Keywords
Field
DocType
high-speed router,communication complexity,flow identification,throughput-efficient packet classifier,memory efficiency,bloom filters,filters,filtering theory,telecommunication network routing,access complexity,multitiered packet classifier,table lookup,bloom filter,memory management,throughput,high throughput,binary trees,best effort
Bloom filter,Computer science,Network packet,Binary tree,Computer network,Communication complexity,Memory management,Throughput,Router,Classifier (linguistics)
Conference
ISSN
ISBN
Citations 
1930-529X
978-1-4244-2324-8
0
PageRank 
References 
Authors
0.34
12
2
Name
Order
Citations
PageRank
Heeyeol Yu1646.09
Rabi N. Mahapatra246344.06