# Vectored-Bloom Filter for IP Address Lookup: Algorithm and Hardware Architectures
## 4 Hardware Architecture
### Basic IP Address Lookup Module  
Figure 2 shows the block diagram of our proposed IP address lookup module in its basic form. The basic IP address lookup module contains a hash index generator, a VBF search block and a hash table search block. The hash index generator is realized with a 64-bit cyclic redundancy check (CRC-64) generator. The CRC-64 is implemented with a shift register and few exclusive-OR gates, which is much simpler than MD5 and SHA-256 and hence the CRC-64 is used in our implementation.  
Figure 3 shows the state machine representing the IP address lookup procedure in detail. When the reset signal is given at state **Start**, the state machine is ready to accept an input address. When an IP address is given to the module, the lookup procedure starts from the longest prefix length and iterates by decreasing the length until a matching prefix is found.At state **CRC Gen**, for a substring of the input IP address, the CRC code is first obtained when the corresponding number of input bits are serially entered into the CRC generator starting from the most significant bit. Multiple hash indexes are obtained by combining multiple bits in the CRC code. In our implementation, to obtain the CRC code within a single cycle, the operations required in the 64-bit CRC generator are implemented in parallel.  
Figure 3: State machine for Internet Protocol (IP) address lookup procedure.  
Figure 2: Block diagram of _Basic IP Address Lookup Module_: the bold lines represent data paths and the dotted line represents a control path.  
The vectors of the VBF pointed by hash indexes are bitwise-ANDed to obtain a result vector at state **Query VBF**. The vector can produce three different results: _negative_, _positive_ or _indeterminable_. The negative result means no matching output port at the current length; the search procedure goes on to state **No match** and then continues to query the VBF with a shorter length. The positive result means a matching output port from the VBF and hence the search is completed for the current input; in this case, the search procedure goes to state **Input ready** for the next input. The indeterminable result means that an output port cannot be returned from the VBF and hence the search procedure needs to proceed to the hash table.  
At State **1 st HT entry**, the hash entry pointed by the first hash index is accessed. If the entry does not have a matching prefix, another entry pointed by the second hash index is accessed at state **2 nd HT entry**. If the entry pointed by the second hash index does not have a matching prefix, the other entry pointed by the linked list of the second entry is accessed at state **Linked list**. If the output port is not found in any of these hash entries, the matching prefix does not exist in the current length and the search procedure goes back to state **No match** and continues to query the VBF with a shorter length. If a matching prefix is found from any of these entries, the search is completed for the current input and hence the search procedure goes to state **Input ready** for the next input.  
In terms of time complexity, since the query for the vectored-Bloom filter performs the linear search on the number of bits in an IP address, the on-chip search performance is \(O(W)\), where \(W\) is the length of the IP address. However, the off-chip hash table access which mainly determines the IP address lookup performance does not occur for a sufficiently large VBF.