(57)【要約】      （修正有）【課題】情報中心ネットワーク（ＩＣＮ）においてインタレストを正確に処理するためのシステムを提供する。【解決手段】システムは、ＩＣＮにおける第１のノードにより、第２のノードからコンテンツの一部についてのインタレストを受信する。インタレストは、コンテンツの一部の名称を指定する。システムは、転送情報及び第１のノードに記憶されている保留インタレストに関連付けられた情報に基づいて、転送条件又はインタレスト集約条件が満たされているかどうかを判定する。転送条件が満たされるのに応答して、システムは、インタレストを転送する。インタレスト集約条件が満たされるのに応答して、システムは、インタレストを集約する。【選択図】なし【特許請求の範囲】
【請求項１】
情報中心ネットワーク（ＩＣＮ）においてインタレストを正確に処理するためのコンピュータ実行可能な方法において、
前記ＩＣＮにおける第１のノードにより、第２のノードからコンテンツの一部についてのインタレストであって、前記コンテンツの一部の名称を指定する前記インタレストを受信することと、
転送情報及び前記第１のノードに記憶されている保留インタレストに関連付けられた情報に基づいて、転送条件又はインタレスト集約条件が満たされているかどうかを判定することと、
前記転送条件が満たされるのに応答して、前記インタレストを転送することと、
前記インタレスト集約条件が満たされるのに応答して、前記インタレストを集約することとを備える、方法。
【請求項２】
前記転送情報が、前記コンテンツの一部の名称に関連付けられた１つ以上のエントリを含み、各エントリが、前記第１のノードが前記コンテンツの一部を記憶する宛先ノードに対して前記インタレストを転送することができる次ホップ隣接者を指定し、前記エントリが、さらに、前記次ホップ隣接者から前記宛先ノードまでの距離を指定する、請求項１に記載の方法。
【請求項３】
前記転送情報の少なくとも１つのエントリによって指定された距離が前記第２のノードから前記宛先ノードまでの距離よりも小さい場合に前記転送条件が満たされる、請求項２に記載の方法。
【請求項４】
コンピューティングデバイスによって実行されたときに前記コンピューティングデバイスに情報中心ネットワーク（ＩＣＮ）においてインタレストを正確に処理するための方法を実行させる命令を記憶する非一時的コンピュータ読み取り可能な記憶媒体において、
前記方法が、
前記ＩＣＮにおける第１のノードにより、第２のノードからコンテンツの一部についてのインタレストであって、前記コンテンツの一部の名称を指定する前記インタレストを受信することと、
転送情報及び前記第１のノードに記憶されている保留インタレストに関連付けられた情報に基づいて、転送条件又はインタレスト集約条件が満たされているかどうかを判定することと、
前記転送条件が満たされるのに応答して、前記インタレストを転送することと、
前記インタレスト集約条件が満たされるのに応答して、前記インタレストを集約することとを備える、コンピュータ読み取り可能な記憶媒体。
【請求項５】
前記転送情報が、前記コンテンツの一部の名称に関連付けられた１つ以上のエントリを含み、各エントリが、前記第１のノードが前記コンテンツの一部を記憶する宛先ノードに対して前記インタレストを転送することができる次ホップ隣接者を指定し、前記エントリが、さらに、前記次ホップ隣接者から前記宛先ノードまでの距離を指定する、請求項４に記載のコンピュータ読み取り可能な記憶媒体。
【請求項６】
前記転送情報の少なくとも１つのエントリによって指定された距離が前記第２のノードから前記宛先ノードまでの距離よりも小さい場合に前記転送条件が満たされる、請求項５に記載のコンピュータ読み取り可能な記憶媒体。
【請求項７】
情報中心ネットワーク（ＩＣＮ）においてインタレストを正確に処理するためのコンピュータシステムにおいて、
前記ＩＣＮにおける第１のノードにより、第２のノードからコンテンツの一部についてのインタレストであって、前記コンテンツの一部の名称を指定する前記インタレストを受信するように構成されたインタレスト受信モジュールと、
転送情報及び前記第１のノードに記憶されている保留インタレストに関連付けられた情報に基づいて、転送条件又はインタレスト集約条件が満たされているかどうかを判定するように構成されたインタレスト処理モジュールと、
前記転送条件が満たされるのに応答して、前記インタレストを転送するように構成された転送モジュールと、
前記インタレスト集約条件が満たされるのに応答して、前記インタレストを集約するように構成されたインタレスト集約モジュールとを備える、システム。
【請求項８】
前記転送情報が、前記コンテンツの一部の名称に関連付けられた１つ以上のエントリを含み、各エントリが、前記第１のノードが前記コンテンツの一部を記憶する宛先ノードに対して前記インタレストを転送することができる次ホップ隣接者を指定し、前記エントリが、さらに、前記次ホップ隣接者から前記宛先ノードまでの距離を指定する、請求項７に記載のシステム。
【請求項９】
前記保留インタレストに関連付けられた情報が、前記コンテンツの一部の名称に関連付けられたエントリを含み、前記エントリが、前記第１のノードから前記コンテンツの一部を記憶する宛先ノードまでの距離を指定する、請求項７に記載のシステム。
【請求項１０】
さらに、制御メッセージ生成モジュールを備え、
前記転送条件も前記インタレスト集約条件も満たされないことに応答して、
前記制御メッセージ生成モジュールが、制御メッセージを生成し、前記第２のノードに対して前記制御メッセージを返送するように構成されており、
前記インタレスト処理モジュールが、前記インタレストを削除するように構成されている、請求項７に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に、情報中心ネットワーク（ＩＣＮ）に関する。より具体的には、本開示は、未検出のインタレストループを解消することができるＩＣＮアーキテクチャに関する。
【背景技術】
【０００２】
インターネット及び電子商取引の普及は、ネットワーク業界における革命的な変化を刺激し続けている。今日では、オンライン映画鑑賞から毎日のニュース配信、小売売上高及びインスタントメッセージまで、かなりの数の情報交換がオンラインで行われている。増加する数のインターネットアプリケーションはまたモバイルになってきている。しかしながら、現在のインターネットは、主にロケーションベースのアドレッシング方式で動作する。２つの最もユビキタスなプロトコルであるインターネットプロトコル（ＩＰ）及びイーサネット（登録商標）プロトコルは、双方とも、エンドホストアドレスに基づいている。すなわち、コンテンツの消費者は、典型的には物理オブジェクト又は位置に関連しているアドレス（例えば、ＩＰアドレス又はイーサネット（登録商標）メディアアクセス制御（ＭＡＣ）アドレス）からコンテンツを明示的に要求することによってコンテンツを受信することができるにすぎない。この制限のあるアドレッシング方式は、刻々と変化するネットワークの要求を満たすために次第に不十分になってきている。
【０００３】
近年、コンテンツが直接名称付けられてアドレッシングされる情報中心ネットワーク（ＩＣＮ）アーキテクチャが業界において提案されている。コンテンツ中心ネットワーキング（ＣＣＮ）及び名称付きデータネットワーキング（ＮＤＮ）は、主要なインタレストベースのＩＣＮアプローチである。例えば、ＣＣＮにおいて、コンテンツが移動するエンドツーエンド会話としてのアプリケーションレベルでネットワークトラフィックを表示する代わりに、コンテンツは、固有名称に基づいて要求又は返送される。ネットワークは、提供者から消費者へとコンテンツをルーティングする責を担う。コンテンツは、テキスト、画像、映像及び／又は音声などの任意の形態のデータを含む通信システムにおいて伝送されることができるデータを含むことに留意されたい。消費者及び提供者は、ＣＣＮの内部又は外部のコンピュータ又は自動プロセスにおける人とすることができる。コンテンツの一部は、コンテンツ全体又はコンテンツの各部を指すことができる。例えば、新聞記事は、データパケットとして具現化されたコンテンツの複数部分によって表されることができる。コンテンツの一部はまた、認証データ、作成日付、コンテンツ所有者などの情報を有するコンテンツの一部を記述又は増補するメタデータに関連付けることができる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
現在のＩＣＮアーキテクチャが直面する１つの課題は、同じコンテンツを要求する異なる消費者からのインタレストが集約され且つインタレストが障害又は輻輳に起因して発生することがあるルーティングループに沿って転送されるとき、インタレストループが検出されないことがあるということである。現在の転送戦略は、インタレストループ検出の基礎として名称付きデータオブジェクト（ＮＤＯ）のノンス及び名称を使用することができる。しかしながら、そのような転送戦略は、大抵の場合、インタレスト集約の存在下で正確に動作することができない。特定の改善された転送戦略は、意図された名称接頭辞までのホップ数を記載するようにインタレストを要求することによるインタレストループ検出問題に対する救済策を提供する。しかしながら、そのようなアプローチは、インタレストのフォーマットを変更する必要があり、ネットワークの制御プレーンにおいて動作するルーティングプロトコルがネットワークにおいて使用することができる任意の他の種類の距離情報（例えば、輻輳又は遅延ベースの距離）に加えて名称接頭辞までのホップ数を維持することを要求する。したがって、そのような解決策は望ましくない。さらに、名称接頭辞までのホップ数は、自律システム間で実施可能ではない。
【課題を解決するための手段】
【０００５】
本発明の１つの実施形態は、情報中心ネットワーク（ＩＣＮ）においてインタレストを正確に処理するためのシステムを提供する。動作中において、システムは、ＩＣＮにおける第１のノードにより、第２のノードからコンテンツの一部についてのインタレストを受信する。インタレストは、コンテンツの一部の名称を指定する。システムは、転送情報及び第１のノードに記憶されている保留インタレストに関連付けられた情報に基づいて、転送条件又はインタレスト集約条件が満たされているかどうかを判定する。転送条件が満たされるのに応答して、システムは、インタレストを転送する。インタレスト集約条件が満たされるのに応答して、システムは、インタレストを集約する。
【０００６】
この実施形態の変形例において、転送情報は、コンテンツの一部の名称に関連付けられた１つ以上のエントリを含み、各エントリは、第１のノードがコンテンツの一部を記憶する宛先ノードに対してインタレストを転送することができる次ホップ隣接者を指定する。エントリは、さらに、次ホップ隣接者から宛先ノードまでの距離を指定する。
【０００７】
さらなる変形例において、転送情報の少なくとも１つのエントリによって指定された距離が第２のノードから宛先ノードまでの距離よりも小さい場合に転送条件が満たされる。
【０００８】
さらなる変形例において、エントリは、さらに、次ホップ隣接者のランキングを指定し、インタレストは、転送条件を満たす隣接者のうち最も高くランク付けされた次ホップ隣接者に対して転送される。
【０００９】
この実施形態の変形例において、保留インタレストに関連付けられた情報は、コンテンツの一部の名称に関連付けられたエントリを含み、エントリは、第１のノードからコンテンツの一部を記憶する宛先ノードまでの距離を指定する。
【００１０】
さらなる変形例において、エントリによって指定された距離が第２のノードから宛先ノードまでの距離よりも小さい場合にインタレスト集約条件が満たされる。
【００１１】
さらなる変形例において、エントリは、さらに、コンテンツの一部についてのインタレストが受信される到来隣接者のセットを指定し、インタレストは、到来隣接者のセットに第２のノードを追加することによって集約される。
【００１２】
この実施形態の変形例において、転送条件もインタレスト集約条件も満たされないのに応答して、システムは、インタレストを削除し、第２のノードに対して制御メッセージを返送する。
【図面の簡単な説明】
【００１３】
【図１】図１は、本発明の実施形態にかかる、ネットワークの例示的なアーキテクチャを図示している。
【図２Ａ】図２Ａは、情報中心ネットワーク（ＩＣＮ）における例示的なインタレストルーピングを図示する図である。
【図２Ｂ】図２Ｂは、ＩＣＮにおける例示的なインタレストルーピングを図示する図である。
【図３】図３は、本発明の実施形態にかかる、例示的な転送情報ベース（ＦＩＢ）を図示する図である。
【図４】図４は、本発明の実施形態にかかる、例示的な保留インタレストテーブル（ＰＩＴ）を図示する図である。
【図５】図５は、本発明の実施形態にかかる、例示的なＩＣＮルータのアーキテクチャを表す図である。
【図６】図６は、本発明の実施形態にかかる、例示的なインタレスト処理アルゴリズムを図示するための図である。
【図７Ａ】図７Ａは、本発明の実施形態にかかる、ＦＩＢの拡張検索の例示的な動作を図示している。
【図７Ｂ】図７Ｂは、本発明の実施形態にかかる、ＦＩＢの拡張検索の例示的な動作を図示している。
【図８Ａ】図８Ａは、本発明の実施形態にかかる、ＦＩＢの拡張検索の例示的な動作を図示している。
【図８Ｂ】図８Ｂは、本発明の実施形態にかかる、ＦＩＢの拡張検索の例示的な動作を図示している。
【図８Ｃ】図８Ｃは、本発明の実施形態にかかる、ＦＩＢの拡張検索の例示的な動作を図示している。
【図９】図９は、本発明の実施形態にかかる、ＦＩＢの拡張検索のための例示的なシステムを図示している。
【発明を実施するための形態】
【００１４】
図面において、同様の参照符号は、同じ図要素を指している。
【００１５】
概説
本発明の実施形態は、インタレストフォーマットを変更する必要なく、インタレスト集約の存在下でインタレストルーピングを検出することができるＣＣＮシステムを提供する。具体的には、ＣＣＮシステムは、コンテンツルータの全ての隣接者によって報告された名称接頭辞までの距離を記憶する拡張転送情報ベース（ＦＩＢ）の単純な検索に基づいてインタレストループを検出する。
【００１６】
ＣＣＮアーキテクチャ
一般に、ＣＣＮは、インタレスト及びコンテンツオブジェクトという２つの種類のメッセージを使用する。インタレストは、コンテンツオブジェクトの「名称」とも称され且つそのオブジェクトについての要求として機能する階層的構造化可変長識別子（ＨＳＶＬＩ）を担持する。ネットワーク要素（例えば、ルータ）が同じ名称についての複数のインタレストを受信した場合、それはそれらのインタレストを集約することができる。一致するコンテンツオブジェクトとともにインタレストの経路に沿ったネットワーク要素は、インタレストを満たすそのオブジェクトをキャッシュして返送することができる。コンテンツオブジェクトは、インタレストの発信元へのインタレストの逆経路をたどる。
【００１７】
本開示において使用される用語は、一般に、以下のように定義される（それらの解釈はそのように限定されるものではない）。
【００１８】
「ＨＳＶＬＩ」：名称とも称される階層的構造化可変長識別子である。それは、可変長オクテット文字列とすることができる名称要素の順序付きリストである。人間が読める形式において、ｃｃｎｘ：／ｐａｔｈ／ｐａｒｔなどの形式で表現することができる。また、ＨＳＶＬＩは、人間が読めるものでなくてもよい。上述したように、ＨＳＶＬＩは、コンテンツを指し、それらは、コンテンツについての組織的構造を表現することができ且つ人間にとって少なくとも部分的に有意とすることができるのが望ましい。ＨＳＶＬＩの個別の要素は、任意長を有することができる。さらにまた、ＨＳＶＬＩは、明示的に区切られた要素を有することができ、バイトの任意のシーケンスを含むことができ、人間が読める文字に限定されるものではない。最長接頭辞一致検索は、ＨＳＶＬＩを有するパケットの転送に重要である。例えば、「／ｐａｒｃ／ｈｏｍｅ／ｂｏｂ」におけるインタレストを示すＨＳＶＬＩは、「／ｐａｒｃ／ｈｏｍｅ／ｂｏｂ／ｔｅｓｔ．ｔｘｔ」及び「／ｐａｒｃ／ｈｏｍｅ／ｂｏｂ／ｂａｒ．ｔｘｔ」の双方に一致する。名称要素の数の観点で最長の一致は、最も特異的であるために最良であると考えられる。ＨＳＶＬＩの詳細な説明は、２００９年９月２３日に出願された発明者Ｖａｎ  Ｌ．  Ｊａｃｏｂｓｏｎ及びＪａｍｅｓ  Ｄ．  Ｔｈｏｒｎｔｏｎによる「階層的構造化可変長識別子を有するパケットを転送するためのシステム」と題された米国特許第８，１６０，０６９号明細書においてみることができる。
【００１９】
「インタレスト」：コンテンツオブジェクトについての要求である。インタレストは、同じ名称接頭辞を有する複数のオブジェクトを選択するために使用することができるＨＳＶＬＩ名称接頭辞及び他の任意のセレクタを指定する。名称がインタレスト名称接頭辞と一致する（及び、必要に応じて発行者鍵ＩＤなど他の要求されたパラメータが一致する）任意のコンテンツオブジェクトは、インタレストを満たす。
【００２０】
「コンテンツオブジェクト」：インタレストに応答して送信されたデータオブジェクトである。それは、暗号化署名を介して互いに結合しているＨＳＶＬＩ名称及びコンテンツペイロードを有する。必要に応じて、全てのコンテンツオブジェクトは、コンテンツオブジェクトのＳＨＡ−２５６ダイジェストから構成された暗黙的な端末名称要素を有する。１つの実施形態において、暗黙的なダイジェストは、有線で転写されないが、必要に応じて、各ホップにおいて計算される。この開示において、用語「コンテンツオブジェクト」及び用語「名称付きデータオブジェクト（ＮＤＯ）」は互換性がある。
【００２１】
「フェース」：ＣＣＮにおいて、用語フェースは、インターフェースの概念の一般化である。フェースは、ネットワーク又は直接アプリケーションパーティに接続されることができる。フェースは、特定のネットワークインターフェース上でブロードキャスト又はマルチキャストパケットを送受信するか又は下層伝送においてポイントツーポイントアドレッシングを使用して若しくはトンネル（例えば、ＴＣＰトンネル）を使用してパケットを送受信するように構成されることができる。フェースはまた、ＵＤＰ又はＯＳ固有のプロセス間通信経路のようなカプセル化を介して、同じマシン上で実行されている単一のアプリケーションプロセスへの接続とすることができる。全てのメッセージは、フェースを介して到達し、フェースを介して送信される。この開示において、用語「隣接者」は、用語「フェース」と互換可能であり、インタレストの到来又は発信インターフェースを指す。
【００２２】
前述したように、ＨＳＶＬＩは、コンテンツの一部を示し、階層的に構造化されており、最も一般的なレベルから最も特定のレベルまで順序付けられた連続要素を含む。各ＨＳＶＬＩの長さは固定されていない。コンテンツ中心ネットワークにおいて、従来のＩＰネットワークとは異なり、パケットは、ＨＳＶＬＩによって識別されることができる。例えば、「ａｂｃｄ／ｂｏｂ／ｐａｐｅｒｓ／ｃｃｎ／ｎｅｗｓ」は、コンテンツの名称とすることができ、対応するパケット、すなわち、「ＡＢＣＤ」と名付けられた組織における「Ｂｏｂ」と名付けられたユーザについての新聞の「ｃｃｎ」コレクションからの「ｎｅｗｓ」記事を識別する。コンテンツの一部を要求するために、ノードは、コンテンツの名称によってそのコンテンツにおけるインタレストを表現する（例えば、ブロードキャストする）。コンテンツの一部におけるインタレストは、コンテンツの名称又は識別子に応じたコンテンツについてのクエリとすることができる。コンテンツは、ネットワークにおいて利用可能な場合、コンテンツを記憶する任意のノードから要求ノードに対して返送される。ルーティングインフラストラクチャは、情報を有する可能性が高い有望なノードに対してインタレストをインテリジェントに伝播した後、インタレストメッセージが移動する逆経路に沿って利用可能なコンテンツを運ぶ。基本的に、コンテンツオブジェクトは、インタレストメッセージによって残されたブレッドクラムにしたがい、それゆえに要求ノードに到達する。
【００２３】
図１は、本発明の実施形態にかかる、ネットワークの例示的なアーキテクチャを図示している。この例において、ネットワーク１８０は、ノード１００〜１４５を備える。ネットワーク内の各ノードは、１つ以上の他のノードに接続されている。ネットワーク接続１８５は、そのような接続の例である。ネットワーク接続は実線で示されているが、各線はまた、１つのノードが他のノードに結合することができるサブネットワーク又はスーパーネットワークを表現することができる。ネットワーク１８０は、コンテンツ中心のローカルネットワーク、スーパーネットワーク又はサブネットワークとすることができる。１つのネットワーク内のノードが他のネットワーク内のノードに到達することができるように、これらのネットワークのそれぞれは、相互接続することができる。ネットワーク接続は、ブロードバンド、無線、電話、衛星又は任意の種類のネットワーク接続とすることができる。ノードは、コンピュータシステム、ユーザを表すエンドポイント及び／又はインタレストを生成したり若しくはコンテンツを発信したりすることができる装置とすることができる。
【００２４】
本発明の実施形態によれば、消費者は、コンテンツの一部についてのインタレストを生成し、ネットワーク１８０内のノードに対してそのインタレストを転送することができる。コンテンツの一部は、ネットワークの内部又は外部に配置することができる発行者又はコンテンツ提供者によってネットワーク１８０内のノードに記憶されることができる。例えば、図１において、コンテンツの一部におけるインタレストは、ノード１０５において発生する。コンテンツがノードにおいて利用可能でない場合、インタレストは、第１のノードに結合された１つ以上のノードへと流れる。例えば、図１において、インタレストは、利用可能なコンテンツを有していないノード１１５に流れる（インタレストフロー１５０）。次に、インタレストは、ノード１１５から同様にコンテンツを有しないノード１２５に流れる（インタレストフロー１５５）。そして、インタレストは、利用可能なコンテンツを有するノード１３０に流れる（インタレストフロー１６０）。そして、コンテンツオブジェクトのフローは、コンテンツが配信されるノード１０５に到達するまでその経路を引き返す（コンテンツフロー１６５、１７０及び１７５）。認証などの他のプロセスは、コンテンツのフローに含まれることができる。
【００２５】
ネットワーク１８０において、コンテンツホルダ（ノード１３０）とインタレスト生成ノード（ノード１０５）との間の経路における任意数の中間ノード（ノード１００〜１４５）は、それがネットワークを介して移動するのにともないコンテンツのローカルコピーをキャッシュする際に加入することができる。キャッシングは、ローカルにキャッシュされたコンテンツに対するアクセスを暗黙的に共有することによって他の加入者の近傍に位置する第２の加入者についてのネットワーク負荷を低減する。
【００２６】
既存のＣＣＮ又はＮＤＮにおいて、各ノードは（ルータとも称される）は、転送情報ベース（ＦＩＢ）、コンテンツストア（ＣＳ）及び保留インタレストテーブル（ＰＩＴ）を含む３つの主要なデータ構造を維持する。転送プレーンは、要求されたコンテンツのコピーを有して公表するノードに向けてインタレストを転送し、インタレストが移動する逆経路上にそれらを要求した消費者に対してＮＤＯ又は他の応答を返送するために、これらの３つのテーブルに記憶された情報を使用する。
【００２７】
ＦＩＢは、一致コンテンツオブジェクトのポテンシャルソースに向けてインタレストパケットを転送するために使用される。典型的に、ルーティングプロトコルは、ネットワーク内の全てのノード間でＦＩＢを投入するために使用される。従来のＣＣＮにおいて、ＦＩＢエントリは、大抵の場合、一致するインタレストが転送されるべき少なくとも１つのフェースの物理アドレスを含む各エントリとともに名称接頭辞によってインデックス付けされる。ＮＤＮにおいて、名称接頭辞についてのＦＩＢエントリはまた、その後にエントリが削除されることができる失効時間、インターフェースを介したラウンドトリップ時間、レート制限、及び、インターフェースがデータを戻すことができるかできないことを知っているか知っていないかを記載するステータス情報を含む。インタレストメッセージを転送するとき、一致するエントリをみつけるためにＦＩＢにおいて名称最長接頭辞一致検索が実行される。
【００２８】
コンテンツストア（ＣＳ）は、ＩＰルータにおいて使用されるバッファメモリと同様である。より具体的には、ＣＳは、このノードを通過するコンテンツオブジェクトを一時的にバッファリングし、異なる消費者による効率的なデータ検索を可能とする。ルータがインタレストパケットを受信したとき、それは、上流のインタレストを発行する前にそのコンテンツストアに一致するコンテンツオブジェクトがあるかどうかを最初にチェックする。
【００２９】
保留インタレストテーブル（ＰＩＴ）は、インタレスト状態のキャッシュとして機能する。ＰＩＴは、返送されたコンテンツオブジェクト又はＮＤＯがその要求者に対して逆インタレスト経路をたどって下流に送信されることができるように上流からコンテンツソースに向けて転送されるインタレストを追跡する。これは、上流及び下流のネットワークフローを維持する。ＣＣＮ及びＮＤＮはまた、インタレストがそれらのソースを開示せず且つインタレスト集約を有効とするのを可能とするためにＰＩＴを使用することができる。インタレストパケットのみがルーティングされる。返送コンテンツオブジェクト又はＮＤＯは、コンテンツ要求者に対してインタレストパケットの逆に軌跡をたどる。ＰＩＴエントリは、同じＮＤＯ名称について処理された各ノンスについての１つのタプルを有する１つ以上のタプルのベクトルから構成される。各タプルは、使用されるノンス、到来インターフェース及び発信インターフェースを記載する。各ＰＩＴエントリはまた、ＮＤＯをみつけることができるノードまでのラウンドトリップ時間よりも大きい寿命を有する。
【００３０】
インタレストパケットが特定のフェースにおいてルータに到達すると、コンテンツ名又はＨＳＶＬＩに基づいて最長一致検索を行うことができる。名称検索のために使用されるインデックス構造は、ＣＳ一致がＰＩＴ一致よりも好ましいように順序付けられ、ＦＩＢ一致よりも好ましい。したがって、インタレストに一致するコンテンツオブジェクトがＣＳに既にある場合、コンテンツオブジェクトは、インタレストが到達したフェースを介して送出され、インタレストは廃棄される。そうでない場合、ＰＩＴは、一致をみつけることができるかどうかを確認するためにチェックされる。ＮＤＮにおいて、インタレストが要求されたコンテンツについてのＰＩＴエントリに記憶されたものとは異なるノンスを記載する場合、ルータは、インタレストを転送することなく、ＰＩＴエントリにインタレストが受信された到来フェース及びノンスを追加することによってインタレストを「集約」する。一方、インタレストにおける同じノンスが要求されたコンテンツについてのＰＩＴエントリに記載されている場合、ルータは、インタレストが移動する逆経路上にＮＡＣＫを送信する。ＣＣＮにおいて、集約は、要求されたコンテンツについてのＰＩＴエントリに記載されていないフェースからインタレストが受信された場合に行うことができ、同じフェースから受信した繰り返されたインタレストは単に削除される。
【００３１】
ルータがそのＣＳ及びＰＩＴにおいて一致をみつけなかった場合、ルータは、最高の接頭辞一致についてそのＦＩＢに記載されているルートに沿ってインタレストを転送する。ＮＤＮにおいて、ルータは、それがコンテンツをもたらすことができることが知られており且つその性能がコンテンツを同様にもたらすことができる他のフェースよりも高くランク付けされている場合、インタレストを転送するようにフェースを選択することができる。フェースのランキングは、他のルータとは独立してルータによって行うことができる。
【００３２】
未検出のインタレストルーピング
図２Ａは、情報中心ネットワーク（ＩＣＮ）における例示的なインタレストルーピングを図示する図である。図２Ａにおいて、ネットワーク２００は、ルータ２０２〜２１４などの相互接続された多数のルータを含む。図２Ａにおける矢印線は、各ルータに記憶されているＦＩＢエントリにしたがってルータ２１４によって公表されたコンテンツへの次ホップを示している。わかるように、ルータ２０４、２０６及び２０８から構成されるループが存在する。インタレストは、ルータ２０４からルータ２０６、２０８に対して転送されてルータ２０４に戻ることができる。図２Ａにおいて、太線は、隣接者の体感的な性能が細線で示された隣接者よりも良好であることを示している。例えば、ルータ２０４に対して、ルータ２０６は、ルータ２１０よりも優れた性能の隣接者である。ＦＩＢにおいて暗示された複数の経路がループフリーではないことから、全てのルーティングテーブルが一致しているにもかかわらず、長期間のインタレストループが存在することができることが図２Ａからわかる。この場合、ＦＩＢにおける隣接者のランキングは、接頭辞に向かってフェース又は経路の体感的な性能のために、より大きなホップ数を有する経路が小さいホップ数を有する経路よりも高くランク付けされることができるようなものとすることができる。
【００３３】
また、図２Ａにおいて、破線は、リンク及び経路にわたるインタレストの移動を示しており、異なる破線パターンが異なる発信元によるインタレストを表し、それゆえに異なるノンスを有する。イベントがルータに到達する時間はｔｉによって示される。例えば、ルータ２０４は、ｔ１において、ルータ２０２からインタレストを受信し、ｔ３において、ルータ２０８から同じ名称についてのインタレストであるが異なるノンスを有するインタレストを受信する。同様に、ルータ２０８は、ｔ４において、ルータ２０６からインタレストを受信する。理想的には、ルータが以前にそれ自体によって送出されたＮＤＯ名称及びノンスによって識別されるような同じインタレストを受信することを通知する場合に、インタレストループが検出されることができる。しかしながら、例えば図２Ａに示される例において、インタレスト集約に起因して、ルータ２０４は、インタレストのルーピングを検出することができない。具体的には、図２Ａは、ルータ２０２からルータ２０４に対して送信された同じインタレストであるインタレスト（ｎ（ｊ），ｎｏｎｃｅ１）をルータ２０８がｔ４においてルータ２０６から受信することを示している。しかしながら、ルータ２０４に対してそのようなインタレストを転送する代わりに、ルータ２０８は、このインタレストをｔ３においてルータ２０４に到達した異なるノンスのインタレスト（ｎ（ｊ），ｎｏｎｃｅ２）と集約する。換言すれば、ルータ２０４は、ルータ２０８から送信された（ｎ（ｊ），ｎｏｎｃｅ２）のみをみる。同様に、ルータ２０４はまた、ルータ２０８から受信したインタレスト（すなわち、（ｎ（ｊ），ｎｏｎｃｅ２））を集約し、ルータ２０２から受信したインタレスト（すなわち、（ｎ（ｊ），ｎｏｎｃｅ１））を送出するのみである。したがって、インタレストループは、ルータ２０４によって検出されることなく形成される。
【００３４】
さらに、ルーティングテーブルがネットワーク又はコンテンツダイナミクスの結果として一致していない状況において、インタレストループは、制御プレーンがコンテンツに対する単一パスルーティングのみをサポートしている場合であっても検出されなくすることができる。図２Ｂは、ＩＣＮにおける例示的なインタレストルーピングを図示する図である。図２Ｂは、図２Ｂに示される例において、ルーティングが単一パスであり、ルータ２０４と２１０との間のリンクに障害があるとき、ｔ１においてネットワークトポロジが変更することを除き、図２Ａに示されたのと同じ例示的なネットワーク２００を示している。図２Ａに示される例と同様に、ルータ２０４は、ルータ２０８からのインタレストを集約し、ルータ２０８は、ルータ２０６からのインタレストを集約し、これらの組み合わせステップは、一時的なインタレストルーピングの検出を妨げる。この例において、ルーピングの問題は、ルータ２１４によって通知される接頭辞に関するインタレストについてルータ２０８よりもむしろルータ２１２を使用するようにルータ２０６を強制することによって回避することができると思われる。しかしながら、リンク（ノード２０６、ノード２１２）が例において削除された場合には同じルーピングの問題が存在する。ＦＩＢが投入され且つフェースがランク付けされる方法は、ＰＩＴに対して行われた更新とは無関係であることに留意されたい。
【００３５】
実際に、ＮＤＮ転送戦略は、ノンスが固有にインタレストを示すためであったとしても、インタレストループが発生する安定したエラーのないネットワークにおいて安全ではないことを証明することができる。さらに、インタレスト識別データの照合に基づくインタレスト集約及びインタレストループ検出による転送戦略が安全ではないことも証明することができる。簡略化された証明は、ＮＤＮのインタレスト処理戦略及びインタレスト識別データを照合することによってインタレストループを検出しようとする任意の転送戦略を、サイクルにわたる分散終端検出の問題にマッピングすることであり、ここで、インタレストは、アルゴリズムのトークンとして機能する。インタレスト集約は、リング内の任意のノードが以前に作成された異なるトークンを有するリング（インタレストループ）を移動するトークンをなくす。したがって、リング上の正確な終端検出（すなわち、インタレストループ検出）は、インタレスト集約の存在下では保証することができない。対応するＰＩＴエントリは、ルーティングループを移動する集約されたインタレストに対して応答が送信されないとしたら最終的にタイムアウトすることから、インタレストは、永遠にルーティングループに沿って再循環させることができない。しかしながら、未検出のインタレストループは、ループを移動する小さな割合のインタレストについてもエンドツーエンド遅延及びコンテンツルータによって記憶されたＰＩＴエントリ数の大幅な増加を引き起こすことがある。
【００３６】
ＦＩＢの拡張検索を有するＣＣＮ（ＣＣＮ−ＥＬＦ）
ＣＣＮ−ＥＬＦアプローチは、インタレストが集約された場合であってもインタレストループが検出されないことを保証し、ＮＤＮ及びＣＣＮにおいて使用されるパケットフォーマットに対するいかなる変更も必要としない。これは、ホップ数情報を伝送するためにインタレストに依存する他のループ検出解決策とは対照的である。
【００３７】
動作中において、ＣＣＮ−ＥＬＦは、ＮＤＯの名称及びＦＩＢに記憶された距離情報を使用することにより、インタレスト、ＮＤＯ及び制御メッセージ（例えば、ＮＡＣＫ）の正確な転送を保証する。距離情報は、ルータが、インタレストによってネットワークをフラッディングするか又はコンテンツのネットワーク検索のランダムウォークを行うよりも、要求されたコンテンツの最も近いインスタンスに向けてインタレストを転送するのを可能とすることができることに留意されたい。同じ情報はまた、インタレストが要求されたコンテンツを公表したノードにそれらが近づくように転送されることを保証するために使用することができる。
【００３８】
この開示において、ＮＤＯｊの名称は、ｎ（ｊ）によって表され、用語「隣接者」及び「フェース」は、互換可能に使用される。ルータｉの隣接者のセットは、Ｎｉによって表される。ＮＤＯｎ（ｊ）を要求するノードｋによって転送されるインタレストは、Ｉｋ［ｎ（ｊ）］によって表される。インタレストに応答してルータｋによって送信されたＮＤＯは、Ｄｋ［ｎ（ｊ），ｓｐ（ｊ）］によって表され、ｓｐ（ｊ）は、コンテンツオブジェクトを検証するために必要に応じて使用されるセキュリティペイロードである。ルータｋによって送信されたインタレストに対するＮＡＣＫは、ＮＩｋ［ｎ（ｊ），ＣＯＤＥ］によって表され、ＮＡＣＫが送信された理由を示すＮＤＯの名称を記載する（ｎ（ｊ）及びコードＣＯＤＥ）。
【００３９】
図３は、本発明の実施形態にかかる、例示的な転送情報ベース（ＦＩＢ）を図示する図である。図３において、ＦＩＢ３００は、コンテンツ名称接頭辞を使用してインデックス付けされた多数のエントリを含む。各エントリは、対応する名称接頭辞に対する現在のルータの各隣接者についてのタプルのセットを含む。例えば、エントリ３０２は、名称接頭辞ｎ（ｊ）＊に対応し、多数のタプルを含む。隣接者ｐのタプルは、隣接者ｐの名称及び隣接者ｐから名称接頭辞ｎ（ｊ）＊までの距離（例えば、ホップ数）を記載する。同様に、隣接者ｑについてのタプルは、隣接者ｑの名称及び隣接者ｑから名称接頭辞ｎ（ｊ）＊までの距離を記載する。表記のために、ルータｉにおけるＦＩＢは、ＦＩＢｉとして表され、名称接頭辞ｎ（ｊ）＊についてのＦＩＢエントリは、
【００４０】
【数１】
2017063413.tif 000002
【００４１】
として表され、隣接者ｑから名称接頭辞ｎ（ｊ）＊までの距離は、Ｄ（ｉ，ｎ（ｊ）＊，ｑ）として表される。その隣接者から接頭辞までの距離に加えて、いくつかの実施形態において、ルータのＦＩＢはまた、隣接者のランキングを記憶することができる。そのようなランキングはまた、インタレスト転送プロセスにおいて重要な役割を果たすことができる。
【００４２】
図４は、本発明の実施形態にかかる、例示的な保留インタレストテーブル（ＰＩＴ）を図示する図である。図４において、ＰＩＴ４００は、ＮＤＯの名称を使用してインデックス付けされた多数のエントリを含む。ルータｉにおいて、ＰＩＴは、ＰＩＴｉとして表され、
【００４３】
【数２】
2017063413.tif 000003
【００４４】
は、名称ｎ（ｊ）を有するＰＩＴｉにおいて作成されるエントリを示す。ＰＩＴにおける各エントリは、ＮＤＯの名称、インタレストがＮＤＯによって満たされたかどうかを記載するフラグ、インタレストを転送する際にルータによって想定される距離、ＮＤＯについてのインタレストが受信される到来隣接者のセット、ルータがそのインタレストを転送する発信隣接者のセット、同じインタレストについて許可される再送信回数、及び、インタレストについての残り寿命を指定する。ＰＩＴエントリの各要素についての表記が図４に示されている。例えば、ＰＩＴエントリ
【００４５】
【数３】
2017063413.tif 000004
【００４６】
又は図４におけるエントリ４０２は、ＮＤＯ名称ｎ（ｊ）；フラグ
【００４７】
【数４】
2017063413.tif 000005
【００４８】
；名称接頭辞ｎ（ｊ）＊に対してインタレストＩｉ［ｎ（ｊ）］を転送する際にルータｉによって想定される距離Ｄ（ｉ，ｎ（ｊ））；ルータｉがｎ（ｊ）についてのインタレストを受信した到来隣接者のセット
【００４９】
【数５】
2017063413.tif 000006
【００５０】
；ルータｉがｎ（ｊ）についてのインタレストを送信した発信隣接者のセット
【００５１】
【数６】
2017063413.tif 000007
【００５２】
；許可される再送信回数
【００５３】
【数７】
2017063413.tif 000008
【００５４】
；及び残り寿命
【００５５】
【数８】
2017063413.tif 000009
【００５６】
を含む。
【００５７】
本発明の実施形態において、ルータがインタレストを受信したとき、それらは、まず、以下の２つの条件のいずれかが満たされる場合、ルータｉが隣接者ｋからインタレストＩｋ［ｎ（ｊ）］を受け入れることができることを記載するＦＩＢの拡張検索（ＥＬＦ）規則を使用してインタレストを受け入れるかどうかを判定する。
【００５８】
【数９】
2017063413.tif 000010
【００５９】
条件（１）は、ルータｉが隣接者ｋよりも名称接頭辞ｎ（ｊ）＊に近い隣接者を介してｎ（ｊ）についての新たなインタレストを転送することができることを判定する場合にのみ、ルータｉが隣接者ｋからインタレストを受け入れることを保証する。条件（２）は、ｎ（ｊ）についてのそのインタレストを送信したときのルータｉからｎ（ｊ）＊までの距離が、インタレストが隣接者ｋから受信されたときの隣接者ｋからｎ（ｊ）＊までの距離と比較して小さいことを判定する場合にのみ、ルータｉが隣接者ｋからインタレストを受け入れることを保証する。ＥＬＦ規則は、ルータから名称接頭辞までの距離（例えば、ホップ数）を測定するために使用される特定のメトリック、又は、１つ以上の経路が指定された名称接頭辞について維持されているかどうかとは無関係である。
【００６０】
図５は、本発明の実施形態にかかる、例示的なＩＣＮルータのアーキテクチャを表す図である。図５において、ＩＣＮルータ５００は、フェース５０２、５０４及び５０６などの多数のフェースと、インタレスト処理モジュール５０８と、転送モジュール５１０と、ＮＤＯ処理モジュール５１２と、制御メッセージ生成モジュール５１４と、データベース５１６とを含む。
【００６１】
フェース５０２〜５０６は、物理インターフェースのみならず、インタレスト及びＮＤＯを含むパケットの送受信が可能なアプリケーションプロセスを含むことができる。インタレスト処理モジュール５０８は、様々なフェース上で受信されたインタレストメッセージを処理する責を担う。いくつかの実施形態において、インタレスト処理モジュール５０８は、上述したＥＬＦ規則に基づいて到来インタレストを受け入れるかどうかを判定するように構成されることができる。転送モジュール５１０は、インタレスト又はコンテンツオブジェクトなどのパケットをフェースに対して転送する責を担う。ＮＤＯ処理モジュール５１２は、インタレストに応答して受信したＮＤＯメッセージを処理する責を担う。制御メッセージ生成モジュール５１４は、異なるＮＡＣＫメッセージを含むことができる制御メッセージを生成する。いくつかの実施形態において、制御メッセージ生成モジュール５１４は、それらに限定されるものではないが、インタレストループが検出されたとき、要求されたコンテンツに向かうルートがみつからないとき、コンテンツがみつからないとき、及び、ＰＩＴエントリの期限が切れたときを含む様々な条件下でＮＡＣＫメッセージを生成する。データベース５１６は、コンテンツストア、転送情報ベース及び保留情報テーブルという３つの必須のデータ構造を記憶する。
【００６２】
図６は、本発明の実施形態にかかる、例示的なインタレスト処理アルゴリズムを図示するための図である。名称接頭辞に対する利用可能な経路の負荷分散、輻輳制御又は同時に複数の経路にわたるインタレストの転送などの特定のネットワークトラフィック制御の問題は、この開示の範囲を超えており、ここで記載されることはない。簡略化するために、全てのインタレストの再送信は、エンドツーエンドベースで（すなわち、中継ルータよりもむしろコンテンツの消費者によって）行われるものとする。したがって、ルータは、隣接者に障害がある場合又はインタレストに対するＮＡＣＫが受信された場合にいかなる「ローカルリペア」も提供しようとしない。
【００６３】
図５〜図６を参照すると、ルータｉのインタレスト処理モジュール５０８が隣接者ｋからインタレストＩｋ［ｎ（ｊ）］を受信したとき、照合のためにコンテンツストアＣＳｉを最初にチェックすることがわかる。一致がみつかった場合、転送モジュール５１０は、隣接者ｋに対して一致するＮＤＯを返送する。Ｄｉ［ｎ（ｊ），ｓｐ（ｊ）］がインタレストＩｋ［ｎ（ｊ）］に応答して送信されたコンテンツオブジェクトメッセージを表すことに留意されたい。
【００６４】
一致がコンテンツストア及びＰＩＴにおいてみつからない場合（図６における５行目）、インタレスト処理モジュール５０８は、照合のためにＦＩＢをチェックする。一致がＦＩＢにおいてみつからない場合、要求されたコンテンツまでのルートが存在しないと判定される。これに応答して、制御メッセージ生成モジュール５１４は、ルートがみつからないためにＮＡＣＫが発行されたことを記載するＮＡＣＫメッセージＮＩｉ［ｎ（ｊ），ルートなし］を生成する（図６における６行目）。その後、転送モジュール５１０は、隣接者ｋに対してＮＡＣＫを転送し、インタレスト処理モジュール５０８は、受信したインタレストを削除する（図６における７行目）。
【００６５】
一致がＦＩＢにおいてみつかった場合、インタレスト処理モジュール５０８は、上述した条件（１）が満たされたかどうか、すなわち、そのインタレストを送信したときにルータｉがルータｋよりも名称接頭辞ｎ（ｊ）＊に近い隣接者νが存在するかどうかを判定する。そうである場合、インタレストが転送されることができると判定され、転送モジュール５１０は、適切な転送アルゴリズムに基づいてンタレストを転送する（図６における９〜１２行目）。さらに、ＰＩＴエントリは、到来隣接者リストにルータｋを且つ発信隣接者リストにルータνを追加することによってｎ（ｊ）について作成される。残り寿命は、最大インタレスト寿命（ＭＩＬ）として設定される。ＭＩＬは、そのＰＩＴからインタレストを削除する前にルータによって想定され、過剰数の再送信を排除するのに十分な大きさであるが、ＮＤＯメッセージ又はＮＡＣＫが障害又は送信エラーに起因して送信されることができないあまりにも多くのインタレストをＰＩＴに記憶させるほど大きくはない。いくつかの実施形態において、ＭＩＬは、数秒（例えば、１から１０秒）の範囲に設定される。
【００６６】
条件（１）が満たされない場合、インタレストがループを移動することができると判定される。これに応答して、制御メッセージ生成モジュール５１４は、ループがみつかったためにＮＡＣＫが発行されたことを記載するＮＡＣＫメッセージＮＩｉ［ｎ（ｊ），ループ］を生成する。その後、転送モジュール５１０は、隣接者ｋに対してＮＡＣＫを転送し、インタレスト処理モジュール５０８は、受信したインタレストを削除する（図６における１４行目）。
【００６７】
インタレスト名称の一致がＰＩＴにおいてみつかった場合、インタレスト処理モジュール５０８は、上述した条件（２）が満たされたかどうか、すなわち、双方のルータがそれらのインタレストを送信したときにルータｉがルータｋよりも名称接頭辞ｎ（ｊ）＊に近かったかどうかを判定する。そうである場合、インタレストが集約されることができると判定される。これに応答して、ＰＩＴは、ｎ（ｊ）についてのインタレストが受信される到来隣接者のセットにルータｋを追加することによって更新される（図６における１８〜１９行目）。条件（２）が満たされない場合、インタレストがループを移動することができると判定される。これに応答して、制御メッセージ生成モジュール５１４は、ループがみつかったためにＮＡＣＫが発行されたことを記載するＮＡＣＫメッセージＮＩｉ［ｎ（ｊ），ループ］を生成する。その後、転送モジュール５１０は、隣接者ｋに対してＮＡＣＫを転送し、インタレスト処理モジュール５０８は、受信したインタレストを削除する（図６における２１行目）。
【００６８】
図６に示されるインタレスト処理アルゴリズムは、ルータｉがＥＬＦ規則の条件（１）を満たす接頭辞ｎ（ｊ）＊についてのＦＩＢに記憶された隣接者のランク付けリストにおける第１の隣接者νを単に選択する単純なインタレスト転送戦略を提供する。より洗練された戦略はまた、コンテンツに向かう複数のルート間の負荷分散を達成するために考案することができる。さらに、同じインタレストは、同時に複数の経路を介して転送されることができる。そのような場合、コンテンツは、インタレストが正常に移動する各経路を介して返送されることができる。有効であるために、しかしながら、これらのアプローチは、制御プレーンにおけるループフリーマルチパスルーティングプロトコルの採用を必要とする。例えば、そのようなルーティングプロトコルは、距離ベースのルーティングを含むことができる。距離ベースのルーティングの詳細な説明は、２０１４年１２月１６日に出願された発明者Ｊｏｓｅ  Ｊ．  Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓによる「距離ベースのインタレスト転送のためのシステム及び方法」と題された米国特許出願第１４／５７２，６０８号（代理人整理番号ＰＡＲＣ−２０１４１０７８ＵＳ０１）においてみることができる。距離ベースのルーティングに基づいて、制御プレーンは、長期間の性能指標を使用してコンテンツ接頭辞に対する有効なマルチパスを確立し、データプレーンは、ルーピングに起因するバックトラッキングに関連付けられた長い遅延のリスクなしに、集約規則によるホップ数転送（ＨＦＡＲ）及び短期間の性能指標を使用してこれらの経路を利用する。
【００６９】
例示的な動作
図７Ａ〜図７Ｂは、本発明の実施形態にかかる、例示的なＣＣＮ−ＥＬＦの動作を図示している。具体的には、図７Ａは、制御プレーンによって判定されたルーティング情報を図示しており、図７Ｂは、インタレストがリンクを移動する方法を図示している。図において、ネットワーク７００は、ノード７０２〜７１４などの多数のノードを含み、矢印線は、ルータに記憶されているＦＩＢエントリにしたがってルータ７１４によって公表された（名称ｎ（ｊ）を有する）コンテンツまでの次ホップを示している。矢印線の太線は、フェースの体感的な性能を示している。フェースを指す太線は、示されたフェースが細線によって指されたフェースよりも良好に動作することを意味する。例えば、リンク（ノード７０６、ノード７０８）は、リンク（ノード７０４、ノード７０６）よりも良好に動作する。図において、ルータからその隣接者へと発信する各リンクにおいて、一対の数字が記載されており、これは、ｎ（ｊ）（ノード７１４）まで隣接者を通る距離（第１の番号）と、ルータのＦＩＢに応じた隣接者のランキング（第２の番号）とを示す。いくつかの実施形態において、距離はホップ数とすることができる。同じリンクについて、２つの対が存在する可能性があり、各対が対に近いルータにおけるＦＩＢに記憶されることに留意されたい。例えば、ルータ７０４からルータ７０６までのリンクにおいて、２つの番号対、対（４，１）及び対（５，２）がリンクの隣に示されている。番号対（４，１）は、ルータ７０４に隣接し且つルータ７０４のＦＩＢに記憶されており、番号対（５，２）は、ルータ７０６に隣接し且つルータ７０６のＦＩＢに記憶される。具体的には、ルータ７０４に隣接する番号対（４，１）は、その隣接者７０６を介したｎ（ｊ）までのホップ数が４であり、隣接者７０６がルータ７０４のＦＩＢにおいて番号１にランク付けしていることを示す。一方、ルータ７０６に隣接する番号対（５，２）は、その隣接者７０４からｎ（ｊ）までのホップ数が５であり、隣接者７０４がルータ７０６のＦＩＢにおいて番号２にランク付けしていることを示す。
【００７０】
表記のために、トリプレット（ν，ｈ，ｒ）は、フェース、そのホップ数及びそのランキングを表すために使用することができる。例えば、ＦＩＢｎｏｄｅ７０４におけるエントリに基づくノード７０４からｎ（ｊ）（ノード７１４）までの距離は、（ノード７０６，４，１）、（ノード７１０，４，２）及び（ノード７０８，６，３）であり、ＦＩＢｎｏｄｅ７０６におけるエントリに基づくノード７０６からｎ（ｊ）までの距離は、（ノード７０８，６，１）、（ノード７０４，５，２）及び（ノード７１２，３，３）であり、ノード７０８からｎ（ｊ）までは、（ノード７０４，５，２）及び（ノード７０６，５，１）を有する。
【００７１】
図７Ｂは、ＣＣＮ−ＥＬＦに基づくインタレスト転送シナリオを示している。図７Ｂに示される例において、ルータ７０４は、時間ｔ１において、ルータ７０２から名称ｎ（ｊ）についてのインタレストＩ［ｎ（ｊ）］を受信する。ルータ７０６は、ＥＬＦ規則を満たすｎ（ｊ）までの最高ランクの距離を提供することから（すなわち、Ｄ（ノード７０４，ｎ（ｊ）＊，ノード７０６）＝３＜５＝Ｄ（ノード７０４，ｎ（ｊ）＊，ノード７０２））、ルータ７０４は、ルータ７０６に対してインタレストＩ［ｎ（ｊ）］を転送する。そして、ルータ７０４は、そのＰＩＴにＤ（ノード７０４、ｎ（ｊ））＝４を設定する。ルータ７０６は、時間ｔ２において、ルータ７０４からインタレストを受信し、ＥＬＦ規則がまた、その隣接者のうちの少なくとも１つによって満たされることから（すなわち、Ｄ（ノード７０６，ｎ（ｊ）＊，ノード７１２）＝２＜４＝Ｄ（ノード７０６，ｎ（ｊ）＊，ノード７０４））、それを受け入れる。したがって、ルータ７０６は、時間ｔ３においてインタレストを受信するルータ７１２に対してインタレストを転送する。また、時間ｔ３において、ＥＬＦ規則の条件（２）が満たされることから（すなわち、Ｄ（ノード７０４，ｎ（ｊ）＊，ノード７０８）＝５＞４＝Ｄ（ノード７０４、ｎ（ｊ）））、ルータ７０８によって生成されたインタレストは、ルータ７０４によって集約される。図２Ａに示されるシナリオとは対照的に、ループは、ＣＣＮ−ＥＬＦの実装に起因して図７Ａにおいては発生しない。
【００７２】
図８Ａ〜図８Ｃは、本発明の実施形態にかかる、例示的なＣＣＮ−ＥＬＦの動作を図示している。具体的には、図８Ａ〜図８Ｃによって示される例は、トポロジ変更が生じたときのＣＣＮ−ＥＬＦが動作する方法を証明するために使用することができる。図において、ネットワーク８００は、ノード８０２〜８１４などの多数のノードを含む。
【００７３】
図８Ａは、時間ｔ０において（リンク（ノード８０４，ノード８１０）が失敗したとき）ルータ８０４がそのＦＩＢを更新し、時間ｔ１において（リンク（ノード８０６，ノード８１２）が失敗したとき）ルータ８０６がそのＦＩＢを更新する旨を示している。インタレストがデータプレーンにおいて転送されている一方で、ルーティングテーブルの更新が制御プレーンにおいて送信されていることから、ルータは、ｎ（ｊ）についての一貫性のないＦＩＢ状態を有することがある。具体的には、図８Ａは、（時間ｔ０において）リンク（ノード８０４，ノード８１０）が失敗するとともに（時間ｔ１において）リンク（ノード８０６，ノード８１２）が失敗した後のインタレストが伝播する時間においてＦＩＢに記憶された距離値のスナップショットを示している。距離のランキングは、図８Ａには示されていないことに留意されたい。図８Ａに示されるように、ルータ８０６がＥＬＦ規則の条件（１）を満たすｎ（ｊ）までの最高ランクの距離を提供することから（すなわち、Ｄ（ノード８０４，ｎ（ｊ）＊，ノード８０６）＝３＜５＝Ｄ（ノード８０４，ｎ（ｊ）＊，ノード８０２））、ルータ８０２からのｎ（ｊ）についてのインタレストが時間ｔ１においてルータ８０４に到達したとき、ルータ８０４は、ルータ８０６に対してインタレストを転送する。インタレストの転送後、ルータ８０４は、そのＰＩＴにＤ（ノード８０４、ｎ（ｊ））＝４を設定する。
【００７４】
図８Ｂは、ルータ８０６がＥＬＦ規則を満たすいかなる隣接者（すなわち、ｎ（ｊ）までの距離が４未満である全ての隣接者）もみつけることができないことから、ルータに記憶されたＦＩＢが一致しないにもかかわらず、ｎ（ｊ）についてのインタレストが時間ｔ２において到達したときに、ルータ８０６がルータ８０４に対してＮＡＣＫを送信する旨を示している。ＥＬＦ規則の条件（２）が満たされることから（すなわち、Ｄ（ノード８０４，ｎ（ｊ）＊，ノード８０８）＝５＞４＝Ｄ（ノード８０４、ｎ（ｊ））、ルータ８０４は、時間ｔ３においてルータ８０８からのインタレストを集約する。図８Ｃは、時間ｔ５において、ルータ８０４が時間ｔ４においてルータ８０６から受信したＮＡＣＫをルータ８０２及び８０８に対して転送する旨を示している。ルータ８０２及び８０８からのインタレストは集約されたことに留意されたい。
【００７５】
有限時間内において、全てのルータのＦＩＢは、リンク（ノード８０４，ノード８１０）及び（ノード８０６，ノード８１２）に対する変更を考慮した新たな最短経路を反映するように更新される。ＦＩＢが一致すると、名称接頭辞ｎ（ｊ）＊におけるオブジェクトに関するインタレストがｎ（ｊ）＊に向かう最短経路に沿って転送される。
【００７６】
ＥＬＦ規則は、インタレストルーピングを回避するための唯一の十分条件であり、ルータにとってそうでないときにインタレストがループを移動していることを前提とすることが可能である。換言すれば、偽のループ検出が発生する可能性がある。図８Ｂにおける例において、ルータ８０６は、ループを発生させることなくルータ８１２に対してインタレストを転送することができる。しかしながら、ＥＬＦ規則は、ルータ８１２によって満たされず、ルータ８０６は、それを選択することができない。制御プレーンにおいて計算される正確な距離を反映するようにＦＩＢが更新される速度を考えると、偽のループ検出はまれであり、偽のループ検出を有することは、長期持続のＰＩＴエントリ（例えば、ルーピングに起因して応答を受信することができず、最終的に数秒後に期限が切れるインタレストについてのエントリ）を有するよりも優れている。したがって、インタレストループ検出についての十分条件は、ＩＣＮにおける正確なインタレスト転送のための良好なベースラインである。
【００７７】
ＣＣＮ−ＥＬＦによって達成される性能の利点は、従来のＩＣＮ（例えば、ＮＤＮ又はＣＣＮ）を使用して達成されるものと比較して顕著である。具体的には、ＣＣＮ−ＥＬＦシステムにおいて使用されるＰＩＴは、はるかに小さい。さらにまた、消費者は、従来のＮＤＮ転送戦略の代わりに、ルータがＣＣＮ−ＥＬＦを実装したときにそれらが要求するコンテンツを取得するか又はコンテンツに関するフィードバックを受信するためのより少ない待ち時間を経験する。
【００７８】
ＦＩＢは、例えば、各接頭辞ｎ（ｊ）＊についての各隣接者によって報告された距離などの距離情報を現在記憶することから、ＣＣＮ−ＥＬＦは、従来のＣＣＮ又はＮＤＮシステムと比較してさらなるＦＩＢ記憶装置を必要とする。これは、ルータｉにおいて（｜Ｄ｜）（｜ＦＩＢｉ｜）（｜Ｎｉ｜）になる。ここで、Ｄは、距離を表すために必要なバイト数であり、｜Ｎｉ｜は、ルータｉの隣接者数であり、｜ＦＩＢｉ｜は、ＦＩＢｉにおけるエントリ数である。一方、ＣＣＮ−ＥＬＦはまた、各ＰＩＴエントリが距離を記憶することから、従来のＮＤＮ又はＣＣＮシステムと比較してさらなるＰＩＴオーバーヘッドも必要とする。ＰＩＴオーバーヘッドは、ルータｉにおいて（｜Ｄ｜）（｜ＰＩＴｉ｜）バイトに対応する。
【００７９】
従来のＣＣＮシステムと比較して、ＣＣＮ−ＥＬＦは、名称接頭辞について維持される各ＦＩＢエントリ及びインタレストについて維持される各ＰＩＴエントリについてのさらなる記憶装置を必要とする。ＣＣＮ−ＥＬＦがインタレストルーピングを検出するためにノンスを必要としないことを考えると、ＰＩＴは、インタレストに記載されているノンスを記憶しないことによって簡略化することができる。従来のＮＤＮシステムと比較して、これは、オーダ（｜ｉｄ｜）（｜ＰＩＴｉ｜）（｜Ｎｉ｜）の記憶装置の節約を表す。ここで、｜ｉｄ｜は、ノンスを記載するために必要なバイト数である。距離情報を維持するためにＣＣＮ−ＥＬＦによって必要とされるさらなる記憶装置は、インタレストにおいてノンスを記憶する必要がないことから得られる記憶装置の節約によって補償されるよりも多くなる可能性があることがわかる。
【００８０】
ＣＣＮ−ＥＬＦは、インタレスト及びそれらの応答が最短経路を移動することを考えると、ＦＩＢエントリにおけるルーティングテーブルループの不在下で従来のＮＤＮ及びＣＣＮシステムと同じエンドツーエンドの待ち時間を招く。しかしながら、従来のＮＤＮ及びＣＣＮシステムは、インタレストがルーティングループに沿って集約されるとき、コンテンツの検索又はＮＡＣＫの受信のためにＣＣＮ−ＥＬＦよりもはるかに長いエンドツーエンド遅延を招くことがある。少数のインタレストのみがルーティングループに沿って集約される場合であっても、未検出インタレストループは、コンテンツルータに記憶されたＰＩＴエントリの数及びコンテンツを得る際のエンドツーエンド遅延の非常に大きな増加をもたらすことがあることが示されている。
【００８１】
従来のＮＤＮ及びＣＣＮシステムにおいて、ルーティングループに沿って集約されるインタレストは、任意のＮＡＣＫがインタレスト発行消費者に対して送信され得る前に期限が切れるまでＰＩＴに残る。ＰＩＴにおけるインタレストの寿命は、通常、インタレストの不要な再送信を回避するために長く設定されることから、得られた待ち時間は秒のオーダである。一方、ＣＣＮ−ＥＬＦにより、消費者は、消費者とＮＤＯを送信するか又はインタレストループを検出するルータとの間の経路に沿ってラウンドトリップタイムの範囲内でインタレストに応答してＮＤＯ又はＮＡＣＫのいずれかを得ることができる。これは、通常、今日のインターネットと同様のトポロジで数百ミリ秒に相当する。さらにまた、インタレストループの誤検出は、インタレスト転送効率に大幅には影響を与えないことを示すことができる。これは、特に、名称接頭辞に対するループフリーマルチパスルーティングが制御プレーンにおいて提供される場合にあてはまる。
【００８２】
ＣＣＮ−ＥＬＦによって提供されるさらなる利点は、従来のＣＣＮ及びＮＤＮシステムによるパケットフォーマットとの互換性を含む。
【００８３】
コンピュータ及び通信システム
図９は、本発明の実施形態にかかる、ＦＩＢの拡張検索のための例示的なシステムを図示している。ＦＩＢの拡張検索のためのシステム９００は、プロセッサ９１０と、メモリ９２０と、記憶装置９３０とを含む。記憶装置９３０は、典型的には、メモリ９２０にロード可能であり且つ上述した方法を実行するためにプロセッサ９１０によって実行可能な命令を記憶する。１つの実施形態において、記憶装置９３０における命令は、インタレスト処理モジュール９３２と、名称付きデータオブジェクト処理モジュール９３４と、転送モジュール９３６と、制御メッセージ生成モジュール９３８とを実装することができ、それらの全ては様々な手段を介して互いに通信することができる。記憶装置９３０は、さらに、コンテンツストア９４０、転送情報ベース９４２及び保留インタレストテーブル９４４などの多数のデータ構造を含むことができる。
【００８４】
いくつかの実施形態において、モジュール９３２、９３４、９３６及び９３８は、部分的又は全体的にハードウェアで実装することができ、プロセッサ９１０の一部とすることができる。さらに、いくつかの実施形態において、システムは、別個のプロセッサ及びメモリを含まなくてもよい。代わりに、それらの特定のタスクを実行することに加えて、モジュール９３２、９３４、９３６及び９３８は、別個に又は一体的に、汎用又は専用計算エンジンの一部とすることができる。
【００８５】
記憶装置９３０は、プロセッサ９１０によって実行されることになるプログラムを記憶する。具体的には、記憶装置９３０は、ＦＩＢの拡張検索についてのシステム（アプリケーション）を実装するプログラムを記憶する。動作中において、アプリケーションプログラムは、記憶装置９３０からメモリ９２０にロードされることができ、プロセッサ９１０によって実行されることができる。その結果、システム９００は、上述した機能を実行することができる。システム９００は、（タッチスクリーンディスプレイとすることができる）任意のディスプレイ９８０、キーボード９６０及びポインティングデバイス９７０に結合されることができ、また、ネットワーク９８２に対して１つ以上のネットワークインターフェースを介して結合されることができる。
【００８６】
この詳細な説明に記載されたデータ構造及びコードは、典型的には、コンピュータシステムによって使用するためのコード及び／又はデータを記憶することができる任意の装置又は媒体であり得るコンピュータ読み取り可能な記憶媒体に記憶される。コンピュータ読み取り可能な記憶媒体は、これらに限定されるものではないが、揮発性メモリ、不揮発性メモリ、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）、ＤＶＤ（ディジタル多用途ディスク若しくはディジタルビデオディスク）などの磁気及び光記憶装置、又は、現在知られている若しくは今後開発されるコンピュータ読み取り可能な媒体を記憶することができる他の媒体を含む。
【００８７】
詳細な説明のセクションに記載された方法及びプロセスは、上述したようなコンピュータ読み取り可能な記憶媒体に記憶されることができるコード及び／又はデータとして具体化することができる。コンピュータシステムがコンピュータ読み取り可能な記憶媒体に記憶されたコード及び／又はデータを読み取って実行する場合、コンピュータシステムは、データ構造及びコードとして具現化されてコンピュータ読み取り可能な記憶媒体内に記憶された方法及びプロセスを実行する。
【００８８】
さらにまた、本願明細書に記載された方法及びプロセスは、ハードウェアモジュール又は装置に含めることができる。例えば、これらのモジュール又は装置は、これらに限定されるものではないが、特定用途向け集積回路（ＡＳＩＣ）チップ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定の時間に特定のソフトウェアモジュール若しくはコードの一部を実行する専用又は共有プロセッサ、及び／又は、現在知られている若しくは今後開発される他のプログラマブル論理デバイスを含むことができる。ハードウェアモジュール又は装置が起動されると、それらは、それらの内部に含まれる方法及びプロセスを実行する。
【図１】
2017063413.tif 000011
【図２Ａ】
2017063413.tif 000012
【図２Ｂ】
2017063413.tif 000013
【図３】
2017063413.tif 000014
【図４】
2017063413.tif 000015
【図５】
2017063413.tif 000016
【図６】
2017063413.tif 000017
【図７Ａ】
2017063413.tif 000018
【図７Ｂ】
2017063413.tif 000019
【図８Ａ】
2017063413.tif 000020
【図８Ｂ】
2017063413.tif 000021
【図８Ｃ】
2017063413.tif 000022
【図９】
2017063413.tif 000023