路由原理与技术第3章路由器硬件结构与路由查询算法.pptVIP

路由查询算法评价标准 时间复杂度（查找速度） 空间复杂度（占用的存储空间） 更新复杂度（增加、删除、变更路由表条目时，路由表的更新速度） 可扩展性 注意，上述复杂度一般是指最坏情况下的复杂度。 基本的二叉检索树（Trie） ①? 根据唯一前缀原则把路由表组织成一棵二叉树 问题：使用二叉树仅为每个路由存储唯一前缀，而没有覆盖路由的整个网络部分。 为了确保选路正确，应保证整个网络前缀与路由匹配才转发数据报。 ②?为保证正确选路，外部节点必须完全匹配(需在外部节点增加网络地址和地址掩码) 问题：若包含了子网路由和特定主机路由，则内节点也有可能标识了路由。此时的策略如何？ ③?最长匹配选路策略:相关内节点也包含地址/掩码对，并且按最长匹配选路 。 唯一前缀 00 0100 0101 011 1010 10110 32比特地址（目标项）0000000000000000000000000000000000000000000000000000000000000000111100000000000000000010000000000000101000000000 10111 0 0 0 0 1 1 1 0 0 1 0 1 ， 例：假如目标地址是1010000000000001 若仅查二叉树，则出现错误！ * 下一跳 前缀 /16 /24 /24 /24 /32 /24 /32 问题：路由表中含有同一网络的一般路由和具体路由。 0 0 0 1 1 10 128 1 5个0 0 1 7 3 /16 /24 /32 路径压缩Trie 该算法是对基本二叉检索树的改进，最早起源于Patricia算法，后来Sklower对Patricia算法做了改进，使之可以用于路由查询。 其基本思想是去掉没有分支的节点，所谓没有分支的节点是指一个几点不同时有左子节点和右子节点，同时该节点也不是有效节点。 由于去掉了一些节点，某些比特将被忽略，所以节点要维护一个变量，用于维持下一个要检查的比特位。 多比特检索树（Trie） 在基本的二叉检索树中每次检查一个比特，即一级对应1个比特；如果让每一级对应多个比特，就可以大大降低树的深度。也就能够降低路由查询的时间复杂度。 每一级对应的比特数被称为查找步宽。同一级的步宽可以一样，也可以不一样。前者实现起来比较简单，但浪费存储空间，后者实现复杂一些，但是会节省一定的存储空间。 因为一次查找多个比特，因此不能处理任意长度的路由前缀，一般要使用前缀扩展。 每一级的步宽都是2 第一级的步宽是2 第二级三个节点步宽是2，一个节点步宽是1 对于上图中绿色部分，如何应用多比特检索？ 前缀扩展：将一条较短的路由前缀展开成多条较长的路由前缀集，这些前缀集的转发信息就是原来地址前缀所对应的转发信息。也就是扩展后的路由前缀要继承原来前缀的转发信息。例如，1*可以扩展为10*和11*。 对于Trie中不能直接应用多比特树的地方，可以先进行前缀扩展，使应用多比特树的局部成为一个满的子树。 由于步宽大于等于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之间的前缀数最多。 叶子扩展的概念 路由前缀长度空间的二分查找 Trie树算法的实质是地址前缀长度空间的线性查找：先检查第1个（1－k）个比特，再检查第2个（k+1－2k