(57)【特許請求の範囲】
【請求項１】
複数のノードを含み、クライアント端末にデータを配信するデータ配信システムであって、
前記クライアント端末までのデータの配信経路に含まれるノード群に含まれる各ノードは、
前記クライアント端末に配信されるデータである配信データが複数に分割された分割データ群のうちの少なくとも１つの分割データを記憶する記憶部と、
前記クライアント端末から前記配信データの配信要求があった場合に、前記記憶部に保持される前記少なくとも１つの分割データを送信するセグメント送信部と、
を備え、
前記分割データ群に含まれる分割データのそれぞれは、前記分割データ群において前記配信データが開かれる際の参照順序が早い分割データほど、前記クライアント端末までのコストが小さいノードの前記記憶部に記憶され、前記分割データの数が前記ノード群のノード数を超過する場合、前記分割データ群において前記参照順序が前記ノード群のノード数より後の分割データは、前記参照順序が早い分割データほど、前記クライアント端末までのコストが大きいノードの前記記憶部に記憶される、
データ配信システム。
【請求項２】
前記ノード群の各ノードに前記クライアント端末に近づくにつれて大きな番号が割り当てられる場合に、前記ノード群に含まれるノード総数をＮ（０＜Ｎ）、ノード番号をｎ（０＜ｎ≦Ｎ）、変数ｉ（０≦ｉの整数）とすると、前記分割データ群に含まれる前記参照順序の（２ｉ＋１）Ｎ−（ｎ−１）番目及び（２ｉ＋１）Ｎ＋ｎ番目の分割データは、前記ノード群のｎ番目のノードの記憶部に記憶される
請求項１に記載のデータ配信システム。
【請求項３】
前記各ノードは、
前記ノード群内の第１の隣接ノードから受信した分割データを記憶する第２の記憶部と、
前記セグメント送信部によって送信されてから所定時間内に前記第２の記憶部に記憶される分割データに対する配信要求があった場合には、前記第２の記憶部に記憶される分割
データの保持期間を延長し、前記所定時間内に前記第２の記憶部に記憶された分割データに対する配信要求が無い場合には、前記第２の記憶部に記憶された分割データを削除する一時セグメント管理部と、
をさらに備える請求項１又は２に記載のデータ配信システム。
【請求項４】
前記各ノードは、
新たなクライアント端末の追加が通知された際に、少なくとも１つの分割データが前記記憶部に記憶されていない場合には、前記少なくとも１つの分割データを保持する他のノードから少なくとも１つの分割データの複製を取得する固定セグメント取得部
をさらに備える請求項１から３の何れか一項に記載のデータ配信システム。
【請求項５】
前記各ノードは、
前記配信データを各ノード間のデータ伝送速度のうち最小のデータ伝送速度において単位時間当たりに伝送可能なデータ量以下のサイズの分割データに分割するクエリ処理部
をさらに備える請求項１から４の何れか一項に記載のデータ配信システム。
【請求項６】
前記コストは、ノードと前記クライアント端末間の中継ホップ数、応答時間、ＲＴＴ（Round Trip Time）、ＲＷＩＮ（Receive Window）、最大ＭＴＵ（Maximum Transmission Unit）長、データ損失率、使用可能な回線帯域、スループット、地理的な距離、ノードのプロセッサの使用率、ノードのメモリ使用率、ノードのスループット性能、ノードの記憶媒体の読み書き速度のうち１つ以上の値を重みとして換算して表したものである、
請求項１から５のいずれか一項に記載のデータ配信システム。
【請求項７】
複数のノードを含み、クライアント端末にデータを配信するデータ配信システムにおいて、前記クライアント端末までのデータの配信経路に含まれるノード群に含まれるノードであって、
前記クライアント端末に配信されるデータである配信データが複数に分割された分割データ群のうち少なくとも１つの分割データを記憶する記憶部と、
前記クライアント端末から前記配信データの配信要求があった場合に、前記記憶部に保持される前記少なくとも１つの分割データを送信するセグメント送信部と、
を備え、
前記分割データ群に含まれる分割データのそれぞれは、前記分割データ群において前記配信データが開かれる際の参照順序が早い分割データほど、前記クライアント端末までのコストが小さいノードの前記記憶部に記憶され、前記分割データの数が前記ノード群のノード数を超過する場合、前記分割データ群において前記参照順序が前記ノード群のノード数より後の分割データは、前記参照順序が早い分割データほど、前記クライアント端末までのコストが大きいノードの前記記憶部に記憶される、
ノード。
【請求項８】
複数のノードを含み、クライアント端末にデータを配信するデータ配信システムにおいて実行されるデータ配信方法であって、前記クライアント端末までのデータの配信経路に含まれるノード群に含まれる各ノードは、
前記クライアント端末に配信されるデータである配信データが複数に分割された分割データ群のうちの少なくとも１つの分割データを記憶部に記憶し、
前記クライアント端末から前記配信データの配信要求があった場合に、前記記憶部に保持される前記少なくとも１つの分割データを送信し、
前記分割データ群に含まれる分割データのそれぞれは、前記分割データ群において前記配信データが開かれる際の参照順序が早い分割データほど、前記クライアント端末までのコストが小さいノードの前記記憶部に記憶され、前記分割データの数が前記ノード群のノード数を超過する場合、前記分割データ群において前記参照順序が前記ノード群のノー
ド数より後の分割データは、前記参照順序が早い分割データほど、前記クライアント端末までのコストが大きいノードの前記記憶部に記憶される、
データ配信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノードから同一コンテンツのデータをクライアントに配信する技術に関する。
【背景技術】
【０００２】
例えば、映画やテレビ番組の動画データ等のコンテンツ配信サービスでは、不特定多数のクライアントからあらゆるタイミングでコンテンツ配信要求が発生することがある。いかなる場所に位置するクライアントに対しても、コンテンツ到着までの遅延時間を短くし、配信品質を保つ技術として、クライアントに近いネットワーク上で、同一コンテンツを格納するミラーサーバやミラーストレージを設ける技術がある。以降、ミラーサーバ及びミラーストレージをまとめて、ミラーと称する。配信品質には、例えば、コンテンツ配信のビットレート等がある。また，配信品質を低下させる原因には、遅延，ジッタ，パケットロス等がある。
【０００３】
コンテンツ配信サービスで配信されるコンテンツのように、ネットワーク上に格納しておきたいデータは、日々増加している。また、動画データ配信において、高画質なデータ配信を実現しようとすると、ネットワーク上の格納用資源が枯渇してしまうおそれがある。上述のようなミラーの技術が用いられる場合に、ネットワーク上の格納資源の枯渇や、資源増大による運用コストの増加を防止するためには、例えば、ミラーに格納されるデータ量を減らすこと、及び、同一コンテンツを格納するミラーの冗長数を減らすこと等が考えられる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−１４７９０６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、ミラーに格納されるデータ量が減らされる場合には、配信品質を保つことができないコンテンツが出てくる可能性がある。また、同一コンテンツを有するミラーの数が減らされる場合には、ミラーからクライアントまでのネットワーク上の距離や地理的な距離が遠いクライアントが出てくる可能性がある。例えば、ニューヨークに位置するクライアントが東京にあるミラーからコンテンツをストリーミング配信する場合のように、ミラーからの距離が遠いクライアントには、コンテンツ到着までの遅延時間が長くなってしまい、コンテンツ配信時の品質を一定に保つことができなくなる。例えば、ストリーム性を要する映像、音声コンテンツが配信される場合には、ミラーからの距離が遠いクライアントでは、配信経路上でデータロストする可能性が高くなり、再生が途切れてしまったりするため、解像度等のコンテンツ品質を落として配信することがある。また、ＳａａＳ（Software as a Service）アプリケーションにおいては、レスポンス遅延が発生する
可能性があり、クライアントの作業に支障をきたすおそれがある。配信プロトコルの観点からみると、ＴＣＰプロトコルやそれに準じたプロトコルを用いた配信の場合には、３ｗａｙハンドシェイク等、品質確保の再送制御処理により物理的な距離に依存した遅延が生じ、ＵＤＰプロトコルを用いた配信の場合には、一般に物理的な距離が長くなるほど中継機器や中継回線が増えるため、配信経路上の品質低下の確率が高まり、遅延が生じやすくなる。
【０００６】
本発明の一態様は、ネットワーク上に格納されるデータ量を低減し、クライアントへの
コンテンツ到達までの遅延時間の長期化を防止するデータ配信システムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の態様の一つは、データ配信システムである。このデータ配信システムは、複数のノードを含み、クライアント端末にデータを配信するデータ配信システムであって、前記クライアント端末までのデータの配信経路を形成するノード群に含まれる各ノードは、
前記クライアント端末に配信されるデータである１の配信データを該配信データが実行される際の時系列の順で複数に分割された分割ブロック群のうち、前記クライアント端末までのコストに応じた所定の条件を満たす少なくとも１つのブロックを保持する記憶部と、
前記クライアントから前記配信データの配信要求があった場合に、前記記憶部に保持される前記少なくとも１つのブロックを送信するセグメント送信部と、
を備える。
【０００８】
本発明の他の態様の一つは、上述したデータ配信方法である。また、本発明の他の態様は、コンピュータを情報処理装置として機能させるデータ配信プログラム、及び当該データ配信プログラムを記録したコンピュータ読み取り可能な記録媒体を含むことができる。コンピュータ等が読み取り可能な記録媒体には、データやプログラム等の情報を電気的、磁気的、光学的、機械的、または化学的作用によって蓄積し、コンピュータ等から読み取ることができる記録媒体をいう。
【発明の効果】
【０００９】
開示のデータ配信システムによれば、ネットワーク上に格納されるデータ量を低減し、クライアントへのコンテンツ到達までの遅延時間の長期化を防止することができる。
【図面の簡単な説明】
【００１０】
【図１】データ配信システムの構成例を示す図である。
【図２】配信ノード群におけるコンテンツの分散配置の例を示す図である。
【図３】配信ノード群に含まれる各ノードのハードウェア構成の例を示す図である。
【図４】配信ノード群に含まれる各ノードの機能構成例を示す図である。
【図５Ａ】配信ノード群情報の例を示す図である。
【図５Ｂ】上位隣接ノード情報及び下位隣接ノード情報の例を示す図である。
【図６】配信ノード群生成処理の例を説明するための図である。
【図７】参加クエリ，参加クエリ応答，参加確定通知，及び生成完了通知に含まれる情報の例を示す図である。
【図８Ａ】配信ノード群生成処理においてデータ配信システム内の各ノードにおいて実行される処理のフローチャートの例である。
【図８Ｂ】配信ノード群生成処理においてデータ配信システム内の各ノードにおいて実行される処理のフローチャートの例である。
【図８Ｃ】配信ノード群生成処理においてデータ配信システム内の各ノードにおいて実行される処理のフローチャートの例である。
【図９】配信コンテンツ分散配置処理の例を示す図である。
【図１０】配信コンテンツの分割について説明するための図である。
【図１１Ａ】配信コンテンツの分散配置処理において各配信ノードで実行される処理のフローチャートの例を示す図である。
【図１１Ｂ】配信コンテンツの分散配置処理において各配信ノードで実行される処理のフローチャートの例を示す図である。
【図１２】クライアント群へのコンテンツ配信処理の例を示す図である。
【図１３Ａ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｂ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｃ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｄ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｅ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｆ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｇ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｈ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｉ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｊ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｋ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｌ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｍ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｎ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１３Ｏ】配信コンテンツがクライアント群に配信される様子を示す図である。
【図１４】ストリーム管理テーブルの例を示す図である。
【図１５】データ配信システムのコンテンツ配信処理における各配信ノードによって実行される処理のフローチャートの例である。
【図１６】データ配信システムのコンテンツ配信処理における各配信ノードによって実行される処理のフローチャートの例である。
【図１７】データ配信システムのコンテンツ配信処理における各配信ノードによって実行される処理のフローチャートの例である。
【図１８】データ配信システムのコンテンツ配信処理における各配信ノードによって実行される処理のフローチャートの例である。
【図１９】コンテンツの開始位置の要求と一時セグメントの削除処理との関係を説明するための図である。
【図２０】配信コンテンツへのコンテンツ配信要求が集中した場合の例を説明するための図である。
【図２１】スケールアウトを説明するための図である。
【図２２】スケールアウトが発生した場合のデータ配信システムのコンテンツ配信処理を説明するための図である。
【図２３】スケールアウト発生時のセグメント配置の例を示す図である。
【図２４】スケールアウト発生によるセグメント配置処理の例を説明するための図である。
【図２５Ａ】スケールアウト発生時のセグメント配置処理において各配信ノードで実行される処理のフローチャートの例である。
【図２５Ｂ】スケールアウト発生時のセグメント配置処理において各配信ノードで実行される処理のフローチャートの例である。
【図２５Ｃ】スケールアウト発生時のセグメント配置処理において各配信ノードで実行される処理のフローチャートの例である。
【図２５Ｄ】スケールアウト発生時のセグメント配置処理において各配信ノードで実行される処理のフローチャートの例である。
【発明を実施するための形態】
【００１１】
以下、図面に基づいて、本発明の実施の形態を説明する。以下の実施形態の構成は例示であり、本発明は実施形態の構成に限定されない。
【００１２】
＜第１実施形態＞
図１は、データ配信システムの構成例を示す図である。データ配信システムは、例えば、クライアント端末に映画やテレビ番組等の動画コンテンツや、楽曲などの音声コンテンツを配信するサービスを提供するシステムである。なお、コンテンツは、ＰＡＡＳ（Plat
form As A Service）やＳＡＡＳ(Software as a service)を含むデータ配信システムで配信されるデータの固まりであってもよい。データ配信システムには、複数のサーバ，ストレージ，ルータ等と、複数のクライアント群とが含まれる。以降、ストレージを管理するコンピュータやコンテンツを配信するサーバなど、ネットワーク上でコンテンツのミラーデータ（コピー）を格納し、クライアント端末に配信する能力を有する装置を「ノード」と称する。なお、図１では、ノードは、長方形で表わされている。
【００１３】
図１に示される例では、各クライアント群Ａ−Ｃは、配信コンテンツの実データを有するノードからは地理的に離れた位置にあり、さらに互いも地理的に充分離れた位置に存在する。例えば、実データを有するノードは東京、クライアント群Ａはニューヨーク、クライアントＢ群はロンドン、クライアントＣ群はシドニーに位置する。
【００１４】
第１実施形態では、データ配信システムは、コンテンツごと、及び／又は、クライアント群ごとにコンテンツを配信するための配信経路を形成する。図１に示される例では、ノード１−６がクライアント群Ａにコンテンツを配信するための配信経路を形成している。このように、或るクライアント群にコンテンツを配信するための配信経路を形成するノード群を、以降、配信ノード群と称する。配信ノード群は、クライアント群からネットワーク上の距離が離れるほど上位ノードであり、クライアント群からネットワーク上の距離が近いほど下位ノードである。また、下位ノードになるにつれて割り当てられるノード番号が大きくなる。
【００１５】
ネットワーク上の距離とは、例えば、ネットワーク上の２点間の中継ホップ数，応答時間，ＴＣＰ（Transmission Control Protocol）関連情報（ＲＴＴ（Round Trip Time）,
ＲＷＩＮ（Receive Window）），最大ＭＴＵ（Maximum Transmission Unit）長，データ
損失率，使用可能な回線帯域，スループット，地理的な距離，ノードのＣＰＵ（Central Processing Unit）使用率，ノードのメモリ使用率，ノードのスループット性能，ノード
の記憶媒体の読み書き速度のうち１つ以上の値を重みとして換算して表すものとする。ネットワーク上の距離は、２点間のコストとも称することができる。
【００１６】
また、第１実施形態において、配信ノード群では、コンテンツは各ノードに分散配置されている。
【００１７】
図２は、配信ノード群におけるコンテンツの分散配置の例を示す図である。図２に示される例では、各ノード番号は図１に示されるデータ配信システムの各ノード番号と対応する。１のコンテンツを複数に分割したブロックをセグメントと称する。各セグメントには、コンテンツが実行、すなわち動画や音声が再生された場合の時系列に従って、識別番号が先頭から順に付されている。第１実施形態では、各ノードが、コンテンツ（配信データ）が分割されて生成されるセグメント群（分割ブロック群）のうち、クライアント群からのコストに応じた所定の条件を満たすセグメントを記憶部に記憶することによって、コンテンツの分散配置が行われる。
【００１８】
図２に示される例では、先頭セグメント１はクライアント群Ａにネットワーク上の距離が最も近いノード６に配置される。セグメント２以降のセグメント２−６は、それぞれ、クライアント群Ａからネットワーク上の距離が近い順番で、ノード５，４，３，２，１に配置される。
【００１９】
次に、セグメント７−１２は、それぞれ、セグメント１−６とは反対に、クライアント群Ａからネットワーク上の距離が遠い順番で、ノード１−６に配置される。これ以降、最終セグメントまでの各セグメントは、配信ノード群の総ノード数の２倍の１２セグメント毎に、クライアント群Ａに近いノードの順番で配置された後クライアント群Ａから遠い順
番のノードに配置されることを繰り返して配置される。すなわち、コンテンツ番号が横軸、ノード番号が縦軸としてコンテンツのセグメントの配置図が作成された場合に、配置図上において、各ノードに配置されるセグメントは、図２に示されるような波形を形成する。図２に示されるような配信ノード群の各ノードに配置されるセグメントは、該コンテンツを配信する該配信ノード群に該ノードが参加している間、該ノードに保持され続ける。このような配信ノード群にノードが参加している間該ノードに保持され続けるセグメントを、以降、固定セグメントと称する。
【００２０】
各ノードは、クライアント端末（クライアント群）から配信要求を受信すると、まず、自ノードが保持する固定セグメント群のうち最も小さい番号のセグメントを下位の隣接ノードに送信する。次に、各ノードは、上位の隣接ノードから受信したセグメントと未送信の固定セグメントとを含む保持するセグメントのうち、最も小さい番号のセグメントを下位の隣接ノードに送信する。各ノードは、この処理を繰り返してクライアント群へのコンテンツ配信を実行する。すなわち、各ノードは、互いに協働し、番号の小さいセグメントから順にバケツリレーのようにして、コンテンツをクライアント群に配信する。コンテンツ配信開始後、バケツリレーで他のノード（上位のノード）から受信して次のノード（下位のノード）へ送信完了するまでの間、ノードに一時的に保持されるセグメントは、以降、一時セグメントと称される。また、固定セグメント及び一時セグメントを区別せずに各ノードが保持するセグメントを指す場合には、以降、保持セグメントと称する。
【００２１】
図２に示されるように波形に固定セグメントを配置することによって、配信ノード群の各ノードが同期送信した場合に、クライアントＡ群へのコンテンツ到着までの遅延時間を短くすることができる。詳細は後述する。
【００２２】
図３は、配信ノード群に含まれる各ノードのハードウェア構成の例を示す図である。配信ノード群に含まれるノードは、例えば、サーバマシン等の専用のコンピュータである。ノード１は、プロセッサ１０１，主記憶装置１０２，入力装置１０３，出力装置１０４，補助記憶装置１０５，媒体駆動装置１０６，ネットワークインタフェース１０７，及び外部記憶装置１１１を備え、これらがバス１０９により互いに接続されている情報処理装置である。
【００２３】
入力装置１０３は、例えば、キーボード，マウス等のポインティングデバイス，スキャナ等である。入力装置１０３から入力されたデータは、プロセッサ１０１に出力される。なお、ノード１に入力装置１０３は備えられていなくてもよく、この場合には、入力装置１０３は、ネットワーク管理者等によって外付けされる。
【００２４】
ネットワークインタフェース１０７は、ネットワークとの情報の入出力を行うインタフェースである。ネットワークインタフェース１０７は、有線のネットワーク、および、無線のネットワークと接続する。ネットワークインタフェース１０７は、例えば、光ファイバーインターフェースモジュール，ＮＩＣ（Network Interface Card），無線ＬＡＮ（Local Area Network）カード等である。ネットワークインタフェース１０７で受信されたデータ等は、プロセッサ１０１に出力される。
【００２５】
主記憶装置１０２は、プロセッサ１０１に、補助記憶装置１０５又は外部記憶装置１１１に格納されているプログラムをロードする記憶領域および作業領域を提供したり、バッファとして用いられたりする。主記憶装置１０２は、例えば、ＲＡＭ（Random Access Memory）のような半導体メモリである。
【００２６】
補助記憶装置１０５は、様々なプログラムや、各プログラムの実行に際してプロセッサ１０１が使用するデータを格納する。補助記憶装置１０５は、ノード１に内蔵されており
、例えば、ＥＰＲＯＭ（Erasable Programmable ROM）、又はハードディスクドライブ（Hard Disc Drive）である。補助記憶装置１０５は、例えば、オペレーティングシステム（ＯＳ），コンテンツを配信するためのデータ配信プログラム，その他様々なアプリケーションプログラムを保持する。
【００２７】
媒体駆動装置１０６は、可搬記録媒体１１０を駆動し、可搬記録媒体１１０に記録される様々なプログラムやデータを読み出し、プロセッサ１０１に出力する。媒体駆動装置１０６に駆動される可搬記録媒体１１０は、例えば、ＵＳＢ（Universal Serial Bus）フラッシュメモリ，ＣＤ（Compact Disc），又はＤＶＤのような記録媒体である。なお、媒体駆動装置１０６は、ノード１に備えられていなくともよい。
【００２８】
外部記憶装置１１１は、ノード１に外付けされており、データ配信システムで配信されるコンテンツまたはコンテンツのセグメントを保持する。外部記憶装置１１１は、例えば、ＨＤＤであり、補助記憶装置１０５よりも容量が大きい。なお、ノード１に内蔵される補助記憶装置１０５の容量が十分に大きい場合には、外部記憶装置１１１は用いらないこともある。
【００２９】
プロセッサ１０１は、例えば、ＣＰＵ（Central Processing Unit）や、ＤＳＰ（Digital Signal Processor）である。プロセッサ１０１は、補助記憶装置１０５や外部記憶装
置１１１に保持されたＯＳや様々なアプリケーションプログラムを主記憶装置１０２にロードして実行することによって、様々な処理を実行する。また、プロセッサ１０１は、媒体駆動装置１０６によって読み出された可搬記録媒体１１０に記録されたアプリケーションプログラムを主記憶装置１０２にロードして実行したり、データを処理したりする。
【００３０】
出力装置１０４は、プロセッサ１０１の処理の結果を出力する。出力装置１０４は、ディスプレイ等を含む。出力装置１０４は、ノード１に備えられてなくてもよく、必要な時に外付けされてもよい。
【００３１】
例えば、ノード１は、プロセッサ１０１が補助記憶装置１０５に保持されるデータ配信プログラムを主記憶装置１０２にロードして実行する。ノード１は、データ配信プログラムの実行を通じて、ネットワークインタフェース１０７を介して配信ノード群に参加する。また、ノード１は、データ配信プログラムの実行を通じて、該配信ノード群においてクライアント端末に配信されるコンテンツのセグメントの一部を補助記憶装置１０５又は外部記録装置１１１に保持する。さらに、ノード１は、データ配信プログラムの実行を通じて、クライアント端末からの配信要求に応じて、補助記憶装置１０５又は外部記憶装置１１１に保持されるコンテンツのセグメントを配信する。
【００３２】
なお、ノード１として機能する情報処理装置は、サーバマシンのような専用のコンピュータに限定されず、十分なメモリ資源を有するルータやレイヤ３スイッチのような中継装置であってもよい。
【００３３】
図４は、配信ノード群に含まれる各ノードの機能構成例を示す図である。配信ノード群に含まれる各ノードの機能構成は共通する。ノード１は、プロセッサ１０１が補助記憶装置１０５又は外部記録装置１１１に保持されるデータ配信プログラムの実行を通じて、クエリ処理部１１，隣接ノード情報取得部１２，配信ノード群情報管理部１３，固定セグメント取得部１４，一時セグメント管理部１５，ルーティング部１６，テーブル管理部１７，及びセグメント送信部１９として動作する。ただし、第１実施形態では、各機能ブロックが全てソフトウェア処理により実現されていると仮定しているが、機能ブロックそれぞれに対応するプロセッサや信号処理回路等を用いて、ハードウェアで図４に示される構成を実現してもよい。
【００３４】
クエリ処理部１１は、他のノードから受信したクエリ，クエリ応答，通知等の種別を判別し、種別に応じた処理を実行する。例えば、データ配信システムにおいて用いられるクエリには、配信ノード群への参加を要求する参加クエリ，配信コンテンツの配置を要求するコンテンツ配置クエリ，コンテンツの配信開始を要求するコンテンツン配信開始クエリ等がある。クエリ処理部１１の処理の詳細については、後述のフローチャート等で説明される。クエリ処理部１１は、例えば、クエリ処理部に相当する。
【００３５】
隣接ノード情報取得部１２は、配信ノード群の上位隣接ノード及び下位隣接ノードの内能及び外能の情報を取得する。内能とは、ノードの内部処理の能力である。隣接ノードの内能の情報には、例えば、ＣＰＵ使用率，メモリ使用率，スループット性能，及び記憶媒体の読み書き速度等が含まれる。これらの隣接ノードの内能の情報は、隣接ノード情報取得部１２が隣接ノードに問い合わせることによって取得される。また、外能とは、ノードの外部のノードとの処理の能力である。隣接ノードの外能の情報は、例えば、ホップ数，応答時間，ＴＣＰ関連情報（ＲＴＴ、ＲＷＩＮ），最大ＭＴＵ長，データ損失率，使用可能な回線帯域，スループット等である。隣接ノード情報取得部１２は、例えば、ｐｉｎｇやｔｒａｃｅｒｏｕｔｅ等のソフトウェアを用いて隣接ノードの外能の情報を取得する。取得された隣接ノードの内能及び外能の情報は、隣接ノードとのネットワーク上の距離（コスト）を決定するために用いられる情報であって、後述の配信ノード群情報に格納される。
【００３６】
配信ノード群情報管理部１３は、ノード１が所属する配信ノード群に関する情報である、後述の配信ノード群情報を管理（生成、更新、削除等）する。固定セグメント取得部１４は、コンテンツ配置クエリを受信した場合に、自ノードが固定で保持すべきセグメントを判定し、該セグメントを補助記憶装置１０５又は外部記憶装置１１０に格納する。固定セグメント取得部１４の処理の詳細については、後述のフローチャート等で説明される。固定セグメント取得部１４は、例えば、固定セグメント取得部に相当する。
【００３７】
一時セグメント管理部１５は、隣接ノードから受信した一時セグメントを管理する。例えば、一時セグメント管理部１５は、下位の隣接ノードへの送信が完了した一時セグメントの削除を行う。一時セグメント管理部１５は、例えば、一時セグメント管理部に相当する。
【００３８】
ルーティング部１６は、各種クエリやクエリ応答、セグメント等、ノード１から送信されるデータのルーティングを行う。テーブル管理部１７は、ノード１が所属する配信ノード群のコンテンツ配信状況を管理する、後述のストリーム管理テーブル１８３を管理（生成、更新、削除等）する。セグメント送信部１９は、コンテンツのセグメントを下位隣接ノード又はクライアント群に送信する。
【００３９】
記憶部１８は、データ配信プログラムの実行を通じて、又は、静的に補助記憶装置１０５又は／及び外部記憶装置１１１の記憶領域に生成される。記憶部１８には、一時セグメントバッファ１８１，配信ノード群情報１８２，ストリーム管理テーブル１８３，及び固定セグメント群１８４が含まれる。一時セグメントバッファ１８１は、例えば、第２の記憶部に相当する。
【００４０】
一時セグメントバッファ１８１は、他のノードから受信した一時セグメントを格納するバッファである。固定セグメント群１８４は、ノード１が担当する固定セグメントである。
【００４１】
図５Ａ及び図５Ｂは、配信ノード群情報の例を示す図である。配信ノード群情報は、ノ
ード１が参加している配信ノード群ごとに生成される。
【００４２】
配信ノード群情報には、配信ノード群番号，該配信ノード群内の総ノード数，該配信ノード群における自ノードの位置（ノード番号），上位隣接ノード情報，下位隣接ノード情報，配信クライアント群の番号，配信コンテンツ情報が含まれる。
【００４３】
配信ノード群番号は、配信ノード群を識別するための番号である。配信ノード群における自ノードの位置は、配信ノード群においてクライアント群からネットワーク上の距離が離れている順番を示す番号である。この配信ノード群における自ノードの位置を示す番号は、ノード番号とも称される。第１実施形態においては、配信クライアント群にネットワーク上の距離が最も離れたノードを「１」とし、配信クライアント群にネットワーク上の距離が近いノードになるにつれて大きい番号が順に付される。自ノードのノード番号は、配信ノード群生成処理を通じて決定される（後述）。
【００４４】
データ配信システム内の各クライアント群には、識別するための番号が予め割り当てられている。配信クライアント群の番号は、該配信ノード群からのコンテンツ配信を受信するクライアント群に割り当てられている番号である。配信ノード群番号，配信ノード群内の総ノード数，自ノードのノード番号，配信クライアント群の番号は、それぞれ配信ノード群生成処理を通じて取得される情報である。
【００４５】
配信コンテンツ情報は、該配信ノード群によって配信クライアント群に配信されるコンテンツに関する情報である。配信コンテンツ情報には、コンテンツ番号，コンテンツビットレート，総セグメント数，固定セグメント番号，一時セグメント番号，空セグメント番号，総コンテンツ容量，総固定セグメント容量，総一時セグメント容量，及び総保持セグメント容量が含まれる。コンテンツ番号は、配信ノード群によって配信されるコンテンツの識別番号である。以降、配信ノード群によって配信されるコンテンツは、配信コンテンツとも称される。コンテンツビットレートは、配信コンテンツの配信に要求されるビットレートである。
【００４６】
配信コンテンツは、所定のサイズの複数のセグメントに分割され、図２で示されるように、各セグメントは配信ノード群の各ノードによって分散して保持される。各セグメントには、配信コンテンツの先頭から順番に識別番号が付されている。
【００４７】
総セグメント数は、配信コンテンツに含まれるセグメントの総数である。固定セグメント番号は、自ノードが保持する固定セグメントの番号のリストである。一時セグメント番号は、自ノードが保持する一時セグメントの番号のリストである。空セグメント番号は、配信コンテンツのセグメントのうち、自ノードが保持していないセグメントの番号リストである。総固定セグメント容量は、自ノードが保持する固定セグメント群の総容量である。総一時セグメント容量は、自ノードが保持する一時セグメント群の総容量である。総保持セグメント容量は、自ノードが保持する固定セグメント群と一時セグメント群との総容量である。一時セグメントは送信完了に伴う削除や追加等によって変更があるため、一時セグメントとなるセグメントに変更がある度に、一時セグメント番号，総一時セグメント容量，及び総保持セグメント容量は更新される。
【００４８】
図５Ｂは、上位隣接ノード情報及び下位隣接ノード情報の例を示す図である。配信ノード群において、自ノードのノード番号の前後の番号を有する配信ノードを、自ノードの配信ノード群における隣接ノードと、定義する。最上位のノードと最下位のノードとを除いて、配信ノード群における各配信ノードには、上位隣接ノードと下位隣接ノードとが存在する。最上位のノードには、下位隣接ノードのみが存在する。最下位のノードには、上位隣接ノードのみが存在する。
【００４９】
各ノードは、上位隣接ノードと下位隣接ノードと、それぞれについて、隣接ノード情報を有する。隣接ノード情報には、隣接ノードとのネットワーク上の距離を求めるために必要な情報が含まれる。例えば、上位隣接ノード情報には、ノード間のホップ数，ノード間の応答時間，ノード間のＴＣＰ関連情報（ＲＴＴ，ＲＷＩＮ），ノード間の最大ＭＴＵ長,ノード間のデータ損失率，ノード間で使用可能な回線帯域，ノード間のスループット，
ノード間の地理的距離，上位隣接ノードのＣＰＵ使用率，上位隣接ノードのメモリ使用率，上位隣接ノードのスループット性能，上位隣接ノードの記憶媒体の読み書き速度，及び上位隣接ノードのＩＰアドレスが含まれる。
【００５０】
（配信ノード群生成処理）
図６は、配信ノード群生成処理の例を説明するための図である。図６では、便宜上、ノードは円で示されている。図６では、５台のノードが配信ノード群を生成する例が示される。配信ノード群の生成に係る処理は、配信ノード群生成処理と称される。
【００５１】
まず、配信ノード群が生成される際には、データ配信システムの管理者等によって、入力装置から、又は、ネットワークを介して、データ配信システムに属するノードに、配信ノード群生成指示が入力される。配信ノード群生成指示が入力されたノードは、その配信ノード群においてノード番号が１の配信ノードとなる。なお、配信ノード群生成指示が入力されるノードは、データ配信システムの管理者によって選択され、例えば、オリジナルのコンテンツが格納されるノードの近傍のノードであってもよいし、オリジナルのコンテンツが格納されるノード自体であってもよい。
【００５２】
ノード番号「１」の配信ノードは（以降、単に「配信ノード１」）、配信ノード群への参加を要求する参加クエリを送信する。参加クエリの流れは、図６中で実線の矢印で示される。参加クエリには、例えば、配信ノード群に参加するための参加条件、配信ノード群生成処理の終了条件等が含まれる。参加クエリは、例えば、データ配信システムに割り当てられるマルチキャストアドレスを用いて送信され、配信ノード１の近傍に位置するノードに受信される。
【００５３】
配信ノード１の近傍のノードは、参加クエリを受信すると、配信ノード群への参加条件を満たしているか否かを判定し、満たしている場合には、配信ノード１に参加クエリ応答を送信する。参加クエリ応答は、例えば、参加クエリの送信元ＩＰアドレスを宛先とするユニキャストパケットとして送信される。図６中では、参加クエリ応答の流れは、破線の矢印で示される。
【００５４】
配信ノード１は、最初に受信した参加クエリ応答の送信元のノードをノード番号「２」の配信ノードに決定する。配信ノード１が最初に受信した参加クエリ応答の送信元のノードが、配信ノード１とのネットワーク上の距離が一番近いノードであることが暗示されるからである。配信ノード１は、最初に受信した参加クエリ応答の送信元のノードにノード番号「２」で配信ノード群に参加することが決定された旨を通知する参加確定通知を送信する。参加確定通知は、例えば、最初に受信された参加クエリ応答の送信元ＩＰアドレス宛てにマルチキャストパケットとして送信される。図６中では、便宜上、参加確定通知の流れの表示は省略されている。配信ノード１は、それ以降に受信する参加クエリ応答は廃棄する。該参加確定通知を受信したノードは、以降、該配信ノード群のノード番号「２」の配信ノード（以降、単に「配信ノード２」）として処理を行う。なお、配信ノード１は、所定時間経過しても何れのノードからも参加クエリ応答を受信しない場合には、再度参加クエリを送信する。所定回数参加クエリを送信しても、配信ノード１が所定時間中に何れのノードからも参加クエリ応答を受信できない場合には、配信ノード１は、配信ノード群生成処理を終了する。
【００５５】
配信ノード２は、配信ノード１から参加確定通知を受信すると、参加クエリを送信する。参加クエリは、配信ノード２の近傍に位置するノードによって受信され、配信ノード２は、参加条件を満たすノードから参加クエリ応答を受信する。なお、このとき、既に該配信ノード群に参加しているノード（この場合には、配信ノード１）は、配信ノード２から参加クエリを受信しても、参加クエリ応答を配信ノードに送信せずに、受信した参加クエリを廃棄する。配信ノード２は、最初に受信した参加クエリ応答の送信元のノードに、ノード番号「３」の配信ノードとして配信ノード群に参加が決定した旨の参加確定通知を送信する。以降、配信ノード２は、参加クエリ応答を受信しても廃棄する。
【００５６】
該参加確定通知を受信したノードは、以降、該配信ノード群のノード番号「３」の配信ノード（以降、単に「配信ノード３」）として処理を行う。以降、配信ノード３は、配信ノード１及び配信ノード２と同様にして、参加クエリを送信し、最初に受信した参加クエリ要求の送信元のノードをノード番号「４」の配信ノード（以降、単に「配信ノード４」）として決定し、該ノードに参加確定通知を送信する処理を実行する。配信ノード４も同様の処理を行い、ノード番号「５」の配信ノード（以降、単に「配信ノード５」）が決定される。
【００５７】
参加クエリによって各配信ノードに通知される配信ノード群生成処理の終了条件が、例えば、配信ノード数が５台である場合には、配信ノード５は、終了条件が満たされたことを検知する。終了条件が満たされた場合には、配信ノード５は、配信ノード群生成処理の完了を通知する生成完了通知を送信する。生成完了通知には、例えば、該配信ノード群に含まれる配信ノードの総数が含まれる。生成完了通知は、例えば、参加クエリと同じマルチキャストアドレスを用いて、各配信ノードに転送される。なお、生成完了通知は、例えば、配信ノード５から配信ノード４、配信ノード４から配信ノード３、配信ノード３から配信ノード２、配信ノード２から配信ノード１、というように、上位の隣接ノードに次々と転送されていってもよい。生成完了通知を全配信ノードが受信すると、配信ノード群生成処理が終了する。生成完了通知によって、配信ノード群の各配信ノードは、配信ノード群に含まれるノードの総数を取得する。
【００５８】
図７は、参加クエリ，参加クエリ応答，参加確定通知，及び生成完了通知に含まれる情報の例を示す図である。参加クエリには、例えば、配信ノード群番号，配信クライアント群番号，参加条件，配信ノード群生成処理の終了条件，クエリ送信時点での参加ノード数，及び最小配信能力が含まれる。
【００５９】
配信ノード群番号は、該参加クエリを用いる配信ノード群生成処理によって生成される配信ノード群を識別するための番号である。配信クライアント群番号は、参加クエリを用いる配信ノード群生成処理によって生成される配信ノード群がコンテンツを配信するクライアント群を識別するための番号である。
【００６０】
参加条件は、該参加クエリを用いる配信ノード群生成処理によって生成される配信ノード群に参加するための条件である。参加条件は、例えば、ノードの外能及び内能の基準値、配信品質等で定義されている。配信品質は、動画や音声コンテンツ再生が途切れないために必要とされるノード間の配信能力であり、例えば、データ伝送速度（ｂｐｓ等）である。
【００６１】
配信ノード群生成処理の終了条件は、例えば、配信ノード群の上限ノード数，ノードが位置する地域等で定義されている。配信ノード群番号，配信クライアント群番号，参加条件，及び配信ノード群生成処理の終了条件は、データ配信システムの管理者によって指定され、配信ノード群生成指示とともに配信ノード１に入力される。この他に、配信ノード
群生成指示とともに、配信コンテンツのコンテンツ番号，オリジナルの配信コンテンツを有するノードのＩＰアドレス等も入力される。また、配信ノード群番号，配信クライアント群番号，参加条件，及び配信ノード群生成処理の終了条件は、参加クエリを送信する各配信ノードによって書き換えられることなく、全配信ノードに通知される。
【００６２】
クエリ送信時点での参加ノード数は、すなわち、参加クエリを送信する配信ノードの配信ノード番号である。これによって、参加クエリを受信するノードに、現在配信ノード群に参加しているノード数を通知する。また、参加クエリを受信したノードは、自ノードに割り当てられる予定のノード番号が通知された参加ノード数に１を加算した番号であることを取得する。
【００６３】
最小配信能力は、配信ノード１から該参加クエリの送信元ノードまでの各配信ノード間の配信能力（ｂｐｓ）の最小値である。配信能力は、例えば、各配信ノード間で使用可能な回線帯域である。最小配信能力は、新たな配信ノードが参加クエリを送信する際に、受信した参加クエリに含まれる最小配信能力と上位隣接ノードとの間の配信能力とを比較して、上位隣接ノードとの間の配信能力の方が小さい場合に、上位隣接ノードとの間の配信能力で更新する。
【００６４】
クエリ送信時点での参加ノード数及びクエリ送信ノードのＩＰアドレスは、各配信ノードにおいて参加クエリが送信される度に書き換えられる。最小配信能力は、新たに参加クエリを送信する配信ノードと上位隣接ノードとの間の配信能力が、該配信ノードが受信した参加クエリに含まれる最新配信能力の値を下回った場合に、書き換えられる。
【００６５】
参加クエリに対する応答である参加クエリ応答には、例えば、配信ノード群番号，配信クライアント群番号，該参加クエリ応答の送信元ノードのノード番号，及び該参加応答クエリの送信元ノードのＩＰアドレスが含まれる。配信ノード群番号及び配信クライアント群番号は、それぞれ参加クエリに含まれるものと同じ番号であり、参加クエリと参加クエリ応答とで整合性を保つためのものである。参加クエリ応答の送信元ノードのノード番号は、参加クエリ応答の送信元ノードが配信ノード群に参加する場合に割り当てられる予定のノード番号である。
【００６６】
参加クエリ応答の送信元ノードのＩＰアドレスによって、該参加クエリ応答に対応する参加クエリの送信元ノードに、参加クエリ応答の送信元ノードのＩＰアドレスを通知することができる。このとき、参加クエリ応答が最初に対応する参加クエリの送信元ノードに受信された場合には、該参加クエリの送信元ノードは下位隣接ノードのＩＰアドレスを取得することになる。すなわち、参加クエリ応答の送信元ノードのＩＰアドレスは、該参加クエリ応答が参加クエリの送信元ノードに最初に到着した場合に、参加クエリの送信元ノードの配信ノード群情報（下位隣接ノード情報）に格納される。
【００６７】
参加確定通知は、配信ノード群に参加が決定したノードに送信されるメッセージであり、参加クエリを送信した配信ノードから、該参加クエリ対して参加クエリ応答を最初に受信されたノードに対して送信される。参加確定通知には、例えば、配信ノード群番号，配信クライアント群番号，決定された配信ノード番号，及び参加確定通知の送信元ノードのＩＰアドレスが含まれる。
【００６８】
配信ノード群番号及び配信クライアント群番号は、参加クエリ及び参加クエリ応答に含まれるものと同じ番号であり、参加クエリ，参加クエリ応答，及び参加確定通知とで整合性を保つためのものである。
【００６９】
決定されたノード番号は、参加確定通知を受信したノードに割り当てられるノード番号
である。参加確定通知に含められる決定されたノード番号には、参加確定通知を送信する配信ノードのノード番号に１を加算した番号が格納される。参加確定通知の送信元ノードのＩＰアドレスは、参加確定通知を受信したノードにとって、上位隣接ノードのＩＰアドレスであって、配信ノード群情報（上位隣接ノード情報）に格納される。
【００７０】
生成完了通知は、配信ノード群生成処理の終了条件を満たしたことを検知した配信ノード、すなわち、配信ノード群において最下位の配信ノードが配信ノード群生成処理の終了を他の配信ノードに通知するために送信するメッセージである。生成完了通知には、例えば、配信ノード群番号，配信クライアント群番号，総ノード数，及び配信ノード群内最小配信能力が含まれる。
【００７１】
配信ノード群番号及び配信クライアント群番号は、参加クエリ，参加クエリ応答，及び参加確定通知に含まれるものと同じ番号であり、参加クエリ，参加クエリ応答，参加確定通知，及び生成完了通知とで整合性を保つためのものである。
【００７２】
総ノード数は、配信ノード群に参加する配信ノードの総数である。生成完了通知に含められる総ノード数には、生成完了通知を送信するノード、すなわち、配信ノード群の最下位の配信ノードに割り当てられたノード番号が格納される。
【００７３】
配信ノード群内最小配信能力は、各配信ノード間の配信能力のうち最小の配信能力である。配信ノード群最小能力として格納される情報は、生成完了通知を送信する配信ノード群の最下位の配信ノードによる、参加クエリで通知された最小配信能力と、自ノードと自ノードの上位隣接ノードとの間の配信能力との比較によって決定される。比較の結果、最下位の配信ノードと上位隣接ノードとの間の配信能力の方が小さい場合には、生成完了通知の配信ノード群内最小配信能力には、最下位の配信ノードと上位隣接ノードとの間の配信能力が格納される。比較の結果、参加クエリで通知された最小配信能力の方が小さい場合には、生成完了通知の配信ノード群内最小配信能力には、参加クエリで通知された最小配信能力が格納される。
【００７４】
生成完了通知によって、総ノード数及び配信ノード群内最小配信能力が配信ノード群内の全配信ノードに通知される。総ノード数及び配信ノード群内最小配信能力は、後述の配信コンテンツの配置処理に用いられる情報である。
【００７５】
参加クエリは、マルチキャストアドレスを用いて送信される。参加クエリ応答は、参加クエリの送信元に宛ててユニキャストを用いて送信される。参加決定通知は、参加クエリ応答の送信元に宛ててユニキャストアドレスを用いて送信される。生成完了通知は、マルチキャストアドレス、ユニキャストアドレスの何れを用いて送信されてもよく、データ配信システムの管理者によって何れを用いるか選択されてもよい。また、参加クエリ，参加クエリ応答，参加確定通知，及び生成完了通知を区別するために、例えば、それぞれには識別番号が割り当てられている。図７において示された参加クエリ，参加クエリ応答，参加確定通知，及び生成完了通知に含められる情報は、一例であり、図７に示される例に限定されない。データ配信システムの管理者は、これらに含められる情報を編集（追加，削除）することができる。
【００７６】
図８Ａ，図８Ｂ，及び図８Ｃは、配信ノード群生成処理においてデータ配信システム内の各ノードにおいて実行される処理のフローチャートの例である。図８Ａ、図８Ｂ，及び図８Ｃに示されるフローは、パケットを受信すると開始される。
【００７７】
ＯＰ１では、クエリ処理部１１は、受信したパケットが配信ノード群生成指示であるか否かを判定する。配信ノード群生成指示は、例えば、データ配信システムの管理者からネ
ットワークを介するネットワークインタフェース１０７を通じて入力される。なお、配信ノード群生成指示は、データ配信システムの管理者から入力装置１０３を通じて入力されてもよい。配信ノード群生成指示とともに、例えば、配信ノード群番号，配信クライアント群番号，配信コンテンツのコンテンツ番号，参加条件，配信ノード群生成処理の終了条件，オリジナルの配信コンテンツを保持するノードのＩＰアドレスがノードに入力される。受信パケットが配信ノード群生成指示である場合には（ＯＰ１：Ｙｅｓ）、処理がＯＰ２に進む。受信パケットが配信ノード群生成指示でない場合には（ＯＰ１：Ｎｏ）、処理が図８ＢのＯＰ１１に進む。
【００７８】
ＯＰ２では、クエリ処理部１１は、図７において示された情報を含めて、参加クエリを送信する。参加クエリは、ルーティング部１６においてルーティングされてからネットワークインタフェース１０７を通じて送信される。以降、送信処理の際のルーティング部１６によるルーティングについては説明が省略されるが、何れのパケットの送信の際でも、ルーティング部１６によるルーティングは実行される。参加クエリを送信すると、クエリ処理部１１は、タイマーを開始させる。なお、ＯＰ２の処理がＯＰ１の処理に続けて実行される場合には、ＯＰ２において、クエリ処理部１１は、ＯＰ１において配信ノード群生成指示を受信したので、自ノードのノード番号を１に決定し、参加クエリを送信する。ＯＰ３では、クエリ処理部１１は、ＯＰ２において送信した参加クエリに対応する参加クエリ応答の受信の有無を判定する。参加クエリ応答の受信がある場合には（ＯＰ３：Ｙｅｓ）、処理がＯＰ５に進む。参加クエリ応答の受信が無い場合には（ＯＰ３：Ｎｏ）、処理がＯＰ４に進む。
【００７９】
ＯＰ４では、クエリ処理部１１は、タイムアウトか否かを判定する。クエリ処理部１１は、予め設定される所定時間が経過しても参加クエリ応答の受信が無い場合、すなわち、タイムアウトした場合には（ＯＰ４：Ｙｅｓ）、図８Ａに示される処理のフローを終了する。予め設定される所定時間が経過していない場合には、すなわち、タイムアウトしていない場合には（ＯＰ４：Ｎｏ）、処理がＯＰ３に戻り、参加クエリ応答を受信するまで、又は、タイムアウトするまでＯＰ３及びＯＰ４の処理が繰り返される。
【００８０】
ＯＰ５では、クエリ処理部１１は、受信した参加クエリ応答で特定される配信ノード群の下位隣接ノードが既に登録されているか否かを判定する。すなわち、ＯＰ５では、クエリ処理部１１は、受信した参加クエリ応答は、自ノードが最初に受信した参加クエリ応答であるか否かを判定する。受信した参加クエリ応答で特定される配信ノード群の下位隣接ノードが既に登録されているか否かは、配信ノード群情報管理部１３が記憶部１８に格納される配信ノード群情報を確認することによって判定される。
【００８１】
受信した参加クエリ応答で特定される配信ノード群の下位隣接ノードが既に登録されている場合には（ＯＰ５：Ｙｅｓ）、クエリ処理部１１は、該参加クエリ応答を廃棄し、図８Ａに示される処理のフローを終了する。受信した参加クエリ応答で特定される配信ノード群の下位隣接ノードが登録されていない場合には（ＯＰ５：Ｎｏ）、受信した参加クエリ応答が、最初に受信した参加クエリ応答であることを検知し、処理がＯＰ６に進む。
【００８２】
ＯＰ６では、クエリ処理部１１は、受信した参加クエリ応答が最初に受信した参加クエリ応答であるので、該参加クエリ応答の送信元ノードを自ノードの下位隣接ノードに決定し、該参加クエリ応答の送信元ノードに参加確定通知を送信する。自ノードのノード番号をｎ（ｎ：０を含まない自然数）であるとすると、参加確定通知によって参加クエリ応答の送信元ノードに通知されるノード番号はｎ＋１となる。
【００８３】
ＯＰ７では、配信ノード群情報管理部１３は、配信ノード群情報を生成又は更新する。自ノードがノード番号「１」の配信ノードである場合には、配信ノード群情報管理部１３
は、配信ノード群生成指示によって指示された配信ノード群の配信ノード情報を生成する。自ノードがノード番号「１」以外の配信ノードである場合には、配信ノード群情報管理部１３は、参加クエリ応答によって特定される配信ノード群の配信ノード群情報を更新する。具体的には、配信ノード群情報管理部１３は、参加確定通知を送信したノードを、参加確定通知によって特定される配信ノード群の配信ノード群情報に、自ノードの下位隣接ノードとして登録する。すなわち、参加確定通知を送信したノードから受信した参加クエリ応答に含まれる送信元ノードのＩＰアドレスを参加クエリ応答によって特定される配信ノードの下位隣接ノードのＩＰアドレスとして配信ノード群情報に格納する。その後、隣接ノード情報取得部１２が、下位隣接ノードのＩＰアドレスを用いて、下位隣接ノードの情報（図５Ｂ参照）を取得する。下位隣接ノードの配信ノード群情報への登録が完了すると、図８Ａに示される処理のフローが終了する。
【００８４】
図８ＢのＯＰ１１では、クエリ処理部１１は、受信パケットが参加クエリであるか否かを判定する。受信パケットが参加クエリである場合には（ＯＰ１１：Ｙｅｓ）、処理がＯＰ１２に進む。受信パケットが参加クエリでない場合には（ＯＰ１１：Ｎｏ）、処理が図８ＣのＯＰ３１に進む。
【００８５】
ＯＰ１２では、クエリ処理部１１は、受信した参加クエリによって特定される配信ノード群の配信ノード群情報が記憶部１８に保持されているか否かを判定する。この判定は、記憶部１８に受信した参加クエリによって特定される配信ノード群の配信ノード群情報が有るか否かを、配信ノード群情報管理部１３が確認することによって行われる。受信した参加クエリによって特定される配信ノード群の配信ノード群情報が記憶部１８に保持されている場合には（ＯＰ１２：Ｙｅｓ）、既に自ノードが該配信ノード群に参加しているので、図８Ｂに示される処理のフローが終了する。受信した参加クエリによって特定される配信ノード群の配信ノード群情報が記憶部１８に保持されていない場合には（ＯＰ１２：Ｎｏ）、処理がＯＰ１３に進む。
【００８６】
ＯＰ１３では、クエリ処理部１１は、自ノードが参加クエリに含まれる参加条件を満たすか否かを判定する。自ノードが参加クエリに含まれる参加条件を満たす場合には（ＯＰ１３：Ｙｅｓ）、処理がＯＰ１４に進む。自ノードが参加クエリに含まれる参加条件を満たさない場合には（ＯＰ１３：Ｎｏ）、クエリ処理部１１は参加クエリを廃棄し、図８Ｂに示されるフローが終了する。
【００８７】
ＯＰ１４では、クエリ処理部１１は、例えば、図7に示される情報を含めて参加クエリ
応答を、参加クエリの送信元の配信ノードに送信する。参加クエリ応答を送信すると、クエリ処理部１１は、タイマーを開始させる。
【００８８】
ＯＰ１５では、クエリ処理部１１は、ＯＰ１４において送信した参加クエリ応答に対応する参加確定通知を受信したか否かを判定する。参加確定通知を受信した場合には（ＯＰ１５：Ｙｅｓ）、処理がＯＰ１７に進む。参加確定通知を受信していない場合には（ＯＰ１５：Ｎｏ）、処理がＯＰ１６に進む。
【００８９】
ＯＰ１６では、クエリ処理部１１は、タイムアウトか否かを判定する。クエリ処理部１１は、予め設定される所定時間が経過しても参加確定通知の受信が無い場合、すなわち、タイムアウトした場合には（ＯＰ１６：Ｙｅｓ）、ノード１は参加クエリによって特定される配信ノード群に参加できず、図８Ｂに示される処理のフローを終了する。予め設定される所定時間が経過していない場合には、すなわち、タイムアウトしていない場合には（ＯＰ１６：Ｎｏ）、処理がＯＰ１５に戻り、参加確定通知を受信するまで、又は、タイムアウトするまでＯＰ１５及びＯＰ１６の処理が繰り返される。
【００９０】
ＯＰ１７では、配信ノード群情報管理部１３は、参加確定通知によって特定される配信ノード群の配信ノード群情報を生成する。このとき、配信ノード群情報管理部１３は、参加確定通知に含まれるノード番号を自ノードのノード番号として配信ノード群情報に登録する。さらに、配信ノード群情報管理部１３は、参加確定通知の送信元の配信ノードのＩＰアドレスを参加確定通知によって特定される配信ノード群の上位隣接ノードのＩＰアドレスとして配信ノード群情報に登録する。その後、隣接ノード情報取得部１２が、上位隣接ノードのＩＰアドレスを用いて、上位隣接ノードの情報（図５Ｂ参照）を取得する。
【００９１】
ＯＰ１８では、クエリ処理部１１は、参加クエリに含まれる終了条件が満たされているか否かを判定する。終了条件が満たされている場合には（ＯＰ１８：Ｙｅｓ）、自ノードが最下位の配信ノードとなり配信ノード群生成処理を終了させるため、処理がＯＰ１９に進む。終了条件が満たされていない場合には（ＯＰ１８：Ｎｏ）、配信ノード群生成処理は継続するので、処理が図８ＡのＯＰ２に進み、クエリ処理部１１は参加クエリを送信して、ＯＰ３からＯＰ７の処理を行い、下位隣接ノードを決定する。
【００９２】
ＯＰ１９では、クエリ処理部１１は、終了条件が満たされているので、配信ノード群生成処理を終了させ、例えば、図７で示される情報を含めて、参加確定通知によって特定される配信ノード群の自ノードの上位隣接ノードに生成完了通知を送信する（ユニキャスト）。その後、図８Ｂに示される処理のフローが終了する。
【００９３】
図８ＣのＯＰ３１では、クエリ処理部１１は、受信パケットが生成完了通知か否かを判定する。受信パケットが生成完了通知である場合には（ＯＰ３１：Ｙｅｓ）、処理がＯＰ３３に進む。受信パケットが生成完了通知でない場合には（ＯＰ３１：Ｎｏ）、処理がＯＰ３２に進む。
【００９４】
ＯＰ３２では、クエリ処理部１１は、受信パケットが参加クエリ応答か否かを判定する。受信パケットが参加クエリ応答である場合には（ＯＰ３２：Ｙｅｓ）、処理が図８ＡのＯＰ５に進み、受信した参加クエリ応答によって特定される配信ノード群において自ノードの下位隣接ノードが登録されているか否かが判定される（ＯＰ５）。なお、ＯＰ３２において受信される参加クエリ応答は、最初に受信された参加クエリ応答でない可能性が高い。なぜなら、最初に受信される参加クエリ応答は図８ＡのＯＰ３において処理されるはずだからである。したがって、ＯＰ３２において受信される参加クエリ応答は図８ＡのＯＰ５の処理で廃棄される可能性が高い。
【００９５】
受信パケットが参加クエリ応答ではない場合には（ＯＰ３２：Ｎｏ）、受信パケットは配信ノード群生成処理に係るパケットではないので、図８Ｃに示される処理のフローが終了する。
【００９６】
ＯＰ３３では、クエリ処理部１１は、生成完了通知によって特定される配信ノード群の配信ノード群情報が記憶部１８に保持されているか否かを判定する。この判定は、配信ノード群情報管理部１３による記憶部１８内に保持される配信ノード群情報の確認結果に基づいて行われる。生成完了通知によって特定される配信ノード群の配信ノード群情報が記憶部１８に保持されている場合には（ＯＰ３３：Ｙｅｓ）、自ノードが該配信ノード群に参加しており、処理がＯＰ３５に進む。生成完了通知によって特定される配信ノード群の配信ノード群情報が記憶部１８に保持されていない場合には（ＯＰ３３：Ｎｏ）、自ノードが該配信ノード群に参加しておらず、処理がＯＰ３４に進む。
【００９７】
ＯＰ３４では、クエリ処理部１１は、自ノードは生成完了通知によって特定される配信ノード群に参加しておらず、該生成完了通知は不要なので、該生成完了通知を廃棄する。その後、図８Ｃに示される処理のフローが終了する。
【００９８】
ＯＰ３５では、受信した生成完了通知が自ノードの参加する配信ノード群の生成完了通知であるので、配信ノード群情報管理部１３は、生成完了通知に含まれる総ノード数と最小配信能力とを該当する配信ノード群情報に格納する。
【００９９】
ＯＰ３６では、クエリ処理部１１は、受信した生成完了通知によって特定される配信ノード群において自ノードの上位隣接ノードが存在するか否かを判定する。すなわち、クエリ処理部１１は、自ノードが受信した生成完了通知によって特定される配信ノード群において最上位の配信ノード（ノード番号「１」）か否かを判定する。この判定は、配信ノード群情報管理部１３による該当配信ノード群情報に上位隣接ノード情報が含まれるか否か、又は、該当配信ノード情報内のノード番号が「１」であるか否かの判定結果に基づいて行われる。該当配信ノード群情報に上位隣接ノード情報が含まれる場合、及び、該当配信ノード群情報のノード番号が「１」ではない場合には、該当配信ノード群に自ノードの上位隣接ノードが存在することが示される。一方、該当配信ノード群情報に上位隣接ノード情報が含まれない場合、及び、該当配信ノード群情報のノード番号が「１」である場合には、該当配信ノード群に自ノードの上位隣接ノードが存在しないことが示される。
【０１００】
受信した生成完了通知によって特定される配信ノード群において自ノードの上位隣接ノードが存在する場合には（ＯＰ３６：Ｙｅｓ）、該上位隣接ノードに生成完了通知を転送する必要があるため、処理がＯＰ３７に進む。受信した生成完了通知によって特定される配信ノード群において自ノードの上位隣接ノードが存在しない場合には（ＯＰ３６：Ｎｏ）、クエリ処理部１１は、受信した完成完了通知を転送せず、図８Ｃに示される処理が終了する。
【０１０１】
ＯＰ３７では、クエリ処理部１１は、受信した生成完了通知によって特定される配信ノード群の配信ノード群情報に含まれる上位隣接ノードに生成完了通知を転送する（ユニキャスト）。その後、図８Ｃに示される処理が終了する。
【０１０２】
図８Ｃに示される処理のフローでは、上位隣接ノードが存在する場合には、生成完了通知は上位隣接ノードに転送される、というように生成完了通知はユニキャストアドレスで送受信されている。これに変えて、生成完了通知は、マルチキャストアドレスを用いて送信されてもよい。生成完了通知にマルチキャストアドレスが用いられる場合には、自ノードが最下位の配信ノードのクエリ処理部１１は、図８ＢのＯＰ１９の処理において、マルチキャストアドレスを用いて生成完了通知を送信する。また、マルチキャストアドレスを用いた生成完了通知を受信した場合には、図８ＣのＯＰ３６及びＯＰ３７の処理が省略される。
【０１０３】
図６，図７，図８Ａ−図８Ｃにおいて説明されたように、第１実施形態では、データ配信システムの管理者から配信ノード群生成指示が入力されることによって、各ノードが自律的に動作して配信ノード群を生成する。
【０１０４】
（配信コンテンツ分散配置処理）
配置ノード生成処理によって配信ノード群が生成されると、次に、配信ノード群が配信する配信コンテンツを各配信ノードに分散配置するための配信コンテンツ分散配置処理が実行される。
【０１０５】
図９は、配信コンテンツ分散配置処理の例を示す図である。配信コンテンツ分散配置処理では、ノード番号「１」の配信ノードから順に各配信ノードに配信コンテンツが転送される。各配信ノードは、配信コンテンツが転送されてくると、自ノードに担当が割り当てられた配信コンテンツのセグメントを取得し、記憶部１８の固定セグメント群１８４に格
納する。各配信ノードは、取得したセグメントを配信コンテンツから削除し、下位隣接ノードに転送する。
【０１０６】
第１実施形態では、図２で説明されたように、配信コンテンツのセグメント配置マップが波形になるように、配信コンテンツが分散配置される。配信コンテンツのセグメント配置マップが図２の波形になるように配信コンテンツが配置される場合、ノード番号「ｎ」の配信ノードに割り当てられるセグメントは、以下の式１を満たす番号Ｓのセグメントと式２を満たす番号Ｓのセグメントとである。なお、以下の式１及び式２において、Ｎは、或る配信ノード群に含まれる配信ノードの総数（Ｎ：０を含まない自然数）である。ｎは、該配信ノードに含まれる或る配信ノードのノード番号（０＜ｎ≦Ｎ）である。変数ｉは、ｉ＝０，１，２，．．．である。
【数１】
0005732919.tif 000002
【０１０７】
図９に示される例では、配信ノード群には５台の配信ノードが含まれている。以下、図９に示される配信ノード群に、セグメント配置マップが図２に示されるような波形になるようにセグメントが配置される場合の配信コンテンツの分散配置処理について説明する。なお、図９では、ノード番号「ｎ」の配信ノードを、単に、配信ノードｎと称する。
【０１０８】
まず、配信ノード１は、オリジナルの配信コンテンツを保持するノードに対して、配信コンテンツ要求を送信し、配信コンテンツを取得する。配信コンテンツ要求には、例えば、要求する配信コンテンツのコンテンツ番号が含まれる。なお、配信ノード１がオリジナルの配信コンテンツを保持するノードである場合には、この処理は実行されない。
【０１０９】
配信ノード１は、配信コンテンツを取得すると、配信コンテンツをセグメントに分割する。配信コンテンツの分割方法については、図１０にて詳細に説明される。図９に示される例では、配信コンテンツが１４個のセグメントに分割されたものとする。各セグメントには、先頭のセグメントのセグメント番号を「１」として、先頭セグメントから順にセグメント番号が付される。
【０１１０】
配信ノード１は、配信コンテンツの自ノードの担当するセグメントを記憶部１８に格納する。図９に示される例の場合、配信ノード１は、式１を満たすセグメント５と式２を満たすセグメント６とを記憶部１８に保持し、配信コンテンツからセグメント５とセグメント６とを削除する。
【０１１１】
配信ノード１は、下位隣接ノードである配信ノード２に、配置クエリと、セグメント５とセグメント６とが削除された配信コンテンツとを送信する。配置クエリは、下位隣接ノードにセグメントの配置（取得）を要請するクエリである。配置クエリには、例えば、配信ノード群番号，配信クライアント群番号，配信コンテンツのコンテンツ番号，配信コンテンツのビットレート，総セグメント数，総コンテンツ容量等の、配信コンテンツに係る情報が含まれている。配置クエリ及び配信コンテンツは、それぞれユニキャストアドレスで送信される。
【０１１２】
配信ノード１から配置クエリと配信コンテンツとを受信すると、配信ノード２は、配信コンテンツから配信コンテンツの自ノードの担当するセグメントを記憶部１８に格納する。図９に示される例の場合、配信ノード２は、式１を満たすセグメント４と、式２を満たすセグメント７とを記憶部１８に保持し、受信した配信コンテンツからセグメント４とセ
グメント７とを削除する。自ノードの担当するセグメントを記憶部１８に格納すると、配信ノード２は、上位隣接セグメントである配信ノード１に配置クエリ応答を送信するとともに、下位隣接セグメントである配信ノード３に配置クエリと配信コンテンツ（セグメント４−７は削除）とを転送する。
【０１１３】
以下、配信ノード３，配信ノード４，配信ノード５も、配信ノード２と同様にして、それぞれ、自ノードが担当するセグメントを記憶部１８に格納する。ただし、配信ノード５では、最下位の配信ノードであるため、配置クエリ及び配信コンテンツの転送は行われない。ちなみに、配信ノード３が担当するセグメントは、式１を満たすセグメント３，１３と、式２を満たすセグメント８とである。配信ノード４が担当するセグメントは、式１を満たすセグメント２，１２と、式２を満たすセグメント９とである。配信ノード５が担当するセグメントは、式１を満たすセグメント１，１１と、式２を満たすセグメント１０とである。
【０１１４】
図１０は、配信コンテンツの分割について説明するための図である。配信コンテンツが要求するコンテンツビットレートをα（ｂｐｓ）、配信ノード群生成処理を通じて決定される配信ノード群内の最小配信能力をβ（ｂｐｓ）とする。α＜βである。配信コンテンツを配信する際に、最小配信能力である配信ノード間がボトルネックとなり、遅延が発生することを防ぐために、配信コンテンツは、コンテンツビットレートα以上であり最小配信能力β以下となる分割単位Ｘ（ｂｉｔ）で分割される。ただし、最後尾のセグメントは、分割単位Ｘ以下のサイズとする。
【０１１５】
配信コンテンツが分割されて生成されたセグメントの数をｍ、セグメント番号ｉのセグメントのサイズをＸ（ｉ）（ｉ＝０，１，．．．，ｍ）とすると、α≦Ｘ≦β，Ｘ（１）＝Ｘ（２）＝．．．＝Ｘ（Ｍ−１）＝Ｘ，及びＸ（ｍ）≦Ｘを満たすように、配信コンテンツは分割される。
【０１１６】
図１１Ａ及び図１１Ｂは、配信コンテンツの分散配置処理において各配信ノードで実行される処理のフローチャートの例を示す図である。図１１Ａに示されるフローは、配信ノードがパケットを受信すると開始される。
【０１１７】
ＯＰ４１では、クエリ処理部１１は、受信パケットが生成完了通知であるか否かを判定する。受信パケットが生成完了通知である場合には（ＯＰ４１：Ｙｅｓ）、処理がＯＰ４２に進む。受信パケットが生成完了通知出ない場合には（ＯＰ４１：Ｎｏ）、処理がＯＰ４７に進む。
【０１１８】
ＯＰ４２では、クエリ処理部１１は、自ノードのノード番号が「１」であるか否かを判定する。この判定は、配信ノード群情報管理部１３によって、受信した生成完了通知によって特定される配信ノード群の配信ノード情報内の自ノードのノード番号の確認結果に基づいて判定される。自ノードのノード番号が「１」である場合には（ＯＰ４２：Ｙｅｓ）、処理がＯＰ４３に進む。自ノードのノード番号が「１」でない場合には（ＯＰ４２：Ｎｏ）、図１１Ａに示される処理が終了する。
【０１１９】
ＯＰ４３では、クエリ処理部１１は、ノード番号「１」であるので、オリジナルの配信コンテンツを保持するノードに配信コンテンツ要求を送信する（ユニキャスト）。配信コンテンツ要求を送信するとともに、クエリ処理部１１は、タイマーを開始する。
【０１２０】
ＯＰ４４では、クエリ処理部１１は、配信コンテンツの受信処理が実行されているか否かを判定する。配信コンテンツの受信処理が実行されている場合には（ＯＰ４４：Ｙｅｓ）、処理がＯＰ４６に進む。配信コンテンツの受信処理が実行されていない場合には（Ｏ
Ｐ４４：Ｎｏ）、処理がＯＰ４５に進む。
【０１２１】
ＯＰ４５では、クエリ処理部１１は、タイムアウトか否かを判定する。クエリ処理部１１は、予め設定される所定時間が経過しても配信コンテンツの受信処理が開始されない場合、すなわち、タイムアウトした場合には（ＯＰ４５：Ｙｅｓ）、図１１Ａに示される処理のフローを終了する。予め設定される所定時間が経過していない場合には、すなわち、タイムアウトしていない場合には（ＯＰ４５：Ｎｏ）、処理がＯＰ４４に戻り、配信コンテンツの受信処理が開始されるまで、又は、タイムアウトするまでＯＰ４４及びＯＰ４５の処理が繰り返される。なお、自ノード（ノード番号「１」の配信ノード）がオリジナルの配信コンテンツを保持するノードである場合には、ＯＰ４３−ＯＰ４５の処理は省略される。
【０１２２】
ＯＰ４６では、クエリ処理部１１は、受信した配信コンテンツを、図１０において説明されたように、複数のセグメントに分割する。その後、処理が図１１ＢのＯＰ５２に進む。
【０１２３】
ＯＰ４７では、クエリ処理部１１は、受信パケットが配置クエリであるか否かを判定する。受信パケットが配置クエリである場合には（ＯＰ４７：Ｙｅｓ）、処理が図１１ＢのＯＰ５２に進む。なお、配置クエリが受信された場合には、配置クエリの後、配信コンテンツのセグメント群も受信する。受信パケットが配置クエリでない場合には（ＯＰ４７：Ｎｏ）、受信パケットは配信コンテンツの分散配置処理に係るパケットではないので、図１１Ａに示される処理のフローが終了する。
【０１２４】
図１１ＢのＯＰ５２では、固定セグメント取得部１４は、受信された配信コンテンツのセグメント群から、自ノードが担当するセグメントを記憶部１８に格納する。例えば、図２で示されるような分散配置の場合には、固定セグメント取得部１４は、式１を満たすセグメント番号のセグメント、式２を満たすセグメント番号のセグメントを自ノードが担当するセグメント（固定セグメント）として記憶部１８に格納する。さらに、固定セグメント取得部１４は、受信された配信コンテンツのセグメント群から自ノードが担当するセグメントを削除する。
【０１２５】
ＯＰ５３では、クエリ処理部１１は、受信した配信コンテンツのセグメントが残っているか否かを判定する。例えば、自ノードが最下位の配信ノードである場合には、最下位の配信ノードが担当する分のセグメント群だけを含む配信コンテンツが受信され、ＯＰ５２において、該セグメントの削除されてしまうため、受信した配信コンテンツのセグメントは残らない。受信した配信コンテンツのセグメントが残っている場合には（ＯＰ５３：Ｙｅｓ）、下位の配信ノードが存在し、処理がＯＰ５４に進む。受信した配信コンテンツのセグメントが残っていない場合には（ＯＰ５３：Ｎｏ）、下位の配信ノードは存在しておらず、配置クエリと配信コンテンツとを送信する必要がないため、処理がＯＰ５８に進む。
【０１２６】
ＯＰ５４では、クエリ処理部１１は、配置クエリと残りの配信コンテンツのセグメント群とを下位隣接ノードに送信する（ユニキャスト）。クエリ処理部１１は、配置クエリに例えば、配信ノード群番号，配信クライアント群番号，配信コンテンツのコンテンツ番号，配信コンテンツのビットレート，総コンテンツ容量等の、配信コンテンツに係る情報を含める。配置クエリの送信とともに、クエリ処理部１１は、タイマーを開始する。
【０１２７】
ＯＰ５５では、クエリ処理部１１は、配置クエリに対する応答である配置クエリ応答を下位隣接ノードから受信したか否かを判定する。配置クエリ応答を受信した場合には（ＯＰ５５：Ｙｅｓ）、処理がＯＰ５８に進む。配置クエリ応答を受信していない場合には（
ＯＰ５５：Ｎｏ）、処理がＯＰ５６に進む。
【０１２８】
ＯＰ５６では、クエリ処理部１１は、タイムアウトか否かを判定する。クエリ処理部１１は、予め設定される所定時間が経過しても配置クエリ応答が受信されない場合、すなわち、タイムアウトした場合には（ＯＰ５６：Ｙｅｓ）、処理がＯＰ５７に進む。予め設定される所定時間が経過していない場合には、すなわち、タイムアウトしていない場合には（ＯＰ５６：Ｎｏ）、処理がＯＰ５５に戻り、配置クエリ応答が受信されるまで、又は、タイムアウトするまでＯＰ５５及びＯＰ５６の処理が繰り返される。
【０１２９】
ＯＰ５７では、クエリ処理部１１は、配置クエリの再送回数が予め設定される上限回数を超えているか否かを判定する。配置クエリの再送の上限回数は、例えば、３回に設定される。配置クエリの再送回数が上限回数を超えている場合には（ＯＰ５７：Ｙｅｓ）、図１１Ｂに示される処理のフローが終了する。配置クエリの再送回数が上限回数を超えていない場合には（ＯＰ５７：Ｎｏ）、処理がＯＰ５４に戻り、クエリ処理部１１は、配置クエリと配信コンテンツのセグメント群とを再送する。
【０１３０】
ＯＰ５８では、配信ノード群情報管理部１３は、配置クエリまたは配置クエリ応答によって特定される配信ノード群の配信ノード情報を更新する。具体的には、配信ノード群情報に含まれる配信コンテンツ情報（図５Ａ）に、配置クエリに含まれる、コンテンツ番号，コンテンツビットレート，総セグメント数，総コンテンツ容量を格納する。但し、自ノードがノード番号「１」の配信ノードである場合には、自ノードにおける処理の結果として、これらの情報が得られる。さらに、配信ノード群情報管理部１３は、ＯＰ５２において記憶部１８に格納された固定セグメントの番号に基づいて、配信コンテンツ情報の固定セグメント番号，空セグメント番号，総固定セグメント容量，総保持セグメント容量を格納する。その後、図１１Ｂに示される処理のフローが終了する。
【０１３１】
図１１Ａ及び図１１Ｂの処理が、各配信ノードによって実行されることによって、自律的に、配信コンテンツが配信ノード群内に分散配置される。なお、図９，図１０，図１１Ａ，及び図１１Ｂでは、ノード番号１の配信ノードが配信コンテンツを分割してセグメントを生成し、各配信ノードは自ノードが担当するセグメントを配信コンテンツから取り出し取り出したセグメントを削除して次の配信ノードに転送するようにして、セグメントが配置されることを説明した。これに代えて、各配信ノードにおいて配信コンテンツを取得し、セグメントに分割し、自ノードが担当するセグメントだけ保持するようにしてセグメントが配置されてもよい。
【０１３２】
（クライアント群へのコンテンツの配信処理）
配信コンテンツ分散配置処理が終了し、クライアント群からコンテンツ配信の要求が受信されると、クライアント群へのコンテンツ配信処理が実行される。
【０１３３】
図１２は、クライアント群へのコンテンツ配信処理の例を示す図である。データ配信システムでは、配信クライアント群からコンテンツ配信要求が受信されると、配信ノード群に含まれる配信ノードが同期してコンテンツの配信を開始する。各配信ノードは、固定セグメントのうち番号の小さい固定セグメントから送信を開始する。また、各配信ノードは固定セグメントを下位隣接ノードに送信することに加え、上位隣接ノードから送信されるセグメントを下位隣接ノードに転送することも実行する。各セグメントは、送信元の配信ノードから最下位の配信ノードまでの各配信ノードによって、バケツリレー形式でクライアント群まで送信される。
【０１３４】
図１２に示される配信ノード群は、図６及び図９に示される例でも説明された配信ノード群と同じである５台の配信ノードを含む配信ノード群である。さらに、図１２に示され
る配信ノード群は、図９と同様に、１４個に分割された配信コンテンツのセグメントが波形に分散配置されている。以下、図１２に示される配信ノード群において、クライアント群へのコンテンツ配信処理が実行される例について説明する。なお、図１２では、ノード番号「ｎ」の配信ノードを、単に、配信ノードｎと称する。
【０１３５】
コンテンツ配信要求は、コンテンツの配信を要求するためにクライアント端末（またはクライアント群）によって送信される。コンテンツ配信要求には、例えば、配信を要求するコンテンンツのコンテンツ番号（配信要求コンテンツ番号）が含まれる。例えば、データ配信システムが定められた時刻に動画データを配信するようなサービスを提供する場合には、コンテンツ配信要求には、配信要求コンテンツ番号に加えて、配信開始時刻も含まれる。コンテンツ配信要求は、例えば、クライアント端末上で、データ配信システムが提供するサービスのウェブページ上で動画の視聴を指示するボタンがクリックされると、クライアント端末から配信される。
【０１３６】
配信クライアント端末（配信クライアント群）からのコンテンツ配信要求は、配信ノード群において配信クライアント群に最もネットワーク上の距離が近い配信ノード、すなわち、最下位の配信ノードである配信ノード５によって受信される。最下位の配信ノード５は、上位隣接ノードである配信ノード４にコンテンツ配信開始クエリを送信する。コンテンツ配信開始クエリは、コンテンツの配信開始を要求するクエリである。コンテンツ配信開始クエリには、例えば、配信ノード群番号，配信クライアント群番号，配信クライアント群によって配信要求されたコンテンツのコンテンツ番号（配信要求コンテンツ番号），配信開始時刻，及び，要求セグメント番号が含まれる。
【０１３７】
配信開始時刻は、クライアント群によってコンテンツ配信要求内で指定されている場合には、コンテンツ配信要求内の配信開始時刻となる。一方、クライアント群によって配信開始時刻が指定されていない場合には、すなわち、コンテンツ配信要求に配信開始時刻が含まれていない場合には、例えば、配信開始時刻は、現在時刻から所定時間後の時刻に設定される。この所定時間は、例えば、配信ノード群内の全配信ノードにコンテンツ配信開始クエリが行き渡り、セグメントの同期送信が可能となるまでに要すると予想される時間である。
【０１３８】
要求セグメント番号は、コンテンツ配信開始クエリの送信元の配信ノードが上位隣接ノードに配信を要求するセグメントの番号である。各配信ノードに対して下位隣接ノード又はクライアント群への配信が要求されるセグメントを要求セグメントと称する。コンテンツ配信開始クエリの要求セグメント番号には、自ノードに対する要求セグメントのうち、コンテンツ配信開始クエリの送信時に自ノードが保持していないセグメントの番号が格納される。なお、保持セグメントには、固定セグメントと一時セグメントとが含まれる。
【０１３９】
例えば、配信ノード５の場合には、クライアント群にネットワーク上の距離が最も近いので、全セグメント（セグメント１−１４）をクライアント群に配信しなければならないため、要求セグメントはセグメント１−１４となる。一方、配信ノード５は、固定セグメントとして、セグメント１，１０，１１を保持しているので、残りのセグメント２−９，１２−１４が上位隣接ノードに配信を要求するセグメントとなる。したがって、配信ノード５が送信するコンテンツ配信開始クエリに含まれる要求セグメント番号は、２−９，１２−１４となる。図１２では、各配信ノードから送信されるコンテンツ配信開始クエリに含まれる要求セグメント番号が示されている。なお、各配信ノードにおいて、要求セグメントは例えば記憶部１８に格納される。
【０１４０】
配信ノード５からコンテンツ配信開始クエリを受信する配信ノード４は、コンテンツ配信開始クエリに含まれる要求セグメント番号を書き換えて、上位隣接ノードである配信ノ
ード３に送信する。配信ノード４の要求セグメントは、配信ノード５から受信したコンテンツ配信開始クエリに含まれる要求セグメント番号のセグメント２−９，１２−１４となる。配信ノード４は、固定セグメントとしてセグメント２，９，１２を保持しているので、要求セグメント（セグメント２−９，１２−１４）のうち、セグメント３−８，１３，１４が上位隣接ノードに配信を要求するセグメントとなる。したがって、配信ノード４が上位隣接ノードである配信ノード３に送信するコンテンツ配信開始クエリの要求セグメント番号は、３−８，１３，１４となる。
【０１４１】
以降、配信ノード１から配信ノード３も配信ノード４と同様の処理を行う。配信ノード３では、セグメント３−８，１３，１４が要求セグメントであり、固定セグメントがセグメント３，８，１３であるので、配信ノード３が送信するコンテンツ配信開始クエリに含まれる要求セグメント番号は、４−７，１４となる。配信ノード２では、セグメント４−７，１４が要求セグメントであり、固定セグメントがセグメント４，７，１４であるので、配信ノード２が送信するコンテンツ配信開始クエリに含まれる要求セグメント番号は、５，６となる。
【０１４２】
配信ノード１では、セグメント５，６が要求セグメントであり、固定セグメントがセグメント５，６であるので、上位隣接ノードに配信を要求するセグメントはない。また、配信ノード１には、上位のノードもないので、コンテンツ配信開始クエリは送信されない。
【０１４３】
配信ノード群内の全配信ノードにコンテンツ配信開始クエリが到着し、各配信ノードに対する要求セグメントが取得され、コンテンツの配信開始時刻になると、各ノードは、保持するセグメントのうち最も番号の小さいセグメントから順に配信を開始する。コンテンツ配信処理を通じて、各配信ノードは、要求セグメントとなるセグメントを下位隣接ノード又はクライアント群に配信することになる。
【０１４４】
図１３Ａ，図１３Ｂ，図１３Ｃ，図１３Ｄ，図１３Ｅ，図１３Ｆ，図１３Ｇ，図１３Ｈ，図１３Ｉ，図１３Ｊ，図１３Ｋ，図１３Ｌ，図１３Ｍ，図１３Ｎ，及び図１３Ｏは、図１２に示される配信ノード群において配信コンテンツがクライアント群に配信される様子を示す図である。
【０１４５】
図１３Ａ−図１３Ｏでは、縦方向がノード番号，横方向がセグメント番号を示す、配信コンテンツの分散配置図が示されている。各配信ノードの固定セグメントを示すフィールドは、斜線のテクスチャで塗りつぶされており、一時セグメントを示すフィールドは黒で塗りつぶされる。また、分散配置図の下方には、クライアント群に到着したセグメントが表示されている。図１２及び図１３Ａ−図１３Ｏで示される配信ノード群の各配信ノード間の配信能力は同じであるとする。
【０１４６】
図１３Ａは、コンテンツ配信開始前の配信コンテンツの分散配置図を示す。図１３Ａ−図１３Ｏでは、図１２（図９）に示される配信ノード群の配信コンテンツの分散配置図が示されるので、分散配置図は、固定セグメントによって波形を示す。コンテンツ配信要求がクライアント群から受信されるとコンテンツ配信が開始される。
【０１４７】
図１３Ｂは、コンテンツ配信開始時の配信コンテンツの分散配置図を示す。各配信ノードは、固定セグメントのうち番号の小さいものから下位隣接ノード又はクライアント群への送信を開始する。図１３Ｂでは、配信ノード５はクライアント群にセグメント１（固定セグメント）を送信している。配信ノード４は、下位隣接ノードの配信ノード５にセグメント２（固定セグメント）を送信している。配信ノード３は、下位隣接ノードの配信ノード４にセグメント３（固定セグメント）を送信している。配信ノード２は、下位隣接ノードの配信ノード３にセグメント４（固定セグメント）を送信している。配信ノード１は、
下位隣接ノードの配信ノード２にセグメント５（固定セグメント）を送信している。図１３Ｂに示される各配信ノードの配信コンテンツのセグメントの送信処理によって、クライアント群にセグメント１が到着する。
【０１４８】
図１３Ｃは、図１３Ｂにおいて示される各配信ノードの保持セグメントの送信が完了し、各配信ノードが次の保持セグメントを送信する際の配信コンテンツンの分散配置図を示す。図１３Ｃでは、配信ノード５は、配信ノード４から受信したセグメント２を一時セグメントとして保持しており、未送信の要求セグメント（２−２０）のうちセグメント番号が最も小さいセグメント２をクライアント群に送信する。配信ノード４は、配信ノード３から受信したセグメント３を一時セグメントとして保持しており、未送信の要求セグメント（３−９，１２−１４）のうちセグメント番号が最も小さいセグメント３を下位隣接ノードである配信ノード５に送信する。配信ノード３は、配信ノード２から受信したセグメント４を一時セグメントとして保持しており、未送信の要求セグメント（４−８，１３，１４）のうちセグメント番号が最も小さいセグメント４を下位隣接ノードである配信ノード４に送信する。配信ノード２は、配信ノード１から受信したセグメント５を一時セグメントとして保持しており、未送信の要求セグメント（５−７，１４）のうちセグメント番号が最も小さいセグメント５を下位隣接ノードである配信ノード３に送信する。配信ノード１は、前回の送信で固定セグメントであるセグメント５を下位隣接ノードである配信ノード２に送信したので、次に番号の大きい固定セグメントであるセグメント６を配信ノード２に送信する。配信ノード１の保持セグメント及び要求セグメント（５，６）で未送信のセグメントはなくなったので、配信ノード１はこれ以上セグメントを送信しない。
【０１４９】
図１３Ｃに示される各配信ノードの配信コンテンツのセグメントの送信処理によって、クライアント群にセグメント２が到着する。図１３Ｃにおいて説明された、配信ノード２〜５の一時セグメントを下位隣接ノードに送信する処理が終了すると、各一時セグメントは、所定時間経過後、各配信ノード２〜５から削除される。ただし、該所定時間内に新たにクライアント端末からコンテンツ配信要求又は配信開始クエリが受信された場合には、該所定時間を計測するタイマーがリセットされる。この場合には、一時コンテンツは、該コンテンツ配信要求又は配信開始クエリに対する一時セグメントの送信が終了し、新たにコンテンツ配信要求又は配信開始クエリを受信せずに該所定時間経過するまで、各配信ノードに保持される。
【０１５０】
以降、図１３Ｄ〜図１３Ｏでは、図１３Ｃにおいて説明されたようにして、各配信ノードによるバケツリレーで配信コンテンツのセグメントがクライアント群に送信されていく。図１３Ｄ〜図１３Ｏに示されるように、クライアント群には、セグメント１からセグメント１４まで途切れなく、且つ順番に、セグメントが到着する。
【０１５１】
図１３Ａ〜図１３Ｏにおいて示されるように、波形で配信コンテンツが分散配置されることによって、クライアント群（クライアント端末）により遅延を抑えてコンテンツを配信することができる。例えば、セグメント１は、クライアント群に最もネットワーク上の距離が近い配信ノード１が固定保持しており、該配信ノード１から送信されるので、クライアント群がコンテンツ配信要求を送信してからセグメント１の到着までの遅延を小さく抑えることができる。すなわち、クライアントへのコンテンツ到達までの遅延時間の長期化を防止することができる。さらに、セグメントが波形で配置されていることによって、例えば、配信コンテンツが動画データである場合には、クライアント端末上でセグメント１が再生されている間に次に再生されるセグメント２以降のセグメントがセグメント順にクライアント端末に到着する。したがって、クライアント端末は配信コンテンツの再生開始から途切れなくコンテンツを再生することができる。すなわち、コンテンツ配信の為に要求された配信品質を確保することができる。
【０１５２】
図１４は、ストリーム管理テーブルの例を示す図である。図１４では、例えば、図１２において示される配信ノード群のノード番号３の配信ノード（配信ノード３）が保持するストリーム管理テーブル１８３が示される。
【０１５３】
例えば、データ配信システムが、ユーザの好きな時間に動画データを視聴可能なサービスを提供しているような場合には、配信ノードは、或る時刻において複数のストリームを扱うことになる。ストリーム管理テーブル１８３は、自ノードが扱うストリームにおいて配信しているセグメントを管理するためのテーブルである。ストリームは、一般に、ストリーミング再生されるデータ（動画データ、音声データ等）の列を指すが、第１実施形態では、このストリーミングされるデータ（コンテンツ）を送信するフローをストリームと呼ぶこととする。同時刻に同セグメントの送信が開始されるストリームは同ストリームとみなされる。
【０１５４】
ストリーム管理テーブル１８３は、行がストリーム番号，列がセグメント番号を示す表であり、コンテンツ毎に保持される。ストリーム番号は、ストリームを識別するための番号である。ストリーム番号は、例えば、クライアント端末からコンテンツ配信要求に含まれて指定されてもよいし、各配信ノードにおいて新たにストリームが追加された際に付与されてもよい。ストリーム管理テーブル１８３では、ストリーム毎の要求セグメントを示すフィールドに、要求セグメントを示す印（例えば、フラグ等）が付けられる。図１４では、要求セグメントとなるセグメントは米印で示される。配信ノードは、ストリーム管理テーブル１８３において、要求セグメントを示す印が付されているセグメントを下位隣接ノード又はクライアント群に送信する。また、ストリーム管理テーブル１８３では、自ノードが現時点における下位隣接ノード又はクライアント群に送信中のセグメントを示すポインタを有しており、図１４ではポインタはそれぞれのストリーム番号で示される。
【０１５５】
ストリーム管理テーブル１８３には、ストリームを使用するユーザ番号が保持されてもよい。図１４に示される例では、各ストリームに使用ユーザ番号が保持される。ユーザ番号は、例えば、コンテンツ配信要求に含まれてもよい。
【０１５６】
図１４では、ストリーム管理テーブルの下方に、配信ノード３が保持するセグメントが示される。セグメントは図１３Ａ〜図１３Ｏと同様に、固定セグメントは斜線のテクスチャで、一時セグメントは黒で示されている。配信ノード３は、図１４に示されるストリーム管理テーブルの時点で、セグメント３，８，１３を固定セグメントとして有しており、セグメント５〜７，１４を一時セグメントとして保持している。
【０１５７】
一時セグメントは、送信終了後、自ノードがコンテンツ配信要求又は配信開始クエリを受信せずに、所定時間経過した場合には、配信ノードから削除される。一方、一時セグメントは、送信終了後、該所定時間内に、自ノードが新たにコンテンツ配信要求又は配信開始クエリを受信すると、該コンテンツ配信要求又は配信開始クエリに対して送信されるまで保持される。新たにコンテンツ配信要求又は配信開始クエリを受信することは、新たにストリームが発生することと等しい。そのため、新たにストリームが発生し、再度保持する一時セグメントを送信する必要がある場合には、該一時セグメントを保持する時間を延長する。これによって、上位のノードからの該一時セグメントの送信処理が省かれ、且つ、該一時セグメントのデータ量の分だけ上位のノードから自ノードまでの間のネットワークを流れるデータ量を低減することができる。
【０１５８】
図１４に示される配信ノード３のストリーム管理テーブル１８３では、現時点でストリーム番号１〜３の３つのストリーム（ストリーム１−３）が存在することが示される。なお、図１４に示される配信ノード３のストリーム管理テーブル１８３では、ストリーム番号は配信ノード３における発生順を示すこととする。
【０１５９】
ストリーム１では、要求セグメントはセグメント３−８，１３，１４であり、配信ノード３はセグメント８を下位隣接ノードである配信ノード４に送信中である。ストリーム２は、ストリーム１においてセグメント番号３が送信された後に発生したストリームであり、セグメント３は下位の配信ノードによって一時セグメントとして保持されているため、要求セグメントはセグメント４−８，１３，１４となっている。ストリーム２では、配信ノード３は、セグメント７を配信ノード４に送信中である。ストリーム３は、ストリーム２においてセグメント５の送信完了の後に発生したストリームであり、セグメント３−５は、下位の配信ノードによって一時セグメントとして保持されているため、要求セグメントはセグメント６−８，１３，１４となっている。
【０１６０】
ストリーム１の送信において、要求セグメントであるセグメント３−８，１３，１４のうち、固定セグメントであるセグメント３，８，１３を除くセグメント４−７，１３が上位隣接ノードから送られてきて、一時セグメントとして保持される。ストリーム１において、図１４に示される時点では、一時セグメント４−７は、送信が完了している。ストリーム１以外のストリームが発生していない場合には、図１４に示される時点では、一時セグメント４−７は、削除される。しかしながら、図１４では、ストリーム１の後にストリーム２，３が発生しており、ストリーム２では要求セグメント４−８，１３，１４のうちセグメント４−６の送信が完了しており、ストリーム３では何れの要求セグメントも送信完了していない。そのため、ストリーム１，２において送信済みの要求セグメントであり、ストリーム３においては要求セグメントではない一時セグメント４，５は削除されている。ストリーム１，２では送信済の要求セグメントであるが、ストリーム３では、送信中の要求セグメントである一時セグメント６は、保持されている。ストリーム１では送信済みの要求セグメントであるが、ストリーム２，３では送信中又は未送信の要求セグメントである一時セグメント７は、保持されている。ストリーム１〜３において、送信中又は未送信の要求セグメントである一時セグメント１４は保持されている。すなわち、いずれかのストリームにおいて送信中又は未送信の要求セグメントに該当する一時セグメントは、少なくとも何れのストリームにおいても送信完了するまでは、配信ノードに保持される。
【０１６１】
ストリーム管理テーブル１８３は、テーブル管理部１７によって管理される。テーブル管理部１７は、新たなコンテンツに対するコンテンツ配信要求又は配信開始クエリを受信すると、配信ノード群情報に含まれる配信コンテンツ情報の総セグメント数から、ストリーム管理テーブル１８３を生成する。また、テーブル管理部１７は、受信した配信開始クエリに含まれる要求セグメント番号から、新たなストリームの要求セグメントをストリーム管理テーブル１８３に記録する。さらに、テーブル管理部１７は、セグメントの送信処理と一時セグメント管理部による一時セグメントの削除処理とを監視しており、これらの処理に応じて、ストリーム管理テーブル１８３を更新する。
【０１６２】
図１５，図１６，図１７，及び図１８は、データ配信システムのコンテンツ配信処理における各配信ノードによって実行される処理のフローチャートの例である。図１５に示されるフローチャートは、コンテンツの配信に先駆けて行われる配信準備の処理のフローチャートである。
【０１６３】
図１５に示されるフローチャートは、配信ノードがクライアント群からコンテンツ配信要求を受信した場合、又は、下位隣接ノードから配信開始クエリを受信した場合に開始される。
【０１６４】
ＯＰ６１では、テーブル管理部１７は、受信したコンテンツ配信要求又は配信開始クエリに発生が示される新たなストリームの番号を取得する。なお、ストリーム番号は、受信したコンテンツ配信要求又は配信開始クエリに含まれていてもよいし、各配信ノードのテ
ーブル管理部１７が独自に付与してもよい。ストリーム番号がコンテンツ配信要求又は配信開始クエリに含まれる場合には、クエリ処理部１１がストリーム番号を読み出すことによって、テーブル管理部１７がストリーム番号を取得する。
【０１６５】
ＯＰ６２では、テーブル管理部１７は、ストリーム管理テーブル１８３に取得したストリーム番号で新たにストリームを追加する。ＯＰ６３では、テーブル管理部１７は、新たに追加されたストリームにおける要求セグメントの番号を保持する。コンテンツ配信要求を受信した場合には、テーブル管理部１７は、配信コンテンツの全セグメントを要求セグメントとしてストリーム管理テーブル１８３に記録する。配信開始クエリを受信した場合には、クエリ処理部１１は、配信開始クエリに含まれる要求セグメント番号を読み出し、テーブル管理部１７は、読み出された要求セグメント番号のセグメントを要求セグメントとしてストリーム管理テーブル１８３に記録する。
【０１６６】
ＯＰ６４では、クエリ処理部１１は、上位隣接ノードに送信予定の配信開始クエリに含められる要求セグメント番号を取得する。クエリ処理部１１は、ＯＰ６３においてストリーム管理テーブル１８３に記録された要求セグメントのうち、自ノードが保持する固定セグメント及び一時セグメントを除いたセグメントの番号を要求セグメント番号として取得する。
【０１６７】
ＯＰ６５では、クエリ処理部１１は、上位隣接ノードに送信予定の配信開始クエリに含められる要求セグメント番号は取得されたか否かを判定する。すなわち、クエリ処理部１１は、上位隣接ノードに送信を要求するセグメントがあるか否かを判定する。上位隣接ノードに送信予定の配信開始クエリに含められる要求セグメント番号が取得された場合には（ＯＰ６５：Ｙｅｓ）、処理がＯＰ６６に進む。上位隣接ノードに送信予定の配信開始クエリに含められる要求セグメント番号が取得されなかった場合には（ＯＰ６５：Ｎｏ）、上位隣接ノードに送信を要求するセグメントが無く、クエリ処理部１１は、配信開始クエリを送信しない。その後、図１５に示される処理のフローが終了する。
【０１６８】
ＯＰ６６では、クエリ処理部１１は、上位隣接ノードが存在するか否かを判定する。上位隣接ノードが存在する場合には（ＯＰ６６：Ｙｅｓ）、処理がＯＰ６７に進む。上位隣接ノードが存在しない場合には（ＯＰ６６：Ｎｏ）、クエリ処理部１１は、配信開始クエリを送信する相手が存在しないので、配信開始クエリを送信しない。その後、図１５に示される処理が終了する。
【０１６９】
ＯＰ６７では、クエリ処理部１１は、ＯＰ６４において取得した要求セグメント番号を含めて上位隣接ノードに配信開始クエリを送信する。その後、図１５に示される処理が終了する。
【０１７０】
図１５に示される処理が、各配信ノードで実行されると、配信ノード群におけるコンテンツ配信処理の準備が完了する。その後、配信開始時刻になると、コンテンツ配信処理が開始される。
【０１７１】
図１６は、配信ノード群におけるコンテンツ配信の処理のフローチャートの例である。図１６に示されるフローチャートは、コンテンツの配信開始時刻になると各配信ノードで開始される。図１６に示されるフローチャートは、配信ノードに存在するストリームごとに実行される。
【０１７２】
ＯＰ７１では、セグメント送信部１９は、要求セグメントのうちで最もセグメント番号の小さいセグメントから下位隣接ノード又はクライアント群への送信を決定する。すなわち、セグメント送信部１９は、最初に送信される、送信対象のセグメントを決定する。
【０１７３】
ＯＰ７２では、セグメント送信部１９は、送信対象セグメントが自ノードに保持されているか否かを判定する。送信対象セグメントが自ノードに保持されている場合には（ＯＰ７２：Ｙｅｓ）、処理がＯＰ７４に進む。送信対象セグメントが自ノードに保持されていない場合には（ＯＰ７２：Ｎｏ）、処理がＯＰ７３に進む。
【０１７４】
ＯＰ７３では、セグメント送信部１９は、送信対象セグメントの受信を待機する。送信対象セグメントが受信されるまで、ＯＰ７２及びＯＰ７３の処理が繰り返される。なお、ＯＰ７３の処理が配信ノード群のいずれかの配信ノードにおいて実行された場合には、遅延が発生するおそれがある。特に、クライアント群にネットワーク上の距離が最も近い配信ノードにおいてＯＰ７３の処理が実行された場合には、遅延が発生する。ただし、配信コンテンツの分割時に、遅延を低減するために、セグメントのサイズは配信ノード群における最小配信能力とコンテンツビットレートとが考慮された値に設定されているため、ＯＰ７３の処理が実行される可能性は低い。
【０１７５】
ＯＰ７４では、セグメント送信部１９は、送信対象セグメントの下位隣接ノード又はクライアント群への送信を開始する。ＯＰ７５では、セグメント送信部１９は、送信対象セグメントの送信が完了したか否かを判定する。送信対象セグメントの送信が完了した場合には（ＯＰ７５：Ｙｅｓ）、処理がＯＰ７６に進む。送信対象セグメントの送信が完了していない場合には（ＯＰ７５：Ｎｏ）、処理がＯＰ７７に進む。
【０１７６】
ＯＰ７６では、セグメント送信部１９は、図１６に示されるフローチャートを実行中のストリームにおける全ての要求セグメントを送信完了したか否かを判定する。この判定は、テーブル管理部１７によるストリーム管理テーブルにおける、図１６に示されるフローチャートを実行中のストリームにおける配信中のセグメントのポインタの位置からの確認結果に基づいて実行される。全ての要求セグメントの送信が完了した場合には（ＯＰ７６：Ｙｅｓ）、図１６に示されるコンテンツ配信処理が終了する。未送信の要求セグメントが存在する場合には（ＯＰ７６：Ｎｏ）、処理がＯＰ７７に進む。
【０１７７】
ＯＰ７７では、テーブル管理部１７は、ストリーム管理テーブル中の図１６に示されるフローチャートを実行中のストリームにおける配信中のセグメントのポインタの位置を次の要求セグメントの位置に移動させる。セグメント送信部１９は、ストリーム管理テーブルの該ストリームにおけるポインタの位置が示すセグメントを送信対象に設定する。その後処理がＯＰ７２に戻り、全要求セグメントの送信が完了するまでＯＰ７２−ＯＰ７７の処理が繰り返される。
【０１７８】
図１７は、コンテンツ配信処理の間、各配信ノードにおいて実行されるセグメントの受信処理のフローチャートの例である。図１７に示されるフローチャートは、図１６のコンテンツ配信処理が実行されている間、セグメントを受信が検出されると開始される。また、図１７に示されるフローチャートは、セグメントが受信されるたびに実行される。
【０１７９】
ＯＰ８１では、一時セグメント管理部１５は、受信検知されたセグメントの受信が完了したか否かを判定する。該セグメントの受信が完了した場合には（ＯＰ８１：Ｙｅｓ）、処理がＯＰ８２に進む。該セグメントの受信が完了していない場合には（ＯＰ８１：Ｎｏ）、該セグメントの受信が完了するまで、ＯＰ８１の処理が繰り返される。
【０１８０】
ＯＰ８２では、配信ノード群情報管理部１３は、配信ノード群情報１８２に格納される受信したセグメントに対応する配信コンテンツ情報の一時セグメント番号に受信したセグメントのセグメント番号を追加記録する。また、配信ノード群情報管理部１３は、配信コンテンツ情報の空セグメント番号，総一時セグメント容量，及び総保持セグメント容量を
更新する。その後、図１７に示される処理が終了する。
【０１８１】
図１８は、一時セグメントの削除処理のフローチャートの例である。図１８に示されるフローチャートは、記憶部１８の一時セグメントバッファ１８１に一時セグメントが保持されている間繰り返し実行される。また、図１８に示されるフローチャートは、一時セグメントバッファ１８１に保持される各一時セグメントに対して実行される。
【０１８２】
ＯＰ９１では、一時セグメント管理部１５は、処理対象の一時セグメントは、自ノードのストリームのいずれかの未送信セグメントに含まれているか否かを判定する。この判定は、テーブル管理部１７によるストリーム管理テーブル１８３の参照結果に基づいて行われる。処理対象の一時セグメントがいずれかの未送信セグメントに含まれている場合には（ＯＰ９１：Ｙｅｓ）、処理がＯＰ９１に戻り、処理対象の一時セグメントがいずれかのストリームの未送信要求セグメントに含まれる間はＯＰ９１の処理が繰り返される。処理対象の一時セグメントがいずれの未送信セグメントにも含まれていない場合には（ＯＰ９１：Ｎｏ）、処理がＯＰ９２に進む。
【０１８３】
ＯＰ９２では、一時セグメント管理部１５はタイマーを開始する。このタイマーは、所定時間を計測する。所定時間は、例えば、数秒でも、１時間でも、０秒でもよく、データ配信システムの管理者がネットワークの状況に応じて設定可能である。又は、例えば、セグメント及びコンテンツ配信がＴＣＰを用いて行われる場合には、一時セグメントの送信先からＡＣＫを受信した時点からタイマーを開始してもよい。
【０１８４】
ＯＰ９３では、一時セグメント管理部１５は、タイムアウトか否かを判定する。タイムアウトである場合には（ＯＰ９３：Ｙｅｓ）、処理がＯＰ９６に進む。タイムアウト出ない場合には（ＯＰ９３：Ｎｏ）、処理がＯＰ９４に進む。
【０１８５】
ＯＰ９４では、一時セグメント管理部１５は、処理対象の一時セグメントが新たに発生したストリームの未送信要求セグメントに含まれているか否かを判定する。処理対象の一時セグメントが新たに発生したストリームの未送信要求セグメントに含まれている場合には（ＯＰ９４：Ｙｅｓ）処理がＯＰ９５に進む。処理対象の一時セグメントが新たに発生したストリームの未送信要求セグメントに含まれていない場合（ＯＰ９４：Ｎｏ）、または、新たにストリームが発生していない場合には、処理がＯＰ９３に戻る。
【０１８６】
ＯＰ９５では、一時セグメント管理部１５は、タイマーをリセットする。これによって、処理対象の一時セグメントの保持期間が延長される。その後処理がＯＰ９３に戻る。
【０１８７】
ＯＰ９６では、一時セグメント管理部１５は、処理対象の一時セグメントを削除する。その後、処理対象の一時セグメントに対する図１８に示される処理のフローが終了する。
【０１８８】
図１９は、コンテンツの開始位置の要求と一時セグメントの削除処理との関係を説明するための図である。クライアント端末のユーザが常にコンテンツの先頭からの再生を指示するとは限らず、コンテンツの途中の所定の時点からの再生を指示することもある。コンテンツの再生開始位置は、クライアント群から送信されるコンテンツ配信要求に含まれる。また、ネットワークに最も近い配信ノード以外のノードのセグメント送信開始位置は、配信コンテンツの先頭ではない（図１３Ａ−図１３Ｏ参照）。すなわち、配信開始クエリの要求セグメント番号によって指定される送信開始位置となるセグメントは、先頭のセグメントではない。
【０１８９】
図１９では、配信コンテンツのセグメントが示されており、配信ノードに保持されている一時セグメントは黒で表わされる。図１９では、配信ノードが保持する一時セグメント
は、セグメント５−１１である。なお、図１９では、説明の簡略化のため、固定セグメントは保持されていないものとする。
【０１９０】
（Ａ）送信開始位置が保持される一時セグメントよりもよりも前にある場合
この場合には、一時セグメント５−１１はコンテンツ配信に必要なセグメントであるので、保持期間が延長される。
【０１９１】
（Ｂ）送信開始位置が保持される一時セグメントである場合
この場合には、送信開始位置の一時セグメント６以降の一時セグメント６−１１が、コンテンツ配信に必要なセグメントであるので、保持期間が延長される。送信開始位置より前の一時セグメント５は、コンテンツ配信に必要ないため、所定時間経過後、削除される。ただし、一時セグメント５がコンテンツ配信に必要なセグメントとなる送信開始位置を指定するコンテンツ配信要求又は配信開始クエリが到着した場合には、一時セグメント５の保持期間が延長される。
【０１９２】
（Ｃ）送信開始位置が保持される一時セグメントよりも後ろの場合
この場合には、一時セグメント５−１１はコンテンツ配信に必要なセグメントではないので、何れの一時セグメントも保持期間が延長されず、所定時間経過後に削除される。ただし、一時セグメント５−１１がコンテンツ配信に必要なセグメントとなる送信開始位置を指定するコンテンツ配信要求又は配信開始クエリが到着した場合には、一時セグメント５−１１の保持期間は延長される。
【０１９３】
図２０は、配信コンテンツへのコンテンツ配信要求が集中した場合の例を説明するための図である。クライアント群からのコンテンツ配信要求を受信すると、図１８に示される一時セグメントの削除処理の実行によって、ネットワーク上の距離がクライアント群に最も近い配信ノード（以下、単に「クライアント群に最も近い配信ノード」）に保持される一時セグメントの保持期間が延長される（図１９参照）。また、クライアント群に最も近い配信ノードは、配信コンテンツの全セグメントをクライアント群に送信する。そのため、クライアント群からのコンテンツ配信要求が集中すると、クライアント群に最も近い配信ノードに一時セグメントが蓄積されていき、最終的に、クライアント群に最も近い配信ノードは配信コンテンツの全セグメントを保持することになる。すなわち、一時的に、クライアント群に最も近い配信ノードが配信コンテンツのミラーサーバとなる。
【０１９４】
配信コンテンツの全セグメントがクライアント群に最も近い配信ノードに保持される状態になると、該配信ノードのみでクライアント群からのコンテンツ配信要求に対応することができる。そのため、他の上位の配信ノードからのセグメントの送信の必要がなくなるので、ネットワーク上に無駄な配信開始クエリが流れることを防ぐことができ、さらに、ネットワークを流れるデータ量を抑えることができる。
【０１９５】
また、クライアント群からのコンテンツ配信要求が途絶えると、所定時間経過後、クライアント群に最も近い配信ノードは保持している一時セグメントを削除する。そのため、ネットワーク上に保持される配信コンテンツのデータ量が増えるのはコンテンツ配信要求の集中時だけに抑えられる。
【０１９６】
（スケールアウト発生時の処理）
図２１は、スケールアウトを説明するための図である。図２１に示されるデータ配信システムは、図１で示されるデータ配信システムと同じである。
【０１９７】
図２１に示される配信ノード群は、クライアント群Ａに対してコンテンツを配信するための配信ノード群である。この配信ノード群に対して、コンテンツを配信するクライアン
ト群を追加することをスケールアウトと称する。図２１に示される例では、クライアント群Ｂが配信ノード群に追加される。
【０１９８】
図２２は、スケールアウトが発生した場合のデータ配信システムのコンテンツ配信処理を説明するための図である。図２２では、図１２において示される配信ノード１−５によって形成される配信ノード群にクライアント群Ｂが追加される例が示される。図２２において、クライアント群Ｂにネットワーク上の距離が最も近い配信ノードは、配信ノード１である。
【０１９９】
図２２に示される配信ノード群によって、クライアント群Ｂにコンテンツが配信される場合には、まず、クライアント群Ｂには、配信ノード１の固定セグメントであるセグメント５が配信ノード１によって送信されて到着する。なお、クライアント群Ｂからのコンテンツ配信要求では、送信開始位置はコンテンツの先頭が指定されているものとする。したがって、この時点では、クライアント群Ｂでは、配信ノード１からセグメント５が到着しても、コンテンツ再生は開始されない。
【０２００】
次に、クライアント群Ｂには、配信ノード２の固定セグメントであり配信ノード２によって送信されたセグメント４が、配信ノード１を経由して、到着する。その次に、クライアント群Ｂには、配信ノード３の固定セグメントであり配信ノード３によって送信されたセグメント３が、配信ノード２及び配信ノード１を経由して、到着する。さらに、その次に、クライアント群Ｂには、配信ノード４の固定セグメントであり配信ノード４によって送信されたセグメント２が、配信ノード３，配信ノード２，及び配信ノード１を経由して、到着する。さらに、その次に、クライアント群Ｂには、配信ノード５の固定セグメントであり配信ノード５によって送信されたセグメント１が、配信ノード４，配信ノード３，配信ノード２，及び配信ノード１を経由して、到着する。
【０２０１】
クライアントＢ群では、セグメント１が到着してから初めてコンテンツの再生が開始される。そのため、上述のように、クライアントＢ群では、コンテンツの再生が、セグメント５−２を受信する時間だけ遅延してしまう。そこで、第１実施形態では、スケールアウトが発生した場合に、追加されたクライアント群のネットワーク上に最も近い距離に位置する配信ノードにセグメント１，その次に近い配信ノードにセグメント２、というように、配信コンテンツのセグメントの複製を配置する。
【０２０２】
図２３は、スケールアウト発生時のセグメント配置の例を示す図である。図２３に示される配信ノード群は、図２２に示される配信ノード群と同じである。第１実施形態では、クライアント群Ｂが配信ノード群の配信クライアント群に追加された場合には、クライアント群Ｂにネットワーク上の距離が最も近い配信ノード１にも固定セグメントとしてセグメント１（コピー）が配置される。さらに、配信ノード１の隣接セグメントであり、クライアント群Ｂに配信ノード１の次に近い配信ノード２に固定セグメントとしてセグメント２（のコピー）が配置される。図２３では、新たに固定セグメントとして保持されるセグメントは黒色で示されている。
【０２０３】
このようにセグメントを配置することによって、クライアント群Ｂには、コンテンツ配信要求後、最初にセグメント１が到着し、続けてセグメント２，３と順番にセグメントが到着することになり、コンテンツ再生開始までの遅延を解消することができる。
【０２０４】
図２４は、スケールアウト発生によるセグメント配置処理の例を説明するための図である。図２４に示される配信ノード群は、図２２及び図２３で示される配信ノード群と同様である。図２４には、配信ノード群に新たにクライアント群Ｂが追加された際のスケールアウト発生によるセグメント配置処理が示される。
【０２０５】
まず、新たに追加されるクライアント群Ｂにネットワーク上の距離が最も近い配信ノード１にスケールアウト配置要求が入力される。スケールアウト配置要求は、データ配信システムの管理者によって、配信ノード１に直接入力されてもよいし、ネットワークを開始入力されてもよい。又は、クライアント群Ｂからネットワークを介して入力されてもよい。スケールアウト配信要求には、配信ノード群番号，新たに追加されるクライアント群のクライアント群番号，配信コンテンツ番号等が含まれる。
【０２０６】
スケールアウト配信要求が入力された配信ノード１には、固定セグメントとしてセグメント５，６が保持されているが、セグメント１は保持されていない。配信ノード１は、少なくとも固定セグメントとしてセグメント１を保持する必要がある。そこで、配信ノード１は、スケールアウト配信要求によって特定される配信ノード群に、スケールアウト配信要求によって特定される配信コンテンツのセグメント１のコピーを要求する複製依頼クエリを送信する。複製依頼クエリには、例えば、配信ノード群番号，配信クライアント群番号，配信コンテンツ番号，複製依頼するセグメント番号，複製依頼クエリを生成したノードのＩＰアドレス等が含まれる。また、複製依頼クエリは、マルチキャストで送信されてもよいし、上位又は下位の隣接ノードに宛ててユニキャストで送信されてもよい。なお、第１実施形態では、自ノードが保持する最小番号の固定セグメントよりも小さい番号のセグメントは、自ノードよりも下位のノードが保持しているはずである（図２参照）。したがって、ユニキャストで複製依頼クエリを送信する場合には、第１実施形態では、下位隣接ノードに宛てて複製依頼クエリを送信する。
【０２０７】
複製依頼クエリによってコピーを要求されたセグメント１を保持する配信ノード５が、配信ノード１から送信された複製依頼クエリを受信すると、複製依頼クエリ応答とともにセグメント１のコピーを配信ノード１にユニキャストで送信する。なお、複製依頼クエリがユニキャストで送信される場合には、複製依頼クエリを受信した配信ノードは、複製依頼のセグメントを保持していない場合には、自ノードの上位又は下位の隣接ノードに複製依頼クエリを転送する。これによって、配信ノード１から送信される複製依頼クエリが配信ノード５に到着する。複製依頼クエリ応答とともにセグメント１の複製を受信した配信ノード１は、セグメント１を固定セグメント群に追加する。
【０２０８】
配信ノード１は、複製依頼クエリとともに、ユニキャストで下位隣接ノードである配信ノード２に保持要求クエリも送信する。保持要求クエリは、自ノードが保持する最小番号の固定セグメント５のうち、自身が担当するセグメント１を除いた、セグメント２−４の保持を依頼するクエリである。保持要求クエリには、例えば、配信ノード群番号，配信クライアント群番号，配信コンテンツ番号，及び、必須保持セグメント番号，保持可能セグメント番号等が含まれる。
【０２０９】
必須保持セグメント番号は、保持要求クエリを受信した配信ノードが必ず固定セグメントとして保持しなければならないセグメントの番号である。例えば、図２４の配信ノード群の場合、セグメント１の次にセグメント２がクライアント群に到着するためには、配信ノード２がセグメント２を固定セグメントとして保持する必要がある。そのため、配信ノード１から配信ノード２に送信される保持要求クエリには、必須保持セグメント番号として「２」が格納される。保持可能セグメント番号は、保持要求クエリを受信した配信ノードによって保持されていてもよいし、さらに下位のノードによって保持されてもよいセグメントの番号である。例えば、図２４の配信ノードでは、セグメント３及び４は、配信ノード２が保持していてもよい。そのため、配信ノード１から配信ノード２に送信される保持要求クエリには、保持可能セグメント番号として、「３」及び「４」が格納される。
【０２１０】
配信ノード２は、保持要求クエリを受信すると、必須保持セグメント番号で指定される
セグメント２を固定セグメントとして保持していないので、セグメント２の複製を要求する複製依頼クエリを送信する。セグメント２を固定セグメントとして保持する配信ノード４が、配信ノード２によって送信された複製依頼クエリを受信すると、セグメント２の複製を複製依頼クエリ応答とともに配信ノード２に送信する。配信ノード２は、受信したセグメント２を固定セグメント群に追加する。
【０２１１】
配信ノード２は、複製依頼クエリを送信するとともに、下位隣接ノードである配信ノード３に保持要求クエリを送信する。配信ノード２が配信ノード１から受信した保持要求クエリの保持可能セグメント（セグメント３，４）のうち、配信ノード２は、セグメント３は保持していないが、セグメント４を既に固定セグメントとして保持している。セグメント３は、自身が複製依頼したセグメント２の次のセグメントであるので、下位隣接ノードである配信ノード３が固定セグメントとして保持する必要がある。そのため、配信ノード２は、必須保持セグメント番号に１を加算して更新する、すなわち、必須保持セグメント番号を「３」に更新する。また、配信ノード２は、保持可能セグメント（セグメント３，４）から、必須保持セグメント番号に設定されたセグメント４と、既に固定セグメントとして保持しているセグメント４とを削除する。したがって、配信ノード２から配信ノード３に送信される保持要求クエリには、必須保持セグメント番号として「１」が格納され、保持可能セグメント番号には何れの番号も格納されない。
【０２１２】
配信ノード３は、配信ノード２から保持要求クエリを受信する。配信ノード３は、配信ノード２から受信した保持要求クエリに含まれる必須保持セグメント番号で指定されるセグメント３を固定セグメントとして保持している。また、配信ノード２から受信した保持要求クエリには保持可能セグメント番号は含まれていない。したがって、配信ノード３は、複製依頼クエリも保持要求クエリも送信せず、この時点で、スケールアウト発生によるセグメント配置処理が終了する。
【０２１３】
図２５Ａ，図２５Ｂ，図２５Ｃ，及び図２５Ｄは、スケールアウト発生時のセグメント配置処理において各配信ノードで実行される処理のフローチャートの例である。図２５Ａに示される処理のフローは、配信ノード群生成処理の実行によって配信ノード群が生成された後に、配信ノードに指示が入力された場合、及びパケットを受信した場合に実行される。
【０２１４】
ＯＰ１１１では、クエリ処理部１１は、スケールアウト配置要求の入力であるか否かを判定する。スケールアウト配置要求である場合には（ＯＰ１１１：Ｙｅｓ）、処理がＯＰ１１２に進む。スケールアウトの配置要求はない場には（ＯＰ１１１：Ｎｏ）、処理が図２５ＢのＯＰ１２１に進む。
【０２１５】
ＯＰ１１２では、クエリ処理部１１は、自ノードが固定セグメントとして、スケールアウト配置要求によって特定されるコンテンツのセグメント１を保持しているか否かを判定する。自ノードがセグメント１を固定セグメントとして保持している場合には（ＯＰ１１２：Ｙｅｓ）、既に遅延することなく追加されたクライアント分にコンテンツが配信されるように各配信ノードに配置されているため、複製依頼クエリも保持要求クエリも送信する必要が無い。この場合には、図２５Ａに示される処理が終了する。自ノードがセグメント１を固定セグメントとして保持していない場合には（ＯＰ１１２：Ｎｏ）、処理がＯＰ１１３に進む。
【０２１６】
ＯＰ１１３では、クエリ処理部１１は、自ノードがスケールアウト配置要求によって特定されるコンテンツのセグメント２を固定セグメントとして保持しているか否かを判定する。自ノードがセグメント２を固定セグメントとして保持している場合には（ＯＰ１１３：Ｙｅｓ）、セグメント２以降のセグメントは遅延することなく追加されたクライアント
群にコンテンツが配信されるように各配信ノードに配置されているため、保持要求クエリの送信の必要が無い。この場合には、処理がＯＰ１１５に進む。自ノードがセグメント２を固定セグメントとして保持していない場合には（ＯＰ１１３：Ｎｏ）、処理がＯＰ１１４に進む。
【０２１７】
ＯＰ１１４では、セグメント２から最小番号の固定セグメントの一つ前のセグメントまでのセグメント番号を含む保持要求クエリを下位隣接ノードに送信する。このとき、保持要求クエリには、必須保持セグメント番号として「２」が保持される。また、保持可能セグメント番号には、「３」から最小番号の固定セグメントの一つ前のセグメントのセグメント番号までの番号が含まれる。以降、最小番号の固定セグメントの番号は、Ｆｍｉｎと示される。また、最小番号の固定セグメントの一つ前のセグメントの番号は、Ｆｍｉｎ−１ト示される。
【０２１８】
ＯＰ１１５では、クエリ処理部１１は、セグメント１の複製を要求する複製依頼クエリを送信する。複製依頼クエリの送信とともに、クエリ処理部１１は、タイマーを開始する。
【０２１９】
ＯＰ１１６では、クエリ処理部１１は、複製依頼クエリ応答及びセグメント１を受信したか否かを判定する。複製依頼クエリ応答及びセグメント１を受信した場合には（ＯＰ１１６：Ｙｅｓ）、固定セグメント取得部１４は、セグメント１を記憶部１８に格納し、その後、自ノードにおいて図２５Ａに示される処理が終了する。複製依頼クエリ応答及びセグメント１を受信していない場合には（ＯＰ１１６：Ｎｏ）、処理がＯＰ１１７に進む。
【０２２０】
ＯＰ１１７では、クエリ処理部１１は、タイムアウトか否かを判定する。クエリ処理部１１は、予め設定される所定時間が経過しても複製依頼クエリ応答及びセグメント１が受信されない場合、すなわち、タイムアウトした場合には（ＯＰ１１７：Ｙｅｓ）、処理がＯＰ１１８に進む。予め設定される所定時間が経過していない場合には、すなわち、タイムアウトしていない場合には（ＯＰ１１７：Ｎｏ）、処理がＯＰ１１６に戻り、複製依頼クエリ応答及びセグメント１が受信されるまで、又は、タイムアウトするまでＯＰ１１６及びＯＰ１１７の処理が繰り返される。
【０２２１】
ＯＰ１１８では、クエリ処理部１１は、複製依頼クエリの再送回数が予め設定される上限回数を超えているか否かを判定する。複製依頼クエリの再送の上限回数は、例えば、３回に設定される。複製依頼クエリの再送回数が上限回数を超えている場合には（ＯＰ１１８：Ｙｅｓ）、図２５Ａに示される処理のフローが終了する。複製依頼クエリの再送回数が上限回数を超えていない場合には（ＯＰ１１８：Ｎｏ）、処理がＯＰ１１５に戻り、クエリ処理部１１は、複製依頼クエリを再送する。
【０２２２】
図２５ＢのＯＰ１２１では、クエリ処理部１１は、複製依頼クエリを受信したか否を判定する。複製依頼クエリを受信した場合には（ＯＰ１２１：Ｙｅｓ）、処理がＯＰ１２２に進む。複製依頼クエリを受信していない場合には（ＯＰ１２１：」Ｎｏ）、処理が図２５ＣのＯＰ１３１に進む。
【０２２３】
ＯＰ１２２では、クエリ処理部１１は、受信した複製依頼セグメントによって複製が要求されるセグメントを固定セグメントとして保持しているか否かを判定する。受信した複製依頼セグメントによって複製が要求されるセグメントを固定セグメントとして保持している場合には（ＯＰ１２２：Ｙｅｓ）、処理がＯＰ１２３に進む。受信した複製依頼セグメントによって複製が要求されるセグメントを固定セグメントとして保持していない場合には（ＯＰ１２２：Ｎｏ)、処理がＯＰ１２４に進む。
【０２２４】
ＯＰ１２３では、クエリ処理部１１は、複製依頼クエリによって複製が要求されたセグメントの複製を複製依頼クエリの生成ノードに送信する。その後、図２５Ｂに示される処理のフローが終了する。
【０２２５】
ＯＰ１２４では、クエリ処理部１１は、下位隣接ノードが存在するか否かを判定する。下位隣接ノードが存在する場合には（ＯＰ１２４：Ｙｅｓ）、処理がＯＰ１２５に進む。下位隣接ノードが存在しない場合には（ＯＰ１２４：Ｎｏ）、図２５Ｂに示される処理のフローが終了する。
【０２２６】
ＯＰ１２５では、クエリ処理部１１は、受信した複製依頼クエリを下位隣接ノードに送信する。その後、自ノードにおいて、図２５Ｂに示される処理のフローが終了する。
【０２２７】
図２５ＣのＯＰ１３１では、クエリ処理部１１は、保持要求クエリを受信したか否かを判定する。保持要求クエリを受信した場合には（ＯＰ１３１：Ｙｅｓ）、処理がＯＰ１３２に進む。保持要求クエリを受信していない場合には（ＯＰ１３１：Ｎｏ）、図２５Ｃに示される処理のフローが終了する。
【０２２８】
ＯＰ１３２では、クエリ処理部１１は、下位隣接ノードが存在するか否かを判定する。下位隣接ノードが存在する場合には（ＯＰ１３２：Ｙｅｓ）、処理がＯＰ１３３に進む。下位隣接ノードが存在しない場合には（ＯＰ１３２：Ｎｏ)、図２５Ｃに示される処理が
終了する。
【０２２９】
ＯＰ１３３では、クエリ処理部１１は、受信した保持要求クエリに含まれる保持可能セグメント番号うち最小の番号のセグメントを、自ノードが固定セグメントとして保持しているか否かを判定する。受信した保持要求クエリに含まれる保持可能セグメント番号うち最小の番号のセグメントを、自ノードが固定セグメントとして保持している場合には（ＯＰ１３３：Ｙｅｓ）、処理がＯＰ１３４に進む。受信した保持要求クエリに含まれる保持可能セグメント番号うち最小の番号のセグメントを、自ノードが固定セグメントとして保持していない場合には（ＯＰ１３３：Ｎｏ）、処理がＯＰ１３６に進む。
【０２３０】
ＯＰ１３４では、クエリ処理部１１は、保持可能セグメント番号を更新する。クエリ処理部１１は、受信した保持要求クエリに含まれる保持可能セグメント番号うち最小の番号のセグメントを保持しているので、保持可能セグメント番号から最小の番号を削除する。さらに、受信した保持要求クエリに含まれる保持可能セグメント番号に、自ノードの固定セグメントの番号が含まれている場合には、固定セグメントの番号も保持可能セグメント番号から削除する。
【０２３１】
ＯＰ１３５では、クエリ処理部１１は、更新された保持可能セグメント番号に格納される番号があるか否かを判定する。更新された保持可能セグメント番号に格納される番号がある場合には（ＯＰ１３５：Ｙｅｓ）、保持要求クエリを送信する必要があり、処理がＯＰ１３７に進む。更新された保持可能セグメント番号に格納される番号がない場合には（ＯＰ１３５：Ｎｏ）、必須保持セグメント番号のセグメントは自ノードが保持しているので保持要求クエリを送信する必要が無いので、図２５Ｃに示される処理が終了する。
【０２３２】
ＯＰ１３６では、クエリ処理部１１は、必須保持セグメント番号及び保持可能セグメント番号を更新する。クエリ処理部１１は、受信した保持要求クエリに含まれる保持可能セグメント番号うち最小の番号で必須保持セグメントを書き換える。クエリ処理部１１は、受信した保持要求クエリに含まれる保持可能セグメント番号うち最小の番号は必須保持セグメント番号となったので、保持可能セグメント番号から最小の番号を削除する。さらに、受信した保持要求クエリに含まれる保持可能セグメント番号に、自ノードの固定セグメ
ントの番号が含まれている場合には、固定セグメントの番号も保持可能セグメント番号から削除する。その後、処理がＯＰ１３７に進む。
【０２３３】
ＯＰ１３７では、クエリ処理部１１は、ＯＰ１３４において更新された保持可能セグメント番号を含む、又は、ＯＰ１３６において更新された必須保持セグメント番号と保持可能セグメント番号とを含む、保持要求クエリを下位隣接ノードに送信する。その後、処理が図２５ＤのＯＰ１４１に進む。
【０２３４】
ＯＰ１４１では、クエリ処理部１１は、受信した保持要求クエリに含まれる必須保持セグメント番号のセグメントを固定セグメントとして保持しているか否かを判定する。受信した保持要求クエリに含まれる必須保持セグメント番号のセグメントを固定セグメントとして保持している場合には（ＯＰ１４１：Ｙｅｓ）、複製依頼クエリを送信する必要が無く、図２５Ｄに示される処理が終了する。受信した保持要求クエリに含まれる必須保持セグメント番号のセグメントを固定セグメントとして保持していない場合には（ＯＰ１４１：Ｎｏ）、処理がＯＰ１４２に進む。
【０２３５】
ＯＰ１４２では、クエリ処理部１１は、必須保持セグメント番号のセグメントの複製依頼クエリを送信する。複製依頼クエリを送信するとともに、クエリ処理部１１は、タイマーを開始する。
【０２３６】
ＯＰ１４３では、クエリ処理部１１は、複製依頼クエリ応答及び複製依頼したセグメントを受信したか否かを判定する。複製依頼クエリ応答及び複製依頼したセグメントを受信した場合には（ＯＰ１４３：Ｙｅｓ）、固定セグメント取得部１４は、受信した複製依頼のセグメントを記憶部１８に格納し、その後、自ノードにおいて図２５Ｄに示される処理が終了する。複製依頼クエリ応答及び複製依頼したセグメントを受信していない場合には（ＯＰ１４３：Ｎｏ）、処理がＯＰ１４４に進む。
【０２３７】
ＯＰ１４４では、クエリ処理部１１は、タイムアウトか否かを判定する。クエリ処理部１１は、予め設定される所定時間が経過しても複製依頼クエリ応答及び複製依頼したセグメントが受信されない場合、すなわち、タイムアウトした場合には（ＯＰ１４４：Ｙｅｓ）、処理がＯＰ１４５に進む。予め設定される所定時間が経過していない場合には、すなわち、タイムアウトしていない場合には（ＯＰ１４４：Ｎｏ）、処理がＯＰ１４３に戻り、複製依頼クエリ応答及び複製依頼したセグメントが受信されるまで、又は、タイムアウトするまでＯＰ１４３及びＯＰ１４４の処理が繰り返される。
【０２３８】
ＯＰ１４５では、クエリ処理部１１は、複製依頼クエリの再送回数が予め設定される上限回数を超えているか否かを判定する。複製依頼クエリの再送の上限回数は、例えば、３回に設定される。複製依頼クエリの再送回数が上限回数を超えている場合には（ＯＰ１４５：Ｙｅｓ）、図２５Ｄに示される処理のフローが終了する。複製依頼クエリの再送回数が上限回数を超えていない場合には（ＯＰ１４５：Ｎｏ）、処理がＯＰ１４２に戻り、クエリ処理部１１は、複製依頼クエリを再送する。
【０２３９】
図２５Ａ〜図２５Ｄに示される処理が各配信ノードによって実行されることによって、例えば、図２４に示されるスケールアウト発生時のセグメント配置処理が実行され、図２３のようなセグメントの配置となる。
【０２４０】
＜第１実施形態の作用効果＞
配信コンテンツ分散配置処理において、各セグメントが、クライアント群にネットワーク上の距離が近い配信ノードから順番に、先頭のセグメントから配置されていき、クライアント群からネットワーク上の距離が最も遠い配信ノードまで配置されると、次に、該最
も遠いクライアントから順番に配置されていく。これによって、クライアント群にコンテンツを配信する際には、コンテンツ配信要求からコンテンツ再生までの時間を最も短くする、すなわち、遅延を小さく抑えることができる。また、各セグメントは、セグメント番号の順番に配信ノードに配置されていくので、コンテンツ配信の際にもセグメント番号の順番にクライアント端末に到着し、クライアント端末上で途切れることなくコンテンツが再生される。また、ネットワーク全体が保持する配信コンテンツのデータ量を小さく抑えることができる。
【０２４１】
クライアント群へのコンテンツの配信処理では、各配信ノードは、コンテンツ配信要求ク又は配信開始クエリを受信すると、配信に必要な一時セグメントの保持期間を延長する。これによって、アクセス集中時には、クライアント群にネットワーク上の距離が最も近い配信ノードに全セグメントが保持されることになり、ミラーサーバが一時的に形成される。これによって、アクセス集中時には、コンテンツ配信要求をクライアント群にネットワーク上の距離が最も近い配信ノードのみで処理することができ、配信開始クエリ送信の無駄を省くことができる。また、各配信ノード間の一時セグメントの送信がされなくなるので、ネットワーク上のデータの流量を抑えることができる。
【０２４２】
また、一時セグメントを必要とするコンテンツ配信要求又は配信開始クエリが、所定時間受信されない場合に、一時セグメントは配信ノードから削除される。これによって、ネットワーク全体で保持されるデータ量が増えることを防ぐことができる。
【０２４３】
スケールアウトが発生した場合には、スケールアウト発生時のコンテンツ配置処理が実行され、新たに追加されたクライアント群に最もネットワーク上の距離が近い配信ノードに先頭セグメントが配置される。これによって、クライアント群が新たに追加された場合でも、新たなクライアント群においてコンテンツ配信要求からコンテンツ再生までの時間、すなわち、遅延を小さく抑えることができる。
【０２４４】
配信ノード群生成処理，配信コンテンツ分散配置処理，クライアント群へのコンテンツの配信処理，及びスケールアウト時のコンテンツ配置処理の何れにおいても、各配信ノードは自律的に動作するので、データ配信システムの管理者は指示を入力するだけで済み、手間がかからない。
【０２４５】
＜その他＞
第１実施形態では、図２に示されるような波形のセグメント分散配置について説明したが、セグメントの配置は、図２のような波形に限定されるものではない。クライアント群にネットワーク上の距離が最も近い配信ノードに先頭セグメントが配置され、セグメント番号の順番で、次の隣接ノード、その次の隣接ノードへと次々と配置されていく方法であればよい。
【０２４６】
第１実施形態では、各クエリは、マルチキャスト又はユニキャストで送信される。ただし、第１実施形態に説明されたものに限られない。各クエリは、マルチキャスト又はユニキャストの何れで送信されてもよく、データ配信システムの管理者が自由に選択可能である。
【符号の説明】
【０２４７】
１        ノード
１１      クエリ処理部
１２      隣接ノード情報取得部
１３      配信ノード群情報管理部
１４      固定セグメント取得部
１５      一時セグメント管理部
１６      ルーティング部
１７      テーブル管理部
１９      セグメント送信部
１８      記憶部
１８１    一時セグメントバッファ
１８２    配信ノード群情報
１８３    ストリーム管理テーブル
１８４    固定セグメント群
【図１】
0005732919.tif 000003
【図２】
0005732919.tif 000004
【図３】
0005732919.tif 000005
【図４】
0005732919.tif 000006
【図５Ａ】
0005732919.tif 000007
【図５Ｂ】
0005732919.tif 000008
【図６】
0005732919.tif 000009
【図７】
0005732919.tif 000010
【図８Ａ】
0005732919.tif 000011
【図８Ｂ】
0005732919.tif 000012
【図８Ｃ】
0005732919.tif 000013
【図９】
0005732919.tif 000014
【図１０】
0005732919.tif 000015
【図１１Ａ】
0005732919.tif 000016
【図１１Ｂ】
0005732919.tif 000017
【図１２】
0005732919.tif 000018
【図１３Ａ】
0005732919.tif 000019
【図１３Ｂ】
0005732919.tif 000020
【図１３Ｃ】
0005732919.tif 000021
【図１３Ｄ】
0005732919.tif 000022
【図１３Ｅ】
0005732919.tif 000023
【図１３Ｆ】
0005732919.tif 000024
【図１３Ｇ】
0005732919.tif 000025
【図１３Ｈ】
0005732919.tif 000026
【図１３Ｉ】
0005732919.tif 000027
【図１３Ｊ】
0005732919.tif 000028
【図１３Ｋ】
0005732919.tif 000029
【図１３Ｌ】
0005732919.tif 000030
【図１３Ｍ】
0005732919.tif 000031
【図１３Ｎ】
0005732919.tif 000032
【図１３Ｏ】
0005732919.tif 000033
【図１４】
0005732919.tif 000034
【図１５】
0005732919.tif 000035
【図１６】
0005732919.tif 000036
【図１７】
0005732919.tif 000037
【図１８】
0005732919.tif 000038
【図１９】
0005732919.tif 000039
【図２０】
0005732919.tif 000040
【図２１】
0005732919.tif 000041
【図２２】
0005732919.tif 000042
【図２３】
0005732919.tif 000043
【図２４】
0005732919.tif 000044
【図２５Ａ】
0005732919.tif 000045
【図２５Ｂ】
0005732919.tif 000046
【図２５Ｃ】
0005732919.tif 000047
【図２５Ｄ】
0005732919.tif 000048