用于交换芯片地址表查找的快速并行Hash算法研究

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

用于交换芯片地址表查找的快速并行Hash算法研究

曹晓东, 石寅, 张强

文章导航 > 电子科技大学学报 > 2014 > 43(2): 287-291

曹晓东, 石寅, 张强. 用于交换芯片地址表查找的快速并行Hash算法研究[J]. 电子科技大学学报, 2014, 43(2): 287-291. doi: 10.3969/j.issn.1001-0548.2014.02.025

引用本文:

曹晓东, 石寅, 张强. 用于交换芯片地址表查找的快速并行Hash算法研究[J]. 电子科技大学学报, 2014, 43(2): 287-291. doi: 10.3969/j.issn.1001-0548.2014.02.025

CAO Xiao-dong, SHI Yin, ZHANG Qiang. Research on Fast Parallel Hash Algorithm for Switch Chip Address Lookup[J]. Journal of University of Electronic Science and Technology of China, 2014, 43(2): 287-291. doi: 10.3969/j.issn.1001-0548.2014.02.025

Citation:

CAO Xiao-dong, SHI Yin, ZHANG Qiang. Research on Fast Parallel Hash Algorithm for Switch Chip Address Lookup[J]. Journal of University of Electronic Science and Technology of China, 2014, 43(2): 287-291. doi: 10.3969/j.issn.1001-0548.2014.02.025

用于交换芯片地址表查找的快速并行Hash算法研究

doi: 10.3969/j.issn.1001-0548.2014.02.025

1.
中国科学院半导体研究所北京海淀区 100083

基金项目:

国家科技重大专项(2009ZX01031-002-002)

作者简介:
曹晓东(1980-),男,博士,主要从事SoC、数模混合集成电路方面的研究.

中图分类号: TN4

Research on Fast Parallel Hash Algorithm for Switch Chip Address Lookup

1.
Institute of Semiconductors,Chinese Academy of Sciences Haidian Beijing 100083

摘要: 为了以尽量少的硬件资源实现高效能的二层交换地址表查找功能, 通过分析交换芯片地址表以及循环冗余算法的特点, 提出了一种硬件电路由寄存器和异或门构成的10位并行Hash算法. 通过并行地将输入信号帧的48位物理地址转换为10位的地址表查询地址, 可以快速准确地查询1024存储深度的地址表, 采用该地址表查询算法的二层交换芯片实现了线速交换, 从而有效提高了所实现网络设备的性能. 仿真显示, 算法生成的Hash地址较为均匀地分布在其10位地址空间内, 有效地降低Hash冲突发生的几率. 采用FPGA实现的交换电路进一步验证了算法的优异性能.
- 地址查询 /
- 循环冗余码 /
- 哈希算法 /
- 交换芯片 /
- 均匀分布
Abstract: In order to implement a high performance layer 2 switch address lookup function with minimum hardware consumption, a 10-bit Hash algorithm consisting of registers and XoR gates was presented by analyzing the characteristics of switch chip address table and cyclic redundancy check algorithm. 48-bit physical address is transferred into 10-bit lookup address in parallel and the address table of 1 024 storage depth can be quickly and accurately searched. The layer 2 switch chip using this address lookup algorithm can implement line speed exchange. The performance of the network equipments using the switch chips can be improved. The generated Hash addresses are uniformly distributed in the 10-bit address space. The performance of the algorithm was further verified by using switch circuit implemented on FPGA.
- address lookup /
- cyclic redundancy checks /
- hash algorithm /
- switch chip /
- uniform distribution

[1]	张辰逸, 尚涛, 刘建伟. 基于交换门的前瞻启发式量子线路映射算法 . 电子科技大学学报, 2023, 52(4): 489-497. doi: 10.12178/1001-0548.2022339
[2]	白焱, 孙万录, 宋平, 李伟. 基于时间触发光纤通道网络的交换调度算法 . 电子科技大学学报, 2022, 51(3): 392-396. doi: 10.12178/1001-0548.2021275
[3]	王静, 雷珂, 李家仪, 田松涛, 王相隆. 基于非均匀循环编码的分组修复码构造 . 电子科技大学学报, 2022, 51(1): 57-64. doi: 10.12178/1001-0548.2021013
[4]	孟凡博, 巩小雪, 郭磊, 张旭. 基于马尔科夫预测的时分复用弹性波带交换算法 . 电子科技大学学报, 2018, 47(4): 486-490. doi: 10.3969/j.issn.1001-0548.2018.04.002
[5]	李玮, 张大方, 徐冰. 面向NDN中名字查找的哈希布鲁姆过滤器 . 电子科技大学学报, 2017, 46(5): 734-740. doi: 10.3969/j.issn.1001-0548.2017.05.016
[6]	康凯, 高宗智. CMOS多通道芯片 . 电子科技大学学报, 2016, 45(4): 502-510. doi: 10.3969/j.issn.1001-0548.2016.04.002
[7]	张兵, 马新新, 志光. 轻量级RFID双向认证协议设计与分析 . 电子科技大学学报, 2013, 42(3): 425-430. doi: 10.3969/j.issn.1001-0548.2013.03.021
[8]	张忠培, 高中杰, 徐俊辉. 高阶调制码辅助同步算法研究 . 电子科技大学学报, 2011, 40(6): 825-828. doi: 10.3969/j.issn.1001-0548.2011.06.003
[9]	王俊芳, 张思东. 通用高速分组交换调度算法 . 电子科技大学学报, 2010, 39(1): 69-73. doi: 10.3969/j.issn.1001-0548.2010.01.017
[10]	任超, 李战怀, 张英. 异构P2P网络的分布式查询协议 . 电子科技大学学报, 2009, 38(1): 108-112.
[11]	王娜, 张邦宁, 郭道省, 张国敏. 频偏条件下基于循环平稳的定时估计算法 . 电子科技大学学报, 2008, 37(2): 191-193,220.
[12]	佟卫华. 采用循环前缀的OFDM信道盲估计算法 . 电子科技大学学报, 2008, 37(3): 370-373.
[13]	许都, 宋雷, 王宏. 死锁恢复的多维交换结构容错路由算法 . 电子科技大学学报, 2008, 37(6): 844-847,854.
[14]	骆宗伟, 周世杰, LI Jenny. 一种轻量级RFID安全协议的改进 . 电子科技大学学报, 2007, 36(6): 1172-1178,1186.
[15]	高宏峰, 许宗泽, 吴援明. IRA码简化译码算法的研究 . 电子科技大学学报, 2005, 34(1): 40-43.
[16]	李刚俊. 冗余度机器人的运动规划碰撞算法 . 电子科技大学学报, 2005, 34(6): 828-831,864.
[17]	胡冰, 李乐民. 一种用于分组交换机的缓存管理算法 . 电子科技大学学报, 2004, 33(6): 656-658.
[18]	陈绍刚, 赵蜀蓉. 基于随机估值的两物品拍卖的投标决策 . 电子科技大学学报, 2002, 31(4): 418-421.
[19]	陈运, 龚耀寰. 大数幂剩余的二进制冗余数Montgomery算法 . 电子科技大学学报, 2000, 29(6): 587-590.
[20]	陈运, 龚耀寰. 基于二进制冗余数的递归余数和算法 . 电子科技大学学报, 2000, 29(1): 1-4.

WeChat

点击查看大图

计量

文章访问数: 3430
HTML全文浏览量: 146
PDF下载量: 66
被引次数: 0

用于交换芯片地址表查找的快速并行Hash算法研究

doi: 10.3969/j.issn.1001-0548.2014.02.025

1. 中国科学院半导体研究所北京海淀区 100083

基金项目:

国家科技重大专项(2009ZX01031-002-002)

作者简介:
曹晓东(1980-),男,博士,主要从事SoC、数模混合集成电路方面的研究.

收稿日期: 2012-12-10
修回日期: 2014-01-08
刊出日期: 2014-04-15

中图分类号: TN4

关键词:

摘要: 为了以尽量少的硬件资源实现高效能的二层交换地址表查找功能, 通过分析交换芯片地址表以及循环冗余算法的特点, 提出了一种硬件电路由寄存器和异或门构成的10位并行Hash算法. 通过并行地将输入信号帧的48位物理地址转换为10位的地址表查询地址, 可以快速准确地查询1024存储深度的地址表, 采用该地址表查询算法的二层交换芯片实现了线速交换, 从而有效提高了所实现网络设备的性能. 仿真显示, 算法生成的Hash地址较为均匀地分布在其10位地址空间内, 有效地降低Hash冲突发生的几率. 采用FPGA实现的交换电路进一步验证了算法的优异性能.

English Abstract

曹晓东, 石寅, 张强. 用于交换芯片地址表查找的快速并行Hash算法研究[J]. 电子科技大学学报, 2014, 43(2): 287-291. doi: 10.3969/j.issn.1001-0548.2014.02.025

引用本文:

曹晓东, 石寅, 张强. 用于交换芯片地址表查找的快速并行Hash算法研究[J]. 电子科技大学学报, 2014, 43(2): 287-291. doi: 10.3969/j.issn.1001-0548.2014.02.025

CAO Xiao-dong, SHI Yin, ZHANG Qiang. Research on Fast Parallel Hash Algorithm for Switch Chip Address Lookup[J]. Journal of University of Electronic Science and Technology of China, 2014, 43(2): 287-291. doi: 10.3969/j.issn.1001-0548.2014.02.025

Citation:

CAO Xiao-dong, SHI Yin, ZHANG Qiang. Research on Fast Parallel Hash Algorithm for Switch Chip Address Lookup[J]. Journal of University of Electronic Science and Technology of China, 2014, 43(2): 287-291. doi: 10.3969/j.issn.1001-0548.2014.02.025

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

期刊在线

编辑办公

友情链接

电子科技大学

版权所有 © 《电子科技大学学报》编辑部

地址: 成都市建设北路二段四号电子科技大学主楼中350室电话: 028-83202308,83207559 Email: xuebao@uestc.edu.cn

本系统由北京仁和汇智信息技术有限公司开发