# Vectored-Bloom Filter for IP Address Lookup: Algorithm and Hardware Architectures
## 6 Hardware Implementation
\begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline
**Routing** & **Input Set (\#. of blks)** & **VBF (\#. of blks)** & **Total VBFs (\#. of blks)** & **HT (\#. of blks)** & **Total BRAMs** \\ \cline{2-11}
**Set** & **18-Kbits** & **36-Kbits** & **18-Kbits** & **36-Kbits** & **18-Kbits** & **36-Kbits** & **18-Kbits** & **36-Kbits** & **(KBytes)** & **(\%)** \\ \hline
1000 & 0 & 3 & 1 & 0 & 12 & 0 & 0 & 3 & 54 & 2.7 \\
5000 & 4 & 12 & 0 & 4 & 0 & 48 & 0 & 24 & 387 & 19.3 \\
14,553 & 7 & 36 & 0 & 8 & 0 & 96 & 0 & 49 & 830 & 41.5 \\
30,000 & 0 & 80 & 0 & 16 & 0 & 192 & 0 & 102 & 1683 & 84.0 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Memory requirement in hardware. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline
**Resource** & **Capacity** & \multicolumn{3}{c}{**1 k**} & \multicolumn{3}{c}{**5 k**} & \multicolumn{3}{c}{**14 k**} & \multicolumn{3}{c}{**30 k**} \\ \cline{3-9}  & & **Used** & **Utilization (\%)** & **Used** & **Utilization (\%)** & **Used** & **Utilization (\%)** & **Used** & **Utilization (\%)** \\ \hline LUT & 203,800 & 5560 & 2.7 & 6440 & 3.2 & 6995 & 3.4 & 7419 & 3.6 \\ FF & 407,600 & 2824 & 0.7 & 3029 & 0.7 & 3084 & 0.8 & 3087 & 0.8 \\ BRAM & 445 & 12 & 2.7 & 86 & 19.3 & 184.5 & 41.5 & 374 & 84.0 \\ IO & 400 & 6 & 1.5 & 6 & 1.5 & 6 & 1.5 & 6 & 1.5 \\ BUFG & 32 & 3 & 9.4 & 3 & 9.4 & 3 & 9.4 & 3 & 9.4 \\ \hline \hline \end{tabular}
\end{table} 
Table 9: Resource utilization. Figure 9 shows the average number of cycles needed to perform an IP address lookup and the throughput of our implementation. The average number of cycles is related to the search performance and the search performance is affected by the prefix length distribution shown in Figure 6. The throughput is the maximum number of processed packets per second (p/s or pps) and it is inversely related to the average number of cycles. The best-case of the throughput is 4.92 million packets/sec for the 1 k set, while the worst-case of the throughput is 3.32 million packets/sec for the 5 k set, because the 5 k set has more short-length prefixes than other sets as shown in Figure 6. Note that the throughput performance depends more on the prefix length distribution rather than the number of prefixes. The prefix length distribution is related to the role of routers, whether the router is a backbone router or an edge router. Backbone routers have the more number of short-length prefixes than edge routers, since edge routers connect mostly access networks, which has a more specific (longer-length) prefix. Considering that the number of prefixes is scaled to several hundred thousands reflecting real backbone routing tables, if the proposed architecture is implemented with an ASIC, which has at least 4 Mbytes on-chip memory operating at 500 MHz [6], the expected throughput can be improved by 5 times. The proposed architecture can provide the wire-speed IP address lookup at the rate of about 15 to 25 million packets/sec, since the routing sets used in our simulation has the similar characteristics as actual routing sets by being downloaded (and randomly selected) from real backbone routers.