| Title |
IP Address Lookup Algorithm Using a Vectored Bloom Filter |
| Authors |
변하영(Byun, Hayoung) ; 임혜숙(Lim, Hyesook) |
| DOI |
https://doi.org/10.5370/KIEE.2016.65.12.2061 |
| Keywords |
Bloom filter ; IP address lookup ; Vectored bloom filter |
| Abstract |
A Bloom filter is a space-efficient data structure popularly applied in many network algorithms. This paper proposes a vectored Bloom filter to provide a high-speed Internet protocol (IP) address lookup. While each hash index for a Bloom filter indicates one bit, which is used to identify the membership of the input, each index of the proposed vectored Bloom filter indicates a vector which is used to represent the membership and the output port for the input. Hence the proposed Bloom filter can complete the IP address lookup without accessing an off-chip hash table for most cases. Simulation results show that with a reasonable sized Bloom filter that can be stored using an on-chip memory, an IP address lookup can be performed with less than 0.0003 off-chip accesses on average in our proposed architecture. |