(57)【要約】【課題】コンテンツダウンロードにおけるスループットを向上できるネットワーク符号化装置、ネットワーク符号化方法及びネットワーク符号化プログラムを提供すること。【解決手段】中継ノード２０は、コンテンツを構成するＣｈｕｎｋのうち、送信した１又は複数のＣｈｕｎｋの線形結合による符号化キャッシュを記憶するキャッシュ記憶部２１と、Ｃｈｕｎｋのいずれかを要求するＩｎｔｅｒｅｓｔパケットを受信した際に、要求されたＣｈｕｎｋを含む符号化キャッシュがキャッシュ記憶部２１に存在しない場合、要求されたＣｈｕｎｋ及び要求元を識別するデータを記憶するリクエスト記憶部２４と、複数の隣接ノードに対して、Ｉｎｔｅｒｅｓｔパケットを転送する転送部２６と、を備える。【選択図】図２
2015076833.tif 000002
【特許請求の範囲】
【請求項１】
コンテンツを構成する断片のうち、送信した１又は複数の断片の線形結合による符号化キャッシュを記憶するキャッシュ記憶部と、
前記断片のいずれかを要求する要求パケットを受信した際に、当該要求された断片を含む符号化キャッシュが前記キャッシュ記憶部に存在しない場合、当該要求された断片及び要求元を識別するデータを記憶するリクエスト記憶部と、
複数の隣接ノードに対して、前記要求パケットを転送する転送部と、を備えるネットワーク符号化装置。
【請求項２】
前記断片のいずれかを要求する要求パケットを受信した際に、当該要求された断片を含む符号化キャッシュが前記キャッシュ記憶部に存在する場合、当該要求された断片を含む１又は複数の符号化キャッシュに対して、ランダム係数に基づく再符号化を行い、当該再符号化したデータを含むデータパケットを、要求元へ送信する符号化部を備える請求項１に記載のネットワーク符号化装置。
【請求項３】
前記符号化部は、データパケットを受信した場合、当該データパケットに含まれている前記要求された断片を含む符号化キャッシュ、及び前記キャッシュ記憶部に記憶されている前記コンテンツを構成するいずれかの断片を含む符号化キャッシュに対して再符号化を行い、当該再符号化したデータを含むデータパケットを、要求元へ送信する請求項２に記載のネットワーク符号化装置。
【請求項４】
前記キャッシュ記憶部は、前記受信したデータパケットに基づいて再符号化されたデータを、新たな符号化キャッシュとして記憶する請求項３に記載のネットワーク符号化装置。
【請求項５】
前記キャッシュ記憶部は、記憶する符号化キャッシュが所定の閾値を超える場合、線形従属な符号化キャッシュを優先して削除する請求項１から請求項４のいずれかに記載のネットワーク符号化装置。
【請求項６】
前記キャッシュ記憶部は、記憶している符号化キャッシュの利用率に基づいて、削除対象を決定する請求項５に記載のネットワーク符号化装置。
【請求項７】
コンテンツを伝送する中継ノードが、
前記コンテンツを構成する断片のうち、送信した１又は複数の断片の線形結合による符号化キャッシュを記憶するステップと、
前記断片のいずれかを要求する要求パケットを受信した際に、当該要求された断片を含む符号化キャッシュを記憶していない場合、当該要求された断片及び要求元を識別するデータを記憶するステップと、
複数の隣接ノードに対して、前記要求パケットを転送するステップと、を実行するネットワーク符号化方法。
【請求項８】
コンテンツを伝送する中継ノードに、
前記コンテンツを構成する断片のうち、送信した１又は複数の断片の線形結合による符号化キャッシュを記憶するステップと、
前記断片のいずれかを要求する要求パケットを受信した際に、当該要求された断片を含む符号化キャッシュを記憶していない場合、当該要求された断片及び要求元を識別するデータを記憶するステップと、
複数の隣接ノードに対して、前記要求パケットを転送するステップと、を実行させるためのネットワーク符号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの中継ノードにおけるネットワーク符号化装置、ネットワーク符号化方法及びネットワーク符号化プログラムに関する。
【背景技術】
【０００２】
従来のインターネットに代わって、より効率的なデータ伝送・拡散を実現する情報ネットワーク構成であるＩＣＮ（Ｉｎｆｏｒｍａｔｉｏｎ−Ｃｅｎｔｒｉｃ  Ｎｅｔｗｏｒｋ）が提案されている（例えば、非特許文献１参照）。ＩＣＮでは、ネットワークを構成する中継ノードに、一度中継したデータをキャッシュする機能を持たせることで、効率的なデータ転送を実現している。
さらに、ＩＣＮに分類されるネットワーク構成の１つとしてＣＣＮ（Ｃｏｎｔｅｎｔ−Ｃｅｎｔｒｉｃ  Ｎｅｔｗｏｒｋ）がある。ＣＣＮでは、前述のキャッシュ機能を持つノードは、コンテンツへのリクエストを示す「Ｉｎｔｅｒｅｓｔ」と、このＩｎｔｅｒｅｓｔパケットに対応したコンテンツデータを包含する「Ｄａｔａ」と呼ばれる２種類のパケットを処理する。
【０００３】
また、ＩＣＮに限らず、ネットワークの中継ノード（例えば、ルータ又はスイッチ）に、コピー及び転送機能とは異なる数学的な演算機能（符号化機能）を持たせることによって、伝送レート及びスループットの向上、並びに消費エネルギの低減を実現するネットワーク符号化と呼ばれる技術が提案されている（例えば、非特許文献２参照）。さらに、このネットワーク符号化をＩＣＮの構成に取り入れることが提案されている（例えば、非特許文献３及び４参照）。ネットワーク符号化されたＩＣＮでは、符号化されたデータが中継ノードにキャッシュされる。
【０００４】
ネットワーク符号化を組み込んだＩＣＮの方式として、ＣＣＮにおける「ＣｏｄｉｎｇＣａｃｈｅ」と呼ばれる手法がある（例えば、非特許文献５参照）。コンテンツは複数の断片（Ｃｈｕｎｋ）で構成される。通常のＣＣＮでは、このＣｈｕｎｋ１つに対して要求元のノードがＩｎｔｅｒｅｓｔパケット１つを使ってリクエストを送る。また、Ｃｈｕｎｋ１つがＤａｔａパケットの１つを構成する。一方、ＣｏｄｉｎｇＣａｃｈｅを施したＣＣＮでは、Ｉｎｔｅｒｅｓｔパケットは、通常通りＣｈｕｎｋ１つ１つに対してそれぞれ送信される。ところが、このＩｎｔｅｒｅｓｔパケットに応じて送られるＤａｔａパケットは、コンテンツを構成する複数のＣｈｕｎｋのうち、少なくとも指定されたＣｈｕｎｋを含む１又は複数のＣｈｕｎｋの線形結合となる。コンテンツに対してＩｎｔｅｒｅｓｔパケットは、Ｃｈｕｎｋの数だけ発行される。また、Ｉｎｔｅｒｅｓｔパケットを発行したノードは、複数のＤａｔａパケットを受け取ることでコンテンツを復号する。ＣｏｄｉｎｇＣａｃｈｅを施したＣＣＮでは、通常のＣＣＮよりもネットワークの利用効率が向上することが知られている。
【０００５】
また、ＣｏｄｉｎｇＣａｃｈｅでは、Ｉｎｔｅｒｅｓｔパケットを受信したノード自身がこのＩｎｔｅｒｅｓｔパケットに対応するＤａｔａパケットのキャッシュを有していない場合、Ｄａｔａパケットを発行してくれる可能性のある隣接ノードを、Ａｄａｐｔｉｖｅ  Ｆｏｒｗａｒｄｉｎｇを使って１つ選択し、この隣接ノードに対してＩｎｔｅｒｅｓｔパケットを転送する（例えば、非特許文献６参照）。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｂ．  Ａｈｌｇｅｎ，  Ｃ．  Ｄａｎｎｅｗｉｔｚ，  Ｃ．  Ｉｍｂｒｅｎｄａ，  Ｄ．  Ｋｕｔｓｃｈｅｒ，  ａｎｄ  Ｂ．  Ｏｈｌｍａｎ，  “Ａ  ｓｕｒｖｅｙ  ｏｆ  ｉｎｆｏｒｍａｔｉｏｎ−ｃｅｎｔｒｉｃ  ｎｅｔｗｏｒｋｉｎｇ”，  ＩＥＥＥ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｍａｇａｚｉｎｅ，  ｖｏｌ．  ５０，  ｎｏ．  ７，  ｐｐ．  ２６−３６，  ２０１２．
【非特許文献２】Ｖ．  Ｊａｃｏｂｓｏｎ，  Ｄ．  Ｋ．  Ｓｍｅｔｔｅｒｓ，  Ｊ．  Ｄ．  Ｔｈｏｒｎｔｏｎ，  Ｍ．  Ｆ．  Ｐｌａｓｓ，  Ｎ．  Ｈ．  Ｂｒｉｇｇｓ  ａｎｄ  Ｒ．  Ｌ．  Ｂｒａｙｎａｒｄ，  “Ｎｅｔｗｏｒｋｉｎｇ  Ｎａｍｅｄ  Ｃｏｎｔｅｎｔ，”  Ｐｒｏｃ．  ＣｏＮＥＸＴ  ２００９，  ｐｐ．  １−１２，  ２００９．
【非特許文献３】Ｒ．  Ａｈｌｓｗｅｄｅ，  Ｎ．  Ｃａｉ，  Ｓ．−Ｙ．  Ｒ．  Ｌｉ，  ａｎｄ  Ｒ．  Ｗ．  Ｙｅｕｎｇ，  “Ｎｅｔｗｏｒｋ  ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ，”  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，  ｖｏｌ．  ４６，  ｎｏ．  ４，  ｐｐ．１２０４−１２１６，  ２０００．
【非特許文献４】Ｍ．  Ｍｏｎｔｐｅｔｉｔ，  Ｃ．  Ｗｅｓｔｐｈａｌ，  ａｎｄ  Ｄ．  Ｔｒｏｓｓｅｎ，  “Ｎｅｔｗｏｒｋ  ｃｏｄｉｎｇ  ｍｅｅｔｓ  ｉｎｆｏｒｍａｔｉｏｎ−ｃｅｎｔｒｉｃ  ｎｅｔｗｏｒｋｉｎｇ：  ａｎ  ａｒｃｈｉｔｅｃｔｕｒａｌ  ｃａｓｅ  ｆｏｒ  ｉｎｆｏｒｍａｔｉｏｎ  ｄｉｓｐｅｒｓｉｏｎ  ｔｈｒｏｕｇｈ  ｎａｔｉｖｅ  ｎｅｔｗｏｒｋ  ｃｏｄｉｎｇ，”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＮｏＭ  ２０１２，  ｐｐ．  ３１−３６，  ２０１２．
【非特許文献５】Ｑ．  Ｗｕ，  Ｚ．  Ｌｉ  ａｎｄ  Ｇ．  Ｘｉｅ，  “ＣｏｄｉｎｇＣａｃｈｅ：  Ｍｕｌｔｉｐａｔｈ−ａｗａｒｅ  ＣＣＮ  Ｃａｃｈｅ  ｗｉｔｈ  Ｎｅｔｗｏｒｋ  Ｃｏｄｉｎｇ，”  Ｐｒｏｃ．  ＡＣＭ  ＳＩＧＣＯＭＭ  ｗｏｒｋｓｈｏｐ  ｏｎ  ｉｎｆｏｒｍａｔｉｏｎ−ｃｅｎｔｒｉｃ  ｎｅｔｗｏｒｋｉｎｇ  ２０１３，  ｐｐ．  ４１−−４２，  Ａｕｇ．  ２０１３．
【非特許文献６】Ｃ．  Ｙｉ，  Ａ．  Ａｆａｎａｓｙｅｖ，  Ｌ．  Ｗａｎｇ，  Ｂ．  Ｚｈａｎｇ  ａｎｄ  Ｌ．  Ｚｈａｎｇ，  “Ａｄａｐｔｉｖｅ  Ｆｏｒｗａｒｄｉｎｇ  ｉｎ  Ｎａｍｅｄ  Ｄａｔａ  Ｎｅｔｗｏｒｋｉｎｇ，”  ＡＣＭ  ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｒｅｖｉｅｗ，  ｖｏｌ．  ４２，  ｎｏ．３，  ｐｐ．６２−−６７，  Ｊｕｌｙ  ２０１２．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、前述のＣｏｄｉｎｇＣａｃｈｅによっても、ネットワークの利用効率は十分ではなく、スループットの向上が望まれている。
【０００８】
本発明は、コンテンツダウンロードにおけるスループットを向上できるネットワーク符号化装置、ネットワーク符号化方法及びネットワーク符号化プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明に係るネットワーク符号化装置は、コンテンツを構成する断片のうち、送信した１又は複数の断片の線形結合による符号化キャッシュを記憶するキャッシュ記憶部と、前記断片のいずれかを要求する要求パケットを受信した際に、当該要求された断片を含む符号化キャッシュが前記キャッシュ記憶部に存在しない場合、当該要求された断片及び要求元を識別するデータを記憶するリクエスト記憶部と、複数の隣接ノードに対して、前記要求パケットを転送する転送部と、を備える。
【００１０】
前記ネットワーク符号化装置は、前記断片のいずれかを要求する要求パケットを受信した際に、当該要求された断片を含む符号化キャッシュが前記キャッシュ記憶部に存在する場合、当該要求された断片を含む１又は複数の符号化キャッシュに対して、ランダム係数に基づく再符号化を行い、当該再符号化したデータを含むデータパケットを、要求元へ送信する符号化部を備えてもよい。
【００１１】
前記符号化部は、データパケットを受信した場合、当該データパケットに含まれている前記要求された断片を含む符号化キャッシュ、及び前記キャッシュ記憶部に記憶されている前記コンテンツを構成するいずれかの断片を含む符号化キャッシュに対して再符号化を行い、当該再符号化したデータを含むデータパケットを、要求元へ送信してもよい。
【００１２】
前記キャッシュ記憶部は、前記受信したデータパケットに基づいて再符号化されたデータを、新たな符号化キャッシュとして記憶してもよい。
【００１３】
前記キャッシュ記憶部は、記憶する符号化キャッシュが所定の閾値を超える場合、線形従属な符号化キャッシュを優先して削除してもよい。
【００１４】
前記キャッシュ記憶部は、記憶している符号化キャッシュの利用率に基づいて、削除対象を決定してもよい。
【００１５】
本発明に係るネットワーク符号化方法は、コンテンツを伝送する中継ノードが、前記コンテンツを構成する断片のうち、送信した１又は複数の断片の線形結合による符号化キャッシュを記憶するステップと、前記断片のいずれかを要求する要求パケットを受信した際に、当該要求された断片を含む符号化キャッシュを記憶していない場合、当該要求された断片及び要求元を識別するデータを記憶するステップと、複数の隣接ノードに対して、前記要求パケットを転送するステップと、を実行する。
【００１６】
本発明に係るネットワーク符号化プログラムは、コンテンツを伝送する中継ノードに、前記コンテンツを構成する断片のうち、送信した１又は複数の断片の線形結合による符号化キャッシュを記憶するステップと、前記断片のいずれかを要求する要求パケットを受信した際に、当該要求された断片を含む符号化キャッシュを記憶していない場合、当該要求された断片及び要求元を識別するデータを記憶するステップと、複数の隣接ノードに対して、前記要求パケットを転送するステップと、を実行させる。
【発明の効果】
【００１７】
本発明によれば、コンテンツダウンロードにおけるスループットが向上する。
【図面の簡単な説明】
【００１８】
【図１】実施形態に係るネットワーク符号化システムの構成を示す図である。
【図２】実施形態に係る中継ノードの機能構成を示すブロック図である。
【図３】実施形態に係るネットワーク符号化によって伝送されるコンテンツの構成例を示す図である。
【図４】実施形態に係る中継ノードがＩｎｔｅｒｅｓｔパケットを受信したとき、対応する符号化キャッシュがある場合の機能を示す図である。
【図５】実施形態に係る中継ノードがＩｎｔｅｒｅｓｔパケットを受信したとき、対応する符号化キャッシュがない場合の機能を示す図である。
【図６】実施形態に係る中継ノードがＩｎｔｅｒｅｓｔパケットを受信したとき、対応する符号化キャッシュはないが、リクエスト記憶部に同一のＣｈｕｎｋを要求するエントリが存在する場合の機能を示す図である。
【図７】実施形態に係る中継ノードがＤａｔａパケットを受信した場合の機能を示す図である。
【図８】実施形態に係る受信ノードの機能を示す図である。
【図９】実施形態に係る中継ノードがＩｎｔｅｒｅｓｔパケットを受信した際の処理を示すフローチャートである。
【図１０】実施形態に係る中継ノードがＤａｔａパケットを受信した際の処理を示すフローチャートである。
【発明を実施するための形態】
【００１９】
本発明の実施形態の一例について説明する。
図１は、本実施形態に係るネットワーク符号化システム１の構成を示す図である。
本実施形態では、ＣＣＮに対してネットワーク符号化が適用される。
【００２０】
送信ノード１０から送信されるコンテンツ等のデータは、ネットワーク内の複数の中継ノード２０（ネットワーク符号化装置）を経由して、受信ノード３０で受信される。中継ノード２０では、後述の符号化処理により符号化されたデータがキャッシュ記憶部２１に記憶される。このキャッシュ記憶部２１は、受信ノード３０からのダウンロード要求に応じて参照される。
【００２１】
図２は、本実施形態に係る中継ノード２０の機能構成を示すブロック図である。
中継ノード２０は、キャッシュ記憶部２１と、符号化部２２と、乱数生成部２３と、リクエスト記憶部２４と、転送情報記憶部２５と、転送部２６と、インタフェース２７とを備える。
【００２２】
キャッシュ記憶部２１（Ｃａｃｈｅ  Ｓｔｏｒａｇｅ）は、符号化部２２により符号化された符号化キャッシュを記憶する。
符号化部２２（Ｅｎｃｏｄｅｒ）は、受信したＤａｔａパケット及びキャッシュ記憶部２１の符号化キャッシュに対して、所定の符号化演算を行う。
乱数生成部２３（Ｒａｎｄｏｍ  Ｇｅｎｅｒａｔｏｒ）は、符号化部２２に対する入力として、乱数を生成する。
リクエスト記憶部２４（ＰＩＴ；Ｐｅｎｄｉｎｇ  Ｉｎｔｅｒｅｓｔ  Ｔａｂｌｅ）は、隣接ノードから受信したＩｎｔｅｒｅｓｔパケットのリクエスト情報を記憶する。
転送情報記憶部２５（ＦＩＢ；Ｆｏｒｗａｒｄｉｎｇ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｂａｓｅ）は、Ｄａｔａパケットが発行される可能性のあるＩｎｔｅｒｅｓｔパケットの転送先を記憶する。
転送部２６（Ｆｏｒｗａｒｄｅｒ）は、転送情報記憶部２５の情報に従って、Ｉｎｔｅｒｅｓｔパケットを隣接ノードへ転送する。
インタフェース２７（Ｆａｃｅ）は、隣接ノードとの間でＩｎｔｅｒｅｓｔパケット又はＤａｔａパケットを送受信する。
【００２３】
図３は、本実施形態に係るネットワーク符号化によって伝送されるコンテンツの構成例を示す図である。
コンテンツは、送信ノード１０により複数のＣｈｕｎｋに分割されて送信される。本実施形態では、例として、コンテンツＡは、３つの断片（Ｃｈｕｎｋ）Ｃ１〜Ｃ３で構成されているものとして説明する。
Ｄａｔａパケットは、この３つのＣｈｕｎｋのうち、いずれかの線形結合となる。Ｄａｔａパケットには、例えばヘッダ部に、コンテンツの識別子及び線形結合の係数等の符号化情報が記述される。なお、それぞれのＣｈｕｎｋに対するＩｎｔｅｒｅｓｔパケットは全て発行され、コンテンツＡ全体に対するリクエストが行われているものとする。
【００２４】
以下、中継ノード２０の機能を、ケース１〜４に場合分けして詳述する。
＜ケース１＞
図４は、本実施形態に係る中継ノード２０がＩｎｔｅｒｅｓｔパケットを受信したとき、対応する符号化キャッシュがある場合の機能を示す図である。
【００２５】
中継ノード２０は、インタフェース２７（Ｆａｃｅ  Ｆ１）から、Ｃｈｕｎｋ  Ｃ２を要求するＩｎｔｅｒｅｓｔパケットを受信する。
このとき、キャッシュ記憶部２１（Ｃａｃｈｅ  Ｓｔｏｒａｇｅ）は、要求されたＣｈｕｎｋ  Ｃ２を含むＣｈｕｎｋの線形結合である符号化キャッシュを１又は複数個記憶している。
【００２６】
符号化部２２（Ｅｎｃｏｄｅｒ）は、キャッシュ記憶部２１から抽出した複数の符号化キャッシュ、及び乱数生成部２３（Ｒａｎｄｏｍ  Ｇｅｎｅｒａｔｏｒ）により生成されたランダム係数を入力として再符号化を行い、符号化キャッシュのランダムな線形結合を生成する。
符号化部２２は、このランダムな線形結合を、受信したＩｎｔｅｒｅｓｔパケットに対応するＤａｔａパケットとして送り返す。
なお、符号化部２２は、要求されたＣｈｕｎｋ以外の同一コンテンツに関するＣｈｕｎｋ（Ｃ１又はＣ３）から構成される符号化キャッシュを含めて再符号化してもよい。
【００２７】
＜ケース２＞
図５は、本実施形態に係る中継ノード２０がＩｎｔｅｒｅｓｔパケットを受信したとき、対応する符号化キャッシュがない場合の機能を示す図である。
【００２８】
中継ノード２０は、インタフェース２７（Ｆａｃｅ  Ｆ１）から、Ｃｈｕｎｋ  Ｃ２を要求するＩｎｔｅｒｅｓｔパケットを受信する。
このとき、キャッシュ記憶部２１は、要求されたＣｈｕｎｋ  Ｃ２を含む符号化キャッシュを記憶していない。
【００２９】
また、中継ノード２０は、Ｃｈｕｎｋ  Ｃ２に対するＩｎｔｅｒｅｓｔパケットを過去に受信しておらず、リクエスト記憶部２４（ＰＩＴ；Ｐｅｎｄｉｎｇ  Ｉｎｔｅｒｅｓｔ  Ｔａｂｌｅ）には、Ｃｈｕｎｋ  Ｃ２に関する未処理のエントリがない。そこで、中継ノード２０は、いずれのインタフェース２７から、どのＣｈｕｎｋに対するＩｎｔｅｒｅｓｔパケットを受信したかを示す情報（Ｆａｃｅ  Ｆ１からＣｈｕｎｋ  Ｃ２に対するリクエスト）を、リクエスト記憶部２４に追加記憶する。
【００３０】
続いて、転送部２６は、転送情報記憶部２５（ＦＩＢ；Ｆｏｒｗａｒｄｉｎｇ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｂａｓｅ）から、Ｃｈｕｎｋ  Ｃ２を含むＤａｔａパケットが発行される可能性のある隣接ノード又はネットワークに対するインタフェース２７のリストを取得する。そして、転送部２６は、これらのインタフェース２７（例えば、Ｆａｃｅ  Ｆ２及びＦ３）から、隣接ノードへＩｎｔｅｒｅｓｔパケットを転送する。
なお、転送先は、転送情報記憶部２５から取得された複数のインタフェース２７の全て、又は所定数がランダムに選択されてもよい。
【００３１】
＜ケース３＞
図６は、本実施形態に係る中継ノード２０がＩｎｔｅｒｅｓｔパケットを受信したとき、対応する符号化キャッシュはないが、リクエスト記憶部に同一のＣｈｕｎｋを要求するエントリが存在する場合の機能を示す図である。
【００３２】
中継ノード２０は、インタフェース２７（Ｆａｃｅ  Ｆ１）から、Ｃｈｕｎｋ  Ｃ２を要求するＩｎｔｅｒｅｓｔパケットを受信する。
中継ノード２０は、Ｃｈｕｎｋ  Ｃ２に対するＩｎｔｅｒｅｓｔパケットを過去に受信しており、リクエスト記憶部２４（ＰＩＴ；Ｐｅｎｄｉｎｇ  Ｉｎｔｅｒｅｓｔ  Ｔａｂｌｅ）には、Ｃｈｕｎｋ  Ｃ２に関する未処理のエントリ（例えば、Ｆａｃｅ  Ｆ２からのリクエスト）がある。
【００３３】
中継ノード２０は、いずれのインタフェース２７から、どのＣｈｕｎｋに対するＩｎｔｅｒｅｓｔパケットを受信したかを示す情報（Ｆａｃｅ  Ｆ１からＣｈｕｎｋ  Ｃ２に対するリクエスト）を、リクエスト記憶部２４に追加記憶する。この場合、既にＣｈｕｎｋ  Ｃ２に対するＩｎｔｅｒｅｓｔパケットは送信されているので、更に転送処理は行われない。
【００３４】
＜ケース４＞
図７は、本実施形態に係る中継ノード２０がＤａｔａパケットを受信した場合の機能を示す図である。
【００３５】
中継ノード２０は、インタフェース２７（Ｆａｃｅ  Ｆ３）から、Ｃｈｕｎｋ  Ｃ２を含むＤａｔａパケットを受信する。
このとき、キャッシュ記憶部２１（Ｃａｃｈｅ  Ｓｔｏｒａｇｅ）は、コンテンツＡを構成するいずれかのＣｈｕｎｋ（Ｃ１又はＣ３）の線形結合である他の符号化キャッシュを記憶しているものとする。
【００３６】
中継ノード２０は、リクエスト記憶部２４（ＰＩＴ）に、受信したＤａｔａパケットに対応するエントリがあるか否かを確認する。そして、符号化部２２（Ｅｎｃｏｄｅｒ）は、エントリの数だけ、再符号化した符号化キャッシュを生成し、各エントリに記載されているＩｎｔｅｒｅｓｔパケットの要求元のインタフェース２７（Ｆａｃｅ  Ｆ１及びＦ２）に対してＤａｔａパケットを送信する。
【００３７】
具体的には、符号化部２２は、Ｆａｃｅ  Ｆ３から受信したＤａｔａパケット、及びキャッシュ記憶部２１から抽出したコンテンツＡに関する符号化キャッシュと、乱数生成部２３（Ｒａｎｄｏｍ  Ｇｅｎｅｒａｔｏｒ）により生成されたランダム係数とを入力として、当該エントリの数の符号化キャッシュの線形結合を新たに生成する。
なお、キャッシュ記憶部２１に対象の符号化キャッシュがない場合、受信したＤａｔａパケットに対する再符号化は省略可能である。
【００３８】
また、中継ノード２０は、再符号化された符号化キャッシュを、キャッシュ記憶部２１に追加記憶する。このとき、規定の閾値を超える場合には、キャッシュ記憶部２１は、古い符号化キャッシュを上書きする。あるいは、キャッシュ記憶部２１は、線形従属の関係にあるいずれかの符号化キャッシュ、又は利用率の低い符号化キャッシュを優先して削除してもよい。
【００３９】
図８は、本実施形態に係る受信ノード３０の機能を示す図である。
受信ノード３０は、キャッシュ記憶部３１（Ｃａｃｈｅ  Ｓｔｏｒａｇｅ）と、復号部３２（Ｄｅｃｏｄｅｒ）と、インタフェース３３（Ｆａｃｅ  Ｆ４）とを備える。
【００４０】
受信ノード３０は、コンテンツＡを構成する全てのＣｈｕｎｋ（Ｃ１〜Ｃ３）に対するＩｎｔｅｒｅｓｔパケットを発行し、これらへの応答として、Ｄａｔａパケットを受信し、キャッシュ記憶部３１に記憶する。
この例では、受信ノード３０は、Ｃｈｕｎｋ  Ｃ１及びＣ２に続いて、Ｃｈｕｎｋ  Ｃ３に関するＤａｔａパケットをインタフェース２７（Ｆａｃｅ  Ｆ４）から受信している。
【００４１】
復号部３２は、キャッシュ記憶部３１から、コンテンツＡを構成するＣｈｕｎｋの符号化キャッシュを抽出し、線形結合を解くことで復号してコンテンツＡを取得する。
【００４２】
図９は、本実施形態に係る中継ノード２０がＩｎｔｅｒｅｓｔパケットを受信した際の処理を示すフローチャートである。
【００４３】
ステップＳ１において、中継ノード２０は、隣接ノードからインタフェース２７を介してＩｎｔｅｒｅｓｔパケットを受信する。
【００４４】
ステップＳ２において、中継ノード２０は、受信したＩｎｔｅｒｅｓｔパケットにより要求されているＣｈｕｎｋを含む符号化キャッシュがキャッシュ記憶部２１に記憶されているか否かを判定する。この判定がＹＥＳの場合、処理はステップＳ３に移り、判定がＮＯの場合、処理はステップＳ５に移る。
【００４５】
ステップＳ３において、中継ノード２０は、符号化部２２により、要求されたＣｈｕｎｋを含む符号化キャッシュの再符号化を行い、新たな符号化キャッシュを生成する。
【００４６】
ステップＳ４において、中継ノード２０は、生成した新たな符号化キャッシュを、Ｄａｔａパケットとして要求元へ送信する。
【００４７】
ステップＳ５において、中継ノード２０は、リクエスト記憶部２４（ＰＩＴ）に、要求されたＣｈｕｎｋに関する他のリクエストが存在するか否かを判定する。この判定がＹＥＳの場合、処理はステップＳ６に移り、判定がＮＯの場合、処理はステップＳ７に移る。
【００４８】
ステップＳ６において、中継ノード２０は、リクエスト記憶部２４（ＰＩＴ）に、受信したＩｎｔｅｒｅｓｔパケットに対応するエントリを追加し、処理を終了する。
【００４９】
ステップＳ７において、中継ノード２０は、リクエスト記憶部２４（ＰＩＴ）に、受信したＩｎｔｅｒｅｓｔパケットに対応するエントリを追加する。
【００５０】
ステップＳ８において、中継ノード２０は、転送情報記憶部２５（ＦＩＢ）から転送すべきインタフェース２７の情報を抽出し、複数の転送先を決定する。
【００５１】
ステップＳ９において、中継ノード２０は、ステップＳ８で決定した複数のインタフェース２７に対してＩｎｔｅｒｅｓｔパケットを転送する。
【００５２】
図１０は、本実施形態に係る中継ノード２０がＤａｔａパケットを受信した際の処理を示すフローチャートである。
【００５３】
ステップＳ１１において、中継ノード２０は、隣接ノードからインタフェース２７を介してＤａｔａパケットを受信する。
【００５４】
ステップＳ１２において、中継ノード２０は、受信したＤａｔａパケットに含まれるＣｈｕｎｋと同一のコンテンツに関する符号化キャッシュを、キャッシュ記憶部２１から抽出する。
【００５５】
ステップＳ１３において、中継ノード２０は、リクエスト記憶部２４（ＰＩＴ）に、受信したＤａｔａパケットに含まれるＣｈｕｎｋを要求するエントリが存在すれば、このエントリの数だけ、ランダムな再符号化を実行して新たな符号化キャッシュを生成する。
なお、リクエスト記憶部２４（ＰＩＴ）にエントリが存在しない場合、及びキャッシュ記憶部２１に関連する符号化キャッシュが存在しない場合には、再符号化は省略されてもよい。
【００５６】
ステップＳ１４において、中継ノード２０は、新たな符号化キャッシュを含むＤａｔａパケットを、リクエスト記憶部２４（ＰＩＴ）のエントリで指定されているＣｈｕｎｋの要求元へ送信する。
【００５７】
ステップＳ１５において、中継ノード２０は、リクエスト記憶部２４（ＰＩＴ）から、ステップＳ１４で送信したＤａｔａパケットに関するエントリを削除する。
【００５８】
ステップＳ１６において、中継ノード２０は、ステップＳ１３で生成した符号化キャッシュを、キャッシュ記憶部２１に追加記憶する。
【００５９】
以上のように、本実施形態によれば、ネットワーク符号化装置としての中継ノード２０は、キャッシュ記憶部２１を備える。そして、中継ノード２０は、Ｉｎｔｅｒｅｓｔパケットを受信した際に、要求されたＣｈｕｎｋを記憶していない場合、要求されたＣｈｕｎｋ及び要求元を示すリクエスト情報を記憶した上で、このＣｈｕｎｋを含むＤａｔａパケットの発行が期待できる複数の隣接ノードに対してＩｎｔｅｒｅｓｔパケットを転送する。
【００６０】
すなわち、従来の技術（ＣｏｄｉｎｇＣａｃｈｅ）では、可能性のある隣接ノードをランダムに１つだけ選択するのに対して、本実施形態では、可能性のある隣接ノードの全て又は任意に選択した複数個に対してＩｎｔｅｒｅｓｔパケットを転送する。
したがって、単一パスのみを利用して該当Ｉｎｔｅｒｅｓｔパケットを発行し、この単一パスのみから対応するＤａｔａパケットを受信する場合に比べて、本実施形態のＩｎｔｅｒｅｓｔパケットの転送手法によれば、中継ノード２０は、より多くの種類の線形結合を取得でき、効率的にコンテンツを伝送及び拡散できる。この結果、たとえキャッシュ容量がＣＣＮと同等であっても、コンテンツダウンロードにおけるスループットの向上が期待できると共に、より確実なコンテンツの復号が担保される。
さらに、符号化キャッシュが拡散されることにより、ネットワーク障害に強いダウンロードシステムが構成される。
【００６１】
また、中継ノード２０は、Ｉｎｔｅｒｅｓｔパケットに対して、Ｄａｔａパケットを返信する場合、要求されたＣｈｕｎｋを含む複数の符号化キャッシュに対して、ランダム係数に基づく再符号化を行って要求元へ送信する。
従来の技術（ＣｏｄｉｎｇＣａｃｈｅ）では、この再符号化処理が行われないため、同じＣｈｕｎｋに対するＩｎｔｅｒｅｓｔパケットを受けたノードは、常に同じＤａｔａパケットを返す。一方、本実施形態の符号化手法では、中継ノード２０は、ランダム係数による再符号化を行うので、複数個のＩｎｔｅｒｅｓｔパケットを発行しても、これらに対して隣接ノードから発行される複数のＤａｔａパケットは、高い確率で線形独立となる。したがって、復号時に収集される符号化キャッシュが互いに線形独立となる確率が向上するので、コンテンツ全体の送付に関して、ネットワークの利用効率の向上が期待できる。
【００６２】
同様に、中継ノード２０は、Ｉｎｔｅｒｅｓｔパケットに対するＤａｔａパケットを受信した場合にも、同一のコンテンツに関して記憶している符号化キャッシュを含めて再符号化を行い、要求元へ送信する。
これにより、発行されるＤａｔａパケットが高い確率で線形独立となるので、コンテンツ全体の送付に関して、ネットワークの利用効率の向上が期待できる。
【００６３】
このとき、中継ノード２０は、受信したＤａｔａパケットに基づいて再符号化されたデータを、新たな符号化キャッシュとしてキャッシュ記憶部２１に記憶する。
従来の技術（ＣｏｄｉｎｇＣａｃｈｅ）では、単一の線形結合を生成・キャッシュして転送を行うが、本実施形態の符号化及びキャッシュ手法では、中継ノード２０は、複数個の異なる線形結合を生成し、キャッシュを更新し続ける。これにより、発行されるＤａｔａパケットが高い確率で線形独立となるので、コンテンツ全体の送付に関して、ネットワークの利用効率の向上が期待できる。
【００６４】
また、中継ノード２０は、キャッシュ記憶部２１を最適化する手段を備え、キャッシュ容量に所定の閾値が設けられると、線形従属な符号化キャッシュ、又は利用率が相対的に低い符号化キャッシュを優先的に削除できる。
したがって、キャッシュ記憶部２１の利用効率が向上すると共に、ネットワークに拡散される符号化キャッシュの線形独立性が高まることが期待できる。
【００６５】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。
【００６６】
本実施形態では、コンテンツは、複数のＣｈｕｎｋにより構成されることとしたが、Ｃｈｕｎｋの数が多くなることにより伝送効率が低下するのを抑制するため、例えばコンテンツの容量に応じて、コンテンツを複数のグループに分割し、このグループ毎に複数のＣｈｕｎｋの線形結合によりネットワーク符号化を行ってもよい。
【００６７】
また、本実施形態では、ＣＣＮにネットワーク符号化を適用した場合を説明したが、本発明は、種々のネットワークにおける、データセンタサービス又はクラウドサービス等に適用可能である。
【００６８】
本実施形態に係るネットワーク符号化方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。
【符号の説明】
【００６９】
１  ネットワーク符号化システム
１０  送信ノード
２０  中継ノード（ネットワーク符号化装置）
２１  キャッシュ記憶部
２２  符号化部
２３  乱数生成部
２４  リクエスト記憶部
２５  転送情報記憶部
２６  転送部
２７  インタフェース
３０  受信ノード
３１  キャッシュ記憶部
３２  復号部
３３  インタフェース
【図１】
2015076833.tif 000003
【図２】
2015076833.tif 000004
【図３】
2015076833.tif 000005
【図４】
2015076833.tif 000006
【図５】
2015076833.tif 000007
【図６】
2015076833.tif 000008
【図７】
2015076833.tif 000009
【図８】
2015076833.tif 000010
【図９】
2015076833.tif 000011
【図１０】
2015076833.tif 000012