| 高端路由器路由查找算法分析与实现 |
| |
| 引用本文： | 孙红权,王新,李飞. 高端路由器路由查找算法分析与实现[J]. 计算机应用与软件, 2006, 23(9): 19-20,56 |
| |
| 作者姓名： | 孙红权 王新 李飞 |
| |
| 作者单位： | 复旦大学软件学院,上海,200433;复旦大学计算机科学与工程系,上海,200433 |
| |
| 基金项目： | 国家高技术研究发展计划(863计划);上海市科技发展基金;上海市重点实验室基金 |
| |
| 摘 要： | 分析了当前普遍使用的AVL＋Cache路由查找解决方案的不足，提出将新的查找算法MBit-Trie应用于高端路由器设计的构想。通过测试，验证了MBit-Trie在路由查找性能上的优越性，以及应用在高端路由器设计中的可行性。
|
| 关 键 词： | 最长匹配 多比特树 平衡二叉树 缓存 |
| 收稿时间： | 2005-07-15 |
| 修稿时间： | 2005-07-15 |
ANALYSIS AND IMPLEMENTATION OF ROUTE LOOKUP ALGORITHM IN HIGH-END ROUTER |
| |
| Sun Hongquan,Wang Xin,Li Fei. ANALYSIS AND IMPLEMENTATION OF ROUTE LOOKUP ALGORITHM IN HIGH-END ROUTER[J]. Computer Applications and Software, 2006, 23(9): 19-20,56 |
| |
| Authors: | Sun Hongquan Wang Xin Li Fei |
| |
| Affiliation: | Software School, Fudan University, Shanghai 200433, China;Department of Computer Science and Engineering, Fudan University, Shanghai 200433, China |
| |
| Abstract: | In this article we analyze and summarize the drawbacks of the AVL algorithm and conceive to use the new algorithm,MBit-Trie to replace it in the design of high-end router.On the basis of the design and implementation of the new algorithm,the real test result validates that the MBit-Trie has much higher performance than the AVL and it is feasible in high-end router's design. |
| |
| Keywords: | Best/Longest prefix matching Multi bit trie(MBit-Trie) AVL tree Cache |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
