Abstract: IP address lookup is a key issue in modern high performance muter design, especially with the evolution of IPv6. In order to improve the efficiency of IP address lookup, a novel IPv6 address lookup scheme based on Hash tables and tree bitmaps was proposed, with an analysis on the prefix length distribution of routing table state-of-the-art. In this scheme,four Hash tables were used to store the prefixes with the length of 16，32,48 and 64 bits respectively; the subprefixes with length of 16，32，48 bits of the other prefixes were stored in these four Hash tables too, their remaining part shorter than 16 bits was coded into tree-bitmap and indexed by a certain Hash table entry, thereby to form a two-stage address lookup architecture. I}hc results show that the scheme can achieve an average memory access number of1--2 per IPv6 address lookup and 7 for the worst case, and can be applied in the high performance IPv6 address lookup implementation.

Key words: IPv6 , Routing lookup, Hash table, Tree bitmap