Improving Bloom Filter Forwarding Architectures

To improve Bloom filter-based packet forwarding architectures, we introduce one additional Bloom filter that stores the correct next hop information for recent false positives so as to handle subsequent false positives. Through Click-based experiments, we show that the additional Bloom filter reduces the average table lookup time (i.e., from 120 ns to 93 ns) by handling most false positives within the fast memory.

I. Introduction

IN a packet forwarding architecture, efficient use of a fast memory (e.g., on-chip SRAM) is important because the memory access is one of the main performance bottlenecks. In this regard, Bloom filter is considered as one attractive way for improving the packet forwarding because of its space efficiency. For example, the routing table can be transformed into Bloom filters so that whole or partial routing table can be kept in the fast memory [2], [3].