A Power and Throughput-Efficient Packet Classifier with n Bloom Filters

Packet processing is a critical operation in a high-speed router, and in order for this router to achieve memory efficient and fast O(1) lookup operations, Bloom filters (BFs) have been widely used as a packet classifier to reduce expensive hash table accesses. However, it has been identified that a parallel packet classifier (PPC), using all n parallel BFs for a lookup, is neither power nor throughput efficient for high-speed routers. In this paper, we propose a multitiered packet classifier (MPC), both to save power and to improve throughput, with the same memory size as that of a PPC. While a PPC with n BFs consumes Θ(n) BF access complexity for a lookup, our MPC is designed to have the complexity which is probabilistically significantly less than Θ(n). Furthermore, by preprocessing a group of lookups in one cycle in an MPC, we assign each lookup to its associated BF at best effort, and consequently, obtain a higher throughput. With the same reason, as in preprocessing, our MPC design reduces a significant amount of power by preventing accesses to noninvolved BFs during a lookup. In simulation for flow identification with NLANR traces, we observed that the MPC throughput is increased by at most 100 percent, compared to a PPC. Additionally, our MPC shows 4.2 times power efficiency over an equivalent PPC, in terms of power saving.