Self-Stabilizing Minimum Spanning Tree

Self-Stabilizing Minimum
Spanning Tree
斎藤大
1
発表の流れ
1.
Self-Stabilizing Minimum Spanning
Tree（ＭＳＴ）の概要

2.
ＭＳＴアルゴリズム


3.
モデル
ＧＨＳアルゴリズム
Antonoiu and Srimaniアルゴリズム
Self-Stabilizing ＭＳＴアルゴリズム
2
１． Self-Stabilizing MSTの
概要
3
１．Spanning Treeとは？
頂点Vと辺Eの集合（V,E）から同じ頂点
集合を持つ（V,E’）を生成する
 循環構造を持たない
 孤立した部分集合を持たない
→木構造

和訳：生成木
4
１．MSTとは？
各辺に重み（コスト）をつける
 木の辺の重みの和を最小にする
 一般にMSTは一意に定まらない
→重みは全て異なる（単射）と仮定する
と一意に定まる

和訳：最小生成木
5
１．MSTの具体例
8
a
5
c
3
6
g
a
4
e
f
11
7
b
5
9
1
d
10
b
1
d
2
h
c
3
6
g
4
e
f
7
2
h
∑cost = 28（最小）
6
１．Self-Stabilizing MSTとは
頂点の増減や辺の切断を考慮
→現実のネットワークに適用
 状況の変化に合わせて自動で木の再構
築を行う

8
a
3
b
5 c 4
d
6
g
e
1
f
7
2
h
7
１．現実への適用
グラフ → ネットワーク
 辺の重み → 通信コスト
 生成木 → あるプロセスの情報を全プロ
セスに放送
 最小生成木 → 通信コストが最小の放送

8
１．モデル
Message-Passing Networkを想定
 重み付き無向グラフ（重みは単射）
 各ノード（頂点）は固有のIDを持つ
 各ノードは、隣接するノードのID、及びそ
れらの間の枝（辺）の重みを保持する

9
２． MSTアルゴリズム
1.
ＧＨＳアルゴリズム
2.
Antonoiu and Srimaniアルゴリズム
10
２．１．MINTREE
Gallager-Humblet-Spiraのアルゴリズム
→MINTREEと呼ぶ
 グラフ理論のKRUSKALアルゴリズムを
基にしている
 ノード全体の情報を知る必要がない
 フラグメント（後述）をまとめて統率するプ
ロセッサを仮定

11
２．１．KRUSKAL
G=(V, E, c)からT=(V, ET)を求める
e1...em をコストの小さい順に並べる(m:枝 n:ノード)
[KRUSKAL]
i : 0; ET : ;
while | ET | n  1 do {
i : i  1;
if ET∪ {ei } が閉路を含まない
t henET : ET  {ei }
};
12
２．１．用語の定義
a
b
フラグメント
c
3
4
外向枝
(outgoing edge)
d
6
特に最小外向枝
(Minimum Outgoing Edge)
e
g
f
レベル：合併（後述）回数
7
h
が重要！
内枝 (inside edge)
13
２．１．MINTREEの流れ（１）
各フラグメントのプロセスが最小外向枝
（MOE）を探す
 レベルが等しくMOEも共通な場合
→合併[merge]・レベルが１増加
 MOEの相手のレベルが高い場合
→吸収[absorb]・レベル変化無し
 absorbはレベルが低い方のみ出せる

14
２．１．MINTREEの流れ（２）
F２：L１
F1：L１
a
b
c
3
d
4
F３：L０
e
１
merge
6
g
f
２
absorb
7
h
F４：L１ (c, f)：L2
15
２．２． Basic_MST
Antonoiu and Srimaniアルゴリズム
→Basic_MSTと呼ぶ
 各枝がプロセッサを持っていると仮定
 既になんらかの生成木が存在する時の
アルゴリズム→初期設定が必要
 一般にはあまり用いられないが、SelfStabilizationを適用する上で便利

16
２．２．Basic_MSTの流れ（１）
1. 既に生成木が構築されているとする
2. 適当なnon-tree edgeを選ぶ
→循環構造が出来る
3. 循環構造内で最も重い枝を切る
4. ２～３の繰り返しによって、MSTを構築
17
２．２．Basic_MSTの流れ（２）
a
b
5
c
3
9
1
d
コスト最大の枝
4
e
コスト最大の枝
10
6
g
f
7
2
h
18
２．２．簡単な証明

ある関数を定義する（e:non-tree edge）
minimize_cycle( E, e)  ( E∪
 {e}) \ {max(fnd _ cyl( E, e))}




minimize_cycleは生成木を返す
E’がMSTだったら、どんなeに対しても
E’=minimize_cycle(E’,e)逆も成り立つ
一度minimize_cycleによって除かれた
枝は二度と選ばれることはない
よって全てのeについてminimize_cycle
を実行し求まる生成木はMSTとなる
19
２．２．Basic_MSTの実装（１）
枝に{chosen, unchosen}のstatus追加
 待ち時間safetime(e)を追加
→n個のノードを通る最大の時間
徐々に減少し、自分の命令受信でreset
 search、remove、insert命令を追加
 unchosen edgeはtime-outするとsearch
命令を送信する
 循環した自分のsearchを受信し、重みが
自分より大きかったらremove送信

20
２．２．Basic_MSTの実装（２）
a
[g,f],6
[g,f],6
b
4
5
c
[g,f],9
[g,f],6
9
3
[g,f],6
1
d
Insert ([g, f])
e
search ([g, f],6)
[g,f],9
[g,f],10 10
6
f
2
remove ([g,f],10)
g
[g,f],10
h
21
３．Self-Stabilizing MST
22
３．Self-Stabilizeのために

Basic_MSTに以下の機能を追加
search_sent ：search到着待ちstatus
 search命令に通ってきたpathを追加
pathは重みも保持する
 find_cycle ：chosen edgeが発する命令
→３*Safetime間メッセージを受信しない
と送信（Safetime：max{safetime(e)}）

23
３．Self-Stabilizingの実装（１）

各枝プロセッサが３つの変数を持つ
boolean chosen_status
 unsigned int timer
 boolean search_sent


３種類のメッセージ
(“search”, eid, path)
 (“remove”, path)
 (“find_cycle”, path)

24
３．Self-Stabilizingの実装（２）

２種類の通信プロトコル
send(mess, e) (e:隣接する枝)
 propagate(mess, v) (v:ノード)


タイムアウトの機構
chosen edgeは3*Safetimeでtime-out
 unchosen edgeはSafetimeでtime-out

［配布資料参照］
25
３．Self-Stabilizingの実装（３）
a
[g, f], path
[g, f], path
b
4
5
[g, f], path
c
9
3
[g, f], path
1
d
e
search ([g, f], φ)
10
6
g
f
2
h
26
３．Self-Stabilizingの実装（４）
a
[g, f], [fhebc]
5
b
4
c
remove ([fhebc])
cycle
3
9
[g, f], path
1
d
e
search ([g, f], φ)
10
2
6
g
f
７
[g, f], [fh]
[g, f], [fhe]
h
27
３．正当性の直観的な証明
MSTとなるべき枝が一度chosen edge
になったらそれは二度とremoveされない
 時間を重ねれば重ねるほど、生成木全
体のコストは小さくなっていく
 MSTとなるべき枝がまだchosen edgeで
なかったら、必ずchosen edgeになる
 一度MSTが構築されたら、エラーが無い
限りMSTは不変

28
３．現実に適用するために
各枝がプロセッサを持っていると仮定
→各ノードがそれぞれの枝を担当
→枝を挟む相手の情報が欲しい
 大規模ネットワークでのSafetimeの設定

ネットワーク全体を知ることは不可能
 Safetime大：ネットワークトラフィック減
 Safetime小：エラーに即座に対応

29
まとめ

MSTとは


コスト最小の生成木を構成
Self-Stabilizing MST
エラーを自動的に修復
 ノードの増減が激しいインターネットにも
適用可能

30

Download Report