第三章实现原则
3.1运用实现原则的例子:更新TCAM 内容可寻址存储器CAM: CAM 种支持快速搜索和数据存储的 one slot 存储器,主要用于改善查表操作 的性能 CAM被组织成一个二维阵列: 每一行(slot)长度固定,存放 个关键字 每一位为“0”或“1” 并行查找: 。处理器提供一个查找关键字 CAM返回匹配该关键字的一组 槽,响应时间一般不超过100ns CAM的组织
内容可寻址存储器CAM： ◦ 一种支持快速搜索和数据存储的 存储器，主要用于改善查表操作 的性能 CAM被组织成一个二维阵列： ◦ 每一行（slot）长度固定，存放 一个关键字 ◦ 每一位为“0”或“1” 并行查找： ◦ 处理器提供一个查找关键字 ◦ CAM返回匹配该关键字的一组 槽，响应时间一般不超过100ns CAM的组织
三态内容可寻址存储器TCAM 〉支持“0”、“1”和“ 三种状态的CAM,其中*如-[0 00450600500000 表示可以匹配0或1 每个条目存储一个二进制 0800450600500002 数和一个掩码,掩码说明 ask 仟f ffffff ff 00 哪些比特要和查找关键字 slot =2 0800450600350003 中的相应比特进行比较 ask ffff ffffff ff0000 TCAM并行地执行查找 返回匹配的最小槽号 特别适合存储P转发表
支持“0”、“1”和“*” 三种状态的CAM，其中 * 表示可以匹配0或1 每个条目存储一个二进制 数和一个掩码，掩码说明 哪些比特要和查找关键字 中的相应比特进行比较 TCAM并行地执行查找， 返回匹配的最小槽号 特别适合存储IP转发表
使用TCAM进行|P地址查找 Prefix Next Hop 问题: Free 如何在TCAM中添加或删 010001·P5 110001 P3 110001*P5 P4 除一条地址前缀? [」區 Router 比如,添加前缀11* 朴素的方法 10 P4 0 P4 将前缀10至010001整 FIGURE 3.4 Example of using a ternary CAM for prefix lookups 体向上移动一个位置 图中地址前缀的排列方法: 将11插入0和10之间 。按前缀长度从长到短排列 若包含大量表项,更新太 慢! 相同长度的前缀,按从小 到大排列
图中地址前缀的排列方法： ◦ 按前缀长度从长到短排列 ◦ 相同长度的前缀，按从小 到大排列 问题： ◦ 如何在TCAM中添加或删 除一条地址前缀？ ◦ 比如，添加前缀11* 朴素的方法： ◦ 将前缀10*至010001*整 体向上移动一个位置 ◦ 将11*插入 0*和10*之间 ◦ 若包含大量表项，更新太 慢！
理解并利用自由度 自由度:允许改变的量 Prefix Next Hop 自由度一: Free Free 相同长度的前缀不必有序 010001*P5 1100 110001*P5 优化方法: 110 Router 111 将11移出,将11插 00 入到原111的位置 01 10 P4 然后,为111寻找一个 新的位置 FIGURE 3.4 Example of using a ternary CAM for prefix lookups 尽管仍然要向TCAM中插入 条前缓,但是问题的规 模缩小了
自由度：允许改变的量 自由度一： ◦ 相同长度的前缀不必有序 优化方法： ◦ 将111*移出，将11*插 入到原111*的位置 ◦ 然后，为111*寻找一个 新的位置 尽管仍然要向TCAM中插入 一条前缀，但是问题的规 模缩小了