図面 (/)

技術 分散ストレージ制御方法及び分散ストレージシステム

出願人 日本電信電話株式会社
発明者 三宅茂樹
出願日 2015年11月12日 (3年10ヶ月経過) 出願番号 2015-222053
公開日 2017年5月25日 (2年3ヶ月経過) 公開番号 2017-091307
状態 特許登録済
技術分野 計算機におけるファイル管理 入出力制御 ハードウェアの冗長性 検索装置
主要キーワード 再生成後 データ保存量 線形ネットワーク リセット手順 トレードオフ曲線 故障回数 スカラー積 復号用データ
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2017年5月25日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (9)

課題

α−βトレードオフ曲線上の任意の点(α,β)を含む分散ストレージパラメータ(n、k、d、α、β)が与えられた時に「Information flow graph」に対する線形ネットワーク符号で構成できる分散ストレージ制御方法及び分散ストレージシステムを提供することを目的とする。

解決手段

本願発明に係る分散ストレージ制御方法及び分散ストレージシステムは、ノード故障回数毎に加算するカウンタを設置し、ノード故障が最大カウンタ値に達したならば,分散ストレージ系をすべてリフレッシュして分散符号化を始めから再開するようにした。また、符号化ベクトルのデータ量をコンテンツ符号化データ量に比較して無視できるほど小さくするために情報源ノードおよび復元ノードにおいて適切な大きさのアルファベットに変換する処理を配置した。

概要

背景

1.分散ストレージ技術の概要
(n、k)分散ストレージ系を図1に示す。図1はn=4、k=3の場合である。情報源をsとし、sは保存・復元されるコンテンツを持つ。保存・復元されるコンテンツをxBと書く。肩にかかるBはコンテンツ長がBバイトであることを示すものとする。すなわちxB={x1,x2、・・・,xB}に対してxi∈{0,1,・・・,q−1}とする。ここで集合{0,1,・・・,q−1}を「分散ストレージ系のアルファベット」と呼ぶ。また、分散ストレージ系のアルファベットを有限体Fqにとる。ここでq=2mであり、1バイト=mビットとしておく(要するにxB∈FqBである。)。例えば対象とする系で送受信されるパケット長を1バイトとおくことが考えられる。コンテンツはn個のストレージに分散して保存される。また、データを復元する者を「Data Collector」以下、「DC」と略記する。)と呼ぶことにする。DCは任意のk個のストレージにアクセスして、各ストレージからαバイトずつデータを受け取る。DCは受け取ったデータを復号することで元のコンテンツxBを復元する。

ところで、分散ストレージの各ノード故障リスクが常につきまとう。図2はノード1が故障し、同じサイトにおいてノード5を新たに構成した状況を表している。本明細書では「サイト」という言葉を特定のストレージが存在する場所を指すものとする。このとき、ノード5は故障する前のノード1と同じ機能をもつことが要請される。すなわち、図2においてノードの再生成後、DCは再び任意のk個のストレージにアクセスして、各ストレージからαバイトずつデータを受け取ることで元のコンテンツxBを復元することができることになる。ノードが故障した際に、同じサイトに同一機能を持つ新たなノードを構成することを「再生成」と呼ぶ。再生成は新たなノード(図2の符号5’)が故障していないd個のノードからβバイトずつ再生成用データを受け取ることでなされる。

図2においてノード5およびノード5’の2種類が存在するのは、後で再生成符号としてのネットワーク符号非特許文献4を参照)を構成するための便宜的なもので、物理的な存在としては同一である。ノード5’は再生成用のデータを受け取るノード、ノード5は復元用のデータをDCに送信するノードを表している。なお、図2の横軸は時間を表しており、図は各時点でどのノードが故障し、どのノードから再生成用データが転送され、DCはどのノードから復号用データを取得したか、等を示すもので、一般に「Information flow graph」と呼ばれている。

上記で説明した再生成のための分散データを構成するための符号(n、k、d、α、β)を「再生成符号」と呼ぶ。再生成符号は分散符号の1つである。再生成符号はDimakis達によって提案(非特許文献3)され、その基本的な性質が明らかにされている。再生成の特徴はデータ保存量αと再生成用データ転送量βとの間にトレードオフがあるというもので次の命題として記される。
[命題1]
分散ストレージ系のパラメータ(n,k,d,α,β)が与えられているとする。DCが任意のk個の分散ストレージにアクセスすることで大きさBバイトのコンテンツを正しく復元することができ、さらに故障ノードが任意のd個の分散ストレージにアクセスすることで正しく再生成されるための必要十分条件は、



として与えられる(非特許文献3を参照。)。

(1)式が表す曲線トレードオフ曲線)の例を図3(非特許文献3)に示す。図3の曲線の上側が理論的に実現可能な領域を表す。課題は、トレードオフ曲線上の任意の点に近接する点を実現するような再生成符号を構成することである。

概要

α−βトレードオフ曲線上の任意の点(α,β)を含む分散ストレージのパラメータ(n、k、d、α、β)が与えられた時に「Information flow graph」に対する線形ネットワーク符号で構成できる分散ストレージ制御方法及び分散ストレージシステムを提供することを目的とする。本願発明に係る分散ストレージ制御方法及び分散ストレージシステムは、ノード故障回数毎に加算するカウンタを設置し、ノード故障が最大カウンタ値に達したならば,分散ストレージ系をすべてリフレッシュして分散符号化を始めから再開するようにした。また、符号化ベクトルのデータ量をコンテンツの符号化データ量に比較して無視できるほど小さくするために情報源ノードおよび復元ノードにおいて適切な大きさのアルファベットに変換する処理を配置した。

目的

課題は、トレードオフ曲線上の任意の点に近接する点を実現するような再生成符号を構成することである

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

コンテンツデータを保持する情報源ノードと、前記コンテンツデータを分散させた分散データを保持する複数のストレージノードと、任意の前記ストレージノードから出力された分散データを受信して前記コンテンツデータを復元する復元ノードと、で構成される分散ストレージ系を有する分散ストレージシステムを制御する分散ストレージ制御方法であって、前記情報源ノードで前記コンテンツデータを符号化する分散ストレージ系アルファベットを、前記分散ストレージ系アルファベットより小さな符号化アルファベットに変換する変換手順と、前記復元ノードで前記符号化アルファベットを前記分散ストレージ系アルファベットに戻す逆変換手順と、前記ストレージノードの故障時に他の少なくとも1の前記ストレージノードからデータを受信して故障した前記ストレージノードの代替となる再生成用ストレージノードを形成し、前記分散ストレージ系を更新する再生成手順と、前記ストレージノードの故障の回数カウントし、前記回数が上限値に達した時、構成された前記分散ストレージ系をリセットして改めて分散ストレージ系を構成するリセット手順と、を行うことを特徴とする分散ストレージ制御方法。

請求項2

前記ストレージノードにおいて、ネットワーク符号化された少なくとも1つの入力データが入力され、ネットワーク符号構成アルゴリズムとしてランダムネットワーク符号化アルゴリズムを適用し、前記入力データに含まれる前記分散データと前記変換手順で変換された前記符号化アルファベットで構成された符号化行列掛け合わせて後段のノードへ出力する出力データを計算することを特徴とする請求項1に記載の分散ストレージ制御方法。

請求項3

コンテンツデータを保持する情報源ノードと、前記コンテンツデータを分散させた分散データを保持する複数のストレージノードと、任意の前記ストレージノードから出力された分散データを受信して前記コンテンツデータを復元する復元ノードと、で構成される分散ストレージ系を有する分散ストレージシステムであって、前記情報源ノードが、前記コンテンツデータを符号化する分散ストレージ系アルファベットを、前記分散ストレージ系アルファベットより小さな符号化アルファベットに変換する変換機能を有し、前記復元ノードが、前記符号化アルファベットを前記分散ストレージ系アルファベットに戻す逆変換機能を有しており、前記ストレージノードの故障時に他の少なくとも1の前記ストレージノードからデータを受信して故障した前記ストレージノードの代替となる再生成用ストレージノードを形成し、前記分散ストレージ系を更新する再生成機能と、前記ストレージノードの故障の回数をカウントし、前記回数が上限値に達した時、構成された前記分散ストレージ系をリセットして改めて分散ストレージ系を構成するリセット機能と、を備える制御部を備えることを特徴とする分散ストレージシステム。

請求項4

前記ストレージノードは、ネットワーク符号化された少なくとも1つの入力データが入力され、ネットワーク符号構成アルゴリズムとしてランダムネットワーク符号化アルゴリズムを適用し、前記入力データに含まれる前記分散データと前記情報源ノードが変換した前記符号化アルファベットで構成された符号化行列を掛け合わせて後段のノードへ出力する出力データを計算することを特徴とする請求項3に記載の分散ストレージシステム。

技術分野

0001

本発明は、分散ストレージにおけるデータ保存量ノード再生データ転送量との任意のトレードオフを達成する符号化技術に関する。

背景技術

0002

1.分散ストレージ技術の概要
(n、k)分散ストレージ系を図1に示す。図1はn=4、k=3の場合である。情報源をsとし、sは保存・復元されるコンテンツを持つ。保存・復元されるコンテンツをxBと書く。肩にかかるBはコンテンツ長がBバイトであることを示すものとする。すなわちxB={x1,x2、・・・,xB}に対してxi∈{0,1,・・・,q−1}とする。ここで集合{0,1,・・・,q−1}を「分散ストレージ系のアルファベット」と呼ぶ。また、分散ストレージ系のアルファベットを有限体Fqにとる。ここでq=2mであり、1バイト=mビットとしておく(要するにxB∈FqBである。)。例えば対象とする系で送受信されるパケット長を1バイトとおくことが考えられる。コンテンツはn個のストレージに分散して保存される。また、データを復元する者を「Data Collector」以下、「DC」と略記する。)と呼ぶことにする。DCは任意のk個のストレージにアクセスして、各ストレージからαバイトずつデータを受け取る。DCは受け取ったデータを復号することで元のコンテンツxBを復元する。

0003

ところで、分散ストレージの各ノードは故障リスクが常につきまとう図2はノード1が故障し、同じサイトにおいてノード5を新たに構成した状況を表している。本明細書では「サイト」という言葉を特定のストレージが存在する場所を指すものとする。このとき、ノード5は故障する前のノード1と同じ機能をもつことが要請される。すなわち、図2においてノードの再生成後、DCは再び任意のk個のストレージにアクセスして、各ストレージからαバイトずつデータを受け取ることで元のコンテンツxBを復元することができることになる。ノードが故障した際に、同じサイトに同一機能を持つ新たなノードを構成することを「再生成」と呼ぶ。再生成は新たなノード(図2の符号5’)が故障していないd個のノードからβバイトずつ再生成用データを受け取ることでなされる。

0004

図2においてノード5およびノード5’の2種類が存在するのは、後で再生成符号としてのネットワーク符号非特許文献4を参照)を構成するための便宜的なもので、物理的な存在としては同一である。ノード5’は再生成用のデータを受け取るノード、ノード5は復元用のデータをDCに送信するノードを表している。なお、図2横軸は時間を表しており、図は各時点でどのノードが故障し、どのノードから再生成用データが転送され、DCはどのノードから復号用データを取得したか、等を示すもので、一般に「Information flow graph」と呼ばれている。

0005

上記で説明した再生成のための分散データを構成するための符号(n、k、d、α、β)を「再生成符号」と呼ぶ。再生成符号は分散符号の1つである。再生成符号はDimakis達によって提案(非特許文献3)され、その基本的な性質が明らかにされている。再生成の特徴はデータ保存量αと再生成用データ転送量βとの間にトレードオフがあるというもので次の命題として記される。
[命題1]
分散ストレージ系のパラメータ(n,k,d,α,β)が与えられているとする。DCが任意のk個の分散ストレージにアクセスすることで大きさBバイトのコンテンツを正しく復元することができ、さらに故障ノードが任意のd個の分散ストレージにアクセスすることで正しく再生成されるための必要十分条件は、



として与えられる(非特許文献3を参照。)。

0006

(1)式が表す曲線トレードオフ曲線)の例を図3(非特許文献3)に示す。図3の曲線の上側が理論的に実現可能な領域を表す。課題は、トレードオフ曲線上の任意の点に近接する点を実現するような再生成符号を構成することである。

先行技術

0007

V. Jacobson, D. K. Smetters, J. D. Thornton, M. F. Plass, N. H. Briggs, and R. L. Braynard, “Networking named content”, in Proc. 5thACMInternational Conference on Emerging Networking Experiments and Technologies, pp.1−12, 2009.
門秀典,原正純, 「分散ストレージシステムのための新しい符号化法−再生成符号とPyramid符号−」, 信学会誌, vol.98, no.2, pp.130−137,2015.
A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems”,IEEE Trans. Inf. Theory, vol.56, no.9, pp.4539−4551, Sept. 2010.
T.Ho, M.Medard, R.Koetter, D.R.Karger, M.Effros, J.Shi, and B.Leong, “A random linear network coding approach to multicast”, IEEE Trans. Inf. Theory, vol.52, no.10, pp.4413−4430, Oct. 2006.

発明が解決しようとする課題

0008

2.従来の技術での困難点
図2で示したように 「Information flow graph」は一般に有向周期グラフとなるため、再生成符号の実現にはネットワーク符号を適用することが適切であるように思われる。ここで、ネットワーク符号とは、非特許文献4にあるように与えられたネットワーク上でマルチキャスト伝送を実現するためのものである。このネットワーク符号を「Information flow graph」における再生成符号の実現に適用することが試みられている。ところが、「Information flow graph」にネットワーク符号化を適用しようとすると以下の困難に直面する。
[困難1]分散ストレージの各ノードはランダムに故障する。従って「Information flow graph」の形は一通りではない。
[困難2] 「Information flow graph」は時間的に発展しているためネットワークはいくらでも大きくなり得る。つまり、ノードの故障・再生成が発生するたびにいくらでも長く伸びていく。
[困難3] 「Information flow graph」の形が予め確定していないため、符号化のための行列の情報もコンテンツデータと一緒に送信されなければならない。このため分散ストレージ系のアルファベットFqにおけるq=2mのmをブロック長と見なしたとき、コンテンツの大きさが再生成符号の容量限界に近づくためには、符号化行列(もしくは符号化ベクトル)の情報はo(m)の大きさでなければならない。ここで、mに依存する量f(m)がo(m)の大きさであるとは、



満足する量であることをいう。

0009

上述の困難のため、現状ではトレードオフ曲線上の任意の点における再生成符号を構成するのではなく、αやβが最小であるような特定の点についてのみ具体的な符号が構成されている(例えば、非特許文献2を参照。)。αに関して最小の符号を「Minimum Storage Regeneration(MSR)符号」、βに関して最小の符号を「Minimum Bandwidth Regeneration(MBR)符号」と呼ぶ。

0010

MSR/MBR点以外での符号の具体的な構成は分散ストレージのみならず、ICNやCCN(例えば、非特許文献1を参照)などのネットワーク上の各ノードに付随するキャッシュ機能拡張してコンテンツ・ストレージとして利用するデータ転送方式においても今後重要になってくると見なされる。

0011

3.課題
前節で述べたように、α−βトレードオフ曲線上の任意の点(α、β)を含む分散ストレージのパラメータ(n、k、d、α、β)が与えられた時に、このパラメータを実現する再生成符号を構成することが理想である。しかしながら、「Information flow graph」に対する線形ネットワーク符号を構成するという自然なアプローチでは2節で述べた困難が生ずる。

0012

そこで、本発明は、α−βトレードオフ曲線上の任意の点(α,β)を含む分散ストレージのパラメータ(n、k、d、α、β)が与えられた時に「Information flow graph」に対する線形ネットワーク符号で構成できる分散ストレージ制御方法及び分散ストレージシステムを提供することを目的とする。

課題を解決するための手段

0013

上記目的を達成するために、本願発明に係る分散ストレージ制御方法及び分散ストレージシステムは、ノード故障回数毎に加算するカウンタを設置し、ノード故障が最大カウンタ値に達したならば、分散ストレージ系をすべてリフレッシュして分散符号化を始めから再開するようにした。また、符号化ベクトルのデータ量をコンテンツの符号化データ量に比較して無視できるほど小さくするために、情報源ノードで分散ストレージ系アルファベットを適切な大きさの符号化アルファベットに変換し、復元ノードで符号化アルファベットを分散ストレージ系アルファベットへ逆変換する処理を配置した。

0014

具体的には、本願発明に係る分散ストレージ制御方法は、
コンテンツデータを保持する情報源ノードと、
前記コンテンツデータを分散させた分散データを保持する複数のストレージノードと、
任意の前記ストレージノードから出力された分散データを受信して前記コンテンツデータを復元する復元ノードと、
で構成される分散ストレージ系を有する分散ストレージシステムを制御する分散ストレージ制御方法であって、
前記情報源ノードで前記コンテンツデータを符号化する分散ストレージ系アルファベットを、前記分散ストレージ系アルファベットより小さな符号化アルファベットに変換する変換手順と、
前記復元ノードで前記符号化アルファベットを前記分散ストレージ系アルファベットに戻す逆変換手順と、
前記ストレージノードの故障時に他の少なくとも1の前記ストレージノードからデータを受信して故障した前記ストレージノードの代替となる再生成用ストレージノードを形成し、前記分散ストレージ系を更新する再生成手順と、
前記ストレージノードの故障の回数カウントし、前記回数が上限値に達した時、構成された前記分散ストレージ系をリセットして改めて分散ストレージ系を構成するリセット手順と、
を行うことを特徴とする。

0015

また、本願発明に係る分散ストレージシステムは、
コンテンツデータを保持する情報源ノードと、
前記コンテンツデータを分散させた分散データを保持する複数のストレージノードと、
任意の前記ストレージノードから出力された分散データを受信して前記コンテンツデータを復元する復元ノードと、
で構成される分散ストレージ系を有する分散ストレージシステムであって、
前記情報源ノードが、前記コンテンツデータを符号化する分散ストレージ系アルファベットを、前記分散ストレージ系アルファベットより小さな符号化アルファベットに変換する変換機能を有し、
前記復元ノードが、前記符号化アルファベットを前記分散ストレージ系アルファベットに戻す逆変換機能を有しており、
前記ストレージノードの故障時に他の少なくとも1の前記ストレージノードからデータを受信して故障した前記ストレージノードの代替となる再生成用ストレージノードを形成し、前記分散ストレージ系を更新する再生成機能と、
前記ストレージノードの故障の回数をカウントし、前記回数が上限値に達した時、構成された前記分散ストレージ系をリセットして改めて分散ストレージ系を構成するリセット機能と、
を備える制御部を備えることを特徴とする。

0016

本発明は、最大カウンタ値を導入することで「Information flow graph」を時間的にも空間的にも有限にすることを可能とし、ランダムネットワーク符号化アルゴリズムを用いた再生成符号のネットワーク符号化を実現できる。本発明は、線形ネットワーク符号を用いるため、再生成符号の符号化をベクトルどうしのスカラー積復号化ガウスの掃き出し法を用いることできわめて容易に実現できる。

0017

従って、本発明は、α−βトレードオフ曲線上の任意の点(α,β)を含む分散ストレージのパラメータ(n、k、d、α、β)が与えられた時に「Information flow graph」に対する線形ネットワーク符号で構成できる分散ストレージ制御方法及び分散ストレージシステムを提供することができる。

0018

好ましい形態として、本願発明に係る分散ストレージ制御方法は、前記ストレージノードにおいて、ネットワーク符号化された少なくとも1つの入力データが入力され、ネットワーク符号構成アルゴリズムとしてランダムネットワーク符号化アルゴリズムを適用し、前記入力データに含まれる前記分散データと前記変換手順で変換された前記符号化アルファベットで構成された符号化行列を掛け合わせて後段のノードへ出力する出力データを計算することを特徴とする。

0019

また、本願発明に係る分散ストレージシステムの前記ストレージノードは、ネットワーク符号化された少なくとも1つの入力データが入力され、ネットワーク符号構成アルゴリズムとしてランダムネットワーク符号化アルゴリズムを適用し、前記入力データに含まれる前記分散データと前記情報源ノードが変換した前記符号化アルファベットで構成された符号化行列を掛け合わせて後段のノードへ出力する出力データを計算することを特徴とする。

発明の効果

0020

本発明は、α−βトレードオフ曲線上の任意の点(α,β)を含む分散ストレージのパラメータ(n、k、d、α、β)が与えられた時に「Information flow graph」に対する線形ネットワーク符号で構成できる分散ストレージ制御方法及び分散ストレージシステムを提供することができる。

図面の簡単な説明

0021

分散ストレージシステムのInformation flow graphの例を説明する図である。
分散ストレージシステムのInformation flow graphの例を説明する図である。
非特許文献3に記載されるα‐βトレードオフ曲線の例を説明する図である。
本発明に係る分散ストレージシステムのストレージノードを説明する図である。
本発明に係る分散ストレージシステムの復元ノードを説明する図である。
本発明に係る分散ストレージシステムの情報源ノードの動作(符号化ベクトルの割り当て)を説明する図である。
本発明に係る分散ストレージシステムのストレージノードの動作(符号化ベクトルの割り当て)を説明する図である。
本発明に係る分散ストレージシステムを説明する図である。

実施例

0022

4.開発技術の具体的な説明
4.1 システム概要
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。

0023

図8は、本実施形態の分散ストレージシステム301を説明する図である。分散ストレージシステム301は、
コンテンツデータを保持する情報源ノード5と、
前記コンテンツデータを分散させた分散データを保持する複数のストレージノード10と、
任意のストレージノード10から出力された分散データを受信して前記コンテンツデータを復元する復元ノード20と、
で構成される分散ストレージ系を有する分散ストレージシステムであって、 情報源ノード15が、前記コンテンツデータを符号化する分散ストレージ系アルファベットを、前記分散ストレージ系アルファベットより小さな符号化アルファベットに変換するアルファベット変換処理部16を有し、
復元ノード20が、前記符号化アルファベットを前記分散ストレージ系アルファベットに戻すアルファベット変換処理部24を有しており、
ストレージノード10の故障時に他の少なくとも1のストレージノード10からデータを受信して故障したストレージノード10の代替となる再生成用ストレージノードを形成し、前記分散ストレージ系を更新する再生成機能と、
前記ストレージノードの故障の回数をカウントし、前記回数が上限値に達した時、構成された前記分散ストレージ系をリセットして改めて分散ストレージ系を構成するリセット機能と、
を備える制御部を備えることを特徴とする。

0024

ストレージノード10は、
ネットワーク符号化された少なくとも1つの入力データが入力され、ネットワーク符号構成アルゴリズムとしてランダムネットワーク符号化アルゴリズムを適用し、前記入力データに含まれる前記分散データと情報源ノード15が変換した前記符号化アルファベットで構成された符号化行列を掛け合わせて後段のノードへ出力する出力データを計算する。なお、当該計算は後述する数式(13)の処理である。

0025

分散ストレージシステム301は2節で述べた困難を次のように克服することでα−βトレードオフ曲線上の任意の点を達成する再生成符号を構成する。

0026

困難2に対して:
分散ストレージシステム301は、ノード故障回数毎に加算するカウンタを持ち、ノード故障が最大カウンタ値Tに達したならば、分散ストレージ系をすべてリフレッシュして分散符号化(本実施形態の場合、ネットワーク符号化)を始めから再開する。最大カウンタ値を設定することで、「Inforamtion flow graph」が(時間方向に)無限に延びていくことはなくなった。

0027

困難1に関して:
最大カウンタ値Tを定義することによって故障がT回発生するまでに「Information flow graph」の取り得るトポロジーの数は有限で抑えられる。従って、ネットワーク符号構成アルゴリズムにランダムネットワーク符号化アルゴリズム(非特許文献4を参照。)を適用すれば、ノード間の通信路である各リンク、すなわち「Information Flow Graph」の各辺に適切な符号化ベクトルが割り当てられる確率を、分散ストレージ系アルファベットもしくは符号化アルファベットのバイト長mに関して漸近的に限りなく1に近づけることが示せる。ここで、「適切な符号化ベクトルの割り当て」とは、それによって復元ノード20がいかなるコンテンツデータに対しても正しく復号化可能であるような符号化ベクトルの割り当てのことをいう。そして、「バイト長mに関して漸近的に限りなく1に近づける」とは、後述するように符号化ベクトルの構成は(10)式および(11)式のようにランダムになされるので、バイト長mを十分大きくすれば適切な符号化ベクトルが得られる確率を高めることができるという意味である。

0028

困難3に関して:
分散ストレージシステム301は、予め与えられている分散ストレージ系のアルファベットFqから小さな符号化アルファベットFq〜={0,1,2,・・・,q〜−1}(ただしq〜<q)に変換することによって符号化アルファベットFq〜上でネットワーク符号を構成する。このため、分散ストレージシステム301は、バイト長mが十分長い漸近的な極限では再生成用のデータ量βに比べてネットワーク符号のための符号化ベクトルのデータ量を無視できる。

0029

4.2 具体的な符号構成
分散ストレージシステム301の動作は、
(0)分散ストレージ系アルファベットFqから符号化アルファベットFq〜への変換、
(1)符号化ベクトルの構成、
(2)各リンクにおける符号化および送信データの構成、
(3)DC(復元ノード)における復号化、および符号化アルファベットFq〜から分散ストレージ系のアルファベットFqへの逆変換、
の4ステップよりなる。
図4は、ノードν(ストレージノード10)の構成および動作(ステップ(1)と(2))を説明する図である。図5は、復元ノード20の構成および動作(ステップ(3))を説明する図である。

0030

ステップ(0)[分散ストレージ系のアルファベットから符号化アルファベットへの変換]
分散ストレージ系のアルファベットFq(ただしq=2m)から符号化アルファベットFq〜(ただしq〜=2ε,ε=mδ)への1対1写像ψを次のように定義する。



すなわちx∈Fqを2進表現すれば(b1、・・・、bm)とmビットで表すことができる。写像ψは、この2進表現をmδビット毎に区切ることで



として表現したものである。また、x1、x2∈Fqに対して



として定義する。ここで“*”は文字列の連接を表すものとする。

0031

ステップ(1)[符号化ベクトルの構成]
正の定数0<δ<1が予め与えられているとする。最初に符号化アルファベットを確定させるために,情報源ノード15(情報源ノードs)においてアルファベットのFqからFq〜への変換処理(ただし、q〜=2ε<q=2m)が行われる((3)式及び(5)式を参照)。ランダムネットワーク符号化アルゴリズム実行部12は、入力部11に入力された符号化アルファベットFq〜上の符号化ベクトルを利用し、これらから出射リンクe’上の符号化ベクトルを構成する。対象となる「Information flow graph」は有向非周期グラフなので、情報源ノードsを1番目とした順序付けが可能となる。この順序に従って、各ノードから出射するリンクに対して符号化ベクトルを帰納的に割り当てる。

0032

図6は、情報源ノードsの動作を説明する図である。情報源ノードsに対しては図6のように仮想的に容量Bのリンクが入射しているものと見なす。このとき、sへの入射リンクには符号化ベクトル



が割り当てられる。ここで、[1:B]={1、2、・・・、B}を表すものとする。単位容量あたり1つの符号化ベクトルが割り当てられることに注意しておく。

0033

図7は、ノードνの動作を説明する図である。ノードνにおける容量Reの入射リンクeには符号化ベクトル



が割り当てられているものとする。ここで、



である。ただしTは転置を表す。このデータは符号語と一緒に図4の入力部11に蓄積される。このときノードνの出射リンクe’に対しては



のRe’個の符号化ベクトルが割り当てられることになる。各々の符号化ベクトルは、



として与えられる。ただし、係数



は符号化アルファベットFq〜より一様ランダムに取り出されたものとする。ここで、In(ν)はノードνへ入射するリンクの集合を表す。また「Information flow graph」においてリンク容量Reはαもしくはβの値をとる。

0034

次に符号化を実行するために(10)式で与えられた符号化ベクトルから符号化行列を構成する。以下m1−δ×m1−δ単位行列をIとする。ノードνから出射するリンクe∈Out(ν)上の符号化行列は



として与えられる。ここで、Out(ν)はノードνから出射するリンクの集合を表す。

0035

ステップ(2)[各リンクにおける符号化および送信データの構成]
図4の出力部13の動作を説明する。リンクeにおける符号化を説明する。e∈Out(ν)において、符号化を



によって実行する。このときリンクeが出力する出力データを



とする。(14)式には未知の量xBが見かけ上含まれているが、ノードνが受け取るデータ(入力部11が受信する入力データ)を



とすると、



によって与えられる。

0036

また、ノードνからDCへ送られるデータはノードν’(物理的なノードとしてはノードνと同一であるが再生成のためのデータを受信するノードとして論理的に区別した)より送られてきたデータをそのまま転送するものとする。ここで、q〜=2mδなので



ならば、適切な符号化ベクトルが各リンクに割り当てられる確率が十分大きくなることが示せる。ただし、Tは予め設定された最大カウンタ値である。また符号化ベクトルに関するデータを送信する際のデータ量は(14)式よりBRemδビットであるので、mが十分大きければ符号語のデータ量Remビットに比較して無視できるほど小さくなる。

0037

ステップ(3)[DCにおける復号化]
図5の復元ノード20の動作を説明する。
DC(復元ノード20)がk個のノードνi1、・・・、νikにアクセスするとき、ノードνiaより送られるデータを



と書く。これらのデータは入力部21に蓄積される。ただし、A〜iaは対応する符号化ベクトルを横に並べたものをまとめて行列表現としたものである。このとき復号化は次の一次方程式



解くことにより実行される。一次方程式の求解は掃き出し法実行部22でなされる。ここで、AiaはA〜iaの対応する符号化ベクトルの各要素にm1−δ×m1−δ単位行列を掛けたものである。次に変換処理部24で符号化アルファベットから分散ストレージ系アルファベットへの逆変換処理がなされる。処理内容は,ステップ(0)で説明した変換処理の逆処理である。要するに



は1対1写像であるので一次方程式(19)式の解ψ(xB)から求めるコンテンツデータxBを復元できることになる。

0038

5.発明によって生じる効果
非特許文献1のICN/CCNは次世代コンテンツ配信の有力な方式のひとつである。これは、ネットワーク上のノードに付随するキャッシュローカルなストレージとして再定義することでネットワーク負荷の低減およびエンドユーザに対する実効スループット向上を目指すものである。ICN/CCNの具体的なアーキテクチャは現在のところ研究段階ではあるが、その実現においてはネットワーク上にある種の分散ストレージが実現されることになることは明らかである。分散ストレージでのデータ保存量と再生成のためのデータ転送量は(1)式で示したトレードオフの関係を持つ。従って、もしMSR/MBR点でなければ最適な符号が構成できないようであればネットワーク上の各ノードで保存可能なデータ量に対しても著しい制限が課されることになり、ICN/CCNの最大限パフォーマンスを発揮することが困難となると考えられる。本発明は、α−βトレードオフ曲線上の任意の点における再生成符号の構成を可能とするものであるから、ICN/CCN のキャッシュ(もしくはローカルストレージ)機能を最大限に発揮させることができる。

0039

6.発明のポイント
4.1節で述べたように、本発明は、最大カウンタ値を導入することで「Information flow graph」を時間的にも空間的にも有限にすることが可能となったのがポイントである。これによって、ランダムネットワーク符号化アルゴリズムを使う際に符号化ベクトルの係数をランダムに割り当ててもアルファベットのバイト長が十分大きいならば適切に符号化ベクトルの係数が割り当てられる確率を限りなく1に近くなることを示すことができた。ここで,適切な符号化ベクトルの割り当てとは、それによってDCがいかなるコンテンツデータに対しても正しく復号化可能であるような符号化ベクトルの割り当てのことをいう。また適切な符号化アルファベットへの変換を用いることで、符号化アルファベットを分散ストレージ系のアルファベットよりも小さくとることができるので、再生成のデータ転送の際に、符号化ベクトルの係数の転送にかかるデータ量は再生成用のコンテンツデータに比較して無視できるようにすることができた。

0040

10:ストレージノード
11:入力部
12:ランダムネットワーク符号化アルゴリズム実行部
13:出力部
15:情報源ノード
16:アルファベット変換処理部
20:復元ノード
21:入力部
22:掃き出し法実行部
24:アルファベット変換処理部
30:制御部
31:再生成機能
32:リセット機能
301:分散ストレージシステム

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • オムロン株式会社の「 マッチング処理装置」が 公開されました。( 2019/08/08)

    【課題・解決手段】利活用対象のセンシングデータによる容易なセンサマッチングを行うマッチング処理部50が提供される。マッチング処理部50は、提供側端末11により入力された提供側センシングデータを取得する... 詳細

  • オムロン株式会社の「 検索用データ生成装置」が 公開されました。( 2019/08/08)

    【課題・解決手段】センサの検索精度を向上させることができる検索用データ生成装置が提供される。検索用データ生成装置50は、入力された、センシングデバイス20に関連する検索条件301から検索用データを取得... 詳細

  • 三菱電機株式会社の「 情報処理装置および情報処理方法」が 公開されました。( 2019/08/08)

    【課題・解決手段】情報処理装置(10)は、時系列データである入力データを取得するデータ取得部(101)と、時系列データである学習データから抽出した部分列である複数の学習部分列の中で類似する学習部分列を... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ