(57)【特許請求の範囲】
【請求項１】
配信対象のコンテンツが(K，N)閾値秘密分散法によりN分割されてネットワーク上の配信元ノードに分散配置され、各配信元ノードから配信先ノードへ複数の経路で各部分コンテンツを配信するコンテンツ配信システムの配信経路計算装置において、
各リンクのリンクコストを、n本の既設経路のうちのx本が当該リンクを通過するときに、n-x本の既設経路が全て障害になる確率と当該リンクの障害確率との積として求める第１リンクコスト更新手段と、
既設の経路数がN-K+1本に達するまで、更新済みのリンクコストに基づく最小コスト経路の計算を、前記リンクコストを更新しながら繰り返し、各最小コスト経路を配信経路に逐次的に設定する第１経路設定手段と、
N-K+2本目からN本目までの各配信経路を設定する第２経路設定手段とを具備したことを特徴とするコンテンツ配信システムの配信経路計算装置。
【請求項２】
前記第２経路設定手段は、各リンクのリンクコストを、n本の既設経路のうちのx本が当該リンクを通過するとき、n-x本の配信経路のうちのN-K-x本のみが障害になる確率と当該リンクの障害確率との積として求める第２リンクコスト更新手段を具備し、
更新済みのリンクコストに基づく最小コスト経路の計算を、前記第２リンクコスト更新手段によりリンクコストを更新しながら繰り返し、各最小コスト経路を配信経路に逐次的に設定することを特徴とする請求項１に記載のコンテンツ配信システムの配信経路計算装置。
【請求項３】
ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数mを計算するリンク独立経路数算出手段をさらに具備し、
前記第１リンクコスト更新手段において、各リンクを通過する既設経路の本数がN/m以上の最小整数に達した場合は、当該リンクのリンクコストを無限大に更新設定することを特徴とする請求項１に記載のコンテンツ配信システムの配信経路計算装置。
【請求項４】
ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数mを計算するリンク独立経路数算出手段をさらに具備し、
前記第２リンクコスト更新手段において、各リンクを通過する既設経路の本数がN/m以上の最小整数に達した場合は、当該リンクのリンクコストを無限大に更新設定することを特徴とする請求項２に記載のコンテンツ配信システムの配信経路計算装置。
【請求項５】
前記ネットワークのトポロジを、各配信元ノードの上流側に擬似発ノードを仮想的に設けて各配信元ノードと仮想リンクで接続する仮想トポロジに変換するトポロジ変形手段をさらに具備し、
前記第１および第２経路設定手段ならびに前記リンク独立経路数算出手段は、各配信元ノードと接続される各仮想リンクの容量を、当該配信元ノードが保有している部分コンテンツ数に相当する値に設定し、前記擬似発ノードから各仮想リンクおよび各配信元ノードを経由して配信先ノードへ至る経路を計算することを特徴とする請求項３または４に記載のコンテンツ配信システムの配信経路計算装置。
【請求項６】
配信対象のコンテンツが(K，N)閾値秘密分散法によりN分割されてネットワーク上の配信元ノードに分散配置され、各配信元ノードから配信先ノードへ各部分コンテンツを配信する経路を計算するコンテンツ配信システムの配信経路計算方法において、
コンピュータが、ネットワークを構成する各リンクのリンクコストを更新しながら、配信元ノードから各リンクを通過して配信先ノードへ至るN本の最小コスト経路を逐次的に計算して配信経路に設定する経路設定手順を含み、
前記経路設定手順は、
各リンクのリンクコストを、n本の既設経路のうちのx本が当該リンクを通過するときに、n-x本の既設経路が全て障害になる確率と当該リンクの障害確率との積として求める第１手順と、
前記更新済みのリンクコストに基づいて、配信元ノードから各リンクを通過して配信先ノードへ至る最小コスト経路を計算して配信経路に設定する第２手順と、
既設の経路数がN-K+1本に達するまで、前記第１手順に戻って各リンクコストの更新および配信経路の設定を繰り返す第３手順と、
N-K+2本目からN本目までの各配信経路を設定する第４手順とを含むことを特徴とするコンテンツ配信システムの配信経路計算方法。
【請求項７】
第４手順は、
各リンクのリンクコストを、n本の既設経路のうちのx本が当該リンクを通過するとき、n-x本の配信経路のうちのN-K-x本のみが障害になる確率と当該リンクの障害確率との積として求める第５手順と、
前記更新済みのリンクコストに基づいて、配信元ノードから各リンクを通過して配信先ノードへ至る最小コスト経路を計算して配信経路に設定する第６手順と、
既設の経路数がN本になるまで、前記第５手順に戻って各リンクコストの更新および配信経路の設定を繰り返す第７手順とを含むことを特徴とする請求項６に記載のコンテンツ配信システムの配信経路計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテンツ配信システムの配信経路計算方法および装置に係り、特に、一つのコンテンツを複数の部分コンテンツに分割してネットワーク上に分散配置し、これらの部分コンテンツを一つの配信先ノードへ複数の経路で配信して復号する閾値秘密分散に好適なコンテンツ配信システムの配信経路計算方法および装置に関する。
【背景技術】
【０００２】
１つのコンテンツを暗号化されたN個の部分コンテンツに分割し、当該N個の部分コンテンツのうち、K (≦N) 個以上の部分コンテンツが集まらないと元のコンテンツを復号できないように秘密分散する閾値秘密分散が非特許文献１に開示されている。
【０００３】
また、データ保持のリスク分散を図るために、N個に分割された部分コンテンツを複数のノードで秘密分散保持する技術が特許文献１，２に開示されている。
【０００４】
さらに、複数のノードで秘密分散保持されているN個の部分コンテンツの内のK (≦N) 個をネットワーク経由で配信先ノードまで転送する際に、全ての部分コンテンツが転送途中に盗聴される確率が最小となる配信経路を算出する技術が特許文献３，４に開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００９−１２２７３１号公報
【特許文献２】特開２００９−１０５３１号公報
【特許文献３】特開２０１１−１３４２４６号公報
【特許文献４】特開２０１１−１３９２４０号公報
【非特許文献】
【０００６】
【非特許文献１】Shamir, Adi (1979), "How to share a secret", Communications of the ACM 22 (11): 612-613
【発明の概要】
【発明が解決しようとする課題】
【０００７】
（K，N）閾値秘密分散では、N個の部分コンテンツから任意のK個の部分コンテンツを集めれば元データを復号できるので、複数のノードで秘密分散保持されているN個の部分コンテンツを配信先ノードまでネットワークを介して転送する際、転送途中でN-K個の部分コンテンツが失われても、配信先ノードで元のコンテンツを復号できる。
【０００８】
すなわち、多重リンク障害によってN-K+1個以上の部分コンテンツが欠落してしまう確率を最小化できる部分コンテンツの配信経路を設定できれば、多重リンク障害により元のコンテンツを復号できなくなる確率を最小化できる。
【０００９】
例えば、各部分コンテンツの配信経路が同一リンクを通っていると、当該リンクに障害が発生した場合には、N-K本以下の多重リンク障害でも元のコンテンツを復号できなくなってしまう場合がある。したがって、（K，N）閾値秘密分散を適用したデータ配信では、各配信経路は同一リンクを通らない経路（リンク独立経路）であることが望ましい。
【００１０】
しかしながら、従来技術では（K，N）閾値秘密分散を利用して部分コンテンツを複数経路で配信する際に、部分コンテンツがリンク独立経路を通るようにすることで、多重リンク障害により元のコンテンツを復号できなくなる確率を最小化できる経路を簡単に計算することができなかった。
【００１１】
本発明の目的は、上記した従来技術の課題を解決し、閾値秘密分散された複数の部分コンテンツがネットワーク上の配信元ノードに分散配置され、各配信元ノードから配信先ノードへ複数の経路で各部分コンテンツを配信する際に、多重リンク障害によって元のコンテンツを復号できなくなる確率を最小化できる配信経路の計算方法および装置を提供することにある。
【課題を解決するための手段】
【００１２】
上記の目的を達成するために、本発明は、配信対象のコンテンツが(K，N)閾値秘密分散法によりN分割されてネットワーク上の配信元ノードに分散配置され、各配信元ノードから配信先ノードへ複数の経路で各部分コンテンツを配信するコンテンツ配信システムの配信経路計算装置において、以下の構成を具備した点に特徴がある。
【００１３】
(1)各リンクのコストを、n本の既設経路のうちのx本が当該リンクを通過するときに、n-x本の既設経路が全て障害になる確率と当該リンクの障害確率との積として求める第１リンクコスト更新手段と、更新済みのコストに基づく最小コスト経路の計算を前記リンクコストを更新しながら繰り返してN-K+1本目までの各経路を逐次的に設定する第１経路設定手段と、N-K+2本目からN本目までの各経路を設定する第２経路設定手段とを具備した。
【００１４】
(2)第２経路設定手段は、各リンクのコストを、n本の既設経路のうちのx本が当該リンクを通過するとき、n-x本の配信経路のうちのN-K-x本のみが障害になる確率と当該リンクの障害確率との積として求める第２リンクコスト更新手段を具備し、更新済みのコストに基づく最小コスト経路の計算を、リンクコストを更新しながら繰り返して各経路を逐次的に設定するようにした。
【００１５】
(3)ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数mを計算するリンク独立経路数算出手段をさらに設け、リンクコストが最大数mの関数として算出されるようにした。
【００１６】
(4)ネットワークのトポロジを、各配信元ノードの上流側に擬似発ノードを仮想的に設けて各配信元ノードと仮想リンクで接続した仮想トポロジに変換するトポロジ変形手段を設け、リンク独立経路数算出手段は、各配信元ノードと接続される各仮想リンクの容量を、当該配信元ノードが保有している部分コンテンツ数に相当する値に設定し、前記擬似発ノードから各仮想リンクおよび各配信元ノードを経由して配信先ノードへ至る経路を計算するようにした。
【発明の効果】
【００１７】
本発明によれば、以下のような効果が達成される。
【００１８】
(1)第１リンクコスト更新手段および第１経路設定手段を設けたことにより、経路の設定数がN-K+1本になるまでは、新たに設定する経路があるリンクを通過した場合に、設定される全ての経路が障害になる確率を当該リンクのコストとして更新設定される。したがって、新たに設定する経路として最小コスト経路を計算すれば、設定される全ての経路が障害になる確率が最小化される経路を計算できる。
【００１９】
(2)第２リンクコスト更新手段を設けたことにより、経路の設定数がN-K+1本を超えてN本になるまでは、新たに設定する経路があるリンクを通過した場合に、設定される経路の中のN-K+1本以上の経路が障害になる確率の増加量が当該リンクのコストとして更新設定される。したがって、新たに設定する経路として最小コスト経路を計算すれば、設定される経路の中のN-K+1本以上の経路が障害になる確率の増加量が最小化される経路を計算できる。
【００２０】
(3)リンク独立な経路の最大数mを計算するリンク独立経路数算出手段を設け、各リンクコストを最大数mの関数として求めるようにしたので、N-K+1本以上の配信経路障害を引き起こすリンク障害多重数の最大化を保障できるようになる。
【００２１】
(4)各配信元ノードの上流側に擬似発ノードを仮想的に設けると共に、擬似発ノードと各配信元ノードとを接続する仮想リンクの容量が、当該配信元ノードが保有している部分コンテンツ数に相当する値に設定されるので、各配信元ノードが保持する部分コンテンツ数を考慮した経路計算が可能になる。
【図面の簡単な説明】
【００２２】
【図１】本発明が適用されるコンテンツ配信システムのネットワーク構成を示した図である。
【図２】本発明の一実施形態に係る配信経路計算サーバの機能ブロック図である。
【図３】本発明の一実施形態の動作を示したフローチャートである。
【図４】ネットワークトポロジの変形例を示した図である。
【図５】第１規則によるリンクコストの更新方法を模式的に表現した図である。
【図６】第２規則によるリンクコストの更新方法を模式的に表現した図である。
【図７】リンクコストの更新方法を説明するための図である。
【図８】n-x本の配信経路が全て障害になる確率PF1の算出方法を示したフローチャートである。
【図９】N-K-x本の配信経路のみが障害になる確率PF2の算出方法を示したフローチャートである。
【発明を実施するための形態】
【００２３】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明の配信経路計算方法および装置が適用されるコンテンツ配信システムのネットワーク構成を示した図であり、ここでは、(K，N)閾値秘密分散を利用した複数経路によるコンテンツ配信を例にして説明する。
【００２４】
制御対象のネットワークには、コンテンツを保持するS個の配信元ノードsnodeが配置され、各配信元ノードsnode(s)には、１つのコンテンツをN分割して得られるN個の部分コンテンツが分散配置されている。各配信元ノードsnode(s)に分散配置される部分コンテンツは一つとは限らず、複数の異なる部分コンテンツが配置される場合もある。
【００２５】
配信先ノードdは、少なくともK個の部分コンテンツから元のコンテンツを復号するコンテンツ復号機能を備えている。配信経路計算サーバ１は、各配信元ノードsnode(s)から配信先ノードdへ、N個の部分コンテンツを漏れなく配信する経路を決定して各配信元ノードsnode(s)へ通知し、その配信を要求する。各配信元ノードsnode(s)は、保持している部分コンテンツを、通知された配信経路で配信先ノードdへ配信する。
【００２６】
なお、配信経路計算サーバ１から各配信元ノードsnode(s)へ配信要求される部分コンテンツ数は一つとは限らず、複数の場合もある。そして、複数の部分コンテンツを配信する配信元ノードsnode(s)に対しては、部分コンテンツ数分の複数の経路が通知される。
【００２７】
本発明は、S個の配信元ノードsnode(s)において閾値秘密分散保持されているN個の部分コンテンツを、N本の経路を使って配信先ノードdまで転送する際の経路計算を対象とする。そして、N本の配信経路を１本ずつ逐次的に計算し、この逐次的な計算の各段階で、常にN-K+1個以上の部分コンテンツが損失する確率を最小化するように、更新したリンクコストの下で最小コスト経路を計算する。
【００２８】
図２は、前記配信経路計算サーバ（コンピュータ）１の主要部の構成を示した機能ブロック図であり、本発明の説明に不要な構成は図示が省略されている。
【００２９】
トポロジ取得部１０１は、図１に示した監視対象ネットワークNWの実トポロジを各リンクの障害確率と共に取得する。トポロジ変形部１０２は、前記ネットワークNWの実トポロジを、後に詳述するように、図４に示した仮想トポロジに変換する。リンク独立経路数算出部１０３は、各配信元ノードから配信先ノードdへ至るリンク独立な経路の最大数mを、後述する整数計画法により求解する。
【００３０】
第１経路設定部１０４は、ネットワークを構成する各リンクlのコストCost lを第１規則で更新する第１リンクコスト更新部１０４ａを備える。そして、逐次的な経路計算の各段階で、各リンクlのコストCost lを更新しながら、既設の経路数が当該既設経路の全てが障害になるとコンテンツを復元できなくなる本数、すなわちN-K+1本になるまで、配信先ノードdで元のコンテンツを復元できなくなる確率を最小化する最小コスト経路の計算を繰り返す。計算された最小コスト経路は既設の配信経路として都度追加される。
【００３１】
前記第１コスト更新部１０４ａは、設定されるn+1本全ての配信経路が障害となる確率が最小化されるように、各リンクlのコストCost lを、n本の既設経路のうちのx本が当該リンクlを通過するときに、n-x本の既設経路が全て障害になる確率と当該リンクlの障害確率との積として求める
【００３２】
第２経路設定部１０５は、ネットワークを構成する各リンクlのコストCost lを第２規則で更新する第２コスト更新部１０５ａを備え、逐次的な経路計算において、各リンクlのコストCost lを更新しながら、既設の経路数がN本になるまで、最小コスト経路の計算を繰り返して配信経路に追加する。
【００３３】
前記第２コスト更新部１０５ａは、設定されるn+1本の配信経路の内のN-K+1本以上が障害となる確率の増加が最小化されるように、各リンクlのコストCost lを、n本の既設経路のうちのx本が当該リンクを通過するとき、n-x本の配信経路のうちN-K-x本の経路のみが障害になる確率と当該リンクlの障害確率との積として求める。
【００３４】
経路通知部１０６は、前記N本の最小コスト経路の設定結果を、対応する各配信元ノードsnodeへ通知する。
【００３５】
次いで、フローチャートを参照して本発明の動作について説明する。図３は、本発明の一実施形態に係るコンテンツ配信経路の設定手順を示したフローチャートである。
【００３６】
ステップＳ１では、ネットワークの実トポロジ(Node，Link)および各リンクlの障害確率が前記トポロジ取得部１０１により取得される。ステップＳ２では、コンテンツ配信経路を算出するためのネットワークが、前記トポロジ変形部１０２により、図４の様に仮想的に変形される。
【００３７】
すなわち、配信ノードsnodeの上流側に擬似発ノードvsを仮想的に新たに設け、これを各配信元ノードsnodeと仮想リンクvlinkで接続する。各仮想リンクvlinkの障害確率はゼロとし、各仮想リンクvlinkの容量は、接続している配信元ノードsnodeが保有している部分コンテンツ数C(s)に相当する値に設定する。このようなネットワーク変形により、各配信元ノードsnodeが保持している部分コンテンツ数を考慮してコンテンツ配信経路を計算できるようになる。
【００３８】
ステップＳ３では、部分コンテンツを保持しているS個の配信元ノードsnode(s)から配信先ノードdに至る多数の経路のうち、互いに共通のリンクを含まないリンク独立な経路の最大数mが、前記リンク独立経路数算出部１０３において、以下の整数計画法を解くことにより求められる。ここでは、整数計画法の定数が以下のように定義される。
・node：ネットワークを構成するノード（擬似発ノードは含まない）
・Node：ノードnodeの集合
・d：配信先ノード
・link：ネットワークを構成するリンク（仮想リンクも含む）
・Link：リンクlinkの集合
・vs：擬似発ノード
・vlink：仮想リンク
・VLink：仮想リンクの集合
・snode(vlink)：仮想リンクvlinkが接続する部分コンテンツ保持ノード
・SNode：配信元ノードの集合
・C snode(vlink)：コンテンツ保持ノードsnode(vlink)が保有している部分コンテンツ数
・INnode：ノードnodeを終点とするリンクの集合
・OUTnode：ノードnodeを始点とするリンクの集合
【００３９】
また、本実施形態では変数が以下の様に定義される。
・x link：：リンクlinkを通過するリンク独立経路の本数を表す整数変数。
・M：リンク独立な経路の数。
【００４０】
前記リンク独立経路数算出部１０３における整数計画法では、制約式が次式(1)〜(5)で与えられる。これらは経路保存則に係り、(1)式は、擬似発ノードvsから出る経路の総数がリンク独立な経路の数Mと等しくなるという制約である。(2)式は、配信先ノードdに入る経路数がMであるという制約である。(3)式は、配信先ノードdから出る経路数がゼロであるという制約である。(4)式は、擬似発ノードvsおよび配信先ノードd以外のノード（中継ノード）では、入る経路数と出る経路数とが同一であるという制約である。
【００４１】
【数１】
0005792097.tif 000002
【００４２】
【数２】
0005792097.tif 000003
【００４３】
【数３】
0005792097.tif 000004
【００４４】
【数４】
0005792097.tif 000005
【００４５】
また、本実施形態では全ての経路がリンク独立でなければならず、各リンクを複数の経路が通ることは無いので、次式(5)がリンク独立の条件として与えられる。
【００４６】
【数５】
0005792097.tif 000006
【００４７】
さらに、本実施形態では仮想リンクvlinkの容量条件が次式(6)で与えられる。これは、擬似発ノードvsと各配信元ノードsnodeとを結ぶ仮想リンクvlinkを通過する経路の本数、すなわち当該配信元ノードsnodeから配信される部分コンテンツ数は、当該配信元ノードsnodeが保持している部分コンテンツ数を超えないという条件となる。
【００４８】
【数６】
0005792097.tif 000007
【００４９】
ここで、最大化すべき目的関数Objは変数Mなので、ステップＳ３では、上記の整数計画法を解いてリンク独立な経路数Mの最大数mが求められる。そして、この最大数mおよび前記変数x linkに基づいて各リンク独立経路が具体的に求まる。
【００５０】
ステップＳ４ないしＳ８では、前記第１経路設定部１０４において、既設の経路数がN-K+1本になるまで、ネットワークを構成する各リンクlのコストCostlを前記１コスト更新部１０４ａで更新しながら、擬似発ノードvsから配信元ノードsを経由して配信先ノードdへ至る最小コスト経路が逐次的に計算され、コンテンツの復号に不可欠なK本分の経路（必須経路）以外の冗長分の経路（冗長経路）として設定される。この時、仮想リンクの容量制約を満足する必要がある。すなわち、仮想リンクを通過する既設経路の本数が仮想リンク容量に達した場合は、仮想リンクのコストを無限大に更新設定し、以後、当該仮想リンクを通過する経路が設定されないようにする。
【００５１】
ステップＳ４では、既設経路数nのカウンタが初期化（＝０）される。ステップＳ５では、ネットワークを構成する全てのリンクlのコストCost lが、後述する第１規則にしたがって更新される。ステップＳ６では、擬似発ノードvsから配信先ノードdへ至る最小コスト経路が、前記更新されたリンクコストに基づいて計算される。
【００５２】
ステップＳ７では、前記計算された最小コスト経路が既設経路として追加され、前記既設経路数nがインクリメントされる。ステップＳ８では、前記既設経路数nとN-K+1とが比較され、経路数nがN-K+1に達していなければ前記ステップＳ５へ戻り、各リンクlのコストCost lを第１の規則で更新しながら上記の各処理が繰り返される。
【００５３】
次いで、前記ステップＳ５における第１規則に基づくコストCost lの更新方法について説明する。本実施形態では、既にn本の最小コスト経路が既設であり、次いでn+1本目の最小コスト経路を計算する際、各リンクlのコストCost lは、これらn+1本全ての配信経路が障害となる確率が最小化されるように、以下の第１規則で更新される。
【００５４】
すなわち、図５に模式的に示したように、各リンクlのコストCost lは、n本の既設経路の内のx本が今回の注目リンクlを通過している場合、残りのn-x本の配信経路が全て障害になる確率PF1と当該リンクlの障害確率plとの積PF1×plに設定される。但し、n-x=0の時は、Cost l = plとする。
【００５５】
ここで、配信元ノードsnodeから配信先ノードdに至るリンク独立な経路数がm本であれば、残りのn-x本の配信経路が全て障害になる確率は、図８のフローチャートを参照して後述するように、最大m-1重リンク障害までを考慮して算出される。この時、各リンクの障害確率は十分に小さいと仮定して、f（=1〜m-1）重リンク障害によって、残りのn-x本の配信経路が全て障害になる場合は、f重よりも大きい多重リンク障害は考慮しない。
【００５６】
さらに図７を例にして説明すると、ここでは、３つの最小コスト経路P1、P2、P3が既に計算済みであり、次いで４つ目の最小コスト経路P4を設定する場合、リンクl1はいずれの経路P1、P2、P3も通過しないので、そのコストCost l1は、既設経路P1、P2、P3が全て障害になる確率とリンクl1の障害確率p l1との積に設定される。リンクl2は経路P1のみが通過するので、そのコストCost l2は、経路P2、P3が全て障害になる確率とリンクl2の障害確率p l2との積に設定される。リンクl3は２つの経路P2、P3が通過するので、そのコストCost l3は、経路P1が障害になる確率とリンクl3の障害確率p l3との積に設定される。リンクl4は３つの経路P1、P2、P3が通過するので、そのコストCost l4は、リンクl4の障害確率p l4に設定される。
【００５７】
図８は、前記n-x本の配信経路が全て障害になる確率PF1の算出方法を示したフローチャートであり、ステップＳ２１では、確率PF1がリセットされ、リンク障害の多重数ｆに初期値「１」がセットされる。ステップＳ２２では、注目リンクlを除くf本のリンクの組合せが列挙されてリストが構成される。ステップＳ２３では、前記リストからリンクの組合せが１つずつ取り出されて多重リンク障害が想定される。
【００５８】
ステップＳ２４では、n-x本の経路が全て障害であるか否かが判定される。全て障害であればステップＳ２５へ進み、その障害確率がPF1に加算される。ステップＳ２６では、全てのリンク組合せの取り出しが完了したか否かが判定される。完了していなければステップＳ２３へ戻り、リンク組合せを切り替えながら上記の各処理が繰り返される。
【００５９】
その後、全てのリンク組合せの取り出しが完了するとステップＳ２７へ進み、PF1がゼロであるか否かが判定される。ゼロでなければ当該処理を終了し、ゼロであればステップＳ２８へ進む。ステップＳ２８では、リンク組合せ数ｆとm-1とが比較され、ｆ＜m-1でなければ当該処理を終了し、ｆ＜m-1であれば、ステップＳ２９でfを更新（f=f＋1）してステップＳ２２へ戻る。
【００６０】
図３へ戻り、ステップＳ９ないしＳ１１では、前記第２経路設定部１０５において、既設経路数がコンテンツの分割数に相当するN本になるまで、ネットワークを構成する各リンクlのコストCost lを前記２コスト更新部１０５ａで更新しながら、擬似発ノードvsから配信先ノードdまでの最小コスト経路が逐次的に計算されて設定される。この時、仮想リンクの容量制約を満足する必要がある。すなわち、仮想リンクを通過する既設定の経路の本数が仮想リンク容量に達した場合は、仮想リンクのコストを無限大に更新設定し、以後、当該仮想リンクを通過する経路が設定されないようにする。
【００６１】
ステップＳ９では、ネットワークを構成する全てのリンクlのコストCost lが、後述する第２規則にしたがって更新される。ステップＳ１０では、擬似発ノードvsから配信先ノードdへ至る最小コスト経路が、前記更新されたリンクコストに基づいて計算される。
【００６２】
ステップＳ１１では、前記計算された最小コスト経路が既設経路として追加され、前記既設経路数nがインクリメントされる。ステップＳ１２では、前記既設経路数nと分割数Nとが比較される。経路数nが分割数Nに達していなければ前記ステップＳ９へ戻り、各リンクlのコストCost lを前記第２の規則で更新しながら上記の各処理が繰り返される。
【００６３】
次いで、前記ステップＳ９における第２の規則に基づくコストlの更新方法について説明する。本実施形態では、既にn（≧N-K+1）本の最小コスト経路が設定済みであり、n+1本目の最小コスト経路を計算する際、各リンクlのコストCost lは、これらn+1本の配信経路のうちN-K+1本以上が障害となる確率の増加が最小化されるように、以下の第２規則で更新される。
【００６４】
すなわち、図６に模式的に示したように、n本の既設経路の内のx本が今回の注目リンクlを通過している場合、当該リンクlのコストCost lは、残りのn-x本の経路の内のN-K-x本のみが障害になる確率とリンクlの障害確率plとの積に設定される。但し、N-K-x=0の時は、Cost l=plとする。また、N-K-x<0の時は、Cost l=0とする。
【００６５】
残りのn-x本の配信経路の内N-K-x本のみが障害になる確率PF2は、図９のフローチャートを参照して後述するように、最大でm-1重リンク障害までを考慮して算出する。この時、各リンクの障害確率は十分小さいと仮定して、f（=1〜m-1）重リンク障害によって、残りのn-x本の配信経路の内N-K-x本のみが障害になる場合は、f重よりも大きい多重リンク障害は考慮しない。
【００６６】
図９は、N-K-x本の配信経路のみが障害になる確率PF2の算出方法を示したフローチャートであり、ステップＳ４１では、確率PF2がリセットされ、リンク障害の多重数ｆに初期値「１」がセットされる。ステップＳ４２では、注目リンクlを除くf本のリンクの組合せが列挙されてリストが構成される。ステップＳ４３では、前記リストからリンクの組合せが１つずつ取り出されて多重リンク障害が想定される。
【００６７】
ステップＳ４４では、N-K-x本の経路のみが障害であるか否かが判定される。N-K-x本の経路のみが障害であればステップＳ４５へ進み、その障害確率がPF2に加算される。ステップＳ４６では、全てのリンク組合せの取り出しが完了したか否かが判定される。完了していなければステップＳ４３へ戻り、リンク組合せを切り替えながら上記の各処理が繰り返される。
【００６８】
その後、全てのリンク組合せの取り出しが完了するとステップＳ４７へ進み、PF2がゼロであるか否かが判定される。ゼロでなければ当該処理を終了し、ゼロであればステップＳ４８へ進む。ステップＳ４８では、リンク組合せ数ｆとm-1とが比較され、ｆ＜m-1でなければ当該処理を終了し、ｆ＜m-1であれば、ステップＳ４９でfを更新（f=f＋1）してステップＳ４２へ戻る。
【００６９】
さらに前記図７を例にして説明すると、N-K=2と仮定すれば、配信経路P4を設定する場合、リンクl1のコストCost l1は、配信経路P1、P2、P3の内の２本のみが障害になる確率とリンクl1の障害確率p l1との積に設定される。リンクl2のコストCost l2は、配信経路P2、P3の内の１本のみが障害になる確率とリンクl2の障害確率p l2との積に設定される。リンクl3のコストCost l3は、リンクl3の障害確率p l3に設定される。リンクl4のコストCost l4はゼロに設定される。
【００７０】
更に、N-K+1本以上の配信経路障害を引き起こすリンク障害多重数の最大化を保障する目的で、前記第１の経路設定手順（ステップＳ４ないしＳ８）および第２の経路設定手順（ステップＳ９ないしＳ１２）において、各リンクの容量をN/m以上の最小整数に設定して、最小コスト経路が計算される。すなわち、各リンクを通過する既設経路の本数がN/m以上の最小整数に達した場合は、当該リンクのコストを無限大に更新設定し、以後、当該リンクを通過する経路が設定されないようにする。
【００７１】
本実施形態によれば、経路を逐次的に設定するにあたり、経路の設定数がN-K+1本になるまでは、新たに設定する経路があるリンクを通過した場合に、設定される全ての経路が障害になる確率を当該リンクのコストとして更新設定される。したがって、新たに設定する経路として最小コスト経路を計算すれば、設定される全ての経路が障害になる確率が最小化される経路を計算できる。
【００７２】
また、経路の設定数がN-K+1本を超えてN本になるまでは、新たに設定する経路があるリンクを通過した場合に、設定される経路の中のN-K+1本以上の経路が障害になる確率の増加量が当該リンクのコストとして更新設定される。したがって、新たに設定する経路として最小コスト経路を計算すれば、設定される経路の中のN-K+1本以上の経路が障害になる確率の増加量が最小化される経路を計算できる。
【００７３】
そして、以上のように大きく２段階の処理で経路を逐次的に設定することにより、N本の経路の中のN-K+1本以上の経路が障害になる確率を最小化できるようになる。
【符号の説明】
【００７４】
１…配信経路計算サーバ，１０１…トポロジ取得部，１０２…トポロジ変形部，１０３…リンク独立経路数算出部，１０４…第１経路設定部，１０４ａ…第１リンクコスト更新部，１０５…第２経路設定部，１０５ａ…第２コスト更新部，１０６…経路通知部
【図１】
0005792097.tif 000008
【図２】
0005792097.tif 000009
【図３】
0005792097.tif 000010
【図４】
0005792097.tif 000011
【図５】
0005792097.tif 000012
【図６】
0005792097.tif 000013
【図７】
0005792097.tif 000014
【図８】
0005792097.tif 000015
【図９】
0005792097.tif 000016