Comments
Description
Transcript
P2P方式における検索効率の改善手法の評価
5W-5 情報処理学会第65回全国大会 P2P 方式における検索効率の改善手法の評価 難波 貞暁 山名 早人 早稲田大学理工学部情報学科 1 はじめに して顕著である。これは、クライアント/サーバ方式のネット ワークシステムにおいてサーバが処理している部分を複数の 近年、Peer-to-Peer(P2P) ネットワークに対する関心が高 コンピュータに分散して実現しているためである。 まっている。P2P ネットワークは従来の Client/Server 方式 によるネットワークトラフィックの一極集中を回避する手段 として注目されており、Napster に代表される Hybrid 型と 3 問題点解決手法の評価 Gnutella[1] に代表される Pure 型が存在する。 前節でとりあげた Pure 型 P2P ネットワークシステムが持 Hybrid 型 P2P ネットワークはネットワーク上にサーバが 存在し、データのインデックスやユーザの管理をサーバで行 う。データベースの検索はサーバが自身のデータベースを検 つ２つの問題点のうち、検索効率の悪さを解決するためのアプ ローチとして 2 通りの方法を解決手法として選択し評価する。 索することで行い、データの通信に P2P 方式を用いる。 1. 検索範囲を広げる 2. ネットワーク上のファイル数を増やす Pure 型 P2P ネットワークはネットワーク上にサーバが存在 せず、隣接ノードとパケットの通信を行うことでネットワー 本節ではこの 2 通りのアプローチの評価を行った。評価に クを維持し、データベースの検索もパケットの通信によって 際し、隣接ノード数は 4、ネットワークは木構造をとる、ネッ 行われる。 Pure 型 P2P ネットワークはネットワーク上にサーバが存 在しないため、管理コストが低く、耐障害性が高い。しかし 一方で、トラフィック量が多い、検索効率が悪いという問題 点を持つ。本稿では、この問題点を解決するための手法につ トワーク上の任意のノード間の通信速度は等しいものとして 評価を行った。 3.1 いての評価を行った。 検索範囲を広げる手法 Pure 型 P2P ネットワークシステムの検索パケット (Query) には TTL が設けられ、検索はその範囲内のノードに対して行 2 われる。したがって、検索範囲を広げる手法として TTL の値 Pure 型 P2P ネットワークの問題点 を増やすことが考えられる。 Pure 型 P2P ネットワークの問題点として、以下の点があ げられる。 TTL の値を変化させると、隣接ノード数 4 の元で Query が 到達可能なノード数は図 1 のようになる。Gnutella などでは • 検索効率が悪い デフォルトで 7 に設定されており、Query が到達可能なノー • トラフィック量が多い ド数は 4372 である。 Pure 型 P2P ネットワークシステムでは検索効率がクライア ント/サーバ方式のネットワークシステムと比較して悪い。ク ライアント/サーバ方式のネットワークシステムにおいては、 サーバがデータベースを作成しており、クライアントがサー バに問い合わせる形で検索が行われる。一方、Pure 型 P2P ネットワークシステムではデータベースのないネットワーク に対してパケットを送信して返信を待つという形で実現して いるためである。 Pure 型 P2P ネットワークシステムではトラフィック量の多 さもクライアント/サーバ方式のネットワークシステムと比較 Evaluation of the Improvement Technique of the Reference Efficiency in P2P System Sadaaki Nanba Hayato Yamana School of Department of Information and Computer Science,Science and Engineering,Waseda University 図 1 : TTL と Query が到達するノード数の関係 同じネットワーク上で TTL の値を変化させたときの 1 ノー 3−503 ドあたりのトラフィック量の変化を示したものが図 2 である。 全ノードがファイルのダウンロードを終了したとき、ネッ ここで、計算に用いた値は TTL=7 で実測を行った値に基づ トワーク上のレプリカの数は Gnutella が 2916、Freenet が いており、表１のようになる。Ping、Pong パケットについて 4372 である。したがって、後に同じファイルを検索した場合、 は TTL の値によらないので、実測したトラフィック量である Freenet のほうがファイルを発見しやすいといえる。 Ping、Pong の合計で 0.31Kbyte/s をそのまま用いている。 表 1 : 計算に用いた値 パケットの割合 パケットの平均サイズ (%) (byte/s) Query 98.89 75.5 Query Hit 1.11 779.2 TTL の値を 1 増やすことで検索可能なノード数は 3 倍にな る。しかし同時に 1 ノードあたりのトラフィック量も 3 倍と なるため、ネットワークへの負荷が増大する。Gnutella のデ フォルトである TTL=7 では検索可能なノード数が 4372 に 対しトラフィック量が 9.98Kbyte/s であるが、TTL=10 とす 図 3 : ダウンロード時間とレプリカ数の関係 ると検索可能なノード数が 118096 に対しトラフィック量が 261.54Kbyte/s となり、ネットワークへの負荷を考慮すると これは現実的ではない。 4 考察 本稿では、Pure 型 P2P ネットワークシステムの問題点の 1 つである検索効率の悪さに着目し、それを解決するための手 法 2 つについての評価を行った。 検索範囲を広げる手法では、TTL の値を増やすことで検索 に対するヒット数を増やすという手法を用いた。しかし、こ れは現在の効率の悪い手法の適用範囲を広げただけのもので あり、よい手法とはいえない。また、TTL の値を 1 増やすご とにトラフィック量が約 3 倍になることから、ネットワーク の負荷という視点からもよい手法とはいえない。 ネットワーク上のファイル数を増やす手法では、Freenet に 代表されるネットワーク上の経路に位置するノードにレプリ 図 2 : TTL とトラフィック量の関係 カを作成する手法を用いた。これは、検索効率を向上させる うえで有効な手法であるといえる。 3.2 しかし、レプリカを作成する手法では自身の隣接ノードが ネットワーク上のファイル数を増やす手法 そのファイルを持たない限りダウンロードを開始できない。 ネットワーク上にそのファイルのレプリカを作成すること ネットワークが大規模になると流通するファイルの数が増加 で、検索効率をあげることが可能である。Gnutella では、ファ し、各ノードに対するハードディスクの要求量も多くなって イルのダウンロードの段階では当該ノード同時が直接通信を しまう。間に回線の遅いノードが入った場合にダウンロード 行うため、ネットワーク上のそのファイルの増加は緩やかで にかかる時間が長くなってしまう、などといった問題点があ ある。一方、ネットワーク上のファイル数を増やす手法の代 る。これらをどう解決していくかが今後の課題である。 表例である Freenet[2] ではダウンロードにも同じネットワー クを使用し、ファイルを要求したノードとファイルを所持す るノードの途中に位置するノードにもダウンロードを行わせ る。その内容をキャッシュしレプリカとすることで、ネット ワーク上のそのファイルを効果的に増加させることができる。 あるノードが所持するファイルに対して、ホップ数 7 の距 参考文献 [1] Gnutella : http://gnutella.wego.com [2] Ian 離上にある全てのノードがファイルを要求した場合、1 つの ノードがダウンロードを完了するまでの時間を単位時間とし たときの単位時間とレプリカ数の関係は図 3 のようになる。 ともに同時ダウンロード数を 3 としている。 3−504 Clarke,Oskar Sandberg,Brandon Wiley and Theodore W.Hong,”Freenet:A Distributed Anonymous Information Storage and Retrieval System”,ICSI workshopon Design Issues in Anonymity and Unobsevability,Berkeley,CA,2000(2000).