基于分割多分枝Trie树的并行路由查找算法OA北大核心
Divided multi-branched trie-based parallel routing lookup algorithm
为解决在多核处理器平台下路由器报文转发时路由查找速度慢的“瓶颈”问题，提出了一种基于分割的多分枝 Trie树的并行路由查找算法。该算法将一棵多分枝 Trie 树根据处理器的核数分割成若干子树，每棵子树又构成一棵单独的多分枝Trie树，子树中取消了前缀查找，采取组成一个大中间节点的方式，在中间节点之间采用固定步长查询，中间节点内部采用二进制Trie树来表示。实验结果表明，该算法具有访存次数少、查询速度快、占用存储空间少和更新开销小等特点，同时适用于…查看全部>>
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…查看全部>>
雷升平;吉萌
光纤通信技术和网络国家重点实验室，武汉 430074 武汉烽火网络有限责任公司，武汉 430074
信息技术与安全科学
并行路由查找算法Trie树多核处理器前缀匹配
parallel routing lookup algorithmtriemulti-core processorprefix match
《光通信研究》 2014 (5)
19-21,29,4
评论