摘要
在分析原有查找算法的基础上,结合IPv6地址结构和骨干路由表特点,提出一种新的快速IPv6路由查找算法。基于Hash表和多分支Trie树结构,将最常用到的路由前缀按前缀长度放置在Hash表中,并按前缀值有序存放在表结点中,不仅可以进行最常用前缀的二分查找,同时又是其他前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。分析及测试证明该算法具有很好的时间效率,更新速度很快。
By analysising IP lookup algorithms, the IPv6 address structure and characters of bone route table, provided a new IPv6 lookup algorithm, which uses Hash table and muhi-tries , plays the frequency prefix in Hash table by order of their value, not only can make binsearch , but also take a index of other prefix. So other prefix can complete it＇s best prefix matching on multi-trie. This algorithm has better time efficiency and space efficiency.
出处
《现代计算机》
2009年第5期54-57,共4页
Modern Computer
基金
苏州科技学院基金项目资助(No.z995)
