(57)【要約】【課題】複数の配信元ノードに部分コンテンツが重複保持を許容して分散配置され、配信先ノードが不特定多数となるようなデータ配信において、各配信元ノードが配信する部分コンテンツを適正化できるコンテンツ配信システムの配信制御装置を提供する。【解決手段】コンテンツ配信決定グラフは、擬似配信元ノードVaと、各配信元ノードNsに分散配置されている部分コンテンツcpを一つずつ仮想的に保持するn個の部分コンテンツノードVbと、各配信元ノードNs1，Ns2…に対応し、各部分コンテンツノードVbから配信される部分コンテンツcpを配信先へ転送する配信元対応ノードVc1，Vc2…と、配信先ノードNdに対応する配信先対応ノードVdとから構成される。各配信元対応ノードVcは、当該各配信元対応ノードVc1，Vc2…に対応する各配信元ノードNs1，Ns1…に分散配置されている部分コンテンツcpを保持する各部分コンテンツノードVbと容量が「１」のリンクで接続される。【選択図】図２
2011134246.tif 000002
【特許請求の範囲】
【請求項１】
配信対象のコンテンツを複数の部分コンテンツに分割してネットワーク上の複数の配信元ノードに分散配置し、各配信元ノードから配信先ノードへ所定数の部分コンテンツを重複無く配信するコンテンツ配信システムの配信制御装置において、
各部分コンテンツの配置状況に基づいて、各配信元ノードが配信する部分コンテンツの選択を最大フロー問題として解けるコンテンツ配信グラフを生成する手段と、
前記コンテンツ配信グラフの最大フロー問題を解いて、各配信元ノードが配信する部分コンテンツを決定する手段とを具備し、
前記コンテンツ配信グラフが、
各部分コンテンツを一つずつ仮想的に保持する部分コンテンツノードと、
前記配信先ノードに対応する配信先対応ノードと、
各配信元ノードに対応し、前記各部分コンテンツノードから配信された部分コンテンツを前記配信先対応ノードへ転送する複数の配信元対応ノードと、
各配信元対応ノードを、当該配信元対応ノードに対応する配信元ノードに分散配置されている部分コンテンツを保持している部分コンテンツノードと、一つの部分コンテンツに対応した容量で接続するリンクとを含むことを特徴とするコンテンツ配信システムの配信制御装置。
【請求項２】
前記コンテンツ配信グラフが、各配信元対応ノードと配信先対応ノードとを、当該配信元対応ノードに対応する配信元ノードに設定されている部分コンテンツの配信数に応じた容量で接続するリンクを含むことを特徴とする請求項１に記載のコンテンツ配信システムの配信制御装置。
【請求項３】
前記コンテンツ配信グラフが、各部分コンテンツノードと一つの部分コンテンツに対応した容量のリンクで接続される擬似配信元ノードを含むことを特徴とする請求項１または２に記載のコンテンツ配信システムの配信制御装置。
【請求項４】
前記配信対象のコンテンツが（k，n）閾値秘密分散法に基づいてn分割され、前記コンテンツ配信グラフでは、n個の部分コンテンツノードの中の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個の部分コンテンツが漏れなく、かつ重複なく配信されるように、k個の部分コンテンツをどの配信元ノードから配信先ノードへ配信させるのかを適正に決定する必要がある。しかしながら、上記の従来技術では、秘密分散保持を上記のようなコンテンツ配信に適用する場合の技術課題が認識されていなかった。
【０００９】
本発明の目的は、上記した従来技術の課題を解決し、複数の配信元ノードに部分コンテンツが重複保持を許容して分散配置され、配信先ノードが不特定多数となるようなデータ配信において、各配信元ノードが配信する部分コンテンツを適正化できるコンテンツ配信システムの配信制御装置を提供することにある。
【課題を解決するための手段】
【００１０】
上記の目的を達成するために、本発明は、配信対象のコンテンツを複数の部分コンテンツに分割してネットワーク上の複数の配信元ノードに分散配置し、各配信元ノードから配信先ノードへ所定数の部分コンテンツを重複無く配信するコンテンツ配信システムの配信制御装置において、以下のような手段を講じた点に特徴がある。
【００１１】
(1)各部分コンテンツの配置状況に基づいて、各配信元ノードが配信する部分コンテンツの選択を最大フロー問題として解けるコンテンツ配信グラフを生成する手段と、コンテンツ配信グラフの最大フロー問題を解いて、各配信元ノードが配信する部分コンテンツを決定する手段とを具備し、前記コンテンツ配信グラフが、各部分コンテンツを一つずつ仮想的に保持する部分コンテンツノードと、配信先ノードに対応する配信先対応ノードと、各配信元ノードに対応し、前記各部分コンテンツノードから配信された部分コンテンツを前記配信先対応ノードへ転送する複数の配信元対応ノードと、各配信元対応ノードを、当該配信元対応ノードに対応する配信元ノードに分散配置されている部分コンテンツを保持している部分コンテンツノードと、一つの部分コンテンツに対応した容量で接続するリンクとを含むことを特徴とする。
【００１２】
(2)コンテンツ配信グラフが、各配信元対応ノードと配信先対応ノードとを、当該配信元対応ノードに対応する配信元ノードに設定されている部分コンテンツの配信数に応じた容量で接続するリンクを含むことを特徴とする。
【００１３】
(3)コンテンツ配信グラフが、各部分コンテンツノードと一つの部分コンテンツに対応した容量のリンクで接続される擬似配信元ノードを含むことを特徴とする。
【００１４】
(4)配信対象のコンテンツが（k，n）閾値秘密分散法に基づいてn分割され、コンテンツ配信グラフでは、n個の部分コンテンツノードの中のk個から部分コンテンツが配信されることを特徴とする。
【発明の効果】
【００１５】
本発明によれば、以下のような効果が達成される。
【００１６】
(1)部分コンテンツが複数の配信元ノードに重複して分割配置されているときにでも、各配信元ノードが配信する部分コンテンツの選択を、部分コンテンツが分散配置されている状況を模したコンテンツ配信グラフ上の最大フロー問題を解くことで決定できるようになる。
【００１７】
(2)コンテンツ配信グラフに部分コンテンツノードを仮想的に設け、各配信元ノードに対応した配信元対応ノードと接続して最大フロー問題を解くようにしたので、各配信元ノードが実際には保持していない部分コンテンツを配信するような決定を避けることができ、その結果、部分コンテンツの配信漏れを防ぐことができる。
【００１８】
(3)コンテンツ配信グラフに擬似配信元ノードを設けて各部分コンテンツノードと容量が「１」のリンクで接続し、最大フロー問題を解くようにしたので、各部分コンテンツが２つ以上の配信元ノードから重複して配信されることを防ぐことができる。
【００１９】
(4)コンテンツを（k，n）閾値秘密分散法に基づいて配信する際に、各配信元ノードから配信する部分コンテンツを適正に決定できるようになる。
【図面の簡単な説明】
【００２０】
【図１】本発明が適用されるコンテンツ配信システムのネットワーク構成を示した図である。
【図２】コンテンツ配信決定グラフの一例を示した図である。
【図３】本発明の一実施形態の動作を示したフローチャートである。
【図４】コンテンツ配信グラフの一例を示した図である。
【図５】最大フロー問題の解決手順を示したフローチャートである。
【図６】最大フロー問題の解決手順を模式的に示した図である。
【図７】最大フロー問題の解決結果を模式的に示した図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明が適用されるコンテンツ配信システムのネットワーク構成を示した図であり、ここでは、（k，n）閾値秘密分散を利用したコンテンツ配信を例にして説明する。
【００２２】
配信元ノードNs(Ns1，Ns2…)には、一つのコンテンツcをn分割して得られるn個の部分コンテンツcp1，cp2…cpn（以下、cpで代表することもある)のうち、k個未満の少なくとも一つが、各配信元ノードNs間での重複保持を許容して分散配置されている。配信先ノードNdは、k個の部分コンテンツcpからコンテンツcを再現するコンテンツ再現機能を備えている。コンテンツ配信制御サーバScは、配信先ノードNdへk個の部分コンテンツcpが重複無く配信されるように、各配信元ノードNsが配信する部分コンテンツcpを決定して各配信元ノードNsへ通知する。各配信元ノードNsは、通知された部分コンテンツcpのみを選択的に配信する。
【００２３】
前記配信制御サーバScにおいて、部分コンテンツ管理部１０１は、n個の部分コンテンツcpがどの配信元ノードNsに分散配置されているのかを示す分散配置情報を管理する。コンテンツ配信グラフ生成部１０２は、各部分コンテンツcpの配置状況に基づいて、各配信元ノードNsが配信する部分コンテンツcpの選択を最大フロー問題として解くためのコンテンツ配信グラフを生成する。配信決定部１０３は、前記コンテンツ配信グラフ上の最大フロー問題を解くことで、各配信元ノードNsから配信する部分コンテンツcpを決定して各配信元ノードNsへ通知する。
【００２４】
図２は、前記コンテンツ配信決定グラフの一例を示した図であり、擬似配信元ノードVaと、前記各配信元ノードNsに分散配置されている部分コンテンツcpを一つずつ仮想的に保持するn個の部分コンテンツノードVbと、前記各配信元ノードNs1，Ns2…に対応し、各部分コンテンツノードVbから配信される部分コンテンツcpを配信先へ転送する配信元対応ノードVc（Vc1，Vc2…）と、前記配信先ノードNdに対応する配信先対応ノードVdとを主要なノードとして構成される。
【００２５】
本実施形態では、配信元ノードNsの数および各配信元ノードNsに分散配置されている部分コンテンツcpが既知であるものとし、各配信元対応ノードVcは、当該各配信元対応ノードVc1，Vc2…に対応する各配信元ノードNs1，Ns1…に分散配置されている部分コンテンツcpを保持する各部分コンテンツノードVbと、容量が「１」のリンクで接続されている。したがって、例えば配信元ノードNs1に３つの部分コンテンツcp1，cp2，cp3が分散配置されていれば、各部分コンテンツcp1，cp2，cp3を保持する３つの部分コンテンツノードVb1，Vb2，Vb3と配信元対応ノードVc1とは、容量が「１」の３本の仮想リンクでそれぞれ接続されることになる。
【００２６】
さらに、本実施形態では各配信元ノードNsから配信先ノードNdへ配信する部分コンテンツの数が予め規定されており、各配信元対応ノードVcと配信先対応ノードVdとは、各配信元対応ノードVcに対応する配信元ノードNsが配信する部分コンテンツcpの数に一致する容量で接続されている。したがって、例えば配信元ノードNs1が２つの部分コンテンツcpを配信するように規定されていれば、配信元対応ノードVc1と配信先対応ノードVdとは容量「２」のリンクで接続されることになる。
【００２７】
次いで、フローチャートを参照して本発明の一実施形態の動作を説明する。図３は、本発明の一実施形態の動作を示したフローチャートであり、主に前記配信制御サーバScの動作を示している。
【００２８】
ステップＳ１では、前記コンテンツ配信グラフ生成部１０２により、前記部分コンテンツcpの分散配置情報に基づいてコンテンツ配信グラフが生成される。ここでは、３つの配信元ノードNs1，Ns2，Ns3に５つの部分コンテンツcp1〜cp5が分散配置され、そのうちの４つでコンテンツcを再現できる（４，５）閾値秘密分散を例にして説明する。
【００２９】
したがって、コンテンツ配信グラフでは、図４に一例を示したように、擬似配信元ノードVaに５つの部分コンテンツノードVb1〜Vb5が容量「１」の仮想リンクで接続されている。また、２つの配信元ノードNs1，Ns3がいずれも一つの部分コンテンツcpを配信し、配信元ノードNs2が２つの部分コンテンツcpを配信するものと規定されているので、配信元対応ノードVc1，Vc3と配信先対応ノードVdとは容量「１」のリンクで接続され、配信元対応ノードVc2と配信先対応ノードVdとは容量「２」のリンクで接続されることになる。したがって、各配信元対応ノードVcと配信先対応ノードVdとを接続するリンク容量の合計は、配信すべき部分コンテンツ数kに相当する容量となる。
【００３０】
ステップＳ２では、前記コンテンツ配信グラフ上で最大フロー問題を解き、擬似配信元ノードVaから配信先対応ノードVdまで、容量が「１」のフローを最大数流すための経路が求められる。その結果、擬似配信元ノードVaから配信先対応ノードVdへ至るk本（ここでは、４本）の経路が決定され、各部分コンテンツノードVbと各配信元対応ノードVcとの接続関係に基づいて、各配信元ノードNsから配信される部分コンテンツcpが決定される。
【００３１】
図５は、前記コンテンツ配信グラフ上の最大フロー問題を解く手順の一例を示したフローチャートであり、図６は、前記コンテンツ配信グラフ上で経路が確保される様子を模式的に示した図である。
【００３２】
ステップＳ１０１では、擬似配信元ノードVaから配信先対応ノードVdに至る容量「１」の空き経路の有無が判定される。初めは空き経路が有ると判定されるのでステップＳ１０２へ進み、擬似配信元ノードVaから配信先対応ノードVdへ至る容量「１」の擬似経路が確保されて容量が「１」のフローが流される。ここでは、図６に示したように、擬似配信元ノードVa→部分コンテンツノードVb1→配信元対応ノードVc1→配信先対応ノードVdの経路L1が確保され、容量が「１」のフローが流されたものとして説明を続ける。ステップＳ１へ戻り、ここでも空き経路が有ると判定されるのでステップＳ２へ進み、今度は、擬似配信元ノードVa→部分コンテンツノードVb3→配信元対応ノードVc2→配信先対応ノードVdの経路L2が確保され、容量が「１」のフローが流されたものとして説明を続ける。
【００３３】
一方、擬似配信元ノードVaから部分コンテンツノードVb2および配信元対応ノードVc1を経由する経路では、配信元対応ノードVc1から配信先対応ノードVdへ向かうリンクの容量が前記擬似経路L1で既に消費されており、空き容量が無いと判定されるのでステップＳ１０３へ進む。ステップＳ１０３では、既に容量「１」以上のフローが流れているリンクを逆向きに辿ることにより、擬似配信元ノードVaから配信先対応ノードVdに至る容量「１」の空き経路が存在するか否かが判定される。ここでは、配信元対応ノードVc1から部分コンテンツノードVb1へ向かうリンクを逆向きに辿ることにより、配信先対応ノードVdへ至る空きの擬似経路L3を確保できるのでステップＳ１０４へ進む。
【００３４】
ステップＳ１０４では、擬似配信元ノードVa→部分コンテンツノードVb2→配信元対応ノードVc1→部分コンテンツノードVb1→配信元対応ノードVc2→配信先対応ノードVdの経路L3が構築されて容量が「１」のフローが流される。
【００３５】
ステップＳ１０５では、前記逆向きに辿ったリンクのフロー流量が修正される。すなわち、最大フロー問題を解くアルゴリズムでは、各リンクのフロー流量は逆向きのフロー流量分だけ減ぜられるので、前記配信元対応ノードVc1と部分コンテンツノードVb1とを接続するリンクのフロー流量が「０」に修正される。これにより、前記部分コンテンツノードVb1から配信元対応ノードVc1へ向かうリンクを通る経路L1，L3を流れるフローの経路が変更されることになる。
【００３６】
同様に、擬似配信元ノードVaから部分コンテンツノードVb5および配信元対応ノードVc2を経由する経路でも、配信元対応ノードVc2から配信先対応ノードVdへ至るリンクの容量が前記２つの経路L2，L3により既に消費されており、空き容量が無いと判定されるのでステップＳ１０３へ進む。ステップＳ１０３では、既に容量「１」以上のフローが流れているリンクを逆向きに辿ることにより、擬似配信元ノードVaから配信先対応ノードVdに至る容量「１」の空き経路が存在するか否かが判定される。ここでは、配信元対応ノードVc2から部分コンテンツノードVb3へ向かうリンクを逆向きに辿ることにより、配信先対応ノードVdへ至る空き経路L4を確保できるのでステップＳ１０４へ進む。
【００３７】
ステップＳ１０４では、擬似配信元ノードVa→部分コンテンツノードVb5→配信元対応ノードVc2→部分コンテンツノードVb3→配信元対応ノードVc3→配信先対応ノードVdの経路L4が構築されて容量が「１」のフローが流される。ステップＳ１０５では、前記逆向きに辿ったリンクのフロー流量が「０」に修正され、経路L2，L4を流れるフローの経路が変更される。
【００３８】
これに対して、擬似配信元ノードVaから部分コンテンツノードVb4を経由する経路に関しては、前記ステップＳ１０３において、逆向きにリンクを辿ることを考慮しても容量を確保できないと判定されるので、その経路確立が不可能と判定されて当該処理を終了する。
【００３９】
図７は、上記の手順により得られる最大フロー経路の一例を示した図であり、擬似配信元ノードVaから４つの異なる部分コンテンツノードVb1，Vb2，Vb3，Vb5をそれぞれ経由し、さらに３つの配信元対応ノードVc1，Vc2，Vc3を経由して配信先対応ノードVdへ至る４つの経路L1〜L4が形成されている。したがって、本実施形態では配信元ノードNs1には部分コンテンツcp2を配信させ、配信元ノードNs2には２つの部分コンテンツcp1，cp5を配信させ、配信元ノードNs3には部分コンテンツcp3を配信させれば良いことが判る。
【００４０】
このように、本実施形態によれば、コンテンツ配信グラフに部分コンテンツノードVbを仮想的に設けて各配信元対応ノードVcと接続し、最大フローを流す経路を探索することにより、各配信元ノードNsが実際には保持していない部分コンテンツcpを配信するような決定を避けることができる。したがって、部分コンテンツcpの配信漏れを防ぐことができる。
【００４１】
また、本実施形態によれば、擬似配信元ノードVaを設けて各部分コンテンツノードVbと容量「１」のリンクで接続し、最大フローを流す経路を探索することにより、各部分コンテンツcpが２つ以上の配信元ノードNsから重複して配信されることを防ぐことができる。
【符号の説明】
【００４２】
１０１…部分コンテンツ管理部
１０２…コンテンツ配信グラフ生成部
１０３…配信決定部
Ns…配信元ノード
Nd…配信先ノード
cp…部分コンテンツ
Va…擬似配信元ノード
Vb…部分コンテンツノード
Vc…配信元対応ノード
Vd…配信先対応ノード
【図１】
2011134246.tif 000003
【図２】
2011134246.tif 000004
【図３】
2011134246.tif 000005
【図４】
2011134246.tif 000006
【図５】
2011134246.tif 000007
【図６】
2011134246.tif 000008
【図７】
2011134246.tif 000009