论文部分内容阅读
为解决在多核处理器平台下路由器报文转发时路由查找速度慢的“瓶颈”问题,提出了一种基于分割的多分枝Trie树的并行路由查找算法。该算法将一棵多分枝Trie树根据处理器的核数分割成若干子树,每棵子树又构成一棵单独的多分枝Trie树,子树中取消了前缀查找,采取组成一个大中间节点的方式,在中间节点之间采用固定步长查询,中间节点内部采用二进制Trie树来表示。实验结果表明,该算法具有访存次数少、查询速度快、占用存储空间少和更新开销小等特点,同时适用于IPv4和IPv6地址。
In order to solve the bottleneck problem of slow routing in router forwarding under multi-core processor platform, a parallel routing lookup algorithm based on partitioned multi-branch Trie tree is proposed. The algorithm divides a multi-branch Trie tree into several sub-trees according to the number of processors, and each sub-tree forms a single multi-branch Trie tree. The prefix search is canceled in the sub-tree and taken as a large- Way, using a fixed step in the middle of the node inquiries, intermediate nodes using binary Trie tree to represent. Experimental results show that the proposed algorithm has the advantages of less number of accesses, faster query speed, less storage space and less update overhead, and is suitable for both IPv4 and IPv6 addresses.