(57)【要約】【課題】各サーバの負荷をおおむね均等にしながら、地理的に近いクライアント端末群をなるべく同一サーバに振り分ける。【解決手段】負荷分散装置２０は、所定平面を区分した格子ごとに、所定期間における当該格子内のクライアント端末１０からの要求量をカウントし、要求量情報保持テーブルを作成する。次に、負荷分散装置２０は、格子の集合である部分領域を、各部分領域における要求量がおおむね均等になる部分領域を格子の集合として設計した部分領域情報保持テーブルを生成する。そして、クライアント端末１０からの要求を受け付けたとき、部分領域情報保持テーブルを参照し、クライアント端末１０の位置に対応する部分領域情報をキーとして要求の振り分け先のサーバ３０を決定する。【選択図】図２
2015201029.tif 000002
【特許請求の範囲】
【請求項１】
複数のサーバにより負荷分散を行う分散処理システムにおいて、クライアント端末からの要求をいずれかのサーバへ振り分ける負荷分散装置であって、
前記クライアント端末からの要求を受け付ける要求受け付け部と、
所定平面を区分した領域ごとに、所定期間における当該領域内に位置するクライアント端末からの要求量をカウントする要求量カウント部と、
前記平面上の領域の集合である部分領域を、各部分領域における前記要求量ができるだけ均等になるように決定し、前記決定した部分領域と、前記部分領域の識別情報とを対応付けた部分領域情報保持テーブルを生成する部分領域決定部と、
前記クライアント端末からの要求を受け付けたとき、前記部分領域情報保持テーブルを参照して、前記クライアント端末の属する部分領域の識別情報に対応するサーバへ前記要求を振り分ける要求振り分け部と、
を備えることを特徴とする負荷分散装置。
【請求項２】
前記部分領域決定部は、
前記サーバの負荷が増加したとき、前記部分領域数を増加させることを特徴とする請求項１に記載の負荷分散装置。
【請求項３】
前記要求振り分け部は、
前記サーバへ要求を振り分けるとき、前記要求に、読み出した部分領域の識別情報を含めることを特徴とする請求項１または２に記載の負荷分散装置。
【請求項４】
前記要求振り分け部は、
前記要求の振り分け先のサーバを決定するとき、前記部分領域の識別情報をキーとしたコンシステント・ハッシュ法により決定することを特徴とする請求項１〜３のいずれか１項に記載の負荷分散装置。
【請求項５】
前記領域は、所定平面を格子状に区分した領域であることを特徴とする請求項１〜４のいずれか１項に記載の負荷分散装置。
【請求項６】
前記要求量カウント部は、
前記所定期間経過後、前記領域ごとの前記クライアント端末からの要求量を再度カウントすることを特徴とする請求項１〜５のいずれか１項に記載の負荷分散装置。
【請求項７】
複数のサーバにより負荷分散を行う分散処理システムにおいて、クライアント端末からの要求をいずれかのサーバへ振り分ける負荷分散装置が、
前記クライアント端末からの要求を受け付けるステップと、
所定平面を区分した領域ごとに、所定期間における当該領域内に位置するクライアント端末からの要求量をカウントするステップと、
前記平面上の領域の集合である部分領域を、各部分領域における前記要求量ができるだけ均等になるように決定し、前記決定した部分領域と、前記部分領域の識別情報とを対応付けた部分領域情報保持テーブルを生成するステップと、
前記クライアント端末からの要求を受け付けたとき、前記部分領域情報保持テーブルを参照して、前記クライアント端末の属する部分領域の識別情報に対応するサーバへ前記要求を振り分けるステップと、
を実行することを特徴とする負荷分散方法。
【請求項８】
クライアント端末からの要求をいずれかのサーバへ振り分ける負荷分散装置と、前記要求の振り分け先となるサーバとを備える負荷分散システムであって、
前記負荷分散装置は、
前記クライアント端末からの要求を受け付ける要求受け付け部と、
所定平面を区分した領域ごとに、所定期間における当該領域内に位置するクライアント端末からの要求量をカウントする要求量カウント部と、
前記平面上の領域の集合である部分領域を、各部分領域における前記要求量ができるだけ均等になるように決定し、前記決定した部分領域と、前記部分領域の識別情報とを対応付けた部分領域情報保持テーブルを生成する部分領域決定部と、
前記クライアント端末からの要求を受け付けたとき、前記部分領域情報保持テーブルを参照して、前記クライアント端末の属する部分領域の識別情報に対応するサーバへ前記要求を振り分ける要求振り分け部と、
を備えることを特徴とする負荷分散システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、負荷分散装置、負荷分散方法、および、負荷分散システムに関する。
【背景技術】
【０００２】
クライアント端末からの要求を処理するサーバシステムにおいて、クライアント端末からの要求量が多く、単一のサーバでは処理できない場合、クライアント端末とサーバシステムの間に負荷分散装置を設置し、負荷分散装置が複数のサーバに要求を振り分けることが広く行われている。
【０００３】
負荷分散装置における負荷分散手法として、例えば、非特許文献１に記載されているコンシステント・ハッシュ法等のように、要求中に含まれる属性情報をキーとして振り分け先のサーバを決定することで、同じ属性情報を含む要求を同一のサーバに振り分ける手法が知られている。
【０００４】
また、クライアント端末からの要求に位置情報が含まれる場合に、その位置情報から、クライアント端末とネットワーク上の距離が近いサーバを特定し、当該サーバに要求を振り分ける技術も知られている。
【０００５】
また、特許文献１には、キーの要求頻度に応じて、要求頻度の高いキーは複数のサーバに、要求頻度の低いキーは単一のサーバに振り分けを行う負荷分散手法に関する技術が記載されており、本技術によれば、例えば、各クライアント端末が送信する要求の量が均一でない場合でも、振り分け先のサーバの負荷をおおむね均一にすることができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１３−１５２５６９号公報
【非特許文献】
【０００７】
【非特許文献１】D.  Karger他、"Consistent  Hashing  and  Random  Trees:  Distributed  Caching  Protocols  for  Relieving  Hot  Spots  on  the  World  Wide  Web"  in  Proceedings  of  the  29th  ACM  Symposium  on  Theory  of  Computing  (STOC'97)、pp.654-663、May  1997.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ここで、例えば、クライアント端末が送信するセンサ情報を処理するサーバシステム等においては、要求量の観点から複数のサーバでの処理が必要となる一方で、地理的に近いクライアント端末群からのセンサ情報はなるべく単一のサーバで処理したいという要件がある。
【０００９】
こうした要件に対して、例えば、非特許文献１に記載されている負荷分散方式を適用し、要求に含まれる位置情報をキーとした負荷分散を行うことで、地理的に近いクライアント端末群を同一のサーバに収容することが可能である。しかし、クライアント端末は必ずしも一様に分布せず、また各クライアント端末が送信する要求量も均一ではない場合、等しい面積の領域を各サーバに割り当てたとしても、サーバの負荷が著しく偏ってしまう場合がある。
【００１０】
このようにサーバ負荷が著しく偏ると、サーバのコンピューティングリソースを有効に活用できず、結果として、本来必要な数以上のサーバ数が必要になってしまうという問題がある。
【００１１】
また一方で、特許文献１で開示されている負荷分散方式では、サーバの負荷をおおむね均一にすることはできるが、この場合、地理的に近いクライアント端末群の要求が複数のサーバに振り分けられてしまい、上記の要件を満たすことができないという問題がある。
【００１２】
そこで本発明は、前記した問題を解決し、各サーバの負荷をおおむね均等にしつつ、地理的に近いクライアント端末群をなるべく同一サーバに振り分けることを目的とする。
【課題を解決するための手段】
【００１３】
上述した課題を解決し、目的を達成するために、本発明は、複数のサーバにより負荷分散を行う分散処理システムにおいて、クライアント端末からの要求をいずれかのサーバへ振り分ける負荷分散装置であって、前記クライアント端末からの要求を受け付ける要求受け付け部と、所定平面を区分した領域ごとに、所定期間における当該領域内に位置するクライアント端末からの要求量をカウントする要求量カウント部と、前記平面上の領域の集合である部分領域を、各部分領域における前記要求量ができるだけ均等になるように決定し、前記決定した部分領域と、前記部分領域の識別情報とを対応付けた部分領域情報保持テーブルを生成する部分領域決定部と、前記クライアント端末からの要求を受け付けたとき、前記部分領域情報保持テーブルを参照して、前記クライアント端末の属する部分領域の識別情報に対応するサーバへ前記要求を振り分ける要求振り分け部と、を備えることを特徴とする。
【発明の効果】
【００１４】
本発明によれば、各サーバの負荷をおおむね均等にしつつ、地理的に近いクライアント群をなるべく同一サーバに振り分けることができる。
【図面の簡単な説明】
【００１５】
【図１】図１は、負荷分散システムの構成の一例を示す図である。
【図２】図２は、負荷分散システムの処理の概要を説明する図である。
【図３】図３は、負荷分散装置の処理の概要を説明する図である。
【図４】図４は、負荷分散装置の機能ブロック図である。
【図５】図５は、要求量情報保持テーブルの一例を示す図である。
【図６】図６は、部分領域情報保持テーブルの一例を示す図である。
【図７】図７は、要求量のカウントから部分領域の決定までの処理手順を示すシーケンス図である。
【図８】図８は、部分領域決定処理の詳細を示すフローチャートである。
【図９】図９は、要求の振り分けの処理手順を示すシーケンス図である。
【図１０】図１０は、要求処理サーバ決定処理の詳細を示すフローチャートである。
【図１１】図１１は、部分領域数保持テーブルの一例を示す図である。
【図１２】図１２は、部分領域数の増加手順を示すシーケンス図である。
【図１３】図１３は、負荷分散プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１６】
以下、図面を参照しながら、本発明を実施するための形態（実施形態）について説明する。
【００１７】
（システム構成）
まず、図１を用いて本実施形態の負荷分散システムの構成を説明する。負荷分散システムは、クライアント端末１０（１０Ａ〜１０Ｄ）と、負荷分散装置２０と、サーバ３０（３０Ａ〜３０Ｄ）とを備える。負荷分散システムにおいて、クライアント端末１０と負荷分散装置２０とは、例えば、ネットワーク４１により接続され、負荷分散装置２０とサーバ３０とはネットワーク４２により接続される。ネットワーク４１，４２は、例えば、ＩＰ（Internet  Protocol）ネットワークである。それぞれの台数は図１に示す台数に限定されない。
【００１８】
クライアント端末１０は、負荷分散装置２０経由でサーバ３０に対しサービス要求（以下適宜、要求と略す）を送信する。このクライアント端末１０は、例えば、当該クライアント端末１０の備えるセンサ情報と、例えば、ＧＰＳ（Global  Positioning  System）等で取得した自身の位置情報とを含む要求を負荷分散装置２０へ送信する。
【００１９】
負荷分散装置２０は、クライアント端末１０からの要求を受信すると、このクライアント端末１０の位置情報をもとに当該要求をいずれかのサーバ３０に振り分ける。
【００２０】
サーバ３０は、負荷分散装置２０経由でクライアント端末１０からの要求を受信すると、当該要求に基づく処理を実行する。例えば、サーバ３０は、受信した要求に含まれるセンサ情報に対し、当該要求に含まれるクライアント端末１０の部分領域情報に基づき統計処理等のアプリケーションロジックを実施する。具体例を挙げると、サーバ３０は同じ部分領域情報を持つ要求（例えば、地理的に近いクライアント端末１０からの要求）に含まれるセンサ情報をまとめ、これらのセンサ情報に対し統計処理等を行う。なお、このサーバ３０の設置台数は、例えば、負荷分散装置２０に到達する全要求量に応じて、各サーバ３０の平均負荷が８０％程度となるような台数とする。
【００２１】
（処理の概要）
図２を用いて負荷分散システムの処理の概要を説明する。負荷分散システムの負荷分散装置２０はクライアント端末１０からの要求を受信すると、この要求をいずれかのサーバ３０に振り分ける。そして、サーバ３０では受信した要求に基づく処理を実行する。このクライアント端末１０からの要求には、例えば、クライアント端末１０の識別情報（例えば、ＩＰ（Internet  Protocol）アドレス等）、クライアント端末１０の位置情報等が含まれる。負荷分散装置２０は、クライアント端末１０からの要求に含まれる識別情報や位置情報に基づき、要求の振り分け先のサーバ３０を決定するが、ここでの振り分け先のサーバ３０の決定は以下のようにして行う。
【００２２】
すなわち、まず、負荷分散装置２０は、クライアント端末１０の位置情報をもとにクライアント端末１０の分布を示す情報を作成する。例えば、符号１０１に示すように所定平面上におけるクライアント端末１０の分布を示した情報を作成する。その後、負荷分散装置２０は、図２に示すように当該平面を所定数の格子に区分し、それぞれの格子単位で所定期間における要求量をカウントする（符号１０２参照）。これにより格子内のクライアント端末１０それぞれからの所定期間における要求量が得られる。この格子単位での要求量のカウント結果を示した情報を要求量情報保持テーブルと称す（図５参照）。
【００２３】
その後、負荷分散装置２０は、要求量情報保持テーブルにおける要求量がおおむね均等となる部分領域を格子の集合として設計する。例えば、負荷分散装置２０は要求量がおおむね均等となる格子の集合として、符号１０３に示す９つの部分領域を設計する。なお、部分領域に添えられた、Ａ１、Ａ２、Ａ３、Ｂ１、Ｂ２、Ｂ３、Ｃ１、Ｃ２、Ｃ３は部分領域の識別情報（部分領域情報）である。
【００２４】
負荷分散装置２０はこのようにして得られた情報（部分領域情報保持テーブル）を参照して振り分け先のサーバ３０を決定する。
【００２５】
例えば、負荷分散装置２０は、クライアント端末１０から要求を受信すると、部分領域情報保持テーブルを参照して、受信した要求について所属する部分領域を判定する。例えば、負荷分散装置２０は、受信した要求の所属する部分領域が「Ａ２」であると判定する。そして、負荷分散装置２０は部分領域の判定結果（例えば、「Ａ２」）をもとに、コンシステント・ハッシュ法で当該部分領域に対応するサーバ３０を選択し、この選択したサーバ３０を振り分け先のサーバ３０として決定する。これにより、同じ部分領域に属する要求は同じサーバに振り分けられることになる。この後、負荷分散装置２０は振り分け先のサーバ３０へ要求を転送する。なお、負荷分散装置２０は、クライアント端末１０からの要求に、当該クライアント端末１０に対応する部分領域の情報（部分領域情報）を付加して転送してもよい。その後、サーバ３０は、転送された要求について、例えば、部分領域単位でアプリケーションロジックを実施する。
【００２６】
（処理の詳細）
図３を用いて、負荷分散装置２０における処理を詳細に説明する。ここでは、クライアント端末１０Ａとクライアント端末１０Ｂとが地理的に近く、クライアント端末１０Ｃとクライアント端末１０Ｄとが地理的に近いものとする。
【００２７】
負荷分散装置２０は所定期間における各格子内の領域のクライアント端末１０の要求量をカウントし、そのカウント結果を要求量情報保持テーブルに記録する。そして、負荷分散装置２０は、この要求量情報保持テーブルにおける要求量がおおむね均等となる部分領域を決定し、例えば、図３に示す部分領域情報保持テーブルを得る。
【００２８】
その後、負荷分散装置２０は、クライアント端末１０からの要求を受け付けると、このクライアント端末１０の属する格子の位置に対応する部分領域情報を読み出し、要求を振り分ける。例えば、負荷分散装置２０がクライアント端末１０Ａ（（Ｘ，Ｙ）＝（２，２））からの要求を受け付けたとき、この（Ｘ，Ｙ）＝（２，２）に対応する部分領域情報「Ａ１」を読み出し、この「Ａ１」に対応するサーバ３０（例えば、サーバ３０Ｂ）へ要求を振り分ける。また、負荷分散装置２０がクライアント端末１０Ｂ（（Ｘ，Ｙ）＝（２，３））からの要求を受け付けたとき、この（Ｘ，Ｙ）＝（２，３）に対応する部分領域情報「Ａ１」を読み出し、この「Ａ１」に対応するサーバ３０（例えば、サーバ３０Ｂ）へ要求を振り分ける。その結果、地理的に近いクライアント端末１０Ａ，１０Ｂからの要求は同じサーバ３０Ｂへ振り分けられる。
【００２９】
また同様に、例えば、負荷分散装置２０がクライアント端末１０Ｃ（（Ｘ，Ｙ）＝（５，４））からの要求を受け付けたとき、この（Ｘ，Ｙ）＝（５，４）に対応する部分領域情報「Ｂ２」を読み出し、この「Ｂ２」に対応するサーバ３０（例えば、サーバ３０Ｃ）へ要求を振り分ける。また、負荷分散装置２０がクライアント端末１０Ｄ（（Ｘ，Ｙ）＝（５，５））からの要求を受け付けたとき、（Ｘ，Ｙ）＝（５，５）に対応する部分領域情報「Ｂ２」を読み出し、この「Ｂ２」に対応するサーバ３０（例えば、サーバ３０Ｃ）へ要求を振り分ける。その結果、地理的に近いクライアント端末１０Ｃ，１０Ｄからの要求は同じサーバ３０Ｃへ振り分けられる。
【００３０】
（構成）
次に、図４を用いて、負荷分散装置２０の構成を説明する。負荷分散装置２０は、入出力部２１と、制御部２２と、記憶部２３とを備える。
【００３１】
入出力部２１は、外部装置との間での各種情報の入出力を司る。例えば、入出力部２１は、クライアント端末１０からの要求を受信したり、当該要求をサーバ３０へ転送したりする。この入出力部２１は、例えば、ネットワーク４１，４２経由で通信を行うための通信インタフェースにより実現される。
【００３２】
制御部２２は、負荷分散装置２０全体の制御を司り、要求受け付け部２２１と、要求量カウント部２２２と、部分領域決定部２２３と、要求振り分け部２２４とを備える。破線で示した部分領域数更新部２２５は装備する場合と装備しない場合とがあり、装備する場合については後記する。
【００３３】
要求受け付け部２２１は、入出力部２１経由でクライアント端末１０からの要求を受け付ける。
【００３４】
要求量カウント部２２２は、要求の送信元のクライアント端末１０の位置情報に基づき、所定期間における各クライアント端末１０からの要求量を領域ごとにカウントする。つまり、要求量カウント部２２２は、要求の送信元の各クライアント端末１０の位置情報をもとに、所定平面を区切った領域（例えば、格子状の領域）上で、各クライアント端末１０がどの領域に属するかを判定する。そして、要求量カウント部２２２は、この領域ごとに、所定期間における当該領域に属するクライアント端末１０からの要求量をカウントし、そのカウント結果を要求量情報保持テーブル（図５参照）に書き込む。
【００３５】
なお、以下では、領域の形状は、格子である場合を例に説明するが、格子以外の形状であってもよい。また、平面をいくつの領域に分割するかは、負荷分散装置２０の処理性能に応じて予め設定されているものとする。例えば、負荷分散装置２０の処理能力が比較的高ければ、領域数を多く設定しておく。
【００３６】
部分領域決定部２２３は、前記した所定平面上の領域（例えば、格子状の領域）の集合である部分領域を、各部分領域における要求量ができるだけ均等になるように決定する。そして、部分領域決定部２２３は、決定した部分領域と、当該部分領域の識別情報とを対応付けた部分領域情報保持テーブル（図６参照）を生成する。生成した要求量情報保持テーブルは、記憶部２３に格納する。なお、部分領域決定部２２３が決定する部分領域数は、少なくとも負荷分散システムにおけるサーバ３０の数以上とする。この部分領域決定部２２３の処理の詳細は具体例を交えながら後記する。
【００３７】
要求振り分け部２２４は、クライアント端末１０からの要求をいずれかのサーバ３０に振り分ける。例えば、要求振り分け部２２４は、クライアント端末１０からの要求を受け付けたとき、部分領域情報保持テーブルからクライアント端末１０の位置に対応する部分領域情報を読み出す。そして、要求振り分け部２２４は、この部分領域情報をキーとして、コンシステント・ハッシュ法等により、このキーに対応するサーバ３０を決定する。そして、要求振り分け部２２４は、クライアント端末１０からの要求を当該決定したサーバ３０へ送信（転送）する。なお、要求振り分け部２２４がサーバ３０へ要求を送信するとき、部分領域情報保持テーブルから読み出した部分領域情報を含めて送信してもよい。
【００３８】
記憶部２３は、要求量情報保持テーブルと、部分領域情報保持テーブルとを所定領域に記憶する。破線で示す部分領域数保持テーブルについては、後記する。
【００３９】
要求量情報保持テーブルは、所定の平面を区分した領域ごとに、所定期間における当該領域内のクライアント端末１０からの要求量のカウント結果を示す情報である。この要求量情報保持テーブルの一例を図５に示す。図５に示す要求量情報保持テーブルは、座標平面をＸ軸、Ｙ軸それぞれ８つに分割し、計６４個の領域（格子）からなる。各格子内の数値は、所定期間における、当該格子（領域）内の各クライアント端末１０からの要求数の合計値である。この要求量情報保持テーブルは要求量カウント部２２２によるカウント結果に基づき更新される。この要求量情報保持テーブルは、記憶部２３上において、二次元配列として記憶される。
【００４０】
部分領域情報保持テーブルは、部分領域決定部２２３により決定された部分領域と、当該部分領域の識別情報とを対応付けた情報である。この部分領域情報保持テーブルの一例を図６に示す。図６に示す部分領域情報保持テーブルは、図５に示す要求量情報保持テーブルの格子全体を、Ｘ軸、Ｙ軸それぞれ３つに分割することで得られた９つの部分領域を示す。部分領域に添えられた、Ａ１、Ａ２、Ａ３、Ｂ１、Ｂ２、Ｂ３、Ｃ１、Ｃ２、Ｃ３は部分領域の識別情報（部分領域情報）である。この部分領域情報保持テーブルは、要求振り分け部２２４が要求の振り分け先のサーバ３０を決定する際に参照される。
【００４１】
このような負荷分散装置２０によれば、負荷分散システムの各サーバ３０の負荷をおおむね均等にしながら、地理的に近いクライアント端末１０群をなるべく同一サーバに振り分けることができる。
【００４２】
（処理手順）
次に、負荷分散システムの処理手順を説明する。なお、以下に説明する、要求量のカウントから部分領域の決定までの処理と、要求の振り分け処理とは、それぞれ並列に実行されるものとする。まず、図７を用いて、要求量のカウントから部分領域の決定までの処理手順を説明する。
【００４３】
負荷分散装置２０の要求受け付け部２２１が、クライアント端末１０からの要求を受信すると（Ｓ１）、要求量カウント部２２２は、要求量のカウント処理を行う（Ｓ２）。このＳ１、Ｓ２の処理を繰り返す。つまり、要求量カウント部２２２は、クライアント端末１０から送信される要求数のカウントを継続的に実施する。そして、要求量カウント部２２２は、要求量情報保持テーブルにクライアント端末１０からの要求量を書きこむ。要求量カウント部２２２は、予めクライアント端末１０が位置する座標平面を、例えば、格子状に区分けしておき、要求に含まれるクライアント端末１０の位置情報（例えば、ＧＰＳで取得した緯度・経度の情報等）から、クライアント端末１０の位置がどの格子に対応しているか判定し、格子ごとの要求量をカウントする。Ｓ２の後、負荷分散装置２０の部分領域決定部２２３は、要求量情報保持テーブルの情報をもとに部分領域決定処理を行う（Ｓ３）。
【００４４】
次に、図７のＳ３の部分領域決定処理を詳細について、図８を用いて説明する。ここでは要求量情報保持テーブルに示される格子全体を、Ｘ軸、Ｙ軸それぞれについて３つに分割し（つまり、Ｘ軸、Ｙ軸それぞれに２箇所の境界を入れ）、合計９つの部分領域を作成する場合を例に説明する。
【００４５】
まず、部分領域決定部２２３は、要求量情報保持テーブル（図５参照）に示される平面のＸ軸について、動的計画法により、部分領域の境界を決定する（Ｓ３０１）。具体的には、部分領域決定部２２３は、Ｙ軸を分割しない前提で、各部分領域の要求量の分散を最小化する境界を、動的計画法により決定する。
【００４６】
次に、部分領域決定部２２３は、Ｓ３０１で決定したＸ軸の境界を固定して、Ｙ軸について動的計画法により、部分領域の境界を決定する（Ｓ３０２）。具体的には、部分領域決定部２２３は、Ｙ軸について、各部分領域の要求量の分散を最小化する境界を、動的計画法により決定する。
【００４７】
次に、部分領域決定部２２３は、Ｓ３０２で決定したＹ軸の境界を固定して、改めてＸ軸について、各部分領域の要求量の分散を最小化する境界を、動的計画法により決定する（Ｓ３０３）。
【００４８】
次に、部分領域決定部２２３は、Ｓ３０３の処理により、各部分領域の要求量の分散値が改良されたか否かを判定する（Ｓ３０４）。つまり、部分領域決定部２２３は、Ｓ３０３の処理により計算された各部分領域の要求量の分散値が、前回計算された値よりも下がったか否かを判定する。
【００４９】
ここで、各部分領域の要求量の分散値の改良がされていなければ（Ｓ３０４でＮｏ）、
部分領域決定部２２３は、Ｓ３０２、Ｓ３０３で決定したＸ軸、Ｙ軸の境界に基づいて、部分領域情報保持テーブルを更新する（Ｓ３０５）。一方、Ｓ３０４で分散値が改良されていた場合（Ｓ３０４でＹｅｓ）、Ｓ３０２へ戻る。つまり、部分領域決定部２２３は、部分領域の境界を変更させながら、各部分領域の要求量ができるだけ均等になるような部分領域を探索する。そして、部分領域決定部２２３は、各部分領域の要求量ができるだけ均等になるような部分領域を発見すると、Ｓ３０２、Ｓ３０３で決定したＸ軸、Ｙ軸の境界に基づいて、部分領域情報保持テーブルに各格子の部分領域情報を格納する（図６参照）。
【００５０】
部分領域決定部２２３は、上記の処理を、例えば、所定期間ごとに実行する。また、要求量情報保持テーブルに示される要求量の値は、部分領域が決定されるとリセットされるものとする。
【００５１】
部分領域決定部２２３が上記の処理を行うことで、各部分領域の要求量をできるだけ均等にするような部分領域を決定することができる。また、部分領域決定部２２３は、上記の処理を所定期間ごとに実施するので、クライアント端末１０の増減や移動等による要求量の分布の変化があった場合、このような変化を反映させた部分領域を決定することができる。
【００５２】
次に、図９を用いて、負荷分散装置２０がクライアント端末１０からの要求の振り分けを行う手順を説明する。
【００５３】
負荷分散装置２０の要求受け付け部２２１は、クライアント端末１０からの要求を受信すると（Ｓ５０１）、負荷分散装置２０の要求振り分け部２２４は、部分領域情報保持テーブルを参照して、当該要求を処理するサーバ３０を決定する（Ｓ５０２：要求処理サーバ決定処理）。そして、要求振り分け部２２４は決定したサーバ３０へ要求を送信する（Ｓ５０３）。この要求を受信したサーバ３０は、受信した要求に基づく処理を実行する（Ｓ５０４：サービス要求処理）。例えば、サーバ３０は、受信した要求に含まれるセンサ情報を、当該要求に含まれる部分領域情報ごとにまとめ、統計処理等を行う。
【００５４】
以下、図１０を用いて、図９のＳ５０２の要求処理サーバ決定処理の詳細を説明する。
【００５５】
まず、要求振り分け部２２４は、クライアント端末１０から送信された要求に含まれる位置情報から、当該要求の送信元のクライアント端末１０の位置に対応する格子（領域）を特定する（Ｓ６０１）。つまり、要求振り分け部２２４は、要求の送信元のクライアント端末１０の位置に対応する部分領域情報保持テーブル上の格子（領域）を特定する。
【００５６】
その後、部分領域決定部２２３はクライアント端末１０の属する格子（領域）の部分領域情報を部分領域情報保持テーブルから取得する（Ｓ６０２）。
【００５７】
例えば、クライアント端末１０の位置に対応する部分領域情報保持テーブル（図６参照）上の位置が（Ｘ，Ｙ）＝（５，４）であった場合、要求振り分け部２２４は部分領域情報保持テーブルから部分領域情報として「Ｂ２」を取得する。
【００５８】
次に、部分領域決定部２２３は取得した部分領域情報をキー（例えば、「Ｂ２」）として、コンシステント・ハッシュ法により、要求の送信先のサーバ３０を決定する（Ｓ６０３）。
【００５９】
このようにすることで、要求振り分け部２２４は部分領域情報保持テーブルを参照して要求振り分け先のサーバ３０を決定することができる。
【００６０】
（その他の実施形態）
なお、負荷分散装置２０は負荷分散システムのいずれかのサーバ３０から負荷が所定の閾値（例えば、当該サーバ３０の処理性能の９５％）を超えた旨の通知を受信したとき、部分領域情報保持テーブルにおける部分領域数を増加させてもよい。
【００６１】
この場合、負荷分散装置２０は、図４に示す部分領域数更新部２２５をさらに備える。また、負荷分散装置２０の記憶部２３は、さらに部分領域数保持テーブルを記憶する。
【００６２】
部分領域数更新部２２５は、サーバ３０から負荷が所定の閾値を超えた旨の通知（サーバ負荷閾値超過通知）を受信したとき、部分領域数保持テーブルにおける部分領域数を増加させる。
【００６３】
部分領域数保持テーブルは、部分領域数を示す情報である。この部分領域数は、例えば、部分領域情報保持テーブルの部分領域の区切り目となるＸ軸、Ｙ軸の境界の数の組み合わせで示される（図１１参照）。図１１に例示する部分領域数保持テーブルは、部分領域情報保持テーブルの部分領域の区切り目となるＸ軸、Ｙ軸の境界の数がそれぞれ「８」であることを示す。部分領域数保持テーブルは、部分領域決定部２２３が部分領域を決定する際に参照される。つまり、部分領域数保持テーブルが更新されると、部分領域決定部２２３は、現在の部分領域情報保持テーブルをリセットし、部分領域数保持テーブルに示される部分領域数となるように再度部分領域を決定する。
【００６４】
図１２を用いて、負荷分散装置２０における部分領域数の増加手順を説明する。負荷分散装置２０の部分領域数更新部２２５は、サーバ３０からサーバ負荷閾値超過通知を受信すると（Ｓ４０１）、部分領域数加算処理を行う（Ｓ４０２）。つまり、部分領域数更新部２２５は部分領域数保持テーブルの値を増加させる。
【００６５】
例えば、図１１の部分領域数保持テーブルに示すように、部分領域の境界数が、Ｘ軸、Ｙ軸それぞれについて「８」であった場合、部分領域数更新部２２５は、Ｘ軸の境界数を「８」から「９」に更新する。そして、部分領域決定部２２３は、現在の部分領域情報保持テーブルをリセットし、更新された部分領域数保持テーブルに示される部分領域数（Ｘ軸の境界数が「９」）となるように再度部分領域を決定する。
【００６６】
なお、部分領域数更新部２２５が、さらに継続してサーバ負荷閾値超過通知を受信した場合は、さらに部分領域数加算処理を行う。例えば、部分領域数更新部２２５は、Ｙ軸の境界数を「８」から「９」に更新する。そして、部分領域決定部２２３は、現在の部分領域情報保持テーブルをリセットし、更新された部分領域数保持テーブルに示される部分領域数（Ｘ軸、Ｙ軸の境界数が「９」）となるように再度部分領域を決定する。以降、サーバ負荷閾値超過通知を受信するたびに、Ｘ軸、Ｙ軸の境界数を交互に加算していく。
【００６７】
このように負荷分散装置２０がサーバ負荷閾値超過通知を受信するたびに部分領域数を増加させることで、サーバ３０間の負荷の偏りを減少できる可能性を高めることができる。
【００６８】
なお、負荷分散システムのサーバ３０の増設または減設が行われたときは、負荷分散装置２０は部分領域数を最小値（負荷分散システムのサーバ３０の台数）にリセットするものとする。
【００６９】
また、前記した実施形態において、クライアント端末１０から送信される要求には、当該クライアント端末１０の位置情報が含まれるものとして説明したが、これに限定されない。例えば、クライアント端末１０が固定的に設置され、移動しない場合には、各要求に位置情報を含める必要はない。この場合、負荷分散装置２０は予めクライアント端末１０の識別情報（例えば、ＩＰアドレス）と、位置情報との対応関係を示す情報を保持しておき、この情報をもとにクライアント端末１０の位置を特定すればよい。
【００７０】
さらに、負荷分散装置２０は、サーバ負荷閾値超過通知の受信によりサーバ３０の負荷が高いことを検出することとしたが、負荷分散装置２０が各サーバ３０への要求の振り分け数を記録しておき、その振り分け数に基づき各サーバ３０の負荷の高さを推定してもよい。
【００７１】
また、負荷分散装置２０は、部分領域を決定する際、矩形の部分領域を決定するものとして説明したが、部分領域の形状はこれ以外の形状であってももちろんよい。
【００７２】
なお、負荷分散装置２０は、要求量の分散値を最小化するような部分領域を決定する際、動的計画法を用いるものとして説明したが、動的計画法以外のアルゴリズムを用いてももちろんよい。
【００７３】
（プログラム）
また、上記実施形態に係る負荷分散装置２０が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。この場合、コンピュータがプログラムを実行することにより、上記実施形態と同様の効果を得ることができる。さらに、かかるプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータに読み込ませて実行することにより上記実施形態と同様の処理を実現してもよい。以下に、負荷分散装置２０と同様の機能を実現する負荷分散プログラムを実行するコンピュータの一例を説明する。
【００７４】
図１３は、負荷分散プログラムを実行するコンピュータを示す図である。図１３に示すように、コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有する。これらの各部は、バス１０８０によって接続される。
【００７５】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ（Random  Access  Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０には、ハードディスクドライブ１０９０が接続される。ディスクドライブインタフェース１０４０には、ディスクドライブ１１００が接続される。ディスクドライブ１１００には、例えば、磁気ディスクや光ディスク等の着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０には、例えば、マウス１１１０およびキーボード１１２０が接続される。ビデオアダプタ１０６０には、例えば、ディスプレイ１１３０が接続される。
【００７６】
ここで、図１３に示すように、ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３およびプログラムデータ１０９４を記憶する。上記実施形態で説明した各テーブルは、例えばハードディスクドライブ１０９０やメモリ１０１０に記憶される。
【００７７】
また、負荷分散プログラムは、例えば、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、ハードディスクドライブ１０９０に記憶される。具体的には、上記実施形態で説明した負荷分散装置２０が実行する各処理が記述されたプログラムモジュールが、ハードディスクドライブ１０９０に記憶される。
【００７８】
また、負荷分散プログラムによる情報処理に用いられるデータは、プログラムデータとして、例えば、ハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、ハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して、上述した各手順を実行する。
【００７９】
なお、負荷分散プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限られず、例えば、着脱可能な記憶媒体に記憶されて、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、負荷分散プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ＬＡＮ（Local  Area  Network）やＷＡＮ（Wide  Area  Network）等のネットワークを介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【００８０】
１０，１０Ａ〜１０Ｄ    クライアント端末
２０    負荷分散装置
２１    入出力部
２２    制御部
２３    記憶部
３０，３０Ａ〜３０Ｄ    サーバ
２２１  要求受け付け部
２２２  要求量カウント部
２２３  部分領域決定部
２２４  要求振り分け部
２２５  部分領域数更新部
【図１】
2015201029.tif 000003
【図２】
2015201029.tif 000004
【図３】
2015201029.tif 000005
【図４】
2015201029.tif 000006
【図５】
2015201029.tif 000007
【図６】
2015201029.tif 000008
【図７】
2015201029.tif 000009
【図８】
2015201029.tif 000010
【図９】
2015201029.tif 000011
【図１０】
2015201029.tif 000012
【図１１】
2015201029.tif 000013
【図１２】
2015201029.tif 000014
【図１３】
2015201029.tif 000015