Technical Report Number
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's Tree Bitmap algorithm  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's scalability, efficiency, and favorable update performance make it an ideal candidate for System-On-a-Chip (SOC) solutions for programmable router port processors.
Taylor, David E.; Lockwood, John W.; Sproull, Todd; and Parlour, David B., "Scalable IP Lookup for Programmable Routers" Report Number: WUCS-01-33 (2001). All Computer Science and Engineering Research.
Permanent URL: http://dx.doi.org/10.7936/K7XP735N