2019/4/20 Progress Report 修士2年 金田　憲二 2019/4/20 全体ミーティング

Progress Report この一ヶ月ぐらいでやったことについて PhoenixのNaiveな実装 上田さんの修論・関連研究のサーベイ 2019/4/20 全体ミーティング

Outline of the Presentation Overview of Phoenix API Execution Example Implementation of Phoenix Join/Leave Algorithm Routing Algorithm Summary Related Work Future Work 2019/4/20 全体ミーティング

Background Peer-to-Peer Systemの普及 特徴 e.g.) Gnutella 多数のノードが計算に参加 ノードが頻繁に参加・脱退 個々のノードが自律的に動作 decentralized 2019/4/20 全体ミーティング

Phoenix 広域並列計算システムのためのフレームワーク 概要 P2Pシステムを簡便に記述するためのライブラリを提供 通信ライブラリ 仮想的なノード番号集合が存在 例) 0~216-1 各ノードに分割して割り当てられている ノードの参加・脱退によって、分割は動的に変化 仮想ノード番号で宛先を指定してメッセージを送信 2019/4/20 全体ミーティング

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) 自分宛のメッセージを受信 自分宛=今現在自分が担当している仮想ノード番号宛 2019/4/20 全体ミーティング

Example of Execution (1/2) broadcastを行うprogram (Figure 1参照) root nodeの場合 0~15番にメッセージを送信する 暫く待つ メッセージの受信を繰り返す root node以外の場合 Join (隣接ノードから仮想ノード番号集合を受け取る) 注)root node プログラム起動時に利用者が指定 起動時に全ての仮想ノード番号 (0~15)を担当 自ノードがrootかどうかの判定はphoenix_is_root()で行う 2019/4/20 全体ミーティング

Example of Execution (2/2) 3ノードでの実行結果 > ./run –r rootとして起動 (ノード番号0~15を担当) send message to 0 … send message to 15 8~15番を委譲 Join 12~15番を委譲 Join > ./run > ./run recv message from 0 recv message from 1 … recv message from 7 recv message from 8 … send message from 11 recv message from 12 … send message from 15 2019/4/20 全体ミーティング

Other Examples of Execution Scalable distributed hash table hashのkeyとノード番号が対応 例) 分散ファイル共有システム scalable distributed queue? 2019/4/20 全体ミーティング

Outline of the Presentation Overview of Phoenix API Execution Examples Implementation of Phoenix Join/Leave Algorithm Routing Algorithm Summary Related Work Future Work 2019/4/20 全体ミーティング

Join/Leave Algorithm ノードの追加・脱退時のアルゴリズム 上田さんの修士論文を少し変更したもの (Figure 2,3,4参照) 2019/4/20 全体ミーティング

Invariants of Join/Leave Algorithm アルゴリズム中で常に成り立つ性質 各ノードの仮想ノード番号集合はdisjoint 各ノードの仮想ノード番号集合の和は不変 ただしjoin, leaveの最中は別 2019/4/20 全体ミーティング

Routing Algorithm メッセージの配送 メッセージをノード番号で指定された宛先に転送する必要がある どのノードがどの仮想ノード番号を担当しているのか？ TCP/IPだけでは任意のノードで通信可能とならない 例) Firewall, Private IP Application LevelでRoutingを行う必要がある 2019/4/20 全体ミーティング

Distance-Vector Routing (1/3) 2019/4/20 Distance-Vector Routing (1/3) Distance Vector Routing 最も基本的なルーティング 今現在の実装 基本的なアイディア 以下の式でshortest pathを計算 d(u,v) = minwはuの隣接ノード{d(u,w) + d(w,v)} Neigh : uの隣接ノード 右辺の2項目の情報を交換 隣接ノードの数×全ノード uからvへの最短距離 隣接ノードwを中継したときのuからvへの最短距離 2019/4/20 全体ミーティング

Distance-Vector Routing (2/4) メッセージの転送方法 ノードuからノードvへのメッセージの転送 以下の式でminとなる隣接ノードwに転送 d(u,v) = minwはuの隣接ノード{d(u,w) + d(w,v)} 2019/4/20 全体ミーティング

Distance-Vector Routing (3/4) Routing Table 個々のノードはネットワークの全体像を知らない 自ノードに関する情報のみ把握している 右辺第2項の情報を隣接ノード間で交換 d(u,v) = minwはuの隣接ノード{d(u,w) + d(w,v)} この情報はuは知っている この情報はuは知らない 2019/4/20 全体ミーティング

Distance-Vector Routing (4/4) 欠点 動的なトポロジーの変化への適応が遅い ループの検出が遅い ルーティングテーブルが大きい 隣接ノード全てにコネクションを張らなければいけない 以上の問題の解決を目指す 2019/4/20 全体ミーティング

Landmark Routing (1/4) 利点 基本的なアイディア ルーティングテーブルの縮小 仮想ノード番号を2b進数で表記 共有するprefixの桁数が増加する方にメッセージを転送 2019/4/20 全体ミーティング

Landmark Routing (2/4) メッセージの転送方式 共有するprefixの桁数が大きくなるほうに転送 hop数はO(log2b N) ただしNはノードの数 例)ノード2011から2200へのメッセージの送信 2202 2123 2200 2012 2201 2203 2019/4/20 全体ミーティング

自分とまったくprefixを共有しないノード宛 Landmark Routing (3/4) Routing Table log2b N ×2b ただしNはノード数 例)2012のルーティングテーブル ただしb=2として4進数 自分とまったくprefixを共有しないノード宛 0***=a 1***=b 3***=c 21**=d 22**=e 23**=f 200*=g 202*=h 203*=i 2010=j 2011=k 2013=l 自分とprefixを1桁共有するノード宛 自分とprefixを2桁　共有するノード宛 2019/4/20 全体ミーティング

Landmark Routing (4/4) 問題 任意のノード間で通信可能であることを仮定 irregularなgraphの場合、必ずしもprefixをより共有する方へと通信できるとは限らない 2019/4/20 全体ミーティング

Landmark + Distance Vector Routing (1/2) 上田さんの修士論文 landmarkで通信できないところにdistance vector routing を行う 上田さんのアルゴリズムの細かい所理解できず とりあえず単純なversionを自分で書き下してみた 2019/4/20 全体ミーティング

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列目に対応するノード番号集合 2019/4/20 全体ミーティング

Outline of the Presentation Overview of Phoenix API Execution Examples Implementation of Phoenix Join/Leave Algorithm Routing Algorithm Summary Related Work Future Work 2019/4/20 全体ミーティング

Related Work P2Pシステムを簡単に記述するための枠組み 具体的にはdistributed hash tableを提供 hash tableはscalableかつfault-tolerant 例) Pastry, CAN, … 2019/4/20 全体ミーティング

Pastry Pastry 計算に参加するノードがHash Tableを共有 基本的なアイディア 2019/4/20 Pastry Pastry 計算に参加するノードがHash Tableを共有 基本的なアイディア 個々のノードにrandomにノード番号を割り当て hashのkeyがノード番号で表される hashへのアクセスにはlandmark routing 2019/4/20 全体ミーティング

CAN (1/4) CAN (Content Addressable Network) 計算に参加するノードがHash Tableを共有 2019/4/20 全体ミーティング

CAN (2/4) 基本的なアイディア zone ハッシュテーブルへの操作 仮想的なd次元上のtorusが存在 2019/4/20 CAN (2/4) 基本的なアイディア zone 仮想的なd次元上のtorusが存在 各ノードに分割して割り当てられている ノードの参加・脱退によって割り当ては動的に変化 ハッシュテーブルへの操作 hashのkeyとzone上の座標が対応 hashへのアクセスにはrouting 2019/4/20 全体ミーティング

CAN (3/4) ノードの追加 ノードの脱退 ただしd=2 A B A C A B C A B A A B 15 8 0 15 8 0 15 8 0 15 8 0 15 8 0 A B A C A B 0 8 15 0 8 15 0 8 15 ノードの脱退 15 8 0 15 8 0 15 8 0 C A B A A B 0 8 15 0 8 15 0 8 15 2019/4/20 全体ミーティング

CAN (4/4) メッセージの配送 個々のノードは自分の隣接ノードを把握 目的座標に近づくように隣接ノード間を転送される D C A B (13,13) 15 8 0 0 8 15 2019/4/20 全体ミーティング

Future Work (1/2) とりあえず実装の続きをやる Routingの効率化 インターフェースの整理 Application Objectの委譲 etc. 2019/4/20 全体ミーティング

Future Work (2/2) reliableな通信 fault tolerance メッセージの再送 2019/4/20 Future Work (2/2) reliableな通信 メッセージの再送 メッセージのreordering fault tolerance なんらかの原因によってノード番号集合が欠けてしまったことの検出・対処 プログラムエラーで永遠にメッセージが配達できなくなったり，同じノード名が2重に登録されたりしたときに，システムがそれをどう検地するのか 2019/4/20 全体ミーティング

Summary Progress Report PhoenixのNaiveな実装 上田さんの修論・関連研究のサーベイ 2019/4/20 全体ミーティング

References (1/2) P2P System CAN Pastry 2019/4/20 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 2019/4/20 全体ミーティング

References (2/2) Routing Landmark Routing Distance Vector 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 2019/4/20 全体ミーティング