第八章解复用PPT课件

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