JP2012070169A - 配信経路決定装置及び方法 - Google Patents

Abstract

【課題】コンテンツ分散配信等に用いる、経路間の共通リンク部分を避け安全性の高い複数の配信経路を少ない計算資源で計算できる配信経路決定装置を提供する。
【解決手段】複数の配信元ノードのいずれかより配信先ノードに至る複数の配信経路を決定する配信経路決定装置１を、経路探索の起点となる根ノードを順次に選択する根ノード選択手段２と、根ノードの隣接ノードごとに、いずれかの配信元ノードへ到達する最短経路として上流側経路を探索する経路探索手段３と、当該隣接ノードと配信先ノードとを結ぶ下流側経路と上流側経路とを接続してコンテンツ配信経路を確立する経路確立手段４と、確立された経路を構成するリンクの距離が長くなるよう補正するリンク距離補正手段５とを具備して提供する。根ノードは配信先ノードから始まる幅優先探索の順で選択する。
【選択図】図１０Ｂ

Description

本発明は、コンテンツを分散配信するための配信経路を決定する配信経路決定装置及び方法に係り、特に、安全性の高い配信経路を、実用規模のネットワークにおいても計算可能な少ない計算資源を使って計算し決定できる配信経路決定装置及び方法に関する。

１つのコンテンツを暗号化されたn個の部分コンテンツに分割し、n個の部分コンテンツのうち、k(≦n)個以上の部分コンテンツが集まらないと元のコンテンツを復元できないように秘密分散する(k, n)閾値秘密分散が非特許文献１に開示されている。また、データ保持のリスク分散を図るために、n個に分割された部分コンテンツを複数のノードで秘密分散保持する技術が特許文献１，２に開示されている。

こうした技術は盗聴を困難とするコンテンツ配信に利用することができ、(k, n)閾値秘密分散を用いる場合であれば少なくともk個の部分コンテンツをネットワーク上の配信元ノードに分散配置して、元データを復元しようとする配信先ノードに対して、各部分コンテンツを保持する配信元ノードから配信を行うことでコンテンツ配信を実現する。

しかしこのとき、各部分コンテンツの配信経路が同一リンクや同一ノードを通っていると、k本未満のリンクやk個未満のノードが盗聴されるだけで元のデータが復元されてしまい、安全性が低下する。

また盗聴以外の危険性として、同様に各部分コンテンツの配信経路が同一リンクや同一ノードを通っていると、k本未満のリンクやk個未満のノードに障害が発生するだけで、配信先ノードでコンテンツの復元が不可能となってしまう。

よって(k, n)閾値秘密分散などを利用したコンテンツ配信において盗聴や障害発生などのリスクに強い配信を実現するには、k本の経路ができる限り同一リンクや同一ノードを通らないようにし、且つ異なる経路間に共通部分が生じる状況が避けられない場合であっても、できる限り安全性を確保するような経路を選択するようにすることが要求される。

またこのような経路選択技術は盗聴を困難とするコンテンツ配信以外にも利用でき、例えば同一コンテンツを複数の経路により冗長化して配信する場合にこのような経路選択を適用すれば安全性が向上する。

このような経路選択の従来技術として特許文献３では、複数のノードで秘密分散保持されているk個の部分コンテンツを、ネットワークを介して配信先ノードまで転送する際に、全ての部分コンテンツが転送途中に盗聴される確率が最小となるような配信経路を算出する技術が開示されている。

また特許文献３では、複数のノードで保持されているコンテンツを、k本の経路を使って配信先ノードまで転送する際に、全ての経路が障害になって、配信先ノードまでコンテンツを転送できない確率が最小となるような配信経路を算出する技術が開示されている。

特開２００９−１２２７３１号公報 特開２００９−１０５３１号公報 特願２００９−２９７２６２号

Shamir, Adi (1979), "How to share a secret", Communications of the ACM 22 (11): 612-613

しかしながら特許文献３に開示された従来技術では、整数計画法を解くことによってコンテンツ配信経路を計算しているので、実用規模のネットワークに対して適用すると、計算資源の制約から、短時間で配信経路を算出することができないという課題がある。

本発明の目的は、上記した従来技術の課題を解決し、閾値秘密分散される等した複数の部分コンテンツとして又は同一コンテンツを複数同時に冗長化してといったような配信形態によってコンテンツを配信するシステムにおいて、盗聴や障害に対する信頼性の高い配信経路を、少ない計算資源を使って計算できる配信経路決定装置及び方法を提供することにある。

上記した従来技術の課題を解決するために、本発明は、ネットワーク上で複数の配信元ノードから配信先ノードへコンテンツを分散配信する複数のコンテンツ配信経路を決定する経路決定装置において、以下のような手段を講じた点に特徴がある。

（１）経路探索の起点となる根ノードを重複なく順次に選択する根ノード選択手段と、前記選択された根ノードの隣接ノードごとに、当該隣接ノードからいずれかの前記配信元ノードへ到達する最短経路として上流側経路を探索する経路探索手段と、前記隣接ノードごとに探索された上流側経路と、当該隣接ノードと前記配信先ノードとを結ぶ下流側経路と、を接続して前記コンテンツ配信経路を確立する経路確立手段とを具備し、前記根ノード選択手段は、前記配信先ノードを最初の根ノードに選択する第１ステップと、前記第１ステップの後、前記配信先ノードを根ノードとして上流側経路を探索された隣接ノードの集合から根ノードを順次に選択する第２ステップと、前記第２ステップの後、前記コンテンツ配信経路の確立本数が目標数に達するまで、上流側経路を探索された隣接ノードの集合から前記根ノードを順次に選択することを繰り返す第３ステップとを実行することを特徴とする。

（２）前記根ノード選択手段は、選択した根ノードの全隣接ノードに対して前記コンテンツ配信経路が確立されてから次の根ノードを選択し、前記第３ステップにおいて根ノードを前記配信先ノードからのホップ数の小さい順に選択することを特徴とする。

（３）前記経路探索手段は、前記選択された根ノードの隣接ノードであり且つ当該根ノードの選択以前に前記下流側経路のうちいずれかを構成するノードにはなっていないノードごとに、当該隣接ノードからいずれかの前記配信元ノードへ到達する最短経路として上流側経路を探索することを特徴とする。

（４）前記経路探索手段は、前記選択された根ノードの隣接ノードであり且つ前記経路確立手段にて既に確立された前記コンテンツ配信経路上には存在しないノードごとに、当該隣接ノードからいずれかの前記配信元ノードへ到達する最短経路として上流側経路を探索することを特徴とする。

（５）前記根ノード選択手段は前記第２ステップおよび前記第３ステップにおいて、上流側経路を前記探索された隣接ノードの集合から当該上流側経路の距離が短い順に根ノードを順次に選択することを特徴とする。

（６）前記経路確立手段により前記コンテンツ配信経路が確立される都度、既に確立されたコンテンツ配信経路群を構成する各リンクのリンク距離であって且つ前記経路探索手段が前記上流側経路を最短経路として探索するのに参照するリンク距離を補正するリンク距離補正手段をさらに具備することを特徴とする。

本発明によれば、以下のような効果が達成される。

（１）配信先ノードを最初の根ノードとして根ノードを順次選択してその隣接ノードを選ぶことにより、配信先ノードの存在する下流側においてあらかじめ分散させた下流側経路と、最短経路計算により求める上流側経路とを接続して順次コンテンツ配信経路を確定するので、従来技術と比べて少ない計算負荷で分散した安全なコンテンツ配信経路を決定することができる。

（２）下流側経路群が、その端点が配信先ノードから近い順に順次枝分かれさせて構築されていくことにより、あらかじめ分散させて構築され、安全なコンテンツ配信経路を決定できる。

（３）下流側経路群が重複なく構築され、安全なコンテンツ配信経路を決定することができる。

なお、前記（１）〜（３）の特徴によれば、下流側経路群が、配信先ノードを最初の根ノードとする幅優先探索によるノード訪問の順に従ってあらかじめ分散させて構築され、安全なコンテンツ配信経路を決定することができる。

（４）１本の下流側経路の端点からは１本のみの上流側経路が定められ、分散した安全なコンテンツ配信経路を決定することができる。

（５）配信元ノードに近い側のノードから順に、経路探索の起点となる根ノードが選択されるので、全体としてのリンク距離の短い、安全なコンテンツ配信経路を決定することができる。

（６）確立したコンテンツ配信経路のリンク距離が長くなるよう補正して、以降の上流側経路を探索するので、上流側経路同士の重複部分が生じる傾向を抑制して上流側経路が探索され、安全なコンテンツ配信経路を決定することができる。

配信経路決定装置によって決定した配信経路によりコンテンツ配信が行われているネットワークを示す図である。 配信経路決定装置が最適な経路を選択する概略を説明するための図である。 図２の配信経路を確立するにあたって始めに配信先ノードが根ノードとして選択され、その隣接ノード（第１隣接ノード）から上流側経路が探索されることを示す図である。 図３の探索による上流側経路と下流側経路とを結んだ経路としてコンテンツ配信経路が確立されることを示す図である。 図４の状態の次に、第１隣接ノードのうち、探索された上流側経路のうち距離が最短の経路が経由するノードが新たな根ノードに選ばれて、その隣接ノード（第２隣接ノード）から上流側経路が探索されることを示す図である。 図５の状態の次に、探索された上流側経路と下流側経路とを結んだ経路としてコンテンツ配信経路が確立されることを示す図である。 図６の状態の次に、第１隣接ノードのうち、探索された上流側経路のうち距離が最短から２番目の経路が経由するノードが新たな根ノードに選ばれて、その隣接ノード（第２隣接ノード）から上流側経路が探索されることを示す図である。 図７の状態の次に、探索された上流側経路と下流側経路とを結んだ経路としてコンテンツ配信経路が確立されることを示す図である。 図８の状態の次以降も同様に第１隣接ノードが順次、根ノードとして選ばれてその隣接ノードから上流側経路が探索され下流側経路と結合して配信経路が確立され、目標数に達するまで同様にしてさらに第２隣接ノードが順次、根ノードとして選ばれて同様に配信経路が確立されていく様子を示す図である。 基本の一実施形態における配信経路決定装置の機能ブロック図である。 詳細な一実施形態における配信経路決定装置の機能ブロック図である。 幅優先探索の定める順に根ノードを辿って配信経路を確定していく実施形態における処理のフローチャートである。 図１１のフローによりネットワーク上に配信経路が確定されていく例を示す図である。 リンク距離補正を説明するためのネットワーク構成例を示す図である。 リンク距離補正を説明するためのネットワーク構成例を示す図である。 リンク距離補正を説明するためのネットワーク構成例を示す図である。 リンク距離補正の効果を説明する例を示す図である。

以下、図面を参照して本発明を詳細に説明する。図１に、本発明の配信経路決定装置１によって決定・確立されたk本の転送経路によって、コンテンツ配信が行われているネットワークを示す。コンテンツを保持する配信元ノードは、同図に示すようにc1, c2, c3, …,cCの計C個である。同図に示すように、これら各配信元ノードci(i＝１〜C)は、配信先ノードd及び配信経路決定装置１と共に、当該コンテンツ配信の行われるネットワーク上に存在している。

計Ｃ個の各配信元ノードci(i＝１〜C)と配信先ノードdとのネットワーク上の位置は、アドレス情報などによって所与の位置が与えられているものとする。配信経路決定装置１は、各配信元ノードciのいずれかを始点とし、終点である配信先ノードdへ到着する、所定数k本のコンテンツ配信経路を計算する。また配信経路決定装置１は、計算結果を各配信元ノードciに通知することで、当該計算結果に従うコンテンツ配信を行えるようにする。

当該コンテンツ配信は、配信の冗長化を目的とした配信であって、k本の経路により同一の単一コンテンツを配信するものであってもよい。また当該コンテンツ配信は、(k, n)閾値秘密分散等を適用した盗聴防止を目的とした配信であって、n個の部分コンテンツのうち元コンテンツを復元できる任意のk個の部分コンテンツを、k本の経路により配信するものであってもよい。

配信経路計算の結果、配信元ノードciのうちコンテンツを配信しないことになるノードがあってもよい。所定数kが配信元ノード数Cよりも小さい場合は、こうした配信しないノードが必ずある。また計算の結果、配信元ノードciのうち複数のコンテンツを配信することになるノードがあってもよく、k>Cの場合、このようなノードが必ずある。

また、例えば(k, n)閾値秘密分散を利用した配信を行う場合であれば、各配信元ノードは(k, n)閾値秘密分散を適用した各部分コンテンツを予め保持しているものとする。そして配信経路計算結果により、自身が配信元となることが決定された部分コンテンツを、指定配信経路にて配信先ノードへ配信するものとする。

次に、配信経路決定装置１が上述のような配信経路を順次に確立していく流れの概略と、当該確立を行う際に用いられる基本的な概念（上流側経路、最短到達経路として求まる下流側経路、など）とを説明する。当該概略説明においては説明の便宜上、配信経路確立の流れの部分のみに注目して説明するが、これは基本的な一実施形態である。そして当該概略説明の後に、最短到達経路の算出の詳細などを含む、より詳細な各実施形態についてさらに説明する。

図２に示すように、複数のコンテンツ配信元ノードc1〜cCから唯一のコンテンツ配信先ノードdへ向けて、冗長化や閾値分散を目的に複数の経路でコンテンツを配信する際の、最適な経路決定について考える。

始めに、図３に示したように、経路探索の起点となる根ノードとしてコンテンツ配信先ノードdが選択され、当該根ノードからのホップ数が「１」の隣接ノード（第１隣接ノード）N11，N12，N13…ごとに、前記配信元ノードci(i＝1〜C)のいずれかに最短で到達できる上流側経路Pupp(Pupp1，Pupp2，Pupp3…)が探索される。

次いで、各上流側経路Puppを、前記各第１隣接ノードN11，N12，N13…から根ノード経由でコンテンツ配信先ノードd（ここでは、根ノードとコンテンツ配信先ノードdとが同一）へ至る各下流側経路Plow(Plow1，Plow2，Plow3…)と連結することで、図４に示したように、各コンテンツ配信元ノードci(i＝1〜C)のいずれかとコンテンツ配信先ノードdとを結ぶ複数のコンテンツ配信経路Pcd１，Pcd２，Pcd３，…(Pupp1+Plow1，Pupp2+Plow2，Pupp3+Plow3…)が、新規に確立される。すなわち、図１のようなコンテンツ配信を行うのに実際に用いることとなるk本の経路の一員となる経路として、当該時点において新規に決定される。さらに、前記各上流側経路Puppの距離が算出され、ここでは、距離が短い順にPupp2，Pupp1，Pupp3の結果が得られたものとして説明を続ける。

次いで、図５に示したように、前記距離が最短の上流側経路Pupp2が経由する前記第１隣接ノードN12が根ノードに選択され、新たな根ノードN12からのホップ数が「１」の隣接ノード（第２隣接ノード）N121，N122，N123…の集合から、既に確立済みのコンテンツ配信経路Pcd2が経由するノードN121を除く残りの第２隣接ノードN122，N123…ごとに、前記コンテンツ配信元ノードci(i＝1〜C)のいずれかに最短で到達できる上流側経路Pupp(Pupp4，Pupp5…)が探索される。

次いで、各上流側経路Pupp4，Pupp5…を、前記各第２隣接ノードN122，N123…から根ノードN12を中継して配信先ノードdへ至る下流側経路Plow(Plow4，Plow5…)と連結することで、図６に示したように、各コンテンツ配信元ノードci(i＝1〜C)のいずれかとコンテンツ配信先ノードdとを結ぶコンテンツ配信経路Pcd4，Pcd5，…(Pupp4+Plow4，Pupp5+Plow5…)が、既に確立済みのPcd2等に対して、さらに追加して確立される。

次いで、図７に示したように、前記第１隣接ノード集合(N11，N12，N13…)の中で、上流側経路がN12を経由するPcd2の次に短い上流側経路Pupp1が経由する前記第１隣接ノードN11が根ノードに選択され、当該根ノードN11からのホップ数が「１」の隣接ノード（第２隣接ノード）N111，N112，N113…の集合から、既に確立済みのコンテンツ配信経路Pcd1が経由する第２隣接ノードN112を除く残りの第２隣接ノードN111，N113…ごとに、前記コンテンツ配信元ノードci(i＝1〜C)のいずれかに最短で到達できる上流側経路Pupp(Pupp6，Pupp7…)が探索される。そして、各上流側経路Pupp6，Pupp7…を前記各第２隣接ノードN111，N113…から今回の根ノードN11を中継して配信先ノードｄへ至る下流側経路Plow(Plow6，Plow7…)と連結することで、図８に示したように、各コンテンツ配信元ノードci(i＝1〜C)のいずれかとコンテンツ配信先ノードｄとを結ぶコンテンツ配信経路Pcd6，Pcd7(Pupp6+Plow6，Pupp7+Plow7…)がさらに追加して確立される。

以下同様に、第１隣接ノード集合から未探索の第１隣接ノードを上流側経路の短い順に根ノードとして順次に選択して経路探索を繰り返す処理が、コンテンツ配信経路の総数ΣPが目標数kに達するまで繰り返される。さらに、第１隣接ノードの全てについて探索が完了しても依然として経路総数ΣPが目標数kに満たなければ、図９に示したように、根ノードの選択対象を更に上流側の隣接ノード（ここでは、第２隣接ノード集合）へ切り替える。そして、上記と同様に第２隣接ノードの各々の隣接ノードを第３隣接ノードとして第３隣接ノードから上流側経路を探索し下流側経路と結合して配信経路を確定し、目標数kに達するまでこれを繰り返す。第２隣接ノード集合を全て根ノードとして配信経路を確定しても目標数kに達しなければ、さらに同様に根ノード設定対象を第３隣接ノード，第４隣接ノード，…として、順次繰り返す

以上、図２ないし図９を用いて配信経路が順次確立される、本願における基本の一実施形態を説明した。図１０Aは当該一実施形態における配信経路決定装置１の機能ブロック図である。図１０Aに示すように、配信経路決定装置１は、根ノード選択手段２、経路探索手段３及び経路確立手段４を具備する。

コンテンツ配信経路を順次確立する処理を開始するにあたって、配信経路決定装置１は、図１０Aに示すように、予めネットワークのトポロジ情報を適宜管理サーバから入手するなどして把握している。そして配信経路決定装置１の各部は、当該トポロジ情報を必要に応じて参照することで各機能を果たす。

根ノード選択手段２は、図２ないし図９で説明したように、経路探索の起点となる根ノードを順次選択する。経路探索手段３は、図２ないし図９で説明したように、根ノードの各隣接ノードから配信元ノードのいずれかに至る経路のうち最短の経路を探索して、上流側経路として定める。経路確立手段４は、図２ないし図９で説明したように、経路探索手段３により隣接ノード毎に定められた上流側経路と、当該隣接ノードと配信先ノードとを接続する下流側経路とを接続することで、コンテンツ配信経路を確立する。

次に、より詳細な一実施形態について説明する。当該実施形態における配信経路決定装置１は、その機能ブロック図を図１０Bに示すように、基本的な実施形態における図１０Aの構成と比べて、リンク距離補正手段５が追加された構成を取る。当該詳細な一実施形態においても、根ノード選択手段２、経路探索手段３及び経路確立手段４による処理は、図２ないし図９で説明した基本的な処理と合致するが、次に述べるように、より詳細な処理が行われる。

すなわち、当該詳細な一実施形態では、特に根ノード選択手段２における処理をより詳細に説明する。この処理により、配信経路決定装置１の処理の流れは、周知の幅優先探索において、配信先ノードを最初の根ノードとしてノードリストを管理し、幅優先探索の定める順に従って順次根ノードの隣接ノードを訪問してノードリストに追加して探索すると共に、配信経路を確定していく流れとなる。特に、基本実施形態では説明しなかったノードリストへのノード追加管理に関して、当該実施形態にて詳細に説明する。

またさらに、当該一実施形態においては、リンク距離補正手段５が利用される。リンク距離補正手段５は、経路探索手段３が最短経路として上流側経路を探索するに際して参照するリンク距離を補正する。そして、リンク距離補正手段５は、経路探索手段３により上流側経路が探索される直前に、既に確立した配信経路を構成するリンクのリンク距離を長くするように補正する。当該補正により、既に確立した配信経路を構成するリンクは、経路探索手段３により最短経路を構成するリンクとして探索される傾向が弱まる。その結果として、確立されるコンテンツ配信経路は、各経路同士に共通リンク部分が少ない安全性の高い経路となる傾向が強まるという効果がある。

なお、当該補正されるリンク距離は、経路探索手段３が上流側経路を求めるのに際してのみ、参照される。経路探索手段３以外の機能ブロックでは、補正を加えないリンク距離（最初にネットワークのトポロジ情報より得られるリンク距離）を参照することはあっても、補正されたリンク距離を参照することはない。

すなわち、当該一実施形態では、幅優先探索の定める順に従うノード訪問と、各訪問先における（幅優先探索以外の）付加的な処理としての経路確定及び距離補正と、によって配信経路を順次に確定する。幅優先探索の部分により下流側経路が求められる。付加的な処理の部分により上流側経路が求められ、且つ下流側経路と結合することで配信経路が確立される。

当該詳細な一実施形態における処理のフローチャートを図１１に示す。また、当該フローによりネットワーク上にコンテンツ配信経路が順次確立されていく例を図１２に示し、図１２の例を用いて図１１のフローを説明する。

図１１のステップＳ０にて処理を開始するにあたって、配信経路決定装置１はまず、ネットワークのトポロジ情報を入手しておく。当該トポロジ情報においては、図１２に示すような、配信先ノードd、コンテンツ保持ノードc1,c2, ..., ce, ...,cC及びネットワーク上の各ノードの接続関係並びに各ノード間接続のリンク距離が与えられているものとする。当該情報を参照することで、例えば配信先ノードdの隣接ノード（１ホップ先のノード）が、図１２に示すようなN1,N2, ..., Nmのm個であることがわかるものとする。また、ステップＳ０にて処理を開始するにあたって、幅優先探索におけるノードリストは空の状態である。

なお、当該ノードリストとは、配信経路決定装置１における機能ブロックではなく、幅優先探索におけるキューに相当し、当該キューに加えられるのがネットワーク上の各ノードとなるので、ノードリストと呼んでいる。すなわち、以降の説明より明らかなように、根ノード選択手段２による、順次に根ノードを選択する順番管理の処理を、周知の幅優先探索と関連づけて説明するために、ノードリストを用いる。

上記のような状態のステップS０から処理を開始し、ステップＳ１に進み、配信先ノードdをノードリストに追加する。ノードリストは{d}となる。ステップＳ２に進み、ノードリストから先頭ノードを取り出し、根ノードとする。ここで根ノード=d,ノードリスト={}(空リスト)の状態となる。

ステップＳ３に進み、根ノード（現在、配信先ノードd）の１ホップ上流に位置するノードのうち、既に確立したコンテンツ配信経路上に存在するノードを、続くステップＳ４から始まるループＬ１内での処理対象すなわち中継ノードから除く。現段階では１ホップ上流ノードはN1,N2, ..., Nmであるが、そもそもまだ配信経路が1本も確立されていないので、除かれるノードは存在しない。

（用語定義１）根ノードの１ホップ上流ノード
なお、ステップＳ３において、根ノードに対する「１ホップ上流ノード」とは、根ノードの隣接ノードのうち、当該フロー中において根ノード選択手段２によりノードリストに加えられたことがないノード、すなわち幅優先探索において未訪問のノード、である。よって、根ノードに対する１ホップ上流ノードは、隣接ノードを求めるためのトポロジ情報と、ノードリストに加えられたことがあるか確認するためのノードリスト履歴とを参照して、根ノード選択手段２により求められる。そして、当該フローの以降の説明より明らかとなるが、順次更新される根ノードを起点に、このような根ノードの１ホップ上流を辿る関係の連続により、図１２に示すような配信先ノードを根とする木構造が得られる。

なおまた、以降の説明よりも明らかとなるが、上述のノードリストに加えられたことがあるか否かという事項は、既に確立された配信経路のいずれかの下流側経路を構成するノードであるか否かと言う事項と、等価となる。よって、上述の説明を言い換えることができ、次のようになる。すなわち、根ノードの１ホップ上流ノードを求める場合には、根ノードの隣接ノードのうちから、その時点において既に確立した配信経路の下流側経路を構成するノードを除外することで、求めることができる。

（用語定義２）確立経路上での１ホップ上流ノード
また、図１１の各ステップにおいて、既に確立した配信経路上のノードにおける「１ホップ上流ノード」とは、当該ノードの当該配信経路上での隣接ノードであって且つ配信元ノードに近い側のノード、である。

ステップＳ４に進み、根ノード（現在は配信先ノードd）の１ホップ上流のノード（現在はN1,N2, ..., Nm）であり、且つ経路未確立すなわちステップＳ３で除外されず、且つ当該ループＬ１においてもまだ経路確立されていないノードがあればステップＳ５へ進み、当該ノードを、上流側経路を定めるための中継ノードとして選択する。すなわち、ステップＳ４では、根ノードの１ホップ上流ノードで且つ確立した経路上に存在しないノードが残っていれば、ステップＳ５に進んで当該ノードを選択し、以降のループＬ１内の処理によって経路を確立させるようにする。

ステップＳ６に進み、既に確立された配信経路を構成する各リンクのリンク距離が長くなるよう、リンク距離補正手段５が補正を行う。当該リンク距離の補正の詳細（アルゴリズムなど）については後述する。なお、前述のように、補正されるリンク距離は、経路探索手段３が最短経路としての上流側経路を求めるのに際してのみ、利用される。

なお、配信経路がまだ１本も確立されていない場合は、ステップＳ６はスキップされる。

なお、配信経路が確立されるのはステップＳ８であるが、追加して配信経路を確立しようとする場合、必ず上記ステップＳ６を経由することとなる。よって、配信経路がステップＳ８で確立される都度、当該直前のステップＳ８にて確立された配信経路を含む、既に確立された配信経路の全ての距離の補正が、次のステップＳ６にて実行される。（ただし、確立された配信経路が目標数であるk本目の配信経路である場合は、それ以上配信経路を求める必要がないので、当然ながら距離の補正の必要はなく、当該k本目の配信経路の距離の補正は行われない。）

ステップＳ７に進み、中継ノードから配信元ノードci(i＝１〜C)へのいずれかに至る経路のうち、最短となる経路を算出する。当該算出は、トポロジ情報と、リンク距離補正手段５により補正された値として参照されるリンク距離と、に基づいて経路探索手段３が行う。一実施形態においては、当該算出には周知のダイクストラ法が用いられる。そして、経路探索手段３は算出した最短経路を上流側経路として定める。

ステップＳ８へ進み、当該中継ノードにつき定められた上流側経路と、当該中継ノードと配信先ノードdとを結ぶ下流側経路と、を経路確立手段４が結合することによってコンテンツ配信経路が新たに１本確立される。

ステップＳ９に進んで、経路算出数が目標所定数kに達していれば、ステップＳ１１へ進みフローは終了する。フローの説明を続けるために、ここでk>(配信先ノードdの隣接ノード数m)>1とすると、現在における経路算出数の１はkに達していないので、ステップＳ９からステップＳ４に戻る。

ステップＳ４からステップＳ５、Ｓ６、Ｓ７、Ｓ８に進み、ステップＳ９で経路算出数がkに未達のためステップＳ４に戻るというループを、図示しているようにループＬ１と呼ぶこととする。ループＬ１内の各処理ステップの詳細は既に説明したので、以降は、当該実施形態において幅優先探索の定める順に根ノードを選択し、配信経路が確定していく流れを強調して説明する。そこで、以上説明してきたステップＳ０、Ｓ１、Ｓ２、Ｓ３及びループＬ１の流れの処理を経ることで、図１２において配信経路がどのように確定していくかを再度簡潔に説明して、それ以降の流れに関してもループＬ１を参照して説明することにする。

まず、ステップＳ０からステップＳ３まで至った時点で、根ノード＝d、ノードリスト＝{ }(空ノード)の状態である。そして、根ノードの１ホップ上流ノードは、図１２にノード群Ｒ100として示すN1,N2,..., Nmであり（N2は不図示）、いずれも経路確定していない、すなわち確定した配信経路上には存在していない。よって、これら経路確定していない１ホップ上流ノードが、ループＬ１内にて最短経路として上流側経路を算出するための中継ノードとして逐次用いられ、コンテンツ配信経路が逐次確定する。１ホップ上流ノードの全てに対して経路が確定すると、実線矢印で示すような１ホップ上流の中継ノードから上流側経路を算出した配信経路群が得られる。

例えば、１ホップ上流ノードN1から算出された配信経路c1−N111−N11−N1−dや、１ホップ上流ノードＮmから算出された配信経路cC−Nmb1−Nmb−Nm−dが求まる等する。ここで、例えば前者経路は、下流側経路d-N1と上流側経路c1−N111−N11−N1とを、中継ノードN1を介して接続することにより得られる。そして、これら上流側経路を算出され且つ下流側経路と接続されて確立した配信経路群の構成リンクは、その確立された後のステップＳ６において、続くステップＳ７での最短経路算出に際して参照するリンク距離が大きくなるように、その値を補正される。

なお、当該ノードN1,N2,..., Nmを対象とする場合に限らず、ループＬ１のステップＳ５において、根ノードに対する1ホップ上流ノードを選択する順は任意である。この点は後述のステップＳ１０で順序が指定されているのと異なる。

以上、根ノードdの１ホップ上流ノードの全てN1,N2,..., Nmにつき経路が確立し、且つ確立した経路数がkに達していないと、ステップＳ４からステップＳ１０に進む。ここでは、根ノードdの上流ノードN1,N2,..., Nmのうち、確立した配信経路における配信元ノードから各上流ノードへの距離、すなわち各配信経路における上流側経路部分の距離が小さい順に、根ノード選択手段２がこれら１ホップ上流ノードをノードリストの最後に追加する。

なお、前述のように当該距離の小さい順とは、リンク距離補正手段５の補正とは無関係に、最初のトポロジ情報におけるリンク距離を用いて定められる。

なおまた、ステップＳ１０では、（用語定義２）で述べたような、「既に確立した配信経路上での根ノードに対する１ホップ上流ノード」、に対しても処理を行う。よって、ステップＳ１０に至る前にループＬ１で中継ノードとして処理されたノードのみならず、当該ループＬ１に入る前のステップＳ３で除外されたノードも含めて、距離の比較を行う。

これは、次の事情に基づく。ステップＳ３で除外されたノードは既に確立された経路を構成するノードであったとしても、その１ホップ上流ノードには、経路未確立のノードが存在しうる。このような経路未確立ノードも中継ノードとして選ぶことで、下流側経路群を偏りなく分散させて木構造となるよう構築することができる。具体例については図１２を用いて以降（根ノードがN1でのステップＳ１０）に述べる。

ステップＳ１０でこのように、補正を考慮しない距離の小さい順に、１ホップ上流ノードをノードリストへ追加することにより、さらに当該フローを継続して順次配信経路を確立するに際して、当該距離すなわち確立経路における配信元ノードとの距離、の小さい順に根ノードが選択される。よって、当該根ノードを起点として確立される追加配信経路は、当該順序に従わない場合よりも距離が小さくなる可能性が高い。よって、補正距離によりできるだけ分散した配信経路を求めながらも、同時に配信経路全体の距離を抑制する傾向を高められるという効果がある。

根ノードの１ホップ上流ノードから確立済み配信経路上で配信元ノードへ至る距離（前述のように補正は考慮しない距離）が、小さい順に仮にN1,N2,..., Nmであったとする。ノードリストは空の状態から、まずリンク距離が最短のN1が最後に追加され{N1}に、次にN2が最後に追加され{N1,N2}に、以降Nmまで順次追加されて、ステップＳ１０によりノードリストは{N1,N2,..., Nm}となる。

ステップＳ２に戻り、根ノード選択手段２は、先頭のノードすなわちN1を取り出して根ノードとする。ノードリストは{N2,..., Nm}となる。根ノードN1に対して、ステップＳ３にて、１ホップ上流ノードのうち既に確立された配信経路上にあるノードを、次のループＬ１の処理対象から除外する。

図１２に示すように、N1の１ホップ上流ノードはノード群R210（N11,N12, ..., N1a）であり（N12は不図示）、このうちN11は、N1を中継ノードとして既に確立された配信経路上にあるので、N11がループL1での処理対象から除外される。

なお、根ノードがdの時点では（用語定義１）に従った結果、隣接ノードが全て１ホップ上流ノードとなった。根ノードがN1となった以降では（用語定義１）に従い、隣接ノードが全て１ホップ上流ノードとなるわけではない。すなわち、N1の隣接ノードには配信先ノードdが含まれるが、これは１ホップ上流ノードには含めず、排除する。また、N1の隣接ノードに、dの一ホップ上流ノード（のうちのN1以外）N2,…Nmが含まれることもありうるが、これらも１ホップ上流ノードに含めず、排除する。

この例からも明らかなように、ステップＳ３において、（用語定義１）に従う１ホップ上流ノード、すなわち根ノードの隣接ノードから当該時点で確立している配信経路の下流側経路を構成するノードを除外したノード、を順次求めることで、新たに構築される下流側経路が、それまで構築された下流側経路群に対して常に枝分かれして構築され、且つ枝分かれ先で再度合流することがないよう構築される。すなわち、木構造を取る下流側経路群が構築され、結果として分散した配信経路が得られるという効果がある。

ループＬ１に入り、ノードN11を除いたN1の１ホップ上流ノードN12, ..., N1aを中継ノードとして、既に確立した配信経路の構成リンクの距離補正が行われ、新たな配信経路が確立される。例えばN1aを中継ノードとする配信経路としてce−N1a1−N1a−N1−dが確立されるが、これは算出された最短経路（上流側経路）ce−N1a1−N1aと下流側経路N1a−N1−dとを、当該中継ノードN1aにて接続することにより確立される。

ループＬ１の処理を対象となる全中継ノードN12, ..., N1aに対して行っても配信経路本数がk本に達していなければ、この時点で、根ノードN1の１ホップ上流ノードで且つ経路確立されていないノードはなくなったので、ステップＳ１０に進む。

ステップＳ１０では、ステップＳ３でN11を除外したのと異なり、根ノードN1の１ホップ上流ノードの全てN11,N12, ..., N1aから各確立配信経路上で配信元ノードに至る距離（リンク距離補正なし）が比較される。小さい順にN11,N12, ..., N1aであったとすると、ステップＳ９にてノードリストは{N2,..., Nm}であった状態から{N2,..., Nm,N11,N12, ..., N1a}へと更新される。

以降同様に、配信経路がk本に達するまで根ノードをN2, ...Nmとして（ステップＳ２→Ｓ３）→（ループＬ１）→（ステップＳ１０）を繰り返すと、ノードリストは順次更新された後、図１２にＲ２００として示す、配信先ノードdから２ホップ上流のノード群のみからなる状態となる。確立経路がｋ本に達しない場合、さらに同様に継続し、２ホップ上流の各ノードを根ノードとして、配信先ノードdから３ホップ上流のノード群Ｒ３００を中継ノードとして、上流側経路を算出して配信経路が確立される。

例えば、２ホップ上流ノードN11を根ノードとし、３ホップ上流のノード群Ｒ３１０のノードを中継ノードとして、配信経路（ce−N11c−N11−N1−d等）が追加確立される。２ホップ上流ノードの根ノードＮ1aに対しては、３ホップ上流のノード群Ｒ3a0のノードを上流ノードとして、配信経路（c1−N1ad−N1a−N1−d等）が追加確立される。同様に、例えば１ホップ上流ノードNmのさらに１ホップ上流ノードを構成するノード群R2m0（Nm1, ..., Nmb）を根ノードとして、３ホップ上流ノード群Ｒ3m0のいずれかのノードNm11, ..., Nmb1を中継ノードとして、配信経路が確立される。

以上の説明より明らかなように、当該実施形態では配信先ノードdの各上流ノードを、dからのホップ数順に中継ノードとして、所定数k本に達するまで配信経路を逐次確立する。すなわち、配信先ノードdを根ノードとし、ノード群R100に示す１ホップ上流ノードを中継ノードとして、実線矢印に示すように配信経路を求める。続いて１ホップ上流ノード、すなわちノード群Ｒ１００の各々を根ノードとし、ノード群Ｒ２００内の２ホップ上流ノードを中継ノードとして、破線矢印で示されるような配信経路を求める。

同様にさらに続けて、２ホップ上流ノードの各々、すなわちノード群Ｒ２００内の各ノードを根ノードとして、ノード群Ｒ３００に示す３ホップ上流のノードを中継ノードとし、点線矢印で示される配信経路を求める。以下、k本に達するまで、さらに上流ノードを中継ノードとして同様に続ける。そして、配信先ノードdからの上流ホップ数が同一のノードの間では、配信経路確立にあたって中継ノードを探索する根ノードの順が、ステップＳ１０により定められる。また、新たに配信経路が確立される前に、ステップＳ６にて既に確立した配信経路の構成リンクのリンク距離が補正される。

以上のような、図１１、図１２にて説明した一実施形態によって、次のような効果がある。すなわち、当該実施形態では、コンテンツ配信経路が通過する複数リンクで発生するリスクが、全配信経路に及ぶリスクを引き起こす確率を、できる限り小さくするという効果がある。当該効果は、当該実施形態において、リンク１本のリスク発生が、多くの配信経路へのリスクとなることを避けるために、コンテンツを転送するためのk本の配信経路を、できるだけ同一リンク上に重ならない様に配置し、たとえ重ならざるを得ない場合でも、できる限り安全を確保することを目指して、次の（方針１）及び（方針２）に沿うように配信経路を確立していることによる効果である。

（方針１）当該全配信経路に及ぶリスクを引き起こすのに必要な、リスク発生リンク数（例えば全k個の部分コンテンツを盗聴するのに必要となるリンク数）を最大化する。すなわち、できる限り確立配信経路本数のｋ個に近づけるようにする。

（方針２）上記のような全配信経路に及ぶリスク発生リンクの、組合せパターン数（例えば全k個の部分コンテンツの盗聴を行いうるリンクの選択パターン数）を最少とする。

そして当該実施形態では次のように上記方針が満たされている。すなわち当該実施形態では、配信先ノードを根ノードとする木（配信先ノードから順次１ホップ上流ノードを辿ることで図１２に示したように木の構造が得られる）において、幅優先木探索の形で上流ノードを根ノードとして選択して行き、選択した根ノードの１ホップ上流の各ノードについて、補正されたリンク距離に基づいて、コンテンツ保持ノードとの間の最短経路計算を行う。

ここで、幅優先木探索の形で根ノードを選択し、順次枝分かれした下流側経路を構築して行くことにより、できるだけ同一リンク上への経路の重なりを避けることができ、全経路に及ぶリスクを引き起こすリスク発生リンク数を大きくできる。すなわち（方針１）が満たされる。

また、図１１ステップＳ１０の処理が存在するため、配信元ノードから同一ホップ数上流に位置するノードの間では、コンテンツ保持ノードからの距離が短いノードを優先的に根ノードとして選択することにより、算出される経路の距離が短くなって、全経路に及ぶリスクを引き起こすリスク発生リンクの組合せパターン数を小さくできる。すなわち（方針２）が満たされる。

なおここでリスクとは、単一コンテンツをk本の経路で冗長化して転送する場合にはリンク障害であり、(k, n)閾値秘密分散によるk個の部分コンテンツを転送する場合にはリンクの盗聴である。すなわちk本の配信経路の全てでリスクが発生すると、冗長化の場合ならコンテンツ配信が達成されず、(k, n)閾値秘密分散の場合なら秘密コンテンツが解読され漏洩してしまう。その他の場合であっても、上記の方針で計算され確立された経路が有利となるような任意の配信形態の各々において対応するリスクが定義でき（例えば配信途中で改竄されるリスクなど）、配信経路決定装置１を利用できる。すなわち配信経路決定装置１は、図１のような形となる各配信形態において配信経路決定サーバの役割を担い、配信先ノードdの要求等に応じて経路計算を行う。

次に、当該実施形態における図１１のステップＳ６におけるリンク距離の補正すなわち、経路探索手段３が最短経路として上流側経路を算出するにあたって参照するリンク距離のリンク距離補正手段５による補正、について説明する。当該補正ももちろん前述の（方針１）及び（方針２）に沿う形で行われる。

図１３Ａに、当該補正を説明するためのネットワーク構成例を示す。同図には配信先ノードd、配信元ノードc1〜c4及び途中のノードn1〜n50が存在し、配信経路として実線で示すP1（c1−n30−n31−d）、P2（c2−n40−n41−n1−d）、P3（c3−n50−n51−n1−d）及びP4（c4−n50−n51−n1−d）の４本が既に確立しており、これから配信経路Ｐを新たに確立しようとしている状態である。そして、当該状態において根ノードはn1で、その上流ノードであるノードn2を中継ノードとして、配信経路Ｐを確立しようとしている。すなわち、中継ノードn2から配信元ノードc1〜c4のいずれかに至る経路のうち、最短経路を上流側経路として（例えば点線c3−n2で示すように）求め、実線で示すように既に決定している下流側経路部分n2-n1-dと接続することによって、配信経路Ｐを確立しようとしている。すなわち、図１１のフローにおけるステップＳ５を終えた段階である。そして、当該ステップＳ６においてどのような補正を行えば、続くステップＳ８にて上流側経路として好ましい経路が最短経路として計算されるか、ということを検討するため、仮想的に種々の経路を検討して、その各々が上流側経路となった場合にリスクがどうなるかを考察する。そして当該リスク考察に基づく補正アルゴリズムを与える。これは後述の第２実施形態における図１３Ｂ、図１３Ｃの説明でも同様である。

リンク距離補正の方針（技術的意義）は次の通りである。経路Ｐが、既に確立された経路が全く通過していないリンクのみを通る場合は、経路Pの追加によって、全経路に及ぶリスクを引き起こすのに必要なリスク発生リンク数が増加し、（方針１）にも沿っており安全性上好ましい。しかし、経路Pが、既に確立された経路が通過するリンクを通る場合は、全経路に及ぶリスクを引き起こすリスク発生リンク数は増加せず、（方針１）に反し、前者と比べて好ましくない。

例えば図１３Ａにおいて、経路Pが、既に確立された配信経路を構成するリンクn30-n31、リンクn40-n41又はリンクn50-n51を通る場合には、これらのリンクでリスクが発生した時、全経路に及ぶリスクを引き起こすリスク発生リンク数は増加ぜず、好ましくない経路となる。従って、この様なリンクを回避するような経路Ｐを算出するために、既に確立された経路を構成するリンクの距離を、十分大きな値に補正する。さらに当該補正においては、（方針１）に反するため回避すべきリンクを経路の一部として選択せざるを得ない場合であっても、（方針２）に沿い、それら回避すべきリンクの中から、最終的に決定される全配信経路におけるリスク度合いが小さくなるようなリンクを選択するよう重み付けをして補正する。

当該十分大きな値への補正の第１実施形態として、十分大きな所定値をMとして、距離の補正対象であるリンクを通過する既に確立した配信経路数にMを掛けた値を、補正後のリンク距離とする。これによって、新たな経路を追加する際に、（方針１）に従い全経路に及ぶリスクを引き起こすリスク発生リンク数を増加させることができると共に、以下のような考察よりわかるように、（方針２）に従い各リンクのリスクに応じた値に補正することができるという効果がある。

そして、当該第１実施形態の上記アルゴリズムを確立済みの全配信経路に適用すると、結果として補正によりリンク距離が変化するのは、上記「通過する既に確立した配信経路数」に変化があるもののみである。すなわち、補正によりリンク距離が変わるのは、当該補正を行う図１１ステップＳ６の直前のステップＳ８にて確立された配信経路のみとなる。しかし形式上は、当該第１実施形態のアルゴリズムの適用対象は、既に確立された全ての配信経路としてよく、本発明における補正とは、距離が変わらない場合も含むものとする。

第１実施形態の効果は次のような考察より明らかである。例えば図１３Ａにおいて、経路Pが、既に確定した配信経路を構成するリンクn30-n31、リンクn40-n41又はリンクn50-n51を通る場合には、これらのリンクでリスクが発生した時、全経路に及ぶリスクを引き起こすリスク発生リンク数は変わらない。この観点では当該３つのリンクのいずれを通ったとしてもリスクは変わらない。

しかし更にこれら３つのリンクを比較すると、リンクn30-n31やリンクn40-n41を通る場合（通過する既に確立した配信経路はP1やＰ２の各１本のみ）に比べて、リンクn50-n51を通る（通過する既に確立した配信経路はP3およびP4の２本）ことによって、同一リンクを通過する経路数が大きくなり、当該リンクにおけるリスクの発生によって、全経路にリスクが及ぶ確率が大きくなる。すなわち確立した経路が１本通るリンクn30-n31やリンクn40-n41よりも、確立した経路が２本通るリンクn50-n51の方が選んだ場合のリスクが大きい。

よって第１実施形態では、全経路に及ぶリスクを引き起こすリスク発生リンク数を最大限確保すると共に更に全経路にリスクが及ぶ確率をも抑えるため（すなわち前述の例でn50-n51を選ばないようにするため）に、リンクの距離を前述のように補正する。すなわちリンク距離を、当該リンクを通過する既に確定した配信経路の数に比例した値に補正する。

ここでリンク距離の補正の効果につき、具体的な例として図１４を用いて説明する。同図（Ａ）は、不図示のある根ノードの１ホップ上流ノードである、中継ノードn10、n20及びn30から、各配信元ノードc10、c20及びc30のいずれかへ至る最短経路を、これから決定する状態を示している。途中にはノードa、b及びcが存在して、各ノード間のリンク距離は、リンクを示す線の下部に括弧で示している通りとする。全く補正が行われないならば、明らかなように、同図Ｂに実線で示すような最短経路が３本決定されてしまう。この場合、リンクa−c20間のいずれか１本のみのリンクにおけるリスク発生により、全経路にリスクが及んでしまう。

そこで、リンク距離補正の第１実施形態を適用し、既に確立した経路の数の所定倍の例として、１０倍に補正する場合の経過が同図Ａ１〜Ａ３である。まず、n10からの最短経路が、同図（Ａ）のリンク距離に基づいてn10−a−b−c−c20(距離9)と求まり、これによりリンク距離が補正されて、同図（Ａ１）に示す60[n10−a]、10[a−b]、10[b−c]及び10[c−c20]となる。

同図（Ａ１）に示す補正されたリンク距離に基づき、次に、n20からの最短経路が計算されて、n20−a−b−c30(距離21)と求まる。これによりリンク距離がさらに補正されて、同図（Ａ２）に示す60[n20−a]、20[a−b]及び50[b−c30]となる。リンクa-bは、n10経由及びn20経由の２本の経路が通過するので、初期リンク距離1×通過本数２×所定倍10によりリンク距離20に補正される。

さらに同図（Ａ２）に示す補正されたリンク距離に基づき、最後にn30からの最短経路が計算され、n30−b−c−c10(距離26)と求まり、リンク距離が同様にさらに補正されて、80[n30−b]、20[b−c]及び80[c−c10]となって、同図（Ａ３）の状態となる。（Ａ３）の配信経路は、（Ｂ）の配信経路と比べて、明らかに散らばった配信経路となっている。、そして、全経路におよぶリスクを与えるリンクとして、例えばa−b且つb−cの２本などが必要となっており、補正を行わない結果の（Ｂ）に示す配信経路では当該２本のうち片方のみでも全経路のリスクとなるのに比べ、安全性が高まっている。

図１４ではリンク距離補正の第１実施形態で説明したが、リンク距離を大きく補正する他の実施形態でも同様の傾向の効果となることは明らかである。

ここで図１３Ａに戻り、リンク距離を十分大きな値に補正する別実施形態である、第２実施形態についてさらに説明する。当該第２実施形態の方針は次の通りである。すなわち、（方針２）に従い、全経路に及ぶリスクを引き起こすリスク発生リンクの組合せパターン数を抑えるために、当該組み合わせパターン数に基づいてリンクの距離を補正する。

そして具体的な方式として、リンク距離の比が、順次確立される経路がそれらのリンクを通過することによって、当該リンクを追加したにもかからわらず、全経路に及ぶリスクを引き起こすリスク発生リンク数の最小数が（増加することなく）変わらない場合、すなわち（方針１）にそぐわない形でリスク発生リンクが現れた場合における、リスク発生リンクの組合せパターン数の比に等しくなるように、リンク距離を補正する。

なお、ここで「リンク距離の比」とは正確には「リンク距離を補正するために、各リンクの初期リンク距離に対して積算する値（補正係数と呼ぶこととする）同士の比」である。しかし当該第２実施形態においては説明の簡略化のため、特に具体例による説明においては、前者の用語で後者を表すものとする。「補正距離の比」などに関しても同様とする。

当該補正に用いる当該リスク発生リンクの組み合わせパターン数の求め方及び当該パターン数に基づいて各リンクのリンク距離がどう補正されるかは以降述べる第１および第２の例を通じて説明する。

また当該方針において、全経路に及ぶリスクを引き起こすリスク発生リンクの組み合わせパターン数の増加とは、以下に説明する具体例のように、配信経路を確立しようとしている経路の既に確立している部分、すなわち下流側経路の部分、を除いて算出するものとする。これを「パターン数算出方針」と呼ぶこととする。すなわち新たに確立しようとする配信経路の安全性への寄与は、その新規確立される経路が、他の既確立経路から枝分かれすることによって新たに生じる部分、すなわち上流側経路部分の寄与として考慮する。よって、上流側経路を求めようとしている状態において、既に決定している下流側経路部分を除いて組み合わせパターン数を求めるものとする。

なおまた、当該第２実施形態においては、リンク距離補正の技術的意義の説明のために、上流側経路が未確立の状態（前述のステップＳ５を終えた時点の状態）において、種々の経路を仮に確立した場合のリスクを検討する。 図１３Ａと同様の構成で、経路Pを確立しようとしている状態であって、且つ仮に配信経路Pの上流側経路部分が、リンクn30-n31又はリンクn40-n41を通る、２本の経路Pa又はPbのいずれかに決まる場合を図１３Ｂに示し、これをまず第１の例として第２実施形態における補正を説明する。同図に示すように、経路候補Paはc3−n30−n31−n2であり、途中のリンクn30−n31が既に確立した経路P1上にある。また経路候補Pbはc3−n40−n41−n2であり、途中のリンクn40−n41が既に確立した経路P2上にある。Pa、Pb共に残りの点線で示す部分は確立した配信経路と共通リンクを持たないものとする。

経路候補Paを配信経路として確立した場合は、経路P2のノードC2からn1までの部分を構成するリンクの中のいずれか１本のリンクと、１本のリンクn30-n31と、でリスクが発生する時に、経路P1、P2、Pに及ぶリスクを引き起こすリスク発生リンク数は経路Ｐを追加したにもかかわらず２本から３本に増えず２本のまま不変になる。なおここで、前述の「パターン数算出方針」に従い、経路P2のうち経路Pの確立部分と重なるn1−dの部分を除外して、リスク発生リンク数を検討している。そしてこの場合、経路P1、P2、Pに及ぶリスクを引き起こす２本のリスク発生リンクの組合せパターンは、経路P2のノードc2からn1までの部分（c2−n40−n41−n1）を構成するリンク数である。当該リンク数が、リンクn30−n31を用いて配信経路Pを確定した場合、すなわちPaを選んだ場合のリスクに相当する。

一方、経路候補Pbを配信経路として確定した場合は、経路P1のノードc1からdまでの部分を構成するリンクの中のいずれか１本のリンクと、１本のリンクn40-n41と、でリスクが発生する時に、経路P1、P2、Pに及ぶリスクを引き起こすリスク発生リンク数は、経路Ｐを追加したにもかかわらず２本から３本に増えず２本のまま不変になる。そしてこの場合、経路P1、P2、Pに及ぶリスクを引き起こす２本のリスク発生リンクの組合せパターンは、経路P1のノードC1からdまでの部分（c1−n30−n31−d）を構成するリンク数である。当該部分にはPの下流側経路を構成する部分は含まれないので、前述の「パターン数算出方針」に従い、当該部分をそのままリスク発生リンク数の検討に用いる。当該リンク数がリンクn40-n41を選んで配信経路Pを確定した場合、すなわちPbを選んだ場合のリスクに相当する。

ここで当該第２実施形態におけるリンク距離補正の方式を適用して補正係数を求める。リンクn30-n31とリンクn40-n41の補正係数の比をa1：a2とすると、
a1：ａ2＝（c2−n40−n41−n1の距離）：（c1−n30−n31−dの距離）
＝（リンクn40-n41を通過する確立経路すなわちP2の内、経路Pの確立部分である下流側経路部分d−n1−n2とリンクを共有しない部分の距離）：（リンクn30-n31を通過する確立経路すなわちP1の距離）
となる。

これを、後述する各リンクのリンク距離の一般的な補正方法に適合する形に言い換える。すなわち、上記ではリンクn30-n31の補正係数（の比ａ１）がリンクn40-n41に関連する部分で与えられ、リンクn40−n41の補正係数（の比ａ２）がリンクn30−n31に関連する部分で与えられているので、逆数をとることで、各リンク自身に関連する部分で補正係数比を与えるようにする。

そして当該第２実施形態におけるリンクn30-n31とリンクn40-n41の補正係数の比a1：a2は、
a1：a2=（リンクn30-n31を通過する確立経路すなわち経路P1の距離の逆数）：（リンクn40-n41を通過する確立経路すなわち経路P2の内、経路Pの下流側経路部分とリンクを共有しない部分の距離の逆数） …（式１）
となる。

当該第１の例は特に、前述の「パターン数算出方針」により、上流側経路を求めて当該確立しようとしている経路Ｐの既確定部分である下流側経路を除外して比を求めることを示すための例である。すなわち、上記（式１）では、比ａ１の経路Ｐ１には経路Ｐの下流側経路部分と共通する部分がないので経路Ｐ１全体を考慮し、比ａ２の経路Ｐ２には経路Ｐの下流側経路部分と共通する部分があるので当該部分を除外して考慮する。

同様に、当該第２の実施形態におけるリンク距離の補正を、第２の例を用いてさらに説明する。図１３Ｃに第２の例を示す。当該第２の例は、前述の第１の例で各距離補正対象のリンクを通過する確立経路が１本のみの場合であったのに対し、２本以上ある場合を説明するための例である。図１３Ｃは、図１３Ａと同様の構成で経路Pを確立しようとしている状態であって、且つ仮に配信経路Pの上流側部分が、リンクn30-n31又はリンクn50-n51を通る、２本の経路候補Pa又はPcのいずれかに決まる場合を示している。

経路候補Paを選んで配信経路を確立した場合は、ノードc3又はc4からノードn1までの部分で、経路P3とP4が重なっているリンクと、リンクn30-n31と、でリスクが発生する時に、経路P1、P3、P4、Pに及ぶリスクを引き起こすリスク発生リンク数は、経路Ｐを追加したにもかかわらず、２本から３本に増えず２本のまま不変になる。そしてこの場合、経路P1、P3、P4、Pに及ぶリスクを引き起こす、２本のリスク発生リンクの組合せパターンは、ノードn1までの部分で、経路P3とP4が重なっている部分のリンク数であり、当該Paを選んだ場合のリスクに相当する。経路Ｐ３とＰ４との重なりはn1−d間にも存在するが、前述のとおり「パターン数算出方針」によって、除外して考える。

一方、経路候補Pcを配信経路として確立した場合は、経路P1のノードC1からdまでの部分を構成するリンクの中の１つのリンクと、リンクn50-n51と、でリスクが発生する時に、経路P1、P3、P4、Pに及ぶリスクを引き起こすリスク発生リンク数が、経路Ｐを追加したにもかかわらず、２本から３本に増えず２本のまま不変になる。そしてこの場合、経路P1、P3、P4、Pに及ぶリスクを引き起こす２本のリスク発生リンクの組合せパターンは、経路P1のノードC1からdまでの部分を構成するリンク数であり、当該Ｐcを選んだ場合のリスクに相当する。

ここで、当該第２実施形態におけるリンク距離補正の方式を適用し、補正係数を求める。リンクn30-n31とリンクn50-n51の補正係数の比をａ１：ａ３とする。
ａ１：ａ３＝（n50-n51の距離）：（c1−n30−n31−dの距離）
＝（リンクn50-n51を通過する全ての確立経路P3とP4が通過し、かつ経路Pの確定部分すなわち下流側経路部分n2−dが通過しない部分の距離）：（リンクn30-n31を通過する確立経路P1の距離）

前述の第１の例と同様に、逆数に変換して、各リンクn30-n31及びn50-n51自身に関連する部分で、補正係数の比を与えるようにする。すなわち、
a1：ａ３＝（リンクn30-n31を通過する確立経路P1の距離の逆数）：（リンクn50-n51を通過する全ての確立経路P3とP4が通過し、かつ経路Pの確定部分すなわち下流側経路部分n2−dが通過しない部分の距離の逆数） …（式２）
となる。

以上のような、図１３Ｂ及び図１３Ｃにおける第１及び第２の例の説明から、当該第２実施形態において、一般的に各リンクのリンク距離を補正する場合の計算手法も明らかであり、次の通りである。すなわち、まず、距離の補正対象であるリンクを通過する、既に確立された全ての配信経路群を共通に構成するリンクの集合を第１リンク集合とする。また当該補正を行う図１１のステップＳ６の直前のステップＳ５にて中継ノードを選択することで定まる下流側経路部分に含まれるリンク集合を、第２リンク集合とする。すなわち、第２リンク集合とは、次に新たに確立される配信経路の下流側経路を構成するリンク集合である。

そして第１リンク集合から第２リンク集合を引いた差集合を第３リンク集合とする。当該第２実施形態では、第３リンク集合に含まれるリンクの本数の逆数に十分大きな所定値Mを掛けた値を、最初に与えられるリンク距離に積算することによって補正後のリンク距離とする。そして、補正対象は既に確立された全配信経路である。

上記計算手法は図１３Ｂ、図１３Ｃの例で求めた（式１）、（式２）を再現し、一般的な補正算出手法であることは明らかであるが、第１ないし第３リンク集合を具体例で確認するために、（式１）（式２）と同様のa1、a2、a3が上記手法で求まることを以下に説明する。

[a1]
距離の補正対象リンクはn30-n31である。当該リンクを通過する既に確立された配信経路群は構成要素の配信経路が１本の経路Ｐ１のみからなる｛Ｐ１｝であるので、その共通部分は配信経路群自身と一致し｛Ｐ１｝である。よって第１リンク集合はＰ１に含まれるリンク集合である。第２リンク集合は{n2−n1、n1−d}である。これらには共通部分がないので、第１リンク集合から第２リンク集合を引いたものは、第１リンク集合自身であり、これが第３リンク集合として定まる。よって第３リンク集合はＰ１に含まれるリンク集合であり、
ａ１＝（リンクn30-n31を通過する確立経路すなわち経路P1の距離の逆数）となり、（式１）（式２）に一致する。

[a2]
距離の補正対象リンクはn40-n41である。当該リンクを通過する既に確立された配信経路群は構成要素の配信経路が１本の経路Ｐ２のみからなる｛Ｐ２｝である。その共通部分は自身と一致し｛Ｐ２｝である。よって第１リンク集合はＰ２に含まれるリンク集合である。第２リンク集合は{n2−n1、n1−d}である。差集合をとると、共通部分の{n1−d}が引かれて第３リンク集合はＰ２のうち（c2−n40−n41−n1）の部分となる。よって、
ａ２＝（リンクn40-n41を通過する確立経路すなわち経路P2の内、経路Pの下流側経路部分とリンクを共有しない部分の距離の逆数）となり、（式１）に一致する。

[a3]
距離の補正対象リンクはn50−n51である。当該リンクを通過する既に確立された配信経路群は｛Ｐ３、Ｐ４｝である。よって第１リンク集合は
｛Ｐ３∩Ｐ４｝＝｛n50−n51，n1−d｝となる。第２リンク集合は{n2−n1、n1−d}である。差集合をとると、共通部分の{n1−d}が引かれて第３リンク集合は{n50−n51}となる。よって、
a3＝（リンクn50-n51を通過する全ての確立経路P3とP4が通過し、かつ経路Pの確定部分すなわち下流側経路部分n2−dが通過しない部分の距離の逆数）となり、（式２）に一致する。

当該第２実施形態では、このようにリンク距離を補正することによって、（方針１）に従い、新たな経路を追加したにも拘らず、全経路に及ぶリスクを引き起こすリスク発生リンク数が変わらない場合を極力避けて、更にリスク発生リンク数が変わらない場合は、（方針２）に従い、その様なリスク発生リンクの組合せパターン数の増加を抑えることができるという効果がある。

なお、第１実施形態と第２実施形態との補正の形式的な意義を図１１のフローに即して再度説明する。ループＬ1におけるi回目(i=1〜k)の各ステップＳｎ(ｎ＝４〜９)をSn[i]と表記する。ステップS8[i]まで至り配信経路がi本目まで確立された後の、ステップＳ６[i+1]の補正を考える。

第１実施形態では、ステップＳ６[i+1]の補正によって、補正対象である既に確立された配信経路全体のうち、特に当該i本目に確立された配信経路の距離が変化する。

第２実施形態では、ステップＳ６[i+1]の補正において、当該i本目に確立された配信経路までの、既に確立されたi本の配信経路に基づく第１リンク集合と、次にステップS8[i+1]にて確立する配信経路の下流側経路部分を構成する第２リンク集合と、を用いることにより、既に確立された配信経路全体の距離補正を行う。

すなわち、第２実施形態において、第１リンク集合はステップＳ８[j](j=1〜i)にて既に確立された配信経路全体に基づく集合であり、第２リンク集合はステップＳ５[i+1]の中継ノード選択により定まる、後のステップＳ８[i+1]で確立される配信経路を構成することとなる下流側経路を構成するリンク集合である。

なおまた、本発明全体において、下流側経路を構築するに際して１ホップ先の隣接ノードを順次辿るとした。当該ホップ数と、上流側経路を最短経路として算出するに際して参照されるリンク距離（特に、補正を加える前の、最初にネットワークのトポロジ情報より得られるリンク距離）との関係は次の通りである。すなわち、リンク距離の一実施形態として、ホップ数がある。リンク距離はホップ数以外によっても定義できる。そして、本発明全体において、下流側経路を構築する際の隣接ノードは、ホップ数以外のリンク距離における単位距離先にあるノード、としてもよい。

以上説明した様に、本発明では、（方針１）に従い、全経路に及ぶリスクを引き起こすリスク発生リンク数が大きくするようにし、（方針２）に従いその様なリスク発生リンクの組合せパターン数が小さくなるように、算出経路の順番を決定し、かつリンク距離を補正して、逐次的に最短経路計算を繰り返すのみである。そして、当該処理を実行するための計算において最も負荷の大きい部分である最短経路計算には、ダイクストラ法などを利用する。よって、厳密解は求まるものの計算が膨大となる従来技術の整数計画法と比べ、十分に少ない計算資源を使って、準最適解としてコンテンツ配信経路を計算できる。

本発明は、複数のノードで秘密分散保持されているn個の部分コンテンツの中の任意のk個の部分コンテンツを、ネットワークを介して配信先ノードまで転送するためのk本の経路の計算に適用できる。本発明によって、転送途中の部分コンテンツがリンク上で盗聴される可能性がある場合に、k個の部分コンテンツの全てを盗聴するために必要な盗聴リンク数を最大化し、その様な盗聴リンクの組合せパターン数が最少となるような安全な部分コンテンツ配信経路の算出が可能となる。

また本発明は、複数のノードで重複保持されているk個の同一コンテンツを、ネットワークを介して配信先ノードまで転送するためのk本の経路の計算に適用できる。本発明によって、多重リンク障害が発生し得る場合に、k本の経路の全てが障害となって配信先ノードまでコンテンツが転送されなくなる障害リンク数を最大化し、その様な障害リンクの組合せパターン数が最少となるような高信頼なコンテンツ配信経路の算出が可能となる。

１…配信経路決定装置、２…根ノード選択手段、３…経路探索手段、４…経路確立手段、５…リンク距離補正手段

Claims (10)

1. ネットワーク上で複数の配信元ノードから配信先ノードへコンテンツを分散配信する複数のコンテンツ配信経路を決定する経路決定装置において、
   経路探索の起点となる根ノードを重複なく順次に選択する根ノード選択手段と、
   前記選択された根ノードの隣接ノードごとに、当該隣接ノードからいずれかの前記配信元ノードへ到達する最短経路として上流側経路を探索する経路探索手段と、
   前記隣接ノードごとに探索された上流側経路と、当該隣接ノードと前記配信先ノードとを結ぶ下流側経路と、を接続して前記コンテンツ配信経路を確立する経路確立手段とを具備し、
   前記根ノード選択手段は、
   前記配信先ノードを最初の根ノードに選択する第１ステップと、
   前記第１ステップの後、前記配信先ノードを根ノードとして上流側経路を探索された隣接ノードの集合から根ノードを順次に選択する第２ステップと、
   前記第２ステップの後、前記コンテンツ配信経路の確立本数が目標数に達するまで、上流側経路を探索された隣接ノードの集合から前記根ノードを順次に選択することを繰り返す第３ステップとを実行することを特徴とする配信経路決定装置。
2. 前記根ノード選択手段は、選択した根ノードの全隣接ノードに対して前記コンテンツ配信経路が確立されてから次の根ノードを選択し、前記第３ステップにおいて根ノードを前記配信先ノードからのホップ数の小さい順に選択することを特徴とする請求項１に記載の配信経路決定装置。
3. 前記経路探索手段は、前記選択された根ノードの隣接ノードであり且つ当該根ノードの選択以前に前記下流側経路のうちいずれかを構成するノードにはなっていないノードごとに、当該隣接ノードからいずれかの前記配信元ノードへ到達する最短経路として上流側経路を探索することを特徴とする請求項１または２に記載の配信経路決定装置。
4. 前記経路探索手段は、前記選択された根ノードの隣接ノードであり且つ前記経路確立手段にて既に確立された前記コンテンツ配信経路上には存在しないノードごとに、当該隣接ノードからいずれかの前記配信元ノードへ到達する最短経路として上流側経路を探索することを特徴とする請求項１または３に記載の配信経路決定装置。
5. 前記根ノード選択手段は前記第２ステップおよび前記第３ステップにおいて、上流側経路を前記探索された隣接ノードの集合から当該上流側経路の距離が短い順に根ノードを順次に選択することを特徴とする請求項１ないし４のいずれかに記載の配信経路決定装置。
6. 前記経路確立手段により前記コンテンツ配信経路が確立される都度、既に確立されたコンテンツ配信経路群を構成する各リンクのリンク距離であって且つ前記経路探索手段が前記上流側経路を最短経路として探索するのに参照するリンク距離を補正するリンク距離補正手段をさらに具備することを特徴とする請求項１ないし５のいずれかに記載の配信経路決定装置。
7. 前記リンク距離補正手段が、前記各リンクのリンク距離を、当該リンクを通過する前記経路確立手段にて既に確立された前記コンテンツ配信経路の本数に比例した値に補正することを特徴とする請求項６に記載の配信経路決定装置。
8. 前記リンク距離補正手段は前記コンテンツ配信経路が確立される都度、前記各リンクのリンク距離を、当該リンクを通過する前記経路確立手段にて既に確立された全ての前記コンテンツ配信経路を共通に構成するリンクの集合である第１リンク集合から、当該確立されたコンテンツ配信経路の次に確立するコンテンツ配信経路の前記下流側経路を構成するリンクの集合である第２リンク集合を引いた差集合である第３リンク集合を構成するリンクの本数に反比例した値に補正することを特徴とする請求項６に記載の配信経路決定装置。
9. 前記経路探索手段が前記上流側経路をダイクストラ法により探索することを特徴とする請求項１ないし８のいずれかに記載の配信経路決定装置。
10. ネットワーク上で複数の配信元ノードから配信先ノードへコンテンツを分散配信する複数のコンテンツ配信経路を決定する経路決定方法において、
    経路探索の起点となる根ノードを重複なく順次に選択する根ノード選択ステップと、
    前記選択された根ノードの隣接ノードごとに、当該隣接ノードからいずれかの前記配信元ノードへ到達する最短経路として上流側経路を探索する経路探索ステップと、
    前記隣接ノードごとに探索された上流側経路と、当該隣接ノードと前記配信先ノードとを結ぶ下流側経路と、を接続して前記コンテンツ配信経路を確立する経路確立ステップとを具備し、
    前記根ノード選択ステップは、
    前記配信先ノードを最初の根ノードに選択する第１ステップと、
    前記第１ステップの後、前記配信先ノードを根ノードとして上流側経路を探索された隣接ノードの集合から根ノードを順次に選択する第２ステップと、
    前記第２ステップの後、前記コンテンツ配信経路の確立本数が目標数に達するまで、上流側経路を探索された隣接ノードの集合から前記根ノードを順次に選択することを繰り返す第３ステップとを含むことを特徴とする配信経路決定方法。

Images