Fast Routing Lookup Algorithms Based On Multi-bit Trie

With the continuous development of the Internet, IP routing lookup has become one of the main reasons why performance of core routers in the Internet becomes the bottleneck. Reducing the memory access times is an effective way to improve lookup speed. This paper uses four-step parallel pipelines to search the longest prefix matching. This scheme can finish the lookup within one memory access time.This paper introduces some existing algorithms, and then gives an algorithm for IP routing lookup which bases on multi-bit trie and prefix expansion technology, and suits to implement by FPGA. The algorithm uses four-table architecture, and divides the search into four levels. In order to reduce memory, this paper also proposes a dynamic programming algorithm to solve the four target levels. The experimental results show that the algorithm has a better performance than DIR-24-8-BASIC. We also design the hardware architecture which fits for being implemented on FPGA. The simulated results show that it furnishes 15×106 routing lookups/s.