Trie树路由查找算法在网络处理器中的实现

摘要

Trie tree data structure is flexible to realize and require small storage space, and it is the preferred to realize high speed routing lookup and packet forwarding. In order to meet the design requirements of micro engine of 10 Gb/s line speed in Network Processor(NP), an optimal balance, multilayer storage routing lookup algorithm based on Trie tree is proposed. That is to establish a balanced compression tree structure, then the adjacent multi nodes are compressed to a storage node. It constructs a specific tree structure to reduce the tree search depth, exchanging space for time, improving the efficiency of lookup and packet forwarding. Router lookup algorithm based on Trie tree is implemented in NP design, and the algorithm performance is analyzed. A single micro engine lookup speed is up to 4.4 Mb/s, and it has an advantage of small storage and high update speed.%Trie树数据结构的实现方法灵活，所需存储器空间小，是实现高速路由查找和分组转发的理想选择。为满足10 Gb/s陑速度网络处理器中微引擎的设计要求，提出一种基于最优平衡、多层存储的 Trie树路由查找算法。建立一种平衡的压缩树结构，将该树中陒邻的多层节点压缩到一个存储节点中。通过构造特定的数据存储结构来减小树的搜索深度，以空间换取时间，从而提高路由查找速度和分组转发效率。在网络处理器的查找微引擎设计中实现 Trie路由查找算法，实验结果表明，单个微引擎的查找速度为4.4 Mb/s，能达到节省存储空间、提高查找效率的效果。