(57)【要約】      （修正有）【課題】情報中心ネットワークにおけるネットワーク符号化を容易とするシステムを提供する。【解決手段】システムは、コンテンツ消費者ノードから、コンテンツオブジェクトに関連付けられた複数のチャンクについての１つ以上のインタレストを送信する。各インタレストは、最も一般的なレベルから最も特定のレベルまで順序付けられた連続的な名称要素を含む階層的に構造化された可変長識別子を使用して対応するチャンクを示している。応答において、システムは、多数のネットワーク符号化されたデータパケットを受信し、各データパケットは、コンテンツオブジェクトについての全てのチャンクの独立線形結合に対応している。システムは、その後、受信したデータパケットに基づいてコンテンツオブジェクトを再構成する。【選択図】なし【特許請求の範囲】
【請求項１】
情報中心ネットワークにおけるネットワーク符号化を容易とするコンピュータ実行可能な方法において、
コンテンツ消費者ノードから、コンテンツオブジェクトに関連付けられた複数のチャンクについての１つ以上のインタレストを送信することであり、各インタレストが最も一般的なレベルから最も特定のレベルまで順序付けられた連続的な名称要素を含む階層的に構造化された可変長識別子を使用して前記対応するチャンクを示していることと、
応答において、多数のネットワーク符号化されたデータパケットを受信することであり、各データパケットが前記コンテンツオブジェクトについての全ての前記チャンクの独立線形結合に対応していることと、
受信した前記データパケットに基づいて前記コンテンツオブジェクトを再構成することとを備える方法。
【請求項２】
受信した前記データパケットに基づいて前記コンテンツオブジェクトを再構成することが、
少なくとも１つ以上のデータパケットが欠落したチャンクを再構成するのに必要とされる旨を判定することと、
前記欠落したチャンクを示す再試行インタレストを送信することとを備える、請求項１に記載の方法。
【請求項３】
情報中心ネットワークにおけるネットワーク符号化を容易とするコンピュータシステムにおいて、
コンテンツ消費者ノードから、コンテンツオブジェクトに関連付けられた複数のチャンクについての１つ以上のインタレストを送信するように構成されたインタレスト生成モジュールであり、各インタレストが最も一般的なレベルから最も特定のレベルまで順序付けられた連続的な名称要素を含む階層的に構造化された可変長識別子を使用して前記対応するチャンクを示しているインタレスト生成モジュールと、
コンテンツ再構成モジュールとを備え、前記コンテンツ再構成モジュールが、
多数のネットワーク符号化されたデータパケットを受信し、各データパケットが前記コンテンツオブジェクトについての全ての前記チャンクの独立線形結合に対応しており、
受信した前記データパケットに基づいて前記コンテンツオブジェクトを再構成するように構成されているコンピュータシステム。
【請求項４】
受信した前記データパケットに基づいて前記コンテンツオブジェクトを再構成するとき、前記コンテンツ再構成モジュールが、さらに、
少なくとも１つ以上のデータパケットが欠落したチャンクを再構成するのに必要とされる旨を判定し、
前記欠落したチャンクを示す再試行インタレストを送信するように構成されている、請求項３に記載のコンピュータシステム。
【請求項５】
前記階層的に構造化された可変長識別子が、ネットワーク符号化の使用及び前記コンテンツオブジェクトについての多数のチャンクを示す要素を含む、請求項３に記載のコンピュータシステム。
【請求項６】
前記階層的に構造化された可変長識別子が、前記対応するインタレストが再試行インタレストであるかどうかを示す要素を含む、請求項３に記載のコンピュータシステム。
【請求項７】
前記階層的に構造化された可変長識別子が、既に再構成された１つ以上のチャンクを示す要素を含む、請求項３に記載のコンピュータシステム。
【請求項８】
情報中心ネットワークにおけるスイッチングノードにおけるネットワーク符号化を容易とするコンピュータシステムにおいて、
コンテンツオブジェクトに関連付けられたチャンクについてのコンテンツ消費者ノードによって生成されたインタレストを受信するように構成されたインタレスト受信モジュールと、
転送モジュールとを備え、前記転送モジュールが、
ローカルに利用可能であり且つ前記インタレストを受信したノードに対して以前に送信されなかった前記チャンクに応答して、前記チャンクと前記インタレストが受信された前記ノードに対する前記コンテンツオブジェクトに関連付けられた１つ以上の他のチャンクとの独立線形結合を送信し、
ローカルに利用可能でない前記チャンクに応答して、前記インタレストを転送し、その後、そのような組み合わせが前記転送されたインタレストの応答において受信されたとき、前記コンテンツオブジェクトについての前記チャンク及び他のチャンクの独立線形結合をキャッシュするように構成されているコンピュータシステム。
【請求項９】
さらに、
他のノードから前記コンテンツオブジェクトについての複数のチャンクの線形結合を受信し、
受信した前記チャンクの線形結合がローカルにキャッシュされたチャンクの線形結合から独立していない旨を判定し、
前記受信したチャンクの線形結合を破棄するように構成されたチャンク管理モジュールを備える、請求項８に記載のコンピュータシステム。
【請求項１０】
さらに、
前記チャンクの前記独立線形結合を送信した後に、前記インタレストが受信された前記ノードに対して前記チャンクが送信された旨を示すチャンク送信指示モジュールを備える、請求項８に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に、ネットワークにおけるデータ処理を容易とすることに関する。より具体的には、本開示は、コンテンツ中心ネットワークにおけるネットワーク符号化を容易とするシステム及び方法に関する。
【背景技術】
【０００２】
インターネットや電子商取引の普及は、ネットワーク業界の革命的な変化を刺激し続けている。今日では、オンライン映画視聴から、毎日のニュースの配信、小売販売及びインスタントメッセージングまでのかなりの数の情報交換は、オンラインで行われている。インターネットアプリケーションの増加はまた、モバイルになっている。しかしながら、現在のインターネットは、主に、位置ベースのアドレス指定方式で動作する。２つの最もユビキタスなプロトコルであるインターネットプロトコル（ＩＰ）及びイーサネット（登録商標）プロトコルは、双方とも、位置ベースのアドレスに基づいている。すなわち、コンテンツの消費者は、物理的な対象又は位置に密接に関連しているアドレス（例えば、ＩＰアドレス又はイーサネット（登録商標）メディアアクセス制御（ＭＡＣ）アドレス）からコンテンツを明示的に要求することによってコンテンツを受信することのみができる。この制限されたアドレス指定方式は、刻々と変化するネットワーク要求を満たすためには徐々に不十分になってきている。
【０００３】
近年、業界においてコンテンツ中心ネットワーク（ＣＣＮ）アーキテクチャが提案されている。ＣＣＮは、コンテンツ伝送への新たなアプローチをもたらす。コンテンツが移動するエンドツーエンド会話としてアプリケーションレベルでネットワークトラフィックを視認する代わりに、コンテンツは、その固有の名称に基づいて要求され又は返送され、ネットワークは、プロバイダから消費者に対してコンテンツをルーティングする責を担う。コンテンツは、テキスト、画像、映像及び／又は音声などの任意の形態のデータを含む通信システムにおいて伝送されることができるデータを含むことに留意されたい。消費者及びプロバイダは、コンピュータにおける人やＣＣＮの内部又は外部の自動プロセスとすることができる。コンテンツの一部は、コンテンツ全体又はコンテンツの各部分を参照することができる。例えば、新聞記事は、データパケットとして具現化されたコンテンツの複数の部分によって表されることができる。コンテンツの一部はまた、認証データ、作成日付、コンテンツ所有者などの情報を有するコンテンツの一部を説明又は増強するメタデータに関連付けることができる。
【０００４】
ＣＣＮにおいて、コンテンツオブジェクト及びインタレストは、通常は階層的に構造化された可変長識別子（ＨＳＶＬＩ）であるそれらの名称によって識別される。コンテンツの一部におけるインタレストがＣＣＮノードにおいて受信されたとき、ローカルコンテンツキャッシュは、要求されたコンテンツが存在するかどうかを確認するために検査される。しかしながら、ある状況において、多数のＣＣＮノード及びリンクを介した伝送データは、インタレストの複数のコピーが送出されるときに非効率となり得る。
【発明の概要】
【課題を解決するための手段】
【０００５】
本発明の１つの実施形態は、情報中心ネットワークにおけるネットワーク符号化を容易とするシステムを提供する。動作中、システムは、コンテンツ消費者ノードから、コンテンツオブジェクトに関連付けられた複数のチャンクについての１つ以上のインタレストを送信する。各インタレストは、最も一般的なレベルから最も特定のレベルまで順序付けられた連続的な名称要素を含む階層的に構造化された可変長識別子を使用して対応するチャンクを示している。応答において、システムは、次に、多数のネットワーク符号化されたデータパケットを受信し、各データパケットは、コンテンツオブジェクトについての全てのチャンクの独立線形結合に対応している。その後、システムは、受信したデータパケットに基づいてコンテンツオブジェクトを再構成する。
【０００６】
本実施形態の変形例において、受信したデータパケットに基づいてコンテンツオブジェクトを再構成することは、少なくとも１つ以上のデータパケットが、欠落したチャンクを再構成するのに必要とされる旨を判定することと、欠落したチャンクを示す再試行インタレストを送信することとを含む。
【０００７】
本実施形態の変形例において、階層的に構造化された可変長識別子は、ネットワーク符号化の使用及びコンテンツオブジェクトについての多数のチャンクを示す要素を含む。
【０００８】
本実施形態の変形例において、階層的に構造化された可変長識別子は、対応するインタレストが再試行インタレストであるかどうかを示す要素を含む。
【０００９】
本実施形態の変形例において、階層的に構造化された可変長識別子は、既に再構成された１つ以上のチャンクを示す要素を含む。
【００１０】
本発明の１つの実施形態は、情報中心ネットワークにおけるスイッチングノードにおけるネットワーク符号化を容易とするシステムを提供する。動作中、システムは、コンテンツオブジェクトに関連付けられたチャンクについてのコンテンツ消費者ノードによって生成されたインタレストを受信する。ローカルに利用可能であり且つインタレストを受信したノードに対して以前に送信されなかったチャンクに応答して、システムは、チャンクとインタレストが受信されたノードに対するコンテンツオブジェクトに関連付けられた１つ以上の他のチャンクとの独立線形結合を送信する。ローカルに利用可能でないチャンクに応答して、システムは、インタレストを転送し、その後、そのような組み合わせが転送されたインタレストの応答において受信されたとき、コンテンツオブジェクトについてのチャンク及び他のチャンクの独立線形結合をキャッシュする。
【００１１】
本実施形態の変形例において、システムは、他のノードからコンテンツオブジェクトについての複数のチャンクの線形結合を受信する。そして、システムは、受信したチャンクの線形結合がローカルにキャッシュされたチャンクの線形結合から独立していない旨を判定し、受信したチャンクの線形結合を破棄する。
【００１２】
本実施形態の変形例において、チャンクの独立線形結合を送信した後に、システムは、インタレストが受信されたノードに対してチャンクが送信された旨を示す。
【００１３】
本実施形態の変形例において、システムは、受信したインタレストが迂回インタレストであると判定し、応答において、迂回インタレストを破棄する。
【図面の簡単な説明】
【００１４】
【図１】図１は、本発明の実施形態にかかるネットワークの例示的なアーキテクチャを図示している。
【図２】図２は、本発明の実施形態にかかるコンテンツオブジェクトについての例示的なチャンクを示している。
【図３−１】図３は、本発明の実施形態にかかる例示的なネットワークプロトコルスタックを図示するブロック図である。
【図３−２】表１は、本発明の実施形態にかかる例示的な名称要素を図示している。
【図４】図４は、本発明の実施形態にかかる例示的な迂回インタレストを図示する図である。
【図５】図５は、本発明の実施形態にかかるネットワーク符号化による例示的なコンテンツ・消費者システムを図示している。
【図６】図６は、本発明の実施形態にかかるネットワーク符号化による例示的なスイッチングシステムを図示している。
【発明を実施するための形態】
【００１５】
図面において、同様の参照符号は、同一の図要素を指す。
【００１６】
いくつかの情報中心ネットワーク（ＩＣＮ）アーキテクチャは、既存のインターネットアーキテクチャの代替として、それらの位置とは無関係に名称によるコンテンツ及びサービスへの効率的なアクセスを可能とするためにこれまでに提案されている。一方、ネットワーク符号化（ＮＣ）は、マルチポイント通信又は接続中断を受けるネットワークにおける情報発信のスループットを向上させるために示されている。これは、任意のリレー又は意図された受信機がデータパケットの十分な独立線形結合を受信する限りデータパケットを復号することができるように、ソース及びリレーが、個々のデータパケット自体よりもむしろ、データパケットの（要素単位の）線形結合を送信することができるような方法でデータパケットを符号化することによって達成される。
【００１７】
ＮＣは、情報発信の面でＩＣＮの全体的な性能を向上させることができる。しかしながら、いくつかの提案は、ＮＣ及びＩＣＮの統合についてこれまで進められている。さらにまた、通常、全てのルータは、ＮＣをサポートするものとされる。
【００１８】
本発明の実施形態は、ＮＣを実装するために全てのルータを必要とすることなくＩＣＮの性能を向上させるために、ＮＣがＩＣＮアプローチとシームレスに統合可能な方法の一例として、ネットワーク符号化コンテンツ中心ネットワーク（ＮＣＣＮ）を容易とする。ＮＣＣＮは、インタレスト及びデータパケットが通常のＣＣＮ又はＮＤＮパケットとしてのＮＣの能力がない通常のＣＣＮ又は名称付きデータネットワーキング（ＮＤＮ）ノードによって処理されるのを可能とする。この互換性を実現するために、ＮＣＣＮは、インタレスト及びデータパケットの構造を変更せずにＮＣの使用に必要な情報を表す新しい名称要素を導入する。ＮＣＣＮのプロトコルスタックは、通常のＣＣＮ又はＮＤＮスタックに対する最小限の変更によって設計されている。ＮＣＣＮは、ＮＣの使用を可能とするためにＣＣＮ又はＮＤＮの基本転送及びキャッシュ戦略の前に追加のステップを追加するのみである。これは、ＣＣＮ又はＮＤＮについて設計された既存の転送戦略及びキャッシュ戦略がＮＣＣＮにおいて変更することなく使用可能であることを意味する。
【００１９】
一般に、ＣＣＮは、インタレスト及びコンテンツオブジェクトという２つの種類のメッセージを使用する。インタレストは、コンテンツオブジェクトの「名称」とも称される階層的に構造化された可変長識別子（ＨＳＶＬＩ）を伝搬し、そのオブジェクトについてのリクエストとして機能する。ネットワーク要素（例えば、ルータ）が同じ名称についての複数のインタレストを受信した場合、それらのインタレストを集約することができる。マッチングコンテンツオブジェクトとインタレストの経路に沿ったネットワーク要素は、インタレストを満たす、そのオブジェクトをキャッシュして返送することができる。コンテンツオブジェクトは、インタレストの原点（複数可）までインタレストの逆経路をたどる。コンテンツオブジェクトは、他の情報のうち、ペイロードにＨＳＶＬＩを結合するために使用される同じＨＳＶＬＩ、オブジェクトのペイロード及び暗号情報を含む。
【００２０】
本開示において使用される用語は、一般に、以下のように定義される（それらの解釈は、そのようなものに限定されない）。
【００２１】
「ＨＳＶＬＩ」：名称とも称される階層的に構造化された可変長識別子である。それは、可変長のオブジェクトストリングとすることができる名称要素の順序付けられたリストである。人が読み取り可能な形態において、ｃｃｎｘ：／ｐａｔｈ／ｐａｒｔなどのフォーマットにおいて表されることができる。ホスト又はクエリ文字列はない。上述したように、ＨＳＶＬＩは、コンテンツを指し、それらがコンテンツについての組織的構造を表し且つ人に対して少なくとも部分的に有意とすることができることが望ましい。ＨＳＶＬＩの個々の要素は、任意長を有することができる。さらにまた、ＨＳＶＬＩは、明確に区切られた要素を有することができ、数バイトの任意のシーケンスを含むことができ、人が読み取り可能な特性に限定されるものではない。最長接頭辞一致検索は、ＨＳＶＬＩを有するパケット転送において重要である。例えば、「／ｐａｒｃ／ｈｏｍｅ／ｂｏｂ」におけるインタレストを示すＨＳＶＬＩは、「／ｐａｒｃ／ｈｏｍｅ／ｂｏｂ／ｔｅｓｔ．ｔｘｔ」及び「／ｐａｒｃ／ｈｏｍｅ／ｂｏｂ／ｂａｒ．ｔｘｔ」の双方と一致する。名称要素の数を考慮すると、最長一致は、最も特異的であることから最良であると考えられる。
【００２２】
「インタレスト」：コンテンツオブジェクトについてのリクエストである。インタレストは、ＨＳＶＬＩ名称接頭辞と、同じ名称接頭辞を有する複数のオブジェクトを選択するのに使用可能な他の任意のセレクタとを指定する。名称がインタレストの名称接頭辞及びセレクタと一致するいかなるコンテンツオブジェクトも、インタレストを満たす。
【００２３】
「コンテンツオブジェクト」：インタレストに応答して送信されたデータオブジェクトである。暗号化署名を介して一体に結合されたＨＳＶＬＩ名称及びコンテンツペイロードを有する。必要に応じて、全てのコンテンツオブジェクトは、コンテンツオブジェクトのＳＨＡ−２５６ダイジェストから形成された暗黙の端末名称要素を有する。１つの実施形態において、暗黙のダイジェストは、ワイヤ上で転送されず、必要に応じて、各ホップにおいて算出される。
【００２４】
上述したように、ＨＳＶＬＩは、コンテンツの一部を示し、階層的に構造化され、最も一般的なレベルから最も特定のレベルまで順序付けられた連続する要素を含む。各ＨＳＶＬＩの長さは、固定されていない。コンテンツ中心ネットワークにおいて、従来のＩＰネットワークとは異なり、パケットは、ＨＳＶＬＩによって識別されることができる。例えば、「ａｂｃｄ／ｂｏｂ／ｐａｐｅｒｓ／ｃｃｎ／ｎｅｗｓ」は、コンテンツの名称とすることができ、対応するパケット（複数可）、すなわち、「ＡＢＣＤ」と名称付けられた組織における「Ｂｏｂ」と名称付けられたユーザについて新聞の「ｃｃｎ」コレクションからの「ｎｅｗｓ」記事を識別する。コンテンツの一部を要求するために、ノードは、コンテンツの名称によってそのコンテンツにおけるインタレストを表現する（例えば、ブロードキャストする）。コンテンツの一部のインタレストは、コンテンツの名称又は識別子にしたがったコンテンツについてのクエリであってもよい。コンテンツは、ネットワーク内で利用可能な場合、コンテンツを記憶する任意のノードからそれに対して返送される。ルーティングインフラストラクチャは、情報を有する可能性の高い有望なノードにインタレストをインテリジェントに伝播し、インタレストが通過する経路に沿って利用可能なコンテンツを伝搬して戻す。
【００２５】
図１は、本発明の実施形態にかかるネットワークの例示的なアーキテクチャを図示している。この例において、ネットワーク１８０は、ノード１００〜１４５を含む。ネットワーク内の各ノードは、１つ以上の他のノードに接続されている。ネットワーク接続１８５は、そのような接続の例である。ネットワーク接続は、実線として示されているが、各線は、他のノードに１つノードを結合することができるサブネットワーク又はスーパーネットワークを表すこともできる。ネットワーク１８０は、コンテンツ中心のローカルネットワーク、スーパーネットワーク又はサブネットワークとすることができる。これらのネットワークのそれぞれは、１つのネットワーク内のノードが他のネットワーク内のノードに到達することができるように、相互接続されることができる。ネットワーク接続は、広帯域、無線、電話、衛星又は任意の種類のネットワーク接続とすることができる。ノードは、インタレストを生成するか又はコンテンツを発信することができるコンピュータシステム、ユーザを表すエンドポイント及び／又は装置とすることができる。
【００２６】
本発明の実施形態によれば、消費者は、コンテンツの一部におけるインタレストを生成することができ、ネットワーク１８０内のノードに対してインタレストを送信することができる。コンテンツの一部は、ネットワークの内部又は外部に位置することができる発行者又はコンテンツプロバイダによってネットワーク１８０内のノードに記憶されることができる。例えば、図１において、コンテンツの一部におけるインタレストは、ノード１０５において生成する。コンテンツがノードにおいて利用可能でない場合、インタレストは、第１のノードに結合された１つ以上のノードに流れる。例えば、図１において、インタレストは、利用可能なコンテンツを有していないノード１１５に流れる（インタレストフロー１５０）。次に、インタレストは、ノード１１５から、同様にコンテンツを有していないノード１２５に流れる（インタレストフロー１５５）。そして、インタレストは、利用可能なコンテンツを有するノード１３０に流れる（インタレストフロー１６０）。そして、コンテンツの流れは、コンテンツが配信されるノード１０５に到達するまでその逆経路を引き返す（コンテンツフロー１６５、１７０及び１７５）。認証などの他のプロセスは、コンテンツの流れに含まれることができる。
【００２７】
ネットワーク１８０において、コンテンツホルダ（ノード１３０）とインタレスト生成ノード（ノード１０５）との間の経路における任意数の中間ノード（ノード１００〜１４５）は、ネットワークを介して移動するのに伴い、コンテンツのローカルコピーをキャッシュするのに参加することができる。キャッシングは、ローカルにキャッシュされたコンテンツに対するアクセスを暗黙的に共有することによって他の加入者の近傍に位置する第２の加入者についてのネットワーク負荷を軽減する。
【００２８】
ＮＣＣＮの説明において使用される定義及び表記法を最初に紹介する。Ｆｑを次数ｑの有限体とし、
【００２９】
【数１】
2016048913.tif 000002
【００３０】
をＦｑ上のｍ次元ベクトル空間とする。コンテンツオブジェクトが同じ大きさの複数のチャンクｋ１、ｋ２、・・・、に分割されていると考える。有限体Ｆｑの要素又は
【００３１】
【数２】
2016048913.tif 000003
【００３２】
におけるベクトルとして各チャンクを扱う。例えば、各チャンクの大きさが１０２４バイトである場合、各チャンクは、
【００３３】
【数３】
2016048913.tif 000004
【００３４】
にわたる１０２４次元ベクトルとみなされる。固定サイズｎを有するコンテンツチャンクのグループ（ｇｒｏｕｐ）の使用を前提とし、任意の２つのグループ間の共通集合が空であるものとする。また、各グループは、固有の識別子又は番号を有するものとする。
【００３５】
図２は、コンテンツオブジェクトについての例示的なチャンクを示しており、ここで、ｎ＝４である。図における各グループは、番号＃１、＃２、・・・を有する。各グループについて、そのグループ内のコンテンツチャンクの線形結合として符号化チャンク（ｃｏｄｅｄ−ｃｈｕｎｋｓ）を定義する。ネットワークノードがそのキャッシュ内にグループ（ｋ１、・・・、ｋｎ）のｔ個の符号化チャンク
【００３６】
【数４】
2016048913.tif 000005
【００３７】
を有しており、それらが［ｙ１、・・・、ｙｔ］Ｔ＝Ａ［ｋ１，・・・，ｋｎ］Ｔとして表されると仮定する。ここで、
【００３８】
【数５】
2016048913.tif 000006
【００３９】
であり、Ｔは転置を表している。
【００４０】
【数６】
2016048913.tif 000007
【００４１】
が成立することから、ベクトル
【００４２】
【数７】
2016048913.tif 000008
【００４３】
は、Ｙｉの係数ベクトル（ｃｏｅｆｆｉｃｉｅｎｔ  ｖｅｃｔｏｒ）と称される。符号化チャンクは、それらの係数ベクトルが線形独立である場合に、他の符号化チャンクから線形独立であるという。
【００４４】
【数８】
2016048913.tif 000009
【００４５】
をＡの行ベクトル、すなわち、係数ベクトルにわたる線形部分空間とする。そして、以下のようにみえる（ｓｅｅｎ）及びみえない（ｕｎｓｅｅｎ）チャンクの定義を導入する。チャンクＫｉは、フォームのベクトル
【００４６】
【数９】
2016048913.tif 000010
【００４７】
がＶＡに属する場合にみえるといわれている。それ以外の場合、それはみえないといわれる。
【００４８】
ノードにおいてみえるチャンクの数は、ｄｉｍＶＡに等しいことに留意されたい。ノードにおいてみられる所定のグループからのチャンクの情報は、ｎ次元のバイナリベクトルによって表される。例えば、ｎ＝４であり且つグループ内の第１及び第２のチャンクがみえる場合には、グループ内のみえる又はみえないチャンクの情報は、
【００４９】
【数１０】
2016048913.tif 000011
【００５０】
によって与えられる。
【００５１】
ＮＣＣＮにおける主要な設計目標は、ＮＣＣＮに対するＣＣＮ又はＮＤＮからの漸進的な展開が可能であるように、通常のＣＣＮ又はＮＤＮアーキテクチャとの互換性を実現することである。これは、ネットワークにおけるいくつかの中間ノードがＮＣＣＮをサポートしない通常のＣＣＮ又はＮＤＮノードであったとしても、それらが通常のＣＣＮ又はＮＤＮパケットとしてＮＣＣＮインタレスト及びデータパケットを処理することができるが、制作者及び消費者は、ネットワーク符号化を使用してなおも通信することができることを意味する。逆に、ＮＣＣＮノードは、ネットワーク符号化を使用せずに通信を行う制作者及び消費者との通常のＣＣＮ又はＮＤＮトラフィックのインタレスト及びデータパケットを提供することができる。
【００５２】
図３は、ＮＣＣＮとＣＣＮ又はＮＤＮとの間の意図された互換性を図示している。ＮＣＣＮプロトコルスタックは、下位層に対する同じインターフェースと、通常のＣＣＮ又はＮＤＮノードと同じアプリケーション・プログラミング・インターフェース（ＡＰＩ）とを有する。さらに、ＮＣＣＮ戦略層は、最小限の変更が通常のＣＣＮ又はＮＤＮプロトコルスタックのものから必要とされるようにパケットを転送してキャッシュすることができなければならない。一方、ネットワーク符号化が使用されるたびに、符号化されたコンテンツは、元の（非符号化）コンテンツの利用可能性を保証するように復号されなければならない。ＣＣＮ又はＮＤＮにおいて、データパケットは、転送ノードによって日和見的にキャッシュされ、同じコンテンツを参照するインタレストに答えるために繰り返し使用される。ＮＣＣＮにおける第２の主要な設計目標は、コンテンツの消費者に元のコンテンツを復号させることによってネットワークを介して符号化されたコンテンツチャンクの発信を可能とすることである。
【００５３】
ＮＣＣＮの設計は、ＣＣＮ及びＮＤＮの文脈においてネットワーク符号化（ＮＣ）を最大限に利用するために、コンテンツが名称付けられ、転送され、キャッシュされる方法を含む。
【００５４】
ＣＣＮ、ＮＤＮ及びＮＣＣＮの間における最大の互換性を実現するために、新たな名称要素は、ＮＣＣＮルータがＮＣを利用してインタレストパケット及びデータパケットを処理するのを可能とするＮＣＣＮにおいて定義される一方で、ＣＣＮ又はＮＤＮルータは、ＮＣなしでそのようなパケットを処理することができる。ＮＣＣＮにおけるインタレスト及びデータパケットのパケットフォーマットは、ＣＣＮにおけるものと同じである。
【００５５】
符号化されたコンテンツチャンクの発信及びキャッシュについてのＮＣＣＮにおいて採用されたアプローチは、各ＮＣＣＮノードにおいて送信フラグのテーブルを実装する。ノードにおける送信フラグのテーブルは、各コンテンツチャンクがその下流ノードに対して「みえる」又は「みえない」とみなされることを示している。送信フラグを参照することにより、各ＮＣＣＮノードは、ＣＣＮ又はＮＤＮの基本戦略を実行する前に到来するパケットの転送又はキャッシュの方法を制御する。送信フラグに基づくこの制御方法を使用して、ＮＣＣＮノードは、消費者における復号可能性を維持しながら、ネットワークを介して符号化されたコンテンツチャンクを広めることができる。
【００５６】
表１は、本発明の１つの実施形態にかかるＮＣの使用を可能とするためにＮＣＣＮにおいて導入される３つの新たな名称要素を図示している。この表において、「ＣＣＮ／ＮＤＮにおける名称」は、ＣＣＮ／ＮＤＮにおけるシーケンス番号０ｘ０３を有するチャンクについての名称の例を表し、「ＮＣＣＮにおける名称」は、ＮＣ操作を使用してグループ内の他のチャンクによって符号化された同じチャンクを表している。この例に示されるように、以下の３つの名称要素を導入する。
・グループサイズを有するネットワーク符号化フラグ（ＮＣフラグ）
・再試行フラグ
・消費者において「みえる」情報
【００５７】
例えば表１におけるシーケンス番号の接頭辞％００などのマーカは、ＣＣＮ又はＮＤＮアーキテクチャにおける制御文字である。一般に、名称における制御文字は、バージョン番号又はシーケンス番号などのコンテンツチャンクの追加情報を示している。３つの新たな名称要素を追加するために３つの新たなマーカを導入する。
【００５８】
ＮＣフラグは、表１においてマーカ％Ａ０によって示されており、マーカに続く値は、グループサイズを表している。例えば、インタレストが表１におけるＮＣＣＮの名称を有する場合、サイズ０ｘ１０＝１６のグループにおける符号化チャンクについての要求であり、そのグループは、シーケンス番号０ｘ０３を有するチャンクを含む。グループは、元々存在するシーケンス番号及びグループサイズによって固有に判定されることができる。ＮＣフラグのおかげで、中間ノードに到来するインタレスト／データパケットは、ＮＣＣＮパケットとして又はＣＣＮ／ＮＤＮパケットとして認識されることができることに留意されたい。
【００５９】
再試行フラグは、表１においてマーカ％Ａ１によって示されている。マーカに続く値は、０ｘ００（偽）又は０ｘ０１（真）である。インタレストが％Ａ１％０１を含む名称を有する場合、それは特定のチャンクについての再試行インタレストと称される特別なインタレストである。それ以外の場合、単に符号化チャンクについての通常のインタレストである。
【００６０】
消費者が符号化されたチャンクについてのインタレストを送信する場合、消費者によってみえるグループ内のチャンクの情報は、名称に追加される。消費者によってみえる所定のグループＧ内のチャンクの情報は、Ｇの「みえる情報（ｓｅｅｎ  ｉｎｆｏｒｍａｔｉｏｎ）」と称され、ｎ次元のバイナリベクトル
【００６１】
【数１１】
2016048913.tif 000012
【００６２】
によって表される。表１において、みえる情報は、マーカ％Ａ２によって示されている。マーカに続く値は、ｖｓｅｅｎ，Ｇを表す１６進数値である。例えば、ｎ＝４であり且つｖｓｅｅｎ，Ｇ＝［１，１，０，０］である場合、みえる情報値は、（００１１）２＝０ｘ０３である。
【００６３】
これらの新たな名称付け要素は、中間ＮＣＣＮノードの動作を制御するために及び通常のＣＣＮ又はＮＤＮノードとの互換性を維持するために使用される。ＮＣＣＮは、３つの新たな名称要素を追加するものの、ＣＣＮ又はＮＤＮインタレストパケットフォーマットの残りを変更しない。ネットワーク符号化操作を実行するために必要な符号化チャンク及び情報は、ＣＣＮ又はＮＤＮデータパケットフォーマットのペイロードフィールドに含まれている。ＮＣＣＮにおいて導入された名称要素がちょうどＣＣＮ及びＮＤＮにおける名称の一部とみなされていることを考えると、ＮＣＣＮノードのインターフェースは、ＣＣＮ又はＮＤＮノードのものから変更されないままであり、通常のＣＣＮ又はＮＤＮノードは、通常のＣＣＮ又はＮＤＮパケットとして、ＮＣＣＮパケットのインタレスト及びデータパケットを提供することができる。
【００６４】
ＮＣＣＮにおけるインタレストパケットの処理は、通常のＣＣＮ又はＮＤＮと同様である。ノードが符号化チャンクについてのインタレストを受信すると、ノードは、（可能な場合）キャッシュされたデータパケットから新たな符号化チャンクを含むデータパケットを生成し、いくつかの条件が満たされる場合にはインタレストに対する応答として送信する。それ以外の場合、通常のＣＣＮ又はＮＤＮのように、ノードは、保留インタレスト表（ＰＩＴ）に対してインタレストを追加し、インタレストが一定時間内に転送されていない場合、ノードはまた、基本転送戦略にしたがってＰＩＴ及び転送情報ベース（ＦＩＢ）を参照することによっていくつかのフェースにわたってインタレストを転送する。
【００６５】
ＮＣＣＮにおいて、全てのデータパケットは、ＣＣＮ又はＮＤＮのデータパケットフォーマットのペイロードフィールドにおいて符号化チャンク及びその係数ベクトルを含む。
【００６６】
アルゴリズム１は、通常のＣＣＮ又はＮＤＮの基本キャッシュ戦略上で動作するＮＣＣＮのキャッシュアルゴリズムを以下に記載する。アルゴリズム１に示されるように、ＣＣＮ及びＮＤＮに対する追加のステップは、グループＧにおける受信データＹの符号化チャンクが自由度を増やさない（すなわち、Ｇについてのキャッシュされた符号化チャンクの係数ベクトルにわたる部分空間を拡張しない）とき、ノードは、データパケットをキャッシュせずに破棄するということである。
【００６７】
アルゴリズム１：そのキャッシュ内にＧについての係数ベクトル
【００６８】
【数１２】
2016048913.tif 000013
【００６９】
を有するｔ個の符号化チャンク
【００７０】
【数１３】
2016048913.tif 000014
【００７１】
を有するノードにおいて係数ベクトルｖを有するグループＧにおける符号化チャンクｙを含む到来データＹをキャッシュする。
【００７２】
【数１４】
2016048913.tif 000015
【００７３】
基本戦略にしたがってＹをキャッシュする
【００７４】
全てのＮＣＣＮノードは、ｎ次元のバイナリベクトル
【００７５】
【数１５】
2016048913.tif 000016
【００７６】
によって表される各グループＧについての送信フラグのテーブルを有し、ベクトルの初期値は０である。送信フラグの目的は、どのチャンクが下流ノードによってみえる又はみえないのかを管理すること、ノードがそのキャッシュ内に符号化チャンクを使用することによってインタレストに応答するかどうかを決定することである。Ｇにおけるチャンクｋに対応する送信フラグ（ｖｓｅｎｔ，Ｇの要素）が１である場合、ノードが符号化チャンクを既に生成し、ｋの名称を有するデータを送出したことを示している。そして、ｋを下流ノードによって既にみえるものとする。また、グループＧにおけるキャッシュされた符号化チャンクの数がｖｓｅｎｔ，Ｇのハミング重みよりも小さい場合には、符号化チャンクを生成してノードから送出することによって下流ノードによって新たにみえるようになることができるいくつかのチャンクがＧに存在するものとする。
【００７７】
アルゴリズム２は、ＮＣＣＮノード又はそのＰＩＴにおいて保留中のものによって受信されたインタレストに応答するために使用される手順を記載している。グループＧにおけるデータパケットが到来し、それがアルゴリズム１によってキャッシュされることができる場合、ノードは、アルゴリズム２によってそのＰＩＴに記憶されているＧにおける符号化チャンクについての全てのインタレストを検査し、それらのいずれかに対する応答を試みる。
【００７８】
アルゴリズム２：そのキャッシュ内に送信フラグ
【００７９】
【数１６】
2016048913.tif 000017
【００８０】
を有するＧにおけるｔ個の符号化チャンクを有するノードにおいてグループＧにおけるチャンクｋについてのインタレストに応答する。
フラグ←ｋに対応するｖｓｅｎｔ，Ｇの要素
ｗｔ（ｖｓｅｎｔ，Ｇ）←ｖｓｅｎｔ，Ｇのハミング重み
ｉｆ  フラグ  ≠  １  ｔｈｅｎ
ｉｆ  ｗｔ（ｖｓｅｎｔ，Ｇ）＜ｔであり且つｋがキャッシュにおいてみえない  ｔｈｅｎ
ｒｅｔｕｒｎ
ｅｎｄ  ｉｆ
１→ｋに対応するｖｓｅｎｔ，Ｇの要素
ｅｎｄ  ｉｆ
アルゴリズム３によってデータパケットＹを生成する
インタレストに応答する
【００８１】
アルゴリズム３：Ｇについてのｔ個の符号化チャンク
【００８２】
【数１７】
2016048913.tif 000018
【００８３】
を有するノードにおいてグループＧにおける（保留）インタレストＸに対する応答としてデータパケットＹを生成する。
【００８４】
【数１８】
2016048913.tif 000019
【００８５】
Ｘの名称を有するｙ及びｖを含むＹを生成する。
【００８６】
アルゴリズム２に示されるように、各ＮＣＣＮノードは、チャンクが下流ノードによって「既にみえる」又は「みることができる」場合にのみチャンクについてのインタレストに応答する。これは、各下流ノードにキャッシュされた符号化チャンクの係数ベクトルにわたる部分空間を拡張していない符号化チャンクの不要な送信を回避する。
【００８７】
ノードがインタレストに応答してデータパケットを生成することを決定した場合、アルゴリズム３に記載されたプロセスに続いてランダムネットワーク符号化を使用する。
【００８８】
アルゴリズム３によれば、ノードは、Ｇについてのキャッシュされた符号化チャンクのランダムな線形結合を生成し、（保留）インタレストに対する応答としてそれを送信する。そして、ＰＩＴエントリが複数の出口フェースを有する場合、各出口フェースを介して送信される符号化チャンクは異なる必要があり、したがって、アルゴリズム３は、各フェースについて実行される必要がある。
【００８９】
ＮＣＣＮノードがグループＧにおける符号化チャンクについてのインタレストを受信した場合、ノードは、まず、アルゴリズム２を実行する前にｖｓｅｎｔ，Ｇを更新する。ｄｉｍＧは、Ｇについてのキャッシュされた符号化チャンクの数を示すものとする。ｄｉｍＧは、キャッシュされた符号化チャンクの係数ベクトルにわたる部分空間の次元に等しく、ｗｔ（ｖｓｅｎｔ，Ｇ）≦ｄｉｍＧは、我々の構築を常に保持する。ここで、ｗｔはハミング重みである。到来したインタレストの名称から取得したｖｓｅｅｎ，Ｇにより、ｕＧを
【００９０】
【数１９】
2016048913.tif 000020
【００９１】
とする。ここで、
【００９２】
【数２０】
2016048913.tif 000021
【００９３】
及び「＆」は、それぞれ、要素毎の排他的論理和演算及び「論理積」演算である。そして、ｖｓｅｎｔ，ＧにおけるゼロのｕＧ要素は１になる。例えば、ｄｉｍＧ＝３、ｖｓｅｎｔ，Ｇ＝［１，１，０，０］及びｖｓｅｅｎ，Ｇ＝［１，０，１，０］である場合、ｖｓｅｎｔ，Ｇは、［１，１，１，０］に更新される。送信フラグを更新することにより、ＮＣＣＮノードは、消費者によって受信したデータパケットのステータスを管理することができる。復号コンテンツチャンクの能力は、アルゴリズム２の前に、この更新アルゴリズムを実行することによって保証される。
【００９４】
ＮＣＣＮにおいてランダムネットワーク符号化を使用して、コンテンツの消費者は、Ｆｑの大きさが大きい場合に、十分な符号化チャンクが高い確率で、各グループ、すなわち、各グループについてのｎ個の線形独立な符号化チャンクを再構成するために配信される限り、それを再構成することができる。
【００９５】
送信フラグに基づく発信技術は、ネットワークを介した線形独立な符号化チャンクの発信をサポートする。しかしながら、消費者は、コンテンツの一部を復号するためにｎ個よりも少ない線形独立な符号化チャンクを取得する可能性があり、制作者以外の全てのノードにおけるキャッシュされた全ての符号化チャンクの係数ベクトルは、次元ｎの空間にまたがらない可能性がある。そして、グループ内のいくつかのチャンクは、一定時間内にみえることができず、そのようなチャンクについての要求はタイムアウトする。この場合に対処してコンテンツチャンクが復号されるのを可能とするために、ＮＣＣＮは、再試行インタレストと称される特別なインタレストを使用する。再試行インタレストは、上述したように、名称中のマーカによって示される。消費者は、チャンクがみえておらず且つ前の保留インタレストがタイムアウトした場合に、チャンクについての再試行インタレストを送信するのが可能とされる。
【００９６】
ＮＣＣＮノードがグループＧにおけるチャンクについての再試行インタレストを受信したとき、ノードがそのキャッシュ内にＧについてのｎ個の符号化チャンクを有する場合に通常のインタレストとして再試行インタレストを処理する。ノードがｎ個よりも少ない符号化チャンクを有する場合、ノードは、チャンクについての送信フラグを０に変更し、基本ＣＣＮ又はＮＤＮ転送戦略にしたがって上流ノードに対して再試行インタレストを転送する。チャンクについての再試行インタレストの役割は、ネットワーク上でのチャンクについての符号化及び送信を再起動することである。
【００９７】
先に説明したように、ＮＣＣＮは、ネイティブＣＣＮ又はＮＤＮアーキテクチャにおいてサポートされているマルチフェース転送戦略を使用するものとする。マルチフェース転送戦略を考えると、ノードのＰＩＴに対して受信したインタレストを追加する手順前に追加工程を導入することができる。ネットワーク内のＮＣＣＮ又は通常のＣＣＮ若しくはＮＤＮノードが複数のフェースに対する転送の戦略を使用する場合、図４に示されるように、ノードに対するインタレストの「迂回」が存在する可能性がある。ネットワーク符号化の恩恵を受けるために、消費者から制作者までの異なる複数の経路が提供されるべきであるものの、図４に示されるインタレストの迂回は不要である。この例において、ノード２からノード３へと到来したインタレストは、迂回したものとみなされる。実際に、そのような迂回インタレストに対する応答は、ＮＣＣＮ内の不要なネットワーク帯域幅及び計算資源を消費する。それゆえに、そのような不要な迂回インタレストは、ＰＩＴに追加されるべきではない。
【００９８】
アルゴリズム４は、迂回インタレストを破棄するために使用される追加工程を提示する。中間ノードは、受信インタレストの到来時間又はホップ数に基づいて迂回インタレストを省略して破棄する。特に、（固有の）消費者ノードからのホップ数又は迂回インタレストの到来時間と、ＰＩＴに記憶された同じインタレストのものとの差異が閾値ｔｄｅｔｏｕｒよりも大きい場合、迂回インタレストは破棄される。ホップ数は、通常、インタレストパケットに含まれ、到来時間は、ＰＩＴエントリの寿命から明らかである。
【００９９】
アルゴリズム４：マルチフェース転送を有するノードにおいてノンスを有する迂回インタレストＸｄを破棄する。
ｈｄ←Ｘｄのホップ数（到来時間）
ＰＩＴにおいてノンスを有するインタレストＸｐが∃であるかどうかを検査する
ｉｆ  Ｘｐ≠ＮＵＬＬ  ｔｈｅｎ
ｈｐ←Ｘｐのホップ数（到来時間）
ｉｆ  ｈｄ−ｈｐ＞ｔｄｅｔｏｕｒ  ｔｈｅｎ
Ｘｄを破棄する
ｒｅｔｕｒｎ
ｅｎｄ  ｉｆ
ｅｎｄ  ｉｆ
基本戦略にしたがってＸｄを処理する
【０１００】
図５は、実施形態にかかるネットワーク符号化を容易とする例示的なコンテンツ・消費者システムを図示している。ネットワーク符号化能力を有するコンテンツ・消費者システム５００は、プロセッサ５１０と、メモリ５２０と、記憶装置５３０とを備える。記憶装置５３０は、典型的には、メモリ５２０にロードされて上述した方法を実行するためにプロセッサ５１０によって実行可能な命令を記憶する。１つの実施形態において、記憶装置５３０内の命令は、インタレスト生成モジュール５３２と、コンテンツ再構成モジュール５３４とを実装することができ、それらは、様々な手段を介して互いに通信することができる。１つの実施形態において、コンテンツ消費者システム５００は、ディスプレイ５８０、キーボード５６０及びポインティングデバイス５７０に結合される。
【０１０１】
動作中、インタレスト生成モジュール５３２は、コンテンツオブジェクトのチャンクに対応するインタレストを生成する。コンテンツ再構成モジュール５３４は、上述したように、受信したチャンクの線形結合を使用してコンテンツオブジェクトを再構成する。
【０１０２】
図６は、本発明の１つの実施形態にかかるネットワーク符号化を容易とする例示的なスイッチングシステムを図示している。この例において、ネットワーク符号化能力を有する情報中心スイッチングシステム６００は、プロセッサ６１０と、メモリ６２０と、記憶装置６３０とを備える。記憶装置６３０は、典型的には、メモリ６２０にロードされて上述した方法を実行するためにプロセッサ６１０によって実行可能な命令を記憶する。１つの実施形態において、記憶装置６３０内の命令は、インタレスト受信モジュール６３２と、ネットワーク符号化コンテンツ転送モジュール６３４と、チャンク管理モジュール６３５と、コンテンツキャッシュ６３６とを実装することができる。
【０１０３】
動作中、インタレスト受信モジュール６３２は、コンテンツオブジェクトのチャンクに対応するインタレストを受信する。そして、コンテンツ転送モジュール６３４は、受信したインタレストに応答して、コンテンツキャッシュ５３６に記憶されているチャンクの独立線形結合を構成する。チャンク管理モジュール６３５は、線形結合が要求ノードに対して予め送信された記録を維持し、また、どの線形結合がローカルにキャッシュされることになるかを管理する。
【０１０４】
この詳細な説明に記載されたデータ構造及びコードは、典型的には、コンピュータシステムによって使用するためのコード及び／又はデータを記憶することができる任意の装置又は媒体であり得るコンピュータ読み取り可能な記憶媒体に記憶される。コンピュータ読み取り可能な記憶媒体は、これらに限定されるものではないが、揮発性メモリ、不揮発性メモリ、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）、ＤＶＤ（ディジタル多用途ディスク若しくはディジタルビデオディスク）などの磁気及び光記憶装置、又は、現在公知の若しくは後に開発されるコンピュータ読み取り可能な媒体を記憶することができる他の媒体を含む。
【０１０５】
詳細な説明のセクションに記載された方法及びプロセスは、上述したようなコンピュータ読み取り可能な記憶媒体に記憶されることができるコード及び／又はデータとして具体化することができる。コンピュータシステムがコンピュータ読み取り可能な記憶媒体に記憶されたコード及び／又はデータを読み取って実行する場合、コンピュータシステムは、データ構造及びコードとして具現化されてコンピュータ読み取り可能な記憶媒体に記憶された方法及びプロセスを実行する。
【０１０６】
さらにまた、本願明細書に記載された方法及びプロセスは、ハードウェアモジュール又は装置に含めることができる。これらのモジュール又は装置は、これらに限定されるものではないが、特定用途向け集積回路（ＡＳＩＣ）チップ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定の時間に特定のソフトウェアモジュール若しくはコードの一部を実行する専用又は共有プロセッサ、及び／又は、現在公知の若しくは後に開発される他のプログラマブル論理デバイスを含むことができる。ハードウェアモジュール又は装置が起動されると、それらは、それらの内部に含まれる方法及びプロセスを実行する。
【図１】
2016048913.tif 000022
【図２】
2016048913.tif 000023
【図３−１】
2016048913.tif 000024
【図３−２】
2016048913.tif 000025
【図４】
2016048913.tif 000026
【図５】
2016048913.tif 000027
【図６】
2016048913.tif 000028