(57)【要約】  方法は、効率的な手順である、コンピュート後ネットワーク負荷分散（ＣＮＬＢ）を伴い、これは、最初に、異なるタイプの計算リソースを分散させつつ、物理ノード上に仮想ノードをマッピングし、最終的に、ネットワーク・スペクトル・リソースを分散させつつ、物理経路上に仮想リンクをマッピングさせることである。【選択図】図１
2016512001.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータによって、ソフトウェア・デファインド・フレキシブル・グリッド光伝達網上で、クラウド要求の組込みを実施する工程を含む方法であって、該実施する工程は、
該ネットワーク中の仮想ノードを、必要なリソースの総数の降順で並べる工程と、
異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に該仮想ノードをマッピングする工程と、
推定されるスペクトルリソースの降順で仮想リンクを並べる工程と、
物理リンク上で該負荷を分散させつつ、物理経路上で仮想リンクをマッピングし、該仮想リンクの変調フォーマットを選択する工程と、
波長及びスペクトルを該仮想リンクに割り当てる工程と、を含む、方法。
【請求項２】
前記異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に仮想ノードをマッピングする工程は、所与のクラウド要求の前記仮想ノードＶＮのうちのいずれもまだマッピングされていない物理ノードＰＮのセットを見つける工程を含み、これらのノードは、少なくとも前記仮想ノードＶＮによってリクエストされている数の、異なるタイプのリソースを含む、請求項１に記載の方法。
【請求項３】
前記異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に仮想ノードをマッピングする工程は、物理ノードＰＮのセットが空であるか否かを確認する工程を更に含み、該セットが空である場合、前記事前に割り当てたノード及びスペクトルリソースを解放した後、前記クラウド要求がブロックされ、該セットが空でない場合、前記仮想ノードＶＮが、各リソースタイプごとに、利用可能なリソース数の、提供されたリソース数に対する累積率を最大化する物理ノードＰＮにマッピングされる、請求項１に記載の方法。
【請求項４】
前記異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に仮想ノードをマッピングする工程は、前記所与のクラウド要求の仮想ノードＶＮがすべてマッピングされているか否かを確認する工程を更に含み、前記ＶＮのうちの少なくとも１つがまだマッピングされていない場合は、前記所与のクラウド要求の前記仮想ノードＶＮのうちのいずれもまだマッピングされていない物理ノードＰＮのセットが見つけられ、これらのノードは、少なくとも前記仮想ノードＶＮによってリクエストされている数の、異なるタイプのリソースを含み、そうでない場合は、各仮想リンクＶＬに対して、前記仮想リンクＶＬの仮想ノードＶＮがマッピングされた物理ノードＰＮ間の最短距離に基づき、最適スペクトル及び到達可能性制約の充足を必要とする変調フォーマットが見つけられる、請求項１に記載の方法。
【請求項５】
前記推定されるスペクトルリソースの降順で仮想リンクを並べる工程は、各仮想リンクＶＬに対して、前記仮想リンクＶＬの仮想ノードＶＮがマッピングされた物理ノードＰＮ間の最短距離に基づき、続いて、最適スペクトルを必要とし、かつ到達可能性制約を充足する変調フォーマットを見つける工程と、関数に従って、降順でクラウドリクエストの仮想リンクＶＬを並べる工程と、を含む、請求項１に記載の方法。
【請求項６】
前記物理経路上で仮想リンクをマッピングする工程は、
リストの先頭から仮想ノードＶＮを選択し、各到達可能性要件及びリクエストされた回線速度に基づいて、仮想ノードＶＮがマッピングされた物理ノードＰＮに接続する最短経路ｋのそれぞれに対して、実施可能な変調フォーマットのセットを決定する工程と、
ＶＮがマッピングされたＰＮに接続する最短経路ｋのそれぞれのビット−マップを求める工程であって、経路のビット−マップは、各変調フォーマットごとに、経路に沿ったすべての物理リンクのビット−マップにおいて、ビット単位の論理エンド演算を行うことによって、決定される、工程と、
必要な総スペクトルを決定し、連続波長スロットが経路ｋのビット−マップ上の変調フォーマットに対して利用可能となる、波長スロットの数の、連続波長スロットがマッピング可能となる、可能な波長スロット総数に対する比率に基づく、変調フォーマットを用いた、経路上での前記ＶＬのマッピングの確率を決定する工程と、
前記仮想リンクＶＬに対して最大確率を有する経路及び変調フォーマットを選択し、該最大確率が０であるか否かを確認する工程と、を含む、請求項１に記載の方法。
【請求項７】
コンピュータによる、ソフトウェア・デファインド・フレキシブル・グリッド光伝達網上での、クラウド要求の組込みの実施を含むシステムであって、該実施は、
該ネットワーク中の仮想ノードを、必要なリソースの総数の降順で並べる工程と、
異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に該仮想ノードをマッピングする工程と、
推定されるスペクトルリソースの降順で仮想リンクを並べる工程と、
物理リンク上で該負荷を分散させつつ、物理経路上で仮想リンクをマッピングし、該仮想リンクの変調フォーマットを選択する工程と、
波長及びスペクトルを該仮想リンクに割り当てる工程と、を含む、システム。
【請求項８】
前記異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に仮想ノードをマッピングする工程は、物理ノードＰＮのセットが空であるか否かを確認する工程を更に含み、該セットが空である場合、前記事前に割り当てたノード及びスペクトルリソースを解放した後、前記クラウド要求がブロックされ、該セットが空でない場合、前記仮想ノードＶＮが、各リソースタイプごとに、利用可能なリソース数の、提供されたリソース数に対する累積率を最大化する物理ノードＰＮにマッピングされる、請求項７に記載のシステム。
【請求項９】
前記異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に仮想ノードをマッピングする工程は、前記所与のクラウド要求の仮想ノードＶＮがすべてマッピングされているか否かを確認する工程を更に含み、前記ＶＮのうちの少なくとも１つがまだマッピングされていない場合は、前記所与のクラウド要求の前記仮想ノードＶＮのうちのいずれもまだマッピングされていない物理ノードＰＮのセットが見つけられ、これらのノードは、少なくとも前記仮想ノードＶＮによってリクエストされている数の、異なるタイプのリソースを含み、そうでない場合は、各仮想リンクＶＬに対して、前記仮想リンクＶＬの仮想ノードＶＮがマッピングされた物理ノードＰＮ間の最短距離に基づき、最適スペクトル及び到達可能性制約の充足を必要とする変調フォーマットが見つけられる、請求項７に記載のシステム。
【請求項１０】
前記推定されるスペクトルリソースの降順で仮想リンクを並べる工程は、各仮想リンクＶＬに対して、前記仮想リンクＶＬの仮想ノードＶＮがマッピングされた物理ノードＰＮ間の最短距離に基づき、続いて、最適スペクトルを必要とし、かつ到達可能性制約を充足する変調フォーマットを見つける工程と、関数に従って、降順でクラウドリクエストの仮想リンクＶＬを並べる工程と、を含む、請求項７に記載のシステム。
【請求項１１】
前記物理経路上で仮想リンクをマッピングする工程は、
リストの先頭から仮想ノードＶＮを選択し、各到達可能性要件及びリクエストされた回線速度に基づいて、仮想ノードＶＮがマッピングされた物理ノードＰＮに接続する最短経路ｋのそれぞれに対して、実施可能な変調フォーマットのセットを決定する工程と、
ＶＮがマッピングされたＰＮに接続する最短経路ｋのそれぞれのビット−マップを求める工程であって、経路のビット−マップは、各変調フォーマットごとに、経路に沿ったすべての物理リンクのビット−マップにおいて、ビット単位の論理エンド演算を行うことによって、決定される、工程と、
必要な総スペクトルを決定し、連続波長スロットが経路ｋのビット−マップ上の変調フォーマットに対して利用可能となる、波長スロットの数の、連続波長スロットがマッピング可能となる、可能な波長スロット総数に対する比率に基づく、変調フォーマットを用いた、経路上での前記ＶＬのマッピングの確率を決定する工程と、
前記仮想リンクＶＬに対して最大確率を有する経路及び変調フォーマットを選択し、該最大確率が０であるか否かを確認する工程と、を含む、請求項１に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の相互参照）
本出願は、２０１３年６月２４日出願の仮出願第６１／８３８，４６２号に対する優先権を主張し、その内容は、参照により本明細書に援用される。本出願は、２０１４年６月２３日に出願の、発明の名称が「Ｎｅｔｗｏｒｋ  Ｆｏｌｌｏｗｅｄ  ｂｙ  Ｃｏｍｐｕｔｅ  Ｌｏａｄ  Ｂａｌａｎｃｉｎｇ  Ｐｒｏｃｅｄｕｒｅ  ｆｏｒ  Ｅｍｂｅｄｄｉｎｇ  Ｃｌｏｕｄ  Ｓｅｒｖｉｃｅｓ  ｉｎ  Ｓｏｆｔｗａｒｅ−Ｄｅｆｉｎｅｄ  Ｆｌｅｘｉｂｌｅ−Ｇｒｉｄ  Ｏｐｔｉｃａｌ  Ｔｒａｎｓｐｏｒｔ  Ｎｅｔｗｏｒｋｓ」である、同時係属の米国特許出願第１４／３１２，６１０号に関連する。
【背景技術】
【０００２】
本発明は、概して、光通信、より具体的には、ソフトウェア・デファインド・フレキシブル・グリッド光伝達網における、クラウドサービスの組込みのための、コンピュート後ネットワーク負荷分散（ｃｏｍｐｕｔｅ  ｆｏｌｌｏｗｅｄ  ｂｙ  ｎｅｔｗｏｒｋ  ｌｏａｄ  ｂａｌａｎｃｉｎｇ）手順に関する。
【０００３】
ソフトウェア・デファインド・ネットワーク（ＳＤＮ）アーキテクチャーにより、マルチベンダー、マルチテクノロジー、マルチレイヤー通信をサポートし、かつ、サービスとしてインフラストラクチャを提供するネットワークプログラマビリティが可能になる。近年では、低干渉、長リーチ、消費電力のより少ない大容量伝送といった光伝達による利点を活用するために、ＩＰ／イーサネット（登録商標）ベースＳＤＮアーキテクチャー内に、光伝達を集約する試みが行われている。このようなネットワークは、光伝達ＳＤＮ（Ｏｐｔｉｃａｌ  Ｔｒａｎｓｐｏｒｔ  ＳＤＮ）と呼ばれる。光伝達ＳＤＮは、伝送中のフレキシビリティ及びプログラマビリティを可能にすることのほか、トランスポンダー及びＲＯＡＤＭなどのネットワーク要素の切替え、フレキシブル・グリッド・チャンネルのマッピングなど、光チャンネルの管理、及び物理ハードウェアから集中型コントローラーへの制御プレーン知能の抽出を行うことによって、実現し得る。
【０００４】
図１には、制御プレーンが、ネットワーク要素の物理ハードウェアから抽出されている光伝達ＳＤＮのアーキテクチャーを示し、ほとんどのネットワークコントロール及びマネジメント知能が、集中型コントローラー内に存在している。集中型コントローラーは、コントローラー及びネットワーク要素での標準インターフェイス上で、ＯｐｅｎＦｌｏｗなどの標準プロトコルを用いて、ネットワーク要素を制御する。制御プレーンの決定は、ルール、アクション及びポリシーの形態で存在し、ネットワーク要素は、接続点でのマッチアクションに基づくこれらの決定に適用する。したがって、光伝達ＳＤＮでは、ネットワークをソフトウェア・デファインド・オプティクス（ＳＤＯ）とオプティクス・デファインド・コントローラー（ＯＤＣ）とに分割する。
【０００５】
ソフトウェア・デファインド・オプティクスは、可変レートトランスポンダー、フレキシブル・グリッド・チャンネル・マッピング、及びカラーレス・ディレクションレス・コンテンションレス・グリッドレス（ＣＤＣＧ）ＲＯＡＤＭからなる。可変レートトランスポンダーは、種々の変調フォーマット及びＦＥＣコーディング用にプログラムすることができる。したがって、トランスポンダーは、異種の到達要件の可変伝送能力を提供することができる。フレキシブル・グリッド・チャンネル・マッピングにより、変更可能な量のスペクトルをチャンネルに割当て、スペクトル効率変調フォーマットを適用すること及び保護帯域を取り除くことによって、更に高いスペクトル効率を達成することができる。ＣＤＣＧ−ＲＯＡＤＭは、任意の下り方向上で、任意のスペクトル要件で、任意の波長で作動する接続を切替えるように、プログラムできる。更に、ノードにおいて、競合なく、接続をアド及びドロップすることができる。これらのハードウェア及びこれらの特徴により、ＳＤＯＮ最適化能力及びカスタマイズ能力の基盤が確立される。
【０００６】
オプティクス・デファインニング・コントローラー（ｏｐｔｉｃｓ  ｄｅｆｉｎｉｎｇ  ｃｏｎｔｒｏｌｌｅｒ）は、ＳＤＯのフレキシビリティを活用するために、ネットワークを管理し、ネットワークの最適化及びカスタマイズを行う。ＯＤＣの機能は、ネットワーク／コンピュートハイパーバイザー、オペレーティングシステム、ネットワークアプリケーション及びデータベース、及びデバッガ、及び管理プレーンに更に抽出される。これらのプレーンは、オープンな標準化されたインターフェイスによって分離されており、各レイヤーにて、独立して、同時かつ迅速な革新が可能である。例えば、クラウドリソースのマッピング、経路決定及びリソースの割当て、保護及び修復、デフラグメンテーション、エネルギー最適化などの、種々の制御プレーンの機能は、ＯＤＣにおいて、アプリケーション及びデータベースとして、インストールされる。ネットワーク／コンピュートハイパーバイザーは、ネットワーク操作を最適化し、かつ単純化するために、コントローラーに対して、物理レイヤーの実装の詳細を隠した状態で、データプレーンに対する分離及び共有機能、並びにネットワーク及びコンピューティングリソースの抽象化ビューを提供することにより、仮想化を提供する。オペレーティングシステムは、アプリケーション及びハイパーバイザーを実行するためのプログラム可能なプラットフォームを提供する。デバッガ及び管理プレーンは、ネットワークのパフォーマンスを監視しつつ、アクセス制御及びＱｏＳ管理を提供し、また、故障の隔離、ローカライゼーション及びリカバリーを行う。
【０００７】
近年、クラウドサービスは、新しいものをスクラッチから構築する代わりに、既存の配備されたインフラストラクチャ内で、リソースの共有によって、アプリケーションをサポートすることから、多くの関心を集めている。最近、ネットワークアプリケーションは、例えば、ソーシャル・ネットワーキング・アプリケーション（ＦａｃｅＢｏｏｋ、Ｔｗｉｔｔｅｒ及びＧｏｏｇｌｅ＋）、ｅ−ｓｃｉｅｎｃｅアプリケーション（Ｌａｒｇｅ  Ｈａｄｒｏｎ  Ｃｏｌｌｉｄｅｒなど）、コンテンツアプリケーション（ＮｅｔＦｌｉｘ）及び検索アプリケーション（Ｇｏｏｇｌｅ及びＢａｉｄｕ）など、ますますクラウド中心になってきている。クラウドアプリケーションは、ネットワークを介してデータセンター内で種々の計算、保存、ソフトウェア及びプラットフォーム指向リソースを相互接続することによってサポートされる。各データセンターは、提供する種類のサービスを最適化することを目的に構築される。例えば、Ｇｏｏｇｌｅデータセンターは、ウェブページの及び効率の良いインデックス化及びコンテンツ検索時間の最小化を目的に構築され、Ｆａｃｅｂｏｏｋデータセンターは、ユーザーコンテンツの保存の最大化、及びユーザーのソーシャルグループ内でのこれらのコンテンツの効率の良い管理及びリンク付けを提供するために構築され、Ａｍａｚｏｎ  ＥＣ２データセンターは、更に早い計算時間を提供するために構築されている。したがって、１つのデータセンターにより、すべてのリソースタイプが提供されなくてもよく、また、クラウドアプリケーションのすべての要件を最適に充足していなくてもよい。こうした状況では、残された課題は、異種リソースを提供するデータセンター間でクラウドリクエストをいかにマッピングするかということ、及びデータセンター間のネットワーク接続性をいかに確立するか、ということである。この問題は、クラウドサービス組込み問題と呼ばれている。本発明では、ソフトウェア・デファインド・フレキシブル・グリッド伝達ＳＤＮネットワーク上でのクラウドサービス組込み問題を調査する。問題点は、形式的には、以下のように定義される。
【０００８】
物理ネットワークトポロジ−Ｇ（Ｎ、Ｌ）を仮定し、ここで、Ｎは、物理ノード（ＰＮ）のセットを示し、Ｌは、物理ノードを相互接続する物理リンク（ＰＬ）のセットを示す。各ノードは、異なるタイプのリソースを提供し（例えば、１、２、３、．．，ｎなど）、各タイプｊに対して提供されるリソースの数Ｃｊｎが予め与えられている。また、ノードは、ＣＤＣＧ−ＲＯＡＤＭ及び可変レートトランスポンダーから構成される。ＣＤＣＧ−ＲＯＡＤＭにより、フレックスグリッド光学的接続の切替えが提供され、可変レートトランスポンダーにより、変調フォーマットＭが提供され、スペクトル効率Ｚｍビット／秒／Ｈｚ及び各変調フォーマットｍの伝送到達Ｄｍ  Ｋｍも与えられる。ファイバーは、総スペクトルＴ  ＴＨｚを提供する。クラウド要求は、Ｇ’（Ｖ、Ｅ、Ｃ、Ｌ）と定義され、Ｖは仮想ノード（ＶＮ）のセットであり、Ｅは仮想ノードに接続している仮想リンク（ＶＬ）のセットであり、Ｃは各仮想ノードｉでのリクエストされたリソースのセット（Ｃｉ１、Ｃｉ２、．．．、Ｃｉｎ）であり、Ｌは、仮想ノードｉとｊとの間のリクエストされた回線速度（ｌｉｎｅ  ｒａｔｅ）のセットｌｉｊである。クラウドリクエストの着信及び発信分布が与えられる。問題点は、組込まれるクラウド要求数が最大になるように、物理ノード上でクラウド要求の仮想ノードをいかにマッピングするのかということ（仮想ノード組込み問題）、及び物理リンク上でクラウド要求の仮想リンクをいかにマッピングするのかということ（仮想リンク組込み問題）である。仮想リンク組込み問題は、物理経路上で仮想リンクの経路をいかに決定するか、いかに波長を割り当て、スペクトルを配分するのか、また、いかに変調フォーマットを選択するのかといった、副次的な問題からなっている。ネットワークは、波長、スペクトル又は変調フォーマット変換能力をサポートしていないことが想定される。
【０００９】
クラウド組込みは、主に、仮想ノード組込み及び仮想リンク組込みから構成される。物理ノード及びリンクリソースは、複数のクラウド要求間で共有されるため、組込み手順では、リソース容量の制約を維持しつつ、これらのリソースを確実に分離させる必要がある。物理ノード上に仮想ノードをマッピングするとき、手順においては、異なる仮想ノードを同じ物理ノード上にマッピングできないようにすることを確実にする必要がある。フレックスグリッド伝達ＳＤＮにおいて、光学チャンネルを介して、物理経路で仮想リンクをマッピングするとき、手順においては、波長連続性、スペクトル連続性、スペクトル競合を確保する必要がある。波長連続性の制約は、光学チャンネル経路に沿ったすべてのリンク上における、同一動作波長でのスペクトルの割当てとして定義される。スペクトル連続性の制約は、光学チャンネル経路に沿ったすべてのリンク上における、同一スペクトル量の割当てとして定義される。スペクトル競合の制約は、同一ファイバーを介した経路のすべてのチャンネルへの重複しないスペクトルの割当てとして定義される。また、更に、手順では、仮想リンク及びそのネットワーク上の経路に対する変調フォーマットの選択は、仮想ノードがマッピングされる物理ノード間の少なくとも物理ユークリッド距離をサポートすべきである点を確認する必要がある。この制約は、到達可能性制約（ｒｅａｃｈａｂｉｌｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）とも呼ばれる。
【００１０】
クラウドサービス組込みは、仮想ノード組込み及び仮想リンク組込みの副次的な問題から構成される。仮想ノードが物理ノードごと割り当てられた（ｐｅｒ−ａｓｓｉｇｎｅｄ）場合、物理リンク上に仮想リンクを正しくマッピングする問題は、仮想ネットワーク組込み問題と呼ばれる。この仮想ネットワーク組込み問題は、ＩＰ／イーサネット（登録商標）ベースネットワークでは、光伝達を無視して、広範囲に解決されている。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかし、既知の技術と比較して、より短い時間間隔で、早急にクラウドサービス組込み問題を解決する手順が必要とされている。
【課題を解決するための手段】
【００１２】
本発明は、コンピュータによって、ソフトウェア・デファインド・フレキシブル・グリッド光伝達網上で、クラウド要求の組込みを実施する工程を含む方法に関し、該実施する工程は、該ネットワーク中の仮想ノードを、必要なリソースの総数の降順で並べる工程と、異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に該仮想ノードをマッピングする工程と、推定されるスペクトルリソースの降順で仮想リンクを並べる工程と、物理リンク上で該負荷を分散させつつ、物理経路上で仮想リンクをマッピングし、該仮想リンクの変調フォーマットを選択する工程と、波長及びスペクトルを該仮想リンクに割り当てる工程と、を含む。
【００１３】
本発明の代替的実施形態では、システムは、コンピュータによる、ソフトウェア・デファインド・フレキシブル・グリッド光伝達網上での、クラウド要求の組込みの実施を含み、該実施は、該ネットワーク中の仮想ノードを、必要なリソースの総数の降順で並べる工程と、異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に該仮想ノードをマッピングする工程と、推定されるスペクトルリソースの降順で仮想リンクを並べる工程と、物理リンク上で該負荷を分散させつつ、物理経路上で仮想リンクをマッピングし、該仮想リンクの変調フォーマットを選択する工程と、波長及びスペクトルを該仮想リンクに割り当てる工程と、を含む。
【００１４】
本発明のこれらの利点及び他の利点は、当業者には、以下の発明を実施するための形態及び添付図面を参照することによって、明らかであろう。
【図面の簡単な説明】
【００１５】
【図１】光伝達ソフトウェアデファインド網ＳＤＮの例示的なアーキテクチャーを示した図である。
【図２】本発明によるコンピュート後ネットワーク負荷分散の詳細を示すブロックを示した図である。
【図３】本発明を実施するための例示的なコンピュータ構成を示した図である。
【発明を実施するための形態】
【００１６】
本発明は、効率的な手順である、コンピュート後ネットワーク負荷分散（ＣＮＬＢ）を伴い、これは、最初に、異なるタイプの計算リソースを分散させつつ、物理ノード上に仮想ノードをマッピングし、最終的に、ネットワーク・スペクトル・リソースを分散させつつ、物理経路上に仮想リンクをマッピングさせることである。
【００１７】
管理の複雑性を低減するために、スペクトルは、ｑ  ＧＨｚの細分性（ｇｒａｎｕｌａｒｉｔｙ）にてスロットに分ける。スロットは、波長スロットと呼ばれている。したがって、スペクトルは、連続波長スロットのセット（ｃｏｎｓｅｃｕｔｉｖｅ  ｗａｖｅｌｅｎｇｔｈ  ｓｌｏｔ）によって表すことが可能であり、その中で、最初の波長スロットインデックスは、光学チャンネルの波長として示される。したがって、ネットワークは、全部でｃｅｉｌｉｎｇ（Ｔ／ｑ）の波長スロットから構成される［注記：ｃｅｉｌｉｎｇ（．）及びｆｌｏｏｒ（．）は、それぞれ、括弧内で限定された値に対する、天井関数及び床関数の数学演算を示す］。各波長スロットの状態は、２値変数で表され；「１」は、波長スロットを利用できることを示し、「０」は、波長スロットが占有されていることを示す。ファイバーのスペクトル状態は、ファイバーのビット−マップと呼ばれている２値ベクトルとして示される。
【００１８】
本手順では、各ノードペア間の最短経路ｋ（ｋ−ｓｈｏｒｔｅｓｔ  ｒｏｕｔｅ）までを事前に計算する（ｋ≦｜Ｎ｜）。本手順では、最初に、ノードリソース上に負荷分散を行いつつ、物理ノード（ＰＮ）上に仮想ノード（ＶＮ）をマッピングする。ＶＮは、必要な異なるタイプのリソースの総数の降順に並べられる。これらのＶＮは、順次、降順でＰＮ上にマッピングされる。ＶＮは、所与のクラウド要求からのＶＮのうちのいずれもまだマッピングされていないＰＮに対してマッピングされ得、このＰＮは、少なくとも必要な数の、ＶＮによってリクエストされた異なるタイプのリソースを含む必要がある。これらのＰＮの中から、異なるタイプのリソース数を最大にするよう、利用可能リソース数対リソース総数の最大比率を有するＰＮが選択される。ＶＮのうちの少なくとも１つがマッピングできない場合、本手順により、クラウド要求がブロックされる。
【００１９】
ＶＮのマッピング後、ネットワークリソース上で負荷の分散を行いつつ、物理リンク（ＰＬ）上に仮想リンク（ＶＬ）をマッピングする。各ＶＬ（ｉ，ｊ）に対して、本手順では、まず必要な量のスペクトルリソースｆｉｊを推定する。ｆｉｊは、ＶＮ、ｉ及びｊがマッピングされるＰＮ間のホップｄｉｊの観点からの最短距離と、必要な最低スペクトルＡｉｊとの積として定義され、Ａｉｊは、少なくとも距離ｈｉｊに到達可能な最もスペクトル効率の高い変調フォーマットから決定され、ｈｉｊは、ＶＮ、ｉとｊとの間のＫｍの観点からの物理（ユークリッド）距離である。本手順では、ＶＬを必要なスペクトル推定値の降順に並べ、これらのＶＬを以下のように１つずつマッピングする。
【００２０】
本手順では、各到達可能性要件に基づいて、ＶＮ、ｉ及びｊがマッピングされたＰＮに接続する最短経路ｋのそれぞれに対して、実施可能な変調フォーマットのセット、Ｍｉｊｋを決定する。次の工程において、本手順では、変調フォーマットｍを使用した、物理経路ｋ上でのＶＬ（ｉ，ｊ）のマッピングの確率Ｐｉｊｋｍを決定する。この確率を求めるために、本方法は、まず、ＶＮ、ｉ及びｊがマッピングされるＰＮに接続する最短経路ｋのそれぞれのビット−マップを求める。経路のビット−マップは、経路に沿ったすべての物理リンクのビット−マップにおいて、ビット単位の論理エンド演算（ｂｉｔ−ｗｉｓｅ  ｌｏｇｉｃａｌ  ｅｎｄ  ｏｐｅｒａｔｉｏｎ）を行うことによって、決定される。その後、本手順では、変調フォーマットｍを用いて、経路ｋ上で回線速度ｌｉｊをサポートするために、必要なスペクトルＳｉｊｋｍ＝ｃｅｉｌｉｎｇ（ｌｉｊ／Ｚｍ）を決定する。次の工程では、本手順では、経路ｋのビット−マップにおいて、少なくとも［ｃｅｉｌｉｎｇ（Ｓｉｊｋｍ／ｑ）］の連続スロットが使用可能となる、波長スロットの数を求める。求めた波長スロットの数対［ｆｌｏｏｒ（Ｔ／ｑ）−ｃｅｉｌｉｎｇ（Ｓｉｊｋｍ／ｑ）＋１］の比率は、確率Ｐｉｊｋｍを示し、ここで、［ｆｌｏｏｒ（Ｔ／ｑ）−ｃｅｉｌｉｎｇ（Ｓｉｊｋｍ／ｑ）＋１］は、少なくとも［ｃｅｉｌｉｎｇ（Ｓｉｊｋｍ／ｑ）］の連続波長スロットが利用可能となる、潜在的波長スロットの総数を示す。次の工程において、本手順では、確率Ｐｉｊｋｍが最大になる経路ｋ及び変調フォーマットｍを選択する。Ｐｉｊｋｍ＝０である場合、本手順では、接続をブロックし、事前に割り当てたノードリソース及びリンクリソースを解放し、そうでない場合、本手順では、［ｃｅｉｌｉｎｇ（Ｓｉｊｋｍ／ｑ）］の連続波長スロットが、選択されたｋ及びｍに対して利用可能な、最も低い波長スロットを見つけ、変調フォーマットｍに対して選択された経路ｋ上で求められた波長スロットに、ＶＬを供給する。最終的に、本手順では、すべてのＶＬが供給されているか否かを確認する。ＶＬのうちの少なくとも１つがまだ供給されていない場合、本手順では、ＶＬマッピング手順を繰り返し、そうでない場合は、本手順は、終了する。
【００２１】
図２に示すように、フローチャートによって、詳細な手順を説明する。
【００２２】
１０１：本手順では、所与のクラウドリクエストのＶＮを、リクエストされた異なるタイプのリソースの総数の降順に並べる。
【００２３】
１０２：本手順では、所与のクラウド要求のＶＮのうちのいずれもまだマッピングされていないＰＮのセットを見つけ出し、これらのノードは、少なくともＶＮによってリクエストされている数の、異なるタイプのリソースを含む。
【００２４】
１０３：本手順では、前記ＰＮのセットが空であるか否かを確認する。セットが空である場合、本手順から、工程１１４に進む。セットが空でない場合、本手順から、工程１０４に進む。
【００２５】
１０４：本手順では、前記ＶＮを、各リソースタイプごとに、利用可能なリソース数の、提供されたリソース数に対する累積率を最大化するＰＮにマッピングする。
【００２６】
１０５：本手順では、所与のクラウド要求のＶＮがすべてマッピングされているか否かを確認する。ＶＮのうちの少なくとも１つがまだマッピングされていない場合、本手順から、工程１０２に進み、そうでない場合は、本手順から、工程１０６に進む。
【００２７】
１０６：本手順では、各ＶＬ（ｉ，ｊ）に対し、そのＶＬのＶＮ、ｉ及びｊがマッピングされたＰＮ間の最短距離ｈｉｊに基づいて、最適スペクトルＡｏを必要とし、かつ到達可能性制約を充足する変調フォーマットを見つける。
【００２８】
１０７：本手順では、関数ｆｉｊ＝（Ａｉｊ＊ｄｉｊ）により、降順にクラウドリクエストのＶＬを並べる。
【００２９】
１０８：本手順では、リストの先頭からＶＮ（ｉ，ｊ）を選択し、各到達可能性要件及びリクエストされた回線速度に基づいて、ＶＮ、ｉ及びｊがマッピングされたＰＮに接続する最短経路ｋのそれぞれに対して、実施可能な変調フォーマットのセット、Ｍｉｊｋを決定する。
【００３０】
１０９：本手順では、ＶＮ、ｉ及びｊがマッピングされたＰＮに接続する最短経路ｋのそれぞれのビット−マップを求める。経路のビット−マップは、経路に沿ったすべての物理リンクのビット−マップにおいて、ビット単位の論理エンド演算（ｂｉｔ−ｗｉｓｅ  ｌｏｇｉｃａｌ  ｅｎｄ  ｏｐｅｒａｔｉｏｎ）を行うことによって、決定される。
【００３１】
１１０：本手順では、各変調フォーマットｍ∈Ｍｉｊｋに対して、必要な総スペクトルＳｉｊｋｍ＝ｃｅｉｌｉｎｇ（ｌｉｊ／Ｚｍ）を決定する。
【００３２】
１１１：本手順では、変調フォーマットｍを用いた、経路ｋ上でのＶＬ（ｉ，ｊ）のマッピングの確率Ｐｉｊｋｍを決定する。Ｐｉｊｋｍは、［ｃｅｉｌｉｎｇ（Ｓｉｊｋｍ／ｑ）］の連続波長スロットが、経路ｋのビット−マップ上の変調フォーマットｍに対して利用可能となる、波長スロットの数の、［ｃｅｉｌｉｎｇ（Ｓｉｊｋｍ／ｑ）］の連続波長スロットがマッピング可能となる、可能な波長スロット総数［ｆｌｏｏｒ（Ｔ／ｑ）−ｃｅｉｌｉｎｇ（Ｓｉｊｋｍ／ｑ）＋１］に対する比率である。
【００３３】
１１２：本手順は、ＶＬ（ｉ，ｊ）に対して、最大Ｐｉｊｋｍを有する、経路ｋ及び変調フォーマットｍ∈Ｍｉｊｋを選択する。
【００３４】
１１３：本手順では、最大確率Ｐｉｊｋｍが０であるか否かを確認する。最大確率が０である場合、本手順から、工程１１４に進み、そうでない場合は、本手順から、工程１１５に進む。
【００３５】
１１４：本手順では、事前に割り当てたノード及びスペクトルリソースを解放した後、クラウド要求をブロックする。
【００３６】
１１５：本手順では、［ｃｅｉｌｉｎｇ（Ｓｉｊｋｍ／ｑ）］の連続波長スロットが、選択されたｍ及びｋに対して利用可能となる、最も低い波長のスロットを見つけ、ｉ及びｊがマッピングされたＰＮ間で選択された経路ｋ上で、見つけた波長スロットに、ＶＬを供給する。
【００３７】
１１６：本手順では、すべてのＶＬがすでにマッピングされているか否かを確認する。ＶＮのうちの少なくとも１つがまだマッピングされていない場合、本手順から、工程１０８に進み、そうでない場合は、本手順は、終了する。
【００３８】
本発明は、ハードウェア、ファームウェア又はソフトウェア又はこれら３つの組み合わせにおいて実装されてよい。好ましくは本発明は、プロセッサ、データ・ストレージ・システム、揮発性及び非揮発性のメモリ及び／又はストレージ要素、少なくとも１つの入力装置及び少なくとも１つの出力装置を有するプログラム可能なコンピュータで実行されるコンピュータプログラムで実装される。更なる詳細は、米国特許第８３８０５５７号に記載され、その内容は、参照により援用される。
【００３９】
例として、本システムをサポートするコンピュータのブロック図を次の図３において説明する。コンピュータは、好ましくは、プロセッサ、ランダムアクセスメモリ（ＲＡＭ）、プログラムメモリ（好ましくは、フラッシュＲＯＭなどの書込み可能な読み取り専用メモリ（ＲＯＭ））、及びＣＰＵバスによって連結されている入力／出力（Ｉ／Ｏ）制御装置を含む。コンピュータは、ハードディスク及びＣＰＵバスを連結したハードドライブ制御装置を任意に含んでもよい。ハードディスクは、本発明などのアプリケーションプログラム及びデータの保存に使用してもよい。あるいは、アプリケーションプログラムは、ＲＡＭ又はＲＯＭに保存してもよい。Ｉ／Ｏ制御装置は、Ｉ／ＯバスからＩ／Ｏインターフェイスを用いて、連結させる。Ｉ／Ｏインターフェイスは、シリアルリンク、ローカルエリアネットワーク、ワイヤレスリンク、及びパラレルリンクなどの、通信リンク上で、アナログ又はデジタル形態にてデータの送受信を行う。任意により、ディスプレイ、キーボード、及びポインティングデバイス（マウス）を、Ｉ／Ｏバスに接続してもよい。あるいは、Ｉ／Ｏインターフェイス、ディスプレイ、キーボード及びポインティングデバイス用に個別接続（個別バス）を、使用してもよい。プログラム可能な処理システムは、事前にプログラムされていてもよいし、別のソース（例えば、フロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ又は別のコンピュータ）からプログラムをダウンロードすることによって、プログラム（及び再プログラム）されてもよい。
【００４０】
各コンピュータプログラムは、本明細書に記載された手順を実施するために、ストレージ媒体又は装置をコンピュータによって読み出されるときに、コンピュータの操作を構成し、制御するために、汎用又は専用のプログラム可能なコンピュータによって読み取り可能な機械読取り可能ストレージ媒体又は装置（例えば、プログラムメモリ又は磁気ディスク）に有形物として保存される。また、本発明に関するシステムは、コンピュータプログラムと共に構成される、コンピュータ読み取り可能なストレージ媒体中に組込まれるものと考えられてもよく、ここで、このように構成されたストレージ媒体は、コンピュータを特定の事前に定義された方法で操作して、本明細書に記載される機能を実施させる。
【００４１】
以上より、本発明の主要機能により、クラウドサービス組込み問題の解決策を迅速に見つけることができ、本発明を、パス計算装置（ＰＣＥ）などの光学制御プレーンにおいて、適用でき、ソフトウェア・デファインド・コントローラーにおける適用としては、本発明の適用により、合理的かつ正しい数のクラウド要求も最も素早い時間で組込むことができるため、ソフトウェア・デファインド・オプティクス伝達光網を拡張できることが理解できよう。
【００４２】
以上は、あらゆる点で説明的かつ例示的なものであり、限定的なものではないことが理解されるべきであり、本明細書に開示された本発明の範囲は、発明を実施するための形態から決定されるべきではなく、むしろ、特許法によって認められる限りの範囲において解釈されるように、請求項から決定されるべきである。本明細書に示され、記載された実施形態は、単に本発明の原理を例示的に示すのみであり、当業者は、本明細書の範囲及び趣旨を逸脱することなく、様々な変更形態を実施し得ることを理解すべきである。当業者は、本発明の範囲及び趣旨を逸脱することなく、様々な他の特徴の組み合わせを実施できるであろう。
【図２】
2016512001.tif 000003
【図３】
2016512001.tif 000004
【図１】
2016512001.tif 000005
【手続補正書】
【提出日】平成27年8月24日(2015.8.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コンピュータによって、ソフトウェア・デファインド・フレキシブル・グリッド光伝達網上で、クラウド要求の組込みを実施する工程を含む方法であって、該実施する工程は、
該ネットワーク中の仮想ノードを、必要なリソースの総数の降順で並べる工程と、
異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に該仮想ノードをマッピングする工程と、
推定されるスペクトルリソースの降順で仮想リンクを並べる工程と、
物理リンク上で該負荷を分散させつつ、物理経路上で仮想リンクをマッピングし、該仮想リンクの変調フォーマットを選択する工程と、
波長及びスペクトルを該仮想リンクに割り当てる工程と、を含む、方法。
【請求項２】
前記異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に仮想ノードをマッピングする工程は、所与のクラウド要求の前記仮想ノードＶＮのうちのいずれもまだマッピングされていない物理ノードＰＮのセットを見つける工程を含み、これらのノードは、少なくとも前記仮想ノードＶＮによってリクエストされている数の、異なるタイプのリソースを含む、請求項１に記載の方法。
【請求項３】
前記異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に仮想ノードをマッピングする工程は、物理ノードＰＮのセットが空であるか否かを確認する工程を更に含み、該セットが空である場合、前記事前に割り当てたノード及びスペクトルリソースを解放した後、前記クラウド要求がブロックされ、該セットが空でない場合、前記仮想ノードＶＮが、各リソースタイプごとに、利用可能なリソース数の、提供されたリソース数に対する累積率を最大化する物理ノードＰＮにマッピングされる、請求項１に記載の方法。
【請求項４】
前記異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に仮想ノードをマッピングする工程は、前記所与のクラウド要求の仮想ノードＶＮがすべてマッピングされているか否かを確認する工程を更に含み、前記ＶＮのうちの少なくとも１つがまだマッピングされていない場合は、前記所与のクラウド要求の前記仮想ノードＶＮのうちのいずれもまだマッピングされていない物理ノードＰＮのセットが見つけられ、これらのノードは、少なくとも前記仮想ノードＶＮによってリクエストされている数の、異なるタイプのリソースを含み、そうでない場合は、各仮想リンクＶＬに対して、前記仮想リンクＶＬの仮想ノードＶＮがマッピングされた物理ノードＰＮ間の最短距離に基づき、最適スペクトル及び到達可能性制約の充足を必要とする変調フォーマットが見つけられる、請求項１に記載の方法。
【請求項５】
前記推定されるスペクトルリソースの降順で仮想リンクを並べる工程は、各仮想リンクＶＬに対して、前記仮想リンクＶＬの仮想ノードＶＮがマッピングされた物理ノードＰＮ間の最短距離に基づき、続いて、最適スペクトルを必要とし、かつ到達可能性制約を充足する変調フォーマットを見つける工程と、関数に従って、降順でクラウドリクエストの仮想リンクＶＬを並べる工程と、を含む、請求項１に記載の方法。
【請求項６】
前記物理経路上で仮想リンクをマッピングする工程は、
リストの先頭から仮想ノードＶＮを選択し、各到達可能性要件及びリクエストされた回線速度に基づいて、仮想ノードＶＮがマッピングされた物理ノードＰＮに接続する最短経路ｋのそれぞれに対して、実施可能な変調フォーマットのセットを決定する工程と、
ＶＮがマッピングされたＰＮに接続する最短経路ｋのそれぞれのビット−マップを求める工程であって、経路のビット−マップは、各変調フォーマットごとに、経路に沿ったすべての物理リンクのビット−マップにおいて、ビット単位の論理エンド演算を行うことによって、決定される、工程と、
必要な総スペクトルを決定し、連続波長スロットが経路ｋのビット−マップ上の変調フォーマットに対して利用可能となる、波長スロットの数の、連続波長スロットがマッピング可能となる、可能な波長スロット総数に対する比率に基づく、変調フォーマットを用いた、経路上での前記ＶＬのマッピングの確率を決定する工程と、
前記仮想リンクＶＬに対して最大確率を有する経路及び変調フォーマットを選択し、該最大確率が０であるか否かを確認する工程と、を含む、請求項１に記載の方法。
【請求項７】
コンピュータによる、ソフトウェア・デファインド・フレキシブル・グリッド光伝達網上での、クラウド要求の組込みの実施を含むシステムであって、該実施は、
該ネットワーク中の仮想ノードを、必要なリソースの総数の降順で並べる工程と、
異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に該仮想ノードをマッピングする工程と、
推定されるスペクトルリソースの降順で仮想リンクを並べる工程と、
物理リンク上で該負荷を分散させつつ、物理経路上で仮想リンクをマッピングし、該仮想リンクの変調フォーマットを選択する工程と、
波長及びスペクトルを該仮想リンクに割り当てる工程と、を含む、システム。
【請求項８】
前記異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に仮想ノードをマッピングする工程は、物理ノードＰＮのセットが空であるか否かを確認する工程を更に含み、該セットが空である場合、前記事前に割り当てたノード及びスペクトルリソースを解放した後、前記クラウド要求がブロックされ、該セットが空でない場合、前記仮想ノードＶＮが、各リソースタイプごとに、利用可能なリソース数の、提供されたリソース数に対する累積率を最大化する物理ノードＰＮにマッピングされる、請求項７に記載のシステム。
【請求項９】
前記異なるタイプのリソースに対して、負荷を分散させつつ、物理ノード上に仮想ノードをマッピングする工程は、前記所与のクラウド要求の仮想ノードＶＮがすべてマッピングされているか否かを確認する工程を更に含み、前記ＶＮのうちの少なくとも１つがまだマッピングされていない場合は、前記所与のクラウド要求の前記仮想ノードＶＮのうちのいずれもまだマッピングされていない物理ノードＰＮのセットが見つけられ、これらのノードは、少なくとも前記仮想ノードＶＮによってリクエストされている数の、異なるタイプのリソースを含み、そうでない場合は、各仮想リンクＶＬに対して、前記仮想リンクＶＬの仮想ノードＶＮがマッピングされた物理ノードＰＮ間の最短距離に基づき、最適スペクトル及び到達可能性制約の充足を必要とする変調フォーマットが見つけられる、請求項７に記載のシステム。
【請求項１０】
前記推定されるスペクトルリソースの降順で仮想リンクを並べる工程は、各仮想リンクＶＬに対して、前記仮想リンクＶＬの仮想ノードＶＮがマッピングされた物理ノードＰＮ間の最短距離に基づき、続いて、最適スペクトルを必要とし、かつ到達可能性制約を充足する変調フォーマットを見つける工程と、関数に従って、降順でクラウドリクエストの仮想リンクＶＬを並べる工程と、を含む、請求項７に記載のシステム。
【請求項１１】
前記物理経路上で仮想リンクをマッピングする工程は、
リストの先頭から仮想ノードＶＮを選択し、各到達可能性要件及びリクエストされた回線速度に基づいて、仮想ノードＶＮがマッピングされた物理ノードＰＮに接続する最短経路ｋのそれぞれに対して、実施可能な変調フォーマットのセットを決定する工程と、
ＶＮがマッピングされたＰＮに接続する最短経路ｋのそれぞれのビット−マップを求める工程であって、経路のビット−マップは、各変調フォーマットごとに、経路に沿ったすべての物理リンクのビット−マップにおいて、ビット単位の論理エンド演算を行うことによって、決定される、工程と、
必要な総スペクトルを決定し、連続波長スロットが経路ｋのビット−マップ上の変調フォーマットに対して利用可能となる、波長スロットの数の、連続波長スロットがマッピング可能となる、可能な波長スロット総数に対する比率に基づく、変調フォーマットを用いた、経路上での前記ＶＬのマッピングの確率を決定する工程と、
前記仮想リンクＶＬに対して最大確率を有する経路及び変調フォーマットを選択し、該最大確率が０であるか否かを確認する工程と、を含む、請求項７に記載のシステム。
【国際調査報告】
2016512001.tif 000006
2016512001.tif 000007