(57)【特許請求の範囲】
【請求項１】
コンテンツデータを保持する情報源ノードと、
前記コンテンツデータを分散させた分散データを保持する複数のストレージノードと、
任意の前記ストレージノードから出力された分散データを受信して前記コンテンツデータを復元する復元ノードと、
で構成される分散ストレージ系を有する分散ストレージシステムを制御する分散ストレージ制御方法であって、
前記情報源ノードで前記コンテンツデータを符号化する分散ストレージ系アルファベットを、前記分散ストレージ系アルファベットより小さな符号化アルファベットに変換する変換手順と、
前記復元ノードで前記符号化アルファベットを前記分散ストレージ系アルファベットに戻す逆変換手順と、
前記ストレージノードの故障時に他の少なくとも１の前記ストレージノードからデータを受信して故障した前記ストレージノードの代替となる再生成用ストレージノードを形成し、前記分散ストレージ系を更新する再生成手順と、
前記ストレージノードの故障の回数をカウントし、前記回数が上限値に達した時、構成された前記分散ストレージ系をすべてリフレッシュして始めから前記コンテンツデータを分散させることで改めて分散ストレージ系を構成するリセット手順と、
を行うことを特徴とする分散ストレージ制御方法。
【請求項２】
前記ストレージノードにおいて、
ネットワーク符号化された少なくとも１つの入力データが入力され、ネットワーク符号構成アルゴリズムとしてランダムネットワーク符号化アルゴリズムを適用し、前記入力データに含まれる前記分散データと前記変換手順で変換された前記符号化アルファベットで構成された符号化行列を掛け合わせて後段のノードへ出力する出力データを計算する
ことを特徴とする請求項１に記載の分散ストレージ制御方法。
【請求項３】
コンテンツデータを保持する情報源ノードと、
前記コンテンツデータを分散させた分散データを保持する複数のストレージノードと、
任意の前記ストレージノードから出力された分散データを受信して前記コンテンツデータを復元する復元ノードと、
で構成される分散ストレージ系を有する分散ストレージシステムであって、
前記情報源ノードが、前記コンテンツデータを符号化する分散ストレージ系アルファベットを、前記分散ストレージ系アルファベットより小さな符号化アルファベットに変換する変換機能を有し、
前記復元ノードが、前記符号化アルファベットを前記分散ストレージ系アルファベットに戻す逆変換機能を有しており、
前記ストレージノードの故障時に他の少なくとも１の前記ストレージノードからデータを受信して故障した前記ストレージノードの代替となる再生成用ストレージノードを形成し、前記分散ストレージ系を更新する再生成機能と、
前記ストレージノードの故障の回数をカウントし、前記回数が上限値に達した時、構成された前記分散ストレージ系をすべてリフレッシュして始めから前記コンテンツデータを分散させることで改めて分散ストレージ系を構成するリセット機能と、
を有する制御部を備えることを特徴とする分散ストレージシステム。
【請求項４】
前記ストレージノードは、
ネットワーク符号化された少なくとも１つの入力データが入力され、ネットワーク符号構成アルゴリズムとしてランダムネットワーク符号化アルゴリズムを適用し、前記入力データに含まれる前記分散データと前記情報源ノードが変換した前記符号化アルファベットで構成された符号化行列を掛け合わせて後段のノードへ出力する出力データを計算する
ことを特徴とする請求項３に記載の分散ストレージシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散ストレージにおけるデータ保存量とノード再生成データ転送量との任意のトレードオフを達成する符号化技術に関する。
【背景技術】
【０００２】
１．分散ストレージ技術の概要
（ｎ、ｋ）分散ストレージ系を図１に示す。図１はｎ＝４、ｋ＝３の場合である。情報源をｓとし、ｓは保存・復元されるコンテンツを持つ。保存・復元されるコンテンツをｘＢと書く。肩にかかるＢはコンテンツ長がＢバイトであることを示すものとする。すなわちｘＢ＝｛ｘ１，ｘ２、・・・，ｘＢ｝に対してｘｉ∈｛０，１，・・・，ｑ−１｝とする。ここで集合｛０，１，・・・，ｑ−１｝を「分散ストレージ系のアルファベット」と呼ぶ。また、分散ストレージ系のアルファベットを有限体Ｆｑにとる。ここでｑ＝２ｍであり、１バイト＝ｍビットとしておく（要するにｘＢ∈ＦｑＢである。）。例えば対象とする系で送受信されるパケット長を１バイトとおくことが考えられる。コンテンツはｎ個のストレージに分散して保存される。また、データを復元する者を「Ｄａｔａ  Ｃｏｌｌｅｃｔｏｒ」以下、「ＤＣ」と略記する。）と呼ぶことにする。ＤＣは任意のｋ個のストレージにアクセスして、各ストレージからαバイトずつデータを受け取る。ＤＣは受け取ったデータを復号することで元のコンテンツｘＢを復元する。
【０００３】
ところで、分散ストレージの各ノードは故障のリスクが常につきまとう。図２はノード１が故障し、同じサイトにおいてノード５を新たに構成した状況を表している。本明細書では「サイト」という言葉を特定のストレージが存在する場所を指すものとする。このとき、ノード５は故障する前のノード１と同じ機能をもつことが要請される。すなわち、図２においてノードの再生成後、ＤＣは再び任意のｋ個のストレージにアクセスして、各ストレージからαバイトずつデータを受け取ることで元のコンテンツｘＢを復元することができることになる。ノードが故障した際に、同じサイトに同一機能を持つ新たなノードを構成することを「再生成」と呼ぶ。再生成は新たなノード（図２の符号５’）が故障していないｄ個のノードからβバイトずつ再生成用データを受け取ることでなされる。
【０００４】
図２においてノード５およびノード５’の２種類が存在するのは、後で再生成符号としてのネットワーク符号（非特許文献４を参照）を構成するための便宜的なもので、物理的な存在としては同一である。ノード５’は再生成用のデータを受け取るノード、ノード５は復元用のデータをＤＣに送信するノードを表している。なお、図２の横軸は時間を表しており、図は各時点でどのノードが故障し、どのノードから再生成用データが転送され、ＤＣはどのノードから復号用データを取得したか、等を示すもので、一般に「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」と呼ばれている。
【０００５】
上記で説明した再生成のための分散データを構成するための符号（ｎ、ｋ、ｄ、α、β）を「再生成符号」と呼ぶ。再生成符号は分散符号の１つである。再生成符号はＤｉｍａｋｉｓ達によって提案（非特許文献３）され、その基本的な性質が明らかにされている。再生成の特徴はデータ保存量αと再生成用データ転送量βとの間にトレードオフがあるというもので次の命題として記される。
［命題１］
分散ストレージ系のパラメータ（ｎ，ｋ，ｄ，α，β）が与えられているとする。ＤＣが任意のｋ個の分散ストレージにアクセスすることで大きさＢバイトのコンテンツを正しく復元することができ、さらに故障ノードが任意のｄ個の分散ストレージにアクセスすることで正しく再生成されるための必要十分条件は、
【数１】
0006445955.tif 000002
として与えられる（非特許文献３を参照。）。
【０００６】
（１）式が表す曲線（トレードオフ曲線）の例を図３（非特許文献３）に示す。図３の曲線の上側が理論的に実現可能な領域を表す。課題は、トレードオフ曲線上の任意の点に近接する点を実現するような再生成符号を構成することである。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｖ．  Ｊａｃｏｂｓｏｎ，  Ｄ．  Ｋ．  Ｓｍｅｔｔｅｒｓ，  Ｊ．  Ｄ．  Ｔｈｏｒｎｔｏｎ，  Ｍ．  Ｆ．  Ｐｌａｓｓ，  Ｎ．  Ｈ．  Ｂｒｉｇｇｓ，  ａｎｄ  Ｒ．  Ｌ．  Ｂｒａｙｎａｒｄ，  “Ｎｅｔｗｏｒｋｉｎｇ  ｎａｍｅｄ  ｃｏｎｔｅｎｔ”，  ｉｎ  Ｐｒｏｃ．  ５ｔｈ  ＡＣＭ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｅｍｅｒｇｉｎｇ  Ｎｅｔｗｏｒｋｉｎｇ  Ｅｘｐｅｒｉｍｅｎｔｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｉｅｓ，  ｐｐ．１−１２，  ２００９．
【非特許文献２】桑門秀典，  栗原正純，  「分散ストレージシステムのための新しい符号化法  −再生成符号とＰｙｒａｍｉｄ符号−」，  信学会誌，  ｖｏｌ．９８，  ｎｏ．２，  ｐｐ．１３０−１３７，２０１５．
【非特許文献３】Ａ．  Ｇ．  Ｄｉｍａｋｉｓ，  Ｐ．  Ｂ．  Ｇｏｄｆｒｅｙ，  Ｙ．  Ｗｕ，  Ｍ．  Ｊ．  Ｗａｉｎｗｒｉｇｈｔ，  ａｎｄ  Ｋ．  Ｒａｍｃｈａｎｄｒａｎ，  “Ｎｅｔｗｏｒｋ  ｃｏｄｉｎｇ  ｆｏｒ  ｄｉｓｔｒｉｂｕｔｅｄ  ｓｔｏｒａｇｅ  ｓｙｓｔｅｍｓ”，  ＩＥＥＥ  Ｔｒａｎｓ．  Ｉｎｆ．  Ｔｈｅｏｒｙ，  ｖｏｌ．５６，  ｎｏ．９，  ｐｐ．４５３９−４５５１，  Ｓｅｐｔ．  ２０１０．
【非特許文献４】Ｔ．Ｈｏ，  Ｍ．Ｍｅｄａｒｄ，  Ｒ．Ｋｏｅｔｔｅｒ，  Ｄ．Ｒ．Ｋａｒｇｅｒ，  Ｍ．Ｅｆｆｒｏｓ，  Ｊ．Ｓｈｉ，  ａｎｄ  Ｂ．Ｌｅｏｎｇ，  “Ａ  ｒａｎｄｏｍ  ｌｉｎｅａｒ  ｎｅｔｗｏｒｋ  ｃｏｄｉｎｇ  ａｐｐｒｏａｃｈ  ｔｏ  ｍｕｌｔｉｃａｓｔ”，  ＩＥＥＥ  Ｔｒａｎｓ．  Ｉｎｆ．  Ｔｈｅｏｒｙ，  ｖｏｌ．５２，  ｎｏ．１０，  ｐｐ．４４１３−４４３０，  Ｏｃｔ．  ２００６．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
２．従来の技術での困難点
図２で示したように  「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」は一般に有向非周期なグラフとなるため、再生成符号の実現にはネットワーク符号を適用することが適切であるように思われる。ここで、ネットワーク符号とは、非特許文献４にあるように与えられたネットワーク上でマルチキャスト伝送を実現するためのものである。このネットワーク符号を「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」における再生成符号の実現に適用することが試みられている。ところが、「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」にネットワーク符号化を適用しようとすると以下の困難に直面する。
［困難１］  分散ストレージの各ノードはランダムに故障する。従って「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」の形は一通りではない。
［困難２］  「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」は時間的に発展しているためネットワークはいくらでも大きくなり得る。つまり、ノードの故障・再生成が発生するたびにいくらでも長く伸びていく。
［困難３］  「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」の形が予め確定していないため、符号化のための行列の情報もコンテンツデータと一緒に送信されなければならない。このため分散ストレージ系のアルファベットＦｑにおけるｑ＝２ｍのｍをブロック長と見なしたとき、コンテンツの大きさが再生成符号の容量限界に近づくためには、符号化行列（もしくは符号化ベクトル）の情報はｏ（ｍ）の大きさでなければならない。ここで、ｍに依存する量ｆ（ｍ）がｏ（ｍ）の大きさであるとは、
【数２】
0006445955.tif 000003
を満足する量であることをいう。
【０００９】
上述の困難のため、現状ではトレードオフ曲線上の任意の点における再生成符号を構成するのではなく、αやβが最小であるような特定の点についてのみ具体的な符号が構成されている（例えば、非特許文献２を参照。）。αに関して最小の符号を「Ｍｉｎｉｍｕｍ  Ｓｔｏｒａｇｅ  Ｒｅｇｅｎｅｒａｔｉｏｎ（ＭＳＲ）符号」、βに関して最小の符号を「Ｍｉｎｉｍｕｍ  Ｂａｎｄｗｉｄｔｈ  Ｒｅｇｅｎｅｒａｔｉｏｎ（ＭＢＲ）符号」と呼ぶ。
【００１０】
ＭＳＲ／ＭＢＲ点以外での符号の具体的な構成は分散ストレージのみならず、ＩＣＮやＣＣＮ（例えば、非特許文献１を参照）などのネットワーク上の各ノードに付随するキャッシュ機能を拡張してコンテンツ・ストレージとして利用するデータ転送方式においても今後重要になってくると見なされる。
【００１１】
３．課題
前節で述べたように、α−βトレードオフ曲線上の任意の点（α、β）を含む分散ストレージのパラメータ（ｎ、ｋ、ｄ、α、β）が与えられた時に、このパラメータを実現する再生成符号を構成することが理想である。しかしながら、「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」に対する線形ネットワーク符号を構成するという自然なアプローチでは２節で述べた困難が生ずる。
【００１２】
そこで、本発明は、α−βトレードオフ曲線上の任意の点（α，β）を含む分散ストレージのパラメータ（ｎ、ｋ、ｄ、α、β）が与えられた時に「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」に対する線形ネットワーク符号で構成できる分散ストレージ制御方法及び分散ストレージシステムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するために、本願発明に係る分散ストレージ制御方法及び分散ストレージシステムは、ノード故障回数毎に加算するカウンタを設置し、ノード故障が最大カウンタ値に達したならば、分散ストレージ系をすべてリフレッシュして分散符号化を始めから再開するようにした。また、符号化ベクトルのデータ量をコンテンツの符号化データ量に比較して無視できるほど小さくするために、情報源ノードで分散ストレージ系アルファベットを適切な大きさの符号化アルファベットに変換し、復元ノードで符号化アルファベットを分散ストレージ系アルファベットへ逆変換する処理を配置した。
【００１４】
具体的には、本願発明に係る分散ストレージ制御方法は、
コンテンツデータを保持する情報源ノードと、
前記コンテンツデータを分散させた分散データを保持する複数のストレージノードと、
任意の前記ストレージノードから出力された分散データを受信して前記コンテンツデータを復元する復元ノードと、
で構成される分散ストレージ系を有する分散ストレージシステムを制御する分散ストレージ制御方法であって、
前記情報源ノードで前記コンテンツデータを符号化する分散ストレージ系アルファベットを、前記分散ストレージ系アルファベットより小さな符号化アルファベットに変換する変換手順と、
前記復元ノードで前記符号化アルファベットを前記分散ストレージ系アルファベットに戻す逆変換手順と、
前記ストレージノードの故障時に他の少なくとも１の前記ストレージノードからデータを受信して故障した前記ストレージノードの代替となる再生成用ストレージノードを形成し、前記分散ストレージ系を更新する再生成手順と、
前記ストレージノードの故障の回数をカウントし、前記回数が上限値に達した時、構成された前記分散ストレージ系をリセットして改めて分散ストレージ系を構成するリセット手順と、
を行うことを特徴とする。
【００１５】
また、本願発明に係る分散ストレージシステムは、
コンテンツデータを保持する情報源ノードと、
前記コンテンツデータを分散させた分散データを保持する複数のストレージノードと、
任意の前記ストレージノードから出力された分散データを受信して前記コンテンツデータを復元する復元ノードと、
で構成される分散ストレージ系を有する分散ストレージシステムであって、
前記情報源ノードが、前記コンテンツデータを符号化する分散ストレージ系アルファベットを、前記分散ストレージ系アルファベットより小さな符号化アルファベットに変換する変換機能を有し、
前記復元ノードが、前記符号化アルファベットを前記分散ストレージ系アルファベットに戻す逆変換機能を有しており、
前記ストレージノードの故障時に他の少なくとも１の前記ストレージノードからデータを受信して故障した前記ストレージノードの代替となる再生成用ストレージノードを形成し、前記分散ストレージ系を更新する再生成機能と、
前記ストレージノードの故障の回数をカウントし、前記回数が上限値に達した時、構成された前記分散ストレージ系をリセットして改めて分散ストレージ系を構成するリセット機能と、
を備える制御部を備えることを特徴とする。
【００１６】
本発明は、最大カウンタ値を導入することで「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」を時間的にも空間的にも有限にすることを可能とし、ランダムネットワーク符号化アルゴリズムを用いた再生成符号のネットワーク符号化を実現できる。本発明は、線形ネットワーク符号を用いるため、再生成符号の符号化をベクトルどうしのスカラー積、復号化をガウスの掃き出し法を用いることできわめて容易に実現できる。
【００１７】
従って、本発明は、α−βトレードオフ曲線上の任意の点（α，β）を含む分散ストレージのパラメータ（ｎ、ｋ、ｄ、α、β）が与えられた時に「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」に対する線形ネットワーク符号で構成できる分散ストレージ制御方法及び分散ストレージシステムを提供することができる。
【００１８】
好ましい形態として、本願発明に係る分散ストレージ制御方法は、前記ストレージノードにおいて、ネットワーク符号化された少なくとも１つの入力データが入力され、ネットワーク符号構成アルゴリズムとしてランダムネットワーク符号化アルゴリズムを適用し、前記入力データに含まれる前記分散データと前記変換手順で変換された前記符号化アルファベットで構成された符号化行列を掛け合わせて後段のノードへ出力する出力データを計算することを特徴とする。
【００１９】
また、本願発明に係る分散ストレージシステムの前記ストレージノードは、ネットワーク符号化された少なくとも１つの入力データが入力され、ネットワーク符号構成アルゴリズムとしてランダムネットワーク符号化アルゴリズムを適用し、前記入力データに含まれる前記分散データと前記情報源ノードが変換した前記符号化アルファベットで構成された符号化行列を掛け合わせて後段のノードへ出力する出力データを計算することを特徴とする。
【発明の効果】
【００２０】
本発明は、α−βトレードオフ曲線上の任意の点（α，β）を含む分散ストレージのパラメータ（ｎ、ｋ、ｄ、α、β）が与えられた時に「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」に対する線形ネットワーク符号で構成できる分散ストレージ制御方法及び分散ストレージシステムを提供することができる。
【図面の簡単な説明】
【００２１】
【図１】分散ストレージシステムのＩｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈの例を説明する図である。
【図２】分散ストレージシステムのＩｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈの例を説明する図である。
【図３】非特許文献３に記載されるα‐βトレードオフ曲線の例を説明する図である。
【図４】本発明に係る分散ストレージシステムのストレージノードを説明する図である。
【図５】本発明に係る分散ストレージシステムの復元ノードを説明する図である。
【図６】本発明に係る分散ストレージシステムの情報源ノードの動作（符号化ベクトルの割り当て）を説明する図である。
【図７】本発明に係る分散ストレージシステムのストレージノードの動作（符号化ベクトルの割り当て）を説明する図である。
【図８】本発明に係る分散ストレージシステムを説明する図である。
【発明を実施するための形態】
【００２２】
４．開発技術の具体的な説明
４．１  システム概要
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００２３】
図８は、本実施形態の分散ストレージシステム３０１を説明する図である。分散ストレージシステム３０１は、
コンテンツデータを保持する情報源ノード５と、
前記コンテンツデータを分散させた分散データを保持する複数のストレージノード１０と、
任意のストレージノード１０から出力された分散データを受信して前記コンテンツデータを復元する復元ノード２０と、
で構成される分散ストレージ系を有する分散ストレージシステムであって、  情報源ノード１５が、前記コンテンツデータを符号化する分散ストレージ系アルファベットを、前記分散ストレージ系アルファベットより小さな符号化アルファベットに変換するアルファベット変換処理部１６を有し、
復元ノード２０が、前記符号化アルファベットを前記分散ストレージ系アルファベットに戻すアルファベット変換処理部２４を有しており、
ストレージノード１０の故障時に他の少なくとも１のストレージノード１０からデータを受信して故障したストレージノード１０の代替となる再生成用ストレージノードを形成し、前記分散ストレージ系を更新する再生成機能と、
前記ストレージノードの故障の回数をカウントし、前記回数が上限値に達した時、構成された前記分散ストレージ系をリセットして改めて分散ストレージ系を構成するリセット機能と、
を備える制御部を備えることを特徴とする。
【００２４】
ストレージノード１０は、
ネットワーク符号化された少なくとも１つの入力データが入力され、ネットワーク符号構成アルゴリズムとしてランダムネットワーク符号化アルゴリズムを適用し、前記入力データに含まれる前記分散データと情報源ノード１５が変換した前記符号化アルファベットで構成された符号化行列を掛け合わせて後段のノードへ出力する出力データを計算する。なお、当該計算は後述する数式（１３）の処理である。
【００２５】
分散ストレージシステム３０１は２節で述べた困難を次のように克服することでα−βトレードオフ曲線上の任意の点を達成する再生成符号を構成する。
【００２６】
困難２に対して：
分散ストレージシステム３０１は、ノード故障回数毎に加算するカウンタを持ち、ノード故障が最大カウンタ値Ｔに達したならば、分散ストレージ系をすべてリフレッシュして分散符号化（本実施形態の場合、ネットワーク符号化）を始めから再開する。最大カウンタ値を設定することで、「Ｉｎｆｏｒａｍｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」が（時間方向に）無限に延びていくことはなくなった。
【００２７】
困難１に関して：
最大カウンタ値Ｔを定義することによって故障がＴ回発生するまでに「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」の取り得るトポロジーの数は有限で抑えられる。従って、ネットワーク符号構成アルゴリズムにランダムネットワーク符号化アルゴリズム（非特許文献４を参照。）を適用すれば、ノード間の通信路である各リンク、すなわち「Ｉｎｆｏｒｍａｔｉｏｎ  Ｆｌｏｗ  Ｇｒａｐｈ」の各辺に適切な符号化ベクトルが割り当てられる確率を、分散ストレージ系アルファベットもしくは符号化アルファベットのバイト長ｍに関して漸近的に限りなく１に近づけることが示せる。ここで、「適切な符号化ベクトルの割り当て」とは、それによって復元ノード２０がいかなるコンテンツデータに対しても正しく復号化可能であるような符号化ベクトルの割り当てのことをいう。そして、「バイト長ｍに関して漸近的に限りなく１に近づける」とは、後述するように符号化ベクトルの構成は（１０）式および（１１）式のようにランダムになされるので、バイト長ｍを十分大きくすれば適切な符号化ベクトルが得られる確率を高めることができるという意味である。
【００２８】
困難３に関して：
分散ストレージシステム３０１は、予め与えられている分散ストレージ系のアルファベットＦｑから小さな符号化アルファベットＦｑ〜＝｛０，１，２，・・・，ｑ〜−１｝（ただしｑ〜＜ｑ）に変換することによって符号化アルファベットＦｑ〜上でネットワーク符号を構成する。このため、分散ストレージシステム３０１は、バイト長ｍが十分長い漸近的な極限では再生成用のデータ量βに比べてネットワーク符号のための符号化ベクトルのデータ量を無視できる。
【００２９】
４．２  具体的な符号構成
分散ストレージシステム３０１の動作は、
（０）分散ストレージ系アルファベットＦｑから符号化アルファベットＦｑ〜への変換、
（１）符号化ベクトルの構成、
（２）各リンクにおける符号化および送信データの構成、
（３）ＤＣ（復元ノード）における復号化、および符号化アルファベットＦｑ〜から分散ストレージ系のアルファベットＦｑへの逆変換、
の４ステップよりなる。
図４は、ノードν（ストレージノード１０）の構成および動作（ステップ（１）と（２））を説明する図である。図５は、復元ノード２０の構成および動作（ステップ（３））を説明する図である。
【００３０】
ステップ（０）［分散ストレージ系のアルファベットから符号化アルファベットへの変換］
分散ストレージ系のアルファベットＦｑ（ただしｑ＝２ｍ）から符号化アルファベットＦｑ〜（ただしｑ〜＝２ε，ε＝ｍδ）への１対１写像ψを次のように定義する。
【数３】
0006445955.tif 000004
すなわちｘ∈Ｆｑを２進表現すれば（ｂ１、・・・、ｂｍ）とｍビットで表すことができる。写像ψは、この２進表現をｍδビット毎に区切ることで
【数４】
0006445955.tif 000005
として表現したものである。また、ｘ１、ｘ２∈Ｆｑに対して
【数５】
0006445955.tif 000006
として定義する。ここで“＊”は文字列の連接を表すものとする。
【００３１】
ステップ（１）［符号化ベクトルの構成］
正の定数０＜δ＜１が予め与えられているとする。最初に符号化アルファベットを確定させるために，情報源ノード１５（情報源ノードｓ）においてアルファベットのＦｑからＦｑ〜への変換処理（ただし、ｑ〜＝２ε＜ｑ＝２ｍ）が行われる（（３）式及び（５）式を参照）。ランダムネットワーク符号化アルゴリズム実行部１２は、入力部１１に入力された符号化アルファベットＦｑ〜上の符号化ベクトルを利用し、これらから出射リンクe’上の符号化ベクトルを構成する。対象となる「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」は有向非周期グラフなので、情報源ノードｓを１番目とした順序付けが可能となる。この順序に従って、各ノードから出射するリンクに対して符号化ベクトルを帰納的に割り当てる。
【００３２】
図６は、情報源ノードｓの動作を説明する図である。情報源ノードｓに対しては図６のように仮想的に容量Ｂのリンクが入射しているものと見なす。このとき、ｓへの入射リンクには符号化ベクトル
【数６】
0006445955.tif 000007
が割り当てられる。ここで、［１：Ｂ］＝｛１、２、・・・、Ｂ｝を表すものとする。単位容量あたり１つの符号化ベクトルが割り当てられることに注意しておく。
【００３３】
図７は、ノードνの動作を説明する図である。ノードνにおける容量Ｒｅの入射リンクｅには符号化ベクトル
【数７】
0006445955.tif 000008
が割り当てられているものとする。ここで、
【数８】
0006445955.tif 000009
である。ただしＴは転置を表す。このデータは符号語と一緒に図４の入力部１１に蓄積される。このときノードνの出射リンクｅ’に対しては
【数９】
0006445955.tif 000010
のＲｅ’個の符号化ベクトルが割り当てられることになる。各々の符号化ベクトルは、
【数１０】
0006445955.tif 000011
として与えられる。ただし、係数
【数１１】
0006445955.tif 000012
は符号化アルファベットＦｑ〜より一様ランダムに取り出されたものとする。ここで、Ｉｎ（ν）はノードνへ入射するリンクの集合を表す。また「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」においてリンク容量Ｒｅはαもしくはβの値をとる。
【００３４】
次に符号化を実行するために（１０）式で与えられた符号化ベクトルから符号化行列を構成する。以下ｍ１−δ×ｍ１−δ単位行列をＩとする。ノードνから出射するリンクｅ∈Ｏｕｔ（ν）上の符号化行列は
【数１２】
0006445955.tif 000013
として与えられる。ここで、Ｏｕｔ（ν）はノードνから出射するリンクの集合を表す。
【００３５】
ステップ（２）［各リンクにおける符号化および送信データの構成］
図４の出力部１３の動作を説明する。リンクｅにおける符号化を説明する。ｅ∈Ｏｕｔ（ν）において、符号化を
【数１３】
0006445955.tif 000014
によって実行する。このときリンクｅが出力する出力データを
【数１４】
0006445955.tif 000015
とする。（１４）式には未知の量ｘＢが見かけ上含まれているが、ノードνが受け取るデータ（入力部１１が受信する入力データ）を
【数１５】
0006445955.tif 000016
とすると、
【数１６】
0006445955.tif 000017
によって与えられる。
【００３６】
また、ノードνからＤＣへ送られるデータはノードν’（物理的なノードとしてはノードνと同一であるが再生成のためのデータを受信するノードとして論理的に区別した）より送られてきたデータをそのまま転送するものとする。ここで、ｑ〜＝２ｍδなので
【数１７】
0006445955.tif 000018
ならば、適切な符号化ベクトルが各リンクに割り当てられる確率が十分大きくなることが示せる。ただし、Ｔは予め設定された最大カウンタ値である。また符号化ベクトルに関するデータを送信する際のデータ量は（１４）式よりＢＲｅｍδビットであるので、ｍが十分大きければ符号語のデータ量Ｒｅｍビットに比較して無視できるほど小さくなる。
【００３７】
ステップ（３）［ＤＣにおける復号化］
図５の復元ノード２０の動作を説明する。
ＤＣ（復元ノード２０）がｋ個のノードνｉ１、・・・、νｉｋにアクセスするとき、ノードνｉａより送られるデータを
【数１８】
0006445955.tif 000019
と書く。これらのデータは入力部２１に蓄積される。ただし、Ａ〜ｉａは対応する符号化ベクトルを横に並べたものをまとめて行列表現としたものである。このとき復号化は次の一次方程式
【数１９】
0006445955.tif 000020
を解くことにより実行される。一次方程式の求解は掃き出し法実行部２２でなされる。ここで、ＡｉａはＡ〜ｉａの対応する符号化ベクトルの各要素にｍ１−δ×ｍ１−δ単位行列を掛けたものである。次に変換処理部２４で符号化アルファベットから分散ストレージ系アルファベットへの逆変換処理がなされる。処理内容は，ステップ（０）で説明した変換処理の逆処理である。要するに
【数２０】
0006445955.tif 000021
は１対１写像であるので一次方程式（１９）式の解ψ（ｘＢ）から求めるコンテンツデータｘＢを復元できることになる。
【００３８】
５．発明によって生じる効果
非特許文献１のＩＣＮ／ＣＣＮは次世代コンテンツ配信の有力な方式のひとつである。これは、ネットワーク上のノードに付随するキャッシュをローカルなストレージとして再定義することでネットワーク負荷の低減およびエンドユーザに対する実効スループット向上を目指すものである。ＩＣＮ／ＣＣＮの具体的なアーキテクチャは現在のところ研究段階ではあるが、その実現においてはネットワーク上にある種の分散ストレージが実現されることになることは明らかである。分散ストレージでのデータ保存量と再生成のためのデータ転送量は（１）式で示したトレードオフの関係を持つ。従って、もしＭＳＲ／ＭＢＲ点でなければ最適な符号が構成できないようであればネットワーク上の各ノードで保存可能なデータ量に対しても著しい制限が課されることになり、ＩＣＮ／ＣＣＮの最大限のパフォーマンスを発揮することが困難となると考えられる。本発明は、α−βトレードオフ曲線上の任意の点における再生成符号の構成を可能とするものであるから、ＩＣＮ／ＣＣＮ  のキャッシュ（もしくはローカルストレージ）機能を最大限に発揮させることができる。
【００３９】
６．発明のポイント
４．１節で述べたように、本発明は、最大カウンタ値を導入することで「Ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ  ｇｒａｐｈ」を時間的にも空間的にも有限にすることが可能となったのがポイントである。これによって、ランダムネットワーク符号化アルゴリズムを使う際に符号化ベクトルの係数をランダムに割り当ててもアルファベットのバイト長が十分大きいならば適切に符号化ベクトルの係数が割り当てられる確率を限りなく１に近くなることを示すことができた。ここで，適切な符号化ベクトルの割り当てとは、それによってＤＣがいかなるコンテンツデータに対しても正しく復号化可能であるような符号化ベクトルの割り当てのことをいう。また適切な符号化アルファベットへの変換を用いることで、符号化アルファベットを分散ストレージ系のアルファベットよりも小さくとることができるので、再生成のデータ転送の際に、符号化ベクトルの係数の転送にかかるデータ量は再生成用のコンテンツデータに比較して無視できるようにすることができた。
【符号の説明】
【００４０】
１０：ストレージノード
１１：入力部
１２：ランダムネットワーク符号化アルゴリズム実行部
１３：出力部
１５：情報源ノード
１６：アルファベット変換処理部
２０：復元ノード
２１：入力部
２２：掃き出し法実行部
２４：アルファベット変換処理部
３０：制御部
３１：再生成機能
３２：リセット機能
３０１：分散ストレージシステム
【図１】
0006445955.tif 000022
【図２】
0006445955.tif 000023
【図３】
0006445955.tif 000024
【図４】
0006445955.tif 000025
【図５】
0006445955.tif 000026
【図６】
0006445955.tif 000027
【図７】
0006445955.tif 000028
【図８】
0006445955.tif 000029