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

Research on Fast Parallel Hash Algorithm for Switch Chip Address Lookup

  • 摘要: 为了以尽量少的硬件资源实现高效能的二层交换地址表查找功能, 通过分析交换芯片地址表以及循环冗余算法的特点, 提出了一种硬件电路由寄存器和异或门构成的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.

     

/

返回文章
返回