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

More than 1 year has passed since last update.


1. はじめに

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

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

TcpAll20.0-cwnd.png

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


2. 環境構築


2.1 ns-3 (Network Simulator 3)

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

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


2.2 python

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


  • Python 2.7.11

  • NumPy 1.10.4

  • matplotlib 1.5.1


3. TCPにおける輻輳制御


3.1 概要

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

model.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$の調整戦略を,本記事では輻輳制御と呼びます.

 輻輳制御は,輻輳状態4(Congestion state)と,アルゴリズム(Congestion control algorithm)という2つの要素によって決まります.輻輳状態は,OPENDISORDERRECOVERLOSS等,ネットワークの混雑状態を表します.アルゴリズムは,各輻輳状態における$cwnd$の更新方法を表します.


3.2 輻輳状態(Congestion state)

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

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

アルゴリズム
TypeId
ソースコード

NewReno
TcpNewReno
tcp-congestion-ops.cc

HighSpeed
TcpHighSpeed
tcp-highspeed.cc

Hybla
TcpHybla
tcp-hybla.cc

Westwood
TcpWestwood
tcp-westwood.cc

Westwood+
TcpWestwoodPlus
tcp-westwood.cc

Vegas
TcpVegas
tcp-vegas.cc

Scalable
TcpScalable
tcp-scalable.cc

Veno
TcpVeno
tcp-veno.cc

Bic
TcpBic
tcp-bic.cc

YeAH
TcpYeah
tcp-yeah.cc

Illinois
TcpIllinois
tcp-illinois.cc

H-TCP
TcpHtcp
tcp-htcp.cc

 例えば,最もメジャーな輻輳制御アルゴリズムの1つであるNewReno(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)$, $cwnd \gets ssth +3$

RECOVERY状態で,重複ACKを受信したとき
$ \displaystyle cwnd \gets cwnd + 1$

RECOVERY状態で,新規ACKを受信し,OPEN状態に遷移したとき
$ cwnd \gets ssth$

LOSS状態に遷移したとき
$ cwnd \gets smss$, $ssth \gets max(\mathit{inflight} /2, 2 \cdot smss)$

 ここで,$\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に対するACK2を受信するため,上記の更新を4回行います.

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


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

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


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

 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は,それぞれトレース対象の初期値を取り扱う際に一時的に使用される変数を表します.


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*()の定義を行います.ここでは,トレース対象の1つであるBytesInFlightを例に解説します.


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において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()で,ネットワーク構成の設定を行います.詳細は公式マニュアルに譲り,ここではポイントのみ記載します.

network.png

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


コマンドライン引数

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


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()等のトレース設定関数(コールバック関数と,トレース対象を紐付ける関数)をスケジューリングします.


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.ccAddTraceSource()されています.よって,シナリオスクリプトに少し変更を加えるだけで,これらをトレース対象に追加することができます.以下では,その方法をご紹介します.


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

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

$ 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を追加します.


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()も,それぞれ追加します.


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()をスケジューリングします.


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をコンパイルできます.

$ ./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を作成します.

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

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


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$と,輻輳状態の変化をプロットしてみます.


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

 横軸は時間[s],縦軸は$cwnd$および$ssth$[segment]です.$cwnd$は実線,$ssth$は点線です.輻輳状態に応じて,色を塗り分けています.$OPEN$は青,$DISORDER$は緑,$RECOVERY$は黄色,そして$LOSS$は赤です.

 当初の想定以上に,各アルゴリズムの個性が色濃く出てくれました.


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

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


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

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

\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節参照)でしたので,輻輳が発生するタイミングとして不自然ではないです5.$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

TcpHybla020-cwnd-ack-rtt.png

TcpWestwood020-cwnd-ack-rtt.png

TcpWestwoodPlus020-cwnd-ack-rtt.png

TcpVegas020-cwnd-ack-rtt.png

TcpScalable020-cwnd-ack-rtt.png

TcpVeno020-cwnd-ack-rtt.png

TcpBic020-cwnd-ack-rtt.png

TcpYeah020-cwnd-ack-rtt.png

TcpIllinois020-cwnd-ack-rtt.png

TcpHtcp020-cwnd-ack-rtt.png


6. おわりに

 本記事では,ns-3を使ってTCPの輻輳制御をシミュレートし,pythonで可視化してみました.初心者なりに,TCPの雰囲気を掴むことができました.また,ns-3のサンプルシナリオの優秀さを再認識しました.

 今後は,CUBICCTCPのようなメジャーなアルゴリズムの実装や,Remyのような最新のアルゴリズムの実装に挑戦したいと思っています.あるいは,異なるアルゴリズム同士の競合を観察してみるのもいいかなと思っています.

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


参考

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





  1. ネットワークにおける混雑,的なイメージの言葉です. 



  2. 説明をシンプルにするため,本記事では遅延ACK(delayed acknowledgement)は考慮しません.遅延ACKは,複数のACKをまとめて送信することでネットワークの利用効率を向上させる方式です. 



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



  4. いわゆるTCPの状態遷移図(Finite state machine)とは異なります.状態遷移図は,コネクションの確立から切断までを対象としていますが,輻輳状態はコネクション確立(ESTABLISHED)中の輻輳の状態を対象としています. 



  5. たぶん.キューの分析等,もっと詳細な分析が必要だと思いますが力尽きました….