ns-2のRTTの計測方法に関する調査

# 環境
ns-2.35

# 調査事象

再送処理そのものについては、Agent/TCPとAgenet/TCP/FullTcpで差はない。しかし、rttの計測のところで差が生じている。なぜだろうか。

以下、Estimated RTTとReal RTTの乖離によって、不要な再送が発生してしまうケースを再現。NewReno（PartialACK）を使った回復も併せて行っているケース。


```
----pkt units
time: 0.000000000  saddr: -1 sport: -1 daddr: -1 dport: -1 maxseq: -1   hiack: -1   seqno: 0    cwnd: 1.000  ssthresh: 20  dupacks: 0  rtt: 0.000000000 srtt: 0.000000000 rttvar: 12.000000000 bkoff: 1 fid: 13 wnd: 44.000
time: 0.000000000  saddr: -1 sport: -1 daddr: -1 dport: -1 maxseq: -1   hiack: -1   seqno: 0    cwnd: 1.000  ssthresh: 20  dupacks: 0  rtt: 0.000000000 srtt: 0.000000000 rttvar: 12.000000000 bkoff: 1 fid: 13 wnd: 44.000
time: 1.000050000  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 0    hiack: -1   seqno: 0    cwnd: 1.000  ssthresh: 44  dupacks: 0  rtt: 0.000000000 srtt: 0.000000000 rttvar: 12.000000000 bkoff: 1 fid: 13 wnd: 44.000
time: 1.000131440  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 0    hiack: 0    seqno: 1    cwnd: 1.000  ssthresh: 44  dupacks: 0  rtt: 0.000000000 srtt: 0.000000000 rttvar: 12.000000000 bkoff: 1 fid: 13 wnd: 44.000
time: 1.000131440  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 1    hiack: 0    seqno: 1    cwnd: 2.000  ssthresh: 44  dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 1 fid: 13 wnd: 44.000
time: 1.000131440  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 2    hiack: 0    seqno: 2    cwnd: 2.000  ssthresh: 44  dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 1 fid: 13 wnd: 44.000

time: 1.000383920  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 2    hiack: 1    seqno: 2    cwnd: 1.000  ssthresh: 2   dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 2 fid: 13 wnd: 44.000
time: 1.000383920  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 3    hiack: 1    seqno: 3    cwnd: 2.000  ssthresh: 2   dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 2 fid: 13 wnd: 44.000
# backoffが1にならない。どこでなるのか。
time: 1.000587920  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 3    hiack: 2    seqno: 4    cwnd: 2.000  ssthresh: 2   dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 2 fid: 13 wnd: 44.000
time: 1.000587920  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 4    hiack: 2    seqno: 4    cwnd: 2.500  ssthresh: 2   dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 2 fid: 13 wnd: 44.000
time: 1.001055920  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 4    hiack: 3    seqno: 5    cwnd: 2.500  ssthresh: 2   dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 2 fid: 13 wnd: 44.000
time: 1.001055920  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 5    hiack: 3    seqno: 5    cwnd: 2.900  ssthresh: 2   dupacks: 0  rtt: 0.000672000 srtt: 0.000155300 rttvar: 0.000178200 bkoff: 1 fid: 13 wnd: 44.000
time: 1.001403920  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 5    hiack: 4    seqno: 6    cwnd: 2.900  ssthresh: 2   dupacks: 0  rtt: 0.000672000 srtt: 0.000155300 rttvar: 0.000178200 bkoff: 1 fid: 13 wnd: 44.000
time: 1.001403920  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 6    hiack: 4    seqno: 6    cwnd: 3.245  ssthresh: 2   dupacks: 0  rtt: 0.000672000 srtt: 0.000155300 rttvar: 0.000178200 bkoff: 1 fid: 13 wnd: 44.000

----byte units
time: 0.000000000  saddr: -1 sport: -1 daddr: -1 dport: -1 maxseq: -1   hiack: -1   seqno: 0    cwnd: 1.000  ssthresh: 20  dupacks: 0  rtt: 0.000000000 srtt: 0.000000000 rttvar: 12.000000000 bkoff: 1 fid: 13 wnd: 44.000
time: 0.000000000  saddr: -1 sport: -1 daddr: -1 dport: -1 maxseq: -1   hiack: -1   seqno: 0    cwnd: 1.000  ssthresh: 20  dupacks: 0  rtt: 0.000000000 srtt: 0.000000000 rttvar: 12.000000000 bkoff: 1 fid: 13 wnd: 44.000
time: 1.000050000  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 1    hiack: -1   seqno: 0    cwnd: 1.000  ssthresh: 44  dupacks: 0  rtt: 0.000000000 srtt: 0.000000000 rttvar: 12.000000000 bkoff: 1 fid: 13 wnd: 44.000
time: 1.000131440  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 1    hiack: 1    seqno: 1    cwnd: 1.000  ssthresh: 44  dupacks: 0  rtt: 0.000000000 srtt: 0.000000000 rttvar: 12.000000000 bkoff: 1 fid: 13 wnd: 44.000
time: 1.000131440  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 1461 hiack: 1    seqno: 1    cwnd: 2.000  ssthresh: 44  dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 1 fid: 13 wnd: 44.000
time: 1.000131440  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 2921 hiack: 1    seqno: 1461 cwnd: 2.000  ssthresh: 44  dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 1 fid: 13 wnd: 44.000

time: 1.000386687  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 2921 hiack: 1461 seqno: 1461 cwnd: 1.000  ssthresh: 2   dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 2 fid: 13 wnd: 44.000
time: 1.000386687  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 4381 hiack: 1461 seqno: 2921 cwnd: 2.000  ssthresh: 2   dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 1 fid: 13 wnd: 44.000
# Recoverから回復すると、backoffは1になる。しかし、rttは更新されない。
time: 1.000590687  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 4381 hiack: 2921 seqno: 4381 cwnd: 2.000  ssthresh: 2   dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 1 fid: 13 wnd: 44.000
time: 1.000590687  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 5841 hiack: 2921 seqno: 4381 cwnd: 2.500  ssthresh: 2   dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 1 fid: 13 wnd: 44.000
time: 1.001058687  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 5841 hiack: 4381 seqno: 4381 cwnd: 1.000  ssthresh: 2   dupacks: 2  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 2 fid: 13 wnd: 44.000
time: 1.001058687  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 7301 hiack: 4381 seqno: 5841 cwnd: 2.000  ssthresh: 2   dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 1 fid: 13 wnd: 44.000
time: 1.001406687  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 7301 hiack: 5841 seqno: 7301 cwnd: 2.000  ssthresh: 2   dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 1 fid: 13 wnd: 44.000
time: 1.001406687  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 8761 hiack: 5841 seqno: 7301 cwnd: 2.500  ssthresh: 2   dupacks: 0  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 1 fid: 13 wnd: 44.000
time: 1.002186687  saddr: 15 sport: 1  daddr: 1  dport: 269 maxseq: 8761 hiack: 7301 seqno: 7301 cwnd: 1.000  ssthresh: 2   dupacks: 1  rtt: 0.000081500 srtt: 0.000081500 rttvar: 0.000040750 bkoff: 4 fid: 13 wnd: 44.000
```

# 分析

## 正しい挙動

[RFC6298: Computing TCP's Retransmission Timer (June 2011)](http://qiita.com/osada/items/a2ae361572aa637cb395)参照

## 修正ポイント
Backoff初期化でバグあり。正しくは、RFCの通り、SRTTなどが更新されるときにBackoffを初期化することになっているが、ns-2のバイト実装では、「新しいACKを受信すれば、いつでも」Backoffは初期化されている。

```cpp:tcp/tcp.cc
/*
 * Process an ACK
 *	this version of the routine doesn't necessarily
 *	require the ack to be one which advances the ack number
 *
 * if this ACKs a rtt estimate
 *	indicate we are not timing
 *	reset the exponential timer backoff (gamma)
 * update rtt estimate
 * cancel retrans timer if everything is sent and ACK'd, else set it
 * advance the ack number if appropriate
 * update segment to send next if appropriate
 */
void
FullTcpAgent::newack(Packet* pkt)
{
	hdr_tcp *tcph = hdr_tcp::access(pkt);

	register int ackno = tcph->ackno();
	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

        /*
         * Update RTT only if it's OK to do so from info in the flags header.
         * This is needed for protocols in which intermediate agents
         * in the network intersperse acks (e.g., ack-reconstructors) for
         * various reasons (without violating e2e semantics).
         */
        hdr_flags *fh = hdr_flags::access(pkt);

	if (!fh->no_ts_) {
                if (ts_option_) {
			recent_age_ = now();
			recent_ = tcph->ts();
			rtt_update(now() - tcph->ts_echo());
			if (ts_resetRTO_ && (!ect_ || !ecn_backoff_ ||
		           !hdr_flags::access(pkt)->ecnecho())) { 
				// From Andrei Gurtov
				//
                         	// Don't end backoff if still in ECN-Echo with
                         	// a congestion window of 1 packet.
				t_backoff_ = 1;
			}
		} else if (rtt_active_ && ackno > rtt_seq_) {
			// got an RTT sample, record it
			// "t_backoff_ = 1;" deleted by T. Kelly.
			rtt_active_ = FALSE;
			rtt_update(now() - rtt_ts_);
                }
		if (!ect_ || !ecn_backoff_ ||
		    !hdr_flags::access(pkt)->ecnecho()) {
			/*
			 * Don't end backoff if still in ECN-Echo with
			 * a congestion window of 1 packet.
			 * Fix from T. Kelly.
			 */
			t_backoff_ = 1;  // <- ここ！！！
			ecn_backoff_ = 0;
		}

        }
	return;
}
```


## 修正後

SRTT更新時のみ、backoffが初期化されるようにする。
ちなみに、ns-2のパケット実装ではこのバグは存在していないため、ケア不要。

```cpp:tcp/tcp-full.cc
// （省略）
        if (!fh->no_ts_) {
                if (ts_option_) {
                        recent_age_ = now();
                        recent_ = tcph->ts();
                        rtt_update(now() - tcph->ts_echo());
                        if (ts_resetRTO_ && (!ect_ || !ecn_backoff_ ||
                           !hdr_flags::access(pkt)->ecnecho())) {
                                // From Andrei Gurtov
                                //
                                // Don't end backoff if still in ECN-Echo with
                                // a congestion window of 1 packet.
                                t_backoff_ = 1;
                                ecn_backoff_ = 0; // osada
                        }
                }
                if (rtt_active_ && ackno > rtt_seq_) {
                        if (!ect_ || !ecn_backoff_ ||
                            !hdr_flags::access(pkt)->ecnecho()) {
                                // got an RTT sample, record it
                                /*
                                 * Don't end backoff if still in ECN-Echo with
                                 * a congestion window of 1 packet.
                                 * Fix from T. Kelly.
                                 */
                                // bugfix osada 2016-08-06
                                t_backoff_ = 1;
                                ecn_backoff_ = 0;
                        }
                        rtt_active_ = FALSE;
                        if (!ts_option_) rtt_update(now() - rtt_ts_);
                }
        }
        return;
```

# 発展
## タイムスタンプオプションの罠

上の修正プログラム中で登場する一部の変数の初期値に注意。

```tcl/lib/ns-defaults.tcl
Agent/TCP set timestamps_ false
Agent/TCP set ts_resetRTO_ false ;      # Added 2003/07/24.
                                        # Set to true to un-back-off RTO
                                        #   after any valid RTT measurement.
```

コメント文を読むと、「ts_resetRTO_がtrueだと、有効なRTT計測後にバックオフしない」と書いてあるけど、ソースコードを見ると、逆では？！

ということで、ご注意を。（これは、ほかの実装ではこういう動作するものがあるということを示唆しているのかな？）

ちなみに、Agent/TCP/FullTcpはAgent/TCPのサブクラスであり、これらの変数は継承しているので、ここで設定すれば有効になる。

# メモ
ECNを利用する場合は、挙動要調査です。

# 参考
ns-2でバイト単位でシミュレーションする
http://qiita.com/osada/items/aa08b5db6ae39f1464f6