最长前缀匹配查找的索引分离trie树结构及其算法
A Data Structure and Algorithm of Indexes and Split Multibit Trie for Longest Matching Prefix Lookup作者机构：西安交通大学电信学院
出 版 物：《计算机工程与应用》 (Computer Engineering and Applications)
年 卷 期：2005年第41卷第20期
页 面：131-134页
核心收录：
学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）]
主 题：最长前缀匹配 索引表 trie树 快速查找 快速更新
摘 要：Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。索引分离trie树结构建立了具有k比特的一级索引,m比特的二级索引和步宽为s、最大深度为m/s的多分支trie树结构。在这种数据结构中进行最长前缀匹配查找的算法复杂度为:O(m/s+2)。它具有算法简单、查找速度快、易于更新、便于向IPv6过渡等特点,是一种综合性能较好的快速最长前缀匹配查找算法。
维普期刊数据库
同方期刊数据库