1986年10月、初期のインターネットは最初の輻輳崩壊に見舞われた。400ヤード離れたローレンス・バークレー研究所からUCバークレーへのスループットは、32 Kbpsから40 bpsにまで低下した。ホストは失われたパケットを全速力で再送し、ネットワークをさらに氾濫させていた。

Van Jacobsonの1988年の論文「Congestion Avoidance and Control」は、その仕組みを説明し、修正策を処方した。送信側は、損失がないときはラウンドトリップごとにウィンドウを1パケットずつ増やし、パケットが失われたときはそれを半分にすべきであるという、加算増加・乗算減少の方針である。

すべてのTCP送信側が同じアルゴリズムに従うため、ネットワークは中央制御装置なしで安定した、ほぼ公平な均衡に達する。この考え方はTCPに採用され、後にスロースタート、高速再送、高速リカバリとともにRFC 5681で成文化された。

損失を検知したら速度を半分にし、その後ゆっくりと再び上げていく

損失はすべての送信側がすでに受け取っている輻輳の信号であるため、追加のネットワーク機構は必要ない。

乗算減少は問題に素早く反応し、加算増加は容量をゆっくりと探る。

この規則を共有するすべての送信側がいることで、公平性は個々の行動から自然に生まれる。

ルーターを変更したり帯域幅を追加したりすることなく、この障害を修正した。

すべての主体の合理的な対応が共有資源を悪化させる場合には、全員が従う規則を変える。安全な行動はゆっくりと拡大し、有害な行動は急激に縮小するようにする。

このアルゴリズムは、インターネットトラフィックの大部分を運ぶトランスポートプロトコルであるTCPの既定の動作となった。2009年に公開されたRFC 5681は、依然としてスロースタート、輻輳回避、高速再送、高速リカバリを標準として挙げており、輻輳制御の研究はこの論文から独自の分野へと発展した。

出典をたどる

出典

  1. Congestion Avoidance and Control (Van Jacobson & Michael Karels, November 1988) Lawrence Berkeley National Laboratory · ee.lbl.gov
  2. RFC 5681 — TCP Congestion Control Internet Engineering Task Force · rfc-editor.org