Fast IP routing lookup with configurable processor and compressed routing table
H.M. Ji, Rangarajan Srinivasan · 2002
We examine a primitive data structure for routing lookup called 24/8 which requires about 32 MB memory to store the routing table information. A novel compression algorithm is used to reduce the memory requirement to about 3 MB. The data structure is common for both route lookup and update. We present a fast route lookup algorithm and an efficient update algorithm that supports incremental route update. A configurable processor is used to achieve fast IP route lookup. Through configuring the processor properly and developing a few customized instructions specifically for route lookup, we can achieve up to 66 million lookups per second (MLPS) for the processor at 200 MHz.