GT-ITM をビルドして使ってみる

はじめに

GT-ITM¹ とは，トランジット・スタブ・モデル (TS モデル)² を含むいくつかのモデルに基づくネットワークトポロジーを生成するツールです．
TS モデルの論文² は結構古いですが，引用数が 2000 を超える論文です．
この論文を知らないとモグリの研究者にみられてしまうので，ネットワーク関連の研究者の皆様はぜひおさえておきましょう．
以下の図 (GT-ITM のドキュメント¹ から引用) は TS モデルの概要を表しています．

ビルド

公式のサイト¹ からダウンロードできる tarball には，Soralis と SunOS 用の静的ライブラリのみしか含まれておらず，最近の OS だとビルドすることができません．
インターネットで検索してみると，ネットワークシミュレータの ns-2 は GT-ITM を含んでおり，その中に汎用の静的ライブラリ libgb.a が含まれていることがわかりました．
今回は，ns-2 の中の GT-ITM を拝借してビルドします．

ns-2 のダウンロード: https://sourceforge.net/projects/nsnam/files/latest/download

ダウンロードしたアーカイブを展開すると，gt-itm というディレクトリが見つかります．

ns-allinone-2.35
├── INSTALL.WIN32
├── README
├── bin
├── cweb
├── dei80211mr-1.1.4
├── gt-itm
├── install
├── nam-1.15
├── ns-2.35
├── otcl-1.14
├── sgb
├── tcl8.5.10
├── tclcl-1.20
├── tk8.5.10
├── xgraph-12.2
└── zlib-1.2.3

このディレクトリだけを抜き出して，ビルドします．
ただし，結構古いツールなのでイマドキの gcc を使うとビルドできません．
gcc-4.9 を使いましょう．
macOS なら brew install gcc@4.9 でインストールできます．
任意の gcc を使うために，Makefile 中の CC = gcc の指定を消します．

gt-itm/src/Makefile

--- Makefile	2018-10-31 21:55:35.000000000 +0900
+++ Makefile	2018-10-31 21:55:48.000000000 +0900
@@ -17,7 +17,6 @@
 BDIR = ../bin
 
 CFLAGS = -I$(IDIR) -L$(LDIR) $(SYS) $(BSDF)
-CC = gcc 
 
 GO = itm.o geog.o ts.o dfs.o
 CO = sgb2alt.o 

eval.c のインクルードを修正します．

gt-itm/src/eval.c

--- eval.c	2018-10-31 21:57:58.000000000 +0900
+++ eval.c	2018-10-31 21:58:08.000000000 +0900
@@ -5,7 +5,7 @@
  */
 
 #include <stdio.h>
-#include <malloc.h>
+#include <stdlib.h>
 #include "gb_graph.h"
 #include "gb_dijk.h"
 #include "eval.h"

ビルドします．

cd gt-itm/src
export CC=gcc-4.9 && make

これで無事ビルドできました．
gt-itm/bin の中に 3 つのバイナリが生成されているはずです．

使い方

ts100

# <method keyword> <number of graphs> [<initial seed>]
# <# stubs/trans node> <#rand. t-s edges> <#rand. s-s edges>
# <n> <scale> <edgemethod> <alpha> [<beta>] [<gamma>]
# number of nodes = 1x4x(1+3x8) = 100
ts 10 47
3 0 0
1 20 3 0.5 1.0 
4 20 3 0.6 1.0
8 10 3 0.42 1.0

上記の例は TS モデルに基づくネットワークトポロジを生成するファイルです．
各行は以下のような構成になっています．

[# comment line]
<method keyword> <# graphs> [<initial seed>]
<# stub domains/transit> <# extra transit-stub edges> <# extra stub-stub edges>
<# transit domains> <scale> <edgemethod> <alpha> [<beta> <gamma>]
<# nodes/transit domain> <scale> <edgemethod> <alpha> [<beta> <gamma>]
<# nodes/stab domain> <scale> <edgemethod> <alpha> [<beta> <gamma>]

例のネットワークだと，トランジットノードあたりのスタブドメイン数が 3，トランジットドメイン数が 1，トランジットドメインあたりのノード数が 4，スタブドメインあたりのノード数が 8 なので，ルーターの総数は 1 × 4 × (3 × 8 + 1) = 100 になります．

ネットワークトポロジは以下のコマンドで生成することができます．

./itm ts100

生成が完了すると，ts100-[0-9].gb というファイルが生成されます．

TS モデル以外のネットワークトポロジを生成する方法については，ツールに付属のドキュメントを参照してください．
ここでは割愛します．

可視化

生成されたネットワークトポロジを可視化してみます．
ts100-[0-9].gb のファイル内容を見てもトポロジをあまり理解することができないので，sgb2alt コマンドを使ってわかりやすい形式に変換します．

./sgb2alt ts100-0.gb ts100-0.alt

例えば，上記のコマンドを実行すると，ts100-0.alt というファイルが生成されます．

Python の NetworkX と Matplotlib というライブラリを用いて可視化してみます．

import argparse

import networkx as nx
import matplotlib.pyplot as plt


def main():
    parser = argparse.ArgumentParser()
    parser.add_argument('alt_file', type=argparse.FileType('r'), metavar='<alt file>')
    args = parser.parse_args()

    graph = nx.Graph()
    d = {}

    for line in args.alt_file:
        w = line.strip().split()
        if len(w) == 4:
            a, b, _, _ = line.strip().split()
            if b[0] in ('T', 'S'):
                d[a] = b
            else:
                graph.add_edge(d[a], d[b])

    nx.draw_networkx(graph, node_size=32, width=0.5, font_size=4)
    plt.savefig('graph.pdf')


if __name__ == '__main__':
    main()

上記のプログラムを altvis.py という名前で保存し，下記のように実行すると graph.pdf が生成されます．

python3 altvis.py ts100-0.alt

ルーターの総数が 2080 となる別のネットワークで可視化してみた結果は以下のとおりです．

1. Modeling Topology of Large Internetworks, https://www.cc.gatech.edu/projects/gtitm/ ↩ ↩² ↩³

2. E. W. Zegura, K. L. Calvert, and S. Bhattacharjee, “How to model an internetwork,” in Proceedings of IEEE INFOCOM ’96. Conference on Computer Communications, 1996, vol. 2, pp. 594–602 vol.2. ↩ ↩²