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