TCP-Reno混雑アルゴリズム

古典的なRenoアルゴリズムは以下のように3つの混雑関数を実現した.

struct tcp_congestion_ops tcp_reno = {
    .flags      = TCP_CONG_NON_RESTRICTED,
    .name       = "reno",
    .owner      = THIS_MODULE,
    .ssthresh   = tcp_reno_ssthresh,
    .cong_avoid = tcp_reno_cong_avoid,
    .undo_cwnd  = tcp_reno_undo_cwnd,
};

TCPソケットはTCP_に入るCA_CWR/Recovery/LOss混雑状態の場合、tcp_が実行されますcongestion_ops混雑構造のメンバー関数ssthreshは、遅い起動しきい値を更新します.以下に示すように、混雑したウィンドウを半分にしますが、2以下ではありません.

/* Slow start threshold is half the congestion window (min 2) */
u32 tcp_reno_ssthresh(struct sock *sk)
{
    const struct tcp_sock *tp = tcp_sk(sk);

    return max(tp->snd_cwnd >> 1U, 2U);
}

ACK確認メッセージの受信時にcong_を呼び出すAVoidポインタ関数、すなわちtcp_reno_cong_avoid.現在の混雑したウィンドウが十分に使用されている場合は、処理しません.TCPソケットが遅い起動段階にある場合、関数tcp_slow_startは混雑回避フェーズのウィンドウ処理、すなわち関数tcp_cong_avoid_ai.

/* This is Jacobson's slow start and congestion avoidance. SIGCOMM '88, p. 328.
 */
void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 acked)
{
    struct tcp_sock *tp = tcp_sk(sk);

    if (!tcp_is_cwnd_limited(sk))
        return;

    /* In "safe" area, increase. */
    if (tcp_in_slow_start(tp)) {
        acked = tcp_slow_start(tp, acked);
        if (!acked)
            return;
    }
    /* In dangerous area, increase slowly. */
    tcp_cong_avoid_ai(tp, tp->snd_cwnd, acked);
}

スロースタートフェーズでは、新しい混雑ウィンドウは、元のウィンドウにACK確認を加えたメッセージ数に等しいが、結果値がスロースタート閾値ssthreshを超えた場合、超過部分はウィンドウ増加操作を実行せず、混雑回避フェーズアルゴリズム処理に渡される.

/* Slow start is used when congestion window is no greater than the slow start
 * threshold. We base on RFC2581 and also handle stretch ACKs properly.
 * We do not implement RFC3465 Appropriate Byte Counting (ABC) per se but
 * something better;) a packet is only considered (s)acked in its entirety to
 * defend the ACK attacks described in the RFC. Slow start processes a stretch
 * ACK of degree N as if N acks of degree 1 are received back to back except
 * ABC caps N to 2. Slow start exits when cwnd grows over ssthresh and
 * returns the leftover acks to adjust cwnd in congestion avoidance mode.
 */
u32 tcp_slow_start(struct tcp_sock *tp, u32 acked)
{
    u32 cwnd = min(tp->snd_cwnd + acked, tp->snd_ssthresh);

    acked -= cwnd - tp->snd_cwnd;
    tp->snd_cwnd = min(cwnd, tp->snd_cwnd_clamp);

    return acked;
}

混雑回避フェーズにおいて、混雑カウントsnd_cwnd_cntは現在のウィンドウより大きく、カウントをクリアし、現在の混雑しているウィンドウを1つ追加します(snd_cwnd).逆に、混雑カウントsnd_cwnd_cntは現在のウィンドウより小さく、カウントをacked増加し、増加するとカウントが現在のウィンドウw以上になると、新しい混雑ウィンドウ(snd_cwnd)増加値はカウントを現在のウィンドウの整数値で除算し、残りはウィンドウカウント変数(snd_cwnd_cnt)に保存される.混雑回避フェーズでは、各ACKメッセージについて、ウィンドウの増加は次の式に従います.
c w n d + = 1 c w n d cwnd +=\frac{1}{cwnd} cwnd+=cwnd1​

/* In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd (or alternative w),
 * for every packet that was ACKed.
 */
void tcp_cong_avoid_ai(struct tcp_sock *tp, u32 w, u32 acked)
{
    /* If credits accumulated at a higher w, apply them gently now. */
    if (tp->snd_cwnd_cnt >= w) {
        tp->snd_cwnd_cnt = 0;
        tp->snd_cwnd++;
    }

    tp->snd_cwnd_cnt += acked;
    if (tp->snd_cwnd_cnt >= w) {
        u32 delta = tp->snd_cwnd_cnt / w;

        tp->snd_cwnd_cnt -= delta * w;
        tp->snd_cwnd += delta;
    }
    tp->snd_cwnd = min(tp->snd_cwnd, tp->snd_cwnd_clamp);
}

Reno処理混雑取り消しの関数tcp_reno_undo_cwndは、現在の混雑ウィンドウと混雑発生前のウィンドウの両方の最大値を返します.

u32 tcp_reno_undo_cwnd(struct sock *sk)
{
    const struct tcp_sock *tp = tcp_sk(sk);

    return max(tp->snd_cwnd, tp->prior_cwnd);
}

カーネルバージョン5.0