(57)【要約】  波長分割多重方式（ＷＤＭ）光ネットワークにおいて用いられるネットワーク装置において実装される方法が開示される。上記方法は、（ａ）まだ考慮されていない仮想リンク（ＶＬ）（ｉ，ｊ）のうち最大の費用（ただし費用とは、前記ＶＬ（ｉ，ｊ）に要求された回線速度ｒｉｊとノードｉ及びｊ間の最短距離との積である）のものを選択することと、（ｂ）前記ＶＬ（ｉ，ｊ）の前記ノードｉ及びｊ間の、ＡＴ個の最短のルートから、まだ考慮されていないルートｋを選択することと、（ｃ）前記まだ考慮されていないルートｋのビットマップを決定することと、（ｄ）前記要求された回線速度ｒｉｊを、式（Ｉ）で表現される最小のスペクトル（ただし、Ｓｚは、変調フォーマットがチャネルを送信するのに用いるスペクトル効率である）でサポートする変調フォーマットを見出すことと、（ｅ）前記選択されたルートｋの前記ビットマップ内において、Ｍ個の最も低い波長で、式（Ｉ）で表される個数の連続するスペクトルスロットを見出すことと、（ｆ）前記選択されたルートｋ上のそれぞれの波長ｍ（ただし１≦ｍ≦Ｍ）で、チャネルを提供した後で、断片化率Ｆｋｍを決定することと、を含む。他の装置、システム、及び方法も開示されている。【選択図】図４
2016511577.tif 000002
【特許請求の範囲】
【請求項１】
波長分割多重方式（ＷＤＭ）光ネットワークにおいて用いられるネットワーク装置において実装される方法であって、
（ａ）まだ考慮されていない仮想リンク（ＶＬ）（ｉ，ｊ）のうち最大の費用（ただし費用とは、前記ＶＬ（ｉ，ｊ）に要求された回線速度ｒｉｊとノードｉ及びｊ間の最短距離との積である）のものを選択することと、
（ｂ）前記ＶＬ（ｉ，ｊ）の前記ノードｉ及びｊ間の、Ｋ個の最短のルートから、まだ考慮されていないルートｋを選択することと、
（ｃ）前記まだ考慮されていないルートｋのビットマップを決定することと、
（ｄ）前記要求された回線速度ｒｉｊを最小のスペクトル
【数１】
2016511577.tif 000014
（ただし、Ｓｚは、変調フォーマットがチャネルを送信するのに用いるスペクトル効率である）でサポートする変調フォーマットを見出すことと、
（ｅ）前記選択されたルートｋの前記ビットマップ内において、Ｍ個の最も低い波長で、
【数２】
2016511577.tif 000015
の連続するスペクトルスロットを見出すことと、
（ｆ）前記選択されたルートｋ上のそれぞれの波長ｍ（ただし１≦ｍ≦Ｍ）で、チャネルを提供した後で、断片化率Ｆｋｍを決定することと、を含む方法。
【請求項２】
前記断片化率Ｆｋｍは、到達範囲要件Ｂｉｊ≦Ｄｚ（ただしＢｉｊは、前記ＶＬ（ｉ，ｊ）の前記エンドノードｉ及びｊ間の前記ルートｋの距離を表し、Ｄｚは、前記変調フォーマットが前記チャネルを送信する最長の距離を表す）を満たしながら見出される、請求項１に記載の方法。
【請求項３】
すべてのルートが考慮されるまで、上記ステップ（ｂ）〜（ｆ）を繰り返すことを更に含む、請求項１に記載の方法。
【請求項４】
ｈ）前記供給されるＶＬのために、リザーブされたスペクトルを開放し、前記Ｋ個の最短のルート上にスペクトルが存在しない場合には、仮想ネットワーク（ＶＮ）デマンドをブロックすることと、
ｇ）前記Ｋ個の最短のルートの中の前記ルートｋ上にスペクトルが存在する場合に、前記Ｆｋｍが最小化されるように、前記ＶＬの前記ルートｋ上の前記波長ｍに、スペクトルリソースをリザーブすることと、を更に含む、請求項３に記載の方法。
【請求項５】
すべての仮想リンクが考慮されるまで、上記ステップ（ａ）〜（ｈ）を繰り返すことを更に含む、請求項４に記載の方法。
【請求項６】
前記ＷＤＭ光ネットワークは、ソフトウェア定義型ネットワーク（ＳＤＮ）又はフレキシブルグリッドネットワークを含む、請求項１に記載の方法。
【請求項７】
前記断片化率は、以下の式
【数３】
2016511577.tif 000016
（式中、Ｔは、スペクトルがスロット化される粒度であり、（ｓ，ｄ）（ただし、ｓ，ｄ∈Ｖ、且つ｜Ｖ｜≦Ｋであり、式中Ｖは、ＲＯＡＤＭノードの１セットである）は、ノードのペアを表し、Ｌは、回転速度の提供されるセットであり、ｌは、１つの回線速度を表す）に従って決定される、請求項１に記載の方法。
【請求項８】
ネットワーク装置を含み、
該ネットワーク装置は、
（ａ）まだ考慮されていない仮想リンク（ＶＬ）（ｉ，ｊ）のうち最大の費用（ただし費用とは、前記ＶＬ（ｉ，ｊ）に要求された回線速度ｒｉｊとノードｉ及びｊ間の最短距離との積である）のものを選択し、
（ｂ）前記ＶＬ（ｉ，ｊ）の前記ノードｉ及びｊ間の、Ｋ個の最短のルートから、まだ考慮されていないルートｋを選択し、
（ｃ）前記まだ考慮されていないルートｋのビットマップを決定し¨、
（ｄ）前記要求された回線速度ｒｉｊを最小のスペクトル
【数４】
2016511577.tif 000017
（ただし、Ｓｚは、変調フォーマットがチャネルを送信するのに用いるスペクトル効率である）でサポートする変調フォーマットを見出し、
（ｅ）前記選択されたルートｋの前記ビットマップ内において、Ｍ個の最も低い波長で、
【数５】
2016511577.tif 000018
の連続するスペクトルスロットを見出し、
（ｆ）前記選択されたルートｋ上のそれぞれの波長ｍ（ただし１≦ｍ≦Ｍ）で、チャネルを提供した後で、断片化率Ｆｋｍを決定する、波長分割多重方式（ＷＤＭ）光ネットワーク。
【請求項９】
前記断片化率Ｆｋｍは、到達範囲要件Ｂｉｊ≦Ｄｚ（ただしＢｉｊは、前記ＶＬ（ｉ，ｊ）の前記エンドノードｉ及びｊ間の前記ルートｋの距離を表し、Ｄｚは、前記変調フォーマットが前記チャネルを送信する最長の距離を表す）を満たしながら見出される、請求項８に記載のＷＤＭ光ネットワーク。
【請求項１０】
前記ネットワーク装置が、
すべてのルートが考慮されるまで、上記ステップ（ｂ）〜（ｆ）を繰り返す、請求項８に記載のＷＤＭ光ネットワーク。
【請求項１１】
前記ネットワーク装置が、
ｈ）前記供給されるＶＬのために、リザーブされたスペクトルを開放し、前記Ｋ個の最短のルート上にスペクトルが存在しない場合には、仮想ネットワーク（ＶＮ）デマンドをブロックし、及び
ｇ）前記Ｋ個の最短のルートの中の前記ルートｋ上にスペクトルが存在する場合に、前記Ｆｋｍが最小化されるように、前記ＶＬの前記ルートｋ上の前記波長ｍに、スペクトルリソースをリザーブする、請求項１０に記載のＷＤＭ光ネットワーク。
【請求項１２】
前記ネットワーク装置が、
すべての仮想リンクが考慮されるまで、上記ステップ（ａ）〜（ｈ）を繰り返すことを更に含む、請求項１１に記載のＷＤＭ光ネットワーク。
【請求項１３】
ソフトウェア定義型ネットワーク（ＳＤＮ）又はフレキシブルグリッドネットワークを含む、請求項８に記載のＷＤＭ光ネットワーク。
【請求項１４】
前記断片化率は、以下の式
【数６】
2016511577.tif 000019
（式中、Ｔは、スペクトルがスロット化される粒度であり、（ｓ，ｄ）（ただし、ｓ，ｄ∈Ｖ、且つ｜Ｖ｜≦Ｋであり、式中Ｖは、ＲＯＡＤＭノードの１つのセットである）は、ノードのペアを表し、Ｌは、回転速度の提供されるセットであり、ｌは、１つの回線速度を表す）に従って決定される、請求項８に記載のＷＤＭ光ネットワーク。
【請求項１５】
波長分割多重方式（ＷＤＭ）光ネットワークにおいて用いられるネットワーク装置において実装される方法であって、
（ａ）仮想ネットワーク（ＶＮ）のそれぞれの仮想リンク（ＶＬ）を、費用関数（ただし費用関数とは、前記ＶＬ（ｉ，ｊ）に要求された回線速度ｒｉｊとノードｉ及びｊ間の最短距離との積である）に従って供給することと、
（ｂ）前記ＶＬ（ｉ，ｊ）の前記ノードｉ及びｊ間の、Ｋ個の最短のルートの１つ上のそれぞれのＶＬをマッピングすることと、
（ｃ）Ｍ個の最も低い波長で、前記ＶＬ（ｉ，ｊ）のためにスペクトルを供給することと、
（ｄ）断片化を最小化する波長とルートとを選択することと、を含む方法。
【請求項１６】
前記各仮想リンク（ＶＬ）は、より距離が長く、回線速度がより速いＶＬを供給する蓋然性が高くなるように供給される、請求項１５に記載の方法。
【請求項１７】
リソースが供給過剰となることを最小化でき、複数のファイバの間で負荷の均衡をとるように、前記各ＶＬのマッピングを制限することを更に含む、請求項１５に記載の方法。
【請求項１８】
複数のＶＬを最小のスペクトル内に詰めながらも、断片化を減少させるように、前記スペクトルは供給される、請求項１５に記載の方法。
【請求項１９】
将来ＶＮ接続を供給する蓋然性が最大化されるように、前記波長及び前記ルートが選択される、請求項１５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、その内容が参照によって本明細書に組み込まれる、２０１３年２月１４日出願の、「光ＷＤＭネットワークにおける、ネットワーク断片化測定の手続き」と題される米国特許仮出願第６１／７６４，５６８号の利益を主張する。
【０００２】
本出願は、本明細書と同時に出願され、その内容が参照により本明細書に組み込まれる、「光波長分割多重方式（ＷＤＭ）ネットワークにおけるネットワーク断片化測定」と題された、本発明の譲受人に譲渡された出願第１４／１７７，６５４号（代理人整理番号第１２１２０号）に関連する。
【背景技術】
【０００３】
本発明は、波長分割多重方式（ＷＤＭ）光ネットワークに関し、特に、ＷＤＭ光ネットワークへの仮想ネットワーク埋め込みに関する。
【０００４】
現行のネットワークインフラストラクチャは、多くの異種類の独自ネットワークエレメントからなる。このインフラストラクチャにおけるいかなる技術的進化も、設計−統合−展開のサイクルが繰り返される必要があるため、投資コストの増加と結びつく。従って、そのようなインフラストラクチャが、新たなサービス及びネットワークにおける革新の展開を骨化させる。
【０００５】
革新の速度を上げるために、ソフトウェア定義型光（ＳＤＯ）ネットワークアーキテクチャが最近導入され［１］、当該アーキテクチャは、ハイパーバイザのプレーンを介して、ネットワーク仮想化を提供し、同じ物理的基盤を、近接していない複数の仮想ネットワークの例の間で共有するものである。ネットワーク仮想化は、インターネットプロバイダの機能的役割を、インフラストラクチャのプロバイダ（ＩｎＰ）とサービスのプロバイダ（ＳＰ）に分割する［２］。ＩｎＰは、ハードウェアリソース及びソフトウェアリソースを管理維持し、ＳＰはエンドユーザに、ネットワークサービス及びネットワークアプリケーションを提供する。ネットワークハイパーバイザは、ＩｎＰの物理的基盤に対するＳＰからの仮想ネットワーク（ＶＮ）要求をマッピングすることで、ＩｎＰとＳＰとの間のブローカとしての役割を果たす。仮想ノードを物理的ノード上に、また仮想リンク（ＶＬ）を物理的ルート上にマッピングするプロセスを、仮想ネットワーク埋め込みと呼ぶ。ＩｎＰがその収入を最大にし、ＳＰがリソースを最大限利用可能にするためにＶＮ埋め込みが直面する課題の１つは、いかにして、物理的基盤上に埋め込まれるＶＮの数を最大にするかということである。
【０００６】
波長分割多重方式（ＷＤＭ）光ネットワークにおいては、エンドノード間にある回線速度を求めるデマンドが到着すると、ルートに沿って、全ファイバ上の有限の量のスペクトルを割り当てることで、光チャネルが樹立される。前記ルート上の中間ノードが波長変換能力をサポートしていない場合には、ノードを経由するチャネルは、同じ中心波長をチャネルに割り当てることとして定義される波長連続性の制約と、同じ量のスペクトルをノードに出入りするファイバ内のチャネルに割り当てることとして定義されるスペクトル連続性の制約と、に従わなければならない。１本のファイバ上で複数の上記のようなチャネルをサポートするためには、同じファイバ上の複数のチャネルルートに重複しないスペクトルを割り当てることして定義される、スペクトルコンフリクトの制約を満たさなければならない。ある光チャネルが、ネットワーク設備及びファイバを経由する場合には、ルート上の線形及び非線形の障害を蓄積し、光信号の質を劣化させる。データの成功裏の送信を確かなものとするためには、受信機の位置で、少なくとも最低限の検知可能な信号の質が維持されていなければならない。
【０００７】
従来、相互運用状の問題に対処するため、国際電気通信連合の電気通信規格化セクター（ＩＴＵ−Ｔ）は、規格化された固定チャネルスペーシングを有している［３］。ＩＴＵ−Ｔの規格に準拠するネットワークは、図１（ａ）に示すような、固定グリッドネットワークと呼ばれるものである。固定グリッドネットワークでは、増え続ける帯域幅デマンドに対して、異種類の粒度で、複数の回線速度をサポートしつつも、スペクトル効率が最適化されない場合がある。昨今、（図１（ｂ）に示すような）フレキシブルなグリッドネットワークのアーキテクチャが導入されている。ここで、柔軟に変化する量のスペクトルが、求められた帯域幅、送信到達範囲、及び提供された変調フォーマットに基づいて、チャネルに割り当てられる。フレキシブルなグリッドネットワークは、ネットワークのスペクトル効率を高度に最適化するものの、異種類のスペクトル要求を伴うチャネルの動的な到着及び離脱は、（図２に示すような）スペクトルの断片化を引き起こし、ネットワークはもはやその最適な状態でいることはできなくなる。ネットワーク内のスペクトルが断片化した状態は、ネットワーク断片化と呼ばれる。ネットワーク断片化は、固定グリッドネットワーク及びフレキシブルグリッドネットワークにおいて深刻な問題である。スペクトルの断片化は、ある接続が利用できるスペクトルの量が十分存在するにもかかわらず、その接続をブロックする場合があり、その結果、ネットワークのパフォーマンスを劣化させる場合がある。
【０００８】
ソフトウェア定義型光ネットワークにおいて、送信到達範囲上の制約を守りつつ、フレキシブルなグリッドの伝送ネットワーク上に、いかにして仮想ネットワークをマッピングするかという点において、議論の余地がある。その問題は、ソフトウェア定義型フレキシブルグリッドネットワーク上への伝送品質考慮式仮想ネットワーク埋め込みと呼ばれる。当該問題の詳細な定義は次の通りである。
【０００９】
所与の物理的ネットワークＧｐ（Ｎｐ，Ｌｐ）を考える。ただしＮｐは、再構成可能光信号分岐／挿入多重化（ＲＯＡＤＭ）ノードのセットを意味し、Ｌｐは、ファイバのセットを意味する。それぞれのノードにおける可変速度トランスポンダは、サブキャリアを、回線速度を変化させるための電気的変調フォーマットのセットＺを用いて変調可能な、光マルチキャリア変調器（ただし、Ｚ＝｛ＰＭ−ＢＰＳＫ，ＰＭ−ＱＰＳＫ，ＰＭ−１６ＱＡＭ｝）からなる。なお、ＰＭ−ＢＰＳＫは、偏波多重バイナリ位相偏移の略である。ＰＭ−ＱＰＳＫは、偏波多重直角位相偏移の略である。ＰＭ−１６ＱＡＭは、偏波多重１６直角位相振幅変調の略である。
【００１０】
上記セットＺ中の各変調フォーマットｚはチャネルを、スペクトル効率Ｓｚ（ｂ／ｓ／Ｈｚ）で、最大Ｄｚ（ｋｍ）まで送信できる。ＶＮデマンド（Ｇｖ（Ｎｖ，Ｌｖ），ＲＬｖ）がネットワークに、恒久的ＶＮが、１つずつ供給される増加性トラフィックモデル［４］に従って到達する。ただし、Ｎｖは仮想ノードのセットを指し、Ｌｖは仮想リンクのセットを指し、ＲＬｖは、要求された回線速度のセットを指し、ｒｉｊ（∈  ＲＬｖ）は、Ｌｖにおけるある１つの仮想リンク（ｉ，ｊ）において、要求された回線速度を表す。デマンドをサポートするために、ネットワークは総スペクトルＹ（ＧＨｚ）を提供する。埋め込まれるＶＮの数が最大になるように、物理的基盤上にＶＮのマッピングを見出する必要がある。物理的基盤上のＶＮのマッピングは、物理的ルート状の仮想リンクのルーティングを見出すことと、仮想リンクに対する変調フォーマットの選択を見出すことと、波長及びスペクトルの仮想リンクへの割り当てを見出すことと、を要する。
【００１１】
下記［５］において、著者らは、１セット分のＶＮデマンドが、任意の順序で供給され得る静的トラフィックモデルに対する整数線形計画を用いて、固定グリッドネットワーク及びフレキシブルグリッドネットワークにおけるＶＮ埋め込みの問題を定式化した。この［５］におけるソリューションは、ＶＮデマンドが供給されている間の、物理的層の障害を無視している。更に、提案された定式化は、最適なソリューションを保証せず、しかも大規模な問題の例に対してスケーラブルではない。
【００１２】
参照文献
［１］Ｐ．Ｊｉ著、「ソフトウェア定義型光ネットワーク」Ｐｒｏｃ．ｏｆ  ＩＣＯＣＮ、Ｎｏ．ＴＨＵ−０７、２０１２年１１月
［２］Ｔ．Ｇｈａｚａｒ  ａｎｄ  Ｎ．Ｓａｍａａｎ著、「精確なサブグラフマッチングに基づく、効率的仮想ネットワーク埋め込みへの階層的アプローチ」、グローバル電気通信会議（ＧＬＯＢＥＣＯＭ  ２０１１）、２０１１年、ＩＥＥＥ，２０１１年１２月、１〜６頁
［３］ＩＴＵ−Ｔ  Ｇ．６９４．１、「ＷＤＭ用途のスペクトルグリッド：ＤＷＤＭ周波数グリッド」、２００２年５月
［４］Ｙ．Ｓｏｎｅ，Ａ．Ｈｉｒａｎｏ，Ａ．Ｋａｄｏｈａｔａ，Ｍ．Ｊｉｎｎｏ，ａｎｄ  Ｏ．Ｉｓｈｉｄａ著、「ルーティング及びスペクトル割り当てアルゴリズムによる、光ネットワークにおけるスペクトル利用の最大化」、光通信に関する欧州会議・発表会、アメリカ光学会、２０１１年
［５］Ａ．Ｐａｇｅｓ，Ｊ．Ａ．Ｇａｒｃｉａ−Ｅｓｐｉｎ，Ｊ．Ｐｅｒｅｌｌｏ，Ｊ．Ｆｅｒｒｅｒ  Ｒｉｅｒａ，Ｓ．Ｓｐａｄａｒｏ，ａｎｄ  Ｓ．Ｆｉｇｕｅｒｏｌａ著、「将来のインターネットに対する、仮想光ネットワークの最適な割り当て」、光ネットワーク設計及びモデリングに関する第１６回会議議事録（ＯＮＤＭ  ２０１２），２０１２年４月
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本発明の目的の１つは、例えばフレキシブルグリッド伝送ネットワークのようなＷＤＭ光ネットワーク上に、仮想ネットワークをマッピングすることである。
【課題を解決するための手段】
【００１４】
本発明の一態様は、波長分割多重方式（ＷＤＭ）光ネットワークにおいて用いられるネットワーク装置において実装される方法を含む。上記方法は、（ａ）まだ考慮されていない仮想リンク（ＶＬ）（ｉ，ｊ）のうち最大の費用（ただし費用とは、前記ＶＬ（ｉ，ｊ）に要求された回線速度ｒｉｊとノードｉ及びｊ間の最短距離との積である）のものを選択することと、（ｂ）前記ＶＬ（ｉ，ｊ）の前記ノードｉ及びｊ間の、Ｋ個の最短のルートから、まだ考慮されていないルートｋを選択することと、（ｃ）前記まだ考慮されていないルートｋのビットマップを決定することと、（ｄ）前記要求された回線速度ｒｉｊを、最小のスペクトル
【００１５】
【数１】
2016511577.tif 000003
【００１６】
（ただし、Ｓｚは、変調フォーマットがチャネルを送信するのに用いるスペクトル効率である）でサポートする変調フォーマットを見出すことと、（ｅ）前記選択されたルートｋの前記ビットマップ内において、Ｍ個の最も低い波長で、
【００１７】
【数２】
2016511577.tif 000004
【００１８】
の連続するスペクトルスロットを見出すことと、（ｆ）前記選択されたルートｋ上のそれぞれの波長ｍ（ただし１≦ｍ≦Ｍ）で、チャネルを提供した後で、断片化率Ｆｋｍを決定することと、を含む。
【００１９】
本発明の別の態様は、波長分割多重方式（ＷＤＭ）光ネットワークを含む。Ｔｈｅ  ＷＤＭ光ネットワークは、ネットワーク装置を含み、該ネットワーク装置は、（ａ）まだ考慮されていない仮想リンク（ＶＬ）（ｉ，ｊ）のうち最大の費用（ただし費用とは、前記ＶＬ（ｉ，ｊ）に要求された回線速度ｒｉｊとノードｉ及びｊ間の最短距離との積である）のものを選択し、（ｂ）前記ＶＬ（ｉ，ｊ）の前記ノードｉ及びｊ間の、Ｋ個の最短のルートから、まだ考慮されていないルートｋを選択し、（ｃ）前記まだ考慮されていないルートｋのビットマップを決定し、（ｄ）前記要求された回線速度ｒｉｊを最小のスペクトル
【００２０】
【数３】
2016511577.tif 000005
【００２１】
（ただし、Ｓｚは、変調フォーマットがチャネルを送信するのに用いるスペクトル効率である）でサポートする変調フォーマットを見出し、（ｅ）前記選択されたルートｋの前記ビットマップ内において、Ｍ個の最も低い波長で、
【００２２】
【数４】
2016511577.tif 000006
【００２３】
の連続するスペクトルスロットを見出し、及び（ｆ）前記選択されたルートｋ上のそれぞれの波長ｍ（ただし１≦ｍ≦Ｍ）で、チャネルを提供した後で、断片化率Ｆｋｍを決定する。
【００２４】
本発明の更に別の態様は、波長分割多重方式（ＷＤＭ）光ネットワークにおいて用いられるネットワーク装置において実装される方法を含む。当該方法は、（ａ）仮想ネットワーク（ＶＮ）のそれぞれの仮想リンク（ＶＬ）を、費用関数（ただし費用関数とは、前記ＶＬ（ｉ，ｊ）に要求された回線速度ｒｉｊとノードｉ及びｊ間の最短距離との積である）に従って供給することと、（ｂ）前記ＶＬ（ｉ，ｊ）の前記ノードｉ及びｊ間の、Ｋ個の最短のルートの１つ上のそれぞれのＶＬをマッピングすることと、（ｃ）Ｍ個の最も低い波長で、前記ＶＬ（ｉ，ｊ）のためにスペクトルを供給することと、（ｄ）断片化を最小化する波長とルートとを選択することと、を含む。
【００２５】
本開示の手段は、例えば、ソフトウェア、コンピュータプログラム、電子デバイス、コンピュータ、及び／又は、専用コントローラのような、さまざまな種類の構成要素の１種類又はそれより多くの種類を含む。
【図面の簡単な説明】
【００２６】
【図１（ａ）】固定グリッドＷＤＭネットワークの、チャネルスペーシングを描く図である。
【図１（ｂ）】フレキシブルＷＤＭネットワークのチャネルスペーシングを描く図である。
【図２】ファイバのスペクトルにおける断片化を描く図である。
【図３】断片化したスペクトルにおける、スペクトルの島と波長のスロットを描く図である。
【図４】（Ｍ，Ｋ）−断片化−考慮ＶＮ埋め込み手続きを描くフローチャートである。
【発明を実施するための形態】
【００２７】
波長及びスペクトル連続性の制約の下で、複数のファイバに接続をルーティングした場合、当該ファイバ内の、利用可能なスペクトル及び占有されるスペクトルは相互に関連付けられる。ファイバの状態が相互に関連付けられる。本発明者らは、ファイバ状態の相関を、ネットワーク断片化を測定するために考慮する、新規の手続きを設計している。
【００２８】
本発明者らは効果的な手続き、すなわち（Ｍ，Ｋ）−断片化−考慮ＶＮ埋め込み手続きを開発したが、当該手続きは、物理層の障害を考慮しつつ、フレキシブルなグリッドネットワークにおけるＶＮ埋め込み問題に対処する。当該手続きは、フレキシブル伝送ネットワーク上にＶＮを埋め込むが、その際、ネットワーク断片化を最小化し、ネットワーク上に最大限多くのＶＮを埋め込むために将来のＶＮの到来を供給する蓋然性を最大化する。
【００２９】
（１）上記手続きは、ＶＮを埋め込むために、ＳＤＮコントローラのネットワークハイパーバイザプレーンに適用可能である。
（２）上記手続きは、既存のソリューションより速い。
（３）上記手続きは、既存のソリューションと比較して、問題のより大規模な例を解決できる。
（４）上記手続きは、ネットワークリソースの利用を改善する。
（５）上記手続きは、既存のソリューションよりも複雑ではない。
（６）上記手続きは、固定グリッドネットワークに加えて、フレキシブルグリッドネットワークにも適用できる。
【００３０】
管理上の複雑さを減らすために、スペクトルは、λ  ＧＨｚの粒度でスロットを設けられる。スロットは、図３に示されるような、波長スロットと呼ばれるものである。従って、スペクトルは、連続する波長スロットによって表され得るが、そのような波長スロットの中で、第１の波長スロットのインデックスが、波長として表示される。つまり、ネットワークは、全部で
【００３１】
【数５】
2016511577.tif 000007
【００３２】
の波長スロットからなる。それぞれの波長スロットの状態は、バイナリ変数によって表現される。すなわち「１」は、当該波長スロットが利用可能であることを示し、「０」は、当該波長スロットが占有されていることを示す。ファイバのスペクトル状態は、バイナリのベクトルによって表現される。
【００３３】
上記手続きはまず、物理的ネットワークＧｐ（Ｎｐ，Ｌｐ）
【００３４】
【数６】
2016511577.tif 000008
【００３５】
内のノードの各ペア間のルートのうち、最大Ｋ個の、最も短いルートをあらかじめ計算する。
【００３６】
所与のＶＮデマンドに対し、（Ｍ，Ｋ）−断片化−考慮手続きは、ＶＮのＶＬを、物理的ルート上に、１つずつマッピングする。もし、ＶＬのうち、少なくとも１つがマッピングできない場合、ＶＮは、ブロックされているとみなされる。まず、上記手続きは、最大の費用関数のＶＬ、（ｉ，ｊ）、を選択するが、ここでいう費用とは、当該ＶＬに要求された回線速度と、当該ＶＬのエンドノード間の最短のパスの距離との積として定義される。次に、上記手続きは、前記、それぞれのイテレーションにおいて当該ＶＬのエンドノード間の、最も短いＫ個のルートｋの１つを選び、当該ルートのビットマップを見出す。ルートのビットマップは、当該ルートに沿ったファイバのビットベクトルに論理的ＡＮＤ演算を実行することによって見出すことができる。可変速度トランスポンダにより提供されたセットの変調フォーマットの中から、上記手続きは、１つの変調フォーマットを選択するが、当該選択されるフォーマットは、送信到達範囲要件Ｂｋｉｊ≦ＤＺを満たしながら、当該ＶＬ，ｒｉｊ上に要求された回線速度を、最小のスペクトル
【００３７】
【数７】
2016511577.tif 000009
【００３８】
でサポートし得るものである。なお、Ｂｉｊｋは、仮想リンク（ｉ，ｊ）のエンドノード間のルートｋの物理的距離を表す。当該ルートｋの見出されたビットマップにおいて、上記手続きは、
【００３９】
【数８】
2016511577.tif 000010
【００４０】
の連続する波長スロットを、Ｍ個の最も低い波長に見出し、選択されたルートｋ上のそれぞれの潜在的な波長１≦ｍ≦ＭにＶＬ（ｉ，ｊ）を供給した後に、当該ネットワークの断片化率Ｆｋｍを評価する。断片化率（ＦＦ）は、ネットワーク断片化の尺度である。断片化率は、以下のように定義される：
【００４１】
【数９】
2016511577.tif 000011
【００４２】
上式中、Ｔは、スペクトルがスロット化される粒度であり、（ｓ，ｄ）（ただし、ｓ，ｄ∈Ｖ、且つ｜Ｖ｜≦Ｋであり、式中Ｖは、ＲＯＡＤＭノードの１つのセットである）は、ノードのペアであり、Ｌは、回転速度の提供されるセットであり、ｌは、１つの回線速度を表す。断片化率は、「光波長分割多重方式（ＷＤＭ）ネットワークにおけるネットワーク断片化測定」と題された、本発明の譲受人に譲渡された出願第１４／１７７，６５４号（代理人整理番号第１２１２０号）においても定義されている。
【００４３】
上記手続きは、Ｋ個の最も短いルートすべてに対して同じ手続きを繰り返して、それぞれの潜在的ルートｋ上において、要求されたスペクトルが利用可能となる、Ｍ個の最も低い波長に対する断片化率を決定する。もし、Ｋ個の最も短いルートのいずれかの上で、十分なスペクトルが利用できない場合には、上記手続きは、リザーブしておいたスペクトルリソースを、ＶＮの供給されたＶＬに対して解放して、ＶＮデマンドをブロックする。そうでない場合には、上記手続きは、１つの波長ｍと１つのルートｋとの組み合わせで、最小の断片化率Ｆｋｍを有するものを選択する。上記手続きは、スペクトルリソースを、選択されたルートｋ上の選択された波長ｍで供給する。もし、任意のＶＬリンクがまだブロックされていない場合には、上記手続きは次に、最高の費用の、まだ考慮されていないＶＬを選択し、上記の同じ手続きを、当該ＶＮのすべてのＶＬが満たすまで繰り返す。上記手続きは、Ｋ個の潜在的ルート上のＭ個の潜在的波長を評価して、断片化を最小化する目的をもって、ＶＮをネットワーク上に供給するので、上記手続きは、（Ｍ，Ｋ）−断片化−考慮ＶＮ埋め込み手続きと呼ぶ。
【００４４】
当該（Ｍ，Ｋ）−断片化−考慮ＶＮ埋め込み手続きの詳細は、図４に示されるようなフローチャートによって以下のように説明することができる：
ステップ１０１において、上記手続きは、費用が最大のまだ考慮されていないＶＬ（ｉ，ｊ）を選択するが、前記ｉ，ｊ  ∈Ｎは、当該ＶＬのエンドノードであり、ここでいう費用とは、当該ＶＬに要求された回線速度と、当該ＶＬのエンドノード間の最短のパスの距離との積として定義される。
【００４５】
ステップ１０２において、上記手続きは、Ｋ個の最短のルートから１つのまだ考慮されていないルートｋを選択し、当該ルートのビットマップを決定する。ルートのビットマップは、ビットごとの論理的ＡＮＤ演算を、当該ルートに沿ったすべてのファイバのビットベクトルに実行することによって決定できる。
【００４６】
ステップ１０３において、可変速度トランスポンダにより提供されたセットの変調フォーマットの中から、上記手続きは、１つの変調フォーマットを選択するが、当該選択されるフォーマットは、送信到達範囲要件Ｂｋｉｊ≦ＤＺを満たしながら、要求された回線速度をサポートするために、最小の量のスペクトル
【００４７】
【数１０】
2016511577.tif 000012
【００４８】
しか必要としないものである。なおＢｉｊｋは、仮想リンク（ｉ，ｊ）のエンドノード間のルートｋの物理的距離を表す。
【００４９】
ステップ１０４において、選択されたルートｋのビットマップにおいて、上記手続きは、
【００５０】
【数１１】
2016511577.tif 000013
【００５１】
の連続する波長スロットを、Ｍ個の最も低い波長に見出す。
【００５２】
ステップ１０５において、上記手続きは、断片化率Ｆｋｍを、ルートｋ上のそれぞれの見出された波長ｍに見出すが、１≦ｍ≦Ｍである。
【００５３】
ステップ１０６において、上記手続きは、すべてのＫ個の最短のルートが考慮されているかをチェックする。もし、すべてのＫ個の最短のルートが既に考慮されている場合には、上記手続きはステップ１０７に進み、そうでなければ上記手続きは、ステップ１０２に戻る。
【００５４】
ステップ１０７において、上記手続きは、十分なスペクトルが、前記Ｋ個の最短のルートのうちの少なくとも１つの上にあるかどうかをチェックする。もし十分なスペクトルが存在しない場合には、上記手続きはステップ１０８に進み、そうでなければ上記手続きはステップ１０９に進む。
【００５５】
ステップ１０８において、上記手続きは、リザーブされたスペクトルリソースを、ＶＮの供給されるＶＬに対して開放し、ＶＮデマンドをブロックする。最後に、上記手続きは終了する。
【００５６】
ステップ１０９において、上記手続きは、波長ｍ及びルートｋを、断片化率Ｆｋｍを最小化するように選択する。最後に、選択されたルートｋ上の選択された波長ｍにＶＬが供給される。
【００５７】
ステップ１１０において、上記手続きは、すべてのＶＬが供給されているかどうかをチェックする。もし、ＶＬのうち、少なくとも１つがまだ供給されていない場合には、上記手続きはステップ１０１に戻り、そうでなければ上記手続きは終了する。
【００５８】
本明細書に開示される方法は、ネットワーク装置において実装され得る。
【００５９】
ＶＮをソフトウェア定義型フレキシブルグリッドＷＤＭネットワークに埋め込むための、伝送品質考慮式ＶＮ埋め込み手続き（すなわち、（Ｍ，Ｋ）−断片化−考慮ＶＮ埋め込み手続き）は以下のものを含む：
１）１つのＶＮのそれぞれのＶＬを、費用関数（なお、費用関数とは、当該ＶＬに要求された回線速度と、当該ＶＬのエンドノード間の最短のルートの距離との積である）に基づいて１つずつ供給することと、
２）Ｋ個の最短のルートの１つの上に、１つのＶＬをマッピングすることと、
３）１つのＶＬに対し、Ｍ個の最も低い波長の１つでスペクトルを供給することと、
４）ネットワークの断片化を最小化する波長とルートとを選択すること。
【００６０】
上記１）において、費用関数とは、当該ＶＬに要求された回線速度と、ただし、より距離が長く、回線速度が高いＶＬ供給する可能性が高くなる順序において、当該ＶＬの最短のルートのエンドノード間の距離との積である。
【００６１】
上記２）において、１つのＶＬをマッピングすることを、Ｋ個の最短のルートの１つ上に制限することにより、リソースが供給過剰となることを最小化でき、複数のファイバの間で負荷の均衡をとることができる。
【００６２】
上記３）において、このマッピングは、複数のＶＬを最小のスペクトル内に詰めながらも、断片化を減少させる。
【００６３】
上記４）において、将来ＶＮ接続を供給する蓋然性が最大化される。
【００６４】
以上の説明は、あらゆる面で説明的かつ例示的なものであり、制約的なものではなく、本明細書に開示されている発明の範囲は、「詳細な説明」によって決定されるのではなく、むしろ請求項を特許関連法規の許す限りにおいてのもっとも広い解釈により定められる。本発明で示し説明した実施形態は、本発明の原理を説明的したものにすぎず、当業者はさまざまな修正を、本発明の範囲及び精神から逸脱することなく実現することができるであろう。当業者は、さまざまな他の特徴的組み合わせを、本発明の範囲と精神から逸脱することなく、実現できるであろう。
【図１（ａ）】
2016511577.tif 000020
【図１（ｂ）】
2016511577.tif 000021
【図２】
2016511577.tif 000022
【図３】
2016511577.tif 000023
【図４】
2016511577.tif 000024
【国際調査報告】
2016511577.tif 000025
2016511577.tif 000026