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

はじめに バンド幅マップとは ネットワークを表すグラフの全エッジに、バンド幅の値を割り振ったもの 5 9 2 2 5 5 5 4 4 9 2

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

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

背景 バンド幅マップを得ることはますます重要に ネットワークの管理、運用のため 広域分散アプリケーションの最適化のため ますますというゆえんは広域分散環境上で並列処理が盛んにおこなわれるようになってきて、 ネットワークの性能も、アプリケーション最適化するための指標の一つとなった。 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とかは機器や規格に依るものがある

bhtree [SACSIS2008, pp. 359-366. ] 入力はネットワークトポロジーを表すデータ、出力はその全エッジにバンド幅の値を割り振ったデータ 基本セットに小分けにするという考えで、高速化、高精度化を実現 既存手法の問題点を克服し、要望条件をおよそ満足するかたちでバンド幅マップの推定ができた

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

一部を拡大したもの

bhtree で残された問題点 ネットワークをツリーとして扱っていた リンクのバンド幅は上下対称であるとしていた 特にWAN では上の二つの仮定には無理がある bhtree を実環境ネットワークに適用可能なように考え直したい 有向グラフ 仮定

新たな目標 実ネットワーク環境では、循環構造や非対称なリンクも含む。bhtree では不十分 有向グラフを入力とし、バンド幅マップを出力することができる新たな手法が必要

応用例 より実環境に近い形でバンド幅マップの情報を得ることによって 通信性能を考慮しながら柔軟に最適通信を行うネットワークアプリケーションに より詳細にネットワークを把握し、管理・運用・トラブルシュートに

発表の流れ 背景と目的、目標 既存手法 新手法の提案 実例 まとめ

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

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

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

発表の流れ 背景と目的、目標 既存手法 新手法の提案 実例 まとめ

手順の概要 (1/2) 入力データとして、ネットワークのルーティング情報を含むトポロジーを有向グラフとして用意する bhtree ではRTT 測定によって得た論理トポロジーを入力データとして使用していた[*] 入力された有向グラフをn 個のシンクツリーに分解して考える グラフとしてそのまま眺めても、複雑過ぎて、どこをどの向きで推定しようとしているのかが分かりにくい [*] Shirai et al. A Fast Topology Inference　(HPDC 2007)

手順の概要 (2/2) 各シンクツリーのバンド幅マップを決定したら、元のネットワークグラフに組み立てなおす 既存手法 (bhtree) と同様に、構造としてはツリーのみを推定の対象とし、結果は循環構造や非対称のリンクを含む実ネットワークの形で出力可能

手順1: グラフをn 個のシンクツリーに分けて考える 5 9 2 2 5 5 5 4 4 9 2

手順2: 各シンクツリーの　　　　　　　　　　 バンド幅マップを決定する

手順3: 元のネットワークグラフ に組み立て直す

完了 同エッジ同方向で異なるバンド幅の値が重なる場合、 大きい方の値を採用する。

次に、各シンクツリーのバンド幅マップ決定について

シンクツリーのバンド幅マップ決定アルゴリズム 各ノード{Aj | j = 1, 2, …, n}からシンクノードに向かってバンド幅推定。結果を{BAj}。 max{BAj} = BAk となるようなAk について、 2.1 (Ak – シンクノード)間のroute 上にある各分岐点Si について、Si – Aj (j ≠ k) がただ一つのエッジで成るroute である場合、 Si – Aj のバンド幅はBAj 。 2.2 そうならないAj については、Si をシンクノードとした部分木について手順1. を繰り返す。

各シンクツリーのバンド幅マップ決定アルゴリズム (例) B2 B3 B4 B5 B1 Iperf でもなんでもいい B1 < B2 < B3 < B4 < B5 と観測されたとする

シンクツリーのバンド幅マップ決定アルゴリズム (例) B1 B2 B5 B4 B3 B1 < B2 < B3 < B4 < B5 と観測されたとする

シンクツリーのバンド幅マップ決定アルゴリズム (例) B1 B2 B5 B4 B3 B1 < B2 < B3 < B4 < B5 と観測されたとする

シンクツリーのバンド幅マップ決定アルゴリズム (例) B1 B2 B5 B4 B3 B1 < B2 < B3 < B4 < B5 と観測されたとする

シンクツリーのバンド幅マップ決定アルゴリズム (例) B1 B2 B5 B3 B4 B1 < B2 < B3 < B4 < B5 と観測されたとする

シンクツリーのバンド幅マップ決定アルゴリズム (例) B1 B2 B5 B3 B4 B1 < B2 < B3 < B4 < B5 と観測されたとする

シンクツリーのバンド幅マップ決定アルゴリズム (例) B1 B2 B5 B3 B4 B1 < B2 < B3 < B4 < B5 と観測されたとする

シンクツリーのバンド幅マップ決定アルゴリズム (例) B1 B2 B5 B3 B4

発表の流れ 背景と目的 既存手法 新手法の提案 実例 まとめ

実例 InTrigger の各拠点間のネットワークグラフを見てみる グラフの生成にはtraceroute と ally [*]を使用 [*] CAIDA, http://www.caida.org/tools/

InTrigger (11 clusters) n <--> n graph

n <--> n graph [shrinked] InTrigger (11 clusters) n <--> n graph [shrinked]

InTrigger (11 clusters) n * (n --> 1 tree)

発表の流れ 背景と目的 既存手法 新手法の提案 実例 まとめ

まとめ 実ネットワークに対する既存バンド幅推定手法の限界を見た トポロジーを複数のシンクツリーに分けて考え、既存手法を工夫して実行することによって、実ネットワークに対応しうるバンド幅推定手法を提唱した

今後について 提唱アルゴリズムの実装と実験 高速化 精度、正確さ、ばらつきなどの評価 基本部分であるバンド幅推定手法の追求 互いに測定が干渉しないような測定を同時にやってしまう グラフ的に近いノードをルートとするシンクツリーらは、ほとんど同じ部分グラフをもつ 精度、正確さ、ばらつきなどの評価 基本部分であるバンド幅推定手法の追求