生産と技術

第64巻 第４号（2012）

インターネットの輻輳制御技術
長谷川

技術解説

剛＊

Congestion control mechanisms in the Internet
Key Words：Internet, TCP, Congestion Control

はじめにクセスネットワーク環境の劇的な進歩にともない、そのような環境における TCP の性能が着目されるTransmission Control Protocol（TCP）[1] は現在ことが多くなり、様々な問題が指摘されつつある。のインターネットにおけるトランスポート層プロト

例えば、ネットワーク輻輳に加えてリンクエラーにコルとして最も多くのネットワークアプリケーショよりパケット廃棄が発生、および変動する無線ネッンが利用しており、TCP トラヒックは現在のイントワークや、端末の移動によりエンド間の経路が通ターネットトラヒックの大部分を占めている。また、

信中に変化し、スループット低下が発生するモバイ

インターネットは様々な種類のネットワークを取りル環境などが挙げられる。これらを始めとするさま込むことによって大規模化し、指数関数的な拡大をざまな問題を解決するために、これまでに多くの続けている [2]。その結果、TCP が誕生した 1970

TCP に対する改善が行われてきた。

年代当初には想定することができなかったネットワ

また、近年のネットワークの高速化により、TCPーク環境が発生している。TCP において最も重要コネクションが利用できるネットワークの帯域遅延な機能はネットワーク輻輳を回避・検知・解消する積（リンク帯域とエンドホスト間の伝播遅延時間の輻輳制御機構 [3] であり、多様化するネットワーク積）が飛躍的に増大している。例えば、ラウンドト環境において安定的に TCP による通信を行なうこリップ時間（RTT）が約 130 msec となる太平洋をとができる大きな要因である。

狭んだ 2 台のエンドホスト間の最低帯域がTCP がどのようなネットワーク環境においても100 Mbps から 1 Gbps 程度である、という環境も一安定的な通信を行なうことができる、というロバス般に利用可能となりつつある。このような高速・高ト性は、逆に言うと、個々のネットワーク環境にお遅延ネットワーク環境において、現在多くの OS のける性能の最適化の観点では劣る場合があるという

TCP 実装が基本としている TCP Reno を用いると、ことを意味する。これは、インターネットがさまざその輻輳制御方式の特徴が原因となって、リンク帯まなネットワークを IP というルーティングプロト域を十分使うことができない、という問題が指摘さコルで接続しているという性質を鑑みると、止むをれている。これは、TCP Reno が旧来の低速ネット得ない性質であると考えられる。しかし、特に近年ワークを想定して設計されていること、またインタの光ファイバ技術や無線ネットワーク技術によるアーネットユーザがよりスループットなどの性能に敏感になっていることなどに起因していると考えられ＊

Go HASEGAWA
1974年3月生
大阪大学大学院基礎工学研究科博士前期課程修了（1997年）
現在、大阪大学 サイバーメディアセン
ター先端ネットワーク環境研究部門
准教授 博士（工学） 情報ネットワーク
TEL：06-6850-6864
FAX：06-6850-6868
E-mail：hasegawa@cmc.osaka-u.ac.jp

る。
本稿では、このような新たなネットワーク環境に対応するために行われてきた、TCP の輻輳制御機構に関する近年の研究動向について概説する。特に、無線ネットワーク環境、および高速・高遅延ネットワーク環境における従来 TCP の輻輳制御機構の問題点を整理し、提案されている改善手法について述べる。
− 28 −

生産と技術

1

TCP の輻輳制御方式

2

TCP はウィンドウサイズと呼ばれる、一度にネ第64巻第４号（2012）

無線環境における TCP 輻輳制御機構

2.1

問題点

ットワークに送出することができるデータ量を動的無線ネットワーク環境における TCP の性能評価制御することによって、ネットワークの輻輳制御をに関しては、数多くの研究がこれまでに行われてお行っている。TCP Reno の輻輳制御方式は、スローり、それらを通じていくつかの問題が明らかになっスタートフェーズおよび輻輳回避フェーズと呼ばれている。本節では、それらのうち、輻輳に無関係なる 2 つのフェーズから構成され、それぞれにおいてパケット廃棄、およびコネクション間の不公平性に輻輳ウィンドウサイズ（cwnd）の増加速度が異なる。

関して説明する。

スロースタートフェーズにおいては、1 つの ACK

無線ネットワークは有線ネットワークに比べて通パケットを受信するごとに輻輳ウィンドウサイズ信路のビットエラー率が非常に高く、無線リンクロを 1 パケット増加させる。一方、輻輳回避フェーズス、すなわち、ビットエラーが原因となるパケットにおいては、1 つの ACK パケットを受信するごと廃棄が頻繁に発生する。一方、TCP はパケット廃に輻輳ウィンドウサイズをその逆数分だけ増加させ棄を検出すると、それはネットワーク輻輳の徴候でる。すなわち、TCP Reno の輻輳ウィンドウサイズあると判断し、ウィンドウサイズを減少させることを wreno とすると、その更新アルゴリズムは以下のによって、自身のデータ転送速度を低下させる [3] 。

ように表すことができる。

したがって、無線ネットワーク環境における TCP

wreno｛←wreno ＋ 1
wreno ＋

1wreno（ wreno ＜ sreno ）（1）（ wreno sreno ）ここで、sreno は、TCP Reno がスロースタートフェ

データ転送において、無線リンクロスによってパケット廃棄が発生すると、不必要なウィンドウサイズの減少が発生し、スループットが低下する。
2.2

改善手法

ーズから輻輳回避フェーズに移行する時のしきい値

無線ネットワークにおける TCP 性能の改善に関

ssthresh である。送信側端末において ACK パケッする研究はこれまで多数行われており、無線基地局トを受信する度に上式が用いられることによって、との連携手法、送信側 TCP の改変手法、およびwreno ＜ sreno の場合には R T T ごとに cwnd が 2 倍にMAC 層と TCP/IP 層の連携に基づくクロスレイヤなり、wreno制御などが挙げられる。本章では、それらの中でもsreno の場合には R T T ごとに cwnd が1 だけ増加する。

特に、無線基地局の改変を必要とするものに関して、一方、パケット廃棄を検出した場合には、次式のように輻輳ウィンドウサイズを減少させる。

wreno｛←

利点と欠点を述べる。なお、送信側 TCP の改変手法は、無線基地局の改変が必要な方式に比べて、送信側 TCP の変更のみで実現することができるため、

wreno / 2 （重複 ACK ）1（タイムアウト）（2）

より導入が容易であると考えられる。が、得られる性能改善効果は、一般的に無線基地局の改変が必要な方式に比べて低くなる。

すなわち、TCP Reno はパケット廃棄を検出するまで輻輳ウィンドウサイズを増加させ続け、パケット2.2.1 無線基地局の改変をともなう手法廃棄をきっかけに減少させる。これは、TCP Reno

無線ネットワークにおける TCP 性能向上手法のがパケット廃棄の発生をネットワーク輻輳の指標と1 つとして、有線ネットワークと無線ネットワーク見なしていることに起因する。本稿ではこのようにの境界に存在する無線基地局を改変するものが挙げ

パケット廃棄をネットワーク輻輳の指標として用いられる。これは、有線ネットワークと無線ネットワる手法を loss-based 手法と呼ぶ。

ークの特性の違いが与える影響をそれぞれ局所化することによって TCP 性能を向上させるものである。
これらの手法は主に、基地局においてコネクション− 29 −

生産と技術第64巻 第４号（2012）（a）TCP コネクションの分割（b）TCP コネクションのスヌーピング
図 1：無線基地局の改変をともなう手法

分割を行なうもの、およびコネクション監視（スヌを、基地局から行なうことができるため、再送効率ーピング）を行なうものに分類される。図 1 に、無が向上する。

線ネットワークに存在する端末が受信側 TCP となる場合の、両方式の挙動を示す。

一方、文献 [4] などにおいて提案されているコネクション監視（スヌーピング）手法は、廃棄された

コネクション分割を行なう手法においては、通常パケットの基地局からの再送を、コネクション分割エンド端末間に 1 本設定される TCP コネクションを、を行なわずに実現する手法である（図 1(b)）。具体無線基地局において分割する（図 1(a)）。有線ネッ

的には、基地局に監視のためのエージェントを導入

トワーク側においては、有線側のエンド端末とのデし、通過する TCP コネクションのデータパケットを、ータパケットおよび ACK パケットのやり取りを無対応する ACK パケットが逆向きに通過するまでキ線側端末に代わって行なう。こうすることによって、ャッシュとして保存し、ACK パケットのシーケン有線ネットワークにおけるデータ転送速度が、無線ス番号を監視することによって、再送すべきデータネットワーク環境に影響を受けないようにすることパケットを決定する。また、重複 ACK パケットがができる。また、無線ネットワーク側においては、通過する際には、それを適宜削除することによって、発生するパケット廃棄を全て無線リンクロスに基づエンド端末からのパケット再送を抑制する。
これらの手法は、インターネットにおけるプロトくものと見なすことができるため、無線リンクロスによるパケット廃棄に対してはウィンドウサイズをコル設計の際の指針として従来考えられてきたエン減少させない、といった制御により、スループット

ドツーエンド原理 [5] に反するものであるが、近年低下を回避することができる。また、無線ネットワはオーバレイネットワークやファイアウォールシスークで発生したパケット廃棄に対するパケット再送テムなど、ネットワーク内においてセッションの切− 30 −

生産と技術第64巻第４号（2012）

図 2：TCP Reno の高速・高遅延環境における問題点

このような高速・高遅延ネットワークにおける断・中継を前提とするシステムが普及しており、導TCP Reno の問題点に対する数多くの改善手法が近入障壁は以前ほど高くはないと考えられる。

年提案されている。本章では、それらのうち主要な3高速・高遅延環境における TCP 輻輳制御機構ものを紹介する。それらの改善手法の多くは、TCPReno がパケット廃棄をネットワーク輻輳の指標と3.1問題点して判断しているのに対して（あるいはそれに加えTCP Reno を高速・高遅延ネットワーク環境におて）、別の指標を導入している。本章では新たに導いて用いると、大きなリンク帯域を十分使う程度の入している指標によって分類を行っている。また本

スループットを得ることができないという問題が指章では、特に指定しない限りは、輻輳回避フェーズ

摘されている [6]。図 2 に、送受信端末間のラウンにおける輻輳ウィンドウサイズの増減アルゴリズム

ドトリップ時間（R T T）が 100 msec、リンク帯域について説明する。なお、スロースタートフェーズが 10 Gbps であるような大きな帯域のリンク上で、に関しては、多くの改善手法が TCP Reno と同じア

パケット長が 1500 Byte である 1 本の TCP Reno コ

ルゴリズム（式 (1) の 1 行目）を採用している。また、ネクションを用いてデータ転送を行ったときの、輻輻輳回避フェーズにおいては、輻輳ウィンドウサイ

輳ウィンドウサイズの変化の様子を示す。この環境

ズがある値以下である場合には、TCP Reno と同じにおいてはリンク帯域を十分使う程度のスループッアルゴリズム（1 節）を用いることで、低速ネット

トを得るためには、パケット廃棄率が 2 × 10 − 10

ワーク環境における TCP Reno との親和性を確保し以下である必要がある [6]。これは現在の光ファイている手法も存在する。

バ技術では実現困難な性能である。また図 2 から、一度パケット廃棄が発生すると、輻輳ウィンドウサ

3.2 Loss-based 手法

イズが回復するまでに、40000 R T T（約 4000 秒）

3.2.1 HighSpeed TCP(HSTCP)[6]以上の時間を要することがわかる。これは、TCP

HSTCP は、高速・高遅延環境向けの改善手法とReno において 1 Gbps を超えるスループットを継続して比較的初期に提案された手法である。HSTCP的に得ることは現実的には不可能であることを表しは TCP Reno と同様、パケット廃棄のみをネットワている。この問題は、式 (1) からわかるように、輻

ーク輻輳の指標として利用するが、現在の輻輳ウィ輳ウィンドウサイズの増加の幅がラウンドトリップンドウサイズの大きさに合わせて、輻輳ウィンドウ時間（R T T）ごとに 1 パケットと非常に小さいにサイズの増加速度およびパケット廃棄検出時の減少もかかわらず、式 (2) に示すように、パケット廃棄幅を調整する。すなわち、HSTCP は現在の輻輳ウを検出した際にウィンドウサイズを 1/2 以下へと大ィンドウサイズが大きいほど、その増加速度を大ききく減少させるために、輻輳ウィンドウサイズがなくし、減少幅を小さくすることを意味している。こかなか大きくならないことに起因している。

れにより、HSTCP はネットワークの帯域遅延積の− 31 −

生産と技術第64巻 第４号（2012）

大きさに応じたウィンドウサイズの増加・減少速度場合にもすばやくネットワーク利用率を向上させるを用いることができる。

ことができる点が特長である。その反面、パラメー

しかし、このような TCP の改良手法は、TCPタαの適切な設定が難しいという欠点を持つ。

Reno に比べて積極的に輻輳ウィンドウサイズを増加させるため、そのようなプロトコルが TCP Reno

3.4 Hybrid 手法

コネクションと共存した場合、それらのプロトコル

FAST TCP に代表される delay-based 手法は、そは高いスループットを獲得する反面、共存するれが単独で用いられる場合にはスループット、公平

TCP Reno コネクションのスループットを低下させ性、収束速度などの面で優れていることが明らかにるという問題点がある。この問題に対する改善手法なっている。しかし、TCP Reno や HSTCP のようとして我々の研究グループでは gentle HighSpeed

な loss-based 手法と混在した環境においては、de-TCP 手法を提案している [7]。

lay-based 手法を用いるコネクションのスループットが低下するという問題が文献 [9] などにおいて指3.3

Delay-based 手法

摘されている。これは以下の理由による。混在環境

Loss-based 手法はネットワーク内でパケット廃においてネットワーク帯域が使い切られ、ルータバ棄が発生するまで輻輳ウィンドウサイズの増加を停ッファにパケットが蓄積し始めると、R T T が増加止しないため、理想的に動作した場合においても、する。その際、delay-based 手法は R T T の増加にと周期的なパケット廃棄の発生を避けることができなもない輻輳ウィンドウサイズを小さくするが、loss-い。一方、ルータの出力リンクにおいて高負荷時にbased 手法はパ ケット廃棄が発生するまで輻輳ウィパケットが蓄積されるバッファが FIFO 規律に従っンドウサイズを大きくし続ける。したがって、ボトている場合、バッファが一杯になりパケット廃棄がルネックリンクを両手法のコネクションが共有した発生する前に、そのリンクにおいてバッファリング

場合、delay-based 手法のコネクションは、loss-遅延が増大することが期待される。そこで、各パケbased 手法のコネクションに比べてスループットがットの R T T を監視し、その増大をネットワーク輻低下する。

輳の初期段階の指標として利用する手法（本稿ではこの問題に対し、delay-based 手法に loss-baseddelay-based 手法と呼ぶ）が提案されている。理想手法を組み合わせる Hybrid 手法が提案されている（例的に動作すると、loss-based 手法では避けることのえば Compound TCP [10] など）。これらの手法は、できないパケット廃棄を完全に回避することが可能

通常の delay-based 手法と同様に、R T T が増加してとなる。

おらずネットワーク帯域が使い切られていないと判断された場合には輻輳ウィンドウサイズを TCP

3.3.1

FAST TCP[8]Reno よりも大きく増加させる。さらに、輻輳ウィ

FAST TCP は TCP Vegas と同様に、観測されたンドウサイズの増加幅を TCP Reno 相当の部分と、最小の RT T である base RTT と現在の R TT であるそうでない追加部分に分けて管理する。その後、

RT T を利用し、以下の式にしたがって輻輳ウィン

RTT が増加し始めると、輻輳ウィンドウサイズの（大ドウサイズを増減させる。

幅な）増加を停止する。その後、TCP Reno と同じ

w fast←min {2 w fast ,増加幅で輻輳ウィンドウサイズを増加させ、loss-（（1 −γ）w fast ＋）｝

baceRTTw fast ＋α
RTT

based 手法を用いる（パケット廃棄の発生まで輻輳ウィンドウサイズを大きくし続ける）。すなわち、ネットワークの未使用帯域がある場合には、delay-αはパラメータであり、ネットワーク内滞留パケ

based 手法によっ てそれを高速に使い切るように動ット数の目標値に相当する。TCP Vegas と異なり、作し、輻輳時には loss-based 手法で動作することに目標となる輻輳ウィンドウサイズが現在値に比べてよって、共存する TCP Reno との公平性を維持して大きい場合には輻輳ウィンドウサイズを指数的に増いる。

加させるため、ネットワークの帯域遅延積が大きい− 32 −

生産と技術

3.5

その他の手法[4]

第64巻第４号（2012）

H. Balakrishnan, S. Seshan, and R. H. Katz,

その他、パケット廃棄が発生した時の輻輳ウィン

Improving reliable transport and handoff

ドウサイズを記憶し、その値を基にその後の輻輳ウ

performance in cellular wireless networks,ィンドウサイズの制御を行う CUBIC-TCP [11]（L-ACM / Baltzer Wireless Networks, vol. 1,

inux の標準プロトコル）、また ACK パケットの到pp. 469 − 481, Dec. 1995.

着間隔から現在のスループットを推測し、その値を[5]J. H. Saltzer, D. P. Reed, and D. D. Clark,輻輳ウィンドウサイズの制御に用いる TCP West-

End-to-end arguments in system design,

wood [12] などが提案されている。また、Explicit

ACM Transactions on Computer Systems,

Congestion Notification（ECN）[13] などを使って、vol. 2, pp. 277 − 288, Nov. 1984.

ネットワーク側から明示的に利用可能性帯域や輻輳

[6]

S. Floyd,

HighSpeed TCP for large conges-の有無などの情報を明示的に取得することで、エンtion windows,ド端末における輻輳制御の効率を高める検討も行わ(Experimental), Dec. 2003.

れている。

[7]

Request for Comments 3649

Z. Zhang, G. Hasegawa, and M. Murata,
Performance analysis and improvement of4

おわりに

HighSpeed TCP with TailDrop/RED routers,

I E I CE Transactions on Communications,
本稿では、TCP の輻輳制御機構に関する近年の研究動向を概説した。主に無線ネットワーク環境おvol. E88-B, pp. 2495 − 2507, June 2005.
[8]

C. Jin, D. X. Wei, and S. H. Low,

FAST TCP:

よび高速高遅延ネットワーク環境における問題点をmotivation, architecture, algorithms, performance,整理し、近年提案されている様々な改善手法を紹介

in Proceedings of IEEE INFOCOM 2004,

した。無線ネットワーク環境に関しては、今後もWiMAX や LTE など、従来とは異なる特性を持つネ

Mar. 2004.
[9]

G. Hasegawa, K. Kurata, and M. Murata, Analysis

ットワークが登場するため、これらのネットワーク

and improvement of fairness between TCP

において TCP を用いた場合の性能評価や、特性をReno and Vegas for deployment of TCP Vegas

考慮した輻輳制御機構の改善が求められると考えら

to the Internet, in Proceedings of IEEE ICNPれる。また、高速・高遅延ネットワーク環境向けの

2000, Nov. 2000.

改善手法に関しては、有効な改善手法が出揃った印[10] K. T. J. Song, Q. Zhang, and M. Sridharan,

象があり、今後は、どの改善手法が最も有効なのか、

Compound TCP: A scalable and TCP friendly

あるいは、条件に応じた輻輳制御機構の切り替え手

congestion control for high-speed networks,法などに関する研究が進むものと考えられる。

in Proceedings of PFLDnet 2006, Feb. 2006.
[11] I. Rhee and L. Xu,

参考文献

CUBIC: A new TCP

friendly high-speed TCP variant,in Proceed-ings of PFLDnet 2005, Feb. 2005.
[1]J. B. Postel,Transmission control protocol,[12] TCP WESTWOOD Home Page. available atRequest for Comments 793, Sept. 1981.
[2]

[3]

http://www.cs.ucla.edu/NRL/hpi/tcpw/.

Hobbes Internet timeline 10. available at[13] K. Ramakrishnan, S. Floyd, and D. Black, The

http://www.zakon.org/robert/internet/

addition of explicit congestion notification

timeline/.

(ECN) to IP,V. Jacobson,
trol,

Congestion avoidance and con-in Proceedings of ACM SIGCOMM 88,

pp. 314 − 329, Aug. 1988.

− 33 −

RFC 3135, Sept. 2001.