ip路由查找(编辑修改稿)

ip路由查找(编辑修改稿)内容摘要：

rie查找能够允许的地址前缀。 图  多分支 Trie树的深度有很大缩减，因而提高了查找效率。  多分支 Trie的查找过程类似于二进制 Trie。  多分支 Trie的更新过程比二进制 Trie复杂：  插入一个前缀时，需要找到相应的 subtrie，对前缀进行扩展，然后插入。  删除一个前缀时，需要删除所有扩展的前缀。  需要额外的数据结构保存原始前缀。 可变步宽与固定步宽的多分支 Trie树 多分支 Trie例 1 多分支 Trie例 2 在地址扩展过程中，如果扩展的地址前缀与原来的地址前缀冲突，应保留原来的地址前缀。 多分支 Trie的优化（ 1）  步宽的选择  步宽的选择是在算法查找速度、存储空间和更新复杂度之间的折衷。  一种较自然的做法是根据实际地址前缀的分布来选择合适的步宽。  使用某种优化策略，使在搜索深度固定的情况下整个树的存储空间最小。 多分支 Trie的优化（ 2）  248多分支 trie快速查找算法的硬件实现  查找最多只需要两次访存；采用硬件流水线技术，实际上只需要一次访存的时间。  算法要求的内存空间比较大。 TBL24 TBLlong 多分支 Trie的优化（ 3）  压缩  在前缀扩展的过程中，前缀的转发信息被扩展到了 trie树的多个连续节点中，造成大量的信息冗余。  压缩因前缀扩展造成的大量冗余信息，减少算法占用的内存空间。 基于前缀长度的二分查找 01011100110011011110111101000hash tables01011100110 marker111 marker010 marker11001101111011110100 marker01000hash tables with marker前缀范围查找 任何地址区域所对应的最长前缀应该是包含此区域的前缀中范围最窄的那一项。 地址区间的二分查找树  最长前缀匹配查找变成在左端点集合中寻找离目的地址最近的左端点。  路由表规模很大时，查找效果不好。  更新性能较差。 基于 TCAM的硬件查找  TCAM中每一个表项以 地址，掩码 序偶的形式保存。  TCAM在所有匹配的表项中选取地址最低的表项作为最后的结果，所以必须将前缀较长的关键字表项存储在低地址。  查找速度快，实现简单。 完成一次查找只需三步操作，采用流水线技术可以进一步提高查找速度。  容量小，代价高，功耗大，更新复杂（关键字需要排序）。 T C A M 芯片 NextHop索 引表 NextHop映 射表目的I P 地址下一跳地址和端口IPv6地址查找的困难  前缀更长：  IPv6地址长度为 128比特，路由器只转发 Aggregatable Global Unicast Address，这类地址的前 3个比特总为 001，且最后 64比特用于标识网络接口。  规模更大：  目前 IPv6尚未广泛使用， IPv6路由表都很小（基本不超过 1000个前缀项），但估计的前缀项应在 50万条左右。  IPv4路由查找算法不能直接应用于 IPv6：  基于 trie的算法访存次数很多，或内存需求很大，像 Sta。