Using multiple hash functions to improve IP lookups
Authors:
- M. MitzenmacherMMM. Mitzenmacher
- 13 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3, 1454-1463
Abstract
High performance Internet routers require a mechanism for very efficient IP address look-ups. Some techniques used to t his end, such as binary search on levels, need to construct quickly a good hash table for the appropriate IP prefixes. In this paper we describe an appr oach for obtaining good hash tables based on using multiple hashes of each input key (which is an IP address). The methods we describe are fast, simple, scalable, parallelizable, and flexible. In particular, in i nstances where the goal is to have one hash bucket fit into a cache line, using mult iple hashes proves extremely suitable. We provide a general analysis of this hashing technique and specifically discuss its application to binar y search on levels. Keywords—IP routing, hashing, binary search on levels, two choices.Keywords
This publication has 10 references indexed in Scilit:
- How asymmetry helps load balancing2003
- Load balancing and density dependent jump Markov processes2002
- Studying Balanced Allocations with Differential EquationsCombinatorics, Probability and Computing, 1999
- Routing with a clueACM SIGCOMM Computer Communication Review, 1999
- Fast address lookups using controlled prefix expansionACM Transactions on Computer Systems, 1999
- Scalable high speed IP routing lookups1997
- Markov Processes1986
- Approximation of Population Processes1981
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- Solutions of ordinary differential equations as limits of pure jump markov processesJournal of Applied Probability, 1970