采用分段哈希方法的IPv6路由查找算法研究  

IPv6 routing lookup algorithm based on hierarchical Hash

作　　者：高莹[1] 王贺明[1] 陈强[1] 

机构地区：[1]郑州大学信息工程学院,河南郑州450001

出　　处：《计算机工程与设计》2010年第22期4790-4793,共4页Computer Engineering and Design

摘　　要：分析了现有IPv4路由表查找算法和IPv6地址的特性以及主干网路由表的前缀分布特点,借鉴LFT哈希表结构简单、查找快速的特点,提出了以32bits为查找路由前缀起点的分段哈希表和多分支Trie树相结合的IPv6路由查找算法。该算法结构简单、查找效率高、易于更新,多数情况下只需一次内存访问就可查找到路由信息,提高了IPv6主干网路由器转发速度,以满足下一代互联网IPv6发展的需求。With the combination of hash table and multibit trie after sufficient and thorough analysis of the now available IPv4 routing algorithm, especially simple and efficient LFT （level forwarding table）, the characteristics of IPv6 address and the prefix particularity of real live IPv6 backbone routing table, a hierarchical hash routing lookup algorithm for IPv6 is proposed which using the 32bits prefix as the lookup starting point to achieve faster search just need one memory access. This proposed scheme uses simple data structure, performs faster and supports update easily, and improve the IPv6 backbone network forwarding speed to meet the development demand for IPv6.

关 键 词：路由查找 哈希表 多分支Trie树 最长前缀匹配 树形结构 

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