(57)【特許請求の範囲】
【請求項１】
クライアントにサービスを提供する複数の処理装置と、コンシステント・ハッシュ法により前記クライアントから得られるメッセージを前記処理装置に振り分ける複数の振り分け装置とが通信可能に接続されている分散システムの振り分け装置における振り分け方法であって、
前記コンシステント・ハッシュ法による処理装置の処理装置識別子の払い出しは、その払い出し時点で、識別子空間にすでに配置されている処理装置の処理装置識別子の配置状態に基づいて行われ、
前記振り分け装置の記憶部は、
前記処理装置ごとに払い出される処理装置識別子を格納する処理装置管理テーブルを記憶しており、
前記振り分け装置の制御部は、
前記分散システムにおける前記振り分け装置の代表を決定するステップと、
前記振り分け装置の代表に該当する場合には、前記処理装置の増設があると、前記増設した処理装置の処理装置識別子を払い出し、前記払い出した処理装置識別子を用いて前記処理装置管理テーブルを更新するとともに、前記払い出した処理装置識別子を代表以外の振り分け装置に通知するステップと、
前記振り分け装置の代表以外に該当する場合には、前記処理装置の増設があると、代表の振り分け装置から通知された、前記増設した処理装置の処理装置識別子を用いて前記処理装置管理テーブルを更新するステップと、を実行する
ことを特徴とする振り分け方法。
【請求項２】
前記処理装置管理テーブルは、前記処理装置ごとに、前記代表以外の振り分け装置が前記代表の振り分け装置から通知される前に、対応する処理装置識別子を払い出したことを示す暫定フラグを格納し、
前記振り分け装置の制御部は、
前記振り分け装置の代表以外に該当する場合には、前記処理装置の増設があると、前記代表の振り分け装置から通知される前に、前記増設した処理装置の処理装置識別子を払い出し、前記払い出した処理装置識別子を用いて、前記増設した処理装置に対応する暫定フラグをオンにして前記処理装置管理テーブルを更新するステップと、
前記代表の振り分け装置から通知された、前記増設した処理装置の処理装置識別子と、前記代表以外の振り分け装置が払い出した、前記増設した処理装置の処理装置識別子とが一致すれば、前記代表以外の振り分け装置が払い出した、前記増設した処理装置の処理装置識別子を採用するとともに、前記増設した処理装置に対応する暫定フラグをオフにして前記処理装置管理テーブルを更新するステップと、を実行する
ことを特徴とする請求項１に記載の振り分け方法。
【請求項３】
前記振り分け装置の制御部は、
前記処理装置の減設があると、前記減設した処理装置の処理装置識別子を削除して前記処理装置管理テーブルを更新するステップを実行する
ことを特徴とする請求項１または請求項２に記載の振り分け方法。
【請求項４】
前記振り分け装置の記憶部は、
振り分け装置の振り分け装置識別子を格納する振り分け装置管理テーブルを記憶しており、
前記振り分け装置の制御部は、
前記振り分け装置の増設があると、前記増設した振り分け装置の振り分け装置識別子を用いて前記振り分け装置管理テーブルを更新するステップと、
前記処理装置管理テーブルおよび前記振り分け装置管理テーブルの内容を前記増設した振り分け装置に通知するステップと、を実行する
ことを特徴とする請求項１から請求項３のいずれか一項に記載の振り分け方法。
【請求項５】
前記振り分け装置の記憶部は、
振り分け装置の振り分け装置識別子を格納する振り分け装置管理テーブルを記憶しており、
前記振り分け装置の制御部は、
前記振り分け装置の代表に該当する場合には、前記振り分け装置の増設があると、前記増設した振り分け装置の振り分け装置識別子を用いて前記振り分け装置管理テーブルを更新するとともに、前記増設した振り分け装置の振り分け装置識別子を前記代表以外の振り分け装置に通知するステップと、
前記振り分け装置の代表以外に該当する場合には、前記振り分け装置の増設があると、代表の振り分け装置から通知された、前記増設した振り分け装置の振り分け装置識別子を用いて前記振り分け装置管理テーブルを更新するステップと、
前記処理装置管理テーブルおよび前記振り分け装置管理テーブルの内容を前記増設した振り分け装置に通知するステップと、を実行する
ことを特徴とする請求項１から請求項３のいずれか一項に記載の振り分け方法。
【請求項６】
前記振り分け装置の記憶部は、
振り分け装置の振り分け装置識別子を格納する振り分け装置管理テーブルを記憶しており、
前記振り分け装置の制御部は、
前記振り分け装置の増設があると、前記増設した振り分け装置の振り分け装置識別子を用いて前記振り分け装置管理テーブルを更新するステップと、
前記振り分け装置の記憶部が記憶している前記処理装置管理テーブルおよび前記振り分け装置管理テーブルそれぞれのメモリアドレスおよびサイズを、前記増設した振り分け装置に通知し、前記増設した振り分け装置によるダイレクトメモリアクセスを許可するステップと、を実行する
ことを特徴とする請求項１から請求項３のいずれか一項に記載の振り分け方法。
【請求項７】
前記振り分け装置の制御部は、
前記振り分け装置の減設があると、前記減設した振り分け装置の振り分け装置識別子を削除して前記振り分け装置管理テーブルを更新するステップを実行する
ことを特徴とする請求項４から請求項６のいずれか一項に記載の振り分け方法。
【請求項８】
クライアントにサービスを提供する複数の処理装置と、コンシステント・ハッシュ法により前記クライアントから得られるメッセージを前記処理装置に振り分ける複数の振り分け装置とが通信可能に接続されている分散システムの振り分け装置であって、
前記コンシステント・ハッシュ法による処理装置の処理装置識別子の払い出しは、その払い出し時点で、識別子空間にすでに配置されている処理装置の処理装置識別子の配置状態に基づいて行われ、
前記振り分け装置の記憶部は、
前記処理装置ごとに払い出される処理装置識別子を格納する処理装置管理テーブルを記憶しており、
前記振り分け装置の制御部は、
前記分散システムにおける前記振り分け装置の代表を決定する制御と、
前記振り分け装置の代表に該当する場合には、前記処理装置の増設があると、前記増設した処理装置の処理装置識別子を払い出し、前記払い出した処理装置識別子を用いて前記処理装置管理テーブルを更新するとともに、前記払い出した処理装置識別子を代表以外の振り分け装置に通知する制御と、
前記振り分け装置の代表以外に該当する場合には、前記処理装置の増設があると、代表の振り分け装置から通知された、前記増設した処理装置の処理装置識別子を用いて前記処理装置管理テーブルを更新する制御と、を実行する
ことを特徴とする振り分け装置。
【請求項９】
クライアントにサービスを提供する複数の処理装置と、コンシステント・ハッシュ法により前記クライアントから得られるメッセージを前記処理装置に振り分ける複数の振り分け装置とが通信可能に接続されている分散システムの振り分け装置としてコンピュータを機能させる振り分けプログラムであって、
前記コンシステント・ハッシュ法による処理装置の処理装置識別子の払い出しは、その払い出し時点で、識別子空間にすでに配置されている処理装置の処理装置識別子の配置状態に基づいて行われ、
前記振り分け装置の記憶部は、
前記処理装置ごとに払い出される処理装置識別子を格納する処理装置管理テーブルを記憶しており、
前記振り分け装置の制御部に、
前記分散システムにおける前記振り分け装置の代表を決定する処理と、
前記振り分け装置の代表に該当する場合には、前記処理装置の増設があると、前記増設した処理装置の処理装置識別子を払い出し、前記払い出した処理装置識別子を用いて前記処理装置管理テーブルを更新するとともに、前記払い出した処理装置識別子を代表以外の振り分け装置に通知する処理と、
前記振り分け装置の代表以外に該当する場合には、前記処理装置の増設があると、代表の振り分け装置から通知された、前記増設した処理装置の処理装置識別子を用いて前記処理装置管理テーブルを更新する処理と、を実行させる
ことを特徴とする振り分けプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散処理を行う分散システムにおける負荷分散の技術に関する。
【背景技術】
【０００２】
分散システムは、複数の処理装置（サーバ）を含み、例えば、これらの処理装置を仮想化することで、呼制御などのセッション制御を実現する。また、分散システムは、一般的には、複数の振り分け装置を含む。振り分け装置は、端末（クライアント）からセッション接続要求などのメッセージを受信すると、そのメッセージに含まれるセッション制御用のデータを分析し、メッセージを所定の方法に従って、処理装置に振り分ける。各処理装置は、振り分けられたメッセージを処理（例：呼処理）し、端末に対して所定のサービスを提供する。
【０００３】
前記所定の方法としては、例えば、コンシステント・ハッシュ法がある。コンシステント・ハッシュ法は、処理装置を識別する処理装置識別子および処理装置に振り分けるメッセージに含まれるデータを識別するデータ識別子に基づいて、どの処理装置にどのメッセージを振り分けるかを決定する方法である。
【０００４】
具体的に、どのようにしてメッセージの振り分けが決定されるかを、図１を参照して説明する。図１は、コンシステント・ハッシュ法を説明するための識別子空間の概念図である。処理装置識別子は、例えば、処理装置のＩＰ（Internet Protocol）アドレス、処理装置名などに、ハッシュ関数を作用させて得られた値である。なお、処理装置識別子を得て、識別子空間に配置することを、処理装置識別子を「払い出す」と表現する場合がある。処理装置識別子の払い出しは、振り分け装置が実行する。
【０００５】
識別子空間は、図１に示すようにリング状で描写されるハッシュ空間である。処理装置識別子は、例えば、その値に基づいて識別子空間において時計回りに昇順に配置される。データ識別子は、その値に基づいてハッシュ空間に写像して配置される、つまり振り分けられる。データ識別子も、その値に基づいて識別子空間において時計回りに昇順に配置される。
【０００６】
このとき、処理装置は、自身の処理装置識別子の直近の処理装置識別子の配置場所から自身の処理装置識別子の配置場所まで時計回りに辿る円弧上に配置されるデータ識別子のデータを含むメッセージを処理する。ここで、「直近の処理装置識別子」とは、識別子空間において、対象の処理装置識別子の値よりも小さな値を持つ処理装置識別子のうち最も大きな値を持つ処理装置識別子を意味する。しかし、対象の処理装置識別子が識別子空間において、最も小さな値を持つ場合には、直近の処理装置識別子は、識別子空間において、最も大きな値を持つこととする。すると、直近の処理装置識別子の配置場所から対象の処理装置識別子の配置場所まで時計回りに辿る円弧が、対象の処理装置識別子で識別される処理装置がメッセージの処理を担当する領域である。よって、担当する円弧が長いほど、つまり、直近の処理装置識別子の配置場所と離れているほど、対象の処理装置識別子で識別される処理装置が処理するメッセージの処理量、つまり負荷が大きくなる。
【０００７】
図１によれば、処理装置識別子Ａ、Ｂ、Ｃの値にＡの値＜Ｂの値＜Ｃの値という関係があるので、時計回りにＡ→Ｂ→Ｃの順番に処理装置識別子が配置される。また、データ識別子Ｘの値は、Ａの値＜Ｘの値＜Ｂの値という関係を満たすので、処理装置識別子Ａおよび処理装置識別子Ｂの間に配置される。よって、データ識別子Ｘで識別されるデータを含むメッセージは、処理装置識別子Ｂで識別される処理装置が処理する。なお、処理装置識別子Ａで識別される処理装置は、処理装置識別子Ｃの配置場所から処理装置識別子Ａの配置場所まで時計回りに辿る円弧上に配置されるデータ識別子のデータを含むメッセージを処理する。
【０００８】
前記したように、処理装置識別子をＩＰアドレス、処理装置名などから払い出した場合には、処理装置識別子が無作為に定まる。よって、識別子空間における処理装置識別子の配置場所も無作為に定まる。その結果、処理装置がメッセージの処理を担当する領域の分布、つまり、処理装置の負荷の分布は確率的に定まる。このことは、処理装置それぞれの負荷に偏りが生じることを意味し、例えば、処理装置の性能を超える負荷がその処理装置に発生した場合には、メッセージの一部を破棄する必要がある、という事態が生じる。よって、分散システムの運用を継続するうえで、処理装置を増減設する場合には、処理装置それぞれの負荷を均一化することが望まれる。
【０００９】
非特許文献１は、増設する処理装置の処理装置識別子を払い出す時点で、メッセージの処理を担当する領域が最も大きな処理装置に対し、その領域を２等分するような処理装置識別子を払い出す技術を開示している。これにより、隣接する処理装置識別子同士の間隔を平均化し、処理装置それぞれの負荷を均一化することができる。
【００１０】
図２は、非特許文献１の技術による処理装置識別子の払い出しの説明図である。図２の識別子空間内の処理装置識別子Ａ、Ｂ、Ｃは、図１に倣う。図２によれば、処理装置識別子Ａで識別される処理装置が最も大きな領域を担当する。よって、増設する処理装置の処理装置識別子Ｄは、処理装置識別子Ｃから処理装置識別子Ａに延びる円弧を２等分する場所に配置される。
【００１１】
振り分け装置は、例えば、前記した非特許文献１の技術により払い出される処理装置識別子を処理装置ごとに管理するテーブルを持つ。このとき、分散システムを構築する際に、スケーラビリティを確保するためには、複数の振り分け装置は、前記テーブルをそれぞれ持つ。つまり、複数の振り分け装置が共有するテーブルは作成しない。よって、振り分け装置は、自身が備えるテーブルの内容に基づいて、メッセージを処理装置のそれぞれに振り分ける。
【先行技術文献】
【特許文献】
【００１２】
【非特許文献１】入江、他３名、「コンシステント・ハッシュ法におけるノード増減を意識した負荷分散方法」、2010年電子情報通信学会通信ソサイエティ大会、2010年9月、B-7-50  p.127
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、前記したように、振り分け装置が、自身の持つテーブルに従って、メッセージを処理装置のそれぞれに振り分ける場合、処理装置の増減設に伴い、テーブルそれぞれの内容が一致しなくなる場合がある。一致しなくなることにより、たとえ非特許文献１の技術を用いたとしても、処理装置それぞれの負荷の不均一化を招く場合がある。例えば、同一のメッセージであっても、振り分け装置により、場合によっては異なる処理装置に振り分けられてしまう。このため、増設した処理装置間でデータを検索する負荷が増加し、前記した負荷の不均一化を招く。
【００１４】
前記したテーブルそれぞれの内容の不一致は、主に、振り分け装置による処理装置の増減設の検出のタイムラグに起因する。つまり、処理装置の増減設の実際の順番が定まっていたとしても、振り分け装置による処理装置の増減設の検出の順番は、実際の順番とは異なる場合がある。振り分け装置による処理装置識別子の払い出しのアルゴリズムは、処理装置の増減設の実際の順番ではなく、検出の順番に従う。
【００１５】
このことを、図３を参照して具体的に説明する。図３は、２つの処理装置の増設に伴う処理装置識別子の払い出しの違いを説明する図である。図３の識別子空間内の処理装置識別子Ａ、Ｂ、Ｃは、図１、図２に倣う。処理装置識別子Ｘ、Ｙで識別される２つの処理装置を増設し、非特許文献１の技術により処理装置識別子Ｘ、Ｙを払い出す場合を考える。図３の（ａ）は、第１の振り分け装置における処理装置識別子Ｘ、Ｙの払い出しを示し、図３の（ｂ）は、第２の振り分け装置における処理装置識別子Ｘ、Ｙの払い出しを示す。
【００１６】
増設する２つの処理装置は、処理装置識別子Ｘの処理装置→処理装置識別子Ｙの処理装置の順に実際に増設されたとする。このとき、第１の振り分け装置は、増設の実際の順番の通りに、処理装置を検出する。よって、まず、処理装置識別子Ｘが、処理装置識別子Ｃから処理装置識別子Ａに延びる円弧を２等分する場所に配置される。この配置後では、処理装置識別子Ｂで識別される処理装置が最も大きな領域を担当する。よって、次に、処理装置識別子Ｙが、処理装置識別子Ａから処理装置識別子Ｂに延びる円弧を２等分する場所に配置される。
【００１７】
一方、第２の振り分け装置は、処理装置識別子Ｘの処理装置の検出にタイムラグが生じたため、増設の実際の順番とは逆の順番で処理装置を検出する。よって、まず、処理装置識別子Ｙが、処理装置識別子Ｃから処理装置識別子Ａに延びる円弧を２等分する場所に配置され、次に、処理装置識別子Ｘが、処理装置識別子Ａから処理装置識別子Ｂに延びる円弧を２等分する場所に配置される。
【００１８】
このように、処理装置の増設の検出のタイムラグにより、識別子空間の内容が振り分け装置ごとで変わってしまい、結果的に処理装置それぞれの負荷の不均一化を招く場合がある。このような事態は、基本的には、処理装置の減設についてもあてはまる。
なお、検出のタイムラグの影響を解消するように、処理装置の増減設の作業１つ１つの間隔を十分に空けるような措置をとってもよいが、このような措置は、分散システムにおける情報処理の遅延化を招くので好ましくない。
【００１９】
このような事情に鑑みて、本発明は、分散システムにおける処理装置それぞれの負荷を均一化することを目的とする。
【課題を解決するための手段】
【００２０】
前記課題を解決するため、請求項１の発明は、クライアントにサービスを提供する複数の処理装置と、コンシステント・ハッシュ法により前記クライアントから得られるメッセージを前記処理装置に振り分ける複数の振り分け装置とが通信可能に接続されている分散システムの振り分け装置における振り分け方法であって、前記コンシステント・ハッシュ法による処理装置の処理装置識別子の払い出しは、その払い出し時点で、識別子空間にすでに配置されている処理装置の処理装置識別子の配置状態に基づいて行われ、前記振り分け装置の記憶部が、前記処理装置ごとに払い出される処理装置識別子を格納する処理装置管理テーブルを記憶しており、前記振り分け装置の制御部が、前記分散システムにおける前記振り分け装置の代表を決定するステップと、前記振り分け装置の代表に該当する場合には、前記処理装置の増設があると、前記増設した処理装置の処理装置識別子を払い出し、前記払い出した処理装置識別子を用いて前記処理装置管理テーブルを更新するとともに、前記払い出した処理装置識別子を代表以外の振り分け装置に通知するステップと、前記振り分け装置の代表以外に該当する場合には、前記処理装置の増設があると、代表の振り分け装置から通知された、前記増設した処理装置の処理装置識別子を用いて前記処理装置管理テーブルを更新するステップと、を実行することを特徴とする。
【００２１】
請求項１の発明によれば、分散システムにおける処理装置それぞれの負荷を均一化することができる。
【００２２】
請求項２の発明は、請求項１に記載の振り分け方法において、前記処理装置管理テーブルは、前記処理装置ごとに、前記代表以外の振り分け装置が前記代表の振り分け装置から通知される前に、対応する処理装置識別子を払い出したことを示す暫定フラグを格納し、前記振り分け装置の制御部が、前記振り分け装置の代表以外に該当する場合には、前記処理装置の増設があると、前記代表の振り分け装置から通知される前に、前記増設した処理装置の処理装置識別子を払い出し、前記払い出した処理装置識別子を用いて、前記増設した処理装置に対応する暫定フラグをオンにして前記処理装置管理テーブルを更新するステップと、前記代表の振り分け装置から通知された、前記増設した処理装置の処理装置識別子と、前記代表以外の振り分け装置が払い出した、前記増設した処理装置の処理装置識別子とが一致すれば、前記代表以外の振り分け装置が払い出した、前記増設した処理装置の処理装置識別子を採用するとともに、前記増設した処理装置に対応する暫定フラグをオフにして前記処理装置管理テーブルを更新するステップと、を実行することを特徴とする。
【００２３】
請求項２の発明によれば、代表以外の振り分け装置は、代表の振り分け装置からの通知がなされる前であっても処理装置へのメッセージの振り分けの準備を部分的に達成することができる。
【００２４】
請求項３の発明は、請求項１または請求項２に記載の振り分け方法において、前記振り分け装置の制御部が、前記処理装置の減設があると、前記減設した処理装置の処理装置識別子を削除して前記処理装置管理テーブルを更新するステップを実行することを特徴とする。
【００２５】
請求項３の発明によれば、処理装置を減設した場合であっても、分散システムにおける処理装置それぞれの負荷を均一化することができる。
【００２６】
請求項４の発明は、請求項１から請求項３のいずれか一項に記載の振り分け方法において、前記振り分け装置の記憶部が、振り分け装置の振り分け装置識別子を格納する振り分け装置管理テーブルを記憶しており、前記振り分け装置の制御部が、前記振り分け装置の増設があると、前記増設した振り分け装置の振り分け装置識別子を用いて前記振り分け装置管理テーブルを更新するステップと、前記処理装置管理テーブルおよび前記振り分け装置管理テーブルの内容を前記増設した振り分け装置に通知するステップと、を実行することを特徴とする。
【００２７】
請求項４の発明によれば、例えば、非特許文献１の技術のような払い出し方法を用いたとしても、増設した振り分け装置において、他の振り分け装置が持つ処理装置管理テーブルと同じものを持つことができる。
【００２８】
請求項５の発明は、請求項１から請求項３のいずれか一項に記載の振り分け方法において、前記振り分け装置の記憶部が、振り分け装置の振り分け装置識別子を格納する振り分け装置管理テーブルを記憶しており、前記振り分け装置の制御部が、前記振り分け装置の代表に該当する場合には、前記振り分け装置の増設があると、前記増設した振り分け装置の振り分け装置識別子を用いて前記振り分け装置管理テーブルを更新するとともに、前記増設した振り分け装置の振り分け装置識別子を前記代表以外の振り分け装置に通知するステップと、前記振り分け装置の代表以外に該当する場合には、前記振り分け装置の増設があると、代表の振り分け装置から通知された、前記増設した振り分け装置の振り分け装置識別子を用いて前記振り分け装置管理テーブルを更新するステップと、前記処理装置管理テーブルおよび前記振り分け装置管理テーブルの内容を前記増設した振り分け装置に通知するステップと、を実行することを特徴とする。
【００２９】
請求項５の発明によれば、振り分け装置の増設の検出のタイムラグの影響を受けずに済ませることができる。
【００３０】
請求項６の発明は、請求項１から請求項３のいずれか一項に記載の振り分け方法において、前記振り分け装置の記憶部は、振り分け装置の振り分け装置識別子を格納する振り分け装置管理テーブルを記憶しており、前記振り分け装置の制御部は、前記振り分け装置の増設があると、前記増設した振り分け装置の振り分け装置識別子を用いて前記振り分け装置管理テーブルを更新するステップと、前記振り分け装置の記憶部が記憶している前記処理装置管理テーブルおよび前記振り分け装置管理テーブルそれぞれのメモリアドレスおよびサイズを、前記増設した振り分け装置に通知し、前記増設した振り分け装置によるダイレクトメモリアクセスを許可するステップと、を実行することを特徴とする。
【００３１】
請求項６の発明によれば、増設した振り分け装置が自身の処理装置管理テーブルおよび振り分け装置管理テーブルを更新するにあたり、分散システムを元々構成している振り分け装置の制御部の負荷を軽減することができる。
【００３２】
請求項７の発明は、請求項４から請求項６のいずれか一項に記載の振り分け方法において、前記振り分け装置の制御部が、前記振り分け装置の減設があると、前記減設した振り分け装置の振り分け装置識別子を削除して前記振り分け装置管理テーブルを更新するステップを実行することを特徴とする。
【００３３】
請求項７の発明によれば、振り分け装置を減設した場合であっても、残りの振り分け装置によるメッセージの振り分けは、支障なく実行することができる。
【００３４】
請求項８の発明は、クライアントにサービスを提供する複数の処理装置と、コンシステント・ハッシュ法により前記クライアントから得られるメッセージを前記処理装置に振り分ける複数の振り分け装置とが通信可能に接続されている分散システムの振り分け装置であって、前記コンシステント・ハッシュ法による処理装置の処理装置識別子の払い出しは、その払い出し時点で、識別子空間にすでに配置されている処理装置の処理装置識別子の配置状態に基づいて行われ、前記振り分け装置の記憶部が、前記処理装置ごとに払い出される処理装置識別子を格納する処理装置管理テーブルを記憶しており、前記振り分け装置の制御部が、前記分散システムにおける前記振り分け装置の代表を決定する制御と、前記振り分け装置の代表に該当する場合には、前記処理装置の増設があると、前記増設した処理装置の処理装置識別子を払い出し、前記払い出した処理装置識別子を用いて前記処理装置管理テーブルを更新するとともに、前記払い出した処理装置識別子を代表以外の振り分け装置に通知する制御と、前記振り分け装置の代表以外に該当する場合には、前記処理装置の増設があると、代表の振り分け装置から通知された、前記増設した処理装置の処理装置識別子を用いて前記処理装置管理テーブルを更新する制御と、を実行することを特徴とする。
【００３５】
請求項８の発明によれば、分散システムにおける処理装置それぞれの負荷を均一化することができる。
【００３６】
請求項９の発明は、クライアントにサービスを提供する複数の処理装置と、コンシステント・ハッシュ法により前記クライアントから得られるメッセージを前記処理装置に振り分ける複数の振り分け装置とが通信可能に接続されている分散システムの振り分け装置としてコンピュータを機能させる振り分けプログラムであって、前記コンシステント・ハッシュ法による処理装置の処理装置識別子の払い出しは、その払い出し時点で、識別子空間にすでに配置されている処理装置の処理装置識別子の配置状態に基づいて行われ、前記振り分け装置の記憶部が、前記処理装置ごとに払い出される処理装置識別子を格納する処理装置管理テーブルを記憶しており、前記振り分け装置の制御部に、前記分散システムにおける前記振り分け装置の代表を決定する処理と、前記振り分け装置の代表に該当する場合には、前記処理装置の増設があると、前記増設した処理装置の処理装置識別子を払い出し、前記払い出した処理装置識別子を用いて前記処理装置管理テーブルを更新するとともに、前記払い出した処理装置識別子を代表以外の振り分け装置に通知する処理と、前記振り分け装置の代表以外に該当する場合には、前記処理装置の増設があると、代表の振り分け装置から通知された、前記増設した処理装置の処理装置識別子を用いて前記処理装置管理テーブルを更新する処理と、を実行させることを特徴とする。
【００３７】
請求項９の発明によれば、分散システムにおける処理装置それぞれの負荷を均一化することができる。
【発明の効果】
【００３８】
本発明によれば、分散システムにおける処理装置それぞれの負荷を均一化することができる。
【図面の簡単な説明】
【００３９】
【図１】コンシステント・ハッシュ法を説明するための識別子空間の概念図である。
【図２】非特許文献１の技術による処理装置識別子の払い出しの説明図である。
【図３】２つの処理装置の増設に伴う処理装置識別子の払い出しの違いを説明する図である。
【図４】第１の実施形態の分散システムの構成図である。
【図５】第１の実施形態の（ａ）振り分け装置で使用されるソフトウェアおよび（ｂ）処理装置で使用されるソフトウェアの構成図である。
【図６】第１の実施形態の処理装置管理テーブルのデータ構造を示す図である。
【図７】第１の実施形態の振り分け装置管理テーブルのデータ構造を示す図である。
【図８】第１の実施形態の処理装置増設時における処理を示すシーケンス図である。
【図９】第１の実施形態の振り分け装置増設時における処理を示すシーケンス図である。
【図１０】第２の実施形態の振り分け装置増設時における処理を示すシーケンス図である。
【図１１】第３の実施形態の振り分け装置で使用されるソフトウェアの構成図である。
【図１２】第３の実施形態の処理装置管理テーブルのデータ構造を示す図である。
【図１３】第３の実施形態の処理装置増設時における処理を示すシーケンス図である。
【図１４】第４の実施形態の振り分け装置で使用されるソフトウェアの構成図である。
【図１５】第４の実施形態の振り分け装置増設時における処理を示すシーケンス図である。
【図１６】第５の実施形態の振り分け装置で使用されるソフトウェアの構成図である。
【図１７】第５の実施形態の調整テーブルのデータ構造を示す図である。
【図１８】第５の実施形態の処理装置増設時における処理を示すシーケンス図である。
【発明を実施するための形態】
【００４０】
次に、本発明を実施するための形態（以下、「実施形態」という。）について、適宜図面を参照しながら説明する。なお、後記する各実施形態において、同一の構成要素には、同一の符号を付し、また、一度説明した事項と共通する事項を説明する場合には、基本的には、その事項の説明は省略し、相違する事項を説明する。
【００４１】
≪第１の実施形態≫
まず、第１の実施形態の分散システムの構成について説明する。
図４は、第１の実施形態の分散システムの構成図である。この分散システムは、振り分け装置１、処理装置２、クライアント３およびロードバランサ４を含む。この分散システムは、複数の処理装置２などのコンピュータ資源を仮想化し、複数の処理装置２が協調してセッション制御を行い、クライアント３に所定のサービスを提供するクラスタシステムである。前記セッション制御は、例えば、呼制御であり、ＳＩＰ（Session Initiation Protocol）を使用して、インターネット電話などのサービスが提供される。
【００４２】
振り分け装置１は、ロードバランサ４から受信したメッセージに含まれる呼制御用のデータを分析し、メッセージを例えばコンシステント・ハッシュ法によって、処理装置２に振り分ける。
処理装置２は、振り分け装置１から振り分けられたメッセージを呼処理し、クライアント３にサービスを提供する。
クライアント３は、データを含むセッション接続要求などのメッセージをロードバランサ４に送信し、処理装置２が提供するサービスを利用する。
ロードバランサ４は、クライアント３から受信したメッセージを、例えばラウンドロビンによって、振り分け装置１のそれぞれに振り分ける。
【００４３】
振り分け装置１、処理装置２、クライアント３およびロードバランサ４はいずれも、入力部、出力部、制御部および記憶部といったハードウェアを含むコンピュータである。入力部は、例えば、入力インタフェースから構成される。出力部は、例えば、出力インタフェースから構成される。制御部は、例えば、ＣＰＵ（Central Processing Unit）や専用回路から構成される。記憶部は、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリの記憶媒体から構成される。前記制御部がＣＰＵから構成される場合、その制御部を含むコンピュータによる情報処理は、ＣＰＵによるプログラム実行処理で実現する。また、そのコンピュータが含む記憶部は、ＣＰＵが指令し、そのコンピュータの機能を実現するためのプログラム（振り分けプログラムを含む）を記憶する。これによりソフトウェアとハードウェアの協働が実現される。
【００４４】
本実施形態は、前記情報処理を実行させるプログラムによって実現することができ、そのプログラムをコンピュータによる読み取り可能な記録媒体（例：ＣＤ−ＲＯＭ）に記憶して提供することが可能である。また、そのプログラムを、インターネットのネットワークを通して提供することも可能である。
【００４５】
本実施形態の分散システムで使用されるソフトウェアについて説明する。
図５は、第１の実施形態の（ａ）振り分け装置で使用されるソフトウェアおよび（ｂ）処理装置で使用されるソフトウェアの構成図である。振り分け装置１は、処理装置増減設検出部１０１、処理装置識別子通知部１０２、振り分け装置増減設検出部１０３、振り分け装置通知部１０４、代表振り分け装置決定部１０５、処理装置管理テーブル１１１および振り分け装置管理テーブル１１２、といった構成要素を備える。また、処理装置２は、処理装置増設通知部２０１および処理装置生存通知部２０２、といった構成要素を備える。
【００４６】
まず、振り分け装置１について説明する。
処理装置増減設検出部１０１は、分散システムに処理装置２が増設された旨を検出したり、分散システムから処理装置２が減設された旨を検出したりする。増設された処理装置２については、例えば、非特許文献１の技術により、対応する処理装置識別子が払い出される。払い出された処理装置識別子は、処理装置管理テーブル１１１に追加する。一方、減設された処理装置２については、例えば、その処理装置２を識別する処理装置識別子を、処理装置管理テーブル１１１から削除する。
なお、非特許文献１の技術による、処理装置識別子の払い出しは、その払い出し時点において、識別子空間にすでに配置されている処理装置識別子の配置状態に依存する。このため、非特許文献１の技術は、過去の処理装置２の増減設の順序に依存する処理装置識別子の払い出し方法であるということができ、つまり、時間に依存した払い出し方法といえる。これに対し、例えば、すでに説明したような、処理装置のＩＰ（Internet Protocol）アドレス、処理装置名などに基づく処理装置識別子の払い出しは、過去の処理装置２の増減設の順序に依存せず、時間に依存しない払い出し方法といえる。
【００４７】
処理装置識別子通知部１０２は、処理装置増減設検出部１０１により払い出された処理装置識別子を、他の振り分け装置１に通知する。
【００４８】
振り分け装置増減設検出部１０３は、分散システムに振り分け装置１が増設された旨を検出したり、分散システムから振り分け装置１が減設された旨を検出したりする。増設された振り分け装置１については、増設された振り分け装置１を特定する情報（振り分け装置識別子）が定められる。前記情報は、例えば、振り分け装置１のアドレスである。前記情報は、振り分け装置管理テーブル１１２に追加する。一方、減設された振り分け装置１については、前記情報を、振り分け装置管理テーブル１１２から削除する。
【００４９】
振り分け装置通知部１０４は、マルチキャストにより他の振り分け装置（増設された振り分け装置１も含む）に対し、分散システムを構成する振り分け装置１の存在を通知する。具体的には、分散システムを構成する振り分け装置１の識別子として例えば、自身の振り分け装置１のアドレスを通知する。振り分け装置１が増設された振り分け装置１である場合は、分散システムを構成する振り分け装置１に対し、例えば、自身の振り分け装置１のアドレスを通知する。
【００５０】
代表振り分け装置決定部１０５は、分散システムを構成する振り分け装置１のなかから所定の方法に従って、振り分け装置１の代表を決定する。なお、説明の便宜上、代表振り分け装置決定部１０５により代表として決定された振り分け装置１を「代表」と称する場合がある。また、分散システムを構成する振り分け装置１のうち、代表以外の振り分け装置１を「代表以外」と称する場合がある。
【００５１】
前記所定の方法は、例えば、以下の代表決定方法１〜３がある。
代表決定方法１：分散システムを構成する振り分け装置１のアドレスにおいて、最若番または最老番のアドレスを持つ振り分け装置１を代表とする。
代表決定方法２：分散システムを構成する振り分け装置１の増設順に従い、最も古く増設された振り分け装置１を代表とする。
代表決定方法３：あらかじめ決めておいた振り分け装置１を代表とする。
【００５２】
処理装置管理テーブル１１１は、分散システムを構成する処理装置２を管理する。スケーラビリティを確保するため、振り分け装置１は、それぞれ処理装置管理テーブル１１１を持つ。
【００５３】
図６は、第１の実施形態の処理装置管理テーブルのデータ構造を示す図である。処理装置管理テーブル１１１は、「処理装置識別子」および「処理装置ＩＰアドレス」といったフィールドを含み、処理装置２ごとにレコードが作成される。
「処理装置識別子」フィールドには、処理装置増減設検出部１０１により払い出された処理装置識別子の値が格納される。
「処理装置ＩＰアドレス」フィールドには、処理装置２のＩＰアドレスの値が格納される。
【００５４】
振り分け装置管理テーブル１１２は、分散システムを構成する振り分け装置１を管理する。スケーラビリティを確保するため、振り分け装置１は、それぞれ振り分け装置管理テーブル１１２を持つ。
【００５５】
図７は、第１の実施形態の振り分け装置管理テーブルのデータ構造を示す図である。このデータ構造は、例えば、前記した代表決定方法１〜３に応じて変更することができる。ただし、いずれの代表決定方法であっても、振り分け装置管理テーブル１１２は、「振り分け装置アドレス」フィールドを含み、「振り分け装置アドレス」フィールドには、振り分け装置１のアドレスの値が格納される。また、振り分け装置管理テーブル１１２のレコードは、振り分け装置１ごとに作成される。
【００５６】
図７の（ａ）は、代表決定方法１に従った振り分け装置管理テーブル１１２のデータ構造を示す。振り分け装置管理テーブル１１２のセルには、振り分け装置１のアドレスの値が格納される。代表振り分け装置決定部１０５は、振り分け装置管理テーブル１１２を参照して、最若番または最老番のアドレスを持つ振り分け装置１を特定する。図７の（ａ）では、例えば、最若番は「１０」なので、アドレスが「１０」である振り分け装置１を代表とする。振り分け装置管理テーブル１１２において、代表と決定した振り分け装置１に対して、代表であることを示す代表フラグを付してもよい。
【００５７】
図７の（ｂ）は、代表決定方法２に従った振り分け装置管理テーブル１１２のデータ構造を示す。このデータ構造は、振り分け装置１の増設の順番を特定できるように、例えば、振り分け装置管理テーブル１１２の個々のセルをチェーン状に組む。各セルには、直前のセルに付随し、当該セルの開始を示すデータである開始データ、および振り分け装置１のアドレスの値が格納される。代表振り分け装置決定部１０５は、振り分け装置管理テーブル１１２を参照して、チェーン状の組まれたセルの先頭を特定する。特定したセルに格納されるアドレスを持つ振り分け装置１が代表となる。振り分け装置管理テーブル１１２において、代表と決定した振り分け装置１に対して、代表であることを示す代表フラグを付してもよい。
【００５８】
図７の（ｃ）は、代表決定方法３に従った振り分け装置管理テーブル１１２のデータ構造を示す。振り分け装置管理テーブル１１２のセルには、振り分け装置１のアドレスの値が格納される。代表決定方法３に従うと、ある振り分け装置１が代表に決定されるが、いくつかの振り分け装置１を代表候補として決定してもよい。このとき、振り分け装置管理テーブル１１２において、代表候補に決定した振り分け装置１のセルには、振り分け装置１のアドレスの値の他に、優先度を示す値が格納される。この優先度は、代表候補から代表を決定する可能性の高い順に「１」、「２」、・・・、といった順位が定められる。優先度は、例えば、振り分け装置１それぞれに過去に発生した障害の回数、態様、頻度などに基づいて算出してもよい。代表振り分け装置決定部１０５は、振り分け装置管理テーブル１１２を参照して、代表候補のうち優先度の順位が最も早い振り分け装置１を特定する。図７の（ｃ）では、例えば、優先度が「１」である振り分け装置１を代表とする。振り分け装置管理テーブル１１２において、代表と決定した振り分け装置１に対して、代表であることを示す代表フラグを付してもよい。
【００５９】
次に、処理装置２について説明する。
処理装置増設通知部２０１は、処理装置２が増設されたとき、マルチキャストにより分散システムを構成するすべての振り分け装置１に対して増設された旨を通知する。
【００６０】
処理装置生存通知部２０２は、分散システムを構成する処理装置２が、マルチキャストにより分散システムを構成するすべての振り分け装置１に対して、当該処理装置２が分散システムのネットワークに通信可能に接続している旨、つまり、生存している旨を通知する。
【００６１】
次に、第１の実施形態の分散システムで実行される処理について説明する。具体的には、処理装置２および振り分け装置１の増減設に関わる処理について説明する。この処理の主体は、振り分け装置１の制御部、および処理装置２の制御部である。
【００６２】
〔処理装置の増設〕
図８は、第１の実施形態の処理装置増設時における処理を示すシーケンス図である。この処理は、処理装置２が分散システムに増設したときに行われ、主に、増設した処理装置２、代表の振り分け装置１、代表以外の振り分け装置１が関わる。この処理は、ステップＳ８０１から開始する。
【００６３】
まず、ステップＳ８０１において、増設した処理装置２の制御部は、処理装置増設通知部２０１により、自身が増設された旨を代表の振り分け装置１、代表以外の振り分け装置２に通知する。なお、増設した処理装置２自身が増設された旨には、例えば、その処理装置２の処理装置ＩＰアドレスが含まれる。ステップＳ８０１の後、増設した処理装置２では処理を終了する。また、代表の振り分け装置１ではステップＳ８０２を開始し、代表以外の振り分け装置１ではステップＳ８０３を開始する。
【００６４】
ステップＳ８０２において、代表の振り分け装置１の制御部は、代表振り分け装置決定部１０５により、自身が代表であるか否かを確認する。この場合は、自身が代表であると確認される。ステップＳ８０２の後、ステップＳ８０４に進む。
【００６５】
ステップＳ８０３において、代表以外の振り分け装置１の制御部は、代表振り分け装置決定部１０５により、自身が代表であるか否かを確認する。この場合は、自身が代表ではないと確認される。ステップＳ８０３の後、ステップＳ８０６を待ってステップＳ８０７に進む。
【００６６】
ステップＳ８０４において、代表の振り分け装置１の制御部は、処理装置増減設検出部１０１により、増設した処理装置２に対する処理装置識別子を払い出す。ステップＳ８０４の後、ステップＳ８０５に進む。
【００６７】
ステップＳ８０５において、代表の振り分け装置１の制御部は、処理装置増減設検出部１０１により、処理装置管理テーブル１１１を更新し、増設した処理装置２の処理装置識別子を追加する。ステップＳ８０５の後、ステップＳ８０６に進む。
【００６８】
ステップＳ８０６において、代表の振り分け装置１の制御部は、処理装置識別子通知部１０２により、増設した処理装置２の処理装置識別子を代表以外の振り分け装置１に通知する。なお、代表の振り分け装置１から代表以外の振り分け装置１への処理装置識別子の通知では、例えば、処理装置２のＩＰアドレスも併せて通知される。ステップＳ８０６の後、代表の振り分け装置１では処理を終了する。
【００６９】
ステップＳ８０７において、代表以外の振り分け装置１の制御部は、処理装置増減設検出部１０１により、処理装置管理テーブル１１１を更新し、代表の振り分け装置１から通知された、増設した処理装置２の処理装置識別子を追加する。ステップＳ８０７の後、代表以外の振り分け装置１では処理を終了する。
以上で、第１の実施形態の処理装置増設時における処理の説明を終える。
【００７０】
この処理により、分散システムにおける処理装置それぞれの負荷を均一化することができる。振り分け装置１それぞれの処理装置管理テーブル１１１は、代表の振り分け装置１の処理装置管理テーブル１１１に統一され、処理装置２それぞれの負荷の不均一化を招く要因が無くなるからである。代表以外の振り分け装置１は、増設した処理装置２から増設通知があったとしても、独自に処理装置識別子を払い出すことはせず、代表の振り分け装置１から通知される処理識別装置を用いて、自身の処理装置管理テーブル１１１を更新する。
【００７１】
２以上の処理装置２の増設があった場合でも、結局は、代表の振り分け装置１において払い出された処理装置識別子を用いた処理装置管理テーブル１１１が採用されるので、２以上の処理装置２の増設の検出のタイムラグの影響を受けない。そのような影響が無いことにより、わざわざ増設の間隔を空けたりする必要も無く、２以上の処理装置２の増設を短時間で完了することができる。
【００７２】
〔振り分け装置の増設〕
図９は、第１の実施形態の振り分け装置増設時における処理を示すシーケンス図である。この処理は、振り分け装置１が分散システムに増設したときに行われ、主に、増設した振り分け装置１、代表の振り分け装置１、代表以外の振り分け装置１が関わる。この処理は、ステップＳ９０１から開始する。
【００７３】
まず、ステップＳ９０１において、増設した振り分け装置１の制御部は、振り分け装置通知部１０４により、自身が増設された旨を代表の振り分け装置１、代表以外の振り分け装置１に通知する。ステップＳ９０１の後、ステップＳ９０６を待ってステップＳ９０７に進む。また、代表の振り分け装置１ではステップＳ９０２を開始し、代表以外の振り分け装置１ではステップＳ９０３を開始する。
【００７４】
ステップＳ９０２において、代表の振り分け装置１の制御部は、代表振り分け装置決定部１０５により、自身が代表であるか否かを確認する。この場合は、自身が代表であると確認される。ステップＳ９０２の後、ステップＳ９０４に進む。
【００７５】
ステップＳ９０３において、代表以外の振り分け装置１の制御部は、代表振り分け装置決定部１０５により、自身が代表であるか否かを確認する。この場合は、自身が代表ではないと確認される。ステップＳ９０３の後、ステップＳ９０５に進む。
【００７６】
ステップＳ９０４において、代表の振り分け装置１の制御部は、振り分け装置増減設検出部１０３により、振り分け装置管理テーブル１１２を更新し、例えば、振り分け装置１のアドレスを追加する。ステップＳ９０４の後、ステップＳ９０６に進む。
【００７７】
ステップＳ９０５において、代表以外の振り分け装置１の制御部は、振り分け装置増減設検出部１０３により、振り分け装置管理テーブル１１２を更新し、例えば、振り分け装置１のアドレスを追加する。ステップＳ９０５の後、代表以外の振り分け装置１では処理を終了する。
【００７８】
ステップＳ９０６において、代表の振り分け装置１の制御部は、処理装置識別子通知部１０２および振り分け装置通知部１０４により、自身が持つ処理装置管理テーブル１１１およびステップＳ９０４において更新された振り分け装置管理テーブル１１２である２つの管理テーブルの内容を増設した振り分け装置１に通知する。ステップＳ９０６の後、代表の振り分け装置１では処理を終了する。
【００７９】
ステップＳ９０７において、増設した振り分け装置１の制御部は、処理装置増減設検出部１０１および振り分け装置増減設検出部１０３により、ステップＳ９０６における代表の振り分け装置１からの通知に対し、自身が持つ処理装置管理テーブル１１１および振り分け装置管理テーブル１１２である２つの管理テーブルを更新する。ステップＳ９０７の後、増設した振り分け装置１では処理を終了する。
【００８０】
なお、この処理では、代表の振り分け装置１が２つの管理テーブル１１１、１１２の内容を増設した振り分け装置１に通知したが、代表以外の振り分け装置１が代わりに通知してもよい。
以上で、第１の実施形態の振り分け装置増設時における処理の説明を終える。
【００８１】
この処理により、非特許文献１の技術のような、過去の処理装置２の増減設の順序に依存する処理装置識別子の払い出し方法を用いたとしても、増設した振り分け装置１において、他の振り分け装置１が持つ処理装置管理テーブル１１１と同じものを持つことができる。一般的には、過去の処理装置２の増減設の順序に依存する処理装置識別子の払い出し方法を用いた場合には、振り分け装置１が処理装置管理テーブル１１１を作成するためには、過去の処理装置２の増減設に関する情報を持つ必要がある。このため、そのような情報を持たない増設した振り分け装置１は、処理装置管理テーブル１１１を作成することができない。これに対し、図９の処理によれば、代表の振り分け装置１が処理装置管理テーブル１１１を通知するので、増設した振り分け装置１は、処理装置管理テーブル１１１を持つことができる。
【００８２】
〔処理装置の減設〕
処理装置２の制御部は、処理装置生存通知部２０２により、例えば、自身が生存していることを示す生存信号を、（代表も代表以外も含む）すべての振り分け装置１に周期的に送信する。振り分け装置１の制御部は、処理装置増減設検出部１０１により、受信した生存信号に基づいて処理装置管理テーブル１１１を参照し、処理装置２の生存を確認する。振り分け装置１の制御部は、所定期間以上経過しても処理装置２から生存信号を受信できなかった場合、その処理装置２は減設されたとみなし、処理装置管理テーブル１１１から該当するレコードを削除する。
【００８３】
また、（代表も代表以外も含む）すべての振り分け装置１の制御部が、例えば、ping（Packet INternet Groper）で実現される処理装置増減設検出部１０１により、処理装置２の生存を周期的に確認する。振り分け装置１の制御部は、所定期間以上経過しても処理装置２の生存を確認できなかった場合、その処理装置２は減設されたとみなし、処理装置管理テーブル１１１から該当するレコードを削除する。
【００８４】
また、前記した生存信号やpingによる処理装置２の生存の確認は、代表の振り分け装置１のみが行うようにしてもよい。この場合、代表の振り分け装置１の制御部は、減設されたとみなした処理装置２について、自身の処理装置管理テーブル１１１から該当するレコードを削除する。また、代表の振り分け装置１の制御部は、処理装置識別子通知部１０２により、減設されたとみなした処理装置２の処理装置識別子を代表以外の振り分け装置１に通知してもよい。代表以外の振り分け装置１の制御部は、通知された処理装置識別子に基づいて自身の処理装置管理テーブル１１１から該当するレコードを削除する。
【００８５】
この処理により、処理装置２を減設した場合であっても、分散システムにおける処理装置それぞれの負荷を均一化することができる。振り分け装置１それぞれの処理装置管理テーブル１１１は統一され、処理装置２それぞれの負荷の不均一化を招く要因が無くなるからである。
【００８６】
なお、処理装置２を減設が問題になるのは、例えば、処理装置２の増設と処理装置２の減設が同時またはほぼ同時に実行された場合である。基本的には、処理装置２を減設しても、その処理装置識別子が識別子空間上で削除されるだけである。しかし、処理装置２を減設によりその処理装置識別子の削除の前後では、残りの処理装置識別子の配置状態が異なる。よって、増設した処理装置２の処理装置識別子の配置場所も、前記した削除の前後で異なる。それゆえ、処理装置２の減設および増設の検出のタイミングの違いが処理装置識別子の配置状態に影響を与える。
処理装置２の減設だけの場合は、特に本発明で採り上げる問題は生じない。例えば、２つの処理装置２の減設があった場合に、その検出の順序が検出のタイムラグにより変わったとしても、識別子空間において対応する処理装置識別子が削除されるだけなので、識別子空間上の結果は変わらない。ただし、識別子空間において処理装置識別子を削除すれば、減設の検出のタイムラグとは無関係に、残りの処理装置識別子が担当する領域は変わる。よって、処理装置２の減設により、残りの処理装置２それぞれの負荷の不均一化が生じることになり、何らかの対策を講じる必要はある。
【００８７】
〔振り分け装置の減設〕
対象の振り分け装置１の制御部は、振り分け装置通知部１０４により、例えば、自身が分散システムのネットワークに接続している、つまり生存していることを示す生存信号を、他のすべての振り分け装置１に周期的に送信する。他のすべての振り分け装置１の制御部は、振り分け装置増減設検出部１０３により、受信した生存信号に基づいて振り分け装置管理テーブル１１２を参照し、対象の振り分け装置１の生存を確認する。他のすべての振り分け装置１の制御部は、所定期間以上経過しても対象の振り分け装置１から生存信号を受信できなかった場合、その対象の振り分け装置１は減設されたとみなし、振り分け装置管理テーブル１１２から該当するレコードを削除する。このような処理は、対象の振り分け装置１が代表であっても代表以外であっても行う。
【００８８】
また、他のすべての振り分け装置１の制御部が、例えば、pingで実現される振り分け装置増減設検出部１０３により、対象の振り分け装置１の生存を周期的に確認する。他のすべての振り分け装置１の制御部は、所定期間以上経過しても対象の振り分け装置１の生存を確認できなかった場合、その対象の振り分け装置１は減設されたとみなし、振り分け装置管理テーブル１１２から該当するレコードを削除する。このような処理は、対象の振り分け装置１が代表であっても代表以外であっても行う。
【００８９】
また、前記した生存信号やpingにより振り分け装置１の生存の確認は、確認する対象が代表以外であれば、代表の振り分け装置１のみが行うようにしてもよい。この場合、代表の振り分け装置１の制御部は、減設されたとみなした振り分け装置１について、自身の振り分け装置管理テーブル１１２から該当するレコードを削除する。また、代表の振り分け装置１の制御部は、振り分け装置通知部１０４により、例えば、減設されたとみなした振り分け装置１のアドレスを代表以外の振り分け装置１（減設されたとみなしたものを除く）に通知してもよい。前記代表以外の振り分け装置１の制御部は、通知されたアドレスに基づいて自身の振り分け装置管理テーブル１１２から該当するレコードを削除する。
【００９０】
この処理により、振り分け装置１を減設した場合であっても、残りの振り分け装置１によるメッセージの振り分けは、支障なく実行することができる。残りの振り分け装置１のそれぞれにおいて、振り分け装置管理テーブル１１２は、減設した振り分け装置１のレコードが削除されるだけであり、処理装置管理テーブル１１１は、依然として一致しているからである。
【００９１】
≪第２の実施形態≫
第２の実施形態について説明する。第１の実施形態では、振り分け装置１の増設において、代表の振り分け装置１も、代表以外の振り分け装置１も増設された振り分け装置１からの増設の通知に応答して自身の振り分け装置管理テーブル１１２を更新した。しかし、本実施形態では、振り分け装置１の増設において、代表以外の振り分け装置１は、代表の振り分け装置１からの通知を待って自身の振り分け装置管理テーブル１１２を更新する。
【００９２】
図１０は、第２の実施形態の振り分け装置増設時における処理を示すシーケンス図である。この処理は、振り分け装置１が分散システムに増設したときに行われ、主に、増設した振り分け装置１、代表の振り分け装置１、代表以外の振り分け装置１が関わる。この処理は、ステップＳ１００１から開始する。
【００９３】
ステップＳ１００１からステップＳ１００４までは、それぞれステップＳ９０１からステップＳ９０４と同じである。増設した振り分け装置１ではステップＳ１００１の後、ステップＳ１００７を待ってステップＳ１００８に進む。代表の振り分け装置１ではステップＳ１００４の後、ステップＳ１００５に進む。代表以外の振り分け装置１ではステップＳ１００３の後、ステップＳ１００６に進む。
【００９４】
ステップＳ１００５において、代表の振り分け装置１の制御部は、振り分け装置通知部１０４により、増設した振り分け装置１のアドレスを代表以外の振り分け装置１に通知する。ステップＳ１００５の後、ステップＳ１００７に進む。
【００９５】
ステップＳ１００６において、代表以外の振り分け装置１の制御部は、振り分け装置増減設検出部１０３により、振り分け装置管理テーブル１１２を更新し、代表の振り分け装置１から通知された、増設した振り分け装置１のアドレスを追加する。ステップＳ１００６の後、代表以外の振り分け装置１では処理を終了する。
【００９６】
ステップＳ１００７およびステップＳ１００８までは、それぞれステップＳ９０６およびステップＳ９０７と同じである。ステップＳ１００７の後、代表の振り分け装置１では処理を終了する。また、ステップＳ１００８の後、増設した振り分け装置１では処理を終了する。
以上で、第２の実施形態の振り分け装置増設時における処理の説明を終える。
【００９７】
この処理により、第１の実施形態の振り分け装置増設時における処理と比較して、振り分け装置１の増設の検出のタイムラグの影響を受けずに済ませることができる。
例えば、処理装置２の場合と同様、振り分け装置１の増設が２以上あった場合には、その増設の検出にもタイムラグが存在し、分散システムを構成する振り分け装置１のそれぞれにおいて、増設した振り分け装置１の検出の順番が、実際の増設の順番と異なる場合がある。もし、異なる場合には、例えば、代表振り分け装置決定部１０５による代表の決定に影響を及ぼすことがある（例：代表決定方法２）。
【００９８】
これに対し、図１０の処理によれば、代表以外の振り分け装置１は、増設した振り分け装置１から増設通知があったとしても、独自に振り分け装置管理テーブル１１２を更新することはせず、代表の振り分け装置１からの通知内容に従う。よって、振り分け装置１のそれぞれにおいて、振り分け装置管理テーブル１１２が、代表の振り分け装置１の振り分け装置管理テーブル１１２に統一される。このように振り分け装置管理テーブル１１２を統一しておくことで、例えば、振り分け装置１の代表を、振り分け装置１の増設順に決定し、定期的に代表を交代することもできる。
【００９９】
≪第３の実施形態≫
第３の実施形態について説明する。第１の実施形態では、処理装置２の増設において、代表以外の振り分け装置１は、増設した処理装置２からの増設の通知に対しては何ら処理を行わず、代表の振り分け装置１からの通知を待ち、処理装置管理テーブル１１１を更新した。しかし、本実施形態では、代表以外の振り分け装置１は、増設した処理装置２からの増設の通知に対して暫定的に処理装置管理テーブル１１１を更新する。
【０１００】
図１１は、第３の実施形態の振り分け装置で使用されるソフトウェアの構成図である。振り分け装置１は、すでに説明した（図５の（ａ））構成要素（１０１〜１０５、１１１、１１２）の他に、タイマ１０６といった構成要素を備える。また、処理装置２は、第１の実施形態のときと同様である（図５の（ｂ））。
【０１０１】
タイマ１１６は、計時手段であり、本実施形態では、後記する暫定フラグをオンにしてから代表の振り分け装置１から処理装置識別子の通知がなされるまでの時間を計測する。
【０１０２】
図１２は、第３の実施形態の処理装置管理テーブルのデータ構造を示す図である。処理装置管理テーブル１１１は、すでに説明した（図６）「処理装置識別子」および「処理装置ＩＰアドレス」といったフィールドの他に、「暫定フラグ」のフィールドを含み、処理装置２ごとにレコードが作成される。
【０１０３】
「暫定フラグ」フィールドには、代表以外の振り分け装置１において、独自にかつ暫定的に処理装置２の処理装置識別子を払い出したか否かを示す暫定フラグの値が格納される。暫定フラグの値がオンであれば、独自にかつ暫定的に処理装置２の処理装置識別子を払い出したことを意味し、オフであれば、代表の振り分け装置１からの通知を受けて所定の処理が完了したことを意味する。
【０１０４】
図１３は、第３の実施形態の処理装置増設時における処理を示すシーケンス図である。この処理は、処理装置２が分散システムに増設したときに行われ、主に、増設した処理装置２、代表の振り分け装置１、代表以外の振り分け装置１が関わる。この処理は、ステップＳ１３０１から開始する。
【０１０５】
ステップＳ１３０１からステップＳ１３０６までは、それぞれステップＳ８０１からステップＳ８０６（図８）と同じである。ステップＳ１３０１の後、増設した処理装置２では処理を終了する。ステップＳ１３０６の後、代表の振り分け装置１では処理を終了する。また、代表以外の振り分け装置１ではステップＳ１３０３の後、ステップＳ１３０７に進む。
【０１０６】
ステップＳ１３０７において、代表以外の振り分け装置１の制御部は、処理装置増減設検出部１０１により、増設した処理装置２に対する処理装置識別子を払い出す。ステップＳ１３０７の後、ステップＳ１３０８に進む。
【０１０７】
ステップＳ１３０８において、代表以外の振り分け装置１の制御部は、処理装置増減設検出部１０１により、処理装置管理テーブル１１１を更新し、増設した処理装置２の処理装置識別子を追加する。このとき、前記追加は暫定的に行い、増設した処理装置２に対応する暫定フラグをオンに設定する。ステップＳ１３０８の後、ステップＳ１３０９に進む。
【０１０８】
ステップＳ１３０９において、代表以外の振り分け装置１の制御部は、ステップＳ１３０８において、暫定フラグをオンに設定した時点から計時する。ステップＳ１３０９の後、ステップＳ１３１０に進む。
【０１０９】
ステップＳ１３１０において、代表以外の振り分け装置１の制御部は、ステップＳ１３０６において、代表の振り分け装置１から、増設した処理装置２の処理装置識別子の通知を受けるとタイマ１０６を停止する。ステップＳ１３１０の後、ステップＳ１３１１に進む。
【０１１０】
ステップＳ１３１１において、代表以外の振り分け装置１の制御部は、処理装置増減設検出部１０１により、ステップＳ１３０７において、代表以外の振り分け装置１が払い出した処理装置識別子と、代表の振り分け装置１から通知された処理装置識別子とが一致するか否か照合する。ステップＳ１３１１の後、ステップＳ１３１２に進む。
【０１１１】
なお、前記照合の結果、代表以外の振り分け装置１が払い出した処理装置識別子と、代表の振り分け装置１から通知された処理装置識別子とが一致すれば、代表以外の振り分け装置１が払い出した処理装置識別子を採用する。もし、一致していなければ、代表の振り分け装置１から通知された処理装置識別子を採用する。また、代表の振り分け装置１からの通知が遅れ、または通知がなされず、タイマ１０６の起動から停止までの時間が所定時間を超えた場合には、例えば、いずれの処理装置識別子も採用しない。
【０１１２】
前記照合は、処理装置識別子のみならず、処理装置ＩＰアドレスについて適用してもよい。つまり、増設した処理装置２から代表以外の振り分け装置１に通知された増設した処理装置２の処理装置ＩＰアドレスと、代表の振り分け装置１から代表以外の振り分け装置１に通知された増設した処理装置２の処理装置ＩＰアドレスとが一致するか否か照合してもよい。
【０１１３】
ステップＳ１３１２において、代表以外の振り分け装置１の制御部は、処理装置増減設検出部１０１により、ステップＳ１３１１における照合の結果に基づいて、処理装置管理テーブル１１１を更新する。前記照合の結果、いずれかの処理装置識別子を採用すれば、処理装置管理テーブル１１１において、増設した処理装置２に関するレコードの暫定フラグはオフにする。もし、いずれの処理装置識別子も採用しないときは、増設した処理装置２に関するレコードは削除する。分散システムでは、前記レコードの削除を踏まえ、例えば、処理装置２の増設を保留し、分散システムの管理者に対して所定の警告表示を行ってもよい。ステップＳ１３１２の後、代表以外の振り分け装置１では処理を終了する。
以上で、第３の実施形態の振り分け装置増設時における処理の説明を終える。
【０１１４】
この処理により、第１の実施形態の処理装置増設時における処理と比較して、代表以外の振り分け装置１は、代表の振り分け装置１からの通知がなされる前であっても処理装置２へのメッセージの振り分けの準備を部分的に達成することができる。よって、処理装置管理テーブル１１１の更新（図１３のステップＳ１３１２）に伴う負荷を軽減することができる。
【０１１５】
なお、暫定フラグがオンに設定されている処理装置２については、振り分け装置１は、その処理装置２に対してメッセージの振り分けを実行しないようにしてもよいし、実行してもよい。実行する場合には、それぞれの振り分け装置１が備える処理装置管理テーブル１１１の不一致に起因する負荷の不均一化を引き起こさないように留意することが好ましい。
【０１１６】
≪第４の実施形態≫
第４の実施形態について説明する。第４の実施形態は、振り分け装置１の増設において、増設した振り分け装置１は、代表の振り分け装置１のメモリにアクセスすることで、処理装置管理テーブル１１１、振り分け装置管理テーブル１１２を取得するものである。
【０１１７】
図１４は、第４の実施形態の振り分け装置で使用されるソフトウェアの構成図である。振り分け装置１は、すでに説明した（図５の（ａ））構成要素（１０１〜１０５、１１１、１１２）の他に、ダイレクトメモリアクセス部１０７といった構成要素を備える。また、処理装置２は、第１の実施形態のときと同様である（図５の（ｂ））。
【０１１８】
ダイレクトメモリアクセス部１０７は、他の振り分け装置１からの要求に対し、対象の振り分け装置１のメモリ（記憶部）へのアクセスを許可する。許可を受けた他の振り分け装置１は、対象の振り分け装置１のメモリに格納されている処理装置管理テーブル１１１、振り分け装置管理テーブル１１２の内容を取得する。
【０１１９】
図１５は、第４の実施形態の振り分け装置増設時における処理を示すシーケンス図である。この処理は、振り分け装置１が分散システムに増設したときに行われ、主に、増設した振り分け装置１、代表の振り分け装置１が関わる。この処理は、ステップＳ１５０１から開始する。
【０１２０】
ステップＳ１５０１からステップＳ１５０３までは、それぞれステップＳ９０１、ステップＳ９０２、ステップＳ９０４（図９）と同じである。増設した振り分け装置１ではステップＳ１５０１の後、ステップＳ１５０４を待ってステップＳ１５０５に進む。代表の振り分け装置１ではステップＳ１５０３の後、ステップＳ１５０４に進む。
【０１２１】
ステップＳ１５０４において、代表の振り分け装置１の制御部は、処理装置識別子通知部１０２および振り分け装置通知部１０４により、代表の振り分け装置１のメモリに格納されている２つの管理テーブル、つまり処理装置管理テーブル１１１および振り分け装置管理テーブル１１２それぞれのメモリアドレスおよびサイズを増設した振り分け装置１に通知する。また、代表の振り分け装置１の制御部は、増設した振り分け装置１による代表の振り分け装置１へのメモリアクセスを許可する。ステップＳ１５０４の後、代表の振り分け装置１では処理を終了する。
【０１２２】
ステップＳ１５０５において、増設した振り分け装置１の制御部は、処理装置増減設検出部１０１および振り分け装置増減設検出部１０３により、ステップＳ１５０４において通知されたメモリアドレスおよびサイズを用いて、代表の振り分け装置１へのダイレクトメモリアクセスを実行し、前記した２つの管理テーブルの内容を取得する。ステップＳ１５０５の後、ステップＳ１５０６に進む。
【０１２３】
ステップＳ１５０６において、増設した振り分け装置１の制御部は、処理装置増減設検出部１０１および振り分け装置増減設検出部１０３により、取得した２つの管理テーブルの内容を用いて、増設した振り分け装置１が持つ２つの管理テーブルを更新する。ステップＳ１５０６の後、増設した振り分け装置１では処理を終了する。
以上で、第４の実施形態の振り分け装置増設時における処理の説明を終える。
【０１２４】
この処理により、第１の実施形態の振り分け装置増設時における処理と比較して、増設した振り分け装置１が自身の処理装置管理テーブル１１１および振り分け装置管理テーブル１１２を更新するにあたり、代表の振り分け装置１の制御部の負荷を軽減することができる。代表の振り分け装置１が処理装置管理テーブル１１１および振り分け装置管理テーブル１１２の内容を増設した振り分け装置１へ通知する手間が省かれるからである。
なお、増設した振り分け装置１は、代表の振り分け装置１ではなく、代表以外の振り分け装置１へのダイレクトメモリアクセスを行ってもよい。つまり、増設した振り分け装置１は、自身以外の、分散システムを元々構成している任意の振り分け装置１へダイレクトメモリアクセスを行うことで、２つの管理テーブルを更新するにあたり、任意の振り分け装置１の制御部の負荷を軽減することができる。
【０１２５】
≪第５の実施形態≫
第５の実施形態について説明する。第１の実施形態では、処理装置２の増設において、複数の振り分け装置１から代表を決定することで、すべての振り分け装置１の処理装置管理テーブル１１１の内容を一致させた。しかし、本実施形態では、代表を決定することなく、その内容を一致させる。
【０１２６】
図１６は、第５の実施形態の振り分け装置で使用されるソフトウェアの構成図である。振り分け装置１は、すでに説明した（図５の（ａ））構成要素（１０１〜１０５、１１１、１１２）の他に、処理装置識別子調整部１０８、調整テーブル１１３といった構成要素を備える。また、処理装置２は、第１の実施形態のときと同様である（図５の（ｂ））。
【０１２７】
処理装置識別子調整部１０８は、他の振り分け装置１の処理装置識別子調整部１０８と連携し、振り分け装置１それぞれにおいて仮に払い出された、処理装置２の処理装置識別子をすべて取得する。また、処理装置識別子調整部１０８は、取得した処理装置識別子同士を比較して最適な処理装置識別子を特定する。
【０１２８】
調整テーブル１１３は、振り分け装置１それぞれにおいて仮に払い出された、処理装置２の処理装置識別子を管理する。スケーラビリティを確保するため、振り分け装置１は、それぞれ調整テーブル１１３を持つ。
【０１２９】
図１７は、第５の実施形態の調整テーブルのデータ構造を示す図である。調整テーブル１１３は、「処理装置ＩＰアドレス」、「処理装置識別子」および「振り分け装置の回答数」といったフィールドを含み、処理装置２ごとにレコードが作成される。
「処理装置ＩＰアドレス」フィールドには、処理装置２のＩＰアドレスの値が格納される。
「処理装置識別子」フィールドには、処理装置識別子調整部１０８が取得した、振り分け装置１それぞれにおいて仮に払い出された、処理装置２の処理装置識別子の値が格納される。一般的に、１つの処理装置ＩＰアドレスに対し、複数の仮の処理装置識別子が払い出されるため、調整テーブル１１３には、その個数分のサブレコードが作成される。
「振り分け装置の回答数」フィールドには、１つの処理装置ＩＰアドレスに対して払い出された仮の処理装置識別子の個数が格納される。調整テーブル１１３には、前記サブレコードの個数と同数のサブレコードが作成される。
【０１３０】
図１８は、第５の実施形態の処理装置増設時における処理を示すシーケンス図である。この処理は、処理装置２が分散システムに増設したときに行われ、主に、増設した処理装置２、分散システムを構成するすべての振り分け装置１のうちの第１の振り分け装置１および第２の振り分け装置１が関わる。ここで、第２の振り分け装置１は、分散システムを構成するすべての振り分け装置１のうち第１の振り分け装置１を除いたものの一部または全部を指す。この処理は、ステップＳ１８０１から開始する。
【０１３１】
まず、ステップＳ１８０１において、増設した処理装置２の制御部は、処理装置増設通知部２０１により、自身が増設された旨を第１の振り分け装置１、第２の振り分け装置１に通知する。なお、増設した処理装置２自身が増設された旨には、例えば、その処理装置２の処理装置ＩＰアドレスが含まれる。ステップＳ１８０１の後、増設した処理装置２では処理を終了する。また、第１の振り分け装置１ではステップＳ１８０２を開始し、第２の振り分け装置１ではステップＳ１８０３を開始する。
【０１３２】
ステップＳ１８０２において、第１の振り分け装置１の制御部は、処理装置増減設検出部１０１により、増設した処理装置２に対する処理装置識別子を仮に払い出す。ステップＳ１８０２の後、ステップＳ１８０４に進む。
【０１３３】
ステップＳ１８０３において、第２の振り分け装置１の制御部は、処理装置増減設検出部１０１により、増設した処理装置２に対する処理装置識別子を仮に払い出す。ステップＳ１８０３の後、ステップＳ１８０５に進む。
【０１３４】
ステップＳ１８０４およびステップＳ１８０５において、第１の振り分け装置１の制御部および第２の振り分け装置１の制御部は、それぞれの処理装置識別子調整部１０８により、それぞれの振り分け装置１で仮に払い出された処理装置識別子を取得し、取得した処理装置識別子を調整する。
【０１３５】
具体的には、第１の振り分け装置１は、自身で仮に払い出された処理装置識別子および増設した処理装置２のＩＰアドレスを第２の振り分け装置１に通知する。また、第１の振り分け装置１は、第２の振り分け装置１から各自で仮に払い出された処理装置識別子および増設した処理装置２のＩＰアドレスを取得する。第１の振り分け装置１は、自身で持つ処理装置識別子およびＩＰアドレス、かつ、取得した処理装置識別子およびＩＰアドレスの値を比較して、調整テーブル１１３の内容を更新する。つまり、調整テーブル１１３（図１７）において、増設した処理装置２のレコードを作成し、そのレコードの「処理装置ＩＰアドレス」、「処理装置識別子」のフィールドには、増設した処理装置２に対応する値が格納される。「振り分け装置の回答数」フィールドには、「処理装置識別子」フィールドに格納された処理装置識別子が払い出された個数が格納される。なお、第１の振り分け装置１自身で払い出された処理装置識別子も「振り分け装置の回答数」フィールドに格納される個数に計上される。
【０１３６】
次に、増設した処理装置２のＩＰアドレスについて、「処理装置識別子」、「振り分け装置の回答数」のフィールドに注目して、払い出された個数が最多数の処理装置識別子を特定する。第１の振り分け装置１は、特定した処理装置識別子が、増設した処理装置２に払い出された真の処理装置識別子であるとみなす。
【０１３７】
払い出された個数が最多数の処理装置識別子が２以上存在した場合、例えば、代表振り分け装置決定部１０５により、振り分け装置１の代表を決定し、代表の振り分け装置１により特定した処理装置識別子を採用してもよい。
なお、上記した処理装置識別子の特定は、第２の振り分け装置１についても適用される。
第１の振り分け装置１では、ステップＳ１８０４の後、ステップＳ１８０６に進み、第２の振り分け装置１では、ステップＳ１８０５の後、ステップＳ１８０７に進む。
【０１３８】
ステップＳ１８０６において、第１の振り分け装置１の制御部は、処理装置増減設検出部１０１により、処理装置管理テーブル１１１を更新し、ステップＳ１８０４において特定された、増設した処理装置２の処理装置識別子を追加する。ステップＳ１８０６の後、第１の振り分け装置１では処理を終了する。
【０１３９】
ステップＳ１８０７において、第２の振り分け装置１の制御部は、処理装置増減設検出部１０１により、処理装置管理テーブル１１１を更新し、ステップＳ１８０５において特定された、増設した処理装置２の処理装置識別子を追加する。ステップＳ１８０７の後、第２の振り分け装置１では処理を終了する。
以上で、第５の実施形態の処理装置増設時における処理の説明を終える。
【０１４０】
この処理により、他の実施形態と比較して、わざわざ振り分け装置１の代表を決定しなくても、代表を決定したときの処理装置２へのメッセージの振り分けの性能と同等の性能を達成することができる。よって、例えば、振り分け装置１において代表を決定する機能（代表振り分け装置決定部１０５）を省いて簡略化したソフトウェアを設計することができる。
【０１４１】
≪その他≫
前記実施形態は、本発明を実施するために好適のものであるが、その実施形式はこれらに限定されるものでなく、本発明の要旨を変更しない範囲内において種々変形することが可能である。
【０１４２】
例えば、分散システムを構成する処理装置２は、あらかじめ代表の振り分け装置１から処理装置識別子を付与されて保持する。振り分け装置１を増設する場合、増設した振り分け装置１は、マルチキャストによりすべての処理装置２に処理装置識別子の送信要求を行い、処理装置２から処理装置識別子およびＩＰアドレスを取得する。増設した振り分け装置１は、取得した処理装置識別子およびＩＰアドレスを用いて処理装置管理テーブルを作成してもよい。
【０１４３】
また、本発明に関しては、分散システムにおいてロードバランサ４を省略してもよい。必要であれば、振り分け装置１は、ロードバランサ４が備える機能（例：ラウンドロビン）を備えてもよい。
【０１４４】
また、本発明は、非特許文献１の技術に限らず、過去の処理装置２の増減設の順序に依存する処理装置識別子の払い出し方法に適用できる。このような払い出し方法としては、例えば、短時間のうちに２以上の処理装置の増設が行われることを把握できるときは、対応する２以上の処理装置識別子をまとめて払い出す時点で、識別子空間において、ある処理装置がメッセージの処理を担当する最大の領域を３以上に等分したり、２番目に大きな領域を２等分したりする、などの方法がある。
前記した２以上の処理装置の増設を把握する方法としては、例えば、前記した短時間では、処理装置の増設があったとしても、振り分け装置１は、対応する処理装置識別子の払い出しを一旦保留し、さらに別の処理装置の増設があるか否か待つという方法がある。
【０１４５】
また、本実施形態で説明した種々の技術を適宜組み合わせた技術を実現することもできる。
また、本実施形態で説明したソフトウェアをハードウェアとして実現することもでき、ハードウェアをソフトウェアとして実現することもできる。
【０１４６】
その他、ハードウェア、ソフトウェア、テーブル、シーケンスなどの具体的な構成について、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【０１４７】
１      振り分け装置
２      処理装置
３      クライアント
４      ロードバランサ
１０１  処理装置増減設検出部
１０２  処理装置識別子通知部
１０３  振り分け装置増減設検出部
１０４  振り分け装置通知部
１０５  代表振り分け装置決定部
１０６  タイマ
１０７  ダイレクトメモリアクセス部
１０８  処理装置識別子調整部
１１１  処理装置管理テーブル
１１２  振り分け装置管理テーブル
１１３  調整テーブル
２０１  処理装置増設通知部
２０２  処理装置生存通知部
【図１】
0005667517.tif 000002
【図２】
0005667517.tif 000003
【図３】
0005667517.tif 000004
【図４】
0005667517.tif 000005
【図５】
0005667517.tif 000006
【図６】
0005667517.tif 000007
【図７】
0005667517.tif 000008
【図８】
0005667517.tif 000009
【図９】
0005667517.tif 000010
【図１０】
0005667517.tif 000011
【図１１】
0005667517.tif 000012
【図１２】
0005667517.tif 000013
【図１３】
0005667517.tif 000014
【図１４】
0005667517.tif 000015
【図１５】
0005667517.tif 000016
【図１６】
0005667517.tif 000017
【図１７】
0005667517.tif 000018
【図１８】
0005667517.tif 000019