(57)【要約】      （修正有）【課題】情報指向ネットワークにおけるコンテンツ配置のための方法、システム、媒体を提供する。【解決手段】方法は、要求ノードから生じたＩｎｔｅｒｅｓｔパケットを受信するステップを有し、意志決定ノード及び前記要求ノードは、ツリートポロジを有する下位ネットワークの複数のノードの一部であって、前記Ｉｎｔｅｒｅｓｔパケットはコンテンツ及び前記要求ノードを特定する。コンテンツが前記複数のノードのうちの１又は複数の中間ノードに格納されていることに応答して、前記方法は、前記意志決定ノードにおいて解決フラグがオンの前記Ｉｎｔｅｒｅｓｔパケットを受信し、前記意志決定ノードにあるアクセス履歴テーブルを更新するステップ、を更に有する。【選択図】図６
2016111703.tif 000002
【特許請求の範囲】
【請求項１】
意志決定ノードにおいて、要求ノードから生じたＩｎｔｅｒｅｓｔパケットを受信するステップであって、前記意志決定ノード及び前記要求ノードは、ツリートポロジを有する下位ネットワークの複数のノードの一部であり、前記Ｉｎｔｅｒｅｓｔパケットはコンテンツ及び前記要求ノードを特定する、ステップと、
前記下位ネットワークの前記複数のノードのうち前記要求ノードと前記意志決定ノードとの間の経路に配置される１又は複数の中間ノードに前記コンテンツが格納されていることに応答して、
前記意志決定ノードにおいて、解決フラグがオンである前記Ｉｎｔｅｒｅｓｔパケットを受信し、
前記意志決定ノードにおいて、アクセス履歴テーブルを更新するステップと、
前記コンテンツが、前記下位ネットワークの前記複数のノードのうちの前記１又は複数の中間ノードの各々に存在しないことに応答して、
前記意志決定ノードにおいて、前記解決フラグがオフである前記Ｉｎｔｅｒｅｓｔパケットを受信し、
前記意志決定ノードにおいて、前記アクセス履歴テーブルを更新し、
前記コンテンツについて前記意志決定ノードを調べるステップと、
を有する方法。
【請求項２】
前記コンテンツが、前記１又は複数の中間ノード及び前記意志決定ノードに存在しないことに応答して、
前記コンテンツは、前記下位ネットワークの前記複数のノードのうちのピアノードに格納されていると判断するステップであって、前記ピアノードは、前記要求ノードと前記意志決定ノードとの間の前記経路の外側にある、ステップと、
前記意志決定ノードから前記ピアノードへ前記Ｉｎｔｅｒｅｓｔパケットを転送するステップと、
を更に有する請求項１に記載の方法。
【請求項３】
１又は複数の中間ノード及び／又は１又は複数のピアノードが、前記意志決定ノードと前記コンテンツを有する前記ピアノードとの間に位置することに応答して、前記意志決定ノードが、前記Ｉｎｔｅｒｅｓｔパケットの中に、前記コンテンツを有する前記ピアノードへの道順を含めるステップであって、前記１又は複数のピアノードは、前記要求ノードと前記意志決定ノードとの間の前記経路の外側にある、ステップ、を更に有する請求項２に記載の方法。
【請求項４】
前記コンテンツは前記ピアノードに格納されていると判断するステップは、線形計画最適化を実行して得られた解を調べるステップを有する、請求項２に記載の方法。
【請求項５】
前記線形計画最適化は、前記アクセス履歴テーブルにより決定される、前記下位ネットワークの各ノードにおける前記下位ネットワークの各コンテンツの人気に基づくパラメータを有し、前記線形計画最適化を実行するステップは、前記コンテンツのＤａｔａパケットの中の１又は複数のキャッシュフラグの各々を設定する確率を決定するステップを有する、請求項４に記載の方法。
【請求項６】
前記意志決定ノードにおける前記コンテンツのＤａｔａパケットの受信に応答して、前記要求ノードに、前記１又は複数の中間ノードのうちの少なくとも１つに、又はそれらの両者に前記コンテンツを格納するよう指示するために、前記Ｄａｔａパケットの中の１又は複数のキャッシュフラグを設定するステップ、を更に有する請求項１に記載の方法。
【請求項７】
前記１又は複数のキャッシュフラグを設定するステップの前に、前記１又は複数のキャッシュフラグの各々を設定する確率を決定するために線形計画最適化を実行するステップを更に有する、請求項６に記載の方法。
【請求項８】
前記線形計画最適化は、前記アクセス履歴テーブルにより決定される、前記下位ネットワークの各ノードにおける前記下位ネットワークの各コンテンツの人気に基づくパラメータを有する、請求項７に記載の方法。
【請求項９】
前記線形計画最適化を実行するステップは、前記下位ネットワークの前記複数のノードのうちの１又は複数のノードにおける記憶サイズ割り当てを決定するステップを有する、請求項８に記載の方法。
【請求項１０】
ツリートポロジを有するネットワークの複数のノードを有し、前記複数のノードは、意志決定ノード、要求ノード、及び１又は複数の中間ノードを有し、前記意志決定ノードは、
前記要求ノードから生じたＩｎｔｅｒｅｓｔパケットを受信し、前記Ｉｎｔｅｒｅｓｔパケットはコンテンツ及び前記要求ノードを特定し、
前記要求ノードと前記意志決定ノードとの間の経路に配置される前記１又は複数の中間ノードに前記コンテンツが格納されていることに応答して、
解決フラグがオンである前記Ｉｎｔｅｒｅｓｔパケットを受信し、
前記意志決定ノードにあるアクセス履歴テーブルを更新し、
前記コンテンツが、前記１又は複数の中間ノードの各々に存在しないことに応答して、
前記解決フラグがオフである前記Ｉｎｔｅｒｅｓｔパケットを受信し、
前記意志決定ノードにある前記アクセス履歴テーブルを更新し、
前記コンテンツについて前記意志決定ノードを調べる、
よう構成される、システム。
【請求項１１】
前記コンテンツが、前記１又は複数の中間ノード及び前記意志決定ノードに存在しないことに応答して、前記意志決定ノードは、
前記コンテンツは、前記要求ノードと前記意志決定ノードとの間の前記経路の外側にある前記ネットワークの前記複数のノードのうちのピアノードに格納されていると判断し、
前記意志決定ノードから前記ピアノードへ前記Ｉｎｔｅｒｅｓｔパケットを転送する、
よう更に構成される、請求項１０に記載のシステム。
【請求項１２】
前記意志決定ノードは、１又は複数の中間ノード及び／又は１又は複数のピアノードが、前記意志決定ノードと前記コンテンツを有する前記ピアノードとの間に位置することに応答して、前記Ｉｎｔｅｒｅｓｔパケットの中に、前記コンテンツを有する前記ピアノードへの道順を含め、前記１又は複数のピアノードは、前記要求ノードと前記意志決定ノードとの間の前記経路の外側にある、よう更に構成される、請求項１１に記載のシステム。
【請求項１３】
前記意志決定ノードは、
線形計画最適化を実行して得た解を調べるよう構成されることにより、前記コンテンツが前記ピアノードに格納されていると判断し、前記線形計画最適化は、前記アクセス履歴テーブルにより決定される、前記ネットワークの各ノードにおける前記ネットワークの各コンテンツの人気に基づくパラメータを有し、
前記コンテンツのＤａｔａパケットの中の１又は複数のキャッシュフラグの各々を設定する確率を決定する、
よう構成される、請求項１１に記載のシステム。
【請求項１４】
前記意志決定ノードは、前記意志決定ノードにおける前記コンテンツのＤａｔａパケットの受信に応答して、前記要求ノードに、前記１又は複数の中間ノードのうちの少なくとも１つに、又はそれらの両者に前記コンテンツを格納するよう指示するために、前記Ｄａｔａパケットの中の１又は複数のキャッシュフラグを設定するよう更に構成される、請求項１０に記載のシステム。
【請求項１５】
前記意志決定ノードは、前記１又は複数のキャッシュフラグを設定する前に、前記１又は複数のキャッシュフラグの各々を設定する確率を決定するために線形計画最適化を実行するよう更に構成され、
前記線形計画最適化は、前記アクセス履歴テーブルにより決定される、前記ネットワークの各ノードにおける前記ネットワークの各コンテンツの人気に基づくパラメータを有し、
前記線形計画最適化の実行は、前記ネットワークの前記複数のノードのうちの１又は複数のノードにおける記憶サイズ割り当ての決定を含む、
請求項１４に記載のシステム。
【請求項１６】
非一時的コンピュータ可読媒体であって、格納されたコンピュータ可読命令を有し、前記コンピュータ可読命令は、動作を実行し又は該動作の性能を制御するためにプロセッサにより実行可能であり、前記動作は、
意志決定ノードにおいて、要求ノードから生じたＩｎｔｅｒｅｓｔパケットを受信するステップであって、前記意志決定ノード及び前記要求ノードは、ツリートポロジを有する下位ネットワークの複数のノードの一部であり、前記Ｉｎｔｅｒｅｓｔパケットはコンテンツ及び前記要求ノードを特定する、ステップと、
前記下位ネットワークの前記複数のノードのうち前記要求ノードと前記意志決定ノードとの間の経路に配置される１又は複数の中間ノードに前記コンテンツが格納されていることに応答して、
前記意志決定ノードにおいて、解決フラグがオンである前記Ｉｎｔｅｒｅｓｔパケットを受信し、
前記意志決定ノードにおいて、アクセス履歴テーブルを更新するステップと、
前記コンテンツが、前記下位ネットワークの前記複数のノードのうちの前記中間ノードに存在しないことに応答して、
前記意志決定ノードにおいて、前記解決フラグがオフである前記Ｉｎｔｅｒｅｓｔパケットを受信するステップと、
前記意志決定ノードにおいて、前記アクセス履歴テーブルを更新し、
前記コンテンツについて前記意志決定ノードを調べるステップと、
前記コンテンツが前記中間ノード及び前記意志決定ノードに存在しないことに応答して、
前記コンテンツは前記下位ネットワークの前記複数のノードのうちのピアノードに格納されていると判断し、前記ピアノードは、前記要求ノードと前記意志決定ノードとの間の前記経路の外側にあり、
前記意志決定ノードから前記ピアノードへ前記Ｉｎｔｅｒｅｓｔパケットを転送するステップと、
を有する、非一時的コンピュータ可読媒体。
【請求項１７】
前記動作は、１又は複数の中間ノード又は１又は複数のピアノードが、前記意志決定ノードと前記コンテンツを有する前記ピアノードとの間に位置することに応答して、前記Ｉｎｔｅｒｅｓｔパケットの中に、前記コンテンツを有する前記ピアノードへの道順を含めるステップ、を更に有し、
前記１又は複数のピアノードは、前記要求ノードと前記意志決定ノードとの間の前記経路の外側にある、
請求項１６に記載の非一時的コンピュータ可読媒体。
【請求項１８】
前記コンテンツが前記ピアノードに格納されていると判断するステップは、線形計画最適化を実行して得た解を調べるステップを有し、前記線形計画最適化は、前記アクセス履歴テーブルにより決定される、前記下位ネットワークの各ノードにおける前記下位ネットワークの各コンテンツの人気に基づくパラメータを有し、
前記動作は、前記コンテンツのＤａｔａパケットの中の１又は複数のキャッシュフラグの各々を設定する確率を決定するステップを更に有する、
請求項１６に記載の非一時的コンピュータ可読媒体。
【請求項１９】
前記動作は、前記意志決定ノードにおける前記コンテンツのＤａｔａパケットの受信に応答して、前記要求ノードに、前記１又は複数の中間ノードのうちの少なくとも１つに、又はそれらの両者に前記コンテンツを格納するよう指示するために、前記Ｄａｔａパケットの中の１又は複数のキャッシュフラグを設定するステップ、を更に有する、請求項１６に記載の非一時的コンピュータ可読媒体。
【請求項２０】
前記動作は、前記１又は複数のキャッシュフラグを設定する前に、前記１又は複数のキャッシュフラグの各々を設定する確率を決定するために線形計画最適化を実行するステップ、を更に有し、
前記線形計画最適化は、前記アクセス履歴テーブルにより決定される、前記下位ネットワークの各ノードにおける前記下位ネットワークの各コンテンツの人気に基づくパラメータを有し、
前記線形計画最適化を実行するステップは、前記下位ネットワークの前記複数のノードのうちの１又は複数のノードにおける記憶サイズ割り当てを決定するステップを含む、
請求項１９に記載の非一時的コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本願明細書で議論する実装は、情報指向ネットワークにおけるコンテンツ配置に関する。
【背景技術】
【０００２】
本願明細書に特に示されない限り、本願明細書に記載される構成要素は、本願の請求項に対する従来技術ではなく、この章に含まれることにより従来技術と見なされるものではない。
【０００３】
現在のインターネット構造はホスト指向であり且つ１対１パラダイムに基づくが、ビデオ、音楽、写真、文書等を閲覧する及び共有するような現在のインターネットの使用の大部分は、ホスト指向の態様とは異なるデータ又はコンテンツ指向の態様を有する場合が多い。エンドポイントがインターネットプロトコル（ＩＰ）アドレスの代わりに名前付きデータに基づき通信する情報指向ネットワーク（Information  centric  network：ＩＣＮ）は、ホスト指向インターネットアーキテクチャの代替として発展してきた。ＩＣＮは、スケーラブル且つコスト効率の良いコンテンツ配信を提供しようとしている。
【０００４】
本願明細書で請求される主題は、上述のような欠点を解決する実装や上述のような環境でのみ機能する実装に限定されない。むしろ、この背景技術は、単に、本願明細書に記載される複数の実装が実施される技術分野の一例を説明するために提供される。
【発明の概要】
【０００５】
一実装の態様によると、方法は、要求ノードから生じたＩｎｔｅｒｅｓｔパケットを受信するステップを有し、前記意志決定ノード及び前記要求ノードは、ツリートポロジを有する前記下位ネットワークの複数のノードの一部であって、前記Ｉｎｔｅｒｅｓｔパケットはコンテンツ及び前記要求ノードを特定する。前記方法は、前記コンテンツが前記下位ネットワークの前記複数のノードのうちの１又は複数の中間ノードに格納されていることに応答して、前記１又は複数の中間ノードは前記要求ノードと前記意志決定ノードとの間の経路の中に位置し、前記意志決定ノードにおいて解決フラグがオンの前記Ｉｎｔｅｒｅｓｔパケットを受信するステップと、前記意志決定ノードにあるアクセス履歴テーブルを更新するステップと、を更に有する。前記方法は、前記コンテンツが前記下位ネットワークの前記複数のノードのうちの前記１又は複数の中間ノードの各々に存在しないことに応答して、前記意志決定ノードにおいて前記解決フラグがオフの前記Ｉｎｔｅｒｅｓｔパケットを受信するステップと、前記意志決定ノードにあるアクセス履歴テーブルを更新するステップと、前記コンテンツについて前記意志決定ノードを調べるステップと、を更に有する。
【０００６】
実施形態の目的及び利点が理解され、少なくとも特に特許請求の範囲で指摘された要素、特徴及び組合せを用いて達成されるだろう。
【０００７】
上述の全体的説明及び以下の詳細な説明の両方は、例示及び説明のためであり、本発明の範囲を限定しないことが理解される。
【図面の簡単な説明】
【０００８】
例示的な実装は、添付の図面を用いて、更なる特異性及び詳細事項と共に記載され説明される。
【図１】幾つかの実装が実施され得る例示的なＩＣＮを示す概略図である。
【図２Ａ】標準的なＩＣＮルータの３つの例示的なデータ構造の概略図である。
【図２Ｂ】意志決定ルータにおける例示的な解テーブル及びアクセス履歴テーブルの概略図である。
【図３Ａ】２レベルツリートポロジを有する下位ネットワークを含む例示的なＩＣＮを示す概略図である。
【図３Ｂ】意志決定ノードにより実行され得る例示的な線形計画最適化を示す。
【図３Ｃ】意志決定ノードにより実行され得る例示的な線形計画最適化を示す。
【図３Ｄ】図３Ｂ〜３Ｃの線形計画最適化で用いられる表記法の表である。
【図４】例示的なＩＣＮルータシステムを説明するブロック図である。
【図５Ａ】例示的なコンテンツ検索シナリオの概略図である。
【図５Ｂ】例示的なコンテンツ検索シナリオの概略図である。
【図５Ｃ】例示的なコンテンツ検索シナリオの概略図である。
【図６】ＩＣＮの下位ネットワークの中のノードのネットワークの間のコンテンツ配置スキームを説明する例示的なフロー図である。
【発明を実施するための形態】
【０００９】
インターネットでビデオ及びオーディオをストリーミングする要求は、近年増大しており、インターネットトラフィックを増大させている。情報指向ネットワーク（ＩＣＮ）は、コンテンツ配信を増強するためにネットワーク内のキャッシングのためのアーキテクチャを提供する。ＩＣＮは、１又は複数の下位ネットワークを有し得る。下位ネットワークの中では、ルータはコンテンツを共有するために互いに接続されても良い。１又は複数の下位ネットワークの各ルータは、要求されるコンテンツを格納するために、記憶空間も有し得る。ＩＣＮの下位ネットワークでは、全体の記憶及びリンク能力が限られているとき、コンテンツが格納される場所と各ルータにおけるストレージサイズ割り当てとの両者の最適化は、ＩＣＮのデータ配信の全体コストを削減し得る。したがって、本願明細書に記載の幾つかの実装は、ＩＣＮアーキテクチャ、及び最適化を通じてネットワーク又はコンテンツプロバイダへのデータ配信の全体コストを削減できる通信プロトコルをサポートすることに関する。本願明細書で言及される「最適化」は、実関数を最大化すること又は最小化することを含み得る。ここで、「最大化」又は「最小化」は、必ずしも絶対的な最大又は最小ではなく、他の値と比べたとき想定的な最大又は最小を達成することを意味する。
【００１０】
本願明細書に記載の幾つかの実装では、下位ネットワークの中の各ノードにおける要求コンテンツの人気（popularity）に基づく線形計画最適化は、下位ネットワークの中のコンテンツ配置及び記憶サイズ割り当てを決定するために実行され又は解かれても良い。
【００１１】
本発明の実装を、添付の図面を参照して以下に説明する。
【００１２】
図１Ａは、本願明細書に記載の少なくとも１つの実装に従って配置される例示的なＩＣＮ１００の概略図である。ＩＣＮ１００は、Ｄａｔａパケットを配信するための「Ｉｎｔｅｒｅｓｔパケット」とも称されるメッセージをルーティングするよう構成されるノードのネットワークを有しても良い。用語「Ｉｎｔｅｒｅｓｔパケット」は、特定のコンテンツのための要求を表しても良い。用語「Ｄａｔａパケット」は、Ｉｎｔｅｒｅｓｔパケットに適応するコンテンツを表しても良い。各Ｉｎｔｅｒｅｓｔパケットは、１つのＤａｔａパケットに対応しても良い。
【００１３】
種々の実装では、ＩＣＮ１００は、インターネット又はその部分を含んでも良く、又はその中に含まれても良い。図１Ａに示すように、ＩＣＮ１００は、サーバ１０４と、２個の上流ノード１０５、２個のコア若しくは意志決定ノード１０１ａ、１０１ｂ（概して、「意志決定ノード１０１」又は「複数の意志決定ノード１０１」）、２個の中間ノード１０２ａ、１０２ｂ（概して、「中間ノード１０２」又は「複数の中間ノード１０２」）、２個の要求ノード１０３ａ、１０３ｂ（概して、「要求ノード１０３」又は「複数の要求ノード１０３」）及び８個のピアノード１０６ａ〜１０６ｈ（概して、「ピアノード１０６」又は「複数のピアノード１０６」）を含む多数のネットワークノードと、を有する。
【００１４】
本開示の利益により、図１Ａに示すＩＣＮ１００は幾つかの点で簡素化されていることが明らかである。例えば、ＩＣＮ１００は、図１Ａに示されたのと異なる数の要求ノード１０３、中間ノード１０２、ピアノード１０６、及び／又は意志決定ノード１０１を有しても良い。ＩＣＮ１００は、意志決定ノード１０１とサーバ１０４との間に上流ノード１０５を有しても良い。ＩＣＮ１００は、意志決定ノード１０１と要求ノード１０３との間に追加中間ノード１０２を有しても良い。ＩＣＮ１００は、クライアント、サーバ、ルータ、スイッチ、及び／又は他のネットワーク装置のような様々な追加ネットワークノードを有しても良い。さらに、意志決定ノード１０１は、要求ノード１０３に直接結合されても良い。意志決定ノード１０１は、サーバ１０４に直接結合されても良い。要求ノード１０３は、意志決定ノード１０１に直接結合されても良い。
【００１５】
ＩＣＮ１００のネットワークトポロジは、階層的構造を有しても良い。ネットワークトポロジは、ツリー構造又はツリー構造のセットを有しても良い。図１Ａに示した階層的ツリー構造トポロジでは、中間ノード１０２は、意志決定ノード１０１及び要求ノード１０３を相互接続して、Ｉｎｔｅｒｅｓｔパケット及びＤａｔａパケットがこれらのノード間で交換できるようにしても良い。意志決定ノード１０１は、サーバ１０４への経路上で中間ノード１０２及び上流ノード１０５を相互接続して、Ｉｎｔｅｒｅｓｔパケット及びＤａｔａパケットがこれらのノード間で交換できるようにしても良い。同様に、上流ノード１０５は、意志決定ノード１０１及びサーバ１０４を相互接続して、Ｉｎｔｅｒｅｓｔパケット及びＤａｔａパケットがこれらのノード間で交換できるようにしても良い。要求ノード１０３及びピアノード１０６は、中間ノード１０２より下流にあると考えられる。中間ノード１０２は、意志決定ノード１０１より下流にあると考えられる。意志決定ノード１０１は、上流ノード１０５より下流にあると考えられる。上流ノード１０５は、サーバ１０４の下流にあると考えられる。
【００１６】
ネットワークの要求ノード１０３、ピアノード１０６、中間ノード１０２、位置決定ノード１０１、及び上流ノード１０５の各々は、ルータを有しても良い。用語「ルータ」は、Ｉｎｔｅｒｅｓｔパケットを受信し及び転送し、及び／又はＤａｔａパケットを受信し及び転送することが可能な任意のネットワーク装置を表しても良い。用語「サーバ」は、Ｉｎｔｅｒｅｓｔパケットを受信し、及びＤａｔａパケットを供給することが可能な任意の装置を表しても良い。要求ノード１０３、ピアノード１０６、中間ノード１０２、意志決定ノード１０１、上流ノード１０５及びサーバ１０４は、コンテンツを、又はより一般的には、それぞれ少なくとも１つのコンテンツ名により識別される１又は複数の異なるコンテンツをホスティングしても良い。
【００１７】
要求ノード１０３の各々は、デスクトップコンピュータ、ラップトップコンピュータ、タブレットコンピュータ、携帯電話機、スマートフォン、パーソナルデジタルアシスタント（ＰＤＡ）、ウエアラブル装置、又は他のクライアント装置のようなクライアント装置を有しても良く、又はそれに結合されても良い。
【００１８】
ＩＣＮ１００は、１又は複数の下位ネットワーク１０８ａ、１０８ｂ（概して「下位ネットワーク１０８」又は「複数の下位ネットワーク１０８」）を有しても良い。各下位ネットワークは、１つの意志決定ノード１０１を有しても良い。下位ネットワーク１０８の中で意志決定ノード１０１の下流にあるノードであって、該ノードからコンテンツの要求が生じるノードは、本願明細書では「要求ノード」と呼ばれる。Ｉｎｔｅｒｅｓｔパケットが下位ネットワーク１０８の中の要求ノード１０３から生じると、下位ネットワーク１０８の中の中間ノード１０２からの対応するＤａｔａパケットの配信によりＩｎｔｅｒｅｓｔパケットが既に満たされている場合でも、Ｉｎｔｅｒｅｓｔパケットは、下位ネットワーク１０８の意志決定ノード１０１へルーティングされ、意志決定ノード１０１により受信され得る。Ｉｎｔｅｒｅｓｔパケットは、要求されたコンテンツ名、要求ノード１０３、及びＩｎｔｅｒｅｓｔパケットを意志決定ノード１０１へ転送する任意のノードを識別し得る。したがって、意志決定ノード１０１は、下位ネットワーク１０８のデータコレクタとして動作し、コンテンツが下位ネットワーク１０８の中の各ノードにより何回アクセスされたかをアクセス履歴テーブルの中で追跡し続ける。意志決定ノード１０１は、下位ネットワーク１０８の中の各ノードにおけるコンテンツの人気を決定するために、アクセス履歴テーブルを用いても良い。
【００１９】
意志決定ノード１０１は、下位ネットワーク１０８の中の各ノードにおける下位ネットワーク１０８の各コンテンツの人気に基づくパラメータを含む線形計画最適化を実行して、下位ネットワーク１０８の中のデータダウンロードの合計コストを最小化するために、下位ネットワーク１０８の１又は複数のノードにおいて記憶サイズをどのように割り当てるか、及び下位ネットワーク１０８の中のコンテンツの各々をどこに配置するか、を決定しても良い。線形計画最適化の解に基づき、意志決定ノード１０１は、コンテンツを格納すべき下位ネットワーク１０８の中の１又は複数のノードに知らせるために、該コンテンツのＤａｔａパケットの中の１又は複数のキャッシュフラグを設定しても良い。したがって、下位ネットワーク１０８の中で要求されたコンテンツは、ネットワーク内に配置されても良く、記憶サイズは、下位ネットワーク１０８の中の要求ノード１０１へのよりコスト効率の良いコンテンツ配信を提供するために割り当てられても良い。
【００２０】
前述の実装のために、ＩＣＮ１００の要求ノード１０３、ピアノード１０６、中間ノード１０２、及び意志決定ノード１０１の各々は、ＰＩＴ（pending  interest  table、未解決Ｉｎｔｅｒｅｓｔテーブル）、ＦＩＢ（forwarding  information  base、情報転送ベース）、及びＣＣ（content  cache、コンテンツキャッシュ）を備えるルータを有し、転送、配信、及びＩｎｔｅｒｅｓｔパケットの記録を含む記憶タスクを実行しても良い。図２Ａは、本願明細書に記載の少なくとも１つの実装に従って配置される標準的なＩＣＮの３つの例示的なデータ構造の概略図である。３つのデータ構造は、ＣＣ２００、ＰＩＴ２０１、及びＦＩＢ２０２を有する。
【００２１】
ＣＣ２００は、Ｉｎｔｅｒｅｓｔパケットを対応するＤａｔａパケットに関連付けても良い。例えば、ＣＣ２００は、各々の受信したＩｎｔｅｒｅｓｔパケットを示す「Ｎａｍｅ（名称）」欄と、ルータにおいて受信されキャッシュされ得る対応するＤａｔａパケットを示す「Ｄａｔａ（データ）」欄と、を有しても良い。
【００２２】
ＰＩＴ２０１は、各々のＩｎｔｅｒｅｓｔパケットを１又は複数の要求側インタフェースに関連付けることにより、（対応する要求されたＤａｔａパケットが受信されるまで）供給され又は保留されている各々の受信したＩｎｔｅｒｅｓｔパケットを記録し追跡しても良い。要求側インタフェースは、例えば、要求ノード１０３、１又は複数の中間ノード１０２、及び／又は意志決定ノード１０１のうちの１又は複数に、固定（有線）リンク、無線リンク、ネットワーク、インターネット、及び／又は他のコンポーネント若しくはシステムを介して結合されても良い。例えば、ＰＩＴ２０１は、各々のＩｎｔｅｒｅｓｔパケットを示す「プレフィックス」欄と、Ｉｎｔｅｒｅｓｔパケットの１又は複数の要求側インタフェース、例えば図２Ａの「要求側フェース０」を示す「Requesting  Face（要求側フェース）」欄と、を有しても良い。
【００２３】
ＦＩＢ２０２は、各々のＩｎｔｅｒｅｓｔパケットを、Ｉｎｔｅｒｅｓｔパケットが転送され得る対応する転送インタフェースに関連付けても良い。転送インタフェースは、１又は複数の中間ノード１０２、１又は複数のピアノード１０６、１又は複数の上流ノード１０５、及び／又は意志決定ノード１０１に、固定（有線）リンク、無線リンク、ネットワーク、インターネット、及び／又は他のコンポーネント若しくはシステムを介して結合されても良い。例えば、ＦＩＢ２０２は、各々のＩｎｔｅｒｅｓｔパケットを示す「Ｎａｍｅ（名称）」欄と、対応する転送インタフェースを示す「Face（フェース）」欄と、を有しても良い。要求側インタフェースは、本願明細書では、「第１のインタフェース」と称されても良く、転送インタフェースは、本願明細書では、「第２のインタフェース」と称されても良い。ＣＣ２００、ＰＩＴ２０１、及びＦＩＢ２０２は、図４に関して更に詳細に説明される。
【００２４】
ＣＣ２００、ＰＩＴ２０１、及びＦＩＢ２０２に加えて、ＩＣＮ１００の意志決定ノード１０１は、アクセス履歴テーブル、解テーブル、及びコンテンツカタログを備えるルータを有しても良い。アクセス履歴テーブルは、下位ネットワーク１０８の中の各ノードにより、コンテンツが何回アクセスされたかを追跡するために用いられても良い。解テーブルは、線形計画最適化を実行することから得られたコンテンツ配置解を有しても良く、下位ネットワーク１０８の中のどこにコンテンツが格納されたかを追跡するために用いられても良い。図２Ｂは、本願明細書に記載の少なくとも１つの実装に従って配置される例示的な解テーブル２０３及び例示的なアクセス履歴テーブル２０４の概略図である。下位ネットワーク１０８の中の１又は複数のルータの名称は、「Router  ID（ルータＩＤ）」欄の下で、解テーブル２０３の１つの行に入力されても良い。線形計画最適化から得られた、ルータの各々においてキャッシュされるべきコンテンツのリストは、「Content  Placement  Solution（コンテンツ配置解）」欄の下で、解テーブル２０３の同じ行に入力されても良い。解テーブル２０３は、下位ネットワークの中のルータの各々のルータＩＤを有しても良い。アクセス履歴テーブル２０４は、下位ネットワーク１０８の中の１又は複数のルータの名称を示す「Client（クライアント）（Router  ID）」欄と、１又は複数のルータの各々が要求したコンテンツを示す「Access  History（アクセス履歴）」欄と、を有しても良い。
【００２５】
図３Ａは、本願明細書に記載の少なくとも１つの実装に従って配置される、ツリートポロジを有する下位ネットワーク３１９の２つのレベルを示す、例示的なＩＣＮ３０６の簡略概略図である。図３Ａに示すように、下位ネットワーク３１９の第２のレベルは、図１の意志決定ノード１０１を含み又はそれに対応し得る意志決定ノード３０２（「コア」）を含んでも良い。
【００２６】
下位ネットワーク３１９の第１のレベルは、図１の中間ノード１０２を含み又はそれに対応し得る１又は複数の中間ノード３００（概して「中間ノード３００」又は「複数の中間ノード３００」と表す）を有しても良い。各中間ノード３００は、要求ノード（図示しない）と意志決定ノード３０２との間に配置されても良い。要求ノード（図示しない）は、図１の要求ノード１０３を含み又はそれに対応しても良い。下位ネットワーク３１９の第１のレベルは、要求ノード（図示しない）と意志決定ノード３０２との間の経路の外側に配置される１又は複数のピアノード３０１（概して「ピアノード３０１」又は「複数のピアノード３０１」）も有しても良い。ピアノード３０１は、図１のピアノード１０６を含み又はそれに対応しても良い。
【００２７】
ＩＣＮ３０６は、サーバ３０３を更に有しても良い。意志決定ノード３０２は、線形計画最適化を実行しても良い。線形計画最適化の一例は、図３Ｂ〜３Ｄに関して更に詳細に記載される。図２Ａ〜３Ａを合わせて参照して、上述の及び他の実装では、中間ノード３００が要求ノード（図示しない）からＩｎｔｅｒｅｓｔパケットを受信し、そして対応するＤａｔａパケットが中間ノード３００及び意志決定ノード３０２のＣＣ２００に無いが、ピアノード３０１のＣＣ２００に存在する場合、Ｉｎｔｅｒｅｓｔパケットは、中間ノード３００から意志決定ノード３０２へ、次にピアノード３２０１へ、経路３０４で転送されても良い。意志決定ノードからピアノードへのＩｎｔｅｒｅｓｔパケットの転送処理は、「最近複製探索（nearest  replica  search）」と呼ばれる。
【００２８】
中間ノード３００が要求ノード（図示しない）からＩｎｔｅｒｅｓｔパケットを受信するが、対応するＤａｔａパケットが中間ノード３００のＣＣ２００及び意志決定ノード３０２のＣＣ２００に無い場合、Ｉｎｔｅｒｅｓｔパケットは、中間ノード３００から意志決定ノード３０２へサーバ３０３に向かって経路３０５で転送されても良い。要求ノードから意志決定ノードへの経路に沿ったＩｎｔｅｒｅｓｔパケットの転送処理は、「経路探索」と呼ばれる。意志決定ノード３０２により実行される線形計画最適化は、経路探索と最近複製探索の両方と互換性がある。
【００２９】
図３Ｂ〜３Ｃは、本願明細書に記載の少なくとも１つの実装に従って配置される、意志決定ノードにより実行され得る例示的な線形プログラム最適化を示す。図３Ｄは、本願明細書に記載の少なくとも１つの実装に従って配置される、図３Ｂ〜３Ｃの線形計画最適化で用いられる表記法の表である。図３Ｄの中で（及び図３Ｂ〜３Ｃで使用される種々の表記により本質的に）示される「Ｎｏｄｅ  ｉ」は、既に説明したように１又は複数の中間ノード３００及び／又は１又は複数のピアノード３０１を含み得る図３Ａの第１のレベルのノードを含み又はそれに対応しても良い。図３Ｂ〜３Ｄの線形計画最適化は、図３Ａの状況で説明される。
【００３０】
図３Ｂに示すように、図３Ｂ〜３Ｃにおける線形計画最適化の目的は、下位ネットワーク３１９の中の合計ダウンロードコストを採用かすることであっても良い。下位ネットワーク３１９は、図１の下位ネットワーク１０８を含み又はそれに対応しても良い。さらに、図３Ｂ〜３Ｃの線形計画最適化は、合計記憶容量及びリンク容量が限られるとき、有用であり得る。図３Ｂで、第１のレベルのノードｉは、１〜Ｒの範囲であっても良く、下位ネットワーク３１９の中で要求されるコンテンツｊは、１〜Ｍの範囲であっても良い。
【００３１】
ノードｉにおけるコンテンツｊの人気は、パラメータαｉｊにより表され、ノードｉにおけるコンテンツｊのランクに基づいても良い。コンテンツｊのランクがノードｉにおいて上昇するにつれ、αｉｊも増大する。ノードｉにおけるコンテンツｊのランクは、ノードｉにおける他のコンテンツと比較したコンテンツｊに対する要求に従って決定されても良い。ノードｉにおけるコンテンツｊに対する要求は、下位ネットワーク３１９の中の各ノードによりコンテンツｊが何回要求されたかをアクセス履歴テーブルの中で意志決定ノードが追跡をしてからの過去の履歴から推定されても良い。要求は、アクセス履歴テーブルを用いて、コンテンツｊがノードｉにおいて過去に要求された回数を計数することにより、推定されても良い。代替で又は追加で、要求は、ＳＶＤ（Singular  Value  Decomposition）を含む協調フィルタリング技術を用いて、コンテンツｊがノードｉにおいて将来に要求される回数又は潜在的要求を推定することにより推定されても良い。
【００３２】
アクセス履歴テーブル及び要求値は、任意の新しいアクセス要求によりオンラインで更新されても良い。しかし、ノードｉにおけるコンテンツのランクは、例えば、日毎に更新されても良い。図３Ｂ〜３Ｃの線形計画最適化は、オフラインで実行されても良い。幾つかの実装では、図３Ｂ〜３Ｃの線形計画最適化は、ＩＣＮ３０６が設定されるとき下位ネットワーク３１９のノードにおける記憶サイズ割り当てを決定するために、１回オフラインで実行されても良い。アクセス履歴テーブル及び要求値が変化すると、人気パラメータαｉｊは更新されるが、線形計画最適化に対する同じ解は、新しいコンテンツランクであっても使用されても良い。線形計画最適化から得た記憶サイズ割り当ては、比較的静的であり、下位ネットワーク３１９の各ノードにおける記憶サイズを含むネットワーク設計をオフラインで実装できるようにし得る。
【００３３】
図３Ｂのコンポーネントは、要求ノードと意志決定ノード３０２との間の経路に置かれた中間ノード３００からコンテンツｊをダウンロードするコストを表し得る。コンポーネント３０８は、意志決定ノード３０２からコンテンツｊをダウンロードするコストを表し得る。コンポーネント３０９は、ピアノード３０１からコンテンツｊをダウンロードするコストを表し得る。コンポーネント３１０は、サーバ３０３からコンテンツｊをダウンロードするコストを表し得る。
【００３４】
意志決定ノード３０２により実行される線形計画最適化は、１又は複数の制約を有しても良い。例えば、図３Ｃの制約３１１に従って、種々の可能性が０〜１を含む範囲内の値に抑制される。図３Ｃの制約３１２に従って、可能性のうちの幾つかの間の関係が抑制される。図３Ｄの制約３１３及び３１４は、コンテンツｊが中間ノード３００のＣＣ及び意志決定ノード３０２のＣＣに存在しないとき、コンテンツｊが１つのピアノード３０１からアクセスされることを保証しても良い。図３Ｃの制約３１５は、下位ネットワーク３１９の中のノードのうち１又は複数における記憶割り当てを指示しても良い。図３Ｃの制約３１６は、ピアノード３０１と意志決定ノード３０２との間のアップリンクにおける輻輳を回避するよう設計されても良い。図３Ｄの制約３１７は、意志決定ノード３０２と中間ノード３００との間のダウンリンクにおける輻輳を回避するよう設計されても良い。図３Ｄの制約３１８は、サーバ３０３と意志決定ノード３０２との間のダウンリンクにおける輻輳を回避するよう設計されても良い。
【００３５】
線形計画最適化は、下位ネットワーク３１９の中の１又は複数のノードにおける記憶サイズ割り当てを決定するために、及び下位ネットワーク３１９の中の合計データダウンロードコストを最小化するよう下位ネットワーク３１９の中でどこにコンテンツを格納するかを決定するために、意志決定ノード２０２により実行されても良い。線形計画最適化は、内点又片方向（Interior  Point  or  Simplex）方法を用いて実行されても良い。
【００３６】
線形計画最適化の実行は、下位ネットワーク３１９の中のノードにおけるコンテンツの確率（probability）、例えばノードｉにおけるコンテンツｊの確率ｐｉｊ、を示しても良い。意志決定ノード３０２は、線形計画最適化を用いて決定されたノードにおけるコンテンツの確率に従って１又は複数のキャッシュフラグを設定しても良い。例えば、意志決定ノード３０２は、下位ネットワーク３１９の中のノードｉにおけるコンテンツｊの確率ｐｉｊに従って１又は複数のキャッシュフラグを設定しても良い。ノードにおけるコンテンツの確率が分数である場合、意志決定ノード３０２は、下位ネットワーク３１９の１又は複数のノードにデータの１又は複数のチャンクをキャッシュすることを指示するために、１又は複数のキャッシュフラグを設定しても良い。上述の及び他の態様は、以下に更に詳細に議論される。
【００３７】
図４は、本願明細書に記載の少なくとも１つの実装に従って配置される例示的なＩＣＮルータシステム（以後、「システム４００」）を説明するブロック図である。システム４００は、本願明細書に記載の少なくとも１つの実装に従って、ノードの下位ネットワークの配信経路に沿ったコンテンツ配置のために構成されても良く、コンピューティング装置又はシステムとして実装されても良い。
【００３８】
システム４００は、図１の要求ノード１０３、中間ノード１０２、ピアノード１０６、及び／又は意志決定ノード１０１のうちの任意の１つを有し又はそれに対応しても良い。システム４００は、図３の中間ノード３００、ピアノード３０１、及び／又は意志決定ノード３０２のうちの任意の１つを有し又はそれに対応しても良い。例えば、要求ノード１０３、中間ノード１０２、ピアノード１０６、意志決定ノード１０１、中間ノード３００、ピアノード３０１、及び／又は意志決定ノード３０２のうちの１又は複数は、システム４００として実装されても良い。システム４００は、本願明細書に記載のような、ルータ又はルーティング装置又はルーティングの可能な他の装置として実装されても良い。
【００３９】
システム４００は、幾つかの例に応じて、キャッシュマネジャアプリケーション４０１、プロセッサ装置４０７、第１のインタフェース４１０、第２のインタフェース４１３、記憶装置４１５、及びメモリ４０８を有しても良い。システム４００のコンポーネントは、バス４１７により通信可能に結合されても良い。バス４１７は、メモリバス、記憶装置インタフェースバス、バス／インタフェース制御部、インタフェースバス、等、又はそれらの任意の組み合わせを含み得るが、これらに限定されない。
【００４０】
プロセッサ装置４０７は、本願明細書に記載の動作を実行する又はその性能を制御するためのＡＬＵ（arithmetic  logic  unit）、マイクロプロセッサ、汎用制御部、又は何らかの他のプロセッサアレイを有する。プロセッサ装置４０７は、データ信号を処理し、ＣＩＳＣ（complex  instruction  set  computer）アーキテクチャ、ＲＩＳＣ（reduced  instruction  set  computer）アーキテクチャ、又は命令セットの組合せを実施するアーキテクチャを含む種々のコンピューティングアーキテクチャを有しても良い。図４は単一プロセッサ装置４０７を有するが、複数のプロセッサ装置が含まれても良い。他のプロセッサ、オペレーティングシステム、及び物理構成も可能であり得る。
【００４１】
メモリ４０８は、プロセッサ装置４０７により実行され及び／又はそれにより操作され得る命令及び／又はデータを格納する。命令又はデータは、本願明細書に記載の動作を実行する又はその性能を制御するために、プロセッサ装置４０７により実行され得るプログラミングコードを有しても良い。命令又はデータは、図２ＡのＣＣ２００、ＰＩＴ２０１、及び／又はＦＩＢ２０２、及び／又は図２Ｂのアクセス履歴テーブル２０４及び／又は解テーブル２０３を有しても良い。命令又はデータは、システム４００が意志決定ノードを有するとき、アクセス履歴テーブル２０４及び／又は解テーブル２０３を有しても良い。メモリ４０８は、ＤＲＡＭ（dynamic  random  access  memory）素子、ＳＲＡＭ（static  random  access  memory）素子、フラッシュメモリ又は何らかの他のメモリ素子を有しても良い。幾つかの実装では、メモリ４０８は、不揮発性メモリ、又はハードディスクドライブ、フロッピディスクドライブ、ＣＤ−ＲＯＭ装置、ＤＶＤ−ＲＯＭ装置、ＤＶＤ−ＲＡＭ装置、ＤＶＤ−ＲＷ装置、フラッシュメモリ装置又は従来知られているより永久的に情報を格納する特定の他の大容量記憶装置を含む同様の永久記憶装置及び媒体も有しても良い。
【００４２】
第１のインタフェース４１０は、図２Ａに関して説明したように、少なくとも１つの要求ノード、中間ノード、及び／又は意志決定ノードからＩｎｔｅｒｅｓｔパケットを受信し及びそれらへＤａｔａパケットを送信するよう構成される。例えば、第１のインタフェースは、図１の要求ノード１０３、中間ノード１０２、及び／又は意志決定ノード１０１、及び／又は図３Ａの中間ノード３００及び／又は意志決定ノード３０２からＩｎｔｅｒｅｓｔパケットを受信し、それらへＤａｔａパケットを送信するよう構成されても良い。
【００４３】
第２のインタフェース４１３は、図２Ａに関して説明したように、少なくとも１つの中間ノード、ピアノード、及び／又は上流ノードから意志決定ノードへＩｎｔｅｒｅｓｔパケットを転送し及びそれらからＤａｔａパケットを受信するよう構成される。例えば、第２のインタフェース４１３は、図１の中間ノード１０２、ピアノード１０６、及び／又は上流ノード１０５、及び／又は図３Ａの中間ノード３００及び／又はピアノード３０１へＩｎｔｅｒｅｓｔパケットを転送し、それらからＤａｔａパケットを受信するよう構成されても良い。
【００４４】
幾つかの実装では、第１及び第２のインタフェース４１０、４１３は、図１のＩＣＮ１００及び／又は図３ＡのＩＣＮ３０６の中の他のノード又は別の通信チャネルへの直接物理接続のためのポートを有する。例えば、第１及び第２のインタフェース４１０、４１３は、ＵＳＢ（universal  serial  bus）ポート、ＳＤ（secure  digital）ポート、ＣＡＴ−５（category  ５）ポート、又は図１Ａのコンポーネント１０１〜１０６のうちの少なくとも１つ及び／又は図３Ａのコンポーネント３００〜３０３のうちの少なくとも１つとの有線通信のための類似のポートを有しても良い。幾つかの実装では、第１及び第２のインタフェース４１０、４１３は、図１のコンポーネント１０１〜１０６及び／又は図３Ａの３００〜３０３のうちの少なくとも１つとデータを交換する無線トランシーバ、又はＩＥＥＥ８０２．１１、ＩＥＥＥ８０２．１６、Ｂｌｕｅｔｏｏｔｈ（登録商標）、若しくは別の適切な無線通信方法を含む１又は複数の無線通信方法を用いる他の通信チャネルを有する。
【００４５】
幾つかの実装では、第１及び第２のインタフェース４１０、４１３は、ＳＭＳ（short  messaging  service）、ＭＭＳ（multimedia  messaging  service）、ＨＴＴＰ（hypertext  transfer  protocol）、直接データ接続、ＷＡＰ（wireless  application  protocol）、電子メール又は他の適切な種類の電子通信を介することを含むセルラネットワークでデータを送信及び受信するセルラ通信トランシーバを有する。幾つかの実装では、第１及び第２のインタフェース４１０、４１３は、有線ポート及び無線トランシーバを有しても良い。第１及び第２のインタフェース４１０、４１３は、ＴＣＰ／ＩＰ（transmission  control  protocol/internet  protocol）、ＨＴＴＰ、ＨＴＴＰセキュア（ＨＴＴＰＳ）、及びＳＭＴＰ（simple  mail  transfer  protocol）等を含む標準ネットワークプロトコルを用いてファイル又はメディアオブジェクトの配信のために図１及び３ＡのＩＣＮ１００及び／又は３０６又はそのコンポーネントへの他の接続を提供しても良い。
【００４６】
記憶装置４１５は、本願明細書に記載の機能を提供するために命令及び／又はデータを格納する非一時的記憶媒体を有しても良い。記憶装置４１５は、ＤＲＡＭ（dynamic  random  access  memory）素子、ＳＲＡＭ（static  random  access  memory）素子、フラッシュメモリ又は何らかの他のメモリ素子を有しても良い。幾つかの実装では、記憶装置４１５は、不揮発性メモリ、又はハードディスクドライブ、フロッピディスクドライブ、ＣＤ−ＲＯＭ装置、ＤＶＤ−ＲＯＭ装置、ＤＶＤ−ＲＡＭ装置、ＤＶＤ−ＲＷ装置、フラッシュメモリ装置又は従来知られているより永久的に情報を格納する特定の他の大容量記憶装置を含む同様の永久記憶装置及び媒体も有しても良い。記憶装置４１５は、メモリ４０８に一時的に格納される又はロードされる命令及び／又はデータを格納しても良い。
【００４７】
図４に示すように、キャッシュマネジャアプリケーション４０１は、コンテンツキャッシュモジュール４０３（以後「ＣＣモジュール４０３」）、未解決Ｉｎｔｅｒｅｓｔテーブルモジュール４０５（以後「ＰＩＴ（pending  interest  table）モジュール４０５」）、転送情報ベースモジュール４０２（以後「ＦＩＢ（forwarding  information  base）モジュール４０２」）、意志決定モジュール４０４（以後「ＤＭ（decision  maker）モジュール４０４」）、及び通信モジュール４０６、本願明細書ではこれらを総称して「モジュール４０９」と表す、のうちの少なくとも１つを有しても良い。モジュール４０２〜４０６を含むキャッシュマネジャアプリケーション４０１は、通常、本願明細書に記載の機能及び動作を実行し又はその性能を制御するために、プロセッサ装置４０７により実行可能なプログラミングコード及び／又はコンピュータ可読命令を有するソフトウェアを含み得る。モジュール４０２〜４０６のうちの１又は複数を含むキャッシュマネジャアプリケーション４０１は、システム４００のコンポーネントのうちの１又は複数からデータを受信しても良く、及び／又は記憶装置４１５及びメモリ４０８のうちの一方又は両方にデータを格納しても良い。
【００４８】
ＣＣモジュール４０３は、通常、本願明細書に更に詳細に記載するように、図１の中間ノード１０２、ピアノード１０６及び／又は意志決定ノード１０１、及び／又は図３Ａの中間ノード３００及び／又はピアノード３０１のような中間ノード、ピアノード、及び／又は意志決定ノードに格納され得る対応するＤａｔａパケットにＩｎｔｅｒｅｓｔパケットを関連付けるよう構成されても良い。この及び他の実装では、ＣＣモジュール４０３は、ＣＣ２００からデータを読み出し及び／又はそれにデータを書き込んでも良い。
【００４９】
ＰＩＴモジュール４０５は、ここで詳述するように、各々のＩｎｔｅｒｅｓｔパケットを１又は複数の受信インタフェースに関連付けることにより、（対応する要求されたＤａｔａパケットが受信されるまで）供給され又は保留されている各々の受信したＩｎｔｅｒｅｓｔパケットを記録し追跡するよう構成されても良い。上述の及び他の実装では、ＰＩＴモジュール４０５は、ＰＩＴ２０１からデータを読み出し及び／又はそれにデータを書き込んでも良い。
【００５０】
ここで詳述されるように、ＦＩＢモジュール４０２は、Ｉｎｔｅｒｅｓｔパケットが転送される１又は複数の対応するインタフェースに、Ｉｎｔｅｒｅｓｔパケットを関連付けるよう構成されても良い。ＦＩＢモジュール４１２は、ＦＩＢ２０２からデータを読み出し及び／又はそれにデータを書き込んでも良い。
【００５１】
システム４００が意志決定ノードを有するとき存在し得るＤＭモジュール４０４は、線形計画最適化を実行して、下位ネットワークの中の各ノードにおける下位ネットワークの各コンテンツの人気に基づき、下位ネットワークの中のデータダウンロードの合計コストを最小化するために、下位ネットワークの１又は複数のノードにおいて記憶サイズをどのように割り当てるか、及び下位ネットワークの中のコンテンツの各々をどこに配置するか、を決定するよう構成されても良い。線形計画最適化の解に基づき、ＤＭモジュール４０４は、コンテンツをキャッシュするよう下位ネットワークの中の１又は複数のノードに知らせるために、該コンテンツのＤａｔａパケットの中の１又は複数のキャッシュフラグを設定するよう構成されても良い。
【００５２】
通信モジュール４０６は、モジュール４０２〜４０５とシステム４００の他のコンポーネントとの間の通信を処理するルーチンを含むソフトウェアとして実装されても良い。キャッシュマネジャアプリケーション４０１が図１又は３Ａの意志決定ノード１０１又は３０２に実装されるとき、通信モジュール４０６は、インタフェースを介して、図１のコンポーネント１０２〜１０６及び／又は図３Ａの３００、３０１、３０３のうちの１又は複数へデータを送信し及びそれらからデータを受信する。幾つかの実装では、通信モジュール４０６は、モジュール４０２〜４０５のうちの１又は複数からデータを受信し、記憶装置４１５及びメモリ４０８のうちの１又は複数に該データを格納する。幾つかの実装では、通信モジュール４０６は、記憶装置４１５又はメモリ４０８からデータを読み出し、該データをモジュール４０２〜４０５のうちの１又は複数に送信する。
【００５３】
図５Ａ〜５Ｃは、本願明細書に記載の少なくとも１つの実装に従って配置される例示的なコンテンツ検索シナリオの概略図である。図５Ａ〜５Ｃは、意志決定ノード５０１、中間ノード５０２、要求ノード５０３、サーバ５０４、及び１又は複数のピアノード５０６を含むツリートポロジを有する下位ネットワークを示す。前述のコンポーネントは、他の図の中の同一名称のコンポーネントを含み又はそれに対応しても良い。図５Ａ〜５Ｃは、さらに、１又は複数のＩｎｔｅｒｅｓｔパケット５０７、Ｄａｔａパケット５０９、及びコンテンツ５１０を示す。コンテンツ５１０は、Ｄａｔａパケット５０９を有しても良い。図５Ａ〜５Ｃの議論では、ノード５０１〜５０３及び５０６の各々は図４のＩＣＮルータシステム４００に従って個々に実装されると仮定する。
【００５４】
図５Ａで、中間ノード５０２の通信モジュール４０６は、要求ノード５０３からＩｎｔｅｒｅｓｔパケットを受信しても良い。Ｉｎｔｅｒｅｓｔパケット５０７は、要求ノード５０３により要求されているコンテンツ５１０のコンテンツ名、及び意志決定ノード５０１へＩｎｔｅｒｅｓｔパケットを転送する任意のノードを識別しても良い。本実装及び他の実装では、中間ノード５０２のＣＣモジュール４０３は、コンテンツ５１０について中間ノード５０２のＣＣ２００を調べ、中間ノード５０２のＣＣ２００にコンテンツが格納されていることに応答して、中間ノード５０２の通信モジュール４０６は、コンテンツ５１０のＤａｔａパケット５０９を中間ノード５０２から要求ノード５０３へ転送しても良い。中間ノード５０２のＦＩＢモジュール４０２は、Ｉｎｔｅｒｅｓｔパケット５０７が既に満たされていることを示すために解決（satisfied）フラグをオンにされたＩｎｔｅｒｅｓｔパケット５０７を、意志決定ノード５０１へ転送しても良い。意志決定ノード５０１のＤＭモジュール４０４は、相応して、意志決定ノード５０１のアクセス履歴テーブル２０４を更新しても良い。
【００５５】
代替で、コンテンツ５１０が中間ノード５０２のＣＣ２００に存在しないことに応答して、図５Ｂ及び５Ｃに示すように、中間ノード５０２のＰＩＴモジュール４０５は、中間ノード５０２のＰＩＴ２０１にＩｎｔｅｒｅｓｔパケット５０７を記録しても良い。中間ノード５０２のＦＩＢモジュール４０２は、Ｉｎｔｅｒｅｓｔパケット５０７が未だ満たされていないことを示すためにＩｎｔｅｒｅｓｔパケット５０７の中の解決フラグをオフにして、Ｉｎｔｅｒｅｓｔパケット５０７を意志決定ノード５０１へ転送しても良い。そして、意志決定ノード５０１のＣＣモジュール４０３は、コンテンツ５１０について意志決定ノード５０１のＣＣ２００を調べても良い。
【００５６】
コンテンツ５１０が意志決定ノード５０１のＣＣ２００の中に存在することに応答して、意志決定ノード５０１の通信モジュール４０６は、コンテンツ５１０の１又は複数のＤａｔａパケットを、下流にある中間ノード５０２へ転送しても良い。次に、中間ノード５０２は、１又は複数のＤａｔａパケット５０９を要求ノード５０３へ転送しても良い。コンテンツ５１０が意志決定ノード５０１のＣＣ２００に存在しないことに応答して、図５Ｂ及び５Ｃに示すように、意志決定ノード５０１のＤＭモジュール４０４は、線形計画最適化を実行することにより得られた意志決定ノード５０１の解テーブル２０３及び／又はアクセス履歴テーブル２０４を調べることにより、コンテンツ５１０が、要求ノード５０２と意志決定ノード５０１との間の経路の外側にある下位ネットワークの中のピアノード５０６のうちの１つに格納されているかどうかを決定しても良い。
【００５７】
図５Ｂ及び５Ｃでは、コンテンツ５１０は、要求ノード５０３と意志決定ノード５０１との間の経路の外側にある下位ネットワークの中のピアノード５０６のうちの異なる１つに格納されているように示される。コンテンツ５１０が、要求ノード５０３と意志決定ノード５０１との間の経路の外側にある下位ネットワークの中のピアノード５０６のうちの対応する１つに格納されていることに応答して、意志決定ノード５０１のＤＭモジュール４０４は、ピアノード５０６のうちの対応する１つを選択しても良く、意志決定ノード５０１のＦＩＢモジュール４０２は、Ｉｎｔｅｒｅｓｔパケット５０７を、意志決定ノード５０１から対応するピアノード５０６へ転送しても良い。図５Ｂのような幾つかの例では、Ｉｎｔｅｒｅｓｔパケット５０７は、意志決定ノード５０１から対応するピアノード５０６へ、中間ノード５０２（又は複数の中間ノード）及び／又は他のピアノード５０６を通じて転送されても良い。コンテンツ５１０が、コンテンツ５１０を有しない中間ノード５０２（又は複数の中間ノード）のような１又は複数の介在ノード或いは他のピアノード５０６により意志決定ノード５０１から分離されているピアノード５０６のうちの対応する１つに格納されていると決定することに応答して、意志決定ノード５０１のＤＭモジュール４０４は、コンテンツ５１０を有するピアノード５０６への道順をＩｎｔｅｒｅｓｔパケット５０７に含めても良い。道順は、次ホップ情報を有しても良い。
【００５８】
コンテンツ５１０を有すると識別されたピアノード５０６がＩｎｔｅｒｅｓｔパケット５０７を受信した後、ピアノード５０６のＣＣモジュール４０３は、ピアノード５０６のＣＣ２００を調べても良い。コンテンツがピアノード５０６のＣＣ２００に格納されていることに応答して、ピアノード５０６の通信モジュール４０６は、ピアノード５０６のうちの１又は複数、意志決定ノード５０１、及び中間ノード５０２のような１又は複数の介在ノードを通じて、コンテンツ５１０の１又は複数のＤａｔａパケット５０９をピアノード５０６から要求ノード５０３へ送信しても良い。
【００５９】
コンテンツ５１０がピアノード５０６のうちの１より多いノードに格納されていると決定することに応答して、意志決定ノード５０１のＤＭモジュール４０４は、要求ノード５０３に最も近い又はそれから最小ホップ数の、又は線形計画最適化を実行して得たピア確率、例えば図３Ｂ〜３Ｃのｑｉｊｋに基づき、ピアノード５０６を選択しても良く、意志決定ノード５０１のＦＩＢモジュール４０２は、Ｉｎｔｅｒｅｓｔパケット５０７を選択したピアノード５０６へ転送しても良い。幾つかの例では、及び先に示したように、ピアノード５０６への道順は、Ｉｎｔｅｒｅｓｔパケット５０７に含まれ又はそれと共にあっても良い。
【００６０】
図５Ｃの例では、コンテンツ５１０を有するピアノード５０６の通信モジュール４０６は、コンテンツ５１０の１又は複数のＤａｔａパケット５０９を、意志決定ノード５０１を経由して要求ノード５０３へ送信しても良い。
【００６１】
意志決定ノード５０１のＤＭモジュール４０４は、下位ネットワークの中の各ノード５０１〜５０３における下位ネットワークの各コンテンツの人気に基づき、下位ネットワークの中のデータダウンロードの合計コストを最小化するために、下位ネットワークの１又は複数のノード５０１〜５０３において記憶サイズをどのように割り当てるか、及び下位ネットワークの中のコンテンツの各々をどこに配置するか、を決定するために、線形計画最適化を実行しても良く又は予め実行していても良い。線形計画最適化の解に基づき、意志決定ノード５０１のＤＭモジュール４０４は、コンテンツ５１０のＤａｔａパケット５０９を格納すべき下位ネットワークの中の１又は複数のノード５０１〜５０３、５０６に知らせるために、Ｄａｔａパケット５０９の中の１又は複数のキャッシュフラグを設定しても良い。
【００６２】
図６は、本願明細書に記載の少なくとも１つの実装に従って配置される、ＩＣＮの中のノードの下位ネットワークの配信経路に沿ったコンテンツ配置のための方法６１０の例示的なフロー図である。方法６１０は、全体的に又は部分的に、図１の１又は複数の意志決定ノード１０１、図２の意志決定ノード３０２、図５の意志決定ノード５０１、又は別の適切なネットワーク、ＩＣＮルータ、及び／又はシステムにより実装されても良い。方法６１０はブロック６００で開始し得る。
【００６３】
ブロック６００で、意志決定ノードは、要求ノードから生じたＩｎｔｅｒｅｓｔパケットを受信する。意志決定ノード及び要求ノードは、ＩＣＮの下位ネットワークの中に位置しても良く、ツリートポロジを有しても良い。Ｉｎｔｅｒｅｓｔパケットは、コンテンツ及び要求ノード、並びにＩｎｔｅｒｅｓｔパケットを意志決定ノードへ転送する任意のノードを識別し得る。意志決定ノードは、図１の意志決定ノード１０１、図２の意志決定ノード３０２、又は図５の意志決定ノード５０１を有しても良い。要求ノードは、図１の要求ノード１０３又は図５の要求ノード５０３を有しても良い。ブロック６００の次にブロック６０１が続いても良い。
【００６４】
ブロック６０１で、意志決定ノードは、図２Ｂ及び４のアクセス履歴テーブル２０４を有し得る自身のアクセス履歴テーブルを更新しても良い。ブロック６０１の次にブロック６０２が続いても良い。
【００６５】
ブロック６０２で、意志決定ノードは、要求ノードから生じたＩｎｔｅｒｅｓｔパケットの中にオンの解決フラグがあるかどうかを決定しても良い。ブロック６０２の次に、解決フラグがオンである場合（ブロック６０２で「Ｙｅｓ」）はブロック６０３が、解決フラグがオフの場合（ブロック６０２で「Ｎｏ」）はブロック６０４が、続いても良い。コンテンツが要求ノードと意志決定ノードとの間の経路にある１又は複数の中間ノードに格納されていることに応答して、解決フラグがオンにされても良い。コンテンツが要求ノードと意志決定ノードとの間の経路にある１又は複数の中間ノードの各々に存在しないことに応答して、解決フラグがオフにされても良い。
【００６６】
ブロック６０３で、Ｉｎｔｅｒｅｓｔパケットの中の解決フラグがオンであることに応答して、意志決定ノードは、次のＩｎｔｅｒｅｓｔパケットを受信するために待機し、及び／又は方法６１０はブロック６０３からブロック６００へ戻っても良い。
【００６７】
ブロック６０４で、Ｉｎｔｅｒｅｓｔパケットの中の解決フラグがオフであることに応答して、意志決定ノードは、コンテンツについて自身のＣＣを調べても良い。ブロック６０４の次に、コンテンツが意志決定ノードのＣＣに格納されている場合（ブロック６０４で「Ｙｅｓ」）はブロック６０５が、コンテンツが意志決定ノードのＣＣに存在しない場合（ブロック６０４で「Ｎｏ」）はブロック６０６が、続いても良い。意志決定ノードのＣＣは、図２Ａ及び４のＣＣ２００を有しても良い。
【００６８】
ブロック６０５で、コンテンツが意志決定ノードのＣＣの中に存在することに応答して、意志決定ノードは、コンテンツのＤａｔａパケットを要求ノードに返しても良い。
【００６９】
ブロック６０６で、コンテンツが意志決定ノードのＣＣに存在しないことに応答して、意志決定ノードは、線形計画最適化を実行することにより得た意志決定ノードの解テーブル及び／又はアクセス履歴テーブルを調べることにより、コンテンツが、要求ノードと意志決定ノードとの間の経路の外側にある下位ネットワークの中のピアノードに格納されているかどうかを決定しても良い。ピアノードは、図１のピアノード１０６、図３Ａのピアノード３０１、又は図５のピアノード５０６を有しても良い。解テーブルは、図２Ｂ及び４の解テーブル２０３を有しても良い。アクセス履歴テーブルは、図２Ｂ及び４のアクセス履歴テーブル２０４を有しても良い。線形計画最適化は、図３Ｂ〜３Ｄに示されそれらに関して説明された線形計画最適化を有しても良い。ブロック６０６の次に、ブロック６０７（ブロック６０６で「Ｎｏ」）又はブロック６０８（ブロック６０６で「Ｙｅｓ」）が続いても良い。
【００７０】
ブロック６０７で、意志決定ノードが、コンテンツは下位ネットワークのピアノードに存在しないと決定することに応答して、意志決定ノードは、上流ノード又はサーバへＩｎｔｅｒｅｓｔパケットを転送しても良い。サーバは、図１のサーバ１０４、図３Ａのサーバ３０３、又は図５のサーバ５０４を有しても良い。上流ノードは、図１の上流ノード１０５を有しても良い。意志決定ノードが、上流ノード又はサーバから対応するＤａｔａパケットを受信した後、意志決定ノードは、Ｄａｔａパケットの中の１又は複数のキャッシュフラグの各々を設定する確率を決定するために、線形計画最適化の解を調べても良い。確率は、図３Ｂ〜３Ｄに示すように、ノードｉの中のコンテンツｊの確率ｐｉｊを有しても良い。線形計画最適化は、下位ネットワークの中の各ノードにおける下位ネットワークの各コンテンツの人気、例えば図３Ｂ〜３Ｃのαｉｊに基づくパラメータを有しても良い。
【００７１】
ブロック６０８で、意志決定ノードが、コンテンツは下位ネットワークのピアノードに格納されていると決定することに応答して、意志決定ノードは、意志決定ノード又はピアノードからＩｎｔｅｒｅｓｔパケットを転送しても良い。１又は複数の中間ノード又は１又は複数のピアノードが、要求ノードと意志決定ノードとの間の経路の外側にあってコンテンツを有するピアノードと意志決定ノードとの間に位置することに応答して、意志決定ノードは、Ｉｎｔｅｒｅｓｔパケットの中に、コンテンツを有するピアノードへの道順を含めても良い。図５Ｃに示すように、幾つかの実施形態では、Ｄａｔａパケットは、ピアノードから要求ノードへ意志決定ノードを経由して送信されても良い。Ｄａｔａパケットが要求ノードへ意志決定ノードを経由して送信される場合、意志決定ノードは、線形計画最適化を用いて決定されたノードの中の要求されたコンテンツの確率に従って、キャッシュフラグを設定しても良い。例えば、線形計画最適化を用いて、ノードｉの中のコンテンツｊの確率であるｐｉｊが１であると決定された場合、意志決定ノードは、コンテンツｊを格納するようノードｉに指示するキャッシュフラグを設定しても良い。線形計画最適化を用いて、ノードｉの中のコンテンツｊの確率であるｐｉｊが０であると決定された場合、意志決定ノードはキャッシュフラグを設定しなくても良く、ノードｉはコンテンツｊを格納しない。
【００７２】
当業者は、この処理及び本願明細書に開始した他の処理及び方法において、その処理及び方法で実行される機能が異なる順序で実施されても良いことを理解するだろう。さらに、概略のステップ及び動作は単に例として提供され、幾つかのステップ及び動作は、開示の実装の本質から逸脱することなく、任意であり、より少ないステップ及び動作に組み合わされ、又は追加ステップ及び動作に拡張されても良い。
【００７３】
本願明細書に記載の実装は、コンピュータにより実行可能な命令又はデータ構造を伝える又は格納しているコンピュータ可読媒体を含み得る。このようなコンピュータ可読媒体は、汎用又は特定目的コンピュータによりアクセスできる利用可能な媒体であり得る。例として且つ限定ではなく、このようなコンピュータ可読媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭ又は他の光ディスク記憶装置、磁気ディスク記憶装置又は他の磁気記憶装置を含む非一時的コンピュータ可読記憶媒体、又はコンピュータにより実行可能な命令若しくはデータ構造の形式で所望のプログラムコード手段を伝える若しくは格納するために用いられ汎用若しくは特定目的コンピュータによりアクセス可能な他の媒体を有し得る。上述の組合せも、コンピュータ可読媒体の範囲に包含され得る。
【００７４】
コンピュータにより実行可能な命令は、例えば、汎用コンピュータ、特定目的コンピュータ又は特定目的処理装置に特定の機能又は機能グループを実行させる命令及びデータを有する。本発明の主題は構造的特徴及び／又は方法論的動作に特有の言葉で記載されたが、本発明の主題は、特許請求の範囲に定められる上述の特定の特徴又は動作に限定されないことが理解されるべきである。むしろ、上述の特定の特徴及び動作は、特許請求の範囲の実施の例示的形態として開示されたものである。
【００７５】
本願明細書で用いられるように、用語「モジュール」又は「コンポーネント」は、コンピューティングシステムで実行されるソフトウェアオブジェクト又はルーチンを表し得る。本願明細書に記載されたのと異なるコンポーネント、モジュール、エンジン及びサービスは、（例えば、別個のスレッドとして）コンピューティングシステムで実行されるオブジェクト又は処理として実施されても良い。本願明細書に記載されたシステム及び方法はソフトウェアで実施されることが望ましいが、ハードウェアによる実装又はソフトウェアとハードウェアの組合せも、可能であり想定される。この説明では、「コンピュータエンティティ」は、本願明細書で先に定められたようにコンピューティングシステム、又はコンピューティングシステムで実行されるモジュール若しくはモジュールの組合せであっても良い。
【００７６】
本願明細書に記載された全ての例及び条件文は、教育上の目的で、読者が本発明の原理及び発明者により考案された概念を理解するのを助け、技術を促進させるためであり、これらの特に記載された例及び条件に限定されないものと考えられるべきである。本発明の実装が詳細に記載されたが、種々の変更、置換及び修正が本発明の精神及び範囲から逸脱することなく行われうることが理解されるべきである。
【符号の説明】
【００７７】
１００  ＩＣＮ
１０１  意志決定ノード
１０２  中間ノード
１０３  要求ノード
１０４  サーバ
１０５  上流ノード
１０６  ピアノード
１０８  下位ネットワーク
２０３  解テーブル
２０４  アクセス履歴テーブル
３００  中間ノード
３０１  ピアノード
３０２  コア、意志決定ノード
３０３  サーバ
３０４、３０５  経路
３１９  下位ネットワーク
４０１  キャッシュマネジャアプリケーション
４０２  転送情報ベースモジュール
４０３  コンテンツキャッシュモジュール
４０４  意志決定モジュール
４０５  未解決Ｉｎｔｅｒｅｓｔテーブルモジュール
４０７  プロセッサ装置４０７
４０８  メモリ
４１０  第１のインタフェース
４１３  第２のインタフェース
４１５  記憶装置
５０１  意志決定ノード
５０２  中間ノード
５０６  ピアノード
５０７  Ｉｎｔｅｒｅｓｔパケット
５１０  コンテンツ
以上の実施形態に関し、更に以下の付記を開示する。
（付記１）  意志決定ノードにおいて、要求ノードから生じたＩｎｔｅｒｅｓｔパケットを受信するステップであって、前記意志決定ノード及び前記要求ノードは、ツリートポロジを有する下位ネットワークの複数のノードの一部であり、前記Ｉｎｔｅｒｅｓｔパケットはコンテンツ及び前記要求ノードを特定する、ステップと、
前記下位ネットワークの前記複数のノードのうち前記要求ノードと前記意志決定ノードとの間の経路に配置される１又は複数の中間ノードに前記コンテンツが格納されていることに応答して、
前記意志決定ノードにおいて、解決フラグがオンである前記Ｉｎｔｅｒｅｓｔパケットを受信し、
前記意志決定ノードにおいて、アクセス履歴テーブルを更新するステップと、
前記コンテンツが、前記下位ネットワークの前記複数のノードのうちの前記１又は複数の中間ノードの各々に存在しないことに応答して、
前記意志決定ノードにおいて、前記解決フラグがオフである前記Ｉｎｔｅｒｅｓｔパケットを受信し、
前記意志決定ノードにおいて、前記アクセス履歴テーブルを更新し、
前記コンテンツについて前記意志決定ノードを調べるステップと、
を有する方法。
（付記２）  前記コンテンツが、前記１又は複数の中間ノード及び前記意志決定ノードに存在しないことに応答して、
前記コンテンツは、前記下位ネットワークの前記複数のノードのうちのピアノードに格納されていると判断するステップであって、前記ピアノードは、前記要求ノードと前記意志決定ノードとの間の前記経路の外側にある、ステップと、
前記意志決定ノードから前記ピアノードへ前記Ｉｎｔｅｒｅｓｔパケットを転送するステップと、
を更に有する付記１に記載の方法。
（付記３）  １又は複数の中間ノード及び／又は１又は複数のピアノードが、前記意志決定ノードと前記コンテンツを有する前記ピアノードとの間に位置することに応答して、前記意志決定ノードが、前記Ｉｎｔｅｒｅｓｔパケットの中に、前記コンテンツを有する前記ピアノードへの道順を含めるステップであって、前記１又は複数のピアノードは、前記要求ノードと前記意志決定ノードとの間の前記経路の外側にある、ステップ、を更に有する付記２に記載の方法。
（付記４）  前記コンテンツは前記ピアノードに格納されていると判断するステップは、線形計画最適化を実行して得られた解を調べるステップを有する、付記２に記載の方法。
（付記５）  前記線形計画最適化は、前記アクセス履歴テーブルにより決定される、前記下位ネットワークの各ノードにおける前記下位ネットワークの各コンテンツの人気に基づくパラメータを有し、前記線形計画最適化を実行するステップは、前記コンテンツのＤａｔａパケットの中の１又は複数のキャッシュフラグの各々を設定する確率を決定するステップを有する、付記４に記載の方法。
（付記６）  前記意志決定ノードにおける前記コンテンツのＤａｔａパケットの受信に応答して、前記要求ノードに、前記１又は複数の中間ノードのうちの少なくとも１つに、又はそれらの両者に前記コンテンツを格納するよう指示するために、前記Ｄａｔａパケットの中の１又は複数のキャッシュフラグを設定するステップ、を更に有する付記１に記載の方法。
（付記７）  前記１又は複数のキャッシュフラグを設定するステップの前に、前記１又は複数のキャッシュフラグの各々を設定する確率を決定するために線形計画最適化を実行するステップを更に有する、付記６に記載の方法。
（付記８）  前記線形計画最適化は、前記アクセス履歴テーブルにより決定される、前記下位ネットワークの各ノードにおける前記下位ネットワークの各コンテンツの人気に基づくパラメータを有する、付記７に記載の方法。
（付記９）  前記線形計画最適化を実行するステップは、前記下位ネットワークの前記複数のノードのうちの１又は複数のノードにおける記憶サイズ割り当てを決定するステップを有する、付記８に記載の方法。
（付記１０）  ツリートポロジを有するネットワークの複数のノードを有し、前記複数のノードは、意志決定ノード、要求ノード、及び１又は複数の中間ノードを有し、前記意志決定ノードは、
前記要求ノードから生じたＩｎｔｅｒｅｓｔパケットを受信し、前記Ｉｎｔｅｒｅｓｔパケットはコンテンツ及び前記要求ノードを特定し、
前記要求ノードと前記意志決定ノードとの間の経路に配置される前記１又は複数の中間ノードに前記コンテンツが格納されていることに応答して、
解決フラグがオンである前記Ｉｎｔｅｒｅｓｔパケットを受信し、
前記意志決定ノードにあるアクセス履歴テーブルを更新し、
前記コンテンツが、前記１又は複数の中間ノードの各々に存在しないことに応答して、
前記解決フラグがオフである前記Ｉｎｔｅｒｅｓｔパケットを受信し、
前記意志決定ノードにある前記アクセス履歴テーブルを更新し、
前記コンテンツについて前記意志決定ノードを調べる、
よう構成される、システム。
（付記１１）  前記コンテンツが、前記１又は複数の中間ノード及び前記意志決定ノードに存在しないことに応答して、前記意志決定ノードは、
前記コンテンツは、前記要求ノードと前記意志決定ノードとの間の前記経路の外側にある前記ネットワークの前記複数のノードのうちのピアノードに格納されていると判断し、
前記意志決定ノードから前記ピアノードへ前記Ｉｎｔｅｒｅｓｔパケットを転送する、
よう更に構成される、付記１０に記載のシステム。
（付記１２）  前記意志決定ノードは、１又は複数の中間ノード及び／又は１又は複数のピアノードが、前記意志決定ノードと前記コンテンツを有する前記ピアノードとの間に位置することに応答して、前記Ｉｎｔｅｒｅｓｔパケットの中に、前記コンテンツを有する前記ピアノードへの道順を含め、前記１又は複数のピアノードは、前記要求ノードと前記意志決定ノードとの間の前記経路の外側にある、よう更に構成される、付記１１に記載のシステム。
（付記１３）  前記意志決定ノードは、
線形計画最適化を実行して得た解を調べるよう構成されることにより、前記コンテンツが前記ピアノードに格納されていると判断し、前記線形計画最適化は、前記アクセス履歴テーブルにより決定される、前記ネットワークの各ノードにおける前記ネットワークの各コンテンツの人気に基づくパラメータを有し、
前記コンテンツのＤａｔａパケットの中の１又は複数のキャッシュフラグの各々を設定する確率を決定する、
よう構成される、付記１１に記載のシステム。
（付記１４）  前記意志決定ノードは、前記意志決定ノードにおける前記コンテンツのＤａｔａパケットの受信に応答して、前記要求ノードに、前記１又は複数の中間ノードのうちの少なくとも１つに、又はそれらの両者に前記コンテンツを格納するよう指示するために、前記Ｄａｔａパケットの中の１又は複数のキャッシュフラグを設定するよう更に構成される、付記１０に記載のシステム。
（付記１５）  前記意志決定ノードは、前記１又は複数のキャッシュフラグを設定する前に、前記１又は複数のキャッシュフラグの各々を設定する確率を決定するために線形計画最適化を実行するよう更に構成され、
前記線形計画最適化は、前記アクセス履歴テーブルにより決定される、前記ネットワークの各ノードにおける前記ネットワークの各コンテンツの人気に基づくパラメータを有し、
前記線形計画最適化の実行は、前記ネットワークの前記複数のノードのうちの１又は複数のノードにおける記憶サイズ割り当ての決定を含む、
付記１４に記載のシステム。
（付記１６）  非一時的コンピュータ可読媒体であって、格納されたコンピュータ可読命令を有し、前記コンピュータ可読命令は、動作を実行し又は該動作の性能を制御するためにプロセッサにより実行可能であり、前記動作は、
意志決定ノードにおいて、要求ノードから生じたＩｎｔｅｒｅｓｔパケットを受信するステップであって、前記意志決定ノード及び前記要求ノードは、ツリートポロジを有する下位ネットワークの複数のノードの一部であり、前記Ｉｎｔｅｒｅｓｔパケットはコンテンツ及び前記要求ノードを特定する、ステップと、
前記下位ネットワークの前記複数のノードのうち前記要求ノードと前記意志決定ノードとの間の経路に配置される１又は複数の中間ノードに前記コンテンツが格納されていることに応答して、
前記意志決定ノードにおいて、解決フラグがオンである前記Ｉｎｔｅｒｅｓｔパケットを受信し、
前記意志決定ノードにおいて、アクセス履歴テーブルを更新するステップと、
前記コンテンツが、前記下位ネットワークの前記複数のノードのうちの前記中間ノードに存在しないことに応答して、
前記意志決定ノードにおいて、前記解決フラグがオフである前記Ｉｎｔｅｒｅｓｔパケットを受信し、
前記意志決定ノードにおいて、前記アクセス履歴テーブルを更新し、
前記コンテンツについて前記意志決定ノードを調べるステップと、
前記コンテンツが前記中間ノード及び前記意志決定ノードに存在しないことに応答して、
前記コンテンツは前記下位ネットワークの前記複数のノードのうちのピアノードに格納されていると判断し、前記ピアノードは、前記要求ノードと前記意志決定ノードとの間の前記経路の外側にあり、
前記意志決定ノードから前記ピアノードへ前記Ｉｎｔｅｒｅｓｔパケットを転送するステップと、
を有する、非一時的コンピュータ可読媒体。
（付記１７）  前記動作は、１又は複数の中間ノード又は１又は複数のピアノードが、前記意志決定ノードと前記コンテンツを有する前記ピアノードとの間に位置することに応答して、前記Ｉｎｔｅｒｅｓｔパケットの中に、前記コンテンツを有する前記ピアノードへの道順を含めるステップ、を更に有し、
前記１又は複数のピアノードは、前記要求ノードと前記意志決定ノードとの間の前記経路の外側にある、
付記１６に記載の非一時的コンピュータ可読媒体。
（付記１８）  前記コンテンツが前記ピアノードに格納されていると判断するステップは、線形計画最適化を実行して得た解を調べるステップを有し、前記線形計画最適化は、前記アクセス履歴テーブルにより決定される、前記下位ネットワークの各ノードにおける前記下位ネットワークの各コンテンツの人気に基づくパラメータを有し、
前記動作は、前記コンテンツのＤａｔａパケットの中の１又は複数のキャッシュフラグの各々を設定する確率を決定するステップを更に有する、
付記１６に記載の非一時的コンピュータ可読媒体。
（付記１９）  前記動作は、前記意志決定ノードにおける前記コンテンツのＤａｔａパケットの受信に応答して、前記要求ノードに、前記１又は複数の中間ノードのうちの少なくとも１つに、又はそれらの両者に前記コンテンツを格納するよう指示するために、前記Ｄａｔａパケットの中の１又は複数のキャッシュフラグを設定するステップ、を更に有する、付記１６に記載の非一時的コンピュータ可読媒体。
（付記２０）  前記動作は、前記１又は複数のキャッシュフラグを設定する前に、前記１又は複数のキャッシュフラグの各々を設定する確率を決定するために線形計画最適化を実行するステップ、を更に有し、
前記線形計画最適化は、前記アクセス履歴テーブルにより決定される、前記下位ネットワークの各ノードにおける前記下位ネットワークの各コンテンツの人気に基づくパラメータを有し、
前記線形計画最適化を実行するステップは、前記下位ネットワークの前記複数のノードのうちの１又は複数のノードにおける記憶サイズ割り当てを決定するステップを含む、
付記１９に記載の非一時的コンピュータ可読媒体。
【図１】
2016111703.tif 000003
【図２Ａ】
2016111703.tif 000004
【図２Ｂ】
2016111703.tif 000005
【図３Ａ】
2016111703.tif 000006
【図３Ｂ】
2016111703.tif 000007
【図３Ｃ】
2016111703.tif 000008
【図３Ｄ】
2016111703.tif 000009
【図４】
2016111703.tif 000010
【図５Ａ】
2016111703.tif 000011
【図５Ｂ】
2016111703.tif 000012
【図５Ｃ】
2016111703.tif 000013
【図６】
2016111703.tif 000014