第八章解复用

1、： 协议将收到的消息分发给合适的客户。分层解复用： 利用包含在消息各层协议头中的解复用域逐层进行。提前解复用（early demultiplexing）： 消息到达时，使用一个操作确定消息要经过的整条协议路径。在用户空间实现协议栈，减少上下文切换。将不同应用的包流分开，进行显式调度，如： 优先处理重要的包； 尽快丢弃超载应用的包，避免接收端活锁； 保证某些应用的服务质量，等等。定制路径：为确定的包处理路径定制高效的处理代码。快速分发：消除每一层上的解复用代码，以及由逐层解复用产生的控制开销。实现提前解复用的数据结构，称为包过滤器或包分类器。包过滤器： 以完整的包头作为输入，将包映射到一条路径的

2、端点； 端点代表最终处理该包的应用进程； 路径代表在包交给端点之前，需要用来处理该包的一个协议序列。安全性： 包过滤器由用户级程序提供，在内核实现，应确保用户之间不相互影响。高速度： 解复用必须实时完成。可组合性： 应能将N个独立的包过滤器组合为一个复合的包过滤器，并获得更高的匹配速度。应用程序提供给内核一个包过滤器，用于处理收到的包。若某个包为应用 A 希望接收的，A的包过滤器返回“真”。包过滤器是一段程序，用来对描述包特征的表达式树进行求值。为保证安全性： 使用能力有限的堆栈指令； 监视堆栈引用，以保证引用与堆栈范围一致； 检查包的引用，以保证引用在包长范围之内。架构不匹配：CSPF堆栈模

3、型是为PDP-11发明的，和现代的RISC架构很不匹配。模型低效：表达式树模型经常导致更多的操作（不能记住包的解析状态）。只能解析包头中固定偏移位置的域。为了约束运行时间，没有跳转或循环结构。用基于寄存器的语言替换了基于堆栈的语言，以与RISC架构相匹配。使用一个间接操作符将指定偏移位置的域装入寄存器，从而可以访问非固定偏移位置的域，比如Load14。可以进行比较和跳转操作。使用一个控制流图模型（状态机）进行计算，可减少比较操作的次数。BPF提高了单个过滤器的匹配速度，但是每个包仍然必须与每一个过滤器比较，处理时间为O(n)。BPF应用于提前解复用，有扩放性问题： 一个繁忙的服务器中，并发的T

4、CP连接数可能很大，每一个TCP连接可能提供一个包过滤器。设想有500个过滤器，每个过滤器具有相同的Ethernet type =IP和 IP protocol =TCP，只是TCP端口对不同。BPF的问题： 用到来的包与每个过滤器匹配，需比较500次Ethernet type 和 500次IP protocol。重复！ 用包的端口号与500个过滤器的端口号逐个比较，类似于通过线性查找进行精确匹配。 低效！合并N个包过滤器为一个复合过滤器： 将在同一个包头域上进行的比较放在一个节点中； 每个节点实现为一个哈希表，用哈希查找代替线性查找。Trie是一种树结构： 每个节点包含一个数组；每个valu

5、e对应一个固定字符集中的一个取值，pointer指向对应该值的一个subtrie。 在Trie上查找一个关键字： 将关键字划分成字符；从树根开始，用第 i 个字符作为索引查找路径上的第 i 个节点，得到指向第（i+1）个节点的指针。pathfinder结构是Trie的推广： 在每个节点上，包头域代替了要查找的字符，哈希表代替了数组。 Pathfinder的最基本单位称为一个cell。一个cell描述了包头中的一个域（用偏移量、长度和掩码表示）、一个比较值和一个指针。举例： 检查IP protocol是否为TCP： cell = (9, 1 ,0 xff, 6, Ptr)。 将一组cell串在一

6、起，构成一个line。若一个line中的所有cell匹配一个包，就说这个line匹配这个包。直观上，一个line匹配一个协议头，一个cell匹配协议头中的一个域。在最简单的情形中，协议用一个pattern =描述希望进行的匹配，hdrlen给出协议头的长度。 Pathfinder的软件实现达不到线速，硬件实现不能处理分片的复杂情况。两个原因导致Pathfinder的软件实现很慢： 解释开销： Pathfinder代码在一定程度上是在解释执行cell。 安全检查开销： 运行时检查包头域的引用是否在包的边界内。 实时检查一个包头域的引用是否字对齐。 cell C = ，检查数据包 P 是否匹配 C 的最小机器代码是： 通过动态重编译为每个新加入的cell生成优化的代码，消除解释开销： DPF在创建代码时，将cell的参数作为立即数硬编码到机器码中。 利用编译时的知识优化实时安全检查： 编译时知道任何一个cell指定的最大偏移量，只需在包处理前检查一次，保证最大偏移量在当前包的边界内。 绝大部分引用的对齐检查在编译时完成，编译时无法推断的引用才在运行时检查。其它优化： 利用编译时的知识，将对几个较小的相邻域的访问合并为一次较大的内存访问。 CSPF：首次将解复用和包处理分离，并将应用提供的包过滤器安全地输出到内核。BPF：用基于寄存器的状态机模型替