Design and Implementation of Hardware Search Algorithm Based on FPGA

Xi Gao ； Liyan Zhang

《Frontiers in Economics and Management》 2卷5期 (2021/05) Pp. 317-320

https://doi.org/10.6981/FEM.202105_2(5).0040

摘要

In the design of the switch, the search algorithm is one of the most critical core modules. There are many traditional table entry search methods, mainly: linear search method, binary tree search method, hash table search, etc. These search methods are software search methods based on SRAM, and the common feature is slow search speed. The linear lookup table method needs to traverse all entries in the table; the binary tree search method needs to traverse most nodes in the tree, and the search speed is greatly affected by the depth of the tree; the hash table search method is relatively fast, but with the network speed requirement As it gets higher and higher, hash search still cannot meet the demand for extremely fast search. This text designs and realizes a kind of hardware search algorithm, utilizes the characteristic of FPGA to process the data in parallel, speed up the data search ability greatly, further shorten the switch forwarding delay.

關鍵字

Field Programmable Gate Array ； Media Access Control Address ； TCAM

參考文獻

L.Zhang, Z.J.Wu, L.Z.Kang ,Z.J.Guo, Y.H.Lu. TCAM design and FPGA implementation based on SRAM[J]. Network Security Technology and Application, 2018(07): 23-24.

C.Li, Z.Q.Wang, D.Zhang. VerilogHDL design of CAM based on RAM structure [J]. Computer Engineering and Applications, 2003(27): 157-159.

J.Q.Lu, Z.P.Huang, Liu Chunwu, D.S.Liu, S.Chen . Design and implementation of a network shunt system based on FPGA+TCAM architecture[J]. Microcomputers and Applications, 2016, 35(15): 65-68+71 .

S.W.Chen, W.W.Huang ,J.Y.Cao. FPGA hardware implementation of a deep packet inspection engine[J]. Measurement and Control Technology, 2014, 33(06): 100-102+109.

X.B.Zhang. Research on routing lookup algorithm and its FPGA implementation [D]. East China Normal University, 2006.