ns-2でバイト単位のシミュレーションをする

動機

TCP互換のプロトコルを作ったときに、その有効性はいかほどか？といった評価をしたくなる。

実機の実装は簡単だけれども、厳密なプロトコルとしての性能評価を行おうとすると、バックグラウンドトラフィックやプロセッサ・メモリ等の状態の影響を受けるため、なかなか難しい。
また、数式を立てて評価することもできるが、その数式そのもの妥当性を評価することは、専門家も限られていて、相当難しい。

ということで、シミュレータを使って、簡単に評価したくなったときに使うのが、このns-2（とかns-3）。自由度が高く、しかも、無償。ありがたい。

チュートリアルサイトで説明しているケースは、シーケンス番号単位のシミュレーション方法しか解説していないことが多いため、ここではバイト単位のシミュレーションを行う方法をご紹介。

問題

ns-2は、スループットの計算（というか、各LinkのDelayの計算）ではバイト単位で計算してくれるが、Agent/TCPの処理に目を向けると、実はバイト単位ではなく、多くの箇所はMSSで正規化されたSequence番号で処理している。

というわけで、パケットサイズが異なるとどういう挙動をするのか、見れない。

対応方針

Full TCPを使うと、バイト単位でできそう。

35.3 Two-Way TCP Agents (FullTcp)
The Agent/TCP/FullTcp object is a new addition to the suite of TCP agents supported in the simulator and is still under development. It is different from (and incompatible with) the other agents, but does use some of the same architecture. It differs from these agents in the following ways: following ways:
• connections may be establised and town down (SYN/FIN packets are exchanged)
• bidirectional data transfer is supported
• sequence numbers are in bytes rather than packets ← これ！！

ただし、開発途中とのことなので、どこまで信頼性があるのか謎。検証を進めながら評価する必要あり。

• ほかにも、BayFullTCPというものもあるようですが、PartialACK(NewReno)はサポートしてい模様。
• linuxやintも、packet単位のシミュレーションの模様。

FullTCP

TcpAgentを継承するサブクラス。基本的に、すべてのTCP設定をここから引き継ぐ。

Tclファイルの見本

• ns-2.35/tcl/ex/delaybox/db-fulltcp.tcl

入門サイトで最初に勉強する「Agent/TCPとAgent/TcpSinkの組合せ」から、「Agent/TCP/FullTcp同士」の組合せに変更する。受信側Agentは、listenコマンドを発行することで、LISTEN状態に遷移して通信を待ち受ける。

それ以外は、大まかにはAgent/TCPと同様の動きをする。ただし、動作の詳細は少々違う模様。評価時には注意深く観察が必要。

検証・評価

MSS

"packetSize_"ではなく、"segsize_"で制御する。

遅延ACK

デフォルトで遅延ACKがON（0.1; 100ms）なので、必要に応じて"inetrval_"の値を調整する。

tick

TcpAgentから継承

bytes_

OTclの世界でのスループット計算など、受信したバイト数（ヘッダ含む）を確認したいときに、Agent/TcpSinkでは"bytes_"が使えた。しかし、Fullでは用意されていないため、後述する追加開発を行う。

seqno

seqnoにアクセスするときには、Agent/TCPで定義済みのものを使うと簡単そう。
TCPSinkは、TCPを継承していないため、これらが使えない。（なので、上述のbytes_が追加されたのかと）

tcp.h

TracedInt t_seqno_; /* sequence number */
TracedInt curseq_;  /* highest seqno "produced by app" */

tcp.cc

bind("seqno_", &curseq_);     // 送信データが固定値であれば、その最大値が格納される
bind("t_seqno_", &t_seqno_);  

tcp-full.cc

        int progress = (ackno > highest_ack_);

        if (ackno == maxseq_) {
                cancel_rtx_timer();     // all data ACKd
        } else if (progress) {
                set_rtx_timer();
        }

        // advance the ack number if this is for new data
        if (progress)
                highest_ack_ = ackno;

        // if we have suffered a retransmit timeout, t_seqno_
        // will have been reset to highest_ ack.  If the
        // receiver has cached some data above t_seqno_, the
        // new-ack value could (should) jump forward.  We must
        // update t_seqno_ here, otherwise we would be doing
        // go-back-n.

        if (t_seqno_ < highest_ack_)
                t_seqno_ = highest_ack_; // seq# to send next

        bind("ack_", &highest_ack_);

ackno

Agent/TCPとAgent/TCP/FullTcpの違いは、ACKパケットのACK番号の格納場所。前者はパケットのseqnoにACK番号が格納され、一方、後者はacknoにそれが格納される。すなわち、TCP実装の通りで、もし受信側が受信に専念しているのであれば、それが返送するACKのseqnoは常に1になる。（ISSは0から始まる前提。1はSYNフラグ分）

TCP

r 1.000089 0 1 tcp 40 ------- 0 2.1 1.256 0 2
r 1.000189 0 1 tcp 1500 ------- 0 2.1 1.256 1 4
r 1.000201 0 1 tcp 1500 ------- 0 2.1 1.256 2 5
# 右から2番目（seqno）は1ずつ増える。（受け取ったseqnoが入っている）
r 1.000583 0 1 tcp 1500 ------- 0 2.1 1.256 22 41
r 1.000595 0 1 tcp 1500 ------- 0 2.1 1.256 23 43

TCP-FULL

r 1.000108 1 0 ack 40 ------- 0 1.256 2.1 0 3
r 1.000209 1 0 ack 40 ------- 0 1.256 2.1 1 7
r 1.000221 1 0 ack 40 ------- 0 1.256 2.1 1 8
# ずっと1...（右から2番目がseqno）
r 1.00059 1 0 ack 40 ------- 0 1.256 2.1 1 52
r 1.000602 1 0 ack 40 ------- 0 1.256 2.1 1 53

標準のパケットトレース機能では、seqnoしか表示しないため、acknoもみたい場合は、以下のページを参考にするとよい。

ACK with data for SYN/ACK

Agent/TCPの標準では、SYN/ACKに対するACKにDataを載せていたが、Agent/TCP/FullTcpでは、TCP標準実装に基づいて送っていなった。Linuxは前者で、その他の実装でも前者を採用するものは多いし、一応RFC違反ではない。ただし、ACKとデータは別々のパケットで同じタイミングで送信されているだけで、キューがバイト単位で処理されている限り、ほとんど影響はない。

TCP-FULL

osada@share1% grep '+.*\ 2\ 0\ tcp' out.ns          # 2: 送信側（アクティブオープン:SYN_SENT）, 0: ルータ
+ 1.00005 2 0 tcp 40 ------- 0 2.1 1.256 0 2        # SYN
+ 1.000127 2 0 tcp 40 ------- 0 2.1 1.256 1 4       # SYN/ACK (cwnd = cwnd + 1)
+ 1.000127 2 0 tcp 1500 ------- 0 2.1 1.256 1 5     # Data (cwnd = 1 of 2 pkt)
+ 1.000127 2 0 tcp 1500 ------- 0 2.1 1.256 1461 6  # Data (cwnd = 2 of 2 pkt)

osada@share1% grep 'r.*\ 0\ 1\ tcp' out.ns        # 0: ルータ, 1: 受信側（パッシブオープン：LISTEN）
r 1.000089 0 1 tcp 40 ------- 0 2.1 1.256 0 2     # SYN/ACK
r 1.000166 0 1 tcp 40 ------- 0 2.1 1.256 1 4     # ACK
r 1.00019 0 1 tcp 1500 ------- 0 2.1 1.256 1 5    # Data (TransmissionDelay分到着時間に差が出る）
r 1.000202 0 1 tcp 1500 ------- 0 2.1 1.256 1461 6

TCP

osada@share1% grep '+.*\ 2\ 0\ tcp' out.ns          # 2: 送信側（アクティブオープン:SYN_SENT）, 0: ルータ
+ 1.00005 2 0 tcp 40 ------- 0 2.1 1.256 0 2
+ 1.000127 2 0 tcp 1500 ------- 0 2.1 1.256 1 4     # SYN/ACKに対するACKが含まれる
+ 1.000127 2 0 tcp 1500 ------- 0 2.1 1.256 2 5


osada@share1% grep 'r.*\ 0\ 1\ tcp' out.ns        # 0: ルータ, 1: 受信側（パッシブオープン：LISTEN）
r 1.000089 0 1 tcp 40 ------- 0 2.1 1.256 0 2
r 1.000189 0 1 tcp 1500 ------- 0 2.1 1.256 1 4   # ACK分40バイトのQueuingが発生しない分、若干早い
r 1.000201 0 1 tcp 1500 ------- 0 2.1 1.256 2 5

Nagle

送るべきデータが少なく、MSSに満たないときは、snd_unaが0になるまで送信を保留するように見える。

+ 1.00059 0 2 ack 40 ------- 0 1.256 2.1 1 51
+ 1.000602 0 2 ack 40 ------- 0 1.256 2.1           # ACK

+ 1.000454 2 0 tcp 1500 ------- 0 2.1 1.256 27741 40
+ 1.000466 2 0 tcp 1500 ------- 0 2.1 1.256 29201 41
+ 1.000466 2 0 tcp 1500 ------- 0 2.1 1.256 30661 42
+ 1.000622 2 0 tcp 688 ------- 0 2.1 1.256 32121 54  # 送信がやけに遅い。タイミングは最後のACKが来てから

r 1.000559 0 1 tcp 1500 ------- 0 2.1 1.256 27741 40
r 1.000571 0 1 tcp 1500 ------- 0 2.1 1.256 29201 41
r 1.000583 0 1 tcp 1500 ------- 0 2.1 1.256 30661 42
r 1.000677 0 1 tcp 688 ------- 0 2.1 1.256 32121 54 

理由は、これ。Agent/TCPはNagleがオフだが、FullTcpはオンの様子。

tcp-full.cc

int
FullTcpAgent::foutput(int seqno, int reason)
{
// 省略
        if (datalen > 0) {
                // if full-sized segment, ok
                if (datalen == maxseg_)
                        goto send;
                // if Nagle disabled and buffer clearing, ok
                if ((quiet || nodelay_)  && emptying_buffer) // <-　これ。バッファが空になったときの挙動。nodelay_がtrueでないため。
                        goto send;
                // if a retransmission
                if (is_retransmit)
                        goto send;
                // if big "enough", ok...
                //      (this is not a likely case, and would
                //      only happen for tiny windows)
                if (datalen >= ((wnd_ * maxseg_) / 2.0))
                        goto send;
        }

以下を宣言してあげる。

        Agent/TCP/FullTcp set nodelay_ true; # Nagle disable? (default: false)

こうなる。

r 1.000559 0 1 tcp 1500 ------- 0 2.1 1.256 27741 40
r 1.000571 0 1 tcp 1500 ------- 0 2.1 1.256 29201 41
r 1.000583 0 1 tcp 1500 ------- 0 2.1 1.256 30661 42
r 1.000588 0 1 tcp 688 ------- 0 2.1 1.256 32121 44   # !!!

バイト単位でシミュレーションする醍醐味。

FIN

受信に専念しているノードが生成するACKを見ると、ずっとFINがついているように見える。

osada@share1% grep '+.*1\ 0\ ack' out.ns | more
+ 1.000089 1 0 ack 40 ------- 0 1.256 2.1 0 3 1 0x1a 40 0
+ 1.00019 1 0 ack 40 ------- 0 1.256 2.1 1 7 1461 0x18 40 0
+ 1.000202 1 0 ack 40 ------- 0 1.256 2.1 1 8 2921 0x18 40 0
・・・
+ 1.000583 1 0 ack 40 ------- 0 1.256 2.1 1 53 32121 0x18 40 0
+ 1.000871 1 0 ack 40 ------- 0 1.256 2.1 1 58 32769 0x18 40 0 # !!!

あれ、最後のACKが遅い。

「2つのセグメントに1つのACK返送」という戦略か、SWS回避か。

まずは、「2つのセグメントに1つのACK返送」をオフにする。

シナリオファイル

Agent/TCP/FullTcp set segsperack_ true; # (default: false)

＜受信＞
r 1.000571 0 1 tcp 1500 ------- 0 2.1 1.256 29201 42 1 0x10 40 0
r 1.000583 0 1 tcp 1500 ------- 0 2.1 1.256 30661 43 1 0x10 40 0
r 1.000588 0 1 tcp 688 ------- 0 2.1 1.256 32121 45 1 0x18 40 0
r 1.000672 0 1 tcp 40 ------- 0 2.1 1.256 32769 57 1 0x18 40 0

＜ACK返送＞
+ 1.000571 1 0 ack 40 ------- 0 1.256 2.1 1 53 30661 0x18 40 0
+ 1.000583 1 0 ack 40 ------- 0 1.256 2.1 1 54 32121 0x18 40 0
+ 1.000588 1 0 ack 40 ------- 0 1.256 2.1 1 55 32769 0x18 40 0

逐次ACKを返送するようになった。
受信の最後を見ると、ご丁寧に送信からFINが送られてきていることがわかる。素晴らしい再現度。

RTT計測・RTO計算・backoff初期化

長くなるので、記事を分割

cwndの開き方

ns-2実装では、cwndはパケット単位（MSS）でカウントされている。これはバイト実装でもパケット実装でも同じ。
バイト実装では、これにMSS（segsize_）をかけた値をwindowチェックで使う。

windowチェック用のメソッド（window()）は、int型の値を返す設計になっているため、cwndが小数点を持つ場合、端数は切り捨てられる。

小数点以下も加味して評価する場合は、windowd()というdouble型の値を返すメソッドを使うとよい。

（といっても、NagleがONである限り、あまり関係ありませんが）

追加開発

基本方針

基本方針は、スーパークラスの仮想関数をオーバライドする。仮想化されていない場合は、スーパークラスの関数を仮想化して、サブクラスで関数を実装する。OTclに対しては、極力新しいオブジェクトを作らず、既存流用に努める。

受信データ量計測

リアルタイムにスループットを計測し、オブジェクト間でコマンドをやり取りしたくなったときのために、rcv_nxtにアクセスできるようにする。

• 初期値設定（OTcl）

ns-2.35/tcl/lib/ns-default.tcl

        Agent/TCP/FullTcp set rcv_nxt_ -1; # 2016.6.30 Osada

• OTcl/C++リンク

ns-2.35/tcp/tcp-full.cc

void
FullTcpAgent::delay_bind_init_all()
{
        // 省略
        delay_bind_init_one("rcv_nxt_"); // ←これ追加

        TcpAgent::delay_bind_init_all();

        reset();
}

int
FullTcpAgent::delay_bind_dispatch(const char *varName, const char *localName, TclObject *tracer)
{
        // 省略
        if (delay_bind(varName, localName, "rcv_nxt_", &rcv_nxt_, tracer)) return TCL_OK; // ←これ追加

        return TcpAgent::delay_bind_dispatch(varName, localName, tracer);
}

rcv_nxt_は、TCP実装のrcv_nxtそのもの。つまり、次に受信を期待するシーケンス番号が入っている。（TCPSinkのsizeはヘッダサイズも含むが、rcv_nxtは含まない＝Goodput計測に有効）
これにアクセスできれば、受信用のTCPfullがどこまでデータを受信したかわかる。

例。こんな感じででアクセスする

$tcp set rcv_nxt_

パケット送信時の干渉

• recv # 受信したパケットに応じて、送信が必要かチェック
• send_much # 全体を通して送信可能かチェック
• foutput <- ここか　　　 // send_muchでは、if条件中に実行される
• sendpacket <- ここで干渉する
• send # ここは、次のオブジェクトにパケットを渡す処理

sendpacketには、統計値（snd_maxなど）の更新がないので、
foutputでの干渉が妥当か。

参考

ns-2: http://www.isi.edu/nsnam/ns/index.html
インストール: http://qiita.com/osada/items/133afdbba68c388ab818
C++とOtclのリンク：http://www.ece.ubc.ca/~teerawat/publications/NS2/04-OTcl.pdf