コンテンツ配信システムの配信経路決定装置
【課題】閾値秘密分散された複数の部分コンテンツや冗長化された複数の同一コンテンツを異なる経路で配信するシステムにおいて、盗聴や障害に対する信頼性の高い配信経路を決定できるコンテンツ配信システムの配信経路決定装置を提供する。
【解決手段】最大独立経路数求解部１０２は、各配信元ノードから配信先ノードへ至るリンク独立（第１実施形態）またはノード独立（第２実施形態）な経路の最大数mを算出する。配信経路決定部１０３は、配信先ノードへ配信する部分コンテンツの数kが最大数m以下であると当該m本の独立経路の中からk本の独立経路を決定する第１の配信経路決定部１０３ａ、および配信先ノードへ配信する部分コンテンツの数kが最大数mよりも多いと当該m本の独立経路を含むk本の経路を決定する第２の配信経路決定部１０３ｂを含む。経路通知部１０４は、前記k本の経路の決定結果を各配信元ノード１へ通知する。
【解決手段】最大独立経路数求解部１０２は、各配信元ノードから配信先ノードへ至るリンク独立（第１実施形態）またはノード独立（第２実施形態）な経路の最大数mを算出する。配信経路決定部１０３は、配信先ノードへ配信する部分コンテンツの数kが最大数m以下であると当該m本の独立経路の中からk本の独立経路を決定する第１の配信経路決定部１０３ａ、および配信先ノードへ配信する部分コンテンツの数kが最大数mよりも多いと当該m本の独立経路を含むk本の経路を決定する第２の配信経路決定部１０３ｂを含む。経路通知部１０４は、前記k本の経路の決定結果を各配信元ノード１へ通知する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテンツ配信システムの配信経路決定装置に係り、特に、一つのコンテンツを複数の部分コンテンツに分割してネットワーク上に分散配置し、これらの部分コンテンツを一つの配信先ノードへ複数の経路で配信する閾値秘密分散に好適なコンテンツ配信システムの配信経路決定装置に関する。
【背景技術】
【０００２】
１つのコンテンツを暗号化されたn個の部分コンテンツに分割し、n個の部分コンテンツのうち、k (<= n) 個以上の部分コンテンツが集まらないと元のコンテンツを復元できないように秘密分散する閾値秘密分散が非特許文献１に開示されている。
【０００３】
また、データ保持のリスク分散を図るために、n個に分割された部分コンテンツを複数のノードで秘密分散保持する技術が特許文献１，２に開示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Shamir, Adi (1979), "How to share a secret", Communications of the ACM 22 (11): 612-613
【特許文献】
【０００５】
【特許文献１】特開２００９−１２２７３１号公報
【特許文献２】特開２００９−１０５３１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
n個の部分コンテンツから任意のk個の部分コンテンツを集めれば元データを復元できるが(k-1)個の部分コンテンツからでは元データを復元できない（k，n）閾値秘密分散では、少なくともk個の部分コンテンツがネットワーク上の配信元ノードに分散配置され、元データを復元しようとする配信先ノードに対して、部分コンテンツを保持する配信元ノードから部分コンテンツが配信される。
【０００７】
このとき、各部分コンテンツの配信経路が同一リンクや同一ノードを通っていると、k本未満のリンクやk個未満のノードを盗聴するだけで元のデータが復元されてしまうので安全率が低下してしまう。したがって、（k，n）閾値秘密分散を適用したデータ配信では、できるだけk本の経路は同一リンクや同一ノードを通らない経路であることが望ましい。
【０００８】
また、閾値秘密分散以外であっても、同一コンテンツを複数の経路で配信する冗長化では、全ての経路が同一リンクや同一ノードを通過する場合はもちろん、一部の経路が同一リンクや同一ノードを通過する場合でも、リンク障害やノード障害に対する安全度が低下してしまう。
【０００９】
本発明の目的は、上記した従来技術の課題を解決し、閾値秘密分散された複数の部分コンテンツや冗長化された複数の同一コンテンツを異なる経路で配信するシステムにおいて、盗聴や障害に対する信頼性の高い配信経路を決定できるコンテンツ配信システムの配信経路決定装置を提供することにある。
【課題を解決するための手段】
【００１０】
上記の目的を達成するために、本発明は、以下のような手段を講じた点に特徴がある。
【００１１】
(1)配信対象のコンテンツを複数の部分コンテンツに分割してネットワーク上の配信元ノードに分散配置し、各配信元ノードから配信先ノードへ複数の経路で各部分コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数mを算出する手段と、配信先ノードへ配信する部分コンテンツの数kが前記最大数m以下であると、当該m本のリンク独立な経路の中からk本の経路を決定する第１の決定手段と、配信先ノードへ配信する部分コンテンツの数kが前記最大数mよりも多いと、当該m本のリンク独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、各決定手段は、各経路のリンクが盗聴される確率に基づいて、全ての経路が盗聴される確率が最小となるk本の経路の組み合わせを決定することを特徴とする。
【００１２】
(2)配信対象のコンテンツを複数の部分コンテンツに分割してネットワーク上の配信元ノードに分散配置し、各配信元ノードから配信先ノードへ複数の経路で各部分コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るノード独立な経路の最大数mを算出する手段と、配信先ノードへ配信する部分コンテンツの数kが前記最大数m以下であると、当該m本のノード独立な経路の中からk本の経路を決定する第１の決定手段と、配信先ノードへ配信する部分コンテンツの数kが前記最大数mよりも多いと、当該m本のノード独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、各決定手段は、各経路上のノードが盗聴される確率に基づいて、全ての経路が盗聴される確率が最小となるk本の経路の組み合わせを決定することを特徴とする。
【００１３】
(3)配信対象のコンテンツが（k，n）閾値秘密分散法に基づいてn分割され、各配信元ノードからは、n個の部分コンテンツの中のk個が重複無く配信されることを特徴とする。
【００１４】
(4)ネットワーク上の配信元ノードに複数の同一コンテンツを分散配置し、各配信元ノードから配信先ノードへ複数の経路で各コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数mを算出する手段と、配信先ノードへ配信するコンテンツの数kが前記最大数m以下であると、当該m本のリンク独立な経路の中からk本の経路を決定する第１の決定手段と、配信先ノードへ配信するコンテンツの数kが前記最大数mよりも多いと、当該m本のリンク独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、各決定手段は、各経路のリンクに障害が発生する確率に基づいて、全ての経路に障害が発生する確率が最小となるk本の経路の組み合わせを決定することを特徴とする。
【００１５】
(5)ネットワーク上の配信元ノードに複数の同一コンテンツを分散配置し、各配信元ノードから配信先ノードへ複数の経路で各コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るノード独立な経路の最大数mを算出する手段と、配信先ノードへ配信するコンテンツの数kが前記最大数m以下であると、当該m本のノード独立な経路の中からk本の経路を決定する第１の決定手段と、配信先ノードへ配信するコンテンツの数kが前記最大数mよりも多いと、当該m本のノード独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、各決定手段は、各経路上のノードに障害が発生する確率に基づいて、全ての経路に障害が発生する確率が最小となるk本の経路の組み合わせを決定することを特徴とする。
【発明の効果】
【００１６】
本発明によれば、以下のような効果が達成される。
【００１７】
(1)盗聴されると元のコンテンツを復元できてしまうようなリンク数を最大化し、そのような組み合せのリンクが実際に全て盗聴される確率を最小化するような部分コンテンツの配信経路を決定できる。したがって、複数のノードで秘密分散保持されている部分コンテンツを、盗聴される可能性のあるリンクを含む経路で配信する場合でも、安全なコンテンツ配信が可能になる。
【００１８】
(2)盗聴されると元のコンテンツを復元できてしまうような中継ノード数を最大化し、そのような組み合せの中継ノードが実際に全て盗聴される確率を最小化するような部分コンテンツの配信経路を決定できる。したがって、複数の配信元ノードで秘密分散保持されている部分コンテンツを、盗聴される可能性のあるノードを中継して配信する場合でも、安全なコンテンツ配信が可能になる。
【００１９】
(3)コンテンツを（k，n）閾値秘密分散法に基づいて配信する際に、n分割された部分コンテンツの配信経路を適正に決定できるようになる。
【００２０】
(4)同一コンテンツを複数の経路で同時に配信する冗長化において、同時にリンク障害が発生するとコンテンツ配信が不能となるようなリンク数を最大化し、そのような組み合わせのリンクの全てに実際に障害が発生する確率を最小化するようなコンテンツの配信経路を決定できるので、信頼性の高い冗長化が可能になる。
【００２１】
(5)同一コンテンツを複数の経路で同時に配信する冗長化において、同時にノード障害が発生するとコンテンツ配信が不能となるようなノード数を最大化し、そのような組み合わせのノードの全てに実際に障害が発生する確率を最小化するようなコンテンツの配信経路を決定できるので、信頼性の高い冗長化が可能になる。
【図面の簡単な説明】
【００２２】
【図１】本発明が適用されるコンテンツ配信システムのネットワーク構成を示した図である。
【図２】配信経路決定装置の機能ブロック図である。
【図３】本発明の第１実施形態の動作を示したフローチャートである。
【図４】本発明の第１実施形態によりリンク独立経路が確立される様子を示した図である。
【図５】本発明の第２実施形態の動作を示したフローチャートである。
【発明を実施するための形態】
【００２３】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明が適用されるコンテンツ配信システムのネットワーク構成を示した図であり、ここでは、(k，n)閾値秘密分散を利用したコンテンツ配信を例にして説明する。
【００２４】
制御対象のネットワーク３にはU個の配信元ノード１が配置され、各配信元ノード１には、１つのコンテンツcをn分割して得られるn個の部分コンテンツcp(cp1〜cpn)が分散配置されている。各配信元ノード１に分散配置される部分コンテンツcpは一つとは限らず、複数の異なる部分コンテンツcpが配置される場合もあり、また同一の部分コンテンツcpが複数の配信元ノード１に重複配置されることもある。
【００２５】
配信先ノード２は、少なくともk個の部分コンテンツcpから元のコンテンツcを再現するコンテンツ再現機能を備えている。配信経路決定サーバ４は、各配信元ノード１から配信先ノード２へk個の部分コンテンツを漏れなく、かつ重複無く配信する経路を決定して各配信元ノード１へ通知する。
【００２６】
図２は、前記配信経路決定サーバ４の主要部の構成を示した機能ブロック図である。トポロジ取得部１０１は、ネットワーク３のトポロジを取得する。最大独立経路数求解部１０２は、各配信元ノード１から配信先ノード２へ至るリンク独立（第１実施形態）またはノード独立（第２実施形態）な経路の最大数mを、後述する第１の整数計画法（第１実施形態）または第４の整数計画法（第２実施形態）を解くことで算出する。
【００２７】
配信経路決定部１０３は、配信先ノードへ配信する部分コンテンツの数kが最大数m以下であると、後述する第２の整数計画法（第１実施形態）または第５の整数計画法（第２実施形態）を解くことで当該m本の独立経路の中からk本の独立経路を決定する第１の配信経路決定部１０３ａ、および配信先ノードへ配信する部分コンテンツの数kが最大数mよりも多いと、後述する第３の整数計画法（第１実施形態）または第６の整数計画法（第２実施形態）を解くことで当該m本の独立経路を含むk本の経路を決定する第２の配信経路決定部１０３ｂを含む。経路通知部１０４は、前記k本の経路の決定結果を各配信元ノード１へ通知する。
【実施例１】
【００２８】
本発明の第１実施形態では、U個の配信元ノード１で秘密分散保持されているn個の部分コンテンツcpのうち任意のk個をネットワーク３を介して配信先ノード２まで配信するための経路選択において、配信途中の部分コンテンツcpが経路上のリンクで盗聴される可能性がある場合を想定し、k個の部分コンテンツcpの全てが盗聴される確率を最小化する経路が決定される。
【００２９】
次いで、本発明の一実施形態の動作を図３のフローチャートに沿って説明する。ステップＳ１では、ネットワーク３のトポロジ(N，Link)が前記トポロジ取得部１０１により取得される。ステップＳ２では、部分コンテンツcpを保持しているU個の配信元ノード１から配信先ノード２に至る多数の経路のうち、互いに共通のリンクを含まないリンク独立な経路の最大数mが、前記最大独立経路数求解部１０２において第１の整数計画法を解くことで求められる。第１の整数計画法では、定数が以下のように定義される。
【００３０】
N：ネットワークを構成するノードの集合
n：ノード
NC：部分コンテンツを保持しているノードの集合
c：部分コンテンツを保持しているノード
d：配信先ノード
L：ネットワークを構成するリンクの集合
l：リンク
【００３１】
また、変数が以下のように定義される。
【００３２】
xl：リンク独立な経路がリンクlを通れば「１」、通らなければ「０」であるバイナリ変数
M：リンク独立な経路の数
【００３３】
第１の整数計画法では制約式が次式(1)〜(5)で与えられる。(1)式は、部分コンテンツcpを保持している配信元ノード１に入る経路数はゼロであるという制約であり、経路をループさせない条件となる。(2)式は、各配信元ノード１から出る経路の総数がリンク独立な経路の数Mと等しくなるという制約である。(3)式は、配信先ノード２に入る経路数がMであるという制約である。(4)式は、配信先ノード２から出る経路数がゼロであるという制約である。(5)式は、配信元ノード１および配信先ノード２以外の中継ノードでは、入る経路数と出る経路数とが同一であるという制約である。
【００３４】
【数１】
【００３５】
【数２】
【００３６】
【数３】
【００３７】
【数４】
【００３８】
【数５】
【００３９】
また、本実施形態では全ての経路がリンク独立でなければならず、各リンクを複数の経路が通ることは無いので、次式(6)がリンク独立の条件として与えられる。
【００４０】
【数６】
【００４１】
最大化すべき目的関数は変数Mなので、このステップＳ２では、上記の第１の整数計画法を解いてリンク独立な経路数Mの最大数mが求められる。
【００４２】
ステップＳ３では、リンク独立な経路数の最大数mが閾値kと比較される。最大数mがk以上であれば、m本のリンク独立経路からk本の経路を選んでk個の部分コンテンツを配信すべくステップＳ４へ進む。これにより、攻撃者は少なくともk本のリンクを盗聴しなければ元のコンテンツcを復元することができない。
【００４３】
ステップＳ４では、k本のリンクが盗聴されて元のコンテンツcが漏洩する確率が最小となるように、各部分コンテンツcpを配信するためのリンク独立なk本の経路が、前記第１の配信経路決定部１０３ａにより決定される。ここでは、以下に詳述する第２の整数計画法を解くことでk本の経路が決定される。第２の整数計画法では定数が以下のように定義される。
【００４４】
N：ネットワーク構成するノードの集合
n：ノード
NC：部分コンテンツを保持しているノードの集合
c：部分コンテンツを保持しているノード
d：配信先ノード
L：ネットワークを構成するリンクの集合
l：リンク
LK：盗聴されるk本のリンクの組合せの集合
LKj：LK内のj番目の組合せに含まれるリンクの集合
P j：LKjに含まれる全てのリンクが盗聴される確率
nin：ノードnを終点とするリンクの集合
nout：ノードnを始点とするリンクの集合
【００４５】
また、変数が以下のように定義される。
【００４６】
Xl(i)：i(1〜k)番目の経路がリンクlを通れば「１」、通らなければ「０」であるバイナリ変数
Yj(i)：i(1〜k)番目の経路がLKjに含まれるリンクを通れば「１」、通らなければ「０」であるバイナリ変数
Zj：全ての経路がLKjに含まれるリンクを通れば「１」、通らなければ「０」であるバイナリ変数
Obj：k本のリンクが盗聴されて元のコンテンツcが漏洩する確率
【００４７】
この第２の整数計画法では制約式が次式(7)〜(9)で与えられる。(7)式は、各k本の経路が、配信元ノード１から出るリンクの中の1本だけを通ること、すなわちk本の経路は配信元ノード１のいずれかから出るという経路保存則である。(8)式は、配信先ノード２に入るリンクにはk本の経路が必ず通るという経路保存則である。(9)式は、配信元ノード１および配信先ノード２以外の中継ノードでは、各k本の経路が、入らなければ出ても行かないし、入れば必ず出て行くという経路保存則である。
【００４８】
【数７】
【００４９】
【数８】
【００５０】
【数９】
【００５１】
また、本実施形態では全ての経路がリンク独立でなければならず、各リンクlを複数の経路が通ることは無いので、次式(10)がリンク独立の条件とされる。
【００５２】
【数１０】
【００５３】
さらに、本実施形態では盗聴されるリンク集合を経路が通る条件として次式(11)が与えられる。また、盗聴されるリンク集合を全ての経路が通る条件として次式(12)が与えられる。
【００５４】
【数１１】
【００５５】
【数１２】
【００５６】
そして、本実施形態では盗聴されるｋ本のリンクの中の少なくとも１つのリンクを全ての経路が通過するときに元のコンテンツcが漏洩する。本実施形態の目的は、このような確率を最小化することであるから、最小化すべき目的関数は次式(13)で与えられる。なお、本実施形態では各リンクlが盗聴される確率が既知であり、確率PjはLK jに含まれる全てのリンクlの盗聴確率に基づいて、例えば各盗聴確率の積として算出される。
【００５７】
【数１３】
【００５８】
このステップＳ４では、上記の第２の整数計画法を解くことによって得られるXl(i)の値から、各部分コンテンツcpを配信すべきリンク独立なk本の経路が決定される。
【００５９】
一方、前記ステップＳ３において、リンク独立な経路の最大数mが必要経路数kよりも小さいと判定されるとステップＳ５へ進む。この場合、攻撃者はk本よりも少ないm本のリンクを盗聴するだけで元のコンテンツcを復元できる場合がある。しかしながら、部分コンテンツを配信するためのk本の経路がm本のリンク独立な経路を含んでいれば、攻撃者はm-1本のリンクを盗聴するだけでは元のコンテンツcを復元できない。
【００６０】
そこで、このステップＳ５では、図４に一例を示したように、m(＜k)本のリンク独立な経路を含み、かつm本のリンクが盗聴されて元のコンテンツcが漏洩する確率が最小となるように、部分コンテンツcpを配信するためのk本の経路が、前記第２の配信経路決定部１０３ｂにより決定される。
【００６１】
本実施形態では、以下に詳述する第３の整数計画法を解くことにより、このようなk本の経路が決定される。第３の整数計画法における定数は以下のように定義される。
【００６２】
N：ネットワーク構成するノードの集合
n：ノード
NC：部分コンテンツを保持しているノードの集合
c：部分コンテンツを保持しているノード
d：配信先ノード
L：ネットワークを構成するリンクの集合
l：リンク
LK：盗聴されるm本のリンクの組合せの集合
LKj：LK内のj番目の組合せに含まれるリンクの集合
Pj：LKj含まれる全てのリンクが盗聴される確率
nin：ノードnを終点とするリンクの集合
nout：ノードnを始点とするリンクの集合
【００６３】
また、第３の整数計画法では変数が以下のように定義される。
【００６４】
Xl(i)：i(1〜k)番目の経路がリンクlを通れば「１」、通らなければ「０」であるバイナリ変数。
Yj(i)：i(1〜k)番目の経路がLKjに含まれるリンクlを通れば「１」、通らなければ「０」であるバイナリ変数。
Zj：全ての経路がLKjに含まれるリンクlを通れば「１」、通らなければ「０」であるバイナリ変数。
Obj：m本のリンクが盗聴されて元のコンテンツが漏洩する確率。
【００６５】
第３の整数計画法における制約式は次式(14)〜(16)の通りであり、これらは第２の整数計画法における経路保存則の制約式(7)〜(9)と同一である。
【００６６】
【数１４】
【００６７】
【数１５】
【００６８】
【数１６】
【００６９】
第３の整数計画法において、k本の経路の内、m本の経路がリンク独立である条件は、次式(17)で与えられる。
【００７０】
【数１７】
【００７１】
さらに、本実施形態では盗聴されるリンク集合を経路が通る条件として次式(18)が与えられる。また、盗聴されるリンク集合を全ての経路が通る条件として次式(19)が与えられる。
【００７２】
【数１８】
【００７３】
【数１９】
【００７４】
そして、盗聴されるm本のリンクの中の少なくとも１つのリンクを全ての経路が通過するとき、元のコンテンツが漏洩する。本発明の目的は、この様な確率を最小化することであるから、最小化すべき目的関数は次式(20)で与えられる。
【００７５】
【数２０】
【００７６】
本実施形態によれば、盗聴されると元のコンテンツcを復元できてしまうようなリンク数を最大化し、そのような組み合せのリンクが実際に全て盗聴される確率を最小化するような部分コンテンツcpの配信経路を決定できる。したがって、複数のノードで秘密分散保持されている部分コンテンツcpを、盗聴される可能性のあるリンクを含む経路で配信する場合でも、安全なコンテンツ配信が可能になる。
【実施例２】
【００７７】
上記の第１実施形態では、配信途中の部分コンテンツcpがリンク上で盗聴される可能性を想定していたが、配信途中の部分コンテンツcpが中継ノード上で盗聴される可能性を想定する場合も、リンク独立な経路をノード独立な経路で置き換えることにより、同様の手順で各部分コンテンツの配信経路を決定できる。
【００７８】
すなわち、本発明の第２実施形態では、U個の配信元ノード１で秘密分散保持されているn個の部分コンテンツcpのうち任意のk個をネットワーク３を介して配信先ノード２まで配信するための経路選択において、配信途中の部分コンテンツcpが経路上の中継ノードで盗聴される可能性がある場合を想定し、k個の部分コンテンツcpの全てが盗聴される確率を最小化する経路が決定される。
【００７９】
図５は、本実施形態の動作を示したフローチャートである。ステップＳ２１では、ネットワーク３のトポロジ(N，Link)が前記トポロジ取得部１０１により取得される。ステップＳ２２では、部分コンテンツcpを保持しているU個の配信元ノード１から配信先ノード２に至る多数の経路のうち、互いに共通のノードを含まないノード独立な経路の最大数mが、第４の整数計画法を解くことにより求められる。第４の整数計画法では、定数が以下のように定義される。
【００８０】
N：ネットワーク構成するノードの集合。
n：ノード。
NC：部分コンテンツを保持しているノードの集合。
c：部分コンテンツを保持しているノード。
d：配信先ノード。
L：ネットワークを構成するリンクの集合。
l：リンク。
【００８１】
また、変数が以下のように定義する。
【００８２】
xl：ノード独立な経路がリンクlを通れば「１」、通らなければ「０」であるバイナリ変数。
M：ノード独立な経路の数。
【００８３】
この第４の整数計画法では、経路の保存則に係る制約式が次式(21)〜(25)で与えられる。また、各経路がノード独立である条件として次式(26)が与えられる。
【００８４】
【数２１】
【００８５】
【数２２】
【００８６】
【数２３】
【００８７】
【数２４】
【００８８】
【数２５】
【００８９】
【数２６】
【００９０】
最大化すべき目的関数は変数Mなので、このステップＳ２２では、上記の第４の整数計画法を解いてノード独立な経路数の最大数mが求められる。
【００９１】
ステップＳ２３では、ノード独立な経路数の最大数mが閾値kと比較される。最大数mがk以上であれば、m本のノード独立経路からk本の経路を選んでk個の部分コンテンツを配信すべくステップＳ２４へ進む。これにより、攻撃者は少なくともk個の中継ノードを盗聴しなければ元のコンテンツcを復元することができない。
【００９２】
ステップＳ２４では、k個の中継ノードが全て盗聴されて元のコンテンツcが漏洩する確率が最小となるように、各部分コンテンツcpを配信するためのノード独立なk本の経路が決定される。ここでは、以下に詳述する第５の整数計画法を解くことでk本の経路が決定される。第５の整数計画法では定数が以下のように定義される。
【００９３】
N：ネットワーク構成するノードの集合
n：ノード
NC：部分コンテンツを保持しているノードの集合
c：部分コンテンツを保持しているノード
d：配信先ノード
L：ネットワークを構成するリンクの集合
l：リンク
NK：盗聴されるk個の中継ノードの組合せの集合
NK j：NK内のj番目の組合せに含まれる中継ノードの集合
P j：NK jに含まれる全ての中継ノードが盗聴される確率
nin：ノードnを終点とするリンクの集合
nout：ノードnを始点とするリンクの集合
【００９４】
また、変数が以下のように定義される。
【００９５】
Xl(i)：i（1〜k）番目の経路がリンクlを通れば「１」、通らなければ「０」であるバイナリ変数
Yj(i)：i（1〜k）番目の経路がNKjに含まれる中継ノードを通れば「１」、通らなければ「０」であるバイナリ変数
Zj：全経路がNKjに含まれる中継ノードを通れば「１」、通らなければ「０」であるバイナリ変数
Obj：k個の中継ノードが盗聴されて元のコンテンツcが漏洩する確率
【００９６】
この第５の整数計画法では、経路保存則として次式(27)，(28)，(29)の制約式が与えられる。また、本実施形態では全ての経路がノード独立でなければならず、各中継ノードnを複数の経路が通ることは無いので、次式(30)がノード独立の条件とされる。
【００９７】
【数２７】
【００９８】
【数２８】
【００９９】
【数２９】
【０１００】
【数３０】
【０１０１】
さらに、本実施形態では盗聴される中継ノードの集合を経路が通る条件として次式(31)が与えられる。また、盗聴される中継ノードの集合を全ての経路が通る条件として次式(32)が与えられる。
【０１０２】
【数３１】
【０１０３】
【数３２】
【０１０４】
そして、本実施形態では盗聴されるk個の中継ノードの中の少なくとも１つの中継ノードを全ての経路が通過するときに元のコンテンツcが漏洩する。本実施形態の目的は、このような確率を最小化することであるから、最小化すべき目的関数は次式(33)で与えられる。なお、本実施形態では各中継ノードnが盗聴される確率が既知であり、確率PjはLK jに含まれる全ての中継ノードnの盗聴確率に基づいて、例えば各盗聴確率の積として算出される。
【０１０５】
【数３３】
【０１０６】
このステップＳ２４では、上記の第５の整数計画法を解くことによって得られるXl(i)の値から、各部分コンテンツcpを配信すべきノード独立なk本の経路が決定される。
【０１０７】
一方、前記ステップＳ２３において、ノード独立な経路の最大数mが必要経路数kよりも小さいと判定されるとステップＳ２５へ進む。この場合、攻撃者はk個よりも少ないm個の中継ノードを盗聴するだけで元のコンテンツcを復元できる場合がある。しかしながら、部分コンテンツを配信するためのk本の経路がm本のノード独立な経路を含んでいれば、攻撃者はm-1個のノードを盗聴するだけでは元のコンテンツcを復元できない。
【０１０８】
そこで、このステップＳ２５では、m(＜k)本のノード独立な経路を含み、かつm個の中継ノードが盗聴されて元のコンテンツcが漏洩する確率が最小となるように、部分コンテンツcpを配信するためのk本の経路が決定される。
【０１０９】
本実施形態では、以下に詳述する第６の整数計画法を解くことにより、このようなk本の経路が決定される。第６の整数計画法における定数は以下のように定義される。
【０１１０】
N：ネットワーク構成するノードの集合
n：ノード
NC：部分コンテンツを保持しているノードの集合
c：部分コンテンツを保持しているノード
d：配信先ノード
L：ネットワークを構成するリンクの集合
l：リンク
NK：盗聴されるm個の中継ノードの組合せの集合
NKj：NK内のj番目の組合せに含まれる中継ノードの集合
P j：NKjに含まれる全ての中継ノードが盗聴される確率
nin：ノードnを終点とするリンクの集合
nout：ノードnを始点とするリンクの集合
【０１１１】
また、変数が以下のように定義される。
【０１１２】
Xl(i)：i（1〜k）番目の経路がリンクlを通れば「１」、通らなければ「０」であるバイナリ変数
Yj(i)：i（1〜k）番目の経路がNKjに含まれる中継ノードを通れば「１」、通らなければ「０」であるバイナリ変数
Zj：全経路がNKjに含まれる中継ノードを通れば「１」、通らなければ「０」であるバイナリ変数
Obj：m個の中継ノードが盗聴されて元のコンテンツが漏洩する確率
【０１１３】
第６の整数計画法における制約式は次式(34)〜(36)の通りであり、これらは第５の整数計画法における経路保存則の制約式(27)〜(29)と同一である。
【０１１４】
【数３４】
【０１１５】
【数３５】
【０１１６】
【数３６】
【０１１７】
第６の整数計画法において、k本の経路の内、m本の経路がノード独立である条件は、次式(37)で与えられる。
【０１１８】
【数３７】
【０１１９】
さらに、本実施形態では盗聴される中継ノードの集合を経路が通る条件として次式(38)が与えられる。また、盗聴される中継ノードの集合を全ての経路が通る条件として次式(39)が与えられる。
【０１２０】
【数３８】
【０１２１】
【数３９】
【０１２２】
そして、盗聴されるm個の中継ノードの中の少なくとも１つの中継ノードを全ての経路が通過するとき、元のコンテンツが漏洩する。本発明の目的は、この様な確率を最小化することであるから、最小化すべき目的関数は次式(40)で与えられる。
【０１２３】
【数４０】
【０１２４】
本実施形態によれば、盗聴されると元のコンテンツを復元できてしまうような中継ノード数を最大化し、そのような組み合せの中継ノードが実際に全て盗聴される確率を最小化するような部分コンテンツの配信経路を決定できる。したがって、複数の配信元ノードで秘密分散保持されている部分コンテンツを、盗聴される可能性のあるノードを中継して配信する場合でも、安全なコンテンツ配信が可能になる。
【実施例３】
【０１２５】
上記の各実施形態では、本発明を(k，n)閾値秘密分散を利用したコンテンツ配信を例にして説明したが、本発明はこれのみに限定されるものではなく、経路上の各リンクまたは各ノード上で部分コンテンツが盗聴される確率を、各リンクまたは各中継ノードの障害確率と考えれば、k個の同一コンテンツをU個のノードから配信先ノードまで配信する際に、信頼性のより高いk本の経路を決定できる。
【０１２６】
すなわち、複数の同一データを一つの配信先ノードへ配信する冗長化において、多重リンク障害または多重ノード障害によってk本の経路が全て障害になり、コンテンツ配信が行えなくなる確率が最小化されるような配信経路を決定できるので、信頼性の高い冗長化が可能になる。
【符号の説明】
【０１２７】
１…配信元ノード
２…配信先ノード
３…ネットワーク
４…配信経路決定サーバ
【技術分野】
【０００１】
本発明は、コンテンツ配信システムの配信経路決定装置に係り、特に、一つのコンテンツを複数の部分コンテンツに分割してネットワーク上に分散配置し、これらの部分コンテンツを一つの配信先ノードへ複数の経路で配信する閾値秘密分散に好適なコンテンツ配信システムの配信経路決定装置に関する。
【背景技術】
【０００２】
１つのコンテンツを暗号化されたn個の部分コンテンツに分割し、n個の部分コンテンツのうち、k (<= n) 個以上の部分コンテンツが集まらないと元のコンテンツを復元できないように秘密分散する閾値秘密分散が非特許文献１に開示されている。
【０００３】
また、データ保持のリスク分散を図るために、n個に分割された部分コンテンツを複数のノードで秘密分散保持する技術が特許文献１，２に開示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Shamir, Adi (1979), "How to share a secret", Communications of the ACM 22 (11): 612-613
【特許文献】
【０００５】
【特許文献１】特開２００９−１２２７３１号公報
【特許文献２】特開２００９−１０５３１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
n個の部分コンテンツから任意のk個の部分コンテンツを集めれば元データを復元できるが(k-1)個の部分コンテンツからでは元データを復元できない（k，n）閾値秘密分散では、少なくともk個の部分コンテンツがネットワーク上の配信元ノードに分散配置され、元データを復元しようとする配信先ノードに対して、部分コンテンツを保持する配信元ノードから部分コンテンツが配信される。
【０００７】
このとき、各部分コンテンツの配信経路が同一リンクや同一ノードを通っていると、k本未満のリンクやk個未満のノードを盗聴するだけで元のデータが復元されてしまうので安全率が低下してしまう。したがって、（k，n）閾値秘密分散を適用したデータ配信では、できるだけk本の経路は同一リンクや同一ノードを通らない経路であることが望ましい。
【０００８】
また、閾値秘密分散以外であっても、同一コンテンツを複数の経路で配信する冗長化では、全ての経路が同一リンクや同一ノードを通過する場合はもちろん、一部の経路が同一リンクや同一ノードを通過する場合でも、リンク障害やノード障害に対する安全度が低下してしまう。
【０００９】
本発明の目的は、上記した従来技術の課題を解決し、閾値秘密分散された複数の部分コンテンツや冗長化された複数の同一コンテンツを異なる経路で配信するシステムにおいて、盗聴や障害に対する信頼性の高い配信経路を決定できるコンテンツ配信システムの配信経路決定装置を提供することにある。
【課題を解決するための手段】
【００１０】
上記の目的を達成するために、本発明は、以下のような手段を講じた点に特徴がある。
【００１１】
(1)配信対象のコンテンツを複数の部分コンテンツに分割してネットワーク上の配信元ノードに分散配置し、各配信元ノードから配信先ノードへ複数の経路で各部分コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数mを算出する手段と、配信先ノードへ配信する部分コンテンツの数kが前記最大数m以下であると、当該m本のリンク独立な経路の中からk本の経路を決定する第１の決定手段と、配信先ノードへ配信する部分コンテンツの数kが前記最大数mよりも多いと、当該m本のリンク独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、各決定手段は、各経路のリンクが盗聴される確率に基づいて、全ての経路が盗聴される確率が最小となるk本の経路の組み合わせを決定することを特徴とする。
【００１２】
(2)配信対象のコンテンツを複数の部分コンテンツに分割してネットワーク上の配信元ノードに分散配置し、各配信元ノードから配信先ノードへ複数の経路で各部分コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るノード独立な経路の最大数mを算出する手段と、配信先ノードへ配信する部分コンテンツの数kが前記最大数m以下であると、当該m本のノード独立な経路の中からk本の経路を決定する第１の決定手段と、配信先ノードへ配信する部分コンテンツの数kが前記最大数mよりも多いと、当該m本のノード独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、各決定手段は、各経路上のノードが盗聴される確率に基づいて、全ての経路が盗聴される確率が最小となるk本の経路の組み合わせを決定することを特徴とする。
【００１３】
(3)配信対象のコンテンツが（k，n）閾値秘密分散法に基づいてn分割され、各配信元ノードからは、n個の部分コンテンツの中のk個が重複無く配信されることを特徴とする。
【００１４】
(4)ネットワーク上の配信元ノードに複数の同一コンテンツを分散配置し、各配信元ノードから配信先ノードへ複数の経路で各コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数mを算出する手段と、配信先ノードへ配信するコンテンツの数kが前記最大数m以下であると、当該m本のリンク独立な経路の中からk本の経路を決定する第１の決定手段と、配信先ノードへ配信するコンテンツの数kが前記最大数mよりも多いと、当該m本のリンク独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、各決定手段は、各経路のリンクに障害が発生する確率に基づいて、全ての経路に障害が発生する確率が最小となるk本の経路の組み合わせを決定することを特徴とする。
【００１５】
(5)ネットワーク上の配信元ノードに複数の同一コンテンツを分散配置し、各配信元ノードから配信先ノードへ複数の経路で各コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るノード独立な経路の最大数mを算出する手段と、配信先ノードへ配信するコンテンツの数kが前記最大数m以下であると、当該m本のノード独立な経路の中からk本の経路を決定する第１の決定手段と、配信先ノードへ配信するコンテンツの数kが前記最大数mよりも多いと、当該m本のノード独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、各決定手段は、各経路上のノードに障害が発生する確率に基づいて、全ての経路に障害が発生する確率が最小となるk本の経路の組み合わせを決定することを特徴とする。
【発明の効果】
【００１６】
本発明によれば、以下のような効果が達成される。
【００１７】
(1)盗聴されると元のコンテンツを復元できてしまうようなリンク数を最大化し、そのような組み合せのリンクが実際に全て盗聴される確率を最小化するような部分コンテンツの配信経路を決定できる。したがって、複数のノードで秘密分散保持されている部分コンテンツを、盗聴される可能性のあるリンクを含む経路で配信する場合でも、安全なコンテンツ配信が可能になる。
【００１８】
(2)盗聴されると元のコンテンツを復元できてしまうような中継ノード数を最大化し、そのような組み合せの中継ノードが実際に全て盗聴される確率を最小化するような部分コンテンツの配信経路を決定できる。したがって、複数の配信元ノードで秘密分散保持されている部分コンテンツを、盗聴される可能性のあるノードを中継して配信する場合でも、安全なコンテンツ配信が可能になる。
【００１９】
(3)コンテンツを（k，n）閾値秘密分散法に基づいて配信する際に、n分割された部分コンテンツの配信経路を適正に決定できるようになる。
【００２０】
(4)同一コンテンツを複数の経路で同時に配信する冗長化において、同時にリンク障害が発生するとコンテンツ配信が不能となるようなリンク数を最大化し、そのような組み合わせのリンクの全てに実際に障害が発生する確率を最小化するようなコンテンツの配信経路を決定できるので、信頼性の高い冗長化が可能になる。
【００２１】
(5)同一コンテンツを複数の経路で同時に配信する冗長化において、同時にノード障害が発生するとコンテンツ配信が不能となるようなノード数を最大化し、そのような組み合わせのノードの全てに実際に障害が発生する確率を最小化するようなコンテンツの配信経路を決定できるので、信頼性の高い冗長化が可能になる。
【図面の簡単な説明】
【００２２】
【図１】本発明が適用されるコンテンツ配信システムのネットワーク構成を示した図である。
【図２】配信経路決定装置の機能ブロック図である。
【図３】本発明の第１実施形態の動作を示したフローチャートである。
【図４】本発明の第１実施形態によりリンク独立経路が確立される様子を示した図である。
【図５】本発明の第２実施形態の動作を示したフローチャートである。
【発明を実施するための形態】
【００２３】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明が適用されるコンテンツ配信システムのネットワーク構成を示した図であり、ここでは、(k，n)閾値秘密分散を利用したコンテンツ配信を例にして説明する。
【００２４】
制御対象のネットワーク３にはU個の配信元ノード１が配置され、各配信元ノード１には、１つのコンテンツcをn分割して得られるn個の部分コンテンツcp(cp1〜cpn)が分散配置されている。各配信元ノード１に分散配置される部分コンテンツcpは一つとは限らず、複数の異なる部分コンテンツcpが配置される場合もあり、また同一の部分コンテンツcpが複数の配信元ノード１に重複配置されることもある。
【００２５】
配信先ノード２は、少なくともk個の部分コンテンツcpから元のコンテンツcを再現するコンテンツ再現機能を備えている。配信経路決定サーバ４は、各配信元ノード１から配信先ノード２へk個の部分コンテンツを漏れなく、かつ重複無く配信する経路を決定して各配信元ノード１へ通知する。
【００２６】
図２は、前記配信経路決定サーバ４の主要部の構成を示した機能ブロック図である。トポロジ取得部１０１は、ネットワーク３のトポロジを取得する。最大独立経路数求解部１０２は、各配信元ノード１から配信先ノード２へ至るリンク独立（第１実施形態）またはノード独立（第２実施形態）な経路の最大数mを、後述する第１の整数計画法（第１実施形態）または第４の整数計画法（第２実施形態）を解くことで算出する。
【００２７】
配信経路決定部１０３は、配信先ノードへ配信する部分コンテンツの数kが最大数m以下であると、後述する第２の整数計画法（第１実施形態）または第５の整数計画法（第２実施形態）を解くことで当該m本の独立経路の中からk本の独立経路を決定する第１の配信経路決定部１０３ａ、および配信先ノードへ配信する部分コンテンツの数kが最大数mよりも多いと、後述する第３の整数計画法（第１実施形態）または第６の整数計画法（第２実施形態）を解くことで当該m本の独立経路を含むk本の経路を決定する第２の配信経路決定部１０３ｂを含む。経路通知部１０４は、前記k本の経路の決定結果を各配信元ノード１へ通知する。
【実施例１】
【００２８】
本発明の第１実施形態では、U個の配信元ノード１で秘密分散保持されているn個の部分コンテンツcpのうち任意のk個をネットワーク３を介して配信先ノード２まで配信するための経路選択において、配信途中の部分コンテンツcpが経路上のリンクで盗聴される可能性がある場合を想定し、k個の部分コンテンツcpの全てが盗聴される確率を最小化する経路が決定される。
【００２９】
次いで、本発明の一実施形態の動作を図３のフローチャートに沿って説明する。ステップＳ１では、ネットワーク３のトポロジ(N，Link)が前記トポロジ取得部１０１により取得される。ステップＳ２では、部分コンテンツcpを保持しているU個の配信元ノード１から配信先ノード２に至る多数の経路のうち、互いに共通のリンクを含まないリンク独立な経路の最大数mが、前記最大独立経路数求解部１０２において第１の整数計画法を解くことで求められる。第１の整数計画法では、定数が以下のように定義される。
【００３０】
N：ネットワークを構成するノードの集合
n：ノード
NC：部分コンテンツを保持しているノードの集合
c：部分コンテンツを保持しているノード
d：配信先ノード
L：ネットワークを構成するリンクの集合
l：リンク
【００３１】
また、変数が以下のように定義される。
【００３２】
xl：リンク独立な経路がリンクlを通れば「１」、通らなければ「０」であるバイナリ変数
M：リンク独立な経路の数
【００３３】
第１の整数計画法では制約式が次式(1)〜(5)で与えられる。(1)式は、部分コンテンツcpを保持している配信元ノード１に入る経路数はゼロであるという制約であり、経路をループさせない条件となる。(2)式は、各配信元ノード１から出る経路の総数がリンク独立な経路の数Mと等しくなるという制約である。(3)式は、配信先ノード２に入る経路数がMであるという制約である。(4)式は、配信先ノード２から出る経路数がゼロであるという制約である。(5)式は、配信元ノード１および配信先ノード２以外の中継ノードでは、入る経路数と出る経路数とが同一であるという制約である。
【００３４】
【数１】
【００３５】
【数２】
【００３６】
【数３】
【００３７】
【数４】
【００３８】
【数５】
【００３９】
また、本実施形態では全ての経路がリンク独立でなければならず、各リンクを複数の経路が通ることは無いので、次式(6)がリンク独立の条件として与えられる。
【００４０】
【数６】
【００４１】
最大化すべき目的関数は変数Mなので、このステップＳ２では、上記の第１の整数計画法を解いてリンク独立な経路数Mの最大数mが求められる。
【００４２】
ステップＳ３では、リンク独立な経路数の最大数mが閾値kと比較される。最大数mがk以上であれば、m本のリンク独立経路からk本の経路を選んでk個の部分コンテンツを配信すべくステップＳ４へ進む。これにより、攻撃者は少なくともk本のリンクを盗聴しなければ元のコンテンツcを復元することができない。
【００４３】
ステップＳ４では、k本のリンクが盗聴されて元のコンテンツcが漏洩する確率が最小となるように、各部分コンテンツcpを配信するためのリンク独立なk本の経路が、前記第１の配信経路決定部１０３ａにより決定される。ここでは、以下に詳述する第２の整数計画法を解くことでk本の経路が決定される。第２の整数計画法では定数が以下のように定義される。
【００４４】
N：ネットワーク構成するノードの集合
n：ノード
NC：部分コンテンツを保持しているノードの集合
c：部分コンテンツを保持しているノード
d：配信先ノード
L：ネットワークを構成するリンクの集合
l：リンク
LK：盗聴されるk本のリンクの組合せの集合
LKj：LK内のj番目の組合せに含まれるリンクの集合
P j：LKjに含まれる全てのリンクが盗聴される確率
nin：ノードnを終点とするリンクの集合
nout：ノードnを始点とするリンクの集合
【００４５】
また、変数が以下のように定義される。
【００４６】
Xl(i)：i(1〜k)番目の経路がリンクlを通れば「１」、通らなければ「０」であるバイナリ変数
Yj(i)：i(1〜k)番目の経路がLKjに含まれるリンクを通れば「１」、通らなければ「０」であるバイナリ変数
Zj：全ての経路がLKjに含まれるリンクを通れば「１」、通らなければ「０」であるバイナリ変数
Obj：k本のリンクが盗聴されて元のコンテンツcが漏洩する確率
【００４７】
この第２の整数計画法では制約式が次式(7)〜(9)で与えられる。(7)式は、各k本の経路が、配信元ノード１から出るリンクの中の1本だけを通ること、すなわちk本の経路は配信元ノード１のいずれかから出るという経路保存則である。(8)式は、配信先ノード２に入るリンクにはk本の経路が必ず通るという経路保存則である。(9)式は、配信元ノード１および配信先ノード２以外の中継ノードでは、各k本の経路が、入らなければ出ても行かないし、入れば必ず出て行くという経路保存則である。
【００４８】
【数７】
【００４９】
【数８】
【００５０】
【数９】
【００５１】
また、本実施形態では全ての経路がリンク独立でなければならず、各リンクlを複数の経路が通ることは無いので、次式(10)がリンク独立の条件とされる。
【００５２】
【数１０】
【００５３】
さらに、本実施形態では盗聴されるリンク集合を経路が通る条件として次式(11)が与えられる。また、盗聴されるリンク集合を全ての経路が通る条件として次式(12)が与えられる。
【００５４】
【数１１】
【００５５】
【数１２】
【００５６】
そして、本実施形態では盗聴されるｋ本のリンクの中の少なくとも１つのリンクを全ての経路が通過するときに元のコンテンツcが漏洩する。本実施形態の目的は、このような確率を最小化することであるから、最小化すべき目的関数は次式(13)で与えられる。なお、本実施形態では各リンクlが盗聴される確率が既知であり、確率PjはLK jに含まれる全てのリンクlの盗聴確率に基づいて、例えば各盗聴確率の積として算出される。
【００５７】
【数１３】
【００５８】
このステップＳ４では、上記の第２の整数計画法を解くことによって得られるXl(i)の値から、各部分コンテンツcpを配信すべきリンク独立なk本の経路が決定される。
【００５９】
一方、前記ステップＳ３において、リンク独立な経路の最大数mが必要経路数kよりも小さいと判定されるとステップＳ５へ進む。この場合、攻撃者はk本よりも少ないm本のリンクを盗聴するだけで元のコンテンツcを復元できる場合がある。しかしながら、部分コンテンツを配信するためのk本の経路がm本のリンク独立な経路を含んでいれば、攻撃者はm-1本のリンクを盗聴するだけでは元のコンテンツcを復元できない。
【００６０】
そこで、このステップＳ５では、図４に一例を示したように、m(＜k)本のリンク独立な経路を含み、かつm本のリンクが盗聴されて元のコンテンツcが漏洩する確率が最小となるように、部分コンテンツcpを配信するためのk本の経路が、前記第２の配信経路決定部１０３ｂにより決定される。
【００６１】
本実施形態では、以下に詳述する第３の整数計画法を解くことにより、このようなk本の経路が決定される。第３の整数計画法における定数は以下のように定義される。
【００６２】
N：ネットワーク構成するノードの集合
n：ノード
NC：部分コンテンツを保持しているノードの集合
c：部分コンテンツを保持しているノード
d：配信先ノード
L：ネットワークを構成するリンクの集合
l：リンク
LK：盗聴されるm本のリンクの組合せの集合
LKj：LK内のj番目の組合せに含まれるリンクの集合
Pj：LKj含まれる全てのリンクが盗聴される確率
nin：ノードnを終点とするリンクの集合
nout：ノードnを始点とするリンクの集合
【００６３】
また、第３の整数計画法では変数が以下のように定義される。
【００６４】
Xl(i)：i(1〜k)番目の経路がリンクlを通れば「１」、通らなければ「０」であるバイナリ変数。
Yj(i)：i(1〜k)番目の経路がLKjに含まれるリンクlを通れば「１」、通らなければ「０」であるバイナリ変数。
Zj：全ての経路がLKjに含まれるリンクlを通れば「１」、通らなければ「０」であるバイナリ変数。
Obj：m本のリンクが盗聴されて元のコンテンツが漏洩する確率。
【００６５】
第３の整数計画法における制約式は次式(14)〜(16)の通りであり、これらは第２の整数計画法における経路保存則の制約式(7)〜(9)と同一である。
【００６６】
【数１４】
【００６７】
【数１５】
【００６８】
【数１６】
【００６９】
第３の整数計画法において、k本の経路の内、m本の経路がリンク独立である条件は、次式(17)で与えられる。
【００７０】
【数１７】
【００７１】
さらに、本実施形態では盗聴されるリンク集合を経路が通る条件として次式(18)が与えられる。また、盗聴されるリンク集合を全ての経路が通る条件として次式(19)が与えられる。
【００７２】
【数１８】
【００７３】
【数１９】
【００７４】
そして、盗聴されるm本のリンクの中の少なくとも１つのリンクを全ての経路が通過するとき、元のコンテンツが漏洩する。本発明の目的は、この様な確率を最小化することであるから、最小化すべき目的関数は次式(20)で与えられる。
【００７５】
【数２０】
【００７６】
本実施形態によれば、盗聴されると元のコンテンツcを復元できてしまうようなリンク数を最大化し、そのような組み合せのリンクが実際に全て盗聴される確率を最小化するような部分コンテンツcpの配信経路を決定できる。したがって、複数のノードで秘密分散保持されている部分コンテンツcpを、盗聴される可能性のあるリンクを含む経路で配信する場合でも、安全なコンテンツ配信が可能になる。
【実施例２】
【００７７】
上記の第１実施形態では、配信途中の部分コンテンツcpがリンク上で盗聴される可能性を想定していたが、配信途中の部分コンテンツcpが中継ノード上で盗聴される可能性を想定する場合も、リンク独立な経路をノード独立な経路で置き換えることにより、同様の手順で各部分コンテンツの配信経路を決定できる。
【００７８】
すなわち、本発明の第２実施形態では、U個の配信元ノード１で秘密分散保持されているn個の部分コンテンツcpのうち任意のk個をネットワーク３を介して配信先ノード２まで配信するための経路選択において、配信途中の部分コンテンツcpが経路上の中継ノードで盗聴される可能性がある場合を想定し、k個の部分コンテンツcpの全てが盗聴される確率を最小化する経路が決定される。
【００７９】
図５は、本実施形態の動作を示したフローチャートである。ステップＳ２１では、ネットワーク３のトポロジ(N，Link)が前記トポロジ取得部１０１により取得される。ステップＳ２２では、部分コンテンツcpを保持しているU個の配信元ノード１から配信先ノード２に至る多数の経路のうち、互いに共通のノードを含まないノード独立な経路の最大数mが、第４の整数計画法を解くことにより求められる。第４の整数計画法では、定数が以下のように定義される。
【００８０】
N：ネットワーク構成するノードの集合。
n：ノード。
NC：部分コンテンツを保持しているノードの集合。
c：部分コンテンツを保持しているノード。
d：配信先ノード。
L：ネットワークを構成するリンクの集合。
l：リンク。
【００８１】
また、変数が以下のように定義する。
【００８２】
xl：ノード独立な経路がリンクlを通れば「１」、通らなければ「０」であるバイナリ変数。
M：ノード独立な経路の数。
【００８３】
この第４の整数計画法では、経路の保存則に係る制約式が次式(21)〜(25)で与えられる。また、各経路がノード独立である条件として次式(26)が与えられる。
【００８４】
【数２１】
【００８５】
【数２２】
【００８６】
【数２３】
【００８７】
【数２４】
【００８８】
【数２５】
【００８９】
【数２６】
【００９０】
最大化すべき目的関数は変数Mなので、このステップＳ２２では、上記の第４の整数計画法を解いてノード独立な経路数の最大数mが求められる。
【００９１】
ステップＳ２３では、ノード独立な経路数の最大数mが閾値kと比較される。最大数mがk以上であれば、m本のノード独立経路からk本の経路を選んでk個の部分コンテンツを配信すべくステップＳ２４へ進む。これにより、攻撃者は少なくともk個の中継ノードを盗聴しなければ元のコンテンツcを復元することができない。
【００９２】
ステップＳ２４では、k個の中継ノードが全て盗聴されて元のコンテンツcが漏洩する確率が最小となるように、各部分コンテンツcpを配信するためのノード独立なk本の経路が決定される。ここでは、以下に詳述する第５の整数計画法を解くことでk本の経路が決定される。第５の整数計画法では定数が以下のように定義される。
【００９３】
N：ネットワーク構成するノードの集合
n：ノード
NC：部分コンテンツを保持しているノードの集合
c：部分コンテンツを保持しているノード
d：配信先ノード
L：ネットワークを構成するリンクの集合
l：リンク
NK：盗聴されるk個の中継ノードの組合せの集合
NK j：NK内のj番目の組合せに含まれる中継ノードの集合
P j：NK jに含まれる全ての中継ノードが盗聴される確率
nin：ノードnを終点とするリンクの集合
nout：ノードnを始点とするリンクの集合
【００９４】
また、変数が以下のように定義される。
【００９５】
Xl(i)：i（1〜k）番目の経路がリンクlを通れば「１」、通らなければ「０」であるバイナリ変数
Yj(i)：i（1〜k）番目の経路がNKjに含まれる中継ノードを通れば「１」、通らなければ「０」であるバイナリ変数
Zj：全経路がNKjに含まれる中継ノードを通れば「１」、通らなければ「０」であるバイナリ変数
Obj：k個の中継ノードが盗聴されて元のコンテンツcが漏洩する確率
【００９６】
この第５の整数計画法では、経路保存則として次式(27)，(28)，(29)の制約式が与えられる。また、本実施形態では全ての経路がノード独立でなければならず、各中継ノードnを複数の経路が通ることは無いので、次式(30)がノード独立の条件とされる。
【００９７】
【数２７】
【００９８】
【数２８】
【００９９】
【数２９】
【０１００】
【数３０】
【０１０１】
さらに、本実施形態では盗聴される中継ノードの集合を経路が通る条件として次式(31)が与えられる。また、盗聴される中継ノードの集合を全ての経路が通る条件として次式(32)が与えられる。
【０１０２】
【数３１】
【０１０３】
【数３２】
【０１０４】
そして、本実施形態では盗聴されるk個の中継ノードの中の少なくとも１つの中継ノードを全ての経路が通過するときに元のコンテンツcが漏洩する。本実施形態の目的は、このような確率を最小化することであるから、最小化すべき目的関数は次式(33)で与えられる。なお、本実施形態では各中継ノードnが盗聴される確率が既知であり、確率PjはLK jに含まれる全ての中継ノードnの盗聴確率に基づいて、例えば各盗聴確率の積として算出される。
【０１０５】
【数３３】
【０１０６】
このステップＳ２４では、上記の第５の整数計画法を解くことによって得られるXl(i)の値から、各部分コンテンツcpを配信すべきノード独立なk本の経路が決定される。
【０１０７】
一方、前記ステップＳ２３において、ノード独立な経路の最大数mが必要経路数kよりも小さいと判定されるとステップＳ２５へ進む。この場合、攻撃者はk個よりも少ないm個の中継ノードを盗聴するだけで元のコンテンツcを復元できる場合がある。しかしながら、部分コンテンツを配信するためのk本の経路がm本のノード独立な経路を含んでいれば、攻撃者はm-1個のノードを盗聴するだけでは元のコンテンツcを復元できない。
【０１０８】
そこで、このステップＳ２５では、m(＜k)本のノード独立な経路を含み、かつm個の中継ノードが盗聴されて元のコンテンツcが漏洩する確率が最小となるように、部分コンテンツcpを配信するためのk本の経路が決定される。
【０１０９】
本実施形態では、以下に詳述する第６の整数計画法を解くことにより、このようなk本の経路が決定される。第６の整数計画法における定数は以下のように定義される。
【０１１０】
N：ネットワーク構成するノードの集合
n：ノード
NC：部分コンテンツを保持しているノードの集合
c：部分コンテンツを保持しているノード
d：配信先ノード
L：ネットワークを構成するリンクの集合
l：リンク
NK：盗聴されるm個の中継ノードの組合せの集合
NKj：NK内のj番目の組合せに含まれる中継ノードの集合
P j：NKjに含まれる全ての中継ノードが盗聴される確率
nin：ノードnを終点とするリンクの集合
nout：ノードnを始点とするリンクの集合
【０１１１】
また、変数が以下のように定義される。
【０１１２】
Xl(i)：i（1〜k）番目の経路がリンクlを通れば「１」、通らなければ「０」であるバイナリ変数
Yj(i)：i（1〜k）番目の経路がNKjに含まれる中継ノードを通れば「１」、通らなければ「０」であるバイナリ変数
Zj：全経路がNKjに含まれる中継ノードを通れば「１」、通らなければ「０」であるバイナリ変数
Obj：m個の中継ノードが盗聴されて元のコンテンツが漏洩する確率
【０１１３】
第６の整数計画法における制約式は次式(34)〜(36)の通りであり、これらは第５の整数計画法における経路保存則の制約式(27)〜(29)と同一である。
【０１１４】
【数３４】
【０１１５】
【数３５】
【０１１６】
【数３６】
【０１１７】
第６の整数計画法において、k本の経路の内、m本の経路がノード独立である条件は、次式(37)で与えられる。
【０１１８】
【数３７】
【０１１９】
さらに、本実施形態では盗聴される中継ノードの集合を経路が通る条件として次式(38)が与えられる。また、盗聴される中継ノードの集合を全ての経路が通る条件として次式(39)が与えられる。
【０１２０】
【数３８】
【０１２１】
【数３９】
【０１２２】
そして、盗聴されるm個の中継ノードの中の少なくとも１つの中継ノードを全ての経路が通過するとき、元のコンテンツが漏洩する。本発明の目的は、この様な確率を最小化することであるから、最小化すべき目的関数は次式(40)で与えられる。
【０１２３】
【数４０】
【０１２４】
本実施形態によれば、盗聴されると元のコンテンツを復元できてしまうような中継ノード数を最大化し、そのような組み合せの中継ノードが実際に全て盗聴される確率を最小化するような部分コンテンツの配信経路を決定できる。したがって、複数の配信元ノードで秘密分散保持されている部分コンテンツを、盗聴される可能性のあるノードを中継して配信する場合でも、安全なコンテンツ配信が可能になる。
【実施例３】
【０１２５】
上記の各実施形態では、本発明を(k，n)閾値秘密分散を利用したコンテンツ配信を例にして説明したが、本発明はこれのみに限定されるものではなく、経路上の各リンクまたは各ノード上で部分コンテンツが盗聴される確率を、各リンクまたは各中継ノードの障害確率と考えれば、k個の同一コンテンツをU個のノードから配信先ノードまで配信する際に、信頼性のより高いk本の経路を決定できる。
【０１２６】
すなわち、複数の同一データを一つの配信先ノードへ配信する冗長化において、多重リンク障害または多重ノード障害によってk本の経路が全て障害になり、コンテンツ配信が行えなくなる確率が最小化されるような配信経路を決定できるので、信頼性の高い冗長化が可能になる。
【符号の説明】
【０１２７】
１…配信元ノード
２…配信先ノード
３…ネットワーク
４…配信経路決定サーバ
【特許請求の範囲】
【請求項１】
配信対象のコンテンツを複数の部分コンテンツに分割してネットワーク上の配信元ノードに分散配置し、各配信元ノードから配信先ノードへ複数の経路で各部分コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、
ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数mを算出する手段と、
前記配信先ノードへ配信する部分コンテンツの数kが前記最大数m以下であると、当該m本のリンク独立な経路の中からk本の経路を決定する第１の決定手段と、
前記配信先ノードへ配信する部分コンテンツの数kが前記最大数mよりも多いと、当該m本のリンク独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、
前記各決定手段は、各経路のリンクが盗聴される確率に基づいて、全ての経路が盗聴される確率が最小となるk本の経路の組み合わせを決定することを特徴とするコンテンツ配信システムの配信経路決定装置。
【請求項２】
配信対象のコンテンツを複数の部分コンテンツに分割してネットワーク上の配信元ノードに分散配置し、各配信元ノードから配信先ノードへ複数の経路で各部分コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、
ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るノード独立な経路の最大数mを算出する手段と、
前記配信先ノードへ配信する部分コンテンツの数kが前記最大数m以下であると、当該m本のノード独立な経路の中からk本の経路を決定する第１の決定手段と、
前記配信先ノードへ配信する部分コンテンツの数kが前記最大数mよりも多いと、当該m本のノード独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、
前記各決定手段は、各経路上のノードが盗聴される確率に基づいて、全ての経路が盗聴される確率が最小となるk本の経路の組み合わせを決定することを特徴とするコンテンツ配信システムの配信経路決定装置。
【請求項３】
前記配信対象のコンテンツが(k，n)閾値秘密分散法に基づいてn分割され、各配信元ノードからは、n個の部分コンテンツの中のk個が重複無く配信されることを特徴とする請求項１または２に記載のコンテンツ配信システムの配信経路決定装置。
【請求項４】
ネットワーク上の配信元ノードに複数の同一コンテンツを分散配置し、各配信元ノードから配信先ノードへ複数の経路で各コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、
ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数mを算出する手段と、
前記配信先ノードへ配信するコンテンツの数kが前記最大数m以下であると、当該m本のリンク独立な経路の中からk本の経路を決定する第１の決定手段と、
前記配信先ノードへ配信するコンテンツの数kが前記最大数mよりも多いと、当該m本のリンク独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、
前記各決定手段は、各経路のリンクに障害が発生する確率に基づいて、全ての経路に障害が発生する確率が最小となるk本の経路の組み合わせを決定することを特徴とするコンテンツ配信システムの配信経路決定装置。
【請求項５】
ネットワーク上の配信元ノードに複数の同一コンテンツを分散配置し、各配信元ノードから配信先ノードへ複数の経路で各コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、
ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るノード独立な経路の最大数mを算出する手段と、
前記配信先ノードへ配信するコンテンツの数kが前記最大数m以下であると、当該m本のノード独立な経路の中からk本の経路を決定する第１の決定手段と、
前記配信先ノードへ配信するコンテンツの数kが前記最大数mよりも多いと、当該m本のノード独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、
前記各決定手段は、各経路上のノードに障害が発生する確率に基づいて、全ての経路に障害が発生する確率が最小となるk本の経路の組み合わせを決定することを特徴とするコンテンツ配信システムの配信経路決定装置。
【請求項１】
配信対象のコンテンツを複数の部分コンテンツに分割してネットワーク上の配信元ノードに分散配置し、各配信元ノードから配信先ノードへ複数の経路で各部分コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、
ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数mを算出する手段と、
前記配信先ノードへ配信する部分コンテンツの数kが前記最大数m以下であると、当該m本のリンク独立な経路の中からk本の経路を決定する第１の決定手段と、
前記配信先ノードへ配信する部分コンテンツの数kが前記最大数mよりも多いと、当該m本のリンク独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、
前記各決定手段は、各経路のリンクが盗聴される確率に基づいて、全ての経路が盗聴される確率が最小となるk本の経路の組み合わせを決定することを特徴とするコンテンツ配信システムの配信経路決定装置。
【請求項２】
配信対象のコンテンツを複数の部分コンテンツに分割してネットワーク上の配信元ノードに分散配置し、各配信元ノードから配信先ノードへ複数の経路で各部分コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、
ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るノード独立な経路の最大数mを算出する手段と、
前記配信先ノードへ配信する部分コンテンツの数kが前記最大数m以下であると、当該m本のノード独立な経路の中からk本の経路を決定する第１の決定手段と、
前記配信先ノードへ配信する部分コンテンツの数kが前記最大数mよりも多いと、当該m本のノード独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、
前記各決定手段は、各経路上のノードが盗聴される確率に基づいて、全ての経路が盗聴される確率が最小となるk本の経路の組み合わせを決定することを特徴とするコンテンツ配信システムの配信経路決定装置。
【請求項３】
前記配信対象のコンテンツが(k，n)閾値秘密分散法に基づいてn分割され、各配信元ノードからは、n個の部分コンテンツの中のk個が重複無く配信されることを特徴とする請求項１または２に記載のコンテンツ配信システムの配信経路決定装置。
【請求項４】
ネットワーク上の配信元ノードに複数の同一コンテンツを分散配置し、各配信元ノードから配信先ノードへ複数の経路で各コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、
ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るリンク独立な経路の最大数mを算出する手段と、
前記配信先ノードへ配信するコンテンツの数kが前記最大数m以下であると、当該m本のリンク独立な経路の中からk本の経路を決定する第１の決定手段と、
前記配信先ノードへ配信するコンテンツの数kが前記最大数mよりも多いと、当該m本のリンク独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、
前記各決定手段は、各経路のリンクに障害が発生する確率に基づいて、全ての経路に障害が発生する確率が最小となるk本の経路の組み合わせを決定することを特徴とするコンテンツ配信システムの配信経路決定装置。
【請求項５】
ネットワーク上の配信元ノードに複数の同一コンテンツを分散配置し、各配信元ノードから配信先ノードへ複数の経路で各コンテンツを配信するコンテンツ配信システムの配信経路決定装置において、
ネットワークのトポロジに基づいて、各配信元ノードから配信先ノードへ至るノード独立な経路の最大数mを算出する手段と、
前記配信先ノードへ配信するコンテンツの数kが前記最大数m以下であると、当該m本のノード独立な経路の中からk本の経路を決定する第１の決定手段と、
前記配信先ノードへ配信するコンテンツの数kが前記最大数mよりも多いと、当該m本のノード独立な経路を含むk本の経路を決定する第２の決定手段とを具備し、
前記各決定手段は、各経路上のノードに障害が発生する確率に基づいて、全ての経路に障害が発生する確率が最小となるk本の経路の組み合わせを決定することを特徴とするコンテンツ配信システムの配信経路決定装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１１−１３９２４０（Ｐ２０１１−１３９２４０Ａ）
【公開日】平成２３年７月１４日（２０１１．７．１４）
【国際特許分類】
【出願番号】特願２００９−２９７２６２（Ｐ２００９−２９７２６２）
【出願日】平成２１年１２月２８日（２００９．１２．２８）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２３年７月１４日（２０１１．７．１４）
【国際特許分類】
【出願日】平成２１年１２月２８日（２００９．１２．２８）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]