TCP中RTT的测量和RTO的计算

news/2024/5/17 19:18:44 标签: tcp, 路由器, 网络

内核版本：3.2.12
本文主要剖析：RTT的测量、RTO的计算
作者：zhangskd @ csdn

 

概述

 

RTO（Retransmission TimeOut）即重传超时时间。
TCP超时与重传中一个很最重要的部分是对一个给定连接的往返时间（RTT）的测量。由于网络流量的变化，
这个时间会相应地发生改变，TCP需要跟踪这些变化并动态调整超时时间RTO。
RFC2988中是这样描述RTO的：

“The Transmission Control Protocol (TCP) uses a retransmission timer to ensure
data delivery in the absence of any feedback from the remote data receiver. The 
duration of this timer is referred to as RTO (retransmission timeout).”

RTT（Round Trip Time）由三部分组成：链路的传播时间（propagation delay）、末端系统的处理时间、
路由器缓存中的排队和处理时间（queuing delay）。
其中，前两个部分的值对于一个TCP连接相对固定，路由器缓存中的排队和处理时间会随着整个网络拥塞程度
的变化而变化。所以RTT的变化在一定程度上反应了网络的拥塞程度。

 

平均偏差

 

平均偏差（mean deviation），简写为mdev。
It is the mean of the distances between each value and the mean. It gives us an idea of how spread
out from the center the set of values is.
Here's the formula.

通过计算平均偏差，可以知道一组数据的波动情况。
在这里，平均偏差可以用来衡量RTT的抖动情况。

 

RTT测量原理

 

RTT的测量可以采用两种方法：

（1）TCP Timestamp选项
在前面的blog中有详细的介绍过这个选项，TCP时间戳选项可以用来精确的测量RTT。
RTT = 当前时间 -  数据包中Timestamp选项的回显时间
这个回显时间是该数据包发出去的时间，知道了数据包的接收时间（当前时间）和发送时间
（回显时间），就可以轻松的得到RTT的一个测量值。

（2）重传队列中数据包的TCP控制块
在TCP重传队列中保存着发送而未被确认的数据包，数据包skb中的TCP控制块包含着一个变量，
tcp_skb_cb->when，记录了该数据包的第一次发送时间。
RTT = 当前时间 - when

有人可能会问：既然不用TCP Timestamp选项就能测量出RTT，为什么还要多此一举？
这是因为方法一比方法二的功能更加强大，它们是有区别的。
“TCP must use Karn's algorithm for taking RTT samples. That is, RTT samples MUST NOT
be made using segments that were retransmitted (and thus for which it is ambiguious whether
the reply was for the first instance of the packet or a later instance). The only case when TCP
can safely take RTT samples from retransmitted segments is when the TCP timestamp option
is employed, since the timestamp option removes the ambiguity regarding which instance of
the data segment triggered the acknowledgement.”
对于重传的数据包的响应，方法1可以用它来采集一个新的RTT测量样本，而方法二则不能。因为
TCP Timestamp选项可以区分这个响应是原始数据包还是重传数据包触发的，从而计算出准确的
RTT值。

 

RTT测量实现

 

发送方每接收到一个ACK，都会调用tcp_ack()来处理。
tcp_ack()中会调用tcp_clean_rtx_queue()来删除重传队列中已经被确认的数据段。
在tcp_clean_rtx_queue()中：
如果ACK确认了重传的数据包，则seq_rtt = -1；
否则，seq_rtt = now - scb->when；
然后调用tcp_ack_update_rtt(sk, flag, seq_rtt)来更新RTT和RTO。

[java]  view plain copy
  1. static inline void tcp_ack_update_rtt (struct sock *sk, const in flag,   
  2.         const s32 seq_rtt)  
  3. {  
  4.     const struct tcp_sock *tp = tcp_sk(sk);  
  5.     /* Note that peer MAY send zero echo. In this case it is ignored. (rfc1323) */  
  6.     /* 如果有启用TCP Timestamp选项，且接收方的回显不为0*/  
  7.     if (tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr)  
  8.         tcp_ack_saw_tstamp(sk, flag); /* 方法一*/  
  9.   
  10.     else if (seq_rtt >= 0) /* 不能是重传数据包的ACK */  
  11.         tcp_ack_no_tstamp(sk, seq_rtt, flag); /* 方法二*/  
  12. }  

方法一：tcp_ack_saw_tstamp()

[java]  view plain copy
  1. /* Read draft-ietf-tcplw-high-performance before mucking with this code. 
  2.  * (Supersedes RFC1323) 
  3.  */  
  4. static void tcp_ack_saw_tstamp(struct sock *sk, int flag)  
  5. {  
  6.     /* RTTM Rule : A TSecr value received in a segment is used to update the 
  7.      * averaged RTT measurement only if the segment acknowledges some new 
  8.      * data, i.e., only if it advances the left edge of the send window. 
  9.      * 
  10.      * See draft-ietf-tcplw-high-performance-00, section 3.3. 
  11.      * 1998/04/10 Andrey V. Savochkin saw@msu.ru 
  12.      * 
  13.      * Changed : reset backoff as soon as we see the first valid sample. 
  14.      * If we do not, we get strongly overestimated rto. With timestamps  
  15.      * samples are accepted even from very old segments: f.e., when  
  16.      * rtt = 1 increases to 8, we retransmit 5 times and after 8 seconds 
  17.      * delayed answer arrives rto becomes 120 seconds! If at least one  
  18.      * of segments in window is lost... Volia. 
  19.      * ——ANK(010210) 
  20.      */  
  21.     struct tcp_sock *tp = tcp_sk(sk);  
  22.     /* RTT采样值：now - rcv_tsecr */  
  23.     tcp_valid_rtt_meas(sk, tcp_time_stamp - tp->rx_opt.rcv_tsecr);  
  24. }  

方法二：tcp_ack_no_tstamp()

[java]  view plain copy
  1. static void tcp_ack_no_tstamp(struct sock *sk, u32 seq_rtt, int flag)  
  2. {  
  3.     /* We don't have a timestsamp. Can only use packets that are not 
  4.      * retransmitted to determine rtt estimates. Also, we must not reset 
  5.      * the backoff for rto until we get a non-retransmitted packet. This  
  6.      * allows us to deal with a situation where the network delay has 
  7.      * increased suddenly. I.e. Karn's algorithm. (SIGCOMM '87, p5.) 
  8.      */  
  9.     if (flag & FLAG_RETRANS_DATA_ACKED)  
  10.         return; /* 如果ACK确认的是重传的数据包，则不进行RTT采样*/  
  11.     /* RTT采样值：seq_rtt，这个值是在tcp_clean_rtx_queue()中计算得到的。*/  
  12.     tcp_valid_rtt_meas(sk, seq_rtt);  
  13. }  

OK，到这边RTT的测量已经结束了，接下来就是RTO值的计算。

 

RTO计算原理

 

涉及到的变量

[java]  view plain copy
  1. struct tcp_sock {  
  2.     ...  
  3.   
  4.     /* RTT measurement */  
  5.     u32 srtt; /* smoothed round trip time << 3 */  
  6.     u32 mdev; /* medium deviation */  
  7.     u32 mdev_max; /* maximal mdev for the last rtt period */  
  8.     u32 rttvar /* smoothed mdev_max */  
  9.     u32 rtt_seq; /* sequence number to update rttvar */  
  10.   
  11.     ...  
  12. }  

srtt为经过平滑后的RTT值，它代表着当前的RTT值，每收到一个ACK更新一次。
为了避免浮点运算，它是实际RTT值的8倍。
mdev为RTT的平均偏差，用来衡量RTT的抖动，每收到一个ACK更新一次。
mdev_max为上一个RTT内的最大mdev，代表上个RTT内时延的波动情况，有效期为一个RTT。
rttvar为mdev_max的平滑值，可升可降，代表着连接的抖动情况，在连接断开前都有效。
“To compute the current RTO, a TCP sender maintains two state variables, 
SRTT (smoothed round-trip time) and RTTVAR (round-trip time variation).”
实际上，RTO = srtt >> 3 + rttvar.

rtt表示新的RTT测量值。
old_srtt表示srtt更新前的srtt >>3，即旧的srtt值。
new_srtt表示srtt更新后的srtt>>3，即新的srtt值。
old_mdev表示旧的mdev。
new_mdev表示更新后的mdev。

（1）获得第一个RTT测量值
srtt = rtt << 3;
mdev = rtt << 1;
mdev_max = rttvar = max(mdev, rto_min);
所以，获得第一个RTT测量值后的RTO = rtt + rttvar，如果mdev = 2*rtt > rto_min，
那么RTO = 3 * rtt；否则，RTO = rtt + rto_min。

（2）获得第n个RTT测量值(n >= 2)
srtt的更新：new_srtt = 7/8 old_srtt + 1/8 rtt
mdev的更新：
err = rtt - old_srtt
当RTT变小时，即err < 0时
1) 如果|err| > 1/4 old_mdev，则new_mdev = 31/32 old_mdev + 1/8 |err|
此时：old_mdev < new_mdev < 3/4 old_mdev + |err|
new_mdev有稍微变大，但是增大得不多。由于RTT是变小，所以RTO也要变小，如果
new_mdev增大很多(比如：new_mdev = 3/4 old_mdev + |err|)，就会导致RTO变大，不符合
我们的预期。
“This is similar to one of Eifel findings. Eifel blocks mdev updates when rtt decreases.
This solution is a bit different : we use finer gain for mdev in this case (alpha * beta).
Like Eifel it also prevents growth of rto, but also it limits too fast rto decreases, happening
in pure Eifel.”
2) 如果|err| <= 1/4 old_mdev，则new_mdev = 3/4 old_mdev + |err|
此时：new_mdev < old_mdev
new_mdev变小，会导致RTO变小，符合我们的预期。

当RTT变大时，即err > 0时
new_mdev = 3/4 old_mdev + |err|
此时：new_mdev > old_mdev
new_mdev变大，会导致RTO变大，这也符合我们的预期。

mdev_max和rttvar的更新
在每个RTT开始时，mdev_max = rto_min。
如果在此RTO内，有更大的mdev，则更新mdev_max。
如果mdev_max > rttvar，则 rttvar = mdev_max;
否则，本RTT结束后，rttvar -= (rttvar - mdev_max) >> 2。
这样一来，就可以通过mdev_max来调节rttvar，间接的调节RTO。

 

RTO计算实现

 

不管是方法一还是方法二，最终都调用tcp_valid_rtt_meas()来更新RTT和RTO。

[java]  view plain copy
  1. /* seq_rtt为此次得到的RTT测量值。*/  
  2. void tcp_valid_rtt_meas(struct sock *sk, u32 seq_rtt)  
  3. {  
  4.     tcp_rtt_estimator(sk, seq_rtt); /* 更新相关值*/  
  5.     tcp_set_rto(sk); /*设置新的RTO*/  
  6.     inet_csk(sk)->icsk_backoff = 0; /* 清零退避指数*/  
  7. }  

RTO = srtt >> 8 + rttvar。而srtt和rttvar的更新都是在tcp_rtt_estimator()中进行的。

[java]  view plain copy
  1. /* Called to compute a smoothed rtt estimate. The data fed to this  
  2.  * routine either comes from timestamps, or from segments that were 
  3.  * known _not_ to have been retransmitted [see Karn/Partridge Proceedings 
  4.  * SIGCOMM 87]. The algorithm is from the SIGCOMM 88 piece by Van 
  5.  * Jacobson. 
  6.  * NOTE : the next three routines used to be one big routine. 
  7.  * To save cycles in the RFC 1323 implementation it was better to break it 
  8.  * up into three procedures. ——erics 
  9.  */  
  10.   
  11. static void tcp_rtt_estimator (struct sock *sk, const __u32 mrtt)  
  12. {  
  13.     struct tcp_sock *tp = tcp_sk(sk);  
  14.     long m = mrtt; /*此为得到的新的RTT测量值*/  
  15.   
  16.     /* The following amusing code comes from Jacobson's article in 
  17.      * SIGCOMM '88. Note that rtt and mdev are scaled versions of rtt and 
  18.      * mean deviation. This is designed to be as fast as possible 
  19.      * m stands for "measurement". 
  20.      *  
  21.      * On a 1990 paper the rto value is changed to : 
  22.      * RTO = rtt + 4 * mdev 
  23.      * 
  24.      * Funny. This algorithm seems to be very broken. 
  25.      * These formulae increase RTO, when it should be decreased, increase 
  26.      * too slowly, when it should be increased quickly, decrease too quickly 
  27.      * etc. I guess in BSD RTO takes ONE value, so that it is absolutely does 
  28.      * not matter how to calculate it. Seems, it was trap that VJ failed to  
  29.      * avoid. 8) 
  30.      */  
  31.     if (m == 0)  
  32.         m = 1; /* RTT的采样值不能为0 */  
  33.   
  34.     /* 不是得到第一个RTT采样*/  
  35.     if (tp->srtt != 0) {  
  36.         m -= (tp->srtt >> 3); /* m is now error in rtt est */  
  37.         tp->srtt += m; /* rtt = 7/8 rtt + 1/8 new ，更新srtt*/  
  38.   
  39.         if (m < 0) { /*RTT变小*/  
  40.             m = -m; /* m is now abs(error) */  
  41.             m -= (tp->mdev >> 2); /* similar update on mdev */  
  42.   
  43.             /* This is similar to one of Eifel findings. 
  44.              * Eifel blocks mdev updates when rtt decreases. 
  45.              * This solution is a bit different : we use finer gain 
  46.              * mdev in this case (alpha * beta). 
  47.              * Like Eifel it also prevents growth of rto, but also it 
  48.              * limits too fast rto decreases, happening in pure Eifel. 
  49.              */  
  50.              if (m > 0) /* |err| > 1/4 mdev */  
  51.                  m >>= 3;  
  52.   
  53.         } else { /* RTT变大 */  
  54.             m -= (tp->mdev >> 2); /* similar update on mdev */  
  55.         }  
  56.   
  57.         tp->mdev += m; /* mdev = 3/4 mdev + 1/4 new，更新mdev */  
  58.   
  59.         /* 更新mdev_max和rttvar */  
  60.         if (tp->mdev > tp->mdev_max) {  
  61.             tp->mdev_max = tp->mdev;  
  62.             if (tp->mdev_max > tp->rttvar )  
  63.                 tp->rttvar = tp->mdev_max;  
  64.         }  
  65.   
  66.        /* 过了一个RTT了，更新mdev_max和rttvar */  
  67.         if (after(tp->snd_una, tp->rtt_seq)) {  
  68.             if (tp->mdev_max < tp->rttvar)/*减小rttvar */  
  69.                 tp->rttvar -= (tp->rttvar - tp->mdev_max) >> 2;   
  70.             tp->rtt_seq = tp->snd_nxt;  
  71.             tp->mdev_max = tcp_rto_min(sk); /*重置mdev_max */  
  72.         }  
  73.   
  74.     } else {   
  75.     /* 获得第一个RTT采样*/  
  76.         /* no previous measure. */  
  77.         tp->srtt = m << 3; /* take the measured time to be rtt */  
  78.         tp->mdev = m << 1; /* make sure rto = 3 * rtt */  
  79.         tp->mdev_max = tp->rttvar = max(tp->mdev, tcp_rto_min(sk));  
  80.         tp->rtt_seq = tp->snd_nxt; /*设置更新mdev_max的时间*/  
  81.     }  
  82. }  

rto_min的取值如下：

[java]  view plain copy
  1. /* 最大的RTO为120s，指数退避时不能超过这个值 */  
  2. #define TCP_RTO_MAX ((unsigned) (120*HZ))  
  3.   
  4. /* 最小的RTO为200ms，rttvar不能低于这个值 */  
  5. #define TCP_RTO_MIN ((unsigned) (HZ / 5))  
  6.   
  7. /* 还没有计算出RTO值前的RTO初始值，为1s */  
  8. #define TCP_TIMEOUT_INIT ((unsigned) (1 * HZ))  
  9.   
  10. /* Compute the actual rto_min value */  
  11. static inline u32 tcp_rto_min (struct sock *sk)  
  12. {  
  13.     const struct dst_entry *dst = __sk_dst_get(sk);  
  14.     u32 rto_min = TCP_RTO_MIN;  
  15.   
  16.     /*如果路由缓存中存在RTO_MIN，则取其为最小RTO*/  
  17.     if (dst && dst_metric_locked(dst, RTAX_RTO_MIN))  
  18.         rto_min = dst_metric_rtt(dst, RTAX_RTO_MIN));  
  19.     return rto_min;  
  20. }  

RTO的设置：

[java]  view plain copy
  1. /* Calculate rto without backoff. This is the second half of Van Jacobson's  
  2.  * routine referred to above. 
  3.  */  
  4. static inline void tcp_set_rto(struct sock *sk)  
  5. {  
  6.     const struct tcp_sock *tp = tcp_sk(sk);  
  7.     inet_csk(sk)->icsk_rto = __tcp_set_rto(tp);  
  8.     tcp_bound_rto(sk);  
  9. }  
  10.   
  11. static inline u32 __tcp_set_rto(const struct tcp_sock *tp)  
  12. {  
  13.     return (tp->srtt >> 3) + tp->rttvar;  
  14. }  
  15.   
  16. static inline void tcp_bound_rto(const struct sock *sk)  
  17. {  
  18.     if (inet_csk(sk)->icsk_rto > TCP_RTO_MAX)  
  19.         inet_csk(sk)->icsk_rto = TCP_RTO_MAX;  
  20. }  

 

函数调用

 

以上涉及到的函数调用关系如下：

 

总结

 

早期的RTT的测量是采用粗粒度的定时器（Coarse grained timer），这会有比较大的误差。
现在由于TCP Timestamp选项的使用，能够更精确的测量RTT，从而计算出更加准确的RTO。

 

Reference

 

RFC 2988


http://www.niftyadmin.cn/n/1713774.html

相关文章

tcp的option字段

tcp的option字段

找到了RFC文档中关于tcp报头中option字段的内容&#xff0c;好好阅读一下&#xff0c;有时间再给翻成中文的。TCP选项(RFC793和更新的RFC1323)– 这里充满了各种组合的可能性– 应答方式“Query-Reply”&#xff0c;可以把多个选项放到一个包中– 有些高级选项在新的协议栈实现…
阅读更多...
RTMP/RTP/RTSP/RTCP的区别

RTMP/RTP/RTSP/RTCP的区别

用一句简单的话总结&#xff1a;RTSP发起/终结流媒体、RTP传输流媒体数据 、RTCP对RTP进行控制&#xff0c;同步。 之所以以前对这几个有点分不清&#xff0c;是因为CTC标准里没有对RTCP进行要求&#xff0c;因此在标准RTSP的代码中没有看到相关的部分。而在私有RTSP的代码中&a…
阅读更多...
Libevent参考手册：evbuffer：缓冲IO实用功能

Libevent参考手册：evbuffer：缓冲IO实用功能

libevent的evbuffer实现了为向后面添加数据和从前面移除数据而优化的字节队列。 evbuffer用于处理缓冲网络IO的“缓冲”部分。它不提供调度IO或者当IO就绪时触发IO的功能&#xff1a;这是bufferevent的工作。 除非特别说明&#xff0c;本章描述的函数都在event2/buffer.h中声明…
阅读更多...
libev入门

libev入门

引言 实现应用的捷径是充分利用开放源代码和开放标准等资源。为了实现视频服务器&#xff0c;研究了开源视频服务器DarwinStreamingServer&#xff0c;Reactor并发编程设计模式&#xff0c;同时还评估了Boost.Asio、ACE、libevent以及 libev等网络编程相关的库。得出的结论是基…
阅读更多...
libev库的用法

libev库的用法

libev是一个高性能的事件循环库&#xff0c;比libevent库的性能要好。Nodejs就是采用它作为底层库。libev的官方文档在 这里 &#xff0c;文档比较长。本文结合里面的例子对它的用法做些简单的总结。 Contents 例子事件循环观察器 ev_ioev_timerev_periodicev_signalev_childev…
阅读更多...
在北京的那三年———初来乍到

在北京的那三年———初来乍到

离开北京来上海快两个月了&#xff0c;突然想通过博客记录自己在北京的那三年&#xff0c;算作给自己的北漂经历一个交代&#xff0c;给未来的北漂们一点参考。 ————woxiaozhi 依然保留着那张车票&#xff0c;2010年7月19日&#xff0c;从郑州到北京西站。 早晨6点多我和…
阅读更多...
在北京的那三年——培训的日子

在北京的那三年——培训的日子

培训的日子很苦&#xff0c;但是每个学员都是怀揣着梦想来到北京的&#xff0c;所以苦也不觉得。白天上课的时间是朝九晚六&#xff0c;大家在教师附近吃了晚饭后继续回到教师自习到10点左右&#xff0c;其实关键还是在自习中让我有时间来消化白日里学的东西。晚上回到住的地方…
阅读更多...
在北京的那三年——游清华

在北京的那三年——游清华

终于&#xff0c;在一个周末的早上宿舍人对当天的安排达成一致意见————游清华。作为一个理工科的学生&#xff0c;心目中清华的名气比北大要大点&#xff0c;至少我是这么觉得的。那天我们5个人吧&#xff0c;从中关村一街步行走到清华大学西门&#xff0c;一路上不停的讨论…
阅读更多...
最新文章

Copyright @ 2022~2023