路由原理与技术第8章路由查询

《路由原理与技术第8章路由查询》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章路由查询北京邮电大学网络技术研究院下一代互联网技术研究中心第一部分概述影响IP网络性能的关键因素链路速度路由器的吞吐量包转发速率对路由变化的快速适应性采用光纤等技术提高链路速度在路由器中采用大容量的交换结构以提高吞吐量采用高效的路由查询算法和硬件路由查询方案提高包转发速率（路由查询）优化各种动态路由协议解决方案路由查询定义设分组的目的地址为D，包含长度为W的比特数。设路由前缀为P，包含的比特数为0～W，L(P)表示前缀长度。地址D匹配前缀P的含义：地址D的前L(P)位比特值与前缀P完全相同。给定一个路由前缀集合PA，集合含有N个路由前缀，到达分组的目的地

2、址为D，路由的最长前缀匹配查找定义为：在前缀集合PA中搜索到的前缀Pm满足：目的地址D匹配前缀Pm；在集合PA中不存在其他的前缀P，满足D匹配P，且L(P)>L(Pm)为什么是最长前缀匹配而不是精确匹配CIDR等机制的引入：IP地址是无类别的，从IP地址不能判断出其网络前缀长度；IPv6单播地址也是无类别的。最长前缀匹配给路由查询带来很大的困难，因为不仅要考虑前缀的值，还要考虑前缀的长度。传统的关键字查找算法不能直接用于路由查询。W.Doeringer,G.Karjoth,andM.Nassehi,“Routingonlongestmatchingprefixe

3、s,”IEEE/ACMTrans.Networking,vol.4,pp.86–97,Feb.1996.路由查询算法分类按照采用的数据结构和实现方式，大致可以分为：基于检索树（Trie）查找基于硬件TCAM查找分段查找哈希表查找Cache命中查找等。按照路由查询的依据，可以分为：基于路由前缀值的查找基于路由前缀长度的查找路由查询算法评价标准时间复杂度（查找速度）空间复杂度（占用的存储空间）更新复杂度（增加、删除、变更路由表条目时，路由表的更新速度）可扩展性注意，上述复杂度一般是指最坏情况下的复杂度。第二部分各种路由查询算法路由前缀值的线性查找所有路由前缀按照线

4、性链表的方式组织。查询时要遍历路由表中的所有表项，并记录查询过程中匹配的最长路由前缀项，一直到最后一项为止。时间复杂度O(N)，空间复杂度O(N)，插入/删除路由前缀条目的复杂度为O(1)。如果使用有序链表，即把路由前缀按照长度大小排列，可以提高路由查询的平均速度，但更新复杂度上升。此时，时间复杂度O(N)，空间复杂度O(N)，插入/删除路由前缀条目的复杂度为O(N)。基本的二叉检索树（Trie）路由前缀按照二叉树的结构来组织。树中的每个节点含有路由前缀的1比特信息，并根据下一个比特生成两个子节点。在树的非空节点处，存放该节点对应的下一跳信息。在进行最长前缀匹配

5、时，首先根据路由前缀的比特信息遍历二叉树，达到最终匹配的叶子节点处，最后读出存储在叶子节点中的下一跳路由信息。基本二叉检索树的一个例子在查找的过程中，有可能出现多个前缀匹配的情况，如上图中的(A,C)和(B,D,E)，这时要选择最长的前缀。在查找时要记录当前最匹配的路由前缀，一直到叶子节点或者节点没有合适的分支为止。例如，对于地址111*，按照上图的例子，当查到B时，由于是匹配的，所以就记录下相应的信息，继续向下查询，没有更匹配的路由前缀，所以此时B就是最长匹配的路由前缀。这种查找实际上是地址前缀长度空间的线性查找。因为是按照单个比特的顺序来查询的。很显然，使用

6、基本的二叉检索树进行路由查询时，时间复杂度与树的深度（在这种算法中就等于路由前缀的最大长度）有关。如果最大可能的路由前缀长度为W，则最坏情况下的查找时间复杂度为O(W)。最坏情况下的空间复杂度为O(N*W)。更新复杂度为O(W)。更新时需要先进行查找，找到之后进行相应的增删操作就可以了（包括中间节点和叶子节点两种情况）。在IPv4中最多需要32次查找，在IPv6中最多需要128次查找。路径压缩Trie该算法是对基本二叉检索树的改进，最早起源于Patricia算法，后来Sklower对Patricia算法做了改进，使之可以用于路由查询。其基本思想是去掉输出为1的中

7、间节点，压缩叶子节点的路径，将叶子节点提升到最近一级父节点的下一层。这样，每个中间节点都有两个输出。由于有可能去掉了一些包含路由前缀的中间节点，所有某些节点会有多个路由前缀。由于去掉了一些节点，某些比特将被忽略，所以节点要维护一个变量，用于维持下一个要检查的比特位。路径压缩Trie对稀疏的基本Trie有明显的压缩效果，但对稠密的则作用不大。路径压缩Trie不能从本质上降低树的深度，在最坏情况下它的时间复杂度仍然为O(W)。路径压缩Trie的空间复杂度为O(N)，因为这种Trie中N个叶子节点对应N－1个内部节点。路径压缩Trie更新算法的复杂度也是O(W)，其动

8、态性比基本Trie要差，