(57)【要約】方法は、光転送ソフトウェア定義型ネットワークにおいて時間変動するトラフィックデマンドをプロビジョニングすることを提供する。この方法は、ベストエフォートトラフィック用のある量の帯域幅を事前プロビジョニングすることを含む。この方法は、プロセッサを用いて、反復シミュレーテッドアニーリング型トラフィックプロビジョニング手順を繰返し適用して、１組の反復においてベストエフォートトラフィック用の候補帯域幅を決定することをさらに含む。この方法は、また、所与のブロッキング要件β未満の対応するブロッキング値を有し、かつ他の候補帯域幅と比較して最小の量のスペクトルを必要とする、特定の候補帯域幅を選択することを含む。繰り返し適用するステップは、各反復においてベストエフォートトラフィック用の前記ある量の帯域幅を変動させて、候補帯域幅を決定することを含む。繰り返して適用するステップは、各反復において、ベストエフォートトラフィック用の前記ある量の帯域幅の中で、隣接するチャネルの間のある量の共有帯域幅を変動させて、候補帯域幅をさらに決定することをさらに含む。
2016524430.tif 000002
【特許請求の範囲】
【請求項１】
光転送ソフトウェア定義型ネットワークにおいて時間変動するトラフィックデマンドをプロビジョニングする方法であって、
ベストエフォートトラフィック用のある量の帯域幅を事前プロビジョニングすることと、
プロセッサを用いて、反復シミュレーテッドアニーリング型トラフィックプロビジョニング手順を繰返し適用して、１組の反復において前記ベストエフォートトラフィック用の候補帯域幅を決定することと、
所与のブロッキング要件β未満の対応するブロッキング値を有し、かつ、前記ベストエフォートトラフィック用の前記候補帯域幅のうちの他の帯域幅と比較して最小の量のスペクトルを必要とする、前記ベストエフォートトラフィック用の前記候補帯域幅のうちの特定の１つを選択することとを含み、
繰り返し適用する前記ステップが、
前記反復のそれぞれにおいてベストエフォートトラフィック用の前記ある量の帯域幅を変動させて、前記ベストエフォートトラフィック用の候補帯域幅を決定することと、
前記反復のそれぞれにおいて、ベストエフォートトラフィック用の前記ある量の帯域幅の中で、隣接するチャネルの間のある量の共有帯域幅を変動させて、前記ベストエフォートトラフィック用の前記候補帯域幅をさらに決定することと、を含む、方法。
【請求項２】
前記ベストエフォートトラフィック用の前記候補帯域幅が、前記反復シミュレーテッドアニーリング型トラフィックプロビジョニング手順に適用されるルーティング／波長割当て／スペクトル割振り手順に応答して求められる、請求項１に記載の方法。
【請求項３】
前記ルーティング／波長割当て／スペクトル割振り手順が、
Ｋ個の最短ルート上のスペクトルを求めることと、
前記Ｋ個の最短ルートから、前記Ｋ個の最短ルートの他のルートに対して最短の波長のスペクトルが利用可能である所与のルートを選択することと、を含む、請求項２に記載の方法。
【請求項４】
前記ルーティング／波長割当て／スペクトル割振り手順が、
前記所与のルートのスペクトルプロファイルを決定することと、
空き波長スロットおよび共有波長スロットのうちの少なくとも一方を少なくとも所定の最小数だけ有する、最短の利用可能な波長のスペクトルアイランドを、前記スペクトルプロファイル中で探索することと、をさらに含む、請求項３に記載の方法。
【請求項５】
前記スペクトルプロファイルが、占有、プロビジョニング、共有、および空きを含む所定の可能な１組のスペクトルプロファイル状態の中から決定される、請求項４に記載の方法。
【請求項６】
ベストエフォートトラフィック用の前記ある量の帯域幅を変動させる前記ステップが、前記ベストエフォートトラフィック用の異なる量の帯域幅を使用して、異なるブロッキング確率を有するベストエフォートトラフィックに対応する異なる量のスペクトルを評価することを含む、請求項１に記載の方法。
【請求項７】
ある量の共有帯域幅を変動させる前記ステップが、隣接するチャネル間の異なる量の共有帯域幅を使用して、異なるブロッキング確率を有するベストエフォートトラフィックに対応する異なる量のスペクトルを評価することを含む、請求項１に記載の方法。
【請求項８】
前記ベストエフォートトラフィック用の前記ある量の帯域幅、および前記ある量の共有帯域幅を、前記反復のそれぞれにおいて増加させる、請求項１に記載の方法。
【請求項９】
前記反復シミュレーテッドアニーリング型トラフィックプロビジョニング手順が、
現在のトラフィックデマンド構成を、無作為な順序の複数の時間変動するトラフィックデマンドとして定義することと、
新たなトラフィックデマンド構成を、降順の前記複数の時間変動するトラフィックデマンドとして定義して、収束時間を短縮することとをさらに含み、前記降順が、前記複数の時間変動するトラフィックデマンドそれぞれのコスト関数に基づいている、請求項１に記載の方法。
【請求項１０】
前記新たなトラフィックデマンド構成が、前記複数の時間変動するトラフィックデマンドから無作為に選択された２つの隣接するトラフィックデマンドの順序を交換することによって定義される、請求項９に記載の方法。
【請求項１１】
反復して適用する前記ステップが、前記複数の時間変動するトラフィックデマンドに、降順で、ルーティング／波長割当て／スペクトル割振り手順を適用することを含む、請求項９に記載の方法。
【請求項１２】
前記新たなトラフィックデマンド構成のエネルギーの量が前記現在のトラフィックデマンド構成のエネルギーの量未満になったのに応答して、前記現在のトラフィックデマンド構成を前記新たなトラフィックデマンド構成で置換することをさらに含む、請求項９に記載の方法。
【請求項１３】
前記複数の時間変動するトラフィックデマンドのそれぞれが、それぞれの要求される保証帯域幅と、前記ネットワーク中の発信元ノードと宛先ノードの間の最短ルート上のそれぞれのホップ数とのそれぞれの積として定義される、請求項９に記載の方法。
【請求項１４】
前記シミュレーテッドアニーリング型トラフィックプロビジョニング手順が、前記ベストエフォートトラフィック用に事前プロビジョニングされた帯域幅の量が対応するトランスポンダの容量と等しくなるまで実行される、請求項１に記載の方法。
【請求項１５】
光転送ソフトウェア定義型ネットワークにおいて時間変動するトラフィックデマンドをプロビジョニングする方法を実行するコンピュータ可読プログラムコードが実装されたコンピュータ可読記憶媒体を含むコンピュータプログラム製品であって、前記方法が、
ベストエフォートトラフィック用のある量の帯域幅を事前プロビジョニングすることと、
プロセッサを用いて、反復シミュレーテッドアニーリング型トラフィックプロビジョニング手順を繰返し適用して、１組の反復において前記ベストエフォートトラフィック用の候補帯域幅を決定することと、
所与のブロッキング要件β未満の対応するブロッキング値を有し、かつ前記ベストエフォートトラフィック用の前記候補帯域幅のうちの他の帯域幅と比較して最小の量のスペクトルを必要とする、前記ベストエフォートトラフィック用の前記候補帯域幅のうちの特定の１つを選択することとを含み、
繰り返し適用する前記ステップが、
前記反復のそれぞれにおいてベストエフォートトラフィック用の前記ある量の帯域幅を変動させて、前記ベストエフォートトラフィック用の候補帯域幅を決定することと、
前記反復のそれぞれにおいて、ベストエフォートトラフィック用の前記ある量の帯域幅の中で、隣接するチャネルの間のある量の共有帯域幅を変動させて、前記ベストエフォートトラフィック用の前記候補帯域幅をさらに決定することと、を含む、コンピュータプログラム製品。
【請求項１６】
前記ベストエフォートトラフィック用の前記候補帯域幅が、前記反復シミュレーテッドアニーリング型トラフィックプロビジョニング手順に適用されるルーティング／波長割当て／スペクトル割振り手順に応答して求められる、請求項１５に記載のコンピュータプログラム製品。
【請求項１７】
前記ルーティング／波長割当て／スペクトル割振り手順が、
Ｋ個の最短ルート上のスペクトルを求めることと、
前記Ｋ個の最短ルートから、前記Ｋ個の最短ルートの他のルートに対して最短の波長のスペクトルが利用可能である所与のルートを選択することと、を含む、請求項１６に記載のコンピュータプログラム製品。
【請求項１８】
前記ルーティング／波長割当て／スペクトル割振り手順が、
前記所与のルートのスペクトルプロファイルを決定することと、
空き波長スロットおよび共有波長スロットのうちの少なくとも一方を少なくとも所定の最小数だけ有する、最短の利用可能な波長のスペクトルアイランドを、前記スペクトルプロファイル中で探索することと、をさらに含む、請求項１７に記載のコンピュータプログラム製品。
【請求項１９】
前記スペクトルプロファイルが、占有、プロビジョニング、共有、および空きを含む所定の可能な１組のスペクトルプロファイル状態の中から決定される、請求項１８に記載のコンピュータプログラム製品。
【請求項２０】
前記反復シミュレーテッドアニーリング型トラフィックプロビジョニング手順が、
現在のトラフィックデマンド構成を、無作為な順序の複数の時間変動するトラフィックデマンドとして定義することと、
新たなトラフィックデマンド構成を、降順の前記複数の時間変動するトラフィックデマンドとして定義して、収束時間を短縮することとをさらに含み、前記降順が、前記複数の時間変動するトラフィックデマンドそれぞれのコスト関数に基づいている、請求項１５に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、参照により本明細書に組み込む、２０１３年８月７日出願の仮出願第61/863187号の優先権を主張する。
【０００２】
本発明は、信号処理に関し、さらに詳細には、ソフトウェア定義型フレキシブルグリッド転送ネットワークにおける時間変動するトラフィックのプロビジョニングに関する。
【背景技術】
【０００３】
時間変動するトラフィックデマンドに応じるフレキシブルグリッドネットワークを設計する際の未解決の問題は、所与の漸増トラフィックのブロッキング確率に対して所与のデマンドに対応するための最大所要スペクトルが最小となるように、適応光チャネルを用いて、どのようにこれらのデマンドをプロビジョニングするかということである。この問題は、時間変動するトラフィックのプロビジョニング問題と呼ばれる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来技術の上記その他の短所および欠点は、本発明の原理によって対処される。本発明の原理は、ソフトウェア定義型フレキシブルグリッド転送ネットワークにおける時間変動するトラフィックのプロビジョニングを対象とする。
【課題を解決するための手段】
【０００５】
本発明の原理の一態様によれば、光転送ソフトウェア定義型ネットワークにおいて時間変動するトラフィックデマンドをプロビジョニングする方法が提供される。この方法は、ベストエフォートトラフィック用のある量の帯域幅を事前プロビジョニングすることを含む。この方法は、プロセッサを用いて、反復シミュレーテッドアニーリング型トラフィックプロビジョニング手順を繰返し適用して、１組の反復においてベストエフォートトラフィック用の候補帯域幅を決定することをさらに含む。この方法は、また、所与のブロッキング要件β未満の対応するブロッキング値を有し、かつベストエフォートトラフィック用の候補帯域幅のうちの他の帯域幅と比較して最小の量のスペクトルを必要とする、ベストエフォートトラフィック用の候補帯域幅のうちの特定の１つを選択することを含む。繰り返し適用するステップは、反復のそれぞれにおいてベストエフォートトラフィック用のある量の帯域幅を変動させて、ベストエフォートトラフィック用の候補帯域幅を決定することを含む。繰り返し適用するステップは、反復のそれぞれにおいて、ベストエフォートトラフィック用のある量の帯域幅の中で、隣接するチャネルの間のある量の共有帯域幅を変動させて、ベストエフォートトラフィック用の候補帯域幅をさらに決定することをさらに含む。
【０００６】
本発明の原理の別の態様によれば、光転送ソフトウェア定義型ネットワークにおいて時間変動するトラフィックデマンドをプロビジョニングする方法を実行するコンピュータ可読プログラムコードが実装されたコンピュータ可読記憶媒体を含むコンピュータプログラム製品が提供される。この方法は、ベストエフォートトラフィック用のある量の帯域幅を事前プロビジョニングすることを含む。この方法は、プロセッサを用いて、反復シミュレーテッドアニーリング型トラフィックプロビジョニング手順を繰返し適用して、１組の反復においてベストエフォートトラフィック用の候補帯域幅を決定することをさらに含む。この方法は、また、所与のブロッキング要件β未満の対応するブロッキング値を有し、かつベストエフォートトラフィック用の候補帯域幅のうちの他の帯域幅と比較して最小の量のスペクトルを必要とする、ベストエフォートトラフィック用の候補帯域幅のうちの特定の１つを選択することを含む。繰り返し適用するステップは、反復のそれぞれにおいてベストエフォートトラフィック用のある量の帯域幅を変動させて、ベストエフォートトラフィック用の候補帯域幅を決定することを含む。繰り返し適用するステップは、反復のそれぞれにおいて、ベストエフォートトラフィック用のある量の帯域幅の中で、隣接するチャネルの間のある量の共有帯域幅を変動させて、ベストエフォートトラフィック用の候補帯域幅をさらに決定することをさらに含む。
【０００７】
上記その他の特徴および利点は、以下の例示的な実施形態の詳細な説明を添付の図面と関連付けて読めば明らかになるであろう。
【図面の簡単な説明】
【０００８】
本開示では、以下の図面を参照する好ましい実施形態の以下の説明において、詳細を提供する。
【図１】本発明の原理の一実施形態による、本発明の原理を適用することができる例示的な光転送ソフトウェア定義型ネットワーク（ＳＤＮ）アーキテクチャ１００を示す図である。
【図２】本発明の原理の一実施形態による、例示的な反復シミュレーテッドアニーリング型方法２００を示す図である。
【図３】本発明の原理の一実施形態による、例示的な反復シミュレーテッドアニーリング型トラフィックプロビジョニング方法３００を示す図である。
【図４】本発明の原理の一実施形態による、例示的なルーティング／波長割当て／スペクトル割振り（ＲＷＳＡ）方法４００を示す図である。
【図５】本発明の原理の一実施形態による、例示的なルーティング／波長割当て／スペクトル割振り（ＲＷＳＡ）方法４００を示す図である。
【発明を実施するための形態】
【０００９】
本発明の原理は、ソフトウェア定義型フレキシブルグリッド転送ネットワークにおける時間変動するトラフィックのプロビジョニングを対象とする。「トラフィックデマンド」および「要求」という用語は、本明細書では交換可能に使用されていることを理解されたい。同様に、「確保する」および「プロビジョニングする」という用語も、交換可能に使用されている。
【００１０】
一実施形態では、発明者等は、所与のブロッキング確率に対して隣接するチャネルの間で最大量のスペクトルを共有することによって、最小のスペクトル量で、時間変動するトラフィックデマンドをプロビジョニングする、反復シミュレーテッドアニーリング（ＩＳＡ：Iterative Simulated Annealing）型手順を提供する。第１の段階では、このＩＳＡ手順を使用して、所与のトラフィックデマンドについて、ｘＧｂ／ｓの保証トラフィック用、およびｙＧｂ／ｓの予測されるベストエフォート帯域幅用に、スペクトルをプロビジョニングする。本明細書で使用する「ベストエフォート帯域幅」という用語は、ベストエフォートトラフィック用にプロビジョニングされる帯域幅を意味する。本明細書で使用する「ベストエフォートトラフィック」という用語は、十分な帯域幅リソースが利用できない場合にはドロップされる可能性がある、優先順位の低いトラフィックを意味する。ベストエフォートトラフィックは、サービス品質保証制度（ＳＬＡ）の要件が緩い。ベストエフォートトラフィックは、デフォルトトラフィックとも呼ばれる。本明細書で使用する「保証トラフィック」という用語は、厳しいＳＬＡ要件を課された、ネットワーク中でプロビジョニングされなければならない、優先順位の高いトラフィックを意味する。帯域幅リソースが不足している間は、保証トラフィックの方を優先してプロビジョニングしなければならない。保証トラフィックは、優先トラフィックとも呼ばれる。ＩＳＡ手順は、予測されるベストエフォートトラフィック用に事前プロビジョニングされたｐＧｂ／ｓのスペクトルを隣接するチャネル間で共有することができるように、スペクトルのルーティングおよび割当てを行う。
【００１１】
次の段階では、時間変動するベストエフォートトラフィックの拡大および縮小を、ネットワークが定常状態に達するまで十分な時間にわたって動的に実行して、ベストエフォートトラフィックのブロッキングを決定する。この手順は、ベストエフォートトラフィック用のプロビジョニング帯域幅および共有帯域幅の量を増加させ、ベストエフォートトラフィック用に見込まれる潜在的な事前プロビジョニング帯域幅および共有帯域幅が考慮されるまで、この手順が繰り返される。最後に、ベストエフォートトラフィック用に見込まれる潜在的な帯域幅について求められた解の中から、この手順は、スペクトルの量が最小となるネットワークのブロッキング要件に合う解を選択する。
【００１２】
次に、ＩＳＡ手順に付随する多くの利点のうちのいくつかについて、簡単に説明する。ＩＳＡ手順は、時間変動するトラフィックデマンドに対応するネットワークを計画および設計するための有効なツールを提供するので有利である。さらに、ＩＳＡ手順は、ベストエフォートトラフィックの所与のブロッキング確率に対して最小のスペクトル量の範囲内で所与の時間変動するトラフィックデマンドを効果的にプロビジョニングする。さらに、ＩＳＡ手順は、所与のトラフィックブロッキング確率に対してスペクトルを最小限に抑えるという目的を有する時間変動するトラフィックのプロビジョニング問題に対処する第１の手順である。
【００１３】
図１は、本発明の原理の一実施形態による、本発明の原理を適用することができる例示的な光転送ソフトウェア定義型ネットワーク（ＳＤＮ：software definednetwork）アーキテクチャ１００を示す図である。この光転送ＳＤＮアーキテクチャ１００では、制御プレーンは、ネットワーク要素の物理ハードウェアから抽出され、ほとんどのネットワーク制御および管理知能は、中央制御装置、すなわちオプティクス定義制御装置（ＯＤＣ：optics defining controller）１９２にある。ＯＤＣ１９２は、制御装置およびネットワーク要素の標準化されたインタフェースを介してＯｐｅｎＦｌｏｗプロトコルなどの標準化されたプロトコルを用いてネットワーク要素を制御する。制御プレーンの判断は、ルール、アクション、およびポリシーの形態で現れ、ネットワーク要素は、これらの判断を接続におけるマッチアクションに基づいて適用する。したがって、光転送ＳＤＮ１００は、ネットワークを、複数のソフトウェア定義型オプティクス（ＳＤＯ）１９１とオプティクス定義制御装置（ＯＤＣ）１９２とに分割する。
【００１４】
ＯＤＣ１９２は、ネットワークを管理し、ＳＤＯ１９１のフレキシビリティを利用するようにネットワークの最適化およびカスタマイゼーションを実行する。ＯＤＣの機能性は、さらに、ネットワークハイパーバイザ１５１、ネットワークオペレーティングシステム１５２、図面では参照番号１５３で集合的に表されるネットワークアプリケーションおよびデータベース、ならびにデバッガおよび管理プレーン１５４として抽出される。これらのプレーン１５４は、オープンな標準化されたインタフェースによって分離されて、各層で独立して同時かつ急速なイノベーションを行うことができるようにしている。例えば、これらに限定されないが、ルーティング１６１、スケジューリング１６２、アクセス制御１６３、サービス品質（ＱｏＳ）管理１６４、クラウドリソースマッピング、リソース割振り、保護および復元、デフラグメンテーション、エネルギー最適化など（後の方は図示せず）、様々な制御プレーンの機能性は、アプリケーションおよびデータベースとしてＯＤＣ１９２にインストールされる。ネットワークハイパーバイザ１５１は、ネットワークの動作を最適化および簡略化するために、物理レイヤの実装の詳細を制御装置に対して隠しながら、データプレーンに分離および共有機能ならびにネットワークおよびコンピューティングリソースの抽象的なビューを提供することによって、仮想化を実現する。ネットワークオペレーティングシステム１５２は、アプリケーションおよびハイパーバイザの実行のためのプログラマブルプラットフォームを提供する。デバッガおよび管理プレーン１５４は、ネットワークのパフォーマンスを監視し、かつ、障害分離、局所化、および、回復を実行しながら、ネットワークアプリケーションとしてアクセス制御１６３およびＱｏＳ管理１６４を提供する。
【００１５】
ソフトウェア定義オプティクス（ＳＤＯ：software definedoptics）１９１は、プログラマブルトランスポンダ１７１と、カラーレスディレクションレスコンテンションレスグリッドレス（ＣＤＣＧ：colorless-directionless-contentionless-gridless）ＲＯＡＤＭ１７２と、増幅器１７３とを含む。
【００１６】
本発明の原理の１つまたは複数の実施形態によれば、発明者等は、ｙＧｂ／ｓとして表されるベストエフォートトラフィックが事前に保証トラフィックのための帯域幅とともに事前プロビジョニングされる反復シミュレーテッドアニーリング（ＩＳＡ：Iterative SimulatedAnnealing）手順を提供し、この事前プロビジョニング帯域幅ｙＧｂ／ｓの中で、この手順は、隣接するチャネル間で最大ｐＧｂ／ｓの帯域幅までを共有することを可能にする。したがって、動的なベストエフォートトラフィックは、実行中に０からｙＧｂ／ｓまで変動する可能性がある。このｙＧｂ／ｓの帯域幅は常にベストエフォートトラフィックによって占められるとは限らないので、ｙＧｂ／ｓの帯域幅についてプロビジョニングされたスペクトルは、隣接するチャネルの間で共有される可能性がある。この手順は、このスペクトルの一部（ｐ／ｙ）を、隣接するチャネルの間で共有することを可能にする。次の段階では、この手順は、隣接するチャネル間のスペクトルの共有を最大にするという目的を有するシミュレーテッドアニーリング型トラフィックプロビジョニング手順を用いて、所与のトラフィックデマンドのセットをプロビジョニングする。トラフィックがプロビジョニングされたら、この手順は、所与の分布に基づいて、ベストエフォートトラフィックデマンドの到着および発出時に、チャネルを動的に拡大および縮小させる。動的なベストエフォートトラフィックの到着時には、この手順は、中央チャネル周波数を起点として低周波数側に向かってプロビジョニングチャネルスペクトルまたは共有チャネルスペクトルの占有を開始する。低周波数側のスペクトルが既に占有されている場合には、この手順は、中央チャネル周波数を起点として高周波数側に向かってプロビジョニングチャネルスペクトルまたは共有チャネルスペクトルの占有を開始する。低周波数および高周波数の両方のチャネルのスペクトルが既に占有されている場合には、トラフィックはブロックされる。この手順は、ネットワークが定常状態に達するまで、このような動的トラフィックシナリオでネットワークのパフォーマンスを評価し、最終的にベストエフォートトラフィックのブロッキングを決定する。ＩＳＡ手順は、ベストエフォートトラフィックの共有帯域幅ｐをｖＧｂ／ｓだけ増加させた後で、同じ手順を反復する。ここで、ｖＧｂ／ｓは、トランスポンダがチャネル帯域幅を拡大および縮小させることができる粒度である。反復する度に、１つの潜在的な解が得られる。
【００１７】
共有帯域幅ｐが事前プロビジョニング帯域幅ｙを超える場合には、ＩＳＡ手順は、事前プロビジョニング帯域幅ｙの量をｖＧｂ／ｓだけ増加させる。この手順は、事前プロビジョニング帯域幅がトランスポンダの容量ＬＧｂ／ｓと等しくなるまで繰り返される。最後に、求められた潜在的な解の中から、この手順は、所与のブロッキング限界βより低いブロッキングをもたらす、必要なスペクトルの量が最小となる解を選択する。
【００１８】
ＩＳＡ手順は、固体をアニーリングする物理プロセスに基づいて設計された、確率的反復方法である。ここで、発明者等は、以下のように、ネットワーク中の時間変動するトラフィックをプロビジョニングするようにこのプロセスを修正した。この手順の構成は、時間変動する接続をルーティングし、波長を割り当て、スペクトルを割り振る、デマンドの順序として定義される。最小化の対象となるエネルギー関数は、ファイバリンク上の最大所要スペクトルを表す。温度は、大域的な時間変動パラメータＴとして定義され、アニーリングスケジュールは、この温度が時間とともにどのように変化するかを制御する。
【００１９】
ＩＳＡ手順は、最初に、要求される保証帯域幅と発信元ノードと宛先ノードとの間の最短ルート上のホップ数ｈsdの積として定義される、各デマンドのコストを決定する。次のステップで、この手順は、所与のトラフィックデマンドを、それらのコストの降順に分類する。この分類されたデマンドの順序は、新たな構成Ｎと見なされる。無作為な順序のデマンドが、現在の構成Ｃと見なされる。現在の構成のエネルギー関数Ｅ（Ｃ）、および新たな構成のエネルギー関数Ｅ（Ｎ）は、無限へ初期化される。この手順は、温度Ｔおよびアニーリングパラメータαも初期化する。初期化後に、このプロセスは、時間変動するトラフィックデマンドについてのルーティング／波長割当て／スペクトル割振り手順を、新たな構成Ｎで定義されたトラフィックデマンドの順序で適用する。ファイバ上の最大所要スペクトルは、構成ＮのエネルギーＥ（Ｎ）を表す。新たな構成のエネルギーＥ（Ｎ）が、現在の構成のエネルギーＥ（Ｃ）と比較して低い場合には、この手順は、現在の構成Ｃを新たな構成Ｎで置換する。一方、エネルギーが改善されない場合には、この手順は、現在の構成を、確率ｅ-(E(N)-E(C)/T)を有する新たな構成で置換する。次のステップで、この手順は、α＊Ｔとなるアニーリングスケジュールで温度Ｔを更新する。最後に、この手順は、終了条件、すなわち温度がしきい値未満に低下しているか、または最大反復数に到達しているかを確認する。これらの条件のうちのいずれか一方が満たされている場合には、この手順は終了する。そうでない場合には、この手順は、無作為に選択された２つの隣接するデマンドの順序を交換することによって現在の構成Ｃから新たな構成Ｎを生成し、同じ手順を繰り返す。
【００２０】
この手順では、ルーティング／波長割当て／スペクトル割振り（ＲＷＳＡ：routing, wavelength assignment, and spectrum allocation）手順のために離散化したスペクトルを考慮する。このスペクトル中の各スロットは、波長スロットと呼ばれる。各波長スロットは、ｇＧＨｚである。このスペクトルは、連続する波長スロットの数によって定義される。中央波長スロットは、チャネルの波長と呼ばれる。ある波長スロットの状態は、占有、空き、共有、またはプロビジョニングとなり得る。占有状態は、その波長スロットが、現在トラフィックを搬送するために使用されていることを表す。空き状態は、その波長スロットが、いかなるチャネルにも割り当てられていないことを表す。共有状態は、その波長スロットが、事前プロビジョニングされていて、複数のチャネルに共有されていることを表す。プロビジョニング状態は、その波長スロットが、あるチャネルのために確保されているが、いかなるトラフィックを搬送するためにも使用されてはいないことを表す。ファイバ／ルート上の波長スロットの状態は、そのファイバ／ルートのスペクトルプロファイルと呼ばれる。空きまたは共有のいずれかの状態を有する１組の連続した波長スロットのセットは、スペクトルアイランドと呼ばれる。保証トラフィック用に確保された１組の波長スロットのセットは、保証スペクトルと呼ばれる。ベストエフォートトラフィック用に確保された、共有されていない１組の波長スロットのセットは、プロビジョニングスペクトルと呼ばれる。隣接するチャネル間で共有される１組の波長スロットのセットは、共有スペクトルと呼ばれる。本明細書では、保証スペクトルの周りでプロビジョニングスペクトルがどのように確保されているか、およびプロビジョニングスペクトルの周りで共有スペクトルがどのように確保されているかについて説明する。これに関連して記載するＣｅｉｌ（．）は、数学のシーリング演算を表す。
【００２１】
時間変動するトラフィックデマンドのルーティング、波長割当て、およびスペクトル割振りのために、この手順は、各ノード対の間のＫ個の最短ルートを事前に計算する。トラフィックデマンドについては、この手順は、最初に、Ｋ個の最短ルートのうち、まだ考慮されていない１つを選択する。この手順は、以下のように、選択したルートに沿ったスペクトルプロファイルを求める。このルート上のリンクのうちの少なくとも１つにおいて波長スロットｗが占有されている場合には、このスペクトルプロファイルの波長スロットｗの状態は、占有である。波長スロットｗが、ルート上の全てのリンクにおいて占有されておらず、波長スロットｗの状態が、ルート上のリンクのうちの少なくとも１つにおいてプロビジョニングである場合には、このスペクトルプロファイルの波長スロットｗの状態は、プロビジョニングである。波長スロットｗが、ルート上の全てのリンクにおいて占有もプロビジョニングもされておらず、波長スロットｗの状態が、ルート上のリンクのうちの少なくとも１つにおいて共有である場合には、このスペクトルプロファイルの波長スロットｗの状態は、共有である。波長スロットｗが、ルート上の全てのリンクにおいて空いている場合には、このスペクトルプロファイルの波長スロットｗの状態は、空きである。選択したルートのスペクトルプロファイルを求めた後で、この手順は、以下の要件を有するスペクトルアイランドを求める。少なくとも［Ｃｅｉｌ（ｘ／ｖ）＊Ｃｅｉｌ（ｚ／ｇ）］個の連続した空き状態の波長スロットを有するスペクトルアイランド（保証スペクトルと呼ばれる）と、スペクトルアイランドの両端にある、保証スペクトルの周りの［Ｃｅｉｌ（（ｙ−ｐ）／ｖ）＊Ｃｅｉｌ（ｚ／ｇ）］個の空き状態の波長スロット（プロビジョニングスペクトルと呼ばれる）、およびプロビジョニングスペクトルの周りの［Ｃｅｉｌ（ｐ／ｖ）＊Ｃｅｉｌ（ｚ／ｇ）］個の空き状態または共有状態の波長スロット（共有スペクトルと呼ばれる）とが、このルートのスペクトルプロファイル中で探索される。この手順では、このスペクトルアイランドが利用可能となる波長を記録する。上述の手順は、Ｋ個の最短ルートの全てについて繰り返される。最後に、この手順では、このスペクトルアイランドが最も長い波長で利用可能となるルートを選択し、このルート上の全てのリンクにおける関連する波長スロットの状態を以下のように更新する。選択したルート上で、選択した波長のスペクトルアイランド内で、この手順は、保証トラフィック用の［Ｃｅｉｌ（ｘ／ｖ）＊Ｃｅｉｌ（ｚ／ｇ）］個の連続した空き波長スロットを、それらの波長スロットの状態を占有に更新することによって確保し、保証スペクトルの周りのベストエフォートトラフィック用の［Ｃｅｉｌ（（ｙ−ｐ）／ｖ）＊Ｃｅｉｌ（ｚ／ｇ）］個の空き波長スロットを、それらの波長スロットの状態をプロビジョニングに更新することによって確保し、ベストエフォートトラフィック用のプロビジョニングスペクトルの周りの［Ｃｅｉｌ（ｐ／ｖ）＊Ｃｅｉｌ（ｚ／ｇ）］個の空き状態または共有状態の波長スロットを、それらの波長スロットの状態を共有に更新することによって確保する
図２は、本発明の原理の一実施形態による、例示的な反復シミュレーテッドアニーリング型方法２００を示す図である。
【００２２】
ステップ２０１で、ベストエフォートトラフィック用の事前プロビジョニング帯域幅ｙを０に初期化し、この事前プロビジョニング帯域幅のうちの共有帯域幅ｐを０に初期化する。ここで、ｐ≦ｙである。
【００２３】
ステップ２０２で、シミュレーテッドアニーリング型トラフィックプロビジョニング手順を用いて、潜在的な解を求める。
【００２４】
ステップ２０３で、求められた解について、ベストエフォートトラフィックの到着時および発出時の動的なチャネルの拡大／縮小を適用し、ブロッキング確率を求める。動的なベストエフォートトラフィックの到着時には、この手順は、中央チャネル周波数を起点として波長スロットの指標が小さくなる方向に向かってプロビジョニングチャネルまたは共有チャネルのいずれかの占有を開始する。チャネルの中で指標の小さい側の波長スロットが既に占有されている場合には、この手順は、中央チャネル周波数を起点として波長スロットの指標が大きくなる方向に向かってプロビジョニングチャネルスペクトルまたは共有チャネルスペクトルの占有を開始する。
【００２５】
ステップ２０４で、共有帯域幅がベストエフォートトラフィック用の事前プロビジョニング帯域幅を超えるかどうかを確認する。超えない場合には、この方法は、ステップ２０５に進む。そうでない場合には、この方法は、ステップ２０６に進む。
【００２６】
ステップ２０５で、提案されるトランスポンダの粒度ｖＧｂ／ｓだけｐを増加させる。
【００２７】
ステップ２０６で、ｙＧｂ／ｓがトランスポンダの容量ＬＧｂ／ｓと等しいかどうかを確認する。等しくない場合には、この方法は、ステップ２０７に進む。そうでない場合には、この方法は、ステップ２０８に進む。
【００２８】
ステップ２０７で、提案されるトランスポンダの粒度ｖＧｂ／ｓだけｙを増加させる。
【００２９】
ステップ２０８で、求められた潜在的な解の中から、β未満のブロッキングに対して必要なスペクトル量が最小となる解を選択する。
【００３０】
図３は、本発明の原理の一実施形態による、例示的な反復シミュレーテッドアニーリング型トラフィックプロビジョニング方法３００を示す図である。
【００３１】
ステップ３０１で、トラフィックデマンドＲをプロビジョニングするコストｆを決定する。ここで、ｆ＝ｘ＊ｈsdである。
【００３２】
ステップ３０２で、現在の構成Ｃを無作為な順序の所与のトラフィックデマンドで初期化し、新たな構成Ｎを、トラフィックデマンドのコストｆ、初期温度Ｔ、アニーリングパラメータα、現在の構成のエネルギーＥ（Ｃ）＝∞、および新たな構成のエネルギーＥ（Ｎ）＝∞に基づく降順のトラフィックデマンドで初期化する。
【００３３】
ステップ３０３で、新たな構成Ｎ中で定義された要求の順序で、時間変動するトラフィックデマンドについて、ルーティング／波長割当て／スペクトル割振り（ＲＷＳＡ）手順を適用する。
【００３４】
ステップ３０４で、新た構成ＮのエネルギーＥ（Ｎ）を表す、ネットワーク中のファイバ上の最大所要スペクトルを求める。
【００３５】
ステップ３０５で、新たな構成のエネルギーが現在の構成のエネルギーより小さいかどうかを確認する。新たな構成のエネルギーの方が小さい場合には、この方法は、ステップ３０７に進む。そうでない場合には、この方法は、ステップ３０６に進む。
【００３６】
ステップ３０６で、確率ｅ-(E(N)-E(C)/T)が０から１の間の一様乱数を超えるかどうかを確認する。超えない場合には、この方法は、ステップ３０８に進む。そうでない場合には、この方法は、ステップ３０７に進む。
【００３７】
ステップ３０７で、構成Ｎによって構成Ｃを更新する。
【００３８】
ステップ３０８で、温度Ｔを（α＊Ｔ）によって更新する。
【００３９】
ステップ３０９で、温度Ｔが所与のしきい値より低いかどうか、または最大反復数に達しているかどうかを確認する。これらの条件のいずれか１つが満たされている場合には、この方法は、終了する。そうでない場合には、この方法は、ステップ３１０に進む。
【００４０】
ステップ３１０で、無作為に選択された２つの隣接するデマンドの順序を交換することによって、新たな構成Ｎを生成する。
【００４１】
図４〜図５は、本発明の原理の一実施形態による、例示的なルーティング／波長割当て／スペクトル割振り（ＲＷＳＡ）方法４００を示す図である。
【００４２】
ステップ４０１で、発信元ノードｓと宛先ノードｄの間のＫ個の最短ルートから、まだ考慮されていないルートを選択する。
【００４３】
ステップ４０２で、選択したルートに沿ったスペクトルプロファイルを以下のように決定する。
【００４４】
ケース１：このルート上のリンクのうちの少なくとも１つにおいて波長スロットｗが占有されている場合には、このスペクトルプロファイルの波長スロットｗの状態は、占有である。
【００４５】
ケース２：このルート上の全てのリンクにおいて波長スロットｗが占有されておらず、波長スロットｗの状態が、このルート上のリンクのうちの少なくとも１つにおいてプロビジョニングである場合には、このスペクトルプロファイルの波長スロットｗの状態は、プロビジョニングである。
【００４６】
ケース３：波長スロットｗが、このルート上の全てのリンクにおいて占有もプロビジョニングもされておらず、波長スロットｗの状態が、このルート上のリンクのうちの少なくとも１つにおいて共有である場合には、このスペクトルプロファイルの波長スロットｗの状態は、共有である。
【００４７】
ケース４：波長スロットｗが、このルート上の全てのリンクにおいて空いている場合には、このスペクトルプロファイルの波長スロットｗの状態は、空きである。
【００４８】
ステップ４０３で、このルートのスペクトルプロファイル中で、少なくとも［Ｃｅｉｌ（ｘ／ｖ）＊Ｃｅｉｌ（ｚ／ｇ）］個の連続した空き状態の波長スロットを有する、最も短い波長のスペクトルアイランド（保証スペクトルと呼ばれる）と、スペクトルアイランドの両端にある、保証スペクトルの周りの［Ｃｅｉｌ（（ｙ−ｐ）／ｖ）＊Ｃｅｉｌ（ｚ／ｇ）］個の空き状態の波長スロット（プロビジョニングスペクトルと呼ばれる）、およびプロビジョニングスペクトルの周りの［Ｃｅｉｌ（ｐ／ｖ）＊Ｃｅｉｌ（ｚ／ｇ）］個の空き状態または共有状態の波長スロット（共有スペクトルと呼ばれる）とを求める。この方法では、このスペクトルアイランドが利用可能である波長を記録する。
【００４９】
ステップ４０４で、全てのルートが考慮されているかどうかを確認する。Ｋ個の最短ルートが全て考慮された場合には、この方法は、ステップ４０５に進む。そうでない場合には、この方法は、ステップ４０１に戻る。
【００５０】
ステップ４０５で、このスペクトルアイランドが最短の波長で利用可能となるルートを選択する。選択したルート上で、選択した波長のスペクトルアイランド内で、この手順は、保証トラフィック用の［Ｃｅｉｌ（ｘ／ｖ）＊Ｃｅｉｌ（ｚ／ｇ）］個の連続した空き波長スロットを、それらの波長スロットの状態を占有に更新することによって確保し、保証スペクトルの周りのベストエフォートトラフィック用の［Ｃｅｉｌ（（ｙ−ｐ）／ｖ）＊Ｃｅｉｌ（ｚ／ｇ）］個の空き波長スロットを、それらの波長スロットの状態をプロビジョニングに更新することによって確保し、ベストエフォートトラフィック用のプロビジョニングスペクトルの周りの［Ｃｅｉｌ（ｐ／ｖ）＊Ｃｅｉｌ（ｚ／ｇ）］個の空き状態または共有状態の波長スロットを、それらの波長スロットの状態を共有に更新することによって確保する。
【００５１】
本明細書に記載する実施形態は、完全にハードウェアであってもよいし、完全にソフトウェアであってもよいし、ハードウェア要素とソフトウェア要素の両方を含んでいてもよい。好ましい実施形態では、本発明は、ファームウェア、常駐ソフトウェア、マイクロコードなどを含む（ただしこれらに限定されるわけではない）ソフトウェアで実施される。
【００５２】
実施形態は、コンピュータまたは任意の命令実行システムによって使用される、またはそれらと関連付けて使用されるプログラムコードを提供する、コンピュータ使用可能媒体またはコンピュータ可読媒体からアクセス可能なコンピュータプログラム製品を含み得る。コンピュータ使用可能媒体またはコンピュータ可読媒体は、命令実行システム、装置、またはデバイスによって使用される、またはそれらと関連付けて使用されるプログラムを記憶、通信、伝搬、または転送する任意の装置を含み得る。この媒体は、磁気、光学、電子、電磁気、赤外線、または半導体のシステム（または装置もしくはデバイス）あるいは伝搬媒体とすることができる。この媒体は、半導体メモリまたは固体状態メモリ、磁気テープ、取外し可能なコンピュータディスケット、ランダムアクセスメモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）、固体磁気ディスク、および光ディスクなどのコンピュータ可読媒体を含み得る。
【００５３】
例えば「Ａ／Ｂ」、「Ａおよび／またはＢ」、ならびに「ＡおよびＢのうちの少なくとも１つ」のように、「／」、「および／または」、ならびに「のうちの少なくとも１つ」のうちのいずれかを使用している場合、それは、１つ目に挙げた選択肢（Ａ）のみを選択する場合、２つ目に挙げた選択肢（Ｂ）のみを選択する場合、または両選択肢（ＡおよびＢ）を選択する場合を包含することを意図している。さらに別の例として、「Ａ、Ｂ、および／またはＣ」ならびに「Ａ、Ｂ、およびＣのうちの少なくとも１つ」の場合には、このような表現は、１つ目に挙げた選択肢（Ａ）のみを選択する場合、２つ目に挙げた選択肢（Ｂ）のみを選択する場合、３つ目に挙げた選択肢（Ｃ）のみを選択する場合、１つ目に挙げた選択肢と２つ目に挙げた選択肢（ＡおよびＢ）のみを選択する場合、１つ目に挙げた選択肢と３つ目に挙げた選択肢（ＡおよびＣ）のみを選択する場合、２つ目に挙げた選択肢と３つ目に挙げた選択肢（ＢおよびＣ）のみを選択する場合、または３つ全ての選択肢（ＡおよびＢおよびＣ）を選択する場合を包含することを意図している。これは、当技術分野および関連する技術分野の当業者には容易に明らかになるであろうが、列挙される品目の数だけ拡張することができる。
【００５４】
以上は、あらゆる点において、説明および例示のためのものであって、制限的なものではないものとして理解すべきものであり、本明細書に開示する本発明の範囲は、上記の詳細な説明によって決定されるのではなく、特許法によって許される最大の範囲に従って解釈される特許請求の範囲によって決定される。追加の情報は、「追加情報」と題する本出願の付属書類に記載されている。本明細書に示して説明した実施形態は、本発明の原理の単なる例示であること、および当業者なら、本発明の範囲および趣旨を逸脱することなく、様々な変形形態を実施することができることを理解されたい。当業者なら、本発明の範囲および趣旨を逸脱することなく、特徴の様々な他の組合せを実施することもできる。
【図１】
2016524430.tif 000003
【図２】
2016524430.tif 000004
【図３】
2016524430.tif 000005
【図４】
2016524430.tif 000006
【図５】
2016524430.tif 000007
【国際調査報告】
2016524430.tif 000008
2016524430.tif 000009