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

万成威; 邬江兴; 李玉峰; 兰巨龙

doi:10.3724/SP.J.1146.2010.00162

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

doi: 10.3724/SP.J.1146.2010.00162

万成威^{*① 邬江兴,},
邬江兴,
李玉峰,
兰巨龙

基金项目:

国家973计划项目(2007CB307102)和国家863计划项目(2008AA01A323)资助课题

计量
- 文章访问数: 3122
- HTML全文浏览量: 89
- PDF下载量: 1131
- 被引次数: 0
出版历程
- 收稿日期: 2010-02-26
- 修回日期: 2010-11-15
- 刊出日期: 2011-02-19

Analysis on Lookup of CAM Aided Hash Table

摘要

摘要: 现有大规模IP流处理方式中，哈希机制极具优势而在高速网络环境下被广泛采用，但其查找性能直接受限于访存次数。该文主要研究了CAM(Content Addressable Memory)辅助的哈希表(CAHT)查找性能。利用合理的近似，推导了单函数CAHT查找时平均访存次数的理论下限；结合单函数CAHT的分析结论给出了多函数CAHT查找时达到平均访存次数最小的条件。最后，使用实际网络数据验证了分析结果的有效性，为准确评估CAHT处理能力提供了必要的理论依据。
- CAM(Content Addressable Memory)辅助的哈希表(CAHT) /
- 查找 /
- 平均访存次数下限 /
- 泊松分布
Abstract: 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.
- CAM (Content Addressable Memory) Aided Hash Table (CAHT) /
- Lookup /
- Lower bound of average memory access /
- Poisson distribution

HTML全文

参考文献(1)

[1] Yan H.[J].Maltz D A, and Eugene Ng T S, et al.. Tesseract: a 4D network control plane [C]. 4th USENIX Symposium on Networked Systems Design Implementation (NSDI), Cambridge, MA, USA, April 11-1.2007,:- [2] Casado M, Freedman M J, and Pettit J, et al.. Ethane: taking control of the enterprise [J].ACM SIGCOMM Computer Communication Review.2007, 37(4):1-12 [3] McKeown N, Anderson T, and Balakrishnan H. OpenFlow: enabling innovation in campus networks [J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74. [4] Azar Y, Broder A Z, and Karlin A R, et al.. Balanced allocation [J].SIAM Journal on Computing.1999, 29(1):180-200 [5] Kirsch A and Mitzenmacher M. The power of one move: hashing schemes for hardware [C]. the 27th IEEE International Conference on Computer Communications (INFOCOM), Phoenix, AZ, USA, April 15-17, 2008: 565-573. [6] Fotakis D, Pagh R, and Sanders P, et al.. Space efficient hash tables with worst case constant access time [C]. the 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27-March 1, 2003: 271-282. [7] Kanizo Y, Hay D, and Keslassy I. Optimal fast hashing [C]. the 28th IEEE International Conference on Computer Communications (INFOCOM), Rio de Janeiro, Brazil, April 19-25, 2009: 2500-2508. [8] Bremler-Barr A, Hay D, and Hendler D, et al.. Layered interval codes for tcam-based classification [C]. the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, Annapolis, MD, USA, June 2-6, 2008: 445-446. [9] Steele M J. Le Cams inequality and Poisson approximations [J].American Mathematical Monthly.1994, 101(1):48-54 [10] Kurtz T G. Solutions of ordinary differential equations as limits of pure jump Markov processes [J].Journal of Applied Probability.1970, 7(1):49-58 [11] 程光, 龚俭, 丁伟等. 面向IP流测量的哈希算法研究[J].软件学报.2005, 16(5):652-658 Cheng Guang, Gong Jian, and Ding Wei, et al.. A hash algorithm for IP flow measurement [J].Journal of Software.2005, 16(5):652-658

施引文献

资源附件(0)

访问统计