TCP 輻輳制御

TCP の送信側は経路の容量を直接見られません。フィードバックから送信量を調整します。この教材は教科書型 Reno です。1 パケットから始め、スロースタートで RTT ごとに倍増し、しきい値以降は 1 ずつ増やし、損失時に減らします。ウィンドウは一定値に落ち着かず、のこぎり歯状になります。

経路は RTT ごとに 8 パケットを排出し、バッファーは 4 パケットを保持します。送信側が持つのは cwnd（送信中にできる MSS 数）と ssthresh（スロースタートのしきい値）です。3 重複 ACK は後続データが届いていることを示すため、本例では半減後も輻輳回避を続けます。タイムアウトの設定では ACK が戻らず、cwnd を 1 にしてスロースタートを再開します。

TCP 輻輳制御の仕組み

損失のない各 RTT の後で cwnd < ssthresh を調べます。

成立すればスロースタートで cwnd = min(cwnd * 2, ssthresh)。実 TCP は ACK ごとに更新します。ウィンドウを使い切り、各パケットが個別に確認される条件では、およそ RTT ごとに倍になります。遅延 ACK やバイト数による計算は成長率に影響します。本例は 1 往復の確認をまとめ、しきい値で増加を止めます。

しきい値に達すると輻輳回避へ移り、cwnd += 1。RTT ごとに 1 MSS の線形成長です。

cwnd > C + B であふれます。C は RTT ごとの排出数で、この固定 1 RTT 経路では帯域遅延積にも相当します。B はバッファー容量です。C を超えた分が待ち行列へ入り、C + B を超えた分を落とします。送信側は C を読みません。このモデルは容量計算と損失通知を分けており、同じ送信群の末尾損失から 3 重複 ACK を導出するものではありません。

• 3 重複 ACK による高速再送。 ssthresh = max(cwnd // 2, 2)、cwnd = ssthresh として輻輳回避を続けます。実 Reno の高速リカバリーが一時的に使う ssthresh + 3 は省略します。
• タイムアウト。 必要な ACK の到着前に再送タイマーが切れます。しきい値は失われた送信群の窓から max(cwnd // 2, 2) とし、cwnd = 1 でスロースタートへ戻ります。このプリセットは送信群への応答がない状態を使います。

AIMD は加算的増加（RTT ごとに +1）と乗算的減少（× ½）です。1 だけ減らすと満杯に近い状態が続き、増加後にまたあふれます。半減すると次の探索の余地が生まれます。

TCP 輻輳制御のステップ

初期設定の Sawtooth は C = 8 パケット/RTT、B = 4、cwnd = 1、ssthresh = 8。容量を超えたときに損失が起きます。

1. 初期化。 パイプは空で、点は (RTT 0, cwnd 1)。ssthresh = 8 は送信側の状態、C = 8 は送信側から見えない値です。一致はこの設定の選択であり、同じ変数ではありません。
2. スロースタート。 1 を送り 1 を確認、cwnd 1 → 2。
3. スロースタート。 2 を送り確認、2 → 4。
4. スロースタート。 4 を送り確認、4 → 8。しきい値で止まります。
5. しきい値到達。 増加規則を ×2 から +1 へ変更。このステップではパケットは動きません。
6. 輻輳回避。 8 を送り確認。待ち行列 0、8 → 9。
7. 輻輳回避。 9 を送り、待ち行列 1、9 → 10。
8. 輻輳回避。 10 を送り、待ち行列 2、10 → 11。
9. 輻輳回避。 11 を送り、待ち行列 3、11 → 12。
10. 輻輳回避。 12 を送り、待ち行列 4/4、12 → 13。次の送信群は収まりません。
11. あふれる。 13 のうち 12 が収まり、1 が損失。3 重複 ACK を表示します。縮小は次のステップなので cwnd はまだ 13 です。
12. 半減。 ssthresh = max(13 // 2, 2) = 6、cwnd = 6。輻輳回避のまま点が垂直に下がり、しきい値線も 8 から 6 へ移ります。
13. 輻輳回避。 6 を送り、6 → 7。倍増ではありません。高速リカバリーの一時的な +3 を省いた動きです。
14. 輻輳回避。 7 を送り、7 → 8。
15. 輻輳回避。 8 を送り、8 → 9。帯域遅延積を再び通過します。
16. 次の歯。 9 → 10 → 11 → 12 → 13、損失、6 への下降を 1 ステップで描きます。
17. 完了。 cwnd = 6、ssthresh = 6。スロースタートの上昇と輻輳回避の歯が 2 個残ります。正確な容量を決めて終わるのではなく、増加、損失、半減を続けます。

No loss は B = 16 に変えます。cwnd = 14 まで損失なく増え、縮小せずに再生を終えます。

Timeout は 13 の送信群への ACK を返しません。RTO が発火して cwnd = 1。その後 1 → 2 → 4 → 6 と増やし、新しいしきい値で止め、輻輳回避へ移ります。同じ過負荷でも通知方法で減少幅が変わります。

パイプはその RTT の損失理由、グラフは各 RTT のウィンドウ履歴です。指数成長、線形成長、下降を、それぞれの更新規則と結び付けてください。

のこぎり歯になる理由

理想化した固定経路で C が分かれば、送信中の量を C にできます。しかし送信側にはその情報がありません。スロースタートで N のウィンドウに達するには Θ(log N) RTT。1, 2, 4, 8 は 4 回の送信ウィンドウです。輻輳回避は RTT ごとに 1 MSS なので、さらに N パケット増やすには Θ(N) RTT かかります。

損失後の半減は待ち行列に余裕を作ります。13 から 12 にしか減らさなければ 4/4 のままで、12 の送信成功後に 13 へ増え、再びあふれます。初期設定で歯を 2 回描くのは、同じ条件から同じ動作が繰り返されることを示すためです。

プリセットは次の特徴を示します。

• 線形成長後に半減：Reno 型の損失探索。3 重複 ACK が典型的な契機です。
• 1 へ落ちて再びスロースタート：タイムアウトや確認の遅れ。
• 待ち行列が増えてもまだ下がらない：バッファーが過負荷を吸収し、バッファーブロートによる遅延が生じ得る状態。

Cubic や BBR は別の曲線になります。ここでは Reno だけを扱います。

境界条件

• 初期しきい値は教材の設定。 実装では大きい値から始め、最初の輻輳でスロースタートを終える場合があります。本例は最初の損失前に両方の成長規則を見せるため 8 にしています。
• しきい値の下限は 2。 max(cwnd // 2, 2) は整数の半減でゼロになることを防ぎます。
• しきい値にちょうど着地。 しきい値 8 なら 4 → 8、タイムアウト後の 6 なら 4 → 6 で輻輳回避へ移ります。
• タイムアウトと重複 ACK は異なる。 同じ 13 の過負荷から、本例は前者で 1、後者で 6 にします。
• 損失なしでは縮小しない。 このモデルは増加を続けますが、有限のバッファーは成長が続けばいずれあふれます。長い待ち行列は無限の容量ではありません。

よくある間違い

• スロースタートは必ず最初の損失まで続くと思う。 初期しきい値が大きいときの挙動です。判定は cwnd < ssthresh。本例は 8 で切り替わり、13 で損失が起きます。
• 3 重複 ACK 後に倍増する。 この Reno モデルは半分を残して輻輳回避を続けます。小さなウィンドウからスロースタートへ戻る方式とは異なります。
• ACK 番号の増加を輻輳制御と読む。 ハンドシェイクの ack = seq + 1 は番号の確認。cwnd は送信中のデータ量の上限です。
• すべての損失をタイムアウトと呼ぶ。 重複 ACK は受信側が後続データを見ていることを示し、Reno は半分を残します。
• 単一フローの歯から無条件の公平性を導く。 AIMD の公平性は共有モデルや RTT などの条件に依存します。Chiu–Jain の図が扱う問題であり、本例は 1 フローです。
• 容量 C を発見して終わったと思う。 送信側は範囲を探索し続け、次の増加でもあふれます。

省略した内容

これは 1 フローを RTT ごとにまとめた Reno です。実 TCP は ACK ごとに更新し、初期ウィンドウは 1 より大きいことが多く、例えば 10 MSS です。高速リカバリーでは一時的に cwnd = ssthresh + 3 とします。損失時のしきい値は FlightSize から求め、送信量は受信ウィンドウにも制約されます。本例はウィンドウ全体を送る想定で cwnd を使います。Cubic、BBR、pacing、遅延 ACK、SACK、複数フローの公平性は省略しています。成長と後退の規則を示すモデルであり、完全な TCP 実装ではありません。