# A New Bloom Filter Architecture
## 2 Related Works
### FIB Lookup Algorithms Applying Bloom Filters  
The NPT-BF algorithm [9] has a Bloom filter applied in order to improve the search performance of the NPT. In this algorithm, the NPT is assumed to be stored in an off-chip memory because of its size while an on-chip Bloom filter is used to reduce the number of off-chip memory accesses. Every node of the NPT is programmed in a Bloom filter. Prior to accessing the NPT stored in an off-chip memory for an input, the Bloom filter is examined for each substring of the input in order to identify the existence of the substring. If the Bloom filter produces a positive result for a substring of some input, the off-chip NPT is accessed, and the search procedure remembers the output face stored with a matching name prefix (if one exists), then the search procedure continues on the next substring. If the Bloom filter produces a _negative_ result, the search procedure finishes without accessing the off-chip NPT, since the Bloom filter can never produce false negatives and no matching prefix longer than the current longest matching name prefix is guaranteed in the NPT. Hence, the NPT-BF reduces the number of off-chip accesses by avoiding unnecessary off-chip access when the Bloom filter produces a _negative_ result.  
While the NPT-BF accesses the off-chip NPT for every positive result of the Bloom filter, the NPT-BF-chaining [9] accesses the off-chip NPT for the longest positive result. In other words, the NPT-BF-chaining continuously performs Bloom filter queries without needing to access the off-chip NPT until a negative result is produced. The off-chip NPT is accessed for the last positive result, which may be the longest name prefix matching the substring of the input. If a matching name prefix is found with an output face (assuming that the matching output face is pre-computed to each empty node), the search procedure finishes and returns the output face. If no matching name prefix exists because of a Bloom filter false positive, back-tracking will occur.  
However, in these algorithms, every node, including empty nodes, should be programmed into the Bloom filter, and the search performance is directly affected by the NPT depth since the Bloom filter is sequentially accessed from the shortest level to the longest level in the same way as the search in the NPT. Moreover, the search procedure cannot be completed only through Bloom filter accesses because the Bloom filter does not provide a return value.  
The I(FIB)F structure [12] uses iterated Bloom filters, and can complete the search procedure without accessing the off-chip memory since an I(FIB)F is constructed for each output face, as opposed to a single FIB that defines the next-hop. An I(FIB)F consists of \(d\) iterated Bloom filters (IBF) [29] with iterated hash functions. In order to construct an I(FIB)F, a \(m\)-bit standard BF is split in \(d\) IBFs of \(m/d\) bits. IBFs benefit from the properties of iterative trees, such as NPTs. In the search procedure, when an Interest packet arrives through a face, the I(FIB)Fs of all faces except for the incoming face are checked, and then the face with the largest match is selected for forwarding. Since the I(FIB)F structure considers a flat naming scheme, while, in this paper, we consider a structured naming scheme using name prefixes, the I(FIB)F is not directly compared with our proposed algorithm.