Progress Report

Progress Report
修士2年
金田憲二
2015/10/1
全体ミーティング
1
Progress Report
この一ヶ月ぐらいでやったことについて


PhoenixのNaiveな実装
上田さんの修論・関連研究のサーベイ
2015/10/1
全体ミーティング
2
Outline of the Presentation
Overview of Phoenix


API
Execution Example
Implementation of Phoenix


Join/Leave Algorithm
Routing Algorithm
Summary


Related Work
Future Work
2015/10/1
全体ミーティング
3
Background
Peer-to-Peer Systemの普及

e.g.) Gnutella
特徴



多数のノードが計算に参加
ノードが頻繁に参加・脱退
個々のノードが自律的に動作
 decentralized
2015/10/1
全体ミーティング
4
Phoenix
広域並列計算システムのためのフレームワーク

P2Pシステムを簡便に記述するためのライブラリを提供
概要


通信ライブラリ
仮想的なノード番号集合が存在
 例) 0~216-1
 各ノードに分割して割り当てられている
 ノードの参加・脱退によって、分割は動的に変化

仮想ノード番号で宛先を指定してメッセージを送信
2015/10/1
全体ミーティング
5
Interface of Phoenix
phoenix_join()
 ノード番号集合を隣接ノードから譲り受ける
phoenix_leave()
 自ノード担当の仮想ノード番号集合を、他ノードに委譲
phoenix_send(ph_vp_t vp, void * buf, size_t len)
 仮想ノード番号vp宛にメッセージを送信
phoenix_recv(void * buf, size_t len)
 自分宛のメッセージを受信
 自分宛=今現在自分が担当している仮想ノード番号宛
2015/10/1
全体ミーティング
6
Example of Execution (1/2)
broadcastを行うprogram (Figure 1参照)

root nodeの場合
1. 0~15番にメッセージを送信する
2. 暫く待つ
3. メッセージの受信を繰り返す

root node以外の場合
1. Join (隣接ノードから仮想ノード番号集合を受け取る)
2. メッセージの受信を繰り返す

注)root node



2015/10/1
プログラム起動時に利用者が指定
起動時に全ての仮想ノード番号 (0~15)を担当
自ノードがrootかどうかの判定はphoenix_is_root()で行う
全体ミーティング
7
Example of Execution (2/2)
3ノードでの実行結果
rootとして起動
(ノード番号0~15を担当)
> ./run –r
send message to 0
…
send message to 15
Join
Join
> ./run
> ./run
recv message from 0
recv message from 1
…
…
recv message from 7
2015/10/1
recv message from 8
8~15番を委譲
send message from 11
recv message from 12
…
send message from 15
全体ミーティング
12~15番を委譲
8
Other Examples of Execution
Scalable distributed hash table


hashのkeyとノード番号が対応
例) 分散ファイル共有システム
scalable distributed queue?
2015/10/1
全体ミーティング
9
Outline of the Presentation
Overview of Phoenix


API
Execution Examples
Implementation of Phoenix


Join/Leave Algorithm
Routing Algorithm
Summary


Related Work
Future Work
2015/10/1
全体ミーティング
10
Join/Leave Algorithm
ノードの追加・脱退時のアルゴリズム


上田さんの修士論文を少し変更したもの
(Figure 2,3,4参照)
2015/10/1
全体ミーティング
11
Invariants of Join/Leave
Algorithm
アルゴリズム中で常に成り立つ性質


各ノードの仮想ノード番号集合はdisjoint
各ノードの仮想ノード番号集合の和は不変
 ただしjoin, leaveの最中は別
2015/10/1
全体ミーティング
12
Routing Algorithm
メッセージの配送

メッセージをノード番号で指定された宛先に転送する必
要がある
 どのノードがどの仮想ノード番号を担当しているのか？

TCP/IPだけでは任意のノードで通信可能とならない
 例) Firewall, Private IP
Application LevelでRoutingを行う必要がある
2015/10/1
全体ミーティング
13
Distance-Vector Routing (1/3)
Distance Vector Routing


最も基本的なルーティング
今現在の実装
基本的なアイディア

以下の式でshortest pathを計算
d(u,v) = minwはuの隣接ノード{d(u,w) + d(w,v)}
uからvへの最短距離
2015/10/1
隣接ノードwを中継したときのuからvへの
最短距離
全体ミーティング
14
Distance-Vector Routing (2/4)
メッセージの転送方法

ノードuからノードvへのメッセージの転送
 以下の式でminとなる隣接ノードwに転送
d(u,v) = minwはuの隣接ノード{d(u,w) + d(w,v)}
2015/10/1
全体ミーティング
15
Distance-Vector Routing (3/4)
Routing Table

個々のノードはネットワークの全体像を知らない
 自ノードに関する情報のみ把握している

右辺第2項の情報を隣接ノード間で交換
この情報はuは
知っている
この情報はuは知
らない
d(u,v) = minwはuの隣接ノード{d(u,w) + d(w,v)}
2015/10/1
全体ミーティング
16
Distance-Vector Routing (4/4)
欠点

動的なトポロジーの変化への適応が遅い
 ループの検出が遅い


ルーティングテーブルが大きい
隣接ノード全てにコネクションを張らなければい
けない
以上の問題の解決を目指す
2015/10/1
全体ミーティング
17
Landmark Routing (1/4)
利点

ルーティングテーブルの縮小
基本的なアイディア


仮想ノード番号を2b進数で表記
共有するprefixの桁数が増加する方にメッセー
ジを転送
2015/10/1
全体ミーティング
18
Landmark Routing (2/4)
メッセージの転送方式


共有するprefixの桁数が大きくなるほうに転送
hop数はO(log2b N)
 ただしNはノードの数

例)ノード2011から2200へのメッセージの送信
2123
2202
2200
2012
2201
2015/10/1
2203
全体ミーティング
19
Landmark Routing (3/4)
Routing Table

log2b N ×2b
 ただしNはノード数

例)2012のルーティングテーブル
自分とまったく
prefixを共有しない
ノード宛
 ただしb=2として4進数
0***=a
1***=b
21**=d
200*=g
2010=j
2015/10/1
3***=c
22**=e
23**=f
202*=h
203*=i
2011=k
2013=l
全体ミーティング
自分とprefixを1桁
共有するノード宛
自分とprefixを2桁
共有するノード宛
20
Landmark Routing (4/4)
問題


任意のノード間で通信可能であることを仮定
irregularなgraphの場合、必ずしもprefixをより
共有する方へと通信できるとは限らない
2015/10/1
全体ミーティング
21
Landmark + Distance Vector
Routing (1/2)
上田さんの修士論文

landmarkで通信できないところにdistance vector
routing を行う
上田さんのアルゴリズムの細かい所理解できず
とりあえず単純なversionを自分で書き下してみた
2015/10/1
全体ミーティング
22
Landmark + Distance Vector
Routing (2/2)
ルーティングテーブルの縮小


下の式でdistance-vector algorithmを行う
(Figure6,7,8,9参照)
コネクションの削減


定期的にルーティングに使用していないコネクションの
削除
(Figure 10参照)
d(u,Δu(i,j)) = minwはuの隣接ノード{d(u,w) + d(w,Δu(i,j))}
Δu(i,j) : ノードuのi行j列目に対応するノード番号集合
2015/10/1
全体ミーティング
23
Outline of the Presentation
Overview of Phoenix


API
Execution Examples
Implementation of Phoenix


Join/Leave Algorithm
Routing Algorithm
Summary


Related Work
Future Work
2015/10/1
全体ミーティング
24
Related Work
P2Pシステムを簡単に記述するための枠組み

具体的にはdistributed hash tableを提供
 全ノード間で共有されるhash tableが存在
 hash tableはscalableかつfault-tolerant

例) Pastry, CAN, …
2015/10/1
全体ミーティング
25
Pastry
Pastry


計算に参加するノードがHash Tableを共有
基本的なアイディア
 個々のノードにrandomにノード番号を割り当て
 hashのkeyがノード番号で表される
 hashへのアクセスにはlandmark routing
2015/10/1
全体ミーティング
26
CAN (1/4)
CAN (Content Addressable Network)

計算に参加するノードがHash Tableを共有
2015/10/1
全体ミーティング
27
CAN (2/4)
基本的なアイディア

zone
 仮想的なd次元上のtorusが存在
 各ノードに分割して割り当てられている


ノードの参加・脱退によって割り当ては動的に変化
ハッシュテーブルへの操作
 hashのkeyとzone上の座標が対応
 hashへのアクセスにはrouting
2015/10/1
全体ミーティング
28
CAN (3/4)
ノードの追加
15
15
A
8
0
ただしd=2
0
8
15
0
0
A
B
0
2015/10/1
0
A
8
8
15
0
0
A
B
0
8
15
15
B
8
15
C
8
15
C
8
B
8
 ノードの脱退
15
15
0
A
8
A
8
15
全体ミーティング
0
0
8
15
29
CAN (4/4)
メッセージの配送


個々のノードは自分の隣接ノードを把握
目的座標に近づくように隣接ノード間を転送される
 例) Bから (13,13)へのメッセージの転送
(13,13)
15
D
C
A
8
B
0
2015/10/1
0
全体ミーティング
8
15
30
Future Work (1/2)
とりあえず実装の続きをやる


Routingの効率化
インターフェースの整理
 Application Objectの委譲
 etc.
2015/10/1
全体ミーティング
31
Future Work (2/2)
reliableな通信


メッセージの再送
メッセージのreordering
fault tolerance

なんらかの原因によってノード番号集合が欠け
てしまったことの検出・対処
2015/10/1
全体ミーティング
32
Summary
Progress Report


PhoenixのNaiveな実装
上田さんの修論・関連研究のサーベイ
2015/10/1
全体ミーティング
33
References (1/2)
P2P System

CAN
 "A Scalable Content-Addressable Network"
 Sylvia Ratnasamy, et al.
 U.C. Berkeley and AT&T
 SIGCOMM 2001

Pastry
 "Pastry : Scalable, distributed object location and routing
for large-scale peer-to-peer systems"
 A.Rowstron et al.

Microsoft Research
 Middleware 2001
2015/10/1
全体ミーティング
34
References (2/2)
Routing

Landmark Routing
 "Accessing Nearby Copies of Objects in Distributed
Environment"
 C. Greg Plaxton et al.
 SPAA 1997

Distance Vector Routing
 "Introduction to Distributed Algorithm"
 Gerard Tel
 Cambridge Press, 1994
2015/10/1
全体ミーティング
35

Download Report