An efficient oriented-Hash table for connection record management in high-speed networks

作者：Xiong Bing^*; Li Feng; Jiang Lalin; Chen Xiaosu

来源：Journal of Huazhong University of Science and Technology (Natural Science Edition), 2011, 39(2): 19-22+31.

• Average search lengths
• Hash collisions
• Hash table
• High-speed
• Lookup performance
• Move to front heuristic
• Move-to-front
• Network traffic
• Network traffic locality
• Packet arrivals
• Packet trains
• Performance requirements
• Pseudo random
• Record management

An improved efficient Hash table PRH-MTF (pseudo random hashing-move to front) was presented, after the performance requirements of connection record management in high-speed networks were considered. Firstly, an efficient and robust Hash function PRH by defining connection identifier as its input keyword and selecting suitable operators for it were designed. To resolve Hash collision efficiently, the MTF heuristic was applied to improve the traditional chaining resolution based on network traffic locality. Selecting packet train model as the packet arrival pattern, the complexity of PRH-MTF Hash table was analyzed and its average search length was deduced. Finally, PRH-MTF Hash table by experiments with physical high-speed network traffic and attack simulation were evaluated. Experimental results indicate that the PRH-MTF Hash table performs better than the traditional simple sorted Hash table in terms of lookup performance and robustness.

• 出版日期2011