(57)【要約】【課題】  光ネットワークの中の制約を有する最短経路を決定するための方法及びシステムが提供される。【解決手段】  当該方法は、前記制約により定められる許容イベント数を識別するステップを有する。当該方法は、前記光ネットワークの中の各々のノードについて仮想ノードを生成するステップであって、前記仮想ノードは前記許容イベント数に対応する、ステップを更に有する。当該方法は、最短経路アルゴリズムにより送信元ノードから宛先ノードまで前記仮想ノードをトラバースするステップであって、前記仮想ノードをトラバースするステップは、前記制約に違反しないとき前記仮想ノードの間の仮想リンクを生成するステップであって、前記仮想リンクは物理リンクに対応する、ステップを含む、ステップと、前記仮想リンクから前記送信元ノードと前記宛先ノードとの間の最短経路を識別するステップであって、前記最短経路は前記制約に違反しない、ステップと、を更に有する。【選択図】  図４
2017216684.tif 000002
【特許請求の範囲】
【請求項１】
光ネットワークの中の制約を有する最短経路を決定する方法であって、前記方法は、
前記制約により定められる許容イベント数を識別するステップと、
前記光ネットワークの中の各々のノードについて仮想ノードを生成するステップであって、前記仮想ノードは、前記許容イベント数に対応する、ステップと、
最短経路アルゴリズムにより送信元ノードから宛先ノードまで前記仮想ノードをトラバースするステップであって、前記仮想ノードをトラバースするステップは、
前記制約に違反しないとき、前記仮想ノードの間の仮想リンクを生成するステップであって、前記仮想リンクは物理リンクに対応する、ステップと、
前記仮想リンクから前記送信元ノードと前記宛先ノードとの間の最短経路を識別するステップであって、前記最短経路は前記制約に違反しない、ステップと、
を含む、ステップと、
を有する方法。
【請求項２】
前記仮想ノードの間の仮想リンクを生成するステップは、
仮想ノードと近隣仮想ノードとの間の候補仮想リンクを識別するステップであって、前記近隣仮想ノードは、前記仮想ノードから前記近隣仮想ノードに到達するまでのイベント数に対応する、ステップと、
前記近隣仮想ノードの結合重みが前記仮想ノードを通じる前記近隣仮想ノードへの結合重みより大きいとき、前記候補仮想リンクから仮想リンクを生成するステップと、
を含む、請求項１に記載の方法。
【請求項３】
前記仮想ノードの間の仮想リンクを生成するステップは、前記近隣仮想ノードの前記結合重みが前記仮想ノードを通じる前記近隣仮想ノードへの前記結合重みより小さいとき、前記候補仮想リンクからの前記仮想リンクを無視するステップ、を更に含む、請求項１に記載の方法。
【請求項４】
前記最短経路アルゴリズムはダイクストラのアルゴリズムである、請求項１に記載の方法。
【請求項５】
前記制約は、光信号リカラーリング数を制限する、請求項１に記載の方法。
【請求項６】
前記制約は、光信号再生数を制限する、請求項１に記載の方法。
【請求項７】
前記ノードをトラバースするステップは、前記制約に違反するとき、前記仮想ノードの間の仮想リンクをブロックするステップを更に含む、請求項１に記載の方法。
【請求項８】
前記ノードをトラバースするステップは、
仮想ノードがトラバースされた後、該仮想ノードを訪問済みとしてマークするステップと、
仮想ノードを訪問済みとしてマークされた後、該仮想ノードへの仮想リンクをブロックするステップと、
を更に含む、請求項１に記載の方法。
【請求項９】
各々の仮想リンクは、対応するノードの間の前記物理リンクの重みに等しい重みを有する、請求項１に記載の方法。
【請求項１０】
前記最短経路を識別するステップは、
最小結合重みを有する前記宛先ノードの仮想ノードを識別するステップであって、前記最小結合重みは、前記最短経路の中の前記物理リンクの重みの和を表す、ステップと、
前記最小結合重みを有する仮想ノードから前記送信元ノードへの仮想リンクを辿るステップと、
を含む、請求項１に記載の方法。
【請求項１１】
制約を有する最短経路を識別する制御システムであって、前記制御システムは、命令を格納する記憶媒体へのアクセスを有するプロセッサを有し、前記命令は、前記プロセッサにより実行可能であり、
前記制約により定められる許容イベント数を識別し、
光ネットワークの中の各々のノードについて仮想ノードを生成し、前記仮想ノードは、前記許容イベント数に対応し、
前記制約に違反しないとき前記仮想ノードの間の仮想リンクを生成し、前記仮想リンクは物理リンクに対応し、前記仮想リンクから送信元ノードと宛先ノードとの間の最短経路を識別し、前記最短経路は前記制約に違反しない、ことにより、最短経路アルゴリズムにより前記送信元ノードから前記宛先ノードまで前記仮想ノードをトラバースする、
ためのものである、制御システム。
【請求項１２】
前記仮想ノードの間の仮想リンクの生成は、
仮想ノードと近隣仮想ノードとの間の候補仮想リンクを識別し、前記近隣仮想ノードは、前記仮想ノードから前記近隣仮想ノードに到達するまでのイベント数に対応し、
前記近隣仮想ノードの結合重みが前記仮想ノードを通じる前記近隣仮想ノードへの結合重みより大きいとき、前記候補仮想リンクから仮想リンクを生成する、
請求項１１に記載の制御システム。
【請求項１３】
前記仮想ノードの間の仮想リンクの生成は、前記近隣仮想ノードの前記結合重みが前記仮想ノードを通じる前記近隣仮想ノードへの前記結合重みより小さいとき、前記候補仮想リンクからの前記仮想リンクを無視する、請求項１１に記載の制御システム。
【請求項１４】
前記最短経路アルゴリズムはダイクストラのアルゴリズムである、請求項１１に記載の制御システム。
【請求項１５】
前記制約は、光信号リカラーリング数を制限する、請求項１１に記載の制御システム。
【請求項１６】
前記制約は、光信号再生数を制限する、請求項１１に記載の制御システム。
【請求項１７】
前記記憶媒体は、前記制約に違反するとき、前記仮想ノードの間の仮想リンクをブロックするための命令を更に含む、請求項１１に記載の制御システム。
【請求項１８】
前記記憶媒体は、
仮想ノードがトラバースされた後、該仮想ノードを訪問済みとしてマークし、
仮想ノードを訪問済みとしてマークされた後、該仮想ノードへの仮想リンクをブロックする、
ための命令を更に含む、請求項１１に記載の制御システム。
【請求項１９】
各々の仮想リンクは、対応するノードの間の前記物理リンクの重みに等しい重みを有する、請求項１１に記載の制御システム。
【請求項２０】
前記最短経路の識別は、
最小結合重みを有する前記宛先ノードの仮想ノードを識別し、
前記最小結合重みを有する仮想ノードから前記送信元ノードまで、前記仮想リンクを辿る、
ことを含む、請求項１１に記載の制御システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、概して、光通信ネットワークに関し、より詳細には、制約を有する最短経路検索に関する。
【背景技術】
【０００２】
電気通信システム、ケーブルテレビシステム、データ通信ネットワークは、光ネットワークを用いて、遠隔地点間で大量の情報を迅速に伝達する。光ネットワークでは、情報は、光ファイバを通じて光信号の形式で伝達され得る。光ネットワークは、増幅器、分散補償器、マルチプレクサ／デマルチプレクサフィルタ、波長選択スイッチ、カプラ、及び他の要素等のような、ネットワーク内で種々の動作を実行するよう構成される種々のネットワークコンポーネントを有して良い。
【０００３】
種々のネットワークノードを通じる光信号経路の計算は、光ネットワークの設計、モデル化、管理、及び制御のための中核機能である。光経路計算は、光ネットワークのオペレータがネットワークポリシをカスタマイズし、制御し及び／又は更新することを可能にし得る。光経路計算の１つの特徴は、送信元ノードから宛先ノードまでのエンド−エンド経路の決定を含む。例えば、信号遅延又はコストを低減するために、送信元と宛先ノードとの間の最短経路を選択することが望ましい場合がある。最短経路は、ノード間の重み（例えば、距離又は別の因子）により測定されて良い。
【０００４】
しかしながら、光ネットワークの中の経路は、重み以外の因子により変化し得る。例えば、送信元と宛先ノードとの間の１つの経路は、同じ累積重みを有する別の経路より多くのネットワークノードを通過することがある。特定経路は、一層多くの特定種類のノード又は物理リンクを通過することがある。別の例として、特定経路は、光信号再生及び／又はリカラーリングのような処理を要求することもある。これらの因子は、光信号経路の中の遅延、リソース、信号品質、及び／又はコストに影響を与え得る。しかしながら、これらの因子は、最短経路の計算において考慮されない場合がある。
【０００５】
したがって、信号経路の中の特定イベントを制限するために、経路計算の間に制約を追加することが望ましい場合がある。例えば、信号経路の中の合計ネットワークノード数を制限して、経路が所定最大ノード数（例えば、経路の中の最大ホップ数）を超えないようにすることが望ましい場合がある。別の例として、経路の中の特定種類のネットワークノード、リンク、及び／又は処理（例えば、再生及び／又はリカラーリング）の数を制限することが望ましい場合がある。
【発明の概要】
【０００６】
特定の実施形態では、光ネットワークの中の制約を有する最短経路を決定する方法は、制約により定められる許容イベント数を識別するステップを有する。当該方法は、前記光ネットワークの中の各々のノードについて仮想ノードを生成するステップであって、前記仮想ノードは前記許容イベント数に対応する、ステップを更に有する。当該方法は、最短経路アルゴリズムにより送信元ノードから宛先ノードまで前記仮想ノードをトラバースするステップであって、前記仮想ノードをトラバースするステップは、前記制約に違反しないとき前記仮想ノードの間の仮想リンクを生成するステップであって、前記仮想リンクは物理リンクに対応する、ステップを含む、ステップと、前記仮想リンクから前記送信元ノードと前記宛先ノードとの間の最短経路を識別するステップであって、前記最短経路は前記制約に違反しない、ステップと、を更に有する。
【０００７】
別の実施形態では、制約を有する最短経路を識別する制御システムは、前記制約により定められる許容イベント数を識別するためにプロセッサにより実行可能な命令を格納する記憶媒体へのアクセスを有する。前記命令は、さらに、前記光ネットワークの中の各々のノードについて仮想ノードを生成するために実行可能であり、前記仮想ノードは前記許容イベント数に対応する。前記命令は、さらに、前記制約に違反しないとき前記仮想ノードの間の仮想リンクを生成することにより、最短経路アルゴリズムにより送信元ノードから宛先ノードまで前記仮想ノードをトラバースし、前記仮想リンクは物理リンクに対応し、前記仮想リンクから前記送信元ノードと前記宛先ノードとの間の最短経路を識別し、前記最短経路は前記制約に違反しない、ために実行可能である。
【図面の簡単な説明】
【０００８】
本発明並びにその特徴及び利点のより完全な理解のため、添付の図と共に以下の説明を参照する。
【図１】ネットワークの一実施形態の選択された要素のブロック図である。
【図２】光ネットワークの制御システムの一実施形態の選択された要素のブロック図である。
【図３Ａ】制約を有する光経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【図３Ｂ】制約を有する光経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【図３Ｃ】制約を有する光経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【図３Ｄ】制約を有する光経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【図３Ｅ】制約を有する光経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【図３Ｆ】制約を有する光経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【図３Ｇ】制約を有する光経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【図３Ｈ】制約を有する光経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【図３Ｉ】制約を有する光経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【図３Ｊ】制約を有する光経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【図３Ｋ】制約を有する光経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【図３Ｌ】制約を有する光経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【図４】光ネットワークの中の制約を有する最短経路を決定するための方法のフローチャートである。
【発明を実施するための形態】
【０００９】
以下の説明では、開示の主題の議論を容易にするために例として詳細事項が説明される。しかしながら、当業者には、開示の実施形態が例示であること及び全ての可能な実施形態を網羅するものではないことが明らかである。
【００１０】
本開示を通じて、ハイフンで結んだ形式の参照符号は、１つの要素の特定のインスタンスを表し、ハイフンを有しない形式の参照符号は、要素を一般的又は集合的に表す。したがって、例として（図示しない）、装置１２−１は、装置クラスのインスタンスを表し、装置１２として集合的に言及されて良く、それらのうちの任意のものが装置１２として一般的に言及されて良い。図及び説明の中で、同様の記号は同様の要素を表す。
【００１１】
ネットワークは、互いに通信可能に結合されるノード（又はネットワーク要素）により構成される。これらのノードは、リンク（又は伝送媒体）を介して互いに情報を通信する。例えば、送信元ノードは、ノード及びリンクの経路を通じてネットワークの中の宛先ノードへ情報を送信して良い。しかしながら、このような情報を送信すべき１より多くのネットワーク経路が存在することがある。幾つかの実施形態では、経路計算エンジンは、ノード間のリンクを識別するため、及び送信元ノードと宛先ノードとの間の最短経路を選択するために、使用されて良い。しかしながら、例えばネットワーク経路の中の特定イベントの発生数を制限するために、距離に加えて、ネットワーク経路に制約を課すことが望ましい場合がある。一例として、信号劣化を低減し及び信号品質を保証するために、光ネットワーク経路の中の再生又はリカラーリングの数を制限する制約を実施することが望ましい場合がある。このように、制約は、信号品質、コスト、ネットワークリソース、又は、信号、経路若しくはネットワークの他の側面を向上するために、経路計算中に使用されて良い。
【００１２】
図を参照すると、図１は、ネットワーク１００の一実施形態の選択された要素を示すブロック図である。種々の実施形態において、ネットワーク１００は、Ｅｔｈｒｅｎｅｔ（登録商標）ネットワークであって良い。ネットワーク１００は、ネットワーク１００のコンポーネントにより通信される１又は複数の信号を運ぶよう動作する１又は複数の伝送媒体１２を含む。ネットワーク１００のコンポーネントは、伝送媒体１２により一緒に結合され、複数のネットワーク要素１０２（ネットワークノード、又は単にノードとしても参照される）を含んで良い。図示のネットワーク１００では、各々のネットワーク要素１０２は、４個の他のノードと結合される。しかしながら、任意の適切な数のネットワーク要素１０２の任意の適切な構成がネットワーク１００を生成して良い。ネットワーク１００はメッシュネットワークとして示されるが、ネットワーク１００は、リング型ネットワーク、ポイントツーポイントネットワーク、又は任意の他の適切なネットワーク若しくはネットワークの結合として構成されても良い。光ネットワーク１００は、短距離都市域ネットワーク、長距離都市間ネットワーク、又は任意の他の適切なネットワーク若しくはネットワークの組合せの中で用いられて良い。
【００１３】
各々の伝送媒体１２は、ネットワーク要素１０２を互いに通信可能に結合しそれらの間で情報を通信するよう構成される、任意のシステム、装置、又は機器を有して良い。例えば、伝送媒体１２は、光ファイバ、イーサネット（登録商標）ケーブル、Ｔ１ケーブル、WiFi又はBluetooth（登録商標）接続、及び／又は任意の他の適切な媒体を有して良い。
【００１４】
ネットワーク１００は、伝送媒体１２を介して情報又は「トラフィック」を通信して良い。ここで使用されるとき、「トラフィック」は、ネットワーク１００で送信され、格納され又はソートされる情報を意味する。このようなトラフィックは、オーディオ、ビデオ、テキスト、及び／又は他の適切なデータをエンコードするよう構成された光又は電気信号を有して良い。データは、同期又は非同期で送信されて良く、確定的に（「リアルタイム」とも表される）及び／又は確率的に送信されて良い。トラフィックは、OSI（Open  Systems  Interconnection）標準及びIP（Internet  Protocol）を含むがこれらに限定されない任意の適切な通信プロトコルを介して通信されて良い。さらに、ネットワーク１００を介して通信されるトラフィックは、フレーム又はパケットを含むがこれらに限定されない任意の適切な方法で構造化されて良い。
【００１５】
ネットワーク１００の中の各々のネットワーク要素１０２は、ネットワークトラフィックを送信及び受信するよう動作する任意の適切なシステムを有して良い。例えば、ネットワーク要素１０２は、ハブ、ルータ、スイッチ、ブリッジ、又はネットワークトラフィックを送信及び受信するよう動作する任意の他のシステム若しくは装置であって良い。図示の実施形態では、各ネットワーク要素１０２は、伝送媒体１２を介して、１又は複数の他のネットワーク要素１０２にトラフィックを直接送信し、１又は複数の他のネットワーク要素１０２からトラフィックを直接受信するよう動作して良い。
【００１６】
上述のように、ネットワーク１００の１又は複数のコンポーネントは、光ネットワークコンポーネントであって良い。例えば、ネットワーク要素１０２の一部又は全部は、光信号により通信して良い。したがって、ネットワーク要素１０２は、１又は複数の光送信機、マルチプレクサ、光増幅器、アッド／ドロップマルチプレクサ、デマルチプレクサ、及び光受信機を有して良い。光ネットワーク要素１０２は、非常に低損失で長距離に渡り信号を伝達可能なガラスの細い紐を有する光ファイバを介して通信して良い。これらの光ファイバは、例えばＳＭＦ（Single−Mode  Fiber）、Ｅ−ＬＥＡＦ（Enhanced  Large  Effective  Area  Fiber）、又はＴＷ−ＲＳ（TrueWave（登録商標）Reduced  Slope）ファイバを含む適切な種類のファイバを有して良い。
【００１７】
ネットワーク１００の中の光要素は、光ファイバを介して光信号の中で情報を伝達するために、変調技術を用いて良い。このような変調方式は、変調技術の他の例の中でも特に、ＰＳＫ（phase−shift  keying）、ＦＳＫ（frequency−shift  keying）、ＡＳＫ（amplitude−shift  keying）、及びＱＡＭ（quadrature  amplitude  modulation）を有して良い。ＰＳＫでは、光信号により伝達される情報は、搬送波又はキャリアとしても知られる参照信号の位相を変調することにより搬送されて良い。情報は、２レベル又はＢＰＳＫ（binary  phase−shift  keying）、４レベル又はＱＰＳＫ（quadrature  phase−shift  keying）、Ｍ−ＰＳＫ（multi−level  phase−shift  keying）及びＤＰＳＫ（differential  phase−shift  keying）を用いて信号自体の位相を変調することにより搬送されて良い。ＱＡＭでは、光信号により運ばれる情報は、搬送波の振幅と位相の両方を変調することにより伝達されて良い。ＰＳＫは、ＱＡＭの一部であると考えられる。ここで、搬送波の振幅は、一定に維持される。さらに、ＰＤＭ（polarization  division  multiplexing）技術は、情報送信のために、より大きなビットレートを達成できる。ＰＤＭ伝送は、チャネルに関連する光信号の種々の偏光成分に情報を変調することを含む。光信号の偏波は、通常、光信号の振動方向を表し得る。用語「偏波」は、通常、光信号の伝搬方向に垂直な、空間内のある点における光信号の電場ベクトルの先端により追跡される経路を表し得る。
【００１８】
ネットワーク１００は、管理プレーン、制御プレーン、及びトランスポートプレーン（物理レイヤと呼ばれることが多い）を有して良い。中央管理ホスト（図１に明示しない）は、管理プレーンに存在して良く、制御プレーンのコンポーネントを構成し管理して良い。管理プレーンは、トランスポートプレーン及び制御プレーンエンティティ（例えば、ネットワーク要素１０２及び図３に関連して後述するネットワークノード３０２）を制御して良い。一例として、管理プレーンは、１又は複数の処理リソース、データ記憶コンポーネント、等を含む中央処理センタ（例えば、中央管理ホスト）を有して良い。管理プレーンは、制御プレーンの要素と通信して良く、トランスポートプレーンの１又は複数のネットワーク要素と通信して良い。管理プレーンは、システム全体の管理機能を実行し、ネットワーク要素、制御プレーン及びトランスポートプレーンの間の調整を提供して良い。例として、管理プレーンは、要素の観点から１又は複数のネットワーク要素を取り扱うＥＭＳ（element  management  system）、ネットワークの観点から多くの装置を取り扱うＮＭＳ（network  management  system）、及び／又はネットワーク全体の動作を取り扱うＯＳＳ（operational  support  system）を有して良い。
【００１９】
本開示の範囲から逸脱することなく、ネットワーク１００に対し変更、追加又は省略が行われて良い。記載のネットワーク１００のコンポーネント及び要素は、特定の必要に従い統合され又は分離されて良い。さらに、ネットワーク１００の動作は更に多くの、更に少ない又は他のコンポーネントにより実行されて良い。
【００２０】
図２は、例えば図１のネットワーク１００又は図３のネットワーク３００におけるようなネットワークにおける制御プレーン機能を実装する制御システム２００の一実施形態の選択された要素のブロック図である。例示的な制御システムは、Fujitsu  Network  Communications  Inc.のNETSMART（登録商標）システムである。制御プレーンは、ネットワーク知能及び制御のための機能を有して良く、更に詳細に後述するように発見、ルーティング、経路計算、及びシグナリングのためのアプリケーション又はモジュールを含むネットワークサービスを確立する能力をサポートするアプリケーションを有して良い。制御システム２００により実行される制御プレーンアプリケーションは、例えばネットワークの光コンポーネント内を含むネットワーク内でサービスを自動的に確立するために一緒に動作して良い。発見モジュール２１２は、ノード（つまり、ネットワーク要素）を近隣ノードに接続する物理リンクを発見して良い。ルーティングモジュール２１０は、データベース２０４を移植する（populate）間に、ネットワークノードへ物理リンク（例えば、伝送媒体）情報をブロードキャストして良い。ネットワークからのサービスに対する要求が受信されると、経路計算エンジン２０２は、データベース２０４を用いてネットワーク経路を計算するために呼び出されて良い。このネットワーク経路は、次に、要求されたサービスを確立するために、シグナリングモジュール２０６に提供されて良い。
【００２１】
図２に示すように、制御システム２００は、プロセッサ２０８と、記憶媒体２２０とを有する。記憶媒体２２０は、記憶媒体２２０へのアクセスを有するプロセッサ２０８により実行可能な実行可能命令（つまり、実行可能コード）を格納して良い。プロセッサ２０８は、制御システム２００に本願明細書に記載の機能及び動作を実行させる命令を実行して良い。本開示の目的のために、記憶媒体２２０は、少なくともある時間期間の間、データ及び命令を格納する非一時的コンピュータ可読媒体を含み得る。記憶媒体２２０は、永続的及び揮発性媒体、固定及び取り外し可能媒体、磁気及び半導体媒体を含み得る。記憶媒体２２０は、直接アクセス記憶装置（例えば、ハードディスクドライブ又はフロッピーディスク）、順次アクセス記憶装置（例えば、テープディスクドライブ）、ＣＤ（compact  disk）、ＲＡＭ（random  access  memory）、ＲＯＭ（read−only  memory）、ＣＤ−ＲＯＭ、ＤＶＤ（digital  versatile  disc）、ＥＥＰＲＯＭ（electrically  erasable  programmable  read−only  memory）、及びフラッシュメモリのような記憶媒体、非一時的媒体、又はこれらの種々の組合せを有して良いが、これらに限定されない。記憶媒体２２０は、命令、データ、又はそれらの両方を格納するよう動作する。図示のような記憶媒体２２０は、実行可能コンピュータプログラム、つまり経路計算エンジン２０２、シグナリングモジュール２０６、発見モジュール２１２、及びルーティングモジュール２１０を表し得る命令のセット又はシーケンスを有する。本願明細書に記載のように、経路計算エンジン２０２は、シグナリングモジュール２０６、発見モジュール２１２、及びルーティングモジュール２１０と連動して、本開示による種々のアルゴリズムを実装する命令又はコードを表して良い。
【００２２】
図２の制御システム２００には、ネットワークインタフェース２１４も含まれる。ネットワークインタフェース２１４は、プロセッサ２０８とネットワーク２３０との間のインタフェースとして機能するよう動作する適切なシステム、機器又は装置であって良い。ネットワークインタフェース２１４は、制御システム２００が適切な送信プロトコル又は規格を用いてネットワーク２３０を介して通信することを可能にして良い。幾つかの実施形態では、ネットワークインタフェース２１４は、ネットワーク２３０を介してネットワーク記憶リソースに通信可能に結合されて良い。幾つかの実施形態では、ネットワーク２３０は、ネットワーク１００の少なくとも特定の部分の一実施形態であって良い。ネットワーク２３０は、ハードウェア、ソフトウェア、又はそれらの種々の組合せを用いて実装されて良い。
【００２３】
特定の実施形態では、制御システム２００は、人（つまり、ユーザ）と相互作用し、光信号送信経路に関するデータを受信するよう構成されて良い。例えば、制御システム２００は、ユーザからの光信号送信経路に関するデータの受信を実現するために及びユーザに結果を出力するために、１又は複数の入力装置及び出力装置を有し又はそれらに結合されて良い。１又は複数の入力又は出力装置（図示しない）は、キーボード、マウス、タッチパッド、マイクロフォン、ディスプレイ、タッチスクリーンディスプレイ、オーディオスピーカ、等を有して良いが、これらに限定されない。代替又は追加で、制御システム２００は、例えばネットワーク２３０を介して、別のコンピューティング装置又はネットワーク要素のような装置から光信号送信経路に関するデータを受信するよう構成されて良い。
【００２４】
幾つかの実施形態では、発見モジュール２１２は、ネットワークにおける光信号送信経路に関するデータを受信するよう構成されて良く、近隣ノード及びこれらのノードの間のリンクの発見を担って良い。言い換えると、発見モジュール２１２は、発見プロトコルに従って発見メッセージを送信して良く、光信号送信経路に関するデータを受信して良い。幾つかの実施形態では、発見モジュール２１２は、特に、ノードの特徴、リンク、コンポーネントの数及び種類、データレート及び／又は信号情報（例えば、データの変調フォーマット、信号の入力パワー、信号搬送波長の数、チャネル間隔、トラフィック要求、及びネットワークトポロジ）を決定して良い。
【００２５】
ルーティングモジュール２１０は、図３に関して議論されるネットワーク１００又はネットワーク３００のようなネットワークの中の種々のノードにリンク接続性情報を伝搬することを担って良い。特定の実施形態では、ルーティングモジュール２１０は、リンク帯域幅可用性を含み得る、トラフィックエンジニアリングをサポートするためのリソース情報をデータベース２０４に移植して良い。したがって、データベース２０４は、ルーティングモジュール２１０により、ネットワークのネットワークトポロジを決定するのに有用な情報を移植されて良い。
【００２６】
経路計算エンジン２０２は、ネットワークの光部分の中の光信号送信経路を含む光信号送信経路の送信特性を決定するために、ルーティングモジュール２１０によりデータベース２０４に提供される情報を用いて良い。光信号送信経路の送信特性は、特に、色分散（chromatic  dispersion：ＣＤ）、非線形（nonlinear：ＮＬ）効果、偏光モード分散（polarization  mode  dispersion：ＰＭＤ）及び偏光依存損失（polarization  dependent  loss：ＰＤＬ）のような偏光効果、並びに自然放出雑音（amplified  spontaneous  emission：ＡＳＥ）のような送信劣化因子が、光信号送信経路内で光信号にどれ位影響を与え得るかについての見識を提供して良い。光信号送信経路の送信特性を決定するために、経路計算エンジン２０２は、送信劣化因子の間の相互作用を検討して良い。種々の実施形態では、経路計算エンジン２０２は、特定の送信劣化因子の値を生成して良い。経路計算エンジン２０２は、光信号送信経路を記述するデータをデータベース２０４に更に格納して良い。
【００２７】
図２で、シグナリングモジュール２０６は、図１のネットワーク１００又は図３のネットワーク３００のような光ネットワークにおいてエンド−エンドネットワークサービスの設定、変更、及び取り壊しに関連する機能を提供して良い。例えば、ネットワーク内のイングレスノードがサービス要求を受信すると、制御システム２００は、シグナリングモジュール２０６を用いて、帯域幅、コスト、等のような異なる基準に従って最適化され得る経路計算エンジン２０２からのネットワーク経路を要求して良い。所望のネットワーク経路が識別されると、次に、シグナリングモジュール２０６は、要求されたネットワークサービスを確立するために、ネットワーク経路に沿って個々のノードと通信して良い。異なる実施形態では、シグナリングモジュール２０６は、ネットワーク経路に沿ってノードへ及びノードから後続の通信を伝搬するために、シグナリングプロトコルを用いて良い。
【００２８】
制御システム２００の動作では、光経路計算の特徴は、エンド−エンドの到達可能経路の計算を有して良い。直接到達可能経路は、送信元ノードと宛先ノードとの間で光信号が再生しないで送信できる、ネットワークにおける送信元ノードと宛先ノードとの間の経路を表して良い。これに対し、送信元ノードと宛先ノードとの間の間接到達可能経路は、宛先に到達する前に光−電気−光（Ｏ−Ｅ−Ｏ）、全部光、又は他の適切な再生器を用いる光信号の再生を含んで良い。幾つかの例では、経路は、光信号のリカラーリング（recoloring）を必要として良い。光ネットワークにおけるリカラーリングは、波長チャネルを異なる波長にシフトすることを表す。スペクトルスロットフラグメント化のために、光ネットワークにおけるネットワークリソース利用は、リカラーリングを使用せずに、限定されて良い。リカラーリングは、Ｏ−Ｅ−Ｏ再生器により、又はＯ−Ｅ−Ｏ再生器より低い光信号対雑音比（optical  signal−to−noise  ratio：ＯＳＮＲ）ペナルティ及びより多くの運用上の柔軟性を有する光要素により達成されて良い。したがって、送信元ノードから宛先ノードへの間接エンドツーエンド到達可能経路は、再生器ノード及び／又はリカラーリングノードのうちの１又は複数を有して良い。
【００２９】
経路計算エンジン２０２は、最短エンドツーエンド到達可能経路を決定して良い。例えば、経路計算エンジン２０２は、ネットワークノード間の最小結合重みを有する送信元ノードから宛先ノードへの経路を選択して良い。ネットワークノードを結合する各々の物理リンクは、距離、コスト、遅延、雑音、送信特性、及び／又はそれらの組合せを含む１又は複数の因子を表す重みを有して良い。経路計算エンジン２０２は、任意の２つのノード間の最短経路を決定するために、最短経路アルゴリズムを使用して良い。最短経路アルゴリズムの例は、ダイクストラ（Dijkstra）のアルゴリズム、ベルマン−フォード（Bellman−Ford）アルゴリズム、ガボウ（Gabow）のアルゴリズム、及びThorupのアルゴリズムを含むが、これらに限定されない。
【００３０】
しかしながら、上述のように、経路が配置される光経路又はネットワークの性能に影響を与える物理リンクの重み以外の因子が存在し得る。例えば、各々の経路は、宛先ノードに到達するまでに、多数のネットワークノード、多数の特定種類のノード、又は多数の特定種類の物理リンクをトラバースし得る。さらに、経路は、光信号再生及び／又はリカラーリングのような特定種類の処理を要求することがある。これらの因子のうちの任意のものは、信号品質、コスト、ネットワークリソース、又は、光経路若しくはネットワークの他の側面に影響を与えることがあり、したがって、経路計算のために考慮する必要がある場合がある。
【００３１】
幾つかの実施形態では、ネットワーク管理者は、特定イベントの発生数を制限するために、経路計算エンジン２０２に１又は複数の制約を課して良い。制約は、例えば、経路の中にあるネットワークノードの数を制限して良く、最短経路が所定最大ノード数を超えないようにして良い。別の例として、制約は、任意の経路の中で許容される特定種類のネットワークノード、リンク、及び／又は処理（例えば、再生及び／又はリカラーリング）の数を制限して良い。経路計算エンジン２０２は、送信元と宛先ノードとの間の最短経路を計算する際に、このような制約を考慮して良く、最短経路が制約に従うようにして良い。経路計算エンジン２０２は、制約に従わない経路を無視して良い。
【００３２】
図３Ａ〜３Ｌは、制約を有する光経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【００３３】
図示のように、ネットワーク３００は、集合的にノード３０２として参照されるノード３０２−１〜３０２−６を含む。動作中、特定ノード３０２は、適切な波長で物理リンク３０４上を伝搬する光信号により、光ネットワーク３００の他のノード３０２及び他のコンポーネントとメッセージを通信して良い。光信号は、例えば変調又は多重化を含む図１に関連して上述した技術のうちの任意のものを使用し又は含んで良い。ノード３０２は、物理リンク３０４を用いて、データ（例えば、ファイル又はウェブページ）及びシグナリング（例えば、制御メッセージ、ルーティングメッセージ、及びリンク管理メッセージ）の両方を通信して良い。データ及びシグナリングは、メッセージ又はトラフィックとして集合的に参照されて良い。
【００３４】
ノード３０２は、メッセージを送信及び受信するよう動作する任意の適切なシステムを有して良い。例えば、ノード３０２は、ＯＡＤＭ、クロスコネクト、再生ユニット、アクセスゲートウェイ、エンドポイント、ソフトスイッチサーバ、トランクゲートウェイ、アクセスサービスプロバイダ、インターネットサービスプロバイダ、ハブ、ルータ、スイッチ、ブリッジ、又はネットワーク３００へ、それから、又はその中でデータをルーティングするよう動作する任意の他の装置を含んで良い。
【００３５】
物理リンク３０４は、ノード３０２間の通信をトランスポートする任意の適切な媒体を有して良い。例えば、物理リンク３０４は、図１の伝送媒体１２に関して上述したような光ファイバを有して良い。
【００３６】
ノード３０２−１がノード３０２−４にメッセージを送信する必要があるとする。このようなシナリオでは、この特定の送信について、ノード３０２−１は送信元ノードであり、ノード３０２−４は宛先ノードである。図３の例示的なネットワークトポロジにより示されるように、送信元ノードから宛先ノードへメッセージをルーティングするために、１より多くの経路が使用されて良い。可能な経路は、ノード３０２−１→３０２−２→３０２−３→３０２−４の間、ノード３０２−１→３０２−２→３０２−６→３０２−４の間、ノード３０２−１→３０２−５→３０２−６→３０２−４の間、ノード３０２−１→３０２−５→３０２−３→３０２−４の間、を含む。
【００３７】
ノード３０２−１からノード３０２−４までの適切な経路を選択するために、ネットワーク３００は、経路識別及び／又は選択のためにシステムを含み又はシステムに通信可能に結合して良い。例えば、ネットワーク３００は、図２に関して上述したものと同様に、制御システムを有して良い。制御システムは、発見モジュール、ルーティングモジュール、シグナリングモジュール、及び／又は経路計算エンジンを用いて、ネットワーク３００の種々のノード３０２の間のエンドツーエンド経路を分析し及び選択して良い。
【００３８】
経路を選択する際の１つの検討事項は、ノード３０２を結合する物理リンクに関連付けられる重みであって良い。ネットワーク３００では、各々の物理リンク３０４は割り当てられた重みを有する。重みは、特定リンクについての、距離、コスト、遅延、雑音、及び／又はそれらの組み合わせを表して良い。例えば、ノード３０２−１及び３０２−２を結合するリンクは重み３を有し、ノード３０２−２を３０２−３に結合するリンクは重み１を有し、ノード３０２−３を３０２−４に結合するリンクは重み４を有し、ノード３０２−２を３０２−６に結合するリンクは重み３を有し、ノード３０２−１を３０２−５に結合するリンクは重み２を有し、ノード３０２−５を３０２−６に結合するリンクは重み１を有し、ノード３０２−５を３０２−３に結合するリンクは重み３を有し、ノード３０２−６を３０２−４に結合するリンクは重み１を有する。
【００３９】
ネットワーク３００は、ネットワーク３００の中の物理リンク３０４の重みを用いてノード３０２間の最短経路を識別するために、上述の列挙されたものを含む最短経路アルゴリズムを使用して良い。最短経路は、経路の中の物理リンク３０４の最小結合重みを有する経路を表して良い。例えば、送信元ノード３０２−１から宛先ノード３０２−４までの最短経路は、ノード３０２−１→３０２−５→３０２−６→３０２−４（最短経路３１０により示される）の間であって良く、結合重み４（例えば、２＋１＋１）を表す。
【００４０】
しかしながら、幾つかの実施形態では、ネットワーク３００は、ネットワーク経路についての１又は複数の制約を有して良い。制約は、特定経路の中のイベント数を制限して良い。例えば、制約は、経路の中で生じる、ネットワークノード数、特定種類のネットワークノード数、特定種類の物理リンク数、及び／又は特定種類の処理（例えば、再生及び／又はリカラーリング）の発生数、を制限して良い。
【００４１】
説明のために、ネットワーク３００は、図３において破線のリンクとして識別される、ネットワーク３００内の任意の経路の中で許容される特定種類の物理リンク３０４の数を制限する制約を有して良い。破線の物理リンクは、リンクに関連付けられるノードにおいて生じる処理の種類（例えば、再生及び／又はリカラーリング）、特定種類のネットワークノードの通過、特定種類の物理リンクの通過、偏波依存損失の発生、又は別の因子に対応して良い。制約は、例えば、１つのこのような破線の物理リンク３０４を通過するよう（例えば本例におけるイベント）、全ての経路を制限して良い。最短経路３１０（例えば、ノード３０２−１→３０２−５→３０２−６→３０２−４）は、２つの破線の物理リンク３０４を通過するので（例えば、ノード３０２−１→３０２−５で１度、３０２−５→３０２−６でもう１度）、この制約に違反する。したがって、最短経路３１０は、送信元と宛先ノードとの間の最短経路であるにも拘わらず、例示的な制約を順守できない。
【００４２】
ネットワーク３００は、制約を考慮するために１又は複数の仮想ノードを使用して良い。図３Ｂは、仮想ノードを有する光ネットワーク３００の一実施形態の選択された要素のブロック図である。１又は複数の仮想ノードが各々のノード３０２に追加されて良い。仮想ノードは、制約の中のイベント発生数に対応して良い。例示的な制約では（つまり、ネットワーク３００の中の任意の経路は、１つの破線の物理リンク３０４を超えてはならない）、２つの仮想ノードが各々のノード３０２について生成されて良い。１つの仮想ノード（例えば、仮想ノード３０６）は、ゼロ個のイベント発生に対応して良く、他のノード（例えば、仮想ノード３０８）は、１つのイベント発生に対応して良い。各々のノード３０２は、対応する仮想ノード３０６及び３０８を有して良い。
【００４３】
最短経路アルゴリズムは、制約を有する最短経路を計算するために、仮想ノードに対して実行して良い。仮想ノードが物理リンクを用いてトラバースされるとき、イベント数が許容最大値を超えない場合、仮想リンクが仮想ノードの間に生成されて良い。例えば、仮想ノード３０６（例えば、ゼロ個のイベント発生に対応する仮想ノード）は、ゼロ個又は１回の発生に対応する近隣ノード３０２の仮想ノードにリンクして良い。イベントが仮想ノードに対応するノード３０２の間に存在しない又は発生しない場合、特定の仮想ノード３０６は、ゼロ個のイベント発生に対応する近隣仮想ノード３０６にリンクして良い。イベントが仮想ノードに対応するノード３０２の間に存在する又は発生する場合、特定の仮想ノード３０６は、１回のイベント発生に対応する近隣仮想ノード３０８にリンクして良い。同様に、仮想ノード３０８（例えば、１回のイベント発生に対応する仮想ノード）は、１回の発生に対応する近隣仮想ノードにリンクして良い。イベントが仮想ノードに対応するノード３０２の間に存在しない又は発生しない場合、特定の仮想ノード３０８は、近隣仮想ノード３０８にリンクして良い。しかしながら、イベントが仮想ノードに対応するノード３０２の間に存在する又は発生する場合、特定の仮想ノード３０８は、近隣ノード３０２の仮想ノードに結合することが許されない。つまり、特定の仮想ノード３０８から近隣仮想ノードへの経路は、最大許容イベント数を超えるので（つまり、制約に違反する）、ブロックされる。
【００４４】
最短経路の計算において、２つの仮想ノードの間に形成される任意の仮想リンクは、対応するノード３０２を結合する特定の物理リンク３０４と等価な重みを有する。例えば、ノード３０２−１の仮想ノードとノード３０２−２の仮想ノードとの間の仮想リンクは、これらの２つのノードを結合する物理リンク３０４と同じ重み（つまり、３）を有する。
【００４５】
仮想ノードを使用する制約を有する最短経路を計算するステップは、図３Ｂ〜Ｌに示される。始めに、各々の仮想ノード３０６及び仮想ノード３０８における結合重みは、送信元ノード３０２−１と宛先ノード３０２−４との間の最短経路の決定の際に仮想ノードがトラバースされていないことを表す無限大又は別の値（例えば、未定義値）に初期化されて良い。仮想ノード３０６−１の結合重みは、送信元ノード３０２−１からそれ自体までの距離が存在しないので、０に設定されて良い。
【００４６】
ネットワーク３００のトラバースは、送信元ノード３０２−１及びゼロ回のイベント発生に対応する仮想ノードである、仮想ノード３０６−１で開始して良い。図３Ｃでは、仮想ノード３０６−１からの近隣仮想ノードとの候補仮想リンクが検討される。例えば、仮想ノード３０６−１から仮想ノード３０６−２（例えば、イベント発生無しに対応する仮想ノード）までのリンクは、仮想ノード３０６−１から仮想ノード３０６−２まで破線の物理リンクを渡らなかったので、可能である。しかしながら、リンクが形成される前に、仮想ノードにおける既存の結合重みと候補リンクを用いる結合重みとの間で比較が行われて良い。候補リンクを有する結合重みが仮想ノードにおける既存の結合重みより小さい場合、仮想リンクが仮想ノードの間で形成されて良い。例えば、結合重み３が仮想ノード３０６−２における現在の結合重みである無限大より小さいので、仮想リンクは、仮想ノード３０６−１と仮想ノード３０６−２との間で形成されて良い。仮想ノード３０６−１における結合重みは、３に設定されて良く、ノード３０２−１をノード３０２−２に結合する物理リンク３０４の重みを反映する。ノード３０６−１からノード３０８−５までトラバースする際に１つの破線の物理リンクを渡ったので、及び結合重み２が、仮想ノード３０８−５における現在の結合重である無限大より小さいので、リンクは、仮想ノード３０６−１と３０８−５（例えば、１回のイベント発生に対応する仮想ノード）との間にも形成される。３０８−５における距離は、２に設定されて良く、ノード３０２−１をノード３０２−５に結合する物理リンク３０４の重みを反映する。近隣ノード３０２の仮想ノードが考慮された後、ノード３０２−１は訪問済みとしてマークされて良く、他の仮想ノードが仮想ノード３０６−１及び３０８−１にリンクできないようにする。
【００４７】
仮想ノード３０８−５は、訪問されていない仮想ノードのうち最小結合重みを有するので、次に検討されて良い。図３Ｄでは、仮想ノード３０８−５からの近隣仮想ノードとの候補仮想リンクが検討される。例えば、仮想ノード３０８−５からのリンクは、ノード３０８−５からノード３０８−３までトラバースする際に破線の物理リンクを渡らなかったので、及び結合重み５（例えば２＋３）が仮想ノード３０８−３における現在の結合重みである無限大より小さいので、仮想ノード３０８−３と形成される。仮想ノード３０８−３における結合重みは、５に設定されて良く、ノード３０２−１、３０２−５、及び３０２−３を結合する物理リンク３０４の結合重みを反映する。仮想ノード３０８−５と近隣ノード３０２−６に対応する仮想ノードとの間のリンクは、ノード３０２−５からノード３０２−６までトラバースする際に第２の破線の物理リンクを渡らなければならないので（例えば、経路は最大１つの破線の物理リンクを有して良いという制約の違反）、ブロックされて良い。近隣ノード３０２の仮想ノードが考慮された後、仮想ノード３０６−５は訪問済みとしてマークされて良く、他の仮想ノードがそれにリンクできないようにする。
【００４８】
仮想ノード３０６−２は、訪問されていない仮想ノードのうち最短距離を有するので、次に検討されて良い。図３Ｅでは、仮想ノード３０６−２からの近隣仮想ノードとの候補仮想リンクが検討される。例えば、仮想ノード３０６−２からのリンクは、ノード３０６−２からノード３０６−３までトラバースする際に破線の物理リンクを渡らなかったので、及び結合重み４（例えば３＋１）が仮想ノード３０６−３における現在の結合重みである無限大より小さいので、仮想ノード３０６−３と形成される。３０６−３における結合重みは、４に設定されて良く、ノード３０２−１、３０２−２、及び３０２−３を結合する物理リンク３０４の結合重みを反映する。ノード３０６−２からノード３０８−６までトラバースする際に破線の物理リンクを渡ったので、及び結合重み６（例えば３＋３）が仮想ノード３０８−６における現在の結合重みである無限大より小さいので、リンクは仮想ノード３０６−２と３０８−６との間にも形成される。３０８−６における結合重みは、６に設定されて良く、ノード３０２−１、３０２−２、及び３０２−６を結合する物理リンク３０４の結合重みを反映する。近隣ノード３０２の仮想ノードが考慮された後、仮想ノード３０６−２は訪問済みとしてマークされて良く、他の仮想ノードがそれにリンクできないようにする。
【００４９】
仮想ノード３０６−３は、訪問されていない仮想ノードのうち最短距離を有するので、次に検討されて良い。図３Ｆでは、仮想ノード３０６−３からの近隣仮想ノードとの候補仮想リンクが検討される。例えば、仮想ノード３０６−３からのリンクは、ノード３０６−３からノード３０６−５までトラバースする際に破線の物理リンクを渡らなかったので、及び結合重み７（例えば３＋１＋３）が仮想ノード３０６−５における現在の結合重みである無限大より小さいので、仮想ノード３０６−５と形成される。３０６−５における距離は、７に設定されて良く、ノード３０２−１、３０２−２、３０２−３及び３０２−５を結合する物理リンク３０４の結合重みを反映する。ノード３０６−３からノード３０８−４までトラバースする際に破線の物理リンクを渡ったので、及び結合重み８（例えば３＋１＋４）が仮想ノード３０８−４における現在の結合重みである無限大より小さいので、リンクは仮想ノード３０６−３と３０８−４との間にも形成される。３０８−６における結合重みは、６に設定されて良く、ノード３０２−１、３０２−２、及び３０２−６を結合する物理リンク３０４の結合重みを反映する。近隣ノード３０２の仮想ノードが考慮された後、仮想ノード３０６−３は訪問済みとしてマークされて良く、他の仮想ノードがそれにリンクできないようにする。
【００５０】
仮想ノード３０８−３は、訪問されていない仮想ノードのうち最小結合重みを有するので、次に検討されて良い。図３Ｇでは、仮想ノード３０８−３からの近隣仮想ノードとの候補仮想リンクが検討される。例えば、仮想ノード３０８−３からのリンクは、ノード３０８−３からノード３０８−２までトラバースする際に破線の物理リンクを渡らなかったので、及び結合重み６（例えば２＋３＋１）が仮想ノード３０８−２における現在の結合重みである無限大より小さいので、仮想ノード３０８−２と形成される。仮想ノード３０８−２における結合重みは、６に設定されて良く、３０２−１、３０２−５、３０２−３、及び３０２−２を結合する物理リンク３０４の重みを反映する。仮想ノード３０８−３と近隣ノード３０２−４に対応する仮想ノードとの間のリンクは、ノード３０２−３からノード３０２−４までトラバースする際に第２の破線の物理リンクを渡らなければならないので（例えば、経路は最大１つの破線の物理リンクを有して良いという制約の違反）、ブロックされて良い。近隣ノード３０２の仮想ノードが考慮された後、仮想ノード３０８−３は訪問済みとしてマークされて良く、他の仮想ノードがそれにリンクできないようにする。幾つかの実施形態では、仮想ノード３０６−３がより低い結合重み（例えば４＜５）を有し及び仮想ノード３０６−３がより少ないイベント発生（例えば０＜１）を表すので、仮想ノード３０８−３はスキップされて良い（例えば、近隣仮想ノードの分析又は仮想リンクの生成がされない）。したがって、仮想ノード３０８−３を通る経路は３０６−３を通る経路より短くならず、経路計算は、時間及びリソースを節約するために、仮想ノード３０８−３をスキップして良い。
【００５１】
仮想ノード３０８−２は、訪問されていない仮想ノードのうち最小結合重みを分け合うので、次に検討されて良い。図３Ｈでは、仮想ノード３０８−２からの近隣仮想ノードとの候補仮想リンクが検討される。仮想ノード３０８−２と近隣ノード３０２−６に対応する仮想ノードとの間のリンクは、ノード３０２−２からノード３０２−６までトラバースする際に第２の破線の物理リンクを渡らなければならないので（例えば、経路は最大１つの破線の物理リンクを有して良いという制約の違反）、ブロックされて良い。近隣ノード３０２の仮想ノードが考慮された後、仮想ノード３０８−２は訪問済みとしてマークされて良く、他の仮想ノードがそれにリンクできないようにする。
【００５２】
仮想ノード３０８−６は、訪問されていない仮想ノードのうち最小結合重みを有するので、次に検討されて良い。図３Ｉでは、仮想ノード３０８−６からの近隣仮想ノードとの候補仮想リンクが検討される。例えば、仮想ノード３０８−６からのリンクは、ノード３０８−６からノード３０８−４までトラバースする際に破線の物理リンクを渡らなかったので、及び結合重み７（例えば３＋３＋１）が仮想ノード３０８−４における現在の結合重みである無限大より小さいので、仮想ノード３０８−４と形成される。３０８−４における結合重みは、７に設定されて良く、ノード３０２−１、３０２−２、３０２−６及び３０２−４を結合する物理リンク３０４の結合重みを反映する。仮想ノード３０８−６と近隣ノード３０２−５に対応する仮想ノードとの間のリンクは、ノード３０２−６からノード３０２−５までトラバースする際に第２の破線の物理リンクを渡らなければならないので（例えば、経路は最大１つの破線の物理リンクを有して良いという制約の違反）、ブロックされて良い。近隣ノード３０２の仮想ノードが考慮された後、仮想ノード３０８−６は訪問済みとしてマークされて良く、他の仮想ノードがそれにリンクできないようにする。
【００５３】
仮想ノード３０６−５は、訪問されていない仮想ノードのうち最小結合重みを有するので、次に検討されて良い。図３Ｊでは、仮想ノード３０６−５からの近隣仮想ノードとの候補仮想リンクが検討される。仮想ノード３０６−５と仮想ノード３０６−１との間のリンクは、３０６−１が図３Ｃで訪問済みとして既にマークされているので、ブロックされて良い。同様に、仮想ノード３０６−５と仮想ノード３０８−６との間のリンクは、３０８−６が図３Ｉで訪問済みとして既にマークされているので、ブロックされて良い。近隣ノード３０２の仮想ノードが考慮された後、仮想ノード３０６−５は訪問済みとしてマークされて良く、他の仮想ノードがそれにリンクできないようにする。
【００５４】
仮想ノード３０８−４は、訪問されていない仮想ノードのうち最小結合重みを有するので、次に検討されて良い。図３Ｋでは、仮想ノード３０８−４からの近隣仮想ノードとの候補仮想リンクが検討される。仮想ノード３０８−４と近隣ノード３０２−３に対応する仮想ノードとの間のリンクは、ノード３０２−４からノード３０２−３までトラバースする際に第２の破線の物理リンクを渡らなければならないので（例えば、経路は最大１つの破線の物理リンクを有して良いという制約の違反）、ブロックされて良い。仮想ノード３０８−４と仮想ノード３０８−６との間のリンクは、３０８−６が図３Ｉで訪問済みとして既にマークされているので、ブロックされて良い。近隣ノード３０２の仮想ノードが考慮された後、仮想ノード３０６−５は訪問済みとしてマークされて良く、他の仮想ノードがそれにリンクできないようにする。
【００５５】
図３Ｋの後、訪問済みとしてマークされていない残りの仮想ノードは、ノード３０６−４及び３０６−６である。これらの仮想ノードの両方における結合重みは無限大であり、これらのノードへの仮想リンクが存在しないこと、したがって、これらの仮想ノードは制約を有するネットワーク３００において到達できないことを意味する。つまり、ゼロ個の破線の物理リンクを通過する送信元ノード３０２−１からノード３０２−６又はノード３０２−４への経路は存在しない。
【００５６】
ネットワーク３００内の全ての仮想ノードが検討された後、制約（例えば、１以下の破線の物理リンク）に違反しない送信元ノード３０２−１から宛先ノード３０２−４までの最短距離は、３０２−４にける仮想ノードから決定されて良い。仮想ノード３０６−４は、ネットワーク３００の中に送信元ノード３０２−１から宛先ノード３０２−４までの、ゼロ個の破線の物理リンクを通過する経路が存在しないことを示す、無限大の結合重みを有する。仮想ノード３０８−４は、制約に違反しない、送信元ノード３０２−１から宛先ノード３０２−４までの最短距離を表す結合重み７を有する。図３Ｌの最短経路３２０（例えば、ノード３０２−１→３０２−２→３０２−６→３０２−４）は、制約に違反しない送信元ノード３０２−１から宛先ノード３０２−４までの最短経路を表す。最短経路の中のノードの決定は、任意の適切な方法で追跡されて良い。例えば、仮想リンクが生成された前のノードは、最短経路の計算中に追跡されて良く、宛先ノードから送信元ノードへと逆に作業することにより、経路内の特定仮想ノードが決定されるようにして良い。
【００５７】
図３Ａ〜３Ｌは本発明に従い動作する例示的な最短経路アルゴリズムを示すが、上述の順序及び実装は限定を意図しない。上述の実装は、上述の変更が行われたダイクストラの最短経路アルゴリズムによる実装を表す。しかしながら、本発明は、図２に関して上述したものを含む別の最短経路アルゴリズムに対する同様の変更と共に実装されて良い。また、幾つかの実施形態では、制約はイベント（例えば、トラバースされる破線のリンク）を１より多くに制限して良い。例えば、制約は、経路をｎ回のイベントに制限して良い。このような一実施形態では、合計ｎ＋１個の仮想ノードが各々のノード３０２について生成されて良い。各々の仮想ノードは、許容イベント数（例えば、０からｎまで）に対応して良い。
【００５８】
上述のように、ネットワーク３００は、制約を有する最短経路を決定する制御システムを有して良い。図２の制御システムと同様に、実行可能命令（つまり、実行可能コード）は、本発明の１又は複数の特徴を実装するためにプロセッサにより実行されて良い。これらの命令は多くの形式をとり得るが、以下の疑似コードは制御システムにより実行され得る例示的な命令を表す。
【数１】
2017216684.tif 000003
【００５９】
図４は、光ネットワークの中の制約を有する最短経路を決定するための方法のフローチャートである。方法４００は、経路計算エンジン２０２を含む図２に記載した制御システム２００の要素のうちの１又は複数を用いて実行されて良い。留意すべきことに、方法４００で記載される特定の動作は、異なる実施形態では任意であって良く或いは再配置されて良い。
【００６０】
方法４００は、ステップ４０２で、制約により許容されるイベント数を決定することにより開始して良い。上述のように、制約は、ネットワークの中の送信元ノードと宛先ノードとの間の経路の中で許容可能なイベント数を定めて良い。イベントは、ネットワークノードの通過、物理リンクの通過、及び／又は特定種類の信号処理の実行（例えば、再生及び／又はリカラーリング）のような経路の中での発生を表して良い。制約は、ネットワーク経路の中の最大特定イベント数を表す。例えば、幾つかの実施形態では、制約は、コスト、遅延、雑音、伝送特性、及び／又はそれらの組み合わせを低減するために、経路の中で発生し得る再生及び／又はリカラーリングの数を制限して良い。
【００６１】
ステップ４０４で、仮想ノードは、ネットワークの中の各々のノードについて生成されて良い。制約がネットワーク経路の中で合計ｎ回のイベントを許容するとき、ｎ＋１個の仮想ノードが、ネットワークの中の各々のノードについて生成されて良い。各々の仮想ノードは、許容イベント数（例えば、０からｎまで）に対応して良い。
【００６２】
ステップ４０６で、送信元ノードの仮想ノードは、処理のために選択される。幾つかの実施形態では、トラバースされる最初のノードは、ゼロ個の許容イベントに対応する仮想ノードであって良い。
【００６３】
ステップ４０８で、近隣仮想ノードへの候補仮想リンクは、検討のために選択される。候補仮想リンクは、制約に違反せずに、現在の仮想ノードから近隣仮想ノードへの生成され得る仮想リンクを表す。例えば、ｘ回のイベント発生に対応する仮想ノードは、ｘ又はｘ＋ｙ回の発生に対応する近隣ノードの仮想ノードにリンクして良い。ここで、ｙは、仮想ノードに対応するノード間に存在する又は発生するイベント数を表す。
【００６４】
次に、ステップ４１０で、候補仮想リンクに沿う結合重みが、候補仮想リンクが接続し得る仮想ノードにおける現在の結合重みより小さいか否かに関して決定が行われて良い。例えば、候補仮想リンクの重みが、候補仮想リンクが生成され得る仮想ノード（例えば仮想ノードＡ）の結合重みに追加されて良い。計算された重みが、候補仮想リンクが生成され得る仮想ノード（例えば、仮想ノードＢ）における現在の結合重みより小さいとき、これは、仮想ノードＢへの任意の前の仮想リンクより、仮想ノードＢへのより短い経路を表し得る。ステップ４１０の結果がＮＯであるとき（例えば、候補仮想リンクに沿う結合重みが、候補仮想リンクが接続し得る仮想ノードにおける現在の結合重みより大きい）、方法４００は、ステップ４１４に進んで良い。このようなシナリオでは、候補仮想リンクは、仮想ノードＢへのより短い経路を表さない。しかしながら、ステップ４１０の結果がＹＥＳであるとき（例えば、候補仮想リンクに沿う結合重みが、候補仮想リンクが接続し得る仮想ノードにおける現在の結合重みより小さい）、方法４００は、仮想リンクが生成されるステップ４１２に進んで良い。このようなシナリオでは、候補仮想リンクは、仮想ノードＢへのより短い経路を表し得る。
【００６５】
次に、ステップ４１４で、検討するための更なる候補仮想リンクが存在するか否かに関して決定が行われて良い。検討するための更なる候補仮想リンクが存在する場合、方法４００は、ステップ４０８に戻って良い。ステップ４０８では、新しい候補仮想リンクが処理のために選択される。しかしながら、検討するための更なる候補仮想リンクが存在しない場合、方法４００はステップ４１６に進んで良い。
【００６６】
ステップ４１６で、処理中の仮想ノードは、訪問済みとしてマークされて良い。仮想ノードを訪問済みとしてマークすることは、他の仮想ノードが該ノードへの候補仮想リンクを検討することを防ぐことができる。このような実施形態では、訪問済み仮想ノードへの仮想リンクは、ブロックされ又は候補仮想リンクとして検討され得ない。
【００６７】
ステップ４１８で、検討されるべきネットワークの中の未訪問仮想ノードが存在するか否かに関して決定が行われて良い。動作４１８の結果がＹＥＳである場合、方法４００は、次の仮想ノードを処理するためにステップ４０８へ戻って良い。幾つかの実施形態では、トラバースされる次の仮想ノードは、最小結合重みを有する未訪問仮想ノードに対応して良い。ステップ４１８の結果がＮＯである場合、方法４００は、ステップ４２０へ進んで良い。
【００６８】
ステップ４２０で、制約に違反しない最短経路が識別される。幾つかの実施形態では、最短経路は、仮想ノード間の仮想リンクにより識別されて良い。例えば、最小結合重みを有する宛先ノードにおける仮想ノードは、制約に違反しない最短経路に対応して良い。したがって、仮想ノード間の仮想リンクは、最短経路を識別するために、送信元ノードにおいて仮想ノードへと逆にトラバースされて良い。最短経路は、仮想ノードの経路に対応するネットワークノードを通じて良い。経路は、制約に違反しない送信元ノードと宛先ノードとの間の最短経路を表して良い。例えば、制約が任意の経路で生じ得る再生及び／又はリカラーリングの数をｎに制限する場合、ｎ回以下の再生及び／又はリカラーリングを有する最短経路が識別される。制約に違反しない最短経路は、最小結合重みを有する宛先ノードにおける仮想ノードへの経路により表されて良い。識別された経路は、送信元と宛先ノードとの間の通信のために使用されて良い。例えば、ネットワーク制御システムは、識別された経路に沿う送信元と宛先ノードとの間の通信チャネルをプロビジョニングして良く、これらのノード間のトラフィックが経路の中の種々のノードに沿って向けられるようにする。
【００６９】
以上に開示した主題は、説明のためであり、限定ではないと考えられるべきである。また、添付の特許請求の範囲は、本開示の真の精神及び範囲に包含される全ての変更、拡張及び他の実施形態を包含することを意図している。したがって、法により認められる最大範囲まで、本開示の範囲は、特許請求の範囲及びその等価物の最も広い許容可能な解釈により決定されるべきであり、前述の詳細な説明により限定又は制限されるべきではない。
【００７０】
以上の実施形態に加えて、更に以下の付記を開示する。
（付記１）  光ネットワークの中の制約を有する最短経路を決定する方法であって、前記方法は、
前記制約により定められる許容イベント数を識別するステップと、
前記光ネットワークの中の各々のノードについて仮想ノードを生成するステップであって、前記仮想ノードは、前記許容イベント数に対応する、ステップと、
最短経路アルゴリズムにより送信元ノードから宛先ノードまで前記仮想ノードをトラバースするステップであって、前記仮想ノードをトラバースするステップは、
前記制約に違反しないとき、前記仮想ノードの間の仮想リンクを生成するステップであって、前記仮想リンクは物理リンクに対応する、ステップと、
前記仮想リンクから前記送信元ノードと前記宛先ノードとの間の最短経路を識別するステップであって、前記最短経路は前記制約に違反しない、ステップと、
を含む、ステップと、
を有する方法。
（付記２）  前記仮想ノードの間の仮想リンクを生成するステップは、
仮想ノードと近隣仮想ノードとの間の候補仮想リンクを識別するステップであって、前記近隣仮想ノードは、前記仮想ノードから前記近隣仮想ノードに到達するまでのイベント数に対応する、ステップと、
前記近隣仮想ノードの結合重みが前記仮想ノードを通じる前記近隣仮想ノードへの結合重みより大きいとき、前記候補仮想リンクから仮想リンクを生成するステップと、
を含む、付記１に記載の方法。
（付記３）  前記仮想ノードの間の仮想リンクを生成するステップは、前記近隣仮想ノードの前記結合重みが前記仮想ノードを通じる前記近隣仮想ノードへの前記結合重みより小さいとき、前記候補仮想リンクからの前記仮想リンクを無視するステップ、を更に含む、付記１に記載の方法。
（付記４）  前記最短経路アルゴリズムはダイクストラのアルゴリズムである、付記１に記載の方法。
（付記５）  前記制約は、光信号リカラーリング数を制限する、付記１に記載の方法。
（付記６）  前記制約は、光信号再生数を制限する、付記１に記載の方法。
（付記７）  前記ノードをトラバースするステップは、前記制約に違反するとき、前記仮想ノードの間の仮想リンクをブロックするステップを更に含む、付記１に記載の方法。
（付記８）  前記ノードをトラバースするステップは、
仮想ノードがトラバースされた後、該仮想ノードを訪問済みとしてマークするステップと、
仮想ノードを訪問済みとしてマークされた後、該仮想ノードへの仮想リンクをブロックするステップと、
を更に含む、付記１に記載の方法。
（付記９）  各々の仮想リンクは、対応するノードの間の前記物理リンクの重みに等しい重みを有する、付記１に記載の方法。
（付記１０）  前記最短経路を識別するステップは、
最小結合重みを有する前記宛先ノードの仮想ノードを識別するステップであって、前記最小結合重みは、前記最短経路の中の前記物理リンクの重みの和を表す、ステップと、
前記最小結合重みを有する仮想ノードから前記送信元ノードへの仮想リンクを辿るステップと、
を含む、付記１に記載の方法。
（付記１１）  制約を有する最短経路を識別する制御システムであって、前記制御システムは、命令を格納する記憶媒体へのアクセスを有するプロセッサを有し、前記命令は、前記プロセッサにより実行可能であり、
前記制約により定められる許容イベント数を識別し、
光ネットワークの中の各々のノードについて仮想ノードを生成し、前記仮想ノードは、前記許容イベント数に対応し、
前記制約に違反しないとき前記仮想ノードの間の仮想リンクを生成し、前記仮想リンクは物理リンクに対応し、前記仮想リンクから送信元ノードと宛先ノードとの間の最短経路を識別し、前記最短経路は前記制約に違反しない、ことにより、最短経路アルゴリズムにより前記送信元ノードから前記宛先ノードまで前記仮想ノードをトラバースする、
ためのものである、制御システム。
（付記１２）  前記仮想ノードの間の仮想リンクの生成は、
仮想ノードと近隣仮想ノードとの間の候補仮想リンクを識別し、前記近隣仮想ノードは、前記仮想ノードから前記近隣仮想ノードに到達するまでのイベント数に対応し、
前記近隣仮想ノードの結合重みが前記仮想ノードを通じる前記近隣仮想ノードへの結合重みより大きいとき、前記候補仮想リンクから仮想リンクを生成する、
付記１１に記載の制御システム。
（付記１３）  前記仮想ノードの間の仮想リンクの生成は、前記近隣仮想ノードの前記結合重みが前記仮想ノードを通じる前記近隣仮想ノードへの前記結合重みより小さいとき、前記候補仮想リンクからの前記仮想リンクを無視する、付記１１に記載の制御システム。
（付記１４）  前記最短経路アルゴリズムはダイクストラのアルゴリズムである、付記１１に記載の制御システム。
（付記１５）  前記制約は、光信号リカラーリング数を制限する、付記１１に記載の制御システム。
（付記１６）  前記制約は、光信号再生数を制限する、付記１１に記載の制御システム。
（付記１７）  前記記憶媒体は、前記制約に違反するとき、前記仮想ノードの間の仮想リンクをブロックするための命令を更に含む、付記１１に記載の制御システム。
（付記１８）  前記記憶媒体は、
仮想ノードがトラバースされた後、該仮想ノードを訪問済みとしてマークし、
仮想ノードを訪問済みとしてマークされた後、該仮想ノードへの仮想リンクをブロックする、
ための命令を更に含む、付記１１に記載の制御システム。
（付記１９）  各々の仮想リンクは、対応するノードの間の前記物理リンクの重みに等しい重みを有する、付記１１に記載の制御システム。
（付記２０）  前記最短経路の識別は、
最小結合重みを有する前記宛先ノードの仮想ノードを識別し、
前記最小結合重みを有する仮想ノードから前記送信元ノードまで、前記仮想リンクを辿る、
ことを含む、付記１１に記載の制御システム。
【符号の説明】
【００７１】
２００  制御システム
２０２  経路計算エンジン
２０４  データベース
２０６  シグナリングモジュール
２０８  プロセッサ
２１０  ルーティングモジュール
２１２  発見モジュール
２１４  ネットワークインタフェース
２２０  記憶媒体
２３０  ネットワーク
【図１】
2017216684.tif 000004
【図２】
2017216684.tif 000005
【図３Ａ】
2017216684.tif 000006
【図３Ｂ】
2017216684.tif 000007
【図３Ｃ】
2017216684.tif 000008
【図３Ｄ】
2017216684.tif 000009
【図３Ｅ】
2017216684.tif 000010
【図３Ｆ】
2017216684.tif 000011
【図３Ｇ】
2017216684.tif 000012
【図３Ｈ】
2017216684.tif 000013
【図３Ｉ】
2017216684.tif 000014
【図３Ｊ】
2017216684.tif 000015
【図３Ｋ】
2017216684.tif 000016
【図３Ｌ】
2017216684.tif 000017
【図４】
2017216684.tif 000018