A collision-mitigation hashing scheme utilizing empty slots of cuckoo hash table

摘要

In SDN and NFV technologies, performance of a virtual switch is important to provide network functionalities swiftly. Since the lookup operation of the virtual switch has been considered a major bottleneck of performance, we need to devise an efficient way to reduce the lookup time. To improve the lookup speed, previous research has suggested a compact lookup table in a fast memory, but the issue of collision in a hash table has not been addressed well enough. This paper proposes a new scheme that mitigates collisions by utilizing empty slots of the hash table. We propose to insert a new element that may collide to an empty slot instead of linking it with a pointer. According to an evaluation on our experiments, about 20% of elements that could have experienced collisions in the conventional scheme are inserted into empty slots in each bucket. Moreover, the access time of collided elements has halved by avoiding unnecessary memory accesses.