Research And Implementation Of The FPGA-based High-speed Routing Lookup Algorithm

With the development of high-speed IP networks, multimedia services have emerged. Therequirement on network speed is increasingly stringent, in which lookup speed of network routershas become a bottleneck. Considering that software-based routing search is difficult to achieve thehigh speed required, hardware-based search technique is of special importance.Following an outline of the technical background and research contents, the dissertationintroduces the existing lookup algorithms, including some typical hardware-based algorithmsTogether with a summary of the pros and cons of each algorithm. Then, a routing lookuphardware structure BstLpmF (Binary Search Tree-Based Longest Prefix Match for Embedded-Fpga) is proposed based on FPGA platform. The use of parallel processing and pipeline hardwaredesign greatly improves the search speed and efficiency. Low power design approach isemployed to reduce the power consumption of the entire structure. A high performance routingupdate message is designed to make the FPGA routing table simple and easy to update with noadverse impact on the normal operation of lookup. Furthermore the design and implementation ofthe FPGA structure is detailed, including individual module coding using Xilinx ISE10.1softwareand system synthesis using Synplify Pro9.6.2software. Finally functional simulation is done withmodelsim software and complehensive simulation cases designed. The simulation results haveshown that the system features designed are correct and a high rate of lookup with the maximumoperating frequency of up to374MLPS is reached, fully meeting the design requirements.