(57)【要約】      （修正有）【課題】情報指向ネットワーク（ＩＣＮ）内のプレフィックスに関するリンク状態情報を更新するシステムを提供する。【解決手段】ＩＣＮ内の第１のノードが、周辺ノードからのリンクステート広告（ＬＳＡ）メッセージを受信する。ＬＳＡメッセージにはプレフィックスが規定され、アンカーノードが規定されたプレフィックスを広告する。このシステムは、第１のノードに格納されているトポロジー情報に基づいて、最短経路条件が満たされているかどうかを判定し、最短経路条件が満たされていることに対応して、受信したＬＳＡメッセージを第１のノードの他の周辺ノードに転送する。【選択図】図５
2016119665.tif 000002
【特許請求の範囲】
【請求項１】
情報指向ネットワーク（ＩＣＮ）内のプレフィックスに関するリンク状態情報を更新する、コンピュータで実行可能な方法であって、
前記ＩＣＮ内の第１のノードにより、周辺ノードからのリンクステート広告（ＬＳＡ）メッセージを受信するステップであって、前記ＬＳＡメッセージにはプレフィックスが規定され、アンカーノードが前記規定されたプレフィックスを広告する、ステップと、
前記第１のノードに格納されるトポロジー情報に基づいて、最短経路条件が満たされているかどうかを判定するステップと、
前記最短経路条件が満たされていることに対応して、前記受信したＬＳＡメッセージを前記第１のノードの他の周辺ノードに転送するステップと、を含む方法。
【請求項２】
前記最短経路条件が満たされているかどうかを判定するステップには、最短経路優先（ＳＰＦ）アルゴリズムを用いて、前記第１のノードから前記規定されたプレフィックスまでの最短距離を計算することが含まれる、請求項１に記載の方法。
【請求項３】
前記第１のノードにより、ローカルのプレフィックスへの状態の変化を反映するＬＳＡメッセージを生成するステップと、
前記生成されたＬＳＡメッセージを前記第１のノードの周辺ノードに転送するステップと、をさらに含む請求項１に記載の方法。
【請求項４】
前記第１のノードにより、前記受信したＬＳＡメッセージに基づいて、ルーティングテーブルを更新するステップをさらに含む請求項１に記載の方法。
【請求項５】
コンピュータ装置により実行されると、前記コンピュータ装置が、情報指向ネットワーク（ＩＣＮ）内のプレフィックスに関するリンク状態情報を更新する方法を実行する命令を格納する非一時的コンピュータ可読記憶媒体であって、前記方法には、
前記ＩＣＮ内の第１のノードにより、周辺ノードからのリンクステート広告（ＬＳＡ）メッセージを受信するステップであって、前記ＬＳＡメッセージにはプレフィックスが規定され、アンカーノードが前記規定されたプレフィックスを広告する、ステップと、
前記第１のノードに格納されるトポロジー情報に基づいて、最短経路条件が満たされているかどうかを判定するステップと、
前記最短経路条件が満たされていることに対応して、前記受信したＬＳＡメッセージを前記第１のノードの他の周辺ノードに転送するステップと、が含まれる、コンピュータ可読記憶媒体。
【請求項６】
前記最短経路条件が満たされているかどうかを判定するステップには、最短経路優先（ＳＰＦ）アルゴリズムを用いて、前記第１のノードから前記規定されたプレフィックスまでの最短距離を計算することが含まれる、請求項５に記載のコンピュータ可読記憶媒体。
【請求項７】
前記方法には、
前記第１のノードにより、ローカルのプレフィックスへの状態の変化を反映するＬＳＡメッセージを生成するステップと、
前記生成されたＬＳＡメッセージを前記第１のノードの周辺ノードに転送するステップと、がさらに含まれる、請求項５に記載のコンピュータ可読記憶媒体。
【請求項８】
情報指向ネットワーク（ＩＣＮ）内のプレフィックスに関するリンク状態情報を更新するコンピュータシステムであって、
プロセッサと、
前記プロセッサと連結する記憶装置であって、前記プロセッサにより実行されると、前記プロセッサが、
前記ＩＣＮ内の第１のノードにより、周辺ノードからのリンクステート広告（ＬＳＡ）メッセージを受信するステップであって、前記ＬＳＡメッセージにはプレフィックスが規定され、アンカーノードが前記規定されたプレフィックスを広告する、ステップと、
前記第１のノードに格納されるトポロジー情報に基づいて、最短経路条件が満たされているかどうかを判定するステップと、
前記最短経路条件が満たされていることに対応して、前記受信したＬＳＡメッセージを前記第１のノードの他の周辺ノードに転送するステップと、を含む方法を実行する命令を格納する記憶装置と、含むシステム。
【請求項９】
前記最短経路条件が満たされているかどうかを判定するステップには、最短経路優先（ＳＰＦ）アルゴリズムを用いて、前記第１のノードから前記規定されたプレフィックスまでの最短距離を計算することが含まれる、請求項８に記載のシステム。
【請求項１０】
前記方法には、
前記第１のノードにより、ローカルのプレフィックスへの状態の変化を反映するＬＳＡメッセージを生成するステップと、
前記生成されたＬＳＡメッセージを前記第１のノードの周辺ノードに転送するステップと、がさらに含まれる、請求項８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に情報指向ネットワーク（ＩＣＮ）に関する。より具体的には、本開示は、ＩＣＮ内のリンクステート情報を用いて、コンテンツルーティングを行うシステムおよび方法に関する。
【背景技術】
【０００２】
ネットワーク産業では、インターネットや電子商取引の普及により、革命的な変化が加速し続けている。今日では、オンライン映画鑑賞から、日々のニュース配信、小売販売、およびインスタントメッセージのやり取りに至るまで、著しい数の情報交換がオンラインで行われている。ますます多くインターネット・アプリケーションが携帯可能になってきている。しかし、現在のインターネットは、その大部分が位置ベースのアドレス指定スキームに依存している。インターネットプロトコル（ＩＰ）とイーサネット（登録商標）プロトコルが、今最も普及している２種類のプロトコルであるが、その両方ともエンドホストのアドレス指定に基づいている。すなわち、コンテンツの顧客ができることは、物理的対象または場所に、通常、関連するアドレス（例えば、ＩＰアドレス、またはイーサネット（登録商標）・メディア・アクセス制御（ＭＡＣ）アドレス）からコンテンツを明示的に要求することにより、コンテンツを受信することだけである。この制限的なアドレス指定スキームは、絶え間なく変化し続けるネットワークの需要に対応するには、次第に不十分になってきている。
【０００３】
近年、この業界では、情報指向ネットワーク（ＩＣＮ）アーキテクチャが提案されており、この情報指向ネットワークでは、コンテンツが直接名前を付けられ、アドレス指定される。例示的なＩＣＮアーキテクチャ、すなわちコンテンツ指向ネットワーク（ＣＣＮ）により、コンテンツを配信する新しいアプローチがもたらされている。エンド・トウ・エンドの会話としてアプリケーションレベルで見ることができる、コンテンツが移動するためのネットワークトラフィックの代わりに、コンテンツはその一意の名前に基づいてやり取りされ、プロバイダから顧客へのコンテンツルーティングをネットワークが担っている。なお、コンテンツは通信システムで通信可能なデータを含み、このデータはテキスト、画像、ビデオ、および／または、音声などのデータの全ての形態を取る。顧客およびプロバイダは、ＩＣＮの内または外に存在するコンピュータすなわち自動処理側の当事者でよい。１つのコンテンツとは、コンテンツ全体またはコンテンツの各部分のことを指し得る。例えば、新聞記事は、データパケットとして具現化される複数のコンテンツにより表すことができる。また、１つのコンテンツはメタデータと関連付けられ得、このメタデータにより、１つのコンテンツに、認証データ、作成日、コンテンツの所有者などの情報が記述される、すなわち、補強される。
【０００４】
全てのＩＣＮアーキテクチャの中心は、名前解決およびコンテンツのルーティングであり、いくつかのアプローチが提案されている。いくつかのＩＣＮアーキテクチャでは、ディレクトリサーバにより、データオブジェクトの名前がアドレスにマッピングされ、コンテンツを配信するために、アドレスベースのルーティングが用いられている。これとは対照的に、複数のＩＣＮアーキテクチャでは、名前解決とコンテンツルーティングを統合する、名前ベースのコンテンツルーティングが用いられている。名前ベースのルーティングでは、ルータ（プロデューサまたはキャシングサイト）のうちのいくつかが、名前付きデータオブジェクト（ＮＤＯ）、あるいは、共通のプレフィックスを共有する一連の名前付きオブジェクトを示す名前のプレフィックスのローカルコピーの存在を広告し、それらへのルートが確立される。コンテンツの顧客は、コンテンツ要求を発行し、このコンテンツ要求が、ＮＤＯまたは名前のプレフィックスの広告を発行したルータへのルートに沿って転送される。
【０００５】
様々なＩＣＮアーキテクチャの中でも、ＣＣＮは、分散ルーティングプロトコルを用いて、コンテンツ要求を転送するルートを確立する。ＣＣＮでは、１つまたは複数の経路を介して、コンテンツ要求（「インタレスト」と呼ぶ）を名前のプレフィックスに送信可能である。いくつかのＣＣＮスキームでは、イントラドメインルーティングに関して、リンクステート型内部ゲートウェイプロトコル（ＩＧＰ）などの既存のインターネットルーティングプロトコルが用いられる。このイントラドメインルーティングでは、それらルーティングプロトコルのローカル接続性および隣接リソース（コンテンツ）がルータにより記述される。ドメインレベルのコンテンツのプレフィックスを既存の境界ゲートウェイプロトコル（ＢＧＰ）と統合して、ドメイン間のコンテンツルーティングの問題を解決することも提案されている。
【０００６】
ＩＣＮ内の例示的なコンテンツルーティングスキームには、ＮＬＳＲ（名前付きデータ・リンクステート型ルーティングプロトコル）とＯＳＰＦＮ（名前付きデータ用のＯＳＰＮ）とがある。これら両方のプロトコルでは、ルータは、２種類のリンクステート広告（ＬＳＡ）を氾濫させることにより、トポロジー情報をやり取りする。ＬＳＡは、従来のリンクステート型ルーティングプロトコルで行われている物理リンクの状態を記述することができる。さらに、ルータはプレフィックスのローカルコピーを有し、そのプレフィックスに関するＬＳＡを氾濫させる。物理的インフラの上に存在するオーバレイ内で動作する分散ハッシュテーブル（ＤＨＴ）を用いて、名前ベースのルーティングを実行し、その状況下で、リンクステート型プロトコルから通常構成されるアンダーレイ内で用いられるルーティングプロトコルを実行することも可能である。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
既存のリンクステートベースのルーティングプロトコルが直面している問題のうちの１つは、これらのルーティングプロトコルでは、ＬＳＡなどの、公開される各名前付きデータオブジェクト、すなわちネットワークで広告される名前のプレフィックスの全てのレプリカに関する情報を各ルータが受信する必要があり、そのために、これらのルーティングプロトコルは拡張性が無いことである。
【課題を解決するための手段】
【０００８】
本発明の一実施形態では、情報指向ネットワーク（ＩＣＮ）内のプレフィックスに関するリンク状態情報を更新するシステムが提供される。動作中、ＩＣＮ内の第１のノードが、周辺ノードからのリンクステート広告（ＬＳＡ）メッセージを受信する。このＬＳＡメッセージにはプレフィックスが規定され、アンカーノードが規定されたプレフィックスを広告する。このシステムは、第１のノードに格納されているトポロジー情報に基づいて、最短経路条件が満たされているかどうか判定し、最短経路条件が満たされていることに対応して、この受信したＬＳＡメッセージを第１のノードのその他の周辺ノードに転送する。
【０００９】
本実施形態の変更形態では、最短経路条件が満たされているかどうかを判定するステップには、最短経路優先（ＳＰＦ）アルゴリズムを用いて、第１のノードから規定されたプレフィックスまでの最短距離を計算することが含まれる。
【００１０】
本実施形態の変更形態では、第１のノードが、ローカルのプレフィックスへの状態変化を反映するＬＳＡメッセージを生成し、生成されたＬＳＡメッセージを第１のノードの周辺ノードに転送する。
【００１１】
本実施形態の変更形態では、第１のノードは、受信したＬＳＡメッセージに基づいて、ルーティングテーブルを更新する。
【００１２】
さらに別の変更形態では、ルーティングテーブルを更新するステップには、プレフィックスへの一連の有効なネクストホップ先の周辺ノードを識別することが含まれ、それぞれの有効なネクストホップ先の周辺ノードの識別には、有効なネクストホップ先の周辺ノードが第１のノードよりもアンカーノードに近いかどうかを判定し、それにより、更新されるルーティングテーブル内でループが形成されることを防ぐことが含まれる。
【００１３】
さらに別の変更形態では、有効なネクストホップ先の周辺ノードからアンカーノードまでの距離が、有効なネクストホップ先の周辺ノードから第１のノードまでの距離と同じ場合、このシステムは、有効なネクストホップ先の周辺ノードが、第１のノードと比較して小さい辞書式順序値を有しているかどうかを判定する。
【００１４】
本実施形態の変更形態では、ＬＳＡメッセージには、アンカーノードにより作成される順序番号がさらに含まれ、規定されたプレフィックスに関するＬＳＡメッセージをアンカーノードが更新するごとに、この順序番号が増加する。
【図面の簡単な説明】
【００１５】
【図１】図１は、本発明の実施形態に従った、ネットワークの例示的なアーキテクチャを示す図である。
【図２】図２は、本発明の実施形態に従った、ルータで維持される例示的なトポロジテーブルを示す図である。
【図３】図３は、本発明の実施形態に従った、ルータで維持される例示的なルーティングテーブルを示す図である。
【図４】図４は、本発明の実施形態に従った、ルータで維持される例示的なアンカーテーブルを示す図である。
【図５】図５は、本発明の実施形態に従った、ＬＣＲを実施するルータの例示的なアーキテクチャを示す図である。
【図６】図６は、本発明の実施形態に従った、ＬＣＲのルーティングの一例を示す図である。
【図７】図７は、本発明の実施形態に従った、リンクステート型コンテンツルーティングを行うための例示的なシステムを示す図である。
【００１６】
これらの図面では、同様の参照符号は同じ数字の要素を示す。
【発明を実施するための形態】
【００１７】
本発明の実施形態では、情報指向ネットワーク（ＩＣＮ）内のリンクステート情報に基づいて、コンテンツルーティングを行うシステムが提供される。より具体的には、リンクステート型コンテンツルーティング（ＬＣＲ）システムは、リンクコストテーブル、トポロジテーブル、ルーティングテーブル、およびアンカーテーブルなどの複数のテーブルを維持するルータを有し、これらのルータと共に動作する。これらのテーブル内に格納される情報は、ルータにより定期的に更新され得る。ルータが、その周辺ルータからリンクステート広告（ＬＳＡ）を受信すると、トポロジテーブルが更新される。ルーティングテーブルは、最短経路優先（ＳＰＦ）アルゴリズムにより、計算され更新され得る。従来のリンクステートベースのルーティングと異なり、ＬＣＲシステムでは、ルータは、名前のプレフィックスの全てのレプリカに関するネットワークＬＳＡを氾濫させない。その代わり、各ルータが名前のプレフィックスごとに１つのレプリカだけ（多くの場合、最も近い）を報告するよう、名前のプレフィックスに関するＬＳＡを設定する。
【００１８】
リンクステート型コンテンツルーティング（ＬＣＲ）システムの動作を実際に説明するため、本開示では、ＣＣＮを例として用いる。しかし、ＬＣＲシステムの動作は、ＣＣＮに限定されない。一般に、ＬＣＲはその他の全ての種類のＩＣＮネットワークに適用することができる。
【００１９】
ＣＣＮでは、インタレストとコンテンツオブジェクトという２種類のメッセージが用いられる。インタレストは、コンテンツオブジェクトの階層構造可変長識別子（ＨＳＶＬＩ）（「名前」とも呼ばれる）を保持し、そのオブジェクトに対する要求としての役割を果たす。ネットワーク要素（例えば、ルータ）が、同じ名前に関して複数のインタレストを受信した場合、この要素はこれらのインタレストを１つに集めることができる。コンテンツオブジェクトと一致したインタレストの経路に沿ったネットワーク要素は、そのオブジェクトをキャッシュして戻して、そのインタレストを満足させることができる。コンテンツオブジェクトは、そのインタレストの起点（複数可）まで、インタレストの逆経路をたどる。
【００２０】
一般に、本開示で使用される用語は以下の通り規定される（しかし、それらの解釈は下記に限定されない）：
【００２１】
「ＨＳＶＬＩ」：階層構造可変長識別子（「名前」とも呼ばれる）であり、名前要素の順序リスト（可変長オクレット文字列でよい）である。人間が読み取り可能な形態では、ｃｃｎｘ：／ｐａｔｈ／ｐａｒｔなどの形式で表すことが可能である。ＨＳＶＬＩはまた、人間が読み取り可能でなくてもよい。上述した通り、ＨＳＶＬＩはコンテンツを表し、コンテンツの組織構造を表示可能であり、人間に対しても少なくとも部分的に意味を有することが望ましい。ＨＳＶＬＩの個々の要素の長さは任意でよい。さらに、ＨＳＶＬＩは明示的に区切られた要素を有し、バイトの任意のシーケンスを含むことができるが、人間が読み取り可能な文字には限定されない。ＨＳＶＬＩを有するパケットを転送する際、最長プレフィックス一致検索が重要である。例えば、「／ｐａｒｃ／ｈｏｍｅ／ｂｏｂ」内のインタレストを示すＨＳＶＬＩは、「／ｐａｒｃ／ｈｏｍｅ／ｂｏｂ／ｔｅｓｔ．ｔｘｔ」と「／ｐａｒｃ／ｈｏｍｅ／ｂｏｂ／ｂａｒ．ｔｘｔ．」の両方と一致する。名前要素の数に関して、最長の一致は、最も明示的であるため最良と見なされている。ＨＳＶＬＩの詳細な説明は、発明者、Ｖａｎ  Ｌ．  ＪａｃｏｂｓｏｎおよびＪａｍｅｓ  Ｄ．  Ｔｈｏｒｎｔｏｎによる２００９年９月２３日出願の「ＳＹＳＴＥＭ  ＦＯＲ  ＦＯＲＷＡＲＩＤＮＧ  Ａ  ＰＡＣＫＥＴ  ＷＩＴＨ  Ａ  ＨＩＥＲＡＲＣＨＩＣＨＡＬＬＹ  ＳＴＲＵＣＴＵＲＥＤ  ＶＡＲＩＡＢＬＥ−ＬＥＮＧＴＨ  ＩＤＥＮＴＩＦＩＥＲ」と題する米国特許第８，１６０，０６９号明細書に記載されている。
【００２２】
「インタレスト」：コンテンツオブジェクトに対する要求である。インタレストは、ＨＳＶＬＩの名前のプレフィックスと、同じ名前のプレフィックスを有する複数のオブジェクトから特定のオブジェクトを選ぶために使用することができるその他の随意的なセレクタと、を規定する。その名前がインタレストの名前のプレフィックス（および発行者キーＩＤの一致などのその他の随意的に要求されるパラメータ）と一致する全てのコンテンツオブジェクトによりインタレストが満足される。
【００２３】
「コンテンツオブジェクト」：インタレストに応じて送信されるデータオブジェクトである。コンテンツオブジェクトは、ＨＳＶＬＩの名前とコンテンツのペイロードとを有し、これらは暗号署名を介して、一緒に束ねられる。随意的に、全てのコンテンツオブジェクトは、コンテンツオブジェクトのＳＨＡ−２５６ダイジェストから成る、暗示的なターミナル名の要素を有する。実施形態によっては、暗示的なダイジェストは有線では転送されないが、必要であれば、各ホップにて計算される。本開示では、用語「コンテンツオブジェクト」と用語「名前付きデータオブジェクト（ＮＤＯ）」とを、同じ意味で使用可能である。
【００２４】
「フェース（Ｆａｃｅ）」：ＣＣＮでは、フェースという用語は、インターフェースの概念を一般化したものである。フェースは、ネットワークに接続され得る、あるいは、アプリケーションパーティに直接接続され得る。特定のネットワークのインターフェースで、ブロードキャストパケットやマルチキャストパケットを送受信するようフェースを構成することができる。あるいは、下層トランスポートにおける２点間アドレス指定、またはトンネル（例えば、ＴＣＰトンネル）を用いてパケットを送受信するようフェースを構成することができる。また、フェースは、ＵＤＰやＯＳ専用プロセス間通信経路のようなカプセル化を介する、同じマシン上で動作する単一のアプリケーションプロセスへの接続でもよい。全てのメッセージはフェースを通じて受信され、フェースを通じて送信される。本開示では、用語「周辺」は、用語「フェース」と同じ意味で用いることができ、インタレストの着信インターフェースまたは送信インターフェースのことを指す。
【００２５】
「プレフィックス」：本開示では、特定のコンテンツオブジェクトの名前、またはコンテンツオブジェクトに関する名前のプレフィックスのどちらかを指すために、用語「プレフィックス」を使用する。
【００２６】
「アンカー」：本開示では、コンテンツを広告するルータを指すために、用語「アンカー」を使用する。より具体的には、プレフィックスに対応するいくつかの、または全てのコンテンツを広告するルータ（またはノード）を、プレフィックスのアンカーと呼ぶ。
【００２７】
上述した通り、ＨＳＶＬＩは、１つのコンテンツを示し、階層的に構造化され、かつ、最も一般的なレベルから最も特別なレベルに順序付けられる連続要素を含む。各ＨＳＶＬＩの長さは固定されていない。コンテンツ指向ネットワークでは、従来のＩＰネットワークとは異なり、ＨＳＶＬＩによってパケットを認識することができる。例えば、「ａｂｃｄ／ｂｏｂ／ｐａｐｅｒｓ／ｃｃｎ／ｎｅｗｓ」は、コンテンツの名前であり得、対応するパケット（複数可）（すなわち、「ＡＢＣＤ」という名前が付いた組織の「Ｂｏｂ」という名前が付いたユーザに関する新聞の「ｃｃｎ」コレクションからの「ｎｅｗｓ」記事）を認識する。１つのコンテンツを要求するために、ノードは、コンテンツの名前により、そのコンテンツにおけるインタレストを表す（例えば、一斉送信する）。１つのコンテンツにおけるインタレストは、コンテンツの名前または識別子による、そのコンテンツに対するクエリーでよい。コンテンツがネットワーク内で取得可能であれば、そのコンテンツを格納している任意のノードから要求しているノードにコンテンツが送り返される。ルーティング・インフラクチャでは、その情報を持っていそうな見込みのあるノードにインタレストが理知的に伝えられ、インタレストのメッセージが伝えられた経路の逆方向に沿って有効なコンテンツが送り返される。基本的には、コンテンツオブジェクトはインタレストのメッセージが残した経路を引き返し、したがって、要求を出したノードに到達する。
【００２８】
図１には、本発明の実施形態に従った、ネットワークの例示的なアーキテクチャが示されている。この例では、ネットワーク１８０には、ノード１００〜１４５が含まれる。ネットワーク内の各ノードは、１つ以上の他のノードと接続する。ネットワーク接続１８５は、そのような接続の１つの例である。ネットワーク接続は実線で示されているが、各線はノードとノードとを接続可能なサブネットワークまたはスーパーネットワークも表し得る。ネットワーク１８０は、コンテンツ指向で、ローカルネットワーク、スーパーネットワーク、またはサブネットワークであり得る。特定のネットワーク内のノードと別のネットワーク内のノードとが接続可能であるよう、これらのネットワークはそれぞれ相互接続可能である。このネットワーク接続は、ブロードバンド、無線、電話、人工衛星、または全てのタイプのネットワーク接続でよい。ノードは、コンピュータシステム、およびユーザを表すエンドポイント、および／または、インタレストを生成したり、コンテンツを生成したりすることが可能な装置でよい。
【００２９】
本発明の実施形態では、顧客は、１つのコンテンツに関するインタレストを生成し、そのインタレストをネットワーク１８０内のノードに転送できる。その１つのコンテンツは、ネットワークの内または外に存在する発行者やコンテンツプロバイダにより、ネットワーク１８０内のノードに格納され得る。例えば、図１では、１つのコンテンツにおけるインタレストが、ノード１０５で始まる。そのノードでコンテンツが取得できない場合、そのインタレストは第１のノードに接続する１つ以上のノードに流れる。例えば、図１では、そのインタレストはノード１１５に流れるが（インタレストフロー１５０）、そこには取得可能なコンテンツが存在しない。次に、インタレストはノード１１５からノード１２５に流れるが（インタレストフロー１５５）、そこにも取得可能なコンテンツが存在しない。次いで、インタレストはノード１３０に流れ（インタレストフロー１６０）、そこには取得可能なコンテンツが存在する。次いで、コンテンツオブジェクトの流れは、その経路を逆方向に引き返し（コンテンツの流れ１６５、１７０、および１７５）、ノード１０５に到達し、そこでこのコンテンツが配信される。このコンテンツの流れには、認証などのその他の処理も含まれ得る。
【００３０】
ネットワーク１８０では、コンテンツがネットワーク全体を移動するとき、コンテンツ保持ノード（ノード１３０）とインタレスト生成ノード（ノード１０５）との間の経路内で、あらゆる数の中間ノード（ノード１００〜１４５）が、コンテンツのローカルコピーのキャッシングに参加可能である。キャッシングを行うことで、ローカルでキャシングされたコンテンツへのアクセスを暗示的に共有することにより、他の配信先の近くに存在する第２の配信先に対するネットワーク負荷を軽減することができる。
【００３１】
ＬＣＲシステムは、下記のことを前提として動作する。：（ａ）各ネットワークノードには、平坦構造または階層構造の名前が割り当てられる。（ｂ）各コンテンツは、名前で要求可能な名前付きデータオブジェクト（ＮＤＯ）である。（ｃ）ＮＤＯは、平坦構造の名前または階層構造の名前のうちのどちらかの名前（ＨＳＶＬＩベースの名前などの）で示され得、全体のシステムを通して同じ命名規則が用いられる。（ｄ）ルータは、便宜的にコンテンツをキャシュ可能である。
【００３２】
階層構造の名前が用いられるとき、ルータは、それらのＮＤＯを異なる方法で広告する。例えば、ルータが名前のプレフィックスに関する全てのＮＤＯのローカルコピーを有する場合に限り、そのルータは名前のプレフィックスを広告することが可能となる。あるいは、ルータが名前のプレフィックスのＮＤＯの一部を有する場合、そのルータは名前のプレフィックスを広告することが可能となる。本開示では、名前または名前のプレフィックスに対応する、いくつかの、または全てのコンテンツを格納していることを広告するルータは、名前または名前のプレフィックスのアンカーと呼ばれる。
【００３３】
ＬＣＲを実施するために、ＩＣＮ内のルータは、リンクコストテーブル、トポロジテーブル（ＴＴｉ）、ルーティングテーブル（ＲＴｉ）、およびアンカーテーブル（ＡＴｉ）などの複数のデータ構造を備える。
【００３４】
ルータｉに関するリンクコストテーブル（ＬＴｉ）は、ルータｉからその各周辺ルータへのリンクのコストを一覧表示する。本開示では、ルータｉからルータｋへのリンクは（ｉ，ｋ）と示され、そのリンクのコストは
【００３５】
【数１】
2016119665.tif 000003
【００３６】
と示される。いくつかの実施形態では、リンクのコストは、正の数であることを前提とし、そのリンクに関してルータｉにより作成される、管理制限および性能測定の関数でよい。
【００３７】
ルータｉにより維持されるトポロジテーブル（ＴＴｉ）は、各ルータおよび知られている各プレフィックスに関する各周辺ルータにより、報告または転送されるリンクステート情報を表示する。いくつかの実施形態では、トポロジテーブルＴＴｉ内に格納されている情報には、ルータｉから各周辺ルータへのリンク、ルータｉからローカルで取得可能なプレフィックスへのリンク、ならびに、周辺ルータにより転送される、ルータｉからノードまたはプレフィックスへのリンクが含まれる。なお、ノードへのリンクは物理リンクと考えられ、プレフィックスへのリンクは仮想リンクと考えられる。例えば、トポロジテーブルＴＴｉ内のサブテーブル
【００３８】
【数２】
2016119665.tif 000004
【００３９】
には、周辺ルータｍにより転送される、ノードまたはプレフィックスへのリンクが含まれる。
【００４０】
図２には、本発明の実施形態に従った、ルータで維持される例示的なトポロジテーブルが示されている。図２では、ルータｉに維持されるトポロジテーブル２００は、異なる２つの種類のリンクステート広告（ＬＳＡ）のエントリを含む。第１の種類のＬＳＡのエントリは、物理リンクに関連する情報を格納するために用いられ、リンク識別子により索引付けられる。このようなＬＳＡのエントリには、リンク識別子、リンクに関するコスト関数、順序番号、および存続時間が含まれ得る。例えば、エントリ２０２は、ルータｉ内に格納される、リンク（ｕ，ｖ）に関するＬＳＡを表し、このエントリ２０２には、リンク識別子（ｕ，ｖ）と、リンクのコスト
【００４１】
【数３】
2016119665.tif 000005
【００４２】
と、リンク
【００４３】
【数４】
2016119665.tif 000006
【００４４】
に関するルータｕにより作成された、ルータｉにより知られている最新の順序番号と、ＬＳＡの有効期間
【００４５】
【数５】
2016119665.tif 000007
【００４６】
（残されている存続時間）と、が含まれる。いくつかの実施形態では、リンク（ｕ，ｖ）に関するルータｉに格納されるＬＳＡは、
【００４７】
【数６】
2016119665.tif 000008
【００４８】
と示される。
【００４９】
一方、第２の種類のＬＳＡのエントリは、仮想リンク（プレフィックス）に関する情報を格納するために用いられ、プレフィックスにより索引付けられる。このようなＬＳＡのエントリには、プレフィックス、プレフィックスに対するアンカー、順序番号、および存続時間が含まれ得る。例えば、エントリ２０４は、アンカールータｋにより広告されるプレフィックスｊに関するルータｉに格納されるＬＳＡを表す。このエントリには、プレフィックスｊの名前と、プレフィックスｊのアンカーとして機能するルータの名前と、プレフィックス
【００５０】
【数７】
2016119665.tif 000009
【００５１】
に関するルータｋにより作成された、ルータｉにより知られている最新の順序番号と、ＬＳＡの有効期間
【００５２】
【数８】
2016119665.tif 000010
【００５３】
（残されている存続時間）と、が含まれる。いくつかの実施形態では、アンカールータｋにより広告されるプレフィックスｊに関する、ルータｉに格納されるＬＳＡは、
【００５４】
【数９】
2016119665.tif 000011
【００５５】
と示される。
【００５６】
なお、ＬＳＡがトポロジテーブルに格納されている間、ＬＳＡの有効期間は単調に減らされていく。有効期間がゼロの値に達すると（期限切れとしても知られている）、ＬＳＡ（物理リンクまたは仮想リンクのどちらかに関する）は削除される。ネットワークのトポロジーすなわちコンテンツ（プレフィックス）の位置の変更を反映させるために、ネットワーク内のルータは、更新メッセージを定期的に送信する。例えば、ルータｉは、更新メッセージをその周辺ルータｋに定期的に送信することができ、この更新メッセージには、ルータｉのトポロジテーブルＴＴｉに対して行われた変更が含まれる。
【００５７】
ルータｕとルータｖの間の各物理リンクは、２つの方向を有するリンク（ｕ，ｖ）および（ｖ，ｕ）に対応し、ルータｕで維持されるプレフィックスｊのコピーごとに、１つの方向をだけを有するリンク（ｕ，ｊ）が存在するよう、トポロジテーブルＴＴｉに格納されるグラフは構成されている。したがって、トポロジテーブルＴＴｉ内で最短経路優先アルゴリズム、または、その他の全ての最短経路アルゴリズムを実行して、プレフィックスまたは物理的ルータへの最短経路を計算することができ、その際、その経路に沿った中継点としてプレフィックスノードを通過する、任意の目的地（プレフィックスまたは物理的ルータ）への経路は存在しない。
【００５８】
いくつかの実施形態では、隣接する全てのリンクがその状態を変更する、新しいコンテンツがローカルで取得可能になる、あるいは、ＬＳＡが受信されるとき、ルータｉはそのトポロジテーブルＴＴｉを更新する。ルータｉが、ＬＳＡ
【００５９】
【数１０】
2016119665.tif 000012
【００６０】
などのリンクＬＳＡ（物理リンクと関連するＬＳＡ）を周辺ルータｋから受信すると、そのＬＳＡが期限切れＬＳＡではなく（すなわち、有効期間
【００６１】
【数１１】
2016119665.tif 000013
【００６２】
の場合）、かつリンク（ｕ，ｖ）がトポロジテーブル
【００６３】
【数１２】
2016119665.tif 000014
【００６４】
内に存在しない、あるいは、ＬＳＡ内の順序番号
【００６５】
【数１３】
2016119665.tif 000015
【００６６】
が、トポロジテーブル
【００６７】
【数１４】
2016119665.tif 000016
【００６８】
内のリンク（ｕ，ｖ）に関して格納される順序番号より大きい場合に限って、ルータｉは、周辺ルータｍごとにトポロジテーブル
【００６９】
【数１５】
2016119665.tif 000017
【００７０】
を更新する。つまり、ルータｉがリンクＬＳＡを受信するとき、そのリンクが新しいリンクであるか、または、同じリンクに関するトポロジテーブル内に格納されている順序番号よりもそのＬＳＡ内の順序番号が大きい場合に限り、かつ、そのＬＳＡの期限が切れていない場合に、そのルータｉは、トポロジテーブルを更新する。
【００７１】
同様に、ルータｉが、ＬＳＡ
【００７２】
【数１６】
2016119665.tif 000018
【００７３】
などのプレフィックスＬＳＡ（プレフィックスに関するＬＳＡ）を周辺ルータｋから受信した場合、ルータｋからのＬＳＡの有効期間が
【００７４】
【数１７】
2016119665.tif 000019
【００７５】
であり、リンク（ｕ，ｊ）がトポロジテーブルＴＴｉ内に存在しない、あるいはＬＳＡ内の順序番号
【００７６】
【数１８】
2016119665.tif 000020
【００７７】
が、トポロジテーブルＴＴｉ内のリンク（ｕ，ｊ）に関して格納されている順序番号より大きい場合に、ルータｉはトポロジテーブルＴＴｉを更新する。つまり、ルータｉがプレフィックスＬＳＡを受信したとき、その仮想リンクが新しいリンクであるか、あるいは、同じ仮想リンクに関する、トポロジテーブル内に格納されている順序番号よりもそのＬＳＡ内の順序番号が大きい場合に限り、かつ、そのＬＳＡの期限が切れていない場合に、そのルータｉは、トポロジテーブルＴＴｉを更新する。
【００７８】
ルータｉで維持されるルーティングテーブル（ＲＴｉ）には、ルータｉで知られるプレフィックスごとのルーティング情報が格納されている。いくつかの実施形態では、ルーティングテーブルには、プレフィックスにより索引付けられる複数のエントリが含まれ得る。図３には、本発明の実施形態に従った、ルータで維持される、例示的なルーティングテーブルが示されている。図３では、ルータｉに維持されるルーティングテーブル３００が、複数のエントリを含む。各エントリには、プレフィックスの名前と、このプレフィックスに対して有効なネクストホップである一連の周辺ノードと、このプレフィックスへの最短距離を提供する周辺ノードとが含まれている。例えば、エントリ３０２には、プレフィックス（ｊ）と、プレフィックスｊへの有効な一連のネクストホップ先の周辺ノード
【００７９】
【数１９】
2016119665.tif 000021
【００８０】
と、プレフィックスｊへの最短経路の周辺ノード
【００８１】
【数２０】
2016119665.tif 000022
【００８２】
と含まれる。
【００８３】
最短経路優先（ＳＰＦ）アルゴリズムを動かすことにより、ルーティングテーブルが更新され得る。いくつかの実施形態では、ルータｉは、ルータｉを起点としてＳＰＦを動かすことにより、各プレフィックスへの最短経路を計算する。ルータｉから各プレフィックスｊへの計算された最短距離は
【００８４】
【数２１】
2016119665.tif 000023
【００８５】
と示される。次いで、ルータｉは、その周辺ノードをそれぞれ起点としてＳＰＦを動かす。ルータｉの周辺ノードｋを介した各プレフィックスｊへの計算された最短距離は
【００８６】
【数２２】
2016119665.tif 000024
【００８７】
と示される。いくつかの実施形態では、各プレフィックスまでの計算された最短距離（ルータｉからの最短距離と、その周辺ノードからの最短距離を含む）はルーティングテーブルに格納される。
【００８８】
ルータｉで維持されるアンカーテーブル（ＡＴｉ）には、ルータｉで知られているプレフィックスごとの最も近いアンカーのリストが格納されている。いくつかの実施形態では、このアンカーテーブルには、プレフィックスで索引付けされる複数のエントリが含まれる。図４には、本発明の実施形態に従った、ルータで維持される例示的なアンカーテーブルが示されている。図４では、ルータｉで維持されるアンカーテーブル４００は、複数のエントリを含む。各エントリには、プレフィックスの名前と、プレフィックスに最も近いアンカー（そのプレフィックスへの最短距離と、そのプレフィックスを報告する最小識別子とを有するルータ）と、そのプレフィックスに最も近いアンカーにより、そのプレフィックスに割り当てられる順序番号と、全てのネクストホップ先の周辺ノードにより報告される一連の有効アンカーと、が含まれている。なお、有効アンカーごとに、アンカーテーブルは、アンカーの名前、およびそのアンカーにより報告される順序番号を表示するタプルを格納する。例えば、エントリ４０２には、プレフィックス（ｊ）と、プレフィックスｊに最も近いアンカー
【００８９】
【数２３】
2016119665.tif 000025
【００９０】
と、アンカー
【００９１】
【数２４】
2016119665.tif 000026
【００９２】
によりプレフィックスｊに割り当てる順序番号
【００９３】
【数２５】
2016119665.tif 000027
【００９４】
と、アンカーの集合
【００９５】
【数２６】
2016119665.tif 000028
【００９６】
とが含まれている。なお、アンカーの集合
【００９７】
【数２７】
2016119665.tif 000029
【００９８】
には、ネクストホップ先の周辺ノードにより報告される別の有効アンカーに関するタプル
【００９９】
【数２８】
2016119665.tif 000030
【０１００】
が格納さている。但し、ｍは有効アンカーの名前を表し、ｓｎ（ｍ）はアンカーｍにより報告される順序番号を表す。ルーティングテーブルが更新されるとき、この順序番号を用いて、ルーティングテーブルのループを避けることができる。なお、プレフィックスのアンカーだけが、発表されたプレフィックスまでの距離に関する順序番号を変更することができる。
【０１０１】
アンカーテーブルの更新は、ルーティングテーブルの更新の一部として行われ得る。より具体的には、ルータｉで、周辺ノードｋを起点としてＳＰＦが動かされ、プレフィックスｊまでの最短距離
【０１０２】
【数２９】
2016119665.tif 000031
【０１０３】
が取得されると、プレフィックスｊへのリンク、および、そのルータにより作成される順序番号を有する周辺ルータ（プレフィックスｊまでの最短経路内のルータ）の名前がルータｉに格納される。ルータｉの各周辺ノードを起点としてＳＰＦを１回動かした後、ルータｉは、トポロジテーブルＴＴｉに格納されるトポロジー情報に従って、各プレフィックスｊに関する各周辺ノードにより報告されるべきアンカーを取得する。上記で議論した通り、ルータｉの周辺ノードにより報告される、プレフィックスｊに関するこれらの一連のアンカーは
【０１０４】
【数３０】
2016119665.tif 000032
【０１０５】
と表され、アンカーテーブルＡＴｉに格納される。
【０１０６】
ループを含まないルーティングテーブルを有することが望ましい。そのために、いくつかの実施形態では、所与のプレフィックスから、そのプレフィックスの有効アンカーへの距離が、ルータｉからそのプレフィックスまでの距離以下であるが、そのプレフィックスがより小さい辞書式順序値の名前を有している場合に限り、ルータｉは、そのプレフィックスへのネクストホップとして周辺ルータを選択し得る。動作中、アンカーは、ローカルで有効なプレフィックスに関する更新情報を定期的に送信し、プレフィックスに割り当てる順序番号を増やし、それに応じて、ルータがそのルーティングテーブルを更新する。なお、ルータがそのネクストホップを変更するときに、ルーティングテーブルのループが作られていないことを十分に確認するためには、後者集合の順序条件（ＳＯＣ）を満たさなければならない。このＳＯＣは、以下の２つの記述が真の場合に限り、周辺ノードｋ（ルータｉとその周辺ルータを含む集合Ｎｉに属する）が、順序番号
【０１０７】
【数３１】
2016119665.tif 000033
【０１０８】
を有する要素（すなわち、ルータｉのプレフィックスｊへの有効なネクストホップ）になれることを示す。
記述（１）：
【０１０９】
【数３２】
2016119665.tif 000034
【０１１０】
および
【０１１１】
【数３３】
2016119665.tif 000035
【０１１２】
なお、「ｓｎ（ｍ）」は、ルータｉに知られている、プレフィックスｊに関する一連のアンカー
【０１１３】
【数３４】
2016119665.tif 000036
【０１１４】
のうちのアンカーｍによりプレフィックスｊに割り当てられる順序番号を示し、
【０１１５】
【数３５】
2016119665.tif 000037
【０１１６】
は、ルータｋにより報告される、プレフィックスｊに最も近いアンカーを示し、
【０１１７】
【数３６】
2016119665.tif 000038
【０１１８】
は、アンカー
【０１１９】
【数３７】
2016119665.tif 000039
【０１２０】
により割り当てられる、プレフィックスｊに関する順序番号を示し、「|ｉ|」は、名前ｉの辞書式順序値を示す。
【０１２１】
記述（１）には、既知のプレフィックスｊのアンカーからの最新の順序番号を報告する周辺ルータだけがネクストホップと見なされ得ることが規定されている。記述（２）には、それらの周辺ノードからプレフィックスｊまでの距離と、それらのノードの名前とに基づいて、それらのノードが辞書式に順序付けられていることが示されている。より具体的には、ルータｉがプレフィックスｊへの有限距離を有する場合、ルータｋがルータｉよりもプレフィックスに近いか、あるいはルータｋがルータｉとプレフィックスまでの同じ距離を有するが、ルータｋが、ルータｉより小さい辞書式順序値を有すると、ルータｉは、プレフィックスｊへのネクストホップとして、周辺ノードｋを選択することができる（記述（２）の１行目に規定される通り）。一方で、ルータｉがプレフィックスｊへの無限距離を有する場合、全ての周辺ノードの中で、ルータｋがプレフィックスｊへの最短有限距離を報告する、あるいは、プレフィックスｊへの最短有限距離を報告する周辺ノードの中で、ルータｋが最小識別子を有する場合に限り、ルータｉは、プレフィックスｊへのネクストホップとして、ルータｋを選択することができる（記述（２）の最後の３行で規定される通り）。
【０１２２】
図５には、本発明の実施形態に従った、ＬＣＲを実施するルータの例示的なアーキテクチャが示されている。図５では、ＬＣＲルータ５００は、トポロジテーブルモジュール５０２、アンカーテーブルモジュール５０４、ルーティングテーブルモジュール５０６、ＬＳＡ受信モジュール５０８、ＬＳＡ処理モジュール５１０、ＬＳＡ転送モジュール５１２、およびＬＳＡ生成モジュール５１４を含む。
【０１２３】
トポロジテーブルモジュール５０２は、トポロジテーブルの維持と更新を担う。上記で議論した通り、このトポロジテーブルには、リンクＬＳＡおよびプレフィックスＬＳＡの２種類のＬＳＡが含まれ得る。いくつかの実施形態では、全ての隣接リンクがその状態を変更し、新しいコンテンツが取得可能になったとき、あるいは、ＬＳＡ受信モジュール５０８がＬＳＡを受信したとき、トポロジテーブルモジュール５０２によりトポロジテーブルが更新される。アンカーテーブルモジュール５０４は、アンカーテーブルの維持と更新を担う。いくつかの実施形態では、アンカーテーブルを更新する際、最も近いアンカーを発見するために、トポロジテーブル内の最短経路優先（ＳＰＦ）アルゴリズムを動かす。さらに別の実施形態では、最も近いアンカーはアンカーテーブルに格納される。プレフィックスに最も近いアンカーに加えて、周辺ルータにより報告されたプレフィックスの一連のアンカーもアンカーテーブルに格納される。ルーティングテーブルモジュール５０６は、ルーティングテーブルの維持と更新を担い、各プレフィックスへのネクストホップ先の周辺ノード、および、そのプレフィックスへの最短経路の周辺ノードを規定する。同様に、ルーティングテーブルを更新する際、ルータだけでなく、ルータの周辺ノードも起点として用いて、ＳＰＦアルゴリズムが動かされる。いくつかの実施形態では、ルーティングテーブルでのループの発生を避けるため、ルーティングテーブルを更新する際、ルータの周辺ノードは、特定のプレフィックスへの有効なネクストホップと見なされるために、ＳＯＣ（両方の記述が真）を満たしていなければならない。
【０１２４】
ＬＳＡ受信モジュール５０８は、周辺ノードからのＬＳＡの受信を担い、ＬＳＡ処理モジュール５１０は、受信したＬＳＡの処理を担い、ＬＳＡ転送モジュール５１２は、ＬＳＡの転送を担う。いくつかの実施形態では、ＬＳＡ処理モジュール５１０が、受信したＬＳＡの順序番号および有効期間を調べる。いくつかの実施形態では、ＬＳＡ処理モジュール５１０が、受信したＬＳＡがリンクＬＳＡか、あるいは、プレフィックスＬＳＡかを判定する。周辺ノードｋからルータｉが受信したＬＳＡがリンク（ｕ，ｖ）に関する場合、このＬＳＡを
【０１２５】
【数３８】
2016119665.tif 000040
【０１２６】
と表すことができる。なお、このリンクＬＳＡには、リンク識別子、リンクのコスト、ルータｕにより作られる順序番号、およびＬＳＡの有効期間が含まれ得る。
【０１２７】
動作中、ＬＳＡ処理モジュール５１０は、ＬＳＡ内で識別されたリンクが、トポロジテーブル内に格納されているかどうかをさらに判定し得る。格納されていない場合は、そのリンクは新しいリンクであり、ＬＳＡ転送モジュール５１２によりＬＳＡは転送される。さらに別の実施形態では、ＬＳＡはネットワーク全体に氾濫する。リンクがトポロジテーブル内に既に格納されている場合、ＬＳＡ処理モジュール５１０は、ＬＳＡ内で規定されている順序番号が、トポロジテーブル内の対応エントリで規定されている順序番号より大きいかどうかを判定する。大きい場合で、かつ、ＬＳＡの有効期間が０より大きい場合、ＬＳＡ転送モジュール５１２は、受信したリンクＬＳＡをその他の周辺ルータに転送する。それ以外の場合、ルータｉはＬＳＡを削除することができる。
【０１２８】
周辺ノードｋからルータｉが受信するＬＳＡが、プレフィックスｊに関する場合（
【０１２９】
【数３９】
2016119665.tif 000041
【０１３０】
と表される）、ＬＳＡ処理モジュール５１０は、ルータｉからプレフィックスｊまでの最短距離が、仮想リンク（ｕ，ｊ）を含む経路を通っているかどうかを判定する。すなわち、ＬＳＡ処理モジュール５１０は、アンカーｕがプレフィックスｊに最も近いアンカーかどうかを判定する。いくつかの実施形態では、プレフィックスへの最短経路を計算するために、最短経路優先（ＳＰＦ）アルゴリズムを動かし、これにより、ルーティングテーブルとアンカーテーブルも更新される。アンカーｕが、最も近いアンカーであり、かつ、ＬＳＡの有効期間が０より大きい場合、ＬＳＡ転送モジュール５１２は、プレフィックスＬＳＡを他の周辺ルータに転送する。それ以外の場合、ルータｉは、そのＬＳＡを削除することができる（有効期間が切れている場合）、あるいは、ＬＳＡをそのトポロジテーブル内に格納する（ＬＳＡ内の順序番号が、同じ仮想リンクに関するトポロジテーブル内の既存のエントリの順序番号よりも大きい場合）。
【０１３１】
ＬＳＡ生成モジュール５１４は、ＬＳＡの生成を担う。いくつかの実施形態では、ＬＳＡ生成モジュール５１４は、周辺ノードへの物理リンクに関するリンクＬＳＡを定期的に生成し、リンク内で状態が変更されるたびに生成する。例えば、ルータｉは、その周辺ルータｖへの物理リンク（ｉ，ｖ）（
【０１３２】
【数４０】
2016119665.tif 000042
【０１３３】
で表される）に関するリンクＬＳＡを生成することができる。なお、ルータｉがＬＳＡを１回更新するごとに、リンクＬＳＡに関する順序番号
【０１３４】
【数４１】
2016119665.tif 000043
【０１３５】
が増やされ、ＬＳＡは有効期間
【０１３６】
【数４２】
2016119665.tif 000044
【０１３７】
の最大値を表示する。いくつかの実施形態では、ＬＳＡ生成モジュール５１４は、プレフィックスに関するプレフィックスＬＳＡを定期的に生成し、ローカルで利用可能なプレフィックス内で状態が変更されるたびに生成する。例えば、ルータｉは、プレフィックスｊに関するＬＳＡ（
【０１３８】
【数４３】
2016119665.tif 000045
【０１３９】
と表される）を生成することができる。なお、ルータｉがＬＳＡを１回更新するごとに、リンクＬＳＡに関する順序番号
【０１４０】
【数４４】
2016119665.tif 000046
【０１４１】
が増やされ、ＬＳＡは有効期間
【０１４２】
【数４５】
2016119665.tif 000047
【０１４３】
の最大値を表示する。生成されるＬＳＡは、ＬＳＡ転送モジュール５１２により、周辺ルータに転送され得る。なお、ＬＳＡの起点だけがＬＳＡに割り当てられる順序番号を変更することができる。
【０１４４】
最も近いプレフィックスのレプリカにルーティングする際、ＬＣＲを実装するルータは、トポロジテーブルおよびアンカーテーブルに維持されている情報を用いて、ルーティングテーブルを計算し、更新情報を周辺ルータに定期的に送信する、あるいは、そのトポロジテーブルに対する更新が行われるたびに送信する。いくつかの実施形態では、更新情報はＬＳＡの形態を取る。上記で議論した通り、動作中、ＬＣＲを実装するルータはＬＳＡを互いに送信し合って、それらのルータのリンクステート情報を更新する。しかし、ＬＣＲ内のＬＳＡの拡散は、従来のリンクステート型ルーティング（ＬＳＲ）プロトコルとは異なる。従来のＬＳＲプロトコルでは、ネットワーク全体に全てのＬＳＡを氾濫させる。一方、ＬＣＲでは、物理リンクに関するＬＳＡだけをネットワーク全体に氾濫させ、全ての既知プレフィックスに関して１つのアンカー（大抵の場合は、最短経路のアンカー）のみを各ルータが報告するように、プレフィックスに関するＬＳＡはネットワーク全体に伝わる。
【０１４５】
図６には、本発明の実施形態に従った、ＬＣＲルーティングの一例が示されている。図６では、ネットワーク６００は複数のルータを含み、これらのルータはそれぞれルータａ、ｂ、ｃ、…、ｘ、ｙ、およびｚなど、その名前で識別される。なお、ネットワーク６００には、ｇまたはｊの名前のルータは含まれていない。図６に示される例では、４つのルータ（図面内で影を付けられているルータｄ、ルータｕ、ルータｏ、およびルータｒ）が特定のプレフィックスのアンカールータとして機能している。なお、影が暗ければ暗いほど、そのルータの辞書式順序値は小さい。つまり、ルータｄは最も小さい辞書式順序値を有し、ルータｒは最も大きい辞書式順序値を有する。なお、図６では、各リンクがユニット・コストを有することを前提とする。
【０１４６】
図６では、各ルータの隣に１つ以上のタプルが辞書式順序で記載されており、各タプルには、プレフィックスのアンカーまでの距離と、そのアンカーの識別子が示されている。リスト内の第１のタプル（より暗いフォントで示されている）には、プレフィックスまでの最短距離と、その距離と同じ距離の全てのアンカーのうちで最も小さい名前のアンカーが表示されている。例えば、ルータｑの隣には３つのタプルが記載されており、ルータｑからアンカーｕまでの距離が１（１ホップ）であり、ルータｑからアンカーｒまでの距離が２（２ホップ）であり、ルータｑからアンカーｄまでの距離が３（３ホップ）であることが示されている。つまり、ルータｑからプレフィックスのアンカーまでの最短距離は１であり、その最短距離はアンカーｕまでの距離である。一方、ルータｈの隣には２つのタプルが記載されており、ルータｈからアンカーｄまでの距離が２（２ホップ）であり、ルータｈからアンカーｕまでの距離が２（２ホップ）であることが示されている。なお、ルータｄはルータｕよりも小さい辞書式順序値を有しているため、距離が同じ場合であっても、ルータｄが第１のタプル内で記載される。
【０１４７】
いくつかの実施形態では、各ルータからの更新情報には、優先アンカー（第１の名前付きアンカー）だけが表示されている。つまり、各ルータは、その周辺ルータに報告する情報を事前にフィルタリングしている。例えば、ネットワークの変更により、ルータｒがプレフィックスに関するアンカーになるとき、ルータｅで知られている全てのアンカーを報告する代わりに、ルータｅからの更新情報には、アンカーとしてのルータｒ、およびルータｒまでの距離として１が表示され得る。図６では、隣に付加的なタプルが記載されているルータもあり、これらの付加的なタプルにはそれぞれ、そのプレフィックスに関する別のアンカーと、そのアンカーまでの距離とが表示されている。これらの付加的なタプルは、ルータによって、周辺ルータには報告されない。図６で示されている例では、全てのルータが、プレフィックスのアンカーのいずれかから、最新の順序番号を受け取っていることが前提となる。
【０１４８】
アンカーにより生成される更新情報により、ルータがプレフィックスまでのより短い経路に提供される場合に限り、その更新情報は伝えられる。つまり、ＬＳＡを発行し、そのＬＳＡを周辺ルータに転送することにより、アンカーはローカルのプレフィックスに関する状態情報を更新する。しかし、ＬＳＡがプレフィックスへのより短い経路を示している場合に限り、そのＬＳＡは周辺ルータにより、周辺ルータに転送される。したがって、ネットワーク内に他のレプリカが存在している場合、起点のアンカーからＬＳＡが転送されるとき、より短い経路が提供されている可能性は低い。図６に示される例では、ネットワークの直径が８であっても、プレフィックスに関するルーティング更新情報は３ホップより先に伝わっていない。一般に、どれだけ多くの所与のプレフィックスに関するアンカーがネットワーク内に存在するかには関係なく、ルータは、その周辺ルータと同じ数のプレフィックスに関するアクティブアンカーを有するのみである。これは、各プレフィックスに関して知る最も良いアンカーだけを各ルータが報告しているためである。図６では、ノード間のリンクの矢印は、プレフィックスへのネクストホップであるルータを指し、これらのリンクはその影と形状で識別される。暗い実線の矢印は、それらのリンクがルータｄに向かっていることを示し、明るい実線の矢印は、それらのリンクがルータｏに向かっていることを示し、二重線の矢印は、それらのリンクがルータｒに向かっていることを示し、点線の矢印は、それらのリンクがルータｕに向かっていることを示す。
【０１４９】
なお、たった２４個のルータしか存在しない、この小さいネットワーク内でさえも、大部分のルータがプレフィックスまでの複数の経路を有し、そのうちの少なくとも１つが最短経路となる。図６では、全てのリンクを用いてコンテンツに関する要求を転送することが可能である。図６で見られる通り、プレフィックスのアンカーの４個のアンカー全てに関して知るルータは存在しない（ルータｎ、ルータｑ、およびルータｅはそれぞれ３個のアンカーを知っている）。同様に図６で見られる通り、全ての方向を有する潜在的経路の横断は、アンカー（アンカーｄ、アンカーｏ、アンカーｒ、またはアンカーｕ）のうちの１つで必ず終了し、ループを通過することはない。但し、ＬＣＲと共に取得されるルートにはループは存在しないが、プロトコルが全てのルーティングテーブルの更新を終了させた後、ネットワーク内の全てのルーティングテーブルが、一致していない間に、一時的なループが形成される可能性がある。
【０１５０】
ＩＣＮのアーキテクチャによって、異なる名前ベースの信号方式のアプローチを用いてＬＣＲが実施され得る。ＩＣＮネットワーク内でＬＣＲを実施する際、ルータの命名規則、更新メッセージの構文規則、周辺ルータの間での更新メッセージのやり取りの仕方について決めておく必要がある。
【０１５１】
いくつかの実施形態では、階層の名前空間を用いてルータの名前を付けることができる。例えば、特定のルータは、「／＜ｎｅｔｗｏｒｋ＞／＜ｓｉｔｅ＞／＜ｒｏｕｔｅｒ＞」などの階層の名前を持つことができ、このルータ上で動くＬＣＲデーモンを「／＜ｎｅｔｗｏｒｋ＞／＜ｓｉｔｅ＞／＜ｒｏｕｔｅｒ＞／ＬＣＲ」と名前付けることができる。
【０１５２】
ＬＣＲ内の更新処理の意味規則には、ルータがそのトポロジテーブルの増分更新情報を全ての周辺ルータに送ることが含まれる。いくつかの実施形態では、そのような更新メッセージは、ルータの名前、プロトコル（ＬＣＲ）、メッセージの種類、送信ルータにより増やされる順序番号により識別される。これらの更新メッセージは、定期的に送信され得、これらの更新メッセージは、そのルータが動作中であることを示す役割も果たしている。更新メッセージの構文規則、およびルータ間での正確なメッセージのやり取りの仕方は、ＬＣＲが動作するＩＣＮアーキテクチャ内で規定される基本的な信号方式に依存する。ルータ間の信号方式は、受信側起動または送信側起動でよい。
【０１５３】
受信側起動の信号方式では、受信者により記述されるインタレストにデータが続く。ＮＤＮまたはＣＣＮを用いるルータ内のＬＣＲ処理では、「ルーティングインタレスト」（ＲＩ）を定期的に送信して、ルーティング更新を周辺ルータから引き出さなくてはならない。ＮＬＳＲとは対照的に、ＬＣＲでは各周辺ルータの状態が異なり、それゆえ、ＬＣＲの信号方式は、同期メッセージに基づくことはできない。いくつかの実施形態では、ルータがＲＩを各周辺ルータに送信して、ルーティング情報を要求する。このＲＩは、「／＜ｎｅｔｗｏｒｋ＞／＜ｓｉｔｅ＞／＜ｒｏｕｔｅｒ＞／ＬＣＲ／ｕｐｄａｔｅ／ｓｅｑ＿ｎｏ」などの形式を有することができる。ＲＩを受信するルータは、最新のＲＩのときから存在するルーティングテーブルに対して行われる更新で「ルーティング更新」（ＲＵ）に対応するコンテンツオブジェクトに応じることができる。
【０１５４】
送信側起動の信号方式では、どの周辺ルータからもはっきりと依頼されていないが、各ルータはＲＵを全ての周辺ルータに送信し得る。この信号方式のアプローチを実施することはより効率的ではあるが、いくつかのＩＣＮアーキテクチャのデータ平面内に「プッシュ」機構を加えなければならない、または、インタレストの意味規則を変更しなければならない。例えば、ルータの存在を示す「Ｈｅｌｌｏ」メッセージを、長期のＲＩとして、送信することができ、同じルータからこのＨｅｌｌｏメッセージに、必要に応じて、複数のＲＵを送信することができる。あるいは、属性として更新を含むインタレストとしてＲＵを送信することができる。ルータから送信されるＲＩまたはＲＵにより、そのルータが動作していることがその周辺ルータに知らされる。
【０１５５】
いくつかの実施形態では、ＣＣＮまたはＮＤＮ内のＬＣＲ更新情報は、その更新情報の発信源であるアンカーから、デジタル署名され、その更新情報には、署名照合で用いる情報が表示されている。したがって、ローカルコンテンツのプレフィックスに関するＬＳＡが有効であることをＬＣＲは証明することができる。さらに、ＬＣＲに対する種々のセキュリティ機構を実装可能である。
【０１５６】
このセクションでは、制御プレーンにおける時間、通信、および格納の複雑度に基づいて、ＬＣＲの性能を、その他の名前ベースのコンテンツルーティングアプローチの性能と比較する。以下の議論では、ネットワーク内のルータの数はＮと示され、ネットワークリンクの数はＥと示される。さらに、ネットワーク内で取得可能な異なる名前のプレフィックスの数をＣとし、所与の名前のプレフィックスに関するレプリカの平均数をＲとし、ルータごとの周辺ルータの平均数ｌとし、ネットワーク直径をｄとする。
【０１５７】
説明を簡単にするために、所与のＬＳＡまたは距離の更新情報に関して別々の制御メッセージが送信されているものと想定する。実際には、複数のＬＳＡおよび距離の更新情報をまとめて、帯域幅を維持することができる。事実、複数のプレフィックスに関する距離の更新情報をまとめるほうが、複数の供給源からＬＳＡをまとめることよりも簡単である。しかし、ＮまたはＣの増加には関係なく、制御メッセージの最大サイズが一定な値であることを考慮すると、ルーティングプロトコルにより生じるオーバーヘッドのオーダーサイズはこの集約により変化しない。
【０１５８】
ルーティングプロトコルの通信の複雑度（ＣＣ）は、全てのＣ個のプレフィックスに関する正確なルーティング情報を得るために、ルータごとに正しく送信されなければならないメッセージの数である。ルーティングプロトコルの時間の複雑度（ＴＣ）は、全てのメッセージが正しく送信されるときに、全てのルータが全てのプレフィックスに関して正確なルーティング情報を得るために必要な最大時間である。ルーティングプロトコルの格納の複雑度（ＳＣ）は、任意のルータのルーティングテーブル内のエントリの最大数である。受信側起動の信号方式または送信側起動の信号方式を用いる周辺ルータ間でやり取りされるメッセージの数の差がＮ、ＣおよびＲとは関係ないことを考慮すると、本明細書で示される結果は、両方の種類の信号方式のアプローチに適用され得る。
【０１５９】
背景技術のセクションで議論した通り、ＮＬＳＲおよびＯＳＰＦＮでは、リンクステート型ルーティング（ＬＳＲ）のアプローチを用いる。ＬＳＲを用いる場合、リンクまたは名前のプレフィックスに関するルータを起点とするＬＳＡはネットワーク内の全てのその他のルータに送信されなければならない。さらに、各隣接リンク、およびローカルで格納される各プレフィックスに関するＬＳＡをルータは送信しなければならず、各ＬＳＡはネットワーク内で氾濫しなければならず、各ルータはネットワーク内のプレフィックスのコピーをリンクごとの記録と共に格納しなければならない。したがって、ＬＳＲの時間、通信、格納の複雑度は下記の通り表される。
ＴＣＬＳＲ＝Ｏ（ｄ）；
ＣＣＬＳＲ＝Ｏ（Ｅ×Ｒ×Ｃ＋ｌ×Ｅ×Ｎ）；
ＳＣＬＳＲ＝Ｏ（Ｒ×Ｃ＋Ｅ）
【０１６０】
次に、分散ハッシュテーブル（ＤＨＴ）に依存するルーティングアプローチについて説明する。最も効率的なＤＨＴスキームは、ワンホップルーティングを行う仮想ＤＨＴであり、この仮想ＤＨＴでは、ルータはＤＨＴをローカルで動かし、ネットワーク内の全てのルータへのルートを維持する。ＤＨＴ内でプレフィックスを発行し、そのプレフィックスとｒ個のサイトとを関連付けること（任意または全てのプレフィックスのコピーへのルーティングをサポートするために）に関する通信の複雑度は、Ｏ（ｄ＊Ｒ×Ｃ）であり、これはループが存在しないことを前提とする。リンクステート型ルーティングが通常通り使用されていることを考慮すると、全てのルータへのルートを維持する通信の複雑度は、Ｏ（ｌ＊Ｎ×Ｅ）である。全てのルータへのルートの最も速い可能性のある伝達は、次数Ｏ（ｄ）であり、各ルータは、ネットワーク内に存在するプレフィックスと同じ数のプレフィックスに関する記録を格納しなければならない。したがって、ＤＨＴの時間、通信、格納の複雑度は下記の通り表される。：
ＴＣＤＨＴ＝Ｏ（ｄ）；
ＣＣＤＨＴ＝Ｏ（ｄ×Ｒ×Ｃ＋ｌ×Ｅ×Ｎ）；
ＳＣＤＨＴ＝Ｏ（Ｃ＋Ｅ）
【０１６１】
次に、従来の距離ベクトルルーティング（ＤＶＲ）アプローチについて説明する。ＤＶＲの信号方式では、長い経路を横断することができることから、長期間のループおよび「無限カウント」が発生する可能性があり、基本的な距離ベクトルアプローチは、時間の複雑度Ｏ（Ｎ）、および通信の複雑度Ｏ（Ｎ２）を有することで知られている。さらに、各ルータは、ネットワーク内の全てのプレフィックスのレプリカおよび目的地ノードに関する距離情報を格納し通信しなければならない。したがって、ＤＶＲの時間、通信、格納の複雑度は下記の通り表される。
ＴＣＤＶＲ＝Ｏ（Ｎ）；
ＣＣＤＶＲ＝Ｏ（Ｎ２×Ｒ×Ｃ）；
ＳＣＤＶＲ＝Ｏ（Ｒ×Ｃ＋Ｎ）
これから分かる通り、ＤＶＲの複雑度は、ＬＳＲアプローチおよびＤＨＴアプローチの複雑度よりもかなり劣る。距離ベクトルを用いる名前ベースのルーティングがなぜ過去において考慮されなかったかが分かる。
【０１６２】
一方、ＬＣＲのアプローチでは、所与のプレフィックスに関するルータが通信する情報は、所与のプレフィックスまたはネットワーク内のルータに関するアンカーの数とは関係ない。より具体的には、ＬＣＲでは、所与のプレフィックスに関して、ルータは、プレフィックスから最も近いアンカーまでの距離、ならびに、アンカーの名前、およびそのアンカーにより作られる最新の順序番号だけを通信する。レプリカの数が増えると、ルータから最も近いプレフィックスのレプリカまでの距離は実際には短くなり、任意のルータから最も近いプレフィックスのレプリカまでのホップ数（ｘ）は、いつでも、最大でｄ回のホップであることは事実である。さらに、上記で議論した通り、ＬＣＲはルーティングテーブルでループを発生させない。このことは、次のことを意味する。：（１）全てのルーティング情報は、その起点から受信者までの最短経路と同じ速さで伝達される。（２）プレフィックスが複製される回数（Ｒ）には関係なく、全てのルータが所与のプレフィックスまでの正確な距離を得るために必要なメッセージの数はＯ（Ｅ）である。ネットワーク内にＣ個のプレフィックスが存在することを考慮すると、ＬＣＲの複雑度は下記の通り表される。
ＴＣＬＣＲ＝Ｏ（ｘ）；
ＣＣＬＣＲ＝Ｏ（Ｅ×Ｃ）；
ＳＣＬＣＲ＝Ｏ（ｌ×Ｃ＋Ｅ）
【０１６３】
上記の分析により、ＬＣＲは、ＬＳＲまたはＤＶＲよりもはるかに低い格納の複雑度を有することが明確に示される。というのも、ＬＣＲのルータは、プレフィックスのレプリカごとに１つエントリを格納するのではなく、プレフィックスに関して１つのエントリだけを格納すればよく、全てのトポロジー情報を格納する必要はないからである。特に大きなネットワークでは、ＲがＯ（Ｎ）になると、ＬＣＲは、ＬＳＲやＤＶＲよりも桁違いに小さい記憶オーバーヘッドしか必要としない。なお、大きなネットワークにおける格納の複雑度に関して、ＬＣＲはＤＨＴアプローチと同等である。その一方で、その他のアプローチと比べると、ＬＣＲはかなり小さい時間の複雑度、および桁違いに小さい通信の複雑度を有する。より具体的には、ＬＣＲにより、ルータは、ＤＶＲ、ＬＳＲ、およびＤＨＴを用いるときよりもかなり速く、正確なルーティングテーブルを得ることができる。というのも、ルータは、全てのコピーではなく、最も近いプレフィックスのコピーに関する更新情報をやり取りするだけであり、コンテンツのレプリカが増えるにつれ、そのような更新情報は、ネットワーク直径よりもかなり短くなる経路を横断するだけでよいからである。
【０１６４】
図７には、本発明の実施形態に従った、リンクステート型コンテンツルーティングを行う例示的なシステムが示されている。リンクステート型コンテンツルーティングを行うシステム７００は、プロセッサ７１０、メモリ７２０、および記憶装置７３０を含む。通常、記憶装置７３０は、メモリ７２０内にローディングされ、上記の方法を行うプロセッサ７１０が実行可能な命令を格納する。ある実施形態では、記憶装置７３０内の命令は、トポロジテーブルモジュール７３２、アンカーテーブルモジュール７３４、ルーティングテーブルモジュール７３６、ＬＳＡ受信モジュール７３８、ＬＳＡ処理モジュール７４０、ＬＳＡ転送モジュール７４２、およびＬＳＡ生成モジュール７４４を実装可能であり、これらのモジュールは全て種々の手段を通して互いに通信可能である。
【０１６５】
いくつかの実施形態では、モジュール７３２〜７４４は、ハードウェア内に部分的または完全に実装可能であり、プロセッサ７１０の一部でよい。さらに、いくつかの実施形態では、分離したプロセッサおよびメモリをシステムが含まなくてもよい。その代わり、モジュール７３２〜７４４が、その特定のタスクを実行する以外に、個々に、あるいは共働して、汎用のコンピュータエンジンまたは専用のコンピュータエンジンとして機能し得る。
【０１６６】
記憶装置７３０は、プロセッサ７１０が実行するプログラムを格納する。具体的には、記憶装置７３０は、リンクステート型コンテンツルーティングに関するシステム（アプリケーション）を実施するプログラムを格納する。動作中、アプリケーションプログラムは、記憶装置７３０からメモリ７２０にローディングされ、プロセッサ７１０により実行され得る。その結果、システム７００は上記の機能を実行することができる。システム７００は、随意的なディスプレイ７８０（タッチスクリーン・ディスプレイでもよい）、キーボード７６０、ポインティングディバイス７７０に接続可能であり、１つ以上のネットワークインターフェースを介してネットワーク７８２にも接続可能である。
【０１６７】
詳細な説明に記載されている、データ構造およびコードは、通常、コンピュータ可読記憶媒体に格納される。このコンピュータ可読記憶媒体は、コンピュータシステムが使用するコード、および／またはデータを格納可能な全ての装置または媒体でよい。このようなコンピュータ可読記憶媒体には、揮発性メモリ、不揮発性メモリ、ディスクドライブなどの磁気記憶装置および光学記憶装置、磁気テープ、ＣＤ（コンパクトディスク）、ＤＶＤ（デジタル多機能ディスクまたはデジタルビデオディスク）、または、現在知られている、あるいは将来開発されるコンピュータ可読媒体を格納可能なその他の媒体が含まれるが、これらには限定されない。
【０１６８】
詳細な説明のセクションに記載されている方法および処理は、コード、および／またはデータとして具現化することができ、上記の通り、コンピュータ可読記憶媒体内に格納することができる。コンピュータシステムが、コンピュータ可読記憶媒体上に格納されるコード、および／またはデータを読み取り、実行すると、このコンピュータシステムは、データ構造およびコードとして具現化され、コンピュータ可読記憶媒体内に格納される方法および処理を実行する。
【０１６９】
さらに、本明細書に記載されている方法および処理は、ハードウェアのモジュールまたは装置内に含まれ得る。これらのモジュールまたは装置には、特定用途向け集積回路（ＡＳＩＣ）チップ、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、特定の時間に特定のソフトウェアモジュールまたは１つのコードを実行する専用または共有プロセッサ、および／または、現在知られている、あるいは将来開発されるその他のプログラム可能な論理回路が含まれ得るが、これらには限定されない。ハードウェアのモジュールまたは装置が起動すると、その中に含まれる方法および処理が実行される。
【図１】
2016119665.tif 000048
【図２】
2016119665.tif 000049
【図３】
2016119665.tif 000050
【図４】
2016119665.tif 000051
【図５】
2016119665.tif 000052
【図６】
2016119665.tif 000053
【図７】
2016119665.tif 000054