(57)【要約】【課題】ウェブ・ファームを制御する方法および装置を提供すること。【解決手段】開示されるのは、複数のウェブサイトおよびサーバを有するウェブ・ファームを制御する方法であって、前記ウェブサイトによって受信される顧客要求を複数のカテゴリに分類することであって、前記カテゴリが、共用可能顧客要求および共用不能顧客要求を含む、分類すること、前記サーバのいずれもが前記ウェブサイトの異なる１つから受け取られる共用可能顧客要求を処理できるように、前記共用可能な顧客要求を経路指定すること、前記ウェブサイトの特定の１つからの前記共用不能顧客要求を、前記特定のウェブサイトが割り当てられた特定のサーバだけに経路指定することを含む方法である。
2005516293.tif 000002
【特許請求の範囲】
【請求項１】
複数のウェブサイトおよびサーバを有するウェブ・ファームを制御する方法であって、
前記ウェブサイトによって受信される顧客要求を、共用可能顧客要求および共用不能顧客要求を含む複数のカテゴリに分類するステップ、
前記サーバのいずれもが前記ウェブサイトの異なる１つから受け取られる共用可能顧客要求を処理できるように、前記共用可能な顧客要求を経路指定するステップ、および
前記ウェブサイトの特定の１つからの前記共用不能顧客要求を、前記特定のウェブサイトが割り当てられた特定のサーバだけに経路指定するステップ
を含む方法。
【請求項２】
ゴール手順をさらに含み、前記ゴール手順が、前記ウェブサイトの前記サーバへの前記割当および現在の顧客要求負荷を与えられて、任意の所与の瞬間の平均顧客応答時間を最小にするために、前記顧客要求のそれぞれについて、前記顧客要求が割り当てられる前記サーバの間から最適なサーバを決定するステップを含む、請求項１に記載の方法。
【請求項３】
前記ゴール手順が、制約
【数１】
2005516293.tif 000129
の下で関数
【数２】
2005516293.tif 000130
を最小にすることによって行われ、ここで、Ｍは、ウェブサイトの数であり、Ｎは、サーバの数であり、Ｒｊは、サーバｊでの顧客到着レートの関数としての期待される応答時間であり、ｘｉ、ｊは、サーバｊによって処理することができるウェブサイトｉの共用可能要求の仮定の数を表す決定変数であり、ｙｉ、ｊは、サーバｊによって処理することができるウェブサイトｉの共用不能要求の仮定の数を表す決定変数であり、Ｌｊは、サーバｊの最大許容可能負荷であり、ｃｉは、ウェブサイトｉからの共用可能顧客要求の現在の数であり、ｄｉは、ウェブサイトｉからの共用不能な要求の現在の数であり、ａｉ、ｊは、ウェブサイトｉからの共用可能要求をサーバｊに経路指定できる場合を示すインデックスであり、ｂｉ、ｊは、ウェブサイトｉからの共用不能要求をサーバｊに経路指定できる場合を示すインデックスである、請求項２に記載の方法。
【請求項４】
有向グラフを作成し、維持するステップであって、前記有向グラフが、ダミー・ノードおよび複数のサーバ・ノードを含み、各前記サーバ・ノードが、前記サーバの１つに対応する、作成し、維持するステップ、
前記サーバ・ノードのうちで式
【数３】
2005516293.tif 000131
が最小であるサーバ・ノードを勝利ノードに指定するステップ、および、
前記ダミー・ノードから前記勝利ノードへの最短有向パスを選択するステップ
をさらに含む、請求項３に記載の方法。
【請求項５】
静的手順をさらに含み、前記静的手順が、共用不能顧客要求を処理するために前記ウェブサイトの特定の１つを特定の前記サーバに割り当てるステップを含む、請求項１ないし４のいずれかに記載の方法。
【請求項６】
前記静的手順が、各前記ウェブサイトの共用可能顧客要求および共用不能顧客要求の予測された需要に基づいて前記ウェブサイトを特定のサーバに割り当てる、請求項５に記載の方法。
【請求項７】
動的手順をさらに含み、前記動的手順が、
次の顧客要求を検査するステップ、
前記次の顧客要求を現在処理するのにどのサーバが最適サーバであるかを判定するために前記ゴール手順を呼び出すステップ、および、
前記次の顧客要求を前記最適サーバにディスパッチするステップ
を含む、請求項２ないし４のいずれか一項に記載の方法。
【請求項８】
前記顧客要求をキューに受信するステップ
をさらに含み、前記動的手順が、さらに、
前記キュー内の前記顧客要求を監視するステップ、
前記サーバによって現在処理されつつある顧客要求を監視するステップ、
各ｊ番目のサーバについて、
【数４】
2005516293.tif 000132
をセットするステップによって、関数
【数５】
2005516293.tif 000133
を定義するステップ、
各ｊ番目のサーバについて、
【数６】
2005516293.tif 000134
をセットするステップによって、改訂された許容可能負荷限度
【数７】
2005516293.tif 000135
を定義するステップ、および、
制約
【数８】
2005516293.tif 000136
の下で関数
【数９】
2005516293.tif 000137
を最小にするために前記
【数１０】
2005516293.tif 000138
関数および改訂された許容可能負荷限度
【数１１】
2005516293.tif 000139
を使用するために前記ゴール手順を呼び出すステップ
を含み、
【数１２】
2005516293.tif 000140
が、サーバｊによって処理できるウェブサイトｉに関する前記キュー内の共用可能要求の仮定の数を表す決定変数であり、
【数１３】
2005516293.tif 000141
が、サーバｊによって処理できるウェブサイトｉに関する共用不能要求の仮定の数を表す決定変数であり、
【数１４】
2005516293.tif 000142
が、ウェブサイトｉからの前記キュー内の共用可能顧客要求の現在の数であり、
【数１５】
2005516293.tif 000143
が、ウェブサイトｉからの前記キュー内の共用不能要求の現在の数であり、
【数１６】
2005516293.tif 000144
が、サーバの１つで現在処理されつつある、ウェブサイトｉからの共用可能顧客要求の現在の数であり、
【数１７】
2005516293.tif 000145
が、サーバの１つで現在処理されつつある、ウェブサイトｉからの共用不能要求の現在の数である
請求項７に記載の方法。
【請求項９】
請求項１ないし８のいずれかに記載の方法の各ステップをコンピュータに実行させるためのプログラム。
【請求項１０】
複数のウェブサイトおよびサーバを有するウェブ・ファームであって、さらに、
顧客から顧客要求を受信する手段と、
応答を作るために前記顧客要求を処理する手段と、
前記応答を前記顧客に送信する手段と、
前記顧客要求を共用可能顧客要求および共用不能顧客要求に分類する手段と、
前記サーバのいずれかが前記ウェブサイトの異なる１つから受け取られる共用可能顧客要求を処理できるように、前記共用可能顧客要求を経路指定する手段と、
前記ウェブサイトの特定の１つからの前記共用不能顧客要求を、前記特定のウェブサイトに割り当てられた特定のサーバだけに経路指定する手段と
を含むウェブ・ファーム。
【請求項１１】
ゴール手順、静的手順、および動的手順を実行する手段を含むネットワーク・ディスパッチャをさらに含み、
前記ゴール手順が、前記ウェブサイトの前記サーバへの前記割当および現在の顧客要求負荷を与えられて、任意の所与の瞬間の平均顧客応答時間を最小にするために、前記顧客要求のそれぞれについて、各前記顧客要求が割り当てられる前記サーバの間から最適なサーバを決定する手段を含み、前記共用可能顧客要求を、いずれかの前記サーバに割り当てることができ、前記共用不能顧客要求を、前記共用不能顧客要求が発した前記ウェブサイトに依存する特定のサーバに割り当てることだけができ、
前記静的手順が、特定の前記ウェブサイトを特定の前記サーバに割り当てる手段を含み、
前記動的手順が、
次の顧客要求を検査する手段、
前記次の顧客要求を現在処理するのにどのサーバが最適サーバであるかを判定するために前記ゴール手順を呼び出す手段、および、
前記次の顧客要求を前記最適サーバにディスパッチする手段
を含む
請求項１０に記載のウェブ・ファーム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ウェブ・ファーム（ｗｅｂ  ｆａｒｍ）の負荷の平衡化に関する。
【背景技術】
【０００２】
ウェブ・ファームまたはウェブ・コンプレックスは、非常に普及しつつある。ウェブ・ファームの背後の鍵になる概念は、複数の異なるウェブサイトが、共用リソースを共用するという概念である。具体的に言うと、ウェブ・ファームでは、通常は、共通のフロントエンド・ディスパッチャが共用されて、負荷制御が実行され、顧客要求が分配される。ウェブ・ファームでは、複数のウェブ・サーバも共用され、顧客に要求を返すのにバックエンド帯域幅が共用される。ハードウェアおよびソフトウェアは、通常は、単一のサービス・プロバイダまたはコンテンツ・ホストによって所有され、運営され、維持される。現在このサービスを提供するか提供を計画している会社の例に、ＡＴ＆Ｔ、Ｅｘｏｄｕｓ、Ｉｎｔｅｌ、ＩＢＭ、Ｑｗｅｓｔ、Ｖｅｒｉｏ、およびＷｏｒｌｄｃｏｍが含まれる。
【０００３】
ウェブ・ファームの主要な性能の課題は、サーバで負荷を効率的に平衡化して、システムで達成される平均応答時間を最小にすることである。サーバの過剰使用は、顧客要求の課題な遅延を引き起こす可能性がある。その一方で、サーバの過小使用は、不経済である。平均応答時間を最小にすることには、ウェブ・ファームが達成することができるスループットが最大になるという二重の効果がある。これは、フロントエンド・ディスパッチャの負荷制御手順をより寛大にすることができ、拒否される要求が減ることを意味する。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ウェブ・ファームの主な動機の１つは、共用リソースのゆえに生じる効率である。各ウェブサイトが、１つまたは複数のサーバの組に割り当てられる。しかし、従来技術では、ウェブサイト割当が、サーバの間で区分されることが仮定されている。すなわち、複数のウェブサイトからのトラフィックを処理するサーバはない。
【０００５】
複数のサーバを含む組を作成することの裏にある論拠は、実現可能性である。さまざまなサイトの間での顧客の分布は、通常は非常に不均一である。一部のサイトが他のサイトより非常に人気がある可能性があり、話題のウェブサイトの人気は、一般に、単一のサーバを割り当てるとそのサーバに負荷をかけすぎることになるのに十分なものとなる。したがって、許容できる性能を達成するために、一部のサイトに複数のサーバを割り当てることが必要になる。
【０００６】
区分された事例について負荷平衡化アルゴリズムを実施することが既知であるが、サーバのそのような区分は、柔軟性の低下につながり、したがって、より最適でなく平衡化されたウェブサイト負荷平衡化につながる。
【特許文献１】米国特許第６３７４２９７号
【非特許文献１】タンタウイ（Tantawi）他、「コンピュータ・システムでの複数クラス・リソースの最適割振り（Optimalallocation of multiple class resources in computer systems）、ＡＣＭ  Ｓｉｇｍｅｔｒｉｃｓ会議（ACMSigmetrics Conference）、１９８８年５月、253〜260頁
【非特許文献２】ガーファンケル（R. Garfinkel）他、「整数プログラミング（IntegerProgramming）」、ジョン・ワイリー・アンド・サンズ（John Wiley and Sons）、米国ニューヨーク州ニューヨーク、１９７２年
【課題を解決するための手段】
【０００７】
開示されるのは、複数のウェブサイトおよびサーバを有するウェブ・ファームを制御する方法であって、前記ウェブサイトによって受信される顧客要求を複数のカテゴリに分類することであって、前記カテゴリが、共用可能顧客要求および共用不能顧客要求を含む、分類すること、前記サーバのいずれもが前記ウェブサイトの異なる１つから受け取られる共用可能顧客要求を処理できるように、前記共用可能な顧客要求を経路指定すること、前記ウェブサイトの特定の１つからの前記共用不能顧客要求を、前記特定のウェブサイトが割り当てられた特定のサーバだけに経路指定することを含む方法である。
【０００８】
本発明のもう１つの態様に、ゴール手順（Ｇｏａｌ  ｐｒｏｃｅｄｕｒｅ）が含まれ、前記ゴール手順は、前記ウェブサイトの前記サーバへの前記割当および現在の顧客要求負荷を与えられて、任意の所与の瞬間の平均顧客応答時間を最小にするために、前記顧客要求のそれぞれについて、前記顧客要求が割り当てられる前記サーバの間から最適なサーバを決定することを含む。
【０００９】
本発明のもう１つの態様では、前記ゴール手順が、制約
【００１０】
【数１】
2005516293.tif 000003
の下で関数
【００１１】
【数２】
2005516293.tif 000004
を最小にすることによって行われ、ここで、Ｍは、ウェブサイトの数であり、Ｎは、サーバの数であり、Ｒｊは、サーバｊでの顧客到着レートの関数としての期待される応答時間であり、ｘｉ、ｊは、サーバｊによって処理することができるウェブサイトｉの共用可能要求の仮定の数を表す決定変数であり、ｙｉ、ｊは、サーバｊによって処理することができるウェブサイトｉの共用不能要求の仮定の数を表す決定変数であり、Ｌｊは、サーバｊの最大許容可能負荷であり、ｃｉは、ウェブサイトｉからの共用可能顧客要求の現在の数であり、ｄｉは、ウェブサイトｉからの共用不能な要求の現在の数であり、ａｉ、ｊは、ウェブサイトｉからの共用可能要求をサーバｊに経路指定できる場合を示すインデックスであり、ｂｉ、ｊは、ウェブサイトｉからの共用不能要求をサーバｊに経路指定できる場合を示すインデックスである。
【００１２】
本発明のもう１つの態様は、有向グラフを作成し、維持することであって、前記有向グラフが、ダミー・ノードおよび複数のサーバ・ノードを含み、各前記サーバ・ノードが、前記サーバの１つに対応する、作成し、維持すること、前記サーバ・ノードのうちで式
【００１３】
【数３】
2005516293.tif 000005
が最小であるサーバ・ノードを勝利ノード（ｗｉｎｎｉｎｇ  ｎｏｄｅ）に指定すること、前記ダミー・ノードから前記勝利ノードへの最短有向パスを選択することを含む。
【００１４】
本発明のもう１つの態様は、静的手順（Ｓｔａｔｉｃ  ｐｒｏｃｅｄｕｒｅ）を含み、前記静的手順が、特定の前記ウェブサイトを特定の前記サーバに割り当てることを含む。
【００１５】
本発明のもう１つの態様では、前記静的手順が、各前記ウェブサイトの共用可能顧客要求および共用不能顧客要求の予測された需要に基づいて前記ウェブサイトを特定のサーバに割り当てる。
【００１６】
本発明のもう１つの態様は、動的手順（Ｄｙｎａｍｉｃ  ｐｒｏｃｅｄｕｒｅ）を含み、前記動的手順が、次の顧客要求を検査すること、前記次の顧客要求を現在処理するのにどのサーバが最適サーバであるかを判定するために前記ゴール手順を呼び出すこと、前記次の顧客要求を前記最適サーバにディスパッチすることを含む。
【００１７】
本発明のもう１つの態様は、前記顧客要求をキューに受信することをさらに含み、前記動的手順が、さらに、前記キュー内の前記顧客要求を監視すること、前記サーバによって現在処理されつつある顧客要求を監視すること、各ｊ番目のサーバについて、
【００１８】
【数４】
2005516293.tif 000006
をセットすることによって、関数
【００１９】
【数５】
2005516293.tif 000007
を定義すること、各ｊ番目のサーバについて、
【００２０】
【数６】
2005516293.tif 000008
をセットすることによって、改訂された許容可能負荷限度
【００２１】
【数７】
2005516293.tif 000009
を定義すること、制約
【００２２】
【数８】
2005516293.tif 000010
および、ｂｉ、ｊ＝０の場合に
【００２３】
【数９】
2005516293.tif 000011
の下で関数
【００２４】
【数１０】
2005516293.tif 000012
を最小にするために前記
【００２５】
【数１１】
2005516293.tif 000013
関数および改訂された許容可能負荷限度
【００２６】
【数１２】
2005516293.tif 000014
を使用するために前記ゴール手順を呼び出すことを含み、
【００２７】
【数１３】
2005516293.tif 000015
が、サーバｊによって処理できるウェブサイトｉに関する前記キュー内の共用可能要求の仮定の数を表す決定変数であり、
【００２８】
【数１４】
2005516293.tif 000016
が、サーバｊによって処理できるウェブサイトｉに関する共用不能要求の仮定の数を表す決定変数であり、
【００２９】
【数１５】
2005516293.tif 000017
が、ウェブサイトｉからの前記キュー内の共用可能顧客要求の現在の数であり、
【００３０】
【数１６】
2005516293.tif 000018
が、ウェブサイトｉからの前記キュー内の共用不能要求の現在の数であり、
【００３１】
【数１７】
2005516293.tif 000019
が、サーバの１つで現在処理されつつある、ウェブサイトｉからの共用可能顧客要求の現在の数であり、
【００３２】
【数１８】
2005516293.tif 000020
が、サーバの１つで現在処理されつつある、ウェブサイトｉからの共用不能要求の現在の数である。
【００３３】
開示されるのは、機械によって可読のプログラム記憶装置であって、複数のウェブサイトおよびサーバを有するウェブ・ファームを制御する方法ステップを実行するために前記機械によって実行可能な命令のプログラムを有形に実施し、前記方法ステップは、前記ウェブサイトから受け取られる顧客要求を複数のカテゴリに分類することであって、前記カテゴリが、共用可能顧客要求および共用不能顧客要求を含む、分類すること、前記サーバのいずれもが異なる前記ウェブサイトから受け取られる共用可能顧客要求を処理できるように、前記共用可能な顧客要求を経路指定すること、特定の前記ウェブサイトからの前記共用不能顧客要求を、前記特定のウェブサイトが割り当てられた特定のサーバだけに経路指定することを含む。
【００３４】
本発明のもう１つの態様は、ゴール手順を含み、前記ゴール手順が、前記ウェブサイトの前記サーバへの前記割当および現在の顧客要求負荷を与えられて、任意の所与の瞬間の平均顧客応答時間を最小にするために、前記顧客要求のそれぞれについて、前記顧客要求が割り当てられる前記サーバの間から最適なサーバを決定することを含む。
【００３５】
この装置のもう１つの態様では、前記ゴール手順が、制約
【００３６】
【数１９】
2005516293.tif 000021
の下で関数
【００３７】
【数２０】
2005516293.tif 000022
を最小にすることによって行われ、ここで、Ｍは、ウェブサイトの数であり、Ｎは、サーバの数であり、Ｒｊは、サーバｊでの顧客到着レートの関数としての期待される応答時間であり、ｘｉ、ｊは、サーバｊによって処理することができるウェブサイトｉの共用可能要求の仮定の数を表す決定変数であり、ｙｉ、ｊは、サーバｊによって処理することができるウェブサイトｉの共用不能要求の仮定の数を表す決定変数であり、Ｌｊは、サーバｊの最大許容可能負荷であり、ｃｉは、ウェブサイトｉからの共用可能顧客要求の現在の数であり、ｄｉは、ウェブサイトｉからの共用不能な要求の現在の数であり、ａｉ、ｊは、ウェブサイトｉからの共用可能要求をサーバｊに経路指定できる場合を示すインデックスであり、ｂｉ、ｊは、ウェブサイトｉからの共用不能要求をサーバｊに経路指定できる場合を示すインデックスである。
【００３８】
この装置のもう１つの態様は、有向グラフを作成し、維持することであって、前記有向グラフが、ダミー・ノードおよび複数のサーバ・ノードを含み、各前記サーバ・ノードが、前記サーバの１つに対応する、作成し、維持すること、
前記サーバ・ノードのうちで式
【００３９】
【数２１】
2005516293.tif 000023
が最小であるサーバ・ノードを勝利ノードに指定すること、
前記ダミー・ノードから前記勝利ノードへの最短有向パスを選択すること
を含む。
【００４０】
この装置のもう１つの態様は、静的手順を含み、前記静的手順が、特定の前記ウェブサイトを特定の前記サーバに割り当てることを含む。
【００４１】
この装置のもう１つの態様では、前記静的手順が、各前記ウェブサイトからの共用可能顧客要求および共用不能顧客要求の予測された需要に基づいて前記ウェブサイトを特定のサーバに割り当てる。
【００４２】
この装置のもう１つの態様は、動的手順を含み、前記動的手順が、次の顧客要求を検査すること、前記次の顧客要求を現在処理するのにどのサーバが最適サーバであるかを判定するために前記ゴール手順を呼び出すこと、前記次の顧客要求を前記最適サーバにディスパッチすることを含む。
【００４３】
この装置のもう１つの態様は、前記顧客要求をキューに受信することを含み、前記動的手順が、さらに、前記キュー内の前記顧客要求を監視すること、前記サーバによって現在処理されつつある顧客要求を監視すること、各ｊ番目のサーバについて、
【００４４】
【数２２】
2005516293.tif 000024
をセットすることによって、関数
【００４５】
【数２３】
2005516293.tif 000025
を定義すること、各ｊ番目のサーバについて、
【００４６】
【数２４】
2005516293.tif 000026
をセットすることによって、改訂された許容可能負荷限度
【００４７】
【数２５】
2005516293.tif 000027
を定義すること、制約
【００４８】
【数２６】
2005516293.tif 000028
およびｂｉ、ｊ＝０の場合に
【００４９】
【数２７】
2005516293.tif 000029
の下で関数
【００５０】
【数２８】
2005516293.tif 000030
を最小にするために前記
【００５１】
【数２９】
2005516293.tif 000031
関数および改訂された許容可能負荷限度
【００５２】
【数３０】
2005516293.tif 000032
を使用するために前記ゴール手順を呼び出すことを含み、
【００５３】
【数３１】
2005516293.tif 000033
が、サーバｊによって処理できるウェブサイトｉに関する前記キュー内の共用可能要求の仮定の数を表す決定変数であり、
【００５４】
【数３２】
2005516293.tif 000034
が、サーバｊによって処理できるウェブサイトｉに関する共用不能要求の仮定の数を表す決定変数であり、
【００５５】
【数３３】
2005516293.tif 000035
が、ウェブサイトｉからの前記キュー内の共用可能顧客要求の現在の数であり、
【００５６】
【数３４】
2005516293.tif 000036
が、ウェブサイトｉからの前記キュー内の共用不能要求の現在の数であり、
【００５７】
【数３５】
2005516293.tif 000037
が、サーバの１つで現在処理されつつある、ウェブサイトｉからの共用可能顧客要求の現在の数であり、
【００５８】
【数３６】
2005516293.tif 000038
が、サーバの１つで現在処理されつつある、ウェブサイトｉからの共用不能要求の現在の数である。
【００５９】
開示されるのは、ウェブ・ファームであって、顧客から顧客要求を受信する手段と、応答を作るために前記顧客要求を処理する手段と、前記応答を前記顧客に送信する手段と、前記顧客要求を共用可能顧客要求および共用不能顧客要求に分類する手段と、ゴール手順、静的手順、および動的手順を実行する手段を含むネットワーク・ディスパッチャとを含み、前記ゴール手順が、前記ウェブサイトの前記サーバへの前記割当および現在の顧客要求負荷を与えられて、任意の所与の瞬間の平均顧客応答時間を最小にするために、前記顧客要求のそれぞれについて、各前記顧客要求が割り当てられる前記サーバの間から最適なサーバを決定することを含み、前記共用可能顧客要求を、いずれかの前記サーバに割り当てることができ、前記共用不能顧客要求を、前記共用不能顧客要求が発した前記ウェブサイトに依存する特定のサーバに割り当てることだけができ、前記静的手順が、特定の前記ウェブサイトを特定の前記サーバに割り当てることを含み、前記動的手順が、次の顧客要求を検査すること、前記次の顧客要求を現在処理するのにどのサーバが最適サーバであるかを判定するために前記ゴール手順を呼び出すこと、前記次の顧客要求を前記最適サーバにディスパッチすることを含む、ウェブ・ファームである。
【発明を実施するための最良の形態】
【００６０】
本発明は、複数のサイトのサーバ割り当ての間でオーバーラップを可能にすることによって、ウェブ・ファームの負荷を平衡化するという問題に対する解決策を提供し、さまざまなサイトの所有者にここちよい実用的な形でこれを行う。本発明の教示は、現在は米国特許第６３７４２９７号である、本出願の譲受人に譲渡された、１９９９年８月１６日出願の同時係属の米国特許出願第０９／３７４５３９号明細書、整理番号１２７９３（ＹＯ９９９−３０７）、「METHOD AND APPARATUS FOR LOAD BALANCING OF WEB CLUSTER FARMS」という名称で開示された負荷平衡化システムの代わりに使用することができる。
【００６１】
ウェブサイトの組のオーバーラップの裏にある論拠は、柔軟性である。ウェブ・ファームは、多数の異なるサイトから顧客要求を同時に処理できなければならず、この顧客需要は、通常はバースト性である。このバースト性は、変化するウェブサイトの人気および顧客の混合に起因して、週、日、および時間毎に見ることができる。この証拠から、分および秒などのはるかに小さい原子的時間単位でもこれが発生することが暗示される。ここでのポイントは、平均ウェブサイト・アクセス・レートが、顧客挙動の変わりやすい性質を十分に取り込んでいないことである。あるウェブサイトのトラフィックは、劇的に干満する可能性があり、あるウェブサイトが忙しい時に、別のウェブサイトがそうでない場合がある。複数のサイトを処理するサーバを、これらのサイトの間で作業負荷平衡を変更して、これらの動的トラフィックに反応するようにすることができるという望みがある。区分設計では、この反応性の機能が可能にならないことに留意されたい。
【００６２】
本発明では、サーバ・リソースが効率的にプールされ、これらのサーバの負荷を平衡化するために、フロントエンド・ディスパッチャに関するインテリジェントな方法が使用される。本発明は、各ウェブサイトが１つまたは複数のサーバの組に割り当てられると仮定するに十分に一般化可能であり、さらに、これらの組をオーバーラップできると仮定するに十分に一般化可能である。これは、所与のサーバによって、必要な場合に複数のサイトから顧客要求を処理できることを意味する。より望ましくない代替案は、さまざまなサイトの間でサーバを区分し、その結果、各サーバが正確に１つのウェブサイトから要求を処理するようにすることである。本発明は、より非効果的ではあるが、このより好ましくない特殊な事例についても動作する。
【００６３】
しかし、ウェブ・ファームの場合にオーバーラップする組は、問題がないわけではない。技術的な観点からは、適切に洗練されたサーバが適度な数のウェブサイトに対処することは無理でないが、政治的な観点からは、それほど理にかなっていない場合がある。たとえば、ｅ−ｃｏｍｍｅｒｃｅ商人は、サーバがサイトの間で論理的に区分される場合であっても、トランザクション要求を処理するサーバを他の商人と共用することに異議を申してたてる可能性がある。商人の異議は、通常は、プライバシの理由に基づく。幸い、そのような商人は、ブラウズ要求のためのサーバの共用には、それほど敏感でないことがだいたい常である。負荷平衡化手順を実用的にし、したがって実施可能にするために、この問題に有効に対処しなければならない。これは、必要な場合に各ウェブサイトの作業負荷を２つに分割することによって達成することができ、この２つの部分の一方は共用可能でなく、他方は共用可能である。これによって、パブリック要求（ブラウザによって動機づけされる）によって、他のサイトからの共用可能な要求を有するサーバを共用できるようになる。このパブリック要求は、同一のウェブサイトからのプライベート要求（トランザクションによって動機づけされる）を有するサーバも共用することができる。この非常に重要な洗練によって、本発明に、オーバーラップする割当の政治的侵害の問題をものともせずに良好に実行するのに必要な柔軟性が与えられる。
【００６４】
本発明を、２レベルの顧客トラフィックに関して本明細書で説明するが、本発明を、変化するウェブサイト対サーバ制限を有する複数レベルのトラフィックの階層に一般化可能であることを、当業者なら理解するであろう。
【００６５】
パブリック・カテゴリおよびプライベート・カテゴリが、それぞれブラウズ要求およびトランザクション要求によって動機づけされるが、これらの項が、実際には、共用の能力または不能によって定義されることに留意されたい。論理分割の概念を受け入れるｅ−ｃｏｍｍｅｒｃｅサイトについて、たとえば、トランザクション要求は、パブリック・トラフィックの一部としてカウントされ、その結果、プライベート・トラックは全くない。もう一方の極端で、ブラウザに関してもサーバの共用を可能にすることを拒否するｅ−ｃｏｍｍｅｒｃｅサイトでは、ブラウズ要求がプライベート・トラフィックの一部としてカウントされ、パブリック・トラフィックが全くない。もちろん、ブラウズ項およびトランザクション項が文字どおりの意味を全く有しない非商用サイトも存在する可能性がある。説明を簡単にするために、それでも、トラフィックを、共用可能性に応じてパブリック・カテゴリおよびプライベート・カテゴリのいずれかに分類する。
【００６６】
本発明では、オーバーラップするウェブサイト割当の可能性を利用して、ウェブ・ファーム負荷を非常に効果的に平衡化する。問題は、自然に２つの副問題に分離され、それぞれに対する解決策で、同一の基本的な最適化方法を使用して、適切なゴールを設定する。したがって、本発明には３つの主要な構成要素があり、これを、ゴール手順、静的手順、および動的手順と称する。
【００６７】
ゴール手順は、鍵になる共通の手順である。ゴール手順では、サーバへのサイトの割当および現在の顧客要求負荷を与えられて、所与の瞬間の平均顧客応答時間を最小にするように設計された最適化技法が使用される。この技法は、タンタウイ（Tantawi）他、「コンピュータ・システムでの複数クラス・リソースの最適割振り（Optimal allocation ofmultiple class resources in computer systems）、ＡＣＭ  Ｓｉｇｍｅｔｒｉｃｓ会議（ACM SigmetricsConference）、１９８８年５月、253〜260頁によって教示される、いわゆる離散クラス制約付き分離可能凸リソース割振り問題（ｄｉｓｃｒｅｔｅ  ｃｌａｓｓ  ｃｏｎｓｔｒａｉｎｅｄ  ｓｅｐａｒａｂｌｅ  ｃｏｎｖｅｘ  ｒｅｓｏｕｒｃｅ  ａｌｌｏｃａｔｉｏｎ  ｐｒｏｂｌｅｍ）を解くのに使用されるわずかに特殊な事例である。したがって、この方法では、最適負荷平衡化ゴールが決定される。具体的に言うと、出力は、各適切なサーバによって処理されるウェブサイトごとのパブリック・カテゴリおよびプライベート・カテゴリの両方の顧客要求の最適な数であり、したがって、サーバごとの全顧客要求の最適な数の合計によるものである。この問題は、比較的頻繁な基礎で解決される必要がある。幸い、この解決技法は、高速（および性質において増分的）である。この解決技法では、異機種サーバを処理することができ、これは、一部の古く低速のサーバが、不可避的に経時的に新しい高速のサーバに置換されるので、重要である。ゴール手順は、動的手順構成要素および静的手順構成要素に一体化された部分である。
【００６８】
静的手順では、パブリック要求およびプライベート要求の要件に関する、よい、うまくいけばほぼ最適な、サーバへのサイトの割当が作成される。これをうまく行うほど、ゴール手順の平均応答時間をよくすることができる。静的手順構成要素によって、進行中にゴール手順が反復的に呼び出される。この技法は、初期モードまたは増分モードのいずれかで実行することができる。初期モードは、新しいウェブ・ファームを構成する時に適切である。増分モードを用いると、割当変更の数を制限する制約が可能になり、したがって、増分モードは、高品質ウェブサイト対サーバ割当を維持するのに実用的である。ガーファンケル（R. Garfinkel）他、「整数プログラミング（Integer Programming）」、ジョン・ワイリー・アンド・サンズ（JohnWiley and Sons）、米国ニューヨーク州ニューヨーク、１９７２年で開示されたものなどの近傍エスケープ・ヒューリスティック（ｎｅｉｇｈｂｏｒｈｏｏｄ  ｅｓｃａｐｅ  ｈｅｕｒｉｓｔｉｃ）が使用される。増分モードは、おそらくは毎週１回など、周期的に実行されることを意味する。ウェブサイト対サーバ割当の再構成は、明らかにささいな作業ではない。正確な頻度は、ウェブサイト需要予測の揮発性および新しい割当を行うことのコストに依存する。
【００６９】
動的手順によって、静的手順構成要素の出力および変動するウェブサイト顧客需要に基づいて、ネットワーク・ディスパッチャ内でのリアルタイム・ウェブ・サーバ経路指定が実行される。動的手順によって、ゴール手順に基づいて、制限された副問題が解かれて、この理想化された経路指定が計算される。動的手順では、性能を改善することができるが、極端に高いオーバーヘッドをこうむる、先にディスパッチされた要求の割当の転送を行わない。
【００７０】
図１を参照すると、３つのサイト１２および９つのサーバ１３を有する仮定のウェブ・ファーム１０の例が示されている。ネットワーク・ディスパッチャ１４によって、３つのサイト１２に関する顧客要求が適切なサーバに経路指定される。第１ウェブサイト１２ａには、２つのサーバ（１および）が含まれ、第１ウェブサイト１２ａは、第２ウェブサイト１２ｂとオーバーラップし、第２ウェブサイト１２ｂは、５つのサーバ（２から５）を有し、第３ウェブサイト１２ｃとオーバーラップし、第３ウェブサイト１２ｃは、４つのサーバ（６から９）を有する。顧客要求の結果が、顧客にパイプ・バックされ、顧客は、追加要求を行うことができる。
【００７１】
図１の例示的な例があるので、本発明の３つの主要な構成要素を詳細に説明することが有用である。
【００７２】
ゴール手順（Ｇｏａｌ）構成要素
まず、いくつかの表記を定義することが有用であろう。Ｍは、ウェブサイトの数を表し、便宜上、必ずｉによってインデクシングされる。Ｎは、サーバの数を表し、ｊによってインデクシングされる。｛０、１｝のＭ×Ｎ行列Ａ＝（ａｉ、ｊ）は、ウェブサイトｉのパブリック要求のサーバｊへの割当の可能性を意味する。言い換えると、ウェブサイトｉの共用可能要求を、サーバｊによって処理できる場合にａｉ、ｊ＝１であり、そうでない場合にａｉ、ｊ＝０である。同様に、｛０、１｝のＭ×Ｎ行列Ｂ＝（ｂｉ、ｊ）は、ウェブサイトｉのプライベート要求のサーバｊへの割当の可能性を意味する。言い換えると、ウェブサイトｉの非共用可能要求をサーバｊによって処理できる場合にｂｉ、ｊ＝１であり、そうでない場合にｂｉ、ｊ＝０である。実際には、ウェブサイトｉのプライベート要求を処理するサーバｊが、そのウェブサイトのパブリック要求も処理できると仮定する。したがって、ｂｉ、ｊ＝１の場合に、ａｉ、ｊ＝１である。
【００７３】
各サーバｊに関連するのが、顧客到着レートの関数として、期待される応答時間を測定する関数Ｒｊである。この関数は、サービス時間分布に依存し、サービス時間分布は、プロセッサの速度に依存する。関数Ｒｊは、一般に、増加する凸関数である。その開示が参照によって本明細書に組み込まれる、ラベンバーグ（Lavenberg）、「コンピュータ性能モデリング・ハンドブック（Computer Performance ModelingHandbook）」、アカデミック・プレス（Academic Press）、米国ニューヨーク州ニューヨーク、１９８３年によって教示されるものなどの、古典的なキューイング技法が、到着レート・パターンおよびサービス時間分布に関するある単純化する前提の下でのＲｊの計算または推定について存在するが、一般に、この関数は、シミュレーション実験または監視を介して評価される必要がある可能性がある。この関数に基づいて、この閾値を超えるとＲｊの値が大きくなりすぎるという意味でのサーバｊでの最大許容可能負荷Ｌｊがあると仮定することができる。Ｌｊ＝∞にセットすると、この最大負荷制約は、もちろん緩慢になる。所与の瞬間に、ウェブサイトｉについて進行中のｃｉ個のパブリック要求とｄｉ個のプライベート要求があると仮定する。これを、さらに、サーバｊ上のウェブサイトｉのｃｉ、ｊ個のパブリック要求とｄｉ、ｊ個のプライベート要求に分解することができる。したがって、ｃｉ＝
【００７４】
【数３７】
2005516293.tif 000039
であり、ａｉ、ｊ＝０の時には、必ずｃｉ、ｊ＝０である（割り当てられていないサーバからウェブサイトに関するパブリック要求を処理することはできない）。同様に、ｂｉ、ｊ＝０の時には、必ずｄｉ、ｊ＝０である。
【００７５】
【数３８】
2005516293.tif 000040
が、進行中のパブリック要求の総数を表し、同様に、
【００７６】
【数３９】
2005516293.tif 000041
が、進行中のプライベート要求の総数を表すものとする。
【００７７】
サーバ負荷は、目的関数
【００７８】
【数４０】
2005516293.tif 000042
が、制約
【００７９】
【数４１】
2005516293.tif 000043
に従って最小化される時に、現在の負荷およびウェブサイト対サーバ割当について最適に平衡化されるとみなすことができる。
【００８０】
ここで、ｘｉ、ｊは、サーバｊによって処理できる、ウェブサイトｉのパブリック要求の仮定の数を表す決定変数である。同様に、ｙｉ、ｊは、サーバｊによって処理できる、ウェブサイトｉのプライベート要求の仮定の数を表す決定変数である。目的関数によって、さまざまなサーバでの期待される応答時間の合計が測定され、これは、平均応答時間とは乗算定数だけ異なる。この定数は、最適化問題の観点からは無関係である。制約（２）によって、サーバｉでの許容可能な負荷が制限される。制約（３）によって、ウェブサイトｉのパブリック要求の総数が、進行中のパブリック要求の実際の数と等しくなることが保証される。制約（４）によって、ウェブサイト対サーバ割当が、パブリック要求について守られることが保証される。制約（５）から（６）は、プライベート要求に関する対応する必要条件である。
【００８１】
【数４２】
2005516293.tif 000044
および
【００８２】
【数４３】
2005516293.tif 000045
が最適解に含まれる場合に、Ｘｊ＋Ｙｊが、サーバｊの所望の負荷を表すことに留意されたい。最終的な目標は、サーバｊのそれぞれについて、最適負荷Ｘｊ＋Ｙｊおよび実際の負荷
【００８３】
【数４４】
2005516293.tif 000046
が、必ず互いに近いことを保証することである。
【００８４】
上で説明した最適化問題は、いわゆる離散クラス制約付き分離可能凸リソース割振り問題の特殊な事例である。このクラスは、さまざまなサイトのパブリック要求およびプライベート要求に対応する。この問題が離散的であるのは、制約（２）のゆえであり、リソース割振り問題であるのは、制約（３）および（５）のゆえであり、クラス制約付きなのは、制約（４）および（６）のゆえである。分離可能という用語は、目的関数の性質を指し、凸という用語は、自明である。タンタウイによる教示のように、離散クラス制約付きリソース割振り問題は、グラフ理論最適化手順を使用して正確かつ効率的に解くことができる。
【００８５】
図３を参照すると、ゴール手順の好ましい実施形態の流れ図が示されている。可能解が存在すると仮定すると、この手順は、Ｃ＋Ｄステップで進行する。図２に示されたものなどの有向グラフが、作成され、この手順の過程全体を通じて維持される。グラフのノードは、サーバ１、…、Ｎと、「ノード０」という符号を付けられたダミー・ノードである。各ｉについて、ａｉ、０＝１かつｂｉ、０＝１とし、Ｌ０＝０とする。部分可能解｛ｘｉ、ｊ｜ｉ＝１、…、Ｍ、ｊ＝０、…、Ｎ｝∪｛ｙｉ、ｊ｜ｉ＝１、…、Ｍ、ｊ＝０、…、Ｎ｝を作成し、修正する。まず、図３のステップ１００および１０５で、各ｉについて、この部分可能解が、ｘｉ、０＝ｃｉ、ｙｉ、０＝ｄｉを有し、すべてのｊ＝１、…、Ｎについてｘｉ、ｊ＝ｙｉ、ｊ＝０を有し、したがって、すべてのリソースがダミー・ノードに存在するようにする。ステップ１１０で、有向グラフを初期化し、この有向グラフは、どのステップでも、
【００８６】
【数４５】
2005516293.tif 000047
を満たす少なくとも１つのウェブサイトｉ１、または
【００８７】
【数４６】
2005516293.tif 000048
および条件（９）を満たす少なくとも１つのウェブサイトｉ１がある場合に、ノードｊｉ∈｛０、…、Ｎ｝からノードｊ２∈｛０、…、Ｎ｝への有向弧を有する。条件（７）は、ノードｊ１およびｊ２が、ウェブサイトｉ１のパブリック要求を扱えることを示す。条件（８）は、ウェブサイトｉ１のパブリック要求が、ノードｊ１に割り当てられていることを示す。条件（９）は、ノードｊ２の負荷限界を超えずに、この要求をノードｊ２に転送できることを示す。条件（１０）、（１１）、および（９）は、プライベート要求に関する対応する必要条件である。ノード０からの有向弧が存在する場合があるが、ノード０への有向弧が存在しないことに留意されたい。したがって、受取り側のノードは、ダミー・ノードではなく、必ず実際のサーバになる。
【００８８】
この方法の全般的なステップでは、０からｊへの有効パスがあるすべてのノードｊ∈｛１、…、Ｎ｝の間で、第１階差分
【００８９】
【数４７】
2005516293.tif 000049
が最小である勝利ノードを見つける。このいわゆる第１階差分は、連続関数の導関数の離散系での類似物である。第１階差分は、Ｒｊが凸なので、各ｉについてｊで非減少関数である。そのようなノードが存在しない場合に、この手順は、可能解なしで終了する。そうでない場合には、０から勝利ノードへの最短の有効パスを選択する。このパスの有向弧（ｊ１、ｊ２）のそれぞれについて、適切なウェブサイトｉ１について、
【００９０】
【数４８】
2005516293.tif 000050
の値を１つ減分し、
【００９１】
【数４９】
2005516293.tif 000051
の値を１つ増分する（パブリック要求に関する減少および増加、またはプライベート要求に関する減少および増加のいずれかによる）。このステップをすべての有向弧に対して実行することには、１単位の負荷をダミー・ノードから除去し、１単位の負荷を勝利ノードに追加するという効果がある。中間ノードの負荷に対する正味の影響はない。したがって、ダミー・ノードは、リソースのステージング・エリアとして働き、このリソースの１つが、各ステップでサーバ・ノードに解放される。その後、有向グラフ上で記帳を実行し、これによって、一部の有向弧が修正され、あるノードが潜在的に切断され、このステップが繰り返される。（Ｃ＋Ｄ）ステップの後に、この手順は、元の離散クラス制約付きリソース割振り問題に対する最適解を得て終了する。有向グラフの弧に対する条件のゆえに、実現可能性が保証される。
【００９２】
より詳細に図３を参照すると、ゴール手順の好ましい実施形態は、ステップ１００で、すべてのサイトｉおよびサーバｊについて、０になるように変数ｘｉ、ｊおよびｙｉ、ｊをセットすることによって開始される。この手順では、進行中にこれらの変数を増減する。ステップ１０５で、ダミー・ノードを、ノード０として初期化する。すべてのリソースが、当初はこのノードに置かれ、その結果、ｘｉ、０＝ｃｉおよびｙｉ、０＝ｄｉがセットされる。ステップ１１０で、Ｎ＋１個のノードを接続する有向グラフを、下で図４に関して詳細に説明するように、式（７）から（１１）に従って初期化する。これから、ダミー・ノード０からノードｊへの有向弧があり、ａｉ、ｊ＝１またはｂｉ、ｊ＝１である少なくとも１つのウェブサイトがあると決定することができる。このグラフは、この手順の進行中に修正される。ステップ１１５で、ｋ＝１をセットする。この変数によって、リソースが割り当てられる際にリソースの単位がカウントされる。ステップ１２０で、ｍを無限大、ｊを１に初期化する。ステップ１２５で、０からノードｊへの有向パスがあるかどうかを判定する。ある場合には、ステップ１３０で、このサーバｊについて式（１２）を評価し、ｍと比較する。ｍ未満である場合には、ステップ１３５で、ｊ＊＝ｊをセットし、ｍが式（１２）の値になるようにする。これは、ｍの現在の最小値である。次に、ステップ１４０に進む。ステップ１２５でパスがない場合、またはステップ１３０で式（１２）がｍ以上に評価される場合にも、ステップ１４０に進む。ステップ１４０では、ｊを増分する。ステップ１４５で、ｊがＮ以下であるかどうかを調べる。そうである場合には、ステップ１２５に戻る。そうでない場合には、ステップ１５０に進み、ｍを無限大と比較する。ｍが無限大未満でない場合には、ダミー・ノードから他のノードへのパスが存在せず、したがって、この問題に対する可能解がない。したがって、この手順はステップ１５５で停止する。そうでない場合には、ステップ１６０に進み、最短のそのようなパスを探す。ステップ１６５で、このパスに関して記帳を実行し、ｘｉ、ｊおよびｙｉ、ｊの適切な値を増分し、減分する。それを行う際に、下で図５に関して詳細に説明するように、１単位のリソースが、ダミー・ノードから除去され、１単位のリソースが、サーバｊ＊に追加される。次に、ステップ１７０で、有向グラフに関する記帳を実行し、やはり、式（７）から（１１）が満足されることを保証する。この処理で、有向弧の一部が追加され、一部が除去される場合があるが、これについては下で図６に関して詳細に説明する。ステップ１７５で、ｋを増分する。ステップ１８０で、ｋをテストして、ｋがＣ＋Ｄ以下であるかどうかを調べる。そうでない場合には、この手順は、ステップ１８５で、最終的な解ｘｉ、ｊおよびｙｉ、ｊで完了し、そうである場合には、ステップ１２０に戻って、この手順を継続する。
【００９３】
図２を参照すると、クラス制約付きリソース割振り手順の有向グラフのパスが示されている。グラフのすべてのノードおよび有向弧が示されてはいないことに留意されたい。負荷は、ダミー「ノード０」２０から、第１階差分が最小である、ノード０に接続された勝利（サーバ）ノード２５に転送されつつある。図示の有向パスは、そのような最短パスであることが意図されている。有向弧に、１から５の番号が付けられている。この図では、あるウェブサイトに関する１つの新しい（パブリックまたはプライベートの）要求が、有向弧１を介して割り振られているが、それが割り振られる最初の（サーバ）ノード２１のアクティビティのレベルは変更されない。実際には、最初の４つのサーバ・ノード２１から２４のどれもが、異なるレベルのアクティビティを有していない。第５の、勝利サーバ・ノード２５は、ダミー・ノード２０と引き換えに、１単位のアクティビティの増加を経験する。
【００９４】
図４を参照すると、図３のステップ１１０に対応する初期化手順の流れ図が示されている。ステップ４００で、ｊ＝１に初期化し、次に、ステップ４０５で、テストして、Ｌｊが０を超えるかどうかを調べる。そうである場合には、ステップ４０１でｉを１に初期化し、ステップ４１５で、テストして、ａｊが０を超えるかどうかを調べる。そうである場合には、ステップ４２０で、テストして、ｘｉ０が０を超えるかどうかを調べる。そうである場合には、ステップ４２５で、ダミー・ノード０からｊへの有向弧を作成し、ステップ４３０に進む。ステップ４１５またはステップ４２０のいずれかで否定になる場合には、ステップ４３５に進み、テストして、ｂｊが０を超えるかどうかを調べる。そうである場合には、ステップ４４０で、テストして、ｙｉ０が０を超えるかどうかを調べる。そうである場合には、流れは、前と同様にステップ４２５に進む。ステップ４３５またはステップ４４０のいずれかで否定になる場合には、制御は、ステップ４３０に進み、ｊを増分する。ステップ４４５で、テストして、ｊがＮ以下であるかどうかを調べる。そうでない場合には、制御はステップ４０５にループバックし、そうである場合には、ステップ４５０で終了する。
【００９５】
図５を参照すると、図３のステップ１６５のパス記帳手順の流れ図が示されている。この流れ図では、最短パスが、ｋ個の有向弧を有し、ｊ０＝０からｊ１からｊ２からｊｋ＝ｊまでの符号が付けられている。ステップ５００で、ｊ＝０に初期化し、ステップ５０５で、ｉ＝１に初期化する。ステップ５１０で、ａｉｊ＝ａｉ（ｊ＋１）＝１であるかどうかを調べる。そうである場合には、ステップ５１５で、ｘｉｊが０を超えるかどうかを調べる。そうである場合には、ステップ５２０で、ｘｉｊを減分し、ｘｉ（ｊ＋１）を増分する。ステップ５１０または５１５のテストのいずれかが否定になる場合には、ステップ５２５に進み、同様に、ｂｉｊ＝ｂｉ（ｊ＋１）＝１であるかどうかを調べる。そうである場合には、ステップ５３０で、ｙｉｊが０を超えるかどうかを調べる。そうである場合には、ステップ５３５で、ｙｉｊを減分し、ｙｉ（ｊ＋１）を増分する。ステップ５２５または５３０のいずれかのテストが否定になる場合には、ステップ５４０に進み、ｉを増分し、ステップ５１０に戻る（制約によって、あるサーバｉが最終的にこのテストに合格することがわかっている）。ステップ５２０またはステップ５３５の後に、ステップ５４５に進み、ｊを増分する。ステップ５５０で、ｊがｋ未満であるかどうかを調べる。そうである場合には、ステップ５０５に戻る。そうでない場合には、ステップ５５５でこの手順を終了する。
【００９６】
図６を参照すると、図３のステップ１７０のグラフ記帳手順の流れ図が示されている。ステップ６００で開始して、ｊ１が１になるように初期化する。ステップ６０５で、ｊ２が１になるように初期化する。ステップ６１０でテストして、
【００９７】
【数５０】
2005516293.tif 000052
に関する条件（９）が真であるかどうかを調べる。そうでない場合には、６１２でこの手順を終了し、そうである場合には、ステップ６１５でｉ＝１に初期化し、ステップ６２０で、ａｊ，１＝ａｊ，２＝１であるかどうかを調べる。そうである場合には、ステップ６２５でテストして、
【００９８】
【数５１】
2005516293.tif 000053
が０を超えるかどうかを調べる。そうである場合には、ステップ６３０で、ノードｊ１からノードｊ２への有向弧を作成し、ステップ６３５に進んでｊ２を増分する。ステップ６２０またはステップ６２５のいずれかで否定になる場合には、ステップ６４０に進み、テストして、ｂｊ，１＝ｂｊ，２＝１であるかどうかを調べる。そうである場合には、ステップ６４５で、
【００９９】
【数５２】
2005516293.tif 000054
が０を超えるかどうかを調べる。そうである場合には、前と同様にステップ６３０に進む。ステップ６４０またはステップ６４５のいずれかで否定になる場合には、ステップ６３５に進む。ステップ６５０でテストして、ｊ２がＮ以下であるかどうかを調べる。そうである場合には、ステップ６５５でｊ１を増分し、ステップ６６０に進んで、テストして、ｊ１がＮ以下であるかどうかを調べる。そうでない場合には、ステップ６６５で終了する。ステップ６５０のテストが否定になる場合には、ステップ６７０に進み、ｊ１＝ｊ２であるかどうかを調べる。ｊ１＝ｊ２である場合には、ステップ６３５に戻り、そうでない場合には、ステップ６１０に戻る。ステップ６６０のテストが否定になる場合には、ステップ６７５に進み、ｊ１＝ｊ２であるかどうかを調べる。ｊ１＝ｊ２である場合には、ステップ６５５に戻り、そうでない場合には、ステップ６０５に戻る。
【０１００】
動的手順（Ｄｙｎａｍｉｃ）
図７を参照して、負荷平衡化手順の動的手順構成要素を説明する。この技法では、所与のものとして、サーバへのサイトの割当（静的手順構成要素）を前提とする。これは、行列ＡおよびＢの決定ということになる。次に、サーバでの正確なまたは近似の負荷ならびにネットワーク・ディスパッチャでの新しい顧客要求の到着を監視する。動的手順構成要素の仕事は、これらのキューイングされた要求を適切なサーバに割り当てて、これらの要求に関するネットワーク・ディスパッチャでの経路指定判断を行うことである。それを行う際に、動的手順では、可能な範囲まで、ゴール手順によって指示される最適平均応答時間およびサーバ負荷レベルの達成を試みる。実際に、動的手順では、ネットワーク・ディスパッチャにキューイングされたトラフィックについてゴール手順を呼び出して、判断を行う。経路指定判断は、正確なポリシまたは確率的ポリシを介して実施することができる。要求が、静的手順構成要素によってサーバに割り当てられたならば、それらの要求はそのサーバで満足される。言い換えると、好ましい実施形態では、ネットワーク・ディスパッチャの判断が、最終的とみなされ、サーバ自体にある要求を負荷に基づいてリダイレクトすることはできない。
【０１０１】
あるメタ表記を定義することが有用であろう。任意の所与の時に、いくつかの負荷が、ネットワーク・ディスパッチャでキューイングされ、いくつかの負荷が、既にサーバにディスパッチされている。この２タイプの負荷ならびに全体的な負荷を区別したい。ディスパッチャ内の負荷に関する変数を参照する時に、単一のドットを使用し、サーバ内の負荷に関する変数を参照する時に、２つのドットを使用する。ドットが使用されない場合に、その変数は、ディスパッチャ負荷およびサーバ負荷の組合せを指す。
【０１０２】
この方法では、サーバｊ上のウェブサイトｉに関するディスパッチされるパブリック要求の現在の個数
【０１０３】
【数５３】
2005516293.tif 000055
と、ディスパッチされるプライベート要求の現在の個数
【０１０４】
【数５４】
2005516293.tif 000056
を監視する。動的手順構成要素では、サーバでの要求の完了に直接に反応するのではなく、
【０１０５】
【数５５】
2005516293.tif 000057
および
【０１０６】
【数５６】
2005516293.tif 000058
の値を適切に減分する。このデータがすぐに使用可能でない場合には、推定することができる。その間に、新しい要求が到着し、ネットワーク・ディスパッチャ内でキューイングされる。
【０１０７】
【数５７】
2005516293.tif 000059
が、動的手順構成要素の最後の実行以降の、ウェブサイトｉに関する新しいパブリック要求の数を表すものとする。同様に、
【０１０８】
【数５８】
2005516293.tif 000060
が、動的手順構成要素の最後の実行以降の、ウェブサイトｉに関する新しいプライベート要求の数を表すものとする。合計して、
【０１０９】
【数５９】
2005516293.tif 000061
および
【０１１０】
【数６０】
2005516293.tif 000062
によって、それぞれディスパッチャにキューイングされたパブリック要求およびプライベート要求の総数を表すものとする。
【０１１１】
動的手順構成要素を、固定された時間間隔の後に、キュー内の項目の数
【０１１２】
【数６１】
2005516293.tif 000063
が固定されたバッチ・サイズ閾値に達した後に、またはおそらくはこの両方の判断基準の組合せで、覚醒し、実行するように設計することができる。
【０１１３】
ネットワーク・ディスパッチャ内にキューイングされた要求にゴール手順を適用するが、その間に、前にディスパッチされた要求には手を付けない。これを行うために、多少の記帳が必要である。具体的に言うと、サーバｊのそれぞれについて、
【０１１４】
【数６２】
2005516293.tif 000064
をセットすることによって、新しい凸増加関数
【０１１５】
【数６３】
2005516293.tif 000065
を定義する。
【０１１６】
この関数では、元の関数を単純にシフトして、サーバ内の摂動不能な負荷の量を考慮に入れる。同一の理由から、サーバｊのそれぞれについて、
【０１１７】
【数６４】
2005516293.tif 000066
をセットすることによって、改訂された許容可能負荷限界
【０１１８】
【数６５】
2005516293.tif 000067
も定義する。
【０１１９】
これらの形式を用いて、
【０１２０】
【数６６】
2005516293.tif 000068
個のキューイングされた要求をディスパッチする最適な形は、制約
【０１２１】
【数６７】
2005516293.tif 000069
の下で
【０１２２】
【数６８】
2005516293.tif 000070
を最小化するという、図７のステップ２００に対応する制限付きゴール手順構成要素問題を解くことによって決定される。最適解においても、サーバｊの総負荷
【０１２３】
【数６９】
2005516293.tif 000071
は、全体的に準最適である。しかし、これは、前に割り当てられた負荷をサーバの間で転送できないという追加の制約の最適な対象である。
【０１２４】
さらに、新しい要求がネットワーク・ディスパッチャに到着する時に必ずこの技法が覚醒され、その結果、あるウェブサイトｉ１について
【０１２５】
【数７０】
2005516293.tif 000072
または
【０１２６】
【数７１】
2005516293.tif 000073
のいずれかになる特殊な場合に、この手順が単に貪欲であることに留意されたい。言い換えると、
【０１２７】
【数７２】
2005516293.tif 000074
であり、その結果、ウェブサイトｉ１の新しいパブリック要求が割り当てられる場合に、
【０１２８】
【数７３】
2005516293.tif 000075
および
【０１２９】
【数７４】
2005516293.tif 000076
を満足し、第１階差分
【０１３０】
【数７５】
2005516293.tif 000077
が最小であるサーバｊが選択される。
【０１３１】
【数７６】
2005516293.tif 000078
であり、その結果、ウェブサイトｉ１の新しいプライベート要求が追加される場合に、
【０１３２】
【数７７】
2005516293.tif 000079
を満足し、その第１階差分が式（１２）によって与えられる負荷限度制約が最小であるサーバｊが選択される。
【０１３３】
動的手順を、図８および９に示された例によって示すことができる。ここでは、８つのサイトをホスティングする１５個のサーバの構成を検討する。パブリック・ウェブサイト・トラフィックを処理するために割り当てられた５つのサーバがある。各サーバが複数のサイトからのトラフィックを処理する能力を有するので、これらのサーバをクラスタ・サーバと呼ぶ。プライベート・ウェブサイト・トラフィックを処理するために割り当てられた１０個のサーバもある。したがって、これらを区画サーバと呼ぶ。各このようなサーバは、パブリック・トラフィックとプライベート・トラフィックの両方を処理できるが、単一のウェブサイトのトラフィックだけを処理できる。この例のウェブサイト記号用語集である図８を検討されたい。各記号は、ウェブサイトに一意の形状を有する。たとえば、ｃｉｒｃｕｌａｒｌｏｇｉｃ．ｃｏｍは、円によって表される。灰色の記号は、パブリック・トラフィックを示し、黒の記号は、プライベート・トラフィックを示す。関連するクラスタ・サーバおよび区画サーバの濃度も示される。それぞれ、割当行列ＡおよびＢの行合計
【０１３４】
【数７８】
2005516293.tif 000080
および
【０１３５】
【数７９】
2005516293.tif 000081
がある。たとえば、ｃｉｒｃｕｌａｒｌｏｇｉｃ．ｃｏｍは、３つのクラスタ・サーバおよび２つの区画サーバを割り当てられている。
【０１３６】
このすべてを、図９に詳細に示す。内側のループに、５つのクラスタ・サーバＣ１からＣ５が含まれ、外側ループに、１０個の区画サーバＰ１からＰ１０が含まれる。たとえば、ｃｉｒｃｕｌａｒｌｏｇｉｃ．ｃｏｍが、クラスタ・サーバＣ１、Ｃ２、およびＣ５に割り当てられていることに留意されたい。サーバＣ１では、このウェブサイトのパブリック・トラフィックによって、ｈｅｘｎｕｔ．ｃｏｍおよびｅｇｇｃｅｎｔｒｉｃ．ｃｏｍのパブリック・トラフィックと共にこのサーバが共用されなければならない。同様に、ｃｉｒｃｕｌａｒｌｏｇｉｃ．ｃｏｍは、区画サーバＰ１およびＰ２に割り当てられる。この２つのサーバのそれぞれが、パブリック・トラフィックおよびプライベート・トラフィックの両方を処理するが、このウェブサイトからのトラフィックだけを処理する。
【０１３７】
実際には、図９によって、より多くの情報が伝えられる。図９には、ゴール手順によって使用される種類の、わずかに修正された有向グラフが示されている。図２を想起されたい。図２には、クラス制約付きリソース割振り問題の解での、特定の瞬間のダミー・ノードからサーバ・ノードへの最短パスが示されている。対照的に、図９には、１つの例外を含めて、そのような瞬間の、すべての有向弧およびノードを示す有向グラフＨが示されている（例外は、ダミー・ノードと、そこからの有向弧が削除されていることである）。
【０１３８】
したがって、Ｈは、次のように定義される：ノードは、サーバに対応する。別個のサーバ・ノードの対ｊ１およびｊ２のそれぞれについて、条件（７）から（９）または条件（１０）、（１１）、および（９）を満足する少なくとも１つのウェブサイトｉ１が存在するならば、ｊ１からｊ２への有向弧がある。
【０１３９】
図９では、すべての有向弧が両方向で示されてはいないが、これは、それらが、関連する制約のすべてを満足できないからである。たとえば、Ｐ３からＰ４への有向弧がないが、これは、明らかに、Ｐ３に、パブリック（条件８）およびプライベート（条件１１）の両方の負荷がないからである。Ｃ３からＰ７への有向弧がないが、これは、明らかに、Ｐ７が最大容量で動作している（条件９）からである。Ｃ１とＰ３の間は両方向で弧がないが、これは、明らかに、Ｐ３にパブリック負荷がなく（条件８）、Ｃ１が最大容量で動作しているからである。Ｐ１とＣ４の間は両方向で弧がないが、これは、条件（７）および条件（１０）の両方が満足されないからである。
【０１４０】
やはり、有向弧の存在は、サーバの負荷を減らし、負荷容量を超えずに別のサーバに負荷を増やし、他のサーバの負荷に影響しないようにする可能性を意味する。ダミー・ノードからサーバ・ノードの１つへの有向パスによって、負荷の１単位をステージング・ノードからそのサーバ・ノードに転送し、他のサーバ・ノードを影響されないままにすることができる。この転送の後に、グラフＨを、記帳技法を介して修正して、制約（８）、（９）、および（１１）の現在の状況を守ることができる（制約（７）および（１０）の状況は変更されない）。
【０１４１】
図９で、３つの異なるタイプの有向弧を見ることができる。１つのタイプは、ある区画サーバから別の区画サーバへのパブリック負荷またはプライベート負荷の潜在的な転送を示し、Ｐ１とＰ２の間に見られる。第２のタイプは、区画サーバからクラスタ・サーバへまたはその逆のパブリック負荷の潜在的な転送を示し、Ｐ１とＣ１の間に見られる。第３のタイプは、あるクラスタ・サーバから別のクラスタ・サーバへのパブリック負荷の潜在的な転送を示し、Ｃ１とＣ２の間に見られる。
【０１４２】
グラフＨが、できる限り多数の有向弧を有することに関して密であるほどに、ゴール手順によってより短い応答時間を生じる良い品質の結果を達成できる可能性が高くなることを理解されたい。これが、次に説明する静的手順の目標である。
【０１４３】
動的手順の詳細な実施形態を、図７の流れ図に示す。制御の流れは、ステップ２００で開始され、ウェブサイトｉおよびサーバｊのそれぞれについて、ゴール手順を使用して、最適化目標
【０１４４】
【数８０】
2005516293.tif 000082
および
【０１４５】
【数８１】
2005516293.tif 000083
を解く。ステップ２０５で、ｋ＝１をセットする。ステップ２１０で、ウェブサイトｉおよびサーバｊのそれぞれについて、
【０１４６】
【数８２】
2005516293.tif 000084
および
【０１４７】
【数８３】
2005516293.tif 000085
が０になるように初期化する。これらの変数によって、ゴールに関するディスパッチャの進捗をカウントする。ステップ２１５で、どのウェブサイトがキュー内の要求ｋに対応するかを判定する。ステップ２２０で、要求がパブリックまたはプライベートのどちらであるかを判定する。この２つの可能性のそれぞれについて、匹敵するフローがあるが、パブリックのフローに焦点を合わせる。これは、ステップ２２５で開始され、ここで、ｊ＝１をセットし、Ｍに負の無限大をセットする。下記のように、ゴールと達成された値の間の最大の差を有するサーバを見つける。ステップ２３０で、Ｍが
【０１４８】
【数８４】
2005516293.tif 000086
未満であるかどうかを調べる。そうである場合には、ステップ２３５で、ｊ＊＝ｊおよび
【０１４９】
【数８５】
2005516293.tif 000087
をセットし、ステップ２４０に進む。ステップ２３０のテストが否定の場合にもステップ２４０に分岐する。ステップ２４０で、ｊを増分する。ステップ２４５で、ｊがＮ以下であるかどうかを調べる。そうである場合には、ステップ２３０に戻る。そうでない場合には、勝利サーバｊ＊が得られており、ステップ２５０で
【０１５０】
【数８６】
2005516293.tif 000088
を増分し、要求ｋをサーバｊ＊にディスパッチする。次に、ステップ２５５に進み、ｋを増分する。ステップ２６０で、ｋが
【０１５１】
【数８７】
2005516293.tif 000089
以下であるかどうかをテストする。そうである場合には、ステップ２１０に戻って、次の要求をディスパッチする。そうでない場合には、要求のキューが空になっており、停止する。ステップ２２０で、要求がプライベート要求と決定された場合には、ステップ２７０から２９５に進む。これらのステップは、パブリック要求ではなくプライベート要求を扱うことを除いて、ステップ２２５から２５０に正確に類似する。最終的に、制御フローはステップ２２０に戻る。
【０１５２】
静的手順構成要素
図１０から１２を参照して、サイトをサーバに割り当てる静的手順構成要素を説明する。目標は、ゴール手順の達成可能な性能を最適化し、したがって、動的手順構成要素の性能を最適化することである。静的手順構成要素の鍵になる入力は、各ウェブサイトのパブリック要求およびプライベート要求の平均需要の予測と、許容可能なウェブサイト対サーバ割当に対する制約である。静的手順構成要素の出力は、単に、２つの｛０、１｝割当行列Ａ＝（ａｉ、ｊ）およびＢ＝（ｂｉ、ｊ）である。
【０１５３】
また、所与のものとしてウェブサイト対サーバ割当に関する制約を仮定する。この制約は、サーバ自体の物理的能力、許容可能に高いキャッシュ・ヒット率の達成の目標、サーバ上のオペレーティング・システム、あるサイトがネゴシエーションする可能性がある固定されたサーバ割当などに関する可能性がある。そのような制約は、非常に複雑または非常に初歩的である可能性がある。たとえば、キャッシュ制約を、おそらくは分析的ヒット率モデル、ウェブ・サイト・データの局所性、およびキャッシュ・サイズに基づく比較的複雑なものにすることができる。これが、比較的少数のサイトが各サーバに割り当てられることの保証という影響を有する。その一方で、オペレーティング・システム制約は、単に、どのサイトがあるサーバに関して不適切であるかのリストとすることができる。ポイントは、静的手順構成要素が、性質においてヒューリスティックであり、割当の変更を検討する前に単純に制約を検査することによって、制約を扱うことができることである。
【０１５４】
静的手順構成要素は、２つの可能なモードを有する。初期モード（図１２）は、サイトがまだサーバに割り当てられていない、新しいシステムを一から構成するのに使用される。次に、増分モードが、周期的に使用されて、改訂されたウェブサイト需要予測に基づいて既存のウェブサイト対サーバ割当が調整される。この調整の実施が実用的になることを保証するために、許可されるウェブサイト対サーバ割当変更の許容可能な回数を制限する制約を考慮に入れる。両方のモードが、本質的に同一の方法論を使用するように見える。初期モードでは、応答時間関数に分析的モデルを使用しなければならない可能性があり、増分モードでは、その代わりにより正確に測定された応答時間を使用することができる。これによって、おそらくは、キャッシングおよび他の実世界の現象の影響がよりよく取り込まれる。
【０１５５】
静的手順構成要素の増分は、頻繁に実行してはならない。というのは、割当変更を行う際に明白なコストがあるからである。週に１回程度が、おそらくは適度である。正確な頻度は、更新されたウェブサイト予測による性能改善の可能性と比較したこのコストの相対トレードオフに依存する。おそらく、静的手順の実行は、ある種の負荷不平衡状態の検出によってトリガすることができる。
【０１５６】
両方のモードの主要な目標は、次のように定義される非有向グラフＧの高い接続性を達成することである。ノードは、サーバに対応する。別個のノードの対ｊ１およびｊ２のそれぞれについて、
【０１５７】
【数８８】
2005516293.tif 000090
である少なくとも１つのウェブサイトｉ１、または
【０１５８】
【数８９】
2005516293.tif 000091
である少なくとも１つのウェブサイトｉ１が存在するならば、ｊ１とｊ２の間に弧がある。この条件は、有向グラフＨの定義の条件（７）および（１０）を模倣したものである。条件（８）、（９）、および（１１）は、一般に、すべてのよく平衡を取られたウェブ・ファームで満足されるので、この概念は、ＧがＨの効果的な代用物として働くということである。また、条件（７）および（１０）が、本質的に静的であり、条件（８）、（９）、および（１１）が、本来動的であることに留意されたい。これが、Ｇが静的手順構成要素についてより適切である理由である。
【０１５９】
図１０に、上で説明した例のグラフＧを示す。図９に示された有向グラフＨとの類似性に留意されたい。しかし、図１０の弧には、サーバＣ１とＰ３の間の弧があるが、図９には、どちらの方向にもそれに相当する有向弧がない。サーバＰ４からＰ３など、図９に示された複数の他の有向弧が、反対方向の有向弧と一致しない。図１０では、２つのクラスタ・サーバの間の弧が、実線として示され、２つの区画サーバの間の弧が、点線として示され、クラスタ・サーバと区画サーバの間の弧が、破線として示されている。
【０１６０】
最適化が試みられる目的関数は、本発明ではブラック・ボックスとして扱われる、ゴール手順構成要素自体の目的関数である。ここでの原理は、効果的に平均応答時間であるこの測定値が、明らかに、他の２つのグラフ理論の代用物（直径または平均距離）のどちらよりも直接的に適切であり、計算するのにそれほどコンピュータのコストがかからない。
【０１６１】
使用されるメタ表記は、チルダ「〜」が、静的手順問題定式化を指すことである。
【０１６２】
次のように、サーバへのサイトの割当の空間（いくつかの意味で好ましい）を記述する新しい行列
【０１６３】
【数９０】
2005516293.tif 000092
を発明することによって進行する。
【０１６４】
【数９１】
2005516293.tif 000093
は、やはり、サイズＭ×Ｎの｛０、１｝行列である。各ウェブサイトのパブリック・トラフィックおよびプライベート・トラフィックの両方に存在する通常の条件の下で、下記の形での、
【０１６５】
【数９２】
2005516293.tif 000094
から
【０１６６】
【数９３】
2005516293.tif 000095
および
【０１６７】
【数９４】
2005516293.tif 000096
への変換を行う。
【０１６８】
【数９５】
2005516293.tif 000097
【０１６９】
【数９６】
2005516293.tif 000098
【０１７０】
これによって、行の和が
【０１７１】
【数９７】
2005516293.tif 000099
であるすべてのサーバｊが、１つのウェブサイトのパブリックとプライベートの両方のトラフィックを有する区分サーバであり、他のすべてのサーバが、複数のパブリック・ウェブサイト・トラフィックを有するサーバであるという暗黙の仮定が行われる。割当行列ＡおよびＢのすべての可能な対を、ある行列
【０１７２】
【数９８】
2005516293.tif 000100
からの変換とみなすことはできないことに留意されたい。しかし、見なすことができない対は、より好ましくない。静的手順構成要素では、これらは選択されない。
【０１７３】
特殊な事例を扱うために、微調整を行う必要がある。ウェブサイトｉにプライベート・トラフィックだけが存在する場合に、
【０１７４】
【数９９】
2005516293.tif 000101
である時に、必ず、ｉ’≠ｉについて
【０１７５】
【数１００】
2005516293.tif 000102
であることが必要である。これによって、ｊが、ウェブサイトｉの区画サーバにされる。ａｉ、ｊ＝０かつｂｉ、ｊ＝１とする。ウェブサイトｉについてパブリック・トラフィックだけが存在する場合に、そのウェブサイトに割り当てられたすべてのサーバｊを、
【０１７６】
【数１０１】
2005516293.tif 000103
の場合であっても、公式にパブリックとみなすことができる。したがって、
【０１７７】
【数１０２】
2005516293.tif 000104
かつｂｉ、ｊ＝０とする。
【０１７８】
各サーバの負荷がその負荷限度Ｌｊを超える場合を処理するために、各サーバｊの応答時間関数Ｒｊも修正する必要がある。そのような実現不能性は、少なくともこの静的手順構成要素の初期段階で発生する可能性があり、大きい目的関数コストで実現可能性を強制することによって、この実現不能性を扱う必要がある。したがって、非常に大きい数Ｑを考慮し、ｋ≦Ｌｊについて
【０１７９】
【数１０３】
2005516293.tif 000105
であるが、
【０１８０】
【数１０４】
2005516293.tif 000106
などであるものとする。一般的な再帰によって、ｋ＞０について
【０１８１】
【数１０５】
2005516293.tif 000107
が定義される。
【０１８２】
【数１０６】
2005516293.tif 000108
が、凸の連続関数のままであることに留意されたい。また、最大許容可能負荷を、
【０１８３】
【数１０７】
2005516293.tif 000109
になるように再定義する。
【０１８４】
【数１０８】
2005516293.tif 000110
および
【０１８５】
【数１０９】
2005516293.tif 000111
が、それぞれ、ウェブサイトｉの予測されたパブリック負荷および予測されたプライベート負荷を指すものとする。ここでの説明は、各ウェブサイトにパブリック・トラフィックとプライベート・トラフィックの両方が存在する場合に基づくが、そうでない時に適切な修正は、簡単に決定することができる。
【０１８６】
一般性を失わずに、増加する予測された総負荷
【０１８７】
【数１１０】
2005516293.tif 000112
に関してサイトが再インデクシングされていると仮定する。また、サーバが、増加する性能に関して再インデクシングされていると仮定する。これは、たとえば、元々の最大許容可能負荷Ｌｊによって決定することができる。
【０１８８】
初期割当方法の最初のステップは、可能な範囲でのサイトをサーバに順番にマッチングすることである。あるサーバからあるサイトを制限する実現可能性制約がある場合があり、これを守らなければならない。したがって、図１２のステップ３０５から３３５に示された順番でウェブサイトｉ＝１からＭまでループして、ステップ３２５で
【０１８９】
【数１１１】
2005516293.tif 000113
をセットし、ここで、ｊは実現可能であるが現在割り当てられていないサーバの最小のインデックスであり、初期化時にすべての他のｊで
【０１９０】
【数１１２】
2005516293.tif 000114
をセットする。すべてのサイトに関して可能な実現可能な割当がないことは、可能であるが、おそらくは非常に可能性が低い。これが発生するのは、制約のゆえであり、Ｍ＞Ｎなので発生する可能性がある。この場合には、初期割当技法が失敗する。そうでない場合には、この時点でＭ個の区画サーバがあり、残りのＮ−Ｍ個のサーバは、アイドルである。
【０１９１】
この初期解の目的関数を評価するが、これは次のようになる。
【０１９２】
【数１１３】
2005516293.tif 000115
【０１９３】
この初期解を、いわゆる近傍エスケープ・ヒューリスティックの実施形態によって修正する。このヒューリスティックでは、メトリックΔを使用して、サーバへのサイトの２つの可能な割当の間の距離を測定するが、これを短く説明する。短く言えば、近傍エスケープ・ヒューリスティックは、局所最小値にトラップされないようにしながら比較的低い計算コストを達成する反復改良手順である。可能解の検索空間に対するモーメントの事前定義のメトリックΔと、上で説明したものなどの既存の初期可能解を仮定すると、この技法は、複数のステージで進行する。各ステージの始めに、ステージ中に修正できる、いわゆる現在の解がある。第１ステージの始めに、現在の解は、初期解である。各ステージで、現在の解の周囲で距離１、２、などの近傍を連続して検索する（現在の解の周囲の距離ｋの近傍は、現在の解からの距離がｋ以下のすべての実現可能な割当の集合である。現在の解の周囲の距離ｋのリングは、現在の解からの距離がｋであるすべての実現可能な割当の集合であり、距離ｋの近傍から距離ｋ−１の近傍を引いたものである）。目的関数改善を、現在の解の周囲の距離１の近傍で見つけることができる場合に、このヒューリスティックでは、そのような最善の改善を選択し、現在の解としてラベルを付けなおし、次のステージを開始することによって処理を繰り返す。距離１の近傍以内で改善が見つからない場合には、このヒューリスティックでは、代わりに距離２のリングを検討する。ここで、やはり２つの可能性がある。改善がある場合には、そのような最善の改善を現在の解として選択し、この手順では次のステージを開始する。そうでない場合には、距離３などのリングを検討し、固定された距離限度、たとえばＫまでリングを検討する。Ｋ番目のリング以内で目的関数改善に到達しない場合には、現在の解と等しい最終的な解を得て処理が終了する。さまざまなリングの検査は、図１２のステップ３６０、３８０、および３８５で行われる。改善は、ステップ３７０で検査される。
【０１９４】
図１１に、この処理を示す。初期ステージの始めの現在の解は、近傍の最初の集合、距離１の中心４００にある。ヒューリスティックでは、第１の近傍を検索し、改善が見つかるまで、後続のリングを順番に検索する。図では、改善が発生するのは、Ｋ番目のリング、距離Ｋのみである。次に、このヒューリスティックでは、新しい中心４１０によって表されるように、現在の解を検索で見つかった最善の改善にリセットし、第２ステージを開始する。この図には、その解の周囲の近傍が示されている。改善は、３番目のリングで見つかる。第３ステージが開始されるが、図には示されていない。第１ステージでＫ番目のリングで改善を得られない場合には、初期解が最終的な解になる。
【０１９５】
ここで、距離メトリックΔを定義する。
【０１９６】
【数１１４】
2005516293.tif 000116
および
【０１９７】
【数１１５】
2005516293.tif 000117
が、そのような２つの割当であるものとして、
【０１９８】
【数１１６】
2005516293.tif 000118
を定義する。
【０１９９】
ここでの意図は単純である。たとえば、単一のウェブサイトをサーバの１つに追加またはサーバの１つから削除することによって、割当
【０２００】
【数１１７】
2005516293.tif 000119
を新しい割当
【０２０１】
【数１１８】
2005516293.tif 000120
に修正する場合に、
【０２０２】
【数１１９】
2005516293.tif 000121
が得られる。古いサーバから新しいサーバ（前にウェブサイトを割り当てられていない）へのウェブサイトの移動は、図１１で距離２を有する。ウェブサイトをサーバから除去し、同時にそのサーバに異なるウェブサイトを追加することも、距離２を有する。異なるサーバでの異なるサイトの交換は、距離４を有し、以下同様である。
【０２０３】
所与の解
【０２０４】
【数１２０】
2005516293.tif 000122
とその変換された割当行列
【０２０５】
【数１２１】
2005516293.tif 000123
および
【０２０６】
【数１２２】
2005516293.tif 000124
を与えられれば、改善のテストに、制約
【０２０７】
【数１２３】
2005516293.tif 000125
の下で
【０２０８】
【数１２４】
2005516293.tif 000126
を最小化するというゴール手順構成要素問題を解くことが含まれる。
【０２０９】
もちろん、
【０２１０】
【数１２５】
2005516293.tif 000127
を伴う制約は、無意味である。しかし、限度Ｌｊを超える負荷のコストを与えられれば、近傍エスケープ・ヒューリスティックの非常に少数のステージの後に、各サーバｊについて
【０２１１】
【数１２６】
2005516293.tif 000128
を満足する解が期待される。したがって、あらゆる見通しから実現可能な割当が、短い順番で達成可能でなければならない。実際に、この手順の最初の少数のステージで、通常は、量の多いサイトが現在未使用のサーバに割り当てられ、その後、この技法では、区画サーバがクラスタ・サーバにされ、通常は、性能の高いサーバの状況が最初に変更される。
【０２１２】
増分手順は、周期的に、おそらく毎週１回実行されて、変化する予測の存在の下で、よいウェブサイト対サーバ割当が保たれる。幸い、増分手順では、実質的に同一の方法が使用される。
【０２１３】
初期解は、最後に実行された静的手順構成要素からの現在の解であり、もちろん、近傍エスケープ技法を介してこれを修正する。唯一の変更は、追加の停止判断基準すなわち、初期解と現在の解の間の距離が、あるユーザ定義の閾値Ｔを超える場合に停止するという判断基準を使用することである。これの理由は、割当変更が、実際に実施するのにコストがかかり、実行された静的手順構成要素の連続するインスタンスの間で激しく異なる解を許容することは望まないからである。
【０２１４】
図１２を参照すると、静的手順の詳細な実施形態が示されている。ステップ３００から開始して、ウェブサイトｉを１に初期化する。ステップ３０５で、サーバｊを１に初期化する。ステップ３１０で、サーバｊがウェブサイトｉについて実現可能であるかどうかを判定する。そうである場合には、ステップ３２０に進み、サーバｊが現在未割当であるかどうかを判定する。現在は未割当である場合には、ステップ３２５でこれを割り当て、ステップ３３０でウェブサイトｉを増分する。ステップ３３５で、ｉがサイトの総数Ｍ以下であるかどうかを判定する。そうである場合には、ステップ３０５に戻る。ステップ３１０または３２０のテストが否定の場合には、ステップ３４０に進み、サーバｊを増分する。ステップ３４５で、ｊがサーバの総数Ｎ以下であるかどうかを判定する。そうである場合には、ステップ３１０に戻る。そうでない場合には、ステップ３５０で、可能解なしで停止する。ステップ３３５でサイトが使い果たされた場合に戻ると、ステップ３５５に進み、この手順の近傍エスケープ構成要素を開始する。式（２５）によって、解の値Ｒを評価する。ステップ３６０で、ｋ＝１をセットする。ステップ３６５で、ｋ番目のリングを検索して、最良の可能な解Ｒｋを評価する。ステップ３７０で、最良の現在の解Ｒと比較してＲｋを評価する。新しい値の方がよい場合には、ステップ３７５でこれを最良の解にし、ステップ３６０に戻る。新しい値がよりよくない場合には、ステップ３８０でｋを増分する。ステップ３８５で、すべてのリングｋを使い果たしたかどうかを判定する。まだ使い果たしていない場合には、ステップ３６５に戻る。そうでない場合には、ステップ３９０で最後の割当解を得て停止する。
【０２１５】
本発明は、たとえば、コンピュータなどの命令を実行できる機械によって可読の記憶媒体上で命令のプログラムを有形に実施することによるなど、自動化に簡単に適合させることができる。
【０２１６】
用語「ウェブサイト」は、本発明をワールド・ワイド・ウェブのハイパーテキスト・マークアップ言語（ＨＴＭＬ）文書と共に使用することに制限する必要があるのではなく、顧客要求の受信、結果の出力、ならびに、たとえばローカル・エリア・ネットワーク上および類似物などのサーバとの通信が可能なすべてのユーザ・ネットワーク・インターフェースを含むと解釈されるべきである。
【０２１７】
本明細書で開示されたすべての物理的量が、他の形で明示的に示されない限り、開示された量と正確に等しいものと解釈されるのではなく、開示された量におおむね等しいと解釈されるべきであることを理解されたい。さらに、「約」などの修飾語が単にないことを、そのような修飾語が本明細書で開示される他の物理的な量に関して使用されるかどうかに無関係に、そのような開示された物理的量が正確な量であることの明示的な表示と解釈すべきでない。
【図面の簡単な説明】
【０２１８】
【図１】ネットワーク・ディスパッチャおよび複数のサーバを含むウェブ・ファームを示す図である。
【図２】ゴール手順の一部である、ダミー・ノードから勝利ノードへのパスを示す図である。
【図３】ゴール手順を示す流れ図である。
【図４】ゴール手順の初期化ステップを示す流れ図である。
【図５】ゴール手順のパス記帳ステップを示す流れ図である。
【図６】ゴール手順のグラフ記帳ステップを示す流れ図である。
【図７】動的手順を示す流れ図である。
【図８】動的手順を示す例のウェブサイト・シンボルの用語集である。
【図９】同一の例での動的手順の有向グラフを示す図である。
【図１０】同一の例での静的手順の非有向グラフを示す図である。
【図１１】静的手順での近傍エスケープ・ヒューリスティックを示す図である。
【図１２】静的手順を示す流れ図である。
【符号の説明】
【０２１９】
１０  ウェブ・ファーム
１２  サイト
１３  サーバ
１４  ネットワーク・ディスパッチャ
２０  ダミー「ノード０」
２１  サーバ・ノード
２２  サーバ・ノード
２３  サーバ・ノード
２４  サーバ・ノード
２５  勝利（サーバ）ノード
４００  中心
４１０  新しい中心
【図１】
2005516293.tif 000146
【図２】
2005516293.tif 000147
【図３】
2005516293.tif 000148
【図４】
2005516293.tif 000149
【図５】
2005516293.tif 000150
【図６】
2005516293.tif 000151
【図７】
2005516293.tif 000152
【図８】
2005516293.tif 000153
【図９】
2005516293.tif 000154
【図１０】
2005516293.tif 000155
【図１１】
2005516293.tif 000156
【図１２】
2005516293.tif 000157
【手続補正書】
【提出日】平成16年1月19日(2004.1.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のウェブサイトおよびサーバを有し、さらに、静的手順を有するウェブ・ファームを制御する方法であって、
前記ウェブサイトによって受信される顧客要求を、共用可能顧客要求および共用不能顧客要求を含む複数のカテゴリに分類するステップ、
前記サーバのいずれもが前記ウェブサイトの異なる１つから受け取られる共用可能顧客要求を処理できるように、前記共用可能顧客要求を経路指定するステップ、
前記ウェブサイトの特定の１つからの前記共用不能顧客要求を、前記特定のウェブサイトが割り当てられた特定のサーバだけに経路指定するステップ
を含み、前記共用不能顧客要求を経路指定する前記ステップは、前記静的手順が、各前記ウェブサイトからの共用可能顧客要求および共用不能顧客要求の予測された需要に基づいて前記ウェブサイトの特定の１つを特定の前記サーバに割り当てるステップを含む
方法。
【請求項２】
ゴール手順をさらに含み、前記ゴール手順が、前記ウェブサイトの前記サーバへの前記割当および現在の顧客要求負荷を与えられて、任意の所与の瞬間の平均顧客応答時間を最小にするために、前記顧客要求のそれぞれについて、前記顧客要求が割り当てられる前記サーバの間から最適なサーバを決定するステップを含む、請求項１に記載の方法。
【請求項３】
前記ゴール手順が、制約
【数１】
2005516293.tif 000158
の下で関数
【数２】
2005516293.tif 000159
を最小にすることによって行われ、ここで、Ｍは、ウェブサイトの数であり、Ｎは、サーバの数であり、Ｒｊは、サーバｊでの顧客到着レートの関数としての期待される応答時間であり、ｘｉ、ｊは、サーバｊによって処理することができるウェブサイトｉの共用可能要求の仮定の数を表す決定変数であり、ｙｉ、ｊは、サーバｊによって処理することができるウェブサイトｉの共用不能要求の仮定の数を表す決定変数であり、Ｌｊは、サーバｊの最大許容可能負荷であり、ｃｉは、ウェブサイトｉからの共用可能顧客要求の現在の数であり、ｄｉは、ウェブサイトｉからの共用不能な要求の現在の数であり、ａｉ、ｊは、ウェブサイトｉからの共用可能要求をサーバｊに経路指定できる場合を示すインデックスであり、ｂｉ、ｊは、ウェブサイトｉからの共用不能要求をサーバｊに経路指定できる場合を示すインデックスである、請求項２に記載の方法。
【請求項４】
有向グラフを作成し、維持するステップであって、前記有向グラフが、ダミー・ノードおよび複数のサーバ・ノードを含み、各前記サーバ・ノードが、前記サーバの１つに対応する、作成し、維持するステップ、
前記サーバ・ノードのうちで式
【数３】
2005516293.tif 000160
が最小であるサーバ・ノードを勝利ノードに指定するステップ、および、
前記ダミー・ノードから前記勝利ノードへの最短有向パスを選択するステップ
をさらに含む、請求項３に記載の方法。
【請求項５】
動的手順をさらに含み、前記動的手順が、
次の顧客要求を検査するステップ、
前記次の顧客要求を現在処理するのにどのサーバが最適サーバであるかを判定するために前記ゴール手順を呼び出すステップ、および、
前記次の顧客要求を前記最適サーバにディスパッチするステップ
を含む、請求項２ないし４のいずれか一項に記載の方法。
【請求項６】
前記顧客要求をキューに受信するステップ
をさらに含み、前記動的手順が、さらに、
前記キュー内の前記顧客要求を監視するステップ、
前記サーバによって現在処理されつつある顧客要求を監視するステップ、
各ｊ番目のサーバについて、
【数４】
2005516293.tif 000161
をセットするステップによって、関数
【数５】
2005516293.tif 000162
を定義するステップ、
各ｊ番目のサーバについて、
【数６】
2005516293.tif 000163
をセットするステップによって、改訂された許容可能負荷限度
【数７】
2005516293.tif 000164
を定義するステップ、および、
制約
【数８】
2005516293.tif 000165
の下で関数
【数９】
2005516293.tif 000166
を最小にするために前記
【数１０】
2005516293.tif 000167
関数および改訂された許容可能負荷限度
【数１１】
2005516293.tif 000168
を使用するために前記ゴール手順を呼び出すステップ
を含み、
【数１２】
2005516293.tif 000169
が、サーバｊによって処理できるウェブサイトｉに関する前記キュー内の共用可能要求の仮定の数を表す決定変数であり、
【数１３】
2005516293.tif 000170
が、サーバｊによって処理できるウェブサイトｉに関する共用不能要求の仮定の数を表す決定変数であり、
【数１４】
2005516293.tif 000171
が、ウェブサイトｉからの前記キュー内の共用可能顧客要求の現在の数であり、
【数１５】
2005516293.tif 000172
が、ウェブサイトｉからの前記キュー内の共用不能要求の現在の数であり、
【数１６】
2005516293.tif 000173
が、サーバの１つで現在処理されつつある、ウェブサイトｉからの共用可能顧客要求の現在の数であり、
【数１７】
2005516293.tif 000174
が、サーバの１つで現在処理されつつある、ウェブサイトｉからの共用不能要求の現在の数である
請求項５に記載の方法。
【請求項７】
請求項１ないし６のいずれかに記載の方法の各ステップをコンピュータに実行させるためのプログラム。
【請求項８】
複数のウェブサイトおよびサーバを有するウェブ・ファームであって、さらに、
顧客から顧客要求を受信する手段と、
応答を作るために前記顧客要求を処理する手段と、
前記応答を前記顧客に送信する手段と、
前記顧客要求を共用可能顧客要求および共用不能顧客要求に分類する手段と、
前記サーバのいずれかが前記ウェブサイトの異なる１つから受け取られる共用可能顧客要求を処理できるように、前記共用可能顧客要求を経路指定する手段と、
各前記ウェブサイトからの共用可能顧客要求および共用不能顧客要求の予測された需要に基づいて、前記ウェブサイトの特定の１つからの前記共用不能顧客要求を、前記特定のウェブサイトに割り当てられた特定のサーバだけに経路指定する静的手順と
を含むウェブ・ファーム。
【請求項９】
ゴール手順、静的手順、および動的手順を実行する手段を含むネットワーク・ディスパッチャをさらに含み、
前記ゴール手順が、前記ウェブサイトの前記サーバへの前記割当および現在の顧客要求負荷を与えられて、任意の所与の瞬間の平均顧客応答時間を最小にするために、前記顧客要求のそれぞれについて、各前記顧客要求が割り当てられる前記サーバの間から最適なサーバを決定する手段を含み、前記共用可能顧客要求を、いずれかの前記サーバに割り当てることができ、前記共用不能顧客要求を、前記共用不能顧客要求が発した前記ウェブサイトに依存する特定のサーバに割り当てることだけができ、
前記静的手順が、特定の前記ウェブサイトを特定の前記サーバに割り当てる手段を含み、
前記動的手順が、
次の顧客要求を検査する手段、
前記次の顧客要求を現在処理するのにどのサーバが最適サーバであるかを判定するために前記ゴール手順を呼び出す手段、および、
前記次の顧客要求を前記最適サーバにディスパッチする手段
を含む
請求項８に記載のウェブ・ファーム。
【国際調査報告】
2005516293.tif 000175
2005516293.tif 000176