此帖子不代表我现在的、过去的或者将来的任何雇主的观点。文中所表达的观点完全是我个人的看法。

上次我们讨论了主机中的亲和性问题网络接收路径，今天我们来看看发送端，包括发送包导向和队列调度。在深入了解之前，我先简单介绍一下为什么网络的发送和接收路径如此不同。

在主机网络堆栈领域工作了25年以上，我总是对发送和接收路径的不同感到惊讶。这些差异可以用寄信的例子很好地解释。

假设有人去邮局寄二十封信。他们可以控制这些信件的寄送方式。也许一些作为普通邮件寄出，一些作为优先邮件寄出，还有一些作为挂号信寄出。我们的朋友还可以决定寄信的时间，比如留一些到明天再寄。重点是，在信件实际投入邮箱之前，寄信人可以决定使用什么服务，以及何时寄出。当然，一旦信件投入邮箱，事情就不再由他们掌控了——从那时起，就由邮局来处理了。

现在让我们假设我们的朋友还有一个邮箱，并决定去取他们的邮件。他们不知道将会收到什么。邮箱里可能塞满了垃圾邮件、优先信件、包裹和普通信件的混合物。重点是，收件人无法控制什么最终会出现在他们的邮箱里，这时候他们才能对邮件进行优先处理和分类。

这种类比在网络通信中也同样适用。在网络发送端，有更多的选择来决定如何以及何时发送数据包。发送方的目标通常是为客户端应用程序提供最佳的服务质量（QoS），这通过仔细控制应用程序数据包的发送方式来实现。而在网络接收端，选择少得多。可能有多个接收队列来处理不同优先级的数据包，但即便如此，接收端的能力仍然远远不及发送端。接收处理的主要目标是低延迟和高吞吐量，这也是接收数据包调度机制所关注的重点。

服务质量（QoS）通常由应用程序的期望或需求来定义。例如，某些应用程序可能需要低延迟的通信，有些可能需要高带宽，有些可能需要最小的丢包率等。在线视频游戏可能需要极低的延迟，视频聊天可能需要低抖动，下载视频可能需要高速下载。想象一下，有人在网络中运行各种应用程序，因此挑战在于同时满足这些应用程序的各种服务质量需求。

QoS 通过各种流量管理机制实现。其中一些机制可能相当复杂。其中一种基本技术是流量整形。流量整形是一种网络管理技术，用来控制数据流，通过有意延迟某些数据包，优先处理高优先级应用程序，从而确保关键流量有更好的性能，通过调节不同类型网络数据的带宽使用。本质上，流量整形通过延迟不太重要的数据来优先处理重要数据，保持网络顺畅运行。

家庭网络中流量管理的一个例子。在此示例中，基本上有四类流量在同一网络中传输。这四类流量具有不同的服务质量期望。在线视频游戏要求严格的延迟保证，视频会议需要低延迟和小抖动以保证通话质量，阅读纯文本网页对带宽和延迟的要求都不高，下载电影则需要高吞吐量以确保快速完成。发送方和网络的目的是为所有用户提供最佳体验。

传输包调度（XPS）是一种机制，用于在多队列设备上传送包时，智能选择要使用的传输队列。它可以视为接收包调度的补充。

XPS通过主机将每个流映射到一个传输队列。映射可以通过两种方式建立之一。在发送数据包时，正在运行的CPU会被映射到一个传输队列。这会在CPU和传输队列之间创建一种亲和性，从而促进良好的缓存局部性并减少类似锁这样的资源竞争。

第二种方法是根据接收该流的数据包的接收队列来选择发送队列。这使得发送队列和接收队列之间建立了关联性（在其他上下文中，如RDMA中，这种关联性被正式定义为“队列对（queue pair）”）。这种方法促进传输和接收队列之间的亲和性，这有助于在流处理过程中提升传输和接收两端的CPU亲和性和局部性。

如果一个流的传输队列在传输过程中发生变化，例如一个线程被调度到一个映射到不同传输队列的CPU上运行，那么就有可能出现乱序传输。为解决这个问题，可以将一个流标记为仅在该流中没有未被确认的数据包时使用不同的传输队列——例如，所有TCP发送的数据已被确认接收。这类似于RFS中避免接收包的乱序等机制。

传输包导向（XPS）：在此示例中，四个CPU中的每一个都对应于其自己的传输队列。比如，运行在CPU #1上的应用程序会将数据包发送到第二个设备队列。

排队规则是流量管理的基础机制。我们将“排队规则”定义为“一组规则，用于决定人们或事物在线或队列中服务的先后顺序”。这是一个通用的概念，可以应用到计算机系统、急诊室、银行等领域。为了我们当前的目的，我们主要关注排队规则在网络包发送中的应用。

决定哪个数据包接下来发送的过程称为数据包调度，执行数据包调度的实体称为数据包调度器（当然）。数据包调度器的核心所在是队列策略。

队列纪律是一个既有趣又非常广泛的话题。队列纪律可以从简单的结构变得极其复杂。最简单的队列纪律是一个简单的FIFO（先进先出）。而在另一端，我们可以构建多层次的队列纪律，将流量分为不同的类别和子类别，每个类别都有自己的服务质量。我见过这种队列纪律在实际应用中拥有成千上万的类别！

幸运的是，最极端的队列调度策略仅在最大的云服务提供商网络中才需要。对于那些想要调整家庭路由器的人来说，这并不那么可怕。如果你对此感兴趣并想尝试一下，我建议你可以看看SQM这个工具。

有很多种排队方式，详细描述这些排队方式可能需要一本书。今天我只简单介绍一下几种。

优先级排队规则创建了多个不同“优先级带”的优先级队列。数据包（packet）被分类为不同的优先级，然后被放入相应的优先级队列中。一个包调度器（packet scheduler）按照优先级顺序选择数据包，优先级最高的包优先发送，其次是次高的优先级，以此类推。

pfifo_fast 是一种优先级队列调度策略，它是 Linux 系统中默认启用的队列调度策略。在 pfifo_fast 中，包会根据配置的包过滤器返回的分类，被放入三个优先级队列之一。

优先队列。在这个例子中，有三个优先级，由左侧的三个FIFO表示。数据包会根据优先级进入队列，包调度器会先从优先级最高的FIFO中出队，随后再依次从较低优先级的FIFO中出队。最终，数据包会被放入右侧显示的设备FIFO中。

一种轮询（round robin）排队机制使用了一组FIFO，这样不同的流会被映射到不同的FIFO中。这些FIFO按照轮询的方式服务，包调度器依次从每个FIFO中取出包，顺序是第一个，然后是第二个，接着是第三个，依此类推。当队列发送数据包时，根据其流进行分类，同一流的数据包都会放入同一个FIFO。例如，TCP连接的数据包可以通过TCP四元组（正如在RSS中使用的哈希）匹配到其流。

轮转排队策略促进了不同流之间的公平性。特别是在存在发送少量数据包的小流量（小流量）和高数据速率的大流量（大象）的情况下，这一点尤为重要。我们不希望大流量压制小流量，尤其是因为小流量通常更需要低延迟。

随机公平队列 (SFQ) 是 Linux 中的一种循环公平队列策略。它利用概率方法将数据包分配至不同的队列，它旨在公平地分配网络带宽资源给不同的流。这确保了没有单一的流可以独占网络资源，同时仍然保持高性能和可扩展性，尤其是在数据流数量很大的情况下。

轮流排队机制：在此示例中，数据包按照其流被分类，并映射到八个FIFO队列中的一个（例如FIFO0到FIFO7）。数据包调度器会轮询从这八个FIFO队列中取出数据包，所以可能是先发送一个红色的数据包，接着是一个蓝色的，再接着是绿色的，等等。

基于类的排队策略利用了层级类结构和队列结构。这种结构允许将流量划分成具有不同服务质量要求的多个类。在层级的末端是无类的排队策略，它们提供了必要的服务质量保证。

HTB（层次化令牌桶）是 Linux 中的一种队列调度算法，它利用分层队列结构来通过将流量分类到具有不同优先级和速率限制的不同队列中来控制带宽使用。这使得不同类型的流量可以高效地共享带宽。本质上，它是标准令牌桶算法的更复杂版本，允许通过创建具有父子关系的队列层次结构来实现更复杂的流量管理，从而根据流量类型和优先级进行更细致的带宽分配。

基于类的排队机制。在此示例中，公司的销售和市场部门各自分配了一个类。在这两个类之间，可以分配可用带宽（“保证速率”和“峰值速率”）。每个高级别类都有自己的子类，这些子类具有各自的QoS属性。销售部门的子类有高优先级消息、视频会议和普通通信。市场部门的子类与销售部门相同，还多出一个用于市场演示的子类。

你可能在想，队列调度与XPS之间有什么关系。通常来说，队列调度与设备队列是独立的。例如，包调度器会选择下一个发送的包，然后独立决定用XPS把包放入哪个设备队列。

硬件正在变得越来越先进，实际上一些较新的设备支持更高级的队列管理机制，不再仅限于简单的FIFO，甚至支持多队列功能。这是一个好的方向，但这需要某种方式将这些高级硬件功能集成到主机软件堆栈内。早期为此进行的努力之一是MQPRIO。

MQPRIO 是 Linux 中的一种简单的队列管理机制，允许通过优先级和可配置的优先级到流量类映射，将流量流映射到硬件队列的范围。在此上下文中，流量类由一系列连续的类构成，这些类映射到一系列硬件队列（比例为1:N）。数据包按照优先级进行分类，并在它们被出队时，XPS 可从对应的优先级队列中选择设备队列。

MQPRO：数据包根据优先级被分类并放入FIFO队列中。当数据包调度器从队列中取出一个数据包时，XPS选择一个队列。