ネットワークトポロジを考慮した効率的なバンド幅推定手法 長沼翔　高橋慧　斎藤秀雄　柴田剛志 田浦健次朗　近山隆 （東京大学）

背景 バンド幅マップを得ることはますます重要に ネットワークの管理、運用のため 広域分散アプリケーションの最適化のため 8 8 10 7 9 3 5 A S B C D E F バンド幅マップの例

背景 バンド幅マップを得ることはますます重要に ネットワークの管理、運用のため 広域分散アプリケーションの最適化のため only 3!? 8 以前からよくあるパターン、使いみち 8 8 10 7 10 9 3 5 A S B C D E F only 3!?

背景 バンド幅マップを得ることはますます重要に ネットワークの管理、運用のため 広域分散アプリケーションの最適化のため ますますというゆえんは広域分散環境上で並列処理が盛んにおこなわれるようになってきて、 ネットワークの性能も、アプリケーション最適化するための指標の一つとなった。 8 8 Throughput = 3 10 7 10 9 3 5 source : (A) destinations : others A S B C D E F パイプラインを用いたブロードキャスト

A Stable Broadcast Algorithm [Kei Takahashi et al, CCGrid2008] 背景 バンド幅マップを得ることはますます重要に ネットワークの管理、運用のため 広域分散アプリケーションの最適化のため タスクをばらまくタスクスケジューラや Map reduceの際のタスクばらまき時の最適なばらまき方っていうのを実現できると考えられる 3 4 8 1 5 source : (A) destinations : others A S B C D E F A Stable Broadcast Algorithm [Kei Takahashi et al, CCGrid2008]

背景 バンド幅マップを得ることの難しさ ネットワークの深部の情報が得られない 多大な時間と手間を要する 既存の1対1推定ではボトルネックリンクしか得られないことがほとんど 多大な時間と手間を要する ホスト数N に対して推定すべき組み合わせはO(N2) 深部　-> ツリーと見たときのルート付近 ただ列挙するマトリクス 情報量が削減されている 応用が利かない マップとして得ないと、先ほどの例のどれも実現できない バンド幅マップ 従来方法で得られるバンド幅マトリクス A B C D E F - 3 7 8 5 9 8 8 10 7 10 9 3 5 A S B C D E F

目的 バンド幅マップを得る為の新たな手法の提案 正確 高速 ユーザレベルで実行可能 ネットワーク深部まで把握できる 高いスケーラビリティを持つ ユーザレベルで実行可能 root 権限を必要としない 機器や規格に依らない 既存手法の中にはroot 権限を必要としたり、snmpとかは機器や規格に依るものがある

352 ホストからなる分散環境で120 秒程度で構築ができた

発表の流れ 背景と目的 既存手法の紹介 提案手法の紹介 実験と評価 まとめ

1対1の推定を基調とした手法 Iperf など (Streaming method) 10 sec データを送受信，送れたデータサイズを10 sec で割る ○　正確でばらつきの小さい結果 ×　ボトルネックリンクの値しか得られない Pathchar など (One-Packet method) パケットの伝送時間をキュー待ち，機器の遅れ，転送時間に分けて考え，沢山の観測データから転送時間のみを抽出し，バンド幅を算出する ○　負荷が小さい ×　不正確でしかもばらつきが大きい，スイッチが介在すると測れない，測定時間が長い，root 権限が必要など Nettimer など (Packet-Pair method) 二つのパケットを連続送信し，受信側で到達時間の差を見，それから間のリンクのバンド幅を推定する ○　Pathchar より高速 ×　不正確でしかもばらつきが大きい，ボトルネックリンクの値しか得られない 一対一の推定では ボトルネックリンクしか得られない 時間と手間がかかりすぎる そもそもマトリクスしかえられないので本研究の目標とは別方向 これらを使ってバンド幅マップを構築することは不可能

Network Weather Service 各ホストにデーモンが置かれる 各ホスト間の全体全で推定を自動に行う 結局、得られるものはバンド幅マトリクス 手間は省けるが、バンド幅マップの様な詳細な情報は得られない スケールしない トポロジアンアウェア 推定の干渉・競合を避けるためにトークンを渡して一つ一つやっている デーモン走らせて、ユーザは出来上がるのをまったり待つというポリシーかもしれないが、スマートな方法ではない ?

perfSONAR SNMP を用いたネットワーク監視ツール ただし機器や規格に依存する 得られるバンド幅の値は定格値 高速であり、バンド幅マップの様な詳細な情報も得られる ただし機器や規格に依存する SNMP 非対応の機器 perfSONARプロトコルの標準化 得られるバンド幅の値は定格値 ユーザレベルではあまり実用的ではない データベースをつつくだけなので 味が違うのが、実際に測ってバンド幅を確かめるのではなく、管理データを見て調べるというようなアプローチ 非対応の機器も未だ多くある。通信経路上のすべての機器についてそれを確かめたり置き換えたりするのは現実的ではない 実際に測るのと管理データをつつくことの違いは、ここ

発表の流れ 背景と目的 既存手法の紹介 提案手法の紹介 実験と評価 まとめ

問題設定 木構造ネットワーク上に、バンド幅マップを構築する トポロジは既知とする リンクのバンド幅は上下対称とする トポロジは高速に推定可能 入力はトポロジ、出力はそれの全リンクにバンド幅の値を割り当てたバンド幅マップ トポロジは既知とする トポロジは高速に推定可能 4 クラスタ，256 ノードの推定に16 秒 Shirai et al. A Fast Topology Inference　(HPDC 2007) リンクのバンド幅は上下対称とする 一般の場合にも適用可能

提案手法 基本はIperf トポロジを基本セットに分解して考え、それらを葉部からボトムアップ式に並列に推定を進める 1対1を推定対象の単位とするのではなく、 1スイッチ + 3ノードで1セット（基本セット） を推定対象の単位とする トポロジを基本セットに分解して考え、それらを葉部からボトムアップ式に並列に推定を進める 前スライドの仮定のもと、 Iperf の何を改善したかというと、、

全体的な処理の進み方 葉の部分からじわりじわりとリンクのバンド幅を決定していくイメージ

個々の基本セットの推定 基本セット 1 スイッチに3 ノード（ホスト，スイッチ等）が接続されたネットワーク B Link A Link Link C 基本セット 1 スイッチに3 ノード（ホスト，スイッチ等）が接続されたネットワーク 一般のネットワークは基本セットの連続である

基本セットのバンド幅マップは，4 ケースしかない 個々の基本セットの推定 a a B B a a Link Link A A Link Link Link Link a C b C b B b B a a Link Link A Link A Link Link Link b C c C 基本セットのバンド幅マップは，4 ケースしかない 　　　　　　　　　　　　　　　　　　　　　（ a < b < c としてよい）

各ケースで期待される、1 対 1 もしくは 1 対 2 のバンド幅推定結果 個々の基本セットの推定 4 ケースのバンド幅マップ y x B Link A Link Link たとえばcase 3 だった場合、A と一対一推定するとバンド幅aがボトルネックとなって、aとしか出ない、bは見えてこない 一対一が三種類、一対二が三種類、そういったことを利用して、絞り込み z C 各ケースで期待される、1 対 1 もしくは 1 対 2 のバンド幅推定結果 a < b < c

各ケースで期待される、1 対 1 もしくは 1 対 2 のバンド幅推定結果 個々の基本セットの推定 i j j B Link A Link 基本セットの推定完了 ( i < j < k ) i Link j k 初めはABCの区別もない C k 各ケースで期待される、1 対 1 もしくは 1 対 2 のバンド幅推定結果 a < b < c 20

個々の基本セットの推定 一般の場合の推定手順 y 個々の基本セットの推定 　一般の場合の推定手順 x B Link A Link Link z 1 対1 推定を三種類行う。 If 　二種の異なる値が観測された １ 対2 推定を二種類行う。 If 　異なる値が観測された case 4 Else if 　等しい値が観測された case 3 Else if 　三つとも等しい値が観測された 1 対2 推定を三種類行う。 if 　二種の異なる値が観測された case 2 case 1 C 手順 論文にも同じものが載っているので、詳しく確認したい方はそちらを a < b < c

セットまでの経路にボトルネックリンクがあると、結果が誤る 基本セットは決定できたが… セットまでの経路にボトルネックリンクがあると、結果が誤る さて、基本セットの推定はできました。これを実際のネットワーク上でボトムアップ式に 実行していけばいいかというと実は　　　　　それでは不十分。ネットワークの深部に進むにつれて、 ネットワークの深部にある基本セットでは、そこ にたどり着くまでにボトルネックリンクを通ってしまうかもしれない。 せっかくやってもこれじゃ意味がない

ネットワーク深部 （エンドホストから離れた位置にある基本セット）では、束ねたストリームを用いる 各スイッチがもつ子ノードから必要最小限の複数ホストを選んで、 そいつらから同時にストリームをセンドレシーブすることによって、 この基本セットから見れば一本の大きいストリームで基本セットの決定を行うことができる

提案手法の特徴 詳細なバンド幅マップの推定が可能 高速でスケーラブル root 権限は不要、ネットワーク機器の設定変更なども不要 基本セット、ストリームの束という考え方を組み合わせることで実現 高速でスケーラブル 干渉・競合を気にせず、各セットを葉部分から並列に推定を進めることができるため root 権限は不要、ネットワーク機器の設定変更なども不要 各セットはネットワーク的に独立している

発表の流れ 背景と目的 既存手法の紹介 提案手法の紹介 実験と評価 まとめ

実験結果 先に提案した手法を利用した、バンド幅マップ推定ツールを実装した 11 クラスタ、352 エンドホストで構成される、実際の広域分散環境上で実行し、120 秒程度でバンド幅マップが得られた

実験環境 hongo@東大 imade@京大 suzuk@東工大 kyoto@京大 hiro@広島大 kyushu@九州大 kobe@神戸大 85 hosts imade@京大 31 hosts 15 14 14 suzuk@東工大 37 hosts 31 37 14 14 14 kyoto@京大 36 hosts mirai@未来大 6 hosts 6 バンド幅マップを構築する環境として, InTrigger InTrigger とは日本各地に散らばったクラスタをネットワーク接続して、広域分散環境を作ろうというプロジェクト 11 clusters, more than 300 nodes 36 hiro@広島大 11 hosts okubo@早大 15 hosts 15 11 keio@慶應 11 hosts 11 kyushu@九州大 10 hosts 10 11 kobe@神戸大 11 hosts chiba@NII 129 hosts 16 19 16 19 48 10

バンド幅マップを図示したもの 定格の値から大きく外れているリンクも多い

一部を拡大したもの

推定精度 実験環境の全リンクについて， 実際に負荷をかけて確かめたスループットに対する実験結果の比と， 実用という観点からすると非常に有用で正確な値が得られた。±5% 誤差がでた理由として、タイミング合わせがうまくいかなかった。 Iperf そのものの誤差（2秒）など 実験環境の全リンクについて， 実際に負荷をかけて確かめたスループットに対する実験結果の比と， そのような比の値をとったリンクの出現頻度

推定時間 本手法はツリーの直径d に比例した時間を要する． ホスト数 N のときd はΟ(log N) 、なので推定時間はlog N。グラフからも確かめられる 既存手法ではO(N^2)をやっていたのとくらべ、非常に高速で、かつスケーラブルである

発表の流れ 背景と目的 既存手法の紹介 提案手法の紹介 実験と評価 まとめ

まとめ 正確かつ短時間にバンド幅マップを推定する手法を提案した． 実際の分散環境上で実験を行い，その精度を検証し，またスケーラビリティの高さを確認した． 11 クラスタ，352 ホストの環境で120 秒程度

今後考えられる課題 一般的なネットワークの適用 非ツリー 非対称なリンク ストリームを流す方向も制御して、そこに2 本のリンクがあるとして推定を進める　など