Internet migration from IPv4 to IPv6 has introduced more challenge to IP address lookup problem. Nowadays, some existing address lookup algorithms work well for IPv4 addresses, however, few of them can scale well to IPv6 both in lookup and update speed. As IPv6 uses 128-bit addresses, schemes whose lookup time grows with address length become less attractive. In this paper, a novel level based IPv6 routing lookup algorithm, called level-based routing lookup (LRL) algorithm, is proposed. This proposed algorithm is specially designed based on the extensive research on the characteristics of IPv6 prefix length distribution, which is composed of four levels. Different structures are used for different levels. Intensive experiments have been done to evaluate the algorithm. The results show that the new algorithm excels in following aspects: good support of IPv6, extremely excellent fast lookup speed, stable memory consumption and competitive update speed.

Next generation internet protocol, IPv6, has attracted growing attention and has been deploying worldwide. With 128-bit address, IPv6 provides an extremely large address space and poses a great challenge to the routing table lookup algorithms. Today's efficient IPv4 routing table lookup schemes can hardly be competent for IPv6. In this paper, we propose a multi-stage IPv6 routing table lookup algorithm based on a sufficient study on the characteristics of the IPv6 address structure, the IPv6 address allocation policies, and the real world IPv6 backbone BGP routing tables. The proposed algorithm combines the binary tree, the segment table, and the route bucket other than adopting single technique as previous schemes do. Compared with previous algorithms, the proposed algorithm performs faster, occupies less memory, scales better, and supports incremental update.