数据包丢失检测算法

TCP在传输过程中，对于丢失的数据包会采用重传的方式来修复。但是，数据包是如何丢失的呢？TCP又是如何检测到这种丢失情况的呢？在本文中，我们将探讨用于检测数据包丢失的算法。

数据包丢失通常发生在什么时候呢？

数据包丢失的原因主要有以下几点：

1. 当接收方的缓冲区已满时，但发送方仍然持续发送大量数据包。
2. 当中间设备（如路由器）的缓冲区已满时，发送方仍然继续发送数据包。

第一个案例与流量控制有关，接收方会向发送方告知自己的缓冲区大小，从而避免出现这种情况。第二个案例则与拥塞控制相关，发送方需要结合“慢启动”和AIMD等策略来避免这种情况的发生。

数据包丢失检测算法：

Linux内核中使用了三种用于检测数据包丢失情况的算法。具体方法如下：

1. RTO（重传超时时间）
2. FR（快速重传）
3. RACK（最近确认）

这些算法能够检测到数据包的丢失情况，从而让发送方降低向接收方传输数据包的频率。

RTO算法：

这一方法最初是由Van Jacobson在1988年的论文《Congestion Avoidance and Control》中提出的。

当发送方将数据包发送到飞行器中时，就会启动一个计时器，这个计时器实际上就是RTT的度量单位。 这个计时器会持续运行一段时间，然后等待收到确认信号。 如果ACK在RTO时间内没有到达，那么相应的数据包就被认为已经丢失了。 RTO是往返时间（RTT）的一个函数。 其计算方式可以是按“每个数据包”来进行的，也可以是按“每个拥塞窗口(cwnd)”来进行的。 当RTO计时器在收到ACK之前就已经到期时，发送方会认为网络处于拥堵状态，于是会重新发送丢失的数据包，从而使得等待时间翻倍。 这被称为……二进制指数退避技术。这样做是为了让网络从拥挤的状态中恢复过来，让网络能够“喘息”一下。

Some important variables used in the computation of RTOSRTT -> Smoothed RTTRTTVar -> RTT VariationRTO -> Retransmission TimeOutR -> Current RTT measuredWhen the first RTT measurement (R) is made, the host must set:SRTT = RRTTVar = R ÷ 2RTO = SRTT + (K x RTTVar), where K = 4 as proposed by Van Jacobson in 1988When a subsequent RTT measurement (R) is made, the host must set:RTTVar = (1 - β) x RTTVar + β x |SRTT - R|, where β = 1/4SRTT = (1 - α) x SRTT + α x R, where α = 1/8RTO = SRTT + (K x RTTVar), where K = 4

每当计算RTO时，如果其小于1秒，那么RTO应向上取整为1秒。当然，RTO的最大值可以设定为60秒以上。当重传计时器到期时（即没有收到ACK响应），发送方需要重新发送丢失的数据包，此时RTO的值会变为RTO×2。不过，RTO的最大值仍然应该是60秒。

快速重传算法：

它会在不等待RTO计时器到期的情况下，重新传输丢失的数据包。如果接收到三个重复的ACK信号，那么发送方就会重新传输丢失的数据包。发送方不需要等待RTO时间结束，而是直接等到收到三个重复的ACK信号之后再进行传输。这种现象被称为“重传机制”。快速重传因为，重复发送3次ACK所需的时间，比单次发送RTO所需的时间要少。 那么，为什么在收到“1”或“2”个确认后，它仍然不重新传输数据呢？因为那些看似被丢弃的数据包，实际上可能是被延迟了而已。因此，不要因为急躁而过早地重新传输这些数据包。 那么，为什么它不等待超过三个重复的ACK信号后再重新发送丢失的数据包呢？因为如果等待的时间过长，RTO计时器可能会到期。 Fast Retransmit的主要目标是避免等待RTO的到期。

重复确认：

发送方一次向接收方发送6个数据包。假设发送方已经收到了第1个和第2个数据包的确认信号。

由于网络拥塞，数据包3丢失了。接收方收到了数据包4、5和6。

当接收器接收到第4个数据包时，它会发送对第2个数据包的确认，但不会发送对第4个数据包的确认。因为第2个数据包的确认已经收到了。这种现象被称为“重复确认”。

TCP接收器会按照顺序，逐一确认它已经接收到的数据包。因此，当1-2-4-5-6的顺序发生混乱时，接收方只有在接收到4-5-6数据包之后才会为第2个数据包发送ACK信号。这意味着接收方已经成功接收了直到第2个数据包为止的所有数据包。它会继续发送重复的ACK信号，直到所有数据包都按正确的顺序被接收完毕。

在发送了3次重复确认后，对于4、5、6个数据包，发送方再次重新发送这些数据包。此时，接收方会按顺序接收到第3到第6个数据包，并发送确认信号，表示已经收到了第6个数据包。这种确认方式被称为“累积确认”。

FR的局限性：

快速重传是一种启发式机制，它“有时”会比常规的RTO机制更早地触发对丢失数据包的重新传输。这种快速重传机制并不会取代常规的时间超时机制；它只是进一步增强了这一功能而已。例如，如果数据包在TCP连接的末端被丢失，那么快速重传机制就无法发挥作用了，因为至少需要三个重复的确认信号才能实现重新传输。

最近确认算法：

一种名为“Tail Loss Probe”（TLP）的新机制，可以解决数据包在TCP连接末尾被丢弃的问题。此外，谷歌还提出了一种新的数据包丢失检测技术。最近的致谢/认可信息。

因此，目前所使用的数据包丢失检测方法可以协同工作来发挥作用。RACK → 快速重传 → RTO

Linux内核同时使用这三种丢失检测算法。首先使用RACK算法；如果RACK算法无法达到预期效果，则采用Fast Retransmit算法；如果这两种算法都无法解决问题，那么就会使用RTO算法来解决问题。