-
-
手机阅读
1 常用路由查找算法
线性表算法基本方案：基本思想是对于IPv4，把地址分成两部分，第一部分24bit，第二部分8bit，两部分均由线性表组成。两个线性表分别用于存储第0级扩展树和第1级扩展树。其中最高位为0表示查找结束，其他位表示下一跳地址信息；否则必须继续查找。
算法性能评估：优点——最差情况只需要读两次内存。由于这两次读取在不同的内存中可以使用流水线方法；算法简单，易于硬件实现。缺点——内存利用不充分；转发表的更新比较麻烦，更新一个前缀可能需要多次访问内存。
基于前缀区间的算法 基本方案：将0～232-1视为IP地址的全空间，地址前缀视为IP地址空间中的一段连续区域，并用范围取值来编码，把最长匹配前缀问题转化为寻找包含地址的最窄区间的问题。
算法性能评估：优点——性能与地址的长度关系不是很密切，所以对前缀长度有很好的扩展性。缺点——转发表不支持动态更新。
基于前缀长度的二分查找算法基本方案：把前缀按长度分类，长度相同的前缀放到同一集合中，每个集合组成—个Hash表，用—个阵列来存储这些Hash表。进行最长前缀匹配时，在各个集合中寻找分组目的地址的匹配前缀，首先在长度最长的非空前缀集合中进行，若成功则停止查找；否则转至尚未查找的非空前缀集合中前缀长度最大的集合继续进行。
算法性能评估：优点——该算法具有很好的扩展性，而其他方法对于扩展到IPv6是很困难的。缺点——某些前缀集合中的前缀数量大，找到一个无冲突的Hash函数很困难。
基于Trie的路由查找算法 基本方案：通过Trie结构相关技术构造Trie树，以此Trie树为基础进行基于地址前缀长度的查找。
算法性能评估：基于Trie树的算法不仅具有较好的查找速度、空间复杂度和时间复杂度，而且能适应不断提高的路由器陛能的要求。
2 基于二分查找Trie的路由查找算法
在分析现有算法的基础上，本文提出了一种新颖的路由查找算法—基于二分查找Trie的路由查找算法。该算法的特点是采用了二分查找算法的思想，查找速度快，对前缀长度的扩展性好；继承了基于Trie算法的特点，支持转发表的动态更新，更新速度快；结合了基于前缀长度二分查找的优点，并利用部分IP地址为索引避免了使用Hash函数。
2.1 算法基本原理
在论述前，首先对有关定义加以说明。
步长：第k(k＞1)次查询的前缀长度Lk与第k-1次查询的长度Lk-1的差值的绝对值△L=∣Lk-Lk-1∣称为第k次查询的步长L0=0。
查询方向：假设第K次查询的网络前缀长度为Lk，第K-1次查询的网络前缀为Lk-1，如果Lk-1<Lk测称为k-1次查询结果的方向是正向的(该节点为其父节点的右节点)，否则为反向(该节点为其父节点的左节点)。
节点表示为NL,i，其中L表示该节点代表前缀的长度，i为节点编号。
节点数组的表项表示为EL,i,j，其中L和i的定义与节点中的定义相同，j为节点数组索引值。
节点编号长度Li：该长度与节点所代表的前缀长度有关，根节点的编号长度为0，节点如果是其父节点的左节点，则该节点的节点编号长度与其父节点相同；如果是右节点，则该节点的节点编号长度等于其父节点所代表前缀的前缀长度。例如节点NW／2,i的Li=0，其左节点的节点编号长度为0，右节点的节点编号长度为W／2。
节点编号值i：IP地址(用二进制表示)前Li位的值。
索引长度Lj=节点代表的前缀长度L-节点编号长度Li。
索引值j：IP地址第Li+1位到第Li+Lj位所代表的值，该值既与前缀有关又与节点有关，对于不同的节点即使是相同的前缀其索引值也不同。
查找级Le：表示节点所处的查找级。
基于Trie的路由查找算法采用顺序比较IP地址位数的方法，所以访问存储器次数较多，查找速度慢，如果采用二分的方法将会提高查找速度，基于二分查找Trie的路由查找算法的前缀长度查询顺序如图1所示。对于前缀长度为W的IP地址，首先利用IP地址的前W／2 bit与所有前缀长度为W／2前缀进行匹配，如果匹配成功则用IP地址的W／2+1～W／2+W／4 bit为索引，查找前缀长度为W／2+W／4的其前W／2 bit与该IP地址相同的前缀；如果匹配失败则取IP地址的前W／4 bit与所有前缀长度为W／4前缀进行匹配。依次类推，直到查询结束。
 |
每个节点的数据结构由节点头和节点数组组成。节点头的数据结构：backward(B)表示该节点是否有左分支；backward_address(BA)在backward有效时表示左分支节点的地址。节点数组的数据结构：prefix_valid(PV)表示该表项是否是有效节点；forward(F)表示该表项是否有右分支；backtrack(T)表示该节点是否存在回溯，关于该标记将在后文中详细描述；nexthop_address(HNA)在prefix_valid或backtrack有效时表示该表项对应的下一条地址信息；forward_address(FA)在forward有效时表示该表项对应的右节点的地址。
 |
该方案实际上是一种特殊的Trie结构，每个节点包含—个节点头和一个节点数组。节点数组的大小和与该节点表示前缀的长度有关，处于第Le级的节点其数组大小为2W／a，a=2Le，所以处于第一级的节点数组最大，为2W／a，第一级节点只有一个，为NW／2,0称为根节点，以后每一级节点数组的大小是前一级的1／2。节点头指向该节点的方向节点(如果方向节点存在)，每个节点最多包含一个反向节点(左节点)；每个节点数组指向一个该节点的正向数组，所以最多包含2W／a个正向节点(右节点)。
如果把一个前缀长度为W／2的前缀加入转发表，该前缀在第一级的索引值j等于前缀1～W／2 bit所代表的值，把第一级节点数组第j个表项的prefix_valid置为有效(置为1)，同时将nexthop_address设置为该前缀对应的下—跳地址。
如果把一个前缀的长度为W／2+W／4的前缀加入转发表，该前缀在第一级的编号长度Li=0，编号值为i=0，索引长度Lj=W／2，索引值jW／2等于前缀1～W／2 bit所代表的值。该前缀在前缀长度为3W／4的第二级节点的编号长度Li=W／2，编号值i等于前缀1～W／2 bit所代表的值，索引长度Lj=W／4，索引值j3W／4等于前缀的第W／2+1～3W／4 bit所代表的值。首先把第一级节点第jW／2表项的forward置为有效，申请一个前缀长度为3W／4的第二级节点N3W／4,i，其中i为第二级节点的编号，把该节点的地址写入第一级节点的：forward_address。把第二级节点的第j3W／4个表项的prefix_valid置为有效，将nexthop_address设置为该前缀对应的下一跳地址。
如果把一个前缀的长度为W／4的前缀加入转发表，把第一级节点头backword置为有效，申请一个前缀长度为W／4的第二级节点NW／4,i，该前缀在第二级节点的编号长度Li=0，编号值i=0，索引长度Lj=W／4，索引值j等于前缀1W／4 bit所代表的值。把第二级节点的地址写入第一级节点头中的backword_address，第二级节点数组第j个表项的prefix_valid置为有效，将nexthop_address设置为该前缀对应的下一跳地址。
2.2 IPv6路由查找的方案
由于IPv6的地址长度为128bit，如果采用该算法应用于IPv6，第一级节点数组包含264个表项，第二级的节点数组包含232个表项，所需的存储空间过大。本文对该算法进行改进，通过增加3个数组Table-64、Table-32和Table-96使其适应IPv6路由查找，查找结构如图3所示。Table-64中索引项存放的是长度大于等于64bit的路由前缀的前64bit；Table-96的索引表项长度为96bit，存放长度大于等于96bit的前缀的前96bit；Table-32的索引表项长度为32bit,存放长度大于32bit小于64bit的前缀的前32bit。这3个表可以通过CAM实现，通过两次查询剩下的前缀按长度分成4类：1～31bit、33～63bit、65～95bit和97～128bit。
 |
Table-32、Table-64和Table-96表项的数据结构：prefix_valid、forward、backtrack、nexthop_address和forward_address。 3个数组均不再包含节点头。其中forward_address表示的意义与原算法有所不同，Table_64中的forward_address指向的是一个Trie的入口地址，该Trie由前缀长度大于64bit小于96bit，且前64bit与该表项索引相同的前缀构成的Trie；Table-32中forward_address指向的Trie由前缀长度大于32bit小于64bit，且前32bit与该表项索引相同的前缀构成的；Table-96中forward_address指向的Trie由前缀长度大于32bit小于96bit，且前96bit与该表项索引相同的前缀构成Trie。
2.3 性能分析
查找速度快：本算法最坏的情况下需要访问存储器的次数为log2W，所以对于IPv4来说完成一次查找最多访问存储器5次，对于IPv6地址查找最多只需要7次。本算法是现有算法中查找速度较陕的。
对前缀长度的扩展性好：在现有路由查找算法中，只有基于前缀区间的算法和基于前缀长度的二分查找算法扩展性较好，但基于前缀区间的算法随着网络前缀数量的增加查找性能下降，而后者则不会出现这种问题，本算法采用基于前缀长度的二分查找算法的思想，对前缀长度的扩展性好。
支持转发表的动态更新：支持转发表的动态更新使得该算法的更新速度快。
3 结束语
本文在分析已有算法优缺点的基础上提出了一种新颖的性能良好的路由查找算法—基于二分查找Trie的路由查找算法，该算法具有查找、更新速度快，对前缀长度扩展性好的特点，给出了算法的实现步骤及算法在IPv6下的实现方案，对算法性能进行了分析，结果显示该算法是一种性能良好的快速路由查找算法。