|
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 C2BF reduces
more than 70% of the verification processing time with cache design
compared with traditional schemes without cache.
|
