(57)【要約】      （修正有）【課題】輻輳を回避させるためには、超高精細コンテンツのストリーミング配信に際しては、リンク負荷を効果的に分散させて、「リンク使用率」を平準化することで、ネットワークスループットを向上させる。【解決手段】ネットワーク上に複数のミラーサーバを配置し、各配信要求に対して配信に複数のサーバ用いることで各フローの転送ビットレートを低減するデータ並列配信システムにおいて、サーバ配置設計装置１０２とサーバ選択設計装置１０３を設け、最大リンク使用率を最小化するよう、サーバを配置するノードの選択を行う。これにより、ネットワーク全体で収容可能な総配信要求量（ネットワークスループット）を最大化する。【選択図】図１
2010268126.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上に配置された複数のサーバから配信先のノードにデータを並列配信するデータ並列配信システムであって、
プログラムされたコンピュータ処理を実行する手段として、
データ配信に用いる各サーバを配置するノードを、各ノード間の各リンクの最大使用率（最大リンク使用率）が最小となるよう選択するサーバ配置選択手段を有する
ことを特徴とするデータ並列配信システム。
【請求項２】
請求項１に記載のデータ並列配信システムであって、
上記サーバ配置選択手段は、
上記ネットワーク内の各ノード間の各リンクの最大リンク使用率を求め、
求めた最大リンク使用率が小さい順に予め定められたＳ個のノードを特定し、
該特定したＳ個のノードを、上記サーバを設置するノードとして選択する
ことを特徴とするデータ並列配信システム。
【請求項３】
請求項２に記載のデータ並列配信システムであって、
上記サーバ配置選択手段は、
最大使用率のリンクを配信フローが経由する配信先ノードに対して用いるサーバを他のサーバに置き換えた場合の最大リンク使用率が最小となるサーバ置き換えを順次実施することで、
上記Ｓ個のノードに配置された各サーバから、
配信先ノードとの上記最大リンク使用率が最小となるノードに配置されたサーバを１つだけ、配信先ノードに対する配信元サーバとして選択する
ことを特徴とするデータ並列配信システム。
【請求項４】
請求項２もしくは請求項３のいずれかに記載のデータ並列配信システムであって、
上記サーバ配置選択手段は、
最大使用率のリンクを配信フローが経由する配信先ノードに対して用いるサーバの集合に新たにサーバを一つ追加した場合の最大リンク使用率が最小となる使用サーバの追加を順次実施することで、
上記Ｓ個のノードに配置された各サーバから、配信先ノードへの並列配信に用いる複数のサーバを、上記配信先ノードとの上記最大リンク使用率が最小化するよう選択する
ことを特徴とするデータ並列配信システム。
【請求項５】
ネットワーク上に配置された複数のサーバから配信先のノードにデータを並列配信するデータ並列配信システムにおけるサーバの配置と選択を、プログラムされたコンピュータ装置によって行う方法であって、
プログラムされたコンピュータ装置による処理実行手順として、
請求項１から請求項４のいずれかに記載のデータ並列配信システムにおける上記サーバ配置選択手段が実行する処理手順を含むことを特徴とするデータ並列配信方法。
【請求項６】
コンピュータを、請求項１から請求項４のいずれかに記載のデータ並列配信システムにおけるサーバ配置選択手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット等のネットワークにおいて動画のストリーミングデータ等を配信する際に、配信サーバの負荷を分散するために１本の動画を複数のサーバを用いて並列的に配信する技術に係り、特に、ネットワーク内のノードにどのように配信サーバを配置すれば効率的な負荷分散が実現できるかを決定するのに好適な技術に関するものである。
【背景技術】
【０００２】
近年、ＹｏｕＴｕｂｅ（登録商標）等の動画ストリーミングサービスをインターネット上で利用するユーザが急増している。高品質な動画配信に対するユーザの要望は高く、将来、約２５Ｍｂｐｓのビットレートを有するＨＤＴＶ（Ｈｉｇｈ  Ｄｅｆｉｎｉｔｉｏｎ  ＴＶ）の視聴がインターネット上でも可能になると思われる。また、さらに品質を向上させたＵＨＤＶ（Ｕｌｔｒａ  Ｈｉｇｈ  Ｄｅｆｉｎｉｔｉｏｎ  Ｖｉｄｅｏ）が日本放送協会により提案されている。
【０００３】
ＵＨＤＶの画像の非圧縮時のビットレートは２４Ｇｂｐｓであり、圧縮後も１８０〜６００Ｍｂｐｓの高いレートを有する。
【０００４】
このようなＨＤＴＶやＵＨＤＶ等を用いた超高精細コンテンツの動画ストリーミングサービスは、インターネットにおける重要なサービスの一つになると思われる。しかし、生成されるトラヒックフローの伝送レートは非常に高く、サーバやリンクの輻輳を招く要因となる。
【０００５】
以下、ネットワーク（ＮＷ）全体で運ぶことができる発着ノード間の総トラヒックデマンド量の最大値をＮＷスループットと定義し、ネットワークにおける輻輳について説明する。
【０００６】
特定の「リンクの使用率」が、他のリンクの使用率と比較して突出して高い場合、そのリンクがボトルネックとなり、多数のリンクが低い使用率で留まる結果、ＮＷスループットが低くなり輻輳を招くことになる。
【０００７】
このような輻輳を回避させるためには、超高精細コンテンツのストリーミング配信に際しては、リンク負荷を効果的に分散させて、「リンク使用率」を平準化することが重要である。
【０００８】
インターネットの標準的なＡＳ（Ａｕｔｏｎｏｍｏｕｓ  Ｓｙｓｔｅｍ）内ルーティングプロトコルであるＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）では、シスコ社の推奨値であるリンク容量の逆数や、全リンクに対して同一の固定値をリンク重みに設定した、最小コスト経路が一般に用いられる。
【０００９】
しかし、ＯＳＰＦでは、いずれの場合も、「リンク使用率」とは無関係な値をリンク重みに用いるため、経路設定によりリンク負荷を平準化することができない。
【００１０】
静的に与えた交流デマンド行列に対して、「最大リンク使用率を最小化する」ようリンク重みを最適設計する技術も提案されているが、インターネット上で提供される全てのサービスを対象に、交流デマンド行列を事前に推定することが難しく、普及するに至っていない。
【００１１】
また、「リンク使用率が平準化される」よう、各発着ノード間の経路を最適設定するトラヒックエンジニアリングが広く検討されているが、管理すべき経路数がノード数の自乗に比例して増加することや、ＮＷ内の全てのルータが発着ノードペアごとに経路を切り替える機能を実装する必要があること等の理由から、普及するに至っていない。そのため、コンテンツの配信経路を制御することでリンク負荷分散を図ることは困難である。
【００１２】
ところで、サーバの負荷分散を図る効果的な技術として、例えば、非特許文献１等に記載のＣＤＮ（Ｃｏｎｔｅｎｔ  Ｄｅｌｉｖｅｒｙ  Ｎｅｔｗｏｒｋ）が広く知られている。
【００１３】
このＣＤＮは、ＩＳＰ（Ｉｎｔｅｒｎｅｔ  Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｅｒ）とは独立したＣＤＮ事業者が、複数のＩＳＰのＮＷ上に多数のサーバを用意し、コンテンツのコピーをこれらサーバに配置することで、複数のサーバ間で負荷を分散させる。
【００１４】
しかし、ＣＤＮは、ＩＳＰとは独立したＣＤＮ事業者がサーバの設置運営を行うため、ＮＷトポロジや経路といったＮＷ情報を活用することができず、ＮＷのリンク使用率を平準化することが困難である。
【００１５】
また、ＣＤＮは、各配信要求に対して、常に、一つのサーバを選択するため、生成される個々の配信フローのビットレートを低減することはできず、ＮＷ情報を利用できたとしても、リンク使用率の平準化効果は限定的である。
【００１６】
「リンク使用率を平準化する」ためには、超高精細コンテンツのストリーミング配信フローのビットレートを低減することが重要となる。そのためには各配信要求に対して、複数のサーバを用いて並列配信を行うことが有効である。
【００１７】
例えば、二つのサーバを一本の配信セッションに用いることにより、生成される各フローの転送レートを半分に抑えることができる。
【００１８】
Ｐ２Ｐファイル共有サービスである「ＢｉｔＴｏｒｒｅｎｔ」（登録商標）も、このような並列配信技術を用いているが、各ユーザは、配信を受ける間、他のユーザにデータセグメントをアップロードする必要がある。
【００１９】
そのため、ＢｉｔＴｏｒｒｅｎｔ（登録商標）の性能は、ユーザの行動や、上り方向のアクセス回線レートに大きく依存する。しかし、超高精細コンテンツの配信ビットレートは極めて大きく、大容量の上りアクセスリンクを有するユーザが多数、これらサービスを安定的に利用することは期待できない。
【００２０】
そのため、ＢｉｔＴｏｒｒｅｎｔ（登録商標）等のＰ２Ｐファイル共有システム上で、超高精細ストリーミング配信を提供することは困難である。
【００２１】
これらサービスのフローがＮＷに与える影響を緩和し、リンク使用率を平準化し、ＮＷスループットを向上させるためには、ＮＷトポロジ等のＮＷ情報を利用可能なＩＳＰが自身のＮＷ上に複数のサーバを設置し、複数のサーバから並列配信を行う必要がある。
【先行技術文献】
【非特許文献】
【００２２】
【非特許文献１】Ａ．Ｓｕ，  Ｄ．Ｃｈｏｆｆｎｅｓ，  Ａ．Ｋｕｚｍａｎｏｖｉｃ，  ａｎｄ  Ｆ．Ｂｕｓｔａｍａｎｔｅ，“Ｄｒａｆｔｉｎｇ  Ｂｅｈｉｎｄ  Ａｋａｍａｉ  （Ｔｒａｖｅｌｏｃｉｔｙ−Ｂａｓｅｄ  Ｄｅｔｏｕｒｉｎｇ）”，  ＡＣＭ  ＳＩＧＣＯＭＭ  ２００６．
【発明の概要】
【発明が解決しようとする課題】
【００２３】
並列配信に関しては、例えば、本願発明者等による特願２００８−０５４３２１号に記載のものがある。この技術では、例えば、動画ストリーミング配信において、１つの配信要求に対して、要求された動画コンテンツが保存されている複数のサーバを用いて動画データを並列にダウンロードする配信形態において、配信フローの平均ホップ長が短くなるよう、他のノードへの平均ホップ長が小さいノードに優先的にサーバを配置する。
【００２４】
また、各配信要求に対して、ホップ長の最も短い最近接サーバに加えて、そのホップ数からプラスＢホップ以内の位置に存在するサーバをも配信サーバとして選択する。さらに、並列配信の効果を高めるために、他の大部分のノードと接続するスーパーハブノードを複数ネットワーク内に配置し、それらスーパーハブノードにサーバを設置する。
【００２５】
これにより、データの並列配信における配信フローの平均ホップ長を抑えつつ、リンク負荷の偏りを低減することができる。
【００２６】
このように、上述の特願２００８−０５４３２１号に記載の技術では、配信サーバを選択する際の評価尺度として、「平均リンク負荷」と「リンク負荷の変動係数」を用いている。
【００２７】
しかし、ＮＷスループットは、最大リンク使用率で決まることから、最大リンク使用率を最小化してリンク使用率を平準化することが重要であるが、上述の特願２００８−０５４３２１号に記載の技術では、「リンク使用率」に関しては考慮していない。
【００２８】
解決しようとする問題点は、従来の技術では、例えば、超高精細コンテンツのストリーミング等のデータを並列配信するサーバの配置と選択に、リンク使用率を考慮していない点である。
【００２９】
本発明の目的は、これら従来技術の課題を解決し、データの並列配信を行うサーバの配置と選択を、最大リンク使用率を最小化してリンク使用率を平準化することで、ＮＷスループットを大幅に向上させることである。
【課題を解決するための手段】
【００３０】
上記目的を達成するため、本発明では、例えば、動画ストリーミング配信において、１つの配信要求に対して、要求された動画コンテンツが保存されている複数のサーバを用いて動画データを並列にダウンロードする配信形態において、最大リンク使用率を最小化することで、ＮＷスループット（ネットワーク全体で収容可能な総配信要求量）を最大化するように、サーバを配置するノードを選択することを特徴とする。
【発明の効果】
【００３１】
本発明によれば、データの並列配信を行うサーバの配置と選択を、最大リンク使用率を最小化するよう行うことで、ＮＷスループット（ネットワーク全体で収容可能な総配信要求量）を大幅に向上させることが可能となる。
【図面の簡単な説明】
【００３２】
【図１】本発明に係るデータ並列配信システムの構成例を示すブロック図である。
【図２】図１におけるサーバ配置設計装置の本発明に係る処理手順例を示すアルゴリズムである。
【図３】図１におけるサーバ選択設計装置の本発明に係る第１の処理手順例を示すアルゴリズムである。
【図４】図１におけるサーバ選択設計装置の本発明に係る第２の処理手順例を示すアルゴリズムである。
【図５】本発明に係るデータ並列配信システムの処理対象となるネットワークのトポロジ別のノード次数の散布状態を示す説明図である。
【図６】本発明に係るデータ並列配信システムの処理対象となるネットワークのトポロジ例を示す説明図である。
【図７】本発明に係るデータ並列配信システムの処理対象となる各ネットワークの特性例を示す説明図である。
【図８】本発明に係るデータ並列配信システムによる処理の第１の効果例を示す説明図である。
【図９】本発明に係るデータ並列配信システムによる処理の第２の効果例を示す説明図である。
【図１０】本発明に係るデータ並列配信システムによる処理の第３の効果例を示す説明図である。
【図１１】本発明に係るデータ並列配信システムによる処理の第４の効果例を示す説明図である。
【図１２】本発明に係るデータ並列配信システムの処理対象となるバックボーンネットワークの一覧を示す説明図である。
【発明を実施するための形態】
【００３３】
以下、図を用いて本発明を実施するための形態例を説明する。図１においては、本発明に係るデータ並列配信システムの構成例を示しており、１０１は本発明係る各入力条件データ（サーバ設置数Ｓ、ＮＷトポロジＴ、各ノードの配信要求量比Ｒｎ、各リンクの伝送容量Ｃｅ、各リンクのコストｃｅ）を入力するための入力データ設定装置、１０２はＳ個のサーバを配置するノードを選択するサーバ配置設計装置、１０３はデータの並列配信に用いるサーバを選択するサーバ選択設計装置、１０４はサーバ配置設計装置１０２とサーバ選択設計装置１０３の処理結果を出力する設計結果出力装置である。
【００３４】
図１におけるデータ並列配信システムは、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）や主メモリ等を具備したコンピュータ構成からなり、プログラムされたコンピュータ処理を実行する手段として、入力データ設定装置１０１とサーバ配置設計装置１０２およびサーバ選択設計装置１０３と設計結果出力装置１０４のそれぞれを具備している。尚、サーバ選択設計装置１０３と設計結果出力装置１０４は、本発明に係るサーバ配置選択手段を構成するものである。
【００３５】
入力データ設定装置１０１は、図示していないキーボードやマウス等の操作あるいはデータ通信装置等の入力装置を介して入力される、設置サーバ数Ｓ、ＮＷトポロジＴ、各ノードの配信要求量比Ｒｎ、各リンクの伝送容量Ｃｅ、各リンクのコストｃｅ等の各入力データを取得し、図示していない記憶装置に格納する。
【００３６】
ＮＷトポロジＴは、ノード数Ｎの規模の行列で表され、その要素ｉｊ（トポロジ行列Ｔにおける第ｉ行目第ｊ列目の行列要素であり、ノードｉとノードｊとを結ぶリンク位置）は、ノードｉとノードｊの間にリンクが存在する場合に「１」を、存在しない場合に「０」をとる２値変数である。
【００３７】
ノードｎの配信要求量比Ｒｎは、ノードｎから生じる配信要求量の、ＮＷ全体で発生する配信要求量に占める割合を表し、０．０５等の値をとる。
【００３８】
各リンクのコストｃｅは、経路設定の際に用いられる重みであり、例えば、最小ホップ経路を用いる場合には「１」を、また大容量リンクを積極的に経由するよう経路を設定する場合にはリンク容量の逆数が設定される。
【００３９】
サーバ配置設計装置１０２は、入力データを用いて、各ノードに対して経由リンクのコスト和が最小となるサーバを一つだけ用いる場合に、最大リンク使用率が最小となるようＳ個のサーバを配置するノードを特定する。
【００４０】
サーバ選択設計装置１０３は、各ノードに対して複数のサーバを配信に用いる場合に、最大リンク使用率が最小となるよう、要求されたデータの配信に用いるサーバ集合を特定する。
【００４１】
設計結果出力装置１０４は、サーバ配置設計装置１０２によるＳ個のサーバを配置するノードの特定結果、および、サーバ選択設計装置１０３によるデータ配信用のサーバ集合の特定結果を、表示装置や記憶装置あるいはデータ通信装置等を介して出力する。
【００４２】
このような構成により、図１におけるデータ並列配信システムは、例えば、動画ストリーミングの配信要求に対して、要求された動画コンテンツが保存されている複数のサーバを用いて動画データを並列にダウンロードする配信形態において、最大リンク使用率を最小化することで、ＮＷスループット（ネットワーク全体で収容可能な総配信要求量）を最大化するように、サーバを配置するノードを選択する。
【００４３】
以下、このように、ＮＷスループットを最大化するためのコンテンツ並列配信技術について、［前提条件］、［最適サーバ配置設計法］、［最適サーバ選択設計法］、［評価結果］の順に、詳細を説明する。
【００４４】
まず、［前提条件］について説明する。
［前提条件］：
ＮＷのノード数をＮ、双方向のリンク数をＭとし、リンクｅの伝送容量をＣｅとする。
【００４５】
Ｎのノード中Ｓ個のノードにミラーサーバが配置され、これらＳ個のミラーサーバには全ての超高精細コンテンツのコピーが用意されることを想定する。そのため、配信システムの設計や評価を行う際に、コンテンツごとの要求発生比率について考慮する必要がなく、以後は単一のコンテンツの配信を対象に検討を進める。
【００４６】
経路設定法として、リンク重みを「１」に設定する場合（ｍｉｎ．ｈｏｐと表記）と、Ｃｉｓｃｏ（登録商標）社が推奨するリンク容量の逆数に設定する場合（ｉｎｖ．ｃａｐと表記）の二つの重み設定法に対して各々、ダイクストラの最小コスト経路を用いることを想定する。
【００４７】
尚、「ｍｉｎ．ｈｏｐ」は、最短ホップ経路を用いる場合に相当し、また、「ｉｎｖ．ｃａｐ」は容量の大きなリンクを積極的に用いる場合に相当する。
【００４８】
同一発着ノード間に最小コスト経路が複数存在する場合、これら複数の経路に均等にトラヒックを分割して流す形態もルータの実装上可能であるが、同一フローに属するパケットが異なる経路を通ると、受信端末においてソーティング等の余計な処理が必要となること、通信品質が安定しない等の理由から、現実にはルータのポートの識別番号が最も若い経路を選択する等、同一ノード間に対しては最小コスト経路が１本だけ用いられることが多い。
【００４９】
そこで、後述の「評価結果」では、ノードペアごとに経路をランダムに固定的に１本選択した評価を１００回反復し、その平均値で全て評価する。
【００５０】
ＮＷ全体の総トラヒック量、すなわちＮ個の全てのノードから発生する単位時間あたりのトラヒック需要量の平均をＶ（ｂｐｓ）とし、さらにノードｓからノードｄに対して発生する単位時間あたりの平均トラヒック量をｖｓｄ（ｂｐｓ）とする。また、ｖｓｄのＶに対する比率をｒｓｄとする（ｒｓｄ＝ｖｓｄ／Ｖ）。
【００５１】
平均トラヒック量ｖｓｄに加えて、ＮＷトポロジとリンク容量、そして経路設定のための静的なリンク重みが与えられると、各リンクｅの平均使用率ｕｅが次の数１に示す式により一意に定まる。
【００５２】
【数１】
2010268126.tif 000003
ただし、Ｎをノード集合、ｘ（ｓ，ｄ，ｅ）はノードｓからノードｄに至る配信経路がリンクｅを通る場合に「１」を、通らない場合に「０」をとる２値変数とする。
【００５３】
リンク使用率が最大となるリンクをεとする。経路と交流デマンド行列ｒｉｊ（ノードｉからノードｊに向かうトラヒック需要量）が与えられたとき、トラヒック需要量平均Ｖが変化しても、リンク使用率が最大となるリンクεは常に同一のリンクとなり、このリンクεは、ＮＷ全体で達成可能なトラヒック需要量平均Ｖの最大値Ｖｍａｘ（ＮＷスループット）を定めるボトルネックリンクとなる。
【００５４】
本例では、Ｖｍａｘを、上述の数１で示す式（１）において「ｕε＝１」となるときのトラヒック需要量平均Ｖの値と定義する。
【００５５】
各ノードｎから発生する配信要求量のＮＷ全体の配信要求量に対する比率をＲｎとする。本例では、この比率Ｒｎとして静的な値が与えられることを想定する。
【００５６】
一般に、インターネットにおいて生じる任意のサービスに対して、交流デマンド行列ｒｉｊを推定することは困難であるが、超高精細ストリーミング配信に限定された比率Ｒｎを推定することは比較的容易であると思われる。
【００５７】
ＩＳＰは、上述の比率Ｒｎを直接制御することはできないが、要求されたコンテンツが複数のサーバに存在する場合、ＩＳＰは交流デマンド行列ｒｉｊを、サーバ配置法とサーバ選択法によって制御することが可能である。
【００５８】
すなわち、経路を固定的なリンク重みを用いて静的に設定した場合でも、サーバ配置とサーバ選択を最適化することで、ＮＷスループットＶｍａｘの最適化が可能となる。
【００５９】
そこで、本例では、Ｖｍａｘを最大化する、すなわち最大リンク使用率を最小化する並列配信のためのサーバ配置設計法とサーバ選択法を検討する。
【００６０】
コンテンツの並列配信を行うに際しては、ＩＳＰは事前に自身のＮＷのノード集合に対して、複数のミラーサーバを配置する必要がある。
【００６１】
また、個々の配信要求に対して用いるサーバを選択する必要がある。
【００６２】
各リンクの使用率は、サーバ配置だけでなく、各配信セッションに対するサーバ選択法にも依存するため、並列配信時の最大リンク使用率が最小化するようサーバを配置設計するためには、サーバ配置とサーバ選択を同時に最適設計する必要がある。
【００６３】
しかし、組合せ数が膨大となり、現実的な時間で解を得ることが困難なことから、本例では、各々の設計問題を、［最適サーバ配置設計法］と［最適サーバ選択設計法］に分離して検討する。
【００６４】
まず、［最適サーバ配置設計法］について説明する。
［最適サーバ配置設計法］：
一般に、ノード間の転送コスト、ＮＷトポロジ、各ノードで発生するデマンド量、設置ノード数Ｋが与えられたときに、総転送コストを最小化するＫのファシリティ配置位置を選択する問題は、ＵＫＭ（Ｕｎｃａｐａｃｉａｔｅｄ  Ｋ−Ｍｅｄｉａｎ）として知られており、ＮＰ困難であるため、様々な近似解法が検討されている。
【００６５】
これら設計法では、総転送コストの最小化が目的となっているが、本例では、新たに、貪欲算法を用いた最大リンク使用率を最小化するサーバの近似最適配置法を検討する。
【００６６】
ｊ個のサーバがノード集合Ｎｊに配置された状態で、さらに、ノード集合Ｎｊに含まれない任意のノードｉにサーバを配置した場合の最大リンク使用率をｕｍａｘ（Ｎｊ，ｉ）とする。
【００６７】
リンク使用率を算出するためには、個々の配信に対して用いるサーバを便宜上定める必要があるため、配信コスト（経由リンクのコストの総和）が最小のサーバを一つ用いることを想定する。
【００６８】
すなわち、任意のノードｄに対して、サーバ集合Ｓ＝｛Ｎｊ＋ｉ｝に含まれる各サーバｓからの配信コストδｓｄが最小となるサーバがσであるとき、「ｒσｄ＝１」である一方、「ｓ≠σ」の全てのｓに対して「ｒｓｄ＝０」と設定する。
【００６９】
このとき、上述の数１で示す式（１）より各リンクの使用率を算出し、その最大値ｕｍａｘ（Ｎｊ，ｉ）が得られる。ただし、ネットワーク全体の総トラヒック量Ｖの値は、使用率が最大となるリンクを求めるときには無関係であるため「Ｖ＝１」に設定する。
【００７０】
そして、「ｉ∈Ｎ＼Ｎｊ」の全てのノードｉに対してリンク使用率の最大値ｕｍａｘ（Ｎｊ，ｉ）を算出し、この値が最小となるノードにｊ＋１番目のサーバを配置する。
【００７１】
この処理を、任意に与えた回数Ｓだけ反復することで、Ｓ個のサーバを配置するノードが特定できる。
【００７２】
図２においては、このようなＳ個のサーバを配置するノードを特定するための手順（サーバ最適配置アルゴリズム）を示している。このサーバ最適配置アルゴリズムをＣＰＵが実行することにより、サーバ配置ノードが集合Ｓとして得られる。
【００７３】
次に、［最適サーバ選択設計法］について説明する。
［最適サーバ選択設計法］：
ノードｄに属するユーザの配信要求に対して用いるサーバの集合をＳｄとする。このサーバ集合Ｓｄを事前に最適設計し、得られた集合Ｓｄに含まれる全てのサーバをノードｄへの配信に対して常に使用する。
【００７４】
まず、各ノードへの配信に単一のサーバを用いる場合に、与えられたサーバ配置に対して最大リンク使用率を最小化する最適サーバを選択する。そして、得られたサーバ選択を初期状態とし、さらに、最大リンク使用率を低減するよう、並列配信における最適サーバの選択を行う。
【００７５】
初期状態では、配信コストδｓｄが最小となるサーバσｄを、ノードｄに対する配信サーバに設定する（Ｓｄ＝｛σｄ｝）。以後、本状態を最小コスト単一サーバ配信（ＭＳＤ:Ｍｉｎｉｍｕｍ  ｃｏｓｔ  Ｓｉｎｇｌｅ  Ｄｅｌｉｖｅｒｙ）と呼ぶ。
【００７６】
このＭＳＤにおける各リンクの使用率を、上述の数１に示す式（１）より算出し、使用率が最大のリンクεとその使用率ｕｍａｘを得る。
【００７７】
そして、リンクεを経路が経由する配信先ノード集合Ｄεに属する各ノードｄに対して、配信に用いるサーバを他の各サーバｋに変えた場合の最大リンク使用率ｕｍａｘ，ｄ，ｋが最小となるサーバｋ＊を、ノードｄに対する配信サーバに変更する（Ｓｄ＝｛ｋ＊｝）。
【００７８】
この処理を、ノード集合Ｄεに属する全てのノードに対して反復し、その結果得られる最大リンク使用率ｕ’ｍａｘが、修正前の値ｕｍａｘより低減する限り、使用サーバの修正を反復する。
【００７９】
このようにして得られた最適単一サーバ選択状態を、最適単一サーバ配信（ＯＳＤ:Ｏｐｔｉｍｕｍ  Ｓｉｎｇｌｅ  Ｄｅｌｉｖｅｒｙ）と呼ぶ。
【００８０】
図３においては、このようなＯＳＤのサーバを選択するための手順（サーバ最適選択アルゴリズム）を示している。このサーバ最適選択アルゴリズムをＣＰＵが実行することにより、ＯＳＤのサーバ選択を行うことができる。
【００８１】
そして、ＯＳＤを初期状態として、さらに、各ノードへの配信に用いるサーバを追加することで、並列配信において最大リンク使用率を最小化する最適サーバ選択を設計する。
【００８２】
ノードｄへの配信に用いるサーバの数をｎｄとし、ノードｄへの配信に用いるｎｄ本の配信フローに対して均等にトラヒックを分散させる。
【００８３】
ＯＳＤにおける各リンクの使用率を、上述の数１に示す式（１）より算出し、使用率が最大のリンクεと、その使用率ｕｍａｘを得る。
【００８４】
そして、取得したリンクεを経路が経由する配信先ノード集合Ｄεに属する各ノードｄに対して、ｎｄ＜Ｓの場合には、未使用のサーバ集合Ｓ＼Ｓｄの各サーバｋを１つだけＳｄに追加したときの最大リンク使用率ｕｍａｘ，ｄ，ｋが最小となるサーバｋ＊を、Ｓｄに追加する。
【００８５】
この処理を、配信先ノード集合Ｄεに属する全てのノードに対して反復し、その結果得られる最大リンク使用率ｕ’ｍａｘが、修正前の値ｕｍａｘより低減する限り、使用サーバの追加処理を反復する。
【００８６】
その結果で得られた最適複数サーバ選択状態を最適並列配信（ＯＰＤ:Ｏｐｔｉｍｕｍ  Ｐａｒａｌｌｅｌ  Ｄｅｌｉｖｅｒｙ）と呼ぶ。
【００８７】
図４においては、このようなＯＰＤの追加サーバを選択するための手順（追加サーバ選択アルゴリズム）を示している。この追加サーバ選択アルゴリズムをＣＰＵが実行することにより、並列配信するサーバの選択を行うことができる。
【００８８】
以下、このようにして選択した並列配信サーバによる効果を、［評価結果］として説明する。
【００８９】
［評価結果］：
まず、評価に用いたＮＷトポロジの説明を行う。
【００９０】
［評価に用いたＮＷトポロジ］：
ＣＡＩＤＡのＷｅｂページでトポロジとリンク容量が公開されている商用ＩＳＰのバックボーンＮＷのうち、ノード数Ｎが２０以上の２３のＮＷを評価に用いる。
【００９１】
図１２においては、これら２３のＮＷのノード数Ｎ、双方向リンク数Ｍ、平均ノード次数ｇ、最大ノード次数Ｇ、そして高次数ノード数比率Ｒをまとめている。
【００９２】
ただしＲを、平均次数ｇより大きな次数を有するノードの数をＮで除した値で定義する。また、正規化最大次数ＧｒをＧｒ＝Ｇ／Ｎで定義する。Ｇｒが大きなＮＷには、多数のノードと接続するハブノードが存在すること、また、Ｒが大きなＮＷには、高次数ノードが多数存在することを意味する。
【００９３】
ここでは、２３のＮＷを便宜上、以下の規則によりＳｔａｒ型、Ｈ＆Ｓ型、Ｌａｄｄｅｒ型の３つのトポロジ種別に分類する。
【００９４】
まず、「Ｇｒ＜０．４」かつ「ｇ＜３」を満たすＮＷをＬａｄｄｅｒ型に分類する。
【００９５】
２３の各ＮＷに対して、正規化最大次数Ｇｒと平均次数ｇの散布図を図５（ａ）に示すが、図中、左下の実線枠で示される領域に存在するＮＷをＬａｄｄｅｒ型に分類することになるが、１１のＮＷが該当する。
【００９６】
そして、Ｌａｄｄｅｒ型に分類されなかったＮＷの中で、さらに、「Ｒ≧０．２５」のＮＷをＨ＆Ｓ型に、「Ｒ＜０．２５」のＮＷをＳｔａｒ型に分類する。
【００９７】
Ｌａｄｄｅｒ型に分類されなかった１２のＮＷに対して、最大ノード次数Ｇと高次数ノード数比率Ｒの散布図を図５（ｂ）に示す。６つのＮＷが各々、Ｓｔａｒ型とＨ＆Ｓ型に分類される。
【００９８】
図６においては、３つのＮＷ種別の各々に分類されるＮＷトポロジの例を示している。これら３つのＮＷは、全て米国に存在するが、ＮＷ種別に応じて大きく形状が異なることが確認できる。各ＮＷ種別は、以下の傾向を有する。
【００９９】
Ｓｔａｒ型は、図６（ａ）に示すように、非常に少数の高次数ノード（ハブノード）が多数の低次数ノードと接続した構造となる。ハブノード以外の大多数のノードは、ハブノードの一つとのみ接続する場合が多く、次数が「１」のノードが多い。ただし、ＮＷ１２（ＬＬ）だけは、例外的に、図６（ｂ）に示すように、多数のノードが複数のハブノードと接続した形状となっている。
【０１００】
このＳｔａｒ型は、ハブノードを介して、少ないホップ数で他のノードに到達できるため、ノード間のホップ距離が短くなる傾向があるが、ハブノードに負荷が集中しやすい。
【０１０１】
Ｈ＆Ｓ型は、図６（ｃ）に示すように、Ｓｔａｒ型ＮＷと比較して多数のハブノードが存在し、これらハブノードが相互接続される傾向がある。低次数ノードの多くは一つ以上のハブノードに接続した構造となるため、ハブ＆スポーク型と呼ばれる。航空路線網が本形態となることが知られている。Ｓｔａｒ型と同様、ノード間のホップ距離が小さくなる傾向がある反面、ハブノードに負荷が集中しやすい。
【０１０２】
Ｌａｄｄｅｒ型は、図６（ｄ）に示すように、ハブノードが存在せず、いくつかのループを組み合わせたトポロジ構造となる。総リンク長を抑えられる反面、ノード間のホップ距離が長くなる傾向がある。高速道路網が本形態となることが知られている。
【０１０３】
本例では、リッチコンテンツ配信に対する需要に地域的な偏りがなく、ノードｎから発生する配信要求数比Ｒｎは、ノードｎが収容する人口のＮＷ全体が収容する人口に対する比率ｐｎに一致することを想定する。
【０１０４】
図７（ａ）においては、２３の各ＮＷの、ノードの次数ｇｎと人口比ｐｎとの相関係数（ＣＣ:Ｃｏｒｒｅｌａｔｉｏｎ  Ｃｏｅｆｆｉｃｉｅｎｔ）を、ノード数Ｎに対してプロットした状態を示している。
【０１０５】
この図７（ａ）からは、多くのＮＷにおいて、各ノードの次数と人口比との間には正の相関が見られ、大都市に配置されたノードの次数が高くなる傾向が確認できる。
【０１０６】
ただし、相関性の強さはＮＷごとに大きく異なり、Ｓｔａｒ型ＮＷは大多数のノードが低次数であるため多くのＳｔａｒ型ＮＷにおける相関性は低い。
【０１０７】
また、図７（ｂ）においては、２３の各ＮＷの、全ノード間の最短ホップ距離の平均値を、ノード数Ｎに対してプロットした状態を示している。
【０１０８】
この図７（ｂ）からは、Ｌａｄｄｅｒ型ＮＷの平均ノード間距離が長い傾向のあること、また、ノード数Ｎの増加に伴い、平均ホップ距離が緩やかに増加する傾向があることが確認できる。
【０１０９】
一方、Ｓｔａｒ型ＮＷとＨ＆Ｓ型ＮＷの平均ホップ距離は、ＮＷ規模とは無関係であり、高次数のハブノードの存在が、ノード間距離の短縮に大きく貢献する。
【０１１０】
次に、並列配信による効果の説明を行う。
【０１１１】
［並列配信の性能評価］：
本例では、図１におけるサーバ配置設計装置１０２とサーバ選択設計装置１０３によるサーバ選択設計を行った際の並列配信（ＯＰＤ）の効果を評価する。
【０１１２】
各ノードペア（ノードｉ，ノードｊ）間のトラヒック量比率ｒｉｊが与えられると、任意に定めた静的なリンク重みに対して各リンクの使用率ｕが一意に決まる。
【０１１３】
そのため、単一時間あたりにＮＷ全体で発生する配信要求から生じるトラヒック量Ｖ（ｂｐｓ）が変化しても、トラヒック量比率Ｒｎが不変という想定の下では、リンク使用率ｕが最大となるボトルネックリンクは不変であり、その最大のリンク使用率ｕｍａｘは、トラヒック量Ｖに比例するため、Ｖ＝１のときのボトルネックリンクの使用率をｕｍａｘ，１とすると、ｕｍａｘ＝ｕｍａｘ，１Ｖとなる。
【０１１４】
ここでは、ｕｍａｘ＝１となるときのＶを最大ＮＷスループットと定義し、最大ＮＷスループットを各ＮＷの平均リンク容量Ｃｅで除した正規化最大ＮＷスループットＶｍａｘ（＝１／ｕｍａｘ，１／Ｃａ）で各配信システムの性能を評価する。
【０１１５】
ＯＰＤの単一配信に対する効果を測る比較対象をＯＳＤとし、ＯＰＤの平均効果ξＯＰＤを、ＯＰＤにおけるＮＷスループットＶｍａｘ，ＯＰＤをＶｍａｘ，ＯＳＤで除した値で定義する（ξＯＰＤ＝Ｖｍａｘ，ＯＰＤ／Ｖｍａｘ，ＯＳＤ）。
【０１１６】
図８においては、サーバ数を２から、ｃｅｉｌｉｎｇ（Ｎ／２）の範囲で変化させたときの、ＯＰＤの平均効果ξＯＰＤを、サーバ数比率ｓに対してＮＷごとにプロットした状態を示している。
【０１１７】
図８（ａ）、図８（ｃ）に示すように、ＮＷ１０とＮＷ２３は、ＯＰＤの効果も見られない。他のＮＷはＯＰＤの効果が見られるが、効果は設置サーバ数に大きく依存する。
【０１１８】
図８（ａ）に示すように、Ｓｔａｒ型ＮＷは、多数のノードの次数が１であり、それらノードに繋がるリンクがボトルネックとなる場合、並列配信を行ってもＮＷスループットを向上させることができずＯＰＤの効果は低い。
【０１１９】
ただし、ＮＷ１２（ＣＡＩＤＡで示されるＧｏｏｄＮｅｔ）は複数のハブノードが存在し、多数のノードが複数のハブノードと接続しているため、並列配信を行うことでＮＷスループットが大きく向上する。
【０１２０】
また、ＮＷ２０は、サーバ数Ｓの広い範囲にわたりＯＰＤの効果が低いが、サーバ数Ｓ＝７のときのみはξＯＰＤ＝１．８となり、ＯＰＤの効果が高い。
【０１２１】
本ＮＷ２０は、ＣＡＩＤＡで示される「Ｔｅｌｓｔｒａ  Ｉｎｔｅｒｎｅｔ」であり、このＮＷ２０において、具体的には、ノード３（Ｈｏｂａｒｔ）がノード４（Ｌａｕｃｎｃｅｓｔｏｎ）とノード５（Ｍｅｌｂｏｕｒｎｅ）に接続しているが、リンク（４，３）と（５，３）の容量の本ＮＷの最大リンク容量に対する比率が０．０１９と小さく、ボトルネックとなりやすい。
【０１２２】
サーバ数Ｓ＝７のとき、ノード４とノード５の両方にサーバが配置されるが、ＯＳＤではノード３に対する配信に、どちらか一方のサーバのみを用いるため、リンク（４，３）かリンク（５，３）のどちらかがボトルネックとなりやすい。
【０１２３】
ＯＰＤにおいては、ノード３に対してノード４とノード５に設置された両方のサーバが配信に用いられ、各々のリンクに加わる負荷が半減する結果、ＯＰＤの効果が高くなる。
【０１２４】
この例が示すように、次数が２のノードに接続する２本のリンクの容量が共に小さい場合、ＯＰＤが効果的となる。
【０１２５】
ところで、ＮＷ２０（Ｔｅｌｓｔｒａ  Ｉｎｔｅｒｎｅｔ）において、サーバ数Ｓ≦４のときは、ノード４とノード５の両方にサーバが設置されず、ノード３に対する配信に効果的に用いることが可能なサーバが複数存在しないため、また５≦Ｓ≦６もしくはＳ≧８のときは、他のリンクがボトルネックとなりＯＰＤの効果がほとんど見られない。
【０１２６】
これに対して、図８（ｂ）、図８（ｃ）に示すように、Ｈ＆Ｓ型ＮＷとＬａｄｄｅｒ型ＮＷにおいては、多くの設置サーバ数に対してＯＰＤの効果が見られる。
【０１２７】
これらのＮＷの中で、図８（ｂ）に示すように、ＮＷ１９（ＣＡＩＤＡで示されるＳｐｒｉｎｔ）におけるＯＰＤの効果が、特にサーバ数Ｓに対して大きく変化している。
【０１２８】
このＮＷ１９は、ＣＡＩＤＡで示される「Ｓｐｒｉｎｔ」であり、具体的には、サーバ数Ｓ＝５のとき、次数１のノード２０（Ｓｙｄｎｅｙ）が接続するリンク（１７，２０）がＯＳＤにおいてボトルネックとなっているため、並列配信では、本ボトルネックリンクの負荷を低減することができず、ＯＰＤの効果が見られない。
【０１２９】
しかし、サーバ数Ｓ≧６のときは、ノード２０にサーバが設置される結果、ボトルネックが他のリンクに移りＯＰＤの効果が見られる。２≦Ｓ≦４のときも、他のリンクがボトルネックでありＯＰＤの効果が見られる。
【０１３０】
例えば、サーバ数Ｓ＝３のとき、ξＯＰＤ＝１．７５と、ＯＰＤの効果が高いが、３つのサーバのうち２つがノード８（Ｃｈｉｃａｇｏ）とノード１５（Ｌｏｎｄｏｎ）に設置され、人口比の大きいノード５（ＮｅｗＹｏｒｋ）にはサーバが配置されないがこれら２つのノードと隣接している。
【０１３１】
リンク（８，５）の容量が２．４８８Ｇｂｐｓと大きいのに対して、リンク（１５，５）の容量が１５５Ｍｂｐｓと小さく、ノード５に対する配信が、ＯＳＤではノード８からのみとなり、ハブノード間に設置されたリンク（８，５）がボトルネックとなった。
【０１３２】
しかし、ＯＰＤではノード８とノード１５の二つから、ノード５に対して配信されるため、ボトルネックリンクの負荷が低減される。
【０１３３】
このように、人口比が高く、次数が２以上のノードにサーバが設置されず、さらに、リンクを共有しないサーバが２つ以上存在する場合には、リンク容量が大きい場合にもＯＰＤが効果的となる。
【０１３４】
図９（ａ）においては、３６の各ＮＷに対して、２≦Ｓ≦ｃｅｉｌｉｎｇ（Ｎ／２）の範囲の各Ｓ（サーバ数）におけるξＯＰＤの値の平均値をＮに対してプロットした状態を示している。
【０１３５】
Ｓｔａｒ型ＮＷは、多数のノードが複数のハブに接続しているＮＷ１２（ＣＡＩＤＡで示されるＧｅｎｕｉｔｙ）を除き、全体的に並列配信の効果が小さい。
【０１３６】
Ｈ＆Ｓ型ＮＷは、次数が２以上のノードに接続するリンクがボトルネックとなる場合には、並列配信を行うことで、ボトルネックリンクの負荷を大きく低減することが可能であり、ＯＰＤの効果が高い。
【０１３７】
また、Ｌａｄｄｅｒ型ＮＷは、ＯＳＤの効果が見られたが、並列配信を行うことで、さらにＮＷスループットが向上する。
【０１３８】
２つのＨ＆Ｓ型ＮＷ（ＮＷ５とＮＷ２１）と４つのＬａｄｄｅｒ型ＮＷ（ＮＷ６、ＮＷ９、ＮＷ１３、ＮＷ２３）は、並列配信の効果が小さいが、ＮＷ５（ＣＡＩＤＡで示されるＡＴ＆Ｔ  ＷｏｒｌｄＮｅｔ）とＮＷ２１（ＣＡＩＤＡで示されるＵＵＮＥＴ）は、大多数のリンクが小容量であるため、また、ＮＷ６（ＣＡＩＤＡで示されるＢＢＮ  ＰＬＡＮＥＴ），９（ＥＰＯＣＨ  Ｎｅｔｗｏｒｋｓ  Ｉｎｃ．），１３（ｉＳＴＡＲ  Ｉｎｔｅｒｎｅｔ  Ｉｎｃ．），２３（ＸＯ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）は次数１のノードが多数存在し、それらを繋ぐリンクがボトルネックとなる傾向があるため並列配信の効果が小さい。
【０１３９】
リンク容量の影響を排除し、トポロジ構造が並列配信の効果に与える影響を評価するため、全てのリンク容量を各ＮＷの平均リンク容量に設定した場合のξＯＰＤの平均値を図９（ｂ）に同様に示す。
【０１４０】
図９（ａ）と図９（ｂ）の比較から、トポロジ構造のみを考えた場合、Ｈ＆Ｓ型ＮＷにおける並列配信の効果が大きく向上する。Ｈ＆Ｓ型ＮＷは、ＯＳＤの場合と比較すれば並列配信の効果が見られるものの、大多数のリンクの容量が平均リンク容量に対して小さい傾向があり、リンク容量の不均一性により並列配信の効果が抑えられていることが確認できる。
【０１４１】
トポロジ構造のみを考えた場合、並列配信が最も効果的なトポロジは複数のサーバが低配信コストで利用しやすいＨ＆Ｓ型であると言える。
【０１４２】
また、図８で見たように、並列配信の効果は設置サーバ数Ｓに大きく依存する。そこで各ＮＷにおいてξＯＰＤが最大となったサーバ数ＳにおけるξＯＰＤを、ノード数Ｎに対してプロットした状態を、図１０（ａ）に示す。
【０１４３】
この図１０（ａ）からは、多数のＮＷにおいて並列配信を行うことで、ＮＷスループットを最大で２０％から１００％程度、向上できることが確認される。
【０１４４】
ただし、多くのＳｔａｒ型ＮＷ（ＮＷ１、ＮＷ１０、ＮＷ１４、ＮＷ１６）と一部のＬａｄｄｅｒ型ＮＷ（ＮＷ９、ＮＷ１３、ＮＷ２３）においては並列配信の効果が小さい。特に、３つのＳｔａｒ型ＮＷ（ＮＷ１０、ＮＷ１４、ＮＷ１６）と１つのＬａｄｄｅｒ型ＮＷ（ＮＷ２３）は、並列配信の効果が全く見られない。
【０１４５】
また、図１０（ｂ）においては、並列配信の効果が全く見られなかった４つのＮＷを除く３２の各ＮＷに対して、並列配信の効果が最大となった設置サーバ数Ｓをノード数Ｎに対して各々プロットした状態を示している。
【０１４６】
図１０（ｂ）に示すように、Ｌａｄｄｅｒ型ＮＷは、並列配信の効果が最大となるサーバ数が多い傾向があり、ノードＮとは無関係に１０〜２０程度の場合が多い。これは、Ｌａｄｄｅｒ型ＮＷは、ほとんど全てのリンクが多数のノードペア間の経路によって共有される傾向があり、サーバ数Ｓが小さい場合には並列配信によって使用率の高いリンクを避ける効果が得にくいためである。
【０１４７】
また、Ｈ＆Ｓ型ＮＷは、次数１のノードに接続するリンクを除き、経由するハブノードを変えることで経由リンクを容易に変えることができるため、少数のサーバ配置時にも並列配信の効果が得やすい。
【０１４８】
図１１においては、各ＮＷに対して、「２≦Ｓ≦ｃｅｉｌｉｎｇ（Ｎ／２)」の全てのサーバ数Ｓにおける並列配信時の、各配信において用いられるサーバ数の累積補分布を示している。
【０１４９】
全てのＮＷにおいて９０％以上の配信で用いられるサーバ数は２以下であり、設置サーバ数が多い場合も含め、各配信先ノードに対して並列配信で用いられるサーバは少数である。
【０１５０】
並列配信の効果の高い一部のＮＷ（図１１（ａ）におけるＮＷ１２、図１１（ｂ）におけるＮＷ１９）においては、並列配信に用いられるサーバ数が多いが、全体的には、並列配信の有効性と並列配信サーバ数との間には相関性は見られず、図１１（ｂ）におけるＮＷ１７（Ｓａｖｖｉｓ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）など、並列配信サーバ数の少ないＮＷにおいても並列配信が効果的なＮＷも存在する。
【０１５１】
以上、図１〜図１２を用いて説明したように、本例のデータ並列配信システムでは、ネットワーク上に複数のミラーサーバを配置し、各配信要求に対して配信に複数のサーバ用いることで各フローの転送ビットレートを低減し、さらに、最大リンク使用率を最小化することで、ネットワーク全体で収容可能な総配信要求量（ネットワークスループット）を最大化する。
【０１５２】
最大リンク使用率を最小化するために、設置サーバ数Ｓ、ネットワークトポロジ、各ノードから発生する配信要求量比、リンク容量、静的なリンクコストの各データを用いて、まず、リンクコスト和が最小となる経路を１本、各ノードペアに対して用い、各ノードに対する配信に用いるサーバを、最小コストのサーバ一つとした場合に、最大リンク使用率が最小となるよう、Ｓ個のサーバを最適配置する。
【０１５３】
また、各ノードに対して用いる単一のサーバを、最大リンク使用率が最小化するように他のサーバに変更する処理を反復することで、単一サーバを各配信に用いる場合に最大リンク使用率が最小化するよう、各ノードに対して用いるサーバを最適選択する。
【０１５４】
さらに、各ノードに対して複数のサーバを同一データの配信に用いることを許容した場合に、最大リンク使用率を最小化するよう、各ノードに対して用いるサーバ集合を最適設計する。
【０１５５】
すなわち、ネットワーク上に配置された複数のサーバから配信先のノードにデータを並列配信するデータ並列配信システムにおける、プログラムされたコンピュータ処理を実行する手段としてのサーバ配置設計装置１０２とサーバ選択設計装置１０３からなるサーバ配置選択手段により、データ配信に用いる各サーバを配置するノードを、各ノード間の各リンクの最大使用率（最大リンク使用率）が最小となるよう選択する。
【０１５６】
特に、サーバ配置設計装置１０２は、ネットワーク内の各ノード間の各リンクの最大リンク使用率を求め、求めた最大リンク使用率が小さい順に予め定められたＳ個のノードを特定し、特定したＳ個のノードを、サーバを設置するノードとして選択する。
【０１５７】
そして、サーバ選択設計装置１０３は、最大使用率のリンクを配信フローが経由する配信先ノードに対して用いるサーバを他のサーバに置き換えた場合の最大リンク使用率が最小となるサーバ置き換えを順次実施することで、Ｓ個のノードに配置された各サーバから、
配信先ノードとの上記最大リンク使用率が最小となるノードに配置されたサーバを１つだけ、配信先ノードに対する配信元サーバとして選択する。
【０１５８】
また、サーバ選択設計装置１０３は、最大使用率のリンクを配信フローが経由する配信先ノードに対して用いるサーバの集合に新たにサーバを一つ追加した場合の最大リンク使用率が最小となる使用サーバの追加を順次実施することで、Ｓ個のノードに配置された各サーバから、配信先ノードへの並列配信に用いる複数のサーバを、配信先ノードとの最大リンク使用率が最小化するよう選択する。
【０１５９】
このように、本例によれば、ネットワーク上に複数のミラーサーバを配置し、各配信要求に対して配信に複数のサーバ用いることで各フローの転送ビットレートを低減する際に、さらに、最大リンク使用率を最小化することで、ネットワーク全体で収容可能な総配信要求量（ネットワークスループット）を最大化することができる。
【０１６０】
尚、本発明は、図１〜図１２を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、サーバ配置設計装置１０２とサーバ選択設計装置１０３を１つのコンピュータ装置内に設けた構成としているが、それぞれを異なるコンピュータ装置に設けた構成としても良い。
【符号の説明】
【０１６１】
１０１：入力データ設定装置、１０２：サーバ配置設計装置、１０３：サーバ選択設計装置、１０４：設計結果出力装置。
【図１】
2010268126.tif 000004
【図２】
2010268126.tif 000005
【図３】
2010268126.tif 000006
【図４】
2010268126.tif 000007
【図５】
2010268126.tif 000008
【図６】
2010268126.tif 000009
【図７】
2010268126.tif 000010
【図８】
2010268126.tif 000011
【図９】
2010268126.tif 000012
【図１０】
2010268126.tif 000013
【図１１】
2010268126.tif 000014
【図１２】
2010268126.tif 000015