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 字节的内存.

TSB:A Multi-Stage Algorithm for IPv6 Routing Table Lookup

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.