構造化オーバレイと P2Pアーキテクチャの研究動向1 情報工学専攻 FM10005　尾上達彦

アウトライン 構造化オーバレイの実例 5.1 5.2 5.3 5.4 構造化オーバレイの事例 5.5 Chord（コード） Pastry（パストリー） 5.2 Kademlia（カデムリア） 5.3 Skip Graph（スキップ・グラフ） 5.4 構造化オーバレイの事例 BitTorrent（ビットトレント） 5.5

5.1 Chord 分散ハッシュテーブル（DHT）を代表するアルゴリズムの一つ 2001年にMITのPDOSグループ※が発表 K7 ノードN8が ファイルK7を格納 N43 N1 N8 時計回りで最初にいるノード（プレデセッサ・ノード） 反時計回りで最初にいるノード（サクセッサ・ノード）を決定 N30 N16 ノードN24が ファイルK18を格納 K18 N24 ※Parallel & Distributed Operating Systems Group（並列分散OSグループ）

Chordのルーティング例 ノード アクセス 探索に時間がかかる ファイルの所有者（P） ルックアップ 時計周りで最初に存在するノードがファイルを格納する ルックアップ Pの位置を得る ファイルを欲しい人 ファイル位置を格納しているノードから

フィンガー・テーブルと動作 名称 説明 ルックアップでの役割 維持コスト サクセッサ・リスト 識別子距離が最も近いノードへの経路 サクセッサ・リストにルックアップを順々に伝播させてもルックアップ可能 低い フィンガー・テーブル 2kずつ遠い識別子距離のノードへの経路 全て正しければ、ノード総数に対して対数オーダーでルックアップ可能 高い N1 N8 + 2k リンクするリスト N8+1(k=0) N16 N8+2(k=1) N8+4(k=2) N8+8(k=3) N20 N8+16(k=4) N32 N8+32(k=5) N40 ルックアップ N52 N8 N45 k = 3 k = 5 N40 N16 N8のフィンガー・テーブル N20 N32 N24

ノードの参加・離脱が発生する場合 ノードの離脱 ノードの参加 N1 N8 N43 N16 N32 ファイルを格納 K18 各フィンガー・テーブルリストを更新 N20のサクセッサ・リストにN32を追加 N32のプレデセッサ・リストにN20を追加 ノードの離脱が起きたので N16 N32 ファイルを格納 K18 各フィンガー・テーブルリストを更新 N16のサクセッサ・リストに追加 N28のプレデセッサ・リストに追加 N20 N28 K25 ノードの参加 ノードの離脱

5.2 Pastry マイクロソフト社とライス大学が開発されたDHTの実装を目的とし たP2Pシステム 目的のIDを探索する為にPlaxton（プラクストン）アルゴリズムを 採用しているのが特徴 オープンな実装としてはFreePastryとBambooが有名 Plaxtonアルゴリズム ノードIDとして、決まった基数と桁数を持つ整数を使う 例えばノードID = 123456というノードのルーティングテーブルは、1桁目が1以外であるノードの集合、1桁目が1だが2桁目が2以外であるノードの集合…という具合で構成されており、上から最長一致（プレフィックス一致長）したノードへ検索が転送される

Plaxton構造とルーティング例 ノード302を検索する場合、まず目的ノードとの桁数が一致する近接ノード を選び出し、上位から1桁ずつ数字を揃える 233 230 出発点 321 123 323 302 133 301

Pastryのルーティング手順 目的キーがリーフセット（自分の近くのノードの場所を記憶してい る表）内に含まれているとき、最もIDが近いノードにメッセージを 転送 ①でない場合、ルーティング・テーブルから次に転送すべきノー ドを探し、そのノードにメッセージを転送 ルーティング・テーブルにエントリーがない場合、リーフセットから 自ノードよりIDの近い候補を探し、そのノードにメッセージを転送 リーフセットにIDの近い候補がない場合は、自ノードが目的ノー ドになる

Pastryのノード状態とルーティング例 10223220が目的のキーの時 10222302から探索…を繰り返す ノードID　10233102 ①探索 リーフセット 小さな値 大きな値 ③最も近いノードIDを探索 10233033 10233020 10233001 10233000 10233120 10233122 10233230 10233232 ルーティングテーブル -0-2212102 1 -2-2301203 -3-1203203 1-1-301233 1-2-230203 1-3-021022 10-0-31203 10-1-32102 2 10-3-23302 102-0-0230 102-1-1302 102-2-2302 3 1023-0-322 1023-1-000 1023-2-120 10233-0-01 102331-2-0 ②探索

5.3　Kademlia 発表された際の内容が実用性を重視しており、XOR （排他的論 理和）を使ったシンプルなプログラムであったことから人気になった Cordと同等の機能を有するが、Cordがリング状にノードを配置し ているのに対し、Kademliaでは二分木のような構造上にノードを 配置する ノード管理 あるキーとバリューの組をどのノードが管理するかは、そのキーとノードのプレフィックス一致長で決まり、一番長いノードが管理ノードとなる。実際にはXORをID空間の距離関数とすることで実現できる プレフィックス一致長が一番大きいノード＝XOR距離が一番小さいノード

k-bucket 4ビットのID空間を想定し、あるノードIDが0101だとするとルー ティングテーブルは となる（*は0か1） これらルーティングテーブル内のノードの集合をk-bucket（ケー・ バケット）と呼び、最大kノード格納できる 4ビットの場合、約4kノードが格納される プレフィックス一致長 XOR距離 ノードID 3 1 0100 2 2～3 011* 4～7 00** 8～15 1***

k-bucket例とルーティング例 0101のk-bucket 0101から1110へのルーティング ノードID = 1*** プレフィックス長 = 0 （XOR距離 = 8～15） ノードID = 00** プレフィックス長 = 1 （XOR距離 = 4～7） ノードID = 011* プレフィックス長 = 2 （XOR距離 = 2～3） ノードID = 0100 プレフィックス長 = 3 （XOR距離 = 1） 0000　　0001　　0010　　0011　　0100　　0101　　0110　　0111　　1000　　1001　　1010　　1011　　 1100　 1101　　 1110　　1111　 　　

Kademliaの特徴・採用しているシステム ルーティングテーブルが対称性を持っているので、ルーティングテーブルの更新をメッセージの受信によって行うことができ、効率がよい メッセージを受信するたびにk-bucketを更新し、古いノードから消していく機構があり、これによって常にルーティングテーブルを新鮮に保つことができる Kademliaを採用しているシステム システム名 特徴 Overnet 最古のシステム、その後eDonkeyに吸収 eMule Kadネットワークと呼ばれる Khashmir BitTorrentにより採用された Kenosis P2P RPC（Remote Procedure Call）システム BitTorrent トラッカーレスで使われる Azureus 同じくトラッカーレスで使われるがBitTorrentと互換性なし

5.4 Skip Graph DHTアルゴリズムとは異なる機能を持つ ノードIDを割り当てる際に別にキーが割り当てられる キーを探索する為にSkip Listを用いる Skip Listは1990年にW.プフが提案したバランス木を構成する ためのデータ構造 ヘッド テール n3 level2 level1 level0 n1 n4 n2 n5 n6 Skip listのデータ構造

Skip Graphの例 Skip Listの拡張版のようなもので、探索する際はどのノードから始めても よい 最初のノードが決まったら、Skip Listと同じように上位のレベルから下位 のレベルに向かって探したいノードに向かって移動する n1 n2 n3 n4 n5 n6 level2 level1 level0 Skip List Skip Graphのデータ構造

5.5 BitTorrent P2Pファイル配信アプリケーション 大容量のファイルを素早く、低コストで配信することを目的に、2001 年に開発された 特徴 ピアの状態を管理する為のサーバ（トラッカー）が存在する ファイルを持つピアの検索は行わず、代わりに各ピアがトラッカーにファイルを持っているピアを問い合わせる ファイルをピースと呼ばれる単位に分割して、ピース単位でダウンロードする トレントファイルを取得してからでないと、 P2Pから本体ファイルをダウンロードできない 「相手（ピア）からピースを受け取るには、自分もピースを渡さなければならない」という規則を導入したため、貧弱な帯域を持つユーザでも、全体のファイル配布に協力できるようにした

BitTorrentの動作 サーバはそれぞれ異なる断片を、常にピアの一部だけに配布し、各ピア は、ピアやサーバから断片をダウンロードすると同時に自分の持つ部分を 持っていないピアにアップロードする DHT検索 DHTネットワーク ピアのリスト取得 torrentファイルのダウンロード サーバ

BitTorrentのアルゴリズム：１ ピース選択アルゴリズム ダウンロードするファイル・ピースの順番は、ダウンロード効率に大きく影響する 　　　ダウンロードするファイル・ピースの順番は、ダウンロード効率に大きく影響する 取得中のピースのダウンロードに集中戦略 　　　　現在ダウンロードしようとしているピースに集中。BitTorrentでは1つのピースを複数のサブピースに分割してダウンロードし、完全なピースが確認できたら完全性をチェックする。その後、他ピアからのダウンロード対象となる 希少ピースを優先戦略 　　　　1つのピースのダウンロードが完了すると、各ピアがもっているピースのうち、最も少ないピースをダウンロードする。ピアの離脱時、そのピアしか特定のピースを持っていなかった場合にピースを取得できなくなる可能性があるので 最初はランダム戦略 　　　　2が採用されない例外がBitTorrentクライアントの起動直後 EndGameモデル 　　　　ファイルのダウンロードの最終段階では、最後のサブピースは一斉に複数のピアからダウンロードする

BitTorrentのアルゴリズム：２ チョーク・アルゴリズム（アップロードするピアを決める方法） 　　　ファイル共有を目的とした多くのP2Pでは、ファイルの需要と供給のバランスの上 に成り立っており、BitTorrentではこれを「囚人のジレンマ」の「しっぺ返し戦略」 をもとに調整している 基本的なチョーク・アルゴリズム 　　　　各ピアは、一定数のピアに対してアップロードを許可（アンチョーク状態）する。アンチョーク状態にするピアの選択はダウンロード速度によって決める 楽天的なアンチョーク戦略 　　　　30秒ごとにピアのリストから順々にアンチョーク状態にする。 反冷遇主義戦略 　　　　1分以上、アンチョーク状態のピアからピースを全く取得できなかった場合は、そのピアをチョーク状態にする。この時、(2)が働き代わりを見つける。また、一度冷遇されたピアに対しては、アンチョーク状態にしないようにする。 アップロード・オンリー 　　　　全ピースのダウンロードが終了すると、(1)をする必要がないので、アップロード速度が速いピアをアンチョーク状態にする戦略に変更