摘要：充分分析IPv6地址结构、IPv6地址分配策略和IPv6骨干网路由表的特点后，将二叉树、段表和路由桶技术相结合，提出一种多阶段IPv6路由表查找算法．和已有算法相比，提出的算法查找速度快、占用内存少、扩展性好、支持增量更新．实验结果表明算法的软件参考实现在装有P42．4GHzCPU，512M DDR333内存和Linux操作系统的普通PC机上的查找能力可以到达16MPPS（Million Packetper Second），这可以满足10Gbps 80字节IPv6最小包的线速转发．对于当前IPv6骨干网BGP路由表，算法的参考实现只占用几百K字节的内存．

关键词：算法 路由查找 ipv6 多阶段 

单位：北京邮电大学计算机科学与技术学院; 北京100876; 北京邮电大学信息网络中心; 北京100876