高端路由器路由查找算法分析与实现  

ANALYSIS AND IMPLEMENTATION OF ROUTE LOOKUP ALGORITHM IN HIGH-END ROUTER

作　　者：孙红权[1,2] 王新[1,2] 李飞[1,2] 

机构地区：[1]复旦大学软件学院,上海200433 [2]复旦大学计算机科学与工程系,上海200433

出　　处：《计算机应用与软件》2006年第9期19-20,56,共3页Computer Applications and Software

基　　金：八六三计划(2002AA103065);上海市科技发展基金(03510708);上海市智能信息处理重点实验室开放基金(IIPL04004)共同资助

摘　　要：分析了当前普遍使用的AVL+Cache路由查找解决方案的不足,提出将新的查找算法MBitTrie应用于高端路由器设计的构想。通过测试,验证了MBitTrie在路由查找性能上的优越性,以及应用在高端路由器设计中的可行性。In this article we analyze and summarize the drawbacks of the AVL algorithm and conceive to use the new algorithm, M Bit-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.

关 键 词：最长匹配 多比特树 平衡二叉树 缓存 

分 类 号：TP393.4[自动化与计算机技术—计算机应用技术]