Using multiple hash functions to improve IP lookups
- 13 November 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3, 1454-1463
- https://doi.org/10.1109/infcom.2001.916641
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 balancingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Load balancing and density dependent jump Markov processesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- 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 lookupsPublished by Association for Computing Machinery (ACM) ,1997
- Markov ProcessesPublished by Wiley ,1986
- Approximation of Population ProcessesPublished by Society for Industrial & Applied Mathematics (SIAM) ,1981
- 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