Comments
Description
Transcript
0.3MB - 高知工科大学
平成 26 年度 学士学位論文 P2P を利用した計算機の 遊休リソース利用を目的とした システムの提案 Proposed a system for the purpose of idle resource utilization of the computer using the P2P 1150373 指導教員 瀨仁志 植田 和憲 2015 年 2 月 27 日 高知工科大学 情報学群 要 旨 P2P を利用した計算機の 遊休リソース利用を目的とした システムの提案 瀨仁志 データ処理の複雑化に伴い、より演算能力の高い計算機を要求されるようになった。近 年、クラウドと P2P を組み合わせたリソースの効率化を目指す研究がなされているが、リ アルタイムでユーザ側が処理すべきデータをある peer に処理を任せ、他の peer と処理の 結果を共有する研究はあまりなされていない。本研究では、ハイブリッド P2P ネットワー クを用いることで、性能差による処理終了の遅延を小さくすることが目的とする。ユーザ同 士が性能を比較しあい、その中で処理能力の高い peer が処理を担当し、結果を共有するこ とで処理を同時に終了させることが可能となる。今後はシミュレータ上で、ハイブリッド型 P2P ネットワークの構築と提案システムの実装を行い、peer 数を増減させたときのシステ ムの評価を比較し検証する。 キーワード P2P、負荷分散 –i– Abstract Proposed a system for the purpose of idle resource utilization of the computer using the P2P Satoshi YANASE Recently, researches about system combined cloud and P2P to improve efficiency of resource sharing have been proposed. However, systems that can share peers ’processes that should be processed in real time have not been proposed, In this paper, in order to share processes of peers we propose a system adopts hybrid P2P network model and enables to reduce processing delay due to performance differences. By comparing performance of each peer and grouping the peers, the system can be responsible for high processing with peers processing capacity. To evaluate our proposal system, we implement our proposal system on a simulator. We evaluate our proposal system in terms of increase or decrease of peers. key words P2P, Load sharing – ii – 目次 第1章 はじめに 1 第2章 ネットワークアーキテクチャ 2 2.1 クライアント・サーバシステム . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 P2P ネットワークシステム . . . . . . . . . . . . . . . . . . . . . . . . . 3 第3章 2.2.1 Winny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.2 Skype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 P2P クラウドアーキテクチャ・分散コンピューティング 6 3.1 MMOG のための P2P クラウドアーキテクチャ . . . . . . . . . . . . . . 6 3.2 Folding@home . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.3 SETI@home . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 遊休リソースを考慮した提案手法 8 4.1 提案手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.2 クラスタリング . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.2.1 ピアの演算能力を考慮したクラスタリング . . . . . . . . . . . . . . 9 4.2.2 ソフトウェア上の距離を考慮したクラスタリング . . . . . . . . . . 10 4.2.3 ピア間のスループットを考慮したクラスタリング . . . . . . . . . . 11 第4章 第5章 ジョブの分割による処理時間の評価と検証 12 5.1 検証方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5.2 検証結果・考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.3 今後の課題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 まとめ 16 第6章 – iii – 目次 謝辞 17 参考文献 18 – iv – 図目次 2.1 クライアント・サーバシステム . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 P2P ネットワークシステム . . . . . . . . . . . . . . . . . . . . . . . . . . 3 4.1 提案システム概念図 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.2 ソフトウェア上の距離の例 . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.3 通信速度の概念図 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.4 通信速度を考慮したクラスタリング . . . . . . . . . . . . . . . . . . . . . . 11 5.1 処理 Default の内部処理 . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.2 処理 Proposed の内部処理 . . . . . . . . . . . . . . . . . . . . . . . . . . 13 –v– 表目次 4.1 同一仮想空間でのクラスタリング . . . . . . . . . . . . . . . . . . . . . . . 10 5.1 シミュレーション環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.2 ジョブの分割による実行時間の検証 . . . . . . . . . . . . . . . . . . . . . . 14 – vi – 第1章 はじめに 近年のグラフィックスなどのデータの大規模化により、データの処理を行うために、演算 能力の高い計算機を用意する必要があるが、このような計算機を用意するためには多くのコ ストが必要である。また、このような計算機を用意したとしても、ゲームプレイ時での特定 の条件でのみ PC の最大能力を発揮するため、多くの場合、遊休リソースが発生してしま う。さらに、多くの予算をかけて構築した計算機は多くのサービスを高品質で受けることが 可能であるが、中には演算能力の低い計算機を所有している場合があり、サービスを低品質 でしか受けることができない計算機もある。そこで、本研究では、ハイブリット P2P ネッ トワークを用いた高性能な計算機の遊休リソースを活用した、ネットワーク上のリソースの 効率化を目的としたシステムの提案を行う。このシステムは、ネットワーク上にある低性能 な計算機の負担を軽減し、サービス全体の品質の向上につなげるものである。 –1– 第2章 ネットワークアーキテクチャ この章では、ネットワークアーキテクチャとして確立しているクライアント・サーバシス テム、P2P ネットワークシステムについて述べる。 2.1 クライアント・サーバシステム クライアント・サーバシステムとは、図 2.1 のように、ひとつのサーバに複数のクライア ントが接続された構成となっている。クライアントが情報を管理するサーバに必要な情報の 取得の要求を行い、要求を受けたサーバは必要な情報をクライアントに送信し通信を終了す る。このような一連の流れがクライアント・サーバシステムである。 図 2.1 クライアント・サーバシステム –2– 2.2 P2P ネットワークシステム 2.2 P2P ネットワークシステム P2P とは Peer-to-Peer の略称であり、Peer とは対等の立場でネットワークを解して接続 されるコンピュータの意味で、図 2.2 のように P2P を構成するコンピュータはクライアン ト、サーバを区別することなく、全てのコンピュータがサーバやクライアントとして動作す るシステムである [1]。P2P ネットワークを用いているアプリケーションとして、ファイル 共有ソフトの Winny や無料通話が可能な Skype があげられる。 図 2.2 P2P ネットワークシステム P2P ネットワークシステムの主な利点として、機器・管理・運用・保守などに関するコス トの削減が容易な点や、サーバ機能が各ピアによって分散して維持されているため、ユーザ の数が増加してもシステムの規模を増加しなくてもシステム規模を増加する必要がない点、 障害耐性に優れている点があげられる。しかしながら、一度サービスを開始するとシステム 全体を停止することができないものがあり、ネットワーク全体の管理・監視には不向きであ るという点がある。 P2P ネットワークにおける、ピアの探索方法でピュア P2P、ハイブリッド P2P、スーパー ノード P2P の 3 種類が存在している。 ハイブリッド P2P は、中央にインデックスサーバと呼ばれる管理サーバによって P2P –3– 2.2 P2P ネットワークシステム ネットワーク全体を管理する。管理サーバはネットワークに参加している全てのピアが保持 しているコンテンツの一覧を格納しており、コンテンツを取得したいピアの問い合わせに対 してコンテンツの一覧を参照し該当するピアの情報の送信を返す。この情報を受け取ると 直接ピア同士で通信を行い情報のやり取りを行う。ハイブリッド P2P ネットワークは管理 サーバによりネットワーク全体の管理監視ができるため、他の探索方法より要求したピアの 検索が早いという利点を持つが、管理サーバが全てのピアが保持しているコンテンツの一覧 を格納していることから管理サーバがダウンしてしまうと、P2P ネットワーク全体に影響 を与えてしまうという欠点を持つ。 ピュア P2P は、ハイブリッド P2P と違い、サーバを用いることなくピア同士が直接通信 を行うのが特徴で、ピアが各ピアの情報を保持している。ピュア P2P は、各ピアが他のピ アの情報を分散して保持しているため、障害耐性が非常に強いといえる。また、システム側 がシステムの拡張を行うことなく多くのピアが参加でき、ピアの参加数が多ければより多く のコンテンツがシステムとして保有が可能であるため、スケーラビリティが高いといる。し かし、ピュア P2P にはインデックスサーバのような管理サーバが存在しないため、全ての コンテンツデータの把握ができないため、コンテンツの探索効率は低いという欠点を持つ。 スーパーノード P2P は、同一の機能をもつピアのほかに、スーパーノードと呼ばれる検 索機能などを備えるピアがネットワーク上に参加していることが特徴で、サーバの代わりに スーパーノードがピアの情報を分散的に保持する。ピアから要求があった際に他のピアの情 報を提供する役目を持つ。また、スーパーノードは端末の演算能力や回線速度など他のピア より優れていることなどを考慮してが選ばる。サーバの代わりにスーパーノードがピアの情 報を分散的に保持しているため障害耐性が強いといえる。 2.2.1 Winny Winny は国産の P2P ファイル共有アプリケーションで、Freenet のアーキテクチャを元 に、ファイル検索の効率性を追及したものである [3]。特徴として、ファイル共有に中央サー バを必要としないピュア P2P ネットワークであり、通信の暗号化、データを拡散する際に –4– 2.2 P2P ネットワークシステム 複数のコンピュータを仲介させるなどして各コンピュータにキャッシュを残す転送機能、似 たようなコンテンツを検索しているピア同士をグループ化するクラスタリングがあり、これ らによって、高い匿名性、効率のよいファイル共有の実現させた。 2.2.2 Skype Skype はマイクロソフト社が提供する P2P 技術を利用したインターネット電話サービス で、機能として、Skype ユーザ間での音声通話、文字チャットを無料で行うことができる [4]。また、有料のサービスとして、Skype から固定電話へ発信、着信が可能となる。 –5– 第3章 P2P クラウドアーキテクチャ・分散 コンピューティング MMOG のための P2P クラウドアーキテクチャ、分散コンピューティングプロジェクト における研究、プロジェクトを述べる。提案手法では P2P の利点を利用しつつ、分散コン ピューティングの高い品質の総合演算能力を生かし、ユーザ側のサービス品質の向上させる ものである。 3.1 MMOG のための P2P クラウドアーキテクチャ P2P クラウドコンピューティングは高い演算能力、スケーラビリティ、信頼性、および サーバの効率的な情報共有の特徴を有しており、これを用いて 2 レベルの負荷管理、ゲーム サーバ間で各ゲームサーバおよび負荷管理のためのマルチスレッショルド負荷管理を含む同 時多人数参加型オンラインゲームのためのハイブリッド P2P クラウドアーキテクチャの提 案であり、高負荷下でのマルチサーバアーキテクチャと比べ、20.6%もの平均時間を短縮す ることが可能である [5]。 3.2 Folding@home Folding@home[6] とはアメリカのスタンフォード大学の分散コンピューティングプロジェ クトであり、2000 年 10 月より、全世界から 100 万個以上の CPU が参加している分散コン ピューティングプロジェクトで、このプロジェクトの最終目標として、たんぱく質の折りた –6– 3.3 SETI@home たみ構造を研究し、アルツハイマー病、がん、パーキンソン病、狂牛病をはじめとする各 種疾病の治療に役立てることである [7]。2015 年 2 月 21 日 18 時現在、演算能力を総合で 6.049PFLOPS を達成している [8]。 3.3 SETI@home SETI とは地球外の知的生命を検出することを目標としている科学の一分野であり、この うち radio SETI(電波による SETI) として知られる手法では、電波望遠鏡を使って宇宙か らの狭帯域電波信号を検出するプロジェクトであり、このプロジェクトにおける大量のデー タを解析するために、電波望遠鏡の近くに設置した特殊用途スーパーコンピュータを用いた が、1995 年に David Gedye が、インターネットでお互いにつながれた多数のコンピュータ によって構成される仮想スーパーコンピュータを使って、電波による SETI の計算処理をす ることを提案し、1999 年 5 月に SETI@home プロジェクトを組織した [9]。 –7– 第4章 遊休リソースを考慮した提案手法 本研究ではハイブリット P2P ネットワークにおけるリソースの効率化を目的としたシス テムの提案を行う。遊休リソースとは、プロセッサなどの余剰能力の部分を指す。今回提案 するシステムは、このプロセッサの余剰能力である遊休リソースを使い、P2P ネットワーク 全体のリソースの効率化を目指すものである。この提案システムは、大規模多人数同時参加 型のオンラインゲームといったアプリケーションのひとつとして使用することができるシス テムである。 4.1 提案手法 本研究で提案するシステムはピアからピアに処理結果を共有するシステムであり、ネット ワーク全体の処理時間を減少させ、ネットワーク全体のサービスの品質の向上を目指すもの である。このシステムは 4.2 であげた 3 つのクラスタリングを用いて運用する。提案手法の 概念図を図 4.1 に示す。低性能ピアとはいくつかのデータを処理するのに十分な演算能力を 保有していないのに対し、高性能ピアとは他のピアのデータを処理するのに十分な演算能力 を保有している。 図 4.1 では、まず運営側であるサーバから送信されたデータは各ピアに送信されている。 ピアが受け取ったデータは性能を考慮したクラスタリングで決められた高性能ピアがデータ の処理を行う。高性能ピアが処理した処理結果は低性能ピアへ送信し、共有を行う。 この提案手法によって、P2P ネットワークに接続されたすべてのピアのリソースを効率的 に使用することができるため、各ピアは快適なサービスを受けることが可能である。この提 –8– 4.2 クラスタリング $&%&'() $&%'() ! "# 図 4.1 提案システム概念図 案手法を PIAX を用いて実装を行い、提案手法の評価と検証を行う。 4.2 クラスタリング 今回、クラスタリングはネットワーク全体の実行時間を減少させるために提案手法による クラスタリングは以下の 3 つを行う。 • ピアの演算能力を考慮したクラスタリング • ソフトウェア上の距離を考慮したクラスタリング • ピア間のスループットを考慮したクラスタリング 以下ではこれらのクラスタリングの説明を行う。 4.2.1 ピアの演算能力を考慮したクラスタリング 演算能力の考慮とは各ピアに対してある共通のデータを処理を行うことによる経過時間を 測定し、その結果を元にクラスタリングを行う。想定されている負荷が加わったとしても、 他に計算を余裕を持って行うことができるピアを高性能ピアとし、反対に、計算に余裕がな いピアを低性能ピアとしてクラスタリングを行う。このクラスタリングを元に、どのピアの –9– 4.2 クラスタリング 演算能力や閾値はサービスによって設定に変更を加える必要がある。ピアの性能を測るため にはベンチマークとして用いられるスーパー π[10] などを用いる。 4.2.2 ソフトウェア上の距離を考慮したクラスタリング ソフトウェア上の距離とは、ピア同士が同一のソフトウェアを用いている場合や、同一ア プリケーション上で、同じ仮想空間にいるといった関係の近いものを考慮し、クラスタリン グを行う。 オンラインゲームで例えると、図 4.2 ではエリア 1 という仮想空間にプレイヤーが A、B、 C、D が、エリア 2 という仮想空間にプレイヤー E、F、G、H が存在しているとする。こ の場合をソフトウェア上の距離が近いという。各プレイヤーの仮想空間での位置情報を取得 し、距離が近い者でクラスタリングを行う。図 4.2 の場合では表 4.1 のようなクラスタ分け となる。 図 4.2 ソフトウェア上の距離の例 表 4.1 同一仮想空間でのクラスタリング クラスタ プレイヤー (ピア) C1 ABCD C2 EFGH – 10 – 4.2 クラスタリング 4.2.3 ピア間のスループットを考慮したクラスタリング ピア間のスループット計測し、スループットの値が高いものでクラスタリングを行う。こ のクラスタリングはサービスの品質低下を抑制するために必要である。スループットの値に よっては自分自身でデータの処理を行うほうが早い場合があり、さらに、ボトルネックを回 避するためである。図 4.3 は通信速度の概念図を表している。ピア A とピア B はリアルタ イムで通信するのに向いており、ピア A とピア C は致命的な遅延が存在するものとする。 図 4.3 の場合、ピア C を含むネットワークを作成した場合、ピア C は重大な遅延が発生し、 ピア A、B、C の受けることができるサービスの質が低下してしまう。そこで、図 4.4 のよ うにクラスタリングすることによって、ピア A、B のサービスの低下を防ぎ、ピア C はよ りよい条件下でサービスを受けることができるピアを探索する。 図 4.3 通信速度の概念図 図 4.4 – 11 – 通信速度を考慮したクラスタリング 第5章 ジョブの分割による処理時間の評価 と検証 ネットワーク全体のサービス品質向上を目指すために、ネットワーク全体の処理時間の短 縮ための検証を行う。そのために、あるジョブを分割することで、ネットワーク全体の処理 時間を短縮できるかどうか検証を行う。 5.1 検証方法 重い処理と軽い処理を用意し、重い処理と軽い処理でジョブを分割した場合と、重い処理 と軽い処理でジョブを分割しない場合でどちらの処理時間が短いかを比較検証を行う。な お、あるピアが動作を開始してから全てのピアが動作を終えるまでの時間を計測する。今回 の検証では PIAX[11] を用い、ローカルでのシミュレーションを行った。前提として、共有 すべきデータは全てのピアが保持しており、計算を行うピアの数は 3 つで高性能ピアの数 は 1 つと低性能ピアの数は 2 つからなるネットワークを作成し、別に実行時間計測ピアを 設定している。また、今回はローカル上でシミュレーションを行っているため、ソフトウェ ア上の距離は近いものとする。重い処理として逆行列の導出を、軽い処理として行列同士の 掛け算を行う。さらに、高性能ピアはランダムで選定を行う。各ピアに 1∼5 の値を設定し、 値が低いほうが高性能ピアとした。また、行列は第 250∗n 行の行列としており。n は各ピ アに与えられた能力値 1∼5 を用いる。これは、ピア間で実行時間の差を出すためのもので あり、実環境とは大きく異なる。今回、Default と Proposed の 2 つのシミュレーションを – 12 – 5.1 検証方法 行う。Proposed の処理時間が短くなるのかどうかの検証を行う。2 つのシミュレーション Default、Proposed の内部処理はそれぞれ図 5.1 と図 5.2 である。Default は全てのピアが 逆行列と行列の掛け算を行っており、Proposed では高性能ピアから逆行列を行ったときの 結果が送信すると、全てのピアが行列の掛け算を行うシミュレーションである。シミュレー ション環境は表 5.1 である。 !"#$% &"#$% $% 図 5.1 処理 Default の内部処理 '()*+,./0 1234 図 5.2 !"#$% &"#$% $% 処理 Proposed の内部処理 – 13 – 5.2 検証結果・考察 表 5.1 5.2 シミュレーション環境 OS windows 7 Enterprise (64bit) CPU Intel Core i7 3770 メモリ 16GB 検証結果・考察 プログラムを実行した結果、表 5.2 となった。処理時間は計算開始から全てのピアが計算 終了するまでの時間を計測し、出力した値である。表 5.2 より、Default より提案手法であ る Proposed の処理時間は短くなっていることが分かる。しかし、今回のシミュレーション はローカルで行っているため、スループットや実際の性能は考慮されていない。そのため、 Proposed の処理時間はこの結果より長くなるということが見込まれる。 表 5.2 ジョブの分割による実行時間の検証 処理方法 処理時間 Default 30162ms Proposed 3790ms シミュレーションでは、高性能ピアが低性能ピアの一部の処理を担当するということを 行っているので、ネットワーク上に接続されているピアの演算能力の効率化が図れたといえ る。さらに、ジョブを分割し、結果の送信を行うことで、全てのピアが計算処理を行うより もネットワークに負荷がかかるという懸念が存在しているが、今回、スループットを考慮し たクラスタリングを行っているため、スループットの値が高いもの同士のグループとなって いるため、懸念されるほどの影響を与えることはないと推測する。また、今回では逆行列を 導出することが重い処理と分かっているため、逆行列を重い処理として高性能ピアに計算を 任せていたが、実環境で用いる場合、重い処理ということの判定を行う必要がある。また、 送信されるデータの信頼性を考慮しなければならない。 – 14 – 5.3 今後の課題 今回は処理するデータが全てのピアで同じであるという前提の下、シミュレーションを 行った。そのため、同一のアプリケーション上でのみ動作するシステムとなったが、各ピア の CPU やメモリなどの使用率を監視し、各ピアの遊休リソースを把握することで、異なる アプリケーション上、異なる動作を行う処理であっても処理を任せることが可能になると見 込まれる。 5.3 今後の課題 実際にスループット、性能差を考慮するために、実環境上の P2P プラットフォームを用 い、より実環境に近づけたシミュレーションを行う必要がある。また、送信されるデータの 信頼性を調査やどの処理が重い処理なのかを判定を行う管理サーバの設置が必要である。さ らに、遊休リソースの活用のため、CPU やメモリといったリソースの監視を行うシステム を実装する必要がある。 – 15 – 第6章 まとめ 近年、グラフィックなどのデータの大規模化により、よりたかい演算能力をもつ計算機を 用意する必要があり、多くのコストが必要になる。この研究により、演算能力の高い計算機 の遊休リソースを用いることで、演算能力の低い計算機の演算能力を補い、ネットワーク全 体のサービスの品質向上につながる。本研究では、P2P ネットワークにおけるリソースの効 率化を目的とし、高性能ピアから低性能ピアの処理結果を共有することで低性能ピアの負担 を軽減するシステムの提案を行った。シミュレーションの結果、すべてのピアが持つ共通の データを高性能ピアが処理を行うことで、低性能ピアの負担軽減分、他のデータの処理を行 うための余裕を持たせることが可能であることが分かった。今後の課題として、スループッ トの考慮と、性能差の考慮を行うとともに、全てのピアの遊休リソースを活用するため、 CPU やメモリのといったリソースの監視を行うシステムの実装、共有されるデータの信頼 性の監視を行うサーバの設置、重い処理の判定を行うシステムの実装を行い、実環境上の P2P プラットフォームを活用することで、実環境でのシミュレーションを行う必要がある。 – 16 – 謝辞 本研究を行うにあたり、ご指導を賜りました高知工科大学の植田 和憲講師に心から感謝 いたします。また、本論文に対し副査を努めていただいた福本 昌弘教授、吉田 真一准教授 に心から感謝いたします。ご自身も忙しいのにもかかわらずこちらにも気にかけてください ました木村 紀夫氏に感謝いたします。論文およびプログラムに助言をいただきました小柳 翔氏、菅谷 和馬氏、冨田 涼太氏、松下 和生氏、入本 静哉氏に感謝いたします。また、4 年 間お世話になった情報学群の教職員の皆様にも感謝いたします。 – 17 – 参考文献 [1] 江崎 浩, “P2P 教科書”, インプレス R&D, 2008. [2] Jogn F. Buford, Heather Yu, Eng Keong Lua, “P2P Networking and Applications”, MORGAN KAUFMANN, 2008. [3] 金子 勇, “winny の技術”, アスキー書籍編集部, 2006. [4] “Skype”, http://www.skype.com/, 2015/02/22 閲覧. [5] Ginhung Wang, Kuochen Wang, “An efficient hybrid P2P MMOG cloud architecture for dynamic load management”, IEEE, pp.199-204, 2012. [6] Stanford Univercity, “Folding@home” https://folding.stanford.edu/home/, 2015/02/06 閲覧. [7] Sony Computer Entertainment Inc, “Folding@home for PlayStation3”, http://www.scei.co.jp/folding/jp/, 2015/02/06 閲覧. [8] “Folding@home Client statisvivs by OS ”, http://fah-web.stanford.edu/cgi-bin/main.py?qt 閲覧. [9] Univercity of Calfornia, “SETI@home”, http://setiathome.berkeley.edu/index.php, 2015/02/06 閲覧. [10] 金 田 康 正, “金 田 研 究 室”, http://pi2.cc.u-tokyo.ac.jp/index-j.html, 2015/01/31 閲覧. [11] “PIAX”, http://www.piax.org/, 2015/02/22 閲覧. – 18 –