Peer-to-Peerシステムにおける動的な木構造の生成による検索の高速化 柿原聡@東工大情報科
Peer-To-Peer (P2P) システム 分散型の検索 特定のホストにインデックス（目的とする情報がどのホスト上にあるか）が集中していない 応用例：ファイル交換 (Napster, Gnutella, etc) Cf. 集中型の検索 Web の検索エンジン (google 等) 単一ホストが検索を集中処理
P2Pネットワークでの検索 検索時にブロードキャスト 無駄な query が多く効率が悪い 有効なQuery 無駄なQuery Query Hit 発見
P2P の利点と問題点 利点 問題点 検索用の巨大サーバーが不要 検索サーバのホスト名を知らなくてもよい 無駄な query が多く、ネットワーク帯域を浪費する 効率のよいキャッシュが困難
管理された検索ネットワーク 管理することで無駄な query を減らせる 例：階層型分散検索 管理する人間の組織が必要 DNS (Domain Name System) com jp ac ebay sun titech is
p2p-cacheの提案 階層構造の検索ネットワークを動的に作成 検索経路 新しいノード ノードが追加されるたびに検索ネットワークを自動で作り直す 人手はかからない アルゴリズムは実用上のトレードオフを考え単純なものにした バランスは無視 ランダムに加わる ディスク容量の大きい ノードが根に近くなる ようにする 検索経路 新しいノード
P2p-cache の位置付け 集中型検索 分散型検索 従来の P2P 型検索 管理なし p2p-cache 型検索 自動管理 Web 検索エンジン 分散型検索 従来の P2P 型検索 管理なし p2p-cache 型検索 自動管理 利点 動的に自動管理 階層型検索 管理あり
キャッシュの実装 さらに、検索時にその経路上のすべてのノードでキャッシュをとる Indexのあるノード Indexのキャッシュのあるノード Query Query Hit Query Query Hit Query Hit Indexのあるノード
実験 実験環境 実験内容 Pentium 3 733MHz, Memory 512MB Linux version 2.4.2-2のRedHat Linux OS で１６ノードのクラスタ 実験内容 各ノードがランダムに検索を行い、その検索時間を従来型P2Pとp2p-cacheで比較
測定結果１: 検索の高速化 従来型とp2p-cacheの比較
測定結果２: メッセージ数の削減 約40%のメッセージ削減 P2p-cacheと従来型のメッセージ数 の比較
まとめ p2p-cache の提案 Future Work P2Pネットワークの欠点を改良 動的に木を作成 P2Pと階層型の両方の利点を実現 キャッシュの実装 C++で実装、約4000行 p2p-cacheでの検索速度向上、メッセージ数削減の確認 Future Work LRUなどのキャッシュのアルゴリズムの導入