ip路由器(编辑修改稿)

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

需要维护一个变量，指示下一个需要检查的比特位  前缀节点需要保存地址前缀的比特串 路径压缩 Trie树（续）  当二元 Trie树中的前缀分布较稀疏时，路径压缩算法能够获得良好的压缩效果。  二元 Trie树和路径压缩 Trie树的不足是查找过程需要大量的存储器访问操作。  研究表明，对于一个具有 47113个前缀表项的典型骨干网路由器，使用 BSD Trie会创建 93304个节点，树的最大高度为 26，平均高度为 20。 而对于同样的前缀表，二元 Trie树的最大高度为 30，平均高度为 22。 （ 3）多分支 Trie  查找的每一步检查地址的多个比特，以减少树的高度（访存次数）。  查找步宽：每次检查的比特数称为查找步宽。  根据同一层中不同子树的步宽是否相同，分为：  固定步宽多分支 Trie  可变步宽多分支 Trie 可变步宽与固定步宽的多分支 Trie树 前缀扩展  前缀表中的地址前缀必须转换成多分支 Trie查找允许的地址前缀。 前缀扩展例 2 在前缀扩展过程中，如果扩展的地址前缀与原来的地址前缀冲突，应保留原来的地址前缀。 多分支 Trie的查找和更新  多分支 Trie的查找过程类似于二分支 Trie。  多分支 Trie可以看成是由单层 subtrie构成的树，在每个 subtrie所做的前缀扩展是局部的。  多分支 Trie的更新过程比二分支 Trie复杂：  插入一个前缀时，需要找到相应的 subtrie，对前缀进行扩展，然后插入。  删除一个前缀时，需要删除所有扩展的前缀。  需要额外的数据结构保存原始前缀。 多分支 Trie的优化  步宽的选择  步宽的选择是在算法查找速度、存储空间和更新复杂度之间的折衷。  一种较自然的做法是根据二分支 Trie的 地址前缀分布来选择合适的步宽。  使用某种优化策略，使在搜索深度固定的情况下整个树的存储空间最小。 （ 4） Stanford算法  据统计，因特网中 %的前缀长度分布在 24或小于 24的范围内。  提出一种 248的多分支 Trie快速查找算法：  第一层步宽 24比特：绝大多数情况下访问这一层就可以找到最佳匹配前缀。  第二层步宽 8比特：少数情况下需要查找这一层。  查找速度快，要求较大的存储空间。 Stanford算法的硬件实现 TBL24 TBLlong （ 5）基于 TCAM的地址查找  内容可寻址存储器（ Content Addressable Memory）是一种支持快速搜索和数据存储的存储机制，主要用于提高查表速度。  CAM被组织成一个二维阵列，每一行长度固定，称为一个槽。  处理器提供一个查找关键字，CAM返回匹配该关键字的一组槽。 CAM的组织 TCAM（三态 CAM）  每个 TCAM条目存储一个二进制数和一个掩码。  掩码长度等于槽长度，指示哪些比特要和关键字的相应比特比较。  若有多个条目匹配，选择地址最低的条目。  TCAM适合于查找带通配符的关键字。 （ 5）基于 TCAM的地址查找  优点：查找速度快，实现简单。 采用流水线技术可以进一步提高查找速度。  缺点： TCAM容量小、代价高、功耗大、更新复杂（关键字需要排序）。 T C A M 芯片 NextHop索 引表 NextHop映 射表目的I P 地址下一跳地址和端口（ 6） IPv6地址查找  IPv6路由表的特点：  前缀更长： IPv6地址长 128比特。  由路由器转发的一类地址（可聚合的全局单播地址），前 3比特（格式前缀）总是 001，最后 64比特用于标识网络接口。  规模更大：大规模应用后，前缀项估计在 50万条左右。  IPv4地址查找算法不能直接应用于 IPv6：  基于 Trie的算法访存次数很多，或内存需求很大。  基于 TCAM的方法不适用于规模巨大的表。 采用多分支 Trie树构造查找表 [5]  采用改进的 Stanford算法，保留其查找快速、易于更新及硬件实现容易等优点，并压缩算法所需的存储空间。  根据统计结果及 IPv6地址分配策略，长度大于 48比特的前缀仅为 5%左右。  构造查找步宽为 2488816的五层多分支 Trie树，限制最坏情况下路由查找的访存次数。 前缀扩展产生许多冗余 （ 2020:4*::/18, A）和（ 2020:5*::/20, B）扩展出来的表项 TrieC的算法思想  具有相同下一跳的前缀项组成一个数据块，下一跳信息只在表中存储一次。  采用一个位向量记录每个数据块的起始位置。  64条前缀压缩成一个表项，高 18比特作为表项索引，低 6比特用作位向量索引。  统计位向量中从起始位置到当前位置 “ 1”的个数，作为数组下标。 TrieC树结构  建立 2488816多分支 TrieC树：  根节点采用 TrieC15/6数据结构，存储长度为 [1, 24]比特的地址前缀。  第二层至第四层均采用 TrieC4/4数据结构，分别存储长度为 [25, 32]、 [33, 40]、 [41, 48]比特的地址前缀。  第五层为基于 CRC的哈希表，存储长度为 [49, 64]比特的地址前缀。  每一层节点的数据结构中都有一个标志位用于指示是否需要继续查找下一层节点。 网络处理器中的实现优化  位操作指令  POP_COUNT指令：可在 3个时钟周期内计算 32位寄存器中 1的个数。 在 RISC结构上通常需要 100多条指令。  分支跳转指令：可在 1条指令中完成分支跳转操作。 在RISC体系结构上通常至少需要 3条指令。  硬件 CRC指令：  5个时钟周期完成计算。  数据分布  TrieC表按照 TrieC树的层次存储在四个 SRAM控制器中 3 数据包分类 包分类的术语  包头 H：有 K个域的实体，第 i个域表示为一个比特串 H[i]。  过滤规则 f ：具有 K个域，第 i个域表示为 f[i]。  与每个 f[i]相关联有一个匹配方式，可以是：  精确匹配： f[i]用一个值表示，若 H[i]=f[i]，称 H[i]与 f[i]精确匹配。  前缀匹配： f[i]通过一个前缀指定，若 H[i]与 f[i]表示的前缀匹配，称 H[i]与 f[i]前缀匹配。  范围匹配： f[i]通过一个范围 [val1, val2]指定，若满足val1≤ H[i] ≤ val2，称 H[i]与 f[i]范围匹配。  规则 f 与包头 H匹配，当且仅当每个 H[i]匹配 f[i]。 IP分类问题的定义  给定一个具有 N条规则的规则集 F，与每条规则 f 相联系有一个代价函数 cost(f)，给定一个包头 H，最佳规则匹配问题为在 F 中查找满足下列条件的规则 fbest：  Fbest 匹配 H  在 F 中不存在其它的规则 f ，使得 f 匹配 H且满足 cost(f)cost(fbest)。 IP分类与多维空间的点定位  多维空间的点定位问题：  给定多维空间中一些互不相交的区域，找出包含指定点的区域。  IP分类问题与多维空间中的点定位问题相似：  每条规则对应多维空间中的一个。