使用算法技术:采用递归 采用递归的算法思想: 实现时展开递归,从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查找哈希表， 将数据包在队列中的地址放入表尾 ◦ 当数据包离开队列时，从指针列表头部删除其指针 问题： ◦ 增加了空间复杂度：需要维护哈希表和指针列表 ◦ 增加了计算复杂度：需要维护哈希表