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

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

作　　者：李振强[1] 郑东去[2] 马严[1] 

机构地区：[1]北京邮电大学计算机科学与技术学院,北京100876 [2]北京邮电大学信息网络中心,北京100876

出　　处：《电子学报》2007年第10期1859-1864,共6页Acta Electronica Sinica

摘　　要：充分分析IPv6地址结构I、Pv6地址分配策略和IPv6骨干网路由表的特点后,将二叉树、段表和路由桶技术相结合,提出一种多阶段IPv6路由表查找算法.和已有算法相比,提出的算法查找速度快、占用内存少、扩展性好、支持增量更新.实验结果表明算法的软件参考实现在装有P4 2.4GHz CPU,512M DDR333内存和Linux操作系统的普通PC机上的查找能力可以到达16MPPS(Million Packet per Second),这可以满足10Gbps 80字节IPv6最小包的线速转发.对于当前IPv6骨干网BGP路由表,算法的参考实现只占用几百K字节的内存.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 Lmux operating system. The sample implementation only needs several hundreds of kilobytes memory for the current real live IPv6 backbone BGP routing tables.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]