Research And FPGA Implementation Of IP Lookup Algorithm

Recently, internet is popular in people's life and more and more machines are connected to the internet. On the other hand, the new media service based on the internet emerged.So the internet capability becomes the rare recource. In order to adapt the rapid improvement of internet application and provide more effective service quality,the network capability must be improved. With the improvement of fiber technology and G-bit switch technology, the network bandwidth and router throughput have been effictive resolved. But the router's transmit efficiency becomes the bottleneck to limit the development of network. The transmit package of router includes these process: package head assemble,update TTL field, caculate and update CRC field , classify the package and put the package into the appropriate queue and so on. However, the search next hop according to package's destination address in the transmit process is the most time-consuming. So, how to implement the high speed router lookup is the key to implement high speed transmit package.In this thesis, based on the IP address lookup algorithms, their implementing paths and their relative technologies are developed in these fields. The RAM and TCAM are adopted to store IP lookup items. Then the Tree Bitmap structure is implemented in our design with xc2v1000 device of Xilinx VirtexII series.Several aspects are included in the thesis:1. After implementing the IP lookup algorithms in software and hardware, its complexity in space and time domain are analyzed and compared.2. According to the prefix length distribution, especially the prefix longer than 24 have grown fastly in recently year. So the prifix which the length longer than 23 are puted into TCAM ,and the others are stored in the RAM with the Tree Bitmap structure,then the ip lookup can be searched in the RAM and TCAM.3. The Internal Prefix and Extending Path item are synchronized dealed with in our design, when the prefix are being searched in the RAM.This can prevent algorithm trace back and redure access the RAM times, quicken the speed of search ip lookup.4. The forward engine using the above IP lookup algorithms is implemented, the forward engine realize these functions: receive package,check CRC field,update TTL field and CRC field.5. The Top-Down design methodology is used in our design and all modules are coding in Verilog-HDL. The design has been implementing in xc2v1000...