1、第一部分第一部分概述概述影响影响IP网络性能的关键因素网络性能的关键因素v链路速度链路速度v路由器的吞吐量路由器的吞吐量v包转发速率包转发速率v对路由变化的快速适应性对路由变化的快速适应性v采用光纤等技术提高链路速度采用光纤等技术提高链路速度v在路由器中采用大容量的交换结构以提高吞在路由器中采用大容量的交换结构以提高吞吐量吐量v采用高效的路由查询算法和硬件路由查询方采用高效的路由查询算法和硬件路由查询方案提高包转发速率（案提高包转发速率（路由查询路由查询）v优化各种动态路由协议优化各种动态路由协议解决方案解决方案路由查询定义路由查询定义v 设分组的目的地址为设分组的目的地址为D，包含长度为，包
2、含长度为W的比特数。的比特数。v 设路由前缀为设路由前缀为P，包含的比特数为，包含的比特数为0W，L(P)表示前缀长度。表示前缀长度。v 地址地址D匹配前缀匹配前缀P的含义：地址的含义：地址D的前的前L(P)位比特值与前缀位比特值与前缀P完完全相同。全相同。v 给定一个路由前缀集合给定一个路由前缀集合PA，集合含有，集合含有N个路由前缀，到达分组个路由前缀，到达分组的目的地址为的目的地址为D，路由的最长前缀匹配查找定义为：在前缀集，路由的最长前缀匹配查找定义为：在前缀集合合PA中搜索到的前缀中搜索到的前缀Pm满足：满足：目的地址目的地址D匹配前缀匹配前缀Pm；在集合在集合PA中不存在其他的前缀
3、中不存在其他的前缀P，满足，满足D匹配匹配P，且，且L(P)L(Pm)v为什么是最长前缀匹配而不是精确匹配为什么是最长前缀匹配而不是精确匹配CIDR等机制的引入：等机制的引入：IP地址是无类别的，从地址是无类别的，从IP地址不能地址不能判断出其网络前缀长度；判断出其网络前缀长度；IPv6单播地址也是无类别的。单播地址也是无类别的。最长前缀匹配给路由查询带来很大的困难，因为不仅要最长前缀匹配给路由查询带来很大的困难，因为不仅要考虑前缀的值，还要考虑前缀的长度。考虑前缀的值，还要考虑前缀的长度。传统的关键字查找算法不能直接用于路由查询。传统的关键字查找算法不能直接用于路由查询。W. Doering
4、er, G. Karjoth, and M. Nassehi, “Routing on longest matching prefixes,” IEEE/ACM Trans. Networking, vol. 4, pp. 8697, Feb. 1996. 路由查询算法分类路由查询算法分类v按照采用的数据结构和实现方式，大致可以分为：按照采用的数据结构和实现方式，大致可以分为：基于检索树（基于检索树（Trie）查找）查找基于硬件基于硬件TCAM查找查找分段查找分段查找哈希表查找哈希表查找Cache命中查找等。命中查找等。v按照路由查询的依据，可以分为：按照路由查询的依据，可以分为：基于路由前缀
5、值的查找基于路由前缀值的查找基于路由前缀长度的查找基于路由前缀长度的查找路由查询算法评价标准路由查询算法评价标准v时间复杂度（查找速度）时间复杂度（查找速度）v空间复杂度（占用的存储空间）空间复杂度（占用的存储空间）v更新复杂度（增加、删除、变更路由表条目时，更新复杂度（增加、删除、变更路由表条目时，路由表的更新速度）路由表的更新速度）v可扩展性可扩展性 v注意，上述复杂度一般是指最坏情况下的复杂度。注意，上述复杂度一般是指最坏情况下的复杂度。第二部分第二部分各种路由查询算法各种路由查询算法路由前缀值的线性查找路由前缀值的线性查找v所有路由前缀按照线性链表的方式组织。所有路由前缀按照线性链表的
6、方式组织。v查询时要遍历路由表中的所有表项，并记录查询过查询时要遍历路由表中的所有表项，并记录查询过程中匹配的最长路由前缀项，一直到最后一项为止。程中匹配的最长路由前缀项，一直到最后一项为止。v时间复杂度时间复杂度O(N)，空间复杂度，空间复杂度O(N)，插入，插入/删除路删除路由前缀条目的复杂度为由前缀条目的复杂度为O(1)。v如果使用有序链表，即把路由前缀按照长度大小排如果使用有序链表，即把路由前缀按照长度大小排列，可以提高路由查询的平均速度，但更新复杂度列，可以提高路由查询的平均速度，但更新复杂度上升。此时，时间复杂度上升。此时，时间复杂度O(N)，空间复杂度，空间复杂度O(N)，插入插
7、入/删除路由前缀条目的复杂度为删除路由前缀条目的复杂度为O(N)。基本的二叉检索树（基本的二叉检索树（Trie）v路由前缀按照二叉树的结构来组织。路由前缀按照二叉树的结构来组织。v树中的每个节点含有路由前缀的树中的每个节点含有路由前缀的1比特信息，并根比特信息，并根据下一个比特生成两个子节点。据下一个比特生成两个子节点。v在树的非空节点处，存放该节点对应的下一跳信息。在树的非空节点处，存放该节点对应的下一跳信息。v在进行最长前缀匹配时，首先根据路由前缀的比特在进行最长前缀匹配时，首先根据路由前缀的比特信息遍历二叉树，达到最终匹配的叶子节点处，最信息遍历二叉树，达到最终匹配的叶子节点处，最后读出
8、存储在叶子节点中的下一跳路由信息。后读出存储在叶子节点中的下一跳路由信息。ABDE000011C1A 0*B 1*C 001*D 10*E 110*基本二叉检索树的一个例子基本二叉检索树的一个例子v 在查找的过程中，有可能出现多个前缀匹配的情况，如上图在查找的过程中，有可能出现多个前缀匹配的情况，如上图中的中的(A,C)和和(B,D,E)，这时要选择最长的前缀。，这时要选择最长的前缀。v 在查找时要记录当前最匹配的路由前缀，一直到叶子节点或在查找时要记录当前最匹配的路由前缀，一直到叶子节点或者节点没有合适的分支为止。例如，对于地址者节点没有合适的分支为止。例如，对于地址111*，按照上，按照上
9、图的例子，当查到图的例子，当查到B时，由于是匹配的，所以就记录下相应时，由于是匹配的，所以就记录下相应的信息，继续向下查询，没有更匹配的路由前缀，所以此时的信息，继续向下查询，没有更匹配的路由前缀，所以此时B就是最长匹配的路由前缀。就是最长匹配的路由前缀。v 这种查找实际上是地址前缀长度空间的线性查找。因为是按这种查找实际上是地址前缀长度空间的线性查找。因为是按照单个比特的顺序来查询的。照单个比特的顺序来查询的。v 很显然，使用基本的二叉检索树进行路由查询时，时间复杂很显然，使用基本的二叉检索树进行路由查询时，时间复杂度与树的深度（在这种算法中就等于路由前缀的最大长度）度与树的深度（在这种算法
10、中就等于路由前缀的最大长度）有关。如果最大可能的路由前缀长度为有关。如果最大可能的路由前缀长度为W，则最坏情况下的，则最坏情况下的查找时间复杂度为查找时间复杂度为O(W)。v 最坏情况下的空间复杂度为最坏情况下的空间复杂度为O(N*W) 。v 更新复杂度为更新复杂度为O(W)。更新时需要先进行查找，找到之后进。更新时需要先进行查找，找到之后进行相应的增删操作就可以了（包括中间节点和叶子节点两种行相应的增删操作就可以了（包括中间节点和叶子节点两种情况）。情况）。v 在在IPv4中最多需要中最多需要32次查找，在次查找，在IPv6中最多需要中最多需要128次查找。次查找。路径压缩路径压缩Triev
11、 该算法是对基本二叉检索树的改进，最早起源于该算法是对基本二叉检索树的改进，最早起源于Patricia算法，算法，后来后来Sklower对对Patricia算法做了改进，使之可以用于路由查询。算法做了改进，使之可以用于路由查询。v 其基本思想是去掉输出为其基本思想是去掉输出为1的中间节点，压缩叶子节点的路径，的中间节点，压缩叶子节点的路径，将叶子节点提升到最近一级父节点的下一层。这样，每个中间将叶子节点提升到最近一级父节点的下一层。这样，每个中间节点都有两个输出。节点都有两个输出。v 由于有可能去掉了一些包含路由前缀的中间节点，所有某些节由于有可能去掉了一些包含路由前缀的中间节点，所有某些节点
12、会有多个路由前缀。点会有多个路由前缀。v 由于去掉了一些节点，某些比特将被忽略，所以节点要维护一由于去掉了一些节点，某些比特将被忽略，所以节点要维护一个变量，用于维持下一个要检查的比特位。个变量，用于维持下一个要检查的比特位。BDEA 0*B 1*C 001*D 10*E 110*A/CABDE000011C1A 0*B 1*C 001*D 10*E 110*v 路径压缩路径压缩Trie对稀疏的基本对稀疏的基本Trie有明显的压缩效果，但对稠有明显的压缩效果，但对稠密的则作用不大。密的则作用不大。v 路径压缩路径压缩Trie不能从本质上降低树的深度，在最坏情况下它不能从本质上降低树的深度，在最
13、坏情况下它的时间复杂度仍然为的时间复杂度仍然为O(W)。v 路径压缩路径压缩Trie的空间复杂度为的空间复杂度为O(N)，因为这种，因为这种Trie中中N个叶个叶子节点对应子节点对应N1个内部节点。个内部节点。v 路径压缩路径压缩Trie更新算法的复杂度也是更新算法的复杂度也是O(W)，其动态性比基本，其动态性比基本Trie要差，因为当需要加入或者删除叶子节点时，会导致其要差，因为当需要加入或者删除叶子节点时，会导致其对应的若干条路径上的叶子节点位置发生变化。对应的若干条路径上的叶子节点位置发生变化。v 这种算法在这种算法在BSD系统上得到了实现（系统上得到了实现（Radix树），并随着树），
14、并随着BSD的推广而得到广泛应用。的推广而得到广泛应用。多比特检索树（多比特检索树（Trie）v 在基本的二叉检索树中每次检查一个比特，即一级对应在基本的二叉检索树中每次检查一个比特，即一级对应1个个比特；如果让每一级对应多个比特，就可以大大降低树的深比特；如果让每一级对应多个比特，就可以大大降低树的深度。也就能够降低路由查询的时间复杂度。度。也就能够降低路由查询的时间复杂度。v 每一级对应的比特数被称为查找步宽。同一级的步宽可以一每一级对应的比特数被称为查找步宽。同一级的步宽可以一样，也可以不一样。前者实现起来比较简单，但浪费存储空样，也可以不一样。前者实现起来比较简单，但浪费存储空间，后者
15、实现复杂一些，但是会节省一定的存储空间。间，后者实现复杂一些，但是会节省一定的存储空间。v 因为一次查找多个比特，因此不能处理任意长度的路由前缀，因为一次查找多个比特，因此不能处理任意长度的路由前缀，一般要使用前缀扩展。一般要使用前缀扩展。每一级的步宽都是每一级的步宽都是2 第一级的步宽是第一级的步宽是2 第二级三个节点步宽第二级三个节点步宽是是2，一个节点步宽是，一个节点步宽是1对于上图中绿色部分，如何应用多比特检索？对于上图中绿色部分，如何应用多比特检索？v前缀扩展：将一条较短的路由前缀展开成多条较长前缀扩展：将一条较短的路由前缀展开成多条较长的路由前缀集，这些前缀集的转发信息就是原来地的
16、路由前缀集，这些前缀集的转发信息就是原来地址前缀所对应的转发信息。也就是扩展后的路由前址前缀所对应的转发信息。也就是扩展后的路由前缀要继承原来前缀的转发信息。例如，缀要继承原来前缀的转发信息。例如，1*可以扩展可以扩展为为10*和和11*。v对于对于Trie中不能直接应用多比特树的地方，可以先中不能直接应用多比特树的地方，可以先进行前缀扩展，使应用多比特树的局部成为一个满进行前缀扩展，使应用多比特树的局部成为一个满的子树。的子树。101*111*1010* 1011*1110* 1111*v 由于步宽大于等于由于步宽大于等于1，使检索树的深度明显降低，所以多比，使检索树的深度明显降低，所以多比
17、特检索树的时间复杂度比基本二进制特检索树的时间复杂度比基本二进制Trie或路径压缩或路径压缩Trie要要低，具体的数值与每一级步宽有关。当每一级步宽都是低，具体的数值与每一级步宽有关。当每一级步宽都是K时时（这是多比特检索树中最简单的情况），时间复杂度为（这是多比特检索树中最简单的情况），时间复杂度为O(W/K)。v 时间复杂度降低的代价就是空间复杂度的上升，每一个中间时间复杂度降低的代价就是空间复杂度的上升，每一个中间节点都需要包含节点都需要包含2k个指针（每一级步宽都是个指针（每一级步宽都是K），最差情况），最差情况下每加入一个新前缀，需要插入下每加入一个新前缀，需要插入W/K个中间节点，
18、从而需要个中间节点，从而需要占用空间占用空间O(2k *W/K)，所以空间复杂度为，所以空间复杂度为O(N*2k *W/K)。v 更新时需要进行一次路由查找，然后更新节点的指针，最差更新时需要进行一次路由查找，然后更新节点的指针，最差情况下需要更新情况下需要更新2k-1指针，所以更新复杂度为指针，所以更新复杂度为O(2k W/K)。v对于多比特检索树来说，当步宽为对于多比特检索树来说，当步宽为1时，就成为基时，就成为基本二叉检索树或路径压缩树，当步宽达到本二叉检索树或路径压缩树，当步宽达到W时，时时，时间复杂度为间复杂度为O(1)，但空间复杂度变为，但空间复杂度变为O(2W)。v很显然，多比特
19、检索树的主要问题就是引入了很多很显然，多比特检索树的主要问题就是引入了很多冗余路由前缀，占用了大量存储空间，所以对它的冗余路由前缀，占用了大量存储空间，所以对它的优化是研究的一个重点，例如有些人就提出了步宽优化是研究的一个重点，例如有些人就提出了步宽选择策略，也有人提出了一些压缩算法。选择策略，也有人提出了一些压缩算法。v实际进行压缩时可以考虑互联网地址分布的特点，实际进行压缩时可以考虑互联网地址分布的特点，例如长度例如长度1624之间的前缀数最多。之间的前缀数最多。v叶子扩展的概念叶子扩展的概念0*110*10*111*0*11*1*111*路由前缀长度空间的二分查找路由前缀长度空间的二分查
20、找v Trie树算法的实质是地址前缀长度空间的线性查找：先检查第树算法的实质是地址前缀长度空间的线性查找：先检查第1个（个（1k）个比特，再检查第）个比特，再检查第2个（个（k+12k）个比特，一直）个比特，一直到路由前缀的最大长度为止。到路由前缀的最大长度为止。v 文献文献“Scalable high-speed prefix matching，Marcel Waldvogel,George Varghese,Jon Turner, Bernhard Plattner ，ACM Transactions on Computer Systems, 2001”提出了地址前提出了地址前缀长度空间的
21、二分查找法。缀长度空间的二分查找法。v 基本思想是把所有路由前缀按照其长度分为不同的前缀集合，基本思想是把所有路由前缀按照其长度分为不同的前缀集合，每个前缀集合内采用哈希算法查找；查询时，从长度位每个前缀集合内采用哈希算法查找；查询时，从长度位W/2的的集合开始，采用二分查找法。集合开始，采用二分查找法。W/23W/45W/87W/8W/43W/8W/84657231图中节点对应的是前缀集合，而不是某个或某几个比特位图中节点对应的是前缀集合，而不是某个或某几个比特位v 为了保证该算法的正确性，需要引入一个被成为为了保证该算法的正确性，需要引入一个被成为Marker的的表项。考虑下面的例子。有表
22、项。考虑下面的例子。有4个地址前缀：个地址前缀：0*、1*、00*、110*。现查找。现查找110*。0*1*00*110*2130*1*00*11*(Marker)110*213v路由前缀长度空间的二分查找在路由查询方面的时路由前缀长度空间的二分查找在路由查询方面的时间复杂度为间复杂度为O(logW)，对，对IPv4来说，最多需要来说，最多需要5次查次查询，对询，对IPv6来说，最多需要来说，最多需要7次查询。次查询。v对于每个前缀，最多可能需要对于每个前缀，最多可能需要logW个个Marker，因，因此，算法的空间复杂度为此，算法的空间复杂度为O(N*logW)。v路由更新比较麻烦，其复杂
23、度为路由更新比较麻烦，其复杂度为O(N*logW)，因为，因为最坏情况下更新一个前缀可能影响最坏情况下更新一个前缀可能影响N-1个前缀，而个前缀，而一个前缀又有可能对应一个前缀又有可能对应logW 个个Maker。v哈希算法也是该算法中的关键问题。哈希算法也是该算法中的关键问题。TCAMv TCAM（Ternary Content Address Memory）是一种新型的）是一种新型的存储器，存放一系列路由表项，为到来的每一个分组并行查存储器，存放一系列路由表项，为到来的每一个分组并行查找所有的路由前缀。因此，它的路由查询只需要一次内存访找所有的路由前缀。因此，它的路由查询只需要一次内存访问
24、，若有多个匹配表项，经过优先级比较后，确定路由信息。问，若有多个匹配表项，经过优先级比较后，确定路由信息。v 路由管理比较复杂，路由表的动态删除和更新会导致路由管理比较复杂，路由表的动态删除和更新会导致TCAM中存放大量的碎片。中存放大量的碎片。v 成本昂贵，功耗比较大，存储容量小。成本昂贵，功耗比较大，存储容量小。v 这实际上是一种硬件查找方法。这实际上是一种硬件查找方法。基于分段的查找基于分段的查找v 这种方案实际上是多比特检索树的具体硬件实现方案。典型这种方案实际上是多比特检索树的具体硬件实现方案。典型的是的是Gupta等人提出的等人提出的DIR-24-8-BASIC查找算法。查找算法。
25、v DIR-24-8-BASIC算法是把算法是把IPv4地址空间分为长度分别为地址空间分为长度分别为24和和8的两部分（的两部分（TBL24和和TBLlong），最大内存访问次数为），最大内存访问次数为2，采用硬件流水线技术可以用采用硬件流水线技术可以用1次内存访问。第一部分是次内存访问。第一部分是22416M个表项；第二部分个表项；第二部分256个表项。个表项。v 因为是基于多比特检索树，因此需要进行前缀扩展。因为是基于多比特检索树，因此需要进行前缀扩展。v 第一级中的节点携带的指针信息指示可能存在于第第一级中的节点携带的指针信息指示可能存在于第2级中的级中的一棵子树。一棵子树。指针指针下一
26、跳信息下一跳信息10下一跳下一跳基基地地址址下一跳下一跳信息信息TBL24TBLlong偏偏移移量量缓存（缓存（Cache）策略）策略v缓存策略是指把最近查找过的目的地址和路由下缓存策略是指把最近查找过的目的地址和路由下一跳信息放在缓存之中，当一跳信息放在缓存之中，当IP分组达到时，先从分组达到时，先从缓存中查找，找不到时再执行最长前缀匹配策略。缓存中查找，找不到时再执行最长前缀匹配策略。v显然，数据包的相关度越大，这种方法的有效性显然，数据包的相关度越大，这种方法的有效性就越高。就越高。v缓存的命中率是这种策略的一个关键。由于缓存缓存的命中率是这种策略的一个关键。由于缓存容量有限，且数据日益
27、多样化，缓存的命中率大容量有限，且数据日益多样化，缓存的命中率大大降低。大降低。哈希查找哈希查找v 哈希哈希(Hash)算法在路由查询中应用的时候，通过查找建立的算法在路由查询中应用的时候，通过查找建立的哈希索引，来找到对应的路由前缀。哈希索引，来找到对应的路由前缀。v 理论上讲，哈希算法的时间复杂度和空间复杂度都很低，但理论上讲，哈希算法的时间复杂度和空间复杂度都很低，但实际上很难找到一个完美的或者近似完美的哈希函数。另外，实际上很难找到一个完美的或者近似完美的哈希函数。另外，路由更新也往往会导致哈希表的重建。路由更新也往往会导致哈希表的重建。v 一般来说，把整个路由表做为一个哈希表是不切实
28、际的，可一般来说，把整个路由表做为一个哈希表是不切实际的，可以在局部范围内应用哈希算法。如在前缀长度空间的二分查以在局部范围内应用哈希算法。如在前缀长度空间的二分查找中，就可以在同一前缀长度的前缀集合内应用哈希算法。找中，就可以在同一前缀长度的前缀集合内应用哈希算法。其他路由查询算法其他路由查询算法v层压缩树层压缩树v地址区间的二分查找法地址区间的二分查找法v多路和多列查询算法等多路和多列查询算法等第三部分第三部分路由查询算法的评测路由查询算法的评测算法算法时间复杂时间复杂度度空间复杂度空间复杂度更新复杂更新复杂度度基本二叉检索基本二叉检索树树O(W)O(N*W)O(W)路径压缩检索路径压缩检
29、索树树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）基本算法在时间复杂度等方面的基本算法在时间复杂度等方面的比较比较其他需要考虑的方面其他需要考虑的方面v 算法的可扩展性。即路由前缀长度增加后，不能使查询的复算法的可扩展性。即路由前缀长度增加后，不能使查询的复杂度大幅度上升。杂度大幅度上升。v 路由前缀长度空间的二分查找的扩展性比较好，从路由前缀长度空间的二分查找的扩展性比较好，从IPv4到到IPv6后，最差情况下的查询次数从后，最差情况下的查询
30、次数从5升到升到7。v 各种基于检索树的查找算法可扩展性一般，多比特查找树可各种基于检索树的查找算法可扩展性一般，多比特查找树可以通过增加以通过增加K的方法来降低时间复杂度，但会带来空间复杂的方法来降低时间复杂度，但会带来空间复杂度的大幅度上升。不过也可以通过分段的方法来部分地解决度的大幅度上升。不过也可以通过分段的方法来部分地解决这方面的问题。这方面的问题。对路由查询算法实际评测的方法对路由查询算法实际评测的方法测试数据测试数据被测算法被测算法测试执行测试执行参考算法参考算法测试结果测试结果v测试数据：包括路由前缀和目的地址序列两部分。测试数据：包括路由前缀和目的地址序列两部分。v路由前缀的
31、生成有三种方法路由前缀的生成有三种方法典型数据生成，即采用骨干路由器统计的实际路由表，典型数据生成，即采用骨干路由器统计的实际路由表，测试结果更有实际意义。测试结果更有实际意义。随机生成，测试结果可以反映算法的平均性能。随机生成，测试结果可以反映算法的平均性能。拓扑结构生成，模拟互联网拓扑结构生成测试数据。拓扑结构生成，模拟互联网拓扑结构生成测试数据。v目的地址序列的生成有两种方法目的地址序列的生成有两种方法随机地址生成随机地址生成加权随机地址生成，即按照互联网实际目的地址的分布加权随机地址生成，即按照互联网实际目的地址的分布情况进行加权。情况进行加权。v被测算法指具体被评测的路由查询算法被测
32、算法指具体被评测的路由查询算法v参考算法是指用来参照对比的基本路由查询参考算法是指用来参照对比的基本路由查询算法，如路径压缩算法，如路径压缩Trie等。等。v测试执行则是从查询的时间复杂度、空间复测试执行则是从查询的时间复杂度、空间复杂度、更新复杂度等几个方面进行测试。杂度、更新复杂度等几个方面进行测试。v测试结果反映被测算法在各个评价标准方面测试结果反映被测算法在各个评价标准方面的性能的性能。路由查询和路由更新的分析模型路由查询和路由更新的分析模型v一般来说，为了提高路由查询的速度，往往采用比较一般来说，为了提高路由查询的速度，往往采用比较复杂的数据结构，这就造成路由更新的效率很低。复杂的数
33、据结构，这就造成路由更新的效率很低。v路由查询和路由更新都要访问路由表，由于读写的冲路由查询和路由更新都要访问路由表，由于读写的冲突，它们对路由表的访问一般是互斥的。突，它们对路由表的访问一般是互斥的。v通常考虑的是路由更新对路由查询的影响。通常考虑的是路由更新对路由查询的影响。v路由查询和路由更新之间的定量关系，还没有一个明路由查询和路由更新之间的定量关系，还没有一个明确的结论。确的结论。路由查询队列路由查询队列路由更新队列路由更新队列路由查询请求路由查询请求路由更新请求路由更新请求路由表路由表U到达率到达率lookup到达率到达率update一个简单的分析模型一个简单的分析模型v 路由查询
34、请求的到达一般是泊松分布；路由更新的则未必是，路由查询请求的到达一般是泊松分布；路由更新的则未必是，具体的分布目前还没有定论，为了简单起见，可以假设也是具体的分布目前还没有定论，为了简单起见，可以假设也是泊松到达。泊松到达。v 实际中路由查询请求的到达率要远大于路由更新请求到达率。实际中路由查询请求的到达率要远大于路由更新请求到达率。v 一般来说，路由更新请求不会被丢弃，但路由查询请求就不一般来说，路由更新请求不会被丢弃，但路由查询请求就不一定了，如果网络拥塞，或者分组排队时间过长，都有可能一定了，如果网络拥塞，或者分组排队时间过长，都有可能造成分组被丢弃，自然路由查询请求也就被丢弃了。造成分
35、组被丢弃，自然路由查询请求也就被丢弃了。v 在实际路由器中，路由查询和路由更新一般没有优先级区别。在实际路由器中，路由查询和路由更新一般没有优先级区别。v 可以把路由表做为一个服务者，它的服务时间是一般分布。可以把路由表做为一个服务者，它的服务时间是一般分布。v 路由更新的服务时间一般要大于路由查询的服务时间。路由更新的服务时间一般要大于路由查询的服务时间。第四部分第四部分流分类简介流分类简介流分类概述流分类概述v根据一定的分类规则，检查根据一定的分类规则，检查IP数据包中的多个字段，数据包中的多个字段，对对IP包进行分类，并应用不同的处理策略。也称为包进行分类，并应用不同的处理策略。也称为I
36、P包分类或者包分类或者IP分类。分类。v需求：需求：防火墙防火墙策略路由策略路由服务质量服务质量流量计费等。流量计费等。v检查的字段：检查的字段：源地址和目的地址源地址和目的地址源端口和目的端口源端口和目的端口协议协议(IPv4)、下一个首部、下一个首部(IPv6)业务类型业务类型(IPv6)流标签流标签(IPv6)等。等。v处理策略：处理策略：是否转发数据包；是否转发数据包；向哪里转发数据包；向哪里转发数据包；数据包应该得到什么样的服务；数据包应该得到什么样的服务；相应流量数据包应该收取多少费用等。相应流量数据包应该收取多少费用等。v流分类一般要检查流分类一般要检查IP数据包中的多个字段数据
37、包中的多个字段（域），而路由查询只检查目的（域），而路由查询只检查目的IP地址字段，地址字段，如果把路由查询看作是一维检索的话，那么如果把路由查询看作是一维检索的话，那么流分类就是多维检索。实际上也可以把路由流分类就是多维检索。实际上也可以把路由查询看成是流分类的一个特例。查询看成是流分类的一个特例。流分类的数学定义流分类的数学定义v 每一条流分类规则每一条流分类规则R和数据包首部和数据包首部H中的中的d个域（维）有关，个域（维）有关，相应地可以把每一条规则划分为相应地可以把每一条规则划分为d个分量（可以假设每一分个分量（可以假设每一分量有量有W个比特）。个比特）。v 我们称规则我们称规则R和
38、首部和首部H匹配，当且仅当匹配，当且仅当H的每一个域的每一个域Hi和和R相应的域相应的域Ri匹配。匹配。v H可能匹配规则库可能匹配规则库RS中的多条规则（即发生规则冲突），因中的多条规则（即发生规则冲突），因此要为每一条规则赋予一个优先级。此要为每一条规则赋予一个优先级。v 流分类实质上就是在流分类实质上就是在RS中搜索给定数据包首部中搜索给定数据包首部H的最佳匹配的最佳匹配规则的过程。通常，最佳匹配规则指优先级最高的规则。规则的过程。通常，最佳匹配规则指优先级最高的规则。v给定一个流分类规则集合给定一个流分类规则集合RS，集合含有，集合含有N个规则，个规则，设到达的数据包首部为设到达的数据
39、包首部为H，规则集合中可能存在多，规则集合中可能存在多个规则个规则Ri匹配匹配H。对于每一条规则，赋予一个优先。对于每一条规则，赋予一个优先级级prii，用，用pri(R) 来表示。则流分类的数学定义为：来表示。则流分类的数学定义为：在流分类规则集合在流分类规则集合RS中搜索规则中搜索规则Rm满足以下条件：满足以下条件：数据包首部数据包首部H匹配规则匹配规则Rm在规则集合在规则集合RS中不存在另外的规则中不存在另外的规则R，满足，满足H匹配匹配R，且，且pri(R) 大于大于pri(Rm) 流分类算法的类别流分类算法的类别v 直接查找存储器，预处理时建立线性的数据结构，通过查找线直接查找存储器
40、，预处理时建立线性的数据结构，通过查找线性数据结构和一些处理获得最终结果。包括线性查找、性数据结构和一些处理获得最终结果。包括线性查找、TCAM、Cross-producting、位向量（、位向量（BV）、）、RFC （Recursive Flow Classification）等。其中）等。其中Cross-producting、位向量等算法利、位向量等算法利用了计算几何中点定位问题的思想；用了计算几何中点定位问题的思想； RFC 算法则是利用了映算法则是利用了映射和分段的思想，即可以把射和分段的思想，即可以把IP分类看成是从数据包首部中的分类看成是从数据包首部中的S比特到比特到T比特的一个集
41、合的映射，同时引入分段以降低对存储比特的一个集合的映射，同时引入分段以降低对存储容量的需求（实际上多维归并为一维）。容量的需求（实际上多维归并为一维）。v 基于查找树，预处理时建立以查找树为中心的数据结构，有基于查找树，预处理时建立以查找树为中心的数据结构，有分层查找树、集合归并查找树、网格查找树、智能分层查找分层查找树、集合归并查找树、网格查找树、智能分层查找树等。分层查找树是一维树等。分层查找树是一维Trie的扩展，从的扩展，从d维中选任一维生维中选任一维生成第一级二进制成第一级二进制Trie，对于该，对于该Trie中每一个与第一维匹配的中每一个与第一维匹配的节点（有些节点是因为树的生成而
42、引入的），再按照第二维节点（有些节点是因为树的生成而引入的），再按照第二维建立另一个二叉树，反复这一过程直到完成对每一维的处理，建立另一个二叉树，反复这一过程直到完成对每一维的处理，时间复杂度为时间复杂度为Wd，空间复杂度为，空间复杂度为NdW；其他算法基本上属；其他算法基本上属于在此基础上的改进。于在此基础上的改进。v 利用哈希表。利用哈希表。流分类算法的评价流分类算法的评价v时间复杂度，即查找速度快，包括最坏情时间复杂度，即查找速度快，包括最坏情况、平均情况、统计情况等，一般也是用况、平均情况、统计情况等，一般也是用内存访问次数来衡量；内存访问次数来衡量；v空间复杂度，即占用内存小；空间复杂度，即占用内存小；v易于更新，包括完全更新、增量更新等。易于更新，包括完全更新、增量更新等。
