RTO的准确计算对于TCP的可靠性传输和性能都具有重要作用。
这篇文章首先介绍最新的RFC中对于RTO的计算方法，然后结合Linux 3.10的源码对
具体的实现进行分析和理解。
RTO计算算法
1.1. 在没有任何rtt sample的时候，RTO <- TCP_TIMEOUT_INIT (1s)
多次重传时同样适用指数回避算法(backoff)增加RTO
1.2. 获得第一个RTT sample后，
SRTT <- RTT
RTTVAR <- RTT/2
RTO <- SRTT + max(G, K * RTTVAR)
其中K=4, G表示timestamp的粒度(在CONFIG_HZ=1000时，粒度为1ms)
1.3. 后续获得更多RTT sample后，
RTTVAR <- (1 - beta) * RTTVAR + beta * |SRTT - R|
SRTT <- (1 - alpha) * SRTT + alpha * R
其中beta = 1/4, alpha = 1/8
1.4. Whenever RTO is computed, if it is less than 1 second, then the
RTO SHOULD be rounder up to 1 second.
1.5. A maximum value MAY be placed on RTO provided it is at least 60 seconds.
RTTVAR表示的是平滑过的平均偏差，SRTT表示的平滑过的RTT。这两个值的具体含义会在后面介绍
具体实现的时候进一步的解释。
以上是计算一个初始RTO值的过程，当连续出现RTO超时后，
RTO值会用一个叫做指数回避的策略进行调整，下面来具体介绍。
RTO timer的管理
2.1. 发送一个带有数据的包后，如果RTO timer未启动，启动RTO timer
2.2. 当所有发送的数据都被确认后，关闭RTO timer
2.3. 当收到一个ACK确认了新数据后，重新设置RTO时间为当前RTO值
如果RTO超时了
2.4. 重传最早的一个未被确认的数据包(序号最小的，即tp->snd_una)
2.5. RTO <- RTO * 2 ("back off the timer"，即指数回避策略)
2.6. 重现设定RTO时间为当前RTO值
2.7. 如果是在等待SYN包的ACK时RTO超时的，在连接建立之后，会将RTO从TCP_TIMEOUT_INIT
改为TCP_TIMEOUT_FALLBACK(3s)
就是如果syn包被重传过，则上一节第一步中的RTO则会从1s被重设为3s。
RFC6298中的其他要点
Note that a TCP implementation MAY clear SRTT and RTTVAR after
backing off the timer multiple times as it is likely that the current
SRTT and RTTVAR are bogus in this situation. Once SRTT and RTTVAR
are cleared, they should be initialized with the next RTT sample
taken per (1.2) rather than using (1.3).
1.1和2.7是RFC6298与RFC2988的主要不同，RFC6298在Appendix A中详细解释了为什么将INIT_RTO从
3s降到1s。里面有一些dataset的测试数据证明，有兴趣的话可以看一看。
Linux实现之RTO计算
以下开始分析Linux 3.10关于RTO的具体实现，序号与RFC原理中的需要一一对应。
首先是RTO计算相关的部分。
在理解这部分代码之前，有几个关键变量需要解释一下。
tp->srtt实际上存的是8SRTT，而tp->rttvar实际上存储的是4RTTVAR。
所以在后续代码注释中，也会使用大小写加以区分。使用大写时与RFC定义的变量含义一致。
1.1. 对应在net/ipv4/tcp.c line372 tcp_init_sock()
...
tcp_init_xmit_timers(sk); // 初始化tcp中timer对应的处理函数
...
icsk->icsk_rto = TCP_TIMEOUT_INIT; // 初始RTO设为1s
tp->mdev = TCP_TIMEOUT_INIT; // 初始medium deviation为1s
...
1.2. 对应net/ipv4/tcp_input.c line639 tcp_rtt_estimator()
...
if (tp->srtt != 0) {
...
} else { // 第一次获取RTT sample
tp->srtt = m << 3; // SRTT = RTT, 需要注意的是tp->srtt存的是8*SRTT
/* RTTVAR = RTT/2, 需要注意的是tp->rttvar存的是4*RTTVAR
* tcp_rto_min(sk)限制了rttvar的最小值为TCP_RTO_MIN(HZ/5)=200ms */
tp->mdev = m << 1;
tp->mdev_max = tp->rttvar = max(tp->mdev, tcp_rto_min(sk));
/* 记录引起rttvar改变的序列号，用于后续判断是否过了一个RTT，这是常用技巧 */
tp->rtt_seq = tp->snd_nxt; // 注意这里是snd_nxt，不是snd_una
}
1.3. 对应net/ipv4/tcp_input.c line639 tcp_rtt_estimator()
long m = mrtt; // RTT
if (m == 0)
m = 1;
if (tp->srtt != 0) {
m -= (tp->srtt >> 3); // m = RTT - SRTT
tp->srtt += m; // 8SRTT = 7 * SRTT + 1 * RTT
if (m < 0) {
m = -m; // m = |RTT - SRTT|
m -= (tp->mdev >> 2); // m = |RTT - SRTT| - RTTVAR
if (m > 0)
/* 此处m>0意味着，RTT与SRTT之间的波动过大，甚至烧过了RTTVAR
* 因此选择使用更小的beta值= 1/(4*8)
* 执行下面语句后，再执行tp->mdev += m则会得到如下结果
* RTTVAR = (1-1/32)RTTVAR + |RTT - SRTT|
* 这样做的目的是避免突发的RTT变化，对RTTVAR的历史记录造成过大的影响
*/
m >>= 3; // m = 1/8 (|RTT - SRTT| - RTTVAR)
} else {
m -= (tp->mdev >> 2); // m = |RTT - SRTT| - RTTVAR
}
tp->mdev += m; // 4RTTVAR = 3RTTVAR + |RTT - SRTT|
if (tp->mdev > tp->mdev_max) {
tp->mdev_max = tp->mdev;
if (tp->mdev_max > tp->rttvar)
/* 真正的RTTVAR会取一个RTT中最大的RTTVAR，是一种相对保守的策
* 因为计算略微偏大的RTO不会引起大问题，
* 但如果计算的RTO偏小则可能引起spurious retransmission
tp->rttvar = tp->mdev_max;
}
/* 如果过了一个RTT，则重置mdev_max，并适当调整rttvar */
if (after(tp->snd_una, tp->rtt_seq)) {
/* 目前看到的代码里面唯一可能导致mdev_max < rttvar的代码就是
* tp->mdev_max = tcp_rto_min(sk);
*/
if (tp->mdev_max < tp->rttvar)
tp->rttvar -= (tp->rttvar - tp->mdev_max) >> 2;
tp->rtt_seq = tp->snd_nxt;
tp->mdev_max = tcp_rto_min(sk); // 每过一个RTT重置mdev_max
}
}
1.4 根据代码和实际测量值，均未发现Linux有将RTO设置round to 1s了
1.5 net/ipv4/tcp_input.c line705 tcp_set_rto()
/*1.2和1.3都只是计算srtt和rttvar，并未计算rto */
inet_csk(sk)->icsk_rto = __tcp_set_rto(tp); // 根据srtt和rttvar计算rto
tcp_bound_rto(sk); // 限制rto的最大值
其中，__tcp_set_rto(tp)和tcp_bound_rto(sk)的代码如下：
static inline u32 __tcp_set_rto(const struct tcp_sock *tp)
{
return (tp->srtt >> 3) + tp->rttvar; // RTO = SRTT + 4 * RTTVAR
}
static inline void tcp_bound_rto(const struct sock *sk)
{
if (inet_csk(sk)->icsk_rto > TCP_RTO_MAX)
inet_csk(sk)->icsk_rto = TCP_RTO_MAX; // TCP_RTO_MAX = 120s
}
为了更好的理解RTT采样和RTO的整体流程，可以参考这篇资料，尤其是最后一张函数关系调用图。
关键就是理解下面这个函数的调用过程
void tcp_valid_rtt_meas(struct sock *sk, u32 seq_rtt)
{
tcp_rtt_estimator(sk, seq_rtt); // 根据RTT sample，更新SRTT和RTTVAR
tcp_set_rto(sk); // 重新计算RTO值
inet_csk(sk)->icsk_backoff = 0; // 将backoff清零
}
Linux实现之RTO timer的管理
2.1 net/ipv4/tcp_output.c line72 tcp_event_new_data_sent()
...
unsigned int prior_packets = tp->packets_out;
...
tp->packets_out += tcp_skb_pcount(skb); // 更新已经发出未被确认的数据包数目
if (!prior_packets // 如果prior_packets=0，表示之前未发送过数据，因此需要启动timer
||...)
tcp_rearm_rto(sk); // 启动RTO timer
2.2 net/ipv4/tcp_input.c line2926 tcp_rearm_rto()
...
/* 如果packet_out=0，则停掉RTO timer */
if (!tp->packets_out) {
inet_csk_clear_xmit_timer(sk, ICSK_TIME_RETRANS);
}
2.3 net/ipv4/tcp_input.c line3105 tcp_clean_rtx_queue()
...
if (flag & FLA_ACKED) {
...
tcp_ack_update_rtt(sk, flag, seq_rtt); // 得到一个RTT sample，更新RTO
tcp_rearm_rto(sk); // 重设RTO timer
...
}
2.4+2.5+2.6 net/ipv4/tcp_timer.c line340 tcp_retransmit_timer()
...
tcp_enter_loss(sk, 0); // 进入RTO超时重传阶段
if (tcp_retransmit_skb(sk, tcp_write_queue_head(sk)) > 0) // 重传第一个未确认的数据包
...
/* 如果这是一个thin的TCP流，则不适用backoff机制
* 什么是thin tcp呢？就是网络中in_flight的数据包很少的流
* 具体请看tcp_stream_is_thin(tp)
*/
if (STREAM IS THIN ?) {
icsk->icsk_backoff = 0;
icsk->icsk_rto = min(__tcp_set_rto(tp), TCP_RTO_MAX);
} else {
/* Use normal (exponential) backoff */
icsk->icsk_rto = min(icsk->icsk_rto << 1, TCP_RTO_MAX); // 步骤2.5
}
/* 步骤2.6 重设RTO timer */
inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS, icsk->icsk_rto, TCP_RTO_MAX);
2.7 net/ipv4/tcp_metrics.c line441 tcp_init_metrics()
/* tcp_init_metrics是在TCP建立连接之后进行的初始化动作
* 一个明显的例子： tcp_finish_connect() => tcp_init_metrics()
*/
...
if (tp->srtt == 0) {
/* 如果在3WHS阶段没有获得srtt，基本就意味着发生了重传 */
tp->mdev = tp->mdev_max = tp->rttvar = TCP_TIMEOUT_FALLBACK;
inet_csk(sk)->icsk_rto = TCP_TIMEOUT_FALLBACK;
}
至此，基本上把Linux 3.10中关于RTO的基本逻辑弄清楚了。RFC6298中proposed的算法的
主要步骤也找到了对应的代码实现位置。