基于d-left算法的硬件哈希表研究与实现  

Research and Implementation of Hardware Hash Table Based on d-left Algorithm

作　　者：谭兴晔[1] 张勇 雷振明[1] 

机构地区：[1]北京邮电大学ATM中心,北京100876 [2]Intel中国研究中心,北京100020

出　　处：《计算机应用研究》2005年第10期52-55,共4页Application Research of Computers

基　　金：国家自然科学基金重大项目(69896240);"211工程"重点学科建设项目

摘　　要：基于d-left算法和片内CAM的硬件哈希表解决方案可以通过一次查表操作获得结果,解决了一般哈希表存在的最坏访问时间的问题;利用片内CAM使哈希表的加入失败概率降到可以忽略的程度,同时提高了存储器的利用率。在实现方面可以按照设计需要折中考虑存储器利用率、加入失败概率、占用片内CAM资源多少以及硬件实现复杂度等因素,具有很好的灵活性和可扩展性,将之应用到基于哈希表的硬件报文分类算法中,可以有效地提高其处理性能。仿真和应用证明其有很好的可行性和实用性。Hash table, with its lower cost and better scalability, is widely used in many routing and packet classification algorithms. This paper presents an approach for obtaining high-performance hardware Hash table based on d-left algorithm and onchip CAM, The time complexity of insertion and lookup time of Hash table is only by using d-left algorithm. Benefiting from faster on-chip CAM, the failure probability of insert operation decrease to ultra low level, at the same time, the availability ratio of memory is improved dramatically. The results of the experiment and application show that it is practical and efficient.

关 键 词：哈希 d-left算法 片内CAM 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]