1、第八章 解复用,什么是解复用（demultiplexing）,解复用： 协议实体将收到的报文交付给相应的客户 分层解复用： 利用包含在报文各层协议头中的解复用域逐层进行，例如： 以太帧头中的type域 IP头中的protocol域 TCP/UDP头中的dest port域 提前解复用（early demultiplexing）： 报文到达时，使用一个操作确定报文要经过的整条协议路径,分层解复用示意图,为什么要提前解复用？,区分处理： 优先处理重要的包 尽早丢弃超载应用的包 保证某些应用的服务质量，等等定制路径： 为确定的包处理路径定制高效的处理代码快速分发： 去除每一层上的解复用代码，以及由逐
2、层解复用产生的控制开销（进程或线程调用）,包过滤器（包分类器）,包过滤器（包分类器）： 实现提前解复用的数据结构 以完整的包头作为输入，将包映射到一条处理路径的端点处理路径： 路径端点：最终处理该包的应用进程 路径：在包交给端点之前，需要用来处理该包的一个协议序列,算法设计目标,安全性： 包过滤器由用户级程序提供，在内核实现，应确保用户之间不相互影响高速度： 解复用必须实时（线速）完成可组合性： 应能将N个独立的包过滤器组合为一个复合的包过滤器，并获得更高的匹配速度,8.1 Berkeley Packet Filter（BPF）,专为高性能网络监视工具（如tcpdump）而设计 使用一个控制流
3、图模型（状态机）进行计算,感兴趣的包：src IP=X 的IP包和ARP包,BPF内置于OS内核,BPF的调用,BPF由用户提供的一组包过滤器组成，每个包过滤器有一个对应的缓冲区 到达的包首先被网卡驱动程序处理： 若BPF是活跃的，首先调用BPF： 用包头与每个过滤器匹配 对于每个匹配的过滤器，将一定数量的字节（由过滤器指定）拷贝到对应的缓冲区中 不与任何一个过滤器匹配的包交给TCP/IP栈处理,BPF的有用特性,先过滤再缓存： 若大多数包都不是应用想要的，可以避免不必要的浪费（缓冲空间，拷贝时间）允许一次read()调用返回多个包： 为区分包的边界，BPF为每个包加上一个头部，包括一个时间戳
4、和包长度,BPF的扩放性,收到的每一个包必须与每一个包过滤器匹配，处理时间为O(n)： 对于典型的BPF应用没有问题：一个典型的BPF应用可能只提供几个过滤器将BPF应用于提前解复用，有扩放性问题： 一个繁忙的服务器中，并发的TCP连接数可能很大，每一个TCP连接可能提供一个包过滤器,8.2 Pathfinder,为在x-kernel中支持用户级网络而设计 设想有500个过滤器，每个过滤器具有相同的Ethernet type =IP和 IP protocol =TCP，只是TCP端口对不同 如果用BPF实现： 用到来的包与每个过滤器匹配，需比较500次Ethernet type 和 500次I
5、P protocol。重复！ 用包的端口号与500个过滤器的端口号逐个比较，类似于通过线性查找进行精确匹配。 低效！,Pathfinder的设计思想,合并N个包过滤器为一个复合过滤器： 将在同一个包头域上进行的比较放在一个节点中： 比如，将对Ethernet type的查找放在一个节点中 每个节点实现为一个哈希表，用哈希查找代替线性查找,Pathfinder的数据结构示例,根节点对应以太帧的type域，包含过滤器集合中描述的所有Ethernet type值。 根节点实现为一个哈希表，每个哈希表项包含一个值和一个指针，指针指向下一个要查找的节点。 Pathfinder的每个节点用于匹配包头中的一
6、个域,Pathfinder 推广了 Trie,Trie是一种前缀树： 每个节点包含一个数组，pointer指向一个subtrie 键并不保存在节点中，而是作为查找节点数组的索引在Trie上查找一个关键字： 将关键字划分成字符；从树根开始，用第 i 个字符作为索引查找路径上第 i 个节点的数组，得到指向第（i+1）个节点的指针。 pathfinder结构是Trie的推广： 在每个节点上，包头域代替了要查找的字符，哈希表代替了数组。,Pathfinder的技术细节,Pathfinder的最基本单位称为一个cell 一个cell描述了包头中的一个域（用offset、 length、mask表示）、一
7、个比较值和一个指针 举例： 检查IP protocol是否为TCP，cell = (9, 1 ,0xff, 6, Ptr)： 9：相对于IP头部起始位置偏移9个字节处 1：读取一个字节的内容 0xff：提取整个字节作为比较关键字 6：将提取的关键字与6（TCP协议号）进行比较 Ptr：若匹配，沿指针查找下一个cell,Line 和 pattern,将一组cell用指针链在一起，构成一个line。 若一个line中的所有cell匹配一个包，就说这个line匹配这个包。 在最简单的情形中，用一个pattern =描述希望进行的匹配，hdrlen给出协议头的长度。 直观上，一个line匹配一个协议头
8、，一个cell匹配协议头中的一个域。,举例,Pathfinder的问题,Pathfinder的软件实现达不到线速；若使用硬件实现，不能处理分片的复杂情况（只有第一个分片包含TCP头）Pathfinder的软件实现为什么很慢： 解释开销： Pathfinder代码在一定程度上是在解释执行cell 安全检查开销： 运行时检查包头域的引用是否在包的边界内 实时检查一个包头域的引用是否字对齐,举例：Pathfinder的解释开销,cell C = ，检查数据包 P 是否匹配 C 的最小机器代码是：,8.4 Dynamic Packet Filter（DPF）,动态包过滤器（DPF）利用动态编译技术优化
9、Pathfinder的执行速度 通过动态重编译为每个新加入的cell生成优化的代码，消除解释开销： DPF在创建代码时，将cell的参数作为立即数硬编码到机器码中 每个cell都有自己特殊的代码，而不是所有cell使用同一段代码,DPF（续）,利用编译时的知识优化实时安全检查： 编译时知道任何一个cell指定的最大偏移量，因此，只需在包处理前检查一次，保证最大偏移量在当前包的边界内（不需要每引用一个包头域都检查） 绝大部分引用的对齐检查在编译时完成，编译时无法推断的引用才在运行时检查其它优化： 利用编译时的知识，将对几个较小的相邻域的访问合并为一次较大的内存访问。,DPF的性能提升,解复用一个包的速度是Pathfinder的13-26倍（与平台有关） 添加一个包过滤器的时间是Pathfinder的 3 倍： 在增加的插入开销中，动态代码生成占了40%,8.5 总结,BPF：使用状态机模型进行计算，每个包需和所有的过滤器进行匹配Pathfinder：利用推广的trie结构提取包过滤器中的公共比较，将N个BPF过滤器合并为一个综合过滤器DPF：利用动态重编译技术优化了pathfinder的执行,
