平成 18 年 11 月 24 日大学院輪講発表資料ヘテロなグリッド環境における並列計算に関する研究動向 A Survey on Parallel Computing in Heterogeneous Grid Environments 電子情報学専攻修士課程１年 66425 関谷岳史近山・田浦研究室 Dynamic Change of CPU/Network Load Abstract In this survey, I introduce WOW; a middleware for parallel computing in heterogeneous environments. WOW is a distributed system that combines virtual machines, overlay networking and peer-to-peer techniques to create scalable wide-area networks of virtual workstations for highthroughput computing. WOW present to end-users and applications an environment that is functionally identical to a local-area network or clusters of workstations. Experiments show that the latency in joining a WOW network is of the order of seconds. Experiments also show that the parallel speedup of 13.5 for the PVM-based fastDNAml application. Heterogeneous hardware and Firewall/ software NAT Maintenance はじめに 1 Complex Configuration 近年、コモディティコンピュータを用いた PC クラスタの低価格化、ネットワークバンド幅の増加などにより、WAN をまたがる PC クラスタを複数つなげ、大規模な計算資源とし Difficult to Know What’s Happening て利用しようという研究が盛んに行われている。このような Grid 環境では様々な理由により、いままで同じサブネットに属する 1 つのクラスタで行われていた並列計算の仕組みをそのまま用いることができない。問題としてたとえば、 • • • • 図1 Failure Problems in Grid Environment ハードウェアやソフトウェアのヘテロ性ファイアウォール/NAT による通信の妨げたとえば、OS の違いは協調して動作するアプリケーショ故障ンを動かす上で大きな障害になる。仮に同じ Linux であった資源の状態の動的な変化 (CPU/ネットワーク負荷など) としてもディストリビューションによって違いが生じることなどが、あげられる。また、エンドユーザやアプリケーショもある。また、インストールされているソフトウェアやラインの立場からみると、ブラリが異なれば、同じアプリケーションを実行するのは難しくなる。同じソフトウェアがインストールされていたとし • グリッド用ミドルウェアの設定の複雑さ • 資源状態やアプリケーションの状態の把握の難しさても、バージョンの違いによって性能の低下や、場合によっては動かなくなる可能性もある。などが、Grid 計算利用の妨げになっていると考えられるまた、ネットワークのヘテロ性も大きな障害である。各ド (Figure. 1)。本サーベイでは特にグリッド環境のヘテロ性にメイン間の通信のレイテンシやバンド幅は WAN をまたがる対応する技術について紹介する。ために大きな違いがあり、通信を頻繁に行うような計算を行環境のヘテロ性はアプリケーションやエンドユーザにとっおうとすれば、深刻な性能低下がおきる。さらに、各ドメイて様々な問題を生じさせる。Grid 計算に用いられる各ドメンの入り口にはセキュリティポリシーやネットワーク事情にインのマシンはベンダーや購入時期が違うのが普通でハードよりファイアウォールや NAT がある場合がある。クラスタウェアやソフトウェアのヘテロ性は当然生じるものとして考計算では各マシンから他のマシンへ自由に TCP/UDP を用えなければならない。いた通信が行えるのが普通であるため、それを想定したアプ 1 リケーションがほとんどである。そのため、ファイアウォーアプリケーション環境などが修正なしに再利用可能となる。ル/NAT は、今までの仕組みが適応できなくなる大きな原因以降の構成は次のとおりである。2 節で WOW[2] および、その基盤技術である IPOP[1] について述べる。3 節で WOW になっている。の性能に関する実験の結果を紹介し、4 節でまとめをする。このような問題に対して様々なアプローチがとられているが、中でも仮想マシンとオーバレイネットワークを組み合わせて非対称な接続性の問題を解決している研究が多くなされ 2 ている。立薗らの研究 [4] では Xen と VPN によって、それ WOW ぞれ仮想マシン、仮想ネットワークを構築している。ViNe[3] まず、WOW のネットワーク部分で用いられている IPOP にでは仮想ルータとなる仮想マシンを設置し、やはり、オーバついて述べる。レイネットワークによって、対称な接続性のある仮想ネット 2.1 IPOP IPOP とは、P2P ネットワークを用いて IP をトンネリンワークを構築している。本サーベイでは、WOW[2] および IPOP[1] という手法をグすることで、ネットワークを仮想化する技術である。これ取り上げる。WOW は各マシン上で仮想マシンを動かすことによって提供される仮想 IP ネットワークによって、実ネットでソフトウェアのヘテロ性をなくす。また、P2P を用いたワーク上に存在するファイアウォールや NAT を苦にするこオーバレイネットワークを構築し、その上に IP ネットワークとなく、両方向での接続性が得られる。先行研究として、ネッを構築することで、ファイアウォールや NAT をアプリケートワークを仮想化するものは存在するが、いずれも中央サーションに対して隠すということを行っている (Figure. 2)。バを用いて適応的ルーティングを行っており、ネットワークそのため、WOW 上では仮想的なクラスタが構築され今までが大きくなるのに対応ができないと考えられる。IPOP のよクラスタで用いられてきたミドルウェア、アプリケーションうに P2P でルーティングを行うことは次のような利点があを修正することなくそのまま使える。IPOP は WOW で仮ると考えられる。想オーバレイネットワークを構築するために用いられている • スケーラビリティ: P2P の技術により、自己構成、分散技術である。化、動的なノードの増加・減少への適応が可能になるた Virtual Grid Cluster IPOP (IP over P2P) め、大規模な環境でも運用が可能になる。 • 弾力性: P2P ネットワークは高い故障確率の中でもロバストであることが知られている。IPOP でも様々なレ P2P Network ベルでの耐故障性技術が応用可能であるという利点が Physical Infrastructure ある。故障や脱退によって IP パケットが落ちることがあるが、そのようなパケットは P2P の上に実装された NAT firewall TCP/IP によってうまく処理される。 • アクセス可能性: NAT/ファイアウォール越えの技術は P2P overlay network いくつか提案されているが、グローバルに到達可能な STUN/STUNT サーバが必要である。P2P ネットワークを用いることで、このような専用のサーバなしに、図2 NAT/ファイアウォール超えが可能である。 Network Virtualization 2.2 IPOP の設計 2.2.1 IP パケットのキャプチャリング IPOP は図 3 のように送りもとのホストからの IP パケットを仮想ネットワークデバイスで受け取り、Brunet P2P に WOW の設計の目指したところは次のようなものである。 • 多数のノードでスケールする • 仮想ネットワークリンクの自動構成を通じてノードの追よるオーバレイネットワーク上でトンネリングする。最後に加を容易にするあて先の Brunet ノード上に届いたメッセージはあて先ホス • 仮想マシンがドメイン間で移動しても IP の接続性をトの仮想デバイスへ IP パケットとして届けられる。IPOP 保つでは tap とよばれる仮想ネットワークインターフェースをホ • エンドユーザとアプリケーションに LAN におけるワーストの中にもつ。tap は read/write が可能なデバイスとしてクステーションのクラスタと機能的にまったく同じもの振舞う。を提供する tap を通して仮想インターフェースのカーネルによって作このような機能を提供することで、異なるドメインに独立にられたイーサネットフレームはユーザレベルのアプリケー WOW ノードを配置でき、LAN であるかのように管理・プションによって読むことが可能である。tap はネットワークログラミングが行える。また、管理者や、ユーザにとってよインターフェースとして振舞うのでイーサネットフレームレく慣れたバッチスケジューラや分散ファイルシステム、並列ベルのメッセージを扱う必要があるので、ARP や RARP と 2 IP: A application Tunneling tap IPOP IP: N IP: M Src: A:a Dst: M:m application tap Host A Brunet Message IPOP IP Packet Src: M:m Dst: A:a Src: N:n Dst: M:m NAT NAT Src: M:m Dst: N:n NAT Table A:a ⇔ N:n 図 3 IP packet capturing IP: B Src: B:b Dst: N:n Host B NAT Table M:m ⇔ B:b 図 4 NAT Hole Punching いった IP ベースでないフレームも受け取る可能性がある。現在の実装では、仮想アドレス空間中のすべてのホストは存在しないゲートウェイに対してルーティングされることに算ノードには要求される環境 (たとえば、ある Linux のディなっている。このゲートウェイは仮想アドレス空間での IP ストリビューションとライブラリ、ユーティリティやアプリアドレスと tap と競合しないイーサネットアドレスを持つ。ケーションなど) をあらかじめ VM イメージとして設定してよって、ホストは IP ベースのイーサネットフレームのみをおく。あとは、LAN におけるクラスタ環境で、ディスクか送ることになる。また、P2P エンドポイントに届いた IP パら環境が読み込まれるように、WOW ではすべてのノードにケットは、この仮想的なゲートウェイのイーサネットアドレ理者は tap をセットアップし、仮想アドレス空間でユニー VM イメージがコピーされ、実行される。 WOW は VMware などの NAT ベースの仮想ネットワークインターフェースとともに動くので、VM にあらたに実 IP を割り当てる必要はない。ただ、先に述べた IPOP のみが必要である。また、IPOP にはグローバル IP を持つ IPOP ノード (はじめに接続するためのノード) とオーバレイ上での IP アドレスを設定するための短い設定ファイルが必要であるクな IP を割り当てる必要がある。P2P ノードのアドレスはが、今までのグリッド用ミドルウェアに比べればほとんど設この IP アドレスの SHA-1 ハッシュ (160bit) である。送信定することなしに運用が開始できると考えられる。もとのホストのアプリケーションは IP ベースのトラフィックを tap に対して発生する。IPOP により、イーサネットフ 2.3.2 使い方のシナリオ WOW のゴールとしては、あらかじめ設定済みの VM イレームから IP パケットが抽出され、P2P のパケットでカプメージをインストールするだけで、プールされたグリッド資セル化される。つまり、IP アドレスから P2P の 160bit の源を利用できるようにすることである。WOW はリソースの SHA-1 ハッシュに変換される。P2P パケットがあて先のホストに届くと、IP パケットは再びイーサネットフレームに入れられ、tap を通じて、アプリケーションへ届けられる。追加を管理上のオーバヘッドをほとんど押し付けることなし 2.2.3 ファイアウォール/NAT を超えた通信現在一般に使われている NAT では、IP アドレス A のポート pA から IP アドレス B のポート pB へ UDP パケットが送られ、エントリーが追加されると、逆に B:pB から A:pA への通信が可能になる (NAT ホールパンチング。図 4)。また、 P2P ネットワークは通信をある程度続けるうち、NAT により IP の変換が行われていることを知ることができるため、その情報を P2P ネットワーク内で広告することで、各ノードがそれを知ることができる。NAT 超えのプロトコルは STUN で使われているものをもとにしているが、STUN とは違い、る巨大な計算資源によって恩恵を受けやすいため、WOW がスが source であるようなイーサネットフレームに入れられ、ホストへと届けられる。 2.2.2 P2P オーバレイネットワークにおける IP ルーティング IPOP ネットワークにホストを追加するには、システム管に、完全に分散化された方法で行える。ハイスループットコンピューティングは WOW が提供す応用例として最も適当であると考えられる。また、通信の少ない並列アプリケーションも WOW によって、恩恵を受けることができる。さらに、WOW の設計では、複数のユーザが利用する環境でバッチスケジュラを使うのにも適した環境を提供する。 2.4 WOW のオーバレイコネクション管理 WOW は新しく参加するノードに対して、オーバレイリンクを自己構成するように設計されている。ここでは WOW の適応的仮想 IP ネットワークシステムについて述べる。このような仕組みは Brunet P2P によって提供されるユーザレベルフレームワークによって構築されている。WOW はシングルホップ (LAN のような) オーバーレイネットワークを構築するために、Brunet と IPOP を用いている。この節では Brunet P2P システムがどのようにオーバレイ専用のサーバを使わずに、分散された手法に改良されている。 2.3 WOW の設定と配備 2.3.1 VM の設定 WOW はクラスタ計算環境と同じ性質をもつような環境を提供するので、WOW の設定は多くの管理者にとってほとんコネクションを扱うかを述べる。すなわち、新しくノードがどの部分がすでによく慣れた手続きである。ベースとなる計追加するときのプロトコルや、NAT の後ろにいるノードとの 3 接続の確立、通信量の監視にもとづくショートカット接続の分散生成について述べる。 2.4.1 Brunet P2P Brunet は 160bit のアドレス順に並んだリングを構築する。各ノードは P2P アドレス空間において最も近い 2 つのノードとの接続を張る (structured near connections)。また、各ノードはそれ以外の k ノードに対して接続を張る (structured far connections)。k をコンスタントとすると平均オーバレイホップ数はネットワークのサイズを n として 1 O( log2 (n)) k であることが示されている。 n4 n3 n5 図6 n6 n2 Connection Setup 1. Connection Protocol: コネクションプロトコルに従い、ノードはコネクションをセットアップしたいという意図 n1 Multi hop path from n1 to n7 と、URI のリストを相手のノードに伝える。まず、コネ n7 クションを張りたいノードは CTM (Connect To Me) リクエストを相手ノードへ送る。CTM リクエストにはそのノードの URI のリストが含まれている。メッセージ n8 n12 は P2P ネットワーク上をルーティングされ、あて先ノードへ届くとあて先ノードは CTM リプライを元のノード n11 n10 へ返信する。CTM リプライにも同様にリプライを送信 n9 したノードの URI のリストが含まれている。CTM リプライを送信したノードはその後、次に述べるリンキングプロトコルを開始する。また、最初のノードは CTM リプライを受け取ると、同様にリンキングプロトコルを開図 5 Greedy Routing 始する。 2. Linking Protocol: P2P ノードは CTM リクエストを受け取るか、CTM リクエストを送信した相手から CTM Brunet はこれらの接続を用いて、図 5 のようなグリーディルーティングを行う。すなわち、あて先ノードに P2P アドレリプライを受け取るとリンキングプロトコルを開始すス空間上で最も近いノードへ転送する。パケットは最終的にる。なお、ノードは CTM リクエスト・CTM リプライあて先ノードに届くか、または、あて先ノードがダウンしてから、相手の URI は分かっている。ノードはプロトコルいた場合は、アドレス空間上で最も近い 2 つのノードへ届く。を開始すると、実ネットワーク上で URI に対して一連の Brunet ノード間のコネクションは抽象化され、いくつかの種類のプロトコル (TCP や UDP など) 上で実現される。そのようなプロトコルの情報とエンドポイントの情報 (IP アドレスとポート番号) は URI (Uniform Resource Indicator) に含められる (たとえば brunet.TCP:18.52.0.0.1:1024 など)。リンクリクエストメッセージを送信することで、ハンドシェイクを試みる。相手のノードは単純に実ネットワーク上でそれに答える。一連のハンドシェイクが行われると、新しい接続として登録し、プロトコルが完了する。また、ノードはいくつかのネットワークインターフェースを確立された接続でははときどき ping-pong が行われる。ももっていたり、NAT の中にあったりして URI を複数持つ可し、ping に答えない接続があったとすると、それは相手が能性がある。現在の実装では TCP と UDP が仮想の通信プダウンしたか、ネットワークが非連結になったとみなされ、ロトコルとして利用可能である。ノードは接続を破棄する。これらの ping メッセージはバン 2.4.2 接続のセットアップすでに P2P ネットワークに参加している 2 ノード間で新しく接続を確立するには、以下の 2 つのプロトコルに従う (Figure. 6)。ド幅や計算性能にオーバヘッドを招くので、ひとつのノードが保持できる接続の数はある程度制限されることになる。リンキングプロトコルが両方のピアーによって開始されると、片方が成功し、他方が失敗するようにすべき競合状態に 4 なることがある。そのため、各ノードは今どのノードと接続れぞれのノードが互いにハンドシェイクメッセージが送受信を試みているか覚えておく必要がある。もし、現在接続要求できるまで接続を試す。ある決まった回数接続ができなかっを送ったノードがターゲットのノードから接続要求を受け取たら、別の URI に対して同様に数回の試行を行う。ると、エラーメッセージを送る。両方のノードにエラーメッ 2.4.5 適応的なショートカット生成セージが届いて、いずれも接続が失敗することがあるが、この場合は、再び競合が起きないように、試行回数の指数時間だけ待機して再度試行を行う。 2.4.3 ネットワークへの参加と接続の獲得新しい P2P ノードはすでにネットワークに参加しているノードの URI によって初期化を行う。新しいノードは初期ノードの中のひとつと直接リンキングプロトコルを用いて、 leaf コネクションと呼ばれる接続を生成する。初期ノードはグローバル IP を持ち、ファイアウォールのないネットワーク上にいる必要がある。新しいノードがもし、NAT の向こう側にいたとすると、初期ノードは NAT に割り当てられた IP/port と一致した URI を P2P ネットワーク上で広告する。leaf コネクションが確立されると、leaf ターゲット (新しいノードから接続を張られたノード) は新しいノードへメッセージを転送する役割を担う。この時点では、新しいノードの URI あてのメッセージがそのノードへ届くことは保障さ図 7 Distribution of round-trip latencies for れていない。 ICMP/ping packets 次に、新しいノードはリング構造の中で自分がいるべき正しい場所を探し、near コネクションを張りに行くことになる。新しいノードは CTM リクエストを自身のアドレスあて図 7 のようにレイテンシが最も多い場合で 1600ms であるに leaf ターゲットを通じて P2P ネットワークに送り出す。ことが分かった。このような大きなレイテンシはオーバレイ CTM リクエストはネットワーク上をルーティングされ、新しいノードの隣接ノードになるべきノードへ届く (新しいノードがまだリングに入っていないため)。leaf ターゲットによって受け取られる返ってきた CTM リプライは新しいノードへネットワークにおいて複数回ホップしてルーティングされる転送される。よって、このノードは自分の隣接ノードとなる Brunet ライブラリでは開発者が新しいルーティングアルべき 2 つのノードの URI を知ることができたので、near コゴリズムや接続のタイプを加えることを可能にしてある。まネクションを確立することができる。この時点でノードは完た、各ノードはコネクションを何本保持しているかを管理す全にネットワークに参加できたことになる。るコネクション管理者を持つ。ために起きると考えられる。この節では、通信量に応じてシングルホップのリンクをセットアップするための分散化された適応的なショートカット生成について述べる。各ノードは他のノードとの通信について score という基準 2.4.4 NAT 越えを使う。アルゴリズムとしてはキューイングシステムをもと前にも述べたように、NAT の内側にいるノードは複数の URI(プライベートな IP/port とグローバルネットワークにいるノードと通信するときに用いられる NAT に割り当てられた IP/port) を持つ。はじめは、NAT の内側にいるノードは自身のグローバルな IP/port を知ることはできないがにしている。時間をあるインターバルに分けて、時間ユニットの i 番目に届いたパケットの数を ai とする。ノードはあるコンスタントな数 c でサービスを行うものとする。時間 i での score を si とすると、si を漸化式で定義する。グローバルネットワークにいるノードと通信をすることで、 si+1 = max(si + ai − c, 0) NAT に割り当てられた IP/port を知ることができる。また、すべての URI に対して、通信が行えるわけではない。どの URI が使えるかは相手ノードの場所と NAT の性質による。二つのノードが両方ともヘアピン NAT の内側にいる場合には、両方の URI を通信に用いることができる。 Brunet は UDP 通信を用いた実装もなされているので、両方のノードが別々の NAT の内側にいる場合には前に述べた NAT ホールパンチングを用いて通信を行う。NAT やファイアウォールのために、いくつかのノードは URI のすべてが接 score は仮想キューにたまっている仕事の量を表し、score が高いほど、そのノードでは通信がたくさん行われていることになる。各あて先ノードの仮想キューに最も仕事がたまっているノードがコネクションを張るべき相手である。コネクション管理者は si がある閾値を超えたら、ショートカットコネクションを張る。しかしながら、他のすべてのノードに対してショートカットを作ってしまっては、大きなネットワークにおいては、コ続不可能である可能性がある。リンキングプロトコルではそネクションを保持することにより、バンド幅や計算に対する 5 大きなオーバヘッドを引き起こす。そのため、ショートカットの数に制限を設け、使われなくなったショートカットは削除する。 3 実験 3.1 実験環境 Hosts: 2.4GHz Xeon, Linux 2.4.20, VMware GSX Hosts: 2.0 GHz Xeon, Linux 2.4.20, VMware GSX Host: 1.3GHz P-III Linux 2.4.21 VMPlayer 図 9 Latencys Average Host: 1.7GHz P4, Win XP SP2, VMPlayer 図 8 Experiments Environment 実験は図 8 のような環境で行われた。Debian/Linux ベースの OS で設定された (すなわち、均一なソフトウェア環境)33 個の VM を仮想クラスタに配置する。これらの VM が配置された環境ははホスト OS(Linux と Windows) や VM モニターがばらばらであり、異なるファイアウォールポリシーの異なるネットワークドメインに属している。PlanetLab に属する 118 ノードはファイアウォール内のノードがつなげるように、グローバルでファイアウォールがないようなノードであり、”bootstrap” ノードとして用いられる。また、これらの PlanetLab のノードはオーバレイネットワークでルー図 10 ティングが行えるように IPOP ネットワークを構築している Percentage of lost packets が、パケットを取り込んだり、送り出したりはしない。 3.2 ショートカットによるレイテンシとバンド幅の変化ショートカットを生成することによるレイテンシとバンド幅の改善を調べるために、次のような実験を行った。ノード’A’ を uﬂ.edu ドメインに属するあるノードであるとするとき、以降のような処理を繰り返した。 1. northwestern.edu ドメインに属するノードのひとつを ‘B‘とし、IPOP ネットワークへの参加プロトコルを行う 2. B から A へ 1 秒間隔で 400 個の ICMP echo パケットを送信する。 3. B を IPOP から脱退させる。このような繰り返しを異なる 10 個の A,B に対して行った (計 100 回)。また、A,B を uﬂ.edu-uﬂ.edu と、northwestern.edunorthwestern.edu の組み合わせに対しても同様の実験を行った。図 11 Percentage of lost packets on the uﬂ.edunorthwestern.edu 図 9、10 が結果のグラフである。また、uﬂ.edu- northwestern.edu の組み合わせに対しては、はじめの 50 パケットまでの詳しいグラフを作成した (Figure. 11)。この 6 組み合わせでは 3 つの異なる状態が観測された。3 つの状態ンド幅が得られた。とは、 3.3 アプリケーションの実行 WOW では修正なしで、クラスタ計算用のミドルウェアや 1. B がまだ P2P ネットワークに参加を完了していない状態 2. B へルーティングが行われるようになり、もしかするとアプリケーションが使えるので、それについての実験を行った。ミドルウェアとしては PVM を用い、アプリケーションショートカットが生成された状態としては、FastDNAml を用いた、FastDNAml とは DNA 鎖 3. ショートカットが生成された状態から系統発生の木の最尤推定を行うというアプリケーション状態 1 ではパケットロス率が 90% 以上の場合である。この 3 である。PVM ベースのマスタワーカモデルで並列化されて秒の間に B へのルートが生成されたことが分かる。状態 2 はおり、マスターはタスクのプールからタスクをワーカに動的パケットロス率が 1% まで落ちるまでである。このとき、レに割り当てるというものである。これは、通信に対して、非イテンシも 146ms から 43ms まで落ちる。P2P ネットワー常に計算が多く、動的にタスクを割り当てるために、ノードク上でルーティングが可能になり、さらに、ショートカット間の性能のヘテロ性は問題にならない。接続が確立された場合もあることが分かる。最後に 33 から 400 番のパケットが送られた状態 3 ではパケットロス率が 1% まで落ち、レイテンシは 38ms まで落ちる。ショートカット接続が確立されたことを示していると考えられる。表2 uﬂ.edu-uﬂ.edu 間の場合は 3 つの状態が観測された。40 パ Execution Times ケット目くらいまでにはノードはルーティング可能になり、 200 パケット目くらいにショートカットが確立されたと考えられる。この大きな遅れはこのドメインの NAT と現在の実装に起因する。このドメインの NAT はヘアピン変換をサポートしていない。すなわち、NAT の中からは NAT の外側に割り当てられた IP/port に対して通信を行えない。前に述べたように、ハンドシェイクはひとつひとつ URI を試して結果は表 2 のようになった。30 ノードでショートカットありの場合はなしの場合に比べ、24% 速くなった。FastDNAml は通信に対して、非常に計算が多いために、ショートカットがあっても大きな性能改善は見られなかった。現時点での最もよい木を選ぶために、同期何度もとることが実行速度が遅くなる原因であると説明できる。ゆき、メッセージの送受信が行えるまで探し続ける。よって、逐次実行で Node 2 と Node 34 を示したのは各ノードにはこの遅延は一度失敗したときの待ち時間と UDP ホールパン性能差があることを示すためである。ネットワーク中で最もチングを試して見ることにより、接続をあきらめ、成功する平均的な性能である Node 2 を基準として、並列化の速度向プライベート URI を試すまでに大きく時間を割いてしまっ上を計算してみると 13.6 倍であった。均一なクラスタ環境たためであると考えられる。では 23 倍の速度向上があったことが先行研究では報告され northwestern.edu-northwestern.edu のケースでは NAT がヘアピン変換をサポートしていたため、どちらの URI ている。でも通信が行える。よって、一度目のショートカット作成で 4 成功し、約 20 パケット目くらいまでにショートカットが確立したことが分かる。終わりに本サーベイでは、WOW および IPOP を紹介した。WOW では VM イメージと VM モニター・IPOP が必要とされるのみで、VM イメージは一度ベースとなるものを作ってしまえば、それをコピーするのみですべてのノードにセットアップができる。また、IPOP によるオーバレイネットワークは NAT/ファイアウォールによる通信の妨害を隠し、また、動的表 1 Average Bandwidth なノードの追加を可能にした。実験においては異なるドメイン間で 3 秒程度でノードの追加が行われ、40 秒程度でショーまた、表 1 のようにバンド幅の測定を行った。バンド幅のトカットが作成されることが示された。また、通信に対して変化には二つの要因がある。ひとつは、二つのノード間での計算がインテンシブなアプリケーションにおいて、クラスタルーティングされるパスのバンド幅、もうひとつは、中間で環境と比べ、2 分の 1 程度の並列化の性能が得られることがルーティングを行う IPOP ルータの負荷である。ショート示された。カットなしでは 3 ホップ程度のルーティングが行われてお今後の課題としては、このようなヘテロな環境でもユーザり、負荷が高いノードが間に入ってしまったために、非常ににとって使いやすい (設定が楽、今までのミドルウェア、アプ小さなバンド幅が計測された。一方、ショートカットを作成リケーションが利用可能) ようなミドルウェアについて研究した場合には、間に IPOP ルータを挟まないため、大きなバを進めていきたい。 7 参考文献 [1] Arijit Ganguly, Abhishek Agrawal, P. Oscar Boykin, and Renato Figueiredo. IP over P2P: Enabling selfconﬁguring virtual IP networks for grid computing. In Proceedings of International Parallel and Distributed Processing Symposium (IPDPS). To appear, Apr 2006. cs.DC/0603087. [2] Arijit Ganguly, Abhishek Agrawal, P. Oscar Boykin, and Renato Figueiredo. WOW: Self-organizing wide area overlay networks of virtual workstations. In Proceedings of the 15th IEEE International Symposium on High Performance Distributed Computing (HPDC), pages 30–41, June 2006. [3] Mauricio Tsugawa and Jose A. B. Fortes. A virtual network (vine) architecture for grid computing. In Proceedings of International Parallel and Distributed Processing Symposium (IPDPS). To appear, April 2006. [4] 立薗真樹, 中田秀基, and 松岡聡. 仮想計算機を用いたグリッド上での MPI 実行環境. In 先進的計算基盤システムシンポジウム SACSIS2006, pages 525–532, May 2006. 8