CAM辅助的哈希表查找性能分析

Analysis on Lookup of CAM Aided Hash Table

现有大规模IP流处理方式中,哈希机制极具优势而在高速网络环境下被广泛采用,但其查找性能直接受限于访存次数。该文主要研究了CAM(Content Addressable Memory)辅助的哈希表(CAHT)查找性能。利用合理的近似,推导了单函数CAHT查找时平均访存次数的理论下限;结合单函数CAHT的分析结论给出了多函数CAHT查找时达到平均访存次数最小的条件。最后,使用实际网络数据验证了分析结果的有效性,为准确评估CAHT处理能力提供了必要的理论依据。

Hashing is popularly adopted when it comes to a large scale of IP flows.High throughout is available with minimized average memory access number.This paper mainly focused on the lookup performance of CAM（Content Addressable Memory） Aided Hash Table（CAHT）.By rational approximation,the paper provides the lower bound on average memory access number over lookup of CASHT;based on the analysis of CASHT,the paper also proposes the condition when to get the lower bound on average memory access number over lookup of CAMHT;Finally,simulation of actual network data shows its consistency to the theory model,which gives essential theory support to design and evaluate the hashing scheme in the actual applications.