を基本ノードセット

ネットワークトポロジを考慮した
バンド幅推定の高速化手法
長沼翔高橋慧柴田剛志
田浦健次朗近山隆
（東京大学）
背景
• 並列処理の必要性
• Web ドキュメントの言語処理など
– 処理対称のデータは数TB～数PBにもなる
• 並列処理を行う環境としてグリッドという分
散環境が注目される
– グリッドではノード間のバンド幅が場所により
大きく異なる
• 10Mbps～1Gbps以上
背景
• 並列分散アプリケーションの通信部分を無計画
に行うと，性能が上がらない
• 現在提案されている計画立ての手法の多くは，
リンクのバンド幅の情報をたよりにしている
• バンド幅マップを構築する必要がある．しかし，
既存のバンド幅推定手法では，グリッドのような
入り組んだネットワークでのバンド幅マップ構築
は難しい
– #バンド幅マップとは
• ネットワークトポロジ上の全リンクにバンド幅の値を割り当て
たイメージ
目的
• グリッドでのバンド幅マップの構築
– 正確
– 短時間
構築したバンド幅マップの応用例
• 通信部分を考慮した，アプリケーションの
最適化など
• グリッドの管理・運用，トラブルシュートなど
発表の流れ
•
•
•
•
背景と目的
既存手法の紹介
提案手法
実験と評価
既存手法
• Iperf など (Streaming method)
– 10 sec データを送受信，送れたデータサイズを10 sec で割る
• ○ 正確でばらつきの小さい結果
• × ボトルネックリンクの値しか得られない
• Pathchar など (One-Packet method)
– パケットの伝送時間をキュー待ち，機器の遅れ，転送時間に分けて考え，
沢山の観測データから転送時間のみを抽出し，バンド幅を算出する
• ○ 負荷が小さい
• × 不正確でしかもばらつきが大きい，スイッチが介在すると測れない，測定時間が長
い，root 権限が必要など
• Nettimer など (Packet-Pair method)
– 二つのパケットを連続送信し，受信側で到達時間の差を見，それから間
のリンクのバンド幅を推定する
• ○ Pathchar より高速
• × 不正確でしかもばらつきが大きい，ボトルネックリンクの値しか得られない
既存手法の問題
• One-Packet method やPacket-Pair method は不正
確でばらつきが大きく，実用の域に達していると
は言い難い（様々研究が進められている）
• 時間と手間がかかる
– 数時間単位
– グリッドでは測定箇所が多いので，スケーラビリティの高さは必須
• 正確なバンド幅マップを構築するには，ボトルネッ
クリンク以外のリンクも測ることができなくてはな
らない
発表の流れ
•
•
•
•
背景と目的
既存手法の紹介
提案手法
実験と評価
提案手法
• ネットワークトポロジを表すツリーの，全ノード（エンドホス
ト，スイッチ等）を基本ノードセットに分解して考え，葉の
部分のセットからボトムアップ式にそれらを並列に推定
• ネットワークトポロジは既知とする
– トポロジは高速に推定可能
• 4 クラスタ，256 ノードの推定に16 秒
– Shirai et al. A Fast Topology Inference
-- A building block for network-aware parallel
computing. (HPDC 2007)
基本ノードセットとは
B
A
Link
C
基本ノードセット
1 スイッチに3 ノード（ホスト，スイッチ等）が接続されたネットワーク．
一般のネットワークは基本ノードセットの連続である．
基本ノードセットのバンド幅推定
a
A
B
a
A
Link
a
A
a
a
B
Link
a
C
b
C
b
B
b
B
c
C
Link
a
A
b
C
Link
基本ノードセットのバンド幅マップは，4 パターンしかない
（ a < b < c としてよい）
基本ノードセットのバンド幅推定
a
a
a
A
A
b
a
B
Link
C
B
b
C
b
a
A
B
a
Link
C
Link
b
A
a
Link
a
A
B
a
b
B
c
C
b
Link
C
?
4 パターンのうち，2 つに絞り込めた
a<b<c
基本ノードセットのバンド幅推定
a
a
A
a
A
Link
a
a
b
a
A
B
B
b
C
b
C
b
B
c
C
min(2a, b)
a
A
b
B
Link
C
Link
a
Link
min(a+b, c)
B
A
Link
?
C
1 つに絞り込めた
a<b<c
基本ノードセットのバンド幅推定
Bandwidth Map
of Primal Set
x
A
B
Link
C
Expected Values of Measurement
for each Case
動作例
動作例
ホスト
スイッチ
1. 基本ノードセットに分解
2. 葉の基本ノードセットのバンド幅推定
3. 以後ボトムアップ式に
基本ノードセットのバンド幅推定
ボトルネックリンクに影響されて結果が誤る
3. 以後ボトムアップ式に
基本ノードセットのバンド幅推定
3 本のストリームを束ねて流す
提案手法（改め）
• ネットワークトポロジを表すツリーの，全ノード（エンドホス
ト，スイッチ等）を基本ノードセットに分解して考え，葉の
部分のセットからボトムアップ式にそれらを並列に推定．
• 必要ならば複数本束ねたストリームを用いる．
発表の流れ
•
•
•
•
背景と目的
既存手法の紹介
提案手法
実験と評価
実験結果
• 6 クラスタ，333 ホストの環境で，1 分55 秒
程度でバンド幅マップを構築できた
実験環境
cluster A@本郷
cluster B@早稲田
15 hosts
15
85 hosts
15
14
14
14
14
14
cluster C@京都
31 hosts
31
cluster F@横浜
cluster D@京都
37 hosts
36 hosts
36
16
37
19
16
19
48
10
cluster E@西千葉
129 hosts
数字は各スイッチを結ぶリンクのバンド幅 (Mbps)．
リンクの太さはバンド幅の大きさに対応．
見易さのために一部の葉の図示を省略している．
推定精度
実験環境の全リンクについて，
実際のバンド幅（スループット）に対する実験結果の比と，
そのような比の値をとったリンクの出現頻度
推定時間
本手法はトポロジの半径d に比例した時間を要する．
ホスト数 N のときd はΟ(log N)
まとめ
• グリッド環境におけるバンド幅マップを，短
時間かつ正確に構築する手法を述べた．
• グリッド上で実験を行い，その性能評価を
し，またスケーラビリティの高さも確認した．
– 6 クラスタ，333 ホストの環境で1 分55 秒程度

Download Report