A Dynamic Binary Hash Scheme for IPv6 Lookup

Recently, the significantly increased IPv6 address length has posed a greater challenge on wire-speed router for IP lookup. As a result, even the most efficient IPv4 lookup scheme can not meet the demand in IPv6. In this paper, we make a thorough observation on the characteristic of IPv4/IPv6 routing table and propose a novel division technique for routing table, with which the traditional LPM (longest prefix matching) problem can be changed to an exact matching one for majority prefixes. Based on this technique, we propose a DBH (dynamic binary hash) scheme for dynamic IPv6 routing lookup, which achieves O(log W) (W stands for the address length) lookup performance. Key feature of the new scheme is its ability to have a performance guarantee of 7 hash probes in the worst cast of IPv6 routing lookup, meanwhile it can support incremental update. This makes it more attractive in reality. The performance evaluation has shown that the newly proposed scheme can achieve an average lookup memory access number of 2.7 for current IPv6 lookup. It is below 35% of best existing dynamic algorithm. Besides, the memory cost by the data structure itself is extremely small and the average update memory access number is very few.