(57)【要約】      （修正有）【課題】インターネットまたは任意の物理ネットワーク上にコンテンツ中心ネットワーク（ＣＣＮ）トポロジを設計して展開する。【解決手段】ＣＣＮ展開システムは、物理ネットワークトポロジを判定するために、Ｎ個のネットワークノードのコンピュータネットワークを分析する。システムはまた、コンテンツ中心ネットワーク（ＣＣＮ）をオーバーレイするために物理ネットワークのネットワークノードの数ｋを判定する。次に、システムは、ＣＣＮオーバーレイネットワークについての最適な性能メトリックを実現する接続性の平均レベル及び接続性レベル分布を判定する。システムは、接続性の平均レベルを満たし且つ接続性レベル分布を満たすｋ個のネットワークノードのネットワークトポロジを生成する。【選択図】なし【特許請求の範囲】
【請求項１】
コンピュータ実装方法において、
コンピューティングデバイスにより、コンテンツ中心ネットワーキング（ＣＣＮ）ネットワークについてのネットワークノードの数ｋを判定することと、
前記ＣＣＮネットワークについての最適な性能メトリックを実現する接続性の平均レベル及び接続性レベル分布を判定することと、
前記接続性の平均レベルを満たし且つ前記接続性レベル分布を満たすｋ個のネットワークノードのネットワークトポロジを生成することと、
物理コンピュータネットワークのノードに対して、前記生成されたネットワークトポロジのｋ個のノードをマッピングすることとを備える方法。
【請求項２】
前記接続性レベル分布を判定することが、
１つ以上の分布関数にわたって反復し、対応する分布関数に基づいて前記接続性の平均レベルを満たすｋ個のネットワークノードのネットワークトポロジを生成することと、
各ネットワークトポロジについての性能メトリックを算出することと、
最良の性能メトリックを有する接続性レベル分布を選択することとを含む、請求項１に記載の方法。
【請求項３】
プロセッサと、
前記プロセッサによって実行されたときに、前記装置に方法を実行させる命令を記憶する記憶媒体とを備え、前記方法が、
コンテンツ中心ネットワーキング（ＣＣＮ）ネットワークについてのネットワークノードの数ｋを判定することと、
前記ＣＣＮネットワークについての最適な性能メトリックを実現する接続性の平均レベル及び接続性レベル分布を判定することと、
前記接続性の平均レベルを満たし且つ接続性レベル分布を満たすｋ個のネットワークノードのネットワークトポロジを生成することと、
物理コンピュータネットワークのノードに対して、前記生成されたネットワークトポロジのｋ個のノードをマッピングすることとを備える装置。
【請求項４】
前記物理コンピュータネットワークのノードに対して、前記生成されたネットワークトポロジのｋ個のノードをマッピングすることが、前記選択されたノードが前記ＣＣＮネットワークについての前記生成されたネットワークトポロジを満たすように、前記ＣＣＮネットワークをオーバーレイするために前記物理コンピュータネットワークのｋ個のネットワークノードを選択することを含み、
前記方法が、さらに、前記物理コンピュータネットワークから選択されたｋ個のノードにわたって前記ＣＣＮネットワークを展開することを備える、請求項３に記載の装置。
【請求項５】
接続性の平均レベルを判定することが、
１つ以上の接続性の平均レベルを反復し、前記接続性の各平均レベルについてのｋ個のネットワークノードのネットワークトポロジを生成することと、
各ネットワークトポロジについての性能メトリックを算出することと、
最良の性能メトリックを有する接続性の平均レベルを選択することとを含む、請求項３に記載の装置。
【請求項６】
前記接続性レベル分布を判定することが、
べき乗則分布、及び、
ガウス分布
のうちの１つ以上に基づいて最適な分布を判定することを含む、請求項３に記載の装置。
【請求項７】
前記接続性レベル分布を判定することが、
１つ以上の分布関数にわたって反復し、対応する分布関数に基づいて前記接続性の平均レベルを満たすｋ個のネットワークノードのネットワークトポロジを生成することと、
各ネットワークトポロジについての性能メトリックを算出することと、
最良の性能メトリックを有する接続性レベル分布を選択することとを含む、請求項３に記載の装置。
【請求項８】
前記接続性レベル分布を判定することが、さらに、
前記分布関数についての１つ以上のパラメータを反復し、各分布関数に基づいて前記接続性の平均レベルを満たすｋ個のネットワークノードのネットワークトポロジを生成することと、
各ネットワークトポロジについての性能メトリックを算出することと、
最良の性能メトリックを有するネットワークパラメータを選択することとを含む、請求項７に記載の装置。
【請求項９】
前記接続性レベル分布が分布レベルマトリクスを含む、請求項３に記載の装置。
【請求項１０】
前記接続性レベル分布を判定することが、
前記接続性レベルの各対についての発生値を含むように前記最適な分布レベルマトリクスを生成することを含み、前記分布レベルマトリクスが前記接続性の平均レベルを満たすｋ個のネットワークノードのネットワークトポロジについての最適な性能メトリックを実現する、請求項９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に、コンピュータネットワークに関する。より具体的には、本開示は、インターネットプロトコルネットワークを介したオーバーレイコンテンツ中心ネットワークの展開に関する。
【背景技術】
【０００２】
最近の研究努力は、コンテンツまわりの全ネットワークスタックを再設計するためにコンテンツ中心ネットワーク（ＣＣＮ）を生み出している。ＣＣＮにおいて、パケットは、典型的には、パケットの送信元及び送信先のネットワークアドレスを含んでいない。むしろ、クライアントがコンテンツオブジェクトのリクエストを発行し、ルータがネットワークを介してこれらのリクエストを、リクエストされたコンテンツオブジェクトを含むパケットを返してリクエストに応答する、コンテンツのコピーを記憶する最も近いネットワークノードに対してネットワークを介して直接ルーティングする。
【０００３】
ＣＣＮは、全ての考えられるコンテンツプロバイダまでの明確なルートを設定しなければならないという負担をなくす、適切なコンテンツプロバイダに対してリクエストをルーティングするための機構として制御されたフラッディングを使用することができる。しかしながら、この機構によって生み出される利点は、ネットワークにおけるオブジェクト要求トラフィックの増加したオーバーヘッドのコストがかかる。さらに悪いことに、ＣＣＮノードが互いに接続される方法は、衰弱させるオーバーヘッドなしでＣＣＮネットワークを展開するのを困難とする、ネットワークに存在するインタレスト量において大きな影響を有する。例えば、次善のＣＣＮトポロジは、望ましくない多数のリンクを介してインタレストを流すことができ、特定のＣＣＮノードにおけるネットワークの輻輳を生み出し得る。この次善のトポロジは、ＣＣＮノードにおける不要な処理オーバーヘッドをもたらし得て、これらのインタレストによってアクセスされるコンテンツについての配信時間を増加させ得る。
【発明の概要】
【課題を解決するための手段】
【０００４】
１つの実施形態は、オーバーレイとしてＣＣＮノードの集合体にわたって又は既存のインターネットプロトコル（ＩＰ）ネットワークにわたってコンテンツ中心ネットワーク（ＣＣＮ）のトポロジを設計して展開するシステムを提供する。動作中、システムは、Ｎ個のネットワークノードのコンピュータネットワークを分析し、物理的なネットワークトポロジを判定する。システムはまた、コンテンツ中心ネットワーク（ＣＣＮ）をオーバーレイする物理ネットワークのネットワークノードの個数ｋを判定する。そして、システムは、ＣＣＮオーバーレイネットワークについての最適な性能メトリックを実現する、接続性の平均レベル及び接続性レベルの分布などのトポロジの特定の特性を判定する。システムは、接続性の平均レベルを満たし且つ接続性レベルの分布（又は任意の他の代替若しくは追加の要件）を満たすｋ個のネットワークノードのネットワークトポロジを生成する。システムは、基本的な物理ネットワークのｋ個のノードにわたってコンテンツ中心ネットワークトポロジを展開することができる。
【０００５】
いくつかの実施形態において、オーバーレイＣＣＮネットワークは、ＩＰベースの物理ネットワークを使用して、データの一部の名称に基づいてインタレストメッセージを転送することができる。ＣＣＮにおいて、コンテンツの各部分は、個別に名称付けられ、データの各部分は、同じデータ又は他のソースからのデータの他のバージョンなど、任意の他のデータの部分からデータを区別する固有の名称に結合される。この固有の名称は、固有の名称を示すリクエスト又はインタレストを広めることによってネットワークデバイスがデータをリクエストするのを可能とし、データの記憶場所、ネットワークの場所、アプリケーション及び伝送手段から独立したデータを得ることができる。以下の用語は、ＣＣＮアーキテクチャの要素を説明する。
【０００６】
コンテンツオブジェクト：固有の名称に結合されている名称付きデータの単一部分である。コンテンツオブジェクトは、固有の名称及びデータが暗号化署名を介して結合されていることを意味する、「永続的」である。コンテンツオブジェクトは、変化せずにコンピューティングデバイス内又は異なるコンピューティングデバイス間を移動することができる。コンテンツオブジェクトの任意の要素が変化した場合、変更を行ったエンティティは、更新されたコンテンツを含む新たなコンテンツオブジェクトを作成し、新たな暗号化署名を介して新たな固有の名称に新たなコンテンツオブジェクトを結合する。
【０００７】
固有の名称：ＣＣＮ内の名称は、通常、場所とは無関係であり、コンテンツオブジェクトを固有に識別する。データ転送装置は、コンテンツオブジェクトについてのネットワークアドレス又は物理的場所を必要とせずに、コンテンツオブジェクトを生成又は記憶するネットワークノードに向けてパケットを転送するために名称又は名称接頭辞を使用することができる。いくつかの実施形態において、名称は、階層的に構造化された可変長識別子（ＨＳＶＬＩ）とすることができる。ＨＳＶＬＩは、様々な方法で構築可能ないくつかの階層的な要素に分割されることができる。例えば、個々の名称要素ｐａｒｃ、ｈｏｍｅ、ｎｄｎ及びｔｅｓｔ．ｔｘｔは、名称「／ｐａｒｃ／ｈｏｍｅ／ｎｄｎ／ｔｅｓｔ．ｔｘｔ」を形成するために左指向の接頭辞が主要である方法で構築可能である。それゆえに、名称「／ｐａｒｃ／ｈｏｍｅ／ｎｄｎ」は、「／ｐａｒｃ／ｈｏｍｅ／ｎｄｎ／ｔｅｓｔ．ｔｘｔ」の「親」又は「接頭辞」とすることができる。共同文書などの異なるバージョンのコンテンツアイテムを区別するためにさらなる要素が使用可能である。
【０００８】
いくつかの実施形態において、名称は、コンテンツオブジェクトのデータ（例えば、チェックサム値）及び／又はコンテンツオブジェクトの名称の要素から導出されるハッシュ値などの非階層識別子を含むことができる。ハッシュベースの名称の記載は、（２０１３年３月２０日に出願された発明者Ｉｇｎａｃｉｏ  Ｓｏｌｉｓによる「名称ベースのパケット転送用の順序付けられた要素の名称付け」と名称が付された）米国特許出願第１３／８４７，８１４号に記載されている。名称はまた、フラットラベルとすることができる。以下では、「名称」は、階層名称若しくは名称接頭辞、フラット名称、固定長名称、任意長名称又はラベル（例えば、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ラベル）など、名称データネットワークにおけるデータの一部用の任意の名称を指すのに使用される。
【０００９】
インタレスト：データの一部についてのリクエストを示し且つデータの一部についての名称（又は名称接頭辞）を含むパケットである。データ消費者は、ＣＣＮルータが、記憶装置（例えば、キャッシュサーバ）又はリクエストやインタレストを満たすために要求されたデータを提供することができるデータ制作者に向けて伝播することができるコンテンツ中心ネットワークにわたってリクエストやインタレストを広めることができる。
【００１０】
いくつかの実施形態において、本願明細書に開示される方法はまた、名称付きデータネットワーク（ＮＤＮ）などの他の情報中心ネットワーク（ＩＣＮ）アーキテクチャに適用可能である。ＣＣＮアーキテクチャの記載は、（２００８年１２月１８日に出願された発明者Ｖａｎ  Ｌ．Ｊａｃｏｂｓｏｎ及びＤｉａｎａ  Ｋ．Ｓｍｅｔｔｅｒｓによる「コンテンツ中心ネットワークにおけるインタレスト及びコンテンツの普及の制御」と名称が付された）米国特許出願第１２／３３８，１７５号に記載されている。
【００１１】
いくつかの実施形態において、性能メトリックは、インタレストオーバーヘッド、インタレスト再送回数、利用可能なネットワーク帯域幅、ネットワーク使用率及びインタレスト・ツー・コンテンツオブジェクト往復遅延のうちの少なくとも１つを含む。
【００１２】
いくつかの実施形態において、接続性の平均レベルを測定しながら、システムは、接続性の平均レベルについて１つ以上の値にわたって反復し、接続性の各平均レベルに対するｋ個のネットワークノードのネットワークトポロジを生成する。システムは、各ネットワークトポロジについての性能メトリックを算出し、最良の性能メトリックを有する接続性の平均レベルを選択する。
【００１３】
いくつかの実施形態において、接続性レベルの分布を判定しながら、システムは、べき乗則分布に基づいて、ガウス分布又は分布に関連したパラメータに基づいて、最適な分布を判定する。システムはまた、既知の又は後に開発される任意の他の確率分布に基づいて及び／又は分布に関連したパラメータを用いて最適な分布を判定することができる。
【００１４】
いくつかの実施形態において、接続性レベルの分布を判定しながら、システムは、１つ以上の分布関数にわたって反復し、対応する分布関数に基づいて接続性の平均レベルを満たすｋ個のネットワークノードのネットワークトポロジを生成する。そして、システムは、各ネットワークトポロジについての性能メトリックを算出し、最良の性能メトリックを有する接続性レベルの分布を選択する。
【００１５】
いくつかの実施形態において、接続性レベルの分布を判定しながら、システムは、分布関数についての１つ以上のパラメータにわたって反復し、各分布関数に基づいて接続性の平均レベルを満たすｋ個のネットワークノードのネットワークトポロジを生成する。そして、システムは、各ネットワークトポロジについての性能メトリックを算出し、最良の性能メトリックを有するネットワークパラメータを選択する。
【００１６】
いくつかの実施形態において、接続性レベルの分布を判定しながら、システムは、接続性のレベルの各対についての発生値を指定する最適度分布マトリクスを判定する。レベル分布マトリクスは、接続性の平均レベルを満たすｋ個のネットワークノードのネットワークトポロジについての最適な性能メトリックを実現する。
【図面の簡単な説明】
【００１７】
【図１】図１は、実施形態にかかるＩＰネットワークにわたってオーバーレイされた典型的なコンテンツ中心ネットワークを図示している。
【図２】図２は、実施形態にかかるＩＰネットワークにわたるオーバーレイコンテンツ中心ネットワークを展開する方法を図示するフローチャートである。
【図３Ａ】図３Ａは、実施形態にかかる典型的な接続性レベルの分布を図示している。
【図３Ｂ】図３Ｂは、実施形態にかかる典型的なレベル分布マトリクスを図示している。
【図４】図４は、実施形態にかかる性能メトリックを最適化する接続性の平均レベルを判定する方法を図示するフローチャートである。
【図５】図５は、実施形態にかかる性能メトリックを最適化する分布関数及び関数パラメータを判定する方法を図示するフローチャートである。
【図６】図６は、実施形態にかかるＩＰネットワークにわたるオーバーレイコンテンツ中心ネットワークを展開するのを容易とする典型的な装置を図示している。
【図７】図７は、実施形態にかかるＩＰネットワークにわたるオーバーレイコンテンツ中心ネットワークを展開するのを容易とする典型的なコンピュータシステムを図示している。
【発明を実施するための形態】
【００１８】
図面において、同様の参照符号は、同じ図要素を指す。
【００１９】
以下の説明は、当業者が実施形態を製造して使用するのを可能とするために提示され、特定の用途及びその要件の文脈において提供される。開示された実施形態に対する様々な変更例は、当業者にとって容易に明らかであり、本願明細書において定義される一般的原理は、本開示の精神及び範囲から逸脱することなく、他の実施形態及び用途に適用することができる。それゆえに、本発明は、示された実施形態に限定されるものではなく、本願明細書に開示された原理及び特徴と一致する最も広い範囲を与えられるべきである。
【００２０】
概要
本発明の実施形態は、全てのノードがＣＣＮ機能を有するネットワーク上にＣＣＮネットワークを展開するとき又はインターネット若しくは任意の物理ネットワーク上にＣＣＮオーバーレイを展開するときなど、コンテンツ中心ネットワーク（ＣＣＮ）についての最適なネットワークトポロジを判定するという問題を解決するＣＣＮ展開システムを提供する。例えば、物理ネットワークは、それぞれがＩＰアドレスに関連付けされたルータ、サーバ及びクライアントデバイスのセットを含むことができる。具体的には、各ＩＰアドレスは、物理ＩＰネットワークの特定のネットワークノードに対応し、物理ネットワークにおけるノードは、そのＩＰアドレスに基づいて、意図された受信者に対してデータパケットを転送することができる。しかしながら、ＣＣＮネットワークにおいては、インタレストメッセージが要求されているデータの一部についての名称を指定し、ＣＣＮネットワーク上のノードは、データを提供することができる任意のデバイスに到達するためにインタレストメッセージを転送することができる。
【００２１】
いくつかの実施形態において、ＣＣＮ展開システムは、ＣＣＮネットワークについてのネットワークトポロジを判定することができ、ＩＰネットワーク内のノードのサブセットを使用して、オーバーレイネットワークとして物理ＩＰネットワークにわたってＣＣＮネットワークを展開する。ＣＣＮネットワークを展開しながら、ＣＣＮ展開システムは、ＣＣＮトポロジを実装する適切なフェース（例えば、物理若しくは仮想インターフェース）又は物理ＩＰネットワーク上の仮想リンクを作成することができる。また、ＣＣＮネットワークのトポロジは、オーバーレイＣＣＮネットワークの性能に影響を与えることができる。したがって、システムは、最適に近い性能メトリックを実現するトポロジを判定するために、１つ以上の性能メトリックを使用して、様々なトポロジパラメータをテストすることができる。ＣＣＮトポロジの接続性の特性は、ネットワーク内に存在するインタレストの量に大きな影響を与える可能性がある。例えば、次善のＣＣＮトポロジは、インタレストが望ましくない多数のリンクを介して流れることがあり、特定のＣＣＮノードにおけるネットワークの輻輳を生み出し得る。
【００２２】
システムは、オーバーレイＣＣＮネットワークを形成し、オーバーレイネットワークについての性能メトリックを予測するために、ＣＣＮノード間におけるグラフ特性化及び接続性情報を使用することができる。これらの性能メトリックは、送信又は再送信されたＣＣＮインタレストメッセージの数（又は割合）、これらのインタレストメッセージに起因するオーバーヘッド、コンテンツオブジェクトを取得するための予定時間などの典型的なネットワークの性能メトリック及びＣＣＮ固有の性能メトリックを含むことができる。
【００２３】
システムは、新たなＣＣＮフェース（若しくはリンク）を形成すること又は最適なＣＣＮネットワークトポロジを達成するための既存のＣＣＮフェースを壊すことなどによってオーバレイネットワークのトポロジを微調整するために、これらの予測されたメトリック及びライブネットワークから収集された測定値を使用することができる。例えば、ネットワークプロバイダが物理ネットワークのｋ個のノードにＣＣＮを展開したい場合、システムは、性能メトリックを予測するために、各オーバーレイネットワークの接続性特性に基づいて、最良のＣＣＮオーバーレイトポロジの設計（例えば、メッシュトポロジ、ツリートポロジなど）を算出することができる。オペレータ又はＣＣＮ展開システムは、システムによって生成されるＣＣＮトポロジに基づいてＣＣＮエッジを動的に追加又は除去することにより、オーバーレイＣＣＮネットワークを調整することができる。
【００２４】
図１は、実施形態にかかる物理ネットワーク１００にわたってオーバーレイされた典型的なコンテンツ中心ネットワーク１０２を図示している。コンピューティング環境１００は、１つ以上の技術（例えば、ブルートゥース、Ｗｉ−Ｆｉ、携帯電話、イーサネット（登録商標）、光ファイバなど）によって実装されたコンピュータネットワークなど、様々なコンピューティングデバイスを互いにインターフェースする任意の有線又は無線ネットワークを含むことができる物理ネットワーク１０２を含むことができる。
【００２５】
いくつかの実施形態において、物理ネットワーク１００は、ＩＰベースのネットワークなどの既存のコンピュータネットワークを含んでもよい。ＣＣＮ展開システムは、（物理ネットワーク１０２において太線を使用して図示された）オーバーレイＣＣＮネットワーク１１６を展開するために使用するために物理ネットワーク１００のサブセットを選択することができる。例えば、システムは、オーバレイＣＣＮネットワークが特定のトポロジ（例えば、ツリートポロジ又は特定の平均レベル若しくは特定のレベルの分布を有するトポロジ）を有する場合、４ノードのオーバレイＣＣＮネットワークが最適に近い性能を有することができる旨を判定することができる。したがって、システムは、ＣＣＮノードとして同様に機能するようにエッジノード１０６及びエッジノード１０８を構成することにより、オーバーレイＣＣＮネットワーク１１６を展開することができる。エッジノード１０６及び１０８は、インタレストを処理及び転送するための転送情報ベース（ＦＩＢ）、コンテンツオブジェクトを処理及び転送するための保留インタレスト表（ＰＩＴ）、並びに、コンテンツオブジェクトをキャッシュするためのコンテンツストア（ＣＳ）を含むことができる。システムはまた、それらの高いレベルの接続性に起因してＣＣＮノードとして動作するようにルータノード１０４及び１０６を構成することができる。具体的には、システムは、ＣＣＮネットワーク１１６の他のノードに対する接続性に起因してオーバーレイＣＣＮネットワーク１１６のハブとして動作するようにルータノード１０４を構成することができる。
【００２６】
いくつかの実施形態において、システムは、所望のトポロジを維持するのを確実にするために、オーバーレイＣＣＮネットワーク１１６を維持することができる。例えば、リンク若しくはＣＣＮフェースが故障した場合、又は、ＣＣＮノードがオフラインになるか若しくは到達不能になった場合（例えば、ルータノード１０４又は１１０）、システムは、同じトポロジを維持するために使用するように物理ネットワーク内の他のノードを選択することができ、又は、最適に近い性能メトリックを実現する代わりのＣＣＮのネットワークトポロジを展開することができる。
【００２７】
ＣＣＮトポロジの設計
ＣＣＮ展開システムは、最適なＣＣＮオーバーレイを設計するために、インタレストオーバーヘッドの増加に貢献し、コンテンツを配信してこの特性の特性化情報を使用する時間に影響を与えるネットワークトポロジの特性を特徴付ける。例えば、システムは、ＣＣＮインタレストオーバーヘッド及びコンテンツを配信する時間に影響を与えるトポロジ的特性を最初に分離することができる。これを達成するために、システムは、それらがどのように相互接続されているかを判定するために、グラフのｄＫシリーズのグラフ特性を分析する。これらのグラフは、ｎ個のノードを含み、レベルｋ１、ｋ２、・・・ｋｐは、グラフ内で固有のレベルである。固有のレベルｐの数は、複数のノードが同じレベルを有してもよいことから、グラフｎの大きさに等しくする必要はない。
【００２８】
システムは、各ｄＫ特性と、その基礎となるグラフ（例えば、基礎となるＮノードの物理ネットワークトポロジ）の全てのｄサイズのサブグラフにおける接続性のレベルとの相関を再現するｄＫグラフのセットを生成することができる。ｄ＝０の場合、０Ｋグラフは、基礎となるグラフの接続性の平均レベルを再現する。ｄ＝１の場合、１Ｋグラフは、基礎となるグラフの接続性レベルの分布を再現する。ｄ＝２の場合、２Ｋグラフは、与えられたグラフの結合レベル分布を再現する。同様の方法でこのシリーズを拡張し、ｄ＝ｎの場合、生成されたｎＫグラフは、基礎となるグラフと同型である。要約すると、ｄＫシリーズの各特性は、基礎となるグラフの構造に関するますます多くの情報を埋め込み、それゆえに、ｄＫグラフが基礎となるグラフに収束するまで、対応するｄＫグラフは、ますます制約される。
【００２９】
システムは、ｄＫ分布を満たすランダムグラフ構造を生成することにより、ｄＫグラフを生成することができ、各選択された分布についての予測されるＣＣＮ性能メトリック（例えば、インタレストオーバーヘッド及びコンテンツ配信時間）を測定する。これらのｄＫグラフは、平均ノードレベル又は与えられた構造（例えば、ツリー構造、メッシュ構造など）において相互接続されたｋ＋１個のノードを発見する確率などの様々なグラフトポロジについてのトポロジ的特性の分布を明らかにすることができる。例えば、２Ｋグラフは、レベルｍのノードがレベルｐの他のノードに接続する可能性を明らかにすることができる。さらに、３Ｋグラフは、最大３ノードのループの確率分布を捕捉することができる。ｄＫ分布が明らかにされると、ｄＫグラフ構成アルゴリズムは、この分布を表すランダムグラフを構築するのに使用可能である。
【００３０】
いくつかの実施形態において、システムは、１つの値で２Ｋグラフ構成分布を要約するそれらの選択係数によって２Ｋグラフを特徴付けることができる。システムは、グラフの特定の２Ｋファミリーのトポロジ特性を記載する対応する選択係数に対して性能メトリック値（例えば、予測されるＣＣＮトラフィックのオーバーヘッド及びコンテンツ配信時間）をマッピングすることができる。
【００３１】
システムはまた、ｘ軸上の性能メトリック及びｙ軸上の選択係数によってこのマッピングを図示するプロットグラフを生成することができ、ネットワーク管理者がそれらのＣＣＮインフラストラクチャのニーズに最良に適した選択係数を容易に選択するのを可能とする。プロットグラフは、様々な異なる性能メトリックに対する選択係数（及び様々な対応するグラフ構造）の相関を図示するｄＫグラフを分析するのに使用されるそれぞれ異なる性能メトリックのプロットを含むことができる。
【００３２】
いくつかの実施形態において、システムは、１つ以上の所定の性能メトリックを最適化する選択係数を検索して同定することにより（例えば、平均経路長及び平均インタレストカウントを最小化することにより）、最適に近い選択係数値を自動的に（例えば、人間の介入なしで）算出することができる。
【００３３】
システムはまた、高次のｄＫグラフを分析することができる。例えば、システムは、クラスタリング係数を算出するために、３Ｋグラフ確率分布を分析することができる。これらの３Ｋグラフは、グラフトポロジ的制約に関するより多くの情報をもたらすことができるが、そうすることは、十分に高い計算オーバーヘッドを必要とする。この問題の回避策として、システムは、それらのグラフトポロジ的制約を分析するために、より小さな３Ｋグラフを生成し、それらのクラスタリング係数を比較することができる。そして、トポロジ的制約を満たすグラフ構造を選択した後、システムは、所望の大きさのスケーリングされたグラフを生成するために、所望のグラフ構造のクラスタリング係数を保持するグラフスケーリングアルゴリズムを使用することができる。
【００３４】
システムがＣＣＮネットワークの要件を満たす選択係数及び／又はクラスタリング係数を同定すると、システムは、ｄＫグラフ構築アルゴリズムを使用してこれらの係数を満たす必要なＣＣＮトポロジを生成することができる。管理者はまた、コンピュータネットワーク（例えば、インターネット又は任意の物理ネットワーク）にわたってＣＣＮトポロジを展開した後に得られた実世界の性能データを使用してＣＣＮトポロジをさらに絞り込むためにＣＣＮ展開システムを使用することができる。例えば、展開されたＣＣＮトポロジが輻輳状態を受ける場合、又は、ダウンリンクが実行中のＣＣＮ環境で検出された場合、システムは、所望のｄＫ分布を維持する新たなグラフ構成を生成するためにＣＣＮトポロジを修正することができる。
【００３５】
図２は、実施形態にかかるＩＰネットワーク上のオーバーレイコンテンツ中心ネットワークを展開する方法２００を図示するフローチャートである。動作中、システムは、Ｎ個のネットワークノードのコンピュータネットワークについての物理ネットワークトポロジを判定することができる（動作２０２）。
【００３６】
次に、システムは、物理ネットワーク上に展開するためにオーバーレイコンテンツ中心ネットワークの大きさについての数ｋを選択する（動作２０４）。システムはまた、１つ以上の性能メトリックを最適化することができるオーバーレイコンテンツ中心ネットワークの特徴を判定する。例えば、システムは、オーバーレイＣＣＮネットワークについての最適な性能メトリックを実現する接続性の平均レベルを判定するために、様々なオーバーレイネットワークトポロジを構築して分析することができる（動作２０６）。システムはまた、接続性の平均レベルを満たし且つオーバーレイＣＣＮネットワークについての性能メトリックをさらに最適化する接続性レベル分布を判定するために、様々なオーバレイネットワークトポロジを構築して分析することにより、オーバレイネットワークトポロジについての要件を微調整することができる（動作２０８）。
【００３７】
いくつかの実施形態において、システムは、性能メトリックをさらに最適化するかどうかを判定することができる（動作２１０）。システムが性能メトリックをさらに最適化する必要がない場合には、システムは、接続性の平均レベル及び接続性レベル分布を満たすｋ個のノードのネットワークトポロジを生成するように進むことができる（動作２１４）。
【００３８】
一方、システムが性能メトリックをさらに最適化する必要がある場合には、システムは、接続性の平均レベルを満たすネットワークトポロジについての性能メトリックをさらに最適化する最適なレベル分布マトリクスを判定することができる（動作２１２）。次に、システムは、接続性の平均レベル及びレベル分布マトリクスを満たすｋ個のノードのネットワークトポロジを生成する（動作２１４）。
【００３９】
システムが最適化されたネットワークトポロジを生成すると、システムは、物理ネットワークトポロジのｋ個のノードにわたってオーバーレイＣＣＮネットワークを展開することができる（動作２１６）。
【００４０】
図３Ａは、実施形態にかかる典型的な接続性レベルの分布３００を図示している。具体的には、分布３００のｘ軸は、接続性の平均レベルの範囲にわたり、ｙ軸は、所定の接続性レベルを有するノードの数を指定する。
【００４１】
いくつかの実施形態において、システムは、所定の接続性の平均レベルを満たすように接続性レベルの分布３００を生成する。例えば、１．９６の接続性の平均レベルが最適に近い性能メトリックをもたらすことができるとシステムが判定した場合、システムは、１．９６の接続性の平均レベルを満たす様々な代わりの接続性レベルの分布を生成することができる。システムは、べき乗則分布関数、ガウス分布関数又は既知の若しくは後に開発される任意の他の分布関数を使用することができる。分布３００を生成しながら、システムは、所定の接続性の平均レベルを満たす分布を確保するために分布関数のパラメータを微調整することができる。システムは、これらの分布を満たす様々なネットワークトポロジを生成してシミュレートすることにより、これらの様々な分布関数をテストすることができ、品質メトリックをさらに改善する分布を選択する。
【００４２】
図３Ｂは、実施形態にかかる典型的なレベル分布マトリクス３５０を図示している。具体的には、レベル分布マトリクス３５０の行及び列は、２つの隣接するネットワークノードについての様々な接続性レベルに及ぶ。また、分布マトリクス３５０は、正方行列を含むことができ、分布マトリクス３５０の各要素は、固有のレベルの組み合わせに対応する。分布マトリクス３５０の各セル（ｉ，ｊ）は、レベルｊのノードに接続するレベルｉのノードの確率を示している。例えば、発生値３５２は、ＣＣＮトポロジ内の２つの隣接ノードが値ｍ及び値ｎの所定レベルを有する確率に対応することができ、レベル値ｍのノードは、レベル値ｎのノードに対するアクティブインターフェースを有する。あるいは、発生値３５２は、値ｍ及び値ｎの所定レベルを有するＣＣＮトポロジ内の２つの隣接するノード間にある接続の合計数（又は全ての可能な接続の割合）を含むことができる。
【００４３】
また、システムは、接続性の所定の平均レベルを満たすようにレベル分布マトリクス３５０を生成することができる。いくつかの実施形態において、システムは、所定の分布関数に基づいて値を最初に入力した後に、分布の所定の平均レベルを維持しながら品質メトリックをさらに改善するために様々なセルにおける発生値を調整することによってマトリクス３５０を生成することができる。いくつかの他の実施形態において、システムは、マトリクス３５０にわたって各セルについてのランダムに生成された発生値を最初に入力することにより、マトリクス３５０を生成することができる。そして、システムは、品質メトリックをさらに改善して分布の所定の平均レベルを維持するために様々なセルにおける発生値を調整する。
【００４４】
図４は、実施形態にかかる性能メトリックを最適化する接続性の平均レベルを判定する方法４００を図示するフローチャートである。動作中、システムは、最良の性能メトリックを有する値を選択するために、接続性値の様々な平均レベルを分析することができる。例えば、システムは、ｋ個のノードについての接続性の平均レベルを選択することができ（動作４０２）、接続性の平均レベルを満たすｋ個のノードのネットワークトポロジを生成する（動作４０４）。次に、システムは、ネットワークトポロジについての性能メトリックを算出し（動作４０６）、接続性値の他のレベルを分析するかどうかを判定する（動作４０８）。
【００４５】
システムが分析するために接続性値のより多くの平均レベルを有する場合、システムは動作４０２に戻ることができる。そうでない場合、システムは、最良の性能メトリックを有する接続性の平均レベルを選択するように進むことができる（動作４１０）。
【００４６】
図５は、実施形態にかかる性能メトリックを最適化する分布関数及び関数パラメータを判定する方法を図示するフローチャートである。動作中、システムは、最良の性能メトリックを有する値を選択するために、様々な分布関数及び関数パラメータを分析することができる。例えば、システムは、ｋ個のノードについての分布関数を選択することができ（動作５０２）、分布関数についてのパラメータを選択する（動作５０４）。いくつかの実施形態において、分布関数は、べき乗則分布、ガウス分布又は既知の若しくは後に開発される任意の他の分布関数を含むことができる。
【００４７】
次に、システムは、ｋ個のネットワークノードのネットワークトポロジを生成し（動作５０６）、ネットワークトポロジについての性能メトリックを算出する（動作５０８）。システムは、接続性の平均レベルを満たし且つ分布関数及びパラメータを満たすように、ネットワークトポロジを生成する。また、システムは、フラットファイル（例えば、スプレッドシート文書）又はデータベースリポジトリなどにおける接続性の平均レベル、分布関数及び関数パラメータに関連して性能メトリックを記憶することができる。
【００４８】
いくつかの実施形態において、システムは、他の関数パラメータ又は他の分布関数についての追加の代わりのネットワークトポロジを生成してテストすることができる。例えば、システムが同じ分布関数についての他のパラメータを分析する必要がある場合（動作５１０）、システムは、他のパラメータを選択してこれらのパラメータについての性能メトリックを算出するために動作５０４に戻ることができる。そうでない場合、システムが異なる分布関数を分析する必要がある場合（動作５１２）、システムは、ｋ個のノードについての他の分布関数及び関数パラメータを選択してこの他の関数及びそのパラメータについての性能メトリックを算出するために動作５０２に戻ることができる。
【００４９】
システムが様々な分布関数及び様々な代わりの関数パラメータについての性能メトリックを算出すると、システムは、最良の算出された性能メトリックを判定することができ、最良の性能メトリックに関連付けて記憶された分布関数及び関数パラメータを選択することができる（動作５１４）。システムは、最適に近い性能メトリックを有するネットワークトポロジを生成するために、この分布関数及び関数パラメータを使用することができる。
【００５０】
図６は、実施形態にかかるＩＰネットワークにわたるオーバーレイコンテンツ中心ネットワークの展開を容易とする典型的な装置６００を図示している。装置６００は、有線又は無線通信チャネルを介して互いに通信することができる複数のモジュールを備えることができる。装置６００は、１つ以上の集積回路を使用して実現されてもよく、図６に示されるものよりも少ないか又は多くのモジュールを含んでもよい。さらに、装置６００は、コンピュータシステムに一体化されるか、又は、他のコンピュータシステム及び／又はデバイスと通信することができる別個の装置として実現されてもよい。具体的には、装置６００は、トポロジ特徴付けモジュール６０２と、トポロジ生成モジュール６０４と、ネットワーク分析モジュール６０６と、ＣＣＮ展開モジュール６０８とを備えることができる。
【００５１】
いくつかの実施形態において、トポロジ特徴付けモジュール６０２は、ＣＣＮネットワークについてのネットワークノードの数ｋを判定することができ、ＣＣＮネットワークについての最適な性能メトリックを実現する少なくとも接続性の平均レベル及び接続性レベル分布を判定することができる。トポロジ生成モジュール６０４は、接続性の平均レベルを満たし且つ接続性レベル分布を満たすｋ個のネットワークノードのネットワークトポロジを生成することができる。ネットワーク分析モジュール６０６は、選択されたノードがＣＣＮネットワークについての生成されたネットワークトポロジを満たすように、ＣＣＮネットワークをオーバーレイするコンピュータネットワークのｋ個のネットワークノードを選択することができる。また、ＣＣＮ展開モジュール６０８は、コンピュータネットワークのｋ個のノードにわたってＣＣＮネットワークを展開することができる。
【００５２】
図７は、実施形態にかかるＩＰネットワーク上のオーバーレイコンテンツ中心ネットワークの展開を容易とする典型的なコンピュータシステム７０２を図示している。コンピュータシステム７０２は、プロセッサ７０４と、メモリ７０６と、記憶装置７０８とを含む。メモリ７０６は、管理メモリとして機能する揮発性メモリ（例えば、ＲＡＭ）を含むことができ、１つ以上のメモリプールを記憶するのに使用可能である。さらにまた、コンピュータシステム７０２は、表示装置７１０と、キーボード７１２と、ポインティングデバイス７１４に接続可能である。記憶装置７０８は、オペレーティングシステム７１６、ＣＣＮ展開システム７１８及びデータ７２８を記憶することができる。
【００５３】
ＣＣＮ展開システム７１８は、コンピュータシステム７０２によって実行された場合に、コンピュータシステム７０２に本開示に記載された方法及び／又は処理を実行させることができる命令を含むことができる。具体的には、ＣＣＮ展開システム７１８は、ＣＣＮネットワークについてのネットワークノードの数ｋを判定し、ＣＣＮネットワークについての最適な性能メトリックを実現する少なくとも接続性の平均レベル及び接続性レベル分布を判定するための命令を含むことができる（トポロジ特徴付けモジュール７２０）。さらに、ＣＣＮ展開システム７１８は、接続性の平均レベルを満たし且つ接続性レベル分布を満たすｋ個のネットワークノードのネットワークトポロジを生成するための命令を含むことができる（トポロジ生成モジュール７２２）。
【００５４】
ＣＣＮ展開システム７１８は、選択されたノードがＣＣＮネットワークについて生成されたネットワークトポロジを満たすように、ＣＣＮネットワークをオーバーレイするためにコンピュータネットワークのｋ個のネットワークノードを選択するための命令を含むことができる（ネットワーク分析モジュール７２４）。ＣＣＮ展開システム７１８はまた、コンピュータネットワークのｋ個のノードにわたってＣＣＮネットワークを展開するための命令を含むことができる（ＣＣＮ展開モジュール７２６）。
【００５５】
データ７２８は、本開示に記載された方法及び／又は処理による入力として必要とされるか又は出力として生成される任意のデータを含むことができる。具体的には、データ７２８は、少なくとも基礎となる物理ネットワークのネットワークトポロジ、様々なグラフサイズｋ及び様々な接続性ｄの平均レベルについての一連のネットワークトポロジ、様々なネットワークトポロジについての性能メトリック、並びに、基礎となる物理ネットワークにわたって展開するためのＣＣＮネットワークについての最適化されたトポロジを記憶することができる。
【００５６】
この詳細な説明に記載されたデータ構造及びコードは、典型的には、コンピュータシステムによって使用するためのコード及び／又はデータを記憶することができる任意の装置又は媒体であり得るコンピュータ読み取り可能な記憶媒体に記憶される。コンピュータ読み取り可能な記憶媒体は、これらに限定されるものではないが、揮発性メモリ、不揮発性メモリ、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）、ＤＶＤ（ディジタル多用途ディスク若しくはディジタルビデオディスク）などの磁気及び光記憶装置、又は、既知の若しくは後に開発されるコンピュータ読み取り可能な媒体を記憶することができる他の媒体を含む。
【００５７】
詳細な説明のセクションに記載された方法及び処理は、上述したようなコンピュータ読み取り可能な記憶媒体に記憶されることができるコード及び／又はデータとして具現化することができる。コンピュータシステムがコンピュータ読み取り可能な記憶媒体に記憶されたコード及び／又はデータを読み取って実行した場合、コンピュータシステムは、データ構造及びコードとして具体化され且つコンピュータ読み取り可能な記憶媒体内に記憶された方法及び処理を実行する。
【００５８】
さらにまた、上述した方法及び処理は、ハードウェアモジュールに含めることができる。例えば、ハードウェアモジュールは、これらに限定されるものではないが、特定用途向け集積回路（ＡＳＩＣ）チップ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）及び既知の又は後に開発される他のプログラマブル論理デバイスを含むことができる。ハードウェアモジュールが起動された場合、ハードウェアモジュールは、ハードウェアモジュール内に含まれる方法及び処理を実行する。
【図１】
2016005270.tif 000002
【図２】
2016005270.tif 000003
【図３Ａ】
2016005270.tif 000004
【図３Ｂ】
2016005270.tif 000005
【図４】
2016005270.tif 000006
【図５】
2016005270.tif 000007
【図６】
2016005270.tif 000008
【図７】
2016005270.tif 000009