摘要： 提出一种应用于网络处理器的Hash 算法,通过建立新型查找表的结构和构造两级Hash 函数,能够有效地解决Hash 冲突的问题。描述Hash 表的软件建立流程和硬件查找过程,在Hash 查找的基础上,给出硬件表项的学习过程和老化方法,简化表项的更新操作。针对不同的应用,建立不同类型的Hash 表,合理地利用内外部存储资源,兼顾了存储资源和处理速度的平衡。实验结果表明,该算法对各种查找表中不同的表项数目和关键词长度均具有较好的兼容性,成功查找的平均长度为2,减少了存储器的访存次数,其单个微引擎的查找速度高达25 Mb / s,能够满足网络处理器接口处理带宽20 Gb / s 的要求。

关键词: 网络处理器, Hash 表, 查找效率, 学习, 老化

Abstract: A novel Hash algorithm is proposed in this paper for network processor application. It resolves Hash collision problem by constructing new look up table and new two-level Hash function. The software processing and hardware lookup flow of Hash table are descripted,and the learning process and ageing machine for entry of table are designed for simplifying the entry updating operation. For different engineering applications,the algorithm sets up different Hash table, which makes the efficience of memory utilization improved and the tradeoff between memory and processing speed optimized. Simulation results show the algorithm works well despite of the number of table entry and the size of keyword.The average length of look up’s success is 2 and the memory access times is reduced dramaticlly. The look up speed of micro-engine is improved to 25 Mb / s,satisfing the requinrement of 20 Gb / s bandwidth performance of network processor.

Key words: network processor, Hash table, lookup efficiency, learning, ageing

中图分类号: 

• TP393