Early Retransmit(ER)机制的提出主要解决的是在某些特定场景下，没有足够的
dupack触发fast retransmit造成的问题。
本质上就是通过检测出某些考虑到的特定场景，然后降低触发FR的dupack threshold值。
具体需要考虑那些特定场景后续后详细介绍。
RFC5827解读
ER要解决的问题:
当无法收到足够的dupack时，TCP标准的Fast Retransmit机制无法被
触发，只能等待RTO超时才能进行丢包的重传。而RTO超时不管是时间等待代价，还是
性能损耗代价都很大。
ER的解决方法:
检测出无法收到足够dupack的场景，进而降低dupack threshold来触发快速重传。
从而避免等待RTO超时重传，对性能造成较大的损耗。
TCP中的标准的重传机制:
a. 如果超过RTO时间没有收到ACK包，则会触发RTO超时机制。代价就是cwnd=1，慢启动
b. 如果收到三个重复dupack，则会触发快速重传。代价是cwnd减半(视congestion算法而定)，拥塞避免
为什么需要等三个重复dupack ？
那是因为dupack即可能是丢包造成的，也可能是网络乱序造成的。所以那帮设计标准的
牛牛们，一方面拍拍脑袋，一方面测点实验数据定了这么一个值：3。
倒也正好吻合了一句古话：事不过三。哈哈
但是阈值设置为三，也存在一些问题。
比如当cwnd较小时(比如3)，当发生丢包后，可能就无法产生足够的dupack来触发快速重传。
结果就是只能靠RTO超时来重传丢包了。
那么什么情况下cwnd会比较小呢？
1. TCP流经过的链路bandwidth-delay product (BDP)很小，就会导致很小的cwnd
2. 应用层限制，没有足够的数据可以发送，进而导致cwnd一直很小
3. 由于接收端的接收窗口的限制，导致cwnd很小
总结下，出现dupack不够的情况：
a. cwnd较小
b. 发送窗口里大量的数据包都被丢失了
c. 在数据发送的尾端发生丢包时
但是，上面各种极端的case有共同的特点：
m. 无法产生足够的dupack
n. 没有新的数据包可以发送进入网络
Early Retransmit机制就是在判断条件m和n都成立后，选择降低触发Fast Retransmit
的阈值，来避免只能通过RTO超时重传的问题。
ER算法
名词解释
oseg: outstanding segments, segements sent but not yet acknowledged
并且是没有被累计确认！及内核中的snd_nxt - snd_una
ER_thresh: 启用ER算法后，触发快速重传的dupack个数阈值
算法逻辑
ER_thresh = 3 // 等于3，表示还是标准的FR算法
if (oseg < 4 && new data cannot be sent) // 如果满足条件，考虑启用ER算法
if (SACK is unsupport) // 如果SACK选项不支持，则使用oseg-1作为阈值
ER_thresh = oseg - 1
elif (SACKed packet == oseg-1) // 否则，只有当oseg-1个包被SACK，才能启用ER
ER_thresh = oseg - 1
RFC的算法的算法主要是看个思路，具体算法的实现和逻辑细节还是要看代码。
The code in the real world is another cat compared with RFC’s.
开启SACK的必要性
总的来说就是更推荐使用SACK选项的方法
假设发送了三个数据包，S1，S2，S3，但是S2被丢弃了。
当S1到达接收端时，它是按序到达的。接收方可能会delay这个ACK，所以分两种情况讨论：
a. S1的ack被delay了：这种情况下S3的接收会触发一个ACK被发送（因为delay ack
机制最多能delay一个数据包）。那么此时如果没有带SACK信息，发送发就会收到
一个正常的ACK，而不是dupack。这样一个dupack都没有收到过，所以也就不会触发
ER机制，而只能靠RTO超时来进行重传(而且S2和S3都要重传)。
而如果有SACK信息，oseg=1，进而ER算法就能被启用。
具体就是：支持SACK，oseg=1, oseg-1=0 => 启用ER
不支持SACK，oseg=2, oseg-1=1 => 无法启用ER，因为没收到任何dupack
b. 如果ack没有被delay，ER都能被启用。
具体就是：支持SACK，oseg=1, oseg-1=0 => 启用ER
不支持SACK，oseg=2, oseg-1=1 => 启用ER
ER的问题
核心意思就是：如果一条TCP流，cwnd一直很小，然后cwnd内发送的数据
每次都乱序到达接收端，这样使用ER算法就可能导致较多的spurious retransmit。
比如cwnd=2，而每次这两个包都reorder，结果就是发两个数据包，就ER重传一个。
是的，这就叫TCP设计里面常提到的pathological case.
一种可能的解决办法就是发送一个TCP层data payload=0的包去增加dupack的个数，
但是这会一定程度上浪费网络资源。暂时未找到采用了这一思想的TCP实现。
解决降低DupACK阈值可能带来的问题
RFC附录提到了三种缓解ER可能带来问题的方法，具体如下
a. 判断ER是否发送了多次spurious retransmit数据，利用的手段就是D-SACK技术
b. 如果无法判断ER是否发送了spurious retransmit，则可以暴力的设置一个固定值来限制ER被触发的次数
c. 当需要触发ER机制时，等待一个固定长度的时间再重传。
Linux默认选用这种方式
源码分析
下面的源码分析，基于Linux3.10版本
是否开启ER功能
既然RFC中说了ER还是实验性的，而不是标准。故Linux kernel提供了选项来开启或关闭ER功能。
开关的名字是tcp_early_retrans，当然3.10的代码中还有Tail Loss Probe(TLP)的内容，暂时咱可以
忽略，之后再写一篇关于TLP的wiki。
sysctl_tcp_early_retrans (defalut:3)
0 disables ER
1 enables ER
2 enables ER but delays fast recovery and fast retransmit by a
fourth of RTT.
3 enables delayed ER and TLP.
4 enables TLP only.
具体的判断函数就是在TCP sock初始化(tcp_init_sock)时，调用tcp_enable_early_retrans()
来判断是否开启
static inline void tcp_enable_early_retrans(struct tcp_sock *tp)
{
tp->do_early_retrans =
sysctl_tcp_early_retrans && /* ER开关是否开启 */
sysctl_tcp_early_retrans < 4 && /* ER开关是否开启 */
!sysctl_tcp_thin_dupack && /* 只有关闭thin-dupack才开ER */
sysctl_tcp_reordering == 3; /* 需要默认的reordering是3菜开ER */
}
根据3.10内核默认的配置，ER是默认开启的，也就是tp->do_early_retrans默认等于1
当然了，在下面几种情况下也会disable ER
a. 应用程序通过setsockopt设置了TCP_THIN_DUPACK
b. TCP层发现了reorder，调用tcp_update_reordering尝试更新了reorder值
c. 配置了TCP_METRIC_REORDERING值，改变了reordering值
判断是否触发FR中ER判断部分
tcp_time_to_recoever这个函数就是判断是否该触发FR的函数
static bool tcp_time_to_recover(struct sock *sk, int flag)
{
...
/* Trick#6: TCP early retransmit, per RFC5827. To avoid spurious
* retransmissions due to small network reorderings, we implement
* Mitigation A.3 in the RFC and delay the retransmission for a short
* interval if appropriate.
*/
if (tp->do_early_retrans && /* 内核配置是否开启ER */
!tp->retrans_out && /* 当前没有重传数据 */
tp->sacked_out && /* 当前收到了dupack */
tp->packets_out < 4 && /* packets_out很小, 及RFC oseg < 4 */
tp->packets_out >= (tp->sacked_out + 1) && /* dupack个数满足ER/TLP条件 */
!tcp_may_send_now(sk)) /* 没有新数据可发送 */
return !tcp_pause_early_retransmit(sk, flag); /* 判断是否等待一段时间再触发ER */
return false; // 默认返回false，即不进入fast recovery阶段
}
主要需要解释的变量，应该是tp->sacked_out。
如果没有开SACK选项，那么该值就是表示dupack的个数。具体可参考tcp_add_reno_sack()函数相关代码
如果开启了SACK选项，那么这个值无疑就是表示被SACK的乱序包的个数。具体可参考tcp_sacktag_one()函数相关代码。
另外，观察仔细的人也许会发现”tp->packets_out >= (tp->sacked_out + 1)”与ER的RFC不一致，
应该是’==’，而不是’>=’。至于为什么代码中是这样修改的，暂时还不明确。
但可以确定的是这个概念是由于TLP算法的引入而改变的，具体的修改发生在Nandita的这个patch中
等四分之一RTT再触发ER
Linux中选择了等待四分之一RTT再触发ER的方式，来缓解降低dupack threshold可能带来的问题。
相关代码在tcp_pause_early_retransmit()中
// 返回false表示立即进入FR，即立即触发ER；返回ture则是等待一个超时时间后再进入FR
static bool tcp_pause_early_retransmit(struct sock *sk, int flag)
{
struct tcp_sock *tp = tcp_sk(sk);
unsigned long delay;
/* Delay early retransmit and entering fast recovery for
* max(RTT/4, 2msec) unless ack has ECE mark, mo RTT samples
* available, or RTO is scheduled to fire first.
*/
if (sysctl_tcp_early_retrans < 2 || /* kernel就没开delay ER的功能*/
sysctl_tcp_early_retrans > 3 || /* kernel跟本就没开ER功能(这个地方与do_early_retrans的判断有重复，感觉有点多余) */
(flag & FLAG_ECE) || /* ECE mark，ECN-Echo, Explict Congestion Notification */
!tp->srtt) /* 没有RTT采样 */
return false;
delay = max_t(unsigned long, (tp->srtt >> 5), msecs_to_jiffiec(2)); /* 计算delay ER的时间 */
if (!time_after(inet_csk(sk)->icsk_timeout, (jiffies + delay))) /* 如果RTO先超时 */
return false;
// 设置ER超时计时器
inet_csk_reset_xmit_timer(sk, ICSK_TIME_EARLY_RETRANS, delay, TCP_RTO_MAX);
return true;
}
ICSK_TIME_EARLY_RETRANS超时后，会调用tcp_resume_early_retransmit(sk)
void tcp_resume_early_retransmit(struct sock *sk)
{
strcut tcp_sock *tp = tcp_sk(sk);
tcp_rearm_rto(sk); // 重设RTO计时器
/* Stop if ER is disabled after the delayed ER timer is sheduled */
if (!tp->do_early_retrans)
return;
// 进入快速重传阶段
tcp_enter_recovery(sk, false);
tcp_update_scoreboard(sk, 1);
tcp_xmit_retransmit_queue(sk);
}
说一句题外话，TCP的具体设计经常需要考虑很多极端的case。
这类case，以前一般也就称之为corner case。但是越看RFC，越发现corner已经不足以
形容TCP设计的严谨性了，只能用pathological了。T_T