Congestion Avoidance and Control

October 9, 2021

86年の10月に生じたインターネットの輻輳の反省から、4BSDに7つのTCPの輻輳制御のアルゴリズムが導入された。 うち5つは、送信したパケットが到達や消失でネットワークからなくなるまでウィンドウサイズ以上の新しいパケットを送らない原則を守るためにある。 この原則をconservation of packets principleという。

原則が守られない状況の原因は、接続が平衡状態に到達しないか、古いパケットがネットワークから消える前に新しいパケットが流れているか、経路上のリソースが足らずに平衡に到達できないかの3つのいずれかである。 消失したパケットを再送する接続や最初のパケット送信に問題があるときに、接続が平衡状態に達しないことがある。 これは、ackが到達した既存のパケットがあることを前提にするため、前提をみたさない初回の接続や再送はackによって原則を守ることができないからである。 slow-startアルゴリズムは、接続後の最初のパケット送信や再送では輻輳ウィンドウサイズを1パケットに制限し、到達ごとに1パケットずつ受信側の設定した上限の大きさまでウィンドウサイズを大きくしていくことで、これらの接続を制御する。

TCPプロトコルを正しく実装していれば、送信側の再送するタイミングに問題があるとき、古いパケットの消失前に新しいパケットが送られる。 正しい再送のタイミングのためには、正確なラウンドトリップタイム(RTT)の予測が欠かせない。 待ち行列理論によれば、負荷が大きくなるについてRTT(\(R\))のばらつきが急激に大きくなる。 そこで、RTTの予測値を\(R\)、パラメタを\(\beta\)とする再送のタイムアウト間隔\(\beta R\)に対して、\(\beta\)を定数にせずoverflowのおそれが少なく分散よりも大きな値になる平均偏差を使い、実際の測定結果にもとづくタイムアウト間隔を設定する。 また、一度再送に失敗したら、以降は間隔を指数関数的に増やして再送する。

経路上のリソースが不足しているときにタイムアウトがおきるため、タイムアウト時には流すパケットを減らさなければならない。 タイムアウトがおきたら、輻輳ウィンドウサイズを半分にする。 ackを受けとれたら、輻輳ウィンドウサイズに現在の輻輳ウィンドウサイズの逆数を加算し、流せるパケットの量を増やす。 送信するときは、受信側の設定する輻輳ウィンドウで通信する。

論文をこちらからダウンロードできます。