JP3818655B2 - タスク・スケジューリングの方法、システム、およびプログラム製品 - Google Patents

タスク・スケジューリングの方法、システム、およびプログラム製品 Download PDF

Info

Publication number
JP3818655B2
JP3818655B2 JP2003415773A JP2003415773A JP3818655B2 JP 3818655 B2 JP3818655 B2 JP 3818655B2 JP 2003415773 A JP2003415773 A JP 2003415773A JP 2003415773 A JP2003415773 A JP 2003415773A JP 3818655 B2 JP3818655 B2 JP 3818655B2
Authority
JP
Japan
Prior art keywords
request
level
queue
requests
value
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
JP2003415773A
Other languages
English (en)
Other versions
JP2004199678A (ja
Inventor
アシシュ・クンドゥ
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of JP2004199678A publication Critical patent/JP2004199678A/ja
Application granted granted Critical
Publication of JP3818655B2 publication Critical patent/JP3818655B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
    • G06F9/5027—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals
    • G06F9/505—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals considering the load
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/54—Interprogram communication
    • G06F9/546—Message passing systems or structures, e.g. queues
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2209/00—Indexing scheme relating to G06F9/00
    • G06F2209/54—Indexing scheme relating to G06F9/54
    • G06F2209/548—Queue

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computer And Data Communications (AREA)

Description

本発明は、コンピュータ・システムのタスク・スケジューリングの分野に関する。具体的には、本発明は、コンピュータ・システムで除去される要求の数の削減と、サービス品質（Quality of Service、ＱｏＳ）およびサービス・レベル・アグリーメント（Service Level Agreement、ＳＬＡ）の実施とタスク・スケジューリングの方法、システム、およびフレームワークに関する。
コンピュータ・システムは、さまざまなタスクを実行し、さまざまな要求を処理する処理能力およびメモリを有するシステムと定義することができる。そのような要求は、ネットワークを介するデータベースへのアクセスなどの単純なデータ要求から、元の要求を処理するためにデータベース内のあるデータを必要とするアプリケーションの実行の要求などの複雑な要求までの広範囲にわたる可能性がある。
要求（またはタスク）を受け取り、処理するコンピュータ・システムは、その容量に関するある制限を有する。コンピュータ・システムが同時に処理できる要求の最大の個数には限度がある。そのような制限は、コンピュータ・システムの設計および容量に起因して生じる可能性がある。したがって、システムがそれに基づいて展開されるＣＰＵ速度、メモリ容量、ネットワーク接続速度などのパラメータによって、システムの処理できる要求の数が制限される。したがって、要求の数がこの限度を超えると、完全には処理されない要求がいくつか生じる。コンピュータ・システムに達する前に除去される要求も生じる。これらの要求は、コンピュータ・システムによって全く受け取られない。また、コンピュータ・システムによって受け取られるが、部分的に実行されただけで打ち切られる要求も生じる。これは、通常は、メモリの不足またはネットワーク接続のタイムアウトに起因して発生する。
そのようなシステムの１つの例を、インターネットベースのオンライン株式取引サービスとすることができる。そのようなサービスによって、ユーザの要求時に、特定の株の価格に関する情報がユーザに供給される。しかし、そのようなオンライン・インターネット・サービスのユーザの数が増加するにつれて、オンライン・インターネット・サービスのサーバによって並行に処理されるユーザ要求の数が、時々収拾不可能になる。たとえば、バスケットボールに関する特定の情報を供給するオンライン・インターネット・サービスのサーバは、全国レベルのバスケットボール・トーナメントの決勝中に、ユーザ要求で過負荷になる。実際に、要求の過負荷に起因して、部分的にしか処理されないユーザ要求が生じ、全く処理されない要求が生じる。これらの、完全には処理されないか全く処理されない要求は、除去されたと見なされる。
要求自体の完全な処理にクリティカルであるトランザクションが処理されない場合に、要求は除去されたとみなされる。要求Ａの部分的な処理によって生成される要求Ｂが、要求Ａの完全な処理にクリティカルであると仮定する。しかし、要求Ｂが除去される（たとえば、要求Ｂを処理するコンポーネントに対する要求の過負荷に起因して）場合に、要求Ａを完全に処理することはできない。そのような場合に、要求Ａも、除去されたとみなされる。
したがって、要約すると、要求が除去されたとみなされるには、（ｉ）システムまたはシステム・コンポーネントによる要求の処理（部分的なまたは完全な）の前に、コンポーネントに対する要求過負荷に起因して、要求が、処理に関する将来の検討から除外される（すなわち、完全に除去される）か、（ｉｉ）要求の完全な処理にクリティカルなトランザクションが打ち切られるか、（ｉｉｉ）元の要求の処理から生成され、その完全な処理が元の要求の完全な処理にクリティカルである別の要求が除去された場合である。
過負荷に起因する要求除去の問題に対処する方法の１つが、同一システムの複数の複製（すなわち複数のサーバ）を使用して、着信要求を処理することである。したがって、単一のサーバの代わりにサーバのクラスタを使用して、要求を処理することができる。ロード・バランサは、クラスタの前で要求を受け取り、複製の間での要求の公平な分配を保証するのに使用される。ロード・バランサは、コンポーネントの過負荷を防ぐために、クラスタのさまざまなコンポーネントの間でユーザ要求を均等に分配するハードウェア装置またはソフトウェア・プログラムである。たとえば、ロード・バランサを使用して、サーバの複数の複製（ｈｔｔｐｌサーバなど）の間でユーザ要求を分配することができる。この分配は、各コンポーネントの作業負荷、要求の内容タイプ（ビデオまたはテキスト）、コンポーネントの地理的配置、および期待されるＱｏＳおよびＳＬＡなどの、事前定義の判断基準に基づくものとすることができる。さらに、後で説明するように、類似するコンポーネントの間でこれらの要求を分配する事前定義の方法や技法が存在する可能性がある。
同一サーバの複数のインスタンスを使用すると、各サーバによって処理される要求の数が減る。これによって、サーバが過負荷になる機会が減る。しかし、いくつかのケースでの要求の数は、非常に多いので、その要件を満たすために複数のサーバを有することは非実用的である。ネットワーク伝送速度の向上およびユーザ／クライアントの数の増加によって、ネットワークを介する要求の伝送が、コンポーネントで要求を処理する速度またはロード・バランサによって要求が転送される速度あるいはその両方よりはるかに速い。このため、コンポーネント／ロード・バランサでの要求の蓄積が引き起こされ、したがって、コンポーネント／ロード・バランサが過負荷になる。これが、コンポーネント／ロード・バランサでの要求除去につながる。他のいくつかの場合に、コンポーネントが、要求を処理し始めるが、高いロード条件に起因して、処理が、事前定義の期間内に完了しない。これも、要求除去につながる可能性がある。
要求除去は、コンピュータ・システムの性能に悪影響を及ぼす。第１に、リソースすなわち、要求を処理し、転送したロード・バランサのリソース、または要求の部分的処理に使用されたリソースあるいはその両方の浪費がある。これは、リソース使用率の減少につながる。第２に、処理される時に、要求が、コンポーネントのいくつか（その要求を処理したもの）の状態の変化をもたらす場合がある。要求が、中間コンポーネントで除去される場合には、そのシステムを、最も最近の一貫性のある状態にロール・バックする必要が生じる可能性がある。言い換えると、システム全体を、除去された要求の処理が開始される前のそのシステムの状態に戻さなければならない。各ロールバックは、要求処理でのシステムの応答時間を悪化させ、システムのスループットを低下させ、システム・リソースも浪費する。第３に、システム・リソースの浪費が、十分なシステム・リソースが使用可能でなくなることに起因して、そうでなければ処理できたはずの他のリソースの除去を引き起こす場合がある。第４に、上で述べたものと同一の理由から、そうでなければよりよいサービス品質で処理できたはずのいくつかの他の要求が、より低いサービス品質で処理される。第５に、除去される要求の部分的処理に浪費された時間が、除去されたか失敗した要求に関するユーザ応答時間に追加される。これによって、ユーザに提供されるサービス品質（ＱｏＳ）が阻害される可能性があり、ユーザとネットワークの間のサービス・レベル・アグリーメント（ＳＬＡ）の侵害にもつながる可能性がある。最後に、要求の処理の応答時間が長くなるにつれて、ユーザの不満が高まる。
上で述べた要求除去の不利益に鑑みて、要求除去の数を減らすことが肝要である。要求除去を減らすためにロード・バランサを使用する複数の方法および技法がある。ロード・バランサによってユーザ要求の分配を実行する例示的な方法の１つが、ラウンド・ロビン・ドメイン・ネーム・サーバ（Round Robin Domain Name Server、ＲＲ−ＤＮＳ）手法である。この方法では、要求が、回転式（すなわちラウンド・ロビン式）に１つずつ複数のサーバにルーティングされる。
特定のユーザ要求のターゲット・コンポーネントを決定するための、クラスタ（類似するコンポーネントの）内の個々のコンポーネントの間での情報の流れという発想に基づく他のいくつかのロードバランシング解決策がある。この情報は、負荷がロード・バランサによって平衡化される、クラスタ内の各コンポーネントの負荷レベルに関連するものとすることができる。
そのような解決策の１つが、米国特許第５９３８７３２号、表題"Loadbalancing and fail over of network services"に開示されている。この方法では、コンポーネントのクラスタ内の通信の維持と、それらの間の協力の調整に対処する。これは、サービスを提供するコンポーネントの１つまたは複数が、障害を介するなど、時々使用不能になる場合であっても、そのグループによって提供されるサービスが使用可能なままになるようにするために行われる。各処理要素は、グループ内の他のすべての処理要素に周期的に制御メッセージを送って、通信を維持するのを助ける。このメッセージは、送出側コンポーネントの状況ならびにグループ内の他のコンポーネントの知覚された状況に関するデータが含まれる。
もう１つの解決策が、チョウ（Myongsu Choe）およびトロッパ（CarlTropper）著の研究論文、"Flow Control and Dynamic Load Balancing in Time Warp"で提案された。この論文では、フロー制御および動的ロード・バランシングを一体化するアルゴリズムが開示されている。フロー制御は、クラスタ内のプロセッサによって、その間で負荷を共用または分配するのに使用される。この場合のフロー制御は、ターゲット・コンポーネントの間のフロー制御である。
オスマン（Ossama Othman）、オライアン（Carlos O'Ryan）、およびシュミット（DouglasC. Schmidt）著の研究論文"The Design and Performance of an Adaptive CORBA LoadBalancing Service"でも、解決策が提案されている。この論文は、将来の研究で、所与のクラスタ（コンポーネントの）からターゲット複製（コンポーネント）を決定するためにさまざまなロード・バランサの間のフロー制御を使用する必要を掲げている。
上で説明した解決策のすべてで、要求を処理するターゲット・コンポーネントを決定するために、クラスタ（類似するコンポーネントの）内のさまざまなコンポーネントの間での情報交換が使用されている。しかし、これらのどれもが、高い要求速度で働くことを意図されたシステムでの要求除去の問題に対処していない。完了の前に最終的に除去される要求も、処理され、これによって、リソースの浪費と、処理時間および電力消費の増加が引き起こされる。これが、より低いシステム効率をもたらす。これらの解決策は、上で説明した要求除去の通常の不利益も有する。
米国特許第５９３８７３２号、表題"Load balancingand fail over of network services" チョウ（Myongsu Choe）およびトロッパ（CarlTropper）著、"Flow Control and Dynamic Load Balancing in Time Warp" オスマン（Ossama Othman）、オライアン（CarlosO'Ryan）、およびシュミット（Douglas C. Schmidt）著、"The Design and Performance of anAdaptive CORBA Load Balancing Service"
したがって、上の説明に鑑みて、コンピュータ・システムでの要求除去の数を減らすことができるシステムおよび方法の必要が存在する。具体的に言うと、ロード・バランサでの要求除去の数を減らすシステムおよび方法の必要がある。ロード・バランサでのサービス品質（ＱｏＳ）およびサービス・レベル・アグリーメント（ＳＬＡ）の実施を容易にするシステムおよび方法の必要も存在する。システムのスループットを高める、ロードバランシング・フレームワークの必要も存在する。これは、システム・リソースの浪費を減らすために必要である。
本発明の目的は、コンピュータ・システムで要求をスケジュールすることである。
本発明の具体的な目的は、コンピュータ・システムの中間コンポーネントおよびロード・バランサで除去される要求の数を減らすことである。
本発明のもう１つの具体的な目的は、サービス品質（ＱｏＳ）およびサービス・レベル・アグリーメント（ＳＬＡ）を実施することである。
本発明のもう１つの具体的な目的は、フロー制御メッセージを処理し、ＱｏＳ／ＳＬＡを実施する、ロード・バランサ内のシステムおよび方法を提供することである。
本発明のもう１つの具体的な目的は、ロード・バランサならびにシステムの要求スループットを高めることである。
本発明のもう１つの目的は、システム・リソース使用率を最大にすることである。
本発明のもう１つの目的は、要求の区別された分配を提供することである。
本発明のもう１つの目的は、システム・ロールバックの数を最小にすることである。
本発明のもう１つの目的は、ユーザへの応答時間を減らすことである。
本発明の上記および他の目的は、複製の組の間で負荷を平衡化する、方法、システム、およびコンピュータ・プログラム製品によって提供される。この方法は、実施されるポリシに基づいてコンピュータ・システムに到達する要求をスケジューリングすることを目的とする。コンピュータ・システムには、複数のレベルが含まれ、各レベルは、少なくとも１つのキューを有し、各キューは、少なくとも１つのバッファを有し、各キューは、少なくとも１つの処理コンポーネントに関連する。各キューは、それに関連する任意の個数のクラスタに対応するものとすることもできる。着信要求は、完全に処理される前に、１つまたは複数のレベルを介して処理される。フロー制御情報が、要求除去を減らすために２つのレベルの間で交換される。本発明の一実施形態では、すでに説明したロード・バランサ内の上の方法の実施形態を説明する。着信要求が、第１レベル・キューに保管される。要求は、さらに、ユーザ定義のパラメータ（ＱｏＳ／ＳＬＡなど）に基づいて、複数のクラスに分類される。その後、要求は、事前定義の判断基準に基づいて、複数の第２レベル・キューの１つに転送される。たとえば、各第２レベル・キューを、要求のクラスに対応するものとすることができる。キューの２つのレベルの間に、制御情報のフローが存在する。この制御情報は、第２レベル・キューの状態に基づいて要求を適当な第２レベル・キューに転送するのに使用され、これによって、ロード・バランサ内で除去される要求の数が減る。
本発明のもう１つの実施形態では、上で述べたロード・バランサを、フレームワークで使用して、複数のクラスタの間で負荷を動的に平衡化することができる。着信要求が、第１レベル・ロード・バランサで受け取られる。ロード・バランサは、１つまたは複数の要求を、要求のタイプまたはターゲット・コンポーネントの状態あるいはその両方に基づいて、ターゲット・コンポーネントに並行にディスパッチする。ロード・バランサは、要求除去が起ころうとしているのを感知する場合に、フロー制御メッセージを生成し、そのメッセージを前レベル・ロード・バランサに送る。フロー制御メッセージを受け取る時に、ロード・バランサは、対応する処置を講ずることを決定することができ、その結果、後のレベルの要求除去が回避される。ロード・バランサは、前レベル・ロード・バランサおよび次レベル・ロード・バランサと交換できるフロー制御メッセージも生成することができる。
本発明の好ましい実施形態を、以下で、本発明を例示するが制限しない添付図面に関して説明する。図では、類似する符号が類似する要素を示す。
使用される用語法
論理インスタンス：論理インスタンスとは、物理インスタンス／コンポーネントまたは物理インスタンス／コンポーネントのある容量のいずれかである。論理インスタンスは、物理インスタンスの名前／アドレスと、物理インスタンス内で割り振られた容量との対によって表すことができる。本明細書の用語「インスタンス」および「複製」の使用のすべてが、「論理インスタンス」の同意語である。
クラスタ：クラスタとは、サポートされる機能性、インスタンスを使用するためのプロトコルなどに関して同一である論理インスタンスの集合である。
次レベル・ロード・ディストリビュータ：ロード・ディストリビュータ（ＬＤ）−ｘの次レベル・ロード・ディストリビュータ（ＬＤ）とは、ＬＤ−ｘに隣接し、トポロジ的にその次のＬＤである。たとえば、図６では、ＬＤ６０６およびＬＤ６０８が、ＬＤ６０２の次レベルＬＤであり、ＬＤ６１４が、ＬＤ６０６およびＬＤ６０８の次レベルＬＤである。
前レベル・ロード・ディストリビュータ：ＬＤ−ｘの前レベル・ロード・ディストリビュータとは、ＬＤ−ｘに隣接し、トポロジ的にその前のＬＤである。たとえば、図６では、ＬＤ６０２が、ＬＤ６０６およびＬＤ６０８の前レベルであり、ＬＤ６０６およびＬＤ６０８が、ＬＤ６１４の前レベルＬＤである。
フロントエンド：フロントエンドとは、エンド・ユーザから要求を受け取る、アプリケーション・インスタンスのクラスタである。
要求分類要因（ＲＣＦ）：ＲＣＦは、要求をカテゴリに分類（他の要求から区別）するのに使用される。たとえば、本発明の一実施形態で、要求に関連する顧客識別またはサービス・クラス／グレード、あるいは顧客ＩＤと要求のサービス・クラスの組合せを、ＲＣＦとして使用して、着信要求を分類する。ＲＣＦ値の計算に使用することができる他のパラメータは、要求タイプ（たとえば、カタログ表示要求、ショッピング要求など）、要求の複雑さ、要求の優先順位などとすることができる。
負荷モニタ：Ｃの状態またはＣに対する負荷あるいはその両方を監視できるような所与の時点でのシステムまたは別のコンポーネントＣに関連付けられるコンポーネントＭ。Ｃの状態には、可用性、応答時間、ＣＰＵ消費などが含まれる。Ｃに対する負荷は、ＣまたはＣを展開する基礎になるシステムの消費される容量の尺度である。
リソース・マネージャ：ある顧客から別の顧客へのリソースの割振り／割振り解除、または関連するシステムの容量プラニング、あるいはその両方が可能なコンポーネントＲ。
本発明は、要求除去を最小にするためにフロー制御技法を使用するモデル（システムおよび方法）を提供する。要求のスケジューリングは、既存のポリシ／技法を使用して実行することができる。本明細書での説明のために、そのようなポリシの単純で一般的な例を選ぶ、すなわち、高いユーティリティ値を有する要求を転送し、要求のユーティリティ値は、要求が完全に処理される確率と、要求の優先順位（要求クラスとも称する）とによって決定される。この例を、図３に関して後で詳細に説明する。要求除去を減らすために実施する／従うことができる多数のそのようなポリシがありえることは、当業者に明白であろう。
図１に、本発明の好ましい実施形態による、要求を処理するコンピュータ・システム１００を示す。システム１００は、１つまたは複数のレベルを有することができ、各レベルは、その中に１つまたは複数のキューを有する。各レベルのキューは、さらに、１つまたは複数のバッファと、それに関連する１つまたは複数の処理機能を有することができる。例示のために、図１に、コンピュータ・システムの２つのレベル（すなわち、１０８および１１２）だけを示す。また、例示のために、図１に、その中に１つのキュー（すなわち１０２および１１０）だけを有する各レベルを示す。また、各キューは、１つのバッファ（すなわち、１０４および１２２）だけを有するものとして図示されている。
広義には、要求がシステム１００で処理される形は、次の通りである。キュー１０２に、バッファ１０４およびそれに関連する処理機能１０６が含まれる。キュー１０２内のバッファ１０４は、着信要求を受け取り、これらの着信要求を処理機能１０６に転送する。処理機能１０６は、要求ディスパッチ機能（要求のディスパッチに使用される）または要求分類機能（要求を分類するのに使用される）とすることができる。例示のために、図１に、処理機能１０６が要求ディスパッチ機能であるキュー１０２を示す。キューには、任意の数のクラスタを関連付けることができる。任意選択として、キューに、クラスタを関連付けないことができる。そのような場合には、あるキューに別のキューを続け、最後のキューだけがクラスタを関連付けられるようにすることができる。クラスタは、同等のタスクを実行するコンポーネント・インスタンスを含む。例示のために、図１に、クラスタ１０８に関連するキュー１０２を示し、このクラスタ１０８は、実際には、要求実行機能を実行するコンポーネントのクラスタである。要求ディスパッチ機能によって、要求が、クラスタ１０８にディスパッチされ、クラスタ１０８によって、要求が処理され、次のレベルのキュー１１０に転送される。各キューに、前のレベル／次のレベルのキューからの処理制御メッセージ／フロー制御メッセージを交換する交換モジュール１１６と、フロー制御メッセージの指示を実施する実施モジュール１１８と、制御信号／フロー制御信号を作成し、送る時を感知する感知モジュール１２０も含まれることが好ましい。そのようなモデルの実施形態が、必ずしも３つの別個のモジュールのすべてを有するのではないことに留意されたい。たとえば、ある実施形態が、３つのすべてのモジュールの機能を実行する１つのモジュールだけを有する場合がある。しかし、３つのすべてのモジュールの機能を、どの実施形態でも実行する必要がある。これらモジュールの使用を、本明細書で後で詳細に説明する。キュー１１０は、バッファと、要求ディスパッチ機能も有する。要求ディスパッチ機能によって、要求が、キュー１１０に関連するクラスタ１１２にディスパッチされる。クラスタ１１２のコンポーネントによって、要求が適当に処理される。クラスタ１１２からの要求が、要求の処理要件に応じて複数のキューに転送される場合がありえることに留意されたい。この処理要件に関する情報を、要求のヘッダに保管することができ、したがって、この情報は、ターゲット・キューを決定するためにクラスタ１１２のコンポーネントによって処理される。
開示されるシステムでは、異なるレベルのキューの間に情報（メッセージ）のフローがある。言い換えると、キュー１０２および１１０は、情報を交換する（１１４）。既に述べたように、この２つのキューの交換モジュールが、ある判断基準に基づいて要求除去を減らすためにキュー１０２が訂正処置を講じられるようにするために、情報１１４を交換する。バッファ管理ポリシを使用して、訂正処置を完全にまたは部分的に実行することができる。バッファ管理ポリシの簡単な例の１つを、下で例示のため説明する。
バッファ管理ポリシの例は、次の通りである。要求を分類（またはディスパッチ）し、ＦＣＦＳ（先着順サービス）に基づいて次のレベルに転送する。キューによって、フロー制御情報に基づいて、次レベルのキューで要求が残存する確率が判定される。あるレベルの各キューは、フロー制御信号を前のレベルのキューに送ることができ、制御信号を次のレベルのキューに送ることができる。この情報は、キューにある要求の残存確率に対応する負荷情報に関するものとすることができる。この確率および要求の優先順位を使用して、要求のユーティリティ値を判定することを図３に関して詳細に説明する。着信要求の数が、キューの要求処理容量を超える場合には、キューは、より高いユーティリティ値の要求を受け取り、他の要求を除去すると決断することができる。キューは、次レベル・キューに転送できなかった要求をハッシュ・テーブルに編成することもでき、その結果、それらの要求を、次レベル・キューが要求を受け取る準備ができるとすぐに転送できるようになる。
要求除去を減らすために、キューによって、複数の訂正処置を実行することができる。これらの訂正処置を、図２に関して詳細に説明する。これらの訂正処置は、実施モジュール１１８によって実行され、除去される要求の数のかなりの削減がもたらされる。また、本発明の好ましい実施形態では、これらの処置によって、ＱｏＳ／ＳＬＡ標準規格の厳密な実施がもたらされる。
図２は、本発明の好ましい実施形態による、要求を処理するために従われるステップのシーケンスを示す流れ図である。以下の説明では、要求のユーティリティ値の例が、本発明の好ましい実施形態の動作を示すだけのために使用されることに留意されたい。以下の説明を、どのような形でも、制限的であると考えてはならない。
ステップ２０２で、キュー１０２によって、要求を受け取り、バッファに保管する。ステップ２０４で、キュー１０２の交換モジュール１１６によって、キュー１１０の負荷およびクラスタ１１２の負荷に関する情報１１４を受け取る。ステップ２０６で、キュー１０２の実施モジュール１１８によって、情報１１４と、任意選択として要求に関する情報（要求ヘッダに保管されている可能性がある）に基づいて、クラスタ１１２への要求転送の「ユーティリティ値」を計算する。例示のために、ユーティリティ値が、要求の完了の確率に依存し、この確率が、後続レベルのキューおよびクラスタの負荷に基づくと仮定する。次レベル・キューおよび対応するクラスタの負荷が高いと、要求の完了の確率が下がり、したがって、要求のユーティリティ値が下がる。こうなるのは、完了の低い確率を有する要求がキュー１０２によって転送される場合に、その要求によってキュー１０２の処理時間およびシステム・リソースが利用されるからである。この要求が、その後キュー１１０で除去され、これによってシステム・リソースおよび時間が浪費される可能性が、非常に高い。ユーティリティ値は、要求のクラスにも基づくものとすることができる。たとえば、ＱｏＳ／ＳＬＡレベル・ゴールドの要求の転送は、ＱｏＳ／ＳＬＡレベル・ブロンズの要求の転送よりも、商業的に有用である。要求のユーティリティ値を判定するために導入することができる多数の他の要因があることは、当業者に明白である。しかし、説明のために、情報１１４を使用して計算することができる完了の確率と、要求パケットのヘッダから得ることができる要求クラスだけを含むように要求のユーティリティ値を制限する。この例によるユーティリティ値の計算は、図３に関して詳細に例を使用して説明する。
ステップ２０８で、要求の計算されたユーティリティ値を、キュー１０２に割り当てられた閾ユーティリティ値と比較する。閾ユーティリティ値は、計算され、各キューに割り当てられる。この閾値は、特定のキューについて固定された値である。この閾値は、次レベル・キューおよび対応するクラスタの推定負荷に関する情報を使用することと、キューによって処理される要求クラスを検討することによって計算される。この値は、システムの後続のスケール・アップまたはスケール・ダウンの度に、またはキューによって処理される要求クラスの変更について、変更されなければならない。
計算されたユーティリティ値が、閾ユーティリティ値を超える場合には、ステップ２１０で、キュー１０２の処理機能１０６によって要求を処理する（ディスパッチするか分類する）。しかし、計算されたユーティリティ値が、閾ユーティリティ値より小さい場合には、ステップ２１２で、キュー１０２の感知モジュールによって、要求の修正されたユーティリティ値を計算する。修正されたユーティリティ値は、キューが訂正処置を実施すると仮定した後に要求のユーティリティ値を増やすために計算される。この値は、訂正処置を講じるコストに基づく。コストは、主に、訂正処置を講じるためのメモリ消費および処理能力使用量によって左右される。ユーティリティ値を、訂正処置が講じられた後の要求の完了の確率および要求のクラスに基づくものとすることもできる。
キューによって講じられる訂正処置は、下記とすることができる。まず、キューの感知モジュールによって、制御信号を送ってその要求ディスパッチ速度を変更することができ、その結果、次レベル・キューおよび対応するクラスタの負荷が、最適レベルに達する。要求が、以前に、次レベル・キューでの過負荷に起因して低いユーティリティ値を有した場合には、制御信号によって、負荷が減らされ、したがって、要求の完了の確率が増える。これによって、要求のユーティリティ値の増加がもたらされる。この処置に関連するコストは、通常は、この処置が小さいコードの実行だけを伴うので、非常に低い。したがって、要求の修正されたユーティリティ値は、一般に要求の元のユーティリティ値より高い（完了の確率の増加に起因する）。この処置を講じることに関係するステップを、図４に関して詳細に説明する。ステップ２１４で、修正されたユーティリティ値を、修正された閾ユーティリティ値と比較する。スケール・アップが実行されない（すなわち、第２の処置が実行されない）場合に、修正された閾ユーティリティ値が、元の閾ユーティリティ値と同一になることに留意されたい。修正された閾ユーティリティ値が、修正された閾値より小さい場合には、ステップ２１６で、要求を除去する。そうでない場合には、ステップ２１８で、ステップ２１２で仮定された訂正処理を講じ、要求を、キューによってそのクラスタにディスパッチし、これによって、ステップ２２０で、適当な処理の後に、要求が次のレベルに転送される。
ユーティリティ値、閾ユーティリティ値、修正されたユーティリティ値、および修正された閾ユーティリティの概念をより明瞭に示すため、図３の表を検討されたい。説明される形が、例示のために働くことだけを意図され、どのような形でも本発明を制限するものと考えてはならないことに留意されたい。説明を単純にするために、ユーティリティ値を計算する非常に単純な例を選ぶ、すなわち、残存確率（０から１の間）にＱｏＳレベル（ブロンズ要求で１、シルバー要求で２、またはゴールド要求で３）をかける。したがって、０．７５の残存確率を有する要求Ａ（たとえばブロンズ要求）は、０．７５×１＝０．７５のユーティリティ値を有する。この要求は、キューによってディスパッチされる。というのは、ユーティリティ値が、閾ユーティリティ値（このキューについては＝０．５）を超えるからである。同様に、図３に示された要求Ｂもディスパッチされる。しかし、０．４８のユーティリティ値を有する要求Ｃ（０．１６の完了確率を有するゴールド要求（ＱｏＳ＝３））は、閾ユーティリティ値（０．５）の方が高いので、転送されない。修正された閾ユーティリティ値は、ロード・バランサのディスパッチ速度を変更する修正処置が講じられると仮定することによって計算される。この訂正処置のステップは、図４で説明する。要求Ｃ’が、修正された要求である。図３から、ディスパッチ速度を修正する訂正処置が講じられる場合に、完了確率が０．２０に増える。しかし、その処置に関連するコスト要因（たとえば０．９）がある。したがって、要求Ｃ’の修正されたユーティティ値は、０．２×３×０．９＝０．５４になり、これは、閾ユーティリティ値０．５より大きい。したがって、訂正処置を講じると、要求Ｃのユーティリティ値が増え、これによって、要求Ｃを除去する必要がなくなる。
また図３を参照して、要求Ｄの場合（完了確率＝０．４、ＱｏＳレベル＝１（ブロンズ））を検討されたい。第１の処置を講じたと仮定した後であっても、修正されたユーティリティ値（０．４５）は、閾ユーティリティ値を超えない。しかし、第２の処置（スケール・アップ）を講じたと仮定する。この処置に関連するコストは、第１の処置のコスト（０．９の乗算要因）より高い（０．８の乗算要因）。したがって、修正されたユーティリティ値は、０．６×１×０．８＝０．４８になる。しかし、この場合に、閾ユーティリティ値も、０．４５に減る（スケール・アップに起因して）。したがって、第２の訂正処置を講じる場合には、要求Ｄを渡すことができる。しかし、要求Ｅなど、両方の訂正処置を講じた場合であっても渡されない要求が存在する可能性がある。そのような要求は、システムによって除去される。
図４に、キューがロード・バランサ内で実施され、ロード・バランサのディスパッチ速度を修正した後に要求が渡せるようになる、例示的な例でのステップのシーケンスを示す。やはり、要求を渡せるようにする多数の形があり、以下の説明では、その１つの可能な形を示す。この処置で使用される情報には、次レベル・ロード・バランサおよびそれに対応するクラスタの負荷に関する情報が含まれる。ステップ４０２で、キューが、特定の要求クラスｒの要求を受け取る。ステップ４０４で、キューの実行可能モジュールが、要求クラスｒに関する要求の現在の着信速度、要求クラスｒに関する着信要求の期待される速度、および次レベル・ロード・バランサからの要求クラスｒの要求の現在のディスパッチ速度に関する情報を受け取る。要求の完了の確率は、この受け取られた情報をキューの実施モジュールで処理することによって判定される。この確率は、多数の形で計算することができる。確率を計算する例示的な形の１つを、ステップ４１０に関して説明する。
ステップ４０６で、キューが、要求クラスに関する情報を収集する。この情報は、着信要求のヘッダに格納されることが好ましい。要求のＱｏＳ／ＳＬＡレベルを、要求クラスの例の１つとすることができる。単純な実施の例を、ゴールド要求に３、シルバー要求に２、ブロンズ要求に１の値を割り当てることとすることができる。ステップ４０８で、キューが、ステップ４０４および４０６で収集した情報に基づいて、要求のユーティリティ値を計算する。やはり、前に述べたように、この情報をキューによって使用してユーティリティ値を得る多数の形が存在する可能性がある。前に説明したように、それを行う単純な例の１つが、完了の確率と要求クラス・レベルの乗算によるものである。したがって、次レベル・ロード・バランサの負荷が７５％（完了確率＝０．２５）である場合に、ブロンズ要求のユーティリティ値は、０．２５（ゴールド要求のユーティリティ値は０．７５、シルバー要求のユーティリティ値は０．５）である。
ブロンズ要求のユーティリティ値が、閾ユーティリティ値より小さいと仮定する。その場合には、修正されたユーティリティ値は、キューの要求ディスパッチ速度の変化を仮定することによって計算される。ステップ４１０で、要求ディスパッチ速度の変化を、収集した情報を使用してキューの実施モジュールによって計算する。ディスパッチ速度の計算には、どのような技法でも使用することができる。以下は、特定の要求クラスの残存確率に基づいてディスパッチ速度の変化を計算する単純な例示的な形である（この例では、要求の優先順位（要求クラス）を考慮に入れていない。要求クラスの考慮ありまたはなしでディスパッチ速度を計算する多数の方法があることは、当業者に明白である）。最後に、ステップ４１２で、要求ディスパッチの計算された新しい速度で要求をディスパッチする。
Ｑ＝｛Ｑ２、Ｑ３、Ｑ４、…、Ｑ−ｋ｝の前レベル・キューを有するキューＱ−ｍを検討されたい。Ｑ−ｍのバッファが、要求クラス−ｒのクリティカル値（たとえば９５％満杯）より大きい場合には、キューＱ−ｍは、Ｑ内のキューのフロー制御メッセージを生成すると判断する。このフロー制御メッセージには、Ｑ−ｍでのクラスｒの着信要求速度Ｒｒ ｍが含まれる。期待される着信速度はＥｒ ｍである。受取り側のキューＱ−ｋは、このメッセージを処理し、そのディスパッチ速度を訂正すると判断する。Ｑ−ｋによって実施される処置は、ディスパッチ速度を下げることである。最終的なディスパッチ速度ｄｒ ｋを計算するのに使用される式の例は、下記とすることができる。
Ｄｒ ｋが、ＣＬＤ−ｋからのクラスｒの要求の現在のディスパッチ速度であるものとする。
着信速度への寄与の割合は、Ｃ＝Ｄｒ ｋ／Ｒｒ ｍである。
ディスパッチ速度に対する変更は、ｚｒ ｋ＝Ｃ×（Ｅｒ ｍ−Ｒｒ ｍ）である。
新しいディスパッチ速度はｄｒ ｋ＝Ｄｒ ｋ＋ｚｒ ｋである。
ｄｒ ｋ＜Ｄｒ ｋの場合には、Ｑ−ｋは、要求クラス−ｒのディスパッチ速度をｄｒ ｋまで減らす。これは、ディスパッチされる要求のそれぞれの後に遅延を追加して、新しいディスパッチ速度を実施することによって達成される。
開示されるモデル（システムおよび方法）は、ある事前定義のパラメータ（サービス品質／サービス・レベル・アグリーメント（ＱｏＳ／ＳＬＡ）など）に基づいて要求を分類し、処理する能力も有する。本発明を使用することによって、システムで発生する要求除去の数が大幅に減る。また、システム・リソース使用は、コンピュータ・システム内の中間コンポーネントで要求が除去される機会が減るので、はるかに効率的になる。本発明の一実施形態では、厳密なサービス品質／サービス・レベル・アグリーメント（ＱｏＳ／ＳＬＡ）の実施が保証され、これによって、サービス品質の改善がもたらされる。これによって、ユーザ要求に対するより高速の応答時間が保証される。
これまでに説明したシステムのハードウェア実施形態は、下記の形で行うことができる。各キューを、集積回路によって実施することができる。バッファは、ＤＲＡＭ技術または、より高速のメモリ動作のためにキャッシュ・メモリを実施するのに使用される技術を使用して実施することができる。フロー制御メッセージを処理するサブコンポーネントに、マイクロプロセッサ、メモリ、および通信プロセッサも含めることができる。処理機能は、多少のメモリを有するマイクロプロセッサおよび通信プロセッサとして実施することもできる。バッファ、処理機能、およびコントローラの間に、通信リンクがある。各サブコンポーネントは、所望の構成および挙動のために特定の命令を介してプログラムすることができる。
説明したシステムは、ソフトウェア実施形態も有することができ、これは、メモリおよび処理能力を有する計算装置で実施することができる。各コンポーネントは、一般的なプログラミング言語（Ｃ、Ｃ＋＋、またはＪａｖａ（Ｒ）など）のいずれかを使用して記述されるソフトウェア・コードの形で実施される。これらのソフトウェア・コードによって、実行時に、コンポーネントの機能性を実行するために、計算装置のメモリおよび処理能力が使用される。
これまでに述べたモデルは、図５に関して説明する連繋負荷ディストリビュータ（ＣＬＤ）アーキテクチャで実施することができる。このモデルは、複数のそのようなＣＬＤ（図５で説明する）を使用する連繋負荷分配フレームワークでも実施することもできる。そのようなフレームワークを、図６に関して詳細に説明する。
実施形態１：連繋負荷ディストリビュータ（ＣＬＤ）
これまでに説明したモデルのＣＬＤとしての実施形態は、ｎレベルのキューを有し、ｎ≧１である。最初の（ｎ−１）個のレベルのどれにも、クラスタは関連付けられない。これらのレベルの各キューの処理機能は、要求分類機能である。ｎ番目のレベルは、キューごとに１つまたは複数のクラスタを有し、これらのレベルの処理機能は、要求ディスパッチ機能である。
これまでに説明した実施形態を、例を使用して説明する。図５に、連繋負荷ディストリビュータ（ＣＬＤ）５００の全体的なシステム・アーキテクチャの例を示す。ＣＬＤ５００には、２レベルのキューすなわち、第１レベル・キュー（グローバル要求ハンドラ（ＧＲＨ）５０２）および第２レベル・キュー（特定要求ハンドラ（ＳＲＨ）５０４）が含まれる。ＧＲＨ５０２は、クラスタを関連付けられず、ＧＲＨ５０２の処理機能は、要求分類機能である（要求クラシファイヤ（ＲＣ）とも称する）。ＲＣは、要求分類要因（ＲＣＦ）に基づいて要求を分類し、ＲＣＦは、ある事前定義のパラメータ（後で説明するように、サービス・ベースの分類または顧客ベースの分類など）に依存するものとすることができる。ＧＲＨ５０２から分類された要求を受け取る複数のＳＲＨ（第２レベル・キュー、ＳＲＨ５０４に似る）がある。これらのＳＲＨは、要求のさまざまなクラスに対応するものとすることができる。図示の例では、各ＳＲＨが、要求ディスパッチ機能（要求ディスパッチャ（ＲＤ）とも称する）を有する。各ＳＲＨは、１つまたは複数のクラスタを有することができ、そのクラスタに、ＳＲＨが要求をディスパッチする。本発明のＣＬＤ実施形態を、２レベルのキューに関して説明したが、複数レベルのキューも使用できることに留意されたい。たとえば、第２レベル・キューでの要求の副分類を設けることができる。３つのレベルを有するロード・バランサの例示的実施形態は、グローバル・バッファとして働く１つの第１レベル・キュー、異なるサービス・クラスの複数の第２レベル・キュー、および異なる顧客クラスの複数の第３レベル・キューを有することができる。
ＣＬＤ５００は、感知モジュール、交換モジュール、および実施モジュールの機能性を実行する、要求ディスパッチ・マネージャ（ＲＤＭ）５０６および負荷分配コントローラ（ＬＤＣ）５０８を有する。この実施形態では、交換モジュール、感知モジュール、および実施モジュールが、キュー固有として図示されていない、すなわち、各キューが、この３つのモジュールを有しないことに留意されたい。その代わりに、この例示的ＣＬＤアーキテクチャでは、これらのモジュールの機能性を実施する、１つのＲＤＭおよび１つのＬＤＣだけがある。ＲＤＭ５０６は、ＳＲＨ５０４の負荷状態のセンサとして働き、ＧＲＨ５０２とＳＲＨ５０４の間のメッセージの交換を可能にする。ＲＤＭ５０６は、ＳＲＨがほぼ満杯の状態（後で詳細に説明する）に達した時に、ＧＲＨに適当なメッセージを送る。ＲＤＭ５０６は、各複製に関する動的負荷情報を得るために、負荷モニタ（ＬＭ）とも情報を交換する。ＬＤＣ５０８は、他のＣＬＤとの間で、メッセージを受け取り、生成し、送る（図６に関して説明する）。ＬＤＣ５０８は、リソース・マネージャ（ＲＭ）とも情報を交換する。
ＣＬＤアーキテクチャを、これから詳細に説明する。図５に関して既に述べたように、ＣＬＤ５００は以下のコンポーネント、グローバル要求ハンドラ（ＧＲＨ）５０２、要求ディスパッチ・マネージャ（ＲＤＭ）５０６、特定要求ハンドラ（ＳＲＨ）５０４、および負荷分配コントローラ（ＬＤＣ）５０８を有する。ＧＲＨ５０２には、バッファ、要求レシーバ、および要求分類機能が含まれる。ＲＤＭ５０６には、ＬＤＣ５０８およびＧＲＨ５０２からのメッセージのレシーバと、ＳＲＨ５０４、ＬＤＣ５０８、およびＧＲＨ５０２へのメッセージのセンダが含まれる。ＲＤＭ５０６によって、ＳＲＨ５０４とＧＲＨ５０２の間のメッセージ５１０の交換が可能になる。ＲＤＭ５０６には、任意選択として、負荷モニタに関する負荷レシーバおよびメッセージ・センダも含まれる。ＳＲＨ５０４には、要求レシーバ、第２レベル・バッファ（ＳＬＢ）と称するバッファ、および要求ディスパッチ機能が含まれる。ＬＤＣ５０８には、新しい要求クラスに基づくか、クラスタ容量などの変更に基づいて、動的にＣＬＤの構成を修正するモジュールが含まれる。ＬＤＣ５０８には、ＱｏＳ／ＳＬＡ関係のインテリジェンスを実施する任意選択のモジュールも含まれる。たとえば、ＬＤＣ５０８は、満杯になる頻度、要求除去の割合などに基づいて、ＱｏＳクラスごとのバッファ・サイズを判断することができる。
ＧＲＨ５０２は、第１レベル・キューであり、ＳＲＨの組は、第２レベル・キューからなる。ＳＲＨの数は、要求クラスの数によって左右される。好ましい実施形態では、その数が、要求クラスの数と等しい。ＧＲＨ５０２は、主に、着信要求の受け取りの責任を負い、任意選択として、要求／他の定義された判断基準の正当性の認証に基づいて管理制御を実行し、要求を受け入れ、各要求を分類し、要求のクラスに適当なＳＲＨに要求を送る。各ＳＲＨ５０４は、主に、ＧＲＨ５０２から要求を受け取り、バッファが満杯でない場合にその要求をバッファにバッファリングし、満杯の場合には要求を選択的に除去し（前にモデルの説明で既に説明したバッファ管理ポリシに従って）、使用されるロード・バランシング技法に基づいて各要求をディスパッチする責任を負う。ＧＲＨ５０２およびＲＤＭ５０６は、ＧＲＨ５０２および各ＳＲＨ５０４の間のフロー制御を実施するために、フロー制御を実行しなければならない。ＲＤＭ５０６は、ＳＲＨ５０４およびＳＲＨ５０４のそれぞれのディスパッチ速度の管理を実行する責任を負う。
ＧＲＨ５０２は、要求を受け取る場合に、バッファが満杯であるか否かを検査する。満杯の場合には、ＬＤＣ５０８が、ユーティリティ値に基づいて要求を選択的に除去するか、要求を受け入れるようにＧＲＨ５０２に指示する。既に説明したように、実施されるバッファ管理ポリシによって、要求がそのユーティリティ値に基づいて処理される形が左右される。要求を処理する例示的な形は、キューが、閾ユーティリティ値より高いユーティリティ値の要求を受け取り、他の要求を除去できることとすることができる。また、次レベル・キューに転送できない（ユーティリティ値が低いことに起因する）要求をハッシュテーブルに編成することができ、その結果、これらの要求を、次レベル・キューが要求を受け取る準備ができるとすぐに転送することができる。要求を受け入れた後に、ＧＲＨ５０２は、要求をグローバル要求バッファにバッファリングする。ＧＲＨ５０２の要求分類機能が、バッファ内の要求を分類し、そのＲＣＦに基づいて正しいＳＲＨにディスパッチする。アプリケーションレベルの要求を分類するために（ロード・バランサがアプリケーション・レベルのロード・バランシングを実行している場合）、ＧＲＨ５０２の要求分類機能が、要求分類要因（ＲＣＦ）を判定するために、要求の要求ヘッダを解析する。ロード・バランサが、ネットワーク・レベルのロード・バランシングを行っている場合に、ＧＲＨ５０２の要求分類機能は、優先順位または他の情報あるいはその両方（どの種類のＲＣＦが使用されるかに依存する）についてＩＰパケット・ヘッダを解析し、ＲＣＦを判定する。
ＲＣＦを、ＧＲＨ５０２によって計算することができる。ＲＣＦに基づいて、ＧＲＨ５０２は、そのＲＣＦ値に関連する次レベル・バッファＢの状態を検査する。ＳＲＨ５０４のバッファが満杯の場合には、ＧＲＨ５０２のバッファ管理ポリシによって、要求を処理する方法が判断される。ＬＣＤ５０８によって、ＳＲＨ５０４に、要求のユーティリティ値に基づいて、受け取った要求の一部を除去するように指示することもできる。そうでなければ、ＲＣＦを判定した後に、ＧＲＨ５０２の要求分類機能が、要求を適当なＳＲＨに引き渡す。
ＳＲＨ５０４は、要求をキューにバッファリングする。同時に、ＳＲＨのＲＤが、ターゲット・クラスタ内の各複製の負荷情報を受け取る。ロード・バランシング技法が静的な技法（たとえばラウンド・ロビン・ロード・バランシング技法）である場合には、負荷情報は不要である。しかし、動的なロード・バランシング技法の場合には、要求ディスパッチ機能が、特定の要求クラス（そのＳＲＨが属する）のクラスタの各複製の負荷情報を必要とする可能性がある。この負荷情報は、負荷モニタから受け取られる。要求ディスパッチに、２つの可能性があることに留意されたい。まず、要求ごとに、ターゲット・クラスタ内の各複製の負荷情報が入手され、対応するユーティリティ値が計算される。しかし、要求密度が高いネットワークでは、要求ディスパッチ速度が、非同期フロー制御メッセージを得る速度よりもあまりに高い。その場合には、負荷情報を、事前定義の基礎で受け取る。たとえば、この情報を、関係するクラスタ内の複製の負荷に大きい変化がある時だけ受け取ることができる。その場合の要求ディスパッチ速度は、使用可能な負荷情報に基づいて計算される。クラスタの負荷に大きい変化がある時に限って、新しい負荷情報が、入手され、ユーティリティ値の計算に使用される。説明した実施形態では、前者の形の要求のディスパッチを説明した。しかし、後者の形および多数の他の形を使用して、本発明の趣旨および範囲から逸脱せずにこの目的を達成できることは、当業者に明白であろう。
好ましい実施形態では、受け取った負荷情報に基づいて、ＲＤが、負荷が最小の複製を識別し、その複製が正の残余容量を有するかどうか、すなわち、その複製が、さらに要求を処理できるかどうかを識別する。その後、ＲＤは、バッファから要求を検索し、その（最小の負荷の）複製にディスパッチする。ＲＤは、ディスパッチ速度に基づいてディスパッチを継続する。
各ＳＲＨ５０４のＲＤは、使用されるロード・バランシング技法に基づいて、ターゲット複製（クラスタ）に要求をディスパッチする。要求ディスパッチ機能は、要求をターゲット複製にディスパッチする方法を知る必要がある。使用される要求ディスパッチ技法は、ネットワーク・レベルとアプリケーション・レベルのロード・バランシングで異なるので、要求ディスパッチ機能も、それぞれに別々に実施することができる。アプリケーション・ロード・バランシングの場合に、要求ディスパッチは、アプリケーションのそれぞれの使用するプロトコルに応じて、アプリケーションごとに異なる。したがって、アプリケーションのクラスについて、要求ディスパッチ機能の１つの実施形態だけがある。
ＧＲＨ内のＲＣおよびＳＲＨ内のＲＤは、ＣＬＤがアプリケーション・レベル・ロード・バランシングまたはネットワークレベル・ロード・バランシングのどちらに使用されるかに依存するので、これらを、ロード・バランサのプラグ可能コンポーネントとして実施することができる。そのようなプラグ可能コンポーネントは、スタートアップ中にロード・バランサによって使用される。このコンポーネントは、アプリケーションレベル・ロード・バランシングについてアプリケーション依存である。
ＲＤＭ５０６は、各ＳＲＨ５０４の負荷の状態を追跡する。ＳＲＨが、ほぼ満杯（たとえば、７５％満杯、これはユーザが定義することができる）になる場合に、ＲＤＭ５０６は、フロー制御メッセージをＧＲＨ５０２に送る。ほぼ満杯状態は、必ずバッファの満杯状態以下である。ＧＲＨ５０２がフロー制御を実施する時までに、ＧＲＨ５０２が、特定の要求クラスについてさらに要求を送っている可能性があるので、ほぼ満杯状態は有用である。フロー制御メッセージには、とりわけ、要求クラスと、その要求クラスの着信要求速度が含まれる。ＧＲＨ５０２は、要求の転送を中止するか、要求をディスパッチする速度を減らすか、他の手段を講じることができ、これは、モデルに関して前に説明した。ＳＲＨ状態が、「ほぼ満杯」状態から「ほぼ満杯でない」状態に戻る場合に、ＲＤＭ５０６は、状態変化に関するメッセージをＧＲＨ５０２に送る。ＧＲＨ５０２は、前の状態に戻ることができる。ＧＲＨ５０２のバッファがほぼ満杯になるか、ＧＲＨ５０２が、あるＳＬＢがより頻繁にほぼ満杯になるのを観察するか、ＧＲＢが満杯なのでＧＲＨ５０２が要求を除去しているか、着信要求速度が、ＳＲＨ５０４にディスパッチする速度よりはるかに高いか、類似する状況が生じる場合に、ＧＲＨ５０２は、その状態に関する制御メッセージをＬＤＣ５０８に送る。このメッセージには、関連するデータが含まれ、着信要求速度、要求分類速度、ＳＲＨの要求ディスパッチ速度などを含めることができる。ＬＤＣは、ＧＲＢ／ＳＬＢのバッファ・サイズを増やすか、フロー制御メッセージを前のレベルのロード・バランサに送るか、その両方を行うかを判断する。
ＬＤＣ５０８は、要求クラスｒのフロー制御メッセージを受け取る時に、ｒのディスパッチ速度をどれほど減らすか、ｒの要求のディスパッチをどれだけの時間だけ停止するか、要求クラスｒのＧＲＨおよびＳＲＨのバッファ・サイズをどれだけ増やすか（この前の２つの判断に起因してバッファリングされる要求を処理するために）を判断する。ＬＤＣ５０８は、ｒの最新の要求ディスパッチ速度を知らない場合に、その値に関する制御メッセージを介してＲＤＭに尋ねることができる。ＬＤＣ５０８は、値および判断を計算し、最終的な要求ディスパッチ速度、要求ディスパッチを停止する時間、またはＳＬＢサイズの増加、あるいはこれらの組合せを実施するようにＲＤＭに指示する。同様に、ＧＲＨ５０２についてこれに関する指示がある場合には、ＬＤＣ５０８は、ＧＲＨ５０２にも指示する。ＲＤＭ５０６は、指示に従ってＳＲＨ５０４のディスパッチ速度を制御する。ＲＤＭ／ＧＲＨは、必要な場合に、それぞれＳＬＢ／ＧＲＢのバッファ・サイズを増やす。ＧＲＨ５０２およびＲＤＭ５０６は、指示の成功裡の実施についてＬＤＣ５０８に肯定応答を送り、そうでない場合には、否定応答がＬＤＣ５０８に送られる。
リソース・マネージャのメッセージに起因して、または他の理由に起因して（ＳＬＢまたはＧＲＢの頻繁なオーバーフローに対抗するなど）、ＬＤＣ５０８が、バッファのいずれかのサイズを変更する（増やす／減らす）と判断する場合がある。ＧＲＢのサイズを変更するために、ＬＤＣ５０８は、ＧＲＨ５０２に指示する。ＧＲＨ５０２は、指示を実施し、成功裡の変更の際には肯定応答、そうでない場合には否定応答を送る。ＳＬＢのサイズを変更するため、またはＳＲＨのディスパッチ速度を変更するために、ＬＤＣ５０８は、特定の要求クラスに必要な処置に関して知らせることによって、ＲＤＭ５０６に指示する。ＲＤＭ５０６は、指示の処置を実施し、成功裡の変更の際には肯定応答、そうでない場合には否定応答を送る。
リソース・マネージャは、新しい要求クラスｒを追加する場合に、その更新に関してＣＬＤのＬＤＣ５０８に通知する。更新には、可能なＱｏＳ／ＳＬＡパラメータ、または可能な最大要求速度、あるいはその両方も含まれる。ＬＤＣは、ｒの新しいＳＲＨを作成し、要求クラスのリストにｒを追加するようにＲＤＭに指示する。ＲＤＭは、ＬＤＣによって指定されるＳＬＢサイズのＳＲＨを作成する。次に、ＲＤＭは、ＬＤＣにメッセージを送り、成功裡のＳＲＨ作成について知らせる。ＲＤＭは、ＳＲＨを作成できない場合に、ＬＤＣに否定の応答を送る。ＲＤＭからの肯定の応答を受け取る時に、ＬＤＣは、ＧＲＢサイズの変更および新しい要求クラスｒの追加についてＧＲＨに指示する。ＧＲＨは、ＧＲＢサイズを増やし、要求クラスのリストを更新することによって、ＬＤＣ指示を実施する。ＧＲＨは、成功裡の完了時に肯定応答を送る。ＧＲＨは、失敗した場合に、否定応答を送る。
ＧＲＨ／ＬＤＣ／ＲＤＭでのなんらかの種類の障害によって、ロード・バランサが効果的にロード・バランサに要求クラスｒを追加できない場合には、ＬＤＣは、リソース・マネージャに否定応答を送ることができる。
同様に、要求クラスｒの削除について、ＬＤＣは、対応するＳＲＨを削除するようにＲＤＭに指示する。ＲＤＭは、そのような指示を受け取る時に、「要求ｒのＳＲＨを削除せよ」という制御メッセージをＧＲＨに送る。次にＧＲＨは、外部からｒに関する要求をそれ以上受け取るのを停止し、ｒのすべての要求をＳＲＨに転送する。ＧＲＨは、肯定応答をＲＤＭに送る。ＧＲＨからの肯定応答を受け取る時に、ＲＤＭは、ｒのＳＬＢが空になる（ディスパッチされる要求がなくなる）まで待ち、その後、ＳＲＨを削除する。ＲＤＭは、その後、ＬＤＣに肯定応答を送る。ＬＤＣは、ＧＲＢのサイズを変更し、適宜レコードから要求クラスｒを削除するようにＧＲＨに指示する。ＧＲＨは、ＧＲＢのサイズを変更し、リストを更新し、その後、肯定応答をＬＤＣに送る。ＧＲＨとＲＤＭの両方から肯定応答を受け取る時に、ＬＤＣは、必要であれば、「要求クラスｒが除去された」ことを含む肯定応答をＲＭに送ることができる。ＧＲＨ／ＬＤＣ／ＲＤＭでのなんらかの種類の障害によって、ロード・バランサが効果的に要求クラスｒを削除できない場合には、ＬＤＣは、リソース・マネージャに否定応答を送ることができる。
各要求クラスの要求は、他の要求クラスの要求と並行にディスパッチされる。ＣＬＤは、２つのディスパッチャが一時に同一のインスタンスに要求を送らないことを保証するために、平行ディスパッチを使用するが、各論理インスタンスは、１つのリソース・クラスだけに属さなければならない。論理インスタンスが、クラスタ内の、物理インスタンス／複製または物理インスタンス／複製のある容量のいずれかであることに留意されたい。たとえば、要求クラスがゴールドおよびシルバーである場合に、論理インスタンスは、ゴールドまたはシルバーのいずれかに属すが、両方には属さない。
代替実施形態では、このアーキテクチャに順次ディスパッチ技法も使用することができる。平行列ディスパッチの代わりに、下記の技法を使用して順次ディスパッチを実施することができる。各ＳＲＨの要求ディスパッチャを削除する。これらの要求ディスパッチャの代わりに、すべての要求クラスに関する単一要求のディスパッチャを使用する。この要求ディスパッチャは、任意のパラメータ（たとえばＱｏＳ／ＳＬＡベースの重み）に基づいてさまざまなキューの間でスケジューリングを実行し、一時に１つの要求をディスパッチする責任を負う。
実施形態１で説明したＣＬＤでは、要求の処理に二重レベル・バッファリングを使用する。２レベルのバッファの間に、情報フローが存在する。これは、要求が第２レベルで受け入れられる確率を識別するのに役立つ。その結果、低い残存確率を有する要求が、第１レベルで除去され、これによって、システム・リソース（たとえば、メモリ可用性および処理能力）の浪費が減る。
ＣＬＤによって、要求の区別されたロード・バランシングも実行され、これによって、ＱｏＳ／ＳＬＡの厳密な実施がもたらされる。
各ＳＲＨは、ターゲット・コンポーネントに直接に要求をディスパッチする。したがって、要求の平行ディスパッチが行われる。要求が、ターゲット・コンポーネントに最終的にディスパッチされる前に通過しなければならないボトルネックはない。これによって、ＣＬＤのスループットが高まる。
ＣＬＤで除去される要求の数は、システム・リソースがより効率的に使用されるので減る。したがって、第２レベルに転送される要求は、高い残存確率を有するか、転送の高いユーティリティを有するものだけである。これは、ＣＬＤアーキテクチャのレベル間のフロー制御によって達成される。
実施形態１：ＣＬＤは、オブジェクト指向技術を使用して実施することができる。たとえば、Ｃ＋＋を使用して、システムを実施することができる。各モジュール／エンティティは関連するクラス、Ｂｕｆｆｅｒ、Ｑｕｅｕｅ、ＧＲＨ、ＳＲＨ、ＬＤＣ、ＲＤＭ、ＲＤを有する。ＳＬＢおよびＧＲＢは、Ｂｕｆｆｅｒのサブクラスである。オブジェクト・メッセージングが、これらのクラスのオブジェクトの間で、通信を実行するのに使用される。ＣＬＤには、１つのＧＲＨ、複数のＳＲＨ、１つのＲＤＭ、および１つのＬＤＣのオブジェクトが含まれる。各ＧＲＨに、オブジェクトＧＲＢが含まれる。各ＳＲＨに、ＳＬＢおよびＲＤのオブジェクトが含まれる。各ＲＤＭが、各ＳＲＨとの関連関係を有する。各ＬＤＣに、前レベル・ロード・バランサおよび次レベル・ロード・バランサのリストが含まれる。ＲＤＭは、ロード・バランサとの関連を有する。
もう１つの実施形態では、ＣＬＤが、ＩＣまたは論理回路あるいはその両方であり、これに、マイクロプロセッサＩｎｔｅｌ ｘ８６としてのＬＤＣ、別のマイクロプロセッサＩｎｔｅｌ ｘ８６としてのＲＤＭ、Ｉｎｔｅｌ ｘ８６としてのＲＤ、ＧＲＢのＤＲＡＭメモリを有するＧＲＨが含まれる。ＳＬＢも、ＤＲＡＭメモリとして実施される。要求を受け取り、要求を送り、フロー制御メッセージを通信する入出力に標準ネットワーク・カード／インターフェースを使用することができる。ロード・バランサの間の通信のプロトコルを、ＴＣＰ／ＩＰとすることができる。
実施形態２：連繋負荷バランシングのフレームワーク
図１に関して説明したモデルは、マルチレベル処理システム（フレームワーク）で実施され、クラスタの前の各ロード・バランサ（スケジューラ）を、キューとしてモデル化することができる。そのようなキューの処理機能は、ディスパッチ機能である。各キューに関連する１つまたは複数のクラスタがありえる。感知モジュール、実施モジュール、および交換モジュールの機能性を、各ロード・バランサ（ＣＬＤ５００）のＬＤＣ５０８によって実行することができる。図５に関して上で説明したＣＬＤ５００は、そのようなマルチ・レベル処理システム（フレームワーク）で、図６に示されているように使用される。
ここで、このフレームワークが使用される環境を短く説明する。連繋負荷バランシング・フレームワークを使用する集中システムに、システムの複製の組が含まれる。これらの複製は、着信要求について負荷が平衡化される。連繋する負荷バランシング・フレームワークを使用する分散システムに、そのコンポーネントのクラスタが含まれる。システム全体の複製は、使用されない。コンポーネントの複製のクラスタが使用される。各クラスタに、１つのコンポーネントの複製が含まれる。クラスタに関連するロード・バランサが、そのクラスタの複製の間で負荷を分配する。中間クラスタでの要求除去を減らすために、ロード・バランサの間でクラスタにまたがってフロー制御が使用される（図６）。
連繋負荷バランシング・フレームワーク（図１で説明したモデルに基づく）の例を、図６に関してこれから説明する。本発明の趣旨および範囲から逸脱せずにＣＬＤ５００を使用する連繋負荷バランシング・フレームワークの多数の変形形態がありえることに留意されたい。
このフレームワークで使用されるＣＬＤは、感知モジュール、実施モジュール、および交換モジュールの機能性を実行するために、ＣＬＤ５００のアーキテクチャを有する。この例のフレームワークには、それぞれクラスタ６０４、クラスタ６１０、クラスタ６１２、およびクラスタ６１６のコンポーネントに要求を分配するＣＬＤ６０２、ＣＬＤ６０６、ＣＬＤ６０８、およびＣＬＤ６１４（それぞれがＣＬＤ５００のシステム・アーキテクチャを有する）が含まれる。情報（またはメッセージ）６１８が、ＣＬＤ６０６およびＣＬＤ６０２の間で交換され、情報６２０が、ＣＬＤ６０８とＣＬＤ６０２の間で交換される。同様に、情報６２２が、ＣＬＤ６１４とＣＬＤ６０６の間で交換され、情報６２４が、ＣＬＤ６１４とＣＬＤ６０８の間で交換される。
ロード・バランシング・フレームワークへの要求は、ＣＬＤ６０２に進み、クラスタ６０４のフロントエンド・コンポーネントの１つに分配される。フロントエンド・コンポーネントによる処理の後に、要求は、その要求の後続処理要件に応じて、ＣＬＤ６０６（サーバ・アプリケーションＡのクラスタ６１０を制御する）またはＣＬＤ６０８（サーバ・アプリケーションＢのクラスタ６１２を制御する）のいずれかに進む可能性がある。この処理の後に、要求が、ＣＬＤ６１４に送られ、ＣＬＤ６１４によって、要求の処理を完了するために、要求が、クラスタ６１６内のデータベースの間で分配される。さまざまなクラスタへの要求のフローは、ＣＬＤ間の情報のフローによって左右される。
これから、ＣＬＤ５００を、上で説明した連繋負荷バランサ・フレームワークで使用する方法を説明する。既に説明したように、各ＣＬＤ５００が、ＬＤＣ５０８を有し、これによって、ＣＬＤ５００が、メッセージを生成し、フレームワーク内の他のＣＬＤと交換できるようになる。したがって、この実施形態では、ＬＤＣ５０８が、ＣＬＤ５００（キューとして働く）の感知モジュールならびに生成モジュールとして働く。ＬＤＣ５０８は、負荷モニタ（ＬＭ）とも情報を交換する。前に説明したモジュール／コンポーネントのほかに、ＬＤＣ５０８には、さまざまなコンポーネント、隣接するロード・バランサ、および隣接するリソース・マネージャからのメッセージのレシーバと、そのようなコンポーネントへのメッセージのセンダー（sender）と、始動時のシステムの初期化のモジュール、クラスタ内の動的な修正に起因してＣＬＤレコードを更新するモジュールも含まれる。ＬＤＣ５０８は、新しい要求クラスに基づくか、クラスタの要求処理容量の変化に基づいてＣＬＤの構成を動的に修正するモジュールも有する。手短に言えば、ＬＤＣ５０８は、ＬＤＣシステム全体を管理し、ロード・バランサの間でクラスタにまたがってフロー制御を適用する責任を負う。
ＧＲＨ５０２のバッファがほぼ満杯になる（たとえば、前レベルＣＬＤの高い要求ディスパッチ速度に起因する）場合に、ＧＲＨは、その状態に関してＬＤＣに制御メッセージを送る。このメッセージは、関連するデータが含まれ、着信要求速度、要求分類速度、要求ディスパッチ速度などを含めることができる。ＬＤＣは、ＧＲＢのバッファ・サイズを増やす、または前レベルＣＬＤにフロー制御メッセージを送る、あるいはその両方を行うかどうかを判断する。
ＬＤＣ５０８は、フロー制御メッセージを生成し、前レベル・ロード・ディストリビュータに送る時を判断する責任を負う。ＧＲＨがほぼ満杯である時に、ＬＤＣは、ＧＲＨにフロー制御メッセージを送ることができる。ＧＲＨは、必要な場合にＧＲＢのバッファ・サイズを増やす。ＧＲＨは、指示を成功裡に実施した場合に肯定応答をＬＤＣに送り、そうでない場合には、否定応答がＬＤＣに送られる。フロー制御指示を成功裡に実施した時に、ＬＤＣは、要求クラスｒの新しいディスパッチ速度をすべての次レベル・ディストリビュータに送る。そのようなＣＬＤは、そのメッセージを受け取る時に、レコードを更新する。
要求クラスｒのクラスタ内のＳＬＢの容量またはあるインスタンスの容量（要求速度に関する）の大きい増加がある場合に、ＬＤＣは、前レベル・ロード・バランサに、容量の増加、それが処理できる予測（容量増加に起因する）最大要求速度、ｒに関する現在のディスパッチ速度、ｒに関する現在の着信要求などについて通知する。ＬＤＣは、要求クラスｒに関して前のロード・バランサにフロー制御メッセージを最近に送った場合に限って通知する。前レベルＣＬＤのＬＤＣは、そのようなメッセージを受け取るとすぐに、ｒに関する要求ディスパッチ速度の可能な増加の量ｄを計算する。その後、前レベルＣＬＤのＬＤＣは、ＧＲＨまたはＲＤＭあるいはその両方に、ｒのディスパッチ速度を増やすように指示する。
リソース・マネージャは、新しい要求クラスｒを追加する場合に、ＣＬＤのＬＤＣにその更新に関して通知する。更新には、可能なＱｏＳ／ＳＬＡパラメータまたは可能な最大要求速度あるいはその両方も含まれる。フロントエンド・クラスタへのクラスｒの要求速度は、所与の点での要求クラスｒのすべてのエンドユーザからの集合要求速度である。しかし、フロントエンド・クラスタのクラスｒの各要求によって、次のクラスタに関する複数の要求が生成される場合がある。したがって、クラスタごとに、おそらくは異なる着信要求速度がある。ＬＤＣは、ｒに関する、ＧＲＢサイズに対する可能な変更およびＳＬＢの可能なサイズに基づいて判断する。ＬＤＣは、まず、ＳＬＢへの適当な変更を行うようにＲＤＭに指示する。ＲＤＭから肯定の応答を受け取る時に、ＬＤＣは、ＧＲＢサイズの変更および新しい要求クラスｒの追加についてＧＲＨに指示する。ＧＲＨは、ＧＲＢサイズを増やし、要求クラスのリストを更新することによって、ＬＤＣ指示を実施する。ＧＲＨは、成功裡の完了の際に肯定応答を送る。ＧＲＨは、失敗する場合に、否定応答を送る。
同様に、要求クラスｒの削除について、ＬＤＣは、ＧＲＢサイズの可能な変更について判断する。ＬＤＣは、適当なＳＲＨを削除するようにＲＤＭに指示を送る。ＲＤＭから肯定の応答を受け取る時に、ＬＤＣは、適当に、ＧＲＢのサイズを変更し、レコードから要求クラスｒを削除するようにＧＲＨに指示する。ＧＲＨは、ＧＲＢのサイズを変更し、リストを更新し、肯定の応答をＬＤＣに送る。ＧＲＨおよびＲＤＭの両方から肯定の応答を受け取る時に、ＬＤＣは、必要な場合に、「要求クラスｒが削除された」ことを含む肯定応答をＲＭに送ることができる。ＧＲＨ／ＬＤＣ／ＲＤＭでのなんらかの種類の障害によって、ロード・バランサが効果的に要求クラスｒを削除できない場合には、ＬＤＣは、必要な場合に、リソース・マネージャに否定応答を送ることができる。
図７に示されているように代替実施形態では、クラスタ間ロード・バランサの間での集中フロー制御を使用することができる。この実施形態では、ＣＬＤごとにＬＤＣを有するのではなく、集中的な形でフロー制御を実行する１つまたは複数の集中ＬＤＣ７０２を設けることができる。この集中ＬＤＣ７０２の重要な機能に、フロー制御が含まれる。リソース・マネージャ割振りプランの実施、ＲＤを作成または削除するようにＲＤＭに指示すること、ＧＲＨおよびＲＤＭからの制御メッセージの受取、スタートアップ中のＣＬＤの初期化を含むＬＤＣの機能の一部を、各ロード・ディストリビュータにローカルなエンティティ（たとえば部分的なＬＤＣ）によって実行することができる。対応するロード・バランシング・フレームワークを、図７に示す。
ロード・バランシングに関する提案されるフレームワークによって、クラスタごとの基礎でのロード・バランシングおよびクラスタ間ロード・バランサの間のフロー制御が容易になる。連繋負荷ディストリビュータ（ＣＬＤ）のシステムが、クラスタ間ロード・バランサの間の分散フロー制御を実行する。連繋負荷ディストリビュータは、システムに存在する場合に、リソース・マネージャによるカスタマへのインスタンス容量の動的な割振りおよび割振り解除を考慮する。また、ＣＬＤは、システムに存在する場合に、負荷モニタによって収集される動的な負荷情報を使用して、負荷を効率的に平衡化する。ＣＬＤは、顧客ごとの現在の着信要求速度および顧客ごとの要求ディスパッチ速度、または容量割振り／割振り解除、あるいはその両方に基づいて、あるいは他のシステム状態に基づいて、前レベルＣＬＤに制御メッセージを送るかどうかを動的に決定する。
本発明の好ましい実施形態を図示し、説明したが、本発明が、これらの実施形態だけに制限されないことは明瞭である。請求項に記載の本発明の趣旨および範囲から逸脱しない多数の修正、変更、変形、置換、および同等物が可能であることは、当業者に明白であろう。
まとめとして、本発明の構成に関して以下の事項を開示する。
（１）マルチレベル・コンピュータ・システムで処理される要求のスケジューリングの方法であって、前記コンピュータ・システムの各レベルが、少なくとも１つのキューを有し、各キューが、少なくとも１つの処理機能を関連付けられ、
ａ．第１レベルの前記キューに前記要求をバッファリングするステップと、
ｂ．前記第１レベルに隣接する他のレベルとフロー情報を交換するステップと、
ｃ．前記要求の分類値を得るステップと、
ｄ．前記得られた値に基づいて前記要求をスケジューリングするステップと
を含む方法。
（２）スケジューリングする前記ステップが、前記要求をディスパッチするステップを含む、上記（１）に記載の方法。
（３）スケジューリングする前記ステップが、前記要求を分類するステップを含む、上記（１）に記載の方法。
（４）スケジューリングする前記ステップが、前記要求を除去するステップを含む、上記（１）に記載の方法。
（５）前記得られた分類値が事前定義の値より大きい場合に、前記第１レベルで前記要求を処理するステップをさらに含む、上記（１）に記載の方法。
（６）前記分類値を得る前記ステップが、
ａ．前記交換されるフロー情報に基づいてユーティリティ値を計算するステップと、
ｂ．前記計算されるユーティリティ値が事前定義の値より小さい場合に訂正処置を仮定するステップと、
ｃ．前記仮定される訂正処置を考慮した後の前記ユーティリティ値を再計算するステップと
を含む、上記（１）に記載の方法。
（７）ａ．前記再計算されるユーティリティ値が前記事前定義の値より大きい場合に、仮定された訂正処置を行うステップと、
ｂ．前記仮定された訂正処置を行った後に、前記第１レベルで前記要求を処理するステップと
をさらに含む、上記（６）に記載の方法。
（８）訂正処置を仮定する前記ステップが、適当なキューが要求を受け入れることができない場合に、前記適当なキューの要求処理容量の増加を仮定するステップを含む、上記（６）に記載の方法。
（９）訂正処置を仮定する前記ステップが、次レベルのキューが要求を受け入れることができない場合に、適当なキューからの要求ディスパッチ速度の減少を仮定するステップを含む、上記（６）に記載の方法。
（１０）マルチレベル・コンピュータ・システムで処理される要求のスケジューリングに適するシステムであって、前記コンピュータ・システムの各レベルが、少なくとも１つのキューを有し、各キューが、少なくとも１つの処理機能を関連付けられ、
ａ．第１レベルと前記第１レベルに隣接する他のレベルとの間でフロー情報を交換する手段と、
ｂ．前記交換されるフロー情報に基づいて、前記要求の分類値を得る手段と、
ｃ．前記要求をスケジューリングする手段と
を含むシステム。
（１１）前記スケジューリングする手段が、前記要求をディスパッチする手段をさらに含む、上記（１０）に記載のシステム。
（１２）前記スケジューリングする手段が、前記要求を分類する手段をさらに含む、上記（１０）に記載のシステム。
（１３）前記スケジューリングする手段が、前記要求を除去する手段をさらに含む、上記（１０）に記載のシステム。
（１４）前記得られる分類値が事前定義の値より大きい場合に、前記第１レベルで前記要求を処理する手段をさらに含む、上記（１０）に記載のシステム。
（１５）前記分類値を得る前記手段が、
ａ．前記交換されるフロー情報に基づいてユーティリティ値を計算する手段と、
ｂ．仮定された訂正処置を検討した後の前記ユーティリティ値を再計算する手段と、
ｃ．前記再計算されるユーティリティ値が事前定義の値より大きい場合に、前記仮定された訂正処置を行う手段と
を含む、上記（１０）に記載のシステム。
（１６）前記仮定された訂正処置を行う前記手段が、第２レベル・キューが余分な要求を受け入れることができない場合に、第１レベル・キューの要求ディスパッチ速度を減らす手段を含む、上記（１５）に記載のシステム。
（１７）前記仮定された訂正処置を行う前記手段が、第２レベル・キューが余分な要求を受け入れることができない場合に、第２レベル・キューの要求処理容量を増やす手段を含む、上記（１５）に記載のシステム。
（１８）コンピュータ・システムで要求をスケジューリングするコンピュータ・プログラム製品であって、
ａ．第１レベルのキューに前記要求をバッファリングするプログラム命令手段と、
ｂ．前記第１レベルに隣接する他のレベルとフロー情報を交換するプログラム命令手段と、
ｃ．前記要求の分類値を得るプログラム命令手段と、
ｄ．前記分類値に基づいて前記要求をスケジューリングするプログラム命令手段と
を含むコンピュータ・プログラム製品。
（１９）コンピュータ・システムでのロード・バランシングに適する装置であって、
ａ．複数のキューであって、
ｉ．着信要求をバッファリングする第１レベル・キューと、
ｉｉ．複数の後続レベル・キューであって、キューの各後続レベルが、着信要求のクラスに対応する、複数の後続レベル・キューと
を含む複数のキューと、
ｂ．ユーザ定義パラメータに基づいて、前記要求を複数の後続レベル・キューに分類する手段と、
ｃ．前記複数のレベルのキューの間で情報を交換する手段と、
ｄ．前記キューからの前記要求を前記キューまたはターゲット・コンポーネントの少なくとも１つにディスパッチする手段と
を含む装置。
（２０）ディスパッチする前記手段が、要求の平行ディスパッチの手段を含む、上記（１９）に記載の装置。
（２１）情報を交換する前記手段が、前記キューからの要求のディスパッチ速度を制御する手段を含む、上記（１９）に記載の装置。
（２２）前記要求が、ＱｏＳ／ＳＬＡおよび前記後続レベル・キューからの情報に基づいて前記第１レベル・キューで分類される、上記（１９）に記載の装置。
（２３）コンピュータ・システムでのロード・バランシングのコンピュータ・プログラム製品であって、
ａ．複数のキューを生成するプログラム命令手段であって、前記複数のキューが、
ｉ．着信要求をバッファリングする第１レベル・キューと、
ｉｉ．複数の後続レベル・キューであって、キューの各後続レベルが、着信要求のクラスに対応する、複数の後続レベル・キューと
を含む、プログラム命令手段と
ｂ．ユーザ定義パラメータに基づいて、前記要求を複数のクラスに分類するプログラム命令手段と、
ｃ．前記複数のレベルのキューの間で情報を交換するプログラム命令手段と、
ｄ．前記キューからの前記要求を前記キューまたはターゲット・コンポーネントの少なくとも１つにディスパッチするプログラム命令手段と
を含むコンピュータ・プログラム製品。
（２４）コンピュータ・システムで要求をスケジューリングするのに適するシステムであって、
ａ．複数のクラスタと、
ｂ．複数のロード・バランサであって、各ロード・バランサが、少なくとも１つのクラスタに対応し、
ｉ．要求を受け取る手段と、
ｉｉ．隣接レベル・ロード・バランサから情報を交換する手段と、
ｉｉｉ．前記要求の分類値を得る手段と、
ｉｖ．前記分類値に基づいて次レベル・クラスタに前記要求をディスパッチする手段と
を含む、複数のロード・バランサと
を含むシステム。
（２５）ネットワークで要求をスケジューリングする方法であって、前記ネットワークが、複数のロード・バランサを含み、
ａ．第１レベル・ロード・バランサで要求を受け取るステップと、
ｂ．前記特定の要求に関する情報を隣接レベル・ロード・バランサと交換するステップと、
ｃ．前記交換される情報を処理することによって前記要求の分類値を得るステップと、
ｄ．前記得られる値に基づいて前記要求をスケジューリングするステップと
を含む方法。
（２６）前記交換される情報を処理する前記ステップが、
ａ．前記要求の転送の閾ユーティリティ値を判定するステップと、
ｂ．前記要求の転送のユーティリティ値を得るステップと、
ｃ．前記ユーティリティ値と前記閾ユーティリティ値とを比較するステップと、
ｄ．ユーティリティ値が前記閾ユーティリティ値より小さい場合に訂正処置を行うステップと
を含む、上記（２５）に記載の方法。
（２７）ユーティリティの閾値を判定する前記ステップが、さらに
ａ．前記ネットワークがサービスを必要とするＱｏＳ要件およびＳＬＡ要件を識別するステップと、
ｂ．前記ネットワーク内で前記要求に割り振られるリソースを判定するステップと
を含む、上記（２６）に記載の方法。
（２８）前記ユーティリティ値を得る前記ステップが、
ａ．要求ヘッダから前記要求に関係するＱｏＳおよびＳＬＡを識別するステップと、
ｂ．次レベル・バランサで前記要求に対応する割り振られるリソースを判定するステップと、
ｃ．前記ユーティリティ値を得るために前記識別された情報および前記判定された情報を処理するステップと
を含む、上記（２６）に記載の方法。
（２９）訂正処置を行う前記ステップが、前記ロード・バランサでの要求ディスパッチ速度を下げるステップを含む、上記（２６）に記載の方法。
（３０）訂正処置を行う前記ステップが、余分な負荷を受け入れるためにロード・バランサ容量を増やすステップを含み、ロード・バランサ容量を増やすステップが、前記要求の前記ユーティリティ値を増やす、上記（２６）に記載の方法。
（３１）ネットワーク内で要求をスケジューリングするコンピュータ・プログラム製品であって、
ａ．第１レベル・ロード・バランサで要求を受け取る第１プログラム命令手段と、
ｂ．前記要求に関する情報を隣接レベル・ロード・バランサと交換する第２プログラム命令手段と、
ｃ．前記交換される情報に基づいて前記要求の分類値を得る第３プログラム命令手段と、
ｄ．前記分類値に基づいて前記要求をスケジューリングする第４プログラム命令手段と
を含むコンピュータ・プログラム製品。
本発明の好ましい実施形態による、要求を処理するシステムの例を示す図である。 本発明の好ましい実施形態による、要求を処理するために実施されるステップのシーケンスの例を示す図である。 ユーティリティ値の計算を示すのに使用される表の例を示す図である。 ロード・バランサの要求ディスパッチ速度を修正した後に要求が渡せるようになる、例示的な事例でのステップのシーケンスを示す図である。 要求除去の数を減らすための情報のフローという発想に基づく連繋負荷ディストリビュータ（ＣＬＤ）の全体的なシステム・アーキテクチャを示す図である。 図５で説明したＣＬＤの間での情報のフローという発想に基づく連繋負荷バランシング・フレームワークを示す図である。 ロード・バランサの間での情報のフローという発想に基づくもう１つの連繋負荷バランシング・フレームワークを示す図である。
符号の説明
５００ 連繋負荷ディストリビュータ（ＣＬＤ）
５０２ グローバル要求ハンドラ（ＧＲＨ）
５０４ 特定要求ハンドラ（ＳＲＨ）
５０６ 要求ディスパッチ・マネージャ（ＲＤＭ）
５０８ 負荷分配コントローラ（ＬＤＣ）
６０２ ＣＬＤ
６０４ クラスタ
６０６ ＣＬＤ
６０８ ＣＬＤ
６１０ クラスタ
６１４ ＣＬＤ
６１２ クラスタ
６１６ クラスタ

Claims (31)

  1. マルチレベル・コンピュータ・システムで処理される複数の要求をスケジューリングする方法であって、前記コンピュータ・システムの各レベルが、少なくとも１つのキューを有し、各キューが、少なくとも１つの処理機能を関連付けられ、
    前記方法が、
    ａ．第１レベルの前記キューに前記要求をバッファリングするステップと、
    ｂ．前記第１レベルに隣接する他のレベルとフロー情報を交換するステップと、
    ｃ．前記交換されるフロー情報に基づいて前記要求の夫々の分類値を得るステップと、
    ｄ．前記得られた分類値の夫々に基づいて前記要求の夫々をスケジューリングするステップと
    を含む方法。
  2. スケジューリングする前記ステップが、前記要求をディスパッチするステップを含む、請求項１に記載の方法。
  3. スケジューリングする前記ステップが、前記要求を分類するステップを含む、請求項１に記載の方法。
  4. スケジューリングする前記ステップが、前記要求を除去するステップを含む、請求項１に記載の方法。
  5. 前記得られた分類値が事前定義の値より大きい場合に、前記第１レベルで前記要求を処理するステップをさらに含む、請求項１に記載の方法。
  6. 前記交換するステップが、前記フロー情報に基づいて、前記他のレベルのキューで要求が残存する確率が判定されるステップを含み、
    前記分類値を得る前記ステップが、
    ｅ．前記交換されるフロー情報に基づいてユーティリティ値を計算するステップであって、前記ユーティリティ値が、前記残存する確率と、要求の優先順位とによって決定されるステップと、
    ｆ．前記計算されるユーティリティ値が事前定義の値より小さい場合に訂正処置を仮定するステップと、
    ｇ．前記仮定される訂正処置を考慮した後の前記ユーティリティ値を再計算するステップと
    を含む、請求項１に記載の方法。
  7. ｈ．前記再計算されるユーティリティ値が前記事前定義の値より大きい場合に、仮定された訂正処置を行うステップと、
    ｉ．前記仮定された訂正処置を行った後に、前記第１レベルで前記要求を処理するステップと
    をさらに含む、請求項６に記載の方法。
  8. 訂正処置を仮定する前記ステップが、適当なキューが要求を受け入れることができない場合に、前記適当なキューの要求処理容量の増加を仮定するステップを含む、請求項６に記載の方法。
  9. 訂正処置を仮定する前記ステップが、次レベルのキューが要求を受け入れることができない場合に、適当なキューからの要求ディスパッチ速度の減少を仮定するステップを含む、請求項６に記載の方法。
  10. マルチレベル・コンピュータ・システムで処理される複数の要求をスケジューリングするシステムであって、前記コンピュータ・システムの各レベルが、少なくとも１つのキューを有し、各キューが、少なくとも１つの処理機能を関連付けられ、
    前記システムが、
    ａ．第１レベルの前記キューに前記要求をバッファリングする手段と、
    ｂ．前記第１レベルと前記第１レベルに隣接する他のレベルとの間でフロー情報を交換する手段と、
    ｃ．前記交換されるフロー情報に基づいて前記要求の夫々の分類値を得る手段と、
    ｄ．前記得られた分類値の夫々に基づいて前記要求の夫々をスケジューリングする手段と
    を含むシステム。
  11. 前記スケジューリングする手段が、前記要求をディスパッチする手段をさらに含む、請求項１０に記載のシステム。
  12. 前記スケジューリングする手段が、前記要求を分類する手段をさらに含む、請求項１０に記載のシステム。
  13. 前記スケジューリングする手段が、前記要求を除去する手段をさらに含む、請求項１０に記載のシステム。
  14. 前記得られる分類値が事前定義の値より大きい場合に、前記第１レベルで前記要求を処理する手段をさらに含む、請求項１０に記載のシステム。
  15. 前記交換する手段が、前記フロー情報に基づいて、前記他のレベルのキューで要求が残存する確率が判定される手段を含み、
    前記分類値を得る前記手段が、
    ｅ．前記交換されるフロー情報に基づいてユーティリティ値を計算する手段であって、前記ユーティリティ値が、前記残存する確率と、要求の優先順位とによって決定される手段と、
    ｆ．仮定された訂正処置を検討した後の前記ユーティリティ値を再計算する手段と、
    ｇ．前記再計算されるユーティリティ値が事前定義の値より大きい場合に、前記仮定された訂正処置を行う手段と
    を含む、請求項１０に記載のシステム。
  16. 前記仮定された訂正処置を行う前記手段が、第２レベル・キューが余分な要求を受け入れることができない場合に、第１レベル・キューの要求ディスパッチ速度を減らす手段を含む、請求項１５に記載のシステム。
  17. 前記仮定された訂正処置を行う前記手段が、第２レベル・キューが余分な要求を受け入れることができない場合に、第２レベル・キューの要求処理容量を増やす手段を含む、請求項１５に記載のシステム。
  18. マルチレベル・コンピュータ・システムで処理される複数の要求をスケジューリングするコンピュータ・プログラムであって、前記コンピュータ・システムの各レベルが、少なくとも１つのキューを有し、各キューが、少なくとも１つの処理機能を関連付けられ、コンピュータ・システムに、
    ａ．第１レベルの前記キューに前記要求をバッファリングするステップと、
    ｂ．前記第１レベルに隣接する他のレベルとフロー情報を交換するステップと、
    ｃ．前記交換されるフロー情報に基づいて前記要求の分類値を得るステップと、
    ｄ．前記得られた分類値の夫々に基づいて前記要求の夫々をスケジューリングするステップと
    を実行させるコンピュータ・プログラム。
  19. コンピュータ・システムでのロード・バランシングをする装置であって、
    ａ．複数のキューであって、
    ｉ．着信要求をバッファリングする第１レベル・キューと、
    ｉｉ．複数の後続レベル・キューであって、キューの各後続レベルが、着信要求のクラスに対応する、複数の後続レベル・キューと
    を含む複数のキューと、
    ｂ．ユーザ定義パラメータに基づいて、前記要求を複数の後続レベル・キューに分類する手段と、
    ｃ．前記複数のレベルのキューの間でフロー情報を交換する手段と、
    ｄ．前記交換されるフロー情報に基づいて前記要求の夫々の分類値を得る手段と、
    ｅ．前記得られた分類値の夫々に基づいて前記キューからの前記要求の夫々を前記キューまたはターゲット・コンポーネントの少なくとも１つにディスパッチする手段と
    を含む装置。
  20. ディスパッチする前記手段が、要求の平行ディスパッチの手段を含む、請求項１９に記載の装置。
  21. 情報を交換する前記手段が、前記キューからの要求のディスパッチ速度を制御する手段を含む、請求項１９に記載の装置。
  22. 前記要求が、ＱｏＳ／ＳＬＡおよび前記後続レベル・キューからの情報に基づいて前記第１レベル・キューで分類される、請求項１９に記載の装置。
  23. コンピュータ・システムでのロード・バランシングのコンピュータ・プログラムであって、コンピュータ・システムに、
    ａ．複数のキューを生成するステップであって、前記複数のキューが、
    ｉ．着信要求をバッファリングする第１レベル・キューと、
    ｉｉ．複数の後続レベル・キューであって、キューの各後続レベルが、着信要求のクラスに対応する、複数の後続レベル・キューと
    を含む、前記生成するステップと
    ｂ．ユーザ定義パラメータに基づいて、前記要求を複数のクラスに分類するステップと、
    ｃ．前記複数のレベルのキューの間でフロー情報を交換する手段と、
    ｄ．前記交換されるフロー情報に基づいて前記要求の夫々の分類値を得る手段と、
    ｅ．前記得られた分類値の夫々に基づいて前記キューからの前記要求の夫々を前記キューまたはターゲット・コンポーネントの少なくとも１つにディスパッチするステップと
    を実行させるコンピュータ・プログラム。
  24. コンピュータ・システムで要求をスケジューリングするシステムであって、
    ａ．複数のクラスタと、
    ｂ．複数のロード・バランサであって、各ロード・バランサが、少なくとも１つのクラスタに対応し、
    ｉ．要求を受け取る手段と、
    ｉｉ．隣接レベル・ロード・バランサからフロー情報を交換する手段と、
    ｉｉｉ．前記交換されるフロー情報に基づいて前記要求の夫々の分類値を得る手段と、
    ｉｖ．前記得られた分類値の夫々に基づいて次レベル・クラスタに前記要求の夫々をディスパッチする手段と
    を含む、複数のロード・バランサと
    を含むシステム。
  25. 複数のロード・バランサを含むネットワーク内で複数の要求をスケジューリングする方法であって、
    ａ．第１レベル・ロード・バランサで要求を受け取るステップと、
    ｂ．前記要求に関する情報を隣接レベル・ロード・バランサと交換するステップと、
    ｃ．前記交換される情報に基づいて前記要求の夫々の分類値を得るステップと、
    ｄ．前記得られた分類値の夫々に基づいて前記要求の夫々をスケジューリングするステップと
    を含む方法。
  26. 前記交換するステップが、前記情報に基づいて、前記隣接レベルのキューで要求が残存する確率が判定されるステップを含み、
    前記分類値を得る前記ステップが、
    ｅ．前記要求の転送の閾ユーティリティ値を判定するステップと、
    ｆ．前記要求の転送のユーティリティ値を得るステップであって、前記ユーティリティ値が、前記残存する確率と、要求の優先順位とによって決定されるステップと、
    ｇ．前記ユーティリティ値と前記閾ユーティリティ値とを比較するステップと、
    ｈ．前記ユーティリティ値が前記閾ユーティリティ値より小さい場合に訂正処置を行うステップと
    を含む、請求項２５に記載の方法。
  27. ユーティリティの閾値を判定する前記ステップが、
    ｉ．前記ネットワークがサービスを必要とするＱｏＳ要件およびＳＬＡ要件を識別するステップと、
    ｊ．前記ネットワーク内で前記要求に割り振られるリソースを判定するステップと
    をさらに含む、請求項２６に記載の方法。
  28. 前記ユーティリティ値を得る前記ステップが、
    ｋ．要求ヘッダから前記要求に関係するＱｏＳおよびＳＬＡを識別するステップと、
    ｌ．次レベル・バランサで前記要求に対応する割り振られるリソースを判定するステップと、
    ｍ．前記ユーティリティ値を得るために前記識別された情報および前記判定された情報を処理するステップと
    を含む、請求項２６に記載の方法。
  29. 訂正処置を行う前記ステップが、前記ロード・バランサでの要求ディスパッチ速度を下げるステップを含む、請求項２６に記載の方法。
  30. 訂正処置を行う前記ステップが、余分な負荷を受け入れるためにロード・バランサ容量を増やすステップを含み、ロード・バランサ容量を増やすステップが、前記要求の前記ユーティリティ値を増やす、請求項２６に記載の方法。
  31. 複数のロード・バランサを含むネットワーク内で複数の要求をスケジューリングするコンピュータ・プログラムであって、コンピュータ・システムに、
    ａ．第１レベル・ロード・バランサで要求を受け取るステップと、
    ｂ．前記要求に関する情報を隣接レベル・ロード・バランサと交換するステップでと、
    ｃ．前記交換される情報に基づいて前記要求の夫々の分類値を得るステップと、
    ｄ．前記得られた分類値の夫々に基づいて前記要求の夫々をスケジューリングするステップと
    を実行させるコンピュータ・プログラム。
JP2003415773A 2002-12-17 2003-12-12 タスク・スケジューリングの方法、システム、およびプログラム製品 Expired - Fee Related JP3818655B2 (ja)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
US10/321,680 US7243351B2 (en) 2002-12-17 2002-12-17 System and method for task scheduling based upon the classification value and probability

Publications (2)

Publication Number Publication Date
JP2004199678A JP2004199678A (ja) 2004-07-15
JP3818655B2 true JP3818655B2 (ja) 2006-09-06

Family

ID=32507113

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2003415773A Expired - Fee Related JP3818655B2 (ja) 2002-12-17 2003-12-12 タスク・スケジューリングの方法、システム、およびプログラム製品

Country Status (3)

Country Link
US (1) US7243351B2 (ja)
JP (1) JP3818655B2 (ja)
CN (1) CN100343810C (ja)

Families Citing this family (123)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7808937B2 (en) 2005-04-07 2010-10-05 Rambus, Inc. Variable interference cancellation technology for CDMA systems
US7426535B2 (en) 2002-10-08 2008-09-16 Telecommunication Systems, Inc. Coordination of data received from one or more sources over one or more channels into a single context
US7986625B2 (en) * 2002-12-10 2011-07-26 International Business Machines Corporation Resource-aware system, method and program product for managing request traffic based on a management policy
JP4077352B2 (ja) * 2003-03-31 2008-04-16 株式会社日立製作所 負荷分散方法及びその実施システム並びにその処理プログラム
US7657933B2 (en) * 2003-04-12 2010-02-02 Cavium Networks, Inc. Apparatus and method for allocating resources within a security processing architecture using multiple groups
US7661130B2 (en) * 2003-04-12 2010-02-09 Cavium Networks, Inc. Apparatus and method for allocating resources within a security processing architecture using multiple queuing mechanisms
US7483374B2 (en) * 2003-08-05 2009-01-27 Scalent Systems, Inc. Method and apparatus for achieving dynamic capacity and high availability in multi-stage data networks using adaptive flow-based routing
US7664847B2 (en) * 2003-08-14 2010-02-16 Oracle International Corporation Managing workload by service
US7441033B2 (en) 2003-08-14 2008-10-21 Oracle International Corporation On demand node and server instance allocation and de-allocation
US7552171B2 (en) * 2003-08-14 2009-06-23 Oracle International Corporation Incremental run-time session balancing in a multi-node system
US7953860B2 (en) * 2003-08-14 2011-05-31 Oracle International Corporation Fast reorganization of connections in response to an event in a clustered computing system
US7437459B2 (en) 2003-08-14 2008-10-14 Oracle International Corporation Calculation of service performance grades in a multi-node environment that hosts the services
US20060064400A1 (en) * 2004-09-21 2006-03-23 Oracle International Corporation, A California Corporation Methods, systems and software for identifying and managing database work
US7437460B2 (en) 2003-08-14 2008-10-14 Oracle International Corporation Service placement for enforcing performance and availability levels in a multi-node system
US8365193B2 (en) * 2003-08-14 2013-01-29 Oracle International Corporation Recoverable asynchronous message driven processing in a multi-node system
US7516221B2 (en) * 2003-08-14 2009-04-07 Oracle International Corporation Hierarchical management of the dynamic allocation of resources in a multi-node system
US20050256971A1 (en) * 2003-08-14 2005-11-17 Oracle International Corporation Runtime load balancing of work across a clustered computing system using current service performance levels
CN100547583C (zh) * 2003-08-14 2009-10-07 甲骨文国际公司 数据库的自动和动态提供的方法
US20050044127A1 (en) * 2003-08-18 2005-02-24 Vivek Jaiswal Dynamic load distribution within a session initiation protocol network
US8356098B2 (en) * 2003-11-10 2013-01-15 Hewlett-Packard Development Company, L.P. Dynamic management of workloads in clusters
US8782654B2 (en) 2004-03-13 2014-07-15 Adaptive Computing Enterprises, Inc. Co-allocating a reservation spanning different compute resources types
US9558042B2 (en) 2004-03-13 2017-01-31 Iii Holdings 12, Llc System and method providing object messages in a compute environment
US20060031506A1 (en) * 2004-04-30 2006-02-09 Sun Microsystems, Inc. System and method for evaluating policies for network load balancing
US7614055B2 (en) * 2004-06-14 2009-11-03 Alcatel-Lucent Usa Inc. Selecting a processor to run an executable of a distributed software application upon startup of the distributed software application
US20070266388A1 (en) * 2004-06-18 2007-11-15 Cluster Resources, Inc. System and method for providing advanced reservations in a compute environment
US7689998B1 (en) * 2004-07-13 2010-03-30 Microsoft Corporation Systems and methods that manage processing resources
US7502824B2 (en) * 2004-08-12 2009-03-10 Oracle International Corporation Database shutdown with session migration
US8176490B1 (en) 2004-08-20 2012-05-08 Adaptive Computing Enterprises, Inc. System and method of interfacing a workload manager and scheduler with an identity manager
US20060070060A1 (en) * 2004-09-28 2006-03-30 International Business Machines Corporation Coordinating service performance and application placement management
US8271980B2 (en) 2004-11-08 2012-09-18 Adaptive Computing Enterprises, Inc. System and method of providing system jobs within a compute environment
JP4707376B2 (ja) * 2004-11-29 2011-06-22 富士通株式会社 情報処理方法及びプログラム
JP5300266B2 (ja) * 2004-12-03 2013-09-25 ナショナル ユニヴァーシティー オブ シンガポール ネットワークにおけるクエリマッチング
US7734785B2 (en) * 2004-12-09 2010-06-08 International Business Machines Corporation On demand message based financial network integration middleware
US9489424B2 (en) * 2004-12-20 2016-11-08 Oracle International Corporation Cursor pre-fetching
US9176772B2 (en) 2005-02-11 2015-11-03 Oracle International Corporation Suspending and resuming of sessions
US8631130B2 (en) 2005-03-16 2014-01-14 Adaptive Computing Enterprises, Inc. Reserving resources in an on-demand compute environment from a local compute environment
US8863143B2 (en) 2006-03-16 2014-10-14 Adaptive Computing Enterprises, Inc. System and method for managing a hybrid compute environment
US9231886B2 (en) 2005-03-16 2016-01-05 Adaptive Computing Enterprises, Inc. Simple integration of an on-demand compute environment
CA2603577A1 (en) 2005-04-07 2006-10-12 Cluster Resources, Inc. On-demand access to compute resources
US8015564B1 (en) 2005-04-27 2011-09-06 Hewlett-Packard Development Company, L.P. Method of dispatching tasks in multi-processor computing environment with dispatching rules and monitoring of system status
US11733958B2 (en) 2005-05-05 2023-08-22 Iii Holdings 1, Llc Wireless mesh-enabled system, host device, and method for use therewith
US8019883B1 (en) 2005-05-05 2011-09-13 Digital Display Innovations, Llc WiFi peripheral mode display system
US7870265B2 (en) * 2005-06-30 2011-01-11 Oracle International Corporation System and method for managing communications sessions in a network
US8281313B1 (en) 2005-09-29 2012-10-02 Hewlett-Packard Development Company, L.P. Scheduling computer processing jobs that have stages and precedence constraints among the stages
JP4777994B2 (ja) * 2005-09-29 2011-09-21 富士通株式会社 マルチコアプロセッサ
CN101346634B (zh) * 2005-11-04 2012-10-24 甲骨文国际公司 用于通信网络中的网守的系统和方法
JP4616159B2 (ja) * 2005-11-30 2011-01-19 富士通株式会社 クラスタシステム、ロードバランサ、ノード振替方法およびノード振替プログラム
US7917656B2 (en) * 2005-12-29 2011-03-29 Sap Ag Statistics monitoring for messaging service
US8938515B2 (en) * 2005-12-29 2015-01-20 Sap Se Master queue for messaging service
CN100346307C (zh) * 2006-01-17 2007-10-31 浙江大学 Java操作系统中实时任务调度的实现方法
US8090082B2 (en) 2006-01-23 2012-01-03 Icall, Inc. System, method and computer program product for extracting user profiles and habits based on speech recognition and calling history for telephone system advertising
GB2451371B (en) 2006-04-17 2011-02-23 Vovision Llc Method and systems for correcting transcribed audio files
US7933205B1 (en) 2006-05-01 2011-04-26 At&T Mobility Ii Llc Generalized interconnection apparatus for delivering services based on real time performance requirements
US8923853B1 (en) 2006-05-04 2014-12-30 At&T Mobility Ii Llc Dynamic provisioning system for policy-based traffic navigation for roaming traffic
CN100420241C (zh) * 2006-05-08 2008-09-17 国家数字交换系统工程技术研究中心 实现信息交换的系统及方法和调度算法
US8001250B2 (en) * 2006-05-16 2011-08-16 Oracle International Corporation SIP and HTTP convergence in network computing environments
US8171466B2 (en) 2006-05-16 2012-05-01 Oracle International Corporation Hitless application upgrade for SIP server architecture
US8112525B2 (en) * 2006-05-16 2012-02-07 Oracle International Corporation Engine near cache for reducing latency in a telecommunications environment
US8219697B2 (en) 2006-05-17 2012-07-10 Oracle International Corporation Diameter protocol and SH interface support for SIP server architecture
US8903968B2 (en) * 2006-08-29 2014-12-02 International Business Machines Corporation Distributed computing environment
GB0619644D0 (en) * 2006-10-05 2006-11-15 Ibm Data processing system and method of handling requests
US9027025B2 (en) * 2007-04-17 2015-05-05 Oracle International Corporation Real-time database exception monitoring tool using instance eviction data
US8326669B2 (en) * 2007-04-19 2012-12-04 International Business Machines Corporation System and method for selecting and scheduling corrective actions for automated storage management
US8065429B2 (en) 2007-06-28 2011-11-22 Nokia Corporation System, apparatus and method for associating an anticipated success indication with data delivery
US8041773B2 (en) 2007-09-24 2011-10-18 The Research Foundation Of State University Of New York Automatic clustering for self-organizing grids
US20090144404A1 (en) * 2007-12-04 2009-06-04 Microsoft Corporation Load management in a distributed system
US20090150536A1 (en) * 2007-12-05 2009-06-11 Microsoft Corporation Application layer congestion control
US9497583B2 (en) 2007-12-12 2016-11-15 Iii Holdings 2, Llc System and method for generating a recommendation on a mobile device
US7895353B2 (en) * 2008-02-29 2011-02-22 Oracle International Corporation System and method for providing throttling, prioritization and traffic shaping during request processing via a budget service
US9961374B2 (en) * 2008-03-07 2018-05-01 Iii Holdings 1, Llc Pause and replay of media content through bookmarks on a server device
JP5291366B2 (ja) * 2008-03-18 2013-09-18 株式会社野村総合研究所 流量制御装置
GB0815362D0 (en) 2008-08-22 2008-10-01 Queen Mary & Westfield College Music collection navigation
US8180823B2 (en) * 2008-08-27 2012-05-15 International Business Machines Corporation Method of routing messages to multiple consumers
US8638701B2 (en) 2008-09-26 2014-01-28 Nxp, B.V. Methods and apparatus for power saving in personal area networks
US8051136B2 (en) * 2008-10-13 2011-11-01 International Business Machines Corporation Optimizing a presence enabled managed service
CN101446910B (zh) * 2008-12-08 2011-06-22 哈尔滨工程大学 基于smp的高级最早期限优先算法任务调度方法
US9128895B2 (en) * 2009-02-19 2015-09-08 Oracle International Corporation Intelligent flood control management
US20100218191A1 (en) * 2009-02-24 2010-08-26 Kannan Shivkumar Apparatus and Method for Processing Management Requests
US9424094B2 (en) * 2009-06-01 2016-08-23 International Business Machines Corporation Server consolidation using virtual machine resource tradeoffs
US8233919B2 (en) 2009-08-09 2012-07-31 Hntb Holdings Ltd. Intelligently providing user-specific transportation-related information
EP2293524A1 (en) 2009-09-07 2011-03-09 Nxp B.V. Set-up of media stream transmission and server and client for media stream transmission
US11720290B2 (en) 2009-10-30 2023-08-08 Iii Holdings 2, Llc Memcached server functionality in a cluster of data processing nodes
US10877695B2 (en) 2009-10-30 2020-12-29 Iii Holdings 2, Llc Memcached server functionality in a cluster of data processing nodes
US8706928B2 (en) * 2009-11-26 2014-04-22 Freescale Semiconductor, Inc. Integrated circuit and method for reducing violations of a timing constraint
US8276004B2 (en) * 2009-12-22 2012-09-25 Intel Corporation Systems and methods for energy efficient load balancing at server clusters
CN102118261B (zh) 2009-12-30 2014-11-26 上海中兴软件有限责任公司 一种数据采集的方法、数据采集装置及网管设备
US9165086B2 (en) 2010-01-20 2015-10-20 Oracle International Corporation Hybrid binary XML storage model for efficient XML processing
US8972551B1 (en) * 2010-04-27 2015-03-03 Amazon Technologies, Inc. Prioritizing service requests
JP5585195B2 (ja) * 2010-05-12 2014-09-10 日本電気株式会社 トランザクション処理装置、トランザクション処理方法およびトランザクション処理プログラム
GB201008819D0 (en) * 2010-05-26 2010-07-14 Zeus Technology Ltd Apparatus for routing requests
US8799411B2 (en) 2010-05-28 2014-08-05 Arvato Digital Services Canada, Inc. Method and apparatus for providing enhanced streaming content delivery with multi-archive support using secure download manager and content-indifferent decoding
US8458530B2 (en) 2010-09-21 2013-06-04 Oracle International Corporation Continuous system health indicator for managing computer system alerts
US8755283B2 (en) 2010-12-17 2014-06-17 Microsoft Corporation Synchronizing state among load balancer components
US8612550B2 (en) 2011-02-07 2013-12-17 Microsoft Corporation Proxy-based cache content distribution and affinity
US8380704B1 (en) 2011-05-04 2013-02-19 Google Inc. Coordinating different search queries using a translated query cursor
CN102508716B (zh) * 2011-09-29 2015-04-15 用友软件股份有限公司 任务控制装置和任务控制方法
US8826284B1 (en) * 2011-10-31 2014-09-02 Google Inc. Scalable task scheduling
US9043371B1 (en) 2011-11-04 2015-05-26 Google Inc. Storing information in a trusted environment for use in processing data triggers in an untrusted environment
US9104486B2 (en) * 2011-11-08 2015-08-11 Mckesson Financial Holdings Apparatuses, systems, and methods for distributed workload serialization
US9626273B2 (en) * 2011-11-09 2017-04-18 Nec Corporation Analysis system including analysis engines executing predetermined analysis and analysis executing part controlling operation of analysis engines and causing analysis engines to execute analysis
US9064013B1 (en) 2011-11-30 2015-06-23 Google Inc. Application of resource limits to request processing
US9235607B1 (en) 2012-03-29 2016-01-12 Google Inc. Specifying a predetermined degree of inconsistency for test data
US8621074B2 (en) 2012-04-27 2013-12-31 Xerox Business Services, Llc Intelligent work load manager
US8805990B2 (en) 2012-07-12 2014-08-12 Microsoft Corporation Load balancing for single-address tenants
AU2013296619B2 (en) * 2012-07-30 2016-07-28 The Ohio State University Antibacterial protein kinase inhibitors
US9246998B2 (en) 2012-10-16 2016-01-26 Microsoft Technology Licensing, Llc Load balancer bypass
US11132277B2 (en) 2012-12-28 2021-09-28 Iii Holdings 2, Llc System and method for continuous low-overhead monitoring of distributed applications running on a cluster of data processing nodes
US9590885B1 (en) 2013-03-13 2017-03-07 Sprint Communications Company L.P. System and method of calculating and reporting of messages expiring from a queue
US9432445B1 (en) * 2013-05-17 2016-08-30 Sprint Communications Company L.P. System and method of maintaining an enqueue rate of data messages into a set of queues
TWI533211B (zh) * 2013-11-14 2016-05-11 財團法人資訊工業策進會 用於任務排程之電腦系統，方法及電腦可讀取記錄媒體
WO2015139048A1 (en) * 2014-03-14 2015-09-17 Concurrent, Inc. Cluster (sub) graph isomorphism logical data flow mapping rules
US9367384B2 (en) 2014-06-12 2016-06-14 International Business Machines Corporation Admission control based on the end-to-end availability
US20160255013A1 (en) * 2015-02-27 2016-09-01 Ixia Dynamic Resource Management For Load Balancing In Network Packet Communication Systems
US10659366B1 (en) * 2015-11-04 2020-05-19 Amazon Technologies, Inc. Load balancer metadata forwarding on secure connections
US20180062944A1 (en) * 2016-09-01 2018-03-01 Cisco Technology, Inc. Api rate limiting for cloud native application
US10474653B2 (en) 2016-09-30 2019-11-12 Oracle International Corporation Flexible in-memory column store placement
CN108521856A (zh) * 2017-01-22 2018-09-11 华为技术有限公司 内容分发网络中的调度方法和设备
US12007941B2 (en) 2017-09-29 2024-06-11 Oracle International Corporation Session state tracking
US10574561B2 (en) 2017-10-04 2020-02-25 Cisco Technology, Inc. Centralized error telemetry using segment routing header tunneling
JP6955171B2 (ja) * 2018-06-28 2021-10-27 日本電信電話株式会社 通信制御装置及び通信制御方法
US10887380B2 (en) 2019-04-01 2021-01-05 Google Llc Multi-cluster ingress
CN110351335B (zh) * 2019-06-06 2021-11-16 国网浙江省电力有限公司衢州供电公司 一种云计算用通信效率与服务平衡方法
US11936739B2 (en) 2019-09-12 2024-03-19 Oracle International Corporation Automated reset of session state

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5012409A (en) * 1988-03-10 1991-04-30 Fletcher Mitchell S Operating system for a multi-tasking operating environment
US5640563A (en) * 1992-01-31 1997-06-17 International Business Machines Corporation Multi-media computer operating system and method
US5437032A (en) * 1993-11-04 1995-07-25 International Business Machines Corporation Task scheduler for a miltiprocessor system
US5938732A (en) * 1996-12-09 1999-08-17 Sun Microsystems, Inc. Load balancing and failover of network services
US6295553B1 (en) * 1998-12-22 2001-09-25 Unisys Corporation Method and apparatus for prioritizing delivery of data transfer requests
US6389448B1 (en) * 1999-12-06 2002-05-14 Warp Solutions, Inc. System and method for load balancing
JP4294879B2 (ja) * 2001-02-05 2009-07-15 株式会社日立製作所 サービスレベル制御機構を有するトランザクション処理システム及びそのためのプログラム
US7161901B2 (en) * 2001-05-07 2007-01-09 Vitesse Semiconductor Corporation Automatic load balancing in switch fabrics

Also Published As

Publication number Publication date
CN100343810C (zh) 2007-10-17
US7243351B2 (en) 2007-07-10
JP2004199678A (ja) 2004-07-15
US20040117794A1 (en) 2004-06-17
CN1508682A (zh) 2004-06-30

Similar Documents

Publication Publication Date Title
JP3818655B2 (ja) タスク・スケジューリングの方法、システム、およびプログラム製品
US7388839B2 (en) Methods, apparatus and computer programs for managing performance and resource utilization within cluster-based systems
US8484348B2 (en) Method and apparatus for facilitating fulfillment of web-service requests on a communication network
CN101167054B (zh) 用于在多个数据中心之间选择性卸载工作负荷的方法和装置
JP4294879B2 (ja) サービスレベル制御機構を有するトランザクション処理システム及びそのためのプログラム
EP1412857B1 (en) Managing server resources for hosted applications
JP3989443B2 (ja) ウェブ・ファームを制御する方法およびウェブ・ファーム
US5440741A (en) Software overload control method
US20040111506A1 (en) System and method for managing web utility services
US20220318071A1 (en) Load balancing method and related device
US11847503B2 (en) Execution of functions by clusters of computing nodes
US7925785B2 (en) On-demand capacity management
US7113986B2 (en) System and method for modeling information system capacity and accepting sessions in an information system
Patel et al. Survey of load balancing techniques for grid
JPH11259443A (ja) クライアント要求をスケジュ―ルしディスパッチする装置及び方法
US20020019873A1 (en) System and method for modeling and provisioning information system capacity
US20050060497A1 (en) Selectively accepting cache content
CN111401752A (zh) 一种飞轮储能调频共享处理方法、装置、系统及电子设备
CN118939414A (zh) 负载均衡的优化方法、装置、电子设备及可读存储介质
Dornala An Ensemble Load Balancing Algorithm to Process the Multiple Transactions Over Banking
US6912586B1 (en) Apparatus for journaling during software deployment and method therefor
US20050060496A1 (en) Selectively caching cache-miss content
WO2025015094A1 (en) Dynamic task allocation and datastore scaling
US12242898B2 (en) Systems, methods and computer program products for job management
Acharya et al. Enhanced dynamic load balancing algorithm for resource provisioning in cloud

Legal Events

Date Code Title Description
A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20051024

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20051115

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A821

Effective date: 20060123

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20060123

RD12 Notification of acceptance of power of sub attorney

Free format text: JAPANESE INTERMEDIATE CODE: A7432

Effective date: 20060123

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A821

Effective date: 20060123

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20060608

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A821

Effective date: 20060608

RD14 Notification of resignation of power of sub attorney

Free format text: JAPANESE INTERMEDIATE CODE: A7434

Effective date: 20060608

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20060612

R150 Certificate of patent or registration of utility model

Free format text: JAPANESE INTERMEDIATE CODE: R150

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20100623

Year of fee payment: 4

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20110623

Year of fee payment: 5

LAPS Cancellation because of no payment of annual fees