基于分割多分枝Trie树的并行路由查找算法

• 作者: 吉萌 雷升平
• 来源期刊: 光通信研究
• 学科: 工学
• 关键词: 并行路由查找算法 Trie树 多核处理器 前缀匹配
• 年，卷（期）: 2014,（5）
• 所属期刊栏目: 光通信系统与网络技术
• 页码范围: 19-21,29
• 页数: 4页
• 分类号: TP393.2
• 字数: 2390字
• 语种: 中文
• DOI: 10.13756/j.gtxyj.2014.05.007

摘要

为解决在多核处理器平台下路由器报文转发时路由查找速度慢的“瓶颈”问题，提出了一种基于分割的多分枝 Trie树的并行路由查找算法。该算法将一棵多分枝 Trie 树根据处理器的核数分割成若干子树，每棵子树又构成一棵单独的多分枝Trie树，子树中取消了前缀查找，采取组成一个大中间节点的方式，在中间节点之间采用固定步长查询，中间节点内部采用二进制Trie树来表示。实验结果表明，该算法具有访存次数少、查询速度快、占用存储空间少和更新开销小等特点，同时适用于IPv4和 IPv6地址。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吉萌		6	13	3.0	3.0
5	雷升平		2	5	1.0	2.0