(57)【特許請求の範囲】
【請求項１】
マルチドメイン・ネットワークにおいて要件を満たすサービス機能チェーン形成の解を同定する方法であって：
資源オーケストレーターにおいて、前記マルチドメイン・ネットワークにおける個々の物理ノード上で実行されるべき複数のサービス機能を指定するサービス機能チェーン要求を受領する段階であって、各ノードは資源オーケストレーション・フレームワークにおけるバーテックスとして表わされる、段階と；
前記複数のサービス機能のうちの第一のものが利用可能である一つまたは複数のバーテックスを同定する段階と；
同定されたバーテックスのうち第一の同定されたバーテックスについて、
該第一の同定されたバーテックスを候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第一のものにマッピングし、
前記複数のサービス機能のうちの第二のものが前記第一の同定されたバーテックスの第一の近傍バーテックスにおいて利用可能であることを判別し、前記第一の近傍バーテックスは、前記マルチドメイン・ネットワークの、前記第一の同定されたバーテックスが存在するドメインとは異なるドメインに存在し、
前記第一の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第二のものにマッピングして前記候補サービス機能チェーンを延長する、
段階とを含む、
方法。
【請求項２】
前記複数のサービス機能のうちの第三のものが前記第一の近傍バーテックスの第二の近傍バーテックスにおいて利用可能であることを判別する段階であって、前記第二の近傍バーテックスは、前記マルチドメイン・ネットワークの、前記第一の近傍バーテックスが存在するドメインとは異なるドメインに存在する、段階と；
前記第二の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第三のものにマッピングして前記候補サービス機能チェーンをさらに延長する段階とをさらに含む、
請求項１記載の方法。
【請求項３】
前記第一の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第二のものにマッピングすることは、前記候補サービス機能チェーンを完成させ、
当該方法はさらに、完成された候補サービス機能チェーンを前記資源オーケストレーターに返すことを含む、
請求項１記載の方法。
【請求項４】
前記サービス機能チェーン要求は、前記マルチドメイン・ネットワークにおける個々の物理ノード上で実行されるべき前記複数のサービス機能についての固定された順序を指定し、
前記固定された順序は、前記複数のサービス機能のうちの前記第一のものが、前記複数のサービス機能のうちの前記第二のものより先に実行されるべきであることを指定する、
請求項１記載の方法。
【請求項５】
前記候補サービス機能チェーンを完成させる段階と；
一つまたは複数の他の候補サービス機能チェーンを完成させる段階であって、前記他の候補サービス機能チェーンのそれぞれを完成させることは、該他の候補サービス機能チェーンにおける前記複数のサービス機能のうちのそれぞれに対して前記資源オーケストレーション・フレームワークにおける個々のバーテックスをマッピングすることを含み、前記候補サービス機能チェーンと、前記一つまたは複数の他の候補サービス機能チェーンのそれぞれとにおけるマッピングのセットは異なる、段階と；
前記候補サービス機能チェーンおよび前記一つまたは複数の他の候補サービス機能チェーンのうちから、一つまたは複数のサービス機能チェーン解を実行のために選択する段階であって、選択は、サービス・プロバイダー・ポリシー、サービス・プロバイダー制約条件または要求者に依存し、前記サービス機能チェーン要求は該要求者のために受領されたものである、段階とをさらに含む、
請求項１記載の方法。
【請求項６】
前記選択は：
候補サービス機能チェーンの全遅延；
候補サービス機能チェーンの全コスト；
候補サービス機能チェーンのうちの二つにおける物理ノードの重複；
候補サービス機能チェーンのうちの二つにおける物理リンクの重複；または
負荷均衡化機構
のうちの一つまたは複数に依存する、請求項５記載の方法。
【請求項７】
前記サービス機能チェーン要求は、前記マルチドメイン・ネットワークにおける個々の物理ノード上で実行されるべき前記複数のサービス機能についての柔軟な順序付けを指定し、
前記第一の同定されたバーテックスを候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第一のものにマッピングすることは、前記第一の同定されたバーテックスを、前記候補サービス機能チェーンにおける最初の位置以外の位置にあるサービス機能にマッピングすることを含む、
請求項１記載の方法。
【請求項８】
当該方法がさらに：
前記候補サービス機能チェーンを完成させ；
第二の候補サービス機能チェーンを完成させることを含み、
前記第二の候補サービス機能チェーンを完成させることは、前記第二の候補サービス機能チェーンにおける前記複数のサービス機能のうちのそれぞれに対して前記資源オーケストレーション・フレームワークにおける個々のバーテックスをマッピングすることを含み、バーテックスは、前記第二の候補サービス機能チェーンにおいては、前記候補サービス機能チェーンにおいて前記複数のサービス機能にマッピングされたのとは異なる順序で、前記複数のサービス機能にマッピングされる、
請求項７記載の方法。
【請求項９】
前記資源オーケストレーターは、前記マルチドメイン・ネットワークにおいてバーテックス中心のサービス機能チェーン形成を協調させるための唯一の資源オーケストレーターである、請求項１記載の方法。
【請求項１０】
前記資源オーケストレーターは、前記マルチドメイン・ネットワークにおいてバーテックス中心のサービス機能チェーン形成を協調させるための複数の資源オーケストレーターの一つであり、各資源オーケストレーターは、前記マルチドメイン・ネットワークにおけるそれぞれのドメインに関連付けられており、それぞれのドメイン内のバーテックス上での共通のコンピュート関数の実行を協調させる、
請求項１記載の方法。
【請求項１１】
前記複数のサービス機能のうちの第一のものが利用可能である前記一つまたは複数のバーテックスを同定する段階は：
前記資源オーケストレーターがコントローラ・メッセージを別の資源オーケストレーターに送る段階であって、該別の資源オーケストレーターは前記第一の同定されたバーテックスが存在するドメインに関連付けられている、段階と；
前記別の資源オーケストレーターが前記複数のサービス機能のうちの前記第一のものが前記第一の同定されたバーテックスにおいて利用可能であることを判別する段階とを含み、
前記第一の同定されたバーテックスを前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第一のものにマッピングする段階は、前記第一の同定されたバーテックスによって実行される、
請求項１０記載の方法。
【請求項１２】
前記同定されたバーテックスのうち前記第一の同定されたバーテックスおよび前記第一の近傍バーテックスは、物理リンクを通じて互いに通信上結合されており、
前記複数のサービス機能のうちの前記第二のものが前記第一の近傍バーテックスにおいて利用可能であることを判別する段階は：
前記物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすことを判別し；
前記候補サービス機能チェーンを含むコントローラ・メッセージを前記第一の近傍バーテックスに送り；
前記第一の近傍バーテックスが、前記複数のサービス機能のうちの前記第二のものが前記第一の近傍バーテックスにおいて利用可能であることを判別することを含む、
請求項１記載の方法。
【請求項１３】
複数のネットワーク・ドメインを含むマルチドメイン・ネットワークにおける資源オーケストレーション・フレームワークであって、各ネットワーク・ドメインは一つまたは複数の物理ノードを含み、前記物理ノードのそれぞれは、前記マルチドメイン・ネットワークにおいてサポートされる複数のサービス機能の部分集合を実行するための回路または論理を含み、
前記資源オーケストレーション・フレームワークは：
それぞれが前記マルチドメイン・ネットワークにおける前記物理ノードの一つを表わす複数のバーテックスと；
資源オーケストレーターとを含み、
当該資源オーケストレーション・フレームワークにおける各バーテックスは：
プロセッサと；
該プロセッサによって実行されたときに該プロセッサに、当該資源オーケストレーション・フレームワークにおける前記バーテックスの間で共通のコンピュート関数を実行させるプログラム命令を記憶しているメモリとを含み、
前記資源オーケストレーターは、
プロセッサと；
該プロセッサによって実行されたときに該プロセッサに、
前記マルチドメイン・ネットワークにおけるそれぞれの物理ノード上で実行されるべき複数のサービス機能を指定するサービス機能チェーン要求を受領する段階と；
前記複数のサービス機能のうちの第一のものが利用可能である前記資源オーケストレーション・フレームワークにおける一つまたは複数のバーテックスを同定する段階と；
前記複数のバーテックスのうちの複数のものの上での前記共通のコンピュート関数の二つのさらなるスーパーステップの実行を協調させる段階とを実行させるプログラム命令を記憶しているメモリとを含み、前記共通のコンピュート関数の第一のスーパーステップの間に、前記同定されたバーテックスのうち第一の同定されたバーテックスでの前記共通のコンピュート関数の実行は、
該第一の同定されたバーテックスを候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第一のものにマッピングする段階と；
前記第一の同定されたバーテックスと前記第一の同定されたバーテックスの第一の近傍バーテックスとの間の物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすか否かを判定する段階とを含み、前記第一の近傍バーテックスは、前記マルチドメイン・ネットワークの、前記第一の同定されたバーテックスが存在するドメインとは異なるドメインに存在する、
資源オーケストレーション・フレームワーク。
【請求項１４】
前記第一のスーパーステップの間に、前記第一の同定されたバーテックスでの前記共通のコンピュート関数の実行はさらに、
前記第一の同定されたバーテックスと前記第一の近傍バーテックスとの間の物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすと判定することに応答して、前記候補サービス機能チェーンを前記第一の近傍バーテックスに提供することを含み、
前記共通のコンピュート関数の第二のスーパーステップの間に、前記第一の近傍バーテックスでの前記共通のコンピュート関数の実行は、
前記候補サービス機能チェーンを取得することに応答して、前記候補サービス機能チェーンが前記第一の近傍バーテックスにおいて延長されることができるか否かを判定することを含む、
請求項１３記載の資源オーケストレーション・フレームワーク。
【請求項１５】
前記第二のスーパーステップの間に、前記第一の近傍バーテックスでの前記共通のコンピュート関数の実行はさらに、
前記複数のサービス機能のうちの第二のものが前記第一の近傍バーテックスにおいて利用可能であることを判別する段階と；
前記第一の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第二のものにマッピングして前記候補サービス機能チェーンを延長する段階とを含む、
請求項１４記載の資源オーケストレーション・フレームワーク。
【請求項１６】
前記第二のスーパーステップの間に、前記第一の近傍バーテックスでの前記共通のコンピュート関数の実行はさらに、
前記第一の近傍バーテックスと前記第一の近傍バーテックスの第二の近傍バーテックスとの間の物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすか否かを判定する段階であって、前記第二の近傍バーテックスは、前記マルチドメイン・ネットワークの、前記第一の近傍バーテックスが存在するドメインとは異なるドメインに存在する、段階と；
前記第一の近傍バーテックスと前記第二の近傍バーテックスとの間の物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすと判定することに応答して、延長された候補サービス機能チェーンを前記第二の近傍バーテックスに提供する段階とを含む、
請求項１５記載の資源オーケストレーション・フレームワーク。
【請求項１７】
前記第二のスーパーステップの間に、前記第一の近傍バーテックスでの前記共通のコンピュート関数の実行はさらに、
前記第一の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第二のものにマッピングすることが、前記候補サービス機能チェーンを完成させることを判別し；
完成された候補サービス機能チェーンを前記資源オーケストレーターに提供することを含む、
請求項１５記載の資源オーケストレーション・フレームワーク。
【請求項１８】
前記資源オーケストレーターの前記プロセッサによって実行されたとき、前記資源オーケストレーターの前記メモリに記憶された前記プログラム命令は、該プロセッサに、
前記の完成された候補サービス機能チェーンおよび一つまたは複数の他の完成された候補サービス機能チェーンのうちから、一つまたは複数のサービス機能チェーン解を実行のために選択することを実行させ、該選択は、サービス・プロバイダー・ポリシー、サービス・プロバイダー制約条件または要求者に依存し、前記サービス機能チェーン要求は該要求者のために受領されたものである、
請求項１７記載の資源オーケストレーション・フレームワーク。
【請求項１９】
前記資源オーケストレーターは、前記マルチドメイン・ネットワークにおいてバーテックス中心のサービス機能チェーン形成を協調させるための唯一の資源オーケストレーターである、請求項１３記載の資源オーケストレーション・フレームワーク。
【請求項２０】
前記資源オーケストレーション・フレームワークは前記資源オーケストレーターを含む複数の資源オーケストレーターを含み、各資源オーケストレーターは、前記マルチドメイン・ネットワークにおけるそれぞれのドメインに関連付けられており、それぞれのドメイン内のバーテックス上での前記共通のコンピュート関数の前記二つのさらなるスーパーステップの実行を協調させる、請求項１３記載の資源オーケストレーション・フレームワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願への相互参照
本願は、2015年10月12日に出願された、「マルチドメイン・ネットワークにおけるサービス機能チェーン形成」という名称の米国仮特許出願第62/240,199号からの米国特許法第１１９条のもとでの優先権を主張するものである。同出願の内容はここに参照によってあらゆる目的についてその全体において組み込まれる。
【０００２】
開示の分野
本開示は概括的にはネットワーク機能仮想化に、より詳細にはマルチドメイン・ネットワークにおけるバーテックス中心のサービス機能チェーン形成を実行するためのシステムおよび方法に関する。
【背景技術】
【０００３】
クラウドおよびビッグデータといった新興ネットワーク・アプリケーションは、一つまたは複数のデータ・センター（DC）内の複数のドメイン内に存在するIT資源を合同して考慮することに関わることがある。ネットワーク機能仮想化（NFV:  network  function  virtualization）は、ネットワーク機能を仮想化し、該ネットワーク機能を単一の特定の目的のために構築されている装置から多目的仮想マシンに移行させるために使用されることができる。それにより、サービス展開コストを低減するとともに、サービスの柔軟性を改善しうる。より多くのサービス機能が地理的に分散したデータ・センターにある仮想マシンに移行するにつれ、またソフトウェア定義ネットワーキング（SDN:  software-defined  networking）技術によってますます多くの個々に管理されるネットワーク・オン・デマンドが有効にされるにつれ、エンドツーエンドのネットワーク・サービスは、複数ドメインのネットワークを横断した諸資源を協調させるためのさまざまな機構を実装しうる。たとえば、ネットワーク・サービスは、一つまたは複数の消費者ブロードバンド・ネットワーク、モバイル・バックホール・ネットワーク、モバイル・パケット・コア・ネットワークおよび／または仮想閉域網（virtual  private  network）を横断しうる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
伝統的な分散式のルーティング・プロトコルは典型的には、個々のネットワーク・ノードにおけるサービス機能および仮想マシンの利用可能性は考慮することなくネットワーク経路を計算する。ハイブリッド・アーキテクチャ（たとえば、サービス機能、仮想マシンおよびネットワークのグローバル・ビューを複製する地理的に分散したオーケストレーターをもつもの）は、グローバルなネットワーク状態の管理、さまざまなネットワーク・ドメインの秘匿性の維持および大規模なグローバル・ビューでの高い計算上の複雑さの管理といった追加的な課題につながりうる。仮想光ネットワーク要求（virtual  optical  network  requests）をマッピングするための経路計算要素（PCE:  path-computation  element）ベースのマルチドメイン・ヒューリスティックスを使う手法は、典型的には、あらゆる可能なドメイン間経路を計算するために親PCEを必要とする。さらに、単一の仮想リンクをマッピングするために典型的には、すべての可能なドメイン間経路に沿って信号伝達することが必要になり、これは大規模ネットワークにおける非常に多数の経路については著しい信号伝達オーバーヘッドにつながりうる。マルチドメイン・ネットワークについての以前に提案された仮想ネットワーク・マッピング・アルゴリズムは、サービス機能チェーン（SFC:  service  function  chain）要求をマッピングするには好適でありうるが、典型的には、マルチドメイン・ネットワークにおいてすべてのドメインについての階層的なトポロジーを維持するために、中央集中したオーケストレーターを必要とする。
【課題を解決するための手段】
【０００５】
ある側面では、開示される方法は、マルチドメイン・ネットワークにおいて要件を満たす（qualified）サービス機能チェーン形成の解を特定するためのものである。本方法は、資源オーケストレーターにおいて、マルチドメイン・ネットワークにおける個々の物理ノード上で実行されるべき複数のサービス機能を指定するサービス機能チェーン要求を受領する段階であって、各ノードは資源オーケストレーション・フレームワークにおいてバーテックスとして表わされる、段階と、前記複数のサービス機能のうちの第一のものが利用可能である一つまたは複数のバーテックスを同定する段階とを含んでいてもよい。本方法はまた、同定されたバーテックスのうち第一の同定されたバーテックスにおいて、該第一の同定されたバーテックスを候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第一のものにマッピングする段階と、前記複数のサービス機能のうちの第二のものが前記第一の同定されたバーテックスの第一の近傍（neighbor）バーテックスにおいて利用可能であることを判別する段階であって、前記第一の近傍バーテックスは、マルチドメイン・ネットワークの、前記第一の同定されたバーテックスが存在するドメインとは異なるドメインに存在する、段階と、前記第一の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第二のものにマッピングして前記候補サービス機能チェーンを延長する段階とを含んでいてもよい。
【０００６】
開示される実施形態の任意のものにおいて、本方法はさらに、前記複数のサービス機能のうちの第三のものが前記第一の近傍バーテックスの第二の近傍（neighbor）バーテックスにおいて利用可能であることを判別する段階であって、前記第二の近傍バーテックスは、マルチドメイン・ネットワークの、前記第一の近傍バーテックスが存在するドメインとは異なるドメインに存在する、段階と、前記第二の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第三のものにマッピングして前記候補サービス機能チェーンをさらに延長する段階とを含んでいてもよい。
【０００７】
開示される実施形態の任意のものにおいて、前記第一の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第二のものにマッピングすることは、前記候補サービス機能チェーンを完成させてもよく、本方法はさらに、完成された候補サービス機能チェーンを前記資源オーケストレーターに返すことを含んでいてもよい。
【０００８】
開示される実施形態の任意のものにおいて、前記サービス機能チェーン要求は、マルチドメイン・ネットワークにおけるそれぞれの物理ノード上で実行されるべき前記複数のサービス機能についての固定された順序を指定してもよく、固定された順序は、前記複数のサービス機能のうちの前記第一のものが、前記複数のサービス機能のうちの前記第二のものより先に実行されるべきであることを指定してもよい。
【０００９】
開示される実施形態の任意のものにおいて、本方法はさらに、前記候補サービス機能チェーンを完成させ、一つまたは複数の他の候補サービス機能チェーンを完成させることを含んでいてもよい。前記他の候補サービス機能チェーンのそれぞれを完成させることは、前記資源オーケストレーション・フレームワークにおけるそれぞれのバーテックスを、前記他の候補サービス機能チェーンにおける前記複数のサービス機能のうちのそれぞれにマッピングすることを含んでいてもよい。前記候補サービス機能チェーンと、前記一つまたは複数の他の候補サービス機能チェーンのそれぞれとにおけるマッピングのセットは異なっていてもよい。本方法は、前記候補サービス機能チェーンおよび前記一つまたは複数の他の候補サービス機能チェーンのうちから、一つまたは複数のサービス機能チェーン解を実行のために選択することをも含んでいてもよい。選択は、サービス・プロバイダー・ポリシー、サービス・プロバイダー制約条件または要求者（該要求者のために前記サービス機能チェーン要求が受領された）に依存してもよい。
【００１０】
開示される実施形態の任意のものにおいて、前記選択は：候補サービス機能チェーンの全遅延、候補サービス機能チェーンの全コスト、候補サービス機能チェーンのうちの二つにおける物理ノードの重複、候補サービス機能チェーンの二つにおける物理リンクの重複または負荷均衡化機構のうちの一つまたは複数に依存していてもよい。
【００１１】
開示される実施形態の任意のものにおいて、前記サービス機能チェーン要求は、マルチドメイン・ネットワークにおけるそれぞれの物理ノード上で実行されるべき前記複数のサービス機能についての柔軟な順序付けを指定してもよく、前記第一の同定されたバーテックスを候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第一のものにマッピングすることは、前記第一の同定されたバーテックスを、前記候補サービス機能チェーンにおける最初の位置以外の位置にあるサービス機能にマッピングすることを含んでいてもよい。
【００１２】
開示される実施形態の任意のものにおいて、本方法はさらに、前記候補サービス機能チェーンを完成させ、第二の候補サービス機能チェーンを完成させることを含んでいてもよい。前記第二の候補サービス機能チェーンを完成させることは、前記資源オーケストレーション・フレームワークにおけるそれぞれのバーテックスを、前記第二の候補サービス機能チェーンにおける前記複数のサービス機能のうちのそれぞれにマッピングすることを含んでいてもよい。バーテックスは、前記第二の候補サービス機能チェーンにおいては、前記候補サービス機能チェーンにおいて前記複数のサービス機能にマッピングされたのとは異なる順序で、前記複数のサービス機能にマッピングされてもよい。
【００１３】
開示される実施形態の任意のものにおいて、前記資源オーケストレーターは、マルチドメイン・ネットワークにおいてバーテックス中心のサービス機能チェーン形成を協調させるための唯一の資源オーケストレーターであってもよい。
【００１４】
開示される実施形態の任意のものにおいて、前記資源オーケストレーターは、マルチドメイン・ネットワークにおいてバーテックス中心のサービス機能チェーン形成を協調させるための複数の資源オーケストレーターの一つであってもよい。各資源オーケストレーターは、マルチドメイン・ネットワークにおけるそれぞれのドメインに関連付けられており、それぞれのドメイン内のバーテックス上での共通のコンピュート関数の実行を協調させる。
【００１５】
開示される実施形態の任意のものにおいて、前記複数のサービス機能のうちの第一のものが利用可能である前記一つまたは複数のバーテックスを同定する段階は、前記資源オーケストレーターがコントローラ・メッセージを別の資源オーケストレーターに送る段階であって、該別の資源オーケストレーターは前記第一の同定されたバーテックスが存在するドメインに関連付けられている、段階と、前記別の資源オーケストレーターが前記複数のサービス機能のうちの前記第一のものが前記第一の同定されたバーテックスにおいて利用可能であることを判別する段階とを含んでいてもよい。前記第一の同定されたバーテックスを前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第一のものにマッピングする段階は、前記第一の同定されたバーテックスによって実行されてもよい。
【００１６】
開示される実施形態の任意のものにおいて、前記同定されたバーテックスのうち前記第一の同定されたバーテックスおよび前記第一の近傍バーテックスは、物理リンクを通じて互いに通信上結合されていてもよく、前記複数のサービス機能のうちの前記第二のものが前記第一の近傍バーテックスにおいて利用可能であることを判別する段階は、前記物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすことを判別し、前記候補サービス機能チェーンを含むコントローラ・メッセージを前記第一の近傍バーテックスに送り、前記第一の近傍バーテックスが、前記複数のサービス機能のうちの前記第二のものが前記第一の近傍バーテックスにおいて利用可能であることを判別することを含んでいてもよい。
【００１７】
もう一つの側面では、マルチドメイン・ネットワークにおける開示される資源オーケストレーション・フレームワークは、それぞれがマルチドメイン・ネットワークにおける物理ノードの一つを表わす複数のバーテックスと、資源オーケストレーターとを含んでいてもよい。マルチドメイン・ネットワークは、それぞれが一つまたは複数の物理ノードを含む複数のネットワーク・ドメインを含んでいてもよい。各物理ノードは、マルチドメイン・ネットワークにおいてサポートされる複数のサービス機能の部分集合を実行するための回路または論理を含んでいてもよい。資源オーケストレーション・フレームワークにおける各バーテックスは、プロセッサと、該プロセッサによって実行されたときに該プロセッサに、資源オーケストレーション・フレームワークにおけるバーテックスの間で共通のコンピュート関数を実行させるプログラム命令を記憶しているメモリとを含んでいてもよい。資源オーケストレーターは、プロセッサと、該プロセッサによって実行されたときに該プロセッサに、マルチドメイン・ネットワークにおけるそれぞれの物理ノード上で実行されるべき複数のサービス機能を指定するサービス機能チェーン要求を受領する段階と、前記複数のサービス機能のうちの第一のものが利用可能である前記資源オーケストレーション・フレームワークにおける一つまたは複数のバーテックスを同定する段階と、前記複数のバーテックスのうちの複数のものの上での前記共通のコンピュート関数の二つのさらなるスーパーステップの実行を協調させる段階とを実行させるプログラム命令を記憶しているメモリとを含んでいてもよい。前記共通のコンピュート関数の第一のスーパーステップの間に、前記同定されたバーテックスのうち前記第一の同定されたバーテックスでの前記共通のコンピュート関数の実行は、該第一の同定されたバーテックスを候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第一のものにマッピングする段階と、前記第一の同定されたバーテックスと前記第一の同定されたバーテックスの第一の近傍バーテックスとの間の物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすか否かを判定する段階とを含んでいてもよい。前記第一の近傍バーテックスは、マルチドメイン・ネットワークの、前記第一の同定されたバーテックスが存在するドメインとは異なるドメインに存在していてもよい。
【００１８】
開示される実施形態の任意のものにおいて、前記第一のスーパーステップの間に、前記第一の同定されたバーテックスでの前記共通のコンピュート関数の実行はさらに、前記第一の同定されたバーテックスと前記第一の近傍バーテックスとの間の物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすと判定することに応答して、前記候補サービス機能チェーンを前記第一の近傍バーテックスに提供することを含んでいてもよい。前記共通のコンピュート関数の第二のスーパーステップの間に、前記第一の近傍バーテックスでの前記共通のコンピュート関数の実行は、前記候補サービス機能チェーンを取得することに応答して、前記候補サービス機能チェーンが前記第一の近傍バーテックスにおいて延長されることができるか否かを判定することを含んでいてもよい。
【００１９】
開示される実施形態の任意のものにおいて、前記第二のスーパーステップの間に、前記第一の近傍バーテックスでの前記共通のコンピュート関数の実行はさらに、前記複数のサービス機能のうちの第二のものが前記第一の近傍バーテックスにおいて利用可能であることを判別する段階と、前記第一の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第二のものにマッピングして前記候補サービス機能チェーンを延長する段階とを含んでいてもよい。
【００２０】
開示される実施形態の任意のものにおいて、前記第二のスーパーステップの間に、前記第一の近傍バーテックスでの前記共通のコンピュート関数の実行はさらに、前記第一の近傍バーテックスと前記第一の近傍バーテックスの第二の近傍バーテックスとの間の物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすか否かを判定する段階を含んでいてもよい。前記第二の近傍バーテックスは、マルチドメイン・ネットワークの、前記第一の近傍バーテックスが存在するドメインとは異なるドメインに存在していてもよい。前記第二のスーパーステップの間に、前記第一の近傍バーテックスでの前記共通のコンピュート関数の実行はまた、前記第一の近傍バーテックスと前記第二の近傍バーテックスとの間の物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすと判定することに応答して、延長された候補サービス機能チェーンを前記第二の近傍バーテックスに提供することをも含んでいてもよい。
【００２１】
開示される実施形態の任意のものにおいて、前記第二のスーパーステップの間に、前記第一の近傍バーテックスでの前記共通のコンピュート関数の実行はさらに、前記第一の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第二のものにマッピングすることが、前記候補サービス機能チェーンを完成させることを判別し、完成された候補サービス機能チェーンを資源オーケストレーターに提供することを含んでいてもよい。
【００２２】
開示される実施形態の任意のものにおいて、資源オーケストレーターのプロセッサによって実行されたとき、資源オーケストレーターのメモリに記憶された前記プログラム命令は、該プロセッサに、前記の完成された候補サービス機能チェーンおよび一つまたは複数の他の完成された候補サービス機能チェーンのうちから、一つまたは複数のサービス機能チェーンの解を実行のために選択することを実行させる。選択は、サービス・プロバイダー・ポリシー、サービス・プロバイダー制約条件または要求者（該要求者のために前記サービス機能チェーン要求が受領された）に依存してもよい。
【００２３】
開示される実施形態の任意のものにおいて、前記資源オーケストレーターは、マルチドメイン・ネットワークにおいてバーテックス中心のサービス機能チェーン形成を協調させるための唯一の資源オーケストレーターであってもよい。
【００２４】
開示される実施形態の任意のものにおいて、前記資源オーケストレーション・フレームワークは前記資源オーケストレーターを含む複数の資源オーケストレーターを含んでいてもよく、各資源オーケストレーターは、マルチドメイン・ネットワークにおけるそれぞれのドメインに関連付けられており、それぞれのドメイン内のバーテックス上での共通のコンピュート関数の前記二つのさらなるスーパーステップの実行を協調させる。
【図面の簡単な説明】
【００２５】
本発明ならびにその特徴および利点のより完全な理解のために、ここで、付属の図面との関連で参酌される以下の記述を参照する。
【図１】少なくともいくつかの実施形態に基づく、分散式の資源オーケストレーションの選択された要素を示す図である。
【図２】ある実施形態に基づく、エンドツーエンド・サービスを提供するためのマルチドメイン・ネットワークの選択された要素を示すブロック図である。
【図３】ある実施形態に基づく、複数の分散されたネットワーク・ドメインの選択された要素を示すネットワーク図である。
【図４】ある実施形態に基づく、異なるドメインのそれぞれの資源オーケストレーターの間の通信チャネル（またはリンク）を含む分散式の資源オーケストレーション・アーキテクチャを示す図である。
【図５】ある実施形態に基づく、例示的なSFC要求の抽象化を描く図である。
【図６】ＡおよびＢは、ある実施形態に基づく、柔軟な順序のサービス機能チェーンを指定するSFC要求と、いずれももしみつかるならこの要求を満たすはずの六つの固定した順序のチェーンとの間の例示的なマッピングを示す図である。
【図７Ａ】ある実施形態に基づく、compute()関数を実行する例示的方法の選択された要素を示す図である。
【図７Ｂ】ある実施形態に基づく、compute()関数を実行する例示的方法の選択された要素を示す図である。
【図８Ａ】ある実施形態に基づく、サービス機能チェーン要求に対する一つまたは複数の候補解を生成するためのバーテックス中心の分散式コンピューティングの例を示す図である。
【図８Ｂ】ある実施形態に基づく、サービス機能チェーン要求に対する一つまたは複数の候補解を生成するためのバーテックス中心の分散式コンピューティングの例を示す図である。
【図８Ｃ】ある実施形態に基づく、サービス機能チェーン要求に対する一つまたは複数の候補解を生成するためのバーテックス中心の分散式コンピューティングの例を示す図である。
【図８Ｄ】ある実施形態に基づく、サービス機能チェーン要求に対する一つまたは複数の候補解を生成するためのバーテックス中心の分散式コンピューティングの例を示す図である。
【図８Ｅ】ある実施形態に基づく、サービス機能チェーン要求に対する一つまたは複数の候補解を生成するためのバーテックス中心の分散式コンピューティングの例を示す図である。
【図８Ｆ】ある実施形態に基づく、サービス機能チェーン要求に対する一つまたは複数の候補解を生成するためのバーテックス中心の分散式コンピューティングの例を示す図である。
【図８Ｇ】ある実施形態に基づく、サービス機能チェーン要求に対する一つまたは複数の候補解を生成するためのバーテックス中心の分散式コンピューティングの例を示す図である。
【図８Ｈ】ある実施形態に基づく、サービス機能チェーン要求に対する一つまたは複数の候補解を生成するためのバーテックス中心の分散式コンピューティングの例を示す図である。
【図８Ｉ】ある実施形態に基づく、サービス機能チェーン要求に対する一つまたは複数の候補解を生成するためのバーテックス中心の分散式コンピューティングの例を示す図である。
【図８Ｊ】ある実施形態に基づく、サービス機能チェーン要求に対する一つまたは複数の候補解を生成するためのバーテックス中心の分散式コンピューティングの例を示す図である。
【図９】ある実施形態に基づく、マルチドメイン・ネットワークにおいてサービス機能チェーン要求についての要件を満たす解すべてを同定するための、バーテックス中心の分散式アルゴリズムを実行するための方法の選択された要素を示す流れ図である。
【図１０】ある実施形態に基づく、サービス機能チェーン要求を満足させる方法の選択された要素を示す流れ図である。
【図１１】少なくともいくつかの実施形態に基づく、例示的なネットワーク要素の選択された要素のブロック図である。
【図１２Ａ】ある実施形態に基づく、本稿に記載されるマルチドメイン・ネットワークにおける要件を満たすSFC解すべてを同定するためのバーテックス中心の計算のシミュレーションの選択された結果を示す図である。
【図１２Ｂ】ある実施形態に基づく、本稿に記載されるマルチドメイン・ネットワークにおける要件を満たすSFC解すべてを同定するためのバーテックス中心の計算のシミュレーションの選択された結果を示す図である。
【図１２Ｃ】ある実施形態に基づく、本稿に記載されるマルチドメイン・ネットワークにおける要件を満たすSFC解すべてを同定するためのバーテックス中心の計算のシミュレーションの選択された結果を示す図である。
【発明を実施するための形態】
【００２６】
以下の記述では、開示される主題の議論を助けるため、例として、詳細が記述される。しかしながら、開示される実施形態は例示的なものであり、あらゆる可能な実施形態を網羅したものではないことは当業者には明白なはずである。
【００２７】
本開示を通じて、参照符号のハイフン付きの形は要素の個別的なインスタンスを指し、該参照符号のハイフンなしの形は該要素を一般的または集団的に指す。よって、例として（図示せず）、装置「１２−１」は、装置「１２」とまとめて称されうる装置クラスのあるインスタンスを指す。それらの装置の任意のものは一般的に装置「１２」と称されうる。図面および本記述において、同様の符号は同様の要素を表わすことが意図されている。
【００２８】
本稿で後述するように、マルチドメイン・ネットワークにおいて要件を満たすサービス機能チェーン（SFC）解すべてを同定するためのスケーラブルなバーテックス中心の分散式手法を提供する分散式資源オーケストレーション・フレームワークが開示される。いくつかの実施形態では、本稿に開示される分散式資源オーケストレーション・フレームワークは、異なるバーテックスが可能なSFC解についての情報を交換できるようにするバーテックス中心の分散式処理手法を、すべての可能な解が同定されるまで、コントローラ・メッセージを使って逐次反復的に適用しうる。本稿に開示される分散式資源オーケストレーション・フレームワークのいくつかの実施形態では、ネットワーク・ドメインの資源を管理する各ドメイン資源オーケストレーターがそのネットワーク・ドメイン内の各バーテックスにメッセージを送ってもよく、ドメイン資源オーケストレーターはコントローラ・メッセージを使って互いと通信してもよい。シミュレーション結果は、中央集中されたアルゴリズムに比べたときに大きなSFC要求を計算するためのよりすぐれた効率性およびスケーラビリティーを実証した。
【００２９】
ここで図面に目を転じると、図１は、少なくともいくつかの実施形態に基づく、分散式資源オーケストレーション・フレームワークの選択された要素を示している。より具体的には、図１は、ネットワーク・ドメイン１００の例示的実施形態を示しており、これは個々のネットワーク要素（NE:  network  element）であるバーテックスに基づく。図１では、ネットワーク・ドメイン１００はドメイン固有の資源オーケストレーター１０８および物理ネットワーク１１０を含むものとして示されている。いくつかの実施形態では、物理ネットワーク１１０は、光転送ネットワーク（OTN:  optical  transport  network）または接続の帯域幅を調整するよう構成されている柔軟な光データ面（optical  data  plane）（たとえば柔軟なトランシーバ）のような根底にある光ネットワークであってもよい。
【００３０】
図１では、資源オーケストレーター１０８は、複数のネットワーク要素１１２を有するものとして示されているネットワーク・ドメイン１００内の資源の使用を管理するまたは協調させることをしてもよい。ネットワーク要素１１２は、スイッチ、ルーターなどといったネットワーク機能のさまざまな型を表わしていてもよく、さまざまな型の物理的インターフェースを相互接続するためのハードウェアを含んでいてもよい。ネットワーク・ドメイン１００は、ネットワーク要素NE_A  １１２−１、ネットワーク要素NE_B  １１２−２、ネットワーク要素NE_C  １１２−３、ネットワーク要素NE_D  １１２−４、ネットワーク要素NE_E  １１２−５、ネットワーク要素NE_F  １１２−６を、該ネットワーク要素間の、異なる距離をもちうる接続とともに、有している。このように、ネットワーク・ドメイン１００は、資源オーケストレーター１０８によってその資源の使用が協調させられる単一のネットワーク・ドメインについてのネットワーク・トポロジーを表わしていてもよい。いくつかの実施形態では、資源オーケストレーター１０８によって提供されるもの以外のネットワーク・ドメイン１００のためのさまざまなネットワーク管理機能が、専用の（たとえばドメイン固有の）SDNコントローラ（図示せず）によって提供されてもよい。より大きなネットワークが複数のネットワーク・ドメインを含むときは、個々の各ネットワーク・ドメインがそれぞれのSDNコントローラによって管理されてもよい。
【００３１】
本稿でさらに詳細に開示されるように、ネットワーク・ドメイン１００は、分散式処理手法を使うマルチドメイン・ネットワークに含まれていてもよい。該マルチドメイン・ネットワークでは、それぞれ物理ネットワーク１１０のような複数のネットワーク・ドメインのうち対応する一つに関連付けられている、資源オーケストレーター１０８および／またはSDNコントローラのような複数の資源オーケストレーターおよび／またはネットワーク・コントローラの間でコントローラ・メッセージが交換される。本稿の記載では、資源オーケストレーターは、マルチドメイン・ネットワークにおけるSFCを協働的に実行するために機能してもよく、これはすべての可能なSFC解を同定し、（たとえばユーザー選好またはさまざまなポリシーに依存して）可能なSFC解の一つまたは複数を実行のために選択し、選択解（単数または複数）を実装するようさまざまなネットワーク・ノードの物理資源を構成することを含んでいてもよい。
【００３２】
先述したように、ネットワーク機能仮想化（NFV）は、ネットワーク機能を仮想化し、該ネットワーク機能を単一の特定の目的のために構築されている装置から、商業的な既製の多目的仮想マシンに移行させるために使用されることができる。それにより、サービス展開コストを低減するとともに、サービスの柔軟性を改善しうる。NFVを実装するシステムにおいて、エンドツーエンド・ネットワーク・サービスを提供するために、サービス機能チェーン（SFC:  service  function  chain）と称される諸仮想ネットワーク機能（VNF:  virtual  network  function）が逐次順に呼び出される必要があることがある。サービス機能チェーン形成は、これらの仮想化されたネットワーク機能を実行するためにさまざまな仮想マシン（VM）を構成するおよび／または割り当てることを含んでいてもよく、一つまたは複数のネットワークを横断してトラフィックをステアリングすることにも関わっていてもよい。たとえば、トラフィック・フローは、サービス・プロバイダーのポリシーおよび／またはユーザー選好に基づいて特定の順序でいくつかの仮想ネットワーク機能（VNF）またはサービス機能（SF:  service  function）を通じてステアリングされてもよい。本稿に記載される分散式資源オーケストレーション・フレームワークのいくつかの実施形態では、サービス機能チェーン形成は、資源オーケストレーションの適用によってサポートされてもよい。たとえば、いくつかの実施形態では、本稿で資源オーケストレーターと称される複数の資源オーケストレーション要素が集団的および個々に、各データ・センターにおけるさまざまな資源（サービス機能、仮想マシンおよびネットワークを含む）ならびにVNFを相互接続するための関連するネットワーク資源の使用を管理し、協調させてもよい。地理的に分散した諸データ・センターのVMへのVNFの移行と、IP/OTNネットワークにおけるSDN制御されたオンデマンド接続性の実施により、本稿に記載されるようなマルチドメイン・ネットワークを横断した分散式の資源オーケストレーションは、エンドツーエンド・ネットワーク・サービスを提供するためにきわめて有益になりうる。たとえば、ネットワーク・サービスは、消費者ブロードバンド、モバイル・バックホール、モバイル・パケット・コアおよび／または仮想閉域網（たとえば富士通ネットワークコミュニケーションズ社からの1Finity（商標）プラットフォーム上に実装された諸ネットワークを含む）といった複数のネットワークにまたがっていてもよい。
【００３３】
本開示のさまざまな実施形態において、大規模なマルチドメイン・ネットワークは多くの異なるドメインを含むことがあり、これらのドメインは異なるネットワーク技術、異なるベンダー、異なるアドミニストレーション、異なる型の資源および／または異なる仮想化されたネットワークを有することがある。これらのドメインは、モノのインターネット（IoT:  Internet  of  Things）装置、コンピューティング資源、記憶資源および／または種々の型のサービス機能（アクセス・サービス機能、メトロ・サービス機能および／またはコア・サービス機能を含む）が存在するドメインを含んでいてもよい。少なくともいくつかの実施形態では、これらのマルチドメイン・ネットワークは、ドメイン間で秘匿性を保持し、サービス・プロバイダーについてのスケーラビリティーを改善しうる。本稿に記載されるマルチドメイン・オーケストレーション・アーキテクチャの少なくともいくつかでは、各ドメインはローカルなオーケストレーターによって制御されてもよく、オーケストレーター間のバーテックス中心の分散式コンピューティングがエンドツーエンドの資源割り当てを提供しうる。
【００３４】
図２は、ある実施形態に基づく、エンドツーエンド・サービスを提供するためのマルチドメイン・ネットワークの選択された要素を示すブロック図である。この例示的実施形態では、マルチドメイン・ネットワーク２００はドメイン２１０、２２０、２３０、２４０として示されている四つのドメインを含む。これらの各ドメインは、一つまたは複数のノード（バーテックス）を含んでいてもよく、少なくともそのいくつかは、そのドメイン内の資源を使って一つまたは複数のサービス機能を実装してもよい。第一のドメイン、ドメイン２１０は、モノのインターネット（IoT）を表わし、そのさまざまな装置がサービス機能チェーン要求を発しうる。三つのそのような装置が図２に装置２１１、２１２、２１３として示されているが、種々の実施形態において、任意の数の装置がドメイン２１０に含まれうる。この例示的実施形態では、第二のドメイン、ドメイン２２０は、サービス機能チェーンに含まれうるアクセス・サービスを提供する一つまたは複数のデータ・センターまたは他のエンティティを表わす。三つのそのようなサービスが図２にサービス２２１、２２２、２２３として示されているが、種々の実施形態において、任意の数の装置がドメイン２２０に含まれうる。
【００３５】
この例示的実施形態において、第三のドメイン、ドメイン２３０は、サービス機能チェーンに含まれうるコンピューティングおよび／または記憶サービスを提供する一つまたは複数のデータ・センターまたは他のエンティティを表わす。三つのそのようなサービスが図２にサービス２３１、２３２、２３３として示されているが、種々の実施形態において、任意の数の装置がドメイン２３０に含まれうる。この例示的実施形態では、第四のドメイン、ドメイン２４０は、サービス機能チェーンに含まれうるコア・サービス機能を提供する一つまたは複数のデータ・センターまたは他のエンティティを表わす。三つのそのようなサービスが図２にコア・サービス機能２４１、２４２、２４３として示されているが、種々の実施形態において、任意の数の装置がドメイン２４０に含まれうる。
【００３６】
図２に示される例では、ドメイン２１０内の装置２１１がサービス機能チェーン要求２１４を発している。このサービス機能チェーン要求２１４は、少なくとも一つのアクセス・サービス、一つのコンピューティングもしくは記憶サービスおよび一つのコア・サービス機能を含む。より具体的には、サービス機能チェーン要求２１４は、アクセス・サービス機能２２３（これはドメイン２２０内のノード／バーテックスの一つで利用可能である）と、コンピューティングもしくは記憶サービス機能２３２（これはドメイン２３０内のノード／バーテックスの一つで利用可能である）と、コア・サービス機能２４３（これはドメイン２４０内のノード／バーテックスの一つで利用可能である）とを含むサービス機能チェーンを指定する。
【００３７】
本稿で詳述するように、さまざまな実施形態において、SFC要求について要件を満たすサービス機能チェーン（SFC）解すべてを同定するためのバーテックス中心の分散式コンピューティングを実行するための本稿に記載されるシステムおよび方法は、ネットワーク機能仮想化、モバイル・エッジ・コンピューティングおよび／またはデータ解析（data  analytics）をもつIoTを含むシステムにおいて適用されてもよい。該システムでは、トラフィックは、複数のドメインを横断するサービス機能インスタンスのシーケンスを通過する。
【００３８】
本開示の少なくともいくつかの実施形態では、マルチドメイン・ネットワーク内の各ドメインは物理ノードおよびIP/OTNリンクを含みうる。少なくともいくつかの実施形態では、各ネットワーク・ドメインにそれぞれの資源オーケストレーターが関連付けられていてもよい。ドメイン内のすべての物理ノードおよびリンクを管理するためである。いくつかの実施形態では、各物理ノードは、サービス機能のカタログから選択されるサービス機能の部分集合を呼び出すことのできる、ネットワーク要素（たとえばOTNスイッチ、ルーター）および／または計算サーバーおよび記憶要素（たとえばデータ・センター）を含んでいてもよい。これらのマルチドメイン・ネットワークにおいて提供されるサービス機能のいくつかの例は、ファイアウォール、ディープ・パケット・インスペクション（DPI:  deep  packet  inspection）、ネットワーク・アドレス変換（NAT:  network  address  translation）、負荷均衡化器およびペアレンタル・コントロール機能を含む。一例では、サービス機能チェーンはファイアウォール、ディープ・パケット・インスペクション（DPI）サービス機能、ペアレンタル・コントロール・サービス機能およびアンチウイルス・サービス機能を含んでいてもよく、そのそれぞれは異なるネットワーク・ドメイン内のノードによって提供されてもよい。別の例では、サービス機能チェーンは、二つの他の型のサービス機能の間および／または他のサービス機能とインターネット・アクセス・サービス機能との間のネットワーク・アドレス変換（NAT）サービス機能を含んでいてもよく、そのそれぞれは異なるネットワーク・ドメイン内のノードによって提供されてもよい。
【００３９】
ここで図３を参照するに、複数の分散されたネットワーク・ドメインの選択された要素がネットワーク図として示されている。この例示的実施形態において、分散されたネットワーク・ドメインは、SFC要求を満たすための資源の使用が図１に示され本稿に記載されるようなそれぞれの複数の資源オーケストレーター１０８によって協調させられるマルチドメイン・ネットワーク３００の例示的実施形態を表わしている。マルチドメイン・ネットワーク３００内の分散されたネットワーク・ドメインは特定のネットワーク・トポロジーとして示されているが、ネットワークのさまざまな異なる型およびサイズならびにネットワーク・ドメインの異なる数が本稿に開示されるネットワーク・サービス計算システムと一緒に使用されてもよいことは理解されるであろう。マルチドメイン・ネットワーク３００内の分散されたネットワーク・ドメインは、概略図として示されており、縮尺通りに描かれていないことを注意しておく。
【００４０】
図３において、マルチドメイン・ネットワーク３００は、それぞれ個々のバーテックスからなる複数のドメイン１１０を含む。バーテックスは、他にもあるがスイッチ、ルーター、ネットワーク要素、データ・センター、サブネットワーク、サブドメインといった多様なネットワーク・ノードの任意のものを表わしうる。このように、各バーテックスは、たとえばネットワーク・サービスを提供し、ネットワーク・アプリケーションをサポートするために、他のバーテックスへのネットワーク接続性ならびに計算資源を提供することができるようにされていてもよい。図のように、バーテックス間に接続リンクが提供され、図３では接続リンクについての相対経路距離を表わす整数値でラベル付けされている。この相対経路距離は、他の実施形態では、バーテックス間の遅延または他のエッジ情報（たとえば帯域幅）を表わしていてもよい。接続リンクはドメイン内でもドメイン間でもありうることを注意しておく。
【００４１】
マルチドメイン・ネットワーク３００におけるバーテックスは、ソース・バーテックスSと宛先バーテックスDとの間の潜在的な経路を提供しうる、到達可能バーテックス・ネットワークを表わす。この例では、各ドメインはローカルなオーケストレーター１０８を有する。たとえば、資源オーケストレーター１０８−Ａは、ソース・バーテックスSおよびバーテックスＡ１、Ａ２、Ａ３を含むドメイン１１０−Ａ内の資源の使用を協調させてもよく；資源オーケストレーター１０８−Ｂは、バーテックスＢ１、Ｂ２、Ｂ３、Ｂ４、Ｂ５、Ｂ６、Ｂ７を含むドメイン１１０−Ｂ内の資源の使用を協調させてもよく；資源オーケストレーター１０８−Ｃは、バーテックスＣ１、Ｃ２、Ｃ３および宛先バーテックスDを含むドメイン１１０−Ｃ内の資源の使用を協調させてもよく；資源オーケストレーター１０８−Ｄは、バーテックスＤ１、Ｄ２、Ｄ３を含むドメイン１１０−Ｄ内の資源の使用を協調させてもよい。マルチドメイン・ネットワーク３００内に示される分散されたネットワーク・ドメインのいくつかの実施形態では、各資源オーケストレーター１０８（および／またはそのドメインについてのSDNコントローラ）は、それぞれの自分のドメイン１１０内のバーテックスと通信してもよく、それらのバーテックスは互いと通信することは控えてもよい。
【００４２】
いくつかの実施形態では、サービス機能チェーン形成要求を計算〔コンピュート〕するとき、各バーテックス（ノード）は、その近傍バーテックスへ／からコンピュート関数（compute  function）内部でメッセージを送受信してもよい。たとえば、バーテックス（ノード）A1は、通信できる三つの近傍バーテックスをもつので三つのエッジをもつとともに、共通のコンピュート関数をもつ。バーテックスA1は、たとえば当該ノード上で利用可能な計算資源の数、当該ノード上で利用可能な記憶資源の数、当該ノードについてのバーテックスIDおよび当該ノードで実装され、利用できるサービス機能を示すノード情報をも有していてもよい。少なくともいくつかの実施形態では、異なるドメインに関連付けられた資源オーケストレーターは、本稿に記載されるバーテックス中心の分散式処理に基づいて要求（たとえばサービス機能チェーン形成要求）を計算するための通信のために、制御チャネルを介して相互接続されてもよい。
【００４３】
少なくともいくつかの実施形態では、資源オーケストレーター（図１および図３に示される資源オーケストレーター１０８のさまざまなものなど）は互いと通信してもよく、他にもあるがメッシュ、リング、スターまたはバスといった任意の好適なトポロジーを使って一緒にネットワーク接続されてもよい。同様に、ドメインのためのSDNコントローラは互いと通信してもよく、他にもあるがメッシュ、リング、スターまたはバスといった任意の好適なトポロジーを使って一緒にネットワーク接続されてもよい。いくつかの実施形態では、資源オーケストレーター１０８の間および／またはSDNコントローラの間の通信は、サイドバンド・ネットワーク・チャネルまたは管理目的のための他のネットワーク接続であって、バーテックス間のネットワーク接続に干渉しないものを用いてもよい。該バーテックス間のネットワーク接続は、サービス・プロバイダーによって顧客に商業サービスとして提供されるペイロード・ネットワークを表わしうる。
【００４４】
少なくともいくつかの実施形態では、資源オーケストレーター（図１および図３に示される資源オーケストレーター１０８のさまざまなものなど）は、サービス機能チェーン要求を解くための分散式の計算についての最終結果を計算するために、互いに対してメッセージを送ってもよい。そのような実施形態では、各資源オーケストレーターは、自分自身のドメインの物理的インフラストラクチャーの論理表現を維持していてもよい。ここで、資源オーケストレーション・アーキテクチャ内のバーテックスはそのドメイン内の物理ノードを表わす。少なくともいくつかの実施形態では、バーテックス情報（上記のノード情報など）を維持することに加えて、各バーテックスは、はいってくるエッジおよび出て行くエッジについての情報ならびにユーザー定義される機能である共通のコンピュート関数をも維持してもよい。少なくともいくつかの実施形態では、オーケストレーター間の分散式のコンピューティングのために、計算はスーパーステップと称される反復工程に分解されてもよい。各スーパーステップにおいて、各オーケストレーターは、そのドメイン内の各バーテックスのコンピュート関数の実行を協調させうる。
【００４５】
図４は、図３に示した種々のドメインのそれぞれの資源オーケストレーターの間の通信チャネル（またはリンク）を含む分散式資源オーケストレーション・アーキテクチャ４００を示している。この例では、資源オーケストレーター１０８−Ａ（これはドメイン１１０−Ａ内の資源の使用を協調させる）と資源オーケストレーター１０８−Ｂ（これはドメイン１１０−Ｂ内の資源の使用を協調させる）との間のリンクはリンク４０６として示されている。同様に、資源オーケストレーター１０８−Ａと資源オーケストレーター１０８−Ｃ（これはドメイン１１０−Ｃ内の資源の使用を協調させる）との間のリンクはリンク４０４として示されている。資源オーケストレーター１０８−Ａと資源オーケストレーター１０８−Ｄ（これはドメイン１１０−Ｄ内の資源の使用を協調させる）との間のリンクはリンク４０２として示されている。資源オーケストレーター１０８−Ｂと資源オーケストレーター１０８−Ｄとの間のリンクはリンク４１０として示されている。資源オーケストレーター１０８−Ｃと資源オーケストレーター１０８−Ｄとの間のリンクはリンク４０８として示されている。資源オーケストレーター１０８−Ｂと資源オーケストレーター１０８−Ｃとの間のリンクはリンク４１２として示されている。
【００４６】
図３および図４に示した例では、四つのネットワーク・ドメインがあり、各ネットワーク・ドメインは、複数の物理ノードおよび光転送ネットワーク（OTN）オーバーレイ・リンクを含んでいてもよい。各物理ノードは、一つまたは複数の仮想マシンを含み、一組のサービス機能を呼び出すことのできるスイッチ、ルーターまたはデータ・センターであってもよい。たとえば、各物理ノードは、ファイアウォール、ディープ・パケット・インスペクション（DPI）、WAN最適化コントローラ（WOC:  WAN  optimization  controller）、顧客構内設備（CPE:  customer  premises  equipment）、プロバイダー・エッジ（PE:  provider  edge）または一般に任意の型のサービス機能を提供することができてもよい。
【００４７】
本開示のさまざまな実施形態において、マルチドメイン・ネットワークにおいて要件を満たすSFCをすべて見出すために、分散式資源オーケストレーション・フレームワークおよびバーテックス中心の分散式アルゴリズムが用いられてもよい。いくつかの実施形態では、要件を満たすチェーンすべてを同定したのち、任意の好適な基準に基づいて、一つまたは複数のSFCが実行のために選択されてもよい。たとえば、資源使用のためのユーザー選好または他のポリシー決定を最もよく反映するSFCが、実行のために選択されてもよい。別の例では、最低コストの、共通部分をもたないSFCが選択されてもよい（たとえば、保護の懸念に対処するために）。さらに別の例では、ユーザー選好または適用可能なSFC選択ポリシーに従って複数の並列SFCが実行のために選択されてもよい。
【００４８】
少なくともいくつかの実施形態では、SFC要求は、下記の要求要素を指定する情報を含んでいてもよい：実行されるべきサービス機能、それらのサービス機能を実行するために必要とされる資源（たとえば、仮想マシンおよび／または記憶資源の必要数）およびチェーン内の種々のサービス機能が実行されるノードの間のリンクについての遅延もしくは帯域幅要求。
【００４９】
図５は、ある実施形態に基づく、例示的なSFC要求５００の抽象化を描いている。この例では、SFC要求５００を満たすために、分散式資源オーケストレーション機構は、n1個の仮想マシン（VM）を含み、第一のサービス機能f1を実行できる第一のノード５０２；n2個の仮想マシン（VM）を含み、第二のサービス機能f2を実行できる第二のノード５０４；およびn3個の仮想マシン（VM）を含み、第三のサービス機能f3を実行できる第三のノード５０６を同定する必要があることがある。加えて、分散式資源オーケストレーション機構は、ノード５０２とノード５０４の間のリンクが第一の組の帯域幅および／または遅延要求５０８（たとえばBW1および／またはdelay1）を満たすことおよびノード５０４とノード５０６の間のリンクが第二の組の帯域幅および／または遅延要求５１０（たとえばBW2および／またはdelay2）を満たすことを検証する必要があることがある。
【００５０】
他の型の仮想ネットワーク要求とは対照的に、SFC要求は二つの独特な特徴を含みうる：場合によって、SFC要求はトポロジーにおいてより線形であってもよく、サービス機能が実行される順序の点でより柔軟であってもよい。SFC要求のこれらの特徴に基づき、本稿に記載される分散式アルゴリズムは、マルチドメイン・ネットワークにおけるサービス機能チェーン形成を解くために、バーテックス中心の分散式コンピューティング手法を適用してもよい。いくつかの実施形態では、SFC内の複数のサービス機能が単一の物理ノードにマッピングされることができる。
【００５１】
図６のＡおよびＢは、柔軟な順序のサービス機能チェーンf1*f2*f3（図６のＡに示される）を指定するSFC要求と、もしみつかるならいずれもこの要求を満たすはずの六つの可能な固定順序のチェーンとの間の例示的なマッピングを示している。これら六つの固定順序のチェーンは図６のＢにおいて、f1・f2・f3、f1・f3・f2、f2・f1・f3、f2・f3・f1、f3・f1・f2、f3・f2・f1として示されている。これらの図において、機能間の記号「*」は柔軟な順序付けを表わし、機能間の記号「・」は固定した順序を表わす。
【００５２】
先述したように、さまざまな実施形態において、バーテックス中心の分散式の処理手法は、逐次的に実行されるスーパーステップの反復工程を実行することを含んでいてもよい。各スーパーステップは、一つまたは複数の資源オーケストレーター（図１、図３または図４に示される資源オーケストレーター１０８のさまざまなものなど）またはSDNコントローラにおいてコントローラ・メッセージまたは情報を受領すること、それぞれのネットワーク・ドメイン１１０においてローカル・アクションを実行すること（この場合、共通のコンピュート関数を実行すること）、次いで他の資源オーケストレーター１０８またはSDNコントローラにコントローラ・メッセージを送り出すことを含んでいてもよい。バーテックス中心の分散式処理手法は、図２、図３および図４に示されるような分散されたネットワーク・ドメインを使う好適なネットワーク・オペレーティング・システムとともに用いられてもよいことを注意しておく。いくつかの実施形態では、各ネットワーク・ドメイン１１０についての資源オーケストレーター１０８またはSDNコントローラは、それぞれのネットワーク・ドメイン１１０のネットワーク・トポロジーを追跡してもよい。
【００５３】
いくつかの実施形態では、コントローラ・メッセージは、異なるドメインにある送り側バーテックスおよび目標バーテックスに関して送られるドメイン間メッセージであってもよい。いくつかの実施形態では、各コントローラ・メッセージは：送り側バーテックス識別子；目標バーテックス識別子およびソース・バーテックスSから目標バーテックスまでの最小距離を含んでいてもよい。さまざまな実施形態において、異なる数のスーパーステップが可能なSFC解すべての同定につながることがありうる。
【００５４】
先述したように、いくつかの実施形態では、各ネットワーク・ドメインは、そのドメイン内の物理ノードおよびリンクを管理する（そしてその使用を協調させる）それぞれの資源オーケストレーターを含んでいてもよい（または該資源オーケストレーターに関連付けられていてもよい）。これらの分散された資源オーケストレーターは、制御チャネル（たとえば、種々の実施形態において帯域内制御チャネルまたは帯域外制御チャネル）によって相互接続されてもよい。少なくともいくつかの実施形態では、各オーケストレーターは、各物理ノードについての情報を「バーテックス」データ構造として記憶してもよく、各オーバーレイOTNリンクについての情報を「エッジ」データ構造として記憶してもよい。少なくともいくつかの実施形態では、各バーテックス・データ構造は現在の値、はいってくる／出て行くエッジの集合およびユーザー定義された機能であってもよい共通のcompute()関数（その例示的実施形態は後述する擬似コードによって示される）を含んでいてもよい。少なくともいくつかの実施形態では、各エッジ・データ構造は、帯域幅、遅延情報、リンクを使うためのコストについての情報および／またはシステムにおいて使用可能な他の任意の情報といった、それぞれのOTNリンクについての情報を含んでいてもよい。いくつかの実施形態では、各バーテックスは、他のバーテックスにメッセージを送るおよび／または他のバーテックスからメッセージを受け取ることができてもよい。メッセージはメモリ内で送達されてもよく（たとえば、同じネットワーク・ドメイン内にあるまたは同じオーケストレーターによって制御されるバーテックス間で交換される場合）、一方、異なるネットワーク・ドメインにあるまたは異なるオーケストレーターによって制御されるバーテックス間で交換されるメッセージはさまざまな制御チャネルを介して送達されてもよい。
【００５５】
〈分散式サービス機能チェーン形成のアルゴリズム〉
本稿に記載される分散式資源オーケストレーション・フレームワークの少なくともいくつかの実施形態では、グローバルなネットワーク・トポロジーやグローバルなノード情報は利用可能ではないことがある。その代わり、各オーケストレーターは、グローバルなネットワーク・トポロジーのパーティションへのアクセスをもつだけであることがある。そのような実施形態では、SFC要求についての一つまたは複数の候補解を同定するために、各計算がスーパーステップと呼ばれる反復工程に分解される、バーテックス中心の分散式プロセスが採用されてもよい。そのような実施形態では、各スーパーステップにおいて、各バーテックスのcompute()関数が一度実行されてもよい。たとえば、いくつかの実施形態では、SFC要求が到着すると、ソース・オーケストレーターは該SFC要求をすべての参加オーケストレーターに送ってもよく、各スーパーステップにおいてcompute()関数を実行するためにすべてのオーケストレーターを協調させてもよい。各スーパーステップの間に、これらのコンピュート関数は異なるドメインにおけるバーテックス（ノード）で実質的に並列に実行されてもよいが、各スーパーステップの終わりには互いと同期してもよい。たとえば、次のスーパーステップに進む前に、資源オーケストレーターは、現在のスーパーステップについてのメッセージ交換が終わっていることならびに全バーテックスが、制御チャネルを通じて他のバーテックスから受信することになっているコントローラ・メッセージを受信したことを確かめてもよい。
【００５６】
ひとたびバーテックスにおいてSFC要求に対する要件を満たす解が見出されたら、その解は資源オーケストレーターに送られてもよい。分散式コンピューティングは、オーケストレーター間で交換されるさらなるメッセージがないときに停止してもよい。いくつかの実施形態では、参加オーケストレーターから要件を満たすSFC解すべてを取得したのち、ソース・オーケストレーターは、さまざまなユーザー選好および／または適用可能な資源使用ポリシーに基づいて、実行のために、最適なマルチドメインSFC解を選択してもよく、関連する諸オーケストレーター（たとえば、要求されたSFCを実行するように選択された諸資源を管理するもの）に、それらのオーケストレーターが自分のドメイン内の物理ノードをしかるべく（たとえばSFCのさまざまな機能を実行するために必要とされるように）構成するべきであることを通知してもよい。先述したように、（たとえばさまざまなユーザー選好および／または適用可能な資源使用ポリシーに依存して）いくつかの実施形態では、ソース・オーケストレーターは、可能なSFC解のうちの二つ以上を並列実行のために選択してもよい。そのような実施形態では、ソース・オーケストレーターは、選択されたSFC解に関連する全オーケストレーターに、SFCの機能のうち特定のものを実行するために自分のドメイン内の物理ノードを構成するべきであることを通知してもよい。
【００５７】
いくつかの実施形態では、バーテックス（ノード）およびエッジ（ノード間のリンク）を含むマルチドメイン・ネットワーク・トポロジー（物理的なインフラストラクチャーのトポロジー）を与えられ、一組のサービス機能および各バーテックスにおいて利用可能な計算および／または記憶資源の数を与えられ、各エッジにおける遅延および帯域幅を与えられて、分散式サービス機能チェーン形成を提供することは、SFC要求についてのすべての可能な解を同定することを含んでいてもよい。先述したように、各SFC要求は、サービス機能のシーケンスを指定していてもよい。各サービス機能は、ある数の計算および／または記憶資源（たとえば仮想マシン）を使ってもよく、出て行くトラフィックのためにある量の帯域幅を必要としてもよい（あるいは、遅延に対する上限があってもよい）。いくつかの実施形態では、SFC要求についてすべての実現可能なマッピング解を同定したのち、解は、さまざまなポリシー、要求またはサービス・プロバイダーもしくはサービスの要求者によって課される制約条件に従って枝刈りされてもよい。たとえば、解は、最低の全コストまたは最低の全遅延をもつ解、共通部分をもたない複数のチェーンを含む解の部分集合、双方向チェーンを含む（または含まない）または複数の異なる制約条件を満たす解のみを含むよう枝刈りされてもよい。いくつかの実施形態では、解は、チェーン内のサービス機能にマッピングされているノード上での現在の負荷に基づいてマッピング解を選択する負荷均衡化器によって枝刈りされてもよい。いくつかの実施形態では、SFC要求についての解（または解の集合）の計算は、非決定論的多項式時間困難な（NP困難な）問題であることがある。いくつかの場合には、より複雑なSFC要求（たとえばメッシュ要求）が複数の逐次的なSFC要求に分割されてもよく、結果はその後、これらの要求を満たすために改めてマージされてもよい。
【００５８】
本開示の少なくともいくつかの実施形態では、マルチドメイン・ネットワークにおけるサービス機能チェーン形成を解くためのバーテックス中心の分散式コンピューティング手法について、バーテックス値データ構造およびコントローラ・メッセージ・フォーマットが定義されてもよい。このバーテックス・データ構造およびメッセージ・フォーマットは、この特定の分散式コンピューティング問題について固有であってもよいことを注意しておく。下記の表１は、少なくとも一つの実施形態に基づく、このコンテキストにおいて使うための、例示的なバーテックス値データ構造を示している。
【表１】
0006733486.tif 000002
【００５９】
この例において、バーテックス値データ構造は、バーテックス識別子、バーテックスにおいて利用可能なサービス機能の集合およびバーテックスにおいて利用可能な資源（これは計算および／または記憶資源を含んでいてもよい）の集合を含む。いくつかの実施形態では、バーテックスにおいて利用可能なサービス機能の集合は、マルチドメイン・ネットワークにおいてサポートされているサービス機能の部分集合であってもよく、あるいは（たとえばサービス機能の一部がSFC要求解に含めるために現在利用でない場合）バーテックスにおいて実装されているサービス機能の部分集合であってもよい。下記の表２は、少なくとも一つの実施形態に基づく、このコンテキストにおいて使うための、例示的なコントローラ・メッセージ・フォーマットを示している。
【表２】
0006733486.tif 000003
【００６０】
この例において、マルチドメイン・ネットワークにおけるSFC要求に対する解を同定するためのバーテックス中心の分散式計算の一部として交換される各メッセージは、SFC要求の識別子と、現在のSFCチェーン（これは、種々のコントローラ・メッセージにおいて、部分的にマッピングされたチェーンまたは完成されたチェーンでありうる）とを含んでいてもよい。
【００６１】
少なくともいくつかの実施形態では、所与のSFC要求について可能なすべてのSFC解を同定するために適用されるバーテックス中心の分散式SFCアルゴリズムは、三つの主要なコンポーネントを含んでいてもよい：バーテックス値、メッセージ・フォーマットおよびcompute()関数である。その例はそれぞれ上記の表１、表２および下記の擬似コードに示される。メッセージ・フォーマットの例を記述する表２に示されるように、現在のチェーンは、<バーテックスID、次バーテックスID、エッジ情報>の形の要素のシーケンスを含んでいてもよい。各要素が対応する機能にマッピングされていてもよい特定のバーテックスIDをもつバーテックスを表わす。これらの要素において、空の括弧（<>として示される）は、対応する機能がまだバーテックスにマッピングされていないことを示してもよい。少なくともいくつかの実施形態では、バーテックスおよびその対応する機能は、チェーンにおいて同じ順序を維持する必要がある。シーケンスの各要素における次バーテックスIDの指示は、チェーン内のマッピングされたバーテックスを順序付けるために使われてもよい。
【００６２】
いくつかの実施形態では、所与のバーテックスについてのバーテックスIDの値は、そのローカルな資源オーケストレーターによって割り当てられてもよく、そのドメイン内で一意的であってもよい。いくつかの実施形態では、異なるドメインにおけるバーテックスの間の区別をするために、バーテックスIDはドメインまたはその資源オーケストレーターの識別子を含んでいてもよい。他の実施形態では、バーテックス間で交換されるコントローラ・メッセージ内において、バーテックスIDは、ドメインまたはその資源オーケストレーターの識別子により補強されてもよい。いくつかの実施形態では、SFC要求識別子の値は、SFC要求が受領されるときまたはソース資源オーケストレーターがSFC要求を含むコントローラ・メッセージをマルチドメイン・ネットワーク内の他の資源オーケストレーターに送るときに、ソース資源オーケストレーターによって割り当てられてもよい。
【００６３】
バーテックス中心の分散式サービス機能チェーン形成アルゴリズムにおいてさまざまなバーテックス（ノード）において実行されるcompute()関数の一つの例示的な実施形態が、下記の擬似コードによって例解される。この例において、コンピュート関数〔compute関数〕は、最初のスーパーステップ（スーパーステップ0）の間に、一つまたは複数のその後のスーパーステップの間に実行されない動作を実行する。
compute()
if(superstep==0  &&  vertx.isQualified()){
各近傍について{
if(edge.isQualified()){
そのバーテックスが機能にマッピングされたチェーンを生成；
そのチェーンを近傍に送る；}}}
受領された各メッセージについて{
if(vertex.isQualified()){
if(チェーン内のすべての機能がマッピングされている){
完成されたチェーンをソース・オーケストレーターに送る；}
else{
各近傍について{
前記チェーンにおいてそのバーテックスが機能にマッピングされたものを生成；
そのチェーンを近傍に送る；}}}
。
【００６４】
上記で例解した例示的実施形態において、コンピュート関数は、該コンピュート関数が実行される特定のバーテックスが要件を満たすバーテックスであるか否かを判定するためにvertex.isQualified()メソッドをコールする（または他の仕方で呼び出す）ことができる。この例示的実施形態において、その特定のバーテックスの各近傍バーテックスについて、コンピュート関数は、該コンピュート関数が実行されるその特定のバーテックスとその近傍バーテックスの一つとの間のリンクが要件を満たすリンクであるか否かを判定するためにedge.isQualified()メソッドをコールする（または他の仕方で呼び出す）こともしてもよい。近傍バーテックスの一つまたは複数について、これら両方のメソッドが真を返す場合には、現在のバーテックスは（自らをチェーン内のサービスにマッピングし、近傍バーテックスへのリンクを含めることによって）チェーンを延長してもよく、延長されたチェーンを、コントローラ・メッセージにおいてその近傍バーテックスに送ってもよい。この例では、vertex.isQualified()メソッドが偽を返す場合、vertex.isQualified()メソッドは近傍バーテックスのどれについてもコールされなくてもよい。この例において、vertex.isQualified()メソッドが真を返す場合、現在のチェーンは延長されてもよく、コントローラ・メッセージは、現在のバーテックスが要件を満たす接続をもつ（edge.isQualified()メソッドが真を返す）近傍バーテックスにのみ送られてもよい。少なくともいくつかの実施形態では、スーパーステップ0の間に要件を満たすバーテックスがみつからない場合には、分散式計算はいかなる実現可能な解も返すことなく停止してもよい。同様に、その後のスーパーステップの間に、要件を満たすバーテックスによって生成された部分的にマッピングされたチェーンのどれも完成されることができない場合には、分散式計算はいかなる実現可能な解も返すことなく停止してもよい。
【００６５】
さまざまな実施形態において、メソッドvertex.isQualified()は、コンピュート関数が実行される特定のバーテックスが要件を満たすバーテックスであるか否かを判定するために一つまたは複数の他のメソッドをコールしてもよい。一例では、メソッドvertex.isQualified()は、現在のバーテックスが要求されたサービス機能チェーンを開始、延長または完成できる所与のサービス機能を実行できるか否かを判定するメソッドvertex.hasFunction()をコールしてもよい。もう一つの例では、メソッドvertex.isQualified()は、現在のバーテックスが所与のサービス機能を実行するために利用可能な十分なキャパシティーをもつか否か（たとえば、所与のサービス機能を実装するために必要とされる計算および／または記憶資源が現在のバーテックスにおいて利用可能であるか否か）を判定するメソッドvertex.hasResource()をコールしてもよい。さらにもう一つの例では、メソッドvertex.isQualifid()は、より特定的に、現在のバーテックスが所与のサービス機能を実装するための十分な利用可能なVMを含むか否かを判定するメソッドvertex.hasVMs()をコールしてもよい。種々の実施形態において、コンピュート関数が実行される特定のバーテックスに要件を満たさせる一環としてさらに他のメソッドがコールされてもよい。いくつかの実施形態においては、vertex.isQualified()メソッドが真を返すためには、vertex.hasFunction()メソッドおよびバーテックスにおいて必要とされる資源が利用可能であるか否かを判定する別のメソッド（vertex.hasResource()メソッドまたはvertex.hasVMs()メソッドなど）の両方が真を返す必要があってもよい。
【００６６】
同様に、いくつかの実施形態では、メソッドedge.isQualified()は、コンピュート関数が実行される特定のバーテックスとその近傍バーテックスの一つとの間のリンクが要件を満たすリンクであるか否かを判定するために、一つまたは複数の他のメソッドをコールしてもよい。一例では、メソッドedge.isQualified()は、コンピュート関数が実行される特定のバーテックスとその近傍バーテックスとの間のリンクが、チェーンをその近傍バーテックスまで延長するために十分な帯域幅をもつか否かを判定するメソッドedge.hasBW()をコールしてもよい。もう一つの例では、メソッドedge.isQualified()は、コンピュート関数が実行される特定のバーテックスとその近傍バーテックスとの間のリンクを通じた遅延が、チェーンをその近傍バーテックスまで延長するための遅延要件を満たすか否か（たとえば、該リンクが要求されたSFCについて指定されている受け入れ可能な範囲内の遅延をもつこと）を判定するメソッドedge.delayOK()をコールしてもよい。種々の実施形態において、コンピュート関数が実行される特定のバーテックスとその近傍の一つとの間のリンクに要件を満たさせることの一環として、さらに他のメソッドがコールされてもよい。いくつかの実施形態では、メソッドedge.isQualified()は、二つ以上のメソッドをコールしてもよく、edge.isQualified()メソッドが真を返すためにはそのすべてが真を返さなければならないのでもよい。
【００６７】
図７Ａおよび７Ｂは、上記のようなcompute()関数を実行するための例示的方法の選択された要素を示す図である。より具体的には、図７Ａは、ある実施形態に基づく、コンピュート関数のスーパーステップ0を実行するための方法７００の選択された要素を示している。この例示的実施形態において、スーパーステップ0において、それぞれの要件を満たすバーテックスは、それぞれの潜在的に要件を満たす近傍（前記要件を満たすバーテックスへの要件を満たすリンクをもち、要求されたサービス機能チェーン内の次のサービス機能を含んでもいることができる近傍）にメッセージを送る。この例示的実施形態では、方法は（７０２において）各ネットワーク・ドメインにおける資源オーケストレーターが、所与のサービス機能チェーンを構築することを開始する何らかの要件を満たすバーテックスを同定することを含む。たとえば、あるドメインにおけるソース資源オーケストレーターが、SFC要求を含むコントローラ・メッセージを、一つまたは複数の他のドメインについてのそれぞれの資源オーケストレーターに送ってもよい。その各資源オーケストレーターは、そのドメインにおいて、要求されたサービス機能チェーン内の最初のサービス機能を含む何らかのバーテックス（ノード）を同定してもよい。要件を満たすバーテックスとして同定された各バーテックスは、それぞれの部分的にマッピングされたサービス機能チェーンにおいて最初のサービス機能にマッピングされてもよい。
【００６８】
この例示的実施形態では、本方法は（７０４において）、所与のバーテックスとその近傍との間の要件を満たすリンク（要求されたサービス機能チェーンのための帯域幅および／または遅延要件を満たす物理的インフラストラクチャー内のリンク）があるかどうかを判定することを含む。もしなければ、本方法は、同定された要件を満たすバーテックスを含む部分的にマッピングされたサービス機能チェーンを破棄することを含んでいてもよい（７０６のように）。（７０４において）所与のバーテックスとその近傍との間の要件を満たすリンクが一つまたは複数ある場合には、本方法は（７０８において）、同定された要件を満たすバーテックスの一つが、スーパーステップ0をもって共通のコンピュート関数の実行を開始することを含む。スーパーステップ0は、前記要件を満たすバーテックスから近傍までの任意の要件を満たすリンクについて、前記要件を満たすバーテックスをチェーン内の最初のサービス機能にマッピングし、前記近傍への前記要件を満たすリンクを含む部分的にマッピングされたチェーンを生成することを含む。いくつかの実施形態では（たとえば、要件を満たすリンクが前記要件を満たすバーテックスとは異なるドメインにあるとき）、本方法は、（７１０において）現在のドメインについての資源オーケストレーターが、前記部分的にマッピングされたチェーン（単数または複数）を含むコントロール・メッセージを、前記バーテックスが要件を満たすリンクをもつ近傍（単数または複数）についてのオーケストレーター（単数または複数）に送ることをも含んでいてもよい。その後、スーパーステップ0はこの初期に同定された要件を満たすバーテックスについては完了となる（７１２のように）。要件を満たすリンクをもつ近傍が前記要件を満たすバーテックスと同じドメインにあるいくつかの実施形態では、ドメイン・コントローラは、他のいかなるオーケストレーターにもコントロール・メッセージを送らなくてもよく、その近傍についての次のスーパーステップを自分で処理してもよい。要件を満たすリンクをもつ近傍が前記要件を満たすバーテックスと同じドメインにある他の実施形態では、メモリへの書き込みおよびメモリからの読み出しを通じて二つのバーテックスの間でメッセージが交換されてもよい。
【００６９】
この例示的実施形態において、（７１４に示されるように）（ステップ７０２において）初期に同定された要件を満たすバーテックスがもっとあったら、初期に要件を満たすと同定されたバーテックスのうち追加的な各バーテックスについて、７０４〜７１２に示される動作が適宜繰り返されてもよい。（７１４において）処理すべき、初期に同定された要件を満たすバーテックスがそれ以上ない場合またはそれ以上なくなったら、スーパーステップ0はこのサービス機能チェーン要求については完了となってもよい（７１６のように）。図７Ａは７０４〜７１２に示される動作が、初期に同定された各要件を満たすバーテックスについて直列に実行される実施形態を示しているが、本開示の少なくともいくつかの実施形態では、これらの動作は初期に同定された各要件を満たすバーテックスについて実質的に並列に実行されてもよいことを注意しておく。
【００７０】
図７Ｂは、ある実施形態に基づく、上記のコンピュート関数の、スーパーステップ0以外のスーパーステップを実行する方法７２０の選択された要素を示している。より具体的には、図７Ｂは、SFC要求についての部分的にマッピングされたSFC（これは所与のバーテックス上のサービス機能によって延長または完了されることができてもできなくてもよい）を含むコントローラ・メッセージを受領する一つのバーテックス上で行なわれるアクションを示している。この例示的実施形態では、本方法は（７２２において）一つまたは複数のそのようなコントローラ・メッセージを受領した所与のバーテックスが、スーパーステップ0以外のスーパーステップについて（たとえば、コントローラ・メッセージが所与のバーテックスに送られたスーパーステップに続くスーパーステップについて）コンピュート関数の実行を開始することを含む。本方法は（７２４において）、受領されたコントローラ・メッセージが、所与のバーテックスにおいて利用可能なサービス機能によって延長される（または完了される）ことができる部分的にマッピングされたサービス機能チェーンを含むかどうかを判定することを含む。受領されたコントローラ・メッセージが、所与のバーテックスにおいて利用可能なサービス機能によって延長されることができない（ましてや完了されることができない）部分的にマッピングされたサービス機能チェーンを含むと判定される場合、方法は、（７２６のように）受領されたメッセージに含まれていた部分的にマッピングされたSFCを破棄することを含む。
【００７１】
（７２４において）前記受領されたコントローラ・メッセージが所与のバーテックスにおいて利用可能なサービス機能によって延長されることができる部分的にマッピングされたサービス機能チェーンを含むと判定される場合、本方法は（７２８において）所与のバーテックスが自らをチェーン内の次の機能にマッピングすることを含む。本方法はまた（７３０において）、該所与のバーテックスのチェーン内の次の機能へのマッピングが、要求されたサービス機能チェーンを完成させるかどうかを判定することをも含む。もしそうであれば、マッピングはこの候補SFCについては完了され、本方法は、所与のバーテックスが存在するドメインについてのオーケストレーターが完了したチェーンをソース資源オーケストレーターに送る（７３２のように）ことを含む。
【００７２】
（７３０において）該所与のバーテックスのチェーン内の次の機能へのマッピングによって、受領されたコントローラ・メッセージ内の部分的にマッピングされたSFCが完成されないと判定される場合には、本方法は、SFC要求について潜在的な候補解を同定しようとする試みを継続することを含んでいてもよい。図７Ｂに示される例示的実施形態では、これは（７３４において）、所与のバーテックスとその近傍との間に要件を満たすリンク（要求されたサービス機能チェーンについて帯域幅および／または遅延要求を満たす物理的インフラストラクチャー内のリンク）があるか否かを判定することを含んでいてもよい。もしなければ、本方法は、（７３６のように）同定された要件を満たすバーテックスを含む部分的にマッピングされたサービス機能チェーンを破棄することを含む。（７３４において）所与のバーテックスとその近傍との間に要件を満たすリンクが一つまたは複数みつかった場合（そして要件を満たすリンクをもつ近傍のいずれかが所与のバーテックスとは異なるドメインにある場合）には、本方法は、所与のバーテックスについての資源オーケストレーターが、延長されたSFCをもつそれぞれのコントロール・メッセージを、その所与のバーテックスが要件を満たすリンク（単数または複数）を通じて通信する他のドメイン内の近傍（単数または複数）のそれぞれについてのオーケストレーターに送ることを含む。要件を満たすリンクをもつ近傍が所与のバーテックスと同じドメインにあるいくつかの実施形態では、ドメイン・コントローラは他のいかなるオーケストレーターにもコントロール・メッセージを送らなくてもよく、その近傍についての次のスーパーステップを自分で処理してもよい。要件を満たすリンクをもつ近傍が所与のバーテックスと同じドメインにある他の実施形態では、メモリへの書き込みおよびメモリからの読み出しを通じて二つのバーテックスの間でメッセージが交換されてもよい。
【００７３】
（７４０に示されるように）SFC要求に関係したさらなるコントローラ・メッセージが所与のバーテックスによって受領されていた場合には、受領された追加的な各メッセージについて、７２４〜７３８に示される動作が適宜繰り返されてもよい。（７４０において）処理すべき、さらなる受領されたメッセージがない場合、このスーパーステップは所与のバーテックスについては完了となる（７４２に示されるように）。
【００７４】
上記の例示的実施形態では、スーパーステップ0以外の各スーパーステップの間に、図７Ｂに示される動作が、前のスーパーステップにおいて資源オーケストレーターからコントローラ・メッセージを受領した各バーテックスについて繰り返される。少なくともいくつかの実施形態では、各スーパーステップの間に、図７Ｂに示される動作は、前のスーパーステップにおいて資源オーケストレーターからコントローラ・メッセージを受領した各バーテックスについて実質的に並列に実行されてもよい。先述したように、サービス機能チェーン要求に応答してコンピュート関数によって実行されるスーパーステップの総数は、要求されるサービス機能チェーンに含まれるサービス機能の数に等しくてもよい。
【００７５】
図７Ａおよび７Ｂに示される例では、スーパーステップ0の間に、SFC要求内の最初のサービス機能が実行できる何らかのバーテックス（ノード）を同定し、部分的にマッピングされたチェーンを、要件を満たすリンクをもつその近傍バーテックス（ノード）に送るようコンピュート関数が実行される。スーパーステップ1の間には、SFC要求内の第二のサービス機能が実行されることのできる近傍バーテックス（ノード）のいずれかを同定し、それらの近傍バーテックス（ノード）への要件を満たすリンクがあれば、延長された部分的にマッピングされたチェーンをその近傍（すなわち、近傍の近傍）に送るよう、コンピュート関数が実行される。スーパーステップ2の間には、前記近傍の近傍がSFC要求内の第三のサービス機能についてのマッピングを加えることによってチェーンを完了させることができるかどうかを判定し、完成されたチェーンがあればそれをソース資源要求者に返すためにコンピュート関数が実行される。この例は、少なくともいくつかの実施形態では、スーパーステップの数がSFC要求内のサービス機能の数に等しいであろうことを示す。このことは、この手法のスケーラビリティーを示す。
【００７６】
いくつかの実施形態では、特定のスーパーステップにおいて一対の資源オーケストレーターの間で交換されるメッセージが組み合わされてもよい。しかしながら、少なくともいくつかの実施形態では、分散式コンピューティングの間（たとえば、SFCの機能または他の型の分散式の動作または計算を実行するとき）、物理ノードは互いと通信しなくてもよい。
【００７７】
図８Ａ〜８Ｊは、ある実施形態に基づく、サービス機能チェーン要求に対する一つまたは複数の候補解を生成するための、バーテックス中心の分散式コンピューティングの例を示している。より具体的には、これらの図は、要求ID＝1をもつ固定順序のSFC要求f1・f2・f3について、バーテックス中心の分散式コンピューティングの例を描いている。この例において、図８Ａは、それぞれドメイン８１０、８２０、８３０、８４０として示される四つのドメイン（A、B、C、D）を含むマルチドメイン・ネットワーク８００を呈示している。この例では、各ドメインは単一のノード（それぞれA1  ８１２、B1  ８２２、C1  ８３２、D1  ８４３）を含み、各ノードは、マルチドメイン・ネットワーク内のすべての利用可能なサービス機能の部分集合であるサービス機能の集合をもつ。この例では、ドメインA（８１０）内のノードA1（８１２）はサービス機能f1およびf2を含み、ドメインB（８２０）内のノードB1（８２２）はサービス機能f2およびf3を含み、ドメインC（８３０）内のノードC（８３２）はサービス機能f3を含み、ドメインD（８４０）内のノードD1（８４２）はサービス機能f1を含む。
【００７８】
この例では、サービス機能要求は固定した順序のチェーンf1・f2・f3を求めている。ノードのすべてが要求されたサービス機能チェーンに含まれるサービス機能の全部を含むわけではないが、この例では（図示の簡単のため）、ノード（バーテックス）およびエッジ（リンク）のすべてが、要求されるサービス機能チェーンについての他の要件を満たすための要求を満たしていると想定される。より具体的には、サポートされるサービス機能のそれぞれについて要求される計算および／または記憶資源の数が、各ノード（バーテックス）で利用可能であり、帯域幅および遅延要求が、サービス機能チェーン要求についての候補解の一部としてマッピングされるべきサービス機能を含む隣接するノードの間のエッジ（リンク）のすべてについて満たされていると想定される。たとえば、ドメインA  ８１０およびD  ８４０、ドメインD  ８４０およびC  ８３０、ドメインC  ８３０およびB  ８２０ならびにドメインA  ８１０およびB  ８２０における隣接するノード（およびサービス機能）の間の遅延の全部が1であると想定される。
【００７９】
図８Ｂ〜８Ｊは、分散式資源オーケストレーション・アーキテクチャ８５０上でのバーテックス中心の分散式コンピューティングの動作を示している。分散式資源オーケストレーション・アーキテクチャ８５０は、図８Ａに示されるドメインA  ８１０、B  ８２０、C  ８３０、D  ８４０のそれぞれの資源オーケストレーターの間でコントローラ・メッセージが交換される通信チャネル（またはリンク）を含む。これらの資源オーケストレーターは、それぞれ資源オーケストレーターA（８０２−A）、資源オーケストレーターB（８０２−B）、資源オーケストレーターC（８０２−C）、資源オーケストレーターD（８０２−D）として示されている。この例において、SFC要求８０５は資源オーケストレーターA（８０２−A）に提出される。この資源オーケストレーターは、ソース・オーケストレーターであってもよい（またはソース・オーケストレーターとしてはたらいてもよい）。ソース・オーケストレーターとは、マルチドメイン・ネットワークにおけるマスター・ドメインについての資源オーケストレーターであってもよい。ソース・オーケストレーターとして、資源オーケストレーターA（８０２−A）はSFC要求８０５を、分散式資源オーケストレーション・アーキテクチャ８５０内の他の三つの資源オーケストレーターに転送する。このことは、資源オーケストレーターA（８０２−A）から資源オーケストレーターD（８０２−D）への太い矢印８０４、資源オーケストレーターA（８０２−A）から資源オーケストレーターC（８０２−C）への太い矢印８０６、資源オーケストレーターA（８０２−A）から資源オーケストレーターB（８０２−B）への太い矢印８０８によって示されている。次いで、各資源オーケストレーターは、SFC要求８０５について候補解を構築しはじめる何らかの要件を満たすバーテックスを同定してもよい。たとえば、SFC要求８０５は固定した順序のチェーンを含むので、各資源オーケストレーターは、それぞれのドメイン内において、SFC要求８０５内の最初の機能（すなわち、サービス機能f1）を含む何らかのバーテックスを同定してもよい。この例では、初期に同定された要件を満たすバーテックスは、ノードA1（８１０）およびノードD1（８４０）を含む。この例では、ノードA1およびD1は、サービス機能f1を実行するための十分な資源をもつと想定されており、よってこれらは要件を満たすノードであることを注意しておく。
【００８０】
この例において、スーパーステップ0の間に、最初の機能f1をもつとして同定された各バーテックス（ノード）、この場合ノードA1（８１０）およびD1（８４０）は、上述したようなコンピュート関数の一部を実行する。この場合、その各近傍について、これらのバーテックスのそれぞれは、そのバーテックス自身がチェーン内の最初の機能にマッピングされている、部分的にマッピングされたSFCを生成する。部分的にマッピングされたSFCは、近傍への要件を満たすリンクを含む。バーテックスが存在するドメインについての資源オーケストレーターは、次いで、部分的にマッピングされたSFCのうちの一つを含む適切なコントローラ・メッセージを、それらの近傍のそれぞれに送る。たとえば、図８Ｃは、ドメインA（８１０）内のノードA1（８１２）はサービス機能f1（これは要求されたサービス機能チェーンにおける最初のサービス機能である）を含み、ドメインB（８２０）内のノードB1（８２２）およびドメインD（８４０）内のノードD1（８４２）への要件を満たすリンクをもつので、ノードA1がSFC内の最初の関数にマッピングされており、それぞれノードB1またはノードD1にリンクされている二つの部分的にマッピングされたチェーンを生成することを示している。
【００８１】
この例では、資源オーケストレーターA（８０２−A）はコントローラ・メッセージ８５４をドメインB（８２０）についての資源オーケストレーターB（８０２−B）に送る。コントローラ・メッセージ８５４はSFC要求識別子（1）と、部分的にマッピングされたチェーン（<A1,B1,1>・<>・<>）とを含む。コントローラ・メッセージ内の最初の括弧内の値は、最初の項目であるノードA1が第一のサービス機能f1にマッピングされるバーテックスであり、ノードB1が該部分的にマッピングされたチェーンが遅延値1をもつリンクを通じて送られるバーテックスであることを示す。SFC要求における他のサービス機能はまだマッピングされていないので、コントローラ・メッセージ８５４に含まれる部分的にマッピングされたサービス機能チェーンは二つの空の括弧を含んでいる。同様に、資源オーケストレーターA（８０２−A）はコントローラ・メッセージ８５２をドメインD（８４０）についての資源オーケストレーターD（８０２−D）に送る。コントローラ・メッセージ８５２はSFC要求識別子（1）と、部分的にマッピングされたチェーン（<A1,D1,1>・<>・<>）とを含む。コントローラ・メッセージ内の最初の括弧内の値は、最初の項目であるノードA1が第一のサービス機能f1にマッピングされるバーテックスであり、ノードD1が該部分的にマッピングされたチェーンが遅延値1をもつリンクを通じて送られるバーテックスであることを示す。SFC要求における他のサービス機能はまだマッピングされていないので、コントローラ・メッセージ８５２に含まれる部分的にマッピングされたサービス機能チェーンは二つの空の括弧を含んでいる。
【００８２】
図８Ｄは、スーパーステップ0では、ドメインD（８４０）内のノードD1（８４２）はサービス機能f1（）を含み、ドメインA（８１０）内のノードA1（８１２）およびドメインC（８３０）内のノードC1（８３２）への要件を満たすリンクをもつので、ノードD1がSFC内の最初の関数にマッピングされており、それぞれノードB1またはノードD1にリンクされている二つの部分的にマッピングされたチェーンを生成することを示している。この例では、資源オーケストレーターD（８０２−D）はコントローラ・メッセージ８５６をドメインA（８１０）についての資源オーケストレーターA（８０２−A）に送る。コントローラ・メッセージ８５６はSFC要求識別子（1）と、部分的にマッピングされたチェーン（<D1,A1,1>・<>・<>）とを含む。コントローラ・メッセージ内の最初の括弧内の値は、最初の項目であるノードD1が第一のサービス機能f1にマッピングされるバーテックスであり、ノードA1が該部分的にマッピングされたチェーンが遅延値1をもつリンクを通じて送られるバーテックスであることを示す。SFC要求における他のサービス機能はまだマッピングされていないので、コントローラ・メッセージ８５６に含まれる部分的にマッピングされたサービス機能チェーンは二つの空の括弧を含んでいる。同様に、資源オーケストレーターD（８０２−D）はコントローラ・メッセージ８５８をドメインC（８３０）についての資源オーケストレーターC（８０２−C）に送る。コントローラ・メッセージ８５８はSFC要求識別子（1）と、部分的にマッピングされたチェーン（<D1,C1,1>・<>・<>）とを含む。コントローラ・メッセージ内の最初の括弧内の値は、最初の項目であるノードD1が第一のサービス機能f1にマッピングされるバーテックスであり、ノードC1が該部分的にマッピングされたチェーンが遅延値1をもつリンクを通じて送られるバーテックスであることを示す。SFC要求における他のサービス機能はまだマッピングされていないので、コントローラ・メッセージ８５８に含まれる部分的にマッピングされたサービス機能チェーンは二つの空の括弧を含んでいる。
【００８３】
この例では、ノードB1（８２２）もノードC1（８３２）もサービス機能f1（これが、要求されたサービス機能チェーンにおける最初のサービス機能である）を含まないので、これらのノードは要件を満たすノードではなく、それぞれの資源オーケストレーターからそれらの近傍の資源オーケストレーターへは、スーパーステップ0の間、コントローラ・メッセージは送られない。ひとたびバーテックス（ノード）のすべてが受領するはずのコントローラ・メッセージを受領したら、スーパーステップ0は終了する。図８Ｅは、スーパーステップ0の終わりに、部分的にマッピングされたサービス機能チェーンを含む四つのコントローラ・メッセージが宛先バーテックスに送達されたことを示している。より具体的には、ノードA1はコントローラ・メッセージ８５２を受領しており、ノードB1はコントローラ・メッセージ８５４を受領しており、ノードC1はコントローラ・メッセージ８５８を受領しており、ノードD1はコントローラ・メッセージ８５８を受領しており、これらはみな上述してある。
【００８４】
上記のように、スーパーステップ0以外のスーパーステップの間、前のスーパーステップの間のSFC要求に関係したコントローラ・メッセージを受領した各バーテックス（ノード）は、それらのメッセージを処理し、それらのメッセージ内の部分的にマッピングされたサービス機能チェーンが延長または完成されることができるか否かを判定する。たとえば、図８Ｆは、スーパーステップ１の間に、ノードA1（これは部分チェーン<D1,A1,1>・<>・<>を受領した）が該チェーンを<D1,A1,1>・<A1,B1,1>・<>に延長できることを示している。機能f2（要求されたサービス機能チェーンにおける第二の機能）がノードA1（８１２）において利用可能であり、ノードA1はその近傍ノードB1（８２２）への要件を満たすリンクをもつからである。この例において、資源オーケストレーターA（８０２−A）は、この延長されたサービス機能チェーンを含むコントローラ・メッセージ８６０を、延長されたサービス機能チェーンを含むノードB1についての資源オーケストレーター（資源オーケストレーターB、８０２−B）に送る。
【００８５】
同様に、図８Ｇは、スーパーステップ１の間に、ノードB1（これは部分チェーン<A1,B1,1>・<>・<>を受領した）が該チェーンを<A1,B1,1>・<B1,C1,1>・<>に延長できることを示している。機能f2（要求されたサービス機能チェーンにおける第二の機能）がノードC1（８３２）において利用可能であり、ノードB1はその近傍ノードC1（８３２）への要件を満たすリンクをもつからである。この例において、資源オーケストレーターB（８０２−B）は、この延長されたサービス機能チェーンを含むコントローラ・メッセージ８６２を、延長されたサービス機能チェーンを含むノードC1についての資源オーケストレーター（資源オーケストレーターC、８０２−C）に送る。
【００８６】
この例において、スーパーステップ1の間に、バーテックス（ノード）D1  ８４２は、コントローラ・メッセージ８５２において受領した部分的にマッピングされたチェーン<A1,D1,1>・<>・<>を破棄する。該チェーンを延長する機能f2がノードD1において利用可能でないからである（このためノードD1は失格となる）。同様に、スーパーステップ1の間に、バーテックス（ノード）C1  ８３２は、コントローラ・メッセージ８５８において受領した部分的にマッピングされたチェーン<D1,C1,1>・<>・<>を破棄する。該チェーンを延長する機能f2がノードC1において利用可能でないからである（このためノードC1は失格となる）。このことは図８Ｈに示されている。
【００８７】
ひとたびすべてのバーテックス（ノード）が、スーパーステップ1の間に受領するはずのコントローラ・メッセージを受領したら、スーパーステップ1は終了する。図８Ｉは、スーパーステップ1の終わりに、部分的にマッピングされたサービス機能チェーンを含む二つの残りのコントローラ・メッセージが宛先バーテックスに送達されたことを示している。より具体的には、ノードB1はコントローラ・メッセージ８６０を受領しており、ノードC1はコントローラ・メッセージ８６２を受領している。いずれも上述してある。
【００８８】
スーパーステップ2の間に、バーテックスBおよびバーテックスCがいずれも、要求されたサービス機能チェーンについての最後の必要とされるサービス機能（サービス機能f3）を有するので、そのそれぞれが要求されたサービス機能チェーンについてのそれぞれの候補解を完成させてもよく、完成されたサービス機能チェーンをソース・オーケストレーターに送り返してもよい。たとえば、バーテックス（ノード）C1  ８３２（これは部分チェーン<A1,B1,1>・<B1,C1,1>・<>を受領した）は、自らをチェーン内の第三のサービス機能にマッピングすることによって、チェーンを<A1,B1,1>・<B1,C1,1>・<C1,,>として延長し、完成させることができる。この例では、資源オーケストレーターC（８０２−C）は、完成されたサービス機能チェーンを含むコントローラ・メッセージ８６６をソース資源オーケストレーター（資源オーケストレーターA、８０２−A）に送る。同様に、バーテックス（ノード）B1  ８２２（これは部分チェーン<D1,A1,1>・<A1,B1,1>・<>を受領した）は、自らをチェーン内の第三のサービス機能にマッピングすることによって、チェーンを<D1,A1,1>・<A1,B1,1>・<B1,,>として延長し、完成させることができる。この例では、資源オーケストレーターB（８０２−B）は、完成されたサービス機能チェーンを含むコントローラ・メッセージ８６４をソース資源オーケストレーター（資源オーケストレーターA、８０２−A）に送る。ひとたびコントローラ・メッセージ８６６およびコントローラ・メッセージ８６４がソース資源オーケストレーターに送達されたら、スーパーステップ2（および全体としての分散式計算）は完了である。
【００８９】
図８Ａ〜８Ｊに示される例示的なバーテックス中心の分散式計算では、見出されてソース・オーケストレーターに通信し返された二つの可能なサービス機能チェーン解があった。一方のサービス機能チェーンはノードD1（サービス機能f1を実行）からノードA1（サービス機能f2を実行）、ノードB1（サービス機能f3を実行）へと進む。他方のサービス機能チェーンはノードA1（サービス機能f1を実行）からノードB1（サービス機能f2を実行）、ノードC1（サービス機能f3を実行）へと進む。この例では、ソース・オーケストレーターはこのように、SFC要求８０５についての二つの可能な解、D1・A1・B1およびA1・B1・C1を受け取ることがある。
【００９０】
図８Ａ〜８Ｊに示され、上述される例は、固定した順序のSFC要求に関わるものだが、本稿に記載されるバーテックス中心の分散式コンピューティング手法は、いくつかの実施形態では、柔軟な順序のSFC要求への適用にも好適でありうる。SFC要求が柔軟な順序のサービス機能チェーンを含む場合には、少なくともいくつかのスーパーステップにおいて、各スーパーステップにおいて実行されるコンピュート機能が、それぞれ部分的にマッピングされたチェーンを延長または完成するための複数のオプションの一つを同定しようとする複数の探索を並行して実行してもよい。この場合、バーテックス中心の分散式計算は、サービス機能チェーンが同数のサービス機能をもつ固定した順序のSFC要求について実行される場合と同数のスーパーステップをもつことになるが、固定した順序の場合よりも各スーパーステップの間により多くのメッセージを交換することになる。
【００９１】
柔軟な順序のSFC要求の場合、少なくともいくつかの実施形態では、vertex.hasFunction()メソッド（vertex.isQualifiedによってコールされるものなど）が、現在のチェーンに基づいてチェーンを延長するために使用される機能を計算することができてもよい。たとえば、SFC要求f1*f2*f3について、サービス機能f1をもつバーテックスBが部分的にマッピングされたチェーン<>*<A,B,1>*<>を含むコントローラ・メッセージを受領してもよい。このチェーンは二つの情報を担持していてもよい：バーテックスAがサービス機能f2にマッピングされているという事実と、チェーンを延長するサービス機能はサービス機能f1またはサービス機能f3のいずれかであることができるという指示である。この例において、バーテックスBはサービス機能f1をもつので、チェーン内のf1にマッピングされ、チェーンを<B,,>*<A,B,1>*<>になるよう延長することができる。この例において、次いでバーテックスCが、部分的にマッピングされたチェーン<B,C,1>*<A,B,1>*<>を含むコントローラ・メッセージを受領してもよい。このコントローラ・メッセージに基づいて、バーテックスCは、バーテックスAがサービス機能f2にマッピングされていること、バーテックスBがサービス機能f1にマッピングされていること、この（これまでの）候補解におけるサービス機能の順序はf2・f1であることを知る。よって、バーテックスCはサービス機能f3を有していればチェーンを完成させうる。
【００９２】
いくつかの場合には、SFC要求は、サービス機能のいくつかについては順序が柔軟だが、他については柔軟でないサービス機能チェーンを含むことがある。少なくともいくつかの実施形態では、本稿に記載されるバーテックス中心の分散式コンピューティング手法は、これらの型のSFC要求についても何らかの潜在的な解を同定するために使用されうる。たとえば、サービス機能チェーン要求(f1*f2*f3)・f4について、マッピングされるサービス機能の第一の集合は{f1,f2,f3}である。すなわち、集合{f1,f2,f3}内のいずれかのサービス機能に関連付けされた任意のバーテックスは、関連付けされたサービス機能にマッピングされることができる。サービス機能f1がすでにマッピングされている部分的にマッピングされたチェーンについて、マッピングされるべきサービス機能の次の集合は{f2,f3}である、などとなる。ひとたび集合{f1,f2,f3}内のサービス機能のすべてがマッピングされたら、サービス機能f4がマッピングされる。もう一つの例では、サービス機能チェーン要求f4・(f1*f2*f3)についてのチェーンのために、マッピングされることのできる第一のサービス機能はサービス機能f4であり、サービス機能f4をもつ任意のバーテックスがまずサービス機能f4にマッピングされるべきである。この例では、サービス機能f4がマッピングされたのち、集合{f1,f2,f3}内のサービス機能が任意の順序でマッピングされることができる。
【００９３】
図９は、ある実施形態に基づく、マルチドメイン・ネットワークにおいてサービス機能チェーン要求についての要件を満たす解すべてを同定するための、バーテックス中心の分散式アルゴリズムを実行するための方法９００の選択された要素を示す流れ図である。この例示的実施形態では、方法は（９０２において）、ソース・オーケストレーターがサービス機能チェーン（SFC）要求を受領することを含む。方法は（９０４において）ソース・オーケストレーターが該要求を、種々のネットワーク・ドメインにおける参加する資源オーケストレーターに送ることを含む。
【００９４】
この例では、方法は（９０６において）各ドメインの資源オーケストレーターが、そのドメイン内のそれぞれの要件を満たすノード（バーテックス）上（たとえば、固定した順序のチェーンにおけるサービス機能の最初のもの、あるいは柔軟な順序のチェーンにおけるサービス機能の任意のものを含む各ノード上）での共通のコンピュート関数の実行を協調させることを含む。これは、要件を満たすノードが部分的にマッピングされたサービス機能チェーンをその近傍ノードに送ることを含んでいてもよい。方法は（９０８において）、二つ以上のスーパーステップのそれぞれにおいて、部分的にマッピングされたサービス機能チェーンを受領するこれらおよび他のノード上のコンピュート関数が、チェーンが延長できるか延長できないか、あるいは完成できるかを判定することを含む。方法はまた（９１０において）、バーテックス上でコンピュート関数によって同定されたすべての可能な解が、それぞれの資源オーケストレーターによってそのドメインのために取得され、該資源オーケストレーターは取得された解をソース・オーケストレーターに送ることを含む。
【００９５】
先述したように、本稿に記載されるバーテックス中心の分散式アルゴリズムの目的は、マルチドメイン・ネットワークにおいてSFC要求について、要件を満たす解をすべて同定することである。いくつかの実施形態では、この計算の結果は、サービス・プロバイダーのポリシーおよび／または要求者の選好に従って、他の基準を満たす解のみを同定するために枝刈りされてもよい。たとえば、いくつかの実施形態では、潜在的な解は、指定された全コスト閾値より低い全コストをもつまたは指定された全遅延閾値より低い全遅延をもつ潜在的な解のみを含むよう枝刈りされてもよい。解の全コストは、種々の実施形態において、実際のコスト（たとえば、ファイバー・コストまたは物理的なリンクのコスト）に関してまたは帯域幅もしくは遅延に関して指定されてもよい。いくつかの実施形態では、潜在的な解は、複数のそのような制約条件（たとえば、コスト、遅延および／または帯域幅の二つ以上についての制約条件）を満たす潜在的な解のみを含むよう枝刈りされてもよい。いくつかの実施形態では、潜在的な解の一つまたは複数の選択が、負荷均衡化器によってランタイムで決定されてもよい。いくつかの実施形態では、保護目的のために、潜在的な解は、共通部分をもたない諸チェーンを含む潜在的な解の集合を含むよう枝刈りされてもよい。たとえば、潜在的な解の枝刈りされた集合におけるサービス機能チェーンがいかなる重複する資源も含まない場合（たとえば、重複する物理リンクや物理ノードがない）、集合内の選択されたサービス機能チェーンにおける資源の一つが利用不能になっても、潜在的な解の枝刈りされた集合における他のサービス機能チェーンの利用可能性に影響しない。
【００９６】
図１０は、ある実施形態に基づく、サービス機能チェーン要求を満足させる方法１０００の選択された要素を示す流れ図である。この例示的実施形態では、方法は（１００２において）マルチドメイン・ネットワークのそれぞれのドメイン内の資源オーケストレーターが制御チャネルを通じて互いとの接続を確立することを含む。方法は（１００４において）それぞれのドメイン内の資源オーケストレーターが、自分のローカルなドメインについておよびマルチドメイン・ネットワークについての情報を取得し、維持することを含む。たとえば、いくつかの実施形態では、資源オーケストレーターは、それが存在するノード上のメモリにこの情報を（たとえば、バーテックス値データ構造、エッジ・データ構造および／または他のデータ構造において）記憶してもよい。マルチドメイン・ネットワークにおいてSFC要求についての要件を満たす解すべてを同定するための、バーテックス中心の分散式計算を協調させる間、ローカルな資源オーケストレーターは、種々の実施形態において、SFC要求、部分的にマッピングされたサービス機能チェーン、完成されたサービス機能チェーンを表わす情報またはSFC要求についての解を計算することにおいて使用可能な他の情報をも（たとえばメモリ内に）維持してもよい。
【００９７】
この例示的実施形態では、方法は（１００６において）ソース・オーケストレーターにおいてサービス機能チェーン（SFC）要求を受領することを含む。方法はまた（１００８において）ソース・オーケストレーターがSFC要求を、マルチドメイン・ネットワーク内のすべての参加オーケストレーターに送り、本稿で記載されるような共通のコンピュート関数の実行を協調させることを含む。参加オーケストレーターによって候補解が同定されると（１０１０）、本方法はそれらの候補解をソース・オーケストレーターに送ることを含む。ひとたび（１０１２において）メッセージ交換が終了したら、本方法は、ソース・オーケストレーターが、適用可能なポリシーおよび／または要求者からの入力に基づいて、可能な解の一つまたは複数を、SFC要求を実行するために選択することを含む。本方法は（１０１４において）、SFC内のさまざまなサービス機能が実行されるドメイン（単数または複数）についてのオーケストレーター（単数または複数）に、それらのドメイン（単数または複数）内の物理資源をそれらのサービス機能の実行のために構成するよう通知することを含む。
【００９８】
本稿に記載される例示的実施形態の多くは、分散したマルチドメイン・ネットワークにおいてSFC要求についての要件を満たす解すべてを同定するための、バーテックス中心のアルゴリズムの適用に向けられているが、他の実施形態では、この手法は、中央集中化したシステムにおいて適用されてもよい。たとえば、中央集中化したシステムにおいて、単一の資源オーケストレーターが、マルチドメイン・ネットワーク全体についてのノードおよびリンク情報のすべてを含んでいてもよく、ネットワークは分割されていなくてもよい。この例では、単一の資源オーケストレーターが、SFC要求への何らかの潜在的な解を構築するために、一連のスーパーステップにおいて、バーテックス（ノード）のうちの適切なものの上で共通のコンピュート機能の実行を協調させてもよい。換言すれば、中央集中化したシステムでは、単一の資源オーケストレーターが、上記の分散された諸システムにおけるそれぞれの資源オーケストレーターすべての機能を実装してもよい。そのような中央集中化したシステムのいくつかの実施形態では、制御チャネルを通じてバーテックス（ノード）間でコントローラ・メッセージを交換するのではなく、部分的にマッピングされたチェーンを含むメッセージが、メモリに書き込み、次いでメモリから読み出すことによって、バーテックス（ノード）間で交換されてもよい。上記の分散式システムの場合と同様に、ひとたび単一の資源オーケストレーターがSFC要求を満たすためのすべての実現可能なサービス機能チェーンを同定したら、該単一の資源オーケストレーターがそれらを、一つまたは複数のポリシーもしくは制約条件に基づいて同定されたサービス・チェーンのどの一つまたは複数を実装すべきかを決定する別のプロセスに対して呈示してもよい。
【００９９】
ここで図１１を参照するに、少なくともいくつかの実施形態に基づく、例示的なネットワーク要素１１００の選択された要素のブロック図が示されている。図１１では、ネットワーク要素１１００は、マルチドメイン・ネットワークにおけるネットワーク要素の任意のものを実装する物理的および論理的コンポーネントを含むコンピュータ・システムとして表わされている。さまざまな実施形態において、ネットワーク要素１１００と同様のネットワーク要素は、図１に示されたネットワーク要素１１２の任意のもの、図２に示されたネットワーク要素１１２の任意のもの、本稿に記載されたドメイン固有の資源オーケストレーターの任意のもの（図１、図３、図４に示された資源オーケストレーター１０８のいずれかのような）、本稿に記載されるバーテックス（ノード）の任意のものまたは本稿に記載されるネットワーク・コントローラ（マルチドメイン・ネットワークにおける特定のドメインについてのSDNコントローラのような）を実装しうる。しかしながら、いくつかの実施形態では、ネットワーク要素のいくつかは図１１に示されるコンポーネントの全部を含んでいなくてもよい。他の実施形態では、本稿に記載されるネットワーク要素の任意のものが、図１に示される例示的実施形態に含まれるより多数の、少数のまたは異なるコンポーネントを含んでいてもよい。
【０１００】
この例に示されるように、ネットワーク要素１１００は、よって、一つまたは複数のプロセッサ１１０１、メモリ１１１０、一つまたは複数のサービス機能１１５０およびネットワーク・インターフェース１１２０を含んでいてもよい。プロセッサ１１０１は一つまたは複数の個々の処理ユニットを表わしていてもよく、種々の実施形態において、プログラム命令を実行し、データを解釈し、本稿に記載されるいずれかのネットワーク要素の機能を実装するためにメモリ１１１０もしくはネットワーク要素１１００内の別のコンポーネントによって記憶されているデータを処理してもよい。この例示的実施形態では、各サービス機能１１５０は、本稿に記載されるものを含むがそれに限定されないサービス機能チェーンに含まれうる多様なサービス機能の任意のものを実装するための回路、論理および／またはプログラム命令を表わしていてもよい。
【０１０１】
図１１では、メモリ１１１０は、プロセッサ１１０１に通信上結合されていてもよく、ある時間期間にわたってプログラム命令およびデータを保持するのに好適なシステム、デバイスまたは装置（たとえば、非一時的なコンピュータ可読媒体）を含んでいてもよい。メモリ１１１０は、ランダム・アクセス・メモリ（RAM）、電気的に消去可能なプログラム可能型読み出し専用メモリ（EEPROM）、PCMCIAカード、フラッシュ・メモリ、半導体ディスク、ハードディスク・ドライブ、磁気テープ・ライブラリ、光ディスク・ドライブ、光磁気ディスク・ドライブ、コンパクト・ディスク・ドライブ、コンパクト・ディスク・アレイ、ディスク・アレイ・コントローラおよび／または揮発性もしくは不揮発性メモリの任意の好適なセレクションまたはアレイといった、さまざまな型のコンポーネントおよびデバイスを含みうる。不揮発性メモリとは、電源がオフにされたあともデータを保持するメモリをいう。メモリ１１１０はさまざまな実施形態において種々の数の物理的な記憶デバイスを含みうることを注意しておく。
【０１０２】
図１１に示されるように、メモリ１１１０は資源オーケストレーション・エンジン１１３０の機能を実装するための命令を含んでいてもよい。資源オーケストレーション・エンジン１１３０は、種々の実施形態において、本開示において記載された他の機能の中でも、ネットワーク要素１１００の他のインスタンス上の資源オーケストレーション・エンジン１１３０の他のインスタンスと協働して、マルチドメイン・ネットワークにおけるSFC要求についての要件を満たす解すべてを同定するためのバーテックス中心の分散式アルゴリズムを実装してもよく、および／または図７Ａに示される方法７００、図７Ｂに示される方法７５０、図９に示される方法９００および／または図１０に示される方法１０００の要素の任意のものを実装してもよい。メモリ１１１０は、資源オーケストレーション・エンジン１１３０によって使用可能な情報を記憶しうる情報記憶部１１４０をも含んでいてもよい。記憶される情報は、SFC要求を表わすデータ、ノード情報（利用可能な計算および／または記憶資源および／またはサービス機能を示すデータを含む）、（たとえば一つまたは複数のエッジ・データ構造における）エッジ情報、（たとえば一つまたは複数のバーテックス値データ構造における）バーテックス情報、一つまたは複数の部分的にマッピングされたサービス機能チェーンを表わすデータ、サービス機能チェーン要求についての一つまたは複数の候補解を表わすデータ（たとえば完成されたサービス機能チェーン）、ユーザー資源使用選好およびポリシーを表わすデータ、サービス機能１１５０の入力または出力を表わすデータまたは本稿に記載される機能もしくはネットワーク要素１１００の他の任意の機能を実装するために使用される任意のデフォルトもしくは構成可能なパラメータの値を含むがそれに限定されない。
【０１０３】
〈シミュレーション結果〉
本稿に記載されるマルチドメイン・ネットワークにおいて要件を満たすSFC解すべてを同定するためのバーテックス中心の計算をオープン・ソース・システムにおいてシミュレートした。具体的には、この手法の75ノードのCoronetネットワークおよび225ノードの顧客ネットワークへの適用をシミュレートして種々のシナリオにおけるその性能を判別した。これらのシミュレーションにおいて、サービス機能の総数は10に固定され、一方、機能の数および各バーテックスにおいて利用可能な機能の集合はランダムに生成された。分散式システムについて観察された性能メトリックは、資源オーケストレーター間の信号伝達遅延（たとえば、全スーパーステップの間の全通信遅延；ここで、単一のスーパーステップにおける遅延はそのスーパーステップにおけるすべての通信するオーケストレーターの間の最大遅延とする）、資源オーケストレーター間で交換されたメッセージ数、SFC要求についてのすべての実現可能な解を同定するための全計算時間を含む。
【０１０４】
分散されたオーケストレーターは、最小平均伝搬遅延をもつ物理的なネットワーク・ノードの間で選択され、それらのオーケストレーターが順に、最も近いバーテックスを選択していき、オーケストレーター間で均等の数のバーテックスとなった。これらのシミュレーションにおいて、ランダムに選択された必要とされる機能をもつ単一の線形のSFC要求が、ある時間において生成された。図１２Ａ〜１２Ｃに示されるグラフおよびその記述において、Vは諸ネットワーク内のバーテックスの総数を表わし、Dはネットワーク・ドメインの数を表わし、FはSFC要求におけるサービス機能の数を表わす。これらのシミュレーションにおいて、各バーテックスは、各スーパーステップにおいて比較的短い計算時間を経験した（平均で約2〜10ミリ秒）。よって、図に呈示される結果は主として、信号伝達遅延およびオーケストレーター間のメッセージのサイズに焦点を当てている。
【０１０５】
図１２Ａ〜１２Ｃは、これらのシミュレーションの選択された結果を示す。より具体的には、図１２Ａは、SFC要求について分散式コンピューティングについてのオーケストレーター間の平均信号伝達遅延を、ドメイン数Dに対して描くグラフ１２００を示している。このシミュレーションにおいて、固定した順序のSFC要求が生成された。図１２Ａに示される信号伝達遅延は、所与の要求についての全スーパーステップの総合遅延を表わす。ここで、各スーパーステップにおける遅延は、通信するオーケストレーターの間の最大往復伝搬遅延である。図１２Ａに示されるスーパーステップ数は所与の要求におけるサービス機能の数に等しい。図１２Ａに示されるように、Fのより高い値（たとえば、SFC要求におけるより多数のサービス機能）は、より多くのスーパーステップを実行しなければならないため、より長い信号伝達遅延につながった。さらに、図１２Ａは、Dのより高い値（たとえば、より多数のネットワーク・ドメイン）は、より長い平均信号伝達遅延につながったことを示している。これはたとえば、異なるドメイン内のおよび／または異なるオーケストレーターによって管理されるバーテックスが任意の所与のSFC解に含まれる可能性がより高いためでありうる。少なくともいくつかの実施形態では、信号伝達遅延は、オーケストレーターおよびネットワーク分割の選択に強く依存しうる。メッセージは、物理ノードではなく、オーケストレーターの間で交換されるからである。たとえば、225ノードのネットワークが、75ノードのネットワークより短い信号遅延を有することがありうる。
【０１０６】
図１２Ｂは、分散式システムにおけるオーケストレーター間で交換される平均メッセージ・サイズを、ドメイン数Dに対して描くグラフ１２１０を示している。先のシミュレーションと同様、固定した順序のSFC要求が生成された。この例では、オーケストレーター間のメッセージのみが結果に含められた。図１２Ｂに示されるように、より高いF、Vおよび／またはD値をもつと、各SFC要求についての全メッセージ・サイズも増大した。スーパーステップにおいてオーケストレーターの同じ対の間で交換されるメッセージが単一のメッセージに組み合わされることのできるいくつかの実施形態では、ある要求について交換される最大のメッセージ数はD(D−I)Fでありうる。これは、要求サイズFとともに線形に変化する。
【０１０７】
図１２Ｃは、SFC要求におけるサービス機能の数に対する、本稿に記載されるバーテックス中心の分散式アルゴリズムと対応する中央集中化された網羅的探索アルゴリズムとの計算時間を比較している。両方のアルゴリズムが同じ1.6ギガバイト・メモリ、二プロセッサ仮想マシン上で実行された。公平な比較をするために、分散式アルゴリズムは単一スレッドで単一パーティション内で実行された。このシミュレーションにおいて、いろいろな数のサービス機能をもって柔軟な順序の要求が生成された。網羅的アルゴリズムはまず、あらゆる可能な固定順序のチェーンを生成し、そのそれぞれが次いで、要求された機能をもつ候補バーテックスにマッピングされた。このシミュレーションでは、網羅的なアルゴリズムの計算上の複雑さは、Fに対して指数関数的に変化した。すなわち、計算量はF!VFとして変化した。ここで、可能な固定順序のチェーンの数はF!であり、各チェーンはバーテックスへのVF通りの可能なマッピングをもつ。V＝75について（そしてV＝225について）、F＝4の値を超えては結果は得られなかった。中央集中化された手法は、10分後にメモリ不足のために失敗となったからである。他方、本稿に記載される分散式アルゴリズムは、Fのより高い値について結果を出すことができ、本手法のすぐれた効率性およびスケーラビリティーを実証した。少なくともいくつかの実施形態では、本稿に記載されるバーテックス中心のアルゴリズムは、要求中の二つの連続する機能にマッピングされるバーテックスが隣り合うことを保証して、それにより、候補バーテックス間にネットワーク接続がないときに、候補バーテックスの無用な機能マッピングを避けてもよい。
【０１０８】
本稿に記載されるシステムの少なくともいくつかの実施形態では、マルチドメイン・ネットワークにおいてSFC要求に対してすべての実現可能な解を計算するためのバーテックス中心の手法は、以前の手法に対して利点をもちうる。種々の実施形態において、本稿に記載されるバーテックス中心フレームワークおよび資源オーケストレーション手法は、中央集中化されたセッティングおよび分散式のセッティングの両方について好適でありうる。それは、伝統的なアーキテクチャにおけるグローバルな状態情報の複製に関連する問題を回避でき、信号伝達遅延および交換されるメッセージ数に関して以前の手法より効率的であることが示された。少なくともいくつかの実施形態では、この手法は、マルチドメイン・ネットワークにおいてSFC要求についてすべての実現可能なマッピング解を計算するためにきわめてスケーラブルでありうる。たとえば、本稿に記載されるシステムおよび方法は、いくつかの実施形態では、アクセス、メトロ、コアおよびデータセンター・ネットワークをカバーする富士通ネットワークコミュニケーションズ社からの1Finity（商標）プラットフォーム上で実装される資源を協調させ、制御するために使用されてもよい。
【０１０９】
一般に、本開示の少なくともいくつかの実施形態では、本稿に記載されるバーテックス中心の分散式コンピューティング・フレームワークは、諸サービス機能、仮想マシン、データ・センター、スイッチング・システムおよびモノのインターネットにまたがる大規模な、マルチドメインの、マルチレイヤーのネットワーク問題を解決するために使用されうる。
【０１１０】
本稿で開示されるように、分散式オーケストレーション・システムおよびバーテックス中心の分散式アルゴリズムは、マルチドメイン・ネットワークにおいて要件を満たすサービス機能チェーン形成結果すべてを見出すために使用されうる。シミュレーション結果は、オーケストレーター間のメッセージングの複雑さがSFC要求内のサービス機能の数に比例することを示した。シミュレーションはまた、この手法が、多くの場合において（たとえば、225ノードのネットワークにおいてサービス機能の数が4より多いときを含む）、通常の網羅的な手法よりもすぐれた効率性およびスケーラビリティーを提供することをも実証した。
【０１１１】
本明細書の主題は一つまたは複数の例示的実施形態との関連で記載されてきたが、いずれかの請求項を記載される特定の形に限定することは意図されていない。逆に、本開示に向けられるいかなる請求項も、その精神および範囲内に含まれうるような代替、修正および等価物をカバーすることが意図されている。
【０１１２】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
（付記１）
マルチドメイン・ネットワークにおいて要件を満たすサービス機能チェーン形成の解を同定する方法であって：
資源オーケストレーターにおいて、前記マルチドメイン・ネットワークにおける個々の物理ノード上で実行されるべき複数のサービス機能を指定するサービス機能チェーン要求を受領する段階であって、各ノードは資源オーケストレーション・フレームワークにおけるバーテックスとして表わされる、段階と；
前記複数のサービス機能のうちの第一のものが利用可能である一つまたは複数のバーテックスを同定する段階と；
同定されたバーテックスのうち第一の同定されたバーテックスについて、
該第一の同定されたバーテックスを候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第一のものにマッピングし、
前記複数のサービス機能のうちの第二のものが前記第一の同定されたバーテックスの第一の近傍バーテックスにおいて利用可能であることを判別し、前記第一の近傍バーテックスは、前記マルチドメイン・ネットワークの、前記第一の同定されたバーテックスが存在するドメインとは異なるドメインに存在し、
前記第一の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第二のものにマッピングして前記候補サービス機能チェーンを延長する、
段階とを含む、
方法。
（付記２）
前記複数のサービス機能のうちの第三のものが前記第一の近傍バーテックスの第二の近傍バーテックスにおいて利用可能であることを判別する段階であって、前記第二の近傍バーテックスは、前記マルチドメイン・ネットワークの、前記第一の近傍バーテックスが存在するドメインとは異なるドメインに存在する、段階と；
前記第二の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第三のものにマッピングして前記候補サービス機能チェーンをさらに延長する段階とをさらに含む、
付記１記載の方法。
（付記３）
前記第一の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第二のものにマッピングすることは、前記候補サービス機能チェーンを完成させ、
当該方法はさらに、完成された候補サービス機能チェーンを前記資源オーケストレーターに返すことを含む、
付記１記載の方法。
（付記４）
前記サービス機能チェーン要求は、前記マルチドメイン・ネットワークにおける個々の物理ノード上で実行されるべき前記複数のサービス機能についての固定された順序を指定し、
前記固定された順序は、前記複数のサービス機能のうちの前記第一のものが、前記複数のサービス機能のうちの前記第二のものより先に実行されるべきであることを指定する、
付記１記載の方法。
（付記５）
前記候補サービス機能チェーンを完成させる段階と；
一つまたは複数の他の候補サービス機能チェーンを完成させる段階であって、前記他の候補サービス機能チェーンのそれぞれを完成させることは、該他の候補サービス機能チェーンにおける前記複数のサービス機能のうちのそれぞれに対して前記資源オーケストレーション・フレームワークにおける個々のバーテックスをマッピングすることを含み、前記候補サービス機能チェーンと、前記一つまたは複数の他の候補サービス機能チェーンのそれぞれとにおけるマッピングのセットは異なる、段階と；
前記候補サービス機能チェーンおよび前記一つまたは複数の他の候補サービス機能チェーンのうちから、一つまたは複数のサービス機能チェーン解を実行のために選択する段階であって、選択は、サービス・プロバイダー・ポリシー、サービス・プロバイダー制約条件または要求者に依存し、前記サービス機能チェーン要求は該要求者のために受領されたものである、段階とをさらに含む、
付記１記載の方法。
（付記６）
前記選択は：
候補サービス機能チェーンの全遅延；
候補サービス機能チェーンの全コスト；
候補サービス機能チェーンのうちの二つにおける物理ノードの重複；
候補サービス機能チェーンのうちの二つにおける物理リンクの重複；または
負荷均衡化機構
のうちの一つまたは複数に依存する、付記５記載の方法。
（付記７）
前記サービス機能チェーン要求は、前記マルチドメイン・ネットワークにおける個々の物理ノード上で実行されるべき前記複数のサービス機能についての柔軟な順序付けを指定し、
前記第一の同定されたバーテックスを候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第一のものにマッピングすることは、前記第一の同定されたバーテックスを、前記候補サービス機能チェーンにおける最初の位置以外の位置にあるサービス機能にマッピングすることを含む、
付記１記載の方法。
（付記８）
当該方法がさらに：
前記候補サービス機能チェーンを完成させ；
第二の候補サービス機能チェーンを完成させることを含み、
前記第二の候補サービス機能チェーンを完成させることは、前記第二の候補サービス機能チェーンにおける前記複数のサービス機能のうちのそれぞれに対して前記資源オーケストレーション・フレームワークにおける個々のバーテックスをマッピングすることを含み、バーテックスは、前記第二の候補サービス機能チェーンにおいては、前記候補サービス機能チェーンにおいて前記複数のサービス機能にマッピングされたのとは異なる順序で、前記複数のサービス機能にマッピングされる、
付記７記載の方法。
（付記９）
前記資源オーケストレーターは、前記マルチドメイン・ネットワークにおいてバーテックス中心のサービス機能チェーン形成を協調させるための唯一の資源オーケストレーターである、付記１記載の方法。
（付記１０）
前記資源オーケストレーターは、前記マルチドメイン・ネットワークにおいてバーテックス中心のサービス機能チェーン形成を協調させるための複数の資源オーケストレーターの一つであり、各資源オーケストレーターは、前記マルチドメイン・ネットワークにおけるそれぞれのドメインに関連付けられており、それぞれのドメイン内のバーテックス上での共通のコンピュート関数の実行を協調させる、
付記１記載の方法。
（付記１１）
前記複数のサービス機能のうちの第一のものが利用可能である前記一つまたは複数のバーテックスを同定する段階は：
前記資源オーケストレーターがコントローラ・メッセージを別の資源オーケストレーターに送る段階であって、該別の資源オーケストレーターは前記第一の同定されたバーテックスが存在するドメインに関連付けられている、段階と；
前記別の資源オーケストレーターが前記複数のサービス機能のうちの前記第一のものが前記第一の同定されたバーテックスにおいて利用可能であることを判別する段階とを含み、
前記第一の同定されたバーテックスを前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第一のものにマッピングする段階は、前記第一の同定されたバーテックスによって実行される、
付記１０記載の方法。
（付記１２）
前記同定されたバーテックスのうち前記第一の同定されたバーテックスおよび前記第一の近傍バーテックスは、物理リンクを通じて互いに通信上結合されており、
前記複数のサービス機能のうちの前記第二のものが前記第一の近傍バーテックスにおいて利用可能であることを判別する段階は：
前記物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすことを判別し；
前記候補サービス機能チェーンを含むコントローラ・メッセージを前記第一の近傍バーテックスに送り；
前記第一の近傍バーテックスが、前記複数のサービス機能のうちの前記第二のものが前記第一の近傍バーテックスにおいて利用可能であることを判別することを含む、
付記１記載の方法。
（付記１３）
複数のネットワーク・ドメインを含むマルチドメイン・ネットワークにおける資源オーケストレーション・フレームワークであって、各ネットワーク・ドメインは一つまたは複数の物理ノードを含み、前記物理ノードのそれぞれは、前記マルチドメイン・ネットワークにおいてサポートされる複数のサービス機能の部分集合を実行するための回路または論理を含み、
前記資源オーケストレーション・フレームワークは：
それぞれが前記マルチドメイン・ネットワークにおける前記物理ノードの一つを表わす複数のバーテックスと；
資源オーケストレーターとを含み、
当該資源オーケストレーション・フレームワークにおける各バーテックスは：
プロセッサと；
該プロセッサによって実行されたときに該プロセッサに、当該資源オーケストレーション・フレームワークにおける前記バーテックスの間で共通のコンピュート関数を実行させるプログラム命令を記憶しているメモリとを含み、
前記資源オーケストレーターは、
プロセッサと；
該プロセッサによって実行されたときに該プロセッサに、
前記マルチドメイン・ネットワークにおけるそれぞれの物理ノード上で実行されるべき複数のサービス機能を指定するサービス機能チェーン要求を受領する段階と；
前記複数のサービス機能のうちの第一のものが利用可能である前記資源オーケストレーション・フレームワークにおける一つまたは複数のバーテックスを同定する段階と；
前記複数のバーテックスのうちの複数のものの上での前記共通のコンピュート関数の二つのさらなるスーパーステップの実行を協調させる段階とを実行させるプログラム命令を記憶しているメモリとを含み、前記共通のコンピュート関数の第一のスーパーステップの間に、前記同定されたバーテックスのうち第一の同定されたバーテックスでの前記共通のコンピュート関数の実行は、
該第一の同定されたバーテックスを候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第一のものにマッピングする段階と；
前記第一の同定されたバーテックスと前記第一の同定されたバーテックスの第一の近傍バーテックスとの間の物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすか否かを判定する段階とを含み、前記第一の近傍バーテックスは、前記マルチドメイン・ネットワークの、前記第一の同定されたバーテックスが存在するドメインとは異なるドメインに存在する、
資源オーケストレーション・フレームワーク。
（付記１４）
前記第一のスーパーステップの間に、前記第一の同定されたバーテックスでの前記共通のコンピュート関数の実行はさらに、
前記第一の同定されたバーテックスと前記第一の近傍バーテックスとの間の物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすと判定することに応答して、前記候補サービス機能チェーンを前記第一の近傍バーテックスに提供することを含み、
前記共通のコンピュート関数の第二のスーパーステップの間に、前記第一の近傍バーテックスでの前記共通のコンピュート関数の実行は、
前記候補サービス機能チェーンを取得することに応答して、前記候補サービス機能チェーンが前記第一の近傍バーテックスにおいて延長されることができるか否かを判定することを含む、
付記１３記載の資源オーケストレーション・フレームワーク。
（付記１５）
前記第二のスーパーステップの間に、前記第一の近傍バーテックスでの前記共通のコンピュート関数の実行はさらに、
前記複数のサービス機能のうちの第二のものが前記第一の近傍バーテックスにおいて利用可能であることを判別する段階と；
前記第一の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第二のものにマッピングして前記候補サービス機能チェーンを延長する段階とを含む、
付記１４記載の資源オーケストレーション・フレームワーク。
（付記１６）
前記第二のスーパーステップの間に、前記第一の近傍バーテックスでの前記共通のコンピュート関数の実行はさらに、
前記第一の近傍バーテックスと前記第一の近傍バーテックスの第二の近傍バーテックスとの間の物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすか否かを判定する段階であって、前記第二の近傍バーテックスは、前記マルチドメイン・ネットワークの、前記第一の近傍バーテックスが存在するドメインとは異なるドメインに存在する、段階と；
前記第一の近傍バーテックスと前記第二の近傍バーテックスとの間の物理リンクが前記サービス機能チェーン要求について指定されている要件を満たすと判定することに応答して、延長された候補サービス機能チェーンを前記第二の近傍バーテックスに提供する段階とを含む、
付記１５記載の資源オーケストレーション・フレームワーク。
（付記１７）
前記第二のスーパーステップの間に、前記第一の近傍バーテックスでの前記共通のコンピュート関数の実行はさらに、
前記第一の近傍バーテックスを、前記候補サービス機能チェーンにおける前記複数のサービス機能のうちの前記第二のものにマッピングすることが、前記候補サービス機能チェーンを完成させることを判別し；
完成された候補サービス機能チェーンを前記資源オーケストレーターに提供することを含む、
付記１５記載の資源オーケストレーション・フレームワーク。
（付記１８）
前記資源オーケストレーターの前記プロセッサによって実行されたとき、前記資源オーケストレーターの前記メモリに記憶された前記プログラム命令は、該プロセッサに、
前記の完成された候補サービス機能チェーンおよび一つまたは複数の他の完成された候補サービス機能チェーンのうちから、一つまたは複数のサービス機能チェーン解を実行のために選択することを実行させ、該選択は、サービス・プロバイダー・ポリシー、サービス・プロバイダー制約条件または要求者に依存し、前記サービス機能チェーン要求は該要求者のために受領されたものである、
付記１７記載の資源オーケストレーション・フレームワーク。
（付記１９）
前記資源オーケストレーターは、前記マルチドメイン・ネットワークにおいてバーテックス中心のサービス機能チェーン形成を協調させるための唯一の資源オーケストレーターである、付記１３記載の資源オーケストレーション・フレームワーク。
（付記２０）
前記資源オーケストレーション・フレームワークは前記資源オーケストレーターを含む複数の資源オーケストレーターを含み、各資源オーケストレーターは、前記マルチドメイン・ネットワークにおけるそれぞれのドメインに関連付けられており、それぞれのドメイン内のバーテックス上での前記共通のコンピュート関数の前記二つのさらなるスーパーステップの実行を協調させる、付記１３記載の資源オーケストレーション・フレームワーク。
【符号の説明】
【０１１３】
１０８  資源オーケストレーター
１１０  物理ネットワーク
２１０  モノのインターネット（IoT）
２１４  SFC要求
２２０  アクセス・サービス
２３０  計算および／または記憶サービス
２４０  コア・サービス機能
７０２  各ネットワーク・ドメインにおける資源オーケストレーターが、所与のサービス機能チェーンを構築することを開始する要件を満たすバーテックスを同定
７０４  近傍への要件を満たすリンクがみつかった？
７０６  部分的にマッピングされたSFCを破棄
７０８  同定された要件を満たすバーテックスが、スーパーステップ0をもって共通のコンピュート関数の実行を開始。スーパーステップ0は、前記要件を満たすバーテックスをチェーン内の第一のサービス機能にマッピングし、近傍への要件を満たすリンクを含む部分的にマッピングされたチェーン（単数または複数）を生成することを含む
７１０  現在のドメインについての資源オーケストレーターが、前記部分的にマッピングされたチェーン（単数または複数）を含むコントロール・メッセージを、前記バーテックスが要件を満たすリンクをもつ近傍（単数または複数）についてのオーケストレーター（単数または複数）に送る
７１２  この初期に同定されたバーテックスについてスーパーステップ0が完了
７１４  さらなる要件を満たすバーテックスが初期に同定されていた？
７１６  このSFC要求についてスーパーステップ0が完了
７２２  SFC要求に関係したメッセージを受領した所与のバーテックスが、0以外のスーパーステップについてコンピュート関数の実行を開始
７２４  所与のバーテックスがSFCを延長できるか？
７２６  部分的にマッピングされたSFCを破棄
７２８  所与のバーテックスが自らをチェーン内の次の機能にマッピング
７３０  所与のバーテックスがチェーンを完成？
７３２  オーケストレーターが完成チェーンを送信
７３４  要件を満たすリンクが存在？
７３６  部分的にマッピングされたSFCを破棄
７３８  所与のバーテックスについての資源オーケストレーターが、延長されたSFCをもつコントロール・メッセージを、その所与のバーテックスが上記リンクを通じて通信する近傍についてのオーケストレーターに送る
７４０  さらなるSFCメッセージが受領される？
７４２  所与のバーテックスについてこのスーパーステップが完了
９０２  ソース・オーケストレーターがサービス機能チェーン（SFC）要求を受領
９０４  ソース・オーケストレーターが該要求を、種々のネットワーク・ドメインにおける参加資源オーケストレーターに送る
９０６  各ドメインの資源オーケストレーターが、そのドメイン内のそれぞれの要件を満たすノード（バーテックス）上での共通のコンピュート関数の実行を協調させる。部分的にマッピングされたチェーンをその近傍ノードに送ることを含む
９０８  二つ以上のスーパーステップのそれぞれにおいて、部分的にマッピングされたサービス機能チェーンを受領するノード上のコンピュート関数が、チェーンが延長できるか延長できないか、あるいは完成できるかを判定
９１０  バーテックス上でコンピュート関数によって同定されたすべての可能な解が、それぞれの資源オーケストレーターによってそのドメインのために取得され、該資源オーケストレーターは解をソース・オーケストレーターに送る
１００２  マルチドメイン・ネットワークのそれぞれのドメイン内の資源オーケストレーターが制御チャネルを通じて互いとの接続を確立
１００４  それぞれのドメイン内の資源オーケストレーターが、ローカルなドメインおよびマルチドメイン・ネットワークについての情報を取得し、維持
１００６  ソース・オーケストレーターにおいてサービス機能チェーン要求が受領される
１００８  ソース・オーケストレーターがSFC要求をすべての参加オーケストレーターに送り、コンピュート関数の実行を協調させる
１０１０  参加オーケストレーターによって候補解が同定されると、それらの候補解がソース・オーケストレーターに送信される
１０１２  ひとたびメッセージ交換が終了したら、ソース・オーケストレーターが、適用可能なポリシーおよび／または要求者からの入力に基づいて、可能な解の一つまたは複数を、SFC要求を実行するために選択
１０１４  SFCが実行されるドメインについてのオーケストレーターに、それらのドメイン内の物理資源をそれらのサービス機能の実行のために構成するよう通知
１１０１  プロセッサ
１１１０  メモリ
１１２０  ネットワーク・インターフェース
１１３０  資源オーケストレーション・エンジン
１１４０  情報記憶部
１１５０  サービス機能
【図１】
0006733486.tif 000004
【図２】
0006733486.tif 000005
【図３】
0006733486.tif 000006
【図４】
0006733486.tif 000007
【図５】
0006733486.tif 000008
【図６】
0006733486.tif 000009
【図７Ａ】
0006733486.tif 000010
【図７Ｂ】
0006733486.tif 000011
【図８Ａ】
0006733486.tif 000012
【図８Ｂ】
0006733486.tif 000013
【図８Ｃ】
0006733486.tif 000014
【図８Ｄ】
0006733486.tif 000015
【図８Ｅ】
0006733486.tif 000016
【図８Ｆ】
0006733486.tif 000017
【図８Ｇ】
0006733486.tif 000018
【図８Ｈ】
0006733486.tif 000019
【図８Ｉ】
0006733486.tif 000020
【図８Ｊ】
0006733486.tif 000021
【図９】
0006733486.tif 000022
【図１０】
0006733486.tif 000023
【図１１】
0006733486.tif 000024
【図１２Ａ】
0006733486.tif 000025
【図１２Ｂ】
0006733486.tif 000026
【図１２Ｃ】
0006733486.tif 000027