(57)【要約】【課題】  光ネットワークの中の最短最少再生経路を決定するための方法及びシステムが提供される。【解決手段】  当該方法は、送信元ノードにおいて仮想ノードを生成するステップであって、前記送信元ノードは、複数のノード及びリンクを通じて宛先ノードに通信可能に結合される、ステップを有する。当該方法は、前記仮想ノードをトラバースするステップを有する。前記仮想ノードをトラバースするステップは、ノードにおける未訪問仮想ノードを選択するステップと、前記未訪問仮想ノードから候補仮想ノードを識別するステップと、前記候補仮想ノードが最大許容重みを超えるか否かを決定するステップと、前記候補仮想ノードが最短最少再生経路条件に違反するか否かを決定するステップと、前記候補仮想ノードが前記最大許容重みを超えない場合、及び前記候補仮想ノードが前記最短最少再生経路条件に違反しない場合、前記候補仮想ノードから前記新しい仮想ノードを生成するステップと、を含む。【選択図】  図４
2017216686.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：ＡＳＥ）のような送信劣化因子が、光信号送信経路内で光信号にどれ位影響を与え得るかについての見識を提供して良い。光信号送信経路の送信特性を決定するために、経路計算エンジン２０２は、送信劣化因子の間の相互作用を検討して良い。種々の実施形態では、経路計算エンジン２０２は、特定の送信劣化因子の値を生成して良い。経路計算エンジン２０２は、光信号送信経路を記述するデータをデータベース２０４に更に格納して良い。
【００２６】
図２で、シグナリングモジュール２０６は、図１のネットワーク１００又は図３のネットワーク３００のような光ネットワークにおいてエンド−エンドネットワークサービスの設定、変更、及び取り壊しに関連する機能を提供して良い。例えば、ネットワーク内のイングレスノードがサービス要求を受信すると、制御システム２００は、シグナリングモジュール２０６を用いて、帯域幅、コスト、等のような異なる基準に従って最適化され得る経路計算エンジン２０２からのネットワーク経路を要求して良い。所望のネットワーク経路が識別されると、次に、シグナリングモジュール２０６は、要求されたネットワークサービスを確立するために、ネットワーク経路に沿って個々のノードと通信して良い。異なる実施形態では、シグナリングモジュール２０６は、ネットワーク経路に沿ってノードへ及びノードから後続の通信を伝搬するために、シグナリングプロトコルを用いて良い。
【００２７】
制御システム２００の動作では、光経路計算の特徴は、エンド−エンドの到達可能経路の計算を有して良い。直接到達可能経路は、送信元ノードと宛先ノードとの間で光信号が再生しないで送信できる、ネットワークにおける送信元ノードと宛先ノードとの間の経路を表して良い。これに対し、送信元ノードと宛先ノードとの間の間接到達可能経路は、宛先に到達する前に光−電気−光（Ｏ−Ｅ−Ｏ）、全部光、又は他の適切な再生器を用いる光信号の再生を含んで良い。再生は、再生の可能なネットワークノードにより実行されて良い。信号経路の中で必要な再生数は、信号強度、送信距離、経路の中のネットワークノード、物理リンク、及び／又はそれらの組み合わせに依存して良い。
【００２８】
経路計算エンジン２０２は、最短エンドツーエンド到達可能経路を決定して良い。例えば、経路計算エンジン２０２は、ネットワークノード間の最小結合重みを有する送信元ノードから宛先ノードへの経路を選択して良い。ネットワークノードを結合する各々の物理リンクは、距離、コスト、遅延、雑音、送信特性、及び／又はそれらの組合せを含む１又は複数の因子を表す重みを有して良い。経路計算エンジン２０２は、任意の２つのノード間の最短経路を決定するために、最短経路アルゴリズムを使用して良い。最短経路アルゴリズムの例は、ダイクストラ（Dijkstra）のアルゴリズム、ベルマン−フォード（Bellman−Ford）アルゴリズム、ガボウ（Gabow）のアルゴリズム、及びThorupのアルゴリズムを含むが、これらに限定されない。
【００２９】
しかしながら、上述のように、経路が配置される光経路又はネットワークの性能に影響を与える物理リンクの重み以外の因子が存在し得る。例えば、各々の経路は、宛先ノードに到達するまでに、多数のネットワークノード、多数の特定種類のノード、又は多数の特定種類の物理リンクをトラバースし得る。これらの因子のうちの１又は複数は、光信号再生が信号経路の中でいつ実行されるか及び実行されるか否かに貢献して良い。光信号再生は、信号品質、コスト、ネットワークリソース、又は光経路若しくはネットワークの他の側面に影響を与え得る。したがって、本願明細書において最短最少再生経路として参照される、最も少ない再生を伴う最短経路を選択することが望ましい場合がある。経路計算エンジン２０２は、送信元と宛先ノードとの間の最短経路を計算する際に、光再生を考慮して良い。
【００３０】
図３Ａ〜３Ｑは、最短最少再生経路計算の種々のステージにおける、光ネットワークの一実施形態の選択された要素のブロック図である。
【００３１】
図示のように、ネットワーク３００は、集合的にノード３０２として参照されるノード３０２−１〜３０２−７を含む。動作中、特定ノード３０２は、適切な波長で物理リンク３０４上を伝搬する光信号により、光ネットワーク３００の他のノード３０２及び他のコンポーネントとメッセージを通信して良い。光信号は、例えば変調又は多重化を含む図１に関連して上述した技術のうちの任意のものを使用し又は含んで良い。ノード３０２は、物理リンク３０４を用いて、データ（例えば、ファイル又はウェブページ）及びシグナリング（例えば、制御メッセージ、ルーティングメッセージ、及びリンク管理メッセージ）の両方を通信して良い。データ及びシグナリングは、メッセージ又はトラフィックとして集合的に参照されて良い。
【００３２】
ノード３０２は、メッセージを送信及び受信するよう動作する任意の適切なシステムを有して良い。例えば、ノード３０２は、ＯＡＤＭ、クロスコネクト、再生ユニット、アクセスゲートウェイ、エンドポイント、ソフトスイッチサーバ、トランクゲートウェイ、アクセスサービスプロバイダ、インターネットサービスプロバイダ、ハブ、ルータ、スイッチ、ブリッジ、又はネットワーク３００へ、それから、又はその中でデータをルーティングするよう動作する任意の他の装置を含んで良い。
【００３３】
物理リンク３０４は、ノード３０２間の通信をトランスポートする任意の適切な媒体を有して良い。例えば、物理リンク３０４は、図１の伝送媒体１２に関して上述したような光ファイバを有して良い。
【００３４】
ノード３０２−１がノード３０２−７にメッセージを送信する必要があるとする。このようなシナリオでは、この特定の送信について、ノード３０２−１は送信元ノードであり、ノード３０２−７は宛先ノードである。図３の例示的なネットワークトポロジにより示されるように、送信元ノードから宛先ノードへメッセージをルーティングするために、１より多くの経路が使用されて良い。可能な経路は、ノード３０２−１→３０２−２→３０２−３→３０２−７の間、ノード３０２−１→３０２−２→３０２−４→３０２−３→３０２−７の間、ノード３０２−１→３０２−２→３０２−４→３０２−６→３０２−７の間、ノード３０２−１→３０２−５→３０２−６→３０２−７の間、ノード３０２−１→３０２−５→３０２−４→３０２−６→３０２−７の間、ノード３０２−１→３０２−５→３０２−４→３０２−３→３０２−７の間、を含む。
【００３５】
ノード３０２−１からノード３０２−７までの適切な経路を選択するために、ネットワーク３００は、経路識別及び／又は選択のためにシステムを含み又はシステムに通信可能に結合して良い。例えば、ネットワーク３００は、図２に関して上述したものと同様に、制御システムを有して良い。制御システムは、発見モジュール、ルーティングモジュール、シグナリングモジュール、及び／又は経路計算エンジンを用いて、ネットワーク３００の種々のノード３０２の間のエンドツーエンド経路を分析し及び選択して良い。
【００３６】
経路を選択する際の１つの検討事項は、ノード３０２を結合する物理リンクに関連付けられる重みであって良い。ネットワーク３００では、各々の物理リンク３０４は割り当てられた重みを有する。重みは、特定リンクについての、距離、遅延、雑音、及び／又はそれらの組み合わせを表して良い。例えば、ノード３０２−１及び３０２−２を結合するリンクは重み４を有し、ノード３０２−２を３０２−３に結合するリンクは重み６を有し、ノード３０２−３を３０２−４に結合するリンクは重み３を有し、ノード３０２−３を３０２−７に結合するリンクは重み４を有し、ノード３０２−１を３０２−５に結合するリンクは重み４を有し、ノード３０２−５を３０２−６に結合するリンクは重み３を有し、ノード３０２−５を３０２−４に結合するリンクは重み３を有し、ノード３０２−４を３０２−６に結合するリンクは重み２を有し、ノード３０２−６を３０２−７に結合するリンクは重み４を有する。
【００３７】
ネットワーク３００は、ネットワーク３００の中の物理リンク３０４の重みを用いてノード３０２間の最短経路を識別するために、上述の列挙されたものを含む最短経路アルゴリズムを使用して良い。最短経路は、経路の中の物理リンク３０４の最小結合重みを有する経路を表して良い。例えば、送信元ノード３０２−１から宛先ノード３０２−７までの最短経路は、ノード３０２−１→３０２−５→３０２−６→３０２−７（最短経路３１０により示される）の間であって良く、結合重み１１（例えば、４＋３＋４）を表す。
【００３８】
光信号がネットワーク３００の中を伝搬するとき、信号は、減衰、雑音累積、及び／又は歪みのために劣化し得る。劣化した信号は、信号対雑音比を低下し得る。信号品質及びネットワークの信頼性を維持するために、ネットワークは、光信号が再生される前に該光信号が伝搬して良い最大許容重みを有して良い。信号が再生の前に伝搬して良い最大許容重みは、ネットワーク内の要素、環境がネットワークに及ぼす影響、ネットワーク利用率、及び／又はネットワークの他の特性により影響され得る。
【００３９】
ネットワーク３００は、光信号の伝搬距離を拡張するために再生を使用して良い。例えば、１又は複数のノード３０２は、光信号を再生するためにハードウェア及び／又はソフトウェアを有して良く、遅延及び／又は劣化を低減して、信号がその宛先へ向かって伝搬し続けることができるようにする。信号再生は、信号の強度及び伝搬距離を増大するために、光−電気−光又は別の形式の再生を必要として良い。信号再生は光信号の伝搬距離を延長し得るが、再生は、光信号経路の中の遅延、リソース、信号品質及び／又はコストに悪影響を与え得る。したがって、最も少ない再生を伴う最短経路を表す、ネットワークの中の最短最少再生経路を選択し使用することが望ましい場合がある。
【００４０】
単に一例として、ネットワーク３００の中の光信号は、再生を必要とする前に、最大許容重み６まで、１又は複数の物理リンク３０４を伝搬して良い。つまり、光信号は、信号により伝搬される物理リンク３０４の結合重みが最大許容重みを超えると、再生を必要とし得る。ノード３０２−１→３０２−５→３０２−６からの伝搬が、最大許容重み６を超える結合重み７（例えば４＋３）を有するリンクを通過するので、最短経路３１０（例えば、ノード３０２−１→３０２−５→３０２−６→３０２−７の間の経路）を伝搬する信号は、１回目はノード３０２−５において、２回の再生を必要とし得る。信号はノード３０２−５において再生されると仮定すると、ノード３０２−５→３０２−６→３０２−７の間の伝搬は、最大許容重みを超える結合重み７（例えば３＋４）を有するリンクを通過するので、信号はノ―ド３０２−６において再び再生を必要とし得る。したがって、最短経路３１０は、送信元ノード３０２−１と宛先ノード３０２−７との間の最短経路を表し得るが、最短経路３１０を伝搬する信号は、２回の再生を必要とし得る。
【００４１】
ネットワーク３００は、最短最少再生経路を識別するよう最短経路計算において再生を考慮するために、１又は複数の仮想ノードを用いて良い。図３Ｂは、仮想ノードを有する光ネットワーク３００の一実施形態の選択された要素のブロック図である。１又は複数の仮想ノード３０６が各々のノード３０２に追加されて良い。仮想ノードは、ネットワーク３００の中の候補経路に対応して良い。仮想ノード３０６が物理リンクを用いてトラバースされるとき、更なる仮想ノード３０６がネットワーク３００に追加されて良い。最短経路アルゴリズムは、最も少ない再生を有する最短経路を計算するために、仮想ノードをトラバースして良い。
【００４２】
仮想ノード３０６は、ネットワークの中の別の仮想ノード３０６にリンクして良い。最短経路の計算において、２つの仮想ノードの間に形成される任意の仮想リンクは、対応するノード３０２を結合する特定の物理リンク３０４と等価な重みを有する。例えば、ノード３０２−１の仮想ノードとノード３０２−２の仮想ノードとの間の仮想リンクは、これらの２つのノードを結合する物理リンク３０４と同じ重み（つまり、４）を有する。各々の仮想ノード３０６は、最短再生経路計算に関連する値を有して良い。例えば、仮想ノード３０６は、仮想ノードへの経路の中の物理リンク３０４の結合重みを表す距離値（図３Ｂ〜３Ｑの「ｄ」）を有して良い。仮想ノード３０６は、仮想ノードへの経路の中の再生数を表す再生値（図３Ｂ〜３Ｑの「ｒ」）も有して良い。仮想ノード３０６は、最終再生から仮想ノードまでの物理リンク３０４の結合重みを表す最終再生以来距離値（図３Ｂ〜３Ｑの「ｄｒ」）も有して良い。
【００４３】
最短再生経路計算の間に仮想ノード３０６がトラバースされるとき、更なる仮想ノードが追加されて良い。例えば、仮想ノードは、現在のノード３０２に追加されて良い。現在のノード３０２にある新しい仮想ノード３０６は、特定ノード３０２における再生の実行を表して良い。仮想ノードは、１又は複数の近隣ノード３０２においても追加されて良い。仮想ノード３０６（既存の及び追加の仮想ノード３０６の両方）は、全ての仮想ノード３０６が訪問されるまで、トラバースされて良い。幾つかの候補仮想ノードは、候補仮想ノードへの信号が最大許容重み（例えば、最終再生以来の結合重み６以下）に違反し得るとき、ブロックされて良い。
【００４４】
最短再生経路計算の間の仮想ノード３０６の追加は、経路計算時間を増大し得る。したがって、最短最少再生経路に対応しない候補仮想ノードを識別するために、条件が適用されて良い。例えば、条件Ａは、距離値が同じノード３０２における既存の仮想ノードより大きい又は等しい、候補仮想ノードについての最終再生以来距離が同じノード３０２における既存の仮想ノードの距離より大きい、及び両方のノードの再生値が同じであるときを表して良い。条件Ｂは、候補仮想ノードの距離値及び再生値が同じノード３０２における既存の仮想ノードのものより共に大きいときを表して良い。条件Ｃは、同じノード３０２における既存の仮想ノードのものより、候補仮想ノードの再生値が大きい及び最終再生以来距離値が大きい又は等しいときを表して良い。条件Ｄは、候補仮想ノードの再生値が同じノード３０２における既存の仮想ノードの再生値＋１より大きいときを表して良い。条件Ａ〜Ｄのうちの任意のものが検出されるならば、候補仮想ノードは、より短い再生経路に対応しないので、ブロックされて良い（例えば、無視される又は生成されない）。
【００４５】
仮想ノードを用いて最短最少再生経路を計算するステップは、図３Ｂ〜３Ｑに示される。始めに図３Ｂで、仮想ノード３０５−１は送信元ノード３０２−１において生成される。送信元ノード３０２−１からの物理リンク３０４の結合重みを表す、仮想ノード３０６−１の距離値は、物理リンク３０４がトラバースされていないので、０に設定される。経路の中の再生数を表す再生値は、送信元ノード３０２−１から再生が生じていないので、０に設定される。信号が送信元ノード３０２−１において生成されてから物理リンク３０４がトラバースされていないので、再生以来距離値も０に設定される。
【００４６】
経路計算は、仮想ノード３０６−１、つまり送信元ノード３０２−１に対応する仮想ノードで開始して良い。図３Ｂでは、新しい仮想ノードが生成される前に、仮想ノード３０６−１からの候補仮想ノードが検討される。例えば、仮想ノード３０６−１からの候補仮想ノードは、ノード３０２−１及び近隣ノード３０２−２及び３０２−５における仮想ノードを含む。送信元ノード３０２−１における候補仮想ノードは、ノード３０２−１における再生の実行に対応する。この候補仮想ノードは、条件Ｃが満たされるので（例えば、候補仮想ノードの再生値が仮想ノード３０６−１より大きく、及び候補仮想ノードの最終再生以来距離値が仮想ノード３０６−１と等しい）、ブロックされる。残りの候補仮想ノードは、近隣ノード３０２−２及び３０２−５に対応する。ノード３０２−２における候補仮想ノードは、距離値４（例えば、３０２−１から３０２−２の間の仮想リンク３０４の重み）、再生値０（例えば、仮想ノード３０２−２までに行われる再生がない）、及び再生以来距離値４（例えば、３０２−１から３０２−２までの間の仮想リンク３０４の重み）を有する。仮想ノード３０６−２は、この候補仮想ノードについて生成される。ノード３０２−５における候補仮想ノードは、距離値４（例えば、３０２−１から３０２−５の間の仮想リンク３０４の重み）、再生値０（例えば、仮想ノード３０２−５までに行われる再生がない）、及び再生以来距離値４（例えば、３０２−１から３０２−５までの間の仮想リンク３０４の重み）を有する。仮想ノード３０６−３は、この候補仮想ノードについて生成される。仮想ノード３０６−１は訪問済みとしてマークされる。
【００４７】
仮想ノード３０６−２は、最も少ない再生及び最小距離値について仮想ノード３０６−３と同点なので、トラバースされる次の未訪問仮想ノードである。同点の場合には、いずれかの仮想ノード（例えば、最小ノード番号）が次に選択されて良い。図３Ｃで、仮想ノード３０６−２からの候補仮想ノードは、ノード３０２−２及び近隣ノード３０２−１、３０２−３及び３０２−４における仮想ノードを含む。ノード３０２−２における候補仮想ノードは、ノード３０２−２における再生の実行に対応する。仮想ノード３０６−４は、この候補仮想ノードについて、距離値４（例えば、ノード３０２−１から３０２−２までの間のリンクの重み）、再生値１（例えば、ノード３０２−２における１回の再生）、及び再生以来距離値０（例えば、ノード３０２−２における再生のため）を有し生成される。ノード３０２−１及び３０２−３における候補仮想ノードは、仮想ノード３０６−２からこれらのノードまでの経路が再生無しの最大許容重み６を超えるので（例えば、再生無しで、ノード３０２−１までの結合重みは８であり及びノード３０２−３までの結合重みは１０である）、ブロックされる。仮想ノード３０６−５は、近隣ノード３０２−４において、候補仮想ノードから生成される。仮想ノード３０６−５は、距離値６（例えば、３０２−１→３０２−２→３０２−４の間のリンクの結合重み）、再生値０（例えば、経路内で再生がない）、及び再生以来距離値６（例えば、３０２−１→３０２−２→３０２−４の間の結合重み）を有する。仮想ノード３０６−２は訪問済みとしてマークされる。
【００４８】
仮想ノード３０６−３は、最も少ない再生及び最小距離値を有するので、トラバースされる次の未訪問仮想ノードである。図３Ｄで、仮想ノード３０６−３からの候補仮想ノードは、ノード３０２−５及び近隣ノード３０２−１、３０２−４及び３０２−６における仮想ノードを含む。ノード３０２−５における候補仮想ノードは、ノード３０２−５における再生の実行に対応する。仮想ノード３０６−５は、この候補仮想ノードについて、距離値４（例えば、ノード３０２−１から３０２−５までの間のリンクの重み）、再生値１（例えば、ノード３０２−５における１回の再生）、及び再生以来距離値０（例えば、ノード３０２−５における再生のため）を有し生成される。ノード３０２−１、３０２−４及び３０２−６における候補仮想ノードは、仮想ノード３０６−４からこれらのノードまでの経路が再生無しの最大許容重み６を超えるので（例えば、再生無しで、ノード３０２−１までの結合重みは８であり及びノード３０２−４までの結合重みは７である）、ブロックされる。仮想ノード３０６−４は訪問済みとしてマークされる。
【００４９】
仮想ノード３０６−５は、最も少ない再生及び最小距離値を有するので、トラバースされる次の未訪問仮想ノードである。図３Ｅで、仮想ノード３０６−５からの候補仮想ノードは、ノード３０２−４及び近隣ノード３０２−２、３０２−３、３０２−５及び３０２−６における仮想ノードを含む。ノード３０２−４における候補仮想ノードは、ノード３０２−４における再生の実行に対応する。仮想ノード３０６−７は、この候補仮想ノードについて、距離値６（例えば、ノード３０２−１→３０２−２→３０２−４の間のリンクの結合重み）、再生値１（例えば、ノード３０２−４における１回の再生）、及び再生以来距離値０（例えば、ノード３０２−４における再生のため）を有し生成される。ノード３０２−２、３０２−３、３０２−５及び３０２−６における候補仮想ノードは、仮想ノード３０６−５からこれらのノードまでの経路が再生無しの最大許容重み６を超えるので（例えば、再生無しで、ノード３０２−２までの結合重みは８であり、ノード３０２−３までの結合重みは９であり、ノード３０２−５までの結合重みは９であり、及びノード３０２−６までの結合重みは８である）、ブロックされる。仮想ノード３０６−５は訪問済みとしてマークされる。
【００５０】
仮想ノード３０６−４は、最も少ない再生及び最小距離値について同点であるので、トラバースされる次の未訪問仮想ノードである。図３Ｆで、仮想ノード３０６−４からの候補仮想ノードは、ノード３０２−２及び近隣ノード３０２−１、３０２−３及び３０２−４における仮想ノードを含む。ノード３０２−２における候補仮想ノードは、ノード３０２−２における再生の実行に対応する。この候補仮想ノードは、条件Ｃが満たされるので、ブロックされる。ノード３０２−４における候補仮想ノードは、条件Ａが満たされるので（例えば、仮想ノードは、仮想ノード３０６−５と同じ距離値６、同じ再生値１を有するが、より高い再生以来距離値２を有する）、ブロックされる。ノード３０２−１における候補仮想ノードは、条件Ｂが満たされるので（例えば、仮想ノードは、仮想ノード３０６−１より高い距離値８、高い再生値１を有する）、ブロックされる。ノード３０２−３における候補仮想ノードは、距離値１０（例えば、３０２−１→３０２−２→３０２−３の間のリンクの重み）、再生値１（例えば、仮想ノード３０２−２における１回の再生）、及び再生以来距離値６（例えば、３０２−２から３０２−３までの間のリンクの重み）を有する。仮想ノード３０６−８は、この候補仮想ノードについて生成される。仮想ノード３０６−４は訪問済みとしてマークされる。
【００５１】
仮想ノード３０６−６は、最も少ない再生及び最小距離値を有するので、トラバースされる次の未訪問仮想ノードである。図３Ｇで、仮想ノード３０６−６からの候補仮想ノードは、ノード３０２−５及び近隣ノード３０２−１、３０２−４及び３０２−６における仮想ノードを含む。ノード３０２−５における候補仮想ノードは、ノード３０２−５における再生の実行に対応する。この候補仮想ノードは、条件Ｃ及びＤが満たされるので、ブロックされる。ノード３０２−４における候補仮想ノードは、条件Ａが満たされるので（例えば、仮想ノードは、仮想ノード３０６−７より高い距離値７、同じ再生値１、及び高い再生以来距離値３を有する）、ブロックされる。ノード３０２−１における候補仮想ノードは、仮想ノード３０６−１と比較するとき条件Ｂ及びＣの両方が満たされるので、ブロックされる。ノード３０２−６における候補仮想ノードは、距離値７（例えば、３０２−１→３０２−５→３０２−６の間のリンクの重み）、再生値１（例えば、仮想ノード３０２−５における１回の再生）、及び再生以来距離値３（例えば、３０２−５から３０２−６までの間のリンクの重み）を有する。仮想ノード３０６−９は、この候補仮想ノードについて生成される。仮想ノード３０６−６は訪問済みとしてマークされる。
【００５２】
仮想ノード３０６−７は、最も少ない再生及び最小距離値を有するので、トラバースされる次の未訪問仮想ノードである。図３Ｈで、仮想ノード３０６−７からの候補仮想ノードは、ノード３０２−４及び近隣ノード３０２−２、３０２−３、３０２−５及び３０２−６における仮想ノードを含む。ノード３０２−４における候補仮想ノードは、ノード３０２−４における再生の実行に対応する。この候補仮想ノードは、条件Ｃ及びＤが満たされるので、ブロックされる。ノード３０２−２における候補仮想ノードは、条件Ａが満たされるので（例えば、仮想ノードは、仮想ノード３０６−４と比べて、高い距離値８、同じ再生値１、及び高い再生以来距離値２を有する）、ブロックされる。ノード３０２−５における候補仮想ノードは、仮想ノード３０６−６と比較して条件Ａが満たされるので、ブロックされる。ノード３０２−３における候補仮想ノードは、距離値９（例えば、３０２−１→３０２−２→３０２−４→３０２−３の間のリンクの重み）、再生値１（例えば、仮想ノード３０２−４における１回の再生）、及び再生以来距離値３（例えば、３０２−４から３０２−３までの間のリンクの重み）を有する。仮想ノード３０６−１０は、この候補仮想ノードについて生成される。ノード３０２−６における候補仮想ノードは、距離値８（例えば、３０２−１→３０２−２→３０２−４→３０２−６の間のリンクの重み）、再生値１（例えば、仮想ノード３０２−５における１回の再生）、及び再生以来距離値２（例えば、３０２−４から３０２−６までの間のリンクの重み）を有する。仮想ノード３０６−１１は、この候補仮想ノードについて生成される。仮想ノード３０６−７は訪問済みとしてマークされる。幾つかの実施形態では、仮想ノード３０６−１０がノード３０２−３において追加されるとき、仮想ノード３０６−１０を３０６−８と比べて条件Ａが満たされるので、仮想ノード３０６−８も訪問済みとしてマークされる。
【００５３】
仮想ノード３０６−９は、最も少ない再生及び最小距離値を有するので、トラバースされる次の未訪問仮想ノードである。図３Ｉで、仮想ノード３０６−９からの候補仮想ノードは、ノード３０２−６及び近隣ノード３０２−４、３０２−５及び３０２−７における仮想ノードを含む。ノード３０２−６における候補仮想ノードは、ノード３０２−６における再生の実行に対応する。仮想ノード３０６−１２は、この候補仮想ノードについて、距離値７（例えば、ノード３０２−１→３０２−５→３０２−６の間のリンクの重み）、再生値２（例えば、ノード３０２−５及び３０２−６における再生）、及び再生以来距離値０（例えば、ノード３０２−６における再生のため）を有し生成される。ノード３０２−４における候補仮想ノードは、仮想ノード３０６−７と比較して条件Ａが満たされるので、ブロックされる。宛先ノード３０２−５及び３０２−７における候補仮想ノードは、仮想ノード３０６−９からこれらのノードまでの経路が再生無しの最大許容重み６を超えるので（例えば、再生無しで、ノード３０２−７までの結合重みは８であり及びノード３０２−５までの結合重みは７である）、ブロックされる。仮想ノード３０６−９は訪問済みとしてマークされる。
【００５４】
仮想ノード３０６−１１は、最も少ない再生及び最小距離値を有するので、トラバースされる次の未訪問仮想ノードである。図３Ｊで、仮想ノード３０６−１１からの候補仮想ノードは、ノード３０２−６及び近隣ノード３０２−４、３０２−５及び３０２−７における仮想ノードを含む。ノード３０２−６における候補仮想ノードは、ノード３０２−６における再生の実行に対応する。ノード３０２−６における候補仮想ノードは、仮想ノード３０６−１１と比較して条件Ｃが満たされるので、ブロックされる。ノード３０２−４及び３０２−５における候補仮想ノードは、仮想ノード３０６−６と比較して条件Ａが満たされるので、ブロックされる。ノード３０２−７における候補仮想ノードは、距離値１２（例えば、３０２−１→３０２−２→３０２−４→３０２−６→３０２−７の間のリンクの重み）、再生値１（例えば、仮想ノード３０２−４における１回の再生）、及び再生以来距離値６（例えば、３０２−４→３０２−６→３０２−７の間のリンクの重み）を有する。仮想ノード３０６−１３は、この候補仮想ノードについて生成される。仮想ノード３０６−１１は訪問済みとしてマークされる。
【００５５】
仮想ノード３０６−１０は、最も少ない再生及び最小距離値を有するので、トラバースされる次の未訪問仮想ノードである。図３Ｋで、仮想ノード３０６−１０からの候補仮想ノードは、ノード３０２−３及び近隣ノード３０２−２、３０２−４及び３０２−７における仮想ノードを含む。ノード３０２−３における候補仮想ノードは、ノード３０２−３における再生の実行に対応する。仮想ノード３０６−１４は、この候補仮想ノードについて、距離値９（例えば、ノード３０２−１→３０２−２→３０２−４→３０２−３の間のリンクの重み）、再生値２（例えば、ノード３０２−４及び３０２−３における再生）、及び再生以来距離値０（例えば、ノード３０２−３における再生のため）を有し生成される。ノード３０２−２及び３０２−７における候補仮想ノードは、仮想ノード３０６−１０からこれらのノードまでの経路が再生無しの最大許容重み６を超えるので（例えば、再生無しで、ノード３０２−２までの結合重みは９であり及びノード３０２−７までの結合重みは７である）、ブロックされる。ノード３０２−４における候補仮想ノードは、仮想ノード３０６−７と比較して条件Ａが満たされるので、ブロックされる。仮想ノード３０６−１０は訪問済みとしてマークされる。
【００５６】
仮想ノード３０６−１３は、最も少ない再生及び最小距離値を有するので、トラバースされる次の未訪問仮想ノードである。図３Ｌで、仮想ノード３０６−１３からの候補仮想ノードは、ノード３０２−７及び近隣ノード３０２−３及び３０２−６における仮想ノードを含む。ノード３０２−７における候補仮想ノードは、ノード３０２−７における再生の実行に対応する。仮想ノード３０６−１５は、この候補仮想ノードについて、距離値１２（例えば、ノード３０２−１→３０２−２→３０２−４→３０２−６→３０２−７の間のリンクの重み）、再生値２（例えば、ノード３０２−４及び３０２−７における再生）、及び再生以来距離値０（例えば、ノード３０２−７における再生のため）を有し生成される。ノード３０２−３及び３０２−における候補仮想ノードは、仮想ノード３０６−１３からこれらのノードまでの経路が再生無しの最大許容重み６を超えるので（例えば、再生無しで、ノード３０２−３までの結合重みは１０であり及びノード３０２−６までの結合重みは１０である）、ブロックされる。仮想ノード３０６−１３は訪問済みとしてマークされる。
【００５７】
仮想ノード３０６−１２は、最も少ない再生及び最小距離値を有するので、トラバースされる次の未訪問仮想ノードである。図３Ｍで、仮想ノード３０６−１２からの候補仮想ノードは、ノード３０２−６及び近隣ノード３０２−４、３０２−５及び３０２−７における仮想ノードを含む。ノード３０２−６における候補仮想ノードは、ノード３０２−６における再生の実行に対応する。この候補仮想ノードは、条件Ｃ及びＤが満たされるので、ブロックされる。ノード３０２−４及び３０２−５における候補仮想ノードは、仮想ノード３０６−６及び３０６−７と比較して条件Ｂ及びＣが満たされるので、ブロックされる。ノード３０２−７における候補仮想ノードは、距離値１１（例えば、３０２−１→３０２−５→３０２−６→３０２−７の間のリンクの重み）、再生値２（例えば、仮想ノード３０２−５及び仮想ノード３０２−６における再生）、及び再生以来距離値４（例えば、３０２−６→３０２−７の間のリンクの重み）を有する。仮想ノード３０６−１６は、この候補仮想ノードについて生成される。仮想ノード３０６−１２は訪問済みとしてマークされる。
【００５８】
仮想ノード３０６−１４は、最も少ない再生及び最小距離値を有するので、トラバースされる次の未訪問仮想ノードである。図３Ｎで、仮想ノード３０６−１４からの候補仮想ノードは、ノード３０２−３及び近隣ノード３０２−２、３０２−４及び３０２−７における仮想ノードを含む。ノード３０２−３における候補仮想ノードは、ノード３０２−３における再生の実行に対応する。この候補仮想ノードは、条件Ｃ及びＤが満たされるので、ブロックされる。ノード３０２−７における候補仮想ノードは、仮想ノード３０６−１３及び３０６−１５と比較して条件Ａ及びＢが満たされるので、ブロックされる。ノード３０２−２及び３０２−４における候補仮想ノードは、仮想ノード３０６−４、３０６−７と比較して条件Ｂが満たされるので、ブロックされる。仮想ノード３０６−１４は訪問済みとしてマークされる。
【００５９】
仮想ノード３０６−１６は、最も少ない再生及び最小距離値を有するので、トラバースされる次の未訪問仮想ノードである。図３Ｏで、仮想ノード３０６−１６からの候補仮想ノードは、ノード３０２−７及び近隣ノード３０２−３及び３０２−６における仮想ノードを含む。ノード３０２−７における候補仮想ノードは、ノード３０２−７における再生の実行に対応する。この候補仮想ノードは、条件Ｂ及びＤが満たされるので、ブロックされる。ノード３０２−３及び３０２−６における候補仮想ノードは、仮想ノード３０６−１６からこれらのノードまでの経路が再生無しの最大許容重み６を超えるので（例えば、再生無しで、ノード３０２−３までの結合重みは８であり及びノード３０２−６までの結合重みは８である）、ブロックされる。仮想ノード３０６−１６は訪問済みとしてマークされる。
【００６０】
仮想ノード３０６−１５は、トラバースされる次の且つ最後の未訪問ノードである。図３Ｐで、仮想ノード３０６−１５からの候補仮想ノードは、ノード３０２−７及び近隣ノード３０２−３及び３０２−６における仮想ノードを含む。ノード３０２−７における候補仮想ノードは、ノード３０２−７における再生の実行に対応する。この候補仮想ノードは、条件Ｂ及びＤが満たされるので、ブロックされる。ノード３０２−３及び３０２−６における候補仮想ノードは、これらのノードにおける仮想ノードと比較して条件Ａ，Ｂ及びＣが満たされるので、ブロックされる。仮想ノード３０６−１５は訪問済みとしてマークされる。
【００６１】
ネットワーク３００の中の全ての仮想ノードが訪問された後、送信元ノード３０２−１から宛先ノード３０２−７への最短最少再生経路は、３０２−７における仮想ノードから決定されて良い。仮想ノード３０６−１３は、仮想ノード３０６−１５及び３０６−１６より少ない、再生値１を有する。したがって、仮想ノード３０６−１３を通る経路は、ネットワーク３００における宛先ノード３０２−７への最短最少再生経路を表す。図３Ｑの中の最短経路３２０（例えば、ノード３０２−１→３０２−２→３０２−４→３０２−６→３０２−７の間の経路）は、最短最少再生経路を示す。最短経路の中のノードの決定は、任意の適切な方法で追跡されて良い。例えば、仮想リンクが生成された前のノードは、最短経路の計算中に追跡されて良く、宛先ノードから送信元ノードへと逆に作業することにより、経路内の特定仮想ノードが決定されるようにして良い。
【００６２】
図３Ａ〜３Ｑは本発明に従い動作する例示的な最短経路アルゴリズムを示すが、上述の順序及び実装は限定を意図しない。上述の実装は、ダイクストラの最短経路アルゴリズムによる実装を表す。しかしながら、本発明は、図２に関して上述したものを含む任意の他の最短経路アルゴリズムにより実装されて良い。
【００６３】
上述のように、ネットワーク３００は、制約を有する最短経路を決定する制御システムを有して良い。図２の制御システムと同様に、実行可能命令（つまり、実行可能コード）は、本発明の１又は複数の特徴を実装するためにプロセッサにより実行されて良い。
【００６４】
図４は、光ネットワークの中の最短最少再生経路を決定するための方法のフローチャートである。方法４００は、経路計算エンジン２０２を含む図２に記載した制御システム２００の要素のうちの１又は複数を用いて実行されて良い。留意すべきことに、方法４００で記載される特定の動作は、異なる実施形態では任意であって良く或いは再配置されて良い。
【００６５】
方法４００は、ステップ４０２で、ネットワークの中の送信元ノードに仮想ノードを生成することにより開始して良い。上述のように、各々の仮想ノードは、経路計算で使用される値を有して良い。仮想ノードの、距離値、再生値、及び最終再生以来距離値は、信号が送信元ノードにおいて生成されてからトラバースされた物理リンクが無いので、０に設定されて良い。仮想ノード及び仮想ノードに関連する値は、送信元ノードにある記憶媒体、又はネットワーク内の若しくはネットワークに通信可能に結合される別の要素にある記憶媒体に格納されて良い。
【００６６】
ステップ４０４で、未訪問仮想ノードが処理のために選択される。幾つかの実施形態では、選択された仮想ノードは、最少再生値（例えば、最も少ない再生）及び最小距離値（例えば、送信元ノードから仮想ノードへトラバースされるリンクの最小結合重み）を有する、ネットワーク内の未訪問仮想ノードであって良い。
【００６７】
ステップ４０６で、選択された仮想ノードからの候補仮想ノードが検討される。候補仮想ノードは、ステップ４０４で選択された仮想ノードの現在のノードにある新しい仮想ノードを含んで良い。現在のノード３０２にある新しい仮想ノードは、その特定ノードにおける再生の実行を表す。幾つかの実施形態では、ノードは、再生を実行するためのハードウェア、ソフトウェア、及び／又はリソースが足りなくて良い。この場合には、現在のノードにおける新しい仮想ノードはブロックされて良い。候補仮想ノードは、近隣ノードにおける仮想ノードの追加も含んで良い（例えば、物理リンクにより現在のノードに結合されるノード）。
【００６８】
次に、ステップ４０８で、候補仮想ノードが最大許容重みに違反し得るか否かに関して決定されて良い。例えば、選択された候補仮想ノードの距離は、候補仮想ノードへの経路が最大許容重み（例えば、最終再生以来の最大結合重み）に違反し得るかどうかを決定するために、調べられて良い。候補仮想ノードが最大許容重みに違反した場合、候補仮想ノードは最短最少再生経路の部分になれないので、方法４００はステップ４０６に戻って良い。その他の場合、方法はステップ４１０へ進んで良い。
【００６９】
次に、ステップ４１０で、最短最少再生経路条件が満たされるか否かに関し決定されて良い。例えば、候補仮想ノードは、その距離値が同じノードにおける既存の仮想ノードより大きい又は等しい、最終再生以来距離が同じノードにおける既存の仮想ノードの距離より大きい、及び両方のノードの再生値が同じであるかどうかを決定するために調べられて良い。候補仮想ノードは、その距離値及び再生値が両方とも同じノードにおける既存の仮想ノードのものより大きいかどうかを決定するためにも調べられて良い。候補仮想ノードは、同じノードにおける既存の仮想ノードのものより、該候補仮想ノードの再生値が大きい及び最終再生以来距離値が大きい又は等しいかどうかを決定するためにも調べられて良い。候補仮想ノードは、その再生値が同じノードにおける既存の仮想ノードの再生値に１を加えたものより大きいかどうかを決定するためにも調べられて良い。上述の条件のいずれかが存在する場合、候補仮想ノードは最短最少再生経路の部分になれないので、方法４００はステップ４０６に戻って良い。
【００７０】
しかしながら、ステップ４１０で条件のいずれも識別されないとき、方法４００はステップ４１２に進んで良い。ステップ４１２で、仮想ノードは候補仮想ノードから生成される。仮想ノードの、距離値、再生値、及び最終再生以来距離値は、トラバースされた物理リンク及び生じた再生に基づき、適切な値に設定されて良い。例えば、再生が仮想ノードにおいて実行される場合、再生値は、前の仮想ノードにおける再生値からインクリメントされて良い。距離値は、仮想ノードから伝搬した物理リンクの重みにより増大されて良い。最終再生以来距離値は、再生が仮想ノードにおいて実行される場合には０にリセットされて良く、その他の場合には仮想ノードから伝搬した物理リンクの重みにより増大されて良い。幾つかの実施形態では、同じノードにおける他の仮想ノードは、ステップ４１０で列挙された同じ条件により、新たに生成される仮想ノードに対して調べられて良い。他の仮想ノードが、新しい仮想ノードに基づき最短最少再生経路の部分になれない場合（例えば、ステップ４１０における条件が満たされる）、他の仮想ノードは、処理されないように訪問済みとしてマークされて良い。
【００７１】
次に、ステップ４１４で、検討するための更なる候補仮想ノードが存在するか否かに関して決定されて良い。検討するための更なる候補仮想ノードが存在する場合、方法４００は、ステップ４０６に戻って良い。ステップ４０６では、新しい候補仮想ノードが処理のために選択される。しかしながら、検討するための更なる候補仮想ノードが存在しない場合、方法４００はステップ４１６に進んで良い。
【００７２】
ステップ４１６で、処理中の仮想ノードは、訪問済みとしてマークされて良い。
【００７３】
次に、ステップ４１８で、検討するための更なる未訪問仮想ノードが存在するか否かに関して決定されて良い。検討するための更なる未訪問仮想ノードが存在する場合、方法４００は、ステップ４０４に戻って良い。ステップ４０４では、次の未訪問仮想ノードが処理のために選択される。しかしながら、検討するための更なる未訪問仮想ノードが存在しない場合、方法４００はステップ４２０に進んで良い。
【００７４】
ステップ４２０で、最短最少再生経路が識別される。幾つかの実施形態では、最短経路は、仮想ノード間の仮想リンクにより識別されて良い。例えば、最少再生値及び最小距離値を有する、宛先ノードにおける仮想ノードは、最短最少再生経路に対応して良い。したがって、仮想ノード間の仮想リンクは、最短最少再生経路を識別するために、送信元ノードへと逆にトラバースされて良い。最短最少再生経路は、仮想ノードの経路に対応するネットワークノードを通じて良い。経路は、最も少ない再生を伴う、送信元ノードと宛先ノードとの間の最短経路を表して良い。
【００７５】
ステップ４２２で、送信元ノードと宛先ノードとの間のトラフィックは、ステップ４２０で識別された最短最少再生経路を経由してルーティングされる。識別された経路は、送信元と宛先ノードとの間の通信のために使用されて良い。例えば、ネットワーク制御システムは、識別された経路に沿う送信元と宛先ノードとの間の通信チャネルをプロビジョニングして良く、これらのノード間のトラフィックが経路の中の種々のノードに沿って向けられるようにする。
【００７６】
以上に開示した主題は、説明のためであり、限定ではないと考えられるべきである。また、添付の特許請求の範囲は、本開示の真の精神及び範囲に包含される全ての変更、拡張及び他の実施形態を包含することを意図している。例えば、全ての最短最少再生経路が望ましい場合、ステップ４１０における条件のうちの１又は複数が変更されて良い。説明のために、候補仮想ノードは、その距離値が同じノードにおける既存の仮想ノードより大きい（例えば、それより大きい又は等しいとは反対に）、最終再生以来距離が同じノードにおける既存の仮想ノードの距離より大きい、及び両方のノードの再生値が同じであるかどうかを決定するために調べられて良い。別の例として、候補仮想ノードは、同じノードにおける既存の仮想ノードのものより、該候補仮想ノードの再生値が大きい及び最終再生以来距離値が大きい（例えば、それより大きい又は等しいとは反対に）、かどうかを決定するためにも調べられて良い。したがって、法により認められる最大範囲まで、本開示の範囲は、特許請求の範囲及びその等価物の最も広い許容可能な解釈により決定されるべきであり、前述の詳細な説明により限定又は制限されるべきではない。
【００７７】
以上の実施形態に加え、更に以下の付記を開示する。
（付記１）  光ネットワークにおいて最短最少再生経路を決定する方法であって、前記方法は、
送信元ノードにおいて仮想ノードを生成するステップであって、前記送信元ノードは、複数のノード及びリンクを通じて宛先ノードに通信可能に結合される、ステップと、
前記仮想ノードをトラバースするステップであって、前記仮想ノードをトラバースするステップは、
ノードにおける未訪問仮想ノードを選択するステップと、
前記未訪問仮想ノードから候補仮想ノードを識別するステップであって、前記候補仮想ノードは、前記ノード及び近隣ノードにおける新しい仮想ノードを表す、ステップと、
前記候補仮想ノードが最大許容重みを超えるか否かを決定するステップと、
前記候補仮想ノードが最短最少再生経路条件に違反するか否かを決定するステップであって、前記最短最少再生経路条件は、前記最短最少再生経路の部分にならない仮想ノードを識別する、ステップと、
前記候補仮想ノードが前記最大許容重みを超えない場合、及び前記候補仮想ノードが前記最短最少再生経路条件に違反しない場合、前記候補仮想ノードから前記新しい仮想ノードを生成するステップと、
前記未訪問仮想ノードを訪問済みとしてマークするステップと、
を含む、ステップと、
前記仮想ノードから、前記送信元ノードと前記宛先ノードとの間の最短最少再生経路を識別するステップと、
を有する方法。
（付記２）  前記新しい仮想ノードを生成するステップは、
前記新しい仮想ノードの距離値を、前記送信元ノードから前記新しい仮想ノードへの経路の中のリンクの結合重みに設定するステップと、
前記新しい仮想ノードの再生値を、前記新しい仮想ノードへの前記経路の中の合計再生数に設定するステップと、
前記新しい仮想ノードの最終再生以来距離値を、前記新しい仮想ノードと再生が生じた前の仮想ノードとの間のリンクの結合重みに設定するステップと、
を含む、付記１に記載の方法。
（付記３）  前記新しい仮想ノードと再生が生じた前の仮想ノードとの間のリンクの結合重みが所定最大許容重みを超える場合、前記候補仮想ノードは最大許容重みを超える、付記１に記載の方法。
（付記４）  前記候補仮想ノードが前記最短最少再生経路条件に違反するか否かを決定するステップは、距離値、再生値、及び最終再生以来距離値のうちの１つを、前記ノードにおける既存の仮想ノードと比較するステップを含む、付記１に記載の方法。
（付記５）  前記距離値が前記既存の仮想ノードより大きい又は等しい、前記候補仮想ノードの前記最終再生以来距離値が前記既存の仮想ノードより大きい、及び前記候補仮想ノードの前記再生値が前記既存の仮想ノードと等しい場合、前記仮想ノードは前記最短最少再生経路条件に違反する、付記４に記載の方法。
（付記６）  前記距離値が前記既存の仮想ノードより大きい、及び前記候補仮想ノードの前記再生値が前記既存の仮想ノードより大きい場合、前記仮想ノードは前記最短最少再生経路条件に違反する、付記４に記載の方法。
（付記７）  前記再生値が前記既存の仮想ノードより大きい、及び前記最終再生以来距離値が前記既存の仮想ノードより大きい又は等しい場合、前記仮想ノードは前記最短最少再生経路条件に違反する、付記４に記載の方法。
（付記８）  前記候補仮想ノードの前記再生値が前記既存の仮想ノードの前記再生値に１を加えたものより大きい場合、前記仮想ノードは前記最短最少再生経路条件に違反する、付記４に記載の方法。
（付記９）  前記最短最少再生経路を識別するステップは、
最少再生値及び最小距離値を有する、前記宛先ノードにおける仮想ノードを選択するステップと、
前記送信元ノードへ、前記最少再生値及び前記最小距離値を有する、前記仮想ノードからの前記リンクを辿るステップと、
を含む、付記１に記載の方法。
（付記１０）  前記仮想ノードから未訪問仮想ノードを選択するステップは、最少再生値及び距離値を有する仮想ノードを選択するステップを含む、付記１に記載の方法。
（付記１１）  最短最少再生経路を識別する制御システムであって、前記制御システムは、命令を格納する記憶媒体へのアクセスを有するプロセッサを有し、前記命令は、前記プロセッサにより実行可能であり、
送信元ノードにおいて仮想ノードを生成し、前記送信元ノードは、複数のノード及びリンクを通じて宛先ノードに通信可能に結合され、
ノードにおける未訪問仮想ノードを選択し、
前記未訪問仮想ノードから候補仮想ノードを識別し、前記候補仮想ノードは、前記ノード及び近隣ノードにおける新しい仮想ノードを表し、
前記候補仮想ノードが最大許容重みを超えるか否かを決定し、
前記候補仮想ノードが最短最少再生経路条件に違反するか否かを決定し、前記最短最少再生経路条件は、前記最短最少再生経路の部分にならない仮想ノードを識別し、
前記候補仮想ノードが前記最大許容重みを超えない場合、及び前記候補仮想ノードが前記最短最少再生経路条件に違反しない場合、前記候補仮想ノードから前記新しい仮想ノードを生成し、
前記未訪問仮想ノードを訪問済みとしてマークし、
前記仮想ノードから、前記送信元ノードと前記宛先ノードとの間の最短最少再生経路を識別する、
ためのものである、制御システム。
（付記１２）  前記記憶媒体は、
前記新しい仮想ノードの距離値を、前記送信元ノードから前記新しい仮想ノードへの経路の中のリンクの結合重みに設定し、
前記新しい仮想ノードの再生値を、前記新しい仮想ノードへの前記経路の中の合計再生数に設定し、
前記新しい仮想ノードの最終再生以来距離値を、前記新しい仮想ノードと再生が生じた前の仮想ノードとの間のリンクの結合重みに設定する、
ための命令を更に含む、付記１１に記載の制御システム。
（付記１３）  前記新しい仮想ノードと再生が生じた前の仮想ノードとの間のリンクの結合重みが所定最大許容重みを超える場合、前記候補仮想ノードは最大許容重みを超える、付記１１に記載の制御システム。
（付記１４）  前記候補仮想ノードが前記最短最少再生経路条件に違反するか否かを決定することは、距離値、再生値、及び最終再生以来距離値のうちの１つを、前記ノードにおける既存の仮想ノードと比較することを含む、付記１１に記載の制御システム。
（付記１５）  前記距離値が前記既存の仮想ノードより大きい又は等しい、前記候補仮想ノードの前記最終再生以来距離値が前記既存の仮想ノードより大きい、及び前記候補仮想ノードの前記再生値が前記既存の仮想ノードと等しい場合、前記仮想ノードは前記最短最少再生経路条件に違反する、付記１４に記載の制御システム。
（付記１６）  前記距離値が前記既存の仮想ノードより大きい、及び前記候補仮想ノードの前記再生値が前記既存の仮想ノードより大きい場合、前記仮想ノードは前記最短最少再生経路条件に違反する、付記１４に記載の制御システム。
（付記１７）  前記再生値が前記既存の仮想ノードより大きい、及び前記最終再生以来距離値が前記既存の仮想ノードより大きい又は等しい場合、前記仮想ノードは前記最短最少再生経路条件に違反する、付記１４に記載の制御システム。
（付記１８）  前記候補仮想ノードの前記再生値が前記既存の仮想ノードの前記再生値に１を加えたものより大きい場合、前記仮想ノードは前記最短最少再生経路条件に違反する、付記１４に記載の制御システム。
（付記１９）  前記最短最少再生経路を識別することは、
最少再生値及び最小距離値を有する、前記宛先ノードにおける仮想ノードを選択することと、
前記送信元ノードへ、前記最少再生値及び前記最小距離値を有する、前記仮想ノードからの前記リンクを辿ることと、
を含む、付記１１に記載の制御システム。
（付記２０）  前記仮想ノードから未訪問仮想ノードを選択することは、最少再生値及び距離値を有する仮想ノードを選択することを含む、付記１１に記載の制御システム。
【符号の説明】
【００７８】
２００  制御システム
２０２  経路計算エンジン
２０４  データベース
２０６  シグナリングモジュール
２０８  プロセッサ
２１０  ルーティングモジュール
２１２  発見モジュール
２１４  ネットワークインタフェース
２２０  記憶媒体
２３０  ネットワーク
【図１】
2017216686.tif 000003
【図２】
2017216686.tif 000004
【図３Ａ】
2017216686.tif 000005
【図３Ｂ】
2017216686.tif 000006
【図３Ｃ】
2017216686.tif 000007
【図３Ｄ】
2017216686.tif 000008
【図３Ｅ】
2017216686.tif 000009
【図３Ｆ】
2017216686.tif 000010
【図３Ｇ】
2017216686.tif 000011
【図３Ｈ】
2017216686.tif 000012
【図３Ｉ】
2017216686.tif 000013
【図３Ｊ】
2017216686.tif 000014
【図３Ｋ】
2017216686.tif 000015
【図３Ｌ】
2017216686.tif 000016
【図３Ｍ】
2017216686.tif 000017
【図３Ｎ】
2017216686.tif 000018
【図３Ｏ】
2017216686.tif 000019
【図３Ｐ】
2017216686.tif 000020
【図３Ｑ】
2017216686.tif 000021
【図４】
2017216686.tif 000022