要約

  • 1986年10月、Lawrence Berkeley LaboratoryからUC Berkeleyへの実効スループットは32 Kbpsから40 bpsに落ちた。回線は動いていても、新しいデータではなく再送の複製が仕事を奪っていた。
  • Jacobson、Karelsらは、パケット保存則、ACKクロック、slow start、RTT変動推定、指数バックオフ、輻輳ウィンドウを4BSD TCPの送信側に実装した。
  • RFC 1122は後にslow startとcongestion avoidanceをMUSTにした。分散運用は無規則だったからではなく、攻撃的な端点が損失を他者へ押し付けることを狭い共通規則が止めたから維持できた。

近所への通信が千分の一になった

1986年10月、直線距離にすれば近所同士の二つの研究機関を結ぶ経路で異常が起きた。Van JacobsonとMichael J. Karelsの論文によれば、Lawrence Berkeley Laboratoryとカリフォルニア大学バークレー校は約400ヤード、二つのIMPホップを隔てていた。その経路のデータスループットが32キロビット毎秒から40ビット毎秒まで落ちた。

単なる混雑なら、全員が遅くても前へ進む。輻輳崩壊では、ネットワークは忙しいのに新しいデータをほとんど届けない。負荷が高いと往復時間は大きく揺れる。古い再送タイマーは遅延中のパケットを損失と誤認し、同じデータを満杯のキューへ再投入した。遅延と損失が増え、さらに再送が増える。回復処理そのものが正のフィードバックになった。

John Nagleは1984年のRFC 896でこの現象を「congestion collapse」と呼んでいた。速度の異なるリンクをつなぐデータグラム網が、複製で容量を浪費する安定状態に陥り得ることを説明した文書である。ただし提案は議論を促すためのもので、完成した標準ではなかった。1986年の実障害は、診断を実装上の緊急課題へ変えた。

受信者の余裕と経路の余裕は違う

従来の受信ウィンドウは、宛先のバッファをあふれさせないためにあった。宛先に空きがあっても、途中のゲートウェイと低速リンクに同じ余裕があるとは限らない。高速Ethernetのホストが、56 Kbpsの長距離経路へ受信ウィンドウ分を一気に送り出せば、入口のキューが耐えられない。

そこで送信側に別の上限、輻輳ウィンドウが置かれた。実際の送信量は受信ウィンドウとの小さい方で決まる。タイムアウトが輻輳を示せばウィンドウを乗法的に減らし、新しいACKが戻れば加法的に増やす。端点は経路を所有しなくても、その反応から送信量を調整できた。

根底にあるのはパケット保存則である。平衡状態では、古いパケットが一つネットワークを出るまで新しい一つを入れない。ACKは退出の証拠であり、ボトルネックから戻る時計でもある。受信側はデータがボトルネックを通過した以上の速さでACKを作れないため、その間隔が送信側のペースを整える。

開始直後の接続にはまだ時計がない。slow startは小さなウィンドウから始め、ACKの到着に応じて急速に開く。名前に反して往復ごとの成長は指数的だが、未知の経路へ最初から全量を投げ込まない点が重要だった。RTTの平均だけでなく変動も見積もり、失敗が続けば再送間隔を指数的に延ばす変更も、同じ保存則を支えた。

実装が標準を先導した

1988年論文は、4BSD TCPに入れた変更を七つ挙げる。slow startと動的ウィンドウ以外にも、受信ACK方針、fast retransmit、Phil Karnの手法が含まれる。slow startという名称はNagleに、ウィンドウ方針の発想はRaj Jainに由来すると記す。したがって、これは一人の天才が単独で救った物語ではない。複数の着想がコードと測定で一つの制御系になった歴史である。

四フローの試験では、輻輳回避なしの場合、送信11,000パケット中4,000が再送だった。25 KB/sのリンクで有効帯域が失われた。輻輳回避ありでは8,281パケット中の再送は89、約1%に減り、リンク容量が有用な通信として説明できた。

先に4BSDで動き、負荷試験と利用者の報告が積み上がった。1989年10月のRFC 1122はその後で、RFC 793のタイムアウト計算を不十分とし、slow startとcongestion avoidanceの組合せをTCPのMUSTにした。連続する再送タイムアウトの指数バックオフも必須になった。手続きが実態を作ったのではなく、動く修正が共通義務の根拠になった。

自由には共有キューの請求書が付く

MUSTは任意の助言ではない。ここでの分散性は、各端点が好きなだけ送る権利を意味しなかった。輻輳に応答しない送信側は共通キューを占有し、応答するフローに遅延と損失を負わせる。短期には「速いTCP」に見えても、他者が費用を払っているだけである。

RFC 2914は後に、より攻撃的な実装や多数の並列接続が競争になる危険を述べた。全員が追随すれば、優位は消え、慢性的輻輳だけが残る。狭い要件は広い選択を守った。OS、アプリケーション、経路、具体的アルゴリズムは多様でよい。しかし共有障害を再生産する行動まで相互運用の自由とは呼べない。

端点だけでは公平を決められない

著者らは限界も明記した。端点制御は容量超過を防げても、公平な配分までは保証しない。複数フローが合流する情報を持つのはゲートウェイであり、そこに別の制御面が必要になる。後のAQM、ECN、多様な輻輳制御はその余白を発展させた。

損失が常に輻輳を意味するわけでもない。1988年方式を永遠の完成形と扱うべきではない。その価値は、共有故障の原因を狭く定め、最小の有効箇所を変え、実測で確かめ、必要部分だけを共通化したことにある。

情報源と証拠の限界

中心資料はCongestion Avoidance and ControlとLBNL NRG論文索引である。標準化の流れはRFC 896、RFC 1072、RFC 1122、RFC 2001、RFC 2914、RFC 5681で確認した。当時の議論はLBNLメール索引に残る。

32 Kbpsから40 bpsという数字は一つの観測経路を示す。インターネット全体が同時停止したとの意味ではなく、功績を一人に限定する根拠にもならない。