データ並列配信方法とシステムおよびプログラム
【課題】ＨＤＴＶやＵＨＤＶ等の超高画質の動画ストリーミングのネットワーク配信サービスの実現を可能とする。
【解決手段】データ並列配信方法において、ネットワークトポロジ設計装置１０１によりネットワークを構成する各ノードの接続関係を示すトポロジ情報を生成し（ステップＳ１００１）、サーバ配置設計装置１０２により、このトポロジ情報を参照して各ノード間の平均ホップ長を算出し、算出した平均ホップ長が小さいノードを優先して、データを並列配信するサーバ機能を設置し（ステップＳ１００２）、データの配信要求があれば、サーバ選択装置１０４により、ホップ長の最も短い最近接のサーバノードと共に、この最近接サーバのホップ数に予め定められたホップ数を加えたホップ長以内のサーバノードも加えて選択する（ステップＳ１００３）。
【解決手段】データ並列配信方法において、ネットワークトポロジ設計装置１０１によりネットワークを構成する各ノードの接続関係を示すトポロジ情報を生成し（ステップＳ１００１）、サーバ配置設計装置１０２により、このトポロジ情報を参照して各ノード間の平均ホップ長を算出し、算出した平均ホップ長が小さいノードを優先して、データを並列配信するサーバ機能を設置し（ステップＳ１００２）、データの配信要求があれば、サーバ選択装置１０４により、ホップ長の最も短い最近接のサーバノードと共に、この最近接サーバのホップ数に予め定められたホップ数を加えたホップ長以内のサーバノードも加えて選択する（ステップＳ１００３）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを介して動画ストリーミング等のデータを配信する技術に係り、特に、一つの配信要求に対して、要求されたデータが保存されている複数のサーバから、当該データを並列にダウンロードするデータ並列配信形態において、平均リンク負荷の増加を抑えながらリンク負荷の偏りを効果的に低減するのに好適な技術に関するものである。
【背景技術】
【０００２】
近年、Ｙｏｕｔｕｂｅ等の動画ストリーミングサービスをインターネット上で利用するユーザ数の数が急増している。高品質な動画ストリーミング配信に対する要求は強く、近い将来、約２５Ｍｂｐｓのビットレートを有するＨＤＴＶ（ｈｉｇｈ ｄｅｆｉｎｉｔｉｏｎ ＴＶ）の視聴がインターネット上でも可能になると思われる。
【０００３】
さらに、ＮＨＫによって、より品質を向上させたＵＨＤＶ（Ｕｌｔｒａ Ｈｉｇｈ Ｄｅｆｉｎｉｔｉｏｎ Ｖｉｄｅｏ）が提案されている。このＵＨＤＶの画像の非圧縮時のビットレートは２４Ｇｂｐｓであり、圧縮後も１８０から６００Ｍｂｐｓの高いレートを有する。
【０００４】
このようなＨＤＴＶやＵＨＤＶの高い画像品質での動画ストリーミングサービスは、インターネットにおける重要なサービスの一つになると思われるが、これらのサービスによって生成されるトラヒックフローの伝送レートは非常に高く、サーバやリンクの輻輳を招く要因となることが予想される。そのためこれらサービスの提供に際しては、サーバやリンクの負荷を分散させることを検討する必要がある。
【０００５】
サーバの負荷分散を図る効率的な技術として、例えば非特許文献１等に記載のＣＤＮ（Ｃｏｎｔｅｎｔｓ Ｄｅｌｉｖｅｒｙ Ｎｅｔｗｏｒｋ）が広く知られている。このＣＤＮは、ネットワーク上に複数のサーバを用意し、ユーザの各配信要求に対して１つのサーバを選択する。その結果、複数のサーバ間で負荷が分散される。
【０００６】
しかし、このＣＤＮは、各配信要求に対して常に１つのサーバのみを選択するため、ＨＤＴＶやＵＨＤＶのストリーミング配信によって生成されるフローがネットワークに与える影響を緩和することはできない。
【０００７】
これらフローの転送レートを抑えるためには、１人のユーザに対する１本のストリーミングセッションに対して、複数のサーバを用いる必要がある。例えば、２つのサーバを１本の配信セッションに用いることにより、このセッションによって生成される各フローの転送レートを半分に抑えることができる。
【０００８】
また、ＨＤＴＶやＵＨＤＶの動画ストリーミングサービスによって生じる高レートフローのネットワークに与える影響を、並列配信によって低減させることが可能となる。
【０００９】
このような並列配信技術は、例えば、Ｐ２Ｐファイル共有サービスとして有名なＢｉｔＴｏｒｒｅｎｔにおいても用いている。
【００１０】
しかし、このＢｉｔＴｏｒｒｅｎｔでは、各ユーザは、他のユーザやオリジナルサーバからデータをダウンロードする間、他のユーザにデータセグメントをアップロードする必要がある。そのため、ＢｉｔＴｏｒｒｅｎｔの性能は、ユーザの行動や上り方向のアクセス回線レートに大きく依存する。
【００１１】
また、配信中のユーザの数が増加するほど、コンテンツを提供するサーバが増加することになるため、データをダウンロードするスループットは、ユーザ数の増加に伴い増加する。
【００１２】
ＨＤＴＶやＵＨＤＶの動画配信の転送ビットレートは極めて大きいので、大容量の上りアクセスリンクを有する多数のユーザが、これら超高画質の配信サービスを利用することを期待することは困難である。
【００１３】
そのため、ＢｉｔＴｏｒｒｅｎｔ等のＰ２Ｐファイル共有システム上で、ＨＤＴＶやＵＨＤＶの動画ストリーミング配信を提供することは困難である。
【００１４】
これらサービスのフローがネットワークに与える影響を緩和するためには、ＣＤＮ事業者、ＩＳＰ（Ｉｎｔｅｒｎｅｔ Ｓｅｒｖｉｃｅ Ｐｒｏｖｉｄｅｒ）、ネットワークキャリアなどが運用する複数のサーバから並列配信を行う必要がある。
【００１５】
【非特許文献１】Ａ．Ｓｕ,Ｄ．Ｃｈｏｆｆｎｅｓ,Ａ．Ｋｕｚｍａｎｏｖｉｃ, ａｎｄ Ｆ．Ｂｕｓｔａｍａｎｔｅ,“Ｄｒａｆｔｉｎｇ Ｂｅｈｉｎｄ Ａｋａｍａｉ （Ｔｒａｖｅｌｏｃｉｔｙ−Ｂａｓｅｄ Ｄｅｔｏｕｒｉｎｇ）,” ＡＣＭ ＳＩＧＣＯＭＭ ２００６．
【発明の開示】
【発明が解決しようとする課題】
【００１６】
解決しようとする問題点は、従来の技術では、複数のサーバを用いたデータの並列配信を効率的に行うことができない点である。
【００１７】
本発明の目的は、これら従来技術の課題を解決し、ＨＤＴＶやＵＨＤＶ等の超高画質の動画ストリーミングのネットワーク配信サービスの実現を可能とすることである。
【課題を解決するための手段】
【００１８】
上記目的を達成するため、本発明では、例えば、動画ストリーミング配信において、１つの配信要求に対して、要求された動画コンテンツが保存されている複数のサーバを用いて動画データを並列にダウンロードする配信形態において、配信フローの平均ホップ長が短くなるよう、他のノードへの平均ホップ長が小さいノードに優先的にサーバを配置することを特徴とする。また、各配信要求に対して、ホップ長の最も短い最近接サーバに加えて、そのホップ数からプラスＢホップ以内の位置に存在するサーバをも配信サーバとして選択する。また、並列配信の効果を高めるために、他の大部分のノードと接続するスーパーハブノードを複数ネットワーク内に配置し、それらスーパーハブノードにサーバを設置する。
【発明の効果】
【００１９】
本発明によれば、データの並列配信における配信フローの平均ホップ長を抑えつつ、リンク負荷の偏りを低減することができる。
【発明を実施するための最良の形態】
【００２０】
以下、図を用いて本発明を実施するための最良の形態例を説明する。図１は、本発明に係るデータ並列配信システムの構成例を示すブロック図であり、図２は、図１におけるデータ並列配信システムを適用するバックボーンネットワークを構成する各ネットワークの一覧を示す説明図、図３は、図２における各ネットワークの分類例を示す説明図、図４は、本発明を適用するネットワークの第１のトポロジ例を示す説明図、図５は、本発明を適用するＳｔａｒ型ネットワークの特性例を示す説明図、図６は、本発明を適用するＨ＆Ｓ型ネットワークの特性例を示す説明図、図７は、本発明を適用するＬａｄｄｅｒ型ネットワークの特性例を示す説明図、図８は、本発明を適用するネットワークの第２のトポロジ例を示す説明図、図９は、本発明の作用結果を示す説明図、図１０は、本発明に係るデータ並列配信方法の処理手順例を示すフローチャートである。
【００２１】
図１におけるデータ並列配信システムは、ネットワークトポロジ設計装置１０１、サーバ配置設計装置１０２、ビデオサーバ１０３、サーバ選択装置１０４からなり、それぞれ、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）や主メモリ、表示装置、入力装置、外部記憶装置等を具備したコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、本発明に係る処理を実行する。
【００２２】
すなわち、動画ストリーミングを配信する際、一つの配信要求に対して、要求された動画コンテンツが保存されている複数のサーバを用いて動画データを並列にダウンロードする配信形態をとり、さらに、配信フローの平均ホップ長が短くなるよう、他のノードへの平均ホップ長が小さいノードに優先的にサーバを配置する。
【００２３】
本例では、プログラムされたコンピュータの処理実行手順として、ネットワークトポロジ設計装置１０１は、並列配信の有効性が向上するようネットワークのトポロジを設計し、サーバ配置設計装置１０２は、平均リンク負荷が抑えられるようサーバの配置ノードを選択し、サーバ選択装置１０４は、ユーザ端末１０５からの動画ストリーミング配信要求を受信すると、平均リンク負荷を抑えながらリンク負荷の偏りが低減するよう配信に用いるサーバ（ビデオサーバ１０３）を選択する。
【００２４】
具体的には、ネットワークにおいてデータの並列配信用サーバ機能を設置するノードを選択する際、ネットワークトポロジ設計装置１０１は、ネットワークを構成する各ノードの接続関係を示すトポロジ情報を生成し記憶装置に格納する手順を実行し、サーバ配置設計装置１０２は、トポロジ情報を記憶装置から読み出して参照し、各ノード間の平均ホップ長を算出する手順を実行すると共に、算出した平均ホップ長が小さいノードを優先して、サーバ機能を設置するサーバノードとして選択する手順を実行する。
【００２５】
尚、サーバ配置設計装置１０２は、サーバ機能を設置するサーバノードとして、予め定められた個数だけ選択する。
【００２６】
また、サーバ選択装置１０４は、ユーザ端末１０５からのデータの配信要求に対して当該データを配信するサーバノードを選択する際に、ホップ長の最も短い最近接のサーバノードを選択する手順を実行すると共に、最近接サーバノードのホップ数に予め定められたホップ数を加えたホップ長以内のサーバノードも加えて選択する手順も実行する。
【００２７】
また、サーバ配置設計装置１０２は、予め定められた割合以上で他のノードと接続されているスーパーハブノードを抽出する手順と、抽出したスーパーハブノードにサーバ機能を設置する手順とを実行する。
【００２８】
また、ネットワークトポロジ設計装置１０１は、トポロジ情報を記憶装置から読み出して参照し、当該ネットワークをスター型（Ｓｔａｒ）、ハブ＆スポーク型（Ｈ＆Ｓ）、ラダー型（Ｌａｄｄｅｒ；梯子）のいずれかとして分類する手順を実行し、サーバ配置設計装置１０２は、Ｓｔａｒ型およびＨ＆Ｓ型に分類したネットワークであれば、当該ネットワークを構成する各ノードの内、最も次数の高いノードを上記サーバノードとして選択する手順を実行する。
【００２９】
また、サーバ設置設計装置１０２は、平均ホップ長が小さく、かつ、当該ネットワークの中心に位置するノードをサーバノードとして選択する。
【００３０】
その際、サーバ設置設計装置１０２は、ネットワークの中心に位置するノードとして、全ノード数Ｎと、ノードｉからノードｊへの最短ホップ経路上のホップ数ｈｉｊとを用いた式「Ｈｉ＝（Ｎ−１）÷（ΣＮｊ＝１，ｊ≠ｉｈｉｊ）」で定義される中心性を表す尺度Ｈｉが最も大きいノードを選択する。
【００３１】
以下、このような構成からなる本例のデータ並列配信システムによる、動画ストリーミング配信における並列配信芸術について、詳細を説明する。
【００３２】
まず、図２と図３および図４を用いて、ネットワークトポロジ設計装置１０１による、ネットワークトポロジの設計技術に関して説明する。
【００３３】
本例では、公開されている商用ＩＳＰのバックボーンネットワークの実際のトポロジを評価に用いる。実際には「３９」のトポロジが公開されているが、本例では、ノード数が２０以上ある「２３」のトポロジを評価対象とする。
【００３４】
図２においては、これら２３のネットワークの名称、ノード数Ｎ、リンク数Ｍ、高次数ノード比率Ｒｈ、最大ノード次数Ｄをまとめている。尚、高次数ノード比率Ｒｈは、ノード次数ｄが平均次数Ｅ（ｄ）を越えているノード数の全ノード数Ｎに対する比率で定義する。
【００３５】
また、図３においては、これらの２３個の各ネットワークに対して、高次数ノード比率Ｒｈと最大ノード次数Ｄの散布状態を示す。そして、本図３に基づき、２３のネットワークを、Ｓｔａｒ型、Ｈ＆Ｓ型、Ｌａｄｄｅｒ型の三つのグループに分類する。
【００３６】
Ｓｔａｒ型は、図４（ａ）に示すように、非常に少数のハブノードが、他のほとんど全てのノードと接続しており、高次数ノード比率Ｒｈが小さく、最大ノード次数Ｄが大きな特徴がある。ここでは、Ｄ≧１０かつＲｈ＜０．２のネットワークをＳｔａｒ型と定義し、図３に示すように、５つのネットワークがＳｔａｒ型となる。
【００３７】
Ｈ＆Ｓ型は、図４（ｂ）に示すように、相互接続された数個のハブノードが存在する。他のノードは、一つ以上のハブノードに接続しているため、本構造はハブ＆スポーク型を呼ばれる。航空路線網が本形態となることが知られている。
【００３８】
Ｈ＆Ｓ型では、ハブノードを介して少ないホップ数で他のノードに到達することができるため、ノード間のホップ距離（ホップ長）が小さくなる傾向がある。ここでは、Ｄ≧１０かつＲｈ≧０．２のネットワークをＨ＆Ｓ型と定義し、図３に示すように、６つのネットワークが本形状となる。
【００３９】
Ｌａｄｄｅｒ型では、図４（ｃ）に示すように、ハブノードが存在せず、いくつかのループを組み合わせたトポロジ構造となる。総リンク長を抑えることができる反面、ノード間ホップ距離（ホップ長）が長くなる傾向がある。高速道路網が本形態となることが知られている。
【００４０】
ここでは、Ｄ＜１０のネットワークをＬａｄｄｅｒ型と定義し、図３に示すように、１２のネットワークが本形態となる。
【００４１】
図３において、これら三つのトポロジ例で示されるネットワークは、全て米国に存在するが、ネットワーク種別に応じて大きく形状が異なることが確認できる。
【００４２】
インターネットのＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ）内ルーティングプロトコル（ＯＳＰＦ：Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）は、各ノード間に最小コストの経路を設定するため、各サーバとユーザ間に対してダイクストラの最短ホップ経路が選択されることを想定する。
【００４３】
次に、サーバ配置設計装置１０２による、サーバの配置技術に関して説明する。ここでは、サーバが設置されたノードをサーバノード、サーバが設置されていないノードをユーザノードと表記する。
【００４４】
サーバノード数の全ノード数Ｎに対する比率をｓと定義し、サーバノード数をＳとする。すなわち、サーバノード数Ｓは、「ｓ×Ｎ」の小数点以下を切り上げした値となる。
【００４５】
サーバノードｉに収容されているユーザに対しては、サーバノードｉに設置されたサーバから、動画データの全体を配信するのが最も効率がよいので、以後の評価では、サーバノードに収容されたユーザは評価対象外とする。
【００４６】
ユーザノードに収容されたユーザに対しては、他のノードに設置されたサーバから動画データを転送する必要がある。この際、リンクに加わるトラヒック負荷を最小化するためには、最もユーザからのホップ距離（ホップ長）が近いサーバから動画データを転送するのが望ましい。
【００４７】
従って、他のノードへの平均ホップ距離（ホップ長）が小さく、ネットワークの中心に位置するノードにサーバを設置するのが望ましい。
【００４８】
ここで、ノードｉからノードｊへの最短ホップ経路上のホップ数（経由するルータ等の数）をｈｉｊとする。さらにＨｉを、ノードｉの中心性を表す尺度として、「Ｈｉ＝（Ｎ−１）÷（ΣＮｊ＝１，ｊ≠ｉｈｉｊ）」と定義し、そして、中心性を表す尺度Ｈｉが最も大きいＳ個のノードにサーバを配置する。
【００４９】
ｓ＝０．１とした場合の、Ｓｔａｒ型ネットワークであるＮＷ１４（ＭｉｎｄＳｐｒｉｎｇ）と、Ｈ＆Ｓ型ネットワークであるＮＷ３（Ａｌｌｅｇｉａｎｃｅ Ｔｅｌｅｃｏｍ）のサーバ配置ノードを確認したところ、全てのサーバ（ＮＷ１４では５つ、ＮＷ３では６つ）は、最も次数の高いノードに配置された。
【００５０】
Ｓｔａｒ型ネットワークやＨ＆Ｓ型ネットワークでは、ハブノードの中心性（Ｈｉ）が高く、上述の条件でサーバを配置すると、ハブノードにサーバが配置される。
【００５１】
Ｌａｄｄｅｒ型のネットワークであるＮＷ７（ＣＡＩＳ Ｉｎｔｅｒｎｅｔ）に対しても、サーバ配置ノードを確認したところ、図４（ｃ）において矢印で示した４つのノードに配置された。
【００５２】
このように、Ｌａｄｄｅｒ型ネットワークでは、高次数ノードにサーバが配置されるとは限らない。
【００５３】
次に、サーバ選択装置１０４の処理内容として、サーバの選択技術について説明する。
【００５４】
平均リンク負荷を最小化するためには、ホップ距離の小さいサーバを選択することが望ましい。
【００５５】
従って、従来のＣＤＮにおける単一フロー配信技術においては、各配信要求に対して、ホップ距離の最も近いサーバを一つ選択する。そのようなサーバが複数存在する場合には、シミュレーションの開始時において、それらの中から一つをランダムに選択する。
【００５６】
一方、本例のデータ並列配信システムの場合は、ユーザノードｉの配信要求に対して、ユーザノードｉからのホップ距離が「ｂｉ＋Ｂ」以下のサーバを全て選択する。ただし、「ｂｉ」は、ユーザノードｉから最もホップ距離の近いサーバノードへのホップ距離、「Ｂ」は任意に与えられる整数パラメタである。
【００５７】
このように、本例では、最近接ノードに加えて、「Ｂ」ホップまでホップ数の長いサーバも選択対象に含める。
【００５８】
しかし、この場合、「Ｂ」の増加に伴い、一つの動画ストリーミングセッションに用いられるサーバ数が増加して並列度が向上する反面、フローの平均ホップ長が増加する。そのため、平均リンク負荷が増加する。
【００５９】
以下、以上の本例のシステムによる処理の評価結果を説明する。
【００６０】
転送レートがｃ（ｂｐｓ）で時間長がＴ（秒）の単一種の動画コンテンツを考える。「Ｎ−Ｓ」個の各ユーザノードに対して、発生レートがλのポアソン過程により配信要求を発生させる。リンク負荷をｃで正規化し、λは、式「λ＝ρ×Ｍ÷｛Ｈ×（Ｎ−Ｓ）×Ｔ}」で定義する。
【００６１】
尚、上記式における「ρ」は単一フロー配信における各リンクの平均ふかであり、Ｍはリンク数である。また、「Ｈ」は、最近接サーバへの平均ホップ距離であり、式「Ｈ＝Σｉ∈Ｚ｛ｂｉ÷（Ｎ−Ｓ）｝」で定義される。この式において、「Ｚ」はユーザノード集合である。
【００６２】
以後の評価では、ρ＝１、Ｔ＝１２００秒とする。
【００６３】
選択したサーバに対して最短ホップ経路が複数存在する場合には、各配信要求に対して一つの経路がランダムに選択される。
【００６４】
図５（ａ），（ｂ）においては、５つのＳｔａｒ型ネットワークを対象に、各ストリーミング配信セッションにおける平均フロー数（各配信要求に対して選択されるサーバ数の平均値）を「Ｂ」に対して示す。
【００６５】
図５（ａ）では「ｓ＝０．１」、図５（ｂ）では「ｓ＝０．３」と設定した。ただし、結果を、「０≦Ｂ≦Ｂｍａｘ」の範囲で示している（「Ｂｍａｘ」は任意のユーザノードに対して全てのサーバが選択されるＢの最小の値）。
【００６６】
Ｓｔａｒ型ネットワークでは、ハブノードと他のノード間のホップ距離が短いため、全てのユーザノードは、２ホップ以内で全てのサーバノードに到達できる。
【００６７】
図８（ａ）において矢印で示すように、ＮＷ１２（ＧｏｏｄＮｅｔ）では、３つのハブノードの次数が極めて大きい。これらハブノード（スーパーハブノード）は、他の５８％〜６９％のノードと接続しており、多数のユーザノードは、２つか３つのスーパーハブノードと接続している。従って、ＮＷ１２では、各配信セッションの平均並列フロー数が大きい。
【００６８】
図５（ｃ），（ｄ）においては、スター型ネットワークを対象に、正規化平均リンク負荷を示す。ただし、この正規化平均リンク負荷は、並列フロー配信システム（ＰＤＳ： Ｐａｒａｌｌｅｌ Ｄｏｗｎｌｏａｄ Ｓｙｓｔｅｍ）における平均リンク負荷を、単一フロー配信システム（ＳＤＳ：Ｓｉｎｇｌｅ Ｄｏｗｎｌｏａｄ Ｓｙｓｔｅｍ）における平均リンク負荷で除したものと定義する。
【００６９】
配信要求の発生レートは固定されているため、平均リンク負荷はフローの平均ホップ長に比例する。ＳＤＳでは最近接サーバが常に選択されるため、ＳＤＳにおける平均リンク負荷は、与えられた網トポロジとサーバ配置位置に対して最小となる。よって正規化平均リンク負荷は常に１以上の値をとる。
【００７０】
「Ｂ」の増加に伴い、ＰＤＳにおけるフローの平均ホップ長が増加するため、平均リンク負荷も増加する。
【００７１】
さらに、リンク負荷のＣＶの正規化値（ＰＤＳのリンク負荷のＣＶをＳＤＳのリンク負荷のＣＶで除した値）を図５（ｅ），（ｆ）に示す。
【００７２】
この値が「１」より小さい場合に、ＰＤＳがＳＤＳと比較してリンク負荷のＣＶが低減することを意味する。
【００７３】
ＮＷ１２を除いた４つのＳｔａｒ型ネットワークでは、少数のハブノードが存在し、他の多くのノードはこれらハブノードの１つと接続している。
【００７４】
図５（ｅ）に示すように、ｓ＝０．１のとき、サーバはこれら少数のハブノードにのみ設置され、「Ｂ」を１以上に設定すると、多くのフローは、ハブノード間に設置されたリンクを経由する結果、ＰＤＳにおいてリンク負荷のＣＶが増加する。
【００７５】
それに対してＮＷ１２では、多くのノードは２つか３つのスーパーハブノードと接続しており、スーパーハブノード間に設置されたリンクへの負荷の集中が回避される。
【００７６】
図６においては、６つのＨ＆Ｓ型ネットワークに対する三つの特性について同様に示す。
【００７７】
Ｈ＆Ｓ型ネットワークにおいても、多数のノードはサーバノード（ハブノード）に短いホップ距離で到達できるため、「Ｂ」を２以下に設定した場合でも配信時の並列フロー数を高めることが可能である。
【００７８】
さらに、Ｈ＆Ｓ型ネットワークではハブノードが多数存在し、それらは相互接続している傾向がある。そのため、「Ｂ」を１以上に設定した場合でも、ハブノード間の特定のリンクへの負荷集中は回避され、リンク負荷のＣＶは低減する。
【００７９】
総ノード数Ｎの大きなネットワークほど、「Ｂ」を１以上に設定した場合の並列フロー数がより大きくなり、リンク負荷のＣＶの低減度合いも大きくなる。
【００８０】
図７においては、１２のＬａｄｄｅｒ型ネットワークに対してこれら三つの特性を同様に示す。
【００８１】
Ｌａｄｄｅｒ型ネットワークではノード間の平均距離が大きいため、各ストリーミング配信の並列フロー数を十分に高めるためには「Ｂ」を大きな値に設定する必要がある。
【００８２】
「Ｂ」を大きくしたときのＬａｄｄｅｒ型ネットワークのフローの平均ホップ長の増加度合いは大きいため、Ｌａｄｄｅｒ型ネットワークの正規化平均リンク負荷はＳｔａｒ型やＨ＆Ｓ型のそれに比べて大きい。尚、Ｌａｄｄｅｒ型ネットワークにおいても、リンク負荷のＣＶはＰＤＳにより低減する。
【００８３】
以上の説明をまとめると、ＮＷ１２を除き、Ｓｔａｒ型ネットワークにおいて少数のサーバのみを設置した場合、ＰＤＳを用いるメリットはない。
【００８４】
Ｓｔａｒ型ネットワークにおいて３割程度のノードにサーバを設置した場合や、Ｈ＆Ｓ型やＬａｄｄｅｒ型ネットワークにおいては、ＰＤＳを用い、さらに最近接ノード以外にホップ数の長いサーバも配信に用いた場合、リンク負荷のＣＶは低減する反面、平均リンク負荷が増加する。
【００８５】
よって、ＰＤＳにおいて最近接サーバ以外のサーバも含めて並列配信を行う明確なメリットは見出せない。
【００８６】
ただし、「Ｂ＝０」に設定し、最近接サーバのみを並列配信に用いる場合には、平均リンク負荷の増加を避けながらリンク負荷のＣＶを低減させることが可能であり、ＰＤＳを用いる明確なメリットが見出せる。
【００８７】
しかし、この場合、ＰＤＳの効果は各ユーザノードに対して最近接サーバがいくつ存在するかに依存する。このことを確認するため、図９に、「Ｂ＝０」と設定したときのリンク負荷のＣＶの正規化値を最近接サーバ数比率ηに対して示す。
【００８８】
ただしηは、式「η＝｛Σｉ∈Ｚｘｉ（ｂｉ）｝÷｛（Ｎ−Ｓ）×Ｓ｝」で定義する。この式における「ｘｉ（ｂｉ）」は、ユーザノードｉにおける最近接サーバ（ノードｉからのホップ距離がｂｉのサーバノード）の数である。
【００８９】
これら二つの尺度間には負の相関が確認できる。すなわち、ηが大きなネットワークほどＰＤＳが有効となる。
【００９０】
ηに関して、Ｓｔａｒ型、Ｈ＆Ｓ型、Ｌａｄｄｅｒ型といったネットワーク種別による明確な違いは見られない。
【００９１】
ＮＷ１２（ＧｏｏｄＮｅｔ）はηが大きく、最近接サーバのみを用いて並列配信を行ってもリンク負荷のＣＶの低減効果が顕著に見られる。これは前述したように、ＮＷ１２では、多数のユーザノードが２つか３つのスーパーハブノードと接続していることが原因である。
【００９２】
ＮＷ１７（Ｓａｖｖｉｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）とＮＷ１９（Ｓｐｒｉｎｔ）もηが大きいが、リンク負荷のＣＶの低減効果は限定的である。
【００９３】
ＮＷ１７とＮＷ１９では最大ノード次数が各々１０と８であり、ハブノードは４０％程度以下の他のノードと接続しているのみである。
【００９４】
これらネットワークでは、ＮＷ１２で見られたようなスーパーハブノードが存在せず、リンク負荷のＣＶの低減効果は限定的となっている。図８（ｂ），（ｃ）に、これら二つのネットワーク（ＮＷ１７とＮＷ１９）を示す。
【００９５】
よって、ＮＷ１７のように、ほとんどのノードを接続するスーパーハブノードが２つ以上存在し、かつ、そのようなスーパーハブノードにサーバが設置された場合には、動画ストリーミングサービスを並列配信で提供することにより平均リンク負荷の増加を避けながらリンク負荷の偏りを大きく低減することが可能となる。
【００９６】
次に、図１０を用いて、図１におけるデータ並列配信システムによる本発明に係る処理動作例を説明する。
【００９７】
まず、ネットワークトポロジ設計装置１０１により、ネットワークを構成する各ノードの接続関係を示すトポロジ情報を生成し記憶装置に格納する手順を実行する（ステップＳ１００１）。
【００９８】
次に、サーバ配置設計装置１０２により、トポロジ情報を記憶装置から読み出して参照し、各ノード間の平均ホップ長を算出する手順と、算出した平均ホップ長が小さいノードを優先して、データを並列配信するサーバ機能を設置するサーバノードとして選択する手順とを実行する（ステップＳ１００２）。尚、この際、サーバ機能を設置するサーバノードとして、予め定められた個数だけ選択する。
【００９９】
そして、サーバ選択装置１０４により、データの配信要求に対して当該データを配信するサーバノードを選択する際、ホップ長の最も短い最近接のサーバノードを選択する手順と、この最近接サーバのホップ数に予め定められたホップ数を加えたホップ長以内のサーバノードも加えて選択する手順とを実行する（ステップＳ１００３）。
【０１００】
以上、図１〜図１０を用いて説明したように、本例では、ネットワークにおけるデータの並列配信を行う際、ネットワークトポロジ設計装置１０１により、ネットワークを構成する各ノードの接続関係を示すトポロジ情報を生成し、サーバ配置設計装置１０２により、このトポロジ情報を参照して各ノード間の平均ホップ長を算出し、算出した平均ホップ長が小さいノードを優先して、データを並列配信するサーバ機能を設置する。
【０１０１】
その際、サーバ配置設計装置１０２は、サーバ機能を設置するサーバノードとして、予め定められた個数だけ選択する。
【０１０２】
また、サーバ選択装置１０４において、ユーザ端末１０５からのネットワークを介してのデータの配信要求に対して当該データを配信するサーバノードを選択する際、ホップ長の最も短い最近接のサーバノードを選択すると共に、この最近接サーバのホップ数に予め定められたホップ数を加えたホップ長以内のサーバノードも加えて選択する。
【０１０３】
また、サーバ配置設計装置１０２は、予め定められた割合以上で他のノードと接続されているスーパーハブノードを抽出し、抽出したスーパーハブノードにサーバ機能を設置する。
【０１０４】
また、ネットワークトポロジ設計装置１０１は、トポロジ情報を記憶装置から読み出して参照し、当該ネットワークをＳｔａｒ型、Ｈ＆Ｓ型、Ｌａｄｄｅｒ型のいずれかとして分類し、サーバ配置設計装置１０２は、Ｓｔａｒ型およびＨ＆Ｓ型に分類したネットワークであれば、当該ネットワークを構成する各ノードの内、最も次数の高いノードをサーバノードとして選択する。
【０１０５】
また、サーバ配置設計装置１０２は、平均ホップ長が小さく、かつ、当該ネットワークの中心に位置するノードをサーバノードとして選択する。
【０１０６】
また、サーバ配置設計装置１０２は、ネットワークの中心に位置するノードとして、全ノード数Ｎと、ノードｉからノードｊへの最短ホップ経路上のホップ数ｈｉｊとを用いた式「Ｈｉ＝（Ｎ−１）÷（ΣＮｊ＝１，ｊ≠ｉｈｉｊ）」で定義される中心性を表す尺度Ｈｉが最も大きいノードを選択する。
【０１０７】
このことにより、本例によれば、動画ストリーミング配信において、１つの配信要求に対して、要求された動画コンテンツが保存されている複数のサーバを用いて動画データを並列にダウンロードする配信形態において、配信フローの平均ホップ長を抑えつつ、リンク負荷の偏りを低減する効果を得ることができる。これにより、複数のサーバを用いたデータの並列配信を効率的に行うことができ、ＨＤＴＶやＵＨＤＶ等の超高画質の動画ストリーミングのネットワーク配信サービスの実現が可能となる。
【０１０８】
尚、本発明は、図１〜図１０を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、本発明に係る処理手順を実行するコンピュータ装置として、ネットワークトポロジ設計装置１０１、サーバ配置設計装置１０２、ビデオサーバ１０３、サーバ選択装置１０４のそれぞれを個別に設けた構成としているが、各々の機能を１つのコンピュータ装置内に設けた構成としても良い。
【０１０９】
また、本例のコンピュータ装置の構成としては、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【図面の簡単な説明】
【０１１０】
【図１】本発明に係るデータ並列配信システムの構成例を示すブロック図である。
【図２】図１におけるデータ並列配信システムを適用するバックボーンネットワークを構成する各ネットワークの一覧を示す説明図である。
【図３】図２における各ネットワークの分類例を示す説明図である。
【図４】本発明を適用するネットワークの第１のトポロジ例を示す説明図である。
【図５】本発明を適用するＳｔａｒ型ネットワークの特性例を示す説明図である。
【図６】本発明を適用するＨ＆Ｓ型ネットワークの特性例を示す説明図である。
【図７】本発明を適用するＬａｄｄｅｒ型ネットワークの特性例を示す説明図である。
【図８】本発明を適用するネットワークの第２のトポロジ例を示す説明図である。
【図９】本発明の作用結果を示す説明図である。
【図１０】本発明に係るデータ並列配信方法の処理手順例を示すフローチャートである。
【符号の説明】
【０１１１】
１０１：ネットワークトポロジ設計装置、１０２：サーバ配置設計装置、１０３：ビデオサーバ、１０４：サーバ選択装置、１０５：ユーザ端末。
【技術分野】
【０００１】
本発明は、ネットワークを介して動画ストリーミング等のデータを配信する技術に係り、特に、一つの配信要求に対して、要求されたデータが保存されている複数のサーバから、当該データを並列にダウンロードするデータ並列配信形態において、平均リンク負荷の増加を抑えながらリンク負荷の偏りを効果的に低減するのに好適な技術に関するものである。
【背景技術】
【０００２】
近年、Ｙｏｕｔｕｂｅ等の動画ストリーミングサービスをインターネット上で利用するユーザ数の数が急増している。高品質な動画ストリーミング配信に対する要求は強く、近い将来、約２５Ｍｂｐｓのビットレートを有するＨＤＴＶ（ｈｉｇｈ ｄｅｆｉｎｉｔｉｏｎ ＴＶ）の視聴がインターネット上でも可能になると思われる。
【０００３】
さらに、ＮＨＫによって、より品質を向上させたＵＨＤＶ（Ｕｌｔｒａ Ｈｉｇｈ Ｄｅｆｉｎｉｔｉｏｎ Ｖｉｄｅｏ）が提案されている。このＵＨＤＶの画像の非圧縮時のビットレートは２４Ｇｂｐｓであり、圧縮後も１８０から６００Ｍｂｐｓの高いレートを有する。
【０００４】
このようなＨＤＴＶやＵＨＤＶの高い画像品質での動画ストリーミングサービスは、インターネットにおける重要なサービスの一つになると思われるが、これらのサービスによって生成されるトラヒックフローの伝送レートは非常に高く、サーバやリンクの輻輳を招く要因となることが予想される。そのためこれらサービスの提供に際しては、サーバやリンクの負荷を分散させることを検討する必要がある。
【０００５】
サーバの負荷分散を図る効率的な技術として、例えば非特許文献１等に記載のＣＤＮ（Ｃｏｎｔｅｎｔｓ Ｄｅｌｉｖｅｒｙ Ｎｅｔｗｏｒｋ）が広く知られている。このＣＤＮは、ネットワーク上に複数のサーバを用意し、ユーザの各配信要求に対して１つのサーバを選択する。その結果、複数のサーバ間で負荷が分散される。
【０００６】
しかし、このＣＤＮは、各配信要求に対して常に１つのサーバのみを選択するため、ＨＤＴＶやＵＨＤＶのストリーミング配信によって生成されるフローがネットワークに与える影響を緩和することはできない。
【０００７】
これらフローの転送レートを抑えるためには、１人のユーザに対する１本のストリーミングセッションに対して、複数のサーバを用いる必要がある。例えば、２つのサーバを１本の配信セッションに用いることにより、このセッションによって生成される各フローの転送レートを半分に抑えることができる。
【０００８】
また、ＨＤＴＶやＵＨＤＶの動画ストリーミングサービスによって生じる高レートフローのネットワークに与える影響を、並列配信によって低減させることが可能となる。
【０００９】
このような並列配信技術は、例えば、Ｐ２Ｐファイル共有サービスとして有名なＢｉｔＴｏｒｒｅｎｔにおいても用いている。
【００１０】
しかし、このＢｉｔＴｏｒｒｅｎｔでは、各ユーザは、他のユーザやオリジナルサーバからデータをダウンロードする間、他のユーザにデータセグメントをアップロードする必要がある。そのため、ＢｉｔＴｏｒｒｅｎｔの性能は、ユーザの行動や上り方向のアクセス回線レートに大きく依存する。
【００１１】
また、配信中のユーザの数が増加するほど、コンテンツを提供するサーバが増加することになるため、データをダウンロードするスループットは、ユーザ数の増加に伴い増加する。
【００１２】
ＨＤＴＶやＵＨＤＶの動画配信の転送ビットレートは極めて大きいので、大容量の上りアクセスリンクを有する多数のユーザが、これら超高画質の配信サービスを利用することを期待することは困難である。
【００１３】
そのため、ＢｉｔＴｏｒｒｅｎｔ等のＰ２Ｐファイル共有システム上で、ＨＤＴＶやＵＨＤＶの動画ストリーミング配信を提供することは困難である。
【００１４】
これらサービスのフローがネットワークに与える影響を緩和するためには、ＣＤＮ事業者、ＩＳＰ（Ｉｎｔｅｒｎｅｔ Ｓｅｒｖｉｃｅ Ｐｒｏｖｉｄｅｒ）、ネットワークキャリアなどが運用する複数のサーバから並列配信を行う必要がある。
【００１５】
【非特許文献１】Ａ．Ｓｕ,Ｄ．Ｃｈｏｆｆｎｅｓ,Ａ．Ｋｕｚｍａｎｏｖｉｃ, ａｎｄ Ｆ．Ｂｕｓｔａｍａｎｔｅ,“Ｄｒａｆｔｉｎｇ Ｂｅｈｉｎｄ Ａｋａｍａｉ （Ｔｒａｖｅｌｏｃｉｔｙ−Ｂａｓｅｄ Ｄｅｔｏｕｒｉｎｇ）,” ＡＣＭ ＳＩＧＣＯＭＭ ２００６．
【発明の開示】
【発明が解決しようとする課題】
【００１６】
解決しようとする問題点は、従来の技術では、複数のサーバを用いたデータの並列配信を効率的に行うことができない点である。
【００１７】
本発明の目的は、これら従来技術の課題を解決し、ＨＤＴＶやＵＨＤＶ等の超高画質の動画ストリーミングのネットワーク配信サービスの実現を可能とすることである。
【課題を解決するための手段】
【００１８】
上記目的を達成するため、本発明では、例えば、動画ストリーミング配信において、１つの配信要求に対して、要求された動画コンテンツが保存されている複数のサーバを用いて動画データを並列にダウンロードする配信形態において、配信フローの平均ホップ長が短くなるよう、他のノードへの平均ホップ長が小さいノードに優先的にサーバを配置することを特徴とする。また、各配信要求に対して、ホップ長の最も短い最近接サーバに加えて、そのホップ数からプラスＢホップ以内の位置に存在するサーバをも配信サーバとして選択する。また、並列配信の効果を高めるために、他の大部分のノードと接続するスーパーハブノードを複数ネットワーク内に配置し、それらスーパーハブノードにサーバを設置する。
【発明の効果】
【００１９】
本発明によれば、データの並列配信における配信フローの平均ホップ長を抑えつつ、リンク負荷の偏りを低減することができる。
【発明を実施するための最良の形態】
【００２０】
以下、図を用いて本発明を実施するための最良の形態例を説明する。図１は、本発明に係るデータ並列配信システムの構成例を示すブロック図であり、図２は、図１におけるデータ並列配信システムを適用するバックボーンネットワークを構成する各ネットワークの一覧を示す説明図、図３は、図２における各ネットワークの分類例を示す説明図、図４は、本発明を適用するネットワークの第１のトポロジ例を示す説明図、図５は、本発明を適用するＳｔａｒ型ネットワークの特性例を示す説明図、図６は、本発明を適用するＨ＆Ｓ型ネットワークの特性例を示す説明図、図７は、本発明を適用するＬａｄｄｅｒ型ネットワークの特性例を示す説明図、図８は、本発明を適用するネットワークの第２のトポロジ例を示す説明図、図９は、本発明の作用結果を示す説明図、図１０は、本発明に係るデータ並列配信方法の処理手順例を示すフローチャートである。
【００２１】
図１におけるデータ並列配信システムは、ネットワークトポロジ設計装置１０１、サーバ配置設計装置１０２、ビデオサーバ１０３、サーバ選択装置１０４からなり、それぞれ、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）や主メモリ、表示装置、入力装置、外部記憶装置等を具備したコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、本発明に係る処理を実行する。
【００２２】
すなわち、動画ストリーミングを配信する際、一つの配信要求に対して、要求された動画コンテンツが保存されている複数のサーバを用いて動画データを並列にダウンロードする配信形態をとり、さらに、配信フローの平均ホップ長が短くなるよう、他のノードへの平均ホップ長が小さいノードに優先的にサーバを配置する。
【００２３】
本例では、プログラムされたコンピュータの処理実行手順として、ネットワークトポロジ設計装置１０１は、並列配信の有効性が向上するようネットワークのトポロジを設計し、サーバ配置設計装置１０２は、平均リンク負荷が抑えられるようサーバの配置ノードを選択し、サーバ選択装置１０４は、ユーザ端末１０５からの動画ストリーミング配信要求を受信すると、平均リンク負荷を抑えながらリンク負荷の偏りが低減するよう配信に用いるサーバ（ビデオサーバ１０３）を選択する。
【００２４】
具体的には、ネットワークにおいてデータの並列配信用サーバ機能を設置するノードを選択する際、ネットワークトポロジ設計装置１０１は、ネットワークを構成する各ノードの接続関係を示すトポロジ情報を生成し記憶装置に格納する手順を実行し、サーバ配置設計装置１０２は、トポロジ情報を記憶装置から読み出して参照し、各ノード間の平均ホップ長を算出する手順を実行すると共に、算出した平均ホップ長が小さいノードを優先して、サーバ機能を設置するサーバノードとして選択する手順を実行する。
【００２５】
尚、サーバ配置設計装置１０２は、サーバ機能を設置するサーバノードとして、予め定められた個数だけ選択する。
【００２６】
また、サーバ選択装置１０４は、ユーザ端末１０５からのデータの配信要求に対して当該データを配信するサーバノードを選択する際に、ホップ長の最も短い最近接のサーバノードを選択する手順を実行すると共に、最近接サーバノードのホップ数に予め定められたホップ数を加えたホップ長以内のサーバノードも加えて選択する手順も実行する。
【００２７】
また、サーバ配置設計装置１０２は、予め定められた割合以上で他のノードと接続されているスーパーハブノードを抽出する手順と、抽出したスーパーハブノードにサーバ機能を設置する手順とを実行する。
【００２８】
また、ネットワークトポロジ設計装置１０１は、トポロジ情報を記憶装置から読み出して参照し、当該ネットワークをスター型（Ｓｔａｒ）、ハブ＆スポーク型（Ｈ＆Ｓ）、ラダー型（Ｌａｄｄｅｒ；梯子）のいずれかとして分類する手順を実行し、サーバ配置設計装置１０２は、Ｓｔａｒ型およびＨ＆Ｓ型に分類したネットワークであれば、当該ネットワークを構成する各ノードの内、最も次数の高いノードを上記サーバノードとして選択する手順を実行する。
【００２９】
また、サーバ設置設計装置１０２は、平均ホップ長が小さく、かつ、当該ネットワークの中心に位置するノードをサーバノードとして選択する。
【００３０】
その際、サーバ設置設計装置１０２は、ネットワークの中心に位置するノードとして、全ノード数Ｎと、ノードｉからノードｊへの最短ホップ経路上のホップ数ｈｉｊとを用いた式「Ｈｉ＝（Ｎ−１）÷（ΣＮｊ＝１，ｊ≠ｉｈｉｊ）」で定義される中心性を表す尺度Ｈｉが最も大きいノードを選択する。
【００３１】
以下、このような構成からなる本例のデータ並列配信システムによる、動画ストリーミング配信における並列配信芸術について、詳細を説明する。
【００３２】
まず、図２と図３および図４を用いて、ネットワークトポロジ設計装置１０１による、ネットワークトポロジの設計技術に関して説明する。
【００３３】
本例では、公開されている商用ＩＳＰのバックボーンネットワークの実際のトポロジを評価に用いる。実際には「３９」のトポロジが公開されているが、本例では、ノード数が２０以上ある「２３」のトポロジを評価対象とする。
【００３４】
図２においては、これら２３のネットワークの名称、ノード数Ｎ、リンク数Ｍ、高次数ノード比率Ｒｈ、最大ノード次数Ｄをまとめている。尚、高次数ノード比率Ｒｈは、ノード次数ｄが平均次数Ｅ（ｄ）を越えているノード数の全ノード数Ｎに対する比率で定義する。
【００３５】
また、図３においては、これらの２３個の各ネットワークに対して、高次数ノード比率Ｒｈと最大ノード次数Ｄの散布状態を示す。そして、本図３に基づき、２３のネットワークを、Ｓｔａｒ型、Ｈ＆Ｓ型、Ｌａｄｄｅｒ型の三つのグループに分類する。
【００３６】
Ｓｔａｒ型は、図４（ａ）に示すように、非常に少数のハブノードが、他のほとんど全てのノードと接続しており、高次数ノード比率Ｒｈが小さく、最大ノード次数Ｄが大きな特徴がある。ここでは、Ｄ≧１０かつＲｈ＜０．２のネットワークをＳｔａｒ型と定義し、図３に示すように、５つのネットワークがＳｔａｒ型となる。
【００３７】
Ｈ＆Ｓ型は、図４（ｂ）に示すように、相互接続された数個のハブノードが存在する。他のノードは、一つ以上のハブノードに接続しているため、本構造はハブ＆スポーク型を呼ばれる。航空路線網が本形態となることが知られている。
【００３８】
Ｈ＆Ｓ型では、ハブノードを介して少ないホップ数で他のノードに到達することができるため、ノード間のホップ距離（ホップ長）が小さくなる傾向がある。ここでは、Ｄ≧１０かつＲｈ≧０．２のネットワークをＨ＆Ｓ型と定義し、図３に示すように、６つのネットワークが本形状となる。
【００３９】
Ｌａｄｄｅｒ型では、図４（ｃ）に示すように、ハブノードが存在せず、いくつかのループを組み合わせたトポロジ構造となる。総リンク長を抑えることができる反面、ノード間ホップ距離（ホップ長）が長くなる傾向がある。高速道路網が本形態となることが知られている。
【００４０】
ここでは、Ｄ＜１０のネットワークをＬａｄｄｅｒ型と定義し、図３に示すように、１２のネットワークが本形態となる。
【００４１】
図３において、これら三つのトポロジ例で示されるネットワークは、全て米国に存在するが、ネットワーク種別に応じて大きく形状が異なることが確認できる。
【００４２】
インターネットのＡＳ（Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ）内ルーティングプロトコル（ＯＳＰＦ：Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）は、各ノード間に最小コストの経路を設定するため、各サーバとユーザ間に対してダイクストラの最短ホップ経路が選択されることを想定する。
【００４３】
次に、サーバ配置設計装置１０２による、サーバの配置技術に関して説明する。ここでは、サーバが設置されたノードをサーバノード、サーバが設置されていないノードをユーザノードと表記する。
【００４４】
サーバノード数の全ノード数Ｎに対する比率をｓと定義し、サーバノード数をＳとする。すなわち、サーバノード数Ｓは、「ｓ×Ｎ」の小数点以下を切り上げした値となる。
【００４５】
サーバノードｉに収容されているユーザに対しては、サーバノードｉに設置されたサーバから、動画データの全体を配信するのが最も効率がよいので、以後の評価では、サーバノードに収容されたユーザは評価対象外とする。
【００４６】
ユーザノードに収容されたユーザに対しては、他のノードに設置されたサーバから動画データを転送する必要がある。この際、リンクに加わるトラヒック負荷を最小化するためには、最もユーザからのホップ距離（ホップ長）が近いサーバから動画データを転送するのが望ましい。
【００４７】
従って、他のノードへの平均ホップ距離（ホップ長）が小さく、ネットワークの中心に位置するノードにサーバを設置するのが望ましい。
【００４８】
ここで、ノードｉからノードｊへの最短ホップ経路上のホップ数（経由するルータ等の数）をｈｉｊとする。さらにＨｉを、ノードｉの中心性を表す尺度として、「Ｈｉ＝（Ｎ−１）÷（ΣＮｊ＝１，ｊ≠ｉｈｉｊ）」と定義し、そして、中心性を表す尺度Ｈｉが最も大きいＳ個のノードにサーバを配置する。
【００４９】
ｓ＝０．１とした場合の、Ｓｔａｒ型ネットワークであるＮＷ１４（ＭｉｎｄＳｐｒｉｎｇ）と、Ｈ＆Ｓ型ネットワークであるＮＷ３（Ａｌｌｅｇｉａｎｃｅ Ｔｅｌｅｃｏｍ）のサーバ配置ノードを確認したところ、全てのサーバ（ＮＷ１４では５つ、ＮＷ３では６つ）は、最も次数の高いノードに配置された。
【００５０】
Ｓｔａｒ型ネットワークやＨ＆Ｓ型ネットワークでは、ハブノードの中心性（Ｈｉ）が高く、上述の条件でサーバを配置すると、ハブノードにサーバが配置される。
【００５１】
Ｌａｄｄｅｒ型のネットワークであるＮＷ７（ＣＡＩＳ Ｉｎｔｅｒｎｅｔ）に対しても、サーバ配置ノードを確認したところ、図４（ｃ）において矢印で示した４つのノードに配置された。
【００５２】
このように、Ｌａｄｄｅｒ型ネットワークでは、高次数ノードにサーバが配置されるとは限らない。
【００５３】
次に、サーバ選択装置１０４の処理内容として、サーバの選択技術について説明する。
【００５４】
平均リンク負荷を最小化するためには、ホップ距離の小さいサーバを選択することが望ましい。
【００５５】
従って、従来のＣＤＮにおける単一フロー配信技術においては、各配信要求に対して、ホップ距離の最も近いサーバを一つ選択する。そのようなサーバが複数存在する場合には、シミュレーションの開始時において、それらの中から一つをランダムに選択する。
【００５６】
一方、本例のデータ並列配信システムの場合は、ユーザノードｉの配信要求に対して、ユーザノードｉからのホップ距離が「ｂｉ＋Ｂ」以下のサーバを全て選択する。ただし、「ｂｉ」は、ユーザノードｉから最もホップ距離の近いサーバノードへのホップ距離、「Ｂ」は任意に与えられる整数パラメタである。
【００５７】
このように、本例では、最近接ノードに加えて、「Ｂ」ホップまでホップ数の長いサーバも選択対象に含める。
【００５８】
しかし、この場合、「Ｂ」の増加に伴い、一つの動画ストリーミングセッションに用いられるサーバ数が増加して並列度が向上する反面、フローの平均ホップ長が増加する。そのため、平均リンク負荷が増加する。
【００５９】
以下、以上の本例のシステムによる処理の評価結果を説明する。
【００６０】
転送レートがｃ（ｂｐｓ）で時間長がＴ（秒）の単一種の動画コンテンツを考える。「Ｎ−Ｓ」個の各ユーザノードに対して、発生レートがλのポアソン過程により配信要求を発生させる。リンク負荷をｃで正規化し、λは、式「λ＝ρ×Ｍ÷｛Ｈ×（Ｎ−Ｓ）×Ｔ}」で定義する。
【００６１】
尚、上記式における「ρ」は単一フロー配信における各リンクの平均ふかであり、Ｍはリンク数である。また、「Ｈ」は、最近接サーバへの平均ホップ距離であり、式「Ｈ＝Σｉ∈Ｚ｛ｂｉ÷（Ｎ−Ｓ）｝」で定義される。この式において、「Ｚ」はユーザノード集合である。
【００６２】
以後の評価では、ρ＝１、Ｔ＝１２００秒とする。
【００６３】
選択したサーバに対して最短ホップ経路が複数存在する場合には、各配信要求に対して一つの経路がランダムに選択される。
【００６４】
図５（ａ），（ｂ）においては、５つのＳｔａｒ型ネットワークを対象に、各ストリーミング配信セッションにおける平均フロー数（各配信要求に対して選択されるサーバ数の平均値）を「Ｂ」に対して示す。
【００６５】
図５（ａ）では「ｓ＝０．１」、図５（ｂ）では「ｓ＝０．３」と設定した。ただし、結果を、「０≦Ｂ≦Ｂｍａｘ」の範囲で示している（「Ｂｍａｘ」は任意のユーザノードに対して全てのサーバが選択されるＢの最小の値）。
【００６６】
Ｓｔａｒ型ネットワークでは、ハブノードと他のノード間のホップ距離が短いため、全てのユーザノードは、２ホップ以内で全てのサーバノードに到達できる。
【００６７】
図８（ａ）において矢印で示すように、ＮＷ１２（ＧｏｏｄＮｅｔ）では、３つのハブノードの次数が極めて大きい。これらハブノード（スーパーハブノード）は、他の５８％〜６９％のノードと接続しており、多数のユーザノードは、２つか３つのスーパーハブノードと接続している。従って、ＮＷ１２では、各配信セッションの平均並列フロー数が大きい。
【００６８】
図５（ｃ），（ｄ）においては、スター型ネットワークを対象に、正規化平均リンク負荷を示す。ただし、この正規化平均リンク負荷は、並列フロー配信システム（ＰＤＳ： Ｐａｒａｌｌｅｌ Ｄｏｗｎｌｏａｄ Ｓｙｓｔｅｍ）における平均リンク負荷を、単一フロー配信システム（ＳＤＳ：Ｓｉｎｇｌｅ Ｄｏｗｎｌｏａｄ Ｓｙｓｔｅｍ）における平均リンク負荷で除したものと定義する。
【００６９】
配信要求の発生レートは固定されているため、平均リンク負荷はフローの平均ホップ長に比例する。ＳＤＳでは最近接サーバが常に選択されるため、ＳＤＳにおける平均リンク負荷は、与えられた網トポロジとサーバ配置位置に対して最小となる。よって正規化平均リンク負荷は常に１以上の値をとる。
【００７０】
「Ｂ」の増加に伴い、ＰＤＳにおけるフローの平均ホップ長が増加するため、平均リンク負荷も増加する。
【００７１】
さらに、リンク負荷のＣＶの正規化値（ＰＤＳのリンク負荷のＣＶをＳＤＳのリンク負荷のＣＶで除した値）を図５（ｅ），（ｆ）に示す。
【００７２】
この値が「１」より小さい場合に、ＰＤＳがＳＤＳと比較してリンク負荷のＣＶが低減することを意味する。
【００７３】
ＮＷ１２を除いた４つのＳｔａｒ型ネットワークでは、少数のハブノードが存在し、他の多くのノードはこれらハブノードの１つと接続している。
【００７４】
図５（ｅ）に示すように、ｓ＝０．１のとき、サーバはこれら少数のハブノードにのみ設置され、「Ｂ」を１以上に設定すると、多くのフローは、ハブノード間に設置されたリンクを経由する結果、ＰＤＳにおいてリンク負荷のＣＶが増加する。
【００７５】
それに対してＮＷ１２では、多くのノードは２つか３つのスーパーハブノードと接続しており、スーパーハブノード間に設置されたリンクへの負荷の集中が回避される。
【００７６】
図６においては、６つのＨ＆Ｓ型ネットワークに対する三つの特性について同様に示す。
【００７７】
Ｈ＆Ｓ型ネットワークにおいても、多数のノードはサーバノード（ハブノード）に短いホップ距離で到達できるため、「Ｂ」を２以下に設定した場合でも配信時の並列フロー数を高めることが可能である。
【００７８】
さらに、Ｈ＆Ｓ型ネットワークではハブノードが多数存在し、それらは相互接続している傾向がある。そのため、「Ｂ」を１以上に設定した場合でも、ハブノード間の特定のリンクへの負荷集中は回避され、リンク負荷のＣＶは低減する。
【００７９】
総ノード数Ｎの大きなネットワークほど、「Ｂ」を１以上に設定した場合の並列フロー数がより大きくなり、リンク負荷のＣＶの低減度合いも大きくなる。
【００８０】
図７においては、１２のＬａｄｄｅｒ型ネットワークに対してこれら三つの特性を同様に示す。
【００８１】
Ｌａｄｄｅｒ型ネットワークではノード間の平均距離が大きいため、各ストリーミング配信の並列フロー数を十分に高めるためには「Ｂ」を大きな値に設定する必要がある。
【００８２】
「Ｂ」を大きくしたときのＬａｄｄｅｒ型ネットワークのフローの平均ホップ長の増加度合いは大きいため、Ｌａｄｄｅｒ型ネットワークの正規化平均リンク負荷はＳｔａｒ型やＨ＆Ｓ型のそれに比べて大きい。尚、Ｌａｄｄｅｒ型ネットワークにおいても、リンク負荷のＣＶはＰＤＳにより低減する。
【００８３】
以上の説明をまとめると、ＮＷ１２を除き、Ｓｔａｒ型ネットワークにおいて少数のサーバのみを設置した場合、ＰＤＳを用いるメリットはない。
【００８４】
Ｓｔａｒ型ネットワークにおいて３割程度のノードにサーバを設置した場合や、Ｈ＆Ｓ型やＬａｄｄｅｒ型ネットワークにおいては、ＰＤＳを用い、さらに最近接ノード以外にホップ数の長いサーバも配信に用いた場合、リンク負荷のＣＶは低減する反面、平均リンク負荷が増加する。
【００８５】
よって、ＰＤＳにおいて最近接サーバ以外のサーバも含めて並列配信を行う明確なメリットは見出せない。
【００８６】
ただし、「Ｂ＝０」に設定し、最近接サーバのみを並列配信に用いる場合には、平均リンク負荷の増加を避けながらリンク負荷のＣＶを低減させることが可能であり、ＰＤＳを用いる明確なメリットが見出せる。
【００８７】
しかし、この場合、ＰＤＳの効果は各ユーザノードに対して最近接サーバがいくつ存在するかに依存する。このことを確認するため、図９に、「Ｂ＝０」と設定したときのリンク負荷のＣＶの正規化値を最近接サーバ数比率ηに対して示す。
【００８８】
ただしηは、式「η＝｛Σｉ∈Ｚｘｉ（ｂｉ）｝÷｛（Ｎ−Ｓ）×Ｓ｝」で定義する。この式における「ｘｉ（ｂｉ）」は、ユーザノードｉにおける最近接サーバ（ノードｉからのホップ距離がｂｉのサーバノード）の数である。
【００８９】
これら二つの尺度間には負の相関が確認できる。すなわち、ηが大きなネットワークほどＰＤＳが有効となる。
【００９０】
ηに関して、Ｓｔａｒ型、Ｈ＆Ｓ型、Ｌａｄｄｅｒ型といったネットワーク種別による明確な違いは見られない。
【００９１】
ＮＷ１２（ＧｏｏｄＮｅｔ）はηが大きく、最近接サーバのみを用いて並列配信を行ってもリンク負荷のＣＶの低減効果が顕著に見られる。これは前述したように、ＮＷ１２では、多数のユーザノードが２つか３つのスーパーハブノードと接続していることが原因である。
【００９２】
ＮＷ１７（Ｓａｖｖｉｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）とＮＷ１９（Ｓｐｒｉｎｔ）もηが大きいが、リンク負荷のＣＶの低減効果は限定的である。
【００９３】
ＮＷ１７とＮＷ１９では最大ノード次数が各々１０と８であり、ハブノードは４０％程度以下の他のノードと接続しているのみである。
【００９４】
これらネットワークでは、ＮＷ１２で見られたようなスーパーハブノードが存在せず、リンク負荷のＣＶの低減効果は限定的となっている。図８（ｂ），（ｃ）に、これら二つのネットワーク（ＮＷ１７とＮＷ１９）を示す。
【００９５】
よって、ＮＷ１７のように、ほとんどのノードを接続するスーパーハブノードが２つ以上存在し、かつ、そのようなスーパーハブノードにサーバが設置された場合には、動画ストリーミングサービスを並列配信で提供することにより平均リンク負荷の増加を避けながらリンク負荷の偏りを大きく低減することが可能となる。
【００９６】
次に、図１０を用いて、図１におけるデータ並列配信システムによる本発明に係る処理動作例を説明する。
【００９７】
まず、ネットワークトポロジ設計装置１０１により、ネットワークを構成する各ノードの接続関係を示すトポロジ情報を生成し記憶装置に格納する手順を実行する（ステップＳ１００１）。
【００９８】
次に、サーバ配置設計装置１０２により、トポロジ情報を記憶装置から読み出して参照し、各ノード間の平均ホップ長を算出する手順と、算出した平均ホップ長が小さいノードを優先して、データを並列配信するサーバ機能を設置するサーバノードとして選択する手順とを実行する（ステップＳ１００２）。尚、この際、サーバ機能を設置するサーバノードとして、予め定められた個数だけ選択する。
【００９９】
そして、サーバ選択装置１０４により、データの配信要求に対して当該データを配信するサーバノードを選択する際、ホップ長の最も短い最近接のサーバノードを選択する手順と、この最近接サーバのホップ数に予め定められたホップ数を加えたホップ長以内のサーバノードも加えて選択する手順とを実行する（ステップＳ１００３）。
【０１００】
以上、図１〜図１０を用いて説明したように、本例では、ネットワークにおけるデータの並列配信を行う際、ネットワークトポロジ設計装置１０１により、ネットワークを構成する各ノードの接続関係を示すトポロジ情報を生成し、サーバ配置設計装置１０２により、このトポロジ情報を参照して各ノード間の平均ホップ長を算出し、算出した平均ホップ長が小さいノードを優先して、データを並列配信するサーバ機能を設置する。
【０１０１】
その際、サーバ配置設計装置１０２は、サーバ機能を設置するサーバノードとして、予め定められた個数だけ選択する。
【０１０２】
また、サーバ選択装置１０４において、ユーザ端末１０５からのネットワークを介してのデータの配信要求に対して当該データを配信するサーバノードを選択する際、ホップ長の最も短い最近接のサーバノードを選択すると共に、この最近接サーバのホップ数に予め定められたホップ数を加えたホップ長以内のサーバノードも加えて選択する。
【０１０３】
また、サーバ配置設計装置１０２は、予め定められた割合以上で他のノードと接続されているスーパーハブノードを抽出し、抽出したスーパーハブノードにサーバ機能を設置する。
【０１０４】
また、ネットワークトポロジ設計装置１０１は、トポロジ情報を記憶装置から読み出して参照し、当該ネットワークをＳｔａｒ型、Ｈ＆Ｓ型、Ｌａｄｄｅｒ型のいずれかとして分類し、サーバ配置設計装置１０２は、Ｓｔａｒ型およびＨ＆Ｓ型に分類したネットワークであれば、当該ネットワークを構成する各ノードの内、最も次数の高いノードをサーバノードとして選択する。
【０１０５】
また、サーバ配置設計装置１０２は、平均ホップ長が小さく、かつ、当該ネットワークの中心に位置するノードをサーバノードとして選択する。
【０１０６】
また、サーバ配置設計装置１０２は、ネットワークの中心に位置するノードとして、全ノード数Ｎと、ノードｉからノードｊへの最短ホップ経路上のホップ数ｈｉｊとを用いた式「Ｈｉ＝（Ｎ−１）÷（ΣＮｊ＝１，ｊ≠ｉｈｉｊ）」で定義される中心性を表す尺度Ｈｉが最も大きいノードを選択する。
【０１０７】
このことにより、本例によれば、動画ストリーミング配信において、１つの配信要求に対して、要求された動画コンテンツが保存されている複数のサーバを用いて動画データを並列にダウンロードする配信形態において、配信フローの平均ホップ長を抑えつつ、リンク負荷の偏りを低減する効果を得ることができる。これにより、複数のサーバを用いたデータの並列配信を効率的に行うことができ、ＨＤＴＶやＵＨＤＶ等の超高画質の動画ストリーミングのネットワーク配信サービスの実現が可能となる。
【０１０８】
尚、本発明は、図１〜図１０を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、本発明に係る処理手順を実行するコンピュータ装置として、ネットワークトポロジ設計装置１０１、サーバ配置設計装置１０２、ビデオサーバ１０３、サーバ選択装置１０４のそれぞれを個別に設けた構成としているが、各々の機能を１つのコンピュータ装置内に設けた構成としても良い。
【０１０９】
また、本例のコンピュータ装置の構成としては、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【図面の簡単な説明】
【０１１０】
【図１】本発明に係るデータ並列配信システムの構成例を示すブロック図である。
【図２】図１におけるデータ並列配信システムを適用するバックボーンネットワークを構成する各ネットワークの一覧を示す説明図である。
【図３】図２における各ネットワークの分類例を示す説明図である。
【図４】本発明を適用するネットワークの第１のトポロジ例を示す説明図である。
【図５】本発明を適用するＳｔａｒ型ネットワークの特性例を示す説明図である。
【図６】本発明を適用するＨ＆Ｓ型ネットワークの特性例を示す説明図である。
【図７】本発明を適用するＬａｄｄｅｒ型ネットワークの特性例を示す説明図である。
【図８】本発明を適用するネットワークの第２のトポロジ例を示す説明図である。
【図９】本発明の作用結果を示す説明図である。
【図１０】本発明に係るデータ並列配信方法の処理手順例を示すフローチャートである。
【符号の説明】
【０１１１】
１０１：ネットワークトポロジ設計装置、１０２：サーバ配置設計装置、１０３：ビデオサーバ、１０４：サーバ選択装置、１０５：ユーザ端末。
【特許請求の範囲】
【請求項１】
プログラムされたコンピュータ処理により、ネットワークにおけるデータの並列配信を行う方法であって、
プログラムされたコンピュータの処理実行手順として、
ネットワークを構成する各ノードの接続関係を示すトポロジ情報を生成し記憶装置に格納する手順と、
上記トポロジ情報を記憶装置から読み出して参照し、各ノード間の平均ホップ長を算出する手順と、
算出した平均ホップ長が小さいノードを優先して、データを並列配信するサーバ機能を設置するサーバノードとして選択する手順と
を含むことを特徴とするデータ並列配信方法。
【請求項２】
請求項１に記載のデータ並列配信方法であって、
プログラムされたコンピュータの処理実行手順として、
上記サーバ機能を設置するサーバノードとして、予め定められた個数だけ選択する手順を含むことを特徴とするデータ並列配信方法。
【請求項３】
請求項１もしくは請求項２のいずれかに記載のデータ並列配信方法であって、
プログラムされたコンピュータの処理実行手順として、
データの配信要求に対して当該データを配信するサーバノードを選択する際に、
ホップ長の最も短い最近接のサーバノードを選択する手順と、
該最近接サーバのホップ数に予め定められたホップ数を加えたホップ長以内のサーバノードも加えて選択する手順と
を含むことを特徴とするデータ並列配信方法。
【請求項４】
請求項１から請求項３のいずれかに記載のデータ並列配信方法であって、
プログラムされたコンピュータの処理実行手順として、
予め定められた割合以上で他のノードと接続されているスーパーハブノードを抽出する手順と、
抽出したスーパーハブノードに上記サーバ機能を設置する手順と
を含むことを特徴とするデータ並列配信方法。
【請求項５】
請求項１から請求項４のいずれかに記載のデータ並列配信方法であって、
プログラムされたコンピュータの処理実行手順として、
上記トポロジ情報を記憶装置から読み出して参照し、当該ネットワークをＳｔａｒ型、Ｈ＆Ｓ型、Ｌａｄｄｅｒ型のいずれかとして分類する手順と、
Ｓｔａｒ型およびＨ＆Ｓ型に分類したネットワークであれば、当該ネットワークを構成する各ノードの内、最も次数の高いノードを上記サーバノードとして選択する手順と
を含むことを特徴とするデータ並列配信方法。
【請求項６】
請求項１から請求項５のいずれかに記載のデータ並列配信方法であって、
プログラムされたコンピュータの処理実行手順として、
上記平均ホップ長が小さく、かつ、当該ネットワークの中心に位置するノードを上記サーバノードとして選択する手順
を含むことを特徴とするデータ並列配信方法。
【請求項７】
請求項６に記載のデータ並列配信方法であって、
プログラムされたコンピュータの処理実行手順として、
上記ネットワークの中心に位置するノードとして、全ノード数Ｎと、ノードｉからノードｊへの最短ホップ経路上のホップ数ｈｉｊとを用いた式「Ｈｉ＝（Ｎ−１）÷（ΣＮｊ＝１，ｊ≠ｉｈｉｊ）」で定義される中心性を表す尺度Ｈｉが大きなノードから優先的に選択する手順
を含むことを特徴とするデータ並列配信方法。
【請求項８】
コンピュータに、請求項１から請求項７のいずれかに記載のデータ並列配信方法における各手順を実行させるためのプログラム。
【請求項９】
プログラムされたコンピュータ処理により、ネットワークにおけるデータの並列配信を行うシステムであって、
プログラムされたコンピュータ処理実行手段として、
請求項１から請求項７のいずれかに記載のデータ並列配信方法における各手順を実行する手段を具備したことを特徴とするデータ並列配信システム。
【請求項１】
プログラムされたコンピュータ処理により、ネットワークにおけるデータの並列配信を行う方法であって、
プログラムされたコンピュータの処理実行手順として、
ネットワークを構成する各ノードの接続関係を示すトポロジ情報を生成し記憶装置に格納する手順と、
上記トポロジ情報を記憶装置から読み出して参照し、各ノード間の平均ホップ長を算出する手順と、
算出した平均ホップ長が小さいノードを優先して、データを並列配信するサーバ機能を設置するサーバノードとして選択する手順と
を含むことを特徴とするデータ並列配信方法。
【請求項２】
請求項１に記載のデータ並列配信方法であって、
プログラムされたコンピュータの処理実行手順として、
上記サーバ機能を設置するサーバノードとして、予め定められた個数だけ選択する手順を含むことを特徴とするデータ並列配信方法。
【請求項３】
請求項１もしくは請求項２のいずれかに記載のデータ並列配信方法であって、
プログラムされたコンピュータの処理実行手順として、
データの配信要求に対して当該データを配信するサーバノードを選択する際に、
ホップ長の最も短い最近接のサーバノードを選択する手順と、
該最近接サーバのホップ数に予め定められたホップ数を加えたホップ長以内のサーバノードも加えて選択する手順と
を含むことを特徴とするデータ並列配信方法。
【請求項４】
請求項１から請求項３のいずれかに記載のデータ並列配信方法であって、
プログラムされたコンピュータの処理実行手順として、
予め定められた割合以上で他のノードと接続されているスーパーハブノードを抽出する手順と、
抽出したスーパーハブノードに上記サーバ機能を設置する手順と
を含むことを特徴とするデータ並列配信方法。
【請求項５】
請求項１から請求項４のいずれかに記載のデータ並列配信方法であって、
プログラムされたコンピュータの処理実行手順として、
上記トポロジ情報を記憶装置から読み出して参照し、当該ネットワークをＳｔａｒ型、Ｈ＆Ｓ型、Ｌａｄｄｅｒ型のいずれかとして分類する手順と、
Ｓｔａｒ型およびＨ＆Ｓ型に分類したネットワークであれば、当該ネットワークを構成する各ノードの内、最も次数の高いノードを上記サーバノードとして選択する手順と
を含むことを特徴とするデータ並列配信方法。
【請求項６】
請求項１から請求項５のいずれかに記載のデータ並列配信方法であって、
プログラムされたコンピュータの処理実行手順として、
上記平均ホップ長が小さく、かつ、当該ネットワークの中心に位置するノードを上記サーバノードとして選択する手順
を含むことを特徴とするデータ並列配信方法。
【請求項７】
請求項６に記載のデータ並列配信方法であって、
プログラムされたコンピュータの処理実行手順として、
上記ネットワークの中心に位置するノードとして、全ノード数Ｎと、ノードｉからノードｊへの最短ホップ経路上のホップ数ｈｉｊとを用いた式「Ｈｉ＝（Ｎ−１）÷（ΣＮｊ＝１，ｊ≠ｉｈｉｊ）」で定義される中心性を表す尺度Ｈｉが大きなノードから優先的に選択する手順
を含むことを特徴とするデータ並列配信方法。
【請求項８】
コンピュータに、請求項１から請求項７のいずれかに記載のデータ並列配信方法における各手順を実行させるためのプログラム。
【請求項９】
プログラムされたコンピュータ処理により、ネットワークにおけるデータの並列配信を行うシステムであって、
プログラムされたコンピュータ処理実行手段として、
請求項１から請求項７のいずれかに記載のデータ並列配信方法における各手順を実行する手段を具備したことを特徴とするデータ並列配信システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２００９−２１２８８１（Ｐ２００９−２１２８８１Ａ）
【公開日】平成２１年９月１７日（２００９．９．１７）
【国際特許分類】
【出願番号】特願２００８−５４３２１（Ｐ２００８−５４３２１）
【出願日】平成２０年３月５日（２００８．３．５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２１年９月１７日（２００９．９．１７）
【国際特許分類】
【出願日】平成２０年３月５日（２００８．３．５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]