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

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