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の最新の実装は、これまでインターネット標準としては完全な形に
ドキュメント化されることのなかった４つの相互に絡み合ったアルゴリズム
を含んでいる：すなわちスロースタート、輻輳回避、早期再送、早期回復。
[2]及び[3]は、これらのアルゴリズムの詳細の一部を提供している。[4]は、
実行中のアルゴリズムの例を示している。そして、[5]は、4.4BSDの実装
のためのソースコードを示している。RFC1122は、TCPが、スロースタート
と輻輳回避([1]のSection 4.2.2.15、参考文献として[2]を引用)を実装しな
ければならないと要求しているが、早期再送と早期回復はRFC1122の後に
実装されたため対象外となっている。このドキュメントの目的は、インター
ネットのためのこれらの４つのアルゴリズムをドキュメント化することである。
謝辞
このメモの大部分は、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の
承認のもとに利用されている。ここに記述されている４つのアルゴリズムは
Van Jacobsonによって開発されたものである。
１．スロースタート
古いTCPは、送信側がネットワークに複数セグメントを送出すると伴に
接続を開始し、受信側から告知されたウィンドウサイズに至るまで送出し
続ける。２つのホストが同じＬＡＮ上にある場合は、これで大丈夫なのだが、
送信側と受信側の間にルータや遅い回線が存在すると問題が生じる可能性が
ある。中間ルータのいくつかは、パケットキューイングしなければならず、
メモリを使い果たしてしまう可能性がある。[2]は、この単純なアプローチが
TCP接続のスループットをいかにドラスティックに下げてしまうかを示して
いる。
Stevens Standards Track [Page 1]
RFC 2001 TCP January 1997
これを回避するアルゴリズムは、”スロースタート”と呼ばれる。スロー
スタートは、ネットワークに送り出されるべき新たなパケットの速度は
接続の終点から返ってくる確認応答の速度である、という事実の観察に
基いて動作する。
スロースタートは送信者のTCPにもう１つのウィンドウを加える：すなわ
ち、"cwnd"と呼ばれる輻輳ウィンドウである。他のネットワーク上のホスト
との間に新しいコネクションが確立されると、輻輳ウィンドウは、１セグメン
トサイズに初期化される(すなわち、受信者から告知されたセグメントサイズ、
もしくは、デフォルト、一般に５３６バイトか５１２バイト)。ＡＣＫが
１返るごとに輻輳ウィンドウは１セグメントずつ増える。送信者は、輻輳
ウィンドウと受信者から告知されたウィンドウのサイズの小さい方に達する
まで送信可能である。輻輳ウィンドウは送信者によって課せられたフロー
制御であり、一方告知(された)ウィンドウは受信者によって課せられた
フロー制御である。前者はネットワーク輻輳に気づいた送信者の評価に基づ
いており、後者はこの接続で受信者が利用できるバッファ領域の総和と関連
している。
送信者は、セグメントを１つ送信しそのＡＣＫを待つことから始める。ＡＣＫ
が返ってくると、輻輳ウィンドウはサイズが１セグメントから２セグメント
に増え２セグメント送信可能になる。その２セグメントそれぞれに対して確認
応答が返ってくると、輻輳ウィンドウは４セグメントに増える。これは、指数
的な増加となるが、正確に指数的というわけではない。なぜなら、受信者は
一般的にセグメントを２つ受け取るごとに１つＡＣＫを返すといったように、
ＡＣＫを遅らせることがあるからである。
あるポイントでインターネットの容量が限界に達すると、中間ルータで
パケットが捨てられ始める。このことは、送信側に輻輳ウィンドウが大きく
なり過ぎたことを伝える。
初期の実装は、一方の終端が異なるネットワーク上にあるときのみスロー
スタートを実行していた。現在ではいつもスロースタートを実行している。
２．輻輳回避
輻輳は、データが太い回線(速いＬＡＮ)を通って細い回線(遅いＷＡＮ)
に送出される時に発生する。また、複数の入力ストリームがその入力の
合計より小さな出力能力しか持たないルータに到着した時にも輻輳が発生
する。輻輳回避は失われたパケットを処理する方法である。輻輳回避は
[2]に記されている。
このアルゴリズムでは、障害によるパケットの損失はとても少ない(１％
よりもずっと少ない)と想定している。それゆえ、パケットの損失は、受信
元から送信先の間のネットワークのどこかで輻輳が起こっていることを知ら
せる合図なのである。パケット損失には２つの徴候がある。すなわち：タイ
ムアウトの発生とduplicate ACK の受信である。
Stevens Standards Track [Page 2]
RFC 2001 TCP January 1997
輻輳回避とスロースタートは、異なる目的を持った独立のアルゴリズム
である。しかし、輻輳が発生したとき、ＴＣＰは、ネットワークに送り
出すパケットの転送速度を下げ、再開のためにスロースタートを実行し
なければならない。実際両者は一緒に実装される。
輻輳回避とスロースタートは、２つの変数(輻輳ウィンドウ−cwndと
スロースタートの敷居値−ssthresh)が各々のコネクションごとに保持される
よう要求する。一連のアルゴリズムは以下のように動作する。
1.ある与えられたコネクションに対して、cwndは１セグメントに、
ssthreshは65535バイトにセットし初期化する。
2.TCPアウトプットルーチンは、cwndと受信者から告知されたウィンドウ
サイズの小さい方より大きなデータは決して送信しない。
3.輻輳(タイムアウトとduplicate ACK の受け取りが示す)が発生した時には、
現在のウィンドウサイズ(cwndと受信者から告知されたウィンドウサイ
ズの小さい方、少なくとも２セグメント)の１/２のサイズがssthreshに
セーブされる。さらに、輻輳がタイムアウトによるものであることを
を示す場合には、cwndは１セグメントにセットされる(すなわち、スロー
スタート)。
4.新しいデータが受信者によって確認応答されたら、cwndを加算するが、
その増やし方は、TCPがスロースタートか輻輳回避のどちらを実行するか
で決まる。
もし、cwndがssthresh以下であるなら、TCPはスロースタートの最中で
ある。そうでなければTCPは輻輳回避を実行している。スロースタートは
TCPのウィンドウサイズが輻輳が発生したときのウィンドウサイズの半分
のサイズ(ステップ２の中で、問題が発生したウィンドウサイズ の１/２の
大きさが記憶されているので)になるまで続き、それから輻輳回避に引き
継がれる。
スロースタートは、cwndを１セグメントから始めて、ＡＣＫが１つ返っ
て来るたびに１セグメントの割合で増やしていく。先に述べたように、
ウィンドウサイズは１セグメントが２セグメント、そして４セグメント
といったように指数的に増えていく。輻輳回避は、１つＡＣＫが返って
くるたびにcwndをsegsize×segsize/cwndの割合で増やすように要求する
(segsizeはセグメントサイズ、また、cwndはバイト単位で保持される)。
これは、スロースタートの指数的なcwndの増加に対して線形的な増加
といえる。cwndの増加は、ラウンドトリップ時間ごとに(ラウンドトリッ
プ時間にＡＣＫをいくつ受け取ったかにかかわらず)多くても１セグメン
ト程度であるべきである。それに対して、スロースタートはラウンドトリ
ップ時間に受け取ったＡＣＫの数によってcwndを増加させる。
Stevens Standards Track [Page 3]
RFC 2001 TCP January 1997
多くの実装では、輻輳回避の間に、適切とはいえないセグメントサイズの
小さな破片(一般的にセグメントサイズの８分の１)を輻輳ウィンドウに
加えている。これは良くないので将来のリリースでは真似るべきではない。
３．早期再送
輻輳回避アルゴリズムの修正は、1990年に提案された([3])。変更箇所を
示す前に、TCPは、順序通りでないセグメントを受け取った時、即時確認
応答(duplicate ACK)を生成する([1]のセクション4.2.2.21に、そのようにする
理由の１つは実験的な早期再送のアルゴリズムのためであるという記述が
ある)ということを理解せよ。このduplicate ACKは遅れるべきではない。
duplicate ACKの目的は、送信者に順序通りでないセグメントが受け取られた
ことを知らせると同時に、期待されているシーケンスナンバーを教えること
だからである。
送信者側のTCPは、duplicate ACKがセグメントの消失で発生したのか、また
は、ちょうど受信者側でセグメントの並べ替えをしている途中で発生した
のかわからないので、少ないいくつかの duplicate ACKを受け取るまで待つ。
もしちょうど並べ替え途中のセグメントがあるなら、並べ替えられたセグメ
ントが処理される前にはせいぜい１つか２つの、duplicate ACKしか存在しない
だろう、そしてそれから(並べ替えられたセグメントに対し)新たなACKが
生成されるだろうと思われる。もし、３つ以上のduplicate ACK が続けて返っ
てきたら、それは、セグメントが失われたことを強く示している。TCPは
そのとき、再送タイマーが切れるのを待たずに失われたと思われるセグメ
ントの再送を実行する。
４．早期回復
早期再送で、失われたと思われるセグメントを再送した後には、スロースター
トではなく、輻輳回避が実行される。これが、早期回復のアルゴリズム
である。そして、これが、そこそこの輻輳の下で(特にウィンドウサイズが
大きい時に)高いスループットを可能にする改良である。
この場合に、スロースタートを実行しない理由は、duplicate ACKの受け取り
が、TCPにパケットが失われただけ以上のことを伝えるからである。別の
セグメントを受け取ったとき、受信者はduplicate ACKを生成することしか
できないので、(その時受け取るはずの)セグメントはネットワークに残され
たまま(失われてはいないがまだ届いていない)か、受信側のバッファに存在
する(まだ並べ替えが完了していない)かのどちらかである。つまり、２つの
終端の間にはまだデータフローが存在しており、TCPはスロースタートを
開始することによって突然フローを減らしたくないのである。
早期再送と早期回復のアルゴリズムは以下に示すように、普通一緒に実装
される。
Stevens Standards Track [Page 4]
RFC 2001 TCP January 1997
1.３番目のduplicate ACKが続けて受け取られたとき、ssthreshを現在の
輻輳ウィンドウ(cwnd、少なくとも２セグメント)の１/２にする。
失われたセグメントを再送する。cwndをssthreshにセグメントサイズ
３つ分を加えた値にする。これは、ネットワークに残っている
セグメントと受信者側にキャッシュされたセグメントの数(３)分だけ
輻輳ウィンドウを増やしたのである。
2.別のduplicate ACKが到着するごとに、cwndをセグメントサイズずつ
増やす。これは、ネットワークに残された更なるセグメントのために
輻輳ウィンドウを増やしているのである。更新したcwndの値が許せば、
パケットを送信する。
3.次のＡＣＫが返って新しいデータの送達が確認されたら、cwndをssthresh
のサイズにセットする(ステップ１でセットされた値)。このＡＣＫは
ステップ１の再送に対する確認応答(再送後１ラウンドトリップタイム
に戻ってくる)であるべきである。さらに、このＡＣＫはパケットが失わ
れてから最初のduplicate ACKを受け取るまでのあいだに送られた全ての
中間セグメントに対する確認応答であるべきである。TCPのスループット
がパケット喪失時の送信速度の半分にまで下がっているので、このステッ
プは輻輳回避そのものである。
早期再送アルゴリズムは4.3BSD Tahoeリリースに初めて登場し、その後、
スロースタートに取り入れられた。早期回復アルゴリズムは4.3BSD Reno
リリースで登場した。
５．セキュリティに関する考察
セキュリティに関する考察はこのメモでは議論されていない。
６．参考文献
[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]
一覧
スポンサーリンク
