(57)【特許請求の範囲】
【請求項１】
ネットワーク上の複数のノード間の通信により、配信データをリレー転送するデータ配信システムであって、  管理装置を有し、
前記管理装置は、
前記ネットワーク上の複数のノードのそれぞれのデータ送信可能帯域の情報を取得し、保持するノード帯域情報取得部と、
配信すべきコンテンツの帯域を取得し、保持するコンテンツ帯域取得部と、
前記配信すべきコンテンツを複数の帯域に分割する分割比である帯域分割情報を取得し、保持する帯域分割情報取得部と、
前記帯域分割情報取得部に保持される帯域分割情報に基づいて分割される前記配信すべきコンテンツの接続先を決定する接続先決定部を有して構成され、
前記管理装置において、
前記接続先決定部が、
前記帯域分割情報に基づいて前記配信データの転送帯域を分割し、前記分割された転送帯域を単位として前記複数のノードのそれぞれのデータ送信帯域を分割し、
前記分割された転送帯域毎に前記帯域単位が確保できるノードを接続先として選択して前記配信データの配信経路を決定する、
ことを特徴とするデータ配信システム。
【請求項２】
請求項１において、
前記配信データの配信経路を決定する際に、該当単位の対応する帯域よりも広帯域の単位を分割して、前記単位を確保する、
ことを特徴とするデータ配信システム。
【請求項３】
請求項１において、
前記配信データの配信経路を決定する際に、該当単位の対応する帯域よりも挟帯域の単位を結合して、前記単位を確保する、
ことを特徴とするデータ配信システム
【請求項４】
請求項１において、
前記帯域分割情報取得部に与える帯域分割情報としての分割比を等比とすることを特徴とするデータ配信システム。
【請求項５】
請求項１において、
前記単位が確保できる接続先として選択するノードが複数存在するときに、前記複数のノードの選択における優先度を、ネットワーク条件に従って決めることを特徴とするデータ配信システム。
【請求項６】
請求項1において、
前記管理装置は、前記複数のノードとは独立して配置されることを特徴とするデータ配信システム。
【請求項７】
請求項１において、前記管理装置は、前記複数の端末のいずれかに 配置されることを特徴とするデータ配信システム。
【請求項８】
ネットワーク上の複数のノード間の通信により、配信データをリレー転送するデータ配信システムに配置される管理装置であって、  前記ネットワーク上の複数のノードのそれぞれのデータ送信可能帯域の情報を取得し、保持するノード帯域情報取得部と、
配信すべきコンテンツの帯域を取得し、保持するコンテンツ帯域取得部と、
前記配信すべきコンテンツを複数の帯域に分割する分割比である帯域分割情報を取得し、保持する帯域分割情報取得部と、
前記帯域分割情報取得部に保持される帯域分割情報に基づいて分割される前記配信すべきコンテンツの接続先を決定する接続先決定部を有して構成され、
前記管理装置において、
前記接続先決定部が、
前記帯域分割情報に基づいて前記配信データの転送帯域を分割し、前記分割された転送帯域を単位として前記複数のノードのそれぞれのデータ送信帯域を分割し、
前記分割された転送帯域毎に前記単位が確保できるノードを接続先として選択して前記配信データの配信経路を決定する、
ことを特徴とするデータ配信システムに配置される管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ピアツーピア（peer-to-peer：以下適宜Ｐ２Ｐと表記する）によるデータ配信（ストリーミング配信）システム及びこれに適用する管理装置に関する。特に、転送データを複数に分割し、各端末の転送帯域に応じて割付を行う、帯域割付制御技術を用いるデータ配信システムに関する。
【背景技術】
【０００２】
データ配信を行う通信システムの分野において、一つのサーバから複数のクライアントに同時的にデータを配信する、クライアント・サーバ型の通信形態がある。かかる通信形態では、データを受信するクライアント端末数が増加すると、それに比例した負荷がサーバ側に集中的に発生する。
【０００３】
このことから、大規模なデータ配信システムでは、アクセスが集中するサーバやネットワークインフラの増強が必須であり、コスト面において課題があった。
【０００４】
そのような背景のもと、近年、Ｐ２Ｐ技術を応用したデータ配信が注目されている。Ｐ２Ｐ型配信は、データを受信した端末が、受信データを他の端末へ中継(リレー)し、次々にリレー配信することによって実現される。このため、クライアント端末数の増加に対してサーバの負荷増加が緩やかである、もしくは影響が無いという特徴を備えている。
【０００５】
Ｐ２Ｐ型配信は、一般的には物理的なネットワーク接続環境を意識しないデータ配信であって、端末間の論理的なリンクで形成される論理ネットワーク（オーバーレイネットワーク）上のデータ配信とみなすことができる。
【０００６】
一方、Ｐ２Ｐによるデータ配信においては、データを中継する端末（ノード）の転送帯域を如何に有効に活用するかが、重要なポイントとなる。
【０００７】
配信ネットワークシステム内で、データ中継を担う中継端末が多いほど、また中継端末の中継性能（データ転送帯域）の使用効率が高いほど、システム全体としての配信性能の向上が期待できる。
【０００８】
これら、配信ネットワークシステムにおける全端末中の中継端末の割合や、中継端末毎の転送帯域の使用効率は、配信経路の生成方法によって決まってくる。
【０００９】
また、データ配信は、非リアルタイム配信とリアルタイム配信に分類できるが、配信経路の生成方法とその経路上でのデータ配信方法によって、リアルタイム性に向き不向きが生じる。
【００１０】
配信経路は、その形態において様々なバリエーションが考えられるが、通常、ツリー（木構造）や、メッシュ（網目構造）となる。一般に、端末をノード、端末間の通信リンクを辺（エッジ）として、グラフで表現する。
【００１１】
単純に単一のツリーによる配信経路でデータ配信を行う場合、葉となるノード（中継に関与しないノード）が必然的に多くなるため、全体としてノードが保有する帯域の使用効率が悪くなり、また、中継ノード側の負担が増加する。
【００１２】
かかる単一のツリーによる配信経路でデータ配信を行う技術に対して、複数ツリーでデータ配信を行う技術として、非特許文献１、２及び、特許文献１に示される技術が在る。非特許文献１に示される (Split Stream)方式と呼ばれる技術では、複数パスによるデータ配信方式であり、データの帯域Ｂをｋ等分し、ノードは、Ｂ/ｋ毎の配信ツリーのうちの一つのツリーでのみ中継を行ない、他のツリーでは葉となって受信する方式である。
【００１３】
また、非特許文献２に、（Coop Net）方式と呼ばれる従来技術が記載されている。かかる非特許文献２に記載のCoop Net方式 は、ピアツーピアネットワークでコンテンツ配信を行なう際に、上記のSplit Stream方式を利用し、データ帯域を複数に「等分」し、複数の配信ツリーでそれぞれを配信し、ツリーの管理を行なう方式である。
【００１４】
さらに、特許文献１に記載の技術は、各端末の帯域利用効率の最大化と、葉ノードの排除を追求した技術である。
【００１５】
図１に特許文献１に示された(図５)を再掲して説明すると、配信元Ｓにおける配信データを単位データに分割し、各ノードｔ１〜ｔ４へ次々に単位データデータを送信していく。受信した各ノードは受信データを自身以外の全てのノードへ転送し、転送が終わったノードには、配信元Ｓから次のデータが送信される。
【００１６】
この処理を繰り返すことにより、各ノードｔ１〜ｔ４は転送可能な最大速度でデータを転送しつつ、必ず中継役を担うことで葉ノードを排除することに成功している。
【非特許文献１】Split Stream:High-bandwidth Content Distribution in a Cooperative Environment. IPTPS, Feb. 2003, M.Castro, P.Druschel,他 (Microsoft)
【非特許文献２】IEEE International Conference on Network Protocols (ICNP), Atlanta, GA,  SA, November 2003,V.N Padmanabhan 他  (Microsoft)
【特許文献１】特開2006-25408号公報
【発明の開示】
【発明が解決しようとする課題】
【００１７】
前記した通り、特許文献１に記載の発明は、各ノードの転送効率を高め、葉ノードを排除することに注力した技術であった。
【００１８】
一方、ノード数Ｎに対して、配信木がＮ本生成されると、ノードの中継先はＮ−１となるため、実際には複数の配信木の重ね合わせとして、全ノード総当たりの往復リンクが生成され、ここにトラフィックが発生する。ノード数Ｎが大きくなるに従い、ノード間のリンク数（グラフの辺の数）がＮの二乗オーダで急増するという、スケーラビリティ(規模拡大化)の面において課題がある。
【００１９】
また、昨今、インターネットにおけるＰ２Ｐトラフィックの増加が問題となっており、そのような観点からも論理リンク数を減らし、サブネットワーク間のトラフィックを削減することが望ましい。
【００２０】
さらに、上記従来技術は、中継が終わったノードに次のデータを送り込むことで最大性能を引き出す仕組みのため、各リンクにどれだけの通信トラフィックが発生するかを予測することが難しいという課題がある。
【００２１】
そして、前記したようなインターネットにおけるＰ２Ｐトラフィック問題に対応するべく、論理リンク間のトラフィックは予測もしくは制御できることが望ましい。
【００２２】
したがって、上記従来技術に鑑みて、本発明の目的は、システム性能とスケーラビリティおよびトラフィック制御を満足するために、論理リンクにおける転送帯域を予め定めた上で、葉ノード率を抑え、中継ノードの帯域利用効率を高めつつ、配信木の数と各ノードの接続ノード数を、ノード数Ｎに非依存で、かつ十分に小さな値にするように接続経路を生成するデータ配信システムを提供することにある。
【００２３】
また、本発明の目的は、経路生成に際して、柔軟かつ容易に経路が選定できるデータ配信システムを提供することにある。
【００２４】
さらに、本発明は、中継ノードの帯域効率を最大に活用することを目的とする。
【００２５】
さらにまた、本発明は、データ配信において、インターネットトラフィックを抑えることを目的とする。
【００２６】
また、本発明は、上記非特許文献１及び２に示される従来技術との比較において、データ帯域を等分するものではなく、等比分割する方式を提案する。
【課題を解決するための手段】
【００２７】
上記の目的を達成する本発明の第１の側面は、ネットワーク上の複数のノード間の通信により、配信データをリレー転送するデータ配信システムであって、管理装置を有し、前記管理装置は、前記ネットワーク上の複数のノードのそれぞれのデータ送信可能帯域の情報を取得し、保持するノード帯域情報取得部と、配信すべきコンテンツの帯域を取得し、保持するコンテンツ帯域取得部と、前記配信すべきコンテンツを複数の帯域に分割する分割比である帯域分割情報を取得し、保持する帯域分割情報取得部と、前記帯域分割情報取得部に保持される帯域分割情報に基づいて分割される前記配信すべきコンテンツの接続先を決定する接続先決定部を有して構成され、前記管理装置において、前記接続先決定部が、前記帯域分割情報に基づいて前記配信データの転送帯域を分割し、前記分割された転送帯域を単位として前記複数のノードのそれぞれのデータ送信帯域を分割し、前記分割された転送帯域毎に前記単位が確保できるノードを接続先として選択して前記配信データの配信経路を決定することを特徴とする。
【００２８】
また、上記の目的を達成する本発明の第２の側面は、データ配信システムに配置される管理装置においてデータ配信の接続先を決定するプログラムであって、前記管理装置を、前記ネットワーク上の複数のノードのそれぞれのデータ送信可能帯域の情報を取得し、保持するノード帯域情報取得手段と、配信すべきコンテンツの帯域を取得し、保持するコンテンツ帯域取得部と、前記配信すべきコンテンツを複数の帯域に分割する分割比である帯域分割情報を取得し、保持する帯域分割情報取得手段と、前記帯域分割情報取得部に保持される帯域分割情報に基づいて分割される前記配信すべきコンテンツの接続先を決定する接続先決定手段として機能させ、さらに、前記接続先決定手段の機能として、
前記帯域分割情報に基づいて前記配信データの転送帯域を分割し、前記分割された転送帯域を単位とした単位で前記複数のノードのそれぞれのデータ送信帯域を分割し、前記分割された転送帯域毎に前記単位が確保できるノードを接続先として選択して前記配信データの配信経路を決定させることを特徴とする。
【発明を実施するための最良の形態】
【００２９】
以下に本発明の実施例を図面に従い説明する。かかる実施例説明は、本発明の理解のためのものであり、本発明の保護の範囲がこれに制限されるものではない。
【００３０】
図２は、本発明に従うネットワークを構成する複数のノード間の経路を設定するデータ配信システムの概略構成を示す図である。
【００３１】
かかるデータ配信システムは、複数のノードとは別個に、ネットワーク全体を管理する管理装置として位置づけられる装置である。
【００３２】
あるいは、配信データの送信元となる一のノードにかかる管理装置を配置する構成とすることも可能である。
【００３３】
さらに、次に説明する管理装置の各構成部において実行される機能をプログラムによって、実現することも可能である。
【００３４】
かかるデータ配信システムは、処理ユニット１を中心機能部として有する。処理ユニット１と、各ノードのデータ転送性能を取得する各ノードのノード帯域取得部３、配信データ（コンテンツ）の転送レート（配信帯域）を取得するコンテンツ帯域取得部４、及び配信データを分割するための情報を取得する帯域分割情報取得部５とがバス２を通して接続されている。
【００３５】
ノード帯域取得部３における各ノードの帯域と、帯域分割情報取得部５における帯域分割情報、およびコンテンツ帯域取得部４における配信データの転送帯域は、通信システムを構築する際に管理装置にデフォルトとして設定される。
【００３６】
処理ユニット１には、これら各部の情報を基に端末間の接続候補を選出する接続先決定部１０を備える。
【００３７】
かかる接続先決定部１０は、ＣＰＵ等の制御手段を含み、プログラムの実行により、以下に説明する処理を実行する機能手段として動作する。
【００３８】
接続先決定部１０は、帯域分割情報取得部５より取得した帯域分割情報に基づいて、コンテンツ帯域取得部４により取得された配信データの転送帯域を分割する(ステップＳ１)。
【００３９】
さらに、接続先決定部１０は、ノード帯域取得部３からノード毎の転送帯域情報を得て、ノードリスト１１を保持している。
【００４０】
新たに、処理ノード対象の情報１００が加わり、パスの再設定が行われる。
【００４１】
処理対象ノード１００に対して、既存のリストから接続先リストを生成し、接続先決定後（もしくは接続後）に、その新規ノードの情報をノードリスト１１に追加更新して終了する。
【００４２】
そして、上記の分割した各帯域幅を単位とした次数でノードリスト１１に登録された端末（ノード）の送信帯域を分割する（ステップＳ２）。
【００４３】
そして、上記分割転送帯域毎に、ノードリスト１１を基に対応する単位（次数）が確保できる端末を接続相手として選択する（ステップＳ３）。
【００４４】
これを分割転送帯域数だけ繰り返す（ステップＳ４）ことで、全ての配信木に新たなノードを接続し、接続ノード情報として、パス毎の接続ノード情報１１０を出力する。
【００４５】
ここで、次数が確保できるノードが無い場合には、より広帯域の次数を狭帯域の次数に分割し、次数を確保する。もしくは、次数が確保できるノードが無い場合に、より狭帯域の次数を統合し、次数を確保する（ステップＳ５）。
【００４６】
さらに、前記処理において、次数の確保対象が複数存在する場合は、物理的なネットワーク環境への影響を抑えるために、物理ネットワーク距離が近いノードを候補とする。  ここで、図１に示した特許文献１に記載の発明を説明する図と比較すると、特許文献１に記載の発明では経路生成において、全ノードを平等に扱って総当たりの経路を生成し、そこに流すデータ量を各ノードの能力に応じて動的配分することによって、結果的にリアルタイム配信を実現するものであった。
【００４７】
このため、ノード数の増加に伴い、二乗オーダでノード間のリンク総数が激増し、かつ、各リンクにどれだけのトラフィックが発生するかが予測不可能であった。
【００４８】
これに対し、上記のデータ配信システムの実施例構成及び、処理手順では、ノード帯域取得部３、コンテンツ帯域取得部４及び帯域分割情報取得部５を備え、これら情報を元に、各ノードの帯域を把握し、コンテンツ帯域を分割した上でその分割帯域に応じた次数をノード毎に決定し、これを用いて接続相手を決定する。これにより、各ノードの帯域利用効率を高めている。
【００４９】
また、経路木の数はノード数Ｎに非依存なコンテンツ帯域の分割数となるため、十分に少なく、また、各ノードの接続相手の数も、その保有次数で決まり、十分に小さいことから、論理リンク数をＮに非依存で削減できる。
【００５０】
また、後に示す設定例のように、コンテンツの分割比を等比とする場合は、ノードの保有次数の分割と統合が可能になるため、より柔軟な割付が可能となり、ノードの帯域利用効率を高めることができる。
【００５１】
さらに、接続候補が複数存在する場合に物理ネットワーク情報を基に優先度を決めるため、接続するノード同士がネットワーク的に近い関係を保ちやすく、サブネット間ネットワークトラフィックを削減することが可能となる。また、帯域を決めた経路を計画的に配線しているので、ノード間のトラフィックを把握することが可能となる。
【００５２】
つぎに、上記図２に示したデータ配信システムの実施例構成に基づき処理ユニット１内の接続先決定部１０により実行される具体的な設定例を以下に説明する。
【００５３】
以下に説明する設定例では、共通に端末を円のノード、端末間の接続リンクを矢印で表示する。矢印の向きはデータの流れる方向である。円の中の数値はノードの保有帯域であり、矢印に付加される数値はリンクの帯域をそれぞれ示し、リンクを生成する毎に、そのリンクに相当する帯域をノードの保有帯域から消費する。
【００５４】
図３に示す第1のネットワーク経路設定例では、ネットワークは５つのノード（Ａ，Ｂ，Ｃ，Ｄ，Ｅ）群で構成される。
【００５５】
そして、ネットワークを構成する５つのノード群に対して、ノードＡからデータを配信する場合の経路生成を考える。
【００５６】
コンテンツ帯域取得部４が取得した送信対象のコンテンツの帯域が１０Mbpsであるとし、帯域分割情報取得部５が取得した分割情報が、１：２：３：４の関係にある４分割であるとする。
【００５７】
このとき、１０Mbpsをかかる帯域分割情報に従い、１Mbps,２Mbps,３Mbps,４Mbpsの４つに分割する。
【００５８】
一方、ノード帯域情報取得部３によって獲得された各ノードの初期保有転送帯域情報が、図３に示すように、ノードＡが２０Mbps、ノードＢが１０Mbps、ノードＣが３Mbps、ノードＤが５Mbps、ノードＥが２Mbpsであるとする。各ノードの帯域を、分割した４つの帯域を係数とした多項式（式１）
X=4 X3 + 3X2 +2X1+ 1X0 ・・・(式１)  の形式に分解する。
【００５９】
ここで、 Xn は、各帯域における接続可能な次数であり、０以上の正の正数である。例えばノードＡの２０Mbpsは、（式２）のように係数の高い方から割り当てて分解する。
【００６０】
20＝4x5 + 3x0 + 2x0 + 1x0 ・・・（式２）
他の各ノードについても同様に分解し、接続先決定部１０のノードリスト１１の一部として保持される表形式で表現された状態が図４に示す例である。
【００６１】
本設定例では、コンテンツ帯域を分割した各データ帯域のそれぞれに経路を生成し、各ノードを各経路に漏れなく重複無く接続する。これにより、各ノードが配信データを過不足なく受信できる。
【００６２】
まず、４Mbpsのデータを配信する経路生成を説明する。図４の表から、４Mbpsの次数を保持しているノードは、配信元のノードＡの次数５と、ノードＢの次数２、ノードＤの次数１、合計８次数となることがわかる。
【００６３】
一方、このノード群でデータを受信するのはノードＢ,Ｃ,Ｄ,Ｅの４つなので、次数８の中から任意の４つを選択する。ここで、可能な限り配信元以外のノード群の送信性能を活用したいため、ノードＡ以外のノードから次数を確保することを優先する。その結果、ノードＡから次数１、ノードＢから２、ノードＤから１の合計４次数を確保することとなる。
【００６４】
この確保した次数を用いて、まず送信元からの次数１を、確保済次数を保有しているノードのうち、次数の多いノードＢに接続するリンクを生成する。続いてノードＢの次数２から次数１を保持するノードＤへ接続する。これにより、４Mbpsのデータを配信に対して、確保済み次数を保有しているノードが無くなくなるので、次数を保有しないノード、ここではノードＣとＥを葉ノードとしてノードＢからノードＣを接続するリンク、及びノードＤからノードＥを接続するリンクを形成する。
【００６５】
以上により接続された経路が図５となる。
【００６６】
ここまでの経路生成によって、４Mbpsの帯域についてノードＡは保有次数１、ノードＢは保有次数２、ノードＤは保有次数１を消費したことになる。このため、保有次数は図６の表のように更新される。すなわち、ノードＢ，Ｄにおける帯域４Mbpsについての次数は無くなり、ノードＡについて、４Mbpsの次数は、４となる。
【００６７】
以上の経路生成を各帯域について繰り返していくが、図６に示すように更新された状態では続く３Mbpsの次数がノードＣの１しか確保できていない。
【００６８】
かかる場合、より広帯域の次数すなわち、ノードＡが４Mbpsを４次数分保持しているので、これを分解して、３Mbpsで計４つ以上の次数が確保でき、図７に示す表の様に変形する。
【００６９】
この結果、図８に示すように、３Mbpsの経路が完成し、残りの保有次数は再び更新され、図９に示すようになる。
【００７０】
次に、２Mbpsの次数については、図９の更新された表では、ノードＢとＥにおいてそれぞれ１しか確保できていない。したがって、上記と同様に、ノードＡの保持する４Mbpsの１つの次数分を２つの２Mbpsの次数に分解して、図１０のように更新する。
【００７１】
かかる図１０の更新された保有次数に基づき、２Mbpsの経路が完成し、図１１のように経路が形成される。
【００７２】
図１２は、かかる２Mbpsの経路の形成後の更新された保有次数の表である。
【００７３】
次いで、１Mbpsの経路の設定の際、図１２に示すように、ノードＤのみについて、１Mbpsの次数が１確保されている状態である。したがって、ノードＡの３Mbpsの1つの次数を分解して図１３に示すように変更する。
【００７４】
したがって、ノードＡについて３つの次数、ノードＤについて、１つの次数が確保される。これに基づき、１Mbpsの経路を設定すると、図１４のように形成される。
【００７５】
この結果、図１５に示すように、全てのノードについて、保有次数を消化することができる。
【００７６】
上記のとおり４Mbps, ３Mbps, ２Mbps, １Mbpsについて、設定した全帯域の経路を重ねて、図１６に示すように全ての経路が生成される。
【００７７】
ここで、上記の第１の設定例では、コンテンツ帯域が１０Mbps、ノードの転送性能が２〜２０Mbpsであった。これに対し、ノード性能の差が大きくなると、より効率的なコンテンツ分割を行なった方が有利となる。次にかかる場合のより効率的なコンテンツ分割を行なう設定例を示す。
【００７８】
すなわち、前記帯域の分割および統合を効率よく行うために、帯域の分割比を等比とすることが有利である。
【００７９】
帯域の分割比が等比、例えば、１：２：４：８・・・とすることにより、次数の分割時や、次数の統合時に余りが発生せずに、効率的な割付が可能となる。
【００８０】
分割数は高々数本程度とし、ノード数Ｎに非依存で決定し、この分割数が、本発明の経路本数となる。分割比としては、等分よりも、比を変える事により後述の効果が得られる。
【００８１】
以下に第２の設定例として、かかる帯域の分割比を等比とする場合の例について説明する。
【００８２】
図１７，図１８に示す第２の設定例においても、端末を円のノード、端末間の接続リンクを矢印で表示する。矢印の向きはデータの流れる方向である。円の中の数値はノードの保有帯域、矢印に付加される数値はリンクの帯域をそれぞれ示し、リンクを生成する毎に、そのリンクに相当する帯域をノードの保有帯域から消費する。
【００８３】
図１７に示す第２の設定例において、第１の設定例と同様にネットワークは５つのノード（Ａ，Ｂ，Ｃ，Ｄ，Ｅ）群で構成される、
ノード群に対して、ノードＡからデータを配信する場合の経路生成を考える。コンテンツ帯域取得部４が取得した送信対象のコンテンツの帯域が１５Mbpsであるとし、帯域分割情報取得部５が取得した分割情報が、１：２：４：８（＝２０：２１：２２：２３）の等比の関係にある４分割であるとする。
【００８４】
このとき、分割情報に従い、接続先決定部１０は、１５Mbpsのコンテンツ帯域を１Mbps,２Mbps,４Mbps,８Mbpsの４つに分割する。
【００８５】
一方、端末帯域取得部３によって獲得された各ノードの初期保有の転送帯域が、図１７に示されるように、ノードＡが３０Mbps、ノードＢが１６Mbps、ノードＣが２Mbps、ノードＤが１Mbps、ノードＥが１１Mbpsであるとする。
【００８６】
各ノードの帯域を、分割した４つの帯域を係数とした下記の多項式（式３）
X=8X3 +4X2 +2X1 + 1X0・・・（式３）
の形式に分解する。ここでXnは、各帯域における、接続可能な次数であり、０以上の正の正数である。
【００８７】
例えば、ノードＡの保有帯域３０Mbpsは、下記の多項式（式４）のように分解できる。
【００８８】
30＝8x3 + 4x1 + 2x1 + 1x0 ・・・（式４）
図１８は、図１７の例を他の各ノードについて同様に分解し、表形式で表したものである。
【００８９】
本設定例でも、分割した帯域それぞれに経路を生成し、各ノードを各経路に漏れなく重複無く接続することにより、各ノードが配信データを過不足なく受信できる。
【００９０】
まず、８Mbpsのデータを配信する経路生成を説明する。図１８の表から、８Mbpsの次数（即ち、出力可能な経路数）を保持しているノードは、配信元のノードＡの次数３と、ノードＢの次数２、ノードＥの次数１の合計次数６となることがわかる。
【００９１】
一方、このノード群でデータを受信するのはＢ,Ｃ,Ｄ,Ｅの４つであるので、次数６の中から任意の４つを選択する。
【００９２】
ここで、可能な限り配信元以外のノード群の送信性能を活用したいため、ノードＡ以外のノードから次数を優先して確保する。その結果、ノードＡから次数１、ノードＢから次数２、ノードＥから次数１の合計４次数を確保することになる。
【００９３】
この確保した次数を用いて、まず送信元ノードＡから、確保済次数を保有しているノード、即ち、ノードＢとＥに優先して接続リンクを生成する。ノードＢとＥのように確保済み次数を保有するノードが複数ある場合は、次数を多く保持しているノードであるノードＢを優先する。
【００９４】
確保済み次数を保有しているノードが無くなったら、最後に次数を保有しないノード、ここではノードＣとＤを葉ノードとして接続する。以上により接続された経路が図１９となる。
【００９５】
ここまでの経路生成によって、ノードＡ，Ｂ，Ｅは８Mbpsの帯域についての保有次数を消費したことになる。すなわち、ノードＡは次数１、ノードＢは次数２，ノードＥは次数１を消費する。
【００９６】
このために保有次数は、図２０の表のように更新される。すなわち、ノードＢ，Ｅにおける８Mbpsの次数はなくなり、ノードＡについては、８Mbpsの次数は２となる。
【００９７】
以上の経路生成を各帯域について繰り返していくことで、全ての経路を生成する。
【００９８】
例えば、続く４Mbpsの経路生成も、８Mbpsの場合と同様であり、図２０の表に示す保有次数から４Mbpsの帯域に相当する次数を４つのノードに送るために４つ確保する。ところが図２０に示されるように、４Mbpsの帯域は、ノードＡの保有する次数１しか、確保できないケースが起こりうる。
【００９９】
このように次数が目標数を確保できない場合は、より広帯域の次数、ここではノードＡの保有する８Mbpsの帯域の次数を分割する。８Mbpsの次数を２つ、分割すれば、４Mbpsの次数４が確保できるため、合計でノードＡが４Mbpsの帯域について次数を５つ保有することになり、ここから目標の次数４を確保する。
【０１００】
この結果、図２１に示すように、４Mbpsの経路が完成し、残りの保有次数は再び更新される。かかる処理を２Mbps,１Mbpsについても繰り返す。
【０１０１】
最終的に、図２２のように次数を無駄なく活用し、図２３のような経路が完成する。図２３は、帯域毎に生成した経路を重ね合わせて形成される完成された経路であり、実際のリアルタイムデータは配信時には、このような複雑なデータ転送が行なわれることになる。
【０１０２】
転送能力が様々なノードが混在するノード群において、本発明によって、各ノードの転送能力を無駄無く活用した経路が生成できることが理解できる。
【０１０３】
なお、上記説明においては、ノードＡ，Ｂ，Ｃ，Ｄ，Ｅのノード群に対し、全てのノードの接続リンクを同時に生成していく例としたが、１ノードずつ生成することも可能である。
【０１０４】
つぎに、既に経路が生成されているネットワークに、新たにノードを追加する場合を説明する。
【０１０５】
処理対象ノード１００に対して、既存のリストから接続先リストを生成し、接続先決定後（もしくは接続後）に、その新規ノードの情報をノードリスト１１に追加更新して終了する。
【０１０６】
図２４は、既に経路設定されているノード群の一部を切り出した例を示す。
ノードＦ,Ｇ,Ｈ,Ｉは既に経路が確定しており、各帯域の経路で接続を完了している。
【０１０７】
この状態にノードＪを新たに追加する場合を説明する。ノードＪは、１,２,４Mbpsの各帯域ではノード群の何れかのノードから次数を確保することができる が、８Mbpsの帯域の次数が、いずれにも余っていないケースを想定している。このような状況は、ノードの追加、削除を繰り返すと起こりやすい。
【０１０８】
ここでノードＦに注目すると、保有帯域を過去に８Mbpsの次数を分割し、４Mbpsの２つの次数に分割して、それぞれノードＨとＩへ分配していることが判る。
【０１０９】
したがって、これらの統合を試みる。統合前に、４Mbpsの次数が他のノードから確保できないか、最新の表を検索し、ノードＧとＨが保有する次数１によって代替が可能であると判定できる。
【０１１０】
代替可能の場合、まず、分割されている４Mbpsの次数を２つ、ノードＦに返却し、返却したノードＨとＩは、ノードＧとＨの保有する４Mbpsの次数から経路を生成する。一方、ノードＦにおいては、返却された４Mbpsの次数２つを統合して８Mbpsとし、続いて、ノードＪに対する経路生成に再利用する。
【０１１１】
図２５は、このようにノード追加後に再設定された状態を示す図である。
【０１１２】
図２５に示されるように、帯域間の次数の分割と統合については、コンテンツ帯域の分割比を等比にすることによって、端数を生じることなく経路生成の柔軟性と効率を向上できる。
【０１１３】
ここで、確保したい対象帯域の次数を保有するノードが複数存在する場合は、端末帯域取得部３からネットワーク情報として、ノードの属するサブネットワークのゲートウェイ、サブネットワークのアドレスなどを収集し、これらが一致する端末を優先選択する。
【０１１４】
(付記１)
ネットワーク上の複数のノード間の通信により、配信データをリレー転送するデータ配信システムであって、
管理装置を有し、
前記管理装置は、
前記ネットワーク上の複数のノードのそれぞれのデータ送信可能帯域の情報を取得し、保持するノード帯域情報取得部と、
配信すべきコンテンツの帯域を取得し、保持するコンテンツ帯域取得部と、
前記配信すべきコンテンツを複数の帯域に分割する分割比である帯域分割情報を取得し、保持する帯域分割情報取得部と、
前記帯域分割情報取得部に保持される帯域分割情報に基づいて分割される前記配信すべきコンテンツの接続先を決定する接続先決定部を有して構成され、
前記管理装置において、
前記接続先決定部が、
前記帯域分割情報に基づいて前記配信データの転送帯域を分割し、前記分割された転送帯域を単位として前記複数のノードのそれぞれのデータ送信帯域を分割し、
前記分割された転送帯域毎に前記帯域単位が確保できるノードを接続先として選択して前記配信データの配信経路を決定する、
ことを特徴とするデータ配信システム。
【０１１５】
(付記２)
付記１において、
前記配信データの配信経路を決定する際に、該当単位の対応する帯域よりも広帯域の単位を分割して、前記単位を確保する、
ことを特徴とするデータ配信システム。
【０１１６】
(付記３)
付記１において、
前記配信データの配信経路を決定する際に、該当単位の対応する帯域よりも挟帯域の単位を結合して、前記単位を確保する、
ことを特徴とするデータ配信システム。
【０１１７】
(付記４)
付記１において、
前記帯域分割情報取得部に与える帯域分割情報としての分割比を等比とすることを特徴とするデータ配信システム。
【０１１８】
(付記５)
付記１において、
前記単位が確保できる接続先として選択するノードが複数存在するときに、前記複数のノードの選択における優先度を、ネットワーク条件に従って決めることを特徴とするデータ配信システム。
【０１１９】
(付記６)
付記1において、
前記管理装置は、前記複数のノードとは独立して配置されることを特徴とするデータ配信システム。
【０１２０】
(付記７)
付記１において、前記管理装置は、前記複数の端末のいずれかに 配置されることを特徴とするデータ配信システム。
【０１２１】
(付記８)
ネットワーク上の複数のノード間の通信により、配信データをリレー転送するデータ配信システムに配置される管理装置であって、
前記ネットワーク上の複数のノードのそれぞれのデータ送信可能帯域の情報を取得し、保持するノード帯域情報取得部と、
配信すべきコンテンツの帯域を取得し、保持するコンテンツ帯域取得部と、
前記配信すべきコンテンツを複数の帯域に分割する分割比である帯域分割情報を取得し、保持する帯域分割情報取得部と、
前記帯域分割情報取得部に保持される帯域分割情報に基づいて分割される前記配信すべきコンテンツの接続先を決定する接続先決定部を有して構成され、
前記管理装置において、
前記接続先決定部が、
前記帯域分割情報に基づいて前記配信データの転送帯域を分割し、前記分割された転送帯域を単位として前記複数のノードのそれぞれのデータ送信帯域を分割し、
前記分割された転送帯域毎に前記単位が確保できるノードを接続先として選択して前記配信データの配信経路を決定する、
ことを特徴とするデータ配信システムに配置される管理装置。
【０１２２】
(付記９)
付記８において、
前記配信データの配信経路を決定する際に、該当単位の対応する帯域よりも広帯域の単位を分割して、前記単位を確保する、
ことを特徴とするデータ配信システムに配置される管理装置。
【０１２３】
(付記１０)
付記８において、
前記配信データの配信経路を決定する際に、該当単位の対応する帯域よりも挟帯域の単位を結合して、前記単位を確保する、
ことを特徴とするデータ配信システムに配置される管理装置。
【０１２４】
(付記１１)
付記８において、
前記帯域分割情報取得部に与える帯域分割情報としての分割比を等比とすることを特徴とするデータ配信システムに配置される管理装置。
【０１２５】
(付記１２)
付記８において、
前記単位が確保できる接続先として選択するノードが複数存在するときに、前記複数のノードの選択における優先度を、ネットワーク条件に従って決めることを特徴とするデータ配信システムに配置される管理装置。
【０１２６】
(付記１３)
付記８において、
前記管理装置は、前記複数のノードとは独立して配置されることを特徴とするデータ配信システムに配置される管理装置。
【０１２７】
(付記１４)
付記８において、
前記管理装置は、前記配信データの配信元となるノードに配置されることを特徴とするデータ配信システムに配置される管理装置。
【０１２８】
(付記１５)
データ配信システムに配置される管理装置においてデータ配信の接続先を決定するプログラムであって、
前記管理装置を、
前記ネットワーク上の複数のノードのそれぞれのデータ送信可能帯域の情報を取得し、保持するノード帯域情報取得手段と、
配信すべきコンテンツの帯域を取得し、保持するコンテンツ帯域取得部と、
前記配信すべきコンテンツを複数の帯域に分割する分割比である帯域分割情報を取得し、保持する帯域分割情報取得手段と、
前記帯域分割情報取得部に保持される帯域分割情報に基づいて分割される前記配信すべきコンテンツの接続先を決定する接続先決定手段として機能させ、
さらに、前記接続先決定手段の機能として、
前記帯域分割情報に基づいて前記配信データの転送帯域を分割し、前記分割された転送帯域を単位として前記複数のノードのそれぞれのデータ送信帯域を分割し、
前記分割された転送帯域毎に前記単位が確保できるノードを接続先として選択して前記配信データの配信経路を決定させる、
ことを特徴とするプログラム。
【産業上の利用可能性】
【０１２９】
上記に説明したように、本発明により、論理リンク数をノード数Ｎに非依存で削減できる。また、コンテンツの分割比を等比とする場合は、より柔軟な割付が可能となり、ノードの帯域利用効率を高めることができる。
【０１３０】
さらに、接続するノード同士がネットワーク的に近い関係を保ちやすく、サブネット間ネットワークトラフィックを削減することが可能となる。また、帯域を決めた経路を計画的に配線しているので、ノード間のトラフィックを把握することが可能となる等の効果を有する。よって、本発明の産業上寄与するところ大である。
【図面の簡単な説明】
【０１３１】
【図１】特許文献１に記載の発明を説明する図である。
【図２】本発明に従う管理装置の 概略構成を示す図である。
【図３】第１のネットワーク経路設定例を示す図である。
【図４】第１の設定例において、接続先決定部のノードリストの一部として保持される表形式で表現された状態を示す例である。
【図５】第１の設定例において、４Mbpsの形成された経路を示す図である。
【図６】図５の経路を形成した状態のノードの保持単位(次数)を示す図である。
【図７】図６のノードの保持次数を分解更新した図である。
【図８】第１の設定例において、３Mbpsの形成された経路を示す図である。
【図９】図８の経路を形成した状態のノードの保持次数を示す図である。
【図１０】図９のノードの保持次数を分解更新した図である。
【図１１】第１の設定例において、２Mbpsの形成された経路を示す図である。
【図１２】図１１の経路を形成した状態のノードの保持次数を示す図である。
【図１３】図１２のノードの保持次数を分解更新した図である。
【図１４】第１の設定例において、１Mbpsの形成された経路を示す図である。
【図１５】図１４の経路を形成した状態のノードの保持次数を示す図である。
【図１６】第１の設定例において経路設定が完了した状態の次数統合例である。
【図１７】第２のネットワーク経路設定例を示す図である。
【図１８】第２の設定例において、接続先決定部のノードリストの一部として保持される表形式で表現された状態を示す例である。
【図１９】第２の設定例において、８Mbpsの形成された経路を示す図である。
【図２０】図１９の経路を形成した状態のノードの保持次数を示す図である。
【図２１】第２の設定例において、４Mbpsの形成された経路を示す図である。
【図２２】図２１の経路を形成した状態のノードの保持次数を示す図である。
【図２３】第２の設定例において経路設定が完了した状態の次数統合例である。
【図２４】既に経路設定されているノード群の一部を切り出した例を示す図である。
【図２５】ノード追加後に再設定された状態を示す図である。
【符号の説明】
【０１３２】
１  処理ユニット
２  バス３  ノード帯域取得部
４  コンテンツ帯域取得部
５  帯域分割情報取得部
１０  接続先決定部
１１  ノードリスト
１００  処理ノード対象の情報
１１０  接続ノード情報
【図１】
0004864868.tif 000002
【図２】
0004864868.tif 000003
【図３】
0004864868.tif 000004
【図４】
0004864868.tif 000005
【図５】
0004864868.tif 000006
【図６】
0004864868.tif 000007
【図７】
0004864868.tif 000008
【図８】
0004864868.tif 000009
【図９】
0004864868.tif 000010
【図１０】
0004864868.tif 000011
【図１１】
0004864868.tif 000012
【図１２】
0004864868.tif 000013
【図１３】
0004864868.tif 000014
【図１４】
0004864868.tif 000015
【図１５】
0004864868.tif 000016
【図１６】
0004864868.tif 000017
【図１７】
0004864868.tif 000018
【図１８】
0004864868.tif 000019
【図１９】
0004864868.tif 000020
【図２０】
0004864868.tif 000021
【図２１】
0004864868.tif 000022
【図２２】
0004864868.tif 000023
【図２３】
0004864868.tif 000024
【図２４】
0004864868.tif 000025
【図２５】
0004864868.tif 000026