09.2.24

研究の背景 (1) オーバレイネットワーク
 IPネットワーク上に論理的に構築されるネットワーク
 アプリケーション指向な上位層ネットワーク

 オーバレイネットワークにおけるトラヒック制御
 例：オーバレイルーティング ネットワーク性能に基いてトラヒックを経由させるオーバレイレベルの経路を選択

オーバレイネットワークの密度にスケーラブルなネットワーク計測手法

 ユーザ性能 (遅延時間、スループット等) の向上、障害箇所の迂回 オーバレイノード間のネットワーク性能の把握が重要○長谷川剛 村田正幸
大阪大学2

2008年12月IN研究会 08.12.12

研究の背景 (2)

研究の目的

 オーバレイネットワークにおける計測 オーバレイネットワークにおけるネットワーク計測手法の提案

 N個のオーバレイノードがあると、N2本のオーバレイパスが存在 計測精度をできるだけ損わない オーバレイノード数の増加にともない計測が困難に

 計測数を大幅に削減

 複数のオーバレイパスが同じIP経路を共有

 計測の競合による精度低下を回避

 お互いが経路の共有に気がつかない場合がある
 計測によるネットワーク負荷の増大、計測の競合による精度の低下

 オーバレイネットワークの密度に着目
 密度：IPルータ数に対するオーバレイノード数の比率

 計測オーバヘッドの削減手法

 密度に対してスケーラブルな計測手法

 ASレベル/IPレベルの(完全な)トポロジ情報が必要
 把握するためにはノード間での情報交換が必要
 N2 のオーバヘッドが発生

 計測の量と計測精度はトレードオフの関係
 計測の量を削減すると、計測精度が犠牲になる3

2008年12月IN研究会 08.12.12

4

2008年12月IN研究会 08.12.12

対象とするオーバレイネットワーク

オーバレイネットワークの密度 エンドホスト上だけではなく、ネットワーク内に IPルータ数に対するオーバレイノード数の比率

ノードが設置されるオーバレイネットワーク

 密度が小さい場合
 オーバレイパスのホップ数が大きい→計測精度は低い
 オーバレイパス上に他のオーバレイノードが存在する確率は低い
 オーバレイパスの経路共有は少ない

オーバレイノード

オーバレイノード
5IPルータ

IPルータ

エンドホスト

2008年12月IN研究会 08.12.126

2008年12月IN研究会 08.12.12

1

09.2.24

オーバレイネットワークの密度

オーバレイパスの経路共有

 IPルータ数に対するオーバレイノード数の比率

 共有パターン (1) 密度が大きい場合

 パスの途中に他のオーバレイノードが存在する場合

 オーバレイパスのホップ数が小さい→計測精度は高い

 パスACとパスAB、パスACとパスBCが同じ経路を共有

 オーバレイパス上に他のオーバレイノードが存在する確率は高い

 AがCまでtracerouteを実行することで検知可能

 オーバレイパスの経路共有は多い

オーバレイノード パスACの計測を、パスABとパスBCの計測結果から推定することで、競合を回避可能

IPルータ

オーバレイノード
IPルータ

ACB

7

2008年12月IN研究会 08.12.12

8

2008年12月IN研究会 08.12.12

オーバレイパスの経路共有

オーバレイパスの経路共有

 共有パターン (2) 共有パターン (3) パスの途中まで経路を共有する場合

 パスの途中部分のみが共有されている場合

 パスABとパスACが途中まで同じ経路を共有

 パスACとパスBDが途中の経路のみを共有

 AがBとCまでtracerouteを実行することで検知可能

 AとBが情報交換をしない限り、検知は不可能

 Aが、パスABとパスACの計測を逐次的に行うことで計測の競合を回避可能

オーバレイノード
IPルータ

A N2の情報交換をして初めて共有を知ることができる
共有パス数を推定することで、計測の競合を確率的に回避可能
オーバレイノード

IPルータ

A
DC

C

B
B

9

2008年12月IN研究会 08.12.12

10

2008年12月IN研究会 08.12.12

計測数削減手法

計測数削減手法 (2) 共有パターン (1) に対する手法

 部分パスの計測結果から全体の計測結果を推定
 RTT：和、帯域：最小値、廃棄率：1-(1-p1)(1-p2)

 前提
 オーバレイノードのIPアドレスは既知

A→C間の経路：
1(A), 2, 3(B), 4, 5, 6(C) オーバレイノードはtracerouteを実行可能

 手順
 オーバレイノードは他のオーバレイノードへtracerouteを実行
 他ノードからのtracerouteパケットが自ノードを通過する場合、そのパケットをキャプチャするA
1

2

A→C間の計測：(1) tracerouteを実行
A→B間：自分で行う
B→C間：Bから取得

A→C間の経路上に(2)経路途中のオーバレイノードはBが存在
tracerouteパケットをキャプチャする
B
3

4

5

C
6

B→C間の計測結果をAに通知

 送信・受信ノードを記録

 自ノードのtracerouteの結果、およびキャプチャした結果から計測するパス、計測結果を伝える相手を決定
11

2008年12月IN研究会 08.12.12

オーバレイノード
12ルータ

2008年12月IN研究会 08.12.122

09.2.24

計測数削減手法 (3)

計測数削減手法の評価
B→D間の経路:
3(B), 4(C), 5, 6(D)B→D間の経路上にCが存在 提案手法によって必要となる計測パス数を評価
 全てのノード間の計測結果を知るために必要な計測パス

数
A→D間の経路：
1(A), 2, 3(B), 4(C), 5, 6(D)A→D間の経路上にBが存在

A→D間の経路上にCが存在 フルメッシュ計測との場合と比較

 評価環境
A
12

B
3

C
45

D6

 ネットワークトポロジ
 Abilene-inspired、BA、ランダム (WAXMAN)

A→D間の計測：
A→B間：自分で行う
B→C間：Bから取得

B→D間の計測：
B→C間：自分で行う
C→D間：Cから取得
計測結果をAに通知

 ルータ数171、リンク数はルータ数の1倍、2倍、4倍

C→D間の計測結果をA、Bに通知

オーバレイノード13

 オーバレイノード
 ルータ数の10%、20%、40%、80%
 ランダムに選択ルータ

2008年12月IN研究会 08.12.12

計測数削減手法の評価 (2) ノード間の経路：ダイクストラ法により算出
14

2008年12月IN研究会 08.12.12

重複経路数の評価
 共有パターン (3) に対する手法
 部分的に経路を共有しているパス数 (重複経路数) がわかれば、それに応じて計測周期を設定しランダムに計測を行う
 周期2倍→競合確率はほぼ1/2倍
 計測の競合を確率的に回避 重複経路数が何に依存するかを明らかにする

ネットワークトポロジによらず計測パス数を1/30〜1/50に削減

密度がある程度以上になると、計測パス数は減少



経路の重なりが急激に増加するため



ノード数が増えても、ネットワーク規模が変化しなければ、計測パス数を小さく維持することが可能

 各オーバレイノードで観測可能な値に基いて重複経路数が推定可能になる

リンク数が増えると削減効果は小さくなる


経路の重なりが減るため

15

2008年12月IN研究会 08.12.12

重複経路数の評価 (2)162008年12月IN研究会 08.12.12

まとめと今後の課題
 まとめ
 オーバレイノード密度にスケーラブルなオーバレイパス計

測手法の基礎検討
 ネットワークトポロジにかかわらず、計測数を最大で1/50にすることが可能
 計測すべきパスの経路重複の発生頻度は、オーバレイノード密度に強く依存 今後の課題
 重複経路数はオーバレイ密度に強く依存 パスのホップ数にはそれほど依存しない

 密度が極端に高いと異なる傾向

 密度にかかわらず重複経路数を推定可能な指標
 計測手法の確立、性能評価
 計測手法を基にしたパス選択、障害回復手法

 計測パス数が減少することとの関連性を検討
17

2008年12月IN研究会 08.12.12

18

2008年12月IN研究会 08.12.12

3

09.2.24

予備スライドAbiline-inspired トポロジ
 実際のルータレベルのトポロジが基になっている
 ノード次数分布はべき乗則に従う

19

2008年12月IN研究会 08.12.1220

2008年12月IN研究会 08.12.12

BAトポロジCQR2009 Workshop

 アルゴリズムに基き人工的に生成

 IEEE Communications Society ノード次数分布はべき乗則に従う
[4] A. Barabasi and R. Albert, “Emergence of scaling in random networks,”
Science, vol. 286, pp. 509‒512, Oct. 1999.

2009 International Communications Qualityand Reliability (CQR) Workshop
 May 12-14, 2009
 The Naples Beach Hotel & Golf Club

851 Gulf Shore Boulevard NorthNaples, Florida 34102, USA Submission Deadline: 2008/12/15
 Will be extended to 2008/12/29

 Accepted papers will be includd in IEEE Explore http://www.ieee-cqr.org/21

2008年12月IN研究会 08.12.1222

2008年12月IN研究会 08.12.124