| 散列索引多分支Trie树快速路由查找算法 |
| |
| 引用本文： | 崔尚森,冯博琴.散列索引多分支Trie树快速路由查找算法[J].计算机应用与软件,2005,22(9):115-117. |
| |
| 作者姓名： | 崔尚森 冯博琴 |
| |
| 作者单位： | 1. 西安交通大学电信学院,陕西,西安,710049;长安大学信息工程学院,陕西,西安,710064
2. 西安交通大学电信学院,陕西,西安,710049 |
| |
| 摘 要： | 路由器的主要任务是转发IP分组，实现高速分组转发的关键是快速的路由查找算法。我们针对IPv4地址，首先建立前缀长度为8、16和24的3张hash表，在此基础上，再分别针对不同长度的前缀建立最多只涉及其余8比特的多分支Trie树。在这种结构中进行IP路由查找，其存储器访问次数最多为7次，而且还具有易于更新、易于扩展等特点。
|
| 关 键 词： | 最长前缀匹配 路由查找算法 散列表 多分支Trie树 快速路由查找算法 Trie树 索引 散列 IPv4地址 IP分组 |
| 收稿时间： | 2004-12-06 |
| 修稿时间： | 2004-12-06 |
A FAST IP ROUTING LOOKUP ALGORITHM BASED ON HASH INDEXED MULTIBIT-TRIE |
| |
| Cui Shangsen,Feng Boqin.A FAST IP ROUTING LOOKUP ALGORITHM BASED ON HASH INDEXED MULTIBIT-TRIE[J].Computer Applications and Software,2005,22(9):115-117. |
| |
| Authors: | Cui Shangsen Feng Boqin |
| |
| Abstract: | The main task of a router is to forward the IP packet. The key to realize the high speed IP packet forwarding is the lookup algorithm. We buildup three hash tables of the prefix length belongs to 8,16 and 24 first,and then build up multibit-trie which deals with rest 8 bits. To lookup the IP routing in this data structures has at the worst seven times memory access,it also give facility for updating and expansive. |
| |
| Keywords: | Longest matching prefix Routing lookup algorithm Hash Multibit-trie |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
