High performance Internet routers require a mechanism for very efficient IP address look-ups. Some techniques used to this end, such as binary search on levels, need to construct quickly a good hash table for the appropriate IP prefixed. In this talk we describe an approach for obtaining good hash tables using multiple hashes on each IP address. The methods we describe are fast, simple, scalable, parallelizable, and flexible.

The double hashing technique is of general interest in applications other than IP routing. In particular, in instances where the goal is to have one hash bucket to fit into a cache line, using multiple hashes proves extremely suitable. We provide a general analysis of this hashing technique in addition to its application to IP routing based on binary search on levels.

Includes joint work with Berthold Voecking and Andrei Broder.

Host: Rajmohan Rajaraman