拥塞控制原理
拥塞的危害
回想一下，如果许多数据包同时到达路由器（例如突发流量），而路由器需要通过同一条链路发送这些数据包，那么路由器会发送一个数据包，将其他数据包放入队列（稍后发送）。
更一般地说，如果数据包的输入速率超过了链路能够维持的输出速率，路由器将无法跟上输入数据包的速度。此时路由器处于拥塞状态，需要将数据包放在队列中等待发送。队列会导致数据包延迟。如果队列本身已满且仍有数据包进入，那么数据包可能会被丢弃。
该图显示了具有突发到达的排队系统的性能。虚线表示链路的容量（最大负载）。随着负载的增加，数据包的延迟会增大。
当到达是突发的时，我们实际上无法充分利用链路的最大容量。我们必须在负载和数据包延迟之间找到适当的性能权衡。
注意，在达到虚线之前，图表就已经开始向上倾斜。这意味着即使没有数据包被丢弃，排队已经在延迟数据包了。当我们达到最大利用率并开始丢包时，队列已经造成了非常大的数据包延迟。
拥塞的简要历史
20 世纪 80 年代，TCP 没有实现任何拥塞控制。发送速率仅受流量控制（接收方缓冲区容量）的限制。
如果数据包被丢弃，发送方会以同样快的速率反复重发该数据包，直到数据包到达为止。更明智的做法是减慢发送速度，以避免数据包被丢弃并减少堵塞网络的副本，但早期的 TCP 实现并没有这样做。
1986 年 10 月，互联网开始遭受一系列拥塞崩溃，互联网的容量大幅下降。加州大学伯克利分校到劳伦斯伯克利实验室（两个地点相距约 400 码）之间的一条链路，其吞吐量从 32 Kbps（32,000 bps）下降到 40 bps。
Michael Karels（加州大学伯克利分校本科生）和 Van Jacobson（劳伦斯伯克利实验室研究员）当时正在研究伯克利 Unix 系统（有影响力的早期操作系统）中的网络栈，他们意识到网络中有数千个相同数据包的副本，因为每个人都在尝试重发被丢弃的数据包。
Karels 和 Jacobson 开发了一种解决该问题的算法，该算法后来演变为现代的 TCP 拥塞控制算法。他们的修复是对 TCP 本身的修改，其中窗口大小（决定数据包发送速率）会根据丢包情况动态调整。
由于他们的解决方案是对 TCP 逻辑的修改（回想一下，TCP 是在操作系统中实现的），因此不需要对路由器或应用程序进行升级。
TCP 拥塞控制是互联网设计具有临时性的众多例子之一。Karels 和 Jacobson 的补丁只是 BSD 操作系统的 TCP 实现中额外的几行代码。这个补丁奏效了，因此很快被采用。从那以后，拥塞控制这一主题得到了广泛研究，并取得了一些改进，但最终，原始补丁中的核心思想一直沿用至今。从那以后，互联网再也没有发生过拥塞崩溃，因此最初的修复经受住了时间的考验。
为什么拥塞控制很难？
为了理解为什么拥塞控制是一个难题，考虑以下网络拓扑图。主机 A 应该以什么速率发送流量？
这取决于目的地，因此 A 不能只为所有目的地设定一个固定的速率。例如，如果 A 与 C 通信，那么 A 可以以 10 Gbps 的速率发送数据包。
如果 A 与 F 通信呢？这条路径上的瓶颈链路（容量最小的链路）是 2 Gbps，因此 A 可能应该以 2 Gbps 的速率发送数据包。
如果 A 与 E 通信呢？
这取决于流量在 A 和 E 之间采取的路径。如果流量通过 R3 走下方路径，那么 A 可以以 10 Gbps 的速率发送数据包。但如果流量通过 R2 走上方路径，那么 A 现在只能以 1 Gbps 的速率发送数据包。
到目前为止，一个结论是我们的拥塞控制算法需要以某种方式了解数据包所走路径上的带宽和瓶颈。
此外，回想一下，网络拓扑会随着新链路的添加或链路的中断而随时间变化。这意味着仅一次了解路径是不够的。我们的算法需要能够适应网络拓扑的变化。
到目前为止，我们假设 A 是网络上唯一发送流量的主机，并且 A 可以使用每条链路的全部容量。但是如果其他连接也在使用带宽呢？
在这个例子中，A 和 F 有一个连接，B 和 E 有一个连接。这两个连接看起来应该是完全独立的（不同的发送方，不同的接收方），但实际上，它们的路径在网络中共享一条链路。
如果我们希望这两个连接公平地共享这条链路上的容量，那么 A 和 B 可能应该各以 1 Gbps 的速率发送。
如果在 G 和 D 之间启动一个新的连接呢？A 应该改变其 1 Gbps 的速率吗？（目前还没有正式的算法，只需考虑以合理的方式使用带宽。）
首先，注意 G-D 和 B-E 连接正在共享一条链路。这意味着这两个连接必须将其速率降至 0.5 Gbps。
现在，回顾一下 A-F 和 B-E 共享的 2 Gbps 链路，B-E 在这条链路上仅使用 0.5 Gbps。这意味着 A 可以将其速率提高到 1.5 Gbps。
这里发生了什么？G-D 连接被创建，其路径与 A-F 连接没有共享任何链路。然而，这个看似无关的连接导致 A-F 连接的速率增加。连接之间可能会间接影响其他连接，即使这两个连接没有共享任何链路！
总之：当发送方试图确定数据包的发送速率时，它必须考虑：目的地、到该目的地的路径、沿该路径共享链路的连接、与这些连接共享链路的连接（间接竞争）等等。拥塞控制是一个难题，因为网络中的所有连接都相互依赖，以确定各自的最佳发送速率。
更根本地说，拥塞控制是一个资源分配问题。带宽是一种有限的资源，每个连接都需要一定数量的该资源，我们需要决定为每个连接分配多少带宽。
资源分配是计算机科学中的一个经典问题（例如 CPU 调度和内存分配算法）。然而，与某些资源分配问题不同，一个连接的分配变化可能会对所有其他连接产生全局影响。此外，每当创建或销毁一个连接时，分配都必须改变。因此，拥塞控制比传统的资源分配问题更复杂，事实上，我们甚至没有一个正式的模型来定义这个问题。
与传统的资源分配问题不同（在传统问题中，算法提前知道资源（例如 CPU 时间）和作业（例如进程）），没有一个全局的 “智囊” 能够看到整个网络来分配资源。我们的解决方案必须是去中心化的，即每个发送方自行决定其分配（尽管每个人的决定高度相互依赖）。
良好拥塞控制算法的目标
从资源分配的角度来看，一个良好的拥塞控制算法需要实现三个目标。
我们希望资源分配是高效的。链路不应过载，并且数据包的延迟和丢失应最小化。此外，链路应尽可能被充分利用。
我们还希望连接之间的资源分配是公平的。我们稍后会正式定义公平性，但大致来说，每个连接应该共享可用容量的相等部分。
我们希望找到一个能够在这些目标之间取得良好平衡的解决方案。优化一个目标而牺牲其他目标是可能的，但这会导致糟糕的解决方案。例如，我们可以通过让所有人都极快地发送数据包来确保链路的最大利用率（糟糕的解决方案，会导致拥塞）。或者，我们可以通过让所有人都极慢地发送数据包来确保最小的丢包率（糟糕的解决方案，无法充分利用容量）。
从更实际的系统角度来看，我们提出的解决方案需要具有可扩展性和去中心化的特点。我们的解决方案还应该能够适应网络的变化（例如拓扑变化、连接的创建和销毁）。
解决方案的设计空间
如前所述，Karels 和 Jacobson 通过修补操作系统中的 TCP 实现来修复 TCP 拥塞控制。但是，如果我们可以从头开始重新设计互联网，还有哪些其他可能的拥塞控制设计呢？
一种可能的替代设计基于预留。发送方可以提前请求带宽，然后在连接结束后释放该带宽。如前所述，在整个网络中维护预留会带来许多技术困难。这种方法还有一个问题，即它假设发送方提前知道它需要的带宽，而事实并非如此。
另一种替代设计基于定价。打个比方，考虑高速公路上的收费快车道（仅向付费司机开放的专用车道）。使用收费快车道的价格取决于高速公路的拥堵程度。当高速公路上车辆很少时，使用收费车道非常便宜；当交通拥堵时，使用收费车道则更贵。另一种形式的拥塞定价出现在飞机票中，在繁忙时段（例如节假日）票价更高。
要将拥塞定价应用于互联网，你的互联网服务提供商（ISP）可以在你的网页浏览器中添加一个按钮，允许你支付额外费用以获得更高的互联网速度，费用可以根据互联网的拥堵程度而变化。然后，路由器可以优先发送付费更多用户的数据包，丢弃未付费用户的数据包。关于互联网拥塞定价的研究已经存在，经济学家有时声称，如果带宽是一种稀缺商品，那么市场结构将导致最优解。拥塞定价尚未被广泛部署，因为它需要某种将支付与拥塞联系起来的商业模式。
所有现代拥塞控制算法（包括我们将要研究的那些）都基于动态调整。主机动态了解当前的拥塞程度，并相应地调整其发送速率。在实践中，动态调整是一种实用的解决方案，因为它可以轻松推广。这种方法不依赖任何商业模式（定价所需），也不假设用户提前知道所需的带宽（预留所需）。
动态调整确实需要良好的 “公民意识”。TCP 需要网络上的所有参与者共同努力，公平地共享资源。例如，当一个新连接开始使用链路时，其他连接需要减速并共享带宽。
在动态调整方法中，有两大类解决方案。在基于主机的拥塞控制算法中，发送方监控性能并相应地调整其速率。这些算法完全在发送方实现，不需要路由器的特殊支持。对 TCP 的修改就是一种基于主机的算法，目前已被广泛部署。
在路由器辅助的拥塞控制算法中，路由器会明确地将拥塞信息发送回发送方，以帮助发送方调整其速率。拥塞发生在路由器处，因此路由器处于提供拥塞信息的有利位置。近年来，路由器辅助算法已经得到部署，特别是在数据中心中。
一些路由器辅助算法发送的信息很少，例如一个表示拥塞的比特，而其他算法发送更详细的信息，例如发送方应使用的确切速率。
请注意，在这两种情况下，路由器都在向发送方发出拥塞信号。在路由器辅助算法中，路由器会明确发送关于其拥塞程度的消息。相比之下，在基于主机的算法中，发送方不会收到来自路由器的明确反馈。相反，发送方使用来自路由器的隐含线索（例如数据包被丢弃或延迟）来推断路由器处于拥塞状态。
在这个拥塞控制方法的分类中，我们将重点关注动态调整方法，并且在动态调整解决方案的范围内，我们将重点关注基于主机的解决方案。
（注：文档部分内容可能由 AI 生成）