(57)【要約】  【課題】  多層コンピューティング・システムで容量割当てを決定するための技術を提供する。  【解決手段】  本発明のある態様においては、その各層が１つまたは複数のコンピューティング装置（例えばサーバ）を有する多層コンピューティング・システムのための容量割当てを設計するための技術は、下記のステップ／動作、すなわち、容量割当てに関する入力パラメータを入手するステップと、容量割当てを入力パラメータの少なくとも一部に基づいて計算するステップとを含む。容量割当ては、１つまたは複数のエンド・ツウ・エンド性能測定値が複数のサービス・クラスを実質的に満足させるように計算することができる。容量割当ての計算は、コスト関数を最小化することができる。容量割当て計算は、また、複数のサービス・クラスに対する１つまたは複数の平均遅延保証、複数のサービス・クラスに対する１つまたは複数のテール分布保証、または複数のサービス・クラスに対する１つまたは複数の平均遅延保証および１つまたは複数のテール分布保証の両方を満足させることができる。【選択図】      図９
2008503008.tif 000002
【特許請求の範囲】
【請求項１】
その各層が１つまたは複数のコンピューティング装置を有する多層コンピューティング・システムの容量割当てを設計するための方法であって、
容量割当てに関連する入力パラメータを入手するステップと、
前記入力パラメータの少なくとも一部に基づいて容量割当てを計算するステップであって、前記容量割当てを１つまたは複数のエンド・ツウ・エンド性能測定値が複数のサービス・クラスを実質的に満足させるように計算することができるステップとを含む方法。
【請求項２】
前記容量割当てを計算する前記ステップが、コスト関数を実質的に最小化するステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記容量割当てを計算する前記ステップが、前記複数のサービス・クラスのための１つまたは複数の平均遅延保証を実質的に満足させるステップをさらに含む、請求項１に記載の方法。
【請求項４】
前記容量割当てを計算する前記ステップが、前記複数のサービス・クラスのための１つまたは複数のテール分布保証を実質的に満足させるステップをさらに含む、請求項１に記載の方法。
【請求項５】
前記容量割当てを計算する前記ステップが、前記複数のサービス・クラスのための１つまたは複数の平均遅延保証および１つまたは複数のテール分布保証を実質的に満足させるステップをさらに含む、請求項１に記載の方法。
【請求項６】
前記容量割当てを計算する前記ステップが、前記複数のサービス・クラスのための前記１つまたは複数の平均遅延保証および前記１つまたは複数のテール分布保証を実質的に満足させるために、容量割当て問題を最適化問題として定式化するステップをさらに含む、請求項５に記載の方法。
【請求項７】
前記容量割当てを計算する前記ステップが、前記最適化問題を線形制約を含む分離可能な凸状計画問題として定式化するステップをさらに含む、請求項６に記載の方法。
【請求項８】
前記容量割当てを計算する前記ステップが、前記計画問題に対する実行可能な解を表す凸包の境界上で最適解を発見することにより、前記分離可能な凸状計画問題を解くステップをさらに含む、請求項７に記載の方法。
【請求項９】
前記求解ステップが、多項式時間内で前記分離可能な凸状計画問題を解くステップをさらに含む、請求項８に記載の方法。
【請求項１０】
その各層が１つまたは複数のコンピューティング装置を有する多層コンピューティング・システムのための容量割当てを設計する装置であって、
メモリと、
前記メモリと結合していて、（ｉ）容量割当てに関連する入力パラメータを入手し、（ｉｉ）前記入力パラメータの少なくとも一部に基づいて容量割当てを計算するために動作する少なくとも１つのプロセッサであって、前記容量割当てを１つまたは複数のエンド・ツウ・エンド性能測定値が複数のサービス・クラスを実質的に満足させるように計算することができるプロセッサとを備える装置。
【請求項１１】
前記容量割当てを計算する前記動作が、コスト関数を実質的に最小化するステップをさらに含む、請求項１０に記載の装置。
【請求項１２】
前記容量割当てを計算する前記動作が、前記複数のサービス・クラスのための１つまたは複数の平均遅延保証を実質的に満足させるステップをさらに含む、請求項１０に記載の装置。
【請求項１３】
前記容量割当てを計算する前記動作が、前記複数のサービス・クラスのための１つまたは複数のテール分布保証を実質的に満足させるステップをさらに含む、請求項１０に記載の装置。
【請求項１４】
前記容量割当てを計算する前記動作が、前記複数のサービス・クラスのための１つまたは複数の平均遅延保証および１つまたは複数のテール分布保証を実質的に満足させるステップをさらに含む、請求項１０に記載の装置。
【請求項１５】
前記容量割当てを計算する前記動作が、前記複数のサービス・クラスのための前記１つまたは複数の平均遅延保証および前記１つまたは複数のテール分布保証を実質的に満足させるために、容量割当て問題を最適化問題として定式化するステップをさらに含む、請求項１４に記載の装置。
【請求項１６】
前記容量割当てを計算する前記動作が、前記最適化問題を線形制約を含む分離可能な凸状計画問題として定式化するステップをさらに含む、請求項１５に記載の装置。
【請求項１７】
前記容量割当てを計算する前記動作が、前記計画問題に対する実行可能な解を表す凸包の境界上で最適解を発見することにより、前記分離可能な凸状計画問題を解くステップをさらに含む、請求項１６に記載の装置。
【請求項１８】
前記求解動作が、多項式時間内で前記分離可能な凸状計画問題を解くステップをさらに含む、請求項１７に記載の装置。
【請求項１９】
その各層が１つまたは複数のコンピューティング装置を有する多層コンピューティング・システムの容量割当てを設計するための製造のための物品であって、前記製造のための物品が、実行した場合に、
容量割当てに関連する入力パラメータを入手するステップと、
前記入力パラメータの少なくとも一部に基づいて容量割当てを計算するステップであって、前記容量割当てを１つまたは複数のエンド・ツウ・エンド性能測定値が複数のサービス・クラスを実質的に満足させるように計算することができるステップと
を実施する１つまたは複数のプログラムを含む機械読み取り可能媒体を有する物品。
【請求項２０】
前記容量割当てを計算する前記ステップが、コスト関数を実質的に最小化するステップをさらに含む、請求項１９に記載の物品。
【請求項２１】
前記容量割当てを計算する前記ステップが、前記複数のサービス・クラスのための１つまたは複数の平均遅延保証を実質的に満足させるステップをさらに含む、請求項１９に記載の物品。
【請求項２２】
前記容量割当てを計算する前記ステップが、前記複数のサービス・クラスのための１つまたは複数のテール分布保証を実質的に満足させるステップをさらに含む、請求項１９に記載の物品。
【請求項２３】
前記容量割当てを計算する前記ステップが、前記複数のサービス・クラスのための１つまたは複数の平均遅延保証および１つまたは複数のテール分布保証を実質的に満足させるステップをさらに含む、請求項１９に記載の物品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、データ・ネットワーク・インフラストラクチャ設計技術に関し、特にデータ・ネットワーク・インフラストラクチャに関連するコストを最小限度まで低減し、複数のクラスのサービスに対するエンド・ツウ・エンド遅延に対する特定の性能保証を行うための設計技術に関する。
【背景技術】
【０００２】
インターネット（またはワールド・ワイド・ウェブ）に関連する帯域幅および接続性が増大するにつれて、電子ビジネスまたは「e-ビジネス」（すなわち、インターネットを通して行うビジネス）はますます広く行われるようになってきている。多くの従来のサービスは、ウェブをベースとするサービスに変換または変容してきている。e-ビジネスは、多くの従来のビジネスのコスト・パフォーマンスがよい解になっているばかりでなく、新しいビジネスの機会も創設している。現在、例えば、オンライン・ショッピング、オンライン・オークション、オンライン予約、オンライン・バンキングおよびオンライン取引から顧客関連管理、個人管理等に至るまで種々のe-ビジネスが行われている。e-ビジネスは、性能および利用度の保証が不可欠なものになってきている多くの会社の非常に重要なコンポーネントとなってきている。
【０００３】
それ故、e-ビジネス・インフラストラクチャの設計および開発は、２つの難問を解決しなければならない。一方では、e-ビジネス・インフラストラクチャの設計および開発は、サービスの品質（ＱｏＳ）の点で顧客の期待を満たさなければならない。他方では、会社は、競合できるように情報技術（ＩＴ）コストを制御しなければならない。それ故、最もコスト・パフォーマンスがよいアーキテクチャおよびシステムを決定することができるように、コストとサービス・レベルとの間の折り合いを理解することが重要である。
【０００４】
e-ビジネス・インフラストラクチャの最も一般的なアーキテクチャのうちの１つは、多層アーキテクチャである。この場合、必ずしもすべての層を通さなくても、前の端部から後の端部へ、サーバのいくつかの層を通してシステムにより要求に対してサービスが提供される。アーキテクチャの点では簡単であっても、システムは非常に複雑なものであり、通常、大型であり、サーバの複数の層を含み、各層は多くのコンポーネントを有することができる。典型的なe-ビジネス・システムは、その上で稼働している数十のアプリケーションを含む数百のノードからなる。システム全体が非常に複雑なために、ＩＴプラナーは、現在のインフラストラクチャ内の各層にどれだけ多くのサーバを設置すべきか、どんなレイアウトにしたらＱｏＳが最善になるか、予想したビジネスの機会および将来の成長をサポートするのに十分な容量があるのかについての問題にいつでも頭を悩ましている。
【０００５】
現在のe-ビジネス環境のもう１つの重要な特徴は、１つのシステムがサポートすることができるサービスが種々様々であることである。複数のクラスのサービスが通常複数のクライアントに提供されるが、そのすべてが時分割であり、同じ一組のリソースに対して競合するものである。サービス・プロバイダは、個々の各クライアントと契約を結び、各クラスのサービスについてあるレベルのＱｏＳを保証することに同意する。
【０００６】
エンド・ツウ・エンド性能を提供するためのリソース割当てを決定するための現在のアプローチは極めて少ない。これらの現在のアプローチの大部分は、１つの層に焦点を当てて、スケジュール作成または負荷のバランスの問題を処理している。
【０００７】
それ故、エンド・ツウ・エンド性能保証を満たしながら、インフラストラクチャ・コストを最小限度まで低減するために、複数のクラスのサービスを含む多層システムで容量割当てを決定する技術が求められている。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は、多層システムで容量割当てを決定するための技術を提供する。
【課題を解決するための手段】
【０００９】
本発明のある態様においては、その各層が１つまたは複数のコンピューティング装置（例えば、サーバ）を有する多層コンピューティング・システムのための容量割当てを設計するための技術は、下記のステップ／動作を含む。容量割当てに関する入力パラメータを入手するステップ。この入力パラメータの少なくとも一部に基づいて容量割当てを計算するステップ、この場合、容量割当ては、１つまたは複数のエンド・ツウ・エンド性能測定値が複数のサービス・クラスを実質的に満足させるように計算することができる。
【００１０】
さらに、容量割当てを計算するステップ／動作は、さらに、コスト関数を実質的に最小化するステップを含むことができる。容量割当てを計算するステップ／動作は、さらに、複数のサービス・クラスに対する１つまたは複数の平均遅延保証を実質的に満足させるステップを含むことができる。容量割当てを計算するステップ／動作は、さらに、複数のサービス・クラスに対する１つまたは複数のテール分布保証を実質的に満足させるステップを含むことができる。
【００１１】
さらに、容量割当てを計算するステップ／動作は、さらに、複数のサービス・クラスに対する１つまたは複数の平均遅延保証および１つまたは複数のテール分布保証を実質的に満足させるステップを含むことができる。容量割当てを計算するステップ／動作は、さらに、複数のサービス・クラスに対する１つまたは複数の平均遅延保証および１つまたは複数のテール分布保証を実質的に満足させるために、容量割当て計算（または問題）を最適化問題として定式化するステップを含むことができる。最適化問題は、線形制約を含む分離可能な凸状計画問題（separable convex programming problem）として定式化することができる。分離可能な凸状計画問題は、この計画問題への実行可能な解を示す凸包（convex hull）の境界上で最適解を発見することにより解くことができる。分離可能な凸状計画問題は、多項式時間で解くことができる。
【発明を実施するための最良の形態】
【００１２】
添付の図面を参照しながら本発明の例示としての実施形態の下記の詳細な説明を読めば、本発明のこれらおよび他の目的、機能および利点を理解することができるだろう。
【００１３】
以下に例示としてのe-ビジネス環境を使用して本発明について説明する。しかし、本発明は、任意の特定の環境での使用に限定されないことを理解されたい。それどころか、本発明は、もっと一般的に、例えば、エンド・ツウ・エンド性能保証を満たしながら、インフラストラクチャ・コストを最小限度まで低減するために容量割当てを決定することが望ましい任意のデータ・ネットワーク環境での使用に適用することができる。
【００１４】
詳細な説明の残りの部分は次のように構成されている。第１節においては、本発明の原理を紹介する。第２節においては、一般的なフィードフォワード・ネットワークにより考慮中の例示としての問題を説明し、当該２つの性能基準、すなわちエンド・ツウ・エンド応答時間の平均分布およびテール分布を紹介する。第３節においては、平均性能保証について重点的に説明する。第４節においては、エンド・ツウ・エンド応答時間のテール分布についての性能保証について重点的に説明する。次に、第３節および第４節の結果が結合され、第５節においては、両方のタイプのエンド・ツウ・エンド応答時間保証により、例示としてのアプローチについて説明する。第６節においては、本発明の技術の例示としての性能を実証するために数字による結果を使用する。第７節においては、いくつかの例示としてのケースについて説明する。第８節においては、例示としての設計システムおよび方法について説明する。
【００１５】
１．始めに
以下に例を挙げて説明するように、本発明は、エンド・ツウ・エンド応答時間の平均分布およびテール分布両方へのサービス保証を提供する。この場合、実際には、平均応答時間は平均遅延とも呼ばれ、テール分布は、予め指定した閾値より長いエンド・ツウ・エンド遅延を受ける要求の百分率を示す。例えば、平均遅延性能保証は、要求当たりの平均遅延が５秒より短くなるように要求することができ、テール分布保証は、要求の５％以上が１５秒より長い遅延を受けないように要求することができる。
【００１６】
所与の容量割当てのコストは、容量割当てベクトルの凸状の分離可能な増大関数であると仮定する。すなわち、層ｔに容量ｃｔが割り当てられた場合には、ｆｔ（ｃｔ）のコストが発生し、Ｔ個の層を有するシステムへの割当ての全コスト（ｃ１,...,ｃＴ）は、単に
【数１】
2008503008.tif 000003
になる。このようなコスト関数は、多くのe-ビジネス・コスト構造に対して使用することができる。例えば、ｆ（ｃ）がｃで線形である場合には、コスト構造はＩＴ費用に関するものだけになる。また、層ｔのところの平均遅延または遅延のテール確率を表すように、ｆｔ（ｃｔ）を選択することもでき、この場合、ｆｔ（ｃｔ）はＱｏＳ契約（すなわち、サービス・プロバイダとサービス・クライアントの間の性能についての合意）に関連する利益または罰金を表す。
【００１７】
さらに、本発明は、非線形計画問題の定式化を提供し、その構造特性を処理する。平均応答時間保証だけの場合には、この解が有利な幾何学的解釈を有することが分かっている。本発明は、また、この問題を解くための種々の方法を提供する。
【００１８】
応答時間のテール分布に対する補償を含む問題はもっと複雑である。本発明は、エンド・ツウ・エンド遅延のテール分布の上下から境界となる近似方法を提供する。上限によりテール分布保証が確保される。それ故、対応する全コストも、最適解の上限である。コスト関数の下限も同様に入手することができる。本発明の解は、すべての層のところのジョブ・クラスのサービス要求から独立している一定の係数だけ最適状態から離れていることが分かっている。また、サービス要件が厳しかった場合、本発明の技術は漸近的最適状態を達成することができることも分かっている。最後に、エンド・ツウ・エンド応答時間保証の両方のタイプに関連して本発明を説明する。
【００１９】
２．問題
この例示としての説明の場合、フィードフォワード多層システムは、図１に示すものと見なされる。ｔ＝１,...,Ｔ個のサーバ・ステーション（または層）、およびｋ＝１,...,Ｋ個のクラスのジョブが存在する。クラスｋの到着はレートλｋのポアソンであると仮定する。クラスｋのジョブは、決定性シーケンスである経路ｋ：ｖ（ｋ，１），ｖ（ｋ，２）,...,ｖ（ｋ，Ｌｋ）に沿ってステーションに行く。ｖ（ｋ，ｌ）＝ｔである場合には、クラスｋのジョブは段階ｌのところでサーバ・ステーションｔに行くと言われる。経路は、すべてのｋに対して、
v(k, 1)<v(k, 2)<...<v(k, Tk)
であるという意味でフィードフォワードであると仮定する。
ここで、Ｔｋは、経路ｋ内のホップ（層）の全数である。経路ｋがステーションｔを通過する場合には、δｔｋ＝１と表示し、そうでない場合には、δｔｋ＝０と表示する。この場合、λｔｋ＝δｔｋλｋは、ステーションｔへのクラスｋジョブの到着レートである。
【００２０】
各サーバ・ステーションのところには、複数のサーバが位置することができる。個々の各サーバは単位容量を有し、ステーションｔのところのサーバｃｔの総数はまだ分かっていないと仮定する。
【数２】
2008503008.tif 000004
は以降ライトアローｃと記載する
＝（ｃ１，ｃ２,..., ｃＴ）はステーションｔが容量ｃｔを有するような容量割当てであるとする。ステーションｔに属するすべてのサーバは、プロセッサを共有（ＰＳ）する形で一緒に動作し、外部からの要件を実行するものと仮定する。
【００２１】
ステーションｔのところでのクラスｋのジョブの公称サービス要件は、独立していて、平均がｍｔｋ＝Ｅ［Ｓｔｋ］である同じように分布されたランダム変数Ｓｔｋである。「公称」という用語を使用したのは、層ｔのところの容量ｃｔが、決定変数であるからである。それ故、容量ｃｔが層ｔに割り当てられた場合には、層ｔのところのクラスｋのジョブに対する平均サービス時間はｍｔｋ／ｃｔである。
【００２２】
ｑｔを下式のようになるようなステーションｔのところでの公称サーバ使用としよう。
【数３】
2008503008.tif 000005
それ故、容量ｃｔの場合には、ステーションｔのところでのサーバの使用はρｔ＝Σｋλｔｋｍｔｋ／ｃｔ＝ｑｔ／ｃｔとなる。システムを安定にするために（すなわち、時間の経過により作業量が無限に蓄積しないように）、最小容量割当てｃは下式を満足させなければならない。
ｃｔ＞ｑｔ（すべてのｔ＝１,...,Ｔに対して）
【００２３】
プロセッサを共有するサービス方針の下で、すべてのサーバ・ステーションは、対称キューであり、そのため準可逆的である。準可逆ステーションの固定オープン・ネットワークの場合には、積形式が保持し、さらに下記の２つの特性を有することになることが分かっている。
ｉ）各ステーションの状態変数は、他のステーションの状態変数から独立している。
ｉｉ）各ステーションのところの各クラスのジョブの到着プロセスは、ＰＡＳＴＡ特性を有する。この場合、ＰＡＳＴＡは、Poisson Arrivals See Time Average（ポアソン到着チェック時間平均）を意味する。これは、任意の到着時間において、新しい到着は、いつでもシステムが平均状態（例えば、任意の新しい到着が見たキュー内のジョブ待ちの数が平均キュー長である等）にあるのを見ることを意味する。
さらに、バークの定理に基づいて、下記のようになる。
ｉｉｉ）フィードフォワード・ネットワーク内の各ステーションのところの到着プロセスもポアソンである。
【００２４】
Ｒｔｋをステーションｔのところのクラスｋのジョブに対する固定応答時間ランダム変数としよう。Ｒｋは、クラスｋジョブの固定エンド・ツウ・エンド応答時間ランダム変数である。特性ｉ〜ｉｉｉ）に基づいて、各ｋに対して、｛Ｒｔｋ，ｔ＝１，２,...,Ｔ｝は独立ランダム変数になり、また
【数４】
2008503008.tif 000006
となる。この場合、
【数５】
2008503008.tif 000007
は分布の等価を示す。積形式に基づいて、ステーションｔのところのジョブの数が、Ｍ／Ｍ／１キュー内のジョブ数と同じであることが分かる。それ故、下式のようになり、
【数６】
2008503008.tif 000008
クラスｋジョブの平均エンド・ツウ・エンド遅延は下式のようになる。
【数７】
2008503008.tif 000009
【００２５】
下記の２つのタイプのサービス保証について考察する。
【数８】
2008503008.tif 000010
および
Ｐ［Ｒｋ＞Ｕｋ］≦εｋ（各ｋに対して）                （２）
制約（１）は、クラスｋジョブの平均エンド・ツウ・エンド応答時間が
【数９】
2008503008.tif 000011
以下であることを保証し、制約（２）は、クラスｋのエンド・ツウ・エンド遅延がＵｋ以上になる確率が∈ｋ以下であることを保証する。
【００２６】
コスト構造は、容量割当てｃ＝（ｃ１，ｃ２,..., ｃＴ）の分離可能な漸増関数であると仮定する。すなわち、すべてのｔ＝１,...,Ｔに対して、ｆｔ（・）は凸状漸増関数である。容量ｃｔが層ｔに割り当てられた場合には、ｆｔ（ｃｔ）のコストが発生する。この割当ての全コストは単に
【数１０】
2008503008.tif 000012
である。この問題は、これらのエンド・ツウ・エンド応答時間保証の一方または両方で、容量割当ての全コストを最小限度まで低減するためのものである。
【００２７】
３．平均遅延保証
最初に、（１）の形の平均遅延保証を含む問題を考察する。これは、顧客からのサービス・レベル要件の普通のまた自然の形である。平均遅延要件が保証されるような最もコスト・パフォーマンスがよい容量割当てを発見する問題は、下式のように定式化することができる。
【数１１】
2008503008.tif 000013
【００２８】
条件（５）はまさしく安定条件である。各層ｔが必要とする容量ｃｔは、システムを確実に安定させるために少なくともｑｔでなければならないし、応答時間を有限にするために、ｑｔより大きくなければならない。それ故、ｃｔ＝ｑｔ＋１／ｘｔとなるように新しい変数ｘｔを割り当てることができる。この場合、１／ｘｔは、層ｔに割り当てられる余分な容量（最小要件ｑｔを超える）である。さらに、下記のようになる。
【数１２】
2008503008.tif 000014
【００２９】
この場合、Ｗｔｋは、その必要な平均エンド・ツウ・エンド上限
【数１３】
2008503008.tif 000015
に対する層ｔのところのクラスｋジョブに対する公称サービス時間の重量（または相対的比率）であると解釈することができる。
【００３０】
この時点で、この問題は下式のように簡単になる。
【数１４】
2008503008.tif 000016
ここで、ｇｔ（ｘｔ）＝ｆｔ（ｑｔ＋１／ｘｔ）＝ｆｔ（ｃｔ）である。この問題は、余分なシステム容量１／ｘｔにより生じる全コストを最小限度に低減する問題になる。当然、各ｔに対して関数ｆｔは漸減しないものと仮定する。それ故、ｇｔは漸増しない関数である。さらに、この節の残りの部分においては、ｇｔは凸状関数であると仮定する。ｆｔが凸状である場合には、この仮定が満たされることを容易に理解することができる。しかし、このことは必要ではない。また、例えばｆｔ（ｃｔ）＝ｌｎ（ｃｔ）のようないくつかの周知の凹状コスト関数の場合にもこの仮定は満たされる。
【００３１】
また、実行可能な領域がコンパクトになるように、最後の制約（５）が＞から≧に緩和されることに留意されたい。ｘｔ＝０が決して最適解にならないことは明らかである。
【００３２】
表記を簡単にするために、ベクトルを表すために
【数１５】
2008503008.tif 000017
は以降ライトアローｘと記載する
および
【数１６】
2008503008.tif 000018
は以降ライトアローｗと記載する
ｋ（ｋ＝１,...,Ｋ）を使用することにする。
【数１７】
2008503008.tif 000019
実行可能性条件は下記のようになる。
【数１８】
2008503008.tif 000020
【００３３】
最適化問題（Ｍ）は、自然の解釈で直ちに簡単にすることができる有利な形を有する。Ωで実行可能な領域を表すことにする。すなわち、
【数１９】
2008503008.tif 000021
となる。Ωが正の象限ＲＴ＋内でベクトルライトアローｗ１,..., ライトアローwＫにより決まる多面体セットであることに留意されたい。またΩを多面体＋（ライトアローｗ１,..., ライトアローwＫ）として表す。｛ライトアローｗλ，λ∈Ｓ｝を多面体＋（ライトアローｗ１,..., ライトアローwＫ）の最大頂点により決まる最大ベクトルであるとしよう。その場合、各ベクトルライトアローwｋ（ｋ＝１,...,Ｋ）は、最大ベクトル｛ライトアローｗλ，λ∈Ｓ｝の凸状組合せにより支配される。すなわち、下記のようになる。
【数２０】
2008503008.tif 000022
【００３４】
この場合、ライトアローｗλ・ライトアローｘ≦１（λ∈Ｓ）を満足させるすべての
【数２１】
2008503008.tif 000023
に対して、ライトアローｘ∈Ωも満足させなければならない。それは、ライトアローｘ≧０であるからであり、
【数２２】
2008503008.tif 000024
であるからである。
【００３５】
このことは、ライトアローｗｋに対応する制約は、最大ベクトル｛ライトアローｗλ，λ∈Ｓ｝に対応する制約から入手することができることを意味する。それ故、それがある他のライトアローｗベクトルの凸状組合せにより支配されている場合には、ベクトルライトアローｗｋに対応する制約を無視することができる。最大ベクトル｛ライトアローｗλ，λ∈Ｓ｝は最大頂点により完全に決まることに留意されたい。多面体＋（ライトアローｗ１,..., ライトアローwＫ）は、単なるすべての最大頂点の凸包である。この場合、下記の特性が得られる。
【００３６】
特性１．（Ｍ）への最適解は、多面体＋（ライトアローｗ１,..., ライトアローwＫ）の頂点により決まる。
【００３７】
すなわち、点ライトアローｗｋが多面体の内部に位置する場合には、最適解を決定する際に役に立たない。もとの問題の場合には、サーバ容量を割り当てる場合には、平均エンド・ツウ・エンド応答時間制約を満足させるあるクラスのジョブは、自動的に満足する他のクラスのジョブの平均応答時間制約を意味することができる。この場合、後者のジョブ・クラスに対する平均応答時間制約の厳しさはもっと緩くなり、前者のジョブ・クラスの制約から入手することができる。この場合、多面体の最大頂点は、その応答時間制約がもっと厳しいジョブのクラスに対応し、他のジョブ・クラスに対する制約から入手することはできない。
【００３８】
定式を簡単にした後で、この問題に対する最適解の発見方法に戻って説明する。最適化問題（Ｍ）は、線形制約を含む分離可能な凸状計画問題である。このような線形制約を含む分離可能な凸状計画問題は、線形プログラムに変換することができ、多項式時間で解くことができることに留意されたい。このようなプログラムについては以下に説明する。
【００３９】
さらに、（Ｍ）の目的関数は、各変数において単調増加しないタイプであることが分かる。何故なら、最適解は、必ず実行可能な領域の境界上に位置していなければならないからである。すなわち、
特性２．（Ｍ）に対する最適解は、必ず多面体＋（ライトアローｗ１,..., ライトアローwＫ）の境界上に位置していなければならない。
【００４０】
このことは、最適解が非常にしばしば内部の点である一般的な凸状最適化問題と比較すると、若干直感的でないことに留意されたい。
【００４１】
３．１．線形コスト関数を含む平均遅延保証
この節の残りの部分では、コスト関数が線形である場合について考察する。すなわち、ｆｔ（ｃｔ）＝ｃｔである。それ故、コスト構造はＩＴ費用に全面的に依存する。次に、平均遅延制約を満たすように全容量を最小限度に低減する問題は、下式により表すことができる。
【数２３】
2008503008.tif 000025
定式（Ｍ１）から、最適解ｘ＊は、到着強度に依存しないことが分かる。すなわち、平均エンド・ツウ・エンド遅延保証を確保するために必要な余分な容量は、重量ｗｔｋだけで決まる。それ故、稼働中のシステムに対して上記プラニング問題をオンラインで容易に適応させることができる。何故なら、外部からの負荷に対する予測した容量要件に、余分な容量に対する解を追加するだけでよいからである。
【００４２】
この双対問題（dual problem）を分析すれば、有利な構造および特性を容易に使用することができ、また効率的な解を容易に開発することができる。さらに、この双対解（dual solution）は、多くの場合、感度および堅牢さの分析の際に重要な役割を演じる。ここで、この双対問題について考察する。
【００４３】
最初に、ラグランジュ問題について考察する。
【数２４】
2008503008.tif 000026
ここで、ｓｋはラグランジュ乗数である。
【００４４】
Karush-Kuhn-Tucker（ＫＫＴ）条件を使用すると、最適解に対する下記の特性が得られる。
【数２５】
2008503008.tif 000027
命題１．最適解ライトアローｘおよびｓ１,..., ｓＫに対して
【数２６】
2008503008.tif 000028
【００４５】
このことは下記のように証明することができる。相補緩み条件（１２）から下式のようになる。
【数２７】
2008503008.tif 000029
ここで、最後から２番目の等式は最適条件（１１）に従う。
【００４６】
所与のｓ＝（ｓ１,...,ｓＫ）の場合には、ラグランジュの双対関数（dual function）ｑ（ｓ）は、下式のように定義される。
【数２８】
2008503008.tif 000030
それ故、（Ｍ１）の双対問題は下式のようになる。
【数２９】
2008503008.tif 000031
ｈを下式のように定義しよう。
【数３０】
2008503008.tif 000032
その場合、ｇは下式により表すことができる。
【数３１】
2008503008.tif 000033
最後のステップの最小値はｕ＝ｈのところで得られる。これにより下記の命題となる。
【００４７】
命題２．目的値がｈに等しい場合には、問題（Ｄ２）に対する最適解は
【数３２】
2008503008.tif 000034
であると仮定する。それ故、問題（Ｄ１）に対する最適解ｓ１,..., ｓＫは
【数３３】
2008503008.tif 000035
となる。また最適目標値は、ｇ＝ｈ２である。
【００４８】
問題（Ｄ２）は、下式のように書き換えることができる。
【数３４】
2008503008.tif 000036
この問題は有利な幾何学的解釈を有する。目的関数Σｔ√ｗｔ０が最大になるように、多面体＋（ライトアローｗ１,..., ライトアローwＫ）上の最良点ライトアローｗ０を発見したい。
【００４９】
図２は問題（Ｄ３）の幾何学的解釈を示す。Ｔ次元の空間を考えてみよう。この場合、各点は加重サービス時間要件ベクトル
【数３５】
2008503008.tif 000037
に対応する。多面体＋（ライトアローｗ１,..., ライトアローwＫ）をライトアローｗ１,..., ライトアローwＫにより決まる正の象限ＲＴ＋内の多面体としよう。問題（Ｄ３）は、原点に向かって面Σｔ√ｗｔ＝ｃを移動し、面と多面体が交差する多面体＋（ライトアローｗ１,..., ライトアローwＫ）の境界上に第１の点ライトアローｗ０を発見することである。所与のベクトル
【数３６】
2008503008.tif 000038
の場合には、超平面ライトアローｗ・ライトアローｘ＝１は、１／ｘｔが超平面とｔ軸の交点になるように一意に決まる。それ故、問題（Ｍ１）に対してライトアローｘが実行可能な場合には、多面体＋（ライトアローｗ１,..., ライトアローwＫ）は、対応する超平面の下に位置していなければならない。何故なら、ライトアローｗｋ・ライトアローｘは各ｋに対して１以下でなければならないからである。この超平面を実行可能な超平面と呼ぶことにする。ライトアローｗを通る超平面を実行可能なものにするために、ライトアローｗは多面体のある面上に位置していなければならない。何故なら、そうでなければ、多面体が超平面の下に来ないからである。このことは、任意のベクトルライトアローｗｋの場合、（Ｍ１）内の対応する制約が束縛するものである場合には、その制約は同じ面上に位置していなければならないことを意味する。
【００５０】
（Ｄ３）の目的関数Σｔ√ｗｔの勾配は、（１／√ｗ１,...,１／√ｗＴ）／２である。これらの勾配は、図２の矢印が示す。グラフの鎖線は、垂線が下式で表されるｗ２を通る超平面を表す。
【数３７】
2008503008.tif 000039
【００５１】
この超平面は、Σｔ（ｗｔ−ｗｔ２）／√ｗｔ２＝０で表すことができる。全多面体がこの超平面以下に位置する場合には、ライトアローｗ２は最適解である。何故なら、ライトアローｗ２から改善する方向はどこにもないからである。この超平面をｗ最適超平面と呼ぶ。何故なら、この超平面がライトアローｗが最適解であるかどうかを決めるからである。それ故、任意のライトアローｗに対して、対応するｗ最適超平面が実行可能な超平面である場合には、ライトアローｗが最適解となる。一方、ライトアローｗを最適なものにするために、全多面体は、その対応するｗ超平面の下に位置していなければならない。上記観察により、下記の副命題が得られる。
【００５２】
副命題３．（Ｄ３）の最適解は、下式で表す場合だけ、ｗ０のところで達成される。
【数３８】
2008503008.tif 000040
【００５３】
意見４．その加重サービス要件ベクトルがライトアローｗ１であるジョブ・クラスを１つだけ含む場合を考えてみよう。超平面ライトアローｗ・ライトアローｘ＝１（但し、
【数３９】
2008503008.tif 000041
）は、ｗ最適超平面である。それ故、
【数４０】
2008503008.tif 000042
がもとの問題（Ｍ１）への最適な割当てとなる。
【００５４】
最適双対解の場合には、ｓｋ＞０である場合には、（Ｍ１）内の対応する制約が拘束力を有し、クラスｋに対する平均応答時間制約が喪失するのを避けるために、ライトアローｗｋがなんらかの増大をした場合には、容量を増大しなければならない。それ故、ｓｋ＞０であるこれらのクラスをボトルネック・クラスと呼ぶことにする。問題（Ｄ２）の最適解
【数４１】
2008503008.tif 000043
は、ボトルネック・クラスの相対的に厳格なレベルを反映していて、
【数４２】
2008503008.tif 000044
は、ボトルネック・クラスに対するプールした等価のサービス要件である。すべてのクラスに対する平均エンド・ツウ・エンド応答時間制約を満足させる最適な容量の割当ては、この等価のボトルネック（仮想）クラスに対する最適な容量の割当てを発見するのと同じことである。
【００５５】
定理５．ライトアローｗ０が問題（Ｄ３）の最適解であると仮定した場合、それが下記の最適化問題の最適解である場合だけ、ライトアローｘは（Ｍ）の最適解である。
【数４３】
2008503008.tif 000045
【００５６】
このことは、下記のように証明することができる。最初に、目的関数の凸部の形が厳しいので、（Ｐ）は一意の解を有さなければならない。
【００５７】
１つの制約を有する最適化問題（Ｐ）への最適解
【数４４】
2008503008.tif 000046
は、下式により表すことができる。
【数４５】
2008503008.tif 000047
これをチェックするために、ｓ０を１つの制約に対応する双対変数（dual variable）としよう。この場合、（１１）から下式が得られる。
【数４６】
2008503008.tif 000048
相補緩み制約（１２）はΣｔｗｔ０ｙｔ＝１になる。ｓ０＝（Σｔ√ｗｔ１）２のように設定すると、（１７）が得られる。
【００５８】
ここで、ライトアローｗ０をｓｋで表すと、（Ｄ１）の解は下式で表される。
【数４７】
2008503008.tif 000049
ここで、第２の等式は最適条件（１１）からのもので、最後の等式は命題１に基づくものである。
【００５９】
この式を（１７）に代入すると、下式が得られる。
【数４８】
2008503008.tif 000050
【００６０】
この節を終わるに当たって、２つの最も簡単なシステム、一層システムおよび二層システムについて考察する。Ｔ＝１がｘ１＝１／ｍａｘｋｗ１ｋである場合に、割当て問題への最適解は簡単である。下記の定理は、二層システムに対する最適容量割当てを示す。
【００６１】
定理６．二層システムについて考えてみよう。下式となると仮定しよう。
【数４９】
2008503008.tif 000051
もし
【数５０】
2008503008.tif 000052
である場合には、最適な容量割当ては下式で表される。
【数５１】
2008503008.tif 000053
そうでない場合、
【数５２】
2008503008.tif 000054
を、
【数５３】
2008503008.tif 000055
および
【数５４】
2008503008.tif 000056
となるような多面体の境界上の
【数５５】
2008503008.tif 000057
に接続している｛ｗ１,...,ｗＫ｝の頂点としよう。その場合には、問題（Ｍ）に対する最適解は下式のようになる。
【数５６】
2008503008.tif 000058
ここで、
【数５７】
2008503008.tif 000059
およびｗ２＝θ２ｗ１である。
【００６２】
このことは下記のように証明することができる。第１の部分は副命題３および定理５から直ちに得られる。第２の部分の場合には、
【数５８】
2008503008.tif 000060
が
【数５９】
2008503008.tif 000061
および
【数６０】
2008503008.tif 000062
の両方を通過する境界に沿った最良点であることに留意されたい。それ故、それは最適なものでなければならない。
【００６３】
４．テール分布保証
この節においては、テール分布保証制約（２）を含む容量立案問題を考察する。この問題は下式のように定式化することができる。
【数６１】
2008503008.tif 000063
第２節のところですでに説明したように、各クラスｋに対して、定常状態のエンド・ツウ・エンド応答時間Ｒｋは、確率的には、Ｍ／Ｇ／１  ＰＳキューである各層のところの定常状態の遅延の合計に等しい。それ故、テール確率保証を研究するために、最初にＰＳキューの応答時間のテールの行動を理解する必要がある。ここで、層ｔＲｔｋのところのクラスｋの遅延は分布関数
【数６２】
2008503008.tif 000064
に従うものと仮定する。Ｒｔｋの分布は、他の層のところの容量割当てに依存しないことに留意されたい。
【００６４】
それ故、各層のところの遅延は独立しているので、各クラスｋに対して、制約（１８）の左辺は、クラスｋジョブが行ったすべての層上のｙに関するＧｔｋのコンボルーションにより計算することができる。コンボルーションの後で、制約（１８）の左辺は、容量割当てベクトルライトアローｃ＝（ｃ１，ｃ２,..., ｃＴ）の関数として表される。それ故、問題（Ｔ）は、非線形プログラムになる。しかし、（ラプラス変換を除いて）ＰＳの下には応答時間テール分布に対する閉の形の式はなく、それ故、ライトアローｃの関数として（１８）の左辺に対して閉の形の式を入手することはほとんど不可能である。いくつかの場合でも、この式（または近似）を使用することができるが、この式は、通常、非常に複雑な関数であり、非線形問題を解くのが難しくなる。それ故、当然、優れた近い最適解および／または境界を探すことになる。
【００６５】
本発明によれば、制約（１８）を近似することにより、上限および下限を入手し、問題（Ｔ）のほぼ最適解が得られる。実際、分布関数Ｇｔｋについてのいくつかの仮定の下では、この解が漸近的に最適であることが証明されている。
【００６６】
４．１．下限
問題（Ｔ）に対する下限を入手するために、制約（１８）を緩和したいと思う。下記の副命題は（１８）を緩和するための簡単な方法を示す。
【００６７】
副命題７．すべてのクラスに対するエンド・ツウ・エンド遅延Ｒｋが制約（２）を満足させる場合には、下式のようになる。
【数６３】
2008503008.tif 000065
【００６８】
このことは下記のように証明することができる。各ｋ、ｔに対して、
【数６４】
2008503008.tif 000066
および
【数６５】
2008503008.tif 000067
であるので、下式のようになる。
【数６６】
2008503008.tif 000068
【００６９】
副命題７は、基本的には、エンド・ツウ・エンド遅延についてのテール分布保証が満足する場合には、これらの保証は各層のところの遅延に対して満足すると述べている。それ故、制約（２）を（１９）で置換することにより、下記の問題（Ｔ）に対する下限を入手することができる。
【００７０】
定理８．Σｔｆｔ（ｃｔ＊）は問題（Ｔ）の下限である。この場合、下式のようになる。
【数６７】
2008503008.tif 000069
【００７１】
４．２．実行可能な解および上限
（２０）により入手した解ライトアローｃは、問題（Ｔ）に対する下限を示すが、問題（Ｔ）に対しては実行不能であり、エンド・ツウ・エンド遅延に関するテール分布要件を保証しない。問題（Ｔ）に対する実行可能な解を入手するために、最初にランダム変数Ｒｔ，ｎｋをＲｔｋのｎ個の独立コピーの合計であると定義する。
【数６８】
2008503008.tif 000070
はクラスｋジョブ（ｋ＝１,...,Ｋ）が行く層の組を示し、Ｔｋは組
【数６９】
2008503008.tif 000071
の層の総数を示す。クラスｋジョブが、層ｔに行かなかった場合には、Ｒｔｋ＝０と設定することに留意されたい。さらに、下記のように仮定する。
【００７２】
仮定１．各クラスｋに対して、下式の場合には、
【数７０】
2008503008.tif 000072
下式のようになる。
【数７１】
2008503008.tif 000073
【００７３】
任意の固定のクラスｋに対して、すべてのＲｔｋが確率的順序方向１≦ｔ≦Ｔに比較できる場合には、仮定１は満足する。Ｘ≦ｓｔＹまたはＹ≦ｓｔＸである場合には、ＸおよびＹは、確率的順序方向≦ｓｔに比較することができる。実際、この場合、各固定クラスｋに対して、応答時間Ｒｔ＊ｋが確率的に他のものを支配するようにボトルネック層ｔ＊が存在する。そのため、
【数７２】
2008503008.tif 000074
は
【数７３】
2008503008.tif 000075
であることを意味する。特に、任意の固定クラスｋに対して、Ｒｔｋがすべて指数ランダム変数である場合、またはすべて同じ形のパラメータを含むワイブル・ランダム変数である場合には、これらを確率的に比較することができる。また、任意の固定クラスｋに対して、Ｓｔｋが分布において同じである場合には、結合引数により、Ｒｔｋが確率的に比較することができることを証明することができる。
【００７４】
Ｇｔ，ｎｋ（ｃ，ｙ）がｙに関してＧｔｋ（ｃ，ｙ）のｎ番目のコンボルーションであると定義すると、下式のようになる。
【数７４】
2008503008.tif 000076
【００７５】
下記の定理は、問題（Ｔ）に対する実行可能な解を示す。
【００７６】
定理９．仮定１が成立すると仮定する。
【数７５】
2008503008.tif 000077
は、問題（Ｔ）に対して実行することができる。それ故、テール分布制約を保証する。この場合、
【数７６】
2008503008.tif 000078
となり、下式のようになる。
【数７７】
2008503008.tif 000079
また、Σｔｆｔ（ｃ＊ｔ）は、問題（Ｔ）に対する上限である。
【００７７】
このことは下記のように証明することができる。ｃ＊ｔの割当ての下で（１８）が満足するのを証明するにはこれで十分である。最初に、ｃ＊ｔの定義により、各ｔおよびｋに対して下式のようになることを容易に理解することができる。
【数７８】
2008503008.tif 000080
ここで、Ｋｔは、層ｔのところでサービスを受ける必要がある一組のジョブ・クラスを示す。これは（２１）と同じものである。それ故、（１８）は仮定１に従う。
【００７８】
４．３．漸近的最適性
この節においては、第４．１節および第４．２節ですでに説明した解の効果について説明する。そのために、下記の簡単にするための仮定を行う。
仮定２．各クラスｋおよび各層ｔに対して下式のようになる。
【数７９】
2008503008.tif 000081
【００７９】
（２５）は近似に過ぎないことに留意されたい。サブ指数的サービス時間を含むＭ／Ｇ／１  ＰＳキューの場合、Ｆｔｋがｅ−√ｙより重いテールを有している場合には、上記仮定は、大きなｙに対して漸近的に真であることが証明されている。この場合、Ｆｔｋは、層ｔのところのクラスｋジョブに対する公称サービス要件ランダム変数Ｓｔｋに対する分布関数である。それ故、仮定２の下で、下式のようになる。
Ｇｔｋ（ｃ，Ｕｋ）＝Ｆｔｋ（（ｃ−ｑｔ）Ｕｋ）
この式は、公称サービス時間分布の関数として、（２０）の下限を示す方法を示す。さらに、Ｆｔｋの相補を
【数８０】
2008503008.tif 000082
であるとした場合、および
【数８１】
2008503008.tif 000083
の逆関数が下式となることが分かった場合には、下式のようになる。
【数８２】
2008503008.tif 000084
（２０）の下限を下式で表すことができる。
【数８３】
2008503008.tif 000085
【００８０】
Ｆｔ，ｎｋをＦｔｋのｎ番目のコンボルーションとして示し、相補
【数８４】
2008503008.tif 000086
を示す。それ故、上記引数により、（２３）の上限を下式のように簡単にすることができる。
【数８５】
2008503008.tif 000087
ここで、
【数８６】
2008503008.tif 000088
である。
【００８１】
仮定３．各ｋ、ｔに対して下式のようにκ０＜∞およびδ０＞０が存在する。
【数８７】
2008503008.tif 000089
および任意のδ１＞０に対して下式のようになる。
【数８８】
2008503008.tif 000090
【００８２】
指数分布およびワイブル分布の両方は、仮定３を満足させる。特に、両方の場合に対して下式のようになる。
【数８９】
2008503008.tif 000091
一方、パレート分布の場合には、仮定３は成立しない。
【００８３】
命題１０．仮定３が成立する場合には、下式のようになる。
【数９０】
2008503008.tif 000092
【００８４】
このことは下記のように証明することができる。仮定３により、任意のδ＞０に対して、任意のｙ≧ｙ０に対して下式になるように、ｙ０＞０が存在する。
【数９１】
2008503008.tif 000093
および
【数９２】
2008503008.tif 000094
それ故、任意のｙ≧ｙ０に対して下式のようになる。
【数９３】
2008503008.tif 000095
ここで
【数９４】
2008503008.tif 000096
としよう。その場合には、任意の∈＜∈０に対して、φｋ，ｔ（∈）≧ｙ０となる。
【００８５】
それ故、下式のようになる。
【数９５】
2008503008.tif 000097
【００８６】
テール分布関数は単調なものでり、下式で表されるので、
【数９６】
2008503008.tif 000098
下式のようになる。
【数９７】
2008503008.tif 000099
それ故、結果は下記のようになる。
【００８７】
命題１０が、すべてのｋに対してεｋ→０になるにつれて、各ｔに対してｃ＊ｔ／ｃｔ＊→１になることを意味することは容易に理解できる。これにより下記の漸近的結果が生じる。
【００８８】
定理１１．仮定（１−３）が成立するなら、（２０）および（２３）により得る解は、すべてのｋに対してεｋ→０になるにつれて、各ｔに対してｃ＊ｔ＝ｃｔ＊→１になるという意味で漸近的に最適になる。
【００８９】
実際には、上記定理が成立するには、すべてのｋに対してεｋが０になる必要はない。それどころか、以下に説明するように、最低のεｋが０になるだけでよい。
【００９０】
推論１２．仮定（２−３）が成立し、任意の０≦ｙ≦∞に対して、Ｆｔｋ（ｙ）≧δになるようなδ＞０が存在する場合には、（２３）により入手した解は、ε０＝ｍｉｎｋεｋである場合に、ε０→０であるという意味で漸近的に最適なものである。
【００９１】
このことは下記のように証明することができる。各層ｔについて、下記のように定義する。
【数９８】
2008503008.tif 000100
および
【数９９】
2008503008.tif 000101
さらに、下式のようになるとしよう。
【数１００】
2008503008.tif 000102
および
【数１０１】
2008503008.tif 000103
その場合には、下式のようになる。
【数１０２】
2008503008.tif 000104
【００９２】
命題１０から、ε０→０になる場合に、各ｔに対して
【数１０３】
2008503008.tif 000105
となり、εｋｔ→０となることを証明するのに十分である。κ＝ｍａｘｋＵｋ／ｍｉｎｋＵｋであるとしよう。任意のδ＞０の場合には、ｙ１＝ｍａｘｋ，ｔφｔｋ（δ）のように設定し、
【数１０４】
2008503008.tif 000106
である。ここで、最初に、任意の｛εｋ：１≦ｋ≦Ｋ｝の場合、ε０≦∈１であれば、εｋｔ→δとなることを証明する。ｋ０＝ａｒｇｍｉｎｋεｋであるとしよう、その場合、φｋ０，ｔ（ε０）≧φｔｋ０（∈１）≧κｙ１となる。一方、ｋｔの定義により、下式のようになる。
【数１０５】
2008503008.tif 000107
それ故、下式のようになる。
【数１０６】
2008503008.tif 000108
この式は、εｋｔ≦δであることを意味する。同様に、
【数１０７】
2008503008.tif 000109
であることを確認することができる。
【００９３】
意見１３．パレット分布は、仮定３を満足させないし、漸近的結果は成立しない。しかし、前の節で得られた境界の比率は、ε０が０になると一定の係数により制約される。
【数１０８】
2008503008.tif 000110
の場合には、２１／ａにより制約される。この場合、ａ＝ｍｉｎｋ，ｔａｔｋである。
【００９４】
４．４．例：指数的な場合
各層Ｒｔｋのところの応答時間が指数的に分布している場合、すなわち
【数１０９】
2008503008.tif 000111
である場合を考察する。この場合には、γｎ（∈）は、パラメータ（ｎ，１）を含むガンマ・テール分布関数の逆数であることを示し、その場合、φｔｋ（∈）＝ｍｔｋγ１（∈）であり、γｔ，τｋ（ε）＝ｍｔｋγτ（∈）である。それ故、下式のようになる。
【数１１０】
2008503008.tif 000112
この式は、問題（Ｔ）の実行可能な解であり、Σｔｆｔ（ｃ＊ｔ）は（Ｔ）の最適解の上限である。同様に、目標値Σｔｆｔ（ｃｔ＊）を含む解は、
【数１１１】
2008503008.tif 000113
問題（Ｔ）の下限を示す。この場合には、下式のようになる。
【数１１２】
2008503008.tif 000114
すなわち、最適性比率は、Ｔおよびεだけに依存する定数により制約を受ける。そのため下記の定理が得られる。
【００９５】
定理１４．応答時間｛Ｒｔｋ，１≦ｔ≦Ｔ｝が独立していて、各クラスに対して同じように分布している指数ランダム変数である場合には、（３４）および（３５）は、それぞれ上限および下限を示す２つの解である。さらに、最適性比率は、Ｔおよびεだけに依存する定数であるｍａｘｋγＴ（εｋ）／γ１（εｋ）により制約される。
【００９６】
指数的な場合に対して仮定（１−３）が満たされるので、前の節で入手した漸近的結果が成立する。
【００９７】
推論１５．応答時間｛Ｒｔｋ，１≦ｔ≦Ｔ｝が独立していて、各クラスに対して同じように分布している指数ランダム変数である場合には、（２３）により入手した解は、漸近的に最適である。
【００９８】
５．平均保証およびテール保証
両方の制約（１）および（２）を満足させるために必要な最低容量は、下記の問題を解くことにより入手される。
【数１１３】
2008503008.tif 000115
【００９９】
問題（Ｔ）と同様に、テール分布制約が問題を難しくする。第４節で行ったように仮定１が成立するものと仮定してこれらの制約を置換した場合には、下記の問題を解くことにより実行可能な解を入手することができる。
【数１１４】
2008503008.tif 000116
または、下記の問題を解くことにより、最適解の下限を入手することができる。
【数１１５】
2008503008.tif 000117
【０１００】
定理１６．仮定１の下では、下記のことが成立する。
（ｉ）（Ｃ１）に対する任意の実行可能な解を（Ｃ）に対して実行することができる。
（ｉｉ）（Ｃ）に対する最適解を（Ｃ２）に対して実行することができ、（Ｃ２）に対する最適解は、（Ｃ）に対する解に対する下限を示す。
（ｉｉｉ）仮定（２−３）の下では、（Ｃ１）および（Ｃ２）ｘ＊およびｘ＊に対する最適解は、すべてのｋに対してεｋ→０になるにつれて、各ｔに対して（ｘ＊）ｔ＝ｘｔ＊→１になるという意味で漸近的に最適である。
【０１０１】
このことは、上記定理９、８および１１から直接証明することができる。
【０１０２】
６．数字による結果
この節においては、本発明の近似方法の性能を証明するために数字による結果を使用する。これらの近似解が、最適解とどれくらい似ているか、性能がシステム・パラメータによりどんな影響を受けるかを証明する。また、近似性能に対する平均エンド・ツウ・エンド遅延制約の影響も調査する。最後に、いくつかの実験を通して、第３節で入手した最適解が堅牢なものであることを証明する。
【０１０３】
６．１．近似性能
この節全体を通して、各クラスに対する各層内の応答時間は、指数的に分布していて、簡単にするために、すべてのクラスが同じテール分布要件εを有するものと仮定する。最初に、エンド・ツウ・エンド応答時間テール要件だけを含み、平均遅延要件は含んでいないシステムについて考察する。第４節においては、最適な全コストの上限（ＵＢ）を入手するための実行可能な解、および最適な全コストの下限（ＬＢ）のための解を説明した。図３、図４および図５は、それぞれ、異なるテール分布要件ε、異なる数の層Ｔ、および異なる数のクラスＫに対してこれら２つの限界がどのように作用するのかを示す。各図面は、最適解に対する上限（ＵＢ）の比率（ＵＢ比率）、最適解に対する下限（ＬＢ）の比率（ＬＢ比率）、およびＬＢに対するＵＢの比率（最適性比率）を示す３つの曲線からなる。
【０１０４】
これらの図面から、最初に、異なるε、ＴおよびＫに対してＵＢ比率が非常に安定していることが分かる。その値はほとんどの場合、約１．２〜１．３である。それ故、第４節で説明した実行可能な解を近似すると、可能な最適解に匹敵する合理的なコストになる。クラスの数が変化しても下限（ＬＢ）の性能は非常に安定しているが、層の数が増大したり、テール分布保証の厳しさが低減すると（εが増大すると）、この性能は劣化する。ＬＢに対するＵＢの比率（最適性比率）は、εまたはＴが低減すると低減する傾向を示す。
【０１０５】
テール分布制約の他に、平均エンド・ツウ・エンド応答時間制約を適用すると、ＬＢに対するＵＢの比率が低減し、この比率は平均制約がより厳格になると低減する。
【０１０６】
テール分布条件を自動的に満たすように平均制約が極度に厳しくなると、この比率は１に等しくなる。表１〜表６（図６Ａ〜図６Ｆ）は、それぞれ、平均制約およびテール制約の両方が行われている場合、ε、ＴおよびＫの異なる値の場合の限界を示す。比較のためにテール分布制約だけの場合の限界も示してある。この場合、テール分布要件Ｕｋに対するエンド・ツウ・エンド応答時間の閾値は、平均エンド・ツウ・エンド応答時間の閾値
【数１１６】
2008503008.tif 000118
の２倍に設定される。いくつかの例の場合、平均制約を追加すると、下限が非常に有意に増大することが分かる。しかし、εが小さい場合には、すべての平均エンド・ツウ・エンド応答時間の制約が自動的に満たされ、問題はテール制約だけを含むものになる。この場合、上限および下限の両方は、平均エンド・ツウ・エンド応答時間の制約の追加により影響を受けない。
【０１０７】
６．２．堅牢さ
１つの実際的な関心事は、平均サービス時間要件ｍｔｋは、通常、ある種の測定および予測機構から入手されることである。誤差は、測定および予測にはつきものである。それ故、全容量を最小限度に低減するばかりでなく、予測したパラメータから入力パラメータが若干ズレた場合でも、大部分のエンド・ツウ・エンド応答時間制約が依然として満たされるような方法で容量の割当てを行うことが望ましい。すなわち、この解は、データが不確かな場合でも堅牢でなければならない。分かり易くするために、平均エンド・ツウ・エンド応答時間の制約だけを考慮した場合の堅牢さの結果だけを示す。
【０１０８】
第３節においては、サービス時間要件がある不確かさを有していて、ボトルネック・クラスの数がＴより小さい場合に、これらのボトルネックでないクラスに対する制約が、ボトルネック・クラスより違反する可能性が少ないことについて注目する。それ故、層の数が少ない場合には、（Ｍ）問題の最適解は非常に堅牢であると予想する。数字の例によりこのことを証明するために、
【数１１７】
2008503008.tif 000119
は以降ｗハットｔｋと記載する
は、［ｗｔｋ（１−Δ），ｗｔｋ（１＋Δ）］内で均一に分布していると見なす。この場合、Δは、ｗｔｋについての予測の不確実性がどの程度のものであるかを測定する。表４および表５は、Ｋ、ＴおよびΔが異なる場合で、本当の入力パラメータが（ｗハットｔｋ）であるが、容量を予測したパラメータ（ｗｔｋ）を含む問題（Ｍ）の最適解に基づいて割り当てた場合の制約違反の平均（１００のサンプルについて）数を示す。この場合、各層内の公称サーバ使用の予測ｑｔは正確なものであると仮定する。この解の堅牢さは非常に満足すべきものである。何故なら、表４および表５内のすべての値が小さいからである。このことは、容量を割り当てるために（Ｍ）の解を使用した場合には、パラメータが予測したものより２５％ズレた場合でも、非常に少ないクラスしかその平均エンド・ツウ・エンド遅延閾値を超えないことを意味する。
【０１０９】
各行および／または列に沿って表の値をチェックすると、制約違反の平均数がΔ、ＴおよびＫによりどのような影響を受けるかが分かる。不確実性のレベルΔまたは層の数Ｔが増大すると、若干より多くのクラスが予測しなかった長いエンド・ツウ・エンド遅延を起こす。しかし、システムのクラスの全数Ｋは、その平均応答時間制約が違反を起こしたクラスの数に大きな影響を与えない。
【０１１０】
表６は、入力パラメータが（ｗｔｋ）および（ｗハットｔｋ）である場合の問題の最適目標値の相対的な違いを示す。表６は、パラメータ（ｗｔｋ）または（ｗハットｔｋ）に基づいて立案した場合、全コストが大きく変化しないことを示す。
【０１１１】
７．非ゼロｓｋの数に基づくケースの説明
ここで、相補緩み制約（１２）内の非ゼロｓｋの数に依存する可能なケースについて説明する。明らかに、ｓｋすべてがゼロであるわけではない。
１つの非ゼロｓｋ：
非ゼロｓｋが正確に１つである場合には、ｓ１≠０およびｓ２＝．．．＝ｓＫ＝０であると仮定する。この場合、（１１）から下式が得られる。
【数１１８】
2008503008.tif 000120
相補緩み制約（１２）は下式のようになる。
【数１１９】
2008503008.tif 000121
この場合、下式のように設定する必要がある。
【数１２０】
2008503008.tif 000122
ライトアローｘに対する解は下式のようになる。
【数１２１】
2008503008.tif 000123
また、目標値は下式のようになる。
【数１２２】
2008503008.tif 000124
【０１１２】
もとの問題が１つの制約しか有していない場合には、上式は最適解を示す。もとの問題の制約が２つ以上である場合には、実行可能性の制約をチェックする必要がある。解ライトアローｘが実行可能性の制約（８）を満足させる場合には、その解は最適解である。実行可能性の制約（８）を保証するためには、下式を満足させなければならない。
【数１２３】
2008503008.tif 000125
この式は下式と同じものである。
【数１２４】
2008503008.tif 000126
非ゼロｓｋがＴ個である場合：
非ゼロｓｋの数が正確にＴ個であると仮定する。このことは、クラスの数Ｋが層の数Ｔより大きいかまたは等しいこと（Ｋ≧Ｔ）を意味する。ｓｋｊ≠０（ｊ＝１,...,Ｔ）であると仮定しよう。さらに、対応するベクトル
【数１２５】
2008503008.tif 000127
が直線的に独立していると仮定しよう。このことは一組の式
【数１２６】
2008503008.tif 000128
に対して一意の解ライトアローｘ０が存在することを意味する。ベクトル
【数１２７】
2008503008.tif 000129
を通過する一意の超平面は、ライトアローｘ０・ライトアローｘ＝１で表すことができる。このことは式にｘとしてｊ＝１,...,Ｔに対して
【数１２８】
2008503008.tif 000130
を挿入することにより容易にチェックすることができる。この超平面とｔ軸との交点が１／ｘｔ０である。この交点は超平面の式にｘｊ＝０（ｊ＝１,...,Ｔ，ｊ≠ｔ）を割り当てることにより入手できる。すべての軸との交点の合計が正確に目的関数であることが分かる。
【０１１３】
次に、任意の実行可能なライトアローｘに対する拘束制約に対応するベクトルライトアローｗｋは、同じファセット上に位置しなければならないことを証明する。このことは矛盾により証明することができる。
【０１１４】
ｘ１,...,ｘＴを入手し、ライトアローｘ≧０であることを確認した後で、相補緩み制約（１２）に基づいてＫ−Ｔｓｋをゼロに設定しなければならない。残りのＴｓｋは、最適性条件（１１）から入手することができる。すべてのｓ１,..., ｓＫが負でない場合には、解ｘ１,..., ｘＴおよびｓ１,..., ｓＫが最適解である。
【０１１５】
８．例示としての設計システムおよび方法
上記の原理に基づいて、最適化問題（Ｍ１）を解くための下記の例示としてのアルゴリズムが得られる。
アルゴリズムＩ：
ステップ１：
【数１２９】
2008503008.tif 000131
であるとしよう。
ステップ２：すべてのｋ＝１,...,Ｋに対して
【数１３０】
2008503008.tif 000132
であるならば、停止する。最適解
【数１３１】
2008503008.tif 000133
を戻す。
そうでない場合には、
【数１３２】
2008503008.tif 000134
として、ステップ３へ行く。
ステップ３：下式を解く。
【数１３３】
2008503008.tif 000135
また、
【数１３４】
2008503008.tif 000136
と設定する。この場合、ｓ＊は、（４３）の解である。
【０１１６】
それ故、上記本発明の原理の詳細な説明により、そのような方法を実施するための例示としての方法および設計システムについて以下に説明する。しかし、本発明はこのような説明に限定されないことを理解されたい。
【０１１７】
ここで図７を参照すると、この図は、上記本発明の例示としての原理による平均分布保証およびテール分布保証両方に対する下限を決定するためのプロセスを示す流れ図である。
【０１１８】
図に示すように、プロセス７００は下記のような動作を行う。
【０１１９】
ステップ７１０において、入力パラメータを入手する。各クラスｋ、分布関数Ｆｔｋ、および層ｔのところの公称サービス時間の平均ｍｋに対して、エンド・ツウ・エンド遅延サービス要件（Ｖｋ，Ｕｋ，εｋ）を入手する。各層ｔに対して、公称トラフィック量ｑｔおよび容量コスト関数ｆｔ（ｃ）を入手する。
【０１２０】
ステップ７２０において、各ｋ、ｔに対して、プロセスがφｔｋ＝ｍｉｎ｛ｙ：Ｆｔｋ（ｙ）≧１−εｋ｝を計算する。
【０１２１】
ステップ７３０において、プロセスはｇｔ（ｘｔ）＝ｆｔ（ｑｔ＋１／ｘｔ）を定義し、下式を解く。
【数１３５】
2008503008.tif 000137
【０１２２】
上記問題は、（Ｍ１）のフォーマットに変換することができ、次にアルゴリズムＩにより解くことができることに留意されたい。
【０１２３】
最後に、ステップ７４０において、ステップ７３０における上記問題の最適目標値が容量割当て問題の下限を示す。
【０１２４】
ここで図８を参照すると、この図は、上記本発明の例示としての原理による平均分布保証およびテール分布保証の両方に対する上限を決定するためのプロセスを示す流れ図である。
【０１２５】
図に示すように、プロセス８００は下記のような動作を行う。
【０１２６】
ステップ８１０において、入力パラメータを入手する。各クラスｋ、分布関数Ｆｔｋ、層ｔのところの公称サービス時間の平均ｍｋに対して、エンド・ツウ・エンド遅延サービス要件（Ｖｋ，Ｕｋ，εｋ）を入手する。各層ｔに対して、公称トラフィック量ｑｔおよび容量コスト関数ｆｔ（ｃ）を入手する。
【０１２７】
ステップ８２０において、各ｋ、ｔに対して、プロセスがＦｔ，Ｔｋ、すなわちＦｔｋのＴ番目のコンボルーションを入手する。
【０１２８】
ステップ８３０において、各ｋ、ｔに対して、プロセスがφｔｋ＝ｍｉｎ｛ｙ：Ｆｔｋ（ｙ）≧１−εｋ｝を計算する。
【０１２９】
ステップ８４０において、プロセスが、ｇｔ（ｘｔ）＝ｆｔ（ｑｔ＋１／ｘｔ）を定義し、下式を解く。
【数１３６】
2008503008.tif 000138
【０１３０】
この場合も、上記問題を（Ｍ１）のフォーマットに変換することができ、次にアルゴリズムＩにより解くことができる。
【０１３１】
最後に、ステップ８５０において、ステップ８４０における上記問題の最適目標値が、容量割当て問題への上限を示す。解ｘｔの場合には、１／ｘｔ＋ｑｔが層ｔに対する実行可能な容量割当てである。
【０１３２】
ここで図９を参照すると、この図は、本発明のある実施形態による容量割当てを計算するための設計システムを示すブロック図である。通常、設計システム９００は、例えば、図７のステップ７１０および図８のステップ８１０に示すように、入力として容量割当て入力パラメータを受信する。次に、本明細書に記載する１つまたは複数の容量割当て方法（例えば、アルゴリズムＩにより定式化した図７のプロセス７００および図８のプロセス８００）が、容量割当て結果（すなわち、コストを最小限度まで低減し、エンド・ツウ・エンド性能を保証するために、入力シナリオによる容量の割当て方法）を計算するために使用される。
【０１３３】
設計システム９００は、スタンドアローンの計算システムであってもよいし、結果を計算するネットワークの１つまたは複数のコンポーネントと動作できるように接続することもできる。設計システム９００が計算した結果は、自動的に実施することもできるし、および／または効率的に設計されたネットワークを実現するために手動により実施することもできる。
【０１３４】
ここで図１０を参照すると、この図は、本発明のある実施形態による容量割当てを計算するための設計システムを実行するのに適しているコンピュータ・システムの一般的なハードウェア・アーキテクチャを示すブロック図である。より詳細に説明すると、図９の設計システム９００は、本発明の方法を実行するためにこのようなコンピューティング・システム１０００を実施することができることを理解されたい。また、１つまたは複数のシステム・コンポーネント（例えば、設計中のネットワーク内の）は、このようなコンピューティング・システム１０００を実施することができる。もちろん、本発明が特定のコンピューティング・システムの実施態様に限定されないことを理解されたい。
【０１３５】
この例示としての実施態様の場合には、本発明の方法の少なくとも一部を実施するためのプロセッサ１０１０は、バス１０５０または代わりの接続装置を介してメモリ１０２０、入出力（Ｉ／Ｏ）装置１０３０、およびネットワーク・インタフェース１０４０と動作できるように結合している。
【０１３６】
本明細書で使用する場合、「プロセッサ」という用語は、例えば、中央処理ユニット（ＣＰＵ）および／または他の処理回路（例えば、デジタル信号プロセッサ（ＤＳＰ）、マイクロプロセッサ等）を含むデバイスのような任意の処理デバイスを含むことを理解されたい。さらに、「プロセッサ」という用語は、２つ以上の処理デバイスを指すことができること、および処理デバイスに関連する種々の素子を他の処理デバイスと共有することができることを理解されたい。
【０１３７】
本明細書で使用する場合、「メモリ」という用語は、メモリ、および例えば、ランダム・アクセス・メモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、固定記憶媒体（例えば、ハード・ドライブ）、取外し可能な記憶媒体（例えば、ディスケット）、フラッシュ・メモリ等のようなプロセッサまたはＣＰＵに関連する他のコンピュータ読み取り可能媒体を含む。
【０１３８】
さらに、本明細書で使用する場合、「Ｉ／Ｏ装置」という用語は、処理ユニットにデータを入力するための１つまたは複数の入力装置（例えば、キーボード、マウス等）、および処理ユニットに関連する結果を提供するための１つまたは複数の出力装置（例えば、ＣＲＴディスプレイ等）を含む。このような入力装置は、設計結果を生成するために、ユーザが本発明の設計システムが使用する設計入力を供給するための１つの機構であってもよいことを理解されたい。別の方法としては、設計入力は、ディスケットから、またはコンピュータ・バス１０５０に接続しているある他のソース（例えば、他のコンピュータ・システム）から設計システム内に読み込むことができる。また、設計方法への入力も、１つまたは複数の入力装置により入手することができる。出力装置は、設計方法の結果を提示するユーザまたは他のコンピュータ・システムのための１つの機構であってもよい。
【０１３９】
さらに、本明細書で使用する場合、「ネットワーク・インタフェース」という用語は、例えば、コンピューティング・システム１０００が他のコンピュータ・システムと通信することができるようにすることができる１つまたは複数のデバイスを含む。それ故、ネットワーク・インタフェースは、適当な通信プロトコルにより他のコンピュータ・システムのトランシーバと通信するように構成されているトランシーバを備えることができる。本発明は任意の特定の通信プロトコルに限定されないことを理解されたい。
【０１４０】
設計システムにより本発明を説明してきたが、本発明の方法は、コンピュータ読み取り可能媒体の形で分散することができ、分散のために実際に使用する信号を送る媒体の特定のタイプが何であれ、本発明を実施することができ、その利点を実現することができることを理解されたい。本明細書で使用する場合、「コンピュータ読み取り可能媒体」という用語は、例えば、フレキシブル・ディスク、ハード・ディスク・ドライブ、ＲＡＭ、コンパクト・ディスク（ＣＤ）ＲＯＭ等のような記録することができるタイプの媒体、デジタルまたはアナログ通信リンク、例えば、無線周波および光伝送等のような伝送形態を使用する有線または無線通信リンクのような送信タイプの媒体を含む。コンピュータ読み取り可能媒体は、特定のデータ処理システムで使用するために復号される符号化したフォーマットの形をとることができる。
【０１４１】
それ故、本明細書に記載するように、本発明の方法を実行するための命令またはコードを含む、１つまたは複数のコンピュータ・プログラムまたはそのソフトウェア・コンポーネントは、１つまたは複数の関連する記憶媒体（例えば、ＲＯＭ、固定または取外し可能な記憶装置）に格納することができ、使用できるようになった場合に、（例えば、ＲＡＭ内に）全部または一部をロードすることができ、プロセッサ１０１０により実行することができる。
【０１４２】
いずれの場合でも、本明細書に記載し、添付の図面に示す本発明の技術は、例えば、関連するメモリ、特定実装向け集積回路、機能回路等を含む１つまたは複数の動作できるようにプログラムされた汎用デジタル・コンピュータのような種々の形のハードウェア、ソフトウェアまたはその組合せで実施することができることを理解されたい。本明細書に記載する本発明の技術を使用すれば、通常の当業者であれば本発明の技術の他の実施態様を思い付くことができるだろう。
【０１４３】
本明細書に説明するように、本発明は、エンド・ツウ・エンド性能保証を行う多層環境でリソース割当て問題の有利な解決方法を提供する。より詳細に説明すると、本発明は、各クラスの要求に対してエンド・ツウ・エンド応答時間の平均分布およびテール分布の両方上でサービス保証を行う。この問題を、容量割当てベクトルの凸状の分離可能な関数を最小化するために、非線形プログラムとして説明のために定式化した。最適解に対する構造上の特性および最適性条件を証明した。また、問題の重要な部分を説明するために幾何学的解釈も行った。
【０１４４】
さらに、すでに説明したように、エンド・ツウ・エンド応答時間のテール確率のための要件を含む問題は難しい問題である。適当な仮定の下で、解のための一定の要因を挙げ、また、それが漸近的に最適なものであることを証明した。これらの仮定は非常に一般的なもので、共通の問題を集めることにより容易に満たされる。数字による結果は、さらに、本発明の方法の有利な性能を証明した。
【０１４５】
都合のよいことに、本発明は多層アーキテクチャを解決する。本発明は、また、エンド・ツウ・エンド応答時間の平均分布およびテール分布の両方の制約を解決する。さらに、本発明の解は、ほぼ最適解であり、効率的に入手することができる。本発明の解は堅牢なものである。本発明の解は、サービス要件が不確実な場合でも使用することができる。さらに、本発明の解は、変化する環境に適応するようにオンラインで容易に入手することができる。
【０１４６】
添付の図面を参照しながら本発明の例示としての実施形態について説明してきたが、本発明は、これらの実施形態そのものに限定されないこと、当業者であれば本発明の範囲または精神から逸脱することなしに、種々の他の変更および修正を行うことができることを理解されたい。
【図面の簡単な説明】
【０１４７】
【図１】本発明の例示としての原理を実施することができるフィードフォワード多層システムを示すブロック図である。
【図２】本発明のある実施形態によるある問題の幾何学的解釈をグラフにより示す図面である。
【図３】本発明のある実施形態によるテール分布要件の関数としての近似性能をグラフで示す図面である。
【図４】本発明のある実施形態による層の数の関数としての近似性能をグラフで示す図面である。
【図５】本発明のある実施形態によるクラスの数の関数としての近似性能をグラフで示す図面である。
【図６】本発明のある実施形態による平均制約およびテール制約の両方が存在する場合の異なる値の下の境界を表で示す図面である。
【図７】本発明のある実施形態による平均制約およびテール制約の両方が存在する場合の異なる値の下の境界を表で示す図面である。
【図８】本発明のある実施形態による平均制約およびテール制約の両方が存在する場合の異なる値の下の境界を表で示す図面である。
【図９】本発明のある実施形態による平均制約およびテール制約の両方が存在する場合の異なる値の下の境界を表で示す図面である。
【図１０】本発明のある実施形態による平均制約およびテール制約の両方が存在する場合の異なる値の下の境界を表で示す図面である。
【図１１】本発明のある実施形態による平均制約およびテール制約の両方が存在する場合の異なる値の下の境界を表で示す図面である。
【図１２】本発明の例示としての原理による平均分布保証およびテール分布保証の両方のための下限を決定するためのプロセスを示す流れ図である。
【図１３】本発明の例示としての原理による平均分布保証およびテール分布保証の両方のための上限を決定するためのプロセスを示す流れ図である。
【図１４】本発明のある実施形態による容量割当てを計算するための設計システムを示すブロック図である。
【図１５】本発明のある実施形態による容量割当てを計算するための設計システムを実施するのに適しているコンピュータ・システムの一般的なハードウェア・アーキテクチャを示すブロック図である。
【図１】
2008503008.tif 000139
【図２】
2008503008.tif 000140
【図３】
2008503008.tif 000141
【図４】
2008503008.tif 000142
【図５】
2008503008.tif 000143
【図６】
2008503008.tif 000144
【図７】
2008503008.tif 000145
【図８】
2008503008.tif 000146
【図９】
2008503008.tif 000147
【図１０】
2008503008.tif 000148
【図１１】
2008503008.tif 000149
【図１２】
2008503008.tif 000150
【図１３】
2008503008.tif 000151
【図１４】
2008503008.tif 000152
【図１５】
2008503008.tif 000153
【国際調査報告】
2008503008.tif 000154
2008503008.tif 000155
2008503008.tif 000156