# Vectored-Bloom Filter for IP Address Lookup: Algorithm and Hardware Architectures
## 3 IP Address Lookup Using a Vectored-Bloom Filter  
The basic idea of the proposed vbf architecture for IP address lookup was briefly introduced in References [31] and [32]. The VBF consists of \(m\) multi-bit vectors and each vector comprised of \(l\) bits contains an output port. The proposed structure completes an IP address lookup by querying only the on-chip VBF without accessing the off-chip hash table. Depending on how output ports are programmed to the VBF, two different structures are possible [31]. The first structure involves making the \(l\)-bit vector represent up to \(2^{l}-2\) output ports, zero and a _conflict_ value, which is the value of \(2^{l}-1\). The _conflict_ indicates that the vector is programmed by two or more different output ports.  
In programming a prefix, the \(k\) vectors pointed by the \(k\) hash indexes of the prefix are written with the output port of the prefix. If any of the vectors already have an output port other than the output port, all of the bits in the vector are set to 1 in order to represent the _conflict_ (\(2^{l}-1\)). In querying an input, if all the \(k\) vectors located by the \(k\) hash indexes of the input have the _conflict_ values, the VBF cannot return an output port and the result is termed an _indeterminable_. If any of the \(k\) vectors has 0, the input is not a prefix and hence the result is termed a _negative_. If the vectors other than _conflict_ have the same value, the input is a prefix and the value is the output port of the prefix and hence the result is termed a _positive_.  
The second structure involves making the \(l\)-bit vector represent \(l\) output ports by assigning each bit in a vector an output port. Hence, two or more different output ports can be represented in a vector by setting the corresponding bits and the _conflict_ value is not necessarily defined.  
The motivation of the proposed VBF structure is to complete the IP address lookup by only searching the VBF implemented with an on-chip memory, without accessing a hash table implemented with an off-chip memory. The hash table is infrequently accessed only when the VBF fails to provide the output port. The VBF structure is shown in Figure 1. Assuming that output ports are uniformly distributed, for \(n\) given prefixes, the optimal number of hash functions for the VBF is defined as follows, similarly to Label (1).  
\[k_{v}=\frac{ml}{n}\ln 2 \tag{3}\]  
since a VBF can be considered with \(l\)\(m\)-bit Bloom filters, each of which is programmed by \(n/l\) prefixes.  
In this paper, we describe the second structure in detail including the hardware architecture which was not described in Reference [31]. Hence, Section 4 is completely a new section compared with Reference [31]. In Reference [32], even though the hardware architecture of the VBF implemented on the FPGA is briefly described, the proposed structure has not been evaluated through a behavior simulation and not been compared with other algorithms. In this paper, we describe our algorithm and the proposed hardware structures in detail and the proposed architecture has been evaluated through both a behavior simulation with C language and a timing simulation with Verilog. In addition, we compare our algorithm with other algorithms with a large scale. Hence. the Section 5 is completely a new section and Section 6 is largely extended compared with Reference [32].  
Figure 1: Overall structure of vectored Bloom filter (VBF) algorithm.