分类： LINUX
2014-03-17 21:34:46
原文地址：TCP接收端估算cwnd 作者：henrystark
作者：henrystark henrystark@126.com
Blog: http://henrystark.blog.chinaunix.net/
日期：20140315
本文可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接。如有错讹，烦请指出。
这篇文章是我在实验过程中用到的方法总结。之所以公开，是因为我的实验方法也借鉴了他人的源码。有必要把这份开源精神传递下去。但是出于保密和个人权利保护需要，并不能说明完整的方法和代码。有需要交流的同行请自行找我的联系方式。
TCP发送端有拥塞控制，根据网络状况调节cwnd，算法核心在于“拥塞状态”的控制，避免网络过度负载，选择合适的发送窗口。
TCP接收端有流量控制，目的不在约束发送端的包投递速率，而在给予发送端足够大的通告窗口，同时顾及到本端的接收速率。这样做的必要原因有：（1）糊涂窗口综合症，避免有一个字节空余就通告一个字节的场景，因为这样会严重降低有效负载率。【注 1】（2）高速链路，例如带宽10Gbps【注 2】，普通PC的总线速率只有6Gbps，过快的包投递可能会淹没缓存。这时候流控的作用就得以体现。在普通网络场景中，通告窗口awnd普遍大于cwnd，这是为了把控制权尽量交给发送方，接收方不成为限制因子。
分配合适的接收窗口需要估算对端的cwnd，一般而言，接收窗口大于cwnd的两倍。
cwnd（拥塞窗口）、awnd（通告窗口）都和RTT（往返延时）关联。要估算cwnd，调节适当的awnd，首先需要估算RTT。RTT的测量大致有两种方法【注 3】：
TCP header有timestamp和echo timestamp，发送端投递数据包、接收端回复ACK都需要携带这些数据。接收方在回复ACK时，会打入时间戳，由发送方回显。接收方在收到有时间戳回显的数据包以后，可以用当前系统时间减去时间戳，即可得出RTT。流程如下：
timestamp = time_
TCP receiver -----------------------> TCP sender
ACK packet |
|
echo timestamp = time_ |
计算RTT <-----------------------------
Data packet
RTT = time_now - time_;
这种测量RTT的策略相当简单，下面来分析优缺点。
优点：在平稳流量下，策略简单，RTT准确。平稳流量指的是没有丢包的情况，一个数据包1500byte，忽略网卡发送消耗的时间，RTT相当可靠。实验：我设置RTT为12ms，内核打印时间为13ms。
缺点：不支持时间戳选项时不可用。
这种方法在丢包情况下够不够可靠呢？丢包情况下，可能经过了较长的时间，数据包才发送。具体情形可以分为：
(1)ACK丢失。
(2)数据包丢失。
(3)发送方等待较长时间才发送新的数据包。
(4)最严重的，超时。
有丢包时，RTT计算过程如下：
timestamp = time1
TCP receiver --------------------------------------------------> TCP sender
| ACK packet, ack_seq = 9000 |
| Data packet, seq = 9000 |
| drop by Switch<--------------------------------- |
| echo ts = time1 |
| dup ACK, ack_seq = 9000 (新的数据包到达接收端，ACK由数据包驱动) | 详见【注 4】
|-------------------------------------------------------------------> |
| |
| echo timestamp = time2 |
计算RTT <---------------------------------------------------------------
Data packet retran, seq = 9000
RTT = time_now - time2；
上面列举的四种情况，能造成RTT测量偏大的只有后两种。超时情况下，发送端没有收到ACK，这时重发数据包的时间戳会造成RTT突发增大。除了超时，还有没有发送方等待较长时间才投递数据包的情况呢？也确实有，为了提升效率，发送端通常在数据负荷不够的情况下，会等待一段时间。实际上，关于丢包和有delay情况下的RTT测量，rfc1072： TCP Extensions for Long-Delay Paths 4.2节【引用 1】 早有讨论。rfc1072主要论述了发送端测量RTT的方式，接收端使用时间戳测量时，原理和发送端是一样的。当然，任何事情都少不了例外，我在实验过程中，确实看到接收端用时间戳测量RTT有偏大的情况，而且不止一次【注 5】。
源码,位于linux-3.2.18/net/ipv4/tcp_input.c:
static inline void tcp_rcv_rtt_measure(struct tcp_sock *tp)
{
if (tp->rcv_rtt_est.time == 0) //第一次接收到数据，三次握手之后，才开始传送数据的阶段
goto new_measure;
if (before(tp->rcv_nxt, tp->rcv_rtt_est.seq)) //这里是判断数据量是否够多，如果有awnd这么多，就可以更新RTT，其中rcv_nxt是接收窗口的边界，表示期望接收的下一个数据包
return;
tcp_rcv_rtt_update(tp, jiffies - tp->rcv_rtt_est.time, 1); //更新RTT，还是用jiffes
new_measure:
tp->rcv_rtt_est.seq = tp->rcv_nxt + tp->rcv_wnd;
tp->rcv_rtt_est.time = tcp_time_stamp;
}
这种方法原理也很简单，判断接收端是否已经收到了一个接收窗口的数据。把这个时间间隔作为一个RTT。然而，这种方法有明显的缺陷，就是RTT偏大，发送端cwnd通常小于接收端awnd。并且这种方法在丢包时，RTT测量也会偏大，因为丢包时，收取一个满窗的数据可能要等很久。
static inline void tcp_rcv_rtt_measure_ts(struct sock *sk,
const struct sk_buff *skb)
{
struct tcp_sock *tp = tcp_sk(sk);
if (tp->rx_opt.rcv_tsecr && //一系列选项判断，是否支持时间戳，数据包是否大于MSS
(TCP_SKB_CB(skb)->end_seq -
TCP_SKB_CB(skb)->seq >= inet_csk(sk)->icsk_ack.rcv_mss))
tcp_rcv_rtt_update(tp, tcp_time_stamp - tp->rx_opt.rcv_tsecr, 0);
}
统计RTT之后，就可以估算发送端拥塞窗口。第二种方法估算cwnd显然偏大。第一种方法比较靠谱。
这些源码很容易懂，无关紧要，注意看函数上面的注释，这里写出了方法的起源：DRS【引 2】。
/* Receiver "autotuning" code.
*
* The algorithm for RTT estimation w/o timestamps is based on
* Dynamic Right-Sizing (DRS) by Wu Feng and Mike Fisk of LANL.
* <
*
* More detail on this code can be found at
* <
* though this reference is out of date. A new paper
* is pending.
*/
static void tcp_rcv_rtt_update(struct tcp_sock *tp, u32 sample, int win_dep)
{
u32 new_sample = tp->rcv_rtt_est.rtt;
long m = sample;
//注意，Linux内核为了避免浮点运算，RTT采样都是按8倍存储的。
//至于为什么是8倍，涉及到排队论的延时采样分析。至于为什么不用浮点数，自行google。
//所以看到">>3" "<<3"这样的源码不要感到奇怪，只是放大和缩小而已。
if (m == 0)
m = 1;
if (new_sample != 0) {
/* If we sample in larger samples in the non-timestamp
* case, we could grossly overestimate the RTT especially
* with chatty applications or bulk transfer apps which
* are stalled on filesystem I/O.
*
* Also, since we are only going for a minimum in the
* non-timestamp case, we do not smooth things out
* else with timestamps disabled convergence takes too
* long.
*/
if (!win_dep) {
m -= (new_sample >> 3);
new_sample += m;
} else {
m <<= 3;
if (m < new_sample)
new_sample = m;
}
} else {
/* No previous measure. */
new_sample = m << 3;
}
if (tp->rcv_rtt_est.rtt != new_sample)
tp->rcv_rtt_est.rtt = new_sample;
}
这才是通告窗口的取值来源，缓存要适当调节，适应发送速率的需要。把缓存通告出去，就是通告窗口了。
/*
* This function should be called every time data is copied to user space.
* It calculates the appropriate TCP receive buffer space.
*/
void tcp_rcv_space_adjust(struct sock *sk)
{
struct tcp_sock *tp = tcp_sk(sk);
int time;
int space;
if (tp->rcvq_space.time == 0)
goto new_measure;
//只有time大于一个RTT，才调节缓存。调节周期就是一个RTT
time = tcp_time_stamp - tp->rcvq_space.time;
if (time < (tp->rcv_rtt_est.rtt >> 3) || tp->rcv_rtt_est.rtt == 0)
return;
//接收缓存应该大于一个RTT内接收数据的两倍
space = 2 * (tp->copied_seq - tp->rcvq_space.seq);
space = max(tp->rcvq_space.space, space);
if (tp->rcvq_space.space != space) {
int rcvmem;
tp->rcvq_space.space = space;
if (sysctl_tcp_moderate_rcvbuf &&
!(sk->sk_userlocks & SOCK_RCVBUF_LOCK)) {
int new_clamp = space;
/* Receive space grows, normalize in order to
* take into account packet headers and sk_buff
* structure overhead.
*/
space /= tp->advmss; //这里是对space做处理，变成MSS的整数倍
if (!space)
space = 1;
rcvmem = SKB_TRUESIZE(tp->advmss + MAX_TCP_HEADER); //一个SKB的size
while (tcp_win_from_space(rcvmem) < tp->advmss)
rcvmem += 128;
space *= rcvmem;
space = min(space, sysctl_tcp_rmem[2]);
if (space > sk->sk_rcvbuf) {
sk->sk_rcvbuf = space;
/* Make the window clamp follow along. */
tp->window_clamp = new_clamp; //更新窗口增长上限
}
}
}
new_measure:
tp->rcvq_space.seq = tp->copied_seq;
tp->rcvq_space.time = tcp_time_stamp;
}
注解：
【1】糊涂窗口综合症，为了避免一字节通告窗口的奇葩现象（有效负载过低），需要对TCP做出改进。
TCPSillyWindowSyndromeandChangesTotheSlidingWindow.htm
window_syndrome
【2】数据中心网络带宽极高，10Gbps已经捉襟见肘。
【3】RTT测量方法和问题。 Zhang [Zhang86], Jain [Jain86] and Karn [Karn87]。
【4】ACK由数据包驱动，数据包由ACK驱动，TCP是一个控制闭环系统。由此可推出的结论是：接收端如果没有收到三个以上的数据包，是无法触发重复ACK，知会发送端重传的。这种情况只有等到RTO才能重传。这也就是TCP窗口尾丢包问题，简称TLP。Google和Taobao hritian都对此做了改进。
【5】准确来说，流量过小的情况，用时间戳测量都是不准的，这时候应该用第二种的方法测量。我在实验中看到RTT有突发2-3倍以上的情况，说明时间戳方法确实有缺陷。
引用：
【1】
【2】Fisk M, Feng W. Dynamic right-sizing in TCP[J]. lanl. gov/la-pubs/00796247. pdf, 2001: 2.