Peer-to-Peerシステムにおける動的な木構造の生成による検索の高速化

Presentation on theme: "Peer-to-Peerシステムにおける動的な木構造の生成による検索の高速化"— Presentation transcript:

1 Peer-to-Peerシステムにおける動的な木構造の生成による検索の高速化

2 Peer-To-Peer (P2P) システム
分散型の検索 特定のホストにインデックス（目的とする情報がどのホスト上にあるか）が集中していない 応用例：ファイル交換 (Napster, Gnutella, etc) Cf. 集中型の検索 Web の検索エンジン (google 等) 単一ホストが検索を集中処理

3 P2Pネットワークでの検索 検索時にブロードキャスト 無駄な query が多く効率が悪い 有効なQuery 無駄なQuery
Query Hit 発見

4 P2P の利点と問題点 利点 問題点 検索用の巨大サーバーが不要 検索サーバのホスト名を知らなくてもよい
無駄な query が多く、ネットワーク帯域を浪費する 効率のよいキャッシュが困難

5 管理された検索ネットワーク 管理することで無駄な query を減らせる 例：階層型分散検索 管理する人間の組織が必要
DNS (Domain Name System) com jp ac ebay sun titech is

6 p2p-cacheの提案 階層構造の検索ネットワークを動的に作成 検索経路 新しいノード
ノードが追加されるたびに検索ネットワークを自動で作り直す 人手はかからない アルゴリズムは実用上のトレードオフを考え単純なものにした バランスは無視 ランダムに加わる ディスク容量の大きい ノードが根に近くなる ようにする 検索経路 新しいノード

7 P2p-cache の位置付け 集中型検索 分散型検索 従来の P2P 型検索 管理なし p2p-cache 型検索 自動管理
Web 検索エンジン 分散型検索 従来の P2P 型検索 管理なし p2p-cache 型検索 自動管理 利点　動的に自動管理 階層型検索 管理あり

8 キャッシュの実装 さらに、検索時にその経路上のすべてのノードでキャッシュをとる Indexのあるノード Indexのキャッシュのあるノード
Query Query Hit Query Query Hit Query Hit Indexのあるノード

9 実験 実験環境 実験内容 Pentium 3 733MHz, Memory 512MB
Linux version のRedHat Linux OS で１６ノードのクラスタ 実験内容 各ノードがランダムに検索を行い、その検索時間を従来型P2Pとp2p-cacheで比較

10 測定結果１: 検索の高速化 従来型とp2p-cacheの比較

11 測定結果２: メッセージ数の削減 約40%のメッセージ削減 P2p-cacheと従来型のメッセージ数　　　　　　　　の比較

12 まとめ p2p-cache の提案 Future Work P2Pネットワークの欠点を改良 動的に木を作成 P2Pと階層型の両方の利点を実現
キャッシュの実装 C++で実装、約4000行 p2p-cacheでの検索速度向上、メッセージ数削減の確認 Future Work LRUなどのキャッシュのアルゴリズムの導入