《网络算法学》课程教学资源（PPT课件讲稿）第三章 实现原则

第三章实现原则

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中插入 一条前缀，但是问题的规 模缩小了

使用算法技术:采用递归 采用递归的算法思想: 实现时展开递归,从TCAM 0将最后一条长度为(i+1)的前 顶部开始: 缀x移出,插入新前缀 0将最后一条长度为32的前缀 将最后一条长度为(i+2)的 移到TCAM的顶部,将最后 前缀Y移出,Ⅹ放到Y的位置 条长度为31的前缀移到空 以此类推 出的位置; 依次类推,直至长度为的前 Prefix Next Hop 缀插入 Free space 最坏情况: 每一种长度的前缀都有,需 要(32-i)次访存 Length-(+1)prefixes 若i较小,访存次数接近32 - Create a hole here by Length-i prefixes moving x to Ys position,问题:还能再改进吗?

 采用递归的算法思想： ◦ 将最后一条长度为 (i+1)的前 缀x移出，插入新前缀 ◦ 将最后一条长度为（i+2）的 前缀 Y 移出，X放到Y的位置 ◦ 以此类推  实现时展开递归，从TCAM 顶部开始： ◦ 将最后一条长度为32的前缀 移到TCAM的顶部，将最后 一条长度为31的前缀移到空 出的位置； ◦ 依次类推，直至长度为i的前 缀插入  最坏情况： ◦ 每一种长度的前缀都有，需 要（32-i）次访存 ◦ 若 i 较小，访存次数接近32  问题：还能再改进吗？

进一步利用自由度 自由度二:空闲空间可以放在TCAM的任何区域 优化方法: 。空闲空间放在长度为16和17的前缀项之间,可将最坏 情况下的访存次数减少一半 自由度三:“如果ij,那么长度为的前缀必须 出现在长度为的前缀之前”,这不是必要的! 改变规范: 0如果两个前缀P和Q可能匹配同一个地址,且P比Q长, 则P必须出现在Q之前

 自由度二：空闲空间可以放在TCAM的任何区域  优化方法： ◦ 空闲空间放在长度为16和17的前缀项之间，可将最坏 情况下的访存次数减少一半  自由度三：“如果i>j，那么长度为i的前缀必须 出现在长度为j的前缀之前”，这不是必要的！  改变规范： ◦ 如果两个前缀P和Q可能匹配同一个地址，且P比Q长， 则P必须出现在Q之前

3.2算法VS算法学:安全物证问题 应用背景: 入侵检测系统在规定的测量周期内检测攻击节 点,并在确定了可疑节点后,将该节点在测量 时间内发送的全部数据包放入安全物证日志, 发送给管理员。 问题: 0当判定一个节点为可疑节点时,如何得到它之 前发送的全部数据包?

 应用背景： ◦ 入侵检测系统在规定的测量周期内检测攻击节 点，并在确定了可疑节点后，将该节点在测量 时间内发送的全部数据包放入安全物证日志， 发送给管理员。  问题： ◦ 当判定一个节点为可疑节点时，如何得到它之 前发送的全部数据包？

解决方案 Packet P arrives for flow F st probabilistic Forward P suspicion test Add co of p to head If alert. add f to table Queue of If F In Table, update state last N Suspicion packets table Report to manager periodically_Forensic or upon bad flow detection How to search memory for log all packets sent with flow ID F to add to forensic log? 问题:如何从队列中高效地找到属于可疑流的包?

 问题：如何从队列中高效地找到属于可疑流的包？

教科书上的算法 ν维护一个流ID的哈希表: 0将每个流D映射到一个指针列表,列表中的指针指 向属于该流的数据包 0当一个数据包放入包队列时,用其流|D查找哈希表, 将数据包在队列中的地址放入表尾 当数据包离开队列时,从指针列表头部删除其指针 问题: 增加了空间复杂度:需要维护哈希表和指针列表 增加了计算复杂度:需要维护哈希表

 维护一个流ID的哈希表： ◦ 将每个流ID映射到一个指针列表，列表中的指针指 向属于该流的数据包 ◦ 当一个数据包放入包队列时，用其流ID查找哈希表， 将数据包在队列中的地址放入表尾 ◦ 当数据包离开队列时，从指针列表头部删除其指针  问题： ◦ 增加了空间复杂度：需要维护哈希表和指针列表 ◦ 增加了计算复杂度：需要维护哈希表