摘要
针对高速网络环境下连接记录管理的性能需求,提出了一种改进的高效哈希表PRH-MTF(伪随机哈希-移至最前).首先在定义输入关键字即连接标识符的基础上,通过选择适当的运算符,设计了高效鲁棒的哈希函数PRH.为有效解决哈希冲突,根据网络数据流局部性特点,应用MTF启发法,改进了传统的链式冲突解决方法.以分组火车模型作为数据包到达模式,分析了PRH-MTF哈希表的算法复杂度,推导出了平均查找长度.最后通过实际高速网络数据流和模拟攻击的方式,对PRH-MTF哈希表进行了实验评估.实验结果表明,PRH-MTF哈希表在查找性能和抗攻击能力等方面均优于传统的简单排序哈希表.
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.
出处
《华中科技大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2011年第2期19-22,31,共5页
Journal of Huazhong University of Science and Technology(Natural Science Edition)
基金
国家自然科学基金资助项目(60973113)
关键词
高速网络
哈希表
连接记录管理
网络数据流局部性
移至最前启发法
High-speed networks
Hash table
connection record management
network traffic locality
move to front heuristic
