CAJ | 학술논문

为解决在多核处理器平台下路由器报文转发时路由查找速度慢的“瓶颈”问题，提出了一种基于分割的多分枝 Trie树的并行路由查找算法。该算法将一棵多分枝 Trie 树根据处理器的核数分割成若干子树，每棵子树又构成一棵单独的多分枝Trie树，子树中取消了前缀查找，采取组成一个大中间节点的方式，在中间节点之间采用固定步长查询，中间节点内部采用二进制Trie树来表示。实验结果表明，该算法具有访存次数少、查询速度快、占用存储空间少和更新开销小等特点，同时适用于IPv4和 IPv6地址。
위해결재다핵처리기평태하로유기보문전발시로유사조속도만적“병경”문제，제출료일충기우분할적다분지 Trie수적병행로유사조산법。해산법장일과다분지 Trie 수근거처리기적핵수분할성약간자수，매과자수우구성일과단독적다분지Trie수，자수중취소료전철사조，채취조성일개대중간절점적방식，재중간절점지간채용고정보장사순，중간절점내부채용이진제Trie수래표시。실험결과표명，해산법구유방존차수소、사순속도쾌、점용존저공간소화경신개소소등특점，동시괄용우IPv4화 IPv6지지。
To break the bottleneck of slow routing lookup in packet forwarding on a multi-core processor platform,this paper presents a parallel routing lookup algorithm based on the divided multi-branch trie.This algorithm divides a multi-branched trie into several subtrees according to the number of processor cores,and each of them becomes a separate multi-branched trie.In the subtrees,it abolishes prefix lookup and composes a large intermediate node and adopts fixed-step query between the inter-mediate nodes,within which it uses the binary tries for expression.The experimental results show that this algorithm is char-acteristic of small number of memory access,fast looking-up speed,small memory space occupation and small update overhead and furthermore,it is applicable to both IPv4 and IPv6 addresses.