Scalable IP lookup for internet routers
Authors:
- D.B. ParlourDPD.B. Parlour
- 7 May 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 21 (4) , 522-534
Abstract
Internet protocol (IP) address lookup is a central processing function of Internet routers. While a wide range of solutions to this problem have been devised, very few simultaneously achieve high lookup rates, good update performance, high memory efficiency, and low hardware cost. High performance solutions using content addressable memory devices are a popular but high-cost solution, particularly when applied to large databases. We present an efficient hardware implementation of a previously unpublished IP address lookup architecture, invented by Eatherton and Dittia (see M.S. thesis, Washington Univ., St. Louis, MO, 1998). Our experimental implementation uses a single commodity synchronous random access memory chip and less than 10% of the logic resources of a commercial configurable logic device, operating at 100 MHz. With these quite modest resources, it can perform over 9 million lookups/s, while simultaneously processing thousands of updates/s, on databases with over 100000 entries. The lookup structure requires 6.3 bytes per address prefix: less than half that required by other methods. The architecture allows performance to be scaled up by using parallel fast IP lookup (FIPL) engines, which interleave accesses to a common memory interface. This architecture allows performance to scale up directly with available memory bandwidth. We describe the tree bitmap algorithm, our implementation of it in a dynamically extensible gigabit router being developed at Washington University in Saint Louis, and the results of performance experiments designed to assess its performance under realistic operating conditions.Keywords
This publication has 12 references indexed in Scilit:
- Control and configuration software for a reconfigurable networking hardware platform2003
- Routing lookups in hardware at memory access speeds2002
- Distributed network management in an Internet environment2002
- Design of a gigabit ATM switch2002
- Reprogrammable network packet processing on the field programmable port extender (FPX)2001
- Field programmable port extender (FPX) for distributed routing and queuing2000
- Faster IP lookups using controlled prefix expansion1998
- Faster IP lookups using controlled prefix expansionACM SIGMETRICS Performance Evaluation Review, 1998
- Fast address lookup for Internet routers1998
- Small forwarding tables for fast routing lookupsACM SIGCOMM Computer Communication Review, 1997