《【教学课件】第八章解复用.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第八章解复用.ppt（24页珍藏版）》请在三一办公上搜索。
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为每个包加上一个头部，包括一个时间戳和包长度,BPF的扩放性,收到的每一
4、个包必须与每一个包过滤器匹配，处理时间为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次IP protocol。重复！用包的端口号与50
5、0个过滤器的端口号逐个比较，类似于通过线性查找进行精确匹配。低效！,Pathfinder的设计思想,合并N个包过滤器为一个复合过滤器：将在同一个包头域上进行的比较放在一个节点中：比如，将对Ethernet type的查找放在一个节点中每个节点实现为一个哈希表，用哈希查找代替线性查找,Pathfinder的数据结构示例,根节点对应以太帧的type域，包含过滤器集合中描述的所有Ethernet type值。根节点实现为一个哈希表，每个哈希表项包含一个值和一个指针，指针指向下一个要查找的节点。Pathfinder的每个节点用于匹配包头中的一个域,Pathfinder 推广了 Trie,Trie是一种
6、前缀树：每个节点包含一个数组，pointer指向一个subtrie键并不保存在节点中，而是作为查找节点数组的索引 在Trie上查找一个关键字：将关键字划分成字符；从树根开始，用第 i 个字符作为索引查找路径上第 i 个节点的数组，得到指向第（i+1）个节点的指针。pathfinder结构是Trie的推广：在每个节点上，包头域代替了要查找的字符，哈希表代替了数组。,Pathfinder的技术细节,Pathfinder的最基本单位称为一个cell一个cell描述了包头中的一个域（用offset、length、mask表示）、一个比较值和一个指针举例：检查IP protocol是否为TCP，cell
7、=(9,1,0 xff,6,Ptr)：9：相对于IP头部起始位置偏移9个字节处1：读取一个字节的内容0 xff：提取整个字节作为比较关键字6：将提取的关键字与6（TCP协议号）进行比较Ptr：若匹配，沿指针查找下一个cell,Line 和 pattern,将一组cell用指针链在一起，构成一个line。若一个line中的所有cell匹配一个包，就说这个line匹配这个包。在最简单的情形中，用一个pattern=描述希望进行的匹配，hdrlen给出协议头的长度。直观上，一个line匹配一个协议头，一个cell匹配协议头中的一个域。,举例,Pathfinder的问题,Pathfinder的软件实现
8、达不到线速；若使用硬件实现，不能处理分片的复杂情况（只有第一个分片包含TCP头）Pathfinder的软件实现为什么很慢：解释开销：Pathfinder代码在一定程度上是在解释执行cell安全检查开销：运行时检查包头域的引用是否在包的边界内实时检查一个包头域的引用是否字对齐,举例：Pathfinder的解释开销,cell C=，检查数据包 P 是否匹配 C 的最小机器代码是：,8.4 Dynamic Packet Filter（DPF）,动态包过滤器（DPF）利用动态编译技术优化Pathfinder的执行速度通过动态重编译为每个新加入的cell生成优化的代码，消除解释开销：DPF在创建代码时，
9、将cell的参数作为立即数硬编码到机器码中每个cell都有自己特殊的代码，而不是所有cell使用同一段代码,DPF（续）,利用编译时的知识优化实时安全检查：编译时知道任何一个cell指定的最大偏移量，因此，只需在包处理前检查一次，保证最大偏移量在当前包的边界内（不需要每引用一个包头域都检查）绝大部分引用的对齐检查在编译时完成，编译时无法推断的引用才在运行时检查其它优化：利用编译时的知识，将对几个较小的相邻域的访问合并为一次较大的内存访问。,DPF的性能提升,解复用一个包的速度是Pathfinder的13-26倍（与平台有关）添加一个包过滤器的时间是Pathfinder的 3 倍：在增加的插入开销中，动态代码生成占了40%,8.5 总结,BPF：使用状态机模型进行计算，每个包需和所有的过滤器进行匹配Pathfinder：利用推广的trie结构提取包过滤器中的公共比较，将N个BPF过滤器合并为一个综合过滤器DPF：利用动态重编译技术优化了pathfinder的执行,
