(57)【特許請求の範囲】
【請求項１】
配信対象のコンテンツが(K，N)閾値秘密分散法によりN分割されてネットワーク上の配信元ノードに分散配置され、各配信元ノードから配信先ノードへ複数の経路で各部分コンテンツを配信するコンテンツ配信システムの配信経路計算装置において、
ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数の値mを第１の整数計画法で求解する第１求解手段と、
N本の経路をm本のリンクに均等に配分するときに、N-K+1本の経路が含まれ得る最少のリンク数Fを算出する多重数算出手段と、
N-K+1本以上の経路が含まれるF本のリンクで構成されるリンク組でＦ重リンク障害が発生する確率を最少化するN本の経路を第２の整数計画法で求解する第２求解手段とを具備したことを特徴とするコンテンツ配信システムの配信経路計算装置。
【請求項２】
前記ネットワークのトポロジを、各配信元ノードの上流側に擬似発ノードが仮想的に設けて各配信元ノードと仮想リンクで接続された仮想トポロジに変換する仮想トポロジ変換手段をさらに具備し、
前記第１求解手段および第２求解手段は、各配信元ノードと接続される各仮想リンクの容量を、当該配信元ノードが保有している部分コンテンツ数に相当する値に設定し、前記擬似発ノードから各仮想リンクおよび各配信元ノードを経由して配信先ノードへ至る経路を求解することを特徴とする請求項１に記載のコンテンツ配信システムの配信経路計算装置。
【請求項３】
配信対象のコンテンツが(K，N)閾値秘密分散法によりN分割されてネットワーク上の配信元ノードに分散配置され、各配信元ノードから配信先ノードへ各部分コンテンツを配信するための経路を計算するコンテンツ配信システムの配信経路計算方法において、
コンピュータが、ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数の値mを第１の整数計画法で求解する手順と、
コンピュータが、N本の経路をm本のリンクに均等に配分するときに、N-K+1本の経路が含まれ得る最少のリンク数Fを算出する手順と、
コンピュータが、N-K+1本以上の経路が含まれるF本のリンクで構成されるリンク組でＦ重リンク障害が発生する確率を最少化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)ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数mを第１の整数計画法で求解する第１求解手段と、N本の経路をm本のリンクに均等に配分するときに、N-K+1本の経路が含まれ得る最少のリンク数Fを算出する多重数算出手段と、N-K+1本以上の経路が含まれるF本のリンク組でリンク障害が生じるＦ重リンク障害の発生確率を最少化するN本の経路を第２の整数計画法で求解する第２求解手段とを具備した。
【００１４】
(2)ネットワークのトポロジを、各配信元ノードの上流側に擬似発ノードを仮想的に設けて各配信元ノードと仮想リンクで接続した仮想トポロジに変換する仮想トポロジ変換手段をさらに設けた。そして、第１求解手段および第２求解手段は、各配信元ノードと接続される仮想リンクの容量を、当該配信元ノードが保有している部分コンテンツ数に相当する値に設定し、擬似発ノードから各仮想リンクおよび各配信元ノードを経由して配信先ノードへ至る経路を求解するようにした。
【発明の効果】
【００１５】
本発明によれば、以下のような効果が達成される。
【００１６】
(1)複数の配信元ノードで閾値秘密分散保持されているN個の部分コンテンツを配信先ノードまでネットワークを介して転送する際に、多重リンク障害によって転送途中のN-K+1個以上の部分コンテンツが損失する確率を最小化することにより、配信先ノードで元のコンテンツを復号できる確率を最大化する高信頼なコンテンツ配信経路の最適計算が可能となる。
【００１７】
(2)各配信元ノードの上流側に擬似発ノードを仮想的に設けると共に、擬似発ノードと各配信元ノードとを接続する仮想リンクの容量が、当該配信元ノードが保有している部分コンテンツ数に相当する値に設定されるので、各配信元ノードが保持する部分コンテンツ数を考慮した経路計算が可能になる。
【図面の簡単な説明】
【００１８】
【図１】本発明が適用されるコンテンツ配信システムのネットワーク構成を示した図である。
【図２】配信経路計算サーバの機能ブロック図である。
【図３】本発明の一実施形態の動作を示したフローチャートである。
【図４】リンク独立経路が確立される様子を示した図である。
【発明を実施するための形態】
【００１９】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明の配信経路計算方法および装置が適用されるコンテンツ配信システムのネットワーク構成を示した図であり、ここでは、(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-K+1個以上の部分コンテンツの損失を引き起こす確率を最小化するN本の配信経路を算出する。
【００２４】
図２は、前記配信経路算出サーバ（コンピュータ）１の主要部の構成を示した機能ブロック図であり、本発明の説明に不要な構成は図示が省略されている。
【００２５】
トポロジ取得部１００は、前記ネットワークのトポロジを取得する。トポロジ変形部１０１は、図１に示した監視対象ネットワークNWの実トポロジを、後に詳述するように、図４に示した仮想トポロジに変換する。第１求解部１０２は、各配信元ノードsnode(s)から配信先ノードdへ至るリンク独立な経路の最大数mを、後述する第１の整数計画法により求解する。
【００２６】
多重数計算部１０３は、N個の部分コンテンツを転送するためのN本の経路を、配信元ノードsnodeと配信先ノードdとの間の最小カットセットを構成するm個のリンクに均等に配分するときに、N-K+1本の経路が含まれる最少のリンク組数Ｆを算出する。第２求解部１０４は、N-K+1本以上の経路が含まれることになるF本のリンク組でリンク障害が生じるＦ重リンク障害の発生確率を最少化するN本の経路を、後述する第２の整数計画法により求解する。経路通知部１０５は、前記N本の経路の決定結果を、対応する各配信元ノードsnode(s)へ通知する。
【００２７】
次いで、本発明の一実施形態の動作を図３のフローチャートに沿って説明する。ステップＳ１では、ネットワークのトポロジ(Node，Link)が前記トポロジ取得部１００により取得される。ステップＳ２では、コンテンツ配信経路を算出するためのネットワークが、前記トポロジ変形部１０１により、図４の様に仮想的に変形される。
【００２８】
すなわち、配信ノードsnodeの上流側に擬似発ノードvsを仮想的に新たに設け、これを各配信元ノードsnodeと仮想リンクvlinkで接続する。各仮想リンクvlinkの障害確率はゼロとし、各仮想リンクvlinkの容量は、接続している配信元ノードsnodeが保有している部分コンテンツ数に相当する値に設定する。このようなネットワーク変形により、各配信元ノード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以外のノード（中継ノード）では、入る経路数と出る経路数とが同一であるという制約である。
【００３２】
【数１】
0005812424.tif 000002
【００３３】
【数２】
0005812424.tif 000003
【００３４】
【数３】
0005812424.tif 000004
【００３５】
【数４】
0005812424.tif 000005
【００３６】
また、本実施形態では全ての経路がリンク独立でなければならず、各リンクlinkを複数の経路が通ることは無いので、次式(5)がリンク独立の条件として与えられる。
【００３７】
【数５】
0005812424.tif 000006
【００３８】
さらに、本実施形態では仮想リンクvlinkの容量条件が次式(6)で与えられる。これは、擬似発ノードvsと各配信元ノードsnodeとを結ぶ仮想リンクvlinkを通過する経路の本数、すなわち当該配信元ノードsnodeから配信される部分コンテンツ数は、当該配信元ノードsnodeが保持している部分コンテンツ数を超えないという条件となる。
【００３９】
【数６】
0005812424.tif 000007
【００４０】
ここで、最大化すべき目的関数Objは変数Mなので、ステップＳ３では、上記の第１の整数計画法を解いてリンク独立な経路数Mの最大数mが求められる。そして、この最大数mおよび前記変数x linkに基づいて各リンク独立経路が具体的に求まる。
【００４１】
リンク独立な経路数Mの最大数mが求まると、次いで、N本の経路を、できるだけ均等（整数単位で最も均等）にm組に分割することを考える。ステップＳ４では、前記多重数計算部１０３において、N本の経路をm本のリンクに均等に配分するときに、N-K+1本の経路が含まれ得る最少のリンク数Fが算出される。
【００４２】
すなわち、i (=1〜m) 番目のリンクには、次式(7)で与えられるh i本の経路を配分する。
【００４３】
【数７】
0005812424.tif 000008
【００４４】
また、Hは次式(8)で与えられる。
【００４５】
【数８】
0005812424.tif 000009
【００４６】
この時、Ｆの値は、配分される経路数の総和がN-K+1本以上となる最小リンク数として、次式(9)で与えられる。
【００４７】
【数９】
0005812424.tif 000010
【００４８】
このようにして算出されたリンク数Fは、F重リンク障害が発生するとN-K+1個以上の部分コンテンツに損失が生じること、すなわち各リンク組に属するF本のリンクに損失が生じるとN-K+1個以上の部分コンテンツに損失が生じ得ること、を意味する。そこで、ステップＳ５以降では、各リンクの障害確率は十分に小さいと仮定してF重リンク障害のみを考慮し、N-K+1個以上の部分コンテンツに損失が生じ得るF重リンク障害の発生確率を最小化するN本の配信経路が、第２の整数計画法により求解される。
【００４９】
本実施形態では、第２の整数計画法における定数および集合が以下の様に定義される。なお、前記と同一の符号は同一または同等部分を表しているので、その説明は省略する。
・FLink：仮想リンクを含まないF本のリンクの組合せの集合
・FLink f：FLink内のf番目の組合せに含まれるリンクの集合
・Plink：予め与えられているリンクlinkの障害確率
【００５０】
また、第２の整数計画法における変数は以下の様に定義される。
・Xlink(n)：n（1〜N）番目の経路がリンクlinkを通過する時に「１」、通過しない時に「０」であるバイナリ変数
・Yf(n)：n（1〜N）番目の経路が、f番目のリンク組合せFLink fに含まれるリンクのいずれかを通過する時に「１」、通過しない時に「０」であるバイナリ変数
・Zf：N-K+1本以上の経路が、リンク組合せFLink fに含まれるリンクを通過する時に1.0、通過しない時に0.0に収束する実変数
【００５１】
さらに、この第２の整数計画法では制約式が次式(10)〜(12)で与えられる。(10)式は、各N本の経路が、擬似発ノードから出る仮想リンクの中の１本だけを通ること、すなわちN本の経路は擬似発ノードから出る仮想リンクのいずれかを通るという経路保存則である。(11)式は、全ての監視経路は、配信先ノードに入るリンクのいずれかを１回だけ通過し、配信先ノードから出るリンクを通過することはないという経路保存則である。(12)式は、全ての経路は、配信先ノードd以外の中継ノードを始点とするリンクおよび終点とするリンクを１回だけ通過するか、どちらも通過しないという経路保存則である。
【００５２】
【数１０】
0005812424.tif 000011
【００５３】
【数１１】
0005812424.tif 000012
【００５４】
【数１２】
0005812424.tif 000013
【００５５】
また、本実施形態ではm本の経路がリンク独立となり、このm本の経路では各リンクを複数の経路が通ることは無い、すなわち各リンクを通る経路数は「０または１」なので、1番目からm番目までの経路がリンク独立である条件を表す次式(13)が加えられる。
【００５６】
【数１３】
0005812424.tif 000014
【００５７】
さらに、本実施形態では仮想リンクvlinkの容量条件が次式(14)で与えられる。これは、擬似発ノードvsと各配信元ノードsnodeとを結ぶ仮想リンクvlinkを通過する経路の本数、すなわち当該配信元ノードsnodeから配信される部分コンテンツ数は、当該配信元ノードsnodeが保持している部分コンテンツ数を超えないという条件となる。
【００５８】
【数１４】
0005812424.tif 000015
【００５９】
さらに、本実施形態では次式(15)がネットワークを構成するリンクの容量条件となる。但し、次式(15)の不等式の右辺は、N / m 以上の最小整数を示す。本実施形態では、本制約により、各リンクを通過する部分コンテンツ数の最大値を最少化できるので、配信先ノードdで元のコンテンツの復号ができなくなるリンク障害多重数の最大化を保障できる。
【００６０】
【数１５】
0005812424.tif 000016
【００６１】
さらに、リンク組合せに含まれるリンクを経路が通過する条件として次式(16)が与えられる。
【００６２】
【数１６】
0005812424.tif 000017
【００６３】
さらに、各リンク組合せに含まれるリンクをN-K+1本以上の経路が通過してしまい、元のコンテンツの復号ができなくなる条件として次式(17)が与えられる。なお、Aは十分大きな値を持つ定数である。
【００６４】
【数１７】
0005812424.tif 000018
【００６５】
そして、本発明の目的は、F重リンク障害によって、N-K+1本以上の経路が障害になる確率を最小化することであるから、最小化すべき目的関数Objは次式(18)で与えられる。
【００６６】
【数１８】
0005812424.tif 000019
【００６７】
図３へ戻り、ステップＳ６では、前記第２の整数計画法を解法することによって得られるXlink(n)の値から、n番目の経路の通過リンクが算出され、計N本の経路の通過リンク情報が、前記経路通知部６から対応する各配信元ノードsnodeへ通知される。
【００６８】
本実施形態によれば、複数のノードで閾値秘密分散保持されているN個の部分コンテンツを配信先ノードdまでネットワークを介して転送する際に、多重リンク障害によって転送途中のN-K+1個以上の部分コンテンツが損失する確率を最小化して、配信先ノードdで元のコンテンツを復号できる確率を最大化する高信頼なコンテンツ配信経路の最適計算が可能となる。
【００６９】
さらに、本実施形態によれば、各配信元ノードの上流側に擬似発ノードを仮想的に設けると共に、擬似発ノードと各配信元ノードとを接続する仮想リンクの容量が、当該配信元ノードが保有している部分コンテンツ数に相当する値に設定されるので、各配信元ノードが保持する部分コンテンツ数を考慮した経路計算が可能になる。
【符号の説明】
【００７０】
１…配信経路算出サーバ，１００…トポロジ取得部，１０２…第１求解部，１０３…多重数計算部，１０１…トポロジ変形部，１０４…第２求解部，１０５…経路通知部
【図１】
0005812424.tif 000020
【図２】
0005812424.tif 000021
【図３】
0005812424.tif 000022
【図４】
0005812424.tif 000023