《网络实现模型第3章实现原则第4章原则的运用》由会员分享，可在线阅读，更多相关《网络实现模型第3章实现原则第4章原则的运用（29页珍藏版）》请在金锄头文库上搜索。
1、Part I第1章 网络算法学概述第2章 网络实现模型第3章 实现原则第4章 原则的运用Part II第5章 数据拷贝第6章 传输控制第7章 定时器管理第8章 提前解复用第9章 协议处理第九章 协议处理本章主要内容缓冲区管理常规协议（TCP/UDP）处理：TCP头部预测分片重组在极高的数据速率下，协议处理的任何一个环节都不能忽视对于大量小包来说，主要开销是一般性协议处理而不是数据处理9.1 缓冲区管理数据包到达后，首先要分配一个缓冲区操作系统需提供分配和释放缓冲区的服务，包括：管理空闲缓冲区为数据包找到合适大小的缓冲空间如果多个连接或用户共享一个缓存空间，还需提供某种形式的公平分配困难：包缓冲
2、区分配必须实时完成9.1.1 缓冲区分配经典的BSD UNIX包缓冲区实现称为mbufs：使用一个缓冲区链来存放一个包，每个缓冲区为一段连续的存储空间BSD定义了三种大小的缓冲区：100字节、108字节、2048字节（称cluster）Mbufs设计的出发点：使用一个缓冲区链来存放一个包：允许动态扩展包的缓冲空间；适应各种协议栈定义不同大小的缓冲区：充分利用内存空间缺点：访问数据和拷贝数据的开销大Sk_buffLinux操作系统的包缓冲区实现是sk_buff：每个包缓冲区都是一块连续地址空间，提前为路径上需要添加的各种协议头预留了空间Sk_buff的设计原则是用空间换时间：使用连续地址空间的缓
3、冲区，实现简单，时间开销小包缓冲区必须满足最大包长，有时会浪费空间如何为不同大小的包分配缓冲区？给每个包分配最大长度的包缓冲区是一种浪费较好的方法是按需分配内存：当一个包到来时，为其分配一块合适大小的缓存空间动态分配内存的困难：用户会在不同的时间释放缓冲区，导致内存中出现许多不连续的、大小不同的空闲区域教科书上的标准算法（如First-Fit、Best-Fit）可以搜索到合适大小的空闲区域，但速度太慢高速包缓冲区分配器开发高速网络软件的工程师通常会考虑以下三种内存分配器：隔离池分配器（Segregated Pool Allocator）Linux分配器（Linux Allocator）批量分配
4、器（Batch Allocator）隔离池分配器随 BSD 4.2 UNIX发布，称Kingsley malloc()将存储空间划分成一组隔离的内存池，同一个内存池中的缓冲区大小相同，为2的幂次内存请求被取整到最近的缓冲区大小，从相应的内存池链表头部取一个空闲缓冲区分配若对应的内存池空间不足，分配失败可能有内存空间浪费，但实现简单Linux分配器Linux分配器最初由Doug Lea实现，称为dlmalloc()内存被划分成128个内存池：前64个内存池，缓冲区大小分别为16、24、32、512字节（按8字节步长增加）后64个内存池，大小为2的幂次分配器会合并相邻的空闲缓冲区，放入合适的缓冲池
5、中Lea分配器比Kingsley分配器使用内存更高效，但实现更复杂批量分配器分配器一次性向系统请求一大块内存，用来作为包缓冲区池（批量的含义）当一个内存块正在使用时，后台创建另一个空闲内存块分配器在当前内存块上采用顺序分配：一个指针指向上一次分配结束的位置，新的内存请求总是从当前位置开始分配一个内存块用完，立即转移到另一个空闲内存块上批量分配器（续）当缓冲区释放的顺序与分配的顺序不一致时，内存块中形成一些孔洞，需要合并。方法一：使用足够多的内存块，确保在这些内存块用完之前，已分配的内存块被释放，避免显式回收。（目前工业界的做法，空间换时间）方法二：使用页面重映射将若干分离的物理页映射成在虚拟存
6、储空间是连续的。优点：支持可变长度的内存分配，没有内存浪费，分配快内存分配用硬件实现，后台创建空闲块用软件实现9.1.2 共享缓冲区假如一群用户共用同一组空闲缓冲区，我们希望共享缓冲区的分配是公平的：这组缓冲区在需要的用户之间近乎均等地分配困难在于共享缓冲区的用户是变化的：每个用户分配的缓冲区数量应当能够动态调整当有新用户加入时，应能从老用户那儿夺取一些缓冲区缓冲器窃取缓冲区窃取是实现公平分配的一种方法：若所有缓冲区已用完，一个分配较少的用户可从当前分配最多的用户那儿窃取一些缓冲区即使一开始分配是不均衡的，最终每个用户都可以获得他们公平的份额缓冲区窃取的通用解决方案：使用一个大顶堆，代价O(l
7、ogn)，n为当前活跃的用户数有无更快的实现方法？问题分析如果允许用户一次获取任意数量的缓冲区，那么使用O(logn)的堆是必需的假设为了获得常数时间的算法，可以降低要求：一个用户一次只能窃取一个缓冲区每个用户拥有的缓冲区数量是一个小整数可以用桶排序代替堆排序常数时间算法：Mckenney算法采用桶排序：将分配了 i 个缓冲区的进程组织在一个链表中，头指针保存在第 i 个桶中一个变量highest指向分配了最多缓冲区的进程链表窃取一个缓冲区当一个进程 P 希望获取一个缓冲区时：算法从highest指向的进程链表头部取进程Q，Q的缓冲区数量减1，P的缓冲区数量加1将P从链表 i 移到链表 i+1
8、将Q从链表 j 移到链表 j-1如果highest指向的链表为空，更新highest为 j-1算法是常数时间的：由于限定了每次只能增加或减少一个缓冲区，算法更新highest指针最多只需移动一个桶9.2 TCP头部预测因特网上最主要的流量是TCP，最复杂的数据面协议也是TCPTcp_input是TCP中最长的一部分代码，约1100行：许多实现完全遵循RFC 793中定义的输入事件处理步骤逐个状态地检查，以确定要执行什么处理然而，检查的大部分状态都是很少发生的Van Jacobson提出头部预测机制 ：快速识别预期的TCP段，避免不必要的状态检查，优化常见情形的处理对TCP头的观察连接完成后，目
9、的端口和源端口是固定的大部分情况下IP包顺序到达，因此序号域通常等于预期接收的下一个序号连接建立后，ACK标志总为1，其它标志一般为0大多数情况下，接收窗口大小不变当URG标志为0时，紧急指针域不用变数较大的域只有两个：确认序号，检查和预期情形大多数时候，TCP连接上的数据传输是单向的：客户从服务器下载一个文件，或客户向服务器上载一个文件两种预期的情形：发送数据一方：收到一个纯ACK段（无数据）接收数据一方：收到一个纯数据段（确认序号无更新）其它预期情形：标志位常规设置无窗口更新接收端头部预测的伪代码接收端头部预测伪代码（续）第一个子句检查标志位设置是否符合预期第二个子句检查是否无窗口更新第三
10、个子句检查是否是预期接收的段（不是乱序到达或重发的）若以上条件判断为真，这是预期接收的TCP段，再区分是纯ACK段还是纯数据段若以上条件判断为假，不是预期接收的TCP段，执行常规的处理过程（慢路径）标志域以及窗口大小组成一个32位的字，可将这个字的预期值保存到TCB中，头两个子句的检查只需用TCP头的第4个字与TCB中保存的字进行一次比较即可。发送端头部预测在发送端发送的一系列 TCP 段中，TCP头部有变化的域只有少数几个发送端头部预测：发送端在TCB中建立一个TCP头模板每当需要发送一个TCP段时 ，将模板拷贝到相应的包缓冲区中，填写少数几个有变化的域9.3 IP分片重组分片重组的经典实现
11、：各分片按照分片偏移量保存在一个有序链表中一个分片到达时，顺序查找链表，插入到合适的位置在寻找插入位置的过程中，检查分片之前的数据是否全部到达；如果是，在插入分片后继续沿链表向下查找，检查是否全部数据已到达；如果是，重新扫描链表，将数据拷贝到另一个缓冲区中优化预期情形重组过程复杂的原因：考虑到IP分片可能乱序到达，且分片之间可能有重叠预期情形：IP分片按序到达，且没有重叠优化预期情形：若判断为预期情形，只需将到来的分片添加到链表尾部（一个常数时间操作）优化的IP分片重组算法在有序链表的基础上，增加一个指向链表尾部的指针分片到来时，用分片的起始字节偏移量与链表上最后一个分片的末字节偏移量（存在一
12、个变量中）进行比较若分片顺序到达且无重叠，将分片添加到链表的尾部，更新指向链表尾部的指针，更新末字节偏移量如果这是最后一个分片（MF=0），重组结束寻找插入位置及检查重组是否结束，只需要常数时间假设与实际相符吗？分片重组优化算法隐含的假设：IP分片按照偏移量从小到大的顺序发送多数情况下IP包顺序到达实际测量：许多较新的实现（包括Linux），发送端按照分片偏移量从大到小的顺序发送IP分片！原因：最后一个分片携带了IP包总长度的信息，让最后一个分片最先到达接收端，方便接收端为数据包分配适当大小的缓冲区算法调整使用第一个到来的分片，判断发送端按照什么顺序发送IP分片如果第一个到来的分片是第一个分片，使用前述实现如果第一个到来的分片是最后一个分片，跳转到按逆序处理的程序：最后一个分片放在链表头部，其余分片按偏移量降序排列用分片的末字节偏移量与链表尾部分片的起始偏移量进行比较9.4 总结缓冲区分配：空间利用率 vs 合并不连续空闲区域的难度缓冲区共享：缓冲区窃取TCP输入处理、IP分片重组：通过优化预期情形的处理，提高大多数情况下的算法性能
