ns-3でTCPの輻輳制御を観察する

#1. はじめに
　インターネット上のほとんどのトラフィックは，**TCP（Transmission Control Protocol）**によって制御されていると言われています．TCPの特徴の一つとして，送信ノードが各々**輻輳[^輻輳]制御アルゴリズム（Congestion control algorithm）**に基づき，一度に送信するデータ量を調整する，という点があります．本記事では，[ns-3](https://www.nsnam.org/)で各アルゴリズムの動作をシミュレートし，[NumPy](http://www.numpy.org/) + [matplotlib](http://matplotlib.org/)で視覚化します．
　TCPの輻輳制御アルゴリズムを比較するために，ns-3には[`tcp-variants-comparison.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-variants-comparison_8cc.html)というサンプルシナリオが用意されています．しかし，このシナリオスクリプトをそのまま使うと，本記事で注目するいくつかの変数をモニタ（ns-3では，**トレース**と呼びます）できない，という課題がありました．そこで，本記事では，シナリオスクリプトに任意のトレース情報を追加する方法を紹介します．

![TcpAll20.0-cwnd.png](https://qiita-image-store.s3.amazonaws.com/0/151195/c67dba4f-93ce-0618-c980-22c888d3afc7.png)

 なお，本記事のソースコードは，全て[Github](https://github.com/haltaro/comparing-tcp-algorithms)に置いてあります．

[^輻輳]: ネットワークにおける混雑，的なイメージの言葉です．


#2. 環境構築

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

[ns-3.26で始めるネットワークシミュレーション](http://qiita.com/haltaro/items/b474d924f63692c155c8)

##2.2 python
本記事では，データ処理に[NumPy](http://www.numpy.org/)，グラフ描画に[matplotlib](http://matplotlib.org/)を利用します．下記の環境で動作を確認しました．

* Python 2.7.11
* NumPy 1.10.4
* matplotlib 1.5.1

#3. TCPにおける輻輳制御

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

[^delayedACK]: 説明をシンプルにするため，本記事では遅延ACK（delayed acknowledgement）は考慮しません．遅延ACKは，複数のACKをまとめて送信することでネットワークの利用効率を向上させる方式です．

[^ACKnumber]: Acknowledgement numberは，厳密には受信したSequence number + Segment sizeです．本記事では，説明を直感的にするため，DATAのセグメント番号をそのままACKするようなイメージ図を用いています．

![model.png](https://qiita-image-store.s3.amazonaws.com/0/151195/ea523d49-c229-2d46-a3c5-7290b3f82dff.png)


　厳密には，データ量の調整は，$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$の更新方法を表します．

[^状態遷移図]: いわゆるTCPの状態遷移図（Finite state machine）とは異なります．状態遷移図は，コネクションの確立から切断までを対象としていますが，輻輳状態はコネクション確立（ESTABLISHED）中の輻輳の状態を対象としています．

##3.2 輻輳状態（Congestion state）
　本記事では，ns-3の実装（[`~/ns-3.26/source/ns-3.26/src/internet/model/tcp-socket-base.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-socket-base_8cc.html)）に基づき，以下の4種類の輻輳状態を想定します．


![state.png](https://qiita-image-store.s3.amazonaws.com/0/151195/29f58349-b23e-636f-64f9-2798a899eb34.png)


* *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のタイムアウトを検知した状態です．深刻な輻輳が生じている可能性があります．


##3.3 輻輳制御アルゴリズム（Congestion control algorithm）
　本記事では，ns-3の[実装](https://www.nsnam.org/docs/models/html/tcp.html)に基づき，以下の輻輳制御アルゴリズムを想定します．`TypeId`とは，ns-3におけるアルゴリズムの呼び名のようなものです．ソースコードは，それぞれ`~/ns-3.26/source/ns-3.26/src/internet/model`に格納されています．

|アルゴリズム|`TypeId`|ソースコード|
|:--|:--|:--|
|[NewReno](https://tools.ietf.org/html/rfc6582) | `TcpNewReno`| [`tcp-congestion-ops.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-congestion-ops_8cc.html)|
|[HighSpeed](https://tools.ietf.org/html/rfc3649) | `TcpHighSpeed`|[`tcp-highspeed.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-highspeed_8cc.html) |
|[Hybla](http://www.mathcs.emory.edu/~cheung/Courses/558/Syllabus/Papers/TCP-Hybla.pdf) | `TcpHybla`| [`tcp-hybla.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-hybla_8cc.html) |
|[Westwood](https://pdfs.semanticscholar.org/d3f0/a499906d7821cf204d9ca26900c11179777e.pdf) | `TcpWestwood`| [`tcp-westwood.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-westwood_8cc.html) |
|Westwood+ | `TcpWestwoodPlus`| [`tcp-westwood.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-westwood_8cc.html) |
|[Vegas](http://cseweb.ucsd.edu/~rbraud/jsac.pdf) | `TcpVegas` | [`tcp-vegas.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-vegas_8cc.html) |
|[Scalable](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.5330&rep=rep1&type=pdf) | `TcpScalable`| [`tcp-scalable.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-scalable_8cc.html) |
|[Veno](http://ieeexplore.ieee.org/document/1177186/) | `TcpVeno`| [`tcp-veno.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-veno_8cc.html) |
|[Bic](http://infocom2004.ieee-infocom.org/Papers/52_4.PDF) | `TcpBic`| [`tcp-bic.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-bic_8cc.html) |
|[YeAH](http://infocom.uniroma1.it/~vacirca/yeah/yeah.pdf) | `TcpYeah`| [`tcp-yeah.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-yeah_8cc.html) |
|[Illinois](http://dl.acm.org/citation.cfm?id=1190166) | `TcpIllinois`| [`tcp-illinois.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-illinois_8cc.html) |
|[H-TCP](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.7816&rep=rep1&type=pdf) | `TcpHtcp`| [`tcp-htcp.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-htcp_8cc.html) |

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

|更新契機|更新式|
|:--|:--|
|*OPEN*（SS）状態で，ACKを受信したとき| $ cwnd \gets cwnd + 1$|
|*OPEN*（CA）状態で，ACKを受信したとき| $ \displaystyle cwnd \gets cwnd + \frac{1}{cwnd}$|
|*RECOVERY*状態に遷移したとき| $ssth \gets max(\mathit{inflight} /2, 2 \cdot smss)$, <bf> $cwnd \gets ssth +3$|
|*RECOVERY*状態で，重複ACKを受信したとき|$ \displaystyle cwnd \gets cwnd + 1$|
|*RECOVERY*状態で，新規ACKを受信し，*OPEN*状態に遷移したとき|$ cwnd \gets ssth$|
|*LOSS*状態に遷移したとき|$ cwnd \gets smss$，<bf> $ssth \gets max(\mathit{inflight} /2, 2 \cdot smss)$|

　ここで，$\mathit{inflight}$は，ACKが返っていないDATAの総量を表し，$smss$は最小セグメントサイズを表します．また，簡単のためPartial ACKやFull ACK等は考慮していません．NewRenoの動作の詳細は，[RFC6582](https://tools.ietf.org/html/rfc6582)等をご参照ください．
　NewRenoは，輻輳の可能性が低いと思われるSlow startフェーズにおいては，$cwnd$を高速に増加させることでDATAを効率的に送信し，一方で輻輳の可能性が高いと思われるCongestion avoidanceフェーズにおいては，徐々に$cwnd$を上げることで急激な輻輳を回避する，という戦略を採用しています．
　ACK受信を契機とする更新式は，**1セグメント分のACKに対する更新式**という点にご注意ください（私はここでハマりました）．例えば，$cwnd=4$のとき，TCP Senderは4セグメント分のDATAに対するACK[^delayedACK]を受信するため，上記の更新を**4回**行います．
　なお，[ns-3におけるTCPの実装](https://www.nsnam.org/docs/models/html/tcp.html)は以下の3種類がありますが，本記事ではns-3ネイティブ（`src/internet/model`）で実装されているアルゴリズムのみを対象とします．つまり，Linuxでメジャーな[CUBIC](http://dl.acm.org/citation.cfm?id=1400105)や，Windowsでメジャーな[CTCP](http://www.dcs.gla.ac.uk/~lewis/CTCP.pdf)は対象外です．これらについては，別途ご紹介できればと思っています．

* ns-3ネイティブ（`src/internet/`）
* [NSC（Network Simulation Cradle）](http://www.wand.net.nz/~stj2/nsc/)
* [DCE（Direct Code Execution）](https://www.nsnam.org/overview/projects/direct-code-execution/)

[^ack]: 遅延ACK．

#4. シナリオスクリプトの作成

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

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

　ns-3は，TCPの輻輳制御アルゴリズムの比較用に，[`tcp-variants-comparison.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-variants-comparison_8cc.html)
というサンプルシナリオを用意しています（`~/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`は，それぞれトレース対象の初期値を取り扱う際に一時的に使用される変数を表します．

```cpp:tcp-variants-comparison.cc（58行目から70行目）
bool firstCwnd = true;
bool firstSshThr = true;
bool firstRtt = true;
bool firstRto = true;
Ptr<OutputStreamWrapper> cWndStream;
Ptr<OutputStreamWrapper> ssThreshStream;
Ptr<OutputStreamWrapper> rttStream;
Ptr<OutputStreamWrapper> rtoStream;
Ptr<OutputStreamWrapper> nextTxStream;
Ptr<OutputStreamWrapper> nextRxStream;
Ptr<OutputStreamWrapper> inFlightStream;
uint32_t cWndValue;
uint32_t ssThreshValue;
```
### トレース用コールバック関数の設定
　73行目から145行目ではトレース用コールバック関数`*Tracer()`の定義を，147行目から202行目ではコールバック関数をトレース対象と紐付ける関数`Trace*()`の定義を行います．ここでは，トレース対象の１つである`BytesInFlight`を例に解説します．

```cpp:tcp-variants-comparison.cc（73行目から202行目）
static void
InFlightTracer (uint32_t old, uint32_t inFlight)
{
  *inFlightStream->GetStream () << Simulator::Now ().GetSeconds () << " " << inFlight << std::endl;
}

//===== 略 =====

static void
TraceInFlight (std::string &in_flight_file_name)
{
  AsciiTraceHelper ascii;
  inFlightStream = ascii.CreateFileStream (in_flight_file_name.c_str ());
  Config::ConnectWithoutContext ("/NodeList/1/$ns3::TcpL4Protocol/SocketList/0/BytesInFlight", MakeCallback (&InFlightTracer));
}
```

　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`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-socket-base_8cc.html)において`AddTraceSource()`されています．ns-3は，トレース対象となった変数が更新される度に，その変数に紐付けられたコールバック関数を呼び出します．よって，トレース対象の設定には，**コールバック関数の定義**と，**トレース対象とコールバック関数の紐付け**が必要です．
　コールバック関数として，上記`InFlightTracer()`のような関数がよく使われます．`InFlightTracer()`は，現在時刻（`Simulator::Now ().GetSeconds ()`）と，更新後の値（`inFlight`）を，都度出力する関数です．
　トレース対象とコールバック関数の紐付け時には，上記`TraceInFlight()`にあるように，`Config::ConnectWithoutContext(variable, MakeCallback(&func))`という構文を使うことができます．ここで，`variable`は，トレース対象のObjectのパスを記載する必要があります．`/NodeList/1/$ns3::TcpL4Protocol/SocketList/0/BytesInFlight`は，`NodeList`1番のノードにぶら下がる，`SocketList`0番のソケットの，変数`BytesInFlight`を意味します．
　ns-3におけるトレース方法の詳細は，[公式マニュアル](https://www.nsnam.org/docs/release/3.26/manual/ns-3-manual.pdf)の1.10節をご参照ください．


### ネットワーク構成

　204行目以降の`main()`で，ネットワーク構成の設定を行います．詳細は[公式マニュアル](https://www.nsnam.org/docs/release/3.26/manual/ns-3-manual.pdf)に譲り，ここではポイントのみ記載します．

![network.png](https://qiita-image-store.s3.amazonaws.com/0/151195/e2b6da86-4058-3ef1-7bba-952887c1d415.png)



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

### コマンドライン引数

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

```cpp:tcp-variants-comparison.cc（224行目から243行目）
CommandLine cmd;
  cmd.AddValue ("transport_prot", "Transport protocol to use: TcpNewReno, "
                "TcpHybla, TcpHighSpeed, TcpHtcp, TcpVegas, TcpScalable, TcpVeno, "
                "TcpBic, TcpYeah, TcpIllinois, TcpWestwood, TcpWestwoodPlus ", transport_prot);
  cmd.AddValue ("error_p", "Packet error rate", error_p);
  cmd.AddValue ("bandwidth", "Bottleneck bandwidth", bandwidth);
  cmd.AddValue ("delay", "Bottleneck delay", delay);
  cmd.AddValue ("access_bandwidth", "Access link bandwidth", access_bandwidth);
  cmd.AddValue ("access_delay", "Access link delay", access_delay);
  cmd.AddValue ("tracing", "Flag to enable/disable tracing", tracing);
  cmd.AddValue ("prefix_name", "Prefix of output trace file", prefix_file_name);
  cmd.AddValue ("data", "Number of Megabytes of data to transmit", data_mbytes);
  cmd.AddValue ("mtu", "Size of IP packets to send in bytes", mtu_bytes);
  cmd.AddValue ("num_flows", "Number of flows", num_flows);
  cmd.AddValue ("duration", "Time to allow flows to run in seconds", duration);
  cmd.AddValue ("run", "Run index (for setting repeatable seeds)", run);
  cmd.AddValue ("flow_monitor", "Enable flow monitor", flow_monitor);
  cmd.AddValue ("pcap_tracing", "Enable or disable PCAP tracing", pcap);
  cmd.AddValue ("queue_disc_type", "Queue disc type for gateway (e.g. ns3::CoDelQueueDisc)", queue_disc_type);
  cmd.Parse (argc, argv);
```

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

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

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

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

```cpp:tcp-variants-comparison.cc（460行目から476行目）
  if (tracing)
    {
      std::ofstream ascii;
      Ptr<OutputStreamWrapper> ascii_wrap;
      ascii.open ((prefix_file_name + "-ascii").c_str ());
      ascii_wrap = new OutputStreamWrapper ((prefix_file_name + "-ascii").c_str (),
                                            std::ios::out);
      stack.EnableAsciiIpv4All (ascii_wrap);

      Simulator::Schedule (Seconds (0.00001), &TraceCwnd, 
                           prefix_file_name + "-cwnd.data");
      Simulator::Schedule (Seconds (0.00001), &TraceSsThresh, 
                           prefix_file_name + "-ssth.data");
      Simulator::Schedule (Seconds (0.00001), &TraceRtt, 
                           prefix_file_name + "-rtt.data");
      Simulator::Schedule (Seconds (0.00001), &TraceRto, 
                           prefix_file_name + "-rto.data");
      Simulator::Schedule (Seconds (0.00001), &TraceNextTx, 
                           prefix_file_name + "-next-tx.data");
      Simulator::Schedule (Seconds (0.00001), &TraceInFlight, 
                           prefix_file_name + "-inflight.data");
      Simulator::Schedule (Seconds (0.1), &TraceNextRx, 
                           prefix_file_name + "-next-rx.data");
    }
```

ns-3では，`Simulator::Schedule(time, &func, args,...)`という構文で，`time`時に`func(args,...)`を実行するようスケジューリングできます．
　しかし，なぜ地の文で`Trace*()`してはいけないのか，イマイチよくわからないです．おそらくオブジェクト生成のタイミングの問題の気がするのですが…．

##4.2 `tcp-variants-comparison.cc`の課題

　`tcp-variants-comparison.cc`は，非常によくできたシナリオスクリプトで，コマンドライン引数をいじるだけでかなり遊べます．しかし，我々が興味のある，ACKや輻輳状態をトレースできません！
　幸いにも，最新のACKを表す変数`HighestRxAck`と，輻輳状態を表す変数`CongState`は，それぞれ[`tcp-socket-base.cc`](https://www.nsnam.org/docs/release/3.26/doxygen/tcp-socket-base_8cc.html)で`AddTraceSource()`されています．よって，シナリオスクリプトに少し変更を加えるだけで，これらをトレース対象に追加することができます．以下では，その方法をご紹介します．

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

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

```bash
$ cd ~/ns-3.26/source/ns-3.26
$ cp examples/tcp/tcp-variants-comparison.cc scratch/my-tcp-variants-comparison.cc 
```

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

### トレース用変数の追加

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

```cpp:my-tcp-variants-comparison.cc（tcp-variants-comparison.ccの58行目から70行目相当）
bool firstCwnd = true;
bool firstSshThr = true;
bool firstRtt = true;
bool firstRto = true;
Ptr<OutputStreamWrapper> cWndStream;
Ptr<OutputStreamWrapper> ssThreshStream;
Ptr<OutputStreamWrapper> rttStream;
Ptr<OutputStreamWrapper> rtoStream;
Ptr<OutputStreamWrapper> nextTxStream;
Ptr<OutputStreamWrapper> nextRxStream;
Ptr<OutputStreamWrapper> inFlightStream;
Ptr<OutputStreamWrapper> ackStream; // NEW!
Ptr<OutputStreamWrapper> congStateStream; // NEW!
uint32_t cWndValue;
uint32_t ssThreshValue;
```

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

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

```cpp:my-tcp-variants-comparison.cc（tcp-variants-comparison.ccの73行目から202行目相当）
static void
AckTracer (SequenceNumber32 old, SequenceNumber32 newAck)
{
  *ackStream->GetStream () << Simulator::Now ().GetSeconds () << " " << newAck << std::endl;
}

static void
CongStateTracer (TcpSocketState::TcpCongState_t old, TcpSocketState::TcpCongState_t newState)
{
  *congStateStream->GetStream () << Simulator::Now ().GetSeconds () << " " << newState << std::endl;
}

//===== 略 =====

static void
TraceAck (std::string &ack_file_name)
{
  AsciiTraceHelper ascii;
  ackStream = ascii.CreateFileStream (ack_file_name.c_str ());
  Config::ConnectWithoutContext ("/NodeList/1/$ns3::TcpL4Protocol/SocketList/0/HighestRxAck", MakeCallback (&AckTracer));
}

static void
TraceCongState (std::string &cong_state_file_name)
{
  AsciiTraceHelper ascii;
  congStateStream = ascii.CreateFileStream (cong_state_file_name.c_str ());
	Config::ConnectWithoutContext ("/NodeList/1/$ns3::TcpL4Protocol/SocketList/0/CongState", MakeCallback (&CongStateTracer));
}
```

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

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

```cpp:my-tcp-variants-comparison.cc（tcp-variants-comparison.cc460行目から476行目相当）
  if (tracing)
    {

// ===== 略 =====

      Simulator::Schedule (Seconds (0.00001), &TraceAck, prefix_file_name + "-ack.data"); // NEW!
      Simulator::Schedule (Seconds (0.00001), &TraceCongState, prefix_file_name + "-cong-state.data"); // NEW!
    }
```

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

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

```bash
$ ./waf
Waf: Entering directory '~/ns-3.26/source/ns-3.26/source/ns-3.26/build'
[ 985/2524] Compiling scratch/my-tcp-variants-comparison.cc
[2501/2524] Linking build/scratch/my-tcp-variants-comparison
Waf: Leaving directory '~/ns-3.26/source/ns-3.26/source/ns-3.26/build'
Build commands will be stored in build/compile_commands.json
'build' finished successfully (3.240s)

Modules built:
antenna                   aodv                      applications              
bridge                    brite (no Python)         buildings                 
click                     config-store              core                      
csma                      csma-layout               dsdv                      
dsr                       energy                    fd-net-device             
flow-monitor              internet                  internet-apps             
lr-wpan                   lte                       mesh                      
mobility                  mpi                       netanim (no Python)       
network                   nix-vector-routing        olsr                      
point-to-point            point-to-point-layout     propagation               
sixlowpan                 spectrum                  stats                     
tap-bridge                test (no Python)          topology-read             
traffic-control           uan                       virtual-net-device        
wave                      wifi                      wimax                     
xgpon (no Python)         

Modules not built (see ns-3 tutorial for explanation):
openflow                  visualizer                
```

#5. 実験

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

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

```bash
$ mkdir ~/ns-3.26/source/ns-3.26/data
```

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

```bash:compare-tcp-algorithms.sh
#!/bin/bash

ALGORITHMS=(TcpNewReno TcpHighSpeed TcpHybla TcpWestwood TcpWestwoodPlus \ 
 TcpVegas TcpScalable TcpVeno TcpBic TcpYeah TcpIllinois TcpHtcp)

for algo in ${ALGORITHMS[@]}; do
  echo "----- Simulating $algo -----"
  ./waf --run "my-tcp-variants-comparison --transport_prot=$algo --prefix_name='data/$algo' --tracing=True --duration=20"
done
```

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

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

```py:plottcpalgo.py
# -*- coding: utf-8 -*-
#!/usr/bin/env python


import numpy as np
import matplotlib.pyplot as plt

# データ成形用の関数です．
def get_data(algo, variable='cwnd', duration=20.):
    file_name = 'data/Tcp' + algo + '-' + variable + '.data'
    data = np.empty((0, 2)) # 初期化

    # ファイルからデータを取得します．
    for line in open(file_name, 'r'):
        data = np.append(
            data, np.array([map(float, line[:-1].split())]),
            axis=0)
    data = data.T

    # duration以下のデータのみ抜き出し，最後尾に[duration, data[1,-1]]を
    # 追加します．duration時刻までキレイにプロットするための処理です．
    data = data[:, data[0] < duration]
    if len(data[0])==0:
        data = np.append(
            data, np.array([[duration, 0]]).T,
            axis=1)
    else:
        data = np.append(
            data, np.array([[duration, data[1, -1]]]).T,
            axis=1)

    return data


def plot_cwnd_all_algorithms(duration=20.):
    algos = ['NewReno', 'HighSpeed', 'Hybla', 'Westwood', 'WestwoodPlus',
             'Vegas', 'Scalable', 'Veno', 'Bic', 'Yeah', 'Illinois', 'Htcp']
    segment = 340 # 本実験構成では，セグメント長は340バイトです．

    plt.figure(figsize=(15, 10))
    for i, algo in enumerate(algos): 
        plt.subplot(3, 4, i + 1)

        # cwnd，ssth，輻輳状態データの取得
        cwnd_data = get_data(algo, 'cwnd', duration) 
        ssth_data = get_data(algo, 'ssth', duration)
        state_data = get_data(algo, 'cong-state', duration)

        # 輻輳状態に応じて色を塗り分けます．
        # OPEN（青），DISORDER（緑），RECOVERY（黄），LOSS（赤）
        plt.fill_between(cwnd_data[0], cwnd_data[1] / segment,
                         facecolor='lightblue') # 初期状態はOPEN（青）
        for n in range(len(state_data[0])-1):
            fill_range = cwnd_data[0] >= state_data[0, n]
            if state_data[1, n]==1: # 1: DISORDER
                plt.fill_between(
                    cwnd_data[0, fill_range], cwnd_data[1, fill_range] / segment,
                    facecolor='lightgreen')
            elif state_data[1, n]==3: # 3: RECOVERY
                plt.fill_between(
                    cwnd_data[0, fill_range], cwnd_data[1, fill_range] / segment,
                    facecolor='khaki')
            elif state_data[1, n]==4: # 4: LOSS
                plt.fill_between(
                    cwnd_data[0, fill_range], cwnd_data[1, fill_range] / segment,
                    facecolor='lightcoral')
            else: # OPEN
                plt.fill_between(
                    cwnd_data[0, fill_range], cwnd_data[1, fill_range] / segment,
                    facecolor='lightblue')

        # cwnd（実線）およびssth（点線）のプロット．
        plt.plot(cwnd_data[0], cwnd_data[1] / segment, drawstyle='steps-post')
        plt.plot(ssth_data[0], ssth_data[1] / segment, drawstyle='steps-post',
                 color='b', linestyle='dotted')
        plt.ylim(0, 1200) # ssthの初期値がめちゃくちゃでかいので，ylimで上限を設定
        plt.title(algo)

    # 図の保存と表示
    plt.savefig('data/TcpAll' + str(duration).zfill(3) + '-cwnd.png')
    plt.show()
```

![TcpAll20.0-cwnd.png](https://qiita-image-store.s3.amazonaws.com/0/151195/cac2dc4a-34fa-5dfd-773e-3dbdb5db7d1e.png)

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

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

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

```py:plot_cwnd_ack_rtt_each_algorithm()
def plot_cwnd_ack_rtt_each_algorithm(duration=20.):
    algos = ['NewReno', 'HighSpeed', 'Hybla', 'Westwood', 'WestwoodPlus',
             'Vegas', 'Scalable', 'Veno', 'Bic', 'Yeah', 'Illinois', 'Htcp']
    segment = 340 # 本実験構成では，セグメント長は340バイトです．
    plt.figure()

    for algo in algos:
        plt.subplot(311) # cwnd，ssthおよび輻輳状態のプロット

        # cwnd，ssth，輻輳状態データの取得
        cwnd_data = get_data(algo, 'cwnd', duration)
        ssth_data = get_data(algo, 'ssth', duration)
        state_data = get_data(algo, 'cong-state', duration)


        # 輻輳状態に応じて色を塗り分けます．
        # OPEN（青），DISORDER（緑），RECOVERY（黄），LOSS（赤）
        plt.fill_between(cwnd_data[0], cwnd_data[1] / segment,
                         facecolor='lightblue') # 初期状態はOPEN（青）
        for n in range(len(state_data[0])-1):
            fill_range = cwnd_data[0] >= state_data[0, n]
            if state_data[1, n]==1: # 1: DISORDER
                plt.fill_between(
                    cwnd_data[0, fill_range], cwnd_data[1, fill_range] / segment,
                    facecolor='lightgreen')
            elif state_data[1, n]==3: # 3: RECOVERY
                plt.fill_between(
                    cwnd_data[0, fill_range], cwnd_data[1, fill_range] / segment,
                    facecolor='khaki')
            elif state_data[1, n]==4: # 4: LOSS
                plt.fill_between(
                    cwnd_data[0, fill_range], cwnd_data[1, fill_range] / segment,
                    facecolor='lightcoral')
            else: # OPEN
                plt.fill_between(
                    cwnd_data[0, fill_range], cwnd_data[1, fill_range] / segment,
                    facecolor='lightblue')

        # cwnd（実線）およびssth（点線）のプロット．
        plt.plot(cwnd_data[0], cwnd_data[1] / segment, drawstyle='steps-post',
                 color='b', label='cwnd')
        plt.plot(ssth_data[0], ssth_data[1] / segment, drawstyle='steps-post',
                 color='b', linestyle='dotted', label='ssth')
        ymax = max(cwnd_data[1] / segment)*1.1
        plt.ylim(0, ymax) # ssthの初期値がめちゃくちゃでかいので，ylimで上限を設定
        plt.ylabel('cwnd [segment]')
        plt.legend()
        plt.title(algo)

        plt.subplot(312) # ACKのプロット
        ack_data = get_data(algo, 'ack', duration)
        plt.plot(ack_data[0], ack_data[1] / segment, drawstyle='steps-post',
                 color='r')
        plt.ylabel('ACK [segment]')

        plt.subplot(313) # RTTのプロット
        rtt_data = get_data(algo, 'rtt', duration)
        plt.plot(rtt_data[0], rtt_data[1], drawstyle='steps-post', color='g')
        plt.ylabel('RTT[s]')
        plt.xlabel('Time [s]')

        # 画像の保存．
        plt.savefig('data/Tcp' + algo + 'Sub-' + str(int(duration)).zfill(3) +
                    '-cwnd-ack-rtt.png')
        plt.clf()
    plt.show()
```

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

### NewReno


![TcpNewReno020-cwnd-ack-rtt.png](https://qiita-image-store.s3.amazonaws.com/0/151195/52b01249-6e2d-33e1-59e6-2de913c81130.png)


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

```math
\frac{cwnd}{RTT} \simeq 
\frac{321\rm{[segment]} \cdot 340 \rm{[byte/segment] \cdot 8 \rm{[bit/byte]}}}{0.33[s]} \simeq 2.3 \rm{[Mbps]}
```

ここで，ボトルネックリンクの帯域は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$状態に遷移しています．

[^分析]: たぶん．キューの分析等，もっと詳細な分析が必要だと思いますが力尽きました…．

### その他のアルゴリズム

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

![TcpHighSpeed020-cwnd-ack-rtt.png](https://qiita-image-store.s3.amazonaws.com/0/151195/de2ae85a-f79f-0d7a-b98a-90c43e7c97e3.png)

![TcpHybla020-cwnd-ack-rtt.png](https://qiita-image-store.s3.amazonaws.com/0/151195/36055b18-bf49-0a50-791e-42929d2c0938.png)

![TcpWestwood020-cwnd-ack-rtt.png](https://qiita-image-store.s3.amazonaws.com/0/151195/3d41b246-a42d-936e-a3d4-11363c65697c.png)

![TcpWestwoodPlus020-cwnd-ack-rtt.png](https://qiita-image-store.s3.amazonaws.com/0/151195/400ec59a-a6df-bbe1-9b8f-2ea6c63ee815.png)

![TcpVegas020-cwnd-ack-rtt.png](https://qiita-image-store.s3.amazonaws.com/0/151195/4ffc8ff4-823f-1aec-3ac1-81eb9469ff76.png)

![TcpScalable020-cwnd-ack-rtt.png](https://qiita-image-store.s3.amazonaws.com/0/151195/93ae3515-e91e-92e1-d466-7d800069d95b.png)

![TcpVeno020-cwnd-ack-rtt.png](https://qiita-image-store.s3.amazonaws.com/0/151195/6122a656-cd75-c408-6e1a-96cc99573182.png)

![TcpBic020-cwnd-ack-rtt.png](https://qiita-image-store.s3.amazonaws.com/0/151195/e48f2ee4-3aa4-0913-e8d4-bf76a814e439.png)

![TcpYeah020-cwnd-ack-rtt.png](https://qiita-image-store.s3.amazonaws.com/0/151195/9ed7a220-96ef-7e02-9fff-c9988cfe5a67.png)

![TcpIllinois020-cwnd-ack-rtt.png](https://qiita-image-store.s3.amazonaws.com/0/151195/f8b06f1b-bee0-9739-0c7d-8a8a0f7ebbfe.png)

![TcpHtcp020-cwnd-ack-rtt.png](https://qiita-image-store.s3.amazonaws.com/0/151195/387a0df2-a07b-e756-114d-8a57cdfa761f.png)

#6. おわりに

　本記事では，ns-3を使ってTCPの輻輳制御をシミュレートし，pythonで可視化してみました．初心者なりに，TCPの雰囲気を掴むことができました．また，ns-3のサンプルシナリオの優秀さを再認識しました．
　今後は，[CUBIC](http://dl.acm.org/citation.cfm?id=1400105)や[CTCP](http://www.dcs.gla.ac.uk/~lewis/CTCP.pdf)のようなメジャーなアルゴリズムの実装や，[Remy](http://web.mit.edu/remy/)のような最新のアルゴリズムの実装に挑戦したいと思っています．あるいは，異なるアルゴリズム同士の競合を観察してみるのもいいかなと思っています．
　最後まで読んでくださり，ありがとうございました！

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

* [TCP各バージョンの輻輳制御の比較](http://www.net.c.dendai.ac.jp/~yutaro/)
* [3分間ネットワーキング，第42回レイヤ４ TCP 輻輳制御](http://www5e.biglobe.ne.jp/aji/3min/42.html)