ns-3でTCPの輻輳制御アルゴリズムをシミュレートし，その動作をmatplotlibで可視化した．本記事は，2017年2月20日にQiitaに投稿した記事を，本サイト向けに再構成したもの．

はじめに

インターネット上のほとんどのトラフィックは，TCP（Transmission Control Protocol）によって制御されていると言われています．TCPの特徴の一つとして，送信ノードが各々輻輳¹制御アルゴリズム（Congestion control algorithm）に基づき，一度に送信するデータ量を調整する，という点があります．本記事では，ns-3で各アルゴリズムの動作をシミュレートし，NumPy + matplotlibで視覚化します．

TCPの輻輳制御アルゴリズムを比較するために，ns-3にはtcp-variants-comparison.ccというサンプルシナリオが用意されています．しかし，このシナリオスクリプトをそのまま使うと，本記事で注目するいくつかの変数をモニタ（ns-3では，トレースと呼びます）できない，という課題がありました．そこで，本記事では，シナリオスクリプトに任意のトレース情報を追加する方法を紹介します．

なお，本記事のソースコードは，全てGithubに置いてあります．

環境構築

ns-3 (Network Simulator 3)

ns-3は，オープンソースの離散事象ネットワークシミュレータです．研究や教育用途での使用を目的に開発されています．本記事では，下記の記事で構築した環境及びディレクトリ構成を前提とします．

• ns-3.26で始めるネットワークシミュレーション

python

本記事では，データ処理にNumPy，グラフ描画にmatplotlibを利用します．下記の環境で動作を確認しました．

• Python 2.7.11
• NumPy 1.10.4
• matplotlib 1.5.1

TCPにおける輻輳制御

概要

下図は，本記事で想定するTCP輻輳制御のイメージです．TCPの送信ノード（TCP Sender）は，受信ノード（TCP Receiver）からの確認応答（Acknowledgement，ACK）²³や信号往復時間（Round Trip Time，RTT）に応じて，データ量（DATA）を調整します．

厳密には，データ量の調整は，\(swnd=min(awnd, cwnd)\)という式で表現できます．ここで，\(swnd\)はTCP SenderがACK無しに送信可能なDATA数の上限値であり，\(cwnd\)はTCP Senderが自律的に調整するウインドウサイズ（Congestion window）であり，\(awnd\)はTCP Receiverから告知されるウインドウサイズ（Advertised window）です．上式の単位はセグメントと呼ばれ，1セグメントの大きさはTCP SenderとReceiverのネゴシエーションで決まります．\(awnd\)は非常に大きい値に設定されることが多いため，簡単のため，本記事では\(cwnd\)のみに注目します．

\(cwnd\)が大きいほど，たくさんのデータを一度に送ることができます．TCP Senderは，ACKやRTTから，Receiverとの間のネットワークの混み具合を予測して，自律的に\(cwnd\)の大きさを調整します．\(cwnd\)の調整戦略を，本記事では輻輳制御と呼びます．

輻輳制御は，輻輳状態⁴（Congestion state）と，アルゴリズム（Congestion control algorithm）という２つの要素によって決まります．輻輳状態は，OPEN，DISORDER，RECOVER，LOSS等，ネットワークの混雑状態を表します．アルゴリズムは，各輻輳状態における\(cwnd\)の更新方法を表します．

輻輳状態（Congestion state）

　本記事では，ns-3の実装（~/ns-3.26/source/ns-3.26/src/internet/model/tcp-socket-base.cc）に基づき，以下の4種類の輻輳状態を想定します．

• OPEN：いわゆる正常な状態です．アルゴリズムによっては，Slow start（SS）とCongestion avoidance（CA）という二種類のフェーズを持ちます．\(cwnd\)が閾値（Slow start threshold, \(ssth\)）より小さいときはSlow startフェーズに，大きいときはCongestion avoidanceフェーズに該当します．
• DISORDER：重複ACK（Duplicate ACK）を受信した状態です．パケットロスや受信順序の乱れ等の可能性があります．
• RECOVERY：3度重複ACK（Triple duplicate ACK）を受信した状態です．パケットロスを確信し，再送を開始します．
• LOSS：RTTが再送タイムアウト時間（Retransmission Time Out, RTO）より大きくなる，つまりACKのタイムアウトを検知した状態です．深刻な輻輳が生じている可能性があります．

輻輳制御アルゴリズム（Congestion control algorithm）

本記事では，ns-3の実装に基づき，以下の輻輳制御アルゴリズムを想定します．TypeIdとは，ns-3におけるアルゴリズムの呼び名のようなものです．ソースコードは，それぞれ~/ns-3.26/source/ns-3.26/src/internet/modelに格納されています．

例えば，最もメジャーな輻輳制御アルゴリズムの１つであるNewReno（Reno）は，各輻輳状態において次のように\(cwnd\)を更新します．

ここで，\(\mathit{inflight}\)は，ACKが返っていないDATAの総量を表し，\(smss\)は最小セグメントサイズを表します．また，簡単のためPartial ACKやFull ACK等は考慮していません．NewRenoの動作の詳細は，RFC6582等をご参照ください．

NewRenoは，輻輳の可能性が低いと思われるSlow startフェーズにおいては，\(cwnd\)を高速に増加させることでDATAを効率的に送信し，一方で輻輳の可能性が高いと思われるCongestion avoidanceフェーズにおいては，徐々に\(cwnd\)を上げることで急激な輻輳を回避する，という戦略を採用しています．

ACK受信を契機とする更新式は，1セグメント分のACKに対する更新式という点にご注意ください（私はここでハマりました）．例えば，\(cwnd=4\)のとき，TCP Senderは4セグメント分のDATAに対するACKを受信するため，上記の更新を4回行います．

なお，ns-3におけるTCPの実装は以下の3種類がありますが，本記事ではns-3ネイティブ（src/internet/model）で実装されているアルゴリズムのみを対象とします．つまり，LinuxでメジャーなCUBICや，WindowsでメジャーなCTCPは対象外です．これらについては，別途ご紹介できればと思っています．

• ns-3ネイティブ（src/internet/）
• NSC（Network Simulation Cradle）
• DCE（Direct Code Execution）

シナリオスクリプトの作成

本章では，もとにするサンプルシナリオtcp-variants-comparison.ccの解説と，その課題，そして修正版のmy-tcp-variants-comparison.ccをご紹介します．

もとにするサンプルシナリオ

ns-3は，TCPの輻輳制御アルゴリズムの比較用に，tcp-variants-comparison.cc というサンプルシナリオを用意しています（~/ns-3.26/source/ns-3.26/examples/tcp/にあります）．本シナリオスクリプトは，以下の変数の時変化をトレースし，ファイルに出力することが可能です．

• Cwnd：前記\(cwnd\)．ただし単位はバイトです．
• SsThresh：前記\(ssth\)．ただし単位はバイトです．
• Rtt：前記RTT．単位は[s]です．
• Rto：前記RTO．単位は[s]です．
• NextTx：TCP Senderが次に送信する予定のSequence numberです．
• NextRx：TCP Receiverが次に受信する予定のSequence numberです．
• InFlight：前記\(\mathit{inflight}\)．ただし，単位はバイトです．TCPの原理上，必ず\(cwnd\)以下になります．

以下では，本記事のテーマであるトレースに特にスポットを当て，ソースコードを解説します．

トレース用変数

58行目から70行目で，トレースに用いる変数の定義を行います．bool first*は，それぞれトレース対象の初期値を出力するか否かを表し，Ptr<OutputStreamWrapper> *Streamは，それぞれトレース対象をファイル出力するためのストリームを表し，uint32_t *Valueは，それぞれトレース対象の初期値を取り扱う際に一時的に使用される変数を表します．

トレース用コールバック関数の設定

73行目から145行目ではトレース用コールバック関数*Tracer()の定義を，147行目から202行目ではコールバック関数をトレース対象と紐付ける関数Trace*()の定義を行います．ここでは，トレース対象の１つであるBytesInFlightを例に解説します．

ns-3においては，ソースファイル（ns-3.26/source/ns-3.26/src/*/model/）中でAddTraceSource()された全ての変数を，シナリオスクリプト中でトレース対象として設定することができます．例えば，上記のBytesInFlightは，~/ns-3.26/source/ns-3.26/src/internet/model/tcp-socket-base.ccにおいてAddTraceSource()されています．ns-3は，トレース対象となった変数が更新される度に，その変数に紐付けられたコールバック関数を呼び出します．よって，トレース対象の設定には，コールバック関数の定義と，トレース対象とコールバック関数の紐付けが必要です．

コールバック関数として，上記InFlightTracer()のような関数がよく使われます．InFlightTracer()は，現在時刻（Simulator::Now ().GetSeconds ()）と，更新後の値（inFlight）を，都度出力する関数です．

トレース対象とコールバック関数の紐付け時には，上記TraceInFlight()にあるように，Config::ConnectWithoutContext(variable, MakeCallback(&func))という構文を使うことができます．ここで，variableは，トレース対象のObjectのパスを記載する必要があります．/NodeList/1/$$ns3::TcpL4Protocol/SocketList/0/BytesInFlightは，NodeList1番のノードにぶら下がる，SocketList0番のソケットの，変数BytesInFlightを意味します．

ns-3におけるトレース方法の詳細は，公式マニュアルの1.10節をご参照ください．

ネットワーク構成

204行目以降のmain()で，ネットワーク構成の設定を行います．詳細は公式マニュアルに譲り，ここではポイントのみ記載します．

上の図は，本シナリオのイメージ図です．TCP SenderとReceiverがそれぞれ１つずつの，簡単な構成を想定します．FTPライクな大量のデータ送信を模擬する，BulkSendHelperを利用します．IPパケットサイズは400バイトです．シミュレーション時間は，デフォルトで100秒間です．

コマンドライン引数

224行目から243行目で，コマンドライン引数を設定します．前回の記事でご紹介したように，CommandLine.AddValue()することで，コマンドライン引数を設定できます．

本記事では，特に下記のコマンドライン引数を利用します．

• transport_prot：輻輳制御アルゴリズムを指定できます．本記事では，シェルスクリプトを使って12種類全てを順番に指定します．
• tracing：トレーシングの有無を指定できます．デフォルトでFalseなので，Trueを指定します．
• duration：シミュレーション時間を指定できます．デフォルトの100秒は長すぎるので，本記事では20秒に設定します．
• prefix_name：出力ファイル名のプレフィックスを指定できます．デフォルト設定だと，~/ns-3.26/source/ns-3.26/直下に大量のファイルを吐いてしまうので，dataディレクトリ配下に吐くよう修正します．

トレース設定のスケジューリング

460行目から476行目で，上記TraceInFlight()等のトレース設定関数（コールバック関数と，トレース対象を紐付ける関数）をスケジューリングします．

ns-3では，Simulator::Schedule(time, &func, args,...)という構文で，time時にfunc(args,...)を実行するようスケジューリングできます．

しかし，なぜ地の文でTrace*()してはいけないのか，イマイチよくわからないです．おそらくオブジェクト生成のタイミングの問題の気がするのですが…．

tcp-variants-comparison.ccの課題

tcp-variants-comparison.ccは，非常によくできたシナリオスクリプトで，コマンドライン引数をいじるだけでかなり遊べます．しかし，我々が興味のある，ACKや輻輳状態をトレースできません！

幸いにも，最新のACKを表す変数HighestRxAckと，輻輳状態を表す変数CongStateは，それぞれtcp-socket-base.ccでAddTraceSource()されています．よって，シナリオスクリプトに少し変更を加えるだけで，これらをトレース対象に追加することができます．以下では，その方法をご紹介します．

新シナリオスクリプトmy-tcp-variants-comparison.cc

まず，もとにするtcp-variants-comparison.ccを~/ns-3.26/source/ns-3.26/scratchにコピーし，名前をmy-tcp-variants-comparison.ccに変更します．

ACKと輻輳状態をトレース対象に追加するため，トレース用変数の追加，トレース用コールバック関数の設定，およびトレース設定のスケジューリングを行います．

トレース用変数の追加

ACKトレース用のストリームackStreamと，輻輳状態トレース用のストリームcongStateStreamを追加します．

トレース用コールバック関数の設定

ACKトレース用のコールバック関数AckTrace()と，輻輳状態トレース用のコールバック関数CongStateTracer()をそれぞれ追加します．なお，輻輳状態は，tcp-socket-base.hで定義される列挙型TcpSocketState::TcpCongState_tです．また，上記のコールバック関数とトレース対象の変数を紐付ける関数TraceAck()およびTraceCongState()も，それぞれ追加します．

トレース設定のスケジューリング

最後に，上記TraceAck()およびTraceCongState()をスケジューリングします．

my-tcp-variants-comparison.ccのコンパイル

~/ns-3.26/source/ns-3.26ディレクトリで./wafすることで，my-tcp-variants-comparison.ccをコンパイルできます．

実験

シナリオスクリプトの実行

まず，データ格納用ディレクトリdataを作成します．

以下のシェルスクリプトを実行して，全12種類のアルゴリズムについて実験を行います．前回の記事でもご紹介した通り，--arg=valueによりコマンドライン引数argに値valueを渡すことができます．transport_protは輻輳制御アルゴリズム，prefix_nameは出力ファイル名のプレフィックス，tracingはトレースの有無，そしてdurationはシミュレーション時間[s]を表します．

全アルゴリズムの輻輳制御を観察

ひとまず，下記のplot_cwnd_all_algorithms()で，全アルゴリズムの\(cwnd\)と，\(ssth\)と，輻輳状態の変化をプロットしてみます．

横軸は時間[s]，縦軸は\(cwnd\)および\(ssth\)[segment]です．\(cwnd\)は実線，\(ssth\)は点線です．輻輳状態に応じて，色を塗り分けています．\(OPEN\)は青，\(DISORDER\)は緑，\(RECOVERY\)は黄色，そして\(LOSS\)は赤です．当初の想定以上に，各アルゴリズムの個性が色濃く出てくれました．

各アルゴリズムのcwnd，ACK，RTTの関係を観察

次は，下記のplot_cwnd_ack_rtt_each_algorithm()で，各アルゴリズムの\(cwnd\)，ACK，およびRTTをプロットします．

以下では，NewRenoを例に，結果を分析します．また，ご参考までに，他のアルゴリズムの結果も載せておきます．

NewReno

1.93[s]付近で，三重複ACKを受信し，\(RECOVERY\)状態に遷移しています．このときのスループットを概算すると：

ここで，ボトルネックリンクの帯域は2.0Mbps（4.1節参照）でしたので，輻輳が発生するタイミングとして不自然ではないです⁵．\(RECOVERY\)に遷移後，ACKおよびRTTの更新が止まっていることがわかります．また，\(cwnd\)や\(ssth\)の更新が3.3節と整合していることが確認できます．

3.26[s]付近で，新規ACKを受信することがないままタイムアウトし，\(LOSS\)状態に遷移しています．\(cwnd\)や\(ssth\)の更新が3.3節と整合していることが確認できます．4.69[s]付近で，ついに新規ACKを受信し，\(OPEN\)状態に遷移しています．

その他のアルゴリズム

ご参考までに，他のアルゴリズムの結果も掲載しておきます．

おわりに

本記事では，ns-3を使ってTCPの輻輳制御をシミュレートし，pythonで可視化してみました．初心者なりに，TCPの雰囲気を掴むことができました．また，ns-3のサンプルシナリオの優秀さを再認識しました． 　今後は，CUBICやCTCPのようなメジャーなアルゴリズムの実装や，Remyのような最新のアルゴリズムの実装に挑戦したいと思っています．あるいは，異なるアルゴリズム同士の競合を観察してみるのもいいかなと思っています．

最後まで読んでくださり，ありがとうございました！

参考

本記事の作成にあたっては，下記を参考にさせて頂きました．ありがとうございました！

• TCP各バージョンの輻輳制御の比較
• 3分間ネットワーキング，第42回レイヤ４ TCP 輻輳制御