| 基于分段地址结构的快速路由查找算法 |
| |
| 引用本文： | 华泽,班建民,陆悠.基于分段地址结构的快速路由查找算法[J].计算机与数字工程,2009,37(10):8-11. |
| |
| 作者姓名： | 华泽 班建民 陆悠 |
| |
| 作者单位： | 苏州科技学院电子与信息工程学院,苏州,215011 |
| |
| 基金项目： | 苏州科技学院基金项目 |
| |
| 摘 要： | 根据IPV6地址结构和骨干路由表特点,分析了原有路由查找算法,基于IPV6的掩码长度和分段地址,采用Hash表和多分支Trie树结构,提出了一种快速的IPV6路由查找算法。根据分段地址和掩码将最常用到的路由前缀按前缀长度设置Hash表,并将前缀值有序存放在表结点中。不仅可以进行前缀长度的二分查找,同时又是其它前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。实践证明该算法具有较好的时空效率,可以较好地提高路由查找速度。
|
| 关 键 词： | 路由查找 长前缀匹配 Hash表 Trie树 掩码 |
A New Rapid IP Lookups Algothrims for IPV6 |
| |
| Hua Ze,Ban Jianmin,Lu You.A New Rapid IP Lookups Algothrims for IPV6[J].Computer and Digital Engineering,2009,37(10):8-11. |
| |
| Authors: | Hua Ze Ban Jianmin Lu You |
| |
| Affiliation: | Hua Ze Ban Jianmin Lu You(College of Electronics and Information Engineering,Suzhou University of Science and Technology,Suzhou 215011) |
| |
| Abstract: | IP lookup algorithms and the characters of IPV6 bone route table has been analysed.Based on mask and segment address,a new IPV6 lookup algorithm has been provided.It uses Hash table and multi-tries,play the frequency prefix in Hash table by order of their value,not only can make bin-search,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. |
| |
| Keywords: | ip lookups best prefix matching Hash table Trie mask |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
