路由器辅助的拥塞控制
基于路由器的拥塞控制
之前我们看到了一些基于主机的拥塞控制算法存在的问题。这些问题中的许多都可以在路由器的帮助下得到解决！
TCP 会混淆拥塞和数据损坏。TCP 会填满队列，速率不稳定，并且在短流上表现不佳，这些都是因为主机需要不断调整速率来检测拥塞。如果路由器能告知发送方拥塞情况，甚至直接告诉发送方理想的速率，那么很多这些问题都能得到解决。
此外，如果路由器能强制实现公平共享，那么主机就很难作弊了。
从更宏观的角度来看，让路由器参与拥塞控制是一种很自然的设计选择。拥塞发生在路由器上，所以它们通常比主机拥有更多关于拥塞的信息。
路由器辅助的拥塞控制可以非常有效，并能实现接近最优的性能（高链路利用率、低延迟），但部署这些协议可能具有挑战性。路由器现在需要支持额外的功能，而且有时这些功能可能相当复杂。有些协议甚至可能要求每个路由器都同意添加该功能。
强制公平排队
路由器如何确保每个连接都能获得公平的份额？
到目前为止，路由器接收数据包，必要时进行排队，然后按先进先出（FIFO）的顺序发送出去。路由器并不关心数据包来自哪个连接。
在我们的新模型中，路由器需要将数据包分类到不同的连接中。（目前假设所有连接都是 TCP 连接。）这意味着路由器必须查看数据包内部，以获取源 IP 地址、目的 IP 地址和端口。
为了正式定义公平性，路由器可以为每个连接维护一个单独的队列。当数据包到达时，路由器将其添加到相应的队列中。然后，路由器每次只需选择一个队列，从该队列的前端发送一个数据包。只要路由器以某种公平的方式选择队列，就能在连接之间强制实现公平性。
如果所有数据包大小相同，路由器可以采用轮询的方式选择队列（先从第一个队列发送，再从第二个队列发送，依此类推）。事实证明，这是有效的，即使并非所有连接需要相同的带宽。有些连接的数据包排队速度可能比其他连接慢。如果我们对不同带宽的连接应用轮询服务，如何计算每个连接分配到的带宽呢？例如，假设我们每秒可以发送 10 个数据包，而 A、B、C 分别每秒发送 8、6、2 个数据包。
如果我们以轮询方式发送数据包，每种类型的数据包每秒会发送多少个？我们可以将其建模为资源分配问题并求解。
例如，假设链路容量为 10。连接 A 请求 8，B 请求 6，C 请求 2。我们应该如何在这三个连接之间分配容量？如果我们追求公平，每个连接会得到 3.33。但 C 只请求了 2，所以我们给 C 它所请求的 2，不多给。
现在还剩下 8 的容量，A 和 B 仍需要分配。如果公平分配，每个会得到 4。这比它们请求的少，但我们无法满足它们的请求，所以我们给每个连接 4 的公平份额。
形式上，为了定义最大 - 最小公平性，假设 C 是路由器可用的总带宽。每个连接 ri 有一个带宽需求，我们需要为每个连接分配带宽 ai。最大 - 最小带宽分配为 ai=min (f,ri)，其中 f 是一个唯一值（对所有连接相同），使得∑ai=C。在这个等式中，min 项确保没有人得到超过其请求的带宽，而求和约束确保没有带宽被浪费。直观地说，f 是我们平等分配给每个连接的公平份额（因此所有连接使用同一个 f 值）。
另一种理解这个等式的方式是：存在一个神奇的公平份额数值，我们将其平等地分配给每个连接。如果你请求的带宽小于这个公平份额，你会得到这个公平份额（不会额外多给）。如果你请求的带宽大于这个公平份额，你的带宽会被限制在这个公平份额，而且其他任何人都不会得到比你更多的带宽。
在前面的例子中，f 是 4。A 和 B 得到了 f（它们想要更多），而 C 得到了 2（它想要更少）。
如果我们应用最大 - 最小公平性，这个等式保证了如果你没有得到你所需求的全部带宽，那么其他人也不会得到比你更多的带宽。轮询方法是符合最大 - 最小公平性的（假设数据包大小相同）。
如果不假设数据包大小相同呢？在现实中，数据包大小可能差异很大（例如 40 字节与 1500 字节）。理想情况下，我们希望执行逐位轮询，即轮流从每个连接的队列中发送一位。这在实际中并不可行（我们不会一次发送一位），但如果从理论上应用这种方式，我们可以记录每个数据包最后一位发送出去的时间。我们将其称为该数据包的截止时间。那么，一个公平的近似方法是按照截止时间的顺序发送数据包（即理论上最后一位应该发送的时间）。
有趣的事实：关于模拟公平排队的论文极具影响力，其两位合著者分别是 Scott Shenker（加州大学伯克利分校教授）和 Srinivasan Keshav（当时是 EECS 博士生）。
以下是两个连接上精确逐位公平排队的示例（当出现平局时，我们选择先到达的数据包）。
实际中的公平排队
公平排队有什么好处？它确保了连接之间的隔离，防止作弊的连接获取更多带宽。连接不需要实现 TCP（或 TCP 友好的替代协议），可以选择自己的（可能不友好的）拥塞控制算法。
从根本上说，公平排队的好处在于它对作弊和 RTT 变化等外部因素具有抵抗力。无论如何，每个连接都能获得特定链路的公平份额。但是，终端主机仍然需要发现并适应它们的公平份额（例如，如果请求过多，就减慢速度）。
公平排队有什么缺点？它比 FIFO 排队复杂得多。计算截止时间的过程很棘手，我们在这里没有展示相关算法。此外，路由器需要维护多个队列，并对每个数据包进行额外的解析工作。
在实际中，我们无法在路由器中实现完美的公平排队（在高速情况下过于复杂），但存在近似方法（例如赤字轮询）。现代路由器通常实现近似方法，但队列数量更少。更少的队列意味着不再是每个连接一个队列，而是隔离粒度更粗（例如每个客户一个队列）。
公平排队不能消除拥塞。它只是管理拥塞的另一种方式。例如，考虑这个瓶颈链路：它可能为每个连接分配 0.5 Gbps，这能防止作弊。但是，如果顶部的连接以 0.5 Gbps 运行，那么 0.4 Gbps 的数据将在紧邻的下一个链路上被丢弃。更好的分配方式是让顶部连接发送 0.1 Gbps，底部连接发送 0.9 Gbps。
根本问题在于，这个瓶颈链路不知道未来（下游）链路会发生什么。解决这个问题的唯一方法是让发送方主机减慢速度（路由器排队无济于事）。
公平排队给了我们每个连接的公平性，但从理论上讲，我们仍然需要问这是否是正确的公平模型。正如我们前面看到的，每个连接的公平性意味着拥有更多连接的人仍然能获得更多带宽。我们是否应该改为按源 - 目的对，或者可能按源来强制公平性？我们是否应该惩罚使用更拥塞链路的连接（占用更多稀缺资源）？
路由器辅助的拥塞控制
公平排队在特定链路上强制公平性，但它不会告诉发送方任何信息。如果路由器将信息反馈给发送方，以帮助发送方调整速率，会怎么样呢？
一种解决方案是让路由器直接告诉发送方它们应该使用的速率。我们可以在数据包中添加一个速率字段，让路由器在该字段中填入连接的公平份额。当数据包到达发送方时，发送方可读取头部并将速率设置为路由器所指示的值。这样，发送方就不需要动态调整来发现合适的速率了。
另一种解决方案是让路由器通知发送方有关拥塞的情况（不指定确切的速率）。这通过 IP 头部中的显式拥塞通知（ECN） 位来实现。如果数据包经过拥塞的路由器，路由器会将该位设置为 1。当接收方收到 ECN 位为 1 的数据包时，确认回复也会设置 ECN 位，这样发送方就会知道发生了拥塞。
路由器设置该位的方式有很多种。路由器可以非常谨慎，频繁设置该位，这会减少延迟但可能导致链路未被充分利用。或者，路由器可以更大胆，很少设置该位，这会增加延迟但能实现高链路利用率。
主机在收到该位被设置时的反应方式也有很多种。例如，主机可以假装数据包被丢弃，并相应地进行调整。
ECN 有什么好处？它解决了混淆数据损坏和拥塞的问题。它允许路由器更早地警告主机拥塞情况（例如在队列满之前），这可以减少延迟。而且它实现起来很轻量。
在实际中，有效的 ECN 需要大多数或所有路由器支持该协议，并在必要时设置该位。在现代互联网中，ECN 位在部分路由器上部署，但并非所有路由器都支持。然而，在小型网络中（例如数据中心的本地网络内部），当所有路由器都同意启用该位时，ECN 位可以有效发挥作用。