大規模ネットワークにおける バンド幅測定アルゴリズム

Presentation on theme: "大規模ネットワークにおける バンド幅測定アルゴリズム"— Presentation transcript:

1 大規模ネットワークにおける バンド幅測定アルゴリズム
長沼 翔、田浦 健次朗（東大）

2 イントロダクション バンド幅を知ることの意味
ネットワークの管理、運用、モニタリングのために 設計通りのバンド幅が出ているか・・・ 並列分散アプリケーションのチューニングパラメータとして 効率の良いファイル転送スケジュール・・・

3 イントロダクション バンド幅情報の二つの記述方法
バンド幅行列 N × N 行列 （N はネットワーク中のエンドホスト数） バンド幅マップ 重み付き有向グラフ

4 N × N 行列 イントロダクション バンド幅行列とは 行： 送信ノード 列： 受信ノード 要素： バンド幅の値 Snd ＼ Rcv A B
行： 送信ノード 列： 受信ノード 要素： バンド幅の値 Snd ＼ Rcv A B C - 1Mbps 3Mbps 5Mbps 2Mbps

5 重み付き有向グラフ イントロダクション バンド幅マップとは ノード： エンドホストやスイッチ エッジ： リンク（上下流）
ノード： エンドホストやスイッチ エッジ： リンク（上下流） コスト： バンド幅の値 6Mbps A 1Mbps 5Mbps 2Mbps sw B C 3Mbps 4Mbps

6 このネットワークの バンド幅情報は？ A sw B C 6Mbps A 1Mbps 5Mbps 2Mbps sw B C 3Mbps
Snd ＼ Rcv A B C - 1Mbps 3Mbps 5Mbps 2Mbps 5Mbps 2Mbps sw B C 3Mbps 4Mbps

7 一般的に情報量はバンド幅マップの方が多いが、バンド幅行列より取得することが難しい。
イントロダクション 行列とマップの比較 一般的に情報量はバンド幅マップの方が多いが、バンド幅行列より取得することが難しい。 分散アプリケーションの性能向上を追求するためにはバンド幅マップのような詳細な情報が必要。 1 Gbps D A E B sw sw F C 10 Gbps

8 一般的に情報量はバンド幅マップの方が多いが、バンド幅行列より取得することが難しい。
イントロダクション 行列とマップの比較 一般的に情報量はバンド幅マップの方が多いが、バンド幅行列より取得することが難しい。 分散アプリケーションの性能向上を追求するためにはバンド幅マップのような詳細な情報が必要。 1 Gbps これをバンド幅行列で表現すると、全要素が1Gbps となる D A E B sw sw F C 10 Gbps

9 一般的に情報量はバンド幅マップの方が多いが、バンド幅行列より取得することが難しい。
イントロダクション 行列とマップの比較 一般的に情報量はバンド幅マップの方が多いが、バンド幅行列より取得することが難しい。 分散アプリケーションの性能向上を追求するためにはバンド幅マップのような詳細な情報が必要。 矢印の通信を同時に行っても、どれも干渉せずに1Gbps 出ると予想がたてられる。 D A E B sw sw F C

10 大規模ネットワークのバンド幅マップを取得する
イントロダクション 本研究の目的 大規模ネットワークのバンド幅マップを取得する 分散アプリケーションのチューニングなどをする際の下地となる位置づけ 最終的に実装するシステムとしては、 入力：　ネットワークトポロジー 出力：　バンド幅マップ

11 発表の流れ イントロダクション 既存手法とその問題 新手法の提案と検証 まとめ

12 二つのエンドホスト間の通信スループットを測定する。最もよく使われるバンド幅測定ツールの一つ
既存手法の紹介 Iperf 二つのエンドホスト間の通信スループットを測定する。最もよく使われるバンド幅測定ツールの一つ 相手ホストにパケットを送信し続け、送受信できたバイトをかかった時間で割ることでバンド幅[bps]を得るという原理

13 難点 既存手法の紹介 Iperf の難点 二つのホスト間の経路中のボトルネックリンクの値以外は見えない そのリンクがどれなのかもわからない
A このような単純なネットワークでもバンド幅マップを構築するという目的は果たせない sw B C

14 既存手法の紹介 bhtree [sacsis2008]
トポロジーを入力し、バンド幅マップを出力するツール 複数のIperf を組み合わせた測定により単独のIperf の難点を克服し、さらに並列測定によって大規模ネットワークにも対応した A sw B C

15

16

17 既存手法の紹介 bhtree で残された課題
ツリーネットワークしか扱えない リンクのバンド幅は上下対称としている ネットワークの形にしたがった複雑な場合分けが多い 問題や実装を単純にするための仮定・設定だったが実ネットワークに適用するには無理がある 実ネットワークに適用可能なように考え直したい。実用的な結果を出したい 統一的なアルゴリズムにしたい

18 InTrigger2009の接続の簡略図 広島大、九州大、神戸大あたりにループが見える

19 九州大 <-> 千葉NII のバンド幅行列
InTrigger2009のバンド幅 九州大 <-> 千葉NII のバンド幅行列 Snd ＼ Rcv 九州大 千葉NII - 50.8Mbps 595Mbps

20 発表の流れ イントロダクション 既存手法とその問題 新手法の提案と検証 まとめ

21 システム ネットワークグラフは既知とする 提案手法 新手法の概要 入力： ネットワークグラフ
入力： ネットワークグラフ 出力： バンド幅マップ（入力のネットワークグ ラフの全エッジにバンド幅の値を割り 振ったもの） ネットワークグラフは既知とする これはtraceroute や既存のトポロジー推定手法で取得可能 [Shirai et al, HPDC2007]

22 各エッジ一つ一つに着目し、そのバンド幅を決定させるという手順をとることで、あらゆるネットワークにも適応
提案手法 新手法の概要 大枠のアルゴリズム 各エッジ一つ一つに着目し、そのバンド幅を決定させるという手順をとることで、あらゆるネットワークにも適応 Input: Network Graph G := (V, E) for each edge in E: 　　　determine_bw_of_edge(edge) endfor

23 これまでの手法ではバンド幅を測定するといっても何の値が得られるのかが明確ではなかった
提案手法 エッジのバンド幅の決定の仕方 これまでの手法ではバンド幅を測定するといっても何の値が得られるのかが明確ではなかった 何をして得られた結果をバンド幅とするかを定義する必要がある

24 一つのエッジに着目する。そのエッジを通過するようなIperf を全て同時に実行する。それぞれ得られた結果の和をそのエッジのバンド幅とする。
提案手法 本研究でのバンド幅の定義 一つのエッジに着目する。そのエッジを通過するようなIperf を全て同時に実行する。それぞれ得られた結果の和をそのエッジのバンド幅とする。 receivers: m nodes senders: n nodes Edge with a direction Iperfs: nm connections

25 以後、この定義に沿って決定した値が正しいバンド幅の値であるとし、話を進める
提案手法 本研究でのバンド幅の定義 妥当性 一本でもIperf を欠かすと、エッジのキャパシティを埋め切れないかもしれない 全てのIperf を以てしても埋め切れないキャパシティを持つエッジであっても、それを答えとする 以後、この定義に沿って決定した値が正しいバンド幅の値であるとし、話を進める

26 一つのエッジのバンド幅を求める度にシステム全体を導引することになってしまう 定義に反しない範囲で手間を削減する必要がある
提案手法 Naïve な方法 一つのエッジのバンド幅を求める度にシステム全体を導引することになってしまう 定義に反しない範囲で手間を削減する必要がある Input: Network Graph G := (V, E) for each edge in E: 　　　naïve_bundle_iperfs(edge) endfor

27 定義に沿った測定を各エッジに適用するnaïve な方法ではネットワークへの負荷と所要時間が多大に
提案手法 ここまでの話の流れ バンド幅測定の定義 定義に沿った測定を各エッジに適用するnaïve な方法ではネットワークへの負荷と所要時間が多大に 定義に反しない範囲でいかに処理を削減するか　←これが本手法の追求のしどころ

28 全Iperf を最初から全部流し始める必要はなく、一本ずつ加えていき、それまでの和が頭打ちになった本数で止めてもよい
これにより測定に伴うネットワークへの負荷軽減が期待できる

29 Bandwidth of (d->e) is
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 Saturated! ・・・ Bandwidth of (d->e) is

30 Bandwidth of (d->e) is
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

31 Bandwidth of (d->e) is
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

32 Bandwidth of (d->e) is
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 Saturated! ・・・ Bandwidth of (d->e) is

33 Bandwidth of (d->e) is
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

34 Bandwidth of (d->e) is
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

35 提案手法 アルゴリズム書き直し Input: Network Graph G := (V, E) for each edge in E:
　　　# naïve_bundle_iperfs(edge) 　　　selective_iperfs(edge) endfor

36 冗長なIperf 流を削減することで、どれ程ネットワークへの負荷を軽減できるか
提案手法 書き直したアルゴリズムの検証 冗長なIperf 流を削減することで、どれ程ネットワークへの負荷を軽減できるか ネットワーク中を往来するIperf 流本数を、naïve な手法と比較

37 以下の様な環境をシミュレータ上で再現 提案手法 検証環境 1Gbps 500Mbps 14 nodes 14 nodes 14 nodes

38 提案手法 検証結果 97% の削減

39 少々強引な設定を最初においたが、工夫次第で通用する見通しがある
提案手法 考察 少々強引な設定を最初においたが、工夫次第で通用する見通しがある Naïve な手法では冗長な手順が多数存在し、アルゴリズムの意味を崩さずにそれらを取り除くことができる 考えられる課題 実用可能なレベルまでコストを削減する工夫を様々な視点から考案する そもそもどれほどまで削減すれば実用可能だといえるか定量的に示す

40 発表の流れ イントロダクション 既存手法とその問題 新手法の提案と検証 まとめ

41 まとめ 求めるべきバンド幅マップを定式化し問題設定を明確にした
1)エッジのバンド幅を定義 2)定義通りの測定を全エッジについて実行するとい うnaïve なアルゴリズムを考案、これを正解とする Naïve なアルゴリズムでは現実的ではないため、処理量削減の工夫を加えていく必要がある 一つの案として冗長Iperf 流の削減を提案

42 今後の課題 様々な視点からnaïve な手法の（時空間共に）コスト削減の工夫を考案する コスト削減の定量的分析 実環境での実験と評価