# Vectored-Bloom Filter for IP Address Lookup: Algorithm and Hardware Architectures
## 3 IP Address Lookup Using a Vectored-Bloom Filter
### Theoretical Analysis on Search Failure Probability  
In this section, we present the theoretical probability of search failure of the proposed VBF. The search failure in the VBF occurs in two cases; _false port return_ and _indeterminable_. The theoreticalprobability of the search failure for the first architecture of the VBF (summarized in the first paragraph of Section 3) has been provided in Reference [21] and this section provides the theoretical search failure probability for the second structure of the VBF. The VBF consists of \(m\) multi-bit vectors and each vector comprised of \(l\) bits contains \(l\) different ports. For \(n\) elements included in programming set \(S\), assuming that the elements are equally distributed to each port, the number of elements in each port set, \(n^{\prime}\), is equal to \(n/l\).  
In querying, while _false positives_ can occur for non-programmed inputs, _indeterminables_ can occur for all inputs including programmed inputs. If the VBF returns a value for a non-programmed input, it is a _false positive_, which means that a single port is returned among \(l\) values. If the VBF returns two or more values, it is an _indeterminable_, which means that more than one port is returned among \(l\) ports in one querying.  
Let \(p\) represent the probability that a specific bit in a vector is set at least once by \(n^{\prime}\) elements, after programming all elements by \(k\) hash functions. If the hash functions are assumed to be perfectly random, \(p\) can be calculated as  
\[p=1-(1-\frac{1}{m})^{kn^{\prime}}. \tag{4}\]  
When querying input \(x\) not included in set \(S\), a _false positive_ can occur if the same bit locations in each of \(k\) vectors are 1 and other bit locations in each of \(k\) vectors are 0. Hence, the _false port return_ probability, \(P(F)\), is as follows.  
\[P(F)=P(S^{c})P(F|S^{c})=P(S^{c})\cdot\Big{(}l\cdot(p^{k})\cdot(1-p^{k})^{l-1} \Big{)} \tag{5}\]  
An _indeterminable_ can occur if there exist more than one port regardless of true or false ports. The _indeterminable_ probability, \(P(I)\), is defined as follows.  
\[P(I)=P(S)P(I|S)+P(S^{c})P(I|S^{c}) \tag{6}\]  
\(P(I|S)\) is the _indeterminable_ probability for the inputs included in \(S\). In case of inputs included in \(S\), since one true port must occur, an _indeterminable_ can occur if the number of false ports is from 1 to \(l-1\) times. Therefore, \(P(I|S)\) is as follows.  
\[P(I|S)=1-(1-p^{k})^{l-1} \tag{7}\]  
\(P(I|S^{c})\) is the _indeterminable_ probability for the inputs not included in \(S\). In case of inputs not included in \(S\), an _indeterminable_ can occur if the number of false ports is from 2 to \(l\) times. Therefore, \(P(I|S^{c})\) is as follows.  
\[P(I|S^{c})=1-(1-p^{k})^{l}-P(F|S^{c}) \tag{8}\]  
From Labels (7) and (8), the _indeterminable_ probability is  
\[P(I) =P(S)\Big{(}1-(1-p^{k})^{l-1}\Big{)}+P(S^{c})\Big{(}1-(1-p^{k})^{ l}-P(F|S^{c})\Big{)}\] \[=P(S)\Big{(}1-(1-p^{k})^{l-1}\Big{)}+P(S^{c})\Big{(}1-(1-p^{k})^{ l}-l\cdot(p^{k})\cdot(1-p^{k})^{l-1}\Big{)} \tag{9}\]  
From Label (4), since \(p\) is the function of the size of the Bloom filter, \(m\), the _false port return_ probability in Label (5) and the _indeterminable_ probability in Label (9) can be controlled by the size of the Bloom filter.