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

《CAM辅助的哈希表查找性能分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第33卷第2期2011年2月电子与信息学报JournalofElectronics＆InformationTechnologyVbl．33No．2Feb．2011CAM辅助的哈希表查找性能分析万成威‘①邬江兴①李玉峰∞兰巨龙①⋯(国家数字交换系统工程技术研究中心郑州450002)⋯(防空兵指挥学院信息控制系郑州450002)摘要：现有大规模IP流处理方式中，哈希机制极具优势而在高速网络环境下被广泛采用，但其查找性能直接受限于访存次数。该文主要研究了CAM(ContentAddressableMemory)辅助的哈希表(CAHT)查找

2、性能。利用合理的近似，推导了单函数CAHT查找时平均访存次数的理论下限：结合单函数CAHT的分析结论给出了多函数CAHT查找时达到平均访存次数最小的条件。最后，使用实际网络数据验证了分析结果的有效性，为准确评估CAHT处理能力提供了必要的理论依据。关键词：CAM(ContentAddressableMemory)辅助的哈希表(CAHT)；查找；平均访存次数下限；泊松分布中图分类号：TP393文献标识码：A文章编号：1009—5896(2011)02-0272-06DOI：10．3724／SP．J．1146．2010．00162Analysi

3、sonLookupofCAMAidedHashTableWanCheng-wei①WuJiang-xing①LiYu-feng∞LanJu-long$⋯(NationalDigitalSwitchingSystemEngineeringandTechnologicalR&DCenter,Zhengzhou450002，China)⋯(Departmento／InformationandControl，AirDefenseCommandCollege，Zhengzhou450002，China)Abstract：Hashingispopula

4、rlyadoptedwhenitcomestoalargescaleofIPflows．Highthroughoutisavailablewithminimizedaveragememoryacee鹤number．ThispapermainlyfocusedonthelookupperformanceofCAM(ContentAddressableMemory)AidedHashTable(CAHT)．Byrationalapproximation，thepaperprovidesthelowerboundonaveragememoryac

5、ce88numberoverlookupofCASHT；basedontheanalysisofCASHT，thepaperalsoproposestheconditionwhentogetthelowerboundonaveragememoryacce&3numberoverlookupofCAMHT；Finally,simulationofactualnetworkdatashowsitsconsistencytothetheorymodel，whichsjvesessentialtheorysupporttodesignandeval

6、uatethehashingschemeintheactualapplications．Keywords：CAM(ContentAddressableMemory)AidedHashTable(CAHT)；Lookup；Lowerboundofaveragememoryaccess；Poiseondistribution1引言EverythingoverIP的思想使得目前网络承载的业务日渐丰富，同时也对互联网的服务质量(QualityofService，QoS)提出了更高的要求，在下一代互联网的研究中，广泛采用了基于策略和流的网络(Poli

7、cyandFlowBasedNetwork，PFBN)架构II-al，期望保证策略指定业务的QoS，从而实现基于流的带宽管理，如斯坦福大学的Ethane[2l网络结构，基于逐流的授权认证与带宽分配策略实现网络的安全访问与精细化管理。PFBN面临的一个重要挑战就是大规模IP流信息的存储与高速处理之2010-02-26收到．2010-11．15改回国家973计划项目(2007CB307102)和国家863计划项目(2008AA01A323)资助课题‘通信作者：万成威chwwanOgnmil，OOrn间的矛盾。目前骨干网中的并发流数量均在百万条以

8、上，需要大容量存储器件实现流信息的存储，然而，大容量存储器件访问速度较慢，因此在处理每个报文时，很难进行连续多次访存：同时，多次访存也增加了系统功耗，需要进行散热等处理，提高了系