ネットワーク (21)

輻輳制御

• 輻輳の例
  
  • セグメントの開始シーケンス番号と送信された時刻をプロット したもの(Fig.21.6)。 再転送は右下への移動した点として表される(時刻10,14,21の3回)。
  • 10秒ふきんでの再送の様子 (Fig.21.7)
    セグメント45消失。 バイト6657より前のものは全てが確認応答されていて(セグメント58)、 その後に同一のシーケンス番号で8個のACKが続いている。 シーケンス番号6657から始まるデータの再転送(セグメント63)を 強いているのは、重複ACKの3番目(セグメント62)の受信である。 バークレーの実装では、重複ACKを3個受けとると、セグメントが 消失したと考え再送する(＝ Jacobsonの高速再送アルゴリズム。 これに続いて Jacobsonの高速リカバリ・アルゴリズムを用いる)。 再転送(セグメント63)後、送り手は(再転送に対するACKを待たずに) 通常のデータ転送を継続している(セグメント67,69,71)。

    受け手側での動作。通常のデータ(セグメント43)が手順どおりに 受けとられると受信TCPは256バイトのデータをユーザ・プロセスに渡す。 しかし、次に受けとられたセグメント (セグメント 46) は順番が違う。 そのデータの開始シーケンス番号 (6913) は、予想されたシーケンス 番号 (6657) と異なっている。TCPは 256バイトのデータを保存し、 それまでに無事に受け取った最も大きなシーケンス番号+1 (6657) の ACKで応答する。 vangoghによって受け取られた次の7つのセグメント (48,50,52,54,55,57,59) は全て順番が異なるので、(データはセーブされて)重複ACKが生成される。 消失したデータが到着すると (セグメント 63)、受信TCPは バッファに 6657〜8960のデータを持っているので、その 2304バイトの データをユーザ・プロセスに渡す。このデータに関しては、セグメント72 でまとめて確認応答する。このACKは、まだユーザ・プロセスが2304バイトの データを読んでいないので5888 (8192-2304) のウィンドウを広告する。

• 輻輳回避アルゴリズム
  

  スロースタートにより、コネクションを流れるデータの量は増加していくが、
  中継ルータの限界に到達するとパケットが破棄されはじめる。
  
  前提：「パケットが破損によって失われることは稀で(1%以下)、パケットの
  消失がおきるのは途中で輻輳が発生しているためである」
  
  パケットの消失を認識する:
    タイムアウトの発生
    重複ACKの受信
  
  輻輳回避とスロースタートは目的が異なる全く独立したアルゴリズム。
  しかし、輻輳が発生するとパケットの転送率を減らすためにスロースタート
  を用いるので、一緒に実装されている。
  
  (注)輻輳回避：送り手によるフロー制御。ウィンドウ：受け手によるフロー制御。
  
  
  輻輳ウィンドウ (cwnd)
  しきい値 (ssthresh)
  

  1. コネクションの初期化。cwnd ← 1セグメント。ssthresh←65535byte。
  2. TCPの出力ルーチンは min(cwnd,受け手の広告したウィンドウ) までしか送信しない。
  3. 輻輳が発生すると、ssthresh←現行ウィンドウサイズの1/2
     タイムアウトの発生によって輻輳が認識された場合は cwnd←1
  4. 新しいデータのACKが返ってくると、cwndを増加させる (Fig.21.8)。

         cwnd≦ssthresh の場合、スロースタート
                ACKの受信毎に cwnd ← cwnd + 1
         それ以外の場合、輻輳回避
                ACKの受信毎に cwnd ← cwnd + 1/cwnd
     

• 高速再転送と高速リカバリ・アルゴリズム
  TCPが順番の違ったセグメントを受け取ったとき、直ちに 確認応答 (重複ACK) を送り返す。 ただし、1個の重複ACKだけでは、その原因が「セグメントの消失」 なのか、「セグメント到着の順番が入れ替わっただけ」なのか判断できない。 いくつかの(実装では3個)重複ACKが到着すると「セグメントの消失」と判断できる。 その場合は、消失したセグメントを再送し、輻輳回避動作を始める (スロースタートは行わない)。
  1. 3個目の重複ACKを受け取ると、

         ssthresh ← (現行の輻輳ウィンドウ cwnd) / 2
         消失セグメントを再送する。
         cwnd ← ssthresh + 3 * (セグメントサイズ)
       

  2. 別の重複ACKが到着する度に

         cwnd ← cwnd + 1 *  (セグメントサイズ)
         新しい cwnd 値に許可されたらパケットを送出する。
       

  3. ステップ1の再転送に対する確認応答(バッファにセーブされている ものもまとめて確認応答される)が返ってきたら

         cwnd ← ssthresh