网络算法学教学课件.ppt

《网络算法学教学课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章实现原则内容可寻址存储器CAM：一种支持快速搜索和数据存储的存储器，主要用于改善查表操作的性能。三态内容可寻址存储器TCAM：支持“0”、“1”和“*”三种状态的CAM，其中*表示可以匹配0或13.1运用实现原则的例子：更新TCAMCAM被组织成一个二维阵列：每一行（slot）长度固定，存放一个关键字。每一位为“0”或“1”。并行查找：处理器提供一个查找关键字CAM返回匹配该关键字的一组槽，响应时间一般不超过100ns。Content-AddressableMemoryCAM的组织每个条目存储一个二进制数和一个掩码，掩码说明哪些比特要和查找关键字中的相应比特进行比较

2、。TCAM并行地执行查找，返回匹配的最小槽号。TernaryContent-AddressableMemroy使用TCAM进行IP地址查找TCAM中的地址前缀必须按照前缀长度从大到小的顺序排列问题：如何在TCAM中添加或删除一条地址前缀？比如，添加前缀11*朴素的方法：将前缀10*至010001*整体向上移动一个位置将11*插入0*和10*之间若包含大量表项，更新太慢！自由度一：相同长度的前缀不需排序方法：将111*移出，将11*插入到原111*的位置然后，为111*寻找一个新的位置尽管仍然要向TCAM中插入一条前缀，但是问题的规模缩小了理解并利用自由度使用算法技术：采用

3、递归采用递归的算法思想：将最后一条长度为(i+1)的前缀x移出，插入新前缀将最后一条长度为（i+2）的前缀Y移出，X放到Y的位置以此类推实现时展开递归，从TCAM顶部开始：将最后一条长度为32的前缀移到TCAM的顶部，将最后一条长度为31的前缀移到空出的位置；依次类推，直至长度为i的前缀插入最坏情况：每一种长度的前缀都有，需要（32-i）次访存若i较小，访存次数接近32自由度二：空闲空间可以放在TCAM的任何区域方法：空闲空间放在长度为16和17的前缀项之间，可将最坏情况下的访存次数减少一半自由度三：“如果i>j，那么长度为i的前缀必须出现在长度为j的前缀之前”，这不是必

4、要的改变规范：如果两个前缀P和Q可能匹配同一个地址，且P比Q长，则P必须出现在Q之前进一步利用自由度应用背景：入侵检测系统在规定的测量周期内检测攻击节点，并在确定了可疑节点后，将该节点在测量时间内发送的全部数据包放入安全物证日志，发送给管理员。问题：当判定一个节点为可疑节点时，如何得到它之前发送的全部数据包？３.２算法VS算法学：安全物证问题问题：如何从队列中高效地找到属于可疑流的包？解决方案维护一个流ID的哈希表：将每个流ID映射到一个指针列表，列表中的指针指向属于该流的数据包。当一个数据包放入包队列时，用其流ID查找哈希表，将数据包在队列中的地址放入表尾。当数据包离开

5、队列时，从指针列表头部删除其指针。问题：增加了空间复杂度：需要维护哈希表和指针列表。增加了计算复杂度：需要维护哈希表。教科书上的算法基本思想：将判断一个包是否属于可疑流这件事情，拖到不得不做时再去做方法：当可疑节点表非空、且队列满时，每当添加一个包到队头，就从队尾移出一个包。若包的源节点在可疑节点表中，拷贝包到物证日志，否则丢弃包。优点：不需要维护哈希表和指针列表，节省了大量的存储空间，也减小了计算复杂度。系统的解决方案—LazyEvaluation系统原则（1-5）：将系统看成由子系统构成，而不是一个黑盒子兼顾模块化和效率（6-10）：允许保留复杂系统的模块化，与此同时

6、给出提高性能的方法加速（11-15）：仅加速某个关键例程的方法３.３十五条实现原则系统原则（1-5）：将系统看成由子系统构成，而不是一个黑盒子兼顾模块化和效率（6-10）：允许保留复杂系统的模块化，与此同时给出提高性能的方法加速（11-15）：仅加速某个关键例程的方法十五条实现原则原则：若某个特殊的操作序列存在资源浪费，且该模式经常出现，就有必要消除这种浪费。编译器的例子：消除重复的子表达式I:=5.1*n+2优化为：t:=5.1*n+2J:=(5.1*n+2)*4i:=tj:=t*4网络的例子：操作系统和用户空间之间多次数据包拷贝P1：避免常见情形中的明显浪费原则：通过

7、在时间轴上移动计算，有时可以获得很大的收益。属于P2的三类技术：P2a：Precompute（预先计算）P2b：EvaluateLazily（延迟计算）P2c：ShareExpenses（分摊开销）P2：在时间轴上移动计算原则：提前计算好需要的值，节省运行时的计算时间函数计算的例子：复杂的函数计算查表操作网络的例子：预先计算好一个连接上的IP头和TCP头，以减小运行时写包头的工作量P2a：预先计算P2b：延迟计算原则：推迟在关键时间点上要执行的高代价操作，寄希望于该操作在未来可能不再需要，或者可以找到较空闲的时间执行。例子：