大規模ネットワークにおける 効率的なバンド幅マップ構築アルゴリズム 電子情報学専攻 近山・田浦研究室 長沼翔

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

広く使われている多ノード環境のバンド幅分布の表記方法 はじめに バンド幅行列 広く使われている多ノード環境のバンド幅分布の表記方法 環境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 のモジュール 関連手法 TopoMon Network Weather Service のモジュール Network Weather Service: グリッド環境で広く用いられるネットワーク監視ツール ネットワークトポロジーとバンド幅行列を測定し、それらよりバンド幅マップを求め、出力する。

関連手法 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 の問題 形としてはバンド幅マップを求めているが、いくつかの中間エッジのバンド幅の情報が欠落している 構築に時間がかかり、スケールもしない TopoMon は環境中の全エンドホストで起動し、バンド幅行列を得る為にEnd-to-End バンド幅測定を全ての組み合わせについて一つ一つ行っている。 バンド幅測定の衝突を避けるため O(N2)

ミクロな視点でパケットの挙動を解析し、バンド幅を推定する バンド幅マップは、これを全てのエンドホストペアで実行すれば得られることになる 関連手法 Pathchar など End-to-End のバンド幅推定手法 経路中にある全ての中間エッジを推定可能としている ミクロな視点でパケットの挙動を解析し、バンド幅を推定する バンド幅マップは、これを全てのエンドホストペアで実行すれば得られることになる

関連手法 Pathchar の仕組み (1/2) 送信元のホストからn ホップ目のルータにサイズs のパケットが到着するまでにかかる時間Tn(s) Qk, dk, bk はそれぞれノードk のキュー待ち時間、機器固有の遅れ、次のルータに繋がるエッジのバンド幅 Q0(待ち時間) S/b0(転送時間) d0(機器の遅れ) d1

関連手法 Pathchar の仕組み (2/2) 全てのルータでキュー待ち無くパケットが通り抜けた場合、 となり、 これはパケットサイズとバンド幅の関数 dn はルータn に固有の値であり、定数 TTL (n) とサイズ(s) を変化させてパケットを送信し、ルータ(n+1) とルータ n の中間エッジのバンド幅 bn を算出

ICMP メッセージを返さない機器があると正しく計算できない 関連手法 Pathchar の問題 ICMP メッセージを返さない機器があると正しく計算できない レイヤー2 スイッチやICMP を返さないルータ root 権限が必要 エンドホストで高精度な計時が必要 10Gbps などパケット到着間隔の短い環境 WAN などのノイズの多い環境 構築に時間がかかり、スケールもしない O(N2)

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

関連手法 SNMP などの管理ツールを使う手法 管理者権限でネットワーク機器にログインし、管理情報を取得 管理者権限が必要であり、非対応の機器や未設定の機器も存在する 仮にできたとしても、高速化やスケーラビリティについては言及されなければならない 我々の研究とは想定する利用シーンの違う研究

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

実装 前提 提案手法 概要 入力： ルーティング情報を含むネットワークトポロジー 出力： バンド幅マップ ネットワークトポロジー情報 traceroute や既存のトポロジー推定手法で取得可能 [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 の処理が終われば、アルゴリズムは終了であり、それまで求めた部分バンド幅マップをマージしたものが出力である。

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

実験 バンド幅マップの可視化 WAN をまたぐ15クラスタ、311ホスト、640エッジの環境において、およそ50秒でバンド幅マップが得られた。 1つのストリームを流す時間は300ms とした。 1クラスタ内 はこだて未来大 – 九州大間

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

実験 所要時間の比較

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

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

本研究の中間エッジバンド幅測定の効果をみる実験 実験 正確さの検証 本研究の中間エッジバンド幅測定の効果をみる実験 シミュレーションにおいて、ランダムに生成したグラフに対する、正しいバンド幅を測定することができた割合 本手法 TopoMon-based

実験 正確さの検証

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

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

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

よりよいグラフ分割手順 ストリームを流す時間の動的調整 まとめ 今後の課題 グラフ分割の指標としてBetweenness に加えて新たなヒューリスティクスを考え、より並列度が高くなるようなグラフ分割 ストリームを流す時間の動的調整 現在は経験的な数字で300ms に固定している