Paper Info
Title
A highly deterministic hashing scheme using bitmap filter for high speed networking
Abstract
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.
Year
DOI
Venue
2015
10.1109/ICCNC.2015.7069445
ICNC
Keywords
Field
DocType
collision resolution mechanisms,hash collision,network traffic,hash queries,data structures,high speed networking,filter queries,bloom filters,off-chip memory accesses,bitmap filter,bidirectional hop hashing,telecommunication traffic,hashing scheme,table lookup,query processing,bismuth,indexes,mathematical model,system on chip
Primary clustering,Double hashing,Computer science,Universal hashing,Algorithm,Theoretical computer science,Hash function,Dynamic perfect hashing,Open addressing,Hash table,Linear hashing
Conference
Citations 
PageRank 
References 
2
0.40
10
Authors
4
Name
Order
Citations
PageRank
Hai Sun171.91
Yan Lindsay Sun27510.41
Victor C. Valgenti3297.00
Min Sik Kim425527.17