光通信研究Issue(5)：19-21,29,4.DOI:10.13756/j.gtxyj.2014.05.007
基于分割多分枝Trie树的并行路由查找算法
Divided multi-branched trie-based parallel routing lookup algorithm
雷升平 1吉萌2
作者信息
- 1. 光纤通信技术和网络国家重点实验室，武汉 430074
- 2. 武汉烽火网络有限责任公司，武汉 430074
- 折叠
摘要
Abstract
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.关键词
并行路由查找算法/Trie树/多核处理器/前缀匹配Key words
parallel routing lookup algorithm/trie/multi-core processor/prefix match分类
信息技术与安全科学引用本文复制引用
雷升平,吉萌..基于分割多分枝Trie树的并行路由查找算法[J].光通信研究,2014,(5):19-21,29,4.
