(57)【要約】  いくつかの実施形態は、複数のパブリッククラウドプロバイダの複数のパブリッククラウドおよび／または複数の領域で、エンティティに対して仮想ネットワークを確立する。いくつかの実施形態では、仮想ネットワークは、複数のパブリッククラウドにまたがるオーバーレイネットワークであり、１つ以上のプライベートネットワーク（例えば、エンティティの支店、部門、部署、またはそれらに関連するデータセンタ内のネットワーク）、モバイルユーザ、およびSaaS (Software as a Service)プロバイダマシン、およびエンティティの他のウェブアプリケーションを相互接続する。いくつかの実施形態における仮想ネットワークは、インターネットを介したこのトラフィックのルーティングを最小化しようとする一方で、最適なエンドツーエンドの性能、信頼性、およびセキュリティのために、エンティティのデータメッセージの宛先へのルーティングを最適化するように構成することができる。また、いくつかの実施形態における仮想ネットワークは、ネットワークを通過するデータメッセージフローのレイヤ4処理を最適化するように構成することができる。
2020536403.tif 000002
【特許請求の範囲】
【請求項１】
複数のパブリッククラウドデータセンタ上に仮想ネットワークを確立する方法であって、
第１のエンティティに対する第１の仮想ワイドエリアネットワーク（ＷＡＮ）を実施するために第１のマルチテナントのパブリッククラウドデータセンタおよび第２のマルチテナントのパブリッククラウドデータセンタに転送要素の第１のセットを構成することであって、前記第１の仮想ＷＡＮは、前記第１のエンティティの２つ以上のマシンロケーションのセットにおいて動作する複数のマシンを接続する、構成することと、
第２のエンティティに対する第２の仮想ワイドエリアネットワークを実施するために前記第１のマルチテナントのパブリッククラウドデータセンタおよび前記第２のマルチテナントのパブリッククラウドデータセンタに転送要素の第２のセットを構成することであって、前記第２の仮想ＷＡＮは、前記第２のエンティティの２つ以上のマシンロケーションのセットにおいて動作する複数のマシンを接続する、構成することと、を含む方法。
【請求項２】
請求項１に記載の方法であって、前記第１のエンティティの前記マシンロケーションのセットは、２つ以上のオフィスロケーションを含む、方法。
【請求項３】
請求項２に記載の方法であって、前記第１のエンティティの前記マシンロケーションのセットは、さらに、少なくとも１つのデータセンタロケーションを含む方法。
【請求項４】
請求項３に記載の方法であって、前記第１のエンティティの前記マシンロケーションのセットは、さらにリモートデバイスロケーションを含む、方法。
【請求項５】
請求項１に記載の方法であって、前記第１のエンティティの前記マシンロケーションのセットは、オフィスロケーションおよびデータセンタロケーションを含む、方法。
【請求項６】
請求項５に記載の方法であって、前記第１のエンティティの前記マシンロケーションのセットは、SaaS(Software as a Service)プロバイダの複数のマシンを有するロケーションをさらに含む、方法。
【請求項７】
請求項１に記載の方法であって、前記マシンは、仮想マシン、コンテナ、またはスタンドアロンコンピュータの少なくとも１つを含む、方法。
【請求項８】
請求項１に記載の方法であって、前記転送要素の第１のセットのうちの転送要素の少なくともサブセットは、前記転送要素の第２のセットにも含まれる、方法。
【請求項９】
請求項８に記載の方法であって、前記転送要素の第１のセットのうちの、転送要素の少なくとも別のサブセットが、前記転送要素の第２のセットには無い、方法。
【請求項１０】
請求項１に記載の方法であって、 
前記転送要素の第１のセットを構成することは、オーバレイ仮想ＷＡＮヘッダの第１のセットを使用するように前記転送要素の第１のセットを構成して、異なるマシンロケーションの前記第１のエンティティのマシン間で交換されるデータメッセージをカプセル化することを含み、
前記転送要素の第２のセットを構成することは、オーバレイ仮想ＷＡＮヘッダの第２のセットを使用するように前記転送要素の第２のセットを構成して、異なるマシンロケーションの前記第２のエンティティのマシン間で交換されるデータメッセージをカプセル化することを含み、
前記オーバレイ仮想ＷＡＮヘッダの第１のセットは前記第１のエンティティを識別する第１のエンティティ識別子を格納し、前記オーバレイ仮想ＷＡＮヘッダの第２のセットは前記第２のエンティティを識別する第２のエンティティ識別子を格納する、方法。
【請求項１１】
請求項１０に記載の方法であって、少なくとも１つの転送要素が転送要素の両方のセットに含まれるように、前記転送要素の第１および第２のセットが重複する、方法。
【請求項１２】
請求項１に記載の方法であって、前記転送要素の第１および第２のセットを構成することは、異なるパブリッククラウドプロバイダのパブリッククラウドデータセンタ上および異なる領域内に、異なるエンティティに対する異なる仮想ＷＡＮをデプロイする仮想ネットワークプロバイダの１つ以上のコントローラのセットによって実行される、方法。
【請求項１３】
請求項１に記載の方法であって、前記転送要素の第１および第２のセットは、コンピュータ上で動作する複数のソフトウェア転送要素を含む、方法。
【請求項１４】
請求項１に記載の方法であって、前記転送要素の第１および第２のセットは、前記データセンタ内のホストコンピュータ上で動作する複数のソフトウェア転送要素を含む、方法。
【請求項１５】
請求項１４に記載の方法であって、前記複数のソフトウェア転送要素は、前記ホストコンピュータ上で動作するマシンである、方法。
【請求項１６】
請求項１５に記載の方法であって、前記複数のソフトウェア転送要素を実装するマシンの少なくともサブセットは、他のマシンと共にホストコンピュータ上で動作する、方法。
【請求項１７】
請求項１５に記載の方法であって、前記複数のソフトウェア転送要素を実装するマシンの少なくともサブセットは、仮想マシンである、方法。
【請求項１８】
複数のパブリッククラウドデータセンタ上に仮想ネットワークを確立するためのプログラムを記憶する非一時的機械可読媒体であって、少なくとも１つのハードウェア処理ユニットによる実行のためのプログラムであって、プログラムは、
第１のエンティティに対する第１の仮想ワイドエリアネットワーク（ＷＡＮ）を実施するために第１のマルチテナントのパブリッククラウドデータセンタおよび第２のマルチテナントのパブリッククラウドデータセンタに転送要素の第１のセットを構成することであって、前記第１の仮想ＷＡＮは、前記第１のエンティティの２つ以上のマシンロケーションのセットにおいて動作する複数のマシンを接続する、構成することと、
第２のエンティティに対する第２の仮想ワイドエリアネットワークを実施するために前記第１のマルチテナントのパブリッククラウドデータセンタおよび前記第２のマルチテナントのパブリッククラウドデータセンタに転送要素の第２のセットを構成することであって、前記第２の仮想ＷＡＮは、前記第２のエンティティの２つ以上のマシンロケーションのセットにおいて動作する複数のマシンを接続する、構成することと、のための命令のセットを含むことを特徴とする非一時的機械可読媒体。
【請求項１９】
請求項１８に記載の非一時的機械可読媒体であって、前記第１のエンティティの前記マシンロケーションのセットは、少なくとも１つのオフィスロケーション、１つのデータセンタロケーション、および複数のリモートユーザロケーションを含む、非一時的機械可読媒体。
【請求項２０】
請求項１９に記載の非一時的機械可読媒体であって、前記第１のエンティティの前記マシンロケーションのセットは、SaaS (Software as a Service)プロバイダの複数のマシンを含むロケーションをさらに含む、非一時的機械可読媒体。
【請求項２１】
少なくとも２つの異なるパブリッククラウドプロバイダの少なくとも２つのパブリッククラウドデータセンタを介して流れるデータメッセージフローを転送する方法であって、前記方法は、
第１のパブリッククラウドデータセンタ内の入力転送要素において、 
パブリッククラウドデータセンタの外部の第１の外部マシンから、前記パブリッククラウドデータセンタの外部の第２の外部マシンに向けたデータメッセージを受信することであって、前記第２の外部マシンは、第２のパブリッククラウドデータセンタ内にある出力転送要素を介して到達可能である、受信することと、
前記入力転送要素および出力転送要素のネットワークアドレスを送信元および宛先アドレスとして含む第１のヘッダを有するデータメッセージをカプセル化することと、
送信元および宛先のネットワークアドレスを、前記入力転送要素の前記ネットワークアドレス、及び、パブリッククラウドデータセンタにあり、前記出力転送要素へのパス上の次ホップである次ホップ転送要素のネットワークアドレスとして指定する第２のヘッダを有する前記データメッセージをカプセル化することと、を含む方法。
【請求項２２】
請求項２１に記載の方法であって、前記次ホップ転送要素は、第３のパブリッククラウドデータセンタ内にある、方法。
【請求項２３】
請求項２２に記載の方法であって、前記第１のパブリッククラウドデータセンタ、前記第２のパブリッククラウドデータセンタ、および前記第３のパブリッククラウドデータセンタは、３つの異なるパブリッククラウドプロバイダに属す、方法。
【請求項２４】
請求項２２に記載の方法であって、前記第１のパブリッククラウドデータセンタおよび前記第２のパブリッククラウドデータセンタは、第１のパブリッククラウドプロバイダに属し、前記第３のパブリッククラウドデータセンタは、異なる第２のパブリッククラウドプロバイダに属す、方法。
【請求項２５】
請求項２２に記載の方法であって、前記第１のパブリッククラウドデータセンタおよび前記第２のパブリッククラウドデータセンタは、２つの異なるパブリッククラウドプロバイダに属し、前記第３のパブリッククラウドデータセンタは、前記第１のパブリッククラウドデータセンタまたは前記第２のパブリッククラウドデータセンタの前記パブリッククラウドプロバイダに属す、方法。
【請求項２６】
請求項２２に記載の方法であって、 
前記次ホップ転送要素は、第１の次ホップ転送要素であり、 
前記第１の次ホップ転送要素は、前記パスに沿った第２の次ホップ転送要素を前記データメッセージの次ホップとして識別し、前記第２のヘッダにおいて、前記第１の次ホップ転送要素および前記第２の次ホップ転送要素のネットワークアドレスとして、送信元および宛先のネットワークアドレスを指定する、方法。
【請求項２７】
請求項２６に記載の方法であって、前記第２の次ホップ転送要素は前記出力転送要素である、方法。
【請求項２８】
請求項２７に記載の方法であって、前記カプセル化されたデータメッセージを受信した後、前記出力転送要素は、前記カプセル化されたデータメッセージが前記出力転送要素に向けられていることを前記第１のヘッダ内の前記宛先のネットワークアドレスから判定し、前記第１のヘッダおよび前記第２のヘッダを前記データメッセージから除去し、前記データメッセージを前記第２の外部マシンに転送する、方法。
【請求項２９】
請求項２６に記載の方法であって、前記第２の次ホップ転送要素は、前記第２の転送要素とは異なる第４の転送要素である、方法。
【請求項３０】
請求項２１に記載の方法であって、前記次ホップ転送要素は、前記第２の転送要素である、方法。
【請求項３１】
請求項２１に記載の方法であって、さらに、 
データメッセージを、異なるテナントのパブリッククラウドデータセンタ上の異なる仮想ネットワークを定義する仮想ネットワークプロバイダの前記異なるテナントに属する前記入力転送要素および前記出力転送要素において処理することと、
前記受信されたメッセージの第１のヘッダをカプセル化することにおいて、前記第１の外部マシンおよび前記第２の外部マシンに関連付けられた前記テナントを識別するテナント識別子を格納することと、を含む、方法。
【請求項３２】
請求項３１に記載の方法であって、前記第１のヘッダおよび前記第２のヘッダによる前記データメッセージのカプセル化は、第１のテナントに対して、前記第１のパブリッククラウドデータセンタおよび前記第２のパブリッククラウドデータセンタを含むグループパブリッククラウドデータセンタのネットワークのグループにまたがるオーバレイ仮想ネットワークを定義する、方法。
【請求項３３】
請求項３２に記載の方法であって、前記テナントは企業であり、前記仮想ネットワークは企業ワイドエリアネットワーク（ＷＡＮ）である、方法。
【請求項３４】
請求項２１に記載の方法であって、 
前記第１の外部マシンは、第１の支店内のマシン、プライベートの第１のデータセンタ内のマシン、またはリモートマシンのいずれかであり、
前記第２の外部マシンは、第２の支店内のマシン、またはプライベートの第２のデータセンタ内のマシンである、方法。
【請求項３５】
エンティティに対する仮想ネットワークを確立するシステムであって、
第１のパブリッククラウドプロバイダによって運用される第１のマルチテナントのパブリッククラウドにおける転送要素の第１のセットと、
第１のパブリッククラウドプロバイダとは異なる第２のパブリッククラウドプロバイダによって運用される第２のマルチテナントパブリッククラウドにおける転送要素の第２のセットと、を有し、
前記転送要素の第１および第２のセットは、第１および第２のマルチテナントのパブリッククラウドの両方にまたがる各オーバレイ仮想ネットワークを有する仮想ネットワークプロバイダの第１および第２のテナントに対する第１および第２のオーバレイ仮想ネットワークを確立し、 
各オーバレイ仮想ネットワークは、各データメッセージを第１および第２のヘッダを用いてカプセル化することによって確立され、前記第１のヘッダは、前記データメッセージに対する前記仮想ネットワーク内の入力または出力インタフェースを識別し、前記第２のヘッダは、前記データメッセージに対する前記オーバレイ仮想ネットワーク内の次ホップを識別する、システム。
【請求項３６】
請求項３５に記載のシステムであって、前記次ホップ転送要素が第３のパブリッククラウドデータセンタ内にある、システム。
【請求項３７】
請求項３５に記載のシステムであって、前記第１のパブリッククラウドデータセンタ、前記第２のパブリッククラウドデータセンタ、および前記第３のパブリッククラウドデータセンタは、３つの異なるパブリッククラウドプロバイダに属す、システム。
【請求項３８】
請求項３６に記載のシステムであって、前記第１のパブリッククラウドデータセンタおよび前記第２のパブリッククラウドデータセンタは、第１のパブリッククラウドプロバイダに属し、前記第３のパブリッククラウドデータセンタは、異なる第２のパブリッククラウドプロバイダに属す、システム。
【請求項３９】
請求項３６に記載のシステムであって、前記第１のパブリッククラウドデータセンタおよび前記第２のパブリッククラウドデータセンタは、２つの異なるパブリッククラウドプロバイダに属し、前記第３のパブリッククラウドデータセンタは、前記第１のパブリッククラウドデータセンタまたは前記第２のパブリッククラウドデータセンタの前記パブリッククラウドプロバイダに属す、システム。
【請求項４０】
請求項３６に記載のシステムであって、 
前記次ホップ転送要素は、第１の次ホップ転送要素であり、 
前記第１の次ホップ転送要素は、前記パスに沿った第２の次ホップ転送要素を前記データメッセージの次ホップとして識別し、前記第２のヘッダにおいて、前記第１の次ホップ転送要素および前記第２の次ホップ転送要素のネットワークアドレスとして、送信元および宛先のネットワークアドレスを指定する、方法。
【発明の詳細な説明】
【背景技術】
【０００１】
現在、企業エンタープライズネットワークは、企業のさまざまなオフィスや部門を安全に接続する通信バックボーンである。このネットワークは、通常、広域ネットワーク（WAN）で、（1）支店および地域キャンパスのユーザ、（2）ビジネスアプリケーション、イントラネット、およびそれらに対応するデータをホストする企業データセンタ、（3）企業ファイアウォールおよびDMZ(非武装地帯）を介してグローバルインターネットを接続する。エンタープライズネットワークには、フレームリレーやMPLS(マルチプロトコル・ラベル・スイッチング）などの高価なリース回線によって相互接続されたスイッチ、ルータ、ミドルボックスアプライアンスなどの特殊なハードウェアが含まれる。 
【０００２】
ここ数年、企業がコミュニケーションサービスを提供し、利用する方法にパラダイムシフトがあった。まず、モビリティ革命により、ユーザはいつでも、スマートフォンを中心としたモバイルデバイスを使用して、どこからでもサービスにアクセスできるようになった。このようなユーザは、パブリックインターネットおよびセルラネットワークを介してビジネスサービスにアクセスする。同時に、サードパーティのSaaS(Software as a Service)ベンダ（例えばSalesforce、Workday、Zendeskなど）が従来のオンプレミスアプリケーションに取って代わり、プライベートデータセンタでホストされている他のアプリケーションがパブリッククラウドに再配置されてきた。このトラフィックはまだエンタープライズネットワーク内で伝送されているが、その大部分は企業ネットワーク境界の外側で発信および終端され、パブリックインターネットと企業ネットワークの両方を（1度または2度）通過する必要がある。最近の研究では、企業ネットワークの40％が、バックホールされたトラフィック（すなわち、企業ネットワークで観測されたインターネットトラフィック）の割合が80％以上であることを報告している。これは、企業トラフィックの大半が高価な専用線と消費者用インターネットの両方を介して伝送されることを意味する。
【０００３】
消費者中心のサービスとしては、インターネット自体はビジネストラフィックに対して劣悪な媒体である。これは、重要なビジネスアプリケーションにおいて期待される、信頼性、QoS(Quality of Service)保証およびセキュリティを欠いている。さらに、絶えず増加する消費者トラフィック需要、ネット中立性規制、及びメジャーなプレーヤ（例えば、Netflix、Google、パブリッククラウド）によるインターネットバイパスの創出により、トラフィックの単位あたりの収益は低下してきた。このような傾向により、サービスプロバイダが消費者の要求に迅速に対応し、適切なビジネスサービスを提供するインセンティブが減少している。 
【０００４】
パブリッククラウドの成長により、企業はより多くのコンピューティング基盤をパブリッククラウドデータセンタに移行している。パブリッククラウドプロバイダは、コンピューティングおよびネットワーク基盤への投資の先頭に立っている。これらのクラウドサービスは、2016年にはAzure、AWS、IBMおよびGoogleを用いてそれぞれ世界中の領域の38、16、25および14にまで拡大している、多くのデータセンタを世界中に構築してきた。各パブリッククラウドプロバイダは、潜水船によって配備された暗いファイバケーブルと海底ケーブルを使用する高価な高速ネットワークを使用して、独自のデータセンタを相互接続している。 
【０００５】
今日では、このような変化にもかかわらず、企業のネットワークポリシによって、すべての企業トラフィックがセキュアなWANゲートウェイを通過するよう強制されることがよくある。ユーザがモバイル化し、アプリケーションがSaaSやパブリッククラウドに移行するにつれて、企業WANは全ての企業通信を低速化させるコストのかかる回り道となっている。企業WANのトラフィックのほとんどは、インターネットから送信されるか、インターネットへ送信される。インターネットを介してこのトラフィックを送信する代替的なセキュアなソリューションは、パフォーマンスが低く信頼性が低いため、適切ではない。 
【発明の概要】
【０００６】
いくつかの実施形態は、1つ以上の領域（例えば、複数の都市、州、国など）の1つ以上のパブリッククラウドプロバイダの複数のパブリッククラウドデータセンタを介して、エンティティに対する仮想ネットワークを確立する。このような仮想ネットワークを確立することができるエンティティの例には、ビジネスエンティティ（例えば、企業）、非営利エンティティ（例えば、病院、研究組織など）、教育エンティティ（例えば、総合大学、カレッジなど）、または他の任意のタイプのエンティティが含まれ得る。パブリッククラウドプロバイダーの例としては、Amazon Web Services (AWS)、Google Cloud Platform (GCP)、Microsoft Azureなどが含まれる。
【０００７】
いくつかの実施形態では、高速で信頼性の高いプライベートネットワークは、2つ以上のパブリッククラウドデータセンタ（パブリッククラウド）を相互接続する。いくつかの実施形態は、仮想ネットワークを、１つ以上のプライベートネットワーク（例えば、支社、部門、エンティティの部門、またはそれらに関連するデータセンタ内のネットワーク）、モバイルユーザ、SaaS(Software as a Service)プロバイダマシン、パブリッククラウド内のマシンおよび／またはサービス、およびその他のウェブアプリケーションを相互接続するための、複数のパブリッククラウドにまたがるオーバーレイネットワークとして定義する。 
【０００８】
いくつかの実施形態における仮想ネットワークは、インターネットを介したこのトラフィックのルーティングを最小化しようとする一方で、最適なエンドツーエンドの性能、信頼性、およびセキュリティのために、エンティティのデータメッセージの宛先へのルーティングを最適化するように構成することができる。また、いくつかの実施形態における仮想ネットワークは、ネットワークを通過するデータメッセージフローのレイヤ4処理を最適化するように構成することができる。例えば、いくつかの実施形態では、仮想ネットワークは、接続パスにわたってレート制御機構を分割することによって、TCP(トランスポート制御プロトコル）接続のエンドツーエンドのレートを最適化する。
【０００９】
いくつかの実施形態では、複数のパブリッククラウドに展開される複数のコンポーネントを構成することによって、仮想ネットワークを確立する。これらのコンポーネントには、いくつかの実施形態において、ソフトウェアベースの測定エージェント、ソフトウェア転送要素（例えば、ソフトウェアルータ、スイッチ、ゲートウェイ等）、レイヤ4接続プロキシ及びミドルボックスサービスマシン（例えば、アプライアンス、VM、コンテナ等）が含まれる。いくつかの実施形態では、これらのコンポーネントの１つ以上が、Open vSwitch、OpenVPN、strongSwan、およびRyuなどの標準化され、または一般的に利用可能なソリューションを使用する。
【００１０】
いくつかの実施形態は、複数のパブリッククラウド上で仮想ネットワークを実装するために、パブリッククラウドコンポーネントを構成する論理的に集中化されたコントローラクラスタ（例えば、１つ以上のコントローラサーバのセット）を利用する。いくつかの実施形態では、冗長性および高可用性を改善するために、このクラスタ内のコントローラは、様々な異なるロケーション（例えば、異なるパブリッククラウドデータセンタ内）に存在する。いくつかの実施形態では、コントローラクラスタは、仮想ネットワークを確立するために使用されるパブリッククラウドコンポーネントの数、またはこれらのコンポーネントに割り当てられるコンピューティングまたはネットワークリソースを、スケールアップまたはスケールダウンする。 
【００１１】
いくつかの実施形態では、同じパブリッククラウドプロバイダの同じパブリッククラウドのセット、および／または同じパブリッククラウドプロバイダまたは異なるパブリッククラウドプロバイダの異なるパブリッククラウドのセット上に、異なるエンティティのための異なる仮想ネットワークを確立する。いくつかの実施形態では、仮想ネットワークプロバイダは、異なるテナントが同じまたは異なるパブリッククラウド上で異なる仮想ネットワークを定義することを可能にするソフトウェアおよびサービスを提供する。いくつかの実施形態では、同じコントローラクラスタまたは異なるコントローラクラスタを使用して、パブリッククラウドコンポーネントを構成し、複数の異なるエンティティに対して同じまたは異なるパブリッククラウドのセット上の異なる仮想ネットワークを実装することができる。
【００１２】
1つ以上のパブリッククラウド上にテナントの仮想ネットワークをデプロイするため、コントローラクラスタは、（1）テナントの支店、データセンタ、モバイルユーザおよびSaaSプロバイダのロケーションに基づいて、テナントの仮想ネットワークに出入りする可能性のある入出力ルータを識別し、（2）仮想ネットワークを実装する他の中間パブリッククラウドルータを介して、識別された入力ルータから識別された出力ルータへ通過する経路を識別する。これらの経路を識別した後、コントローラクラスタはこれらの経路を（１つ以上の）パブリッククラウド内の仮想ネットワークルータの転送テーブルに伝播する。OVSベースの仮想ネットワークルータを使用する実施形態では、コントローラはOpenFlowを使用して経路を配信する。
【００１３】
前述の概要は、本発明のいくつかの実施形態の簡単な紹介として役立つように意図されている。本書において開示されているすべての発明の主題の紹介または概要を意味するものではない。以下の詳細な説明および詳細な説明で参照される図面は、概要ならびに他の実施形態で説明される実施形態をさらに説明する。したがって、本書面によって説明されるすべての実施形態を理解するために、概要、詳細な説明、図面、および特許請求の範囲の全体的な検討が必要である。さらに、特許請求の範囲に記載される主題は、概要、詳細な説明、および図面における例示的な詳細によって限定されるべきではない。 
【図面の簡単な説明】
【００１４】
本発明の新規な特徴は、添付の特許請求の範囲に記載されている。しかしながら、説明のために、本発明のいくつかの実施形態を以下の図に示す。
【００１５】
【図１Ａ】図1Aは、2つのパブリッククラウドプロバイダの複数のパブリッククラウドデータセンタ上に、１つの企業に対して定義された仮想ネットワークを示している。
【００１６】
【図１Ｂ】図1Bは、パブリッククラウド上にデプロイされた、2つの企業テナントに対する2つの仮想ネットワークの例を示している。
【００１７】
【図１Ｃ】図1Cは、パブリッククラウド上にデプロイされた1つのネットワークと、パブリッククラウドの別のペア上にデプロイされたもう1つの仮想ネットワークの、2つの仮想ネットワークの例を代替的に示している。
【００１８】
【図２】図2は、本発明のいくつかの実施形態の管理転送ノードおよびコントローラクラスタの例を示す。
【００１９】
【図３】図3は、いくつかの実施形態において、コントローラ測定処理レイヤが生成する測定グラフの例を示す。
【００２０】
【図４Ａ】図4Aは、いくつかの実施形態において、測定グラフからコントローラパス識別レイヤが生成するルーティンググラフの例を示す。
【００２１】
【図４Ｂ】図4Bは、2つのSaaSプロバイダの既知のIPを、これらのSaaSプロバイダのデータセンタに最も近いデータセンタにあるルーティンググラフの2つのノードに追加する例を示している。
【００２２】
【図４Ｃ】図4Cは、2つのSaaSプロバイダを表すために2つのノードを追加することによって生成されるルーティンググラフを示す。
【００２３】
【図４Ｄ】図4Dは、2つのパブリッククラウドにそれぞれ接続する既知のIPアドレスを持つ支店とデータセンタを表すために追加されたノードを含むルーティンググラフを示している。
【００２４】
【図５】図5は、コントローラ測定レイヤから受信した測定グラフからルーティンググラフを生成するために、コントローラパス識別レイヤが使用するプロセスを示す。
【００２５】
【図６】図6は、いくつかの実施形態のIPsecデータメッセージフォーマットを示す。
【００２６】
【図７】、
【図８】図7は、いくつかの実施形態の2つのカプセル化ヘッダの例を示し、図8は、いくつかの実施形態においてこれら2つのヘッダがどのように使用されるかを説明する例を示す。
【００２７】
【図９】、
【図１０】、
【図１１】図9から図11は、2つの異なる支店の2つのコンピューティングデバイス間で送信されるメッセージを受信したときに、入力、中間、および出力MFNによってそれぞれ実行されるメッセージ処理プロセスを示している。
【００２８】
【図１２】図12は、入力MFNと出力MFNの間に中間MFNを含まない例を示す。
【００２９】
【図１３】図13は、支店の企業コンピューティングデバイスから別の支店またはSaaSプロバイダデータセンタ内の別のデバイスに送信されるメッセージを受信したときに、入力MFNのCFEによって実行されるメッセージ処理プロセスを示している。
【００３０】
【図１４】図14は、出力ルータで実行されているNAT動作を示している。
【００３１】
【図１５】図15は、SaaSプロバイダマシンからテナントマシンに送信されるメッセージを受信する入力ルータによって実行されるメッセージ処理プロセスを示している。
【００３２】
【図１６】図16は、仮想ネットワークのインターネットへの出力パス上にある各仮想ネットワークゲートウェイに配置されるTMエンジンを示している。
【００３３】
【図１７】図17は、図16に示された単一NATアプローチの代わりに、いくつかの実施形態において使用されるダブルNATアプローチを示す。
【００３４】
【図１８】図18は、入力NATエンジンの送信元ポート変換を示す例を示している。
【００３５】
【図１９】図19は、図18のデータメッセージの処理に応答してSaaSマシンが送信する応答メッセージの処理を示す。
【００３６】
【図２０】図20は、1つ以上のパブリッククラウドプロバイダのN個のパブリッククラウドにネットワーク基盤とコントローラクラスタとを有する、仮想ネットワークプロバイダのM個のテナントに対するM個の仮想企業WANの例を示している。
【００３７】
【図２１】図21は、仮想ネットワークプロバイダのコントローラクラスタによって実行される、特定のテナントに対して仮想WANをデプロイおよび管理するプロセスを概念的に示している。
【００３８】
【図２２】図22は、本発明のいくつかの実施形態が実装されるコンピュータシステムを概念的に示している。
【発明を実施するための形態】
【００３９】
本発明の以下の詳細な説明では、本発明の多数の詳細、例および実施形態を説明する。しかしながら、当業者であれば、本発明は、記載された実施形態に限定されず、また、本発明は、説明された特定の詳細および実施例の一部を伴わずに実施することができることは明らか且つ自明である。 
【００４０】
いくつかの実施形態は、1つ以上の領域（例えば、複数の都市、州、国など）の1つ以上のパブリッククラウドプロバイダの複数のパブリッククラウドデータセンタを介して、エンティティに対する仮想ネットワークを確立する。このような仮想ネットワークを確立することができるエンティティの例には、ビジネスエンティティ（例えば、企業）、非営利エンティティ（例えば、病院、研究組織など）、教育エンティティ（例えば、総合大学、カレッジなど）、または他の任意のタイプのエンティティが含まれ得る。パブリッククラウドプロバイダの例としては、Amazon Web Services (AWS)、Google Cloud Platform (GCP)、Microsoft Azureなどが含まれる。
【００４１】
いくつかの実施形態は、仮想ネットワークを、複数のパブリッククラウドデータセンタ（パブリッククラウド）にまたがって、１つ以上のプライベートネットワーク（例えば、支社、部門、部署、またはそれらに関連するデータセンタ内のネットワーク）、モバイルユーザ、SaaS (Software as a Service)プロバイダマシン、パブリッククラウド内のマシンおよび／またはサービス、およびその他のウェブアプリケーションを相互接続するオーバーレイネットワークとして定義する。いくつかの実施形態では、高速で信頼性の高いプライベートネットワークは、2つ以上のパブリッククラウドデータセンタを相互接続する。 
【００４２】
いくつかの実施形態における仮想ネットワークは、インターネットを介したこのトラフィックのルーティングを最小化しようとする一方で、最適なエンドツーエンドの性能、信頼性、およびセキュリティのために、エンティティのデータメッセージの宛先へのルーティングを最適化するように構成することができる。また、いくつかの実施形態における仮想ネットワークは、ネットワークを通過するデータメッセージフローのレイヤ4処理を最適化するように構成することができる。例えば、いくつかの実施形態では、仮想ネットワークは、接続パスにわたってレート制御機構を分割することによって、TCP(トランスポート制御プロトコル）接続のエンドツーエンドのレートを最適化する。
【００４３】
いくつかの実施形態では、複数のパブリッククラウドに展開される複数のコンポーネントを構成することによって、仮想ネットワークを確立する。これらのコンポーネントには、いくつかの実施形態において、ソフトウェアベースの測定エージェント、ソフトウェア転送要素（例えば、ソフトウェアルータ、スイッチ、ゲートウェイ等）、レイヤ4接続プロキシ及びミドルボックスサービスマシン（例えば、アプライアンス、VM、コンテナ等）が含まれる。 
【００４４】
いくつかの実施形態は、パブリッククラウドコンポーネントを構成する論理的に集中化されたコントローラクラスタ（例えば、１つ以上のコントローラサーバのセット）を利用して、複数のパブリッククラウド上で仮想ネットワークを実装する。いくつかの実施形態では、冗長性および高可用性を改善するために、このクラスタ内のコントローラは、様々な異なるロケーション（例えば、異なるパブリッククラウドデータセンタ内）に存在する。コントローラクラスタ内の異なるコントローラが異なるパブリッククラウドデータセンタに配置されている場合、いくつかの実施形態のコントローラは、それらの状態（例えば、テナントを識別するためにそれらが生成する構成データ、仮想ネットワークを通る経路など）を共有する。いくつかの実施形態では、コントローラクラスタは、仮想ネットワークを確立するために使用されるパブリッククラウドコンポーネントの数、またはこれらのコンポーネントに割り当てられるコンピューティングまたはネットワークリソースを、スケールアップまたはスケールダウンする。 
【００４５】
いくつかの実施形態では、同じパブリッククラウドプロバイダの同じパブリッククラウドのセット、および／または同じパブリッククラウドプロバイダまたは異なるパブリッククラウドプロバイダの異なるパブリッククラウドのセット上に、異なるエンティティのための異なる仮想ネットワークを確立する。いくつかの実施形態では、仮想ネットワークプロバイダは、異なるテナントが同じまたは異なるパブリッククラウド上で異なる仮想ネットワークを定義することを可能にするソフトウェアおよびサービスを提供する。いくつかの実施形態では、同じコントローラクラスタまたは異なるコントローラクラスタを使用して、パブリッククラウドコンポーネントを構成し、複数の異なるエンティティに対して同じまたは異なるパブリッククラウドのセット上の異なる仮想ネットワークを実装することができる。
【００４６】
以下の説明では、企業の仮想ネットワークのいくつかの例を示す。しかしながら、当業者は、いくつかの実施形態は他の事業体、非営利組織、教育組織などの他のタイプのエンティティのための仮想ネットワークを定義することを理解するであろう。また、本明細書で使用されているように、データメッセージは、ネットワークを介して送信される特定の形式のビットの集合を指す。当業者であれば、データメッセージという用語は、ネットワークを介して送信される様々なフォーマット化されたビットの集合を指すように本書で用いられることを理解するであろう。これらのビットのフォーマットは、標準化されたプロトコルまたは標準化されていないプロトコルによって指定することができる。標準化されたプロトコルに従ったデータメッセージの例としては、イーサネットフレーム、IPパケット、TCPセグメント、UDPデータグラムなどがある。また、本明細書で使用するL2、L3、L4、L7レイヤ（またはレイヤ2、レイヤ3、レイヤ4、レイヤ7）は、OSI(Open System Interconnection)レイヤモデルの第2データリンクレイヤ、第3ネットワークレイヤ、第4トランスポートレイヤ、第7レイヤプリケーションレイヤをそれぞれ参照している。
【００４７】
図1Aは、2つのパブリッククラウドプロバイダAおよびBの複数のパブリッククラウドデータセンタ105および110上の、企業に対して定義される仮想ネットワーク100を示す。図示するように、仮想ネットワーク100は、異なるパブリッククラウドに異なる管理転送ノード150を配置し、オーバレイトンネル152を介して管理転送ノード（MFN）を相互に接続することによって確立されるセキュアなオーバレイネットワークである。いくつかの実施形態では、MFNは、パブリッククラウドデータセンタ内のいくつかの異なるコンポーネントを概念的にグループ化したものであり、他のパブリッククラウドデータセンタ内の他のMFN（他のコンポーネントのグループと共に）が、1つ以上のエンティティに対して1つ以上のオーバレイ仮想ネットワークを確立する。
【００４８】
以下にさらに説明するように、MFNを形成するコンポーネントのグループは、いくつかの実施形態において、（1）パブリッククラウドデータセンタの外にある外部マシンロケーションである、エンティティのコンピューティングノード（例えば、オフィス、プライベートデータセンタ、リモートユーザなど）とVPN接続を確立する1つ以上のVPNゲートウェイ、（2）共有パブリッククラウドネットワークファブリック上でオーバレイ仮想ネットワークを定義するために、カプセル化されたデータメッセージを相互に転送する1つ以上の転送要素、（3）ミドルボックスサービス動作およびL4−L7最適化を実行する1つ以上のサービスマシン、および（4）パブリッククラウドデータセンタを通る所望のパスを識別するために、パブリッククラウドデータセンタ間のネットワーク接続品質に関する測定値を取得する1つ以上の測定エージェントを含む。いくつかの実施形態では、異なるMFNは、そのようなコンポーネントを異なる配置及び異なる数で有することができ、1つのMFNは、冗長性とスケーラビリティの理由により、そのようなコンポーネントを異なる数で有することができる。 
【００４９】
また、いくつかの実施形態では、各MFNのコンポーネントのグループは、MFNのパブリッククラウドデータセンタ内の異なるコンピュータ上で実行される。いくつかの実施形態では、MFNのコンポーネントのいくつかまたはすべてをパブリッククラウドデータセンタの1つのコンピュータ上で実行することができる。いくつかの実施形態におけるMFNのコンポーネントは、他のテナントの他のマシンも実行するホストコンピュータ上で実行される。これらの他のマシンは、他のテナントの他のMFNの他のマシンであっても、他のテナントの関連のないマシン（コンピューティング仮想マシンやコンテナなど）であってもよい。
【００５０】
いくつかの実施形態における仮想ネットワーク100は、異なるエンティティ（例えば、仮想ネットワークプロバイダの異なる企業顧客／テナント）のために、同一または異なるパブリッククラウドデータセンタ上に異なる仮想ネットワークをデプロイする仮想ネットワークプロバイダによってデプロイ（配備）される。いくつかの実施形態における仮想ネットワークプロバイダは、MFNをデプロイし、これらのMFNを構成および管理するためのコントローラクラスタを提供するエンティティである。
【００５１】
仮想ネットワーク100は、企業のコンピューティングエンドポイント（データセンタ、支店、モバイルユーザなど）を、相互に、及び、パブリッククラウド内に存在するか、またはインターネットを介してアクセス可能なプライベートデータセンタに常駐する外部サービス（パブリックウェブサービス、またはOffice365やSalesforceなどのSaaSサービス）に、接続する。この仮想ネットワークは、異なるパブリッククラウドのさまざまなロケーションを利用して、異なる企業のコンピューティングエンドポイント（異なるプライベートネットワークや企業の異なるモバイルユーザなど）をその周辺のパブリッククラウドに接続する。企業のコンピューティングエンドポイントは、以下の説明では企業コンピューティングノードとも呼ばれる。
【００５２】
いくつかの実施形態では、仮想ネットワーク100は、これらのパブリッククラウドを相互接続する高速ネットワークを利用して、パブリッククラウドを通るデータメッセージをその宛先に転送するか、またはその宛先にできるだけ近づけながら、インターネットを通るデータメッセージの横断を低減する。企業のコンピューティングエンドポイントが、仮想ネットワークがまたがるパブリッククラウドデータセンタの外部にある場合、これらのエンドポイントは外部マシンロケーションと呼ばれる。これは、企業の支店、プライベートデータセンタ、およびリモートユーザのデバイスについての場合である。
【００５３】
図1Aに示す例では、仮想ネットワーク100は、パブリッククラウドプロバイダAの6つのデータセンタ105aから105fと、パブリッククラウドプロバイダBの4つのデータセンタ110aから110dにまたがっている。これらのパブリッククラウドにまたがって、この仮想ネットワークは、異なる地理的領域に位置する企業テナントのいくつかの支店、企業データセンタ、SaaSプロバイダ、およびモバイルユーザを接続する。具体的には、仮想ネットワーク100は、2つの異なる都市（例えば、カリフォルニア州サンフランシスコおよびインドのプネー(Pune)）の2つの支店130aおよび130b、別の都市（例えば、ワシントン州シアトル）の1つの企業データセンタ134、別の2つの都市（ワシントン州レッドモンドおよびフランスのパリ）の2つのSaaSプロバイダデータセンタ136aおよび136b、および世界の様々な場所のモバイルユーザ140を接続する。そのため、この仮想ネットワークは仮想企業WANとして見ることができる。 
【００５４】
いくつかの実施形態では、支店130aおよび130bは、支店の場所にあるコンピュータと、パブリッククラウドの外部にある支店のプライベートデータセンタとを接続する自身のプライベートネットワーク（例えば、ローカルエリアネットワーク）を有する。同様に、いくつかの実施形態における企業データセンタ134は、自身のプライベートネットワークを有し、パブリッククラウドデータセンタの外部に存在する。しかしながら、他の実施形態では、企業データセンタ134または支店130aおよび130bのデータセンタはパブリッククラウド内にあってもよいが、仮想ネットワークは、企業データセンタまたは支店データセンタが仮想ネットワーク100のエッジに接続するので、このパブリッククラウドにはまたがらない。
【００５５】
上述のように、仮想ネットワーク100は、オーバレイトンネル152を介して、異なるパブリッククラウド内の、デプロイされている異なる管理転送ノード150を接続することによって確立される。各管理転送ノード150は、いくつかの構成可能なコンポーネントを含む。上述し、さらに以下に説明するように、MFNコンポーネントは、いくつかの実施形態において、ソフトウェアベースの測定エージェント、ソフトウェア転送要素（例えば、ソフトウェアルータ、スイッチ、ゲートウェイなど）、レイヤ4プロキシ（例えば、TCPプロキシ）、およびミドルボックスサービスマシン（例えば、VM、コンテナなど）を含む。いくつかの実施形態におけるこれらのコンポーネントのうちの1つ以上は、Open vSwitch、OpenVPN、strongSwanなどの標準化された、または一般的に利用可能なソリューションを使用する。 
【００５６】
いくつかの実施形態では、各MFN(すなわち、概念的にMFNを形成するコンポーネントのグループ）は、パブリッククラウドデータセンタにMFNを配置および設定する仮想ネットワークプロバイダの異なるテナントによって共有され得る。結合的にまたは代替的に、いくつかの実施形態における仮想ネットワークプロバイダは、特定のテナントのために、1つ以上のパブリッククラウドデータセンタに一意のMFNのセットをデプロイすることができる。例えば、セキュリティ上の理由やサービス品質上の理由から、特定のテナントが別のテナントとMFNリソースを共有したくない場合がある。このようなテナントの場合、仮想ネットワークプロバイダは、複数のパブリッククラウドデータセンタに自身のMFNのセットをデプロイすることができる。
【００５７】
いくつかの実施形態では、論理的に集中化されたコントローラクラスタ160（例えば、１つ以上のコントローラサーバのセット）は、パブリッククラウド105および110の１つ以上の内外で動作し、管理転送ノード150のパブリッククラウドコンポーネントを構成して、パブリッククラウド105および110上に仮想ネットワークを実装する。いくつかの実施形態では、冗長性および高可用性を改善するために、このクラスタ内のコントローラは、様々なロケーション（例えば、異なるパブリッククラウドデータセンタ内）に存在する。いくつかの実施形態では、コントローラクラスタは、仮想ネットワークを確立するために使用されるパブリッククラウドコンポーネントの数、またはこれらのコンポーネントに割り当てられるコンピューティングまたはネットワークリソースを、スケールアップまたはスケールダウンする。 
【００５８】
いくつかの実施形態では、コントローラクラスタ160、または仮想ネットワークプロバイダの別のコントローラクラスタは、同じパブリッククラウド105および110上に、および／または異なるパブリッククラウドプロバイダの異なるパブリッククラウド上に、別の企業テナントのための別の仮想ネットワークを確立する。コントローラクラスタに加えて、他の実施形態の仮想ネットワークプロバイダは、異なるテナントが同一または異なるパブリッククラウド上に異なる仮想ネットワークをデプロイすることを可能にする転送要素およびサービスマシンをパブリッククラウド内にデプロイする。図1Bは、パブリッククラウド105および110上にデプロイされた2つの企業テナントの2つの仮想ネットワーク100および180の例を示している。図1Cは、代替的に、パブリッククラウド105および110上にデプロイされた1つのネットワーク100と、パブリッククラウド110および115の別のペア上にデプロイされた他の仮想ネットワーク182とを備える、2つの仮想ネットワーク100および182の例を示す。
【００５９】
MFNの構成されたコンポーネントを介して、図1Aの仮想ネットワーク100は、企業テナントの異なるプライベートネットワークおよび／または異なるモバイルユーザが、これらのプライベートネットワークおよび／またはモバイルユーザに関して、（例えば、接続速度、損失、遅延および／またはコストに関して、物理的距離に関して、および／または、ネットワーク接続信頼性等に関して測定されるような）最適なロケーションにある異なるパブリッククラウドに接続することを可能にする。これらのコンポーネントはまた、いくつかの実施形態における仮想ネットワーク100が、パブリッククラウドを相互接続する高速ネットワークを使用して、パブリッククラウドを通過するデータメッセージを、インターネットを通過するそれらのトラバーサルを低減しながら、それらの宛先に転送することを可能にする。
【００６０】
いくつかの実施形態では、MFNコンポーネントはまた、エンドツーエンドのパフォーマンス、信頼性およびセキュリティを最適化する、ネットワークレイヤ、トランスポートレイヤおよびアプリケーションレイヤでの新規なプロセスを実行するように構成される。いくつかの実施形態では、これらのプロセスのうちの1つ以上は、現在のネットワークプロトコルの硬直化から解放された独自の高性能ネットワーキングプロトコルを実装する。したがって、いくつかの実施形態における仮想ネットワーク100は、インターネット自律システム、ルーティングプロトコル、またはエンドツーエンドのトランスポート機構によって制限されない。 
【００６１】
例えば、いくつかの実施形態では、MFN150のコンポーネントは、（1）最適化されたマルチパスおよび適応的な集中化ルーティングを生成し、（2）強力なQoSを提供し、（3）中間TCP分割および／または終端を通してエンドツーエンドのTCPレートを最適化し、（4）スケーラブルなアプリケーションレベルのミドルボックスサービス（例えば、ファイアウォール、侵入検知システム（IDS）、侵入防御システム（IPS）、WAN最適化など）を、グローバルネットワーク機能の仮想化（NFV）におけるクラウドのコンピューティング部分に再配置する。従って、既存のネットワークプロトコルに拘束されることなく、企業のカスタマイズされ且つ変化する要求に適合するように、仮想ネットワークを最適化することができる。また、いくつかの実施形態では、仮想ネットワークは、継続的な要求の変化に応じて、性能のケイパビリティと地理的広がりの両方において、動的かつ弾力的にスケールアップ／ダウンすることができる「従量制(pay as you go)」基盤として構成することができる。 
【００６２】
仮想ネットワーク100を実装するためには、仮想ネットワークがまたがった各パブリッククラウドデータセンタ105aから105fおよび110aから110d内の少なくとも1つの管理転送ノード150を、コントローラのセットによって構成されなければならない。図2は、本発明のいくつかの実施形態の管理転送ノード150およびコントローラクラスタ160の例を示す。いくつかの実施形態では、各管理転送ノード150は、パブリッククラウドデータセンタ内のホストコンピュータ上で動作するマシン（例えば、ＶＭ又はコンテナ）である。他の実施形態では、各管理転送ノード150は、1つのパブリッククラウドデータセンタ内の同じホストコンピュータ上で動作する複数のマシン（例えば、複数のVMまたはコンテナ）によって実現される。さらに他の実施形態では、1つのMFNの2つ以上のコンポーネントは、1つ以上のパブリッククラウドデータセンタ内の2つ以上のホストコンピュータ上で動作する2つ以上のマシンによって実現され得る。
【００６３】
図示されるように、管理転送ノード150は、測定エージェント205、ファイアウォールおよびNATミドルボックスサービスエンジン210および215、1つ以上の最適化エンジン220、エッジゲートウェイ225および230、およびクラウド転送要素235（例えば、クラウドルータ）を含む。いくつかの実施形態では、これらのコンポーネント205から235の各々は、2つ以上のコンポーネントのクラスタとして実装され得る。 
【００６４】
いくつかの実施形態におけるコントローラクラスタ160は、各コンポーネントクラスタを動的にスケールアップまたはスケールダウンして、（1）各コンポーネントの機能を実装するためのマシン（例えば、VMまたはコンテナ）を追加または削除すること、および／または（2）そのクラスタのコンポーネントを実装する以前に配置されたマシンにコンピューティングおよび／またはネットワークリソースを追加または削除することができる。したがって、パブリッククラウドデータセンタ内に配置された各MFN150を、MFNのクラスタとして見る、或いは、MFNの異なる動作を実行する複数の異なるコンポーネントクラスタを含むノードとして見ることができる。 
【００６５】
また、いくつかの実施形態では、コントローラクラスタは、パブリッククラウドデータセンタ上に仮想ネットワークを定義する異なるテナントに対して、コントローラクラスタがパブリッククラウドデータセンタに異なるMFNのセットをデプロイする。このアプローチでは、任意の2つのテナントの仮想ネットワークは、MFNを共有しない。ただし、以下に説明する実施形態では、各MFNを用いて、異なるテナントに対して異なる仮想ネットワークを実装することができる。他の実施形態では、コントローラクラスタ160は、デプロイされた自身専用のMFNのセットを有するテナントの第1のセットの各テナントの仮想ネットワークを実装する一方で、デプロイされたMFNの共有セットを有するテナントの第2のセットの各テナントの仮想ネットワークを実装することができることを、当業者は理解するであろう。
【００６６】
いくつかの実施形態では、図2に示すように、支店ゲートウェイ225およびリモートデバイスゲートウェイ230は、MFN150に接続する１つ以上の支店130およびリモートデバイス（例えば、モバイルデバイス140）とそれぞれセキュアVPN接続を確立する。このようなVPN接続の一例は、以下でさらに説明するIPsec接続である。しかしながら、当業者は、他の実施形態では、このようなゲートウェイ225および／または230が異なるタイプのVPN接続を確立することを理解するであろう。 
【００６７】
いくつかの実施形態におけるMFN150は、ファイアウォール動作、NAT動作、IPS動作、IDS動作、負荷分散動作、WAN最適化動作など、1つ以上のミドルボックスサービス動作を実行する1つ以上のミドルボックスエンジンを含む。これらのミドルボックス動作（例えば、ファイアウォール動作、WAN最適化動作など）を、パブリッククラウドに配置されたMFNに組み込むことにより、仮想ネットワーク100は、企業のデータセンタおよび／または支店において従来企業のWAN基盤によって実行されていた機能の多くをパブリッククラウドに実装する。 
【００６８】
したがって、多くのミドルボックスサービスに対して、企業のコンピューティングノード（例えば、リモートデバイス、支店、データセンタ）は、プライベートデータセンタまたは支店における企業のWAN基盤にアクセスする必要がなくなり、これらのサービスの多くがパブリッククラウドにデプロイされるようになる。このアプローチにより、企業のコンピューティングノード（リモートデバイス、支店、データセンタなど）からこれらのサービスへのアクセスが高速化され、そうでなければこのようなサービスの提供専用になるプライベートデータセンタでのコストのかかる輻輳ネットワークのボトルネックが回避される。
【００６９】
このアプローチは、パブリッククラウドデータセンタにおける各種MFNにWANゲートウェイの機能を効果的に分散させる。例えば、いくつかの実施形態の仮想ネットワーク100では、従来の企業WANゲートウェイセキュリティ機能（例えば、ファイアウォール動作、侵入検知動作、侵入防御動作など）の大部分またはすべてが、パブリッククラウドMFN（例えば、コンピューティングエンドポイントからの仮想ネットワークへのデータが受信される入力MFN）に移動される。これにより、効果的に、仮想ネットワーク100は、仮想ネットワーク100を実装する多くの異なるMFNで実現される分散WANゲートウェイを有することができる。
【００７０】
図2に示す例では、MFN150は、ファイアウォールエンジン210、NATエンジン215、および1つ以上のL4からL7の最適化エンジンを含むように示されている。当業者は、他の実施形態では、MFN150が他のミドルボックス動作を実行するための他のミドルボックスエンジンを含むことを理解するであろう。いくつかの実施形態では、ファイアウォールエンジン210は、（1）仮想ネットワークへの入力パス上のデータメッセージフロー（例えば、ゲートウェイ225および230が支店130およびモバイルデバイス140から受信して処理するデータメッセージフロー）、および（2）仮想ネットワークからの出力パス上のデータメッセージフロー（例えば、NATエンジン215およびインターネット202を介してSaaSプロバイダデータセンタに送信されるデータメッセージフロー）にファイアウォールルールを実施する。 
【００７１】
いくつかの実施形態におけるMFN150のファイアウォールエンジン210は、ファイアウォールエンジンが、データメッセージフローが仮想ネットワークに入る入力MFNと、データメッセージフローが仮想ネットワークから出る出力MFNとの間の中間ホップであるMFNに属する場合にも、ファイアウォールルールを実施する。他の実施形態では、ファイアウォールエンジン210は、データメッセージフローの入力MFNおよび／または出力MFNの一部である場合にのみ、ファイアウォールルールを実施する。
【００７２】
いくつかの実施形態では、NATエンジン215は、ネットワークアドレス変換を実行して、インターネット202を介して仮想ネットワークから第三者デバイス（例えば、SaaSプロバイダマシン）への出力パス上のデータメッセージフローの送信元ネットワークアドレスを変更する。このようなネットワークアドレス変換により、アドレス変換なしでテナントやパブリッククラウドプロバイダのプライベートネットワークアドレスを指定するデータメッセージフローを処理するように、第三者マシン（SaaSマシンなど）を適切に構成することを可能にする。これは、異なるテナントやクラウドプロバイダのプライベートネットワークアドレスが重複する可能性があるため、特に問題になる。アドレス変換により、第三者デバイス（SaaSマシンなど）からの応答メッセージが、仮想ネットワーク（メッセージを仮想ネットワークから出すMFNのNATエンジンなど）によって適切に受信されることも可能にする。 
【００７３】
いくつかの実施形態におけるMFNのNATエンジン215は、第三者マシンに届くように仮想ネットワークを出るか、または第三者マシンから仮想ネットワークに入る、各データメッセージフロー上でダブルNAT動作を行う。後述するように、2つのNAT動作のうちの1つのNAT動作は、仮想ネットワークに入るときにその入力MFNにおけるそのようなデータメッセージフロー上で実行され、もう1つのNAT動作は、仮想ネットワークから出るときにその出力MFNにおけるデータメッセージフロー上で実行される。 
【００７４】
このダブルNATアプローチは、より多くのテナントプライベートネットワークを、パブリッククラウドプロバイダのネットワークにマッピングすることを可能にする。このアプローチはまた、テナントプライベートネットワークへの変更に関するデータをMFNへ配信する負荷を低減する。入力または出力NAT動作の前に、いくつかの実施形態は、テナント識別子を使用して、テナントの送信元ネットワークアドレスを、NAT動作によってさらに別の送信元ネットワークアドレスにマッピングされる別の送信元ネットワークアドレスに最初にマッピングするテナントマッピング動作を実行する。ダブルNAT動作を実行すると、テナントプライベートネットワークへの変更に関するデータを配信するためのデータ配信負荷が軽減される。
【００７５】
最適化エンジン220は、最良のエンドツーエンド性能と信頼性のために、エンティティのデータメッセージの宛先への転送を最適化する新規のプロセスを実行する。これらのプロセスのいくつかは、現在のネットワークプロトコルの硬直化から解放される、独自の高性能ネットワークプロトコルを実現する。例えば、いくつかの実施形態では、最適化エンジン220は、中間TCP分割および／または終端を通して、エンドツーエンドのTCPレートを最適化する。 
【００７６】
クラウド転送要素235は、データメッセージフローが宛先に到達するために別のパブリッククラウドを通過する必要がある場合に、次ホップMFNのクラウド転送要素（CFE）にデータメッセージフローを転送し、またはデータメッセージフローが同じパブリッククラウドを介して宛先に到達できる場合に、同じパブリッククラウド内の出力ルータにデータメッセージフローを転送する、MFNエンジンである。いくつかの実施形態では、MFN150のCFE235はソフトウェアルータである。 
【００７７】
データメッセージを転送するために、CFEはトンネルヘッダを用いてメッセージをカプセル化する。異なる実施形態は、トンネルヘッダを用いてデータメッセージをカプセル化するために異なるアプローチを用いる。以下に説明するいくつかの実施形態は、仮想ネットワークに出入りするためのネットワーク入力／出力アドレスを識別するために1つのトンネルヘッダを使用し、データメッセージが、出力MFNに到達するために1つ以上の中間MFNを通過しなければならない場合には、次ホップMFNを識別するために別のトンネルヘッダを使用する。 
【００７８】
具体的には、いくつかの実施形態では、CFEは、2つのトンネルヘッダである、（1）仮想ネットワークに出入りするための入力CFEおよび出力CFEを識別する内部ヘッダ、および（2）次ホップCFEを識別する外部ヘッダ、を有するデータメッセージを送信する。いくつかの実施形態における内部トンネルヘッダは、仮想ネットワークプロバイダの複数の異なるテナントが仮想ネットワークプロバイダのMFNのCFEの共通セットを使用することを可能にするために、テナント識別子も含む。他の実施形態は、オーバーレイ仮想ネットワークを定義するために、異なるトンネルヘッダを定義する。
【００７９】
1つ以上のパブリッククラウド上にテナントの仮想ネットワークをデプロイするために、コントローラクラスタは、（1）テナント企業のコンピューティングノード（支店、データセンタ、モバイルユーザ、SaaSプロバイダなど）のロケーションに基づいて、テナントの仮想ネットワークに出入りする可能性のある入出力ルータを識別し、（2）仮想ネットワークを実装する他の中間パブリッククラウドルータを介して、識別された入力ルータから識別された出力ルータへ通過する経路を識別する。これらの経路を識別した後、コントローラクラスタは、パブリッククラウド内のMFNのCFE235の転送テーブルにこれらの経路を伝播する。OVSベースの仮想ネットワークルータを使用する実施形態では、コントローラはOpenFlowを使用して経路を配信する。
【００８０】
いくつかの実施形態では、コントローラクラスタ160は、最良のエンドツーエンドの性能、信頼性、およびセキュリティを達成するために、いくつかのネットワーク処理レイヤを最適化するために仮想ネットワークを実装する各MFN150のコンポーネント205から235を構成することもできる。例えば、いくつかの実施形態では、これらのコンポーネントは、（1）レイヤ3トラフィックのルーティング（例えば、最短経路、パケット重複）を最適化し、（2）レイヤ4TCP輻輳制御（例えば、セグメンテーション、レート制御）を最適化し、（3）セキュリティ機能（例えば、暗号化、精密パケット検査、ファイアウォール）を実装し、および（4）アプリケーションレイヤの圧縮機能（例えば、重複排除、キャッシュ）を実装するために、構成される。仮想ネットワーク内では、企業トラフィックはセキュリティ保護され、検査され、そしてログが記録される。 
【００８１】
いくつかの実施形態では、パブリッククラウドデータセンタ内の各MFNに対して、1つの測定エージェントがデプロイされる。他の実施形態では、パブリッククラウドデータセンタ内またはデータセンタの集合内（例えば、1つの利用可能ゾーン内のデータセンタのような、近くに関連するデータセンタの集合内）の複数のMFNは、1つの測定エージェントを共有する。レイヤ3および4の処理を最適化するために、各管理転送ノード150に関連付けられた測定エージェント205は、そのノードと他のいくつかの「隣接」ノードとの間のネットワーク接続の品質を定量化した測定値を、繰り返し生成する。 
【００８２】
異なる実施形態は、隣接ノードを異ならせるように定義する。特定のパブリッククラウドプロバイダの1つのパブリッククラウドデータセンタにおける特定のMFNについて、いくつかの実施形態における隣接ノードは、（1）特定のパブリッククラウドプロバイダの任意のパブリッククラウドデータセンタで動作する任意の他のMFN、および（2）特定のMFNと同じ「領域」内にある別のパブリッククラウドプロバイダのデータセンタで動作する任意の他のMFNを含む。 
【００８３】
異なる実施形態は、同じ領域を異なる形式で定義する。例えば、いくつかの実施形態は、特定の管理転送ノードの周りの境界形状を指定する距離に関して領域を定義する。他の実施形態は、カリフォルニア北部、カリフォルニア南部など、都市、州、または地域の観点から領域を定義する。このアプローチの前提は、同じパブリッククラウドプロバイダの異なるデータセンタが非常に高速なネットワーク接続で接続されているのに対し、異なるパブリッククラウドプロバイダのデータセンタ間のネットワーク接続は、データセンタが同じ領域内にある場合は高速である可能性が高く、データセンタが異なる領域にある場合は高速ではない可能性が高いということである。異なるパブリッククラウドプロバイダのデータセンタ間の接続では、データセンタが異なる領域にある場合、パブリックインターネットを経由して長い距離を通過する必要がある場合がある。
【００８４】
測定エージェント205は、異なる実施形態において異なる方法で測定値を生成する。いくつかの実施形態では、測定エージェントは、周期的に（例えば、毎秒、毎N秒、毎分、毎M分等）pingメッセージを、その隣接する管理転送ノードの測定エージェントのそれぞれに送信する。pingメッセージのサイズが小さい場合、大きなネットワーク接続料金は発生しない。たとえば、各ノードが10秒ごとに互いのノードにpingを送信する100ノードの場合、各ノードに対して約10Kb／sの入出力測定トラフィックが生成され、これにより、現在のパブリッククラウドの価格が与えられた場合、ノードあたり1年あたり数ドル（たとえば＄5）のネットワーク消費料金が発生する。
【００８５】
測定エージェント205は、受信する応答メッセージの速度に基づいて、ネットワーク接続スループット速度、遅延、損失、およびリンク信頼性などの測定メトリック値を計算し、更新する。これらの動作を繰り返し行うことによって、測定エージェント205は、隣接するノードへのネットワーク接続の品質を表す測定結果のマトリックスを定義し、更新する。エージェント205は、その隣接ノードの測定エージェントと相互作用するので、その測定マトリックスは、ノードのローカルクリークへの接続の品質のみを定量化する。 
【００８６】
異なる管理転送ノードの測定エージェントは、それらの測定マトリックスをコントローラクラスタ160に送り、その後、すべての異なるクリーク接続データを集約して、管理転送ノードの異なるペア間の接続の集合メッシュビューを得る。コントローラクラスタ160が、2つのペアの転送ノード間のリンクについて異なる測定値（例えば、異なる時間に1つのノードによって取られた測定値）を収集すると、コントローラクラスタは、異なる測定値からブレンドされた値を生成する（例えば、測定値の平均または加重平均を生成する）。いくつかの実施形態における集約メッシュビューは、管理転送ノードの各ペア間のすべてのネットワーク接続のフルメッシュビューであり、他の実施形態では、個々の管理転送ノードの測定エージェントによって生成されたものよりも完全なビューである。
【００８７】
図2に示すように、コントローラクラスタ160は、1つ以上の測定処理エンジン280、1つ以上のパス識別エンジン282、および1つ以上の管理インタフェース284のクラスタを含む。不必要な詳細を用いて説明を不明瞭にしないために、これらのクラスタの各々は、単一のエンジンまたはインタフェースレイヤ、即ち、測定処理レイヤ280、パス識別レイヤ282、および管理インタフェースレイヤ284に関して、以下に参照される。
【００８８】
測定処理レイヤ280は、管理転送ノードの測定エージェント205から測定マトリックスを受信し、これらの測定マトリックスを処理して、異なるペアの管理転送ノード間の接続品質を表す集約メッシュマトリックスを生成する。測定処理レイヤ280は、集合メッシュマトリックスをパス識別レイヤ282に提供する。集合メッシュマトリックスに基づいて、パス識別レイヤ282は、異なる企業データエンドポイント（例えば、異なる支店、企業データセンタ、SaaSプロバイダデータセンタおよび／またはリモートデバイス）を接続するために、仮想ネットワークを通る異なる所望のルーティングパスを識別する。次いで、このレイヤ282は、管理転送ノード150のクラウド転送要素235に配信される経路テーブル内のこれらのルーティングパスを提供する。 
【００８９】
いくつかの実施形態では、データメッセージエンドポイントの各ペアのために識別されたルーティングパスは、最適化基準のセットに基づいて最適とみなされたルーティングパスである。例えば、それは、最速のルーティングパス、最短のルーティングパス、または、インターネットを最小限に使用するパスである。他の実施形態では、パス識別エンジンは、同じ2つのエンドポイント間の複数の異なるルーティングパスを（ルーティングテーブル内で）識別し、提供することができる。これらの実施形態では、管理転送ノード150のクラウド転送要素235は、次に、それらが実施しているQoS基準または他のランタイム基準に基づいて、パスの1つを選択する。いくつかの実施形態における各CFE235は、CFEから仮想ネットワークの出力ポイントまでのルーティングパス全体を受信せず、むしろパスの次ホップを受信する。
【００９０】
いくつかの実施形態では、パス識別レイヤ282は、集合メッシュマトリックス内の測定値を、それが実行するルーティングアルゴリズムへの入力として使用して、グローバルルーティンググラフを構築する。このグローバルルーティンググラフは、測定処理レイヤ280がいくつかの実施形態で生成する測定グラフの、集約され且つ最適化されたバージョンである。図3は、いくつかの実施形態において、コントローラ測定処理レイヤ280が生成する測定グラフ300の例を示す。このグラフは、AWS内のさまざまな管理転送ノード150とGCPパブリッククラウド310および320（すなわち、AWSおよびGCPのデータセンタ）の間のネットワーク接続を示している。図4Aは、いくつかの実施形態において、測定グラフ300からコントローラパス識別レイヤ282が生成するルーティンググラフ400の例を示す。 
【００９１】
図5は、コントローラパス識別レイヤが、コントローラ測定レイヤから受信した測定グラフからルーティンググラフを生成するために使用する処理500を示す。パス識別レイヤ282は、コントローラ測定レイヤから更新された測定グラフを繰り返し受信すると、この処理500を繰り返し実行する（例えば、新しい測定グラフを受信するたびに処理500を実行する、または新しい測定グラフを受信するたびにそれぞれのN回を実行する）。他の実施形態では、パス識別レイヤ282は、このプロセスを定期的に（例えば、12時間毎または24時間毎に）実行する。
【００９２】
図示したように、パス識別レイヤは、最初に（505において）ルーティンググラフを測定グラフと同一であるように定義する（すなわち、管理転送ノードの同一ペア間に同一のリンクを有するようにする）。510において、プロセスは、測定グラフ300から不良リンクを除去する。不良リンクの例としては、過剰なメッセージ損失や信頼性の低いリンク（たとえば、過去15分間にメッセージ損失が2％を超えたリンクや、過去2分間にメッセージ損失が10％を超えたリンク）がある。図4Aは、測定グラフ300内のリンク302、304および306が、ルーティンググラフ400内で除外されることを示す。この図は、これらのリンクを破線で表すことによって、これらのリンクを除外する方法を示している。
【００９３】
次に、処理500は、515において、いくつかの計算された値とプロバイダ固有の値との加重された組合せとして、リンク重みスコア（コストスコア）を計算する。いくつかの実施形態では、重みスコアは、リンクの（1）計算された遅延値、（2）計算された損失値、（3）プロバイダネットワーク接続コスト、および（4）プロバイダコンピューティングコスト、の加重された組み合わせである。いくつかの実施形態では、プロバイダコンピューティングコストは、リンクによって接続された管理転送ノードがパブリッククラウドデータセンタ内のホストコンピュータ上で実行されるマシン（例えば、VMまたはコンテナ）であるとして考慮される。
【００９４】
520において、プロセスは、仮想ネットワーク内のデータメッセージフローのための既知の送信元および宛先IPアドレス（例えば、企業エンティティによって使用されるSaaSプロバイダの既知のIP）をルーティンググラフに追加する。いくつかの実施形態では、プロセスは、可能性のあるメッセージフローのエンドポイントの各既知のIPアドレスを、そのエンドポイントに最も近いルーティンググラフのノード（例えば、MFNを表すノード）に追加する。そのような場合、いくつかの実施形態での処理は、遅延コストがゼロで損失コストがゼロのリンクを介して、そのような各エンドポイントが仮想ネットワークに接続されることを想定している。図4Bは、2つのSaaSプロバイダのための既知のIPを、これらのSaaSプロバイダのデータセンタに最も近いデータセンタにあるルーティンググラフの2つのノード402および404（2つのMFNを表す）に追加する例を示している。この例では、1つのノードがAWSパブリッククラウドにあり、もう1つのノードがGCPパブリッククラウドにある。
【００９５】
代わりに、または、いくつかの実施形態では、処理500は、送信元および宛先エンドポイントを表すためにノードをこのグラフに追加し、これらのノードにIPアドレスを割り当て、これらの追加されたノードをルーティンググラフの他のノードに接続するリンク（例えば、パブリッククラウドのMFNを表すルーティンググラフのノード）に重み値を割り当てることによって、既知の送信元および宛先IPアドレスをルーティンググラフに追加する。フローの送信元および宛先エンドポイントがノードとして追加されると、パス識別エンジン282は、異なる送信元および宛先エンドポイント間の仮想ネットワークを通る異なる経路を識別するときに、これらのノードに到達するコスト（例えば、距離コスト、遅延コスト、および／または金銭的コストなど）を考慮することができる。
【００９６】
図4Cは、2つのSaaSプロバイダを表すために、2つのノード412および414を図4Aのノードグラフ400に追加することによって生成されるルーティンググラフ410を示す。この例では、既知のIPアドレスがノード412および414に割り当てられ、これらのノードは、重みW1およびW2が割り当てられたリンク416および418を介してノード402および404（2つのMFNを表す）に接続される。このアプローチは、図4Bに示すアプローチに2つのSaaSプロバイダの既知のIPアドレスを追加するための代替アプローチである。
【００９７】
図4Dは、より詳細なルーティンググラフ415を示す。このより詳細なルーティンググラフでは、追加のノード422および424が追加されて、AWSおよびGCPパブリッククラウド310および320にそれぞれ接続する既知のIPアドレスを持つ外部の企業コンピューティングノード（例えば、支店およびデータセンタ）を表す。これらのノード422／424の各々は、MFNを表すルーティンググラフノードの少なくとも1つに関連付けられる重み値Wiを有する、少なくとも1つのリンク426によって接続される。これらのノードのいくつか（例えば、いくつかの支店）は、同じMFNまたは異なるMFNへの複数のリンクで接続されている。
【００９８】
次に、処理500は、525において、各MFNと、企業エンティティのデータメッセージフローのための仮想ネットワークの出力ロケーションとして機能することができる、それぞれの他のMFNとの間の最低コストパス（例えば、最短パスなど）を計算する。いくつかの実施形態における出力MFNは、モバイルデバイス接続および出力インターネット接続のための候補ロケーションであるMFNと、外部の企業コンピューティングノード（例えば、支店、企業データセンタ、およびSaaSプロバイダデータセンタ）に接続されたMFNとを含む。いくつかの実施形態では、この計算は、異なるMFNのペア間の最短経路を識別する従来の最低コスト（例えば、最短経路）識別プロセスを使用する。 
【００９９】
各候補MFNペアに対して、最低コスト識別プロセスは、計算された重みスコア（すなわち、510で計算されたスコア）を使用して、MFNペアの間に複数のそのようなパスが存在するとき、最低スコアをもつパスを識別する。最低コストのパスを計算するためのいくつかの方法について、以下でさらに説明する。上述のように、パス識別レイヤ282は、いくつかの実施形態において、2つのMFNペア間の複数のパスを識別する。これは、異なる状況下で、クラウド転送要素235が異なるパスを使用することを可能にするためである。したがって、これらの実施形態では、処理500は、2つのMFNペア間の複数のパスを識別することができる。 
【０１００】
530において、プロセスは、525で識別される最低コストパスのいずれによっても使用されないMFNペア間のリンクをルーティンググラフから削除する。次に、535において、プロセスは、ルーティンググラフからクラウド転送要素235のためのルーティングテーブルを生成する。535において、プロセスは、これらのルーティングテーブルを管理転送ノードのクラウド転送要素235に配信する。535の後、プロセスは終了する。
【０１０１】
いくつかの実施形態では、仮想ネットワークは、（1）エンティティのコンピューティングノード（例えば、支店、データセンタ、モバイルユーザなど）との外部セキュア接続と、（2）インターネットを介した第三者のコンピュータ（例えば、SaaSプロバイダサーバ）への外部接続との2種類の外部接続を有する。いくつかの実施形態では、仮想ネットワークの外部の送信元ノードおよび宛先ノードで終端する各データパスについて、最適な仮想ネットワークの入出力ロケーションを発見することによって、仮想ネットワークを最適化する。例えば、支店をSaaSプロバイダサーバ（例えば、salesforce.comサーバ）に接続するために、いくつかの実施形態は、支店を最適エッジMFN(例えば、支店または支店に最も近いネットワーク接続を有するMFN）に接続し、最適に配置されたSaaSプロバイダサーバ（例えば、支店のエッジMFNに最も近いか、SaaSプロバイダサーバに接続されたエッジMFNを介して支店のエッジMFNへの最速パスを有するSaaS）への最適なエッジMFNを識別する。
【０１０２】
VPN接続を介してエンティティの各コンピューティングノード（支店、モバイルユーザなど）を最も近いMFNに関連付けるために、いくつかの実施形態では、仮想ネットワークプロバイダは、コンピューティングノードが接続するために、パブリッククラウドに1つ以上の権威(authoritative)ドメインネームサーバ（DNS）をデプロイする。いくつかの実施形態では、ある実施形態の企業コンピューティングノードが、仮想ネットワークプロバイダのMFNへのVPN接続を確立する（すなわち、VPN接続を初期化または再初期化する）必要があるたびに、コンピューティングノードは、まず、権威DNSサーバが企業コンピューティングノードに最も近いMFNとして識別するMFNの識別情報をこのサーバから得るために、このサーバを用いてその仮想ネットワークと関連付けられたアドレス（例えば、virtualnetworkX.net）を解決する。このMFNを識別するために、権威DNSサーバは、いくつかの実施形態において、MFN識別子（例えば、MFNのIPアドレス）を提供する。その後、企業コンピューティングノードは、この管理転送ノードへのVPN接続を確立する。 
【０１０３】
他の実施形態では、企業コンピューティングノードは、VNPのMFNへのVPN接続を確立する必要があるたびに、DNS解決を最初に実行しない（すなわち、特定のドメインのためのネットワークアドレスを最初に解決しない）。例えば、いくつかの実施形態では、企業コンピューティングノードは、対象のMFNが接続すべき最適なものであるかどうかを決定するために別のDNS解決を実行する前に、特定の期間（例えば、1日、1週間など）の間、DNS解決されたMFNを用いる。
【０１０４】
DNS要求の送信元IPアドレスが、ノード自体ではなく、企業コンピューティングノードのローカルDNSサーバの送信元IPアドレスである場合、いくつかの実施形態では、権威DNSサーバは、企業コンピューティングノードに最も近いMFNではなく、ローカルDNSサーバに最も近いMFNを識別する。これに対処するために、いくつかの実施形態におけるDNS要求は、ドットによって連結および区切られた1つ以上の部分（ラベル）を含むドメイン名を用いて企業コンピューティングノードを識別する。ここで、これらの部分の1つは企業を識別し、他の部分は企業のコンピューティングノードを識別する。 
【０１０５】
いくつかの実施形態では、このドメイン名は、ドメイン名内の右ラベルから左ラベルへと階層が下がるドメインおよびサブドメインを規定する。右端の最初のラベルは特定のドメインを識別し、最初のラベルの左側の2番目のラベルは企業エンティティを識別し、2番目のラベルの左側の3番目のラベルは、エンティティに複数の外部マシンロケーションがある場合のエンティティの外部マシンロケーションを識別する。例えば、いくつかの実施形態では、DNS要求は、企業コンピューティングノードを企業myCompanyのmyNodeとして識別し、アドレスmyNode.myCompany.virtualnetwork.netの解像度を求める。次いで、DNSサーバは、myNode識別子を使用して、企業コンピューティングノードがVPN接続を確立すべき入力MFNをより良く選択する。異なる実施形態では、myNode識別子は異なる方法で表現される。例えば、これは、IPアドレス、ロケーションの緯度／経度説明、GPS(地球測位システム）ロケーション、ストリートアドレスなどとしてアドレス指定されてもよい。
【０１０６】
IPアドレスが適切にロケーションを反映している場合であっても、複数の潜在的な入力ルータが存在する可能性があり、たとえば、同じクラウド内の異なるデータセンタに属している場合や、同じ領域内の異なるクラウドに属している場合などである。このような場合、いくつかの実施形態における仮想ネットワークの権威サーバは、潜在的なMFNのCFE(例えば、C5、C8、C12）のIPのリストを送り返す。いくつかの実施形態における企業コンピューティングノードは、次に、リスト内の異なるCFEにpingして測定値（例えば、距離または速度測定値）を生成し、CFE候補のセットのなかで測定値を比較することによって、最も近いものを選択する。 
【０１０７】
さらに、企業コンピューティングノードは、企業エンティティの他のコンピューティングノードによって現在使用されているMFNを識別することによって、この選択の基礎とすることができる。例えば、いくつかの実施形態では、企業のコンピューティングノードは、企業の支店の多くがすでに所定のクラウドに接続されている場合、新しいコンピューティングノードが同じクラウドに接続するインセンティブを有し、これにより、処理、レイテンシー、およびドルに関してクラウド間コストを最小限に抑えるように、各MFNに接続コストを追加する。 
【０１０８】
他の実施形態は、他のDNS解決技術を使用する。例えば、企業コンピューティングノード（例えば、支店、データセンタ、モバイルユーザなど）がDNS解決を行う必要があるたびに、企業コンピューティングノード（例えば、支店またはデータセンタのモバイルデバイスまたはローカルDNSリゾルバ）は、多数のエンティティの権威DNSリゾルバとして機能するDNSサービスプロバイダと通信する。いくつかの実施形態では、このDNSサービスプロバイダは、１つ以上のプライベートデータセンタに配置されたDNS解決マシンを有する一方、他の実施形態では、１つ以上のパブリッククラウドデータセンタの一部である。
【０１０９】
インターネットに直接接続するN個の管理転送ノードのうち、どれがSaaSプロバイダサーバに到達するために使用されるべきかを識別するために、いくつかの実施形態では、仮想ネットワーク（例えば、MFNを構成する入力MFNまたはコントローラクラスタ）は、N個の管理転送ノードから1つ以上の候補エッジMFNのセットを識別する。以下にさらに説明するように、いくつかの実施形態における各候補エッジMFNは、SaaSプロバイダサーバへの距離、ネットワーク接続速度、コスト、遅延および／または損失、ネットワーク計算コストなどの基準のセットに基づいて最適であるとみなされるエッジMFNである。 
【０１１０】
最適なエッジポイントを識別することを支援するために、いくつかの実施形態のコントローラクラスタは、エンティティに対して、最も一般的なSaaSプロバイダおよび消費者ウェブの宛先およびそれらのIPアドレスサブネットのリストを保持する。このような宛先ごとに、コントローラクラスタは、１つ以上の最適なMFN（物理的な距離、ネットワーク接続速度、コスト、損失および／または遅延、計算コストなどによって再び判断される）を候補出力ノードとして割り当てる。次に、各出力MFN候補に対して、コントローラクラスタは、各可能性のある入力MFNから候補MFNまでの最良経路を計算し、それに応じて、インターネットSaaSプロバイダまたはウェブ宛先が正しい仮想ネットワークの次ホップノードに関連付けられるように、結果であるMFN内の次ホップテーブルを設定する。 
【０１１１】
サービス宛先には、（権威DNSサーバによって提供されるように）複数のロケーションの複数のIPサブネットを介して到達できることが多いため、遅延を最小限に抑え、且つ負荷分散を提供するための、いくつかの潜在的な出力ノードが存在する。したがって、いくつかの実施形態では、コントローラクラスタは、各MFNについて最良のロケーションと出力ノードを計算し、それに応じて次ホップを更新する。また、SaaSプロバイダ（例えば、office365.com）に到達するための最良の出力ノードは、1つのパブリッククラウドプロバイダ（例えば、Microsoft Azure)を経由することもできるが、純粋に距離または接続速度からの最良の入力MFNは、別のパブリッククラウドプロバイダ（例えば、AWS）に存在するかもしれない。このような状況では、仮想ネットワークを出る前に別のクラウド（つまり、出力MFNが最適なパブリッククラウド）に移動するための遅延、処理、コストの点で最適ではないかもしれない。複数の候補エッジノードを提供することは、そのような状況において、最適エッジMFNおよび選択されたエッジMFNへの最適経路の選択を可能にする。
【０１１２】
インターネットに接続するか、または企業エンティティの企業コンピューティングノードに接続する出力MFNへの仮想ネットワークを介した最適なパスを識別するために、コントローラクラスタは、MFN間の最適なルーティングパスを識別する。上述のように、いくつかの実施形態におけるコントローラクラスタは、直接接続されたMFNのペア間の各リンクにコストをかけることによって、例えば、推定された待ち時間と金銭的コストの加重和を反映するメトリックスコアに基づいて、任意の2つのMFN間の最良経路を識別する。レイテンシと金銭的コストは、いくつかの実施形態において、（1）リンク遅延測定、（2）推定されたメッセージ処理レイテンシ、（3）同一パブリッククラウドプロバイダの別のデータセンタへ、またはパブリッククラウドプロバイダのクラウド（例えば、別のパブリッククラウドプロバイダの別のパブリッククラウドデータセンタまたはインターネットへ）を出るために、特定のデータセンタからの発信トラフィックに対するクラウド料金、および（4）パブリッククラウド内のホストコンピュータ上で実行されるMFNに関連する推定メッセージ処理コストを含む。 
【０１１３】
これらのペアワイズリンクの計算コストを使用して、コントローラクラスタは、ルーティングパスによって使用される個々のペアワイズリンクのコストを集計することによって、これらのペアワイズリンクのうちの1つ以上を使用する各ルーティングパスのコストを計算することができる。上述のように、コントローラクラスタは、次に、ルーティングパスの計算コストに基づいてそのルーティンググラフを定義し、定義されたルーティンググラフに基づいて、MFNのクラウドルータの転送テーブルを生成する。また、上述のように、コントローラクラスタは、これらのコスト計算、グラフ生成、および転送テーブルの更新および配信動作を繰り返し、定期的に（例えば、12時間毎、24時間毎など）またはMFNの測定エージェントから測定更新を受信すると実行する。
【０１１４】
MFNのCFEの転送テーブルが次ホップMFNのCFEを指すときはいつでも、CFEは近いとみなす。いくつかの実施形態では、CFEは、CFEへのセキュアでアクティブに維持されたVPNトンネルを確立する。いくつかの実施形態における安全なトンネルは、カプセル化されたデータメッセージのペイロードを暗号化することを要するトンネルである。また、いくつかの実施形態では、トンネルは、他のエンドポイントにキープアライブ(keep alive)信号を送信するトンネルの一方または両方のエンドポイントによって能動的に維持される。
【０１１５】
他の実施形態では、CFEは、セキュアでアクティブに維持されているVPNトンネルを確立しない。例えば、いくつかの実施形態では、CFE間のトンネルは、キープアライブ信号の送信を通じて能動的に監視されない静的トンネルである。また、いくつかの実施形態では、CFE間のこれらのトンネルは、それらのペイロードを暗号化しない。いくつかの実施形態では、CFEペアの間のトンネルは、2つのカプセル化ヘッダを含み、データメッセージが仮想ネットワークに出入りする（すなわち、パブリッククラウドに出入りする）ためのテナントIDと入力CFEを識別する内部ヘッダと、入力CFEから出力CFEまでゼロ以上のCFEを通過するための送信元および宛先ネットワークアドレス（例えば、IPアドレス）を特定する外部カプセル化ヘッダとを有する。
【０１１６】
いくつかの実施形態では、内部トンネルに加えて、仮想ネットワークは、上述のように、VPNトンネルを使用して企業コンピューティングノードをエッジMFNに接続する。したがって、セキュアトンネルを使用してCFEと接続する実施形態では、データメッセージは、完全にセキュアなVPNパスを使用して仮想ネットワークを通過する。 
【０１１７】
仮想ネットワークデータメッセージは、仮想ネットワーク内のカプセル化を使用して転送されるため、いくつかの実施形態では、仮想ネットワークは、テナントの異なるプライベートネットワークによって使用されるプライベートアドレスとは異なる自身のユニークなネットワークアドレスを使用する。他の実施形態では、仮想ネットワークは、それが定義されているパブリッククラウドのプライベートおよびパブリックネットワークアドレス空間を使用する。さらに別の実施形態では、仮想ネットワークは、そのコンポーネント（例えば、そのMFN、CFE、および／またはサービスの一部）のために、パブリッククラウドのプライベートおよびパブリックネットワークアドレス空間をそのコンポーネントの他のために使用する一方で、その自身のユニークなネットワークアドレスのいくつかを使用する。
【０１１８】
また、いくつかの実施形態では、仮想ネットワークは、独自のプロトコルを備えたクリーンスレート通信プラットフォームを使用する。データメッセージが全体としてソフトウェアMFNルータ（例えば、ソフトウェアCFE）を介して転送される実施形態では、仮想ネットワークは、長距離のエンドツーエンド接続のための最適化されたレート制御を提供することができる。これは、いくつかの実施形態では、各MFN150でTCP最適化プロキシエンジン220を動作させることによって達成される。（例えば、HTTPSを用いる）TCP自体が破られない他の実施形態では、これは、プロキシエンジン220が、TCP受信ウィンドウおよびACK操作を共に有するフロー毎の中間バッファリングを用いて、レート制御をセグメント化することによって達成される。
【０１１９】
クリーンスレート(clean-slate)の性質により、いくつかの実施形態では、仮想ネットワークは、より良いサービスを提供するために、そのコンポーネントの多くを最適化する。例えば、いくつかの実施形態では、仮想ネットワークは、仮想ネットワークを介してルーティングされるプレミアム帯域幅保証のVPNセットアップをサポートするために、マルチパスルーティングを用いる。いくつかの実施形態では、このようなVPNは、ATM／MPLSルーティングに類似した各MFN内の状態データを含み、それらの確立および除去は、集中的に制御される。いくつかの実施形態は、（パケットペアまたは類似のプロセスを介して）直接測定することにより、または、リンクの所与の容量を有することにより、そして既にこのリンクを介して送信されたトラフィックをこの容量から減少させることにより、送信リンク当たりの利用可能な帯域幅を識別する。 
【０１２０】
いくつかの実施形態は、制約としてリンクの残留帯域幅を使用する。例えば、リンクが利用可能な帯域幅の少なくとも2Mbpsを有していない場合、いくつかの実施形態のコントローラクラスタは、任意の宛先への最低コストパス（例えば、最短パス）を計算するために使用されるリンクのセットからリンクを除去する（例えば、グラフ400のようなルーティンググラフからリンクを除去する）。このリンクの除去後もエンドツーエンド経路が未だ使用可能である場合、新らたなVPNはこの新らたな経路を介してルーティングされる。VPNを除去すると、使用可能なキャパシティを特定のリンクに戻すことができる。これにより、このリンクを最低コストパス（最短パスなど）の計算に含めることができる。いくつかの実施形態は、例えば、MPTCP(マルチパスTCP）を使用するなど、複数パスにわたるトラフィックのロードバランシングのような、複数パスルーティングのための他のオプションを用いる。 
【０１２１】
いくつかの実施形態は、仮想ネットワーク内の2つの分離したパス（例えば、最大分離したパス）を介して、入力MFNから出力MFNへのトラフィックを複製するために、パスの並列性および安価なクラウドリンクを利用することにより、プレミアム顧客に対してより良いサービスを提供する。このアプローチでは、到着した最も早いメッセージは受け入れられ、後のメッセージは破棄される。このアプローチは、出力処理の複雑さを増加させる代わりに、仮想ネットワークの信頼性を増加させ、遅延を低減する。いくつかのそのような実施形態では、順方向誤り訂正（FEC）技法を使用して、信頼性を高める一方で、重複トラフィックを低減する。クリーンスレートの性質により、いくつかの実施形態の仮想ネットワークは、アプリケーションレイヤの最適化（例えば、重複排除およびキャッシュ動作）およびセキュリティ最適化（例えば、暗号化、DPI(ディープパケット検査）およびファイアウォール処理の追加）のような、他の上位レイヤの最適化を行う。 
【０１２２】
いくつかの実施形態の仮想ネットワークは、エニーキャストメッセージングを使用することによって仮想ネットワーク設定をさらに改善するための、クラウドプロバイダとのコラボレーションについて説明する。例えば、全てのMFNが同じ外部IPアドレスを取得する場合、いくつかの実施形態では、エニーキャスト接続を使用して、任意の新しい企業コンピューティングノードを最適エッジノード（例えば、最も近いエッジノード）に接続することは容易である。同様に、SaaSプロバイダは、このIPアドレスを取得し、最適なMFN(例えば、最も近いMFN）に接続することができる。 
【０１２３】
上述したように、異なる実施形態は、異なるタイプのVPN接続を使用して、企業コンピューティングノード（例えば、支店およびモバイルデバイス）を、企業エンティティの仮想ネットワークを確立するMFNに接続する。いくつかの実施形態は、これらのVPN接続を設定するためにIPsecを使用する。図6は、いくつかの実施形態のIPsecデータメッセージフォーマットを示す。具体的には、この図は、企業のコンピューティングノードのマシンによって生成されたデータメッセージ605の元のフォーマットを示し、データメッセージ605がカプセル化された後に（例えば、企業のコンピューティングノードまたはMFN）、IPsecトンネル（例えば、MFNまたは企業のコンピューティングノード）を介して送信するためのIPsecカプセル化データメッセージ610を示す。 
【０１２４】
この例では、IPsecトンネルは、ESPトンネルモード（ポート50）を用いて設定される。図示するように、このモードは、この例においてIPヘッダ内のTCPプロトコル識別子をESPプロトコル識別子で置き換えることによって設定される。ESPヘッダは、メッセージ615（すなわち、ヘッダ620およびペイロード625）の開始を識別する。メッセージ615は、IPsecカプセル化データメッセージの受信装置によって（例えば、MFNのIPsecゲートウェイによって）認証されなければならない。ペイロード625の開始は、メッセージ615の次のフィールド622の値によって識別される。また、ペイロード625は暗号化される。このペイロードは、元のデータメッセージ605のIPヘッダ、TCPヘッダおよびペイロード、ならびに次のフィールド622を含むパディングフィールド630を含む。
【０１２５】
いくつかの実施形態では、MFNのIPsecゲートウェイのそれぞれは、同一または異なる仮想ネットワークテナント（例えば、同一企業または異なる企業）のための複数のIPsec接続を扱うことができる。従って、いくつかの実施形態におけるMFNのIPsecゲートウェイ（例えば、ゲートウェイ230）は、トンネルID、テナントID(TID)、および企業コンピューティングノードのサブネットに関して各IPsec接続を識別する。いくつかの実施形態では、テナントの異なる企業ノード（例えば、異なる支店）は、重複するIPサブネットを持たない（RFC 1579による）。いくつかの実施形態におけるIPsecゲートウェイは、各IPsecトンネルID（IPsecトンネルヘッダに含まれる）をテナントIDにマッピングするテーブルを有する。IPsecゲートウェイが処理するように設定されている特定のテナントの場合、IPsecゲートウェイは、MFNとそのクラウド転送要素によって確立された仮想ネットワークに接続する、そのテナントのすべてのサブネットのマッピングを有する。 
【０１２６】
第１のパブリッククラウドデータセンタの入力側の第１のMFNが、テナントIDに関連付けられた、第２のパブリッククラウドデータセンタの出力側の第２のMFNに接続する宛先（ブランチやデータセンタのサブネット、SaaSプロバイダなど）に向けられたデータメッセージをIPsecトンネルを介して受信すると、第１のMFNのIPsecゲートウェイはIPsecトンネルヘッダを削除する。いくつかの実施形態では、第1のMFNのCFEは、メッセージが、入力側の第1のMFNから出力側の第2のMFNまで、直接または1つ以上の他の中間MFNを介して、パスを通過することを可能にする2つのカプセル化ヘッダでメッセージをカプセル化する。第１のMFNのCFEは、コントローラが構成したルーティングテーブルを使用して、このパスを識別する。 
【０１２７】
上述のように、いくつかの実施形態における2つのカプセル化ヘッダは、（1）カプセル化されたデータメッセージが仮想ネットワークのMFNを通過して出力MFNのCFEに到達することを可能にする次ホップMFNのCFEを指定する外部ヘッダと、（2）テナントIDと、仮想ネットワークに出入りするデータメッセージのためのMFNを識別する入力及び出力MFNのCFEを指定する内部ヘッダとを含む。
【０１２８】
具体的には、いくつかの実施形態では、内部カプセル化ヘッダは、第２の出力MFNのCFEの宛先IPアドレスと、第１の入力MFNのCFEの送信元IPアドレスとを有する有効なIPヘッダを含む。このアプローチは、標準IPルータソフトウェアをMFNのすべてのCFEで使用することを可能にする。カプセル化には、テナントID(たとえば、顧客CID）がさらに含まれる。メッセージが第２の出力MFNのCFEに到着すると、メッセージはカプセル化解除され、第２のMFNによって宛先に送信される（たとえば、第２のMFNのIPsecゲートウェイによって、テナントIDとメッセージの宛先サブネットに関連付けられた別のIPsecトンネルを介して宛先に送信される）。
【０１２９】
クラウドプロバイダによっては、マシンが送信元IPを「なりすまし」することを禁止したり、TCPおよびUDPトラフィックに他の制限を課したりすることがある。このような制限に対処するために、いくつかの実施形態は、1つ以上の経路によって使用されるMFNの隣接するペアを接続するために、外部ヘッダを使用する。いくつかの実施形態におけるこのヘッダは、送信元および宛先IPアドレスおよびUDPプロトコルパラメータを指定するUDPヘッダである。いくつかの実施形態では、入力MFNのCFEは、そのIPアドレスを外部ヘッダの送信元IPアドレスとして指定し、一方、次のMFNのCFEホップのIPアドレスを外部ヘッダの宛先IPアドレスとして指定する。 
【０１３０】
出力MFNのCFEへのパスに1つ以上の中間MFNのCFEが含まれる場合、中間CFEは、受信したダブルカプセル化メッセージの外部ヘッダの送信元IPアドレスをそのIPアドレスに置き換える。また、内部ヘッダの宛先IPアドレスを使用して、ルーティングテーブルで経路ルックアップを実行し、内部ヘッダの宛先IPアドレスへのパス上にある次ホップのMFNのCFEの宛先IPアドレスを識別する。次に、中間CFEは、外部ヘッダ内の宛先IPアドレスを、その経路テーブルルックアップを介して識別したIPアドレスで置き換える。
【０１３１】
ダブルカプセル化されたデータメッセージが出力MFNのCFEに到達すると、CFEは、内部ヘッダで宛先IPアドレスを取得した場合に、この宛先IPアドレスがデータメッセージの出力ノードであると判断し、この宛先IPアドレスがそれに属していると判断する。このCFEは、次に、データメッセージから2つのカプセル化ヘッダを削除し、それを宛先に送信する（例えば、データメッセージの元のヘッダのテナントIDと宛先IPアドレスまたはサブネットに関連付けられた別のIPsecトンネルを介して、MFNのIPsecゲートウェイを通って宛先に送信する）。
【０１３２】
図7は、いくつかの実施形態の2つのカプセル化ヘッダの例を示し、図8は、いくつかの実施形態においてこれら2つのヘッダがどのように使用されるかを説明する例を示す。以下の説明では、内部ヘッダはテナントヘッダと呼ばれる。これには、テナントの企業コンピューティングエンドノードに接続されている仮想ネットワークの入出力ノードのIDとともにテナントIDが含まれるためである。外部ヘッダは、データメッセージが入力および出力MFNのCFEの間の仮想ネットワークを通るパスを移動するときに、仮想ネットワークを通る次ホップを識別するために使用されるため、以下のVNホップトンネルヘッダと呼ばれる。
【０１３３】
図7は、元のヘッダ755およびペイロード760を有する元のデータメッセージ750をカプセル化する、VNホップトンネルヘッダ705およびテナントトンネルヘッダ720を示す。図示されるように、いくつかの実施形態におけるVNホップトンネルヘッダ705は、UDPヘッダ710およびIPヘッダ715を含む。いくつかの実施形態におけるUDPヘッダは、UDPプロトコルに従って定義される。いくつかの実施形態において、VNホップトンネルは標準のUDPトンネルであるが、他の実施形態では、このトンネルは独自のUDPトンネルである。さらに他の実施形態では、このトンネルは、標準または独自のTCPトンネルである。いくつかの実施形態におけるトンネルヘッダ705は、そのペイロードを暗号化した暗号化済みのものであり、他の実施形態においては、それは、暗号化されていないトンネルである。 
【０１３４】
以下にさらに説明するように、いくつかの実施形態におけるトンネルヘッダ705は、オーバーレイVNPネットワークを定義するために使用され、各MFNのCFEによって、アンダーレイパブリッククラウドネットワークを介して次ホップMFNのCFEに到達するために使用される。したがって、トンネルヘッダ705のIPヘッダ715は、VNPトンネルによって接続された第1および第2の隣接MFNの第1および第2のCFEの送信元および宛先IPアドレスを識別する。場合によっては（たとえば、次ホップの宛先MFNが、送信元MFNとは異なるパブリッククラウドベンダーの別のパブリッククラウドにある場合）、送信元IPアドレスと宛先IPアドレスは、MFNを含むパブリッククラウドデータセンタによって使用されるパブリックIPアドレスである。また、送信元と宛先のMFNのCFEが同じパブリッククラウドに属している場合、送信元と宛先のIPアドレスは、パブリッククラウドでのみ使用されるプライベートIPアドレスにすることができる。或いは、このような場合でも、送信元と宛先のIPアドレスがパブリッククラウドベンダのパブリックIPアドレスであり得る。 
【０１３５】
図7に示すように、テナントトンネルヘッダ720は、IPヘッダ725、テナントIDフィールド730および仮想回線ラベル735を含む。テナントトンネルヘッダ720は、データメッセージを出力MFNの出力CFEに転送するための次ホップを識別するために、入力ホップCFEの後の各ホップCFEによって使用される。したがって、IPヘッダ725は、入力CFEのIPアドレスである送信元IPアドレスと、出力CFEのIPアドレスである宛先IPアドレスとを含む。VNホップヘッダ705の送信元および宛先IPアドレスと同様に、テナントヘッダ720の送信元および宛先IPアドレスは、1つのパブリッククラウドプロバイダのプライベートIPアドレス（データメッセージが1つのパブリッククラウドプロバイダのデータセンタのみを通過する経路を通過する場合）または1つ以上のパブリッククラウドプロバイダのパブリックIPアドレス（たとえば、データメッセージが2つ以上のパブリッククラウドプロバイダのデータセンタを通過する経路を通過する場合）のいずれかであることができる。
【０１３６】
テナントヘッダ720のIPヘッダは、いくつかの実施形態では、任意の標準ソフトウェアルータおよびIPルーティングテーブルを使用してルーティングされることができる。テナントIDフィールド730は、テナントIDを含み、これは、テナントをユニークに識別するために入出力MFNで使用することができる、ユニークなテナント識別子である。いくつかの実施形態における仮想ネットワークプロバイダは、プロバイダのテナントである異なる企業エンティティに対して異なるテナントIDを定義する。VCLフィールド735は、いくつかの実施形態が、ネットワークを通してメッセージを転送するための代替の方法（非IPベースの方法）を提供するために使用する、オプションのルーティングフィールドである。いくつかの実施形態では、テナントトンネルヘッダ720は、GUE(汎用UDPカプセル化）ヘッダである。
【０１３７】
図8は、いくつかの実施形態において、これら2つのトンネルヘッダ705および710がどのように使用されるかを示す例を表している。この例では、データメッセージ800は、企業の第1の支店805内の第1のマシン802（例えば、第1のVM）から、企業の第2の支店810内の第2のマシン804（例えば、第2のVM）に送信される。2つのマシンは、2つの異なるサブネット、10．1．0．0と10．2．0．0にある。第１のマシンのIPアドレスは10．1．0．17、第２のマシンのIPアドレスは10．2．0．22である。この例では、第1の支店805は、第1のパブリッククラウドデータセンタ830内の入力MFN850に接続し、第2の支店810は、第2のパブリッククラウドデータセンタ838内の出力MFN855に接続する。また、この例では、第1および第2のパブリッククラウドデータセンタの入力MFN850および出力MFN855は、第3のパブリッククラウドデータセンタ836の中間MFN857を介して間接的に接続されている。
【０１３８】
図示されるように、マシン802からのデータメッセージ800は、最初の支店805を入力MFN850に接続するIPsecトンネル870に沿って入力MFN850に送られる。このIPsecトンネル870は、第1の支店のIPsecゲートウェイ848と、入力MFN850のIPsecゲートウェイ852との間に確立される。このトンネルは、データメッセージ800をIPsecトンネルヘッダ806でカプセル化することによって確立される。
【０１３９】
MFN850のIPsecゲートウェイ852は、データメッセージをカプセル化解除し（すなわち、IPsecトンネルヘッダ806を除去し）、カプセル化解除されたメッセージをこのMFNのCFE832に直接、または1つ以上のミドルボックスサービスマシン（例えば、図2のマシン210のようなファイアウォールマシン）を介して渡す。このメッセージを渡す際に、いくつかの実施形態では、IPsecゲートウェイまたはMFN850の他のモジュールは、メッセージをIPsecトンネルのトンネルIDおよび企業のテナントIDと関連付ける。このテナントIDは、仮想ネットワークプロバイダのレコード内の企業を識別する。 
【０１４０】
関連付けられたテナントIDおよび／またはIPsecトンネルIDに基づいて、入力MFN850のCFE832は、異なるパブリッククラウドデータセンタ内のMFNによって確立された仮想ネットワークを介して、メッセージの宛先のマシンのサブネット（すなわち、第2の支店810）への経路を識別する。たとえば、CFE832は、テナントIDおよび／またはIPsecトンネルIDを使用して、企業のルーティングテーブルを識別する。このルーティングテーブルでは、CFE832は、受信メッセージの宛先IPアドレス10．2．0．22を使用して、パブリッククラウドデータセンタ838の出力MFN855のCFE853を、データメッセージ800の宛先出力転送ノードとして識別するレコードを識別する。いくつかの実施形態では、識別されたレコードは、第2の支店810のサブネット10．2．0．0／16全体をMFN855のCFE853にマップする。
【０１４１】
出力CFE853を識別した後、入力MFN850のCFE832は、受信したデータメッセージを、そのIPヘッダ725内に入力CFE832の送信元IPおよび出力CFE853の宛先IPを含むテナントトンネルヘッダ860でカプセル化する。いくつかの実施形態では、これらのIPアドレスは、パブリックIPアドレス空間で定義される。トンネルヘッダ860はまた、入力MFN850においてデータメッセージに関連付けられたテナントIDを含む。上述したように、このトンネルヘッダは、いくつかの実施形態において、VCLヘッダ値も含む。 
【０１４２】
いくつかの実施形態では、入力CFE832は、出力CFE853への所望のCFEルーティングパス上にある次ホップMFNも識別する。いくつかの実施形態では、入力CFE832は、出力CFE853の宛先IPアドレスを使用して、そのルーティングテーブル内のこの次ホップCFEを識別する。この例の次ホップMFNのCFEは、第3のパブリッククラウドデータセンタ836の第3のMFN857のCFE856である。 
【０１４３】
次ホップMFNのCFEを識別した後、入力MFNのCFEは、カプセル化されたデータメッセージ800をVNホップ、第2のトンネルヘッダ862でカプセル化する。このトンネルヘッダは、メッセージを次ホップCFE856にルーティングできるようにする。この外部ヘッダ862のIPヘッダ715において、入力MFNのCFE832は、送信元および宛先IPアドレスを、入力CFE832の送信元IPおよび中間CFE856の宛先IPとして指定する。また、いくつかの実施形態において、そのレイヤ4プロトコルをUDPとして指定する。
【０１４４】
第3のMFN857のCFE856がダブルカプセル化されたデータメッセージを受信すると、CFE856は、VNホップ、第2のトンネルヘッダ862を取り除き、MFN855のCFE853の宛先IPアドレスをテナントヘッダ860から取り出す。このIPアドレスはCFE856に関連付けられていないため、データメッセージは宛先に到達するために別のMFNを通過しなければならない。したがって、CFE856は、取り出された宛先IPアドレスを使用して、次ホップMFNのCFE853を識別するルーティングテーブル内のレコードを識別する。次に、この変更は外部ヘッダ705を用いたデータメッセージを再カプセル化し、そのIPヘッダ715内の送信元および宛先IPアドレスを、それ自身のIPアドレスおよびMFNのCFE853の宛先IPアドレスとして指定する。次に、CFE856は、パブリッククラウドデータセンタ836および838の中間ルーティングファブリックを介して、ダブルカプセル化データメッセージ800を出力CFE853に転送する。
【０１４５】
カプセル化データメッセージを受信した後、出力CFE853は、内部ヘッダ860内の宛先IPアドレスを検索して、この宛先IPアドレスがそれに属していると判定した場合、カプセル化されたメッセージがそれに向けたものであると判定する。出力CFE853は、データメッセージ800からカプセル化ヘッダ860および862の両方を除去し、データメッセージの元のヘッダ内の宛先IPアドレスを取り出す。この宛先IPアドレスは、第２の支店のサブネット内の第２のマシン804のIPアドレスを示す。
【０１４６】
除去されたテナントトンネルヘッダ860のテナントIDを使用して、出力CFE853は、検索する正しいルーティングテーブルを識別し、受信データメッセージの元のヘッダ値から抽出された宛先IPアドレスに基づいてこのルーティングテーブルを検索する。この検索から、出力CFE853は、データメッセージを宛先に転送するために使用するIPsec接続を識別するレコードを識別する。次に、IPsecコネクション識別子とともにデータメッセージを第2のMFNのIPsecゲートウェイ858に提供し、次にこのメッセージをIPsecトンネルヘッダ859でカプセル化し、それを第2の支店810のIPsecゲートウェイ854に転送する。次に、ゲートウェイ854は、IPsecトンネルヘッダを除去し、データメッセージを宛先マシン804に転送する。
【０１４７】
ここで、図9から図15を参照して、より詳細なメッセージ処理の例について説明する。これらの例では、各テナントIPsecインタフェースがVNPトンネルと同じローカルパブリックIPアドレス上にあると想定されている。したがって、いくつかの実施形態のインタフェースは、単一のVRF(仮想ルーティングおよび転送）ネームスペースに接続される。このVRFネームスペースは、以下ではVNPネームスペースと呼ぶ。
【０１４８】
図9から図11は、テナントの2つの異なる外部マシンのロケーション（例えば、支店、データセンタなど）にある2つのコンピューティングデバイス間で送信されるメッセージを受信したときに、入力MFN、中間MFN、および出力MFNによってそれぞれ実行されるメッセージ処理プロセス900-1100を示す。いくつかの実施形態では、コントローラクラスタ160は、各CFEがテナントの異なるデータメッセージフローの入力、中間、および出力CFEとして動作するように各MFNのCFEを構成するが、そのような各CFEは、テナントの異なるデータメッセージフローのための入力、中間、および出力CFEとしてサービスを提供する候補である。
【０１４９】
プロセス900‐1100は、図8および図12の2つの例を参照して、以下に説明される。上述のように、図8は、データメッセージが中間MFNを通過して出力MFNに到達する場合の例を示している。図12は、入力MFNと出力MFNの間に中間MFNを含まない例を示す。具体的には、2つの支店が直接接続された2つのMFN1250および1255を有する2つのパブリッククラウドデータセンタ1230および1238に接続される場合の、第1の支店1205内の第1のデバイス1202から第2の支店1220内の第2のデバイス1210に送信されるデータメッセージ1200を示す。図示されるように、これらの例のMFNのCFE1232および1253は、各MFNに関連付けられたルーティング動作を実行する。
【０１５０】
いくつかの実施形態では、入力MFN850および1250の入力CFE(例えば、入力CFE832または1232）は、プロセス900を実行する。図9に示すように、入力プロセス900は、受信データメッセージ内のIPsecトンネル（例えば、806または1206）の識別子に基づいて、（905において）最初にテナントルーティングコンテキストを識別することによって開始する。いくつかの実施形態では、IPsecゲートウェイまたは他のMFNモジュールは、マッピングテーブルにIPsecトンネルIDに対するテナントIDを格納する。データメッセージが特定のIPsecトンネルに沿って受信されると、IPsecゲートウェイはIPsecトンネルIDを抽出する。このIPsecトンネルIDは、このゲートウェイまたは別のMFNモジュールが、そのマッピングテーブルを参照することによって、関連するテナントIDを識別するために使用する。テナントIDを識別することで、プロセスは、使用するテナントルーティングテーブルまたはVRFネームスペースのテナント部分を識別する。
【０１５１】
910で、プロセスは、このデータメッセージを受信することを考慮して、識別されたIPsecトンネルのRX(受信）カウンタをインクリメントする。次に、915において、プロセスは、識別されたテナントルーティングコンテキスト（例えば、VRF名前空間のテナントの部分）において、パブリッククラウドデータセンタを介して構築されたテナントの仮想ネットワークを出るための出力インタフェースのIPアドレスを識別するために、経路ルックアップ（例えば、最長のプレフィックスの一致、LPM、ルックアップ）を実行する。ブランチ・ツー・ブランチの例では、出力インタフェースは、宛先ブランチに接続されたMFNの出力CFE(CFE853または1253など）のIPアドレスである。
【０１５２】
920において、プロセスは、受信したデータメッセージにテナントトンネルヘッダ（例えば、ヘッダ860または1260）を追加し、このトンネルヘッダの送信元および宛先IPアドレスとして、入力CFEの送信元IPアドレス（例えば、入力CFE832または1252）および出力CFEの宛先IPアドレス（例えば、出力CFE853または1253）を埋め込む。テナントヘッダでは、テナントID(905で識別）もテナントヘッダに格納される。920で、プロセスはテナントヘッダの外部にVNホップトンネルヘッダ（例えばヘッダ862または1262）を追加し、そのIPアドレスをこのヘッダの送信元IPアドレスとして格納する。このプロセスはまた、（920で）VNPトンネルヘッダのUDPパラメータ（例えばUDPポート）を規定する。
【０１５３】
次に、925において、プロセスは、このデータメッセージの送信を考慮するために、テナントのためのVN送信カウンタをインクリメントする。930において、プロセスは、このデータメッセージの次ホップインタフェースを識別するために、識別されたVNPルーティングコンテキスト（例えば、VRF名前空間のVNPの部分）において、経路ルックアップ（例えば、LPMルックアップ）を実行する。いくつかの実施形態では、この経路ルックアップは、（例えば、VRF名前空間のVNPの部分における）出力CFEの宛先IPに少なくとも部分的に基づいたLPMルックアップである。
【０１５４】
935で、プロセスは、次ホップ出力インタフェースが入力CFEのローカルインタフェース（例えば、物理または仮想ポート）であるかどうかを判定する。もしそうなら、プロセスは（937で）VNホップ外部トンネルヘッダの宛先IPアドレスを915で識別された出力インタフェースIPアドレスとして定義する。次に、940において、プロセスは、宛先の出力CFEに転送できるように、そのローカルインタフェースにダブルカプセル化データメッセージを提供する。940の後、プロセス900は終了する。
【０１５５】
図12は、入力CFE1232が第1の支店1205のデバイス1202から受信するデータメッセージ1200の動作905から940の例を示す。図示されるように、このCFEのMFN1250は、IPsecゲートウェイ1252において、このデータメッセージを、第1の支店1205のIPsecゲートウェイ1248からのIPsecカプセル化メッセージとして受信する。受信CFE1232は、受信したメッセージ1200を（IPsecヘッダがIPsecゲートウェイ1252によって除去された後に）VNホップトンネルヘッダ1262およびテナントトンネルヘッダ1260でカプセル化し、このダブルカプセル化されたメッセージをパブリッククラウド1238のMFN1255の出力CFE1253に転送する。図示されるように、この例では、トンネルヘッダ1260および1262の両方の送信元および宛先IPアドレスは同一である。これらの2セットのIPアドレスが同一である場合、CFE856のような、介在するCFEを介してデータメッセージがルーティングされない場合、いくつかの実施形態は、外部IPヘッダ1262を使用しない。
【０１５６】
プロセスが（935で）次ホップ出力インタフェースが入力CFEのローカルインタフェースではなく、むしろ別のルータの宛先IPアドレスであると判定する場合、プロセスは（945で）VNホップトンネルヘッダに、次ホップ中間CFE(例えば、中間CFE856）の宛先IPアドレスをVNホップトンネルヘッダの宛先IPアドレスとして埋め込む。 
【０１５７】
次に、950において、プロセスは、識別されたVNPルーティングコンテキスト（例えば、VRFネームスペースのVNPの部分）において、別の経路ルックアップ（例えば、LPMルックアップ）を実行する。今回、ルックアップは、VNPトンネルヘッダで識別される中間CFEのIPアドレスに基づいている。中間CFE(例えば、CFE856）は、入力CFE(例えば、CFE832）のための仮想ネットワークにおける次ホップCFEであるので、ルーティングテーブルは、中間CFEに送られるデータメッセージのためのローカルインタフェース（例えば、ローカルポート）を識別する。したがって、VNPルーティングコンテキストにおけるこのルックアップは、受信CFEが（950において）ダブルカプセル化されたメッセージを提供するローカルインタフェースを識別する。その後、プロセスは、このデータメッセージの送信を考慮して、VN中間カウンタを（955で）インクリメントする。955の後、プロセスは終了する。
【０１５８】
図10は、出力MFNのCFE(例えば、CFE853または1253）が、MFNに接続された企業コンピューティングノード（例えば、支店、データセンタ、リモートユーザのロケーション）に転送されるべきデータメッセージを受信したときに、いくつかの実施形態において実行するプロセス1000を示す。図示されるように、プロセスは、最初に、仮想ネットワークに関連付けられたインタフェース上でデータメッセージを（1005で）受信する。このメッセージは、VNホップトンネルヘッダ（ヘッダ862または1262など）とテナントトンネルヘッダ（ヘッダ860または1260など）でカプセル化される。 
【０１５９】
1010で、プロセスは、VNホップトンネルヘッダの宛先IPアドレスがそのCFEの宛先IPアドレスであると判定する（CFE853または1253のIPアドレスなど）。次に、1015で、プロセスは2つのトンネルヘッダを除去する。その後、プロセスは、除去されたテナントトンネルヘッダからテナントIDを（1020で）取得する。受信したデータメッセージを考慮するために、CFEは、抽出されたテナントIDで指定されたテナントに対して保持しているRX(受信）カウンタを（1025で）インクリメントする。 
【０１６０】
次に、1030において、プロセスは、このデータメッセージの次ホップインタフェースを識別するために、識別されたテナントルーティングコンテキスト（すなわち、1020で抽出されたテナントIDによって識別されたテナントのルーティングコンテキスト）において、経路ルックアップ（例えば、LPMルックアップ）を実行する。プロセスは、いくつかの実施形態において、受信データメッセージの元のヘッダ（例えば、ヘッダ755）内の宛先IPアドレスに基づいて、このルックアップを実行する。このルックアップによって識別されるレコードから、プロセス1000は、データメッセージが宛先に送られる必要があるIPsecインタフェースを識別する。従って、プロセス1000は、カプセル化解除され受信されたデータメッセージを、そのMFNのIPsecゲートウェイ（例えば、ゲートウェイ858または1258）に送信する。 
【０１６１】
次に、このゲートウェイは、IPsecトンネルヘッダ（例えば、トンネルヘッダ859または1259）でデータメッセージをカプセル化し、それを宛先の企業コンピューティングノード（例えば、宛先支店）のゲートウェイ（例えば、ゲートウェイ854または1254）に転送する。データメッセージはそこでカプセル化解除され、宛先に転送される。1030の後、CFEまたはそのMFNは、宛先の企業コンピューティングノード（例えばゲートウェイ854と858の間のIPsec接続、またはゲートウェイ1254と1258の間のIPsec接続）へのIPsec接続に沿ったメッセージの送信を管理するカウンタを（1035で）インクリメントする。
【０１６２】
図11は、いくつかの実施形態において、中間MFNのCFE(例えば、CFE856）が、別のMFNの別のCFEに転送されるべきデータメッセージを受信したときに実行するプロセス1100を示す。図示されるように、プロセスは、最初に、仮想ネットワークに関連付けられたインタフェース上で（1105において）データメッセージを受信する。いくつかの実施形態では、このメッセージは、2つのトンネルヘッダである、VNトンネルヘッダ（例えば、ヘッダ862）およびテナントトンネルヘッダ（例えば、ヘッダ860）でカプセル化されている。 
【０１６３】
1110において、プロセスは、このトンネルヘッダの宛先IPアドレスがそのCFEの宛先IPアドレスであると判定されるため、VNホップトンネルを終了する（例えば、CFE856の宛先IPアドレス）。次に、1115で、プロセスはVNホップトンネルヘッダが正しいUDPポートを指定するかどうかを判定する。そうでない場合、プロセスは終了する。それ以外の場合、1120で、プロセスはVNホップトンネルヘッダを削除する。受信したデータメッセージを考慮するために、CFEは、中間ホップCFEとして受信したメッセージの数を定量化するために、保持するRX(受信）カウンタを（1125において）インクリメントする。
【０１６４】
1130において、プロセスは、このデータメッセージの次ホップインタフェースを識別するために、識別されたVNPルーティングコンテキスト（例えば、VRF名前空間のVNPの部分）において、経路ルックアップ（例えば、LPMルックアップ）を実行する。いくつかの実施形態では、この経路ルックアップは、内部テナントトンネルヘッダで識別される出力CFEの宛先IPに少なくとも部分的に基づいた（例えば、VRF名前空間のVNPの部分における）LPMルックアップである。 
【０１６５】
次に、プロセスは、（1135において）次ホップ出力インタフェースが中間CFEのローカルインタフェースであるかどうかを決定する。その場合、プロセスは（1140において）テナントトンネルヘッダを用いて既にカプセル化されているデータメッセージにVNホップトンネルヘッダを追加する。プロセスは、VNホップトンネルヘッダの宛先IPアドレスを、テナントトンネルヘッダで指定されている出力CFEの宛先IPアドレスに（1142において）設定する。また、VNホップトンネルヘッダの送信元IPアドレスを（1142において)CFEのIPアドレスに設定する。このトンネルヘッダでは、プロセスはUDP属性（例えばUDPポートなど）も設定する。
【０１６６】
次に、1144において、プロセスは、データメッセージを宛先の出力CFEに転送できるように、（1130で識別される）そのローカルインタフェースに、ダブルカプセル化されたデータメッセージを提供する。このVNホップトンネルのカプセル化解除および転送の一例は、図8のCFE856の動作を参照して上述した。受信したデータメッセージを考慮するために、CFEは、中間ホップCFEとして送信したメッセージの数を定量化するために保持するTX(送信）カウンタを（1146で）インクリメントする。1146の後、プロセス1100は終了する。
【０１６７】
一方、プロセスは、（1135において）次ホップ出力インタフェースがそのCFEのローカルインタフェースではなく、むしろ別のルータの宛先IPアドレスであると判定した場合、プロセスは、以前にVNホップトンネルヘッダを削除したデータメッセージに（1150において）VNホップトンネルヘッダを追加する。新しいVNホップトンネルヘッダでは、処理1100がそのCFEの送信元IPアドレスと次ホップ中間CFEの宛先IPアドレス（1130で特定）を、VNホップトンネルヘッダの送信元および宛先IPアドレスとして（1150において）埋め込む。このVNPトンネルヘッダは、UDPの宛先ポートを持つUDPレイヤ4プロトコルも指定する。
【０１６８】
次に、1155において、プロセスは、識別されたVNPルーティングコンテキスト（例えば、VRFネームスペースのVNPの部分）において、別の経路ルックアップ（例えば、LPMルックアップ）を実行する。今回、ルックアップは、新しいVNホップトンネルヘッダで識別される次ホップ中間CFEのIPアドレスに基づく。この中間CFEは、仮想ネットワーク内の現在の中間CFEの次ホップであるため、ルーティングテーブルは、次ホップ中間CFEに送信されるデータメッセージのローカルインタフェースを識別する。したがって、VNPルーティングコンテキストにおけるこのルックアップは、現在の中間CFEがダブルカプセル化されたメッセージを提供するためのローカルインタフェースを識別する。次に、プロセスは、このデータメッセージの送信を考慮するための（1160において）VN中間TX(送信）カウンタをインクリメントする。1160の後、プロセスは終了する。
【０１６９】
図13は、テナントの企業コンピューティングデバイス（例えば、支店内）から別のテナントマシン（例えば、別の支店、テナントデータセンタまたはSaaSプロバイダデータセンタ内）に送信されるテナントのメッセージを受信したときに、入力MFNのCFEによって実行されるメッセージ処理プロセス1300を示す。図9のプロセス900は、後述するように、このプロセス1300のサブセットである。図13に示すように、プロセス1300は、入ってくるIPsecトンネルの識別子に基づいて、テナントルーティングコンテキストを（905において）最初に識別することによって、開始される。 
【０１７０】
1310において、プロセスは、受信データメッセージのヘッダ内の送信元IPアドレスと宛先IPアドレスの両方がパブリックIPアドレスであるかどうかを判定する。そうである場合、プロセス（1315）は、データメッセージをドロップし、受信データメッセージのIPsecトンネルのために保持しているドロップカウンタをインクリメントする。1315において、プロセスがカウンタをドロップするのは、テナントのIPsecトンネルを介してメッセージを受信する場合には、パブリックIPアドレスとの間でアドレス指定されたメッセージを受信すべきではないためである。いくつかの実施形態では、プロセス1300はまた、ICMPエラーメッセージを送信元の企業コンピューティングマシンへ送り返す。
【０１７１】
一方、（1310において、)データメッセージがパブリックIPアドレスからのものではなく、他のパブリックIPアドレスへのものでもないと判定した場合、（1320において）受信データメッセージのヘッダ内の宛先IPアドレスがパブリックIPアドレスであるか否かを判定する。その場合、プロセスは、プロセス1300の開始時に実行された動作905を除き、図9のプロセス900を実行するために1325に遷移する。1325の後、プロセス1300は終了する。一方、プロセス1300は、（1320において）受信データメッセージのヘッダ内の宛先IPアドレスがパブリックIPアドレスでないと判定した場合、このデータメッセージを受信するために、識別されたIPsecトンネルのRX(受信）カウンタを（1330で）インクリメントする。
【０１７２】
次に、プロセス1300は、識別されたテナントルーティングコンテキスト（例えば、VRFネームスペースのテナントの部分）において、（1335において）経路ルックアップ（例えば、LPMルックアップ）を実行する。このルックアップは、パブリッククラウドデータセンタを介して構築されたテナントの仮想ネットワークを出るための出力インタフェースのIPアドレスを識別する。図13に示す例では、プロセス1300は、データメッセージがSaaSプロバイダデータセンタ内のマシンに向けたものである場合、ルックアップ動作1335に到達する。したがって、このルックアップは、テナントの仮想ネットワークを出てSaaSプロバイダマシンに到達するための出力ルータのIPアドレスを識別する。いくつかの実施形態では、すべてのSaaSプロバイダ経路は、1つの経路テーブルまたはVRFネームスペースの1つの部分にインストールされ、他の実施形態では、異なるSaaSプロバイダの経路は、異なる経路テーブルまたは異なるVRFネームスペース部分に格納される。
【０１７３】
1340において、プロセスは、受信データメッセージにテナントトンネルヘッダを追加し、このトンネルヘッダに送信元および宛先IPアドレスとして、入力CFEの送信元IPアドレスおよび出力ルータの宛先IPアドレスを埋め込む。次に、1345において、プロセスは、このデータメッセージの送信を考慮するために、テナントのためのVN送信カウンタをインクリメントする。1350において、プロセスは、このデータメッセージの次ホップインタフェースとしてそのローカルインタフェースの一つを識別するために、VNPルーティングコンテキスト（例えば、VNPネームスペースのVNPの部分）において、経路ルックアップ（例えば、LPMルックアップ）を実行する。次ホップが別のCFEである場合（他のパブリッククラウドデータセンタでの場合など）、いくつかの実施形態でのプロセスは、さらにVNホップヘッダでデータメッセージをカプセル化し、VNホップヘッダの送信元および宛先としてCFEのIPアドレスと他のCFEのIPアドレスを組み込む。1355において、プロセスは、データメッセージをその出力ルータに転送できるようにするために、カプセル化されたデータメッセージを識別されたローカルインタフェースに提供する。1355の後、プロセス1300は終了する。 
【０１７４】
いくつかの場合には、入力MFNは、そのCFEが別のMFNのCFEを経由せずにデータメッセージの宛先マシンに直接転送することができる、テナントのためのデータメッセージを受信することができる。このようないくつかの場合において、CFEがテナント固有の情報を他の後続のVN処理モジュールに中継する必要がない場合、または必要な情報を他のメカニズムを介して後続のVN処理モジュールに提供可能である場合、データメッセージをテナントヘッダまたはVNホップヘッダでカプセル化する必要がない。 
【０１７５】
たとえば、テナントのデータメッセージを外部のSaaSプロバイダデータセンタに直接転送するには、後でさらに説明するように、入力MFNのNATエンジン215は、テナント識別子に基づいてNAT動作を実行しなければならない。入力MFN内の入力CFEまたは別のモジュールは、入力MFNの関連するNATエンジン215にテナント識別子を提供しなければならない。入力CFEおよびNATエンジンが同じコンピュータ上で実行される場合、いくつかの実施形態は、この情報を共有メモリの場所に格納することによって、これら2つのモジュール間でこの情報を共有する。一方、CFEおよびNATエンジンが同じコンピュータ上で実行されない場合、いくつかの実施形態は、他のメカニズム（例えば、帯域外通信）を使用して、入力CFEおよびNATエンジン間でテナントIDを共有する。しかしながら、このような場合、他の実施形態は、入力MFNの異なるモジュール間で保存IDを記憶し、共有するためにカプセル化ヘッダを使用する（すなわち、帯域内通信を使用する）。
【０１７６】
以下にさらに説明するように、いくつかの実施形態は、テナントの仮想ネットワークの外部にメッセージを送信する前に、データメッセージの送信元IP／ポートアドレスに対して1または2の送信元NATの動作を実行する。図14は、出力ルータで実行されているNAT動作を示している。しかしながら、以下にさらに説明するように、いくつかの実施形態は、この追加のNAT動作が図13を参照して上述されていないとしても、入力ルータにおけるデータメッセージに対して別のNAT動作を実行する。
【０１７７】
図14は、出力ルータが、インターネットを介してSaaSプロバイダデータセンタに転送されるべきデータメッセージを受信したときに、いくつかの実施形態において実行する処理1400を示す。図示されるように、プロセスは、最初に、仮想ネットワークに関連付けられたインタフェース上で（1405において）データメッセージを受信する。このメッセージは、テナントトンネルヘッダでカプセル化される。 
【０１７８】
1410で、プロセスは、このトンネルヘッダの宛先IPアドレスがルータの宛先IPアドレスであると判定するため、テナントトンネルヘッダを除去する。その後、プロセスは、除去されたトンネルヘッダからテナントIDを（1415において）取得する。受信されたデータメッセージを考慮するために、プロセスは、抽出されたテナントIDによって指定されたテナントに対して保持するRX（受信）カウンタを（1420において）インクリメントする。 
【０１７９】
次に、1425において、プロセスは、データメッセージの元のヘッダ内の宛先IPが、出力ルータのローカルインタフェース（例えば、ローカルポート）を介して到達可能なパブリックIPであるかどうかを判定する。このローカルインタフェースは、VNPトンネルに関連付けられていないインタフェースである。そうでない場合、プロセスは終了する。それ以外の場合、プロセスは（1430において）送信元NAT動作を実行して、このメッセージのヘッダ内のデータメッセージの送信元IP／ポートアドレスを変更する。NAT動作およびそれを実行する理由は、図16および図17を参照して、以下にさらに説明される。
【０１８０】
1430の後に、プロセスは、（1435において）このデータメッセージの次ホップインタフェースを識別するために、インターネットルーティングコンテキスト（すなわち、ルーティングデータのインターネットルーティング部分、例えば、ルータのインターネットVRF名前空間）において経路ルックアップ（例えば、LPMルックアップ）を実行する。プロセスは、いくつかの実施形態において、受信データメッセージの元のヘッダの宛先ネットワークアドレス（例えば、宛先IPアドレス）に基づいて、このルックアップを実行する。このルックアップによって識別されるレコードから、プロセス1400は、データメッセージが宛先に送られる必要があるローカルインタフェースを識別する。したがって、1435において、プロセス1400は、送信元ネットワークアドレス変換データメッセージを、その宛先に転送するために、その識別されたローカルインタフェースに提供する。1435の後、プロセスは、メッセージをSaaSプロバイダに送信するために保持するカウンタを（1440において）インクリメントし、その後終了する。
【０１８１】
図15は、SaaSプロバイダマシンからテナントマシンに送信されるメッセージを受信する入力ルータによって実行されるメッセージ処理プロセス1500を示している。図示されるように、入力プロセス1500は、最初に、いくつかまたは全てのSaaSプロバイダ通信に使用されるパブリックIPアドレスを有する専用の入力インタフェース上のデータメッセージを受信することによって（1505において）開始する。いくつかの実施形態において、この入力インタフェースは、仮想ネットワークとの通信に使用されるものとは異なるIPアドレスを有する、異なるインタフェースである。
【０１８２】
メッセージを受信した後、プロセスは、受信データメッセージのヘッダに含まれる宛先IPアドレスを使用して、パブリックインターネットルーティングコンテキストで（1510において）経路ルックアップを実行する。このルックアップに基づいて、プロセスは宛先IPアドレスがローカルであり、有効なNAT動作に関連付けられているかどうかを（1515において）判定する。そうでない場合、プロセスは終了する。それ以外の場合、プロセスは（1520において）インターネットRX（受信）カウンタをインクリメントして、データメッセージを受信することを考慮する。
【０１８３】
次に、1525で、プロセスは、データメッセージの宛先IP／ポートアドレスを、仮想ネットワークが特定のテナントに関連付けられている新しい宛先IP／ポートアドレスに変換するリバースNAT動作を実行する。このNAT動作では、テナントIDも生成される（たとえば、テナントIDを変換された宛先IPに関連付けるマッピングテーブルからテナントIDを取得したり、新しい宛先IP／ポートアドレスを取得するために使用されるのと同じマッピングテーブルからテナントIDを取得したりする）。いくつかの実施形態では、処理1500は、処理1400が（1430において）そのSNAT動作を実行したときに（1525において）そのリバースNAT動作を実行するために、処理1400が生成した接続レコードを使用する。この接続レコードには、SNATおよびDNAT動作で使用される内部IP／ポートアドレスと外部IP／ポートアドレスのマッピングが含まれる。
【０１８４】
変換された宛先ネットワークアドレスに基づいて、プロセスは、（1530において）識別されたテナントルーティングコンテキスト（すなわち、テナントIDによって指定されたルーティングコンテキスト）で経路ルックアップ（例えば、LPMルックアップ）を実行し、テナントの仮想ネットワークを出て企業コンピューティングノード（例えば、支店）内のテナントのマシンに到達するための出力インタフェースのIPアドレスを識別する。この出力インタフェースは、いくつかの実施形態における出力MFNの出力CFEのIPアドレスである。1530において、プロセスは、受信データメッセージにテナントトンネルヘッダを追加し、このトンネルヘッダの送信元および宛先IPアドレスとして、入力ルータのIPアドレスおよび出力CFEのIPアドレスを埋め込む。次に、1535において、プロセスは、このデータメッセージの送信を考慮するために、テナントのためのVN送信カウンタをインクリメントする。 
【０１８５】
1540において、プロセスは、識別されたVNPルーティングコンテキスト（例えば、ルータのVRFネームスペースのようなルーティングデータのVNPの部分）において、入力ルータがカプセル化されたメッセージを提供するためのローカルインタフェース（例えば、その物理または仮想ポート）を識別するために、経路ルックアップ（例えば、LPMルックアップ）を実行する。次に、プロセスは（1540において）受信データメッセージにVNホップヘッダを追加し、このVNホップヘッダの送信元および宛先IPアドレスとして、入力ルータのIPアドレスと次ホップCFEのIPアドレスを埋め込む。1555の後、プロセスは終了する。
【０１８６】
上述のように、いくつかの実施形態におけるMFNは、仮想ネットワークへのデータメッセージの入出力パス上でNAT動作を行うNATエンジン215を含む。NAT動作は、今日、多くのコンテキストにおいて、そして多くのデバイス（例えば、ルータ、ファイアウォール等）によって、一般に実行される。例えば、NAT動作は一般に、トラフィックがプライベートネットワークから出て、インターネットで使用されている規制されたパブリックIPアドレス空間から内部IPアドレス空間を隔離するときに実行される。NAT動作では、通常、1つのIPアドレスが別のIPアドレスにマップされる。 
【０１８７】
インターネットに接続されたコンピュータの急増に伴い、課題は、コンピュータの数が利用可能なIPアドレスの数を上回ることである。残念ながら、4,294,967,296もの利用可能なユニークなアドレスがあるとしても、各コンピュータに一意のパブリックIPアドレスを割り当てることは、すでに実用的ではない。回避する方法の1つは、プライベートネットワークのエッジポイントにあるルータにのみパブリックIPアドレスを割り当てることである。一方、ネットワーク内の他の装置は、内部プライベートネットワーク内でのみ一意のアドレスを取得する。デバイスが内部プライベートネットワーク外のデバイスと通信する場合、そのトラフィックは通常、NAT動作を実行するインターネットゲートウェイを通過し、このトラフィックの送信元IPをインターネットゲートウェイのパブリック送信元IPアドレスに置き換える。 
【０１８８】
プライベートネットワークのインターネットゲートウェイは、インターネット上に登録されたパブリックアドレスを取得するが、このゲートウェイに接続するプライベートネットワーク内の各デバイスは、登録されていないプライベートアドレスを受信する。内部プライベートネットワークのプライベートアドレスは、任意の範囲のIPアドレスにすることができる。しかしながら、IETF(Internet Engineering Task Force)は、プライベートネットワークが使用するプライベートアドレスのいくつかの範囲を提案している。これらの範囲は、ルータがプライベートアドレスとパブリックアドレスを容易に区別できるように、一般にパブリックインターネットでは利用可能ではない。これらのプライベートアドレスの範囲はRFC1918として知られ、（1）クラスA 10.0.0.0〜10.255.255.255、（2）クラスB 172.16.0.0〜172.31.255.255、（3）クラスC 192.168.0.0〜192.168.255.255である。
【０１８９】
プライベートネットワークから出るデータメッセージフローで送信元IP変換を実行することが重要である。これにより、外部デバイスは、同じ内部IPアドレスを使用する異なるプライベートネットワーク内の異なるデバイスを区別できる。外部デバイスがプライベートネットワーク内のデバイスに応答メッセージを送信する必要がある場合、外部デバイスはインターネット上のユニークでルーティング可能なパブリックアドレスに応答を送信する必要がある。多数のプライベートネットワーク内の多数のデバイスで使用される可能性がある内部デバイスの元のIPアドレスは使用することができない。外部デバイスは、元のNAT動作が内部デバイスのプライベートの送信元IPアドレスを置き換えた、パブリックIPアドレスに応答を送信する。この応答メッセージを受信した後、プライベートネットワーク（例えば、ネットワークのゲートウェイ）は、応答のパブリックの宛先IPアドレスを内部デバイスのIPアドレスに置き換えるために、別のNAT動作を実行する。
【０１９０】
プライベートネットワーク内の多くのデバイス、およびこれらのデバイス上で実行される多くのアプリケーションは、プライベートネットワークに関連付けられた1つまたは有限のパブリックIPアドレスを共有する必要がある。したがって、NAT動作は通常、レイヤ4ポートアドレス（例えば、UDPアドレス、TCPアドレス、RTPアドレスなど）を変換して、これらのマシン上の異なる内部マシンおよび／または異なるアプリケーション上で開始または終了される内部メッセージフローに外部メッセージフローを一意に関連付けることができるようにする。NAT動作は、多くのコンテキストにおいて、これらの動作が、接続を追跡し、テーブル、メッセージの再構成、タイムアウト、期限切れ追跡された接続の強制終了などを動的に処理する必要があるため、ステートフルオペレーションであることもよくある。
【０１９１】
上述のように、いくつかの実施形態の仮想ネットワークプロバイダは、複数のパブリッククラウド上の異なるテナントへのサービスとしての仮想ネットワークを提供する。これらのテナントは、プライベートネットワークで共通のIPアドレスを使用し、仮想ネットワークプロバイダの共通のネットワークリソース（パブリックIPアドレスなど）を共有する。いくつかの実施形態では、異なるテナントのデータトラフィックは、トンネルを介してオーバーレイネットワークのCFE間で伝送され、トンネルは各メッセージを一意のテナントIDでマークする。これらのテナント識別子を使用すると、プライベートのテナントIPスペースが重複している場合でも、メッセージを送信元デバイスに返信することができる。たとえば、テナント識別子により、テナント17の支店から送信元アドレス10.5.12.1を使用してAmazon.comに送信されたメッセージと、テナント235の支店から同じ送信元アドレス（同じ送信元ポート番号55331も含む）を使用してAmazon.comに送信されたメッセージを区別することができる。 
【０１９２】
RFC1631に従って実装された標準的なNATはテナンシー(tenancy)の概念をサポートしていないため、同じプライベートIPアドレスを持つ2つのメッセージを区別する方法がない。しかしながら、いくつかの実施形態の多くの仮想ネットワークのデプロイにおいて、今日では、多くの成熟したオープンソース、高性能な実装が存在するため、標準NATエンジンを使用することは有益である。実際、今日の多くのLinuxカーネルは標準機能としてNATエンジンを機能させている。
【０１９３】
テナントの仮想ネットワークの異なるテナントに標準NATエンジンを使用するために、いくつかの実施形態の仮想ネットワークプロバイダは、標準NATエンジンを使用する前にテナンシーマッピング（TM）エンジンを使用する。図16は、仮想ネットワークのインターネットへの出力パス上にある各仮想ネットワークゲートウェイ1602内にデプロイされるそのようなTMエンジン1605を示す。図示されるように、各TMエンジン1605は、インターネット1625を介してSaaSプロバイダデータセンタ1620へのメッセージの出力パス上のNATエンジン1610の前に配置される。いくつかの実施形態では、MFNの各NATエンジン215は、（TMエンジン1605のような）TMエンジンおよび（NATエンジン1610のような）標準NATエンジンを含む。
【０１９４】
図16に示される例では、メッセージフローは、2つの支店1655および1660、および2つの仮想ネットワークテナントのデータセンタ1665から来て、同じ入力ゲートウェイ1670を介して仮想ネットワーク1600に入るが、必ずしもそうである必要はない。いくつかの実施形態における仮想ネットワーク1600は、複数のパブリッククラウドベンダの複数のパブリッククラウドデータセンタにわたって定義される。いくつかの実施形態では、仮想ネットワークゲートウェイは、管理転送ノードの一部であり、TMエンジンは、出力MFN内のNATエンジン1610の前に配置される。 
【０１９５】
データメッセージがSaaSプロバイダデータセンタ1620への経路上で仮想ネットワークを出るために出力ゲートウェイ1602に到達すると、各TMエンジン1605は、これらのデータメッセージの送信元ネットワークアドレス（例えば、送信元IPおよび／またはポートアドレス）を新しい送信元ネットワークアドレス（例えば、送信元IPおよび／またはポートアドレス）にマッピングし、NATエンジン1610は、新しい送信元ネットワークアドレスをさらに別の送信元ネットワークアドレス（例えば、別の送信元IPおよび／またはポートアドレス）にマッピングする。いくつかの実施形態では、TMエンジンはステートレス要素であり、動的データ構造を見ることなく、静的テーブルを介して各メッセージのマッピングを実行する。ステートレス要素として、TMエンジンは、データメッセージフローの後続のメッセージを処理するときに接続レコードを使用するために、データメッセージフローの最初のデータメッセージを処理するときに接続レコードを生成しない。 
【０１９６】
一方、いくつかの実施形態におけるNATエンジン1605は、以前のSNATマッピングを反映する接続レコードを保存する接続ストレージへの参照によってそのマッピングを実行するステートフル要素である。NATエンジンがデータメッセージを受信すると、いくつかの実施形態では、このエンジンは、最初に接続ストレージをチェックして、受信したメッセージのフローのために以前に接続レコードを生成したかどうかを判定する。その場合、NATエンジンはこのレコードに含まれるマッピングを使用してSNAT動作を実行する。それ以外の場合は、新しいデータメッセージフローの新しいアドレスマッピングを取得するために使用する基準のセットに基づいてSNAT動作を実行する。これを行うために、いくつかの実施形態では、NATエンジンは、共通のネットワークアドレス変換技術を使用する。
【０１９７】
いくつかの実施形態では、NATエンジンは、元のメッセージを送信したテナントマシンに応答データメッセージを転送するDNAT動作を実行するために、SaaSプロバイダマシンからの応答データメッセージを受信したときに、いくつかの実施形態の接続ストレージを使用することもできる。いくつかの実施形態では、処理された各データメッセージフローの接続レコードは、フローの識別子（例えば、変換された送信元ネットワークアドレスを有する5つのタプル識別子）を含むレコード識別子を有する。
【０１９８】
マッピングを実行する際、TMエンジンは、同じ送信元IPアドレスとポートアドレスを使用する異なるテナントからのデータメッセージフローが、重複しない一意のアドレス空間にマッピングされるようにする。各メッセージに対して、TMエンジンはテナントIDを識別し、この識別子に基づいてアドレスマッピングを実行する。いくつかの実施形態では、TMエンジンは、異なるテナントからの任意の2つのメッセージが同じIPアドレスにマッピングされないように、異なるテナントの送信元IPアドレスを異なるIP範囲にマッピングする。 
【０１９９】
したがって、異なるテナントIDを持つ各ネットワークタイプは、IPアドレス（0.0.0.0〜255.255.255.255）の完全な232の領域内の一意の宛先にマップされる。クラスAとBのネットワークは、クラスCのネットワークの256倍と16倍のIPアドレスを使用することができる。クラスA、B、およびCネットワークのサイズ比率を考慮すると、256のクラスAネットワークは、以下のように、（1）240のテナントをクラスAネットワークにマップするための240のクラスAネットワーク、（2）240のテナントをクラスBネットワークにマップするための15のクラスAネットワーク、および（3）240のテナントをクラスCネットワークにマップするための1つのクラスAネットワーク、に割り当てることができる。より具体的には、いくつかの実施形態において、最低範囲のAネットワーク（0．x．x/24から始まり、1．x．x/24、．．．、239．x．x/24まで）は、10．xクラスAネットワークから240の異なる対象クラスAネットワークに至るアドレスをマップするために使用される。次の15のクラスAネットワーク240．x．x．x/24から254．x．x．x/24は、それぞれ16のクラスBネットワーク（例えば、合計240のネットワーク（15＊16））を含めるように使用される。最後のクラスAネットワーク255．x．x．x/24は、最大256のプライベートクラスCネットワークを含めるように使用される。256のテナントを取り付けることができるが、240のみが使用され、16のクラスCネットワークは使用されない。要約すると、いくつかの実施形態は、以下のマッピングを使用する。
・10．x．x．x／24ネットワークは、1．x．x．x／24-239．x．x．x／24につき、テナントごとに240の異なるマッピングとなり、
・172．16-31．x．x／12ネットワークは、240．x．x．x／24-254．x．x．x／24につき、テナントごとに240の異なるマッピングとなり、
・192．168．x．x/16は、255．x．x．x/24ネットワークにつき、各テナントに対して256個のマッピングのうち240個の利用可能なマッピングとなる。
【０２００】
上述のスキームでは、テナントがどのネットワーククラスのタイプを使用するかは事前に不明であると想定して、最大240のテナントをサポートすることができる。いくつかの実施形態では、パブリッククラウドネットワークは、プライベートIPアドレスを使用する。このような場合、プライベートアドレス空間に再びマップしないことが望ましい。いくつかの実施形態では、クラスAネットワークおよびクラスBネットワークを除去するので、これらの実施形態でサポート可能なテナントは239個のみである。ユニークなマッピングを達成するために、いくつかの実施形態は、すべてのテナントIDを1から239まで番号付けし、次に、プライベートなドメインのうちのマスクされていない部分の最下位8ビットに、モジュロ240の（8ビットで表される）テナントIDを加える。この場合、クラスAアドレスの場合、最初のテナント（番号1）は11．xx．xx．xx/24に、最後のテナント（239）は9．xx．xx．xx/24にマップされる。 
【０２０１】
図16に示す実装では、いくつかの実施形態は、各TMエンジン1605に、任意の潜在的なテナントIDのサブネットと、そのような各サブネット内の任意の特定のIPアドレスにメッセージをルーティングする方法とを提供する。この情報は、テナント、ブランチ、およびモバイルデバイスが追加または削除されると、動的に変化し得る。したがって、この情報は、仮想ネットワークのインターネット出力ゲートウェイ内のTMエンジンに動的に配信される必要がある。仮想ネットワークプロバイダの出力インターネットゲートウェイが多数のテナントによって使用される可能性があるため、配信され定期的に更新される情報の量は大きくなる可能性がある。また、テナントIDの240（または239）という制限は、グローバルなものであり、出力ポイントに複数のIPアドレスを追加することによってのみ解決することができる。
【０２０２】
図17は、図16に示された単一NATアプローチの代わりに、いくつかの実施形態において使用されるダブルNATアプローチを示す。図17に示すアプローチは、ほとんどの（すべてではないが）TMエンジンに配布されるテナントデータをより少なくし、より多くのプライベートテナントネットワークを仮想ネットワークプロバイダの内部ネットワークにマップすることを可能にする。テナントマシンから仮想ネットワーク1700を通って、次にインターネット1625を通って別のマシン（例えば、SaaSプロバイダデータセンタ1620内のマシン）に通過するデータメッセージフローの場合、図17に示されているアプローチは、データメッセージフローの入力ゲートウェイ1770と、このフローが仮想ネットワークを出てインターネット1625に入る出力ゲートウェイ1702または1704とにNATエンジンを配置する。このアプローチはまた、入力ゲートウェイ1770のNATエンジン1712の前にTMエンジン1705を配置する。
【０２０３】
図17に示される例では、メッセージフローは、2つの支店1755および1760、および2つの仮想ネットワークテナントのデータセンタ1765から来て、同じ入力ゲートウェイ1770を介して仮想ネットワーク1700に入るが、必ずしもそうである必要はない。仮想ネットワーク1600と同様に、いくつかの実施形態における仮想ネットワーク1700は、複数のパブリッククラウドベンダの複数のパブリッククラウドデータセンタにわたって定義される。また、いくつかの実施形態では、仮想ネットワークゲートウェイ1702、1704、および1770は、管理転送ノードの一部であり、TMエンジンは、これらのMFN内のNATエンジン215の前に、これらの実施形態では配置される。 
【０２０４】
TMエンジン1605および1705は、図16および17において同様に動作する。TMエンジン1605と同様に、TMエンジン1705は、データメッセージがSaaSプロバイダデータセンタ1620に向けられる（すなわち、SaaSプロバイダデータセンタ1620の宛先IPアドレスを有する）場合、仮想ネットワークに入ってくるデータメッセージの送信元IPアドレスおよびポートアドレスを新しい送信元IPアドレスおよびポートアドレスにマップする。このようなデータメッセージごとに、TMエンジン1705は、テナントIDを識別し、この識別子に基づいてアドレスマッピングを実行する。 
【０２０５】
いくつかの実施形態におけるTMエンジン1605と同様に、TMエンジン1705はステートレス要素であり、動的データ構造を参照することなく、静的テーブルを介して各メッセージのマッピングを実行する。ステートレス要素として、TMエンジンは、データメッセージフローの後続のメッセージを処理するときに接続レコードを使用するために、データメッセージフローの最初のデータメッセージを処理するときに接続レコードを生成しない。
【０２０６】
そのマッピングを行う際に、入力ゲートウェイ1770内のTMエンジン1705は、同じ送信元IPおよびポートアドレスを使用する異なるテナントからのデータメッセージフローが、重複しない一意のアドレス空間にマッピングされることを保証する。いくつかの実施形態では、TMエンジンは、異なるテナントからの任意の2つのメッセージが同じIPアドレスにマッピングされないように、異なるテナントの送信元IPアドレスを異なるIP範囲にマッピングする。他の実施形態では、TMエンジン1705は、2つの異なるテナントの送信元IPアドレスを同じ送信元IPの範囲にマッピングするが、異なる送信元ポートの範囲にマッピングすることができる。さらに別の実施形態では、TMエンジンは、2つのテナントを異なる送信元IPの範囲にマッピングする一方で、他の2つのテナントを同じ送信元IPの範囲にマッピングしつつ、異なる送信元ポートの範囲にマッピングする。
【０２０７】
TMエンジン1605とは異なり、仮想ネットワーク入力ゲートウェイのTMエンジン1705は、入力ゲートウェイに接続されている支店、企業データセンタ、および企業コンピューティングノードのテナントを識別するだけでよい。これにより、各TMエンジンに最初に提供され、定期的に更新される必要があるテナントデータが大幅に削減される。また、以前と同様に、各TMエンジンは、一意のアドレス空間に239／240テナントのみをマッピングすることができる。ただし、TMエンジンは仮想ネットワークプロバイダの入力ゲートウェイに配置されるため、TMエンジンはそれぞれ239／240テナントを一意にマップすることができる。 
【０２０８】
いくつかの実施形態における入力ゲートウェイ1770のNATエンジン1712は、入力ゲートウェイ1770が存在するパブリッククラウド（例えば、AWS、GCPまたはAzure）に固有の外部パブリックIPアドレスまたは内部IPアドレスのいずれかを使用することができる。どちらの場合も、NATエンジン1712は、受信メッセージ（すなわち、仮想ネットワーク1700に入るメッセージ）の送信元ネットワークアドレスを、その入力ゲートウェイのプライベートクラウドネットワーク内でユニークなIPアドレスにマップする。いくつかの実施形態では、NATエンジン1712は、各テナントのデータメッセージフローの送信元IPアドレスを異なる一意のIPアドレスに変換する。しかしながら、他の実施形態では、NATエンジン1712は、異なるテナントのデータメッセージフローの送信元IPアドレスを同じIPアドレスに変換するが、異なるテナントのデータメッセージフローを区別するために送信元ポートアドレスを使用する。さらに別の実施形態では、NATエンジンは、2つのテナントの送信元IPアドレスを異なる送信元IPの範囲にマッピングし、一方、2つの他のテナントの送信元IPアドレスを同じ送信元IPの範囲にマッピングするが、送信元ポートの範囲は異なるようにする。
【０２０９】
いくつかの実施形態では、NATエンジン1712は、以前のSNATマッピングを反映する接続レコードを保存する接続ストレージへの参照によってマッピングを実行するステートフル要素である。いくつかの実施形態では、NATエンジンは、元のメッセージを送信したテナントマシンに応答データメッセージを転送するDNAT動作を実行するために、SaaSプロバイダマシンからの応答データメッセージを受信したときに、いくつかの実施形態の接続ストレージを使用することもできる。TMおよびNATエンジン1705、1710および1712は、いくつかの実施形態において、コントローラクラスタ160によって構成される（例えば、異なるテナントおよびネットワークアドレス空間の異なる範囲のために使用するマッピングを記述するためのテーブルが提供される）。
【０２１０】
図18は、入力NATエンジン1712の送信元ポート変換を説明する例を示している。具体的には、入力ゲートウェイ1770を介して仮想ネットワーク1700に入り、出力ゲートウェイ1702で仮想ネットワークを出るときに、テナンシーマッピングエンジン1705および入力NATエンジン1712がデータメッセージ1800上で実行する送信元アドレスマッピングを示す。図示されるように、テナントゲートウェイ1810は、データメッセージ1800を送信し、これは、送信元IPアドレス10．1．1．13および送信元ポートアドレス4432をもつIPsecゲートウェイ1805に到着する。いくつかの実施形態では、これらの送信元アドレスは、テナントマシンによって使用されるアドレスであり（図示せず）、他の実施形態では、これらの送信元アドレスの一方または両方は、テナントゲートウェイによって実行される送信元NAT動作またはテナントデータセンタ内の別のネットワーク要素によって生成される送信元アドレスである。 
【０２１１】
このメッセージがIPsecゲートウェイ1805によって処理された後、このゲートウェイまたは入力MFNの別のモジュールは、このメッセージを15であるテナントIDに関連付け、これはメッセージ1800が属する仮想ネットワークテナントを識別する。このテナントIDに基づいて、テナントマッピングエンジン1705は、次に、図に示すように、送信元IPおよびポートアドレスを15．1．1．13および253の送信元IPおよびポート宛先にマッピングする。この送信元IPアドレスとポートアドレスは、データメッセージ1800のメッセージフローを一意に識別する。いくつかの実施形態では、TMエンジン1705は、このマッピングをステートレスな方法で（すなわち、接続追跡レコードを参照せずに）実行する。他の実施形態では、TMエンジンは、ステートフルな方法でこのマッピングを実行する。
【０２１２】
次に、入力NATエンジン1712は、（1）データメッセージ1800の送信元IPアドレスを198．15．4．33であるユニークなプライベートまたはパブリック（内部または外部) IPアドレスに変換し、（2）このメッセージの送信元ポート宛先をポート宛先714に変換する。いくつかの実施形態において、仮想ネットワークは、同一または異なるテナントの他のデータメッセージフローのために、このIPアドレスを使用する。したがって、これらの実施形態では、NATエンジン1712の送信元ネットワークアドレス変換（SNAT）動作は、送信元ポートアドレスを使用して、仮想ネットワーク内で同じIPアドレスを使用する異なるテナントの異なるメッセージフローを区別する。
【０２１３】
いくつかの実施形態では、入力NATエンジンのSNAT動作によって割り当てられた送信元ポートアドレスは、仮想ネットワーク1700の外部の異なるメッセージフローを区別するために使用される送信元ポートアドレスでもある。これは、図18に示されている例の場合である。この例の出力NATエンジン1710は、SNAT動作を実行するときに、データメッセージの送信元ポートアドレスを変更しない。代わりに、送信元IPアドレスを外部IPアドレス198．15．7．125に変更する。これは、いくつかの実施形態では、仮想ネットワークの出力ゲートウェイのパブリックIPアドレスである。いくつかの実施形態におけるこのパブリックIPアドレスは、パブリッククラウドデータセンタのIPアドレスでもあり、そこでは入出力ゲートウェイ1770および1702が動作する。
【０２１４】
送信元IPアドレスおよびポートアドレスである198．15．7．125および714を使用して、データメッセージはインターネットを介してルーティングされ、SaaSプロバイダのデータセンタのゲートウェイ1815に到達する。このデータセンタでは、SaaSプロバイダマシンは、このメッセージに基づいて動作を実行し、応答メッセージ1900を送り返す。その処理は、図19を参照して後述する。いくつかの実施形態では、SaaSプロバイダマシンは、送信元IPアドレス198．15．7．125および714を参照することによって定義される1つ以上のサービスルールに基づいて、データメッセージに対して1つ以上のサービス動作（例えば、ファイアウォール動作、IDS動作、IPS動作などのミドルボックスサービス動作）を実行する。これらの実施形態のいくつかにおいて、異なるテナントの異なるサービスルールは、これらのルール識別子で異なる送信元ポートアドレスを指定しながら、ルール識別子で同じ送信元IPアドレス（例えば198．15．7．125）を指定することができる。ルール識別子は、データメッセージに一致するルールを識別するルックアップ動作の実行中に、データメッセージフロー属性と比較するための属性のセットを指定する。
【０２１５】
図19は、SaaSマシン（図示せず）がデータメッセージ1800の処理に応答して送信する応答メッセージ1900の処理を示す。いくつかの実施形態では、応答メッセージ1900は、元のデータメッセージ1800と同一であってもよく、元のデータメッセージ1800の修正バージョンであってもよく、あるいは完全に新しいデータメッセージであってもよい。図示されるように、SaaSゲートウェイ1815は、宛先IPアドレスおよびポートアドレス198．15．7．125および714に基づいてメッセージ1900を送信する。これらのアドレスは、このメッセージがSaaSゲートウェイ1815に到着したときのデータメッセージ1800の送信元IPおよびポートアドレスである。
【０２１６】
メッセージ1900は、仮想ネットワークのゲートウェイ（図示せず）で受信され、このゲートウェイは、メッセージ1800がSaaSプロバイダに送信される前に、メッセージ1800に対する最後のSNAT動作を実行したNATエンジン1710に、データメッセージを提供する。図19に示す例では、データメッセージ1900は、最後のSNAT動作を実行したのと同じNATエンジン1710で受信されるが、これは、それぞれのデプロイにおいて該当する必要はない。
【０２１７】
NATエンジン1710（現在入力NATエンジンとして機能している）は、データメッセージ1900上でDNAT(宛先NAT）動作を実行する。この動作は、パブリッククラウドルーティングファブリックおよび仮想ネットワークコンポーネント間を介してデータメッセージ1900を転送するために、外部宛先IPアドレス198．15．7．125を、仮想ネットワークによって使用される宛先IPアドレス198．15．4．33に変更する。繰り返しになるが、IPアドレス198．15．4．33は、いくつかの実施形態において、パブリックまたはプライベートIPアドレスであり得る。
【０２１８】
図示されるように、NATエンジン1712（現在は出力NATエンジンとして機能している）は、NATエンジン1710が宛先IPアドレスを変換した後、メッセージ1900を受信する。次に、NATエンジン1712は、宛先IPおよびポートアドレスを15．1．1．13および253に置き換える、第2のDNAT動作をこのメッセージ1900に対して実行する。これらのアドレスは、TMエンジン1705によって認識されるアドレスである。TMエンジン1705は、これらのアドレスを10．1．1．13および4432の宛先IPおよびポートアドレスに置き換え、データメッセージ1900をテナントID15に関連付け、メッセージ1900をこのテナントIDと共にテナントゲートウェイ1810に転送するためのIPsecゲートウェイ1805に提供する。 
【０２１９】
いくつかの実施形態では、仮想ネットワークプロバイダは、上記のプロセス、システム、およびコンポーネントを使用して、同一または異なるパブリッククラウドプロバイダの複数のパブリッククラウド上で、複数の異なるテナント（たとえば、複数の企業の複数の異なる企業WAN）に複数の仮想WANを提供する。図20は、1つ以上のパブリッククラウドプロバイダの第Nのパブリッククラウド2005で、ネットワーク基盤およびコントローラクラスタ2010を持つ仮想ネットワークプロバイダの第Mのテナントの第Mの仮想企業WAN2015の例を示している。 
【０２２０】
各テナントの仮想WAN2015は、第Nのパブリッククラウド2005の全て又はこれらのパブリッククラウドのサブセットにまたがることができる。各テナントの仮想WAN2015は、1つ以上の支店2020、データセンタ2025、SaaSプロバイダデータセンタ2030、およびテナントのリモートデバイスを接続する。いくつかの実施形態では、各テナントの仮想WANは、VNPのコントローラクラスタがテナントの異なるコンピューティングノード2020から2035の間でデータメッセージを効率的に転送するために必要であるとみなすパブリッククラウド2005にまたがる。パブリッククラウドの選択において、いくつかの実施形態におけるコントローラクラスタは、テナントが選択するパブリッククラウド、および／またはテナントまたはテナントの少なくとも1つのSaaSプロバイダが1つ以上のマシンを持つパブリッククラウドも考慮する。
【０２２１】
各テナントの仮想WAN2015は、テナントのリモートデバイス2035（例えば、モバイルデバイスまたはリモートコンピュータ）が、SaaSプロバイダサービスにアクセスするために（すなわち、SaaSプロバイダマシンまたはマシンクラスタにアクセスするために）、任意の支店またはテナントデータセンタのテナントのWANゲートウェイとのやり取りを回避することを可能にする。いくつかの実施形態におけるテナントの仮想WANは、これらのWANゲートウェイ（例えば、WANセキュリティゲートウェイ）の機能を仮想WANがまたがるパブリッククラウド内の１つ以上のマシンに移動することによって、リモートデバイスが支店およびテナントデータセンタのWANゲートウェイを回避することを可能にする。 
【０２２２】
たとえば、リモートデバイスがテナントまたはそのSaaSプロバイダサービスのコンピューティングリソースにアクセスできるようにするには、いくつかの実施形態のWANゲートウェイが、リモートデバイスがテナントのコンピュータリソースまたはそのSaaSプロバイダサービスにアクセスする方法を制御するファイアウォールルールを適用する必要がある。テナントのブランチまたはデータセンタWANゲートウェイを回避するために、テナントのファイアウォールエンジン210は、テナントの仮想WANがまたがる１つ以上のパブリッククラウドの仮想ネットワークMFNに配置される。 
【０２２３】
これらのMFN内のファイアウォールエンジン210は、リモートデバイスとの間のデータメッセージフローに対してファイアウォールサービス動作を実行する。1つ以上のパブリッククラウドにデプロイされた仮想ネットワークでこれらの動作を実行することで、テナントのリモートデバイスに関連付けられたデータメッセージトラフィックが、ファイアウォールルール処理を受けるためにテナントのデータセンタまたは支店を介して不必要にルーティングされる必要がなくなる。これにより、テナントデータセンタおよび支店でのトラフィックの輻輳が緩和され、これらのロケーションでコンピューティングリソースに送信されないトラフィックを処理するために、これらのロケーションでコストの高い受信／送信ネットワーク帯域幅を消費することが回避される。また、このアプローチは、データメッセージフローが宛先（例えば、入力MFN、出力MFN、または中間ホップMFN）を通過するときに、介在するファイアウォールルール処理が仮想ネットワーク内で発生することを可能にするため、リモートデバイスとの間でのデータメッセージトラフィックの転送を高速化するのにも役立つ。
【０２２４】
いくつかの実施形態では、MFNのファイアウォールを実施するエンジン210（例えば、ファイアウォールサービスVM）は、VNP中央コントローラ160からファイアウォールルールを受信する。いくつかの実施形態におけるファイアウォールルールは、ルール識別子およびアクションを含む。いくつかの実施形態におけるルール識別子は、ファイアウォールルールがデータメッセージに一致するかどうかを判定するために、レイヤ2属性（例えば、MACアドレス）、レイヤ3属性（例えば、5つのタプル識別子など）、テナントID、ロケーションID(例えば、オフィスロケーションID、データセンタID、リモートユーザIDなど）などのデータメッセージ属性と比較される1つ以上の一致用の値(match value)を含む。 
【０２２５】
ファイアウォールルールのいくつかの実施形態におけるアクションは、ファイアーウォールルールがデータメッセージの属性と一致する場合に、ファイアウォール実施エンジン210がデータメッセージに対して取るべきアクション（例えば、許可、ドロップ、再ダイレクトなど）を特定している。複数のファイアウォールルールがデータメッセージと一致する可能性に対処するために、ファイアウォール実施エンジン210は、あるファイアウォールルールが別のファイアウォールルールよりも高い優先順位を持つことができるように、ファイアウォールルールデータストレージにファイアウォールルール（コントローラクラスタ160から受信する）を階層的に保存する。データメッセージが2つのファイアウォールルールに一致する場合、ファイアウォール実施エンジンは、いくつかの実施形態において、より高い優先度をもつルールを適用する。他の実施形態では、ファイアウォール実施エンジンは、その階層に従ってファイアウォールルールを検査し（すなわち、より高い優先順位のルールをより低い優先順位のルールの前に検査する）、別のより低い優先順位のルールがデータメッセージと一致する場合に、それが最初により高い優先順位のルールと一致することを確実にする。
【０２２６】
いくつかの実施形態では、コントローラクラスタは、データメッセージが仮想ネットワークに入るときに入力ノード（例えば、ノード850）において、仮想ネットワーク上の中間ノード（例えば、ノード857）において、または仮想ネットワークを出るときに出力ノード（例えば、ノード855）において、ファイアウォールサービスがデータメッセージを検査するようにMFNコンポーネントを構成することができる。これらのノードのそれぞれにおいて、いくつかの実施形態におけるCFE(例えば、832、856、または858）は、その関連するファイアウォールサービスエンジン210を呼び出して、CFEが受信するデータメッセージ上でファイアウォールサービス動作を実行する。いくつかの実施形態では、ファイアウォールサービスエンジンは、このモジュールがデータメッセージに対してファイアウォールのアクションを実行することができるように、ファイアウォールサービスエンジンがそれを呼び出したモジュール（例えば、CFE）にその決定を返すのに対し、他の実施形態では、ファイアウォールサービスエンジンが、データメッセージに対してそのファイアウォールのアクションを実行することができるようにする。
【０２２７】
いくつかの実施形態において、他のMFNコンポーネントは、ファイアウォールサービスエンジンにその動作を実行させるよう指示する。例えば、いくつかの実施形態におけるVPNゲートウェイ（例えば、225または230）は、データメッセージが入力ノードのCFEに渡されるべきかどうかを判定するため、関連するファイアウォールサービスエンジンにその動作を実行するように指示する。また、いくつかの実施形態のCFEは、データメッセージをその関連するファイアウォールサービスエンジンに渡し、それは、データメッセージを通過させることを決定した場合、外部ネットワーク（例えば、インターネット）を介してその宛先にデータメッセージを渡すか、または、外部ネットワークを介してその宛先にデータメッセージを渡す前に、そのデータメッセージをその関連するNATエンジン215に渡してそのNAT動作を実行する。
【０２２８】
いくつかの実施形態の仮想ネットワークプロバイダは、パブリッククラウドで定義されているテナントのWANセキュリティゲートウェイが、ファイアウォールサービスに加えて、またはファイアウォールサービスの代わりに、他のセキュリティサービスを実装することを可能にする。たとえば、テナントの分散型WANセキュリティゲートウェイ（いくつかの実施形態では、テナントの仮想ネットワークがまたがる各パブリッククラウドデータセンタに分散される）には、ファイアウォールサービスエンジンだけでなく、侵入検知エンジンや侵入防御エンジンも含まれる。いくつかの実施形態では、侵入検知エンジンおよび侵入防御エンジンは、MFN150にアーキテクチャ的に組み込まれ、ファイアウォールサービスエンジン210と同様の位置を占める。
【０２２９】
いくつかの実施形態におけるこれらのエンジンの各々は、中央コントローラクラスタ160によって配信される侵入検知／防御ポリシーを格納する1つ以上のストレージを含む。いくつかの実施形態では、これらのポリシーは、テナントの仮想ネットワーク（複数のパブリッククラウドデータセンタにデプロイされる）への不正な侵入を検出／防止し、検出された侵入イベント（ログの生成、通知の送信、サービスまたはマシンのシャットダウンなど）に応じてアクションを実行するようにエンジンを構成する。ファイアウォールルールと同様に、侵入検知／防御ポリシーは、仮想ネットワークが定義されている、それぞれの管理転送ノード（たとえば、入力MFN、中間MFN、および／またはデータメッセージフローの出力MFN）で実施することができる。
【０２３０】
前述のように、仮想ネットワークプロバイダは、仮想WANがまたがる各パブリッククラウドに少なくとも１つのMFNをデプロイして、テナントのメッセージフローが仮想WANに出入りできるようにMFN間の経路を定義するようにデプロイされたMFNを構成する。また、上述したように、各MFNは、いくつかの実施形態では異なるテナントによって共有されることができ、他の実施形態では、各MFNは、ただ1つの特定のテナントのためにデプロイされる。 
【０２３１】
いくつかの実施形態では、各テナントの仮想WANは、オーバレイトンネルを介してそのWANによって使用されるMFNを接続することによって確立されるセキュアな仮想WANである。いくつかの実施形態におけるこのオーバレイトンネルアプローチは、各テナントのデータメッセージフローを、各テナントに固有のトンネルヘッダでカプセル化する。例えば、テナントを一意に識別するテナント識別子を含む。テナントの場合、いくつかの実施形態では、仮想ネットワークプロバイダのCFEは、テナントの仮想WANに出入りするための入力／出力転送要素を識別するために1つのトンネルヘッダを使用し、仮想ネットワークの介在する転送要素を通過するために別のトンネルヘッダを使用する。仮想WANのCFEは、他の実施形態において、異なるオーバレイカプセル化機構を使用する。
【０２３２】
1つ以上のパブリッククラウド上にテナントの仮想WANをデプロイするために、VNPのコントローラクラスタは、（1）テナントの会社のコンピューティングノード（支店、データセンタ、モバイルユーザ、SaaSプロバイダなど）のロケーションに基づいて、テナントが利用可能なエッジMFN(異なるデータメッセージフローの入力または出力MFNとして機能できる）を識別し、（2）利用可能なすべてのエッジMFN間の経路を識別する。これらの経路が識別されると、CFEの転送テーブルに伝播される（たとえば、OpenFlowを使用して、異なるOVSベースの仮想ネットワークルータに伝播される）。具体的には、テナントの仮想WANを通過する最適な経路を識別するために、このWANに関連付けられたMFNは、それらと隣接するMFNとの間のネットワーク接続の品質を定量化する測定値を生成し、その測定値をVNPのコントローラクラスタに定期的に提供する。 
【０２３３】
前述のように、コントローラクラスタは、異なるMFNからの測定値を集約し、これらの測定値に基づいてルーティンググラフを生成し、テナントの仮想WANを通る経路を定義し、これらの経路をMFNのCFEの転送要素に配信する。テナントの仮想WANの定義済み経路を動的に更新するために、このWANに関連付けられているMFNは、定期的に測定値を生成し、これらの測定値をコントローラクラスタに提供する。コントローラクラスタは、受信した更新された測定値に基づいて、測定集計、経路グラフ生成、経路識別、および経路配信を定期的に繰り返す。
【０２３４】
テナントの仮想WANを経由する経路を定義する場合、VNPのコントローラクラスタは、必要なエンドツーエンドのパフォーマンス、信頼性、およびセキュリティのために経路を最適化し、テナントのメッセージフローのルーティングを最小限に抑えようとする。また、コントローラクラスタは、ネットワークを通過するデータメッセージフローのレイヤ4処理を最適化するように、MFNコンポーネントを構成する（たとえば、接続パス全体でレート制御機構を分割することによってTCP接続のエンドツーエンドレートを最適化する）。
【０２３５】
パブリッククラウドの普及により、企業の各支店に近い主要なパブリッククラウドデータセンタを見つけることが非常に容易になった。同様に、SaaSベンダは、パブリッククラウド内、または、パブリッククラウドデータセンタの近くに同様に配置されるアプリケーションのホスティングを増加させている。したがって、仮想企業WAN2015は、パブリッククラウド2005を、企業のコンピューティングノード（例えば、支店、データセンタ、リモートデバイス、SaaSプロバイダ）の近傍に存在する企業ネットワーク基盤として安全に使用する。
【０２３６】
企業WANでは、ビジネスクリティカルなアプリケーションを常に許容可能なパフォーマンスで提供するために、帯域幅の保証が必要である。このようなアプリケーションは、例えば、ERP、財務または調達、期限指向アプリケーション（例えば、工業またはIoT制御）、リアルタイムアプリケーション（例えば、VoIPまたはビデオ会議）のような、対話型データアプリケーションであり得る。したがって、従来のWAN基盤（フレームリレーやMPLSなど）は、このような保証を提供する。 
【０２３７】
マルチテナントネットワークで帯域幅保証を提供する際の主な障害は、特定の顧客のために1つ以上のパスで帯域幅を確保する必要があることである。いくつかの実施形態では、VNPはQoSサービスを提供し、入力認定レート(Ingress Committed Rate、ICR)保証および出力認定レート(Egress Committed Rate、ECR)保証を提供する。ICRは仮想ネットワークに入るトラフィックレートを表し、ECRは仮想ネットワークからテナントサイトに出るトラフィックレートを表す。 
【０２３８】
トラフィックがICRおよびECRの制限を超えない限り、いくつかの実施形態における仮想ネットワークは、帯域幅および遅延の保証を提供する。たとえば、HTTPの入力または出力トラフィックが1Mbpsを超えない限り、帯域幅と低遅延が保証される。これは、ポイント・ツー・クラウドモデルであり、なぜなら、QoSの目的のためには、VNPは、その宛先がICR／ECRの境界内にある限り、トラフィックの宛先を追跡する必要がないためである。このモデルは、ホースモデルと呼ばれることもある。
【０２３９】
より厳格なアプリケーションでは、顧客がポイント・ツー・ポイント保証を希望する場合、非常に重要なトラフィックを配信するために仮想データパイプを構築する必要がある。たとえば、エンタープライズでは、サービスレベルアグリーメントの保証が高い2つのハブサイトまたはデータセンタが必要になる場合がある。そのため、VNPルーティングでは、各顧客の帯域幅制約を満たすルーティングパスが自動的に選択される。これは、ポイント・ツー・ポイントモデルまたはパイプモデルと呼ばれる。
【０２４０】
エンドユーザに保証された帯域幅を提供するVNPの主な利点は、変化する帯域幅要求に応じてVNP基盤を調整することが可能なことである。ほとんどのパブリッククラウドでは、同じクラウドの異なる領域に配置された2つのインスタンス間の最低帯域幅保証が提供される。現在のネットワークに、新しい要求に対して、保証された帯域幅を提供するのに十分な未使用キャパシティがない場合、VNPはそのファシリティに新しいリソースを追加する。たとえば、VNPは高需要領域に新しいCFEを追加することができる。
【０２４１】
1つの課題は、経路を計画し、基盤をスケールアップおよびスケールダウンする際に、この新しい次元のパフォーマンスとコストを最適化することである。アルゴリズムおよび帯域幅アカウンティングを容易にするために、いくつかの実施形態は、エンド・ツー・エンドの帯域幅確保が分割されないことを想定する。他の方法として、ある特定の帯域幅（例えば、10Mbps）が、特定のテナントのブランチAとブランチBの間に確保されている場合、帯域幅は、ブランチAが接続する入力CFEから始まる単一のパス上に割り当てられ、次に、ブランチBに接続されている出力CFEに到達するために、ゼロ以上の中間CFEのセットを通過する。また、いくつかの実施形態は、帯域幅の保証されるパスは単一のパブリッククラウドを通過するだけであると想定する。
【０２４２】
ネットワークトポロジ上で交差する様々な帯域幅の確保を考慮するために、いくつかの実施形態では、VNPは、確保された帯域幅のパス上のルーティングを静的に定義し、データメッセージフローが、帯域幅要件のために、確保された同じ経路を常に通過するようにする。いくつかの実施形態では、各経路は、その経路によって通過する各CFEが、この経路に関連付けられた単一の発信インタフェースと一致する単一のタグで識別される。具体的には、各CFEは、ヘッダにこのタグがあり、特定の着信インタフェースから到着する各データメッセージに対して、単一の発信インタフェースを照合する。
【０２４３】
いくつかの実施形態では、コントローラクラスタは、いくつかの相互接続されたノードによって形成されるネットワークグラフを維持する。グラフの各ノードnには、このノードに割り当てられた保証帯域幅の合計（TBWn）と、このノードによってすでに確保（特定の予約パスに割り当て）されている帯域幅の合計（RBWn）がある。さらに、各ノードについて、グラフは、ギガバイトあたりのコスト（Cij）と、このノードとグラフ内の他のすべてのノードとの間の送信トラフィックに関連するミリ秒単位の遅延（Dij）とを含む。ノードiとノードjの間の送信トラフィックに関連する重みはWij＝a＊Cij＋Dijであり、ここでaは、典型的には1から10の間のシステムパラメータである。 
【０２４４】
ブランチAとブランチBの間の値BWの帯域幅確保の要求が受け入れられると、コントローラクラスタは、まず、ブランチAとブランチBにそれぞれバインドされている特定の入力および出力ルータnとmに要求をマッピングする。次に、コントローラクラスタは、nとmの間の2つの最低コスト（例えば、最短経路）を計算するルーティングプロセスを実行する。最初の経路は、計算された経路に沿った利用可能な帯域幅に関係なく、nとmの間の最低コスト（例えば最短経路）経路である。この経路の全重みは、W1として計算される。 
【０２４５】
第2の最低コスト（例えば、最短経路）計算は、最初にBW ＞ TBWi - RBWiの全てのノードiを排除することによってグラフを修正する。修正されたグラフは、トリミング済グラフと呼ばれる。次に、コントローラクラスタは、トリミング済みのグラフ上で第２の最低コスト（例えば、最短経路）経路計算を実行する。第２の経路の重みがK％以下（Kは通常、第１の経路よりも10％〜30％高い）の場合、第２の経路が優先パスとして選択される。一方、この要件を満たさない場合、コントローラクラスタは、第１の経路に、TBWiRBWiの値が最も小さいノードiを追加し、次に、2つの最低コスト（例えば、最短経路）計算を繰り返す。コントローラクラスタは、条件が満たされるまで、さらにルータを追加し続ける。その時点で、確保された帯域幅BWがすべてのRBWiに追加され、ここでiは選択された経路上のルータである。
【０２４６】
すでに帯域幅が確保されている経路の追加帯域幅を要求する特別な場合、コントローラクラスタは、まずノードAとBの間の現在の帯域幅確保を削除し、これらのノード間の合計帯域幅要求のパスを計算する。これを行うために、いくつかの実施形態では、各ノードのために保持される情報は、各タグ、または各送信元および宛先ブランチのために確保された帯域幅も含み、確保された帯域幅全体だけではない。帯域幅確保がネットワークに追加された後に、仮想ネットワーク経由の測定されたネットワーク遅延またはコストに大きな変化がない限り、いくつかの実施形態は、経路を再考しない。しかしながら、測定および／またはコストが変更した場合、これらの実施形態は、帯域幅予約および経路計算処理を繰り返す。
【０２４７】
図21は、仮想ネットワークプロバイダのコントローラクラスタ160によって実行され、特定のテナントのために仮想WANをデプロイし管理するプロセス2100を概念的に示している。いくつかの実施形態では、プロセス2100は、コントローラクラスタ160上で実行されるいくつかの異なるコントローラプログラムによって実行される。このプロセスの動作は、図21に示すシーケンスに従う必要はない。なぜなら、これらの動作は、異なるプログラムによって並列または異なるシーケンスで実行することができるからである。したがって、これらの動作は、コントローラクラスタによって実行される動作の1つの例示的なシーケンスを説明するためだけに、この図に示されている。
【０２４８】
図示されているように、コントローラクラスタは、最初に、いくつかの異なるパブリッククラウドプロバイダ(Amazon AWS、Google GCP など）の複数のパブリッククラウドデータセンタに（2105において）複数のMFNをデプロイする。いくつかの実施形態におけるコントローラクラスタは、プロセス2100が示されている特定のテナントとは異なる1つ以上の他のテナントに対して、これらのデプロイされたMFNを（2105において）構成する。
【０２４９】
2110において、コントローラクラスタは、特定のテナントの外部マシン属性およびロケーションに関する特定のテナントデータを受信する。いくつかの実施形態では、このデータは、特定のテナントによって使用されるプライベートサブネットと、特定のテナントが外部マシンを有する1つ以上のテナントオフィスおよびデータセンタの識別子とを含む。いくつかの実施形態では、コントローラクラスタは、APIを介して、またはコントローラクラスタが提供するユーザインタフェースを介してテナントデータを受信することができる。
【０２５０】
次に、2115において、コントローラクラスタは、特定のテナントのための仮想ネットワークを確立するために使用する候補MFNであるMFN150の測定エージェント205によって収集された測定値から、特定のテナントのためのルーティンググラフを生成する。上述のように、ルーティンググラフは、MFNを表すノードと、MFN間のネットワーク接続を表すノード間のリンクを有する。リンクには、関連付けられた重みがある。これは、リンクによって表されるネットワーク接続を用いる際の品質やコストを定量化するコスト値である。前述のように、コントローラクラスタは、まず、収集された測定値から測定グラフを生成し、次に、最適でない（例えば、大きな遅延またはドロップ率を有する）測定グラフからリンクを除去することによって、ルーティンググラフを生成する。
【０２５１】
ルーティンググラフを構築した後、コントローラクラスタは（2120で）パス検索を実行して、テナントの外部マシンが（MFNによって配置される）仮想ネットワークにデータメッセージを送信し、そして仮想ネットワークからデータメッセージを受信するために使用することができる、入出力ノード（つまり、MFN）の候補の異なるペア間の利用可能な経路を識別する。いくつかの実施形態では、コントローラクラスタは、既知のパス探索アルゴリズムを使用して、各候補ノードの入出力ペア間の異なるパスを識別する。このようなペアの各パスは、入力ノードから出力ノードへ、ゼロ個以上の中間ノードを介して連結されたときに通過する、1つ以上のリンクを使用する。
【０２５２】
いくつかの実施形態では、任意の2つのMFN間のコストは、2つのMFN間の接続リンクのための推定遅延と金銭的コストの加重和を含む。待ち時間と金銭的コストは、いくつかの実施形態において、（1）リンク遅延測定、（2）推定メッセージ処理待ち時間、（3）同一パブリッククラウドプロバイダの別のデータセンタからパブリッククラウドプロバイダの別のデータセンタへ、またはパブリッククラウドプロバイダのクラウド（例えば、別のパブリッククラウドプロバイダの別のパブリッククラウドデータセンタへ、またはインターネットへ）を出るために、特定のデータセンタからの発信トラフィックに対するクラウド料金、および（4）パブリッククラウド内のホストコンピュータ上で実行されるMFNに関連する推定メッセージ処理コストのうちの1つ以上を含む。 
【０２５３】
いくつかの実施形態は、可能な限りこのような横断を最小化するために、公衆インターネットを通過する2つのMFN間の接続リンクのペナルティを評価する。また、いくつかの実施形態は、そのような接続を使用するために経路生成をバイアスするために、2つのデータセンタ間のプライベートネットワーク接続の使用を促進する（例えば、接続リンクコストを削減することによって）。これらのペアワイズリンクの計算コストを使用して、コントローラクラスタは、ルーティングパスによって使用される個々のペアワイズリンクのコストを集計することによって、これらのペアワイズリンクのうちの1つ以上を使用する各ルーティングパスのコストを計算することができる。 
【０２５４】
次に、コントローラクラスタは、ノードの各候補の入出力ペア間の識別された候補パスの計算されたコスト（例えば、最低の集約コスト）に基づいて、1つまたは最大N個の識別されたパス（ここで、Nは、1より大きい整数）を（2120において）選択する。いくつかの実施形態では、各パスについて計算されたコストは、上述のように、パスによって使用される各リンクの重みコストに基づく（例えば、各リンクの関連する重み値の合計である）。コントローラクラスタは、2つのMFN間で複数の経路が必要な場合に、入力MFNまたは中間MFNがマルチパス動作を実行できるように、入力／出力ノードのペア間で複数のパスを選択することができる。
【０２５５】
（2120で）入力／出力ノードの候補ペアごとに1つまたはN個のパスを選択した後、コントローラクラスタは選択されたパスに基づいて1つまたはN個の経路を定義し、特定のテナントの仮想ネットワークを実装するMFNの経路テーブルまたは経路テーブルの一部を生成する。生成された経路レコードは、特定のテナントの異なるサブネットに到達するエッジMFNを識別し、入力MFNから出力MFNへの経路を通過するための次ホップMFNを識別する。
【０２５６】
2125において、コントローラクラスタは、特定のテナントのための仮想ネットワークを実装するように、これらのMFNの転送要素235を構成するために、経路レコードをMFNに配信する。いくつかの実施形態では、コントローラクラスタは、ソフトウェアで定義されるマルチテナントデータセンタで現在使用されている通信プロトコルを使用して転送要素と通信し、ホストコンピュータ上で実行されるソフトウェアルータを設定して、ホストコンピュータにまたがる論理ネットワークを実装することにより、経路レコードを通過させる。
【０２５７】
MFNが設定され、仮想ネットワークが特定のテナントに対して動作するようになると、エッジMFNはテナントの外部マシン（つまり、仮想ネットワーク外のマシン）からデータメッセージを受信し、これらのデータメッセージを仮想ネットワーク内のエッジMFNに転送する。このエッジMFNは、テナントの他の外部マシンにデータメッセージを転送する。このような転送動作を実行している間、入力MFN、中間MFN、および出力MFNは、その転送動作に関する統計を収集する。また、いくつかの実施形態では、いくつかの実施形態では、各MFN上の1つ以上のモジュールが、パブリッククラウドデータセンタにおけるネットワークまたはコンピューティング消費に関する他の統計を収集する。いくつかの実施形態では、パブリッククラウドプロバイダは、そのような消費データを収集し、収集されたデータを仮想ネットワークプロバイダに渡す。
【０２５８】
課金サイクルに近づくと、コントローラクラスタは、MFNによって収集された（例えば、2130において）統計、および／またはMFNによって収集された、またはパブリッククラウドプロバイダによって提供されたネットワーク／コンピューティング消費データを収集する。収集された統計、および／または提供されたネットワーク／コンピューティング消費データに基づいて、コントローラクラスタは（2130で）請求レポートを生成し、特定のテナントに請求レポートを送信する。 
【０２５９】
前述のように、請求レポートで請求される金額は、コントローラクラスタが受信する統計およびネットワーク／消費データ（たとえば、2130）を示す。また、いくつかの実施形態では、この請求は、仮想ネットワークプロバイダが（特定のテナントのために仮想ネットワークを実装する）MFNを運用するために費やしたコストと、収益率（例えば、10％の増加）を加算したコストを考慮している。特定のテナントは、テナントの仮想ネットワークがデプロイされている複数の異なるパブリッククラウドプロバイダからの請求を処理する必要がないため、この課金スキームは特定のテナントにとって便利である。いくつかの実施形態におけるVNPの発生費用には、パブリッククラウドプロバイダがVNPに請求する費用が含まれる。2130において、コントローラクラスタはまた、クレジットカードを請求するか、または請求書に反映される料金のために銀行口座から電子的に資金を引き出す。
【０２６０】
2135において、コントローラクラスタは、測定エージェント205から新しい測定値を受信したか否かを判定する。そうでない場合、プロセスは2145に遷移する。これについては後述する。一方、コントローラクラスタは、測定エージェントから新しい測定値を受信したと判定した場合、新しい測定値に基づいて、特定のテナントのルーティンググラフを再検査する必要があるかどうかを（2140で）判定する。MFNの障害がない場合、いくつかの実施形態のコントローラクラスタは、受信され、更新された測定値に基づいて、特定の期間（例えば、24時間毎または週毎）に、各テナントのルーティンググラフを最大で1回更新する。
【０２６１】
コントローラクラスタが、受信した新しい測定に基づいてルーティンググラフを再検査する必要があると判定した場合（2140で）、プロセスは、新たに受信した測定に基づいて新しい測定グラフを（2145において）生成する。いくつかの実施形態では、新しい測定セットが受信されるたびに、測定グラフのリンクに関連する測定値が劇的に変動しないことを確実にするために、コントローラクラスタは、重み付け和を使用して、各新しい測定を以前の測定と混合する。
【０２６２】
2145において、コントローラクラスタはまた、調整された測定グラフに基づいてルーティンググラフを調整する必要があるかどうか（例えば、ルーティンググラフのリンクの重み値を調整する必要があるかどうか、またはリンクに関連する調整された測定値のためにルーティンググラフ内のリンクを追加または削除する必要があるかどうか）を判定する。その場合、コントローラクラスタ（2145）は、ルーティンググラフを調整し、パス探索動作（動作2120など）を実行して、入出力ノードのペア間の経路を識別し、識別された経路に基づいて経路レコードを生成し、経路レコードをMFNに配信する。2145から、プロセスは2150に遷移する。
【０２６３】
また、コントローラクラスタが（2140において）ルーティンググラフを再検査する必要がないと判定した場合、プロセスは2150に遷移する。2150で、コントローラクラスタは、処理されたデータメッセージおよび消費されたネットワーク／コンピューティングリソースに関する統計を収集する必要がある別の請求サイクルに近づいているかどうかを判定する。そうでない場合、プロセスは2135に戻り、MFN測定エージェントから新しい測定値を受信したかどうかを判定する。それ以外の場合、プロセスは2130に戻り、統計の収集、消費データのネットワーク／コンピューティング、および請求レポートの生成と送信を行う。いくつかの実施形態では、コントローラクラスタは、特定のテナントがパブリッククラウドデータセンタ全体にデプロイされる仮想ネットワークを必要としなくなるまで、処理2100の動作を繰り返し実行する。
【０２６４】
いくつかの実施形態では、コントローラクラスタは、パブリッククラウドデータセンタにテナント用の仮想ネットワークをデプロイするだけでなく、パブリッククラウドデータセンタにコンピューティングノードマシンおよびサービスマシンをデプロイし、設定する際にテナントを支援する。デプロイされたサービスマシンは、MFNのサービスマシンとは別のマシンにすることができる。いくつかの実施形態では、コントローラクラスタの請求レポートは、配置されたコンピューティングおよびサービスマシンによって消費されるコンピューティングリソースも考慮する。繰り返しになるが、複数のパブリッククラウドプロバイダの複数のパブリッククラウドデータセンタで消費されるネットワークおよびコンピューティングリソースのために、1つの仮想ネットワークプロバイダから1つの請求書を発行する方が、複数のパブリッククラウドプロバイダから複数の請求書を受信するよりもテナントにとって望ましい。
【０２６５】
上述の特徴およびアプリケーションの多くは、コンピュータ可読記憶媒体（コンピュータ可読媒体とも呼ばれる）に記録された命令のセットとして規定されるソフトウェアプロセスとして実行される。これらの命令が、１つ以上の処理部（例えば、一つ以上のプロセッサ、プロセッサのコア、または他の処理部）によって実行されるとき、それらは、処理部に命令に示された動作を実行させる。コンピュータ可読媒体の例は、限定されるものではないが、CD-ROM、フラッシュドライブ、RAMチップ、ハードドライブ、EPROMなどが含まれる。コンピュータ可読媒体には、搬送波および無線または有線接続を通過する電子信号は含まれない。 
【０２６６】
本明細書では、用語「ソフトウェア」は、読出専用メモリに存在するファームウェア、または磁気ストレージに記憶され、プロセッサによって処理するためにメモリに読み取ることができるアプリケーションを含むことを意味する。また、いくつかの実施形態では、複数のソフトウェア発明は、個別のソフトウェア発明を維持する一方で、より大きなプログラムのサブ部分として実施されてもよい。いくつかの実施形態では、複数のソフトウェア発明はまた、個別のプログラムとして実施されてもよい。最後に、ここで説明されるソフトウェア発明をともに実施する個別のプログラムの任意の組み合わせは、発明の範囲内である。いくつかの実施形態では、ソフトウェアプログラムが、１以上の電子システムを動作させるためにインストールされる場合、１以上の特定の機械的実施を定義し、ソフトウェアプログラムの動作を実行する。
【０２６７】
図22は、本発明のいくつかの実施形態が実施されるコンピュータシステム2200を概念的に示している。コンピュータシステム2200は、上述のホスト、コントローラ、およびマネージャのいずれかを実装するために使用することができる。したがって、それは、上述のプロセスのいずれかを実行するために使用することができる。このコンピュータシステムは、種々のタイプの非一時的な機械可読媒体と、種々の他のタイプの機械可読媒体のためのインタフェースとを含む。コンピュータシステム2200は、バス2205、処理ユニット2210、システムメモリ2225、読出専用メモリ2230、永続ストレージデバイス2235、入力デバイス2240、および出力デバイス2245を含む。 
【０２６８】
バス2205は、集合的に、コンピュータシステム2200の多数の内部装置を通信的に接続するすべてのシステム、周辺装置、およびチップセットバスを表す。例えば、バス2205は、処理ユニット2210を読出専用メモリ2230、システムメモリ2225、および永続ストレージデバイス2235と通信的に接続する。 
【０２６９】
これらの様々なメモリユニットから、処理ユニット2210は、本発明のプロセスを実行するために、処理するための命令を検索し、処理するためのデータを検索する。処理ユニットは、異なる実施形態では、単一プロセッサまたはマルチコアプロセッサであってもよい。読出専用メモリ（ROM）2230は、処理ユニット2210及びコンピュータシステムの他のモジュールによって必要とされる静的データ及び命令を記録する。一方、永続ストレージデバイス2235は、読み出し／書き込みメモリデバイスである。このデバイスは、コンピュータシステム2200がオフの場合であっても命令及びデータを記録する不揮発性メモリユニットである。本発明のいくつかの実施形態は、永続ストレージデバイス2235として大容量記憶装置（例えば、磁気または光ディスクおよびその対応するディスクドライブ）を使用する。 
【０２７０】
他の実施形態では、取り外し可能ストレージデバイス（フロッピーディスク、フラッシュドライブなど）を永続ストレージデバイスとして使用する。永続ストレージデバイス2235と同様に、システムメモリ2225は、読取り／書込みメモリデバイスである。しかしながら、ストレージデバイス2235とは異なり、システムメモリは、ランダムアクセスメモリのような揮発性読み出し／書き込みメモリである。システムメモリは、プロセッサが実行時に必要とする命令とデータの一部が格納される。いくつかの実施形態では、本発明のプロセスは、システムメモリ2225、永続ストレージデバイス2235、および／または読み出し専用メモリ2230に記憶される。これらの様々なメモリユニットから、処理ユニット2210は、いくつかの実施形態のプロセスを実行するために、処理するための命令を検索し、処理するためのデータを検索する。 
【０２７１】
バス2205はまた、入出力デバイス2240および2245に接続する。入力デバイスは、ユーザが情報を通信し、コマンドをコンピュータシステムに選択することを可能にする。入力デバイス2240は、英数字キーボードおよびポインティングデバイス（「カーソル制御装置」とも呼ばれる）を含む。出力デバイス2245は、コンピュータシステムによって生成された画像を表示する。出力デバイスには、プリンタと、ブラウン管（CRT）または液晶ディスプレイ（LCD）などの表示デバイスが含まれる。いくつかの実施形態は、入力デバイスおよび出力デバイスの両方として機能するタッチスクリーンなどのデバイスを含む。 
【０２７２】
最後に、図22に示すように、バス2205は、ネットワークアダプタ（図示せず）を介して、コンピュータシステム2200をネットワーク2265に結合する。このようにして、コンピュータは、（ローカルエリアネットワーク（「LAN」）、ワイドエリアネットワーク（「WAN」）、イントラネット、インターネットなどのネットワークのネットワーク、などのコンピュータのネットワークの一部になることができる。コンピュータシステム2200の任意の又は全てのコンポーネントを、本発明と共に使用することができる。 
【０２７３】
いくつかの実施形態は、機械可読媒体またはコンピュータ可読媒体（代替として、コンピュータ可読ストレージ媒体、機械可読媒体、または機械可読ストレージ媒体）にコンピュータプログラム命令を記憶する、マイクロプロセッサ、ストレージデバイスおよびメモリなどの電子コンポーネントを含む。そのようなコンピュータ可読媒体のいくつかの例には、RAM、ROM、読出専用のコンパクトディスク（CD-ROM）、記録可能コンパクトディスク（CD-R）、書き換え可能コンパクトディスク（CD-RW）、読出専用のデジタル多用途ディスク（例えば、DVD-ROM、デュアルレイヤDVD-ROM）、様々な記録可能／書き換え可能DVD（例えば、DVD-RAM、DVD-RW、DVD＋RWなど）、フラッシュメモリ（例えば、SDカード、ミニSDカード、マイクロSDカードなど）、磁気および／またはソリッドステートハードドライブ、読出専用のおよび記録可能ブルーレイ（登録商標）ディスク、超密度光ディスク、任意の他の光または磁気媒体、およびフロッピー（登録商標）ディスクが含まれる。コンピュータ可読媒体は、少なくとも1つの処理ユニットによって実行可能であり、種々の動作を実行するための命令のセットを含むコンピュータプログラムを記憶することができる。コンピュータプログラムまたはコンピュータコードの例には、コンパイラによって生成されるマシンコード、およびコンピュータ、電子部品、またはインタプリタを使用するマイクロプロセッサによって実行される高水準コードを含むファイルが含まれる。 
【０２７４】
上記の説明は、主に、ソフトウェアを実行するマイクロプロセッサまたはマルチコアプロセッサを指すが、いくつかの実施形態は、特定用途向け集積回路またはフィールドプログラマブルゲートアレイなどの1つ以上の集積回路によって実行される。いくつかの実施形態では、そのような集積回路は、回路自体に格納された命令を実行する。 
【０２７５】
本明細書で使用される「コンピュータ」、「サーバ」、「プロセッサ」、「メモリ」という用語は、すべて電子デバイスまたはその他の技術的なデバイスを指す。これらの用語は、人または人々のグループを除外する。明細書では、用語の表示または表示は、電子デバイス上での表示を意味する。本明細書で使用されるように、「コンピュータ可読媒体」、「コンピュータ可読メディア」、および「機械可読媒体」という用語は、全体として、コンピュータが読み取り可能な形式で情報を保存する実体のある物理的な物体に限定される。これらの用語は、無線信号、有線ダウンロード信号、およびその他の一過性または一時的な信号を除外する。 
【０２７６】
本発明は、数多くの特定の詳細を参照して説明されてきたが、当業者は、本発明が本発明の精神から逸脱することなく、他の特定の形態で実施可能であることを認識するであろう。たとえば、上記の例のいくつかは、仮想ネットワークプロバイダの企業テナントの仮想企業WAN を示している。当業者は、ある実施形態では、仮想ネットワークプロバイダが、企業以外のテナント（例えば、学校、大学、非営利団体など）のために、1つ以上のパブリッククラウドプロバイダの複数のパブリッククラウドデータセンタ上に仮想ネットワークをデプロイすることを理解するであろう。これらの仮想ネットワークは、企業以外のエンティティの複数のコンピューティングエンドポイント（オフィス、データセンタ、コンピュータ、リモートユーザのデバイスなど）を接続する仮想WANである。
【０２７７】
上述のいくつかの実施形態は、オーバレイカプセル化ヘッダ内の各種データの断片を含む。当業者の1人は、他の実施形態が、このデータのすべてを中継するためのカプセル化ヘッダを使用しない可能性があることを理解するであろう。例えば、オーバレイカプセル化ヘッダにテナント識別子を含める代わりに、他の実施形態は、データメッセージを転送するCFEの宛先からテナント識別子を導出する。例えば、異なるテナントがパブリッククラウドにデプロイされた独自のMFNを有するいくつかの実施形態では、テナント識別子は、テナントメッセージを処理するMFNに関連付けられる。
【０２７８】
また、いくつかの図は、本発明のいくつかの実施形態のプロセスを概念的に示す。他の実施形態では、これらのプロセスの特定の動作は、これらの図に示されて説明されている正確な順序では実行されない。特定の動作は、1つの連続した一連の動作では実行されず、異なる特定の動作は、異なる実施形態で実行され得る。さらに、プロセスは、いくつかのサブプロセスを使用して、またはより大きなマクロプロセスの一部として実装することができる。したがって、当業者であれば、本発明は、上述の例示的詳細によって限定されるものではなく、むしろ、添付の請求項によって定義されるものであることが理解されるであろう。
【図１Ａ】
2020536403.tif 000003
【図１Ｂ】
2020536403.tif 000004
【図１Ｃ】
2020536403.tif 000005
【図２】
2020536403.tif 000006
【図３】
2020536403.tif 000007
【図４Ａ】
2020536403.tif 000008
【図４Ｂ】
2020536403.tif 000009
【図４Ｃ】
2020536403.tif 000010
【図４Ｄ】
2020536403.tif 000011
【図５】
2020536403.tif 000012
【図６】
2020536403.tif 000013
【図７】
2020536403.tif 000014
【図８】
2020536403.tif 000015
【図９】
2020536403.tif 000016
【図１０】
2020536403.tif 000017
【図１１】
2020536403.tif 000018
【図１２】
2020536403.tif 000019
【図１３】
2020536403.tif 000020
【図１４】
2020536403.tif 000021
【図１５】
2020536403.tif 000022
【図１６】
2020536403.tif 000023
【図１７】
2020536403.tif 000024
【図１８】
2020536403.tif 000025
【図１９】
2020536403.tif 000026
【図２０】
2020536403.tif 000027
【図２１】
2020536403.tif 000028
【図２２】
2020536403.tif 000029
【手続補正書】
【提出日】令和2年3月30日(2020.3.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のパブリッククラウドデータセンタ上に仮想ネットワークを確立する方法であって、
第１のエンティティに対する第１の仮想ワイドエリアネットワーク（ＷＡＮ）を実施するために第１のマルチテナントのパブリッククラウドデータセンタおよび第２のマルチテナントのパブリッククラウドデータセンタに転送要素の第１のセットを構成することであって、前記第１の仮想ＷＡＮは、前記第１のエンティティの２つ以上のマシンロケーションのセットにおいて動作する複数のマシンを接続する、構成することと、
第２のエンティティに対する第２の仮想ワイドエリアネットワークを実施するために前記第１のマルチテナントのパブリッククラウドデータセンタおよび前記第２のマルチテナントのパブリッククラウドデータセンタに転送要素の第２のセットを構成することであって、前記第２の仮想ＷＡＮは、前記第２のエンティティの２つ以上のマシンロケーションのセットにおいて動作する複数のマシンを接続する、構成することと、を含む方法。
【請求項２】
請求項１に記載の方法であって、前記第１のエンティティの前記マシンロケーションのセットは、２つ以上のオフィスロケーションを含む、方法。
【請求項３】
請求項２に記載の方法であって、前記第１のエンティティの前記マシンロケーションのセットは、さらに、少なくとも１つのデータセンタロケーションを含む方法。
【請求項４】
請求項３に記載の方法であって、前記第１のエンティティの前記マシンロケーションのセットは、さらにリモートデバイスロケーションを含む、方法。
【請求項５】
請求項１に記載の方法であって、前記第１のエンティティの前記マシンロケーションのセットは、オフィスロケーションおよびデータセンタロケーションを含む、方法。
【請求項６】
請求項５に記載の方法であって、前記第１のエンティティの前記マシンロケーションのセットは、SaaS(Software as a Service)プロバイダの複数のマシンを有するロケーションをさらに含む、方法。
【請求項７】
請求項１に記載の方法であって、前記マシンは、仮想マシン、コンテナ、またはスタンドアロンコンピュータの少なくとも１つを含む、方法。
【請求項８】
請求項１に記載の方法であって、前記転送要素の第１のセットのうちの転送要素の少なくともサブセットは、前記転送要素の第２のセットにも含まれる、方法。
【請求項９】
請求項８に記載の方法であって、前記転送要素の第１のセットのうちの、転送要素の少なくとも別のサブセットが、前記転送要素の第２のセットには無い、方法。
【請求項１０】
請求項１に記載の方法であって、 
前記転送要素の第１のセットを構成することは、オーバレイ仮想ＷＡＮヘッダの第１のセットを使用するように前記転送要素の第１のセットを構成して、異なるマシンロケーションの前記第１のエンティティのマシン間で交換されるデータメッセージをカプセル化することを含み、
前記転送要素の第２のセットを構成することは、オーバレイ仮想ＷＡＮヘッダの第２のセットを使用するように前記転送要素の第２のセットを構成して、異なるマシンロケーションの前記第２のエンティティのマシン間で交換されるデータメッセージをカプセル化することを含み、
前記オーバレイ仮想ＷＡＮヘッダの第１のセットは前記第１のエンティティを識別する第１のエンティティ識別子を格納し、前記オーバレイ仮想ＷＡＮヘッダの第２のセットは前記第２のエンティティを識別する第２のエンティティ識別子を格納する、方法。
【請求項１１】
請求項１０に記載の方法であって、少なくとも１つの転送要素が転送要素の両方のセットに含まれるように、前記転送要素の第１および第２のセットが重複する、方法。
【請求項１２】
請求項１に記載の方法であって、前記転送要素の第１および第２のセットを構成することは、異なるパブリッククラウドプロバイダのパブリッククラウドデータセンタ上および異なる領域内に、異なるエンティティに対する異なる仮想ＷＡＮをデプロイする仮想ネットワークプロバイダの１つ以上のコントローラのセットによって実行される、方法。
【請求項１３】
請求項１に記載の方法であって、前記転送要素の第１および第２のセットは、コンピュータ上で動作する複数のソフトウェア転送要素を含む、方法。
【請求項１４】
請求項１に記載の方法であって、前記転送要素の第１および第２のセットは、前記データセンタ内のホストコンピュータ上で動作する複数のソフトウェア転送要素を含む、方法。
【請求項１５】
請求項１４に記載の方法であって、前記複数のソフトウェア転送要素は、前記ホストコンピュータ上で動作するマシンである、方法。
【請求項１６】
請求項１５に記載の方法であって、前記複数のソフトウェア転送要素を実装するマシンの少なくともサブセットは、他のマシンと共にホストコンピュータ上で動作する、方法。
【請求項１７】
請求項１５に記載の方法であって、前記複数のソフトウェア転送要素を実装するマシンの少なくともサブセットは、仮想マシンである、方法。
【請求項１８】
少なくとも１つの処理ユニットによって実行されたときに、請求項１から１７のいずれか１項に記載の方法を実行するプログラム。
【請求項１９】
電子デバイスであって、
処理ユニットのセットと、
少なくとも１つの処理ユニットによって実行されたときに、請求項１から１７のいずれか１項に記載の方法を実行するプログラムを記憶する機械可読媒体とを含む、電子デバイス。
【請求項２０】
請求項１から１７のいずれか１項に記載の方法を実行するための手段を含むシステム。
【国際調査報告】
2020536403.tif 000030
2020536403.tif 000031
2020536403.tif 000032
2020536403.tif 000033
2020536403.tif 000034