(57)【要約】【課題】インデックス情報量（言い換えれば、記憶領域の容量）に応じて、ルートノードの数を適切に変更することが可能な情報配信システム、情報配信方法、ノード装置、及びノード処理プログラムを提供する。【解決手段】本発明は、ネットワークを介して互いに通信可能な複数のノード装置を備えた情報配信システムであって、少なくとも１の配信情報が複製され複数の前記ノード装置に保存されていく情報配信システムにおいて前記複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するノード装置であって、前記ノード情報を記憶するノード情報記憶手段と、前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより大きくなった場合に、当該ノード情報の一部を分割して新たなノード装置に管理させることを決定する分割決定手段と、前記新たなノード装置により管理されるノード情報を、前記ノード情報記憶手段から削除するノード情報削除手段と、を備える。【選択図】図７
2007148545.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを介して互いに通信可能な複数のノード装置を備えた情報配信システムであって、少なくとも１の配信情報が複製され複数の前記ノード装置に保存されていく情報配信システムにおいて前記複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するノード装置であって、
前記ノード情報を記憶するノード情報記憶手段と、
前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより大きくなった場合に、当該ノード情報の一部を分割して新たなノード装置に管理させることを決定する分割決定手段と、
前記新たなノード装置により管理されるノード情報を、前記ノード情報記憶手段から削除するノード情報削除手段と、
を備えることを特徴とするノード装置。
【請求項２】
請求項１に記載のノード装置において、
前記ノード情報削除手段は、新たなノード装置により管理されるノード情報に示されたノード装置から、当該ノード情報の削除要求情報を受信したとき、前記ノード情報記憶手段から当該受信した削除要求情報に示されるノード情報を削除することを特徴とするノード装置。
【請求項３】
請求項１に記載のノード装置において、
前記分割決定手段は、自己が管理しなければならないノード情報の量が所定の基準量と同一になるか又はこれより大きくなった場合に、当該ノード情報の一部を分割して新たなノード装置に管理させることを決定することを特徴とするノード装置。
【請求項４】
請求項１乃至３の何れか一項に記載のノード装置において、
前記新たなノード装置に管理させることが決定された場合に、当該新たなノード装置により管理されるノード情報に示されたノード装置に対して、当該ノード情報が新たなノード装置により管理されることを示す管理元変更情報を送信する管理元変更情報送信手段を更に備えることを特徴とするノード装置。
【請求項５】
請求項４に記載のノード装置において、
前記配信情報には固有の識別情報が対応付けられ、且つ、当該識別情報が１の前記ノード装置から送出された場合、当該識別情報は他の１又は複数の前記ノード装置により、当該識別情報が対応付けられた配信情報に対応する前記ノード情報を管理するノード装置まで転送されるものであって、
前記管理元変更情報送信手段は、前記新たなノード装置に管理させることが決定された場合に、当該新たなノード装置により管理されるノード情報に対応する配信情報に対応付けられるべき新たな識別情報を取得し、当該新たな識別情報が含まれる前記管理元変更情報を前記ノード装置に対して送信することを特徴とするノード装置。
【請求項６】
請求項１乃至５の何れか一項に記載のノード装置において、
前記ノード情報記憶手段に記憶される各前記ノード情報に示されたノード装置の所属情報であって、前記ネットワークにおいて属するネットワーク接続グループを示す所属情報を取得する所属情報取得手段と、を更に備え、
前記分割決定手段は、同一の前記所属情報を有する前記ノード装置を示すノード情報が、別々のノード装置により管理されるように前記ノード情報の一部を分割することを特徴とするノード装置。
【請求項７】
請求項１乃至５の何れか一項に記載のノード装置において、
前記ノード情報記憶手段に記憶される各前記ノード情報に示されたノード装置のアクセス頻度を示すアクセス頻度情報を取得するアクセス頻度情報取得手段と、を更に備え、
前記分割決定手段は、各前記ノード装置のアクセス頻度情報に基づいて、前記ノード情報に示されるノード装置へのアクセス頻度の合計が、自己と前記新たなノード装置とで均等するように前記ノード情報の一部を分割することを特徴とするノード装置。
【請求項８】
請求項１乃至７の何れか一項に記載のノード装置において、
前記新たなノード装置により管理されるノード情報が削除された後、前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記新たなノード装置により管理されている前記分割されたノード情報を、前記記憶されているノード情報に併合することを決定する併合決定手段を更に備えることを特徴とするノード装置。
【請求項９】
請求項８に記載のノード装置において、
前記併合することが決定された場合に、前記新たなノード装置に対して、当該新たなノード装置により管理されている前記分割されたノード情報を元のノード情報に併合することを示す併合情報を送信する併合情報送信手段を更に備えることを特徴とするノード装置。
【請求項１０】
請求項８又は９に記載のノード装置において、
前記併合決定手段は、前記ノード情報が複数回分割されている場合、当該複数回の分割のうち最近分割されたノード情報を元のノード情報に併合することを決定することを特徴とするノード装置。
【請求項１１】
ネットワークを介して互いに通信可能な複数のノード装置を備えた情報配信システムであって、少なくとも１の配信情報が複製され複数の前記ノード装置に保存されていく情報配信システムにおいて前記複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するノード装置であって、
同一の前記配信情報に対応する前記ノード情報は分割されて複数のノード装置により管理されており、
前記ノード情報を記憶するノード情報記憶手段と、
前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、他の前記ノード装置により管理されている前記同一の配信情報に対応するノード情報を、前記記憶されているノード情報に併合することを決定する併合決定手段と、
を備えることを特徴とするノード装置。
【請求項１２】
請求項４に記載のノード装置から送信された管理元変更情報を受信するノード装置であって、
前記受信された管理元変更情報に示される新たなノード装置に対して、自己の前記ノード情報を含む登録要求情報を送信する登録要求情報送信手段を備えることを特徴とするノード装置。
【請求項１３】
請求項５に記載のノード装置から送信された管理元変更情報を受信するノード装置であって、
前記受信された管理元変更情報に含まれる前記新たな識別情報を、自己の前記ノード情報を含む登録要求情報と共に、前記新たなノード装置に向けて送信する登録要求情報送信手段を備えることを特徴とするノード装置。
【請求項１４】
請求項１３に記載のノード装置において、
前記登録要求情報は、前記新たなノード装置に至るまでの転送経路におけるノード装置においても前記ノード情報を登録する要求であることを特徴とするノード装置。
【請求項１５】
請求項５に記載のノード装置から送信された管理元変更情報を受信するノード装置であって、
前記配信情報には固有の識別情報が対応付けられ、且つ、当該識別情報が１の前記ノード装置から送出された場合、当該識別情報は他の１又は複数の前記ノード装置により、当該識別情報が対応付けられた配信情報に対応する前記ノード情報を管理するノード装置まで転送されるものであって、
前記管理元変更情報を送信した前記ノード装置により管理されるノード情報に対応する配信情報に対応付けられた識別情報を、自己の前記ノード情報の削除要求情報と共に、当該ノード装置に向けて送信する削除要求情報送信手段を備えることを特徴とするノード装置。
【請求項１６】
請求項１５に記載のノード装置において、
前記削除要求情報は、前記管理元変更情報を送信した前記ノード装置に至るまでの転送経路におけるノード装置において前記ノード情報を削除する要求であることを特徴とするノード装置。
【請求項１７】
請求項９又は１０に記載のノード装置から送信された併合情報を受信するノード装置であって、
前記ノード情報を記憶するノード情報記憶手段と、
前記併合情報に対応する前記ノード情報に示されたノード装置に対して、当該ノード情報が元のノード装置により管理されることを示す管理元変更情報を送信する管理元変更情報送信手段と、
前記併合情報に対応する前記ノード情報を削除するノード情報削除手段と、
を備えることを特徴とするノード装置。
【請求項１８】
請求項１７に記載のノード装置において、
前記管理元変更情報送信手段は、前記記憶されている前記併合情報に対応する前記ノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記併合情報に対応する前記ノード情報に示されたノード装置に対して、前記管理元変更情報を送信し、
前記ノード情報削除手段は、前記記憶されている前記併合情報に対応する前記ノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記併合情報に対応する前記ノード情報を削除することを特徴とするノード装置。
【請求項１９】
請求項１７に記載のノード装置において、
前記併合情報に対応するノード情報の一部が更に分割されて更に他のノード装置に管理されている場合であって、且つ、当該併合情報に対応するノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記更に分割されたノード情報を、前記併合情報に対応するノード情報に併合することを決定する併合決定手段と、
前記更に分割されたノード情報を前記併合情報に対応するノード情報に併合して記憶するノード情報記憶手段と、を更に備え、
前記管理元変更情報送信手段は、前記併合後の前記併合情報に対応するノード情報に示されたノード装置に対して、前記管理元変更情報を送信し、
前記ノード情報削除手段は、前記併合後の前記併合情報に対応する前記ノード情報を削除することを特徴とするノード装置。
【請求項２０】
請求項１７乃至１９の何れか一項に記載のノード装置から送信された管理元変更情報を受信するノード装置であって、
前記受信された管理元変更情報に示される元のノード装置に対して、自己の前記ノード情報を含む登録要求情報を送信する登録要求情報送信手段を備えることを特徴とするノード装置。
【請求項２１】
請求項１７乃至１９の何れか一項に記載のノード装置から送信された管理元変更情報を受信するノード装置であって、
前記配信情報には固有の識別情報が対応付けられ、且つ、当該識別情報が１の前記ノード装置から送出された場合、当該識別情報は他の１又は複数の前記ノード装置により、当該識別情報が対応付けられた配信情報に対応する前記ノード情報を管理するノード装置まで転送されるものであって、
前記元のノード装置により管理される前記ノード情報に対応する配信情報に対応付けられた識別情報を、自己の前記ノード情報の登録要求情報と共に、当該元のノード装置に向けて送信する登録要求情報送信手段を備えることを特徴とするノード装置。
【請求項２２】
請求項２１に記載のノード装置において、
前記登録要求情報は、前記元のノード装置に至るまでの転送経路におけるノード装置においても前記ノード情報を登録する要求であることを特徴とするノード装置。
【請求項２３】
請求項１７乃至１９の何れか一項に記載のノード装置から送信された管理元変更情報を受信するノード装置であって、
前記配信情報には固有の識別情報が対応付けられ、且つ、当該識別情報が１の前記ノード装置から送出された場合、当該識別情報は他の１又は複数の前記ノード装置により、当該識別情報が対応付けられた配信情報に対応する前記ノード情報を管理するノード装置まで転送されるものであって、
前記管理元変更情報を送信した前記ノード装置により管理されるノード情報に対応する配信情報に対応付けられた識別情報を、自己の前記ノード情報の削除要求情報と共に、当該ノード装置に向けて送信する削除要求情報送信手段を備えることを特徴とするノード装置。
【請求項２４】
請求項２３に記載のノード装置において、
前記削除要求情報は、前記管理元変更情報を送信した前記ノード装置に至るまでの転送経路におけるノード装置において前記ノード情報を削除する要求であることを特徴とするノード装置。
【請求項２５】
コンピュータを、請求項１乃至２４の何れか一項に記載のノード装置として機能させることを特徴とするノード処理プログラム。
【請求項２６】
ネットワークを介して互いに通信可能な複数のノード装置を備えた情報配信システムであって、少なくとも１の配信情報が複製され複数の前記ノード装置に保存されていく情報配信システムにおいて、
前記複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するノード装置は、
前記ノード情報を記憶するノード情報記憶手段と、
前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより大きくなった場合に、当該ノード情報の一部を分割して新たなノード装置に管理させることを決定する分割決定手段と、
前記新たなノード装置により管理されるノード情報を、前記ノード情報記憶手段から削除するノード情報削除手段と、
前記新たなノード装置に管理させることが決定された場合に、当該新たなノード装置により管理されるノード情報に示されたノード装置に対して、当該ノード情報が新たなノード装置により管理されることを示す管理元変更情報を送信する管理元変更情報送信手段と、を備え、
前記送信された管理元変更情報を受信したノード装置は、
前記受信された管理元変更情報に示される新たなノード装置に対して、自己の前記ノード情報を含む登録要求情報を送信する登録要求情報送信手段を備えることを特徴とする情報配信システム。
【請求項２７】
請求項２６に記載の情報配信システムにおいて、
前記複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するノード装置は、
前記新たなノード装置により管理されるノード情報が削除された後、前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記新たなノード装置により管理されている前記分割されたノード情報を、前記記憶されているノード情報に併合することを決定する併合決定手段と、
前記併合することが決定された場合に、前記新たなノード装置に対して、当該新たなノード装置により管理されている前記分割されたノード情報を元のノード情報に併合することを示す併合情報を送信する併合情報送信手段と、
を更に備え、
前記送信された併合情報を受信したノード装置は、
前記ノード情報を記憶するノード情報記憶手段と、
前記併合情報に対応する前記ノード情報に示されたノード装置に対して、当該ノード情報が元のノード装置により管理されることを示す管理元変更情報を送信する管理元変更情報送信手段と、
前記併合情報に対応する前記ノード情報を削除するノード情報削除手段と、
を備え、
前記送信された管理元変更情報を受信したノード装置は、
前記受信された管理元変更情報に示される元のノード装置に対して、自己の前記ノード情報を含む登録要求情報を送信する登録要求情報送信手段を備えることを特徴とする情報配信システム。
【請求項２８】
ネットワークを介して互いに通信可能な複数のノード装置を備えた情報配信システムにおける情報配信方法であって、少なくとも１の配信情報が複製され複数の前記ノード装置に保存されていく情報配信方法において、
前記複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するノード装置は、
ノード情報を記憶する工程と、
前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより大きくなった場合に、当該ノード情報の一部を分割して新たなノード装置に管理させることを決定する工程と、
前記新たなノード装置により管理されるノード情報を削除する工程と、
前記新たなノード装置に管理させることが決定された場合に、当該新たなノード装置により管理されるノード情報に示されたノード装置に対して、当該ノード情報が新たなノード装置により管理されることを示す管理元変更情報を送信する工程と、を備え、
前記送信された管理元変更情報を受信したノード装置は、
前記受信された管理元変更情報に示される新たなノード装置に対して、自己の前記ノード情報を含む登録要求情報を送信する工程を備える特徴とする情報配信方法。
【請求項２９】
請求項２８に記載の情報配信方法において、
前記複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するノード装置は、
前記新たなノード装置により管理されるノード情報が削除された後、前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記新たなノード装置により管理されている前記分割されたノード情報を、前記記憶されているノード情報に併合することを決定する工程と、
前記併合することが決定された場合に、前記新たなノード装置に対して、当該新たなノード装置により管理されている前記分割されたノード情報を元のノード情報に併合することを示す併合情報を送信する工程と、
を更に備え、
前記送信された併合情報を受信したノード装置は、
前記ノード情報を記憶する工程と、
前記併合情報に対応する前記ノード情報に示されたノード装置に対して、当該ノード情報が元のノード装置により管理されることを示す管理元変更情報を送信する工程と、
前記併合情報に対応する前記ノード情報を削除する工程と、
を備え、
前記送信された管理元変更情報を受信したノード装置は、
前記受信された管理元変更情報に示される元のノード装置に対して、自己の前記ノード情報を含む登録要求情報を送信する工程を備えることを特徴とする情報配信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
ネットワークを介して互いに通信可能な複数のノード装置を備えたピアツーピア（Peer to Peer（P2P））型の情報配信システムであって、少なくとも１の配信情報が複製され複数のノード装置に保存されていく情報配信システム等に関し、特に、複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するための技術分野に関する。
【背景技術】
【０００２】
この種のピアツーピア型の情報配信システムにおいて、１つの配信情報（例えば、コンテンツデータ）に対して複数の複製情報（以下、レプリカという）を用意して、当該システムに参加している複数のノード装置に分散配置（分散保存）させておくことで、対故障性やアクセスの分散性を高める手法が知られている。
【０００３】
このようなレプリカの作成・配置に関する提案として、例えば、特許文献１には、ネットワーク上のあるサービスグループ内で接続されている各機器に存在するレプリカの全体サイズ（全体の情報量）及びその数を参照して、当該サービスグループ内のネットワーク全体でバランスよくレプリカを作成・配置する方法が開示されている。また、特許文献２には、アクセス頻度に応じて動的にレプリカを作成する手法が開示されている。
【０００４】
ところで、非特許文献１に開示されるような分散ハッシュテーブル（以下、ＤＨＴ（Distributed Hash Table）という）を利用した情報配信システムにおいては、レプリカの保存するノード装置（以下、「コンテンツ保持ノード」という）を示すノード情報（例えば、コンテンツ保持ノードのＩＰアドレス及びポート番号が含まれる）をインデックス情報として管理するノード装置（以下、「ルートノード」という）を各コンテンツデータ毎に定め（つまり、コンテンツ毎にルートノードが存在する）、コンテンツデータを取得したいノード装置は、そのレプリカを保存しているノード装置のノード情報を、そのルートノードに問い合わせるようになっている。
【特許文献１】特開２００３−９９３３７号公報
【特許文献２】特開２００３−２１６５２１号公報
【非特許文献１】「分散ハッシュテーブルの軽量な負荷分散手法の検討」  社団法人  電子情報通信学会  信学技報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述したレプリカを例えばアクセス頻度等に応じて動的に増やし続け、多くのコンテンツ保持ノードに保存させていくと、インデックス情報を記憶するルートノードの記憶領域の容量は有限であるため、当該記憶領域が容量オーバーとなり（つまり、それ以上インデックス情報を記憶しておけないという状況に至る）、レプリカを増やしても、これらのレプリカへのアクセス負荷をそれ以上分散できないという問題が生じる。
【０００６】
これに対し、初めから例えば１つのコンテンツデータに対応するコンテンツＩＤを複数用意して、ルートノードを複数定めておくことも考えられる。但しこれには、コンテンツＩＤの決定方法を、コンテンツ自身の持つ情報から各ノード装置がハッシュ値を計算して求めるというＤＨＴの一般的な方法ではなく、システム運営者が、情報配信システムへの投入前に、あらかじめ任意のＩＤ値を決めてコンテンツを投入し、そのコンテンツＩＤを、別途コンテンツリストの配布などにより、全てのノード装置に周知させ、ユーザに当該コンテンツリスト中からコンテンツを選ばせて所望のコンテンツＩＤを決定する、という方法にするという前提がある。コンテンツの投入を、各々のノード装置から自由に行うのではなく、配信元の特別なノード装置から一元管理しつつ行うようなビジネス形態の場合には、この手法が使える。しかし、この場合、例えば、アクセス頻度の低下に伴い、ルートノードへの問合せ効率が悪くなることが想定される。例えば、一方のルートノードへの問合せが多いのに対し、他方のルートノードへの問合せが少ないといった問題が想定される（問合せが少ないルートノードが無駄となり、メンテナンス上も好ましくない）。
【０００７】
本発明は、以上の問題等に鑑みてなされたものであり、インデックス情報量（言い換えれば、記憶領域の容量）に応じて、ルートノードの数を適切に変更することが可能な情報配信システム、情報配信方法、ノード装置、及びノード処理プログラムを提供することを課題とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、請求項１に記載の発明は、ネットワークを介して互いに通信可能な複数のノード装置を備えた情報配信システムであって、少なくとも１の配信情報が複製され複数の前記ノード装置に保存されていく情報配信システムにおいて前記複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するノード装置であって、前記ノード情報を記憶するノード情報記憶手段と、前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより大きくなった場合に、当該ノード情報の一部を分割して新たなノード装置に管理させることを決定する分割決定手段と、前記新たなノード装置により管理されるノード情報を、前記ノード情報記憶手段から削除するノード情報削除手段と、を備えることを特徴とする。
【０００９】
この発明によれば、ノード情報を管理するノード装置（ルートノード）における記憶領域があふれそうになった場合であっても、ノード情報を分割して、当該分割されたノード情報を新たなノード装置に管理させるようにしたので、上記ノード情報の量に応じてルートノードの数を適切に変更することができ、複製された配信情報（レプリカ）の数を増大させても、当該レプリカへのアクセスを分散させることができる。
【００１０】
請求項２に記載の発明は、請求項１に記載のノード装置において、前記ノード情報削除手段は、新たなノード装置により管理されるノード情報に示されたノード装置から、当該ノード情報の削除要求情報を受信したとき、前記ノード情報記憶手段から当該受信した削除要求情報に示されるノード情報を削除することを特徴とする。
【００１１】
この発明によれば、コンテンツ保持ノードからの削除要求情報を受信したとき、新たなルートノードにより管理されるノード情報を削除するようにしたので、誤りなく当該ノード情報を削除することができる。
【００１２】
請求項３に記載の発明は、請求項１に記載のノード装置において、前記分割決定手段は、自己が管理しなければならないノード情報の量が所定の基準量と同一になるか又はこれより大きくなった場合に、当該ノード情報の一部を分割して新たなノード装置に管理させることを決定することを特徴とする。
【００１３】
この発明によれば、自己が管理しなければならないノード情報（つまり、自己がルートノードとして管理するノード情報）のみに関して分割を行うことができる。
【００１４】
請求項４に記載の発明は、請求項１乃至３の何れか一項に記載のノード装置において、前記新たなノード装置に管理させることが決定された場合に、当該新たなノード装置により管理されるノード情報に示されたノード装置に対して、当該ノード情報が新たなノード装置により管理されることを示す管理元変更情報を送信する管理元変更情報送信手段を更に備えることを特徴とする。
【００１５】
この発明によれば、新たなルートノードにより管理されるノード情報に示されたコンテンツ保持ノードに対して、当該ノード情報が新たなルートノードにより管理されることをより確実に通知することができる。
【００１６】
請求項５に記載の発明は、請求項４に記載のノード装置において、前記配信情報には固有の識別情報が対応付けられ、且つ、当該識別情報が１の前記ノード装置から送出された場合、当該識別情報は他の１又は複数の前記ノード装置により、当該識別情報が対応付けられた配信情報に対応する前記ノード情報を管理するノード装置まで転送されるものであって、前記管理元変更情報送信手段は、前記新たなノード装置に管理させることが決定された場合に、当該新たなノード装置により管理されるノード情報に対応する配信情報に対応付けられるべき新たな識別情報を取得し、当該新たな識別情報が含まれる前記管理元変更情報を前記ノード装置に対して送信することを特徴とする。
【００１７】
この発明によれば、新たなルートノードにより管理されるノード情報に示されたコンテンツ保持ノードに対して、当該ノード情報が新たなルートノードにより管理されること及び配信情報の新たな識別情報をより確実に通知することができる。
【００１８】
請求項６に記載の発明は、請求項１乃至５の何れか一項に記載のノード装置において、前記ノード情報記憶手段に記憶される各前記ノード情報に示されたノード装置の所属情報であって、前記ネットワークにおいて属するネットワーク接続グループを示す所属情報を取得する所属情報取得手段と、を更に備え、前記分割決定手段は、同一の前記所属情報を有する前記ノード装置を示すノード情報が、別々のノード装置により管理されるように前記ノード情報の一部を分割することを特徴とする。
【００１９】
この発明によれば、ネットワークの負荷を効果的に分散させることができる。
【００２０】
請求項７に記載の発明は、請求項１乃至５の何れか一項に記載のノード装置において、前記ノード情報記憶手段に記憶される各前記ノード情報に示されたノード装置のアクセス頻度を示すアクセス頻度情報を取得するアクセス頻度情報取得手段と、を更に備え、前記分割決定手段は、各前記ノード装置のアクセス頻度情報に基づいて、前記ノード情報に示されるノード装置へのアクセス頻度の合計が、自己と前記新たなノード装置とで均等するように前記ノード情報の一部を分割することを特徴とする。
【００２１】
この発明によれば、ネットワークの負荷を効果的に分散させることができる。
【００２２】
請求項８に記載の発明は、請求項１乃至７の何れか一項に記載のノード装置において、前記新たなノード装置により管理されるノード情報が削除された後、前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記新たなノード装置により管理されている前記分割されたノード情報を、前記記憶されているノード情報に併合することを決定する併合決定手段を更に備えることを特徴とする。
【００２３】
この発明によれば、コンテンツ保持ノードへの例えばアクセス頻度の低下に伴い、当該コンテンツ保持ノードの数が減少したとしても、分割されたノード情報を併合できるので、上記ノード情報の量に応じてルートノードの数を適切に変更することができ、ルートノードへの問合せ効率が悪くなることがない。
【００２４】
請求項９に記載の発明は、請求項８に記載のノード装置において、前記併合することが決定された場合に、前記新たなノード装置に対して、当該新たなノード装置により管理されている前記分割されたノード情報を元のノード情報に併合することを示す併合情報を送信する併合情報送信手段を更に備えることを特徴とする。
【００２５】
請求項１０に記載の発明は、請求項８又は９に記載のノード装置において、前記併合決定手段は、前記ノード情報が複数回分割されている場合、当該複数回の分割のうち最近分割されたノード情報を元のノード情報に併合することを決定することを特徴とする。
【００２６】
この発明によれば、ノード情報が複数回分割されている場合であっても、より効率よくノード情報を併合することができる。
【００２７】
請求項１１に記載の発明は、ネットワークを介して互いに通信可能な複数のノード装置を備えた情報配信システムであって、少なくとも１の配信情報が複製され複数の前記ノード装置に保存されていく情報配信システムにおいて前記複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するノード装置であって、同一の前記配信情報に対応する前記ノード情報は分割されて複数のノード装置により管理されており、前記ノード情報を記憶するノード情報記憶手段と、前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、他の前記ノード装置により管理されている前記同一の配信情報に対応するノード情報を、前記記憶されているノード情報に併合することを決定する併合決定手段と、を備えることを特徴とする。
【００２８】
この発明によれば、コンテンツ保持ノードへの例えばアクセス頻度の低下に伴い、当該コンテンツ保持ノードの数が減少したとしても、分割されたノード情報を併合できるので、上記ノード情報の量に応じてルートノードの数を適切に変更することができ、ルートノードへの問合せ効率が悪くなることがない。
【００２９】
請求項１２に記載の発明は、請求項４に記載のノード装置から送信された管理元変更情報を受信するノード装置であって、前記受信された管理元変更情報に示される新たなノード装置に対して、自己の前記ノード情報を含む登録要求情報を送信する登録要求情報送信手段を備えることを特徴とする。
【００３０】
この発明によれば、新たなルートノードは、分割された夫々のノード情報に示されるコンテンツ保持ノードから、ノード情報の登録要求情報を確実に受けることができる。
【００３１】
請求項１３に記載の発明は、請求項５に記載のノード装置から送信された管理元変更情報を受信するノード装置であって、前記受信された管理元変更情報に含まれる前記新たな識別情報を、自己の前記ノード情報を含む登録要求情報と共に、前記新たなノード装置に向けて送信する登録要求情報送信手段を備えることを特徴とする。
【００３２】
この発明によれば、新たなルートノードは、分割された夫々のノード情報に示されるコンテンツ保持ノードから、新たな識別情報及びノード情報の登録要求情報を確実に受けることができる。
【００３３】
請求項１４に記載の発明は、請求項１３に記載のノード装置において、前記登録要求情報は、前記新たなノード装置に至るまでの転送経路におけるノード装置においても前記ノード情報を登録する要求であることを特徴とする。
【００３４】
この発明によれば、新たなルートノードに至るまでの転送経路におけるノード装置においても新たなルートノードに管理されるノード情報を管理させることができる。
【００３５】
請求項１５に記載の発明は、請求項５に記載のノード装置から送信された管理元変更情報を受信するノード装置であって、前記配信情報には固有の識別情報が対応付けられ、且つ、当該識別情報が１の前記ノード装置から送出された場合、当該識別情報は他の１又は複数の前記ノード装置により、当該識別情報が対応付けられた配信情報に対応する前記ノード情報を管理するノード装置まで転送されるものであって、前記管理元変更情報を送信した前記ノード装置により管理されるノード情報に対応する配信情報に対応付けられた識別情報を、自己の前記ノード情報の削除要求情報と共に、当該ノード装置に向けて送信する削除要求情報送信手段を備えることを特徴とする。
【００３６】
この発明によれば、元のルートノードは、分割された夫々のノード情報に示されるコンテンツ保持ノードから、ノード情報の削除要求情報を確実に受けることができる。
【００３７】
請求項１６に記載の発明は、請求項１５に記載のノード装置において、前記削除要求情報は、前記管理元変更情報を送信した前記ノード装置に至るまでの転送経路におけるノード装置において前記ノード情報を削除する要求であることを特徴とする。
【００３８】
この発明によれば、元のルートノードに至るまでの転送経路におけるノード装置において管理される不要となったノード情報をも確実に削除することができる。
【００３９】
請求項１７に記載の発明は、請求項９又は１０に記載のノード装置から送信された併合情報を受信するノード装置であって、前記ノード情報を記憶するノード情報記憶手段と、前記併合情報に対応する前記ノード情報に示されたノード装置に対して、当該ノード情報が元のノード装置により管理されることを示す管理元変更情報を送信する管理元変更情報送信手段と、前記併合情報に対応する前記ノード情報を削除するノード情報削除手段と、を備えることを特徴とする。
【００４０】
この発明によれば、新たなルートノードにより管理されるノード情報に示されたコンテンツ保持ノードに対して、当該ノード情報が併合により元のルートノードにより管理されることをより確実に通知することができる。
【００４１】
請求項１８に記載の発明は、請求項１７に記載のノード装置において、前記管理元変更情報送信手段は、前記記憶されている前記併合情報に対応する前記ノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記併合情報に対応する前記ノード情報に示されたノード装置に対して、前記管理元変更情報を送信し、前記ノード情報削除手段は、前記記憶されている前記併合情報に対応する前記ノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記併合情報に対応する前記ノード情報を削除することを特徴とする。
【００４２】
この発明によれば、新たなルートノードは、併合情報を受信した場合であっても、自己が管理するノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記管理元変更情報を送信するので、ノード情報の併合を無理なく行わせることができる。
【００４３】
請求項１９に記載の発明は、請求項１７に記載のノード装置において、前記併合情報に対応するノード情報の一部が更に分割されて更に他のノード装置に管理されている場合であって、且つ、当該併合情報に対応するノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記更に分割されたノード情報を、前記併合情報に対応するノード情報に併合することを決定する併合決定手段と、前記更に分割されたノード情報を前記併合情報に対応するノード情報に併合して記憶するノード情報記憶手段と、を更に備え、前記管理元変更情報送信手段は、前記併合後の前記併合情報に対応するノード情報に示されたノード装置に対して、前記管理元変更情報を送信し、前記ノード情報削除手段は、前記併合後の前記併合情報に対応する前記ノード情報を削除することを特徴とする。
【００４４】
この発明によれば、新たなルートノードは、併合情報を受信した場合であっても、自己が管理するノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記管理元変更情報を送信するので、ノード情報の併合を無理なく行わせることができる。
【００４５】
請求項２０に記載の発明は、請求項１７乃至１９の何れか一項に記載のノード装置から送信された管理元変更情報を受信するノード装置であって、前記受信された管理元変更情報に示される元のノード装置に対して、自己の前記ノード情報を含む登録要求情報を送信する登録要求情報送信手段を備えることを特徴とする。
【００４６】
この発明によれば、元のルートノードは、分割された夫々のノード情報に示されるコンテンツ保持ノードから、ノード情報の登録要求情報を確実に受けることができる。
【００４７】
請求項２１に記載の発明は、請求項１７乃至１９の何れか一項に記載のノード装置から送信された管理元変更情報を受信するノード装置であって、前記配信情報には固有の識別情報が対応付けられ、且つ、当該識別情報が１の前記ノード装置から送出された場合、当該識別情報は他の１又は複数の前記ノード装置により、当該識別情報が対応付けられた配信情報に対応する前記ノード情報を管理するノード装置まで転送されるものであって、前記元のノード装置により管理される前記ノード情報に対応する配信情報に対応付けられた識別情報を、自己の前記ノード情報の登録要求情報と共に、当該元のノード装置に向けて送信する登録要求情報送信手段を備えることを特徴とする。
【００４８】
この発明によれば、元のルートノードは、分割された夫々のノード情報に示されるコンテンツ保持ノードから、ノード情報の登録要求情報を確実に受けることができる。
【００４９】
請求項２２に記載の発明は、請求項２１に記載のノード装置において、前記登録要求情報は、前記元のノード装置に至るまでの転送経路におけるノード装置においても前記ノード情報を登録する要求であることを特徴とする。
【００５０】
この発明によれば、元のルートノードに至るまでの転送経路におけるノード装置においても元のルートノードに管理されるノード情報を管理させることができる。
【００５１】
請求項２３に記載の発明は、請求項１７乃至１９の何れか一項に記載のノード装置から送信された管理元変更情報を受信するノード装置であって、前記配信情報には固有の識別情報が対応付けられ、且つ、当該識別情報が１の前記ノード装置から送出された場合、当該識別情報は他の１又は複数の前記ノード装置により、当該識別情報が対応付けられた配信情報に対応する前記ノード情報を管理するノード装置まで転送されるものであって、前記管理元変更情報を送信した前記ノード装置により管理されるノード情報に対応する配信情報に対応付けられた識別情報を、自己の前記ノード情報の削除要求情報と共に、当該ノード装置に向けて送信する削除要求情報送信手段を備えることを特徴とする。
【００５２】
この発明によれば、新たなルートノードは、分割された夫々のノード情報に示されるコンテンツ保持ノードから、ノード情報の削除要求情報を確実に受けることができる。
【００５３】
請求項２４に記載の発明は、請求項２３に記載のノード装置において、前記削除要求情報は、前記管理元変更情報を送信した前記ノード装置に至るまでの転送経路におけるノード装置において前記ノード情報を削除する要求であることを特徴とする。
【００５４】
この発明によれば、新たなルートノードに至るまでの転送経路におけるノード装置において管理される不要となったノード情報をも確実に削除することができる。
【００５５】
請求項２５に記載のノード処理プログラムは、コンピュータを、請求項１乃至２４の何れか一項に記載のノード装置として機能させることを特徴とする。
【００５６】
請求項２６に記載の発明は、ネットワークを介して互いに通信可能な複数のノード装置を備えた情報配信システムであって、少なくとも１の配信情報が複製され複数の前記ノード装置に保存されていく情報配信システムにおいて、前記複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するノード装置は、前記ノード情報を記憶するノード情報記憶手段と、前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより大きくなった場合に、当該ノード情報の一部を分割して新たなノード装置に管理させることを決定する分割決定手段と、前記新たなノード装置により管理されるノード情報を、前記ノード情報記憶手段から削除するノード情報削除手段と、前記新たなノード装置に管理させることが決定された場合に、当該新たなノード装置により管理されるノード情報に示されたノード装置に対して、当該ノード情報が新たなノード装置により管理されることを示す管理元変更情報を送信する管理元変更情報送信手段と、を備え、前記送信された管理元変更情報を受信したノード装置は、前記受信された管理元変更情報に示される新たなノード装置に対して、自己の前記ノード情報を含む登録要求情報を送信する登録要求情報送信手段を備えることを特徴とする。
【００５７】
請求項２７に記載の発明は、請求項２６に記載の情報配信システムにおいて、前記複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するノード装置は、前記新たなノード装置により管理されるノード情報が削除された後、前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記新たなノード装置により管理されている前記分割されたノード情報を、前記記憶されているノード情報に併合することを決定する併合決定手段と、前記併合することが決定された場合に、前記新たなノード装置に対して、当該新たなノード装置により管理されている前記分割されたノード情報を元のノード情報に併合することを示す併合情報を送信する併合情報送信手段と、を更に備え、前記送信された併合情報を受信したノード装置は、前記ノード情報を記憶するノード情報記憶手段と、前記併合情報に対応する前記ノード情報に示されたノード装置に対して、当該ノード情報が元のノード装置により管理されることを示す管理元変更情報を送信する管理元変更情報送信手段と、前記併合情報に対応する前記ノード情報を削除するノード情報削除手段と、を備え、前記送信された管理元変更情報を受信したノード装置は、前記受信された管理元変更情報に示される元のノード装置に対して、自己の前記ノード情報を含む登録要求情報を送信する登録要求情報送信手段を備えることを特徴とする。
【００５８】
請求項２８に記載の発明は、ネットワークを介して互いに通信可能な複数のノード装置を備えた情報配信システムにおける情報配信方法であって、少なくとも１の配信情報が複製され複数の前記ノード装置に保存されていく情報配信方法において、前記複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するノード装置は、ノード情報を記憶する工程と、前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより大きくなった場合に、当該ノード情報の一部を分割して新たなノード装置に管理させることを決定する工程と、前記新たなノード装置により管理されるノード情報を削除する工程と、前記新たなノード装置に管理させることが決定された場合に、当該新たなノード装置により管理されるノード情報に示されたノード装置に対して、当該ノード情報が新たなノード装置により管理されることを示す管理元変更情報を送信する工程と、を備え、前記送信された管理元変更情報を受信したノード装置は、前記受信された管理元変更情報に示される新たなノード装置に対して、自己の前記ノード情報を含む登録要求情報を送信する工程を備える特徴とする。
【００５９】
請求項２９に記載の発明は、請求項２８に記載の情報配信方法において、前記複製された夫々の配信情報を保存するノード装置を示すノード情報を管理するノード装置は、前記新たなノード装置により管理されるノード情報が削除された後、前記記憶されているノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、前記新たなノード装置により管理されている前記分割されたノード情報を、前記記憶されているノード情報に併合することを決定する工程と、前記併合することが決定された場合に、前記新たなノード装置に対して、当該新たなノード装置により管理されている前記分割されたノード情報を元のノード情報に併合することを示す併合情報を送信する工程と、を更に備え、前記送信された併合情報を受信したノード装置は、前記ノード情報を記憶する工程と、前記併合情報に対応する前記ノード情報に示されたノード装置に対して、当該ノード情報が元のノード装置により管理されることを示す管理元変更情報を送信する工程と、前記併合情報に対応する前記ノード情報を削除する工程と、を備え、前記送信された管理元変更情報を受信したノード装置は、前記受信された管理元変更情報に示される元のノード装置に対して、自己の前記ノード情報を含む登録要求情報を送信する工程を備えることを特徴とする。
【発明の効果】
【００６０】
本発明によれば、ルートノードにおける記憶領域があふれそうになった場合であっても、ノード情報を分割して、当該分割されたノード情報を新たなノード装置に管理させるようにしたので、上記ノード情報の量に応じてルートノードの数を適切に変更することができ、レプリカの数を増大させても、当該レプリカへのアクセスを分散させることができる。
【００６１】
また、コンテンツ保持ノードへの例えばアクセス頻度の低下に伴い、当該コンテンツ保持ノードの数が減少したとしても、分割されたノード情報を併合できるので、上記ノード情報の量に応じてルートノードの数を適切に変更することができ、ルートノードへの問合せ効率が悪くなることがない。
【発明を実施するための最良の形態】
【００６２】
以下、本発明の最良の実施形態を図面に基づいて説明する。なお、以下に説明する実施の形態は、コンテンツ配信システムに対して本発明を適用した場合の実施形態である。
【００６３】
［１．コンテンツ配信システムの構成等］
始めに、図１を参照して、情報配信システムの一例としてのコンテンツ配信システムの概要構成等について説明する。
【００６４】
図１は、本実施形態に係るコンテンツ配信システムにおける各ノード装置の接続態様の一例を示す図である。
【００６５】
図１の下部枠１０１内に示すように、ＩＸ（Internet eＸchange）３、ＩＳＰ（Internet Service Provider）４ａ,４ｂ、ＤＳＬ（Digital Subscriber Line）回線事業者（の装置）５ａ,５ｂ、ＦＴＴＨ（Fiber To The Home）回線事業者（の装置）６、及び通信回線（例えば、電話回線や光ケーブル等）７等によって、インターネット等のネットワーク（現実世界の通信ネットワーク）８が構築されている。なお、図１の例におけるネットワーク（通信ネットワーク）８には、データ（パケット）を転送するためのルータが、適宜挿入されているが図示を省略している。
【００６６】
コンテンツ配信システムＳは、このようなネットワーク８を介して相互に接続された複数のノード装置（以下、単に、「ノード」という）ｎ１，ｎ２・・・ｎ２１を備えて構成されることになり、ピアツーピア方式のネットワークシステムとなっている（なお、実際には、これ以上のノードが存在することになる）。また、各ノードｎ１〜ｎ２１には、固有の製造番号及びＩＰ（Internet Protocol）アドレス（グローバルＩＰアドレス）が割り当てられている。なお、製造番号及びＩＰアドレスは、複数のノード間で重複しないものである。
【００６７】
また、コンテンツ配信システムＳは、コンテンツ管理サーバ２ａ及びコンテンツリスト管理サーバ２ｂを備える。
【００６８】
そして、このコンテンツ配信システムＳにおいては、特定のアルゴリズム、例えば、ＤＨＴを利用したアルゴリズムによって、図１の上部枠１００内に示すような、オーバーレイネットワーク９が構築されることになる。つまり、このオーバーレイネットワーク９は、既存のネットワーク８を用いて形成された仮想的なリンクを構成するネットワーク（論理的なネットワーク）を意味する。
【００６９】
本実施形態においては、ＤＨＴを利用したアルゴリズムによって構築されたオーバーレイネットワーク９を前提としており、このオーバーレイネットワーク９（図１の上部枠１００内）に配置されたノードｎ１〜ｎ１５を、オーバーレイネットワーク９に参加しているノードｎｎという。言い換えれば、オーバーレイネットワーク９は、ノードｎｎの参加により形成されている。このようなオーバーレイネットワーク９への参加は、参加していないノードｎ１６〜ｎ２１が、参加している任意のノードｎｎに対して参加要求を示す参加要求情報としての参加メッセージを送信することによって行われる。
【００７０】
また、各ノードｎｎは、固有の識別情報としてのノードＩＤを有しており、当該ノードＩＤは、例えば、ＩＰアドレスあるいは製造番号を共通のハッシュ関数（例えば、ＳＨＡ−１等）によりハッシュ化した値（例えば、ｂｉｔ長が１６０ｂｉｔ）であり、一つのＩＤ空間に偏りなく分散して配置されることになる。
【００７１】
このように共通のハッシュ関数により求められた（ハッシュ化された）ノードＩＤは、当該ＩＰアドレスあるいは製造番号が異なれば、同じ値になる確率が極めて低いものである。なお、ハッシュ関数については公知であるので詳しい説明を省略する。
【００７２】
また、各ノードｎｎは、夫々、ＤＨＴを保持している。このＤＨＴは、オーバーレイネットワーク９上における各種メッセージの転送先を規定しており、具体的には、ノードＩＤ空間内で適度に離れたノードｎｎのノードＩＤとそのＩＰアドレス及びポート番号等の組が複数登録されたルーティングテーブル（転送先テーブル）が含まれている。
【００７３】
図２は、ノードｎ１が保持するＤＨＴのルーティングテーブルの一例を示す図であり、図３は、ＤＨＴのノードＩＤ空間の一例を示す概念図である。
【００７４】
なお、図２及び図３の例においては、説明の便宜上、ノードＩＤのｂｉｔ長を２ｂｉｔ×３桁＝６ｂｉｔとし、各桁を４進数（０〜３の整数）で表している（実際には、もっと長いｂｉｔ長を用い、各桁も例えば４ｂｉｔに区切って０〜ｆの１６進数で表現する）。
【００７５】
図２の例において、ＤＨＴのルーティングテーブルは、レベル１〜レベル３のテーブルからなり（複数のレベルに区分されており）、各レベルのテーブルエントリーには、エリア毎に、ノードＩＤとこれに対応するノードｎｎのＩＰアドレス及びポート番号が対応付けられて登録されている。各レベルのテーブルにおける各エリアは、ＤＨＴのノードＩＤ空間を分割することにより得られるエリアである。例えば、図３に示すように、レベル１では、ＤＨＴのノードＩＤ空間全体が４分割され、“０００”〜“０３３”のノードＩＤが存在するエリアを０ＸＸのエリア、“１００”〜“１３３” のノードＩＤが存在するエリアを１ＸＸのエリア、“２００”〜“２３３” のノードＩＤが存在するエリアを２ＸＸのエリア、“３００”〜“３３３” のノードＩＤが存在するエリアを３ＸＸのエリアとする。また、レベル２では、レベル１のエリア（つまり、０ＸＸ〜３ＸＸのエリア）が更に４分割、例えば１ＸＸのエリアが４分割され、“１００”〜“１０３” のノードＩＤが存在するエリアを１０Ｘのエリア、“１１０”〜“１１３” のノードＩＤが存在するエリアを１１Ｘのエリア、“１２０”〜“１２３” のノードＩＤが存在するエリアを１２Ｘのエリア、“１３０”〜“１３３” のノードＩＤが存在するエリアを１３Ｘのエリアとする。
【００７６】
そして、例えば、ノードｎ１のノードＩＤが“１２２”とすると、図２に示すように、かかるノードｎ１のレベル１における１ＸＸのエリア（自己（つまり、自ノード）が存在するエリア）のテーブルには、自己のノードＩＤ及びＩＰアドレス（ＩＰアドレスは自分のものであるので、当該ルーティングテーブルに登録しなくても良い）等が登録され、自己が存在しないエリア（つまり、０ＸＸのエリア、２ＸＸのエリア、及び３ＸＸのエリア）には、夫々、他の任意のノードｎｎのノードＩＤ及びＩＰアドレス等が登録されている。
【００７７】
また、かかるノードｎ１のレベル２における１２Ｘのエリア（自己が存在するエリア）のテーブルには、図２に示すように、自己のノードＩＤ及びＩＰアドレス（ＩＰアドレスは自分のものであるので、当該ルーティングテーブルに登録しなくても良い）等が登録され、自己が存在しないエリア（つまり、１０Ｘのエリア、１１Ｘのエリア、及び１３Ｘのエリア）等には、夫々、他の任意のノードｎｎのノードＩＤ及びＩＰアドレス等が登録されている。
【００７８】
更に、かかるノードｎ１のレベル３には、図２に示すように、ノードＩＤが“１２０”〜“１２２”のノードＩＤ及びＩＰアドレス（ＩＰアドレスは自分のものであるので、当該ルーティングテーブルに登録しなくても良い）等が登録されている。
【００７９】
なお、図２及び図３の例では、ノードＩＤのｂｉｔ長を３桁×２ｂｉｔとしたので、レベル１〜３の３レベル分のテーブルで網羅できるが、ノードＩＤのｂｉｔ長が増せば、その分のテーブルが必要となる（例えば、ノードＩＤのｂｉｔ長を１６桁×４ｂｉｔとした場合、１６レベル分のテーブルが必要となる）。
【００８０】
このように、本実施形態におけるＤＨＴのルーティングテーブルでは、レベルが上がるほど、エリアが狭まっていくようになっている。
【００８１】
このようなＤＨＴは、未参加のノードがオーバーレイネットワーク９に参加する際に与えられることになる。
【００８２】
ところで、オーバーレイネットワーク９においては、様々なコンテンツ（例えば、映画や音楽等）データ（配信情報の一例）のレプリカが複数のノードｎｎに分散して保存（格納）されている。例えば、ノードｎ１及びノードｎ４には、タイトルがＸＸＸの映画のコンテンツデータのレプリカが保存されており、一方、ノードｎ２及びノードｎ３には、タイトルがＹＹＹの映画のコンテンツデータのレプリカが保存されるというように、複数のコンテンツ保持ノードであるノードｎｎに分散されて保存される。また、これらのコンテンツデータのレプリカには、夫々、コンテンツ名（タイトル）及びコンテンツＩＤ（コンテンツ毎に固有の識別情報）等の情報が付加されている。このコンテンツＩＤは、例えば、コンテンツ名＋任意の数値（或いは、当該コンテンツデータの先頭数バイトでも良い）が、上記ノードＩＤを得るときと共通のハッシュ関数によりハッシュ化されて生成される（ノードＩＤと同一のＩＤ空間に配置）。あるいは、システム運営者が、コンテンツ毎に一意のＩＤ値（ノードＩＤと同一ビット長）を付与しても良い。この場合は、コンテンツのタイトル等とそのコンテンツＩＤの対応が書かれた「コンテンツリスト」を、全ノードｎｎに配布する。
【００８３】
また、このように分散保存されているコンテンツデータのレプリカの所在を示すインデックス情報（当該レプリカを保存している各コンテンツ保持ノードのノード情報（ＩＰアドレス及びポート番号等）を含む）は、上述したように、ルートノードにより管理されるようになっている。例えば、タイトルがＸＸＸの映画のコンテンツデータのレプリカのインデックス情報は、そのコンテンツ（コンテンツＩＤ）のルートノードであるノードｎ１３により管理され、タイトルがＹＹＹの映画のコンテンツデータのレプリカのインデックス情報は、そのコンテンツ（コンテンツＩＤ）のルートノードであるノードｎ１４により管理される。つまり、コンテンツ毎にルートノードが分けられるので負荷分散が図らており、しかも、同一のコンテンツデータ（コンテンツＩＤが同一）のレプリカが、夫々、複数のコンテンツ保持ノードに保存されている場合であっても、かかるコンテンツデータのレプリカのインデックス情報は、１つのルートノードで管理することができる。また、このようなルートノードは、例えば、コンテンツＩＤと最も近い（例えば、上位桁がより多く一致する）ノードＩＤを有するノードｎｎであるように定められる。
【００８４】
そして、コンテンツデータのレプリカの分散保存の制御は、例えば、コンテンツ管理サーバ２ａにより行われる（なお、システム運営者により選定された常にオーバーレイネットワーク９に参加している信頼性の高いノードｎｎにより行われるようにしても良い）。例えば、コンテンツ管理サーバ２ａは、定期的に、コンテンツデータ（コンテンツ保持ノード）へのアクセス頻度やコンテンツデータの人気度を集計（例えば、各ルートノード及び各コンテンツ保持ノードから集計）して、コンテンツ毎に、保存させるレプリカの数を増減させるか否かを決定する。そして、コンテンツ管理サーバ２ａは、レプリカを増加させる決定をした場合、レプリカを保存させるべき任意のノードｎｎを選定（例えば、ランダムに選定）し、当該選定したノードｎｎに対してレプリカの保存要求を行い、そのノードｎｎからレプリカの保存を承諾する応答があれば、該当するコンテンツデータを複製してそのレプリカを当該ノードｎｎに対して配信して保存させる。一方、コンテンツ管理サーバ２ａは、レプリカを減少させる決定をした場合、レプリカを保存している任意のノードｎｎを選定（例えば、ルートノードから取得したインデックス情報からランダムに選定）し、当該選定したノードｎｎに対してレプリカの削除要求を行い、そのノードｎｎからレプリカを削除させる。
【００８５】
なお、コンテンツ管理サーバ２ａによりコンテンツデータのレプリカの分散保存の制御が行わなくても良い。例えば、単に、人気の高いコンテンツは、多くのノードｎｎによりダウンロードされるため、そのレプリカは自然に増加する。一方、その後、人気の無くなってきたコンテンツは、ノードｎｎにより削除されるため、そのレプリカは自然に減少する。
【００８６】
このようにしてレプリカを保存したノードｎｎ（コンテンツ保持ノード）は、当該レプリカを保存したことをそのルートノードに知らせるために、そのレプリカに付加されているコンテンツＩＤ及び自己のノード情報（ＩＰアドレス及びポート番号等）が含まれるパブリッシュ（登録通知）メッセージ（レプリカを保存したので、ノード情報の登録の要求を示す登録要求情報）を、そのルートノードに向けて送出する。これにより、パブリッシュメッセージは、コンテンツＩＤをキーとするＤＨＴルーティングによってルートノードに到着することになる。
【００８７】
一方、レプリカを削除したノードｎｎ（コンテンツ保持ノード）は、当該レプリカを削除したことをそのルートノードに知らせるために、そのレプリカに付加されているコンテンツＩＤ及び自己のノード情報が含まれる削除通知メッセージ（レプリカを削除したので、ノード情報の削除の要求を示す削除要求情報）を、そのルートノードに向けて送出する。これにより、削除通知メッセージは、コンテンツＩＤをキーとするＤＨＴルーティングによってルートノードに到着することになる。
【００８８】
図４（Ａ）は、コンテンツ保持ノードから送出されたパブリッシュメッセージの流れの一例を、図４（Ｂ）は、コンテンツ保持ノードから送出された削除通知メッセージの流れの一例を、夫々、ＤＨＴのノードＩＤ空間にて示した概念図である。
【００８９】
図４（Ａ）の例において、例えば、コンテンツ保持ノードであるノードｎ１は、自己のＤＨＴのレベル１のテーブルを参照して、パブリッシュメッセージに含まれるコンテンツＩＤと最も近い（例えば、上位桁がより多く一致する）ノードＩＤを有する例えばノードｎ８のＩＰアドレス及びポート番号を取得し、そのＩＰアドレス及びポート番号宛てに、上記パブリッシュメッセージを送信する。
【００９０】
これに対して、ノードｎ８は、当該パブリッシュメッセージを受信し、自己のＤＨＴのレベル２のテーブルを参照して、当該パブリッシュメッセージに含まれるコンテンツＩＤと最も近い（例えば、上位桁がより多く一致する）ノードＩＤを有する例えばノードｎ１１のＩＰアドレス及びポート番号を取得し、そのＩＰアドレス及びポート番号宛てに、上記パブリッシュメッセージを転送する。
【００９１】
これに対して、ノードｎ１１は、当該パブリッシュメッセージを受信し、自己のＤＨＴのレベル３のテーブルを参照して、当該パブリッシュメッセージに含まれるコンテンツＩＤと最も近い（例えば、上位桁がより多く一致する）ノードＩＤを有する例えばノードｎ１３のＩＰアドレス及びポート番号を取得し、そのＩＰアドレス及びポート番号宛てに、上記パブリッシュメッセージを転送する。
【００９２】
これに対して、ノードｎ１３は、パブリッシュメッセージを受信し、自己のＤＨＴのレベル４のテーブルを参照して、当該パブリッシュメッセージに含まれるコンテンツＩＤと最も近い（例えば、上位桁がより多く一致する）ノードＩＤが自分である、つまり、自分がそのコンテンツＩＤのルートノードであることを認識し、自己のインデックス情報中に、当該パブリッシュメッセージに含まれるノード情報を登録することになる。
【００９３】
なお、パブリッシュメッセージに含まれるノード情報は、コンテンツ保持ノードからルートノードに至るまでの転送経路におけるノードｎｎ（図４（Ａ）の例では、ノードｎ８及びノードｎ１１）においても登録（キャッシュ）される（以下、このように、ノード情報をキャッシュするノードｎｎをキャッシュノードという）。つまり、パブリッシュメッセージは、ルートノードに至るまでの転送経路におけるキャッシュノードにおいても当該ノード情報を登録する要求を示している。
【００９４】
一方、図４（Ｂ）の例における削除通知メッセージの流れは、図４（Ａ）の例におけるパブリッシュメッセージの流れと同様であり、コンテンツ保持ノードであるノードｎ１から送出された削除通知メッセージは、上記コンテンツＩＤのルートノードであるノードｎ１３に至るまで転送され、ノードｎ１３は、自己のインデックス情報中から当該削除通知メッセージに含まれるノード情報を削除することになる。
【００９５】
なお、削除通知メッセージに含まれるノード情報は、コンテンツ保持ノードからルートノードに至るまでの転送経路におけるキャッシュノード（図４（Ａ）の例では、当該ノード情報をキャッシュしているノードｎ８及びノードｎ１１）においても削除される。つまり、削除通知メッセージは、ルートノードに至るまでの転送経路におけるキャッシュノードにおいても当該ノード情報を削除する要求を示している。これにより、ルートノードに至るまでの転送経路におけるキャッシュノードにおいて管理される古いノード情報をも確実に削除することができる。
【００９６】
さて、あるノードｎｎのユーザが、所望するコンテンツデータのレプリカを取得したい場合、当該レプリカを取得するべきノードｎｎ（以下、「ユーザノード」という）は、当該ユーザにより選択（例えば、全てのノードｎｎに配信されているコンテンツリスト（コンテンツ名とコンテンツＩＤ等が記述されており、例えばコンテンツリスト管理サーバ２ｂにて管理される）から選択）されたコンテンツデータのコンテンツＩＤを含むコンテンツ所在問合せ（検索）メッセージを、自己のＤＨＴのルーティングテーブルにしたがって他のノードｎｎに対して送出する。これにより、当該コンテンツ所在問合せメッセージは、上述したパブリッシュメッセージと同様に、コンテンツＩＤをキーとするＤＨＴルーティングによって、いくつかのノードｎｎ（以下、「中継ノード」という）を経由（転送）されて、そのコンテンツＩＤのルートノードに辿り着く。そして、上記ユーザノードは、当該ルートノードから、上述したインデックス情報を取得（受信）し、当該インデックス情報に含まれるノード情報に基づいて上記コンテンツデータのレプリカを保存しているコンテンツ保持ノードに接続し、そこから当該コンテンツデータのレプリカを取得（ダウンロード）することが可能になる。
【００９７】
なお、上記ユーザノードは、コンテンツ所在問合せメッセージがルートノードに辿り着くまでの間に、当該ルートノードと同じノード情報をキャッシュしているキャッシュノードから当該ノード情報を取得（受信）することもできる。
【００９８】
また、上記コンテンツリストは、システム運営者により選定された常にオーバーレイネットワーク９に参加している信頼性の高いノードｎｎにより管理されるようにしても良く（この場合、コンテンツリスト管理サーバ２ｂは必ずしも必要がない）、また、当該コンテンツリストには、コンテンツＩＤが記述されず、各ユーザノードが、コンテンツリストに記述されたコンテンツ名＋任意の数値を、上記ハッシュ関数によりハッシュ化してコンテンツＩＤを生成するように構成しても良い。
【００９９】
ところで、上述したように、レプリカを例えばアクセス頻度等に応じて動的に増やし続け、多くのコンテンツ保持ノードに保存させていくと、インデックス情報を記憶するルートノードの記憶領域（以下、「インデックスキャッシュ領域」という）の容量は有限であるため、当該記憶領域が容量オーバーとなる（あふれる）。
【０１００】
そこで、本実施形態において、ルートノードは、インデックス情報に含まれる全ノード情報の量（例えば、ノード情報のデータ量）が所定の基準量と同一になるか又はこれより大きくなった場合に、当該ノード情報の一部を分割して新たなルートノードに管理させることを決定し、上記インデックス情報から分割に係るノード情報を削除するようになっている。これにより、１のコンテンツついてのインデックス情報は、複数のルートノードによって管理されることになるが、新たなルートノードが、分割に係るノード情報を管理するまでの詳しい流れついては後述する。
【０１０１】
一方、上述したように、レプリカを例えばアクセス頻度等に応じて動的に減らして（コンテンツ保持ノードから削除）いくと、例えばルートノードへの問合せ効率が悪くなる。
【０１０２】
そこで、本実施形態において、元のルートノードは、インデックス情報に含まれる全ノード情報の量が所定の基準量と同一になるか又はこれより小さくなった場合に、上記分割され新たなルートノードにおいて管理されているノード情報を、上記記憶されているノード情報に併合する（元のインデックス情報に戻す）ことを決定するようになっている。なお、元のルートノードが、上記分割に係るノード情報を併合して管理するまでの詳しい流れついては後述する。
【０１０３】
次に、図５を参照して、ノードｎｎの構成及び機能について説明する。
【０１０４】
図５は、ノードｎｎの概要構成例を示す図である。
【０１０５】
ノードｎｎは、図５に示すように、演算機能を有するＣＰＵ，作業用ＲＡＭ，各種データ及びプログラムを記憶するＲＯＭ等から構成されたコンピュータとしての制御部１１と、各種データ（例えば、コンテンツデータのレプリカ、ノード情報、ＤＨＴ）及びプログラム等を記憶保存（格納）するためのＨＤＤ等から構成されたノード情報記憶手段としての記憶部１２と、受信されたコンテンツデータのレプリカを一時蓄積するバッファメモリ１３と、コンテンツデータのレプリカに含まれるエンコードされたビデオデータ（映像情報）及びオーディオデータ（音声情報）等をデコード（データ伸張や復号化等）するデコーダ部１４と、当該デコードされたビデオデータ等に対して所定の描画処理を施しビデオ信号として出力する映像処理部１５と、当該映像処理部１５から出力されたビデオ信号に基づき映像表示するＣＲＴ，液晶ディスプレイ等の表示部１６と、上記デコードされたオーディオデータをアナログオーディオ信号にＤ（Digital）／Ａ（Analog）変換した後これをアンプにより増幅して出力する音声処理部１７と、当該音声処理部１７から出力されたオーディオ信号を音波として出力するスピーカ１８と、ネットワーク８を通じて他のノードｎｎとの間の情報の通信制御を行うための通信部２０と、ユーザからの指示を受け付け当該指示に応じた指示信号を制御部１１に対して与える入力部（例えば、キーボード、マウス、或いは、操作パネル等）２１と、を備えて構成され、制御部１１、記憶部１２、バッファメモリ１３、デコーダ部１４、及び通信部２０は、バス２２を介して相互に接続されている。
【０１０６】
このような構成において、制御部１１は、ＣＰＵが記憶部１２等に記憶されたプログラム（本発明のノード処理プログラムを含む）を読み出して実行することにより、全体を統括制御すると共に、上述したユーザノード、中継ノード、ルートノード、キャッシュノード、及びコンテンツ保持ノードの少なくとも何れか一つのノードとしての処理を行うようになっており、特に、ルートノードの場合、本発明の分割決定手段、所属情報取得手段、アクセス頻度情報取得手段、ノード情報削除手段、管理元変更情報送信手段、併合決定手段、及び併合情報送信手段等として機能し、コンテンツ保持ノードの場合、登録要求情報送信手段、及び削除要求情報送信手段等として機能し、後述する各種処理を行うようになっている。
【０１０７】
なお、上述したインデックスキャッシュ領域は、例えば記憶部１２における記憶領域のうち、数ｋＢ（キロバイト）〜数ＭＢ（メガバイト）が割り当てられる。
【０１０８】
また、上記ノード処理プログラムは、例えば、ネットワーク８上の所定のサーバからダウンロードされるようにしてもよいし、例えば、ＣＤ−ＲＯＭ等の記録媒体に記録されて当該記録媒体のドライブを介して読み込まれるようにしてもよい。
【０１０９】
［２．コンテンツ配信システムの動作］
次に、ノード情報の登録、分割、削除及び併合が行われる際のコンテンツ配信システムＳの動作例について説明する。
【０１１０】
（２−１．ノード情報の登録、分割）
先ず、図６乃至図１１等を参照して、ノード情報の登録、分割が行われる際の動作例について説明する。
【０１１１】
図６は、ノードｎｎにおけるノード情報登録処理の一例を示すフローチャートであり、図７は、ノードｎｎにおけるノード情報分割処理の一例を示すフローチャートであり、図８は、コンテンツリスト管理サーバ２ｂにおけるコンテンツＩＤ発行処理の一例を示すフローチャートであり、図９は、ノードｎｎにおけるコンテンツＩＤ変更処理の一例を示すフローチャートである。また、図１０は、ノード情報の分割が決定された際におけるインデックスキャッシュ領域に記憶されたノード情報の一例を示す図である。図１１は、ノード情報の分割が決定された後の各種メッセージの流れの一例を示す図である。
【０１１２】
図６に示す処理は、任意のノードｎｎが、他のノードｎｎから送信（又は転送）されてきたパブリッシュメッセージを受信した場合に開始される。これが起こるきっかけは、システム運営者が任意のノードｎｎに新規コンテンツを投入（つまり、そのレプリカを保存）した場合や、任意のノードｎｎがコンテンツを視聴して、そのレプリカを自ノードｎｎに作った場合、あるいは後述の、自ノードｎｎにおける既得コンテンツに新たなコンテンツＩＤの付与が行われた場合等に、そのノードｎｎが、当該コンテンツの所在をルートノードに登録しようとして、パブリッシュメッセージを投げたときである。
【０１１３】
先ず、制御部１１は、自己（自分のノード）のＤＨＴのルーティングテーブルを参照して、自己が、当該パブリッシュメッセージに含まれるコンテンツＩＤのルートノードであるか否かを判別する（ステップＳ１）。自己がルートノードでない（言い換えれば、キャッシュノードである）と判別された場合（例えば、自己以外に当該コンテンツＩＤと最も近い（例えば、上位桁がより多く一致する）ノードＩＤを有するノードｎｎがＤＨＴのルーティングテーブルに登録されている場合）には（ステップＳ１：Ｎ）、ステップＳ２へ進み、自己がルートノードであると判別された場合（例えば、自己のノードＩＤが当該コンテンツＩＤと最も近い（例えば、上位桁がより多く一致する）場合）には（ステップＳ１：Ｙ）、ステップＳ３へ進む。
【０１１４】
ステップＳ２では、制御部１１は、記憶部１２におけるインデックスキャッシュ領域（インデックス情報を記憶するためのキャッシュ領域）が満タン（つまり、ノード情報を記憶する空き領域がない）か否かを判別し、満タンでない場合には（ステップＳ２：Ｎ）、ステップＳ４へ進み、満タンである場合には（ステップＳ２：Ｙ）、ステップＳ５へ進む。
【０１１５】
ステップＳ４では、制御部１１は、上記パブリッシュメッセージに含まれるノード情報を上記コンテンツＩＤに対応付けてインデックスキャッシュ領域に記憶（登録）し、ステップＳ５に進む。
【０１１６】
ステップＳ５では、制御部１１は、自己のＤＨＴのルーティングテーブルから、転送先のノードｎｎ（例えば、上記コンテンツＩＤ（“１１１”）と最も近い（例えば、上位桁がより多く一致する）ノードＩＤを有する例えばノードｎｎ）のＩＰアドレス及びポート番号を取得し、そのＩＰアドレス及びポート番号宛てに、上記パブリッシュメッセージを転送し、当該処理を終了する。
【０１１７】
一方、ステップＳ３では、ノードｎｎ（以下、「ルートノードＲ１」という）の制御部１１は、ステップＳ２と同様、記憶部１２におけるインデックスキャッシュ領域が満タンか否かを判別し、満タンでない場合には（ステップＳ３：Ｎ）には、ステップＳ７へ進み、満タンである場合には（ステップＳ３：Ｙ）、ステップＳ６へ進む。
【０１１８】
ステップＳ６では、ルートノードＲ１の制御部１１は、インデックスキャッシュ領域に記憶されているノード情報の中から、予め定められた削除の優先順位にしたがって、例えば削除の優先順位が最も高い１つのノード情報を削除する。例えば、自己がルートノードＲ１として管理するコンテンツＩＤに対応するコンテンツデータのレプリカを保存しているコンテンツ保持ノードのノード情報は、当該削除の優先順位が低く（つまり、削除対象とはしない）、一方、自己がルートノードＲ１として管理しない（言い換えれば、キャッシュノードとして管理する）コンテンツＩＤに対応するコンテンツデータのレプリカを保存しているコンテンツ保持ノードのノード情報は、当該削除の優先順位が高く（つまり、削除対象とする）設定されている。
【０１１９】
更に、自己がルートノードＲ１として管理しないコンテンツＩＤに対応するコンテンツデータのレプリカを保存しているコンテンツ保持ノードのノード情報の中でも、アクセス頻度が少ない（例えば、コンテンツ所在問合せメッセージに応じてユーザノードにノード情報を送信した頻度が少ない）コンテンツデータのレプリカを保存しているコンテンツ保持ノードのノード情報ほど、当該削除の優先順位が高く設定されている。インデックスキャッシュ領域が満タンである場合、かかるステップＳ６に示す処理により、インデックスキャッシュ領域に記憶されたノード情報は、削除の優先順位が高いものから低いものに入れ替わっていくことになる。
【０１２０】
ステップＳ７では、ルートノードＲ１の制御部１１は、上記パブリッシュメッセージに含まれるノード情報を上記コンテンツＩＤに対応付けてインデックスキャッシュ領域に記憶（登録）する。
【０１２１】
次いで、ルートノードＲ１の制御部１１は、上記コンテンツＩＤ（“１１１”）に対応するコンテンツデータのレプリカを保存しているコンテンツ保持ノードの全ノード情報の量（自己（自身）がルートノードとして管理しなければならない（管理すべき）ノード情報の量）が、所定の基準量（例えば、インデックスキャッシュ領域の９０％の記憶量）以上か否かを判別（つまり、コンテンツＩＤ（“１１１”）に対応する全ノード情報が相当数増えたかどうかを判別）する（ステップＳ８）。なお、上記基準量は、特に９０％の量に限定されるものではなく、任意の量を設定可能である。また、基準量を基準数で表し、上記全ノード情報の数が、所定の基準数以上か否かが判別されるように構成しても良い。また、所定の基準量または所定の基準数よりも大きいか否かが判別されるようにしても良い。
【０１２２】
そして、制御部１１は、所定の基準量未満の場合（ステップＳ８：Ｎ）、当該処理を終了し、所定の基準量以上の場合（ステップＳ８：Ｙ）、当該ノード情報の一部（例えば、半分のノード情報）を分割して新たなルートノード（以下、「ルートノードＲ２」という）に管理させることを決定し（ステップＳ９）、ノード情報分割処理を実行する（ステップＳ１０）。
【０１２３】
例えば、図１０に示す例では、上記コンテンツＩＤ（“１１１”）に対応するコンテンツデータのレプリカを保存しているコンテンツ保持ノードの全ノード情報の量が、基準量（例えば、インデックスキャッシュ領域の例えば９０％の記憶量）を超えているため、符号５１部に示す半分のノード情報がルートノードＲ２により管理されることになる。
【０１２４】
ノード情報分割処理においては、図７に示すように、ルートノードＲ１の制御部１１は、例えばオーバーレイネットワーク９への参加の際に取得されたコンテンツリスト管理サーバ２ｂのＩＰアドレス及びポート番号にしたがって、当該コンテンツリスト管理サーバ２ｂに接続し、上記コンテンツＩＤ（“１１１”）に対応するコンテンツデータの新しいコンテンツＩＤの発行を要求する（ステップＳ１１）。
【０１２５】
コンテンツリスト管理サーバ２ｂは、かかるコンテンツＩＤの発行要求を受信すると、図８に示すコンテンツＩＤ発行処理を開始し、コンテンツリスト内に未だ登録されていない、新たなコンテンツＩＤを生成する（ステップＳ２１）。例えば、コンテンツリスト管理サーバ２ｂは、上記コンテンツＩＤ（“１１１”）に対応するコンテンツデータのコンテンツ名“ＸＸＸ”の末尾に数値“２”を付加した“ＸＸＸ２”を上記ハッシュ関数によりハッシュ化してコンテンツＩＤ（例えば“１２１”）を生成し、一時ＲＡＭに記憶しておく。
【０１２６】
次いで、コンテンツリスト管理サーバ２ｂは、生成した新たなコンテンツＩＤ（“１２１”）のルートノード（新たなルートノード）が既に管理しているコンテンツＩＤに対応する全ノード情報の量が例えば上記ステップＳ８における所定の基準量の半分の量未満であるか否かを判別する（ステップＳ２２）。これは、コンテンツＩＤ（“１２１”）のルートノードＲ２が、既に他のコンテンツＩＤのルートノードＲ２である場合も想定され（つまり、当該ルートノードＲ２のノードＩＤが２つ以上のコンテンツＩＤと最も近いという場合も想定される）ため、上記分割に係るノード情報を管理するためのインデックスキャッシュ領域における記憶領域を確保するためである。
【０１２７】
例えば、元のルートノードＲ１が分割を予定している全ノード情報の量＋新たなルートノードが既にルートノードとして管理しているコンテンツＩＤに対応するノード情報の量＜上記所定の基準量（例えば、インデックスキャッシュ領域の９０％の記憶量）である必要がある。従って、元のルートノードＲ１が分割を予定している全ノード情報の量が、例えば、インデックスキャッシュ領域の４５％の記憶量であるとすると、新たなルートノードが既に管理しているコンテンツＩＤに対応するノード情報の量は、インデックスキャッシュ領域の４５％の記憶量未満である必要がある。
【０１２８】
そして、例えば、コンテンツリスト管理サーバ２ｂは、上記所定の基準量の半分の量未満であるか否かの確認メッセージを、コンテンツＩＤ（“１２１”）をキーとするＤＨＴルーティングによって、コンテンツＩＤ（“１２１”）のルートノードＲ２に向けて送信し、当該ルートノードＲ２から上記所定の基準量の半分の量未満であるとの応答メッセージがあった場合には、上記所定の基準量の半分の量未満であると判別し（ステップＳ２２：Ｙ）、ステップＳ２３に進む。これにより、新たなルートノードＲ２において上記分割に係るノード情報を確実に管理させることができる。
【０１２９】
一方、コンテンツリスト管理サーバ２ｂは、当該ルートノードＲ２から上記所定の基準量の半分の量以上であるとの応答メッセージがあった場合、上記所定の基準量の半分の量未満でないと判別し（ステップＳ２２：Ｎ）、上記生成され、ＲＡＭに記憶されたコンテンツＩＤ（“１２１”）を破棄し、ステップＳ２１に戻り、再度、新たなルートノード用のコンテンツＩＤを生成し、ステップＳ２２の処理を行う。この場合、コンテンツリスト管理サーバ２ｂは、例えば、上記コンテンツＩＤ（“１１１”）に対応するコンテンツデータのコンテンツ名“ＸＸＸ”の末尾に数値“３”（つまり、当該処理が繰り返される度に、末尾の数値が所定値（例えば、１）ずつ増加していく）を付加した“ＸＸＸ３”を上記ハッシュ関数によりハッシュ化してコンテンツＩＤを生成する。
【０１３０】
ステップＳ２３では、コンテンツリスト管理サーバ２ｂは、上記生成され、ＲＡＭに一時記憶された新たなコンテンツＩＤ（例えば“１２１”）を含むコンテンツＩＤ発行メッセージを、上記コンテンツデータの新しいコンテンツＩＤの発行要求元であるルートノードＲ１に対して送信する。
【０１３１】
次いで、コンテンツリスト管理サーバ２ｂは、上記新たなコンテンツＩＤ（例えば“１２１”）を、元のコンテンツＩＤ（“１１１”）に対応するコンテンツデータの新しいコンテンツＩＤとして、コンテンツリストに登録し、当該コンテンツリストを更新（バージョンアップ）する（ステップＳ２４）。
【０１３２】
次いで、コンテンツリスト管理サーバ２ｂは、上記更新されたコンテンツリストを、オーバーレイネットワーク９に参加している全てのノードｎｎに対して送信し（ステップＳ２５）、当該処理を終了する。
【０１３３】
一方、新しいコンテンツＩＤの発行要求元であるルートノードＲ１の制御部１１は、コンテンツリスト管理サーバ２ｂからのコンテンツＩＤ発行メッセージを受信し、当該新たなコンテンツＩＤ（例えば“１２１”）（つまり、分割に係るノード情報に対応するコンテンツデータに対応付けられるべき新たなコンテンツＩＤ）を取得する（ステップＳ１２）。
【０１３４】
次いで、ルートノードＲ１の制御部１１は、インデックス情報から上記一部のノード情報（図１０に示す例では、符号５１部に示す半分のノード情報）を分割し、分割された夫々のノード情報をインデックス情報から取得し、当該夫々のノード情報に示されたコンテンツ保持ノード（以下、「コンテンツ保持ノードＨ１〜Ｈ３」という）のＩＰアドレス及びポート番号宛てに（ここでは、Ｈ１〜Ｈ３の３つのコンテンツ保持ノードを例にとるが実際にはこれよりも多くのコンテンツ保持ノードは存在する）、上記元のコンテンツＩＤ（“１１１”）と新しいコンテンツＩＤ（“１２１”）が含まれる管理元変更メッセージ（当該分割に係るノード情報が新たなルートノードＲ２により管理されることを示す管理元変更情報）を送信する（ステップＳ１３、図１１（Ａ）参照）。
【０１３５】
次いで、ルートノードＲ１の制御部１１は、インデックスキャッシュ領域から上記分割されたノード情報（図１０に示す例では、符号５１部に示す半分のノード情報）を削除する（ステップＳ１４）。なお、ルートノードＲ１の制御部１１は、後述するように、各コンテンツ保持ノードＨ１〜Ｈ３から送信された削除通知メッセージを受信したときに、各削除通知メッセージに含まれるノード情報を、インデックスキャッシュ領域から削除する（１つ１つ削除する）ように構成しても良い（この場合、ステップＳ１４で、一括して分割に係るノード情報を削除しなくても良い）。これにより、誤りなく当該ノード情報を削除することができる。
【０１３６】
次いで、ルートノードＲ１の制御部１１は、上記元のコンテンツＩＤ（“１１１”）、新しいコンテンツＩＤ（“１２１”）、上記分割直後のインデックスキャッシュ領域に記憶されていた元のコンテンツＩＤ（“１１１”）に対応するノード情報の量（又は、ノード情報の数）、及び分割した時の時刻情報を対応付けてノード情報の分割履歴として、記憶部１２に記憶し（ステップＳ１５）、当該処理を終了する。なお、分割直後のインデックスキャッシュ領域に記憶されていたコンテンツＩＤ（“１１１”）に対応するノード情報の量は後述するノード情報併合処理において使用される。
【０１３７】
一方、上記各コンテンツ保持ノードＨ１〜Ｈ３は、ルートノードＲ１からの管理元変更メッセージを受信すると、図９に示すコンテンツＩＤ変更処理を開始し、先ず、制御部１１は、管理元変更メッセージに含まれるコンテンツＩＤ（“１１１”）に対応するコンテンツデータのレプリカを保存しているか否かを判別する（ステップＳ３１）。かかる判別は、コンテンツデータのレプリカがそのコンテンツ保持ノードから既に削除されるが、その情報がルートノードには伝わっていない場合（例えば、タイムラグや通信不良等）が考えられるために行われる。
【０１３８】
次いで、各コンテンツ保持ノードＨ１〜Ｈ３の制御部１１は、管理元変更メッセージに含まれるコンテンツＩＤ（“１１１”）、及び自己のノード情報が含まれる削除通知メッセージを、元のルートノードＲ１に向けて送出（送信）する（ステップＳ３２）。これにより、削除通知メッセージは、図１１（Ｂ）に示すように、コンテンツＩＤ（“１１１”）をキーとするＤＨＴルーティングによってルートノードＲ１まで転送されることになり、その転送経路におけるキャッシュノードＣ１〜Ｃ９においても、削除通知メッセージに含まれるノード情報が削除される。これにより、古いコンテンツＩＤに関するノード情報を効率良く削除することができる。
【０１３９】
次いで、各コンテンツ保持ノードＨ１〜Ｈ３の制御部１１は、コンテンツＩＤ（“１１１”）に対応するコンテンツデータのレプリカを特定し、元のコンテンツＩＤ（“１１１”）を、管理元変更メッセージに含まれる新たなコンテンツＩＤ（“１２１”）に変更する（ステップＳ３３）。つまり、当該レプリカに対して新たなコンテンツＩＤ（“１２１”）を対応付け直して記憶する。
【０１４０】
次いで、各コンテンツ保持ノードＨ１〜Ｈ３の制御部１１は、新たなコンテンツＩＤ（“１２１”）、及び自己のノード情報が含まれるパブリッシュメッセージを、新たなルートノードＲ２に向けて送出（送信）する（ステップＳ３４）。これにより、パブリッシュメッセージは、図１１（Ｃ）に示すように、コンテンツＩＤ（“１２１”）をキーとするＤＨＴルーティングによってルートノードＲ２まで転送されることになり、パブリッシュメッセージに含まれるノード情報は、上述した図６に示すノード情報登録処理によって、当該ルートノードＲ２におけるインデックスキャッシュ領域に、インデックス情報として登録（記憶）され、かつ、パブリッシュメッセージの転送経路におけるキャッシュノードＣ１１〜Ｃ１９においても、パブリッシュメッセージに含まれるノード情報がインデックスキャッシュ領域に登録（記憶）される。こうして、ノード情報の分割が完了する。
【０１４１】
以上説明したように、上記ノード情報の分割に関する処理によれば、ルートノードにおけるインデックスキャッシュ領域があふれそうになった場合であっても、ノード情報を分割して、当該分割されたノード情報を新たなルートノードに管理させるようにしたので、インデックス情報量に応じてルートノードの数を適切に変更することができ、コンテンツデータのレプリカの数を増大させても、当該レプリカへのアクセスを分散させることができる。
【０１４２】
なお、上記ステップＳ９において、ルートノードＲ１の制御部１１は、ネットワーク８の負荷が分散するように分割に係るノード情報を決定するように構成しても良い。例えば、インデックス情報における各ノード情報に対応付けて各ノードｎｎのネットワーク８において属するネットワーク接続グループを示す所属情報を登録しておき、制御部１１は、当該所属情報を取得し、同一の所属情報を有するコンテンツ保持ノードを示すノード情報が、別々のルートノード（例えば、ルートノードＲ１とルートノードＲ２）により均等に管理されるように当該ノード情報の一部を分割する（振り分ける）。ここで、所属情報の例としては、１〜６５５３５の範囲から割り当てられるＡＳ（Autonomous System）番号が挙げられる。このＡＳとは、インターネットを構成する、一つ（共通）の運用ポリシーを持ったネットワークの塊をいい（自律システムともいう）、インターネットはこのＡＳの集合体ととらえることができる。このようにＡＳ単位に分割して管理することでルーティングのオーバーヘッドを減らし、ネットワーク８の管理が容易になる。なお、ＡＳ番号は、例えば、ＩＳＰ（インターネットサービスプロバイダ）からＩＰアドレスが割り当てられる際に、決定される。ノードｎｎ自身が、自分が属するＡＳ番号を取得するには、ＩＲＲ（Internet Routing Registry）やＪＰＮＩＣ（社団法人日本ネットワークインフォメーションセンター）のＷＨＯＩＳデータベースにアクセスする方法（ＩＰアドレスからＡＳ番号が分かる）、あるいは、ユーザがＩＳＰから契約している回線のＡＳ番号を入手して、その値をユーザがノード装置にあらかじめ入力しておく方法、などが可能である。なお、本実施形態においては、ネットワーク接続グループの一例として、ＩＳＰを例にとったがこれに限定されるものではなく、その他のネットワーク運営組織又は運営団体としても良い。
【０１４３】
また、ネットワーク８の負荷が分散するように分割に係るノード情報を決定する他の例として、例えば、制御部１１は、各ノード情報に示されたコンテンツ保持ノードのアクセス頻度を示すアクセス頻度情報を取得（例えば、各コンテンツ保持ノードからアクセス頻度を集計）し、各コンテンツ保持ノードのアクセス頻度情報に基づいて、各コンテンツ保持ノードへのアクセス頻度の合計が、例えば、ルートノードＲ１とルートノードＲ２とで均等するようにノード情報の一部を分割する（振り分ける）。
【０１４４】
また、上記ステップＳ１２においては、ルートノードＲ１は、コンテンツリスト管理サーバ２ｂから新たなコンテンツＩＤ（例えば“１２１”）を取得するようにしたが、これに限定されるものではなく、ルートノードＲ１が、上記コンテンツＩＤ（“１１１”）に対応するコンテンツデータのコンテンツ名“ＸＸＸ”の末尾に任意の数値（例えば“２”）を付加し、これを上記ハッシュ関数によりハッシュ化してコンテンツＩＤ（例えば“１２１”）を生成し、取得するように構成しても良い（この場合、上記ステップＳ１１は不要となる）。この場合、各ユーザノードは、コンテンツリストに記述されたコンテンツ名＋任意の数値を、上記ハッシュ関数によりハッシュ化してコンテンツＩＤを生成することになる。このような構成によれば、コンテンツリスト管理サーバ２ｂが必ずしも必要がなくなる。
【０１４５】
また、上記動作例においては、ルートノードＲ１が、分割に係るノード情報に示されたコンテンツ保持ノードに対して管理元変更メッセージを送信し、当該コンテンツ保持ノードからルートノードＲ２に対してパブリッシュメッセージが送信されることによってルートノードＲ２において分割に係るノード情報が管理されるようにしたが、別の例として、ルートノードＲ１が直接、ルートノードＲ２に対して分割に係るノード情報を送信（例えば、ルートノードＲ２にて管理される新たなコンテンツＩＤをキーとしたＤＨＴルーティングにより）して管理させるように構成しても良い。
【０１４６】
（２−２．ノード情報の削除、併合）
次に、図１２乃至図１７等を参照して、ノード情報の削除、併合が行われる際の動作例について説明する。
【０１４７】
図１２は、ノードｎｎにおけるノード情報削除処理の一例を示すフローチャートであり、図１３は、ノードｎｎ（ルートノード）におけるノード情報併合処理の一例を示すフローチャートであり、図１４は、ノードｎｎ（ルートノード）におけるノード情報被併合処理の一例を示すフローチャートであり、図１５は、コンテンツＩＤ変更処理の一例を示すフローチャートであり、図１６は、コンテンツリスト管理サーバ２ｂにおけるコンテンツＩＤ削除（抹消）処理の一例を示すフローチャートである。また、図１７は、ノード情報の併合が決定された際におけるインデックスキャッシュ領域に記憶されたノード情報の一例を示す図である。図１８は、ノード情報の併合が決定された後の各種メッセージの流れの一例を示す図である。
【０１４８】
図１２に示す処理は、任意のノードｎｎが、他のノードｎｎから送信（又は転送）されてきた削除通知メッセージを受信した場合に開始され、先ず、制御部１１は、削除通知メッセージに含まれるノード情報であって、当該メッセージに含まれるコンテンツＩＤに対応するノード情報が、インデックスキャッシュ領域に記憶されているか（インデックス情報として登録されているか）否かを判別し（ステップＳ４１）、当該ノード情報が記憶されていない場合には（ステップＳ４１：Ｎ）、ステップＳ４３に進み、当該ノード情報が記憶されている場合には（ステップＳ４１：Ｙ）、当該コンテンツＩＤに対応するノード情報をインデックスキャッシュ領域から削除し（ステップＳ４２）、ステップＳ４３に進む。
【０１４９】
ステップＳ４３では、制御部１１は、自己（自分のノード）のＤＨＴのルーティングテーブルを参照して、自己が、当該削除通知メッセージに含まれるコンテンツＩＤ（例えば、上述した“１１１”とする）のルートノードＲ１であるか否かを判別し、自己がルートノードＲ１でない（言い換えれば、キャッシュノードである）と判別された場合には（ステップＳ４３：Ｎ）、ステップＳ４４へ進み、自己がルートノードＲ１であると判別された場合には（ステップＳ４３：Ｙ）、ステップＳ４５へ進む。
【０１５０】
ステップＳ４４では、制御部１１は、自己のＤＨＴのルーティングテーブルから、転送先のノードｎｎ（上記コンテンツＩＤ（“１１１”）と最も近い（例えば、上位桁がより多く一致する）ノードＩＤを有する例えばノードｎｎ）のＩＰアドレス及びポート番号を取得し、そのＩＰアドレス及びポート番号宛てに、上記削除通知メッセージを転送し、当該処理を終了する。
【０１５１】
一方、ステップＳ４５では、ルートノードＲ１の制御部１１は、ノード情報併合処理を実行する。このノード情報併合処理においては、図１３に示すように、ルートノードＲ１の制御部１１は、先ず、上記ステップＳ４２で削除したノード情報に対応するコンテンツＩＤが、記憶部１２に記憶された分割履歴中に含まれているか否かを判別し（ステップＳ５１）、当該コンテンツＩＤが分割履歴中に含まれていない場合には（ステップＳ５１：Ｎ）、当該処理を終了し、当該コンテンツＩＤが分割履歴中に含まれている場合には（ステップＳ５１：Ｙ）、ステップＳ５２に進む。
【０１５２】
なお、当該分割履歴中には、コンテンツＩＤ（“１１１”）、コンテンツＩＤ（“１２１”）、及び分割直後のインデックスキャッシュ領域に記憶されていたコンテンツＩＤ（“１１１”）に対応するノード情報の量等の組が含まれているものとする。
【０１５３】
ステップＳ５２では、ルートノードＲ１の制御部１１は、自己がルートノードとして管理するコンテンツＩＤ（“１１１”）に対応するコンテンツデータのレプリカを保存しているコンテンツ保持ノードの全ノード情報の量が、所定の基準量（例えば、上記分割履歴中に含まれている、分割直後のインデックスキャッシュ領域に記憶されていたコンテンツＩＤ（“１１１”）に対応するノード情報の半分（５０％）の量）以下か否かを判別（つまり、コンテンツＩＤ（“１１１”）に対応する全ノード情報が相当数減ったかどうかを判別）する。例えば、ルートノードとして管理しなければならないノード情報がインデックスキャッシュ領域の９０％以上となったときに、ノード情報分割処理を行う場合では、分割直後のインデックスキャッシュ領域に記憶されていたコンテンツＩＤ（“１１１”）に対応するノード情報がインデックスキャッシュ領域の４５％となるため、ステップＳ５２では、その半分（５０％）の量、つまり、インデックスキャッシュ領域の２２．５％以下か否かを判別する。なお、上記基準量は、特に５０％の量に限定されるものではなく、任意の量を設定可能である。また、基準量を基準数で表し、上記全ノード情報の数が、所定の基準数以下か否かが判別されるように構成しても良い。また、所定の基準量または所定の基準数未満か否かが判別されるようにしても良い。
【０１５４】
そして、制御部１１は、所定の基準量より大きい場合（ステップＳ５２：Ｎ）、当該処理を終了し、所定の基準量以下の場合（ステップＳ５２：Ｙ）、上述した分割されたノード情報（例えば、コンテンツＩＤ（“１２１”）に対応）を、自己のインデックスキャッシュ領域に記憶されているノード情報（例えば、コンテンツＩＤ（“１１１”）に対応）に併合することを決定し（ステップＳ５３）、ステップＳ５４に進む。
【０１５５】
例えば、図１７に示す例では、上記コンテンツＩＤ（“１１１”）に対応するコンテンツデータのレプリカを保存しているコンテンツ保持ノードの全ノード情報（元のノード情報）の量が、基準量（例えば、分割直後のインデックスキャッシュ領域に記憶されていたコンテンツＩＤ（“１１１”）に対応するノード情報の半分（５０％）の量）より少なくなっているため、ルートノードＲ２により管理されているコンテンツＩＤ（“１２１”）に対応するノード情報が、元のノード情報に併合され、ルートノードＲ１により管理されることになる。
【０１５６】
ステップＳ５４では、ルートノードＲ１の制御部１１は、上記分割履歴に含まれるコンテンツＩＤ（“１２１”）に対応するノード情報（つまり、分割されたノード情報）を、当該分割履歴に含まれるコンテンツＩＤ（“１１１”）に対応するノード情報（つまり、元のノード情報）に併合する併合要求メッセージ（併合することを示す併合情報）を、上記コンテンツＩＤ（“１２１”）に対応するノード情報（分割されたノード情報）を管理するルートノードＲ２に向けて送出（送信）する。当該併合要求メッセージには、例えば、ルートノードＲ１のＩＰアドレス及びポート番号、コンテンツＩＤ（“１２１”）、コンテンツＩＤ（“１１１”）及び上記分割直後のインデックスキャッシュ領域に記憶されていたコンテンツＩＤ（“１１１”）に対応するノード情報の半分（５０％）の量が含まれている。そして、併合要求メッセージは、例えば、コンテンツＩＤ（“１２１”）をキーとするＤＨＴルーティングによってルートノードＲ２まで転送されることになる。
【０１５７】
一方、ルートノードＲ２の制御部１１は、かかる併合要求メッセージを受信すると、図１４に示すノード情報被併合処理を開始し、自己がルートノードとして管理するコンテンツＩＤ（“１２１”）に対応するコンテンツデータのレプリカを保存しているコンテンツ保持ノードの全ノード情報（併合要求メッセージに対応するノード情報）の量が、所定の基準量（例えば、併合要求メッセージに含まれる分割直後のインデックスキャッシュ領域に記憶されていたコンテンツＩＤ（“１１１”）に対応するノード情報の半分（５０％）の量）以下か否かを判別する（ステップＳ６１）。なお、上記基準量は、特に５０％の量に限定されるものではなく、任意の量を設定可能である。
【０１５８】
そして、制御部１１は、所定の基準量以下の場合（ステップＳ６１：Ｙ）、ステップＳ６２に進み、所定の基準量より大きい場合（ステップＳ６１：Ｎ）、ステップＳ６５に進む。
【０１５９】
ステップＳ６２では、ルートノードＲ２の制御部１１は、インデックスキャッシュ領域に記憶されている、自己がルートノードとして管理するコンテンツＩＤ（“１２１”）に対応するノード情報（併合要求メッセージに対応するノード情報）に示されたコンテンツ保持ノードＨ１〜Ｈ３のＩＰアドレス及びポート番号宛てに、上記コンテンツＩＤ（“１１１”）とコンテンツＩＤ（“１２１”）が含まれる管理元変更メッセージ（ルートノードＲ２により管理されるコンテンツＩＤ（“１２１”）に対応するノード情報が元のルートノードＲ１により管理されることを示す管理元変更情報）を送信する（図１８（Ａ）参照）。
【０１６０】
次いで、ルートノードＲ２の制御部１１は、インデックスキャッシュ領域からコンテンツＩＤ（“１２１”）に対応するノード情報（併合要求メッセージに対応するノード情報であり、自己がルートノードとして管理するノード情報）を削除する（ステップＳ６３）。なお、ルートノードＲ２の制御部１１は、後述するように、各コンテンツ保持ノードＨ１〜Ｈ３から送信された削除通知メッセージを受信したときに、各削除通知メッセージに含まれるノード情報を、インデックスキャッシュ領域から削除する（１つ１つ削除する）ように構成しても良い（この場合、ステップＳ６３で、一括して分割に係るノード情報を削除しなくても良い）。
【０１６１】
次いで、ルートノードＲ２の制御部１１は、併合成功を示す情報を含む併合返答メッセージを、上記併合要求メッセージの送信元のルートノードＲ１に対して送信し（ステップＳ６４）、当該処理を終了する。
【０１６２】
一方、ステップＳ６５では、ルートノードＲ２の制御部１１は、併合失敗を示す情報を含む併合返答メッセージを、上記併合要求メッセージの送信元のルートノードＲ１に対して送信し、当該処理を終了する。
【０１６３】
そして、図１３に示すように、上記併合要求メッセージの送信元のルートノードＲ１の制御部１１は、ルートノードＲ２からの併合返答メッセージを受信すると（ステップＳ５５）、当該併合返答メッセージに、併合成功を示す情報が含まれているか否かを判別し（ステップＳ５６）、併合成功を示す情報が含まれていない（つまり、併合失敗を示す情報が含まれている）場合には（ステップＳ５６：Ｎ）、当該処理を終了し、併合成功を示す情報が含まれている場合には（ステップＳ５６：Ｙ）、ステップＳ５７に進む。
【０１６４】
ステップＳ５７では、ルートノードＲ１の制御部１１は、上記コンテンツＩＤ（“１２１”）に対応するノード情報が、コンテンツＩＤ（“１１１”）に対応するノード情報に併合されたことを示す併合メッセージをコンテンツリスト管理サーバ２ｂに対して送信する。
【０１６５】
そして、ルートノードＲ１の制御部１１は、記憶部１２に記憶された分割履歴から、上記併合に係るコンテンツＩＤ（“１１１”）、コンテンツＩＤ（“１２１”）、及び分割直後のインデックスキャッシュ領域に記憶されていたコンテンツＩＤ（“１１１”）に対応するノード情報の量の組を削除して（ステップＳ５８）、当該処理を終了する。
【０１６６】
一方、上記各コンテンツ保持ノードＨ１〜Ｈ３は、ルートノードＲ２からの管理元変更メッセージ（上記ステップＳ６２で送信された管理元変更メッセージ）を受信すると、図１５に示すコンテンツＩＤ変更処理を開始し、先ず、制御部１１は、コンテンツＩＤ（“１２１”）に対応するコンテンツデータのレプリカを保存しているか否かを判別する（ステップＳ７１）。
【０１６７】
次いで、各コンテンツ保持ノードＨ１〜Ｈ３の制御部１１は、管理元変更メッセージに含まれるコンテンツＩＤ（“１２１”）、及び自己のノード情報が含まれる削除通知メッセージを、併合されるルートノードＲ２に向けて送出する（ステップＳ７２）。これにより、削除通知メッセージは、図１８（Ｂ）に示すように、コンテンツＩＤ（“１２１”）をキーとするＤＨＴルーティングによってルートノードＲ２まで転送されることになり、その転送経路におけるキャッシュノードＣ１１〜Ｃ１９においても、削除通知メッセージに含まれるノード情報が削除される。これにより、古いコンテンツＩＤに関するノード情報を効率良く削除することができる。
【０１６８】
次いで、各コンテンツ保持ノードＨ１〜Ｈ３の制御部１１は、コンテンツＩＤ（“１２１”）に対応するコンテンツデータのレプリカを特定し、当該コンテンツＩＤ（“１２１”）を、管理元変更メッセージに含まれる元のコンテンツＩＤ（“１１１”）に変更する（ステップＳ７３）。つまり、当該レプリカに対して元のコンテンツＩＤ（“１１１”）を対応付け直して記憶する。
【０１６９】
次いで、各コンテンツ保持ノードＨ１〜Ｈ３の制御部１１は、元のコンテンツＩＤ（“１１１”）、及び自己のノード情報が含まれるパブリッシュメッセージを、元のルートノードＲ１に向けて送出する（ステップＳ７４）。これにより、パブリッシュメッセージは、図１８（Ｃ）に示すように、コンテンツＩＤ（“１１１”）をキーとするＤＨＴルーティングによってルートノードＲ１まで転送されることになり、パブリッシュメッセージに含まれるノード情報は、上述した図６に示すノード情報登録処理によって、当該ルートノードＲ１におけるインデックスキャッシュ領域に、インデックス情報として登録（記憶）され、かつ、パブリッシュメッセージの転送経路におけるキャッシュノードＣ１〜Ｃ９においても、パブリッシュメッセージに含まれるノード情報がインデックスキャッシュ領域に登録（記憶）される。こうして、ノード情報の併合が完了する。
【０１７０】
一方、コンテンツリスト管理サーバ２ｂは、ルートノードＲ１からの併合メッセージ（上記ステップＳ５７で送信された併合メッセージ）を受信すると、図１６に示すコンテンツＩＤ削除（抹消）処理を開始し、併合メッセージに示されたコンテンツＩＤ（例えば“１２１”）を、コンテンツリストから削除（抹消）し、当該コンテンツリストを更新（バージョンアップ）する（ステップＳ８１）。
【０１７１】
次いで、コンテンツリスト管理サーバ２ｂは、上記更新されたコンテンツリストを、オーバーレイネットワーク９に参加している全てのノードｎｎに対して送信し（ステップＳ８２）、当該処理を終了する。
【０１７２】
以上説明したように、上記ノード情報の併合に関する処理によれば、コンテンツ保持ノードへの例えばアクセス頻度の低下に伴い、当該コンテンツ保持ノードの数が減少したとしても、分割されたノード情報を併合して、元のルートノードに管理させるようにしたので、インデックス情報量に応じてルートノードの数を適切に変更することができ、ルートノードへの問合せ効率が悪くなることがない。よって、無駄なルートノードが無く、メンテナンス上も好ましい。
【０１７３】
（２−３．ノード情報の削除、併合（多重分割の対応））
次に、図１９乃至図２２等を参照して、ノード情報の多重分割が行われた後にノード情報の併合が行われる際の動作例について説明する。
【０１７４】
ここで、多重分割とは、上述した図７に示すノード情報分割処理によって、１つのコンテンツに関する多数のノード情報が３つ以上に分割されることをいう。これにより、１つのコンテンツに関して３つ以上のルートノードによりインデックス情報が管理される。
【０１７５】
図１９は、ノード情報の多重分割の様子の一例を示す図であり、図２０は、多重分割が行われた後にノード情報の併合が行われる様子の一例を示す図である。また、図２１は、多重分割を考慮したルートノードにおけるノード情報併合処理の一例を示すフローチャートであり、図２２は、多重分割を考慮したルートノードにおけるノード情報被併合処理の一例を示すフローチャートである。
【０１７６】
なお、図２１に示すノード情報併合処理は、多重分割を考慮した場合に、図１３に示すノード情報併合処理に代えて行われ、図２２に示すノード情報被併合処理は、多重分割を考慮した場合に、図１４に示すノード情報併合処理に代えて行われるものである。従って、多重分割が行われた後にノード情報の併合が行われる際の動作においても、上述した、図１２に示すノード情報削除処理、図１５に示すコンテンツＩＤ変更処理、及び図１６に示すコンテンツＩＤ削除（抹消）処理は、同様に行われる（これらの処理についての重複した説明は省略する）。
【０１７７】
図１９の例では、多重分割によって、１つのコンテンツに関して８つのルートノードＲ１〜Ｒ８ができており、図中に示す“分割”に付記された数字（１〜３）は、ノード情報の分割の順序を示している（つまり、分割１→分割２→分割３の順で分割が行われた例である）。また、図１９の例では、ルートノードＲ１は、自己が管理するインデックス情報からノード情報を、ルートノードＲ２→ルートノードＲ３→ルートノードＲ４の順に計３回分割している。このような多重分割が行われた場合、各ルートノードは、基本的には自分が行った分割しか知らない（例えば、図１９の例において、ルートノードＲ１は、ルートノードＲ２が行った分割は知らない）ので、自分が分割したノード情報は、自分が責任を持って併合するものとし、当該併合は、図２０に示すように、分割とは逆の順序で行われる（併合１→併合２→併合３の順、つまり、現時点から最も近い過去に分割されたノード情報から併合する）ものとする。
【０１７８】
図２１に示すノード情報併合処理が、図１９及び図２０に示すルートノードＲ１で行われる場合、その制御部１１は、先ず、上記ステップＳ４２で削除したノード情報に対応するコンテンツＩＤ（例えば、“１１１”）が、記憶部１２に記憶された分割履歴中に含まれているか否かを判別し（ステップＳ９１）、当該コンテンツＩＤが分割履歴中に含まれていない場合には（ステップＳ９１：Ｎ）、当該処理を終了し、当該コンテンツＩＤが分割履歴中に含まれている場合には（ステップＳ９１：Ｙ）、ステップＳ９２に進む。
【０１７９】
ステップＳ９２では、ルートノードＲ１で行われる場合、その制御部１１は、分割履歴に含まれる各分割した時の時刻情報を参照して、コンテンツＩＤ（“１１１”）に関する分割履歴の中で、現時点から最も近い過去に分割された組合せ（元のコンテンツＩＤ、分割に係るコンテンツＩＤ、及び分割直後のインデックスキャッシュ領域に記憶されていたコンテンツＩＤに対応するノード情報の量の組）を取得する。例えば、図２０の例では、ルートノードＲ４への分割が最も近いことになる。
【０１８０】
ステップＳ９３では、ステップＳ５２と同様、ルートノードＲ１の制御部１１は、上記コンテンツＩＤ（“１１１”）に対応するコンテンツデータのレプリカを保存しているコンテンツ保持ノードの全ノード情報の量が、所定の基準量以下か否かを判別する。
【０１８１】
そして、制御部１１は、所定の基準量より大きい場合（ステップＳ９３：Ｎ）、当該処理を終了し、所定の基準量以下の場合（ステップＳ９３：Ｙ）、上述した分割に係る（分割された）ノード情報（例えば、コンテンツＩＤ（“１４１”）に対応）を、自己のインデックスキャッシュ領域に記憶されているノード情報（例えば、コンテンツＩＤ（“１１１”）に対応）に併合することを決定（つまり、ノード情報が複数回分割されている場合、当該複数回の分割のうち最近分割されたノード情報が元のルートノードＲ１にて管理されるノード情報に併合されることが決定）し（ステップＳ９４）、ステップＳ９５に進む。
【０１８２】
ステップＳ９５では、ルートノードＲ１の制御部１１は、上記分割履歴に含まれるコンテンツＩＤ（“１４１”）に対応するノード情報を、当該分割履歴に含まれるコンテンツＩＤ（“１１１”）に対応するノード情報に併合する併合要求メッセージを、上記コンテンツＩＤ（“１４１”）に対応するノード情報を管理するルートノードＲ４に向けて送出する。当該併合要求メッセージには、例えば、ルートノードＲ１のＩＰアドレス及びポート番号、コンテンツＩＤ（“１４１”）、コンテンツＩＤ（“１１１”）及び上記分割直後のインデックスキャッシュ領域に記憶されていたコンテンツＩＤ（“１１１”）に対応するノード情報の半分（５０％）の量が含まれている。そして、併合要求メッセージは、例えば、コンテンツＩＤ（“１４１”）をキーとするＤＨＴルーティングによってルートノードＲ４まで転送されることになる。
【０１８３】
一方、ルートノードＲ４の制御部１１は、かかる併合要求メッセージを受信すると、図２２に示すノード情報被併合処理を開始し、図２１に示すノード情報併合処理を実行（再帰的に実行される）する（ステップＳ１０１）。このノード情報併合処理でも、上記ステップＳ９１以降の処理が行われ、次いで、ステップＳ１０２では、インデックス併合処理が成功したか否かが判別される。例えば、ステップＳ１０１にて実行される図２１に示すノード情報併合処理において、コンテンツＩＤ（例えば、“１４１”）が分割履歴に含まれていないと判別され（ステップＳ９１：Ｎ）ノード情報併合処理が終了した場合、ステップＳ１０２でインデックス併合処理が成功したと判別され（ステップＳ１０２：Ｙ）、ステップＳ１０３に進み、ステップＳ９３又はＳ９７で“Ｎ（ｎｏ）”となってノード情報併合処理が終了した場合、ステップＳ１０２でインデックス併合処理が失敗したと判別され（ステップＳ１０２：Ｎ）、ステップＳ１０７に進む。
【０１８４】
ステップＳ１０３では、ルートノードＲ４の制御部１１は、自己がルートノードとして管理するコンテンツＩＤ（“１４１”）に対応するコンテンツデータのレプリカを保存しているコンテンツ保持ノードの全ノード情報の量が、所定の基準量以下か否かを判別し（上述したステップＳ６１と同様の考え）、所定の基準量以下の場合（ステップＳ１０３：Ｙ）、ステップＳ１０４に進み、所定の基準量より大きい場合（ステップＳ１０３：Ｎ）、ステップＳ１０７に進む。
【０１８５】
ステップＳ１０４では、ルートノードＲ４の制御部１１は、インデックスキャッシュ領域に記憶されている、コンテンツＩＤ（“１４１”）に対応するノード情報に示されたコンテンツ保持ノードのＩＰアドレス及びポート番号宛てに、コンテンツＩＤ（“１１１”）とコンテンツＩＤ（“１４１”）が含まれる管理元変更メッセージ（ルートノードＲ４により管理されるコンテンツＩＤ（“１４１”）に対応するノード情報が元のルートノードＲ１により管理されることを示す管理元変更情報）を送信する。
【０１８６】
次いで、ルートノードＲ４の制御部１１は、インデックスキャッシュ領域からコンテンツＩＤ（“１４１”）に対応するノード情報を削除する（ステップＳ１０５）。
【０１８７】
次いで、ルートノードＲ４の制御部１１は、併合成功を示す情報を含む併合返答メッセージを、上記併合要求メッセージの送信元のルートノードＲ１に対して送信し（ステップＳ１０６）、当該処理を終了する。
【０１８８】
一方、ステップＳ１０７では、ルートノードＲ４の制御部１１は、併合失敗を示す情報を含む併合返答メッセージを、上記併合要求メッセージの送信元のルートノードＲ１に対して送信し、当該処理を終了する。
【０１８９】
そして、図２１に示すように、上記併合要求メッセージの送信元のルートノードＲ１の制御部１１は、ルートノードＲ４からの併合返答メッセージを受信すると（ステップＳ９６）、当該併合返答メッセージに、併合成功を示す情報が含まれているか否かを判別し（ステップＳ９７）、併合成功を示す情報が含まれていない場合には（ステップＳ９７：Ｎ）、当該処理を終了し、併合成功を示す情報が含まれている場合には（ステップＳ９７：Ｙ）、ステップＳ９８に進む。
【０１９０】
ステップＳ９８では、ルートノードＲ１の制御部１１は、上記コンテンツＩＤ（“１４１”）に対応するノード情報が、コンテンツＩＤ（“１１１”）に対応するノード情報に併合されたことを示す併合メッセージをコンテンツリスト管理サーバ２ｂに対して送信する。
【０１９１】
そして、ルートノードＲ１の制御部１１は、記憶部１２に記憶された分割履歴から、コンテンツＩＤ（“１１１”）、コンテンツＩＤ（“１４１”）、及び分割直後のインデックスキャッシュ領域に記憶されていたコンテンツＩＤ（“１１１”）に対応するノード情報の量の組を削除して（ステップＳ９９）、ステップＳ９１に戻る。こうして、ルートノードＲ４で管理されていたノード情報の併合が完了する。
【０１９２】
そして、ステップＳ９１に戻ると、再び、コンテンツＩＤ（例えば、“１１１”）が、未だ記憶部１２に記憶された分割履歴中に含まれているか否かが判別されることになる。例えば、図１９の例では、ルートノードＲ３が未だあるので、当該ルートノードＲ３にて管理されているノード情報を併合するための処理が行われることになるが、かかるルートノードＲ３は、自らノード情報の分割を行い、分割されたノード情報をルートノードＲ５に管理させているので、図２２に示すノード情報被併合処理がルートノードＲ３で行われた場合、ステップＳ１０１にて実行される図２１に示すノード情報併合処理においてルートノードＲ５にて管理されるノード情報がルートノードＲ３にて管理されるノード情報に併合された後、併合後の当該ルートノードＲ３にて管理されるノード情報に示されるコンテンツ保持ノードに対して更管理元変更メッセージが送信され、当該併合後の当該ルートノードＲ３にて管理されるノード情報がルートノードＲ１にて管理されるノード情報に併合されることになる。
【０１９３】
以上説明したように、多重分割を考慮したノード情報の併合に関する処理によれば、多重分割があった後に、コンテンツ保持ノードへの例えばアクセス頻度の低下に伴い、当該コンテンツ保持ノードの数が減少したとしても、多重分割されたノード情報をより効率よく併合する（元の状態に戻す）ことができる。
【０１９４】
なお、上記実施形態におけるノード情報の併合は、ノード情報の分割があった後に行われる場合を例にとって説明したが、当該ノード情報の分割を前提としない場合、つまり、当初から１つのコンテンツに関するルートノードを複数設けておいた場合についても、上記ノード情報の併合は適用可能である。
【０１９５】
また、上記実施形態においては、ＤＨＴを利用したアルゴリズムによって構築されたオーバーレイネットワーク９を前提として説明したが、本発明はこれに限定されるものではない。
【図面の簡単な説明】
【０１９６】
【図１】本実施形態に係るコンテンツ配信システムにおける各ノード装置の接続態様の一例を示す図である。
【図２】ノードｎ１が保持するＤＨＴのルーティングテーブルの一例を示す図である。
【図３】ＤＨＴのノードＩＤ空間の一例を示す概念図である。
【図４】（Ａ）は、コンテンツ保持ノードから送出されたパブリッシュメッセージの流れの一例を、（Ｂ）は、コンテンツ保持ノードから送出された削除通知メッセージの流れの一例を、夫々、ＤＨＴのノードＩＤ空間にて示した概念図である。
【図５】ノードｎｎの概要構成例を示す図である。
【図６】ノードｎｎにおけるノード情報登録処理の一例を示すフローチャートである。
【図７】ノードｎｎにおけるノード情報分割処理の一例を示すフローチャートである。
【図８】ノードｎｎにおけるコンテンツＩＤ変更処理の一例を示すフローチャートである。
【図９】コンテンツリスト管理サーバ２ｂにおけるコンテンツＩＤ発行処理の一例を示すフローチャートである。
【図１０】ノード情報の分割が決定された際におけるインデックスキャッシュ領域に記憶されたノード情報の一例を示す図である。
【図１１】ノード情報の分割が決定された後の各種メッセージの流れの一例を示す図である。
【図１２】ノードｎｎにおけるノード情報削除処理の一例を示すフローチャートである。
【図１３】ノードｎｎ（ルートノード）におけるノード情報併合処理の一例を示すフローチャートである。
【図１４】ノードｎｎ（ルートノード）におけるノード情報被併合処理の一例を示すフローチャートである。
【図１５】コンテンツＩＤ変更処理の一例を示すフローチャートである。
【図１６】コンテンツリスト管理サーバ２ｂにおけるコンテンツＩＤ削除（抹消）処理の一例を示すフローチャートである。
【図１７】ノード情報の併合が決定された際におけるインデックスキャッシュ領域に記憶されたノード情報の一例を示す図である。
【図１８】ノード情報の併合が決定された後の各種メッセージの流れの一例を示す図である。
【図１９】ノード情報の多重分割の様子の一例を示す図である。
【図２０】多重分割が行われた後にノード情報の併合が行われる様子の一例を示す図である。
【図２１】多重分割を考慮したルートノードにおけるノード情報併合処理の一例を示すフローチャートである。
【図２２】多重分割を考慮したルートノードにおけるノード情報被併合処理の一例を示すフローチャートである。
【符号の説明】
【０１９７】
ｎｎ  ノード
８  ネットワーク
９  オーバーレイネットワーク
１１  制御部
１２  記憶部
１３  バッファメモリ
１４  デコーダ部
１５  映像処理部
１６  表示部
１７  音声処理部
１８  スピーカ
２０  通信部
２１  入力部
２２  バス
Ｓ  コンテンツ配信システム
【図１】
2007148545.tif 000003
【図２】
2007148545.tif 000004
【図３】
2007148545.tif 000005
【図４】
2007148545.tif 000006
【図５】
2007148545.tif 000007
【図６】
2007148545.tif 000008
【図７】
2007148545.tif 000009
【図８】
2007148545.tif 000010
【図９】
2007148545.tif 000011
【図１０】
2007148545.tif 000012
【図１１】
2007148545.tif 000013
【図１２】
2007148545.tif 000014
【図１３】
2007148545.tif 000015
【図１４】
2007148545.tif 000016
【図１５】
2007148545.tif 000017
【図１６】
2007148545.tif 000018
【図１７】
2007148545.tif 000019
【図１８】
2007148545.tif 000020
【図１９】
2007148545.tif 000021
【図２０】
2007148545.tif 000022
【図２１】
2007148545.tif 000023
【図２２】
2007148545.tif 000024