Efficient Hashing Technique Based on Bloom Filter for High-Speed Network

摘要

Hashing is an extensively used technique for packet-processing of High-Speed Network. Hashing provides a more efficient way for storing and looking up TCP sessions, achieving O(1),query, insert, and delete operations at low loads. However, with the rapid development of Network, we have to deal with packets from higher-speed as well as higher-load Network which means that it should be necessary to process more packets in constant time. In this case, traditional hashing scheme using a single hash function with chaining to deal with collisions cannot alleviate the situation of more frequent collisions caused by increased table occupancy and load. In this paper, we aim to seek what makes a more efficient Hashing Scheme from three aspects: Hash function, data storing structure and collision resolution policy. Also, we will survey much of the recent work in hashing scheme, paying particular attention to their performance in High-Speed Network and the difference in their performance when dealing with various situations. Besides, in this paper, we propose a Hashing-Scheme called PBS-CPE (Previous Bucket Store-Change Priority of Elements). Strictly speaking, PBS-CPE is a fast-querying method instead of a complete set of Hashing Scheme, however, PBS-CPE can fit in as part of any efficient Hashing Scheme just because of this.