Part I Part II 第1章 网络算法学概述 第2章 网络实现模型 第3章 实现原则 第4章 原则的运用 第5章 数据拷贝 第1章 网络算法学概述 第2章 网络实现模型 第3章 实现原则 第4章 原则的运用 Part II 第5章 数据拷贝 第6章 传输控制 第7章 定时器管理 第8章 提前解复用 第9章 协议处理

第九章 协议处理

本章主要内容 缓冲区管理 常规协议（TCP/UDP）处理：TCP头部预测 分片重组 在极高的数据速率下，协议处理的任何一个环节都不能忽视 对于大量小包来说，主要开销是一般性协议处理而不是数据处理

9.1 缓冲区管理 数据包到达后，首先要分配一个缓冲区 操作系统需提供分配和释放缓冲区的服务，包括： 管理空闲缓冲区 为数据包找到合适大小的缓冲空间 如果多个连接或用户共享一个缓存空间，还需提供某种形式的公平分配 困难：包缓冲区分配必须实时完成

9.1.1 缓冲区分配 经典的BSD UNIX包缓冲区实现称为mbufs： Mbufs设计的出发点： 缺点：访问数据和拷贝数据的开销大 9.1.1 缓冲区分配 经典的BSD UNIX包缓冲区实现称为mbufs： 使用一个缓冲区链来存放一个包，每个缓冲区为一段连续的存储空间 BSD定义了三种大小的缓冲区：100字节、108字节、2048字节（称cluster） Mbufs设计的出发点： 使用一个缓冲区链来存放一个包：允许动态扩展包的缓冲空间；适应各种协议栈 定义不同大小的缓冲区：充分利用内存空间 缺点：访问数据和拷贝数据的开销大

Sk_buff Linux操作系统的包缓冲区实现是sk_buff： Sk_buff的设计原则是用空间换时间： 每个包缓冲区都是一块连续地址空间，提前为路径上需要添加的各种协议头预留了空间 Sk_buff的设计原则是用空间换时间： 使用连续地址空间的缓冲区，实现简单，时间开销小 包缓冲区必须满足最大包长，有时会浪费空间

如何为不同大小的包分配缓冲区？ 给每个包分配最大长度的包缓冲区是一种浪费 较好的方法是按需分配内存： 动态分配内存的困难： 当一个包到来时，为其分配一块合适大小的缓存空间 动态分配内存的困难： 用户会在不同的时间释放缓冲区，导致内存中出现许多不连续的、大小不同的空闲区域 教科书上的标准算法（如First-Fit、Best-Fit）可以搜索到合适大小的空闲区域，但速度太慢

高速包缓冲区分配器 开发高速网络软件的工程师通常会考虑以下三种内存分配器： 隔离池分配器（Segregated Pool Allocator） Linux分配器（Linux Allocator） 批量分配器（Batch Allocator）

隔离池分配器 可能有内存空间浪费，但实现简单 随 BSD 4.2 UNIX发布，称Kingsley malloc() 将存储空间划分成一组隔离的内存池，同一个内存池中的缓冲区大小相同，为2的幂次 内存请求被取整到最近的缓冲区大小，从相应的内存池链表头部取一个空闲缓冲区分配 若对应的内存池空间不足，分配失败 可能有内存空间浪费，但实现简单

Linux分配器 Linux分配器最初由Doug Lea实现，称为dlmalloc() 内存被划分成128个内存池： 前64个内存池，缓冲区大小分别为16、24、32、……、512字节（按8字节步长增加） 后64个内存池，大小为2的幂次 分配器会合并相邻的空闲缓冲区，放入合适的缓冲池中 Lea分配器比Kingsley分配器使用内存更高效，但实现更复杂

批量分配器 分配器一次性向系统请求一大块内存，用来作为包缓冲区池（批量的含义） 当一个内存块正在使用时，后台创建另一个空闲内存块 分配器在当前内存块上采用顺序分配： 一个指针指向上一次分配结束的位置，新的内存请求总是从当前位置开始分配 一个内存块用完，立即转移到另一个空闲内存块上

批量分配器（续） 当缓冲区释放的顺序与分配的顺序不一致时，内存块中形成一些孔洞，需要合并。 方法一： 使用足够多的内存块，确保在这些内存块用完之前，已分配的内存块被释放，避免显式回收。（目前工业界的做法，空间换时间） 方法二： 使用页面重映射将若干分离的物理页映射成在虚拟存储空间是连续的。 优点：支持可变长度的内存分配，没有内存浪费，分配快 内存分配用硬件实现，后台创建空闲块用软件实现

9.1.2 共享缓冲区 假如一群用户共用同一组空闲缓冲区，我们希望共享缓冲区的分配是公平的： 困难在于共享缓冲区的用户是变化的： 9.1.2 共享缓冲区 假如一群用户共用同一组空闲缓冲区，我们希望共享缓冲区的分配是公平的： 这组缓冲区在需要的用户之间近乎均等地分配 困难在于共享缓冲区的用户是变化的： 每个用户分配的缓冲区数量应当能够动态调整 当有新用户加入时，应能从老用户那儿夺取一些缓冲区

缓冲器窃取 缓冲区窃取是实现公平分配的一种方法： 缓冲区窃取的通用解决方案： 若所有缓冲区已用完，一个分配较少的用户可从当前分配最多的用户那儿窃取一些缓冲区 即使一开始分配是不均衡的，最终每个用户都可以获得他们公平的份额 缓冲区窃取的通用解决方案： 使用一个大顶堆，代价O(logn)，n为当前活跃的用户数 有无更快的实现方法？

问题分析 如果允许用户一次获取任意数量的缓冲区，那么使用O(logn)的堆是必需的 假设为了获得常数时间的算法，可以降低要求： 一个用户一次只能窃取一个缓冲区 每个用户拥有的缓冲区数量是一个小整数 可以用桶排序代替堆排序

常数时间算法：Mckenney算法 采用桶排序： 将分配了 i 个缓冲区的进程组织在一个链表中，头指针保存在第 i 个桶中 一个变量highest指向分配了最多缓冲区的进程链表

窃取一个缓冲区 当一个进程 P 希望获取一个缓冲区时： 算法是常数时间的： 算法从highest指向的进程链表头部取进程Q，Q的缓冲区数量减1，P的缓冲区数量加1 将P从链表 i 移到链表 i+1 将Q从链表 j 移到链表 j-1 如果highest指向的链表为空，更新highest为 j-1 算法是常数时间的： 由于限定了每次只能增加或减少一个缓冲区，算法更新highest指针最多只需移动一个桶

9.2 TCP头部预测 因特网上最主要的流量是TCP，最复杂的数据面协议也是TCP Tcp_input是TCP中最长的一部分代码，约1100行： 许多实现完全遵循RFC 793中定义的输入事件处理步骤 逐个状态地检查，以确定要执行什么处理 然而，检查的大部分状态都是很少发生的 Van Jacobson提出头部预测机制 ： 快速识别预期的TCP段，避免不必要的状态检查，优化常见情形的处理

对TCP头的观察 连接完成后，目的端口和源端口是固定的 大部分情况下IP包顺序到达，因此序号域通常等于预期接收的下一个序号 连接建立后，ACK标志总为1，其它标志一般为0 大多数情况下，接收窗口大小不变 当URG标志为0时，紧急指针域不用 变数较大的域只有两个：确认序号，检查和

预期情形 大多数时候，TCP连接上的数据传输是单向的： 两种预期的情形： 其它预期情形： 客户从服务器下载一个文件，或客户向服务器上载一个文件 两种预期的情形： 发送数据一方：收到一个纯ACK段（无数据） 接收数据一方：收到一个纯数据段（确认序号无更新） 其它预期情形： 标志位常规设置 无窗口更新

接收端头部预测的伪代码

接收端头部预测伪代码（续） 第一个子句检查标志位设置是否符合预期 第二个子句检查是否无窗口更新 第三个子句检查是否是预期接收的段（不是乱序到达或重发的） 若以上条件判断为真，这是预期接收的TCP段，再区分是纯ACK段还是纯数据段 若以上条件判断为假，不是预期接收的TCP段，执行常规的处理过程（慢路径） 标志域以及窗口大小组成一个32位的字，可将这个字的预期值保存到TCB中，头两个子句的检查只需用TCP头的第4个字与TCB中保存的字进行一次比较即可。

发送端头部预测 在发送端发送的一系列 TCP 段中，TCP头部有变化的域只有少数几个 发送端头部预测： 发送端在TCB中建立一个TCP头模板

9.3 IP分片重组 分片重组的经典实现： 各分片按照分片偏移量保存在一个有序链表中 一个分片到达时，顺序查找链表，插入到合适的位置 在寻找插入位置的过程中，检查分片之前的数据是否全部到达；如果是， 在插入分片后继续沿链表向下查找，检查是否全部数据已到达；如果是， 重新扫描链表，将数据拷贝到另一个缓冲区中

优化预期情形 重组过程复杂的原因： 预期情形： 优化预期情形： 考虑到IP分片可能乱序到达，且分片之间可能有重叠 若判断为预期情形，只需将到来的分片添加到链表尾部（一个常数时间操作）

优化的IP分片重组算法 在有序链表的基础上，增加一个指向链表尾部的指针 分片到来时，用分片的起始字节偏移量与链表上最后一个分片的末字节偏移量（存在一个变量中）进行比较 若分片顺序到达且无重叠，将分片添加到链表的尾部，更新指向链表尾部的指针，更新末字节偏移量 如果这是最后一个分片（MF=0），重组结束 寻找插入位置及检查重组是否结束，只需要常数时间

假设与实际相符吗？ 分片重组优化算法隐含的假设： 实际测量： IP分片按照偏移量从小到大的顺序发送 多数情况下IP包顺序到达 许多较新的实现（包括Linux），发送端按照分片偏移量从大到小的顺序发送IP分片！ 原因：最后一个分片携带了IP包总长度的信息，让最后一个分片最先到达接收端，方便接收端为数据包分配适当大小的缓冲区

算法调整 使用第一个到来的分片，判断发送端按照什么顺序发送IP分片 如果第一个到来的分片是第一个分片，使用前述实现 如果第一个到来的分片是最后一个分片，跳转到按逆序处理的程序： 最后一个分片放在链表头部，其余分片按偏移量降序排列 用分片的末字节偏移量与链表尾部分片的起始偏移量进行比较

9.4 总结 缓冲区分配： 缓冲区共享： TCP输入处理、IP分片重组： 空间利用率 vs 合并不连续空闲区域的难度 缓冲区窃取 通过优化预期情形的处理，提高大多数情况下的算法性能