RFC896：Congestion Control in IP/TCP Internetworks，6 January 1984
本备忘录讨论了 IP/TCP 互联网络中拥塞控制的某些方面。它旨在激发对该主题的思考和进一步讨论。虽然对改进拥塞控制实施提出了一些具体建议，但本备忘录并未指定任何标准。
1、 介绍
拥塞控制是复杂网络中公认的问题。我们发现国防部的互联网协议 (Internet Protocol，IP) 是一种纯数据报协议，而传输控制协议 (Transmission Control Protocol，TCP) 是一种传输层协议，当一起使用时，会遇到由传输和数据报之间的交互引起的异常拥塞问题层。特别是，IP 网关容易受到我们称为“拥塞崩溃”的现象的影响，尤其是当此类网关连接带宽差异很大的网络时。我们已经开发出防止拥塞崩溃的解决方案。
这些问题通常没有被认识到，因为这些协议最常用于建立在 ARPANET IMP 技术之上的网络。基于 ARPANET IMP 的网络传统上具有统一的带宽和相同的交换节点，并且具有大量过剩的容量。对于大多数 IP/TCP 主机和网络来说，这种过剩的容量以及 IMP 系统限制主机传输的能力足以处理拥塞。然而，随着最近 ARPANET 分裂为两个互连网络以及连接到 ARPANET 的具有不同属性的其他网络的增长，依赖 IMP 系统的良性属性已不再足以让主机快速可靠地通信。现在，要在负载下成功运行网络，必须改进拥塞处理。
福特航空航天和通信公司及其母公司福特汽车公司运营着当今唯一的私有 IP/TCP 长途网络。该网络连接了四个设施（一个在密歇根州，两个在加利福尼亚州，一个在英格兰），其中一些设施具有广泛的本地网络。该网络与 ARPANET 交叉连接，但使用自己的长途线路；福特设施之间的流量通过私人租用线路流动，包括租用的跨大西洋卫星连接。所有交换节点都是纯 IP 数据包交换机，没有节点到节点的流量控制，并且所有主机都运行由 Ford 或 Ford Aerospace 编写或大量修改的软件。该网络中链路的带宽变化很大，从每秒 1200 到 10,000,000 位。总的来说，我们无法负担阿帕网拥有的超额长途带宽的奢侈，而且我们的长途链路在高峰期负载很重。因此，几秒钟的传输时间在我们的网络中很常见。
由于我们纯数据包方向、重负载和带宽变化很大，我们不得不解决 ARPANET/MILNET 社区刚刚开始认识到的问题。我们的网络对主机 TCP 实现的次优行为很敏感，无论是在我们自己的网络上还是在我们自己的网络外。我们投入了大量精力来检查各种条件下的 TCP 行为，并解决了一些普遍存在的 TCP 问题。我们在这里提出两个问题及其解决方案。许多 TCP 实现都有这些问题；如果对于给定的 TCP 实现，通过 ARPANET/MILNET 网关的吞吐量比通过单个网络的吞吐量差，则 TCP 实现很可能存在这些问题中的一个或两个。
2、 拥塞崩溃
在我们继续讨论这两个具体问题及其解决方案之前，有必要先描述一下当这些问题没有得到解决时会发生什么。在具有端到端重传的重载纯数据报网络中，随着交换节点变得拥塞，通过网络的往返时间增加，并且网络内传输的数据报数量也增加。这是负载下的正常行为。只要传输中的每个数据报只有一个副本，拥塞就受到控制。一旦开始重传尚未交付的数据包，就有可能出现严重的问题。
主机 TCP 实现预计会以增加的时间间隔多次重传数据包，直到达到重传间隔的某个上限。通常，这种机制足以防止严重的拥塞问题。然而，即使使用更好的自适应主机重传算法，网络上的突然负载也会导致往返时间上升得比发送主机的往返时间测量值更新得更快。当新的批量传输（例如文件传输）开始并开始填充大窗口时，就会发生此类加载。如果往返时间超过任何主机的最大重传间隔，该主机将开始将越来越多的相同数据报的副本引入网络。网络现在遇到了严重的问题。最终，交换节点中的所有可用缓冲区都将满，必须丢弃数据包。传送的数据包的往返时间现在已达到最大值。主机多次发送每个数据包，最终每个数据包的某个副本到达其目的地。这就是拥塞崩溃。
这种情况是稳定的。一旦达到饱和点，如果选择要丢弃的数据包的算法是公平的，网络将继续在降级条件下运行。在这种情况下，每个数据包都被多次传输，吞吐量减少到正常的一小部分。我们已经通过实验将我们的网络推到了这种状态并观察了它的稳定性。往返时间可能会变得如此之大，以至于由于主机超时而导致连接中断。
在 ARPANET/MILNET 系统中通常不会出现拥塞崩溃和病理性拥塞，因为这些网络具有大量的过剩容量。在连接不通过 IP 网关的情况下，IMP 到主机的流量控制机制通常可以防止拥塞崩溃，特别是因为 TCP 实现往往会针对与纯 ARPANET 情况相关的时间常数进行很好的调整。然而，除了 ICMP源抑制消息之外，当 TCP 在 ARPANET / MILNET 上运行并且数据包在网关处被丢弃时，没有什么能从根本上防止拥塞崩溃。值得注意的是，一些行为不良的主机本身可以使网关拥塞并阻止其他主机通过流量。我们已经在 ARPANET 上的某些主机（我们已与他们的管理员私下通信）中反复观察到这个问题。
向网关添加额外的内存不会解决问题。添加的内存越多，在数据包被丢弃之前往返时间必须变得越长。因此，拥塞崩溃的开始将被延迟，但是当崩溃发生时，网络中更大比例的数据包将是重复的，吞吐量甚至会更糟。
3、 两个问题
已经观察到 TCP 实现工程的两个关键问题；我们称这些为小包问题和源抑制问题。第二个正在由几个实现者解决；第一个通常被认为（错误地）解决了。我们发现，一旦解决了小数据包问题，源抑制问题就变得更容易处理了。因此，我们首先介绍小数据包问题及其解决方案。
3.1、 小包问题
有一个与小数据包相关的特殊问题。当 TCP 用于传输源自键盘的单字符消息时，典型的结果是为每个有用的数据字节传输 41 字节的数据包（一个字节的数据，40 个字节的标头）。这 4000% 的开销很烦人，但在轻负载网络上是可以容忍的。然而，在负载很重的网络上，这种开销导致的拥塞可能导致数据报丢失和重传，以及交换节点和网关中的拥塞导致过多的传播时间。在实践中，吞吐量可能会下降到 TCP 连接被中止的程度。
这个经典问题是众所周知的，最早在 1960 年代后期在 Tymnet 网络中得到解决。那里使用的解决方案是对每单位时间生成的数据报的数量施加限制。这个限制是通过将小数据包的传输延迟到很短（200-500 毫秒）的时间过去来强制执行的，希望在计时器用完之前，另外一个或两个字符可以添加到同一个数据包中。提高用户可接受性的附加功能是在接收到控制字符（例如回车符）时抑制时间延迟。
此技术已用于 NCP Telnet、X.25 PAD 和 TCP Telnet。它的优点是易于理解，并且实施起来并不太难。它的缺陷是很难想出一个让所有人都满意的时间限制。一个足够短的时间限制以在每秒 10M 比特的以太网上提供高响应服务将太短以防止拥塞崩溃在一个具有 5 秒往返时间的重负载网络上；相反，如果时间限制足够长以处理负载过重的网络，则会在以太网上产生沮丧的用户。
3.2、 小包问题的解决方案
显然，一种适应性方法是可取的。人们会期望根据 TCP 观察到的往返延迟提出自适应数据包间时间限制。虽然这样的机制当然可以实施，但没有必要。已经发现了一个简单而优雅的解决方案。
解决方案是，如果任何先前在连接上传输的数据仍未得到确认，则在来自用户的新传出数据到达时禁止发送新的 TCP 段。这种抑制是无条件的；不需要计时器、接收数据大小的测试或其他条件。实现通常需要在 TCP 程序中使用一两行。
乍一看，这个解决方案似乎意味着 TCP 行为的急剧变化。事实并非如此。一切都在最后。让我们看看为什么会这样。
当用户进程写入 TCP 连接时，TCP 会收到一些数据。它可以保存该数据以备将来发送或可以立即发送数据包。如果它现在不发送，它通常会在传入数据包到达并更改系统状态时稍后发送数据。状态以两种方式之一改变；传入的数据包确认远程主机已接收到的旧数据，或宣布远程主机中缓冲区空间的可用性可用于新数据。（这最后被称为“更新窗口”）。每次数据到达连接时，TCP 必须重新检查其当前状态，并且可能会发送一些数据包。因此，当我们省略从用户到达时发送数据时，我们只是将其传输推迟到下一条消息从远程主机到达。除非连接先前空闲或与另一端的通信已丢失，否则消息必须始终尽快到达。在第一种情况下，空闲连接，我们的方案将导致每当用户写入 TCP 连接时发送一个数据包。因此我们不会在空闲状态下死锁。在第二种情况下，远程主机出现故障，发送更多数据无论如何都是徒劳的。请注意，我们没有采取任何措施来抑制正常的 TCP 重传逻辑，因此丢失消息不是问题。
对该方案在各种条件下的行为的检查表明该方案在所有情况下都有效。要检查的第一个案例是我们想要解决的案例，即面向字符的 Telnet 连接。让我们假设用户每 200 毫秒向 TCP 发送一个新字符，并且连接是通过以太网进行的，往返时间包括 50 毫秒的软件处理。没有任何防止小包拥塞的机制，每个字符发送一个包，响应最优。开销将是 4000%，但这在以太网上是可以接受的。经典的计时器方案，限制为每秒 2 个数据包，将导致每个数据包发送两个或三个字符。因此，即使在高带宽以太网上这是不必要的，响应也会降级。开销将下降到 1500%，但在以太网上这是一个糟糕的权衡。在我们的方案中，用户输入的每个字符都会找到具有空闲连接的 TCP，并且该字符将被立即发送，就像在无控制的情况下一样。用户不会看到任何可见的延迟。因此，我们的方案与无控制方案的性能一样好，并且提供了比定时器方案更好的响应能力。
要检查的第二种情况是相同的 Telnet 测试，但通过具有 5 秒往返时间的长途链路进行测试。如果没有任何防止小数据包拥塞的机制，5 秒内将发送 25 个新数据包。（这里的开销是 4000%。）使用经典的计时器方案，以及每秒 2 个数据包的相同限制，仍然会有 10 个数据包未完成并导致拥塞。当然，发送许多数据包不会改善往返时间；通常情况会更糟，因为数据包会争用线路时间。开销现在下降到 1500%。然而，在我们的方案中，来自用户的第一个字符将找到空闲的 TCP 连接并立即发送。接下来的 24 个字符以 200 毫秒的间隔从用户到达，将等待来自远程主机的消息。当第一个数据包在 5 秒结束时收到 ACK 时，将发送一个包含 24 个排队字符的数据包。因此，我们的方案将开销减少到 320%，而不会影响响应时间。我们的方案通常会改进响应时间，因为减少了数据包开销，比经典定时器方案减少了 4.7 倍。这个因素会减少拥塞，往返延迟会急剧减少。对于这种情况，我们的方案比其他任何一种方法都有显着的优势。
* 这个问题在纯 ARPANET 情况下不会出现，因为当未完成的数据包计数变得过多时，IMP 会阻塞主机，但在纯数据报本地网（如以太网）或纯数据报网关（如当涉及 ARPANET / MILNET 网关）时，可能会有大量未完成的小数据包。
我们将我们的方案用于所有 TCP 连接，而不仅仅是 Telnet 连接。让我们看看使用我们的技术进行文件传输数据连接会发生什么。将再次考虑这两种极端情况。
和以前一样，我们首先考虑以太网情况。用户现在以 512 字节块的形式向 TCP 写入数据，速度与 TCP 接受它们的速度一样快。用户对 TCP 的第一次写入将开始进行；我们的第一个数据报将是 512+40 字节或 552 字节长。用户对 TCP 的第二次写入不会导致发送，但会导致块被缓冲。假设用户在第一个 ACK 返回之前填满了 TCP 的传出缓冲区。然后当 ACK 进来时，所有排队的数据将被发送到窗口大小。从那时起，窗口将保持满状态，因为每个 ACK 启动一个发送周期并发送排队的数据。因此，在仅发送一个块的一个往返时间初始阶段之后，我们的方案稳定到最大吞吐量条件。以太网上的启动延迟只有50ms，因此启动瞬态无关紧要。在这种情况下，所有三种方案都提供了等效的性能。
最后，让我们看看通过 5 秒往返时间连接的文件传输。同样，在第一个 ACK 返回之前，只会发送一个数据包；然后窗口将被填充并保持完整。由于往返时间为 5 秒，因此前 5 秒仅传输 512 字节的数据。假设一个2K的窗口，一旦第一个ACK进来，就会发送2K的数据，之后会保持每5秒2K的稳定速率。仅在这种情况下，我们的方案不如定时器方案，区别仅在于启动瞬态；稳态吞吐量相同。在上述条件下，naive 方案和定时器方案都需要 250 秒来传输 100K 字节的文件，而我们的方案需要 254 秒，相差 1.6%。
因此，对于所有检查的情况，我们的方案提供了至少 98% 的其他方案的性能，并且在具有长往返时间的路径上提供了 Telnet 性能的显着改进。我们在福特航空航天软件工程网络中使用我们的方案，并且能够通过以太网运行屏幕编辑器并与远程 TOPS-20 主机通信，在这两种情况下都具有更高的性能。
3.3、 使用 ICMP 进行拥塞控制
在解决了小包拥塞问题以及我们自己网络中小包过度拥塞的问题后，我们将注意力转向了通用拥塞控制问题。由于我们自己的网络是没有节点到节点流量控制的纯数据包，因此在 IP 标准下我们唯一可用的机制是 ICMP源抑制消息。通过仔细处理，我们发现这足以防止严重的拥塞问题。我们确实发现有必要注意我们的主机和交换节点关于源抑制消息的行为。
3.4、 何时发送 ICMP源抑制
当前的 ICMP 标准规定，无论何时丢弃数据包都应发送 ICMP源抑制消息，此外还可以在网关发现自身资源短缺时发送。这里有一些歧义，但很明显，在不发送 ICMP 消息的情况下丢弃数据包是违反标准的。
我们的基本假设是在正常网络操作期间不应丢弃数据包。因此，我们希望在发送者使交换节点和网关过载之前对其进行节流。我们所有的交换节点都会在缓冲区空间耗尽之前发送 ICMP源抑制消息；在发送 ICMP源抑制之前，它们不会等到有必要丢弃消息。正如我们对小数据包问题的分析所证明的那样，仅仅提供大量缓冲不是解决方案。一般来说，我们的经验是，当大约一半的缓冲空间耗尽时，应该发送源抑制；这不是基于广泛的实验，而是一个合理的工程决策。可以主张一种自适应方案，根据最近的经验调整抑制发生阈值；我们还没有发现这有必要。
存在仅在一个以上的数据包被丢弃后才生成源抑制的其他网关实现。我们认为这种方法是不可取的，因为任何基于丢弃数据包来控制拥塞的系统都会浪费带宽，并且在重负载下可能容易发生拥塞崩溃。我们的理解是，极不情愿地产生源抑制的决定源于对确认流量将被抑制并且这将导致连接失败的恐惧。如下所示，主机实现中对源抑制的适当处理消除了这种可能性。
3.5、 收到 ICMP源抑制后该怎么办
当 ICMP 收到源抑制时，我们会通知 TCP 或该层的任何其他协议。我们的 TCP 实现的基本操作是减少与源抑制中提到的主机的连接上未完成的数据量。通过使发送 TCP 表现得好像远程主机的窗口大小已减小来应用此控制。我们的第一个实现很简单但很有效；一旦接收到源抑制，当窗口不为空时，我们的 TCP 就好像窗口大小为零一样。这种行为一直持续到收到一定数量的（目前为 10 个）ACK，此时 TCP 恢复正常运行。
* Linkabit Corporation 的 David Mills 此后对其 DCN 中未完成数据包的计数实施了类似但更精细的限制系统。额外的复杂性似乎在吞吐量上产生了适度的增长，但我们还没有进行正式的测试。这两种实现都有效地防止了交换节点中的拥塞崩溃。
* ARPANET RFC 792 是现行标准。美国国防通信局告知我们，MIL-STD-1777 中对 ICMP 的描述不完整，将从该标准的未来修订版中删除。
因此，源抑制具有将连接限制为有限数量（可能是一个）未完成消息的效果。因此，通信可以继续，但速率会降低，这正是所需的效果。
该方案的重要特性是源抑制不禁止发送确认或重传。完全在 IP 层内实现源抑制通常是不成功的，因为 IP 缺乏足够的信息来正确地限制连接。阻止确认往往会产生重传，从而产生不必要的流量。阻止重传可能会因重传超时而导致连接丢失。我们的方案将在严重过载的情况下保持连接活跃，但每个连接的带宽会减少。
与 TCP 处于同一层的其他协议也应响应源抑制。在每种情况下，我们都会建议应限制新流量，但应正常处理确认。唯一严重的问题来自用户数据报协议，通常不是主要的流量生成器。我们尚未在这些协议中实施任何限制；所有都由 ICMP 传递源抑制消息，但忽略它们。
4、 网关自卫
正如我们所展示的，网关容易受到主机拥塞管理不善的影响。生成过多流量导致的主机不当行为不仅会阻止主机自己的流量通过，还会干扰其他无关的流量。该问题可以在主机级别处理，但由于一台故障主机可能会干扰其他主机，因此未来的网关应该能够保护自己免受讨厌或恶意主机的此类行为的影响。我们提供一些基本的自卫技巧。
1983 年末有一次，ARPANET 主机中的 TCP 错误导致主机以ARPANET 接受它们的速度疯狂地生成相同数据报的重传。连接我们的网络与 ARPANET 的网关已经饱和，几乎没有有用的流量可以通过，因为网关到 ARPANET 的带宽比到我们的网络的带宽要多。网关忙着发送 ICMP源抑制消息，但故障主机忽略了它们。这持续了几个小时，直到故障主机崩溃。在此期间，我们的网络实际上与 ARPANET 断开了连接。
* 这遵循控制工程的格言“永远不要打扰比例控制，除非 bang-bang 不起作用”。
当网关被迫丢弃数据包时，该数据包由网关自行选择。做出此决定的经典技术是丢弃最近收到的数据包，或最长传出队列末尾的数据包。我们建议一个有价值的实际措施是丢弃来自主机的最新数据包，该主机源自当前在网关中排队的最多数据包。该策略倾向于平衡使用网关的主机之间的吞吐量。我们还没有尝试过这种策略，但它似乎是网关自我保护的合理起点。
另一种策略是如果新到达的数据包与队列中已有的数据包重复，则丢弃该数据包。如果使用散列技术，则此检查的计算负载不是问题。此检查不会防范恶意主机，但会针对重传控制不佳的 TCP 实现提供一些保护。如果本地主机被调整为与本地网络很好地工作，则快速本地网络和较慢的长途网络之间的网关可能会发现此检查很有价值。
理想情况下，网关应该检测故障主机并压制它们；这种检测在纯数据包系统中是困难的。但是，未能响应 ICMP源抑制消息应被视为网关采取措施断开主机连接的理由。检测此类故障并非易事，但值得进一步研究。
5、结论
与纯数据报网络相关的拥塞控制问题很困难，但存在有效的解决方案。如果 IP/TCP 网络要在高负载下运行，TCP 实现必须以至少与此处描述的方法一样有效的方式解决几个关键问题。
