自己組織化型P2P検索システム : TellaGate 小島 一浩 独立行政法人 産業技術総合研究所 背景 Community Netの提案 TellaGateの概要と詳細 今後の課題 デモ

Background 既存のP2Pに対する不満点： 1. P2Pの検索機能を強化するには？ 2. ネットワーク負荷を減らしたい． 3. 回線速度を重視しすぎなのでは？ 4. 匿名性を重視しすぎでは？ 　5. そもそもファイル交換以外の使い方はないのか？ 新たな方向性の提案： 1. 回線速度ではなく，コンテンツ，人主体にすべきでは？ 2. 人のつながり，コミュニティー 3. 魅力あるコンテンツ生成能力のある人は，中心へ．

Community Net TellaGate Net TellaGate Net TellaGate Net TellaScope 発見！ TellaGate Net TellaGate Net TellaGate Net TellaScope エントリーへアクセス 情報共有 ・ 情報検索 ・ 情報配信 コミュニティーに参加＝ コミュニティーの自己組織化 問題発生！

Application Image コミュニティー構造が期待できる対象 分散論文検索 分散掲示板

Hint そもそも現実世界では？ AはBと友人である BはCと友人である AはBの友人にCがいることを知っている BはCの友人にD,E,Fがいることを知っている AはBにCを紹介してもらう. AはCと友人になる 紹介の連鎖　= 「人つて」による検索 連鎖を繰り返し，その関係を維持すると コミュニティーが形成される A B C Cの友人

Proposed Method: TellaGate Protocol 1.PeerDigest => Preference 2.Pong Proxy => Exchange PeerDigest 3.QRP with Firework => Query Routing Protocol 4.Backward Learning => Update Query Routing Table 5.Community Self-Organization Algorithm

Performance a) Success rate b) Network load

TellaGateの概要 2. Query/QueryHit 転送による学習 3. Networkの再構成 1.2. が3.に影響を与える Downloadによる嗜好状態の変化 2. Query/QueryHit 転送による学習 3. Networkの再構成 1.2. が3.に影響を与える QueryHit D C QueryErr E Bは，自身が持つC,Eの内部モデルを変化 Bは，C,Eの内部モデルをAに伝える B Query A

TellaGateの構成 TellaGate Octopus module - P2P Routing TellaPeer 接続要求 TellaGate Octopus module - P2P Routing 登録・経路問合せ 生成・管理 TCP:6699 TellaPeer (QThread) SearchEngine module - Search Engine 検索 HTTP module - HTTP Server - HTTP Client PeerDigest作成 - Indexer ChaSen(形態素解析器) TCP:8080

PeerDigest … text ward hash function M-bits array Bloom filter 1 1 … Index Table Digest file guid size path+name 00 : … : ab 1c : … : e3 45000 自律分散.pdf 00 : … : ff c4 : … : 23 32150 TellaGate.ps dd : … : c1 ae : … : 21 1600 Index.html Definition of similarity

Octopus : P2P Routing Module B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port A B C D E 2nd Neighbors digest peer guid ip port Message Cache Table message guid src. query words des. 0 …

Ex. Ping-Pong and Pong Proxy : step 1 B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port ExPing A B C D E 2nd Neighbors digest peer guid ip port Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D

Ex. Ping-Pong and Pong Proxy : step 2 B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 da : … : 21 d.d.d.d ExPong(D) A B C D E ExPong(C) 2nd Neighbors digest peer guid ip port Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D

Ex. Ping-Pong and Pong Proxy : step 3 B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 da : … : 21 d.d.d.d ExPong(E) A B C D E 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D

Query Routing (QRPwF) : step 0 B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 da : … : 21 d.d.d.d A B C D E Query network = {0, 101, 1858, 25007} 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D

Query Routing (QRPwF) : step 1 B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 da : … : 21 d.d.d.d A B C D E Query network = {0, 101, 1858, 25007} 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D 61 : … : f9 A network

Query Routing (QRPwF) : step 2 B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 da : … : 21 d.d.d.d A B C D E QueryErr network = {0, 101, 1858, 25007} 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D 61 : … : f9 A network

Query Routing (QRPwF) : step 3 B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 da : … : 21 d.d.d.d A B C D E network = {0, 101, 1858, 25007} Query 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D 61 : … : f9 A network

Query Routing (QRPwF) : step 4 B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 00 : … : 01 da : … : 21 d.d.d.d A B C D E network = {0, 101, 1858, 25007} QueryHit 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D 61 : … : f9 A network

Query Routing (QRPwF) : step 5 B’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 3b : … : 00 00 : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 00 00 : … : 01 da : … : 21 d.d.d.d A B C D E network = {0, 101, 1858, 25007} QueryHit 2nd Neighbors digest peer guid ip port 01 : … : 35 68 : … : fa e.e.e.e 6699 Message Cache Table message guid src. query words des. 0 … 01 : ... : ab B C 2c : ... : 61 D 61 : … : f9 A network

Community Self-Organization Algorithm (CSOA) A’s Octopus : 1st Neighbors org. digest adap. digest peer guid ip port 64 : … : 00 00 : … : 01 c5 : … : 8e b.b.b.b 6699 A B C D E 2nd Neighbors digest peer guid ip port 3b : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 01 da : … : 21 d.d.d.d Message Cache Table message guid src. query words des. 0 … 61 : … : f9 A network B

CSOA : step 1 C B D E A A’s Octopus : 1st Neighbors 2nd Neighbors org. digest adap. digest peer guid ip port 64 : … : 00 00 : … : 01 c5 : … : 8e b.b.b.b 6699 A B C D E 2nd Neighbors digest peer guid ip port 3b : … : 00 c5 : … : 8e c.c.c.c 6699 ac : … : 01 da : … : 21 d.d.d.d Handshake Message Cache Table message guid src. query words des. 0 … 61 : … : f9 A network B

CSOA : step 2 C B D E A A’s Octopus : 1st Neighbors 2nd Neighbors org. digest adap. digest peer guid ip port 64 : … : 00 00 : … : 01 c5 : … : 8e b.b.b.b 6699 ac : … : 00 da : … : 21 d.d.d.d A B C D E 2nd Neighbors digest peer guid ip port 3b : … : 00 c5 : … : 8e c.c.c.c 6699 ExPing-ExPong Message Cache Table message guid src. query words des. 0 … 61 : … : f9 A network B

Small World ? Networkの特徴： 1. Diameter 2. Clustering係数(WS-model) Handshake

Conclusions and Future Works □htmlへの対応 -> Apache + Namazu + Squid + Browser? □最近は，海外でもSocial Network(出会い系)がWebサービス として流行っている -> Friendstar, Googleの新サービス Friend Rank 　　P2Pで，主観的Rankを計算できないか？ □数理解析 ->簡単なモデルを作成 □ユーザは使えれば，P2Pでなくてもいい．．． ->ユーザにアピールできるのは？