With the combination of binary tree

segment table and route bucket after sufficient and thorough analysis of the hierarchy of IPv6 address

IPv6 address allocation policy and the characteristics of real live IPv6 backbone BGP routing tables

we propose a multi-stage algorithm for IPv6 routing table lookup in this paper.Compared with previous algorithms

the proposed scheme performs faster

occupies less memory

scales better

and supports incremental update.The evaluation results show that the sample software implementation of the proposed algorithm can forward at a rate of 16MPPS (Million Packet per Second)

or 10Gbps for 80-byte minimal IPv6 packets on a PC with Pentium4 2.4GHz CPU

512M DDR333 memory

and Linux operating system.The sample implementation only needs several hundreds of kilobytes memory for the current real live IPv6 backbone BGP routing tables.