IP address lookup using a dynamic hash function

The explosive growth of the Internet and of new applications over IP has made Internet routers the bottleneck in enabling higher speed communications. One of the more resource intensive functions of a router is the IP address lookup. This paper proposes a new IP address lookup algorithm that improves the performance and memory requirements of a hash-based lookup by exploiting the statistical repartition of prefixes in the forwarding table. Prototyping has shown that only one main memory access and several fast cache memory accesses are needed to perform a lookup on average. Furthermore, the configuration of the data structures can be tuned to control both memory usage and lookup performance