Early Retransmit for TCP


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


参考资料

RFC 5827