《第八章解复用.ppt》由会员分享，可在线阅读，更多相关《第八章解复用.ppt（25页珍藏版）》请在三一文库上搜索。
1、第八章 解复用,什么是解复用（demultiplexing）,解复用： 协议将收到的消息分发给合适的客户。 分层解复用： 利用包含在消息各层协议头中的解复用域逐层进行。 提前解复用（early demultiplexing）： 消息到达时，使用一个操作确定消息要经过的整条协议路径。,分层解复用示意图,为什么要提前解复用,在用户空间实现协议栈，减少上下文切换。 将不同应用的包流分开，进行显式调度，如： 优先处理重要的包； 尽快丢弃超载应用的包，避免接收端活锁； 保证某些应用的服务质量，等等。 定制路径：为确定的包处理路径定制高效的处理代码。 快速分发：消除每一层上的解复用代码，以及由逐层解复用产
2、生的控制开销。,包过滤器（包分类器）,实现提前解复用的数据结构，称为包过滤器或包分类器。 包过滤器： 以完整的包头作为输入，将包映射到一条路径的端点； 端点代表最终处理该包的应用进程； 路径代表在包交给端点之前，需要用来处理该包的一个协议序列。,算法设计目标,安全性： 包过滤器由用户级程序提供，在内核实现，应确保用户之间不相互影响。 高速度： 解复用必须实时完成。 可组合性： 应能将N个独立的包过滤器组合为一个复合的包过滤器，并获得更高的匹配速度。,8.1 CMU/Stanford包过滤器（CSPF）,应用程序提供给内核一个包过滤器，用于处理收到的包。若某个包为应用 A 希望接收的，A的包过滤
3、器返回“真”。 包过滤器是一段程序，用来对描述包特征的表达式树进行求值。 为保证安全性： 使用能力有限的堆栈指令； 监视堆栈引用，以保证引用与堆栈范围一致； 检查包的引用，以保证引用在包长范围之内。,CSPF的表达式树模型,CSPF的问题,架构不匹配：CSPF堆栈模型是为PDP-11发明的，和现代的RISC架构很不匹配。 模型低效：表达式树模型经常导致更多的操作（不能记住包的解析状态）。 只能解析包头中固定偏移位置的域。 为了约束运行时间，没有跳转或循环结构。,8.2 Berkeley Packet Filter（BPF）,用基于寄存器的语言替换了基于堆栈的语言，以与RISC架构相匹配。 使用
4、一个间接操作符将指定偏移位置的域装入寄存器，从而可以访问非固定偏移位置的域，比如Load14。 可以进行比较和跳转操作。 使用一个控制流图模型（状态机）进行计算，可减少比较操作的次数。,BPF的控制流图模型,BPF内置于OS内核,BPF的扩放性,BPF提高了单个过滤器的匹配速度，但是每个包仍然必须与每一个过滤器比较，处理时间为O(n)。 BPF应用于提前解复用，有扩放性问题： 一个繁忙的服务器中，并发的TCP连接数可能很大，每一个TCP连接可能提供一个包过滤器。,8.3 Pathfinder,设想有500个过滤器，每个过滤器具有相同的Ethernet type =IP和 IP protocol
5、 =TCP，只是TCP端口对不同。 BPF的问题： 用到来的包与每个过滤器匹配，需比较500次Ethernet type 和 500次IP protocol。重复！ 用包的端口号与500个过滤器的端口号逐个比较，类似于通过线性查找进行精确匹配。 低效！,Pathfinder的设计思想,合并N个包过滤器为一个复合过滤器： 将在同一个包头域上进行的比较放在一个节点中； 每个节点实现为一个哈希表，用哈希查找代替线性查找。,Pathfinder的数据结构示例,Pathfinder 推广了 Trie,Trie是一种树结构： 每个节点包含一个数组；每个value对应一个固定字符集中的一个取值，pointe
6、r指向对应该值的一个subtrie。 在Trie上查找一个关键字： 将关键字划分成字符；从树根开始，用第 i 个字符作为索引查找路径上的第 i 个节点，得到指向第（i+1）个节点的指针。 pathfinder结构是Trie的推广： 在每个节点上，包头域代替了要查找的字符，哈希表代替了数组。,Pathfinder的技术细节,Pathfinder的最基本单位称为一个cell。 一个cell描述了包头中的一个域（用偏移量、长度和掩码表示）、一个比较值和一个指针。 举例： 检查IP protocol是否为TCP： cell = (9, 1 ,0xff, 6, Ptr)。,Line 和 pattern,
7、将一组cell串在一起，构成一个line。 若一个line中的所有cell匹配一个包，就说这个line匹配这个包。 直观上，一个line匹配一个协议头，一个cell匹配协议头中的一个域。 在最简单的情形中，协议用一个pattern =描述希望进行的匹配，hdrlen给出协议头的长度。,举例,Pathfinder的问题,Pathfinder的软件实现达不到线速，硬件实现不能处理分片的复杂情况。 两个原因导致Pathfinder的软件实现很慢： 解释开销： Pathfinder代码在一定程度上是在解释执行cell。 安全检查开销： 运行时检查包头域的引用是否在包的边界内。 实时检查一个包头域的引用
8、是否字对齐。,举例：Pathfinder的解释开销,cell C = ，检查数据包 P 是否匹配 C 的最小机器代码是：,8.4 Dynamic Packet Filter（DPF）,通过动态重编译为每个新加入的cell生成优化的代码，消除解释开销： DPF在创建代码时，将cell的参数作为立即数硬编码到机器码中。,DPF（续）,利用编译时的知识优化实时安全检查： 编译时知道任何一个cell指定的最大偏移量，只需在包处理前检查一次，保证最大偏移量在当前包的边界内。 绝大部分引用的对齐检查在编译时完成，编译时无法推断的引用才在运行时检查。 其它优化： 利用编译时的知识，将对几个较小的相邻域的访问合并为一次较大的内存访问。,8.5 总结,CSPF：首次将解复用和包处理分离，并将应用提供的包过滤器安全地输出到内核。 BPF：用基于寄存器的状态机模型替换了CSPF基于堆栈的表达式树，以适应底层架构。 Pathfinder：利用推广的trie结构提取包过滤器中的公共比较，将N个BPF过滤器合并为一个综合过滤器。 DPF：利用动态重编译技术优化了pathfinder的执行。,