(57)【要約】【課題】容量・フロー割当てにおいて、システムの容量を上回る到着率で処理要求が発生した場合、処理要求のトラヒックが処理サイト側で拒否されて他のサイトに割り振られ、サイト間を接続するネットワークにより大きな負荷が掛ってしまう。【解決手段】各要求サイトが受け入れた処理要求の到着率は、前記各処理サイトにおける前記サーバの使用数と前記所定周期での有効設計容量の積の全処理サイトに関する総和を上回らないという制約条件とを含み、単位時間当たりにおいて、各サイトでの前記サーバの使用数に関する費用の総和と処理要求の拒否により失われる収入の総和との和を最小化する数理計画問題の最適解から、各処理サイトにおいて各要求サイトからの処理要求を専用に処理するサーバの使用数と、要求サイトで処理要求の拒否を行うための受入れ容量と、各要求サイトから各処理サイトへのフロー比率とを決定する。【選択図】図１
2016157272.tif 000002
【特許請求の範囲】
【請求項１】
各要求サイトに到着する処理要求の到着率の所定周期での予測値と、処理要求の要求サイトと前記処理要求の処理サイトと間の、前記所定周期で予測されたネットワーク遅延を用いて算出された各要求サイトからみた各処理サイトのサーバの前記所定周期での有効設計容量とをそれぞれ定数として含み、
各処理サイトにおいて各要求サイトからの処理要求を専用に処理するサーバの使用数と、各要求サイトでの処理要求の拒否に関する量とをそれぞれ変数として含み、
各処理サイトでの前記サーバの使用数の各要求サイトに関する総和は上限を持つという制約条件と、
各要求サイトが受け入れた処理要求の到着率は、前記各処理サイトにおける前記サーバの使用数と前記所定周期での有効設計容量の積の全処理サイトに関する総和を上回らないという制約条件とを含み、
各サイトでの前記サーバの使用数に関する、単位時間当たりの費用の総和と処理要求を拒否することで失われる単位時間当たりの収入の総和との和を目的関数として最小化する数理計画問題の最適解から、
各処理サイトにおいて各要求サイトからの処理要求を専用に処理するサーバの使用数と、要求サイトで処理要求の拒否を行うための受入れ容量と、各要求サイトから各処理サイトへのフロー比率とを決定することを特徴とするコンピュータネットワークシステムの設計方法。
【請求項２】
前記所定周期である第１周期毎に要求サイト毎に与えられる前記サーバの使用数と、
処理要求の要求サイトと前記処理要求の処理サイトと間の、前記第１周期よりも短い第２周期で予測されたネットワーク遅延を用いて算出された、各要求サイトからみた各処理サイトのサーバの前記第２周期での有効設計容量とから、
各要求サイトで処理要求の拒否を行うための受入れ容量と、各要求サイトから各処理サイトへのフロー比率とを決定することを特徴とする、請求項１記載のコンピュータネットワークシステムの設計方法。
【請求項３】
各要求サイトに到着する処理要求の到着率の所定周期での予測値と、処理要求の要求サイトと前記処理要求の処理サイトと間の、前記所定周期で予測されたネットワーク遅延を用いて算出された各要求サイトからみた各処理サイトのサーバの前記所定周期での有効設計容量とをそれぞれ定数として含み、
各処理サイトにおいて各要求サイトからの処理要求を専用に処理するサーバの使用数と、各要求サイトでの処理要求の拒否に関する量とをそれぞれ変数として含み、
各処理サイトでの前記サーバの使用数の各要求サイトに関する総和は上限を持つという制約条件と、
各要求サイトが受け入れた処理要求の到着率は、前記各処理サイトにおける前記サーバの使用数と前記所定周期での有効設計容量の積の全処理サイトに関する総和を上回らないという制約条件とを含み、
各サイトでの前記サーバの使用数に関する、単位時間当たりの費用の総和と処理要求を拒否することで失われる単位時間当たりの収入の総和との和を目的関数として最小化する数理計画問題の最適解から、
各処理サイトにおいて各要求サイトからの処理要求を専用に処理するサーバの使用数と、要求サイトで処理要求の拒否を行うための受入れ容量と、各要求サイトから各処理サイトへのフロー比率とを決定することを特徴とするコンピュータネットワークシステムの設計プログラム。
【請求項４】
前記所定周期である第１周期毎に要求サイト毎に与えられる前記サーバの使用数と、
処理要求の要求サイトと前記処理要求の処理サイトと間の、前記第１周期よりも短い第２周期で予測されたネットワーク遅延を用いて算出された、各要求サイトからみた各処理サイトのサーバでの短周期での有効設計容量とから、
各要求サイトで処理要求の拒否を行うための受入れ容量と、各要求サイトから各処理サイトへのフロー比率とを決定することを特徴とする請求項３記載のコンピュータネットワークシステムの設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータネットワークシステムの設計方法、およびコンピュータネットワークシステムの設計プログラムに関する。
【背景技術】
【０００２】
ここでは、ユーザからの処理要求を処理するサーバが複数設置されたサーバサイト、もしくはデータセンタが、地理的に広域に分散し、それらが通信ネットワーク（以下ネットワーク）で接続されているシステムを特にクラウドシステムと呼ぶことにする。
こうしたシステムでは、非特許文献１にあるように、あるサイトでのトラヒックの急増、もしくはサイト全体の障害に対して、複数のサイト間で資源を融通してユーザに対する応答時間や信頼性を確保できることが期待されている。
また、非特許文献２にあるように、各サイトでトラヒックの時間的変動のみならず、サーバ稼働に際して支払う必要のある電力料金が時間的に変化する場合も、ユーザからのトラヒックを適応的に各サイトに振り分けて、総合コストを最小化できることが期待されている。
【０００３】
以下では、上記のようなサーバサイト、もしくはデータセンタを単純にサイトと呼ぶことにする。また、設計サーバ、グローバル制御装置、ローカル制御装置と各種のサーバが出てくるが、以下、特に限定のない限り、サーバといえば処理サーバのことを指すものとする。
各サイトで稼働させるべきサーバの台数を決定することを容量割当てと呼ぶ。
また、ある要求サイトに加わる処理要求のトラヒックを、複数の処理サイトに分割することをフロー割当てと呼び、その量を単にフローと呼ぶ。また、個々に到着した処理要求を、各処理サイトへ割り当てられたフローの比率（以下単にフロー比率と呼ぶ）に従って振り分けることを負荷分散と呼ぶ。
【０００４】
非特許文献３では、容量割当て（稼働するサーバ台数）で決まる稼働（エネルギー）費用と、容量割当ておよび、各サイトへの負荷分散によって決まる処理遅延費用の総和を最小化するように、最適な負荷分散と容量割当てを同時に求める方法を提案している。
その数理計画問題を定式化するために、定数として以下のものを定義する。
【０００５】
Ｉ：サイトの総数。各サイトはｉ（＝１，…，Ｉ）等の変数を用いて表す。なお、処理要求が発生する要求サイトも、処理要求を処理する処理サイトもＩ個の中に含まれているものとする。
ｐｊ：サイトｊでサーバ１台を稼働するときの単位時間当たりの費用。これにはサイト毎、および時間帯毎に電力費用が異なるという背景があり、それに応じて容量・フロー割当てを適切に行うことで、電力費用を下げようという技術的な目的がある。
β：平均遅延に関する費用係数。
Λｉ：要求サイトｉに到着する処理要求の到着率。
μｊ：処理サイトｊでの各サーバの処理率。これはサーバの平均処理時の逆数で与えられる。
Ｍｊ：処理サイトｊでのサーバの最大可能使用数。
ｄｉｊ：  ネットワークで接続されたサイトｉ，ｊ間で処理要求を転送する際に生じる遅延（以下ネットワーク遅延と略す）。
【０００６】
変数として以下のものを定義する。
ｍｊ：処理サイトｊでのサーバ使用数。整数変数。
λｉｊ：要求サイトｉから処理サイトｊへ振り分けられたフロー。単位は処理要求の到着率と同じである。
数理計画問題を式（１）〜（５）のように定式化する。
【０００７】
【数１】
2016157272.tif 000003
【０００８】
式（１）の目的関数において、第１項は各サイトでそれぞれ１台もしくは複数台のサーバを使用することによって発生する費用の総和であり、非特許文献３ではサーバ１台の各サイトにおける電力料金を意識している。
更に、式（１）の目的関数の第２項において（）で括った部分は処理サイトにおかれた１台のサーバで処理要求を処理するときの応答時間｛＝（処理サイトにおかれたサーバでの系内時間）＋（要求サイトと処理サイト間のネットワーク遅延）｝に相当する。よって式（１）の第２項のβより後の部分をΣｉ＝１ＩΛｉで割ったものは、ネットワーク全体での応答時間の平均を意味するが、Σｉ＝１ＩΛｉは定数なので、これをβの中に含めている。
なお、ｍｊ台ある各サーバへの到着率をΣｉ＝１Ｉλｉｊ／ｍｊとしていることは、他の複数の要求サイトからの処理要求を要求サイトの区別なく受け入れることを意味する。
【０００９】
式（２）は、あるサイトに到着する処理要求の負荷は、自サイトも含めた各サイトへのフローに分割されるというフロー保存を示す制約式である。
式（３）は、サイトｊの各サーバの利用率が１を超えないことを示す制約式である。
式（４）は各サイトにおいて、使用可能なサーバ数には上限があることを示す。
【００１０】
この従来技術の問題点は以下のとおりである。
１つ目は、式（１）の目的関数を見れば明らかなように、応答時間がコストとして最小化すべき目的関数に組込まれているため、応答時間を保証することができないことである。
２つ目は、システムの容量を上回る到着率の処理要求が発生する、すなわち式（６）が成立する場合は、どのようなフロー割当てに対しても式（３）が全ての処理サイトｊについて成立せず、この設計問題が解けないことである。
【００１１】
【数２】
2016157272.tif 000004
【００１２】
非特許文献４では、各サイトは処理要求が到着する要求サイトにも、それを処理する処理サイトにもなるモデルを設定して、容量・フロー割当ての技術が提案されている。
ここでは、容量割当てとフロー割当てとは、異なる時間区間で設定された異なる最適化問題で行う。これは、自サイトに到着したトラヒックを自サイトで処理しきれない場合、他サイトにそれを振り分けるためである。
【００１３】
定数として新たに以下のものを定義する。
ΛｊＴ１（ｔ）：Ｔ１周期でみた時間区間ｔにおける、ユーザから処理サイトｊに到着する処理要求の到着率の予測値。
ｏｊ：オンデマンドでクラウドサービスプロバイダーから調達可能なサーバに関するコスト係数。
【００１４】
この計算法としては、ＬｊＴ１（ｔ）をＴ１周期の時間区間ｔにおける処理要求の総到着数としてΛｊＴ１（ｔ）＝ＬｊＴ１（ｔ）／Ｔ１とする、あるいは非特許文献１にも示されているような下記に示す指数移動平均の方法がある。ただし、αは０より大きく１以下の定数、ｔ番目の時間区間において到着率の予測値をΛｊＴ１（ｔ）、処理要求の総到着数をＬｊＴ１（ｔ）とすると、式（７）のように算出される。
【００１５】
【数３】
2016157272.tif 000005
【００１６】
ここで、Ｒ、Ｍを、それぞれ以下のように定義する。
Ｒ：  応答時間の要求値。
Ｍ：  広域クラウドシステム全体で使用可能なサーバ数の上限。
また、変数として次のものを定義する。
ｎｊ：オンデマンドでＩａａＳ（Infrastructure as a service）プロバイダーから調達するサーバ数。整数変数。
以上を用いて非特許文献４における容量割当ての設計問題は、式（８）〜（１１）のように定式化される。ただし、非特許文献３の内容にそろえるため、定式化は元のものから一部変更してある。
【００１７】
【数４】
2016157272.tif 000006
【００１８】
これは長い区間での到着率の予測値に対して、処理要求の到着したサイトでの応答時間の要求値を満たすという条件の下で、サーバ使用数に関する費用の総和を最小にするための各サイトでのサーバ使用数を決定するものである。
式（８）の目的関数は各クラウドサービスプロバイダーのサイトにおいてサーバをオンデマンドで借りる場合における、単位時間当たりの料金の総和を意味している。
式（９）は、応答時間の全サイトに関する平均値をＲ以下にするという制約式を表す。
式（１０）はサーバ１台の利用率が１未満であることを示す制約条件である。
式（１１）は、長期的にＩａｓＳプロバイダーから調達しているサーバ数は、広域クラウドシステム全体でＭであり、そのうちｍｊを各サイトで使用することを示す。
【００１９】
次にこの従来技術の問題点について列挙する。
１つ目は、先ず式（９）を見れば明らかなように、非特許文献３と違って応答時間は全サイトでの平均に関しては保証できるが、依然として個々のサイトについて応答時間は保証できないことである。
２つ目は、式（９）では各処理サイトへの到着率はそのサイトにユーザから到着する分であるΛｊＴ１のみを考慮し、他のサイトから振り分けられたフローの到着率を考慮していない。こうしてサイト間で負荷を最適に分散することはできない。
【００２０】
次に、非特許文献４に記載された従来技術では、Ｔ１より短い周期Ｔ２でフロー割当てを行う。
これは、容量割当てで設計されたサーバ数を前提に、より短い区間での予想トラヒックに対して、そのフロー割当てを設計する。その際、処理要求の到着したサイトで処理しきれない部分は他のサイトに振り分ける。その比は、他サイトとのネットワーク転送遅延の逆数に比例する割合で決定される。フロー割当ての目的関数は、ネットワーク転送遅延を含む応答時間を最小化する。
【００２１】
サーバ使用数は容量割当てのための設計問題の解で与えられたものとして、Ｔ２毎に下記のフロー割当てのための設計問題を解く。なお下記の定式化は、上記で定義した変数、定数をなるべく使うように、非特許文献４の式を書き直してある。
定数として新たに以下のものを定義する。
ΛｉＴ２：周期Ｔ２でサイトｉに到着する処理要求の到着率の予測値。
ｍｊ＊：サイトｊでの長期的に調達しているサーバの使用数。
ｎｊ＊：サイトｊにおいてオンデマンドで調達したサーバの使用数。
また、ここで、自サイトｉに到着する処理要求を他の各サイトｊ（＝１，…，Ｉ，ｉ≠ｊ）に振り分けるフロー比率θｉｊを式（１２）のように決める。
【００２２】
【数５】
2016157272.tif 000007
【００２３】
よって、到着率がΛｉＴ２であるサイトｉ自身に振り分けるフローはλｉｉなので、サイトｉからサイトｊにいくフローλｉｊは式（１３）のようになる。
【００２４】
【数６】
2016157272.tif 000008
【００２５】
以上から、フロー割当ての設計問題を、以下の非線形計画問題で定式化する。ただし、非特許文献３の定式化の内容とそろえるため、元の定式化を一部変更してある。
【００２６】
【数７】
2016157272.tif 000009
【００２７】
式（１４）の目的関数は、各要求サイトからみた各処理サイトにおける応答時間の全フローλｉｊ（ｉ，ｊ＝１，…，Ｉ）に関する加重平均値を最小にすることを意味する。
フロー割当てにおいて、この従来技術の問題点を以下に列挙する。
１つ目は、フロー比率は、他のサイトに振り分ける分ＡｉＴ２−λｉｉに関して、伝搬遅延の逆数に比例するという固定的なものであるため、最適化できるのは、同じサイトで処理できる量と、他のサイトで処理する量という粒度にとどまる。
２つ目は、目的関数は総合遅延を最小化することであるため、総合遅延を保証することはできないことである。
３つ目は、システムの容量を上回る到着率の処理要求が発生する、すなわち式（１８）となる場合には、どのようなフロー割当てに対しても式（１６）が少なくとも一つのサイトｊについて成立しなくなり、上記フロー割当てのための設計問題は解けないことである。
【００２８】
【数８】
2016157272.tif 000010
【００２９】
上記の問題点に対して、システム全体が過負荷になっても、受け入れた処理要求に対しては要求性能を保証すべく、容量割当てを決定する方法が特許文献１に示されている。
ここでは、非特許文献３，４とは異なり、サーバ使用数と同時に入力規制割合を決定しており、また、特許文献１では非線形計画法ではなく、線形計画問題に基づいている。
【００３０】
非特許文献１における設計問題を上記の流れに従って説明するため、先ず定数として以下のものを定義する。
ν：１台のサーバの最大収容到着率。特許文献１では最大収容生起率となっているが、ここでは到着率で統一的に表現する。
以下、この具体的な算出方法について説明する。
１台のサーバに到着率λで処理要求が到着するとき、サーバでの系内時間ｔがＲ以内に完了する確率を完了率と呼び、Ｐｒ｛ｒ≦Ｒ｝であらわす。これは一般にλの増加関数、およびＲの減少関数となる。
更に完了率にλを掛けたλ＊Ｐｒ｛ｔ≦Ｒ｝は、要求時間を満足された処理要求のスループットを表し、これをグッドプットと定義する。
最大収容到着率は、グッドプットを最大にする到着率であり、式（１９）のように定式化できる。
【００３１】
【数９】
2016157272.tif 000011
【００３２】
更に以下の定数を定義する。
ｐ：サーバ１台を稼働しているときの時間当たりの費用。
ｑ：処理要求を処理することで得られる収入。
Λ：サイトに到着する処理要求の到着率の予測値。
Ｍ：サーバの最大許容稼働総数。
【００３３】
次に変数として以下のものが定義されている。
ｍ：１台しかないサーバを稼働しているサイトの総数。
φ：サイトに到着した処理要求のうち、その到着率では応答時間の要求値を満たすことができずに、処理要求を拒否した割合を示す拒否率。ここで処理要求の拒否とは具体的には、単純に処理要求メッセージを拒否するか、もしくは拒否メッセージをユーザに返答する。ただし後者の場合、拒否メッセージの返答にかかる負荷は、処理供給を処理する負荷に比べて無視できるものとする。
以上に基づいて、サーバ稼働数と拒否率を最適に決定するための設計問題は、式（２０）〜（２２）のような混合整数計画問題として定式化できる。
【００３４】
【数１０】
2016157272.tif 000012
【００３５】
ここで、式（２０）は、単位時間当たりにおいて、処理要求を処理することで得られる収入からサーバ稼働による費用を差し引いた収益を最大化することを目的とする。あるいは等価的に、単位時間あたりにおいて、処理要求を拒否することで失われる収入と、サーバ稼働による費用との総和を最小化することを目的とする。
式（２１）は、受け入れた処理要求の到着率がシステム全体の総収容能力を上回らないことを示す制約条件である。
ここで、ｍが実数を許すとすると最適解では式（２１）は等号のみ成り立ち、１−φ＝ｍν／Λとなるので、これを目的関数の式（２０）に代入すると、式（２３）のようになる。
【００３６】
【数１１】
2016157272.tif 000013
【００３７】
よってサーバ使用数を増加させることで利益が増大するという技術的に意味のある係数設定をするためには、ｍの係数が正、すなわち式（２４）が成立する必要がある。
【００３８】
【数１２】
2016157272.tif 000014
【００３９】
なお、どのサーバも有効設計容量はνと共通なので、フロー割当ての割合はどのサーバにも等しく１／ｍとなる。
この問題の最適解は次のようにして求められている。すなわち、式（２０）の目的関数をｃとおいてそれをφについて解くと式（２５）となって、（ｍ，φ）空間におけるこの式のφ切片は１−ｃ／ｑΛになるから、ｃを最大にするには上記直線のφ切片を許容領域内で最小にすればよい。
【００４０】
【数１３】
2016157272.tif 000015
【００４１】
よって最適解はｑν＞ｐの場合に、式（２６）となる。
【００４２】
【数１４】
2016157272.tif 000016
【００４３】
よって、Λの上昇に伴ってサーバ使用数はΛに比例してＭまで増大し、その後はＭのまま一定になる。また、拒否率は、Λ＜Ｍνの間はφ＝０と一定であり、Λ＝ＭνになるとΛの増加に伴って１に漸近する。総受入れ速度（システムに受け入れられた単位時間あたりの処理要求）は、Λ＜ＭνではΛであり、Λ≧ＭνではＭνと一定になる。
【００４４】
一方、ｑν＜ｐの場合は、式（２７）のように、サーバ使用数が０という技術的に意味がない最適解しか得られない。
【００４５】
【数１５】
2016157272.tif 000017
【００４６】
この特許文献１の問題点は、要求サイトや、処理サイトがそれぞれ複数ある場合のモデル化に対応できていないことである。もう一つの問題点は、コスト係数の取り方によって最適解が技術的に意味のないものになることである。
【００４７】
次に、特許文献２では、要求サイトも複数ある場合に対応できるフロー割当て問題の解が提示されている。
処理要求の１つある要求サイトｉから一般に複数あり、ネットワーク遅延も異なる処理拠点ｊの１台のサーバとのネットワーク遅延ｄｉｊが一般に異なっている場合の、各サイトにフローを割り当てる係数を決めている。
【００４８】
要求サイトｉからの処理要求を処理サイトｊで処理する際の応答時間ｒｉｊをＲ以下にするということは、サイトｊに設置されたサーバでの系内時間ｔｊは全ての処理サイトｊに関して式（２８）を満たす必要がある。
【００４９】
【数１６】
2016157272.tif 000018
【００５０】
この複数の不等式を処理サイトｊに設置されたサーバでの系内時間についてまとめて書くと、式（２９）となる。
【００５１】
【数１７】
2016157272.tif 000019
【００５２】
よって、処理サイトｊに設置されたサーバのグッドプットは、式（３０）と書ける。
【００５３】
【数１８】
2016157272.tif 000020
【００５４】
従って、式（１９）より、サイトｊのサーバ１台の最大収容到着率νｊは、式（３１）のようになる。
【００５５】
【数１９】
2016157272.tif 000021
【００５６】
つまり、最大許容到着率はサイト間の遅延の最大値を用いて計算する。
更に、各要求サイトからみたフロー比率は、式（３２）に示される最大許容到着率の相対比で、要求サイト側で決定する。
【００５７】
【数２０】
2016157272.tif 000022
【００５８】
この従来技術の問題点は、各処理サイトに複数のサーバがある場合には対応できないことである。
非特許文献４では式（９）からわかるようにサイト全体で平均した応答時間を保証している一方で、非特許文献６には各サイト間で性能保証をする容量・フローの割当て問題が線形問題として示されている。
非特許文献６では、性能評価モデルはＭ／Ｍ／ｎを用いているが、ここでは上述の従来技術の説明の流れに沿ってＭ／Ｍ／１を用いる。またサイト間遅延に関しては考慮されていないが、同じくそれを考慮した応答時間を導出する。
【００５９】
すると処理サイトｊで評価したサーバ処理における平均系内時間がサイト間遅延も含めてＲ以下になるという条件は、サイトｊに加わるフローの総和が、式（２）にあるのと同じくΣｉ＝１Ｉλｉｊとなるので、式（３３）となる。
【００６０】
【数２１】
2016157272.tif 000023
【００６１】
これをｊ毎にまとめると式（３４）のようになる。
【００６２】
【数２２】
2016157272.tif 000024
【００６３】
上式をｍｊ（ｊ＝１，…，Ｉ）について解くと、設計問題の定式化における制約条件である式（３７）を得る。非特許文献６ではこれを用いて下記の容量・フロー割当てのための設計問題を、式（３５）〜（３９）の混合整数計画問題として定式化している。
【００６４】
【数２３】
2016157272.tif 000025
【００６５】
この従来技術の１つの問題点は次のとおりである。すなわち、式（３４）を見てもわかるように、各処理サイトの各サーバには、いずれの要求サイトからの処理要求も受け入れるため、各処理サイトのサーバで満たすべき処理遅延の要求条件は、要求サイトと処理サイトの間のネットワーク遅延で最大のもののみで決まるという比較的厳しい条件設定となる。
【００６６】
これと異なり、非特許文献７では、処理サイトでは要求サイトからの処理要求毎に専用の処理サーバを用意するモデルを設定している。そのために次の変数を定義する。
ｍｉｊ：サイトｉからの処理要求をサイトｊで専用に処理するサーバの使用数。非負の整数とする。
すると、要求サイトと処理サイトの間のネットワーク遅延も取り込んでそのサイト間での応答時間を保証する式は、式（４０）のようになる。
【００６７】
【数２４】
2016157272.tif 000026
【００６８】
このｍｉｊに関する非線形式をｍｉｊについて解くと式（４３）の線形の制約条件が得られる。非特許文献７はこれを用いて、容量・フロー割当てのための設計問題を、式（４１）〜（４５）に示す混合整数計画問題として定式化している。
【００６９】
【数２５】
2016157272.tif 000027
【００７０】
上記の非特許文献６、７に記載されている従来技術の問題点は、用意されたサーバを最大限使用して広域クラウドシステム全体で提供される処理能力の総和を上回る処理要求の到着率が広域クラウドシステム全体に加わった場合には解が存在しない、すなわち対応できないことである。
この過負荷の条件は式（４２）〜（４４）より、式（４６）のように定式化できる。
【００７１】
【数２６】
2016157272.tif 000028
【００７２】
式（４６）の最左辺はシステム全体に加わる到着率、最右辺はシステムの最大処理能力を示す。よって式（４７）の不等式が成立するような到着率のベクトル（Λ１，…，ΛＩ）に対しては式（４４）を満たせなくなり、上記問題は解を持たない。
【００７３】
【数２７】
2016157272.tif 000029
【００７４】
こうした過負荷状況に対応できる従来技術の一つとして非特許文献８がある。そこでは各処理サイトの容量を上回って必要になるサーバ使用数はペナルティーになるとして最小化すべき目的関数に含める容量・フロー割当ての設計問題が示されている。その定式化のために下記の変数を新たに導入する。
ｌｊ：処理サイトｊに割り振られたフローの総和がそのサイトのサーバ使用数上限（容量）Ｍｊを上回って付加的に必要になる超過サーバ稼働数を表す非負の整数。
以上により容量・フロー割当ての設計問題は、式（４８）〜（５２）に示す混合整数計画法に定式化できる。
【００７５】
【数２８】
2016157272.tif 000030
【００７６】
以下非特許文献８の課題について述べる。なお、以下の考察は下記の式（５４）を除き、この文献には記載されていない。
ここで上記問題において式（５３）とおくと、これはサイトｉからサイトｊのサーバ１台が、応答時間の要求値を満たす範囲で収容することができる到着率の最大値を示している。
【００７７】
【数２９】
2016157272.tif 000031
【００７８】
これは特許文献１，２で定義された最大収容到着率と同じ概念の量であるが、以下では有効設計容量と呼ぶことにする。
次に発生サイトｉからみて処理サイトｊへのフロー比率θｉｊおよび、処理サイトｊに到着する処理要求の拒否率φｊは、それぞれ式（５４）、（５５）のようになる。ただし、式（５４）に相当する式はすでに非特許文献８に現れている。
【００７９】
【数３０】
2016157272.tif 000032
【００８０】
すると、広域クラウドシステム全体での網内通過総到着率（単位時間あたり、異なるサイト間を転送される処理要求の総量）、総受入れ速度（短時間あたり処理要求を処理できた処理要求の総和）、総拒否率はそれぞれ、式（５６）、（５７）、（５８）のように計算できる。
【００８１】
【数３１】
2016157272.tif 000033
【００８２】
ただし、容量割当て、超過サーバ数の最適解をそれぞれｍｉｊ＊，ｌｊ＊とし、実際に測定された各サイトでの処理要求の到着率を式（５９）のように表す。
【００８３】
【数３２】
2016157272.tif 000034
【００８４】
また、処理サイトでいずれ廃棄される処理要求がネットワーク上を転送されることで、各サイト間の転送遅延ｄｉｊ（ｉ，ｊ＝１，…，Ｉ）が、有効設計容量の算出で想定したサイト間ネットワーク遅延を増大させることはなく、有効設計容量νｉｊ（ｉ，ｊ＝１，…，Ｉ）を減少させることはないものとする。
【００８５】
以上に基づいて非特許文献８には次の問題がある。
１つ目は、この問題の解からは、各要求サイトに対して実際に稼働させるべきサーバ数が直接求められないことである。すなわち、処理サイトｊで稼働させるべきサーバの総数はΣｉ＝１Ｉｍｉｊ＊−Ｉｊ＊で与えられるが、超過分ｌｊ＊を要求サイトｉ毎に分割する方法は自明ではない。
２つ目は、いずれ処理サイトにおいて処理要求を廃棄される処理要求メッセージが、要求サイトから処理サイトまで転送されることになり、それが各サイト間を接続しているネットワークに負荷を与えるおそれがあることである。更にその負荷でサイト間の転送遅延が増加して、有効設計容量を減少させることにつながるおそれもある。
３つ目は、上式で算出される総処理量が最適化できず、要求サイトからみた廃棄率にもバラつきが生じある可能性があるからである。なぜなら、目的関数に含まれる変数としては到着率や廃棄率ではなく、超過サーバ稼働数しか入っていないからである。
４つ目は、稼働可能なサーバ台数を全て使用することで総廃棄率を最大限下げることが常にできるとは限らないことで。すなわち最適解ｌｊ＊に対してΣｊ＝１ＩＩｊ＊＞０となって少なくとも一つの処理サイトで処理要求の廃棄を行う必要がある場合でも、できるだけ廃棄率を減らせるように次式で与えられる実際に稼働させるサーバ総数をその上限にする解、すなわち式（６０）を満たす解が得られるとは限らないことである。
【００８６】
【数３３】
2016157272.tif 000035
【先行技術文献】
【特許文献】
【００８７】
【特許文献１】国際公開第２０１４／０８０９９４号
【特許文献２】特開２０１４−１０３６３７号公報
【非特許文献】
【００８８】
【非特許文献１】G. Nikolay、他１名、"Inter-cloud architectures and application brokering: taxonomy and survey"、Software-Practice and Experience 2014、２０１４年、p.369-390
【非特許文献２】A. Rahman、他２名、"A survey on geographic load balancing based data center power management in the smart grid environment"、IEEE、２０１４年、IEEE Communications Surveys Tutorials、Volume 16、Issue 1、p.214-233
【非特許文献３】Z. Liu、他４名、"Greening Geographical Load Balancing"、ACM SIGMETRICS 2011、２０１１年６月、p.233-244
【非特許文献４】D. Ardagna、他３名、"Dual time-scale distributed capacity allocation and load redirect algorithms for cloud systems"、J. Parallel Distrib. Comput.、２０１２年、vol.72、no.6、p.796-808
【非特許文献５】Wikipedia  Token bucket、［0nline］、［平成２７年１月１４日検索］、インターネット<URL:http://en.wikipedia.org/wiki/Token_bucket>
【非特許文献６】L. Rao、他３名、"Minimizing electricity cost: optimization of distributed internet data centers in a multi-electricity-market environment"、IEEE、２０１０年、INFOCOM
【非特許文献７】E. Casalicchio、他１名"An Inter-cloud Outsourcing Model to Scale Performance, Availability and Security"、IEEE、２０１２年、IEEE/ACM Fifth International Conference on Utility and Cloud Computing、p.151-158
【非特許文献８】Q. Zhang、他４名、"Dynamic Service Placement in Geographically Distributed Clouds"、IEEE、２０１３年、Selected Areas in Communications, IEEE Journal on、Volume 31、Issue 12、p.762-772
【発明の概要】
【発明が解決しようとする課題】
【００８９】
容量・フロー割当てにおいて、システムの容量を上回る到着率で処理要求が発生した場合、それを要求サイト側ではなく、処理サイト側に到着してからそこで処理要求の受け入れもしくは拒否の判断と実行を行うことが前提となっているので、要求サイトに通常よりも大きな処理要求のトラヒックが発生してそれが他のサイトに割り振られる場合は、それらのサイト間を接続するネットワークにより大きな負荷がかかってしまうことになる。
【００９０】
本発明は、上述の課題を解決することのできるコンピュータネットワークシステムの設計方法、およびコンピュータネットワークシステムの設計プログラムを提供することを目的としている。
【課題を解決するための手段】
【００９１】
本発明の第１の態様によれば、コンピュータネットワークシステムの設計方法は、各要求サイトに到着する処理要求の到着率の所定周期での予測値と、処理要求の要求サイトと前記処理要求の処理サイトと間の、前記所定周期で予測されたネットワーク遅延を用いて算出された各要求サイトからみた各処理サイトのサーバの前記所定周期での有効設計容量とをそれぞれ定数として含み、各処理サイトにおいて各要求サイトからの処理要求を専用に処理するサーバの使用数と、各要求サイトでの処理要求の拒否に関する量とをそれぞれ変数として含み、各処理サイトでの前記サーバの使用数の各要求サイトに関する総和は上限を持つという制約条件と、各要求サイトが受け入れた処理要求の到着率は、前記各処理サイトにおける前記サーバの使用数と前記所定周期での有効設計容量の積の全処理サイトに関する総和を上回らないという制約条件とを含み、各サイトでの前記サーバの使用数に関する、単位時間当たりの費用の総和と処理要求を拒否することで失われる単位時間当たりの収入の総和との和を目的関数として最小化する数理計画問題の最適解から、各処理サイトにおいて各要求サイトからの処理要求を専用に処理するサーバの使用数と、要求サイトで処理要求の拒否を行うための受入れ容量と、各要求サイトから各処理サイトへのフロー比率とを決定することを特徴とする。
【００９２】
本発明の第２の態様によれば、コンピュータネットワークシステムの設計プログラムは、各要求サイトに到着する処理要求の到着率の所定周期での予測値と、処理要求の要求サイトと前記処理要求の処理サイトと間の、前記所定周期で予測されたネットワーク遅延を用いて算出された各要求サイトからみた各処理サイトのサーバの前記所定周期での有効設計容量とをそれぞれ定数として含み、各処理サイトにおいて各要求サイトからの処理要求を専用に処理するサーバの使用数と、各要求サイトでの処理要求の拒否に関する量とをそれぞれ変数として含み、各処理サイトでの前記サーバの使用数の各要求サイトに関する総和は上限を持つという制約条件と、各要求サイトが受け入れた処理要求の到着率は、前記各処理サイトにおける前記サーバの使用数と前記所定周期での有効設計容量の積の全処理サイトに関する総和を上回らないという制約条件とを含み、各サイトでの前記サーバの使用数に関する、単位時間当たりの費用の総和と処理要求を拒否することで失われる単位時間当たりの収入の総和との和を目的関数として最小化する数理計画問題の最適解から、各処理サイトにおいて各要求サイトからの処理要求を専用に処理するサーバの使用数と、要求サイトで処理要求の拒否を行うための受入れ容量と、各要求サイトから各処理サイトへのフロー比率とを決定することを特徴とする。
【発明の効果】
【００９３】
本発明によれば、処理要求の発生サイトでその受入れ容量を上回る処理要求を拒否するので、過剰トラヒックが発生サイトと処理サイトをつなぐネットワークに加える負荷を削減することができる。
【図面の簡単な説明】
【００９４】
【図１】本発明の実施形態における広域クラウドシステムの構成を示すブロック図。
【図２】同実施形態におけるサイトの構成を示すブロック図。
【図３】同実施形態におけるグローバル制御装置の構成を示すブロック図。
【図４】同実施形態におけるグローバル制御装置の動作を示す流れ図。
【発明を実施するための形態】
【００９５】
以下、本発明の実施形態を説明するが、以下の実施形態は請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００９６】
本発明の第１の実施形態について、数式および図面を用いて詳細に説明する。
これは非特許文献８の考え方に従えば、各出口（処理サイト）で超過するサーバ数から算出される拒否率で処理要求をその出口で拒否していたのに対して、システムの入口（要求サイト）において受入れ可能な容量を上回って到着する処理要求をその入口で拒否することに相当する。
【００９７】
先ず容量・フロー割当てのための設計問題を定式化するのに必要となる定数である設計容量を特許文献１で定義された最大収容到着率の概念を用いて定義する。
ここで、サーバでの１回のメッセージ処理における平均系内時間の評価は、Ｍ／Ｍ／１待ち行列モデルを用いて行うとする。そして、ユーザからの一つの処理要求の処理を完了するのに、ユーザと同一サーバ間でやり取りされるＷ個のメッセージを処理する必要があり、更にユーザからみた応答時間には、そのうちＸ回分の処理が含まれるとする。またユーザとサーバの間でメッセージを複数回やり取りする場合の全てのネットワーク遅延をｄｉｊで表す。すると応答時間が要求値以下になるということを示す不等式は、式（６１）のようになる。
【００９８】
【数３４】
2016157272.tif 000036
【００９９】
νｉｊを、サイトｉからみて、サイトｊに設置した単体サーバでの処理における応答時間の要求値Ｒを満たしてサイトｊで収容可能な、サイトｉからの処理要求の到着率の最大とし、これを要求サイトｉからみた処理サイトｊの有効設計容量と呼ぶことにすると、式（６０）より有効設計容量は式（６２）のように計算される。
【０１００】
【数３５】
2016157272.tif 000037
【０１０１】
非特許文献６、７、８では、それぞれ式（３７）、（４３）、（４９）において、サーバでの１回だけの処理で、ユーザからの処理要求の処理を完了する場合の有効設計容量に相当する量しか導出されていなかった。これに対して、本実施形態によれば、式（６２）により一般的な処理を行う場合の有効設計容量が導出できる。
次に新たな変数を定義する。
φｉ：処理サイトｉで到着する処理要求をそのサイトで拒否する割合（拒否率）。非負の実数変数。拒否率は、処理要求の拒否に関する量の例に該当する。
以上に基づいて、長周期（以下、長周期をＴ１と表記する）毎に実行する容量割当てのための設計問題を、式（６３）〜（６７）で示される混合整数計画法による数理計画問題に定式化する。ただしνｉｊＴ１は、Ｔ１周期で推定したネットワーク遅延ｄｉｊＴ１より式（６２）で算出される有効設計容量とする。
【０１０２】
【数３６】
2016157272.tif 000038
【０１０３】
ここで、目的関数の式（６３）は、各サイトで処理要求を受け入れることで得られる単位時間当たりの収入の総和から、各サイトでサーバを使用することで単位時間あたりに発生する費用の総和を引いて得られるシステム全体での総利益を最大化することを意味する。あるいは等価的に、各サイトで処理要求を拒否することで失われる単位時間当たりの収入の総和と各サイトでサーバを使用することで単位時間あたりに発生する費用の総和との和を最小化することを意味する。
式（６４）において、νｉｊＴ１はサーバ単体が最大収容可能な到着率、すなわち有効設計容量を表すので、左辺は全処理サイトで収容可能な到着率の総和を表す。そして右辺、すなわち要求サイトで受け入れられた処理要求の到着率の総和が、左辺を上回らないという制約条件を式（６４）は表している。
式（６５）は、各処理サイトでの処理サーバの使用数の各要求サイトに関する総和は上限を持つという制約条件を示している。
【０１０４】
次に、長周期より短い周期の短周期（以下、短周期をＴ２と表記する）でのフロー割当てと入力規制を行うためのパラメータの計算方法について説明する。
フロー割当てを考えるに当たり、サイトｊでは、サイトｉからの処理要求を専用に処理するためのサーバの使用数は、容量割当ての設計問題１の最適解ｍｉｊ＊（ｉ，ｊ＝１，…，Ｉ）で与えられるものとする。
【０１０５】
以上に基づいて、サイトｉに到着した処理要求の広域クラウドシステム内への受入れ容量Ｃｉを式（６８）で計算する。
【０１０６】
【数３７】
2016157272.tif 000039
【０１０７】
また、サイトｉからサイトｊへのフロー比率θｉｊを、式（６９）で計算する。
【０１０８】
【数３８】
2016157272.tif 000040
【０１０９】
各サイトでは、フロー比率に基づいて各処理要求の処理サイトを決定する。また、各サイトではＣｉの平均レートでポリシングを行い、違反して到着した処理要求を拒否する。ポリシングの方法としては、非特許文献５に示した平均レートを制限するためのトークンバケットがある。
このときの、広域クラウドシステム全体での総受入れ速度、網内通過総到着率、および総拒否率は、それぞれ式（７０）、（７１）、（７２）で与えられる。
【０１１０】
【数３９】
2016157272.tif 000041
【０１１１】
次に、第１の実施形態の構成について説明する。
図１は、広域クラウドシステムの制御を実現する場合の全体構成図である。同図において、広域クラウドシステム１は、サイト１０１〜１０５と、グローバル制御装置２と、サイト１０１〜１０５間を接続するネットワーク３とを含む。サイト１０１〜１０５は、それぞれ、ローカル制御装置４１〜４５を含む。また、同図において、サイト１０１〜１０５のユーザ１５が示されている。
広域クラウドシステム１は、コンピュータネットワークシステムの例に該当する。但し、本発明の適用範囲は広域クラウドシステムに限らない。処理サイトで処理要求を拒否することによるトラヒックが問題になり得るいろいろなコンピュータネットワークシステムに本発明を適用し得る。
なお、広域クラウドシステム１に含まれるサイトの数は、図１に示す５つに限らず複数であればよい。
【０１１２】
グローバル制御装置２は、サイト１０１〜１０５の各々から処理要求の到着率の予測値、各サイト間のネットワーク遅延の予測値を収集して、各サイトでユーザからの処理要求の処理のために使用すべきサーバ数、および各サイト間で処理要求のフローを分割する割合を決定する。
また、グローバル制御装置２は、各サイトのローカル制御装置に、フロー比率と受入れ容量を通知する。
【０１１３】
ユーザ１５から、処理要求が適切なサイトに送信され、サイト内に設置されたサーバではその処理が実行される。サイトについては以下に説明する。
ネットワーク３は各サイト間で送信すべき処理要求、処理応答等のメッセージを伝達するものであるが、その際には、遅延が発生するものとする。
【０１１４】
図２はサイト内の構成を示すブロック図である。同図では、サイト１０１、１０２を例に説明する。サイト１０３〜１０５も同様である。
サイト１０１は、ローカル制御装置４１と、サイト間負荷分散装置（以下サイト間ＬＢと略す）５１と、サイト内負荷分散装置（以下サイト内ＬＢ）６１および６２と、処理サーバ７１〜７４とを含む。サイト１０２は、ローカル制御装置４２と、サイト間ＬＢ５２と、サイト内ＬＢ６３および６４と、処理サーバ７５〜７８とを含む。
【０１１５】
以下、ローカル制御装置４１〜４２を総称してローカル制御装置４と表記する。また、サイト間ＬＢ５１〜５２を総称してサイト間ＬＢ４と表記する。サイト内ＬＢ６１〜６４を総称してサイト内ＬＢ６と表記する。処理サーバ７１〜７８を総称して処理サーバ７と表記する。なお、上述したように、処理サーバを単にサーバとも称する。
【０１１６】
ローカル制御装置４は、グローバル制御装置２からの指令に基づいて、サイト間ＬＢ５に、負荷分散係数と受入れ容量を設定する。また、ローカル制御装置４は、グローバル制御装置２から指示されたサーバ使用数に基づいてサーバ７の立ち上げ、立ち下げを行う。
更に、ローカル制御装置４は、サイト間ＬＢ５から、そのサイトのユーザもしくは、障害サイトから誘導されたユーザから到着した処理要求の到着数に関する情報をＴ１周期で収集し、式（７）を用いてその周期での到着率の予測値を算出する。また、ローカル制御装置４は、サイト間ＬＢ５に指示して他のサイトのサイト間ＬＢ５との間のネットワーク遅延を測定する。そして、ローカル制御装置４は、グローバル制御装置２からの要求に応じて応答する。
【０１１７】
サイト間ＬＢ５は、ローカル制御装置４から指示されているサイト間フロー比率に基づいて、個々の処理要求を自サイトを含む各サイトに振り分ける。自サイトにおいては、一つもしくは複数のサイト内ＬＢ６に処理要求を振り分ける。図２においては、サイト間ＬＢ５１は、自サイト内のサイト内ＬＢ６１，６２、およびサイト間ＬＢ５２に処理要求を振り分ける。
また、サイト間ＬＢ５は、その要求サイトに属するユーザ１５から、受入れ容量を上回る分で到着する処理要求を拒否する。また、サイト間ＬＢ５は、障害サイトから誘導されたユーザ１５から到着する処理要求が受入れ容量を上回る分を拒否する。
【０１１８】
サイト内ＬＢ６は、配下に収容する各サーバ７に等しい比率で処理要求を振り分ける。
サーバ７はサイト内ＬＢ６の配下に一般に複数接続され、稼働中の場合は割り振られた処理要求を処理する。
なお、各サーバ７は稼働していない場合もある。サイト内にあるサーバ７の数の上限は最初からローカル制御装置４に与えられているものとする。本発明では、この使用数を決定する。
【０１１９】
図３はグローバル制御装置２の構成を示すブロック図である。
グローバル制御装置２は、データ処理装置８と、記憶装置９と、入出力装置１０とを含む。データ処理装置８は、設計情報収集手段８１と、設計処理手段８２と、設定処理手段８３とを含む。
設計情報収集手段８１は、長周期もしくは短周期のそれぞれにおける処理要求の各サイトへの到着率の予測値の情報、およびサイト間の平均ネットワーク遅延の情報をそれぞれある周期で収集する。なお、長周期は、所定周期の例に該当する。また、長周期は、第１周期の例にも該当する。短周期は、長周期よりも短い周期であり、第２周期の例に該当する。
設計処理手段８２は、与えられた定数から容量もしくはフロー割当ての最適解を得て、そこからフロー割当てをするために必要となるパラメータを算出する。
設定処理手段８３は、容量割当て、フロー割当てのパラメータを各サイトのローカル制御装置に通知する。
入出力装置１０は、ローカル制御装置４と通信を行う。
【０１２０】
以下、第１の実施形態の動作について図面を用いて説明する。図４はグローバル制御装置２の動作を示す流れ図である。
Ｓ１で、設計情報収集手段８１がＴ２タイマー（周期Ｔ２のタイマー）のタイムアウトを検出したら、Ｓ２で設計情報収集手段８１は各サイト（ｉ＝１，．．．，Ｉ）からＴ２周期での到着率の予測値ΛｉＴ２と、各サイト間のネットワーク遅延のベクトルｄｉＴ２＝（ｄｉ１Ｔ２，…，ｄｉＩＴ２）を収集して設計情報記憶部９１に記憶させ、全サイトからの収集が完了したら、設計情報記憶部からサイト間のネットワーク遅延の行列ＤＴ２＝（ｄ１Ｔ２，…，ｄＩＴ２）Ｔを取り出し、それから式（６２）を用いて各要求サイトからみた各処理サイトのサーバのＴ２周期での有効設計容量の行列ＮＴ２＝［νｉｊＴ２］を算出して、設計情報記憶部９１を更新する。ここで、Ｔ２周期での有効設計容量とは、Ｔ２周期で推定したネットワーク遅延ｄｉｊＴ２より式（６２）で算出される有効設計容量である。
【０１２１】
次にＳ３で設計情報収集手段８１は、Ｔ１タイマー（周期Ｔ１のタイマー）もタイムアウトかどうか調べる。
Ｓ３でタイムアウトしていない場合は（Ｓ３：ＮＯ）、Ｓ４に行く。
Ｓ４で設計処理手段８２は各サイトの短周期の到着率の予測値のベクトルΛＴ２＝｛Λ１Ｔ２，…，ΛＩＴ２｝、ＮＴ２、およびサーバ使用数の行列Ｓ＝［ｍｉｊ＊］を設計情報記憶部９１から取り出し、それらより式（６８）、（６９）をそれぞれ用いて各サイトの受入れ容量Ｃ、全サイトにおけるフロー比率の行列Θ＝［θｉｊ］＝（θ１，…，θＩ）Ｔ（Ｔは縦ベクトルを示す）を順次算出して、設計情報記憶部９１を更新し、Ｓ５に行く。Ｓ５で設定処理手段８３は、容量割当てｓｉＴ≡（ｍ１ｉ＊，…，ｍＩｉ＊）Ｔ、Ｃｉ、およびθｉ＝（θｉ１，…，θｉＩ）を設計情報記憶部９１から取り出し、各サイトｉ（＝１，．．．，Ｉ）のローカル制御装置４に通知する。
【０１２２】
Ｓ３で設計情報収集手段８１は、Ｔ１タイマーがタイムアウトしている場合は（Ｓ３：ＹＥＳ）、Ｓ６で各サイト（ｉ＝１，．．．，Ｉ）からＴ１周期での到着率の予測値ΛｉＴ１と、各サイト間のネットワーク遅延のベクトルｄｉＴ１＝（ｄｉ１Ｔ１，…，ｄｉＩＴ１）とを収集してサイト間のネットワーク遅延行列ＤＴ１＝（ｄ１Ｔ１，…，ｄＩＴ１）Ｔから式（６２）を用いて各要求サイトからみた各処理サイトのサーバのＴ１周期での有効設計容量の行列ＮＴ１＝［νｉｊＴ１］を算出して設計情報記憶部９１に格納し、設計処理手段８２に設計要求を行う。それを受けた設計処理手段８２は、Ｓ７で設計情報記憶部９１より行列ＮＴ１＝［νｉｊＴ１］を読み出し、ΛＴ１とＮＴ１から［容量割当ての設計問題１］を設定して解き、その最適解からサーバ使用数の行列Ｓを決定して設計情報記憶部９１を更新しＳ4に飛ぶ。
【０１２３】
次に、ネットワークもしくはサイトに障害が発生している場合に第１の実施形態に基づいて対処する実施例を示す。
先ず、サイトｋ，ｌ間のネットワークに障害が発生した場合は、それ以降の設計問題において式（７３）のように設定する。
【０１２４】
【数４０】
2016157272.tif 000042
【０１２５】
次に、サイト障害が発生している場合、その障害サイトに属するユーザから処理要求は各サイトとは独立に設置された別の仕組み、例えばＤＮＳにより、他のサイトに誘導する。例えば、サイトｋが障害になった場合の設計問題を定式化する場合は、式（７４）のように設定する。
【０１２６】
【数４１】
2016157272.tif 000043
【０１２７】
障害サイトｋで発生した処理要求は、正常な各サイトに式（７５）のようなフロー比率θｋｊで振り分ける。
【０１２８】
【数４２】
2016157272.tif 000044
【０１２９】
ただしＣｋは広域クラウドシステム全体としての障害サイトｋに対する受入れ容量であり、式（７６）のように示される。
【０１３０】
【数４３】
2016157272.tif 000045
【０１３１】
また、サイトｋを除く各サイトではそのサイトでの受入れ容量νｋｊＴ２ｍｋｊ＊を上回る到着率で到着する処理要求は拒否する。これは障害サイトでは拒否する能力が失われているからである。
また誘導装置は、Ｔ２周期毎に、障害サイトｋに属するユーザを、式（７６）で計算されるフロー比率θｋｊに基づいて、サイトｊに振り分ける。
ここで費用係数が満たすべき条件について説明する。式（６４）を目的関数の式（６３）に代入すると、式（７７）のようになる。
【０１３２】
【数４４】
2016157272.tif 000046
【０１３３】
この式で表される利益が、サーバ使用数ｍｉｊを式（４４）の制約の範囲で増加させることで増加できるという技術的に意味のある問題設定をするためには、少なくとも変数ｍｉｊにかかる係数ｑνｉｊＴ１−ｐｊ（ｉ，ｊ＝１，…，Ｉ）のうち少なくとも一つは非負でなければならない。
一方、負の係数がつく（ｉ，ｊ）についてはｍｉｊ＊＝０が最適解になる。よって、全ての（ｉ，ｊ）について係数が負の場合は、サーバ総使用数が０という最適解になってしまう。
【０１３４】
以上のように、グローバル制御装置２によれば、設計処理手段８２が、要求サイトで処理要求の拒否を行うための受入れ容量を決定し、設定処理手段がこれを各サイトのローカル制御装置４に通知する。ローカル制御装置４はサイト内ＬＢ５にこれを設定する。
これにより、サイト内ＬＢ５は、処理要求の要求サイトでその受入れ容量を上回る処理要求を拒否することができ、過剰トラヒックが要求サイトと処理サイトをつなぐネットワークに加える負荷を削減することができる。
また、第１の実施形態は、非特許文献８に対しては以下の効果がある。
１つめは、有効設計容量を導入したことで、ユーザからの一つの処理要求を完結するのに、同一サーバで複数回の処理を実行する必要があるような複雑な処理における応答時間を満たす必要がある場合でも、容量・フロー割当ての設計・制御ができることである。
２つめは、サイト間のネットワーク遅延が変動した場合に、容量割当てはそのままにして、フロー割当てを再設計して拒否量に関するコストを最適化することができることである。
３つめは、サイト間のネットワーク障害、サイト全体の障害が発生してもそれに対処した容量・フロー割当ての設計・制御ができることである。
【０１３５】
次に、本発明の第２の実施形態について、数式を用いて詳細に説明する。
先ず、各要求サイトからみた拒否の公平性を向上させるために、以下の変数を導入する。
φ：各要求サイトでの処理要求を拒否する拒否率の全サイトに関する最大値。
以上より、第２の実施形態における容量割当ての設計問題を、式（７８）〜（８２）の線形計画問題として定式化する。
【０１３６】
【数４５】
2016157272.tif 000047
【０１３７】
第２の実施形態における構成と動作は第１の実施形態と同じである。
本発明の第２の実施形態による効果は、第１の実施形態のものに加えて以下のものがある。すなわち、特に非特許文献８と違って、要求サイトでの拒否率の最大値に基づく拒否量の総和に基づくコストである（ｑΣｉ＝１ＩΛｉＴ１）φを目的関数に含めることで、式（８３）に示される各要求サイトでの実際の拒否率の間で生じる不公平性を抑制できることである。
【０１３８】
【数４６】
2016157272.tif 000048
【０１３９】
次に、第２の実施形態の変形例について説明する。そのために新たな変数を定義する。
ε：容量飽和フラグ。０，１変数であり、少なくとも一つの要求サイトで処理要求の拒否をする必要がある場合は１となり、サーバを全て稼働させるという制約条件を設定するために用いる。
第２の実施形態の変形例における容量割当の設計問題を、式（８４）〜（９１）のように定式化する。
【０１４０】
【数４７】
2016157272.tif 000049
【０１４１】
これは、第２の実施形態での設計問題に特に、制約条件として式（８７）、（８８）および（９１）を加えたものである。式（８７）は拒否率が正、すなわちφ＞０ならばε＝１とするための制約式である。また式（８８）はε＝１ならば、式（８６）と合わせてΣｉ＝１Ｉｍｉｊ＝Ｍｊ（ｊ＝１，…，Ｉ）、すなわち各サイトのサーバは全て稼働されるようにするための制約式である。
【０１４２】
このようにしてこの第２の実施形態の変形例では、目的関数の各係数間にどのような関係があろうとも、少なくとも一つの要求サイトで拒否がある場合は、サーバは各サイトで全て稼働させて処理要求を収容することを実現することができる。
【０１４３】
なお、上述したコンピュータネットワークシステムの設計方法の全部または一部を実行する機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより各部の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【０１４４】
以上、本発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【符号の説明】
【０１４５】
１  広域クラウドシステム
１０１〜１０５サイト
２  グローバル制御装置
３  ネットワーク
４、４１〜４５  ローカル制御装置
５、５１〜５５  サイト間負荷分散装置（サイト間ＬＢ）
６、６１〜６５  サイト内負荷分散装置（サイト内ＬＢ）
７、７１〜７６  処理サーバ（サーバ）
８  データ処理装置
９  記憶装置
８１  設計情報収集手段
８２  設計処理手段
８３  設定処理手段
９１  設計情報記憶部
１０  入出力装置
１５    ユーザ
【図１】
2016157272.tif 000050
【図２】
2016157272.tif 000051
【図３】
2016157272.tif 000052
【図４】
2016157272.tif 000053