首页 > kernel, 协议 > tcp中RTO的计算以及linux下的实现

tcp中RTO的计算以及linux下的实现

2012年8月1日

原创文章,转载请注明: 转载自pagefault

本文链接地址: tcp中RTO的计算以及linux下的实现

计算RTT以及RTO的代码比较简单,我们先来看原理,首先相关的rfc有两篇分别是rfc793以及rfc6298,而相关的paper有一篇,那就是Van Jacobson和Michael J. Karels的 Congestion Avoidance and Control这篇paper,这篇1988年的paper中描述的RTT计算方法,就是我们当前所使用的计算方法,可能有的操作系统有一点修改,不过基本的东西都一样。

首先RTT是什么,RTT简单来说,就是我发送一个数据包,然后对端回一个ack,那么当我接到ack之后,就能计算出从我发送出包到接到过了多久,这个时间就是RTT。RTT的计算是很简单的,就是一个时间差。

而RTO呢,RTO也就是tcp在发送一个数据包之后,会启动一个重传定时器,而RTO就是这个定时器的重传时间,那么这个时候,就有问题了,由于RTO是指的这次发送当前数据包所预估超时时间,那么RTO就需要一个很好的统计方法,来更好的预测这次的超时时间。

我们所能想到的最简单的方法,那就是取平均数,比如第一次RTT是500毫秒,第二次是800毫秒,那么第三次发送的时候,RTO就应该是650毫秒。其实经典的RTO计算方法和取平均有点类似,只不过因子不太一样,取平均的话,也就是老的RTO和新的RTT都是占50%的权重,而在经典的RTO计算中就有些变化了。

来看经典的RTT计算方法,这个计算方法是在RFC793中提出的,计算方法是这样子的:

  SRTT = ( ALPHA * SRTT ) + ((1-ALPHA) * RTT)
    RTO = min[UBOUND,max[LBOUND,(BETA*SRTT)]]

其中ALPHA是一个scala因子,一般来说建议ALPHA是0.8和0.9.UBOUND就是RTO的最大值,LBOUND是RTO的最小值,BETA也是一个因子,建议是1.3-2.0。

这里可以看到在经典的RTO计算方法中会有一个很大的问题,就是当RTT对RTO的影响太小了,也就是说经典的RTO计算方法在RTT变化比较大的网络中,会表现的非常不好的。

于是在1988年,大神Van jacobson和Michael J. Karels的 Congestion Avoidance and Control这篇paper中,描述了一种新的计算方法,这里对于rtt的采样,多添加了一个因素,那就是均差(mean deviation),而这里并不是传统意义上的均差,使用的平均数其实就是我们在经典方法中的srtt。 计算方法是这样子的:

Err ≡ m−a
a←a+gErr
v ← v+g(|Err|−v)

其中m就是当前最新的RTT,然后 a就是经典方法中的的SRTT,然后v就是均差,而Err顾名思义,就是我们预测的RTT的错误偏差。
可是这里有个问题,那就是由于因子g的存在,那么就有可能出现浮点数,因此我们只需要做个变化,让g=1/2^n,那么上面的的等式就变为下面这个了

2^na ← 2^na+Err 
2^nv ← 2^nv+(|Err|−v)

假设g=1/8,也就是n为3,并且sa为2^n*a,sv为2^n*v,那么对应的c伪码就如下,:

/∗ update Average estimator ∗/
m −= (sa >> 3); 
sa += m;
/∗ update Deviation estimator ∗/
if (m < 0)
   m = −m; 
m −= (sv >> 2);
sv += m;
rto = (sa >> 3) + sv;

然后我们再来看rfc6298中对RTO计算的描述,这个rfc基本上就和Van jacobson和Michael J. Karels所描述的计算方法一致。其中第一次RTO的计算方法是这样子的:


                  SRTT <- R
                 RTTVAR <- R/2 
                 RTO <- SRTT + max (G, K*RTTVAR)

后续的RTO计算是这样子的:


            RTTVAR <- (1 - beta) * RTTVAR + beta * |SRTT - R'| 
            SRTT <- (1 - alpha) * SRTT + alpha * R'  
            RTO <- SRTT + max (G, 4*RTTVAR) 

可以看到和上面的公式有差别,这里RTTVAR就是上面的v,而SRTT就是上面的a。
其实这个公式和jacobson的公式是一样的,只需要对公式做个变化。比如

SRTT <- (1 - alpha) * SRTT + alpha * R' 

这个公式我们可以这样子来:

SRTT <- SRTT - SRTT*alpha + alpha*R` => SRTT <- SRTT + alpha*(R` - SRTT)

于是我们可以看到这个公式就和上面的公式a是相同的了。

最后我们来看linux下的实现,linux的实现和jacobson所描述的伪码基本一致,这里beta因子是1/4,而alpha因子是1/8.
linux下对应的计算是在tcp_rtt_estimator这个函数中,这个函数的第二个参数,就是当前最新的rtt值。linux的实现多了两个东西,分别是mdev和medev_max, 其中mdev就是上面计算方法中的RTTVAR,而mdev_max则就是每次均差的最大值(linux最小是50毫秒).而在linux中RTTVAR也就等于mdev_max.

这里要注意一个东西,那就是RTT的计算是每次都会做的,而对于RTO来说是和数据段相关的,也就是说每次发送的时候估计rtt,然后当估算RTT时发送的段收到ack,之后就应该进行下一次估算了(也就是一个RTT过去了),也就是需要调节对应的rttvar,并且重新初始化一些值.


	u32	srtt;		/* smoothed round trip time << 3	*/
	u32	mdev;		/* medium deviation			*/
	u32	mdev_max;	/* maximal mdev for the last rtt period	*/
	u32	rttvar;		/* smoothed mdev_max			*/
	u32	rtt_seq;	/* sequence number to update rttvar	*/

static void tcp_rtt_estimator(struct sock *sk, const __u32 mrtt)
{
	struct tcp_sock *tp = tcp_sk(sk);
	long m = mrtt; /* RTT */

	/*	The following amusing code comes from Jacobson's
	 *	article in SIGCOMM '88.  Note that rtt and mdev
	 *	are scaled versions of rtt and mean deviation.
	 *	This is designed to be as fast as possible
	 *	m stands for "measurement".
	 *
	 *	On a 1990 paper the rto value is changed to:
	 *	RTO = rtt + 4 * mdev
	 *
	 * Funny. This algorithm seems to be very broken.
	 * These formulae increase RTO, when it should be decreased, increase
	 * too slowly, when it should be increased quickly, decrease too quickly
	 * etc. I guess in BSD RTO takes ONE value, so that it is absolutely
	 * does not matter how to _calculate_ it. Seems, it was trap
	 * that VJ failed to avoid. 8)
	 */
	if (m == 0)
		m = 1;
	if (tp->srtt != 0) {
//开始更新a也就是srtt.可以看到因子为1/8.
		m -= (tp->srtt >> 3);	/* m is now error in rtt est */
		tp->srtt += m;		/* rtt = 7/8 rtt + 1/8 new */
//开始更新mean deviation.
		if (m < 0) {
			m = -m;		/* m is now abs(error) */
			m -= (tp->mdev >> 2);   /* similar update on mdev */
			/* 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.
			 */
			if (m > 0)
				m >>= 3;
		} else {
			m -= (tp->mdev >> 2);   /* similar update on mdev */
		}
		tp->mdev += m;	    	/* mdev = 3/4 mdev + 1/4 new */
//找到最大值付给rttvar
		if (tp->mdev > tp->mdev_max) {
			tp->mdev_max = tp->mdev;
			if (tp->mdev_max > tp->rttvar)
				tp->rttvar = tp->mdev_max;
		}

//本次RTT的估算结束
		if (after(tp->snd_una, tp->rtt_seq)) {
//调节rttvar
			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);
		}
	} else {
//第一次进来的情况
		/* no previous measure. */
		tp->srtt = m << 3;	/* take the measured time to be rtt */
		tp->mdev = m << 1;	/* make sure rto = 3*rtt */
		tp->mdev_max = tp->rttvar = max(tp->mdev, tcp_rto_min(sk));
		tp->rtt_seq = tp->snd_nxt;
	}
}

最后来看一下RTO的计算,RTO的计算在__tcp_set_rto中,这个计算它是严格遵守rfc6298中的描述。

static inline u32 __tcp_set_rto(const struct tcp_sock *tp)
{
	return (tp->srtt >> 3) + tp->rttvar;
}

最后这里有一个要注意的地方,那就是rto的最小值,一般来说,在linux下,这个值是200ms,也就是说最少要200毫秒才会发生重传,而这个值的修改是可以通过ip route来修改的,如何更改请看这里:

http://docs.redhat.com/docs/en-US/Red_Hat_Enterprise_Linux/4/html/Release_Notes/U7/ppc/ar01s04.html

而有关定时器退避这些,我在前面的blog有分析,感兴趣的可以看我前面的blog.

Share
分类: kernel, 协议 标签: , ,
本文的评论功能被关闭了.