Abstract
Bloom filter is widely used in network packet processing due to its fast lookup speed and small memory cost. However, the non-negligible false positive rate and the difficulty of online update still prevent it from extensive utilization. In this paper, we propose a cache-based counting Bloom filter architecture, C 2BF, which is not only easy to update online but also benefical for fast verification for precise matching. We also present a high speed hardware C 2BF architecture with off-chip memory and fast cache replacement method. This paper includes three contributions: 1) compressed CBF implementation and its updating algorithm; 2) pattern grouping for higher cache hit rate; 3) onchip cache organization and replacement policy. Experiments show that our prototype of C 2BF reduces more than 70% of the verification processing time with cache design compared with traditional schemes without cache.
Original language | English |
---|---|
Pages (from-to) | 3747-3754 |
Number of pages | 8 |
Journal | Procedia Engineering |
Volume | 29 |
DOIs | |
Publication status | Published - 2012 |
Event | 2012 International Workshop on Information and Electronics Engineering, IWIEE 2012 - Harbin, China Duration: 10 Mar 2012 → 11 Mar 2012 |
Keywords
- Cache
- Counting Bloom filter
- Precise matching