(57)【要約】【課題】  開示の実施形態は、光ネットワーク内の光経路の評価のための技術を提供する。【解決手段】  マトリックスＭは、可能な再生器配置のグループを決定するために、及び再生器の所望の系列を選択することにより可能なエンド−エンド光経路を得るために用いられる。次に、階層的誘導検索は、可能な光経路から所望のＮタプル分離光経路を効率的に選択するために用いられても良い。階層的誘導検索は、検索を誘導するために並びに候補ノード及び光経路を検索処理の早い段階で削除するために、検索グラフ及び検索ツリーを用いても良い。【選択図】  図８
2015204623.tif 000002
【特許請求の範囲】
【請求項１】
光ネットワーク内の光経路の評価の方法であって、前記方法は、
光ネットワーク内のノードの全光経路到達可能性情報を有するマトリックスＭに基づき、送信元ノードと宛先ノードとの間の全光経路のセットを生成するステップであって、前記全光経路は、前記送信元ノードと前記宛先ノードとの間の最小数の再生器を有する、ステップと、
前記全光経路のセットの経路コスト情報を生成するステップであって、前記経路コスト情報は、前記全光経路のセットのコストメトリック情報を有する、ステップと、
前記経路コスト情報に基づき、前記全光経路に関連する各ノードの前記宛先ノードへのノードコスト情報を計算するステップと、
前記全光経路のセットに関連するノード、共通ノード間の光経路を有する光経路グループ、前記経路コスト情報、及び前記ノードコスト情報を有する階層的誘導検索グラフを生成するステップと、
前記階層的誘導検索グラフに基づき、前記送信元ノードと前記宛先ノードとの間の最低コスト光経路を決定するステップと、
を有する方法。
【請求項２】
前記コストメトリック情報は、待ち時間、距離、ハードウェアコスト、電力消費、超過帯域幅、及び超過光ペナルティ許容範囲、から選択された光経路の少なくとも１つの特性を示す、請求項１に記載の方法。
【請求項３】
前記送信元ノードと前記宛先ノードとの間の前記最低コスト光経路を決定するステップは、
前記階層的誘導検索グラフの中の前記送信元ノードから開始して、前記経路コスト情報及び前記ノードコスト情報に基づき、各ノードから、前記階層的誘導検索グラフ内の前記宛先ノードへ向かって各連続する再生器段への光経路グループを評価するステップであって、次の再生器段への次の光経路を選択するステップを含む、ステップ、
を更に有する、請求項１に記載の方法。
【請求項４】
各ノードから選択されていない未選択の光経路グループを更なる検討から削除するステップであって、前記未選択の光経路グループに依存して未選択のノードを更なる検討から削除するステップを含む、ステップ、
を更に有する請求項３に記載の方法。
【請求項５】
前記経路コスト情報、前記ノードコスト情報、及び選択された光経路間の分離性に基づき前記光経路グループを評価するステップと、
前に選択された光経路から分離される前記次の光経路を選択するステップと、
を更に有する請求項３に記載の方法。
【請求項６】
前記最低コスト光経路を含む、前記送信元ノードと前記宛先ノードとの間の複数の最低コスト光経路を決定するステップ、
を更に有する請求項３に記載の方法。
【請求項７】
前記複数の最低コスト光経路は、分離経路である、請求項６に記載の方法。
【請求項８】
光ネットワーク内の光経路の評価のための経路計算エンジンであって、前記経路計算エンジンは、命令を格納する記憶媒体へのアクセスを有するプロセッサにより実行可能な前記命令を有し、前記命令は、前記プロセッサに、
光ネットワーク内の全光経路到達可能性情報を有するマトリックスＭに基づき、送信元ノードと宛先ノードとの間の全光経路のセットを生成し、前記全光経路は、前記送信元ノードと前記宛先ノードとの間の最小数の再生器を有し、
前記全光経路のセットの経路コスト情報を生成し、前記経路コスト情報は前記全光経路のセットのコストメトリック情報を有し、
前記経路コスト情報に基づき、前記全光経路に関連する各ノードの前記宛先ノードへのノードコスト情報を計算し、
前記全光経路のセット、共通ノード間の光経路を有する光経路グループ、前記経路コスト情報、前記ノードコスト情報を有する階層的誘導検索グラフを生成し、
前記階層的誘導検索グラフに基づき、前記送信元ノードと前記宛先ノードとの間の最低コスト光経路を決定する、
ようにさせる、
経路計算エンジン。
【請求項９】
前記コストメトリック情報は、待ち時間、距離、ハードウェアコスト、電力消費、超過帯域幅、及び超過光ペナルティ許容範囲、から選択された光経路の少なくとも１つの特性を示す、請求項８に記載の経路計算エンジン。
【請求項１０】
前記送信元ノードと前記宛先ノードとの間の前記最低コスト光経路を決定する命令は、
前記階層的誘導検索グラフの中の前記送信元ノードから開始して、前記経路コスト情報及び前記ノードコスト情報に基づき、各ノードから、前記階層的誘導検索グラフ内の前記宛先ノードへ向かって各連続する再生器段への光経路グループを評価する命令であって、次の再生器段への次の光経路を選択する命令を含む、命令、
を更に有する、請求項８に記載の経路計算エンジン。
【請求項１１】
各ノードから選択されていない未選択光経路グループを更なる検討から削除する命令であって、前記未選択光経路グループに依存して未選択ノードを更なる検討から削除する命令を含む、命令、
を更に有する請求項１0に記載の経路計算エンジン。
【請求項１２】
前記経路コスト情報、前記ノードコスト情報、及び選択された光経路間の分離性に基づき前記光経路グループを評価する命令と、
前に選択された光経路から分離される前記次の光経路を選択する命令と、
を更に有する請求項１0に記載の方法。
【請求項１３】
前記最低コスト光経路を含む、前記送信元ノードと前記宛先ノードとの間の複数の最低コスト光経路を決定する命令、
を更に有する請求項１0に記載の経路計算エンジン。
【請求項１４】
前記複数の最低コスト光経路は、分離経路である、請求項１３に記載の経路計算エンジン。
【請求項１５】
光ネットワーク内の光経路の評価のための経路計算エンジンを有する光ネットワークでであって、前記経路計算エンジンは、命令を格納する記憶媒体へのアクセスを有するプロセッサにより実行可能な前記命令を有し、前記命令は、前記プロセッサに、
光ネットワーク内の全光経路到達可能性情報を有するマトリックスＭに基づき、送信元ノードと宛先ノードとの間の全光経路のセットを生成し、前記全光経路は、前記送信元ノードと前記宛先ノードとの間の最小数の再生器を有し、
前記全光経路のセットの経路コスト情報を生成し、前記経路コスト情報は前記全光経路のセットのコストメトリック情報を有し、
前記経路コスト情報に基づき、前記全光経路に関連する各ノードの前記宛先ノードへのノードコスト情報を計算し、
前記全光経路のセット、共通ノード間の光経路を有する光経路グループ、前記経路コスト情報、前記ノードコスト情報を有する階層的誘導検索グラフを生成し、
前記階層的誘導検索グラフに基づき、前記送信元ノードと前記宛先ノードとの間の最低コスト光経路を決定する、
ようにさせ、
前記コストメトリック情報は、待ち時間、ハードウェアコスト、電力消費、超過帯域幅、及び超過光ペナルティ許容範囲から選択された光経路の少なくとも１つの特性を示す、
光ネットワーク。
【請求項１６】
前記送信元ノードと前記宛先ノードとの間の前記最低コスト光経路を決定する命令は、
前記階層的誘導検索グラフの中の前記送信元ノードから開始して、前記経路コスト情報及び前記ノードコスト情報に基づき、各ノードから、前記階層的誘導検索グラフ内の前記宛先ノードへ向かって各連続する再生器段への光経路グループを評価する命令であって、次の再生器段への次の光経路を選択する命令を含む、命令、
を更に有する、請求項１５に記載の光ネットワーク。
【請求項１７】
各ノードから選択されていない未選択の光経路グループを更なる検討から削除する命令であって、前記未選択の光経路グループに依存して未選択ノードを更なる検討から削除する命令を含む、命令、
を更に有する請求項１６に記載の光ネットワーク。
【請求項１８】
前記経路コスト情報、前記ノードコスト情報、及び選択された光経路間の分離性に基づき前記光経路グループを評価する命令と、
前に選択された光経路から分離される前記次の光経路を選択する命令と、
を更に有する請求項１６に記載の光ネットワーク。
【請求項１９】
前記最低コスト光経路を含む、前記送信元ノードと前記宛先ノードとの間の複数の最低コスト光経路を決定する命令、
を更に有する請求項１６に記載の光ネットワーク。
【請求項２０】
前記複数の最低コスト光経路は、分離経路である、請求項１９に記載の光ネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、概して、光通信ネットワークに関し、より詳細には、Ｎタプル分離光経路の階層的誘導検索に関する。
【背景技術】
【０００２】
電気通信システム、ケーブルテレビシステム、データ通信ネットワークは、光ネットワークを用いて、遠隔地点間で大量の情報を迅速に伝達する。光ネットワークでは、情報は、光ファイバを通じて光信号の形式で伝達され得る。光ネットワークは、増幅器、分散補償器、マルチプレクサ／デマルチプレクサフィルタ、波長選択スイッチ、カプラ、等のような、ネットワーク内で種々の動作を実行するよう構成される種々のネットワークコンポーネントを有しても良い。
【０００３】
種々のネットワーク要素を通じる光信号経路の計算の機能は、光ネットワークの設計、モデル化、管理、及び制御のための中核機能である。光経路計算は、光ネットワークのオペレータがネットワークポリシをカスタマイズし、制御し及び更新することを可能し得る。光経路計算の１つの特徴は、送信元ノードから宛先ノードまでのエンド−エンドの到達可能光経路の決定を含む。送信元ノード及び宛先ノードが「直接到達可能」であると決定されるとき、全て光経路である１又は複数の経路が、送信元ノードと宛先ノードとの間の光ネットワーク内に存在する。
【０００４】
送信元ノードから宛先ノードまでの直接到達可能性が存在しない場合、光信号は、光−電気−光（optical−electrical−optical：ＯＥＯ）再生器を用いて、所与の信号経路に沿って電気的に再生されるだろう。これは、多大なネットワークリソースを巻き込み、コスト効率があまり良くない。再生器が用いられるとき、エンド−エンド到達可能経路は、送信元ノードと宛先ノードとの間に特定数の再生器を有しても良い。したがって、光経路計算における１つの困難な目標は、最小限又は指定数の再生器を有するエンド−エンド到達可能経路を見付けること、更に、例えば所望のレベルの信号待ち時間若しくはコストのような他の経路制約を満たすことである。例えば、米国特許出願番号第１４／１６９，９８０号、２０１４年１月３１日出願、は、再生器ノード位置を決定するための、到達可能性マトリックス、及びマトリックス演算に関する推移閉包の特性の使用を開示する。しかしながら、一連の到達可能マトリックスの計算中に消費されるメモリ量は、計算効率又は計算上の実現性を表し得る。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
開示の実施形態は、光ネットワーク内の光経路の評価のための技術を提供する。
【課題を解決するための手段】
【０００６】
一態様では、開示の方法は、光ネットワーク内の光経路の評価のためのものである。光ネットワーク内のノードの全光経路到達可能性情報を含むマトリックスＭに基づき、方法は、送信元ノードと宛先ノードとの間の全光経路のセットを生成するステップを有しても良い。全光経路は、送信元ノードと宛先ノードとの間の最小数の再生器を有しても良い。全光経路のセットは、再生器段に従ってグループ化されても良い。方法は、全光経路のセットの経路コスト情報を生成するステップを更に有しても良い。経路コスト情報は、各全光経路毎のコストメトリックを有しても良い。経路コスト情報に基づき、方法は、宛先ノードを除いて、宛先ノードへの全光経路に関連する各ノードについてノードコスト情報を計算するステップ、を更に有しても良い。方法は、階層的誘導検索グラフを生成するステップであって、階層的誘導検索グラフは、全光経路のセット、共通ノード間の光経路を有する光経路グループ、経路コスト情報、及びノードコスト情報に関連付けられるノードを有する、ステップを有しても良い。階層的誘導検索グラフに基づき、方法は、送信元ノードと宛先ノードとの間の最低コスト光経路を決定するステップを有しても良い。
【０００７】
開示の実施形態のうちの任意の実施形態で、前記送信元ノードと前記宛先ノードとの間の前記最低コスト光経路を決定するステップは、前記階層的誘導検索グラフの中の前記送信元ノードから開始して、前記経路コスト情報及び前記ノードコスト情報に基づき、各ノードから、前記階層的誘導検索グラフ内の前記宛先ノードへ向かって各連続する再生器段への光経路グループを評価するステップであって、次の再生器段への次の光経路を選択するステップを含む、ステップ、を更に有しても良い。
【０００８】
更に開示の態様は、光ネットワーク内の光経路の計算のための経路計算エンジンを有しても良い。経路計算エンジンは、命令を格納する記憶媒体へのアクセスを有するプロセッサにより実行可能な命令を有しても良い。更に別の開示の態様は、本願明細書に記載のような経路計算エンジンを有する光ネットワークを有しても良い。
【図面の簡単な説明】
【０００９】
本発明並びにその特徴及び利点のより完全な理解のため、添付の図と共に以下の説明を参照する。
【図１】光ネットワークの一実施形態の選択された要素のブロック図である。
【図２】光ネットワークの制御システムの一実施形態の選択された要素のブロック図である。
【図３】ネットワークトポロジの一実施形態の選択された要素のブロック図である。
【図４】ネットワークトポロジの一実施形態の選択された要素のブロック図である。
【図５】メモリ効率の良いマトリックスに基づく光経路計算のための方法の一実施形態の選択された要素のフローチャートである。
【図６】メモリ効率の良いマトリックスに基づく光経路計算のための方法の一実施形態の選択された要素のフローチャートである。
【図７Ａ】階層的誘導検索グラフの一実施形態の選択された要素のネットワーク図である。
【図７Ｂ】階層的誘導検索状態ツリーの一実施形態の選択された要素のネットワーク図である。
【図８】階層的誘導検索を用いた光経路評価のための方法の一実施形態の選択された要素のフローチャートである。
【発明を実施するための形態】
【００１０】
以下の説明では、開示の主題の議論を容易にするために例として詳細事項が説明される。しかしながら、当業者には、開示の実施形態が例示であること及び全ての可能な実施形態を網羅するものではないことが明らかである。
【００１１】
ここで用いられるように、ハイフンで結んだ形式の参照符号は、１つの要素の特定のインスタンスを表し、ハイフンを有しない形式の参照符号は、集合的要素を表す。したがって、例えば、装置「７２−１」（図中で用いられない）は、装置クラスのインスタンスを表しても良く、集合的に装置「７２」として表されても良く、これらのうちの任意のものが装置「７２」として一般的に表されても良い。
【００１２】
図に戻ると、図１は、光ネットワーク１０１の例示的な実施形態を示す。図示のように、光ネットワーク１０１は、ユーザデータを伝達しネットワーク機器を有する要素を含むトランスポートプレーンビューを示し得る。したがって、光ネットワーク１０１は、光ネットワーク１０１のコンポーネントにより通信される１又は複数の光信号を運ぶよう構成される１又は複数の光ファイバ１０６を有しても良い。光ネットワーク１０１のネットワーク要素は、ファイバ１０６により互いに結合され、１又は複数の送信機１０２、１又は複数のマルチプレクサ（ＭＵＸ）１０４、１又は複数の増幅器１０８、１又は複数の光アド／ドロップマルチプレクサ（optical  add/drop  multiplexer：ＯＡＤＭ）１１０、及び１又は複数の分受信機１１２を有しても良い。
【００１３】
光ネットワーク１０１は、端末ノードを有するポイントツーポイント型光ネットワーク、リング型光ネットワーク、メッシュ型光ネットワーク、又は任意の他の適切な光ネットワーク若しくは光ネットワークの組合せを有しても良い。光ファイバ１０６は、非常に低損失で長距離に渡り信号を伝達可能なガラスの細い紐を有し得る。光ファイバ１０６は、任意の適切な種類のファイバを有しても良い。
【００１４】
光ネットワーク１０１は、ファイバ１０６を介して光信号を送信するよう構成される装置を有しても良い。情報は、波長に関する情報を符号化するために１又は複数の光の波長の変調により、ネットワーク１０１を通じて送信及び受信されても良い。光ネットワークでは、光の波長は、チャネルとも称される。各チャネルは、光ネットワーク１０１を通じて特定量の情報を伝達するよう構成されても良い。
【００１５】
光ネットワーク１０１の情報伝達能力を増大するために、複数のチャネルで送信される複数の信号は、単一の光信号に結合されても良い。単一の光信号の複数のチャネルで情報を通信するプロセスは、光学的にＷＤＭ（wavelength  division  multiplexing）として言及される。ＤＷＤＭ（Dense  wavelength  division  multiplexing）は、より多数の（密度の高い）、通常４０より多い波長の１本のファイバへの多重化を表す。ＷＤＭ、ＤＷＤＭ、又は他の複数波長送信技術は、光ファイバ当たりの集約帯域幅を増大するために、光ネットワークで用いられる。ＷＤＭ又はＤＷＤＭを有しないと、光ネットワークにおける帯域幅は、単に１波長のビットレートに制限され得る。より大きな帯域幅により、光ネットワークは、より多くの情報を送信できる。光ネットワーク１０１は、ＷＤＭ、ＤＷＤＭ又は特定の他の適切な多チャネル多重化技術を用いて異なるチャネルを送信し、多チャネル信号を増幅するよう構成されても良い。
【００１６】
光ネットワーク１０１は、特定の波長又はチャネルで、光ネットワーク１０１を通じて光信号を送信するよう構成される１又は複数の光送信機（Ｔｘ）１０２を有しても良い。送信機１０２は、電気信号を光信号に変換し該光信号を送信するよう構成される任意のシステム、機器、又は装置を有しても良い。例えば、送信機１０２は、それぞれ、レーザと、電気信号を受信し該電気信号に含まれる情報を特定の波長でレーザにより生成される光のビームに変調しネットワークを通じて信号を伝達するビームを送信するよう構成される変調器と、を有しても良い。
【００１７】
マルチプレクサ１０４は、送信機１０２に結合されても良く、送信機１０２により個々の波長で送信される信号を単一のＷＤＭ又はＤＷＤＭ信号に結合するよう構成される任意のシステム、機器又は装置であっても良い。
【００１８】
増幅器１０８は、光ネットワーク１０１内の多チャネル信号を増幅しても良い。増幅器１０８は、特定長のファイバ１０６の前又は後に置かれても良い。増幅器１０８は、信号を増幅するよう構成される任意のシステム、機器又は装置を有しても良い。例えば、増幅器１０８は、光信号を増幅する光リピータを有しても良い。この増幅は、光−電気又は電気−光変換により実行されても良い。幾つかの実施形態では、増幅器１０８は、希土類元素をドープされた光ファイバを有しても良い。信号がファイバを通過するとき、外部エネルギが印可され、光ファイバのドープされた部分の原子を励起し、光信号の強度を増大する。一例として、増幅器１０８は、エルビウムドープファイバ増幅器（erbium−doped  fiber  amplifier：ＥＤＦＡ）を有しても良い。種々の実施形態では、半導体光増幅器（semiconductor  optical  amplifier：ＳＯＡ）のような他の適切な増幅器が用いられても良い。
【００１９】
ＯＡＤＭ１１０は、ファイバ１０６を介して光ネットワーク１０１に結合されても良い。ＯＡＤＭ１１０は、ファイバ１０６から光信号をアッド及びドロップするよう構成される任意のシステム、機器又は装置を有しても良いアッド／ドロップモジュールを有しても良い。ＯＡＤＭ１１０を通過した後に、信号は、ファイバ１０６に沿って宛先へと直接進んでも良く、或いは、信号は、宛先に達する前に、１又は複数の追加ＯＡＤＭ１１０を通過しても良い。光ネットワーク１１０の特定の実施形態では、ＯＡＤＭ１１０は、例えばＷＳＳ（wavelength  selective  switch）を用いて光領域でアッド又はドロップされるべきデータチャネルを伝達するＷＤＭ信号の個々の又は複数の波長をアッド又はドロップできるＲＯＡＤＭ（reconfigurable  OADM）を表しても良い。
【００２０】
光ネットワーク１０１は、光ネットワーク１０１の１又は複数の宛先に、１又は複数のデマルチプレクサ１０５を有しても良い。デマルチプレクサ１０５は、単一のＷＤＭ信号をその個々のチャネルに分離することによりデマルチプレクサとして動作し得る任意のシステム、機器又は装置を有しても良い。例えば、光ネットワーク１０１は、４０チャネルＤＷＤＭ信号を送信及び伝達しても良い。デマルチプレクサ１０５は、４０個の異なるチャネルに従って、信号、４０チャネルＤＷＤＭ信号を４０個の別個の信号に分割しても良い。
【００２１】
光ネットワーク１０１は、デマルチプレクサ１０５に結合される受信機１１２を有しても良い。各受信機１１２は、特定の波長又はチャネルで送信される信号を受信し、該信号をそれらが含む情報について処理するよう構成されても良い。したがって、光ネットワーク１０１は、ネットワークの各チャネル毎に少なくとも１つの受信機１１２を有しても良い。
【００２２】
光ネットワーク１０１のような光ネットワークは、光ファイバを介して光信号の中で情報を伝達するために、変調方式を更に用いても良い。このような変調方式は、ＰＳＫ（phase−shift  keying）、ＦＳＫ（frequency−shift  keying）、ＡＳＫ（amplitude−shift  keying）、及びＱＡＭ（quadrature  amplitude  modulation）を有しても良い。ＰＳＫでは、光信号により伝達される情報は、搬送波又は単にキャリアとしても知られる参照信号の位相を変調することにより変換されても良い。情報は、ＤＰＳＫ（differential  phase−shift  keying）を用いて信号自体の位相を変調することにより変換されても良い。ＱＡＭでは、光信号により運ばれる情報は、搬送波の振幅と位相の両方を変調することにより伝達されても良い。ＰＳＫは、ＱＡＭの一部であると考えられる。ここで、搬送波の振幅は、一定に維持される。
【００２３】
光ネットワーク１０１のような光通信ネットワークでは、管理プレーン、制御プレーン、及びトランスポートプレーン（物理層と呼ばれることが多い）を言及することが通常である。中央管理ホスト（図示しない）は、管理プレーンに存在しても良く、制御プレーンのコンポーネントを構成し管理しても良い。管理プレーンは、トランスポートプレーン及び制御プレーンのエンティティ（例えば、ネットワーク要素）全てに渡る最終的な制御を有する。一例として、管理プレーンは、１又は複数の処理リソース、データ記憶コンポーネント、等を含む中央処理センタ（例えば、中央管理ホスト）を有しても良い。管理プレーンは、制御プレーンの要素と電気的に通信しても良く、トランスポートプレーンの１又は複数のネットワーク要素と電気的に通信しても良い。管理プレーンは、システム全体の管理機能を実行し、ネットワーク要素、制御プレーン及びトランスポートプレーンの間の調整を提供しても良い。例として、管理プレーンは、要素の観点から１又は複数のネットワーク要素を取り扱うＥＭＳ（element  management  system）、ネットワークの観点から多くの装置を取り扱うＮＭＳ（network  management  system）、及びネットワーク全体の動作を取り扱うＯＳＳ（operational  support  system）を有しても良い。
【００２４】
本開示の範囲から逸脱することなく、光ネットワーク１０１に対し変更、追加又は省略が行われても良い。例えば、光ネットワーク１０１は、図示のものより多くの又は少ない要素を有しても良い。追加で、光ネットワーク１０１は、分散補償モジュールのような明示されない追加要素を有しても良い。また、上述のように、ポイントツーポイントネットワークとして図示されたが、ネットワーク１０１は、リング又はメッシュ型ネットワークのような光信号を送信する任意の適切なネットワークを有しても良い。
【００２５】
動作中、光ネットワーク１０１は、種々のノード及びノード間の光経路接続を有しても良い。本願明細書に開示のように、メモリ効率の良いマトリックスに基づく光経路計算は、光ネットワーク１０１内のノードについて実行されても良い。
【００２６】
図２を参照すると、例えば光ネットワーク１０１（図１を参照）におけるような光ネットワークにおける制御プレーン機能を実装する制御システム２００の一実施形態の選択された要素のブロック図が示される。制御プレーンは、ネットワーク知能及び制御のための機能を有しても良く、更に詳細に記載するように発見、ルーティング、経路計算、及びシグナリングのためのアプリケーション又はモジュールを含むネットワークサービスを確立する能力をサポートするアプリケーションを有しても良い。制御システム２００により実行される制御プレーンアプリケーションは、光ネットワーク内でサービスを自動的に確立するために一緒に動作しても良い。発見モジュール２１２は、近隣同士を接続するローカルリンクを発見しても良い。ルーティングモジュール２１０は、データベース２０４を移植する（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：ＡＳＥ）のような送信劣化因子が、光信号送信経路内で光信号にどれ位影響を与え得るかについての見識を提供しても良い。光信号送信経路の送信特性を決定するために、経路計算エンジン２０２は、送信劣化因子の間の相互作用を検討しても良い。種々の実施形態では、経路計算エンジン２０２は、特定の送信劣化因子の値を生成しても良い。経路計算エンジン２０２は、光信号送信経路を記述するデータをデータベース２０４に更に格納しても良い。
【００３３】
図２で、シグナリングモジュール２０６は、光ネットワーク１０１のような光ネットワークにかえるエンド−エンドサービスを設定、変更、及び取り壊しに関連する機能を提供しても良い。例えば、光ネットワーク内のイングレスノードがサービス要求を受信すると、制御システム１００は、シグナリングモジュール２０６を用いて、帯域幅、コスト、等のような異なる基準に従って最適化され得る経路計算エンジン２０２からのネットワーク経路を要求しても良い。所望のネットワーク経路が識別されると、次に、シグナリングモジュール２０６は、要求されたネットワークサービスを確立するために、ネットワーク経路に沿って個々のノードと通信しても良い。異なる実施形態では、シグナリングモジュール２０６は、ネットワーク経路に沿ってノードへ及びノードから後続の通信を伝搬するために、シグナリングプロトコルを用いても良い。
【００３４】
制御システム２００の動作では、光経路計算の特徴は、エンド−エンドの到達可能経路の計算を有しても良い。前述のように、直接到達可能経路は、送信元ノードと宛先ノードとの間で光信号が純粋に光コンポーネントを通じて送信され受信される光ネットワークにおける送信元ノードと宛先ノードとの間の経路を表しても良い。このような直接到達可能経路は、例えば、本願明細書で単に「再生器」と称されるＯＥＯ再生器を用いた光信号の電気的再生を宛先に到達する前に含む送信元ノードと宛先ノードとの間の間接到達可能経路とは対照的であっても良い。間接到達可能経路は、複数の再生器を有しても良い。したがって、エンド−エンド到達可能経路は、送信元ノードから、第１の再生器ノードまで、少なくとも１つの第２の再生器ノードまで、及び最終的には宛先ノードまでの経路を有しても良い。経路計算エンジン２０２は、待ち時間及びコストのような他の経路制約を満たすことと共に、最小限の又は特に指定された数の再生器を統合するエンド−エンド到達可能経路を発見するよう構成されても良い。
【００３５】
経路計算エンジン２０２は、エンド−エンド到達可能経路計算を決定するために、グラフ変換を実行するよう更に構成されても良い。グラフ変換は、光ネットワークの物理コンポーネントから初めに決定された物理トポロジに仮想リンクを追加することを含み得る。仮想リンクは、、２つのノードが再生器の介入無しに光学的に到達可能なように、２つのノードを接続するリンクを表し得る。ノード対を光学的に到達可能に接続する全ての仮想リンクがグラフトポロジに追加された後に、元のトポロジは、到達可能性グラフに変換されても良い。その後、最小数の再生器を要求するエンド−エンド到達可能経路を得るために最小ホップルーティングが実行されても良い。このような機能を実行するために、計算負荷の多い経路アルゴリズムが経路計算エンジン２０２により用いられ、所望の数及び種類の到達可能経路を得る。しかしながら、このようなグラフ変換に基づくエンド−エンド到達可能経路計算を実行するために経路計算エンジン２０２を構成することは、大規模なグラフ理論及びルーティングアルゴリズムの使用を伴う。これは、扱うのに複雑であり且つ負担になる。
【００３６】
さらに、経路計算エンジン２０２は、グラフ変換に依存するのではなく、マトリックス演算に基づく到達可能性マトリックス型光経路計算を実行するよう構成されても良い。したがって、経路計算エンジン２０２は、対応する到達可能性グラフを表すために到達可能性マトリックスを用い、マトリックス演算に基づいて光経路計算を実行するよう構成されても良く、したがって、複雑なグラフ変換及びルーティングアルゴリズムを回避し得る。到達可能性マトリックスに基づく光経路計算を用いることにより、経路計算エンジン２０２は、少ない光工学的複雑性で構成され得る。さらに、経路計算エンジン２０２は、光ネットワーク１０１の種々の部分の光経路計算機能を集約しても良い。さらに、経路計算エンジン２０２は、光ネットワーク１０１におけるＳＤＮ（software−defined  network）を可能にするために、制御システム２００に抽象化光ネットワークビューを提供しても良い。制御システム２００及び経路計算エンジン２０２は図２に単一要素として示されるが、経路計算エンジン２０２により実行される光経路計算は、モジュラー化され実装され、スケーラブル且つ複数の装置（図示しない）に渡り並列的方法で展開されて、変化するサイズ又はノード複雑性の光ネットワークにおいて経路計算をサポートしても良いことが理解される。
【００３７】
本願明細書に更に詳述されるように、動作中、制御システム２００は、メモリ効率の良いマトリックスに基づく光経路計算のために用いられても良い。具体的には、経路計算エンジン２０２は、到達可能性マトリックスを用いるマトリックス演算に基づく光経路計算を実行するために用いられても良い。さらに、経路計算エンジン２０２は、一連の到達可能性マトリックスＲＭ＾ｉに格納されるとき、全ての情報又は等価な情報を保持し得る単一のマトリックスＭを用いて、メモリ効率の良いマトリックスに基づく光経路計算を実行しても良い。この方法では、本願明細書に開示のメモリ効率の良いマトリックスに基づく光経路計算は、一連の到達可能性マトリックスＲＭ＾ｉ、ｉ＝１，．．．，Ｒ当たりの（例えば経路計算エンジン２０２による）計算リソースの量を削減できる。ここで、ｉは個々の到達可能性マトリックスＲＭ＾ｉにより示される最小ホップ数であり、Ｒは、所与のネットワークトポロジにおける合計ノード数のようなｉの上限である。計算リソースは、計算の実現性の決定要因であり得るメモリ量又は計算効率を含み得る。特に、Ｎが比較的大きいとして、数千個のノードのようなＮ個のノードを有する大規模ネットワークでは、本願明細書に開示のようなメモリ効率の良いマトリックスに基づく光経路計算は、計算上扱いやすい方法で、全系列の到達可能性マトリックスＲＭ＾ｉの計算又は所望の時間における到達可能性マトリックスＲＭ＾ｉのうちの任意の所望の１つの計算を可能にし、特に光ネットワークプロビジョニングに関連するリアルタイムアプリケーションにとって、このような光経路計算を実現可能に又は経済的に実現可能にする。
【００３８】
具体的には、マトリックスＭの要素値は、例えば、光ネットワーク１０１における所望の送信元ノードから所望の宛先ノードまでの全光経路を形成するために連結され得る全ての光経路の数（つまり、ホップ）を示すｍｉｊであり得る。特定の実施形態では、ｍｉｊは、１に、ノードｉ及びノードｊが再生器を用いて到達可能であるとき、ノードｉをノードｊに接続する再生器の最小数を加えた値を有しても良い。ノードｉとノードｊが任意の数の再生器を用いて到達可能ではないとき、ｍｉｊはゼロ（０）の値を有しても良い。以下に説明するように、種々の実施形態では、ｉ＝ｊのとき、ｍｉｊは０又は１であっても良い。このように、マトリックスＭは、Ｍの前の値（又は前の反復）が情報損失無しにＭの現在の値（又は現在の反復）で上書きされ得る所謂「適所」メモリ消費を用いて計算され得る。計算効率の良い（少なくともＯ（Ｎ＾３））、Ｍを計算する第１のアルゴリズムは、図３に関して更に詳述される。
【００３９】
図３を参照すると、本願明細書に開示されるようなメモリ効率の良いマトリックスに基づく光経路計算の例示的な一実施形態を説明するネットワークトポロジ３００の一実施形態の選択された要素のブロック図が示される。図示のように、ネットワークトポロジ３００は、ノードＡ、Ｂ、Ｃ、Ｄを有し、これらのノード間に特定の指向性光経路３０２が存在する。ネットワークトポロジ３００では、光経路３０２−１は、ノードＢからノードＡまでの光通信を可能にする。ネットワークトポロジ３００では、光経路３０２−２は、ノードＡからノードＣまでの光通信を可能にする。ネットワークトポロジ３００では、光経路３０２−３は、ノードＣからノードＤまでの光通信を可能にする。ネットワークトポロジ３００では、光経路３０２−４は、ノードＤからノードＡまでの光通信を可能にする。ネットワークトポロジ３００では、光経路３０２−５は、ノードＣからノードＢまでの光通信を可能にする。したがって、米国特許出願番号１４／１６９，９８０に開示のように、ネットワークトポロジ３００の到達可能性マトリックス（reachability  matrix：ＲＭ）は、表１に与えられ得る。
【表１】
2015204623.tif 000003
［表１］ネットワークトポロジ３００の全ての到達可能性マトリックス（ＲＭ）
【００４０】
表１では、及びマトリックスを示す以下の表では、行は送信元ノードを表し、列は宛先ノードを表す。したがって、表１の到達可能性マトリックスにおいて異なるノードの１の各値は、図３の指向性光経路３０２を示す。任意の習慣として、同じノードへの接続について表１の到達可能性マトリックス内の識別値は１であるが、他の実施形態では０であっても良い。
【００４１】
マトリックスＭを計算するためのネットワークトポロジ３００についてのメモリ効率の良いマトリックスに基づく光経路計算のための第１のアルゴリズムの例示的な一実施形態を以下に更に詳細に記載する。第１のアルゴリズムは、計算効率が良く（少なくともＯ（Ｎ＾３））、推移閉包のFloyd−Warshallアルゴリズムに基づいても良い。第１のアルゴリズムは、ネットワークトポロジ３００について表１の到達可能性マトリックスで開始しても良い。第１のアルゴリズムでは、表１の到達可能性マトリックスは、表２に与えられるようなマトリックスＭの開始バージョンを生じるように変更されても良い。
【表２】
2015204623.tif 000004
［表２］ネットワークトポロジ３００の到達可能性マトリックス（ＲＭ）に基づくマトリックスＭの開始バージョン
【００４２】
表２では、同じノードへの接続について表１の到達可能性マトリックスからの識別値は０に設定される。これは識別値の任意の習慣である。また、表２では、表１の到達可能性マトリックスからの０の値は、値Ｘを与えられる。幾つかの実施形態では、値Ｘは、計算上の目的で無限大（∞）に選択されても良い。所与の実施形態では、値Ｘは、計算上の目的で任意の他の数値より大きくなるよう選択されても良い。特定の実施形態では、値Ｘは、計算上の目的で変数の最大範囲になるよう選択されても良い。特定の実施形態では、値Ｘは、ネットワークトポロジ３００について４より大きいような、光経路計算が実行されているネットワークトポロジにおけるノードの数より大きくなるよう選択されても良い。
【００４３】
第１のアルゴリズムでは、マトリックスＭは、マトリックスＭ内のマトリックス要素が各個々のマトリックス要素について２つのノード間のエンド−エンド全光接続を生成するために連結され得る全光経路の最小数を表すように、最終的に計算される。表２のマトリックスＭから開始して、マトリックスＭは、マトリックスＭを計算するためのメモリ消費を最小化するために、連続的ステップ又は反復でin−placeで計算され得る。幾つかの実施形態では、連続的ステップは、ｎ回の反復に渡り繰り返されても良い。幾つかの実施形態では、連続的ステップは、例えば、マトリックスＭがｎ回の反復に達する前に収束するとき、ｎ回より少ない反復の後に終了しても良い。ｎはマトリックスＭが計算されているネットワークトポロジにおけるノード数であり、ｋ＝１，．．．，ｎとして、各連続的ステップｋ毎に、第１のアルゴリズムでのマトリックスＭの計算は、表３に与えられる擬似コードにより示され得る。
【表３】
2015204623.tif 000005
［表３］マトリックスＭを計算するための第１のアルゴリズムの擬似コード
【００４４】
表３に示す擬似コードにおいて明らかなように、第１のアルゴリズムで、繰り返されるｋの各値について、表ｋ及び列ｋは前のマトリックスＭから変化しないままである。表３の擬似コードに基づき、表３のマトリックスＭの開始バージョンに基づき、ｋ＝１について第１のアルゴリズムに従って最終的なマトリックスＭを計算する第１のステップは、表４に示される。
【表４】
2015204623.tif 000006
［表４］ｋ＝１について第１のアルゴリズムでのマトリックスＭの第１の反復
【００４５】
表４で、ｋ＝１のとき、行Ａ及び列Ａは、第１のアルゴリズムの第１の反復において表３と変わらないままである。表４で、行Ｂ、列Ｃの要素は２に変化し、第１のアルゴリズムでネットワークトポロジ３００におけるノードＢからノードＣに到達するのに２ホップであることを示す。表４で、行Ｄ、列Ｃの要素は２に変化し、第１のアルゴリズムでネットワークトポロジ３００におけるノードＤからノードＣに到達するのに２ホップであることを示す。
【００４６】
表３の擬似コードに基づき、表４のマトリックスＭの第１の反復に基づき、ｋ＝２について第１のアルゴリズムに従って最終的なマトリックスＭを計算する第２のステップは、表５に示される。
【表５】
2015204623.tif 000007
［表５］ｋ＝２について第１のアルゴリズムでのマトリックスＭの第２の反復
【００４７】
表５で、ｋ＝２のとき、行Ｂ及び列Ｂは、第１のアルゴリズムの第２の反復において表４と変わらないままである。表５で、行Ｃ、列Ａの要素は２に変化し、第１のアルゴリズムでネットワークトポロジ３００におけるノードＣからノードＡに到達するのに２ホップであることを示す。
【００４８】
表３の擬似コードに基づき、表５のマトリックスＭの第２の反復に基づき、ｋ＝３について第１のアルゴリズムに従って最終的なマトリックスＭを計算する第３のステップは、表６に示される。
【表６】
2015204623.tif 000008
［表６］ｋ＝３について第１のアルゴリズムでのマトリックスＭの第３の反復
【００４９】
表６で、ｋ＝３のとき、行Ｃ及び列Ｃは、第１のアルゴリズムの第３の反復において表５と変わらないままである。表６で、行Ａ、列Ｂの要素は２に変化し、第１のアルゴリズムでネットワークトポロジ３００におけるノードＡからノードＢに到達するのに２ホップであることを示す。表６で、行Ａ、列Ｄの要素は２に変化し、第１のアルゴリズムでネットワークトポロジ３００におけるノードＤからノードＡに到達するのに２ホップであることを示す。表６で、行Ｂ、列Ｄの要素は３に変化し、第１のアルゴリズムでネットワークトポロジ３００におけるノードＢからノードＤに到達するのに３ホップであることを示す。表６で、行Ｄ、列Ｂの要素は３に変化し、第１のアルゴリズムでネットワークトポロジ３００におけるノードＤからノードＢに到達するのに３ホップであることを示す。
【００５０】
表３の擬似コードに基づき、表６のマトリックスＭの第３の反復に基づき、ｋ＝４について第１のアルゴリズムに従って最終的なマトリックスＭを計算する第４のステップは、表７に示される。
【表７】
2015204623.tif 000009
［表７］ｋ＝４について第１のアルゴリズムでのマトリックスＭの第４の反復
【００５１】
表７で、ｋ＝４のとき、行Ｄ及び列Ｄは、第１のアルゴリズムの第４の反復において表６と変わらないままである。表７で、表３の擬似コードに基づき表６からのいかなる変化も生じない。第１のアルゴリズムで上述のように、マトリックスＭは、所与のネットワークトポロジにおける各個々のノ―ド対について個々の全光経路を表す最小ホップ数を示す値を保持する。マトリックスＭ内の各非ゼロ値（又は各非識別値）が１だけ減算されるとき、結果として生じる値は、全ての光経路により個々のノード対の各々に到達するための再生器の数を表し得る。
【００５２】
マトリックスＭが最終的な収束状態で計算されると、マトリックスＭは、所望の到達可能性マトリックスＲＭ＾ｉを生成するために用いることができる。マトリックスＭから到達可能性マトリックスＲＭ＾ａを得るアルゴリズムは、表８Ａに擬似コードとして示される。表８Ａで、要素ｒｍｉｊは、到達可能性マトリックスＲＭ＾ａ内の要素であり、ａは所望のホップ数であり、要素ｍｉｊは、マトリックスＭ内の対応する要素である。表８Ａの例示的なアルゴリズムでは、ＲＭ＾ａの要素は、ホップ数で又はそれより少なく、２ノード間の到達可能性を示すよう定められる。
【表８】
2015204623.tif 000010
［表８Ａ］マトリックスＭからマトリックスＲＭ＾ａを計算するアルゴリズムの擬似コード
【００５３】
表８Ｂには、要素が正にホップ数で到達可能性を示すために定められる、ＲＭ＾ａを得る別の代替アルゴリズムが示される。
【表９】
2015204623.tif 000011
［表８Ｂ］マトリックスＭからマトリックスＲＭ＾ａを計算するアルゴリズムの擬似コード
【００５４】
したがって、マトリックスＭが計算されると、表８Ａ又は８Ｂのアルゴリズムに基づき、メモリ消費を含む比較的少ない計算リソースにより、任意の到達可能性マトリックスＲＭ＾ａが生成され得る。
【００５５】
例えば表６から第１のアルゴリズムでネットワークトポロジ３００について以上で計算されたマトリックスＭを用いたａ＝１についての表８Ａのアルゴリズムの第１の例示的な計算は、表９に与えられる。留意すべきことに、表９の識別値は、表８Ａのアルゴリズムで使用される符号変換により１になっている。
【表１０】
2015204623.tif 000012
［表９］表８Ａの擬似コードを用いて表６のマトリックスＭから計算された到達可能性マトリックスＲＭ＾１
【００５６】
例えば表６から第２のアルゴリズムでネットワークトポロジ３００について以上で計算されたマトリックスＭを用いたａ＝２についての表８Ａのアルゴリズムの第２の例示的な計算は、表１０に与えられる。留意すべきことに、表１０の識別値は、表８Ａのアルゴリズムで使用される符号変換により１になっている。
【表１１】
2015204623.tif 000013
［表１０］表８Ａの擬似コードを用いて表６のマトリックスＭから計算された到達可能性マトリックスＲＭ＾２
【００５７】
ネットワークトポロジ３００について表１のＲＭ＾１から開始して各連続的マトリックスＭ（ａ）を計算する第２のアルゴリズムは、表１１の擬似コードにより示される。第２のアルゴリズムでは、ａの各連続的な値について、Ｍ（ａ）は、到達可能性マトリックスＲＭ＾１によるブール行列乗算を用いて乗算される。
【表１２】
2015204623.tif 000014
［表１１］マトリックスＭを計算するための第２のアルゴリズムの擬似コード
【００５８】
第２のアルゴリズムでは、Ｍの収束が検出されると、第２のアルゴリズムは早期に終了しても良い。第２のアルゴリズムは、ａが増大するにつれＯ（Ｎ＾３）に近づいても良く、各連続的反復において要素を上書きすることによりin−placeに実行されても良い。
【００５９】
開示のように、異なる方法がマトリックスＭを計算するために用いられても良い。
【００６０】
マトリックスＭを計算する第１の実施形態では、各到達可能性マトリックスＲＭ＾ｉは、全てのｉについて、或いは、到達可能性マトリックスが収束するまで（又は自己増殖で変化しなくなるまで）、予め計算されても良い。次に、全てのマトリックスＲＭ＾ｉの中の情報は、マトリックスＭに符号化されても良い。マトリックスＭを計算する第１の実施形態では、全ての個々の到達可能性マトリックスＲＭ＾ｉはメモリ内に共存しても良い。
【００６１】
上述の第１のアルゴリズム又は第２のアルゴリズムを用いてマトリックスＭを計算する第２の実施形態では、初期到達可能性マトリックスＲＭ＾１は開始点として用いられても良い。次に、in−place計算は、推移閉包を計算することにより、最終マトリックスＭを得るために、ＲＭ＾１から開始して連続的マトリックスに対して実行されても良い。最終マトリックスＭは、全ての到達可能性マトリックスＲＭ＾ｉからの情報を有しても良い。マトリックスＭを計算する第２の実施形態では、計算速度及びメモリ消費は削減され、必要な計算リソースを低減できる。
【００６２】
図４を参照すると、本願明細書に開示されるようなメモリ効率の良いマトリックスに基づく光経路計算の例示的な一実施形態を説明するネットワークトポロジ４００の一実施形態の選択された要素のブロック図が示される。図示のように、ネットワークトポロジ４００は、送信元ノードＳ及び宛先ノードＤ、並びに円として示される複数の他のネットワークノードを有する。ネットワークトポロジ４００におけるネットワークノードの位置は、ネットワークノードの相対的な位置を示し、ネットワークトポロジは縮尺通りに示されない。ネットワークトポロジ３００について上述のように、マトリックスＭは、説明の明確さのために図４では省略されているネットワークトポロジ４００におけるノード間の光経路の物理ネットワークトポロジに基づき、ネットワークトポロジ４００について計算されても良い。マトリックスＭは、ネットワークトポロジ４００における任意のノード対を接続するために用いられる再生器の数を決定することを可能にし得る。したがって、マトリックスＭは、ネットワークトポロジ４００における送信元ノードＳと宛先ノードＤとの間の所望の光経路について可能な再生器位置を見付けるために用いられても良い。
【００６３】
初めに、マトリックスＭは、図３に関して上述したように、ネットワークトポロジ４００の到達可能性マトリックスＲＭ＾１及びＲＭ＾２を生成するために用いられても良い。次に、ネットワークトポロジ４００におけるノードの第１のセット４０２は、マトリックスＭから得られた到達可能性マトリックスＲＭ＾１及びＲＭ＾２から識別されても良い。ここで、第１のセット４０２は、宛先ノードＤから１ホップで且つ送信元ノードＳから２ホップで到達可能なノードを含む。次に、ネットワークトポロジ４００におけるノードの第２のセット４０４は、マトリックスＭから得られた到達可能性マトリックスＲＭ＾１及びＲＭ＾２から識別されても良い。ここで、第２のセット４０４は、第１のセット４０２から１ホップで且つ送信元ノードＳから１ホップで到達可能なノードを含む。
【００６４】
第１のセット４０２及び第２のセット４０４が識別された後、送信元ノードＳと宛先ノードＤとの間のエンド−エンド接続は、第２のセット４０４及び第１のセット４０２を用いて識別されても良い。第２のセット４０４は、送信元ノードＳからの可能な第１のホップ位置を表しても良い。一方、第１のセット４０２は、宛先ノードＤからの可能な第１のホップ位置を表しても良い。次に、第２のセット４０４から第１のセット４０２へのの第１のホップ位置が識別されても良い。このように、送信元ノードＳと宛先ノードＤとの間の可能なエンド−エンド接続が識別されても良い。可能なエンド−エンド接続は、所望の接続を選択するために種々の基準を用いて評価され得る送信元ノードＳと宛先ノードＤとの間の種々の可能な接続を表しても良い。留意すべきことに、ノードのセットを選択するための手順の反復数は、送信元ノードＳ及び宛先ノードＤの対について、マトリックスＭの中の値により境界を定められても良い。
【００６５】
図５を参照すると、メモリ効率の良いマトリックスに基づく光経路計算のための方法５００の一実施形態の選択された要素のフローチャートが示される。方法５００は、本願明細書に開示のような例示的な実施形態では、経路計算エンジン２０２によりマトリックスＭを用いた光経路計算のために実施されても良い。留意すべきことに、方法５００で記載される特定の動作は、異なる実施形態では任意であっても良く或いは再配置されても良い。
【００６６】
方法５００は、光ネットワークにおける各ノード対について到達可能性マトリックスＲＭ＾１を計算することにより開始しても良い（動作５０２）。到達可能性マトリックスＲＭ＾１に基づき、各ノード対について、in−placeアルゴリズムを用いてマトリックスＭにおける個々のノード対の間の全ての光経路の最小数を計算する（動作５０４）。動作５０４は、マトリックスＭの連続的反復について反復的in−place計算を実行するために、推移閉包アルゴリズムを適用するステップを有しても良い。一方、反復的in−place計算は、光ネットワーク内のノード数に対応する最大反復数の間、実行されても良い。動作５０４は、図３に関して上述した第１のアルゴリズム又は第２のアルゴリズムを用いて実行されても良い。マトリックスＭの中の各ノード対の間の全光経路の最小数に基づき、各ノード対の再生器の最小数が決定される（動作５０６）。動作５０６で決定された再生器の最小数は、マトリックスＭの非ゼロ値について、マトリックスＭ内の個々の値から１を減算したものであっても良い。送信元−宛先の対は、１より大きいマトリックスＭ内の値を有し選択されても良い（動作５０８）。送信元ノードと宛先ノードとの間の可能な光経路が決定され（動作５１０）、可能な光経路は、送信元−宛先の対についての再生器の最小数を有する。送信元ノードと宛先ノードとの間の可能な光経路は、所望の光経路を選択するために評価されても良い（動作５１２）。
【００６７】
図６を参照すると、メモリ効率の良いマトリックスに基づく光経路計算のための方法６００の一実施形態の選択された要素のフローチャートが示される。方法６００は、本願明細書に開示のような例示的な実施形態では、経路計算エンジン２０２によるマトリックスＭを用いた光経路計算のために実施されても良い。方法６００は、図５の方法５００における動作５１０の一実施形態を表し得る。留意すべきことに、方法６００で記載される特定の動作は、異なる実施形態では任意であっても良く或いは再配置されても良い。
【００６８】
方法６００は、方法５００の動作５０８の後に、ＧをマトリックスＭの中の送信元−宛先の対の再生器の最小数とし（動作６０２）、Ｈ＝１とする（動作６０２）ことにより、始まっても良い。次に、方法６００は、動作６０４、６０６及び６０８で反復手順を実行しても良い。ここで、「ノードの次のセット」への参照は、反復手順におけるノードのセットの反復的インスタンスを指定するために用いられる。光ネットワーク内のノードの次のセットが決定される（動作６０４）。ノードの次のセットは、宛先ノードからＨホップを用いて、及び送信元ノードからＧホップを用いて、到達可能である。次に、Ｇはデクリメントされても良く（動作６０６）、Ｈはインクリメントされても良い（動作６０８）。次に、Ｇ＝０か否かの決定が行われても良い（動作６０８）。Ｇ≠０のとき、動作６０８の結果はＮＯであり、方法６００は動作６０４にループバックしても良い。Ｇ＝０のとき、動作６０８の結果はＹＥＳであり、ノードのセットに基づき、送信元ノードと宛先ノードとの間の可能な光経路が生成されても良い（動作６１０）。可能な光経路は、送信元−宛先の対のための最小数の再生器を含む。動作６１０の後、方法６００は、方法５００の動作５１２へ進んでも良い。
【００６９】
上述のように、到達可能性マトリックスを用いた行列演算に基づき光経路計算を実行するとき、光経路の望ましさ又は経済的実現性を評価するために例えば経路計算エンジン２０２により消費されるメモリ量は、このような計算を実行する際の制約因子であり得る。光経路は、図４に関して上述したように、再生器位置の最適解を決定するために評価されても良い。したがって、マトリックスＭのin−place計算について上述した方法は、Ｎを数千個のノードのような比較的大きな値としてＮ個のノードを有する大規模ネットワークでも、光経路計算を実行する計算上の扱いやすさを実現できる。図３〜６に関して上述のように、可能な光経路は、再生器段の階層的編成を表しても良い、図４の第１のセット４０２及び第２のセット４０４と共に識別された可能な再生器位置と一緒に、識別されても良い。
【００７０】
以下に更に詳細に記載するように、識別された可能な光経路及び再生器段に基づき、可能な光経路から特定の光経路を選択するために階層的誘導検索が実行されても良い。階層的誘導検索は、ノード同士を接続する光経路グループ（optical  path  group：ＯＰＧ）と共に送信元ノードと宛先ノードとの間の識別された再生器段を含む階層的誘導検索（hierarchical  guided  search：ＨＧＳ）グラフを利用しても良い。記載されるように、階層的誘導検索は、可能な再生器位置情報、並びにノード間の光経路の最小コスト情報を利用しても良い。
【００７１】
光経路グループは、所与のノード対の間の単一方向の１又は複数の全光経路（all−optical  path：ＯＰ）を集合的に表しても良い。したがって、マトリックスＭ内の各マトリックス要素は、単一の光経路グループを表しても良い。Ｍのマトリックス要素がゼロに等しい場合、対応する光経路グループは、光経路の空集合を表す。光経路は、それぞれ、物理光リンクの種々の系列、及び光ノードを有しても良い。ネットワークを通じる光経路が辿る特定のルートは異なっても良い。あるレベルの冗長性を用いたネットワーク保護が望ましい幾つかのアプリケーションでは、特定のレベルの分離性（disjointness）を特色とする光経路の対（又は、より一般的には、ｎ重の光経路若しくはエンド−エンド接続）が用いられても良い。本願明細書で用いられるように、「分離性（disjointness）」は、ネットワーク内の特定の光リソースへの排他的アクセスを有する（又は特定の光リソースを共有しない）ことを表す。例えば、光経路グループ内で、ノード分離（node−disjoint）光経路は、送信元及び宛先ノードを除いて、異なる光ノードのみを通過しても良い（又はいかなる共有ノードも通過しなくても良い）。リンク分離（Link−disjoint）光経路は、異なる光リンクのみを通過しても良い（又は、いかなる共有光リンクも通過しなくても良い）。特定の分離光経路は、ノード分離及びリンク分離の両方として定められても良い。
【００７２】
ノード分離である２つのエンド−エンド接続では、経路計算において関心のある主要な特徴は、エンド−エンド接続の送信元及び宛先ノードが供給され得る場合でも、いかなる再生器ノードも共有しないエンド−エンド接続を有しても良い。経路計算において関心のある第２の特徴は、エンド−エンド接続に含まれる光経路の各々がノード分離でもあることであっても良い。リンク分離である２つのエンド−エンド接続では、各接続における光経路セットは、相互にリンク分離である。
【００７３】
異なる送信元及び宛先ノードを有する光経路グループはノード分離又はリンク分離である可能性がより高いが、分離性は、異なる送信元又は宛先ノードにより保証されなくても良い。したがって、ノード分離又はリンク分離であるエンド−エンド接続の十分な条件ではなく、エンド−エンド接続の再生器ノード分離性が要求され得る。留意すべきことに、種々の実施形態では、他の種類の分離性が定められ、共通ルートを供給しないリンクのような光経路計算における制約として用いられても良い。
【００７４】
次に、階層的誘導検索は、階層的誘導検索（ＨＧＳ）状態ツリーを用いて進められる。ＨＧＳ状態ツリーは、階層的選択を可能にし得る。階層的選択では、可能な再生器ノードが識別された後に、同じ送信元及び宛先ノードを有する複数の光経路を含む光経路グループは、評価され、最小コスト情報に基づき選択されても良い。光経路グループが各分離経路について選択されると、各光経路グループ内からの光経路が選択されても良い。この処理中、可能な解の削除は、検索処理において検索空間を早期に縮小することにより、計算上の扱いやすさを更に向上し得る。例えば、特定の光経路又は光経路グループが分離していないと発見されると直ぐに、このような可能な選択肢は解空間から削除されても良い。特定の実施形態では、Ａ＊アルゴリズムは、可能な光経路を検索又は評価するために用いられても良い。
【００７５】
上述のように、分離性は、可能な又は利用可能な光経路からの特定の光経路の選択において用いられるポリシ制約の一例を表し得る。接続の待ち時間、距離、及び電力消費は、コストメトリックとしても言及される経済的制約の例である。経済的制約は、コスト関数を用いた検索中に、評価され最小化され施行されても良い。ポリシ制約は、特定の可能な解の削除により施行されても良い。
【００７６】
図７Ａを参照すると、ＨＧＳグラフ７００の一実施形態の選択された要素が示される。特定の実施形態では、ＨＧＳグラフ７００は、図４に示すネットワークトポロジ４００の一実施形態を表しても良い。留意すべきことに、ＨＧＳグラフ７００は、説明目的で示される例示的な実施形態であり、ＨＧＳグラフの他の実施形態は、より少ない又は多い要素及び情報を有しても良い。
【００７７】
図７Ａで、ＨＧＳグラフ７００は、送信元ノードＳと宛先ノードＤとの間の光経路グループ７０４を示す。光経路グループ７０４は、中間ノードＢ及びＣを有する再生器段１（ＲＳ１）、並びに中間ノードＦ及びＧを有する再生器段２（ＲＳ２）、に関して階層的に配置される。例えば、ＲＳ１は図４の第２のセット４０４に対応しても良く、一方、ＲＳ２は図４の第１のセット４０２に対応しても良い。ＨＧＳグラフ７００内の各光経路グループ７０４は、光経路の数及び各光経路のコストメトリックを示す光経路情報を注釈される。本願明細書で用いられるように、コストメトリックは、待ち時間、距離、ハードウェアコスト、電力消費、所望の最小帯域幅からの超過帯域幅、超過光ペナルティ許容範囲、又はそれらの異なる組合せのような経済的制約を示しても良い。コストメトリックは、本願明細書で、説明の明確さを目的として、光経路同士の相対的コストの整数メトリックとして用いられる。留意すべきことに、異なる実施形態では、実際の金銭的コストを示す実数値のようなより精細なコストメトリックが用いられても良い。具体的には、光経路グループ７０４−１は、それぞれコストメトリック２及び３を有する送信元ノードＳとノードＢとの間の２つの全光経路を有する。光経路グループ７０４−２は、それぞれコストメトリック３、５及び６を有する送信元ノードＳとノードＣとの間の３つの全光経路を有する。光経路グループ７０４−３は、それぞれコストメトリック２及び４を有するノードＢとノードＦとの間の２つの全光経路を有する。光経路グループ７０４−４は、それぞれコストメトリック１を有する送信元ノードＢとノードＧとの間の１つの全光経路を有する。光経路グループ７０４−６は、それぞれコストメトリック４及び７を有するノードＦと宛先ノードＤとの間の２つの全光経路を有する。光経路グループ７０４−７は、それぞれコストメトリック２及び９を有するノードＧと宛先ノードＤとの間の２つの全光経路を有する。−ＨＧＳグラフ７００内のコストメトリック情報に基づき、各ノードから宛先ノードＤへの最小コストメトリックは、表１２に与えられ、図７Ａの各個々のノードの隣の菱形の中に示される。ここで、宛先ノードＤ自体は省略されている。
【表１３】
2015204623.tif 000015
［表１２］ＨＧＳグラフ７００の宛先ノードＤへの最小コストメトリック
【００７８】
図７Ｂを参照すると、ＨＧＳグラフ状態ツリー７０１の一実施形態の選択された要素が示される。所与の実施形態では、ＨＧＳ状態ツリー７０１は、図７Ａに示されるＨＧＳグラフ７００に基づいても良い。留意すべきことに、ＨＧＳ状態ツリー７０１は、説明目的で示される例示的な実施形態であり、ＨＧＳ状態ツリーの他の実施形態は、より少ない又は多い要素及び情報を有しても良い。
【００７９】
ＨＧＳ状態ツリー７０１では、階層的検索及び決定処理は、ＨＧＳグラフ７００に基づき、送信元ノードＳから宛先ノードＤへの最低コスト光経路を決定する。したがって、ＨＧＳ状態ツリー７０１の葉は光経路グループ７０４を表し、一方、ＨＧＳ状態ツリー７０１の線は連続的光経路グループ７０４の選択を表す。ここで、実線は選択された光経路グループを示し、破線は選択されていない光経路グループを示す。
【００８０】
ＨＧＳ状態ツリー７０１では、送信元ノードＳから開始して、第１の決定は、ノードＢへの光経路グループ７０４−１又はノードＣへの光経路グループ７０４−２を利用可能なコストメトリック情報に基づき選択するために行われても良い。ノードＢ及びＣの両方からの残りのコストメトリック（表１２も参照）は３であり、送信元ノードＳから宛先ノードＤまでの全体的な最低コスト見積もりは５である。したがって、送信元ノードＳから、第１の決定は、ＲＳ１への最低コストの全光経路を選択するために行われても良い。ＨＧＳグラフ７００から明らかなように、光経路グループ７０４−１は、コストメトリック２及び３を有する光経路を有し、一方、光経路グループ７０４−２は、コストメトリック３、５、６を有する光経路を有する。したがって、光経路グループ７０４−１からのＯＰ（２）は、第１の決定でＲＳ１に選択される。第１の決定の結果として、光経路グループ７０４−２は選択されず、光経路グループ７０４−５も第１の決定で削除される。
【００８１】
次に、光経路グループ７０４−１  ＯＰ（２）から、ＨＧＳ状態ツリー７０１において、ノードＢから、ノードＦへの光経路グループ７０４−３の中から選択するために、又はノードＧへの光経路グループ７０４−４を選択するために、第２の決定が行われても良い。ノードＦからの残りのコストメトリックは４であり、ノードＧからの残りのコストメトリックは２であり、ノードＧが好ましい。さらに、光経路グループ７０４−４の中で、ＲＳ２における最低コスト光経路はＯＰ（１）であり、ノードＧが好ましい。したがって、ノードＢから、第２の決定が行われて、ＲＳ２への最低コストの全光経路を選択しても良く、光経路グループ７０４−４からＯＰ（１）がＲＳ１への第１の決定で選択される。第２の決定の結果として、光経路グループ７０４−３は選択されず、光経路グループ７０４−６も第２の決定で削除される。
【００８２】
最後に、第３の決定が行われて、ノードＧから宛先ノードＤまでの光経路グループ７０４−７を選択する。ここで、ＯＰ（２）が最低コストの全光経路として選択される。したがって、ノードＢから、第２の決定が行われて、ＲＳ２への最低コストの全光経路を選択し、光経路グループ７０４−４からＯＰ（１）がＲＳ２への第３の決定で選択される。第３の決定は、送信元ノードＳから宛先ノードＤまでの全体コストメトリック５をもたらす。これは、最低コストメトリックの光経路が選択されることを裏付ける。
【００８３】
ＨＧＳ状態ツリー７０１を用いる決定のための上述の手順は、説明の明確さのために提示され、単一の最低コストメトリック光経路を得るためにＨＧＳグラフ７００内の情報がどのように利用されるかを示した。これは、光経路間の分離性の問題を導入しない。送信元ノードＳと宛先ノードＤとの間の追加光経路が望ましいとき、上述の手順は、前に選択された光経路及び前に選択された再生器ノードを削除して、追加光経路を得るために繰り返されても良い。留意すべきことに、ノードの削除は一時的、例えば、ＨＧＳグラフ７００内の情報を処理する所与の反復の間、であっても良く、前に削除されたノードは後の試みで再検討されても良い。
【００８４】
しかしながら、ＨＧＳ状態ツリー７０１を用いるとき、光経路又は光経路グループを選択するときに分離光経路の検討が導入されても良い。上述のように、異なる光経路グループ内の光経路は、物理ネットワークトポロジのために完全に分離していなくても良い。特に、送信元ノードＳと宛先ノードＤとの間のＮタプル分離光経路のような複数の光経路を選択するとき、ＨＧＳ状態ツリー７０１のＯＰＧ葉の切り落としは、全ての光経路が選択された後に分離性が評価される従来のアプローチと比べて、階層的誘導検索の効率を向上するために効果的なメカニズムであり得る。Ｎタプル分離光経路は、種々の実装の光ネットワークの現実世界の提供において望ましい。例えば、高度なネットワーク可用性又は信頼性が望ましいとき、２タプル分離である運用経路及び保護経路が望ましい。
【００８５】
ＨＧＳ状態ツリー７０１では、各葉で連続的光経路の間で及び宛先ノードへの残りのコストメトリックに基づき選択するとき、分離性が検討されても良い。このように、分離性の評価は、所与の時間において検討される限られた数の光経路により、より効率的にされる。２つの光経路が非分離であると分かると、コストメトリックに基づく選択は、分離である可能性のある残りの光経路の中で行われても良い。特定の実施形態では、最大分離度のような追加基準は、例えば、ＨＧＳ検索ツリー７０１を用いる手順に適用されても良い。この方法では、ＨＧＳグラフ７００及びＨＧＳ状態ツリー７０１を用いる階層的誘導検索は、Ｎタプル分離光経路の所望の分離度について、最低コスト光経路を得ても良い。
【００８６】
図８を参照すると、階層的誘導検索を用いた光経路評価のための方法８００の一実施形態の選択された要素のフローチャートが示される。方法８００は、本願明細書に開示のような例示的な実施形態では、経路計算エンジン２０２による光経路計算のために実施されても良い。特定の実施形態では、方法８００は、方法５００の動作５１２（図５を参照）の一実施形態であっても良い。方法８００は、種々の実施形態ではＨＧＳグラフ７００（図７を参照）を用いて実行されても良い。留意すべきことに、方法８００で記載される特定の動作は、異なる実施形態では任意であっても良く或いは再配置されても良い。
【００８７】
方法８００は、マトリックスＭに基づき、全光経路のセット及び送信元ノードと宛先ノードとの間の再生器段に従ってグループ化される関連ノードを生成するステップ（動作８０２）により開始しても良い。次に、経路計算情報は、全光経路のセットについて生成されても良い（動作８０４）。経路計算情報は、各光経路毎のコストメトリックであっても良い。経路計算情報に基づき、ノードコスト情報は、各ノードについて宛先ノードまで計算されても良い（動作８０６）。ノードコスト情報は、宛先ノードまでの各ノードの最小コストメトリックを有しても良い。次に、ＨＧＳグラフが生成されても良い（動作８０８）。ＨＧＳグラフは、全光経路のセット、共通ノード間の光経路を有する光経路グループ、経路コスト情報、及びノードコスト情報に関連付けられるノードを有しても良い。特定の例では、光経路は、Ｎタプル分離であっても良い。ＨＧＳグラフに基づき、最低コスト光経路は、送信元ノードと宛先ノードとの間で決定されても良い（動作８１０）。ＨＧＳ状態ツリーは、処理の検索空間を最小化するために処理の早い段階で未選択ノード及び光経路を検討から取り除く処理で、最低コスト光経路を選択するために用いられても良い。複数の最低コスト光経路が決定されても良い。複数の最低コスト光経路のうちの少なくとも幾つかは、分離光経路であっても良い。
【００８８】
本願明細書に開示のように、ノード対の間の最小数の全光経路を示すマトリックスＭは、一実施形態では推移閉包のためのアルゴリズムを用いて生成されても良い。種々の実施形態で、異なるアルゴリズム及び方法がマトリックスＭを生成するために用いられても良い。推移閉包に達する収束マトリックスＭが生成されると、任意の値ａについて任意の対応する到達可能性マトリックスＲＭ＾ａが、計算上効率的な方法でマトリックスＭから得られても良い。マトリックスＭは、可能な再生器配置のグループを決定するために、及び再生器の所望の系列を選択することによりエンド−エンド光経路を得るために用いられても良い。
【００８９】
本願明細書に開示のように、マトリックスＭは、可能な再生器配置のグループを決定するために、及び再生器の所望の系列を選択することにより可能なエンド−エンド光経路を得るために用いられる。次に、階層的誘導検索は、可能な光経路から所望のＮタプル分離光経路を効率的に選択するために用いられても良い。階層的誘導検索は、検索を誘導するために並びに候補ノード及び光経路を検索処理の早い段階で削除するために、検索グラフ及び検索ツリーを用いても良い。
【００９０】
以上に開示した主題は、説明のためであり、限定ではないと考えられるべきである。また、添付の特許請求の範囲は、本開示の真の精神及び範囲に包含される全ての変更、拡張及び他の実施形態を包含することを意図している。したがって、法により認められる最大範囲まで、本開示の範囲は、特許請求の範囲及びその等価物の最も広い許容可能な解釈により決定されるべきであり、前述の詳細な説明により限定又は制限されるべきではない。
【００９１】
［関連出願の参照］
本出願は、米国仮出願番号第６１／９７８，０１６号、２０１４年４月１０日出願、名称「MEMORY−EFFICIENT  MATRIX−BASED  OPTICAL  PATH  COMPUTATION」の優先権を主張する。本出願は、米国仮出願番号第６１／９７７，９９９号、２０１４年４月１０日出願、名称「N−TUPLE  DISJOINT  OPTICAL  PATH  COMPUTATION」の優先権を主張する。
【符号の説明】
【００９２】
２００  制御システム
２０２  経路計算エンジン
２０４  データベース
２０６  シグナリングモジュール
２０８  プロセッサ
２１０  ルーティングモジュール
２１２  発見モジュール
２１４  ネットワークインタフェース
２２０  記憶媒体
２３０  ネットワーク
【図１】
2015204623.tif 000016
【図２】
2015204623.tif 000017
【図３】
2015204623.tif 000018
【図４】
2015204623.tif 000019
【図５】
2015204623.tif 000020
【図６】
2015204623.tif 000021
【図７Ａ】
2015204623.tif 000022
【図７Ｂ】
2015204623.tif 000023
【図８】
2015204623.tif 000024