基于压缩Trie树的以太网地址查找结构

Ethernet MAC Address Lookup Architecture Based on Compacted Trie

介绍了一种基于hash表和压缩trie树的查找与更新方法,每个hash桶中的4个地址节点按照trie树的方式组织,并压缩成一个25位字。基于FPGA实现时查找速度为133MSPS,IXP1200的一个微引擎每秒可完成1M次转发表更新。与采用片上嵌入式存储器的以太网交换芯片相比,查找过程可以减少一半的存储器访问带宽,转发表可放置到大容量片外存储器中,从而减少交换芯片面积和成本,显著降低hash表的冲突率。

Ethernet media access control （MAC） address lookup is one of the design challenges of high-performance Ethernet switch chips. In this paper, the trie of four address nodes in one hash bucket are compacted into a 25-bit word. The search procedure based on the compacted word is performed by a three-stage pipeline, which runs at over 133 MSPS on FPGAs. The address-learning algorithm can perform 1 million updating operations per second with one of six micro-engines in IXP1200. With this scheme, memory bandwidth in searching can be decreased by half, and the MAC address forward table can be placed in the high capacity commercial memory modules. Compared with the switch chips whose forward table is placed in the embedded memory, its hash table capacity is higher and the collision rate is much lower.