TCP拥塞窗口校验算法

CWV解决的问题：当主机没有数据包发送，或发送数据包量小于拥塞窗口的情况下，由于数据包个数过少，不能确保当前拥塞窗口正确反映了网络容量。

CWV算法的核心思想就是在每个RTT内递减拥塞窗口， 使得当前拥塞窗口能保守地正确反映网络拥塞情况。此外，CWV算法还使得拥塞窗口只在network-limited状态增长。

该算法中的基本概念：

1. network-limited指应用程序有足够的数据包可发送，但拥塞窗口不允许， 这种情况下拥塞窗口总能正确反映网络拥塞状态。

2. application-limited指应用程序没有足够的数据包可发送， 拥塞窗口还有很多空间可用于数据发送。这种情况下的拥塞窗口不能正确反映网络容量，因为没有足够的数据包测试网络容量。

算法第一步：

当TCP每次发送数据包时检查距上次发包时间是否超过RTO。 如果超过， 则设置ssthreshold为max(3/4*cwnd, ssthreshold)。然后超时多少倍RTO， cwnd就减半多少次， 即乘法递减策略。

snd_cwnd_stamp设置为当前时间：记录最近一次空闲后递减拥塞窗口或者处于network-limited状态的时间。

snd_cwnd_used 置0：该值记录自上次network-limited以来，处于application-limited期间的最大拥塞窗口。

注： 此处3/4倍cwnd， 是对慢启动阈值的经验估计值

tcp_transmit_skb()在调用IP层发包函数前一步调用 tcp_event_data_sent() ， 以此来设置CWV相关变量：

/* Congestion state accounting after a packet has been sent. */
static void tcp_event_data_sent(struct tcp_sock *tp,
                struct sk_buff *skb, struct sock *sk)
{
    ....
    ....
    if (sysctl_tcp_slow_start_after_idle &&
      //如果发送方自上次发包以来已经超过至少一个RTO， 则执行算法第一步
        (!tp->packets_out && (s32)(now - tp->lsndtime) > icsk->icsk_rto))
        tcp_cwnd_restart(sk, __sk_dst_get(sk));

    tp->lsndtime = now;
    ......
    ......
}

/* RFC2861. Reset CWND after idle period longer RTO to "restart window".
 * This is the first part of cwnd validation mechanism. */
static void tcp_cwnd_restart(struct sock *sk, struct dst_entry *dst)
{
    struct tcp_sock *tp = tcp_sk(sk);
    s32 delta = tcp_time_stamp - tp->lsndtime;
    u32 restart_cwnd = tcp_init_cwnd(tp, dst);
    u32 cwnd = tp->snd_cwnd;

    tcp_ca_event(sk, CA_EVENT_CWND_RESTART);
    
//设置慢启动阈值为3/4当前拥塞窗口和慢启动阈值中的最大者
    tp->snd_ssthresh = tcp_current_ssthresh(sk);
    restart_cwnd = min(restart_cwnd, cwnd);
    //超时多少RTO， cwnd就减半多少倍
    while ((delta -= inet_csk(sk)->icsk_rto) > 0 && cwnd > restart_cwnd)
        cwnd >>= 1;
    tp->snd_cwnd = max(cwnd, restart_cwnd);
    tp->snd_cwnd_stamp = tcp_time_stamp; //重置变量，以便下次计算。
    tp->snd_cwnd_used = 0;
}

算法第二步：

在发送数据包成功后， 检查当前已发送数据包个数是否大于cwnd。

如果大于则说明当前处于network-limited状态，无需确认拥塞窗口正确性。

记录当前时间，并且重置snd_cwnd_used为0， 等待以后计算拥塞窗口正确性。

如果已发送数据包个数小于cwnd， 则说明TCP处于application-limited状态。

如果当前未确认包个数大于拥塞窗口， 则保存该拥塞窗口最大值。

如果自上次记录时间起，已经超过RTO。 则说明发送发处于该拥塞窗口半满状态发包已经持续大于1倍RTO且小于2倍RTO的时间了。（因为每次发包都会走到该流程，所以最多是1倍RTO时间的半满状态，考虑RTO超时。）

tcp_write_xmit()函数在调用 tcp_transmit_skb ()函数把所有需要发送的数据包发送完成后， 会调用tcp_cwnd_validate ()来根据此次发送的数据包量， 确定TCP处于network-limited状态还是application-limited状态， 并采取相应策略。

/* Congestion window validation. (RFC2861) */
static void tcp_cwnd_validate(struct sock *sk)
{
    struct tcp_sock *tp = tcp_sk(sk);

    if (tp->packets_out >= tp->snd_cwnd) {
        /* Network is feed fully. */
//如果处于network-limited状态， 则重置变量等待以后计算。
        tp->snd_cwnd_used = 0;
        tp->snd_cwnd_stamp = tcp_time_stamp;
    } else {
        /* Network starves. */
//保存在网络饥饿期间的最大拥塞窗口, 用于测量这期间的网络容量
        if (tp->packets_out > tp->snd_cwnd_used)
            tp->snd_cwnd_used = tp->packets_out;

        if (sysctl_tcp_slow_start_after_idle &&
//如果距离上次记录cwnd_used时间超过rto，则减小拥塞窗口
            (s32)(tcp_time_stamp - tp->snd_cwnd_stamp) >= inet_csk(sk)->icsk_rto)
            tcp_cwnd_application_limited(sk);
    }
}

根据以上算法，tcp_cwnd_application_limited()函数在TCP处于cwnd半满状态发包，且持续一个RTO的情况下被调用。 此时，依旧按照3/4倍cwnd和sstreshold中的最大值设置ssthreshold，而拥塞窗口设置为当前拥塞窗口和半满状态持续一个RTO以来的发送到网络中的最大数据包个数的平均值。随后， 重置snd_cwnd_used为0，snd_cwnd_stamp为当前值。因此，直到下次RTO才会再次递减拥塞窗口， 即在application-limited的状态下， 每过RTO时间递减拥塞窗口。

void tcp_cwnd_application_limited(struct sock *sk)
{
    struct tcp_sock *tp = tcp_sk(sk);

    if (inet_csk(sk)->icsk_ca_state == TCP_CA_Open &&
        sk->sk_socket && !test_bit(SOCK_NOSPACE, &sk->sk_socket->flags)) {
        /* Limited by application or receiver window. */
        u32 init_win = tcp_init_cwnd(tp, __sk_dst_get(sk));
        u32 win_used = max(tp->snd_cwnd_used, init_win);
        if (win_used < tp->snd_cwnd) {
    //由于在application-limited阶段， 我们不会增长cwnd，只会递减。所以只有当snd_cwnd_used < cwnd的时候，才取两者均值。
            tp->snd_ssthresh = tcp_current_ssthresh(sk);
            tp->snd_cwnd = (tp->snd_cwnd + win_used) >> 1;
        }
        tp->snd_cwnd_used = 0;
    }
    tp->snd_cwnd_stamp = tcp_time_stamp;
}

慢启动阈值的算法是取当前拥塞窗口和慢启动阈值的3/4 中的最大值。见下面代码：

static inline __u32 tcp_current_ssthresh(const struct sock *sk)
{
    const struct tcp_sock *tp = tcp_sk(sk);
    if ((1 << inet_csk(sk)->icsk_ca_state) & (TCPF_CA_CWR | TCPF_CA_Recovery))
        return tp->snd_ssthresh;
    else
        return max(tp->snd_ssthresh,
               ((tp->snd_cwnd >> 1) +
                (tp->snd_cwnd >> 2)));
}

以上是CWV算法对拥塞窗口的减少，CWV算法也会使得拥塞窗口只能在network-limited状态增长。

拥塞控制算法只有在通过CWV算法检测的情况下，才会决定采用慢启动还是拥塞避免来增长拥塞窗口。

void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 in_flight)
{
    struct tcp_sock *tp = tcp_sk(sk);

    if (!tcp_is_cwnd_limited(sk, in_flight))
        return;

    /* In "safe" area, increase. */
    if (tp->snd_cwnd <= tp->snd_ssthresh)
        tcp_slow_start(tp);

    ......
}

/* RFC2861 Check whether we are limited by application or congestion window
 * This is the inverse of cwnd check in tcp_tso_should_defer
 */
int tcp_is_cwnd_limited(const struct sock *sk, u32 in_flight)
{
    const struct tcp_sock *tp = tcp_sk(sk);
    u32 left;

    if (in_flight >= tp->snd_cwnd)
        return 1;

    left = tp->snd_cwnd - in_flight;
    if (sk_can_gso(sk) &&
        left * sysctl_tcp_tso_win_divisor < tp->snd_cwnd &&
        left * tp->mss_cache < sk->sk_gso_max_size)
        return 1;
    //当已发送数据包个数远小于cwnd时，即便这次发送max_burst个数据包，也不能填满cwnd，说明当前处于application-limited状态，所以返回false，禁止cwnd增长
    return left <= tcp_max_burst(tp);
}