Scalable IP Lookup for Programmable Routers

Continuing growth in optical link speeds places increasing demands on the performance of Internet routers, while deployment of embedded and distributed network services imposes new demands for flexibility and programmability. IP adress lookup has become a significant performance bottleneck for the highest performance routers. New commercial products utilize dedicated Content Addressable Memory (CAM) devides to achieve high lookup speeds. This paper describes an efficient, scalable lookup engine design, able to achieve high-performance with the use of a small portion of a reconfigurable logic device and a commodity Random Access Memory (RAM) device. Based on Eatherton\u27s Tree Bitmap algorithm [1] the Fast Internet Protocol Lookup (FIPL) engine can be scaled to achieve over 9 million lookups per second at the fairly modest clock speed of 100 MHz. FIPL\u27s scalability, efficiency, and favorable update performance make it an ideal candidate for System-On-a-Chip (SOC) solutions for programmable router port processors