A hierarchical hashing scheme to accelerate longest prefix matching

Longest Prefix Matching in IP Address lookup remains a bottleneck for high-speed routers where large volumes of traffic at multi-gigabyte link speeds require extremely fast lookup time. By taking advantage of bitmap and hashing techniques effectively used in Tree Bitmap algorithm and Binary hash searching on prefix length algorithm we propose a hierarchical hashing scheme based on observations about prefix length distribution in real routing tables. Theoretical analysis and experiments using real routing tables show that our scheme significantly improve IP lookup efficiency by remarkably reducing the number of memory access, consuming less memory and enabling fast update.