狠狠撸

狠狠撸Share a Scribd company logo

kibayos-PIAX & SkipGraph-071207

?
?
M
Mikio Yoshida
1 of 52
Downloaded 22 times
2007/12/7 情報処理学会関西支部講演会 技術紹介: P2Pエージェントプラットフォーム PIAX と 構造化オーバレイ Skip Graph 吉田 幹 （株）ビービーアール （株）ビ ビ ア ル, 大阪大学（招聘研究員） 大阪大学
Agenda PIAX 設計コンセプト アーキテクチャ API Skip Graph Skip List Skip Graph 関連研究 トピック Multi-key Skip Graph Multi-key Skip Graphを使ったオーバレイの実装 2
P2Pエージェントプラットフォーム P2Pエ ジ ントプラ トフォ ム PIAX ※PIAXの 部は、総務省委託研究 ビキタスネットワ ク認証 ※PIAXの一部は、総務省委託研究「ユビキタスネットワーク認証?エージェ ジェ ント技術の研究開発」の一環として開発されたものです
共通プラットフォームのニーズ ユビキタスネットワーク PCに加え、携帯電話、PDA、家電機器、自動車、センサ、 PCに加え 携帯電話 PDA 家電機器 自動車 センサ ロボット、ウェアラブルなど、多種多様のデバイスがネット ワークに接続 3C(Computing, Connectivity, Contents) everywhere 課題 大量のオブジェクトから必要なものを瞬時に発見する 発見したオブジェクトを使って高度なサ ビスを構成する 発見したオブジェクトを使って高度なサービスを構成する ユーザの位置や、情報間の関係に基づくオブジェクトの ユ ザの位置や 情報間の関係に基づくオブジ クトの 発見と連携をスケーラブルに実現するための 共通プラットフォ ムが必要 共通プラットフォームが必要 4
ユビキタスサービスの実現イメージ PIAXは共通プラットフォームとして機能 Reputation Shopping Navigation Sharing ss sta t Assistant Recommendation Streaming Various ubiquitous applications Agents g P2P Overlay Network PIAX Flexible Computing by Mobile Agents Scalable Messaging Peer by P2P Overlay Profiles Reputations Sensors Contents Devices Users 5
近傍性、近接性と相互作用 ＜ユビキタスコンピューティングの処理の流れ＞ 1. ユーザ位置を同定 ザ位置を同定 2. 近傍、近接オブジェクトの探索 近傍に位置するオブジェクト ? 物理空間における近傍性 仮想空間上に蓄積された関連性のあるオブジェクト ? 意味空間における近接性 3. 探索されたオブジェクト（複数のサービス主体と能動的オブ ジ クト）の相互連携によりサ ビスを実現 ジェクト）の相互連携によりサービスを実現 「ユビキタスサービスは、ユーザ（群）とその近傍、近接 にあるオブジェクト間における相互作用により実現される」 6
ユビキタスP2Pサービス セマンティックWebとP2Pシステムの進化融合形 セマンティックWebサービスから見れば、P2P拡張 見 、 張 P2Pシステムから見れば、第４世代P2Pとして知識高度化 Web Services Semantic Web Semantic Web Services Ubiquitous P2P Service Pure P2P Structured Hybrid P2P Unstructured Overlay 1st generation 2nd generation 3rd generation 7
P2Pエージェントプラットフォーム PIAX ユビキタスP2Pサービスの1つの実現形 P2P Interactive Agent eXtentions の略 （エージェントの相互作用を表現） Agents P2Pエージェント P2Pネットワ ク上に分散 P2Pネットワーク上に分散 する相互連携性と自律性 discovery power を持ったオブジェクト サービス主体と能動的オ ビ ブジェクトを含めたオブジェ P2P Overlay Network クトを表現 オーバレイの持つ強力な 資源探索機能を活用することで、“what to find” をス ケーラブルに実現 8
Discovery Messaging オーバレイによって強化されたP2Pエージェントの持つ新し いメッセージング機構 “what to find” を実現する クエリ条件が “what” に相当 擬似言語で表現すると、(b)を実現することになる (a) send(destinationAddress, message); (b) send(queryCondition, message); d( C d ) 次のようなクエリ条件なら、指定された地理的矩形に含まれ、 次のようなク リ条件なら 指定された地理的矩形に含まれ メソッド getTemperature を持つエージェントがメッセージン グ対象となる in rectangle(135.0, 35.0, 1.0, 1.0) and has getTemperature method 9
PIAXのアーキテクチャ (1) Ubiquitous Applications - Context-aware Bayesian - RDF DB - Poe (Prolog Engine) ??? Agent library ??? JSONP- RPC P2P Agents ecure Support LL-Net Discovery Messaging y g g DHT Multi-Overlay plug- plug ALM Auth, Se RPC ins Overlay Transport Social-Net Physical Network ??? 10
PIAXのアーキテクチャ (2) RPC / Overlay Transport Socket通信の隠蔽、NAT越えのサポート 上位レイヤに対し、ピアIDを使った高レベルの通信手段を提供 上位レイヤに対し ピアIDを使った高レベルの通信手段を提供 Multi-Overlay 複数のオーバレイ機能を管理 LL-Net, DHT, ALM, ソーシャルネット等 Discovery Messaging Multi Overlayレイヤと連携し、discovery Multi-Overlayレイヤと連携し、discovery messagingを実現 上位レイヤに対し、オーバレイの実装を隠蔽 P2P Agents P2Pエージェントの稼働環境（API） P2Pエ ジ ントの稼働環境（API） JSONP JSONP- RPC P2P A Agents Auth, Secure Support を提供 Discovery Messaging JSONP-RPC Multi-Overlay e 外部システムとの通信手段を提供 Auth, Secure Support RPC Overlay Transport ピアおよび ピアおよびエージェントの認証等 ジェントの認証等 Physical Network 11
マルチオーバレイ 共通的なプラットフォームとして機能するためには、アプリ ケーションからの様々な探索要求に応える必要がある 複数のオーバレイネットワークを管理 オーバレイネットワークのプラグイン化 クエリパターン オーバレイネットワーク 完全一致探索 DHT, (Skip Graph) 部分一致探索 DHT+α 範囲探索（1またはN次元） Skip Graph, LL-Net 連想探索（SNSなど） Unstructured 意味探索 DHT+α ※複合的なクエリパターンを処理する機構（インターリーブ）については今後の課題 12
マルチオーバレイの機構 目的別にオーバレイを追加拡張するための機構 オーバレイを plug-in service として、ローディングと選択を 行う Discovery Messaging request with query condition -> query condition overlay table qc1 ov A selector qc2 ov B Multi-Overlay qc3 ov C registration Overlay A Overlay B Overlay C New Overlay use use plug-in: Multi-key call dynamic loading Skip Graph call RPC 13
代表的なオーバレイ (1) LL-Net (Location-based Logical P2P Network) 地理的探索のためのオーバレイ 特に、近傍オブジェクトの探索に効力を発揮 ピアの位置（緯度、経度）に基づいてオーバレイネットワークを構築? 維持 対象世界（地球全体）を矩形のエリアに分割し、階層的に管理 モバイル端末の接続?切断?移動に応じて、オーバレイネットワーク を動的に構成 エリア内リンク エリア間リンク 14
代表的なオーバレイ (2) DHT (key, (key value ) のペアをkeyのハッシュ値に従い分散管理 する ALM (Application Layer Multicast) アプリケーションレイヤにおける anycast および multicast を実現する ソーシャルネット SNSのバックボーンとなるオーバレイネットワーク ユビキタスでは、口コミ情報収集に活用 ? 人のセンサ化 人の関係を単方向グラフで表したリンク構造を元に形成 15
P2Pエージェントの状態遷移 一般的なモバイルエージェントシステムと同じ 生成（create）, 消滅（destroy）, 複製（duplicate）, 永続化 （sleep）, 永続状態からの復帰（wakeup）, 他のピアへの移 続 態 ピ 動（travel）等のメソッドがある 移動先の指定は、ピアIDで行う 移動先の指定は ピアIDで行う （IPアドレスは隠蔽される） moving sleeping sleep travel wakeup active duplicate create destroy 16
P2Pエージェントのモビリティ PIAXでは、エージェントに対し弱モビリティ（スタック を含むcontextの移動はしない）をサポート P2Pシステムにおける利点 帯域の効率的利用 通信頻度が高い相手の近傍にエージェントを移動させることで、 ネットワーク全体の帯域消費を抑える 負荷の平準化 負荷の高いエージェントを複製し、リクエスト元の近傍に移動さ せることで、全体負荷を平準化させる サービスの持続性 ユーザが利用するアクセスピアの変化に対し、サービスを追従さ せる アプリケーションの耐性 P2Pネットワークの構成変化（churn）に対するアプリケーション側 の耐性を高める 耐性を高める P2P特有 17
非同期、一方向、同報型メソッド呼び出し エージェント間の通信は、メッセージ送信ではなく、 RPC 操作透過性（ローカルとリモートをできるだけ区別しない） RPCの制約に対処するため、同期型に加え、非同 期、一方向、同報型のメソッド呼び出しを用意 呼び出し例 String name = remoteCall(peerId, agentId, “getName”); FutureReturn future = remoteCallAsync(peerId, agentId, “heavyCalc”, 123456); remoteCallOneway(peerId, agentId, notify ); remoteCallOneway(peerId agentId “notify”); ReturnSet rset = remoteCallMulti(peerId, filter, “getScore”); g ); 18
発見型メソッド呼び出し Discovery messaging の実現形態 P2Pエージェントの探索とリクエストを同時に行える メソッド定義 ReturnSet<Object> R S Obj discoveryCall(QueryCondition qCond, String method, Object... Object args) 呼び出し例 rset = h t home.discoveryCall(new Rectangle(135.0, di C ll( R t l (135 0 35.0, 1.0, 1.0), “getScore”, myProfile); 実行時には、クエリ条件がマルチオーバレイ機構に 実行時には クエリ条件がマルチオ バレイ機構に 渡され、適切なオーバレイが選択される 19
(PIAX video) 20
構造化オーバレイ Skip G h 構造化オ バレイ Ski Graph
Skip Graph Yale大学の J. Aspnes教授の研究による構造化オーバレイ 論文： J. Aspnes and G. Shah. Skip Graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Jan. 2003. 基本とするデータ構造は skip list（W. Pugh,1990）というバ ランス木 ノードは、IDとは別にkeyを持つ 指定された範囲のkeyを持つノードを効率よく探索できる 認知度は低いけど、実はパワフル 範囲探索 任意のkeyを持つオブジェクトをサーチ 任意 を持 オブジ ク を ALM PIAXにおいて、中核的な役割を果たしている PIAXにおいて 中核的な役割を果たしている 22
Skip List ノードはkey順に並ぶ レベル0のリストには全てのノードが含まれる レベルi-1に現れるノードはある確率pでレベルiに現れる（こ こでは簡単のため、p=1/2とします） 通常のバランス木と違い、ノードの追加?削除の際にバラン 通常のバランス木と違い ノ ドの追加 削除の際にバラン ス化の処理が不要 HEAD TAIL Level 2 L l 33 Level 1 L l 13 33 48 Level 0 L l 13 21 33 48 75 99 23
Skip List を使った検索 上位レベルから下位レベルに降りる形で処理が進む 平均検索時間は、ノード数をNとして、O(log N) 平均検索時間は、 ド数を して、 ( g ) 全順序関係が定義できるデータならすべて key として使うこ とができる（数値、文字列など）。片寄りがあってもよい HEAD から Key “75” を検索 75 HEAD TAIL Level 2 L l 33 Level 1 L l 13 33 48 Level 0 L l 13 21 33 48 75 99 24
Coffee Break: Skip List Java 6 から skip list が使えるようになりました java.util.concurrent.ConcurrentSkipListMap うれしいことにスレッドセーフ さらに、SortedMap より強力な NavigableMap が登場し、今 までできなかった次の処理ができるようになりました ま きなか た次 処理が きるよう なりま た 指定したkey以上の大きさを持つ最小のkeyを取得 等 TreeMap ConcurrentSkipListMap は次のように使い分け T M とC tSki Li tM ましょう TreeMap ConcurrentSkipListMap get,put,removeのコスト log N log N バランス処理 要 不要 スレッドセーフ NG OK メモリ消費のオーバヘッド 3*N+α 6*N+α 25
Skip Graph の構成 レベルi では membership vectorのプレフィックスの i桁が 一致するノード同士リンクをはる membership vector “レベルi-1に現れるノードは確率1/2でレベルiに現れる”性質を実現 するための2進整数（ランダムに分布） DHTでいうノードIDに相当 DHTでいうノ ドIDに相当 Key 21 33 Level 2 13 48 75 99 21 75 99 Level 1 13 33 48 Skip List Level 0 L l 13 21 33 48 75 99 Membership vector 000 100 010 001 110 111 26
Skip Graphでのkey検索 個々のノードから見ると、Skip List と同じ構造（アミ掛け部 分） Skip List と同じ検索アルゴリズムを実行 范囲検索も同様にできる key “33”のノードから key “75” を検索 Key 21 33 Level 2 13 48 75 99 21 75 99 Level 1 13 33 48 Skip List Level 0 L l 13 21 33 48 75 99 Membership vector 000 100 010 001 110 111 27
Skip Graphでのノード追加 (1) introducer（ここでは99）から挿入位置を検索 ? key “48” を見つける レベル0のリンクに新規ノードを挿入 21 33 Level 2 introducer 13 48 75 99 21 75 99 Level 1 13 33 48 Level 0 13 21 33 48 75 99 40 011 000 100 010 001 110 111 28
Skip Graphでのノード追加 (2) レベル1から上位レベルへ順番に、プレフィックスの一致す るノードから成るリンクに新規ノードを挿入 21 33 40 Level 2 13 48 75 99 21 75 99 Level 1 13 33 40 48 Level 0 13 21 33 40 48 75 99 000 100 010 011 001 110 111 29
DHTs vs. Skip Graph DHTs Skip Graph ID検索 通常 O(l N) O(log O(log O(l N) key検索 N/A O(log N) 范囲検索 NG O(log N) insert/delete O(log2 N) (*1) O(log N) 経路表 高さ 経路表の高さ ID長 長 log N g 経路表の対称性 ? Kademliaは有 有 insert/delete 時 不要 必要 の排他制御(*2) *1 Chord の場合 *2 排他制御の有無の理由については考察中 30
関連研究 (1) SkipNet 論文： N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman, “SkipNet: A scalable overlay network with practical locality properties,” USITS ’03, 2003. properties, 03, DHTが対象とする情報の格納範囲をネットワーク全体で はなく、近接のサブネットワークに制限 DHTが不得意とするローカリティ制御を実現 Skip B-Tree 論文： I. Abraham, J. Aspnes, and J. Yuan, “Skip B-trees,” in Principles of Distributed Systems; 9th International Conference, OPODIS 2005, Dec. 2005. B-Tree を導入し、keyをブロック化することで効率化 31
関連研究 (2) Rainbow Skip Graph 論文： M. T. Goodrich, M. J. Nelson, and J. Z. Sun, “The rainbow skip graph: a fault-tolerant constant-degree distributed data structure,” i Proc. 17th Symp. Discrete Algorithms, pp. t t in P S Di t Al ith 384–393, Jan 2006. レベル0のリングをまとめることによって、ノ ドの持つ次 レベル0のリングをまとめることによって ノードの持つ次 数が定数オーダーになることを示した SkipIndex 論文： C. Zhang, A. Krishnamurthy, and R. Y. Wang, “Skipindex: Skipindex: Towards a scalable peer-to-peer index service for high dimensional data,” TR-703-04, Princeton University, May 2004. 2004 K-D treeを使うことで、多次元の范囲検索を実現 32
関連研究 (3) Znet 論文： Y. Shu, B. C. Ooi, K.-L. Tan, and A. Zhou, “Supporting multi- dimensional range queries in peer-to-peer systems,” P2P’05, pp. 173 180 2005. 173–180, 2005 空間充填曲線であるZ-orderingを使うことで、多次元の 范囲検索を実現 33
Multi-key Skip G h M lti k Ski Graph
Multi-key Skip Graph 仮想的なピアを複数置くことで複数keyの保持に対応 2007/6 情報処理学会研究報告 DPS-131にて発表 仮想ピアの保持する各レベルの ルーティングテーブルのエントリ 同じ membership vector をもつ （数字は仮想ピアのキ ） （数字は仮想ピアのキー） 仮想ピアは同一物理ピア上に存在する 0 1 3 6 Level 2 2 4 Level 1 5 0 1 2 3 4 6 Level 0 0 1 2 3 4 5 6 00 00 01 00 01 10 00 membership vector （＝物理ピアの識別） 35
マルチレンジフォワード方式 物理ピア単位で見たクエリ転送経路 0 0 0 0 0 0 1 0 0 1 0 1 0 0 物理ピア 00 と 01 間で何度もクエリが往復する 上記の問題への対処 クエリを受け取ると、その物理ピア上に存在する全ての仮想 ク を受 ると 物 ピ 存在する全 仮想 ピアを考慮してルーティング クエリの転送は各物理ピア毎に一度のみ クエリの転送は各物理ピア毎に 度のみ 検索コスト（ホップ数）は、物理ピア数をMとして、log M 仮想ピア数に依存しないところがポイント 36
探索パスの比較 仮想 ア単位のル ティング（改良前） 仮想ピア単位のルーティング（改良前） マルチレンジフォワ ド方式 マルチレンジフォワード方式 37
評価結果 （ピア数 100） 38
Multi-key Skip Graphを使った オーバレイの実装 オ バレイの実装
PIAXにおけるオーバレイの関係 LL-Net, DHT, ALM 等は、Multi-key Skip Graph の 機能を使って実装している 経路表は1つで済む 構造化オーバレイのメンテナンスコスト削減につながる 非構造化オーバレイについては別に用意 Discovery Messaging y g g LL-Net DHT ALM ??? Multi-key Skip Graph 40
LL-Net の4分木による実装 2次元領域を段階的に4分割 得られた 分木を 得られた4分木をベースにルーティングテーブルを構成 ル ティングテ ルを構成 各レベルについて、隣接する3つの領域へのリンクを保持 ルーティングの方法は、Pastryとほぼ同じ しかし、ピアが一様に分布しない問題が... B D A B C D イメージを表示できません。メモリ不足のためにイメージを開く こ とができないか、イメージが 破損している可能性があります。コンピュータ を再起動して再度ファイルを開いてください。 それでも 赤い x が表示される場合は、イメージを削除して挿入してください。 A C ??? ??? ??? ??? ??? 41
参考：ベキ乗分布 集中点20, 総ピア数5000 で出力してみた 代表例： 東京 800万 横浜 340万 大阪 260万 ??? 順位をnとして、 人口が次の関数 になっている にな ている y=an-1 42
そこで、Skip Graph+空間充填曲線 利点 内部に形成されるグラフ構造（skip list）が常にバランス するため、探索効率は、log N に安定 多次元を1次元に変換する手法として、空間充填曲 多次元を1次元に変換する手法として 空間充填曲 線（space-filling curves）を利用する cf. cf Znet 43
空間充填曲線 ペアノ曲線ともいう よく知られているのが、ヒルベルト曲線 Zの書き順にしたのが、Z-ordering（Z曲線） 変換は、Z-orderingの方がやりやすいため、范囲検索では こちらがよく使われる ヒルベルト曲線 位相5 Z-order 位相5 44
2次元を1次元に Location-ID (L-ID) 緯度?経度の2次元位置情報を1次元にエンコード 変換には、Z-orderingを使用 変換 は を使 32桁の4進数値 精度は約1cm （地球の全周が40000kmなので） 使用しない 1 3 90度 2 0 -180度 180度 -90度 032 ベース領域 – 地球全体 エンコーディング例 （3桁） 45
范囲検索 設定した矩形を包含する1次元の範囲を求めて、その後 Skip Graphを使って探索 通常は、4つ以上の部分範囲に分かれる 常 範 誤差部分については間引く必要がある D B 対象矩形 対象 矩形 A B C D A L-IDの値 C 46
DHT Skip Graph でID検索を行う 方法は、SkipNetの論文に記載 ここでは ID = membership vector ここでは、ID レベル0から上位レベルへ、目的のIDとプレフィックスの一 致桁が長くなるよう検索 key “13”のノードから membership vector “111” を検索 Key 21 33 Level 2 11 00 13 48 75 99 21 1 75 99 Level 1 0 13 33 48 Level 0 L l 13 21 33 48 75 99 Membership vector 000 100 010 001 110 111 47
ALM (Application Layer Multicast) Skip Graphの、指定されたkeyを持つピアにメッセージを 送る機能を利用 1 ピア 1 key だと複数のmulticast groupに参加できなくなるの ピア, で、multi-keyが前提となる スパニングツリーを構成する必要がない ランデブーポイントを自由に設定できる ランデブ ポイントを自由に設定できる 経路の障害回避は Skip Graph の方でやってくれる G G rendezvous Level 2 G point G G Level 1 G G: group ID Level 0 L l G G G 00 00 10 10 00 01 11 00 48
まとめ
紹介できなかった技術トピック 範囲探索のストリーム化 返り値集約の機構 約 機構 ヒット数が多い時に有効 近接オ ジ ク 近接オブジェクトの発見 発見 オブジェクト間の近接関係を処理する機構の導入 統計処理： ベイジアン 推論処理： 分散型演繹機構 P2Pエージェントの移動透過性と複製透過性 P2Pエージェントの仮想化 P2P ジ ト 仮想化 一群のP2Pエージェントを論理的に単一のP2Pエージェントとして みせかける セキュリティ、プライバシー保護の強化 現在、 ア 現在、ピアとP2Pエージェントに対するPKIベースの認証 ジ ン 対する 認証 機構のみ実装 50
まとめ PIAX Skip Graph Multi-key Skip Graph, Overlays について紹介 紹介 PIAX: Java 5 以上のJVMで動作 http://www.piax.org にてオープンソースとして公開中 公開して8ヶ月（ダウンロード数 700） 公開して8ヶ月（ダウンロ ド数 行き届かない点が多々ありますが、よかったら使ってみ てください 51
ご清聴ありがとうございました

More Related Content

kibayos-PIAX & SkipGraph-071207

  • 1. 2007/12/7 情報処理学会関西支部講演会 技術紹介: P2Pエージェントプラットフォーム PIAX と 構造化オーバレイ Skip Graph 吉田 幹 （株）ビービーアール （株）ビ ビ ア ル, 大阪大学（招聘研究員） 大阪大学
  • 2. Agenda PIAX 設計コンセプト アーキテクチャ API Skip Graph Skip List Skip Graph 関連研究 トピック Multi-key Skip Graph Multi-key Skip Graphを使ったオーバレイの実装 2
  • 3. P2Pエージェントプラットフォーム P2Pエ ジ ントプラ トフォ ム PIAX ※PIAXの 部は、総務省委託研究 ビキタスネットワ ク認証 ※PIAXの一部は、総務省委託研究「ユビキタスネットワーク認証?エージェ ジェ ント技術の研究開発」の一環として開発されたものです
  • 4. 共通プラットフォームのニーズ ユビキタスネットワーク PCに加え、携帯電話、PDA、家電機器、自動車、センサ、 PCに加え 携帯電話 PDA 家電機器 自動車 センサ ロボット、ウェアラブルなど、多種多様のデバイスがネット ワークに接続 3C(Computing, Connectivity, Contents) everywhere 課題 大量のオブジェクトから必要なものを瞬時に発見する 発見したオブジェクトを使って高度なサ ビスを構成する 発見したオブジェクトを使って高度なサービスを構成する ユーザの位置や、情報間の関係に基づくオブジェクトの ユ ザの位置や 情報間の関係に基づくオブジ クトの 発見と連携をスケーラブルに実現するための 共通プラットフォ ムが必要 共通プラットフォームが必要 4
  • 5. ユビキタスサービスの実現イメージ PIAXは共通プラットフォームとして機能 Reputation Shopping Navigation Sharing ss sta t Assistant Recommendation Streaming Various ubiquitous applications Agents g P2P Overlay Network PIAX Flexible Computing by Mobile Agents Scalable Messaging Peer by P2P Overlay Profiles Reputations Sensors Contents Devices Users 5
  • 6. 近傍性、近接性と相互作用 ＜ユビキタスコンピューティングの処理の流れ＞ 1. ユーザ位置を同定 ザ位置を同定 2. 近傍、近接オブジェクトの探索 近傍に位置するオブジェクト ? 物理空間における近傍性 仮想空間上に蓄積された関連性のあるオブジェクト ? 意味空間における近接性 3. 探索されたオブジェクト（複数のサービス主体と能動的オブ ジ クト）の相互連携によりサ ビスを実現 ジェクト）の相互連携によりサービスを実現 「ユビキタスサービスは、ユーザ（群）とその近傍、近接 にあるオブジェクト間における相互作用により実現される」 6
  • 7. ユビキタスP2Pサービス セマンティックWebとP2Pシステムの進化融合形 セマンティックWebサービスから見れば、P2P拡張 見 、 張 P2Pシステムから見れば、第４世代P2Pとして知識高度化 Web Services Semantic Web Semantic Web Services Ubiquitous P2P Service Pure P2P Structured Hybrid P2P Unstructured Overlay 1st generation 2nd generation 3rd generation 7
  • 8. P2Pエージェントプラットフォーム PIAX ユビキタスP2Pサービスの1つの実現形 P2P Interactive Agent eXtentions の略 （エージェントの相互作用を表現） Agents P2Pエージェント P2Pネットワ ク上に分散 P2Pネットワーク上に分散 する相互連携性と自律性 discovery power を持ったオブジェクト サービス主体と能動的オ ビ ブジェクトを含めたオブジェ P2P Overlay Network クトを表現 オーバレイの持つ強力な 資源探索機能を活用することで、“what to find” をス ケーラブルに実現 8
  • 9. Discovery Messaging オーバレイによって強化されたP2Pエージェントの持つ新し いメッセージング機構 “what to find” を実現する クエリ条件が “what” に相当 擬似言語で表現すると、(b)を実現することになる (a) send(destinationAddress, message); (b) send(queryCondition, message); d( C d ) 次のようなクエリ条件なら、指定された地理的矩形に含まれ、 次のようなク リ条件なら 指定された地理的矩形に含まれ メソッド getTemperature を持つエージェントがメッセージン グ対象となる in rectangle(135.0, 35.0, 1.0, 1.0) and has getTemperature method 9
  • 10. PIAXのアーキテクチャ (1) Ubiquitous Applications - Context-aware Bayesian - RDF DB - Poe (Prolog Engine) ??? Agent library ??? JSONP- RPC P2P Agents ecure Support LL-Net Discovery Messaging y g g DHT Multi-Overlay plug- plug ALM Auth, Se RPC ins Overlay Transport Social-Net Physical Network ??? 10
  • 11. PIAXのアーキテクチャ (2) RPC / Overlay Transport Socket通信の隠蔽、NAT越えのサポート 上位レイヤに対し、ピアIDを使った高レベルの通信手段を提供 上位レイヤに対し ピアIDを使った高レベルの通信手段を提供 Multi-Overlay 複数のオーバレイ機能を管理 LL-Net, DHT, ALM, ソーシャルネット等 Discovery Messaging Multi Overlayレイヤと連携し、discovery Multi-Overlayレイヤと連携し、discovery messagingを実現 上位レイヤに対し、オーバレイの実装を隠蔽 P2P Agents P2Pエージェントの稼働環境（API） P2Pエ ジ ントの稼働環境（API） JSONP JSONP- RPC P2P A Agents Auth, Secure Support を提供 Discovery Messaging JSONP-RPC Multi-Overlay e 外部システムとの通信手段を提供 Auth, Secure Support RPC Overlay Transport ピアおよび ピアおよびエージェントの認証等 ジェントの認証等 Physical Network 11
  • 12. マルチオーバレイ 共通的なプラットフォームとして機能するためには、アプリ ケーションからの様々な探索要求に応える必要がある 複数のオーバレイネットワークを管理 オーバレイネットワークのプラグイン化 クエリパターン オーバレイネットワーク 完全一致探索 DHT, (Skip Graph) 部分一致探索 DHT+α 範囲探索（1またはN次元） Skip Graph, LL-Net 連想探索（SNSなど） Unstructured 意味探索 DHT+α ※複合的なクエリパターンを処理する機構（インターリーブ）については今後の課題 12
  • 13. マルチオーバレイの機構 目的別にオーバレイを追加拡張するための機構 オーバレイを plug-in service として、ローディングと選択を 行う Discovery Messaging request with query condition -> query condition overlay table qc1 ov A selector qc2 ov B Multi-Overlay qc3 ov C registration Overlay A Overlay B Overlay C New Overlay use use plug-in: Multi-key call dynamic loading Skip Graph call RPC 13
  • 14. 代表的なオーバレイ (1) LL-Net (Location-based Logical P2P Network) 地理的探索のためのオーバレイ 特に、近傍オブジェクトの探索に効力を発揮 ピアの位置（緯度、経度）に基づいてオーバレイネットワークを構築? 維持 対象世界（地球全体）を矩形のエリアに分割し、階層的に管理 モバイル端末の接続?切断?移動に応じて、オーバレイネットワーク を動的に構成 エリア内リンク エリア間リンク 14
  • 15. 代表的なオーバレイ (2) DHT (key, (key value ) のペアをkeyのハッシュ値に従い分散管理 する ALM (Application Layer Multicast) アプリケーションレイヤにおける anycast および multicast を実現する ソーシャルネット SNSのバックボーンとなるオーバレイネットワーク ユビキタスでは、口コミ情報収集に活用 ? 人のセンサ化 人の関係を単方向グラフで表したリンク構造を元に形成 15
  • 16. P2Pエージェントの状態遷移 一般的なモバイルエージェントシステムと同じ 生成（create）, 消滅（destroy）, 複製（duplicate）, 永続化 （sleep）, 永続状態からの復帰（wakeup）, 他のピアへの移 続 態 ピ 動（travel）等のメソッドがある 移動先の指定は、ピアIDで行う 移動先の指定は ピアIDで行う （IPアドレスは隠蔽される） moving sleeping sleep travel wakeup active duplicate create destroy 16
  • 17. P2Pエージェントのモビリティ PIAXでは、エージェントに対し弱モビリティ（スタック を含むcontextの移動はしない）をサポート P2Pシステムにおける利点 帯域の効率的利用 通信頻度が高い相手の近傍にエージェントを移動させることで、 ネットワーク全体の帯域消費を抑える 負荷の平準化 負荷の高いエージェントを複製し、リクエスト元の近傍に移動さ せることで、全体負荷を平準化させる サービスの持続性 ユーザが利用するアクセスピアの変化に対し、サービスを追従さ せる アプリケーションの耐性 P2Pネットワークの構成変化（churn）に対するアプリケーション側 の耐性を高める 耐性を高める P2P特有 17
  • 18. 非同期、一方向、同報型メソッド呼び出し エージェント間の通信は、メッセージ送信ではなく、 RPC 操作透過性（ローカルとリモートをできるだけ区別しない） RPCの制約に対処するため、同期型に加え、非同 期、一方向、同報型のメソッド呼び出しを用意 呼び出し例 String name = remoteCall(peerId, agentId, “getName”); FutureReturn future = remoteCallAsync(peerId, agentId, “heavyCalc”, 123456); remoteCallOneway(peerId, agentId, notify ); remoteCallOneway(peerId agentId “notify”); ReturnSet rset = remoteCallMulti(peerId, filter, “getScore”); g ); 18
  • 19. 発見型メソッド呼び出し Discovery messaging の実現形態 P2Pエージェントの探索とリクエストを同時に行える メソッド定義 ReturnSet<Object> R S Obj discoveryCall(QueryCondition qCond, String method, Object... Object args) 呼び出し例 rset = h t home.discoveryCall(new Rectangle(135.0, di C ll( R t l (135 0 35.0, 1.0, 1.0), “getScore”, myProfile); 実行時には、クエリ条件がマルチオーバレイ機構に 実行時には クエリ条件がマルチオ バレイ機構に 渡され、適切なオーバレイが選択される 19
  • 21. 構造化オーバレイ Skip G h 構造化オ バレイ Ski Graph
  • 22. Skip Graph Yale大学の J. Aspnes教授の研究による構造化オーバレイ 論文： J. Aspnes and G. Shah. Skip Graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Jan. 2003. 基本とするデータ構造は skip list（W. Pugh,1990）というバ ランス木 ノードは、IDとは別にkeyを持つ 指定された範囲のkeyを持つノードを効率よく探索できる 認知度は低いけど、実はパワフル 範囲探索 任意のkeyを持つオブジェクトをサーチ 任意 を持 オブジ ク を ALM PIAXにおいて、中核的な役割を果たしている PIAXにおいて 中核的な役割を果たしている 22
  • 23. Skip List ノードはkey順に並ぶ レベル0のリストには全てのノードが含まれる レベルi-1に現れるノードはある確率pでレベルiに現れる（こ こでは簡単のため、p=1/2とします） 通常のバランス木と違い、ノードの追加?削除の際にバラン 通常のバランス木と違い ノ ドの追加 削除の際にバラン ス化の処理が不要 HEAD TAIL Level 2 L l 33 Level 1 L l 13 33 48 Level 0 L l 13 21 33 48 75 99 23
  • 24. Skip List を使った検索 上位レベルから下位レベルに降りる形で処理が進む 平均検索時間は、ノード数をNとして、O(log N) 平均検索時間は、 ド数を して、 ( g ) 全順序関係が定義できるデータならすべて key として使うこ とができる（数値、文字列など）。片寄りがあってもよい HEAD から Key “75” を検索 75 HEAD TAIL Level 2 L l 33 Level 1 L l 13 33 48 Level 0 L l 13 21 33 48 75 99 24
  • 25. Coffee Break: Skip List Java 6 から skip list が使えるようになりました java.util.concurrent.ConcurrentSkipListMap うれしいことにスレッドセーフ さらに、SortedMap より強力な NavigableMap が登場し、今 までできなかった次の処理ができるようになりました ま きなか た次 処理が きるよう なりま た 指定したkey以上の大きさを持つ最小のkeyを取得 等 TreeMap ConcurrentSkipListMap は次のように使い分け T M とC tSki Li tM ましょう TreeMap ConcurrentSkipListMap get,put,removeのコスト log N log N バランス処理 要 不要 スレッドセーフ NG OK メモリ消費のオーバヘッド 3*N+α 6*N+α 25
  • 26. Skip Graph の構成 レベルi では membership vectorのプレフィックスの i桁が 一致するノード同士リンクをはる membership vector “レベルi-1に現れるノードは確率1/2でレベルiに現れる”性質を実現 するための2進整数（ランダムに分布） DHTでいうノードIDに相当 DHTでいうノ ドIDに相当 Key 21 33 Level 2 13 48 75 99 21 75 99 Level 1 13 33 48 Skip List Level 0 L l 13 21 33 48 75 99 Membership vector 000 100 010 001 110 111 26
  • 27. Skip Graphでのkey検索 個々のノードから見ると、Skip List と同じ構造（アミ掛け部 分） Skip List と同じ検索アルゴリズムを実行 范囲検索も同様にできる key “33”のノードから key “75” を検索 Key 21 33 Level 2 13 48 75 99 21 75 99 Level 1 13 33 48 Skip List Level 0 L l 13 21 33 48 75 99 Membership vector 000 100 010 001 110 111 27
  • 28. Skip Graphでのノード追加 (1) introducer（ここでは99）から挿入位置を検索 ? key “48” を見つける レベル0のリンクに新規ノードを挿入 21 33 Level 2 introducer 13 48 75 99 21 75 99 Level 1 13 33 48 Level 0 13 21 33 48 75 99 40 011 000 100 010 001 110 111 28
  • 29. Skip Graphでのノード追加 (2) レベル1から上位レベルへ順番に、プレフィックスの一致す るノードから成るリンクに新規ノードを挿入 21 33 40 Level 2 13 48 75 99 21 75 99 Level 1 13 33 40 48 Level 0 13 21 33 40 48 75 99 000 100 010 011 001 110 111 29
  • 30. DHTs vs. Skip Graph DHTs Skip Graph ID検索 通常 O(l N) O(log O(log O(l N) key検索 N/A O(log N) 范囲検索 NG O(log N) insert/delete O(log2 N) (*1) O(log N) 経路表 高さ 経路表の高さ ID長 長 log N g 経路表の対称性 ? Kademliaは有 有 insert/delete 時 不要 必要 の排他制御(*2) *1 Chord の場合 *2 排他制御の有無の理由については考察中 30
  • 31. 関連研究 (1) SkipNet 論文： N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman, “SkipNet: A scalable overlay network with practical locality properties,” USITS ’03, 2003. properties, 03, DHTが対象とする情報の格納範囲をネットワーク全体で はなく、近接のサブネットワークに制限 DHTが不得意とするローカリティ制御を実現 Skip B-Tree 論文： I. Abraham, J. Aspnes, and J. Yuan, “Skip B-trees,” in Principles of Distributed Systems; 9th International Conference, OPODIS 2005, Dec. 2005. B-Tree を導入し、keyをブロック化することで効率化 31
  • 32. 関連研究 (2) Rainbow Skip Graph 論文： M. T. Goodrich, M. J. Nelson, and J. Z. Sun, “The rainbow skip graph: a fault-tolerant constant-degree distributed data structure,” i Proc. 17th Symp. Discrete Algorithms, pp. t t in P S Di t Al ith 384–393, Jan 2006. レベル0のリングをまとめることによって、ノ ドの持つ次 レベル0のリングをまとめることによって ノードの持つ次 数が定数オーダーになることを示した SkipIndex 論文： C. Zhang, A. Krishnamurthy, and R. Y. Wang, “Skipindex: Skipindex: Towards a scalable peer-to-peer index service for high dimensional data,” TR-703-04, Princeton University, May 2004. 2004 K-D treeを使うことで、多次元の范囲検索を実現 32
  • 33. 関連研究 (3) Znet 論文： Y. Shu, B. C. Ooi, K.-L. Tan, and A. Zhou, “Supporting multi- dimensional range queries in peer-to-peer systems,” P2P’05, pp. 173 180 2005. 173–180, 2005 空間充填曲線であるZ-orderingを使うことで、多次元の 范囲検索を実現 33
  • 34. Multi-key Skip G h M lti k Ski Graph
  • 35. Multi-key Skip Graph 仮想的なピアを複数置くことで複数keyの保持に対応 2007/6 情報処理学会研究報告 DPS-131にて発表 仮想ピアの保持する各レベルの ルーティングテーブルのエントリ 同じ membership vector をもつ （数字は仮想ピアのキ ） （数字は仮想ピアのキー） 仮想ピアは同一物理ピア上に存在する 0 1 3 6 Level 2 2 4 Level 1 5 0 1 2 3 4 6 Level 0 0 1 2 3 4 5 6 00 00 01 00 01 10 00 membership vector （＝物理ピアの識別） 35
  • 36. マルチレンジフォワード方式 物理ピア単位で見たクエリ転送経路 0 0 0 0 0 0 1 0 0 1 0 1 0 0 物理ピア 00 と 01 間で何度もクエリが往復する 上記の問題への対処 クエリを受け取ると、その物理ピア上に存在する全ての仮想 ク を受 ると 物 ピ 存在する全 仮想 ピアを考慮してルーティング クエリの転送は各物理ピア毎に一度のみ クエリの転送は各物理ピア毎に 度のみ 検索コスト（ホップ数）は、物理ピア数をMとして、log M 仮想ピア数に依存しないところがポイント 36
  • 39. Multi-key Skip Graphを使った オーバレイの実装 オ バレイの実装
  • 40. PIAXにおけるオーバレイの関係 LL-Net, DHT, ALM 等は、Multi-key Skip Graph の 機能を使って実装している 経路表は1つで済む 構造化オーバレイのメンテナンスコスト削減につながる 非構造化オーバレイについては別に用意 Discovery Messaging y g g LL-Net DHT ALM ??? Multi-key Skip Graph 40
  • 41. LL-Net の4分木による実装 2次元領域を段階的に4分割 得られた 分木を 得られた4分木をベースにルーティングテーブルを構成 ル ティングテ ルを構成 各レベルについて、隣接する3つの領域へのリンクを保持 ルーティングの方法は、Pastryとほぼ同じ しかし、ピアが一様に分布しない問題が... B D A B C D イメージを表示できません。メモリ不足のためにイメージを開く こ とができないか、イメージが 破損している可能性があります。コンピュータ を再起動して再度ファイルを開いてください。 それでも 赤い x が表示される場合は、イメージを削除して挿入してください。 A C ??? ??? ??? ??? ??? 41
  • 42. 参考：ベキ乗分布 集中点20, 総ピア数5000 で出力してみた 代表例： 東京 800万 横浜 340万 大阪 260万 ??? 順位をnとして、 人口が次の関数 になっている にな ている y=an-1 42
  • 43. そこで、Skip Graph+空間充填曲線 利点 内部に形成されるグラフ構造（skip list）が常にバランス するため、探索効率は、log N に安定 多次元を1次元に変換する手法として、空間充填曲 多次元を1次元に変換する手法として 空間充填曲 線（space-filling curves）を利用する cf. cf Znet 43
  • 45. 2次元を1次元に Location-ID (L-ID) 緯度?経度の2次元位置情報を1次元にエンコード 変換には、Z-orderingを使用 変換 は を使 32桁の4進数値 精度は約1cm （地球の全周が40000kmなので） 使用しない 1 3 90度 2 0 -180度 180度 -90度 032 ベース領域 – 地球全体 エンコーディング例 （3桁） 45
  • 46. 范囲検索 設定した矩形を包含する1次元の範囲を求めて、その後 Skip Graphを使って探索 通常は、4つ以上の部分範囲に分かれる 常 範 誤差部分については間引く必要がある D B 対象矩形 対象 矩形 A B C D A L-IDの値 C 46
  • 47. DHT Skip Graph でID検索を行う 方法は、SkipNetの論文に記載 ここでは ID = membership vector ここでは、ID レベル0から上位レベルへ、目的のIDとプレフィックスの一 致桁が長くなるよう検索 key “13”のノードから membership vector “111” を検索 Key 21 33 Level 2 11 00 13 48 75 99 21 1 75 99 Level 1 0 13 33 48 Level 0 L l 13 21 33 48 75 99 Membership vector 000 100 010 001 110 111 47
  • 48. ALM (Application Layer Multicast) Skip Graphの、指定されたkeyを持つピアにメッセージを 送る機能を利用 1 ピア 1 key だと複数のmulticast groupに参加できなくなるの ピア, で、multi-keyが前提となる スパニングツリーを構成する必要がない ランデブーポイントを自由に設定できる ランデブ ポイントを自由に設定できる 経路の障害回避は Skip Graph の方でやってくれる G G rendezvous Level 2 G point G G Level 1 G G: group ID Level 0 L l G G G 00 00 10 10 00 01 11 00 48
  • 50. 紹介できなかった技術トピック 範囲探索のストリーム化 返り値集約の機構 約 機構 ヒット数が多い時に有効 近接オ ジ ク 近接オブジェクトの発見 発見 オブジェクト間の近接関係を処理する機構の導入 統計処理： ベイジアン 推論処理： 分散型演繹機構 P2Pエージェントの移動透過性と複製透過性 P2Pエージェントの仮想化 P2P ジ ト 仮想化 一群のP2Pエージェントを論理的に単一のP2Pエージェントとして みせかける セキュリティ、プライバシー保護の強化 現在、 ア 現在、ピアとP2Pエージェントに対するPKIベースの認証 ジ ン 対する 認証 機構のみ実装 50
  • 51. まとめ PIAX Skip Graph Multi-key Skip Graph, Overlays について紹介 紹介 PIAX: Java 5 以上のJVMで動作 http://www.piax.org にてオープンソースとして公開中 公開して8ヶ月（ダウンロード数 700） 公開して8ヶ月（ダウンロ ド数 行き届かない点が多々ありますが、よかったら使ってみ てください 51