---

Early Retransmit机制解决了dupack较少，无法触发快速重传的问题。
但是如果发生了尾丢包，由于尾包后面没有更多的数据包，也就没有办法触发任何的dupack。
为解决这种尾丢包的问题，Google的几位大神提出了TLP算法。通过TLP算法，发送一个loss probe包，来产生足够的SACK/FACK的信息来触发RF。根据Google的测试，TLP能够有效的避免较长的RTO超时，进而提高TCP性能。

---

RFC解读

---

TLP基本策略

TLP算法会在TCP还是Open状态的时候，设置一个Probe TimeOut (PTO)。
当链路中有未被确认的数据包，同时在PTO时间内未收到任何ACK，则会触发PTO
超时处理机制。
TLP会选择传输序号最大的一个数据包作为tail loss probe包，这个序号最大的包可能是
一个可以发送的新的数据包，也可能是一个重传包。
TLP通过这样一个tail loss probe包，如果能够收到相应的ACK，则会触发FR机制，而不是RTO机制。

---

触发超时机制的常见场景

这些case还是用大神们的原文描述比较准确:)

a. Drop tail at the end of transactions.
b. Mid-transaction loss of an entire window of data or ACKs.
c. Insufficient number of duplicate ACKs to trigger fast recovery at sender.
    -- 基本被Eearly Retransmit机制解决了
d. An unexpectedly long round-trip time(RTT), such that the ACKs arrive after
   the RTO timer expires.
    -- F-RTO机制通过检测spurious retransmission，能够尽量的undo RTO造成的影响

Early Retransmit技术可参考这篇wiki
F-RTO技术可参考这篇wiki

Google Web servers上面，将近70%的重传是RTO超时重传，只有30%是Fast Recovery重传。
同时还有数据表明，96%的RTO超时重传是在没有收到任何dupack的情况下发生的。
没有到任何dupack就意味着FR和ER机制都是无法生效的。

---

RTO与RTT的比值分布

Googler们还收集RTO/RTT的分布，来了解RTO值到底比RTT值大多少。下面是统计结果

Percentile      RTO/RTT
50%             4.3
75%             11.3
90%             28.9
95%             53.9
99%             214

根据这个数据，显然这是一个CDF的统计。也就是说，50%的流，RTO/RTT小于4.3，75%的流，RTO/RTT小于11.3
不过反过来看，有50%的流RTO/RTT超过4.3，25%的流RTO/RTT超过11.3。
不过这个数据Googler并没有进一步的解释，有很多疑问在里面。
RTO的min值默认是200ms，这数据里面的是多少？这个数据里面是否同时包含了internet-face流和local-face流。
比如说，local-face流的rtt一般很小，常见值就是1.875ms，而min RTO值200ms的话，显然RTO/RTT很容易超过100
不过话说回来，数据来看，local-face的流应该没有包括，但是min RTO就不清楚了。

Googler认为”Such large RTOs make a huge contribution to the long tail on the
latency statistics of short flows.”
这点如果结合TLP考虑的情景，推断确实合理。

那将RTO的计算值设置的较小一点如何？可能会造成两个问题：
a. spurious retransmission
b. 更多的RTO => cwnd=1

TLP试图解决的方式是将”尾丢包+RTO”这种case转换为”尾丢包+尾探测+FR”。

---

TLP算法

名词解释

FlightSize: the amount of data that has been sent but not yet *cumulatively* acknowledged.
    -- 这个与内核中的packet_in_flight计数器要区分开，这里要强调累计确认

PTO: Probe timeout is a timer event indicating that an ACK is overdue.

Open state: the sender has so far received in-sequence ACKs with no SACK
            blocks, and no other indications (such as retransmission timeout) that
            a loss may have occurred.
    -- 换成中文：TCP的正常状态，哈哈

Consecutive PTOs: back-to-back PTOs all scheduled for the same tail packets in a flight.

算法逻辑

1. 在Open state发送新数据后，设置一个PTO计时器  
    if (FlightSize > 1)     PTO = max(2*SRTT, 10ms)
    if (FlightSize == 0)    PTO = max(2*SRTT, 1.5*SRTT + WCDelAckT)
    if (RTO is earlier)     PTO = min(RTO, PTO)
        其中WCDelAckT表示worst case delayed ACK timer，默认值是200ms

2. 启用PTO timer的条件：
    a. connection is in open state
        -- 如果不在open state，说明有其他信息帮助判断丢包。而无需启用TLP
    b. connection is either cwnd limited or application limited
        -- TLP必须满足tail这个条件
    c. number of consecutive PTOs <= 2
        -- TLP 不要尝试太多次
    d. connection is SACK enable
        -- TLP依赖于SACK选项来提供是否触发FR的决策

3. 当PTO超时后：
    if (能发新数据)         发送一个新数据包，FlightSize += SMSS, cwnd不改变
    if (没有新数据可发)     发送一个序号最大的数据包
    增加loss probe的计数器
    如果步骤2中的条件满足，则再次设置PTO；否则设置RTO超时计时器'now+RTO'

4. 在处理收到的ACK包时
    取消PTO timer
    如果步骤2条件满足，则设置PTO timer

---

基于FACK机制的FR触发算法

理解FACK机制最终的一点就是意识到SACK信息能够反应较准确的接收端接收情况。
FACK机制的算法如下，非常好理解：

if (SND.FACK - SND.UNA) > dupack threshold:
    -> Invoke Fast Retransmit and Fast Recovery.
SND.FACK relects the forward-most data held by the received plus one.

---

如果丢失的包就是TLP重传的数据包会怎样

如果丢失的包刚好是最后一个数据包，那么TLP的重传可能会恰巧修复了这个丢包。
这样对于congestion control机制来说，就无法发现这个丢包。这与TCP的拥塞控制
机制相违背。
因此TLP需要设计一个检测丢包是否被TLP探测包修复的逻辑。

检测的核心思想就是：

如果发送了N次TLP探测包，判断是否收到了N个"TLP dupacks"。
如果没有，则意味着第一个TLP探测报可能就刚好修复了一个丢失包。  

---

TLP丢包检测算法

名词解释

TLPRtxOout: the number of unacknowledged TLP retransmissions in current TCP episode.

TLPHighRxt: the value of SND.NXT at the time of TLP retransmission.

算法步骤：

1. 初始化  
    当TCP流进入ESTABLISHED状态，或者RTO超时后，或者进入Fast Recovery后，对上面两个变量进行初始化
    TLPRtxOut = 0;
    TLPHighRxt = 0;
2. 当发送一个TLP探测包后  
    if (TLPRtxOut == 0)
        TLPHighRxt = SND.NXT
    TLPRtxOut++;
3. 在收到一个ACK包后  
    当满足所有以下条件时，认为这个ACK是由TLP包触发的，而且这个TLP是完全多余的
    a. TLPRtxOut > 0                        /* 首先当然得发送过TLP包 */
    b. SEG.ACK == TLPHighRxt                /* ACK包确认了SND.NXT序号 */
    c. ACK不包含序号超过TLPHighRxt的SACK段  /* 意味着这个ACK就是TLP包序号触发的，而不是TLPHighRxt序号之后某个包触发的 */
    d. ACK没有移动SND.UNA                   /* 说明这是一个纯粹的dupack，并且ACK号是SND.NXT证明这个ACK包对应的TLP是完全多余的 */
    e. ACK包不含数据                        /* 就是要证明这个ACK是一个完全多余的TLP包触发的 */
    f. ACK包不是一个窗口更新包              /* 理由同e */
    以上条件都满足时，TLPRtxOut--

    如果ACK.SEQ > TLPHighRxt，则说明TLP阶段应该结束了。最后来判断是否发现了丢包
    isLoss = (TLPRtxOut > 0) &&     /* 不为0说明有一个TLP包不是多余的，也就是说有丢包发生 */
             (ACK不携带任何TLP重传相关的DSACK信息)      /* 如果包含DSACK信息，也能证明TLP是多余的。所以要排除这种情况 */
    TLPRtxOut = 0
    if (isLoss)
        EnterRecovery()
4. TLP探测包的发送条件，除了满足TLP原始算法中步骤2中的条件外，还要满足  
    (TLPRxtOut == 0) || (SND.NXT == TLPHighRxt)
    -- The sender maintains this invariant so that there is at most
       one TLP retransmission "espisode" happening at a time.

---

统一了丢包恢复机制

在原生TCP中，如果丢包发生在packet train的中间，很容易触发快速重传进行丢包恢复；
但是如果丢包发生packet train的末端，则基本只能靠RTO超时来恢复。
而这就意味着丢包的位置的不同，也可能造成TCP不同的重传机制被触发。这与TCP设计时的common sense不一致。

如果使用TLP机制，则能避免丢包位置的不同对TCP重传机制的选择造成影响。

---

恢复任意程度的尾丢包

根据Googler们的讨论，Tail Loss Probe + Early Retransmit能够解决任意程度的尾丢包
下面是所有case情境的讨论汇总

number of losses	scoreboard after TLP retrans ACKed	mechanism	final outcome
AAAL	AAAA	TLP loss detection	all repaired
AALL	AALS	ER	all repaired
ALLL	ALLS	enhanced ER	all repaired
LLLL	LLLS	FACK FR	all repaired
>=5 L	..LS	FACK FR	all repaired

其中：
A = ACKed segment
L = Lost segment
S = SACKed segment

其中case “ALLL”依赖于Googler们提出的enhanced ER机制，首先这个增加做了什么

Propose to allow a delayed early retransmit in the case where there
are three outstanding segments that have not been cumulatively
acknowledged and ont segment that has been fully SACKed.

具体来讲，就体现在之前介绍ER的wiki中提到的如下一个代码更改

@ static bool tcp_time_to_recover()
-   (tp->packets_out == (tp->sacked_out + 1) && tp->packets_out < 4) && 
+   (tp->packets_out >= (tp->sacked_out + 1) && tp->packets_out < 4) && 

具体分析以下，如果是’==’的形式，case”ALLL”会得到”ALLS”的scoreboard，但是这里的packets_out=3，而sacked_out=1所以还无法触发ER。
此时解决方法有两种：要么在重传一个TLP探测报，使sacked_out值增长为2，要么放松条件改用”>=”。
很明显，Googler们选了后者。
而对于case”AALL”这种packets_out=2的情况，一个TLP包引起的dupack就能触发ER，也就无影响了。
下面我来讨论一下packets_out=3的情况，其中R表示reorder达到接收端，即没有被丢弃

1. ALLL
    这种使用TLP和enhanced ER能够做到all repaired。没问题
2. ALRR
    这种能够通过ER机制修复。但是如果使用了enhanced ER，那么在收到第一个reorder触发的SACK信息后，
    socreboard为ALS_状态，此时由于使用了enhanced ER，在第二个SACK信息没有收到时就会被判为启动ER。
    因为packets_out=3, sacked_out = 1, 满足enhanced ER的条件
    当然由于enhanced ER还有一个重要的特性是delayed，如果第二SACK信息能够及时的到来，最严重的后果也就是
    early retransmit的timer被设置两次而已。

3. ALLR
    这种情况首先肯定不会触发TLP机制，因为必能能收到一个dupack。应该属于ER机制要解决的范畴。  
    但是它又由于没有足够的dupack，packet_out=3，dupack等于1。标准的ER对此无能为力。  
    只能靠enhanced ER来恢复。
4. ALRL
    packets_out=3,dupack=1。不能触发TLP，标准ER又解决不了。只能靠enhanced ER来恢复。

---

---

源码分析

以下代码基于Linux3.10内核

---

函数调用逻辑

1. 正常数据的发送流程中，增加调度安装PTO超时计时器的逻辑
   即TLP算法逻辑的第一步。  

__tcp_push_pending_frame()
    ==> tcp_write_xmit() with push_one=0
        ==> tcp_schedule_loss_probe()   /* 尝试安装PTO超时计时器的安装 */

2. 处理ack时，增加调度安装PTO超时计时器和结束TLP状态的逻辑
   即TLP算法的最后一步 

tcp_ack()
    ==> if (tp->tlp_high_seq) tcp_process_tlp_ack();    /* 判断是否需要结束TLP状态 */
    ==> tcp_schedule_loss_probe()

---

安装PTO超时计时器

/* 返回false代表未设置timer, 返回true代表设置了PTO timer */
bool tcp_schedule_loss_probe(struct sock *sk)
{
    ...  
    u32 rtt = tp->srtt >> 3;    /* tp->srtt存的实际是RFC中SRTT的8倍 */
    ...  
    /* TLP is only scheduled when next timer event is RTO. */
    if (icsk->icsk_pending != ICSK_TIME_RETRANS)
        return false;

    /* Schedule a loss probe in 2*RTT for SACK capable connections
     * in Open state, that are either limited by cwnd or application.
     */
    if (sysctl_tcp_early_retrans < 3 ||     /* 没开TLP */
        !rtt ||                             /* 没有RTTsample可用，没法设置PTO */
        !tp->packets_out ||                 /* 网络中没有未被确认的数据包，没必要设置PTO */
        !tcp_is_sack(tp) ||                 /* 不支持SACK选项 */
        !inet_csk(sk)->icsk_ca_state != TCP_CA_Open)    /* 只有在open状态才设置PTO */
        return false;

    /* Probe timeout is at lease 1.5*rtt + TCP_DELACK_MAX to account
     * for delayed ack when there's one outstanding packet.
     */
    /* 这段代码完全符合TLP算法逻辑，不解释了 */
    timeout = rtt << 1;
    if (tp->packets_out == 1)
        timeout = max_t(u32, timeout, (rtt + (rtt >> 1) + TCP_DELACK_MAX));
    timeout = max_t(u32, timeout, msecs_to_jiffies(10));

    /* If RTO is shorter, just schedule TLP in its place. */
    /* PTO = min(PTO, RTO) */
    tlp_time_stamp = tcp_time_stamp + timeout;
    rto_time_stamp = (u32)inet_csk(sk)->icsk_timeout;
    if ((s32)(tlp_time_stamp - rto_time_stamp) > 0) {
        s32 delta = rto_time_stamp - tcp_time_stamp;
        if (delta > 0)
            timeout = delta;
    }

    inet_csk_reset_xmit_timer(sk, ICSK_TIME_LOSS_PROBE, timeout, TCP_RTO_MAX);
    return true;
}

// 在tcp_write_timer_handler中会根据event的类型，来做相应的处理
// 如果是PTO超时，则调用tcp_send_loss_probe(sk)来发送TLP探测包
/* When probe timeout (PTO) fires, send a new segment if one exists, else
 * retransmit the last segment.
 */
void tcp_send_loss_probe(struct sock *sk)
{
    ...
    /*
     * 如果有新数据可以发送，则发新数据作为探测包
     * TLP用了一个push_one=2的trick来区分是正常的发送包，还是loss probe包
     */
    if (tcp_send_head(sk) != NULL) {        
        err = tcp_write_xmit(sk, mss, TCP_NAGLE_OFF, 2, GFP_ATOMIC);
        goto rearm_timer;
    }

    /* At most one outstanding TLP retransmission */
    if (tp->tlp_high_seq)
        goto rearm_timer;

    /* Retransmit last segment */
    skb = tcp_write_queue_tail(sk);
    if (WARN_ON(!skb))
        goto rearm_timer;

    /* 省略一些判断tcp fragment的代码 */

    /* Probe with zero data doesn't trigger fast recovery */
    if (skb->len > 0)
        err = __tcp_retransmit_skb(sk, skb);

    /* Record snd_nxt for loss detection */
    if (!likely(!err))
        tp->tlp_high_seq = tp->snd_nxt;

rearm_timer:
    /* 重新安装RTO超时计时器 */
    inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS, inet_csk(sk)->icsk_rto, TCP_RTO_MAX);

    if (likely(!err))   /* 增加计数器的值，可以在/proc/net/snmp中看到，netstat -s也可以 */
        NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPLOSSPROBES);

    return;
}

---

何时结束一个episode

/* This routine deals with acks during a TLP episodes. */
static void tcp_process_tlp_ack(struct sock *sk, u32 ack, int flag)
{
    struct tcp_sock *tp = tcp_sk(sk);
    /* 判断TLP是否是多余的，及产生了多余的dupack。逻辑参考RFC */
    bool is_tlp_dupack = (ack == tp->tlp_high_seq) &&   
                         !(flag & (FLAG_SND_UNA_ADVANCED | 
                                  FLAG_NOT_DUP | FLAG_DATA_SACKED));

    /* Mark the end of TLP episode on receiving TLP dupack or when
     * ack is after tlp_high_seq.
     */
    /* 可见实现TLP时，选择了最多有一个TLP包发送出去，所以省去了RFC中的TLPRxtOut计数器 */
    if (is_tlp_dupack) {
        tp->tlp_high_seq = 0;
        return;
    }

    if (after(ack, tp->tlp_high_seq)) {
        tp->tlp_high_seq = 0;
        /* Don't reduce cwnd if DSACK arrives for TLP retrans */
        if (!(flag & FLAG_DSACKING_ACK)) {
            /* 折腾这么一圈，最关键的就是降cwnd: ssthresh = 0.7*cwnd; cwnd=ssthresh */
            tcp_init_cwnd_reduction(sk, true);
            tcp_set_ca_state(sk, TCP_CA_CWR);
            tcp_end_cwnd_reduction(sk);
            tcp_set_ca_state(sk, TCP_CA_Open);
            NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPLOSSPROBERECOVERY);
        }
    }
}

问题：代码什么地方体现了TLP中的Tail ?
< 没有dupack收到，自然就认为是Tail了。并不需要想ER那样判断什么packets_out,sacked_out等。
这样的问题可能就是跟RTO抢活了。

最后说一句，TLP的loss probe次数和loss recovery 次数Linux中都有相应的计数器跟踪，
分别对应LINUX_MIB_TCPLOSSPROBES，LINUX_MIB_TCPLOSSPROBERECOVERY。

---

TLP与ER的关系

一句话总结

ER解决的是dupack不够用的情况
TLP解决的是没有dupack可用的情况

---

---

TLP性能评测数据

Measuring TCP Tail Loss Probe Performance中的测试数据显示

TLP is able to decrease the total transfer time in high-speed networks by 38% and the time until data is retransmitted by 81%.
These improvements decrease significantly for higher delay links.

文章中用到mininet和iptables的方式来模拟网络倒是点醒了我。之前我干嘛非得搭物理机环境啊。T_T

An Evaluation of Tail Loss Recovery Mechanisms for TCP
文章评测了RTO Restart(RTOR)、TLP、TLPR三种技术对尾丢包情境性能的影响。都是TLPR得到的性能更好，当然TLP的性能也不赖。
RTOR这个技术主要解决的是现有RTO计时器在每次收到ACK后都会重新reset的问题。而RTOR的timer只要设置好，就不会随着dupack的到来而更改了。这个思路刚好解决了我看RTO代码时的疑问，又是脑洞大开啊。
看来paper还是要保持看下去啊，跟住研究的脚本才能了解技术的变迁。也能了解技术发展过程中的方方面面，而看内核代码只能了解被社区选用的技术(暂且不去评论社区选的好坏)。

---

参考资料

Tail Loss Probe (TLP): An Algorithm for Fast Recovery of Tail Losses Probe
Measuring TCP Tail Loss Probe Performance
An Evaluation of Tail Loss Recovery Mechanisms for TCP