最长前缀匹配查找的索引分离trie树结构及其算法

• 作者: 冯博琴 崔尚森
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 最长前缀匹配 索引表 trie树 快速查找 快速更新
• 年，卷（期）: 2005,（20）
• 所属期刊栏目: 网络、通信与安全
• 页码范围: 131-134
• 页数: 4页
• 分类号: TP301.6
• 字数: 4984字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2005.20.039

摘要

Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法.索引分离trie树结构建立了具有k比特的一级索引,m比特的二级索引和步宽为s、最大深度为m/s的多分支trie树结构.在这种数据结构中进行最长前缀匹配查找的算法复杂度为:O(m/s+2).它具有算法简单、查找速度快、易于更新、便于向IPv6过渡等特点,是一种综合性能较好的快速最长前缀匹配查找算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	崔尚森	西安交通大学电信学院	16	171	8.0	13.0
3	冯博琴	西安交通大学电信学院	171	3268	30.0	50.0