KCP源码解析系列（五）拥塞控制

流量控制和拥塞控制的区别

如果你约了你的朋友见面聊一件事，有两种沟通方式：

• 第一种是一次只说一句话，然后等待你的朋友回应“收到”，确认他在听之后，再说下一句话，如此反复，直到事情说完。
• 第二种是一次性把所有话说完，然后再等朋友点头确认他都听到了。
  理想情况下，第二种方式是最好的，因为这样来回沟通的次数较少。然而，在实际过程中，还需要考虑以下几个因素：
• 对方的理解能力。一次说太多，可能对方无法完全理解和接收。
• 聊天环境。如果环境较为嘈杂，比如在KTV里，那么一次性说太多可能会导致对方听不清，从而产生困惑和尴尬。
  第一个因素涉及到流量控制（Flow Control），主要考虑接收方的信息处理能力。第二个因素涉及到拥塞控制（Congestion Control），主要考虑网络或沟通环境能承受的信息量。

拥塞控制的方式

1. 慢开始（Slow-start）、拥塞避免（Congestion Avoidance）

2. 快重传（Fast Restrangsmit）、快恢复（Fast Recovery）

下图可以表示整个拥塞控制的流程，但这是TCP的，KCP原理一样，但增速有差异。这个图初一看很复杂，但理解起来很简单。

拥塞控制的思路

1. 当主机开始发送数据时，如果立即将较大的发送窗口的全部数据字节都注入到网络中，那么由于不清楚网络的情况，有可能引其网络拥塞

2. 比较好的方法是试探一下，即从小到大逐渐增大发送端的拥塞控制窗口数值。这就叫慢开始。虽然开始的慢，但增速快。通常在刚刚开始发送报文段时可先将拥塞窗口cwnd设置为一个最大报文段的MSS的数值。在每收到一个对新报文段确认后，将拥塞窗口增加一个MSS的数值。

3. 需要设定一个ssthresh，传输门限值，这是一个动态调整的阈值，根据cwnd和ssthresh的比较，采用不同的策略。

1）当cwnd < ssthresh时，使用慢开始算法

2）当cwnd > ssthresh时，停止使用慢开始算法而改用拥塞避免算法

3）当cwnd = ssthresh时 即可以使用慢开始算法，也可以使用拥塞避免算法。

4. 随着cwnd逐步的增大，发送速度也可能会逐步增大，网络就可能发生拥塞，具体就是发生丢包。此时就会触发快重传。快重传很简单，就是比如你发送了1，2，3，4，5这几个包，然后收到了1，3，4，5的ack，2被连续跳过了三次，就直接把2重新发一次。

5. 当发生快重传时，说明网络环境不太好，这是可以快速降低ssthresh，避免网络进一步发生堵塞，这个就叫快恢复。

KCP源码中的拥塞控制

慢开始和拥塞避免

 //当发送窗口的snd_una右移，说明可以更新拥塞窗口了
    if (_itimediff(kcp->snd_una, prev_una) > 0) {
        // 如果拥塞窗口小于远端窗口，表示还有发送空间
        if (kcp->cwnd < kcp->rmt_wnd) {
            
            IUINT32 mss = kcp->mss;
            // 慢开始的处理
            if (kcp->cwnd < kcp->ssthresh) {
                kcp->cwnd++;
                kcp->incr += mss;// 拥塞窗口增加量加上一个 MSS，增速较快。
            } else {// 拥塞避免阶段
                // 保证 incr 不小于 MSS
                if (kcp->incr < mss) {
                    kcp->incr = mss;
                }
                //这里的 /kcp->incr 表示增量会随着incr的增长而放缓， + (mss / 16)这部分是一个调节增加量，避免增长过于缓慢。
                kcp->incr += (mss * mss) / kcp->incr + (mss / 16);
                //这部分代码是为了更新cwnd
                if ((kcp->cwnd + 1) * mss <= kcp->incr) {
#if 1
                    kcp->cwnd = (kcp->incr + mss - 1) / ((mss > 0) ? mss : 1);
#else
                    kcp->cwnd++;
#endif
                }
            }
            //拥塞窗口>远端窗口，以远端窗口为准
            if (kcp->cwnd > kcp->rmt_wnd) {
                kcp->cwnd = kcp->rmt_wnd;
                kcp->incr = kcp->rmt_wnd * mss;
            }
        }

快重传

kcp协议在接收ACK时，会更新segments的fastack计数，如果达到阈值就立即重传

// 更新快速重传计数 fastack,sn为当前收到的包的
void ikcp_parse_fastack(ikcpcb *kcp, IUINT32 sn, IUINT32 ts) {
    struct IQUEUEHEAD *p, *next;

    // 如果 sn 在发送队列的范围之外，则不进行处理
    if (_itimediff(sn, kcp->snd_una) < 0 || _itimediff(sn, kcp->snd_nxt) >= 0)
        return;

    // 遍历发送缓冲区，根据传入的 sn 更新各 segment 的 fastack 计数
    for (p = kcp->snd_buf.next; p != &kcp->snd_buf; p = next) {
        IKCPSEG *seg = iqueue_entry(p, IKCPSEG, node);
        next = p->next;

        // 如果sn小于seg->sn，跳出循环，后面的seg->sn只会更大
        if (_itimediff(sn, seg->sn) < 0) {
            break;    
        }
        // 如果sn大于seg->sn，则增加其 fastack 计数
        else if (sn != seg->sn) {
            seg->fastack++;
        }
    }
}

在每次调用 ikcp_flush 函数时，会检测 segments 的 fastack 是否超过阈值 fastresend，如果超过，则立即进行重传：

void ikcp_flush(ikcpcb *kcp) {
    struct IQUEUEHEAD *p;
    //遍历发送缓冲区
    for (p = kcp->snd_buf.next; p != &kcp->snd_buf; p = p->next) {
        IKCPSEG *segment = iqueue_entry(p, IKCPSEG, node);
        int needsend = 0;
        //判断是否达到快速重传的条件
        if (segment->fastack >= kcp->fastresend) {
           // segment->xmit未超过最大传输次数或者未设置传输限制
            if ((int)segment->xmit <= kcp->fastlimit || kcp->fastlimit <= 0) {
                needsend = 1;
                segment->xmit++;
                segment->fastack = 0;
                segment->resendts = current + segment->rto;
                change++;
            }
        }
        //如果需要重传
        if (needsend) {
            segment->ts = current;
            segment->wnd = seg.wnd;
            segment->una = kcp->rcv_nxt;
            size = (int)(ptr - buffer);
            need = IKCP_OVERHEAD + segment->len;
             // 判断当前缓冲区大小是否超过最大传输单元 (MTU)，如果超过则先发送现有数据
            if (size + need > (int)kcp->mtu) {
                // 发送现有数据
                ikcp_output(kcp, buffer, size);
                // 重置缓冲区指针
                ptr = buffer;
            }
            ptr = ikcp_encode_seg(ptr, segment);
            if (segment->len > 0) {
                memcpy(ptr, segment->data, segment->len);
                ptr += segment->len;
            }
            // 检查传输次数是否超过死链接限制 (dead_link)
            if (segment->xmit >= kcp->dead_link) {
                // 标记连接状态为死链接
                kcp->state = -1;
            }
        }
    }
    // 其他处理...
}d

快速恢复

//change：快速重传的情况说明网络存在短时压力，但没有明显的丢包情况，采用温和策略（增量减半）以快速恢复，始终保持一定传输速率。
//lost：数据包明确丢失表明网络拥塞加剧，需要大幅度减少传输量（cwnd 设为 1）消除拥塞压力。这种情况下，确保数据继续传输但速率极低，避免进一步拥堵。

//是否触发了快重传
if (change) {
    //占用的窗口大小
    IUINT32 inflight = kcp->snd_nxt - kcp->snd_una;
    //慢启动阈值减半
    kcp->ssthresh = inflight / 2;
    if (kcp->ssthresh < IKCP_THRESH_MIN) kcp->ssthresh = IKCP_THRESH_MIN;
    //重设cwnd
    kcp->cwnd = kcp->ssthresh + kcp->fastresend;
    kcp->incr = kcp->cwnd * kcp->mss;
}
//是否触发了丢失
if (lost) {
  // 将 ssthresh 初始值为当前 cwnd 一半，确保下一次启动控制合理。
    kcp->ssthresh = kcp->cwnd / 2;
    if (kcp->ssthresh < IKCP_THRESH_MIN) kcp->ssthresh = IKCP_THRESH_MIN;
   // 设置拥塞窗口 cwnd 为 1
    kcp->cwnd = 1;
    kcp->incr = kcp->mss;
}

if (kcp->cwnd < 1) {
    kcp->cwnd = 1;
    kcp->incr = kcp->mss;
}