| 基于Hash和二叉树的路由表查找算法 |
| |
| 引用本文： | 刘尉悦,王永纲,张万生,王砚方.基于Hash和二叉树的路由表查找算法[J].中国科学技术大学学报,2006,36(3):293-296. |
| |
| 作者姓名： | 刘尉悦 王永纲 张万生 王砚方 |
| |
| 作者单位： | 1. 中国科学技术大学近代物理系快电子学实验室,安徽,合肥,230026;宁波大学信息科学与工程学院,浙江,宁波,315211
2. 中国科学技术大学近代物理系快电子学实验室,安徽,合肥,230026 |
| |
| 基金项目： | 中国科学院留学回国人员择优资助项目 |
| |
| 摘 要： | 提出了一种基于Hash和二叉树的路由表查找算法,这一算法可以满足OC-768的转发要求,支持超过10万条前缀的大规模路由表,并且在路由表更新时,只有少量的存储器需要被改写.仿真结果显示,对于一个149 458条前缀的路由表,算法仅需要2 MB存储器,如果采用200MHz的存储器芯片,平均的查找速度可以达到100M次/秒.
|
| 关 键 词： | 最长前缀匹配 路由表查找 路由表 二叉树 |
| 文章编号： | 0253-2778(2006)03-0293-04 |
| 收稿时间： | 01 18 2005 12:00AM |
| 修稿时间： | 10 11 2005 12:00AM |
IP address lookup algorithm based on Hash and binary-trie |
| |
| LIU Wei-yue,WANG Yong-gang,ZHANG Wan-sheng,WANG Yan-fang.IP address lookup algorithm based on Hash and binary-trie[J].Journal of University of Science and Technology of China,2006,36(3):293-296. |
| |
| Authors: | LIU Wei-yue WANG Yong-gang ZHANG Wan-sheng WANG Yan-fang |
| |
| Institution: | 1. Fast Electronic Lab, Department of Modern Physics, University of Science and Technology of China, Hefei 230026, China; 2. School of Information Science and Engineering, Ningbo University, Ningbo 31522, China |
| |
| Abstract: | An IP address lookup algorithm based on Hash and binary-trie is presented. It is fast enough to support OC-768 links and memory efficient to support large forwarding tables with more than 100k prefixes. Also, the scheme is easy to implement and only a small part of the memory needs to be updated when the routing table is being updated. Simulation results show that only 2 MB memory is required for a routing table with 149 458 prefixes, and with 200 MHz memory chips, average lookup throughput of 100 M/s can be achieved. |
| |
| Keywords: | Hash |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
