工学部第二部 情報通信工学科 4年 宮川 湧太郎
近年のインターネットを含むコンピュータネットワークでは、高速、広帯域な回線を必要とするコンテンツの普及などによって、ネットワーク帯域の公平かつ効率的な利用が求められるようになってきた。その中で主に用いられているプロトコル群として、TCP/IPが挙げられるが、ネットワーク層のプロトコルであるIP(インターネット・プロトコル)は、データの送受信を100%保障はしないものであり、これを補うために上層のトランスポート層でデータを保障するTCP(トランスミッション・コントロール・プロトコル)が用いられている。ネットワーク帯域の公平かつ効率的な利用にはデータの保障を請負うTCPの輻輳制御アルゴリズムが大きく影響しているため、本研究ではNS2(Network Simulator Version.2)を用いてTCP各バージョンの輻輳制御の特徴を比較することを目的とする。そのための事前知識として、TCPの歴史と現在のTCPに関する話題をこの章で扱う。
TCP(Transmission Control Protocol)は1974年に発表され、それまでARPANETで使用されていたNCPとは違い回線の信頼性を仮定せずに送受信者の間で信頼性を確保するというものである。1978年にはTCPから経路制御部分だけをIP(Internet Protocol)として独立させることになり、それまでARPANETの通信をすべて制御していたひとつのプロトコルがトランスポート層のTCP、ネットワーク層のIPの2階層から成り立つように定義された。一般的に言われているTCP/IPはこれらの組み合わせを表す造語である。初期のTCPは輻輳制御機能が搭載されておらず、1980年には輻輳発生時の連続的な再送要求によって起こる輻輳崩壊が指摘された。この輻輳崩壊の指摘をきっかけとして、1980年後半には『エンドノード主体による輻輳制御アルゴリズム』が考案され、1990年後半には『中継ノード主体による輻輳アルゴリズム』が考案された。そして現在は、『エンドノードと中継ノードの両方』から輻輳制御を行う試みが進められている。 現在、数多くの輻輳制御方式が研究、利用されているが、代表的なものとしてTahoe、Reno、NewReno、Vegasがあげられる。
近年、ギガビット・イーサネットや高速無線LAN(IEEE802.11n)に代表される物理層の進化により、ネットワークの帯域幅は増大の一途をたどっている。そのため高速なデータ転送が可能になったが、従来のTCPでは広帯域ネットワークにおいて満足いくスループットが得られないという問題点が浮上してきた。これは伝播遅延と適切でないウィンドウサイズの影響が大きくと言える。ウィンドウサイズが小さいと、一度に送れるパケットの送信量が少なくなる。そのため、1セッション内での送信回数は増加する。そして、1セッションの転送の合計時間は『伝播遅延時間』+『データ転送時間』×『送信回数』かかる。1回の送信ごとに『伝播遅延時間』がかかるため、通信時間内の伝播遅延の合計は送信回数×伝播遅延となる。よって、1回の送信ごとにかかる伝播遅延も送信回数分掛かることになり、1セッションにおける時間の中の伝播遅延時間の割合が多くなってしまう。この解決方法として、TCPの最大ウィンドウサイズを64KB以上に拡張し、送信回数を減らすことにより、伝播遅延時間の合計を減らすといった対策がとられた。これはスケールオプションを呼ばれるもので、最大ウィンドウサイズを1GBまで拡張できるため当面はこのオプションで広帯域ネットワークに対応はできるようになった。この例をもってウィンドウサイズの制御は帯域の有効的な利用に深く結び付いているといえる。
この章ではTCPの輻輳制御について述べる。
TCPは、OSI参照モデルにあてはめると、トランスポート層のプロトコルである。インターネットを利用する上ではIPに次いで重要なプロトコルである。TCPにはUDP(User Datagram Protocol)とは違い輻輳制御の機能が実装されている。今回は複数のバージョンがあるTCPの輻輳制御にフォーカスする。輻輳制御方式には、大きく分けて@ロスベース方式、A遅延ベース方式の二種類があり、近年はBハイブリット方式(@とAの複合型)が登場し注目されている。
Tahoeは1988年ごろから利用されているTCPである。特徴としてはスロースタート段階と輻輳回避段階に分けられるウィンドウサイズ制御と、Fast Retransmitアルゴリズムといった高速再送アルゴリズムを採用した点にある。輻輳制御の流れを図1の輻輳ウィンドウサイズの変化のグラフを用いて説明する。まず、閾値(以下ssthresh)を定めるために、輻輳が起こるまでパケット送信をおこない、輻輳が起こった時点の輻輳ウィンドウサイズの2分の1(cwnd/2)をssthreshと定める。それ以降は、ssthreshまでスロースタート段階で、ACKを受け取るごとに1ずつにウィンドウサイズを指数的に増加させて、ssthresh以上になると輻輳回避段階に移行し輻輳ウィンドウサイズ分の1(1/cwnd)ずつ線形的に輻輳ウィンドウサイズを増加させる。この輻輳回避段階で再び輻輳が起こった場合は輻輳ウィンドウサイズを最小の1にまで落としてスロースタート段階からおなじ工程を繰り返すようになっている。
Fast Retransmitアルゴリズムはロストしたパケットを再送タイマのタイムアウトを待たずに、迅速にパケットを再送するアルゴリズムである。受信側ノードから再送要求する確認応答パケット(ACKパケット)が重複して3つ到着した場合はデータパケットが破棄された可能性が高いと判断し再送タイマのタイムアウトを待たずに、当該パケットを迅速に転送する。その後はスロースタート段階に移行する。
Renoは1990年に登場したバージョンである、これは前項のTahoeの輻輳回避アルゴリズムに改良を加えたFast Recoveryアルゴリズムを採用したものである。Tahoeの場合、輻輳が起きた場合に輻輳ウィンドウサイズを1まで落として、スロースタート段階から開始するため、速度を落としすぎてしまうといった欠点があった。しかし、Fast Recoveryアルゴリズムは、輻輳が発生したときの輻輳ウィンドウサイズの2分の1(cwnd/2)の値をssthreshに設定し、後に輻輳が発生した場合は輻輳ウィンドウサイズを1まで下げずにssthreshから輻輳回避段階に入るアルゴリズムになっている。これにより過剰な輻輳ウィンドウサイズの減少を避けられるため高速な転送が可能となった。
New Renoは1996年に登場したバージョンで、前項のRenoのFast Recoveryアルゴリズムのパケットロスト率の高い場合に対してのアルゴリズムの不具合を修正したものである。RenoのFast Retransmitアルゴリズムでは、1つのパケットが破棄されたときにでも再送信モードに入ってしまうため、このとき新しいパケットの送信が停止される。このようなパケットの破棄が密集して発生すると、スループットが極端に落ちてしまうといった不具合があった。NewRenoでは、この不具合を解消し、1回の再送信モードで複数のパケットを再送信するように改良された。
VegasはこれまでのTCP輻輳アルゴリズムと違い、詳細な通信経路の状態を推測する機能が搭載されて、混雑の具合に応じた転送速度の調節が可能になっている。通信経路の状態の把握にはラウンド・トリップ・タイム(以下RTT)を利用する。Vegasの輻輳制御アルゴリズムはデータ転送しながらRTTを計測し、Actual ThrougputとExpected Througputの2つのスループットを比較する。Actual Througputは実際の転送した際にかかった計測値であり、Expected Througputは転送結果から推測値である。これらの値を比較し、『Actual>Expected』になった場合はネットワークが混んできたとみなして輻輳ウィンドウサイズを1減らし転送速度を落とす。値が『Actual<Expected』になった場合はネットワークが空いてきたとみなして輻輳ウィンドウサイズを1増やして転送速度をあげる。そして、『Actual=Expected』の場合はネットワークが安定しているとみなして転送速度を維持する。
ハイブリット方式のCTCPはWindows系OSがVegasに移行するための前準備として登場した。登場した経緯としてRenoとVegasの競合問題が挙げられる。VegasはReno、New Renoなど競合することにより、適切なウィンドウサイズの調整が行うことができず、RTTの増加とウィンドウサイズの低下によるスループットの低下が指摘されている。このように、VegasはReno、New Renoに帯域を奪われてしまうため、公平な制御が行われないといった欠点を有しているが、CTCPでは、この欠点を補うためにネットワークの環境を判別しVegasとNew Renoの輻輳制御を切り替える機能を有していので競合を避けることが可能になっている。 ちなみに、CTCPは2006年に発売されたWindows Vistaに初めて搭載されたが、Vegasモードでウィンドウサイズが大きくならないというバグが発見され問題になった。そのため、画期的な採用であったはずのCTCPのデビューはMicrosoftの失態によって良いイメージが残らなかったのが皮肉な話である。
この章では実験で使用するネットワークシミュレータと実験方法について解説する。
NS2(Network Simulator Version.2)は米国DARPAの研究プロジェクトVINT(Visual InterNet Testbed)の研究成果の一つで、インターネットの新しい技術の開発を促進するために開発されたものである。NS2はOPNETなどの他のネットワークシミュレータとは異なり完全無料かつパブリックドメイン、オープンソースのソフトウェアである。そのためNSはネットワーク研究のための基本ツールとしての地位を確立している。
そのため、コマンドライン、テキストベースといったような複雑かつ煩雑なユーザーインタフェースであったり、階層モデルのシミュレートができなかったりと、有償のソフトウェアと比べてしまうと幾分劣る点があるが、ネットワーク層、トランスポート層、無線ネットワークのシミュレーションが比較的簡単にできるようになっているため、教育機関や研究機関で多く使われている。
NS2は大きく分けてネットワークシミュレータのnsとビジュアライザのnamの2点から構成され、nsでシミュレートしたテキストベースのシミュレーション結果をnamでネットワーク図やパケットの流れを視覚化することが可能になっている。nsでシミュレーションを行うには、コンポーネントをC++で記述し、ネットワークトポロジやノードの定義をOtcl言語で記述するスタイルとなっている。これは実行速度の速いC++と、単純な記述方式のOtclのメリットを組み合わせて高速な実行と手軽なネットワーク定義を実現するためである。
今回の実験のシナリオは以下の図3、表1、表2を用いて解説する。
シミュレーションは図5で示すように5つのノードと4つのリンクから構成される。ノードとリンクは以下の表1のように定義する。
ノード、リンク名 | ノード、リンク定義 |
---|---|
n0:送信ノード | n0-n4間のコネクションを確立、552KBのTCPパケットを送信 |
n1:送信ノード | n1-n4間のコネクションを確立、1Mbpsの固定レート(CBR)で1000KBのUDPパケットを送信 |
n2:送信ノード | n2-n4間のコネクションを確立、 1Mbpsの固定レート(CBR)で1000KBのUDPパケットを送信 |
n3:中継ノード | 中継(ルータ)、キューリミット:20 |
n4:受信ノード | n0のTCP Sinkエージェント、n1、n2からのCBRパケットの受信 |
n0-n3リンク | n0-n3間、全二重、1Mbps、伝播遅延2ms、ドロップテール型のリンクを定義 |
n1-n3リンク | n1-n3間、全二重、1Mbps、伝播遅延2ms、ドロップテール型のリンクを定義 |
n2-n3リンク | n2-n3間、全二重、1Mbps、伝播遅延2ms、ドロップテール型のリンクを定義 |
n3-n4リンク | n3-n4間、全二重、2.5Mbps、伝播遅延5ms、ドロップテール型のリンクを定義 |
シミュレーションは以下の表2の順序で実行される。
時間(sec) | イベント |
---|---|
0.00 | シミュレーション開始 |
1.00 | n0がTCP通信を開始 |
4.01 | n1がUDP送信開始 |
5.01 | n2のUDP送信開始 |
10.00 | n0,n1,n2送信停止 |
10.10 | シミュレーション終了 |
今回の実験は意図的に輻輳を発生させるために、node3から左側の合計の帯域が3Mbps、右側の帯域を2.5Mbpsとした。また、node0にTCPのエージェントを実装。node1、node2、node3-node4間のリンクに負荷をかけるためにUDPエージェントを実装し、1Mbpsの固定ビットレート(CBR)の通信を行う。順番としては1.00秒の通信開始から4.00秒までの間はTCPの通信はnode3-node4間の通信で帯域を占有し大きな輻輳が起こらずに通信を行い、4.01秒にはnode1がUDPパケットを送信し、5.01秒にはnode2がUDPパケットの送信を開始する。このときにnode0から送信されたTCPのパケットが輻輳により破棄されると仮定しシミュレーションを実行する。
上記のシナリオをNS2でシミュレーションを行うために、以下のプログラムを記述した。
set ns [new Simulator] ;# オブジェクトの生成
# フローに色を定義(namで表示時に使用)
$ns color 0 blue
$ns color 1 red
$ns color 2 yellow
# ノードの定義
set n0 [$ns node]
set n1 [$ns node]
set n2 [$ns node]
set n3 [$ns node]
set n4 [$ns node]
# 出力先の定義
set tf [open tahoe.tr w] ;# NAM用トレースファイルを書き込み属性で開く
$ns trace-all $tf
set winfile [open cwnd_tahoe.tr w] ;# 輻輳ウィンドウのトレースファイルを書き込み属性で開く
set nf [open tahoe.nam w] ;# NAMファイルを書き込み属性で開く
$ns namtrace-all $nf
# リンクの定義
$ns duplex-link $n0 $n3 1Mb 2ms DropTail ;# 全二重,node0-node1間,1Mbps,遅延2ms,DropTali型のリンク ※1
$ns duplex-link $n1 $n3 1Mb 2ms DropTail ※1
$ns duplex-link $n2 $n3 1Mb 2ms DropTail ※1
$ns duplex-link $n4 $n3 2.5Mb 5ms DropTail ※1
# n3のqueueの定義
$ns queue-limit $n3 $n4 20 ;# リンクn3-n4間の最大キューサイズを定義する。
# nam上での表示位置の定義
$ns duplex-link-op $n3 $n0 orient left-up
$ns duplex-link-op $n3 $n1 orient left
$ns duplex-link-op $n3 $n2 orient left-down
$ns duplex-link-op $n4 $n3 orient left
# n4-n3間のキューをモニタリングする
$ns duplex-link-op $n4 $n3 queuePos 0.5
# TCP0のコネクションの定義
set tcp0 [new Agent/TCP] ※2
$ns attach-agent $n0 $tcp0 ;# n0にTCPエージェントを実装
set sink0 [new Agent/TCPSink]
$ns attach-agent $n4 $sink0 ;# n4にTCPSinkエージェントを実装
$ns connect $tcp0 $sink0 ;# n0-n4間のピア接続を確立
$tcp0 set fid_ 0 ;# tcp0のフローIDを0に定義
$tcp0 set window_ 8000 ;# 最大ウィンドウサイズ
$tcp0 set packetSize_ 552 ;# パケットサイズを552KBに定義
$tcp0 trace cwnd_ ;# 輻輳ウィンドウをトレース
# $tcp0 attach $winfile ;# 輻輳ウィンドウのトレース結果をwinfileに出力
set ftp0 [new Application/FTP] ;# FTPトラフィックの生成
$ftp0 attach-agent $tcp0 ;# FTPトラフィックをtcp0(node0)に実装
# UDP1のコネクションの定義
set udp1 [new Agent/UDP] ;# UDPエージェントの定義 ※3
$ns attach-agent $n1 $udp1 ;# node1にUDPエージェントの実装
set null [new Agent/Null] ;# UDP Nullエージェントの定義
$ns attach-agent $n4 $null ;# node4にUDP Nullエージェントの実装
$ns connect $udp1 $null ;# UDPエージェントとNullエージェントの接続
$udp1 set fid_ 1 ;# フローIDを1に定義
set cbr1 [new Application/Traffic/CBR] ;# CBRトラフィックの生成
$cbr1 attach-agent $udp1 ;# UDPエージェントにCBRトラフィックジェネレータを実装
$cbr1 set type_ CBR ;# cbr1が生成するトラフィックをCBR(固定レート)に設定
$cbr1 set packet_size_ 1000 ;# パケットサイズを1000KBに設定
$cbr1 set rate_ 1mb ;# 1Mb/sのレートでトラフィックを生成
$cbr1 set random_ false ;#
# UDP1のコネクションの定義
set udp2 [new Agent/UDP] ※3
$ns attach-agent $n2 $udp2
set null [new Agent/Null]
$ns attach-agent $n4 $null
$ns connect $udp2 $null
$udp2 set fid_ 2
set cbr2 [new Application/Traffic/CBR]
$cbr2 attach-agent $udp2
$cbr2 set type_ CBR
$cbr2 set packet_size_ 1000
$cbr2 set rate_ 1mb
$cbr2 set random_ false
# スタート時間
$ns at 1.0 "$ftp0 start" ※4
$ns at 4.01 "$cbr1 start" ※4
$ns at 5.01 "$cbr2 start" ※4
# 終了時間
$ns at 10.0 "$ftp0 stop" ※4
$ns at 10.0 "$cbr1 stop" ※4
$ns at 10.0 "$cbr2 stop" ※4
#輻輳ウィンドウの変動記録
proc plotWindow {tcpSource file} {
global ns
set time 0.1
set now [$ns now]
set cwnd [$tcpSource set cwnd_];
puts $file "$now $cwnd"
$ns at [expr $now+$time] "plotWindow $tcpSource $file"
}
$ns at 0.1 "plotWindow $tcp0 $winfile"
$ns at 10.1 "finish"
# 終了後処理のプロシージャ
proc finish {} {
global ns tf nf winfile
$ns flush-trace
close $tf ;# トレースファイルを閉じる
close $nf ;# nam用トレースファイルを閉じる
close $winfile ;# 輻輳ウィンドウトレースファイルを閉じる
# namを実行する
puts "running nam..."
exec nam tahoe.nam &
exit 0
}
$ns run
上記のプログラムの要点の解説を行う。
※1では各ノード間のリンクの定義をしている。リンクの定義は、始点ノード番号、終点ノード番号、帯域幅、伝播遅延、ドロップ形式を定義することができる、パラメータは表1で明記しているように、node0-node3間、node1-node3間、node2-node3間のリンクは全二重、1Mbps、遅延2ms、ドロップテール型のリンクを定義した。node3-node4間のリンクは全二重、2.5Mbps、遅延5ms、ドロップテール型のリンクを定義した。
※2ではnode0のエージェントの定義を行っている。今回、例に挙げたプログラムは、Tahoeでの通信を行う場合のものであるため、Reno、NewReno、Vegasで通信を行う場合は ※2 の行を以下のように書き換える。
set tcp0 [new Agent/TCP/Reno]
set tcp0 [new Agent/TCP/Newreno]
set tcp0 [new Agent/TCP/Vegas]
※3では、ネットワークに負荷をかけるためのUPD/CBRトラフィックを定義した。1Mbpsの固定レートでトラフィックを生成し、1000KBのUDPパケットを送信する。
※4では、各ノードの通信開始時間と通信終了時間の定義を行っている。今回は表2のタイムテーブルに従って、TCPのFTPフローを0.01秒、UDPのCBRフローを4.01秒、5.01秒に開始して、すべての通信を10.01秒に終了させる。
各バージョンのTCPによるシミュレーション結果を以下の統計データにて報告する。
以上の図6、図7のグラフを用いてTahoeの実験を解説する。図6のスループットの変化(以下Throughput)からnode1のUDP/CBRの通信が始まる4.01秒前後は、スロースタート段階以外は、ほぼリンク速度を使い切っていることが確認できるが、5.01秒にnode2のUDP/CBRの通信が始まった後に輻輳が発生し、輻輳ウィンドウサイズ(以下cwnd)、Throughputの低下が確認できる。図7のシーケンスナンバーの累積変化(以下sqno)も5.01秒まではスロースタート段階以外、cwndの低下は見られず、5.01秒以降のnode2のUDP/CBR通信が開始後にcwndの大きな低下が8回発生し、Throughputも共に下げたことが確認できる。
以上の図8、図9のグラフを用いてRenoの実験を解説する。こちらもTahoeと同様に図8のThroughputからnode1のUDP/CBRの通信が始まる4.01秒前後は、スロースタート段階以外、ほぼリンク速度を使い切っていることが確認できるが、5.01秒にnode2のUDP/CBRの通信が始まった後に輻輳が発生し、cwnd、Througputの低下が確認できる。図9のsqnoも5.01秒まではスロースタート段階以外、cwndの低下は見られず、5.01秒以降のnode2のUDP/CBR通信が開始後にcwndの大きな低下が9回発生し、Througputも共に下げたことが確認できる。
以上の図10、図11のグラフを用いてNew Renoの実験を解説する。こちらもTahoe、Renoと同様に図10のThroughputからnode1のUDP/CBRの通信が始まる4.01秒前後は、スロースタート段階以外、ほぼリンク速度を使い切っていることが確認できるが、5.01秒にnode2のUDP/CBRの通信が始まった後に輻輳が発生し、cwnd、Througputの低下が確認できる。図11のsqnoも5.01秒まではスロースタート段階以外、cwndの低下は見られず、5.01秒以降のnode2のUDP/CBR通信が開始後にcwndの大きな低下が9回発生し、Througputも共に下げたことが確認できる。
以上の図12、図13のグラフを用いてVegasの実験を解説する。こちらは今までの実験結果とは異なり、スロースタート段階で一度、ウィンドウサイズの低下が発生した以外は5.01秒までcwnd、Throughput共にほぼ一定値を保ち安定した通信を行い、5.01秒以降は大きくcwnd、Throughputともに下げたが、ほぼ一定値を保ったことが確認できる。図13のsqnoも5.01秒以降を境に増加量は鈍化するが、常に直線的に増加していることが確認できる。
前項の実験結果から各バージョンの輻輳制御には特徴があることが分かる。データを以下の表3にまとめて解説する。
Tahoe | Reno | New Reno | Vegas | |
---|---|---|---|---|
ドロップされたパケット(Packet) | 28 | 29 | 30 | 0 |
送信されたパケット(Packet) | 1418 | 1419 | 1462 | 1475 |
平均スループット(Kbps) | 649.64 | 637.38 | 659.95 | 723.24 |
歴史的に古いものから順番にシミュレーションを行い、結果をまとめると表3のようになった。その結果、Tahoeとそれを改良したRenoの総送信パケット数の差は、ドロップパケット数、送信パケット数共に差は1パケットで、平均スループットに至ってはRenoが劣る結果となった。これは第2章でも述べているRenoのFast Retransmitアルゴリズムの不具合によるもので、Renoは送信したパケット数は多いものの、図9の負荷発生後のシーケンスナンバーの変動を見て分かるが、パケットロスが起こった時の再送モードによってスループットが低下していると言える。また、改良型のNew RenoはFast Retransmitアルゴリズムの不具合が解消されているため、負荷発生後のシーケンスナンバーの変動もスムーズで、送信されたパケット数、平均スループット共に向上している。Vegasに至っては送信パケット数、ドロップパケット、平均スループットも最も良い結果をのこした。図12、図13を他のバージョンと比べるとVegasは輻輳ウィンドウ、平均スループット、シーケンスナンバーの累積変化の3つとも直線的な変化であることが分かる。これは、限られた帯域を有効的に使用している結果と言える。
今回は、NS2を使って主要なTCPの輻輳制御方式を観察した。TCPの礎を築いたTahoe、Tahoeを改良したReno、NewReno、遅延ベース方式という概念を確立したVegas。今回の実験では最も帯域を有効的に使える輻輳制御方式はVegasという結果が出た。Vegasは誕生から数年経過しているが、現状ではあまり普及していない。その理由として挙げられているのが、現在Windows系のOSで主流のReno、NewRenoと共存した環境では、VegasのRTT増加、輻輳ウィンドウサイズの減少による、スループットの低下が発生することが指摘されていることが要因と考えられる。このように輻輳制御方式の違いによる不公平が起るようであれば、効率的な輻輳制御方式であっても普及にまでは至らないということがVegasの例をもって言えるだろう。しかし、Windows Vista以降はCTCP(それに実装されたVegas)を標準サポートする事になると思われるため、段階的にVegasが標準の輻輳制御方式となっていくと考えられる。今後、Vegasへの切り替わりの懸け橋としてハイブリット方式のCTCPが大きな役目を果たすと言える。