1. 前言
我们都知道物理网络介质容易因环境因素而产生波动，导致数据在传输过程中损坏或丢失。在如此环境下，如何确保接收方收到发送方发出的完整数据，是科学家们多年来一直攻克的难题。目前主要有两种途径来解决这个问题。针对数据损坏，我们可以使用错误检测与纠错码。针对数据丢失，唯一的解决办法就是重传数据包。TCP（Transmission Control Protocol，传输控制协议）是一种可靠的数据传输协议，它同时使用了错误检测码和重传机制来保证数据的完整性。本文将重点讨论 TCP 的重传机制。当检测到数据包丢失时，就会触发数据包的重传。TCP 基于接收方发回发送方的一系列确认消息（ACK）来判断数据包是否丢失。根据判断丢包的条件不同，重传可以分为超时重传、快速重传和选择性重传。下面我们逐一详细讨论。
2. 超时重传
发送方每发送一个报文段，就为该报文段设置一个计时器。如果在指定时间内没有收到接收方返回的确认消息（ACK），就认为发生了丢包，并开始重传。这里的难点在于如何确定合适的超时时间。如果超时时间设置得太短，可能导致不必要的重传，引起网络拥塞；如果设置得太长，又可能导致网络利用率不足，降低吞吐量。此外，超时时间还需要根据不断变化的网络状况进行动态调整。重传超时时间（Retransmission TimeOut，RTO）的设置对 TCP 协议的传输性能影响很大。由于底层协议不提供精确的网络环境信息，TCP 协议需要自行设计和采集样本数据。一种动态估算 RTO 值的方法是通过测量往返时延（Round Trip Time，RTT），即数据包从发送方到接收方再返回（包括收到 ACK）所花费的时间。在确定合适 RTO 值的过程中，产生了几种典型的解决方案。
2.1 经典方案
2.1.1 经典算法
SRTT = α(SRTT) + (1-α)RTTs (1.1)
RTO = min(ubound, max(lbound, (SRTT)β)) (1.2)如公式 1.1 所示，SRTT 代表一组 RTT 样本的平均值。每当获得一个新的 RTT 样本时，就更新 SRTT。平滑因子 α 的推荐值为 0.8 到 0.9。这意味着新 SRTT 值的 80% 到 90% 基于已有值，而 10% 到 20% 基于新测量值。这种方法被称为加权移动平均，使得 SRTT 值能够随着网络环境的变化而动态调整。一般来说，RTO 应该略大于 RTT 样本的平均值。因此，我们将 SRTT 乘以一个常数 β（推荐值 1.3 到 2.0），得到最终的 RTO 值。为了保证 RTO 值在一个合理范围内波动，公式 1.2 对 RTO 设置了上限和下限。上限（ubound）的推荐值为 1 分钟，下限（lbound）的推荐值为 1 秒。该算法在 RTT 分布相对稳定的网络环境中表现良好。
2.1.2 Karn 算法
当使用经典算法测量 RTT 样本时，存在重传二义性问题。重传二义性问题发生在数据包超时后被重传，随后收到 ACK 的情况。这种情况下，无法确定该 ACK 是对第一次传输还是第二次传输的确认。在测量重传数据包的 RTT 样本时，可能出现以下两种情况：
a) 测量第一次传输到 ACK 到达之间的间隔。如果 ACK 确认的是第二次传输，RTT 会被高估。
b) 测量第二次传输到 ACK 到达之间的间隔。如果 ACK 确认的是第一次传输，RTT 会被低估。
为避免重传数据的 RTT 样本值不准确，进而影响平均 RTT 的统计估计，Karn 算法的第一部分采用了忽略重传的策略。即重传的数据包不计入 RTT 样本采集。然而，这会导致另一个问题。如果网络突然抖动造成较大延迟，所有数据包都可能因超时而重传。由于重传数据不参与 RTT 样本统计，RTO 保持在一个较小的值，导致数据包无谓地重传，加剧网络拥塞。Karn 算法的第二部分通过加倍退避因子来解决这个问题。即每当发生重传时，RTO 值加倍。虽然这种方法可以解决上述问题，但可能降低 TCP 的传输性能。更好的做法是使用时间戳选项来避免重传二义性问题。
2.1.3 Jacobson 算法
srtt = (1-g)(srtt) + (g)M (1.3)
rttvar = (1-h)(rttvar) + (h)(|M-srtt|) (1.4)
RTO = srtt + 4(rttvar) (1.5)前面我们提到，RTO 值应该略大于 RTT 样本的平均值。经典算法通过将 SRTT 乘以常数 β 来得到最终的 RTO 值，但这种方法缺乏灵活性。因此，Jacobson 算法对此进行了改进，用平均偏差作为 RTO 与 SRTT 之间的差值。这样就能保证当 RTT 分布越稳定时，RTO 值越接近 SRTT；反之，当 RTT 波动越大时，RTO 值比 SRTT 越大。完整的计算过程如公式 1.3 至 1.5 所示。其中，M 表示新测量的 RTT 样本值，参数 g 推荐设置为 1/8，rttvar 表示平均偏差，参数 h 推荐设置为 1/4，RTO 值由 srtt 加上四倍的 rttvar 得到。
2.2 Linux 采用的方案
虽然 Jacobson 算法是 TCP 协议估算 RTO 的标准方法，但它仍存在一些问题。例如，当 RTT 样本突然减小时，RTO 值本应随之减小，而不是增大。此外，当使用更频繁的 RTT 测量和更精细的时钟粒度时，平均偏差 rttvar 的值很容易随时间衰减到最小值。Linux 对该算法进行了改进以避免这些问题。
（1）针对频繁进行 RTT 测量时 rttvar 随时间衰减到最小值的问题，Linux 为 rttvar 设置了一个最小值。rttvar 的值取自测量 RTT 样本过程中的最大估计平均偏差，且不低于一个下限。完整公式如下。其中变量 mdev 记录瞬时估计平均偏差，相当于标准方法中的 rttvar。mdev_max 变量用于存储测量过程中的最大估计平均偏差，其最小值设置为 50ms。由于 rttvar 的值与 mdev_max 同步，这就保证了 RTO 的最小值不小于 200ms，从而解决了频繁测量时 rttvar 衰减到最小值的问题。
srtt = (1-g)(srtt) + (g)M (1.6)
mdev = (1-h)(mdev) + (h)(|M-srtt|) (1.7)
mdev_max = max(mdev_max, mdev) (1.8)
rttvar = mdev_max (1.9)
RTO = srtt + 4(rttvar) (2.0)（2）为防止新样本值低于 RTT 估计范围下限时 RTO 反而增大的问题，降低了新样本的权重。具体的实现方式由以下代码片段给出。当新的测量样本值 m 小于估计范围下限（srtt - mdev）时，说明 RTT 正在急剧下降。通过将新样本的均值偏差 |srtt - m| 的权重降低到原来的 1/8，可以避免因 mdev 增大而导致 RTO 增大的问题。
if(m < (srtt - mdev)) {
mdev = (31/32)*mdev + (1/32)*|srtt - m|
} else {
mdev = (3/4)*mdev + (1/4)*|srtt - m|
}3. 快速重传
快速重传机制基于接收端的反馈信息来触发重传，而非依赖重传计时器的超时。因此，相比于超时重传，快速重传能够更及时、更有效地处理丢包情况。典型的 TCP 实现同时集成了这两种重传机制。快速重传的工作原理如下：当接收方收到乱序数据包时，会立即发送重复 ACK。发送方在收到一定数量的重复 ACK 后，便重传前面的数据包。由于收到重复 ACK 并不一定意味着数据包已丢失，也可能是网络中的数据包重排引起的，因此发送方会等待重复 ACK 数量达到一定阈值后才启动重传。通常这个阈值设置为 3，但某些实现可能会根据当前的包重排程度动态调整阈值。具体的工作流程如下图所示。
4. 选择性重传
虽然快速重传相比超时重传能更及时地检测到丢包，但它并不能精确判断哪些数据包丢失了。因此，它可能会重传已经被正确接收的数据包，从而降低 TCP 的传输效率。例如，在上图中，发送方连续收到三个重复 ACK。但由于这些重复 ACK 可以由 Segment 2 之后的任何数据包触发，发送方无法确定是否还需要重传 Segment 2 之后的其他数据包。为了解决这个问题，TCP 在头部引入了选择性确认（Selective Acknowledgment，SACK）选项。通过使用 SACK 选项，一个 ACK 可以包含三到四个 SACK 块，告知发送方缺失的乱序数据信息。每个 SACK 块包含乱序数据的起始和结束序列号。因此，在不考虑拥塞控制的情况下，借助 SACK 选项，发送方可以在一个往返时延（RTT）内填补接收方缓冲区中最多三个空洞，有效提升 TCP 的传输性能。具体的工作原理如下图所示。
5. 参考资料
[1] TCP/IP Illustrated, Volume 1: The Protocols
[2] TCP的哪些事儿(上) || 酷壳 - CoolShell
[3] TCP的哪些事儿(下) || 酷壳 - CoolChell
[4] Improving Round-Trip Time Estimates in Reliable Transport Protocols