TSB:一种多阶段IPv6路由表查找算法

摘要

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