基于非重叠前缀集合的并行路由查找系统

• 作者: 吴建平 徐恪 柴云鹏 梁志勇
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 最长前缀匹配 二分查找 路由查找 路由更新
• 年，卷（期）: 2004,（8）
• 所属期刊栏目: 学术论文
• 页码范围: 1277-1281
• 页数: 5页
• 分类号: TP393
• 字数: 6185字
• 语种: 中文
• DOI: 10.3321/j.issn:0372-2112.2004.08.012

摘要

快速的路由查找机制是高性能路由器设计的关键.最长匹配查找是路由查找的难点所在.本文提出一个并行路由查找系统.它使用一种路由表划分方法,可将路由表中的前缀划分为若干个集合,集合内前缀没有重叠.从而把路由表前缀的最长匹配查找转化为若干个集合内前缀的唯一匹配查找.基于这种方法,本文还提出一个通用的并行路由查找框架,框架适用于大多数路由查找算法.并行查找框架可简化查找算法的设计,提高查找算法的速度.使用二分查找算法,并行查找系统可以达到log2(2N/B)的查找复杂度 (N为路由表前缀数目,B为大于4的整数).同时,并行查找系统对IPv6也具有很好的扩展性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐恪	清华大学计算机科学与技术系	154	2232	24.0	42.0
2	吴建平	清华大学计算机科学与技术系	298	5155	36.0	63.0
3	柴云鹏	清华大学计算机科学与技术系	5	19	2.0	4.0
4	梁志勇	清华大学计算机科学与技术系	4	47	4.0	4.0