基于Hash和CAM的IPv6路由查找算法

doi:10.3969/j.issn.1000-3428.2012.08.017

计算机工程 ›› 2012, Vol. 38 ›› Issue (08): 50-53. doi: 10.3969/j.issn.1000-3428.2012.08.017

基于Hash和CAM的IPv6路由查找算法

王瑞青 ^a，杜慧敏 ^b，王亚刚 ^a

(西安邮电学院 a. 计算机学院；b. 电子工程学院，西安 710061)

收稿日期:2011-08-15 出版日期:2012-04-20 发布日期:2012-04-20
作者简介:王瑞青(1986－)，女，硕士研究生，主研方向：计算机系统结构，IPv6网络；杜慧敏、王亚刚，教授
基金资助:
国家自然科学基金资助项目(60976020)

IPv6 Routing Lookup Algorithm Based on Hash and CAM

WANG Rui-qing ^a, DU Hui-min^b, WANG Ya-gang ^a

(a. School of Computer Science and Technology; b. School of Electronic Engineering, Xi’an University of Post and Telecommunications, Xi’an 710061, China)

Received:2011-08-15 Online:2012-04-20 Published:2012-04-20

摘要/Abstract

摘要： 分析实际网络中的IPv6前缀分布规律与增长趋势，提出一种基于Hash和内容可寻址存储器(CAM)的IPv6路由查找算法。将长度能被8整除的前缀存储在8个Hash表中，发生Hash冲突的前缀存储在CAM中，长度不能被8整除的前缀按照一定的组织方式存储在随机存取存储器中。分析结果表明，该算法具有较高的存储利用率、查找速率及更新速率，并且易于扩展和硬件实现。

关键词: IPv6路由查找, 哈希压缩, 两级查找, 流水线, 内容可寻址存储器

Abstract: This paper presents an IPv6 lookup algorithm based on Hash and Content Addressable Memory(CAM) by analyzing the prefix length distribution of routing table and the growth trend of routing table entries. The prefixes whose length can be divided by 8 are stored in 8 Hash tables, and the remaining prefixes are stored into expanded Random Access Memory(RAM). Analysis result shows that the algorithm has high efficient storage utilization, searching rate and updating rate. It is easy to be scalded in hardware.

Key words: IPv6 routing lookup, Hash compression, two-level lookup, pipeline, Content Addressable Memory(CAM)

中图分类号:

TP393

王瑞青, 杜慧敏, 王亚刚. 基于Hash和CAM的IPv6路由查找算法[J]. 计算机工程, 2012, 38(08): 50-53.

WANG Rui-Jing, DU Hui-Min, WANG E-Gang. IPv6 Routing Lookup Algorithm Based on Hash and CAM[J]. Computer Engineering, 2012, 38(08): 50-53.

http://www.ecice06.com/CN/Y2012/V38/I08/50

参考文献

[1] 徐恪, 徐明伟, 吴建平. 路由查找算法研究综述[J]. 软件学报, 2002, 13(1): 42-50.
[2] Ruiz-Sanchez M A, Biersack E W, Dabbous W. Survey and Taxonomy of IP Address Lookup Algorithms[J]. IEEE Network, 2001, 15(2): 8-23.
[3] Kim Nam-Soo, Kim Young-Sang. Comparative Studies of Address Lookup Algorithms for IPv6[C]//Proc. of ICACT’06. Hong Kong, China: [s. n.], 2006: 285-290.
[4] 赵国峰, 闫亮. 用于快速流分类的关键字分解Hash算法[J].计算机工程, 2010, 36(16): 79-81.
[5] Gamache B, Pfeffer Z, Khatri S P. A Fast Ternary CAM Design for IP Networking Applications[C]//Proc. of the 12th International
Conference on Computer Communications and Networks. Dallas, USA: [s. n.], 2003: 434-439.
[6] 刘丹, 赵有健. 基于Trie树分割路由表降低TCAM功耗的方法[J]. 计算机工程, 2007, 33(11): 100-102.
[7] Erdem O, Bazlama X E, Bazlama?i C F. Array Design for Trie-based IP Lookup[J]. Communications Letters, 2010, 14(8): 773-775.
[8] Zheng Kai, Liu Zhen, Liu Bin. A Scalable IPv6 Route Lookup Scheme via Dynamic Variable-stride Bitmap Compression and Path Compression[J]. Computer Communications, 2006, 29(16): 3037-3050.
[9] Chu Yuansun, Su Huikai, Lin Pofeng, et al. IC Design of IPv6 Routing Lookup for High Speed Networks[C]//Proc. of the 6th International Conference on Computational Science. New York, USA: [s. n.], 2006: 1832-1835.
[10] Li Zhenqiang, Deng Xiaohong, Ma Hongxiao, et al. Divide and Conquer: A Scheme for IPv6 Address Longest Prefix Matching[C]//Proc. of Workshop on High Performance Switching and Routing. Hong Kong, China: [s. n.], 2006: 37-42.
[11] Gamache B, Pfeffer Z, Khatri S P. A Fast Ternary CAM Design for IP Networking Applications[C]//Proc. of the 12th International Conference on Computer Communications and Networks. Dallas, USA: [s. n.], 2003: 434-439.
[12] Table Data[EB/OL]. (2011-05-15). http://bgp.potaroo.net.
[13] Jain R. A Comparison of Hashing Schemes for Address Lookup in Computer Networks[J]. IEEE Transactions on Communications, 1992, 40(10): 1570-1573.

[1]	陈彦光, 王雷, 孙媛媛, 王治政, 张书晨. 面向法律文本的三元组抽取模型[J]. 计算机工程, 2021, 47(5): 277-284.
[2]	李雨倩, 焦继业, 刘有耀, 郝振和. 嵌入式RISC-V乱序执行处理器的研究与设计[J]. 计算机工程, 2021, 47(2): 261-267,284.
[3]	张浩, 魏敬和. 高效率PLB2AXI总线桥的设计与验证[J]. 计算机工程, 2020, 46(8): 228-234.
[4]	吴德祥, 班恬. 一种高速近似乘法器设计[J]. 计算机工程, 2019, 45(12): 289-293.
[5]	王俊昌,王振,付雄. 基于无锁数据结构的FIFO队列算法[J]. 计算机工程, 2018, 44(8): 315-320.
[6]	杨平平,岳春生,胡泽明. 异构信号处理平台中层次性流水线调度算法[J]. 计算机工程, 2018, 44(11): 83-89.
[7]	刘广钟,朱翔宇. 预调度流水线方式的水声传感器网络MAC协议[J]. 计算机工程, 2017, 43(8): 126-131.
[8]	余子健,马德,严晓浪,沈君成. 基于FPGA的卷积神经网络加速器[J]. 计算机工程, 2017, 43(1): 109-114,119.
[9]	徐渊,许晓亮,李才年,姜梅,张建国. 结合SVM分类器与HOG特征提取的行人检测[J]. 计算机工程, 2016, 42(1): 56-60,65.
[10]	张杰鑫,张铮. 包分类算法研究综述[J]. 计算机工程, 2015, 41(12): 111-118.
[11]	黄睿，杨庆庆，程洁琼，周晓方. LDPC与Turbo解码器中的专用控制器设计[J]. 计算机工程, 2014, 40(7): 1-6.
[12]	洪琪，何敏，范继聪，袁粲. 可重构浮点混合/连续乘-加器的设计与实现[J]. 计算机工程, 2014, 40(7): 272-276.
[13]	刘万军，孟煜，曲海成，石翠萍. 基于多尺度的多线程遥感影像渐进传输模型[J]. 计算机工程, 2014, 40(6): 225-229.
[14]	黄世伟, 王云峰. 基于流水线技术的并行模幂算法硬件实现[J]. 计算机工程, 2013, 39(7): 16-20,25.
[15]	张超, 杨晶晶, 王盛, 陈更生. 基于动态场景估计的自适应图像增强算法[J]. 计算机工程, 2013, 39(5): 34-41.

选择文件类型/文献管理软件名称

选择包含的内容

基于Hash和CAM的IPv6路由查找算法

IPv6 Routing Lookup Algorithm Based on Hash and CAM

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于Hash和CAM的IPv6路由查找算法

IPv6 Routing Lookup Algorithm Based on Hash and CAM

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价