(57)【要約】      （修正有）【課題】P２P技術を用いた大規模な放送配信に耐え得ると共に、ユーザトラッキングや品質維持等の制御が容易となる商用の大規模動画配信基盤を構築可能とする。【解決手段】ネットワーク構成システム１４は、グループ分け処理部１４ａにより、ノード１３を、条件情報保持部１４ｄが記憶装置に保持した予め定められた条件に従って、他のノードとのグループに振り分け、同じグループに属する他ノードとの接続に関しては、グループ内接続設定処理部１４ｂにより、各ノード間でメッシュ型の配信を行うよう接続先の設定を行い、他のグループに属する他ノードとの接続に関しては、グループ間接続設定処理部１４ｃにより、当該グループ間でツリー型のパケット配信を行うよう接続先の設定を行う。【選択図】図１
2011055070.tif 000002
【特許請求の範囲】
【請求項１】
Ｐ２Ｐ型でのパケット配信を行うネットワークの構築を行うシステムであって、
ネットワークを構成する各ノードを予め定められた条件に従ってグループ分けする第１の手段と、
同じグループに属する各ノード間ではメッシュ型の配信を行うよう各ノードの接続先を設定する第２の手段と、
各グループ間ではツリー型のパケット配信を行うよう各ノードの接続先を設定する第３の手段と
を有することを特徴とするネットワーク構築システム。
【請求項２】
請求項１に記載のネットワーク構築システムであって、
上記予め定められた条件は、同じグループに所属させるノードの数の上限を定めた閾値条件を含み、
上記第１の手段は、上記閾値条件で定められた数分までのノードを同じグループに所属させ、
同じグループに属する各ノードの数が上記閾値条件で定められた閾値を超えると、当該グループを２つに分割して各ノードをいずれかのグループに振り分ける
ことを特徴とするネットワーク構築システム。
【請求項３】
請求項１もしくは請求項２のいずれかに記載のネットワーク構築システムであって、
上記予め定められた条件は、ホップ数を含むネットワーク的な距離が近いノードを同じグループとするとのグループ化条件を含み、
上記第１の手段は、上記グループ化条件に従って、各ノードのグループ化を行う
ことを特徴とするネットワーク構築システム。
【請求項４】
請求項１から請求項３のいずれかに記載のネットワーク構築システムであって、
上記第１〜第３の手段を各ノードに設け、
各ノードにおいて、Ｐ２Ｐ配信の参加時に、所属するグループの特定と、接続先となる親グループと子グループの特定を行う
ことを特徴とするネットワーク構築システム。
【請求項５】
請求項１から請求項４のいずれかに記載のネットワーク構築システムであって、
上記ネットワークは、オーバーレイネットワークであることを特徴とするネットワーク構築システム。
【請求項６】
コンピュータを、請求項１から請求項５のいずれかに記載のネットワーク構築システムにおける上記第１〜第３の手段として機能させるためのプログラム。
【請求項７】
Ｐ２Ｐ型でのパケット配信を行うネットワークの構築を、プログラムされたコンピュータ装置により行う方法であって、
コンピュータ装置に、請求項１から請求項５のいずれかに記載のネットワーク構築システムにおける上記第１〜第３の手段を設け、
プログラムされたコンピュータ装置による処理手順として、
上記第１の手段による各ノードのグループ分け処理手順と、
上記第２の手段による同じグループに属する各ノード間でのメッシュ型配信の設定処理手順、および、上記第３の手段による各グループ間でのツリー型配信の設定処理手順を含むことを特徴とするネットワーク構築方法。
【請求項８】
請求項１から請求項５のいずれかに記載のネットワーク構築システムにより構築されたツリー型とメッシュ型混在のネットワークにおけるデータ配信方法であって、
データの配信要求元ノードから当該データの配信元ノードに対して当該データの配信が要求されると、
上記配信元ノードは、負荷が予め定められた閾値を越えていないか、もしくは、自配信元ノードにアクセス要求している子グループの数が予め定められた閾値を越えていないかを判定し、
いずれも閾値を越えていなければ、上記配信元ノードから上記配信要求元ノードに当該データを配信し、
いずれかが閾値を越えていれば、もしくは、上記配信元ノードから上記配信要求元ノードへの当該データの配信が失敗すれば、上記配信元ノードは、自身が所属するグループの子グループに属し当該データを保持するノードを上記配信要求元ノードに通知し、
該通知を受けた上記配信要求元ノードは、通知されたノードに対して当該データの配信を要求する
ことを特徴とするデータ配信方法。
【請求項９】
請求項８に記載のネットワーク構築システムにより構築されたツリー型とメッシュ型混在のネットワークにおけるデータ配信方法であって、
子グループからのデータ配信要求があれば、要求を受けたグループ内の各ノードからランダムに選ばれたノードが、要求されたデータを配信する
ことを特徴とするデータ配信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネットやISP（Internet Services Provider）ネットワーク等の広域ネットワークにおけるネットワーク構築技術に係り、特に、大規模な放送コンテンツ配信に耐え得るネットワークを構築するのに好適な技術に関するものである。
【背景技術】
【０００２】
大規模な放送コンテンツ配信には、通常は、電波やCATV（Common Antenna TeleVision, Community Antenna TeleVision）等の放送専用信号を流す回線が用いられてきた。昨今IPネットワークの普及が進むにつれ、IP（Internet Protocol）ネットワーク上にIPの信号として動画を配信する技術が有望視されている。
【０００３】
閉域ネットワークにおいては、IP技術を用いた一斉配信に、限られた領域を対象としたマルチキャスト方式を用いることで、サーバからの配信コストを最低限に留めたまま配信することが可能となる。しかし、この技術では、ルータ等の装置コストが高価であることと、設備を完全に保持する限られた範囲にしかサービスを提供することができないという問題がある。
【０００４】
このため、主にインターネットなどのオープンなIPネットワーク上においては、アプリケーションレイヤマルチキャストやオーバーレイマルチキャストと呼ばれる技術を用いて、各参加ノードでパケットの複製を行うP２P（Peer to Peer）型の配信技術が有望視されている。
【０００５】
P２P配信では、配信元から流されるコンテンツから論理的なリンクが構築され、そこに１つずつＰ２Ｐアプリケーションが動作するノード（ピア）が連なっていくことで配信木が論理レイヤに形成されていく。このため各ノードで動作するＰ２Ｐアプリケーションの方式を定義することによってその全体の挙動も定義される。
【０００６】
P２P型での配信基盤、すなわち、ネットワークトポロジは、例えば、非特許文献１に記載のように、ツリー型とメッシュ型に大きく分けることができる。
【０００７】
ツリー型では、安定的な上り帯域を持つノード（ピア）の確保が必要であることから、現在、ADSL（Asymmetric Digital Subscriber Line）等の非対称なアクセスが大多数であった状況を反映して、メッシュ型が、大規模な配信では主流となっている。
【０００８】
しかし、メッシュ型の配信においては、スケーラビリティが高くなる一方で、利用者の状況、ノード（ピア）間でのコンテンツのやり取りや、品質的ボトルネックの所在、といった通信情報の追跡が困難である。
【０００９】
このため、ユーザのふるまいを基にした課金や、品質ボトルネックを取り除いて品質を一定以上に保つ等といった管理・制御を行うことが、メッシュ型の配信では一般に難しくなる。このため、ビジネスとして配信を行う際や、通信事業者がキャリアグレードの配信に用いるためには、この点を解決する必要がある。
【００１０】
尚、上述の非特許文献１においては、「アプリケーション層マルチキャスト（Application-Level/Layer Multicast，ＡＬＭ）」に関連してオーバーレイネットワーク技術が開示されている。このオーバーレイネットワークは、下位のネットワークレイヤを変更することなくエンド・ツー・エンドＱｏＳの向上を可能とする有力な技術であり、例えば非特許文献２においても記載されている。
【００１１】
このオーバーレイネットワークとは、例えば非特許文献３においても記載のように、既存のリンクを用いて、その上位層に目的に応じて論理的（仮想的）なリンクを形成し、構成するネットワークである。
【００１２】
このようなオーバーレイネットワークによるＱｏＳ管理の基本的な概念を図４に例示する。図４は、オーバーレイネットワークの構成例を示すブロック図であり、オーバーレイネットワーク（図中「Ｏｖｅｒｌａｙ−ＮＷ」と記載）４１は複数のオーバーレイノード４１ａ，４１ｂ，４１ｃからなり、複数のＩＰルータ４２ａ〜４２ｅからなるＩＰネットワーク（図中「ＩＰ−ＮＷ」と記載）４２上に論理的に形成されている。
【００１３】
このような構成のＩＰネットワーク４２において、ｘからｙに向けて、破線矢印で表わされる経路にトラヒックが流れているとする。また、この経路上には輻輳しているＩＰルータ４２ｄが存在しており、その結果として、ｘ，ｙ間のＱｏＳが低下しているとする。
【００１４】
このとき、オーバーレイノード４１ａ，４１ｂ，４１ｃで形成されるオーバーレイネットワーク４１を用いて、実線矢印で表される経路（ｘ→オーバーレイノード４１ａ→オーバーレイノード４１ｂ→オーバーレイノード４１ｃ→ｙ）にトラヒックを迂回させることができれば、上記の輻輳を回避できる。
【００１５】
実際、非特許文献４，５，６，７等では、上記のような迂回経路が実網において多数存在していることを実測に基づいて示している。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】首藤  一幸，“アプリケーション層マルチキャスト”，ＵＮＩＸ（登録商標）  ｍａｇｇａｚｉｎｅ．，  ２００6年１０月号，ｐｐ．３４−４３，（株）アスキー，２００６年９月１６日．
【非特許文献２】Ｌ．Ｚｈｉ  ａｎｄ  Ｐ．Ｍｏｈａｐａｔｒａ，“ＱＲＯＮ：ＱｏＳ−ａｗａｒｅ  ｒｏｕｔｉｎｇ  ｉｎ  ｏｖｅｒｌａｙ  ｎｅｔ−ｗｏｒｋｓ，”ＩＥＥＥ  Ｊ．Ｓｅｌｅｃｔ．Ａｒｅａｓ  Ｃｏｍｍｕｎ．，ｖｏｌ．２２，ｐｐ．２９−４０，Ｊａｎｕａｒｙ  ２００４．
【非特許文献３】ＷＩＤＥプロジェクト，“オーバーレイネットワークによる統合分散環境，”ＷＩＤＥプロジェクト研究報告書，第１７部，２００２．
【非特許文献４】亀井，川原，“エンドホストオーバーレイネットワークによるトラヒックエンジニアリングとその有効性，”信学ソ大，ＢＳ−５−３，２００４．
【非特許文献５】Ｓ．Ｒｅｗａｓｋａｒ  ａｎｄ  Ｊ．Ｋａｕｒ，“Ｔｅｓｔｉｎｇ  ｔｈｅ  Ｓｃａｌａｂｉｌｉｔｙ  ｏｆ  Ｏｖｅｒｌａｙ  Ｒｏｕｔｉｎｇ  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅｓ，”Ｐｒｏｃ．ＰＡＭ  ２００４．Ａｐｒｉｌ  ２００４．
【非特許文献６】Ｓ．Ｂａｎｅｒｊｅｅ，Ｔ．Ｇ．Ｇｒｉｆｉｎ  ａｎｄ  Ｍ．Ｐｉａｓ，“Ｔｈｅ  Ｉｎｔｅｒｄｏｍａｉｎ  Ｃｏｎｎｅｃｔｉｖｉｔｙ  ｏｆ  ＰｌａｎｅｔＬａｂ  Ｎｏｄｅｓ，”  Ｐｒｏｃ．ＰＡＭ  ２００４，Ａｐｒｉｌ  ２００４．
【非特許文献７】平岡，長谷川，村田，“遅延および帯域情報を用いたオーバーレイルーティングの有効性評価，”  信学技報  ＣＱ２００７−１８，２００７年７月．
【発明の概要】
【発明が解決しようとする課題】
【００１７】
解決しようとする問題点は、従来のツリー型のネットワークでは、安定的な上り帯域を持つノードの確保が必要であることから、スケーラビリティが低く、大規模な配信には適していない点と、従来のメッシュ型のネットワークでは、スケーラビリティが高くなる一方で、利用者の状況、コンテンツのやり取りや、品質的ボトルネックの所在、といった通信情報の追跡が困難であり、ユーザのふるまいを基にした課金や、品質ボトルネックを取り除いて品質を一定以上に保つ等といった管理・制御を行うことが難しく、ビジネスとして配信を行う際や、通信事業者がキャリアグレードの配信に用いるのに適していない点である。
【００１８】
本発明の目的は、これら従来技術の課題を解決し、P２P技術を用いた大規模な放送配信に耐え得ると共に、ユーザトラッキングや品質維持等の制御が容易となる商用の大規模動画配信基盤を構築可能とすることである。
【課題を解決するための手段】
【００１９】
上記目的を達成するため、本発明は、ネットワークを、ツリー型とメッシュ型を混在させて形成すると共に、ネットワークの規模に応じて柔軟にツリー型とメッシュ型の構成を切り替えることを特徴とする。具体的には、ネットワークを構成しているノード（ピア）をグループ化し、グループ内ではメッシュ型、グループ間ではツリー型とする。そして、各グループにおけるノード数の最大値等の閾値を調整することにより、メッシュ型とツリー型の比率を変えて混在化させる。例えば、グループの最大ノード数を１にするとツリー型と同じになり、最大ピア数を無限大にするとメッシュ型と同様になる。
【発明の効果】
【００２０】
本発明によれば、ネットワークを構成しているノードをグループ化し、グループ内ではメッシュ型、グループ間ではツリー型としており、これにより、ツリー構造の部分ではユーザ挙動の追跡や品質悪化箇所を発見し、課金や障害を取り除くことが可能となり、全体をメッシュ型で構成した場合と比較して制御性は高くなる。また、メッシュ型で構成されるグループでは、制御可能性は犠牲になるものの、スケーラビリティは維持できるため、全体をツリー型で構成した場合と比較して多数の利用者を収容できる。この結果、スケーラビリティと可制御性を両立させたP２P配信基盤を構築することができる。また、本発明では、対象のネットワークの規模に応じてグループ構成を調整・制御することにより、対象のネットワークのスケーラビリティと制御困難性をコントロールすることが可能である。すなわち、メッシュ型とツリー型のトポロジ・グラフにおいては、節点数が同一の場合、メッシュ型の方の次数が高くなる。このため、メッシュ型の方が冗長度、リンク数ともに大きくなる。冗長度はネットワークのスケーラビリティと相関がある指標で、リンク数はネットワーク制御困難性と相関がある指標である。本発明では、これらの指標を適切にコントロールすることを目指し、2つのグラフ形態の混合型構造を構成し、各ピアグループのサイズを調整することで、ネットワークのスケーラビリティと制御困難性をコントロールすることが可能となる。
【図面の簡単な説明】
【００２１】
【図１】本発明に係るネットワーク構築システムの構成と当該システムで構築されたネットワークの構成例を示す説明図である。
【図２】図１におけるネットワークを構成する各ノードにおける保持情報例を示す説明図である。
【図３】従来のツリー型およびメッシュ型のネットワークの構成例を示す説明図である。
【図４】従来のオーバーレイネットワークの構成例を示す説明図である。
【図５】図１におけるネットワーク構築システムによる本発明に係るネットワーク構築方法の処理動作例を示すフローチャートである。
【発明を実施するための形態】
【００２２】
以下、図を用いて本発明を実施するための形態例を説明する。まず、図３を用いて、従来のツリー型およびメッシュ型のネットワークの構成を説明する。図３（ａ）においては、ノード（ピア）３１ａ〜３１ｇからなる従来のツリー型のネットワーク構成を示しており、このようなツリー型のネットワークでは、まず、ノード３１ａからノード３１ｂ，３１ｃにデータが配信され、さらに、ノード３１ｂからノード３１ｄ，３１ｅに、ノード３１ｃからノード３１ｆ，３１ｇに、それぞれ、データが配信される。
【００２３】
このようなツリー型のネットワークを構成するために、各ノード(ピア)は配信を受け取る親ノード(ピアか配信元サーバのいずれか)のアドレス情報と、配信を提供する子ノード(ピア)のアドレス情報を保持し、各ノード（ピア）は、配信元サーバに配信を要求するアクセスを行う。
【００２４】
そして、配信元となったピア(または配信元サーバ)は、自分が具備したＣＰＵ（Central Processing Unit）やＨＤＤ（Hard Disk Drive）あるいは自ノードが接続された回線等の負荷が予め定められた一定の閾値を越える場合、または、配信を提供する子ノードが充分な数になった時点で、さらに配信を要求してアクセスしてきたピアを自分の子ノードにアクセスするよう誘導する。
【００２５】
さらに、子ノード(ピア)においても、配信元となったピア(または配信元サーバ)と同様に、自身の負荷に応じて子ノードへ誘導するように動作する。
【００２６】
もし、新規参加ピアによる或るノードへのアクセスが失敗した場合は、新規参加ピアは、当該ノードの親ノードへアクセスし、この親ノードから別の子ノードへ誘導を受ける。
【００２７】
以上の処理動作を繰り返すことにより、図３（ａ）に示すツリー型のネットワークが構成される。
【００２８】
このようなツリー型のネットワークでは、ノードの出入りがなければ安定的に配信ができる一方で、それぞれのノードが安定的に上り配信帯域を持つ必要がある。
【００２９】
次に、図３（ｂ）に示す従来のメッシュ型のネットワークの構成を説明する。図３（ｂ）においては、ノード（ピア）３２ａ〜３２ｅからなる従来のメッシュ型のネットワーク構成を示しており、このようなメッシュ型のネットワークでは、例えば、ノード３２ａからノード３２ｂを経由して、もしくは、ノード３２ａからノード３ｄおよびノード３２ｂを経由して、ノード３２ｅにデータが配信され、また、ノードｃからのノード３２ｅへのデータ配信は、（１）ノード３２ａ→ノード３２ｂ経由、（２）ノード３２ａ→ノード３２ｄ→ノード３２ｂ経由、（３）ノード３２ｄ→ノード３２ｂ経由で行われる。
【００３０】
このようなメッシュ型のネットワークを構成するために、各ノード(ピア)は、親ノード、子ノードの階層は持たず、他ピアのアドレス情報をランダム(全てではなく、たとえば１０個ずつとか、最近アクセスしたピアの情報のみ等)に持ち、ある程度のピアが配信可能になるまで、各ピアが、配信元に配信を要求するアクセスを行う。
【００３１】
新たに参加したピアは、ランダムに持っている他のピアのアドレス情報 (あるいは全ピアの情報を持ち、その中からランダムに接続先を選択する場合もある)を基に、必要なコンテンツ片の情報を接続先の全てにリクエストする。
【００３２】
充分なコンテンツ片が収集できなかった場合には、配信元へアクセスする。
【００３３】
以上の処理動作を繰り返すことにより、図３（ｂ）に示すメッシュ型のネットワークが構成される。
【００３４】
このようなメッシュ型のネットワークにおいては、配信方向を仮定せずにコンテンツの断片を収集するため、ノードの出入りが頻繁におきても、安定度が影響を受けず、高いスケーラビリティを保てる。しかし、通信の流れが一定しないために制御は困難である。
【００３５】
これに対して、図１に示すネットワークは、図３（ａ），（ｂ）において示したツリー型およびメッシュ型のネットワークにおけるそれぞれの問題点を解決するよう構成されたものである。尚、図１に示すネットワークはオーバーレイネットワークである。
【００３６】
すなわち、図１におけるネットワークは、ツリー型とメッシュ型を混在させて形成している。さらに、本例のネットワークにおいては、規模の拡大に応じて柔軟にツリー型とメッシュ型の構成を切り替える。
【００３７】
具体的には、図１のネットワークを構成している各ノード（オーバーレイノード）１０ａ〜１０ｅ，１１ａ〜１１ｅ，１２ａ〜１２ｅ，をグループ１０，１１，１２化し、各グループ１０〜１２内では各ノードをメッシュ型で接続し、グループ１０〜１２間ではツリー型で接続する。
【００３８】
図１においては、ノード１０ａ〜１０ｅがグループ１０においてメッシュ型ネットワークを構成し、ノード１１ａ〜１１ｅがグループ１１においてメッシュ型ネットワークを構成し、ノード１２ａ〜１２ｅがグループ１２においてメッシュ型ネットワークを構成しており、各グループ１０，１１，１２でツリー型のネットワークを構成している。
【００３９】
そして、各グループ１０〜１２における各ノードの数の最大値等の閾値を調整することにより、メッシュ型とツリー型の比率を変えて混在化させる。例えば、グループ１０〜１２の最大ノード数を１にするとツリー型と同じになり、グループ１０〜１２の最大ノード数を無限大にするとメッシュ型と同様になる。
【００４０】
このように、図１のネットワーク（オーバーレイネットワーク）を構成しているノード（オーバーレイノード）をグループ１０〜１２化し、グループ内ではメッシュ型、グループ間ではツリー型としてネットワークを構成することにより、ツリー構造の部分ではユーザ挙動の追跡や品質悪化箇所を発見し、課金や障害を取り除くことが可能となり、全体をメッシュ型で構成した場合と比較して制御性は高くなる。
【００４１】
また、メッシュ型で構成されるグループでは、制御可能性は犠牲になるものの、スケーラビリティは維持できるため、全体をツリー型で構成した場合と比較して多数の利用者を収容できる。この結果、スケーラビリティと可制御性を両立させたP２P配信基盤を構築することができる。
【００４２】
図１に示す例では、このようなメッシュ型とツリー型が混在したネットワーク構成を、各ノード１０ａ〜１０ｅ，１１ａ〜１１ｅ，１２ａ〜１２ｅが、Ｐ２Ｐ配信の参加時に、所属するグループと、接続先となる親グループと子グループの特定を行う。
【００４３】
すなわち、各ノード１０ａ〜１０ｅ，１１ａ〜１１ｅ，１２ａ〜１２ｅは、ＣＰＵや主メモリ、表示装置、入力装置、外部記憶装置等を具備したコンピュータ装置からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、ノード１３に示すように、本発明に係るネットワーク構成システム１４の機能を実装している。
【００４４】
そして、ネットワーク構成システム１４は、プログラムされたコンピュータ処理を実行する手段として、グループ分け処理部１４ａとグループ内接続設定処理部１４ｂおよびグループ間接続設定処理部１４ｃと制御情報保持部１４ｄを具備し、図５に示す処理手順により、メッシュ型とツリー型が混在したネットワークの構築を行う。
【００４５】
以下、図１および図５を用いて、図１に示すメッシュ型とツリー型が混在したネットワークの構成処理動作を説明する。
【００４６】
図１におけるノード１３は、Ｐ２Ｐ配信の参加時に、ネットワーク構成システム１４を起動し、ネットワーク構成システム１４は、グループ分け処理部１４ａにより、ノード１３を、条件情報保持部１４ｄが記憶装置に保持した予め定められた条件に従って、他のノードとのグループに振り分け（ステップＳ５０１）、同じグループに属する他ノードとの接続であれば（ステップＳ５０２）、グループ内接続設定処理部１４ｂにより、各ノード間でメッシュ型の配信を行うよう接続先の設定を行い（ステップＳ５０３）、他のグループに属する他ノードとの接続であれば（ステップＳ５０２）、グループ間接続設定処理部１４ｃにより、当該グループ間でツリー型のパケット配信を行うよう接続先の設定を行う（ステップＳ５０４）。
【００４７】
尚、条件情報保持部１４ｄが記憶装置に保持する予め定められた条件は、例えば、同じグループに所属させるノードの数の上限を定めた閾値条件を含み、グループ分け処理部１４ａは、ノード１３を所属させるグループにおけるノード数が、閾値条件で定められた数以内であればノード１３を当該グループに所属させるが、所属させるグループにおいて既に所属しているノードの数が、閾値条件で定められた数を超えると、当該グループを２つに分割してノード１３を含む各既所属ノードをいずれかのグループに振り分ける。
【００４８】
また、条件情報保持部１４ｄが記憶装置に保持する予め定められた条件として、ホップ数を含むネットワーク距離が近いノードを同じグループとするとのグループ化条件を含み、グループ分け処理部１４ａは、このグループ化条件に従って、各ノードのグループ化を行う。
【００４９】
以下、このような構成からなるネットワークにおけるデータの配信動作について説明する。
【００５０】
図１におけるネットワークでのデータ配信の基本的なアーキテクチャとしては、各参加ノードは、グループ化されたノード群を単位としてツリー型の構造を保持し、まず、（１）基本的なデータ配信は、ツリー構造に従い行う。
【００５１】
（２）その一方で、同一グループに所属した各ノード間では、メッシュ方式でのデータ配信を行う。
【００５２】
（３）さらに、補助的に、全体面でのメッシュ方式での配信を行う。
【００５３】
以上の３層構造により、図１におけるネットワークでは、制御とスケーラビリティを実現する。
【００５４】
図２を用いて、図１におけるネットワークの構築手順を説明する。図２（ａ）においては、従来のネットワークの構成手順を示しており、図２（ｂ）においては、図１における本発明に係るネットワークの構成手順を示している。
【００５５】
図２（ａ）において、各ノード２１〜２４は、ツリー型のネットワーク（オーバーレイネットワーク）を構成しているが、従来、各ノード２１〜２４は、ツリー型もしくはメッシュ型のいずれかの構造のネットワークを構成することができ、ツリー型のネットワークを構成する際に用いる情報（保持情報（ツリー））として、親ノードの識別情報と子ノードの識別情報を保持し、メッシュ型のネットワークを構成する際に用いる情報（保持情報（メッシュ））として、適当な接続先ノードの識別情報を保持する。
【００５６】
図２（ａ）に示す例では、例えば、ノード２２は、保持情報（ツリー）において、親ノードとしてノード２１の識別情報を、子ノードとしてノード２３，２４の識別情報を保持しており、これにより、各ノード２１〜２４は、ツリー型のネットワークを構成している。
【００５７】
これに対して、図２（ｂ）においては、ツリー型とメッシュ型が混在したネットワークを構成しており、例えば、ノード２６ａを含む各ノードにおいては、ツリー型のネットワークを構成する際に用いる情報（保持情報（ツリー））として、親ノードが所属するグループの識別情報と子ノードが所属するグループの識別情報を保持し、メッシュ型のネットワークを構成する際に用いる情報（保持情報（メッシュ））として、同一グループのノードの識別情報と共に適当な接続先ノードの識別情報を保持する。
【００５８】
図２（ｂ）に示す例では、例えばノード２６ａを含む各ノードは、保持情報（ツリー）において、親ノードグループとしてグループ２５の識別情報を、子ノードグループとしてグループ２７，２８の識別情報を保持しており、これにより、ノード２６を含む各ノードは、ツリー型とメッシュ型の混在したネットワークを構成する。
【００５９】
このように、図２（ｂ）においては、ツリー構造は、既存方式と同様にして構築する。この際、P２P型のツリー構造の配信基盤は、配信事業者の意図に従って、ピア(Ｐ２Ｐアプリケーションを起動したノード)同士が論理的リンク(TCPのコネクション等)を張ることによってサービス提供時に構築される。
【００６０】
一方、ノード２６ａを含む各参加ノードは、自分がツリー構造の中で、どのグループに所属するかの情報を持ち、同一グループに所属したノード同士では、メッシュの構造を保持して配信を行い、他グループからのリクエストに対しては、ツリーの構造を意識した配信を行う。例えば、配信元に近い・遠い、あるいは、上流・下流などといった情報を持ち、これらの情報を用いることで、構造把握を容易に行うことができる。
【００６１】
以下、一部重複するが、さらに、図２（ｂ）に示すネットワークの構成手順の詳細を説明する。
【００６２】
配信用P２Pアプリケーションを起動したPC（パーソナルコンピュータ）またはノードである各ピアは、グループに属し、グループ内の他ピアの情報、すなわち、他のピアとの接続に必要なアドレス情報を、ランダムに持つ。
【００６３】
また、各ピアは、親グループ(配信を受けるグループ)へアクセスするための情報(グループ所属の任意のノードのアドレス、後述する接続ノードのアドレス等)と、子グループ(配信を提供するグループ)の情報を持つ。
【００６４】
グループの構成技術に関しては、様々な技術が考えられるが、例えばここでは、ネットワーク的に近い物をグループ化するものとして説明する。尚、動的にグループを組替える方式も考えられる。
【００６５】
以下、他グループとのやり取り、すなわち、親グループからの配信・受信、および、子グループへの配信・送信について説明する。
【００６６】
ここでは、説明の簡便化のため、このような他グループとのやり取りは、グループ内において限られたノードが行うものとする。すなわち、各グループ間の接続を担当するノードがグループ間接続毎にひとつずつ存在する(これを接続ピアと呼ぶ)ものとして扱う。
【００６７】
グループの構成に際して、各ピアグループにおけるピア数の最大値等の閾値をNと置き、Nを越える場合には、例えば、同数ピアずつ所属する２グループ等としてグループの分割を行う。
【００６８】
この際、閾値Nが小さいほどツリー型、閾値Ｎが大きいほどメッシュ型に近づくことを利用して、制御の容易性(ツリー型に近づける)や、スケーラビリティ(メッシュ型に近づける)にかかわる動作の調整が可能となる。
【００６９】
ノードグループ間でのやり取りは、既存のツリー型配信方式をピア(ノード)単位ではなく、グループ単位に拡張したものであり、配信元サーバに対して、各ピアグループの接続ピアが配信を要求するアクセスを行う。すなわち、配信元サーバに、ＴＣＰ等のコネクションを張ってコンテンツの転送をリクエストする。
【００７０】
配信元となったピアもしくは配信元サーバは、自身のCPUやHDD、回線等の負荷があらかじめ定められた一定の閾値を越えていないか、もしくは、配信を提供する子グループがグループ内ピア数の最大値(閾値N)を越えていないかを確認し、いずれも越えていない場合は、そのままコンテンツを受信する。
【００７１】
もし、このコンテンツの配信が、アドレス変更、ピアの消滅、ネットワーク遮断等の原因で失敗し場合、あるいは、配信元ピア（サーバ）の負荷があらかじめ定められた一定の閾値を越えている、もしくは、配信を提供する子グループがグループ内ピア数の最大値(閾値N)を越えている場合には、配信元ピア（サーバ）から、配信元ピア（サーバ）が属するグループの子グループのピア情報を受け取り、そのピアに対して配信要求アクセスを行う。
【００７２】
以上の処理手順を繰り返すことで、ノードグループ間でのデータの配信を行う。
【００７３】
次に、ノードグループ内でのやり取りについて説明する。
【００７４】
まず、ノードグループの中からランダムに選ばれたノードのみが、親グループからコンテンツを取得する。
【００７５】
各ノードグループ内では、メッシュ型配信となるように各ピアはふるまう。すなわち、当該ノードグループ内の各ノード同士では、前述したメッシュ式での配信を行う。
【００７６】
ノードグループに対して、子ノードグループからのアクセスがあった場合は、ランダムに選ばれたノードが、接続ノードとなって、問い合わせに返答する。すなわち、あるノードグループに対して、その下位にあたる子ノードグループからアクセスがあった場合は、当該ノードグループ内からランダムに選ばれたノードが配信元となる。
【００７７】
以上の処理手順を繰り返すことで、ノードグループ内でのデータの配信を行う。
【００７８】
以上、図１〜図５を用いて説明したように、本例のネットワーク構築システムでは、ネットワーク（オーバーレイネットワーク）を、ツリー型とメッシュ型を混在させて形成すると共に、規模の拡大に応じて柔軟にツリー型とメッシュ型の構成を切り替えることを特徴とする。具体的には、ネットワークを構成しているノード（オーバーレイノード）をグループ化し、グループ内ではメッシュ型、グループ間ではツリー型とする。そして、各ピアグループにおけるピア数の最大値等の閾値を調整することにより、メッシュ型とツリー型の比率を変えて混在化させる。例えば、ピアグループの最大ピア数を１にするとツリー型と同じになり、最大ピア数を無限大にするとメッシュ型と同様になる。
【００７９】
このように、ネットワークを構成しているノードをグループ化し、グループ内ではメッシュ型、グループ間ではツリー型とすることにより、ツリー構造の部分ではユーザ挙動の追跡や品質悪化箇所を発見し、課金や障害を取り除くことが可能となり、全体をメッシュ型で構成した場合と比較して制御性は高くなり、また、メッシュ型で構成されるグループでは、制御可能性は犠牲になるものの、スケーラビリティは維持できるため、全体をツリー型で構成した場合と比較して多数の利用者を収容でき、さらに、ネットワーク規模に応じて、メッシュ型とツリー型の比率を変えて混在化させることができ、障害検知や構造把握が可能なままでの大規模化が可能となり、スケーラビリティと可制御性を両立させたP２P配信基盤を構築することができ、大規模な商用のコンテンツ配信においてもその制御性を損なうことなく高いスケーラビリティを実現することが可能となる。
【００８０】
また、本例では、対象のネットワークの規模に応じてグループ構成を調整・制御することにより、対象のネットワークのスケーラビリティと制御困難性をコントロールすることが可能である。すなわち、メッシュ型とツリー型のトポロジ・グラフにおいては、節点数が同一の場合、メッシュ型の方の次数が高くなる。このため、メッシュ型の方が冗長度、リンク数ともに大きくなる。冗長度はネットワークのスケーラビリティと相関がある指標で、リンク数はネットワーク制御困難性と相関がある指標である。本例では、これらの指標を適切にコントロールすることを目指し、２つのグラフ形態の混合型構造を構成する。これにより、各ピアグループのサイズを調整することで、ネットワークのスケーラビリティと制御困難性をコントロールすることが可能となる。
【００８１】
このようにして構築されたツリー型とメッシュ型混在のネットワークにおけるデータ配信は、以下のようにして行われる。
【００８２】
すなわち、データの配信要求元ノードから当該データの配信元ノードに対して当該データの配信が要求されると、配信元ノードは、自身の処理負荷が予め定められた閾値を越えていないか、もしくは、自配信元ノードにアクセス要求している子グループの数が予め定められた閾値を越えていないかを判定し、いずれも閾値を越えていなければ、配信元ノードから配信要求元ノードに当該データを配信するが、いずれかが閾値を越えていれば、もしくは、配信元ノードから配信要求元ノードへの当該データの配信が失敗すれば、配信元ノードは、自身が所属するグループの子グループに属し当該データを保持するノードを配信要求元ノードに通知し、この通知を受けた配信要求元ノードは、通知されたノードに対して当該データの配信を要求し、通知されたノードから当該データを受け取る。
【００８３】
尚、通知を受けて配信要求したノードも負荷等の問題があれば、先の配信元ノードと同様にして、子グループに属し当該データを保持するノードを配信要求元ノードに通知する。
【００８４】
また、ツリー型で接続された子グループからのデータ配信要求があれば、要求を受けたグループ内の各ノードからランダムに選ばれたノードが、要求されたデータを配信する。
【００８５】
尚、本発明は、図１〜図５を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、他グループとのやり取り、すなわち、親グループからの配信・受信、および、子グループへの配信・送信は、説明の簡便化のため、グループ内において限られたノードが行うものとして説明したが、複数のノードで行うことでも良い。
【００８６】
また、本例では、ツリー型のネットワークの構成においては、子ノードが２つの２分木での構成を示しているが、子ノードを３つ以上としたツリー構造（多分木、Ｎ分木）としても良い。
【００８７】
また、本例では、オーバーレイネットワークの構成を例に説明したが、本発明は、他のＰ２Ｐ型配信を行うネットワークにも適用可能である。
【００８８】
また、本例のコンピュータ構成に関しても、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【符号の説明】
【００８９】
１０〜１２：グループ、１０ａ〜１０ｅ，１１ａ〜１１ｅ，１２ａ〜１２ｅ，１３：ノード、１４：ネットワーク構成システム、１４ａ：グループ分け処理部、１４ｂ：グループ内接続設定処理部、１４ｃ：グループ悪寒接続設定処理部、１４ｄ：条件情報保持部、２１〜２４，２６ａ：ノード、２５〜２８：グループ、３１ａ〜３１ｇ，３２ａ〜３２ｅ：ノード（ピア）、４１：オーバーレイネットワーク、４１ａ〜４１ｃ：オーバーレイノード、４２：ＩＰネットワーク、４２ａ〜４２ｅ：ＩＰルータ。
【図１】
2011055070.tif 000003
【図２】
2011055070.tif 000004
【図３】
2011055070.tif 000005
【図４】
2011055070.tif 000006
【図５】
2011055070.tif 000007