JP2010009449A - 分散情報配置システム - Google Patents

Abstract

【課題】複数のキャッシュに要求をどのように振り分けるかを決定する負荷分散決定処理が特定の装置に集中しないようにする。
【解決手段】同じデータを記憶するキャッシュを備えた複数のノード装置１００１−１〜１００１−３がネットワークを介して接続される。ノード装置１００１−１〜１００１−３は、ユーザ端末１００２−１、１００２−２からデータのアクセス要求を受信したとき、自ノード装置および他のノード装置の負荷情報に基づいて、受信したアクセス要求を自ノード装置で処理するか、他の何れのノード装置で処理するかを判断する。ノード装置１００１−１〜１００１−３は、自ノード装置で処理すると判断したアクセス要求を自ノード装置で受け付けて処理を行い、何れかの他のノード装置で処理すると判断したアクセス要求は該当する他のノード装置へ転送する。
【選択図】図１９

Description

本発明は、通信ネットワーク（以下ＮＷと略す）上に情報のキャッシュを分散させる分散情報配置システムに関する。

近年、インターネットにおける情報コンテンツの配信サービスや、個人ユーザが情報コンテンツを発信して交換するピア・ツウ・ピアのネットワークサービスの利用が進んでいる。ネットワークを利用して情報コンテンツを配信する際、サーバ装置の処理能力などに制限があるため、処理性能を確保する目的で、１以上のキャッシュをネットワーク上に設け、一時的にサーバ装置のコンテンツを保持することが行われている。ＮＷ上にコンテンツのキャッシュを分散させる技術の一例が特許文献１に記載されている。

特許文献１に記載される技術（以下、本発明の関連技術と記す）では、サーバ装置がインターネットを介して複数のキャッシュクラスタに接続され、各キャッシュクラスタがアクセス網を介してクライアント端末に接続される。各キャッシュクラスタは、複数のキャッシュから構成される。サーバ装置は、クライアント端末からの配送要求を受信すると、各キャッシュの負荷などを考慮して何れかのキャッシュクラスタから最適なキャッシュを選択し、データ配送を指示する。データ配送を指示されたキャッシュは、データをクライアント端末へ配送する。またサーバ装置は、コンテンツのアクセス頻度に応じて、各キャッシュクラスタ内のキャッシュ数の増減を集中管理している。

特開２００３−１２２６５８号公報

上述した本発明の関連技術では、複数のキャッシュに要求を振り分けることで負荷分散を図っているが、どのように要求を振り分けるかを決定する処理（負荷分散決定処理）が唯一のサーバ装置で行われるため、サーバ装置が処理のネックとなってシステム全体のスループットが低下するという課題がある。

本発明はこのような事情に鑑みて提案されたものであり、その目的は、複数のキャッシュに要求をどのように振り分けるかを決定する負荷分散決定処理自体を複数のノードに分散させることにより、特定の装置への負荷分散決定処理の集中を防止し、システム全体のスループットの向上を図ることにある。

本発明の第１の分散情報配置システムは、データを記憶するキャッシュと該キャッシュから前記データを読み出して端末装置に送信する手段とを備えた複数のノード装置がネットワークを介して接続された分散情報配置システムであって、前記ノード装置は、自ノード装置および他のノード装置の負荷情報を記憶する記憶手段と、前記端末装置から前記データのアクセス要求を受信したとき、前記記憶手段に記憶された負荷情報に基づいて、受信した前記アクセス要求を自ノード装置で処理するか、他の何れのノード装置で処理するかを判断する負荷分散手段と、自ノード装置で処理すると判断した前記アクセス要求を自ノード装置で受け付けて処理を行うサービス提供手段と、何れかの他のノード装置で処理すると判断した前記アクセス要求を該当する他のノード装置へ転送する通信手段とを備える。

本発明の第１の負荷分散方法は、データを記憶するキャッシュと該キャッシュから前記データを読み出して端末装置に送信する手段とを備えた複数のノード装置がネットワークを介して接続された分散情報配置システムにおける負荷分散方法であって、前記ノード装置のそれぞれが、前記端末装置から前記データのアクセス要求を受信したとき、自ノード装置および他のノード装置の負荷情報に基づいて、受信した前記アクセス要求を自ノード装置で処理するか、他の何れのノード装置で処理するかを判断するステップと、前記ノード装置のそれぞれが、自ノード装置で処理すると判断した前記アクセス要求を自ノード装置で受け付けて処理を行うステップと、前記ノード装置のそれぞれが、何れかの他のノード装置で処理すると判断した前記アクセス要求を該当する他のノード装置へ転送するステップとを含むことを特徴とする。

本発明の第１のノード装置は、データを記憶するキャッシュと該キャッシュから前記データを読み出して端末装置に送信する手段とを備えたノード装置であって、自ノード装置および他のノード装置の負荷情報を記憶する記憶手段と、前記端末装置から前記データのアクセス要求を受信したとき、前記記憶手段に記憶された負荷情報に基づいて、受信した前記アクセス要求を自ノード装置で処理するか、他の何れのノード装置で処理するかを判断する負荷分散手段と、自ノード装置で処理すると判断された前記アクセス要求を自ノード装置で受け付けて処理を行うサービス提供手段と、何れかの他のノード装置で処理すると判断された前記アクセス要求を該当する他のノード装置へ転送する通信手段とを備える。

本発明によれば、複数のノード装置のそれぞれがキャッシュ負荷分散決定機能を有するため、特定のノード装置に負荷分散決定処理が集中するのを防止でき、負荷分散決定処理の遅延によってシステム全体のスループットが低下するのを防止することができる。

また本発明によれば、複数のノード装置のそれぞれがキャッシュ負荷分散決定機能を有するため、負荷分散決定処理に関する単一故障点が無くなり、システムの可用性が向上する効果がある。

次に本発明の実施の形態について図面を参照して詳細に説明する。

図１９を参照すると、本発明の第１の実施の形態に係る分散情報配置システムは、ＩＰネットワーク上に分散する多数のノード装置１００１のうち、複数のノード装置１００１−１〜１００１−９に同じ提供対象データを記憶し、これら複数のノード装置１００１−１〜１００１−９からユーザ端末１００２−１〜１００２−４に対して提供対象データを提供する。提供対象データとしては、或る種のファイルやデータベースなどが該当する。

図１９に示されるシステムでは、同じ提供対象データ（説明の便宜上、データＤとする）に関し、それをキャッシュしているノード装置は全部で９台あり、そのうちノード装置１００１−１はデータＤのオリジナルを記憶し、残り８台のノード装置１００１−２〜１００１−９はそのコピーを記憶する。ノード装置１００１−１〜１００１−９は、データＤに関してそれぞれキャッシュノードとなる。また、データＤのオリジナルを記憶するキャッシュノード１００１−１は、コピーを記憶するキャッシュノード１００１−２〜１００１−９と区別するために、データＤのオリジナルキャッシュノードと呼ぶ。

オリジナルキャッシュノード１００１−１と２台のキャッシュノード１００１−２、１００１−３との合計３台は、データＤに関して１つのクラスタ１００４−１を形成している。同様に、３台のキャッシュノード１００１−４〜１００１−６は、データＤに関して別の１つのクラスタ１００４−２を形成し、３台のキャッシュノード１００１−７〜１００１−９は、データＤに関してさらに別の１つのクラスタ１００４−３を形成している。

各クラスタ１００４−１〜１００４−３では、そのクラスタを構成する１以上のキャッシュノードのうちの１台が、代表ノードとして機能する。オリジナルキャッシュノード１００１−１を含むクラスタ１００４−１では、オリジナルキャッシュノード１００１−１が代表ノードとなる。オリジナルキャッシュノード１００１−１を含まないクラスタ１００４−２、１００４−３では、任意のキャッシュノードが代表ノードとなる。図１９の状態では、ノード１００１−４、１００１−７が代表ノードになっている。

各クラスタ１００４−１〜１００４−３を構成するキャッシュノード間には、クラスタ内オーバーレイネットワーク１００５−１〜１００５−３が形成されている。また、各クラスタ１００４−１〜１００４−３の代表ノード１００１−１、１００１−４、１００１−７間には、クラスタ間オーバーレイネットワーク１００６が形成されている。オーバーレイネットワークは、ノード装置１００１間をつなぐＩＰネットワークのリンクを用いて、その上位層に形成した仮想的なネットワークである。同じクラスタ１００４−１〜１００４−３に属するキャッシュノード間では、クラスタ内オーバーレイネットワーク１００５−１〜１００５−３を通じて、自クラスタの構成メンバとなるノード装置のグローバルＩＰアドレスや負荷情報などが交換される。クラスタ１００４−１〜１００４−３間では、クラスタ間オーバーレイネットワーク１００６を通じて、各クラスタの代表ノードのグローバルＩＰアドレスや各クラスタの構成メンバとなるノード装置の数などが交換される。

また図１９には、ＩＰネットワークに接続された幾つかのＤＮＳ（Ｄｏｍａｉｎ Ｎａｍｅ Ｓｅｒｖｅｒ）サーバ１００３−１〜１００３−６が図示されている。

ノード装置１００１、ユーザ端末１００２およびＤＮＳサーバ１００３間は、既存のＩＰネットワークによる通信が可能である。

次に、上述のように構成された本実施の形態の分散情報配置システムの概略動作を説明する。

データＤをキャッシュしているキャッシュノード１００１−１〜１００１−９は、自ノードの負荷情報を計測し、クラスタ内オーバーレイネットワーク１００５−１〜１００５−３を通じて、同じクラスタに属する他のキャッシュノードと負荷情報を交換している。

また、各キャッシュノード１００１−１〜１００１−９は、自ノードの所属するネットワークのＤＮＳサーバ１００３に対して、自ノードをネットワーク上で一意に識別可能な識別子であるグローバルＩＰアドレスと、ネットワーク内の他のノードがアクセスする場合に用いるデータＤの場所を指し示す記述方式であるＵＲＬ（Ｕｎｉｆｏｒｍ Ｒｅｓｏｕｒｃｅ Ｌｏｃａｔｏｒ）との対応関係を登録する。

図１９では、キャッシュノード１００１−１が属するネットワークのＤＮＳサーバはＤＮＳサーバ１００３−１であるため、キャッシュノード１００１−１はＤＮＳサーバ１００３−１に、自ノードのグローバルＩＰアドレスとデータＤのＵＲＬとの対応関係を登録している。同様に、キャッシュノード１００１−２はＤＮＳサーバ１００３−２に対して、キャッシュノード１００１−３はＤＮＳサーバ１００３−３に対して、キャッシュノード１００１−４はＤＮＳサーバ１００３−４に対して、キャッシュノード１００１−５、１００１−６はＤＮＳサーバ１００３−５に対して、キャッシュノード１００１−７〜１００１−９はＤＮＳサーバ１００３−６に対して、それぞれ自ノードのグローバルＩＰアドレスとデータＤのＵＲＬとの対応関係を登録している。

この結果、ＤＮＳサーバ１００３−５には、データＤのＵＲＬに対してキャッシュサーバ１００１−５とキャッシュサーバ１００１−６の２種類のグローバルＩＰアドレスが登録される。また、ＤＮＳサーバ１００３−６には、データＤのＵＲＬに対してキャッシュサーバ１００１−７〜１００１−９の３種類のグローバルＩＰアドレスが登録される。各ＤＮＳサーバ１００３は、同じＵＲＬに対して複数のグローバルＩＰアドレスが登録された場合、ＵＲＬに対応するＩＰアドレスの問い合わせに対しては、その何れか１つのＩＰアドレスを応答する。このとき、好ましくは、複数のグローバルＩＰアドレスがほぼ均等に使用されるように、ＵＲＬに対応するグローバルＩＰアドレスの問い合わせに対する応答中に含めるグローバルＩＰアドレスを決定する。

今、ユーザ端末１００２−１〜１００２−４の何れかの利用者、例えばユーザ端末１００２−１の利用者が、データＤをアクセスする場面を想定する。利用者がユーザ端末１００２−１で動作するＷｅｂブラウザのＵＲＬ入力テキストボックスにデータＤのＵＲＬを入力すると、Ｗｅｂブラウザは、最寄りのＤＮＳサーバ１００３−３に対して、ＩＰアドレスの検索要求を送信する（図１９の矢印１００７−１１）。ＤＮＳサーバ１００３−３は、データＤのＵＲＬに対応してキャッシュノード１００１−３のグローバルＩＰアドレスが登録されているため、キャッシュノード１００１−３のグローバルＩＰアドレスを応答としてユーザ端末１００２−１に返す（矢印１００７−１２）。ユーザ端末１００２−１のＷｅｂブラウザは、求まったグローバルＩＰアドレスを使って、キャッシュノード１００１−３に対してデータＤの取得を要求するリクエストを例えばＨＴＴＰプロトコルにより送信する（矢印１００７−１３）。

キャッシュノード１００１−３は、自ノードおよび同じクラスタ１００４−１内の他のキャッシュノード１００１−１、１００１−２の負荷情報に基づいて、何れのキャッシュノードで当該リクエストを処理するかを判断する。そして、例えばキャッシュノード１００１−２をリクエスト処理先に決定したとすると、キャッシュノード１００１−３は当該リクエストをクラスタ内オーバーレイネットワーク１００５−１経由でキャッシュノード１００１−２に転送する（矢印１００７−１４）。キャッシュノード１００１−２は、受信したリクエストを受け付け、要求されたデータを自ノードのキャッシュから読み出し、ユーザ端末１００２−１へレスポンスを送信する（矢印１００７−１５）。

次に、ユーザ端末１００２−２の利用者が、データＤをアクセスする場面を想定する。利用者がユーザ端末１００２−２で動作するＷｅｂブラウザのＵＲＬ入力テキストボックスにデータＤのＵＲＬを入力すると、Ｗｅｂブラウザは、最寄りのＤＮＳサーバ１００３−１に対して、ＩＰアドレスの検索要求を送信する（図１９の矢印１００７−２１）。ＤＮＳサーバ１００３−１は、データＤのＵＲＬに対応してキャッシュノード１００１−１のグローバルＩＰアドレスが登録されているため、キャッシュノード１００１−１のグローバルＩＰアドレスを応答としてユーザ端末１００２−２に返す（矢印１００７−２２）。ユーザ端末１００２−２のＷｅｂブラウザは、求まったグローバルＩＰアドレスを使って、キャッシュノード１００１−１に対してデータＤの取得を要求するリクエストを例えばＨＴＴＰプロトコルにより送信する（矢印１００７−２３）。

キャッシュノード１００１−１は、自ノードおよび同じクラスタ１００４−１内の他のキャッシュノード１００１−２、１００１−３の負荷情報に基づいて、何れのキャッシュノードで当該リクエストを処理するかを判断する。そして、例えば自ノード１００１−１をリクエスト処理先に決定したとすると、キャッシュノード１００１−１は、受信したリクエストを受け付け、要求されたデータを自ノードのキャッシュから読み出し、ユーザ端末１００２−２へレスポンスを送信する（矢印１００７−２４）。

次に、ユーザ端末１００２−３の利用者が、データＤをアクセスする場面を想定する。利用者がユーザ端末１００２−３で動作するＷｅｂブラウザのＵＲＬ入力テキストボックスにデータＤのＵＲＬを入力すると、Ｗｅｂブラウザは、最寄りのＤＮＳサーバ１００３−６に対して、ＩＰアドレスの検索要求を送信する（図１９の矢印１００−３１）。ＤＮＳサーバ１００３−６は、データＤのＵＲＬに対応して複数のキャッシュノード１００１−７〜１００１−９のグローバルＩＰアドレスが登録されているため、その何れか、例えばキャッシュノード１００１−９のグローバルＩＰアドレスを応答としてユーザ端末１００２−３に返す（矢印１００７−３２）。ユーザ端末１００２−３のＷｅｂブラウザは、求まったグローバルＩＰアドレスを使って、キャッシュノード１００１−９に対してデータＤの取得を要求するリクエストを例えばＨＴＴＰプロトコルにより送信する（矢印１００７−３３）。

キャッシュノード１００１−９は、自ノードおよび同じクラスタ１００４−３内の他のキャッシュノード１００１−７、１００１−８の負荷情報に基づいて、何れのキャッシュノードで当該リクエストを処理するかを判断する。そして、例えばキャッシュノード１００１−８をリクエスト処理先に決定したとすると、キャッシュノード１００１−９は当該リクエストをクラスタ内オーバーレイネットワーク１００５−３経由でキャッシュノード１００１−８に転送する（矢印１００７−３４）。キャッシュノード１００１−８は、受信したリクエストを受け付け、要求されたデータを自ノードのキャッシュから読み出し、ユーザ端末１００２−３へレスポンスを送信する（矢印１００７−３５）。

次に、ユーザ端末１００２−４の利用者が、データＤをアクセスする場面を想定する。利用者がユーザ端末１００２−４で動作するＷｅｂブラウザのＵＲＬ入力テキストボックスにデータＤのＵＲＬを入力すると、Ｗｅｂブラウザは、最寄りのＤＮＳサーバ１００３−６に対して、ＩＰアドレスの検索要求を送信する（図１９の矢印１００７−４１）。ＤＮＳサーバ１００３−６は、データＤのＵＲＬに対応して複数のキャッシュノード１００１−７〜１００１−９のグローバルＩＰアドレスが登録されているため、その何れか、例えば最も最近選択していないキャッシュノード１００１−７のグローバルＩＰアドレスを選択し、応答としてユーザ端末１００２−４に返す（矢印１００７−４２）。ユーザ端末１００２−４のＷｅｂブラウザは、求まったグローバルＩＰアドレスを使って、キャッシュノード１００１−７に対してデータＤの取得を要求するリクエストを例えばＨＴＴＰプロトコルにより送信する（矢印１００７−４３）。

キャッシュノード１００１−７は、自ノードおよび同じクラスタ１００４−３内の他のキャッシュノード１００１−８、１００１−９の負荷情報に基づいて、何れのキャッシュノードで当該リクエストを処理するかを判断する。そして、例えば自キャッシュノード１００１−７をリクエスト処理先に決定したとすると、キャッシュノード１００１−７は当該リクエストを受け付け、要求されたデータを自ノードのキャッシュから読み出し、ユーザ端末１００２−４へレスポンスを送信する（矢印１００７−４４）。

以上のように本実施の形態の分散情報配置システムでは、データＤの各キャッシュノード１００１−１〜１００１−９は、ユーザ端末からデータＤのリクエストを受信した場合、自ノードの所属するクラスタ１００４−１〜１００４−３内の何れのキャッシュノードで当該リクエストを処理すべきかを各ノードの負荷情報に基づいて決定する機能を有するため、同一の提供データに対するユーザ端末からのアクセスに係る負荷を各クラスタ１００４−１〜１００４−３毎にそれに含まれる１以上のキャッシュノード間で分散することができる。

また、リクエストを処理するノードを決定する機能が各キャッシュノードに装備されているため、リクエストを処理するノードを決定する処理自体の負荷分散も可能である。

さらに、各キャッシュノード１００１−１〜１００１−９は、自ノードの所属するネットワークのＤＮＳサーバ１００３に対して、自ノードのグローバルＩＰアドレスとデータＤのＵＲＬとの対応関係を登録するため、互いに異なるネットワークに属する複数のユーザ端末がＤＮＳサーバ１００３をアクセスしてデータＤのＵＲＬに対応するキャッシュノードのグローバルＩＰアドレスを取得する場合に、それぞれ異なるキャッシュノードのグローバルＩＰアドレスを取得することになる。この結果、複数のユーザ端末がデータＤのリクエストを出すキャッシュノードを分散させることができる。

また、同じデータＤのＵＲＬに対応して複数のキャッシュノードのグローバルＩＰアドレスが登録されているＤＮＳサーバ１００３において、複数のグローバルＩＰアドレスがほぼ均等に使用されるように、ＵＲＬに対応するグローバルＩＰアドレスの問い合わせに対する応答中に含めるグローバルＩＰアドレスを決定すれば、同じネットワークに属する複数のユーザ端末がデータＤのリクエストを出すキャッシュノードを分散させることができる。

図１９に示されるシステムでは、各クラスタ１００４−１〜１００４−３に存在するキャッシュノードの数はそれぞれ３台であった。しかし、このクラスタ内におけるキャッシュノードの数は固定ではなく、データＤに対する需要に応じて増減される。キャッシュノード数の増減は、各クラスタ毎にそのクラスタの代表ノードの制御の下に実施される。

図１９に示されるシステムでは、データＤに関するクラスタの数は３つであった。しかし、データＤに関するクラスタの数は固定ではなく、データＤに対する需要に応じて増減される。具体的には、初期の状態では、オリジナルキャッシュノード１００１−１だけを含むクラスタ１００４−１が１つ存在するだけである。データＤに対する需要が増加すると、代表ノードであるオリジナルキャッシュノード１００１−１は、クラスタ１００４−１内に新たなキャッシュノード１００１−２、１００１−３を生成する。そして、更に需要が増加し、１クラスタ内におけるキャッシュノード数の最大値を超えるなどの所定の条件が成立すると、クラスタ１００４−１の代表ノードは、データＤを未だキャッシュしていない他のノード、例えばノード１００１−４に対してデータＤのコピーを添えて新規クラスタの生成指示を送信する。ノード１００１−４は、データＤのコピーを自ノードのキャッシュに記憶し、自ノードを代表ノードとする新たなクラスタ１００４−２を生成する。以降、再び新クラスタ生成条件が成立すると、クラスタ１００４−１あるいはクラスタ１００４−２の代表ノードの制御の下に、新クラスタ１００４−３が生成される。

他方、データＤに対する需要が減退すると、それにあわせて各クラスタ１００４−１〜１００４−３のキャッシュノード数が減少していく。そして、例えばクラスタ１００４−３におけるキャッシュノード数が０になると、クラスタ１００４−３が消滅し、クラスタ１００４−１とクラスタ１００４−２の２つになる。同様にクラスタ１００４−２におけるキャッシュノード数が０になると、クラスタ１００４−２が消滅し、クラスタ１００４−１だけが残る。

このように本実施の形態の分散情報配置システムでは、データＤに対する需要に応じて、キャッシュノード数だけでなく、クラスタ数自体も増減する。

次に本発明の実施例について図面を参照して詳細に説明する。

本実施例は、ＮＷ上に存在する情報の分散的キャッシュ配置問題について、情報への需要、すなわちアクセス数に応じて、配置の量および場所を自律分散的に決定する、需要依存で繁栄と衰退とを繰り返す分散情報配置システム（以下、単位分散情報配置システムと記す）に関する。

例えば、粘菌は餌の多寡によって、餌の多い場所では、単細胞生物として生活し、一方で餌の少ない場所では、集合して多細胞生物となり、餌の多い場所を求めて移動する。また、卵生メダカのノソブランキウスおよびシノレビアスは、一年の間に雨季と乾季が交代するサバンナ（草原）に住み、雨が降って水溜りが出来ると、土の中にあった卵が孵り、瞬く間に成長し、土の中に卵を生み、やがて乾季が来て池が干上がると親は死に、土の中に産みつけられた卵は次の雨季が来るのを、わずかな湿り気を残すのみの乾いた池の底の土の中で、辛抱強く待つ。このように生物の中には自身の形態を変えて環境に適応する種類がいる。また、生物は密度依存で個体の量を制御することによって、種の繁栄を維持することが知られており、このダイナミクスは一般にロジスティック方程式で記述される。さらに、生物にはヘルパー遺伝子が存在し、種全体から見れば利己的であるが個体レベルでは利他的な社会的行動を取ることによって、種の繁栄を維持することも知られている。

以上に述べたような特性を持つことによって生物は、環境変動に対して堅牢な生態系を作り出している。本実施例は、以上の説明における「生物種」をＮＷにおける「情報」と読み替えることで実現されるものであり、それら生物種の適応機能を通信ＮＷ上で実現するものである。そのため、従来の分散キャッシュ配置に関する技術とは、その目的を異にする。すなわち、本実施例の目的は、通信ＮＷ上の情報へのアクセス数に適応して、情報のキャッシュ配置の量と質を利他的かつ協調的な仕組みによって自律分散的に決定することで、効率的な情報の分散キャッシュ配置を実現するとともに、一度廃れてアクセスの無くなった情報の効率的な再生を実現することにある。

［本実施例の概要］
基本的な仕組みとして、「情報の必要度」を数値で定義し、これを情報のプロパティとして情報に付与する。情報のキャッシュ元にアクセスがあった場合、１アクセス毎に「情報の必要度」は増加し、また一定時間毎に減少する。この「情報の必要度」の一定時間毎の減少により、情報へのアクセス頻度、換言すれば「情報の鮮度」が決定される。以下では、情報へのアクセス数が増加する場合と、減少する場合について手段と作用を説明する。なお、以下では情報のソース元のサーバおよび情報をキャッシュするサーバを「キャッシュノード」と表記する。

（１）情報へのアクセス数が増加する場合
ステップ１：
情報とある値の「情報の必要度」を最初の情報元のキャッシュノードに配置する。以下ではこのキャッシュノードを「オリジナルキャッシュノード」と呼ぶ。同時に自分を代表キャッシュノードとする下位クラスタを生成し、当該キャッシュノードのIPアドレスと「『情報の必要度』の数値」とを下位クラスタ内用の下位クラスタマップに登録する。下位クラスタ内用の下位クラスタマップは各下位クラスタ内のキャッシュノードが分散的に所有し、キャッシュノードは下位クラスタ内用の下位クラスタマップに登録された複数のキャッシュノードとオーバーレイで下位クラスタＮＷ内通信を行う。

さらにオリジナルノードは、自身の所属するＮＷのＤＮＳサーバに自身のグローバルＩＰアドレスと、ＮＷ内の他のノードがアクセスする場合に用いるキャッシュ情報の場所を指し示す記述方式であるＵＲＬを登録しておく。

ここで、Ｉｎｔｅｒｎｅｔ上の一般的なキャッシュ情報へのアクセス手段について説明する。Ｉｎｔｅｒｎｅｔの通常の通信では、情報へアクセスしたい一般的なノードＢは、次の（ａ）または（ｂ）のいずれかの方法により情報をキャッシュしているサーバにアクセスを行う。
（ａ）ノードＢがキャッシュノードのＵＲＬは知っているが、ＩＰアドレスは知らない場合、ＵＲＬを指定して、そのＩＰアドレスをＤＮＳサーバに問い合わせる。ＤＮＳサーバは、自身がそのＵＲＬとＩＰアドレスの対応を知っていれば、そのＩＰアドレスをＩｎｔｅｒｎｅｔ上の通常の通信を用いて、ノードＢに伝える。もし、ＤＮＳサーバがそのＵＲＬとＩＰアドレスの対応を知らなければ、ＤＮＳサーバは他のＤＮＳサーバに問い合わせる、ということを繰り返し、最終的にそのＵＲＬとＩＰアドレスの対応を知っているＤＮＳサーバがノードＢにＩＰアドレスを伝える。
（ｂ）ノードＢがＩＰアドレスを知っている場合は、直接キャッシュノードにアクセスできる。

以下では（ａ）の場合を前提に説明を続ける。

ステップ２：
情報へのアクセスがあるたびにキャッシュノードの「『情報の必要度』の数値」が増加する。

ステップ３：
アクセスが増えて「『情報の必要度』の数値」がある閾値１を超えると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する。一定時間の「『情報の必要度』の数値」の平均値がある閾値１を超えると代表キャッシュノードはある物理的あるいは論理的ＮＷ距離にある、次数の大きなキャッシュノードに情報をキャッシュしてもらえないかランダムに通常のＩｎｔｅｒｎｅｔにおける通信手法によって打診し、承諾をもらったキャッシュノードにキャッシュさせてもらう。ここで、複数の承諾をもらった場合には、それらの全て、あるいはそれらのうち次数の大きなキャッシュノードに対して、キャッシュさせてもらう。この新規追加されたキャッシュノードは下位クラスタ内の代表キャッシュノード宛に、新規追加されたキャッシュノードが下位クラスタに属することを認識してもらうための「ｅｎｔｒｙメッセージ」を通常のＩｎｔｅｒｎｅｔにおける通信手法によって送る。

新規追加キャッシュノードへの依頼を行った代表キャッシュノードは、新規追加されたキャッシュノード宛に、「ｅｎｔｒｙメッセージ」を受信したことを示すメッセージを下位クラスタ内通信によって送り、同時に下位クラスタマップに必要な情報を要求する。要求を受けた新規追加キャッシュノードは、自身のキャッシュノードに関する要求情報を下位クラスタ内通信によってキャッシュノードへの依頼を行った代表キャッシュノードへ送る。

追加キャッシュノード依頼を行った代表キャッシュノードは、新規追加キャッシュノードから受け取った要求情報をもとに下位クラスタマップを更新し、更新された下位クラスタマップを、下位クラスタ内通信によって代表キャッシュノードの所属する下位クラスタ内の他のキャッシュノードに送る。各キャッシュノードは各自の持つ下位クラスタ用の下位クラスタマップを更新して、登録完了のメッセージを、キャッシュノード依頼を行ったキャッシュノードに、下位クラスタ内通信によって送る。なお、新規キャッシュノードの下位クラスタへの追加は、アクセス数の変動を考慮して、一定時間待ってから行う。この時点でのユーザからのアクセス先は、代表キャッシュノードとする。

ステップ４：
下位クラスタ内に存在する、代表キャッシュノードを含む複数のキャッシュノードらは、下位クラスタ内通信を一定時間間隔毎または不定時間間隔で行うことによって、互いの「生存」と「『情報の必要度』の数値」などの情報を交換し合う。これによって下位クラスタ内のキャッシュノードの下位クラスタ内用の下位クラスタマップの更新と同期とを行う。ここで、下位クラスタ内通信は、新規にキャッシュノードが追加されたり、キャッシュノードやキャッシュノード間のリンクの障害などのイベントが発生した場合には、そのイベントをトリガーとして行われる。

ステップ５：
下位クラスタ内に、代表キャッシュノードを除く少なくとも１つの他のキャッシュノードが追加されると、それらは自律的に負荷分散を行う。すなわち、下位クラスタ内通信によって同一下位クラスタ内の「『情報の必要度』の数値」やそれを用いた計算結果によって値の少ないキャッシュノードから順にアクセスを転送する。

ステップ６：
各クラスタには、その代表キャッシュノードまたはクラスタの中心から一定の物理距離または論理的距離を半径とする円で特定されるクラスタ領域と、このクラスタ領域に設置することのできるキャッシュノードの最大数とが予め定められる。クラスタ領域に設置可能なキャッシュノードの最大数は、換言すれば、当該クラスタのキャッシュノード密度である。キャッシュノード密度は、「キャッシュノード数／ＮＷ半径」で表現しても良いし、「キャッシュノード数／ＮＷ半径内に存在するノード数」で表現しても良い。

ステップ７：
下位クラスタの代表キャッシュノードが「ＮＷ半径を超える遠くからのアクセスが多くなる」あるいは「上記ステップ６で計算した自下位クラスタに置くことの出来るキャッシュノードの最大数に近づく」ことを検知すると、そのＮＷ半径を超える場所に存在する、次数の大きなキャッシュノードに該情報をキャッシュしてもらえないかランダムに通常のＩｎｔｅｒｎｅｔにおける通信手法によって打診し、通常のＩｎｔｅｒｎｅｔにおける通信手法によって承諾をもらったキャッシュノードにキャッシュさせてもらう。ここで、複数の承諾をもらった場合には、それらの全て、あるいはそれらのうち次数の大きなキャッシュノードに対して、キャッシュさせてもらう。また、ＮＷ半径を超える場所は、自クラスタの周囲３６０度方向に存在するが、ＮＷ半径を超える場所があるＮＷドメインに偏っている場合には、このＮＷドメイン近傍の次数の大きなキャッシュノードを優先的に候補として選択する。なお、この新規キャッシュノードの追加は、アクセス数の変動を考慮して、一定時間待ってから行う。

キャッシュノードの依頼を行った代表キャッシュノードは、自キャッシュノードを含む代表キャッシュノードのみで構成される上位クラスタを作成し、上位クラスタ用の上位クラスタマップを作成する。

新規追加されたキャッシュノードは自分を代表キャッシュノードとする下位クラスタを新たに形成し、下位クラスタ内用下位クラスタマップを作成する。ここで、この代表キャッシュノード同士による上位クラスタ内オーバーレイＮＷは、下位クラスタ内ＮＷの上にオーバーレイＮＷの形態で構築される。

また、新規追加されたキャッシュノードはキャッシュノード依頼を受けた代表キャッシュノードに対して、代表キャッシュノードのみで構成される上位クラスタへ新規追加されたキャッシュノードが上位クラスタに属することを認識してもらうための「ｅｎｔｒｙメッセージ」を通常のＩｎｔｅｒｎｅｔにおける通信手法によって送る。

キャッシュノードへの依頼を行った代表キャッシュノードは、新規追加された代表キャッシュノード宛に、「ｅｎｔｒｙメッセージ」を受信したことを示すメッセージを上位クラスタ内通信によって送り、同時に上位クラスタマップに必要な情報を要求する。要求を受けた新規追加キャッシュノードは、自身のキャッシュノードに関する要求情報を上位クラスタ内通信によってキャッシュノードへの依頼を行った代表キャッシュノードへ送る。

キャッシュノード依頼を行った代表キャッシュノードは、新規代表キャッシュノードから受け取った要求情報をもとに上位クラスタマップを更新し、代表キャッシュノードのみで構成される上位クラスタ内の他の代表キャッシュノードに、上位クラスタ内通信によって送る。各キャッシュノードは各自の持つ上位クラスタ用の上位クラスタマップを更新して、登録完了のメッセージを、キャッシュノード依頼を行った代表キャッシュノードに、上位クラスタ内通信によって送る。

下位クラスタ同士は原則的に代表キャッシュノードであるキャッシュノード同士が、各下位クラスタ内のキャッシュノード数などのマクロな情報を、一定時間間隔毎または不定時間間隔でオーバーレイ通信を行うことによって、互いの生存と状況を確認し合う。

（２）情報へのアクセス数が減少する場合
ステップ１：
あるキャッシュノードへのアクセスが減って、「『情報の必要度』の数値」がある閾値を下回ると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する。一定時間の「『情報の必要度』の数値」の平均値がある閾値を下回ると、自キャッシュノードの所属する下位クラスタ内に他のキャッシュノードがいる限り、それら下位クラスタ内の他のキャッシュノード全てに、下位クラスタ内通信によって脱退メッセージを送る。脱退メッセージを受け取った下位クラスタ内の他のキャッシュノードは自キャッシュノードの下位クラスタ内用下位クラスタマップから、脱退キャッシュノードのＩＰアドレス以外の情報を消去し、「脱退メッセージが到着した」という確認メッセージを脱退キャッシュノードに対して、下位クラスタ内通信によって送信する。脱退キャッシュノードは、下位クラスタ内の全ての他のキャッシュノードから、下位クラスタ内通信によって確認メッセージを受け取った後で、自キャッシュノードの保持しているキャッシュデータを削除し、情報のＵＲＬと自身のＩＰアドレスとを登録したＤＮＳサーバに削除要求を出して下位クラスタから抜ける。

ここで、仮に代表キャッシュノードが抜ける場合には、以下のようになる。代表キャッシュノードへのアクセスが減って、「『情報の必要度』の数値」がある閾値を下回ると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する。一定時間の「『情報の必要度』の数値」の平均値がある閾値を下回ると、自キャッシュノードの所属する下位クラスタ内の他のキャッシュノードのうち、最も「『情報の必要度』の数値」の小さいキャッシュノードに他の下位クラスタとの通信を行う代表キャッシュノードを譲り、自キャッシュノードの所属する下位クラスタ内の他のキャッシュノード全てに対しては下位クラスタ内通信によって、また他の下位クラスタの代表キャッシュノードへは上位クラスタ内通信によって、「別のキャッシュノードが代表キャッシュノードを引き継ぎ、自分が抜けること」を知らせる。このメッセージを受け取った下位クラスタ内の他の全てのキャッシュノードは各々の持つ下位クラスタ内用下位クラスタマップから代表キャッシュノードの情報を削除し、「代表キャッシュノードを受け継いだキャッシュノード」を代表キャッシュノードとして下位クラスタ内用下位クラスタマップに設定する。さらに、「元の代表キャッシュノード」と「代表キャッシュノードを受け継いだキャッシュノード」に対して、「新しい代表キャッシュノードを下位クラスタ内用下位クラスタマップに登録したこと」を下位クラスタ内通信によって確認メッセージとして伝える。

同様に他の下位クラスタの代表キャッシュノードは、上位クラスタＮＷ用の上位クラスタマップから代表キャッシュノードの情報を削除し、新しい代表キャッシュノードを下位クラスタの代表キャッシュノードとして上位クラスタＮＷ用の上位クラスタマップに設定する。さらに他の下位クラスタの代表キャッシュノードは、確認メッセージを「代表キャッシュノードを受け継いだキャッシュノード」と「元の代表キャッシュノード」宛に上位クラスタ内通信によって送信する。

自キャッシュノードの所属する下位クラスタ内の全てのキャッシュノード、および他の下位クラスタの全ての代表キャッシュノードからの確認メッセージを下位クラスタ内通信、上位クラスタ内通信によってそれぞれ受け取った後で、「元の代表キャッシュノード」は、自キャッシュノードの保持するキャッシュデータを削除し、情報のＵＲＬと自身のＩＰアドレスとを登録したＤＮＳサーバに削除要求を出して下位クラスタから抜ける。

ステップ２：
ある下位クラスタに最終的に残ったキャッシュノードは必然的に下位クラスタの代表キャッシュノードであるが、代表キャッシュノードでも「『情報の必要度』の数値」がある閾値を下回ると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する。一定時間の「『情報の必要度』の数値」の平均値がある閾値を下回ると、代表キャッシュノードは他の下位クラスタの全ての代表キャッシュノードに対して、脱退メッセージを上位クラスタ内通信によって送る。同時に、脱退代表キャッシュノードは自キャッシュノードの上位クラスタＮＷ用上位クラスタマップを見て、他の下位クラスタの全ての代表キャッシュノードのうち、キャッシュノード当たりの「『情報の必要度』の数値」が最も少なく、かつキャッシュノード密度の最大値の大きい代表キャッシュノードに、自キャッシュノードの所属する下位クラスタ内用の下位クラスタマップを上位クラスタ内通信によって送信する。

他の下位クラスタの全ての代表キャッシュノードは、脱退メッセージを送信した代表キャッシュノードに対して「代表キャッシュノードが抜けること」を確認するメッセージを「代表キャッシュノード」宛に上位クラスタ内通信によって送信した後で、定期メッセージの宛先から代表キャッシュノードに関するＩＰアドレス以外の情報を上位クラスタＮＷ用上位クラスタマップから削除する。ここで脱退代表キャッシュノードから下位クラスタ内用の下位クラスタマップを受け取った代表キャッシュノードは、「下位クラスタマップを受け取ったこと」を確認メッセージとして、脱退代表キャッシュノードに上位クラスタ内通信によって送信する。

脱退代表キャッシュノードは、他の下位クラスタの全ての代表キャッシュノードから「代表キャッシュノードが抜けること」を確認するメッセージを上位クラスタ内通信によって受け取り、かつ脱退代表キャッシュノードから下位クラスタ内用の下位クラスタマップを受け取った代表キャッシュノードから「下位クラスタマップを受け取ったこと」を確認するメッセージを上位クラスタ内通信によって受け取った後で、自キャッシュノードの保持するキャッシュデータを削除し、情報のＵＲＬと自身のＩＰアドレスとを登録したＤＮＳサーバに削除要求を出して上位クラスタＮＷから抜ける。

ステップ３：
オリジナルキャッシュノードを含む下位クラスタ以外で最終的に残った下位クラスタにおいて、最終的に残ったキャッシュノード（以下、終末キャッシュノードと呼ぶ）でも「『情報の必要度』の数値」がある閾値を下回ると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する。一定時間の「『情報の必要度』の数値」の平均値がある閾値を下回ると、オリジナルキャッシュノードに対して「自分が最終データのキャッシュノードであること」、終末キャッシュノードが保持している「キャッシュデータ」および「過去に脱退した他の下位クラスタの下位クラスタ内用の下位クラスタマップ」を、１）自キャッシュノードにそのまま置いても良い、２）何か他の形態（例えばリンク先としてなど）で置いても良い、あるいは、３）削除して欲しい、という「希望情報」と共に、上位クラスタ内通信によって伝える。

ステップ４：
オリジナルキャッシュノードは、終末キャッシュノードからの「希望情報」を元に、情報を、１）そのまま置いてもらうか、２）何か他の形態（例えばリンク先としてなど）で置かせてもらうか、あるいは、３）削除してもらうかを検討し、その結果を週末キャッシュノードに対して上位クラスタ内通信によって伝える。ここで、終末キャッシュノードに情報をキャッシュし続けてもらう理由は、そのデータが再度必要になる場合、最後までアクセスがあったキャッシュノードの周辺からの場合が多いと推定されるためである。

ステップ５：
情報を削除してもらう場合には、最後に残った下位クラスタにいた他のキャッシュノードに対して、情報を、１）そのまま置いて欲しい、２）何か他の形態（例えばリンク先としてなど）で置かせて欲しい、ことを通常のＩｎｔｅｒｎｅｔの通信手段によって伝える。

ステップ６：
終末キャッシュノードは、オリジナルキャッシュノードからの回答に従って、情報の管理形態を決定する。すなわち、情報を、１）そのまま置くか、２）何か他の形態（例えばリンク先としてなど）で置くか、あるいは、３）削除するか、のいずれかを行う。

ステップ７：
オリジナルキャッシュノードから、情報を、１）そのまま置いて欲しい、２）何か他の形態（例えばリンク先としてなど）で置かせて欲しいというメッセージを通常のＩｎｔｅｒｎｅｔの通信手段によって受け取った、最後に残った下位クラスタにいた他のキャッシュノードは、それぞれオリジナルキャッシュノードに対して、情報を、１）自キャッシュノードにそのまま置いても良い、２）何か他の形態（例えばリンク先としてなど）で置いても良い、あるいは、３）置きたくない、という「希望情報」を通常のＩｎｔｅｒｎｅｔの通信手段によって伝える。

ステップ８：
「希望情報」を通常のＩｎｔｅｒｎｅｔの通信手段によって受け取ったオリジナルキャッシュノードは、その中に、情報を、１）自キャッシュノードにそのまま置いても良い、２）何か他の形態（例えばリンク先としてなど）で置いても良いという回答があれば、１）、２）の優先順位で、そのキャッシュノードと上位クラスタを構成し、キャッシュする情報を上位クラスタ内通信によって送信する。

ステップ９：
「希望情報」を受け取ったオリジナルキャッシュノードは、その中に３）置きたくないという回答しか無ければ、最後から２番目に削除された下位クラスタにいた他のキャッシュノードに対して、情報を、１）そのまま置いて欲しい、２）何か他の形態（例えばリンク先としてなど）で置かせて欲しい、ことを通常のＩｎｔｅｒｎｅｔの通信手段によって伝える。

ステップ１０：
以下、ステップ７から９を繰り返す。

ステップ１１：
最終的にオリジナルキャッシュノード以外にキャッシュしてくれるキャッシュノードが無ければ、オリジナルキャッシュノードは、情報を自キャッシュノードに保存したままにする。

（３）アクセスが再度増加した場合に関する動作の説明
上記「情報へのアクセス数が減少する場合」のステップ７〜１１において、最終的にキャッシュされるべき情報をどのキャッシュノードが保持しているかによって、最初のステップのみが異なる。

（３−１）最終的にオリジナルキャッシュノードのみがキャッシュされるべき情報を保持している場合
この場合は、「（１）情報へのアクセス数が増加する場合」のステップ３が最初のステップとなる。

（３−２）最終的にオリジナルキャッシュノードと終末キャッシュノードがキャッシュされるべき情報を保持している場合
この場合、オリジナルキャッシュノードと終末キャッシュノードのうち、アクセスを受けたキャッシュノードにおいて、「（１）情報へのアクセス数が増加する場合」のステップ３が最初のステップとなる。終末キャッシュノードにおいてアクセスが増加し、「（１）情報へのアクセス数が増加する場合」で示した、閾値１を超えてキャッシュノードの追加が必要になった場合、「（１）情報へのアクセス数が増加する場合」のステップ３で示した手順に従って、一定時間待ってから、終末キャッシュノードは自分の保持している下位クラスタ内の下位クラスタマップの中に残っている、下位クラスタ内で過去にキャッシュノードであったキャッシュノードに情報をキャッシュしてもらえないかを通常のＩｎｔｅｒｎｅｔの通信手段によって打診する。もし、いずれからも承諾を得られなかった場合には、ある一定のホップ数にあるキャッシュノードのうち、次数の大きなキャッシュノードにランダムに情報をキャッシュしてもらえないかを通常のＩｎｔｅｒｎｅｔの通信手段によって打診する。一定のホップ数内のキャッシュノードから承諾が得られなければ、終末キャッシュノードは探索ホップ数を＋１して、承諾を得られるキャッシュノードを探索する。

下位クラスタ内の過去のキャッシュノード、あるいはホップ数による探索によって、いずれかのキャッシュノードから承諾を受けると、後は「（１）情報へのアクセス数が増加する場合」のステップ３以降において説明した手順に従って、キャッシュノードを増加させていく。

以上のようにして、通信ＮＷ上の情報へのアクセス数に適応して、情報のキャッシュ配置の量と質を利他的かつ協調的な仕組みによって自律分散的に決定することで、効率的な情報の分散キャッシュ配置を実現するとともに、一度廃れてアクセスの無くなった情報の効率的な再生を実現する。

［構成の説明］
次に、本実施例の構成を詳細に説明する。

図１を参照すると、本実施例の分散情報配置システムにおける「『情報の必要度』の数値」の変化の様子の１例が示されている。アクセスがあるたびに、「『情報の必要度』の数値」は一定量だけ増加する。「『情報の必要度』の数値」は一定時間が経過する毎に一定量だけ減少する。

図２を参照すると、本実施例の分散情報配置システムにおける新規キャッシュノード追加の様子の１例が示されている。図３を参照すると、本実施例の分散情報配置システムにおける新規キャッシュノード追加のフローチャートの１例が示されている。図４を参照すると、本実施例の分散情報配置システムにおける、各キャッシュノードが保持する下位クラスタ内用の下位クラスタマップの１例が示されている。

下位クラスタ内用の下位クラスタマップの内容は、図４に示したように、キャッシュノードの、ＤＮＳ登録名、グローバルＩＰアドレス、『情報の必要度』の数値、『情報の必要度』の数値の１次微分値、および『情報の必要度』の数値の２次微分値である。『情報の必要度』の数値の１次微分値は、直近の単位時間当たりの『情報の必要度』の数値の増減量である。『情報の必要度』の数値の２次微分値は、直近の単位時間当たりの『情報の必要度』の数値の増減割合である。

ここで、下位クラスタＮＷ２内のオーバーレイ通信のために、下位クラスタＮＷ２内のキャッシュノードに、下位クラスタＮＷ２内部でのみ通用するローカルなＩＰアドレスを各々割り当て、このローカルなＩＰアドレスを用いた下位クラスタＮＷ２内のオーバーレイ通信を行っても良い。その場合、下位クラスタ内用の下位クラスタマップの内容は、図４に示した以外に、下位クラスタ２内でローカルに付加したローカルなＩＰアドレスを含んでいても良い。

なお、下位クラスタ内用の下位クラスタマップの内容は、図４の内容から『情報の必要度』の数値の２次微分値を削除したものでも良い。また、下位クラスタ内用の下位クラスタマップの内容は、図４に示した以外に何らかの『情報の必要度』の数値の経時変化の様子を表す変数を含んでいても良い。

オリジナルノードは、自身の所属するＮＷのＤＮＳサーバに自身をＮＷ上で一意に識別可能な識別子であるグローバルＩＰアドレスと、ＮＷ内の他のノードがアクセスする場合に用いるキャッシュ情報の場所を指し示す記述方式であるＵＲＬを登録しておく（図２ａまたは図２ｂのオリジナルノード１から出ている１点鎖線）。

情報とある値（初期値）の「情報の必要度」をオリジナルキャッシュノード１に配置する。同時に自分を代表キャッシュノードとする下位クラスタ２を生成し、オリジナルキャッシュノード１のＩＰアドレスと「『情報の必要度』の数値」とを下位クラスタ内用の下位クラスタマップ４−２に登録する。下位クラスタ内用の下位クラスタマップ４−２は各下位クラスタ内のキャッシュノードが分散的に所有し、キャッシュノードは下位クラスタ内用の下位クラスタマップに登録された複数のキャッシュノードとオーバーレイで下位クラスタ内通信を行う。図１に示したように情報へのアクセスがあるたびに「『情報の必要度』の数値」が増加する。

図２では、理解のし易さを目的に、アクセスをアリ３で表し、またアクセスによる「『情報の必要度』の数値」の増加分をアリ３が運んでいる荷物Ａで表している。アクセスが増えて「『情報の必要度』の数値」がある閾値Θ１を超えると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する。一定時間の「『情報の必要度』の数値」の平均値がある閾値Θ１を超えると代表キャッシュノードはある物理的あるいは論理的ＮＷ距離にある、次数の大きなキャッシュノードに情報をキャッシュしてもらえないかランダムに打診し、承諾をもらったキャッシュノード６にキャッシュさせてもらう。ここで、複数の承諾をもらった場合には、それらの全て、あるいはそれらのうち次数の大きなキャッシュノードに、キャッシュさせてもらう。「ある物理的あるいは論理的ＮＷ距離」としては、ホップ数を用いる。ここで、「ある物理的あるいは論理的ＮＷ距離」は、ある一定のＲＴＴ値を用いても良い。

新規追加されたキャッシュノード６は、情報のＵＲＬと自身のＩＰアドレスを自身の属するＮＷドメインのＤＮＳサーバに登録しておく。これにより、（ａ）自身の属するＮＷドメインがオリジナルキャッシュノード（または代表キャッシュノード）と異なっていれば、オリジナルキャッシュノード（または代表キャッシュノード）と異なるＤＮＳサーバに情報のＵＲＬと自身のＩＰアドレスが登録される（図２ａのキャッシュサーバ６から出ている１点鎖線）。他方、（ｂ）自身の属するＮＷドメインがオリジナルキャッシュノード（または代表キャッシュノード）と同じであれば、同じＤＮＳサーバに情報のＵＲＬと自身のＩＰアドレスが登録される（図２ｂのキャッシュサーバ６から出ている１点鎖線）。

新規追加されたキャッシュノード６は、下位クラスタ２内の代表キャッシュノード１に、キャッシュノード６が下位クラスタ２に属することを認識してもらうための「ｅｎｔｒｙメッセージ」を通常のＩｎｔｅｒｎｅｔ上の通信手段によって送る。キャッシュノード６への依頼を行った代表キャッシュノード１は、新規追加されたキャッシュノード６宛に、「ｅｎｔｒｙメッセージ」を受信したことを示すメッセージを下位クラスタ２内通信によって送り、同時に下位クラスタマップ４−２に必要な情報を要求する。要求を受けた新規追加キャッシュノード６は、自身のキャッシュノード６に関する要求情報を下位クラスタ２内通信によって、キャッシュノード６への依頼を行った代表キャッシュノード１へ送る。

キャッシュノード依頼を行った代表キャッシュノード１は、新規代表キャッシュノード６から受け取った要求情報をもとに下位クラスタマップ４−２を更新し、更新された下位クラスタマップ４−２を、下位クラスタ２内通信によって、代表キャッシュノード１の所属する下位クラスタ内の他のキャッシュノード宛に送る。各キャッシュノードは各自の持つ下位クラスタ用の下位クラスタマップを更新して、登録完了のメッセージを、キャッシュノード依頼を行った代表キャッシュノードに、下位クラスタ内通信によって送る。

図５を参照すると、本実施例の分散情報配置システムにおける同一下位クラスタ内のキャッシュノード間の通信の様子の１例が示されている。下位クラスタ２内に存在する、代表キャッシュノード１を含む複数のキャッシュノード６、８らは、下位クラスタ内通信を一定時間間隔毎または不定時間間隔で行うことによって、互いの「生存」と「『情報の必要度』の数値」などの情報を交換し合う。これによって下位クラスタ２内の全てのキャッシュノードの下位クラスタ２内用の下位クラスタマップの更新と同期とを行う。ここで、下位クラスタ内通信は、新規にキャッシュノードが追加されたり、キャッシュノードやキャッシュノード間のリンクの障害などのイベントが発生した場合には、そのイベントをトリガーとして行われる。

図６（ａ）および図６（ｂ）を参照すると、本実施例の分散情報配置システムにおける同一下位クラスタ内でのアクセスの負荷分散の様子の１例が、それぞれ示されている。図７（ａ）および図７（ｂ）を参照すると、本実施例の分散情報配置システムにおけるアクセスの負荷分散のフローチャートの１例が、それぞれ示されている。

下位クラスタ内に、代表キャッシュノードを除く少なくとも１つの他のキャッシュノードが追加されると、それらは自律的に負荷分散を行う。すなわち、下位クラスタ内通信によって下位クラスタ２内の「『情報の必要度』の数値」は各キャッシュノード１、６、８が、同一内容の下位クラスタ２内用下位クラスタマップを保持しているため、「『情報の必要度』の数値」の最も少ないキャッシュノードから順番にアクセスを転送する。

図８を参照すると、本実施例の分散情報配置システムにおける、あるＮＷ距離以上のキャッシュノードからのアクセスが増加することによって、ＮＷ距離以上の次数の高いキャッシュノードのキャッシュノード化とそこでの新規下位クラスタ生成が行われる様子の１例が示されている。図９を参照すると、本実施例の分散情報配置システムにおける、あるＮＷ距離以上のキャッシュノードからのアクセスが増加することによって、ＮＷ距離以上の次数の高いキャッシュノードのキャッシュノード化とそこでの新規下位クラスタ生成が行われる際のフローチャートの１例が示されている。図１０を参照すると、本実施例の分散情報配置システムにおける、代表キャッシュノードのみで構成される上位クラスタＮＷの上位クラスタマップ１８の１例が示されている。

新規追加されたキャッシュノード１１は自分を代表キャッシュノードとする下位クラスタ１５を新たに形成し、下位クラスタ１５内用下位クラスタマップ４−１５を作成する。また、新規追加されたキャッシュノード１１は情報のＵＲＬと自身のＩＰアドレスを自身の所属するＮＷドメイン内のＤＮＳサーバ３４に登録しておく。ここで、キャッシュノード１１の登録するＤＮＳサーバは、オリジナルキャッシュノードの所属するクラスタ２内のキャッシュノードが、それぞれ情報のＵＲＬと自身のＩＰアドレスを登録しているＤＮＳサーバ３１，３２，３３の全てと異なっている。以降、追加される下位クラスタの代表ノードとその下位クラスタ内に追加されるキャッシュノードでの負荷分散の動作は、図２（ａ）および図２（ｂ）と図３（ａ）および図３（ｂ）で示したように行われる。これらの方法により、自律分散的な負荷分散が実現される。ここで、この代表キャッシュノード同士による上位クラスタ間オーバーレイＮＷ１７は、下位クラスタ２および下位クラスタ１５の上位クラスタ間オーバーレイＮＷの上に構築される。

ここで、上位クラスタＮＷ１７内の上位クラスタ内通信のために、上位クラスタＮＷ１７内の代表キャッシュノードに、上位クラスタＮＷ１７内部でのみ通用するローカルなＩＰアドレスを各々割り当て、このローカルなＩＰアドレスを用いた上位クラスタＮＷ１７内の上位クラスタ内通信を行っても良い。

またここで、上位クラスタ内用の上位クラスタマップの内容は、図１０に示したように、代表キャッシュノードのＤＮＳ登録名、グローバルＩＰアドレス、各クラスタ内のキャッシュノード数、『情報の必要度』の数値の合計値、および『情報の必要度』の数値の合計値の１次微分値である。ここで、上位クラスタ１７内用の上位クラスタマップの内容は、図１０に示した以外に、上位クラスタ１７内でローカルに付加したローカルなＩＰアドレスを含んでいても良い。また、上位クラスタ１７内用の上位クラスタマップの内容は、図１０に示した以外に何らかの『情報の必要度』の数値の経時変化の様子を表す変数を含んでいても良い。

各下位クラスタには、その代表キャッシュノードまたはクラスタの中心から一定の物理距離または論理的距離をＮＷ半径１０とする円で特定されるクラスタ領域と、このクラスタ領域に設置することのできるキャッシュノードの最大数とが予め定められる。

下位クラスタ２の代表キャッシュノード１が「ＮＷ半径１０を超える遠くからのアクセスが多くなる」あるいは「計算した自下位クラスタ２に置くことの出来るキャッシュノードの最大数に近づく」ことを検知すると、ＮＷ半径１０を超える場所に存在する、次数の大きなキャッシュノードに情報をキャッシュしてもらえないかランダムに、通常のＩｎｔｅｒｎｅｔ上の通信手段によって打診し、通常のＩｎｔｅｒｎｅｔ上の通信手段によって承諾をもらったキャッシュノード１１にキャッシュさせてもらう。ここで、複数の承諾をもらった場合には、それらの全て、あるいはそれらのうち次数の大きなキャッシュノードに対して、キャッシュさせてもらう。なお、この新規キャッシュノード１１の追加は、アクセス数の変動を考慮して、一定時間待ってから行う。

キャッシュノードの依頼を行った代表キャッシュノード１は、自キャッシュノード１を含む代表キャッシュノード１のみで構成される上位クラスタＮＷ１７を作成し、上位クラスタＮＷ１７用の上位クラスタマップ１８−２を作成する。

新規追加されたキャッシュノード１１は自分を代表キャッシュノードとする下位クラスタ１５を新たに形成し、下位クラスタ１５内用下位クラスタマップ４−１５を作成する。ここで、この代表キャッシュノード同士による上位クラスタ内オーバーレイＮＷ１７は、下位クラスタ２および下位クラスタ１５のオーバーレイＮＷの上に構築される。また、新規追加されたキャッシュノード１１はキャッシュノード依頼を受けた代表キャッシュノード１に対して、代表キャッシュノードのみで構成される上位クラスタＮＷ１７に対して、キャッシュノード１１が上位クラスタ１７に属することを認識してもらうための「ｅｎｔｒｙメッセージ」を通常のＩｎｔｅｒｎｅｔ上の通信手段によって送る。キャッシュノード１１への依頼を行った代表キャッシュノード１は、新規追加されたキャッシュノード１１宛に、「ｅｎｔｒｙメッセージ」を受信したことを示すメッセージを上位クラスタ１７内通信によって送り、同時に上位クラスタマップ１８に必要な情報を要求する。要求を受けた新規追加キャッシュノード１１は、自身のキャッシュノード１１に関する要求情報を上位クラスタ１７内通信によって、キャッシュノード１１への依頼を行った代表キャッシュノード１へ送る。

キャッシュノード依頼を行った代表キャッシュノード１は、新規代表キャッシュノード１１から受け取った要求情報をもとに上位クラスタマップ１８−１１を更新し、更新された上位クラスタマップ１８−１１を、上位クラスタ１７内通信によって、代表キャッシュノードが所属する下位クラスタ内の他の代表キャッシュノード宛に送る。各代表キャッシュノードは各自の持つ上位クラスタ用の上位クラスタマップを更新して、登録完了のメッセージを、キャッシュノード依頼を行った代表キャッシュノード１に、上位クラスタ内通信によって送る。

図１１を参照すると、本実施例の分散情報配置システムにおける、代表キャッシュノードのみで構成される上位クラスタレベルのＮＷ１７（上位層）、下位クラスタレベルのＮＷ２、１５、１６（中間層）、およびノードレベルのＮＷ（最下層）の関係の１例が示されている。

下位クラスタ同士は原則的に代表キャッシュノードであるキャッシュノード１、１１、１４同士が、各下位クラスタ２、１５、１６内のキャッシュノード数などのマクロな情報を、一定時間間隔毎または不定時間間隔で上位クラスタＮＷ１７上でオーバーレイ通信を行うことによって交換し、互いの生存と状況を確認し合うと共に、各々の代表キャッシュノード１，１１，１４が保持している各下位クラスタ２，１５，１６のマクロ情報を更新する。

図１２を参照すると、本実施例の分散情報配置システムにおけるキャッシュノードの脱退の様子の１例が示されている。図１３を参照すると、本実施例の分散情報配置システムにおけるキャッシュノードの脱退のフローチャートの１例が示されている。図１４を参照すると、本実施例の分散情報配置システムにおける代表キャッシュノードの脱退のフローチャートの１例が示されている。

図１２の下位クラスタ１５を例に取る。キャッシュノード１９へのアクセスが減って、「『情報の必要度』の数値」がある閾値２を下回ると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する。一定時間経過後の「『情報の必要度』の数値」の平均値がある閾値２を下回ると、自キャッシュノード１９の所属する下位クラスタ１５内に他のキャッシュノードがいる限り、下位クラスタ１５内の他のキャッシュノード全てに「脱退メッセージ」を下位クラスタ内通信によって送る。脱退メッセージを受け取った下位クラスタ１５内の他のキャッシュノードは、自キャッシュノードの保持している下位クラスタ１５内用下位クラスタマップから、脱退キャッシュノード１９のＩＰアドレス以外の情報を消去し、「脱退メッセージが到着した」という確認メッセージを脱退キャッシュノード１９に対して、下位クラスタ内通信によって送信する。脱退キャッシュノード１９は、下位クラスタ１５内の全ての他のキャッシュノードから、確認メッセージを受け取った後で、自キャッシュノード１９の保持しているキャッシュデータを削除し、情報のＵＲＬと自身のＩＰアドレスとを登録したＤＮＳサーバに削除要求を出して下位クラスタ１５から抜ける。

ここで、仮に代表キャッシュノード１１が抜ける場合には、以下のようになる。代表キャッシュノード１１へのアクセスが減って、「『情報の必要度』の数値」がある閾値２を下回ると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する。一定時間の「『情報の必要度』の数値」の平均値がある閾値２を下回ると、自キャッシュノード１１の所属する下位クラスタ１５内の他のキャッシュノードのうち、最も「『情報の必要度』の数値」の小さいキャッシュノード１３に他下位クラスタ２、１６との通信を行う代表キャッシュノードを譲り、自キャッシュノード１１の所属する下位クラスタ１５内の他のキャッシュノード全てと、他の下位クラスタ２、１６の各々全ての代表キャッシュノード１、１４へ、「別のキャッシュノード１３が代表キャッシュノードを引き継ぎ、自分１１が抜けること」を、下位クラスタ内通信、上位クラスタ内通信によってそれぞれ知らせる。代表キャッシュノード１１からの脱退メッセージを受け取った下位クラスタ１５内の他の全てのキャッシュノードは各々の持つ下位クラスタ内１５用下位クラスタマップから代表キャッシュノード１１の情報をＩＰアドレスを除いて削除し、「代表キャッシュノードを受け継いだキャッシュノード１３」を代表キャッシュノードとして下位クラスタ１５内用下位クラスタマップに設定する。さらに、「元の代表キャッシュノード１１」と「代表キャッシュノードを受け継いだキャッシュノード１３」に対して、「新しい代表キャッシュノード１３を下位クラスタ１５内用下位クラスタマップ４に登録したこと」を確認メッセージとして、下位クラスタ内通信によって伝える。

同様に他の下位クラスタ２、１６の各々の代表キャッシュノード１、１４は、各々の保持している上位クラスタＮＷ１７用の上位クラスタマップ１８−２、１８−１６から代表キャッシュノード１１の情報を削除し、新しい代表キャッシュノード１３を下位クラスタ１５の代表キャッシュノードとして上位クラスタＮＷ１７用の上位クラスタマップ１８−２、１８−１６に設定する。さらに他の下位クラスタ２、１６の各々の代表キャッシュノード１、１４は、確認メッセージを「代表キャッシュノードを受け継いだキャッシュノード１３」と「元の代表キャッシュノード１１」宛に、上位クラスタ内通信によって送信する。

自キャッシュノード１１の所属する下位クラスタ１５内の全てのキャッシュノード、および他の下位クラスタ２、１６の各々全ての代表キャッシュノード１、１４から、下位クラスタ内通信、上位クラスタ内通信によってそれぞれ確認メッセージを受け取った後で、「元の代表キャッシュノード１１」は、自キャッシュノード１１の保持するキャッシュデータを削除し、情報のＵＲＬと自身のＩＰアドレスとを登録したＤＮＳサーバに削除要求を出して下位クラスタ１５から抜ける。

図１５を参照すると、本実施例の分散情報配置システムにおける下位クラスタの脱退の様子の１例が示されている。図１６を参照すると、本実施例の分散情報配置システムにおける下位クラスタの脱退のフローチャートの１例が示されている。

下位クラスタ１６を例にとって説明する。下位クラスタ１６に最終的に残ったキャッシュノード１４は必然的に下位クラスタの代表キャッシュノードであるが、代表キャッシュノード１４でも「『情報の必要度』の数値」がある閾値を下回ると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する。一定時間の「『情報の必要度』の数値」の平均値がある閾値を下回ると、代表キャッシュノード１４は他の全ての下位クラスタ２、１５の代表キャッシュノード１、１１に対して、脱退メッセージを上位クラスタ内通信によって送る。同時に、脱退代表キャッシュノード１４は自キャッシュノード１４の保持している上位クラスタＮＷ１７用下位クラスタマップ１８−１６を見て、他の全ての下位クラスタ２、１５の代表キャッシュノード１，１１のうち、キャッシュノード当たりの「『情報の必要度』の数値」が最も少なく、かつ下位クラスタ内のキャッシュノード密度の最大値の大きい代表キャッシュノード１１に、自キャッシュノード１４の所属する下位クラスタ１６内用の下位クラスタマップ４−１６を上位クラスタ内通信によって送信する。

他の全ての下位クラスタ２、１５の代表キャッシュノード１、１１は、脱退メッセージを送信した代表キャッシュノード１４に対して「代表キャッシュノード１４が抜けること」を確認するメッセージを「代表キャッシュノード１４」宛に上位クラスタ内通信によって送信した後で、代表キャッシュノード１４に関するＩＰアドレス以外の情報を上位クラスタＮＷ１７用下位クラスタマップ１８−２、１８−１５の各々から削除する。ここで脱退代表キャッシュノード１４から下位クラスタ１６内用の下位クラスタマップ４−１６を受け取った代表キャッシュノード１１は、「下位クラスタマップ４−１６を受け取ったこと」を確認メッセージとして、脱退代表キャッシュノード１４に上位クラスタ内通信によって送信する。

脱退代表キャッシュノード１４は、他の全ての下位クラスタ２、１５の代表キャッシュノード１、１１から「代表キャッシュノード１４が抜けること」を確認するメッセージを受け取り、かつ脱退代表キャッシュノード１４から下位クラスタ１６内用の下位クラスタマップ４−１６を受け取った代表キャッシュノード１１から「下位クラスタマップ４−１６を受け取ったこと」を確認するメッセージを受け取った後で、自キャッシュノード１４の保持するキャッシュデータを削除し、情報のＵＲＬと自身のＩＰアドレスとを登録したＤＮＳサーバに削除要求を出して上位クラスタＮＷ１７から抜ける。

図１７を参照すると、本実施例の分散情報配置システムにおける最後に残ったキャッシュノードの脱退の様子の１例が示されている。図１８を参照すると、本実施例の分散情報配置システムにおける最後に残ったキャッシュノードの脱退のフローチャートの１例が示されている。

オリジナルキャッシュノードを含む下位クラスタ以外で最終的に残った下位クラスタ１５において、最終的に残ったキャッシュノード１１（終末キャッシュノード）でも「『情報の必要度』の数値」がある閾値を下回ると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する。一定時間の「『情報の必要度』の数値」の平均値がある閾値を下回ると、オリジナルキャッシュノード１に対して、「自分１１が最終データのキャッシュノードであること」、終末キャッシュノードが保持している「キャッシュデータ」および「過去に脱退した他の下位クラスタの下位クラスタ内用の下位クラスタマップ」を、１）自キャッシュノード１１にそのまま置いても良い、２）何か他の形態（例えばリンク先としてなど）で置いても良い、あるいは、３）削除して欲しい、という「希望情報」と共に、上位クラスタ内通信によって伝える。

オリジナルキャッシュノード１は、終末キャッシュノード１１からの「希望情報」を元に、情報を、１）そのまま置いてもらうか、２）何か他の形態（例えばリンク先としてなど）で置かせてもらうか、あるいは、３）削除してもらうかを検討し、その結果を終末キャッシュノード１１に対して上位クラスタ内通信によって伝える。ここで、終末キャッシュノード１１に情報をキャッシュし続けてもらう理由は、そのデータが再度必要になる場合、最後までアクセスがあったキャッシュノードの周辺からの場合が多いと推定されるためである。

終末キャッシュノード１１に終末キャッシュノード１１がキャッシュしている情報を削除してもらう場合、オリジナルキャッシュノード１は、最後に残った下位クラスタ１５にいた他のキャッシュノード１３、１９に対して、情報を、１）そのまま置いて欲しい、２）何か他の形態（例えばリンク先としてなど）で置かせて欲しい、ことを通常のＩｎｔｅｒｎｅｔの通信手段によって伝える。

終末キャッシュノード１１は、オリジナルキャッシュノード１からの回答に従って、情報の管理形態を決定する。すなわち、情報を、１）そのまま置くか、２）何か他の形態（例えばリンク先としてなど）で置くか、あるいは、３）削除するか、のいずれかを行う。

オリジナルキャッシュノード１から、情報を、１）そのまま置いて欲しい、２）何か他の形態（例えばリンク先としてなど）で置かせて欲しいというメッセージを通常のＩｎｔｅｒｎｅｔの通信手段によって受け取った、最後に残った下位クラスタ１５にいた他のキャッシュノード１３、１９は、それぞれオリジナルキャッシュノード１に対して、情報を、１）自キャッシュノードにそのまま置いても良い、２）何か他の形態（例えばリンク先としてなど）で置いても良い、あるいは、３）置きたくない、という「希望情報」を通常のＩｎｔｅｒｎｅｔの通信手段によって伝える。

「希望情報」を受け取ったオリジナルキャッシュノード１は、その中に、情報を、１）自キャッシュノードにそのまま置いても良い、２）何か他の形態（例えばリンク先としてなど）で置いても良いという回答があれば、１）、２）の優先順位で、そのキャッシュノードと上位クラスタを形成し、情報を１）自キャッシュノードにそのまま置いても良い、２）何か他の形態（例えばリンク先としてなど）で置いても良いという回答を行ったキャッシュノードへ、キャッシュする情報を上位クラスタ内通信によって送信する。

「希望情報」を受け取ったオリジナルキャッシュノード１は、その中に、３）置きたくないという回答しか無ければ、最後から２番目に削除された下位クラスタ１６にいた全てのキャッシュノードに対して、情報を、１）そのまま置いて欲しい、２）何か他の形態（例えばリンク先としてなど）で置かせて欲しい、ことを通常のＩｎｔｅｒｎｅｔ上の通信手法によって伝える。

オリジナルキャッシュノード１から、情報を、１）そのまま置いて欲しい、２）何か他の形態（例えばリンク先としてなど）で置かせて欲しいというメッセージを受け取った、最後から２番目に残った下位クラスタ１６にいた全てのキャッシュノード１４、２０、２１は、それぞれオリジナルキャッシュノード１に対して、情報を、１）自キャッシュノードにそのまま置いても良い、２）何か他の形態（例えばリンク先としてなど）で置いても良い、あるいは、３）置きたくない、という「希望情報」をそれぞれ通常のＩｎｔｅｒｎｅｔ上の通信手法によって伝える。

以下、上記の段落０１２５から段落０１２８までの手順を繰り返す。

最終的にオリジナルキャッシュノード１以外にキャッシュしてくれるキャッシュノードが無ければ、オリジナルキャッシュノード１は、情報を自キャッシュノード１に保存したままにする。

以上のようにして、通信ＮＷ上の情報へのアクセス数に適応して、情報のキャッシュ配置の量と質を利他的かつ協調的な仕組みによって自律分散的に決定することで、効率的な情報の分散キャッシュ配置を実現するとともに、一度廃れてアクセスの無くなった情報の効率的な再生を実現する。

［動作の説明］
次に本実施例の分散情報配置システムの動作について説明する。

図１を参照すると、本実施例の分散情報配置システムにおける「『情報の必要度』の数値」の変化の様子の１例が示されている。アクセスがあるたびに、「『情報の必要度』の数値」は一定量だけ増加する。「『情報の必要度』の数値」は一定時間が経過する毎に一定量だけ減少する。なお、時間経過に伴い減少する「『情報の必要度』の数値」は、非線形に減少しても良い。また、アクセスがあるたびに増加する「『情報の必要度』の数値」は、キャッシュノードのアクセスを受信可能なインターフェースの数や、インターフェースの入力バッファサイズなどに応じて、キャッシュノード毎に異なっていても良い。また、アクセスがあるたびに増加する「『情報の必要度』の数値」は、自下位クラスタ内に置くことの出来るキャッシュノードの最大数に応じて、下位クラスタ毎で異なっていても良い。また、時間経過に伴い減少する「『情報の必要度』の数値」は、キャッシュノードのアクセスを受信可能なインターフェースの数や、インターフェースの入力バッファサイズなどに応じて、キャッシュノード毎に異なっていても良い。また、時間経過に伴い減少する「『情報の必要度』の数値」は、自下位クラスタ内に置くことの出来るキャッシュノードの最大数に応じて、下位クラスタ毎で異なっていても良い。

（１）キャッシュノードの増加に関する動作の説明
図２（ａ）および（ｂ）、図３（ａ）および（ｂ）、図４を参照して、本実施例の分散情報配置システムにおけるキャッシュノードの増加に関する動作を説明する。

情報とある値（初期値）の「情報の必要度」をオリジナルキャッシュノード１に配置する（図３ａのＳ３０１、図３ｂのＳ３２１）。またオリジナルキャッシュノードは、自身の所属するＮＷのＤＮＳサーバに自身をＮＷ上で一意に識別可能な識別子であるグローバルＩＰアドレスと、ＮＷ内の他のノードがアクセスする場合に用いる該キャッシュ情報の場所を指し示す記述方式であるＵＲＬを登録しておく（図２ａまたは図２ｂのオリジナルキャッシュノード１から出ている１点鎖線）。同時に自分を代表キャッシュノードとする下位クラスタ２を生成し、当該オリジナルキャッシュノード１のＩＰアドレスと「『情報の必要度』の数値」とを下位クラスタ内用の下位クラスタマップ４−２に登録する。下位クラスタ内用の下位クラスタマップ４−２は各下位クラスタ内のキャッシュノードが分散的に所有し、キャッシュノードは下位クラスタ内用の下位クラスタマップに登録された複数のキャッシュノードと下位クラスタ内のオーバーレイ通信で下位クラスタＮＷ２内通信を行う。

図１に示したように情報へのアクセスがあるたびに「『情報の必要度』の数値」が増加する。

図２（ａ）および（ｂ）では、理解のし易さを目的に、アクセスをアリ３で表し、またアクセスによる「『情報の必要度』の数値」の増加分をアリ３が運んでいる荷物Ａで表している。アクセスが増えて「『情報の必要度』の数値」がある閾値Θ１を超えると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する（図３ａのＳ３０２、Ｓ３０３、図３ｂのＳ３２２、Ｓ３２３）。一定時間の「『情報の必要度』の数値」の平均値がある閾値Θ１を超えると、代表キャッシュノードはあるホップ数内にある、次数の大きなキャッシュノードに情報をキャッシュしてもらえないかランダムに打診し、承諾をもらったキャッシュノード６にキャッシュさせてもらう（図３ａのＳ３０４〜Ｓ３０７、図３ｂのＳ３２４〜Ｓ３２７）。

ここで閾値Θ１は、キャッシュノードのアクセスを受信可能なインターフェースの入力バッファサイズの最大値の１から１００％の割合の範囲内で、かつ後述のキャッシュノードが下位クラスタから脱退する場合の閾値Θ２より大きい割合に設定する。また、閾値Θ１は、キャッシュノードのアクセスを受信可能なインターフェースの数や、該インターフェースの入力バッファサイズなどに応じて、キャッシュノード毎に異なっていても良い。また、閾値Θ１は、自下位クラスタ内に置くことの出来るキャッシュノードの最大数に応じて、下位クラスタ毎で異なっていても良い。

複数のキャッシュノードから通常のＩｎｔｅｒｎｅｔにおける通信手法により承諾をもらった場合には、それらの全て、あるいはそれらのうち次数の大きなキャッシュノードに対して、キャッシュさせてもらう（図３ａのＳ３０８、図３ｂのＳ３２８）。もし、一定のホップ数内のキャッシュノードから承諾が得られなければ、オリジナルキャッシュノードは探索ホップ数を＋１して、承諾を得られるキャッシュノードを探索する（図３ａのＳ３０６でＮｏ、図３ｂのＳ３２６でＮｏ）。

新規追加されたキャッシュノード６は、自情報のＵＲＬと自身のＩＰアドレスを自ノードの属するＮＷドメインのＤＮＳサーバに登録しておく（図３ａのＳ３０９、図３ｂのＳ３２９、図２ａのキャッシュサーバ６から出ている１点鎖線、図２ｂのキャッシュサーバ６から出ている１点鎖線）。

新規追加されたキャッシュノード６は、下位クラスタ２内の代表キャッシュノード１に、キャッシュノード６が下位クラスタ２に属することを認識してもらうための「ｅｎｔｒｙメッセージ」を通常のＩｎｔｅｒｎｅｔ上の通信手段によって送る。キャッシュノード６への依頼を行った代表キャッシュノード１は、新規追加されたキャッシュノード６宛に、「ｅｎｔｒｙメッセージ」を受信したことを示すメッセージを下位クラスタ２内通信によって送り、同時に下位クラスタマップ４−２に必要な情報を要求する（図３ａのＳ３１０、図３ｂのＳ３３０）。要求を受けた新規追加キャッシュノード６は、自身のキャッシュノード６に関する要求情報を下位クラスタ２内通信によって、キャッシュノード６への依頼を行った代表キャッシュノード１へ送る（図３ａのＳ３１１、図３ｂのＳ３３１）。

キャッシュノード依頼を行った代表キャッシュノード１は、新規代表キャッシュノード６から受け取った要求情報をもとに下位クラスタマップ４−２を更新し、更新された下位クラスタマップ４−２を、下位クラスタ２内通信によって、代表キャッシュノードの所属する下位クラスタ内の他のキャッシュノード宛に送る（図３ａのＳ３１２、図３ｂのＳ３３２）。各キャッシュノードは各自の持つ下位クラスタ用の下位クラスタマップを更新して、登録完了のメッセージを、キャッシュノード依頼を行った代表キャッシュノードに、下位クラスタ内通信によって送る（図３ａのＳ３１３、図３ｂのＳ３３３）。

図５を参照すると、本実施例の分散情報配置システムにおける同一下位クラスタ内のキャッシュノード間の通信の様子の１例が示されている。下位クラスタ２内に存在する、代表キャッシュノード１を含む複数のキャッシュノード６、８らは、下位クラスタ内通信によって一定時間間隔毎または不定時間間隔で行うことによって、互いの「生存」と「『情報の必要度』の数値」などの情報を交換し合う。これによって下位クラスタ２内の全てのキャッシュノードの下位クラスタ２内用の下位クラスタマップの更新と同期とを行う。ここで、下位クラスタ内通信は、新規にキャッシュノードが追加されたり、キャッシュノードやキャッシュノード間のリンクの障害などのイベントが発生した場合には、そのイベントをトリガーとして行われる。

ここで、同一情報のループを防ぐために、下位クラスタＮＷ内でのオーバーレイ通信は、代表キャッシュノード１をＩＥＴＦ（Ｔｈｅ Ｉｎｔｅｒｎｅｔ Ｅｎｇｉｎｅｅｒｉｎｇ Ｔａｓｋ Ｆｏｒｃｅの略）のＲＦＣ２７９６に規定されたルートリフレクタに設定した上での通信であっても良い。

また、ここで同一情報のループを防ぐために、下位クラスタ内通信は、ＩＥＴＦのＲＦＣ２３２８に規定されたＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ａｌｇｏｒｉｔｈｍ）をプロトコルとして用いても良い。

また、ここで同一情報のループを防ぐために、下位クラスタＮＷ内の何らかのオーバーレイ通信は、ＩＥＴＦのＲＦＣ１１４２またはＲＦＣ１１９５に規定されたＩＳ−ＩＳ（Ｉｎｔｅｒｍｅｄｉａｔｅ Ｓｙｓｔｅｍ−Ｉｎｔｅｒｍｅｄｉａｔｅ Ｓｙｓｔｅｍ）をプロトコルとして用いても良い。

さらに、全てのキャッシュノードの下位クラスタ２内用の下位クラスタマップの同期を取るために、下位クラスタ２内において下位クラスタ内通信によって交換される情報には、何らかのフォーマットによるバージョン情報を含んでいても良い。

（２）下位クラスタ内でのアクセス負荷分散に関する動作の説明
図６（ａ）および図６（ｂ）、図７（ａ）および図７（ｂ）を参照して、本実施例の分散情報配置システムにおける下位クラスタ内でのアクセスの負荷分散に関する動作を説明する。

下位クラスタ内に、代表キャッシュノードを除く少なくとも１つの他のキャッシュノードが追加されると、それらは自律的に負荷分散を行う。すなわち、下位クラスタ内のオーバーレイ通信によって下位クラスタ２内の「『情報の必要度』の数値」は各キャッシュノード１、６、８が、同一内用の下位クラスタ２内用下位クラスタマップ４−２を保持しているため、「『情報の必要度』の数値」の最も少ないキャッシュノードから順番にアクセスを転送する。

図６（ａ）は、下位クラスタ２内の複数のキャッシュノードがそれぞれ個別のＤＮＳに登録している場合である。この場合、アクセス元のノード３ａ、３ｂ、３ｃはそれぞれ自身の所属するＮＷドメインのＤＮＳサーバ３１、３２、３３に、キャッシュされている情報のキャッシュノードのＩＰアドレスを知るためにアクセスする（図７ａのＳ７０１）。ここでは、簡単のためＤＮＳサーバ３１、３２、３３はキャッシュノードのＩＰアドレスを知っていることとする。

ＤＮＳサーバ３１、３２、３３はアクセス元のノード３ａ、３ｂ、３ｃに対してそれぞれキャッシュノードである１、６、８のＩＰアドレスを教える（図７ａのＳ７０２）。これによって、アクセス元のノード３ａ、３ｂ、３ｃはキャッシュノード１、６、８にそれぞれアクセスする（図７ａのＳ７０３）。

アクセスをそれぞれ受けたキャッシュノード１、６、８は、それぞれが保有する下位クラスタ２のクラスタマップ４−２を見て、「『情報の必要度』の数値」の最も少ないキャッシュノードから順番にアクセスを転送する（図７ａのＳ７０４）。

これらの方法により、自律分散的な負荷分散が実現される。

図６（ｂ）は、下位クラスタ２内の複数のキャッシュノードが同じＤＮＳに登録している場合である。この場合、アクセス元のノード３ａ、３ｂ、３ｃはそれぞれＤＮＳサーバ３１に、キャッシュされている情報のキャッシュノードのＩＰアドレスを知るためにアクセスする（図７ｂのＳ７１１）。ここでは、簡単のためＤＮＳサーバ３１はキャッシュノードのＩＰアドレスを知っていることとする。

ＤＮＳサーバ３１は、自身に実装されている手法によってアクセス元のノード３ａ、３ｂ、３ｃに対してそれぞれキャッシュノードである１、６、８の中からいずれかを選んで、そのキャッシュノードのＩＰアドレスを教える（図７ｂのＳ７１２）。これによって、アクセス元のノード３ａ、３ｂ、３ｃは、ＤＮＳサーバによって選択されたキャッシュノードにそれぞれアクセスする（図７ｂのＳ７１３）。

アクセスをそれぞれ受けたキャッシュノードは、それぞれが保有する下位クラスタ２のクラスタマップ４−２を見て、「『情報の必要度』の数値」の最も少ないキャッシュノードから順番にアクセスを転送する（図７ｂのＳ７１４）。

これらの方法により、自律分散的な負荷分散が実現される。

ここで、アクセスを転送する順番は、クラスタマップ４内にある全てのキャッシュノードの「現在の『情報の必要度』の数値」に「アクセス時間間隔の平均値」と「『情報の必要度』の数値の１次微分値」との積を加えた値を計算することで、それぞれのキャッシュノードの今後の「『情報の必要度』の数値」の予測値を計算し、予測値の最も小さいキャッシュノードから順でも良い。

また、アクセスを転送する順番は、クラスタマップ４内にある全てのキャッシュノードの「現在の『情報の必要度』の数値」に「アクセス時間間隔の平均値」と「『情報の必要度』の数値の１次微分値」との積と、「アクセス時間間隔の平均値」の２乗と「『情報の必要度』の数値の２次微分値」との積を加えた値を計算することで、それぞれのキャッシュノードの今後の「『情報の必要度』の数値」の予測値を計算し、予測値の最も小さいキャッシュノードから順でも良い。

また、アクセスを転送する順番は、「『情報の必要度』の数値」の最も少ないキャッシュノードに対して、閾値Θ１まで増加させ、その後その時点で「『情報の必要度』の数値」の最も少ないキャッシュノードに対して、閾値Θ１まで増加させることを繰り返しても良い。

また、アクセスを転送する順番は、「『情報の必要度』の数値」の最も少ないキャッシュノードから「『情報の必要度』の数値」の少ない順番にアクセスを転送することを繰り返すものであっても良い。

また、アクセスを転送する順番は、下位クラスタ２内のキャッシュノードのアクセスを受信可能なインターフェースの数が少ない順でも良い。

また、アクセスを転送する順番は、下位クラスタ２内のキャッシュノードのアクセスを受信可能なインターフェースの入力バッファサイズが少ない順でも良い。

また、アクセスを転送する順番は、下位クラスタ毎で異なっていても良い。

（３）クラスタの増加に関する動作の説明
図８、図９および図１０を参照して、本実施例の分散情報配置システムにおけるクラスタの増加に関する動作を説明する。

各下位クラスタ２には、その代表キャッシュノード１またはクラスタ２の中心から一定の物理距離または論理的距離をＮＷ半径１０とする円で特定されるクラスタ領域と、このクラスタ領域に設置することのできるキャッシュノードの最大数とが予め定められる。

ここで、自キャッシュノード１または下位クラスタ２を中心としたアクセス元のＮＷ半径１０は、下位クラスタ２内の全てまたは１部のキャッシュノードの、アクセスを受信可能なインターフェースの数に基づいて設定しても良い。

また、自キャッシュノード１または下位クラスタ２を中心としたアクセス元のＮＷ半径１０は、下位クラスタ２内の全てまたは１部のキャッシュノードの、アクセスを受信可能なインターフェースの入力バッファサイズに基づいて設定しても良い。

また、自キャッシュノード１または下位クラスタ２を中心としたアクセス元のＮＷ半径１０は、下位クラスタ２内の全てまたは１部のキャッシュノードの、アクセスを受信可能なインターフェースの数と、アクセスを受信可能なインターフェースの入力バッファサイズの両方に基づいて設定しても良い。

このようにして、下位クラスタ２の代表キャッシュノード１が「ＮＷ半径１０を超える遠くからのアクセスが多くなる」あるいは「計算した自下位クラスタ２に置くことの出来るキャッシュノードの最大数に近づく」ことを知ると、ＮＷ半径１０を超える場所に存在する、次数の大きなキャッシュノードに情報をキャッシュしてもらえないかランダムに通常のＩｎｔｅｒｎｅｔにおける通信手法により打診し、承諾をもらったキャッシュノード１１にキャッシュさせてもらう（図９のＳ９０１〜Ｓ９０４）。ここで、複数の承諾をもらった場合には、それらの全て、あるいはそれらのうち次数の大きなキャッシュノードに対して、キャッシュさせてもらう（図９のＳ９０５）。

キャッシュノードの依頼を行った代表キャッシュノード１は、自キャッシュノード１を含む代表キャッシュノード１のみで構成される上位クラスタＮＷ１７を作成し、上位クラスタＮＷ１７用の上位クラスタマップ１８−２を作成する（図９のＳ９０６）。

新規追加されたキャッシュノード１１は自分を代表キャッシュノードとする下位クラスタ１５を新たに形成し、下位クラスタ１５内用下位クラスタマップ４−１５を作成する（図９のＳ９０７）。

また、新規追加されたキャッシュノード１１は情報のＵＲＬと自身のＩＰアドレスを自身の所属するＮＷドメイン内のＤＮＳサーバ３４に登録しておく（図９のＳ９０７）。ここで、キャッシュノード１１の登録するＤＮＳサーバは、オリジナルキャッシュノードの所属するクラスタ２内のキャッシュノードが、それぞれ情報のＵＲＬと自身のＩＰアドレスを登録しているＤＮＳサーバ３１，３２，３３の全てと異なっている。以降、追加される下位クラスタの代表ノードとその下位クラスタ内に追加されるキャッシュノードでの負荷分散の動作は、図２（ａ）および図２（ｂ）と図３（ａ）および図３（ｂ）で示したように行われる。これらの方法により、自律分散的な負荷分散が実現される（図９のＳ９０７）。

ここで、この代表キャッシュノード同士による上位クラスタ間オーバーレイＮＷ１７は、下位クラスタ２および下位クラスタ１５のクラスタ内オーバーレイＮＷの上に構築される（図９のＳ９０７）。

また、新規追加されたキャッシュノード１１はキャッシュノード依頼を受けた代表キャッシュノード１に対して、代表キャッシュノードのみで構成される上位クラスタＮＷ１７に対して、キャッシュノード１１が上位クラスタ１７に属することを認識してもらうための「ｅｎｔｒｙメッセージ」を通常のＩｎｔｅｒｎｅｔ上の通信手段によって送る（図９のＳ９０７）。

キャッシュノード１１への依頼を行った代表キャッシュノード１は、新規追加されたキャッシュノード１１宛に、「ｅｎｔｒｙメッセージ」を受信したことを示すメッセージを上位クラスタ１７内通信によって送り、同時に上位クラスタマップ１８に必要な情報を要求する（図９のＳ９０８）。要求を受けた新規追加キャッシュノード１１は、自身のキャッシュノード１１に関する要求情報を上位クラスタ１７内通信によって、キャッシュノード１１への依頼を行った代表キャッシュノード１へ送る。

キャッシュノード依頼を行った代表キャッシュノード１は、新規代表キャッシュノード１１から受け取った要求情報をもとに上位クラスタマップ１８−１１を更新し、更新された上位クラスタマップ１８−１１を、上位クラスタ１７内通信によって、代表キャッシュノードが所属する下位クラスタ内の他の代表キャッシュノード宛に送る。各代表キャッシュノードは各自の持つ上位クラスタ用の上位クラスタマップを更新して、登録完了のメッセージを、キャッシュノード依頼を行った代表キャッシュノード１に、上位クラスタ内通信によって送る（図９のＳ９０８）。

図１１を参照すると、本実施例の分散情報配置システムにおける、代表キャッシュノードのみで構成される上位クラスタレベルのＮＷ１７（上位層）、下位クラスタレベルのＮＷ２、１５、１６（中間層）、およびノードレベルのＮＷ（最下層）の関係の１例が示されている。

下位クラスタ同士は原則的に代表キャッシュノードであるキャッシュノード１、１１、１４同士が、各下位クラスタ２、１５、１６内のキャッシュノード数などのマクロな情報を、一定時間間隔毎または不定時間間隔で上位クラスタＮＷ１７上でオーバーレイ通信を行うことによって交換し、互いの生存と状況を確認し合うと共に、各々の代表キャッシュノード１，１１，１４が保持している各下位クラスタ２，１５，１６のマクロ情報を更新する（図９のＳ９０９）。

ここで、同一情報のループを防ぐために、何らかのオーバーレイ通信は、代表キャッシュノード１、１１、１４のいずれかをＩＥＴＦのＲＦＣ２７９６に規定されたルートリフレクタに設定した上での通信であっても良い。また、ここで同一情報のループを防ぐために、下位クラスタＮＷ内の何らかのオーバーレイ通信は、ＩＥＴＦのＲＦＣ２３２８に規定されたＯＳＰＦをプロトコルとして用いても良い。また、ここで同一情報のループを防ぐために、下位クラスタＮＷ内の何らかのオーバーレイ通信は、ＩＥＴＦのＲＦＣ１１４２またはＲＦＣ１１９５に規定されたＩＳ−ＩＳをプロトコルとして用いても良い。

さらに、全ての代表キャッシュノードの上位クラスタ１７内用の下位クラスタマップの同期を取るために、上位クラスタ１７内において何らかのオーバーレイ通信によって交換される情報には、何らかのフォーマットによるバージョン情報を含んでいても良い。

（４）キャッシュノードの減少に関する動作の説明
図１２、図１３および図１４を参照して、本実施例の分散情報配置システムにおけるキャッシュノードの減少に関する動作を説明する。

図１２の下位クラスタ１５を例に取る。キャッシュノード１９へのアクセスが減って、「『情報の必要度』の数値」がある閾値Θ２を下回ると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する（図１３のＳ１３０１、Ｓ１３０２）。一定時間経過後の「『情報の必要度』の数値」の平均値がある閾値Θ２を下回ると、自キャッシュノード１９の所属する下位クラスタ１５内に他のキャッシュノードがいる限り、下位クラスタ１５内の他のキャッシュノード全てに「脱退メッセージ」を下位クラスタ１５内用通信によって送る（図１３のＳ１３０３、Ｓ１３０４）。

ここで閾値Θ２は、キャッシュノードのアクセスを受信可能なインターフェースの入力バッファサイズの最大値の０から９９％の割合の範囲内で、かつ後述のキャッシュノードが下位クラスタに追加される場合の閾値Θ１より小さい割合に設定する。また、閾値Θ２は、キャッシュノードのアクセスを受信可能なインターフェースの数や、インターフェースの入力バッファサイズなどに応じて、キャッシュノード毎に異なっていても良い。また、閾値Θ２は、自下位クラスタ内に置くことの出来るキャッシュノードの最大数に応じて、下位クラスタ毎で異なっていても良い。

脱退メッセージを受け取った下位クラスタ１５内の他のキャッシュノードは自キャッシュノードの保持している下位クラスタ１５内用下位クラスタマップから、脱退キャッシュノード１９のＩＰアドレス以外の情報を消去し、「脱退メッセージが到着した」という確認メッセージを脱退キャッシュノード１９に対して下位クラスタ内通信によって送信する（図１３のＳ１３０５、Ｓ１３０６）。脱退キャッシュノード１９は、下位クラスタ１５内の全ての他のキャッシュノードから、確認メッセージを受け取った後で、自キャッシュノード１９の保持しているキャッシュデータを削除し、情報のＵＲＬと自身のＩＰアドレスとを登録したＤＮＳサーバに削除要求を出して下位クラスタ１５から抜ける（図１３のＳ１３０７）。

ここで、仮に代表キャッシュノード１１が抜ける場合には、以下のようになる。代表キャッシュノード１１へのアクセスが減って、「『情報の必要度』の数値」がある閾値Θ２を下回ると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する（図１４のＳ１４０１、Ｓ１４０２）。一定時間の「『情報の必要度』の数値」の平均値がある閾値Θ２を下回ると、自キャッシュノード１１の所属する下位クラスタ１５内の他のキャッシュノードのうち、最も「『情報の必要度』の数値」の小さいキャッシュノード１３に他の下位クラスタ２、１６との通信を行う代表キャッシュノードを譲り、自キャッシュノード１１の所属する下位クラスタ１５内の他のキャッシュノード全てと、他の下位クラスタ２、１６の各々全ての代表キャッシュノード１、１４へ、「別のキャッシュノード１３が代表キャッシュノードを引き継ぎ、自分１１が抜けること」を、下位クラスタ内通信、上位クラスタ内通信によってそれぞれ知らせる（図１４のＳ１４０３、Ｓ１４０４）。

代表キャッシュノード１１からの脱退メッセージを受け取った下位クラスタ１５内の他の全てのキャッシュノードは各々の持つ下位クラスタ１５内用下位クラスタマップから代表キャッシュノード１１の情報をＩＰアドレスを除いて削除し、「代表キャッシュノードを受け継いだキャッシュノード１３」を代表キャッシュノードとして下位クラスタ１５内用下位クラスタマップに設定する。さらに、「元の代表キャッシュノード１１」と「代表キャッシュノードを受け継いだキャッシュノード１３」に対して、下位クラスタ内通信によって「新しい代表キャッシュノード１３を下位クラスタ１５内用下位クラスタマップ４−１５に登録したこと」を確認メッセージとして伝える（図１４のＳ１４０５）。

同様に他の下位クラスタ２、１６の各々の代表キャッシュノード１、１４は、各々の保持している上位クラスタＮＷ１７用の上位クラスタマップ１８−２、１８−１６から代表キャッシュノード１１の情報を削除し、新しい代表キャッシュノード１３を下位クラスタ１５の代表キャッシュノードとして上位クラスタＮＷ１７用の上位クラスタマップ１８−２、１８−１６に設定する。さらに他の下位クラスタ２、１６の各々の代表キャッシュノード１、１４は、確認メッセージを「代表キャッシュノードを受け継いだキャッシュノード１３」と「元の代表キャッシュノード１１」宛に上位クラスタ内通信によって送信する（図１４のＳ１４０６）。

自キャッシュノード１１の所属する下位クラスタ１５内の全てのキャッシュノード、および他の下位クラスタ２、１６の各々全ての代表キャッシュノード１、１４からの確認メッセージを下位クラスタ内通信、上位クラスタ内通信によってそれぞれ受け取った後で、「元の代表キャッシュノード１１」は、自キャッシュノード１１の保持するキャッシュデータを削除し、情報のＵＲＬと自身のＩＰアドレスとを登録したＤＮＳサーバに削除要求を出して下位クラスタ１５から抜ける（図１４のＳ１４０７）。

（５）クラスタの減少に関する動作の説明
図１５および図１６を参照して、本実施例の分散情報配置システムにおけるクラスタの減少に関する動作を説明する。

下位クラスタ１６を例にとって説明する。下位クラスタ１６に最終的に残ったキャッシュノード１４は必然的に下位クラスタの代表キャッシュノードであるが、代表キャッシュノード１４でも「『情報の必要度』の数値」がある閾値を下回ると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する（図１６のＳ１６０１、Ｓ１６０２）。一定時間の「『情報の必要度』の数値」の平均値がある閾値を下回ると、代表キャッシュノード１４は他の全ての下位クラスタ２、１５の代表キャッシュノード１、１１に対して、脱退メッセージを送る（図１６のＳ１６０３、Ｓ１６０４）。同時に、脱退代表キャッシュノード１４は自キャッシュノード１４の保持している上位クラスタＮＷ１７用上位クラスタマップ１８−１６を見て、他の全ての下位クラスタ２、１５の代表キャッシュノード１，１１のうち、キャッシュノード当たりの「『情報の必要度』の数値」が最も少なく、かつ下位クラスタ内のキャッシュノード密度の最大値の大きい代表キャッシュノード１１に、自キャッシュノード１４の所属する下位クラスタ１６内用の下位クラスタマップ４−１６を上位クラスタ内通信によって送信する（図１６のＳ１６０６）。

他の全ての下位クラスタ２、１５の代表キャッシュノード１、１１は、脱退メッセージを送信した代表キャッシュノード１４に対して「代表キャッシュノード１４が抜けること」を確認するメッセージを「代表キャッシュノード１４」宛に上位クラスタ内通信によって送信した後で、代表キャッシュノード１４に関するＩＰアドレス以外の情報を上位クラスタＮＷ１７用上位クラスタマップ１８−２、１８−１５の各々から削除する（図１６のＳ１６０５）。ここで脱退代表キャッシュノード１４から下位クラスタ１６内用の下位クラスタマップ４−１６を受け取った代表キャッシュノード１１は、「下位クラスタマップ４−１６を受け取ったこと」を確認メッセージとして、脱退代表キャッシュノード１４に上位クラスタ内通信によって送信する（図１６のＳ１６０７）。

脱退代表キャッシュノード１４は、他の全ての下位クラスタ２、１５の代表キャッシュノード１、１１から「代表キャッシュノード１４が抜けること」を確認するメッセージを受け取り、かつ脱退代表キャッシュノード１４から下位クラスタ１６内用の下位クラスタマップ４−１６を受け取った代表キャッシュノード１１から「下位クラスタマップ４−１６を受け取ったこと」を確認するメッセージを上位クラスタ内通信によって受け取った後で、自キャッシュノード１４の保持するキャッシュデータを削除し、情報のＵＲＬと自身のＩＰアドレスとを登録したＤＮＳサーバに削除要求を出して上位クラスタＮＷ１７から抜ける（図１６のＳ１６０８）。

（６）終末キャッシュノードの脱退に関する動作の説明
図１７および図１８を参照して、終末キャッシュノードの脱退に関する動作を説明する。

最終的に残った下位クラスタ１５において、最終的に残ったキャッシュノード１１（終末キャッシュノード）でも「『情報の必要度』の数値」がある閾値を下回ると、数値の変動を考慮して、その時点から一定時間の「『情報の必要度』の数値」の平均値を取得する（図１８のＳ１８０１）。一定時間の「『情報の必要度』の数値」の平均値がある閾値を下回ると、オリジナルキャッシュノード１に対して、「自分１１が最終データのキャッシュノードであること」、終末キャッシュノードが保持している「キャッシュデータ」および「過去に脱退した他の下位クラスタの下位クラスタ内用の下位クラスタマップ」を、１）自キャッシュノード１１にそのまま置いても良い、２）何か他の形態（例えばリンク先としてなど）で置いても良い、あるいは、３）削除して欲しい、という「希望情報」と共に、上位クラスタ内通信によって伝える（図１８のＳ１８０２）。

オリジナルキャッシュノード１は、終末キャッシュノード１１からの「希望情報」を元に、情報を、１）そのまま置いてもらうか、２）何か他の形態（例えばリンク先としてなど）で置かせてもらうか、あるいは、３）削除してもらうかを検討し、その結果を終末キャッシュノード１１に対して上位クラスタ内通信によって伝える（図１８のＳ１８０３）。ここで、終末キャッシュノード１１に情報をキャッシュし続けてもらう理由は、そのデータが再度必要になる場合、最後までアクセスがあったキャッシュノードの周辺からの場合が多いと推定されるためである。

終末キャッシュノード１１に終末キャッシュノード１１がキャッシュしている情報を削除してもらう場合、オリジナルキャッシュノード１は、最後に残った下位クラスタ１５にいた他のキャッシュノード１３、１９に対して、情報を、１）そのまま置いて欲しい、２）何か他の形態（例えばリンク先としてなど）で置かせて欲しい、ことを通常のＩｎｔｅｒｎｅｔ上の通信手段によって伝える（図１８のＳ１８０５）。

終末キャッシュノード１１は、オリジナルキャッシュノード１からの回答に従って、情報の管理形態を決定する。すなわち、情報を、１）そのまま置くか、２）何か他の形態（例えばリンク先としてなど）で置くか、あるいは、３）削除するか、のいずれかを行う（図１８のＳ１８０４）。

オリジナルキャッシュノード１から、情報を、１）そのまま置いて欲しい、２）何か他の形態（例えばリンク先としてなど）で置かせて欲しいというメッセージを受け取った、最後に残った下位クラスタ１５にいた他のキャッシュノード１３、１９は、それぞれオリジナルキャッシュノード１に対して、情報を、１）自キャッシュノードにそのまま置いても良い、２）何か他の形態（例えばリンク先としてなど）で置いても良い、あるいは、３）置きたくない、という「希望情報」をそれぞれ通常のＩｎｔｅｒｎｅｔ上の通信手法によって伝える（図１８のＳ１８０６）。

「希望情報」を受け取ったオリジナルキャッシュノード１は、その中に、情報を、１）自キャッシュノードにそのまま置いても良い、２）何か他の形態（例えばリンク先としてなど）で置いても良いという回答があれば、１）、２）の優先順位で、そのキャッシュノードと上位クラスタを形成し、情報を、１）自キャッシュノードにそのまま置いても良い、２）何か他の形態（例えばリンク先としてなど）で置いても良いという回答を行ったキャッシュノードへ、キャッシュする情報を上位クラスタ内通信によって送信する（図１８のＳ１８０７）。

「希望情報」を受け取ったオリジナルキャッシュノード１は、その中に３）置きたくないという回答しか無ければ、最後から２番目に削除された下位クラスタ１６にいた全てのキャッシュノードに対して、情報を、１）そのまま置いて欲しい、２）何か他の形態（例えばリンク先としてなど）で置かせて欲しい、ことを通常のＩｎｔｅｒｎｅｔ上の通信手法によって伝える。

オリジナルキャッシュノード１から、情報を、１）そのまま置いて欲しい、２）何か他の形態（例えばリンク先としてなど）で置かせて欲しいというメッセージを受け取った、最後から２番目に残った下位クラスタ１６にいた全てのキャッシュノード１４、２０、２１は、それぞれオリジナルキャッシュノード１に対して、情報を、１）自キャッシュノードにそのまま置いても良い、２）何か他の形態（例えばリンク先としてなど）で置いても良い、あるいは、３）置きたくない、という「希望情報」をそれぞれ通常のＩｎｔｅｒｎｅｔ上の通信手法によって伝える（図１８のＳ１８０８）。

以下、段落番号０１９９から段落番号０２０２までの手順を繰り返す。

最終的にオリジナルキャッシュノード１以外にキャッシュしてくれるキャッシュノードが無ければ、オリジナルキャッシュノード１は、情報を自キャッシュノード１に保存したままにする（図１８のＳ１８０９）。

ここで、オリジナルキャッシュノード１が保存する情報は、キャッシュ情報および上位クラスタの過去に登録された１部または全ての代表ノードのＤＮＳサーバ上の登録名およびＩＰアドレスであっても良い。また、オリジナルキャッシュノード１が保存する情報は、キャッシュ情報および複数の下位クラスタ過去に登録された１部または全てのキャッシュノードのＤＮＳサーバ上の登録名およびＩＰアドレスを含んでいても良い。また、オリジナルキャッシュノード１が保存する情報は、キャッシュ情報および上位クラスタの過去に登録された１部または全ての代表ノードと、複数の下位クラスタの過去に登録された１部または全てのキャッシュノードのＤＮＳサーバ上の登録名およびＩＰアドレスを含んでいても良い。

（７）アクセスが再度増加した場合に関する動作の説明
上記「（６）終末キャッシュノードの脱退に関する動作の説明」において、最終的にキャッシュされるべき情報をどのキャッシュノードが保持しているかによって、最初のステップのみが異なる。

（７−１）最終的にオリジナルキャッシュノードのみがキャッシュされるべき情報を保持している場合
この場合は、「（１）キャッシュノードの増加に関する動作の説明」が最初のステップとなる。

（７−２）最終的にオリジナルキャッシュノードと終末キャッシュノードがキャッシュされるべき情報を保持している場合

図１７を用いて説明する。この場合、オリジナルキャッシュノード１と終末キャッシュノード１１のうち、アクセスを受けたキャッシュノードにおいて、「（１）キャッシュノードの増加に関する動作の説明」が最初のステップとなる。終末キャッシュノード１１においてアクセスが増加し、「（１）キャッシュノードの増加に関する動作の説明」で示した、閾値Θ１を超えてキャッシュノードの追加が必要になった場合、「（１）キャッシュノードの増加に関する動作の説明」で示した手順に従って、一定時間待ってから、終末キャッシュノード１１は自分の保持している下位クラスタ１５内の下位クラスタマップ４−１５の中に残っている、下位クラスタ１５内で過去にキャッシュノードであったキャッシュノード１３、１９に情報をキャッシュしてもらえないかを通常のＩｎｔｅｒｎｅｔ上の通信手法によって打診する。もし、いずれからも承諾を得られなかった場合には、ある一定のホップ数にあるキャッシュノードのうち、次数の大きなキャッシュノードにランダムに情報をキャッシュしてもらえないかを通常のＩｎｔｅｒｎｅｔ上の通信手法によって打診する。一定のホップ数内のキャッシュノードから承諾が得られなければ、該終末キャッシュノードは探索ホップ数を＋１して、承諾を得られるキャッシュノードを探索する。

下位クラスタ１５内の過去のキャッシュノード１３、１９あるいはホップ数による探索によって、いずれかのキャッシュノードから承諾を通常のＩｎｔｅｒｎｅｔ上の通信手法によって受けると、後は「（１）キャッシュノードの増加に関する動作の説明」において説明した手順に従って、キャッシュノードを増加させていく。

本実施例によれば、以下のような効果が得られる。

第１の効果は、分散キャッシュ配置が効率的に行えることである。その理由は、代表キャッシュノードを用いたキャッシュノードの下位クラスタ化、代表キャッシュノードあるいは下位クラスタを中心としたＮＷ距離の導入、ＮＷ距離より遠い先からのアクセスが一定量以上増加した場合にはＮＷ距離より遠い位置にいるキャッシュノードを中心とした別下位クラスタを形成する、という仕組みを用いたためである。

第２の効果は、キャッシュノード間のアクセスの負荷分散が自律分散的かつ効率的に行えることである。その理由は、代表キャッシュノードを含む下位クラスタ内で独自のオーバーレイＮＷを形成し、その中で各キャッシュノードの負荷状況を、下位クラスタに属する全てのキャッシュノードが把握可能となる仕組みを用いたためである。

第３の効果は、ある期間に渡ってアクセスが減少し、殆どまたは全くアクセスされなくなった情報を、再びアクセスが増えてくると効率的に増加させることができることである。その理由は、アクセス量の減少に伴うキャッシュノードおよび下位クラスタの縮小の仕組み、最終的な情報の効率的な保管の仕組みを設けたためである。

第４の効果は、各々の下位クラスタは自律分散的に負荷分散を行うこと、各々の下位クラスタはネットワーク上の距離的に異なる場所に配置されることによって、キャッシュする情報に対する破壊行為から情報を守ることが可能になる、すなわち情報の攻撃行為に対する頑健性が向上することである。

次に、本発明の分散情報配置システムの構成要素となるノード装置の実施例について説明する。

図２０を参照すると、本実施例のノード装置は、処理装置１１００と、記憶装置１２００と、通信装置１３００とから構成される。

記憶装置１２００は、コンピュータの主記憶や補助記憶で構成され、ユーザ端末へ提供する情報であるキャッシュ情報１２１０、図４に示した下位クラスタマップ１２２０および図１０に示した上位クラスタマップ１２３０を記憶するために用いられる。

通信装置１３００は、ネットワークインタフェースカード等で構成され、インターネット通信手段１３１０およびオーバーレイ通信手段１３２０として用いられる。

処理装置１１００は、コンピュータの中央処理装置で構成され、負荷分散手段１１１０、サービス提供手段１１２０、負荷情報更新手段１１３０、キャッシュノード増加手段１１４０、キャッシュノード減少手段１１５０、クラスタ増加手段１１６０、クラスタ減少手段１１７０、終末手段１１８０およびクラスタマップ同期手段１１９０を備えている。これらの各手段は、処理装置１１００上で実行されるプログラムによって実現することができる。プログラムは、磁気ディスク等のコンピュータ可読記録媒体に記録され、コンピュータに読み取られることによって、コンピュータ上に上記の各手段１１１０〜１１９０を実現する。

負荷分散手段１１１０は、ユーザ端末からキャッシュ情報１２１０に対するアクセス要求を受信した場合に、このアクセス要求を自ノードの属するクラスタの何れのノードで受け付けるかを、下位クラスタマップ１２２０に記載された各ノードの負荷情報（本実施例の場合は、『情報の必要度』の数値）に基づいて判断する機能を有する。負荷分散手段１１１０は、自ノードで受け付けると判断した場合にはアクセス要求を自ノードのサービス提供手段１１２０へ転送し、他ノードで受け付けると判断した場合には、オーバーレイ通信手段１３２０を通じて該当する他のノードへアクセス要求を転送する。また負荷分散手段１１１０は、自ノードのグローバルＩＰアドレスとキャッシュ情報１２１０のＵＲＬの対応関係を、自ノードが属するＮＷドメインのＤＮＳサーバに登録する機能を有する。

サービス提供手段１１２０は、負荷分散手段１１１０から通知されたアクセス要求に従って、キャッシュ情報１２１０を要求元のユーザ端末へ送信する機能を有する。

負荷情報更新手段１１３０は、サービス提供手段１１２０がキャッシュ情報１２１０をアクセスする毎に、図１で説明したように、下位クラスタマップ１２２０中の自ノードの『情報の必要度』の数値を増加させ、それに応じて、その１次および２次微分値を更新する機能を有する。また負荷情報更新手段１１３０は、一定時間経過毎に、下位クラスタマップ１２２０中の自ノードの『情報の必要度』の数値を減少させ、それに応じて、その１次および２次微分値を更新する機能を有する。

キャッシュノード増加手段１１４０は、図２および図３で説明したように、自ノードの属するクラスタに新たなキャッシュノードを追加する機能を有する。このキャッシュノード増加手段１１４０は、図３で説明した処理のうち、クラスタの代表ノードによって実行される処理部であるマスタ部１１４１と、代表ノード以外のノードによって実行される処理部であるスレーブ部１１４２とで構成される。

キャッシュノード減少手段１１５０は、図１２、図１３および図１４で説明したように、クラスタからキャッシュノードを削減する機能を有する。このキャッシュノード減少手段１１５０は、図１３および図１４で説明した処理のうち、削減対象となるノードによって実行される処理部であるマスタ部１１５１と、削減対象となるノード以外のノードによって実行される処理部であるスレーブ１１５２とで構成される。

クラスタ増加手段１１６０は、図８および図９で説明したように、新たなクラスタを追加する機能を有する。このクラスタ増加手段１１６０は、図９で説明した処理のうち、新たなクラスタを生成しようとする代表ノードによって実行される処理部であるマスタ部１１６１と、新たなクラスタを生成しようとする代表ノード以外のノードによって実行される処理部であるスレーブ部１１６２とで構成される。

クラスタ減少手段１１７０は、図１５および図１６で説明したように、クラスタを削減する機能を有する。このクラスタ減少手段１１７０は、図１６で説明した処理のうち、削減対象となるクラスタの代表ノードによって実行される処理部であるマスタ部１１７１と、削減対象となるクラスタの代表ノード以外のノードによって実行される処理部であるスレーブ部１１７２とで構成される。

終末手段１１８０は、図１７および図１８で説明したような終末キャッシュノードに関する処理を司る機能を有する。この終末手段１１８０は、図１８で説明した処理のうち、、オリジナルキャッシュノードによって実行される処理部であるマスタ部１１８１と、それ以外のノードによって実行される処理部であるスレーブ部１１８２とで構成される。クラスタマップ同期手段１１９０は、キャッシュノード間でクラスタマップの内容を一致させる処理を司る機能を有する。このクラスタマップ同期手段１１９０は、図１０に示した上位クラスタマップの同期処理を実行する処理部である上位クラスタ部１１９１と、図４に示した下位クラスタマップの同期処理を実行する処理部である下位クラスタ部１１９２とで構成される。

以上、本発明の実施の形態および実施例を説明したが、本発明は以上の例に限定されずその他各種の付加変更が可能である。例えば、上記の例では、幾つかのキャッシュノードを一つのクラスタとしてまとめたが、クラスタ化は本発明の必須の要件ではない。

本発明の活用例としては、通信ＮＷ上でのキャッシングを行う、Ｗｅｂサービス、Ｐｅｅｒ−ｔｏ−Ｐｅｅｒサービス、データストレージなどが挙げられる。

本発明の一実施例の分散情報配置システムにおける情報の必要度の数値の変化の様子の１例を示す図である。 本発明の一実施例の分散情報配置システムにおける新規キャッシュノード追加の様子の１例を示す図である。 本発明の一実施例の分散情報配置システムにおける新規キャッシュノード追加の様子の１例を示す図である。 本発明の一実施例の分散情報配置システムにおける新規キャッシュノード追加のフローチャートの１例を示す図である。 本発明の一実施例の分散情報配置システムにおける新規キャッシュノード追加のフローチャートの１例を示す図である。 本発明の一実施例の分散情報配置システムにおける、各キャッシュノードが保持する下位クラスタ内用の下位クラスタマップの１例を示す図である。 本発明の一実施例の分散情報配置システムにおける同一下位クラスタ内のキャッシュノード間の通信の様子の１例を示す図である。 本発明の一実施例の分散情報配置システムにおける同一下位クラスタ内でのアクセスの負荷分散の様子の１例を示す図である。 本発明の一実施例の分散情報配置システムにおける同一下位クラスタ内でのアクセスの負荷分散の様子の１例を示す図である。 本発明の一実施例の分散情報配置システムにおけるアクセスの負荷分散のフローチャートの１例を示す図である。 本発明の一実施例の分散情報配置システムにおけるアクセスの負荷分散のフローチャートの１例を示す図である。 本発明の一実施例の分散情報配置システムにおける、あるＮＷ距離以上のキャッシュノードからのアクセスが増加することによって、ＮＷ距離以上の次数の高いキャッシュノードのキャッシュノード化とそこでの新規下位クラスタ生成が行われる様子の１例を示す図である。 本発明の一実施例の分散情報配置システムにおける、あるＮＷ距離以上のキャッシュノードからのアクセスが増加することによって、ＮＷ距離以上の次数の高いキャッシュノードのキャッシュノード化とそこでの新規下位クラスタ生成が行われる際のフローチャートの１例を示す図である。 本発明の一実施例の分散情報配置システムにおける、代表キャッシュノードのみで構成される上位クラスタＮＷの上位クラスタマップの１例を示す図である。 本発明の一実施例の分散情報配置システムにおける、代表キャッシュノードのみで構成される上位クラスタレベルのＮＷ（上位層）、下位クラスタ内レベルのＮＷ（中間層）、およびノードレベルのＮＷ（最下層）の関係の１例を示す図である。 本発明の一実施例の分散情報配置システムにおけるキャッシュノードの脱退の様子の１例を示す図である。 本発明の一実施例の分散情報配置システムにおけるキャッシュノードの脱退のフローチャートの１例を示す図である。 本発明の一実施例の分散情報配置システムにおける代表キャッシュノードの脱退のフローチャートの１例を示す図である。 本発明の一実施例の分散情報配置システムにおける下位クラスタの脱退の様子の１例を示す図である。 本発明の一実施例の分散情報配置システムにおける下位クラスタの脱退のフローチャートの１例を示す図である。 本発明の一実施例の分散情報配置システムにおける最後に残ったキャッシュノードの脱退の様子の１例を示す図である。 本発明の一実施例の分散情報配置システムにおける最後に残ったキャッシュノードの脱退のフローチャートの１例を示す図である。 本発明の一実施の形態の分散情報配置システムのブロック図である。 本発明のノード装置の一実施例のブロック図である。

符号の説明

１…オリジナルキャッシュノードかつ下位クラスタ２の代表キャッシュノード
２…オリジナルキャッシュノードを含む下位クラスタ
３、３ａ、３ｂ、３ｃ…アクセスを表すアリ
４、４−２、４−１５、４−１６…下位クラスタマップ
５…オリジナルキャッシュノード１から一定の距離
６…下位クラスタ２内のキャッシュノード
８…下位クラスタ２内のキャッシュノード
１０…オリジナルキャッシュノード１または下位クラスタ２から一定の物理的または論理的距離
１０ａ…代表キャッシュノード１１または下位クラスタ１５から一定の距離または論理的距離
１０ｂ…代表キャッシュノード１１または下位クラスタ１６から一定の距離または論理的距離
１１…新規追加されたキャッシュノードかつ下位クラスタ１５の代表キャッシュノード
１３…下位クラスタ１５内のキャッシュノード
１４…新規追加されたキャッシュノードかつ下位クラスタ１６の代表キャッシュノード
１５…新規追加されたキャッシュノード１１が作成した下位クラスタ
１６…新規追加されたキャッシュノード１４が作成した下位クラスタ
１７…各下位クラスタの代表キャッシュノードのみで構成される上位クラスタおよびそのＮＷ
１８…上位クラスタ内用のクラスタマップ
１９…下位クラスタ１５内のキャッシュノード
２０…下位クラスタ１６内のキャッシュノード
２１…下位クラスタ１６内のキャッシュノード
３１，３２，３３、３４、３５、３６、３７、３８、３９…ＤＮＳサーバ
Ａ…アクセスによる情報の必要度の数値の増加分で、アリ３が運んでいる荷物
Ｂ…一般的なノード（キャッシュを行っていないノード）

Claims (20)

1. データを記憶するキャッシュと該キャッシュから前記データを読み出して端末装置に送信する手段とを備えた複数のノード装置がネットワークを介して接続された分散情報配置システムであって、
   前記ノード装置は、自ノード装置および他のノード装置の負荷情報を記憶する記憶手段と、前記端末装置から前記データのアクセス要求を受信したとき、前記記憶手段に記憶された負荷情報に基づいて、受信した前記アクセス要求を自ノード装置で処理するか、他の何れのノード装置で処理するかを判断する負荷分散手段と、自ノード装置で処理すると判断した前記アクセス要求を自ノード装置で受け付けて処理を行うサービス提供手段と、何れかの他のノード装置で処理すると判断した前記アクセス要求を該当する他のノード装置へ転送する通信手段とを備えたことを特徴とする分散情報配置システム。
2. 前記ノード装置は、自ノード装置のグローバルＩＰアドレスと前記データのＵＲＬとの対応関係を、自ノード装置が属するネットワークのＤＮＳサーバに登録する手段を備えることを特徴とする請求項１に記載の分散情報配置システム。
3. 前記ＤＮＳサーバは、同一のＵＲＬに対して異なる複数のグローバルＩＰアドレスが登録されているとき、これら複数のグローバルＩＰアドレスがほぼ均等に使用されるように、前記ＵＲＬに対応するグローバルＩＰアドレスの問い合わせに対する応答中に含めるグローバルＩＰアドレスを決定することを特徴とする請求項２に記載の分散情報配置システム。
4. 前記ノード装置は、前記負荷情報の内容を他の前記ノード装置と授受し合って内容を一致させる同期手段を備えることを特徴とする請求項１乃至３の何れか１項に記載の分散情報配置システム。
5. 前記負荷情報は、キャッシュ情報がアクセスされる毎に値が加算され、一定時間が経過する毎に値が減少される数値で表現されることを特徴とする請求項１乃至４の何れか１項に記載の分散情報配置システム。
6. 同じ前記データを記憶する複数の前記ノード装置が複数集まって１つのクラスタを構成し、同じクラスタ内の複数の前記ノード装置間で前記端末装置から受信したアクセス要求の負荷分散を行う請求項１乃至５の何れか１項に記載の分散情報配置システム。
7. 前記クラスタを構成する複数のノード装置のうちの１つのノード装置が代表ノードとして機能し、前記代表ノードは、自クラスタ内の前記ノード装置の負荷情報を収集して監視し、負荷が高くなった際に、前記データを未だキャッシュしていない他の前記ノード装置に前記データのコピーを送信して当該ノード装置を自クラスタの新たな構成メンバに加える処理を行うことを特徴とする請求項６に記載の分散情報配置システム。
8. 前記代表ノードは、自クラスタ内の前記ノード装置の負荷情報を収集して監視し、負荷が低くなった際に、自クラスタ内の幾つかの構成メンバに対して前記データのキャッシュを削除する指示を送信して当該ノード装置を自クラスタの構成メンバから外す処理を行うことを特徴とする請求項７に記載の分散情報配置システム。
9. 前記代表ノードは、新クラスタ生成条件が成立したか否かを判定し、前記新クラスタ生成条件が成立した場合に、前記データを未だキャッシュしていない他の前記ノード装置に対して、前記データのコピーを添えて新規クラスタの生成指示を送信する手段を備え、前記新規クラスタの生成指示を受信した前記ノード装置は、前記データのコピーを自ノード装置の前記キャッシュに記憶し、自ノード装置を代表ノードとする新たなクラスタを生成する手段を備えることを特徴とする請求項６または７に記載の分散情報配置システム。
10. 前記代表ノードは、自クラスタ内の前記ノード装置への前記端末装置からのアクセス情報を収集して監視し、予め定めれたネットワーク半径を超える遠くからのアクセスが増大した状況が発生した場合に、前記新クラスタ生成条件が成立したものと判定することを特徴とする請求項９に記載の分散情報配置システム。
11. 前記代表ノードは、自クラスタに属する前記ノード装置の数が予め定められた最大数に達した場合に、前記新クラスタ生成条件が成立したものと判定することを特徴とする請求項９に記載の分散情報配置システム。
12. 新たに生成された前記クラスタの前記代表ノードは、自クラスタに属する前記ノード装置が自ノードだけになり、且つ、自ノードに対する前記端末装置からのアクセス頻度が低下した場合に、自クラスタを消滅させる処理を行うことを特徴とする請求項１０または１１に記載の分散情報配置システム。
13. 前記データのオリジナルを保有する前記ノード装置を含むクラスタ以外で最終的に残ったクラスタにおいて、最終的に残った前記ノード装置である終末ノードでも前記端末装置からのアクセス頻度が低下した場合は、前記終末ノードと前記データのオリジナルを保有する前記ノード装置との間で、前記終末ノードにおけるキャッシュデータの維持および破棄に関するネゴシエーションを行い、両者で合意が得られた場合、前記終末ノードにおいて前記データのキャッシュを保持し続けることを特徴とする請求項１２に記載の分散情報配置システム。
14. データを記憶するキャッシュと該キャッシュから前記データを読み出して端末装置に送信する手段とを備えた複数のノード装置がネットワークを介して接続された分散情報配置システムにおける負荷分散方法であって、
    前記ノード装置のそれぞれが、前記端末装置から前記データのアクセス要求を受信したとき、自ノード装置および他のノード装置の負荷情報に基づいて、受信した前記アクセス要求を自ノード装置で処理するか、他の何れのノード装置で処理するかを判断するステップと、
    前記ノード装置のそれぞれが、自ノード装置で処理すると判断した前記アクセス要求を自ノード装置で受け付けて処理を行うステップと、
    前記ノード装置のそれぞれが、何れかの他のノード装置で処理すると判断した前記アクセス要求を該当する他のノード装置へ転送するステップとを含むことを特徴とする負荷分散方法。
15. 前記ノード装置が、自ノード装置のグローバルＩＰアドレスと前記データのＵＲＬとの対応関係を、自ノード装置が属するネットワークのＤＮＳサーバに登録するステップを含むことを特徴とする請求項１４に記載の負荷分散方法。
16. 前記ＤＮＳサーバが、同一のＵＲＬに対して異なる複数のグローバルＩＰアドレスが登録されているとき、これら複数のグローバルＩＰアドレスがほぼ均等に使用されるように、前記ＵＲＬに対応するグローバルＩＰアドレスの問い合わせに対する応答中に含めるグローバルＩＰアドレスを決定するステップを含むことを特徴とする請求項１５に記載の負荷分散方法。
17. データを記憶するキャッシュと該キャッシュから前記データを読み出して端末装置に送信する手段とを備えたノード装置であって、
    自ノード装置および他のノード装置の負荷情報を記憶する記憶手段と、前記端末装置から前記データのアクセス要求を受信したとき、前記記憶手段に記憶された負荷情報に基づいて、受信した前記アクセス要求を自ノード装置で処理するか、他の何れのノード装置で処理するかを判断する負荷分散手段と、自ノード装置で処理すると判断された前記アクセス要求を自ノード装置で受け付けて処理を行うサービス提供手段と、何れかの他のノード装置で処理すると判断された前記アクセス要求を該当する他のノード装置へ転送する通信手段とを備えたことを特徴とするノード装置。
18. 自ノード装置のグローバルＩＰアドレスと前記データのＵＲＬとの対応関係を、自ノード装置が属するネットワークのＤＮＳサーバに登録する手段を備えることを特徴とする請求項１７に記載のノード装置。
19. データを記憶するキャッシュと、該キャッシュから前記データを読み出して端末装置に送信する手段と、自ノード装置および他のノード装置の負荷情報を記憶する記憶手段とを備えたノード装置を構成するコンピュータを、
    前記端末装置から前記データのアクセス要求を受信したとき、前記記憶手段に記憶された負荷情報に基づいて、受信した前記アクセス要求を自ノード装置で処理するか、他の何れのノード装置で処理するかを判断する負荷分散手段と、自ノード装置で処理すると判断された前記アクセス要求を自ノード装置で受け付けて処理を行うサービス提供手段と、何れかの他のノード装置で処理すると判断された前記アクセス要求を該当する他のノード装置へ転送する通信手段として機能させるためのプログラム。
20. 前記コンピュータを、さらに、自ノード装置のグローバルＩＰアドレスと前記データのＵＲＬとの対応関係を、自ノード装置が属するネットワークのＤＮＳサーバに登録する手段として機能させるための請求項１９に記載のプログラム。

Images