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

第一部分概述影响IP网络性能的关键因素链路速度路由器的吞吐量包转发速率对路由变化的快速适应性采用光纤等技术提高链路速度在路由器中采用大容量的交换结构以提高吞吐量采用高效的路由查询算法和硬件路由查询方案提高包转发速率（路由查询）优化各种动态路由协议解决方案路由查询定义设分组的目的地址为D，包含长度为W的比特数。设路由前缀为P，包含的比特数为0～W，L(P)表示前缀长度。地址D匹配前缀P的含义：地址D的前L(P)位比特值与前缀P完全相同。给定一个路由前缀集合PA，集合含有N个路由前缀，到达分组的目的地址为D，路由的最长前缀匹配查找定义为：在前缀集合PA中搜索到的前缀Pm满足：目的地址D匹配前缀Pm；在集合PA中不存在其他的前缀P，满足D匹配P，且L(P)L(Pm)为什么是最长前缀匹配而不是精确匹配CIDR等机制的引入：IP地址是无类别的，从IP地址不能判断出其网络前缀长度；IPv6单播地址也是无类别的。最长前缀匹配给路由查询带来很大的困难，因为不仅要考虑前缀的值，还要考虑前缀的长度。传统的关键字查找算法不能直接用于路由查询。W.Doeringer,G.Karjoth,andM.Nassehi,“Routingonlongestmatchingprefixes,”IEEE/ACMTrans.Networking,vol.4,pp.86–97,Feb.1996.路由查询算法分类按照采用的数据结构和实现方式，大致可以分为：基于检索树（Trie）查找基于硬件TCAM查找分段查找哈希表查找Cache命中查找等。按照路由查询的依据，可以分为：基于路由前缀值的查找基于路由前缀长度的查找路由查询算法评价标准时间复杂度（查找速度）空间复杂度（占用的存储空间）更新复杂度（增加、删除、变更路由表条目时，路由表的更新速度）可扩展性注意，上述复杂度一般是指最坏情况下的复杂度。第二部分各种路由查询算法路由前缀值的线性查找所有路由前缀按照线性链表的方式组织。查询时要遍历路由表中的所有表项，并记录查询过程中匹配的最长路由前缀项，一直到最后一项为止。时间复杂度O(N)，空间复杂度O(N)，插入/删除路由前缀条目的复杂度为O(1)。如果使用有序链表，即把路由前缀按照长度大小排列，可以提高路由查询的平均速度，但更新复杂度上升。此时，时间复杂度O(N)，空间复杂度O(N)，插入/删除路由前缀条目的复杂度为O(N)。基本的二叉检索树（Trie）路由前缀按照二叉树的结构来组织。树中的每个节点含有路由前缀的1比特信息，并根据下一个比特生成两个子节点。在树的非空节点处，存放该节点对应的下一跳信息。在进行最长前缀匹配时，首先根据路由前缀的比特信息遍历二叉树，达到最终匹配的叶子节点处，最后读出存储在叶子节点中的下一跳路由信息。ABDE000011C1A0*B1*C001*D10*E110*基本二叉检索树的一个例子在查找的过程中，有可能出现多个前缀匹配的情况，如上图中的(A,C)和(B,D,E)，这时要选择最长的前缀。在查找时要记录当前最匹配的路由前缀，一直到叶子节点或者节点没有合适的分支为止。例如，对于地址111*，按照上图的例子，当查到B时，由于是匹配的，所以就记录下相应的信息，继续向下查询，没有更匹配的路由前缀，所以此时B就是最长匹配的路由前缀。这种查找实际上是地址前缀长度空间的线性查找。因为是按照单个比特的顺序来查询的。很显然，使用基本的二叉检索树进行路由查询时，时间复杂度与树的深度（在这种算法中就等于路由前缀的最大长度）有关。如果最大可能的路由前缀长度为W，则最坏情况下的查找时间复杂度为O(W)。最坏情况下的空间复杂度为O(N*W)。更新复杂度为O(W)。更新时需要先进行查找，找到之后进行相应的增删操作就可以了（包括中间节点和叶子节点两种情况）。在IPv4中最多需要32次查找，在IPv6中最多需要128次查找。路径压缩Trie该算法是对基本二叉检索树的改进，最早起源于Patricia算法，后来Sklower对Patricia算法做了改进，使之可以用于路由查询。其基本思想是去掉输出为1的中间节点，压缩叶子节点的路径，将叶子节点提升到最近一级父节点的下一层。这样，每个中间节点都有两个输出。由于有可能去掉了一些包含路由前缀的中间节点，所有某些节点会有多个路由前缀。由于去掉了一些节点，某些比特将被忽略，所以节点要维护一个变量，用于维持下一个要检查的比特位。BDEA0*B1*C001*D10*E110*A/CABDE000011C1A0*B1*C001*D10*E110*路径压缩Trie对稀疏的基本Trie有明显的压缩效果，但对稠密的则作用不大。路径压缩Trie不能从本质上降低树的深度，在最坏情况下它的时间复杂度仍然为O(W)。路径压缩Trie的空间复杂度为O(N)，因为这种Trie中N个叶子节点对应N－1个内部节点。路径压缩Trie更新算法的复杂度也是O(W)，其动态性比基本Trie要差，因为当需要加入或者删除叶子节点时，会导致其对应的若干条路径上的叶子节点位置发生变化。这种算法在BSD系统上得到了实现（Radix树），并随着BSD的推广而得到广泛应用。多比特检索树（Trie）在基本的二叉检索树中每次检查一个比特，即一级对应1个比特；如果让每一级对应多个比特，就可以大大降低树的深度。也就能够降低路由查询的时间复杂度。每一级对应的比特数被称为查找步宽。同一级的步宽可以一样，也可以不一样。前者实现起来比较简单，但浪费存储空间，后者实现复杂一些，但是会节省一定的存储空间。因为一次查找多个比特，因此不能处理任意长度的路由前缀，一般要使用前缀扩展。每一级的步宽都是2第一级的步宽是2第二级三个节点步宽是2，一个节点步宽是1对于上图中绿色部分，如何应用多比特检索？前缀扩展：将一条较短的路由前缀展开成多条较长的路由前缀集，这些前缀集的转发信息就是原来地址前缀所对应的转发信息。也就是扩展后的路由前缀要继承原来前缀的转发信息。例如，1*可以扩展为10*和11*。对于Trie中不能直接应用多比特树的地方，可以先进行前缀扩展，使应用多比特树的局部成为一个满的子树。101*111*1010*1011*1110*1111*由于步宽大于等于1，使检索树的深度明显降低，所以多比特检索树的时间复杂度比基本二进制Trie或路径压缩Trie要低，具体的数值与每一级步宽有关。当每一级步宽都是K时（这是多比特检索树中最简单的情况），时间复杂度为O(W/K)。时间复杂度降低的代价就是空间复杂度的上升，每一个中间节点都需要包含2k个指针（每一级步宽都是K），最差情况下每加入一个新前缀，需要插入W/K个中间节点，从而需要占用空间O(2k*W/K)，所以空间复杂度为O(N*2k*W/K)。更新时需要进行一次路由查找，然后更新节点的指针，最差情况下需要更新2k-1指针，所以更新复杂度为O(2k＋W/K)。对于多比特检索树来说，当步宽为1时，就成为基本二叉检索树或路径压缩树，当步宽达到W时，时间复杂度为O(1)，但空间复杂度变为O(2W)。很显然，多比特检索树的主要问题就是引入了很多冗余路由前缀，占用了大量存储空间，所以对它的优化是研究的一个重点，例如有些人就提出了步宽选择策略，也有人提出了一些压缩算法。实际进行压缩时可以考虑互联网地址分布的特点，例如长度16～24之间的前缀数最多。叶子扩展的概念0*110*10*111*0*11*1*111*路由前缀长度空间的二分查找Trie树算法的实质是地址前缀长度空间的线性查找：先检查第1个（1－k）个比特，再检查第2个（k+1－2k）个比特，一直到路由前缀的最大长度为止。文献“Scalablehigh-speedprefixmatching，MarcelWaldvogel,GeorgeVarghese,JonTurner,BernhardPlattner，ACMTransactionsonComputerSystems,2001”提出了地址前缀长度空间的二分查找法。基本思想是把所有路由前缀按照其长度分为不同的前缀集合，每个前缀集合内采用哈希算法查找；查询时，从长度位W/2的集合开始，采用二分查找法。W/23W/45W/87W/8W/43W/8W/84657231图中节点对应的是前缀集合，而不是某个或某几个比特位为了保证该算法的正确性，需要引入一个被成为Marker的表项。考虑下面的例子。有4个地址前缀：0*、1*、00*、110*。现查找110*。0*1*00*110*2130*1*00*11*(Marker)110*213路由前缀长度空间的二分查找在路由查询方面的时间复杂度为O(logW)，对IPv4来说，最多需要5次查询，对IPv6来说，最多需要7次查询。对于每个前缀，最多可能需要logW个Marker，因此，算法的空间复杂度为O(N*logW)。路由更新比较麻烦，其复杂度为O(N*logW)，因为最坏情况下更新一个前缀可能影响N-1个前缀，而一个前缀又有可能对应logW个Maker。哈希算法也是该算法中的关键问题。TCAMTCAM（TernaryContentAddressMemory）是一种新型的存储器，存放一系列路由表项，为到来的每一个分组并行查找所有的路由前缀。因此，它的路由查询只需要一次内存访问，若有多个匹配表项，经过优先级比较后，确定路由信息。路由管理比较复杂，路由表的动态删除和更新会导致TCAM中存放大量的碎片。成本昂贵，功耗比较大，存储容量小。这实际上是一种硬件查找方法。基于分段的查找这种方案实际上是多比特检索树的具体硬件实现方案。典型的是Gupta等人提出的DIR-24-8-BASIC查找算法。DIR-24-8-BASIC算法是把IPv4地址空间分为长度分别为24和8的两部分（TBL24和TBLlong），最大内存访问次数为2，采用硬件流水线技术可以用1次内存访问。第一部分是224＝16M个表项；第二部分256个表项。因为是基于多比特检索树，因此需要进行前缀扩展。第一级中的节点携带的指针信息指示可能存在于第2级中的一棵子树。指针下一跳信息10下一跳基地址下一跳信息TBL24TBLlong偏移量缓存（Cache）策略缓存策略是指把最近查找过的目的地址和路由下一跳信息放在缓存之中，当IP分组达到时，先从缓存中查找，找不到时再执行最长前缀匹配策略。显然，数据包的相关度越大，这种方法的有效性就越高。缓存的命中率是这种策略的一个关键。由于缓存容量有限，且数据日益多样化，缓存的命中率大大降低。哈希查找哈希(Hash)算法在路由查询中应用的时候，通过查找建立的哈希索引，来找到对应的路由前缀。理论上讲，哈希算法的时间复杂度和空间复杂度都很低，但实际上很难找到一个完美的或者近似完美的哈希函数。另外，路由更新也往往会导致哈希表的重建。一般来说，把整个路由表做为一个哈希表是不切实际的，可以在局部范围内应用哈希算法。如在前缀长度空间的二分查找中，就可以在同一前缀长度的前缀集合内应用哈希算法。其他路由查询算法层压缩树地址区间的二分查找法多路和多列查询算法等第三部分路由查询算法的评测算法时间复杂度空间复杂度更新复杂度基本二叉检索树O(W)O(N*W)O(W)路径压缩检索树O(W)O(N)O(W)多比特检索树O(W/K)O(2K*N*W/K)O(W/K+2K)前缀长度空间的二分查找O(logW)O(N*logW)O(N*logW）基本算法在时间复杂度等方面的比较其他需要考虑的方面算法的可扩展性。即路由前缀长度增加后，不能使查询的复杂度大幅度上升。路由前缀长度空间的二分查找的扩展性比较好，从IPv4到IPv6后，最差情况下的查询次数从5升到7。各种基于检索树的查找算法可扩展性一般，多比特查找树可以通过增加K的方法来降低时间复杂度，但会带来空间复杂度的大幅度上升。不过也可以通过分段的方法来部分地