ゼミ: Computer Networks 5th edition: 6.5.10
久野靖∗

2014.12.19
5.10

TCP の混雑制御□ 混雑制御は Van Jacobson(1988) のすばらしい物語の結果□ TCP の主要機能の 1 つ、混雑制御の話は最後までとって• 1986 に開始した初期のインターネットは急速にあった。

利用拡大→混雑崩壊 (congestion collapse) で• どんなネットでも、容量以上の負荷が来たら混雑。イ

goodput(有効スループット) が 1/100 にンターネットも同じ。

• Jacobson らは何が起きているのか、どうやって克服するか研究• ネットワーク層はキューの伸びを検出し対処しようとする→できることといえば、パケットを捨てること• ネットワーク層のこのふるまいを感知して通信を絞 □ Jacobson らがやった手直しとは AIMD 混雑窓を近似的に入れること
りネットに入る負荷を調節するのはトランスポート層の仕事• 面白いのは既存の TCP 実装にどうやってこれを入れたか• インターネットでは TCP が、エラーのない伝送に加えて、この混雑への対応を主に受け持っている• メッセージ形式とかは変えられない (すぐに設置できないから)□ 混雑制御の一般的な話は 6.3 でやった。

• まず気づいたこと:す信号• 鍵 と な る の はAIMD(additive increase,multicative decrease) → こ れ に よ り 公 平 か

パケット喪失は混雑を的確に表• 実際にはこの信号は「混雑してしまってから」来るのでやや遅いが、極めて信頼できる

つ効率のよい帯域割り当てに収束• TCP はこれを窓制御と併せ、パケット喪失という 2 値• 結局、過負荷になってもパケットを落とさないルー信号に基づき行う

タなんて作れないからそうなる (ルータに 1TB 積ん• このため TCP は混雑窓 (congestion window) を管理

でも 1Tbit/sec の時代になってすぐに満杯に)• そのサイズは送信側がネットワーク中を流している □ ただし、喪失が混雑の信号として信頼できるためには、伝送エラーはごく少なくないといけない
バイト数• 送信速度は「混雑窓サイズ÷ RTT」で、これを AIMD

• 無線の場合はそうは行かないので→無線リンクはそのリンクだけの再送機能を持たせて喪失を回復で調整• この結果、無線でも有線 (銅線、ファイバー) でもエ□ 混雑窓は流量制御窓 (flow control window) と「一緒ラー率は低いに」維持□ というわけで、TCP はパケット喪失があったら混雑をう• 後者は受信側が持っているバッファのバイト数

たがい、注意深く兆候を調べる• 両方を維持し、送信できる量はその両者の小さい方の値• 例:• 的確かつ迅速にパケット喪失に対処できるためには、受信側は「64k 送っていいよ」しかし送信側はよい再送タイマーが必要だが → 既に TCP では RTT「32k より沢山送ったら詰まる」と思えば 32k だけの平均や変動を見積もってあった

送る• Jacobson の重要な 1 歩はこのタイマーに変動率を追加したこと• 送信側が「128k まで送っても詰まらない」と思っても受信側に 64k しかバッファがなければやっぱり 64k• よい再送タイムアウトを得ることはネットを飛んでだけ送るいるデータ量を知ること (送信バイトと ACK バイトの差がデータ量)∗ 筑波大学ビジネスサイエンス系

1□ とすれば話は簡単?
ればいい?

混雑窓を追跡して AIMD で制御す• キューが積み上がり、待ちやパケット喪失が発生→送信側でタイムアウト→そうしたらそれ以上増やさ

そんな簡単ではない。

なくなる• まず、パケット注入率は (短期的にでも) ネットに合ったものである必要• 例:• 毎 回 ぶ つ か る ま で や ら な い た め 、slow start
threshold という値を維持→ 最初は大きい値 →タイムアウトしたら現在の混雑窓サイズの半分をこホストの混雑窓が 64K で、1G のイーサネットに接続→ 64K 一気に送信?

のしきい値として設定• 途中に 1Mbps の ADSL がはさまっていたら、その入口を 0.5 秒もふさいでしまう → VoIP とかが流れて• 最後に倍にしたことで超えたので、半分というのは適正量のよい見積もりいたら致命的□ しきい値を超えたら slow start から AIMD の定数増加• 一気に送るというのは混雑を産もうとしてるのに等
しいに切り替え• 1RTT ごとに 1 ずつ混雑窓を増加。M を最大セグメントサイズ、C を混雑窓サイズとして、C/M パケット ACK□ 一方で、小さいバーストは望ましい。図 6-43 参照。

• 少数のパケット (4 個) をバーストで送る→ 1M の入されるごとに M*M/C だけ C を増やすとかが典型的

口で待たされるがキューは長くない→ 1M 線の上では• すでに最適値に近づいてきているので、ゆっくり調のびてる

節でよい (図 6-45)• 受信側に来て ACK が返される→ ACK の時間も伸びて□ 性能のための工夫はほかにも可能

いる→どれくらい伸びてるかで最も遅いリンクがどれだけか分かる!

(ack clock)• タイムアウトを待つのは (タイムアウトは保守的に設定するため長めなので) 遅くなる

• 以後、この間隔で送信すれば待ちなしで通過することになる• パケットが喪失するとその後 ACK の番号が増えなくなり、混雑窓が一杯なのでそれ以上送れない状態が• ack clock によって送信率を制御することは TCP の心臓部の 1 つ

しばらく続く• タイマーが発火して再送されるとそこから再度 slow

□ 次の問題は、AIMD は小さい窓サイズから始めるとバラstart になるンスまで時間が掛かるということ

10Mbps で RTT が 100msec だと、混雑窓サイズ □ 「同じ番号の ACK が続いて来た」(重複 ACK, duplicateack)は 1Mbit (1250 バイトパケットであれば 100 個)• 例:• 1 パ ケット か ら は じ め て 1 ず つ 増 加 さ せ た ら 、
100RTT(10 秒) たたないとバランス点まで来ない→
遅すぎ• じゃあ 50 パケットから始めるか?
は致命的に大きい□ Jacobso 解法:• 受信側にパケットが到着したが喪失パケットがある
ため番号が進まないと分かる• パケットの経路が 1 つでないため追い越す場合もあるが実際にはまれ→ 遅いリンクに• そこで TCP では 3 つ重複 ACK があったらその番号のパケットを再送 (fast retransmission)

線形と定数倍の両方をまぜる• その場合も喪失を仮定するので混雑窓サイズを半分にして slow start• リンク確立→混雑窓は小さい初期値として 4 セグ
メントに (RFC399) →到達して (タイムアウトなし• 1RTT 後に喪失パケットが ACK されたらその先のパケットが送られる

で)ACK が帰ってきたら、1 つ帰るごとにもう 1 セグ
メント増やす→ RTT ごとに倍々になっていく• これは slow start と呼ばれるが倍々なので全然 □ こ こ ま で の 混 雑 制 御 の 様 子 → 図 6-46 (1988 年 のslow ではない (図 6-44)
4.2BSD-Tahoe リリースに搭載されたものがこれ)• これを見ると、常に混雑窓サイズは現在送られつつ• セグメントは 1KB。最初混雑窓は 64KB だがタイムアウトのため 32KB に減少させ、1 パケットから slowある (ACK が来ていない) パケットの数に一致• 連続して送ったパケットの間隔は遅いリンクがあると開いている (ack clock) →これの間隔を守って送る

start、32 で 1 ずつ増加
• ラウンド 13 のセグメントが再び喪失し、3 重複 ACK□ 倍々で増やすので速やかにネットワークの容量にぶつで検出されて 20KB で再度 slow start、以下これがかる

繰り返される2• TCP-Tahoe(再送タイマーも適切な値) により混雑崩 □ TCP そのものに対する改良 2 --- ECN壊が回避された• ECN(explicit congestion notification) --□ Jacobson はさらに改善できると認識
IP の機能• これも接続時にオプションで合意すれば使える →• 最初の再送のとき、混雑窓サイズは大きすぎるが、適IP ヘッダに ECN 使用のフラグを立てる

切な ack clock で進んではいる→重複 ACK が来るた

• ルータは混雑が近づいている場合には ECN ビットを立てる

び、パケットが 1 つ到着したと分かる→ネットに残っているパケットが見積もれるを数え、残っているパケットが新たな (半分にした)• 受信側は ECN が立っていたら ECE(ECN Echo) ビットを立てたセグメントを返送

しきい値より下がったら以後の重複 ACK に対応して• 送信側は CWR(Congestion Window Reduced) ビッ• fast recovery:

重複 ACK(最初の 3 連続を含む)

1 パケット送信する

トを立てたセグメントで応答• fast retransmission か ら 1RTT た つ と 喪 失 パ
ケット が ACK さ れ て 重 複 ACK は 止 ま る → fast

• 送信側の動作は重複 ACK の場合と同じだが、まだパケットロスは出ていないので再送など必要なく有利

retransmission を終わって 1 ずつ増加

← RFC3168、まだ広まってない□ fast retransmission により、再度の slow start を回避できる

5.11

The Future of TCP• ただし 2 つ以上喪失した場合はやはり slow start □ TCP はインターネットの担い手として広く使われて来たになる• 広い範囲のネットワークでよい性能、細かな改良が• 通常の場合は slow start が回避され、のこぎり状続いている→ これからもたぶんそうだが。話題が 2に進む (図 6-47)
つ• 1990 の 4.3BSD-Reno に 搭 載 。TCP-Reno は□ TCP は全てのプログラムが欲するトランスポートセマン

TCP-Tahoe + fast recovery

ティクスを提供しているわけではない• これによりほとんどの時間、混雑窓サイズは最適値近辺で推移• レコードバウンダリのあるメッセージが欲しい人も• この基本方式で 20 年以上 (30 年以上?) 進んで来ていいるる (曖昧さの除去とかチューニングとかはあったが)• 複数の通信を束ねたいという人もいる (Web とか)□ いくつかの実装の改良• ネットワーク上の経路をもっと制御したい場合もある• 2 つ以上のパケット喪失に対する改良 (TCP-NewReno, □ 現状ではこれらのミスマッチの解消はアプリケーション
RFC3782)任せ• い く つ か 別 バ ー ジョン:

CUBIC TCP(Linux)、

Compound TCP(Windows)• →少し違うインタフェースを持つものの提案• SCTP(Stream Control Transmission Protocol,
RFC4980)□ TCP そのものに対する改良 1 --- SACK

• 重複 ACK から喪失を推測するところが複雑 (最終番号では情報不足)• STP(Structured Stream Transport)• しかし、これまでうまく動いて来たものを変えるこ• SACK(selective ACK) --- 受信ずみのバイト範囲を 3 組まで通知 →これを見れば適切な再送と伝送中とに抵抗もある□ 混雑の問題→これまでので解決されたというわけではパケットの正確に見積もりが可能ない• 接続時に SACK 可能とのオプションを交換すると使え• スピードが速くなるとパケットロス率は非常に小さるようになる

い必要• 実際に使うようすは図 6-48

• 例:

• SACK の情報はあくまでもオプションで、無しでもこれまで同様動作

速度 1Gbps、RTT 100ms、1500 バイトパケッ

トだと、パケットロスはおおよそ 10 分に 1 回 (ロス率 2*10**-8) でないといけない• しかしこれがあると再送や見積もりが正確になる →広く実装
3• これでは小さすぎて混雑シグナルとして有効に機能しない• 他の原因によるロスによって撹乱されてしまう• 今のところは問題になっていないが、さらにネットが速くなると分からない• 別の方法が多く研究されている。喪失ではなく RTTの変化で検出とか← FAST TCP

4