基于Hash和Radix树的路由查找算法研究  

Research on Router Lookup Algorithm Based on Hash and Radix Tree

作　　者：李渊[1] 阮军洲 

机构地区：[1]中国电子科技集团第五十四研究所 [2]解放军75660部队

出　　处：《计算机与网络》2015年第11期42-44,共3页Computer & Network

摘　　要：介绍了路由查找算法的研究背景和技术指标,对比了基于Radix树和Hash的路由查找算法,进而提出了一种基于Hash和Radix树相结合的路由查找算法,详细介绍了该算法的数据结构和实现步骤,同时给出了该算法基于FPGA的硬件实现模型并设计了对该模型的逻辑仿真结构,对逻辑仿真结构中的测试激励产生机制作了介绍。针对逻辑仿真波形进行了分析,结果显示该算法实现了8.6X106次查找/s。This paper introduces the research background and some technical parameters of the route lookup algorithm. Comparmg the router lookup algorthm based on Radix tree with the router lookup algorithm based on Hash, a kind of router lookup algorithm is proposed, which combines together the router lookup algorithms based on Hash and Radix tree. The data structure and implementation steps of this algorithm are presented. The hardware implementation model based on FPGA is given and the structure of logical simulation for this modal is designed. This paper introduces the test excitation generation mechanism. The analysis is performed for logical simulation waveform, and the result shows that this algorithm can realize 8.6X106 routing lookup/s.

关 键 词：Radix树 路由查找 HASH表 逻辑仿真 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]