(57)【特許請求の範囲】
【請求項１】
ノード・クラスタに対する非集中型のアプリケーションを前記ノード・クラスタ中の各ローカル・ノードに割振るための方法であって、
前記ノード・クラスタ中の各ローカル・ノードで実行されている実行中アプリケーションの現在の集合を含む一つのローカル・ノードが、
（ａ）前記ノード・クラスタ中のローカル・ノードのサブセット（以下、「ノード・サブセット」という）から前記アプリケーションの実行のために利用しうる前記ノード・クラスタ中のローカル・ノードそれぞれのリソースのデータ（以下、「リソース・データ」という）を受信するステップであって、前記ノード・クラスタ中のローカル・ノードそれぞれが、前記ノード・サブセットに含まれるローカル・ノードのリストを保持している、前記受信するステップと、
（ｂ）前記受信したリソース・データに少なくとも部分的に基づいて、前記一つのローカル・ノードで実行されるアプリケーションの新しい集合を決定するステップであって、
当該一つのローカル・ノードで実行されている実行中アプリケーションの集合を定義するステップと、
アプリケーションに与えられるＣＰＵの量とアプリケーションによって利用されるメモリとの比率として定義される密度の低い順に、前記実行中アプリケーションをソートするステップと、
前記ノード・サブセット上で実行されており前記一つのローカル・ノード上では実行されていないアプリケーションと、前記ノード・クラスタ中のどこでも実行されていないアプリケーションとを含む、待機中アプリケーションの集合を定義するステップと、
リソースの需要と供給との差として定義される満たされない需要がないアプリケーションを前記待機中アプリケーションの集合から除去するステップと、
前記満たされない需要とアプリケーションによって利用されるメモリとの比率として定義される満たされない密度の高い順に、前記待機中アプリケーションの集合をソートするステップと、
前記一つのローカル・ノードから前記ノード・サブセットに出来るだけ多くの負荷を割り当てようとすることによって負荷を移動するステップと、
前記ソートされた実行中アプリケーションの集合中のアプリケーションの部分集合を、前記ソートされた待機中アプリケーションの集合中のアプリケーションの部分集合で置き換えることを繰り返し行うことによって、複数のローカル構成を構築するステップと、
前記一つのローカル・ノード上でアプリケーションが実行された場合に当該一つのローカル・ノードのＣＰＵ利用が最大になる最適な構成を前記複数のローカル構成から選択するステップと
をさらに含む、前記決定するステップと、
（ｃ）前記決定されたアプリケーションの新しい集合に属するアプリケーションのうちのどのアプリケーションが当該一つのローカル・ノードで実行されるかを、前記アプリケーションの新しい集合に従って決定するステップと、
（ｄ）当該一つのローカル・ノードにおける前記アプリケーションの新しい集合と前記アプリケーションの現在の集合との間で実行が変更されるアプリケーション情報を当該一つのローカル・ノードから前記ノード・クラスタ中の前記ノード・サブセットに送信するステップであって、前記ノード・サブセット中の各ローカル・ノードは、前記送信されたアプリケーション情報を、当該アプリケーションを前記ノード・クラスタ中の前記各ローカル・ノードに割振るために使用する、前記送信するステップと、
（ｅ）当該一つのローカル・ノード中ですでに実行されている実行中アプリケーションに対するロック要求（以下、第１のロック要求という）を送信するステップであって、当該一つのローカル・ノードに割り振られた実行中のアプリケーションについて、２つの論理ホップ分だけ離れているすべてのローカル・ノードをロックするためにロック要求を送信するステップを含み、当該第１のロック要求によるロックは、当該２つの論理ホップ分だけ離れているすべてのローカル・ノードが前記アプリケーションを開始及び停止しないようにする、前記第１のロック要求を送信するステップと、
（ｆ）前記ノード・クラスタ中のどのローカル・ノードでも現在実行されていないアプリケーションに対するロックをするステップであって、前記ノード・クラスタ中のどのローカル・ノードでも現在実行されていないアプリケーションを当該一つのローカル・ノードが開始しないようにするロック要求（以下、第２のロック要求という）を、前記ノード・クラスタ中の他のローカル・ノードから受信するステップであって、当該第２のロック要求によるロックは、前記ノード・クラスタ中のどのローカル・ノードでも現在実行されていないアプリケーションを開始するために使用される、前記第２のロック要求を送信するステップと
を実行することを含む、前記方法。
【請求項２】
前記ノード・クラスタ中の各ローカル・ノードが、前記ステップ（ａ）〜（ｆ）の各操作を独立して非同期で実施する、請求項１に記載の方法。
【請求項３】
前記受信するステップ（ａ）が、
前記ノード・サブセットを識別するステップ
をさらに含む、請求項１に記載の方法。
【請求項４】
前記受信するステップ（ａ）は、
前記ノード・サブセット中の各ローカル・ノードからアクティブ・アプリケーションのリストを受信するステップと、
前記リスト中の各アクティブ・アプリケーションについてのリソース供給と需要を受信するステップと、
前記リスト中の各アクティブ・アプリケーションについてのリソース・データを受信するステップと
を含む、請求項１に記載の方法。
【請求項５】
前記送信するステップ（ｄ）は、
ゴシップ・プロトコルを使用するステップ
を含み、
前記ゴシップ・プロトコルでは、前記ノード・クラスタ中の前記各ローカル・ノードが、所定期間中に受信したかまたは発生させたメッセージを集約した後で、前記集約したメッセージを近傍ローカル・ノードに送信する、
請求項１に記載の方法。
【請求項６】
前記ノード・サブセットが、当該一つのローカル・ノードで実行されているアプリケーションの現在の集合を含む当該一つのローカル・ノードの近傍にあるローカル・ノードのサブセットである、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
ノード・クラスタに対する非集中型のアプリケーションを前記ノード・クラスタ中の各ローカル・ノードに割振るためのシステムにおいて、前記ノード・クラスタ中の各ローカル・ノードで実行されているアプリケーションの現在の集合を含む一つのローカル・ノードであって、
コンピュータ・プログラムを実行するように構成されたプロセッサと、
前記プロセッサに接続され、コンピュータ・ネットワークを介してデータを送受信するように構成されたネットワーク・インターフェースと、
前記コンピュータ・プログラムを組み入れた記憶デバイスと
を備えており、
前記記憶デバイスは、当該一つのローカル・ノードに、請求項１及び３〜６のいずれか一項に記載の方法の各ステップを実行させるコンピュータ・プログラムを格納している、前記一つのローカル・ノード。
【請求項８】
ノード・クラスタに対する非集中型のアプリケーションを前記ノード・クラスタ中の各ローカル・ノードに割振るためのコンピュータ・プログラムであって、前記ノード・クラスタ中の各ローカル・ノードで実行されているアプリケーションの現在の集合を含む前記一つのローカル・ノードに、請求項１及び３〜６のいずれか一項に記載の方法の各ステップを実行させる、前記コンピュータ・プログラム。
【請求項９】
ノード・クラスタであって、当該ノード・クラスタに対する非集中型のアプリケーションを前記ノード・クラスタ中の各ローカル・ノードに割振るためのシステムにおいて、請求項７に記載の一つのローカル・ノードを複数備えている、前記ノード・クラスタ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータのクラスタ上のアプリケーション配置を対象とし、より詳細には、アプリケーションに対する負荷が変動するのに伴って非集中型かつオンデマンドのアプリケーション・リソース割振りを分散方式で行うことを対象とする。
【背景技術】
【０００２】
ワールド・ワイド・ウェブ（ＷＷＷまたは単に「ウェブ」）、及びデータ・サービスのアウトソーシングの普及に伴い、コンピューティング・サービス・センタは、サイズと複雑さの両方が増してきた。例えばサービス・センタは、特定のアプリケーションのためのプロセスを実行するサーバ・ファームと呼ばれるサーバの集まりを含むことがあり、これはクラスタとして知られる。このようなセンタは、ウェブ・コンテンツ・ホスティング、電子商取引、ウェブ・アプリケーション、ビジネス・アプリケーションなど、様々なサービスを提供する。このようなセンタを管理するのは難題である。というのは、サービス・プロバイダは、提供される様々なサービス及びアプリケーション間の予測できない負荷集中及び分散を考慮して、競合する複数のアプリケーションにもたらされるサービス品質を管理しなければならないからである。これらの運用管理問題に対処するいくつかの管理ソフトウェア・パッケージが導入されている。これらのソフトウェア・システムは、監視、需要推定、負荷平衡、動的なプロビジョニング、サービス差別化、最適化されたリソース割振り、動的なアプリケーション配置を含めた機能を提供する。最後の機能、すなわち動的なアプリケーション配置が、本発明の主題である。
【０００３】
サービス要求は通常、１組のアプリケーションのそれぞれの、１つまたは複数のインスタンスを実行することによって満たされる。アプリケーションは、静的及び動的ウェブ・コンテンツへのアクセスと、エンタープライズ・アプリケーションと、データベース・サーバへのアクセスとを含む。アプリケーションは、ＨＴＴＰ（ハイパーテキスト転送プロトコル）ウェブ・サーバ、サーブレット、エンタープライズＪａｖａ（登録商標）  Ｂｅａｎｓ（ＥＪＢ）、またはデータベース照会によって提供することができる。特定のアプリケーションに対するサービス要求の数が増加したとき、アプリケーションの配置を担う管理ソフトウェアは、増大した負荷に対応するために、そのアプリケーションの追加インスタンスを配備する。アプリケーションのインスタンスを動的に配備及び除去するのを可能にするオンデマンドの管理環境を有することが、しばしば重要である。問題は、アプリケーション・インスタンスを開始及び停止するオーバヘッドを最小限に抑えながら、動的な負荷を満たすようにアプリケーション・インスタンスの数を動的に変更することである。
【０００４】
アプリケーションに対する負荷が変動するのに伴ってサーバ・ファーム中でアプリケーション・プロセスを自動的にインスタンス化することに関連する問題の１つは、各サーバ・マシンがいくらかの限られた数のアプリケーション・プロセスしか実行できないことである。特定のアプリケーションに対する要求メッセージは、そのアプリケーションのすべてのインスタンス間で分割される。したがって、各アプリケーション・インスタンスが異なるサーバを使用するとき、クラスタのサイズが、クラスタが性能劣化なしに維持できる負荷量に直接に影響する。
【０００５】
クラスタのサイズが不十分なとき、アプリケーション・ユーザは性能劣化または障害を被り、その結果、サービス・レベル・アグリーメント（ＳＬＡ）違反となる。現在、ＳＬＡ違反を回避するために、アプリケーション・プロバイダは一般に、ピーク負荷を処理するためのアプリケーション・インスタンスの数を過剰に用意している。この結果、通常動作条件の間はリソース利用が不十分になる。動的割振りは、サーバの現在負荷及びＳＬＡ目標に基づいてアプリケーション間でサーバを自動的に再割振りすることにより、容量浪費の問題を緩和する。
【０００６】
今日利用可能な配置アルゴリズムのほとんどは、集中型である。集中型手法は一般に、２つの配置操作の間で生じた変化にすぐに反応する能力を持たない。集中型解決では、単一のコントローラがいくつかのノードからの制約を処理する必要がしばしばある。さらに、各アプリケーションは通常、開始または停止するためにいくらかの時間を必要とする。この時間中に、再構成プロセスはローカル・マシン上のＣＰＵパワーのほとんどを使用する可能性があり、したがってそのサービス能力を部分的に混乱させる可能性がある。集中型解決は通常、システムの全体的な処理力が激しく低下するのを回避するために、変更が同時に起こらないような方法で変更をスケジュールするための増強を必要とする。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、アプリケーションに対する負荷が変動するのに伴って、サーバ・ファーム中でアプリケーション・プロセスを自動的にインスタンス化して、サーバ・ファームがアプリケーション・プロセスの数を動的に調節できるようにする問題に対処する。アプリケーション配置の非集中型解決は、集中型解決と比較して、いくつかの概念的利点を有することができる。第１に、非集中型配置では、アルゴリズムがシステム中の各マシン上で独立して非同期で実行されるので、システムは外部イベントにかかわらず継続的に再構成することができる。第２に、各ノードはローカル・リソースだけを管理するので、非集中型解決は複雑さがより低い。第３に、配置アルゴリズムが単一マシン上で実行される集中型解決とは異なり、各マシンは同一の機能を有するので、非集中型の場合は構成オーバヘッドがない。本発明は有利にも、サーバ上におけるコンピューティング・アプリケーションの動的な配置を最適化して、アプリケーションの割当ての変更を出来るだけ少なくしながらアプリケーション需要の全体を満たす。
【課題を解決するための手段】
【０００８】
本発明の例示的な一態様は、ノードのクラスタに対する非集中型のアプリケーション・リソース割振りの方法である。この方法は、ノード・クラスタ中のノード・サブセットからアプリケーションのリソース利用データをローカル・ノードで受信するように構成された受信操作を含む。ローカル・ノードは、それが実行している現在アプリケーション集合を含む。決定操作が、ローカル・ノードで実行される新しいアプリケーション集合を形成する。新しいアプリケーション集合は、ローカル・ノードによってローカルで計算される目的関数を最適化し、利用データに少なくとも部分的に基づく。修正操作が、新しい実行中アプリケーション集合に従って、どのアプリケーションがローカル・ノードで実行されるかを修正する。送信操作が、ローカル・ノードにおける新しいアプリケーション集合と現在アプリケーション集合との間のアプリケーション実行変更を、ローカル・ノードからノード・クラスタ中のノード・サブセットに知らせる。
【０００９】
本発明の別の例示的な態様は、ノードのクラスタに対する非集中型のアプリケーション・リソース割振りのためのシステムである。このシステムは、コンピュータ・プログラムを実行するように構成されたプロセッサと、プロセッサに接続され、コンピュータ・ネットワークを介してデータを送受信するように構成されたネットワーク・インターフェースとを備える。さらに、記憶デバイスがコンピュータ・プログラムを組み入れる。コンピュータ・プログラムは、ノード・クラスタ中のノード・サブセットからアプリケーションのリソース利用データをローカル・ノードで受信すること、ローカル・ノードによってローカルで計算される目的関数を最適化する、ローカル・ノードで実行される新しいアプリケーション集合を、利用データに少なくとも部分的に基づいて決定すること、新しい実行アプリケーション集合に従って、どのアプリケーションがローカル・ノードで実行されるかを修正すること、及び、ローカル・ノードにおける新しいアプリケーション集合と現在アプリケーション集合との間のアプリケーション実行変更をローカル・ノードからノード・クラスタ中のノード・サブセットに送信することを行うように構成されたコンピュータ実行可能命令を含む。
【００１０】
本発明の他の例示的な態様は、有形媒体に組み入れられるコンピュータ・プログラム製品である。このコンピュータ・プログラム製品は、ノード・クラスタ中のノード・サブセットからアプリケーションのリソース利用データをローカル・ノードで受信すること、ローカル・ノードによってローカルで計算される目的関数を最適化する、ローカル・ノードで実行される新しいアプリケーション集合を、利用データに少なくとも部分的に基づいて決定すること、新しい実行アプリケーション集合に従って、どのアプリケーションがローカル・ノードで実行されるかを修正すること、及び、ローカル・ノードにおける新しいアプリケーション集合と現在アプリケーション集合との間のアプリケーション実行変更をローカル・ノードからノード・クラスタ中のノード・サブセットに送信することをプログラムに行わせるように構成されたコンピュータ可読プログラム・コードを含む。
【００１１】
本発明の以上及び他の特徴、有用性、利点は、添付の図面に示す本発明の様々な実施形態に関する後続のより具体的な記述から明らかになるであろう。
【発明を実施するための最良の形態】
【００１２】
サーバ上におけるコンピューティング・アプリケーションの動的配置を最適化してアプリケーション需要全体を満たすために本発明がどのように利用されるかを、以下の記述に詳しく述べる。本発明の記述全体を通して、図１〜１２を参照する。図を参照する際、全体を通して図示される同じ構造及び要素は、同じ参照番号で示す。
【００１３】
問題の公式化
動的なアプリケーション配置の問題は、次のように公式化される。すなわち、メモリ容量Γ１，．．．，Γｍ及びサービス容量（１単位時間当たりにサービスできる要求の数）Ω１，．．．，Ωｍを有するｍ個のサーバ１，．．．，ｍがあるとする。また、メモリ要件γ１，．．．，γｎを有するｎ個のアプリケーション１，．．．，ｎがあるとする。アプリケーションｊは、期間ｔ中に、要求の数ωｊｔをサービスしなければならない。
【００１４】
時間ｔにおけるこの問題に対する実行可能解は、サーバへのアプリケーション作業負荷の割当てである。各アプリケーションは、複数のサーバに割り当てられる（複数のサーバ上で複製される）ことができる。アプリケーションｊが割り当てられる全てのサーバｉに対して、この解は、各サーバがこのアプリケーションのために処理する要求の数ωｉｊｔを指定しなければならない。すべてのアプリケーションｊ及び時間ステップｔに対するΣｉωｉｊｔがωｊｔに等しくなければならない。全てのサーバに対して、メモリ制約及び処理制約が考慮されなければならない。ある１つのサーバに割り当てられるアプリケーションのメモリ要件の合計は、そのメモリ容量Γｉを超えることはできず、Σｉωｉｊｔすなわち時間ステップｔ中にこのサーバによってサービスされる要求の総数はサービス容量Ωｉを超えることはできない。１つのサーバへのアプリケーション割当て（コピー）はそれぞれ完全なメモリ・コストを被るが、処理負荷はコピー間で分割されることに留意されたい。
【００１５】
目的は、時間ステップｔにおける解を見つけることであり、当該解は時間ステップｔ−１における解と著しく異ならない。より正式には、全ての実行可能解を用いて、二部グラフ（Ａ，Ｓ，Ｅｔ）を関連付ける。Ａは、時間ステップｔでサーバｉに割り当てられる（またはサーバｉ上にコピーがある）アプリケーションｊの集合を表す。目的関数は、
【００１６】
（数１）
｜ＥｔφＥｔ−１｜
【００１７】
すなわち２つの辺集合の対称差である濃度（cardinality）を最小化することである。これは、時間ｔで遮断またはロードされなければならないアプリケーシン・インスタンスの数である。
【００１８】
システム・モデル
本発明の一実施形態は、図１、２、及び３に一般に示すネットワーク・システム中で実現される。図１に、本発明によって企図される例示的なシステムの物理インフラストラクチャ１０２を示す。物理インフラストラクチャ１０２は、コンピュータ・ネットワーク１０６に接続された１つまたは複数のエントリ・ポイント１０４を含む。コンピュータ・ネットワーク１０６は、ローカル・エリア・ネットワーク（ＬＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、またはこれらの組合せであってよい。コンピュータ・ネットワーク１０６は、インターネットなどの公衆ネットワーク、またはイントラネットやその他の独自仕様の通信システムなどの私設ネットワーク、あるいはその両方として構成できることが企図される。ＴＣＰ／ＩＰやＵＤＰなど、当業者に知られている様々なトポロジ及びプロトコルをネットワーク１０６によって利用することができる。さらに、コンピュータ・ネットワーク１０６は、ルータ、スイッチ、ブリッジ、リピータなど、当技術分野で知られている様々なネットワーキング・デバイスを含むことができる。
【００１９】
物理インフラストラクチャ１０２はさらに、いくつかのノード１０８〜１１８を含む。これらのコンポーネントは、ルータ、スイッチ、ハブなどのネットワーキング・デバイス１２０〜１２４を使用して相互接続される。エントリ・ポイント１０４は、入来した要求をノード１０８〜１１８にリダイレクトするスイッチである。コンピュータ、ハードウェア層４〜７スイッチ、さらにはメインフレームなど、いくつかのタイプのハードウェアがこの機能を実施することができる。ノード１０８〜１１８は、デスクトップ・コンピュータ、サーバ、ラップトップとすることができ、あるいはＣＰＵ及びメモリを備えネットワークに接続できる他の任意のハードウェア・デバイスとすることができる。
【００２０】
図２に、図１に示した物理インフラストラクチャの最上部に構成される、例示的なシステムの論理トポロジ２０２を示す。エントリ・ポイント１０４は、論理リンクを介して多数のノード（場合によってはシステム中のすべてのノード）に接続される。説明のために、図２では、エントリ・ポイントとノードとの間の論理リンクを破線で示す。エントリ・ポイントは、ラウンド・ロビンやランダム転送など様々な転送ポリシーを使用して、入来した要求をノードに転送する。ノード１０８〜１１８は論理オーバーレイ中で自己組織化し、その中では各ノードがその近傍のみと通信する。したがって、ノード・クラスタ中のノードのサブセットが、ノードの近傍に対応して定義される。ノード間の論理ピアツーピア・リンクを実線で示す。通常、ノードの近傍の数は、システム中のノードの総数と比較して少ない。任意のオーバーレイ構築アルゴリズムを使用して、ノードに近傍の集合を割り当てることができる。つまりノード・サブセットを識別する。得られるオーバーレイは、スモールワールドやランダム・グラフなど、様々なタイプとすることができる。論理リンクはいくつかの方式で実現することができる。可能性の１つは、論理リンクの両端の各ノード間でＴＣＰ接続を開設することである。別の可能性は、各ノードが近傍のローカル・リストを保持し、これらの近傍に通信を限定することである。
【００２１】
一実施形態では、ノード１０８〜１１８は、比較的安定したオーバーレイ近傍の集合を維持し、配置周期ごとに状態情報を収集する。別の実施形態では、ノード１０８〜１１８は、安定した近傍の集合を使用する必要はなくてよい。そうではなく、ノード１０８〜１１８は、ゴシップ・プロトコルを実行してシステム中の他のノードを発見し、異なる配置周期で異なるノードによって状態情報を収集することができる。
【００２２】
図３に、単一ノード上で実行される例示的なソフトウェア３０２を示す。本発明の一実施形態では、すべてのノードは、非集中型の配置アルゴリズムのコンテキストで、同一の機能を有する。１つのノードが、１つまたは複数のアプリケーション・プロセス３０４〜３０８を実行することができる。各アプリケーション・プロセスは、単一のアプリケーション・タイプに対する要求を処理する（アプリケーション・タイプをＡ１，Ａ２，．．．Ａｎで示す）。
【００２３】
各アプリケーションは、２つのタイプのパラメータで特徴付けることができる。すなわち、（１）アプリケーションの実行に必要なリソースの、負荷独立の要件、及び（２）アプリケーションに課される外部負荷または需要に応じた、負荷依存の要件である。負荷独立の要件の例は、メモリ、通信チャネル、及びストレージである。負荷依存の要件の例は、現在のまたは予測される要求率、ＣＰＵ（中央処理装置）周期、ディスク活動、及び実行スレッドの数である。
【００２４】
同様に、ノード（例えばサーバ）は、２つのパラメータで特徴付けることができる。すなわち、（１）ノード上でアプリケーションをホストするのに利用可能なリソースの量を表す、負荷独立の容量、及び（２）アプリケーションのサービスに対する要求を処理するのに利用可能な容量を表す、負荷依存の容量である。
【００２５】
配置実行部（placement executor）３１０、配置コントローラ３１２、及びアプリケーション・プロファイラ３１４は、配置機能を提供するように構成されたソフトウェア・オブジェクトである。配置実行部３１０は、アプリケーション・プロセスを停止または開始する能力を有する。アプリケーション・プロファイラ３１４は、要求到着率、１つのアプリケーション・インスタンスによって利用される総メモリ、アプリケーション要求によって消費される平均ＣＰＵ周期数など、各ローカル・アプリケーションに関する統計を収集する。本発明の特定の一実施形態では、アプリケーション・プロファイラ３１４は、要素の抽象集合の、負荷独立の容量の集合及び負荷依存の容量の集合を定義する。これについては後でより詳細に論じる。
【００２６】
配置コントローラ３１２は、非集中型の配置アルゴリズムのコア・ロジックを含む。配置コントローラ３１２は、目的関数に基づいて各ノード上のアプリケーションの配置を動的に再構成して、すべてのノード上におけるアプリケーションのグローバルな配置を最適化する。
【００２７】
配置コントローラ３１２は、各ノード上で独立して非同期で実行される。配置アルゴリズムの２つの実行の間の時間を、本明細書では実行周期と呼ぶ。配置アルゴリズムについては後でより詳細に述べる。
【００２８】
各ノードは、グローバル配置行列Ｐの複製を維持する。グローバル配置行列は、複数のノード及び複数のアプリケーションを要素の抽象集合として記述する。図４に、グローバル配置行列４０２の例示的な一構造を示す。行列の各行はアプリケーションに対応し、各列はノードに対応する。行列Ｐの要素は次のように定義される。すなわち、アプリケーションａがノードｎ上で実行される場合はＰａ，ｎ＝１、そうでない場合はＰａ，ｎ＝０である。グローバル配置行列を更新及び維持するプロセスは、完全に非集中型である。
【００２９】
非集中型の配置アルゴリズム
配置コントローラは、配置アルゴリズムを３段階で実行する。最初に、配置コントローラは、システムの現在状態に関する（部分的な）情報を収集する。次に、この情報に基づいて、配置コントローラは、来たる実行周期の間にどのアプリケーションがローカル・ノード上で実行されるべきか決定する。最後に、配置コントローラは、配置アルゴリズムのローカル決定を反映するグローバル配置行列の更新のセットをシステム中で配布する。
【００３０】
状態情報の収集
スケーラビリティを保証するために、各ノードは、小さい近傍集合から状態情報を取り出す。オーバーレイ構築機構が、各ノードの近傍を定義する論理トポロジを構築する。
【００３１】
図５に、本発明によって企図される、状態情報が近傍間で交換される方法の１つを示す。ノード５０２と５０４は論理的な近傍であると仮定する。ノード５０４上で稼動する配置コントローラ５０６は、矢印５１０で表されるように、ノード５０２上で稼動する配置コントローラ５０８に状態情報を要求する。配置コントローラ５０８は、要求を受け取ると、矢印５１４で表されるように、アクティブ・アプリケーションのリストを配置実行部５１２に要求する。これに応答して、配置実行部５１２はリストを取り出し、矢印５１６で表されるように配置コントローラ５０８にリストを送る。配置コントローラ５０８はまた、矢印５２０及び５２２で表されるように、アプリケーション・プロファイラ５１８からアプリケーション統計も得る。このプロセスの最後に、配置コントローラ５０８は、以下の情報を収集する。すなわち、ローカルにおいてアクティブなアプリケーションのリスト（ａ１．．．ａｍ）、各アプリケーションに与えられる（delivered）ＣＰＵ周期の数（ωａ１ｄｅｌｉｖｅｒｅｄ．．．ωａｍｄｅｌｉｖｅｒｅｄ）、各アプリケーションのメモリ要件（γａ１．．．γａｍ）、各アクティブ・アプリケーションに対してローカルで受ける需要（ωａ１ｒｅｑｕｅｓｔｅｄ．．．ωａｍｒｅｑｕｅｓｔｅｄ）、ならびに、グローバル配置行列中にアクティブなエントリがなくネットワーク中のどこでも提供されないアプリケーションに対してローカルで受ける需要である。配置コントローラ５０８は、矢印５２４で表されるように、この情報を配置コントローラ５０６に返送する。これで２つの論理的な近傍間での情報交換は完了する。
【００３２】
配置コントローラ５０６は、その近傍から情報を取り出すのに加えて、ローカルの配置実行部５２６及びローカルのアプリケーション・プロファイラ５２８からローカル情報も収集する。
【００３３】
再構成段階
図６に、本発明の一実施形態によって実施される再構成段階のフローチャートを示す。以下に詳細に論じるとおり、このフローチャートの操作は、多数のメトリックスを最適化するようにノード上のアプリケーションの配置を分散方式で動的に再構成することによって、１つまたは複数の負荷依存リソース制約及び１つまたは複数の負荷独立リソース制約の元で、非集中型かつオンデマンドのアプリケーション・リソース割振りを可能にする。図示の論理的操作はハードウェアまたはソフトウェア中で、あるいは両方の組合せで実施できることに留意されたい。実装形態は、本発明を実施するシステムの性能要件に応じて選択できる問題である。したがって、本明細書に述べる本発明の実施形態を構成する論理的操作は、代替的に操作、ステップ、またはモジュールとも言われる。
【００３４】
構築操作６０２で、配置コントローラは、前段階で収集した近傍の状態を入力として、実行中アプリケーションの集合Ｒ＝｛ｒ１．．．ｒｒ｝及び待機中アプリケーションの集合Ｓ＝｛ｓ１．．．ｓｓ｝を構築する。Ｒは、ローカル・ノード上で現在アクティブなアプリケーションを含む。Ｓは、そのノードの近傍中で実行されているがそのノード自体では実行されていないアプリケーションか、あるいはシステム中のどこでも提供されていないアプリケーションを含む。Ｓは、前段階で収集した近傍情報を使用して構築される。
【００３５】
Ｒ中のアプリケーションは、それらの密度の低い順にソートされ、この密度は、アプリケーションｒに与えられる負荷をｒのメモリ使用で割った値、すなわち比率（ωｒｄｅｌｉｖｅｒｅｄ／γｒ）に等しい。Ｓ中のアプリケーションは、それらの残余密度の高い順にソートされ、この残余密度は、アプリケーションｓに対する満たされない需要をｓのメモリ使用で割った値、すなわち以下の値に等しい。
（Σｎ∈ｎｅｉｇｈｂｏｒｓ［ωｎｓｄｅｌｉｖｅｒｅｄ−ωｎｓｒｅｑｕｅｓｔｅｄ］）／γｓ
【００３６】
満たされない需要が０である待機中アプリケーションについては、追加のインスタンスを開始する必要がないので、これらのアプリケーションはＳから除去される。構築操作６０２が完了すると、制御は判定操作６０４に移行する。
【００３７】
判定操作６０４で、待機中集合を調べる。待機中集合が空の場合は、アルゴリズムは完了する。待機中集合が１つまたは複数のアプリケーションを含む場合は、制御は移動操作６０６に移行する。
【００３８】
移動操作６０６で、配置コントローラは、１つまたは複数の実行中アプリケーションから出来るだけ多くの負荷を近傍に移動することを試みる。アプリケーションＡに対する負荷を移動することは、１つまたは複数の近傍が（ａ）アプリケーションＡのインスタンスを実行しており（ｂ）遊休ＣＰＵ容量を有するときに可能である。移動操作６０６によって実施される負荷移動プロセスは、アルゴリズムの性能を向上させることのできるオプション・ステップであることに留意されたい。移動操作６０６の完了後、制御は初期化操作６０８に移行する。
【００３９】
初期化操作６０８は制御ループを開始し、この制御ループ中で配置コントローラは、ローカルＣＰＵ利用が最大になるようにして、ローカル・ノードで実行される最適なアプリケーション集合を計算する。初期化操作６０８では、アプリケーションの数が０に設定され、新しい実行中集合が現在実行中集合に設定され、最大ＣＰＵ利用が初期ＣＰＵ利用に設定される。
【００４０】
次に、制御は操作６１０、６１２、６１４、６１６、６１８のループに移行する。このループ中で配置コントローラは、ローカル・ノード上のＣＰＵ利用が最大になるようにしてＲの部分集合をＳの部分集合で置き換えることを試みる。所与の２つの集合ＲとＳについての可能な再構成の組合せの数は、非常に多い可能性がある。以下のヒューリスティックが、この問題のサイズを、（ｒ＋１）回の反復、及び多くても（（ｒ＋１）＊ｓ）回の操作に縮小する。ここで、ｒはＲのサイズであり、ｓはＳのサイズである。
【００４１】
配置コントローラは、（ｒ＋１）回の反復を実行し、この間に、Ｒからのアプリケーションを停止してそれらをＳからのアプリケーションで置き換えることの影響を調べる。反復に関する記述で言及する開始及び停止の操作は、仮定的なものに過ぎない。配置コントローラは、一連の開始及び停止の操作が行われると仮定し、次いで、これらの操作がローカル状態に及ぼすであろう影響を評価する。
【００４２】
第１の反復中、コントローラは、どんな実行中アプリケーションも停止しない。ローカル・ノードが遊休状態のＣＰＵリソース及びメモリ・リソースを有する場合は（Ωａｖａｉｌａｂｌｅ＞０及びΓａｖａｉｌａｂｌｅ＞０）、コントローラは１つまたは複数の待機中アプリケーションを開始することを試みる。
【００４３】
反復ｋの間、コントローラは、実行中アプリケーション｛ｒ１．．．ｒｋ−１｝を停止した後に利用可能になるメモリ・リソース及びＣＰＵリソースを計算する。次いでコントローラは、利用可能なリソースをＳ中のアプリケーションに割り振る。最初、ノードは、ｓ１（Ｓからの第１のアプリケーション）を、利用可能なメモリに適合させることを試みる。この操作が成功した場合は（γｓ１≦Γavailable）、コントローラは、ｓ１に対する満たされないＣＰＵ需要の全体を満たすことを試みる。この結果、ｍｉｎ（（ωｓ１ｒｅｑ−ωｓ１ｄｅｌ），Ωａｖａｉｌａｂｌｅ）個のＣＰＵ周期がｓ１に割り振られる。ｓ１に利用可能なメモリが十分にない場合は、コントローラはＳ中の次のアプリケーションに進む。割り当てる残余メモリまたはＣＰＵがなくなったとき（Ωａｖａｉｌａｂｌｅ＝０及びΓａｖａｉｌａｂｌｅ＝０）、またはＳ中のすべてのアプリケーションについて考察し終えたとき、反復は停止する。
【００４４】
アプリケーションを開始または停止すると、ある時間量にわたってノードのＣＰＵリソースが消費される。各構成ごとに、変更コストが総ＣＰＵ利用から差し引かれる。例えば、アプリケーションの開始がローカルＣＰＵリソースを１５秒間消費し、実行周期の長さが１５分である場合、ノードの総処理力の１．６７％が再構成プロセスに割り振られることになり、ＣＰＵの残りの９８．３３％が要求処理に利用可能である。
【００４５】
反復ｋの終わりに得られる各集合Ｒｋにつき、コントローラはローカルＣＰＵ利用を計算する。ローカルＣＰＵ利用を最大にする集合Ｒｋが、最適な構成であり、これは設定操作６２０で提示される。
【００４６】
構成変更のコミット及び公示
図７の流れ図に、配置アルゴリズムの最終段階の論理を示す。アルゴリズムは判定操作７０２で開始し、実行中アプリケーションの集合を調べる。集合に変化がない場合は、プロセスは終了する。しかし、配置コントローラがローカル構成に何らかの変更を加えた場合は、制御は計算操作７０４に進む。計算操作７０４で、停止または開始するアプリケーションの集合が計算される。例えば、ノード上のアクティブ・アプリケーションの現在集合をＲとし、アルゴリズムの前の（再構成の）段階で配置コントローラによって計算された最適な構成をＲｋとする。計算操作７０４で、停止するアプリケーションの集合（Ｒ＼Ｒｋ）及び開始するアプリケーションの集合（Ｒｋ＼Ｒ）を計算する。公示操作７０６で、ノードは配布機構を使用して、システム中のすべてのノードまたはそのサブセットに変更を知らせる。
【００４７】
判定操作７０８で、得られた停止するアプリケーションの集合を調べる。停止するアプリケーションの集合が空でない場合は、制御は停止操作７１０に移行し、アプリケーションの集合は停止される。同様に、判定操作７１２で、開始するアプリケーションの集合が空でない場合は、開始操作７１４でアプリケーションの集合を開始する。
【００４８】
新しい構成が有効になるためには、配置コントローラがＲ＼Ｒｋ中のアプリケーションを停止してＲｋ＼Ｒ中のアプリケーションを開始する必要がある。アプリケーションの開始または停止は、ある時間量にわたってノードのＣＰＵパワーを大量に消費する。構成決定が行われた時点と、変更が有効になりノードがその全容量で動作する時点との間の遅延は、以下のとおりである。
ｔｃｏｍｍｉｔ＝Σａ∈Ｒ＼Ｒｋ  ｔａｓｔｏｐ＋Σａ∈Ｒｋ＼Ｒ  ｔａｓｔａｒｔ
【００４９】
ｔｃｏｍｍｉｔ期間中は、ノードのＣＰＵパワーが大量に再構成プロセス（アプリケーションの停止及び開始）に割り当てられるので、ノードはその全容量で動作することができない。配置アルゴリズムがうまく完了した時にシステムのリセットを通知するために、配置コントローラは、公示操作７１６で、システム中のすべてのノードまたはそのサブセットに構成変更の完了を知らせる。配置コントローラから発行される各公示メッセージは、配置行列の使用に応じて、システム中のすべてのノードに届くか、またはシステム中のノードのサブセットだけに届くものとすることができる。一実施形態では、配置変更はシステム中のすべてのノードに知らされる。公示遅延ｔｎｏｔｉｆｙは、公示がシステム中の他のノードに届くのに必要な時間を表す。ノード上で行われた配置変更を配布する方法にはいくつかある（例えば同報通信）。次のセクションでは、本発明のコンテキストにおける一実装形態について論じる。
【００５０】
グローバル配置行列の更新及び維持
本発明の特定の一実装形態では、ノードはゴシップ・プロトコルを使用して配置変更を配布し、そのグローバル配置行列のローカル複製中で更新済み情報を維持する。図８の流れ図に、配置行列の変更を伝搬するための例示的な一手順を示す。各ノードは、所定の集約期間（例えば一秒）中にその近傍から受信したすべてのメッセージを集約し、集約したメッセージのサブセットをその各近傍に返送する。例えば、ノード１０８が配置アルゴリズムの実行を終了し、その構成を修正したと仮定する。ノード１０８は、線８０２及び８０４で表されるように、その近傍であるノード１１４及び１１８に更新を送信し、それらのノードに変更を通知する。
【００５１】
ノード１１４及び１１８は、これらの変更メッセージを受け取ると、すぐにこれらを再送するのではなく、集約期間が過ぎるまで待機する。集約期間が終わる前にノード１１４または１１８が受信したかあるいは発生させたメッセージが他にあれば、ノード１０８から受信した更新と集約されることになる。それぞれの集約期間が終了すると、ノード１１４及び１１８は、ノード１０８から受信した更新を含めて、集約したメッセージをノード１１６及び１１０にそれぞれ送信する（線８０６及び８０８）。ノード１１４及び１１８は、ノード１０８から受信した更新をノード１０８に再送することはせず、集約期間中に他のソースから収集したメッセージをノード１０８に送信することになる。同様に、ノード１１０及び１１６は、線８１０及び８１２で表されるように、１０８から発生した更新をノード１１２に送信する。集約期間を導入することで、集約期間中に各ノードが発生させるメッセージの数が制限されるので、この手順は非常にスケーラブルである。
【００５２】
前のセクションで述べたゴシップ手順は、知らされる全ての変更をすべてのノードが受信することを、高確率で保証する。しかし、いくつかのノードが特定のメッセージをまったく受信しない確率もゼロではない。したがって、時間の経過に伴ってエラーが累積する可能性があり、グローバル配置行列のローカル複製の間で不整合が生じることになる。こうならないようにするために、各ノードは、前述したのと同じゴシップ・プロトコルを使用して、その完全なアクティブ・アプリケーション・リストを定期的に送信する。このメッセージを受信したノードは、これを使用して、その配置行列のローカル・コピーを相応に更新する。配置行列中の各エントリは、タイマに関連付けられている。エントリが所定の時間しきい値にわたって更新されなかった場合、このエントリはタイムアウトし、配置行列から削除される。
【００５３】
システムの安定性をさらに向上させる
以下に述べる技法は、システム中で行われる変更を直列化する。これらの技法は、配置手順の間に同じ情報に基づく同時変更が行われないことを確実にする助けとなる。このオプション・プロセスは、システム・コンポーネントが、同じリソースまたはアプリケーションに影響を与える別の決定を行う前に配置決定の影響を観察及び評価するという意味で、システムを安定させる。ロック要求には２つのタイプがある。すなわち、（ａ）システム中ですでに実行されているアプリケーションに対するロック、及び（ｂ）システム中のどこでも実行されていないアプリケーションに対するロックである。
【００５４】
図９の例示的な流れ図に、システム中ですでに実行されているアプリケーションに対するロックをノードが得る方法を示す。ノード１１８が配置アルゴリズムを実行して、アプリケーションＡ１９０２の停止（または開始）を決定したと仮定する。また、他のノードはこのアプリケーションに対するロックを設定していないと仮定する。ノード１１８は、線９０４及び９０６に示すように、Ａ１に対するロックをその近傍ノード１０８及び１１０に要求する。ノード１０８及び１１０がまだアプリケーションＡ１に対するロックを有さない場合、これらのノードは、線９０８及び９１０でそれぞれ示すように、その近傍であるノード１１４及び１１２にロック要求を転送する。ノード１１２及び１１４がまだアプリケーションＡ１に対するロックを有さない場合、これらのノードはロックを設定し、ノード１０８及び１１０からの要求にそれぞれ応答する（線９０８及び９１０）。ノード１０８及び１１０は、肯定の応答を受信すると、それらのロックを設定してノード１１８に応答する（線９０４及び９０６）。ノード１１８は、ノード１０８及び１１０から肯定の応答を受信すると、ロックを得て配置変更に進む。
【００５５】
ロック要求は、要求の発生源からちょうど２つの論理ホップ分だけ伝搬する。ロックは、配置アルゴリズムによって停止または開始されるべき各アプリケーションごとに得られなければならない。いずれかの時点でロック要求が失敗した場合は、ロック予約はロールバックし、ロックを要求したノードは待機して配置アルゴリズムを再実行する。ロック要求が成功した場合は、ノードは配置変更に進み、この手順の完了時にその近傍をロック解除する。ロックを得た後でノードが失敗する可能性に対処するために、ロックはタイムアウトを有し、タイムアウト後は失効する。
【００５６】
図１０に、システム中のどこでも実行されていないアプリケーションをアクティブ化するためにロックを得るプロセスを示す。アプリケーションＡ１はシステム中のどのノード上でも実行されておらず、Ａ１に対するロックを保持しているのは、ハッシュ関数を使用して決定されるようにノード１１６であると仮定する。ノード１１６は、アプリケーションＡ１に対する需要に関して、他の全てのノードから更新を受信する。例えば、ノード１０８は、配置アルゴリズムを実行すると、アプリケーションＡ１に対する需要を受ける。ノード１０８は、矢印１００２で表されるように、需要をノード１１６に送信する。ノード１１６は、矢印１００４で表されるように、アプリケーションＡ１に対する総需要（最後の配置周期にわたって計算される）で応答する。ノード１０８は、その待機中アプリケーションの集合を構築するとき、ノード１１６から受信した需要をアプリケーションＡ１に割り当てる。ノード１１８が、同じ手順に従い、配置アルゴリズムに従ってアプリケーションＡ１の開始を決定すると仮定する。ノード１１８は、矢印１００６で表されるように、アプリケーションＡ１に対するロックをノード１１６に要求する。ノード１１６はロックの利用可能性をチェックし、利用可能であれば、矢印１００８で表されるようにロックをノード１１８に送信する。ノード１１８は、ロックを受信すると、前述のゴシップ・プロトコルを使用して、アプリケーションＡ１を開始しようとしていることを他のノードに知らせる。アプリケーションＡ１を開始した後、ノード１１８は、矢印１０１０で表されるようにノード１１６からのロックを解放する。
【００５７】
図１１を参照して、本発明によるネットワーク・ノード１１０２の例示的な一実施形態を示す。本発明が有用である可能性のあるネットワーク・ノードの１つ１１０２は、汎用コンピュータを包含する。このようなコンピュータの例には、サン・マイクロシステムズ株式会社から提供されるＳＰＡＲＣ（登録商標）システムや、インターナショナル・ビジネス・マシーンズ・コーポレーション及びその他の様々なコンピュータ製造元から入手可能なＰｅｎｔｉｕｍ（登録商標）ベースのコンピュータが含まれる。ＳＰＡＲＣはサン・マイクロシステムズ株式会社の登録商標であり、Ｐｅｎｔｉｕｍはインテル・コーポレーションの登録商標である。
【００５８】
ネットワーク・ノード１１０２は、処理ユニット１１０４と、システム・メモリ１１０６と、システム・メモリ１１０６を処理ユニット１１０４に接続するシステム・バス１１０８とを備える。システム・メモリ１１０６は、読取り専用メモリ（ＲＯＭ）１１０８及びランダム・アクセス・メモリ（ＲＡＭ）１１１０を備える。ＲＯＭ１１０８には、起動中などにネットワーク・ノード１１０２内の要素間で情報を転送する助けとなる基本ルーチンを含むＢＩＯＳ（basic input/output system）１１１２が記憶されている。
【００５９】
ネットワーク・ノード１１０２はさらに、ハード・ディスク・ドライブ１１１４と、磁気ディスク・ドライブ１１１６（取外し可能な磁気ディスク１１１８に対する読み書きのため）と、光学ディスク・ドライブ１１２０（ＣＤ−ＲＯＭディスク１１２２の読取り、及びその他の光学媒体に対する読み書きのため）とを備える。ハード・ディスク・ドライブ１１１４、磁気ディスク・ドライブ１１１６、及び光学ディスク・ドライブ１１２０は、それぞれハード・ディスク・インターフェース１１２４、磁気ディスク・インターフェース１１２６、及び光学ディスク・インターフェース１１２８によってシステム・バス１１０８に接続される。ドライブ及びそれらに関連するコンピュータ可読媒体は、ノード１１０２のための不揮発性記憶域を提供する。コンピュータ可読媒体はハード・ディスク、取外し可能な磁気媒体、及び取外し可能な光学媒体を指すが、フラッシュ・メモリ・カードなど、コンピュータによって読取り可能な他のタイプの媒体も、この例示的なノード１１０２中で使用できることを当業者は理解されたい。
【００６０】
ドライブ及びＲＡＭ１１１０にはいくつかのプログラム・モジュールを記憶することができ、これらにはオペレーティング・システム１１３０、非集中型の配置アプリケーション１１３２、グローバル配置行列１１３４、ならびにその他のプログラム・モジュール及びデータ（図示せず）が含まれる。上で論じたように、ノード１１０２は、アプリケーションの配置を分散方式で動的に再構成するように構成される。
【００６１】
ユーザは、キーボード１１３６、及びマウス１１３８などのポインティング・デバイスを介して、ノード１１０２にコマンド及び情報を入力することができる。その他の入力デバイス（図示せず）には、マイクロホン、モデム、ジョイスティック、ゲーム・パッド、衛星受信アンテナ、スキャナなどを含めることができる。これら及びその他の入力デバイスは、システム・バス１１０８に接続されたシリアル・ポート・インターフェース１１４０を介して処理ユニットに接続されることが多い。
【００６２】
モニタ１１４２またはその他のタイプの表示デバイスも、ビデオ・アダプタ１１４４などのインターフェースを介してシステム・バス１１０８に接続される。モニタに加えて、ノード１１０２は、スピーカやプリンタなど、その他の周辺出力デバイス（図示せず）を備えてもよい。
【００６３】
ノード１１０２は、１つまたは複数のリモート・デバイスへの論理接続を使用して、ネットワーク化された環境で動作する。リモート・デバイスは、サーバ、ルータ、ピア・デバイス、またはその他の一般的なネットワーク・ノードであってよい。ネットワーク化された環境で使用されるとき、ノード１１０２は通常、ネットワーク・インターフェース１１４６を介してネットワーク１１４８に接続される。ネットワーク化された環境では、ノード１１０２に関して示すプログラム・モジュールまたはその一部を、１つまたは複数のリモート・メモリ記憶デバイスに記憶することができる。
【００６４】
図１２に移り、本発明の一実施形態によって企図される、ノードのクラスタに対する非集中型のアプリケーション・リソース割振りの例示的なフローチャートを示す。受信操作１２０２は、ノード・クラスタ中のノード・サブセットからアプリケーションのリソース使用データをローカル・ノードで受信するように構成される。本発明の特定の一実施形態では、全てのノードは、その各近傍から以下の情報を取り出す。
（ａ）アクティブな（実行中の）アプリケーションのリスト
（ｂ）これらのアクティブ・アプリケーションそれぞれに対する需要と供給
（ｃ）その近傍がグローバル配置行列を使用してルーティングすることのできなかった、システム中のどこでも提供されていないアプリケーションに対する需要
【００６５】
この情報に基づいて、ノードは、実行中アプリケーション及び待機中アプリケーションという２つのアプリケーション集合をローカルで構築する。
【００６６】
ローカル・ノードは、それが実行しているアプリケーションの現在集合を含む。実行中アプリケーション集合及び待機中アプリケーション集合により、決定操作１２０４を利用して、ローカル・ノードで実行される新しいアプリケーション集合が形成される（この操作の詳細は上で論じた）。新しいアプリケーション集合は、ローカル・ノードによってローカルで計算される目的関数を最適化するように構成され、利用データに少なくとも部分的に基づく。本発明の一実施形態では、目的関数は、ローカル・ノードのＣＰＵ利用を最大にする関数とすることができる。しかし、本発明によりその他の目的関数を利用してもよいことが企図される。例えば、目的関数は、電力消費を最小限にするものであってもよく、ＣＰＵ需要に関係する他の任意の関数であってもよい。
【００６７】
修正操作１２０６が、新しい実行中アプリケーション集合のうちのどのアプリケーションがローカル・ノードで実行されるかを決定する。送信操作１２０８が、ローカル・ノードにおける新しいアプリケーション集合と現在のアプリケーション集合との間で実行が変更されるアプリケーション情報を、ローカル・ノードからノード・クラスタ中のノード・サブセットに知らせる。
【００６８】
本発明に関する以上の記述は、例示及び記述の目的で提示した。これは網羅的なものでもなく、また開示した正確な形に本発明を限定するものでもなく、上記の教示に鑑みて他の修正及び変形も可能である。したがって、開示した実施形態は、本発明の原理及びその実際の適用を最もよく説明して、それにより、企図される特定の使用に適合された様々な実施形態及び様々な修正形態で当業者が本発明を最もよく利用できるようにするために、選択し記述した。添付の特許請求の範囲は、従来技術によって限定される範囲を除いては、本発明のその他の代替実施形態も含むと解釈されるものとする。
【図面の簡単な説明】
【００６９】
【図１】例示的なシステムの主要コンポーネント及びそれらの物理的な相互接続のブロック図である。
【図２】システム・コンポーネント間の論理的な接続のブロック図である。
【図３】例示的なシステムの一部である各ノード上で実行されるソフトウェア・プログラムを示すブロック図である。
【図４】グローバル配置行列の例示的な構造を示すブロック図である。
【図５】ノードがその近傍から状態情報を取り出す例示的な方法を示す流れ図である。
【図６】本発明の一実施形態による、非集中型の配置アルゴリズムの再構成段階の論理を示す流れ図である。
【図７】本発明の一実施形態による、配置アルゴリズムのコミット段階の論理を示す流れ図である。
【図８】本発明の一実施形態による、配置更新がシステム中で伝搬する方法を示す流れ図である。
【図９】本発明の一実施形態による、既存のアプリケーションを再構成するときのシステムの安定性を維持するために配置更新が直列化される方法を示す流れ図である。
【図１０】本発明の一実施形態による、新しいアプリケーションをアクティブ化するときのシステムの安定性を維持するために配置更新が直列化される方法を示す流れ図である。
【図１１】本発明を組み入れたネットワーク・ノードの例示的な一実施形態を示す図である。
【図１２】本発明によって企図される、ノードのクラスタに対する非集中型のアプリケーション・リソース割振りの例示的なフローチャートである。
【符号の説明】
【００７０】
１０２  例示的なシステムの物理インフラストラクチャ
１０４  エントリ・ポイント
１０６  コンピュータ・ネットワーク
１０８  ノード
１１０  ノード
１１２  ノード
１１４  ノード
１１６  ノード
１１８  ノード
１２０  ネットワーキング・デバイス
１２２  ネットワーキング・デバイス
１２４  ネットワーキング・デバイス
２０２  例示的なシステムの論理トポロジ
３０２  例示的なソフトウェア
３０４  アプリケーション・プロセス
３０６  アプリケーション・プロセス
３０８  アプリケーション・プロセス
３１０  配置実行部
３１２  配置コントローラ
３１４  アプリケーション・プロファイラ
４０２  グローバル配置行列
５０２  ノード
５０４  ノード
５０６  配置コントローラ
５０８  配置コントローラ
５１２  配置実行部
５１８  アプリケーション・プロファイラ
５２６  配置実行部
５２８  アプリケーション・プロファイラ
９０２  アプリケーション
１１０２  ネットワーク・ノード
１１０４  処理ユニット
１１０６  システム・メモリ
１１０８  システム・バス
１１０８  読取り専用メモリ（ＲＯＭ）
１１１０  ランダム・アクセス・メモリ（ＲＡＭ）
１１１２  ＢＩＯＳ
１１１４  ハード・ディスク・ドライブ
１１１６  磁気ディスク・ドライブ
１１１８  磁気ディスク
１１２０  光学ディスク・ドライブ
１１２２  ＣＤ−ＲＯＭディスク
１１２４  ハード・ディスク・インターフェース
１１２６  磁気ディスク・インターフェース
１１２８  光学ディスク・インターフェース
１１３０  オペレーティング・システム
１１３２  非集中型の配置アプリケーション
１１３４  グローバル配置行列
１１３６  キーボード
１１３８  マウス
１１４０  シリアル・ポート・インターフェース
１１４２  モニタ
１１４４  ビデオ・アダプタ
１１４６  ネットワーク・インターフェース
１１４８  ネットワーク
【図１】
0005254547.tif 000002
【図２】
0005254547.tif 000003
【図３】
0005254547.tif 000004
【図４】
0005254547.tif 000005
【図５】
0005254547.tif 000006
【図６】
0005254547.tif 000007
【図７】
0005254547.tif 000008
【図８】
0005254547.tif 000009
【図９】
0005254547.tif 000010
【図１０】
0005254547.tif 000011
【図１１】
0005254547.tif 000012
【図１２】
0005254547.tif 000013