(57)【要約】  本発明の予測的なオーバーレイネットワークアーキテクチャは、関連付けられたコンテンツアイテムがその上に配布されるオーバーレイネットワークトポロジを確立および再構成することによって、インターネットなどの下位ネットワークのノード間でデジタルコンテンツを配布するアプリケーションのパフォーマンスを改善する。本発明は、頻繁に変化するネットワーク輻輳だけでなく、予想オーバーレイネットワークトポロジのノードおよびリンクの間の相互依存性にも対処する。本発明は、メトリックを監視し、かつオーバーレイネットワークのノード間のコンテンツの中継が（現在または将来の）下位ネットワーク輻輳によって影響を受けるであろう程度を反映するように、個々のノードおよびリンクの中継容量（および宛先ノードの需要）を経時的に予測する予測エンジンを提供する。本発明は、ノードおよびリンクの相互依存性に対処する一方、過剰容量を再配布して、アプリケーション固有のパフォーマンス基準を満たすオーバーレイネットワークトポロジを決定するトポロジセレクタをさらに提供する。【選択図】図１Ａ
2020518179.tif 000002
【特許請求の範囲】
【請求項１】
オーバーレイネットワークに沿ったコンテンツアイテムの１つ以上のセグメントの配布に関する１つ以上のアプリケーション固有のパフォーマンス基準のセットを満たすオーバーレイネットワークトポロジを決定するための方法であって、前記オーバーレイネットワークトポロジが、前記オーバーレイネットワークの複数のノードおよび複数のリンクを含み、各リンクが、前記複数のノードのペアを論理的に相互接続して、そのリンクに沿った前記ノードのペア間の前記１つ以上のセグメントの配布を容易にし、前記方法が、
（ａ）連続する時間期間中に複数のメトリックを定期的に測定および処理することであって、各メトリックが、各時間期間の間に、その時間期間中に使用される現在のオーバーレイネットワークトポロジの前記ノードまたはリンクに関連付けられている属性を反映し、前記処理されたメトリックが、前記現在のオーバーレイネットワークトポロジのノード中継属性およびリンク中継属性を反映する、測定および処理することと、
（ｂ）予想オーバーレイネットワークトポロジのノードおよびリンクに関連付けられている前記処理されたメトリックに基づいて、それらのノードおよびリンクのノード中継容量およびリンク中継容量を予測することと、
（ｃ）それらのノードおよびリンクの前記予測されたノード中継容量およびリンク中継容量に少なくとも部分的に基づいて、前記予想オーバーレイネットワークトポロジが前記パフォーマンス基準を満たしているかどうかを決定することと、を含む、方法。
【請求項２】
コンテンツアイテムがその上に配布されるオーバーレイネットワークトポロジを再構成する方法であって、各オーバーレイネットワークトポロジが、複数のネットワークノード、および前記複数のネットワークノードを相互接続する複数のリンクを含み、前記方法が、
（ａ）現在のオーバーレイネットワークトポロジに関する複数のメトリックを生成する工程と、
（ｂ）前記複数のメトリックに基づいて、指定されたノードおよびリンクのセットに関する複数の予測を生成する工程と、
（ｃ）前記複数の予測に基づいて予想オーバーレイネットワークトポロジを識別する工程と、を含む、方法。
【請求項３】
前記予想オーバーレイネットワークトポロジが、前記指定されたノードおよびリンクの前記パフォーマンスに関する１つ以上の制約を表すパフォーマンス基準を満たす、請求項２に記載の方法。
【請求項４】
各オーバーレイネットワークトポロジが、ピアベースのオーバーレイネットワークトポロジである、請求項２に記載の方法。
【請求項５】
各ネットワークノードが前記予想オーバーレイネットワークトポロジの一部となるかどうかを示す視聴者指標予測を生成する工程をさらに含む、請求項２に記載の方法。
【請求項６】
前記予想オーバーレイネットワークトポロジの一部となるそれらのネットワークノードが、前記予想オーバーレイネットワークトポロジの一部のままとなる間の時間の継続期間を示すセッション継続期間予測を生成する工程をさらに含む、請求項５に記載の方法。
【請求項７】
前記複数の予測が、前記指定されたノードのノード中継容量および前記指定されたリンクのリンク中継容量の予測を含む、請求項２に記載の方法。
【請求項８】
前記複数のメトリックが、ノードメトリック、リンクメトリック、ならびに前記ノードメトリックおよびリンクメトリックが取得される間のタイムスタンプを含む、請求項２に記載の方法。
【請求項９】
コンテンツアイテムがその上に配布されるオーバーレイネットワークトポロジを再構成する適応トポロジサーバであって、各オーバーレイネットワークトポロジが、複数のネットワークノード、および前記複数のネットワークノードを相互接続する複数のリンクを含み、前記適応トポロジサーバが、
（ａ）現在のオーバーレイネットワークトポロジに関する複数のメトリックを生成するメトリックプロセッサと、
（ｂ）前記複数のメトリックに基づいて、指定されたノードおよびリンクのセットに関する複数の予測を生成する予測エンジンと、
（ｃ）前記予測エンジンから、前記指定されたノードおよびリンクのセットに関する複数の予測を取得し、かつ前記複数の予測に基づいて予想オーバーレイネットワークトポロジを識別する、トポロジセレクタと、を備える、適応トポロジサーバ。
【請求項１０】
前記トポロジセレクタが、１つ以上のパフォーマンス制約を表すパフォーマンス基準を満たす予想オーバーレイネットワークトポロジを識別する、請求項９に記載の適応トポロジサーバ。
【請求項１１】
各オーバーレイネットワークトポロジが、ピアベースのオーバーレイネットワークトポロジである、請求項９に記載の適応トポロジサーバ。
【請求項１２】
前記予測エンジンが、各ネットワークノードが前記予想オーバーレイネットワークトポロジの一部となるかどうかを示す視聴者指標予測を生成する、請求項９に記載の適応トポロジサーバ。
【請求項１３】
前記予測エンジンが、前記予想オーバーレイネットワークトポロジの一部となるそれらのネットワークノードが、前記予想オーバーレイネットワークトポロジの一部のままとなる間の時間の継続期間を示すセッション継続期間予測を生成する、請求項１２に記載の適応トポロジサーバ。
【請求項１４】
前記予測エンジンが、前記指定されたノードのノード中継容量および前記指定されたリンクのリンク中継容量を生成する、請求項９に記載の適応トポロジサーバ。
【請求項１５】
前記メトリックプロセッサによって生成された前記複数のメトリックが、ノードメトリック、リンクメトリック、ならびに前記ノードメトリックおよびリンクメトリックが取得された間のタイムスタンプを含む、請求項９に記載の適応トポロジサーバ。
【請求項１６】
それぞれのオーバーレイネットワークトポロジに沿って複数のコンテンツアイテムを同時に配布するための方法であって、各オーバーレイネットワークトポロジが、複数のネットワークノード、および前記複数のネットワークノードを相互接続する複数のリンクを含み、前記方法が、
（ａ）第１のオーバーレイネットワークトポロジに沿って第１のコンテンツアイテムを配布する工程と、
（ｂ）第２のオーバーレイネットワークトポロジに沿って第２のコンテンツアイテムを配布する工程であって、前記第１のコンテンツアイテムおよび第２のコンテンツアイテムが、それらのそれぞれのオーバーレイネットワークトポロジに沿って同時に配布される、工程と、
（ｃ）前記第１のオーバーレイネットワークトポロジに沿ってネットワークノードに前記第１のコンテンツアイテムを配布する工程であって、前記ネットワークノードが、前記第１のオーバーレイネットワークトポロジおよび前記第２のオーバーレイネットワークトポロジの両方に含まれ、前記ネットワークノードが、前記第１のコンテンツアイテムを消費する、工程と、
（ｄ）前記第２のオーバーレイネットワークトポロジに沿って前記ネットワークノードに前記第２のコンテンツアイテムを配布する工程であって、前記ネットワークノードが、前記第２のオーバーレイネットワークトポロジの別のネットワークノードに前記第２のコンテンツアイテムを中継する、工程と、を含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
この出願は、２０１７年４月２１日に出願された米国仮特許出願第６２／４８８，５０２号および２０１８年４月１０日に出願された米国仮特許出願第６２／６５５，７０３号の優先権を主張し、その開示は、本明細書に完全に記載されているものとして参照により本明細書に組み込まれる。
【０００２】
背景
本発明は、概して、インターネットなどの下位ネットワークの上に構築されたオーバーレイネットワークのノード間でのデジタルコンテンツの配布に関し、より詳細には、オーバーレイネットワークのノードおよびリンクの間のパフォーマンスの相互依存の状況で、頻繁に変化する下位ネットワークの輻輳に対処することによって、定義されたアプリケーション固有のパフォーマンス基準を満たすオーバーレイネットワークトポロジを決定する予測的なオーバーレイネットワークアーキテクチャに関する。
【背景技術】
【０００３】
Ａ．ネットワーク輻輳の問題
最も基本的なレベルでは、コンピュータネットワークは、データまたは情報（本明細書では互換的に使用される）の交換、およびネットワークノードによって提供されるリソースの共有を目的として、直接的または間接的に相互接続された複数のネットワークデバイス（ノード）で構成される。例えば、１つのネットワークスイッチに接続された２台のコンピュータおよび１台のネットワークプリンタは、両方のコンピュータのユーザがネットワークプリンタによって提供される印刷リソースを共有できる単純な「ローカルエリアネットワーク」（ＬＡＮ）を形成する。
【０００４】
この単純なネットワークでは、コンピュータおよびネットワークプリンタの両方がネットワークスイッチに直接接続されるが、ただし相互には間接的にのみ接続されており、すべてがＬＡＮ上のノードとみなされる。接続が有線媒体または無線媒体のどちらを介して行われても同じである。
【０００５】
この単純なＬＡＮでも、一方または両方のコンピュータが所与の時間期間中に十分に大量の情報をネットワークプリンタに送信すると、ネットワーク輻輳が発生し、これにより、（例えば、ネットワークプリンタのメモリのバッファが過負荷になり、ネットワークトラフィックがプリンタの設計容量を超えている場合）印刷の遅延および個々の印刷ジョブの潜在的な失敗がもたらされる。ネットワーク輻輳の問題に対処するために、特にＬＡＮにより多くのコンピュータが追加されると、追加のネットワークプリンタおよびソフトウェアを導入して、共有されるネットワークプリンタ間でコンピュータからの印刷要求を「負荷分散」し、すなわち、補給品を増加し、需要を分配する場合がある。
【０００６】
明らかになるように、共有されるリソースを提供するネットワークノードでのネットワーク輻輳の問題は、下位コンピュータネットワークのサイズおよび範囲が拡大するにつれて急激により複雑になる。例えば、ネットワーク印刷のサポートに加えて、ＬＡＮ上のデバイスは、ファイル転送、電子メール、ビデオ会議、ならびにその他のネットワークアプリケーションおよびサービスなどの追加のネットワーク機能を提供することがある。ネットワークノードによるこの追加機能が共有で使用されることにより、必然的にネットワーク輻輳の問題が悪化する。というものも、この共有機能を消費するノードの「需要」が、そのような機能を提供および配布する個々のノードの「供給」または容量を日常的に超えるためである。
【０００７】
異なる物理的な場所（例えば、様々な個人、商業、政府、およびその他のエンティティによって運用される）における多くのノードを含めるように、下位ネットワークがＬＡＮを超えて拡張される場合、ネットワークルータは、「ワイドエリアネットワーク」（ＷＡＮ）を形成するために、複数のコンピュータネットワークの相互接続を可能にするように展開される。インターネット、つまり、最も一般的かつ頻繁に利用されるＷＡＮ（すなわち、ネットワークのネットワーク）は、世界中の数十億のデバイスを相互接続し、膨大な数の共有ネットワークアプリケーションおよびサービス（本明細書では単に「アプリケーション」と呼ぶ）をサポートする下位のインフラストラクチャを提供する。
【０００８】
集中制御がほとんどないか、またはまったくないアドホックネットワークとしての歴史的な進化により、インターネットは、全体的に対処するのが困難なネットワーク輻輳の問題に満ちている。特に、ネットワークノード間の情報のルーティングは分散化されている。ルーティングの決定は、様々な分散型のルーティングアルゴリズムを実装する「中間ルーティングノード」（多くの異なるエンティティによって提供されるルータ、スイッチ、ブリッジ、ゲートウェイ、ファイアウォールなど）によって分散型の様式でなされる。
【０００９】
その結果、各ルータまたは他の中間ルーティングノードは、情報を送信する「ネクストホップ」ノードを決定するが、集中型エンティティは、情報が「ソース」ノードから「宛先」ノードへトラバースする経路全体（すなわち、２つのノード間の個々の「ホップ」のセット）を決定しない。さらに、現在、それらの相互接続を含むインターネット上のネットワークノードのトポロジ全体は、任意のそのようなエンティティによって実行可能に決定することはできない。
【００１０】
情報（本明細書では「デジタルコンテンツ」とも呼ばれる）をインターネット上で配布するために、情報は、一意の「インターネットプロトコル」（ＩＰ）アドレスによって各ネットワークノードを識別するＩＰアドレス指定スキームに従って、個々にルーティングされる小さなパケットに分割される。１つのネットワークノード（ノードＡ）が別のネットワークノード（ノードＢ）に情報を送信する場合、通常、その情報は複数のＩＰパケットに分割され、各々、宛先ノード（ノードＢ）の宛先ＩＰアドレスでアドレス指定されるが、各々、ノードＡからノードＢへの異なる経路（様々な中間ルーティングノード間のホップ）を潜在的にトラバースし、ここでこれらのパケットは再構築される。
【００１１】
これらの中間ルーティングノードは、幅広いアプリケーション（例えば、ウェブブラウジング、ファイル転送、電子メール、テレフォニー、ビデオストリーミングなどを含む）に参加している他の多くのネットワークノードによって任意の所与の時点で利用される共有リソースであるため、これらの共有中間ルーティングノードの１つ以上でのネットワーク輻輳は非常に一般的である。その結果、ソースノードが宛先ノードに情報を転送する能力は、これらの共有中間ルーティングノードを介して情報が配布されるときに遅延が発生するため、このネットワーク輻輳によって悪影響を受ける。このようなネットワーク輻輳は、デバイスまたはケーブルの障害、過度な帯域幅需要、および情報がこれらの共有中間ルーティングノードを介して配布される際の「パフォーマンス」を制限する様々な他の要因の結果として発生し得る。
【００１２】
これらの共有中間ルーティングノードでのネットワーク輻輳の性質を理解するには、そのような中間ルーティングノードを、デジタルコンテンツを「消費」する（すなわち、「宛先」ノード）、またはデジタルコンテンツをアプリケーションに関連するネットワーク上に生成または挿入する（すなわち、ソースノード）役割を果たす「ユーザ」ノードから区別することが役立つ。上記で言及したネットワークプリンタ（宛先ノード）は、情報を消費している間に輻輳が発生する可能性がある共有ネットワークリソースであるが、グローバルインターネットにわたって情報を配布する目的で存在する共有中間ルーティングノードにおいて、はるかに問題の多いネットワーク輻輳の形態が発生する。
【００１３】
個々のネットワークノードは、ソースノードと宛先ノードとの両方の機能を実行することができることに留意されたい。このようなノードは、相互接続される特定のタイプのネットワークトポロジ（例えば、スター、リング、ツリー、メッシュ、および実質的にあらゆるタイプの図表またはその他の物理的もしくは論理的トポロジ）を問わず、コンピュータサーバだけでなく、クライアントノード（例えば、デスクトップおよびラップトップコンピュータ、スマートフォン、テレビ、ストリーミングメディアボックス、センサ、ならびにその他の様々な接続デバイス）も含む。
【００１４】
すべてのネットワークデバイスは、インターネットなどの下位ネットワークのネットワークノードとみなすことができるが、特定のアプリケーションに参加するユーザノードは、しばしば、下位ネットワークの上に構築される「オーバーレイネットワーク」を形成する「オーバーレイノード」と呼ばれる。言い換えれば、アプリケーションの上位レベルの「論理」の観点から、オーバーレイノードのみがそれらのオーバーレイノード間の情報の「オーバーレイ配布」に含まれる（それでも、情報は最終的に、任意の所与のオーバーレイノードのペア間の中間ルーティングノードをトラバースする）。
【００１５】
例えば、オーバーレイノードＡ、Ｂ、およびＣが与えられた場合、ノードＡからノードＣへの経路は、２つの論理オーバーレイ経路または「リンク」のセット（ノードＡからノードＢへの第１のリンク、およびノードＢからノードＣへの第２のリンク）として表現できる。ただし、下位ネットワークの観点から、オーバーレイノードのペア間の各論理リンクには、様々な中間ルーティングノードを通る１つ以上の下位レベルのホップが含まれ、これらのうちの任意の１つ以上は、深刻な遅延（例えば、他のアプリケーションサービスプロバイダによって実装された異なるオーバーレイネットワーク間でのこのような中間ルーティングノードの共有から生じるネットワーク輻輳に起因する）を誘引する可能性がある。
【００１６】
そのため、オーバーレイネットワークのオーバーレイノード間のオーバーレイ経路またはリンクのセットを、各リンクの決定の結果として情報がトラバースする中間ルーティングノード間の下位レベルの経路またはホップのセットと区別することが重要である。各論理リンクの作成者は、そのリンクに沿って情報がトラバースすることになるであろう下位レベルの経路を明示的に決定しない。実際、このような下位レベルの経路は、リンクが決定された後でも事前には分からない。
【００１７】
代わりに、これらの下位レベルの経路は、中間ルーティングノード自体の中に実装された分散型のルーティングアルゴリズムによって動的に決定される。したがって、ユーザノードのペア間の各リンクの決定は、（データの各パケットについて）そのリンクに沿った中間ルーティングノード間の多くの異なる下位レベルの経路の１つになり、この各々で異なる程度のネットワーク輻輳が発生する可能性がある。
【００１８】
また、情報の配布は、あるノードから別のノードへの、すなわち、「親」ノードから「子」ノードへのその情報の「中継」を、そのようなノードがオーバーレイノードであるか、もしくは中間ルーティングノードであるか（または、無線もしくは物理ケーブルを介して接続されているか）にかかわらず、本質的に含むことに留意されたい。例えば、上記で言及した（ノードＡからノードＣへの）オーバーレイ経路は、ノードＢを介した情報の中継を含む。同様に、ノードＡとノードＢとの間の個々のリンクは、Ａ→Ｂリンクに沿った下位ネットワーク上で、様々な中間ルーティングノードによる情報の中継をもたらす。
【００１９】
実際問題として、ノードは情報を中継するために、最初にその情報を受信し、次いでそれを他のノードに送信する前に複製するが、このプロセスは本質的に、完了までにある程度の量の時間を必要とし、したがって、遅延期間を誘引する。この遅延期間は、ノード自体の中の内部輻輳を含むネットワーク輻輳の変化の結果として、経時的に増減することがある。例えば、ノードは、そのプロセッサ（複数可）、メモリ、およびその他のコンピューティングリソースにデマンドを要求する複数の内部タスク（例えば、ゲームのプレイまたはスプレッドシートの再計算）を実行するときに遅延を誘引する可能性があり、これは次いで、他のノードへ情報を中継するその能力に影響を与える。中間ルーティングノードは、複数のアプリケーション間で日常的に共有されるため、特に遅延を誘引しやすくなる。
【００２０】
インターネット上でパケットをルーティングする状況では、パケットは光に近い速度で移動するため、ノード間の物理的距離（または地理的な近接度）は、パフォーマンスに有意な影響を与えない。ただし、経路に沿った平均速度または合計スループットは、その経路に沿って遭遇したストップもしくはロードブロックの数、またはこの状況では、ソースノードから宛先ノードに情報を中継する中間ルーティングノードで遭遇したホップの数に影響を受ける。したがって、２つのノードは、比較的少数のホップしか離れていない場合、それらの地理的な近接度に関係なく、（「ネットワークの近接度」で）互いに「近接」していると言える。
【００２１】
ネットワーク近接度は、２つのユーザノード間のリンクに沿ったスループットを決定する要因になる可能性があるが、それはいくつかの理由で決定的ではない。例えば、ソースもしくは宛先ノード、または存在する場合にはいずれかのそのリンクに沿った中間ルーティングノードでは、輻輳または可変量の遅延を誘引するその他の問題が発生する場合がある。複数のスタンドアロンまたはネットワークアプリケーションに同時に参加しているユーザノードが輻輳し、情報の受信、消費、および中継のパフォーマンスに影響を与える場合がある。遅延は、そのリンクに沿ってノードを相互接続する物理的なケーブルの障害から生じる場合もある。
【００２２】
その結果、（特に１つ以上の中間ルーティングノードでの）ネットワーク輻輳は、ソースおよび宛先ノードの任意のペア間の全体の移動時間またはスループットに重大な影響を与えることがある。例えば、ユーザノードのペア間のリンクに沿った６ホップ経路は、４ホップ経路に沿ってのみ遭遇する中間ルーティングノードでのネットワーク輻輳に起因する遅延の結果として、４ホップ経路よりも高速になることがある。
【００２３】
つまり、ネットワーク輻輳には多くの原因がある。上記で例示したように、任意のネットワークノードまたは相互接続されたノードのペア（ユーザノードだけでなく、中間ルーティングノードも含む）のパフォーマンスは、内部需要、ノード内の運用遅延もしくは障害、他のノードとの間のトラフィックにより生じる輻輳、または他の原因を問わず、ネットワーク輻輳によって影響を受けることがある。さらに、インターネットなどの下位ネットワーク上の輻輳は、ネットワークトラフィックが増減することに伴って大きな変動の影響を受けるため、そのような輻輳は、任意の所与の時点で分離および測定することは難しく、特に短期間でさえ予想することは困難である。
【００２４】
Ｎｅｔｆｌｉｘなどの単一の企業がピーク時のインターネットトラフィックの３分の１より多くを占める場合、インターネット上でデジタル情報を配布する他の企業は、確実に一貫性のあるパフォーマンスの目標を達成する（また、企業はそのような目標を定義する）何らかの望みを有する場合、インターネット輻輳のますます不安定な性質に何らかの方法で対処する必要がある。同様に、モバイル音声およびデータ使用量が急増するにつれて、規制されたＲＦスペクトルの限られた可用性は、高帯域幅モバイルアプリケーションを開発する企業にとって特に懸念事項である。
【００２５】
ネットワーク輻輳を予想する問題は、人口が増加している地域の共有道路と高速道路との交差点での交通渋滞を予想する問題に類似している。既存のＧＰＳナビゲーションおよび交通制御システムは、これらの交差点での現在の渋滞を測定し、そのような渋滞の周りの個々の運転手を再案内する代替の経路を計算するが、任意の特定の運転手にとって望ましい経路を予測する能力は、交通渋滞の不安定な性質によって妨げられる。
【００２６】
以下で明らかになるように、（ネットワーク輻輳の悪影響を低減するために）代替の経路の中から選択する問題は、そのようなネットワーク輻輳の多くの原因の各々の性質および場所に関する完全な知識を必ずしも必要としない。代替の経路またはその構成要素（個々のノードまたはリンクなど）のパフォーマンスに対するネットワーク輻輳の影響を決定するだけで十分である。
【００２７】
異なる既存のオーバーレイネットワークアーキテクチャがネットワーク輻輳の問題にどのようにアプローチするかを調べる前に、インターネットの基礎となるアーキテクチャが問題を悪化させるうえでどのように重要な役割を果たしているかを理解しておくと役立つ。
【００２８】
Ｂ．下位インターネットアーキテクチャ
ＡＲＰＡＮＥＴ（インターネットプロトコルスイートまたはＴＣＰ／ＩＰを実装する最も初期のパケットスイッチングネットワーク）に始まり、より後のＮＳＦＮＥＴでは、インターネットの「バックボーン」は、制御を分散化して所望の宛先に情報を到達させるための代替の通信経路を提供することによって、信頼性または「復元力」を提供する冗長な「ネットワークのネットワーク」（すなわち、インターネット）に設計されている。それでもなお、中間ルーティングノードなどの共有ネットワークリソースを通って異なる経路をたどるパケットについて、一貫性のあるパフォーマンスを維持するアプリケーションの能力は、極めて難しい問題のままである。
【００２９】
分散化されたルーティング制御によってもたらされる復元力と一貫性のあるパフォーマンスの欲求との間のこの基本的なトレードオフは、インターネットのトポロジの経時的な進化によって証明されるように、インターネットのネットワーク輻輳問題の中心にある。このトポロジは、おそらく複数の異なるタイプのネットワークを包含するルーティング階層として最もよく説明することができる。
【００３０】
このルーティング階層の中心には、各々がしばしば、「自律システム」（ＡＳ）と呼ばれる、相互接続されたネットワークのグループがある。ウィキペディアに記載されているように、各ＡＳは、「共通の明確に定義されたルーティングポリシをインターネットに提示する単一の管理エンティティまたはドメインに代わって、１つ以上のネットワークオペレータの制御下にある」一連の接続されたＩＰルーティングプレフィックス（ＩＰアドレスの範囲）から成る。各ＡＳには、これによってルーティングの目的でインターネット上で一意に識別される「自律システム番号」（ＡＳＮ）が割り当てられる。
【００３１】
これらのコアネットワークの各々は、本明細書ではＡＳまたはＡＳＮと互換的に呼ばれる。これらのネットワークの数は近年、１５年前の約５，０００のネットワークから現在の世界中の５０，０００を超えるネットワークにまで飛躍的に増加している。まとめて、これらのネットワークは、主に相当量の情報を、ネットワーク間で、最終的には世界中のほぼすべての国の様々な宛先ユーザノードに伝播または中継するために存在するという点で、インターネットの「バックボーン」を形成していると言える。
【００３２】
異なる企業が、これらのコアネットワークを所有しているため、彼らは、これらのネットワークにわたって、またグローバルインターネットを通したインターネットトラフィックのルーティングを容易にするために、しばしば、相互に「ピアリング」契約を締結する。各ＡＳネットワークは、しばしば、「ピアリングポイント」と呼ばれる一連のルータ（中間ルーティングノード）を利用して、別のＡＳネットワークへのアクセスを制御し、「ボーダーゲートウェイプロトコル」またはＢＧＰ（「ＡＳ内」の中間ルーティングノードによって使用される様々なルーティングプロトコルとは区別される）として公知であるルーティングプロトコルを使用する。任意の所与のＡＳは、複数のピアリングポイントを使用して、１つ以上の他のＡＳネットワークに接続し得る。相互接続されたＡＳネットワークは、地理的に隣接している場合もあれば、遠くに離れて、（例えば、国および大洋をも越えて）長距離に及ぶ長いファイバートランクを介して接続されている場合がある。
【００３３】
インターネット上のネットワークトラフィックの相当の部分は、相互接続されたこれらの最大規模のＡＳネットワークの交差点または「ジャンクション」を通過するため、これらのＡＳネットワークのピアリングポイントでは、ラッシュアワー中の主要な高速道路のジャンクションでの交通渋滞とは異なり、多くのネットワーク輻輳が発生する。ただし、これらのネットワーク内のＡＳ内中間ルーティングノードでも重大なネットワーク輻輳が発生することに留意されたい。
【００３４】
ＡＳ間およびＡＳ内ルーティングを実行する中間ルーティングノードの提供に加えて、多くのＡＳネットワークはまた、「インターネットサービスプロバイダ」（ＩＳＰ）として公知であるエンティティによって提供される特別なタイプのＡＳ内「ゲートウェイ」中間ルーティングノードも含む。これらのＩＳＰゲートウェイ中間ルーティングノードは、インターネット上で利用可能な様々なアプリケーションに関連付けられているデジタルコンテンツを配布および消費するユーザノードの様々なネットワークに、インターネットへのゲートウェイを提供する。ユーザノードがインターネットに、そのＩＳＰによって提供されるゲートウェイノードを介して接続する場合、そのユーザノードは、そのゲートウェイ中間ルーティングノードを含むＡＳネットワーク内に「ネットワークロケーション」を有すると言うことができる。
【００３５】
このようなゲートウェイノードを含まないＡＳネットワークは、しばしば、（ユーザノード）顧客にサービスを提供する「パブリック」ネットワークとは対照的に、「プライベートバックボーン」ネットワークと呼ばれる。大規模なパブリックネットワーク（主要なＩＳＰなど）の多くの運営者はまた、重大なインターネットトラフィックのルーティングを容易にするために、（独自のパブリックネットワーク、および／または他者によって所有されたネットワークに接続される）プライベートバックボーンネットワークも所有している。
【００３６】
ただし、ＡＳネットワークによって提供される中間ルーティングノード（例えば、ゲートウェイルータを含むＡＳ内ルータ、ＡＳ間ＢＧＰルータ）は、ユーザソースおよび宛先ノードによって生成され、それらの間で配布される情報の発信元のソースまたは最終的な宛先ではないことに留意することが重要である。代わりに、これらの中間ルーティングノードは、様々なソースユーザノードによって提供される情報をインターネットにわたって位置している分類された宛先ユーザノード間で配布するという最終的な目的のために、大量の情報を中継するように設計された「コンジット」である。これらの区別は、以下の図１Ａに示されている。
【００３７】
図１Ａの図表１００ａは、パブリックＡＳネットワーク１１０ａのセットから成るインターネットのアーキテクチャ図を例示している。各ＡＳネットワーク（１１０ａ−１〜１１０ａ−８）は、それらのＡＳネットワーク１１０ａ間の情報を相互接続および中継するＡＳ間ルータ（ＢＧＰルータ）１１５ａ、ならびに各ＡＳネットワーク１１０ａ内の情報を中継するＡＳ内ルータ１２５ａ（ＩＳＰによって提供されるゲートウェイルータを含む）の２つのセットの中間ルーティングノードを含む。
【００３８】
ユーザノード１３０ａは、ゲートウェイルータとして公知であるＡＳ間ルータ１２５ａのサブセットを介してインターネットに接続する。ユーザノード１３０ａは、インターネットの上で実行される様々な共有アプリケーションに参加する（および／またはその基礎となる機能を提供する）ソースおよび宛先ノードを表す。特定のアプリケーションに関して、そのようなユーザノード１３０ａは、その特定のアプリケーションに関連付けられているオーバーレイネットワークを構成するオーバーレイノード（「アプリケーションノード」とも呼ばれる）とみなすことができる。このオーバーレイネットワークは、インターネットの基礎となるインフラストラクチャ、すなわち、様々なＡＳネットワーク１１０ａの中およびしばしばそれらにわたる中間ルーティングノード１１５ａおよび１２５ａの２つのセットの上で実行される。
【００３９】
上述したように、ユーザノード１３０ａは、任意のそのようなアプリケーションの一部としてコンテンツを消費も提供もしない中間ルーティングノード１１５ａおよび１２５ａと区別することができる。また後述するように、あるタイプの（「エッジベースの」）オーバーレイネットワークアーキテクチャは、技術的にはインターネットの基礎となるアーキテクチャの一部ではないが、本明細書で参照するユーザノードよりも中間ルーティングノードに近い役割を実行するノードから成る。
【００４０】
Ｃ．オーバーレイネットワークアーキテクチャ
上述したように、オーバーレイネットワークは、インターネットなどの下位ネットワークの上に構築される。オーバーレイネットワークの目的の１つは、下位ネットワーク輻輳に対処することである。例えば、２つのオーバーレイノード間の特定のリンクに沿った中間ルーティングノードでのネットワーク輻輳は、そのような輻輳を効果的に「迂回」またはバイパスするようにオーバーレイネットワークを再構成することによって（例えば、そのリンクの親ノードまたは子ノードを交換することによって）対処することができる。
【００４１】
下位ネットワーク輻輳の結果として、多くのアプリケーションでは、ユーザの「経験の質」（ＱｏＥ）、すなわち、ユーザ中心またはアプリケーションレベルのアプリケーションのパフォーマンスの品質観に悪影響を与える中断および遅延が発生する。例えば、ブロードキャストビデオアプリケーションでは、中でもフレームのドロップおよび再バッファリングイベントなどの要因が、ユーザのＱｏＥに影響を与えることがある。さらに、ＱｏＥの低下は、しばしば主に、インターネットの基礎となる共有インフラストラクチャが一貫性のある「サービス品質」（ＱｏＳ）、すなわち、スループット、レイテンシ、およびジッタなどのネットワーク中心のメトリックに基づくパフォーマンスの測定値を配信できないことに起因する。
【００４２】
パフォーマンスをネットワーク中心の抽象レベルで評価し、かつ／またはアプリケーションのユーザの経験を反映するよりも上位の（アプリケーション固有の）抽象レベルで評価するかどうかにかかわらず、ノードの様々な属性、およびオーバーレイネットワーク内の任意の特定の経路に沿ってデータがトラバースするリンクは、経時的に測定することができる。本明細書では、概して、このような属性をメトリックと呼ぶ。
【００４３】
この状況では、メトリックはまた、下位ネットワーク上の他のアプリケーションおよびイベントからもたらされるこれらのノードおよびリンクへの影響（例えば、スーパーボールまたはその他の人気のある帯域幅集中型イベント、ネットワークの特定の領域でのネットワーク停止などに起因するトラフィックおよび遅延の増加）についての「外部」指標も含む。このような情報は、例えば、ネットワークトラフィックを経時的に監視することによって直接取得するか、またはインターネットトラフィックを監視し、特定のトラフィックパターンが経時的に明らかになる地域またはグローバルインターネット「トラフィックマップ」を時折作成する第三者から間接的に取得することができる。
【００４４】
アプリケーションに関連して配布される特定の「コンテンツアイテム」に関して、任意の所与の時間期間中、関連する「オーバーレイネットワークトポロジ」を、オーバーレイノードのセットとして、およびそれらを相互接続するリンクのセットとともに定義することができ、これを通して、コンテンツアイテム（またはその一部）が配布および消費される。さらに、そのオーバーレイネットワークトポロジ（ならびにその構成要素ノードおよびリンク）のパフォーマンスは、一連のメトリックのアプリケーション固有の機能として表現することができる。
【００４５】
その時間期間中、現在のオーバーレイネットワークトポロジのパフォーマンスは、定義された「パフォーマンス基準」を満たす場合と満たさない場合があり、これは、アプリケーション固有の一連のパフォーマンス制約として表すことができる。パフォーマンス基準が満たされない場合（例えば、下位ネットワークの輻輳に起因して）、オーバーレイネットワークトポロジを、そのリンクのうちの１つ以上を変更することによって再構成することを選択することができ、これにより、次いでコンテンツアイテムがトラバースすることになる下位レベルの経路への変更がもたらされる（ネットワーク輻輳をバイパスする可能性がある）。
【００４６】
インターネット上のネットワーク輻輳の問題に対処する多くの異なるアプローチが存在するが、これらのアプローチは、２つの個別のタイプのオーバーレイネットワークアーキテクチャに大きく分類することができる。
【００４７】
１．エッジベースのオーバーレイネットワーク
このようなアーキテクチャの１つは、本明細書では「エッジベースの」オーバーレイネットワークと呼ばれるものから成り、これは、アプリケーションコンテンツを発信および消費するユーザノードとは異なる追加の専用ハードウェア（エッジルータまたはエッジサーバとして公知であり、これらは本明細書では互換的に使用される）の使用を含む。言い換えれば、ユーザ（ソースおよび宛先）ノードは、エッジベースのオーバーレイネットワークの一部とはみなされない。代わりに、オーバーレイノードは、（しばしば、「コンテンツデリバリネットワーク」またはＣＤＮと呼ばれるグループとして）エッジサーバ自体である。
【００４８】
アプリケーションは、ＣＤＮのエッジサーバを利用して、そのリンクに沿った下位レベルの中間ルーティングノードにおいてネットワーク輻輳に対処する目的で、任意の所与のリンクに沿って（ソースユーザノードから宛先ユーザノードへ）代替の「ＣＤＮ経路」を提供し得る。ただし、以下で明らかになるように、これらの代替のＣＤＮ経路は、ＣＤＮを通過するリンクに対してのみネットワーク輻輳に対処する。
【００４９】
アプリケーションのユーザノードがインターネット上に広く分散し、ネットワーク輻輳が事実上どこでも発生する可能性がある場合、ＣＤＮのエッジサーバは通常、インターネット全体を通したＡＳネットワークの「エッジ」に戦略的に配置され、それによって、ＣＤＮによって提供される１つ以上のエッジサーバに（ネットワーク近接度で）「近い」ユーザノードへの代替のＣＤＮ経路を容易にする。さらに、ＣＤＮは、重複するＣＤＮ経路に沿った必要なリンクの数を減少するために、これらのエッジサーバでコンテンツを頻繁に「キャッシュ」する。
【００５０】
例えば、図１Ｂの図表１００ｂは、個々のＡＳネットワーク１１０ｂ−１、１１０ｂ−２、および１１０ｂ−３を含むインターネットの基礎となるアーキテクチャの上で実行されるように示されている、エッジベースのオーバーレイネットワークのアーキテクチャ図を例示する。簡単のために、各ＡＳネットワーク１１０ｂ内のＡＳ間およびＡＳ内中間ルータノードは図表１００ｂには示されていない。
【００５１】
ノード１２０ｂ（ＡＳネットワーク１１０ｂ−１内）は、コンテンツアイテムがそこから発信され、かつインターネット全体を通して様々なユーザノード１３０ｂに（ＣＤＮインフラストラクチャを介して）配布される「ソース」ノードを表す。（通常は共有の）ＣＤＮインフラストラクチャを利用する特定のアプリケーションの状況では、アプリケーションは、ＣＤＮ内の機能に依存して、コンテンツアイテムがソースノード１２０ｂから各ユーザノード１３０ｂまでトラバースすることになるＣＤＮ経路を決定する。
【００５２】
コンテンツアイテムは、ソースノード１２０ｂから（ＣＤＮインフラストラクチャを介して）様々なユーザノード１３０ｂへと配布される前に、「セグメント」（すなわち、構成要素の部分）へと分割されてもよいことに留意されたい。いくつかのシナリオでは、異なるコンテンツアイテムまたは個々のコンテンツアイテムのセグメントを配布するために、複数のソースノードが使用される。上記で示唆したように、コンテンツアイテムの個々のセグメントでさえ、様々な中間ルーティングノードを通る異なる下位レベルの経路に沿ってルーティングされる、ＩＰパケットへとさらに分割されることがある。
【００５３】
いずれにせよ、ソースノード１２０ｂがコンテンツを各個別のユーザノード１３０ｂへと直接配布することは非効率的であるため、エッジベースのオーバーレイネットワークのＣＤＮインフラストラクチャ内の機能（すなわち、ＣＤＮエッジサーバオーバーレイノード１２５ｂ）は、これらのオーバーレイノード１２５ｂを介してソースノード１２０ｂからユーザノード１３０ｂへとコンテンツを中継するために採用される。言い換えれば、各宛先ユーザノード１３０ｂ（宛先ユーザノード１３０ｂ−ＤＥＳＴなど）に関して、ＣＤＮは、個々のＣＤＮエッジサーバオーバーレイノード１２５ｂ（ラベルＡ〜Ｉ）のペア間の親子「ＣＤＮリンク」のセットから成る、その宛先ユーザノード１３０ｂ−ＤＥＳＴへのＣＤＮ経路を決定する。
【００５４】
例えば、図表１００ｂの破線矢印は、ソースノード１２０ｂから１つの特定の宛先ユーザノード１３０ｂ、すなわちノード１３０ｂ−ＤＥＳＴへの現在のＣＤＮ経路を例示している。このＣＤＮ経路は、次の５つの親子ＣＤＮリンク（ソースノード１２０ｂおよび宛先ユーザノード１３０ｂを含む）から成る。１２０ｂ→Ａ、Ａ→Ｂ、Ｂ→Ｆ、Ｆ→Ｈ、最後にＨ→１３０ｂ−ＤＥＳＴ。
【００５５】
ＣＤＮが現在のＣＤＮ経路に沿って、（例えば、そのリンクに沿った下位レベルの中間ルーティングノードを含むＢ→ＦのＣＤＮリンクに沿った輻輳に起因する）輻輳を検出した場合、ＣＤＮはその輻輳を検出された経路をバイパスするための代替のＣＤＮ経路を生成する。
【００５６】
例えば、代替のＣＤＮ経路（実線の矢印で示す）は、次の８つの親子ＣＤＮリンクから成る（ソースノード１２０ｂおよび宛先ユーザノード１３０ｂも含む）：１２０ｂ→Ａ、Ａ→Ｂ、Ｂ→Ｃ、Ｃ→Ｄ、Ｄ→Ｅ、Ｅ→Ｇ、Ｇ→Ｈ、そして最後にＨ→１３０ｂ−ＤＥＳＴ。この代替の８リンクＣＤＮ経路は、現在の５リンクＣＤＮ経路よりもソースノード１２０ｂから宛先ノード１３０ｂ−ＤＥＳＴへのより速いスループットをもたらす可能性がある（これは例えば、問題のあるＢ→ＦのＣＤＮリンクをバイパスするため）。
【００５７】
ＣＤＮは、様々な代替のＣＤＮ経路の全体的なスループットを検出できる場合があるが、ＣＤＮは、結果として生じるネットワーク輻輳の正確な原因を検出できない場合があることに留意されたい。例えば、現在のＣＤＮ経路のネットワーク輻輳は、個々のＢまたはＦオーバーレイノード１２５ｂ自体によって、または問題のあるＢ→ＦのＣＤＮリンクに沿った特定の中間ルーティングノード（Ｂ→Ｆリンクに沿った下位レベル配布ルーティングアルゴリズムによって選択される）によって引き起こされることがある。
【００５８】
いずれにせよ、ＣＤＮ機能が、Ｂ→Ｆリンクに沿った特定のオーバーレイノード１２５ｂまたは中間ルーティングノードがこのネットワーク輻輳の原因であるという事実（ましてやその理由）に「気付かない」場合でも、代替のＣＤＮ経路は、問題のあるＢ→ＦのＣＤＮリンクを含まない（したがって、バイパスする）ため、より高いスループットを実現する場合がある。
【００５９】
上記の例では、代替のＣＤＮ経路の全体的なスループットは、これらのＣＤＮ経路のパフォーマンスの尺度の１つである。それでもなお、このスループットは、複数のＣＤＮ経路間でパフォーマンスを比較するという状況では、このようなパフォーマンスに対するネットワーク輻輳の影響の間接的な指標としても機能する。この例では、全体的なスループットは、ＣＤＮが現在の５リンクＣＤＮ経路よりも良好なパフォーマンスをもたらす代替の８リンクＣＤＮ経路を選択できるようにするのに十分である。他のシナリオでは、代替のＣＤＮ経路のこの比較を容易にするために、ネットワーク輻輳のパフォーマンスへの影響の追加の間接的な指標（すなわち、他のメトリック）を使用することができる。
【００６０】
さらに、様々な個々のエッジサーバでコンテンツをキャッシュすることによって、ＣＤＮは、このキャッシュされたコンテンツを活用することによって、例えば、コンテンツがＣＤＮエッジサーバオーバーレイノード１２５ｂのうちの１つでキャッシュされるという事実を活用し、したがって、ソースノード１２０ｂで発信されるＣＤＮリンクのセットを必要としないことによって、特定の宛先ユーザノード１３０ｂへの全体的なＣＤＮリンクがより少ない、複数の重複するＣＤＮ経路を（ソースユーザノードから）生成してもよい。
【００６１】
要するに、エッジベースのオーバーレイネットワークは、ＣＤＮルーティング機能がそのオーバーレイノード１２５ｂのペア間にＣＤＮリンクの代替のセット（図表１００ｂの破線および実線矢印のそれぞれのセットによって示される代替のＣＤＮ経路など）を定義することによって、（宛先ユーザノード１３０ｂへの）代替のエッジベースのＣＤＮ経路を定義できるようにするオーバーレイノードのセット（エッジサーバ１２５ｂ）を含む。ただし、共有のエッジベースのオーバーレイネットワーク上のアプリケーションによる依存は、多くの欠点をもたらす。
【００６２】
例えば、追加の物理的インフラストラクチャ（ＣＤＮエッジサーバオーバーレイノード１２５ｂ）を購入またはリースするコストは法外なものになる場合がある。エッジサーバは通常、（例えば、インターネット全体を通して多数のユーザノード１３０ｂに対応するために）様々なＡＳネットワーク１１０ｂの「エッジ」の多数の戦略的な場所に配置された高帯域幅接続を有する高価なコンピュータサーバである。
【００６３】
エッジベースのオーバーレイネットワークのコスト効率を高めるために、エッジサーバは、しばしば、複数のエンティティによって提供される様々なアプリケーション間で共有される。その結果、これらのアプリケーションは、様々な宛先ユーザノード１３０ｂへの重複するＣＤＮ経路に対応するために、エッジサーバ１２５ｂを（互いと、かつさらには個々のアプリケーションのユーザノード１３０ｂ間で）共有する必要がある。その結果、エッジベースのオーバーレイネットワークは、実際にネットワーク輻輳を誘引し、解決するように設計された問題を悪化させる可能性がある。
【００６４】
さらに、エッジベースのオーバーレイネットワークは、オーバーレイノードとしてユーザノード１３０ｂを利用しないため、それらの代替のＣＤＮ経路は、コンテンツを消費しないＣＤＮエッジサーバオーバーレイノード１２５ｂに依存する（宛先ユーザノード１３０ｂと同様）。例えば、ＣＤＮの機能を活用するために、任意のユーザノード１３０ｂ宛てのコンテンツは、ＣＤＮ（およびそのエッジサーバオーバーレイノード１２５ｂ）を通過する必要がある。
【００６５】
言い換えれば、ＣＤＮによって提供される追加のインフラストラクチャ（エッジサーバ）は、本質的にコンテンツを「ルーティング」する（そして消費しない）ように存在し、これは、インターネットの基礎となるアーキテクチャの一部である下位レベルの中間ルーティングノードに類似している。その結果、エッジベースのオーバーレイネットワークは、ユーザノード１３０ｂ間でコンテンツを配布するために追加のコンピューティングリソースを必要とし、このこと自体が、遅延および他の非効率性を誘引する可能性がある。
【００６６】
本質的に、エッジベースのオーバーレイネットワークは、「ピアベース」のオーバーレイネットワーク（後述する）よりもネットワーク輻輳に対処する直接的な方法を少ししか提供せず、実際には、コンテンツの消費に直接関与しない共有リソースをインターネットエコシステムに追加することによってネットワーク輻輳に貢献する。
【００６７】
２．ピアベースのオーバーレイネットワーク
本明細書で「ピアベース」のオーバーレイネットワークと呼ばれるものを含む代替のアーキテクチャは、エッジベースのアーキテクチャとは大幅に異なるアプローチを使用する。追加のインフラストラクチャ（エッジサーバ）に依存してコンテンツを宛先ユーザノードへと配布する代わりに、ピアベースのアプローチは、既存の宛先ユーザノード（コンテンツを受信および消費する）のリソースを活用してコンテンツをそれらの間で中継する。言い換えれば、ピアベースのオーバーレイネットワークでは、宛先ユーザノードはオーバーレイノードである。
【００６８】
したがって、「ピアツーピア」（Ｐ２Ｐ）アプローチは、選択した宛先ユーザノードのリソース（既存の「容量」）を活用して、コンテンツを受信および消費するだけでなく、そのコンテンツを他の宛先ユーザノードに中継する。本明細書では、これらのタイプのオーバーレイノードは（ピアベースのオーバーレイネットワークの）「ピアノード」と呼ばれる。というのは、これらのオーバーレイノードは、他のこのようなピアノードへとコンテンツを中継することがあるためである。上述したように、このようなノードはまた、特定のアプリケーション（または個々のコンテンツアイテム）に関連してコンテンツを消費するため、時として「アプリケーションノード」とも呼ばれる。
【００６９】
ピアベースのオーバーレイネットワークは、数多くの異なるタイプの物理および論理ネットワークトポロジ（スター、リング、ツリー、メッシュ、および実質的にあらゆるタイプの図表を含む）に実装することができる。既存のピアベースのオーバーレイネットワークは、ファイル転送、「ビデオオンデマンド」（ＶＯＤ）、オーディオおよびビデオストリーミング、ライブビデオブロードキャスト、ならびに様々なその他のコンテンツ配布アプリケーションなどの、数多くの異なるタイプのアプリケーションに使用されている。
【００７０】
例えば、図１Ｃの図表１００ｃは、ソースノード１２０ｃからのコンテンツが１つのピアノード（ユーザノード１３０ｃ）から別のピアノードに一方向に配布され、このため、すべてのユーザノード１３０ｃ（インターネット全体を通して位置しており、１１０ｃ−１〜１１０ｃ−３として個々に示されているＡＳネットワーク１１０ｃを含む）が最終的にコンテンツを受信しておよび消費する、ツリーベースのトポロジを例示している。図１Ｂに例示されるエッジベースのオーバーレイネットワークとは異なり、図表１００ｃのオーバーレイノードは、ユーザノード１３０ｃ自体、すなわち、コンテンツを受信および消費するノードである。
【００７１】
さらに、これらのユーザノード１３０ｃの多くは、コンテンツを他のユーザノード１３０ｃにも中継する（コンテンツを受信および消費するだけの「リーフノード」とは区別される）。図１Ｃの様々な親子リンクは、エッジサーバのペア間のＣＤＮリンクまたはアプリケーション自体の一部ではない他の追加のインフラストラクチャである図１Ｂのリンクとは異なり、ユーザノード１３０ｃのペア間のリンクである。ユーザノード１３０ｃ自体（ピアベースのオーバーレイノード）のリソースを活用してコンテンツを中継することによって、ピアベースのネットワークは、いかなる追加の外部帯域幅またはエッジベースのオーバーレイネットワーク（ＣＤＮ）の共有エッジサーバによって提供されるものなどのその他のリソースも必要とせずに、そのコンテンツを消費する宛先ユーザノード１３０ｃ間でのそのコンテンツの配布を容易にする。
【００７２】
例えば、ソースノード１２０ｃからユーザノード１３０ｃ−ＤＥＳＴへのピアベースのオーバーレイ経路（破線の矢印で例示する）は、次の３つの親子リンクを含む。１２０ｃ→Ａ、Ａ→Ｂ、そして最後にＢ→１３０ｃ−ＤＥＳＴ。この同じピアベースのオーバーレイ経路のサブセット（例えば、Ａ→Ｂからの単一リンク）を使用して、ソースノード１２０ｃからの代替のオーバーレイ経路、またはユーザノード１３０ｃ自体のインフラストラクチャ以外の任意の追加のインフラストラクチャを必要とせずに、他のユーザノード１３０ｃ（例えば、ノードＢ）による消費のためのコンテンツを配布することもできる。
【００７３】
残りのユーザノード１３０ｃは、他のピアベースのオーバーレイ経路、およびそのサブセットリンク（実線の矢印で例示する）によって処理され、ここでは「ピアツーピア」中継を使用して、それらの個々のピアユーザノード１３０ｃのそうでなければ未使用であるリソースを活用し、例えば、コンテンツを一時的にキャッシュし、そのコンテンツを代替のピアベースのオーバーレイ経路の一部として他のピアノードに中継する。その結果、ピアベースのオーバーレイネットワークは、それらの配布される性質が、輻輳の個々のポイント（デバイスまたはケーブルの障害を含む）からの回復を、例えば、このような輻輳をバイパスするためにその他のピアノードを介してコンテンツを配布することによって容易にするという点で、エッジベースのオーバーレイネットワークよりも復元力および拡張性が高い傾向がある。
【００７４】
ピアベースのネットワークの信頼性およびパフォーマンスは、より多くのノードが追加されるにつれて実際に向上し、追加の物理インフラストラクチャ（エッジサーバ）を、（例えば、ユーザノードが追加および削除され、異なるタイプのコンテンツアイテムが様々なアプリケーションによって展開される場合）帯域幅需要の変化に対応するために「負荷分散」する必要があるエッジベースのネットワークとは対照的に、より多くのより優れた代替のオーバーレイ経路が利用可能になる。
【００７５】
ピアベースのオーバーレイネットワークは、エッジベースのアーキテクチャに固有の高価な追加インフラストラクチャの必要性を回避するが、既存のピアベースのソリューションはなおも、下位ネットワーク輻輳を効果的にバイパスしない。この問題は、同じ時間期間中に多数のピアノードが人気のあるコンテンツアイテムに（または様々な異なるコンテンツアイテムにさえも）アクセスしようとしたときに特によく見られる。
【００７６】
既存のピアベースのオーバーレイネットワークは通常、ノードの追加または削除に対処するために、すなわち、「現在の」ピアノードのセットに対応するために、必要な限りにおいて再構成される。新しいリンクを作成して、システムに新しいノードを追加するだけでなく、ノードがシステムを離れた結果として生じる「壊れた」リンクにも対処する。出発ノードがリーフノードである場合、そのノードへのリンクは削除される。ただし、その出発ノードが以前に子ノードへとコンテンツを中継した親ノードである場合、その子ノードは新しい親ノードを必要とする「孤立した」子ノードになり、新しいリンクの作成が必要になる。
【００７７】
ただし、ピアノードが追加または削除されるときだけでなく、ネットワーク輻輳が個々のノードおよびリンクを含むピアベースのオーバーレイネットワークトポロジのパフォーマンスに悪影響を与えるとき（そして理想的にはその前）にも、（部分的な修正を行うことによるか、または新しいトポロジを効果的に決定することによるかにかかわらず）トポロジを再構成することが望ましい。言い換えれば、ネットワーク輻輳のパフォーマンスへの影響を制限するには、ピアベースのオーバーレイネットワークトポロジを再構成して、アプリケーションのパフォーマンス基準を満たしつつ、検出された（ならびに予想された）ネットワーク輻輳を効果的にバイパスすることが望ましい。
【００７８】
Ｄ．予測的なオーバーレイネットワークアーキテクチャの必要性
ただし、（定義されたアプリケーション固有のパフォーマンス基準を満たすために）どのユーザノードが他のどのユーザノードにコンテンツを中継するべきかを決定するタスクは、特に順列の数がオーバーレイネットワークに追加されるユーザノードの数と共に急激に増加するため、困難なものである。このタスクの困難を理解するために、上記で暗示されるように、経時的に収集されたメトリックは、オーバーレイネットワークトポロジのパフォーマンスに対するネットワーク輻輳の影響の間接的な指標としてのみ機能することを認識することが重要である。
【００７９】
言い換えれば、メトリックは、ネットワーク輻輳の直接的な測定値ではない。代わりに、ネットワークトラフィックのフローに対するネットワーク輻輳の影響を反映する。ネットワーク輻輳は、オーバーレイネットワークトポロジ（ならびにその構成要素ノードおよびリンク）のパフォーマンスに影響を与えるが、そのオーバーレイネットワークトポロジが定義されたパフォーマンス基準を満たしているかどうかを決定するのは、このようなパフォーマンスに対するネットワーク輻輳の影響である。履歴メトリックは、その影響をこれから測定および予測できるデータを提供する。既存のオーバーレイネットワークアーキテクチャはなおも、メトリックを代替のオーバーレイネットワークトポロジのパフォーマンスと相関させる様式で、ネットワークの輻輳に対処していない。
【００８０】
ネットワーク輻輳は、しかしオーバーレイネットワークトポロジの潜在的なパフォーマンスを評価する際の障害の１つにすぎないことに留意されたい。別の（しばしば見落とされる）障害は、オーバーレイネットワークトポロジのノードおよびリンクの間の「相互依存性」の存在である。これらの相互依存性は、頻繁に変化するネットワーク輻輳の影響を除いてさえも、この問題を悪化させる。
【００８１】
静的なネットワーク輻輳を想定してさえも、任意の特定のオーバーレイネットワークトポロジの個々のノードおよびリンクの予想パフォーマンスは、「アップストリーム」ノードおよびリンクのパフォーマンスに依存する。特に、親ノードから子ノードへのリンクのパフォーマンスは、その親ノードへのリンクのアップストリームパフォーマンスに依存する。例えば、ノードが、その親ノードから特定のレート（例えば、５００ｋｂｐｓ）でコンテンツを受信した場合、そのコンテンツをより高いレート（例えば、１ｍｂｐｓ）でその子ノードへと中継することはできない。ただし、より詳しく後述するように、ノードは、（このような各子ノードに対して最大５００ｋｂｐｓのレートで）コンテンツを複数の子ノードに同時に複製および中継する「容量」を有する場合がある。
【００８２】
現在のピアベースのアプローチ（ならびエッジベースのアプローチ）はなおも、コンテンツアイテムがこれを通して配布および消費されるオーバーレイネットワークトポロジの個々のユーザノードおよびリンクの間のこれらの相互依存性に対処していない。これらのアプローチはまた、オーバーレイネットワークトポロジの再構成を容易にする様式で、下位ネットワーク輻輳の問題、すなわち、代替のオーバーレイネットワークトポロジが、コンテンツアイテムの配布および消費に関してアプリケーションによって課されるパフォーマンス基準の制約を満たすかどうかの決定に効果的に対処できていない。
【００８３】
既存のピアベースのオーバーレイネットワーク（ＧＰＳナビゲーションシステムなど）は、ピア中継ノードを選択するために、地理的な近接度に依存し、かつ検出されたネットワーク輻輳に応答したという「事実の後」にのみトラフィックを「再ルーティング」する傾向がある。エッジベースのオーバーレイネットワークは、インターネットなどの下位ネットワークの共有インフラストラクチャの上で実行される様々なアプリケーションによって定義されるパフォーマンス基準を満たす様式で、これも頻繁に変化するネットワーク輻輳の問題に適切に対処することができない、（高速道路のネットワークを構築してより高速の代替のルートを提供するような）高価な外部物理インフラストラクチャに依存している。
【００８４】
そのため、アプリケーションのパフォーマンス基準に照らして代替のオーバーレイネットワークトポロジを評価する際に、ネットワーク輻輳が事後的に評価されるか、または将来的に評価されるかにかかわらず、このような依存性を考慮する必要がある。
【００８５】
要するに、必要とされるのは、個々のノードおよびリンクの予想パフォーマンスがアップストリームノードおよびリンクのパフォーマンスに依存するという事実を反映し、かつノードが追加および削除されるときだけでなく、ネットワーク輻輳が宛先ユーザノードによって経験されるパフォーマンスに悪影響を与えるとき（理想的にはその前）にも、定義されたアプリケーション固有のパフォーマンス基準を満たすオーバーレイネットワークトポロジを決定する様式で、頻繁に変化するネットワーク輻輳に対処する予測的なオーバーレイネットワークアーキテクチャである。
【発明の概要】
【００８６】
上述したように、インターネット全体を通した下位ネットワーク輻輳が、オーバーレイネットワークを介してデジタルコンテンツを配布するアプリケーションのパフォーマンスに影響を与えることは十分に確立されている。本発明は、任意の所与の時間期間中、オーバーレイネットワークトポロジの（およびその個々のノードおよびリンクの）パフォーマンスが、下位ネットワーク輻輳だけでなく、その時間中に使用された特定のオーバーレイネットワークトポロジの構成（これは、そのオーバーレイネットワークトポロジのノードおよびリンクの間にアップストリームおよびダウンストリームの依存関係を生成する）にも依存するという事実に対処することによって、既存のアプローチの欠陥を克服する予測的なオーバーレイネットワークアーキテクチャを提供する。本発明は、現在のオーバーレイネットワークトポロジを経時的に再構成し、ネットワークに追加およびネットワークから削除されたノードに対応するだけでなく、定義されたパフォーマンス基準を満たしつつパフォーマンスを改善する。
【００８７】
一実施形態では、本発明は、オーバーレイネットワークトポロジの個々のノードおよびリンクのパフォーマンスに対するネットワーク輻輳の影響を部分的に測定することによって、頻繁に変化するネットワーク輻輳に対処する。本発明は、このような測定値を使用して、予想オーバーレイネットワークトポロジの指定されたノードおよびリンクの容量を予測してコンテンツを中継する。特に、予想親ノードの「ノード中継容量」は、１つ以上の子ノードからの需要を同時に満たすノードの能力を反映する一方、指定されたリンクの「リンク中継容量」は、そのリンクの指定された子ノードからの需要を満たすリンクの能力を反映する。
【００８８】
例えば、親ノードＡが子ノードＢにコンテンツを中継するリンク（Ａ→Ｂ）のパフォーマンスは、親ノードＡから子ノードＢへのリンクに沿った中間ルーティングノードによって引き起こされるものなどの、下位ネットワーク輻輳による影響を受ける場合がある。子ノードＢによる５ｍｂｐｓの需要を想定して、親ノードＡがその需要を満たす（すなわち、５ｍｂｐｓでコンテンツを子ノードＢに配信することによって）場合、Ａ→Ｂリンクは、５ｍｂｐｓのリンク中継パフォーマンス（リンク中継容量の指標）を示したと言うことができる。代替的に、親ノードＡが（例えば、３ｍｂｐｓで子ノードＢにコンテンツを配信することによって）その需要を満たすことができない場合、Ａ→Ｂリンクは、３ｍｂｐｓリンク中継パフォーマンスを示したと言える。
【００８９】
後者の場合、特定の子ノード（子ノードＢ）の需要を満たす親ノードＡの失敗は、単独の、または組み合わせの様々な要因の結果である場合があることに留意されたい。例えば、このような失敗は、Ａ→Ｂリンクに沿ったネットワーク輻輳などの、ダウンストリームの依存性の結果としてもたらされる場合がある。また、親ノードＡ自体内の要因（例えば、帯域幅集約型ゲームのプレイなど、ノードＡの他のアクティビティのパフォーマンス）の結果としてもたらされる場合もある。さらに、このような失敗は、アップストリームの依存関係（例えば、３ｍｂｐｓでノードＡにコンテンツを配信するノードＡの親ノード）の結果としてもたらされる場合がある。
【００９０】
予想オーバーレイネットワークトポロジのノードおよびリンクの間のこのような相互依存性の評価を容易にするために、本発明は、予想親ノードのノード中継容量も考慮する。例えば、一実施形態では、親ノードＡが現在３つの子ノードに（Ａ→Ｂ、Ａ→Ｃ、およびＡ→Ｄリンクに沿って）コンテンツを同時に中継する場合、親ノードＡは、これら３つのリンクのリンク中継パフォーマンスの合計に等しいノード中継パフォーマンスを示したと言うことができる。より詳細に後述するように、親ノードＡの実際のリンク中継容量は、さらに高い場合さえもある。
【００９１】
上記で示唆したように、ノードは複数の子ノードにコンテンツを同時に複製および中継できるため、５ｍｂｐｓでコンテンツを受信するノードは、複数の子ノードに（各々、５ｍｂｐｓで）コンテンツを同時に中継する容量を有している場合がある。ただし、ノードのノード中継容量は、様々な要因によって制限されることがある。例えば、ノードのアップリンク速度は１０ｍｂｐｓである場合があり、これは、ノードが３つ以上の子ノードに（各々、５ｍｂｐｓで）コンテンツを同時に中継することを妨げる。
【００９２】
ただし、１０ｍｂｐｓのノード中継容量を有するノードは、いかなる２つの子ノードにも（各々、５ｍｂｐｓで）コンテンツを同時に中継できるとは言えない場合があることに留意されたい。例えば、ノードＡのノード中継容量が１０ｍｂｐｓであるが、Ａ→Ｂリンクのリンク中継容量が３ｍｂｐｓである場合、ノードＡは、（例えば、Ａ→Ｂリンクに沿ったダウンストリーム依存性に起因して）子ノードＢにのみ３ｍｂｐｓでコンテンツを中継することができる。
【００９３】
より詳細に後述するように、本発明は、予想オーバーレイネットワークトポロジのノードおよびリンクのノード中継容量とリンク中継容量との両方に依存して、定義されたパフォーマンス基準（各宛先ノードからの５ｍｂｐｓ需要など）を満たすオーバーレイネットワークトポロジを識別する。そうすることで、本発明は、頻繁に変化するネットワーク輻輳、ならびにあらゆる予想オーバーレイネットワークトポロジのノードおよびリンクの間の相互依存性に対処する。
【００９４】
これに関して、本発明は、コンテンツアイテムがこれに沿って伝搬されるオーバーレイネットワークトポロジのノードおよびリンクのパフォーマンスを反映するリアルタイムメトリックの監視および処理を活用する。上記で示唆されるように、任意の所与の時間期間中、現在のリアルタイムメトリックは、現在のオーバーレイネットワークトポロジの個々のノードおよびリンクのパフォーマンスに対するネットワーク輻輳の影響の間接的な指標として機能する。このようなメトリックはまた、現在のオーバーレイネットワークトポロジの構成によって生成されるアップストリームおよびダウンストリーム依存性の結果（ならびにノードおよびリンク自体に固有の属性）を間接的に反映する。
【００９５】
一実施形態では、「メトリックプロセッサ」は、オーバーレイネットワークトポロジの予想ノードおよびリンクに関連付けられている生のメトリックを処理し、このような処理されたメトリックを（このような生のメトリックが観測および収集された時間期間を反映するメトリック「タイムスタンプ」と共に）「予測エンジン」に提供する。予測エンジンは、指定された予想親ノードのノード中継容量を予測する「ノード中継分類器」と、予想リンクのリンク中継容量を予測する「リンク中継分類器」と、を含む。
【００９６】
メトリックプロセッサは、ノード中継分類器への入力として、予想親ノードのノード中継属性を表す１つ以上の「ノードメトリック」、すなわち、ノードが１つ以上の子ノードにコンテンツを中継する能力の指標を生成する。一実施形態では、ノードメトリックは、ＣＰＵ負荷、メモリ使用量、オペレーティングシステム、接続タイプ、アップリンクおよびダウンリンク速度、ＩＰアドレス、ＩＳＰ、ＡＳＮ、ならびに予想親ノードの様々な他のノード中継属性を含む。他の実施形態では、ノードメトリックは、予想親ノードのノード中継パフォーマンスを（間接的にすら）反映する程度まで、様々な追加のＱｏＳおよびＱｏＥメトリック（例えば、とりわけドロップされたフレームおよび再バッファリングイベント）を含む。本発明の趣旨から逸脱することなく、より少ないかまたは追加のメトリックを使用できることは、当業者には明らかであろう。
【００９７】
ノード中継分類器の訓練に関連して、メトリックプロセッサはまた、その親ノードの観測された現在のノード中継パフォーマンスを反映する予想親ノード（例えば、各サンプル時間期間中）に関する対応する出力も生成する。例えば、親ノード（ノードＡ）が特定の時間期間中に５ｍｂｐｓを子ノードＢに、かつ３ｍｂｐｓを子ノードＣに同時に配信した場合、親ノードＡに関する「訓練サンプル」は、（ノード中継分類器への入力として）ノードＡに関連付けられているノードメトリック（これらのノードメトリックが取得された時間期間を反映するタイムスタンプと共に）、および（ノード中継分類器への出力として）ノードＡの観測されたノード中継パフォーマンスの合計（例えば、８ｍｂｐｓ）を含むことになる。他の実施形態では、入力の各セット（ノードメトリック）に対して複数の出力が提供され、親ノードの現在のノード中継パフォーマンスを表す単一の値を計算するために、（一実施形態では）事前定義された関数が使用される。別の実施形態（より詳細に後述する）では、観測された訓練サンプルの特定のサブセットのみがノード中継分類器に提供される。
【００９８】
後述するように、ノード中継分類器は、選択された各訓練サンプルの観測された出力を、ノード中継分類器によって生成された予測されたノード中継容量と比較することによって訓練される。これらの予測値と観測値との間の「誤差」は、ノード中継分類器が親ノードのノードメトリックとそれらの子ノードに関するそれらのノード中継パフォーマンスとの間の関係を学習するため、加重パラメータを経時的に調整して次第により正確な予測を容易にするために使用される。このようにして、ノード中継分類器は、その親ノードが現在いかなる子ノードも有していないか、またはおそらく有したことがない場合でも、指定された予想親ノードのノード中継容量を予測することができる。
【００９９】
同様に、メトリックプロセッサは、リンク中継分類器への入力として、予想リンクのリンク中継属性を表す１つ以上の「リンクメトリック」、すなわち、そのリンクの子ノードにコンテンツを配信するリンクの能力の指標を生成する。一実施形態では、リンクメトリックは、リンクに沿った往復「ピング」時間、様々なＱｏＥおよびＱｏＳメトリック（レイテンシ、ジッタなど）、ならびにリンクの他のリンク中継属性を含む。他の実施形態では、リンクメトリックは、それらの相対的接続タイプ、アップリンクおよびダウンリンク速度、ＩＰアドレス、ＩＳＰ、ならびにＡＳＮなどの、リンクの親および子に関する相対的ノードメトリックを含む。
【０１００】
リンク中継分類器の訓練に関連して、メトリックプロセッサはまた、そのリンクの観測された現在のリンク中継パフォーマンスを反映する、（例えば、各サンプル時間期間中の）所与のリンクに関する対応する出力も生成する。上述した例では、親ノード（ノードＡ）が同時に５ｍｂｐｓを子ノードＢに配信し、３ｍｂｐｓを子ノードＣに配信した場合、Ａ→Ｃリンクに関連付けられている訓練サンプル出力は３ｍｂｐｓになり、そのリンクの現在のリンク中継パフォーマンスを反映することになる。対応するリンクメトリック入力のセットは、そのＡ→Ｃリンクに関連付けられているリンクメトリックを含むことに留意されたい。この例では、追加の訓練サンプルは、Ａ→Ｂリンクに関連付けられているリンクメトリック入力と、そのＡ→Ｂリンクの現在のリンク中継パフォーマンスに関連する対応する出力（この例では５ｍｂｐｓ）と、を含むことになる。一実施形態（より詳細に後述する）では、観測された訓練サンプルの特定のサブセットのみがリンク中継分類器に提供される。
【０１０１】
予測エンジンのリンク中継分類器は、リンク中継分類器によって生成された予測リンク中継容量が各訓練サンプルの観測された出力と、（次第により正確な予測を容易にするために、経時的に加重パラメータを調整するために使用される２つの間の誤差を使用して）比較されるという点で、ノード中継分類器のものと同様の様式で訓練される。ここでも、リンク中継分類器は、そのリンクの指定された親ノードがそのリンクの指定された子ノードにコンテンツを現在中継していない（またはコンテンツを中継したことがない）場合でも、指定された予想リンクのリンク中継容量を予測することができる。
【０１０２】
ノードおよびリンクのメトリック間の関係、ならびにこのようなノードおよびリンクの「中継パフォーマンス」を経時的に学習することによって、予測エンジンは、現在のネットワーク輻輳の状況にあるか、または将来のネットワーク輻輳の状況にあるかにかかわらず、予想親ノードが１つ以上の子ノードにコンテンツを中継する能力だけでなく、および予想リンクがそのリンクの子ノードにコンテンツを配信する能力も次第に高い精度で予測する。
【０１０３】
ただし、上述したように、個々のノードおよびリンクの実際のパフォーマンスは、特定のオーバーレイネットワークトポロジの構成内での「配置」に依存する。本発明は、指定されたノードおよびリンクの「ローカル」ノード中継容量およびリンク中継容量を入力として受け取り、そして定義されたパフォーマンス基準を満たすオーバーレイネットワークトポロジを出力として生成する「トポロジセレクタ」を提供することによって、代替のオーバーレイネットワークトポロジのノードおよびリンクの間のこれらのパフォーマンス相互依存性を考慮する。
【０１０４】
一実施形態では、トポロジセレクタは、定義されたパフォーマンス基準、および（ネットワークに参加およびネットワークを離脱するときに監視ノードから取得される）現在のオーバーレイネットワークなどの既知の要因から宛先ノードによって課される需要を抽出する。他の実施形態では、このような需要は予測エンジンによって予測される。
【０１０５】
これらの予想ノードおよびリンクの容量および需要の値を取得すると、トポロジセレクタは、既存および予想親ノードの「過剰容量」（すなわち、過剰中継容量）を計算し、オーバーレイネットワークトポロジ全体を通した「グローバル」ベースで満たされない需要を満たすために、そのような過剰容量を再配布し、これによって、定義されたパフォーマンス基準を満たすオーバーレイネットワークトポロジを生成する。より詳細に後述するように、トポロジセレクタは（一実施形態では）、新しいまたはより良い親を必要とする子ノードに過剰容量を効果的に再配布する程度に基づいて、予想オーバーレイネットワークトポロジを評価し、すなわち、パフォーマンス基準を満たすようにネットワークトラフィックをシフトする。
【０１０６】
一実施形態では、トポロジセレクタは、ネットワークトラフィックのシフトおよび結果として生じる過剰容量の再配布を達成するために、様々な変換を実行する。例えば、容量がより大きいノードは、オーバーレイネットワークトポロジのより上位レベルにシフトされ、一方で容量がより小さいノードはより下位レベルにシフトされる。容量が過剰なより大容量のノードは子ノードを追加し、場合によっては、子ノードの需要を満たすことができない親ノードを置き換える。より詳細に後述するように、様々な変換が個々に、組み合わせて、および多くの異なるシーケンスで適用されて同じ目標を達成し、すなわち、パフォーマンス基準を満たすオーバーレイネットワークトポロジを識別する。
【０１０７】
一実施形態では、トポロジセレクタは、パフォーマンス基準を満たす任意のオーバーレイネットワークトポロジを選択する。他の実施形態では、トポロジセレクタは、「最適な」トポロジ、すなわち、パフォーマンス基準を「最も良く満たす」（または別の実施形態では、満たすのに「最も近い」トポロジ）を決定する。より詳細に後述するように、本発明の趣旨から逸脱することなく、様々な線形、非線形、および多次元の最適化技法を使用してもよい。
【０１０８】
さらに他の実施形態では、トポロジセレクタは、予想オーバーレイネットワークトポロジの評価および／または特定の選択されたオーバーレイネットワークトポロジの実装の特定の意図しない「システムレベル」結果を考慮する。言い換えれば、トポロジセレクタは望ましいオーバーレイネットワークトポロジを識別し得るが、このタスクを実行する際に様々なリソースを使用すると、それ自体がマイナスの結果になる場合がある。
【０１０９】
例えば、一実施形態では、現在のオーバーレイネットワークトポロジから多くのリンクを同時に変更するオーバーヘッドは、オーバーレイネットワークトポロジの選択に影響を与える要因である。他の実施形態では、現在のオーバーレイネットワークトポロジが再構成される頻度は別の要因である（再構成を実装する時間自体がネットワークパフォーマンスに影響を与える可能性があるため）。さらに他の実施形態では、トポロジセレクタは、「十分な」または「より良い」トポロジを識別しているにもかかわらず、時間、パフォーマンス、メモリ、および他のリソースの様々なトレードオフの結果として、現在のオーバーレイネットワークトポロジを置き換えない。当業者には明らかであるように、本発明の趣旨から逸脱することなく、様々な他のトレードオフ、最適化、および他の技法を使用してもよい。
【０１１０】
さらに、トポロジセレクタが予想オーバーレイネットワークトポロジの評価を実行する頻度もまた、特定のアプリケーション（またはさらにはコンテンツアイテムもしくはコンテンツアイテムのタイプ）によって変化し得る。いくつかの実施形態では、トポロジセレクタに予想オーバーレイネットワークトポロジを評価させる「トリガ」は時間ベースであり、メトリックが収集される時間期間と相関している。例えば、各１秒間の時間期間の間にメトリックが収集され、トポロジセレクタが現在のオーバーレイネットワークトポロジを置き換えるオーバーレイネットワークトポロジ（存在する場合）を決定する。他の実施形態では、期間は、メトリックが収集される時間期間よりも頻度が少ない。
【０１１１】
さらに他の実施形態では、トリガはイベントベースである。例えば、トポロジセレクタは、現在のオーバーレイネットワークトポロジによってもはや満たされなくなったポイントに近いパフォーマンス基準など、特定の指定されたパフォーマンス閾値が満たされた場合にのみ、オーバーレイネットワークトポロジを評価する。
【０１１２】
上述したように、予測エンジンによって生成されるノード中継容量およびリンク中継容量の予測は、「現在の」または「将来の」ネットワーク輻輳のパフォーマンスに対する影響を反映する。一実施形態では、予測エンジンは、ノード中継容量およびリンク中継容量を将来に向けて複数の時間期間で予測する。例えば、メトリックが１秒ごとに収集される場合、ノード中継容量およびリンク中継容量は将来に向けて１０秒間予測される。他の実施形態では、そのような予測は「現在の」ネットワーク輻輳に基づいており、ノード中継容量およびリンク中継容量は将来に向けて「ゼロ」秒間予測される。
【０１１３】
トポロジセレクタが現在のオーバーレイネットワークトポロジを別のオーバーレイネットワークトポロジで置き換えることを選ぶ場合、現在のコンテンツアイテムの後続のセグメントは、その「新しい現在の」オーバーレイネットワークトポロジが置き換えられるときまで、新しく選択されたオーバーレイネットワークトポロジに従って配布されることになる。
【０１１４】
設計およびエンジニアリング実装のトレードオフ、例えば、コスト、パフォーマンス、時間、および他のリソースなどの要因に対するより良いまたは最適なソリューションのバランスをとることによってもたらされる実施形態を含む、本発明の様々な代替の実施形態が以下により詳細に説明される。一実施形態では、トポロジセレクタは、（閾値パフォーマンス「フロア」に基づいて）新しい親を必要とする個々の子宛先ノードを識別し、次いで、そのようなノードに対する新しい親を選択し、「完全な」置き換えオーバーレイネットワークトポロジを決定するのではなく、現在のオーバーレイネットワークトポロジの一部分を効果的に再構成する。
【０１１５】
要約すると、本発明は以下を提供する。
１．オーバーレイネットワークに沿ったコンテンツアイテムの１つ以上のセグメントの配布に関する１つ以上のアプリケーション固有のパフォーマンス基準のセットを満たすオーバーレイネットワークトポロジを決定するための方法であって、オーバーレイネットワークトポロジが、オーバーレイネットワークの複数のノードおよび複数のリンクを含み、各リンクが、複数のノードのペアを論理的に相互接続して、そのリンクに沿ったノードのペア間の１つ以上のセグメントの配布を容易にし、方法が、
（ａ）連続する時間期間中に複数のメトリックを定期的に測定および処理することであって、各メトリックが、各時間期間の間に、その時間期間中に使用される現在のオーバーレイネットワークトポロジのノードまたはリンクに関連付けられている属性を反映し、処理されたメトリックが、現在のオーバーレイネットワークトポロジのノード中継属性およびリンク中継属性を反映する、測定および処理することと、
（ｂ）予想オーバーレイネットワークトポロジのノードおよびリンクに関連付けられている処理されたメトリックに基づいて、それらのノードおよびリンクのノード中継容量およびリンク中継容量を予測することと、
（ｃ）それらのノードおよびリンクの予測されたノード中継容量およびリンク中継容量に少なくとも部分的に基づいて、予想オーバーレイネットワークトポロジがパフォーマンス基準を満たしているかどうかを決定することと、を含む、方法。
２．コンテンツアイテムがその上に配布されるオーバーレイネットワークトポロジを再構成する方法であって、各オーバーレイネットワークトポロジが、複数のネットワークノード、および複数のネットワークノードを相互接続する複数のリンクを含み、方法が、
（ａ）現在のオーバーレイネットワークトポロジに関する複数のメトリックを生成する工程と、
（ｂ）複数のメトリックに基づいて、指定されたノードおよびリンクのセットに関する複数の予測を生成する工程と、
（ｃ）複数の予測に基づいて予想オーバーレイネットワークトポロジを識別する工程と、を含む、方法。
３．予想オーバーレイネットワークトポロジが、指定されたノードおよびリンクのパフォーマンスに関する１つ以上の制約を表すパフォーマンス基準を満たす、請求項２に記載の方法。
４．各オーバーレイネットワークトポロジが、ピアベースのオーバーレイネットワークトポロジである、請求項２に記載の方法。
５．各ネットワークノードが予想オーバーレイネットワークトポロジの一部となるかどうかを示す視聴者指標予測を生成する工程をさらに含む、請求項２に記載の方法。
６．予想オーバーレイネットワークトポロジの一部となるそれらのネットワークノードが、予想オーバーレイネットワークトポロジの一部のままとなる間の時間の継続期間を示すセッション継続期間予測を生成する工程をさらに含む、請求項５に記載の方法。
７．複数の予測が、指定されたノードのノード中継容量および指定されたリンクのリンク中継容量の予測を含む、請求項２に記載の方法。
８．複数のメトリックが、ノードメトリック、リンクメトリック、ならびにノードメトリックおよびリンクメトリックが取得される間のタイムスタンプを含む、請求項２に記載の方法。
９．コンテンツアイテムがその上に配布されるオーバーレイネットワークトポロジを再構成する適応トポロジサーバであって、各オーバーレイネットワークトポロジが、複数のネットワークノード、および複数のネットワークノードを相互接続する複数のリンクを含み、適応トポロジサーバが、
（ａ）現在のオーバーレイネットワークトポロジに関する複数のメトリックを生成するメトリックプロセッサと、
（ｂ）複数のメトリックに基づいて、指定されたノードおよびリンクのセットに関する複数の予測を生成する予測エンジンと、
（ｃ）予測エンジンから、指定されたノードおよびリンクのセットに関する複数の予測を取得し、かつ複数の予測に基づいて予想オーバーレイネットワークトポロジを識別する、トポロジセレクタと、を備える、適応トポロジサーバ。
１０．トポロジセレクタが、１つ以上のパフォーマンス制約を表すパフォーマンス基準を満たす予想オーバーレイネットワークトポロジを識別する、請求項９に記載の適応トポロジサーバ。
１１．各オーバーレイネットワークトポロジが、ピアベースのオーバーレイネットワークトポロジである、請求項９に記載の適応トポロジサーバ。
１２．予測エンジンが、各ネットワークノードが予想オーバーレイネットワークトポロジの一部となるかどうかを示す視聴者指標予測を生成する、請求項９に記載の適応トポロジサーバ。
１３．予測エンジンが、予想オーバーレイネットワークトポロジの一部となるそれらのネットワークノードが、予想オーバーレイネットワークトポロジの一部のままとなる間の時間の継続期間を示すセッション継続期間予測を生成する、請求項１２に記載の適応トポロジサーバ。
１４．予測エンジンが、指定されたノードのノード中継容量および指定されたリンクのリンク中継容量を生成する、請求項９に記載の適応トポロジサーバ。
１５．メトリックプロセッサによって生成された複数のメトリックが、ノードメトリック、リンクメトリック、ならびにノードメトリックおよびリンクメトリックがその間に取得されるタイムスタンプを含む、請求項９に記載の適応トポロジサーバ。
１６．それぞれのオーバーレイネットワークトポロジに沿って複数のコンテンツアイテムを同時に配布するための方法であって、各オーバーレイネットワークトポロジが、複数のネットワークノード、および複数のネットワークノードを相互接続する複数のリンクを含み、方法が、
（ａ）第１のオーバーレイネットワークトポロジに沿って第１のコンテンツアイテムを配布する工程と、
（ｂ）第２のオーバーレイネットワークトポロジに沿って第２のコンテンツアイテムを配布する工程であって、第１のコンテンツアイテムおよび第２のコンテンツアイテムが、それらのそれぞれのオーバーレイネットワークトポロジに沿って同時に配布される、工程と、
（ｃ）第１のオーバーレイネットワークトポロジに沿ってネットワークノードに第１のコンテンツアイテムを配布する工程であって、ネットワークノードが、第１のオーバーレイネットワークトポロジおよび第２のオーバーレイネットワークトポロジの両方に含まれ、ネットワークノードが、第１のコンテンツアイテムを消費する、工程と、
（ｄ）第２のオーバーレイネットワークトポロジに沿ってネットワークノードに第２のコンテンツアイテムを配布する工程であって、ネットワークノードが、第２のオーバーレイネットワークトポロジの別のネットワークノードに第２のコンテンツアイテムを中継する、工程と、を含む、方法。
【図面の簡単な説明】
【０１１６】
【図１Ａ】本発明の下位ネットワーク（すなわち、インターネット）のネットワークアーキテクチャの一実施形態を例示する図表であり、特定のネットワークアプリケーションに参加するユーザノードのセットを含む。
【図１Ｂ】図１Ａの下位ネットワークの上に構築されたエッジベースのオーバーレイネットワーク（コンテンツデリバリネットワークまたは「ＣＤＮ」）のネットワークアーキテクチャの一実施形態を例示する図表であり、ここでコンテンツは、エッジベースのオーバーレイネットワークのオーバーレイノード（エッジサーバ）間のＣＤＮ経路に沿って宛先ユーザノードに配布される。
【図１Ｃ】図１Ａの下位ネットワークの上に構築されたピアベースのオーバーレイネットワークのネットワークアーキテクチャの一実施形態を例示する図表であり、ここでコンテンツは、ピアベースのオーバーレイネットワークのオーバーレイノード（「ピア」宛先ユーザノード）間のオーバーレイ経路に沿って宛先ユーザノードに配布される。
【図２Ａ】本発明のピアベースのオーバーレイネットワークのオーバーレイネットワークトポロジの一実施形態を例示する図表であり、単に「子」宛先ノードであるピアノード、およびコンテンツを他のピアノードに中継する「親」ノードでもあるピアノードを含む。
【図２Ｂ】本発明の複数の相互接続されたピアベースのオーバーレイネットワークトポロジの一実施形態を例示する図表であり、第１のオーバーレイネットワークのコンテンツをその第１のオーバーレイネットワークの他のピアノードに中継するが、そのようなコンテンツを消費しない少なくとも１つのピアノードを含む。
【図２Ｃ】本発明のピアベースのオーバーレイネットワークトポロジのサブセットの一実施形態の「スナップショットの前後」を例示する図表であり、ここで現在のオーバーレイネットワークトポロジは、監視されたメトリックに部分的に基づいて再構成される。
【図３Ａ】本発明の主要なクライアントサーバ構成要素の一実施形態を例示するシステム図である。
【図３Ｂ】本発明のユーザノードデバイスの主要なクライアント側構成要素の一実施形態を例示するブロック図である。
【図３Ｃ】本発明の適応トポロジサーバの主要なサーバ側構成要素の一実施形態を例示するブロック図である。
【図４Ａ】図３Ｃに例示される「オーバーレイネットワークトポロジマネージャ」の「予測エンジン」および「トポロジセレクタ」構成要素の高レベルの実施形態を例示する図である。
【図４Ｂ】図３Ｃに例示される「オーバーレイネットワークトポロジマネージャ」の「メトリックプロセッサ」、「予測エンジン」および「トポロジセレクタ」構成要素間の動的な相互作用の高レベルの実施形態を例示するフロー図である。
【図５】下位ネットワーク輻輳の影響のメトリック指標の変化、ならびに現在のオーバーレイネットワークトポロジのノードおよびリンクの相互依存性に応じて、アプリケーション固有のパフォーマンス基準を満たすオーバーレイネットワークトポロジを決定する、本発明の重要なプロセスの一実施形態のシステムレベルのフロー図である。
【図６Ａ】１つ以上の子ノードにコンテンツを中継する指定された親ノードのノード中継容量を予測する、本発明のノード中継分類器のニューラルネットワーク実装の入力および出力ノードの一実施形態の図である。
【図６Ｂ】そのリンクの親ノードからそのリンクの指定された子ノードにコンテンツを中継するための、指定されたリンクのリンク中継容量を予測する、本発明のリンク中継分類器のニューラルネットワーク実装の入力および出力ノードの一実施形態の図である。
【図７Ａ】図３Ｃに例示されるオーバーレイネットワークトポロジマネージャのトポロジセレクタ構成要素による初期構成に続くオーバーレイネットワークトポロジの状態の一実施形態を例示する図表である。
【図７Ｂ】図３Ｃに例示されるオーバーレイネットワークトポロジマネージャのトポロジセレクタ構成要素による「低パフォーマンス」変換に続くオーバーレイネットワークトポロジの状態の一実施形態を例示する図表である。
【図７Ｃ】図３Ｃに例示されるオーバーレイネットワークトポロジマネージャのトポロジセレクタ構成要素による「レベルシフト」変換に続くオーバーレイネットワークトポロジの状態の一実施形態を例示する図表である。
【図７Ｄ】図３Ｃに例示されるオーバーレイネットワークトポロジマネージャのトポロジセレクタ構成要素による「過剰容量の再配布」変換に続くオーバーレイネットワークトポロジの状態の一実施形態を例示する図表である。
【図７Ｅ】図３Ｃに例示されるオーバーレイネットワークトポロジマネージャのトポロジセレクタ構成要素によって実行される初期構成および再構成変換の一実施形態を例示するフロー図である。
【図７Ｆ】図３Ｃに例示されるオーバーレイネットワークトポロジマネージャのトポロジセレクタ構成要素の主要な工程の代替の実施形態を例示するフロー図であり、ここで新しい孤立した低パフォーマンスノードは、現在のオーバーレイネットワークトポロジの「ローカル」再構成を容易にするために、新しい親を必要とするものとして識別される。
【発明を実施するための形態】
【０１１７】
Ａ．はじめに
より詳細に後述するように、本発明は、インターネットなどの下位ネットワークのノード間でのコンテンツアイテムの配布を対象とする。本発明の予測的なオーバーレイネットワークアーキテクチャの実施形態は、インターネットの上に構築されたピアベースのオーバーレイネットワークの状況で本明細書に記載されているが、本発明は、ピアベースのオーバーレイネットワークに、またはさらにはインターネットに限定されないことが強調されるべきである。明らかになるであろうように、本発明は、中間ルーティングノードおよび他の共有リソースにおいてネットワーク輻輳を経験する実質的にあらゆる下位ネットワークの上に構築されるエッジベースのおよび他のオーバーレイアーキテクチャに統合することができる。
【０１１８】
上記で示唆したように、（下位ネットワークの中間ルーティングノードとは区別される）アプリケーションのコンテンツを消費するユーザノードのセットは、アプリケーションのコンテンツアイテムが配布されるオーバーレイネットワークを一緒に定義するオーバーレイノードを表す。任意の所与のコンテンツアイテム（またはそのセグメント）について、本発明は、そのコンテンツアイテムを消費するオーバーレイノードのセット（オーバーレイネットワーク）を含む対応するオーバーレイネットワークトポロジ、および（本発明がオーバーレイネットワークトポロジを再構成する時点まで）コンテンツアイテムのセグメントがこれに沿って伝播することになるリンクのセット（オーバーレイノードのペア）を定義する。
【０１１９】
より詳細に後述する一実施形態では、１つ以上のユーザノードは、複数のオーバーレイネットワークの一部であり、したがって、特定のコンテンツアイテムを中継するが消費しない場合がある。しかし、その実施形態では、そのようなユーザノードは、それらが一部である重複するオーバーレイネットワークトポロジを介して他のコンテンツアイテムを消費する。本発明の範囲が、１つ以上のアプリケーションに関連付けられている（各々が対応するオーバーレイネットワークトポロジを有する）複数のコンテンツアイテムの同時配布を含むことは、当業者には明らかであろう。
【０１２０】
後述する本発明の予測的なオーバーレイネットワークアーキテクチャの実施形態は、アプリケーション固有のパフォーマンス基準のセットを満たすオーバーレイネットワークトポロジを識別する。各アプリケーション（および潜在的に各コンテンツアイテムまたはそのセグメント）は、独自の関連オーバーレイネットワークトポロジを有している場合があるため、本発明は、別個の（および潜在的に重複する）オーバーレイネットワークトポロジを定義することができ、オーバーレイネットワークトポロジの各々は、独自の定義されたパフォーマンス基準を有する特定のアプリケーション（またはコンテンツアイテムもしくはそのセグメント）に関連付けられている。例えば、ビデオコンテンツアイテムの異なる解像度は、本発明の目的のために別個のコンテンツアイテムとみなすことができる。
【０１２１】
しかしながら、簡単のために、本明細書に記載する実施形態のほとんどは、単一のコンテンツアイテムのセグメントを配布する単一のアプリケーションに関連付けられている単一のオーバーレイネットワークトポロジを決定する。それでも、任意の所与のオーバーレイネットワークトポロジが複数のコンテンツアイテムを同時に配布する複数のアプリケーションに対応し得ること、および本発明の趣旨から逸脱することなく、各アプリケーション（またはコンテンツアイテムもしくはそのセグメント）ごとに別個のオーバーレイネットワークトポロジを定義し得ることは、当業者には明らかである。
【０１２２】
本明細書で提供される例の多くは、インターネットを介して多数の同時ユーザにストリーミングビデオを配信する状況で記載されているが、本発明の原理は、実質的にあらゆるタイプのデジタルコンテンツを配布するあらゆるタイプのアプリケーションに等しく適用される。アプリケーションの例としては、ブロードキャストビデオ、ＶＯＤ、ＶｏＩＰ、およびその他の形式のビデオ会議、オーディオおよびビデオストリーミング、仮想現実（「ＶＲ」）、シングルプレイヤーおよびマルチプレイヤーゲーム、大容量ファイル転送、ならびにその他の様々なコンテンツ配布（およびしばしば、比較的帯域幅が集約した）アプリケーションが挙げられる。デジタルコンテンツアイテムの例としては、テキスト、画像、オーディオおよび／またはビデオファイル、３Ｄモデル、ＶＲゲームプレイ、医療データ、ならびに実質的にあらゆる他の形式のデジタルコンテンツが挙げられる。
【０１２３】
本発明は、スケジュールされた時間に配布されるコンテンツアイテムに限定されないことにさらに留意されたい。例えば、ビデオコンテンツは、イベントが発生したときにライブでストリーミングされてもよく（リアルタイムでストリーミングされるか、またはいくらかの期間遅延してストリーミングされるかにかかわらず）、または事前に録画されて後でストリーミングされてもよい。イベント自体は、事前にスケジュールされてもよく、されなくてもよい。さらに、アプリケーションおよびそれに関連するパフォーマンス基準は、宛先ノードがコンテンツアイテムを「同時に」（すなわち、事前定義された閾値時間期間内に）受信しなければならないか、または同じコンテンツを異なる時間に受信してもよいかを決定することになる。
【０１２４】
以下で明らかになるように、本発明は、インターネットのネットワーク輻輳問題、またはアプリケーション固有のパフォーマンス基準に従ってコンテンツを配布するためのオーバーレイネットワークのノードおよびリンクの制限された容量を「治療」しない。代わりに、制限された容量を効率的に使用し、定義されたパフォーマンス基準をすべて満たしつつ、（ネットワーク輻輳を「迂回」することによって効果的に低減し、かつインターネットの頻繁に使用されないか、または混雑していない領域全体を通してトラフィックを分散することによって）それらのオーバーレイネットワークトポロジのパフォーマンスに対する下位ネットワーク輻輳の悪影響を低減する、オーバーレイネットワークトポロジを経時的に定義する。
【０１２５】
本発明の１つの主要な利点は、帯域幅コスト、および挿入ポイント（「ＰＯＩ」）、すなわち、コンテンツがそこから発信されるネットワークノード（または外部ネットワーク）に対する影響の減少である。例えば、宛先ピアノードを活用して、それらの間でコンテンツアイテムを配信することによって、本発明は、コンテンツアイテムの配布のための高価なエッジベースのルータおよびサーバの必要性を回避する。関連する利点としては、ＰＯＩの直接の到達範囲をはるかに超えるユーザノード（例えば、ＰＯＩに、またはおそらく比較的高い帯域幅の任意のユーザノードに対するネットワーク近接度がない場合）に対してさえ、サービス範囲およびパフォーマンス品質の向上が挙げられる。他の利点は、本発明の様々な実施形態の以下の説明に関連して明らかになるであろう。
【０１２６】
最後に、以下の実施形態が、様々な設計およびエンジニアリングのトレードオフ（時間、パフォーマンス、メモリ、およびその他の要因を含む）の結果であるハードウェアおよびソフトウェア構成要素間の機能の割り当てを表すことが強調されるべきである。この機能は、本発明の趣旨および範囲を逸脱することなく、ハードウェアおよびソフトウェア、クライアント側およびサーバ側のモジュールの間で再割り当てし、単一の構成要素に結合し、または複数の構成要素の間で分割し、かつ標準およびカスタムネットワークプロトコルの組み合わせで実装することができる。
【０１２７】
Ｂ．ピアベースのオーバーレイネットワークトポロジ
図２Ａに目を向けると、図表２００ａは、本発明のピアベースのオーバーレイネットワークトポロジの一実施形態を例示する。ソースノード２２０ａは、ＰＯＩ、すなわちコンテンツアイテムがそこで発信し、かつコンテンツアイテムがそこでオーバーレイネットワークの中へと挿入されるポイントを表す。他の実施形態では、コンテンツは、オーバーレイネットワーク自体の内部へか、またはオーバーレイネットワーク自体から外部へかにかかわらず、複数の異なるノードから発信することができる。外部の「ソース」ネットワークまたはノード（すなわち、オーバーレイネットワークの一部ではなく、コンテンツアイテムを消費しないノード）もまた、オーバーレイネットワークの１つ以上のピアユーザノードにコンテンツアイテムを配布し得る。
【０１２８】
図２Ａに示される実施形態では、ソースノード２２０ａは、（現在のオーバーレイネットワークトポロジ２００ａの定義に従って）最初にコンテンツのセグメントを複数のピアノード２３０ａに直接配布する外部ノードを表す。ピアノード２３０ａは、単に子ノードにすぎないピアノード（コンテンツを消費するが、そのコンテンツを任意の他のピアノードに中継しない「リーフ」ノード２３０ａ−２など）だけでなく、親ノードであるピアノード（コンテンツを消費するだけでなく、そのコンテンツを他のピアノードに中継する「中継」ノード２３０ａ−１など）も含む。
【０１２９】
図２Ｂに目を向けると、図表２００ｂは、本発明の複数の重複しているかまたは相互接続されたピアベースのオーバーレイネットワークトポロジの一実施形態を例示する。この実施形態では、第１のコンテンツアイテムは、その第１のコンテンツアイテムのセグメントを消費する複数のピアノード２３０ｂ−１の第１のオーバーレイネットワーク間でソースノード２２０ｂ−１から配布される。同様に、第２のコンテンツアイテムは、ソースノード２２０ｂ−２から、その第２のコンテンツアイテムのセグメントを消費する複数のピアノード２３０ｂ−２の第２のオーバーレイネットワーク間で配布される。
【０１３０】
しかし、この実施形態では、第２のオーバーレイネットワークのノードのうちの１つ（ピアノード２４０ｂ−２）は、第２のコンテンツアイテムのセグメントを消費し、それらのセグメントを第２のオーバーレイネットワークの他のピアノード２３０ｂ−２へと中継するだけでなく、第１のコンテンツアイテムのセグメントを、第１のオーバーレイネットワークの他のピアノード２３０ｂ−１へと中継する。言い換えれば、この実施形態では、ピアノード２４０ｂ−２は、様々な点で（他のピアノード２３０ｂ−１および２３０ｂ−２とは対照的に）異常なノードである。
【０１３１】
それは、複数の（２つの）親ノードを有し、消費しないコンテンツアイテム（第１のコンテンツアイテム）のセグメントを中継する（第２のコンテンツアイテムのセグメントのみを消費するため）。したがって、このシナリオでは、ピアノード２４０ｂ−２は、複数の別個のピアベースのオーバーレイネットワークの一部である。
【０１３２】
この実施形態の１つの目的は、より効率的なオーバーレイネットワークトポロジを「生成」するために、本発明が、配布されるコンテンツを消費しないピアノードの未使用または過剰の「中継容量」を活用する方法を例示することである。ただし、ピアノード２４０ｂ−２は、エッジサーバノードとは異なり、追加の物理インフラストラクチャの購入またはリースを必要としないことに留意されたい。そうではなく、ピアノード２４０ｂ−２は、（第２のオーバーレイネットワークの）コンテンツアイテムを消費するために既に展開されているユーザノードである。
【０１３３】
以下により詳細に説明するように、本発明は、経時的に（潜在的に複数のオーバーレイネットワークトポロジにわたる）ユーザノード間でのコンテンツの配布に関与するものを含む様々なメトリックを監視し、ひいては第１のオーバーレイネットワークのピアノード間で配布されるコンテンツアイテムのセグメントに対するオーバーレイネットワークトポロジ内のノード２４０ｂ−２を含めることによる、この過剰中継容量を検出（または予測）および活用することができる。重複するオーバーレイネットワークトポロジのこの概念の変形形態（ＣＤＮおよび他のエッジベースのオーバーレイネットワークを統合するハイブリッドネットワークアーキテクチャを含む）は、当業者には明らかであろう。
【０１３４】
最後に、図２Ａおよび図２Ｂに例示されるオーバーレイネットワークトポロジは、所与の時点で本発明によって定義されるオーバーレイネットワークトポロジを表すことに留意されたい。言い換えれば、メトリックが経時的に変化するのに従い、本発明は、現在のオーバーレイネットワークトポロジを置き換えるために、新しいまたは修正されたオーバーレイネットワークトポロジを決定してもよい。
【０１３５】
図２Ｃに目を向けると、図表２００ｃは、現在のオーバーレイネットワークトポロジ２１０ｃがここで（部分的または完全に）監視されたメトリックに基づいて再構成された、本発明のピアベースのオーバーレイネットワークトポロジのサブセットの一実施形態の「スナップショットの前後」を例示しており、結果として新しい「置き換え」オーバーレイネットワークトポロジ２２０ｃがもたらされ、それに沿ってコンテンツアイテムの将来のセグメントが伝播されることになる。より詳細に後述するように、再構成は様々な理由で発生する場合がある。
【０１３６】
例えば、メトリックは経時的に変化し、特定のノードまたはリンクのパフォーマンスが低下している（または低下するであろう）ことを示す。ただし、上記で示唆したように、「パフォーマンスの低い」親ノードまたはリンクを単に置き換えるだけでは、アップストリームノードおよびリンクの相互依存性の影響も考慮せずには、所望の結果（すなわち、定義されたパフォーマンス基準を満たすこと）を達成できないことがある。
【０１３７】
本発明がこれらの問題を解決する（それらの相互依存性だけでなく、現在または将来の下位ネットワーク輻輳の影響にも対処する）様式は一旦置いておいて、図２Ｃは（少なくともノードおよびリンクのサブセットに対する）再構成プロセスの「前後」の影響を例示する。これらの影響は、再構成されたオーバーレイネットワークトポロジ２２０ｃの「後」のリンク２２５ｃのセットとは対照的に、現在のオーバーレイネットワークトポロジ２１０ｃの「前」のリンク２１５ｃのセットによって例示される。
【０１３８】
図２Ｃに例示される例では、ピアノードＸは、ある時点でアプリケーションに参加して特定のコンテンツアイテムを受信する要求を開始する。その時点で、要求されたコンテンツアイテムを受信するためにノードＸに親ピアノードが割り当てられることになる（ただし、後述する一部の実施形態では、ノードＸは、親ピアノードが割り当てられるまで、ＰＯＩ（２２０ｃのＳＲＣノード）から即座にコンテンツを受信し始める）。
【０１３９】
以下により詳細に説明するように、本発明は、新しい親をノードＸにランダムに、またはさらには相対的な地理的位置のみに基づいて割り当てる必要はない。代わりに、結果として生じるオーバーレイネットワークトポロジのパフォーマンス全体（または、一部の実施形態では、ノードＸへのリンクのパフォーマンスのみ）が定義されたアプリケーション固有のパフォーマンス基準を満たすように、ノードＸに対する親を選択する際に様々なメトリックを考慮する。いずれにしても、このプロセスの結果として、２２５ｃおよび再構成されたオーバーレイネットワークトポロジ２２０ｃに示されているＡ→Ｘリンクによって例示されるように、新しいノードＸに親ノードＡが割り当てられる。
【０１４０】
アプリケーションに参加する新しいノードに加えて、本発明は、アプリケーションを離れるノード（特に、「孤立した」子ノードを後に残す親ノード）に対応しなければならない。この例では、ノードＦはアプリケーションを離れ、孤立したノードＮおよびＯを後に残す。ここでも、以下により詳細に説明するように、本発明は、これらの孤立したノードの新しい親を選択する際に様々なメトリックを考慮する。したがって、２１５ｃ（および現在のオーバーレイネットワークトポロジ２１０ｃ）に示されるリンクＦ→ＮおよびＦ→Ｏは、２２５ｃおよび再構成されたオーバーレイネットワークトポロジ２２０ｃに示されるリンクＧ→ＮおよびＧ→Ｏによって効果的に置き換えられる。その結果、親ノードＧには、ここでは３つの子ノード、つまり、孤立したノードＮおよびＯ、ならびに既存の子ノードＰができる。
【０１４１】
新しいノードおよび孤立したノードの親ノードを選択する状況でも、本発明は、メトリックの変更を考慮して、現在のオーバーレイネットワークトポロジを再構成するかどうか、およびどのように再構成するかを決定することを強調することが重要である。言い換えれば（以下により詳細に説明するように）、本発明は、頻繁に変化する下位ネットワーク輻輳の結果、ならびにオーバーレイネットワークトポロジのノードおよびリンクの間の相互依存性に対処する。
【０１４２】
したがって、新しいノードおよび孤立したノードに対応することに加えて、本発明は、定義されたパフォーマンス基準を満たしつつ、現在のオーバーレイネットワークトポロジを再構成することによって、（観測された、かつ／または予想の）「低パフォーマンス」ノードおよびリンクに対処する。図２Ｃに示される例では、２１５ｃ（および現在のオーバーレイネットワークトポロジ２１０ｃ）のＨ→ＲおよびＫ→Ｖリンクは「低パフォーマンス」、例えば、事前定義された閾値を下回るか、または定義されたパフォーマンス基準で必要とされる閾値を下回るパフォーマンスレベルを示している（または示すと予測される）。
【０１４３】
上記で示唆したように、低パフォーマンスの原因は、内部の問題またはノード（ノードＲもしくはノードＶ）自体の中の輻輳、あるいはそれらのノードへのリンク（Ｈ→ＲまたはＫ→Ｖ）に沿った中間ルーティングノードでのアップストリームネットワーク輻輳であり得る。以下により詳細に説明するように、問題の正確な原因が分からなくても、本発明は、パフォーマンス基準を満たすオーバーレイネットワークトポロジを識別し、それにより、下位ネットワーク輻輳を効果的に「迂回」および低減する。
【０１４４】
したがって、この例では、２１５ｃ（および現在のオーバーレイネットワークトポロジ２１０ｃ）に示すように、「低パフォーマンス」問題の原因が既存のノードＲであるか、かつ／もしくはＶ（または既存のリンクＨ→Ｒおよび／もしくはＫ→Ｖ）であるかにかかわらず、本発明は、２２５ｃにも示すように、子ノードＲに新しい親ノードＩを、かつ子ノードＶに新しい親ノードＭを結果として提供する新しいオーバーレイネットワークトポロジ２２０ｃを識別することによって、現在のオーバーレイネットワークトポロジ２１０ｃを再構成した。
【０１４５】
いくつかの実施形態（後述する）では、本発明は最初に（新しい親を必要とするような）「低パフォーマンス」ノードを明示的に識別するが、他の実施形態では、新しい親の割り当ては、（特定の「低パフォーマンス」ノードを明示的に識別することなく）パフォーマンス基準を満たすオーバーレイネットワークトポロジの識別の結果である。
【０１４６】
Ｃ．クライアントサーバアーキテクチャおよび主要な機能コンポーネント
本発明の予測的なオーバーレイネットワークアーキテクチャの一実施形態では、図３Ａのシステム図３００ａに示されるように、クライアントサーバアーキテクチャが使用される。この実施形態では、適応トポロジサーバ３１０ａは、本発明の機能の多くを集中化する、下位ネットワーク３２５ａ（インターネット）上の１つのノード（または他の実施形態では複数のノード）である。
【０１４７】
例えば、適応トポロジサーバ３１０ａは、同時に実行されている１つ以上のアプリケーションだけでなく、ユーザノードデバイス３２０ａ間の情報がその上で交換されるオーバーレイネットワークトポロジを管理することを担う。ユーザノードデバイス３２０ａの各々はまた、インターネット３２５ａの下位ノードとしても接続されている。
【０１４８】
各アプリケーションは、論理的に相互接続されたオーバーレイネットワークトポロジ３２０ａ−１として集合的に例示される、ユーザノードデバイス３２０ａのサブセットの参加に関与する。３２０ａ−１に示される「ＳＲＣ」ノードは、技術的にはオーバーレイネットワークトポロジの一部ではない。これは、各コンテンツアイテムのＰＯＩまたはソースを表す。図３Ａには特に示されていないが、（複数のアプリケーションおよびコンテンツアイテムにわたる）１つ以上のＰＯＩは、一実施形態では、下位ネットワーク（インターネット３２５ａ）上の外部ノードとして展開され、適応トポロジサーバ３１０ａおよびユーザノードデバイス３２０ａと通信するように適応される。この実施形態では、適応トポロジサーバ３１０ａは、そのＰＯＩから各オーバーレイネットワークトポロジ３２０ａ−１の「ルート」ノードへの各コンテンツアイテムのセグメントの配布を管理する（この時点で、これらのセグメントは、より詳細に後述するように、オーバーレイネットワークトポロジ３２０ａ−１に沿って他のユーザノードデバイス３２０ａへとさらに配布される）。
【０１４９】
一実施形態では、オーバーレイネットワークトポロジ３２０ａ−１は、その各々が１つ以上のコンテンツアイテムの同時配布に関与する複数のアプリケーションに関してコンテンツを配布するために使用される。他の実施形態では、各個々のコンテンツアイテムの各セグメントは、別個のオーバーレイネットワークトポロジに沿って配布されてもよい。
【０１５０】
個々のセグメントを有するオーバーレイネットワークトポロジ３２０ａ−１、コンテンツアイテム、およびアプリケーションのこの相関の粒度は、本発明を実施する過程で行われた設計およびエンジニアリングのトレードオフの結果である。簡単のために、オーバーレイネットワークトポロジ３２０ａ−１は、特定のアプリケーションのコンテンツアイテムのセグメントの配布に関与するユーザノードデバイス３２０ａのサブセットを参照して、この状況では低レベルの粒度で記載される。
【０１５１】
この実施形態では、ユーザノードデバイス３２０ａは、経時的にメトリックを収集し、それらをインターネット３２５ａを介して適応トポロジサーバ３１０へと連続的に配信し、適応トポロジサーバ３１０は、いずれかの特定のオーバーレイネットワークトポロジ３２０ａ−１を再構成するかどうかに関する決定を（それらのメトリックに少なくとも部分的に基づいて）行う。適応トポロジサーバ３１０ａが特定のオーバーレイネットワークトポロジ３２０ａ−１を再構成するたびに、（そのトポロジ３２０ａ−１内の）各親ユーザノードデバイス３２０ａに、現在のコンテンツアイテムの後続のセグメントを「プッシュ」することになる子ユーザノードデバイス３２０ａの識別情報を通信する。
【０１５２】
各子ユーザノードデバイス３２０ａは、コンテンツアイテムのセグメントを受信および消費する機能、例えば、ストリーミングビデオコンテンツのセグメントの受信および視聴、画像ファイルの受信および処理、インタラクティブなゲームプレイデータの受信および処理などを含む。ユーザノードデバイス３２０ａが、親ノードでもある場合、コンテンツアイテムのセグメントを受信および消費するだけでなく、適応トポロジサーバ３１０ａによって指定された特定のユーザノードデバイス３２０ａへのこれらのセグメントの中継も行う。言い換えれば、ユーザノードデバイス３２０ａは、適応トポロジサーバ３１０ａによって決定され、かつ経時的に再構成されるオーバーレイネットワークトポロジ３２０ａ−１上でコンテンツの配布を実施する。
【０１５３】
ユーザノードデバイス３００ｂの機能構成要素のより詳細な説明が図３Ｂに例示される。一実施形態では、各ユーザノードデバイス３００ｂは、スタンドアロンおよびネットワークアプリケーションの機能を実装するために、ＣＰＵ３１２ｂ、メモリ３１４ｂ、およびオペレーティングシステム３１５ｂ、ならびにネットワークアダプタ３１６ｂを含む標準ハードウェアおよびソフトウェア構成要素３１０ｂを含む。他の実施形態では、この機能は、完全にハードウェア内で、または汎用ＣＰＵ３１２ｂおよびオペレーティングシステム３１５ｂではなく、１つ以上の専用マイクロコントローラの使用によるだけでなく、複数の（シングルまたはマルチコア）ＣＰＵ３１２ｂでも実装することができる。いくつかの実施形態では、特定のユーザノードデバイス３００ｂはまた、ディスプレイ、キーボード、カメラなどのＩ／Ｏデバイス３１８ｂも含む。
【０１５４】
これらの標準ハードウェアおよびソフトウェア構成要素３１０ｂの機能は、本発明の予測的なオーバーレイネットワークアーキテクチャによって活用される一方で、ユーザノードデバイス３００ｂ自体による汎用使用にも使用されている。例えば、メモリ３１４ｂはまた、いくつかの実施形態では、メトリックの収集、ならびにコンテンツアイテムのセグメントの受信、消費、および中継に関連する適応トポロジサーバ３１０ａとの通信など、本発明の特定のクライアント側機能を実装するカスタムソフトウェア（例えば、適応トポロジサーバ３１０ａから受信したジャバスクリプトコード）を記憶するためにも使用される。他の実施形態では、ユーザノードデバイス３００ｂは、この機能を容易にするためのデータおよびソフトウェアを記憶するための別個の記憶構成要素を含む。
【０１５５】
いずれにせよ、本発明のクライアント側機能は、ハードウェアに実装されていない限りにおいて、非一時的なコンピュータアクセス可能な記憶媒体（メモリ３１４ｂまたは他の形式のデータ記憶装置など）で具現化され、処理装置（ＣＰＵ３１２ｂなど）によって実行される。他の実施形態では、このクライアント側機能は、デスクトップアプリケーションおよびユーザノードデバイス３００ｂへとダウンロードされたモバイルアプリで具現化される。
【０１５６】
このカスタムクライアント側機能はまた、標準ライブラリモジュール３２０ｂによっても（一部の実施形態では）容易にされる。この標準ライブラリモジュール３２０ｂは、適応トポロジサーバ３１０ａと通信し、かつコンテンツアイテムのセグメントを受信、消費、および中継するための標準プロトコルおよびライブラリを含む。このようなプロトコルおよびライブラリの例としては、数ある中でも、ＨＴＴＰ、ＷｅｂＳｏｃｋｅｔ、ＳＴＵＮ、ＷｅｂＲＴＣ、ＭＰＥＧ−ＤＡＳＨなどが挙げられる。標準ライブラリモジュール３２０ｂ内の特定の標準プロトコルおよびライブラリ（ならびに非標準プロトコルおよびライブラリ）の選択は、本発明の範囲内の様々な設計およびエンジニアリングのトレードオフの結果である。
【０１５７】
上記で示唆したように、ユーザノードデバイス３００ｂは、いくつかの実施形態では、他のユーザノードデバイス３００ｂに配布される特定のコンテンツアイテムのソースであり得る。このシナリオでは、アップローダ３８０ｂは、コンテンツアイテムの各セグメントを適応トポロジサーバ３１０ａによって指定されたクライアントユーザノードデバイス３００ｂにストリーミングするか、またはその他の方法で配布する機能を実装する。一実施形態では、ノードデバイス３００ｂは、コンテンツアイテムのソースであることに加えて、他のコンテンツアイテムのセグメントの消費および中継も行う（受信機３５０ｂおよびリレイヤ３６０ｂを利用する）。
【０１５８】
この状況では、結果としてもたらされるオーバーレイネットワークトポロジ（このようなコンテンツアイテムの任意のセグメントがこれに沿って配布される）は、コンテンツアイテムのＰＯＩまたはソースであるため、その「ソース」ユーザノードデバイス３００ｂは含まない。しかし、上述したように、同じユーザノードデバイス３００ｂは、（例えば、上述した図２ｂのユーザノード２４０ｂ−２によって示されるように）異なるコンテンツアイテムがその上に配布される別個の（かつおそらく重複する）オーバーレイネットワークトポロジの一部であってもよい。
【０１５９】
適応トポロジサーバ３１０ａとの通信は、コミュニケータモジュール３３０ｂによって実施される。例えば、コミュニケータ３３０ｂは、オーバーレイネットワークトポロジの決定に使用するために、メトリックモニタ３４０ｂによって収集されたメトリックを適応トポロジサーバ３１０ａに送信する。コミュニケータ３３０ｂはまた、適応トポロジサーバ３１０ａから、（例えば、適応トポロジサーバ３１０ａがオーバーレイネットワークトポロジを再構成する場合に）ユーザノードデバイス３００ｂがコンテンツアイテムの後続のセグメントを中継することになる子ノードの仕様（存在する場合）を受信する。さらに、コミュニケータ３３０ｂは、他の通信関連機能の中でも、特定のアプリケーションに参加またはそれから離脱するユーザノードデバイス３００ｂによる要求を取り扱う。
【０１６０】
一実施形態では、メトリックモニタ３４０ｂは、様々なメトリックの配布コレクタとして実装される。例えば、任意の所与の時間期間中に（例えば、１秒ごとに）、各ユーザノードデバイス３００ｂは、例えば、ノードメトリックとリンクメトリックとの両方を含む生のメトリックを収集し、次いで、それらのメトリックを適応トポロジサーバ３１０ａに配信する。より詳細に後述するように、適応トポロジサーバ３１０ａは、すべてのユーザノードデバイス３００ｂから受信するメトリックを整理および処理し、そのようなメトリックを使用して（セグメント、コンテンツアイテム、およびアプリケーションにわたる）そのオーバーレイネットワークトポロジの決定を容易にする。
【０１６１】
代替の実施形態では、ユーザノードデバイス３００ｂは、そのようなメトリックを適応トポロジサーバ３１０ａに報告するよりも頻繁にメトリックを収集する。別の実施形態では、特定のメトリックはあまり頻繁に収集されないか、または変化した場合にのみ適応トポロジサーバ３１０ａに提供される。さらなる実施形態では、親ノードはリンクメトリックを収集する（子ノードに依存する代わりに、または子ノードに依存することに加えてそのようなリンクメトリックを収集する）。さらに他の実施形態では、ノードメトリックおよびリンクメトリック（またはさらにはコンテンツアイテムのセグメントの転送に直接関係するもの）以外の、既知のＵＲＬへの定期的なｐｉｎｇ、ならびにネットワーク輻輳およびその他の変化する状況の様々な他の間接的な指標などの追加のメトリックが収集される（かつ適応トポロジサーバ３１０ａに報告される）。
【０１６２】
上述したように、一実施形態では、ノードメトリックは、その接続のタイプ（ＬＡＮ、ＷｉＦｉ、ＬＴＥ、４Ｇなど）、ＩＰアドレス／プレフィックス、ＩＳＰ、ＡＳＮ、デバイスのタイプ、ＣＰＵおよびメモリの負荷、オペレーティングシステム、地理的な場所、そのゲートウェイへのアップリンクおよびダウンリンクの速度など）の、ユーザノードデバイス３００ｂに固有のノード中継属性を含む。リンクメトリックは、リンクに沿った往復ｐｉｎｇ時間、レイテンシ、ジッタ、およびその他のネットワーク中心のメトリック、ならびにリンクの親および子に関する相対的ノードメトリック（ＩＰアドレス／プレフィックス、ＩＳＰ、およびＡＳＮなど）などの特定のリンクに関連するリンク中継属性を含む。
【０１６３】
他の実施形態では、アプリケーションパフォーマンスの品質のユーザ中心またはアプリケーションレベルのビューを反映するＱｏＥメトリック（例えば、ドロップされたフレーム、再バッファリングイベントなど）もメトリックとして含まれる。そのようなＱｏＥメトリックは、もちろん、アプリケーション固有であり、一実施形態では、適応トポロジサーバ３１０ａによって（他のメトリックと共に）そのアプリケーション固有のパフォーマンス基準を定義するために使用される。本発明の趣旨から逸脱することなく、様々な異なるまたは他のノードメトリック、リンクメトリック、および他のメトリックが使用されてもよい。
【０１６４】
各ユーザノードデバイス３００ｂ内の受信機３５０ｂは、その親ノードからコンテンツアイテムのセグメントをそれによって受信するプロトコルを管理する。一実施形態では、標準のＷｅｂＲＴＣ  ＡＰＩおよびプロトコルを使用して、親ノードからその子ノードの各々へのコンテンツアイテムの１つ以上のセグメントのピアツーピア送信を容易にする。他の実施形態では、異なる標準またはカスタムプロトコルが使用される。さらに他の実施形態では、特定のユーザノードデバイス３００ｂは、複数の異なるプロトコルをサポートする。プロトコルの選択は、アプリケーションごとに異なる場合がある設計およびエンジニアリングのトレードオフの結果である。
【０１６５】
同様に、ユーザノードデバイス３００ｂが親ノードである場合、リレイヤ３６０ｂは、コンテンツアイテムの受信されたセグメントのその指定された子ノードへの中継を管理する。リレイヤ３６０ｂは、ユーザノードデバイス３００ｂが現在子ノードを指定している場合にのみ使用される。例えば、適応トポロジサーバ３１０ａによるオーバーレイネットワークトポロジの再構成に続いて、ユーザノードデバイス３００ｂには、指定された子ノードがすべてなくなったことが通知されるが、後で（後続の再構成に続いて）コンテンツアイテムの後続のセグメントを配布するために指定された１つ以上の子ノードがあることが通知される場合がある。
【０１６６】
コンテンツアレイマネージャ３７０ｂは、コンテンツアイテムのセグメントの受信および中継の両方を管理する。例えば、セグメントが受信されると、コンテンツアレイマネージャ３７０ｂは、それらのセグメントが関連付けられるアプリケーションに従って、コンテンツプレーヤ３２５ｂによるそれらのセグメントの消費（例えば、ブロードキャストビデオの視聴）での使用のために、受信アレイ３７２ｂ内にそれらのセグメントをバッファリングする。
【０１６７】
コンテンツプレーヤ３２５ｂは、例えば、ユーザノードデバイス３００ｂのユーザによる視聴のために、ビデオコンテンツアイテムの受信されたセグメントを再生するストリーミングＨＴＭＬ５ビデオプレーヤであってもよい。アプリケーションがコンテンツプレーヤ３２５ｂによる３０ｆｐｓの再生を提供する場合、コンテンツアレイマネージャ３７０ｂは、（受信アレイ３７２ｂ内の）受信セグメントのバッファを維持し、これは、適切なレートでのコンテンツプレーヤ３２５ｂへのビデオフレーム（例えば、複数のビデオセグメント）の配信を容易にする。いくつかの実施形態では、コンテンツプレーヤ３２５ｂは、ビデオコンテンツアイテムのスムーズな再生を容易にするために別個のフレームバッファを含んでもよい。
【０１６８】
一実施形態では、コンテンツプレーヤ３２５ｂは、ユーザノードデバイス３００ｂの中へと組み込まれた（または一般的にインストールされた）ウェブブラウザの標準構成要素、例えば標準のサファリ、クローム、またはインターネットエクスプローラウェブブラウザとして実装される。標準機能を活用することによって、本発明は、各ユーザノードデバイス３００ｂに追加のカスタムソフトウェアをインストールする必要性を回避し、したがって、ユーザノードにわたる大きな互換性を保証する。他の実施形態では、コンテンツプレーヤ３２５ｂは、カスタムウェブブラウザまたはスタンドアロンプレーヤとして実装される。
【０１６９】
ユーザノードデバイス３００ｂが親ノードである場合、コンテンツアレイマネージャ３７０ｂはまた、適応トポロジサーバ３１０ａによって指定された各子ユーザノードデバイス３００ｂへのリレイヤ３６０ｂによる送信のためのセグメントのバッファリングを容易にする受信セグメントの中継アレイ３７４ｂも維持する。言い換えれば、コンテンツアレイマネージャ３７０ｂは、それらの子ユーザノードデバイス３００ｂにおける各々の受信機３５０ｂへの外部送信のためにセグメントの別個のバッファを維持する。他の実施形態では、このバッファを使用して、子ユーザノードデバイス３００ｂのセットが同じセグメントを異なる時間に受信しなければならないＶＯＤアプリケーションを容易にする。
【０１７０】
１つのユーザノードデバイス３００ｂ内のリレイヤ３６０ｂは、（一実施形態では）他のユーザノードデバイス３００ｂ内の受信機３５０ｂと直接通信するため、それらは互換性のあるプロトコル（上述したＷｅｂＲＴＣ  ＡＰＩおよびプロトコルなど）を実装する必要がある。異なるユーザノードデバイス３００ｂは、本発明の趣旨から逸脱することなく、異なる（しかし互換性のある）標準またはカスタムプロトコル（またはさらには同じユーザノードデバイス３００ｂの受信機３５０ｂおよびリレイヤ３６０ｂ内の異なるプロトコル）を使用してもよい。
【０１７１】
本発明は、（一実施形態では）ユーザノードデバイス３００ｂ（例えば、標準ライブラリ３２０ｂ、コンテンツプレーヤ３２５ｂ、ならびに受信機３５０ｂおよびリレイヤ３６０ｂによって実装されるプロトコル）内の特定の標準機能を活用するが、（上述したように）ユーザノードデバイス３００ｂに存在するカスタム機能にも依存する。例えば、コミュニケータ３３０ｂは、適応トポロジサーバ３１０ａとの通信を管理するために使用される。メトリックモニタ３４０ｂは、一定のメトリックを経時的に監視し、それらを適応トポロジサーバ３１０ａに提供するために使用される。また、受信機３５０ｂおよびリレイヤ３６０ｂは、（オーバーレイネットワークトポロジが再構成されると変更される場合がある）指定された親ノードから、コンテンツアイテムのセグメントを受信するプロセスを管理するために使用される。最後に、アップローダ３８０ｂを使用して、ユーザノードデバイス３００ｂを本発明のオーバーレイネットワークトポロジに沿って配布されるコンテンツアイテムのソースとすることができるようにする（例えば、カメラからのライブまたは録画ビデオのストリーミングだけでなく、内部で生成されるか、または外部ソースから取得される他のコンテンツアイテム）。
【０１７２】
一実施形態では、このカスタム機能は、アプリケーションに参加する（例えば、ストリーミングビデオを視聴する、または大きなファイルを交換する）ために適応トポロジサーバ３１０ａへの要求を最初に開始するときに、適応トポロジサーバ３１０ａによってユーザノードデバイス３００ｂへとダウンロードされる。他のアプリケーションに参加する、または他のコンテンツアイテムを受信するための後続の要求では、この機能を再度ダウンロードする必要はない。
【０１７３】
適応トポロジサーバ３１０ａはまた、（一実施形態では）関連するＰＯＩとも通信して、後続のセグメントをユーザノードデバイス３００ｂへと直接配信するために親ノードが選択される時間まで、要求されたコンテンツアイテムの初期セグメントを提供するように、「新たに参加した」ユーザノードデバイス３００ｂに指示する。ＰＯＩもまた、上述したようにコンテンツアイテムのすべてのセグメントを各オーバーレイネットワークトポロジ３２０ａ−１のルートノードへと配信することになる。ユーザノードデバイス３００ｂがコンテンツアイテムのソースである他の実施形態では、適応トポロジサーバ３１０ａは、（初期セグメントを新しく結合されたノードに送信することと、すべてのセグメントを指定されたルートノードに送信することとの両方に関して）この点でＰＯＩとして機能するようにアップローダ３８０ｂに指示する。
【０１７４】
本発明の予測的なオーバーレイネットワークアーキテクチャの機能の多くを実装するサーバ側構成要素に目を向けると、図３Ｃは、適応トポロジサーバ３００ｃの主要構成要素の一実施形態を例示している。上述したように、適応トポロジサーバ３００ｃの機能は１つ以上の物理サーバにわたって実装することができ、そのような機能の一部は、完全にハードウェア内またはハードウェア内とソフトウェア内との両方に実装し、単一の概念ソフトウェアモジュールに結合するか、複数のモジュールにわたって分割することができる（様々な設計およびエンジニアリングのトレードオフによって決定される）。
【０１７５】
図３Ｃに示される実施形態では、適応トポロジサーバ３００ｃは、ＣＰＵ３１２ｃ、メモリ３１４ｃ、およびオペレーティングシステム３１５ｃなどの標準ハードウェアおよびソフトウェア構成要素３１０ｃ、ならびにネットワークアダプタ３１６ｃを含む単一の物理的サーバとして示されている。ユーザノードデバイス３００ｂと同様に、この標準のサーバ側ハードウェアおよびソフトウェア機能は、汎用ＣＰＵ３１２ｃおよびオペレーティングシステム３１５ｃ、ならびに複数の（シングルまたはマルチコア）ＣＰＵ３１２ｃではなく、１つ以上の専用マイクロコントローラを使用して実装することができる。いくつかの実施形態では、適応トポロジサーバ３００ｃはまた、ディスプレイ、キーボード、カメラなどのＩ／Ｏデバイス３１８ｃも含む。適応トポロジサーバ３００ｃ内の別個のデータベースが図３Ｃに示されている（かつ後述する）が、メモリ３１４ｃもまた、一部の実施形態では、カスタムデータおよび機能を記憶するために使用される。
【０１７６】
一実施形態では、標準ライブラリ３２０ｃもまた、ユーザノードデバイス３００ｂ（およびコンテンツアイテムの様々なＰＯＩソース）との通信を容易にするために使用される。ここでも、設計およびエンジニアリングのトレードオフにより、どの標準ＡＰＩおよびプロトコルが活用されるかだけでなく、専有のソフトウェアが展開される程度が決まる。ユーザノードデバイス３００ｂの場合のように、本発明のサーバ側機能は、（ハードウェアで実装されない限りにおいて）非一時的なコンピュータアクセス可能な記憶媒体（メモリ３１４ｃ、または後述するデータベース３７５ｃおよび３８５ｃなどの他の形式のデータ記憶装置など）において具現化され、処理装置（ＣＰＵ３１２ｃなど）によって実行される。
【０１７７】
シグナリングサーバ３３０ｃは、例えば、メトリックを受信し、（シグナリングサーバ３３０ｃからのさらなる対話を伴わずに）コンテンツアイテムの後続のセグメントを指定された子ノードへと「プッシュ」するように、親ユーザノードデバイス３００ｂに指示するために、ユーザノードデバイス３００ｂとの通信を取り扱う。一実施形態では、シグナリングサーバ３３０ｃはまた、ユーザノードデバイス３００ｂのペア間の初期「ピア接続」の作成も容易にする。
【０１７８】
別の実施形態では、シグナリングサーバ３３０ｃは、ユーザノードデバイス３００ｂとの他の通信も担当する。例えば、シグナリングサーバ３３０ｃは、アプリケーション（および／または個々のコンテンツアイテム）に参加するリクエストをユーザノードデバイス３００ｂから受信する。シグナリングサーバ３３０ｃはまた、ユーザノードデバイス３００ｂがネットワーク接続を失ったか、そうでない場合は１つ以上のコンテンツアイテムの視聴を停止したかどうかを示すユーザノードデバイス３００ｂからの「ハートビート」およびその他の信号を監視し、その場合、現在のオーバーレイネットワークトポロジから削除される。さらに、シグナリングサーバ３３０ｃは、適応トポロジサーバ３００ｃによって識別されたオーバーレイネットワークトポロジへのコンテンツアイテムのストリーミングまたは他の配布を容易にするために、ＰＯＩノードまたはコンテンツの他のソースとの通信を取り扱う。
【０１７９】
一実施形態では、コンテンツマネージャ３６０ｃは、様々なアプリケーションに関して複数のコンテンツプロバイダによって提供されるコンテンツアイテムを管理する。コンテンツマネージャ３６０ｃは、各コンテンツアイテムが確実に現在のオーバーレイネットワークトポロジのルートノードにストリーミングされるか、またはその他の方法で配布されるようにする。言い換えれば、（所与のコンテンツアイテムに関連付けられている）現在のオーバーレイネットワークトポロジの再構成がそれらのルートノードを変更する限りにおいて、コンテンツマネージャ３６０ｃは、（シグナリングサーバ３３０ｃを介して）関連するＰＯＩと通信して、ＰＯＩがこれらの更新されたルートノードへのコンテンツアイテムの後続のセグメントを確実に配信するようにする。
【０１８０】
コンテンツマネージャ３６０ｃはまた、各アプリケーションのコンテンツアイテムに（または、他の実施形態では、個々のコンテンツアイテムに）関連付けられている、アプリケーション固有のパフォーマンス基準を取得または生成する。コンテンツマネージャ３６０ｃは、パフォーマンス基準をメモリ３１４ｃに、または他の実施形態では、それ自体の別個のデータベースに記憶する。上述したように、任意の特定のアプリケーションまたはコンテンツアイテムについて、現在のオーバーレイネットワークトポロジ（およびその個々のノードおよびリンク）のパフォーマンスは、様々なメトリックの関数として定義され、パフォーマンス基準は、一連の閾値、またはそのパフォーマンスに課せられる他の制約として定義される。一実施形態では、そのようなパフォーマンス基準は、各コンテンツアイテムに対して事前定義される。他の実施形態では、パフォーマンス基準は、経時的に動的に生成および修正される。
【０１８１】
オーバーレイネットワークトポロジマネージャ３５０ｃは、本発明の予測的なオーバーレイネットワークアーキテクチャの主要な構成要素を提供する。以下の説明の多くは、特定のコンテンツアイテムの配布、およびそのコンテンツアイテムの後続のセグメントがこれに沿って（各再構成に続いて）配布されるオーバーレイネットワークトポロジの経時的な再構成に焦点を当てている。しかしながら、上述したように、本発明の予測的なオーバーレイネットワークアーキテクチャは、複数のアプリケーションにわたる複数のコンテンツアイテムの同時配布をサポートする。
【０１８２】
定義された各期間中、メトリクスプロセッサ３５２ｃは、生のメトリックを主にユーザノードデバイス３００ｂから受信するが、（一実施形態では）外部ソースからも、経時的にインターネットトラフィックを監視することによって直接的にか、またはインターネットトラフィックを監視する第三者から間接的に受信し、そして時折、特定のトラフィックパターンが経時的に明らかになる地域またはグローバルインターネットの「トラフィックマップ」を構築する。以下により詳細に説明するように、メトリックプロセッサ３５２ｃは、この生のメトリックデータを予測エンジン３５５ｃおよびトポロジセレクタ３５８ｃによって利用できる形式に変換して、アプリケーション固有のパフォーマンス基準を満たすオーバーレイネットワークトポロジを識別する。
【０１８３】
一実施形態では、メトリックプロセッサ３５３は、連続する各時間期間中に、これらの生のメトリックを、予測エンジン３５５ｃによるノード中継容量およびリンク中継容量予測を容易にする「訓練サンプル」へと整理する。例えば、メトリックプロセッサ３５３は、ノード中継およびリンク中継分類器への訓練サンプル入力および出力を生成するために、生のメトリックを定量化し、（一実施形態では）それらをスケーリングおよび加重する。
【０１８４】
さらに、以下により詳細に説明するように、メトリックプロセッサ３５３は特定のメトリックを統合して、ノード中継分類器への訓練サンプル出力を生成する（例えば、単一の親ノードからの複数のリンクのパフォーマンスに関する観測されたメトリックを組み合わせる）。生のメトリックのその他の変換は、当業者には明らかであろう。
【０１８５】
連続する各時間期間中にメトリックプロセッサ３５２ｃによって処理されたメトリック（および適応トポロジサーバ３００ｃによって取得された他のメトリクス）は、一実施形態では、履歴パフォーマンスデータベース３８５ｃに記憶される。一実施形態では、（生のおよび処理された形式の両方の）これらの履歴メトリックは、予測エンジン３５５ｃによって利用される。
【０１８６】
オーバーレイネットワークデータベース３７５ｃは、異なるオーバーレイネットワークトポロジを定義するノードおよびリンクのセットの識別子を記憶するために使用される。さらに、別の実施形態では、オーバーレイネットワークデータベース３７５ｃは、これらのオーバーレイネットワークトポロジのノードおよびリンクの間の相互依存性、ならびに／または関連する履歴メトリックを反映する他のデータを記憶するために使用される。
【０１８７】
以下により詳細に説明するように、トポロジセレクタ３５８ｃは、一実施形態では、予測エンジン３５５ｃによって生成された、指定されたノード中継容量およびリンク中継容量の予測（および、一実施形態では、需要の予測、すなわち、継続期間と共にネットワークに存在するノードの予測）に基づいて、現在のコンテンツアイテムに適用可能な定義されたアプリケーション固有のパフォーマンス基準を満たすオーバーレイネットワークトポロジを識別する非線形多次元最適化および／またはヒューリスティックアルゴリズムを使用する。トポロジセレクタ３５８ｃは、これらのアルゴリズムを使用して、新しいまたはより良い親を必要とするノードに過剰容量を再配布する程度に基づいて、オーバーレイネットワークトポロジの評価を容易にし、すなわち、パフォーマンス基準を満たすためにネットワークトラフィックをシフトする。
【０１８８】
さらに、これらのアルゴリズムは、オーバーレイネットワークトポロジのグローバルコンテキスト内のノードおよびリンクの間の相互依存性を考慮する。上述したように、任意の特定のオーバーレイネットワークトポロジの状況では、各ノードおよびリンクのパフォーマンスは、アップストリームのノードおよびリンクのパフォーマンスに依存する。
【０１８９】
一実施形態では、トポロジセレクタ３５８ｃは、新たに発見されたノードを追加し、かつ現在のコンテンツアイテムをもはや受信していないノードを削除することによって、現在のオーバーレイネットワークのノードを更新する。さらに重要なことに、トポロジセレクタ３５８ｃはまた、予測エンジン４５５ａも使用して、指定されたノードおよびリンクに対するノード中継容量およびリンク中継容量の予測を生成し、次いで、それらのノードおよびリンクの間の相互依存性を考慮しつつ、それらのノードおよびリンクを含む予想オーバーレイネットワークトポロジを分析する。別の実施形態では、（上記の図２ｂのノード２４０ｂ−２によって示されるように）そのようなノードが現在のコンテンツアイテムを消費していなくても、追加のノードが含まれる。
【０１９０】
他の実施形態では、トポロジセレクタ３５８ｃは、アルゴリズムを使用して、パフォーマンス基準を満たすオーバーレイネットワークトポロジ（および、いくつかの実施形態では、最適なオーバーレイネットワークトポロジ）を識別するのに必要な時間の量（および他のネットワークリソース）を減少する。例えば、トポロジセレクタ３５８ｃは、アルゴリズムを使用して、（１）予測エンジン４５５ａを使用して生成するノード中継容量およびリンク中継容量の予測の数、ならびに／または（２）パフォーマンス基準に関して評価する予想オーバーレイネットワークトポロジの数を減少する。
【０１９１】
（図７Ｆに関してより詳細に後述する）一実施形態では、トポロジセレクタ３５８ｃは、（新しいノードおよび孤立ノードに加えて）新しい親を必要とする「低パフォーマンス」ノードの閾値数を識別する。これにより、（新しい親を必要とする）そのようなノードへのリンクのみを考慮する必要があるため、ノード中継容量とリンク中継容量の予測数が劇的に減少する。他のリンクは、新しく構成された任意のオーバーレイネットワークトポロジ内にそのまま残ることになる。
【０１９２】
他の実施形態では、トポロジセレクタ３５８ｃは、リンクの変更が最大の効果を有するであろう、オーバーレイネットワークトポロジの領域（例えば、ルートもしくは特定の「ブランチ」またはツリーのレベルの近く）を識別することによって、指定されたノード中継容量およびリンク中継容量の予測の数のさらなる減少を達成する。さらに他の実施形態では、トポロジセレクタ３５８ｃは、これらの予測に基づいて、予想オーバーレイネットワークトポロジの順列の数のサブセットを選択的に考慮することによって、同様の減少を達成する。例えば、そのような一実施形態では、トポロジセレクタ３５８ｃは、ツリーのより高い「ブランチ」で親ノードとして利用する「高パフォーマンス」ノードを識別する。様々な他のアルゴリズム、変換、設計、およびエンジニアリングのトレードオフが当業者には明らかであろう。
【０１９３】
使用された特定のアルゴリズムに関係なく、トポロジセレクタ３５８ｃは、パフォーマンス基準を満たすオーバーレイネットワークトポロジを出力として生成する。上述したように、識別されたオーバーレイネットワークトポロジが最適なものではない場合でも、他の要因に（ソリューションの生成に必要な時間などの）優先順位を付けることができるため、本発明の趣旨から逸脱することなく、多くの異なるアルゴリズムを使用することができる。
【０１９４】
図４Ａに目を向けると、図４００ａは、適応トポロジサーバ３００ｃの予測エンジン４５５ａおよびトポロジセレクタ４５８ａの構成要素との間の関係の高レベルの実施形態を例示する。上述したように、予測エンジン４５５ａは、（一実施形態では、履歴パフォーマンスＤＢ４８５ａから以前に取得または観測された履歴メトリックに加えて）連続する各時間期間４５３ａ中に、様々な処理されたメトリック４４５ａを入力として受信する。これらの入力に基づいて、予測エンジン４５５ａは、ノード中継容量４５６ａおよびリンク中継容量４５７ａの予測（および、一実施形態では需要予測）を生成し、これにより、より詳細に後述するように、より多様な訓練サンプルで訓練されるにつれて経時的に改善される。
【０１９５】
一実施形態では、トポロジセレクタ４５８ａは、（予測エンジン４５５ａから）指定されたノード中継容量４５６ａおよびリンク中継容量４５７ａの予測を要求する。より詳細に後述するように、トポロジセレクタ４５８ａは、これらの予測を利用して、パフォーマンス基準を満たすオーバーレイネットワークトポロジ４６０ｂを識別する。
【０１９６】
図４Ｂのフロー図４００ｂは、図４Ａの構成要素の高レベルの動的な例示を提供する。連続する各時間期間（トポロジセレクタ４５８ｂとメトリックプロセッサ４５２ｂと間の反復ループで示されている）に、メトリックプロセッサ４５２ｂは、個々のノードおよびリンクに関連する生のメトリックデータ４５１ｂを受信および処理する。メトリックプロセッサ４５２ｂは、その生のデータを処理して、入力ノード中継属性が（ノード中継容量の予測を生成する）出力ノード中継パフォーマンス値とどのように相関するか、および入力リンク中継属性が（リンク中継容量の予測を生成する）出力リンク中継パフォーマンス値とどのように相関するかを学習するように、予測エンジン４５５ｂを訓練するように設計されたタイムスタンプ付きサンプル４５３ｂを生成する。
【０１９７】
一実施形態では、パフォーマンス基準を満たすオーバーレイネットワークトポロジ４６０ｂのトポロジセレクタ４５８ｂによる識別を容易にする、指定されたノード中継容量およびリンク中継容量の予測４５６ｂ（および別の実施形態では、需要予測）を提供するために、予測エンジン４５５ｂ（一度十分に訓練された）がトポロジセレクタ４５８ｂによって使用される。「訓練閾値」を使用して、予測エンジン４５５ｂがいつトポロジセレクタ４５８ｂによって依存されるのに十分なだけ訓練を受けたかを決定する。別の実施形態では、予測エンジン４５５ｂは、経時的に徐々に改善する（トポロジセレクタ４５８ｂによる使用のための）ノード中継容量およびリンク中継容量予測４５６ｂを連続的に生成する。
【０１９８】
Ｄ．オーバーレイネットワークトポロジの再構成
図５のフロー図５００は、この「オーバーレイネットワークトポロジ再構成プロセス」のわずかにより詳細なシステムレベルのビューの一実施形態を提供する。このプロセスは、予測エンジン４５５ｂの主要構成要素（以下の図６Ａおよび６Ｂ）およびトポロジセレクタ４５８ｂの主要構成要素（以下の図７Ａ〜７Ｅ）の特定の実施形態に関して、より詳細に後述される。
【０１９９】
工程５０５では、コンテンツマネージャ３６０ｃは、システムによってサポートされる各アプリケーション（または別の実施形態では、各コンテンツアイテム）に関して、アプリケーション固有のパフォーマンス基準を定義する。現在のオーバーレイネットワークトポロジ上で配布されている現在のコンテンツアイテムに関して、パフォーマンス基準は、その現在のオーバーレイネットワークトポロジ（およびその個々のノードおよびリンク）のパフォーマンスに課せられた制約を表す。一実施形態では、そのようなパフォーマンスは、（任意の指定された時間期間中に）メトリックプロセッサ４５２ｂに利用可能にされたメトリックの関数として定義され、これは、パフォーマンス基準が満たされるかどうかのトポロジセレクタ４５８ｂによる決定を容易にする。
【０２００】
メトリックプロセッサ４５２ｂは、工程５０７で生のメトリックを処理して、予測エンジン４５５ｂを継続的に訓練するために使用されるタイムスタンプ付きサンプルを生成する。上記で示唆したように、必要な時間およびリソースを考えると、トポロジセレクタ４５８ｂがメトリックを収集および処理するすべての時間期間中に、現在のオーバーレイネットワークトポロジの状態を再評価することは実行不可能な場合がある（工程５０７）。
【０２０１】
したがって、オーバーレイネットワークトポロジマネージャ３５０ｃは、工程５１０を実行して、この再評価をトリガするかどうかを決定する。いくつかの実施形態では、このトリガは時間ベースであり、メトリック収集のプロセスと同じかまたはそれより少ない頻度で実行される。他の実施形態では、トリガはイベントベースである。例えば、一実施形態では、現在のオーバーレイネットワークトポロジ（ならびにその個々のノードおよびリンク）のパフォーマンスに関して、閾値パフォーマンスレベルが確立される。そのようなパフォーマンスがパフォーマンス基準を満たすことができない事前定義された閾値の割合の範囲内である場合、工程５１０は、工程５１５で始まる現在のオーバーレイネットワークトポロジの再評価をトリガする。
【０２０２】
（時間ベースか、イベントベースか、またはその他のトリガによるものかを問わず）トリガされると、トポロジセレクタ４５８ｂは、工程５１５において予測エンジン４５５ｂを使用して、指定されたノード中継容量およびリンク中継容量の予測を生成する。一実施形態では、トポロジセレクタ４５８ｂによって考慮される任意のオーバーレイネットワークトポロジに含まれるべき各親ノードについて、そのような予測が生成される。他の実施形態では、非線形および多次元最適化および／またはヒューリスティックアルゴリズムを使用して、考慮される予想オーバーレイネットワークトポロジの数、ひいては必要なノード中継容量およびリンク中継容量の予測の数を減少させる。
【０２０３】
トポロジセレクタ４５８ｂは、工程５２０においてそのような予測を利用して、パフォーマンス基準を満たすオーバーレイネットワークトポロジを決定する。上述したように、他の実施形態では、トポロジセレクタ４５８ｂは、「最適な」オーバーレイネットワークトポロジ、すなわち、パフォーマンス基準を最も良好に満たす（または満たすことに最も近づく）トポロジを決定する。
【０２０４】
トポロジセレクタ４５８ｂがパフォーマンス基準を満たすオーバーレイネットワークトポロジを決定すると、オーバーレイネットワークトポロジマネージャ３５０ｃは、工程５２５において、現在のオーバーレイネットワークトポロジをトポロジセレクタ４５８ｂによって決定されたトポロジと置き換えるかどうかを決定する。上述したように、より良い（または最適な）オーバーレイネットワークトポロジが存在する場合でも、トポロジを頻繁に変更しすぎる（例えば、一度にあまりにも多くのリンクを変更する）オーバーヘッドは、利点を上回る場合がある。一実施形態では、このオーバーヘッドを低減するために、変更されたリンクの数の事前定義された閾値が使用される。他の実施形態では、時間ベースの閾値が使用される（例えば、現在のオーバーレイネットワークトポロジが所与の時間期間中に変更される回数を制限する）。本発明の趣旨から逸脱することなく、他の様々な最適化および技法を使用してもよい。
【０２０５】
予測エンジン４５５ｂおよびトポロジセレクタ４５８ｂの詳細な実施形態に目を移す前に、上記で示唆したように、ネットワーク輻輳は本質的に需要が供給を超えた結果であることを認識することが役立つ。ネットワーク輻輳が現在のオーバーレイネットワークトポロジのパフォーマンスに与える影響を軽減するために、予測エンジン４５５ｂおよびトポロジセレクタ４５８ｂが連携して、アプリケーション固有のパフォーマンス基準を満たす様式で、オーバーレイネットワークトポロジを再構成し、ひいては需要が供給を超える程度を減少させる（現在のまたは予想ネットワーク輻輳に照らして）。
【０２０６】
予測エンジン４５５ｂは、ローカル（ノードおよびリンク）レベルで、ネットワーク輻輳およびその他のパフォーマンス制限要因に対処して、ノード中継容量およびリンク中継容量を予測するが、トポロジセレクタ４５８ｂは、グローバル（トポロジ）レベルで、個々のノードおよびリンクの間の相互位依存性に対処して、新しいまたはより良い親を必要とするノードに過剰容量を効果的に再配布するオーバーレイネットワークトポロジを識別し、すなわち、パフォーマンス基準を満たすためにネットワークトラフィックをシフトする。
【０２０７】
１．予測エンジン
ａ．ノード中継およびリンク中継分類器
図６Ａおよび図６Ｂは、２つのニューラルネットワーク分類器、つまりノード中継分類器６００ａおよびリンク中継分類器６００ｂが、（ローカルノードおよびリンクレベルで）それぞれのノード中継容量およびリンク中継容量の予測を生成するために使用される予測エンジン４５５ｂの一実施形態を示す。図６Ａのノード中継分類器６００ａは、ノード中継容量の予測を生成する一方で、図６Ｂのリンク中継分類器６００ｂは、リンク中継容量の予測を生成する。他の実施形態では、予測エンジン４５５ｂは、ノード中継容量またはリンク中継容量の予測のみを生成するが、両方は生成しない。さらに他の実施形態（後述する）では、予測エンジン４５５ｂは、「需要予測」を生成する。
【０２０８】
図６Ａおよび図６Ｂに示される実施形態では、ニューラルネットワーク分類器６００ａおよび６００ｂの両方が、監督された機械学習の形態を実装する。他の実施形態において、教師なし機械学習（例えば、それらの様々な属性の類似性に基づくノードのクラスタリング）もまた、このプロセスへの追加入力を提供するために使用される。例えば、オーバーレイネットワークトポロジマネージャ３５０ｃは、クラスタリングアルゴリズムを使用して、オーバーレイネットワークのノードを、複数の「ディメンション」（すなわち、より詳細に後述する、時間のメトリックを含む複数のメトリック）に基づいて複数のクラスタに分類する。ノードがネットワーク分類器６００ａおよび６００ｂへの追加入力として分類されるクラスタのＩＤを含めることによって、このクラスタＩＤは、（特に、後述するように、長期的な時間依存の繰り返しパターンに関して）入力の出力との相関を容易にする。
【０２０９】
本発明のニューラルネットワークは、特に、オーバーレイネットワークのノードおよびリンクの属性を、そのようなノードおよびリンクの観測されたパフォーマンスと相関させるために使用される。一実施形態において、これらのニューラルネットワークは、（連続する時間期間にわたって）ノード中継およびリンク中継属性（例えば、入力ノードメトリックおよびリンクメトリック）を（結果としてもたらされる子宛先ノードによって経験されるパフォーマンスを反映する）それぞれのノード中継およびリンク中継パフォーマンス値と相関させて、それぞれのノード中継容量とおよびリンク中継容量の予測を容易にする。
【０２１０】
特に、ノード中継分類器は、予想親ノードの「容量」を予測してコンテンツを１つ以上の子ノードに中継するために、ノード中継属性（ノードメトリック）を観測されたノード中継パフォーマンス値と相関させる。例えば、各子ノードからの５ｍｂｐｓの需要を想定すると、予測される１３ｍｂｐｓのノード中継容量は、予想親ノードが２つの子ノードに同時にコンテンツを中継する能力を有する（およびその需要を満たす）ことが予測されることを示す。５ｍｂｐｓを下回る予測ノード中継容量は、指定された親ノードが単一の子ノードからの需要も満たす能力を有するとは予測されず、したがって「リーフ」ノードであるべきであることを示す。
【０２１１】
リンク中継分類器は、リンク中継属性（リンクメトリック）を、予想リンクの容量、すなわち、リンクがそのリンクの子ノードにコンテンツを配信する能力を予測する目的で、観測されたリンク中継パフォーマンス値と関連付ける。例えば、ここでも各子ノードからの５ｍｂｐｓの需要を想定すると、予測される５ｍｂｐｓのリンク中継容量は、指定されたリンクがそのリンクの指定された子ノードにコンテンツを配信する能力を有する（かつそのリンクの指定された子ノードからの需要を満たす）と予測されることを示す。５ｍｂｐｓを下回る予測されたリンク中継容量は、このリンクが指定された子ノードの需要を満たすことができると予測されず、したがって、オーバーレイネットワークトポロジのリンクであるべきではないことを示す。
【０２１２】
このような相関および「中継容量」の予測は、（オーバーレイネットワークトポロジの予想ノードおよびリンクの間の）相互依存性を解決すること、および過剰中継容量を（新しいまたはより良い親を必要とするノードに）再配布して、定義されたパフォーマンス基準を満たすオーバーレイネットワークトポロジの識別を容易にすることに関与する、より大きなプロセス（トポロジセレクタ４５８ｂに関して後述する）の一部である。
【０２１３】
より詳細に後述するように、トポロジセレクタ４５８ｂは、ノードＡのノードＩＤを提供することによってではなく、ノードＡに関連付けられている現在のノード中継属性（ノードメトリック）を提供することによって、ノード中継分類器６００ａに予想親ノード（例えばノードＡ）を指定し、そのノード中継属性から、ノード中継分類器６００ａは、トポロジセレクタ４５８ｂに送り返す予想親ノードＡに対する予測されたノード中継容量値（例えば、１３ｍｂｐｓ）を生成する。
【０２１４】
同様に、トポロジセレクタ４５８ｂは、Ａ→ＢリンクのリンクＩＤを提供するのではなく、Ａ→Ｂリンクに関連付けられている現在のリンク中継属性（リンクメトリック）を提供することによって、リンク中継分類器６００ｂへの予想リンク（例えばＡ→Ｂ）を指定し、そのリンク中継属性から、リンク中継分類器６００ｂは、トポロジセレクタ４５８ｂに送り返す予想Ａ→Ｂリンクに対する予測されたリンク中継容量値（例えば、５ｍｂｐｓ）を生成する。
【０２１５】
ｂ．ノード中継およびリンク中継分類器の訓練
ニューラルネットワーク分類器は、分類器が観測したことのない入力からの出力を予測するように、観測された入力を観測された出力に相関させるように訓練されているということを認識することが重要である。言い換えれば、分類器は、特定の観測されたデータから一般化する。
【０２１６】
例えば、ノードＡが親ノードになったことがなかった場合、ノード中継分類器６００ａは、ノードＡからリンクに沿って転送されたコンテンツに関連するメトリックを観測することはなかっただろう。にもかかわらず、トポロジセレクタ４５８ｂがノードＡに対するノード中継容量の予測を要求する場合、ノード中継分類器６００ａは、それでもそのような予測を生成することになる。訓練プロセスの詳細に関して以下に説明するように、その予測の精度は、本質的に、ノードＡに関連付けられている現在の入力メトリック（すなわち、実際の親ノードからの観測されたメトリック）が、経時的にノード中継分類器６００ａに提供されている他のノード（おそらくノードＡを含む）に関連付けられているメトリックにどれだけ類似しているかに依存する。
【０２１７】
言い換えれば、属性が経時的に観測された実際の親ノードは、同様の属性を有する予想親ノードの「代理」として効果的に機能する。両方は、ノード中継分類器６００ａがその親ノードのクラスの子ノードによって経験されるノード中継パフォーマンス値と相関することを学習した親ノードの同じ「クラス」の一部と考えられ得る。複数の入力属性を複数の出力属性に相関させることは、もちろん比較的複雑なタスクであるが、ニューラルネットワークの分野の当業者には明らかであろうように、教師付き機械学習に適している。
【０２１８】
同様に、Ａ→Ｋリンクがいずれのオーバーレイネットワークトポロジのリンクになったことがなかった場合、リンク中継分類器６００ｂは、Ａ→Ｋリンクに沿って転送されたコンテンツに関連するメトリックを観測することはなかっただろう。にもかかわらず、トポロジセレクタ４５８ｂがＡ→Ｋリンクに対するリンク中継容量の予測を要求する場合、リンク中継分類器６００ｂは、それでもそのような予測を生成することになる。
【０２１９】
ここでも、その予測の精度は、本質的にＡ→Ｋリンクに関連付けられている現在の入力リンクメトリックが、経時的にリンク中継分類器６００ｂに提供される他のリンク（おそらくＡ→Ｋリンクを含む）に関連付けられているメトリック（すなわち、実際の親子リンクから観測されたメトリック）にどれだけ似ているかに依存する。ノード中継分類器６００ａに関する場合のように、リンク中継分類器６００ｂによって経時的に属性が観測された実際のリンクは、同様の属性を有する予想リンクの代理として効果的に機能する。
【０２２０】
したがって、一実施形態では、ノード中継分類器６００ａおよびリンク中継分類器６００ｂの両方は、観測される親および子ノードの特定のアイデンティティに関係なく、ノードおよびリンク属性をそれらのそれぞれのノード中継およびリンク中継パフォーマンス値と相関させることによって訓練される。
【０２２１】
例えば、図６Ａを参照して、親ノードＡ（現在コンテンツを子ノードＢおよびＣに同時に中継している）に関してノード中継分類器６００ａに提供される訓練サンプルを検討する。この例では、リンクＡ→ＢおよびＡ→Ｃは、現在のオーバーレイネットワークトポロジの一部であり、各宛先ノードからの需要は５ｍｂｐｓと想定される。
【０２２２】
入力６１０ａは、ノードＡの接続タイプ、アップリンクおよびダウンリンク速度など、ノードＡに固有のノードメトリック６１２ａを含む。入力６１０ａはまた、この訓練サンプルに対するメトリックが収集された時間期間を表すメトリックタイムスタンプ６１４ａも含む（以下により詳細に説明される）。
【０２２３】
この訓練サンプルの出力６３０ａは、それぞれのＡ→ＢおよびＡ→Ｃリンクの子ノードＢおよびＣの両方に関係する。この例では、Ａ→ＢおよびＡ→Ｃリンクに沿って実際に観測されたパフォーマンス（例えば、Ａ→Ｂリンクに沿って５ｍｂｐｓ、Ａ→Ｃリンクに沿って３ｍｂｐｓで構成される合計８ｍｂｐｓ）を、予測されたノード中継容量６３２ａと比較する。一実施形態では、ノード中継分類器６００ａは、１つ以上のメトリックの関数として予測されたノード中継容量６３２ａ（および実際に観測されたパフォーマンス）を計算し、単一の値を生成する。他の実施形態では、複数の出力値を生成する。
【０２２４】
一実施形態では、実際に観測されたパフォーマンスが「容量制限のある」（需要が容量を超える場合）観測を反映するか、または「需要制限のある」（容量が需要以上の場合）観測を反映するかにかかわらず、ノード中継分類器６００ａへのすべての訓練サンプルが含まれる。他の実施形態では、中継容量をより正確に予測するために、ノード中継分類器６００ａへの訓練サンプルがフィルタリングされて、需要制限のある観測値が除外される。言い換えれば、観測は子ノードの合計需要によって制限されたため、観測は、親ノードの実際のノード中継容量を正確に反映していない可能性があるので、除外される。
【０２２５】
例えば、親ノードがその１つ以上の子ノードの合計需要を満たしている場合（例えば、１つの子ノードに対して５ｍｂｐｓ、２つの子ノードに対して１０ｍｂｐｓなど）、その需要制限のある訓練サンプルは除外される。逆に、親ノードがその子ノードのうちのいずれかの需要を満たすことができなかった場合（上記の例で、ノードＡは８ｍｂｐｓのノード中継容量を有していたが、Ａ→Ｃリンクに沿って３ｍｂｐｓしか配信しなかった場合）、その容量制限のある訓練サンプルが含まれる。
【０２２６】
別の実施形態では、明らかな制限された容量がアップストリーム依存性の結果であった場合（例えば、ノードＡの親がノードＡに３ｍｂｐｓのみを配信した場合）、またはリンク自体（Ａ→Ｃリンクに沿った輻輳した中間ルーティングノードなど）に沿って制限が課せられた場合、特定の容量制限のある訓練サンプルも除外される。一実施形態では、これらの条件の両方は、関連リンクに関するリンク中継容量の予測を取得することによって決定される。
【０２２７】
特定の訓練サンプルの包含または除外に関係なく、ノード中継分類器６００ａは、ノード中継容量の予測を継続的に生成する。言い換えれば、この実施形態では、（トポロジセレクタが「十分に」訓練されたとみなされるまで、ノード中継分類器６００ａからのノード中継容量の予測を要求しない場合でさえも）継続的に訓練される。予測されたノード中継容量６３２ａの出力値と実際の観測された出力値（図示せず）との差は、ノード中継分類器６００ａを経時的に訓練するために使用される「誤差」を表す（後述する）。
【０２２８】
ノードＡに関するこの訓練サンプルは、各時間期間中にノード中継分類器６００ａに提供される多くの訓練サンプルのうちの１つにすぎないことに留意されたい。もちろん、他の訓練サンプルは、他のノードおよびリンク、ならびに連続する時間期間中の同じノードおよびリンク（同じ訓練データのセットの繰り返し送信を含む）に関連している。
【０２２９】
上述したように、ノード中継分類器６００ａは、ノード中継属性とノード中継パフォーマンス値との間の相関関係を経時的に学習する。例えば、ノードＡがインターネットへの３Ｇセルラ接続を有し、比較的ゆっくりと子ノードにコンテンツを配信する場合、ノード中継分類器６００ａは、ノードＡが「悪い」親であることを特異的に学習せず、代わりに、より一般的に、３Ｇセルラ接続を有する予想親ノードは悪い親であるということを学習する。もちろん、このプロセスはより多くの属性（メトリック）が考慮され、それらの値は経時的に頻繁に変化するため、より複雑である。
【０２３０】
ノード中継分類器６００ａがトポロジセレクタ４５８ｂによって使用されて、予想親ノードのノード中継容量６３２ａが予測されると、指定された予想親ノード（おそらく親ノードになったことがないものでも）に関する入力６１０ａ（現在のノードメトリック６１２ａおよび現在のタイムスタンプ６１４ａ）が供給される。これらの入力６１０ａに基づいて、ノード中継分類器６００ａは、１つ以上の（指定されていない）子ノードにコンテンツを中継する能力を反映する、その指定された予想親ノードのノード中継容量６３２ａの予測を生成する。
【０２３１】
一実施形態では、１つ以上の隠れ層６２０ａが使用されて、複数の入力６１０ａおよび出力６３０ａの間のより複雑な相関を容易にする。この実施形態では、個々の隠れニューロン６２１ａは、「中間状態」値（このようなニューロン６２１ａへの入力の加重和または他のより複雑な関数として計算される）を表す。訓練中に「順伝播」プロセスを使用すると、入力６１０ａの値は、これらの中間状態を介して変換され、各訓練サンプルで提供される実際の出力値と比較される予測出力値を生成する。
【０２３２】
上述したように、これらの生成された出力値と実際に観測された出力値との差は、ノード中継分類器６００ａによって生成された予測の「誤差」を表す。これらの誤差は、それらの中間状態値を計算するために隠れニューロン６２１ａによって使用される重みを調整する「逆伝播」プロセス（すなわち、統計回帰の形式）でノード中継分類器６００ａを訓練するために利用される。経時的に、より代表的な訓練サンプルが提供されるため、ノード中継分類器６００ａは、これらの誤差を徐々に減少させ、したがってその予測の能力を改善する。ニューラルネットワークおよび教師付き機械学習の分野の当業者には明らかであろうように、本発明の趣旨から逸脱することなく、様々な異なるアルゴリズムが使用されてもよい（単一の隠れ層または複数の「深層学習」隠れ層、および様々な教師なし機械学習アルゴリズムを含む）。
【０２３３】
上記で参照したように、指定された親ノードに関連するノードメトリック６１２ａに加えて、メトリックタイムスタンプ６１４ａも入力６１０ａに含まれる。ノード中継分類器６００ａの訓練中、タイムスタンプ６１４ａは、各訓練サンプルのメトリックがその間に収集された時間期間を表す。（指定された予想親ノードに関するノード中継容量６３２ａの予測を生成するための、トポロジセレクタ４５８ｂによる）ノード中継分類器６００ａの使用中、タイムスタンプ６１４ａは、その指定された予想親ノードに関連するノードメトリック６１２ａが取得された時間期間を表す。
【０２３４】
しかしながら、より重要なことに、タイムスタンプ６１４ａは、「時間」メトリックに関して、すなわち、繰り返される時間依存パターンに関して、ノードメトリックのノード中継パフォーマンス値への相関を容易にする。例えば、他のメトリックが経時的に繰り返されるパターン（朝よりも夕方のほうが、もしくは平日よりも週末のほうが大きい交通遅延、または悪天候時の国内の特定の地域での交通遅延など）を反映している限りにおいて、タイムスタンプ６１４ａは、任意の特定の時間期間中にノード中継容量６３２ａを予測するために使用される場合、ノード中継分類器６００ａが時間メトリックの相対的効果を反映することを可能にする貴重な情報を提供する。一実施形態では、タイムスタンプ６１４ａは、単一の正確な日付／時刻値の代わりに、またはそれに加えて、（ＧＭＴなどのグローバル基準時間に基づいているか、またはローカルタイムゾーンに基づいているかにかかわらず）曜日および時刻を区別するための複数の値、ならびに休日、特別なイベント、および様々な他の値を含む。
【０２３５】
タイムスタンプ６１４ａが様々なノードメトリックに「時間」の次元を追加するように、他の実施形態では、現在のオーバーレイネットワークトポロジの特定のノードおよびリンクに対して「外部」である間接要因を反映するために、追加のメトリックが使用される。例えば、上述したように、下位ネットワーク上の他のアプリケーションおよびイベントの結果としてもたらされるノードおよびリンクに対する影響の外部指標も、予測エンジン４５５ｂへの入力として含まれる。
【０２３６】
このような外部指標としては、スーパーボールおよび人気テレビシリーズのシーズン終了エピソードなど、定期的な人気イベントまたは他の帯域幅集約型イベントが挙げられる。これらのイベントは、しばしば、現在のオーバーレイネットワークトポロジのノードおよびリンクを含む、インターネットの重要な部分に影響を与えるトラフィックおよび遅延の増加をもたらす。他の実施形態では、長期にわたるネットワークの停止および機器の故障（悪天候によって引き起こされても、他の要因によって引き起こされても）も、予測エンジン４５５ｂへの入力として含まれる。上述したように、このような情報は、ネットワークトラフィックを経時的に監視することによって直接取得してもよく、またはインターネットトラフィックを監視し、経時的に特定のトラフィックパターンを明らかにする地域またはグローバルインターネット「トラフィックマップ」を時折構築する第三者から間接的に取得してもよい。
【０２３７】
図６Ｂに目を向けると、リンク中継分類器６００ｂは、予測を生成する際のトポロジセレクタ４５８ｂによるその訓練ならびにその使用に関して、ノード中継分類器６００ａと非常に類似した様式で実行する。しかしながら、上述したように、リンク中継分類器６００ｂは、リンクがコンテンツセグメントを指定された子ノードに配信する能力に関する予測を生成する一方で、ノード中継分類器６００ａは、指定された親ノードがコンテンツセグメントを１つ以上の指定されていない子ノードに中継する能力に関する予測を生成する。この区別は微妙なものに見えるかもしれないが、図７Ａ〜図７Ｅを参照してより詳細に後述するように、定義されたパフォーマンス基準を満たすオーバーレイネットワークトポロジを識別するトポロジセレクタ４５８ｂの状況では非常に重要である。
【０２３８】
図６Ａを参照して上述した例を考慮すると、ここでは、親ノードＡは、現在子ノードＢおよびＣに同時にコンテンツを中継しているため、リンクＡ→ＢおよびＡ→Ｃは、現在のオーバーレイネットワークトポロジの一部である。ノード中継分類器６００ａのために生成された単一の訓練サンプルとは異なり、リンク中継分類器６００ｂ用の２つの訓練サンプル、つまり、Ａ→Ｂリンクに関するものとＡ→Ｃリンクに関する別のものが、この例の状況で生成されることになる。
【０２３９】
いずれかの訓練サンプルに関連付けられているリンクに関して、リンク中継分類器６００ｂへの入力６１０ｂは、リンクに沿った往復ｐｉｎｇ時間、リンクの親および子に関する相対的ノードメトリック、特定のＱｏＳおよびＱｏＥメトリック、ならびにその他のリンク中継属性などのリンクメトリック６１２ｂを含む。入力６１０ｂはまた、（ノード中継分類器６００ａおよびノードメトリック６１２ａに関して上述したように）リンクメトリック６１２ｂが収集された時間期間を表すメトリックタイムスタンプ６１４ｂも含む。
【０２４０】
リンク中継分類器６００ｂの出力６３０ｂは、（複数のリンクの同時パフォーマンスを潜在的に反映するノード中継分類器６００ａの出力６３０ａとは対照的に）単一リンクの観測されたパフォーマンスまたは予測された容量を表す。上記の例のＡ→Ｂリンクに関する訓練サンプル出力６３０ｂが５ｍｂｐｓに等しいのに対し、Ａ→Ｃリンクに関する訓練サンプルは３ｍｂｐｓに等しい。一実施形態では（ノード中継分類器６００ａと同様に）、リンク中継分類器６００ｂは、１つ以上のメトリックの関数として予測されたリンク中継容量６３２ｂ（および実際の観測されたパフォーマンス）を生成し、単一の値を生成する。他の実施形態では、これは複数の出力値を生成する。
【０２４１】
ノード中継分類器６００ａの場合と同様に、（一実施形態では）実際に観測されたパフォーマンスが容量制限のある（需要が容量を超える場合）観測を反映するか、または需要制限のある（容量が需要以上の場合）観測を反映するかにかかわらず、リンク中継分類器６００ｂへのすべての訓練サンプルが含まれる。他の実施形態では、中継容量をより良く予測するために、リンク中継分類器６００ｂへの訓練サンプルは、それらが容量制限であるかまたは需要制限であるかに基づいて分離される。その結果（この分離が複数の分類器で実装されるか、または単一の分類器の別々の構成要素で実装されるかにかかわらず）、リンク中継容量の予測が予想リンクに関して要求されると、リンク中継分類器６００ｂは最初に、予測された容量が子ノードの需要を満たすかどうかを決定する。一実施形態では、リンク中継分類器６００ｂは、バイナリ（「はい」または「いいえ」）結果のみを生成する。別の実施形態では、そのような需要が満たされない場合、リンク中継分類器６００ｂは、予測された容量（例えば、４ｍｂｐｓ、３ｍｂｐｓなど）をさらに生成する。パフォーマンス基準およびその他の要因に応じて、トポロジセレクタ４５８ｂはこのようなリンクを引き続き使用することができる（例えば、より良いリンクが利用できない場合、またはパフォーマンス基準が平均５ｍｂｐｓの需要を課すが、個々の子ノードごとではない場合）。
【０２４２】
ノード中継分類器６００ａと同様に、リンク中継分類器６００ｂは、予測（この場合、リンク中継容量６３２ｂの予測）を継続的に生成し、これを実際の観測された出力値と比較して経時的に誤差を徐々に減少させる。また、この予測は、各時間期間中、および連続する時間期間（同じ訓練データセットの繰り返し送信を含む）にわたって実際に観測されたリンクに関連付けられている訓練サンプルに依存しているため、特定のノードおよびリンクの属性を記憶する必要性が除かれる。
【０２４３】
リンク中継分類器６００ｂがトポロジセレクタ４５８ｂによって使用されて、予想リンクのリンク中継容量６３２ｂを予測すると、それに指定された予想リンク（おそらく実際に観測されたオーバーレイネットワークトポロジの一部になったことがないものでも）に関連する入力６１０ｂ（現在サンプリングされたリンクメトリック６１２ｂおよびタイムスタンプ６１４ｂ）が供給される。これらの入力６１０ｂに基づいて、リンク中継分類器６００ｂは、そのリンクの指定された子ノードにコンテンツを配信するリンクの能力を反映する、その指定されたリンクのリンク中継容量６３２ｂの予測を生成する。
【０２４４】
ノード中継分類器６００ａの場合のように、１つ以上の隠れ層６２０ｂが、リンク中継分類器６００ｂの複数の入力６１０ｂと出力６３０ｂとの間のより複雑な相関を容易にするために使用される。ここでも、個々の隠れニューロン６２１ｂは、中間状態値（そのようなニューロン６２１ｂへの入力の加重和または他のより複雑な関数として計算される）を表す。この実施形態では、訓練中に順伝播プロセスが使用され、これらの中間状態を介して入力６１０ｂの値を変換して、各訓練サンプルで提供される実際の出力値と比較される予測されたリンク中継容量６３２ｂ値を生成する。逆伝播プロセスを使用して、隠れニューロン６２１ｂによって使用される重みを調整して、これらの中間状態値を計算する。
【０２４５】
ここでも、タイムスタンプ６１４ｂは、トポロジセレクタ４５８ｂによるリンク中継分類器６００ｂの使用中に、指定された予想リンクに関するリンク中継容量６３２ｂ識別の予測を生成するために、各訓練サンプルのメトリックが収集された時間期間（現在の時間期間を含む）を表す。さらに、ノード中継分類器６００ａと同様に、タイムスタンプ６１４ｂは、時間メトリックに関して、したがって、上述したように繰り返される時間依存パターン（追加の外部指標の使用を含む）に関して、リンクメトリックのリンク中継パフォーマンスへの相関を容易にする。
【０２４６】
一実施形態では、予想親ノードのノード中継容量６３２ａおよび予想リンクのリンク中継容量６３２ｂは、１つ以上のメトリック（例えば、ユーザの経験を最もよく表すＱｏＥメトリック）のアプリケーション固有の機能として定義される。単純な関数には、ｍｂｐｓで測定される単一のスループットメトリックのみが含まれる場合がある。
【０２４７】
他の実施形態では、ノード中継容量６３２ａおよびリンク中継容量６３２ｂは、適応トポロジサーバ３００ｃによって収集または取得された任意またはすべてのメトリックを潜在的に含む、複数のメトリックのより複雑な関数として定義される。特定のアプリケーション（またはコンテンツアイテム）に関して使用される特定の機能は、（現在または将来の）下位ネットワーク輻輳に照らして、特定のノードおよびリンクの相対的なパフォーマンスを区別することを目的とした設計およびエンジニアリングのトレードオフの結果であることは、当業者には明らかであろう。
【０２４８】
しかし、上述したように、計算および定量化されたノード中継容量６３２ａは、１つ以上の指定されていない子ノードにコンテンツセグメントを中継する予想親ノードの能力を表す一方で、リンク中継容量６３２ｂは、そのリンクの指定された子ノードにコンテンツセグメントを配信する予想リンクの能力を表す。
【０２４９】
一実施形態では、訓練サンプルの代表的なセットは、所定の「履歴継続時間」（通常、数ヶ月または数ヶ年といった比較的長い期間）にわたって生成される。訓練サンプルの各セットは、ノード中継分類器６００ａおよびリンク中継分類器６００ｂを訓練するために、繰り返し使用される。例えば、一実施形態では、メトリックが収集される各時間期間の継続時間は１秒である一方で、履歴継続時間は２年である。他の実施形態では、無制限の履歴継続期間が使用される。
【０２５０】
メトリックは１秒ごとに訓練サンプルとして収集、処理、および送信されるが、履歴継続時間期間中に取得されたメトリックのセットも繰り返し送信される（複数の「エポック」または以前に送信された訓練サンプルの繰り返しにわたって）。このような様式で、ノード中継分類器６００ａおよびリンク中継分類器６００ｂは、比較的最近のメトリックを用いて継続的に「再訓練」される。一実施形態では、任意の履歴継続時間期間中に十分に多様な訓練サンプルのセットを受信すると、ノード中継分類器６００ａおよびリンク中継分類器６００ｂは、「十分に訓練された」とみなされ、トポロジセレクタ４５８ｂからの要求に応じて、それぞれのノード中継容量６３２ａおよびリンク中継容量６３２ｂの予測を生成する。
【０２５１】
上記で示唆したように、ノード中継分類器６００ａおよびリンク中継分類器６００ｂは、将来および現在のネットワーク輻輳に関するそれぞれのノード中継容量６３２ａおよびリンク中継容量６３２ｂの予測を生成する。一実施形態では、そのような予測は、対応する訓練サンプル入力に対して時間的に遅れのある訓練サンプル出力を使用するノード中継分類器６００ａおよびリンク中継分類器６００ｂの結果としての将来のネットワーク輻輳を反映する。
【０２５２】
例えば、入力メトリックが「時間ｎ」において収集された場合、分類器に送信される実際の観測された出力メトリックは、後で（例えば、「時間ｎ＋５」、すなわち５秒後に）収集されたものである。遅れのある出力メトリックで分類器を訓練することにより、後続のノード中継容量６３２ａおよびリンク中継容量６３２ｂの予測は、そのような予測に対する将来のネットワーク輻輳の影響を反映する。別の実施形態では、出力メトリックは遅れず（すなわち、０秒間の遅れ）、これらの予測に対して現在のネットワーク輻輳の影響を反映する。経時的なネットワーク輻輳の重大な変化の頻度を適切に反映するために使用される遅れの量は、アプリケーション固有であり、様々な周知かつ独自の統計手法によって決定されることは当業者には明らかであろう。
【０２５３】
ｃ．トラフィック需要の予測
一実施形態では、宛先ノードの需要は、アプリケーションによって定義される（例えば、各子ノードからの５ｍｂｐｓの需要）。オーバーレイネットワーク上のそのような宛先ノードの存在は、そのような宛先ノードがオーバーレイネットワークに参加またはオーバーレイネットワークを離脱する時間を監視する適応トポロジサーバ３００ｃに既知である。
【０２５４】
さらに、異なる宛先ノードは、（測定されたかまたは予測されたかにかかわらず）異なるトラフィック需要を有することがある。例えば、ブロードキャストビデオシナリオでは、特定の視聴ノードがＨＤビデオをストリーミングする能力を有する場合があるが、他のノードはＳＤビデオに制限される場合がある。そのような異なる需要の知識は、（定義されたパフォーマンス基準に従って）そのような異なる需要を満たすために過剰容量を再配布するオーバーレイネットワークトポロジを決定する際のトポロジセレクタ４５８ｂのタスクを容易にする。
【０２５５】
他の実施形態では、予測エンジン４５５ｂを使用して、特定の宛先ノードの存在を閲覧者として予測する（例えば、バイナリ「閲覧者指標」従属変数によって表される）。言い換えれば、予測エンジン４５５ｂを使用して、例えば、様々なメトリックによって反映される、そのような視聴ノードの以前の動作に基づいて、どの視聴ノードがオーバーレイネットワークトポロジの一部になるかを予測する。
【０２５６】
さらに、予測エンジン４５５ｂは、そのような視聴ノードの「セッション継続時間」を（以前の動作から）予測するためにも使用される。例えば、一実施形態では、セッション継続時間がより長い視聴ノードは、トポロジの安定性を高めるために、オーバーレイネットワークトポロジのより上位レベルに配置される（オーバーレイネットワークトポロジのより上位レベルでの変更はより大きな影響を与え、比較的より多くのリンクの変更をもたらすため）。
【０２５７】
経時的に、宛先ノードはネットワークに参加し、そしてネットワークを離脱する。予測エンジン４５５ｂを使用して、そのような決定を観測されたメトリック（宛先ノードがコンテンツアイテムを消費するためにネットワークに参加する時間の量を含む）と相関させることによって、特定のノードが任意の所与の時間にネットワークの一部になるかどうかを予測することができる（それだけでなく、オーバーレイネットワーク内の任意の所与の時間におけるノードの総数を予測する累積情報を提供することができる）。
【０２５８】
ネットワークから頻繁に切断するノードとネットワーク上に残る可能性が高いノードとを区別することは、重大な利点を提供する。例えば、（視聴者の意図に起因するか、またはデバイスの問題に起因するかにかかわらず）ネットワークから頻繁に切断するノードは、特にオーバーレイネットワークトポロジの比較的上位のレベルで構成されている場合、重大な中断を引き起こす。そのようなノードがネットワークから消えるたびに、オーバーレイネットワークトポロジを少なくとも部分的に再構成する必要があり、その結果、そのようなノードからダウンストリームに「波及」効果がもたらされる。そのようなノードをオーバーレイネットワークトポロジの下位レベルに配置することによって、そのような影響は軽減される。逆に、セッション継続時間がより長いノードをオーバーレイネットワークトポロジのより上位レベルに配置すると、再構成の頻度およびその結果として生じる中断が最小化されるため、より大きい安定性が提供される。
【０２５９】
そのような継続時間が短いかまたは継続時間が長いノードがネットワークに参加する可能性が高いかどうかを事前に知ることで（例えば、視聴者指標の予測を介して）、事前の計画が可能になり、これにより、オーバーレイネットワークトポロジの再構成を実装するために必要な時間が最小化される。さらに、一実施形態では、視聴者指標およびセッション継続時間の予測に基づいて視聴者の累積数が決定され、これにより、トポロジセレクタ４５８ｂは、累積視聴者の予測数に最適化されたオーバーレイネットワークトポロジを構成できるようになる。視聴者の累積数だけでなく、視聴者の個々のセッション継続時間または平均セッション継続時間に基づくオーバーレイネットワークトポロジの様々な最適化（ヒューリスティックアルゴリズムの使用を含む）は、当業者には明らかであろう。
【０２６０】
２．トポロジセレクタ
上位レベルにおいて、トポロジセレクタ４５８ｂは、定義されたアプリケーション固有のパフォーマンス基準を満たすオーバーレイネットワークトポロジを決定する。トポロジセレクタ４５８ｂは、特定の主要なリソースを使用してこのタスクを容易にする。一実施形態では、予測エンジン４５５ｂを使用して、指定された予想ノードおよびリンクの中継容量の予測を生成し、アプリケーションによって定義される既知の需要およびネットワークに参加およびネットワークを離脱するノードの監視に依存する。他の実施形態では、予測エンジン４５５ｂは、パフォーマンス基準を満たすオーバーレイネットワークのトポロジセレクタ４５８ｂによる決定を容易にするために視聴者指標およびセッション継続時間の予測を生成する。
【０２６１】
一実施形態では、トポロジセレクタ４５８ｂは、トラフィックをシフトする目的で（例えば、追加のノードをそのような親ノードの子ノードとして接続することによって）既存および予想親ノードの過剰容量（存在する場合）を決定して、そのような過剰容量を再配布する。そのような過剰容量を計算するために、トポロジセレクタ４５８ｂは、既知のまたは予測された中継容量情報と共に既知または予測されたトラフィック需要を利用する。
【０２６２】
一実施形態では、トポロジセレクタ４５８ｂは、ノードの相対的な中継容量に基づいてノードを分類する。ローカルノード中継容量６３２ａおよびリンク中継容量６３２ｂの予測は、ローカルノードおよびリンクレベルでのみであるが、そのような中継容量情報を提供する。
【０２６３】
例えば、Ａ→ＢおよびＡ→Ｃリンクの予測されたリンク中継容量６３２ｂ値は、ノードＡがノードＢまたはノードＣの好適な親であることを示すには十分であり得るが、ノードＡがコンテンツをノードＢおよびノードＣの両方に同時に中継する適切な過剰中継容量を有しているかどうかを決定するには不十分である。トポロジセレクタ４５８ｂは、予測エンジン４５５ｂからノードＡに対するノード中継容量６３２ａの値を要求することによって、そのような情報を取得し得る。
【０２６４】
しかし、トポロジセレクタ４５８ｂはまた、任意の予想オーバーレイネットワークトポロジのノードおよびリンクの間の相互依存性も考慮する。例えば、ノードＡへのリンクがノードＡからの需要を満たすのに十分でない限り（例えば、５ｍｂｐｓ）、別の方法で十分な中継容量が予測されていても、ノードＡは、ノードＢまたはノードＣの需要を満たすことができない。したがって、トポロジセレクタ４５８ｂは、予測エンジン４５５ｂによって生成されたローカルのノード中継容量６３２ａおよびリンク中継容量６３２ｂの予測を利用するが、いずれかの予想オーバーレイネットワークトポロジが定義されたパフォーマンス基準を満たすかどうかのグローバル評価も実行する。
【０２６５】
上記で示唆したように、ノードＡが現在子ノードを有していない場合でも、１つ以上の子ノードにコンテンツを中継するための過剰容量を有する場合がある。例えば、ノードＡ（または同様の属性を有する「代理」ノード）が履歴として複数の子ノードにコンテンツを同時に中継したことがある場合、予測エンジン４５５ｂは、ノードＡの子ノード（存在する場合）の現在の総需要を超えるノード中継容量を生成する場合がある。
【０２６６】
予想親ノード（最初の子ノードを追加するか、または追加の子ノードを追加するかどうかにかかわらず）は、特定の子ノードに関してのみ（例えば、他の子ノードへのリンクに沿った輻輳に起因する）過剰容量を有する場合があることに留意されたい。トポロジセレクタ４５８ｂは、リンク中継容量６３２ｂの予測を利用して、これに関して好適な子ノードを識別する。
【０２６７】
より詳細に後述するように、トポロジセレクタ４５８ｂは、任意の所与のオーバーレイネットワークトポロジおよびその構成要素ノードおよびリンクの予想パフォーマンスに対する（グローバルトポロジレベル、ならびにローカルノードおよびリンクレベルでの）ネットワーク輻輳の影響に加えて、オーバーレイネットワークトポロジの状況内のアップストリームノードおよびリンクの相互依存性を考慮する。
【０２６８】
本質的に、トポロジセレクタ４５８ｂは、新しいかまたはより良い親を必要とするノードに過剰容量を再配布する程度に基づいて、予想オーバーレイネットワークトポロジを評価することによって、パフォーマンス基準を満たすオーバーレイネットワークトポロジを識別するタスクを実行し、すなわち、パフォーマンス基準を満たすためにネットワークトラフィックをシフトする。これによってトポロジセレクタ４５８ｂがこの機能を実装して、定義されたパフォーマンス基準を満たすオーバーレイネットワークトポロジを識別する様式は、図７Ａ〜図７Ｅ（トポロジセレクタはグローバルトポロジレベルの分析を実行する）および図７Ｆ（トポロジセレクタはローカルまたは部分的なトポロジレベルの分析を実行する）を参照してより詳細に後述される。
【０２６９】
一実施形態では、トポロジセレクタ４５８ｂは、非線形および多次元最適化技法を使用して、パフォーマンス基準を満たす最適なオーバーレイネットワークトポロジを生成することに留意されたい。他の実施形態（後述する）では、様々なヒューリスティックおよび他の変換が使用される。これらの変換の任意のサブセットを、本発明の範囲内の様々な異なるシーケンスで使用できることは、当業者には明らかであろう。
【０２７０】
トポロジセレクタ４５８ｂはまた、予想オーバーレイネットワークトポロジの評価を容易にするために、（一実施形態では）予測エンジン４５５ｂからの需要の予測（視聴者指標およびセッション継続時間の予測を含む）を要求する。例えば、トポロジセレクタ４５８ｂは、特定の「スーパーノード」を予想親ノードとして選択することによって、およびそれらをオーバーレイネットワークトポロジの比較的上位のレベルに配置することによって、このスーパーノードに優先順位を与える。そのようなスーパーノードは、ユーザがプレミアムサービスの料金を支払った「加入者」ノード、ならびに比較的高いノード中継容量および比較的長い予測されたセッション継続時間を有するノード（例えば、常時接続のセットトップボックス）を含む。より詳細に後述するように、トポロジセレクタ４５８ｂは、セッション継続時間に対する過剰容量を効果的にバランスさせて、ノードが頻繁にネットワークを離脱するときに生じる混乱を最小化する。
【０２７１】
ａ．グローバルトポロジレベルの分析
図７Ａに目を向けると、図表７００ａは、トポロジセレクタ４５８ｂによる初期構成に続くオーバーレイネットワークトポロジの状態の一実施形態を例示している。ＰＯＩまたはソースノード７１０ａから始めて、トポロジセレクタ４５８ｂは、（例えば、「参加」要求に応じて）オーバーレイネットワークに経時的にノードを追加し、また（例えば、ノードがネットワークを離脱するか、そうでなければ応答しなくなると）オーバーレイネットワークからノードを削除し、これは、既存のリンクを追加、削除、またはその他の方法で変更することによって、オーバーレイネットワークトポロジのある程度の再構成を必要とする（より詳細に後述する、パフォーマンスの問題に対処し、パフォーマンス基準を満たすためのオーバーレイネットワークトポロジの再構成は別として）。
【０２７２】
図表７００ａは、少数のノード（Ａ−Ｖ）が追加された後の初期構成を例示する。上述したように、ピアベースのオーバーレイネットワークトポロジを使用すると、トポロジセレクタ４５８ｂがピアノード自体の過剰容量を活用し、そのような過剰容量をその他の方法で容量制限のあるリンクに再配布することによってトラフィックをシフトすることができる。
【０２７３】
当初、トポロジセレクタ４５８ｂには、ネットワークに参加する初期ノードを相互接続する方法を決定するための利用可能なパフォーマンスデータがほとんどないか、またはまったくない。一実施形態では、トポロジセレクタ４５８ｂは、ローカル中継容量の予測に依存して、初期オーバーレイネットワークトポロジを確立する。例えば、第１のノードＡは、ソースノード７１０ａに接続される。しかし、第２のノードＢもまた、ソースノード７１０ａに接続されてもよく、またはノードＡの子ノードとして接続されてもよい。
【０２７４】
このような初期決定は、（上述したように）予測エンジン４５５ｂに供給される初期ノードの既知の属性（ノードのアップリンク速度など）、ならびに「代理」ノードおよびリンクの同様の属性に基づいているため、パフォーマンスデータが比較的少ないにもかかわらず恣意的ではない。経時的に、トポロジセレクタ４５８ｂは、図表７００ａに示すように、１つ以上の子ノードにコンテンツを中継するための過剰容量を有するノードを識別する目的で、（予測エンジン４５５ｂからの中継容量の予測に基づいて）徐々により正確な中継容量情報を取得する。
【０２７５】
例示されたカテゴリ７２０ａは、低、中、および高の中継容量を含むが、これらの３つのカテゴリは、図表７００ａの説明を簡略化するために提供されている。他の実施形態では、より少ないかまたはより多いカテゴリが使用される。さらに別の実施形態では、トポロジセレクタ４５８ｂは、オーバーレイネットワーク内のすべてのノードのノード中継容量６３２ａを利用する。
【０２７６】
図表７００ａは、オーバーレイネットワークに参加したノードの初期セットとして構成された、「最上位」レベル７３０ａ（ソースノード７１０ａに最も近い）におけるノードＡ−Ｅ、次のレベル７４０ａにおけるノードＦ−Ｎ、第３のレベル７５０ａにおけるノードＯ−Ｕ、および最後の第４の「最下位」レベル７６０ａにおけるノードＶが続く、４レベルのオーバーレイネットワークトポロジを例示する。
【０２７７】
改善７６５ａは、この初期構成プロセスの主要な結果の要約である。例えば、親ノードＥは「低」中継容量を有するが、このシナリオでは、予測エンジン４５５ｂからのノード中継容量６３２ａの値は、ノードＮからのトラフィック需要を満たすのに十分である。
【０２７８】
さらに、ノードＮ（「中」の中継容量を有する）もまた、子ノードＴおよびＵからのトラフィック需要を同時に満たしている。同様に、ノードＢ（「高」の中継容量を有する）は、子ノードＧ、Ｈ、Ｉ、Ｊ、およびＫからのトラフィック需要を同時に満たしている。より詳細に後述するように、トポロジセレクタ４５８ｂは、親ノードＢおよびＮが複数の子ノードにコンテンツを同時に中継するための十分な過剰中継容量を有しているかどうかだけでなく、そのような子ノードの数および特定の好適な子ノードの識別情報も、（例えば、ローカルノード中継容量６３２ａの予測を分析することによって）決定する。例えば、上述したように、ノードＮなどの親ノードは、２つの子ノード（ノードＴおよびＵなど）にコンテンツを同時に中継するのに十分な過剰容量を有することがあるが、（例えば、より低いかまたは不十分なリンク中継容量６３２ｂの予測によって明らかであるように、このようなノードへのリンクに沿った輻輳に起因して）２つの異なる子ノードにコンテンツを中継しない。
【０２７９】
図表７００ａに例示されるこの初期オーバーレイネットワークトポロジを生成する際に、トポロジセレクタ４５８ｂによってこれまでに実行された作業にもかかわらず、残りの問題７７５ａに例示されるように、様々な問題が残る。一実施形態では、トポロジセレクタ４５８ｂは、現在のオーバーレイネットワークトポロジを再構成するかどうか（例えば、オーバーレイネットワークトポロジを改善または最適化するかどうか、または、現在、パフォーマンス基準を満たしているかどうか）を決定する前に、パフォーマンス基準がこのプロセスの各段階で満たされるかどうかを決定することに留意されたい。
【０２８０】
このシナリオでトポロジセレクタ４５８ｂが残りの問題７７５ａに対処すると仮定すると、トポロジセレクタ４５８ｂは、ノードＧが現在、４つの子ノードＯ、Ｐ、Ｑ、およびＲからの累積トラフィック需要を満たしていないと決定する。例えば、これらの４つのリンクに関するリンク中継容量６３２ｂの予測のうちの１つ以上は、その特定のリンク（複数可）に対するトラフィック需要が満たされていないことを示す場合がある。Ｐ→Ｖリンクに関する同様の予測は、そのリンクのトラフィック需要が満たされていないことも示している。これらの問題に対するトポロジセレクタ４５８ｂによる応答は、図７Ｂを参照して後述される。
【０２８１】
他のより一般的な問題は、比較的低い中継容量ノード（例えば、ノードＡ、Ｃ、およびＥ）がオーバーレイネットワークトポロジの上位レベルに存在するという事実を含む。比較的より低い中継容量ノードへのアップストリームの依存性により、パフォーマンス基準を満たすことができなくなり、オーバーレイネットワークトポロジのレベルを「波及して低下させる」可能性がある。
【０２８２】
さらに、このシナリオでは、多くのノードからのトラフィック需要は、それらの親ノードによって満たされるが、そのような親ノードの過剰容量は、現在のオーバーレイネットワークトポロジの容量制限のあるリンクを通して配布されない。その結果、容量制限の問題は将来発生する可能性が高くなる。理想的なシナリオでは、容量制限のあるリンクの需要を満たすために過剰容量を再配布するようにトラフィックがシフトされることになる一方で、同様の将来の懸念に対処するために追加の過剰容量は利用可能のままである。
【０２８３】
これらのより一般的な問題に対するトポロジセレクタ４５８ｂによる応答は、図７Ｃおよび図７Ｄを参照して後述される。図７Ｂ〜図７Ｅで説明される解決策は、一実施形態では、単一の再構成プロセスの一部として並行して実行されることに留意されたい。他の実施形態では、これらのプロセスのサブセットは特定の順序で実行され、パフォーマンス基準を満たす置き換えオーバーレイネットワークトポロジをトポロジセレクタ４５８ｂが識別すると、任意の時点で終了されてもよい。それにもかかわらず、最適なオーバーレイネットワークトポロジを識別するプロセスの一部として、または単にパフォーマンス基準を満たすオーバーレイネットワークトポロジを識別するプロセスの一部として、トポロジセレクタ４５８ｂが現在のオーバーレイネットワークトポロジをどのように改善するかを例示する目的で、以下にこれらのプロセスの各々が個々に説明される。
【０２８４】
図７Ｂに目を向けると、図表７００ｂは、トポロジセレクタ４５８ｂが特定の「低パフォーマンス」変換を実行した後の図７Ａに例示されるオーバーレイネットワークトポロジの修正された状態（ソースノード７１０ｂから供給される）を例示する。上述したように、トポロジセレクタ４５８ｂは、（例えば、パフォーマンス基準がすでに満たされている場合）そのような変換を実行しないことを選択してもよく、または図７Ａ〜図７Ｅに示される変換（または図７Ｆに示されているようなローカルの部分的なトポロジ分析）のうちのいずれかを任意の順序で実行することを選択してもよい。そのような設計およびエンジニアリングのトレードオフが、本発明の趣旨から逸脱することなく実施され得ることは、当業者には明らかであろう。
【０２８５】
改善７６５ｂに示すように、トポロジセレクタ４５８ｂは、ノードＶを異なる親（ノードＩ）に割り当てることによって、Ｐ→Ｖリンクの低パフォーマンスを解決し、これにより、Ｉ→Ｖリンクを作成する。一実施形態では、ノードＩは、親ノードＩに関するノード中継容量６３２ａの予測、およびＩ→Ｖリンクに関するリンク中継容量６３２ｂの予測に部分的に基づいて選択される。例えば、ノードＩおよびノードＭは両方とも、子ノードを有しない「中」容量ノード（凡例７２０ｂ）であり、したがって、潜在的により大きな過剰容量を有する。このシナリオでは、Ｉ→Ｖリンクに関するリンク中継容量６３２ｂの予測は、Ｍ→Ｖリンクの予測を超えた。
【０２８６】
他の実施形態では、（例えば、ホップ数を減少させることによって）レイテンシを減少させる努力において、そのレベル７４０ｂ（以前の親ノードＰのレベル７５０ｂよりも１レベル上位である）に基づいて親ノードＩが選択される。この実施形態では、この変更の効果がより多くのオーバーレイネットワークトポロジを「波及して低下させ」、したがってより多くの（潜在的に破壊的な）ダウンストリームの影響を有するため、さらに上位のレベル（例えば、７３０ｂ）から親を選択することは破壊的すぎるとみなされる。このレベルの破壊を最小化する決定は、トポロジセレクタ４５８ｂの機能の実装で行われた設計およびエンジニアリングのトレードオフの一例にすぎない。
【０２８７】
同様に、トポロジセレクタ４５８ｂは、ノードＲを「過負荷の」親ノードＧから切断し、新しい親ノードＪを選択してＪ→Ｒリンクを形成する。このシナリオでは、子ノードＲは、（親ノードＧの他の子ノードＯ、Ｐ、およびＱの予測と比較すると）比較的より低いリンク中継容量６３２ｂの予測に基づいて切断された。さらに、トポロジセレクタ４５８ｂは、（他の要因の中でも）親ノードＪのノード中継容量６３２ａならびにＪ→ＲおよびＪ→Ｓリンクのリンク中継容量６３２ｂに基づいて、親ノードＪがノードＲおよびノードＳの両方にコンテンツを同時に中継するのに十分な過剰容量を有していると決定した。
【０２８８】
ノードＭ（「中」の中継容量も有する）は現在の子ノードを有していなかった（したがって、潜在的に過剰容量を有していた）が、（ノードＭに関する）ノード中継容量６３２ａの予測および（Ｍ→Ｒリンクに関する）リンク中継容量６３２ｂの予測は、このシナリオでは、（ノードＪはすでに既存の子ノードＳを有していたにもかかわらず）潜在的な親ノードＪを「アウトスコア」するには十分に高くなかったことが留意される。ここでも、本発明の趣旨から逸脱することなく、（切断されたノードＲに対して十分なまたは最適な親ノードを選択するために行われる）様々な設計およびエンジニアリングのトレードオフが当業者には明らかであろう。
【０２８９】
「低パフォーマンス」リンクに関するこれらの改善７６５ｂにもかかわらず、残りの問題７７５ｂはまだ対処されていない。一実施形態では、パフォーマンス基準が満たされる場合、トポロジセレクタ４５８ｂは、現在のオーバーレイネットワークトポロジに対する潜在的な置き換えとして図表７００ｂに例示される再構成されたオーバーレイネットワークトポロジを選択する。他の実施形態では、トポロジセレクタ４５８ｂは、オーバーレイネットワークトポロジをさらに改善する（または、一実施形態では最適化する）ことを追求する。
【０２９０】
例えば、比較的低い中継容量を有するノード（ノードＡ、Ｃ、およびＥなど）は、オーバーレイネットワークトポロジの上位レベル７３０ｂにおいてまだ存在している。上述したように、このようなノードに依存するダウンストリームの影響により、オーバーレイネットワークトポロジのより下位レベルにおいてトラフィック需要を満たすための様々な障害がもたらされ、これにより、パフォーマンス基準を満たすことができなくなる。さらに、このシナリオでは、ノードＭおよび他のノードなどのノードから過剰容量を再配布することによって、追加の容量制限のあるリンクに対処する必要がまだある。トポロジセレクタ４５８ｂがこれらの残りの問題７７５ｂに対処する様式は、図７Ｃを参照して後述される。
【０２９１】
図７Ｃの図表７００ｃは、トポロジセレクタ４５８ｂが特定の「レベルシフト」変換を実行した後の、図７Ｂに示されるオーバーレイネットワークトポロジの修正された状態を例示する。上述したように、図７Ａ〜図７Ｅに関して示した変換の順序および範囲（ヒューリスティック技法に加えて、またはその代わりに非線形および多次元最適化を使用するかどうかに関する決定を含む）が、本発明の範囲内の設計およびエンジニアリングのトレードオフの結果である。
【０２９２】
改善７６５ｃに示すように、トポロジセレクタ４５８ｂは、ノードＡ、Ｃ、およびＥをレベル７３０ｃからレベル７４０ｃに下へシフトすることによって、比較的上位のレベルのオーバーレイネットワークトポロジに存在する比較的より低い中継容量ノード（凡例７２０ｃ）の問題を解決する一方で、ノードＧ、Ｊ、およびＮをレベル７４０ｃからレベル７３０ｃに昇格させる。ノードＢ（高い中継容量を有する）は、まだ５つの子ノードにコンテンツを中継している。しかし、ノードＧおよびＪがレベル７３０ｃに昇格したため、ここではノードＢは、（ノードＨ、Ｉ、Ｋに加えて）ノードＡおよびＣにコンテンツを中継している。このような「レベルシフト」変換の結果として、オーバーレイネットワークトポロジのより上位レベルに存在する可能性のある容量制限のあるリンクが少なくなる。
【０２９３】
さらに、比較的より高い中継容量のノード（Ｇ、Ｊ、およびＮなど）は、コンテンツをより上位レベルで子ノードへと中継するようになり、最終的にレイテンシの短縮がもたらされる。例えば、ノードＧ（現在、レベル７３０ｃ）は、まだコンテンツを子ノードＯ、Ｐ、およびＱ（現在、レベル７４０ｃ）に中継しているが、これらのノードはソースノード７１０ｃにより近いネットワーク近接度にあり、オーバーレイネットワークトポロジの最下位のレベル７５０ｃにおけるより少ないノードのままである（したがって、全体的なホップ数がより少ない）。上述したように、ソースノード７１０ｃからのホップ数は、（決定的ではないが）全体的なパフォーマンスに関連する要因である。
【０２９４】
最後に、ノードＫは、ここでは（以前の低い中継容量ではなく）中程度の中継容量を有するように分類されるようになることに留意されたい。これは、ノードの中継容量が予想子ノードに関して変化するだけでなく、パフォーマンスメトリックの変化に基づいて経時的に変化することを例示している。上述したように、このような変化は、様々な要因の結果である場合がある。例えば、ノードＫのアップリンク速度は、所与の時間期間にわたって増加している可能性がある。または、ノードＫからその既存の子ノードへのリンクは、その時間期間にわたって輻輳が少なくなる可能性がある。これらの変化の理由に関係なく、トポロジセレクタ４５８ｂは、図７Ｄを参照して後述するように、そのような変化に適応する。
【０２９５】
一実施形態では、トポロジセレクタ４５８ｂは、セッション継続時間の予測を使用して、比較的より上位のまたはより下位レベルのオーバーレイネットワークトポロジでのノードの配置を容易にし、すなわち、セッション継続時間に対して容量をトレードオフする。例えば、上位レベルのオーバーレイネットワークトポロジに予測されたセッション継続時間が短い大容量ノードを配置すると、そのノードがネットワークを離脱するたびに、オーバーレイネットワークトポロジの追加の時間を要する再構成を含む、頻繁かつ重大な中断がもたらされる可能性があり、これにより、適応トポロジサーバ３００ｃが継続的にパフォーマンス基準を満たす能力に経時的に悪影響を与えることになる。
【０２９６】
これらの「レベルシフト」変換によってもたらされる改善７６５ｃにもかかわらず、まだ対処されていない残りの問題７７５ｃがまだ存在する。ここでも、パフォーマンス基準が満たされる場合、（一実施形態では）トポロジセレクタ４５８ｂは、現在のオーバーレイネットワークトポロジに対する潜在的な置き換えとして図表７００ｃに例示される再構成されたオーバーレイネットワークトポロジを選択する。他の実施形態では、トポロジセレクタ４５８ｂは、図７Ｄを参照して以下に示すように、オーバーレイネットワークトポロジをさらに改善する（または、一実施形態では最適化する）ことを追求する。
【０２９７】
残りの問題７７５ｃは、オーバーレイネットワークトポロジ内のどこか別の場所から過剰容量を再配布することによって、まだ対処されていない容量制限のあるリンクの存在を含む。例えば、このシナリオでは、リンクＢ→Ａ、Ａ→Ｆ、Ｇ→Ｑ、およびＣ→Ｌは、予測エンジン４５５ｂから取得したそれぞれのリンク中継容量６３２ｂの予測で示されるように、まだ容量制限がある。トポロジセレクタ４５８ｂがこれらの残りの問題７７５ｃに対処する様式は、図７Ｄを参照して後述される。
【０２９８】
図７Ｄの図表７００ｄは、トポロジセレクタ４５８ｂが特定の「過剰容量の再配布」変換を実行した後の、図７Ｃに例示されるオーバーレイネットワークトポロジの修正された状態を例示する。上述したように、図７Ａ〜図７Ｅに関して例示した変換の順序および範囲（ヒューリスティック技法に加えて、またはその代わりに非線形および多次元最適化を使用するかどうかに関する決定を含む）が、本発明の範囲内の設計およびエンジニアリングのトレードオフの結果である。
【０２９９】
改善７６５ｄに示すように、トポロジセレクタ４５８ｂは、様々なリンクを変化させて、そのようなリンクの子ノードを、過剰容量を有する（かつまた、一実施形態では、セッション継続時間の予測も十分に高い）親ノードに再割り当てすることによって、容量制限のあるリンクＢ→Ａ、Ａ→Ｆ、Ｇ→Ｑ、Ｃ→Ｌの問題を解決する。
【０３００】
例えば、トポロジセレクタ４５８ｂは、ノードＡをノードＢ（凡例７２０ｄで中継容量が大きい）から切断し、ノードＱをノードＧから切断することによって、（将来の）最上位のレベル７３０ｄ（ソースノード７１０ｄに最も近い）で過剰容量を解放した。また、ノードＦも容量制限のあるＡ→Ｆリンクから切断し、またノードＬを容量制限のあるＣ→Ｌリンクから切断した。
【０３０１】
以前にノードＮを（その過剰容量の評価に基づいて）レベル７３０ｄに昇格させ、トポロジセレクタ４５８ｂは、切断されたノードＦを（子ノードＥと合流する）ノードＮの２番目の子ノードとして割り当てた。ノードＮは、コンテンツを複数の子ノード（ＴおよびＵ）に中継するのに十分な容量を以前に実証したことに留意されたい。ただし、上述したように、その事実だけでは、Ｎ→Ｆリンクに沿った過剰容量を実証するには不十分であることに留意されたい。しかし、このシナリオでは、ノード中継容量６３２ａの予測（ノードＮに関する）およびリンク中継容量６３２ｂの予測（Ｎ→Ｆリンクに関する）は、このような過剰容量の十分な証拠を提供した。
【０３０２】
さらに、トポロジセレクタ４５８ｂは、切断されたノードＱを２番目の子ノードとして親ノードＩ（中継容量が中程度である）に割り当て、子ノードＶと合流した。また、切断されたノードＡおよびＬを親ノードＫ（最近、中程度の中継容量に昇格した）に割り当てた。これらの親の割り当て（レベル７４０ｄから７５０ｄ）は、以前は容量制限があったリンクの様々な子ノードに過剰容量を効果的に再配布する。
【０３０３】
その結果、重大な残りの問題７７５ｃは存在せず、トポロジセレクタ４５８ｂは、パフォーマンス基準が（少なくとも現時点では）満たされていることを確認した。トポロジセレクタ４５８ｂは、オーバーレイネットワークトポロジのより上位レベルで過剰容量を解放することによって、比較的上位のレベル（ソースノード７１０ｄからのホップ数がより少ない）で将来の容量制限の問題に対処するためのオプションを提供する。
【０３０４】
図７Ｅに目を向けると、フロー図７００ｅは、トポロジセレクタ４５８ｂによって実行される様々な初期構成および再構成変換の一実施形態を例示する。上述したように、他の実施形態では、トポロジセレクタ４５８ｂは、最適なオーバーレイネットワークトポロジを識別するか、またはパフォーマンス基準が満たされるまで、異なる順序でこれらの変換のサブセットを実行する。この機能は、本発明の趣旨から逸脱することなく、パフォーマンス基準を満たすために多くの異なるやり方で組み合わせることができることは当業者には明らかであろう。
【０３０５】
工程７１０ｅから始まり、トポロジセレクタ４５８ｂは、新しいノードおよび孤立したノードを識別する。上述したように、一実施形態では、新しいノードは適応トポロジサーバ３００ｃへの要求を開始する一方で、孤立したノードは、それらの親が明示的にネットワークを離脱するか、または事前定義された閾値値時間期間の間に応答できない場合、オーバーレイネットワークトポロジマネージャ３５０ｃによって識別される。他の実施形態では、予測エンジン４５５ｂは、トポロジセレクタ４５８ｂによるこの決定を容易にする視聴者指標およびセッション持続時間の予測を生成する。トポロジセレクタ４５８ｂは、パフォーマンスベースの再構成とは全く別に、新しい親を必要とするため、これらの新しいノードおよび孤立したノードを識別する。
【０３０６】
これらの新しいノードおよび孤立したノードに加えて、一実施形態では、トポロジセレクタ４５８ｂは、（図７Ｂを参照して上述したように）「低パフォーマンス」ノード（すなわち、容量制限のあるリンクの子ノード）も識別し、それらをそれらの現在の親ノードから切断する。この実施形態では、これらの新しいノード、孤立したノード、および切断されたノードは、新しい親に割り当てられるための優先順位になる。
【０３０７】
工程７２０ｅでは、トポロジセレクタ４５８ｂは、（図７Ａを参照して上述したように）現在のおよび予想親ノードのノード中継容量６３２ａを決定し、そのようなノードを適宜にランク付けする。上述したように、そのようなノードは、一実施形態ではカテゴリにランク付けされる一方で、他の実施形態では、そのようなノードは個々のノード中継容量６３２ａに従ってランク付けされる。
【０３０８】
工程７３０ｅでは、トポロジセレクタ４５８ｂは、（図７Ｂを参照して上述し、図７Ｆを参照して後述するように）低パフォーマンス変換を実行して、以前に識別された新しいノード、孤立したノード、および切断されたノードに新しい親を割り当てる。工程７４０ｅでは、トポロジセレクタ４５８ｂは、（図７Ｃを参照して上述したように）レベルシフト変換を実行して、比較的より高い中継容量を有するノードをオーバーレイネットワークトポロジのより上位レベルに昇格させる（かつ比較的より低い中継容量を有するノードをオーバーレイネットワークトポロジのより下位レベルに降格させる）。別の実施形態では、トポロジセレクタ４５８ｂはまた、任意の宛先ノードへのホップ数に事前定義された制限を課す。上述したように、そのような決定は、ノードおよびリンクの相互依存性、ならびにノード中継容量６３２ａおよびリンク中継容量６３２ｂの予測を考慮する。
【０３０９】
工程７５０ｅにおいて、トポロジセレクタ４５８ｂは、（図７Ｄを参照して上述したように）過剰容量の再配布変換を実行する。上述したように、必要に応じてトラフィックをシフトすることで一部の過剰容量を再配布する一方で、残りの過剰容量を（特に、オーバーレイネットワークトポロジのより上位レベルで）解放して、将来の容量制限の問題に対処する。上記の工程７４０ｅと同様に、このような決定では、ノードおよびリンクの相互依存性、ならびにノード中継容量６３２ａおよびリンク中継容量６３２ｂの予測を考慮する。
【０３１０】
一実施形態では、トポロジセレクタ４５８ｂは、工程７３０ｅ、７４０ｅ、および７５０ｅを繰り返し実行する。これらの工程の各々は、連続で実行されるか、または、別の実施形態では、例えば、結果として生じるオーバーレイネットワークトポロジが工程７７５ｅに従ってパフォーマンス基準を満たすまでの（または、他の実施形態では、最適なオーバーレイネットワークトポロジが生成されるまでの）、非線形および多次元最適化）の状況で、同時に実行される。工程７８０ｅでは、結果として生じる（パフォーマンス基準を満たすか、またはパフォーマンス基準を満たすことに最も近づく）オーバーレイネットワークトポロジが、現在のオーバーレイネットワークトポロジの潜在的な再構成のために選択される。
【０３１１】
図７Ａ〜図７Ｄは、比較的少数のノードを有するオーバーレイネットワークトポロジを例示するが、これらの概念は、事実上あらゆる数のノード、および本質的にあらゆるタイプの図表の相互接続リンクを含む非常に大きなオーバーレイネットワークトポロジに等しく適用可能である。一実施形態では、トポロジセレクタ４５８ｂは、予測エンジン４５５ｂを使用して、ノード中継容量６３２ａおよびリンク中継容量６３２ｂの予測を取得する一方で、需要は、定義されたパフォーマンス基準および視聴ノードの監視アクティビティに基づいて既知である。別の実施形態では、予測エンジン４５５ｂは、上述したように（視聴者指標およびセッション継続時間の予測に基づいて）需要を予測する。他の実施形態では、これらの容量関連および需要関連の値の一部またはすべてが予測されるのではなく測定される。
【０３１２】
一実施形態では、トポロジセレクタ４５８ｂは、パフォーマンス基準を満たす予想オーバーレイネットワークトポロジを識別すると、処理を停止し、上述したように、現在のオーバーレイネットワークトポロジの潜在的な置き換えのためにそのオーバーレイネットワークトポロジを配信する。他の実施形態では、トポロジセレクタ４５８ｂは、すべての予想オーバーレイネットワークトポロジを評価し、「最適な」トポロジを選択する。別の実施形態では、最適なトポロジは、パフォーマンス基準を「最も満たす」（または満たすことに最も近い）トポロジである。
【０３１３】
他の実施形態では、トポロジセレクタ４５８ｂは、予測エンジン４５５ｂにリンク中継容量６３２ｂの予測を要求する予想リンクの数を制限することによって、すなわち、適格な親ノードである可能性が最も低いノードを削減またはフィルタリングして削除することによって、予想オーバーレイネットワークトポロジの数を制限する。例えば、一実施形態では、トポロジセレクタ４５８ｂは、「最低パフォーマンス」ノードを選択し、そのようなノードを考慮から除外する。
【０３１４】
さらに別の実施形態では、トポロジセレクタ４５８ｂは、最初に予測エンジン４５５ｂからノード中継容量６３２ａの予測を取得し、潜在的な親として、最も高い予測された容量を有するノードのみを考慮する。例えば、潜在的な親ノードの８０％は、ノード中継容量６３２ａの予測の上位２０％において、それらのノードのみを選択することによって排除される。その結果、上位２０％のノードのみが指定された予想リンクの親であるため、予測リンク中継容量６３２ｂの予測の数が大幅に減少される。除外されたノードおよび／またはリンクの適切な数または割合の決定は、様々なアプリケーション固有の設計およびエンジニアリングのトレードオフの結果であることは、当業者には明らかであろう。
【０３１５】
ノード（およびしたがって、リンク）がトポロジセレクタ４５８ｂによって考慮から除外されるこれらの実施形態では、除外されたノードおよびリンクは、依然として識別された（再構成された）オーバーレイネットワークトポロジの一部としてコンテンツを受信する必要があるため、依然として考慮されなければならない。そのようなノードが現在親ノードではない場合、それらの包含（リーフノードとして）は、ダウンストリームの影響を受けない。しかしながら、そのようなノードが現在の親ノードである場合、トポロジセレクタ４５８ｂは、（一実施形態では）上述したプロセスの完了時に追加の工程を実行する。この追加の工程では、これらの除外された親ノードは「新しい」ノードとして再割り当てされ、それらの子ノードは「孤立した」ノードとして再割り当てされる。トポロジセレクタ４５８ｂは、その選択されたオーバーレイネットワークトポロジを効果的に再構成して、これらの新しいノードおよび孤立したノードを統合し、図７Ｆを参照して後述するアプローチを使用する。
【０３１６】
ｂ．ローカル（ノードおよびリンクレベル）分析
予想オーバーレイネットワークトポロジならびに構成要素リンクおよびノードの減少された順列を有するものを含む、上述したグローバルな「トポロジレベル」アプローチに加えて、トポロジセレクタ４５８ｂはまた、他の実施形態では、ローカル最適化を含むローカル（ノードおよびリンクレベル）アプローチも使用する。一実施形態では、トポロジセレクタ４５８ｂは、図７Ａ〜図７Ｅに関して上述した分析を実行する現在のオーバーレイネットワークトポロジのサブセットを選択する。例えば、上述したアップストリームの依存性の性質を考えると、ツリーベースのトポロジの下位レベルでの変化は、ダウンストリームに大きな影響を与える可能性が低くなる。
【０３１７】
一実施形態では、トポロジセレクタ４５８ｂは、パフォーマンス基準を満たす完全に独立した「新しい」オーバーレイネットワークトポロジを識別するのではなく、「ボトムアップ」アプローチで現在のオーバーレイネットワークトポロジの「より下」の部分を分析する。言い換えれば、トポロジセレクタ４５８ｂは、最低レベル（「リーフ」ノードに最も近い）から開始して、ツリーの各「レベル」を分析する。トポロジセレクタ４５８ｂは、所定の「割合改善」が達成されるまで（かつパフォーマンス基準が満たされるまで）ツリーの各連続したより上位レベルを分析し、その時点で再構成プロセスが終了する。
【０３１８】
他の実施形態では、トポロジセレクタ４５８ｂは、現在のオーバーレイネットワークトポロジの様々な構成要素領域の定期的なパフォーマンス評価を実行することによって識別される「トラブル領域」に基づいて、現在のオーバーレイネットワークトポロジの選択されたレベルのローカル最適化を実行する。言い換えれば、「パフォーマンスの低下」を示すトポロジの部分が再構成されるが、（上述したグローバルアプローチで考慮される）そのような再構成のダウンストリームの影響を明示的に考慮しない。
【０３１９】
図７Ｆのフロー図７００ｆに示される一実施形態では、トポロジセレクタ４５８ｂは、（「親中心」ではなく）代替の「子中心」アプローチを使用する。トポロジセレクタ４５８ｂは、分析する親ノード（およびしたがって、リンク）の数を制限するのではなく、パフォーマンス基準を満たすオーバーレイネットワークトポロジを全体的に識別するのとは対照的に、新しい親を「必要」とする子ノードを識別し、次いで、そのようなノードに対する「十分な」または「最適な」親を識別する。
【０３２０】
言い換えれば、ノードのそのサブセットへのリンクのみが変更される。これらのノードに新しい親ノードが割り当てられると、現在のオーバーレイネットワークトポロジ内の残りのリンクは（再構成されたオーバーレイネットワークトポロジが再評価されるまで）影響を受けない。
【０３２１】
例えば、工程７１０ｆでは、オーバーレイネットワークトポロジマネージャ３５０ｃは、新しい親ノードを必要とするピアノードの３つのグループを識別する。最初のグループは、トポロジセレクタ４５８ｂが現在のオーバーレイネットワークトポロジを最後に再評価してから、コンテンツアイテムの視聴（消費）を要求した新しいノードを含む。２番目のグループは、親ノードがネットワークを離脱したか、またはコンテンツアイテムの視聴または消費を停止した孤立したノードを含む。
【０３２２】
上述したように、一実施形態では、これらの新しいノードおよび孤立したノードはまた、上記の図７Ａ〜図７Ｅに関して記載したグローバルアプローチ中に考慮から除外されたノードも含む。この実施形態では、フロー図７００ｆに関して記載したこのプロセスに対して、上述した除外またはフィルタリングプロセスが先行する。
【０３２３】
３番目のグループは、「低パフォーマンス」ノード、すなわち、そのパフォーマンスが定義されたパフォーマンス基準を満たすことができないか、またはパフォーマンスの閾値レベルを下回っており、近い将来パフォーマンス基準を満たすことができなくなる危険性があると考えられるノードを含む。一実施形態では、閾値パフォーマンスレベルは、予想「低パフォーマンス」ノードの親ノードに関して取得されたノード中継容量６３２ａの予測に基づいて決定される。例えば、親ノードがパフォーマンスレベルの閾値を下回る予測された値を有するノードは、「低パフォーマンス」ノードとみなされる。
【０３２４】
一実施形態では、各時間期間中に低パフォーマンスノードの最大数（または上限）が識別される。別の実施形態において、閾値パフォーマンスレベルは、低パフォーマンスノードの下限（および上限）に基づいて可変である。
【０３２５】
これらの「ターゲット」の新しいノード、孤立したノード、および低パフォーマンスノードが、新しい親ノードを必要とすると識別されると、トポロジセレクタ４５８ｂは、工程７２０ｆにおいて、予測エンジン４５５ｂからのノード中継容量６３２ａの予測を要求する。ノード中継容量６３２ａの予測は、親ノードに関連付けられているノードメトリックの仕様のみを必要とするため、この同じノード中継容量６３２ａの予測はすべてのターゲット子ノードに対応することから、工程７２０ｆは各親ノードに対して（この実施形態では）１回のみ実行される。
【０３２６】
一実施形態では、このようなノードはすべて任意の所与のターゲットノードの予想親であるため、ノード中継容量６３２ａの予測は、コンテンツアイテムを消費するすべてのノードに対して要求される。他の実施形態では、ノード中継容量６３２ａの予測は、（例えば、上述したような「悪い親」メトリックの履歴に基づく）予想親ノードのサブセットのみに対して要求される。
【０３２７】
関連するすべてのノード中継容量６３２ａの予測を取得して、工程７３０ｆはターゲットノードに対する「好適な」親を識別するプロセス（各ターゲットノードについて繰り返される）を開始する。トポロジセレクタ４５８ｂは、工程７４０ｆにおいて、予測エンジン４５５ｂから、処理中の現在のターゲットノードへの各予想リンクに対するリンク中継容量６３２ｂの予測（および、別の実施形態では、視聴者指標およびセッション継続時間の予測）を要求する。言い換えれば、（上述した工程７２０ｆで決定される）考慮される各予想親ノードについて、その親ノードから処理中の現在のターゲットノードへのリンクに対してリンク中継容量６３２ｂの予測が要求される。一実施形態では、上記の工程７２０ｆに関して記載したのと同じ考慮事項に基づいて、（ターゲット子ノードの）予想親ノードを「悪い親」として除外することに基づいて、特定のリンクが除外される。
【０３２８】
次に、トポロジセレクタ４５８ｂは、工程７５０ｆでは、上記の工程７２０ｆからのノード中継容量６３２ａの予測、および上記の工程７４０ｆからのリンク中継容量６３２ｂの予測に基づいて、その現在のターゲットに対する親を決定する。一実施形態では、所与の各ターゲットノードについて、パフォーマンス基準、すなわちパフォーマンス基準を「最も良好に満たす」（または満たすことに最も近い）親ノードに基づいて、最適な親ノードが選択される。他の実施形態では、このプロセスは、任意の「好適な」親ノード、すなわちパフォーマンス基準を満たす親ノードが識別されると完了する。
【０３２９】
別の実施形態では、複数の親ノードが、ターゲット子ノードへの十分なリンク中継容量６３２ｂ（および、存在する場合、既存の子ノードにターゲット子ノードを追加するのに十分な過剰容量）を有する場合、最高の過剰容量を有する親ノードが選択される。他の実施形態では、（十分ではあるが）最低の過剰容量を有する親ノードが選択される。ターゲットノードに対して好適な親を選択するための様々な他のアルゴリズムは、当業者には明らかであろう。
【０３３０】
（工程７７５ｆに従って）ターゲットノードが残っている場合、プロセスは、工程７３０ｆから繰り返される。これは、（上述したように）ノード中継リング容量６３２ａの予測が（任意の予想ターゲット子ノードの）すべての予想親ノードについて既に取得されているためである。すべてのターゲットノードに対して好適な（または最適な）親ノードが選択されると、プロセスは工程７９０ｆで終了する。
【０３３１】
３．追加の実施形態
図２Ｂを参照して上述したように、ノードは、消費しないコンテンツアイテムのセグメントを中継するために使用されてもよい（例えば、別のコンテンツアイテムのセグメントを消費するため）。このようなシナリオの目的は、そうしなければ現在のオーバーレイネットワークの一部ではないピアノードの未使用または過剰中継容量を活用することである。
【０３３２】
これらの「外部」ノードが使用されるこのようなシナリオの一例は、複数の解像度（例えば、ビデオコンテンツアイテムの４８０ｐおよび１０８０ｐバージョン）を配布用に利用することができるライブビデオイベントである。基本的に、ビデオの４８０ｐバージョンは、１番目のオーバーレイネットワークトポロジ上で配信されるコンテンツアイテムの１つであり、一方で１０８０ｐバージョンのビデオは、２番目のオーバーレイネットワークトポロジで「同時に」配信される２番目の別個のコンテンツアイテムである。
【０３３３】
現在４８０ｐまたは１０８０ｐのコンテンツを消費している視聴者は、過剰中継容量を有していると識別される場合がある。このような視聴者は、（中継用の目的であるが、消費用の目的ではない）他のオーバーレイネットワークトポロジに追加され、したがって、２つの異なる（ただし、重複している）オーバーレイネットワークトポロジの一部である。
【０３３４】
このシナリオでは、１０８０ｐコンテンツを消費および／または中継できないノードに４８０ｐコンテンツを配信することが目的である。このようなノードは、４８０ｐオーバーレイネットワークトポロジを形成する。しかし、過剰中継容量があると識別された１０８０ｐコンテンツを中継するノードは、４８０ｐオーバーレイネットワークのパフォーマンスを改善するための貴重なリソースとして機能する（すなわち、その過剰中継容量を活用することによって）。
【０３３５】
これらの「外部」ノードが使用される別のシナリオには、使用されていなければアイドル状態になっているデバイスが関与する。例えば、一実施形態では、（図３Ｂに示される）クライアントソフトウェアは、インターネットに継続的に接続される「常にオン」のセットトップボックス内にインストールされるが、通常はいかなるコンテンツアイテムも消費しない。このシナリオでは、そのようなデバイスは、ほとんどがアイドル状態であるため、しばしば、過剰中継容量を有している。したがって、これらのデバイスは、追加の中継ノードを必要とするオーバーレイネットワークトポロジの宛先ノードにコンテンツアイテムのセグメントを中継するための優れた候補となる。
【０３３６】
現在のオーバーレイネットワークトポロジがそのようなアイドルノードの恩恵を受けることができると決定すると、オーバーレイネットワークトポロジマネージャ３５０ｃは、そのようなノードのアイデンティティをトポロジセレクタ３５８ｃに通知する。次に、トポロジセレクタ３５８ｃは、上述したように、そのようなノードを（すなわち、「新しいノード」として）その既存のオーバーレイネットワークトポロジに追加する。このシナリオでは、オーバーレイネットワークトポロジマネージャ３５０ｃは、コンテンツアイテムの視聴の開始または視聴の停止を決定したユーザの気まぐれではなく、１つ以上の現在のオーバーレイネットワークトポロジの状態（すなわち、そのようなアイドルノードが最も必要とされる場所）に基づいて、そのようなノードを追加および削除する。
【０３３７】
他の実施形態では、非ツリーベースのトポロジが使用され、ノードが複数の親ノードからコンテンツセグメントを同時に受信できるようにする。このシナリオでは、例えば、スポーツイベントの視聴者は、複数の異なるブロードキャストの中から受信して、それらを切り替える（例えば、視聴者のローカルのお気に入りを含む異なる実況アナウンサーを切り替える）。このシナリオの他の実施形態では、任意の個々のソースのアップリンク制限などのスループット制限を克服する目的で、複数の異なるソースから大きな医療または他のデータファイルが受信される。
【０３３８】
別の実施形態では、オーバーレイネットワークトポロジマネージャ３５０ｃは、複数の子ノード（または、別の実施形態では、複数の親ノード）のそのノードへの割り当てを容易にする目的で、ノードに「スロット」を割り当てる。例えば、オーバーレイネットワークトポロジマネージャ３５０ｃは、その初期メトリック（例えば、接続タイプ、アップリンクおよびダウンリンク速度など）に基づいて、デフォルトの固定数の中継スロットをノードに割り当てる。次いで、ノードの現在の中継スロット数を増加させるか、または減少させるかを、経時的に識別された過剰容量に基づいて決定する。このようにして、大きい過剰容量を有するノードには、より多くの子ノードが割り当てられる。ノードが複数の親ノードを持つことを許可する他の実施形態では、「着信」スロットに関して同じ概念が使用される。
【０３３９】
上述したように、本発明は、複数のユーザノード間でのデジタルコンテンツの配布を含む実質的にあらゆるタイプのアプリケーションに関して使用することができる。例えば、ＶＯＤシナリオでは、ブロードキャストビデオシナリオとは異なり、ノードは、異なる時間にコンテンツアイテムのセグメントを受信する。そのようなシナリオでは、上述したように、各ユーザノードデバイス３００ｂ内のコンテンツアレイマネージャ３７０ｂは、そのバッファを利用して、長い時間期間（例えば、ブロードキャストビデオの通常の３０秒に対して５〜１０分）のセグメントの記憶を容易にする。このバッファのサイズが大きくなると、現時点では消費していないコンテンツをブロードキャストするために、より多くのノードが利用可能になる。
【０３４０】
オーバーレイネットワークトポロジマネージャ３５０ｃは、ユーザがコンテンツアイテムを要求する時間期間ごとに別個のオーバーレイネットワークトポロジを維持するのではなく、これらの異なる期間を追跡し、様々な親ノードに割り当てられたバッファのサイズを動的に調整する。例えば、１００人のユーザが１００のわずかにずれた時間期間でコンテンツアイテムの視聴を要求した場合、オーバーレイネットワークトポロジマネージャ３５０ｃは、各オーバーレイネットワークが単一のノード（または少なくとも非常に小さい数のノード）を有することになるため、１００の異なるオーバーレイネットワークトポロジを維持しない。
【０３４１】
代わりに、コンテンツアイテム専用のバッファのサイズを大きくすることによって、ノードは、はるかにより少ない数の別個の（ただし、重複する）オーバーレイネットワークトポロジに沿って、各々異なる時間に異なるユーザにセグメントを提供するために、慎重に同期されたバッファサイズ（すべてオーバーレイネットワークトポロジマネージャ３５０ｃによって管理される）を使用して、コンテンツを効果的に配布する。例えば、一実施形態では、１０分間のバッファを使用して、１２の重複するオーバーレイネットワークトポロジを介した２時間のビデオの配布を可能にする。他の実施形態では、異なるオーバーレイネットワークトポロジ間でノードを効果的に移動することにより、追加の機能（一時停止、巻き戻しなど）が実装される。
【０３４２】
本明細書では、添付の図面に示される特定の実施形態を参照しながら本発明を説明してきた。本開示に照らして、本明細書に開示された概念の追加の実施形態が、当業者によって本発明の範囲内で想定および実施され得ることを理解されたい。
【図１Ａ】
2020518179.tif 000003
【図１Ｂ】
2020518179.tif 000004
【図１Ｃ】
2020518179.tif 000005
【図２Ａ】
2020518179.tif 000006
【図２Ｂ】
2020518179.tif 000007
【図２Ｃ】
2020518179.tif 000008
【図３Ａ】
2020518179.tif 000009
【図３Ｂ】
2020518179.tif 000010
【図３Ｃ】
2020518179.tif 000011
【図４Ａ】
2020518179.tif 000012
【図４Ｂ】
2020518179.tif 000013
【図５】
2020518179.tif 000014
【図６Ａ】
2020518179.tif 000015
【図６Ｂ】
2020518179.tif 000016
【図７Ａ】
2020518179.tif 000017
【図７Ｂ】
2020518179.tif 000018
【図７Ｃ】
2020518179.tif 000019
【図７Ｄ】
2020518179.tif 000020
【図７Ｅ】
2020518179.tif 000021
【図７Ｆ】
2020518179.tif 000022
【国際調査報告】
2020518179.tif 000023
2020518179.tif 000024
2020518179.tif 000025
2020518179.tif 000026
2020518179.tif 000027
2020518179.tif 000028