基于多分支优先级树的IP路由查找算法

【前言】基于多分支优先级树的IP路由查找算法由文秘帮小编整理而成，但愿对你的学习工作带来帮助。Key words： IP address lookup； multibit trie tree； longest matching prefix； MultiBit Priority Tries （MBPT） tree 0引言 随着网络流量的不断增长，迫使路由器必须能够按照IP分组中的目的地址快速地进行转发分组，而转发分组中的关键是读取报文的目标地址并...

摘要：针对现有路由表查找方法效率低的问题，提出了一种基于多分支优先级树的数据查找算法。该算法将优先级较高的前缀依次存储在原多分支树的虚节点上，将需要进行扩展的前缀存储在辅助存储结构中，从而在路由查找时，该方法可在内部节点找到最长前缀匹配而无需查找到叶子节点，同时避免了在路由表更新时对路由表的重建。仿真结果表明，提出的查找算法能够有效减少在对路由表查找、插入和删除操作所需的内存访问次数，并大幅度地提高路由查找及其更新速率。

关键词：ip路由查找；多分支tire树；最长前缀匹配；多分支优先级树

中图分类号： TP393.071

文献标志码：A

Abstract： Concerning the low efficiency of present methods of IP lookup， a new data lookup algorithm based on MultiBit Priority Tries （MBPT） was proposed in this paper. By storing the prefixes with higher priority in dummy nodes of multibit tries in proper order and storing the prefixes for being extended in an auxiliary storage structure，this algorithm tried to make the structure find the longest matching prefix in the internal node instead of the leaf node. Meanwhile， the algorithm avoided the reconstruction of routertable when it needed to be updated. The simulation results show that the proposed algorithm can effectively minimize the number of memory accesses for dynamic routertable operations， including lookup， insertion and deletion， which significantly improves the speed of routertable lookup as well as update.

Key words： IP address lookup； multibit trie tree； longest matching prefix； MultiBit Priority Tries （MBPT） tree

0引言

随着网络流量的不断增长，迫使路由器必须能够按照IP分组中的目的地址快速地进行转发分组，而转发分组中的关键是读取报文的目标地址并且在路由表中查找与之匹配的表项，最终根据该表项所指出的端口将报文转发出去[1]。因此，路由表的结构和高效的路由查找算法是实现高速分组转发的主要因素。此外，由于网络是一个动态系统，新的路由器或子网的加入会导致核心路由器更新速度较快。因此，一种高效的路由查找算法不仅应满足快速的路由查找，还应该具有快速的路由更新能力。同时，在设计IP路由查找算法时还应尽可能用较小的存储空间来存储较多的路由前缀以缓解路由表的持续增大所带来的问题[2]。

为了解决路由表查找效率低的问题，研究者提出了不同结构的路由表：文献[3]提出了一种基于前缀长度的二分查找，在进行查找匹配时会向更长的前缀进行匹配，但是当不匹配时，不能确定是向更长的方向还是更短的方向进行匹配，引入marker来能保证获得正确结果，但会导致增量更新困难；文献[4]中提到一种基于地址区间的查找算法，该算法主要是将查找前缀p的最长前缀匹配转化为查找包含前缀p的最窄地址区间，但是当插入或者删除某一个前缀时可能会影响多个原有的地址区间，因此该结构存在的最大问题是增量更新困难。为解决二进制trie树中虚节点所带来的空间资源浪费问题，Berger[5]提出了前缀树（prefixtrie）存储结构，该结构按照前缀长度必须大于等于该节点所在的层数这一特点将前缀依次存储在前缀树中以减少存储空间，但是该算法的最大缺点是进行最长前缀匹配必须要比较到叶子节点且每次只能比较一个前缀。文献[6-7]主要是为了实现最长前缀快速匹配将相对较长的前缀存储在上层节点，但是此结构需要较大的存储空间。

为提高二进制trie树查找速度，研究者提出了基于多分支trie树的LCtrie[8]和受控前缀扩展算法[9]。多分支trie树是通过增加每次查找时所比较的比特位数（步长）来实现快速查找，但是在进行查找操作时必须要一直比较到叶子节点，此方法的前缀扩展同样会导致资源浪费问题[4]。

针对上述相关研究的局限性，本文提出了一种基于多分支优先级（MultiBit Priority Tries， MBPT）树的路由查找结构，该结构不但解决了多分支树前缀扩展所带来的资源浪费问题，同时可有效地弥补在多分支树进行路由查找时必须要比较到叶子节点这一缺陷。

1路由查找算法分析

1.1二进制trie树

二进制trie树是一种最为普遍的路由查找算法结构，文献[10-14]中提到的算法均为此基础上改进的经典算法。每一个与路由相关的转发信息存储在二进制树的一个节点，且此转发信息对应的前缀长度与其所在的层数是一致的。

二进制trie树如图1所示，深色节点表示有效的前缀信息，白色节点表示空白节点（虚节点）。二进制trie树结构简单且易于实现，同时还具有良好的可扩展性，但是此结构具有以下不足：此结构中含有许多虚节点，此类节点不包含任何路由信息，降低了内存利用率；且在进行查找操作时，即使最长匹配前缀在中间节点，也要从根节点一直匹配到叶子节点，导致搜索效率降低。

本实验主要从以下指标评价算法性能：

1）路由表查找操作时，最坏情况下和平均情况下内存访问次数；

2）路由表更新操作时，最坏情况下和平均内存访问次数；

3）路由表所需内存地址空间大小。

在查找操作和路由表更新操作时，本文从总数据中随机地取出15%的前缀进行查找和更新用来统计在进行插入和更新操作时最坏情况下和平均情况下所需要的内存访问次数。

3.3仿真结果分析

由表2可以看出对于路由表查找操作，2MBPT算法的平均内存访问次数为12.51次，相对于二分树和前缀树算法，本文算法较优的原因是引入了优先级前缀和PT结构，PT结构有效地降低了树的高度，优先级前缀能够在中间节点进行最长前缀匹配，此外，在最坏情况下，本文算法的最大内存访问次数为16次，明显优于其他3种算法；对于路由表更新操作，由于引入了优先级前缀和PT结构，因此无论是平均内存访问次数还是最坏情况下的最大内存访问次数，本文算法均明显优于其他3种算法；对于所需内存地址空间，本文提出的算法相对于二分树和前缀树算法略有增加，其原因是增加了辅助信息（如：为了区分是优先级节点还是常规节点而增加的辅助标识信息）以及指向PT的S指针等因素。但是就综合性能而言，本文提出的KMBPT算法在总体性能上有明显提升。图6和图7分别为4种算法的查找操作和更新操作的平均内存访问次数直观图。

4结语

针对传统路由查找算法效率低的问题，本文综合考虑了动态更新、查找速度、更新速度和内存占用率等因素，提出了多分支优先级（KBMPT）树路由查找算法，该算法在多分支树的基础上引进了优先级前缀和辅助节点S，不但保留了多分支树自身的查找速度快的特点，而且由于优先级前缀和S节点的引入，进一步提高了查找速度和空间利用率。实验数据表明，本文提出的算法具有动态更新、查找速度快、更新速度快以及内存占用率高等优点。

参考文献：

[1]XU K， XU M， WU J， et al. Survey on routing lookup algorithms [J]. Journal of Software， 2002， 13（1）： 42-50.

[2]TAN M， GAO L， GONG Z. A survey of IP routing lookup algorithms [J]. Computer Engineering and Science， 2006， 28（6）： 87-91.

[3]WALDVOGEL M， VARGHESE G， TURNER J， et al. Scalable high speed IP routing lookups [J]. ACM SIGCOMM Computer Communication Review， 1997， 27（4）： 25-36.

[4]RUIZSNCHEZ M ， BIERSACK E W， DABBOUS W. Survey and taxonomy of IP address lookup algorithms [J]. IEEE Network： the Magazine of Global Internetworking， 2001， 15（2）： 8-23.

[5]BERGER M. IP lookup with low memory requirement and fast update [C]// HPSR 2003： Proceedings of the 2003 Workshop on High Performance Switching and Routing. Piscataway， NJ： IEEE Press， 2003： 287-291.

[6]HSIEH S Y， HUANG Y L， YANG Y C. Multiprefix trie： a new data structure for designing dynamic routertables [J]. IEEE Transactions on Computers， 2011， 60（5）： 693-706.

[7]HSIEH S Y， YANG Y C. A classified multisuffix trie for IP lookup and update [J]. IEEE Transactions on Computers， 2012， 61（5）： 726-731.

[8]NILSSON S， KARLSSON G. IPaddress lookup using LCtries [J]. IEEE Journal on Selected Areas in Communications， 1999， 17（6）： 1083-1092.

[9]SRINIVASAN V， VARGHESE G. Faster IP lookups using controlled prefix expansion [J]. ACM SIGMETRICS Performance Evaluation Review， 1998， 26（1）： 1-10.

[10]SONG H， TURNER J， LOCKWOOD J. Shape shifting tries for faster IP route lookup [C]// ICNP 2005： Proceedings of the 13th IEEE International Conference on Network Protocols. Piscataway， NJ： IEEE Press， 2005： 358-367.

[11]EATHERTON W. Fast IP lookup using tree bitmap [D]. St Louis： Washington University，1999.

[12]LIM H， YIM C， SWARTZLANDER E E. Priority tries for IP address lookup [J]. IEEE Transactions on Computers， 2010， 59（6）： 784-794.

[13]DEGERMARK M， BRODNIK A， CARLSSON S， et al. Small forwarding tables for fast routing lookups [J]. ACM SIGCOMM Computer Communication Review， 1997， 27（4）： 3-14.

[14]HAO G， LI G. A fast routing lookup algorithm based trie [J]. Microelectronics and Computer， 2011， 28（6）： 163-167.

[15] BGP Table [EB/OL]. [20130715]. http：//bgp.potaroo，net/.