# Vectored-Bloom Filter for IP Address Lookup: Algorithm and Hardware Architectures
## 5 Behavior Simulation
### Performance of the Proposed Structure  
Table 1 shows the data structures of the VBF and a hash table. Let \(N\) be the number of prefixes in each set. For the _depth_ of the VBF, \(m=\alpha N^{\prime}\), where \(N^{\prime}=2^{\lceil\log_{2}N\rceil}\) and sizing factor \(\alpha=1\), 2 and 4. The _width_ of the VBF is the vector size (\(l\)), which is determined by the number of output ports.  
Figure 5: Parallel architecture employing a single hash table: the bold lines represent data paths and the dotted lines represent control paths.  
The _depth_ of the hash table, \(B=2N^{\prime}\) and the _width_ of the hash table is the size of a hash entry. A single hash entry has four fields. In storing a prefix, 32 bits are allocated assuming IPv4. The prefix length has five bits calculated by \(log_{2}32\). The output port uses three bits calculated by \(log_{2}l\) because the number of output ports \(l\) is assumed to be 8. Since the number of entries in the hash table is \(2\cdot 2^{\lceil log_{2}N\rceil}\), the linked list has \(\lceil log_{2}N\rceil+1\) bits.  
Since the VBF querying procedure starts from the longest length existing in the set and stops when a positive result is returned, the performance is affected by the distribution of the prefix lengths. Figure 6 shows the distribution of prefixes according to their lengths in each set.  
Table 2 shows the on-chip memory requirement (\(M_{b}\)) for a VBF and the off-chip memory requirement (\(M_{h}\)) for a hash table. It is shown that the VBF requires less memory than a hash table even when the sizing factor \(\alpha\) is 4, since each vector of the VBF only represents an output port while the hash entry stores a prefix, a length, an output port and a linked list. The optimal number of hash functions for the VBF (\(k_{v}\)) is shown as well.  
Table 3 shows the _indeterminable rate_ and _false port return rate_ according to the size of the VBF. The _indeterminable rate_ (\(I\)) is defined as the number of inputs causing _indeterminable_ over the number of inputs. Since the output ports for these inputs are not identified by the VBF because of multiple set bits in the resulting vector, the search procedure should perform an access to the hash table. The _false port return rate_ (\(F\)) is defined as the number of inputs having false return over the number of inputs. False ports can be returned by the false positives of the VBF. Note that the _indeterminable rate_ and the _false port return rate_ are zero when the sizing factor of the VBF is larger than two as shown in Table 3.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & \multicolumn{2}{c}{**VBF**} & \multicolumn{2}{c}{**HT**} \\ \hline Depth & No. of vectors (\(m\)) & \(\alpha N^{\prime}\) & No. of entries (\(B\)) & \(2N^{\prime}\) & \\ \hline \multirow{3}{*}{Width (bits)} & \multirow{3}{*}{Vector size (\(l\))} & \multirow{3}{*}{output port} & \multirow{3}{*}{8} & prefix & 32 \\  & & & & length & 5 \\ \cline{1-1}  & & & & & output port & 3 \\ \cline{1-1}  & & & & & linked list & \(\lceil log_{2}N\rceil+1\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Data structures.  
Figure 6: Distribution of the number of prefixes according to prefix lengths.