Guided multiple hashing: Achieving near perfect balance for fast routing lookup

The routing and packet forwarding function is at the core of the IP network-layer protocols. The throughput of a router is constrained by the speed at which the routing table lookup can be performed. Hash-based lookup has been a research focus in this area due to its O(1) average lookup time, as compared to other approachs such as trie-based lookup which tends to make more memory accesses. With a series of prior multi-hashing developments, including d-random, 2-left, and d-left, we discover that a new guided multi-hashing approach holds the promise of further pushing the envelope of this line of research to make significant performance improvement beyond what today´s best technology can achieve. Our guided multi-hashing approach achieves near perfect load balance among hash buckets, while limiting the number of buckets to be probed for each key (address) lookup, where each bucket holds one or a few routing entries. Unlike the localized optimization by the prior approaches, we utilize the full information of multi-hash mapping from keys to hash buckets for global key-to-bucket assignment. We have dual objectives of lowering the bucket size while increasing empty buckets, which helps to reduce the number of buckets brought from off-chip memory to the network processor for each lookup. We introduce mechanisms to make sure that most lookups only require one bucket to be fetched. Our simulation results show that with the same number of hash functions, the guided multiple-hashing schemes are more balanced than d-left and others, while the average number of buckets to be accessed for each lookup is reduced by 20-50%.