| 一种基于哈希表和Trie树的快速IP路由查找算法 |
| |
| 引用本文： | 崔尚森,张白一.一种基于哈希表和Trie树的快速IP路由查找算法[J].计算机工程与应用,2005,41(9):156-158. |
| |
| 作者姓名： | 崔尚森 张白一 |
| |
| 作者单位： | 西安交通大学电信学院,西安,710049;长安大学信息工程学院,西安,710064;长安大学信息工程学院,西安,710064 |
| |
| 摘 要： | Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。论文提出了一种基于8比特的前向查找表(LFT)和7比特的简单二进制回退查找Trie树(HBT)的IP路由查找算法。算法综合考虑了IP地址的分布特点,兼顾了查找速度、存储空间利用、硬件实现,以及向IPv6过渡等几个因素。具有算法简单、查找速度较快、存储空间利用率较高、易于扩展和便于硬件实现等特点。
|
| 关 键 词： | 路由查找 最长前缀匹配 哈希 Trie树 |
| 文章编号： | 1002-8331-(2005)09-0156-03 |
A Fast Routing Lookup Algorithm Based on Hash and Trie |
| |
| Cui Shangsen,Zhang Baiyi.A Fast Routing Lookup Algorithm Based on Hash and Trie[J].Computer Engineering and Applications,2005,41(9):156-158. |
| |
| Authors: | Cui Shangsen Zhang Baiyi |
| |
| Affiliation: | Cui Shangsen1,2 Zhang Baiyi21 |
| |
| Abstract: | With rapid development of Internet,it orders the core router to be able to forward ten millions of packets per second.High speed IP address lookup algorithm is the key component of high speed packet forwarding.This paper proposes a new scheme witch based on 8-bit level fronted lookup table(LFT)and 7-bit backward searching Trie(HBT).It considers the distributions of IP address and the transition towards IPv6,it's algorithm is simple,lookup speed is quick,and requiring a small number of memory,expand easy,and convenient for implementing with hardware. |
| |
| Keywords: | route lookup longest matching prefix Hash Trie-tree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
