(57)【特許請求の範囲】
【請求項１】
仮想空間を形成するためのマルチノード・サーバシステムであって、前記マルチノード・サーバシステムは、
前記仮想空間を分割する複数のメッシュをそれぞれ処理する複数のサーバを相互接続して構成され、前記メッシュごとの処理結果を前記仮想空間として表示するアプリケーション実行手段と、
ネットワークを介したクライアントからのリクエストに応答して変化する前記アプリケーション実行手段の前記サーバの負荷状態を検出し、メッシュの移動処理のための処理オーバーヘッドに関する目的関数を最小化させるようにサーバシステム内の資源配分を分散することによって前記サーバシステムで前記メッシュを処理するべき前記サーバの割当てを変更するリソース管理手段と、
ネットワークを介して前記仮想空間を複数のクライアントに共有させるネットワーク手段と
を含み、前記リソース管理手段は、前記メッシュを処理する前記サーバとは異なるサーバにより処理される前記メッシュとの境界として定義されるサーバ境界を挟んで隣接するメッシュを処理する前記異なるサーバの処理を前記サーバに繰り込むことにより、前記隣接するメッシュ間での通信を同一のサーバ内での通信として前記資源配分を分散させる、マルチノード・サーバシステム。
【請求項２】
前記リソース管理手段は、異なるサーバ間でのメッシュ間通信、ＣＰＵ負荷、前記サーバのメモリ利用率、割当てを変更するメッシュの総数を含む目的関数を最小化するメッシュ集合を生成し、前記メッシュ集合にしたがって前記サーバの割当を変更するための目的関数最小化手段を含む、請求項１に記載のマルチノード・サーバシステム。
【請求項３】
前記リソース管理手段は、前記サーバ間での前記メッシュ間通信が単一サーバ内でのノード内通信となるように前記サーバ境界を変更することにより割当てを変更する、請求項２に記載のマルチノード・サーバシステム。
【請求項４】
前記マルチノード・サーバシステムは、前記サーバの割当てを変更するメッシュを指定した後、割当変更対象メッシュについて少なくともメッシュ移動処理のためのプロセス以外のクライアントおよび他のサーバによる書込みアクセスを排他制御する排他制御手段を含む、請求項１に記載のマルチノード・サーバシステム。
【請求項５】
前記サーバは、当該サーバが処理対象とするメッシュ識別値、前記メッシュを固有に識別するアドレス、前記メッシュが使用するリソース・データを、前記メッシュの割当て変更に応答して追加削除して更新するメッシュ管理手段を含み、
前記リソース管理手段は、定期的に前記複数のサーバの前記メッシュ間通信、前記ＣＰＵ負荷、前記サーバのメモリ利用率を検出し、前記目的関数を最小化する前記メッシュ集合を、最新の最適配置データとして登録する最適配置データ登録手段を含む、請求項２に記載のマルチノード・サーバシステム。
【請求項６】
前記マルチノード・サーバシステムは、ゲーム・サーバであり、割当て変更の対象とされる前記メッシュにアクセスしているクライアントを除く、他のクライアントについて前記仮想空間の全メッシュの前記リソース・データの読出処理を可能に保持する、請求項５に記載のマルチノード・サーバシステム。
【請求項７】
相互接続された複数のサーバ間の負荷を分散させ仮想空間を提供するマルチノード・サーバシステムにおける負荷分散方法であって、前記負荷分散方法は、前記マルチノード・サーバシステムが実行する負荷分散方法であって、
相互接続された複数のサーバに対し、前記仮想空間を分割するメッシュを、前記サーバが処理すべきメッシュとして割当てるステップと、
ネットワークを介したクライアントからのリクエストに応答して変化する前記メッシュのアプリケーションの処理により発生した前記サーバの負荷状態を検出するステップと、
メッシュの移動処理のための処理オーバーヘッドに関する目的関数を最小化させるようにサーバシステム内の資源配分を分散させることによって、前記サーバシステム内で前記メッシュを処理するべき前記サーバの割当てを変更するステップと、
ネットワークを介して前記仮想空間を複数のクライアントに共有させるステップと
を含み、前記サーバの割当てを変更するステップは、
前記メッシュを処理する前記サーバとは異なるサーバにより処理される前記メッシュとの境界として定義されるサーバ境界を挟んで隣接するメッシュを選択するステップと、
選択した隣接するメッシュを処理する前記異なるサーバの処理を前記サーバに繰り込むステップとを含む、負荷分散方法。
【請求項８】
前記サーバの前記負荷状態を検出するステップは、異なるサーバ間でのメッシュ間通信、ＣＰＵ負荷、前記サーバのメモリ利用率、割当てを変更するメッシュの総数を含む目的関数を最小化するように前記割当てを変更するべきメッシュを決定するステップを含む、請求項７に記載の負荷分散方法。
【請求項９】
前記サーバの割当てを修正するステップは、前記サーバ間での前記メッシュ間通信が単一サーバ内でのノード内通信となるように前記サーバ境界を変更するステップを含む、請求項８に記載の負荷分散方法。
【請求項１０】
さらに、当該サーバが処理対象とする前記メッシュの識別値、前記メッシュを固有に識別するアドレス、前記メッシュが使用するリソース・データを、前記メッシュの割当て変更に応答して追加削除して更新するステップと、
定期的に前記複数のサーバのメッシュ間通信、ＣＰＵ負荷、前記サーバのメモリ利用率を検出し、前記目的関数を最小化するメッシュ集合を最新の最適配置データとして登録するステップと
を含む、請求項９に記載の負荷分散方法。
【請求項１１】
前記マルチノード・サーバシステムは、ゲーム・サーバであり、さらに、
前記サーバの割当てを変更するメッシュを指定した後、割当変更対象メッシュについて少なくともメッシュ移動処理のためのプロセス以外のクライアントおよび他のサーバによる書込みアクセスを排他制御するステップと、
割当て変更の対象とされる前記メッシュにアクセスしているクライアントを除く、他のクライアントについて前記仮想空間の全メッシュの前記リソース・データの読出し処理を可能に保持するステップと
を含む、請求項１０に記載の負荷分散方法。
【請求項１２】
請求項７〜請求項１１のいずれか１項に記載の各ステップをマルチノード・サーバシステムを構成するコンピュータが実行するための、コンピュータ実行可能なプログラム。
【請求項１３】
仮想空間を形成するためのマルチノード・サーバシステムのためのリソース管理サーバであって、前記リソース管理サーバは、
前記仮想空間を分割する複数のメッシュをそれぞれ処理する複数のサーバを相互接続して構成され、前記メッシュごとの処理結果を前記仮想空間として表示するアプリケーション実行手段を実行させる前記サーバのネットワークを介したクライアントからのリクエストに応答して変化する負荷状態を検出する負荷状態検出手段と、
前記サーバの割当てを変更するべきメッシュの移動候補集合を、前記メッシュを処理する前記サーバが異なる隣接する複数のメッシュにより規定される境界メッシュを選択して生成する移動候補集合生成手段と、
メッシュの移動処理のための処理オーバーヘッドを最小化させるように、異なるサーバ間でのメッシュ間通信を聴取し、ＣＰＵ負荷、前記サーバのメモリ利用率、割当てを変更するメッシュの総数を含む目的関数を最小化するメッシュ集合を生成する、目的関数最小化手段と、
前記メッシュ集合を前記メッシュの最新の最適配置データとして登録する最適配置データ登録手段とを含み、
前記リソース管理サーバは、前記メッシュを処理する前記サーバとは異なるサーバにより処理される前記メッシュとの境界として定義されるサーバ境界を挟んで隣接するメッシュを処理する前記異なるサーバの処理を前記サーバに繰り込むことにより、前記隣接するメッシュ間での通信を同一のサーバ内での通信としてサーバシステムの資源配分を分散させる、リソース管理サーバ。
【請求項１４】
前記リソース管理サーバは、サーバ間での前記メッシュ間通信がサーバ内でのノード内通信となるように前記サーバ境界を変更することにより割当てを変更する、請求項１３に記載のリソース管理サーバ。
【請求項１５】
請求項１３または１４に記載の各手段をコンピュータに実現するためのコンピュータ実行可能なプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の情報処理装置におけるマルチノード・サーバシステム、マルチノード・サーバシステムの負荷分散方法、およびプログラムに関し、より詳細には、複数のサーバ装置を使用して連携した処理を特定のクライアント装置に提供する、マルチノード・サーバシステム、マルチノード・サーバシステムの負荷分散方法、リソース管理サーバ、およびプログラムに関する。
【背景技術】
【０００２】
近年、ネットワーク技術およびコンピュータ技術の進歩により、ネットワークを介した複数のクライアント装置への情報提供、ＣＧＩ(Common Gateway Interface)、Ｓｅｒｖｌｅｔ、ゲーム・アプリケーション、その他のサーバ・アプリケーションを使用したサービス提供などが普及している。サーバ装置は、複数のクライアント装置から不規則かつ予測困難なタイミングでアクセスを受け、各クライアント装置の要求に適合した処理を実行し、実行結果を各クライアント装置に返す必要がある。
【０００３】
また、サーバによるサービス提供も多岐にわたってきており、サーバは、情報検索サービス、ブラウジング・サービス、ゲーム・アミューズメント提供サービスなどのサービスを行っている。このうち、ゲーム・アミューズメント提供サービスは、プレイヤーがそれぞれ固有の画面でゲームプレイを行う、スタンドアロン形のゲームから、多くのプレイヤーがゲーム・サーバに同時接続し、各プレイヤーが巨大な仮想空間を共有してコラボレーション下で連携したゲームを進行させて行くタイプのゲームが登場している。
【０００４】
上述したゲーム・アミューズメント提供サービスを行うゲーム・サーバは、情報検索、ブラウジング・サービスなどを提供するサーバとは異なる処理環境に曝されることになる。すなわち、情報検索やブラウジング・サービスを行うサーバ装置は、クライアントからの要求に対応してスレッドなどを割当て、その処理結果を単に要求元のクライアントに返す処理を行う。この場合、他のクライアントとの間のコラボレーションが行われる場合があることも想定されるが、全部または大多数のクライアントに対してコラボレーション下での処理結果を返す処理は、極めて希なケースということができる。
【０００５】
一方、ゲーム・サーバは、多数のプレイヤーが参加して、ゲーム空間といった仮想空間内で、例えば対戦、生活、投資などのゲーム・アプリケーションの処理結果を、プレイヤーそれぞれをコラボレーションさせながらクライアントに表示する必要がある。さらに、近年ではゲーム内容がますます複雑多様化し、さらに同時接続するユーザ数も増加するなど、ゲーム環境の大規模化に伴い、サーバ側の処理がますます複雑、かつ高速性・高信頼性が要求されるようになっている。
【０００６】
上述した処理負荷や、ネットワーク環境の多様化、さらにサーバダウン時のバックアップ、サーバ拡張性などのメンテナンス性の観点から複数のサーバをＬＡＮ(Local Area Network)で相互接続し、サーバをＬＡＮノードとして、サーバ・ノードを相互接続して構成することも行われている。
【０００７】
ゲーム・サーバが複数台のサーバ・ノードから構成される場合、サーバ内の通信よりも、ＬＡＮを介した通信速度は、ネットワーク・インタフェース・ボード（ＮＩＣ）などにもよるが１Ｇｂｐｓ以下の伝送レートとなり、サーバ内部での伝送レートよりも伝送効率が低下する。また、ＬＡＮは、サーバ間のアプリケーション処理以外にも、ハブ、ルータ、ＤＮＳサーバなどを介したネットワーク通信のための情報通信なども処理する。一方、ＬＡＮを構成するネットワーク基盤の伝送レートが引上げられても、それに伴いＬＡＮを経由して送受信されるデータも増加するので、アプリケーション実行のために必要なデータ通信の伝送効率を改善することにはつながらないという問題点がある。
【０００８】
すなわち、複数台のサーバをＬＡＮノードとして接続した場合、アプリケーション実行に関連するデータ伝送を効率化しなければ、複数台のサーバをＬＡＮで相互接続して構成される、いわゆる、マルチノード・サーバシステムの処理効率を効率的に向上させることができないという問題がある。
【０００９】
一方、ゲーム・アミューズメントなどのアプリケーションの場合、仮想空間内の特定領域（以下、メッシュとして参照する。）の混雑具合は、時間、ゲームの進行度合い、ユーザの好み、ゲーム内容によって常に変動する。このため、サーバ・ノード間でどのように計算資源を分配するかが大きな問題となる。計算資源をサーバ・ノード間で適切に分配しない場合、単一のサーバ・ノードで処理可能な限界性能（同時接続可能なプレイヤー数など）が、プレイヤーの要求に対応することができず、いわゆる処理落ちが発生し、ゲームなどの処理に不都合が発生する。
【００１０】
また、単独サーバ内でのデータ伝送であれば各メッシュ間のコラボレーションには充分対応できる性能を有している場合であってもＬＡＮのデータ輻輳により、メッシュ間の通信効率が低下する場合も想定でき、仮想空間内でのコラボレーションが妨げられたり、データが損失してしまうなどの問題も発生する。
【００１１】
一方、ゲーム状態を保持させながら計算資源の配置を変更する場合には、処理可能なサーバ・ノードの選択や、計算資源の割当てなどの処理のための時間が必要となる。また、仮想空間にアクセスするクライアントは、同時に同一のメッシュ近傍にアクセスするとは限らず、計算機資源の再配置を行う場合、処理負荷がオーバーフローに近いメッシュやサーバが存在することで、処理量が高くないメッシュ近傍にアクセスするクライアントへの応答性が制限されるという不都合も発生する。
【００１２】
これまで、複数のプレイヤーによるゲームを可能とするゲーム・システムが知られている。例えば、特開２００５−２３４６３３号公報（特許文献１）では、複数のサーバによりそれぞれサービスが提供され、これらのサービスにより仮想的な世界を自由に構築・連結し、仮想的な世界の間の移動を自由にさせるサービスの拡張方法が知られている。特許文献１では、結合した仮想的な世界を構築しつつ、所定の単位でその処理を各サーバに分散し、その結果をクライアントに提供するものである。特許文献１は、サーバに対して仮想コミュニティを割当て、クライアントがサーバに設定したインタフェースを超えた場合に、新たな仮想コミュニティを管理するサーバにクライアントについての情報を渡して、新たな仮想コミュニティでの処理を可能とするものである。
【００１３】
しかしながら、特許文献１は、サーバに対して特定の仮想コミュニティが割当てられ、クライアントが移動先の仮想コミュニティを決定することにより、処理を担当するサーバが決定されてしまう。このため、特許文献１は、仮想コミュニティの混雑ぶりに対応して処理担当のサーバを変更することはできない。この他、特開平９−３２５９９１号公報（特許文献２）は、参加者数を増やすことを可能とし、仮想世界を領域に分断した際の違和感を低減するため、隣接する領域にそれぞれサーバを配置し、小領域が隣接した領域間で重なるように設定することを開示している。
【００１４】
また、特開平１１−０３９４７２号公報（特許文献３）は、固定点と新規のユーザの位置との間の距離に応じてユーザに空間およびサーバを割当てることで、ユーザの移動時に要求される衝突検査などの計算量を低減する処理を開示している。特開平１１−２８８３９４号公報（特許文献４）は、ゲームへの参加者の数が多くなるにつれてゲーム・サーバ間のデータ交換量が増大する難点を解消するため、ゲーム端末間の通信距離に応じてメッセージをやりとりできるゲーム端末を限定する処理を開示している。さらに、特開平１１−３２８１２４号公報（特許文献５）は、仮想空間表示システムで、仮想空間をレンダリングする負担を軽減させる処理を開示し、特開２０００−２８５０６４号公報（特許文献６）は、利用者情報データベースを設け、仮想空間サービスにおいて利用者およびキャラクタの単一性を保証し、操作性を向上させる処理を開示している。
【特許文献１】特開２００５−２３４６３３号公報
【特許文献２】特開平９−３２５９９１号公報
【特許文献３】特開平１１−０３９４７２号公報
【特許文献４】特開平１１−２８８３９４号公報
【特許文献５】特開平１１−３２８１２４号公報
【特許文献６】特開２０００−２８５０６４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１５】
上述したように、複数のサーバを使用して仮想空間を提供するシステムは、複数開示されている。しかしながら、複数のサーバにより提供される仮想空間のメッシュの処理において、各サーバの資源を効率的に分配することにより、クライアント増加やメッシュ内処理のオーバーヘッドに対応できるように、複数のサーバのハードウェア資源を分配することを可能とするマルチノード・サーバシステム、マルチノード・サーバシステムの負荷分散方法、リソース管理サーバ、およびプログラムが必要とされていた。
【００１６】
また、仮想空間に参加するクライアントの数が、時間、嗜好性、仮想空間の内容によって常時変動する環境下で、特定のクライアントに対する処理が不能となる、いわゆる「処理落ち」の不都合の発生を最低化させることにより信頼性を向上した、マルチノード・サーバシステムの負荷分散方法、リソース管理サーバ、およびプログラムが必要とされていた。
【００１７】
さらに、複数のサーバにより構築されるマルチノード・サーバシステムの資源を有効利用すると共にサーバ・システムの最大処理量が特定のサーバの処理能力に制限されてしまうことがないように、負荷を分散させ、マルチノード・サーバシステムの処理効率を最大化させる、マルチノード・サーバシステムの負荷分散方法、リソース管理サーバ、およびプログラムが必要とされていた。
【課題を解決するための手段】
【００１８】
本発明は、上述した従来技術の課題に鑑みてなされたものである。本発明では、仮想空間に対して複数の領域（メッシュ）を割当て、仮想空間を隣接するメッシュに分割する。そして、特定のサーバに対してメッシュ単位でアプリケーションを実行するためのリソースを割当てる。サーバ間の負荷分配は、メッシュが消費するハードウェア資源の利用状態を定期的にモニタリングし、それらの実測値に基づいて、当該メッシュの処理を担当するサーバを選択して変更する。
【００１９】
さらに、本発明では、メッシュを処理するサーバを再配置する場合、再配置に伴う時間的中断、メッシュの割当て変更に関連しないメッシュにアクセスするクライアントへの負担、システム性能などの再配置コストを含めて複数のサーバ間で最適なメッシュ割当てをオートノミックに決定する。すなわち、本発明では、複数のサーバによる最適効率の処理を可能とし、システムパーフォマンスを最適化するように、マルチノード・サーバシステムが、対象メッシュに割当てるサーバを変更することで、
【００２０】
サーバが処理対象とするメッシュは、ＬＡＮを経由したメッシュ間通信がデータ伝送を制限している場合、ＬＡＮ経由ではなく、メッシュ間通信がサーバ内のプロセス間通信などとなるように、処理サーバが異なる隣接メッシュのメッシュ境界を含む境界メッシュを選択し、メッシュ間通信がノード内通信となるようにメッシュ処理を担当するサーバ割当てを修正する。また、ＣＰＵ負荷、メモリ利用率などのサーバ能力によりアプリケーションの実行が制限される可能性がある場合には、境界メッシュから順次移動対象となるメッシュを選択し、例えば、最も処理負荷の低いサーバに、処理負荷の高いメッシュの処理を依頼するなど、目的関数の上限値を最小化させるように、サーバ割当てを修正する。
【００２１】
上述したサーバ割当ての変更のため、本発明では、負荷状態を示すパラメータおよびサーバ割当てを行う対象処理メッシュ総数を含む目的関数を使用する。目的関数は、ＣＰＵ負荷、メモリ利用率、メッシュ間通信量などのサーバの負荷状態の他、移動するべきメッシュの総数をパラメータとして含む。マルチノード・サーバシステムは、各パラメータが与える目的関数の上限値が最小となるように、メッシュ−サーバの割当てを反復的に選択して移動するべきメッシュを要素として含むメッシュ集合を生成し、このメッシュ集合を使用して最適配置データを計算し、メモリなどに格納しておく。サーバの負荷状態が設定したしきい値を超えた場合、移動処理プログラムが呼出され、最適配置データにしたがってマルチノード・サーバシステムを構成するサーバ割当てが変更される。
【００２２】
割当てが修正されるメッシュは、少なくとも書込み処理について排他処理制御され、サーバ割当てが進行中でも、割当てに関連しないメッシュにアクセスするクライアントは、自己がアクセスしているメッシュを含む仮想空間を使用してアプリケーション実行を継続することが可能とされる。このため、マルチノード・サーバシステムのリソース割当て変更に伴うクライアントへのアプリケーション提供サービスは、システムおよびクライアント側への負担に関連し、最小限のコストで実行できる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明を実施形態をもって説明するが、本発明は、後述する実施形態に限定されるものではない。図１は、本マルチノード・サーバシステムによる仮想空間のメッシュ分割の実施形態を示す。マルチノード・サーバシステムは、ネットワークを介して複数のクライアントがアクセスし、複数のクライアントに対して共通のアプリケーションによる処理を可能としている。アプリケーションとしては、仮想空間内で複数のクライアントがコラボレーション環境の下でプレイすることができる、マルチメディア・ディスプレイ、対戦型ゲーム、仮想生活ゲーム、投資シミュレーションゲームを挙げることができる。
【００２４】
なお、アプリケーションは、クライアントのディスプレイ画面上に２Ｄ、３Ｄなどの仮想空間を表示させ、当該仮想空間を複数のクライアントに共有させることができる限り、アプリケーション種類、処理内容には限定されるものではない。また、「クライアントによる仮想空間の共有」とは、クライアントが当該仮想空間にアクセスして何らかの処理を依頼することができる限り、ゲームが表示する仮想空間に限定されるものではなく、ディスプレイ画面上に表示される２Ｄ、３Ｄとして識別でき、それぞれにメッシュが割当てられる限り限定されるものではない。
【００２５】
以下、本明細書では、用語「サーバ・コンピュータ」を、ハードウェアおよびサーバ・ソフトウェアが連携してサービスを提供する情報処理装置として定義し、以下、単に「サーバ」として参照し、ローカルエリア・ネットワーク（ＬＡＮ）を構成する機能的要素としては、サーバを、「ノード」として参照する。また、本明細書では、用語「クライアント装置」を、サーバに対して遠隔的に接続され、サーバに対して処理要求を発行し、サーバによる処理結果を受領して処理を続行させる情報処理装置として定義し、以下、単に「クライアント」として参照する。
クライアントは、ユーザにより操作され、マルチノード・サーバシステムへとアプリケーションの処理を要求し、マルチノード・サーバシステムは、要求に対応する処理を実行して、クライアントのディスプレイ装置上に表示された仮想空間に処理結果を反映させて、応答する。
【００２６】
図１に示した仮想空間１００の実施形態では、ドライビング・ゲームなどのため、３Ｄ表示された仮想空間内に、道路１０２が表示されている。ユーザは、仮想空間１００の道路１０２上で、乗用車、スポーツカー、レーシングマシーンなどの車両を操作し、他のクライアントとの間でレースなどを行う。マルチノード・サーバシステムは、仮想空間１００を複数のメッシュに分割して、クライアントのディスプレイ画面上に表示させ、メッシュ内の処理をそれぞれ管理している。これらのメッシュは、図１に示す仮想空間１００では、交差するメッシュ境界１０４により示されていて、メッシュ境界１０４の内部に、単独のメッシュ１０６が規定される。
【００２７】
メッシュのサイズは、特に限定はないが、仮想空間１００内での画素数、仮想的距離、面積など、仮想空間１００を隙間なく分割することができる限り、いかなる基準の下で割当てることができる。また、メッシュ１０６内に移動してきたクライアントは、当該メッシュ内に割当てられたリソース・データを使用してアプリケーションを実行する。この目的から、メッシュには、ＲＡＭなどのメモリ領域を可変サイズで割当てて実装することができる。また、データの整合性などを確保するために、メッシュは、排他制御を可能とするフラグ、テーブル、セマフォなどを構造を伴っていてもよい。
【００２８】
マルチノード・サーバシステムは、メッシュ１０６単位で、処理を担当するサーバのＣＰＵ、メモリ、ユーザ・データ、表示オブジェクト・データなどを管理し、その処理を実行する。また、ユーザが隣接するメッシュに移動する場合には、隣接メッシュ間でユーザ・データ、表示オブジェクト・データなどを通信し、現在のメッシュから隣接メッシュへのアプリケーション処理の受渡しを行って、ユーザに対して違和感なく、ゲームなどの処理を継続させる。隣接するメッシュが同一のノードに割当てられる場合、メッシュ間通信は、プロセス間通信などにより実行され、隣接するメッシュが異なるノードに割当てられる場合、ＬＡＮを経由したＭＡＣ転送などを使用してメッシュ間通信を実行する。
【００２９】
図２は、本実施形態のマルチノード・サーバシステムの機能ブロック図である。マルチノード・サーバシステムは、複数のノード２０２、２０４、２０６、２０８、２１８をノードとし、複数のノードが、ＬＡＮにより接続されて構成されている。これらの複数のノードは、さらにブリッジ、スイッチ、ハブ、ルータなどのネットワーク機器を介して相互接続されている。ノード２０２、２０４、２０６、２０８、２１８は、ＣＰＵ、キャッシュ・メモリ、ＲＡＭ、ネットワーク・アダプタなどを含む従来知られた汎用サーバや、特定アプリケーションのために構成されるアプライアンス・サーバ、シンサーバなどを使用して構成することができる。
【００３０】
ノードを与えるサーバは、例えば、ＵＮＩＸ（登録商標）、ＬＩＮＵＸ（登録商標）、ＡＩＸ（登録商標）、Ｗｉｎｄｏｗｓ（登録商標）２００Ｘサーバなどのオペレーティング・システム（ＯＳ）を実行させ、各種のアプリケーションの処理に対応する。また、ＣＰＵとしては、ＰＯＷＥＲＰＣ（登録商標）などのＲＩＳＣアーキテクチャ、ＰＥＮＴＩＭ（登録商用）などのＣＩＳＣアーキテクチャを有する、シングルコア・プロセッサまたはマルチコア・プロセッサを使用することができ、メイン・キャッシュの他、適宜、Ｌ２キャッシュ、Ｌ３キャッシュなどを実装することができる。
【００３１】
図２に示すマルチノード・サーバシステムは、アプリケーション実行部２００と、アプリケーション実行部２００の計算機資源を管理するリソース管理手段として機能するリソース管理ノード２１８とを含んで構成されている。図１に示した実施形態では、アプリケーション実行部２００は、ノード２０２、ノード２０４、ノード２０６、ノード２０８により構成されている。また、各ノードは、ＬＡＮ２２６を介して相互通信しており、ネットワーク機器が管理するＭＡＣ(Media Access Control)アドレス・テーブルなどを参照して、各ノード間のデータ送信や通知を行っている。リソース管理ノード２１８は、アプリケーション実行部２００との間で、同様にＬＡＮにより接続されていて、アプリケーション実行部２００を構成するノードから、各種情報を収集し、また、ノードに対して資源配分を行うための情報を提供している。
【００３２】
ＬＡＮ２２６は、例えば１０００ＢＡＳＥ−Ｔ、１０００ＢＡＳＥ−ＴＸなどのＥｔｈｅｒｎｅｔ（登録商標）などの有線ＬＡＮ、ＩＥＥＥ８０２．Ｘなど無線ＬＡＮ、またはＢｌｕｅｔｏｏｔｈ（登録商標）、ＩｒＤａなどを利用して構成することができる。
【００３３】
アプリケーション実行部２００を構成するノード２０２、２０４、２０６、２０８は、図１に示した実施形態では、それぞれノード１、ノード２、・・・などのノード識別値が付与されている。ノード識別値は、ＭＡＣアドレスおよびＩＰアドレスなどを併用して付すことができ、ネットワーク上で固有に特定のノードを識別させている。なお、ＩＰアドレスをノードに割当てる場合、各ノードには、それぞれグローバルＩＰアドレスが割当てられ、ユーザからのアクセスが可能とされている。
【００３４】
図２に示す実施形態では、ノード２０２は、アプリケーションを実行するために、複数のメッシュ２１０、２１２、・・・を管理する。例えば、メッシュ２１０は、アプリケーションが提供する仮想空間１００に割当てられる図１に示したメッシュ１０６の処理を実行し、メッシュ１０６に割当てられる仮想空間領域の表示、ユーザ識別、オブジェクト表示処理、オブジェクト移動処理などを実行する。また、ノード２０２のメッシュ２１０は、特定の実施形態によっては、ホットスポットや隠しボタンなどの操作により、当たりや、特別ゲームの呼出し、特別アイテムなどの割当ておよび表示などの処理を実行する。
【００３５】
メッシュ２１０は、アプリケーション実行に際して、ノード２０２が、ハードディスク装置に登録されたリソース・データなどを、ＲＡＭなどにより提供される実行空間を割当てることにより生成される。各メッシュのメモリサイズは、メッシュ内での処理要求に対応してノード２０２が許容可能な割当てサイズまで可変設定され、例えばアプリケーションの要求に応じてノード２０２での処理のオーバーヘッドに許容範囲内で対応することが可能とされている。なお、アプリケーション実行部２００をウェブ・サーバとして実装する場合、各メッシュには、例えは、ＲＦＣ２６１６で規定されるＵＲＩ(Uniform Resource Identifier)またはＲＦＣ３９８６に規定されるＵＲＬ（Uniform Resource
Locator)が付されている。また、他の実施形態では、絶対パス名や相対パス名でメッシュを固有に識別することができる。
【００３６】
各ノードは、クライアントからＴＣＰ／ＩＰプロトコルやＵＤＰ／ＩＰプロトコルなどを使用してリクエストを受付け、メッシュ内での処理結果を、ＨＴＴＰレスポンスなどとして返すことが可能とされている。マルチノード・サーバシステムは、例示的にはウェブ・サーバ、ゲーム・サーバ、またはマルチメディア・サーバとして実装することができる。アプリケーション実行部２００がウェブ・サーバであれば、各ノードは、クライアントからHTMLプロトコルを使用してアクセスを受付け、レスポンスを返す。また、マルチノード・サーバシステムにおけるアプリケーション実行部２００は、ウェブ・サーバ以外にも、例えば、ＲＭＩ(Remote Method Invocation)、ＲＰＣ(Remote Procedure Call)、ＣＯＲＢＡ(Common
Object Resource Broker Architecture)、ＪＡＶＡ（登録商標）、Enterprise Java（登録商標） Beans:  EJB)などの分散コンピューティング環境を使用して実装することができる。この他、マルチノード・サーバシステムを、専用クライアントとの間で相互通信する専用システムとして構成してもよい。また、アプリケーション実行部２００およびアプリケーション実行部２００を構成するノード２０２、２０４、２０６、２０８は、それぞれ処理結果をクライアントに表示させるための手段として、適切なプロトコルを使用してイメージデータをネットワークを介して送信することが可能な、ネットワーク・アダプタ、ＮＩＣ（ネットワーク・インタフェース・カード）を、ネットワーク手段として実装する。
【００３７】
各ノードは、特定のメッシュでの処理を実行し、クライアントからの指令に応答して他メッシュに対し、当該クライアントのデータの送付や特定のクライアントについてメッシュ移動指令など送付することが必要となる。メッシュ間通信は、同一ノードの場合、プロセッサ間通信や、シグナリングなどのプロセス間通信を使用することができ、同一ノード内でのメッシュ切換の場合、プロセッサ・サイクルレベルで処理を行うことが可能となる。一方、異なるノードが処理するメッシュ間通信を行う場合、異なるノード間は、ＬＡＮ２２６で相互通信を行う。このため、ＬＡＮ２２６で行われるメッシュ間通信は、マルチノード・サーバシステム全体の処理効率を低下させるとともに、処理の信頼性を低下させることになる。このため、メッシュ間通信を、異なるサーバ間ではなく、単一サーバ内での、いわゆるノード内通信とし、できるだけＬＡＮ２２６を介したメッシュ間通信を削減することが、マルチノード・サーバシステムのパフォーマンス向上のためには好ましい。
【００３８】
また、図２に示すように、ノード２の特定メッシュ２２０には、複数のクライアント２２２、２２４などから、ネットワーク手段を構成し、ＮＩＣ、ＤＮＳサーバ、ゲートウェイサーバといったリモート・サーバ、ルータ、およびウェブ・ブラウザ／サーバプログラムなどとして構成されるネットワーク基盤２２８を介して、ユーザがアクセスし、メッシュ２２０に割当てられたリソースを使用して仮想空間１００上のコラボレーション環境下で、アプリケーションを実行させている。なお、クライアントは、アプリケーション実行部２００へと、パーソナル・コンピュータ、携帯電話、またはＰＤＡ(Portable Data Assistant)を使用し、ＷＡＮ(Wide Area Network)またはＩＮＴＥＲＮＥＴといった通信インフラ基盤を利用してアクセスし、アプリケーションの処理を要求する。
【００３９】
図３は、リソース管理ノード２１８の実施形態の機能ブロック図である。リソース管理ノード２１８は、資源分配システムにおいて、アプリケーション実行部２００を構成する複数のノードの間の資源配分を、特定のノードが過オーバーヘッドとなって処理落ちなどの不都合を発生させず、さらに、アプリケーション実行部２００内部の各ノードのオーバーヘッドを適切に分散させることで、アプリケーション実行部２００の能力が、特定のノードの容量により制約を受けないようにハードウェア資源を分散管理する。
【００４０】
リソース管理ノード２１８は、ＬＡＮ２２６およびネットワーク・アダプタ３００を介してアプリケーション実行部２００と相互通信する。リソース管理ノード２１８は、その各機能処理手段を、ハードウェア上に展開したプログラムの実行により、サーバ上に実現することができる。リソース管理ノード２１８の機能処理手段は、図３に示した実施形態では、メッシュ情報取得部３０２、メッシュ間通信量取得部３０４、ノード状態検知部３０６、最適配置データ登録部３０８および目的関数最小化部３１０として実装することができる。なお、特定の用途に適合するように、さらに他の機能処理部を実装してもよい。以下、各機能処理部について説明する。
【００４１】
（１）メッシュ情報取得部３０２は、ハードウェア上にプログラムを展開して実行させることによりメッシュ情報取得手段として実現され、ノードが現在処理しているメッシュのメッシュ識別値、メッシュのメモリ利用率、ＣＰＵ負荷など、ノードが特定のノードを処理する場合に割当てるハードウェア資源データを収集し、目的関数最小化部３１０に収集したハードウェア資源データを通知する。
【００４２】
（２）メッシュ間通信量取得部３０４は、ハードウェア上にプログラムを展開して実行させることによりメッシュ間通信量取得手段として実現され、ＬＡＮ２２６を介して相互通信するメッシュｉとメッシュｊとの間の通信量であるメッシュ間通信量Ｔｉｊを取得し、取得したメッシュ間通信量Ｔｉｊを目的関数最小化部３１０に通知する。このため、メッシュ間通信量取得部３０４は、ネットワーク・アダプタ３００を、プロミスキャス・モードでオープンさせ、ＬＡＮ２２６上で転送される全フレームをモニタする。
【００４３】
メッシュ間通信量取得部３０４は、目的とするメッシュｉ、メッシュｊのアドレスやメッシュ識別値を、ＩＰヘッダやペイロードに含み、ＭＡＣアドレスが当該メッシュを処理するノードを有するフレームをカウントし、当該カウント値を、モニタ期間にわたって平均化するなどすることにより、メッシュｉ、メッシュｊに関する単位時間当たりのＬＡＮ２２６を経由したメッシュ間通信量Ｔｉｊを生成し、目的関数最小化部３１０に通知する。また、メッシュ間でのデータ通信の他、メッシュ間通信量取得部３０４は、メッシュ間での処理サイクルを同期化させるため、メッシュ間で送付される同期通知通信も、同様にしてモニタすることができる。
【００４４】
（３）ノード状態検知部３０６は、ハードウェア上にプログラムを展開して実行させることによりノード状態検知手段として実現され、アプリケーション実行部２００のノードの、処理能力をモニタしており、例えば、特定ノードのＣＰＵ負荷および特定メッシュのノード内でのメモリ利用率などを検知して、本実施形態にしたがい、ノードの能力状態に応答して、よりオーバーヘッドの少ない他ノードへのメッシュ処理を移動させるためのノード移動処理の開始契機を提供する。
【００４５】
（４）最適配置データ登録部３０８は、ハードウェア上にプログラムを展開して実行させることにより最適配置データ登録手段として実現され、上記（１）、（２）、（３）で説明した各機能処理手段が取得した値により目的関数最小化部３１０が計算したノード−処理メッシュの最適割当てを登録する。最適配置データ登録部３０８は、適切なポーリング間隔で取得され、アプリケーションの実行に応じて時々刻々に変化するノード−処理メッシュの割当てについて、最新の最適配置データとして更新する。その後、最適配置データ登録部３０８は、メッシュ移動処理の開始に応答して該当ノードからの明示的な要求、またはリソース管理ノード２１８からのメッシュ移動先指令により、該当ノードに最新の最適配置データを取得させ、ノードごとのメッシュ移動処理を可能とする。
【００４６】
（５）目的関数最小化部３１０は、ハードウェア上にプログラムを展開して実行させることにより目的関数最小化手段として実現され、リソース管理するべきノードのメッシュ配置を、ＣＰＵ負荷、メモリ利用率、ＬＡＮ経由でのメッシュ間通信量、移転させるメッシュ数などを含め、メッシュ移動のためのアプリケーション実行部２００の処理オーバーヘッドおよびアプリケーション実行処理へのオーバーヘッドを最小化させるように、ノード−処理メッシュ配置を更新する処理を実行する。なお、目的関数最小化部３１０の処理結果は、メッシュ移動処理開始の後、上述した最適配置データ登録部３０８に送付され、所定のポーリング間隔ごとに更新させ、対象ノードが効率的に最新配置参照を可能としている。
【００４７】
本実施形態では、目的関数は、移動処理がアプリケーション実行部２００によるアプリケーションの実行に対し、メッシュごとのＣＰＵ負荷、メモリ専有状態、メッシュ間通信量、および移動対象メッシュ数を含む移動処理のための処理オーバーヘッドの上限値を最小化させるように設定する。より具体的には、本実施形態では、現在のメッシュ配置についてＳｐとし、目的関数を、下記式（１）のように設定することができる。
【００４８】
【数１】
0005373295.tif 000002
上記式（１）中、Ｃｉは、メッシュｉを処理するためのＣＰＵ計算時間などで与えられるＣＰＵ負荷、Ｍｉは、メッシュｉのメモリ専有状態、Ｔｉｊは、メッシュｉおよびメッシュｊの間のメッシュ間通信量、ｋは、移動させるべきメッシュの総数に対応するコスト係数で、アプリケーションが移動処理中に一時中断されることに対応し、移動処理当たりの平均負荷量などを使用して予め設定される係数である。
【００４９】
上記式（１）で示されるように、目的関数は、移動対象とされるメッシュの集合から、目的関数の上限値を取得し、当該上限値が最低化するようなメッシュ集合を与えるように、移動候補集合の要素メッシュを反復的に決定してゆくことによって最小化することができる。最小化された値を与えるメッシュの集合を、メッシュ集合として参照し、メッシュ集合全部の移動先ノードを最適配置データ登録部３０８に登録することができる。
【００５０】
また、好適な実施形態では、生成されたメッシュ集合のうち、ノードを変更する必要のあるメッシュの差分集合を計算し、当該差分集合の要素に関するノード識別値を最新最適異移動先として登録しておくこともできる。この場合でも、仮想空間１００の分割するメッシュの総数は、それほど多くはないので、例えば総当たり式の最小化であってもオーバーヘッドを抑制することができる。
【００５１】
また、ｇ（Ｓ，Ｓ′）は、Ｓを現在メッシュ配置、Ｓ′を移動後メッシュ配置
として、移動処理に際して移動対象となるメッシュの総数を与える関数である。また、関数ｓ（Ｍｉ）は、メッシュｉにおけるメモリ専有状態の値が、設定しきい値を超える場合、非常に大きな数を与え、設定しきい値以下の場合には０を与える関数である。
【００５２】
図４は、仮想空間１００に割当てたメッシュを処理する場合、各ノードが実行するメッシュ間の同期通知通信の処理の実施形態についてのフローチャートを示す。メッシュ間の同期通知通信は、各メッシュのアプリケーションによる処理を、同期して仮想空間１００として表示させるために利用される。図４に示す処理は、データ伝送に加え、ＬＡＮ２２６を経由するノード間通信として実行される。図４では、説明の目的から、ノードｐとノードｑとの間の処理を使用して説明するが、他のノードの間でも同様のノード間通信が実行される。アプリケーション実行部２００は、複数のメッシュが割当てられた仮想空間１００内でのアプリケーション実行が、クライアント、より具体的にはクライアントを介して仮想空間１００にアクセスするユーザに違和感を与えることがないように、各ノード間で処理サイクルを同期させている。
【００５３】
例えばノードｐでは、ステップＳ４００で、ノードｐに割当てられたメッシュを処理し、プレイヤー（表示オブジェクト）の移動を行い、当たりなどのボーナス処理など、アプリケーションによる処理を、設定された１サイクル単位で実行する。ステップＳ４０１では、他のノードの処理と同期させるため、ノードｑへとＬＡＮ２２６を介して通信し、他ノードの同期状態をモニタする。
【００５４】
その後、ステップＳ４０２では、全メッシュが１サイクルの処理を完了したか否かを判断する。全メッシュで１サイクルの処理が完了した場合（ｙｅｓ）処理をステップＳ４００に戻し、次の１サイクルを開始させる。一方、全メッシュで、１サイクルの処理を完了しない場合（ｎｏ）、全メッシュが１サイクルの処理を完了するまで、処理を待機させる。
【００５５】
ノードｑも同一の処理を、ステップＳ４１０〜ステップＳ４１２で実行し、メッシュが仮想空間１００全体として１サイクル分の処理を同期して実行し、仮想空間１００上の表示を同期させている。なお、図４に示したメッシュ間通信は、ノードｐからノードｑに送付されるものとして説明しているが、メッシュ間でフルメッシュ通信を行なわなくとも良いように、ノードｐおよびノードｑは、それぞれリソース管理ノード２１８に宛てて同期状態を通知する実施形態を採用することもできる。
【００５６】
この実施形態の場合、リソース管理ノード２１８は、サイクル同期テーブルなどを実装し、メッシュ識別値について、例えば、サイクル同期識別値を登録することにより、全メッシュのサイクル同期状態を、リソース管理ノード２１８が判断することができる。全メッシュのサイクルが同期したと判断した場合、リソース管理ノード２１８は、アプリケーション実行部２００を構成するノードに対して、同期完了通知を、ブロードキャストまたはマルチキャストすることで、仮想空間１００内のメッシュの同期的更新処理を可能としてもよい。
【００５７】
以下、図５〜図７を使用して、アプリケーション実行部２００を構成するノード、リソース管理ノード２１８がそれぞれ管理し、データを登録するデータ構造について説明する。図５は、アプリケーション実行部２００を構成するノード２０２、２０４、２０６、２０８がそれぞれ管理する、メッシュ管理手段として機能する、メッシュ管理テーブル５００の実施形態を示す。
【００５８】
図５に示すメッシュ管理テーブル５００は、メッシュ管理手段として機能し、当該ノードが現在処理を実行しているメッシュについての各種情報を登録する。メッシュ管理テーブル５００は、仮想空間内１００内でメッシュを固有に識別するためのメッシュ識別値５０２、当該メッシュのネットワーク上でのアドレス５０４、メッシュ内の処理を実行するために、ハードウェア・リソースのメッシュ利用状態を示すメッシュ能力状態５０６、アプリケーション実行をメッシュ単位で可能とするリソース・データ５０８、および当該処理時点で移動処理中であることを示す移動処理状態識別値５１０などの値が登録されている。
【００５９】
メッシュ識別値５０２は、仮想空間１００の特定の領域を示すものであり、ノン実施形態では、メッシュ識別値５０２で与えられるメッシュの処理を担当するノードが変更される。アドレス５０４は、ネットワーク上で、クライアントが当該メッシュを識別してアクセスすることができる限り、ＵＲＬ、ＵＲＩ、絶対パス名または相対パス名などで指定することができる。メッシュ能力状態５０６は、メッシュ内で実行されるタスクのために割くＣＰＵ負荷、メッシュに対して割当て可能なメモリ容量に関するメモリ利用率などをパラメータとして決定され、メッシュ単位の処理についてのサチュレーション状態を示す値が登録される。
【００６０】
また、リソース・データ５０８には、メッシュ表示のために必要なグラフィック・データ、実行設定などのメッシュ固有データ、ユーザにより指定された設定、ユーザ認証データなど、ユーザごとに異なるデータであるユーザ固有データ、および当該メッシュ内に表示されるオブジェクト（キャラクタ）の種類、移動ベクトル、位置など、メッシュ内に表示するべきオブジェクトに固有のオブジェクト固有データが登録される。
【００６１】
また、メッシュ管理テーブル５００には、その時点でアプリケーション実行部２００が移動処理中であることを示す移動処理状態識別値５１０が登録される。移動処理状態識別値５１０が設定されている間は、移動処理状態識別値５１０が設定されたメッシュは、移動処理プロセス以外のプログラムによる書込みが禁止され、移動処理中におけるデータの整合性を保証している。なお、この場合でも、移動対象のメッシュについてのデータ読出しなどは制限されず、他のクライアントの実行処理中断を最小限の負荷とさせている。
【００６２】
移動処理状態識別値５１０は、特定の実施形態では、フラグとして設定することができ、またさらに他の実施形態では、セマフォ、ミューテックスなどを使用して実装することができる。また、本実施形態では、特定のノードが移動状態に設定された場合、当該ノードが移動処理を開始する前に他の全部のノードに対して通知を行い、移動処理中のメッシュに対する書込み要求をブロックして、移動中のメッシュのデータ整合性をさらに保証する。図５に示した実施形態では、ハッチングで示すように、メッシュ４が移動処理の対象として移動処理状態識別値５１０が設定されている。
【００６３】
また、メッシュ管理テーブル５００は、複数のメッシュの実行処理に伴うノードの能力飽和状態を示す値であるノード能力状態５１２を登録する、ノード能力状態５１２は、簡単な実施形態では、メッシュ１〜メッシュ４のメッシュ能力状態の総和の、当該ノードの最大能力であるＰｍａｘに対する相対比５１４として計算することができる。なお、さらに各能力に対応して重み付け係数を設定し、より詳細な状態制御を行うこともできる。
【００６４】
図６は、リソース管理ノード２１８の最適配置データ登録部３０８が管理する最適配置データ６００の実施形態を示す。最適配置データ６００は、メッシュ識別値６０２に対応して、当該メッシュ識別値で指定されるメッシュの処理を現在実行しているノードを登録するカレント実行ノード６０４と、最新の最適移動先であって、移動後に最適配置Ｓｒｅｓを与える最新最適移動先６０６とが登録されたテーブルとして構成することができる。なお、最新最適移動先６０６の空フィールドは、移動しないことを示すものであり、特定の実装形態に応じて図６に示すように移動するメッシュのみを明示的に登録することもできるし、移動如何にかかわらず、最適配置Ｓｒｅｓを与えるメッシュ集合を登録することもできる。
【００６５】
マルチノード・サーバシステムは、メッシュを移動させる必要があると判断すると、その時点で最新の最適メッシュ配置を最適配置データ６００を参照して取得し、対象となるノード／メッシュに対する排他制御を実行し、ノード１に対してメッシュ識別値を登録するレコードを追加する。その後、マルチノード・サーバシステムは、ノード２のメッシュ４のリソース・データ５０８を読出し、読出したリソース・データをノード１の追加されたレコードに、当該メッシュ識別値と共に登録することで、移動処理を実行する。
【００６６】
図７は、マルチノード・サーバシステムが実行する負荷分散処理の実施形態についてのフローチャートを示す。負荷分散処理は、ステップＳ７００から開始し、ステップＳ７０１で、リソース管理ノード２１８が各メッシュごとに目的関数の計算に必要なデータを回収する。同時にステップＳ７０２でアプリケーション実行部２００がアプリケーションの実行を開始する。なお、実行するアプリケーションは、本実施形態ではゲーム・アプリケーションであるものとして説明する。
【００６７】
ステップＳ７０３では、リソース管理ノード２１８は、移動するべきメッシュを要素として含む、移動候補集合を作成し、テーブルなどの追加登録してゆく。ステップＳ７０３の処理は、ハードウェア上にプログラムを展開して実装される図９に示す移動候補集合生成手段による処理として実行される。ステップＳ７０４では、移動候補集合の要素から目的関数を最小にするメッシュ集合を決定し、これを移動候補集合として設定する。ステップＳ７０５では、目的関数の最小化が収束したかまたは設定回数分最小化計算が終了したかを判断する。ステップＳ７０５の判断が否定的な値を返す場合（ｎｏ）、処理をステップＳ７０３に分岐させて次の移動候補集合を作成する。
【００６８】
一方、ステップＳ７０５の判断が肯定的な値を返す場合（ｙｅｓ）、処理をステップＳ７０６に進め、移動処理を実行する。その間、アプリケーション実行部２００は、ゲーム・アプリケーションの実行を継続しており、ステップＳ７０７では、クライアントから、ゲーム・アプリケーション終了の要求を受領したか否かを判断する。ゲーム・アプリケーションを終了しない場合（ｎｏ）、処理をステップＳ７０２に分岐させ、さらにゲーム・アプリケーションを実行し、その間、リソース管理ノード２１８によるメッシュ配分の処理を継続する。
【００６９】
同時に、リソース管理ノード２１８は、ステップＳ７０８でタイマ・カウンタなどを参照して、ポーリング・タイミングとなったか否かを判断する。ステップＳ７０８でポーリング・タイミングとなっていない場合、ポーリング・タイミングが到来するまで、ステップＳ７０８で待機する。また、ポーリング・タイミングとなった場合（ｙｅｓ）処理をステップＳ７０１に分岐させて、各メッシュの現在状態を回収し、以後のリソース管理を実行する。なお、ステップＳ７０７の判断でゲーム・アプリケーション終了と判断された場合（ｙｅｓ）、ステップＳ７０９その時点のメッシュ分布、メッシュ・データなどをユーザ・データと共に各ノードの固定記憶装置などに格納し、アプリケーション実行部２００の処理を停止させ、同時に負荷分散処理も終了させる。
【００７０】
図８は、リソース管理ノード２１８によるメッシュの処理ノードを移転させる場合の実施形態を示す。図８（ａ）は、現在メッシュ配分を示し、図８（ｂ）〜（ｄ）がメッシュ処理の移転候補集合の要素の実施形態を示す。なお、図８に示したテーブルは、リソース管理ノード２１８のメッシュ割当てテーブル８００として実装することができる。図８に示すメッシュ割当てテーブル８００は、メッシュ識別値に対して、処理ノードのノード識別値を割当てたテーブルとして構成することができる。例えば図８（ａ）の現在メッシュ配分では、メッシュ１〜１１、１３、１４で与えられる領域８０４は、ノード２に処理が割当てられ、メッシュ１２、１５、１６で与えられる領域８０２は、ノード１にそれらの処理が割当てられているものとしている。
【００７１】
図８（ａ）でに示すように、メッシュ列８−１１−１４と、メッシュ列１２−１５とは、処理サーバが異なる領域８０２と８０４とのサーバ境界を規定し、互いに隣接した配置にある境界メッシュである。
【００７２】
この段階で、例えばノード１のノード能力状態が許容能力しきい値を超えた場合や、ノード１の特定のメッシュのメモリ専有状態がメモリ割当てしきい値を超えた場合、またはアプリケーション実行部２００内でのＬＡＮの通信状態が輻輳状態となる可能性がある場合、リソース管理ノード２１８は、移動処理を開始し、移動候補集合の生成を開始する。移動候補集合は、ノード２に含まれるメッシュのうち、ノード１のメッシュに隣接したメッシュが優先的に選択される。この理由は、隣接したメッシュ間では、他のメッシュ間よりもメッシュ間通信量Ｔｉｊが大きいものと判断され、隣接するメッシュであって、処理ノードが異なるメッシュを同一ノードに繰り込むことで、メッシュ間通信量ＴｉｊをＬＡＮ経由の伝送から、ノード内の伝送に変更でき、目的関数の最適化処理を効率化できるためである。
【００７３】
図８（ｂ）に示すように、例えばメッシュ１１とメッシュ１２との間のメッシュ間通信量が、通信しきい値を超えた場合、メッシュ１１の処理ノードを、ノード２からノード１に移動させることで、他の処理条件が変わらない場合、目的関数の最小化を達成することができる。また、図８（ｃ）では、目的関数を最小化する移動候補集合は、ノード１が担当する領域８０２に隣接するメッシュ８、メッシュ１１、メッシュ１４に加え、メッシュ７が含まれている。さらに、ノード２およびノード１の実行状況に対応して図８（ｄ）に示すように、さらに多数のメッシュを移動候補集合として選択することもできる。なお、図８（ｄ）では、サーバ境界を規定する境界メッシュの他、領域８０２および領域８０４の処理負荷を分散させるため、ＣＰＵ負荷またはメモリ利用率を考慮する結果、目的関数の上限値を最小化させるべく、サーバ境界以外のメッシュの移動候補として領域８０６まで、例えば隣接尺度値を変化させて選択されている。なお、隣接尺度値とは、注目するメッシュに対して直接隣接する場合を１、直隣接するメッシュに隣接するメッシュまで含める場合は、２などとして設定することができる。
【００７４】
図９は、リソース管理ノード２１８が実行する移動候補集合生成手段が実行する処理の実施形態のフローチャートを示す。移動候補集合生成処理は、図７のステップＳ７０３で呼出され、移動候補集合ａ、集合Ｂ＝Ｓｐ（ノードｐに含まれるメッシュ集合）に初期設定する。その後、移動候補集合を更新的に生成させる関数create_atemp()呼出し、その結果を集合Ａｔｅｍｐとして登録し、集合Ａｔｅｍｐを移動候補集合Ａｐに追加登録することにより、目的関数最小化に使用する移動対象メッシュ集合を生成する。
【００７５】
ステップＳ７０３で、create_atemp()が呼出されると、ステップＳ９００でグローバル変数として宣言された集合Ａｔｅｍｐを初期化して空集合として設定する。さらに、集合ａおよび集合Ｂを取得して処理対象として設定する。ステップＳ９０１では、集合Ｂからメッシュｉを読み出し、ステップＳ９０２で集合Ｂが空集合か否かを判断する。空集合の場合（ｙｅｓ）、当該ノードは、何もメッシュを処理していないので、処理をステップＳ９０９に分岐させ、処理を戻す。ステップＳ９０２で、集合Ｂが空集合ではないと判断された場合（ｎｏ）、ステップＳ９０３で、メッシュ割当てテーブルを参照し、メッシュｉに隣接し、集合Ｂに含まれないメッシュの集合を抽出し、集合Ｃに登録する。ステップＳ９０４で、集合Ｃが空集合か否かを判断し、集合Ｃが空集合の場合、集合Ｂの境界を構成するメッシュを見出すまでステップＳ９０１に処理を分岐させる。
【００７６】
ステップＳ９０４で集合Ｃが空集合でない場合（ｎｏ）、ステップＳ９０５で、集合Ｃからメッシュｊ（集合Ｂの処理対象メッシュの境界にあって、他のノードが処理を実行しているメッシュに相当する。）を取得し、集合Ｂの要素として追加して、集合Ｂ′を生成し、集合ａにメッシュｊを追加して集合ａ′を生成する。この段階で、移動するべきメッシュと、移動後のメッシュ配置が更新される。
【００７７】
ステップＳ９０６では、集合ａ′が、その時点での集合Ａｔｅｍｐの要素にあるか否かを判断し、すでに含まれている場合（ｙｅｓ）、処理をステップＳ９０４に戻し、さらに集合ａ′の生成を行う。一方、ステップＳ９０６でａ′がＡｔｅｍｐの要素として含まれていない場合（ｎｏ）、集合ａ′の要素数が設定上限値となったか否かを判断する。ステップＳ９０７で集合ａ′の要素数が設定上限値となるまでメッシュが収集された場合（ｙｅｓ）、ステップＳ９０９に処理を進め、ステップＳ７０３で、設定上限値の要素を含むＡｔｅｍｐを、移動候補集合Ａｐに追加登録する。
【００７８】
一方、ステップＳ９０７で集合ａ′の要素数が設定上限値未満の場合（ｎｏ）、ステップＳ９０８で、集合ａ′を、Ａｔｅｍｐの要素に追加し、ａ＝ａ′、Ｂ＝Ｂ′に初期設定して、処理をステップＳ９０１に戻し、設定上限値となるか、または集合Ｂが空集合となるまで処理を繰り返した後、処理をステップＳ７０４へと分岐させ、目的関数の最適化の対象メッシュとして供給する。この段階で、集合Ｂに隣接するメッシュのうち、集合Ｂ、すなわちノードｐに移動させるべきメッシュの集合である、移動候補集合Ａｐが与えられる。
【００７９】
ステップＳ７０４（図７）では、目的関数が収束するか、または指定回数だけ反復計算を繰り返したうち、目的関数を最小とするメッシュ集合を、ノードｐを移動先として移動処理の対象メッシュとして、図６の最適配置データ６００に登録する。なお、この処理は、ポーリング・タイミングの到来に対応して繰り返し実行され、ポーリング・タイミングごとに最適配置も更新されることになり、アプリケーション実行部２００の処理の変化に効率的に対応することが可能となる。
【００８０】
図１０は、本実施形態の移動処理の実施形態のシーケンスを示す。図１０に示すシーケンスは、ステップＳ１０００で、移動処理が起動される。ここで、ノードｐが移動処理を開始し、ノードｐ′を移動先ノードとし、ノードｐが管理するメッシュｉの処理を移動させるものと仮定して説明を行う。
【００８１】
＜ノードｐの処理＞
ノードｐは、ステップＳ１００１で、ノード能力が予め設定した各しきい値のうちのいずれか１つを超えた段階で、リソース管理ノード２１８からノードｐについて登録された、最新の最適移動対象メッシュ集合および移動先ノードｐ′のＭＡＣアドレスなどを取得する。
【００８２】
ステップＳ１００２では、ノードｐは、移動対象のメッシュiについて移動処理プロセスが例えば共有ロックなどの排他制御を実行し、同時にメッシュｉにアクセスする全クライアントに対してアプリケーション実行の一時停止通知を発行する。
【００８３】
その後、ステップＳ１００３で、ノードｐは、サーバ・ノードを構成する他の全ノードに対してメッシュｉへの書込み処理停止命令を送付して、他ノードがメッシュｉに書込みしようとした場合、他ノードのメッシュにアクセスするクライアントに対して例外エラーが送付されないようにして、メッシュ移動に関連のないクライアントの処理の中断を防止する。
【００８４】
ステップＳ１００４では、ノードｐ′に対して、メッシュ登録命令を発行し、メッシュ管理テーブルの空きレコードに、ノードｐ′でのメッシュｉを参照するためのアドレスを生成させ、その他の空きフィールドにメッシュｉの対応フィールドに登録されたデータを送付してコピーする。その後、ステップＳ１００５で、クライアントに対して一時停止解除通知および接続先としてノードｐ′のメッシュｉ′に割当てられた、例えばグローバルＩＰアドレスなどの適切なアドレスを通知して接続させた後、ステップＳ１００６で、ノードｐは、メッシュｉのデータを破棄し、移転元ノードｐの処理を終了させる。
【００８５】
＜ノードｐ′の処理＞
一方、ノードｐ′は、ステップＳ１００７でメッシュ登録命令を受信すると、メッシュｉ′のためのメモリ領域を確保し、ノードｐ′のメッシュ管理テーブルに新たなレコードを生成させ、メッシュｉ′のデータとして、固有アドレスを生成して登録する。その後、続けて送信されるデータを対応するフィールドに登録する。さらに、ノードｐ′は、ステップＳ１００８で、メッシュｉ′の排他制御を解除し、メッシュｉがメッシュｉ′に変更されたことを、そのアドレスと共に通知し、メッシュ間通信を可能とする。その後、さらに、ステップＳ１００９でクライアントからのアクセスを受付け、移動処理後の処理を続行し、ステップＳ１０１４で処理を終了させる。
【００８６】
以上説明したノードｐおよびノードｐ′の処理によって、移動対象とされていないメッシュにアクセスするクライアントの仮想空間表示およびアプリケーション実行は、最小限の制限の下で継続可能となる。
【００８７】
＜クライアントの処理＞
クライアントは、ステップＳ１０１０で、ノードｐから一時停止通知を受信し、ステップＳ１０１１で一時停止画面を表示させる。なお、一時停止画面は、リソース管理ノード２１８などが移動処理開始時での仮想空間１００のスナップショットを、例えば、ＢＭＰ、ＰＮＧ、ＧＩＦ、ＪＰＥＧなどとして作成して、一時停止間面のために確保してあるＵＲＩなどに登録しておき、クライアントに表示させることにより表示させることができる。また、一時停止解除までの残り時間については、リソース管理ノード２１８が、スナップショットを送付するためのＨＴＭＬなどの構造化文書に、アプレットなどとして移動処理プロセスの進行具合に対応するバー表示および「しばらくお待ち下さい」などの表示として与えることができる。
【００８８】
マルチノード・サーバシステムを、ゲーム・サーバとして実装し、クライアントが専用アプリケーションを使用してマルチノード・サーバシステムにアクセスする場合には、専用アプリケーションを実行するクライアントのＬ１キャッシュ・メモリ、Ｌ２キャッシュ・メモリなどのキャッシュ・メモリにノードの状態をキャッシュしておき、表示させることができる。この実施形態の場合、リソース管理ノード２１８からのＨＴＭＬの受信とは別に、専用アプリケーションが予め登録してある、「お待ちください」などの表示を、クライアントに表示させることができる。本実施形態では、リソース管理ノード２１８のクライアント管理による負荷をクライアント側に分散させ、マルチノード・サーバシステム側で、さらに効率的なメッシュ移動処理を実行させることができる。
【００８９】
ステップＳ１０１２では、クライアントが一時停止解除通知を受信すると、ステップＳ１０１３で当該通知と共に送付されるメッシュｉ′のアドレスを取得してノードｐ′へと接続し、スナップショットを表示させるためのＵＲＩからアプリケーションを実行するためのＵＲＩへと接続を切換えて以後の処理を続行させる。
【００９０】
なお、移動処理の対象メッシュ以外のクライアントは、移動対象のメッシュへのアクセスを行わない限り、それまでと同様のアプリケーションを実行することができる。また、クライアントが移動対象のメッシュへの移動を試みた場合でも、メッシュｉへの書込み処理発行停止命令が有効なので、移動対象のメッシュへの移動が、移動処理の期間だけ制約されるのみであり、また当該メッシュからのメッシュｉなどに対する書込み要求が発行されないので、例外エラーも発生せず、移動対象のメッシュ以外でアプリケーションを実行させているクライアントについては、移動処理による処理停止の影響を最小限に済ませることができる。そして、移動処理が終了した時点で全部のクライアントが移動後のメッシュにアクセスしてコラボレーションしながらアプリケーションを実行させることが可能となる。
【００９１】
図１１は、本実施形態の負荷分散方法によるメッシュを処理するノードの移動の実施形態を示す。図１１に示す実施形態では、マルチノード・サーバシステムは、ゲーム・サーバとして構成されており、アプリケーションの実行により、仮想空間上に航空機といった複数のオブジェクトを表示させた、フライトシミュレータとして構成されている。図１１（ａ）に示す実施形態では、仮想空間１１００は、１６個のメッシュが割当てられ、３つのノードがそれぞれ領域１１０２、１１０４、１１０６に含まれるメッシュの処理を実行している。
【００９２】
ここで、領域１１０２は、ノード１により処理が実行されており、領域１１０６は、ノード２により処理が実行され、さらに領域１１０４は、ノード３により実行されている。領域１１０２のメッシュ１１０８は、表示オブジェクトの数および密度が最も高く、メッシュ１１０８でメッシュに割当てられたＣＰＵ負荷量がしきい値を超えたものとする。この段階で、移動処理プロセスが呼出され、ユーザに対して図１１（ａ）に示したイメージがスナップショットとして提供され、好ましい実施形態では、「しばらくお待ち下さい」などの表示が行われる。
【００９３】
この間に、最適配置データが取得され、メッシュのノードに対する処理割当てが変更される。変更後、ユーザに対して新たに割当てられたメッシュのアドレスに基づいて、仮想空間上でのフライトシュミレータの処理が続行される。図１１（ｂ）は、メッシュ割当てが変更された後のメッシュ配置を示す。図１１（ｂ）に示すように、図１１（ａ）の領域１１０２は、メッシュ１１０８がノード２に取る処理へと移動された結果、領域１１２２に変更され、同時に、領域１１０６は、メッシュ１１０８が加えられたことにより、領域１１２６で示されるメッシュの処理を実行している。
【００９４】
ノード２は、図１１（ａ）に示すようにそれ以前では、背景イメージを表示させているのみで、最も処理負荷が少ないノードであり、処理負荷がノード全体にわたって分散できていない。しかしながら、図１１（ｂ）では、ノード１およびノード２、およびノード３がそれぞれ表示オブジェクトの処理を担当しており、また最小のメッシュ移動により負荷分散が可能とされているのがわかる。
【００９５】
なお、本実施形態は、フライトシミュレータ、レーシング・ゲーム、バトル・ゲームなどの対戦型ゲームの他、例えば「SecondLife」などのような生活環境型ゲームにも適用することができ、生活環境形ゲームの場合には、クライアントの一時停止、他の場所へのワープなどの強制的移動などがあった場合にでもゲームの臨場感を保持させることができるので、より好適に本発明を適用することができる。さらに本発明の他の実施形態では、クライアントのディスプレイ画面上に複数の連動するディスプレイ領域を構成して、複数のクライアントにアプリケーション実行画面を共有させることが可能な、ネットワークを介した動画配信サービスにも適用することができる。
【００９６】
以上、本発明によれば、サーバをノードとし、複数のノードが相互接続されたマルチノード・サーバシステムにおいて、マルチノード・サーバシステムの処理効率を仮想空間の領域単位で最適化するようにハードウェア資源を配分することを可能とするとともに、サーバ・システムにおけるハードウェア資源の再配分処理中にクライアントが被るアプリケーションの中断などの影響を最低化することを可能とする、マルチノード・サーバシステム、マルチノード・サーバシステムの負荷分散方法およびプログラムが提供できる。
【００９７】
本発明の上記機能は、Ｃ＋＋、Ｊａｖａ（登録商標）、Ｊａｖａ（登録商標）Ｂｅａｎｓ、Ｊａｖａ（登録商標）Ａｐｐｌｅｔ、Ｊａｖａ（登録商標）Ｓｃｒｉｐｔ、Ｐｅｒｌ、Ｒｕｂｙなどのオブジェクト指向プログラミング言語などで記述された装置実行可能なプログラムにより実現でき、装置可読な記録媒体に格納して頒布することができる。
【００９８】
これまで本発明を実施形態をもって説明してきたが、本発明は、実施形態に限定されるものではなく、他の実施形態、追加、変更、削除など、当業者が想到することができる範囲内で変更することができ、いずれの態様においても本発明の作用・効果を奏する限り、本発明の範囲に含まれるものである。
【図面の簡単な説明】
【００９９】
【図１】マルチノード・サーバシステムによる仮想空間のメッシュ分割の実施形態を示した図。
【図２】本実施形態のマルチノード・サーバシステムの機能ブロック図。
【図３】リソース管理ノードの実施形態の機能ブロック図。
【図４】仮想空間に割当てたメッシュを処理する場合、各ノードが実行する処理の実施形態についてのフローチャート。
【図５】アプリケーション実行部を構成するノードがそれぞれ管理する、メッシュ管理手段として機能する、メッシュ管理テーブルの実施形態を示した図。
【図６】リソース管理ノードの最適配置データ登録部が管理する最適配置データの実施形態を示した図。
【図７】マルチノード・サーバシステムが実行する負荷分散処理の実施形態についてのフローチャート。
【図８】リソース管理ノードによるメッシュの処理ノードを移転させる場合の実施形態を示した図。
【図９】リソース管理ノードが実行する移動候補集合生成処理の実施形態のフローチャート。
【図１０】本実施形態の移動処理の実施形態のシーケンスを示した図。
【図１１】本実施形態の負荷分散方法によるメッシュを処理するノードの移動の実施形態を示した図。
【符号の説明】
【０１００】
１００…仮想空間、１０２…道路、１０４…メッシュ境界、１０６…メッシュ、２００…アプリケーション実行部、２０２、２０４、２０６、２０８…サーバ（ノード）、２１０、２１２、２１４、２１６…メッシュ、２１８…リソース管理ノード、２２０…メッシュ、２２２、２２４…クライアント、２２６…ＬＡＮ、２２８…ネットワーク基盤、３００…ネットワーク・アダプタ、３０２…メッシュ情報取得部、３０４…メッシュ間通信量取得部、３０６…ノード状態検知部、３０８…最適配置データ登録部、３１０…目的関数最小化部、５００…メッシュ管理テーブル、６００…最適配置データ、８００…メッシュ割当てテーブル、８０２、８０４…領域、１１００、１１２０…仮想空間
【図１】
0005373295.tif 000003
【図２】
0005373295.tif 000004
【図３】
0005373295.tif 000005
【図４】
0005373295.tif 000006
【図５】
0005373295.tif 000007
【図６】
0005373295.tif 000008
【図７】
0005373295.tif 000009
【図８】
0005373295.tif 000010
【図９】
0005373295.tif 000011
【図１０】
0005373295.tif 000012
【図１１】
0005373295.tif 000013