快速路由查找算法的研究

1、    快速路由查找算法的研究随着因特网中主机数不断增加，目前制约路由器性能的问题主要有3个：路由查找、分组交换和输出调度。一些性能良好的解决交换和输出调度的方案已经提出，研究路由查找算法，提高路由查找速度成为进一步提高路由器性能的关键。1常用路由查找算法线性表算法基本方案：基本思想是对于IPv4，把地址分成两部分，第一部分24bit，第二部分8bit，两部分均由线性表组成。两个线性表分别用于存储第0级扩展树和第1级扩展树。其中最高位为0表示查随着因特网中主机数不断增加，目前制约路由器性能的问题主要有3个：路由查找、分组交换和输出调度。一些性能良好的解决

2、交换和输出调度的方案已经提出，研究路由查找算法，提高路由查找速度成为进一步提高路由器性能的关键。1 常用路由查找算法线性表算法基本方案：基本思想是对于IPv4，把地址分成两部分，第一部分24bit，第二部分8bit，两部分均由线性表组成。两个线性表分别用于存储第0级扩展树和第1级扩展树。其中最高位为0表示查找结束，其他位表示下一跳地址信息；否则必须继续查找。算法性能评估：优点最差情况只需要读两次内存。由于这两次读取在不同的内存中可以使用流水线方法；算法简单，易于硬件实现。缺点内存利用不充分；转发表的更新比较麻烦，更新一个前缀可能需要多次访问内存。基于前缀区间的算法 基本方案：将0232-1视为

3、IP地址的全空间，地址前缀视为IP地址空间中的一段连续区域，并用范围取值来编码，把最长匹配前缀问题转化为寻找包含地址的最窄区间的问题。算法性能评估：优点性能与地址的长度关系不是很密切，所以对前缀长度有很好的扩展性。缺点转发表不支持动态更新。基于前缀长度的二分查找算法基本方案：把前缀按长度分类，长度相同的前缀放到同一集合中，每个集合组成个Hash表，用个阵列来存储这些Hash表。进行最长前缀匹配时，在各个集合中寻找分组目的地址的匹配前缀，首先在长度最长的非空前缀集合中进行，若成功则停止查找；否则转至尚未查找的非空前缀集合中前缀长度最大的集合继续进行。算法性能评估：优点该算法具有很好的扩展性，而其

4、他方法对于扩展到IPv6是很困难的。缺点某些前缀集合中的前缀数量大，找到一个无冲突的Hash函数很困难。基于Trie的路由查找算法 基本方案：通过Trie结构相关技术构造Trie树，以此Trie树为基础进行基于地址前缀长度的查找。算法性能评估：基于Trie树的算法不仅具有较好的查找速度、空间复杂度和时间复杂度，而且能适应不断提高的路由器陛能的要求。2 基于二分查找Trie的路由查找算法在分析现有算法的基础上，本文提出了一种新颖的路由查找算法基于二分查找Trie的路由查找算法。该算法的特点是采用了二分查找算法的思想，查找速度快，对前缀长度的扩展性好；继承了基于Trie算法的特点，支持转发表的动态

5、更新，更新速度快；结合了基于前缀长度二分查找的优点，并利用部分IP地址为索引避免了使用Hash函数。2.1 算法基本原理在论述前，首先对有关定义加以说明。步长：第k(k1)次查询的前缀长度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,

6、j，其中L和i的定义与节点中的定义相同，j为节点数组索引值。节点编号长度Li：该长度与节点所代表的前缀长度有关，根节点的编号长度为0，节点如果是其父节点的左节点，则该节点的节点编号长度与其父节点相同；如果是右节点，则该节点的节点编号长度等于其父节点所代表前缀的前缀长度。例如节点NW2,i的Li=0，其左节点的节点编号长度为0，右节点的节点编号长度为W2。节点编号值i：IP地址(用二进制表示)前Li位的值。索引长度Lj=节点代表的前缀长度L-节点编号长度Li。索引值j：IP地址第Li+1位到第Li+Lj位所代表的值，该值既与前缀有关又与节点有关，对于不同的节点即使是相同的前缀其索引值也不同。查找级Le：表示节点所处的查找级。基于Trie的路由查找算法采用顺序比较IP地址位数的方法，所以访问存储器次数较多，查找速度慢，如果采用二分的方法将会提高查找速度，基于二分查找Trie的路由查找算法的前缀长度查询顺序如图1所示。对于前缀长度为W的IP地址，首先利用IP地址的前W2 bit与所有前缀长度为W2前缀进行匹配，如果匹配成功则用I