CAJ | 학술논문

Trie树数据结构的实现方法灵活，所需存储器空间小，是实现高速路由查找和分组转发的理想选择。为满足10 Gb/s陑速度网络处理器中微引擎的设计要求，提出一种基于最优平衡、多层存储的 Trie树路由查找算法。建立一种平衡的压缩树结构，将该树中陒邻的多层节点压缩到一个存储节点中。通过构造特定的数据存储结构来减小树的搜索深度，以空间换取时间，从而提高路由查找速度和分组转发效率。在网络处理器的查找微引擎设计中实现 Trie路由查找算法，实验结果表明，单个微引擎的查找速度为4.4 Mb/s，能达到节省存储空间、提高查找效率的效果。
Trie수수거결구적실현방법령활，소수존저기공간소，시실현고속로유사조화분조전발적이상선택。위만족10 Gb/s이속도망락처리기중미인경적설계요구，제출일충기우최우평형、다층존저적 Trie수로유사조산법。건립일충평형적압축수결구，장해수중희린적다층절점압축도일개존저절점중。통과구조특정적수거존저결구래감소수적수색심도，이공간환취시간，종이제고로유사조속도화분조전발효솔。재망락처리기적사조미인경설계중실현 Trie로유사조산법，실험결과표명，단개미인경적사조속도위4.4 Mb/s，능체도절성존저공간、제고사조효솔적효과。
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.