Document

大規模ネットワークにおける
バンド幅測定アルゴリズム
長沼翔、田浦健次朗（東大）
イントロダクション
バンド幅を知ることの意味

ネットワークの管理、運用、モニタリングの
ために
• 設計通りのバンド幅が出ているか・・・

並列分散アプリケーションのチューニング
パラメータとして
• 効率の良いファイル転送スケジュール・・・
イントロダクション
バンド幅情報の二つの記述方法

バンド幅行列
• N × N 行列（N はネットワーク中のエンドホスト数）

バンド幅マップ
• 重み付き有向グラフ
イントロダクション
バンド幅行列とは

N × N 行列
• 行：
送信ノード
• 列：
受信ノード
• 要素：バンド幅の値
Snd ＼ Rcv A
B
C
A
-
1Mbps
1Mbps
B
3Mbps
-
3Mbps
C
5Mbps
2Mbps
-
イントロダクション
バンド幅マップとは

重み付き有向グラフ
• ノード：エンドホストやスイッチ
• エッジ：リンク（上下流） 1Mbps
• コスト：バンド幅の値
2Mbps
6Mbps
A
5Mbps
sw
B
C
3Mbps
4Mbps
A
このネットワークの
バンド幅情報は？
sw
B
C
6Mbps
Snd ＼ Rcv A
B
C
A
-
1Mbps
1Mbps
B
3Mbps
-
3Mbps
C
5Mbps
2Mbps
-
1Mbps
2Mbps
A
5Mbps
sw
B
C
3Mbps
4Mbps
イントロダクション
行列とマップの比較


一般的に情報量はバンド幅マップの方が多いが、
バンド幅行列より取得することが難しい。
分散アプリケーションの性能向上を追求するた
めにはバンド幅マップのような詳細な情報が必
要。
1 Gbps
D
A
sw
B
C
E
sw
10 Gbps
F
イントロダクション
行列とマップの比較


一般的に情報量はバンド幅マップの方が多いが、
バンド幅行列より取得することが難しい。
分散アプリケーションの性能向上を追求するた
めにはバンド幅マップのような詳細な情報が必
要。
1 Gbps
sw
B
C
これをバンド幅行
列で表現すると、
全要素が1Gbps
E となる
D
A
sw
10 Gbps
F
イントロダクション
行列とマップの比較


一般的に情報量はバンド幅マップの方が多いが、
バンド幅行列より取得することが難しい。
分散アプリケーションの性能向上を追求するた
めにはバンド幅マップのような詳細な情報が必
要。
sw
B
C
矢印の通信を同
時に行っても、ど
れも干渉せずに
E 1Gbps 出ると予
想がたてられる。
D
A
sw
F
イントロダクション
本研究の目的

大規模ネットワークのバンド幅マップを取
得する
• 分散アプリケーションのチューニングなどをす
る際の下地となる位置づけ

最終的に実装するシステムとしては、
• 入力：ネットワークトポロジー
• 出力：バンド幅マップ
発表の流れ
イントロダクション
 既存手法とその問題
 新手法の提案と検証
 まとめ

既存手法の紹介
Iperf

二つのエンドホスト間の通信スループット
を測定する。最もよく使われるバンド幅測
定ツールの一つ

相手ホストにパケットを送信し続け、送受
信できたバイトをかかった時間で割ること
でバンド幅[bps]を得るという原理
既存手法の紹介
Iperf の難点

難点
• 二つのホスト間の経路中のボトルネックリンク
の値以外は見えない
• そのリンクがどれなのかもわからない
A
このような単純なネット
ワークでもバンド幅マッ
プを構築するという目
的は果たせない
sw
B
C
既存手法の紹介
bhtree [sacsis2008]
トポロジーを入力し、バンド幅マップを出力
するツール
 複数のIperf を組み合わせた測定により単
独のIperf の難点を克服し、さらに並列測
定によって大規模ネットワークにも対応し
A
た

sw
B
C
既存手法の紹介
bhtree で残された課題



ツリーネットワークしか扱えない
リンクのバンド幅は上下対称としている
ネットワークの形にしたがった複雑な場合分けが多い
• 問題や実装を単純にするための仮定・設定だったが実
ネットワークに適用するには無理がある
実ネットワークに適用可能なように考え直したい。
実用的な結果を出したい
 統一的なアルゴリズムにしたい

InTrigger2009の接続の簡略図
広島大、九州大、神戸大あたりに
ループが見える
InTrigger2009のバンド幅
九州大 <-> 千葉NII のバンド幅行列
Snd ＼ Rcv
九州大
千葉NII
九州大
-
50.8Mbps
千葉NII
595Mbps
-
発表の流れ
イントロダクション
 既存手法とその問題
 新手法の提案と検証
 まとめ

提案手法
新手法の概要

システム
• 入力：ネットワークグラフ
• 出力：バンド幅マップ（入力のネットワークグ
ラフの全エッジにバンド幅の値を割り
振ったもの）

ネットワークグラフは既知とする
• これはtraceroute や既存のトポロジー推定手
法で取得可能 [Shirai et al, HPDC2007]
提案手法
新手法の概要

大枠のアルゴリズム
Input: Network Graph G := (V, E)
for each edge in E:
determine_bw_of_edge(edge)
endfor

各エッジ一つ一つに着目し、そのバンド幅
を決定させるという手順をとることで、あら
ゆるネットワークにも適応
提案手法
エッジのバンド幅の決定の仕方
これまでの手法ではバンド幅を測定すると
いっても何の値が得られるのかが明確で
はなかった
 何をして得られた結果をバンド幅とするか
を定義する必要がある

提案手法
本研究でのバンド幅の定義

一つのエッジに着目する。そのエッジを通
過するようなIperf を全て同時に実行する。
それぞれ得られた結果の和をそのエッジ
のバンド幅とする。
receivers:
m nodes
senders:
n nodes
Iperfs:
nm connections
提案手法
本研究でのバンド幅の定義

妥当性
• 一本でもIperf を欠かすと、エッジのキャパシ
ティを埋め切れないかもしれない
• 全てのIperf を以てしても埋め切れないキャパ
シティを持つエッジであっても、それを答えとす
る

以後、この定義に沿って決定した値が正し
いバンド幅の値であるとし、話を進める
提案手法
Naïve な方法
Input: Network Graph G := (V, E)
for each edge in E:
naïve_bundle_iperfs(edge)
endfor
一つのエッジのバンド幅を求める度にシス
テム全体を導引することになってしまう
 定義に反しない範囲で手間を削減する必
要がある

提案手法
ここまでの話の流れ
バンド幅測定の定義
 定義に沿った測定を各エッジに適用する
naïve な方法ではネットワークへの負荷と
所要時間が多大に
 定義に反しない範囲でいかに処理を削減
するか ←これが本手法の追求のしどころ

提案手法
冗長なIperf 流の削減
全Iperf を最初から全部流し始める必要は
なく、一本ずつ加えていき、それまでの和
が頭打ちになった本数で止めてもよい
 それ以降のまだ流し始めていないIperf 流
については、バンド幅0が観測されたとし、
仮想的に流し終えたと考えられる


これにより測定に伴うネットワークへの負
荷軽減が期待できる
Target edge: d -> e
Iperfs
routing
flowing
I0
a -> b -> c -> d -> e -> f -> g
I1
h -> i -> c -> d -> e -> f -> j
I2
l -> m -> n -> o -> c -> d -> e -> f -> p
I3
q-> m -> n -> r -> d -> e -> f -> g
I4
r -> t -> o -> c -> d -> e -> u -> p
I5
s -> m -> n -> v -> o -> c -> d -> e -> f -> j
I6
w -> d -> e -> z
I7
x -> d -> e -> z
I8
k -> t -> c -> d -> e -> f -> z
I9
u -> c -> d -> e -> f -> z
・
・
・
Bandwidth of (d->e) is
I
all Iperfs
Saturated!
flowing
Target edge: d -> e
Iperfs
routing
flowing
I0
a -> b -> c -> d -> e -> f -> g
I1
h -> i -> c -> d -> e -> f -> j
I2
l -> m -> n -> o -> c -> d -> e -> f -> p
I3
q-> m -> n -> r -> d -> e -> f -> g
I4
r -> t -> o -> c -> d -> e -> u -> p
I5
s -> m -> n -> v -> o -> c -> d -> e -> f -> j
I6
w -> d -> e -> z
I7
x -> d -> e -> z
I8
k -> t -> c -> d -> e -> f -> z
I9
u -> c -> d -> e -> f -> z
・
・
・
Bandwidth of (d->e) is
I
all Iperfs
flowing
Target edge: d -> e
Iperfs
routing
flowing
I0
a -> b -> c -> d -> e -> f -> g
I1
h -> i -> c -> d -> e -> f -> j
I2
l -> m -> n -> o -> c -> d -> e -> f -> p
I3
q-> m -> n -> r -> d -> e -> f -> g
I4
r -> t -> o -> c -> d -> e -> u -> p
I5
s -> m -> n -> v -> o -> c -> d -> e -> f -> j
I6
w -> d -> e -> z
I7
x -> d -> e -> z
I8
k -> t -> c -> d -> e -> f -> z
I9
u -> c -> d -> e -> f -> z
・
・
・
Bandwidth of (d->e) is
0
0
0
0
I
all Iperfs
flowing
Target edge: d -> e
Iperfs
routing
flowing
I0
a -> b -> c -> d -> e -> f -> g
I1
h -> i -> c -> d -> e -> f -> j
I2
l -> m -> n -> o -> c -> d -> e -> f -> p
I3
q-> m -> n -> r -> d -> e -> f -> g
I4
r -> t -> o -> c -> d -> e -> u -> p
I5
s -> m -> n -> v -> o -> c -> d -> e -> f -> j
I6
w -> d -> e -> z
I7
x -> d -> e -> z
I8
k -> t -> c -> d -> e -> f -> z
I9
u -> c -> d -> e -> f -> z
・
・
・
Bandwidth of (d->e) is
0
0
Saturated!
I
all Iperfs
flowing
0
0
Target edge: d -> e
Iperfs
routing
flowing
I0
a -> b -> c -> d -> e -> f -> g
I1
h -> i -> c -> d -> e -> f -> j
I2
l -> m -> n -> o -> c -> d -> e -> f -> p
I3
q-> m -> n -> r -> d -> e -> f -> g
I4
r -> t -> o -> c -> d -> e -> u -> p
I5
s -> m -> n -> v -> o -> c -> d -> e -> f -> j
I6
w -> d -> e -> z
I7
x -> d -> e -> z
I8
k -> t -> c -> d -> e -> f -> z
I9
u -> c -> d -> e -> f -> z
・
・
・
Bandwidth of (d->e) is
I
all Iperfs
0
0
0
0
0
0
flowing
Target edge: d -> e
Iperfs
routing
flowing
I0
a -> b -> c -> d -> e -> f -> g
I1
h -> i -> c -> d -> e -> f -> j
I2
l -> m -> n -> o -> c -> d -> e -> f -> p
I3
q-> m -> n -> r -> d -> e -> f -> g
I4
r -> t -> o -> c -> d -> e -> u -> p
I5
s -> m -> n -> v -> o -> c -> d -> e -> f -> j
I6
w -> d -> e -> z
I7
x -> d -> e -> z
I8
k -> t -> c -> d -> e -> f -> z
I9
u -> c -> d -> e -> f -> z
・
・
・
Bandwidth of (d->e) is
I
all Iperfs
0
flowing
0
0
0
0
0
 I 0  I1  I 3  I 4
提案手法
アルゴリズム書き直し
Input: Network Graph G := (V, E)
for each edge in E:
# naïve_bundle_iperfs(edge)
selective_iperfs(edge)
endfor
提案手法
書き直したアルゴリズムの検証
冗長なIperf 流を削減することで、どれ程
ネットワークへの負荷を軽減できるか
 ネットワーク中を往来するIperf 流本数を、
naïve な手法と比較

提案手法
検証環境

以下の様な環境をシミュレータ上で再現
1Gbps
14 nodes
14 nodes
500Mbps
14 nodes
14 nodes
14 nodes
15 nodes
提案手法
検証結果
traversed streams
16000
14000
12000
97% の削減
10000
8000
6000
4000
2000
0
naïve_bundle_iperfs
selective_iperfs
提案手法
考察

少々強引な設定を最初においたが、工夫
次第で通用する見通しがある
• Naïve な手法では冗長な手順が多数存在し、
アルゴリズムの意味を崩さずにそれらを取り
除くことができる

考えられる課題
• 実用可能なレベルまでコストを削減する工夫
を様々な視点から考案する
• そもそもどれほどまで削減すれば実用可能だ
といえるか定量的に示す
発表の流れ
イントロダクション
 既存手法とその問題
 新手法の提案と検証
 まとめ

まとめ

求めるべきバンド幅マップを定式化し問題設定
を明確にした
• 1)エッジのバンド幅を定義
• 2)定義通りの測定を全エッジについて実行するとい
うnaïve なアルゴリズムを考案、これを正解とする

Naïve なアルゴリズムでは現実的ではないため、
処理量削減の工夫を加えていく必要がある
• 一つの案として冗長Iperf 流の削減を提案
今後の課題
様々な視点からnaïve な手法の（時空間共
に）コスト削減の工夫を考案する
 コスト削減の定量的分析
 実環境での実験と評価


Download Report