(57)【特許請求の範囲】
【請求項１】
データ伝送方法であって、
ピアとシードはそれぞれ、任意のｎ個（ｎは、伝送対象データから分割されたデータ単位の数を表す）の列ベクトルが互いに線形独立であるネットワーク符号化係数テーブルを生成し、
ピアは、全てのシードをトラッカーから知った後、要求されるダウンロード対象データＩＤとネットワーク符号化係数ＩＤとが含まれるダウンロード要求を各シードにそれぞれ送信し、
各シードは、受信されたダウンロード要求に付けられた符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、ネットワーク符号化係数とし、
各シードは、取得されたネットワーク符号化係数により、ダウンロード要求に付けられたデータＩＤにより指示されたデータに含まれるデータ単位に対して、ネットワーク符号化を行って、符号化されたデータ単位をピアに送信し、
ピアは、各シードからのネットワーク符号化されたデータ単位をそれぞれ受信して、ｎ個のデータ単位を受信した後、復号化を行って、ダウンロード対象データを得る、
ことを含むことを特徴とする方法。
【請求項２】
前記ピアとシードがそれぞれネットワーク符号化係数テーブルを生成することは、
ピアとシードがそれぞれ、基数がｎ以上である行列を生成して、前記ネットワーク符号化係数テーブルとする、
ことを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記行列の基数が２ｎである、ことを特徴とする請求項２に記載の方法。
【請求項４】
前記ピアとシードがそれぞれネットワーク符号化係数テーブルを生成することは、
前記ピアとシードが、異なる基数を有してかつ基数がｎ以上である少なくとも２つの行列を生成して、ｎの大きさにより、１つの行列を選択して、ネットワーク符号化係数テーブルとする、
ことを含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記ピアとシードが、異なる基数を有してかつ基数がｎ以上である少なくとも２つの行列を生成して、ｎの大きさにより、１つの行列を選択して、ネットワーク符号化係数テーブルとすることは、
前記ピアとシードがそれぞれ、基数が６４、１２８、２５６、および５１２である４つの行列を生成し、
ダウンロード対象データに含まれるデータ単位の数が３２以下である場合、基数が６４である行列を選択して、ネットワーク符号化係数テーブルとし、
ダウンロード対象データに含まれるデータ単位の数が３２より大きくかつ６４以下である場合、基数が１２８である行列を選択して、ネットワーク符号化係数テーブルとし、
ダウンロード対象データに含まれるデータ単位の数が６４より大きくかつ１２８以下である場合、基数が２５６である行列を選択して、ネットワーク符号化係数テーブルとし、
ダウンロード対象データに含まれるデータ単位の数が１２８より大きくかつ２５６以下である場合、基数が５１２である行列を選択して、ネットワーク符号化係数テーブルとする、
ことを含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記ピアが全てのシードをトラッカーから知ることは、
ピアが、シードリスト要求メッセージをトラッカーへ送信することにより、データを提供できる全てのシードの情報をトラッカーへ要求し、
トラッカーが、シードリスト要求メッセージを受信した後、全てのシードＩＤを含むシードＩＤリストをピアへリターンし、
ピアが、トラッカーからリターンされたシードＩＤリストにより、データを提供する全てのシードを知る、
ことを含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記ネットワーク符号化係数ＩＤは、符号化係数モジュロ値および符号化係数インデックスを含み、
各シードが、受信されたダウンロード要求に付けられた符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、ネットワーク符号化係数とすることは、
各シードが、下記の計算式ｉ＝ｘ×ｋ＋ｙによって、符号化係数として選択される列ベクトルの、ネットワーク符号化係数テーブルにおける番号を算出する、ことを含み、
ここで、ｉはネットワーク符号化係数テーブルにおける列ベクトルの番号であり、ｘは符号化係数モジュロ値であり、ｙは符号化係数インデックスであり、ｋは非負整数である、
ことを特徴とする請求項１に記載の方法。
【請求項８】
ピアから各シードに送信されたダウンロード要求に付けられた符号化係数モジュロ値は同じであるが、符号化係数インデックスは同じではない、
ことを特徴とする請求項７に記載の方法。
【請求項９】
前記ピアが、各シードからのネットワーク符号化されたデータ単位をそれぞれ受信して、ｎ個のデータ単位を受信した後、復号化を行うことは、
ピアが、各シードに送信されたダウンロード要求に付けられたネットワーク符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、各シードの符号化係数としてから、各シードの符号化係数により、それぞれ各シードからのｎ個のデータ単位に対して、復号化を行う、
ことを含むことを特徴とする請求項１に記載の方法。
【請求項１０】
前記ネットワーク符号化係数ＩＤは、符号化係数モジュロ値および符号化係数インデックスを含み、
ピアが、各シードに送信されたダウンロード要求に付けられたネットワーク符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、各シードの符号化係数とすることは、
ピアが、下記の計算式ｉ＝ｘ×ｋ＋ｙによって、各シードで符号化係数として選択される列ベクトルの、ネットワーク符号化係数テーブルにおける番号をそれぞれ算出する、ことを含み、
ここで、ｉはネットワーク符号化係数テーブルにおける列ベクトルの番号であり、ｘとｙは１つのシードの符号化係数モジュロ値と符号化係数インデックスであり、ｋは非負整数である、
ことを特徴とする請求項９に記載の方法。
【請求項１１】
前記データは、１つのファイルであり、前記データ単位は、前記ファイルを分割して得られた少なくとも１つの情報セグメントである、ことを特徴とする請求項１〜１０のいずれか１項に記載の方法。
【請求項１２】
前記データは、１つのファイルを分割して得られた複数の情報セグメントのうちの１つであり、前記データ単位は、該データセグメントに含まれる少なくとも１つのデータブロックである、
ことを特徴とする請求項１〜１０のいずれか１項に記載の方法。
【請求項１３】
ネットワークノードであって、
任意のｎ列（ｎは、伝送対象データから分割されたデータ単位の数を表す）がいずれも線形独立であるネットワーク符号化係数テーブルを生成するネットワーク符号化係数テーブル生成手段と、
データを提供する全てのシードをトラッカーから取得するシード情報取得手段と、
各シードのそれぞれに対して、要求されるダウンロード対象データＩＤとネットワーク符号化係数ＩＤとが少なくとも含まれるダウンロード要求を生成して、ダウンロード要求を相応のシードに送信するダウンロード要求生成手段と、
各シードのそれぞれに対して、生成したダウンロード要求におけるネットワーク符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、各シードのネットワーク符号化係数とする符号化係数生成手段と、
ネットワーク符号化されたデータ単位を各シードから受信して、ｎ個のデータ単位を受信した後、各シードのネットワーク符号化係数により、復号化を行って、ダウンロード対象データを得るデータ受信・復号化手段と、
を含むことを特徴とするネットワークノード。
【請求項１４】
前記ネットワーク符号化係数テーブル生成手段は、
異なる基数を有してかつ基数がｎ以上である少なくとも１つの行列を生成するネットワーク符号化係数行列生成モジュールと、
ｎの大きさにより、生成した少なくとも１つの行列の中から、１つを選択して、ネットワーク符号化係数テーブルとするネットワーク符号化係数テーブル選択モジュールと、
を含むことを特徴とする請求項１３に記載のネットワークノード。
【請求項１５】
ネットワークノードであって、
任意のｎ列（ｎは、伝送対象データから分割されたデータ単位の数を表す）がいずれも線形独立であるネットワーク符号化係数テーブルを生成するネットワーク符号化係数テーブル生成手段と、
ピアからのダウンロード要求を受信するダウンロード要求受信手段と、
受信されたダウンロード要求に付けられたネットワーク符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、ネットワーク符号化係数とする符号化係数生成手段と、
取得されたネットワーク符号化係数により、自身に記憶された、ダウンロード要求に付けられたデータＩＤにより指示されたデータに含まれるデータ単位に対して、ネットワーク符号化を行って、符号化されたデータ単位をピアに送信するネットワーク符号化手段と、
を含むことを特徴とするネットワークノード。
【請求項１６】
前記ネットワーク符号化係数テーブル生成手段は、
異なる基数を有してかつ基数がｎ以上である少なくとも１つの行列を生成するネットワーク符号化係数行列生成モジュールと、
ｎの大きさにより、生成した少なくとも１つの行列の中から、１つを選択して、ネットワーク符号化係数テーブルとするネットワーク符号化係数テーブル選択モジュールと、
を含むことを特徴とする請求項１５に記載のネットワークノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク符号化技術に関し、特に、ネットワーク符号化ベースのデータ伝送方法およびネットワークノードに関する。
【背景技術】
【０００２】
ネットワーク符号化技術は、ネットワーク層でデータパケットに対して符号化を行う技術である。該技術において、ネットワーク内のノードが、受信されたパケットを符号化して、新たなパケットを生成してから転送することが認められている。現在、ネットワーク符号化技術の応用は、主に大規模なファイル配信、即ち、ソースノードまたはサーバから大量な情報をネットワーク内の他のノードに配信するサービス、例えば、ポイントツーポイント（Ｐ２Ｐ）ファイル伝送サービス、または、Ｐ２Ｐストリーミングサービスに集中している。
【０００３】
図１は、ネットワーク符号化の簡単な実例を示している。大規模なファイル配信の応用において、ソースノードによって配信されるファイルが大きすぎる一方、伝送帯域幅が有限であるため、ファイルの伝送前、ソースノードはまず元のファイルをｎ個の元の情報セグメント（Ｓｅｇｍｅｎｔ）Ｓ１，Ｓ２，Ｓ３，…，Ｓｎに分割し、次にこのｎ個の元の情報セグメントに対して線形符号化を行って、新たな情報セグメントＥ１，Ｅ２，…，を生成して、その対応する係数もつけてネットワークで転送する。従って、Ｅｉは全て元の情報セグメントＳ１，Ｓ２，Ｓ３，…，Ｓｎの線形結合であり、その長さが元の情報セグメントと同じであり、区別としては、Ｅｉの各々に一部または全部の元の情報セグメントの情報が付けられていることである。図１において、
0005587735.tif 000002
は、ガロア体（Ｇａｌｏｉｓ  ｆｉｅｌｄ）からランダムに選択した係数であり、それらをそれぞれ元の情報セグメントＳ１，Ｓ２，Ｓ３，…，Ｓｎと乗算して得られる積を加算した後、Ｅ１を得る。即ち、
0005587735.tif 000003
である。Ｅ２の生成方式は類似している。本例において、ネットワークノードＡはファイル配信のソースノードから新たな情報セグメントＥ１とその対応する係数を受信した後、ネットワーク内の他のノードに新たな情報セグメントをブロードキャストまたはマルチキャストする。ネットワークノードＡのキャッシュに情報セグメントＥ２が既に記憶されているため、ネットワークノードＡは情報セグメントＥ１と情報セグメントＥ２に対して線形符号化を行い、新たな情報セグメントＥ３を得た後、ブロードキャストまたはマルチキャストする。ここで、ネットワークノードＡが情報セグメントＥ３を生成する手順は以下の通りである。ネットワークノードＡはガロア体から係数ｃ１およびｃ２をランダムに選択し、次にそれらをそれぞれＥ１およびＥ２と乗算し、得られる積を加算して、Ｅ３を得る。Ｅ１、Ｅ２が両方とも元の情報セグメントＳ１，Ｓ２，Ｓ３，…，Ｓｎの線形符号であるため、Ｅ３もこのｎ個の元の情報セグメントの線形符号となる。説明すべきものとして、ネットワークノードＡは新たなセグメントＥ３をブロードキャストまたはマルチキャストすると共に、Ｅ３に対応する係数ベクトル
0005587735.tif 000004
および
0005587735.tif 000005
もブロードキャストまたはマルチキャストする。ネットワーク内の各ネットワークノードは新たな情報セグメントを受信した後、類似の処理を行う。このようにして、各ネットワークノードは、ｎ個の相関のない情報セグメントおよびその係数を受信しさえすれば、元のファイルを復元することができる。
【０００４】
当業者であれば理解できるものとして、ネットワーク符号化を採用しない場合、ある元の情報セグメント（例えば、ファイルの先頭部分）は、ネットワーク上で、既に多くのネットワークノードに持たれた可能性があって、つまり、比較的高い人気度を有する一方、ある元の情報セグメント（ファイルの末尾部分）は、ネットワーク上で、非常に希少であって、つまり、比較的低い人気度を有する。この場合、ネットワークノードは、自身が既に受信した情報セグメントにより、どの情報セグメントを先に受信するかを判断する必要がある。例えば、希少資源を持つネットワークノードが動的に離れることによるファイルダウンロード失敗を避けるために、ネットワークノードは、一般的に、比較的低い人気度を有する元の情報セグメントを先にダウンロードすることを、選択する。でも、ネットワーク符号化を採用した後、ネットワークにおいて伝播される情報セグメントは、いずれも元の情報セグメントの線形結合であるため、すべての情報セグメントは、同じ人気度を有する。この場合、ネットワークノードは、どの情報セグメントを先に受信する必要があるかを判断する必要がない。それとともに、希少資源の問題もなくなる。このようにして、ネットワークノードが動的に参加しまたは離れることによるほかのネットワークノードへの影響も低減させる。
【０００５】
上記方法において、ネットワークノードは、十分に多くのネットワーク符号化された情報セグメントを受信したことを待って初めて、復号化してファイル全体を得る。従って、上記方法は、ダウンロードしながら視聴する必要があるＰ２Ｐストリーミングサービスに適用されない。そのため、Ｐ２Ｐストリーミングサービスに適用されるネットワーク符号化方法が提供されている。
【０００６】
該方法において、各情報セグメントは、さらに複数の情報ブロック（ｂｌｏｃｋ）に分割されている。Ｐ２Ｐストリーミングサービスに参加するシード（ｓｅｅｄ）は、データの転送前、まず、１つの情報セグメント内の情報ブロック間で、ネットワーク符号化を行う。このようにして、ピア（Ｐｅｅｒ）は、十分に多くのネットワーク符号化された情報ブロックを受信した後、復号化して情報セグメントを得ることができる。このように情報セグメント内の情報ブロック間でネットワーク符号化を行う方法は、複数のシードが同時に１つのピアに、ある情報セグメントを送信することをサポートできる。これにより、ある情報セグメントを伝送する時間を短縮させ、ピアユーザの視聴待ち時間を低減させる。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記２つの方法において、情報セグメントまたは情報ブロックのいずれであるかにかかわらず、その符号化係数は、ランダムに選択されるもの、即ち、ランダムに生成されるものである（このような方法はランダムネットワーク符号化と呼ばれる）。また、ピアで復号化できるために、生成された符号化係数は、情報セグメントまたは情報ブロックと一緒に、伝送しなれけばならない。従って、比較的高い制御オーバヘッド（ＣＯＨ：Ｃｏｎｔｒｏｌ  Ｏｖｅｒｈｅａｄ）を有する。通常、上記方法における制御オーバヘッドの大きさは、下記の数式１によって、算出することができる。
［数式１］
0005587735.tif 000006
ここで、ｑは有限体（ＧＦ）の大きさを表し、ｎは、１つのファイルの分割された情報セグメント数、または、１つの情報セグメントにおける情報ブロック数を表する。例えば、ＧＦの大きさが２５６であって、１つの情報セグメントに１２８個の情報ブロックが含まれる場合、１つの情報セグメントの送信に必要な制御オーバヘッドは、１６．３８４Ｋｂｙｔｅｓに達することになる。
【０００８】
また、ランダムネットワーク符号化の符号化係数がランダムに生成されるものであるため、生成された符号化係数は互いに線形独立であることを、１００パーセント保証できない。従って、たとえピアは既にｎ個の情報セグメントまたは情報ブロックを受信したとしても、正確に復号化できるとは限らない。即ち、復号化失敗の場合がある。上記ネットワーク符号化方法の復号化失敗確率は、下記の数式２によって、算出することができる。
［数式２］
0005587735.tif 000007
ここで、ｑは有限体（ＧＦ）の大きさを表し、ｎは、１つのファイルの分割された情報セグメント数、または、１つの情報セグメントにおける情報ブロック数を表する。数式２から分かるように、有限体の大きさが、復号化失敗確率の決定的な要素である。例えば、有限体の大きさを１２８にする場合、復号化失敗確率は１０−２オーダーとなる。
【０００９】
上記の技術的課題を解決するために、本発明は、データ伝送方法およびネットワークノードを提供している。これにより、制御オーバーヘッドを減少させることができる一方、復号化失敗確率を低減させることもできる。
【課題を解決するための手段】
【００１０】
本発明の実施例に係るデータ伝送方法において、ピアとシードはそれぞれ、任意のｎ個（ｎは、伝送対象データから分割されたデータ単位の数を表す）の列ベクトルが互いに線形独立であるネットワーク符号化係数テーブルを生成し、ピアは、全てのシードをトラッカーから知った後、要求されるダウンロード対象データＩＤとネットワーク符号化係数ＩＤとが含まれるダウンロード要求を各シードにそれぞれ送信し、各シードは、受信されたダウンロード要求に付けられた符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、ネットワーク符号化係数とし、各シードは、取得されたネットワーク符号化係数により、ダウンロード要求に付けられたデータＩＤにより指示されたデータに含まれるデータ単位に対して、ネットワーク符号化を行って、符号化されたデータ単位をピアに送信し、ピアは、各シードからのネットワーク符号化されたデータ単位をそれぞれ受信して、ｎ個のデータ単位を受信した後、復号化を行って、ダウンロード対象データを得る、ことを含む。
【００１１】
ここで、上記ピアとシードがそれぞれネットワーク符号化係数テーブルを生成することは、ピアとシードがそれぞれ、基数がｎ以上である行列を生成して、前記ネットワーク符号化係数テーブルとする、ことを含む。好ましくは、行列の基数が２ｎである。本明細書では、基数がｎ以上である行列を生成する例、即ち、ヴァンデルモンド行列を構成する例が提供されている。
【００１２】
上記ピアとシードがそれぞれネットワーク符号化係数テーブルを生成することは、前記ピアとシードが、異なる基数を有してかつ基数がｎ以上である少なくとも２つの行列を生成して、ｎの大きさにより、１つの行列を選択して、ネットワーク符号化係数テーブルとする、ことを含む。
【００１３】
具体的に、前記ピアとシードがそれぞれ、基数が６４、１２８、２５６、および５１２である４つの行列を生成し、ダウンロード対象データに含まれるデータ単位の数が３２以下である場合、基数が６４である行列を選択して、ネットワーク符号化係数テーブルとし、ダウンロード対象データに含まれるデータ単位の数が３２より大きくかつ６４以下である場合、基数が１２８である行列を選択して、ネットワーク符号化係数テーブルとし、ダウンロード対象データに含まれるデータ単位の数が６４より大きくかつ１２８以下である場合、基数が２５６である行列を選択して、ネットワーク符号化係数テーブルとし、ダウンロード対象データに含まれるデータ単位の数が１２８より大きくかつ２５６以下である場合、基数が５１２である行列を選択して、ネットワーク符号化係数テーブルとする、ことを含んでよい。
【００１４】
上記ピアが全てのシードをトラッカーから知ることは、ピアが、シードリスト要求メッセージをトラッカーへ送信することにより、データを提供できる全てのシードの情報をトラッカーへ要求し、トラッカーが、シードリスト要求メッセージを受信した後、全てのシードＩＤを含むシードＩＤリストをピアへリターンし、ピアが、トラッカーからリターンされたシードＩＤリストにより、データを提供する全てのシードを知る、ことを含む。
【００１５】
上記ネットワーク符号化係数ＩＤは、符号化係数モジュロ値および符号化係数インデックスを含み、各シードは、受信されたダウンロード要求に付けられた符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、ネットワーク符号化係数とすることは、各シードが、下記の計算式ｉ＝ｘ×ｋ＋ｙによって、符号化係数として選択される列ベクトルの、ネットワーク符号化係数テーブルにおける番号を算出する、ことを含み、ここで、ｉはネットワーク符号化係数テーブルにおける列ベクトルの番号であり、ｘは符号化係数モジュロ値であり、ｙは符号化係数インデックスであり、ｋは非負整数である。
【００１６】
ここで、ピアから各シードに送信されたダウンロード要求に付けられた符号化係数モジュロ値は同じであるが、符号化係数インデックスは同じではない。
【００１７】
上記ピアが、各シードからのネットワーク符号化されたデータ単位をそれぞれ受信して、ｎ個のデータ単位を受信した後、復号化を行うことは、ピアが、各シードに送信されたダウンロード要求に付けられたネットワーク符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、各シードの符号化係数としてから、各シードの符号化係数により、それぞれ各シードからのｎ個のデータ単位に対して、復号化を行う、ことを含む。
【００１８】
上記ネットワーク符号化係数ＩＤは、符号化係数モジュロ値および符号化係数インデックスを含み、ピアが、各シードに送信されたダウンロード要求に付けられたネットワーク符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、各シードの符号化係数とすることは、ピアが、下記の計算式ｉ＝ｘ×ｋ＋ｙによって、各シードで符号化係数として選択される列ベクトルの、ネットワーク符号化係数テーブルにおける番号をそれぞれ算出する、ことを含み、ここで、ｉはネットワーク符号化係数テーブルにおける列ベクトルの番号であり、ｘとｙは１つのシードの符号化係数モジュロ値と符号化係数インデックスであり、ｋは非負整数である。
【００１９】
上記データは、１つのファイルであり、前記データ単位は前記ファイルを分割して得られた少なくとも１つの情報セグメントである。あるいは、上記データは、１つのファイルを分割して得られた複数の情報セグメントのうちの１つであり、前記データ単位は、該データセグメントに含まれる少なくとも１つのデータブロックである。
【００２０】
本発明の実施例により提供されているネットワークノードは、任意のｎ列（ｎは、伝送対象データから分割されたデータ単位の数を表す）がいずれも線形独立であるネットワーク符号化係数テーブルを生成するネットワーク符号化係数テーブル生成手段と、データを提供する全てのシードをトラッカーから取得するシード情報取得手段と、各シードのそれぞれに対して、要求されるダウンロード対象データＩＤとネットワーク符号化係数ＩＤとが少なくとも含まれるダウンロード要求を生成して、ダウンロード要求を相応のシードに送信するダウンロード要求生成手段と、各シードのそれぞれに対して、生成したダウンロード要求におけるネットワーク符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、各シードのネットワーク符号化係数とする符号化係数生成手段と、ネットワーク符号化されたデータ単位を各シードから受信して、ｎ個のデータ単位を受信した後、各シードのネットワーク符号化係数により、復号化を行って、ダウンロード対象データを得るデータ受信・復号化手段と、を含む。
【００２１】
ここで、上記ネットワーク符号化係数テーブル生成手段は、異なる基数を有してかつ基数がｎ以上である少なくとも１つの行列を生成するネットワーク符号化係数行列生成モジュールと、ｎの大きさにより、生成した少なくとも１つの行列の中から、１つを選択して、ネットワーク符号化係数テーブルとするネットワーク符号化係数テーブル選択モジュールと、を含む。
【００２２】
本発明の実施例により提供されているほかのネットワークノードは、任意のｎ列（ｎは、伝送対象データから分割されたデータ単位の数を表す）がいずれも線形独立であるネットワーク符号化係数テーブルを生成するネットワーク符号化係数テーブル生成手段と、ピアからのダウンロード要求を受信するダウンロード要求受信手段と、受信されたダウンロード要求に付けられたネットワーク符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、ネットワーク符号化係数とする符号化係数生成手段と、取得されたネットワーク符号化係数により、自身に記憶された、ダウンロード要求に付けられたデータＩＤにより指示されたデータに含まれるデータ単位に対して、ネットワーク符号化を行って、符号化されたデータ単位をピアに送信するネットワーク符号化手段と、を含む。
【００２３】
ここで、上記ネットワーク符号化係数テーブル生成手段は、異なる基数を有してかつ基数がｎ以上である少なくとも１つの行列を生成するネットワーク符号化係数行列生成モジュールと、ｎの大きさにより、生成した少なくとも１つの行列の中から、１つを選択して、ネットワーク符号化係数テーブルとするネットワーク符号化係数テーブル選択モジュールと、を含む。
【発明の効果】
【００２４】
上記データ伝送の過程において、各シードは、符号化係数を、ランダムに選択せず、ピアから送信されたダウンロード要求に付けられた符号化係数モジュロ値および符号化係数インデックスにより選択する。従って、各シードは、ネットワーク符号化されたデータ単位をピアに送信する際、符号化係数をピアに報告する必要がない。これにより、上記データ伝送の過程における制御オーバヘッドを大幅に低減させることができる。
【００２５】
また、各ネットワークノードで生成したネットワーク符号化係数テ―ブルにおける任意のｎ個の列ベクトルがいずれも線形独立であるため、ネットワーク符号化されたデータ単位も線形独立である。このようにして、ピアは、どのシードからデータを受信しても、ｎ個のデータ単位を正確に受信しさえすれば、成功的に復号化して、伝送対象データを得ることができる。
【図面の簡単な説明】
【００２６】
【図１】ネットワーク符号化の簡単な実例を示す図である。
【図２】本発明の実施例によるネットワーク符号化ベースのデータ伝送方法のフローチャートである。
【図３】ネットワーク符号化係数テーブル、および、各シードがネットワーク符号化係数を選択することを示す図である。
【図４】ピアであるネットワークノードの内部構成を示す図である。
【図５】シードであるネットワークノードの内部構成を示す図である。
【図６】本発明の実施例に係る方法および従来のランダムネットワーク符号化方法を採用するとき、制御オーバヘッドが、各情報セグメントに含まれる情報ブロック数につれて変化する曲線である。
【図７】本発明の実施例に係る方法および従来のランダムネットワーク符号化方法を採用するとき、制御オーバヘッドが、ダウンロード対象ファイルに含まれる情報セグメント数につれて変化する曲線である。
【発明を実施するための形態】
【００２７】
上記の課題を解決するために、本発明の実施例は、ネットワーク符号化ベースのデータ伝送方法を提供している。図２に示すように、該方法は、主に以下のステップを含む。
【００２８】
ステップ１０１で、ネットワークにおける各ネットワークノードは、それぞれネットワーク符号化係数テーブル（Ｎｅｔｗｏｒｋ  Ｃｏｄｉｎｇ  Ｔａｂｌｅ）を生成する。
【００２９】
ここで、上記の各ノードは、データを提供するためのシードと、データのダウンロードを必要とするピアと、を含む。
【００３０】
上記ネットワーク符号化係数テーブルは、ネットワーク符号化係数の範囲を限定するものである。各ノードは、ネットワーク符号化係数テーブルにおける少なくとも１つの列ベクトルを選択して、伝送対象データの符号化係数とする。説明すべきものとして、異なるネットワークノードから送信された、ネットワーク符号化されたデータの間が冗長にならないように、各ネットワークノードで生成したネットワーク符号化係数テーブルは、下記の条件を満たす必要がある。即ち、ネットワーク符号化係数テーブルにおける任意のｎ個の列ベクトルは、互いに線形独立であり、ここで、ｎは、伝送対象データから分割されたデータ単位の数、つまり、ネットワーク符号化を行う必要があるデータ単位の数、例えば、Ｐ２Ｐファイル伝送サービスにおけるダウンロード対象ファイルの分割された情報セグメント数、あるいは、Ｐ２Ｐストリーミングサービスにおける各情報セグメント内に含まれる情報ブロック数など、を表す。
【００３１】
上記方法がＰ２Ｐのアプリケーションに応用される場合、各ネットワークノード（データを提供するためのシードと、データのダウンロードを必要とするピアと、を含む）では、Ｐ２Ｐアプリケーションソフトウェアをインストールする時、同時にネットワーク符号化係数テーブルを生成することができる。
【００３２】
ステップ１０２で、ピア（Ｐｅｅｒ）は、トラッカー（Ｔｒａｃｋｅｒ）から、全てのシード（ｓｅｅｄ）を知った後、ダウンロード要求を各シードにそれぞれ送信する。該ダウンロード要求には、要求されるダウンロード対象データＩＤとネットワーク符号化係数ＩＤとが少なくとも含まれる。
【００３３】
具体的に、本ステップにおいて、ピアは、まず、シードリスト要求メッセージをトラッカーへ送信することにより、データを提供できる全てのシードの情報をトラッカーへ要求し、トラッカーは、シードリスト要求メッセージを受信した後、全てのシードのＩＤを含むシードＩＤリストをピアへリターンし、ピアは、トラッカーからリターンされたシードＩＤリストにより、データを提供する全てのシードを知る。
【００３４】
本ステップにおいて、前記ダウンロード対象データは、１つのファイルであってよく、１つのファイルを分割して得られた複数の情報セグメントのうちの１つであってよい。
【００３５】
また、本ステップにおいて、ダウンロード要求に含まれるネットワーク符号化係数ＩＤは、１つのシードがネットワーク符号化を行う際に使用した符号化係数の、ネットワーク符号化係数テーブルにおける位置を指示するものである。好ましくは、ネットワーク符号化係数ＩＤが、符号化係数モジュロ値と符号化係数インデックスとを含んでよい。この場合、各シードで符号化係数として選択される列ベクトルの番号ｉは、下記の計算式ｉ＝ｘ×ｋ＋ｙによって、算出することができる。ここで、ｘは符号化係数モジュロ値であり、ｙは符号化係数インデックスであり、ｋは非負整数（０と正整数とを含む）である。各シードで選択される符号化係数が異なることを保証するために、好ましくは、ピアから各シードに送信されたダウンロード要求に付けられた符号化係数モジュロ値が同じである一方、符号化係数インデックスが同じではない。
【００３６】
ステップ１０３で、各シードは、受信されたダウンロード要求に付けられた符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、ネットワーク符号化係数とする。
【００３７】
上記のように、本ステップにおいて、ネットワーク符号化係数ＩＤが、符号化係数モジュロ値と符号化係数インデックスとを含む場合、各シードは、下記の計算式ｉ＝ｘ×ｋ＋ｙによって、自分のネットワーク符号化係数ベクトルを算出する。ここで、ｘは符号化係数モジュロ値であり、ｙは符号化係数インデックスであり、ｋは非負整数（０と正整数とを含む）である。
【００３８】
ステップ１０４で、各シードは、取得されたネットワーク符号化係数により、ダウンロード要求に付けられたデータＩＤにより指示されたデータに含まれるデータ単位に対して、ネットワーク符号化を行って、符号化されたデータ単位をピアに送信する。
【００３９】
本ステップにおいて、上記データが１つのファイルである場合、上記データ単位は、該ファイルを分割して得られた少なくとも１つの情報セグメントである。上記データが、１つのファイルを分割して得られた複数の情報セグメントのうちの１つである場合、上記データ単位は、該データセグメントに含まれる少なくとも１つのデータブロックである。
【００４０】
ステップ１０５で、ピアは、各シードからのネットワーク符号化されたデータ単位をそれぞれ受信して、ｎ個のデータ単位を受信した後、復号化を行って、ダウンロード対象データを得る。
【００４１】
本ステップにおいても、ピアは、まず、各シードに送信されたダウンロード要求に付けられたネットワーク符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、各シードの符号化係数としてから、各シードの符号化係数により、それぞれ各シードからのデータ単位に対して、復号化を行うことで、ダウンロード対象データを得る。具体的に、ネットワーク符号化係数ＩＤが、符号化係数モジュロ値と符号化係数インデックスとを含む場合、ピアは、下記の計算式ｉ＝ｘ×ｋ＋ｙによって、各シードで符号化係数として選択される列ベクトルの、ネットワーク符号化係数テーブルにおける番号を、それぞれ計算する。ここで、ｉはネットワーク符号化係数テーブルにおける列ベクトルの番号であり、ｘとｙはそれぞれ、１つのシードの符号化係数モジュロ値と符号化係数インデックスであり、ｋは非負整数である。
【００４２】
ここから分かるように、上記方法で使用される符号化係数は、ランダムに生成されたものでもなく、予め固定されたものでもない。従って、上記方法で使用されるネットワーク符号化方法は、半静的ネットワーク符号化と呼ばれてもよい。
【００４３】
上記のデータ伝送の過程において、各シードは、符号化係数を、ランダムに選択せず、ピアから送信されたダウンロード要求に付けられた符号化係数モジュロ値および符号化係数インデックスにより選択する。従って、各シードは、ネットワーク符号化されたデータ単位（情報セグメントあるいは情報ブロック）をピアに送信する際、符号化係数をピアに報告する必要がない。これにより、上記のデータ伝送の過程における制御オーバヘッドを大幅に低減させることができる。
【００４４】
また、各ネットワークノードで生成したネットワーク符号化係数テーブルにおける任意のｎ個の列ベクトルがいずれも線形独立であるため、ネットワーク符号化されたデータ単位（情報セグメントあるいは情報ブロック）も線形独立である。このようにして、ピアは、どのシードからデータを受信しても、ｎ個のデータ単位（情報セグメントあるいは情報ブロック）を正確に受信しさえすれば、成功的に復号化して、伝送対象データを得ることができる。
【００４５】
以下、具体的な例を参照しながら、ネットワーク符号化係数テーブルの生成方法を詳細に説明する。
【００４６】
上記のように、異なるシードから送信された、ネットワーク符号化されたデータの間が冗長にならないように、ネットワーク符号化係数テーブルは、下記の条件を満たす必要がある。即ち、ネットワーク符号化係数テーブルにおける任意のｎ個の列ベクトルはいずれも線形独立であり、ここで、ｎは、伝送対象データに含まれるデータ単位の数、例えば、１つのファイルに含まれる情報セグメント数、あるいは、１つの情報セグメントに含まれる情報ブロック数、を表す。通常、１つの情報セグメントに含まれる情報ブロック数は３２〜２５６の間にある。従って、３２≦ｎ≦２５６と仮定してもよい。ネットワーク符号化係数テーブルは、下記の数式３に示す行列Ａの形式を採用してもよい。
［数式３］
0005587735.tif 000008
【００４７】
上記のように、行列Ａにおける任意のｎ列がいずれも線形独立であれば、即ち、行列Ａの基数（ｃａｒｄｉｎａｌｉｔｙ）がｎであれば、行列Ａにおける列ベクトルを符号化係数として得られたデータ単位（情報セグメントあるいは情報ブロック）の間は、冗長情報を含むことがない。この場合、ピアは、どのシードからデータを受信しても、ｎ個のデータ単位を正確に受信しさえすれば、必ず成功的に復号化して、元のデータを得ることができる。つまり、行列Ａの基数がｎ以上であることを保証しさえすれば、復号化失敗確率を大幅に低減させることができる。好ましくは、ネットワークノードが動的に離れることや、リンクエラーなどの要因を考慮して、Ａの基数をｎより大きいように設定すべきである。好ましくは、Ａの基数を２ｎに設定してもよい。例えば、ｎが２５６である場合、Ａの基数を５１２に設定してもよい。
【００４８】
数学解析により分かるように、Ａの基数がｎであることを保証するための十分な条件は、有限体（ＧＦ）の大きさがｎである、ということである。本明細書では、基数がｎである行列Ａを構成する一例が提供されている。
【００４９】
ヴァンデルモンド（Ｖａｎｄｅｒｍｏｎｄｅ）行列は、典型的な特徴を有する行列であり、下記の数式４で表すことができる。
［数式４］
0005587735.tif 000009
【００５０】
該行列は、下記の特性
0005587735.tif 000010
を満足する。つまり、αｉ≠αｊさえあれば、有限体（ＧＦ）の大きさがｎである場合、ヴァンデルモンド行列から構成されたＡは、基数がｎであることを満足でき、即ち、任意のｎ列の線形独立を満足できる。
【００５１】
実際の応用では、ダウンロード対象データに含まれるデータ単位の数により、有限体の大きさ、即ち、行列Ａの基数を決定してから、任意のｎ個の列ベクトルが互いに線形独立である条件を満足する行列Ａを、上記ヴァンデルモンド行列から構成する。具体的に、各ネットワークノードは、基数がｎ以上である行列をそれぞれ生成して、上記ネットワーク符号化係数テーブルとすることができる。
【００５２】
以下、例を挙げて、本発明の実施例を詳細に説明する。図３は、ネットワーク符号化係数テーブル、および、各シードがネットワーク符号化係数を選択することを示す図である。
【００５３】
まず、ネットワークにおける各ネットワークシードは、図３に示すようなネットワーク符号化係数テーブルを生成する。Ｐｅｅｒは、あるデータをダウンロードする際、まず、トラッカーからフィードバックされたＳｅｅｄＩＤリストにより、適当なシードを選択する。該適当なシードは、Ｓｅｅｄ１、Ｓｅｅｄ２、Ｓｅｅｄ３およびＳｅｅｄ４を含む。次に、Ｐｅｅｒは、各Ｓｅｅｄに対して、符号化係数モジュロ値Ｍｏｄと符号化係数インデックスＩｎｄｅｘをそれぞれ選択する。例えば、Ｓｅｅｄ１に対して選択されたＭｏｄが８であって、Ｉｎｄｅｘが１であり、Ｓｅｅｄ２に対して選択されたＭｏｄが８であって、Ｉｎｄｅｘが２であり、Ｓｅｅｄ３に対して選択されたＭｏｄが８であって、Ｉｎｄｅｘが３であり、Ｓｅｅｄ４に対して選択されたＭｏｄが８であって、Ｉｎｄｅｘが４である。次に、Ｐｅｅｒは、選択された符号化係数モジュロ値および符号化係数インデックスを相応のシードに送信する。その後、Ｓｅｅｄ１、Ｓｅｅｄ２、Ｓｅｅｄ３およびＳｅｅｄ４は、この２つの情報により、それぞれ符号化係数を選択してから、１つのファイルの情報セグメント、あるいは、１つの情報セグメントに含まれる情報ブロックに対して、符号化を行うことができる。例えば、Ｓｅｅｄ１は、ネットワーク符号化係数テーブルにおいて、（番号  ＭＯＤ  ８）が１である列ベクトルを選択して、符号化係数とする（例えば、第１，９，１７．．．列）。Ｓｅｅｄ２は、ネットワーク符号化係数テーブルにおいて、（番号  ＭＯＤ  ８）が２である列ベクトルを選択して、符号化係数とする（例えば、第２，１０，１８．．．列）。Ｓｅｅｄ３は、ネットワーク符号化係数テーブルにおいて、（番号  ＭＯＤ  ８）が３である列ベクトルを選択して、符号化係数とする（例えば、第３，１１，１９．．．列）。Ｓｅｅｄ４は、ネットワーク符号化係数テーブルにおいて、（番号  ＭＯＤ  ８）が４である列ベクトルを選択して、符号化係数とする（例えば、第４，１２，２０．．．列）。上記の規則により符号化係数を選択すると、各Ｓｅｅｄが同じ符号化係数を使用することなく、かつ、各Ｓｅｅｄで使用される符号化係数が線形独立であると保証できる。
【００５４】
ネットワークノードの演算量をできるだけ減少して、上記方法の性能をさらに最適化するために、ダウンロード対象データに含まれるデータ単位の数により、ネットワーク符号化係数行列の基数、つまり、有限体（ＧＦ）の大きさを調整し、さらに、生成したネットワーク符号化係数テーブルの大きさを動的に調整してもよい。例えば、ダウンロード対象データに含まれるデータ単位が比較的少ない場合、基数が比較的小さい行列を生成して、ネットワーク符号化係数テーブルとしてもよい。実際の応用では、ネットワークノードは、異なる基数を有してかつ基数がｎ以上である複数の行列を予め生成して、候補のネットワーク符号化係数テーブルとし、ダウンロード対象データに含まれるデータ単位の数により、全ての候補のネットワーク符号化係数テーブルから、１つの適当なネットワーク符号化係数テーブルを選択してもよい。それから、選択されたネットワーク符号化係数テーブルにより、符号化係数を得る。例えば、ネットワークにおける各ノードは、基数が６４、１２８、２５６、および５１２である４つの行列をそれぞれ生成する。唯一違うのは、この４つの行列の有限体の大きさが、それぞれＧＦ（６４）、ＧＦ（１２８）、ＧＦ（２５６）、およびＧＦ（５１２）である、という点である。シードは、ピアからのダウンロード要求を受信した後、ダウンロード対象データに含まれるデータ単位の数が３２以下である場合、基数が６４である行列を選択してネットワーク符号化係数テーブルとし、ダウンロード対象データに含まれるデータ単位の数が３２より大きくかつ６４以下である場合、基数が１２８である行列を選択してネットワーク符号化係数テーブルとし、ダウンロード対象データに含まれるデータ単位の数が６４より大きくかつ１２８以下である場合、基数が２５６である行列を選択してネットワーク符号化係数テーブルとし、ダウンロード対象データに含まれるデータ単位の数が１２８より大きくかつ２５６以下である場合、基数が５１２である行列を選択してネットワーク符号化係数テーブルとする。当業者であれば理解できるものとして、上記方法において、ダウンロード対象データに含まれるデータ単位の数が比較的少ない場合、ネットワークノードの演算量をさらに低減させることができる。これにより、ネットワークノードの性能を最適化する目的を達成できる。
【００５５】
上記方法以外、本発明は、また、ピアであるネットワークノードと、シードであるネットワークノードとの内部構成を提供している。
【００５６】
ここで、図４は、ピアであるネットワークノードの内部構成を示す。図４に示すように、該ネットワークノードは、主に、任意のｎ列（ｎは、伝送対象データから分割されたデータ単位の数を表す）がいずれも線形独立であるネットワーク符号化係数テーブルを作成する伝送対象ネットワーク符号化係数テーブル生成手段と、データを提供する全てのシードをトラッカーから取得するシード情報取得手段と、各シードのそれぞれに対して、要求されるダウンロード対象データＩＤとネットワーク符号化係数ＩＤとが少なくとも含まれるダウンロード要求を生成して、ダウンロード要求を相応のシードに送信するダウンロード対象ダウンロード要求生成手段と、各シードのそれぞれに対して、生成したダウンロード要求におけるネットワーク符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、各シードのネットワーク符号化係数とする符号化係数生成手段と、ネットワーク符号化されたデータ単位を各シードから受信して、ｎ個のデータ単位を受信した後、各シードのネットワーク符号化係数により、復号化を行って、ダウンロード対象データを得るデータ受信・復号化手段と、を含む。
【００５７】
さらに、上記ネットワーク符号化係数テーブル生成手段は、異なる基数を有してかつ基数がｎ以上である少なくとも１つの行列を生成するネットワーク符号化係数行列生成モジュールと、ｎの大きさにより、生成した少なくとも１つの行列の中から、１つを選択して、ネットワーク符号化係数テーブルとするネットワーク符号化係数テーブル選択モジュールと、を含んでよい。
【００５８】
図５は、シードであるネットワークノードの内部構成を示す。図５に示すように、該ネットワークノードは、主に、任意のｎ列（ｎは、伝送対象データから分割されたデータ単位の数を表す）がいずれも線形独立であるネットワーク符号化係数テーブルを作成するネットワーク符号化係数テーブル生成手段と、ピアからのダウンロード要求を受信するダウンロード要求受信手段と、受信されたダウンロード要求に付けられたネットワーク符号化係数ＩＤにより、自身で生成したネットワーク符号化係数テーブルから、相応の列ベクトルを取得して、ネットワーク符号化係数とする符号化係数生成手段と、取得されたネットワーク符号化係数により、自身に記憶された、ダウンロード要求に付けられたデータＩＤにより指示されたデータに含まれるデータ単位に対して、ネットワーク符号化を行って、符号化されたデータ単位をピアに送信するネットワーク符号化手段と、を含む。
【００５９】
さらに、上記ネットワーク符号化係数テーブル生成手段は、異なる基数を有してかつ基数がｎ以上である少なくとも１つの行列を生成するネットワーク符号化係数行列生成モジュールと、ｎの大きさにより、生成した少なくとも１つの行列の中から、１つを選択して、ネットワーク符号化係数テーブルとするネットワーク符号化係数テーブル選択モジュールと、を含んでもよい。
【００６０】
以下、シミュレーションにより、本発明に係る方法と従来のランダムネットワーク符号化方法とを比較する。仮に、ネットワークにおけるネットワークノードの数は２５０であり、ダウンロード対象ファイルは５０〜２００個の情報セグメントを含み、各情報セグメントは３２〜２５６個の情報ブロックを含むと仮定する。Ｐ２Ｐストリーミングサービスを応用して、ビデオファイルを視聴する際、各ネットワークノードは、２０個の情報セグメントをバッファリングする必要がある。トラッカーは多くとも８個のピアのアクセスを許容し、各ネットワークノードは多くとも４個のピアのアクセスを許容し、各ネットワークノードは多くとも４個のピアのシードになることを許容する。上記の場合で、図６は、本発明の実施例に係る方法および従来のランダムネットワーク符号化方法を採用するとき、制御オーバヘッドが、各情報セグメントに含まれる情報ブロック数につれて変化する曲線である。図７は、本発明の実施例に係る方法および従来のランダムネットワーク符号化方法を採用するとき、制御オーバヘッドが、ダウンロード対象ファイルに含まれる情報セグメント数につれて変化する曲線である。図６と図７において、四角印の曲線は、本発明の実施例に係る方法を採用するときの制御オーバヘッドの変化曲線であるが、丸印の曲線は、従来のランダムネットワーク符号化を採用するときの制御オーバヘッドの変化曲線である。上記の曲線から分かるように、従来のランダムネットワーク符号化方法と比べて、本発明の実施例に係る方法は、制御オーバヘッドを大幅に低減させる。例えば、ランダムネットワーク符号化方法によれば、制御パケットのオーバヘッドは１０％前後であるが、本発明の実施例に係る方法によれば、制御パケットのオーバヘッドは０．１％未満になる。
【００６１】
また、上記のように、本発明の実施例で生成したネットワーク符号化係数テーブルの任意のｎ列がいずれも線形独立であるため、ピアは、どのシードからデータを受信しても、ｎ個のデータ単位を正確に受信しさえすれば、必ず成功的に復号化して、元のデータを得ることができる。これにより、復号化失敗確率を大幅に低減させる。
【００６２】
上記は、本発明の好ましい実施例にすぎず、本発明の保護範囲を限定するものではない。本発明の精神と原則内で行われる種々の修正、均等置換え、改善などは全て本発明の保護範囲内に含まれるべきである。
【図１】
0005587735.tif 000011
【図２】
0005587735.tif 000012
【図３】
0005587735.tif 000013
【図４】
0005587735.tif 000014
【図５】
0005587735.tif 000015
【図６】
0005587735.tif 000016
【図７】
0005587735.tif 000017