(57)【要約】【課題】グループ別のネットワーク符号化を利用し、閾値秘密分散された複数の部分コンテンツを異なる経路で配信する。【解決手段】  第１求解部１０２は、各配信元ノードsから各配信先ノードdへ至るリンク独立な経路の最大数mを第１の整数計画法により求解する。多重数計算部１０３は、N本の経路をM本のリンクに均等に配分するときに、N-K+1本の経路が含まれ得る最少のリンク数Fを算出する。第２求解部１０４は、N-K+1本以上の経路が含まれることになるF本以下のリンク全てにリンク障害が生じるF重リンク障害以下の多重リンク障害の発生によって元のコンテンツを復元できなくなる配信先ノード数の期待値を最小化するような各配信先ノードに至るN本の経路を第２の整数計画法により、ネットワーク符号化の適用範囲を同一グループ内の部分コンテンツに制限して求解する。【選択図】図２
2014200003.tif 000002
【特許請求の範囲】
【請求項１】
配信対象のコンテンツがN分割されて複数のグループに分類され、各部分コンテンツがネットワーク上の配信元ノードから複数の配信先ノードへ、ネットワーク符号化を適用する中継ノードを介して複数の経路で配信されるコンテンツ配信ネットワークにおいて、
前記各中継ノードは、ネットワーク符号化の適用範囲を、同一グループに属して配信先ノードが異なる部分コンテンツに制限することを特徴とするコンテンツ配信ネットワーク。
【請求項２】
コンテンツをN分割して複数のグループに分類された各部分コンテンツにネットワーク符号化を適用して中継する中継ノードにおいて、
ネットワーク符号化の適用範囲を、同一グループに属して配信先ノードが異なる部分コンテンツに制限することを特徴とする中継ノード。
【請求項３】
配信対象のコンテンツが(K,N)閾値秘密分散法によりN分割されて複数のグループに分類され、各部分コンテンツがネットワーク上の配信元ノードから複数の配信先ノードへ、同一グループに属して配信先ノードが異なる部分コンテンツに対してのみネットワーク符号化を適用する中継ノードを介して複数の経路で配信されるコンテンツ配信システムの経路計算装置であって、
符号化ネットワークのトポロジに基づいて、複数の配信元ノードから各配信先ノードへ至るリンク独立な経路の最大数mを第１の整数計画法で求解して、各配信先ノードに関するリンク独立な経路の最大数mの最小数Mを求める第１求解手段と、
N本の経路をM本のリンクに均等に配分するときに、N-K+1本の経路が含まれ得る最少のリンク数Fを算出する多重数算出手段と、
N-K+1本以上の経路が含まれるF本以下のリンク組でリンク障害が生じる多重リンク障害の発生によって、元のコンテンツを復元できなくなる配信先ノード数の期待値を最小化するような各配信先ノードに至るN本の経路を第２の整数計画法で求解する第２求解手段とを具備し、
前記第２求解手段では、各中継ノードの出リンクの使用帯域を、各グループにおける当該出リンクを通過して同一宛先に至る経路数のうちの最大値を全グループについて加算した値に見積もり、ネットワーク符号化された部分コンテンツが損失した場合は、同一グループの全ての部分コンテンツが損失となるような制約条件を課されることを特徴とするコンテンツ配信システムの経路計算装置。
【請求項４】
前記ネットワークのトポロジを、各配信元ノードの上流側に擬似発ノードが仮想的に設けられて各配信元ノードと仮想リンクで接続された仮想トポロジに変換する仮想トポロジ変換手段をさらに具備し、
前記第１求解手段および第２求解手段は、各配信元ノードと接続される各仮想リンクの容量を、当該配信元ノードが保有している部分コンテンツ数に相当する値に設定し、前記擬似発ノードから各仮想リンクおよび各配信元ノードを経由して配信先ノードへ至る経路を求解することを特徴とする請求項２に記載のコンテンツ配信システムの経路計算装置。
【請求項５】
配信対象のコンテンツが(K，N)閾値秘密分散法によりN分割されて複数のグループに分類され、各部分コンテンツがネットワーク上の配信元ノードから複数の配信先ノードへ、同一グループに属して配信先ノードが異なる部分コンテンツに対してのみネットワーク符号化を適用する中継ノードを介して複数の経路で配信されるコンテンツ配信システムの経路計算装置であって、
多重リンク障害によって元のコンテンツを復元できなくなる配信先ノード数の期待値を小さくするコンテンツ配信経路を、各リンクのコストを更新しながら、各配信先ノードへの経路数がN本になるまで、最小コスト経路計算を繰り返して配信先ノードごとに設定する経路設定手段を具備し、
前記経路設定手段は、前記各リンクのコストを更新する方法を、既に算出されている配信経路および新たに算出する配信経路が属するグループ群に含まれる経路総数がN-K+1本以下であるか否かに応じて異ならせ、
前記経路総数がN-K+1本以下であれば、新たな配信経路が当該リンクを通ることによって配信先ノードに転送される全ての部分コンテンツが損失になる確率をリンクコスト更新値としてリンクコストに加算し、
前記経路総数がN-K+1本を超えていれば、新たな配信経路が当該リンクを通ることによって配信先ノードに転送されるN-K+1個以上の部分コンテンツが損失になる確率をリンクコスト更新値としてリンクコストに加算することを特徴とするコンテンツ配信システムの経路計算装置。
【請求項６】
前記各部分コンテンツは、同一の配信元ノードに分散配置されている複数の部分コンテンツが同一グループに属さないように分類されることを特徴とする請求項３ないし５のいずれかに記載のコンテンツ配信システムの経路計算装置。
【請求項７】
配信対象のコンテンツが(K，N)閾値秘密分散法によりN分割されて複数のグループに分類され、各部分コンテンツがネットワーク上の配信元ノードから複数の配信先ノードへ、同一グループに属して配信先ノードが異なる部分コンテンツに対してのみネットワーク符号化を適用する中継ノードを介して複数の経路で配信されるコンテンツ配信システムの経路計算方法であって、
コンピュータが、符号化ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数mを第１の整数計画法で求解して、各配信先ノードに関するリンク独立な経路の最大数mの最小数Mを求める手順と、
コンピュータが、N本の経路をM本のリンクに均等に配分するときに、N-K+1本の経路が含まれ得る最少のリンク数Fを算出する手順と、
コンピュータが、N-K+1本以上の経路が含まれるF本以下のリンク組でリンク障害が生じる多重リンク障害の発生によって、元のコンテンツを復元できなくなる配信先ノード数の期待値を最小化するような各配信先ノードに至るN本の経路を第２の整数計画法で求解する手順とを含み、
前記第２の整数計画法では、各中継ノードの出リンクの使用帯域を、各グループにおいて当該出リンクを通過して同一宛先に至る経路数のうちの最大値を全グループについて加算した値に見積もり、ネットワーク符号化された部分コンテンツが損失した場合は、同一グループの全ての部分コンテンツが損失となるような制約条件を課されることを特徴とするコンテンツ配信システムの経路計算方法。
【請求項８】
コンピュータが、各配信元ノードの上流側に擬似発ノードを仮想的に設けて各配信元ノードと仮想リンクで接続する手順と、
コンピュータが、各配信元ノードと接続される仮想リンクの容量を、当該配信元ノードが保有している部分コンテンツ数に相当する値に設定する手順とを更に含み、
前記第１の整数計画法および第２の整数計画法では、前記擬似発ノードから各仮想リンクおよび各配信元ノードを経由して配信先ノードへ至る経路が求解されることを特徴とする請求項７に記載のコンテンツ配信システムの経路計算方法。
【請求項９】
配信対象のコンテンツが(K，N)閾値秘密分散法によりN分割されて複数のグループに分類され、各部分コンテンツがネットワーク上の配信元ノードから複数の配信先ノードへ、同一グループに属して配信先ノードが異なる部分コンテンツに対してのみネットワーク符号化を適用する中継ノードを介して複数の経路で配信されるコンテンツ配信システムの経路計算方法であって、
多重リンク障害によって元のコンテンツを復元できなくなる配信先ノード数の期待値を小さくするコンテンツ配信経路を、各リンクのコストを更新しながら、各配信先ノードへの経路数がN本になるまで、最小コスト経路計算を繰り返して配信先ノードごとに設定し、
前記各リンクのコストを更新する方法を、既に算出されている配信経路および新たに算出する配信経路が属するグループ群に含まれる経路総数がN-K+1本以下であるか否かに応じて異ならせ、
前記経路総数がN-K+1本以下であれば、新たな配信経路が当該リンクを通ることによって配信先ノードに転送される全ての部分コンテンツが損失になる確率をリンクコスト更新値としてリンクコストに加算し、
前記経路総数がN-K+1本を超えていれば、新たな配信経路が当該リンクを通ることによって配信先ノードに転送されるN-K+1個以上の部分コンテンツが損失になる確率をリンクコスト更新値としてリンクコストに加算することを特徴とするコンテンツ配信システムの経路計算方法。
【請求項１０】
前記各部分コンテンツは、同一の配信元ノードに分散配置されている複数の部分コンテンツが同一グループに属さないように分類されることを特徴とする請求項７ないし９のいずれかに記載のコンテンツ配信システムの経路計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテンツ配信システムの経路計算方法および装置ならびにコンテンツ配信ネットワークおよびその中継ノードに係り、特に、一つのコンテンツを複数の部分コンテンツに分割してネットワーク上に分散配置し、かつネットワーク符号化（network coding）によるスループットの向上を図りながら、各部分コンテンツを複数の配信先ノードへ複数の経路で配信する閾値秘密分散に好適なコンテンツ配信システムの経路計算方法および装置ならびにコンテンツ配信ネットワークおよびその中継ノードに関する。
【背景技術】
【０００２】
非特許文献１には、１つのコンテンツを、暗号化されたn個の部分コンテンツに分割し、n個の部分コンテンツのうち、k (≦n) 個以上の部分コンテンツが集まらないと元のコンテンツを復元できないように秘密分散する閾値秘密分散方法が開示されている。
【０００３】
特許文献１，２には、複数のノードで秘密分散保持されているN個の部分コンテンツをネットワーク経由で配信先ノードまで転送する際に、多重リンク障害によってN-K個よりも多い数の部分コンテンツが転送途中で損失となり、配信先ノードで元のコンテンツを復元できなくなる確率が最小となる配信経路を計算する方法が開示されている。
【０００４】
非特許文献２には、中継ノードにおいて、ネットワーク符号化技術を用いて、異なる配信先ノードへ配信される複数の部分コンテンツを１つの部分コンテンツに符号化して転送することにより、リンク帯域の有効利用を図る技術が開示されている。
【０００５】
特許文献３には、複数のノードで秘密分散保持されているコンテンツを、ネットワークを介して複数の配信先ノードまで同時転送する際に、ネットワーク符号化を適用してリンク帯域の有効利用を図りつつ、多重リンク障害によって元のコンテンツを復元できなくなる配信先ノード数の期待値を小さくするコンテンツ配信経路を計算する技術が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特願２０１２−２３９９３号
【特許文献２】特願２０１２−４５３１５号
【特許文献３】特願２０１２−２７５８２８号
【非特許文献】
【０００７】
【非特許文献１】Shamir, Adi (1979), "How to share a secret", Communications of the ACM 22 (11): 612-613
【非特許文献２】R. Ahlswede, et.al., "Network information flow," IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204-1216, July 2000.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
N個の部分コンテンツから任意のK個の部分コンテンツを集めれば元データを復元できるが(K-1)個の部分コンテンツからでは元データを復元できない（K,N）閾値秘密分散では、N個の部分コンテンツがネットワーク上の配信元ノードに分散配置され、元データを復元しようとする配信先ノードに対して、部分コンテンツを保持する配信元ノードから各配信先ノードへ部分コンテンツが配信される。
【０００９】
（K,N）閾値秘密分散では、N個の部分コンテンツから任意のK個の部分コンテンツを集めれば元のコンテンツを復元できるので、複数のノードで秘密分散保持されているN個の部分コンテンツを配信先ノードまでネットワークを介して転送する際、転送途中でN-K個の部分コンテンツが失われても、配信先ノードで元のコンテンツを復元できる。
【００１０】
すなわち、（K,N）閾値秘密分散では、多重リンク障害によってN-K+1個以上の部分コンテンツが失われてしまう確率を最小化できる部分コンテンツの配信経路を設定できれば、多重リンク障害により元のコンテンツを復元できなくなる確率を最小化できる。
【００１１】
一方、各部分コンテンツの配信経路が同一リンクを通っていると、当該リンクに障害が発生した場合にはN-K本未満の多重リンク障害でも元のコンテンツを復元できなくなってしまう場合がある。したがって、（K,N）閾値秘密分散を適用したコンテンツ配信では、各配信経路は同一リンクを通らない経路（リンク独立経路）であることが望ましい。
【００１２】
しかしながら、従来技術では（K,N）閾値秘密分散を利用して部分コンテンツを複数経路で配信する際に、部分コンテンツがリンク独立経路を通るようにすることで、多重リンク障害により元のコンテンツを復元できなくなる確率を最小化できる経路を簡単に計算することができなかった。
【００１３】
特許文献３によれば、複数の配信先ノードのそれぞれにN個の部分コンテンツを配信する場合、ネットワーク符号化が適用されるのでスループットの向上が期待できる。しかしながら、多重リンク障害によって、配信先ノードでネットワーク復号化できなくなる部分コンテンツ数が増加し、元のコンテンツを復元できない配信先ノード数の期待値が増加してしまうという技術課題があった。
【００１４】
本発明の目的は、上記した従来技術の課題を解決し、ネットワーク符号化を利用し、閾値秘密分散された複数の部分コンテンツを異なる経路で配信するシステムにおいて、複数の部分コンテンツを複数のグループに分類し、ネットワーク符号化を同一グループに属して配信先ノードが異なる部分コンテンツに対してのみ適用することにより、リンク帯域の有効利用は制限されるものの、多重リンク障害によって元のコンテンツを復元できなくなる配信先ノード数の期待値をより小さくできるコンテンツ配信システムの経路計算方法および装置ならびにコンテンツ配信ネットワークおよびその中継ノードを提供することにある。
【課題を解決するための手段】
【００１５】
上記の目的を達成するために、本発明は、配信対象のコンテンツが(K,N)閾値秘密分散法によりN分割されて複数のグループに分類され、各部分コンテンツがネットワーク上の配信元ノードから複数の配信先ノードへ、同一グループに属して配信先ノードが異なる部分コンテンツに対してのみネットワーク符号化を適用する中継ノードを介して複数の経路で配信されるコンテンツ配信システムの経路計算装置であって、符号化ネットワークのトポロジに基づいて、複数の配信元ノードから各配信先ノードへ至るリンク独立な経路の最大数mを第１の整数計画法で求解して、各配信先ノードに関するリンク独立な経路の最大数mの最小数Mを求める第１求解手段と、N本の経路をM本のリンクに均等に配分するときに、N-K+1本の経路が含まれ得る最少のリンク数Fを算出する多重数算出手段と、N-K+1本以上の経路が含まれるF本以下のリンク組でリンク障害が生じる多重リンク障害の発生によって、元のコンテンツを復元できなくなる配信先ノード数の期待値を最小化するような各配信先ノードに至るN本の経路を第２の整数計画法で求解する第２求解手段とを設け、第２求解手段には、各中継ノードの出リンクの使用帯域を、各グループにおける当該出リンクを通過して同一宛先に至る経路数のうちの最大値を全グループについて加算した値に見積もり、ネットワーク符号化された部分コンテンツが損失した場合は、同一グループの全ての部分コンテンツが損失となるような制約条件を課した。
【発明の効果】
【００１６】
本発明のコンテンツ配信システム装置によれば、以下のような効果が達成される。
(1)複数のノードで閾値秘密分散保持されているコンテンツを複数の配信先ノードまでネットワークを介して同時転送する際に、ネットワーク符号化を用いてリンク帯域の有効利用を図りつつ、多重リンク障害によって元のコンテンツが復元できなくなる配信先ノード数の期待値を最小化する高信頼なコンテンツ配信経路の計算が可能となる。
【００１７】
(2)部分コンテンツを複数のグループに分割し、同一グループの部分コンテンツに対してのみネットワーク符号化を適用することで、リンク帯域の有効利用は制限されるものの、多重リンク障害によって元のコンテンツを復元できなくなる配信先ノード数の期待値をより小さくするコンテンツ配信経路の計算が可能となる。
【００１８】
(3)各部分コンテンツが損失した場合は、当該部分コンテンツと同一グループに属する全ての部分コンテンツが損失したと見なすことにより、各中継ノードにおいてネットワーク符号化される部分コンテンツの実際の組合せを考慮することなく、信頼性に関して安全側のコンテンツ配信経路を簡易に計算できるようになる。
【００１９】
また、本発明のコンテンツ配信システムの経路計算方法によれば、以下のような効果が達成される。
(4)リンクコストを更新しながら、最小コスト経路計算法を用いて、各部分コンテンツを各配信先ノードまで配信するための経路を１本ずつ逐次的に算出することにより、コンテンツ配信経路を高速に計算できる。
【図面の簡単な説明】
【００２０】
【図１】本発明が適用されるコンテンツ配信システムのネットワーク構成を示した図である。
【図２】配信経路計算サーバの第１実施形態の機能ブロック図である。
【図３】本発明の一実施形態の動作を示したフローチャートである。
【図４】ネットワークトポロジの変形例を示した図である。
【図５】各リンクにおけるグループ別ネットワーク符号化の適用方法を示した図である。
【図６】配信経路計算サーバの第２実施形態の機能ブロック図である。
【図７】第２実施形態に係るコンテンツ配信経路の設定手順を示したフローチャートである。
【図８】リンクコストCost lの初期値の算出手順を示したフローチャートである。
【図９】リンクコストCost lを算出する手順を示したフローチャートである。
【図１０】リンクコストの算出例を模式的に示した図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明の配信経路計算方法および装置が適用されるコンテンツ配信システムのネットワーク構成を示した図であり、ここでは、(K，N)閾値秘密分散を利用した複数経路によるコンテンツ配信を例にして説明する。
【００２２】
制御対象のネットワークには、コンテンツを保持するS個の配信元ノード（コンテンツ保持ノード）sが配置され、各配信元ノードsには、１つのコンテンツをN分割して得られるN個の部分コンテンツが分散配置されている。各配信元ノードsに分散配置される部分コンテンツは一つとは限らず、複数の異なる部分コンテンツが配置される場合もある。D個の各配信先ノードdには、S個の各配信元ノードからN個の部分コンテンツがそれぞれ配信される。
【００２３】
各配信元ノードsから送信された部分コンテンツは、複数の中継ノードを経由して各配信先ノードdへ配信される。各中継ノードは、宛先の配信先ノードdが異なる複数の部分コンテンツを符号化して一つの符号化部分コンテンツにまとめる周知のネットワーク符号化機能を備える。
【００２４】
本実施形態では、部分コンテンツを複数のグループに分割し、ネットワーク符号化の適用範囲を同一グループ内の部分コンテンツに制限する。これにより、ある部分コンテンツがリンク障害によって損失したとしても、配信先ノードでネットワーク復号化できなくなる可能性のある部分コンテンツは、当該損失部分コンテンツと同一グループに属する部分コンテンツのみに制限できる。
【００２５】
すなわち、当該グループに属さないK個以上の部分コンテンツを配信先ノードでネットワーク復号化できれば、当該配信先ノードで元のコンテンツを復元できる。この時、互いに異なるノードで保持されている部分コンテンツを同一グループに所属させることにより、ネットワーク符号化が促進されてリンク帯域の有効利用が図れる。
【００２６】
各配信先ノードdは、ネットワーク符号化により複数の部分コンテンツが一つにまとめられた符号化部分コンテンツを復号して各部分コンテンツを再現するネットワーク復号機能、および少なくともK個の部分コンテンツから元のコンテンツを復元するコンテンツ復元機能を備えている。
【００２７】
配信経路計算サーバ１は、各配信元ノードsから各配信先ノードdへ、ネットワーク符号化を利用してN個の部分コンテンツを漏れなく配信する経路を決定して各配信元ノードsへ通知し、その配信を要求する。各配信元ノードsは、保持している部分コンテンツを、通知された配信経路で各配信先ノードdへ配信する。
【００２８】
配信経路計算サーバ１から各配信元ノードsへ配信要求される部分コンテンツ数は一つとは限らず、複数の場合もある。そして、複数の部分コンテンツを配信する配信元ノードsに対しては、部分コンテンツ数分の複数の経路が通知される。なお、配信経路計算サーバ１は各配信元ノードsに分散配置されている部分コンテンツを予め認識しており、各部分コンテンツは、同一の配信元ノードに分散配置されている複数の部分コンテンツが同一グループに属さないように、予め複数のグループに分類されている。換言すれば、異なる配信元ノードに分散配置されている部分コンテンツ同士のみが同一グループへの分類を許容される。そして、各部分コンテンツの経路を通知する際は、各部分コンテンツが属するグループ識別子IDgも併せて通知される。
【００２９】
本実施形態では、ネットワーク符号化によるリンク帯域使用の効率化を図りながら、多重リンク障害によって元のコンテンツを復元できなくなる配信先ノード数の期待値を最小化するような配信経路が計算される。
【００３０】
[第１実施例]
図２は、本発明の第１実施形態に係る配信経路計算サーバ（コンピュータ）１の主要部の構成を示した機能ブロック図であり、ここでは、本発明の説明に不要な構成は図示が省略されている。
【００３１】
トポロジ取得部１００は、前記ネットワークのトポロジを取得する。トポロジ変形部１０１は、取得されたネットワークの実トポロジを、後に詳述するように、図４に示した仮想トポロジに変形する。第１求解部１０２は、各配信元ノードsから各配信先ノードdへ至るリンク独立な経路の最大数mを、後述する第１の整数計画法により求解し、さらにはD個の各配信先ノードdに関して求めたリンク独立な経路の最大数mの中の最小値Mを求める。
【００３２】
多重数計算部１０３は、N個の部分コンテンツを転送するためのN本の経路を、配信元ノードsと配信先ノードdとの間の最小カットセットを構成するM個のリンクに均等に配分するときに、N-K+1本の経路が含まれる最少のリンク数Fを算出する。
【００３３】
第２求解部１０４は、N-K+1本以上の経路が含まれることになるF本以下のリンク全てにリンク障害が生じるF重リンク障害以下の多重リンク障害の発生によって、元のコンテンツを復元できなくなる配信先ノード数の期待値を最小化するような各配信先ノードに至るN本の経路を、後述する第２の整数計画法により、ネットワーク符号化の適用範囲を同一グループ内の部分コンテンツに制限しながら求解する。経路通知部１０５は、前記N本の経路の決定結果を、対応する各配信元ノードsへ通知する。
【００３４】
次いで、フローチャートを参照して本発明の動作について説明する。図３は、本発明の一実施形態に係るコンテンツ配信経路の設定手順を示したフローチャートである。
【００３５】
ステップＳ１では、ネットワークの実トポロジ(Node，Link)が、各リンクlinkの障害確率と共に前記トポロジ取得部１０１により取得される。ステップＳ２では、ネットワークのトポロジが、前記トポロジ変形部１０２により図４のように仮想的に変形される。
【００３６】
すなわち、各配信ノードsの上流側に一つの擬似発ノードvsを仮想的に設けて各配信元ノードsと仮想リンクvlinkで接続する。各仮想リンクvlinkの障害確率はゼロとし、各仮想リンクvlinkの容量は、接続している各配信元ノードsが保有している部分コンテンツ数C(s)に相当する値に設定する。このようなネットワーク変形により、各配信元ノードsが保持している部分コンテンツ数C(s)を考慮してコンテンツ配信経路を計算できるようになる。
【００３７】
ステップＳ３では、部分コンテンツを保持しているS個の各配信元ノードsから各配信先ノードdに至る、互いに共通のリンクを含まないリンク独立経路の最大数mが、前記第１求解部１０２において、以下の第１の整数計画法を解くことにより求められる。第１の整数計画法では、各定数が以下のように定義される。
【００３８】
・node：ネットワークを構成するノード
・Node：擬似発ノードを除くノードnodeの集合
・d：配信先ノード
・link：ネットワークを構成するリンク
・Link：仮想リンクを含むリンクlinkの集合
・vs：擬似発ノード
・vlink：仮想リンク
・VLink：仮想リンクの集合
・s(vlink)：仮想リンクvlinkが接続する配信元ノード
・Cs(vlink)：配信元ノードs(vlink)が保有している部分コンテンツ数
・Clink：仮想リンクを除く各リンクlinkの容量
・INnode：ノードnodeを終点とするリンクの集合
・OUTnode：ノードnodeを始点とするリンクの集合
【００３９】
また、本実施形態では変数が以下のように定義される。
・xlink：リンクlinkを通過するリンク独立経路の本数を表す整数変数
・m：リンク独立な経路の本数
【００４０】
前記第１求解部１０２における第１の整数計画法では、制約式が次式(1)〜(4)で与えられる。これらは経路保存則に係り、(1)式は、擬似発ノードvsから出る経路の総数がリンク独立な経路数mと等しくなるという制約である。(2)式は、各配信先ノードdに入る経路数がmであるという制約である。(3)式は、各配信先ノードdから出る経路数がゼロであるという制約である。(4)式は、擬似発ノードvsおよび配信先ノードd以外のノード（中継ノード）では、入る経路数と出る経路数とが同一であるという制約である。
【００４１】
【数１】
2014200003.tif 000003
【００４２】
【数２】
2014200003.tif 000004
【００４３】
【数３】
2014200003.tif 000005
【００４４】
【数４】
2014200003.tif 000006
【００４５】
また、本実施形態では全ての経路がリンク独立でなければならず、各リンクを複数の経路が通ることは無いので、次式(5)がリンク独立の条件として与えられる。
【００４６】
【数５】
2014200003.tif 000007
【００４７】
さらに、本実施形態では各配信元ノードsが保持する部分コンテンツ数の制約条件が次式(6)で与えられる。これは、擬似発ノードvsと各配信元ノードsとを結ぶ仮想リンクvlinkを通過する経路の本数、すなわち配信元ノードsから配信される部分コンテンツ数は、各配信元ノードsが保持している部分コンテンツ数を超えないという条件となる。
【００４８】
【数６】
2014200003.tif 000008
【００４９】
さらに、本実施形態ではリンクlinkの容量条件が次式(7)で与えられる。これは、各リンクlinkを通過するリンク独立な経路の本数が当該リンクClinkを越えないという条件となる。
【００５０】
【数７】
2014200003.tif 000009
【００５１】
ここで、最大化すべき目的関数Objは変数mなので、ステップＳ３では、上記の第１整数計画法を解くことにより、各配信先ノードに関して、配信元ノードからのリンク独立な経路の最大数mが求められる。そして、この最大数mおよび前記変数xlinkに基づいて全てのリンク独立経路が具体的に求まる。
【００５２】
一方、リンク独立な経路の最大数がmであるということは、各配信元ノードsから各配信先ノードdに至るN本の経路全てが、あるm本のリンク組に含まれる何れかのリンクを必ず通過することを意味する。したがって、D個の各配信先ノードdに関して求めたリンク独立な経路の最大数mの中の最小値をMとした時、リンク独立経路の最大数がMであるような配信先ノードdに至るN本の経路は、あるM本のリンクの何れかを通過することになる。本実施形態では、このようなN本の経路を、リンク容量は考慮しないで、できるだけ均等（整数単位で最も均等）にM本のリンクに分配することを考える。
【００５３】
ステップＳ４では、前記多重数計算部１０３において、N本の経路をM本のリンクに均等に配分するときに、N-K+1本の経路が含まれ得る最少のリンク数Fが算出される。すなわち、i (=1〜M)番目のリンクには、次式(8)で与えられるhi本の経路が配分される。
【００５４】
【数８】
2014200003.tif 000010
また、Hは次式(9)で与えられる。
【００５５】
【数９】
2014200003.tif 000011
【００５６】
リンク数Ｆは、配分される経路数の総和がN-K+1本以上となる最小リンク数として、次式(10)で与えられる。
【００５７】
【数１０】
2014200003.tif 000012
【００５８】
この時、M本のリンクの中のF本のリンクに障害が発生すると、リンク独立な経路の最大数がMであるような配信先ノードでは、部分コンテンツを転送するためのN本の経路のうち、必ずN-K+1本以上の経路が障害となる。リンクの容量制約によって、F本よりも少ないリンクの障害によって、ある配信先ノードに至るN-K+1本以上の経路が障害になる可能性もあるが、リンクの容量制約が全く存在しない場合でも、F重リンク障害によって、N-K+1本以上の経路が必ず障害になる。すなわち、ネットワーク符号化が全く実行されない場合でも、F重リンク障害によって、N-K+1個以上の部分コンテンツが損失となり、配信先ノードdでは元のコンテンツを復元できなくなる。
【００５９】
本実施例では、各リンクの障害確率は十分小さいと仮定して、何れかの配信先ノードで必ず元のコンテンツが復元できなくなるF重リンク障害以下の多重リンク障害のみを考慮する。すなわち、F重リンク障害以下の多重リンク障害が発生した時、元のコンテンツを復元できなくなる配信先ノード数の期待値が最小となるような配信経路の算出を考える。
【００６０】
そこで、本実施例では第二の整数計画法を解法して、元のコンテンツを復元できない配信先ノード数の期待値を最小化するような、D個の配信先ノードへ至るそれぞれN本の配信経路が算出される。この時、N個の部分コンテンツをG個のグループに分割し、各中継ノードは、同一グループに属して配信先ノードが異なる部分コンテンツに対してのみ、ネットワーク符号化を適用する。そして、ある部分コンテンツが失われた場合は、ネットワーク符号化が適用される可能性がある当該失われた部分コンテンツと同一グループに属する部分コンテンツのみが同時に失われたと考える。
【００６１】
そこで、ステップＳ５以降では、各リンクの障害確率は十分に小さいと仮定して、F重リンク障害以下の多重リンク障害のみを考慮し、N-K+1個以上の部分コンテンツに損失が生じ得るF重リンク障害以下の多重リンク障害の発生確率を最小化するN本の配信経路が、前記第２求解部１０４において、第２の整数計画法により求解される。
【００６２】
本実施形態では、第２の整数計画法における定数および集合が以下のように定義される。なお、前記と同一の符号は同一または同等部分を表しているので、その説明は省略する。
【００６３】
・Dest：配信先ノードの集合
・FLink：仮想リンクを含まないF本以下のリンクの組合せの集合
・FLinkf：FLink内のf番目の組合せに含まれるリンクの集合
・Plink：予め与えられているリンクlinkの障害確率
・GPC g：グループg（1〜G）に属する配信経路の集合
・n g：グループg（1〜G）に属する配信経路数
【００６４】
また、第２の整数計画法における変数は以下の様に定義される。
・Xlink(d,n)：配信先ノードd(1〜D)に至るn（1〜N）番目の経路が、注目しているリンクlinkを通過する時に「1」、通過しない時に「0」であるバイナリ変数
・Clink(g)：グループgに属する経路による仮想リンクを除くリンクlinkの使用帯域を表す整数変数
・Yf(d,g)：リンク組合せFLink fの多重リンク障害によって、配信先ノードd（1〜D）において、グループg（1〜G）に属する部分コンテンツをネットワーク復号できない時「1」、復号できる時に「0」であるバイナリ変数
・Zf(d)：リンク組合せFLink fの多重リンク障害によって、配信先ノードd（1〜D）において、N-K+1個以上の部分コンテンツをネットワーク復号できず、元のコンテンツを復元できない時に「1」、復元できる時に「0」であるバイナリ変数
【００６５】
さらに、この第２の整数計画法では制約式が次式(11)〜(13)で与えられる。(11)式は、各N本の経路が、擬似発ノードから出る仮想リンクの中の１本だけを通ること、すなわちN本の経路は擬似発ノードから出る仮想リンクのいずれかを通るという経路保存則である。(12)式は、全ての配信経路は、配信先ノードに入るリンクのいずれかを１回だけ通過し、配信先ノードから出るリンクを通過することはないという経路保存則である。(13)式は、全ての経路は、擬似発ノードおよび配信先ノードd以外の中継ノードを始点とするリンクおよび終点とするリンクを１回だけ通過するか、どちらも通過しないという経路保存則である。
【００６６】
【数１１】
2014200003.tif 000013
【００６７】
【数１２】
2014200003.tif 000014
【００６８】
【数１３】
2014200003.tif 000015
【００６９】
また、本実施形態では仮想リンクvlinkの容量条件が次式(14)で与えられる。これは、擬似発ノードvsと各配信元ノードsとを結ぶ仮想リンクvlinkを通過する経路の本数、すなわち配信元ノードsから配信される部分コンテンツ数は、当該配信元ノードsが保持している部分コンテンツ数を超えないという条件となる。
【００７０】
【数１４】
2014200003.tif 000016
【００７１】
グループ別のネットワーク符号化を採用すれば、各中継ノードでは、同一グループに属して配信先ノードが異なる複数の部分コンテンツを１つの部分コンテンツに符号化して出リンクに転送することができる。すなわち、同一グループに所属して異なる配信先ノードに至る複数の配信経路は、互いに出リンク帯域を共用することができる。従って、各リンクの使用帯域は、各グループにおいて当該リンクを通過して各配信先ノードに至る配信経路数の最大数を算出し、算出した最大数を全グループについて加算した値となる。
【００７２】
図５は、グループ別のネットワーク符号化により中継ノードの出リンクにおいて帯域が複数の経路により共有される様子を模式的に表現した図であり、横軸はD個の配信先ノードdを示し、縦軸はN個の配信経路を示している。
【００７３】
グループ１に所属する配信先ノード２に至る配信経路１と配信先ノード３に至る配信経路１は、互いにリンク帯域を共用できる。また、グループ１に所属する配信先ノード１に至る配信経路２と配信先ノード２に至る配信経路２と配信先ノード３に至る配信経路２とは、互いにリンク帯域を共用できる。更に、グループ２に所属する配信先ノード２に至る配信経路n1+2と配信先ノードDに至る配信経路n1+2とは、互いにリンク帯域を共用できる。最後に、グループ２に所属する配信先ノード１に至る配信経路n1+n2と配信先ノード２に至る配信経路n1+1は、互いにリンク帯域を共用できる。
【００７４】
以上より、本リンクの使用帯域は、グループ１に所属して各配信先ノードに至る配信経路数の中で最大である配信先ノード３に至る配信経路数3と、グループ２に所属して各配信先ノードに至る配信経路数の中で最大である配信先ノード２に至る配信経路数2とを加算した値である5となる。
【００７５】
このように、ネットワーク符号化を適用すれば、宛先の異なる複数の部分コンテンツを一つの符号化部分コンテンツにまとめられるので、第２の整数計画法における各リンクの容量制約は以下のようになる。
【００７６】
次式(15)は、ネットワーク符号化を前提としたリンク容量の制約である。各グループに属する部分コンテンツによる各リンクの使用帯域は、当該リンクを通過して各配信先ノードに至る配信経路数のうちの最大数となり、各リンクの使用帯域は、リンク容量以下でなければならない。
【００７７】
【数１５】
2014200003.tif 000017
【００７８】
【数１６】
2014200003.tif 000018
【００７９】
一方、あるグループ内でネットワーク符号化された部分コンテンツがリンク障害によって失われると、配信先ノードdでは、当該グループに属する全ての部分コンテンツをネットワーク復号できなくなる可能性がある。そこで、各部分コンテンツが損失した場合は、当該部分コンテンツと同一のグループに属する全ての部分コンテンツが、配信先ノードにおいてネットワーク復号化できないと考える。これにより、各中継ノードにおけるネットワーク符号化の際の部分コンテンツの組合せ法を考慮することなく、信頼性に関して安全側のコンテンツ配信経路を計算できる。
【００８０】
例えば、図５に示したリンクに障害が発生すると、配信先ノード１に関しては、部分コンテンツ２と部分コンテンツn1+n2のみが損失となるが、ネットワーク符号化の適用可能性があるグループ１およびグループ２に属するn1+n2個の全ての部分コンテンツがネットワーク復号化できなくなると考える。この時、第２の整数計画法における制約条件は次式の様になる。
【００８１】
次式(17)は、各々の多重リンク障害によって、各配信先ノードにおける部分コンテンツのネットワーク復号ができない条件である。
【００８２】
【数１７】
2014200003.tif 000019
【００８３】
次式(18)は、各々の多重リンク障害によって、各配信先ノードにおける元のコンテンツの復元ができない条件である。なお、符号Aは十分大きな値を持つ正定数である。
【００８４】
【数１８】
2014200003.tif 000020
【００８５】
本発明の目的は、F重リンク障害以下の多重リンク障害によって、N個の部分コンテンツのうち、N-K+1本個以上の部分コンテンツが復元できなくなって元のコンテンツを復元できなくなる配信先ノード数の期待値を最小化することであるから、最小化すべき目的関数は、次式(19)で与えられ、第２の整数計画法を解法することによって得られるXlink(d,n)の値から、各配信先ノードdに至るN本の経路が計算される。
【００８６】
【数１９】
2014200003.tif 000021
【００８７】
図３へ戻り、ステップＳ６では、前記第２の整数計画法を解法することによって得られるXlink(d,n)の値から、配信先ノードdに至るn番目の経路の通過リンクが計算され、計N本の経路の通過リンク情報が、前記経路通知部６から対応する各配信元ノードsへ通知される。このとき、各部分コンテンツが属するグループ識別子IDgも併せて通知され、各配信元ノードsは、各部分コンテンツを配信する際に、そのグループ識別子IDgを付して配信する。これにより、各中継ノードは各部分コンテンツの所属グループを認識できるので、同一グループに属する部分コンテンツ同士のみにネットワーク符号化を適用できるようになる。
【００８８】
本発明によれば、複数のノードで閾値秘密分散保持されているコンテンツを複数の配信先ノードまでネットワークを介して同時転送する際に、ネットワーク符号化を用いてリンク帯域の有効利用を図りつつ、多重リンク障害によって元のコンテンツが復元できなくなる配信先ノード数の期待値を最小化する高信頼なコンテンツ配信経路の計算が可能となる。
【００８９】
また、本実施形態によれば、部分コンテンツを複数のグループに分割し、同一グループの部分コンテンツに対してのみネットワーク符号化を適用することで、リンク帯域の有効利用は制限されるものの、多重リンク障害によって元のコンテンツを復元できなくなる配信先ノード数の期待値をより小さくするコンテンツ配信経路の計算が可能となる。
【００９０】
さらに、本実施形態によれば、各部分コンテンツが損失した場合は、当該部分コンテンツと同一グループに属する全ての部分コンテンツが損失したと見なすことにより、各中継ノードにおいてネットワーク符号化される部分コンテンツの実際の組合せを考慮することなく、信頼性に関して安全側のコンテンツ配信経路を簡易に計算できるようになる。
【００９１】
[第２実施例]
次いで、本発明の第２実施形態について説明する。図６は、前記配信経路計算サーバ（コンピュータ）１の主要部の構成を示した機能ブロック図であり、本発明の説明に不要な構成は図示が省略されている。本実施形態では、多重リンク障害によって元のコンテンツを復元できなくなる配信先ノード数の期待値を小さくするコンテンツ配信経路が、各リンクのコストを更新しながら、最小コスト経路計算によって逐次的に設定される。
【００９２】
トポロジ取得部２０１は、図１に示した監視対象ネットワークNWの実トポロジを各リンクの障害確率と共に取得する。トポロジ変形部２０２は、前記ネットワークNWの実トポロジを、前記第１実施形態と同様に、図４に示した仮想トポロジに変換する。リンク独立経路数算出部２０３は、複数の配信元ノードsから各配信先ノードdへ至るリンク独立な経路の最大数mを、後述する整数計画法により求解する。
【００９３】
経路設定部２０４は、ネットワークを構成する各リンクlのコストCost lを更新するリンクコスト更新部２０４ａを備える。そして、逐次的な経路計算の各段階で、各リンクlのコストCost lを更新しながら、各配信先ノードdへ至る既設の経路数がN本になるまで、最小コスト経路の計算を繰り返して配信経路に追加する。経路通知部２０５は、前記各配信先ノードdへ至るN本の最小コスト経路の設定結果を、対応する各配信元ノードsへ通知する。
【００９４】
次いで、フローチャートを参照して本実施形態の動作を説明する。図７は、第２実施形態に係るコンテンツ配信経路の設定手順を示したフローチャートである。
【００９５】
ステップＳ２０では、ネットワークの実トポロジ(Node，Link)および各リンクlの障害確率が前記トポロジ取得部２０１により取得される。ステップＳ２１では、コンテンツ配信経路を算出するためのネットワークが、前記トポロジ変形部２０２により、前記図４のように仮想的に変形される。
【００９６】
ステップＳ２２では、配信先ノードdの識別子iに初期値(=1)がセットされる。ステップＳ２３では、部分コンテンツを保持しているS個の配信元ノードsから今回の配信先ノードd(i)に至る多数の経路のうち、互いに共通のリンクを含まないリンク独立な経路の最大数mが、前記リンク独立経路数算出部２０３において、以下の整数計画法を解くことにより求められる。ここでは、整数計画法の定数が以下のように定義される。
・node：ネットワークを構成するノード
・Node：擬似発ノードを除くノードnodeの集合
・d：配信先ノード
・link：ネットワークを構成するリンク
・Link：仮想リンクを含むリンクlinkの集合
・vs：擬似発ノード
・vlink：仮想リンク
・VLink：仮想リンクの集合
・s(vlink)：仮想リンクvlinkが接続する部分コンテンツ保持ノード
・Cs(vlink)：配信元ノードs(vlink)が保有している部分コンテンツ数
・INnode：ノードnodeを終点とするリンクの集合
・OUTnode：ノードnodeを始点とするリンクの集合
【００９７】
また、本実施形態では変数が以下の様に定義される。
・x link：：リンクlinkを通過するリンク独立経路の本数を表す整数変数。
・m：リンク独立な経路の数。
【００９８】
前記リンク独立経路数算出部２０３における整数計画法では、制約式が前記第１実施形態と同様に上式(1)〜(4)で与えられる。これらは経路保存則に関する。また、本実施形態でも全ての経路がリンク独立でなければならず、各リンクを複数の経路が通ることは無いので、上式(5)がリンク独立の条件として与えられる。さらに、仮想リンクvlinkの容量条件が上式(6)で与えられる。
【００９９】
ここで、最大化すべき目的関数Objは変数mなので、ステップＳ２３では、上記の整数計画法を解いてリンク独立な経路数の最大数mが求められる。最大化された目的関数mの値が、今回の配信先ノードd(i)までのリンク独立な経路の最大数である。ステップＳ２４では、各リンクコストCost lの初期値が算出される。
【０１００】
ステップＳ２５ないしＳ２９では、前記経路設定部２０４において、既設経路数nがN本になるまで、ネットワークを構成する各リンクlのコストCost lをリンクコスト更新部２０４ａで更新しながら、擬似発ノードvsから各配信元ノードsを経由して今回の配信先ノードd(i)へ至る最小コスト経路が逐次的に計算される。この時、N個の部分コンテンツをG個のグループに分割し、各中継ノードは、同一グループに属して配信先ノードが異なる部分コンテンツに対してのみネットワーク符号化を適用する。最小コスト経路の計算順序は、あるグループに属する全ての部分コンテンツのための経路計算を行った後、次のグループに属する部分コンテンツのための経路計算を行う。
【０１０１】
すなわち、ステップＳ２５では、既設の経路数nが初期化(=0)される。ステップＳ２６では、各リンクのコストが算出される。ステップＳ２７では、擬似発ノードvsから配信先ノードd(i)へ至る最小コスト経路が、前記ステップＳ２６で更新された各リンクコストCost lに基づいて計算される。各リンクコストCost lの更新方法および最小コスト経路の算出方法は、後に詳述する。
【０１０２】
ステップＳ２８では、前記計算された最小コスト経路が既設経路として追加され、前記既設経路数nがインクリメントされる。ステップＳ２９では、前記既設経路数nとNとが比較され、経路数nがNに達していなければ、前記ステップＳ２６へ戻って上記の各処理が繰り返される。
【０１０３】
既設の経路数がN本になると、ステップＳ３０では、配信先ノードdの識別子iがインクリメントされる。ステップＳ３１では、全ての配信先ノードdに対して上記の各処理が完了したか否かが判定される。完了していなければ前記ステップＳ２３へ戻り、配信先ノードdを切り替えながら上記の各処理が繰り返される。
【０１０４】
前記ステップＳ２７において最小コスト経路を計算する際は、各仮想リンクの容量制約を満足する必要がある。すなわち、ある仮想リンクvlinkを通過して配信先ノードd(i)まで設定された配信経路の数が、当該仮想リンクの容量に達した場合は、当該仮想リンクのコストをゼロから十分大きな値に変更する。
【０１０５】
最小コスト経路計算を繰り返し実行する際の各リンクのコストCost lは、最小コスト経路計算によって、既にN本の配信経路が決定しているi-1個の配信先ノードdの中で、元のコンテンツを復元できなくなる配信先ノード数の期待値と、今回の配信先ノードd(i)においてN -K+1個以上の部分コンテンツを復元できなくなる確率との和が最小化される経路が得られるように設定される。
【０１０６】
但し、各リンクの使用帯域は、各グループにおいて当該リンクを通過して各配信先ノードに至る配信経路数の最大数を算出し、算出した最大数を全グループについて加算した値と見なす。従って、ネットワーク符号化を考慮したリンク容量制約に基づき、最小コスト経路計算によって新たに算出する配信経路が、あるリンクを通過することにより、当該リンクの使用帯域がリンク容量を超える場合は、当該リンクのコストを十分大きな値に設定する。
【０１０７】
また、あるグループ内でネットワーク符号化された部分コンテンツがリンク障害によって損失すると、配信先ノードdでは、当該グループに属する全ての部分コンテンツをネットワーク復号化できなくなる可能性がある。そこで、配信先ノードdに転送されるべき部分コンテンツが損失した場合は、配信先ノードdに転送される当該部分コンテンツと同一グループに属する全ての部分コンテンツが損失したと考える。これにより、各中継ノードにおけるネットワーク符号化する部分コンテンツの実際の組合せを考慮することなく、信頼性に関して安全側のコンテンツ配信経路を計算できる。
【０１０８】
次いで、前記図７のステップＳ２４で求められる各リンクコストの初期値Cost 0について説明する。リンクコストの初期値Cost 0は、全てのリンクで共通であり、既にN本の配信経路が決定しているd-1個の配信先ノードの中で、元のコンテンツが復元できなくなる配信先ノード数の期待値に対応している。すなわち、ある多重リンク障害によって、d-1個の各々の配信先ノードにおいて元のコンテンツが復元できなくなる場合、当該多重リンク障害の発生確率がリンクコストの初期値Cost 0に加算される。
【０１０９】
その際、ある配信先ノードに転送されるべき部分コンテンツが損失となる場合は、当該配信先ノードに転送される同一グループに所属する全ての部分コンテンツが損失になると考える。そして、ある配信先ノードに転送されるN-K+1個以上の部分コンテンツが損失になる場合、多重リンク障害の発生確率がリンクコストの初期値Cost 0に加算される。
【０１１０】
前記ステップＳ２３で算出された配信先ノードdまでのリンク独立な経路の最大数をm本とすると、リンクコストの初期値Cost 0は、最大m重リンク障害まで考慮して算出する。この時、各リンクの障害確率は十分小さいと仮定して、f（=1〜m）重リンク障害によって、リンクコスト初期値Cost 0が正の値になった場合は、fよりも大きい多重リンク障害は考慮しない。前記ステップＳ２６において、各リンクのコストを更新しながら、配信先ノードdに向かうN本の配信経路を逐次的に算出する。各リンクlのコストCost lは、当該リンクlのコスト更新値を、前記ステップＳ２４で算出したリンクコスト初期値Cost 0に加算して得られる。
【０１１１】
リンクlのコスト更新値は、既に算出されたn-1本の配信経路および新たに算出するn本目の配信経路が属するグループ群に含まれる経路の総数がN-K+1本以下の時は、新たな配信経路がリンクlを通ることによって、配信先ノードdに転送される全ての部分コンテンツが損失になる確率とする。また、既に算出されたn-1本の配信経路および新たに算出されるn本目の配信経路が属するグループ群に含まれる経路の総数がN-K+1本を超える時は、新たな配信経路がリンクlを通ることによって、配信先ノードdに転送されるN-K+1個以上の部分コンテンツが損失になる確率とする。但し、配信先ノードdに転送される１個の部分コンテンツが損失になる場合、配信先ノードdに転送される同一グループに所属する全ての部分コンテンツが損失になると考える。
【０１１２】
図８は、前記図７のステップＳ２４で実行される各リンクコストの初期値Cost 0の算出手順を示したフローチャートである。ここでは、ある多重リンク障害によって、全ての配信経路が既に決定しているd-1個の各配信先ノードにおいて元のコンテンツを復元できなくなる場合、当該多重リンク障害の発生確率が、リンクコストの初期値に加算される。
【０１１３】
ステップＳ６１では、コストCost 0がリセット(=0)され、リンク障害の多重数fが初期化(=1)される。ステップＳ６２では、f本のリンクの組合せが列挙されてリストが構成される。ステップＳ６３では、前記リストからリンクの組合せが１つずつ取り出されて多重リンク障害が想定される。
【０１１４】
ステップＳ６４では、注目する配信先ノードdを特定する識別子iが初期化(=1)される。ステップＳ６５では、配信先ノードd(i)に至るN-K+1個以上の部分コンテンツが失われているか否かが判定される。失われていればステップＳ６６へ進み、その多重リンク障害確率がコストCost 0に加算される。
【０１１５】
ステップＳ６７では、注目する配信先ノードdを特定する識別子iが更新される。ステップＳ６８では、識別子iと配信先ノード数dとが比較される。i＜dであればステップＳ６５へ戻り、配信先ノードdを切り替えて上記の各処理が繰り返される。ステップＳ６９では、全てのリンク組合せの取り出しが完了したか否かが判定される。完了していなければステップＳ６３へ戻り、リンク組合せを切り替えながら上記の各処理が繰り返される。
【０１１６】
その後、全てのリンク組合せの取り出しが完了するとステップＳ７０へ進み、コストCost 0がゼロであるか否かが判定される。ゼロでなければ当該処理を終了し、ゼロであればステップＳ７１へ進む。ステップＳ７１では、リンク組合せ数fとmとが比較され、f＜mでなければ当該処理を終了し、f＜mであれば、ステップＳ７２でfを更新（f=f＋1）してステップＳ６２へ戻る。
【０１１７】
次いで、前記図７のステップS２６で実行されるリンクコストCost lの算出手順について説明する。本実施形態では、初めにリンクlのコストCost lがリンクコスト初期値Cost 0に設定される。そして、新たに算出するn本目の配信経路がリンクlを通過すると仮定し、既に算出されたn-1本の配信経路および新たに算出するn本目の配信経路が属するグループ群に含まれる経路の総数がN-K+1本以下の時は、ある多重リンク障害によって、配信先ノードdに転送される全ての部分コンテンツが損失になる場合、当該多重リンク障害の発生確率がリンクコストCost lに加算される。
【０１１８】
また、既に算出されたn-1本の配信経路および新たに算出するn本目の配信経路が属するグループ群に含まれる経路の総数がN-K+1本を超える時は、ある多重リンク障害によって、配信先ノードdに転送されるN-K+1個以上の部分コンテンツが損失になる場合、当該多重リンク障害の発生確率がリンクコストCost lに加算される。
【０１１９】
前記図７のステップＳ２３で算出された配信先ノードdまでのリンク独立な経路の最大数をm本とすると、リンクコストCost lは、最大m重リンク障害まで考慮して算出される。この時、各リンクの障害確率は十分小さいと仮定して、f（=1〜m）重リンク障害によって、リンクコストCost lがリンクコスト初期値Cost 0から増加した場合は、fよりも大きい多重リンク障害は考慮しない。
【０１２０】
図９は、前記リンクコストCost lの算出手順を示したフローチャートであり、ステップＳ８１では、コストCost lが初期値にセットされ、リンク障害の多重数fが初期化(=1)される。ステップＳ８２では、f本のリンクの組合せが列挙されてリストが構成される。ステップＳ８３では、前記リストからリンクの組合せが１つずつ取り出されて多重リンク障害が想定される。
【０１２１】
ステップＳ８４では、既に算出されたn-1本の配信経路および新たに算出するn本目の配信経路が属するグループ群に含まれる経路の総数がN-K+1本以下であるか否かが判定される。経路の総数がN-K+1本以下であればステップＳ８５へ進み、想定した多重リンク障害によって、新たな部分コンテンツも含めて全ての部分コンテンツが損失するか否かが判定される。全ての部分コンテンツが損失すればステップＳ８７へ進み、その多重リンク障害確率がリンクコストCost lに加算される。全ての部分コンテンツが損失しなければ、前記リンクコストCost lへの加算なしにステップ８８に進む。
【０１２２】
これに対して、経路の総数がN-K+1本以下でなければステップＳ８６へ進み、想定した多重リンク障害によって、新たな部分コンテンツも含む全ての部分コンテンツの中のN-K+1個以上の部分コンテンツが損失になるか否かが判定される。N-K+1個以上の部分コンテンツが損失すれば前記ステップＳ８７へ進み、その多重リンク障害確率がリンクコストCost lに加算される。N-K+1個未満の部分コンテンツの損失であれば、前記リンクコストCost lへの加算なしにステップＳ８８へ進む。
【０１２３】
ステップＳ８８では、全てのリンク組合せの取り出しが完了したか否かが判定される。完了していなければステップＳ８３へ戻り、リンク組合せを切り替えながら上記の各処理が繰り返される。
【０１２４】
その後、全てのリンク組合せの取り出しが完了するとステップＳ８９へ進み、リンクコストCost lが初期値のままであるか否かが判定される。初期値のままでなければ当該処理を終了し、初期値のままであればステップＳ９０へ進む。ステップＳ９０では、リンク組合せ数fとmとが比較され、f＜mでなければ当該処理を終了し、f＜mであれば、ステップＳ９１へ進んでリンク組合せ数fを更新（f=f+1）した後にステップＳ８２へ戻る。
【０１２５】
図１０は、リンクコストの算出例を模式的に示した図であり、ここでは、配信先ノードdに向かう３本の配信経路P1、P2、P3が既に算出されており、配信経路P1，P2によって１グループが構成され、配信経路P3と新たに経路を算出する４本目の配信経路P4とは個別に１グループを構成すると仮定する。また、N-K+1＞３と仮定する。
【０１２６】
この時、４本目の配信経路P4を算出する場合、リンクl1のコストCost l1は、リンクl1およびリンクl3の２重リンク障害の発生確率とリンクl1およびリンクl4の２重リンク障害の発生確率とをリンクコスト初期値に加算することによって算出される。また、リンクl2のコストCost l2は、配信経路P3が障害になる単一リンク障害の発生確率とリンクl2の障害確率との積をリンクコスト初期値に加算することによって得られる。更に、リンクl3のコストCost l3は、リンクl3の障害確率をリンクコスト初期値に加算することによって得られる。リンクl4のコストCost l4は、リンクl4の障害確率をリンクコスト初期値に加算することによって得られる。
【０１２７】
同様に、N-K+1=３と仮定すれば、４本目の配信経路P4を算出する場合、リンクl1のコストCost l1は、リンクl3の障害確率とリンクl4の障害確率とをリンクコスト初期値に加算した値に設定する。また、リンクl2のコストCost l2は、リンクl2の障害確率とリンクl3の障害確率とリンクl4の障害確率とをリンクコスト初期値に加算した値に設定する。更に、リンクl3のコストCost l3は、リンクl3の障害確率とリンクl4の障害確率とをリンクコスト初期値に加算した値に設定する。リンクl4のコストCost l4も、リンクl3の障害確率とリンクl4の障害確率とをリンクコスト初期値に加算した値に設定する。
【０１２８】
本実施例によれば、複数のノードで閾値秘密分散保持されているコンテンツを複数の配信先ノードまでネットワークを介して同時転送する際に、ネットワーク符号化を用いてリンク帯域の有効利用を図りつつ、多重リンク障害によって、元のコンテンツを復元できなくなる配信先ノード数の期待値を小さくする高信頼なコンテンツ配信経路の計算が可能となる。
【０１２９】
また、本実施形態によれば、リンクコストを更新しながら、最小コスト経路計算法を用いて、各部分コンテンツを各配信先ノードまで配信するための経路を１本ずつ逐次的に算出することにより、コンテンツ配信経路を高速に計算できる。
【０１３０】
さらに、本実施形態によれば、部分コンテンツを複数のグループに分割し、同一グループ内の部分コンテンツに対してのみネットワーク符号化を適用することで、リンク帯域の有効利用は制限されるものの、多重リンク障害によって元のコンテンツを復元できなくなる配信先ノード数の期待値をより小さくするコンテンツ配信経路の計算が可能となる。
【０１３１】
さらに、本実施形態によれば、各部分コンテンツが損失した場合は、当該部分コンテンツと同一グループに属する全ての部分コンテンツが損失したと見なすことにより、各中継ノードにおけるネットワーク符号化する部分コンテンツの実際の組合せを考慮することなく、信頼性に関して安全側のコンテンツ配信経路を簡易に計算できる。
【符号の説明】
【０１３２】
１…配信経路計算サーバ、１００，２０１…トポロジ取得部、１０１，２０１…トポロジ変形部，１０２…第１求解部、１０３…多重数計算部、１０４…第２求解部、１０５…経路通知部、２０３…リンク独立経路数出部、２０４…経路設定部、２０４ａ…リンクコスト更新部、２０５…経路通知部
【図１】
2014200003.tif 000022
【図２】
2014200003.tif 000023
【図３】
2014200003.tif 000024
【図４】
2014200003.tif 000025
【図５】
2014200003.tif 000026
【図６】
2014200003.tif 000027
【図７】
2014200003.tif 000028
【図８】
2014200003.tif 000029
【図９】
2014200003.tif 000030
【図１０】
2014200003.tif 000031