路由原理与技术第8章路由查询 北京邮电大学.pptVIP

基于分段的查找 这种方案实际上是多比特检索树的具体硬件实现方案。典型的是Gupta等人提出的DIR-24-8-BASIC查找算法。 DIR-24-8-BASIC算法是把IPv4地址空间分为长度分别为24和8的两部分（TBL24和TBLlong），最大内存访问次数为2，采用硬件流水线技术可以用1次内存访问。第一部分是224＝16M个表项；第二部分256个表项。 因为是基于多比特检索树，因此需要进行前缀扩展。 第一级中的节点携带的指针信息指示可能存在于第2级中的一棵子树。 缓存（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的方法来降低时间复杂度，但会带来空间复杂度的大幅度上升。不过也可以通过分段的方法来部分地解决这方面的问题。 对路由查询算法实际评测的方法 测试数据：包括路由前缀和目的地址序列两部分。 路由前缀的生成有三种方法 典型数据生成，即采用骨干路由器统计的实际路由表，测试结果更有实际意义。 随机生成，测试结果可以反映算法的平均性能。 拓扑结构生成，模拟互联网拓扑结构生成测试数据。 目的地址序列的生成有两种方法 随机地址生成 加权随机地址生成，即按照互联网实际目的地址的分布情况进行加权。 被测算法指具体被评测的路由查询算法 参考算法是指用来参照对比的基本路由查询算法，如路径压缩Trie等。 测试执行则是从查询的时间复杂度、空间复杂度、更新复杂度等几个方面进行测试。 测试结果反映被测算法在各个评价标准方面的性能。 路由查询和路由更新的分析模型 一般来说，为了提高路由查询的速度，往往采用比较复杂的数据结构，这就造成路由更新的效率很低。 路由查询和路由更新都要访问路由表，由于读写的冲突，它们对路由表的访问一般是互斥的。 通常考虑的是路由更新对路由查询的影响。 路由查询和路由更新之间的定量关系，还没有一个明确的结论。 一个简单的分析模型 路由查询请求的到达一般是泊松分布；路由更新的则未必是，具体的分布目前还没有定论，为了简单起见，可以假设也是泊松到达。 实际中路由查询请求的到达率要远大于路由更新请求到达率。 一般来说，路由更新请求不会被丢弃，但路由查询请求就不一定了，如果网络拥塞，或者分组排队时间过长，都有可能造成分组被丢弃，自然路由查询请求也就被丢弃了。 在实际路由器中，路由查询和路由更新一般没有优先级区别。 可以把路由表做为一个服务者，它的服务时间是一般分布。 路由更新的服务时间一般要大于路由查询的服务时间。 第四部分流分类简介 流分类概述 根据一定的分类规则，检查IP数据包中的多个字段，对IP包进行分类，并应用不同的处理策略。也称为IP包分类或者IP分类。 需求： 防火墙 策略路由 服务质量 流量计费等。 检查的字段： 源地址和目的地址 源端口和目的端口 协议(IPv4)、下一个首部(IPv6) 业务类型(IPv6) 流标签(IPv6)等。 处理策略： 是否转发数据包； 向哪里转发数据包； 数据包应该得到什么样的服务； 相应流量数据包应该收取多少费用等。 流分类一般要检查IP数据包中的多个字段（域），而路由查询只检查目的IP地址字段，如果把路由查询看作是一维检索的话，那么流分类就是多维检索。实际上也可以把路由查询看成