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

## はじめに

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

![Screen Shot 2018-10-31 at 21.11.15.png](https://qiita-image-store.s3.amazonaws.com/0/95900/17fdcef0-ab08-cedc-66f8-7e2c3c0ff7c3.png)

## ビルド

公式のサイト[^GTITM] からダウンロードできる 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` の指定を消します．

```diff: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` のインクルードを修正します．

```diff: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"
```

ビルドします．

```bash
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 になります．

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

```bash
./itm ts100
```

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

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

## 可視化

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

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

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

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

```python
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` が生成されます．

```bash
python3 altvis.py ts100-0.alt
```

<img width="1251" alt="Screen Shot 2018-11-01 at 5.17.42.png" src="https://qiita-image-store.s3.amazonaws.com/0/95900/9c5483c9-70c0-a99b-2fbb-3c3e7fa3ab21.png">

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

<img width="1331" alt="Screen Shot 2018-11-02 at 17.29.27.png" src="https://qiita-image-store.s3.amazonaws.com/0/95900/bf68e686-1698-74b1-1035-451477aeb5c7.png">


[^Zegra]: 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.

[^GTITM]: Modeling Topology of Large Internetworks, <https://www.cc.gatech.edu/projects/gtitm/>