-------------------------------------------------------------------------------
                                       
                                       
                   B O S T O N   U N I V E R S I T Y
                                       
                      Computer Science Department
                                       
                          C O L L O Q U I U M

          Using Multiple Hash Functions to Improve IP Routing


                         Michael Mitzenmacher
                          Harvard University


   		         Wednesday, October 11
			       3:00 PM 
                       (Coffee served at 2:45PM)

                                       
                         Seminar Room / MCS 135

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 prefixes.  In this talk we describe an
approach for obtaining good hash tables by 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 for applications
othter than IP routing.  In particular, in instances where the goal is
to have each hash bucket fit into a single cache line, using multiple
hashes proves extremely suitable.  We provide a general analysis of
this hashing technique as well as demonstrate its performance for
binary search on levels.

Includes joint work with Berthold Voecking and Andrei Broder.


Host:  John Byers (byers@cs.bu.edu)

-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
-------------------------------------------------------------------------------