4.3 慢启动(Slow Start)
当发送端使用了接近网络的可用容量时，刚刚介绍的增加机制是一种合理的方法，但如果从头开始时，需要花费太长的时间。因此，TCP 提供了第二种机制，被反直觉的称为慢启动(slow start)，用于从冷启动快速增加拥塞窗口。慢启动可以成倍增加拥塞窗口，而不是线性增加。
具体来说，发送端首先将CongestionWindow设置为一个包。当这个包的 ACK 到达时，TCP 将CongestionWindow加 1，然后发送两个包。在收到相应的两个 ACK 后，TCP 将CongestionWindow加 2，然后发送 4 个数据包。最终的结果是，TCP 在每次 RTT 传输中有效增加了一倍的数据包数量。图 24 显示了慢启动期间传输的数据包数量的增长，可以将其与图 22 所示的线性增长进行比较。
图 24. 慢启动期间传输的数据包。
为什么指数机制会被称为"慢"确实令人费解，但从其历史背景来看，这是有道理的。不要将慢启动与前一节的线性机制进行比较，而是与 TCP 的原始行为进行比较。考虑一下，当建立连接时，发送端首先(即当前没有信息包在传输时)开始发送数据包，会发生什么情况。如果发送端发送的包数量和窗口允许的数量一样多(也正是 TCP 在开发慢启动之前所做的)，那么即使网络中有相当大的可用带宽，路由器也可能无法消耗这些突发的包，因为这完全取决于路由器上有多少缓冲空间可用。因此，慢启动被设计为间隔发送数据包，这样就不会发生突发流量。换句话说，尽管它的指数增长比线性增长要快，但慢启动比一次性发送整个通告窗口的数据要"慢"得多。
实际上，慢启动有两种不同的情况。第一种情况是在连接刚开始建立的时候，此时发送端不知道在给定时间里能传输多少包。(请记住，今天 TCP 链接运行在从 1 Mbps 到 40 Gbps 的各种网络情况下，所以发送端没有办法知道网络容量。)在这种情况下，慢启动每过一个 RTT 就加倍CongestionWindow，直到发生了丢包，然后由于超时导致指数减少并将CongestionWindow除以 2。
第二种情况更微妙一些，当连接在等待超时失效，就会发生这种情况。回想一下 TCP 的滑动窗口算法是如何工作的，当一个包丢失时，发送端最终会到达一个状态，在这个状态上它已经发送了通告窗口允许的尽可能多的数据，因此在等待一个不会到达的 ACK 时阻塞。最终会发生超时，但此时没有包在传输，这意味着发送端将不会收到 ACK 来触发新包的传输。相反，发送端将接收一个累积的 ACK，从而重新打开整个通告窗口，但是，如上所述，发送端将使用慢启动来重新启动数据流，而不是一次将整个窗口的数据全部发送到网络上。
虽然发送端再次使用慢启动，但现在知道的信息比连接开始时更多。具体来说，发送端具有当前(且有用)的CongestionWindow值，作为丢包的结果，这个值是上次丢包之前存在的CongestionWindow值除以 2，我们可以把它看作目标拥塞窗口。慢启动快速增加发送速率到达这个值，然后增加的窗口将超过这个值。注意，我们需要小小的记录一下，因为我们想要记住由指数减少导致的目标拥塞窗口，以及慢启动使用的实际拥塞窗口。为了解决这个问题，TCP 引入了一个临时变量来存储目标窗口，通常称为CongestionThreshold，被设置为与CongestionWindow的值相等，这个值是由指数减少产生的。然后，变量CongestionWindow被重置为一个包，并且随着每一个 ACK 的接收而增加一个包，直到到达CongestionThreshold，然后每过一个 RTT 再增加一个包。
换句话说，以下代码段定义了 TCP 如何增加拥塞窗口:
{ u_int cw = state->CongestionWindow; u_int incr = state->maxseg; if (cw > state->CongestionThreshold) incr = incr * incr / cw; state->CongestionWindow = MIN(cw + incr, TCP_MAXWIN); }
其中state表示特定 TCP 连接的状态，并定义了允许增加的拥塞窗口的上限。
图 25 显示了 TCP 的CongestionWindow是如何随着时间的推移而增加和减少的，并用来说明慢启动和线性增加/指数减少的相互作用。这个图是从实际的 TCP 连接中获取的，并显示了随着时间推移的CongestionWindow的当前值(带颜色的线)。
图 25. TCP 拥塞控制行为。彩色线=随时间推移的 CongestionWindow 的值；顶部实心标记=超时；顶部散列标记=每个数据包传输的时间；竖线=最终重传的数据包的第一次传输时间。
关于这个图示，有几个地方需要注意。首先是连接开始时，拥塞窗口快速增加。这对应于最初的慢启动阶段。慢启动阶段继续，直到在大约 0.4 秒时丢了几个包，此时CongestionWindow在大约 34 KB 时变平。(下面将讨论为什么这么多数据包在慢启动过程中丢失。) 拥塞窗口变平的原因是由于丢失了几个包，没有 ACK 到达。事实上，在此期间没有发送任何新数据包，这一点从顶部缺少散列标记就可以看出。超时最终大约在 2 秒发生，此时拥塞窗口被除以 2(即从大约 34 KB 削减到大约 17 KB)，并且将CongestionThreshold设置为这个值，慢启动导致CongestionWindow被重置为一个包，并从那里开始加速。
图中没有足够的细节来查看当两个数据包在 2 秒后丢失时到底会发生什么，所以我们直接跳到发生在 2 秒到 4 秒之间的拥塞窗口的线性增加。大约 4 秒时，同样是由于丢包，拥塞窗口变平。在 5.5 秒的时候:
- 发生了超时，导致拥塞窗口被除以 2，从大约 22 KB 下降到 11 KB，而
CongestionThreshold被设置为这个值。 CongestionWindow被重置为一个包，发送方进入慢启动。- 慢启动导致
CongestionWindow指数增长，直到达到CongestionThreshold。 - 然后
CongestionWindow线性增长。
当大约 8 秒时再次发生超时，重复相同的模式。
现在我们回到这个问题: 为什么在最初的慢启动期间会丢失这么多包。此时，TCP 试图了解网络上有多少带宽可用，这是一项艰巨的任务。如果发送端在这个阶段不主动，例如，如果只是线性增加拥塞窗口，那么需要很长时间才能发现有多少带宽可用。这可能会对此连接的吞吐量产生重大影响。另一方面，如果发送端在这个阶段比较激进，那么就需要冒着被网络丢弃半个窗口的数据包的风险。
为了了解指数增长过程中会发生什么，考虑这样一种情况: 发送端仅仅能够成功通过网络发送 16 个包，导致网络的拥塞窗口翻倍至 32。然而，假设网络恰好有足够的容量支持来自这个发送端的 16 个数据包。可能的结果是，在新的拥塞窗口下发送的 32 个数据包中，有 16 个将被网络丢弃，实际上这是最坏的结果，因为一些数据包会被缓冲到某个路由器中。随着网络带宽时延积的增加，问题将变得越来越严重。例如，1.8 MB 的带宽时延积意味着每个连接在开始时都有可能丢失高达 1.8 MB 的数据。当然，需要假定发送端和接收端都实现了"大窗口(big windows)"扩展。
也有人探索慢启动的替代方案，即发送端试图通过更复杂的方法估计可用带宽。其中一个例子叫做快启动(quick-start) 。其基本思想是，TCP 发送端通过将请求的速率作为 IP 选项放入 SYN 包中，从而要求比慢启动所允许的更大的初始发送速率。沿路路由器可以检查该选项，评估该流出口链路当前的拥塞水平，并决定该速率是否可以接受，或者是否可以接受较低的速率，或者是否应该使用标准慢启动。当 SYN 到达接收端时，要么包含路径上所有路由器都可以接受的速率，要么包含路径上一个或多个路由器不能支持快启动请求的指示。在前一种情况下，TCP 发送方使用该速率开始传输，在后一种情况下，回到标准慢启动状态。如果允许 TCP 以更高速率开始发送，会话可以更快到达填满流水线的状态，而不用花费许多往返时间来完成此操作。
显然，对 TCP 进行这种增强的挑战之一是，与标准 TCP 相比，需要来自路由器的更多合作。如果路径中的某个路由器不支持快启动，则整个系统将恢复到标准慢启动。因此，在这类增强进入互联网之前可能还需要很长一段时间，目前更可能用于受控的网络环境(例如，研究网络)。
4.4 快速重传和快速恢复
目前为止所介绍的机制是将拥塞控制添加到 TCP 的最初提议的一部分，因为相应实现被包含在 1988 年的 4.3 BSD Unix 的 Tahoe 发行版中，因此被统称为 TCP Tahoe。一旦被广泛部署，经验表明 Tahoe 的一些问题随后被 1990 年初的 TCP Reno (4.3BSD-Reno 版本的一部分)解决。本节将介绍相关经验以及 Reno 解决问题的方法。
简言之，TCP 超时的粗粒度实现导致长时间的连接在等待计时器过期时失效。一种称为快速重传(fast retransmit) 的启发式方法有时会比常规超时机制更早触发丢失数据包的重传。快速重传机制不替换常规超时，只是增加了另一种可以更及时检测丢包的方法。
其思想是，每当一个数据包到达接收端，接收端回应一个 ACK，即使这个序列号已经被确认。因此，当一个乱序包到达，TCP 还不能确认包中包含的数据(因为之前的数据还没有到达)，TCP 会重新发送和上次相同的 ACK。
相同 ACK 的第二次传输称为重复 ACK(duplicate ACK) 。当发送端看到一个重复 ACK 时，就知道另一方一定收到了一个顺序错误的包，这表明前一个包可能已经丢失了。不过也有可能之前的包只是被延迟了而不是丢失了，所以发送端会等待，直到看到一定数量的重复 ACK(实际上是 3 个)，然后重新发送丢失的包。这里内置的假设(在实践中得到了很好的验证)是，乱序数据包比丢失的数据包要少得多。
图 26. 基于重复 ACK 的快速重传。
图 26 说明了重复 ACK 如何触发快速重传。本例中，目的地接收到包 1 和包 2，但包 3 在网络中丢失。因此，当数据包 4 到达时，目的地将对数据包 2 发送一个重复 ACK，当数据包 5 到达时再次发送，以此类推。(为了简化示例，我们从包 1、2、3 等的角度考虑，而不是考虑每个字节的序列号。) 当发送方看到数据包 2 的第三个重复 ACK(因为接收方收到了数据包 6 而发送的 ACK)时，会重新发送数据包 3。请注意，当包 3 的重传副本到达目的地时，接收方随后将包括包 6 在内的所有内容的累积 ACK 发送回发送端。
图 27. 快速重传 TCP 图示。彩色线=CongestionWindow；实心标记=超时；散列标记=每个数据包传输的时间；竖线=最终重传的数据包第一次传输的时间。
图 27 展示了具有快速重传机制的 TCP 版本的行为。将此图示与图 25 进行比较是很有意思的事情，拥塞窗口保持扁平且消除了无法发送数据包的时间。通常，这种技术能够消除典型 TCP 连接上大约一半的粗粒度超时，从而使吞吐量比使用其他方法可以实现的性能提高约 20%。但请注意，快速重传策略并不能消除所有粗粒度超时，这是因为对于小窗口来说，在传输过程中没有足够多的包来导致发送足够多的重复 ACK。如果有足够多的丢包(例如，在初始慢启动阶段发生的情况)，滑动窗口算法最终会阻塞发送方，直到出现超时。在实践中，TCP 的快速重传机制可以在每个窗口中检测到最多三个丢包。
还可以做进一步改进。当快速重传机制发出了拥塞信号，可以基于还在流水线中的 ACK 来触发包的发送，而不是将拥塞窗口设为一个包并开始慢启动。这一被称为快速恢复(fast recovery) 的机制有效消除了快速重传机制检测到丢包并开始慢启动的阶段。例如，快速恢复避免了图 27 中 3.8 到 4 秒之间的慢启动周期，而是简单的将拥塞窗口减少一半(从 22 KB 到 11 KB)，并重新开始增加拥塞窗口。换句话说，慢启动只在连接开始时和发生粗粒度超时时使用，其他任何时候，拥塞窗口都遵循纯粹的线性增加/指数减少模式。
4.5 增量改进
如果对 TCP 拥塞控制的研究只教会了我们一件事，那就是认识到这个问题有多么复杂，以及需要正确处理多少细节。只有通过一系列经过经验检验的结果，即渐进的改进才能实现。下面给出了这一教训的两个额外例子。
4.5.1 TCP SACK
原始 TCP 规范使用累积确认，意味着接收方在任何丢包之前只确认收到的最后一个包。可以认为接收方拥有接收包的集合，其中任何丢失的包都由接收字节流中的空洞表示。根据原始规范，即使丢失了几个包，也只能告诉发送方第一个洞开始。直观的说，这种细节的缺乏可能会限制发送方对丢包作出有效响应的能力。解决这个问题的方法被称为选择性确认(selective acknowledgments) 或 SACK。SACK 是 TCP 的一个可选扩展，最初是在 Jacobson 和 Karels 的早期工作完成后不久提出的，但因为很难证明有用，因此花了几年时间才被接受。
在没有 SACK 的情况下，当分片被无序接收时，发送方只有两种合理的策略。对于重复 ACK 或超时，悲观策略不仅会重传明显丢失的分片(接收方丢失的第一个包)，还会重传随后传输的任何分片。实际上，悲观策略假设了最坏的情况: 所有这些部分都消失了。悲观策略的缺点是可能不必要的重传第一次成功接收到的分片。另一种策略是对丢失信号(超时或重复 ACK)做出响应，方法是只重传触发该信号的分片。乐观方法假设了最乐观的情况: 只有一个部分丢失了。乐观策略的缺点是，当一系列连续分片丢失时，恢复非常缓慢，在拥堵情况下就可能发生这种情况。之所以慢，是因为在发送方收到重传前一段的 ACK 之后，才会发现每一个分片的丢失。这意味着它每个分片都需要消耗一个 RTT，直到重传丢失序列中的所有分片。使用 SACK 选项，发送方可以使用一种更好的策略: 只重传那些填补已选择性确认的分片之间空白的分片。
连接开始时，发送方首先协商 SACK，告诉接收方它可以处理 SACK 选项。当使用 SACK 选项时，接收方继续正常确认分片，Acknowledge字段的含义不会改变,但是也会对任何无序接收的块使用额外的确认扩展报头。这允许发送方识别在接收方存在的空洞，并只重传丢失的分片，而不是之后的所有分片。
SACK 被证明可以提高 TCP Reno 的性能，尤其是在一个 RTT 中丢弃多个包的情况下(因为当只丢弃一个包时，累积 ACK 和 SACK 是一样的)。随着时间的推移，随着带宽时延积的增加，这种情况变得更可能发生，给定 RTT 可能丢弃更多的数据包。因此，在 1996 年被提议成为 IETF 标准的 SACK 是对 TCP 的及时补充。
4.5.2 NewReno
从麻省理工学院的 Janey Hoe 在 20 世纪 90 年代中期的一些研究开始，这种被称为 NewReno 的增强技术通过在某些包丢失的情况下对重传哪些包做出更智能的决定，逐步提高了 TCP 的性能。
延伸阅读:
J. Hoe. Improving the start-up behavior of a congestion control scheme for TCP. SIGCOMM ‘96. August 1996.
NewReno 背后的关键见解是，即使没有 SACK，重复 ACK 也可以向发送方传递丢弃了多少包以及丢弃了哪些包的信息，因此发送方可以在何时重传包方面做出更明智的选择。此外，在单个窗口出现多次丢包的情况下，NewReno 可以避免以前版本中出现的对拥塞窗口多次减半。
NewReno 有很多细节，但简单来说，如果丢了一个包，发送方需要重复 3 次 ACK，才会重新发送丢失的包。当接收端收到重传时，因为现在已经填满了接收缓冲区中的空洞，因此将 ACK 所有缓冲区中的包。相反，如果丢失了多个包，则在收到重传包之后的第一个 ACK 将只能部分覆盖未响应的包。由此，发送方可以推断有更多的包丢失，并立即开始尝试通过发送下一个尚未得到确认的包来填补空白。这可以减少的超时，减少阻塞时间并且缓解对拥塞窗口的减少。
值得注意的是，NewReno 在 1999 年至 2012 年发布了三次 RFC，每一次都修复了之前算法中的一些问题。这是一个关于理解拥塞控制的细节是多么复杂的案例研究(特别是关于 TCP 重传机制的微妙之处)，也增加了部署新算法的挑战。
4.6 TCP CUBIC
现在应该很清楚，试图找到向网络发送流量的适当速率是拥塞控制的核心，而在任何一个方向上都有可能出错。比如发送流量过少，网络利用率不高，会导致应用程序性能下降。而发送过多流量会导致网络拥塞，最坏的情况下会导致拥塞崩溃。在这两种故障模式之间，发送过多流量通常会导致更严重的问题，并且由于重传丢失的数据包，拥塞会迅速加重。Tahoe、Reno 和 NewReno 采用的 AIMD 方法反映了这一点: 缓慢增加窗口(线性增加)，迅速减少窗口(指数减少)，以便在拥塞崩溃变得过于严重之前从崩溃的边缘退回。但是在高带宽延迟环境中，探测拥塞时过于保守的代价是相当高的，因为在"流水线满"之前可能需要许多 RTT。因此，这导致了对如何探测适当的窗口大小的一些反思。
一种被称为 Binary Increase Congestion Control (BIC) 的新方法提出，窗口应该在某些时候快速打开，而在其他时候慢一些的想法。BIC 并没有像 TCP Reno 那样突然的从指数窗口增长切换到线性窗口增长，而是对"正确"的窗口大小进行二分查找。在丢包之后，拥塞窗口以指数参数β截断。每次在新的窗口大小上成功发送报文，窗口就会增加到其当前值和造成拥塞的旧值的中点。通过这种方式，以先快后慢的速度逐渐接近旧值。(极端情况下，窗口将永远不会恢复到原来的值，类似于芝诺的悖论，但当达到某个阈值时，会被设置为原来的值)。
在这一点上，如果没有拥塞，可以得出结论，网络条件已经改变，可以探测新的拥塞窗口大小。BIC 先慢一点，然后快一点。可以在图 28 中看到 BIC 增加窗口的大致形状，渐近接近 Wmax(最后一次丢包之前的旧拥塞窗口)，然后超越它。
图 28. 通用三次(cubic)函数表示拥塞窗口作为时间的函数变化。
三次函数，如图 28 所示，有三个阶段: 缓慢增长，平台阶段，快速增长。在最后一次拥塞事件之前实现的最大拥塞窗口大小是初始目标(表示为Wmax)。可以看到窗口一开始快速增长，但随着越来越靠近Wmax增长越来越平缓，最后阶段开始探索新的可实现的Wmax。
具体来说，CUBIC 用自上次拥塞事件发生以来时间(t)的函数计算拥塞窗口(CongestionWindow)
C 是一个比例常数，β是指数递减因子。CUBIC 将后者设为 0.7，而不是标准 TCP 使用的 0.5。回头看看图 28，CUBIC 通常被描述为在凹函数和凸函数之间转换(而标准 TCP 的线性函数仅是凸函数)。
有趣的是，与 TCP 早期变体相比，CUBIC 要么更激进，要么更不激进，这取决于具体条件。短 RTT TCP Reno 流往往能有效获取瓶颈带宽，因此 CUBIC 包含了一个"TCP 友好"模式，其目标是像 TCP Reno 一样激进。但在其他情况下，尤其是高带宽延迟网络，CUBIC 能够获得更大的瓶颈带宽份额，因为 CUBIC 可以更快增加窗口大小。这让我们想到 3.3 节的讨论，即对现有算法的"公平"是否是正确的设计目标。最后，对 CUBIC 进行了广泛的分析，在许多条件下均表现出良好的性能，且不会造成不适当的伤害，因此得到了广泛应用。
延伸阅读:
S. Ha, I. Rhee, and L. Xu. CUBIC: a New TCP-friendly High-speed TCP Variant. ACM SIGOPS Operating Systems Review, July 2008.
