Name
Abstract | ||
|---|---|---|
Packet processing is a critical operation in a high-speed router, and in order for this router to achieve memory efficient and fast {\cal 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 \Theta (n) BF access complexity for a lookup, our MPC is designed to have the complexity which is probabilistically significantly less than \Theta (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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/TC.2010.213 | IEEE Trans. Computers |
Keywords | Field | DocType |
mpc design,lookup operation,equivalent ppc,higher throughput,mpc throughput,throughput-efficient packet classifier,n bfs consumes,power saving,mpc shows,times power efficiency,n bloom filters,multitiered packet classifier,bloom filter,pipelines,indexing terms,best effort,sram,memory management,throughput,hash table,power efficiency | Bloom filter,Computer science,Parallel computing,Network packet,Real-time computing,Static random-access memory,Packet processing,Memory management,Throughput,Router,Hash table | Journal |
Volume | Issue | ISSN |
60 | 8 | 0018-9340 |
Citations | PageRank | References |
6 | 0.49 | 23 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Heeyeol Yu | 1 | 64 | 6.09 |
| Rabi Mahapatra | 2 | 209 | 19.92 |