Comments
Transcript
Pure 型 P2P ネットワークにおけるヒントと Gossip の有効性 126032
平成 16 年度卒業研究発表会（日本大学工学部情報工学科） G-8 Pure 型 P2P ネットワークにおけるヒントと Gossip の有効性 Effectiveness of Hint and Gossip in Unstructured P2P Network 126032 大瀬裕司 ［竹中研究室］ ノードは、このリクエスターにコンテンツを要求するこ とになる。このため、検索メッセージを大量に減少させ ることができる。しかし、リクエストが成功しない場合、 このヒントは無効になり、別途検索を開始する必要が生 じる。 １ はじめに 現在のインターネットは、サーバーにアクセスして情 報を受信するサーバー・クライアント方式が主流である。 しかし、最近はインターネットの普及とブロードバンド 化に伴い人気のあるサイトにアクセスが集中することに よりサーバーに大きな負担がかかってしまう、といった 問題点が挙げられている。 上記の問題を解決するために、ノード同士で通信を行 い必要な処理を行う P2P（Peer to Peer）ネットワーク が注目されるようになった。しかし、Pure 型 P2P ネッ トワークにおいては、コンテンツを検索する際に大量の データが発生するため、ネットワークに負荷がかかると いった問題点が指摘されている。 本稿では、コンテンツ検索時のネットワーク負荷軽減 手法として提案されているヒントと gossip について述べ るとともに、これらの手法の有効性について、シミュレ ーションにより評価し、Pure 型 P2P である Gnutella[1] と比較する。 ３．２ gossip gossip とは主にある確率 P によってノードから転送さ れる query を次のノードに転送し、確率 1−P で query の転送を制限する負荷軽減手法である。これにより送信 される query 数を確率的に抑え、ネットワークにかかる 負担を軽減する。 確率Ｐでqueryを送信 リクエスター ノード ２ Gnutella ノード Gnutella に代表される Pure 型 P2P は、Hybrid 型の P2P とは異なり、コンテンツ検索にサーバーを用いない 方式である。Gnutella を例にとって Pure 型 P2P の手順 を説明する。 ① リクエスターは、query、TTL を設定して、隣接ノ ードにブロードキャストする。 ② 隣接ノードは、コンテンツを所有しない場合は、TTL が切れない場合、さらに隣接ノードにブロードキャ ストする。 ③ コンテンツを所有しているノードは、query の送信 元のノードに対して queryhit を送信する。 ④ 送信元のノードとコンテンツを所有しているノード が直接通信することで、コンテンツの送受信を行う。 図２ ４．１ ヒントを使用した検索の手順を図３により説明する。 リクエスターから query を受け取ったノード A はコ ンテンツ α に関するヒントを自分が所有しているか を確認する。 ② ヒントが見つかった場合は、ヒントの示すコンテン ツ α を所有しているノード B に query を送信する。 見つからなかった場合は query をブロードキャスト して検索する。 ③ リクエスターはノード B からの queryhit を受け取っ た後、直接通信してコンテンツを取得する。 ④ ノード A の情報とは異なりノード B がコンテンツ を所持していなかった場合は、ヒントの情報による 検索は終了する。 ここでは、ヒントが指すノード B がコンテンツαを所 持していなかった時、そこで検索が終了してしまう。そ のため[2]では、更に検索成功率を向上させるために gossip による再検索が提案されていた。 キ ャ ッ シ ュ され る情 報 リク エ ス タ ー リク エ ス ト情報 query ヒントを使用した検索 ① ヒント ノー ド gossip ４ 検索手順 ３ ヒントと gossip ３．１ ノード リク エ ス ト情報 ノー ド リク エ ス タ ー 図 1 ヒント ヒントは、 「リクエスターA がコンテンツ B を検索して いる」というリクエスト情報である。図１は、リクエス ターの出した query が通ったノードにキャッシュされて いく様子を示している。この時、キャッシュされたリク エスト情報がヒントの情報となる。このリクエストが成 功すると、リクエスターが要求コンテンツを保持するこ とになるため、このヒントが有効になり、ヒントを持つ ノー ドＡ ノー ドＢ ヒント（ノードＢ：コンテンツα） query queryhit 図３ 17 コンテンツの送受信 ヒントを使用した検索 コ ン テ ンツ α 平成 16 年度卒業研究発表会 G-8 ４．２ gossip を使用した検索 message数 gossip を使用した検索では、ヒント情報にあるノード がコンテンツを所持していなかった場合に使用する。 検索の流れを図４により説明する。 ① ノード A の所有しているヒントの情報より、ノード B はノード A から query を受け取る。 ② ノード B がコンテンツを所持している場合、４．１ の手順でコンテンツをリクエスターが取得する。 ③ ノード B がコンテンツを所持していなかった場合、 ノード B は gossip により、隣接するノードに確率 P で query を送信するか否かを判断する。 ⑤ 送信する場合は、ヒントを使用した検索を開始する。 送信しない場合は検索終了となる。 50000000 45000000 40000000 35000000 30000000 25000000 20000000 15000000 10000000 5000000 0 gnutella hint hint+gossip 0 0.5 1 zipfのkの値 1.5 2 図５ message 数の比較 1.2 1 成功率 0.8 gnutella hint hint+gossip 0.6 0.4 0.2 コンテンツαを所持していなかった場合,ノードBは 0 0 確率Ｐで隣接ノードにqueryを送信 図６ ノー ド 1 zipfのｋの値 1.5 2 検索成功率の比較 4.5 ノー ドＢ ノー ドＡ 0.5 4 3.5 平均hop数 ノー ド ヒント（ノードＢ：コンテンツα） 3 gnutella hint hint+gossip 2.5 2 1.5 1 0.5 0 図４ ５ gossip を使用した検索 0 シミュレーション 0.5 図７ 1 zipfのkの値 1.5 2 平均 hop 数の比較 ５．１ シミュレーション条件 ５．３ 今回のシミュレーションでは、message 数、検索成功 率、平均 hop 数を Gnutella とヒント、ヒント+gossip に よるコンテンツ検索により比較し検証した。 シミュレーション条件は、シミュレーション回数 50,000 回、コンテンツ 1,000 種類、ノード数 10,000 台、 ヒント数の上限 100、平均 degree 数 4、TTL 5、gossip のＰの値を 1/3 に固定し、zipf[3]のｋの値を 0~2 に変化 させ、シミュレーションした。zipf の k の値はコンテン ツのリクエスト頻度の偏り定数であり、k の値が大きく なるほど、人気のあるコンテンツにアクセスが集中しや すくなる特徴がある。 シミュレーションによりヒントを使用すると、検索成 功率を約 85%を維持したまま、message 数を 80％程削 減できた。しかし、検索成功率では、ヒントに gossip を 追加して検索を続行することの有効性は見られなかった。 その理由として、gossip を使用して検索を続行した場合 のヒントの使用法にあると考えられる。ヒント情報によ る検索を再び行うため、ヒントが有効でない場合、検索 範囲が広がらないためと考えられる。そのため、再検索 をブロードキャストで行うことにより、検索成功率が向 上すると考えられる。 結果の考察 ６ むすび ５．２ シミュレーション結果 本研究では、ヒントと gossip の手法の有効性を、シミ ュレーションにより検証した。その結果、ヒントにより、 検索成功率を維持しながら message 数を削減できること を示した。今後は、gossip により検索を続行する場合、 ヒントを使用せず、ブロードキャストして検索する場合 のシミュレーションを行い、その有効性を確認するとと もに、queryhit の通過したノードにヒット情報をキャッ シュし、ヒントとして利用する手法の有効性を確認する。 図５では message 数を示している。この図から、ヒン トおよびヒント＋gossip については、Gnutella と比べて 最大約 80%の message 数を削減できていた。 図６では検索成功率を示している。Gnutella について は k の値が上がるほど Owner Replication の効果が上が るため、成功率も上昇している。これに対し、ヒントに よる検索ではｋの値に依存せずに、約 85%の成功率を維 持した。また、ヒント+gossip による検索が、ヒントに よる検索とほぼ同様の結果を示し、gossip により検索を 続行することの有効性は見られなかった。 図７では検索遅延を示す。ここでの検索遅延は、コン テンツに到達するまでの最短 hop 数の平均により示す。 Gnutella と比較した場合、ヒントによる検索では、ｋが 小さい領域で約 24%短くなっている。また、ヒント＋ gossip による検索ではヒントによる検索とほぼ同様の結 果を示した。 参考文献 [1] http://www.gnutella.com. [2] Havad D.Johansen and Dog Johansen, “Improving Object Search using Hints, Gossip, and Supernodes.” Department of Computer Science, SRDS2002, page 336~340, Japan, Osaka, 2002. [3] ”zipf ’s law” http://linkage.rockefeller.edu/wli/zipf. 18