Very Fast Routing Table Lookup and Update Algorithm Based on Index and Compression
Internet protocol (IP) address lookup is a critical function of the network processors. While lots of solutions to this problem have been presented, few of them achieves line rate lookup and high update performance, high memory efficiency, and low hardware cost simultaneously. It is popular to use the content addressable memory devices for current commercial products, but it is a high cost, high power solution, particularly when applied to large databases. This paper presentes a novel high performance routing table lookup and update algorithm. According to the all-around performance, such as search and update performance, cost and consuming power, this work is better than the state-of-the-art. This algorithm is based on the index and compressed bit vector. Here not only one SRAM access cycle routing table lookup performance is accomplished but also two SRAM access cycles update performance is achieved in a pipelined scheme. The search and update process is illustrated in details. A maximum 530k routing entries can be held in about 1Mbytes SRAM space.