IP Address Lookup Algorithm Using Cross-Checking Bloom Filters

Binary search on trie levels is known to be the most efficient IP address lookup algorithm among trie-based algorithms. Recently, a new algorithm that adds a Bloom filter to the binary search on trie levels is proposed. The Bloom filter avoids an unnecessary access to a hash table in case that there is no node in the corresponding level of the trie. This paper proposes a new IP address lookup algorithm that additionally adds cross-checking Bloom filters to the existing algorithm. Compared with the existing single Bloom filter algorithm, the proposed algorithm provides improved search performance by reducing the false positive rate of the Bloom filter. It is shown that an IP address lookup is performed by 2-3 accesses to external memory in average in our proposed scheme.