Research On The Fast Routing Algorithm With Its Realization On FPGA

With the proceeding of the realization by IP networks in modern communication system, the IP lookup algorithm is used widely. With the development of fiber technology, the bit rate can get to 20Gbps. Based on those, route technology turns into the bottleneck in communication system. It is important to find a routing algorithm with high performance and low cost, which can be used widely.The thesis researches on a routing algorithm with high performance and low cost. Based on the four branches parallel route algorithm, a two-branch parallel 16-8-8 route algorithm is realized in the thesis, each branch being processed in pipeline. There are 3 tables, the prefixes less than 16 being expanded to 16, are stored in table 1. Those less than 24 being expanded to 24, are stored in table 1 and table 2. The prefixes more than 24 are stored in special units. The algorithm transforms the two-dimension lookup table into one-dimension table. It needs no more than 3 times to access the register to get the next routing information. The algorithm is simulated by Verilog language. In order to reduce cost, the algorithm is realized on FPGA and SSRAM.Based on the results of functional simulation, the algorithm can support up to 20Gbps bit rate.