(57)【要約】【課題】サーバ間での負荷の均一にする負荷分散システムを提供する。【解決手段】スロット群生成装置は、負荷分散システムにおいて、所定数のサーバの順列組合せをすべて抽出し、それぞれの順列組合せを同じ回数登場するように並べたスロット列を生成する。そして、スロット群生成装置は、ハッシュ空間を、生成したスロット列の長さのスロットに分割し、分割したスロットそれぞれに、スロット列に示される順でサーバを割り当てたスロット群を生成する。つまり、スロット群生成装置は、受信パケットの振り分け対象となるキーの範囲をサーバ間で均一に分割し、かつコンシステント・ハッシュ法において、一部のサーバの故障時も負荷が均一となるスロット群を生成する。【選択図】図９
2015154319.tif 000002
【特許請求の範囲】
【請求項１】
複数のサーバ間で負荷分散を行う負荷分散システムにおいて、受信パケットの振り分けに用いるスロット群を生成するスロット群生成装置であって、
前記負荷分散システムにおける所定数のサーバの順列組合せを生成するスロット列生成部と、
前記生成した順列組合せをノードとして接続した順列接続グラフを生成する接続グラフ生成部と、
前記生成した順列接続グラフから、各ノードの通過回数が全ノード間で同じになる順列閉路を抽出する順列閉路抽出部と、
前記抽出した順列閉路を構成するノードそれぞれの先頭のサーバを閉路の順に並べてスロット列を生成するスロット列生成部と、
所定のハッシュ空間を、前記生成したスロット列の長さのスロットに分割し、前記分割したスロットそれぞれに、前記スロット列に示される順で前記サーバを割り当てたスロット群を生成するスロット群生成部とを備えることを特徴とするスロット群生成装置。
【請求項２】
前記所定数は、前記負荷分散システムにおいて想定する故障サーバの台数に１を加算した値であることを特徴とする請求項１に記載のスロット群生成装置。
【請求項３】
前記スロット群生成装置は、
前記スロット列の対象外としたサーバを、前記スロット列に組み込むとき、前記スロット列に示されるサーバについて、前記所定数から１を減じた数のサーバの順列組合せである拡張基礎順列を生成する拡張基礎順列生成部と、
前記スロット列の対象外としたサーバを、前記拡張基礎順列で挟んだ順列を生成し、前記生成した順列で、前記スロット列における当該拡張基礎順列の箇所を置換したスロット列を生成する拡張スロット列生成部とをさらに備えることを特徴とする請求項１または２に記載のスロット群生成装置。
【請求項４】
複数のサーバ間で負荷分散を行う負荷分散システムにおいて、受信パケットの振り分けに用いるスロット群を生成するスロット群生成装置が、
前記負荷分散システムにおける所定数のサーバの順列組合せを生成するステップと、
前記生成した順列組合せをノードとして接続した順列接続グラフを生成するステップと、
前記生成した順列接続グラフから、各ノードの通過回数が全ノード間で同じになる順列閉路を抽出するステップと、
前記抽出した順列閉路を構成するノードそれぞれの先頭のサーバを閉路の順に並べてスロット列を生成するステップと、
所定のハッシュ空間を、前記生成したスロット列の長さのスロットに分割し、前記分割したスロットそれぞれに、前記スロット列に示される順で前記サーバを割り当てたスロット群を生成するステップとを実行することを特徴とするスロット群生成方法。
【請求項５】
前記所定数は、前記負荷分散システムにおいて想定する故障サーバの台数に１を加算した値であることを特徴とする請求項４に記載のスロット群生成方法。
【請求項６】
前記スロット群生成装置が、
前記スロット列の対象外としたサーバを、前記スロット列に組み込むとき、前記スロット列に示されるサーバについて、前記所定数から１を減じた数のサーバの順列組合せである拡張基礎順列を生成するステップと、
前記スロット列の対象外としたサーバを、前記拡張基礎順列で挟んだ順列を生成し、前記生成した順列で、前記スロット列における当該拡張基礎順列の箇所を置換したスロット列を生成するステップとをさらに実行することを特徴とする請求項４または５に記載のスロット群生成方法。
【請求項７】
複数のサーバ間で負荷分散を行う負荷分散システムにおいて、受信パケットの振り分けに用いるスロット群を生成するスロット群生成装置と、前記生成されたスロット群を用いて、前記受信パケットの振り分けを行う振分装置とを備える負荷分散システムであって、
前記スロット群生成装置は、
前記負荷分散システムの所定数のサーバの順列組合せを生成するスロット列生成部と、
前記生成した順列組合せをノードとして接続した順列接続グラフを生成する接続グラフ生成部と、
前記生成した順列接続グラフから、各ノードの通過回数が全ノード間で同じになる順列閉路を抽出する順列閉路抽出部と、
前記抽出した順列閉路を構成するノードそれぞれの先頭のサーバを閉路の順に並べてスロット列を生成するスロット列生成部と、
所定のハッシュ空間を、前記生成したスロット列の長さのスロットに分割し、前記分割したスロットそれぞれに、前記スロット列に示される順で前記サーバを割り当てたスロット群を生成するスロット群生成部とを備えることを特徴とする負荷分散システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スロット群生成装置、スロット群生成方法、および、負荷分散システムに関する。
【背景技術】
【０００２】
ネットワーク越しにサービス要求を受け付けるシステムでは、膨大なサービス要求にも応答し、かつサービス要求量に応じて割り当てるハードウェア量を柔軟に変更する必要があるため、複数のサーバを並列動作させる分散システムでの実現が主流となっている。
【０００３】
分散システムの実現には、サービス要求を適切にいずれかのサーバへ振り分け、サーバ負荷をサーバ間で均一化する負荷分散装置が必要となる。多くのＷｅｂサービスにおいては個々のサービス要求は独立に処理することが可能なため、サービス要求を順番やランダムなどサービス要求の内容と無関係に振り分ける負荷分散装置が用いられている。しかし、ＳＩＰ（Session  Initiation  Protocol）アプリケーションをはじめとする、複数のサービス要求間で同じ情報を共有する必要があるステートフルなＷｅｂサービスにおいては、それら関係があるサービス要求を同一サーバに振り分ける負荷分散装置を実現する必要がある。
【０００４】
この必要性に関して、非特許文献１では、キーのハッシュ値に応じてデータの格納サーバを決定するコンシステント・ハッシュ法を負荷分散装置に応用し、サービス要求内に同一のキーがある限り同じサーバに振り分ける手法、特にハッシュ値と振り分け先サーバの対応付けを定義するスロット群のスロット数を抑制しながら負荷を均一に分散する手法が記されている。
【０００５】
また、非特許文献２にはスロット数を増加させることで、コンシステント・ハッシュ法の負荷の偏りを低減させる手法が記されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】入江  道生他、“コンシステント・ハッシュ法におけるデータの複製を意識した負荷分散手法”、社団法人電子情報通信学会、信学技報IN2010-77、2010年10月
【非特許文献２】I.Stoica他、“Chord:  A  Scalable  Peer-to-peer  Lookup  Service  for  Internet  Applications”、Proc.  ACM  SIGCOMM  2001、Aug.  2001.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１の手法では、スロット群の数を抑制できる一方で負荷の均一化は完全ではなく、サーバ間で大きな負荷の偏りが生じる可能性がある。また、非特許文献２の手法でも、スロット数の増加によって負荷の偏りが低減することは示されているが、どの程度のスロット数で所望の均一化が図れるかは定かではない。
【０００８】
実際にシステムを構築する場合、負荷の均一化が十分になされず、かつどのサーバの負荷が高くなるかも分からない状況では、サーバ等のハードウェアの調達時に十分な性能を持った機器を選定せざるを得ない。その結果、システム構築のための調達コストを押し上げる結果となってしまう。したがって、システム構築において、システム内のサーバ間の負荷の均一化は非常に重要な課題である。
【０００９】
そこで、本発明は、サーバ間の負荷の偏りがない負荷分散システムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するために、本発明は、複数のサーバ間で負荷分散を行う負荷分散システムにおいて、受信パケットの振り分けに用いるスロット群を生成するスロット群生成装置であって、前記負荷分散システムにおける所定数のサーバの順列組合せを生成するスロット列生成部と、前記生成した順列組合せをノードとして接続した順列接続グラフを生成する接続グラフ生成部と、前記生成した順列接続グラフから、各ノードの通過回数が全ノード間で同じになる順列閉路を抽出する順列閉路抽出部と、前記抽出した順列閉路を構成するノードそれぞれの先頭のサーバを閉路の順に並べてスロット列を生成するスロット列生成部と、所定のハッシュ空間を、前記生成したスロット列の長さのスロットに分割し、前記分割したスロットそれぞれに、前記スロット列に示される順で前記サーバを割り当てたスロット群を生成するスロット群生成部とを備えることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、サーバ間の負荷の偏りがない負荷分散システムを提供することができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、各実施形態の負荷分散システムを示す構成図である。
【図２】図２は、スロット群生成部を示す構成図である。
【図３】図３は、第１の実施形態のスロット群生成部の処理手順を示すフローチャートである。
【図４】図４は、図３の基本スロット列生成処理を示すフローチャートである。
【図５】図５は、基本順列の生成例を示す図である。
【図６】図６は、基本順列接続グラフの生成例を示す図である。
【図７】図７は、基本順列閉路の生成例を示す図である。
【図８】図８は、スロット列の生成例を示す図である。
【図９】図９は、ハッシュ空間にサーバＡ〜Ｂの担当区分を割り当てたスロット群の生成例を示す図である。
【図１０】図１０は、第２の実施形態のスロット群生成部の処理手順を示すフローチャートである。
【図１１】図１１は、図１０のスロット列拡張処理を示すフローチャートである。
【図１２】図１２は、拡張情報の生成例を示す図である。
【図１３】図１３は、拡張基礎順列の生成例を示す図である。
【図１４】図１４は、拡張後のスロット列の生成例を示す図である。
【図１５】図１５は、拡張情報の更新例を示す図である。
【図１６】図１６は、ハッシュ空間にサーバＡ〜Ｅの担当区分を割り当てたスロット群の生成例を示す図である。
【図１７】図１７は、負荷分散システムの他の構成例を示す図である。
【図１８】図１８は、負荷分散プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１３】
以下、本発明の実施形態について、第１の実施形態および第２の実施形態に分けて説明する。なお、各実施形態により本発明が限定されるものではない。
【００１４】
（第１の実施形態）
各実施形態の負荷分散システムは、図１に示すように、クライアント１００と、負荷分散装置２００と、サーバ３００とがネットワーク（図示省略）で接続されて構成される。
【００１５】
負荷分散装置２００は、クライアント１００からのサービス要求パケットを受信するパケット受信部２１０と、受信したパケットから所定のキーを抽出し、そのハッシュ値とスロット群との比較からパケットの転送先のサーバ３００を決定する振分部２２０と、振分部２２０の決定に基づきパケットの転送を実施するパケット転送部２３０と、負荷の均一化を実現するスロット群を生成するスロット群管理部２４０と、スロット群管理部２４０を多くの負荷分散装置で流用できるようにサーバ名称等の抽象化を制御するスロット群汎用化部２５０とを備える。
【００１６】
振分部２２０は、パケット受信部２１０が受信したパケットから、コンシステント・ハッシュ法でキーとする情報を抽出するキー抽出部２２１と、抽出したキーからハッシュ値を生成し、スロット群汎用化部２５０から取得されるスロット群の中からそのハッシュ値に対応するスロットを検索し、そのスロットに割り当てられたサーバをパケットの転送先として決定するパケット送信先決定部２２２とを備える。
【００１７】
スロット群管理部２４０は、サーバのリストやサーバが何台故障した場合まで負荷の均一化をするかを示す耐障害度等の各種パラメータを受信し、スロット群を生成するスロット群生成部（スロット群生成装置）２４１と、スロット群生成部２４１が生成したスロット群を保持するスロット群保持部２４２とを備える。
【００１８】
スロット群汎用化部２５０は、システム保守者４００等から事前に設定された、負荷分散システムサーバリストをもとに、各サーバに汎用的なサーバ名を割り当て、スロット群管理部２４０へスロット群の生成を要求するサーバ群抽象化部２５１と、スロット群管理部２４０が生成したスロット群において、各スロットに割り当てられたサーバ名称を汎用的な名称からシステム固有の名称に変換するサーバ群個別化部２５２と、サーバリストの汎用化に係る対応表を保持するサーバリスト保持テーブル２５３とで構成される。また、図１の負荷分散装置２００は、図１に例示する台数に限定されず、サーバ３００の集合に対し、任意の台数としてもよい。
【００１９】
以下の説明では、負荷分散装置２００の適用サービスが、セッション処理が必要な電話サービスである場合を例に説明するが、適用サービスはこれに限られるものではない。
【００２０】
クライアント１００は、例えば、電話端末のようなＳＩＰ（Session  Initiation  Protocol）クライアントであり、セッション管理に係る要求パケットを送出する装置である。
【００２１】
この場合、負荷分散装置２００とサーバ３００の集合とは一体のシステムとしてＳＩＰサーバであるように振る舞い、クライアント１００からのＳＩＰパケットは専ら負荷分散装置２００が受信・振り分けし、セッション制御そのものはサーバ３００が実施する。これにより、クライアント１００はサーバ３００の増設等を意識することなく、負荷分散装置２００と対向すればよい。ただし、同一クライアント１００に関するセッション処理は同一のサーバ３００が一貫して実施する必要があるため、負荷分散装置２００の振り分けロジックは、同一クライアント１００からのＳＩＰパケットを同一サーバ３００に振り分けるものである必要がある。この点について、負荷分散装置２００は以下で説明するコンシステント・ハッシュ法を用いる。
【００２２】
コンシステント・ハッシュ法において、クライアント１００からのＳＩＰパケットを受信した負荷分散装置２００のパケット受信部２１０は、受信したＳＩＰパケットを振分部２２０のキー抽出部２２１に受け渡す。キー抽出部２２１では、クライアント１００を識別するため、ＳＩＰヘッダからFromやCall-ID等のクライアント識別情報を抽出し、パケット送信先決定部２２２に送る。クライアント識別情報を受信したパケット送信先決定部２２２では、クライアント識別情報のハッシュ値を生成し、スロット群汎用化部２５０から取得した、各サーバ３００が担当するハッシュ値の範囲を記したスロット群にクライアント識別情報のハッシュ値を照らし合わせることで、受信パケットの転送先とするサーバ３００を決定する。このように振り分け先を決定することで、クライアント識別情報が同一である限りにおいて同一のサーバ３００にパケットを転送することができる。
【００２３】
パケットの転送先の決定の後は、パケット転送部２３０がその情報をもとにパケットの送信先ＩＰアドレス等を書き換え、該当するサーバ３００へパケットを転送する。
【００２４】
負荷分散装置２００が上記の処理によってパケットを振り分けた場合に、サーバ３００間での負荷の均一化をはかるためには、各サーバ３００が担当するハッシュ値の範囲が均一化されたスロット群を生成する必要がある。以下では、いくつかのサーバ３００が故障した場合を含め、各サーバ３００が担当するハッシュ値の範囲が均一化されたスロット群を生成する方法について説明する。
【００２５】
今回の例では、負荷分散システムを構成するサーバ３００が５台であり、それぞれサーバ名称が、SIPserver1、SIPserver2、SIPserver3、SIPserver4、SIPserver5であるものとする。また、サーバ３００の故障時の対応については、サーバ３００のうちランダムに１台が故障した場合であっても残るサーバ３００で負荷を均一化する。
【００２６】
スロット群汎用化部２５０は、スロット群管理部２４０が個別のサーバ名SIPserver1等を意識することなくスロット群を生成することができるよう、名称の変換を担う。
【００２７】
具体的には、サーバリスト保持テーブル２５３には、システム保守者４００が事前にSIPserver1等システム固有のサーバ名称と、ＡやＢといったスロット群管理部２４０が用いるサーバ名称の対応付け、例えば、SIPserver1:Ａ、SIPserver2:Ｂ、SIPserver3:Ｃ、SIPserver4:Ｄ、SIPserver5:Ｅを保持させる。この状況でサーバ群抽象化部２５１がシステム保守者４００から、サーバ５台に関して１台故障まで耐性のあるスロット群を生成するよう要請を受けた場合、サーバ群抽象化部２５１では、サーバリスト保持テーブル２５３の情報をもとにＡ、Ｂ、Ｃ、Ｄ、Ｅに関するスロット群を生成するよう、スロット群管理部２４０のスロット群生成部２４１に要求する。この際には、例えば、「故障耐性を求められる台数（想定する故障サーバの台数）＋１」、すなわちここでは「１＋１＝２」を、スロット群生成に係るパラメータとして送信する（以下、本パラメータを基本順列長と呼ぶ）。なお、この「１」を加える処理については、必ずしもサーバ群抽象化部２５１で行う必要はなく、スロット群生成部２４１で行ってもよい。
【００２８】
今回の場合、例えば、サーバ群抽象化部２５１から、サーバリスト「Ａ、Ｂ、Ｃ、Ｄ、Ｅ」、基本順列長「２」という情報がスロット群生成部２４１に送信されると、スロット群管理部２４０からは、例えば、後記する図１６に示すようなスロット群が返送される。つまり、環状のハッシュ空間に対し、各サーバの担当範囲を割り当てたスロット群が返送される。そして、サーバ群個別化部２５２が、返送されたスロット群に対し、サーバリスト保持テーブル２５３の情報をもとに、Ａ，Ｂ等の汎用的な名称からSIPserver1等の個別の名称に変換することで、SIPserver1等の個別の名称に対応したスロット群が生成される。
【００２９】
なお、このスロット群は、負荷分散システムのいずれかのサーバが故障したとき、この故障サーバの処理を引き継ぐサーバを選択するときにも用いられる。例えば、振分部２２０が受信パケットの振り分け先としてSIPserver1を選択した後、このSIPserver1が故障したとき、処理の引き継ぎ先のサーバとして、当該スロット群において故障サーバ（SIPserver1（Ａ））の右隣り（時計回りの向きで隣り）に配置されるサーバ（例えば、SIPserver5（Ｅ））を選択する。
【００３０】
次に、スロット群生成部２４１を詳細に説明する。このスロット群生成部２４１は、図２に示すように、スロット列生成部２４３と、接続グラフ生成部２４４と、順列閉路抽出部２４５と、スロット列生成部２４６と、スロット割り当て部２４７とを備える。拡張基礎順列生成部２４８と、拡張スロット列生成部２４９とは、スロット群生成部２４１が装備する場合と装備しない場合とがあり、装備する場合については第２の実施形態で述べる。なお、各部の処理の詳細は、具体例を交えながら後記する。
【００３１】
スロット列生成部２４３は、負荷分散システムから、（想定する故障サーバの台数＋１）の台数のサーバの順列組合せを生成する。
【００３２】
接続グラフ生成部２４４は、スロット列生成部２４３により生成された順列組合せ同士をノードとして接続した順列接続グラフを生成する。
【００３３】
順列閉路抽出部２４５は、接続グラフ生成部２４４により生成された順列接続グラフから、各ノードを同じ回数通る順列閉路を抽出する。
【００３４】
スロット列生成部２４６は、順列閉路抽出部２４５により抽出された順列閉路を構成するノードそれぞれの先頭のサーバを閉路の順に並べてスロット列（基本スロット列）を生成する。
【００３５】
スロット割り当て部２４７は、スロット列生成部２４６により生成されたスロット列を用いてスロット群を生成する。具体的には、スロット割り当て部２４７は、受信パケットの振り分けに用いるハッシュ空間を、スロット列生成部２４６により生成されたスロット列の長さのスロットに分割する。そして、スロット割り当て部２４７は、この分割したスロットそれぞれに、スロット列に示される順でサーバを割り当てたスロット群を生成する。
【００３６】
次にスロット群生成部２４１の処理手順について説明する。
【００３７】
スロット群生成部２４１は、図３に示すように、スロット群生成の対象となるサーバを示したサーバリストを取得し（Ｓ１０）、サーバリストに示されるサーバの基本スロット列を生成し（Ｓ２０）、生成したスロット列に基づきスロット群を生成する（Ｓ３０）。
【００３８】
例えば、サーバリストにＡ、Ｂ、Ｃが記載され、スロット群生成部２４１が基本スロット列生成処理により、ＡＢＣＢＡＣというスロット列を生成した場合、このＡＢＣＢＡＣというスロット列に基づきスロット群を生成する。例えば、スロット群生成部２４１は、後記する図９に示すように、ハッシュ空間を６等分（スロット列の長さで等分）し、スロット列と同じ順番でスロットにサーバを割り当てる。つまり、スロット群生成部２４１は、Ａ→Ｂ→Ｃ→Ｂ→Ａ→Ｃ（→Ａに戻る）というスロット群を生成する。このように、スロット群生成部２４１が各サーバの登場回数が同じで、かつ各サーバの次に他のサーバが登場する回数が均一になるようなスロット群を生成し、振分部２２０が当該スロット群により受信パケットの振り分けを行うことで、各サーバ間で負荷を均一化し、かつ、故障時の負荷についても均一化することができる。
【００３９】
図３の基本スロット列生成処理（Ｓ２０）は、図４に示す手順により行われる。まず、スロット群生成部２４１のスロット列生成部２４３は、図３のＳ１０で取得されたサーバリストに基づき基本順列を生成する（Ｓ２１）。具体的には、スロット列生成部２４３は、サーバリストに示されるサーバ群について、（想定する故障サーバの台数＋１）、すなわち基本順列長の台数のサーバの順列組合せをすべて抽出する。
【００４０】
例えば、想定する故障サーバの台数を「１」とし、サーバリストにＡ、Ｂ、Ｃが記載されていた場合を考える。この場合、スロット列生成部２４３は、図５に示すように、３つのサーバについて「２（基本順列長）」の長さの全順列を列挙すると、ＡＢ、ＡＣ、ＢＣ、ＢＡ、ＣＡ、ＣＢとなる。つまり、例えば、Ａが故障したときはＢが処理を引き継ぐ、Ａが故障したときにはＣが引き継ぐ、Ｂが故障したときはＣが処理を引き継ぐ、…というように、故障サーバとその故障サーバの処理を引き継ぐサーバとの順列組合せをすべて列挙する。なお、このようにして列挙した順列を基本順列とする。サーバが３台の場合の基本順列の数は３Ｐ２＝３！、つまり６個となる。
【００４１】
図４の説明に戻る。Ｓ２１の後、接続グラフ生成部２４４は、基本順列接続グラフを生成する（Ｓ２２）。具体的には、接続グラフ生成部２４４は、Ｓ１で抽出した順列組合せ（基本順列）同士をノードとして接続した基本順列接続グラフを生成する。
【００４２】
例えば、図６に示すように、基本順列がＡＢ、ＡＣ、ＢＣ、ＢＡ、ＣＡ、ＣＢである場合、接続グラフ生成部２４４は、各基本順列について、後ろ２−１＝１の長さの部分順列で始まる基本順列と接続する。つまり、接続グラフ生成部２４４は、各基本順列をラベルに持つノードを生成し、各基本順列についてはじめの１サーバを除く部分順列を抽出する。例えば、ＡＢ、ＡＣ、ＢＣ、ＢＡ、ＣＡ、ＣＢという基本順列をラベルに持つノードを生成し、ＡＢについてはＢという部分順列を抽出し、ＡＣについてはＣという部分順列を抽出する。このような処理をすべての基本順列に対し行う。そして、接続グラフ生成部２４４は、その抽出した部分順列からはじまる基本順列を抽出する。例えば、Ｂという部分順列から始まる基本順列としてＢＣ、ＢＡを抽出し、Ｃという部分順列から始まる基本順列としてＣＡ、ＣＢを抽出する（図６の「基本順列接続グラフのリンク」参照）。このように、接続グラフ生成部２４４は、基本順列の最後尾と同じサーバを先頭に持つ基本順列をグラフのリンク先として抽出する。そして、接続グラフ生成部２４４は、各基本順列を示すノードを、前記した処理により抽出したリンク先のノードと有向リンクにより接続し、図６の右側に示すような基本順列接続グラフを生成する。
【００４３】
図４の説明に戻る。Ｓ２２の後、順列閉路抽出部２４５は、Ｓ２２で生成された基本順列接続グラフから、各ノードを同じ回数通る基本順列閉路を抽出する（Ｓ２３）。
【００４４】
例えば、順列閉路抽出部２４５は、図７に示すような基本順列接続グラフから、各ノードを同回数通る閉路を抽出し、図７の右側に示す基本順列閉路を得る。このような閉路が生成されれば、スロット群生成部２４１が、この閉路に沿ってスロット列上のサーバの順番を決定することで、各基本順列が同回数出現するスロット列を生成することができる。当該閉路の抽出方法は問わないが、少なくとも当該グラフはオイラー閉路を持つ条件を満たしているため、Fleuryのアルゴリズムを用いることでオイラー閉路を抽出することが可能である。
【００４５】
なお、図７に例示した基本順列接続グラフは、各ノードが入次数、出次数ともに２次の有向グラフとなっているため、抽出されたオイラー閉路は各ノードを丁度２回ずつ通る閉路となる。より一般的なサーバリスト等に対応するには、このオイラー閉路を抽出する手法を想定するが、本例では各ノードを１回ずつ通る閉路が抽出可能であることが明らかなため、以降の説明では図７に示すような基本順列閉路は「ＡＢ→ＢＣ→ＣＢ→ＢＡ→ＡＣ→ＣＡ→（ＡＢに戻る）」を用いるものとする。
【００４６】
図４の説明に戻る。Ｓ２３の後、スロット列生成部２４６は、Ｓ２３で抽出された基本順列閉路を構成するノードそれぞれの先頭のサーバを閉路の順に並べてスロット列を生成する（Ｓ２４）。例えば、スロット列生成部２４６は、図８に示すように基本順列閉路をＡＢ→ＢＣ→ＣＢ→ＢＡ→ＡＣ→ＣＡの順に走査し、それぞれのラベルのはじめのサーバを閉路に沿って並べ、スロット列としてＡＢＣＢＡＣを生成する。
【００４７】
その後、スロット割り当て部２４７は、例えば、図９に示すように、図４のＳ２４で生成されたスロット列の長さでハッシュ空間を等分（空間を６等分）し、スロット列（ＡＢＣＢＡＣ）と同じ順で各スロットにサーバを割り当てたスロット群を生成する。つまり、スロット割り当て部２４７は、Ａ→Ｂ→Ｃ→Ｂ→Ａ→Ｃ（→Ａに戻る）というスロット群を生成する。
【００４８】
このようにして生成されたスロット群には、前記した基本順列が全て同じ回数含まれる。したがって、振分部２２０が、受信パケットの振り分けにこのようなスロット群を用いることで、負荷分散システム内のサーバの故障時を含め、各サーバ間の負荷を均一化させることができる。すなわち、前記したスロット群には、サーバもサーバの順列も同じ数だけ登場するため、平常時の割り当てスロット数が均一となる。さらに、例えばスロットの割り当てとしてＡ→Ｂの順で割り当てている部分があった場合、Ａが故障時にはコンシステント・ハッシュ法に従うと、次のＢが割り当てを受ける形となる結果、全ての基本順列の登場回数が同じであった場合、各サーバの次に他のサーバが登場する回数が均一となり、故障時も負荷を均一化させることができる。
【００４９】
（第２の実施形態）
次に、本発明の第２の実施形態を説明する。第２の実施形態は、スロット群生成部２４１ａが、サーバリストの一部のサーバのスロット列を生成し（基本スロット列生成）、そのスロット列をサーバリストの残りのサーバ分まで拡張する（スロット列拡張を行う）ことを特徴とする。このようにスロット群生成部２４１ａが基本スロット列生成とスロット列拡張とを組み合わせてスロット列を生成することで、サーバリストに示されるサーバの台数が多い場合でも、全サーバのスロット列の生成にかかる計算量とスロット長を低減することができる。
【００５０】
なお、以下、スロット群生成部２４１ａは、まずサーバリストのサーバのうち、（基本順列長＋１）台のサーバのスロット列を生成し、その後、このスロット列を残りのサーバ分まで拡張する場合を例に説明する。前記した第１の実施形態と同じ構成は、同じ符号を付して説明を省略する。
【００５１】
このスロット群生成部２４１ａは、図２に示すように、破線で示す拡張基礎順列生成部２４８と、拡張スロット列生成部２４９とをさらに備える。
【００５２】
まず、スロット群生成部２４１ａは、スロット列生成部２４３、接続グラフ生成部２４４、順列閉路抽出部２４５、および、スロット列生成部２４６により、サーバリストに示されるサーバ（例えば、Ａ〜Ｅ）のうち、（基本順列長＋１）台のサーバ、例えば、Ａ、Ｂ、Ｃの３台のサーバのスロット列を生成する。
【００５３】
拡張基礎順列生成部２４８は、スロット列生成部２４３により生成された基本順列に示されるサーバ（例えば、Ａ、Ｂ、Ｃ）から、（基本順列長−１）台のサーバの順列組合せである拡張基礎順列をすべて抽出する。例えば、拡張基礎順列生成部２４８は、拡張基礎順列として、Ａ、Ｂ、Ｃを抽出する。
【００５４】
拡張スロット列生成部２４９は、サーバリストに示されるサーバ（例えば、Ａ〜Ｅ）のうち、スロット列生成部２４６がスロット列（基本スロット列）の対象としなかったサーバを１つ選択する。
【００５５】
例えば、拡張スロット列生成部２４９は、Ｄ、Ｅのいずれかを選択する、そして、拡張スロット列生成部２４９は、スロット列生成部２４６により生成されたスロット列（例えば、ＡＢＣＢＡＣ）から、拡張基礎順列に示されるサーバ（例えば、Ａ、Ｂ、Ｃ）を１つずつ抽出し、それぞれ拡張対象サーバ（例えば、Ｄ）を拡張基礎順列（例えば、Ａ、Ｂ、Ｃ）で挟んだ順列で置換する。これにより、基本スロット列に、拡張対象サーバが挿入された新たなスロット列が生成される。つまり、基本スロット列が拡張対象サーバの分まで拡張される。その後、拡張スロット列生成部２４９は、上記と同様の処理により、拡張サーバ（例えば、Ｄ）が挿入されたスロット列に、さらに拡張対象サーバ（例えば、Ｅ）を挿入する。これにより、サーバリストに示される全サーバ（Ａ、Ｂ、Ｃ、Ｄ、Ｅ）のスロット列が生成される。
【００５６】
この拡張基礎順列生成部２４８と、拡張スロット列生成部２４９の詳細は、具体例を用いて後記する。
【００５７】
次に、第２の実施形態のスロット群生成部２４１ａにおけるスロット群生成の処理手順について説明する。
【００５８】
図１０に示すように、スロット群生成部２４１ａは、サーバリストおよび基本順列長を示した基礎情報を取得し（Ｓ４０）、この基礎情報をもとに基本スロット列生成用のサーバリストを抽出する（Ｓ５０）。そして、スロット群生成部２４１ａは、Ｓ５０で抽出されたサーバリストをもとに、図３のＳ２０と同様の手順により基本スロット列生成を行う（Ｓ２０）。そして、スロット群生成部２４１ａは、拡張情報を生成する（Ｓ６０）。この拡張情報は、スロット列を拡張するために用いられる情報であり、基本スロット列生成用のサーバリスト（拡張前サーバリスト）と、Ｓ２０で生成した基本スロット列（拡張前のスロット列）と、基本順列長と、サーバリストのうち基本スロット列の対象外としたサーバのリスト（拡張サーバリスト）とを示した情報である。
【００５９】
例えば、図１２に示すように、基礎情報に示されるサーバリストが「Ａ、Ｂ、Ｃ、Ｄ、Ｅ」であり、基本順列長が「２」である場合、スロット群生成部２４１ａは、基本順列長＋１＝３台のサーバを任意に抽出し、基本スロット列生成のためのサーバリスト（例えば、Ａ、Ｂ、Ｃ）を抽出する。なお、ここで抽出対象外のサーバ（例えば、Ｄ、Ｅ）は拡張サーバリストにのせる。その後、スロット群生成部２４１ａは基本スロット列生成処理（図３のＳ２０と同様の処理）によってスロット列を生成する。このスロット列を基本スロット列とする。そして、スロット群生成部２４１ａは、拡張前サーバリスト（基本スロット列生成用のサーバリスト）が「Ａ、Ｂ、Ｃ」であり、拡張前のスロット列（基本スロット列）が「ＡＢＣＢＡＣ」であり、基本順列長が「２」であり、拡張サーバリストが「Ｄ、Ｅ」であることを示した拡張情報を生成する。
【００６０】
図１０の説明に戻る。Ｓ６０の後、スロット群生成部２４１ａは、Ｓ６０で生成された拡張情報をもとにスロット列拡張処理を実行し（Ｓ７０）、Ｓ７０で生成された拡張スロット列を用いて、図３のＳ３０と同様の処理によりスロット群を生成する（Ｓ３０）。
【００６１】
ここで、図１１を用いて、図１０のＳ７０のスロット列拡張処理を説明する。拡張基礎順列生成部２４８は、Ｓ６０で生成された拡張情報を取得すると（Ｓ７１）、拡張対象サーバを抽出し（Ｓ７２）、拡張基礎順列を生成する（Ｓ７３）。
【００６２】
例えば、拡張基礎順列生成部２４８は、図１２に示す拡張情報の拡張サーバリスト「Ｄ、Ｅ」から、Ｄを抽出する。そして、拡張基礎順列生成部２４８は、図１３に示すように、拡張前サーバリストは「Ａ、Ｂ、Ｃ」、基本順列長は「２」という情報から、Ａ、Ｂ、Ｃの３つのサーバについて、基本順列長２−１＝１の長さの全順列を生成する。ここで抽出する順列を拡張基礎順列と呼ぶ。例えば、拡張基礎順列生成部２４８は、拡張基礎順列として「Ａ、Ｂ、Ｃ」を生成する。ここで抽出する拡張基礎順列の個数はサーバがＡ、Ｂ、Ｃの３台の場合、３Ｐ１＝３個となる。
【００６３】
図１１の説明に戻る。Ｓ７３の後、拡張スロット列生成部２４９は、Ｓ７３で生成された拡張基礎順列をスロット列へ挿入する（Ｓ７４）。
【００６４】
例えば、拡張スロット列生成部２４９は、Ｓ７３で生成された拡張基礎順列（例えば、Ａ、Ｂ、Ｃ）について、拡張前のスロット列（例えば、ＡＢＣＢＡＣ）から１つずつ、その位置を検索していく。いくつずつ検索していくかについては、当該スロット列の基本順列閉路（図７参照）において各ノードを通過した回数に等しく、拡張前のスロット列長を基本順列の数で除することで求められる。例えば、前記した例でいうと拡張前のスロット列（ＡＢＣＢＡＣ）の長さは「６」で、基本順列の数は「３Ｐ２＝６」なので、「６÷６＝１」となる。
【００６５】
そして、拡張スロット列生成部２４９は、拡張前のスロット列から検索した拡張基礎順列のそれぞれについて、その拡張基礎順列で拡張対象サーバを挟んだ順列で置換していく。例えば、拡張対象サーバが「Ｄ」である場合を考える。この場合、図１４に示すように、拡張スロット列生成部２４９は、拡張基礎順列「Ａ」については、拡張前のスロット列で「Ａ」となっている箇所１つについて、「ＡＤＡ」で置換する。また、同様に、拡張前のスロット列で「Ｂ」となっている箇所１つについて、「ＢＤＢ」で置換する。さらに、拡張前のスロット列で「Ｃ」となっている箇所１つについて、「ＣＤＣ」で置換する。その結果、拡張後のスロット列として「ＡＤＡＢＣＢＤＢＡＣＤＣ」が得られる。
【００６６】
このように、拡張スロット列生成部２４９は、拡張前のスロット列から、拡張基礎順列を各１抽出し、それぞれ拡張対象サーバを当該拡張基礎順列で挟んだ順列で置換する。なお、前記した例では、拡張基礎順列の長さが「１」である場合について説明したが、長さが「２」である場合、例えば、拡張基礎順列が「ＡＢ」である場合、拡張対象サーバが「Ｄ」なら、拡張前のスロット列で「ＡＢ」となっている箇所について「ＡＢＤＡＢ」に置換する。
【００６７】
図１１の説明に戻る。このようにして拡張基礎順列をスロット列に挿入した（Ｓ７４）後、拡張スロット列生成部２４９は、処理済みの拡張対象サーバを拡張前サーバリストに加える等して拡張情報を更新する（Ｓ７５）。例えば、拡張スロット列生成部２４９は、拡張前のスロット列「ＡＢＣＢＡＣ」に、サーバ「Ｄ」を挿入した後、図１５の左側の拡張情報を、右側の拡張情報へ更新する。
【００６８】
図１１の説明に戻る。Ｓ７６で拡張対象サーバが残存していれば（Ｓ７６でＹｅｓ）、スロット群生成部２４１ａは、更新した拡張情報を用いて、再度Ｓ７１以降の処理を実行する。一方、拡張対象サーバが残存していなければ（Ｓ７６でＮｏ）、スロット列拡張処理を終了し、図１０のＳ３０へ進む。
【００６９】
なお、拡張スロット列生成部２４９は、図１４に示す処理により、拡張対象サーバ「Ｄ」をスロット列へ挿入した後、上記と同様の処理により拡張対象サーバ「Ｅ」をスロット列へ挿入する。つまり、拡張スロット列生成部２４９は、「ＡＤＡＢＣＢＤＢＡＣＤＣ」というスロット列を生成した後、このスロット列の「Ａ、Ｂ、Ｃ、Ｄ」が登場する箇所を１つずつ抽出し、それぞれについて、拡張対象サーバ「Ｅ」を挟んだ順列で置換していく。その結果、拡張スロット列生成部２４９は、「ＡＥＡＤＡＢＥＢＣＢＤＥＤＢＡＣＤＣＥＣ」というスロット列を生成する。
【００７０】
以上の処理によってサーバリストに示される全てのサーバ（Ａ、Ｂ、Ｃ、Ｄ、Ｅ）が組み込まれたスロット列が完成すると、スロット群生成部２４１ａのスロット割り当て部２４７はこれをもとにスロット群を生成する。
【００７１】
例えば、スロット群生成部２４１ａのスロット群割り当て部２４７は、図１６に示すとおりハッシュ値の空間を、スロット列「ＡＥＡＤＡＢＥＢＣＢＤＥＤＢＡＣＤＣＥＣ」の長さ２０個に分割したスロットを生成し、それぞれのスロットに、スロット列「ＡＥＡＤＡＢＥＢＣＢＤＥＤＢＡＣＤＣＥＣ」に登場する順番で担当サーバを割り当てる。
【００７２】
以上の処理によって、サーバリストに示される全てのサーバが含まれ、かつ、それらの間で担当範囲が均一なスロット群が生成されたため、当該スロット群を用いた負荷分散システムでは、負荷をサーバ間で均一に分散することが可能となる。
【００７３】
また、スロット群生成部２４１ａが、スロット列の生成を（基本順列長＋１）台までとし、（基本順列長＋１）台を超えた分のサーバについてはスロット列拡張処理によりスロット列に挿入することで、サーバリストに示される全サーバについてのスロット列を生成する際の計算量とスロット長を低減できる。
【００７４】
（その他の実施形態）
なお、図１のスロット群管理部２４０は、負荷分散装置２００の中に１つであるように例示しているが、図１７のように負荷分散装置２００から切り出し、スロット群提供装置５００のような構成にしてもよく、またこの場合、１つのスロット群提供装置５００が複数の負荷分散装置２００の処理を行うことも可能である。
【００７５】
（プログラム）
また、上記実施形態に係る負荷分散装置２００が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。この場合、コンピュータがプログラムを実行することにより、上記実施形態と同様の効果を得ることができる。さらに、かかるプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータに読み込ませて実行することにより上記実施形態と同様の処理を実現してもよい。以下に、負荷分散装置２００と同様の部を実現する負荷分散プログラムを実行するコンピュータの一例を説明する。
【００７６】
図１８は、負荷分散プログラムを実行するコンピュータを示す図である。図１８に示すように、コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有する。これらの各部は、バス１０８０によって接続される。
【００７７】
メモリ１０１０は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１０１１およびＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Ｂａｓｉｃ  Ｉｎｐｕｔ  Ｏｕｔｐｕｔ  Ｓｙｓｔｅｍ）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。ディスクドライブ１１００には、例えば、磁気ディスクや光ディスク等の着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０には、例えば、マウス１１１０およびキーボード１１２０が接続される。ビデオアダプタ１０６０には、例えば、ディスプレイ１１３０が接続される。
【００７８】
ここで、図１８に示すように、ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３およびプログラムデータ１０９４を記憶する。上記実施形態で説明した各テーブルは、例えばハードディスクドライブ１０９０やメモリ１０１０に記憶される。
【００７９】
また、負荷分散プログラムは、例えば、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、ハードディスクドライブ１０９０に記憶される。具体的には、上記実施形態で説明した負荷分散装置２００が実行する各処理が記述されたプログラムモジュールが、ハードディスクドライブ１０９０に記憶される。
【００８０】
また、負荷分散プログラムによる情報処理に用いられるデータは、プログラムデータとして、例えば、ハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、ハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して、上述した各手順を実行する。
【００８１】
なお、負荷分散プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限られず、例えば、着脱可能な記憶媒体に記憶されて、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、負荷分散プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ＬＡＮ（Local  Area  Network）やＷＡＮ（Wide  Area  Network）等のネットワークを介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【００８２】
２００  負荷分散装置
２１０  パケット受信部
２２０  振分部
２２１  キー抽出部
２２２  パケット送信先決定部
２３０  パケット転送部
２４０  スロット群管理部
２４１、２４１ａ  スロット群生成部
２４２  スロット群保持部
２４３  スロット列生成部
２４４  接続グラフ生成部
２４５  順列閉路抽出部
２４６  スロット列生成部
２４７  スロット割り当て部
２４８  拡張基礎順列生成部
２４９  拡張スロット列生成部
２５０  スロット群汎用化部
２５１  サーバ群抽象化部
２５２  サーバ群個別化部
２５３  サーバリスト保持テーブル
【図１】
2015154319.tif 000003
【図２】
2015154319.tif 000004
【図３】
2015154319.tif 000005
【図４】
2015154319.tif 000006
【図５】
2015154319.tif 000007
【図６】
2015154319.tif 000008
【図７】
2015154319.tif 000009
【図８】
2015154319.tif 000010
【図９】
2015154319.tif 000011
【図１０】
2015154319.tif 000012
【図１１】
2015154319.tif 000013
【図１２】
2015154319.tif 000014
【図１３】
2015154319.tif 000015
【図１４】
2015154319.tif 000016
【図１５】
2015154319.tif 000017
【図１６】
2015154319.tif 000018
【図１７】
2015154319.tif 000019
【図１８】
2015154319.tif 000020