(57)【要約】【課題】各エッジ装置と各サーバとの間の網遅延が一般に異なる場合でも、網遅延と処理遅延とからなる総合遅延に関する要求をすべてのエッジ装置とサーバ間で満たすように負荷分散をする。【解決手段】本発明にかかる負荷分散制御方法は、複数のクライアント１からのサービス要求メッセージを集約してサーバ６に振り分ける複数のエッジ装置３と、サービス要求を処理する複数のサーバ６と、制御装置４とがネットワークで接続され、各エッジ装置３は各サーバ６との間で観測されるネットワーク遅延に関する情報を制御装置４に通知し、制御装置４は各エッジ装置３からあるサーバ６までのネットワーク遅延の最悪値を用いてサーバ６の最大許容生起率を決定してそれを各エッジ装置３に通知し、エッジ装置３はサーバ６の最大許容生起率を用いてクライアント１を各サーバ６へ割当てる係数を決定する【選択図】図１
2014103637.tif 000002
【特許請求の範囲】
【請求項１】
複数のクライアントからのサービス要求メッセージを集約してサーバに振り分ける複数のエッジ装置と、クライアントからのサービス要求を処理する複数のサーバと、少なくとも一つの制御装置とがネットワークで接続された負荷分散システムに用いられる負荷分散制御方法であって、
各エッジ装置は各サーバとの間で観測されるネットワーク遅延に関する情報を前記制御装置に通知し、前記制御装置は各エッジ装置からあるサーバまでのネットワーク遅延の最悪値を用いて前記サーバの最大許容生起率を決定してそれを各エッジ装置に通知し、
エッジ装置は前記サーバの最大許容生起率を用いてクライアントを各サーバへ割当てる係数を決定することを特徴とする負荷分散制御方法
【請求項２】
新規サーバが増設された場合は、前記サーバへのクライアントの登録数が他のサーバの登録数と同等レベルになるまで、他のサーバの最大許容生起率は０に設定されることを特徴とする、請求項１記載の負荷分散制御方法。
【請求項３】
前記エッジ装置は、各サーバへのトラヒックを（最大許容生起率）/（エッジ装置総数）に基づいてシェイピングすることを特徴とする請求項１又は２に記載の負荷分散制御方法。
【請求項４】
前記エッジ装置は３GPPのEvolved Packet System（EPS）に準拠したeNodeBであり、サーバは前記EPSに準拠したMMEであることを特徴とする請求項１乃至３のいずれか１項に記載の負荷分散制御方法。
【請求項５】
前記エッジ装置およびサーバは３GPPのIMSに準拠したCSCFであることを特徴とする請求項１乃至３のいずれか１項に記載の負荷分散制御方法。
【請求項６】
複数のクライアントからのサービス要求メッセージを集約してサーバに振り分ける複数のエッジ装置と、クライアントからのサービス要求を処理する複数のサーバと、少なくとも一つの制御装置とがネットワークで接続された負荷分散システムであって、
各エッジ装置は各サーバとの間で観測されるネットワーク遅延に関する情報を前記制御装置に通知し、前記制御装置は各エッジ装置からあるサーバまでのネットワーク遅延の最悪値を用いて前記サーバの最大許容生起率を決定してそれを各エッジ装置に通知し、エッジ装置は前記サーバの最大許容生起率を用いてクライアントを各サーバへ割当てる係数を決定することを特徴とする負荷分散システム
【請求項７】
新規サーバが増設された場合は、前記サーバへのクライアントの登録数が他のサーバの登録数と同等レベルになるまで、他のサーバの最大許容生起率は０に設定する負荷分散制御手段を前記制御装置が備えることを特徴とする、請求項６記載の負荷分散制御システム。
【請求項８】
前記エッジ装置は、各サーバへのトラヒックを（最大許容生起率）/（エッジ装置数）に基づいてシェイピングすることを特徴とする請求項６又は７に記載の負荷分散システム。
【請求項９】
前記エッジ装置は３GPPのEvolved Packet System（EPS）に準拠したeNodeBであり、前記サーバは前記EPSに準拠したMMEであることを特徴とする請求項６乃至８のいずれか１項に記載の負荷分散システム。
【請求項１０】
前記エッジ装置および前記サーバは３GPPのIMSに準拠したCSCFであることを特徴とする請求項６乃至８のいずれか１項に記載の負荷分散システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は負荷分散制御方法・システムに関連し、特に地理的に分散配置された複数のサーバに関する負荷分散制御方法・システムに関する。
【背景技術】
【０００２】
＜輻輳状態と輻輳制御＞
輻輳とは、システムの最大処理能力以上に処理要求のトラヒックが加わり、有効に処理されるトラヒックがシステムの最大処理能力を下回る状態をさす。これは、処理完了ができない要求に対してもシステムの処理能力の一部を割かなければならない等から発生する。以降では、具体的なシステムにおける従来の輻輳制御について記述する。
【０００３】
＜通信ネットワークにおける輻輳制御について＞
固定電話網では、非特許文献１にあるように、災害発生地域に着信呼が集中する場合に、制御系に輻輳崩壊が発生し、電話がつながりづらくなる。これを防止するため、非特許文献１にあるように、一般的な電話交換網では着信側の交換機の状態を制御装置が随時監視して、輻輳状態を検出したら発信側の交換機に規制指示を出す。
【０００４】
3GPP（3rd Generation Partnership Project）のデータ通信網では、非特許文献２にあるように、ユーザ端末を無線回線で終端して、コア網への振り分けを行うeNodeBと呼処理装置のMMEがそれぞれ複数ある場合、各eNodeBと各MMEの間は柔軟に接続できることが提案されている。この接続形態において、各MME（Mobility Management Entity）から通知をうけた相対容量に基づいてMMEの選択をすることで、複数あるMMEでの負荷バランスをとることができる。またMMEは、つながっている無線終端集約装置eNodeBをランダムに選んで、規制率とともに過負荷状態であることを通知できる。
【０００５】
また、非特許文献３では、IMS（IP Multimedia Subsystem）においてCSCF（call/session control function）と総称されるSIPサーバがVOIPの呼処理に使われることが述べられている。この場合、Interrrogating-CSCF（I-CSCF）は網の入り口に位置し、ユーザに対して最終的に呼処理を行うServing-CSCF(S-CSCF)を選択する。
【０００６】
SIPサーバにおける輻輳制御については、非特許文献４にあるように、SIPサーバが輻輳を検知したら、輻輳通知を上流のノードに送信して、そこで入力規制を行う方法が示されている。こうした外部からの入力規制は、一般的なSIPサーバが処理できない呼処理要求に対してエラー応答を返す内部的な制御が輻輳崩壊を根本的に解決できないことへの対処である。
【０００７】
入力規制の具体的な方法としては、サーバに対して送信するサービス要求を一定の割合で廃棄するパーセント廃棄や、一定時間内にサービス要求を送信できる最大数を規制するレート制御がある。
【０００８】
＜サーバ仮想化等における容量計画＞
非特許文献５にもあるように、計算機資源の設定が迅速にできるサーバ仮想化においては、制御装置があって、それがサーバの性能を監視した結果に基づいて必要となるサーバ数を算出し、新たにサーバを増設することができる。これは容量計画とも呼ばれる。
【０００９】
なお非特許文献６には物理サーバのプロビジョニングを行うのみならず、振分け先として利用可能なサーバ情報を負荷分散装置に通知できる管理装置がある。それはさらに、特定のサーバが異常状態もしくは障害状態になる直前の場合、そのサーバ向けへのトラヒックを削減もしくは停止する指示を負荷分散装置に通知する仕組みがある。
【００１０】
<ネットワークレベルの遅延を考慮したサーバへの負荷分散>
一つの負荷分散装置もしくはクライアントから複数のサーバへの負荷分散が非特許文献８に記載されている。これはサーバでの処理遅延に加えてネットワークレベルの処理遅延も含めた総合遅延を測定し、その逆数を各サーバへ振り分けるトラヒック量の比例係数としている。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】K. Mase and H. Yamamoto,"Advanced Traffic Control Methods for Network Management,"IEEE Communication Magazine, pp. 82-88, October 1990.
【非特許文献２】3GPP  TS23.401 V11.1.0 (2012-03)
【非特許文献３】TS 23.228 V11.4.0 (2012-03)  3GPP Technical Specification Group Services and System Aspects;  IP Multimedia Subsystem (IMS); Stage 2 (Release 11)
【非特許文献４】IETF  RFC6357  V. Hilt, E. Noel, C. Shen, and A. Abdelal, "Design consideration for Session Initiation Protocol (SIP) overload control"
【非特許文献５】VMware vCenter Operations  (2011)
【非特許文献６】F5 iControl White paper (2009)
【非特許文献７】R. R. Pillai, "A distributed overload control algorithm for delay-bounded call setup,"IEEE/ACM ToN, Vol.9, No.6, Dec. 2001, pp. 780-789.
【非特許文献８】A. Karakos, D. Patsas, A. Bornea, and S. Kontogiannis,"Balancing HTTP traffic using dynamically updated weights, an implementation approach,"the 10th Panhellenic Conference on Informatics, 2005, pp. 873-878.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
非特許文献８に示されている方法は、振分け係数を決定するのに、各サーバでの応答時間の計測値に基づいている。応答時間はトラヒックの変動があればそれに応じて変動するため、応答時間が小さいサーバにトラヒックを集中させた結果、そのサーバでの応答時間が増大するといった振動現象を起こす恐れがある。
【００１３】
また、非特許文献２では、新規にMMEが増設された場合、既設のサーバへの振分け係数を他よりも十分小さくして、新設されたサーバへ集中的にクライアントを振り分けることが示されているが、それをいつまで行うのか方法が明確にされていない。
【００１４】
本発明の目的は、トラヒックの変動によらず安定した振分け係数を決定する。またサーバが新設されるような場合は、そのサーバに負荷を集中させる期間を明示的に決定する方法を提供する。
【課題を解決するための手段】
【００１５】
本発明の第１の態様にかかる負荷分散制御方法は、複数のクライアントからのサービス要求メッセージを集約してサーバに振り分ける複数のエッジ装置と、クライアントからのサービス要求を処理する複数のサーバと、少なくとも一つの制御装置とがネットワークで接続された負荷分散システムに用いられる負荷分散制御方法であって、各エッジ装置は各サーバとの間で観測されるネットワーク遅延に関する情報を前記制御装置に通知し、前記制御装置は各エッジ装置からあるサーバまでのネットワーク遅延の最悪値を用いて前記サーバの最大許容生起率を決定してそれを各エッジ装置に通知し、エッジ装置は前記サーバの最大許容生起率を用いてクライアントを各サーバへ割当てる係数を決定することを特徴とするものである。
【００１６】
本発明の第２の態様にかかる負荷分散制御システムは、複数のクライアントからのサービス要求メッセージを集約してサーバに振り分ける複数のエッジ装置と、クライアントからのサービス要求を処理する複数のサーバと、少なくとも一つの制御装置とがネットワークで接続された負荷分散システムであって、各エッジ装置は各サーバとの間で観測されるネットワーク遅延に関する情報を前記制御装置に通知し、前記制御装置は各エッジ装置からあるサーバまでのネットワーク遅延の最悪値を用いて前記サーバの最大許容生起率を決定してそれを各エッジ装置に通知し、エッジ装置は前記サーバの最大許容生起率を用いてクライアントを各サーバへ割当てる係数を決定することを特徴とするものである。
【発明の効果】
【００１７】
各サーバの最大収容生起率に基づいて決定される振分け係数をもちいるため、トラヒック変動に対しても振分け係数が振動しない。上記の最大収容生起率は、各エッジ装置と各サーバとの間の網遅延が一般に異なる場合でも、網遅延と処理遅延とからなる総合遅延に関する要求をすべてのエッジ装置とサーバ間で満たすように決定している。よって、各サーバに対して、その最大収容生起率に基づいてシェイピングすれば、各サーバとの間のそれぞれの総合遅延について、同一の要求を満たすことができる。
【図面の簡単な説明】
【００１８】
【図１】全体構成を示すブロック図である。
【図２】制御装置の構成を示すブロック図である。
【図３】エッジ装置の構成を示すブロック図である。
【図４Ａ】収益最大化の最適化問題の解法を説明する図である。
【図４Ｂ】収益最大化の最適化問題の解法を説明する図である。
【図５】制御装置の輻輳制御手段における動作を示す流れ図である。
【図６】制御装置の負荷分散制御手段における動作を示す流れ図である。
【図７】実施の形態において、トラヒック量の変動に対する、廃棄率、サーバ数の軌跡を示すグラフである。
【発明を実施するための形態】
【００１９】
先ず図１を用いてシステム全体の構成について説明する。システム全体は、クライアント１、フロントエンド網２、エッジ装置３、制御装置４、バックエンド網５、サーバ６とからなる。
【００２０】
クライアント１は、サービス利用登録をエッジ装置３によって割り当てられたサーバ６に対して行うとともに、そのサーバ６へ向けてサービスの要求を送信する。サービスの登録に先立ってクライアント１はエッジ装置３を別の何らかの手段で割り当てられる。
【００２１】
フロントエンド網２はクライアント１とエッジ装置３を接続するネットワークである。エッジ装置３はクライアントから受け取ったサービスへの利用登録に対してサーバ６を割り当て、その後クライアントから受け取ったサービス要求メッセージをすでに割り当てられているサーバ６に転送するという負荷分散の機能を持つ。また、エッジ装置３は、クライアント１からのサービス要求メッセージに対する入力規制を行い、サーバ６に加わるトラヒックを削減する。制御装置４は、エッジ装置３、サーバ６との間で輻輳制御、あるいは負荷分散制御に必要となるメッセージをやり取りする。
【００２２】
バックエンド網５は、エッジ装置３、制御装置４、サーバ６の間を接続するネットワークである。サーバ６はエッジ装置３を経由してクライアント１から受信したサービスへの登録、およびその後受信するサービス要求メッセージを処理する。
【００２３】
次に図２を用いて制御装置４の構成について説明する。制御装置４は、入出力手段７と、輻輳制御管理手段８と、負荷分散制御手段１７と、プロビジョニング手段９と、記憶装置１０とからなる。
【００２４】
輻輳制御手段８は、各サーバ６からサービス処理に関して観測された性能情報を受取り、それに基づいてエッジ装置３で用いる規制率、必要なサーバ数等を決定し、各エッジ装置３に規制率や、使用可能なサーバを通知するという資源管理を行う。
【００２５】
負荷分散制御手段１７は、各エッジ装置３からサーバ６へのネットワークレベルの遅延の観測値を受信し、また各サーバ６からクライアント１の登録数を受信して、それに基づいて各サーバ６の最大許容生起率を決定して、各エッジ装置３に通知する。
【００２６】
プロビジョニング手段９は、資源管理手段から指定されたサーバ６に対して、サーバ６の起動、割当てをおこなうための指示メッセージをサーバ６に送る。
【００２７】
記憶装置１０は、稼働中および待機中のサーバ６のアドレスと、サーバ６の処理率（単位時間あたりのサービス要求の処理可能数）と、およびエッジ装置３の各アドレスと、サーバでの観測性能、入力規制率、各エッジ装置３から受信した各サーバ６との間のネットワークレベルの遅延等を保持している。
【００２８】
次に図３を用いてエッジ装置３の構成について説明する。エッジ装置は資源管理手段１１と、入出力装置１２と、入力規制手段１３と、負荷分散手段１４と、複数の転送キュー１５と、読み出し手段１６とからなる。
【００２９】
資源管理手段１１は、制御装置４から送られた規制値を入力規制手段１３に設定する。また制御装置４から送られた各サーバ６の最大許容生起率から割当て係数を決定して、負荷分散手段１４に設定する。さらに、読み出し手段１６で各転送キュー１５に対してシェイピングを行う場合は、そのレートとして前記（サーバの最大許容生起率）/（エッジ装置総数）を転送キュー１５に設定する。
【００３０】
入力規制手段１３における入力規制の方法にはつぎの２つが考えらえる。一つは、規制率φに基づいて、例えばサービス要求メッセージを受信するたびに乱数を振って、その値がφ未満の場合はそのサービス要求メッセージを廃棄もしくは要求拒否メッセージを返送し、乱数を振った値がφ以上のものはサービス要求メッセージの処理を行う。
【００３１】
もうひとつは総量規制であり、リークレートrと、そこからの揺らぎを表すバケットサイズBを２つのパラメータにもつリーキーバケットアルゴリズムに基づいて規制を行う。リーキーバケットは、リークレートrでサイズBのバケツからデータを読み出すことを想定したもので、到着したメッセージのサイズがバケツの空き容量を超えた場合、それは廃棄される。
【００３２】
負荷分散手段１４は、クライアント１からサービス利用登録要求のメッセージがきたら、割当て係数に基づいて決定されたサーバ６をそのクライアント１に割当てる。一度割り当てられたサーバ６は、クライアント１がサービス利用登録を解除をするまでそのクライアント１からのメッセージが転送される。また予め各クライアント１に割当てられたサーバ６に対応する転送キュー１５にクライアント１からのサービス要求メッセージを振り分ける。
【００３３】
負荷分散手段１４は、例えば、クライアント１からのサービス利用登録要求を、割当て係数に従ってサーバ６に割り当てる。そしてその後、そのクライアント１からその後転送されるメッセージはその割り当てられたサーバ６に対応する転送キュー１５に送る。このサービス利用登録は例えば３GPPのAttach、SIPのuser registrationであり、一度割り当てられたらその間のメッセージはすべておなじサーバ６に送られる。転送キュー１５はサーバ毎に設定される。
【００３４】
読み出し手段１６は、資源管理手段１１から設定された振分け係数に基づいてweighted fair queue形式で、転送キュー１５からサービス要求メッセージを読み出すか、あるいは（最大許容生起率）/(エッジ装置数)で決まるレートでシェイピングしてもよい。
【００３５】
（実施の形態の動作）
次に制御装置の資源管理手段での動作について説明する。次のように与えられた目的関数を最適化するように決めたい。
【００３６】
【数１】
2014103637.tif 000003
【００３７】
【数２】
2014103637.tif 000004
【００３８】
いま、サーバのサービス要求メッセージの処理能力はすべて等しいものとする。先ず定数について説明する。aは一つの処理要求を処理完了できた場合に得られる収入、bは稼働中のサーバ１台で単位時間に発生するコストとする。コストは具体的には電力使用量やサーバ管理の手数等に係るものである。λOはエッジ装置全体に加わるサービス要求のトラヒックとする。Dnはサーバnにおいて要求される遅延限界である。
【００３９】
PG[λ,D]は生起率λのトラヒックが、1台のサーバに加わったとき、許容時間D以内にサービスが完了する確率を表す処理完了率を表す関数である。
【００４０】
つぎに変数について説明する。λnはエッジ装置全体に加わるサービス要求のトラヒックのうちサーバnに加わる生起率、Nはサーバ総数、φは各エッジ装置における共通の規制率を表す。
【００４１】
次に、目的関数について説明する。（１−φ）λnは各エッジ装置における入力規制後、サーバnに加わるトラヒックであり、これをスループットと呼ぶ。
【００４２】
そして、（1−φ）λn*PG[（1−φ）λn,Dn]はサーバnにおいて単位時間あたりに処理完了するサービス要求メッセージ数を示し、これはグッドプットとも呼ばれる。すると、目的関数において、a*Σn=1N（1−φ）λn*PG[（1−φ）λn,Dn]は単位時間当たりのサーバ全体での総収入を表す。一方bNは単位時間あたりサーバ全体に発生するコストになるので、式（１）の目的関数は単位時間当たりの総収益を最大化するものとみなせる。
【００４３】
ここで、式（１）はλnについて非線形関数となるため、これを線形近似して、上記最適化問題を容易に解けるようにする。すなわち与えられたdに対して、PG[λ,d]はλに関する減少関数となるので、λ*PG[λ,D]はλに関して最大値をもつ。非特許文献７によれば、生起率λ、処理率μ最大許容遅延DをパラメータにしたM/M/1の待ち行列システムでの処理完了率はPG[λ, D]=1−exp{−(μ−λ)D}で与えられる。そして与えられたDに対して、グッドプットλ* [1−exp{−(μ−λ)D}]の最大値を与えるλ=λmaxの値を示す表も与えられている。これはDが大きくなるほど大きくなることがわかる。また、一般にある待ち行列システムでのλmaxを求めるのは上記のように解析的に導出するだけでなく、サーバに擬似的なトラヒックを加えていって与えられたλに対する遅延分布を求め、更に与えられたDに対してλに対するグッドプットのグラフを、加えてグッドプット算出して求めることも可能である。
【００４４】
λmaxはサーバにこれ以上の生起率を持つサービス要求のトラヒックを受け入れると、グッドプットが低下するので、輻輳崩壊を防ぐにはこれ以上の生起率をもつトラヒックを受け入れるべきではないことを示す値である。よって、λmaxを最大収容生起率とも呼ぶことにする。
【００４５】
上記の議論に基づいて式（１）を線形近似するため、0≦λn(1−φ)≦λnmaxの範囲ではPG[λn(1−φ),Dn]＝1で近似する。これより式（１）、（２）から、
Σn=1Nλn（1−φ）*PG[λn（1−φ）, Dn]
＝（1−φ）Σn=1Nλn
＝ (1−φ)λO
となるので、上記の最適化問題は次のように簡素化できる。
【００４６】
【数３】
2014103637.tif 000005
【００４７】
【数４】
2014103637.tif 000006
【００４８】
λnmaxはサーバnの最大収容生起率とする。サーバ全体で最大収容可能なトラヒックを
【００４９】
【数５】
2014103637.tif 000007
【００５０】
と定義すると、式（２）、（７）より、
Σn=1Nλn (1−φ)＝(1−φ)λO≦Σn=1Nλnmax＝λ[N]、よって、これより新たな制約条件として、
【００５１】
【数６】
2014103637.tif 000008
【００５２】
を得る。  これより上記の最適化問題はさらに次のようにかける。
【００５３】
【数７】
2014103637.tif 000009
【００５４】
【数８】
2014103637.tif 000010
【００５５】
ここで、D1=,..,=DNであり、各サーバに振り分けられるサービス要求の生起率はすべて等しいとすれば、λ1max=,...,=λNmax≡λmaxが得られる。すると式（８）はλ[N]＝λmaxNとなり、式（５）はφ＋N/(λO/λmax) ≧１となる。すると、上記の最適化問題は、下記のように、φとNからなる線形空間における線形関数の最大化問題となる。
【００５６】
【数９】
2014103637.tif 000011
【００５７】
【数１０】
2014103637.tif 000012
【００５８】
図４Ａ及びＢには上記の（N、φ）の平面上で式（１０）、（４）、（７）の制約条件を満たす許容領域を斜線で示してある。
【００５９】
いま、目的関数（６）の値をｃと置いてφについて解くと、φ=−bN/(aλO）+(aλO−c)となってφ切片はaλO−cであるから、cを最大にするには、上記直線のφ切片を許容領域内で最小にすればよい。
【００６０】
その際、以下に示す２つの場合に分けて考える必要がある。一つは、図４Ａに示されている場合、すなわちλO/λmax＜Nmaxならば、ceilを天井関数として、
【００６１】
【数１１】
2014103637.tif 000013
【００６２】
となる。すなわち、エッジ装置３に加わるトラヒックがサーバ６側の最大容量を下回る場合は、規制率は０にして、サーバ総数は、そこに加わるトラヒックを収容できる最小分だけ用意する。
【００６３】
一方、許容領域が図４Ｂで示されている場合、すなわちλO/λmax≧Nmaxならば、
【００６４】
【数１２】
2014103637.tif 000014
【００６５】
となる。すなわち、エッジ装置３に加わるトラヒックがサーバ６側の最大容量を上回る場合は、サーバ６は準備できる最大限Nmaxを稼働させ、それによる容量を上回る分のトラヒックは入力規制することになる。
【００６６】
ここでこの実施の形態によって得られる効果について述べておく。式(１２)より、φは与えられたサーバ台数に対して、規制されるトラヒックの割合を示している。これはNmaxが大きければ大きいほど小さくなる。よって、従来処理容量が固定であったシステムに比べて処理容量を増加させることができれば、入力規制されるトラヒック量を減少させる、あるいは疎通させるトラヒック量を増大させることができるという効果が得られる。
【００６７】
また目的関数の最適値は、上記のN,φの値を式（４）に入れ、さらにNが連続数を取ることができると近似するならば、
λO/λmax＜Nmax の場合は  a*λO−bλO/λmax＝（a−b/λmax）λO、でλとともに増加し、
λO/λmax≧Nmax, の場合は  (a*λmax−b)Nmax  と一定になる。
【００６８】
上記の収益の最大値より、パラメータa,b に関して次のことがわかる。すなわち、与えられたλOに対して収益が正の値をとるためには、aλmax>bである必要がある。これは、サーバを一台用意して最大得られる収入がそのコストを上回る必要があることを意味する。
【００６９】
一方、a*λmax≦bの場合は、Nmaxを増やすと収益が減るので、収益最大化のためには、N max＝１とせざる終えず、サーバを増設することの意味がない。これは図４Ａ及びＢにおいてそれぞれ直線L1,L3に相当する。
【００７０】
上記のように最適化問題を設定しその解に基づいて輻輳制御をするならば、各エッジ装置で観測して得られる生起率λeの総和から得られるλO=Σe=1Eλeに対して、式（１１）もしくは（１２）からサーバ総数Nと、各エッジ装置に共通の入力規制値であるφを決定するだけでよく、非特許文献２と違って、個別のサーバに対して輻輳検出してから個別に入力規制等の制御をかけるといったサーバ個別の対応を行う必要がなくなる。
【００７１】
以上に基づいた制御装置４の輻輳制御手段８による動作を図５の流れ図を用いて詳細に説明する。ここで、各サーバが最大収容可能なサービス要求の生起率はあらかじめ与えられているものとする。
【００７２】
輻輳制御手段８は、各制御区間の終了時に各エッジ装置３から生起率の観測値を収集したら（S1）、各サーバ６から受信した生起率の総和、および現在稼働中のエッジ装置３の数から、式（１１）、（１２）に基づいてサーバ数N、および入力規制パラメータ（廃棄率φもしくはリークレートm）を決定して記憶装置に格納し（S2）、サーバを新たに増設する、もしくは既存サーバを減設する場合はサーバの起動、終了の指示をプロビジョニング手段９に指示してから、稼働中のサーバ６のアドレスを記憶装置１０上で更新する（S3）。そして輻輳制御手段８は、入力規制パラメータと利用可能なサーバのアドレスを記憶装置から読み出してエッジ装置に通知する（S4）。
【００７３】
なおS3に基づいてプロビジョニング手段９から終了の指示を受けたサーバ６は、実際に稼働を終了する前に、すでに登録されているユーザを他のサーバ６に振り替える必要がある。そのために、輻輳制御手段８は直接もしくは間接的に、終了指示をうけたサーバ６に指示して、そのサーバ６に登録されたクライアント１に他のサーバ６への再登録を促す。そしてすべてのクライアント１の他のサーバ６への再登録が終了したら稼働を終了する。
【００７４】
次に、エッジ装置３における負荷分散に関する動作について説明する。その前に、定量的なモデル化について説明する。いまサーバnにおけるサービス完了はエッジ装置３からサーバ６へのネットワーク遅延も含む総合遅延がd以下であれば実現されるとする。
【００７５】
いまエッジ装置e(=1,..,E)からサーバnへのネットワークレベルでの往復遅延RTTe,nに加えてサーバ６での処理遅延tnsrvを加えた総合時間te,n total=tnsrv＋RTTe,nが任意のエッジ装置３とサーバ６の組に対して共通のD以下であれば処理が完了したとみなす。すると、サーバnにおいて処理完了とみなせるためには、
【００７６】
すべてのエッジ装置３に対してtnsrv≦D−RTTe,n    for all e=1,..E、
【００７７】
すなわち、tnsrv≦D−maxe=1,..,ERTTe,n  でなければならない。よって、サーバnにおける処理完了率Pはグッドプットを表す関数を用いて、PG[λn, D−maxe=1,..,ERTTe,n]と書けるので、サーバnにおけるグッドプットはλn*PG[λn,D−maxe=1,..,ERTTe,n]となる。ここで、先に述べたように、グッドプットGP[λ,τ]を最大化するためのλ=λmaxはあらかじめサーバに生起率λの擬似トラヒックを加えて遅延を計測して、λに対する遅延分布を算出し、そこから各τに関するλ=λmaxを求めて例えば表の形式で保持しておくことができる。
【００７８】
上記のグッドプットを最大化するλn =λn maxを制御装置４でテーブルからひかせるためには、τnを算出する必要がある。
【００７９】
これは、エッジ装置３とサーバ間６で測定したRTTを各エッジ装置から収集する。これより、τn=D−maxe=1,..,ERTTe,n  (n=1,..,N)、そしてτnより得られるλnmax（n=1,..,N）をすべてのサーバ６についてエッジ装置３に通知すれば、エッジ装置３はサーバnへの振分け係数を次のように計算できる。
【００８０】
【数１３】
2014103637.tif 000015
【００８１】
エッジ装置は総数がE台あるので、各エッジ装置３では、最大収容生起率がλnmaxであるサーバnからのサービス要求トラヒックに対してピークレートをmn=λnmax/E (n=1,..,N)の値でシェイピングするならば、サーバnには全エッジ装置から高々λnmaxのトラヒックしか加わらないのでサーバnでの輻輳崩壊は防ぐことができる。
【００８２】
なお、新規にサーバ６を増設した直後からは、接続要求の処理に関する負荷レベルを他のサーバ６と同等レベルにより早く持っていく必要がある。そこで新規クライアントの登録をそのサーバ６へ集中的に行わせために次のように振分け係数のつけ方を通常とは違う方法にする。
【００８３】
すなわち制御装置４は、図５を用いて説明した輻輳制御方法に基づいて新規にサーバ６を増設して、プロビジョニング手段９から増設完了の応答を受けた場合は増設モードを設定する。そして新規サーバ６に対する最大許容生起率は例えば１００、他のサーバ６については０として、エッジ装置３に通知する。もしくは制御装置４が他のサーバ６に直接もしくは間接的に指示して、そのサーバ６にサービス登録済みのクライアントを新設したサーバ６へ再登録するように促す。こうした新設サーバ６への集中的なクライアント１の割当ては、例えば新規サーバ６へのクライアント１の登録数が他のサーバ全体でのクライアント登録数の平均値を超えるまで続ける。前記の平均値を算出するために、制御装置４はサーバ６に定期的にアクセスして登録されているクライアント数の情報を受信する。
【００８４】
以上を考慮してエッジ装置３の資源管理手段１１は下記の動作を行う。すなわち、エッジ装置３は各サーバ６にIP pingを飛ばす等により、ネットワークレベルでの往復遅延RTTを測定する。そしてそれが著しく変化した場合は、制御装置４に各サーバ６へのRTTの最悪値のベクトルを送信する。
【００８５】
エッジ装置３は制御装置４から各サーバ６の最大許容生起率λmax=(λ1max,..,λNmax)を受信した場合は、そこから式（１）に基づいて割当て係数を算出して負荷分散手段１４に設定し、またそれを直接転送キュー１５のシェイピングレートに設定する。
【００８６】
次に制御装置４の負荷分散制御手段１７における動作について図６を用いて説明する。サーバプロビジョニング完了応答がプロビジョニング手段９から出力されたら(S11)、増設モードを設定して(S12)、S16に行く。
【００８７】
一定時間後に各エッジ装置３からRTTを受信したら（S13）、負荷分散制御手段１７は、増設モードであるかどうか調べ（S14）、そうである場合はステップ１６に行く。ステップ１４で増設モードでない場合は、負荷分散制御手段１７は利用可能な各サーバ６ついて、RTTに基づくλmaxを算出して、利用可能なサーバのアドレスとともに各エッジ装置３に通知し（S15）して、S13に戻る。
【００８８】
負荷分散制御手段１７は、S16では、一定時間後に各サーバから登録クライアント数を取得し、次に新規サーバのクライアント数が新規サーバ以外の平均クライアント数を超えたかどうか調べ（S17）、超えた場合は増設モードを解除して最大許容生起率は先に説明したグッドプットを最大化するものに設定し（S18）、S13に飛ぶ。S17で超えない場合は新設された以外の既存サーバは最大許容生起率についてλnmax=0を設定、新設されたサーバに対してはλnmax=100を設定してS16に飛ぶ。
【００８９】
上記の動作により、サーバ増設された状態においては、他の既稼働のサーバと同等レベルまでクライアント数が０から増加するまで、そのサーバに集中して新規クライアントが登録されるので、より早く他のサーバとの負荷レベルを等しくすることができる。
【００９０】
また、各サーバに登録されたクライアント数が平準化されている場合は、各エッジ装置３と各サーバ６との間の総合遅延がすべて許容時間を満たすように新たなクライアント１の登録が振り分けられるようになる。
【００９１】
次に本発明の実施の形態における実施例について説明する。
【００９２】
図６はλOが時間的に変化したとき、制御変数であるφ、Nの軌跡をあらわしている。ただし、どのサーバ６の処理率も等しくμとし、エッジ装置３とサーバ６との間のネットワーク遅延はすべて等しいものとする。λOが増加するにしたがって、φ＝０のまま、Nを増やす。N=Nmaxになっても、さらにλが増えていったら、今度は、N=Nmaxのままで、λOの増加とともにφを増加させる。
【００９３】
一方この状態からλが減少を始めると、φも減少させる。そして、φが０になったところさらにλOが減少すれば、φ＝０のまま、Nが削減されることを示している。
【００９４】
本発明は、3GPPのEPCにおいては、eNodeBとMMEをそれぞれエッジ装置とサーバとみなして適応可能である。また、SIPをもちいたIMSにおけるVOIPにおいて、I-CSCFとS-CSCFをそれぞれエッジ装置とサーバとみなしても適応可能である。
【００９５】
次に図７を用いて、複数のエッジ装置３全体に加わるトラヒックλOが時間的に変化した時、制御変数である入力規制率φ及びサーバ数Ｎの値の軌跡を説明する。ただし、どのサーバの処理率も等しくμとし、エッジ装置３とサーバ６との間のネットワーク遅延はすべて等しいものとする。
【００９６】
図７の横軸は時間変化を示す。つまり、横軸を右に行くに従い時間が経過していることを示す。左側の縦軸は、入力規制率φの値を示す。さらに、右側の縦軸は、λOの値を示す。図７においては、サーバ数Ｎを示す軸は存在しないが、グラフの変化によりサーバ数が増減している様子を示す。
【００９７】
図７のＬ１は、λOが時間０から時間Ｔ２まで増加し、時間Ｔ２から時間Ｔ４まで減少している様子を示している。λOが増加している時間０から時間Ｔ１までを低負荷状態とする。さらに、λOが増加している時間Ｔ１からＴ２及びλOが減少している時間Ｔ２からＴ３までを過負荷状態とする。さらに、λOが減少している時間Ｔ３からＴ４までを低負荷状態とする。
【００９８】
図７のＬ２は、サーバ数の推移を示している。時間０から時間Ｔ１までは、λOが増加するに伴い、稼働するサーバ数Ｎを増加させている。ここで、時間Ｔ２において稼働するサーバ数ＮがＮmaxに達した後、過負荷状態であるＴ３までは、サーバ数がＮmaxである状態が継続する。時間Ｔ３からＴ４までは、λOが減少するに伴い稼働するサーバ数Ｎも減少させる。
【００９９】
図７のＬ３は、入力規制率φの値を示している。入力規制率φは、時間０からＴ１までは０に設定されている。つまり、時間Ｔ１までは、入力規制率φを０に設定して稼働するサーバ数を増加させることにより、増加するトラヒックλOに対応している。時間Ｔ１にサーバ数ＮがＮmaxに達した後、増加するトラヒックλOに対して入力規制率φを増加させることにより、１台のサーバ６に送信されるトラヒックの量を調整する。時間Ｔ２から時間Ｔ３の間は、トラヒックλOの減少に伴い入力規制率φも減少させる。時間Ｔ３から時間Ｔ４の間は、入力規制率φを０に設定し、サーバ数Ｎを減少させることにより、減少するトラヒックλOに対応している。
【０１００】
このようにして、本発明における輻輳制御では、増加するトラヒックに対して稼働させるサーバ数を増加させることができる間においては、トラヒックの入力規制は行わず、稼働させるサーバ数が上限に達した場合に、トラヒックの入力規制を行うように制御される。このように制御することにより、処理するサービス要求の数を増加させることができる。
【０１０１】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【符号の説明】
【０１０２】
１  クライアント
２  フロントエンド網
３  エッジ装置
４  制御装置
５  バックエンド網
６  サーバ
７、１２  入出力装置
８  輻輳制御手段
９  プロビジョニング手段
１０  記憶装置
１１  資源管理手段
１３  入力規制手段
１４  負荷分散手段
１５  転送キュー
１６  読出し手段
１７  負荷分散制御部
【図１】
2014103637.tif 000016
【図２】
2014103637.tif 000017
【図３】
2014103637.tif 000018
【図４Ａ】
2014103637.tif 000019
【図４Ｂ】
2014103637.tif 000020
【図５】
2014103637.tif 000021
【図６】
2014103637.tif 000022
【図７】
2014103637.tif 000023