1、第八章 路由查询北京邮电大学网络技术研究院下一代互联网技术研究中心第一部分概述影响 IP网络性能的关键因素v链路速度v路由器的吞吐量v包转发速率v对路由变化的快速适应性v采用光纤等技术提高链路速度v在路由器中采用大容量的交换结构以提高吞吐量v采用高效的路由查询算法和硬件路由查询方案提高包转发速率（ 路由查询 ）v优化各种动态路由协议解决方案路由查询定义v设分组的目的地址为 D， 包含长度为 W 的比特数。v设路由前缀为 P， 包含的比特数为 0 W ， L(P)表示前缀长度。v地址 D匹配前缀 P的含义：地址 D的前 L(P)位比特值与前缀 P完全相同。v给定一个路由前缀集合 PA， 集合含有
2、 N个路由前缀，到达分组的目的地址为 D， 路由的最长前缀匹配查找定义为：在前缀集合 PA中搜索到的前缀 Pm满足：目的地址 D匹配前缀 Pm；在集合 PA中不存在其他的前缀 P， 满足 D匹配 P， 且L(P)L(Pm)v为什么是最长前缀匹配而不是精确匹配CIDR等机制的引入： IP地址是无类别的，从 IP地址不能判断出其网络前缀长度； IPv6单播地址也是无类别的。最长前缀匹配给路由查询带来很大的困难，因为不仅要考虑前缀的值，还要考虑前缀的长度。传统的关键字查找算法不能直接用于路由查询。W. Doeringer, G. Karjoth, and M. Nassehi, “Routing o
3、n longest matching prefixes,” IEEE/ACM Trans. Networking, vol. 4, pp. 8697, Feb. 1996. 路由查询算法分类v按照采用的数据结构和实现方式，大致可以分为：基于检索树（ Trie） 查找基于硬件 TCAM查找分段查找哈希表查找Cache命中查找等。v按照路由查询的依据，可以分为：基于路由前缀值的查找基于路由前缀长度的查找路由查询算法评价标准v时间复杂度（查找速度）v空间复杂度（占用的存储空间）v更新复杂度（增加、删除、变更路由表条目时，路由表的更新速度）v可扩展性 v注意，上述复杂度一般是指最坏情况下的复杂度。第二部分各种路由查询算法路由前缀值的线性查找v所有路由前缀按照线性链表的方式组织。v查询时要遍历路由表中的所有表项，并记录查询过程中匹配的最长路由前缀项，一直到最后一项为止。v时间复杂度 O(N)， 空间复杂度 O(N)， 插入 /删除路由前缀条目的复杂度为 O(1)。v如果使用有序链表，即把路由前缀按照长度大小排列，可以提高路由查询的平均速度，但更新复杂度上升。此时，时间复杂度 O(N)， 空间复杂度 O(N)，插入 /删除路由前缀条目的复杂度为 O(N)。
