A highly deterministic hashing scheme using bitmap filter for high speed networking

In modern network devices the query performance for a hashing method degrades sharply due to non-determinism incurred by hash collision. Although previous collision resolution mechanisms have made remarkable progress, there is still much room to improve deterministic performance by resolving hash collisions more effectively. Further, the use of probabilistic, on-chip, summaries such as Bloom filters in these solutions causes a large number of off-chip memory accesses when under heavy network traffic. Even worse, these solutions use separate hash computation for filter queries and hash queries, doubling the computational overhead for hash access. We propose two novel collision resolution mechanisms, Double Out hashing and Bidirectional Hop hashing and establish a multiple-segment hash construction to facilitate deterministic query. Collision is restricted to only one segment and the length of a probe sequence in each segment is minimized to 1. In addition an important category of false positive is reduced to 0 due to exact bitmap filters. The use of a unique set of hash functions for filters and hash tables avoids unnecessary computation.