(57)【要約】【課題】処理負荷が小さいネットワーク符号型の伝送システム、伝送方法及び伝送プログラムを提供すること。【解決手段】送信ノード１０は、伝送データのパケット内に、当該パケットの符号化状態を識別するインデックス領域を含め、中間ノード２０は、複数の互いに異なるパケットを受信した場合、当該複数のパケットを排他的論理和した結果を、下流ノードへ転送し、受信ノード３０は、複数経路から受信した複数のパケットを、インデックス領域が所定の状態となる組み合わせで排他的論理和することによって、符号化前のパケットを復元する。【選択図】図１
2015041863.tif 000002
【特許請求の範囲】
【請求項１】
送信ノードから受信ノードへ至る経路の中間ノードでパケットの符号化を行うネットワーク符号型の伝送システムであって、
前記送信ノードは、伝送データのパケット内に、当該パケットの符号化状態を識別するインデックス領域を含め、
前記中間ノードは、複数の互いに異なるパケットを受信した場合、当該複数のパケットを排他的論理和した結果を、下流ノードへ転送し、
前記受信ノードは、複数経路から受信した複数のパケットを、前記インデックス領域が所定の状態となる組み合わせで排他的論理和することによって、符号化前のパケットを復元する伝送システム。
【請求項２】
前記インデックス領域は、複数のパケットのうち、いずれのパケットを排他的論理和したものであるかを示すビット列であり、
前記所定の状態は、前記インデックス領域のハミング重みが１の状態である請求項１に記載の伝送システム。
【請求項３】
前記送信ノードは、パケット内に、前記伝送データの検証値を含め、
前記受信ノードは、前記符号化前のパケットを復元した際に、前記検証値によって前記伝送データの正当性を検証する請求項１又は請求項２に記載の伝送システム。
【請求項４】
前記受信ノードは、前記正当性が検証されたパケットを保存し、新たに受信するパケットとの演算に利用する請求項３に記載の伝送システム。
【請求項５】
前記受信ノードは、前記インデックス領域が所定の状態にならない場合、復元すべきパケットが符号化されている受信パケットを保存する請求項１から請求項４のいずれかに記載の伝送システム。
【請求項６】
送信ノードから受信ノードへ至る経路の中間ノードでパケットの符号化を行うネットワーク符号型の伝送方法であって、
前記送信ノードが、伝送データのパケット内に当該パケットの符号化状態を識別するインデックス領域を含めて送信する送信ステップと、
前記中間ノードが、複数の互いに異なるパケットを排他的論理和した結果を、下流ノードへ転送する符号化ステップと、
前記受信ノードが、複数経路から受信した複数のパケットを、前記インデックス領域が所定の状態となる組み合わせで排他的論理和することによって、符号化前のパケットを復元する復元ステップと、を含む伝送方法。
【請求項７】
送信ノードから受信ノードへ至る経路の中間ノードでパケットの符号化を行わせるためのネットワーク符号型の伝送プログラムであって、
前記送信ノードに、伝送データのパケット内に当該パケットの符号化状態を識別するインデックス領域を含めて送信する送信ステップを実行させ、
前記中間ノードに、複数の互いに異なるパケットを排他的論理和した結果を、下流ノードへ転送する符号化ステップを実行させ、
前記受信ノードに、複数経路から受信した複数のパケットを、前記インデックス領域が所定の状態となる組み合わせで排他的論理和することによって、符号化前のパケットを復元する復元ステップを実行させるための伝送プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク符号型の伝送システム、伝送方法及び伝送プログラムに関する。
【背景技術】
【０００２】
従来、サーバからホスト端末へのソフトウェアのダウンロード等、ネットワーク内でデータが送受信される場合に、データの汚染を防いで安全に伝送するシステムが提案されている。
例えば、非特許文献１には、排他的論理和（ＸＯＲ）を用い、汚染攻撃に耐性のあるネットワーク符号化方式が提案されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｚ．  Ｙｕ，  Ｙ．  Ｗｅｉ，  Ｂ．  Ｒａｍｋｕｍａｒ，  ａｎｄ  Ｙ．  Ｇｕａｎ，  “Ａｎ  Ｅｆｆｉｃｉｅｎｔ  Ｓｃｈｅｍｅ  ｆｏｒ  Ｓｅｃｕｒｉｎｇ  ＸＯＲ  Ｎｅｔｗｏｒｋ  Ｃｏｄｉｎｇ  ａｇａｉｎｓｔ  Ｐｏｌｌｕｔｉｏｎ  Ａｔｔａｃｋｓ”，  ｉｎ  Ｐｒｏｃ．  ＩＮＦＯＣＯＭ，  ２００９，  ｐｐ．４０６−４１４．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、前述の技術では、符号化及び復元のための計算量が著しく大きく、さらに、伝送するに従って、パケットサイズが大きくなるという課題があった。
【０００５】
本発明は、処理負荷が小さいネットワーク符号型の伝送システム、伝送方法及び伝送プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明に係る伝送システムは、送信ノードから受信ノードへ至る経路の中間ノードでパケットの符号化を行うネットワーク符号型の伝送システムであって、前記送信ノードは、伝送データのパケット内に、当該パケットの符号化状態を識別するインデックス領域を含め、前記中間ノードは、複数の互いに異なるパケットを受信した場合、当該複数のパケットを排他的論理和した結果を、下流ノードへ転送し、前記受信ノードは、複数経路から受信した複数のパケットを、前記インデックス領域が所定の状態となる組み合わせで排他的論理和することによって、符号化前のパケットを復元する。
【０００７】
前記インデックス領域は、複数のパケットのうち、いずれのパケットを排他的論理和したものであるかを示すビット列であり、前記所定の状態は、前記インデックス領域のハミング重みが１の状態であってもよい。
【０００８】
前記送信ノードは、パケット内に、前記伝送データの検証値を含め、前記受信ノードは、前記符号化前のパケットを復元した際に、前記検証値によって前記伝送データの正当性を検証してもよい。
【０００９】
前記受信ノードは、前記正当性が検証されたパケットを保存し、新たに受信するパケットとの演算に利用してもよい。
【００１０】
前記受信ノードは、前記インデックス領域が所定の状態にならない場合、復元すべきパケットが符号化されている受信パケットを保存してもよい。
【００１１】
本発明に係る伝送方法は、送信ノードから受信ノードへ至る経路の中間ノードでパケットの符号化を行うネットワーク符号型の伝送方法であって、前記送信ノードが、伝送データのパケット内に当該パケットの符号化状態を識別するインデックス領域を含めて送信する送信ステップと、前記中間ノードが、複数の互いに異なるパケットを排他的論理和した結果を、下流ノードへ転送する符号化ステップと、前記受信ノードが、複数経路から受信した複数のパケットを、前記インデックス領域が所定の状態となる組み合わせで排他的論理和することによって、符号化前のパケットを復元する復元ステップと、を含む。
【００１２】
本発明に係る伝送プログラムは、送信ノードから受信ノードへ至る経路の中間ノードでパケットの符号化を行わせるためのネットワーク符号型の伝送プログラムであって、前記送信ノードに、伝送データのパケット内に当該パケットの符号化状態を識別するインデックス領域を含めて送信する送信ステップを実行させ、前記中間ノードに、複数の互いに異なるパケットを排他的論理和した結果を、下流ノードへ転送する符号化ステップを実行させ、前記受信ノードに、複数経路から受信した複数のパケットを、前記インデックス領域が所定の状態となる組み合わせで排他的論理和することによって、符号化前のパケットを復元する復元ステップを実行させる。
【発明の効果】
【００１３】
本発明によれば、ネットワーク符号化において処理負荷が軽減される。
【図面の簡単な説明】
【００１４】
【図１】実施形態に係る伝送システムによる伝送方法の一例を示す図である。
【図２】実施形態に係るパケットのユーザデータ領域の構造を示す図である。
【図３】実施形態に係る受信ノードにおける第１の復元処理を示すフローチャートである。
【図４】実施形態に係る受信ノードにおける第２の復元処理を示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態の一例について説明する。
本実施形態の伝送システム１は、送信ノード１０から送信されるパケット群を、中間ノード２０を経由して受信ノード３０で受信するシステムである。伝送システム１は、排他的論理和（ＸＯＲ）を用いたネットワーク符号型の伝送方式を採用し、送信ノード１０から受信ノード３０へ至る経路の中間ノード２０でパケットの符号化を行う。
【００１６】
図１は、本実施形態に係る伝送システム１による伝送方法の一例を示す図である。
この例では、送信ノード１０ａからパケットＡが、送信ノード１０ｂからパケットＢが送信される。
【００１７】
中間ノード２０ａは、パケットＡ及びパケットＢを受信すると、両者のＸＯＲを演算し、符号化されたパケット（Ａ＋Ｂ）を送信する。以下、「＋」はバイナリ上のＸＯＲ演算を表す。
中間ノード２０ｂは、パケット（Ａ＋Ｂ）のみを受信し、演算を行わずに転送する。
【００１８】
受信ノード３０ａは、パケットＡ及びパケット（Ａ＋Ｂ）を受信する。このとき、受信ノード３０ａは、パケットＡ及びパケット（Ａ＋Ｂ）のＸＯＲを演算することにより、パケットＢを復元できる。
受信ノード３０ｂは、パケットＢ及びパケット（Ａ＋Ｂ）を受信する。このとき、受信ノード３０ｂは、パケットＢ及びパケット（Ａ＋Ｂ）のＸＯＲを演算することにより、パケットＡを復元できる。
【００１９】
図２は、本実施形態に係るパケットのユーザデータ領域の構造を示す図である。
送信ノード１０で生成されてネットワーク内で送受信されるパケットは、伝送データの他に、当該パケットの符号化状態を識別するインデックス領域（Ｃｏｅｆｆｉｃｉｅｎｔ）と、伝送データの検証値（Ａｃｃｕｍｕｌａｔｏｒ  ｍｅｍｂｅｒｓｈｉｐ）を含む。
【００２０】
前記中間ノード２０は、複数の互いに異なるパケットを受信した場合、これら複数のパケットをＸＯＲ演算した結果を、下流ノードへ転送する。
中間ノード２０では、Ｃｏｅｆｆｉｃｉｅｎｔ、Ａｃｃｕｍｕｌａｔｏｒ  ｍｅｍｂｅｒｓｈｉｐ、及び伝送データの全てのビットがＸＯＲ演算される。
【００２１】
例えば、図２のパケット１（Ｐ１）と、パケット２（Ｐ２）とをＸＯＲ演算すると（Ｐ１＋Ｐ２）、ビット演算によりパケット長は変わらず、Ｃｏｅｆｆｉｃｉｅｎｔ、Ａｃｃｕｍｕｌａｔｏｒ  ｍｅｍｂｅｒｓｈｉｐ、及び伝送データが符号化される。
【００２２】
Ｃｏｅｆｆｉｃｉｅｎｔは、複数のパケットのうち、いずれのパケットをＸＯＲ演算したものであるかを示すビット列である。
例えば、Ｐ１のＣｏｅｆｆｉｃｉｅｎｔは「１１０１１０」であり、６個のパケットそれぞれに対応するビットのうち、「１」となっているビットに対応する４つのパケットがＸＯＲ演算された結果である。また、「Ｐ１＋Ｐ２」の演算により、ハミング重みが２に減少し、符号化前の２つのパケットをＸＯＲ演算した結果に変換される。
【００２３】
Ａｃｃｕｍｕｌａｔｏｒ  ｍｅｍｂｅｒｓｈｉｐは、受信ノード３０においてパケットの正当性を検証するための値であり、例えば、伝送データのハッシュ値が送信ノード１０により格納される。この場合、受信ノード３０は、ハッシュ演算の結果とＡｃｃｕｍｕｌａｔｏｒ  ｍｅｍｂｅｒｓｈｉｐとを比較し、伝送データの正当性を検証する。また、受信ノード３０は、例えば、Ｍｅｒｋｌｅ  Ｔｒｅｅ又はＢｌｏｏｍ  Ｆｉｌｔｅｒを用いた方式により検証を行ってもよい。
【００２４】
受信ノード３０は、複数経路から受信した複数のパケットを、Ｃｏｅｆｆｉｃｉｅｎｔが所定の状態となる組み合わせでＸＯＲ演算することによって、符号化前のパケットを復元する。ここで、所定の状態とは、Ｃｏｅｆｆｉｃｉｅｎｔのハミング重みが１、すなわち「１」のビットが１つの状態である。
受信ノード３０は、ハミング重みが１となり符号化前の元パケットが復元された際に、Ａｃｃｕｍｕｌａｔｏｒ  ｍｅｍｂｅｒｓｈｉｐを用いてパケットの正当性を検証する。
【００２５】
受信ノード３０は、正当性が検証されたパケットを保存し、新たに受信するパケットとのＸＯＲ演算に利用する。
また、受信ノード３０は、Ｃｏｅｆｆｉｃｉｅｎｔのハミング重みが１にならない場合、復元すべきパケットが符号化されている受信パケットを保存し、次回に利用する。
【００２６】
図３は、本実施形態に係る受信ノード３０における第１の復元処理を示すフローチャートである。
ステップＳ１において、受信ノード３０は、ネットワークから新たにパケットを受信する。
【００２７】
ステップＳ２において、受信ノード３０は、パケットを正常に受信したか否かを判定する。この判定がＹＥＳの場合、処理はステップＳ３に移り、判定がＮＯの場合、処理はステップＳ７に移る。
【００２８】
ステップＳ３において、受信ノード３０は、既に記憶済みのパケットとＸＯＲ演算を行うことにより、受信したパケットに含まれるＣｏｅｆｆｉｃｉｅｎｔのハミング重みを減少させる。
【００２９】
ステップＳ４において、受信ノード３０は、ハミング重みが１になったか否かを判定する。この判定がＹＥＳの場合、処理はステップＳ５に移り、判定がＮＯの場合、処理はステップＳ７に移る。
【００３０】
ステップＳ５において、受信ノード３０は、ハミング重みが１となって復元されたパケットのＡｃｃｕｍｕｌａｔｏｒ  ｍｅｍｂｅｒｓｈｉｐを用いて、伝送データの正当であるか否かを判定する。この判定がＹＥＳの場合、処理はステップＳ６に移り、判定がＮＯの場合、処理はステップＳ７に移る。
【００３１】
ステップＳ６において、受信ノード３０は、ステップＳ５で正当性が認証されたパケットを記憶する。
【００３２】
図４は、本実施形態に係る受信ノード３０における第２の復元処理を示すフローチャートである。本処理は、第１の復元処理の効率を更に向上させるため、第１の復元処理に代えて実行される。
【００３３】
ステップＳ１１において、受信ノード３０は、ネットワークから新たにパケットを受信する。
【００３４】
ステップＳ１２において、受信ノード３０は、パケットを正常に受信したか否かを判定する。この判定がＹＥＳの場合、処理はステップＳ１３に移り、判定がＮＯの場合、処理はステップＳ２１に移る。
【００３５】
ステップＳ１３において、受信ノード３０は、正しく受信したパケットを一時記憶領域Ｔ１に記憶する。
【００３６】
ステップＳ１４において、受信ノード３０は、Ｔ１が空か否かを判定する。この判定がＹＥＳの場合、処理はステップＳ２２に移り、判定がＮＯの場合、処理はステップＳ１５に移る。
【００３７】
ステップＳ１５において、受信ノード３０は、Ｔ１からパケットを１つ取り出し、取り出したパケットをＴ１から削除する。
【００３８】
ステップＳ１６において、受信ノード３０は、認証されて既に記憶済みのパケットとＸＯＲ演算を行うことにより、受信したパケットに含まれるＣｏｅｆｆｉｃｉｅｎｔのハミング重みを減少させる。
【００３９】
ステップＳ１７において、受信ノード３０は、ハミング重みが１になったか否かを判定する。この判定がＹＥＳの場合、処理はステップＳ１８に移り、判定がＮＯの場合、処理はステップＳ２０に移る。
【００４０】
ステップＳ１８において、受信ノード３０は、ハミング重みが１となって復元されたパケットのＡｃｃｕｍｕｌａｔｏｒ  ｍｅｍｂｅｒｓｈｉｐを用いて、伝送データの正当であるか否かを判定する。この判定がＹＥＳの場合、処理はステップＳ１９に移り、判定がＮＯの場合、処理はステップＳ２１に移る。
【００４１】
ステップＳ１９において、受信ノード３０は、ステップＳ１８で正当性が認証されたパケットを記憶し、処理はステップＳ１４に戻る。
【００４２】
ステップＳ２０において、受信ノード３０は、ハミング重みが１とならず符号化された状態のパケットを一時記憶領域Ｔ２に記憶し、処理はステップＳ１４に戻る。
【００４３】
ステップＳ２１において、受信ノード３０は、ステップＳ１２で正しく受信できなかったパケット、及びステップＳ１８で正当でないと判定されたパケットを破棄する。
【００４４】
ステップＳ２２において、受信ノード３０は、Ｔ１のパケットを全て処理したので、ステップＳ２０でＴ２に記憶されたパケットを、次回に処理させるためにＴ１へ移動する。
【００４５】
なお、第１の復元処理又は第２の復元処理において、ハミング重みを減少させるためにＸＯＲ演算を行うパケットの組み合わせは、既存の手法が利用可能であり、例えばガウスの消去法により効率的に実行できる。
【００４６】
また、受信ノード３０は、パケットを復元するために、信頼出来るパケットを前もって１つ以上取得していることが望ましい。この信頼出来るパケットは、例えば、送信ノード１０から直接配布されてもよい。
【００４７】
以上のように、本実施形態によれば、伝送システム１は、符号化の際にパケット長を変化させない。さらに、Ｃｏｅｆｆｉｃｉｅｎｔによって符号化状態が判別されるので、ＸＯＲ演算のみで符号化及び復元が可能である。したがって、ネットワーク符号化における処理負荷が軽減される。
【００４８】
また、Ｃｏｅｆｆｉｃｉｅｎｔは、ＸＯＲ演算されたパケットを対象ビットの０／１で示すため、演算後も正しく対象パケットを示す。したがって、受信ノード３０は、ハミング重みが１の状態で元のパケットが復元されたことを容易に判定できる。
【００４９】
また、パケット内に伝送データの検証値を含むことにより、受信ノード３０は、復元したパケットの正当性を容易に検証できる。
【００５０】
また、受信ノード３０は、正当性が検証されたパケット、及び復元できなかったパケットを保存することにより、新たに受信するパケットとの演算に再利用できる。これにより、受信ノード３０は、伝送路における順序逆転又は遅延等が発生した場合にも、効率的に復元処理を行える。
【００５１】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。
【００５２】
伝送システム１の伝送方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、各ノードの情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。
【符号の説明】
【００５３】
１  伝送システム
１０、１０ａ、１０ｂ  送信ノード
２０、２０ａ、２０ｂ  中間ノード
３０、３０ａ、３０ｂ  受信ノード
【図１】
2015041863.tif 000003
【図２】
2015041863.tif 000004
【図３】
2015041863.tif 000005
【図４】
2015041863.tif 000006