Scalable IP Lookup for Programmable Routers

Authors

David E. Taylor, Washington University in St Louis
John W. Lockwood, Washington University in St. Louis
Todd Sproull, Washington Univeristy in St. Louis
David B. Parlour, Washington University in St. Louis

Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2001-01-01

Filename

WUCS-01-33.PDF

Technical Report Number

WUCS-01-33

Abstract

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 [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's scalability, efficiency, and favorable update performance make it an ideal candidate for System-On-a-Chip (SOC) solutions for programmable router port processors.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7XP735N

Recommended Citation

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.
https://openscholarship.wustl.edu/cse_research/271