RFC2001 日本語訳

2001 TCP Slow Start, Congestion Avoidance, Fast Retransmit, and FastRecovery Algorithms. W. Stevens. January 1997. (Format: TXT=12981 bytes) (Obsoleted by RFC2581) (Status: PROPOSED STANDARD)

RFC一覧
英語原文

Network Working Group                                         W. Stevens
Request for Comments: 2001                                          NOAO
Category: Standards Track                                   January 1997


		TCP スロースタートと、輻輳回避、
		早期再送、早期回復 アルゴリズム

このメモの位置づけ

 このドキュメントはインターネットコミュニティのためのインターネット
 標準プロトコルを記すと同時に、改善のための討論及び提案を要求するもの
 である。標準化情勢と、このプロトコルの位置づけは、”インターネット
 公式プロトコル標準”(STD 1)の現行版を参照のこと。なお、このメモの
 配布に制限はない。

摘要

 TCPの最新の実装は、これまでインターネット標準としては完全な形に
 ドキュメント化されることのなかった4つの相互に絡み合ったアルゴリズム
 を含んでいる:すなわちスロースタート、輻輳回避、早期再送、早期回復。
  [2]及び[3]は、これらのアルゴリズムの詳細の一部を提供している。[4]は、
 実行中のアルゴリズムの例を示している。そして、[5]は、4.4BSDの実装
 のためのソースコードを示している。RFC1122は、TCPが、スロースタート
 と輻輳回避([1]のSection 4.2.2.15、参考文献として[2]を引用)を実装しな
 ければならないと要求しているが、早期再送と早期回復はRFC1122の後に
 実装されたため対象外となっている。このドキュメントの目的は、インター
 ネットのためのこれらの4つのアルゴリズムをドキュメント化することである。

謝辞

 このメモの大部分は、W.Richard Stevens著(Addison-Wesley,1994)”TCP/IP
  Illustrated, Volume 1:The Protocols”及びGraray.R.Wright、W.Richard 
  Stevens共著(Addison-Wesley,1995)”TCP/IP Illustrated, Volume 2:The 
  Implementation”から引用したものである。この資料は、Addison-Wesleyの
 承認のもとに利用されている。ここに記述されている4つのアルゴリズムは
 Van Jacobsonによって開発されたものである。

1.スロースタート

 古いTCPは、送信側がネットワークに複数セグメントを送出すると伴に
 接続を開始し、受信側から告知されたウィンドウサイズに至るまで送出し
 続ける。2つのホストが同じLAN上にある場合は、これで大丈夫なのだが、
 送信側と受信側の間にルータや遅い回線が存在すると問題が生じる可能性が
 ある。中間ルータのいくつかは、パケットキューイングしなければならず、
 メモリを使い果たしてしまう可能性がある。[2]は、この単純なアプローチが
 TCP接続のスループットをいかにドラスティックに下げてしまうかを示して
 いる。



Stevens                     Standards Track                     [Page 1]

RFC 2001                          TCP                       January 1997


 これを回避するアルゴリズムは、”スロースタート”と呼ばれる。スロー
 スタートは、ネットワークに送り出されるべき新たなパケットの速度は
 接続の終点から返ってくる確認応答の速度である、という事実の観察に
 基いて動作する。

 スロースタートは送信者のTCPにもう1つのウィンドウを加える:すなわ
 ち、"cwnd"と呼ばれる輻輳ウィンドウである。他のネットワーク上のホスト
 との間に新しいコネクションが確立されると、輻輳ウィンドウは、1セグメン
 トサイズに初期化される(すなわち、受信者から告知されたセグメントサイズ、
 もしくは、デフォルト、一般に536バイトか512バイト)。ACKが
 1返るごとに輻輳ウィンドウは1セグメントずつ増える。送信者は、輻輳
 ウィンドウと受信者から告知されたウィンドウのサイズの小さい方に達する
 まで送信可能である。輻輳ウィンドウは送信者によって課せられたフロー
 制御であり、一方告知(された)ウィンドウは受信者によって課せられた
 フロー制御である。前者はネットワーク輻輳に気づいた送信者の評価に基づ
 いており、後者はこの接続で受信者が利用できるバッファ領域の総和と関連
 している。

 送信者は、セグメントを1つ送信しそのACKを待つことから始める。ACK
 が返ってくると、輻輳ウィンドウはサイズが1セグメントから2セグメント
 に増え2セグメント送信可能になる。その2セグメントそれぞれに対して確認
 応答が返ってくると、輻輳ウィンドウは4セグメントに増える。これは、指数
 的な増加となるが、正確に指数的というわけではない。なぜなら、受信者は
 一般的にセグメントを2つ受け取るごとに1つACKを返すといったように、
 ACKを遅らせることがあるからである。

 あるポイントでインターネットの容量が限界に達すると、中間ルータで
 パケットが捨てられ始める。このことは、送信側に輻輳ウィンドウが大きく
 なり過ぎたことを伝える。

 初期の実装は、一方の終端が異なるネットワーク上にあるときのみスロー
 スタートを実行していた。現在ではいつもスロースタートを実行している。

2.輻輳回避

 輻輳は、データが太い回線(速いLAN)を通って細い回線(遅いWAN)
 に送出される時に発生する。また、複数の入力ストリームがその入力の
 合計より小さな出力能力しか持たないルータに到着した時にも輻輳が発生
 する。輻輳回避は失われたパケットを処理する方法である。輻輳回避は
 [2]に記されている。

 このアルゴリズムでは、障害によるパケットの損失はとても少ない(1%
 よりもずっと少ない)と想定している。それゆえ、パケットの損失は、受信
 元から送信先の間のネットワークのどこかで輻輳が起こっていることを知ら
 せる合図なのである。パケット損失には2つの徴候がある。すなわち:タイ
 ムアウトの発生とduplicate ACK の受信である。





Stevens                     Standards Track                     [Page 2]

RFC 2001                          TCP                       January 1997


 輻輳回避とスロースタートは、異なる目的を持った独立のアルゴリズム
 である。しかし、輻輳が発生したとき、TCPは、ネットワークに送り
 出すパケットの転送速度を下げ、再開のためにスロースタートを実行し
 なければならない。実際両者は一緒に実装される。

 輻輳回避とスロースタートは、2つの変数(輻輳ウィンドウ−cwndと
 スロースタートの敷居値−ssthresh)が各々のコネクションごとに保持される
 よう要求する。一連のアルゴリズムは以下のように動作する。

 1.ある与えられたコネクションに対して、cwndは1セグメントに、
  ssthreshは65535バイトにセットし初期化する。

 2.TCPアウトプットルーチンは、cwndと受信者から告知されたウィンドウ
  サイズの小さい方より大きなデータは決して送信しない。

 3.輻輳(タイムアウトとduplicate ACK の受け取りが示す)が発生した時には、
  現在のウィンドウサイズ(cwndと受信者から告知されたウィンドウサイ
  ズの小さい方、少なくとも2セグメント)の1/2のサイズがssthreshに
  セーブされる。さらに、輻輳がタイムアウトによるものであることを
  を示す場合には、cwndは1セグメントにセットされる(すなわち、スロー
  スタート)。

 4.新しいデータが受信者によって確認応答されたら、cwndを加算するが、
  その増やし方は、TCPがスロースタートか輻輳回避のどちらを実行するか
  で決まる。

  もし、cwndがssthresh以下であるなら、TCPはスロースタートの最中で
  ある。そうでなければTCPは輻輳回避を実行している。スロースタートは
  TCPのウィンドウサイズが輻輳が発生したときのウィンドウサイズの半分
  のサイズ(ステップ2の中で、問題が発生したウィンドウサイズ の1/2の
  大きさが記憶されているので)になるまで続き、それから輻輳回避に引き
  継がれる。

  スロースタートは、cwndを1セグメントから始めて、ACKが1つ返っ
  て来るたびに1セグメントの割合で増やしていく。先に述べたように、
  ウィンドウサイズは1セグメントが2セグメント、そして4セグメント
  といったように指数的に増えていく。輻輳回避は、1つACKが返って
  くるたびにcwndをsegsize×segsize/cwndの割合で増やすように要求する
  (segsizeはセグメントサイズ、また、cwndはバイト単位で保持される)。
  これは、スロースタートの指数的なcwndの増加に対して線形的な増加
  といえる。cwndの増加は、ラウンドトリップ時間ごとに(ラウンドトリッ
  プ時間にACKをいくつ受け取ったかにかかわらず)多くても1セグメン
  ト程度であるべきである。それに対して、スロースタートはラウンドトリ
  ップ時間に受け取ったACKの数によってcwndを増加させる。







Stevens                     Standards Track                     [Page 3]

RFC 2001                          TCP                       January 1997


 多くの実装では、輻輳回避の間に、適切とはいえないセグメントサイズの
 小さな破片(一般的にセグメントサイズの8分の1)を輻輳ウィンドウに
 加えている。これは良くないので将来のリリースでは真似るべきではない。

3.早期再送

 輻輳回避アルゴリズムの修正は、1990年に提案された([3])。変更箇所を
 示す前に、TCPは、順序通りでないセグメントを受け取った時、即時確認
 応答(duplicate ACK)を生成する([1]のセクション4.2.2.21に、そのようにする
 理由の1つは実験的な早期再送のアルゴリズムのためであるという記述が
 ある)ということを理解せよ。このduplicate ACKは遅れるべきではない。
 duplicate ACKの目的は、送信者に順序通りでないセグメントが受け取られた
 ことを知らせると同時に、期待されているシーケンスナンバーを教えること
 だからである。

 送信者側のTCPは、duplicate ACKがセグメントの消失で発生したのか、また
 は、ちょうど受信者側でセグメントの並べ替えをしている途中で発生した
 のかわからないので、少ないいくつかの duplicate ACKを受け取るまで待つ。
 もしちょうど並べ替え途中のセグメントがあるなら、並べ替えられたセグメ
 ントが処理される前にはせいぜい1つか2つの、duplicate ACKしか存在しない
 だろう、そしてそれから(並べ替えられたセグメントに対し)新たなACKが
 生成されるだろうと思われる。もし、3つ以上のduplicate ACK が続けて返っ
 てきたら、それは、セグメントが失われたことを強く示している。TCPは
 そのとき、再送タイマーが切れるのを待たずに失われたと思われるセグメ
 ントの再送を実行する。

4.早期回復
 早期再送で、失われたと思われるセグメントを再送した後には、スロースター
 トではなく、輻輳回避が実行される。これが、早期回復のアルゴリズム
 である。そして、これが、そこそこの輻輳の下で(特にウィンドウサイズが
 大きい時に)高いスループットを可能にする改良である。

 この場合に、スロースタートを実行しない理由は、duplicate ACKの受け取り
 が、TCPにパケットが失われただけ以上のことを伝えるからである。別の
 セグメントを受け取ったとき、受信者はduplicate ACKを生成することしか
 できないので、(その時受け取るはずの)セグメントはネットワークに残され
 たまま(失われてはいないがまだ届いていない)か、受信側のバッファに存在
 する(まだ並べ替えが完了していない)かのどちらかである。つまり、2つの
 終端の間にはまだデータフローが存在しており、TCPはスロースタートを
 開始することによって突然フローを減らしたくないのである。

 早期再送と早期回復のアルゴリズムは以下に示すように、普通一緒に実装
 される。








Stevens                     Standards Track                     [Page 4]

RFC 2001                          TCP                       January 1997


 1.3番目のduplicate ACKが続けて受け取られたとき、ssthreshを現在の
  輻輳ウィンドウ(cwnd、少なくとも2セグメント)の1/2にする。
  失われたセグメントを再送する。cwndをssthreshにセグメントサイズ
  3つ分を加えた値にする。これは、ネットワークに残っている
  セグメントと受信者側にキャッシュされたセグメントの数(3)分だけ
  輻輳ウィンドウを増やしたのである。

 2.別のduplicate ACKが到着するごとに、cwndをセグメントサイズずつ
  増やす。これは、ネットワークに残された更なるセグメントのために
  輻輳ウィンドウを増やしているのである。更新したcwndの値が許せば、
  パケットを送信する。

 3.次のACKが返って新しいデータの送達が確認されたら、cwndをssthresh
  のサイズにセットする(ステップ1でセットされた値)。このACKは
  ステップ1の再送に対する確認応答(再送後1ラウンドトリップタイム
  に戻ってくる)であるべきである。さらに、このACKはパケットが失わ
  れてから最初のduplicate ACKを受け取るまでのあいだに送られた全ての
  中間セグメントに対する確認応答であるべきである。TCPのスループット
  がパケット喪失時の送信速度の半分にまで下がっているので、このステッ
  プは輻輳回避そのものである。

 早期再送アルゴリズムは4.3BSD Tahoeリリースに初めて登場し、その後、
 スロースタートに取り入れられた。早期回復アルゴリズムは4.3BSD Reno
 リリースで登場した。

5.セキュリティに関する考察

 セキュリティに関する考察はこのメモでは議論されていない。

6.参考文献

   [1]  B. Braden, ed., "Requirements for Internet Hosts --
        Communication Layers," RFC 1122, Oct. 1989.

   [2]  V. Jacobson, "Congestion Avoidance and Control," Computer
        Communication Review, vol. 18, no. 4, pp. 314-329, Aug. 1988.
        ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z.

   [3]  V. Jacobson, "Modified TCP Congestion Avoidance Algorithm,"
        end2end-interest mailing list, April 30, 1990.
        ftp://ftp.isi.edu/end2end/end2end-interest-1990.mail.

   [4]  W. R. Stevens, "TCP/IP Illustrated, Volume 1: The Protocols",
        Addison-Wesley, 1994.

   [5]  G. R. Wright, W. R. Stevens, "TCP/IP Illustrated, Volume 2:
        The Implementation", Addison-Wesley, 1995.




Stevens                     Standards Track                     [Page 5]

RFC 2001                          TCP                       January 1997


著者連絡先:

    W. Richard Stevens
    1202 E. Paseo del Zorro
    Tucson, AZ  85718

    Phone: 520-297-9416

    EMail: rstevens@noao.edu
    Home Page: http://www.noao.edu/~rstevens





Stevens                     Standards Track                     [Page 6]

一覧

 RFC 1〜100  RFC 1401〜1500  RFC 2801〜2900  RFC 4201〜4300 
 RFC 101〜200  RFC 1501〜1600  RFC 2901〜3000  RFC 4301〜4400 
 RFC 201〜300  RFC 1601〜1700  RFC 3001〜3100  RFC 4401〜4500 
 RFC 301〜400  RFC 1701〜1800  RFC 3101〜3200  RFC 4501〜4600 
 RFC 401〜500  RFC 1801〜1900  RFC 3201〜3300  RFC 4601〜4700 
 RFC 501〜600  RFC 1901〜2000  RFC 3301〜3400  RFC 4701〜4800 
 RFC 601〜700  RFC 2001〜2100  RFC 3401〜3500  RFC 4801〜4900 
 RFC 701〜800  RFC 2101〜2200  RFC 3501〜3600  RFC 4901〜5000 
 RFC 801〜900  RFC 2201〜2300  RFC 3601〜3700  RFC 5001〜5100 
 RFC 901〜1000  RFC 2301〜2400  RFC 3701〜3800  RFC 5101〜5200 
 RFC 1001〜1100  RFC 2401〜2500  RFC 3801〜3900  RFC 5201〜5300 
 RFC 1101〜1200  RFC 2501〜2600  RFC 3901〜4000  RFC 5301〜5400 
 RFC 1201〜1300  RFC 2601〜2700  RFC 4001〜4100  RFC 5401〜5500 
 RFC 1301〜1400  RFC 2701〜2800  RFC 4101〜4200 

スポンサーリンク

Date.setSeconds

ホームページ製作・web系アプリ系の製作案件募集中です。

上に戻る