(57)【特許請求の範囲】
【請求項１】
コンピュータが、
要求を受け取る段階と、
前記要求を転送するための第１仮想サーバを選択する段階であって、該第１仮想サーバが、複数のサーバのうちの１つによって提供され、該サーバのうちの少なくとも一部が、複数の仮想サーバを提供する前記選択する段階と、
前記第１仮想サーバが前記要求を受け取ることができない場合に該要求を該第１仮想サーバの近隣仮想サーバに転送する段階であって、該第１仮想サーバの該近隣仮想サーバが、該第１仮想サーバを提供するサーバとは異なるサーバの一部である前記転送する段階と、
を含み、
要求に関連付けられたセッション情報が、前記第１仮想サーバにかつ該第１仮想サーバの前記近隣仮想サーバに送信されることを特徴とする方法。
【請求項２】
サーバの各仮想サーバが、異なる他のサーバによって提供される近隣仮想サーバを有することを特徴とする請求項１に記載の方法。
【請求項３】
サーバが作動不能な場合に、残りのサーバの各仮想サーバが、異なる他のサーバによって提供される近隣仮想サーバを有することを特徴とする請求項１又は請求項２に記載の方法。
【請求項４】
サーバが作動不能な場合に、残りのサーバのうちの２つの仮想サーバが、同じ他のサーバによって提供される近隣仮想サーバを有し、あらゆる残りの仮想サーバの各々が、異なる他のサーバによって提供される近隣仮想サーバを有することを特徴とする請求項１又は請求項２に記載の方法。
【請求項５】
要求を受け取るための入力と、
前記要求を第１仮想サーバに転送するための出力であって、該第１仮想サーバが、複数のサーバのうちの１つによって提供され、該サーバのうちの少なくとも一部が、複数の仮想サーバを提供する前記出力と、
前記第１仮想サーバを選択するためのプロセッサであって、該第１仮想サーバの障害の場合に、該プロセッサが、該第１仮想サーバの近隣サーバを選択し、スケジューラーの出力が、前記要求を該近隣サーバに転送し、該第１仮想サーバの該近隣サーバが、該第１仮想サーバを提供するサーバとは異なるサーバによって提供される仮想サーバである前記プロセッサと、
を含み、
前記出力は、要求に関連付けられたセッション情報を前記第１仮想サーバにかつ該第１仮想サーバの前記近隣サーバに提供することを特徴とする装置。
【請求項６】
サーバの各仮想サーバが、異なる他のサーバによって提供される近隣サーバを有することを特徴とする請求項５に記載の装置。
【請求項７】
サーバが作動不能な場合に、残りのサーバの各仮想サーバが、異なる他のサーバによって提供される近隣サーバを有することを特徴とする請求項５又は６に記載の装置。
【請求項８】
サーバが作動不能な場合に、残りのサーバのうちの２つの仮想サーバが、同じ他のサーバによって提供される近隣サーバを有し、あらゆる残りの仮想サーバの各々が、異なる他のサーバによって提供される近隣サーバを有することを特徴とする請求項５又は６に記載の装置。
【請求項９】
システムであって、
複数のサーバと、
スケジューラーであって、
要求を受け取るための入力と、
前記要求を仮想サーバに転送するための出力と、
前記仮想サーバを選択するためのプロセッサと、
を含む前記スケジューラーと、
を含み、
前記サーバのうちの少なくとも一部が、複数の仮想サーバを含み、
各仮想サーバが、近隣サーバに関連付けられ、
各仮想サーバの前記近隣サーバは、前記各仮想サーバを提供するサーバとは異なる他のサーバの一部であり、
仮想サーバの前記近隣サーバは、そのサーバのバックアップとして作用するようになっており、
前記出力は、要求に関連付けられたセッション情報を前記仮想サーバにかつ該仮想サーバの前記近隣サーバに提供することを特徴とするシステム。
【請求項１０】
サーバの各仮想サーバが、異なる他のサーバによって提供される近隣サーバを有することを特徴とする請求項９に記載のシステム。
【請求項１１】
サーバが作動不能な場合に、残りのサーバの各仮想サーバが、異なる他のサーバによって提供される近隣サーバを有することを特徴とする請求項９又は請求項１０に記載のシステム。
【請求項１２】
サーバが作動不能な場合に、残りのサーバのうちの２つの仮想サーバが、同じ他のサーバによって提供される近隣サーバを有し、あらゆる残りの仮想サーバの各々が、異なる他のサーバによって提供される近隣サーバを有することを特徴とする請求項９又は請求項１０に記載のシステム。
【請求項１３】
サーバであって、
複数の仮想サーバと、
スケジューラーであって、
要求を受け取るための入力と、
前記要求を仮想サーバに転送するための出力と、
前記仮想サーバを選択するためのプロセッサと、
を含む前記スケジューラーと、
を含み、
サーバが、複数のサーバを含むシステムの一部を形成し、
前記複数のサーバの少なくとも一部が、複数の仮想サーバを含み、
サーバが、各仮想サーバが近隣仮想サーバに関連付けられるようになっており、
各仮想サーバの前記近隣仮想サーバは、前記各仮想サーバを提供するサーバとは異なるサーバの一部であり、
仮想サーバの前記近隣仮想サーバは、そのサーバのバックアップとして作用するようになっており、
前記出力は、要求に関連付けられたセッション情報を前記仮想サーバにかつ該仮想サーバの前記近隣サーバに提供することを特徴とするサーバ。
【請求項１４】
コンピュータを、
要求を受け取る手段と、
前記要求を転送するための第１仮想サーバを選択するための手段であって、該第１仮想サーバが、複数のサーバのうちの１つによって提供され、該サーバの少なくとも一部が、複数の仮想サーバを提供する前記選択するための手段と、
前記第１仮想サーバが前記要求を受け取ることができない場合に該要求を該第１仮想サーバの近隣仮想サーバに転送するための手段であって、該第１仮想サーバの該近隣仮想サーバが、該第１仮想サーバを提供するサーバとは異なるサーバによって提供される前記転送するための手段と、
して機能させるためのコンピュータプログラムであって、
要求に関連付けられたセッション情報が、前記第１仮想サーバにかつ該第１仮想サーバの前記近隣仮想サーバに送信されるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サーバのクラスターに関する。特に、本発明は、コンピュータサーバクラスターにおける負荷バランシング（負荷分散）に関する。
【背景技術】
【０００２】
情報技術及び電気通信業界では、システムは、通常は要求メッセージを受け取り、要求に応答して何らかの処理を実行する。多くのこのようなシステムは、拡張可能であるように設計されている。拡張可能なシステムは、より高性能のハードウエア及びソフトウエアで新しいシステムを設計して実施するよりも、既存システムに付加的モジュールを追加することによって性能を改善することができる。
【０００３】
図１は、参照番号１によって一般的に示す拡張可能なシステムの例である負荷バランシングクラスターのブロック図である。クラスター１は、スケジューラー２と、第１サーバ４と、第２サーバ６と、第３サーバ８とを含む。サーバの数は、システム１の所要の又は望ましい容量に従って増減することができる。
【０００４】
使用中は、スケジューラー２はいくつかの要求を受け取る。要求は、スケジューラー２によってサーバ４、６、及び８のうちの１つ又はそれよりも多くに経路指定される。サーバは、サーバ要求によって必要にされる実際のサービス処理を担う（要求のサービス提供の性質は、本発明の原理には関係ない）。
【０００５】
要求の経路指定を実施するために、スケジューラー２は、サーバ間でサービス要求をスケジュールする必要がある負荷バランシング機構を含む。負荷バランシング機構の目的は、サーバクラスターを形成するサーバ４、６、及び８の各々を十分に利用すること、並びにサーバの一部が相対的にビジーで、他は相対的にアイドルであるという状況を回避することである。無作為抽出、ラウンドロビン、最小ビジーなどのような多くのスケジューリング方法が当業技術で公知である。当業者は、使用可能な多くの代替的な負荷バランシングアルゴリズムを認識されると考えられる。
【０００６】
用語「サーバクラスター」は、ローカルネットワークによって接続した及び／又は物理的又は論理的に同一場所に配置されたサーバを表現するのに多くの場合に用いられる。本明細書では、用語「サーバクラスター」及び「クラスター」は、幅広い意味で使用し、サーバが分散される、例えば、広域ネットワーク（ＷＡＮ）にわたって又は「インターネット」上で分散されるシナリオを包含すると読み取るべきである。
【０００７】
データベースクエリのようなステートレスアプリケーションの場合、システム１内のスケジューラー２の目的は、比較的分かりやすく、すなわち、サーバ４、６、及び８の間で均等に負荷の均衡を取ることである。このようなシステムでは、到着する要求がサーバによって処理された状態で、この特定の要求は完了し、この要求に関連して更に別のアクションは必要ない。
【０００８】
しかし、多くのネットワークアプリケーションの場合、クライアント及びサーバは、複数の要求及び応答のやり取りの間に進行中のステータスを維持するために何らかの種類のコンテクストを確立する。アプリケーションレベルでは、このコンテクストは、セッションと呼ぶことができ、インターネットプロトコル（ＩＰ）レベルでは、このコンテクストは、「接続」と呼ぶことができる。コンテクスト、セッション、及び接続という用語は、本明細書ではほぼ同義的に使用する。コンテクストを伴うネットワークアプリケーションの場合、拡張性、負荷バランシング、及び高利用可能性を備えた高収量のシステムアーキテクチャを提供するのは、（図１に示すクラスターのような）クラスターに対してより多くの課題がある。例えば、特定のコンテクストに属する要求が１よりも多く存在する場合がある。これらの要求がクラスター内の１つ又は異なるサーバで処理される時に、このコンテクストにアクセスして正確に修正すべきである。望ましい負荷平衡（バランス）を達成するために、スケジューラー２は、要求を転送する際に（サーバ４、６、及び８の相対的負荷を考慮することに加えて）宛先サーバに対しての関連コンテクストのアクセスし易さを考慮すべきである。代替的に、サーバが何らかの機構を利用して、スケジュールされたサーバに対しての要求のコンテクストのアクセスし易さを保証することができる。
【０００９】
アプリケーションがコンテクストデータを有するサーバクラスターを実施するための３つの方法を以下で説明する。第１の方法（多くの場合に「スティッキーセッション」と呼ばれる）では、特定のセッションの全ての要求を同じサーバに送信する必要があり、このサーバがセッション自体を維持する。第２の方法は、１サーバ内のセッションを同じクラスター内の残りの全てのサーバに対して複製するものである。従って、要求は、処理のためにあらゆるサーバに対してスケジュールすることができる。第３の方法は、セッションを格納するために、サーバが「ストレージエリアネットワーク（ＳＡＮ）」のような共有ストレージを使用することを可能にすることである。クラスター内のいずれのサーバも、この共有ストレージ内のセッションにアクセス可能である。いずれのサーバも、要求の関連セッションにアクセス可能なので、いずれのサーバに対しても要求をスケジュールすることができる。
【００１０】
第１の（スティッキーセッション）方法では、サーバ４、６、及び８は簡単であるが、スケジューラー２は、セッション情報を維持し、様々なセッションの要求を区別する必要がある。セッションの数が非常に膨大な場合、スケジューラー２は、セッションのテーブルを格納し、各要求のセッションを識別するための検索機能を提供するのに十分に強力である必要がある。スケジューラーの背後のサーバの性能が非常に高くなることがあるので、スケジューラー２は、システム１において障害になる場合がある。
【００１１】
第２の（セッション複製）方法では、スケジューラーは、コンテクスト情報を格納する必要はなく、（上述の無作為抽出、ラウンドロビン、及び最小ビジーアルゴリズムのうちの１つのような）何らかの簡単なアルゴリズムによって選択されたサーバに単に要求を転送するだけなので、スケジューラー２は簡単である。しかし、サーバ４、６、及び８に関しては、より多くの要件が存在する。サーバは、フルメッシュ複製を要求する相互間のセッションの複製を管理する。この複製は、高いネットワーク帯域幅及び計算機能のオーバヘッドを示唆する。高収量システムでは、コンテクスト情報は膨大になる場合がある。更に、クラスターシステムは、要求されるフルメッシュ複製により、容易に拡張可能ではない。
【００１２】
第３の（セッション共有）方法では、スケジューラー２は簡単であるが、セッション情報を格納して管理するために、高価な高性能ＳＡＮ（図１には図示せず）が必要である。非常に頻繁なコンテクスト修正を要する高収量アプリケーションの場合、セッション情報による共有セッション方法は、十分な性能をもたらすことはできない。このような設定では、ＳＡＮへのアクセスが、システム１において障害になる場合がある。
【００１３】
クラスター内のサーバの障害の場合に、更に別の問題が発生する。この場合には、サーバによって処理中の要求は、クラスター内の残りのサーバ間で再割り当てする必要がある。この処理は、スケジューラー２によってシステム１内で処理される。例示的に、第１サーバ４に障害が生じると仮定する。サーバによって処理中のセッションは、第２サーバ６及び／又は第３サーバ８に再割り当てする必要がある。セッションを処理するために次に利用可能なサーバを単に用いるような一部の単純な機構では、クラスター内の別のサーバの障害の場合に１サーバが過負荷になることがある。
【発明の概要】
【発明が解決しようとする課題】
【００１４】
本発明は、上記で概要を示した問題の少なくとも一部に対処することを目指すものである。
【課題を解決するための手段】
【００１５】
本発明は、独立請求項に示すような装置及び方法を提供する。本発明は、以下の利点の少なくとも一部を提供することを目指すものである。
・サーバ群によって提供されるサービスの高利用可能性を低コストで達成すること。
・適度のメモリ要件による要求スケジューリングのための高速検索。
・デバイスの高利用率。
・高価なストレージエリアネットワーク（ＳＡＮ）媒体及びネットワークが要求されないこと。
・必要なセッション複製が限定されること。
【００１６】
本発明は、要求を受け取る段階と、要求を転送するための第１仮想サーバを選択する段階とを含む方法を提供し、第１仮想サーバは、複数の（物理）サーバのうちの１つによって提供され、（物理）サーバのうちの少なくとも一部（全ての場合もある）は、複数の仮想サーバを含み又は提供し、選択した第１仮想サーバが要求を受け取ることができない場合には、要求を第１仮想サーバの近隣仮想サーバに転送し、第１仮想サーバの近隣仮想サーバは、第１仮想サーバとは異なるサーバの一部である。従って、第１仮想サーバの近隣サーバは、このサーバのバックアップとして作用する。本方法は、第１仮想サーバに要求を転送し、又は転送するよう試みる段階を含むことができる。
【００１７】
本発明はまた、要求を受け取るための入力と、要求を第１仮想サーバに転送する（又は転送するよう試みる）ための出力とを備えた（スケジューラーのような）装置を提供し、第１仮想サーバは、複数のサーバのうちの１つによって提供され、サーバのうちの少なくとも一部は、複数の仮想サーバを提供し、装置は、第１仮想サーバを選択するためのプロセッサを含み、選択した第１仮想サーバの障害（例えば、第１仮想サーバが一部を形成するサーバの障害）の場合には、プロセッサが第１仮想サーバの近隣（仮想）サーバを選択し、スケジューラーの出力は、要求を近隣サーバに転送し、第１仮想サーバの近隣サーバは、第１仮想サーバとは異なるサーバによって提供される仮想サーバである。近隣サーバは、第１仮想サーバと同時に選択することができる（第１仮想サーバが利用不可又は作動不能な場合に選択するのではなく）。
【００１８】
（物理）サーバの各仮想サーバは、異なる他の（物理）サーバによって提供される近隣サーバを有することができる。従って、特定の物理サーバが作動不能になる場合、物理サーバによって提供される様々な仮想サーバの負荷は、多くの異なる他のサーバ間に分散される。
【００１９】
本発明の一部の形態では、（物理）サーバが作動不能な場合に、残りのサーバの各仮想サーバは、異なる他の（物理）サーバによって提供される近隣サーバを有する。従って、第１物理サーバが作動不能になる場合にこのサーバの負荷を分散させるだけでなく、第２物理サーバも作動不能になる場合にも、第２物理サーバによって提供される様々な仮想サーバの負荷を多くの異なる他のサーバ間に分散する。
【００２０】
代替的に、本発明の一部の形態では、（物理）サーバが作動不能な場合に、残りの（物理）サーバの２つの仮想サーバが、同じ他のサーバによって提供される近隣サーバを有し、あらゆる残りの仮想サーバが各々、異なる他のサーバによって提供される近隣サーバを有する。この状況は、例えば、上記に示した前者の条件が数学的に可能でない場合に生じることがある。
【００２１】
要求に関連付けられたセッション情報は、選択した第１仮想サーバに及びこの選択した第１仮想サーバの近隣サーバに送信することができる。例えば、本発明の装置の出力は、要求に関連付けられたセッション情報を選択した第１仮想サーバに及び選択した第１仮想サーバの選択した近隣に提供することができる。従って、仮想サーバが利用不可であり、この仮想サーバに割り当てられたであろうタスクを代わりにこの仮想サーバの近隣サーバに送信する場合には、この近隣サーバが既にこのタスクに関連するセッション情報へのアクセスを有する。従って、上述のようなフルメッシュ複製、又は高性能ＳＡＮの提供、又は何らかの他のストレージ機構を必要とすることなく、コンテクストが関連付けられた要求を容易に近隣サーバに再割り当てすることができる。
【００２２】
本発明はまた、複数の仮想サーバを含むサーバを提供し、サーバは、複数のサーバを含むシステムの一部を形成し、複数のサーバのうちの少なくとも一部（全ての場合もある）は、複数の仮想サーバを含み、サーバは、各仮想サーバが近隣仮想サーバに関連付けられるようになっており、各仮想サーバの近隣サーバは、異なるサーバの一部であり、仮想サーバの近隣サーバは、このサーバのバックアップとして作用する。
【００２３】
要求で第１仮想サーバに提供されるセッションデータは、第１仮想サーバの近隣仮想サーバに対して複製することができる。従って、上述のようなフルメッシュ複製、又は高性能ＳＡＮの提供、又は何らかの他のストレージ機構を必要とすることなく、コンテクストが関連付けられた要求を容易に近隣サーバに再割り当てすることができる。
【００２４】
本発明の一部の形態では、（物理）サーバが作動不能な場合に、残りのサーバの各仮想サーバが、異なる他の（物理）サーバによって提供される近隣サーバを有する。
【００２５】
本発明の一部の形態では、（物理）サーバが作動不能な場合に、残りの（物理）サーバの２つの仮想サーバが、同じ他のサーバによって提供される近隣サーバを有し、サーバのあらゆる残りの仮想サーバの各々は、異なる他のサーバによって提供される近隣サーバを有する。
【００２６】
本発明の多くの形態において、以下の条件の１つ又はそれよりも多くが適用される。
【００２７】
１．あらゆる仮想サーバ／ノード（ピア）に関して、この仮想サーバ及びこの近隣（後継）は、異なる（物理）サーバによって提供される。
２．同じ物理サーバ内のあらゆる２つの仮想サーバ／ノード（ピア）に関して、これらの近隣は、異なる他の物理サーバ内に位置する。
３．いずれか１つの物理サーバに障害が生じた後でも、あらゆる仮想サーバ／ノードに関して、このノードの仮想サーバ及びこの近隣は、依然として異なる物理サーバ内に位置する。
４．２つの物理サーバが故障した場合には、あらゆる仮想サーバ／ノード（ピア）に関して、この仮想サーバ及びこの近隣は、異なる物理サーバによって提供される。
【００２８】
本発明は、複数のサーバを含むシステムを更に提供し、サーバのうちの少なくとも一部（全ての場合もある）は、複数の仮想サーバを含み、各仮想サーバは、近隣サーバに関連付けられ、各仮想サーバの近隣サーバは、異なる他のサーバの一部であり、仮想サーバの近隣サーバは、このサーバのバックアップとして作用する。
【００２９】
本発明の多くの形態において、サーバの各々は、複数の仮想サーバを含む（又は提供する）。
【００３０】
本発明の多くの形態において、特定の（物理）サーバによって提供される複数の仮想サーバの各々は、異なる他のサーバによって提供される近隣サーバを有する。従って、特定の物理サーバが作動不能になる場合、この物理サーバによって提供される様々な仮想サーバの負荷は、多くの異なる他のサーバ間に分散される。
【００３１】
システムは、スケジューラーを更に含み、スケジューラーは、要求を受け取るための入力と、要求を第１仮想サーバに転送するための出力と、第１仮想サーバを選択するためのプロセッサとを含む。更に、選択した仮想サーバの障害（例えば、仮想サーバが一部を形成するサーバの障害）の場合には、プロセッサが第１仮想サーバの近隣サーバを選択することができ、スケジューラーの出力は、要求を近隣サーバに転送することができる。
【００３２】
要求で第１仮想サーバに提供されるセッションデータは、第１仮想サーバの近隣仮想サーバに対して複製することができる。
【００３３】
本発明の一部の形態では、（物理）サーバが作動不能な場合に、残りのサーバの各仮想サーバが、異なる他の（物理）サーバによって提供される近隣サーバを有する。
【００３４】
本発明の一部の形態では、（物理）サーバが作動不能な場合に、残りの（物理）サーバの２つの仮想サーバが、同じ他のサーバによって提供される近隣サーバを有し、サーバのあらゆる残りの仮想サーバの各々は、異なる他のサーバによって提供される近隣サーバを有する。
【００３５】
本発明は、要求を受け取るためのコード（又は何らかの他の手段）と、要求を転送するための第１仮想サーバを選択するためのコード（又は何らかの他の手段）とを含むコンピュータプログラムを更に含み、第１仮想サーバは、複数の（物理）サーバのうちの１つによって提供され、（物理）サーバのうちの少なくとも一部（全ての場合もある）は、複数の仮想サーバを含み又は提供し、コンピュータプログラムは、更に、選択した第１仮想サーバが要求を受け取ることができない場合には、要求を第１仮想サーバの近隣仮想サーバに転送するためのコード（又は何らかの他の手段）を含み、第１仮想サーバの近隣仮想サーバは、第１仮想サーバとは異なるサーバによって提供される。コンピュータプログラムは、コンピュータと共に使用するために内部に具現化されたコンピュータプログラムコードを有するコンピュータ可読媒体を備えたコンピュータプログラム製品とすることができる。
【００３６】
付番された以下の概略図面を単に例示的に参照して本発明の例示的な実施形態について以下で説明する。
【図面の簡単な説明】
【００３７】
【図１】クラスターの複数のサーバ間で要求を割り当てるための公知のシステムのブロック図である。
【図２】本発明の態様によるシステムのブロック図である。
【図３】本発明の態様による仮想サーバ配備を示す図である。
【図４】仮想サーバの一部が作動不能な場合の図３の仮想サーバ配備を示す図である。
【図５】本発明の更に別の態様による仮想サーバ配備を示す図である。
【図６】仮想サーバの一部が作動不能な場合の図５の仮想サーバ配備を示す図である。
【図７】仮想サーバの一部が作動不能な場合の図５及び６の仮想サーバ配備を示す図である。
【発明を実施するための形態】
【００３８】
図２は、参照番号１０によって一般的に示す本発明の態様によるシステムのブロック図である。
【００３９】
システム１０は、スケジューラー１２と、第１サーバ１６と、第２サーバ１７と、第３サーバ１８とを含む。第１サーバ１６は、第１仮想サーバ２１及び第２仮想サーバ２２を含む。第２サーバ１７は、第１仮想サーバ２３及び第２仮想サーバ２４を含む。第３サーバ１８は、第１仮想サーバ２５及び第２仮想サーバ２６を含む。
【００４０】
システム１０において、スケジューラー１２は、到着する要求を受け取り、要求を何らかのアルゴリズムに従ってサーバに転送する責任を担う。仮想サーバ２１から２６には、アイデンティティ（ＩＤ）が割り当てられる。仮想サーバ２１から２６は、原理上、いずれのアルゴリズムも実施することができ、仮想サーバ２１から２６によって実施されるアルゴリズムは、本発明には関係ない。
【００４１】
スケジューラー１２は、要求をサーバ２１から２６までに転送し、各サーバの負荷の均衡を保つ。スケジューラーは、高速の要求転送をもたらすために、宛先サーバの検索が簡単なように設計すべきである。同様に、サーバに障害が生じた場合にバックアップサーバを選択するための高速で簡単なアルゴリズムを提供すべきである。「通常の」宛先（仮想）サーバ、及び通常の宛先サーバの障害の場合のバックアップ（仮想）サーバの両方を選択するためのアルゴリズムについて、以下で更に説明する。最後に、スケジューラー１２は、あまり多くのメモリを必要とすべきではない。
【００４２】
例として、ハッシュベースの検索を提供することができる。ハッシュベースの検索方法では、スケジューラー１２で要求を受け取ると、スケジューラーが、クライアントのＩＰアドレス及びポート番号、ＳＩＰでのクライアントのＵＲＬ、ＧＴＰでのＴＥＩＤなどのような要求メッセージから取得可能なセッションの何らかの識別子に基づいてハッシュ値を計算する。各サーバ（又は仮想サーバ）は、値空間全体の一連の値に責任を有するので、スケジューラーは、いずれのサーバの範囲が計算したこのハッシュ値を含むかを見出して、このサーバに要求を転送することになる。
【００４３】
適切なハッシュ関数により、値空間においてハッシュ値の一様分布を得ることができる。従って、サーバの値範囲は、各サーバの実際の処理機能に合うように選択し又は調整することさえ可能である。負荷をセッション番号で測定すると、ハッシュ値に基づいて要求をスケジュールすることによって負荷バランシングが達成される。
【００４４】
所定の値と適合する範囲を見出すための詳細な検索方法に関しては、線形検索、バイナリ検索、平衡バイナリ検索ツリーなどのような使用することができる多くの利用可能なアルゴリズムが存在する。
【００４５】
別の代替的な検索方法は、セッション識別子のハッシュ値をインデックスとして利用して、担当する宛先サーバを検索するものである。正確なハッシュ値をインデックスとして用いて、各インデックス値毎に対応するサーバ情報を格納するための大型のテーブルを構築する。しかし、この方法は、メモリ要件のために一般的には好ましくない。このインデックステーブルのサイズは、インデックス値のいくつかを無視すれば、低減することができる。例えば、インデックス内の一部のプレフィクスビットのみを用いることによってこのテーブルのサイズを低減することができる。
【００４６】
ハッシュ値のプレフィクスを用いることは、ＩＤ空間を小さいセグメントに分割するのに等しく、このインデックステーブル内の各エントリがセグメントを表している。プレフィクスビットの数により、値空間内の対応するセグメントのサイズが決まる。これらのセグメントを「メタセグメント」と呼ぶ。各サーバの範囲が、１つ又はそれよりも多くのセグメントのみを包含する場合、所定の値による包含する範囲の検索のタスクは、ハッシュ値をインデックスとして用いてインデックステーブルを検索し、包含するメタセグメントを見出すことになる。
【００４７】
より詳細には、範囲の検索は２段階から構成される。第１段階は、セッション識別子のハッシュ値をインデックスとして用いて、適合するメタセグメントを見出すことである。第２段階では、メタセグメントに対応するサーバ範囲を見出す。従って、別のサーバテーブルがサーバの情報を格納する必要がある。インデックステーブル内のメタセグメントの各エントリは、サーバテーブル内の包含するサーバ範囲を表すエントリを指すことになる。従って、ハッシュ値から何らかのサーバ範囲へのマッピングは、２つの検索テーブルを用いて行うことができる。
【００４８】
上述のように、サーバ１６、１７、及び１８の各々が複数の仮想サーバに分割される。仮想サーバの各々には、通常はアイデンティティ（ＩＤ）が与えられる。
【００４９】
図３は、参照番号２０によって一般的に示す仮想サーバ２１から２６の円形の配置を示している。図３の頂点から開始して、円を時計回りに移動すれば、仮想サーバは、以下の順序で与えられる：
【００５０】
１．第１サーバ１６の第１仮想サーバ２１
２．第２サーバ１７の第１仮想サーバ２３
３．第３サーバ１８の第１仮想サーバ２５
４．第２サーバ１７の第２仮想サーバ２４
５．第１サーバ１６の第２仮想サーバ２２
６．第３サーバ１８の第２仮想サーバ２６
【００５１】
本発明では、近隣サーバは、時計回り方向の次の仮想サーバとして定義される。従って、仮想サーバ２３は仮想サーバ２１の近隣であり、仮想サーバ２５は仮想サーバ２３の近隣であり、仮想サーバ２４は仮想サーバ２５の近隣であり、仮想サーバ２２は仮想サーバ２４の近隣であり、仮想サーバ２６は仮想サーバ２２の近隣であり、仮想サーバ２１は仮想サーバ２６の近隣である。
【００５２】
本発明は、１つのサーバ内のセッションを自己の次の近隣サーバに対して複製する。近隣サーバを定義することにより、特定のサーバ（又は仮想サーバ）によるセッションの処理は、第１サーバの障害の場合に近隣サーバによって容易に引き継ぐことができる。このフェイルオーバーでは、スケジューラーが、この障害期間中に要求を正しい宛先に転送する必要がある。
【００５３】
当然ながら、近隣サーバは、別の方法で定義することができる。重要な点は、スケジューラー１２が特定のサーバの近隣を決めるのが容易でなければならないことである。
【００５４】
近隣をバックアップとして使用する場合、過負荷状況が発生する可能性がある。第１サーバＡに障害が生じると、サーバＡが処理する要求が、サーバＡのバックアップサーバ、すなわち、サーバＢに配送されることになる。従って、サーバＡの負荷が、サーバＢの負荷に追加されることになる。サーバＢが過負荷にならないよう保証するための最も簡単な機構は、障害前のサーバＡ及びＢの通常の負荷が、これらのサーバの容量全体の５０％未満になるよう保証することである（これらのサーバに関して同様の容量を前提とする）。当然ながら、これは、かなりの容量を無駄にする。複数の仮想サーバの使用及び図３に示す配置は、以下で説明するようにこの状況を改善する。
【００５５】
図４は、円形に分散された仮想サーバ２１から２６の配置を示しており、参照番号２０’によって示している。配置２０’が、図３を参照して上記で説明した配置２０と異なるのは、サーバ１６が機能していない点である。従って、（物理サーバ１６によって提供される）仮想サーバ２１及び２２が機能しておらず、配置２０’には点線に示している。
【００５６】
上述の近隣原理によれば、仮想サーバ２１に対して行われたであろう要求は、ここでは仮想サーバ２３に経路指定される（次の仮想サーバは配置２０を時計回りに移動する）。仮想サーバ２２に対して行われたであろう要求は、ここでは仮想サーバ２６に経路指定される（次の仮想サーバは配置２０を時計回りに移動する）。この経路指定は、スケジューラー１２によって処理される。当然ながら、近隣として、仮想サーバ２３及び２６は、サーバ２１及び２２にそれぞれ関連するコンテクストデータを既に受け取っていることになる。
【００５７】
仮想サーバ２３は、第２サーバ１７の一部であり、仮想サーバ２６は、第３サーバ１８の一部である。従って、サーバ１６の仮想サーバに対して行われたであろう要求は、サーバ１７及び１８の仮想サーバ間に分割される。従って、この状況では、機能している各物理バックアップサーバが、障害のあったサーバから過度の負荷を引き継ぐことはない。各物理サーバが自己の負荷を約６０％保持する場合に、障害のあったサーバの負荷が自己のバックアップサーバの負荷に追加されると、負荷全体は約９０％である（サーバに関して同様の容量及び負荷を前提とする）。
【００５８】
原理上、物理サーバ毎により多くの仮想サーバを使用して、障害のあったサーバの負荷をより多くの他の物理サーバに更に分散させることができる。従って、通常の状況で、各サーバに関して許容可能な負荷を更に引き上げることができる。
【００５９】
（サーバ１６のような）サーバに障害が生じると、スケジューラー１２は、サーバ（又はこの物理サーバの仮想サーバ）の要求をこのバックアップ近隣サーバに転送するために迅速に対応する必要がある。ここで、サーバは仮想サーバであり、又は単なるサーバＩＤと見なすことができる。
【００６０】
線形範囲検索アルゴリズムでは、要求が、現在到達可能でない特定のサーバ範囲に適合することが見出される場合、スケジューラーは、線形テーブル内で１エントリ下に単に移動して、障害のあったサーバの近隣に関する情報を得る必要がある。サーバの情報は、担当する範囲の昇順で配置されると仮定する。
【００６１】
バイナリ検索及びインデックステーブル検索アルゴリズムでは、サーバの情報は、サーバテーブル内に配置することができ、このエントリは、範囲の順序である。検索の結果は、サーバテーブル内の適切なエントリへのポインタである。
【００６２】
従って、要求の検索後に最終ポインタ値をインクリメントすることにより、近隣サーバのエントリを取得することになる。
【００６３】
当然ながら、他のアルゴリズムが可能である。
【００６４】
図４を参照して上述したように、本発明は、あらゆる物理サーバの全ての仮想サーバに関して、バックアップ近隣が異なる他の物理サーバに属する必要がある配置を提供する。それによって物理サーバに障害が生じた場合、障害のあった物理サーバによって提供される仮想サーバの負荷が複数のバックアップサーバ間に分割されることを保証する。図５は、この条件を満たし、更に別の条件も満たす配置を示しており、参照番号３０によって一般的に示している。更に別の条件は、いずれか１つの物理サーバに障害が生じた場合に、残されたいずれかの物理サーバの仮想サーバに関して、バックアップ近隣も異なる他の物理サーバに属する必要があるという要件である。
【００６５】
図５に示す配置３０は、第１サーバの第１仮想サーバ３１及び第２仮想サーバ３２と、第２サーバの第１仮想サーバ３３及び第２仮想サーバ３４と、第３サーバの第１仮想サーバ３５及び第２仮想サーバ３６と、第４サーバの第１仮想サーバ３７及び第２仮想サーバ３８と、第５サーバの第１仮想サーバ３９及び第２仮想サーバ４０とを含む。図５には仮想サーバ３１から４０を示しているが、明確にするために、これらの仮想サーバを提供する物理サーバは、スケジューラーと同様に省略する。
【００６６】
図５の頂点から開始して、円を時計回りに移動すれば、仮想サーバ３１から４０は、以下の順序で配置される。
【００６７】
１．仮想サーバ３１。
２．仮想サーバ３３が仮想サーバ３１の近隣になるような仮想サーバ３３。
３．仮想サーバ３５が仮想サーバ３３の近隣になるような仮想サーバ３５。
４．仮想サーバ３７が仮想サーバ３５の近隣になるような仮想サーバ３７。
５．仮想サーバ３９が仮想サーバ３７の近隣になるような仮想サーバ３９。
６．仮想サーバ３２が仮想サーバ３９の近隣になるような仮想サーバ３２。
７．仮想サーバ３８が仮想サーバ３２の近隣になるような仮想サーバ３８。
８．仮想サーバ３４が仮想サーバ３８の近隣になるような仮想サーバ３４。
９．仮想サーバ４０が仮想サーバ３４の近隣になるような仮想サーバ４０。
１０．仮想サーバ３６が仮想サーバ４０の近隣になり、仮想サーバ３１が仮想サーバ３６の近隣になるような仮想サーバ３６。
【００６８】
図２から４を参照して上記で説明したシステム１０と同様に、仮想サーバ３１から４０は、仮想サーバの一部を提供する物理サーバのいずれか１つが作動不能な場合に、現在作動不能な仮想サーバの各々が異なる物理サーバの仮想サーバによってバックアップされるように配置する。
【００６９】
図６は、参照番号３０’によって一般的に示す配置を示している。配置３０’は、配置３０に類似し、（点線に示した）仮想サーバ３１及び３２が作動不能な点だけが異なる。仮想サーバ３１及び３２はいずれも、第１サーバ（図示せず）によって提供され、従って、配置３０’は、第１サーバが作動不能な状況を示している。
【００７０】
上述のように、仮想サーバが作動不能な場合、近隣仮想サーバが使用される。従って、仮想サーバ３１に転送されたであろう要求は、ここでは仮想サーバ３３に転送され、仮想サーバ３２に転送されたであろう要求は、ここでは仮想サーバ３８に転送される。仮想サーバ３３は第２サーバによって提供され、仮想サーバ３８は第４サーバによって提供され、従って、現在作動不能な第１サーバの負荷が２つの異なる他のサーバに分散される。
【００７１】
従って、（配置１０と同様に）配置３０は、いずれかの物理サーバの全ての仮想サーバに関して、バックアップ近隣が異なる他の物理サーバに属すようになっている。しかし、上記で指摘したように、配置３０は、いずれか１つのサーバに障害が生じた場合に、残されたいずれかの物理サーバの仮想サーバに関して、バックアップ近隣も異なる他の物理サーバに属する必要があるので更に踏み込んだものになっている。
【００７２】
図７は、参照番号３０’’によって一般的に示す配置を示している。参照番号３０’’は、配置３０及び３０’に類似し、仮想サーバ３１、３２、３５、及び３６（点線で図示）が作動不能な点だけが異なる。仮想サーバ３１及び３２はいずれも第１サーバ（図示せず）によって提供され、仮想サーバ３５及び３６はいずれも第３サーバ（図示せず）によって提供される。従って、配置３０’’は、第１及び第３サーバが作動不能な状況を示している。
【００７３】
従って、仮想サーバ３５に転送されたであろう要求は、ここでは仮想サーバ３７に転送され、仮想サーバ３６に転送されたであろう要求は、ここでは仮想サーバ３３に転送される。仮想サーバ３７は第４サーバによって提供され、仮想サーバ３３は第２サーバによって提供され、従って、現在作動不能な第３サーバの負荷が２つの異なる他のサーバに分散される。
【００７４】
上述の近隣原理は、以下に説明するように一般化することができる。
【００７５】
各物理サーバがＮ個の仮想サーバを有し、合計でｍ個の物理サーバが存在すると仮定する。
【００７６】
上述の第１要件（配置１０及び３０の両方によって満たされる）は、以下のように規定することができる。
・いずれかの物理サーバのＮ個の全ての仮想サーバに関して、これらのバックアップ近隣は、異なる他のｍ個の物理サーバに属する必要がある。
【００７７】
上述の第２要件（配置３０によって満たされるが、配置１０によっては満たされない）は、以下のように規定することができる。
・いずれか１つの物理サーバに障害が生じた場合に、残りの物理サーバのいずれかのＮ個の仮想サーバに関して、バックアップ近隣は、異なる他のｍ個の物理サーバに属する必要がある。
【００７８】
第２の条件を満たすことが数学的に可能でないことがある。例えば、Ｎ＋１＝ｍの場合、障害が生じると、物理サーバの最大数が関わることになる。従って、バックアップ処理を要する要求は、作動中の他のＮ個の物理サーバの全ての助けを得ることになる。各物理サーバは、最小数の追加要求を引き受けるに過ぎない。
【００７９】
第２の条件を満たすことができない場合には、以下のように言い換えることができる。
・いずれか１つの物理サーバに障害が生じた場合に、いずれかの残りの物理サーバのＮ個の仮想サーバに関して、これらのバックアップ近隣は、異なる他のｍ−１個の物理サーバに属する必要がある。従って、同じ物理サーバをバックアップ近隣として共有することができる１物理サーバの２つの仮想サーバが存在する。
【００８０】
ここで、ＩＤ空間の円形内に仮想サーバ配備の一部の例を列挙する。状況の各々は、上述の第１及び第３要件を満たす。物理サーバ当たり４、８、及び１６仮想サーバを有する例について説明する。当然ながら、Ｎ及びｍの別の組合せの仮想サーバ配備のソリューションは、当業者には容易に明らかであろう。
【００８１】
仮想サーバを表すために数字を使用し、数字の値は、物理サーバを表している。数字の行を用いて、空間円内の仮想サーバの実際の配置を示し、数字の行を１つずつ時計回りに円に沿って配置すると見なすことができる。
【００８２】
５つの物理サーバが存在する場合、これらに０から４の付番を行う。各物理サーバは４つの仮想サーバを有するので（Ｎ＋１＝ｍになるように）、各値は、４回出現することになる。以下の表は、上述の第１及び第３要件を満たすソリューションを示している。
0005599943.tif 000002
【００８３】
例えば、物理サーバ１に障害が生じた場合、４つの仮想サーバがバックアップを提供する必要がある。第１行では、バックアップ仮想サーバは物理サーバ２に属す。第２行では、バックアップ仮想サーバは物理サーバ４に属す。第３行では、バックアップ仮想サーバは物理サーバ０に属す。第４行では、バックアップ仮想サーバは物理サーバ３に属す。４バックアップ仮想サーバ全てが、上述の第１要件で上述のように、４つの異なる物理サーバに属すことを認識することができる。他の物理サーバの障害も依然としてこの要件を満たす。
【００８４】
更に、物理サーバ１の障害後、仮想サーバの配置は以下の通りである。
0005599943.tif 000003
【００８５】
この状況では、第３要件を満たす。例えば、物理サーバ０の場合、この近隣は２、３、及び４を含み、物理サーバ２に属す２つの仮想サーバが存在する。
【００８６】
９つの物理サーバが存在する場合、０から８の付番を行い、各物理サーバは８仮想サーバを有し、これはすなわち、仮想サーバ配備の表に８行が存在することを意味する。以下の表は、考えられるソリューションの１つを示しており、第１及び第３要件を満たす。
0005599943.tif 000004
【００８７】
例えば、物理サーバ１に障害が生じた場合、バックアップ近隣は、各行においてそれぞれ物理サーバ２、５、６、８、０、３、４、及び７からになる。
【００８８】
サーバ１の障害後の仮想サーバ配備は、依然として第３要件を満たし、別の物理サーバの更に別の障害により、他の作動中の７サーバへのほぼ均等な要求の分散に至ることになる。
【００８９】
１７個の物理サーバが存在する場合、各物理サーバは１６個の仮想サーバを有することができる。以下の表は、仮想サーバ配備のソリューションの１つを示している。
0005599943.tif 000005
【００９０】
例えば、物理サーバ１に障害が生じた場合、バックアップ近隣は、各行においてそれぞれ物理サーバ２、５、６、９、１０、１３、１４、１６、０、３、４、７、８、１１、１２、及び１７からになる。近隣のリストに重複はなく、これは第１要求を満たす。
【００９１】
第３要件を満たすことの妥当性確認は、全ての行で数字のいずれかを削除することによって実行することができる。
【００９２】
上述のような仮想サーバの配置の要件を満たす問題は、以下でより詳細に説明するように数学的に表現することができる。
【００９３】
第１の問題は、値が１からｍの一連の正の整数が存在する場合に定義することができる。各値に関してｋ個の数字が存在し、ｋは、正の整数である。合計でｋｘｍの数字が存在する。これらの数字は円形に配置される。特定の数字の次の数字は、時計回りに沿うように定義し、ｎｅｘｔ（ａ）と示している。以下の要件を満たす、円形の数字の配置を見出す必要がある：
【００９４】
１．円内のあらゆる数字ａに関して、ｎｅｘｔ（ａ）≠ａ。
２．１からｍのあらゆる値ｘに関して、セット｛ｂ｜ｂ＝ｎｅｘｔ（ａ），ａ＝ｘ｝内に相互に等しい２つの数字がない。
３．いずれか同じ値（１からｍ）のｋ個の数字が円から削除される場合、円内に残された数字は依然として要件１）を満たす必要がある。
４．これらの数字は、（数字によって分割される）円内のセグメントの長さが、できる限り相互に接近するように、できる限り均等に円内に配置する必要がある。
５．（値ｍの）新しいｋ個の数字が円に付加される場合、他の数字の位置は変わらず、新しい円内の数字は依然として上述の要件を満たす必要がある。
これは、ｍ個の物理サーバが存在し、各物理サーバがｋ個のピアＩＤを有する状況を示している。
【００９５】
要件１）は、あらゆる仮想ノード（ピア）に関して、自己及び自己の第１後継（ピア）が異なる物理サーバ内に位置することを意味する。
要件２）は、同じ物理サーバ内のあらゆる２仮想ノード（ピア）に関して、これらの第１後継が異なる他の物理サーバ内に位置することを意味する。
要件３）は、いずれか１つの物理サーバ障害後にも、あらゆる仮想ノード（ピア）に関して、自己及び自己の第１後継（ピア）が依然として異なる物理サーバ内に位置することを意味する。
要件４）は、ピアの担当する空間セグメントをセグメント長の点で異ならないように保とうとする。
要件５）は、他のピアの位置を移動しないように保ちながら、新しい物理サーバの付加をサポートするよう求める。
【００９６】
第１の問題と類似する第２の問題も定義することができるが、この場合、１からｍのｍ個の整数値が存在し、各値に関してｋ個の数字が存在する。円形のこれらの数字の配置は、以下の要件を満たすことになる：
１．問題１の要件１）、２）、３）、４）、及び５）全てを満たす。
２．１からｍのあらゆる値ｘ、ｙに関して、Ｘ＝｛ｂ｜ｂ＝ｎｅｘｔ（ａ），ａ＝ｘ｝及びＹ＝｛ｂ｜ｂ＝ｎｅｘｔ（ａ），ａ＝ｙ｝を定義し、ｙ∈Ｘの場合、
0005599943.tif 000006
である。
３．ｋ個の同じ値の数字の削除後に同じ値を有するｋ個の数字の別の群が削除される場合、円内に残された数字は依然として要件１）を満たす必要がある。
要件７）は、物理サーバＡが物理サーバＢのデータの一部をバックアップし、物理サーバＢが物理サーバＡのデータの一部をバックアップするような場合を除外することに注意する必要がある。要件８）は、２つの物理サーバが機能停止する場合でさえ、あらゆる仮想ノード（ピア）に関して、自己及び自己の第１後継が異なる物理サーバ内に位置することを保証することにも注意する必要がある。
【００９７】
１つの物理サーバが機能停止する場合、問題１及び２に関して、この作業負荷は、他のｋ（ｋ＜ｍ）個の物理サーバに均等に分散させることができる。特に問題１の場合には、ｋ＝ｍ−１の時に、フェイルオーバー時の厳密な負荷平衡（ＬＢＩＦ）に達することができ、すなわち、障害のあったサーバの全ての作業負荷が他の全てのサーバに均等に分散され、異なる物理サーバ間の負荷比率は、（ｋ＋１）：（ｋ＋１）であり、他の場合には、異なる物理サーバ間の最大負荷比率は、（ｋ＋１）：ｋである。
【００９８】
２つ又はそれよりも多くの物理サーバが機能停止する場合も、ハイプ（ｈｙｐｅ）最適化された負荷平衡を維持することができ、異なる物理サーバ間の最大負荷比率は、ｋ値及び問題１つ又は２に応じて、（ｋ＋３）：（ｋ＋２）、又は（ｋ＋３）：（ｋ＋１）、又は（ｋ＋３）：ｋのいずれかであり、特に問題１の場合には、ｋ＝ｍ−１の時に、最大負荷比率は、（ｋ＋３）：（ｋ＋２）である。
【００９９】
「フェイルオーバーにおける負荷バランシングのための仮想ノードＩＤ割り当て（ＶＮＩＡＬ）」アルゴリズムについて、ここで説明する。第１に、特殊なケース、すなわち、ｍが素数である場合に関して円形に数字を配置する方法について説明し、第２に、これを一般的なケースに拡大適用し、すなわち、ｍが素数か又は合成数かに関わらず、新しい数字を円内に付加する方法を紹介する。
【０１００】
定義：所定の自然数ｍに関して、以下の場合かつ以下の場合に限り、自然数α及びβは共役である。
１）α及びｍが、相互に比較的原始的（素）であり、かつ
２）β及びｍが、相互に比較的原始的（素）であり、かつ
３）
0005599943.tif 000007
ｍが素数である特殊な場合、第１の問題は以下のように解決される。
【０１０１】
問題１の説明から、ｍ＞ｋであることは容易に認識することができる。従って、以下の説明は、ｍ＞ｋを前提とする。初等整数論から、あらゆる素数（＞４）は、１つ又はそれよりも多くの原始根を有する。ｒがｍの原始根であると仮定して、一連の行ベクトルを以下のように定義する。
0005599943.tif 000008
0005599943.tif 000009
0005599943.tif 000010
【０１０２】
ｒはｍの原始根なので、ｍ−１個の特殊な行ベクトルが存在するだけであって、いずれの
0005599943.tif 000011
に関しても
0005599943.tif 000012
であり、
0005599943.tif 000013
は、数字１，２，・・・ｍ−１の完全置換である。これは、すなわち、ｋの最大がｍ−１であり、まずｋ＝ｍ−１と見なす。
【０１０３】
Ｘi（ｉ＝１，２，３，．．．，ｍ−１）を円に沿って順に配置するこのような配置は、新しい数字を付加する要件以外の問題１の要件を満たすことができる。新しい数字を付加するアルゴリズムについては、別の節で説明する。
【０１０４】
実際に、一連の行ベクトルを以下のように定義することができる。
0005599943.tif 000014
この場合、以下のようになる。
0005599943.tif 000015
0005599943.tif 000016
0005599943.tif 000017
結論：以下を立証することができる
１）
0005599943.tif 000018
この場合、
0005599943.tif 000019
２）
0005599943.tif 000020
この場合、
0005599943.tif 000021
３）問題１の要件を満たすために、Ｖiには、Ｖm-i以外のいずれかの他のベクトルが（時計回りで）続くことができる。
４）問題１の要件を満たすことができるこれらのベクトルを配置するための様々な方法があり、例えば、以下の通りである。
0005599943.tif 000022
この場合、
0005599943.tif 000023
５）Ｖi及びＶm-iの各共役の組から、ただ１つのみを選択し、また、問題１の付加的要件７）も満たすことができる。例えば、以下の通りである。
0005599943.tif 000024
【０１０５】
第２の問題は、以下のように解決することができる。ｍが素数の時に、ｒはｍの原始根である。ｍ−１個の異なる行ベクトルＸi（ｉ＝１，２，３，．．．，ｍ−１）が節０で上述のように生成された。いずれの２つの値も、ただ一度だけ近隣になり得るので、
0005599943.tif 000025
を得ることができる。
0005599943.tif 000026
とすると、上述のｍ−１個のベクトルからｔ個のベクトルを選択して、一定の順序に従ってこれらを円に沿って配置することができる。
【０１０６】
結論：以下を立証することができる
１）２もｍ−２もｍの原始根でない場合、円に沿って以下のｔ個のベクトルを配置すると、問題２の要件を満たすことができる。
0005599943.tif 000027
この場合、あらゆる数字が、ある意味でＭＯＤ演算であり、すなわち、これらは［１，ｍ］の範囲にある。
２）２又はｍ−２がｍの原始根である場合（ｍ＞７）、この原始根を用いて上述のようなベクトル
0005599943.tif 000028
を生成し、以下のように偶奇性に基づいて円に沿ってｔ個のベクトルを配置すると、問題２の要件を満たすことができる。
0005599943.tif 000029
３）ｍ＝７の場合には、Ｖ1、Ｖ4、Ｖ2を円に沿って配置すると、問題２の要件を満たすことができる。
ｍ＝５は小さすぎて、ｋ＞１の場合は問題２の要件を満たすことができないことに注意する必要がある。
【０１０７】
ｍが素数であるか否かに関わらず、第１の問題は以下のように解決することができる。いずれのｍに関しても、１からｍの全ての数字に関して、ｍに対して比較的原始的（素）なのは、
0005599943.tif 000030
である。
0005599943.tif 000031
及び
0005599943.tif 000032
は、共役であることを立証することができる。これで、
0005599943.tif 000033
個の行ベクトルを有する。
0005599943.tif 000034
【０１０８】
結論：以下を立証することができる
１）いずれのベクトルＶiに関しても、唯一のベクトルＶj（すなわち、
0005599943.tif 000035
）が存在し、これは、円に沿って（時計回りに）Ｖiの次のベクトルにはなり得ない。
２）いずれの
0005599943.tif 000036
に関しても、ベクトルの以下の配置は、問題１の要件を満たす。
0005599943.tif 000037
３）ｋの最大値は
0005599943.tif 000038
である。
４）ｍが素の場合、
0005599943.tif 000039
0005599943.tif 000040
であり、ｉ＝１，２，３，．．．，ｍ−１である。
【０１０９】
第２の問題は、以下のように解決することができる。依然として上述のベクトルセット｛Ｖi｜
0005599943.tif 000041
｝内には、
φ（ｍ）／２個のベクトルが存在し、何らかの一定の順序によるこれらの配置が問題２の要件を満たすことができることを立証することができる。このベクトルセットのベクトルを選択する方法は、ｍの偶奇性に依存する。
【０１１０】
αi及びｍ−αiの各共役の組において、これらのうちの１つを選択すればよい。このようにして、合計でφ（ｍ）／２の数のαiが存在する。選択したαiを用いてφ（ｍ）／２個のベクトルを生成することができる。
0005599943.tif 000042
【０１１１】
ここで、ベクトルの正しい位置を形成する方法について別々に説明する。
・ｍが偶数：円に沿って（時計回りに）φ（ｍ）／２ベクトルのいずれの順序も、問題２に関しては許容されることを立証することができる。
・ｍが奇数：φ（ｍ）／２≧７の時には、問題２の要件を満たすφ（ｍ）／２ベクトルの順序が存在することを立証することができる。しかし、ベクトルの順序を解決するための特定の方法は見出していない。ベクトルの実現可能な配置は、素数ｍの状況に基づいて数字を付加することによって達成することができ、これについて、次の節で説明する。
【０１１２】
第１及び第２の問題の基本要件を満たすように円に沿って数字を配置するという問題が解決されると、次の目標は、数字の近隣への制約に違反することなく、確定済みの円に新しい数字を付加することによってシステムを拡張することである。ｍが素数の場合はこれらの数字を配置するための完璧なソリューションが存在するので、このケース（ｍが素数）から開始する。新しい数字を付加する方法があれば、より小さいが素数ｍのケースから数字を付加することにより、非素数ｍの他のいずれのケースも解決することができる。
【０１１３】
更なる説明の前に、以下のようにＶｉ（ｉ＝１，２，３，．．．，ｍ−１）から（ｍ−１）ｘｍ行列を生成し、これを基本世代行列と呼ぶ。
0005599943.tif 000043
かつ（ｍ−１）ｘｍ行列を定義する。
0005599943.tif 000044
（ｍ−１）ｘｍ行列の連続を以下のように定義する。
0005599943.tif 000045
0005599943.tif 000046
この場合の
0005599943.tif 000047
（ｉ＝１，２，３，．．．，ｍ）は、（ｍ−１）次元の列ベクトルであり、
0005599943.tif 000048
である。ここで、
0005599943.tif 000049
を見出すことができる。実際に、
0005599943.tif 000050
は、あらゆる要素に（ｊ−１）ｍが付加される以外は、Ｖに同等の行列である。
【０１１４】
0005599943.tif 000051
が
0005599943.tif 000052
行列（世代行列と呼ぶ）であるとして定義し、これを、本節のアルゴリズムに従って｛
0005599943.tif 000053
｜
0005599943.tif 000054
｝の融合から生成する。
0005599943.tif 000055
（
0005599943.tif 000056
）は、（ｍ−１）ｘｍ行列である。
【０１１５】
アルゴリズムの説明−ｍ＋１から２ｍまでの数字を挿入
0005599943.tif 000057
なので、ｍ＋１から２ｍ（ｍは素数）までの新しい数字を付加することは、行列
0005599943.tif 000058
及び
0005599943.tif 000059
を融合すると見なすことができる。手法は、以下のようになる。
１）２つの列
0005599943.tif 000060
及び
0005599943.tif 000061
の間に
0005599943.tif 000062
を挿入する。この場合、以下の通りである。
0005599943.tif 000063
２）行列
0005599943.tif 000064
の末尾に
0005599943.tif 000065
を保持する。
【数１】
0005599943.tif 000066
ここで、
0005599943.tif 000067
である。次に、
0005599943.tif 000068
0005599943.tif 000069
結論：以下を立証することができる
１）
0005599943.tif 000070
（又は
0005599943.tif 000071
又は
0005599943.tif 000072
）の全ての行ベクトルのある一定の配置は、問題１の要件を満たすことができ、ｔ個の行ベクトル（例えば、行１、２、・・・、ｔ）のある一定の配置は、問題２の要件を満たすことができる。
２）行列
0005599943.tif 000073
に関してｍ＋１から２ｍまでのいずれかの数字を削除後、残りの行列の全ての行ベクトルのある一定の配置は、問題１の要件を満たすことができ、残りの行列のｔ個の行ベクトルのある一定の配置は、問題２の要件を満たすことができる。
３）所定のｋに関して、
0005599943.tif 000074
又はｍ＋１から２ｍまでのいずれかの数字の削除後の残りの行列からｋ個の行を選択し、問題１及び問題２に関して上述した同様の方法でこれらを配置することができる。
【０１１６】
２ｍ＋１から４ｍまでの数字の挿入
２ｍ＋１から４ｍ（ｍは素数）までの新しい数字を付加することは、行列
0005599943.tif 000075
及び
0005599943.tif 000076
を融合し、行列
0005599943.tif 000077
及び
0005599943.tif 000078
を融合すると見なすことができ、上記と同様の手法に従う。
0005599943.tif 000079
及び
0005599943.tif 000080
を融合する時に、
0005599943.tif 000081
（又は
0005599943.tif 000082
）の２つの列
0005599943.tif 000083
及び
0005599943.tif 000084
の間に
0005599943.tif 000085
の
0005599943.tif 000086
を挿入する。ｉ＋ｊが偶数の場合とｉ＋ｊが奇数の場合とで以下のようになる。
0005599943.tif 000087
0005599943.tif 000088
及び
0005599943.tif 000089
の融合も同様である。
・行列
0005599943.tif 000090
の末尾に
0005599943.tif 000091
を保持する。
結論：以下を立証することができる
１）
0005599943.tif 000092
0005599943.tif 000093
0005599943.tif 000094
0005599943.tif 000095
及び、
0005599943.tif 000096
の全ての行ベクトルのある一定の配置は、問題１及び問題２の要件を満たすことができる。
２）行列
0005599943.tif 000097
に関して２ｍ＋１から４ｍまでのいずれかの数字を削除後、残りの行列の全ての行ベクトルのある一定の配置は、問題１の要件を満たすことができ、ｔ個の行ベクトル（例えば、行１、２、・・・、ｔ）のある一定の配置は、問題２の要件を満たすことができる。
３）所定のｋに関して、
0005599943.tif 000098
又は２ｍ＋１から４ｍまでのいずれかの数字の削除後の残りの行列からｋ個の行を選択し、問題１及び問題２の上述の同様の方法でこれらを配置することができる。
【０１１７】
0005599943.tif 000099
から
0005599943.tif 000100
までの数字の挿入
それは、
0005599943.tif 000101
及び
0005599943.tif 000102
の融合と見なすことができ、この場合、
0005599943.tif 000103
である。上記と同様の手法が続く。
・２つの列
0005599943.tif 000104
及び
0005599943.tif 000105
の間の
0005599943.tif 000106
に
0005599943.tif 000107
を挿入し、
0005599943.tif 000108
及び
0005599943.tif 000109
は、行列
0005599943.tif 000110
（又は
0005599943.tif 000111
）内で近隣であり、ｉ＋ｊが偶数の場合とｉ＋ｊが奇数の場合とで以下のようになる。
0005599943.tif 000112
・行列
0005599943.tif 000113
の末尾に
0005599943.tif 000114
を保持する。
結論：
0005599943.tif 000115
の場合に、以下を立証することができる
１）
0005599943.tif 000116
0005599943.tif 000117
0005599943.tif 000118
・・・、
0005599943.tif 000119
の全ての行ベクトルのある一定の配置は、問題１及び問題２の要件、更により厳しい要件さえも満たすことができる。
２）行列
0005599943.tif 000120
から、
0005599943.tif 000121
から
0005599943.tif 000122
までのいずれかの数字を削除後、残りの行列の全ての行ベクトルのある一定の配置は、問題１及び問題２の要件を満たすことができる。
３）所定のｋに関して、
0005599943.tif 000123
又は
0005599943.tif 000124
から
0005599943.tif 000125
までのいずれかの数字の削除後の残りの行列からｋ個の行を選択し、問題１及び問題２に関して上述した同様の方法でこれらを配置することができる。
【０１１８】
実際のところ、
0005599943.tif 000126
の時に、数字０、１、・・・、ｍに関して有効な行列を得ていた場合、数字ｍ＋１の新しいｋ個の複製は発見的検索によって行列に挿入することができることを立証することができる。言い換えれば、各行ベクトル内には新しい数字ｍ＋１のための少なくとも１つの有効な位置があり、新しい数字の位置は、計算ではなく検索によって見出すことができる。従って、発見的検索は、
0005599943.tif 000127
の時の別の手法である。
【０１１９】
非素数又は大きな素数Ｍのための世代行列を構築するための具体的な段階を以下のように説明する：
・段階１：素数ｍを見出す。この場合、ｍ≦Ｍ。
・段階２：基本世代行列を生成する
・段階３：節０で説明するように行列を拡張する。
・段階４：世代行列において値≧Ｍの要素を削除する
【０１２０】
多くの物理サーバの各々内の仮想サーバの数が同じである実施形態に関連して、本発明について一般的に説明した。これは、本発明の全ての実施形態に対して必須ではない。
【０１２１】
コンピュータサーバクラスターに関連して本発明を説明した。しかし、本発明の原理は、より広範にピアツーピアネットワークに適用することができる。特に、本発明は、構造的ピアツーピアオーバーレイで適用可能であり、この場合、全てのリソース及びピアには、１つの共通ハッシュＩＤ空間で識別子が割り当てられ、各ピアが空間の１エリアを担い、このエリアによって網羅されるリソースを担当する。１次元ＤＨＴ、例えば、Ｃｈｏｒｄにおいて、ＩＤ空間は、通常は線形セグメントに分割され、各ピアは１セグメントの責任を担い、ＣＡＮのようなｄ次元ＤＨＴでは、ｄ次元空間がｄ次元エリアに分割される。特定のリソースへの要求は、オーバーレイにより、このオーバーレイでこのリソースを担当する宛先ピアに経路指定される。
【０１２２】
いずれかのピアが何らかの理由で障害を生じ、オーバーレイから離れる場合、これが担当するエリア及びこのエリアで網羅されるリソースは、その第１の有効後継物（ピア）によって引き継がれ、このピア宛ての全ての要求が後継物に経路指定されてそれによって処理されることになり、この作業負荷は、この後継物にシフトされることになる。オーバーレイによって提供されるこの高利用可能性機能は、システムレベルＨＡと見なすことができる。
【０１２３】
本発明の実施形態は、限定的よりもむしろ例示的なものである。当業者には、上述のデバイス及び方法は、本発明の一般的な範囲から逸脱することなくいくつかの修正を受け入れ可能であることが明らかであろう。このような全ての修正は、特許請求の範囲に収まる限りにおいて本発明の範囲に含まれるものとする。
【符号の説明】
【０１２４】
１０  システム
１２  スケジューラー
１６  第１サーバ
２１  第１仮想サーバ
２２  第２仮想サーバ
【図１】
0005599943.tif 000128
【図２】
0005599943.tif 000129
【図３】
0005599943.tif 000130
【図４】
0005599943.tif 000131
【図５】
0005599943.tif 000132
【図６】
0005599943.tif 000133
【図７】
0005599943.tif 000134