IP Routing Based on Double Hashing

Michael Mitzenmacher
Harvard University

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 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.

Prof. Mitzenmacher would like to speak with graduate students interested in hearing about faculty positions at Harvard (Q&A, 3:00-3:30, room TBD). He would also like to speak with undergraduates interested in graduate school (Q&A, 1pm-3pm, room TBD).