非構造型P2Pネットワークにおけるホップ制限付き木構造に基づくランダムウオーク検索

摘要

非構造型P2Pにホップ制限付き木構造を導入することによりランダムウオークベース検索を効率的に実施する手法を提案する．各ピアはそれぞれ定められたホップ数以内（カバーエリア内）のピアについて，それらが保持するファイルリスト及びそれらピアへの経路表を保持する．ファイル検索の際は，ファイルリスト内に所望のファイルが見つかればファイルを所持するピアへファイル要求メッセージをユニキャストする．ファイルリスト内に所望のファイルがなければ，ファイル検索メッセージを（1つもしくは複数）生成し，カバーエリアの境界に存在するいずれかのピアをランダムに選んでユニキャストする．検索メッセージを受け取ったピアはファイルリスト内の探索及びメッセージのランダム転送を繰り返す．本稿では，提案手法が単純なランダムウオークベース検索に比べて大幅にファイルヒット率を向上させ，またファイル検索時間を短縮させることを示す．%We propose an improvement of Random-Walk-based file search in unstructured P2P networks. In this proposal, each peer keeps the partial information of the n-hop-limited shortest path trees and list of neighbors'file whose roots are located within its n-hop neighbors, which we call the cover area. In file searching, if the requested file is in its file-list, a peer sends the request message to the peer that possess request file; if the requested file is not in its file-list, it sends the query (one or more) to a peer who located at edge of its cover area. Peer(s) that received the query will search the request file in its file-list and sends. Numerical examples show that our proposal can reduce the time in searching and more efficiency then normal Random Walk.