Research On High-Performance Hashing Techniques And Their Applications

Hashing techniques,which have O(1)lookup complexity,are widely used in a variety of network applications.There are many researches on the hashing techniques in the academic community.However,with new development trends of the network,the hashing techniques face some new challenges,which are embodied in: 1)With the rapid growth of the bandwidth of high-speed network,the network functions,which need to keep pace with the line rate,require higher and higher performance,which results that the hash computational cost gradually becomes the system performance bottleneck;2)The parallel processing capacity of network equipment is increasingly rich,making an urgent task to use the parallel processing capacity to accelerate traditional hashing techniques;3)Many network applications require better and better quality of service(QoS),while high-speed routers,as the core forwarding equipment of the network,need better loadbalancing mechanism to improve the QoS of the network.To solve these challenges,this dissertation proposes several new hashing technique solutions.The main contributions are listed as follows:1.This dissertation proposes the One-Hashing Bloom Filter(OHBF)data structure which aims to reduce the hash computational cost.The OHBF uses one hash function and k modulo operations to replace the k hash functions in the standard Bloom filter.Since the computational cost of a modulo operation is much lower than a hash function,the OHBF reduces the computational cost to nearly 1/k of the standard Bloom filter.While reducing the hash computational cost,the OHBF keeps nearly the same false positive probability as the standard Bloom filter.The experiments show that the OHBF can greatly improve the elements’ query speed,and achieve the same false positive probability as its theoretical value.2.This dissertation proposes the Ultra-Fast Bloom Filter(UFBF)data structure which is accelerated by the SIMD parallel technique.The standard Bloom filter implements sequential hash function computation and bit-test processes.While UFBF develops a parallel hash computation algorithm and a parallel bit-test algorithm,by the use of the SIMD technique.To improve the cache hit rate in the element query process,an element’s information is encoded in a block of the bit vector.With a strict alignment condition satisfied,only one cache miss can occur in one element’s query process in worst case.Experimental results show that the UFBF enhances the query speed of about 2 to 3 times,as it effectively improves both the parallelism and the cache hit rate in the query process.3.In a distributed scheduling environment,dispatching traffic with a hash method can achieve good load-balancing.However,under this scheme,a processing engine will become overloaded with a small probability.To solve this problem,this dissertation proposes a randomized load-balancing algorithm.When a processing engine is overloaded,a portion of the traffic that is sent to this processing engine will be re-dispatched to other processing engines with a randomized way.In this dissertation,it has been proved that once a processing engine becomes overloaded,the proposed randomized load-balancing algorithm can restore load-balancing with high probability.Trace-driven experiments show that the packet drop rate of the scheme using randomized load-balancing algorithm,is at least an order of magnitude lower than the scheme using pure-hashing algorithm.