(57)【特許請求の範囲】
【請求項１】
相互に接続されたＮ個のコンピュータを有するネットワークにおいて、現トポロジに関して追加接続の数Ｃを含む改良されたネットワーク・トポロジの計算に基づいてジョブを実行するための方法であって、
（ａ）Ｎ×Ｎラプラシアン行列Ｍによって前記Ｎ個のコンピュータを有する前記ネットワークの前記現トポロジを表すステップを含み、
但し、その値ｌｉ，ｊは次式のように定義され、
【数１】
0005602851.tif 000016
deg（ｖｉ）はノードｉに接続されるノードの数であり、１≦ｉ≦Ｎ及び１≦ｊ≦Ｎであり、
（ｂ）Ｔｒ（Ｍ１）＝Ｔｒ（Ｍ）＋Ｃ＊２を有し且つ最大の可能な２番目に小さい固有値を有するＮ×Ｎラプラシアン行列Ｍ１を計算するステップと、
（ｃ）前記計算されたＮ×Ｎラプラシアン行列Ｍ１に従って前記追加接続の数Ｃを加えることにより、前記現トポロジを改良されたネットワーク・トポロジに修正するステップと、
（ｄ）前記修正されたネットワーク・トポロジを有する前記コンピュータ上にジョブを分散スケジューリングするために前記修正されたネットワーク・トポロジから開始するステップをさらに含む、方法。
【請求項２】
前記改良されたネットワーク・トポロジがスモール・ワールド・ネットワークである、請求項１に記載の方法。
【請求項３】
前記ステップ（ｂ）が Kim-Mesbahi アルゴリズムを適用することを含む。請求項１又は請求項２に記載の方法。
【請求項４】
前記追加接続の数Ｃの所望の値を入力するようにユーザに指示するステップをさらに含む、請求項１ないし請求項３の何れか１項に記載の方法。
【請求項５】
前記ネットワークの効率を示す値を測定するために前記ネットワークの性能をモニタするステップと、
前記測定された効率に従って前記追加接続の数Ｃを決定するステップをさらに含む、請求項１ないし請求項４の何れか１項に記載の方法。
【請求項６】
前記修正されたネットワーク・トポロジを有する前記コンピュータ上にジョブを分散スケジューリングすることが、
前記ネットワーク・トポロジ内にある前記ネットワークについて少なくとも１つの所望の動作可能資源値を確立するステップと、
前記ネットワーク内のコンピュータのうち少なくとも幾つかのコンピュータ上で実行されている１つ以上のジョブによる、当該幾つかのコンピュータの前記資源の現使用率を決定するステップと、
前記現使用率及び前記所望の動作点から前記ネットワーク内の各コンピュータに対する予測状態値を計算するステップと、
前記予測状態値が前記現使用率を超過する場合、前記ネットワーク内の１つのコンピュータによって次に実行すべき他のジョブを選択するステップを含む、請求項１ないし請求項５の何れか１項に記載の方法。
【請求項７】
前記現使用率を決定するステップが、モニタリング・ソフトウェアによって収集される資源消費メトリクスから前記現使用率に関係する情報を取得するステップを含む、請求項６に記載の方法。
【請求項８】
前記予測状態値が前記現使用率を超過する場合、１つのジョブの資源要件が前記予測状態値と前記現使用率との間の差に最も近い資源要件を有する１つのジョブを実行すべきジョブとして選択するステップを含む、請求項６又は請求項７に記載の方法。
【請求項９】
複数のコンピュータ用の作業負荷をスケジュールするためのシステムであって、
請求項１ないし請求項８の何れか１項に記載の方法を実施するのに適合した１つ以上のコンポーネントを備えるシステム。 
【請求項１０】
請求項１ないし請求項８の何れか１項に記載の方法をコンピュータに実行させるためのコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ・ネットワークに係り、さらに詳細に説明すれば、分散コンピューティング環境内のジョブ・スケジューリング・システムに係る。
【背景技術】
【０００２】
ネットワークに連結又は接続された複数の資源間のジョブ・スケジューリング及び作業負荷バランシングは、ＩＴ環境の益々重要なコンポーネントになりつつある。多くのグリッド・コンピューティング環境は、分散された１組の資源間の作業（例えば、計算、ストレージ、通信能力、ソフトウェア・ライセンス、特殊機器等）のスケジューリングにより駆動される。本質的に、スケジューリングは、最適化の問題であり、関与する資源タイプが１つしか存在しない場合は、非常に単純である。しかし、さらなる性能向上を達成することができるようにより多くの資源変数をスケジューリング・プロセスに含めると、その結果として生じる多変数の最適化は、難解な数学問題となる。
【０００３】
一般に、従来のジョブ・スケジューリング・システムは、ジョブのセットアップ、スケジューリング及び管理が中央サーバ（「マスタ」サーバとも称する）から行われる、マスタ／エージェント・アーキテクチャを利用する。実際の作業は、他のサーバ上にインストールされたエージェントによって行われる。使用するとき、マスタは、ジョブの割り当て先を決定することができるように、ジョブや利用可能なサーバ等に関係する情報を維持し且つ解釈する。一方、エージェントは、マスタからのコマンドを待機し、コマンドを実行し、マスタに終了コードを返す。マスタ／エージェント・アーキテクチャは、ジョブの厳格な制御を可能とするが、マスタ及びエージェントを同期されたままに留める必要があり（従ってネットワーク及びマスタの使用可能性への対応する依存性についても同様）、このことがマスタ／エージェント・アーキテクチャの重大な制約となる。これに関連して、マスタ及びエージェントの間のネットワーク・トラフィックの集中度が高まると、マスタ／エージェント・アーキテクチャ全体の性能を低下させることがある。他の問題は、マスタ／エージェント・アーキテクチャの拡張性が制限されることである。特に、マスタは、制限された数のエージェントしかサポートすることができず、そして新しいマスタ又はインスタンスを作成すると、個別の新しい管理が発生するから、作成されるインスタンスが増えるほど、必要となる管理活動も複雑となる。
【０００４】
本出願人によって２００８年４月１５日に出願された欧州特許出願第０８１５４５０７.１号は、異機種分散コンピューティング環境内の増加する作業負荷に適合するように、高度に拡張可能な作業負荷スケジューリング・システムを開示する。具体的には、その推奨実施形態は、複数のコンピュータ間にネットワーク・トラフィック及びジョブを均等に分散させるために、修正された平均コンセンサス・アルゴリズム（modified average consensus algorithm）を利用する。各コンピュータからの状態情報は、修正された平均コンセンサス・アルゴリズムによって残りのコンピュータに伝搬され、その結果、その推奨実施形態は、個々のコンピュータがそれ自体の資源の所望の使用率をジョブによって必要とされる資源に最適に整合させるように当該ジョブをそれ自体で選択することを可能にすることによって、マスタ・サーバの必要性を省くことを可能にする。前記方法の問題点は、ユーザがコンピュータの論理トポロジを含む仮想ネットワークを確立しなければならないということである。換言すれば、正しいトポロジを選択することはユーザの責任であり、このことは、ネットワークの効率を悪化させるような間違った選択につながることがある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】欧州特許出願第０８１５４５０７.１号
【非特許文献】
【０００６】
【非特許文献１】Yoonsoon Kim, Mehran Mesbahi, "On maximizing the SecondSmallest Eigenvalue of a State dependent Graph Laplacian," IEEETRANSACTIONS ON AUTOMATIC CONTROL, VOL. 51, No 1, JANUARY 2006
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ユーザにとっては、この選択プロセス中に誘導されることが望ましく、一層望ましいのは、予定のパラメータに従って最良の解を決定するための信頼性のある方法を利用することであろう。
【０００８】
本発明の目的は、従来技術の前記問題点を緩和するための技術を提供することにある。
【課題を解決するための手段】
【０００９】
本発明の１側面では、相互に接続されたＮ個のコンピュータを有するネットワークにおいて、現トポロジに関して追加接続の数Ｃを含む改良されたネットワーク・トポロジの計算に基づいてジョブを実行するための方法が提供される。この方法は、
（ａ）Ｎ×Ｎラプラシアン行列Ｍによって前記Ｎ個のコンピュータを有する前記ネットワークの前記現トポロジを表すステップを含み、
但し、その値ｌｉ，ｊは次式のように定義され、
【数１】
0005602851.tif 000002
deg（ｖｉ）はノードｉに接続されるノードの数であり、１≦ｉ≦Ｎ及び１≦ｊ≦Ｎであり、
（ｂ）Ｔｒ（Ｍ１）＝Ｔｒ（Ｍ）＋Ｃ＊２を有し且つ最大の可能な２番目に小さい固有値（greatest possible second-smallest eigenvalue）を有するＮ×Ｎラプラシアン行列Ｍ１を計算するステップと、
（ｃ）前記計算されたＮ×Ｎラプラシアン行列Ｍ１に従って前記追加接続の数Ｃを加えることにより、前記現トポロジを改良されたネットワーク・トポロジに修正するステップと、
（ｄ）前記修正されたネットワーク・トポロジを有する前記コンピュータ上にジョブを分散スケジューリングするために前記修正されたネットワーク・トポロジから開始するステップをさらに含む。
【００１０】
本発明の他の側面では、前記方法を実施するのに適した１つ以上のコンポーネントを備えるシステムが提供される。
【００１１】
本発明の他の側面では、前記方法をコンピュータに実行させるためのコンピュータ・プログラムが提供される。
【発明の効果】
【００１２】
本発明の方法は、現トポロジ及び追加接続の所望の数から開始してネットワーク・トポロジの自動的及び最適化された選択を提供することにより、従来技術の前記問題点を解決するのを支援することができる。このようにして、本発明の方法は、例えば、単純なリング・ネットワークに比較すると、修正されたコンセンサス・アルゴリズムについてより高い収束速度を提供する。本方法は、所謂スモール・ワールド・ネットワーク（small-world network）を利用する。スモール・ワールド・ネットワークは、他のネットワーク・アーキテクチャに比較すると、摂動（perturbation）に対しより頑強である。実際、全てのノードがほぼ同数の接続を有するランダム・ネットワークでは、或るランダム・ノードを削除すると、平均最短経路長をわずかに増加させるが、削除された殆どのノードについては著しく増加させる。この意味において、ランダム・ネットワークはランダムな摂動に対し脆弱であり、一方、スモール・ワールド・ネットワークは頑強である。
【図面の簡単な説明】
【００１３】
【図１】リング・トポロジの表現を有する、推奨実施形態に従った作業負荷スケジューリング・システムのソフトウェア・アーキテクチャを示すブロック図である。
【図２】本発明の方法に従って修正された図１のトポロジを示す図である。
【図３】本発明の方法が適用されるコンピュータ・ネットワークを例示する図である。
【図４】本発明の方法が適用されるコンピュータ・ネットワークを例示する図である。
【図５】推奨実施形態に従った作業負荷スケジューリング方法をサポートするのに適合する汎用コンピュータ・システムのブロック図である。
【図６】推奨実施形態に従った方法を実施するためのステップを表すフローチャートである。
【発明を実施するための形態】
【００１４】
図１に示すように、推奨実施形態１００は、異機種分散ネットワーク１０３内で実行すべきジョブのリポジトリ１０１を備える。
【００１５】
説明を簡潔にするため、分散ネットワーク１０３はｎ個のノードを備え、各ノード（ｎｏｄｅｉ）は多数の資源を所有するものと仮定する。推奨実施形態は、以下で詳述するトポロジ形成アルゴリズム１０５を使用する。修正された平均コンセンサス・アルゴリズム１０７は、分散ネットワーク１０３内のノードが、ネットワーク内の他のノードに対し、それぞれの現状態及び新しいジョブの実行に使用できる可能性を通知するために使用される。ジョブ選択モジュール１０９は、分散ネットワーク１０３内のノードが、各ノード（ｎｏｄｅｉ）の資源に関するユーザ定義された所望の使用率及びジョブ（ｊｏｂｋ）の資源要件に従って、ジョブ・リポジトリ１０１から（次に実行すべき）最適ジョブ（ｊｏｂｋ）を選択することを可能にする。
【００１６】
トポロジ形成アルゴリズム１０５は、異機種分散ネットワーク１０３内のノードの論理トポロジを含む仮想ネットワークを確立する。仮想ネットワーク内では、論理トポロジは、どのノードが互いに通信できるかを確立する。特に、論理トポロジは、各ノードがｊ個（但し、ｊ＜ｎ−１）の隣接ノードに直接接続される（且つ通信可能となる）ように定義される。従って、ノードｉは、ｊ個のノードを含む近傍Ｎｉ（ｎｏｄｅｐ、ｐ＝１〜ｊ）が提供される。各ノードが接続されるノードの数は、ユーザによって定義することができ、推奨実施形態の耐障害性（及び収束速度）は、かかるノードの数を増加させることによって改良される。推奨実施形態では、基本トポロジ（例えば、図１のネットワーク１０３）から開始して、ユーザは、ネットワークのモニタされる性能及びトラフィックに従って、追加接続の数を指示することができる。代替的に、追加接続の最適数は、ネットワークの効率及び速度を評価するためにネットワーク性能をモニタする、モニタリング・ツールによって決定することができるであろう。他の可能性は、以前に測定された性能の統計に依存することである。基本トポロジに課される唯一の条件は、仮想ネットワークによって形成されるグラフが連結されねばならないということである、換言すれば、各ノードから開始して、任意の数のステップを通して、他の任意のノードに到達可能でなければならない。
【００１７】
図１に示すようなリング・トポロジでは、各ノードは、２つの接続及び２つの近傍しか有していない。従って、図１に示す例では、ノード１は、ノード２及びノード６に直接接続される。同様に、ノード２は、ノード１及びノード３に直接接続される。また、ノード６は、ノード１及びノード５に直接接続される。ｎ個のノードを有する任意のトポロジは、ｎ×ｎ行列で表すことができる。図１の例は、次の６×６行列Ｍで表すことができる。
２  −１    ０    ０    ０  −１
−１    ２  −１    ０    ０    ０
０  −１    ２  −１    ０    ０
０    ０  −１    ２  −１    ０
０    ０    ０  −１    ２  −１
−１    ０    ０    ０  −１    ２
かかる行列の固有値は、次の通りである。
０，１，１，３，３，４
【００１８】
非特許文献１に記載されているように、ｎ個のノードを有する（ループ又は複数のエッジのない）グラフＧが与えられると、そのラプラシアン行列Ｌは、次式のように定義される。
【数２】
0005602851.tif 000003
但し、deg（ｖｉ）はノードｉに接続されるノードの数である。現トポロジ（例えば、前記のように表されるラプラシアン行列Ｍ）から開始し、既存のノード間の追加接続の数Ｃを加えることを仮定すると、解決すべき問題は、最大の可能な２番目に小さい固有値を有する行列Ｍ＋Ｃ＊２のトレースと等しい（Ｔｒ）を有するラプラシアン行列Ｍ１を見つけることである。
【００１９】
換言すれば、Ｔｒ（Ｍ１）＝Ｔｒ（Ｍ）＋Ｃ＊２であるような全ての可能なラプラシアン行列間で、最大の可能な２番目に小さい固有値を有するラプラシアン行列Ｍ１を決定するということである。
【００２０】
非特許文献１では、提案されたプロトコルを使用すると、収束速度がネットワーク・グラフに関係するラプラシアンの２番目に小さい固有値に比例することが示されている。
【００２１】
従って、収束速度を最大化するために、本発明は、非特許文献１において提案されたアプローチを使用することにより、コンセンサス問題を解決するための最良の論理トポロジを得ることを意図する。この方法を使用すると、最良のスモール・ワールド・ネットワークである、論理トポロジを得ることが可能である。
【００２２】
数学及び物理学では、スモール・ワールド・ネットワークは、殆どのノードが互いの近傍ではないが、各ノードから少数のホップ又はステップを通して殆どのノードに到達可能である、或るタイプの数学的なグラフである。
【００２３】
このようにして、平均最短経路長を減少させることが可能であり、その結果、状態の伝播をより速くすることができる。
【００２４】
非特許文献１において提案されたアルゴリズム（以下「Kim-Mesbahiアルゴリズム」とも称する）は、最初のグラフ（構成）Ｇ０に関して時間ｔ＝０で開始され、その後はｔ＝０、１及び２について、ラムダ＿２（ＬＧ（ｔ＋１））を最大化するグラフを反復的に見つけるように進行する。但し、ＬＧ（ｔ＋１）は時間ｔ＋１におけるグラフＧのラプラシアンである。その後、この貪欲アルゴリズムは、ラムダ＿２（ＬＧ（ｔ））の値をそれ以上改良できなくなるまで、反復されるのである。本発明者は、生成される列が非減少であり且つ有界であるので、提案された貪欲アルゴリズムが収束することに着目する、
【００２５】
非特許文献１において提案された方法によれば、現トポロジから開始し且つ要求される追加接続の数を指示すると、収束速度を最大化するための最良のトポロジ（即ち、当該トポロジを表す行列の２番目に小さい固有値）を識別することが可能である。このアルゴリズムを前記行列で表されたリング・トポロジに適用すると、次の新しい行列が得られる。
３  −１    ０  −１    ０  −１
−１    ３  −１    ０  −１    ０
０  −１    ３  −１    ０  −１
−１    ０  −１    ３  −１    ０
０  −１    ０  −１    ３  −１
−１    ０  −１    ０  −１    ３
この新しい行列は、図２に表されているトポロジに対応する。
【００２６】
この新しい行列の固有値は、次の通りである。
０，３，３，３，３，６
これは、収束速度が３（２番目に小さい固有値）に比例することを意味する。
【００２７】
図１及び図２に示されるトポロジは、例示を目的としてだけ提供されるものであって、推奨実施形態をリング・トポロジに限定することを意図するものではないことを理解されたい。特に、推奨実施形態は、（前述の接続制約に従う限り）任意のトポロジ及び分散ネットワーク１０３内の任意の数のノードについて動作可能であることが当業者には理解されるだろう。図３は、他の（一層複雑な）例を示す。この基本トポロジでは、２６個のノードがリング構成において接続される。かかる構成は、０.０５８１に等しい２番目に小さい固有値を有する２６×２６（本明細書には表されていない）の行列で表される。もし、かかるトポロジに６個の接続を追加することを望んでおり、そして Kim-Mesbahi アルゴリズムを適用するとすれば、０.２４１３に等しい固有値を有する図４のトポロジが得られるであろう。これは、前述のトポロジ構成よりも高い、コンセンサス収束速度４１５％に対応する。この値は、６個の接続を追加する際に得ることが可能な最大値である。
【００２８】
仮想ネットワーク内の各ノード（ｎｏｄｅｉ）は、当該ノードの資源が当該ノード上で現に実行されているジョブによってどの程度占有されるかを指示する使用資源状態変数（used resources state variable）を含む。この情報は、モニタリング・ソフトウェアによって収集される実時間リソース消費メトリックから取得することができる。特に、
【数３】
0005602851.tif 000004
を所与の資源ベクトル
【数４】
0005602851.tif 000005
に関連する消費メトリック・ベクトルとして定義すると、所与のノードの資源が（現に実行中のジョブによって）占有される程度は、ノード（ｎｏｄｅｉ）の資源変数の消費メトリックの加重和である、スカラ変数ｓｔａｔｅｉ、即ち、
【数５】
0005602851.tif 000006
によって与えられ得る。また、スカラ変数ｓｔａｔｅｉのベクトル表記は、
【数６】
0005602851.tif 000007
となる。但し、
【数７】
0005602851.tif 000008
である。推奨実施形態において修正された平均コンセンサス・アルゴリズムを使用すると、各ノードは、この情報を仮想ネットワーク全体にわたって、発信元ノードが直接接続されていないノードにも伝搬させることが可能となる。
【００２９】
同様の表記法を使用して（ジョブ・リポジトリ１０１内の）特定のジョブの要件を記述することができる。特に、ジョブ（ｊｏｂｑ）の正味要件（ｅｑ）は、次式のように定義することができる。
【数８】
0005602851.tif 000009
【００３０】
特許文献１に記載されているように、ジョブ・スケジューラは、所謂コンセンサス・アルゴリズムの修正バージョンに基づいている。
【００３１】
或るグラフの平均コンセンサス・モデルは、ｎｏｄｅｉに対する入力ｕｉ及びその近傍（Ｎｉ）についてグラフ展開を計算する分散方法を提供する。従って、ｎｏｄｅｉのｓｔａｔｅｉの展開を
【数９】
0005602851.tif 000010
によって表すことが可能であれば、次式の連続解
【数１０】
0005602851.tif 000011
又は次式の不連続解
【数１１】
0005602851.tif 000012
は、コンセンサス問題が連結グラフに漸近的に解決されることを証明することができる。従って、動的システムは、連続解については次式の
【数１２】
0005602851.tif 000013
又は不連続解については次式の
【数１３】
0005602851.tif 000014
によって表される初期状態の平均に収束する。これらの極限の証明は、それぞれに関係するナイキスト線図から導出される。
【００３２】
推奨実施形態は、仮想ネットワーク内の他の全てのノードに直接接続される仮想ノードＶ（図示せず）を導入することにより、前述した従来の平均コンセンサス・アルゴリズムを修正する。従って、仮想ノードＶは、ｎｏｄｅｉの近傍Ｎｉの範囲内に含まれる。このアプローチを使用する場合、各ノード（ｎｏｄｅｉ）は、
・当該ノードの現状態（ｓｔａｔｅｉ（ｋ））、及び
・当該ノードの近傍Ｎｉ内の他のノード（仮想ノードＶを含む）の現状態
から、当該ノードの次の状態（ｓｔａｔｅｉ（ｋ＋１））を次式を使用して計算する。
【数１４】
0005602851.tif 000015
【００３３】
仮想ノードＶは、仮想ネットワーク内で全てのノードの所望の作業負荷を表す、ユーザ構成可能な固定状態を有する。仮想ノードＶを仮想ネットワーク内の各ノードの近傍に含めると、仮想ネットワーク内の他の全てのノードに関する平均コンセンサス・アルゴリズムが仮想ノードＶの固定状態とバランスし且つその固定状態に収束することになる（収束速度はネットワーク・グラフのラプラシアンに関係付けられる）。従って、仮想ノードＶの状態をユーザによって構成可能にすることにより、推奨実施形態は、仮想ネットワーク内のノードの資源の所望の使用率（即ち、動作点）が満たされるように（即ち、仮想ネットワークの動作点が効果的に変更されるように）、作業負荷スケジュールを調整する機構を効果的に提供する。
【００３４】
ジョブ選択モジュール１０９は、ノード（ｎｏｄｅｉ）が次に実行すべきジョブを、当該ノードの現状態及び計算された次の状態に従って、（ジョブ・リポジトリ１０１から）選択することを可能にする。特に、ｓｔａｔｅｉ（ｋ＋１）＜ｓｔａｔｅｉ（ｋ）であれば、次の反復時に当該ノードが引き受ける新しいジョブは存在しないことになる。一方、ｓｔａｔｅｉ（ｋ＋１）≧ｓｔａｔｅｉ（ｋ）であれば、差分変数Δは、Δ＝ｓｔａｔｅｉ（ｋ＋１）−ｓｔａｔｅｉ（ｋ）（即ち、ｎｏｄｅｉの計算された次の状態と当該ノードの現状態との差）として定義される。（ジョブ・リポジトリ１０１から）選択される次のジョブ（ｊｏｂｋ＋１）は、その正味要件変数（ｅｔ）が差分変数Δからの最小差分を有する（即ち、ｅｔ｜ｍｉｎｔ（Δ−ｅｔ））ジョブ（ｊｏｂｔ）である。
【００３５】
図５は、汎用コンピュータ・システム４００（例えば、コンピュータ、インターネット・サーバ、ルータ、リモート・サーバ）を示す。コンピュータ４００は、システム・バス４５３に並列接続される幾つかのユニットから形成される。詳細には、１つ又は複数のマイクロプロセッサ４５６は、コンピュータ４００の動作を制御し、ＲＡＭ４５９は、マイクロプロセッサ４５６によって直接作業メモリとして使用され、ＲＯＭ ４６２は、コンピュータ４００のブート・ストラップ用の基本コードを格納する。周辺ユニットは、（それぞれのインタフェースにより）ローカル・バス４６５の周囲にクラスタ化される。特に、大容量メモリは、ハード・ディスク４６８及びＣＤ−ＲＯＭ４７４を読み取るためのドライブ４７１から成る。さらに、コンピュータ４００は、入力装置４７７（例えば、キーボード及びマウス）と、出力装置４８０（例えば、モニタ及びプリンタ）を含む。ネットワーク・インタフェース・カード４８３は、コンピュータ４００をネットワークに接続するために使用される。ブリッジ・ユニット４８６は、システム・バス４５３をローカル・バス４６５とインタフェースする。各マイクロプロセッサ４５６及びブリッジ・ユニット４８６は、情報を伝送するためにシステム・バス４５３へのアクセスを要求するマスタ・エージェントとして動作することができる。アービタ４８９は、相互排除を用いてシステム・バス４５３に対するアクセス権の付与を管理する。システムが異なるトポロジを有する場合、又は他のネットワークに基づく場合も、同様の考えが当てはまる。代替的に、コンピュータは、異なる構造を有するか、同等のユニットを含むか、又は他のデータ処理エンティティ（例えば、ＰＤＡ、携帯電話など）から構成される。
【００３６】
図６は、推奨実施形態に従った方法５００のステップを概略的に示す。この方法５００は、ステップ５０１から開始して、ステップ５０３に進み、そこでネットワークの現トポロジが決定され且つ前述のような行列Ｍで表される。推奨実施形態によれば、ネットワーク内のノードの数がｎである場合、行列Ｍの次元はｎ×ｎである。ステップ５０３では、ネットワークのユーザ（又は管理者）は、追加接続の所望の数を指示することができる。ステップ５０５では、必要とされる追加接続の数が決定される。この決定は、幾つかのパラメータ（例えば、ネットワーク・トラフィック、システム性能、ネットワークの地理的構成）を考慮に入れることができ、幾つかの異なる方法でこれを行うことができる。当業者には明らかなように、この決定は、既存のツールで行うことができ、又は追加接続の数を管理者によって手動的に指示することもできる。また、追加接続の最適数は、ネットワークの効率及び速度を評価するためにネットワーク実行をモニタするモニタリング・ツールによっても、決定することができるであろう。他の可能性は、以前に測定された性能の統計に依存することである。次のステップ５０７では、行列Ｍ及び必要とされる追加接続の数は、全ての解のうちで最大の２番目に小さい固有値を有する行列Ｍ１を見つけることにより、ネットワークの最適トポロジを決定することができる、 Kim-Mesbahi アルゴリズムに入力される。推奨実施形態では、この方法５００は、ステップ５０９に進み、そこでは前述のように修正されたコンセンサス・アルゴリズムに基づくジョブ・スケジューリング・プロセスが行われる。任意選択のステップ５１１では、新しいネットワークの性能が十分であるか否かを決定するために、新しいネットワークの性能がモニタされる。もし、新しいネットワークの性能が十分であると決定されるならば、通常のジョブ・スケジューリング活動を継続することができる。そうでなければ、ネットワークの新しい再構成が考慮され、制御権はステップ５０５に戻る。他の可能な代替案は、ステップ５１１で性能が十分であると決定されるまで、追加接続の数を１だけインクリメントすることであり得る。
【００３７】
前述の解決手段については、本発明の範囲から逸脱することなく、変更及び修正を施すことができる。当然のことながら、ローカル及び特定の要件を満たすために、当業者は、前述の解決手段に対し多数の修正及び変更を適用することができる。特に、本発明は、その推奨実施形態を参照して或る程度まで詳細に記述されたが、形式及び細部において種々の省略、代替及び変更を行うことが可能であり、他の実施形態も可能であることを理解されたい。さらに、本発明の開示された任意の実施形態に関連して記述した特定の要素及び／又は方法ステップを、設計変更の一般的な事項として他の任意の実施形態に組み入れてもよいことは明確に意図されている。
【００３８】
例えば、コンピュータが異なる構造を有するか又は同等のユニットを含む場合、同様の考えが当てはまる。どんな場合でも、コンピュータを任意のコード実行エンティティ（例えば、ＰＤＡ、携帯電話など）と取り替えることができる。
【００３９】
（本発明の各実施形態を実装するのに使用することができる）プログラムが異なる方法で構成されるか、又は追加のモジュール又は機能が提供される場合、同様の考えが当てはまる。同様に、メモリ構造は、他のタイプとすることができ、又は（必ずしも物理的ストレージ媒体から構成されていない）同等のエンティティと取り替えることができる。さらに、提案された解決手段は、（同様又は追加のステップを有し、或いは異なる順序でこれらのステップを有する）同等の方法で実装するのに適している。どんな場合でも、プログラムは、任意のデータ処理システムによって、又はかかるデータ処理システムに関連して使用するのに適した任意の形式（例えば、オブジェクト・コードであるか又はソース・コードであるかに拘わらず、外部若しくは常駐ソフトウェア、ファームウェア又はマイクロコード）を取ることができる。さらに、プログラムは、任意のコンピュータ使用可能媒体上に提供することができる。かかる媒体は、プログラムを保持し、格納し、通信し、伝搬し又は転送するのに適切な任意の要素とすることができる。かかる媒体の例は、（プログラムをプリロードすることができる）固定ディスク、取り外し可能ディスク、テープ、カード、ワイヤ、ファイバ、無線接続、ネットワーク、放送波などである。例えば、かかる媒体は、電子、磁気、光学、電磁気、赤外線又は半導体タイプとすることができる。
【００４０】
どんな場合でも、本発明に従った解決手段は、（例えば、半導体物質のチップ内に統合された）ハードウェア構造又はソフトウェア及びハードウェアの組み合わせで実装するのに適合している。
【図１】
0005602851.tif 000017
【図２】
0005602851.tif 000018
【図３】
0005602851.tif 000019
【図４】
0005602851.tif 000020
【図５】
0005602851.tif 000021
【図６】
0005602851.tif 000022