K-Stage Pipelined Bloom Filter for Packet Classification
Mahmood Ahmadi, Stephan Wong · 2009
A Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. In recent years, Bloom filters have increased in popularity in database and networking applications. In this paper, we introduce a k-stage pipelined Bloom filter architecture to decrease power consumption. In the bit-array of a Bloom filter, bits corresponding to the index pointed to by hashing functions are checked and a "match"/"mismatch" is determined. The match/mismatch determination process can be organized in a k-stage pipelined Bloom filter architecture. We present a k-stage pipelined Bloom filter, the power consumption analysis and utilize a software packet classifier to customize the k-stage pipelined Bloom filter architecture in packet classification. The results of the software packet classifier with real packet traces show that more than 75% of mismatched packets can be detected by the first three stages of the pipelined Bloom filter architecture (the remaining 25% comprises 17% matched and 8% mismatched packets). Therefore, a 4-stage pipelined Bloom filter architecture with one hashing function in the first three stages and k - 3 parallel hashing functions in the last stage is more appropriate for power consumption optimization in packet classification.