www.logos.ic.i.u

高速なトポロジー推定
－ネットワークを考慮した
並列計算の基盤として
2007. 5. 25
東京大学
白井達也（現在リコー所属），斎藤秀雄，田浦健次朗
2007. 5. 25
1
ネットワークを考慮した並列計算

プロセス間の通信量に偏りがある処理の通信コスト削減


e.g. 集合通信，行列演算
プロセス割り当てによって通信コストを削減できる



別のLANのホスト間ではできるだけ通信しない
LAN内でも通信路を共有するとバンド幅を得られない
ネットワークの接続関係（トポロジー）の情報が必要
2007. 5. 25
2
ネットワーク情報の与え方

既存研究のアプローチ



WANとLANだけを区別（MagPIe [Kielmann et al. ‘99]）
必要な情報を手動で設定する（MPICH-G2 [Karonis et al. ‘03]）
手動設定が困難な環境



複数の管理者が個別に管理するクラスタ群
資源が動的に変化
仮想化された環境

ホスト名やIPアドレスがネットワークを反映しない
 ネットワークトポロジーの推定機構が必要
2007. 5. 25
3
並列計算のためのトポロジー推定

動作環境が幅広い



ネットワーク負荷が低い



TCP/IPのような一般的なプロトコルだけで動作
管理者権限が不要
他のプロセスに影響を与えない
他のプロセスに影響されない
短時間で推定


2007. 5. 25
CPU負荷が刻々と変化する
「計算開始時に」負荷の低いホストを使いたい
4
本研究の貢献

与えられた計算環境のトポロジーを「End-Endの
RTTの測定だけ」を用いて「高速に」推定するシス
テムを提案

４クラスタ256ホストを15秒程度で推定


2007. 5. 25
既存手法と比べて非常に高速
通信効率化に有効な精度
5
発表の流れ






背景
関連研究
提案手法
評価
トポロジーを用いた通信効率化
まとめと今後の課題
2007. 5. 25
6
発表の流れ


背景
関連研究






管理プロトコルを用いた研究
End-to-Endの測定を用いた研究
提案手法
評価
トポロジーを用いた通信効率化
まとめと今後の課題
2007. 5. 25
7
管理プロトコルを用いた研究

プロトコル
 traceroute [Benoit et al. ACM SIGMETRICS ’05]
 SNMP [Yuri et al. IEEE/ACM Trans. ’04,
Bruce et al. ACM SIGCOMM ’01]

プロトコルが動作する環境で常に接続情報を交換し，正確な推
定ができる
主な目的はネットワーク管理

動作環境が限られる




2007. 5. 25
インテリジェントスイッチを仮定
管理者権限が必要
セキュリティポリシーによっては，LAN外のユーザはその情報を得
られない
8
End-End間の測定を用いた研究

測定方法


パケットロス率 [Duffield et al. IEEE Trans. ‘02]
バンド幅
[Coates et al. SIGMETRICS ‘03]
遅延 (RTT) [金田ら. SWoPP ‘04]
長所

幅広い環境で動作する



TCP/IP・UDP/IP で動作
管理者権限が不要
短所

推定結果は非決定的


2007. 5. 25
測定の変動が大きいと正確に推定できない
推定に時間がかかる
9
バンド幅を用いた推定
[Coates et al. ACM SIGMETRICS ’03]

測定方法



WANの11ホスト，6スイッチのトポロ
ジーをほぼ正確に推定
ただし，8分程度かかった
長時間の測定が必要


１つのソースホストから他のホストペア
に測定パケットを送信し，共通の通信
路のバンド幅を得る
成果


src
全ホストペアを測定 → O(n2)
srcから遠いホスト群の精度が低い

2007. 5. 25
dest1 dest2
srcを固定したことが原因
10
発表の流れ



背景
関連研究
提案手法





基本アルゴリズム
実ネットワークへの適用
評価
トポロジーを用いた通信効率化
まとめと今後の課題
2007. 5. 25
11
提案手法の概要

ホスト間のRTTの測定を用いる
ホストを１つずつ追加する
３ホストのトポロジーを組み合わせて全体を構成する

構築中のトポロジー情報を用いることで短時間に推定する




遠いホスト間の測定を極力避ける
トポロジーは木構造モデルで表す


2007. 5. 25
ネットワークの良い抽象化
アルゴリズムの単純化
12
RTTの測定


RTT: 小さなパケットのホスト間の往復時間
ホップ数ごとのRTT測定値の分布
 測定回数100回
2 hops
6 hops
40
4 hops
other cluster
30
count
20
10
0
0
50
150
100
RTT [us]
200
250
 2ホップと4ホップ以上の測定値の差を判別できる
2007. 5. 25
13
提案手法の基本的な流れ
対象ホストを
ランダム順に並べる
3ホストのトポロジー
残りのホストを
１つずつ追加
2007. 5. 25
14
３ホストのトポロジー

ホスト間のRTTを枝の重みの和で表す


どのホスト間でも同じリンク，同じスイッチで同じ遅延が生じると仮定
３ホストでは枝の数とRTTの数が同じなので，一意に決まる
ＡＢ
A
a
b
B
c
ＡＣ
C
ＢＣ
AB = a+b
AC = a+c
BC = b+c
3ホストのトポロジー
2007. 5. 25
15
ホストの追加 –Addition –


ホストを１つずつ追加する
追加位置を絞り込む
２ホストを選択
3ホストのトポロジーの分岐位置を求める
測定したホストからその分岐位置まで追加位置の候補から外れる



H
N1
N3
N5 N6 N7
S1
N0
S
S2
S2
S3
N8 N9 N10
N2
2007. 5. 25
N4
16
測定の変動を考慮した工夫
対象ホストを
ランダム順に並べる
3ホストのトポロジー
残りのホストを
１つずつ追加
対象ホストを
ランダム順に並べる
3ホストのトポロジー
近いホストを選択
（Selection）
ホストを追加
（Addition）
細かいリンクを除く
2007. 5. 25
17
細かいリンクを除く


測定の変動によって細かいリンクが生じてしまう
リンクのしきい値を設定して，しきい値以下であれ
ば分岐に加える
H
H
A
B
C
2007. 5. 25
A
B
C
18
リンクのしきい値の適切な値

しきい値を静的に設定したときの推定結果
Cluster 3: 2~4μsが適切
Cluster 4: 6~7μsが適切
1μs
1μs
5μs
8μs
 適切な値は環境によって異なる
2007. 5. 25
19
リンクのしきい値の動的決定

複数回の測定で得られる測定結果の変動をしきい値（r）
とする

測定の変動より大きい遅延が意味を持つ
H
H
A
B
C
リンクの遅延 > r
2007. 5. 25
A
B
C
リンクの遅延 < r
20
測定の変動を考慮した工夫
対象ホストを
ランダム順に並べる
3ホストのトポロジー
残りのホストを
１つずつ追加
対象ホストを
ランダム順に並べる
3ホストのトポロジー
近いホストを選択
（Selection）
ホストを追加
（Addition）
細かいリンクを除く
2007. 5. 25
21
Additionの測定ホストの選択 -Selection
Additionの最初で近くのホストを選択する
 遠いホストを選ぶと誤りの距離が大きい
H
N1
N3
N5 N6 N7
S1
N0
S2
S3
H
N8 N9 N10
N2
2007. 5. 25
N4
22
近いホストを選択する効果

４クラスタ32ホスト
近いホストを選択
ランダムに選択
 遠いホストを選択すると大きく誤る
2007. 5. 25
23
Selectionのための測定

測定するホストを削減する

測定しながら不要なホストを測定対象から除く


測定したホスト (J) より十分遠いホスト(K)は追加するホスト(H)から遠い
測定したホスト (J) と十分近いホスト(K)はどちらを選択しても同じ


JK間の値は構築中のトポロジーから求められる
特にマルチクラスタ環境で効果的

他のクラスタとはそれぞれ高々１ホストずつしか測定しない
J
JK > 3x
x
J
JK < 1/3x
x
H
K
>2x ：遠い
2007. 5. 25
H
J と同程度の距離
K
24
AdditionとSelectionの並列化

ホスト追加時のトポロジー情報の流れ



k ホスト前から受け取ったトポロジーを使って近いホストを選択
１ホスト前から受け取ったトポロジーを使って自ホストを追加
Selectionは他ホストのAdditionと並行して行う

・・・
Selectionの時間的コストはゼロ
n-k
・・・
Tn-k
2007. 5. 25
Tn-1
n-1
n
Tn
・・・
n+1
n+k
・・・
Tn
25
発表の流れ




背景
関連研究
提案手法
評価




推定精度
推定時間
トポロジーを用いた通信効率化
まとめと今後の課題
2007. 5. 25
26
実験環境
４クラスタ256ホストを使用


実験中も他のユーザのプロセスが動作
Cluster 1 (遅延: 20~30μs)
6ポートのハブのスタック
6
6
2
6
6
2
Cluster 3 (遅延: 25~35μs)
2ms
25μs
14
6
6
6
6
6
6
5μs
14 14
14 14
45μs
3ms
16 16 16 16
Cluster 2 (遅延: 25~40μs)
2007. 5. 25
14 14 14
14 14
Cluster 4 (遅延: 50~65μs)
27
推定結果





Cluster 2, 3は正確
同じスイッチにつながるホスト群
を近くに推定した
ただし，特にCluster 1, 4はそれ
らが分散してしまった
Cluster 1, 4はスイッチ間が不
正確
大きな遅延のリンクに隣接する
小さな遅延のリンクが隠されて
しまった
Cluster 1
Cluster 3
Cluster 1
Cluster 3
Cluster 4
Cluster 2
Cluster 4
2ms
3ms
Cluster 2
2007. 5. 25
5μs
28
定量的な評価 1/3

通信路の共有情報の正確さ


２つのホストペアの通信路がリンクを共有するかどう
かの正確さ（バンド幅をシェアするかどうか）
ランダムに100万ペア選択し，誤り率を求めた
共有するのに，しないと推定された場合
2007. 5. 25
共有しないのに，すると推定された場合
29
定量的な評価 1/2

通信路の共有情報の正確さ：１クラスタ
32
32
false positive
24
# of occurrences
# of occurrences
false negative
16
8
0
0
0.05
0.1
false rate
0.15
0.2
24
16
8
0
0
0.1
0.2
0.3
0.4
0.5
false rate
 一つのスイッチにつながるホスト群が分離したため，
false positiveが高かった
2007. 5. 25
30
定量的な評価 2/2
通信路の共有情報の正確さ：４クラスタ

32
32
false negative
false positive
24
# of occurrence
# of occurrence
24
16
8
0
0
0.04
0.08 0.12
false rate
0.16
0.2
16
8
0
0
0.04
0.08 0.12
false rate
0.16
0.2
 Cluster 1，2と3，４の間の 5μs のリンクを見つけられな
かったため，false negativeが上昇した
2007. 5. 25
31
推定時間

Selection時に全ホストと測定した場合（all-toall）と比較
25
1cluster
3 clusters
all-to-all
time [sec]
20
15
2 clusters
4 clusters
10
5
0
0
50
100
150
200
number of hosts
250
300
既存研究では11ホストを8分というオーダー
all-to-all ではホスト数の増加に対して推定時間が増加
 本手法はホストの増加に対して推定時間がそれほど増加せず高い
2007. スケーラビリティを持つ
5. 25
32
測定回数

クラスタ内，クラスタ間で測定したホストペア数

全対全に対する割合を示す
0.6
Cluster 1
Cluster 3
Cluster 2
Cluster 4
0.4
0.2
0
Cluster 1
Cluster 2
Cluster 3
Cluster 4
 クラスタ内の測定は35~50%
 クラスタ間の測定は2％程度と非常に少ない
2007. 5. 25
33
発表の流れ






背景
関連研究
提案手法
評価
トポロジーを用いた通信効率化
まとめと今後の課題
2007. 5. 25
34
トポロジーを用いた通信効率化


バンド幅測定
長いメッセージのブロードキャスト
2007. 5. 25
35
長いメッセージのブロードキャスト 1/2

ユニキャストを組み合わせたブロードキャスト


単純化のため，各リンクでバンド幅が一定とする
バンド幅の最適化



パイプライン転送を行う
各リンクを片方向一度ずつ使うような順に転送
ツリートポロジーでは，トポロジー上で深さ優先順に転送する
0
1
4
0
3
2
×片方向２回
2007. 5. 25
1
2
3
4
○片方向１回
36
長いメッセージのブロードキャスト 2/2


Cluster 4の64ホストを用いて実験を行った
 スイッチ間は４本のトランク
 各リンクは1Gbps
実際のツリー上の深さ優先順(optimal) ・ランダム順(random)と比較
bandwidth [Mbps]
800
600
optimal
random
ours
400
200
0
0.01
0.1
1
10
100
message size [MB]
 randomでは何往復もしてしまい，23%の性能しか得られなかった
 oursは２往復するものはあったが，平均88%の性能を得られた
2007. 5. 25
37
発表の流れ






背景
関連研究
提案手法
評価
トポロジーを用いた通信効率化
まとめと今後の課題
2007. 5. 25
38
まとめ

RTTの測定だけを用いたネットワークトポロジー推定手
法を提案した

４クラスタ256ホストのトポロジーを15秒程度で推定





既存の手法より一桁以上高速
ホスト数に対してスケーラブル
ネットワーク的にヘテロな環境で動作
ネットワーク負荷が低い
トポロジーを用いた通信効率化手法を提示した

2007. 5. 25
長いメッセージのブロードキャスト
39
今後の課題

推定精度の向上


リンクのしきい値のよりよい基準
RTTの測定では推定できない部分の補完



バンド幅など他の測定を使う
使えるときは traceroute なども用いる
推定時間の向上

2007. 5. 25
ホストの追加の並列化
40
ご静聴ありがとうございました
2007. 5. 25
41

Download Report