四-二分搜索高性能IPv4路由查找算法与实现

• 作者: 孙亚民 张彦肖 王振兴 邬江兴
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: IPv4路由查找 四-二分搜索 快速更新 查表连续性 TCAM流水处理
• 年，卷（期）: 2005,（8）
• 所属期刊栏目: 基金项目论文
• 页码范围: 26-28,110
• 页数: 4页
• 分类号: TP393.03
• 字数: 4302字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2005.08.011

摘要

传统二分算法完成一次IPv4最长前缀匹配需5步搜索,且因存在回溯问题难以硬件实现,而单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列,影响表项的更新速度和路由查找流程的连续性.该文提出并以TCAM流水线硬件实现了一种独特的对前缀范围的四-二分搜索算法.仅用3步搜索完成一次IPv4路由查找、转发表不需排序、查找速率高、表项更新快、查表连续性好.满足了IPv4核心路由器的双OC-768(40Gbps)端口、48B包的线速转发.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张彦肖	信息工程大学信息工程学院	9	11	2.0	3.0
2	邬江兴		93	559	12.0	19.0
3	王振兴	信息工程大学信息工程学院	21	113	5.0	10.0
6	孙亚民	南京理工大学计算机系	117	1149	19.0	28.0