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

Abstract

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

Keywords

• 并行路由查找算法;Trie树;多核处理器;前缀匹配