前篇

关于 TCP 拥塞的控制算法,入门知识可以从 《TCP拥塞控制算法BBR的原理和改进实践》开始过一遍

Brutal 算法的核心代码剖析

static void brutal_update_rate(struct sock *sk)
{
    struct tcp_sock *tp = tcp_sk(sk);
    struct brutal *brutal = inet_csk_ca(sk);

    u64 sec = tcp_sock_get_sec(tp);
    u64 min_sec = sec - PKT_INFO_SLOTS;
    u32 acked = 0, losses = 0;
    u32 ack_rate; // Scaled by 100 (100=1.00) as kernel doesn't support float
    u64 rate = brutal->rate;
    u32 cwnd;

    u32 mss = tp->mss_cache;
    u32 rtt_ms = (tp->srtt_us >> 3) / USEC_PER_MSEC;
    if (!rtt_ms)
        rtt_ms = 1;

    for (int i = 0; i < PKT_INFO_SLOTS; i++)
    {
        if (brutal->slots[i].sec >= min_sec)
        {
            acked += brutal->slots[i].acked;
            losses += brutal->slots[i].losses;
        }
    }
    if (acked + losses < MIN_PKT_INFO_SAMPLES)
        ack_rate = 100;
    else
    {
        ack_rate = acked * 100 / (acked + losses);
        if (ack_rate < MIN_ACK_RATE_PERCENT)
            ack_rate = MIN_ACK_RATE_PERCENT;
    }

    rate *= 100;
    rate /= ack_rate;

    // The order here is chosen carefully to avoid overflow as much as possible
    cwnd = rate / MSEC_PER_SEC;
    cwnd *= rtt_ms;
    cwnd /= mss;
    cwnd *= brutal->cwnd_gain;
    cwnd /= 10;
    cwnd = max_t(u32, cwnd, MIN_CWND);

    brutal_tcp_snd_cwnd_set(tp, min(cwnd, tp->snd_cwnd_clamp));

    WRITE_ONCE(sk->sk_pacing_rate, min_t(u64, rate, READ_ONCE(sk->sk_max_pacing_rate)));
}

剖析

  1. 从 struct tcp_sock 检索当前时间戳,转换成秒

  2. 计算出一个最小的时间戳,该时间戳是当前时间戳减去一个固定大小的窗口(PKT_INFO_SLOTS)。这个窗口用来限定考虑的数据包信息的时间范围

  3. 遍历存储数据包信息的数组 brutal->slots,累加在时间窗口内的确认(acked)和丢失(losses)的数据包数量

  4. 如果在时间窗口内的样本数量小于定义的最小样本数量 MIN_PKT_INFO_SAMPLES,则将确认率 ack_rate 设为 100%,表示没有丢包

  5. 如果样本数量足够,则计算确认率 ack_rate,即在考虑的时间窗口内被确认的数据包与总数据包的比例,并乘以 100 转换为百分比格式

  6. 如果确认率低于定义的最小确认率 MIN_ACK_RATE_PERCENT,则使用这个最小值

  7. 然后根据确认率调整发送速率 rate。这里使用了一些数学操作来避免使用浮点数,因为内核通常不使用浮点运算

  8. 接下来,根据新的发送速率、往返时间(RTT),以及最大分段大小(MSS)计算新的拥塞窗口大小 cwnd

  9. 拥塞窗口大小还乘以了窗口增益 cwnd_gain(调整因子),然后除以10(因为增益是以十分之一为单位)

  10. 拥塞窗口大小被限制在一个最小值 MIN_CWND 和 tp->snd_cwnd_clamp(拥塞窗口的最大允许值)之间

  11. 使用 brutal_tcp_snd_cwnd_set 更新 tcp_sock 结构体中的 snd_cwnd 拥塞窗口大小

  12. 最后,更新套接字的发送速率 sk_pacing_rate,这也被限制在 sk_max_pacing_rate(最大发送速率)以下

其实我们能明显看出来,TCP 拥塞算法的核心思想,就是根据当前的网络拥塞情况(在这里依赖于判断丢包率)来计算 cwnd,这个显著指标作为核心值会判定直接影响到发送速率和数据包重传策略的决策,这种 AIMD 原则会在网络状况良好时逐渐增加发送窗口,以增大吞吐量,而在检测到网络拥塞(如丢包事件)时则大幅减小窗口大小,以减轻网络负担,理论上来说遵循这种原则的算法都可以算是一种 “君子算法”,但是 Brutal 算法不是的,在他们的文档中就说明了这一点:

其实这里等比级数和公式中 $$ s = \frac{a}{1-r} $$ 1 / (1 - r) 是弥补丢包的固有损耗比,标称 rate 乘以损耗比就是保住带宽所需要的实际发送速率: $$ \text{rate} = \text{rate} \times \frac{1}{1 - r} $$ 最终 cwnd 就是根据这个算出来的 (发送速率 * 乘以往返时间 * 再乘以增益) $$ \text{cwnd} = \text{rate} \times \text{RTT} \times \text{gain} $$

注意这里,过大的增益会明显放大计算出的拥塞窗口大小,这意味着算法将更加积极地增加 cwnd,从而允许更多的数据在确认之前发送,这可以在网络状况良好时提高吞吐量,副作用则是可能会导致过大的 cwnd 在网络中的路由器和交换机的缓冲区中积累更多的数据包,从而增加排队延迟,引起缓冲膨胀(Bufferbloat)现象。

由于 Bufferbloat 现象,我个人其实不是很推荐使用 Brutal 算法进行游戏加速,因为过大的缓冲区可能导致数据包处理时间的波动,这在对于实时性要求更高的场景中不会特别欢迎,此外 Bufferbloat 会掩盖网络拥塞问题,使得 TCP 拥塞控制算法难以及时检测到拥塞情况,因为数据包并没有实际被丢弃,只是延迟了传输。

拥塞测试

光说不练假把式,Brutal 算法其实设置了一定的使用门槛,即必须以加载库的形式调用,无法直接作为系统默认的拥塞控制算法,这样可以避免一定程度上的泛滥。

我们先写一段正常 TCP 持续下载一个二进制文件的函数,期间一直输出连接信息,以让我们知道默认的情况下,正常的不做限制的 TCP 拥塞是怎么控制的

std::vector<char> data;
    char buffer[BUFFER_SIZE];
    ssize_t bytes_received;
    unsigned long total_bytes = 0;

    auto start = std::chrono::steady_clock::now();
    std::chrono::steady_clock::time_point last_time = start;

    while ((bytes_received = recv(sock, buffer, BUFFER_SIZE, 0)) > 0) {
        data.insert(data.end(),buffer,buffer + bytes_received);
        total_bytes += bytes_received;

        // Calculate download speed every second
        auto current_time = std::chrono::steady_clock::now();
        auto time_diff = std::chrono::duration_cast<std::chrono::seconds>(current_time - start);
        if (time_diff.count() > 1) {
            struct tcp_info tcpi{};
            socklen_t len = sizeof(tcpi);
            getsockopt(sock, SOL_TCP,TCP_INFO,&tcpi,&len);

            double speed = static_cast<double>(total_bytes) / static_cast<double>(time_diff.count());
            std::cout << "Download speed: " << (speed / 1024) << " KB/sec, "
                      << "cwnd: " << tcpi.tcpi_snd_cwnd << ", "
                      << "lost packets: " << tcpi.tcpi_lost << ", "
                      << "retransmitted packets: " << tcpi.tcpi_retrans << ", "
                      << "RTO: " << tcpi.tcpi_rto << " μs" << std::endl;
            total_bytes = 0;
            start = std::chrono::steady_clock::now();
        }
    }

    if (bytes_received < 0) {
        perror("recv failed");
        close(sock);
        return 1;
    }

这是运行的输出,可以看出 cwnd 默认情况下为 10,这也和 ss 抓取的差不多

Download speed: 239.766 KB/sec, cwnd: 10, lost packets: 0, retransmitted packets: 0, RTO: 3040000 μs
Download speed: 205.312 KB/sec, cwnd: 10, lost packets: 0, retransmitted packets: 0, RTO: 3040000 μs
Download speed: 147.062 KB/sec, cwnd: 10, lost packets: 0, retransmitted packets: 0, RTO: 3040000 μs
Download speed: 195.469 KB/sec, cwnd: 10, lost packets: 0, retransmitted packets: 0, RTO: 3040000 μs
Download speed: 57.6562 KB/sec, cwnd: 10, lost packets: 0, retransmitted packets: 0, RTO: 3040000 μs
Download speed: 173.672 KB/sec, cwnd: 10, lost packets: 0, retransmitted packets: 0, RTO: 3040000 μs
Download speed: 98.3281 KB/sec, cwnd: 10, lost packets: 0, retransmitted packets: 0, RTO: 3040000 μs

# 下面这段是使用 ss 从服务端抓取的,注意不是同一个连接,而只是一个示例而已,代表了一个普通连接

cubic wscale:8,9 rto:220 rtt:17.325/1.964 ato:40 mss:1412 pmtu:1500 rcvmss:1412 advmss:1460 cwnd:10 ssthresh:7 bytes_sent:3388 bytes_acked:3388 bytes_received:5764 segs_out:25 segs_in:21 data_segs_out:7 data_segs_in:16 send 6.5Mbps lastsnd:24480 lastrcv:24464 lastack:9400 pacing_rate 7.8Mbps delivery_rate 722.9Kbps delivered:8 app_limited busy:120ms reordering:60 rcv_space:14600 rcv_ssthresh:64076 minrtt:15.626