大規模ネットワークにおける 効率的なバンド幅マップ構築アルゴリズム 東京大学 長沼翔，田浦健次朗

はじめに バンド幅の情報を利用するアプリケーション 並列分散アプリケーションのチューニング 最適なファイル転送スケジュール ネットワーク性能を考慮した負荷分散 ネットワークの管理、運用、モニタリング 高負荷な箇所の特定 可用帯域の確認 など多様化

広く使われている多ノード環境のバンド幅分布の表記方法 はじめに バンド幅行列 広く使われている多ノード環境のバンド幅分布の表記方法 環境U 環境U のバンド幅行列 A B snd＼rcv A B C D - 1Gbps 2Gbps 3Gbps C D

実際のトポロジー上の中間エッジ情報の欠落 中間エッジ： エンドホストに直に接続していないエッジ はじめに バンド幅行列の限界 実際のトポロジー上の中間エッジ情報の欠落 中間エッジ： エンドホストに直に接続していないエッジ 環境U 環境U のバンド幅行列 A B snd＼rcv A B C D - 1Gbps 2Gbps 3Gbps 2 1 10 3 4 C D

不正確なチューニング 不十分な管理情報 など はじめに バンド幅行列の問題 ファイル転送の衝突によるバンド幅低下 未使用のままの豊富なバンド幅 不十分な管理情報 情報の欠落 など

これらの問題を解決するためにはバンド幅マップを求めることが必要。 はじめに バンド幅マップ これらの問題を解決するためにはバンド幅マップを求めることが必要。 ネットワークトポロジーの全てのエッジにそのバンド幅の値が振られた情報 一般に、向きを考える。 バンド幅非対称のリンク A B 2 1 10 3 4 C D

並列分散アプリケーションのチューニングをする際の下地となる位置づけ はじめに 本研究の目的と貢献 バンド幅マップ構築アルゴリズムの考案 中間エッジのバンド幅 高速でスケーラブル 並列分散アプリケーションのチューニングをする際の下地となる位置づけ

発表の流れ はじめに 関連手法 提案手法 実験 まとめ

関連手法 Network Weather Service グリッド環境で広く用いられるネットワーク監視ツール 環境中の全エンドホストで起動し、End-to-End バンド幅測定を全ての組み合わせについて一つずつ行う。 O(N2) バンド幅測定の衝突を避けるため 出力はバンド幅行列

関連手法 Network Weather Service の問題 バンド幅行列しか得られない。 構築に時間がかかり、スケールもしない O(N2)

Network Weather Service の拡張 関連手法 TopoMon Network Weather Service の拡張 ネットワークトポロジーとバンド幅行列をNWS によって測定し、それらよりバンド幅マップを求め、出力する。

関連手法 TopoMon の仕組み 環境U A B 2 1 10 3 4 A B C D C D snd＼rcv A B C D - snd＼rcv A B C D - 1Gbps 2Gbps 3Gbps C D

関連手法 TopoMon の仕組み 環境U A B 2 1 10 3 4 A B C D 1 1 C D snd＼rcv A B C D - 1 1 snd＼rcv A B C D - 1Gbps 2Gbps 3Gbps C D

関連手法 TopoMon の仕組み 環境U A B 2 1 10 3 4 A B C D 1 1 1 1 C D snd＼rcv A B C 1 1 snd＼rcv A B C D - 1Gbps 2Gbps 3Gbps 1 1 C D

関連手法 TopoMon の仕組み 環境U A B 2 1 10 3 4 A B C D 1 1 1 1 1 C D snd＼rcv A B 1 1 snd＼rcv A B C D - 1Gbps 2Gbps 3Gbps 1 1 1 C D

関連手法 TopoMon の仕組み 環境U A B 2 1 10 3 4 A B C D 1 2 1 2 2 2 3 3 3 3 C D snd＼rcv A B C D - 1Gbps 2Gbps 3Gbps 2 2 3 3 3 3 C D

形としてはバンド幅マップを求めているが、いくつかの中間エッジのバンド幅の情報が欠落している 関連手法 TopoMon の問題 形としてはバンド幅マップを求めているが、いくつかの中間エッジのバンド幅の情報が欠落している 構築に時間がかかり、スケールもしない O(N2)

ホスト数N に対してO(N2) であり、実行に時間がかかりスケールしない 関連手法 関連手法の問題点まとめ 中間エッジを意識して測定していない 大きなバンド幅を持つエッジはボトルネックリンクに隠れてしまうため測定できない ホスト数N に対してO(N2) であり、実行に時間がかかりスケールしない 我々の目標で対象としている大規模分散環境に対して使用することができない

発表の流れ はじめに 関連手法 提案手法 実験 まとめ

実装 前提 提案手法 概要 入力： ネットワークトポロジー 出力： バンド幅マップ ネットワークトポロジー情報 既存のトポロジー推定手法で容易に取得可能　[sirai et al, HPDC2007]

提案手法 課題の確認 中間エッジのバンド幅測定 多対多協調のバンド幅測定で実現 高速化 グラフ分割による測定の並列化で実現

発表の流れ はじめに 関連手法 提案手法 中間エッジのバンド幅測定 高速化 実験 まとめ

ネットワーク中のあるエッジ et の測り方 提案手法 中間エッジのバンド幅測定 (1/4) 経路中に et を含む通信ホストペアを列挙

この測り方の意味 提案手法 中間エッジのバンド幅測定 (2/4) 一対一のバンド幅測定では測ることのできない大きなバンド幅を持つエッジは、大勢のネットワークストリームでそのキャパシティを飽和させて測定する。 Receivers Bandwidth of et et Senders

Measurement of et := (s -- u) b c Pair Route Stream (a, h) a – p – q – s – u – h (b, h) b – t – q – s – u – h (c, h) c – t – q – s – u – h (d, h) d – s – u – h (e, h) e – s – u – h (f, h) f – r – s – u – h (g, h) g – r – s – u – h (a, i) a – p – q – s – u – i (b, i) b – t – q – s – u – i (c, i) c – t – q – s – u – i a t p q d r s g e f i u h j v ・・・ ・・・ l k この時の発生しているトラフィック量(bps) の総和が et のバンド幅

このままではネットワークにかかる負荷が大きいため、改善を行う。 提案手法 中間エッジのバンド幅測定 (3/4) このままではネットワークにかかる負荷が大きいため、改善を行う。 et　を飽和させるための必要最小限のペアを用いるようにしたい。

ネットワーク中のあるエッジ et の測り方（改め） 提案手法 中間エッジのバンド幅測定 (4/4) ネットワーク中のあるエッジ et の測り方（改め） 経路中に et を含む通信ホストペアを列挙 1 ペアずつストリームを流し始める。あるストリームを流した時にバンド幅の総和に変化がなかった場合、それまでに共通して登場するパスを含むものは、バンド幅0の仮想的なストリームが既に流れているとする。 列挙した全てのペア間でバンド幅測定を実行している状態で、その時のそれらの合計が et のバンド幅

Measurement of et := (s -- u) b c Pair Route Stream (a, h) a – p – q – s – u – h (b, h) b – t – q – s – u – h (c, h) c – t – q – s – u – h (d, h) d – s – u – h (e, h) e – s – u – h (f, h) f – r – s – u – h (g, h) g – r – s – u – h (a, i) a – p – q – s – u – i (b, i) b – t – q – s – u – i (c, i) c – t – q – s – u – i a t p q d r s g e f i u h j v ・・・ l k Total BW # of streams

Measurement of et := (s -- u) b c Pair Route Stream (a, h) a – p – q – s – u – h (b, h) b – t – q – s – u – h (c, h) c – t – q – s – u – h (d, h) d – s – u – h (e, h) e – s – u – h (f, h) f – r – s – u – h (g, h) g – r – s – u – h (a, i) a – p – q – s – u – i (b, i) b – t – q – s – u – i (c, i) c – t – q – s – u – i a t p q d r s g e f i u h j v ・・・ l k Total BW Saturated. # of streams

Measurement of et := (s -- u) b c Pair Route Stream (a, h) a – p – q – s – u – h (b, h) b – t – q – s – u – h (c, h) c – t – q – s – u – h (d, h) d – s – u – h (e, h) e – s – u – h (f, h) f – r – s – u – h (g, h) g – r – s – u – h (a, i) a – p – q – s – u – i (b, i) b – t – q – s – u – i (c, i) c – t – q – s – u – i a t p q d r s g e f i u h j v ・・・ l k Total BW # of streams

Measurement of et := (s -- u) b c Pair Route Stream (a, h) a – p – q – s – u – h (b, h) b – t – q – s – u – h (c, h) c – t – q – s – u – h (d, h) d – s – u – h (e, h) e – s – u – h (f, h) f – r – s – u – h (g, h) g – r – s – u – h (a, i) a – p – q – s – u – i (b, i) b – t – q – s – u – i (c, i) c – t – q – s – u – i a t p q d r s g e f i u h j v ・・・ l k Total BW # of streams

Measurement of et := (s -- u) b c Pair Route Stream (a, h) a – p – q – s – u – h (b, h) b – t – q – s – u – h (c, h) c – t – q – s – u – h (d, h) d – s – u – h (e, h) e – s – u – h (f, h) f – r – s – u – h (g, h) g – r – s – u – h (a, i) a – p – q – s – u – i (b, i) b – t – q – s – u – i (c, i) c – t – q – s – u – i a t p q d r s g e f i u h j v ・・・ l k Total BW Saturated. # of streams

Measurement of et := (s -- u) b c Pair Route Stream (a, h) a – p – q – s – u – h (b, h) b – t – q – s – u – h (c, h) c – t – q – s – u – h (d, h) d – s – u – h (e, h) e – s – u – h (f, h) f – r – s – u – h (g, h) g – r – s – u – h (a, i) a – p – q – s – u – i (b, i) b – t – q – s – u – i (c, i) c – t – q – s – u – i a t p q d r s g e f i u h j v ・・・ l k Total BW # of streams

Measurement of et := (s -- u) b c Pair Route Stream (a, h) a – p – q – s – u – h (b, h) b – t – q – s – u – h (c, h) c – t – q – s – u – h (d, h) d – s – u – h (e, h) e – s – u – h (f, h) f – r – s – u – h (g, h) g – r – s – u – h (a, i) a – p – q – s – u – i (b, i) b – t – q – s – u – i (c, i) c – t – q – s – u – i a t p q d r s g e f i u ・・・ h j v ・・・ l k Total BW … Bandwidth of et # of streams

発表の流れ はじめに 関連手法 提案手法 中間エッジのバンド幅測定 高速化 実験 まとめ

中間エッジのバンド幅測定をトポロジー中の全てのエッジに適応すれば、目的に適うバンド幅マップを得ることができる(手法naïve_bwmap)。 提案手法 高速化の必要性 中間エッジのバンド幅測定をトポロジー中の全てのエッジに適応すれば、目的に適うバンド幅マップを得ることができる(手法naïve_bwmap)。 しかし、エッジの本数に比例した時間がかかりあまりスマートな手法とは言えず、スケーラブルとも言えない。 naïve_bwmap(G){ 　　　　for all et in G.E { 　　　　　　　　measure_internal_edge(et); 　　　　} }

互いに干渉しないバンド幅測定は並列に実行できる。 提案手法 並列測定による高速化 互いに干渉しないバンド幅測定は並列に実行できる。 干渉しないバンド幅測定 = それらに伴い発生するストリームが同じエッジを通らない しかし、どのような組でどのような手順で並列測定を行えば最適なものになるかという問題を、与えられたトポロジーから計算することは難しい。

入力トポロジーを非連結の複数の部分トポロジーに分割し、それらに並列に先のnaïve_bwmap を適用し、後にマージする。 提案手法 グラフ分割による並列化 入力トポロジーを非連結の複数の部分トポロジーに分割し、それらに並列に先のnaïve_bwmap を適用し、後にマージする。 問題の簡略化 近似解法 naïve_bwmap G0 G naïve_bwmap G1 naïve_bwmap G2

提案手法 Betweenness Centrality そのエッジがどれほどグラフの中央に位置しているかを表す値 |P|はグラフ中に存在するパスの数、|Pet |はそのうちエッジet を通るパスの数

提案手法 Betweenness によるグラフ分割 ネットワークをグラフの中心からバランス良く分割ができるという利点 naïve_bwmap を適用する部分トポロジーの各大きさがほぼ同じになり、階層の幅が広くなるため、全体の処理の並列度が上がる

G(V, E) , ・・・ ・・・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ : Dividing edge : Subgraph , … naïve_bwmap naïve_bwmap naïve_bwmap naïve_bwmap

ある階層では飽和させることのできるエッジでも、それより下の階層では飽和させることができない場合がある。 提案手法 分割後の測定の進め方 ある階層では飽和させることのできるエッジでも、それより下の階層では飽和させることができない場合がある。 ストリームを発生させる為に使えるエンドホスト数が少なくなるため ある階層で飽和しなかったエッジについては「未確定」とし、上の階層でもう一度測定対象とする。 上の階層であれば飽和する可能性が上がるため 上層のnaïve_bwmap では、未確定のエッジのみを測定対象とすればよい。

階層をボトムアップ式に扱う。各階層において、その階層にある部分トポロジー群にnaïve_bwmap を並列に適用する。 提案手法 アルゴリズム全体像 入力トポロジーを階層的に分割する。 階層をボトムアップ式に扱う。各階層において、その階層にある部分トポロジー群にnaïve_bwmap を並列に適用する。 元の入力トポロジーに対するnaïve_bwmap の処理が終われば、アルゴリズムは終了であり、それまで求めた部分バンド幅マップをマージしたものが出力である。

発表の流れ はじめに 関連手法 提案手法 実験 まとめ

実験 バンド幅マップの可視化 15クラスタ、311ホスト、640エッジの環境において、およそ50秒でバンド幅マップが得られた

参加ノード数を変化させた時のバンド幅マップ構築に要する時間の比較 実験 所要時間の比較 本手法の並列化の効果をみる実験 参加ノード数を変化させた時のバンド幅マップ構築に要する時間の比較 並列化ありの本手法 並列化なしの本手法 TopoMon-based な手法

実験 所要時間の比較

実験 本手法の所要時間の変化

実験 所要時間についての考察 既存手法と比較して大幅に高速化が実現された 実験の後半ではグラフ分割が十分に機能していない傾向が見られる 所要時間は階層構造の深さに比例する。もしグラフ分割が常に平衡木状になるように行われれば、ノード追加に対する所要時間の増加はlog の特性を持つ 多数ホストを有するクラスタが追加されると、Betweenness で表されるグラフの中心が偏ることが原因

本研究の中間エッジバンド幅測定の効果をみる実験 実験 正確さの検証 本研究の中間エッジバンド幅測定の効果をみる実験 シミュレーションにおいてランダムに生成したグラフに各手法を適用し、正しいバンド幅を測定することができたエッジ数の割合 本手法 TopoMon-based な手法 ランダムグラフ ノード数とそれらの接続形態がランダム 各エッジのバンド幅は[10.0, 1000.0]

実験 正確さの検証

直径10、498ホストの環境において既存手法では70% の正解率にまで落ちているが、本手法は98% の正解率をもつ 実験 正確さについての考察 直径10、498ホストの環境において既存手法では70% の正解率にまで落ちているが、本手法は98% の正解率をもつ 本手法で誤ったものは、可能な限りのストリームを流しても飽和しきらなかったもの グラフの直径が大きくなるにつれて中間エッジ数が増えるので、TopoMon-based 手法の正解率は落ちていく

発表の流れ はじめに 関連手法 提案手法 実験 まとめ

15クラスタ、311ホスト、640エッジの環境において、およそ50秒でバンド幅マップが得られた まとめ バンド幅マップ構築アルゴリズム バンド幅マップ構築アルゴリズムの提案 多対多協調のバンド幅測定で、中間エッジの正しいバンド幅測定を実現 グラフ分割による測定の並列化で、高速化を実現 15クラスタ、311ホスト、640エッジの環境において、およそ50秒でバンド幅マップが得られた

まとめ 今後の課題 よりよいグラフ分割手順 グラフ分割の指標としてBetweenness に加えて新たなヒューリスティクスを考え、より並列度が高くなるようなグラフ分割