2012 年度 卒業論文要旨 ファイル共有型 P2P ネットワークにおける負荷分散のための遠慮型探索法 学修番号 09175080 1 序論 松下 純也 指導教員 朝香 卓也 関数を用いて，各ピアのハッシュ値を算出し，ハッ シュ空間に配置し，各ピアはデータのハッシュ値を求 近年，インターネットの爆発的普及と共に，イン ターネット上におけるコンテンツ配信が増加してお め，ハッシュ空間内で最も近いピアにクエリを転送 し，データを取得する． り，それに伴い，インターネット上のトラヒックも 非構造型 P2P[2][3] はクエリを転送するピアが決 年々増加している．トラヒックの増加に対応するた まっておらず，フラッディングなどの無作為な検索方 め，従来のコンテンツ配信では，サーバの増設など， 法を用いる．フラッディングはピアがデータを要求 多額の費用を必要とする．このような問題を解決する する際，TTL（Time To Live）と呼ばれる値を定め， ため，新しいコンテンツ配信の技術として，P2P 技 クエリを隣接する全てのピアに送信する．クエリを 術の活用が必要となってきている． 受け取ったピアがデータを保持している場合，クエリ P2P は，インターネット上のコンピュータ同士を 直接繋いで構成されたネットワークであり，各コン を送信したピアへデータを保持していることを送信 ピュータはピアと呼ばれ，他のピアの回線を利用し る全てのピアにデータ要求のクエリを送信する．こ て，各ピアの保持しているコンテンツのやり取りが れを TTL の値を超えない限り繰り返す．しかしこの 可能となる．従来のインターネットのクライアント 方法はネットワーク上のトラヒックが増加してしまう サーバシステムのネットワークとは異なり，サーバが ことや，検索に時間がかかるなどの問題がある．こ 不要であり，ある回線に問題が発生しても，別のピア のような問題を解決するため，ランダムウォークなど を通じて通信が可能であるため，P2P システムは近 の方法がある．ランダムウォークはクエリを受け取っ 年注目されている．しかし P2P システムでは各ピア たピアは隣接するピアからランダムに一つを選択し， ごとに保持しているコンテンツの種類や数が異なり， そのピアにのみクエリを送信する．これにより，ネッ コンテンツを多数保持しているピアは，少数保持し トワーク上のトラヒックを抑えることができる可能 ているピアと比較すると，コンテンツ要求にヒットし 性がある． する．データを保持していない場合，さらに隣接す やすく，負荷が大きくなり，各ピア間に負荷の差がで きてしまう． そこで本論文では，コンテンツ要求クエリの送信 3 提案手法 方式をコンテンツ保持数の少ないピアに優先的に送 信することにより，コンテンツ保持数の多いピアへの 負荷を減らし，負荷分散を行う手法を，計算機を用い たシミュレーションの結果から，既存の送信方式と比 較，評価を行った． 一般的な P2P システムのクエリの経路は，コンテ ンツ保持数の多いノード（ハブノード）とコンテンツ 保持数の少ないノード（非ハブノード）と関係なく， ランダムウォークでホップする．この時，ハブノード は非ハブノードと比較すると，コンテンツ保持数が 多いため，コンテンツ要求クエリが多数ヒットするこ 2 関連研究 ととなる．コンテンツ発見までの時間は短いものの， 多数のコンテンツ要求クエリのヒットにより，負荷が P2P システムにおいて，クエリの転送方式によって 構造型 P2P と非構造型 P2P の二種類に分類できる． かかるため，ダウンロードまでの時間は増加するな 構造型 P2P[1] は DHT（Distributed Hash Table） 本研究で提案する，遠慮型探索法では，始めに非ハ どの問題が発生する． を用いて，ネットワークトポロジや検索情報の配置 ブノードの探索を優先的に行う．このとき非ハブノー が決定されている．構造型 P2P の代表的なものとし ドを探索するホップ数を予め設定し，そのホップ数を て，Chord，Kademlia，CAN（Content-Addressable 超えると，隣接するノードにハブノードが存在する Network）などがある．これらのシステムは，ハッシュ 場合，ハブノードの探索を優先的に行うものとする． 遠慮型探索法を用いることで，ハブノードでのコ ンテンツ発見率が低下し，それに伴い負荷が低下す るため，ネットワーク内の最大負荷を低減することが 可能となる． 4 シミュレーション結果 一般的な P2P システムと遠慮型探索法の比較する シミュレーションを行った．ネットワーク上のノード 図 2: ハブノードのコンテンツ保持数９の場合のヒッ 数 10 個，ハブノード数 4 個，非ハブノード数 6 個， ト数 コンテンツの種類を 20 種類とし，各ノードを直線上 に配置する．一般的な P2P システムではハブノード と非ハブノードをランダムに配置し，ハブノードと非 ハブノード関係なく，探索する手法を表し，遠慮型探 索法では非ハブノードを前に，ハブノードを後ろに 配置し，非ハブノードを優先的に探索する手法を表 す．どちらの場合も，コンテンツを保持しているノー ドが発見された場合は，それ以降のノードにはクエ リの送信を行わない．非ハブノードのコンテンツ保 持数は 3 種類とし，ハブノードのコンテンツ保持数 図 3: ハブノードのコンテンツ保持数１２の場合の を６，9，12 種類として，あるコンテンツ要求クエリ ヒット数 がどのノードでヒットするのか，シミュレーションを 行った． 結果は図 1，図 2，図 3 のようになった．コンテン 5 結論 ツ要求クエリのヒット数の最大値は，各場合におい 本論文では P2P ネットワークにおける負荷分散の て，通常時と比べ，遠慮型探索法の方が減少している ための遠慮型探索法を提案，シミュレーションを行っ ことが分かる．この結果より，最大負荷の分散に遠慮 た．今後は今回のような 1 次元上ではなく，より実環 型探索法が有効であると言える．また，ハブノードの 境に近い 2 次元上におけるシミュレーションを行い， コンテンツ保持数を変化させた場合，ハブノードの 適用可能かどうか検証が必要である．またネットワー コンテンツ保持数が多いほうが，より最大負荷が減 ク上のノード数や，各ノードのコンテンツ保持数など 少していることが分かる．これにより，ハブノードと の様々な数値も，より実環境に近い条件でシミュレー 非ハブノードのコンテンツ保持数の差が大きいほど， ションを行い，遠慮型探索法の有用性の検証が必要で 負荷分散の効果が現れやすいと言える． ある． 参考文献 [1] Eng Keong Lua , Jon Crowcroft , Marcelo Pias , Ravi Sharma , Steven Lim ”A Survey and Comparison of Peer-to-Peer Overlay Network Schemes” IEEE Communications Surveys，pp．72-93，2005． [2] E．Cohen，and S．Shenker: ”Replication strategies in unstructured peer-to-peer networks” Proc． SIGCOMM ’02， pp．177-190， 2002． 図 1: ハブノードのコンテンツ保持数６の場合のヒッ ト数 [3] Q．Lv，P．Cao，E．Cohen，K．Li，and S．Shenker: ”Search and replication in unstructured peer-to-peer networks” Proc．ICS ’02，pp．84-95， 2002．
© Copyright 2024 ExpyDoc
