波長パス再配置方法及び上位レイヤパス再配置方法
【課題】通信網内で使用されている波長領域の空き波長も含めた波長数（使用波長領域数）並びに通信装置コストを削減することを目的とする。
【解決手段】通信網内に設定された波長パスを再配置するパス再配置装置における波長パス再配置方法は、波長パス設計部が、通信網内の使用波長領域数を再配置前の値より小さくする計算を行うことにより、再配置先の波長パスを設計する波長パス設計ステップと、波長パス設定部が、空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更する波長パス設定ステップを有する。
【解決手段】通信網内に設定された波長パスを再配置するパス再配置装置における波長パス再配置方法は、波長パス設計部が、通信網内の使用波長領域数を再配置前の値より小さくする計算を行うことにより、再配置先の波長パスを設計する波長パス設計ステップと、波長パス設定部が、空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更する波長パス設定ステップを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、波長パス再配置方法及び上位レイヤパス再配置方法に関する。
【背景技術】
【０００２】
中継ノード間で波長変換が行われないトランスペアレント光メッシュ網においては、波長パスの設定及び削除を繰り返すことによって徐々に波長空き帯域を有効に使うことができなくなり、ネットワーク設備量が増大することが懸念される。また、OTN（Optical Transport Network）やSDH（Synchronous Digital Hierarchy）やVCAT（Virtual Concatenation）等の上位レイヤパスにおいても、パスの設定及び削除を繰り返すことによって波長パス内の収容効率が悪くなると考えられる。
【０００３】
これらの問題を解決するために、波長パスを再配置する方法（非特許文献１参照）、パスの容量・経路を変更する方法（特許文献１参照）が提案されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−２０５７２
【特許文献２】特開２００７−２０９０４０
【非特許文献】
【０００５】
【非特許文献１】E. Bouillet, et al., "Lightpath Re-Optimization in Mesh Optical Networks", IEEE/ACM Transactions on Networking, Vol. 13, No2, pp437-pp447.April, 2005.
【非特許文献２】J. Kuri, et al., "Resolution of a WDM network design problem using a decomposition approach and a size reduction method", Proceedings of ECUMN 2002, Colmar,. France, April 2002.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記の通り、波長パスの設定及び削除を繰り返すことによって、通信網内で使用されている波長領域内に空き波長が生じて、波長領域内の空き波長も含めた波長数（使用波長領域数）、すなわち、使用中の最小の波長番号から使用中の最大の波長番号までの波長数（通信網内で使用されていない波長番号を除く）が大きくなる。しかし、非特許文献１及び特許文献１に記載の方法では、使用波長領域数を削減することは考慮されていない。
【０００７】
また、波長パスを再配置するときの順序（再配置対象の波長パスを再配置先の波長パスに変更する順序）と空きリソース量によっては、波長パスを再配置できない可能性がある。しかし、非特許文献１及び特許文献１に記載の方法では、波長パスを再配置するときの順序は考慮されていない。
【０００８】
更に、波長パス内に上位レイヤパスが設定されている場合には、上位レイヤパスと波長パスとの双方を考慮して再配置する必要があるが、非特許文献１及び特許文献１に記載の方法では、このような点は考慮されていない。
【０００９】
更に、波長パスの再配置を行うオペレーション数を考慮して、オペレーションコストも最小にするような波長パスの再配置方法は考えられていない。
【００１０】
上記の課題を解決するため、本発明は、通信網内で使用されている波長領域の空き波長も含めた波長数（使用波長領域数）の削減並びにオペレーションコストを削減する波長パス再配置方法及び上位レイヤパス再配置方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の波長パス再配置方法は、
通信網内に設定された波長パスを再配置するパス再配置装置における波長パス再配置方法であって、
波長パス設計部が、通信網内の使用波長領域数を再配置前の値より小さくする計算を行うことにより、再配置先の波長パスを設計する波長パス設計ステップと、
波長パス設定部が、空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更する波長パス設定ステップと、
を有することを特徴とする。
【００１２】
本発明の上位レイヤパス再配置方法は、
通信網内に設定された波長パス内の上位レイヤパスを再配置するパス再配置装置における上位レイヤパス再配置方法であって、
上位レイヤパス設計部が、通信網内で使用されている波長数を再配置前の値より小さくする計算を行うことにより、再配置先の上位レイヤパスを設計する上位レイヤパス設計ステップと、
上位レイヤパス設定部が、再配置対象の上位レイヤパスを再配置先の上位レイヤパスに変更する上位レイヤパス設定ステップと、
を有することを特徴とする。
【００１３】
本発明の波長パス再配置方法は、
通信網内に設定された波長パスを再配置するパス再配置装置におけるパス再配置方法であって、
波長パス設計部が、通信装置の利用効率を上げる、もしくは将来的なトラフィック需要による波長衝突を削減するように波長パスを再配置する波長パス設計ステップと、
空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更するための順序を決定してオペレーション数を算出する収容順序演算ステップを有し、
オペレーション数が最小の波長再配置及び順序を決定するステップを有することを特徴とする。
【発明の効果】
【００１４】
本発明によれば、通信網内で使用されている波長領域の空き波長も含めた波長数（使用波長領域数）を削減とともにオペレーションコストの削減も実現することが可能になる。
【図面の簡単な説明】
【００１５】
【図１】使用波長領域数と使用波長数とを説明するための図（その１）
【図２】使用波長領域数と使用波長数とを説明するための図（その２）
【図３】フラグメンテーション関数の説明図例
【図４】本発明の第１の実施形態に係る管理装置のブロック図（集中制御方式）
【図５】本発明の第１の実施形態に係るノード装置のブロック図（その１）
【図６】本発明の第１の実施形態に係るノード装置のブロック図（その２）
【図７】本発明の第１の実施形態に係るノード装置のブロック図（分散制御方式）
【図８】本発明の第１の実施形態で用いられるフロー保存方程式の算出例を示す図
【図９】本発明の第１の実施形態に係る管理装置で計算された再配置前後の波長パスを示す図
【図１０】本発明の第１の実施形態に係る管理装置における収容順序決定手順を示す図
【図１１】本発明の第１の実施形態に係る管理装置における波長パス設定手順を示す図
【図１２】本発明の第１の実施形態に係る管理装置における波長パスの再配置を示す図
【図１３】本発明の第１の実施形態に従って波長パスを設定するシーケンス図（集中制御方式）
【図１４】本発明の第１の実施形態に従って波長パスを設定するシーケンス図（分散制御方式）
【図１５】本発明の第２の実施形態に係る管理装置における収容順序決定手順を示す図
【図１６】本発明の第３又は４の実施形態に係る管理装置のブロック図（集中制御方式）
【図１７】本発明の第４の実施形態に係る管理装置における波長パスの再配置を示す図
【図１８】本発明の第４の実施形態に係る管理装置における波長パス設定手順を示す図
【図１９】本発明の第５の実施形態に係る管理装置のブロック図（集中制御方式）
【図２０】本発明の第５の実施形態に係る管理装置における波長パスの再配置を示す図
【図２１】本発明の第６の実施形態に係る管理装置のブロック図（集中制御方式）
【図２２】本発明の第６の実施形態に係る管理装置における上位レイヤパス設定手順を示す図
【図２３】本発明の第６の実施形態に従って上位レイヤパスを設定するシーケンス図（集中制御方式）
【図２４】本発明の第６の実施形態に従って上位レイヤパスを設定するシーケンス図（分散制御方式）
【図２５】本発明の第７の実施形態に係る管理装置のブロック図
【図２６】本発明の第７の実施形態に係る管理装置における上位レイヤパス設定手順を示す図
【図２７】本発明の第８の実施形態に係る管理装置のブロック図（集中制御方式）
【図２８】本発明の第８の実施形態に係る管理装置における上位レイヤパス及び波長パスの再配置手順を示す図
【図２９】本発明の第９の実施形態に係る管理装置における収容順序決定手順を示す図
【図３０】本発明の第１０の実施形態に係る管理装置における波長パス設定手順を示す図
【図３１】本発明の第１０の実施形態で用いられる物理トポロジ及び波長割当状況を示す図
【図３２】本発明の第１０の実施形態に係る管理装置における波長パスの再配置を示す図
【図３３】本発明の第１１の実施形態に係る管理装置における計算対象の波長パスを示す図
【図３４】本発明の第１２の実施形態に係る管理装置における計算対象の波長パスを示す図
【図３５】本発明の第１３の実施形態に係る通信システムの概要図
【図３６】本発明の第１４の実施形態に係る管理装置における波長パスの再配置を示す図
【図３７】本発明の第１５の実施形態に係るフローチャート
【図３８】本発明の第１５の実施の形態に係るフラグメンテーションコストの説明図例
【図３９】本発明の第１６の実施形態に係るフローチャート
【図４０】本発明の第１９の実施の形態に係るフローチャート
【図４１】本発明の第１９の実施の形態における効果
【図４２】本発明の第２０の実施の形態における再配置の例を示す図
【図４３】本発明の実施形態における上位レイヤパスの再配置の効果を示す図
【図４４】本発明の実施形態における波長パスの再配置の効果を示す図
【図４５】本発明の効果を示すための想定モデル
【図４６】本発明における波長パス及び上位例やパス再配置の効果
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について詳細に説明する。
【００１７】
まず、本発明の実施形態で用いる用語について説明する。
【００１８】
「使用波長領域数」とは、通信網内で使用されている波長領域の空き波長を含めた波長数、すなわち、使用中の最小の波長番号から使用中の最大の波長番号までの波長数（通信網内で使用されていない波長番号を除く）のことである。使用波長領域数の算出には、（１）リンク毎に使用されている波長領域の波長数を算出する方法と、（２）通信網全体で使用されている波長領域の波長数を算出する方法との２通りがある。
【００１９】
「使用波長数」とは、使用されている波長の数である（空き波長は含まない）。
【００２０】
例えば、図１のように波長を小さい順又は大きい順に割り当てた通信網における使用波長領域数及び波長数について説明する。（１）の場合、ノードA-B間の使用波長領域数は６（λ１〜λ６）となり、使用波長数は４（λ１、λ２、λ３、λ６）となる。ノードB-C間の使用波長領域数は４（λ２〜λ５）となり、使用波長数は３（λ２、λ３、λ５）となる。ノードC-D間の使用波長領域数は５（λ２〜λ６）となり、使用波長数は５（λ２〜λ６）となる。（２）の場合、全てのリンクにおいて使用波長領域数は６（λ１〜λ６）となる。
【００２１】
また、図２のように波長をランダムに（小さい順又は大きい順以外の方法で）割り当てた場合又は波長パスが削除されて使用されていない波長が存在する場合、通信網内において使用されている波長を片側に寄せて使用波長領域数を算出する。（１）の場合、ノードA-B間の使用波長領域数は３（λ１、λ２、λ６）となり、使用波長数は３（λ１、λ２、λ６）となる。ノードB-C間の使用波長領域数は４（λ２、λ６、λ４、λ７）となり、使用波長数は３（λ２、λ４、λ７）となる。ノードC-D間の使用波長領域数は４（λ２、λ６、λ４、λ７）となり、使用波長数は３（λ２、λ６、λ７）となる。（２）の場合、全てのリンクにおいて使用波長領域数は５（λ１、λ２、λ６、λ４、λ７）となる。
【００２２】
なお、「使用波長数領域数」は、ノードの「使用しているポートまでの数」、「使用波長数」はノードの「使用しているポート数」としてもよい。
【００２３】
「スイッチング機能部」とは、信号光をスイッチングする機能部であり、例えば、光クロスコネクト、光スイッチ、ODU（Optical-channel Data Unit）クロスコネクト、2-D MEMS（Micro Electro Mechanical Systems）スイッチ、3-D MEMSスイッチ等が含まれる。
【００２４】
「波長パス選択機能部」とは、波長を選択する機能部であり、例えばWSS（Wavelength Selective Switch）等が含まれる。
【００２５】
「管理装置」とは、波長パスの波長及び経路を選択して設定し、また、上位レイヤパスの経路を選択して設定する装置であり、例えば、NMS（Network Management System）、NRM（Network Resource Manager）、PCE（Path Computation Element）、EMS（Element Management System）等が含まれる。
【００２６】
「無瞬断切り替え」とは、瞬断なく切り替えることであり、例えば、短時間で（50ms以内等）パスを切り替えること、データが欠落しないようにパスを切り替えること、パケットレイヤでパケットが欠落しないようにパスを切り替えること等が含まれる。短時間でパスを切り替える場合には、その間のデータが欠落してもよい。
【００２７】
「上位レイヤパス」とは、波長パス内に設定されてユーザに提供されるパスのことであり、例えば、TDM（Time Division Multiplexing）パス、SDH（Synchronous Digital Hierarchy）パス、Ethernet（登録商標）、MPLS（Multiprotocol Label Switching）のLabel Switched Path、又はそれらをグループ化したVCAT（Virtual Concatenation）、Link Aggregation等が含まれる。上位レイヤパスは、波長パスに重畳される。
【００２８】
「上位レイヤパスの粒度」とは、上位レイヤパスに割り当てられた帯域量のことであり、例えば、１Ｇ上位レイヤパスの粒度とは、１Ｇであり、３Ｇ上位レイヤパスの粒度とは３Ｇである。
【００２９】
「通信路設定メッセージ」とは、リソースの予約又はリソースの割り当てを行う制御情報とパス経路情報とを含むメッセージのことであり、波長パスを設定する場合には、通信路設定メッセージは更に波長情報を含む。
【００３０】
「通信路設定完了通知」とは、波長情報を含む波長パスの設定が完了したことを通知するメッセージである。
【００３１】
「通信路削除メッセージ」とは、リソースの開放予約又はリソースの開放を行う制御情報とパス経路情報とを含むメッセージのことであり、波長パスを削除する場合には、通信路削除メッセージは更に波長情報を含む。
【００３２】
「通信路削除完了通知」とは、波長情報を含む波長パスの削除が完了したことを通知するメッセージである。
【００３３】
「上位レイヤパス設定メッセージ」とは、上位レイヤパスを収容する波長パスを選択するための波長情報又はポート情報と、収容する上位レイヤパスの識別情報とを含むメッセージである。
【００３４】
「上位レイヤパス削除完了通知」とは、上位レイヤパスの識別情報を含む上位レイヤパスの削除が完了したことを通知するメッセージである。
【００３５】
「上位レイヤパス削除メッセージ」とは、リソースの開放予約又はリソースの開放を行う制御情報とパス経路情報とを含むメッセージのことであり、更に上位レイヤパスの識別情報を含む。
【００３６】
「波長パス選択完了通知」とは、上位レイヤパスの識別情報を含む波長パスの選択が完了したことを通知するメッセージである。
【００３７】
「リソース開放メッセージ」とは、ノード装置に対してリソース開放を行う制御情報を含むメッセージのことである。
【００３８】
「リソース割当」とは、波長パスにおいては、入力ポートからの波長多重信号光から分波された光信号を、所定の出力光伝送路ポートに同じ波長で出力されるように設定すること（光クロスコネクト）のことである。上位レイヤパスにおいては、始点ノードと終点ノードとの間に上位レイヤパスを設定することであり、始点ノード及び終点ノードに上位レイヤパス設定メッセージを送信することで設定可能である。
【００３９】
「リソース割当メッセージ」とは、ノード装置に対してリソース割り当てを行う制御情報を含むメッセージのことである。
【００４０】
「通信装置」とは、ROADM、ODUクロスコネクトスイッチ、MPLS-TPルータ、OXC、トランスポンダー等である。
【００４１】
「オペレーション数」とは、パスを再配置するときに必要となるパスの設定／削除シーケンスの数のことである。もしくは、パスの設定／削除に必要なオペレーションコストの合計である。
【００４２】
「波長チャネル」とは、図３に示すように、ネットワーク内における波長番号のことのことである。
【００４３】
「フラグメンテーション」とは、図３に示すように、ある波長チャネルにおいて使用可能な経路が限られている状態、もしくは波長がリンクに対して離散的になっている状態をさす。
【００４４】
本発明における実施形態について、以下の３つの場合について説明する。
【００４５】
（１）波長パスを再配置する場合（第１の実施形態〜第５の実施形態、第９の実施形態〜第１２の実施形態、第１４の実施形態〜第２０の実施の形態）
（２）上位レイヤパスを再配置する場合（第６の実施形態〜第７の実施形態）
（３）上位レイヤパスを再配置し、その後波長パスを再配置する場合（第８の実施形態）
なお、（３）は（１）と（２）とを組み合わせた方法であり、（２）の再配置によって不要な波長パスを削減することによって波長パスの再配置数を削減することが可能となる。
【００４６】
＜第１の実施形態＞
第１の実施形態では、波長パスを再配置する場合について説明する。波長パスの設定方法としては集中制御方式と分散制御方式が存在する。集中制御方式は、１つの管理装置で通信網内全体のノード装置を管理し、各ノード装置に対して波長パス及び上位レイヤパスを設定するための制御信号を送信する方式である。分散制御方式は、各ノード装置に管理制御機能が備えられる方式である。
【００４７】
まず、集中制御方式での管理装置及びノード装置について説明する。
【００４８】
図４は、本発明の第１の実施形態に係る管理装置１０のブロック図である。管理装置１０は、既存パス管理データベース１０１と、波長パス事前設計機能部１０２と、再配置対象パス管理データベース１０３と、波長パス収容順序決定機能部１０４と、収容順序管理データベース１０５と、パス設定機能部１０６と、制御信号送受信インタフェース１０７とを有する。
【００４９】
既存パス管理データベース１０１は、通信網内に設定された既存波長パスの経路・波長情報と、通信網内の各リンクの空き波長情報と、上位レイヤパスの収容先の波長パスの経路・波長情報と、各上位レイヤパスの粒度とを管理する。既存パス管理データベース１０１は、クライアント情報（どの上位レイヤパスがどのクライアントに対応するかという情報）を管理してもよい。
【００５０】
波長パス事前設計機能部１０２は、既存パス管理データベース１０１で管理されている情報を用いて、再配置対象の波長パスと、再配置先の波長パスとを事前に設計する。再配置先の波長パスの設計方法は、後述する。
【００５１】
再配置対象パス管理データベース１０３は、波長パス事前設計機能部１０２から得られた再配置対象の波長パス（再配置する必要のある波長パスの再配置前の波長パス）の経路・波長と、再配置先の波長パス（再配置する必要のある波長パスの再配置後の波長パス）の経路・波長とを保存する。
【００５２】
波長パス収容順序決定機能部１０４は、再配置対象の波長パスを再配置先の波長パスに変更することができる収容順序を決定する。収容順序の決定方法は、後述する。
【００５３】
収容順序管理データベース１０５は、波長パス収容順序決定機能部１０４で決定された収容順序情報を保存する。
【００５４】
パス設定機能部１０６は、収容順序に従って、波長パス及び上位レイヤパスを設定／削除する。具体的には、パス設定機能部１０６は、波長パス及び上位レイヤパスの設定／削除を指示するため、制御信号送受信インタフェース１０７を介してリソース割当メッセージ、通信路設定メッセージ又は通信路削除メッセージをノード装置に送信する。また、パス設定機能部１０６は、上位レイヤパスの収容先波長パスの設定／削除を指示するため、制御信号送受信インタフェース１０７を介して上位レイヤパス設定メッセージをノード装置に送信する。なお、パス設定機能部１０６は、波長パス及び上位レイヤパスのリソースの予約（割当）又は開放（削除）情報を保存するためのリソース管理データベース（図示せず）を有してもよい。
【００５５】
制御信号送受信インタフェース１０７は、制御信号をノード装置に送信し、また、ノード装置から制御信号を受信する。
【００５６】
図５は、本発明の第１の実施形態に係るノード装置２０のブロック図である。ノード装置２０は、制御信号送受信インタフェース２０１と、上位レイヤ装置接続インタフェース２０２と、信号複製機能部２０３と、無瞬断切り替え機能部２０４と、波長パス選択機能部２０５と、スイッチング機能部２０６と、データ転送用インタフェース２０７とを有する。
【００５７】
制御信号送受信インタフェース２０１は、管理装置から制御信号を受信し、また、管理装置へ制御信号を送信する。
【００５８】
上位レイヤ装置接続インタフェース２０２は、上位レイヤパスを提供する上位レイヤ装置に接続するためのインタフェースである。
【００５９】
信号複製機能部２０３は、上位レイヤ装置接続インタフェース２０２から入力された信号を複製し、２つのポートから複製信号を送信する。
【００６０】
無瞬断切り替え機能部２０４は、信号複製機能部２０３から入力された２つの信号の位相同期を行い、無瞬断で切り替える。
【００６１】
波長パス選択機能部２０５は、制御信号送受信インタフェース２０１から送られてきた制御信号に基づいて、上位レイヤパスを収容する波長パス（波長）を選択する。
【００６２】
スイッチング機能部２０６は、制御信号送受信インタフェース２０１から送られてきた制御信号に基づいて、波長パスを設定／削除する。
【００６３】
データ転送用インタフェース２０７は、データを別ノードに転送する。
【００６４】
また、図６に示すように、信号複製機能部２０３で信号を複製せずに、上位レイヤ装置接続インタフェース２０２の２つのポートから同じデータを出力してもよい。この場合、信号複製機能部２０３はノード装置２０に含まれなくてもよい。
【００６５】
次に、分散制御方式でのノード装置について説明する。
【００６６】
図７に分散制御方式でのノード装置を示す。分散制御方式の場合、各ノード装置は、図４に示す管理装置の各管理機能部を有する。例えば、図７に示すように、図５のノード装置に、図４の管理装置の各管理機能部が含まれてもよい。同様に、図６のノード装置に、図４の管理装置の各管理機能部が含まれてもよい。図５又は図６におけるノード装置の制御情報送受信インタフェースが各管理機能部と接続するためのインタフェースとなる。なお、パス設定機能部１０６は、波長パス及び上位レイヤパスのリソースの予約（割当）又は開放（削除）情報を保存するためのリソース管理データベース（図示せず）を有してもよい。
【００６７】
次に、波長パス事前設計機能部１０２における波長パスの再配置先の設計方法について説明する。この設計方法は、オフラインで事前に設計されてもよい。ここでは、整数線形計画法（ILP：integer linear programming）を用いて、再配置先の波長パスの経路及び波長を事前に設計する。
【００６８】
波長パス事前設計機能部１０２は、以下の目的関数を最小化する波長パスの経路及び波長を計算する。
【００６９】
【数１】
この目的関数は、使用されている波長番号と波長数の積の合計数を最小化するための関数、すなわち、使用波長領域数を最小化するための関数である。すなわち、できるだけ小さい波長番号から順に波長を使用し、使用されている波長数を少なくすることを目的とした関数である。ただし、pijwsdは、波長wが使用されているか否かを示す変数であり、始点sから終点dまでの各物理リンク(i,j)において、波長wが使用されている場合はpijwsd=1であり、波長wが使用されていない場合はpijwsd=0である。Vはノードの集合であり、Eはリンクの集合であり、Wは波長の集合（w=0,1,2,3,...,WMAX）であり、WMAXは最大波長多重数であり、これらは予め決められたパラメータである。
【００７０】
目的関数(1)の計算にあたり、以下の制約条件を用いる。
【００７１】
【数２】
【００７２】
【数３】
【００７３】
【数４】
【００７４】
【数５】
制約条件(2)は、始点s、終点d及び波長wにおいて各リンクのトラヒックフローを表す方程式（非特許文献２参照）である。この制約によりパスの経路と始点・終点ノードで同一波長を選択することが可能となる。ただし、λwsdは、始点sから終点dまでの経路で波長wが使用されている数（0〜Dsd）を示す。λwsd=0の場合、始点sから終点dまでの経路で波長wが使用されていないことを示し、λwsd=1の場合、始点sから始点dまでの１つの経路で波長wが使用されていることを示す。また、i＜jのときΣpijwsd=Σpijwsd、i＞jのときΣpijwsd=−Σpjiwsdとなる。制約条件(2)の算出例を図８に示す。λwsdは、既存パス管理データベース１０１内に保存された通信網内に設定された既存波長パスの経路・波長情報から求めることができる。
【００７５】
制約条件(3)は、各リンクの波長数の合計が最大波長多重数WMAX以下とする条件である。
【００７６】
制約条件(4)は、波長衝突を起こさないための条件であり同じリンクで２つ以上の同じ波長を使わないという条件である。
【００７７】
制約条件(5)は、始点sから終点dまでの経路で使用される波長の合計数が、始点sから終点dまでの波長パスの需要総数Dsdに等しいという条件である。ただし、Dsdは、始点sから終点dまでの波長パスの総数であり、既存パス管理データベース１０１内に保存された既存パスの経路・波長情報から予め求められる。
【００７８】
制約条件(2)〜(5)を用いて目的関数(1)を計算することにより、再配置後の波長パスの経路及び波長pijwsdが出力される。
【００７９】
制約条件(2)〜(5)に加えて、次の制約条件(6)〜(9)のうち１つ以上が用いられてもよい。
【００８０】
【数６】
【００８１】
【数７】
【００８２】
【数８】
【００８３】
【数９】
制約条件(6)は、始点sから終点dまでのホップ数の合計が最大ホップ数Himpairment以下とする条件である。ただし、Himpairmentは最大伝送可能ホップ数であり、予め決められたパラメータである。
【００８４】
制約条件(7)は、始点sから終点dまでのホップ数の合計が、始点s及び終点dのノードの組毎に設定した伝送ホップ数Hsd以下とする条件である。ただし、Hsdは、始点sから終点dまでのパスにおける伝送ホップ数であり、予め決められたパラメータである。
【００８５】
制約条件(8)は、再配置する波長の数が既存波長数の合計数のうち所定の割合Rを超えないようにする条件である。すなわち、制約条件(8)は、再配置対象の波長数が所定の閾値を超えないようにする条件である。ただし、Rは再配置する波長パスの割合であり、予め決められたパラメータである。
【００８６】
制約条件(9)は、再配置前の始点sから終点dの経路ホップ数と再配置後の経路ホップ数との差が遅延差又は距離差の限界Hdelayを満たすホップ数以下であるとする条件である。ただし、Hdelayは、許容される最大の遅延差又は距離差を満たすホップ数であり、予め決められたパラメータである。
【００８７】
制約条件(6)を用いることにより、再配置対象の波長数を制限することができる。また、制約条件(7)のHsdにおいて、最短ホップ数を事前に設定することで、最短経路の波長パスを計算することができる。また、制約条件(8)により、パスを切り替える際のバッファメモリの許容範囲内での経路選択が可能になる。
【００８８】
また、制約条件(2)〜(5)に加えて、以下の制約条件(10)が用いられてもよい。
【００８９】
【数１０】
制約条件(10)は、経路変更を行わないという条件、すなわち、再配置前の波長パスと再配置後の波長パスの経路が同じであるという条件である。ただし、p0ijwsdは、再配置前に波長wが使用されているか否かを示す変数であり、始点sから終点dまでの各物理リンク(i,j)において、再配置前に波長wが使用されている場合はp0ijwsd =1であり、再配置前に波長wが使用されていない場合はp0ijwsd=0である。p0ijwsdは、既存パス管理データベース１０１内に、通信網内に設定された既存波長パスの経路・波長情報として保存されている。
【００９０】
このように、制約条件(10)では、経路変更を行わずに再配置先の波長パスを計算することができる。
【００９１】
波長パス事前設計機能部１０２は、線形計画法（ILP）により目的関数を最小化する波長パスの経路・波長pijwsdを求め、再配置対象の波長パスの経路・波長と、再配置先の波長パスの経路・波長とを再配置対象パス管理データベース１０３に保存する。なお、再配置対象の波長パスは、再配置前の波長パスの経路・波長と、前記波長パス事前設計機能部から算出された波長パスの経路・波長pijwsdとの比較により抽出することができる。具体的には、図９に示すように、再配置前後の波長・経路が異なる場合（λ１、λ３、λ５、λ６）、再配置対象の波長パスとなり、再配置前後の波長・経路が同じである場合（λ２、λ４）、再配置対象の波長パスとはならない。
【００９２】
次に、波長パス収容順序決定機能部１０４は、波長パス収容順序決定機能部１０４における再配置対象の波長パスの収容順序を決定する。ここでは、波長パス収容順序決定機能部１０４は、空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更することができる収容順序を事前に決定する。具体的には、波長パス収容順序決定機能部１０４は、再配置対象の波長パスを再配置先の波長パスに変更する際に、再配置先に既に波長パスが存在するか否かを判別し、既に波長パスが存在する場合、その波長パスを空き波長に退避させることにより、再配置対象の波長パスを再配置先の波長パスに変更することができる収容順序を決定する。波長パス収容順序決定機能部１０４における収容順序決定手順について、図１０を用いて説明する。
【００９３】
波長パス事前設計機能部１０２で算出されて再配置対象パス管理データベース１０３に保存された再配置対象の波長パスの数をNとしたときに、N!通りの収容順序が考えられる。波長パス収容順序決定部１０４は、このN!通りの収容順序のそれぞれについて、空き波長を用いて再配置対象の波長パスを再配置先の波長パスに変更可能であるか否かを判別し、変更可能である収容順序jを収容順序管理データベース１０５に出力する。なお、再配置対象の波長パスの経路・波長と、再配置先の波長パスの経路・波長とは、再配置対象パス管理データベース１０３に保存されている。更に、空き波長（各リンクにおける空き波長リソース数、各リンクにおける空き波長番号）は、既存パス管理データベース１０１内に、空き波長情報として保存されている。
【００９４】
まず、ステップＳ１０１において、再配置先のN本の波長パスにおいて、再配置する波長の順番i(1≦i≦N)の全ての組み合わせj（1≦j≦N!）を求める。例えば、図９に示す例では、N=4である。４本の波長を再配置する収容順序は、4!=24通り考えられる。従って、ステップＳ１０１では、4本の波長（λ１、λ３、λ５、λ６）を再配置する収容順序の全ての組み合わせ(1,2,3,4),(1,2,4,3,),(1,3,2,4),...(4,3,2,1)を求め、順にj=1,2,...24とする。
【００９５】
ステップＳ１０２において、再配置する波長の収容順序の組み合わせj=1から計算をする。
【００９６】
ステップＳ１０３において、通信網内全てのリンクlに関して、リンクlの空き波長の使用数Ul=０とする。そして、再配置する波長の順番i=1とする。
【００９７】
ステップＳ１０４において、R0,ijをjの収容順序におけるi番目の再配置対象の波長パスの経路情報とし、W0,ijをjの収容順序におけるi番目の再配置対象の波長パスの波長番号とし、Rijをjの収容順序におけるi番目の再配置先の波長パスの経路情報とし、Wijをjの収容順序におけるi番目の再配置先の波長パスの波長番号としたときに、経路R0,ij・波長W0,ijの波長パスの再配置先の経路Rij・波長Wijに既存波長パスが存在するか否かを判別する。既存波長パスが存在する場合には、ステップＳ１０５に進み、既存波長パスが存在しない場合には、ステップＳ１１２に進む。
【００９８】
ステップＳ１０５において、再配置先の波長パスが既存波長パスに使用されているため、既存波長パスに使われている波長Wijを、一時的に空き波長Wc,ijに退避させる。具体的には、リンクlにおける空き波長数をClとし、Wijに既存波長パスが存在していたときのWijの変更先の波長番号をWc,ijとすると、Clの空き波長の中から変更先の波長番号Wc,jiを見つけ、既存波長パスに使われている波長Wijを、経路Rijの変更先の波長Wc,ijに変更する。そして、Rijの全てのリンクにおいてUl→Ul+１とする。
【００９９】
ステップＳ１０６において、通信網内全てのリンクに関して、ClとUlとを比較する。Cl≧Ulである場合、既存波長パスに使われている波長Wijを、一時的に空き波長Wc,ijに退避させることができるため、ステップＳ１０７に進み、Cl＜Ulである場合、ステップＳ１０９に進む。
【０１００】
ステップＳ１０７において、jの収容順序における最後の順番の波長まで計算したか否かを判別する（i=N ?）。i=Nの場合、最後の順番の波長まで計算したことになり、ステップＳ１０８に進む。i≠Nの場合、最後の順番の波長まで計算していないため、ステップＳ１１４に進む。
【０１０１】
ステップＳ１０８において、再配置する波長の収容順序jを出力する。
【０１０２】
ステップＳ１０９において、再配置する波長の順序の全ての収容順序の組み合わせの計算が終了したか否かを判別する（j=N! ?）。ｊ=N!の場合、全ての収容順序の組み合わせの計算が終了したことになり、収容順序決定手順が終了する。このとき再配置が不可能となるため、波長パス事前設計機能部において例えば数式(8)の制約を用いて再度計算を行う必要がある。j≠N!の場合、全ての収容順序の組み合わせの計算が終了していないため、ステップＳ１１０に進む。
【０１０３】
ステップＳ１１０において、ステップS105で変更した波長情報を初期化する。すなわち、経路Rijの変更先の波長Wc,ijに変更された波長を元の波長Wijに戻す。
【０１０４】
ステップＳ１１１において、j→j+1とし、ステップＳ１０３に戻る。
【０１０５】
ステップＳ１１２において、再配置対象の波長パスに使用されている波長W0,ijがステップＳ１０５で変更した波長Wc,ijであるか否かを判別する。波長W0,ijが波長Wc,ijである場合、ステップＳ１１３において、Wc,ijにおける経路Rijの全てのリンクにおいてUl→Ul−1とし、空き波長数Clを１つ増やす（Cl→Cl−1）、ステップＳ１１４に進む。波長W0,ijが波長Wc,ijでない場合、ステップＳ１１４に進む。
【０１０６】
ステップＳ１１４において、i→i+1とし、ステップＳ１０４に戻る。
【０１０７】
以上から、波長パスの収容順序が決定され、収容順序jは、収容順序管理データベース１０５に保存される。また、図１０の収容順序決定手順は、収容順序jのときにどの空き波長を用いて再配置対象の波長パスを再配置先の波長パスに変更できるかも示している。
【０１０８】
また、ステップＳ１０５とステップＳ１０６との間に以下のステップＳ１０５−２を加え、ステップＳ１０７とステップＳ１０８との間に以下のステップＳ１０７−２を加えることで、最小の空きリソースを使用して波長パスを再配置することが可能となる。
【０１０９】
ステップＳ１０５−２において、各リンクの使用リソースUlの合計使用リソースΣUlを計算し、jの収容順序における合計使用リソース数ΣUlを保存する。
【０１１０】
ステップＳ１０７において、jの収容順序における最後の順番の波長まで計算したか否かを判別する（i=N ?）。i=Nの場合、最後の順番の波長まで計算したことになり、ステップＳ１０７−２に進む。i≠Nの場合、最後の順番の波長まで計算していないため、ステップＳ１１４に進む。この場合、ステップＳ１１４において、i→i+1とし、ステップＳ１０３に戻る。
【０１１１】
ステップＳ１０７−２において、全ての収容順序の組み合わせjについて計算が終了したか否かを判別する（j=N! ?）。j=N!の場合、全ての収容順序の組み合わせjについて計算が終了したことになり、ステップ１０８において、ステップＳ１０５−２で保存したUlが最小値の場合の収容順序jを出力する。j≠N!の場合、全ての収容順序の組み合わせjについて計算が終了していないため、ステップＳ１０３に戻る。
【０１１２】
次に、パス設定機能部１０６は、波長パス収容順序決定機能部１０４で決定された収容順序jに基づいて、波長パスを設定する。パス設定機能部１０６における波長パス設定手順について、図１１を用いて説明する。ここで、パス設定機能部１０６は、空き波長を用いて再配置対象の波長パスを再配置先の波長パスに変更する。なお、再配置対象の波長パスの経路・波長と、再配置先の波長パスの経路・波長とは、再配置対象パス管理データベース１０３に保存されている。更に、空き波長（各リンクにおける空き波長番号）は、既存パス管理データベース１０１内に、空き波長情報として保存されている。更に、上位レイヤパスの収容先の波長パスの経路・波長情報と、上位レイヤパスの粒度とは、既存パス管理データベース１０１に保存されている。
【０１１３】
ステップＳ２０１において、波長パス収容順序決定機能部１０４で決定された収容順序jを取得する。まず、i=1とする。
【０１１４】
ステップＳ２０２において、R0,ijをjの収容順序におけるi番目の再配置対象の波長パスの経路情報とし、W0,ijをjの収容順序におけるi番目の再配置対象の波長パスの波長番号とし、Rijをjの収容順序におけるi番目の再配置先の波長パスの経路情報とし、Wijをjの収容順序におけるi番目の再配置先の波長パスの波長番号としたときに、経路R0,ij・波長W0,ijの波長パスの再配置先の経路Rij・波長Wijに既存波長パスが存在するか否かを判別する。既存波長パスが存在する場合には、ステップＳ２０８に進み、既存波長パスが存在しない場合には、ステップＳ２０３に進む。
【０１１５】
ステップＳ２０３において、再配置先の波長パスが空き波長であるため、再配置先の波長パスの経路Rij・波長Wijを用いて波長パスを設定する。
【０１１６】
ステップＳ２０４において、再配置対象の波長パスに収容されている上位レイヤパスと同じ粒度（及びクライアント情報）の上位レイヤパスを、ステップＳ２０３において設定した再配置先の波長パスに収容する。
【０１１７】
ステップＳ２０５において、経路R0,ij・波長W0,ijの再配置対象の波長パスを削除する。
【０１１８】
ステップＳ２０６において、全ての再配置対象の波長パスの再配置が終了したか否かを判別する。全ての再配置が終了した場合には、波長パス設定手順が終了する。全ての再配置が終了していない場合には、ステップＳ２０７において、i→i+1とし、ステップＳ２０２に戻る。
【０１１９】
ステップＳ２０８において、再配置先の波長パスが既存波長パスに使用されているため、既存波長パスに使われている波長Wijを、一時的に空き波長Wc,ijに退避させる。具体的には、空き波長Wc,ijに波長パスを設定する。
【０１２０】
ステップＳ２０９において、再配置先の経路Rij・波長Wijに存在している波長パスに収容されている上位レイヤパスと同じ粒度（及びクライアント情報）の上位レイヤパスをステップＳ２０８で設定した波長パスに収容する。
【０１２１】
ステップＳ２１０において、再配置先で既存波長パスに使われている経路Rij・波長Wijの波長パスを削除する。
【０１２２】
ステップＳ２１１において、波長Wijを波長Wc,ijに変更したため、既存波長パスに使われている波長Wijを、経路Rijの変更先の波長Wc,ijに変更すると共に、空き波長番号を更新する。そして、ステップＳ２０２に戻る。
【０１２３】
以上の波長パスの再配置の概要図を図１２に示す。図９を用いて説明したように、再配置対象の波長パスは、λ１、λ３、λ５、λ６の４本である。再配置対象の波長パス（λ６）の再配置先の波長パスが使用されていない場合、この波長パスは、再配置先の波長パスに変更することができる。従って、再配置先の波長パスを設定し、再配置対象の波長パス（λ６）に収容されている上位レイヤパスを、再配置先の波長パスに収容する。上位レイヤパスの収容が終了すると、再配置対象の波長パス（λ６）を削除する。
【０１２４】
しかし、再配置対象の波長パス（λ５）の再配置先の波長パスが既存波長パスに使用されている場合、既存波長パス（λ２）を空き波長（λ７）に退避させる。既存波長パス（λ２）と同じ経路の波長パスを空き波長（λ７）に設定し、既存波長パス（λ２）に収容されている上位レイヤパスを空き波長に設定された波長パス（λ７）に収容する。上位レイヤパスの収容が終了すると、既存波長パス（λ２）を削除する。その後、再配置対象の波長パス（λ５）を再配置先の波長パスに変更する。同様に、再配置先の波長パスを設定し、再配置対象の波長パス（λ５）に収容されている上位レイヤパスを、再配置先の波長パスに収容する。上位レイヤパスの収容が終了すると、再配置対象の波長パス（λ５）を削除する。空き波長に設定された波長パス（λ７）を再配置対象の波長パスとして、上記の処理を繰り返すことで、再配置対象の波長パスを再配置先の波長パスに無瞬断で変更することができる。
【０１２５】
次に、集中制御方式の場合に、管理装置１０からノード装置２０に対して波長パスを設定するシーケンス図を図１３に示す。
【０１２６】
ステップＳ３０１において、管理装置１０は、再配置対象の波長パスに対する再配置先の波長パスの経路・波長を決定し、始点ノードにリソース割当メッセージを送信する。ステップＳ３０２において、始点ノードは送信されてきた経路・波長情報に基づいてクロスコネクト（ＸＣ）の設定を行い、通信路設定完了通知を管理装置１０に送信する。同様に、ステップＳ３０３及びＳ３０４において、中継ノード及び終点ノードでＸＣの設定を行う。
【０１２７】
ステップＳ３０５において、終点ノードでの通信路設定完了通知の受信を契機に、再配置対象の波長パスの上位レイヤパスを再配置先波長パスに収容するため、始点ノードに上位レイヤパス設定メッセージを送信する。ステップＳ３０６において、始点ノードの波長パス選択機能部２０５は、再配置先の波長パスを選択し、信号複製機能部２０３で複製された上位レイヤパスの信号を再配置先の波長パスに収容する。全ての上位レイヤパスの収容が終了すると、始点ノードは、波長パス選択完了通知を管理装置に送信する。同様に、ステップＳ３０７において、終点ノードで再配置先の波長パスを選択し、上位レイヤパスの信号を再配置先の波長パスに収容して上位レイヤパスを開通させる。
【０１２８】
ステップＳ３０８において、全ての上位レイヤパスの波長パス選択完了通知の受信を契機に、管理装置１０は、通信路削除メッセージを始点ノード、中継ノード及び終点ノードに送信する。ステップＳ３０９、Ｓ３１０及びＳ３１１において、それぞれ始点ノード、中継ノード及び終点ノードは、ＸＣを削除し、通信路削除完了通知を管理装置１０に送信する。このようにして、再配置対象の波長パスの再配置が終了する。
【０１２９】
なお、再配置対象の波長パスを再配置先の波長パスに変更する際に、再配置先の波長パスに既存波長パスが存在する場合にも、図１３と同様にして再配置対象の波長パスを既存波長パスに変更することができる。
【０１３０】
次に、分散制御方式の場合に波長パスを設定するシーケンス図を図１４に示す。
【０１３１】
ステップＳ４０１において、始点ノードは、再配置対象の波長パスに対する再配置先の波長パスの経路・波長を決定する。ステップＳ４０２において、始点ノードは、再配置先の波長のリソース予約を行い、中継ノードのリソースを予約するため、通信路設定メッセージを中継ノードに送信する。ステップＳ４０３において、中継ノードも同様に、再配置先の波長のリソース予約を行い、終点ノードのリソースを予約するため、通信路設定メッセージを終点ノードに送信する。ステップＳ４０４において、終点ノードは、再配置先の波長のリソース予約を行い、ステップＳ４０５において、ＸＣの設定を行う。ＸＣの設定が終了すると、リソース割当メッセージを中継ノードに送信する。ステップＳ４０６において、中継ノードは、ＸＣの設定を行い、リソース割当メッセージを始点ノードに送信する。ステップＳ４０７において、始点ノードはＸＣの設定を行う。
【０１３２】
ステップＳ４０８において、始点ノードでのＸＣの設定完了を契機に、再配置先波長パスへの上位レイヤパスの収容を開始する。ステップＳ４０９において、始点ノードの波長パス選択機能部２０５は、再配置先の波長パスを選択し、信号複製機能部２０３で複製された上位レイヤパスの信号を再配置先の波長パスに収容する。全ての上位レイヤパスの収容が終了すると、始点ノードは、上位レイヤパス設定メッセージを終点ノードに送信する。同様に、ステップＳ４１０において、終点ノードで再配置先の波長パスを選択し、上位レイヤパスの信号を再配置先の波長パスに収容して上位レイヤパスを開通させる。全ての上位レイヤパスの収容が終了すると、終点ノードは、波長パス選択完了通知を始点ノードに送信する。
【０１３３】
ステップＳ４１１において、始点ノードは、波長パス選択完了通知の受信を契機に、再配置対象の波長パスの削除を開始する。ステップＳ４１２において、始点ノードは、再配置対象の波長パスのリソースを開放するためのスケジュールを生成し、通信路削除メッセージを中継ノードに送信する。ステップＳ４１３において、通信路削除メッセージ中継ノードを受信した中継ノードも同様に、再配置対象の波長パスのリソースを開放するためのスケジュールを生成し、通信路削除メッセージを終点ノードに送信する。ステップＳ４１４において、通信路削除メッセージ中継ノードを受信した終点ノードも、再配置対象の波長パスのリソースを開放するためのスケジュールを生成する。ステップＳ４１５において、終点ノードは、スケジュールに従ってＸＣを削除し、リソース開放メッセージを中継ノードに送信する。ステップＳ４１６において、中継ノードも、ＸＣを削除し、リソース開放メッセージを始点ノードに送信する。ステップＳ４１７において、始点ノードもＸＣを削除する。このようにして、再配置対象の波長パスの再配置が終了する。
【０１３４】
なお、再配置対象の波長パスを再配置先の波長パスに変更する際に、再配置先の波長パスに既存波長パスが存在する場合にも、図１４と同様にして再配置対象の波長パスを既存波長パスに変更することができる。
【０１３５】
＜第２の実施形態＞
第２の実施形態では、波長パスを再配置する場合、波長パス収容順序決定機能部１０４が、より簡単に収容順序を決定する収容順序決定手順について、図１５を用いて説明する。
【０１３６】
波長パス収容順序決定機能部１０４は、N本の再配置対象の波長パスのうち再配置先に既存の波長パスが存在していない波長M本を抽出する。例えば、図９の場合、再配置対象の波長パスλ７は、再配置先に既存の波長パスが存在しない。他の再配置対象の波長パスは、再配置先に既存の波長パスが存在する。従って、図９の場合、M=1である。このM本は、再配置先の波長パスにそのまま変更することができるため、収容順序決定手順における波長の順列数を削減することができる。
【０１３７】
より具体的には、ステップＳ５０１において、N−M本の波長パスのうち、再配置する波長の順番i=1とする。
【０１３８】
ステップＳ５０２において、R0,iをi番目の再配置対象の波長パスの経路情報とし、W0,iをjのi番目の再配置対象の波長パスの波長番号とし、Riをi番目の再配置先の波長パスの経路情報とし、Wiをi番目の再配置先の波長パスの波長番号としたときに、経路R0,i・波長W0,iの波長パスの再配置先の経路Ri・波長Wiに既存波長パスが存在するか否かを判別する。既存波長パスが存在する場合には、ステップＳ５０５において、i→i+1とし、ステップＳ５０２に戻る。既存波長パスが存在しない場合には、ステップＳ５０３に進む。
【０１３９】
ステップＳ５０３において、再配置先の波長パスが空き波長であるため、経路R0,i・波長W0,i及び波長番号iを収容順序管理データベース１０５に保存する。
【０１４０】
ステップＳ５０４において、全ての再配置対象の波長パスの収容順序を決定したか否かを判別する（i=N−M ?）。全ての再配置対象の波長パスの収容順序を決定していない場合、ステップＳ５０５において、i→i+1とし、ステップＳ５０２に戻る。決定した場合、収容順序決定手順が終了する。
【０１４１】
これを全ての再配置する波長の順番の組み合わせjについて計算する。
【０１４２】
以上のステップから、波長パスの収容順序が決定される。前述のように、第２の実施形態における再配置する波長の順番iの範囲は1≦i≦N−Mであり、再配置する波長の順番の組み合わせjの範囲は1≦j≦(N−M)!となる。
【０１４３】
＜第３の実施形態＞
第３の実施形態では、波長パスを再配置する場合について説明する。第３の実施形態では、第１の実施形態における波長パス事前設計機能部１０２で計算された波長パスの経路及び波長を用いて、収容順序を決定せずに、パス設定機能部１０６が波長パス及び上位レイヤパスを設定／削除する。例えば、空き波長が多く存在することが分かっている場合には、収容順序を決定する必要なく、再配置対象の波長パスを再配置先の波長パスに変更することができる。このような場合に、パス設定機能部１０６は、事前に収容順序を決定せずに、逐次的に波長パスを再配置することができる。
【０１４４】
図１６は、第３の実施形態に係る管理装置であり、図３の管理装置から波長パス収容順序決定機能部１０４及び収容順序管理データベース１０５を省いた装置である。
【０１４５】
波長パス事前設計機能部１０２における波長パスの再配置先の設計方法は、第１の実施形態と同じである。パス設定機能部１０６は、波長パス事前設計機能部１０２において計算されたN本の再配置対象の波長パスのうち、波長番号iが小さい順又は大きい順にパスを設定する。より具体的には、図１１のステップＳ２０１を、「N本の再配置対象の波長パスのうち、波長番号iが小さい順又は大きい順に波長パスを設定する」と変更すればよい。また、図１１の各ステップにおいてjが用いられないため、経路R0,ij・波長W0,ijを経路R0,i・波長W0,iに、経路Rij・波長Wijを経路Ri・波長Wiに変更する。管理装置１０からノード装置２０に対して波長パスを設定するシーケンス図は、図１３及び図１４と同じである。
【０１４６】
＜第４の実施形態＞
第４の実施形態では、波長パスを再配置する場合について説明する。第４の実施形態では、第１の実施形態における波長パス事前設計機能部１０２で計算された波長パスの経路及び波長を用いて、収容順序を決定せずに、パス設定機能部１０６が波長パス及び上位レイヤパスを設定／削除する。例えば、空き波長が再配置対象のパスの数より多い場合には、収容順序を決定する必要なく、再配置対象の波長パスを再配置先の波長パスに変更することができる。このような場合に、パス設定機能部１０６は、事前に収容順序を決定せずに、逐次的に波長パスを再配置することができる。第４の実施形態に係る管理装置も、図１６と同様の構成になる。
【０１４７】
第４の実施形態では、例えば図１７に示すように、再配置対象の波長パス（λ１、λ３、λ５、λ６）を空き波長（λ７、λ８、λ９、λ１０）に設定する。このとき、上位レイヤパスも空き波長に設定した波長パスに収容する。次に、再配置対象の波長パス（λ１、λ３、λ５、λ６）を削除する。そして、再配置先の波長パスを設定し、上位レイヤパスを再配置先の波長パスに収容する。最後に、空き波長に設定した波長パス（λ７、λ８、λ９、λ１０）を削除する。
【０１４８】
パス設定機能部１０６における波長パス設定手順について、図１８を用いて説明する。
【０１４９】
ステップＳ６０１において、波長パス事前設計機能部１０２からN本の再配置対象の波長パスを取得する。前述のように、N本の再配置対象の波長パスは、再配置前の波長パスの経路・波長と、波長パス事前設計機能部１０２で計算された波長パスの経路・波長との比較により取得できる。
【０１５０】
ステップＳ６０２において、空き波長にＮ本の波長パスを設定する。
【０１５１】
ステップＳ６０３において、再配置対象の波長パスに収容されている上位レイヤパスをステップＳ６０２で設定された波長パスに収容する。
【０１５２】
ステップＳ６０４において、再配置対象の波長パスを削除する。
【０１５３】
ステップＳ６０５において、波長パス事前設計機能部１０２で計算された波長パスの経路・波長を用いて、N本の再配置先の波長パスを設定する。
【０１５４】
ステップＳ６０６において、ステップＳ６０５で設定した波長パスにステップＳ６０３で設定した上位レイヤパスを収容する。
【０１５５】
ステップＳ６０７において、ステップＳ６０２で設定した波長パスを削除する。
＜第４の実施形態の変形例＞
第４の実施形態の変形例では、波長パスを再配置する場合について説明する。第４の実施形態の変形例ではまず、第１の実施形態における波長パス事前設計機能部１０２で数式(1)〜(5)を用いて計算する。計算結果から各リンクの空き波長を求めることができるので、それを用いて数式(18)の制約を加えて波長パス事前設計機能部１０２で再度計算する。
【０１５６】
【数１１】
ここでCijはリンクijの空き波長である。前記計算結果は、変更する波長よりも空き波長のほうが大きくなるため、確実に波長パスの再配置を実行することが可能となる。
【０１５７】
パス設定機能部１０６における波長パス設定手順については第４の実施形態と同じなので省略する。
【０１５８】
＜第５の実施形態＞
第５の実施形態では、波長パスを再配置する場合について説明する。第５の実施形態では、再配置対象及び再配置先の波長パスを事前に設計せずに、パス設定機能部１０６が波長パス及び上位レイヤパスを設定／削除する。例えば、通信網が複雑でない場合には、再配置対象の波長パスを逐次的に再配置することができる。
【０１５９】
図１９は、第５の実施形態に係る管理装置であり、図４の管理装置から波長パス事前設計機能部１０２、再配置対象パス管理データベース１０３、波長パス収容順序決定機能部１０４及び収容順序管理データベース１０５を省いた装置である。
【０１６０】
第５の実施形態では、例えば図２０に示すように、パス設定機能部１０６は、使用波長領域数内の波長番号の小さい順又は大きい順に未使用の空き波長の経路を検索する。検索された空き波長（λ１、λ４）が再配置予定場所になる。この再配置予定場所（λ１）に収容できる波長パスを波長番号の小さい順又は大きい順に検索する。再配置予定場所（λ１）に収容できる波長パス（λ５）が存在する場合、この波長パスを再配置対象の波長パスとし、再配置予定場所に設定する。このとき、再配置対象の波長パスに収容されている上位レイヤパスを、再配置予定場所に設定した波長パスに収容する。そして、再配置対象の波長パス（λ５）を削除する。この手順を使用波長領域数内の全ての波長番号に関して繰り返すことにより、再配置が完了する。
【０１６１】
＜第６の実施形態＞
第６の実施形態では、上位レイヤパスを再配置する場合について説明する。
【０１６２】
図２１は、本発明の第６の実施形態に係る管理装置３０のブロック図である。管理装置３０は、既存パス管理データベース３０１と、上位レイヤパス事前設計機能部３０２と、再配置対象パス管理データベース３０３と、パス設定機能部３０６と、制御信号送受信インタフェース３０７とを有する。
【０１６３】
既存パス管理データベース３０１は、通信網内に設定された既存波長パスの経路・波長情報と、通信網内の各リンクの空き波長情報と、上位レイヤパスの収容先の波長パスの経路・波長情報と、各上位レイヤパスの粒度とを管理する。既存パス管理データベース３０１は、クライアント情報（どの上位レイヤパスがどのクライアントに対応するかという情報）を管理してもよい。
【０１６４】
上位レイヤパス事前設計機能部３０２は、既存パス管理データベース３０１で管理されている情報を用いて、再配置対象の上位レイヤパスと、再配置先の上位レイヤパスとを事前に設計する。再配置先の上位レイヤパスの設計方法は、後述する。
【０１６５】
再配置対象パス管理データベース３０３は、上位レイヤパス事前設計機能部３０２から得られた再配置対象の上位レイヤパス（再配置する必要のある上位レイヤパスの再配置前の上位レイヤパス）の経路・波長と、再配置先の上位レイヤパス（再配置する必要のある上位レイヤパスの再配置後の上位レイヤパス）の経路・波長とを保存する。
【０１６６】
パス設定機能部３０６は、波長パス及び上位レイヤパスを設定／削除する。具体的には、パス設定機能部３０６は、波長パス及び上位レイヤパスの設定／削除を指示するため、制御信号送受信インタフェース３０７を介してリソース割当メッセージ、通信路設定メッセージ又は通信路削除メッセージをノード装置に送信する。また、パス設定機能部３０６は、上位レイヤパスの収容先波長パスの設定／削除を指示するため、制御信号送受信インタフェース３０７を介して上位レイヤパス設定メッセージをノード装置に送信する。なお、パス設定機能部２０６は、波長パス及び上位レイヤパスのリソースの予約（割当）又は開放（削除）情報を保存するためのリソース管理データベース（図示せず）を有してもよい。
【０１６７】
制御信号送受信インタフェース３０７は、制御信号をノード装置に送信し、また、ノード装置から制御信号を受信する。
【０１６８】
なお、ノード装置は、第１の実施形態と同じである。
【０１６９】
次に、上位レイヤパス事前設計機能部３０２における上位レイヤパスの再配置先の設計方法について説明する。この設計方法は、オフラインで事前に設計されてもよい。ここでは、整数線形計画法（ILP：integer linear programming）を用いて、再配置先の上位レイヤパスの経路を事前に設計する。
【０１７０】
上位レイヤパス事前設計機能部３０２は、以下の目的関数を最小化する波長パスの経路を計算する。
【０１７１】
【数１２】
この目的関数(11)は、通信網内で使用されている波長数（網内波長総数）を最小化するための関数である。ただし、pijwsdは、波長wが使用されているか否かを示す変数であり、始点sから終点dまでの各物理リンク(i,j)において、波長wが使用されている場合はpijwsd=1であり、波長wが使用されていない場合はpijwsd=0である。Vはノードの集合であり、Eはリンクの集合であり、Wは波長の集合（w=0,1,2,3,...,WMAX）であり、WMAXは最大波長多重数であり、これらは予め決められたパラメータである。また、pijwsdを通信装置の設備数もしくは通信装置コストとしてもよい。
【０１７２】
目的関数(11)の計算にあたり、以下の制約条件を用いる。
【０１７３】
【数１３】
【０１７４】
【数１４】
【０１７５】
【数１５】
【０１７６】
【数１６】
制約条件(12)は、始点s、終点d及び上位レイヤパスaにおいて各リンクのトラヒックフローを表す方程式（非特許文献２参照）である。ただし、Aは上位レイヤパスの集合であり、Uijasdは、上位レイヤパスaが使用されているか否かを示す変数であり、始点sから終点dまでの各物理リンク(i,j)において、上位レイヤパスaが使用されている場合はUijasd=1であり、上位レイヤパスaが使用されていない場合はUijasd=0である。また、δasdは、始点sから終点dまでの経路で上位レイヤパスaが使用されているか否かを示す。δasd=0の場合、始点sから終点dまでの経路で上位レイヤパスaが使用されていないことを示し、δasd=1の場合、始点sから始点dまでの経路で上位レイヤパスaが使用されていることを示す。また、i＜jのときΣUijwsd=ΣUijwsd、i＞jのときΣUijwsd=−ΣUjiwsdとなる。
【０１７７】
制約条件(13)は、各リンク内の上位レイヤパスの粒度の和が波長パスの容量以下とする条件である。ただし、Gaは上位レイヤパスaの粒度であり、Cijはリンク(i,j)における容量である。Gaは、既存パス管理データベース３０１内に保存された上位レイヤパスの粒度から予め求められる。
【０１７８】
制約条件(14)は、再配置後に使用される波長パス数が既存の波長パス数以下とする条件である。ただし、p0ijwsdは、再配置前に波長wが使用されているか否かを示す変数であり、始点sから終点dまでの各物理リンク(i,j)において、再配置前に波長wが使用されている場合はp0ijwsd=1であり、再配置前に波長wが使用されていない場合はp0ijwsd=0である。p0ijwsdは、既存パス管理データベース３０１内に、通信網内に設定された既存波長パスの経路・波長情報として保存されている。
【０１７９】
制約条件(15)は、始点sから終点dまでの経路で使用される上位レイヤパスの合計数が、始点sから終点dまでの上位レイヤパスの需要総数Dupper_trafficsdに等しいという条件である。ただし、Dupper_trafficsdは、始点sから終点dまでの上位レイヤパスの総数であり、既存パス管理データベース３０１内に保存された通信網内に設定された既存波長パスの経路・波長情報と、上位レイヤパスの収容先の波長パスの経路・波長情報とから予め求められる。
【０１８０】
制約条件(12)〜(15)を用いて目的関数(11)を計算することにより、再配置後の上位レイヤパスの経路Uijasdが出力される。
【０１８１】
制約条件(12)〜(15)に加えて、次の制約条件(16)〜(17)のうち１つ以上が用いられてもよい。
【０１８２】
【数１７】
【０１８３】
【数１８】
制約条件(16)は、再配置対象の上位レイヤパスの数が既存の上位レイヤパスの合計数のうち所定の割合Rを超えないようにする条件である。すなわち、制約条件(16)は、再配置対象の上位レイヤパスの数が所定の閾値を超えないようにする条件である。ただし、Rは再配置する上位レイヤパスの割合であり、予め決められたパラメータである。また、U0ijasdは、再配置前に上位レイヤパスaが使用されているか否かを示す変数であり、始点sから終点dまでの各物理リンク(i,j)において、再配置前に上位レイヤパスaが使用されている場合はU0ijasd=1であり、再配置前に上位レイヤパスaが使用されていない場合はU0ijasd=0である。U0ijasdは、既存パス管理データベース３０１内に、通信網内に設定された既存波長パスの経路・波長情報と、上位レイヤパスの収容先の波長パスの経路・波長情報とから予め求められる。
【０１８４】
制約条件(17)は、再配置前の始点sから終点dの経路ホップ数と再配置後の経路ホップ数との差が遅延差又は距離差の限界Hdelayを満たすホップ数以下であるとする条件である。ただし、Hdelayは、許容される最大の遅延差又は距離差を満たすホップ数であり、予め決められたパラメータである。
【０１８５】
制約条件(16)を用いることにより、再配置対象の上位レイヤパスの数を制限することができる。また、制約条件(17)を用いることにより、パスを切り替える際のバッファメモリの許容範囲内での経路選択が可能になる。
【０１８６】
上位レイヤパス事前設計機能部３０２は、線形計画法（ILP）により目的関数を最小化する上位レイヤパスの経路Uijasdを求め、再配置対象の上位レイヤパスの経路と、再配置先の上位レイヤパスの経路とを再配置対象パス管理データベース３０３に保存する。なお、再配置対象の上位レイヤパスは、再配置前の上位レイヤパスの経路と、目的関数を最小化する上位レイヤパスの経路との比較により抽出することができる。
【０１８７】
パス設定機能部３０６は、再配置対象の上位レイヤパスを再配置先の上位レイヤパスに変更する。なお、波長パスとは異なり、上位レイヤパスの場合収容順序は予め決定する必要はない。パス設定機能部３０６における上位レイヤパス設定手順について、図２２を用いて説明する。なお、再配置対象の上位レイヤパスの経路と、再配置先の上位レイヤパスの経路とは、再配置対象パス管理データベース３０３に保存されている。更に、上位レイヤパスの粒度は、既存パス管理データベース３０１に保存されている。
【０１８８】
まず、ステップＳ７０１において、N本の再配置対象の上位レイヤパスの収容順序を任意の順番で決定する。なお、上位レイヤパスの収容順序は、波長の小さい順番又は大きい順序に決定されてもよい。N本の上位レイヤパスのうち、再配置する上位レイヤパスの順番i=1とする。
【０１８９】
ステップＳ７０２において、再配置対象の上位レイヤパスと同じ上位レイヤパスを再配置先に設定する。
【０１９０】
ステップＳ７０３において、再配置対象の上位レイヤパスを削除する。
【０１９１】
ステップＳ７０４において、全ての再配置対象の上位レイヤパスの再配置が終了したか否かを判別する（i=N ?）。再配置が終了していない場合（i≠N）、ステップＳ７０５において、i→i+1として、ステップＳ７０２に戻る。再配置が終了した場合（i≠N）、ステップＳ７０６に進む。
【０１９２】
ステップＳ７０６において、上位レイヤパスを収容していない波長パスが存在するか否かを判別する。存在する場合、ステップＳ７０７に進み、存在していない場合、上位レイヤパス設定手順が終了する。
【０１９３】
ステップＳ７０７において、上位レイヤパスを収容していない波長パスを削除する。
【０１９４】
次に、集中制御方式の場合に、管理装置３０からノード装置２０に対して上位レイヤパスを設定するシーケンス図を図２３に示す。
【０１９５】
ステップＳ８０１において、管理装置３０は、再配置対象の上位レイヤパスに対する再配置先の上位レイヤパスの経路を決定し、また、上位レイヤパスを収容する波長パスを決定する。管理装置３０は、始点ノードに上位レイヤパス設定メッセージを送信する。ステップＳ８０２において、始点ノードの波長パス選択機能部２０５は、送信されてきた経路情報に基づいて再配置先の波長パスを選択し、信号複製機能部２０３で複製された上位レイヤパスの信号を再配置先の波長パスに収容する。上位レイヤパスの収容が終了すると、始点ノードは、波長パス選択完了通知を管理装置に送信する。同様に、ステップＳ８０３において、終点ノードで再配置先の波長パスを選択し、上位レイヤパスの信号を再配置先の波長パスに収容して上位レイヤパスを開通させる。
【０１９６】
ステップＳ８０４において、全ての上位レイヤパスの波長パス選択完了通知の受信を契機に、管理装置３０は、再配置対象の上位レイヤパスを削除するため、上位レイヤパス削除メッセージを始点ノードに送信する。ステップＳ８０５において、始点ノードは、上位レイヤパスを削除し、上位レイヤパス削除完了通知を管理装置に送信する。
【０１９７】
ステップＳ８０６において、全ての上位レイヤパスの上位レイヤパス削除完了通知の受信を契機に、管理装置３０は、上位レイヤパスを収容していない波長パスを削除する。このため、管理装置３０は、通信路削除メッセージを始点ノード、中継ノード及び終点ノードに送信する。ステップＳ８０７、Ｓ８０８及びＳ８０９において、それぞれ始点ノード、中継ノード及び終点ノードは、ＸＣを削除し、通信路削除完了通知を管理装置３０に送信する。このようにして、再配置対象の上位レイヤパスの再配置が終了する。
【０１９８】
次に、分散制御方式の場合に上位レイヤパスを設定するシーケンス図を図２４に示す。
【０１９９】
ステップＳ９０１において、始点ノードは、再配置対象の上位レイヤパスに対する再配置先の上位レイヤパスの経路を決定し、また、上位レイヤパスを収容する波長パスを決定する。ステップＳ９０２において、始点ノードの波長パス選択機能部２０５は、決定された経路情報に基づいて再配置先の波長パスを選択し、信号複製機能部２０３で複製された上位レイヤパスの信号を再配置先の波長パスに収容する。上位レイヤパスの収容が終了すると、始点ノードは、上位レイヤパス設定メッセージを終点ノードに送信する。ステップＳ９０３において、同様に終点ノードで再配置先の波長パスを選択し、上位レイヤパスの信号を再配置先の波長パスに収容して上位レイヤパスを開通させる。終点ノードは、波長パスの選択が完了すると、波長パス選択完了通知を始点ノードに送信する。
【０２００】
ステップＳ９０４において、全ての上位レイヤパスの波長パス選択完了通知の受信を契機に、始点ノードは、再配置対象の上位レイヤパスの削除を開始する。ステップＳ９０５において、始点ノードは、再配置対象の上位レイヤパスを削除する。
【０２０１】
ステップＳ９０６において、全ての上位レイヤパスの上位レイヤパスの削除が完了すると、始点ノードは、上位レイヤパスを収容していない波長パスの削除を開始する。始点ノードは、再配置対象の波長パスのリソースを開放するためのスケジュールを生成し、通信路削除メッセージを中継ノードに送信する。ステップＳ９０７において、通信路削除メッセージ中継ノードを受信した中継ノードも同様に、再配置対象の波長パスのリソースを開放するためのスケジュールを生成し、通信路削除メッセージを終点ノードに送信する。ステップＳ９０８において、通信路削除メッセージ中継ノードを受信した終点ノードも、再配置対象の波長パスのリソースを開放するためのスケジュールを生成する。ステップＳ９０９において、終点ノードは、スケジュールに従ってＸＣを削除し、リソース開放メッセージを中継ノードに送信する。ステップＳ９１０において、中継ノードも、ＸＣを削除し、リソース開放メッセージを始点ノードに送信する。ステップＳ９１１において、始点ノードもＸＣを削除する。このようにして、再配置対象の上位レイヤパスの再配置が終了する。
【０２０２】
なお、上位レイヤパスに更に上位レイヤパスが収容されている場合（例えば、３Ｇ上位レイヤパスに３本の１Ｇ上位レイヤパスが収容されている場合）、上記の数式(11)〜(17)の「波長パス」を「上位レイヤパス」に変更することで、複数の上位レイヤパスの再配置が可能になる。
【０２０３】
＜第７の実施形態＞
第７の実施形態では、上位レイヤパスを再配置する場合について説明する。第７の実施形態では、再配置対象及び再配置先の上位レイヤパスを事前に設計せずに、パス設定機能部３０６が上位レイヤパスを設定／削除する。例えば、通信網が複雑でない場合には、再配置対象の上位レイヤパスを逐次的に再配置することができる。
【０２０４】
図２５は、第７の実施形態に係る管理装置３０であり、図２１の管理装置３０から上位レイヤパス事前設計機能部３０２及び再配置対象パス管理データベース３０３を省いた装置である。
【０２０５】
パス設定機能部３０６における上位レイヤパス設定手順について、図２６を用いて説明する。
【０２０６】
ここでは、N本の波長パス内の上位レイヤパスを再配置するものとする。ステップＳ１００１において、波長パス内の使用帯域量が多い順番に波長を並び替え、順にiとする（1≦i≦N）。なお、波長パス内の使用帯域量は、波長パスに収容されている上位レイヤパスの粒度の合計である。更に、波長パス内の使用帯域量が少ない順番に波長を並び替え、順にjとする（1≦j≦N）。
【０２０７】
ステップＳ１００２において、j=1，i=1とする。
【０２０８】
ステップＳ１００３において、aj=1とする。ただし、ajは、j番目の波長パスに収容されている上位レイヤパスに順に付与された番号である。
【０２０９】
ステップＳ１００４において、j番目の波長パスに収容されている上位レイヤパスajと同じ経路であり、i番目の波長パス内の空き容量をCiとしたときに、Ci≧Cjを満たす波長パスをi番目の波長パスから検索する。なお、上位レイヤパスと同じ経路の波長パスとは、上位レイヤパスと同じ始点及び終点ノードを有する波長パスのことを言う。
【０２１０】
ステップＳ１００５において、上位レイヤパスajを収容可能な波長パスが存在するか否かを判別する。存在する場合、ステップＳ１００６に進み、存在しない場合、ステップＳ１００１に進む。
【０２１１】
ステップＳ１００６において、j番目の波長パスの上位レイヤパスajをi番目の波長パスに収容する。
【０２１２】
ステップＳ１００７において、j番目における全ての上位レイヤパスの収容の検索が完了したか否かを判別する。完了した場合、ステップＳ１００８に進み、完了していない場合、ステップＳ１０１３において、aj→aj+1として、ステップＳ１００４に戻る。
【０２１３】
ステップＳ１００８において、j番目の波長パスに収容されている上位レイヤパスが存在するかを判別する。存在しない場合、ステップＳ１００９に進み、存在する場合、ステップＳ１０１０に進む。
【０２１４】
ステップＳ１００９において、上位レイヤパスを収容していない波長パスを削除する。
【０２１５】
ステップＳ１０１０において、i+j=Nであるか否かを判別する。i+j=Nである場合、計算終了となる。i+j≠Nである場合、全ての波長パスを検索していないため、ステップＳ１０１４に進む。
【０２１６】
ステップＳ１０１１において、i+j=Nであるか否かを判別する。i+j=Nである場合、計算終了となる。i+j≠Nである場合、ステップＳ１０１２において、i→i+1として、ステップＳ１００４に戻る。
【０２１７】
以上の手順により、上位レイヤパスの再配置が終了する。
【０２１８】
＜第８の実施形態＞
第８の実施形態では、上位レイヤパスと波長パスとの双方の再配置を行う場合について説明する。
【０２１９】
まず、上位レイヤパスの再配置から行い、その後、波長パスの再配置を行う。これは、第１〜第５の実施形態と、第６〜第７の実施形態との組み合わせである。
【０２２０】
図２７は、第８の実施形態に係る管理装置であり、図４の管理装置と図２１の管理装置とを組み合わせた装置である。図４、図２１と同一構成部分には同一符号を付し、その説明を省略する。
【０２２１】
図２７の管理装置での上位レイヤパス及び波長パスの再配置手順を図２８に示す。
【０２２２】
ステップＳ１１０１において、上位レイヤパス事前設計機能部は、上位レイヤパスの再配置計算を行う。この具体的な手順は、第６〜第７の実施形態に示した通りである。
【０２２３】
ステップＳ１１０２において、再配置計算によって、削除可能な波長パスが存在するか否かを判別する。削除可能な波長パスが存在する場合、ステップＳ１１０３に進み、存在しない場合、ステップＳ１１０４に進む。
【０２２４】
ステップＳ１１０３において、上位レイヤパスを再配置する。この具体的な手順は、第６〜第７の実施形態に示した通りである。
【０２２５】
ステップＳ１００４において、波長パスを再配置する。この具体的な手順は、第１〜第５の実施形態に示した通りである。
【０２２６】
＜第９の実施形態＞
第９の実施形態では、波長パス収容順序決定機能部１０４において、再配置対象の波長パスを再配置先の波長パスに変更するためのオペレーション数を最小化する計算方法について説明する。
【０２２７】
オペレーション数を最小化するため、図１０を参照して説明した収容順序決定手順において、再配置対象の波長パスを再配置先の波長パスに変更するためのオペレーション数を求め、複数の収容順序が決定された場合、オペレーション数の少ない収容順序を選択する。
【０２２８】
図２９は、第９の実施形態に係る管理装置における収容順序決定手順を示す図である。第９の実施形態の基本的なステップは図１０と同じであるが、ステップＳ１０２'、Ｓ１０５'、Ｓ１１４'にオペレーション数の計算が追加され、ステップＳ１１５'及びＳ１１６'が新たに追加されている。
【０２２９】
ステップＳ１０２'において、オペレーション数p=０とする。
【０２３０】
ステップＳ１０５'において、既存パスに使われている波長を空き波長に変更する場合、オペレーション数p→p+2とする。オペレーション数が２回増える理由は、再配置先の波長を一度空き波長に退避させる必要があるためである。
【０２３１】
ステップＳ１１４'においてp→p+1とする。
【０２３２】
ステップＳ１０７においてi=Nの場合に、ステップ１１５'に進み、組み合わせjにおけるオペレーション数p[j]を１つ前のオペレーション数の計算結果P[j-1]と比較する。p[j]とP[j-1]とのうち値が小さいものをP[j-1]とし、その収容順序を保存し、値が大きいものに対応する収容順序は破棄する。
【０２３３】
ステップＳ１１６'において、全ての計算が終了した時点で最小のオペレーション数P[j-1]に対応する収容順序を出力する。
【０２３４】
このように、空き波長を用いて波長パスを再配置するための収容順序を決定する際に、オペレーション数が大きい収容順序を破棄することにより、オペレーション数を最小化することができると共に、計算メモリ量を削減することができる。
【０２３５】
＜第１０の実施形態＞
第１０の実施形態では、波長パスを再配置する場合について説明する。第１０の実施形態では、再配置対象及び再配置先の波長パスを事前に設計せずに、パス設定機能部１０６が波長パス及び上位レイヤパスを設定／削除する。例えば、通信網が複雑でない場合には、再配置対象の波長パスを逐次的に再配置することができる。第１０の実施形態に係る管理装置は、図１９と同様の構成になる。
【０２３６】
図３０は、第１０の実施形態に係る管理装置における波長パス設定手順を示す図である。
【０２３７】
まず、ステップＳ１２０１において、パス設定機能部１０６は、各リンクの波長割当状況を取得する。第１０の実施形態では、図３１に示すように、波長割当状況としてリンク毎の波長の使用／未使用を管理する。例えば、図３１（１）に示すような２×３の格子網の物理トポロジの場合、ノード０とノード１との間のリンク０−１において、波長λ０〜λ１０が使用されているか否かを管理する。波長が使用されている場合、波長パス識別番号も管理する。ここでは、図３１（２）のような波長割当状況を仮定する。ただし、行を波長とし、列をリンク番号とし、波長を使用しているリンクを網掛けで表し、使用していないリンクを空白で表し、枠内の番号を波長パス識別番号とする。例えば、λ２のパス識別番号２は、リンク１−２及びリンク２−５の経路を使用することがわかる。
【０２３８】
ステップＳ１２０２において、パス設定機能部１０６は、波長割当状況において、空き波長が少ない順に波長を並び替える。すなわち、波長を使用していないリンク数が少ない順に波長を並び替える。なお、波長を使用していないリンク数が大きい順に並び替えてもよい。
【０２３９】
ステップＳ１２０３において、パス設定機能部１０６は、空き波長が多い順に移設可能な波長パスを検索する。すなわち、波長を使用してないリンク数が大きい順に、波長パスを再配置先のリンクを検索する。
【０２４０】
ステップＳ１２０４において、検索された再配置先のリンクに波長パスを再配置する。
【０２４１】
ステップＳ１２０５において、上記の手順を移設可能な波長パスが存在しなくなるまで繰り返す。
【０２４２】
図３２は、第１０の実施形態に係る管理装置における波長パスの再配置を示す図である。
【０２４３】
図３２（１）に示すような波長割当状況は、波長を使用していないリンク数が少ない順に並び替えられる。例えば、波長λ２を使用していないリンク数は１であるため、波長割当状況の先頭に並び替えられる。この例では、波長は、λ２、λ３、λ７、λ１０、λ８、λ５の順に並び替えられる。なお、波長λ４、λ６、λ９及びλ１のように、全てのリンクで波長が使用されている場合には、再配置による波長数の削減は見込めないため、波長割当状況の最後に並び替えられてもよい。
【０２４４】
波長を使用していないリンク数が最も大きいものは波長λ５であるため、波長λ５を使用している波長パスの再配置先のリンクを検索する。波長λ５を使用している識別番号８の波長パスは、波長λ３に再配置することができ、波長λ５を使用している識別番号９の波長パスは、波長λ１０に再配置することができる。なお、識別番号１５の波長パスのように波長λ８を複数のリンクで使用している場合、これらの複数のリンクに共通して空きのある波長を検索して再配置する。この例では、識別番号１５の波長パスは、波長λ１０に再配置できる。これを繰り返すことにより、波長パスの再配置が終了する。
【０２４５】
＜第１１の実施形態＞
第１１の実施形態では、波長パス事前設計機能部１０２において、波長パスの再配置先を設計する際の整数線形計画法の計算量を削減する例について説明する。
【０２４６】
波長パス事前設計機能部１０２は、通信網内のいずれかのリンクで使用されている波長について、再配置対象の波長パスと、再配置先の波長パスとを設計する。すなわち、全てのリンクで使用されていない波長については、計算の対象から除外する。
【０２４７】
例えば、図３３に示すような波長割当状況は、全てのリンクで使用されていない波長λ４及びλ９を省いて並び替えられる。いずれかのリンクで波長が使用されている場合、その波長には、仮波長番号（１）〜（８）が順に付与される。この仮波長番号を用いて、波長パス事前設計機能部１０２は、波長パスの再配置先を設計することができる。なお、パス設定機能部１０６において波長を設定する場合、仮の波長番号を元の波長番号に戻して設定する。
【０２４８】
第１１の実施形態によれば、整数線形計画法の変数及び制約数が少なくなるため、計算量の削減が可能となる。
【０２４９】
＜第１２の実施形態＞
第１２の実施形態では、波長パス事前設計機能部１０２において、波長パスの再配置先を設計する際の整数線形計画法の計算量を削減する例について説明する。
【０２５０】
波長パス事前設計機能部１０２は、通信網内のいずれかのリンクに空きのある波長について、再配置対象の波長パスと、再配置先の波長パスとを設計する。すなわち、全てのリンクで使用されている波長については、計算の対象から除外する。なお、全てのリンクで使用されていない波長についても、計算の対象から除外してもよい。
【０２５１】
例えば、図３４に示すような波長割当状況は、全てのリンクで使用されている波長λ４、λ６、λ９及びλ１を省いて並び替えられる。いずれかのリンクにおいて波長に空きがある場合、その波長には、仮波長番号（１）〜（６）が順に付与される。この仮波長番号を用いて、波長パス事前設計機能部１０２は、波長パスの再配置先を設計することができる。なお、パス設定機能部１０６において波長を設定する場合、仮の波長番号を元の波長番号に戻して設定する。
【０２５２】
第１２の実施形態によれば、整数線形計画法の変数及び制約数が少なくなるため、計算量の削減が可能となる。
【０２５３】
＜第１３の実施形態＞
第１３の実施形態では、上記のいずれかの実施形態を、無瞬断切り替え機能をもつイーサネット装置で構成される通信網に適用した場合について説明する。無瞬断切り替え機能をもつイーサネット装置は、例えば特許文献２に記載されている。
【０２５４】
図３５は、第１３の実施形態に係る通信システムの概要図である。この通信システムでは、無瞬断切り替え機能をもつイーサネット装置がトランスポート装置に接続される。トランスポート装置は、イーサネット装置から受信したパケットを対向のトランスポート装置に送信する伝送装置である。
【０２５５】
上記のいずれかの実施形態で説明した管理装置が通信網に接続され、波長パス及び上位レイヤパスの設計及び再配置を行うことで、イーサネット装置間に設定されたパスを無瞬断で切り替えることが可能になる。
【０２５６】
＜第１４の実施形態＞
第１４の実施形態では、波長パス収容順序決定機能部１０４において、再配置対象の波長パスを再配置先の波長パスに変更するためのアルゴリズムを説明する。
【０２５７】
まず、再配置前後で波長パスの経路が変更しない場合について説明する。例えば図３６（１）に示すように、波長λ３の波長パスをλ５に再配置し、波長λ５の波長パスをλ４に再配置し、波長λ４の波長パスをλ６に再配置し、波長λ６の波長パスをλ３に再配置する場合を考える。波長λ６の波長パスをλ３に再配置しようとすると、λ３は使用されているため、無瞬断で再配置できない。このように波長パスの再配置先を順に辿ったときにループが生じる場合が考えられる。この場合、空き波長（例えばλ８０）を用いてループを解除し、再配置関係をツリー化する。そして、ツリーの先端（この場合はλ６）から再配置を開始することで、無瞬断での再配置が可能になる。
【０２５８】
具体的には、まず、波長λ６の波長パスを空き波長λ８０に再配置する。この再配置により、波長λ６が空き波長になり、波長λ４の波長パスをλ６に再配置することができる。同様に、波長λ５の波長パスをλ４に再配置し、次に、波長λ３の波長パスをλ５に再配置することが可能になる。そして、空き波長λ８０に退避させた波長パスをλ３に再配置することが可能になる。このように、最初にループ内のいずれかの波長パスを空き波長に退避させることで、ループを切断できる。
【０２５９】
次に、再配置前後で波長パスの経路が変更する場合について説明する。例えば図３６（２）に示すように、パス識別子１の波長パスをパス識別子１'が収容されている波長に再配置し、パス識別子３の波長パスをパス識別子４が収容されている波長及びパス識別子８が収容されている波長に再配置し、パス識別子８の波長パスをパス識別子１が収容されている波長、パス識別子３が収容されている波長及びパス識別子９が収容されている波長に再配置する場合を考える。パス識別子１の波長パスは、パス識別子１'が収容されている波長に再配置することができる。しかし、パス識別子８の波長パスをパス識別子３が収容されている波長に再配置しようとすると、その波長は使用されているため、無瞬断で再配置できない。このように波長パスの再配置先を順に辿ったときにループが生じる場合が考えられる。この場合も同様に、空き波長（例えばλ８０）を用いてループを解除し、再配置関係をツリー化する。そして、ツリーの先端（この場合はパス識別子１及び３）から再配置を開始することで、無瞬断での再配置が可能になる。
【０２６０】
具体的には、まず、パス識別子３の波長パスを空き波長λ８０に再配置する。また、パス識別子１の波長パスをパス識別子１'が収容されている波長に再配置する。この再配置により、パス識別子１が収容されている波長及びパス識別子３が収容されている波長が空き波長になり、パス識別子８の波長パスを再配置することができる。そして、空き波長λ８０に退避させた波長パスをパス識別子４が収容されている波長及びパス識別子８が収容されている波長に再配置することが可能になる。このように、最初にループ内のいずれかの波長パスを空き波長に退避させることで、ループを切断できる。
【０２６１】
＜第１５の実施形態＞
本発明における第１５の実施の形態を、図３７を用いて説明する。以下のフローで実施する。
ステップ２１００において、前述の数式（１）、もしくは後述の数式（１９）の目的関数を満たす整数線形計画法を用いて、既存波長パスの再配置演算を行う。 このとき、目的関数を満たす複数解を算出する。
【０２６２】
ステップ２２００において、再配置対象の波長パスを再配置先の波長パスに変更するための順序をステップ２１００で算出した複数解において決定する。
【０２６３】
ステップ２３００において、ステップ２２００の順序におけるパスの設定／削除するオペレーション数を算出する。
【０２６４】
ステップ２４００において、オペレーション数を比較してオペレーション数が最小の再配置波長パス並びに再配置順序を決定する。
【０２６５】
以上から目的関数を満たしかつオペレーション数が最小の解を算出可能となる。以下にステップ２１００、２２００の処理について説明をする。ステップ２１００で用いる整数線形計画法は、ノードv (ν∈V)、リンクe (e∈E)のグラフG( V, E)、波長w( w∈W)とし、制約は非特許文献２に示されたフロー保存式を用いる。
【０２６６】
＜変数＞
・Pdew：対地間ペアdの波長パスが、リンクｅにおいて波長番号wが使用される場合は1、それ以外は0
・FW： フラグメンテーション関数：
フラグメンテーション関数は、使用波長領域数を最小にするために用いる関数であり、図３に示すようにある波長に関して全リンクで使用している場合もしくは未使用の場合はコストが０で、それ以外を１とする関数を表す。
【０２６７】
＜定数＞
・P0,dew：対地間ペアdの再配置前の既存波長パスが、リンクeにおいて波長番号wが使用される場合は1、それ以外は0
・CP：波長パスコストパラメータ
・CF：フラグメンテーションコストパラメータ(0以上の実数)
・CWR：波長パス再配置コストパラメータ(0以上の実数)
＜目的関数＞
【０２６８】
【数１９】
目的関数の第１項は、波長パスを最短経路で設計することを示し、第２項は、フラグメンテーションコストを最小にするように設計することを示し、第３項は、波長パスの変更に伴うコスト値を表す。第３項における「波長パス」を「上位レイヤパス」としてもよいし、また波長パス及び上位レイヤパスの両方を考慮してもよい。また、第３項を目的関数に加えないで、式（８）や式(１６）のように変更数を所定数以下とする制約を追加して、その制約内で算出してもよい。第1項と第2項を小さくする目的関数によって使用波長領域数を削減可能となる。
【０２６９】
CPは例えば設備コストから波長１本あたりのコストを算出する方法で設定する。CFも同様に例えば設備コストから波長１本あたりのコストを算出する方法で設定する。ただし、CP 、CF ともに任意の値としてもよい。CWRは任意の値とする。また、式（１９）の第2項を、以下の式に置き換えることでフラグメンテーションが発生している波長チャネルの波長数の重み付けが可能となる。
【０２７０】
【数２０】
ここで、αは実数。
【０２７１】
例えば、リンク数が７のネットワークでCF=1、α=0.1で式（２０）のこの関数をある波長wに関して図示すると図３８のように表すことができる。
【０２７２】
以上から上記目的関数を満たす複数の解を算出する。ステップ２２００における再配置順序演算は前述の図１０で示した第1の実施形態における収容順序決定手順や図３６に示す第14の実施形態における再配置方法により行なう。
【０２７３】
[第１６の実施の形態]
本発明における第１６の実施の形態を、図３９を用いて説明する。予め算出する解の数を決めておき、第１５の実施の形態のステップ２１００の目的関数(式（１９)）の波長パス再配置コスト値CWRを、予め決めた算出する解の数まで変更して複数の解を算出する（ステップ３１０１，３１０２）。ここで再配置効果パラメータをそれぞれの解において算出する。再配置効果パラメータとは、目的関数の値、目的関数(式（１９)）の第１項と第２項の合計値、第２項においてコストが１の波長チャネルにおける波長数の合計値、設備コスト等があげられる。ステップ２２００以降は第１５の実施の形態と同様の処理をし、ステップ２４００において、再配置効果パラメータとオペレーション数がともに小さいものを選択する。
【０２７４】
[第１７の実施の形態]
本発明における第１７の実施の形態を説明する。第１５の実施の形態における図３７のステップ２３００において、例えばホップ数が大きいパスを変更するコストは、小さいものより大きくし、それらの合計をオペレーション数とする(式（2）)。もしくは、パス毎に変更コストの重み付けを行い、それらの合計をオペレーション数とする(式（3）)。
【０２７５】
[第１８の実施の形態]
本発明における第１８の実施の形態を説明する。第１６の実施の形態において、第１７の実施の形態のフロー（図３９）におけるステップ２１０１，２１０２の処理を用いたものである。
【０２７６】
[第１９の実施の形態]
本発明における第１９の実施の形態を、図４０を用いて説明する。第１の実施の形態におけるステップ２１００、ステップ２２００、ステップ２３００は同様の処理を行う。ここでステップ２１００においては複数解でなく１つの解としてもよい。次に予め算出する解の数と、オペレーション数のどちらかもしくは両方を設定しておき、設定数に達した場合はステップ２４００において、再配置効果パラメータとオペレーション数がともに小さいものを選択する。達していない場合は目的関数(式（１９)）の波長パス再配置コスト値CWRを、予め決めた算出する解の数まで変更して複数の解を算出する。
【０２７７】
第１９の実施の形態の効果を図４１に示す。ネットワーク条件は、物理トポロジは2×3格子網、論理トポロジはフルメッシュ双方向パス、上位レイヤパス及び波長パスの収容数は100本、波長パスコストCPは１、フラグメンテーションコストパラメータCFは１、波長パスに上位レイヤパス1本が収容されている条件で評価した。また、オペレーション数は第14の実施の形態を用いて算出した。図４１は波長再配置コストパラメータに対するオペレーション数（左）とフラグメンテーションが起きている波長チャネルにおける波長数（右）を表しており、この結果からCWR＝0~0.2のときにオペレーション数が小さくかつ再配置効果が大きい組み合わせを選択することができることがわかる。本実施の形態を用いることで再配置効果を保ったまま約50％のオペレーション数の削減が可能となる。
【０２７８】
[第２０の実施の形態]
本発明における第２０の実施の形態を、図４２を用いて説明する。第１４の実施の形態において、再配置前後の波長パスの移設関係をグラフツリーに表し、移設ループの小さい順番に移設させることによって、空き波長を有効に使用するための方法である。例えば、図４２のようにツリーAには２つのループが、ツリーBには１つのループが存在していた場合に、ループの数が小さいツリーBから再配置させることによって、空きリソースを有効に使用することができる。
【０２７９】
＜実施形態の効果＞
本発明の実施形態によれば、通信網内で使用されている波長領域の空き波長も含めた波長数（使用波長領域数）もしくは設備コストを削減することが可能になり、設備増設量を低減することが可能になる。
【０２８０】
例えば、図４３に示すように、上位レイヤパスを再配置することにより、上位レイヤパスを収容していない波長パスを削除することが可能になり、また複数の波長パスに跨って上位レイヤパスが設定される場合は、トランスポンダを削減することが可能となる。さらに、図４４に示すように、使用波長領域数（通信網全体で使用されている波長領域の波長数）を削減することが可能になる。
【０２８１】
また、本発明の第８の実施形態の変形例に従って波長パス及び上位レイヤパスを再配置した場合と、再配置しなかった場合との比較結果を図４６に示す。想定するノードアーキテクチャとコストモデルは図４５に示す。ノードアーキテクチャは波長パスクロスコネクト装置に複数の上位レイヤパスクロスコネクト装置が結合しており、波長パスの最大転送レート内において上位レイヤパスをマルチホップグルーミング（複数の拠点から発生する上位レイヤパスを束ねて波長パスに収容。文献：「K. Zhu and B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Select. Areas Commun., vol. 20, no. 1, pp. 122-133, Jan. 2002.」参照）することが可能であるネットワークモデルを想定する。
【０２８２】
シミュレーション条件は、以下の通り。
【０２８３】
・物理トポロジ：２×３格子網
・波長多重数：４０
・上位レイヤパスのクロスコネクト装置のポート数：３２
・波長パス1本あたりの最大転送レート：４０[Gbps]
・上位レイヤパスの転送レート種別：2.5G、10G、40G
・上位レイヤパスの転送レート別存在比率：2.5Gパス:10Gパス:40Gパス＝5:2:3
・再配置タイミング：５０本の上位レイヤパスを収容毎
・トラフィック発生条件：始点と終点のノードペアはランダム
以上のモデルにおいて、本発明の方式とパス再配置を行わなかった場合を比較した結果が図４６である。図４６はトラフィック量に対する本発明方式の相対的なコスト削減効果を表しており、本発明を用いた場合には、用いない場合に比べて最大で１２％のコスト削減効果がある。
【０２８４】
更に、本発明の実施形態によれば、波長パスの再配置及び上位レイヤパスの再配置を無瞬断で行うことができる。
【０２８５】
説明の便宜上、本発明の実施形態に係る管理装置は機能的なブロック図を用いて説明しているが、本発明の管理装置は、ハードウェア、ソフトウェア又はそれらの組み合わせで実現されてもよい。また、２以上の実施形態及び実施形態の各構成要素が必要に応じて組み合わせて使用されてもよい。
【０２８６】
上記の実施形態では、主に集中制御方式について説明しているが、分散制御方式でも同様に実現可能である。また、図５及び図６に本発明の実施形態で用いられるノード装置を示しているが、ノード装置は波長パス及び上位レイヤパスを設定する装置であれば、如何なる構成になってもよい。また、パスの事前設計及び収容順序決定は、事前に計算されずに、逐次的に計算されてもよい。同様に、逐次的な計算も、事前に行われてもよい。
【０２８７】
また、本発明の実施形態では、空き波長を用いて再配置を行っているが、予め再配置専用に空き波長を通信網内に確保しておいてもよい。
【０２８８】
以上、本発明の実施形態について説明したが、本発明は、上記の実施形態に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【産業上の利用可能性】
【０２８９】
本発明は、通信網における波長パス及び上位レイヤパスの再配置に適用可能である。
【符号の説明】
【０２９０】
１０ 管理装置
１０１ 既存パス管理データベース
１０２ 波長パス事前設計機能部
１０３ 再配置対象パス管理データベース
１０４ 波長パス収容順序決定機能部
１０５ 収容順序管理データベース
１０６ パス設定機能部
１０７ 制御信号送受信インタフェース
２０ ノード装置
２０１ 制御信号送受信インタフェース
２０２ 上位レイヤ装置接続インタフェース
２０３ 信号複製機能部
２０４ 無瞬断切り替え機能部
２０５ 波長パス選択機能部
２０６ スイッチング機能部
２０７ データ転送用インタフェース
３０ 管理装置
３０１ 既存パス管理データベース
３０２ 上位レイヤパス事前設計機能部
３０３ 再配置対象パス管理データベース
３０６ パス設定機能部
３０７ 制御信号送受信インタフェース
【技術分野】
【０００１】
本発明は、波長パス再配置方法及び上位レイヤパス再配置方法に関する。
【背景技術】
【０００２】
中継ノード間で波長変換が行われないトランスペアレント光メッシュ網においては、波長パスの設定及び削除を繰り返すことによって徐々に波長空き帯域を有効に使うことができなくなり、ネットワーク設備量が増大することが懸念される。また、OTN（Optical Transport Network）やSDH（Synchronous Digital Hierarchy）やVCAT（Virtual Concatenation）等の上位レイヤパスにおいても、パスの設定及び削除を繰り返すことによって波長パス内の収容効率が悪くなると考えられる。
【０００３】
これらの問題を解決するために、波長パスを再配置する方法（非特許文献１参照）、パスの容量・経路を変更する方法（特許文献１参照）が提案されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−２０５７２
【特許文献２】特開２００７−２０９０４０
【非特許文献】
【０００５】
【非特許文献１】E. Bouillet, et al., "Lightpath Re-Optimization in Mesh Optical Networks", IEEE/ACM Transactions on Networking, Vol. 13, No2, pp437-pp447.April, 2005.
【非特許文献２】J. Kuri, et al., "Resolution of a WDM network design problem using a decomposition approach and a size reduction method", Proceedings of ECUMN 2002, Colmar,. France, April 2002.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記の通り、波長パスの設定及び削除を繰り返すことによって、通信網内で使用されている波長領域内に空き波長が生じて、波長領域内の空き波長も含めた波長数（使用波長領域数）、すなわち、使用中の最小の波長番号から使用中の最大の波長番号までの波長数（通信網内で使用されていない波長番号を除く）が大きくなる。しかし、非特許文献１及び特許文献１に記載の方法では、使用波長領域数を削減することは考慮されていない。
【０００７】
また、波長パスを再配置するときの順序（再配置対象の波長パスを再配置先の波長パスに変更する順序）と空きリソース量によっては、波長パスを再配置できない可能性がある。しかし、非特許文献１及び特許文献１に記載の方法では、波長パスを再配置するときの順序は考慮されていない。
【０００８】
更に、波長パス内に上位レイヤパスが設定されている場合には、上位レイヤパスと波長パスとの双方を考慮して再配置する必要があるが、非特許文献１及び特許文献１に記載の方法では、このような点は考慮されていない。
【０００９】
更に、波長パスの再配置を行うオペレーション数を考慮して、オペレーションコストも最小にするような波長パスの再配置方法は考えられていない。
【００１０】
上記の課題を解決するため、本発明は、通信網内で使用されている波長領域の空き波長も含めた波長数（使用波長領域数）の削減並びにオペレーションコストを削減する波長パス再配置方法及び上位レイヤパス再配置方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の波長パス再配置方法は、
通信網内に設定された波長パスを再配置するパス再配置装置における波長パス再配置方法であって、
波長パス設計部が、通信網内の使用波長領域数を再配置前の値より小さくする計算を行うことにより、再配置先の波長パスを設計する波長パス設計ステップと、
波長パス設定部が、空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更する波長パス設定ステップと、
を有することを特徴とする。
【００１２】
本発明の上位レイヤパス再配置方法は、
通信網内に設定された波長パス内の上位レイヤパスを再配置するパス再配置装置における上位レイヤパス再配置方法であって、
上位レイヤパス設計部が、通信網内で使用されている波長数を再配置前の値より小さくする計算を行うことにより、再配置先の上位レイヤパスを設計する上位レイヤパス設計ステップと、
上位レイヤパス設定部が、再配置対象の上位レイヤパスを再配置先の上位レイヤパスに変更する上位レイヤパス設定ステップと、
を有することを特徴とする。
【００１３】
本発明の波長パス再配置方法は、
通信網内に設定された波長パスを再配置するパス再配置装置におけるパス再配置方法であって、
波長パス設計部が、通信装置の利用効率を上げる、もしくは将来的なトラフィック需要による波長衝突を削減するように波長パスを再配置する波長パス設計ステップと、
空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更するための順序を決定してオペレーション数を算出する収容順序演算ステップを有し、
オペレーション数が最小の波長再配置及び順序を決定するステップを有することを特徴とする。
【発明の効果】
【００１４】
本発明によれば、通信網内で使用されている波長領域の空き波長も含めた波長数（使用波長領域数）を削減とともにオペレーションコストの削減も実現することが可能になる。
【図面の簡単な説明】
【００１５】
【図１】使用波長領域数と使用波長数とを説明するための図（その１）
【図２】使用波長領域数と使用波長数とを説明するための図（その２）
【図３】フラグメンテーション関数の説明図例
【図４】本発明の第１の実施形態に係る管理装置のブロック図（集中制御方式）
【図５】本発明の第１の実施形態に係るノード装置のブロック図（その１）
【図６】本発明の第１の実施形態に係るノード装置のブロック図（その２）
【図７】本発明の第１の実施形態に係るノード装置のブロック図（分散制御方式）
【図８】本発明の第１の実施形態で用いられるフロー保存方程式の算出例を示す図
【図９】本発明の第１の実施形態に係る管理装置で計算された再配置前後の波長パスを示す図
【図１０】本発明の第１の実施形態に係る管理装置における収容順序決定手順を示す図
【図１１】本発明の第１の実施形態に係る管理装置における波長パス設定手順を示す図
【図１２】本発明の第１の実施形態に係る管理装置における波長パスの再配置を示す図
【図１３】本発明の第１の実施形態に従って波長パスを設定するシーケンス図（集中制御方式）
【図１４】本発明の第１の実施形態に従って波長パスを設定するシーケンス図（分散制御方式）
【図１５】本発明の第２の実施形態に係る管理装置における収容順序決定手順を示す図
【図１６】本発明の第３又は４の実施形態に係る管理装置のブロック図（集中制御方式）
【図１７】本発明の第４の実施形態に係る管理装置における波長パスの再配置を示す図
【図１８】本発明の第４の実施形態に係る管理装置における波長パス設定手順を示す図
【図１９】本発明の第５の実施形態に係る管理装置のブロック図（集中制御方式）
【図２０】本発明の第５の実施形態に係る管理装置における波長パスの再配置を示す図
【図２１】本発明の第６の実施形態に係る管理装置のブロック図（集中制御方式）
【図２２】本発明の第６の実施形態に係る管理装置における上位レイヤパス設定手順を示す図
【図２３】本発明の第６の実施形態に従って上位レイヤパスを設定するシーケンス図（集中制御方式）
【図２４】本発明の第６の実施形態に従って上位レイヤパスを設定するシーケンス図（分散制御方式）
【図２５】本発明の第７の実施形態に係る管理装置のブロック図
【図２６】本発明の第７の実施形態に係る管理装置における上位レイヤパス設定手順を示す図
【図２７】本発明の第８の実施形態に係る管理装置のブロック図（集中制御方式）
【図２８】本発明の第８の実施形態に係る管理装置における上位レイヤパス及び波長パスの再配置手順を示す図
【図２９】本発明の第９の実施形態に係る管理装置における収容順序決定手順を示す図
【図３０】本発明の第１０の実施形態に係る管理装置における波長パス設定手順を示す図
【図３１】本発明の第１０の実施形態で用いられる物理トポロジ及び波長割当状況を示す図
【図３２】本発明の第１０の実施形態に係る管理装置における波長パスの再配置を示す図
【図３３】本発明の第１１の実施形態に係る管理装置における計算対象の波長パスを示す図
【図３４】本発明の第１２の実施形態に係る管理装置における計算対象の波長パスを示す図
【図３５】本発明の第１３の実施形態に係る通信システムの概要図
【図３６】本発明の第１４の実施形態に係る管理装置における波長パスの再配置を示す図
【図３７】本発明の第１５の実施形態に係るフローチャート
【図３８】本発明の第１５の実施の形態に係るフラグメンテーションコストの説明図例
【図３９】本発明の第１６の実施形態に係るフローチャート
【図４０】本発明の第１９の実施の形態に係るフローチャート
【図４１】本発明の第１９の実施の形態における効果
【図４２】本発明の第２０の実施の形態における再配置の例を示す図
【図４３】本発明の実施形態における上位レイヤパスの再配置の効果を示す図
【図４４】本発明の実施形態における波長パスの再配置の効果を示す図
【図４５】本発明の効果を示すための想定モデル
【図４６】本発明における波長パス及び上位例やパス再配置の効果
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について詳細に説明する。
【００１７】
まず、本発明の実施形態で用いる用語について説明する。
【００１８】
「使用波長領域数」とは、通信網内で使用されている波長領域の空き波長を含めた波長数、すなわち、使用中の最小の波長番号から使用中の最大の波長番号までの波長数（通信網内で使用されていない波長番号を除く）のことである。使用波長領域数の算出には、（１）リンク毎に使用されている波長領域の波長数を算出する方法と、（２）通信網全体で使用されている波長領域の波長数を算出する方法との２通りがある。
【００１９】
「使用波長数」とは、使用されている波長の数である（空き波長は含まない）。
【００２０】
例えば、図１のように波長を小さい順又は大きい順に割り当てた通信網における使用波長領域数及び波長数について説明する。（１）の場合、ノードA-B間の使用波長領域数は６（λ１〜λ６）となり、使用波長数は４（λ１、λ２、λ３、λ６）となる。ノードB-C間の使用波長領域数は４（λ２〜λ５）となり、使用波長数は３（λ２、λ３、λ５）となる。ノードC-D間の使用波長領域数は５（λ２〜λ６）となり、使用波長数は５（λ２〜λ６）となる。（２）の場合、全てのリンクにおいて使用波長領域数は６（λ１〜λ６）となる。
【００２１】
また、図２のように波長をランダムに（小さい順又は大きい順以外の方法で）割り当てた場合又は波長パスが削除されて使用されていない波長が存在する場合、通信網内において使用されている波長を片側に寄せて使用波長領域数を算出する。（１）の場合、ノードA-B間の使用波長領域数は３（λ１、λ２、λ６）となり、使用波長数は３（λ１、λ２、λ６）となる。ノードB-C間の使用波長領域数は４（λ２、λ６、λ４、λ７）となり、使用波長数は３（λ２、λ４、λ７）となる。ノードC-D間の使用波長領域数は４（λ２、λ６、λ４、λ７）となり、使用波長数は３（λ２、λ６、λ７）となる。（２）の場合、全てのリンクにおいて使用波長領域数は５（λ１、λ２、λ６、λ４、λ７）となる。
【００２２】
なお、「使用波長数領域数」は、ノードの「使用しているポートまでの数」、「使用波長数」はノードの「使用しているポート数」としてもよい。
【００２３】
「スイッチング機能部」とは、信号光をスイッチングする機能部であり、例えば、光クロスコネクト、光スイッチ、ODU（Optical-channel Data Unit）クロスコネクト、2-D MEMS（Micro Electro Mechanical Systems）スイッチ、3-D MEMSスイッチ等が含まれる。
【００２４】
「波長パス選択機能部」とは、波長を選択する機能部であり、例えばWSS（Wavelength Selective Switch）等が含まれる。
【００２５】
「管理装置」とは、波長パスの波長及び経路を選択して設定し、また、上位レイヤパスの経路を選択して設定する装置であり、例えば、NMS（Network Management System）、NRM（Network Resource Manager）、PCE（Path Computation Element）、EMS（Element Management System）等が含まれる。
【００２６】
「無瞬断切り替え」とは、瞬断なく切り替えることであり、例えば、短時間で（50ms以内等）パスを切り替えること、データが欠落しないようにパスを切り替えること、パケットレイヤでパケットが欠落しないようにパスを切り替えること等が含まれる。短時間でパスを切り替える場合には、その間のデータが欠落してもよい。
【００２７】
「上位レイヤパス」とは、波長パス内に設定されてユーザに提供されるパスのことであり、例えば、TDM（Time Division Multiplexing）パス、SDH（Synchronous Digital Hierarchy）パス、Ethernet（登録商標）、MPLS（Multiprotocol Label Switching）のLabel Switched Path、又はそれらをグループ化したVCAT（Virtual Concatenation）、Link Aggregation等が含まれる。上位レイヤパスは、波長パスに重畳される。
【００２８】
「上位レイヤパスの粒度」とは、上位レイヤパスに割り当てられた帯域量のことであり、例えば、１Ｇ上位レイヤパスの粒度とは、１Ｇであり、３Ｇ上位レイヤパスの粒度とは３Ｇである。
【００２９】
「通信路設定メッセージ」とは、リソースの予約又はリソースの割り当てを行う制御情報とパス経路情報とを含むメッセージのことであり、波長パスを設定する場合には、通信路設定メッセージは更に波長情報を含む。
【００３０】
「通信路設定完了通知」とは、波長情報を含む波長パスの設定が完了したことを通知するメッセージである。
【００３１】
「通信路削除メッセージ」とは、リソースの開放予約又はリソースの開放を行う制御情報とパス経路情報とを含むメッセージのことであり、波長パスを削除する場合には、通信路削除メッセージは更に波長情報を含む。
【００３２】
「通信路削除完了通知」とは、波長情報を含む波長パスの削除が完了したことを通知するメッセージである。
【００３３】
「上位レイヤパス設定メッセージ」とは、上位レイヤパスを収容する波長パスを選択するための波長情報又はポート情報と、収容する上位レイヤパスの識別情報とを含むメッセージである。
【００３４】
「上位レイヤパス削除完了通知」とは、上位レイヤパスの識別情報を含む上位レイヤパスの削除が完了したことを通知するメッセージである。
【００３５】
「上位レイヤパス削除メッセージ」とは、リソースの開放予約又はリソースの開放を行う制御情報とパス経路情報とを含むメッセージのことであり、更に上位レイヤパスの識別情報を含む。
【００３６】
「波長パス選択完了通知」とは、上位レイヤパスの識別情報を含む波長パスの選択が完了したことを通知するメッセージである。
【００３７】
「リソース開放メッセージ」とは、ノード装置に対してリソース開放を行う制御情報を含むメッセージのことである。
【００３８】
「リソース割当」とは、波長パスにおいては、入力ポートからの波長多重信号光から分波された光信号を、所定の出力光伝送路ポートに同じ波長で出力されるように設定すること（光クロスコネクト）のことである。上位レイヤパスにおいては、始点ノードと終点ノードとの間に上位レイヤパスを設定することであり、始点ノード及び終点ノードに上位レイヤパス設定メッセージを送信することで設定可能である。
【００３９】
「リソース割当メッセージ」とは、ノード装置に対してリソース割り当てを行う制御情報を含むメッセージのことである。
【００４０】
「通信装置」とは、ROADM、ODUクロスコネクトスイッチ、MPLS-TPルータ、OXC、トランスポンダー等である。
【００４１】
「オペレーション数」とは、パスを再配置するときに必要となるパスの設定／削除シーケンスの数のことである。もしくは、パスの設定／削除に必要なオペレーションコストの合計である。
【００４２】
「波長チャネル」とは、図３に示すように、ネットワーク内における波長番号のことのことである。
【００４３】
「フラグメンテーション」とは、図３に示すように、ある波長チャネルにおいて使用可能な経路が限られている状態、もしくは波長がリンクに対して離散的になっている状態をさす。
【００４４】
本発明における実施形態について、以下の３つの場合について説明する。
【００４５】
（１）波長パスを再配置する場合（第１の実施形態〜第５の実施形態、第９の実施形態〜第１２の実施形態、第１４の実施形態〜第２０の実施の形態）
（２）上位レイヤパスを再配置する場合（第６の実施形態〜第７の実施形態）
（３）上位レイヤパスを再配置し、その後波長パスを再配置する場合（第８の実施形態）
なお、（３）は（１）と（２）とを組み合わせた方法であり、（２）の再配置によって不要な波長パスを削減することによって波長パスの再配置数を削減することが可能となる。
【００４６】
＜第１の実施形態＞
第１の実施形態では、波長パスを再配置する場合について説明する。波長パスの設定方法としては集中制御方式と分散制御方式が存在する。集中制御方式は、１つの管理装置で通信網内全体のノード装置を管理し、各ノード装置に対して波長パス及び上位レイヤパスを設定するための制御信号を送信する方式である。分散制御方式は、各ノード装置に管理制御機能が備えられる方式である。
【００４７】
まず、集中制御方式での管理装置及びノード装置について説明する。
【００４８】
図４は、本発明の第１の実施形態に係る管理装置１０のブロック図である。管理装置１０は、既存パス管理データベース１０１と、波長パス事前設計機能部１０２と、再配置対象パス管理データベース１０３と、波長パス収容順序決定機能部１０４と、収容順序管理データベース１０５と、パス設定機能部１０６と、制御信号送受信インタフェース１０７とを有する。
【００４９】
既存パス管理データベース１０１は、通信網内に設定された既存波長パスの経路・波長情報と、通信網内の各リンクの空き波長情報と、上位レイヤパスの収容先の波長パスの経路・波長情報と、各上位レイヤパスの粒度とを管理する。既存パス管理データベース１０１は、クライアント情報（どの上位レイヤパスがどのクライアントに対応するかという情報）を管理してもよい。
【００５０】
波長パス事前設計機能部１０２は、既存パス管理データベース１０１で管理されている情報を用いて、再配置対象の波長パスと、再配置先の波長パスとを事前に設計する。再配置先の波長パスの設計方法は、後述する。
【００５１】
再配置対象パス管理データベース１０３は、波長パス事前設計機能部１０２から得られた再配置対象の波長パス（再配置する必要のある波長パスの再配置前の波長パス）の経路・波長と、再配置先の波長パス（再配置する必要のある波長パスの再配置後の波長パス）の経路・波長とを保存する。
【００５２】
波長パス収容順序決定機能部１０４は、再配置対象の波長パスを再配置先の波長パスに変更することができる収容順序を決定する。収容順序の決定方法は、後述する。
【００５３】
収容順序管理データベース１０５は、波長パス収容順序決定機能部１０４で決定された収容順序情報を保存する。
【００５４】
パス設定機能部１０６は、収容順序に従って、波長パス及び上位レイヤパスを設定／削除する。具体的には、パス設定機能部１０６は、波長パス及び上位レイヤパスの設定／削除を指示するため、制御信号送受信インタフェース１０７を介してリソース割当メッセージ、通信路設定メッセージ又は通信路削除メッセージをノード装置に送信する。また、パス設定機能部１０６は、上位レイヤパスの収容先波長パスの設定／削除を指示するため、制御信号送受信インタフェース１０７を介して上位レイヤパス設定メッセージをノード装置に送信する。なお、パス設定機能部１０６は、波長パス及び上位レイヤパスのリソースの予約（割当）又は開放（削除）情報を保存するためのリソース管理データベース（図示せず）を有してもよい。
【００５５】
制御信号送受信インタフェース１０７は、制御信号をノード装置に送信し、また、ノード装置から制御信号を受信する。
【００５６】
図５は、本発明の第１の実施形態に係るノード装置２０のブロック図である。ノード装置２０は、制御信号送受信インタフェース２０１と、上位レイヤ装置接続インタフェース２０２と、信号複製機能部２０３と、無瞬断切り替え機能部２０４と、波長パス選択機能部２０５と、スイッチング機能部２０６と、データ転送用インタフェース２０７とを有する。
【００５７】
制御信号送受信インタフェース２０１は、管理装置から制御信号を受信し、また、管理装置へ制御信号を送信する。
【００５８】
上位レイヤ装置接続インタフェース２０２は、上位レイヤパスを提供する上位レイヤ装置に接続するためのインタフェースである。
【００５９】
信号複製機能部２０３は、上位レイヤ装置接続インタフェース２０２から入力された信号を複製し、２つのポートから複製信号を送信する。
【００６０】
無瞬断切り替え機能部２０４は、信号複製機能部２０３から入力された２つの信号の位相同期を行い、無瞬断で切り替える。
【００６１】
波長パス選択機能部２０５は、制御信号送受信インタフェース２０１から送られてきた制御信号に基づいて、上位レイヤパスを収容する波長パス（波長）を選択する。
【００６２】
スイッチング機能部２０６は、制御信号送受信インタフェース２０１から送られてきた制御信号に基づいて、波長パスを設定／削除する。
【００６３】
データ転送用インタフェース２０７は、データを別ノードに転送する。
【００６４】
また、図６に示すように、信号複製機能部２０３で信号を複製せずに、上位レイヤ装置接続インタフェース２０２の２つのポートから同じデータを出力してもよい。この場合、信号複製機能部２０３はノード装置２０に含まれなくてもよい。
【００６５】
次に、分散制御方式でのノード装置について説明する。
【００６６】
図７に分散制御方式でのノード装置を示す。分散制御方式の場合、各ノード装置は、図４に示す管理装置の各管理機能部を有する。例えば、図７に示すように、図５のノード装置に、図４の管理装置の各管理機能部が含まれてもよい。同様に、図６のノード装置に、図４の管理装置の各管理機能部が含まれてもよい。図５又は図６におけるノード装置の制御情報送受信インタフェースが各管理機能部と接続するためのインタフェースとなる。なお、パス設定機能部１０６は、波長パス及び上位レイヤパスのリソースの予約（割当）又は開放（削除）情報を保存するためのリソース管理データベース（図示せず）を有してもよい。
【００６７】
次に、波長パス事前設計機能部１０２における波長パスの再配置先の設計方法について説明する。この設計方法は、オフラインで事前に設計されてもよい。ここでは、整数線形計画法（ILP：integer linear programming）を用いて、再配置先の波長パスの経路及び波長を事前に設計する。
【００６８】
波長パス事前設計機能部１０２は、以下の目的関数を最小化する波長パスの経路及び波長を計算する。
【００６９】
【数１】
この目的関数は、使用されている波長番号と波長数の積の合計数を最小化するための関数、すなわち、使用波長領域数を最小化するための関数である。すなわち、できるだけ小さい波長番号から順に波長を使用し、使用されている波長数を少なくすることを目的とした関数である。ただし、pijwsdは、波長wが使用されているか否かを示す変数であり、始点sから終点dまでの各物理リンク(i,j)において、波長wが使用されている場合はpijwsd=1であり、波長wが使用されていない場合はpijwsd=0である。Vはノードの集合であり、Eはリンクの集合であり、Wは波長の集合（w=0,1,2,3,...,WMAX）であり、WMAXは最大波長多重数であり、これらは予め決められたパラメータである。
【００７０】
目的関数(1)の計算にあたり、以下の制約条件を用いる。
【００７１】
【数２】
【００７２】
【数３】
【００７３】
【数４】
【００７４】
【数５】
制約条件(2)は、始点s、終点d及び波長wにおいて各リンクのトラヒックフローを表す方程式（非特許文献２参照）である。この制約によりパスの経路と始点・終点ノードで同一波長を選択することが可能となる。ただし、λwsdは、始点sから終点dまでの経路で波長wが使用されている数（0〜Dsd）を示す。λwsd=0の場合、始点sから終点dまでの経路で波長wが使用されていないことを示し、λwsd=1の場合、始点sから始点dまでの１つの経路で波長wが使用されていることを示す。また、i＜jのときΣpijwsd=Σpijwsd、i＞jのときΣpijwsd=−Σpjiwsdとなる。制約条件(2)の算出例を図８に示す。λwsdは、既存パス管理データベース１０１内に保存された通信網内に設定された既存波長パスの経路・波長情報から求めることができる。
【００７５】
制約条件(3)は、各リンクの波長数の合計が最大波長多重数WMAX以下とする条件である。
【００７６】
制約条件(4)は、波長衝突を起こさないための条件であり同じリンクで２つ以上の同じ波長を使わないという条件である。
【００７７】
制約条件(5)は、始点sから終点dまでの経路で使用される波長の合計数が、始点sから終点dまでの波長パスの需要総数Dsdに等しいという条件である。ただし、Dsdは、始点sから終点dまでの波長パスの総数であり、既存パス管理データベース１０１内に保存された既存パスの経路・波長情報から予め求められる。
【００７８】
制約条件(2)〜(5)を用いて目的関数(1)を計算することにより、再配置後の波長パスの経路及び波長pijwsdが出力される。
【００７９】
制約条件(2)〜(5)に加えて、次の制約条件(6)〜(9)のうち１つ以上が用いられてもよい。
【００８０】
【数６】
【００８１】
【数７】
【００８２】
【数８】
【００８３】
【数９】
制約条件(6)は、始点sから終点dまでのホップ数の合計が最大ホップ数Himpairment以下とする条件である。ただし、Himpairmentは最大伝送可能ホップ数であり、予め決められたパラメータである。
【００８４】
制約条件(7)は、始点sから終点dまでのホップ数の合計が、始点s及び終点dのノードの組毎に設定した伝送ホップ数Hsd以下とする条件である。ただし、Hsdは、始点sから終点dまでのパスにおける伝送ホップ数であり、予め決められたパラメータである。
【００８５】
制約条件(8)は、再配置する波長の数が既存波長数の合計数のうち所定の割合Rを超えないようにする条件である。すなわち、制約条件(8)は、再配置対象の波長数が所定の閾値を超えないようにする条件である。ただし、Rは再配置する波長パスの割合であり、予め決められたパラメータである。
【００８６】
制約条件(9)は、再配置前の始点sから終点dの経路ホップ数と再配置後の経路ホップ数との差が遅延差又は距離差の限界Hdelayを満たすホップ数以下であるとする条件である。ただし、Hdelayは、許容される最大の遅延差又は距離差を満たすホップ数であり、予め決められたパラメータである。
【００８７】
制約条件(6)を用いることにより、再配置対象の波長数を制限することができる。また、制約条件(7)のHsdにおいて、最短ホップ数を事前に設定することで、最短経路の波長パスを計算することができる。また、制約条件(8)により、パスを切り替える際のバッファメモリの許容範囲内での経路選択が可能になる。
【００８８】
また、制約条件(2)〜(5)に加えて、以下の制約条件(10)が用いられてもよい。
【００８９】
【数１０】
制約条件(10)は、経路変更を行わないという条件、すなわち、再配置前の波長パスと再配置後の波長パスの経路が同じであるという条件である。ただし、p0ijwsdは、再配置前に波長wが使用されているか否かを示す変数であり、始点sから終点dまでの各物理リンク(i,j)において、再配置前に波長wが使用されている場合はp0ijwsd =1であり、再配置前に波長wが使用されていない場合はp0ijwsd=0である。p0ijwsdは、既存パス管理データベース１０１内に、通信網内に設定された既存波長パスの経路・波長情報として保存されている。
【００９０】
このように、制約条件(10)では、経路変更を行わずに再配置先の波長パスを計算することができる。
【００９１】
波長パス事前設計機能部１０２は、線形計画法（ILP）により目的関数を最小化する波長パスの経路・波長pijwsdを求め、再配置対象の波長パスの経路・波長と、再配置先の波長パスの経路・波長とを再配置対象パス管理データベース１０３に保存する。なお、再配置対象の波長パスは、再配置前の波長パスの経路・波長と、前記波長パス事前設計機能部から算出された波長パスの経路・波長pijwsdとの比較により抽出することができる。具体的には、図９に示すように、再配置前後の波長・経路が異なる場合（λ１、λ３、λ５、λ６）、再配置対象の波長パスとなり、再配置前後の波長・経路が同じである場合（λ２、λ４）、再配置対象の波長パスとはならない。
【００９２】
次に、波長パス収容順序決定機能部１０４は、波長パス収容順序決定機能部１０４における再配置対象の波長パスの収容順序を決定する。ここでは、波長パス収容順序決定機能部１０４は、空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更することができる収容順序を事前に決定する。具体的には、波長パス収容順序決定機能部１０４は、再配置対象の波長パスを再配置先の波長パスに変更する際に、再配置先に既に波長パスが存在するか否かを判別し、既に波長パスが存在する場合、その波長パスを空き波長に退避させることにより、再配置対象の波長パスを再配置先の波長パスに変更することができる収容順序を決定する。波長パス収容順序決定機能部１０４における収容順序決定手順について、図１０を用いて説明する。
【００９３】
波長パス事前設計機能部１０２で算出されて再配置対象パス管理データベース１０３に保存された再配置対象の波長パスの数をNとしたときに、N!通りの収容順序が考えられる。波長パス収容順序決定部１０４は、このN!通りの収容順序のそれぞれについて、空き波長を用いて再配置対象の波長パスを再配置先の波長パスに変更可能であるか否かを判別し、変更可能である収容順序jを収容順序管理データベース１０５に出力する。なお、再配置対象の波長パスの経路・波長と、再配置先の波長パスの経路・波長とは、再配置対象パス管理データベース１０３に保存されている。更に、空き波長（各リンクにおける空き波長リソース数、各リンクにおける空き波長番号）は、既存パス管理データベース１０１内に、空き波長情報として保存されている。
【００９４】
まず、ステップＳ１０１において、再配置先のN本の波長パスにおいて、再配置する波長の順番i(1≦i≦N)の全ての組み合わせj（1≦j≦N!）を求める。例えば、図９に示す例では、N=4である。４本の波長を再配置する収容順序は、4!=24通り考えられる。従って、ステップＳ１０１では、4本の波長（λ１、λ３、λ５、λ６）を再配置する収容順序の全ての組み合わせ(1,2,3,4),(1,2,4,3,),(1,3,2,4),...(4,3,2,1)を求め、順にj=1,2,...24とする。
【００９５】
ステップＳ１０２において、再配置する波長の収容順序の組み合わせj=1から計算をする。
【００９６】
ステップＳ１０３において、通信網内全てのリンクlに関して、リンクlの空き波長の使用数Ul=０とする。そして、再配置する波長の順番i=1とする。
【００９７】
ステップＳ１０４において、R0,ijをjの収容順序におけるi番目の再配置対象の波長パスの経路情報とし、W0,ijをjの収容順序におけるi番目の再配置対象の波長パスの波長番号とし、Rijをjの収容順序におけるi番目の再配置先の波長パスの経路情報とし、Wijをjの収容順序におけるi番目の再配置先の波長パスの波長番号としたときに、経路R0,ij・波長W0,ijの波長パスの再配置先の経路Rij・波長Wijに既存波長パスが存在するか否かを判別する。既存波長パスが存在する場合には、ステップＳ１０５に進み、既存波長パスが存在しない場合には、ステップＳ１１２に進む。
【００９８】
ステップＳ１０５において、再配置先の波長パスが既存波長パスに使用されているため、既存波長パスに使われている波長Wijを、一時的に空き波長Wc,ijに退避させる。具体的には、リンクlにおける空き波長数をClとし、Wijに既存波長パスが存在していたときのWijの変更先の波長番号をWc,ijとすると、Clの空き波長の中から変更先の波長番号Wc,jiを見つけ、既存波長パスに使われている波長Wijを、経路Rijの変更先の波長Wc,ijに変更する。そして、Rijの全てのリンクにおいてUl→Ul+１とする。
【００９９】
ステップＳ１０６において、通信網内全てのリンクに関して、ClとUlとを比較する。Cl≧Ulである場合、既存波長パスに使われている波長Wijを、一時的に空き波長Wc,ijに退避させることができるため、ステップＳ１０７に進み、Cl＜Ulである場合、ステップＳ１０９に進む。
【０１００】
ステップＳ１０７において、jの収容順序における最後の順番の波長まで計算したか否かを判別する（i=N ?）。i=Nの場合、最後の順番の波長まで計算したことになり、ステップＳ１０８に進む。i≠Nの場合、最後の順番の波長まで計算していないため、ステップＳ１１４に進む。
【０１０１】
ステップＳ１０８において、再配置する波長の収容順序jを出力する。
【０１０２】
ステップＳ１０９において、再配置する波長の順序の全ての収容順序の組み合わせの計算が終了したか否かを判別する（j=N! ?）。ｊ=N!の場合、全ての収容順序の組み合わせの計算が終了したことになり、収容順序決定手順が終了する。このとき再配置が不可能となるため、波長パス事前設計機能部において例えば数式(8)の制約を用いて再度計算を行う必要がある。j≠N!の場合、全ての収容順序の組み合わせの計算が終了していないため、ステップＳ１１０に進む。
【０１０３】
ステップＳ１１０において、ステップS105で変更した波長情報を初期化する。すなわち、経路Rijの変更先の波長Wc,ijに変更された波長を元の波長Wijに戻す。
【０１０４】
ステップＳ１１１において、j→j+1とし、ステップＳ１０３に戻る。
【０１０５】
ステップＳ１１２において、再配置対象の波長パスに使用されている波長W0,ijがステップＳ１０５で変更した波長Wc,ijであるか否かを判別する。波長W0,ijが波長Wc,ijである場合、ステップＳ１１３において、Wc,ijにおける経路Rijの全てのリンクにおいてUl→Ul−1とし、空き波長数Clを１つ増やす（Cl→Cl−1）、ステップＳ１１４に進む。波長W0,ijが波長Wc,ijでない場合、ステップＳ１１４に進む。
【０１０６】
ステップＳ１１４において、i→i+1とし、ステップＳ１０４に戻る。
【０１０７】
以上から、波長パスの収容順序が決定され、収容順序jは、収容順序管理データベース１０５に保存される。また、図１０の収容順序決定手順は、収容順序jのときにどの空き波長を用いて再配置対象の波長パスを再配置先の波長パスに変更できるかも示している。
【０１０８】
また、ステップＳ１０５とステップＳ１０６との間に以下のステップＳ１０５−２を加え、ステップＳ１０７とステップＳ１０８との間に以下のステップＳ１０７−２を加えることで、最小の空きリソースを使用して波長パスを再配置することが可能となる。
【０１０９】
ステップＳ１０５−２において、各リンクの使用リソースUlの合計使用リソースΣUlを計算し、jの収容順序における合計使用リソース数ΣUlを保存する。
【０１１０】
ステップＳ１０７において、jの収容順序における最後の順番の波長まで計算したか否かを判別する（i=N ?）。i=Nの場合、最後の順番の波長まで計算したことになり、ステップＳ１０７−２に進む。i≠Nの場合、最後の順番の波長まで計算していないため、ステップＳ１１４に進む。この場合、ステップＳ１１４において、i→i+1とし、ステップＳ１０３に戻る。
【０１１１】
ステップＳ１０７−２において、全ての収容順序の組み合わせjについて計算が終了したか否かを判別する（j=N! ?）。j=N!の場合、全ての収容順序の組み合わせjについて計算が終了したことになり、ステップ１０８において、ステップＳ１０５−２で保存したUlが最小値の場合の収容順序jを出力する。j≠N!の場合、全ての収容順序の組み合わせjについて計算が終了していないため、ステップＳ１０３に戻る。
【０１１２】
次に、パス設定機能部１０６は、波長パス収容順序決定機能部１０４で決定された収容順序jに基づいて、波長パスを設定する。パス設定機能部１０６における波長パス設定手順について、図１１を用いて説明する。ここで、パス設定機能部１０６は、空き波長を用いて再配置対象の波長パスを再配置先の波長パスに変更する。なお、再配置対象の波長パスの経路・波長と、再配置先の波長パスの経路・波長とは、再配置対象パス管理データベース１０３に保存されている。更に、空き波長（各リンクにおける空き波長番号）は、既存パス管理データベース１０１内に、空き波長情報として保存されている。更に、上位レイヤパスの収容先の波長パスの経路・波長情報と、上位レイヤパスの粒度とは、既存パス管理データベース１０１に保存されている。
【０１１３】
ステップＳ２０１において、波長パス収容順序決定機能部１０４で決定された収容順序jを取得する。まず、i=1とする。
【０１１４】
ステップＳ２０２において、R0,ijをjの収容順序におけるi番目の再配置対象の波長パスの経路情報とし、W0,ijをjの収容順序におけるi番目の再配置対象の波長パスの波長番号とし、Rijをjの収容順序におけるi番目の再配置先の波長パスの経路情報とし、Wijをjの収容順序におけるi番目の再配置先の波長パスの波長番号としたときに、経路R0,ij・波長W0,ijの波長パスの再配置先の経路Rij・波長Wijに既存波長パスが存在するか否かを判別する。既存波長パスが存在する場合には、ステップＳ２０８に進み、既存波長パスが存在しない場合には、ステップＳ２０３に進む。
【０１１５】
ステップＳ２０３において、再配置先の波長パスが空き波長であるため、再配置先の波長パスの経路Rij・波長Wijを用いて波長パスを設定する。
【０１１６】
ステップＳ２０４において、再配置対象の波長パスに収容されている上位レイヤパスと同じ粒度（及びクライアント情報）の上位レイヤパスを、ステップＳ２０３において設定した再配置先の波長パスに収容する。
【０１１７】
ステップＳ２０５において、経路R0,ij・波長W0,ijの再配置対象の波長パスを削除する。
【０１１８】
ステップＳ２０６において、全ての再配置対象の波長パスの再配置が終了したか否かを判別する。全ての再配置が終了した場合には、波長パス設定手順が終了する。全ての再配置が終了していない場合には、ステップＳ２０７において、i→i+1とし、ステップＳ２０２に戻る。
【０１１９】
ステップＳ２０８において、再配置先の波長パスが既存波長パスに使用されているため、既存波長パスに使われている波長Wijを、一時的に空き波長Wc,ijに退避させる。具体的には、空き波長Wc,ijに波長パスを設定する。
【０１２０】
ステップＳ２０９において、再配置先の経路Rij・波長Wijに存在している波長パスに収容されている上位レイヤパスと同じ粒度（及びクライアント情報）の上位レイヤパスをステップＳ２０８で設定した波長パスに収容する。
【０１２１】
ステップＳ２１０において、再配置先で既存波長パスに使われている経路Rij・波長Wijの波長パスを削除する。
【０１２２】
ステップＳ２１１において、波長Wijを波長Wc,ijに変更したため、既存波長パスに使われている波長Wijを、経路Rijの変更先の波長Wc,ijに変更すると共に、空き波長番号を更新する。そして、ステップＳ２０２に戻る。
【０１２３】
以上の波長パスの再配置の概要図を図１２に示す。図９を用いて説明したように、再配置対象の波長パスは、λ１、λ３、λ５、λ６の４本である。再配置対象の波長パス（λ６）の再配置先の波長パスが使用されていない場合、この波長パスは、再配置先の波長パスに変更することができる。従って、再配置先の波長パスを設定し、再配置対象の波長パス（λ６）に収容されている上位レイヤパスを、再配置先の波長パスに収容する。上位レイヤパスの収容が終了すると、再配置対象の波長パス（λ６）を削除する。
【０１２４】
しかし、再配置対象の波長パス（λ５）の再配置先の波長パスが既存波長パスに使用されている場合、既存波長パス（λ２）を空き波長（λ７）に退避させる。既存波長パス（λ２）と同じ経路の波長パスを空き波長（λ７）に設定し、既存波長パス（λ２）に収容されている上位レイヤパスを空き波長に設定された波長パス（λ７）に収容する。上位レイヤパスの収容が終了すると、既存波長パス（λ２）を削除する。その後、再配置対象の波長パス（λ５）を再配置先の波長パスに変更する。同様に、再配置先の波長パスを設定し、再配置対象の波長パス（λ５）に収容されている上位レイヤパスを、再配置先の波長パスに収容する。上位レイヤパスの収容が終了すると、再配置対象の波長パス（λ５）を削除する。空き波長に設定された波長パス（λ７）を再配置対象の波長パスとして、上記の処理を繰り返すことで、再配置対象の波長パスを再配置先の波長パスに無瞬断で変更することができる。
【０１２５】
次に、集中制御方式の場合に、管理装置１０からノード装置２０に対して波長パスを設定するシーケンス図を図１３に示す。
【０１２６】
ステップＳ３０１において、管理装置１０は、再配置対象の波長パスに対する再配置先の波長パスの経路・波長を決定し、始点ノードにリソース割当メッセージを送信する。ステップＳ３０２において、始点ノードは送信されてきた経路・波長情報に基づいてクロスコネクト（ＸＣ）の設定を行い、通信路設定完了通知を管理装置１０に送信する。同様に、ステップＳ３０３及びＳ３０４において、中継ノード及び終点ノードでＸＣの設定を行う。
【０１２７】
ステップＳ３０５において、終点ノードでの通信路設定完了通知の受信を契機に、再配置対象の波長パスの上位レイヤパスを再配置先波長パスに収容するため、始点ノードに上位レイヤパス設定メッセージを送信する。ステップＳ３０６において、始点ノードの波長パス選択機能部２０５は、再配置先の波長パスを選択し、信号複製機能部２０３で複製された上位レイヤパスの信号を再配置先の波長パスに収容する。全ての上位レイヤパスの収容が終了すると、始点ノードは、波長パス選択完了通知を管理装置に送信する。同様に、ステップＳ３０７において、終点ノードで再配置先の波長パスを選択し、上位レイヤパスの信号を再配置先の波長パスに収容して上位レイヤパスを開通させる。
【０１２８】
ステップＳ３０８において、全ての上位レイヤパスの波長パス選択完了通知の受信を契機に、管理装置１０は、通信路削除メッセージを始点ノード、中継ノード及び終点ノードに送信する。ステップＳ３０９、Ｓ３１０及びＳ３１１において、それぞれ始点ノード、中継ノード及び終点ノードは、ＸＣを削除し、通信路削除完了通知を管理装置１０に送信する。このようにして、再配置対象の波長パスの再配置が終了する。
【０１２９】
なお、再配置対象の波長パスを再配置先の波長パスに変更する際に、再配置先の波長パスに既存波長パスが存在する場合にも、図１３と同様にして再配置対象の波長パスを既存波長パスに変更することができる。
【０１３０】
次に、分散制御方式の場合に波長パスを設定するシーケンス図を図１４に示す。
【０１３１】
ステップＳ４０１において、始点ノードは、再配置対象の波長パスに対する再配置先の波長パスの経路・波長を決定する。ステップＳ４０２において、始点ノードは、再配置先の波長のリソース予約を行い、中継ノードのリソースを予約するため、通信路設定メッセージを中継ノードに送信する。ステップＳ４０３において、中継ノードも同様に、再配置先の波長のリソース予約を行い、終点ノードのリソースを予約するため、通信路設定メッセージを終点ノードに送信する。ステップＳ４０４において、終点ノードは、再配置先の波長のリソース予約を行い、ステップＳ４０５において、ＸＣの設定を行う。ＸＣの設定が終了すると、リソース割当メッセージを中継ノードに送信する。ステップＳ４０６において、中継ノードは、ＸＣの設定を行い、リソース割当メッセージを始点ノードに送信する。ステップＳ４０７において、始点ノードはＸＣの設定を行う。
【０１３２】
ステップＳ４０８において、始点ノードでのＸＣの設定完了を契機に、再配置先波長パスへの上位レイヤパスの収容を開始する。ステップＳ４０９において、始点ノードの波長パス選択機能部２０５は、再配置先の波長パスを選択し、信号複製機能部２０３で複製された上位レイヤパスの信号を再配置先の波長パスに収容する。全ての上位レイヤパスの収容が終了すると、始点ノードは、上位レイヤパス設定メッセージを終点ノードに送信する。同様に、ステップＳ４１０において、終点ノードで再配置先の波長パスを選択し、上位レイヤパスの信号を再配置先の波長パスに収容して上位レイヤパスを開通させる。全ての上位レイヤパスの収容が終了すると、終点ノードは、波長パス選択完了通知を始点ノードに送信する。
【０１３３】
ステップＳ４１１において、始点ノードは、波長パス選択完了通知の受信を契機に、再配置対象の波長パスの削除を開始する。ステップＳ４１２において、始点ノードは、再配置対象の波長パスのリソースを開放するためのスケジュールを生成し、通信路削除メッセージを中継ノードに送信する。ステップＳ４１３において、通信路削除メッセージ中継ノードを受信した中継ノードも同様に、再配置対象の波長パスのリソースを開放するためのスケジュールを生成し、通信路削除メッセージを終点ノードに送信する。ステップＳ４１４において、通信路削除メッセージ中継ノードを受信した終点ノードも、再配置対象の波長パスのリソースを開放するためのスケジュールを生成する。ステップＳ４１５において、終点ノードは、スケジュールに従ってＸＣを削除し、リソース開放メッセージを中継ノードに送信する。ステップＳ４１６において、中継ノードも、ＸＣを削除し、リソース開放メッセージを始点ノードに送信する。ステップＳ４１７において、始点ノードもＸＣを削除する。このようにして、再配置対象の波長パスの再配置が終了する。
【０１３４】
なお、再配置対象の波長パスを再配置先の波長パスに変更する際に、再配置先の波長パスに既存波長パスが存在する場合にも、図１４と同様にして再配置対象の波長パスを既存波長パスに変更することができる。
【０１３５】
＜第２の実施形態＞
第２の実施形態では、波長パスを再配置する場合、波長パス収容順序決定機能部１０４が、より簡単に収容順序を決定する収容順序決定手順について、図１５を用いて説明する。
【０１３６】
波長パス収容順序決定機能部１０４は、N本の再配置対象の波長パスのうち再配置先に既存の波長パスが存在していない波長M本を抽出する。例えば、図９の場合、再配置対象の波長パスλ７は、再配置先に既存の波長パスが存在しない。他の再配置対象の波長パスは、再配置先に既存の波長パスが存在する。従って、図９の場合、M=1である。このM本は、再配置先の波長パスにそのまま変更することができるため、収容順序決定手順における波長の順列数を削減することができる。
【０１３７】
より具体的には、ステップＳ５０１において、N−M本の波長パスのうち、再配置する波長の順番i=1とする。
【０１３８】
ステップＳ５０２において、R0,iをi番目の再配置対象の波長パスの経路情報とし、W0,iをjのi番目の再配置対象の波長パスの波長番号とし、Riをi番目の再配置先の波長パスの経路情報とし、Wiをi番目の再配置先の波長パスの波長番号としたときに、経路R0,i・波長W0,iの波長パスの再配置先の経路Ri・波長Wiに既存波長パスが存在するか否かを判別する。既存波長パスが存在する場合には、ステップＳ５０５において、i→i+1とし、ステップＳ５０２に戻る。既存波長パスが存在しない場合には、ステップＳ５０３に進む。
【０１３９】
ステップＳ５０３において、再配置先の波長パスが空き波長であるため、経路R0,i・波長W0,i及び波長番号iを収容順序管理データベース１０５に保存する。
【０１４０】
ステップＳ５０４において、全ての再配置対象の波長パスの収容順序を決定したか否かを判別する（i=N−M ?）。全ての再配置対象の波長パスの収容順序を決定していない場合、ステップＳ５０５において、i→i+1とし、ステップＳ５０２に戻る。決定した場合、収容順序決定手順が終了する。
【０１４１】
これを全ての再配置する波長の順番の組み合わせjについて計算する。
【０１４２】
以上のステップから、波長パスの収容順序が決定される。前述のように、第２の実施形態における再配置する波長の順番iの範囲は1≦i≦N−Mであり、再配置する波長の順番の組み合わせjの範囲は1≦j≦(N−M)!となる。
【０１４３】
＜第３の実施形態＞
第３の実施形態では、波長パスを再配置する場合について説明する。第３の実施形態では、第１の実施形態における波長パス事前設計機能部１０２で計算された波長パスの経路及び波長を用いて、収容順序を決定せずに、パス設定機能部１０６が波長パス及び上位レイヤパスを設定／削除する。例えば、空き波長が多く存在することが分かっている場合には、収容順序を決定する必要なく、再配置対象の波長パスを再配置先の波長パスに変更することができる。このような場合に、パス設定機能部１０６は、事前に収容順序を決定せずに、逐次的に波長パスを再配置することができる。
【０１４４】
図１６は、第３の実施形態に係る管理装置であり、図３の管理装置から波長パス収容順序決定機能部１０４及び収容順序管理データベース１０５を省いた装置である。
【０１４５】
波長パス事前設計機能部１０２における波長パスの再配置先の設計方法は、第１の実施形態と同じである。パス設定機能部１０６は、波長パス事前設計機能部１０２において計算されたN本の再配置対象の波長パスのうち、波長番号iが小さい順又は大きい順にパスを設定する。より具体的には、図１１のステップＳ２０１を、「N本の再配置対象の波長パスのうち、波長番号iが小さい順又は大きい順に波長パスを設定する」と変更すればよい。また、図１１の各ステップにおいてjが用いられないため、経路R0,ij・波長W0,ijを経路R0,i・波長W0,iに、経路Rij・波長Wijを経路Ri・波長Wiに変更する。管理装置１０からノード装置２０に対して波長パスを設定するシーケンス図は、図１３及び図１４と同じである。
【０１４６】
＜第４の実施形態＞
第４の実施形態では、波長パスを再配置する場合について説明する。第４の実施形態では、第１の実施形態における波長パス事前設計機能部１０２で計算された波長パスの経路及び波長を用いて、収容順序を決定せずに、パス設定機能部１０６が波長パス及び上位レイヤパスを設定／削除する。例えば、空き波長が再配置対象のパスの数より多い場合には、収容順序を決定する必要なく、再配置対象の波長パスを再配置先の波長パスに変更することができる。このような場合に、パス設定機能部１０６は、事前に収容順序を決定せずに、逐次的に波長パスを再配置することができる。第４の実施形態に係る管理装置も、図１６と同様の構成になる。
【０１４７】
第４の実施形態では、例えば図１７に示すように、再配置対象の波長パス（λ１、λ３、λ５、λ６）を空き波長（λ７、λ８、λ９、λ１０）に設定する。このとき、上位レイヤパスも空き波長に設定した波長パスに収容する。次に、再配置対象の波長パス（λ１、λ３、λ５、λ６）を削除する。そして、再配置先の波長パスを設定し、上位レイヤパスを再配置先の波長パスに収容する。最後に、空き波長に設定した波長パス（λ７、λ８、λ９、λ１０）を削除する。
【０１４８】
パス設定機能部１０６における波長パス設定手順について、図１８を用いて説明する。
【０１４９】
ステップＳ６０１において、波長パス事前設計機能部１０２からN本の再配置対象の波長パスを取得する。前述のように、N本の再配置対象の波長パスは、再配置前の波長パスの経路・波長と、波長パス事前設計機能部１０２で計算された波長パスの経路・波長との比較により取得できる。
【０１５０】
ステップＳ６０２において、空き波長にＮ本の波長パスを設定する。
【０１５１】
ステップＳ６０３において、再配置対象の波長パスに収容されている上位レイヤパスをステップＳ６０２で設定された波長パスに収容する。
【０１５２】
ステップＳ６０４において、再配置対象の波長パスを削除する。
【０１５３】
ステップＳ６０５において、波長パス事前設計機能部１０２で計算された波長パスの経路・波長を用いて、N本の再配置先の波長パスを設定する。
【０１５４】
ステップＳ６０６において、ステップＳ６０５で設定した波長パスにステップＳ６０３で設定した上位レイヤパスを収容する。
【０１５５】
ステップＳ６０７において、ステップＳ６０２で設定した波長パスを削除する。
＜第４の実施形態の変形例＞
第４の実施形態の変形例では、波長パスを再配置する場合について説明する。第４の実施形態の変形例ではまず、第１の実施形態における波長パス事前設計機能部１０２で数式(1)〜(5)を用いて計算する。計算結果から各リンクの空き波長を求めることができるので、それを用いて数式(18)の制約を加えて波長パス事前設計機能部１０２で再度計算する。
【０１５６】
【数１１】
ここでCijはリンクijの空き波長である。前記計算結果は、変更する波長よりも空き波長のほうが大きくなるため、確実に波長パスの再配置を実行することが可能となる。
【０１５７】
パス設定機能部１０６における波長パス設定手順については第４の実施形態と同じなので省略する。
【０１５８】
＜第５の実施形態＞
第５の実施形態では、波長パスを再配置する場合について説明する。第５の実施形態では、再配置対象及び再配置先の波長パスを事前に設計せずに、パス設定機能部１０６が波長パス及び上位レイヤパスを設定／削除する。例えば、通信網が複雑でない場合には、再配置対象の波長パスを逐次的に再配置することができる。
【０１５９】
図１９は、第５の実施形態に係る管理装置であり、図４の管理装置から波長パス事前設計機能部１０２、再配置対象パス管理データベース１０３、波長パス収容順序決定機能部１０４及び収容順序管理データベース１０５を省いた装置である。
【０１６０】
第５の実施形態では、例えば図２０に示すように、パス設定機能部１０６は、使用波長領域数内の波長番号の小さい順又は大きい順に未使用の空き波長の経路を検索する。検索された空き波長（λ１、λ４）が再配置予定場所になる。この再配置予定場所（λ１）に収容できる波長パスを波長番号の小さい順又は大きい順に検索する。再配置予定場所（λ１）に収容できる波長パス（λ５）が存在する場合、この波長パスを再配置対象の波長パスとし、再配置予定場所に設定する。このとき、再配置対象の波長パスに収容されている上位レイヤパスを、再配置予定場所に設定した波長パスに収容する。そして、再配置対象の波長パス（λ５）を削除する。この手順を使用波長領域数内の全ての波長番号に関して繰り返すことにより、再配置が完了する。
【０１６１】
＜第６の実施形態＞
第６の実施形態では、上位レイヤパスを再配置する場合について説明する。
【０１６２】
図２１は、本発明の第６の実施形態に係る管理装置３０のブロック図である。管理装置３０は、既存パス管理データベース３０１と、上位レイヤパス事前設計機能部３０２と、再配置対象パス管理データベース３０３と、パス設定機能部３０６と、制御信号送受信インタフェース３０７とを有する。
【０１６３】
既存パス管理データベース３０１は、通信網内に設定された既存波長パスの経路・波長情報と、通信網内の各リンクの空き波長情報と、上位レイヤパスの収容先の波長パスの経路・波長情報と、各上位レイヤパスの粒度とを管理する。既存パス管理データベース３０１は、クライアント情報（どの上位レイヤパスがどのクライアントに対応するかという情報）を管理してもよい。
【０１６４】
上位レイヤパス事前設計機能部３０２は、既存パス管理データベース３０１で管理されている情報を用いて、再配置対象の上位レイヤパスと、再配置先の上位レイヤパスとを事前に設計する。再配置先の上位レイヤパスの設計方法は、後述する。
【０１６５】
再配置対象パス管理データベース３０３は、上位レイヤパス事前設計機能部３０２から得られた再配置対象の上位レイヤパス（再配置する必要のある上位レイヤパスの再配置前の上位レイヤパス）の経路・波長と、再配置先の上位レイヤパス（再配置する必要のある上位レイヤパスの再配置後の上位レイヤパス）の経路・波長とを保存する。
【０１６６】
パス設定機能部３０６は、波長パス及び上位レイヤパスを設定／削除する。具体的には、パス設定機能部３０６は、波長パス及び上位レイヤパスの設定／削除を指示するため、制御信号送受信インタフェース３０７を介してリソース割当メッセージ、通信路設定メッセージ又は通信路削除メッセージをノード装置に送信する。また、パス設定機能部３０６は、上位レイヤパスの収容先波長パスの設定／削除を指示するため、制御信号送受信インタフェース３０７を介して上位レイヤパス設定メッセージをノード装置に送信する。なお、パス設定機能部２０６は、波長パス及び上位レイヤパスのリソースの予約（割当）又は開放（削除）情報を保存するためのリソース管理データベース（図示せず）を有してもよい。
【０１６７】
制御信号送受信インタフェース３０７は、制御信号をノード装置に送信し、また、ノード装置から制御信号を受信する。
【０１６８】
なお、ノード装置は、第１の実施形態と同じである。
【０１６９】
次に、上位レイヤパス事前設計機能部３０２における上位レイヤパスの再配置先の設計方法について説明する。この設計方法は、オフラインで事前に設計されてもよい。ここでは、整数線形計画法（ILP：integer linear programming）を用いて、再配置先の上位レイヤパスの経路を事前に設計する。
【０１７０】
上位レイヤパス事前設計機能部３０２は、以下の目的関数を最小化する波長パスの経路を計算する。
【０１７１】
【数１２】
この目的関数(11)は、通信網内で使用されている波長数（網内波長総数）を最小化するための関数である。ただし、pijwsdは、波長wが使用されているか否かを示す変数であり、始点sから終点dまでの各物理リンク(i,j)において、波長wが使用されている場合はpijwsd=1であり、波長wが使用されていない場合はpijwsd=0である。Vはノードの集合であり、Eはリンクの集合であり、Wは波長の集合（w=0,1,2,3,...,WMAX）であり、WMAXは最大波長多重数であり、これらは予め決められたパラメータである。また、pijwsdを通信装置の設備数もしくは通信装置コストとしてもよい。
【０１７２】
目的関数(11)の計算にあたり、以下の制約条件を用いる。
【０１７３】
【数１３】
【０１７４】
【数１４】
【０１７５】
【数１５】
【０１７６】
【数１６】
制約条件(12)は、始点s、終点d及び上位レイヤパスaにおいて各リンクのトラヒックフローを表す方程式（非特許文献２参照）である。ただし、Aは上位レイヤパスの集合であり、Uijasdは、上位レイヤパスaが使用されているか否かを示す変数であり、始点sから終点dまでの各物理リンク(i,j)において、上位レイヤパスaが使用されている場合はUijasd=1であり、上位レイヤパスaが使用されていない場合はUijasd=0である。また、δasdは、始点sから終点dまでの経路で上位レイヤパスaが使用されているか否かを示す。δasd=0の場合、始点sから終点dまでの経路で上位レイヤパスaが使用されていないことを示し、δasd=1の場合、始点sから始点dまでの経路で上位レイヤパスaが使用されていることを示す。また、i＜jのときΣUijwsd=ΣUijwsd、i＞jのときΣUijwsd=−ΣUjiwsdとなる。
【０１７７】
制約条件(13)は、各リンク内の上位レイヤパスの粒度の和が波長パスの容量以下とする条件である。ただし、Gaは上位レイヤパスaの粒度であり、Cijはリンク(i,j)における容量である。Gaは、既存パス管理データベース３０１内に保存された上位レイヤパスの粒度から予め求められる。
【０１７８】
制約条件(14)は、再配置後に使用される波長パス数が既存の波長パス数以下とする条件である。ただし、p0ijwsdは、再配置前に波長wが使用されているか否かを示す変数であり、始点sから終点dまでの各物理リンク(i,j)において、再配置前に波長wが使用されている場合はp0ijwsd=1であり、再配置前に波長wが使用されていない場合はp0ijwsd=0である。p0ijwsdは、既存パス管理データベース３０１内に、通信網内に設定された既存波長パスの経路・波長情報として保存されている。
【０１７９】
制約条件(15)は、始点sから終点dまでの経路で使用される上位レイヤパスの合計数が、始点sから終点dまでの上位レイヤパスの需要総数Dupper_trafficsdに等しいという条件である。ただし、Dupper_trafficsdは、始点sから終点dまでの上位レイヤパスの総数であり、既存パス管理データベース３０１内に保存された通信網内に設定された既存波長パスの経路・波長情報と、上位レイヤパスの収容先の波長パスの経路・波長情報とから予め求められる。
【０１８０】
制約条件(12)〜(15)を用いて目的関数(11)を計算することにより、再配置後の上位レイヤパスの経路Uijasdが出力される。
【０１８１】
制約条件(12)〜(15)に加えて、次の制約条件(16)〜(17)のうち１つ以上が用いられてもよい。
【０１８２】
【数１７】
【０１８３】
【数１８】
制約条件(16)は、再配置対象の上位レイヤパスの数が既存の上位レイヤパスの合計数のうち所定の割合Rを超えないようにする条件である。すなわち、制約条件(16)は、再配置対象の上位レイヤパスの数が所定の閾値を超えないようにする条件である。ただし、Rは再配置する上位レイヤパスの割合であり、予め決められたパラメータである。また、U0ijasdは、再配置前に上位レイヤパスaが使用されているか否かを示す変数であり、始点sから終点dまでの各物理リンク(i,j)において、再配置前に上位レイヤパスaが使用されている場合はU0ijasd=1であり、再配置前に上位レイヤパスaが使用されていない場合はU0ijasd=0である。U0ijasdは、既存パス管理データベース３０１内に、通信網内に設定された既存波長パスの経路・波長情報と、上位レイヤパスの収容先の波長パスの経路・波長情報とから予め求められる。
【０１８４】
制約条件(17)は、再配置前の始点sから終点dの経路ホップ数と再配置後の経路ホップ数との差が遅延差又は距離差の限界Hdelayを満たすホップ数以下であるとする条件である。ただし、Hdelayは、許容される最大の遅延差又は距離差を満たすホップ数であり、予め決められたパラメータである。
【０１８５】
制約条件(16)を用いることにより、再配置対象の上位レイヤパスの数を制限することができる。また、制約条件(17)を用いることにより、パスを切り替える際のバッファメモリの許容範囲内での経路選択が可能になる。
【０１８６】
上位レイヤパス事前設計機能部３０２は、線形計画法（ILP）により目的関数を最小化する上位レイヤパスの経路Uijasdを求め、再配置対象の上位レイヤパスの経路と、再配置先の上位レイヤパスの経路とを再配置対象パス管理データベース３０３に保存する。なお、再配置対象の上位レイヤパスは、再配置前の上位レイヤパスの経路と、目的関数を最小化する上位レイヤパスの経路との比較により抽出することができる。
【０１８７】
パス設定機能部３０６は、再配置対象の上位レイヤパスを再配置先の上位レイヤパスに変更する。なお、波長パスとは異なり、上位レイヤパスの場合収容順序は予め決定する必要はない。パス設定機能部３０６における上位レイヤパス設定手順について、図２２を用いて説明する。なお、再配置対象の上位レイヤパスの経路と、再配置先の上位レイヤパスの経路とは、再配置対象パス管理データベース３０３に保存されている。更に、上位レイヤパスの粒度は、既存パス管理データベース３０１に保存されている。
【０１８８】
まず、ステップＳ７０１において、N本の再配置対象の上位レイヤパスの収容順序を任意の順番で決定する。なお、上位レイヤパスの収容順序は、波長の小さい順番又は大きい順序に決定されてもよい。N本の上位レイヤパスのうち、再配置する上位レイヤパスの順番i=1とする。
【０１８９】
ステップＳ７０２において、再配置対象の上位レイヤパスと同じ上位レイヤパスを再配置先に設定する。
【０１９０】
ステップＳ７０３において、再配置対象の上位レイヤパスを削除する。
【０１９１】
ステップＳ７０４において、全ての再配置対象の上位レイヤパスの再配置が終了したか否かを判別する（i=N ?）。再配置が終了していない場合（i≠N）、ステップＳ７０５において、i→i+1として、ステップＳ７０２に戻る。再配置が終了した場合（i≠N）、ステップＳ７０６に進む。
【０１９２】
ステップＳ７０６において、上位レイヤパスを収容していない波長パスが存在するか否かを判別する。存在する場合、ステップＳ７０７に進み、存在していない場合、上位レイヤパス設定手順が終了する。
【０１９３】
ステップＳ７０７において、上位レイヤパスを収容していない波長パスを削除する。
【０１９４】
次に、集中制御方式の場合に、管理装置３０からノード装置２０に対して上位レイヤパスを設定するシーケンス図を図２３に示す。
【０１９５】
ステップＳ８０１において、管理装置３０は、再配置対象の上位レイヤパスに対する再配置先の上位レイヤパスの経路を決定し、また、上位レイヤパスを収容する波長パスを決定する。管理装置３０は、始点ノードに上位レイヤパス設定メッセージを送信する。ステップＳ８０２において、始点ノードの波長パス選択機能部２０５は、送信されてきた経路情報に基づいて再配置先の波長パスを選択し、信号複製機能部２０３で複製された上位レイヤパスの信号を再配置先の波長パスに収容する。上位レイヤパスの収容が終了すると、始点ノードは、波長パス選択完了通知を管理装置に送信する。同様に、ステップＳ８０３において、終点ノードで再配置先の波長パスを選択し、上位レイヤパスの信号を再配置先の波長パスに収容して上位レイヤパスを開通させる。
【０１９６】
ステップＳ８０４において、全ての上位レイヤパスの波長パス選択完了通知の受信を契機に、管理装置３０は、再配置対象の上位レイヤパスを削除するため、上位レイヤパス削除メッセージを始点ノードに送信する。ステップＳ８０５において、始点ノードは、上位レイヤパスを削除し、上位レイヤパス削除完了通知を管理装置に送信する。
【０１９７】
ステップＳ８０６において、全ての上位レイヤパスの上位レイヤパス削除完了通知の受信を契機に、管理装置３０は、上位レイヤパスを収容していない波長パスを削除する。このため、管理装置３０は、通信路削除メッセージを始点ノード、中継ノード及び終点ノードに送信する。ステップＳ８０７、Ｓ８０８及びＳ８０９において、それぞれ始点ノード、中継ノード及び終点ノードは、ＸＣを削除し、通信路削除完了通知を管理装置３０に送信する。このようにして、再配置対象の上位レイヤパスの再配置が終了する。
【０１９８】
次に、分散制御方式の場合に上位レイヤパスを設定するシーケンス図を図２４に示す。
【０１９９】
ステップＳ９０１において、始点ノードは、再配置対象の上位レイヤパスに対する再配置先の上位レイヤパスの経路を決定し、また、上位レイヤパスを収容する波長パスを決定する。ステップＳ９０２において、始点ノードの波長パス選択機能部２０５は、決定された経路情報に基づいて再配置先の波長パスを選択し、信号複製機能部２０３で複製された上位レイヤパスの信号を再配置先の波長パスに収容する。上位レイヤパスの収容が終了すると、始点ノードは、上位レイヤパス設定メッセージを終点ノードに送信する。ステップＳ９０３において、同様に終点ノードで再配置先の波長パスを選択し、上位レイヤパスの信号を再配置先の波長パスに収容して上位レイヤパスを開通させる。終点ノードは、波長パスの選択が完了すると、波長パス選択完了通知を始点ノードに送信する。
【０２００】
ステップＳ９０４において、全ての上位レイヤパスの波長パス選択完了通知の受信を契機に、始点ノードは、再配置対象の上位レイヤパスの削除を開始する。ステップＳ９０５において、始点ノードは、再配置対象の上位レイヤパスを削除する。
【０２０１】
ステップＳ９０６において、全ての上位レイヤパスの上位レイヤパスの削除が完了すると、始点ノードは、上位レイヤパスを収容していない波長パスの削除を開始する。始点ノードは、再配置対象の波長パスのリソースを開放するためのスケジュールを生成し、通信路削除メッセージを中継ノードに送信する。ステップＳ９０７において、通信路削除メッセージ中継ノードを受信した中継ノードも同様に、再配置対象の波長パスのリソースを開放するためのスケジュールを生成し、通信路削除メッセージを終点ノードに送信する。ステップＳ９０８において、通信路削除メッセージ中継ノードを受信した終点ノードも、再配置対象の波長パスのリソースを開放するためのスケジュールを生成する。ステップＳ９０９において、終点ノードは、スケジュールに従ってＸＣを削除し、リソース開放メッセージを中継ノードに送信する。ステップＳ９１０において、中継ノードも、ＸＣを削除し、リソース開放メッセージを始点ノードに送信する。ステップＳ９１１において、始点ノードもＸＣを削除する。このようにして、再配置対象の上位レイヤパスの再配置が終了する。
【０２０２】
なお、上位レイヤパスに更に上位レイヤパスが収容されている場合（例えば、３Ｇ上位レイヤパスに３本の１Ｇ上位レイヤパスが収容されている場合）、上記の数式(11)〜(17)の「波長パス」を「上位レイヤパス」に変更することで、複数の上位レイヤパスの再配置が可能になる。
【０２０３】
＜第７の実施形態＞
第７の実施形態では、上位レイヤパスを再配置する場合について説明する。第７の実施形態では、再配置対象及び再配置先の上位レイヤパスを事前に設計せずに、パス設定機能部３０６が上位レイヤパスを設定／削除する。例えば、通信網が複雑でない場合には、再配置対象の上位レイヤパスを逐次的に再配置することができる。
【０２０４】
図２５は、第７の実施形態に係る管理装置３０であり、図２１の管理装置３０から上位レイヤパス事前設計機能部３０２及び再配置対象パス管理データベース３０３を省いた装置である。
【０２０５】
パス設定機能部３０６における上位レイヤパス設定手順について、図２６を用いて説明する。
【０２０６】
ここでは、N本の波長パス内の上位レイヤパスを再配置するものとする。ステップＳ１００１において、波長パス内の使用帯域量が多い順番に波長を並び替え、順にiとする（1≦i≦N）。なお、波長パス内の使用帯域量は、波長パスに収容されている上位レイヤパスの粒度の合計である。更に、波長パス内の使用帯域量が少ない順番に波長を並び替え、順にjとする（1≦j≦N）。
【０２０７】
ステップＳ１００２において、j=1，i=1とする。
【０２０８】
ステップＳ１００３において、aj=1とする。ただし、ajは、j番目の波長パスに収容されている上位レイヤパスに順に付与された番号である。
【０２０９】
ステップＳ１００４において、j番目の波長パスに収容されている上位レイヤパスajと同じ経路であり、i番目の波長パス内の空き容量をCiとしたときに、Ci≧Cjを満たす波長パスをi番目の波長パスから検索する。なお、上位レイヤパスと同じ経路の波長パスとは、上位レイヤパスと同じ始点及び終点ノードを有する波長パスのことを言う。
【０２１０】
ステップＳ１００５において、上位レイヤパスajを収容可能な波長パスが存在するか否かを判別する。存在する場合、ステップＳ１００６に進み、存在しない場合、ステップＳ１００１に進む。
【０２１１】
ステップＳ１００６において、j番目の波長パスの上位レイヤパスajをi番目の波長パスに収容する。
【０２１２】
ステップＳ１００７において、j番目における全ての上位レイヤパスの収容の検索が完了したか否かを判別する。完了した場合、ステップＳ１００８に進み、完了していない場合、ステップＳ１０１３において、aj→aj+1として、ステップＳ１００４に戻る。
【０２１３】
ステップＳ１００８において、j番目の波長パスに収容されている上位レイヤパスが存在するかを判別する。存在しない場合、ステップＳ１００９に進み、存在する場合、ステップＳ１０１０に進む。
【０２１４】
ステップＳ１００９において、上位レイヤパスを収容していない波長パスを削除する。
【０２１５】
ステップＳ１０１０において、i+j=Nであるか否かを判別する。i+j=Nである場合、計算終了となる。i+j≠Nである場合、全ての波長パスを検索していないため、ステップＳ１０１４に進む。
【０２１６】
ステップＳ１０１１において、i+j=Nであるか否かを判別する。i+j=Nである場合、計算終了となる。i+j≠Nである場合、ステップＳ１０１２において、i→i+1として、ステップＳ１００４に戻る。
【０２１７】
以上の手順により、上位レイヤパスの再配置が終了する。
【０２１８】
＜第８の実施形態＞
第８の実施形態では、上位レイヤパスと波長パスとの双方の再配置を行う場合について説明する。
【０２１９】
まず、上位レイヤパスの再配置から行い、その後、波長パスの再配置を行う。これは、第１〜第５の実施形態と、第６〜第７の実施形態との組み合わせである。
【０２２０】
図２７は、第８の実施形態に係る管理装置であり、図４の管理装置と図２１の管理装置とを組み合わせた装置である。図４、図２１と同一構成部分には同一符号を付し、その説明を省略する。
【０２２１】
図２７の管理装置での上位レイヤパス及び波長パスの再配置手順を図２８に示す。
【０２２２】
ステップＳ１１０１において、上位レイヤパス事前設計機能部は、上位レイヤパスの再配置計算を行う。この具体的な手順は、第６〜第７の実施形態に示した通りである。
【０２２３】
ステップＳ１１０２において、再配置計算によって、削除可能な波長パスが存在するか否かを判別する。削除可能な波長パスが存在する場合、ステップＳ１１０３に進み、存在しない場合、ステップＳ１１０４に進む。
【０２２４】
ステップＳ１１０３において、上位レイヤパスを再配置する。この具体的な手順は、第６〜第７の実施形態に示した通りである。
【０２２５】
ステップＳ１００４において、波長パスを再配置する。この具体的な手順は、第１〜第５の実施形態に示した通りである。
【０２２６】
＜第９の実施形態＞
第９の実施形態では、波長パス収容順序決定機能部１０４において、再配置対象の波長パスを再配置先の波長パスに変更するためのオペレーション数を最小化する計算方法について説明する。
【０２２７】
オペレーション数を最小化するため、図１０を参照して説明した収容順序決定手順において、再配置対象の波長パスを再配置先の波長パスに変更するためのオペレーション数を求め、複数の収容順序が決定された場合、オペレーション数の少ない収容順序を選択する。
【０２２８】
図２９は、第９の実施形態に係る管理装置における収容順序決定手順を示す図である。第９の実施形態の基本的なステップは図１０と同じであるが、ステップＳ１０２'、Ｓ１０５'、Ｓ１１４'にオペレーション数の計算が追加され、ステップＳ１１５'及びＳ１１６'が新たに追加されている。
【０２２９】
ステップＳ１０２'において、オペレーション数p=０とする。
【０２３０】
ステップＳ１０５'において、既存パスに使われている波長を空き波長に変更する場合、オペレーション数p→p+2とする。オペレーション数が２回増える理由は、再配置先の波長を一度空き波長に退避させる必要があるためである。
【０２３１】
ステップＳ１１４'においてp→p+1とする。
【０２３２】
ステップＳ１０７においてi=Nの場合に、ステップ１１５'に進み、組み合わせjにおけるオペレーション数p[j]を１つ前のオペレーション数の計算結果P[j-1]と比較する。p[j]とP[j-1]とのうち値が小さいものをP[j-1]とし、その収容順序を保存し、値が大きいものに対応する収容順序は破棄する。
【０２３３】
ステップＳ１１６'において、全ての計算が終了した時点で最小のオペレーション数P[j-1]に対応する収容順序を出力する。
【０２３４】
このように、空き波長を用いて波長パスを再配置するための収容順序を決定する際に、オペレーション数が大きい収容順序を破棄することにより、オペレーション数を最小化することができると共に、計算メモリ量を削減することができる。
【０２３５】
＜第１０の実施形態＞
第１０の実施形態では、波長パスを再配置する場合について説明する。第１０の実施形態では、再配置対象及び再配置先の波長パスを事前に設計せずに、パス設定機能部１０６が波長パス及び上位レイヤパスを設定／削除する。例えば、通信網が複雑でない場合には、再配置対象の波長パスを逐次的に再配置することができる。第１０の実施形態に係る管理装置は、図１９と同様の構成になる。
【０２３６】
図３０は、第１０の実施形態に係る管理装置における波長パス設定手順を示す図である。
【０２３７】
まず、ステップＳ１２０１において、パス設定機能部１０６は、各リンクの波長割当状況を取得する。第１０の実施形態では、図３１に示すように、波長割当状況としてリンク毎の波長の使用／未使用を管理する。例えば、図３１（１）に示すような２×３の格子網の物理トポロジの場合、ノード０とノード１との間のリンク０−１において、波長λ０〜λ１０が使用されているか否かを管理する。波長が使用されている場合、波長パス識別番号も管理する。ここでは、図３１（２）のような波長割当状況を仮定する。ただし、行を波長とし、列をリンク番号とし、波長を使用しているリンクを網掛けで表し、使用していないリンクを空白で表し、枠内の番号を波長パス識別番号とする。例えば、λ２のパス識別番号２は、リンク１−２及びリンク２−５の経路を使用することがわかる。
【０２３８】
ステップＳ１２０２において、パス設定機能部１０６は、波長割当状況において、空き波長が少ない順に波長を並び替える。すなわち、波長を使用していないリンク数が少ない順に波長を並び替える。なお、波長を使用していないリンク数が大きい順に並び替えてもよい。
【０２３９】
ステップＳ１２０３において、パス設定機能部１０６は、空き波長が多い順に移設可能な波長パスを検索する。すなわち、波長を使用してないリンク数が大きい順に、波長パスを再配置先のリンクを検索する。
【０２４０】
ステップＳ１２０４において、検索された再配置先のリンクに波長パスを再配置する。
【０２４１】
ステップＳ１２０５において、上記の手順を移設可能な波長パスが存在しなくなるまで繰り返す。
【０２４２】
図３２は、第１０の実施形態に係る管理装置における波長パスの再配置を示す図である。
【０２４３】
図３２（１）に示すような波長割当状況は、波長を使用していないリンク数が少ない順に並び替えられる。例えば、波長λ２を使用していないリンク数は１であるため、波長割当状況の先頭に並び替えられる。この例では、波長は、λ２、λ３、λ７、λ１０、λ８、λ５の順に並び替えられる。なお、波長λ４、λ６、λ９及びλ１のように、全てのリンクで波長が使用されている場合には、再配置による波長数の削減は見込めないため、波長割当状況の最後に並び替えられてもよい。
【０２４４】
波長を使用していないリンク数が最も大きいものは波長λ５であるため、波長λ５を使用している波長パスの再配置先のリンクを検索する。波長λ５を使用している識別番号８の波長パスは、波長λ３に再配置することができ、波長λ５を使用している識別番号９の波長パスは、波長λ１０に再配置することができる。なお、識別番号１５の波長パスのように波長λ８を複数のリンクで使用している場合、これらの複数のリンクに共通して空きのある波長を検索して再配置する。この例では、識別番号１５の波長パスは、波長λ１０に再配置できる。これを繰り返すことにより、波長パスの再配置が終了する。
【０２４５】
＜第１１の実施形態＞
第１１の実施形態では、波長パス事前設計機能部１０２において、波長パスの再配置先を設計する際の整数線形計画法の計算量を削減する例について説明する。
【０２４６】
波長パス事前設計機能部１０２は、通信網内のいずれかのリンクで使用されている波長について、再配置対象の波長パスと、再配置先の波長パスとを設計する。すなわち、全てのリンクで使用されていない波長については、計算の対象から除外する。
【０２４７】
例えば、図３３に示すような波長割当状況は、全てのリンクで使用されていない波長λ４及びλ９を省いて並び替えられる。いずれかのリンクで波長が使用されている場合、その波長には、仮波長番号（１）〜（８）が順に付与される。この仮波長番号を用いて、波長パス事前設計機能部１０２は、波長パスの再配置先を設計することができる。なお、パス設定機能部１０６において波長を設定する場合、仮の波長番号を元の波長番号に戻して設定する。
【０２４８】
第１１の実施形態によれば、整数線形計画法の変数及び制約数が少なくなるため、計算量の削減が可能となる。
【０２４９】
＜第１２の実施形態＞
第１２の実施形態では、波長パス事前設計機能部１０２において、波長パスの再配置先を設計する際の整数線形計画法の計算量を削減する例について説明する。
【０２５０】
波長パス事前設計機能部１０２は、通信網内のいずれかのリンクに空きのある波長について、再配置対象の波長パスと、再配置先の波長パスとを設計する。すなわち、全てのリンクで使用されている波長については、計算の対象から除外する。なお、全てのリンクで使用されていない波長についても、計算の対象から除外してもよい。
【０２５１】
例えば、図３４に示すような波長割当状況は、全てのリンクで使用されている波長λ４、λ６、λ９及びλ１を省いて並び替えられる。いずれかのリンクにおいて波長に空きがある場合、その波長には、仮波長番号（１）〜（６）が順に付与される。この仮波長番号を用いて、波長パス事前設計機能部１０２は、波長パスの再配置先を設計することができる。なお、パス設定機能部１０６において波長を設定する場合、仮の波長番号を元の波長番号に戻して設定する。
【０２５２】
第１２の実施形態によれば、整数線形計画法の変数及び制約数が少なくなるため、計算量の削減が可能となる。
【０２５３】
＜第１３の実施形態＞
第１３の実施形態では、上記のいずれかの実施形態を、無瞬断切り替え機能をもつイーサネット装置で構成される通信網に適用した場合について説明する。無瞬断切り替え機能をもつイーサネット装置は、例えば特許文献２に記載されている。
【０２５４】
図３５は、第１３の実施形態に係る通信システムの概要図である。この通信システムでは、無瞬断切り替え機能をもつイーサネット装置がトランスポート装置に接続される。トランスポート装置は、イーサネット装置から受信したパケットを対向のトランスポート装置に送信する伝送装置である。
【０２５５】
上記のいずれかの実施形態で説明した管理装置が通信網に接続され、波長パス及び上位レイヤパスの設計及び再配置を行うことで、イーサネット装置間に設定されたパスを無瞬断で切り替えることが可能になる。
【０２５６】
＜第１４の実施形態＞
第１４の実施形態では、波長パス収容順序決定機能部１０４において、再配置対象の波長パスを再配置先の波長パスに変更するためのアルゴリズムを説明する。
【０２５７】
まず、再配置前後で波長パスの経路が変更しない場合について説明する。例えば図３６（１）に示すように、波長λ３の波長パスをλ５に再配置し、波長λ５の波長パスをλ４に再配置し、波長λ４の波長パスをλ６に再配置し、波長λ６の波長パスをλ３に再配置する場合を考える。波長λ６の波長パスをλ３に再配置しようとすると、λ３は使用されているため、無瞬断で再配置できない。このように波長パスの再配置先を順に辿ったときにループが生じる場合が考えられる。この場合、空き波長（例えばλ８０）を用いてループを解除し、再配置関係をツリー化する。そして、ツリーの先端（この場合はλ６）から再配置を開始することで、無瞬断での再配置が可能になる。
【０２５８】
具体的には、まず、波長λ６の波長パスを空き波長λ８０に再配置する。この再配置により、波長λ６が空き波長になり、波長λ４の波長パスをλ６に再配置することができる。同様に、波長λ５の波長パスをλ４に再配置し、次に、波長λ３の波長パスをλ５に再配置することが可能になる。そして、空き波長λ８０に退避させた波長パスをλ３に再配置することが可能になる。このように、最初にループ内のいずれかの波長パスを空き波長に退避させることで、ループを切断できる。
【０２５９】
次に、再配置前後で波長パスの経路が変更する場合について説明する。例えば図３６（２）に示すように、パス識別子１の波長パスをパス識別子１'が収容されている波長に再配置し、パス識別子３の波長パスをパス識別子４が収容されている波長及びパス識別子８が収容されている波長に再配置し、パス識別子８の波長パスをパス識別子１が収容されている波長、パス識別子３が収容されている波長及びパス識別子９が収容されている波長に再配置する場合を考える。パス識別子１の波長パスは、パス識別子１'が収容されている波長に再配置することができる。しかし、パス識別子８の波長パスをパス識別子３が収容されている波長に再配置しようとすると、その波長は使用されているため、無瞬断で再配置できない。このように波長パスの再配置先を順に辿ったときにループが生じる場合が考えられる。この場合も同様に、空き波長（例えばλ８０）を用いてループを解除し、再配置関係をツリー化する。そして、ツリーの先端（この場合はパス識別子１及び３）から再配置を開始することで、無瞬断での再配置が可能になる。
【０２６０】
具体的には、まず、パス識別子３の波長パスを空き波長λ８０に再配置する。また、パス識別子１の波長パスをパス識別子１'が収容されている波長に再配置する。この再配置により、パス識別子１が収容されている波長及びパス識別子３が収容されている波長が空き波長になり、パス識別子８の波長パスを再配置することができる。そして、空き波長λ８０に退避させた波長パスをパス識別子４が収容されている波長及びパス識別子８が収容されている波長に再配置することが可能になる。このように、最初にループ内のいずれかの波長パスを空き波長に退避させることで、ループを切断できる。
【０２６１】
＜第１５の実施形態＞
本発明における第１５の実施の形態を、図３７を用いて説明する。以下のフローで実施する。
ステップ２１００において、前述の数式（１）、もしくは後述の数式（１９）の目的関数を満たす整数線形計画法を用いて、既存波長パスの再配置演算を行う。 このとき、目的関数を満たす複数解を算出する。
【０２６２】
ステップ２２００において、再配置対象の波長パスを再配置先の波長パスに変更するための順序をステップ２１００で算出した複数解において決定する。
【０２６３】
ステップ２３００において、ステップ２２００の順序におけるパスの設定／削除するオペレーション数を算出する。
【０２６４】
ステップ２４００において、オペレーション数を比較してオペレーション数が最小の再配置波長パス並びに再配置順序を決定する。
【０２６５】
以上から目的関数を満たしかつオペレーション数が最小の解を算出可能となる。以下にステップ２１００、２２００の処理について説明をする。ステップ２１００で用いる整数線形計画法は、ノードv (ν∈V)、リンクe (e∈E)のグラフG( V, E)、波長w( w∈W)とし、制約は非特許文献２に示されたフロー保存式を用いる。
【０２６６】
＜変数＞
・Pdew：対地間ペアdの波長パスが、リンクｅにおいて波長番号wが使用される場合は1、それ以外は0
・FW： フラグメンテーション関数：
フラグメンテーション関数は、使用波長領域数を最小にするために用いる関数であり、図３に示すようにある波長に関して全リンクで使用している場合もしくは未使用の場合はコストが０で、それ以外を１とする関数を表す。
【０２６７】
＜定数＞
・P0,dew：対地間ペアdの再配置前の既存波長パスが、リンクeにおいて波長番号wが使用される場合は1、それ以外は0
・CP：波長パスコストパラメータ
・CF：フラグメンテーションコストパラメータ(0以上の実数)
・CWR：波長パス再配置コストパラメータ(0以上の実数)
＜目的関数＞
【０２６８】
【数１９】
目的関数の第１項は、波長パスを最短経路で設計することを示し、第２項は、フラグメンテーションコストを最小にするように設計することを示し、第３項は、波長パスの変更に伴うコスト値を表す。第３項における「波長パス」を「上位レイヤパス」としてもよいし、また波長パス及び上位レイヤパスの両方を考慮してもよい。また、第３項を目的関数に加えないで、式（８）や式(１６）のように変更数を所定数以下とする制約を追加して、その制約内で算出してもよい。第1項と第2項を小さくする目的関数によって使用波長領域数を削減可能となる。
【０２６９】
CPは例えば設備コストから波長１本あたりのコストを算出する方法で設定する。CFも同様に例えば設備コストから波長１本あたりのコストを算出する方法で設定する。ただし、CP 、CF ともに任意の値としてもよい。CWRは任意の値とする。また、式（１９）の第2項を、以下の式に置き換えることでフラグメンテーションが発生している波長チャネルの波長数の重み付けが可能となる。
【０２７０】
【数２０】
ここで、αは実数。
【０２７１】
例えば、リンク数が７のネットワークでCF=1、α=0.1で式（２０）のこの関数をある波長wに関して図示すると図３８のように表すことができる。
【０２７２】
以上から上記目的関数を満たす複数の解を算出する。ステップ２２００における再配置順序演算は前述の図１０で示した第1の実施形態における収容順序決定手順や図３６に示す第14の実施形態における再配置方法により行なう。
【０２７３】
[第１６の実施の形態]
本発明における第１６の実施の形態を、図３９を用いて説明する。予め算出する解の数を決めておき、第１５の実施の形態のステップ２１００の目的関数(式（１９)）の波長パス再配置コスト値CWRを、予め決めた算出する解の数まで変更して複数の解を算出する（ステップ３１０１，３１０２）。ここで再配置効果パラメータをそれぞれの解において算出する。再配置効果パラメータとは、目的関数の値、目的関数(式（１９)）の第１項と第２項の合計値、第２項においてコストが１の波長チャネルにおける波長数の合計値、設備コスト等があげられる。ステップ２２００以降は第１５の実施の形態と同様の処理をし、ステップ２４００において、再配置効果パラメータとオペレーション数がともに小さいものを選択する。
【０２７４】
[第１７の実施の形態]
本発明における第１７の実施の形態を説明する。第１５の実施の形態における図３７のステップ２３００において、例えばホップ数が大きいパスを変更するコストは、小さいものより大きくし、それらの合計をオペレーション数とする(式（2）)。もしくは、パス毎に変更コストの重み付けを行い、それらの合計をオペレーション数とする(式（3）)。
【０２７５】
[第１８の実施の形態]
本発明における第１８の実施の形態を説明する。第１６の実施の形態において、第１７の実施の形態のフロー（図３９）におけるステップ２１０１，２１０２の処理を用いたものである。
【０２７６】
[第１９の実施の形態]
本発明における第１９の実施の形態を、図４０を用いて説明する。第１の実施の形態におけるステップ２１００、ステップ２２００、ステップ２３００は同様の処理を行う。ここでステップ２１００においては複数解でなく１つの解としてもよい。次に予め算出する解の数と、オペレーション数のどちらかもしくは両方を設定しておき、設定数に達した場合はステップ２４００において、再配置効果パラメータとオペレーション数がともに小さいものを選択する。達していない場合は目的関数(式（１９)）の波長パス再配置コスト値CWRを、予め決めた算出する解の数まで変更して複数の解を算出する。
【０２７７】
第１９の実施の形態の効果を図４１に示す。ネットワーク条件は、物理トポロジは2×3格子網、論理トポロジはフルメッシュ双方向パス、上位レイヤパス及び波長パスの収容数は100本、波長パスコストCPは１、フラグメンテーションコストパラメータCFは１、波長パスに上位レイヤパス1本が収容されている条件で評価した。また、オペレーション数は第14の実施の形態を用いて算出した。図４１は波長再配置コストパラメータに対するオペレーション数（左）とフラグメンテーションが起きている波長チャネルにおける波長数（右）を表しており、この結果からCWR＝0~0.2のときにオペレーション数が小さくかつ再配置効果が大きい組み合わせを選択することができることがわかる。本実施の形態を用いることで再配置効果を保ったまま約50％のオペレーション数の削減が可能となる。
【０２７８】
[第２０の実施の形態]
本発明における第２０の実施の形態を、図４２を用いて説明する。第１４の実施の形態において、再配置前後の波長パスの移設関係をグラフツリーに表し、移設ループの小さい順番に移設させることによって、空き波長を有効に使用するための方法である。例えば、図４２のようにツリーAには２つのループが、ツリーBには１つのループが存在していた場合に、ループの数が小さいツリーBから再配置させることによって、空きリソースを有効に使用することができる。
【０２７９】
＜実施形態の効果＞
本発明の実施形態によれば、通信網内で使用されている波長領域の空き波長も含めた波長数（使用波長領域数）もしくは設備コストを削減することが可能になり、設備増設量を低減することが可能になる。
【０２８０】
例えば、図４３に示すように、上位レイヤパスを再配置することにより、上位レイヤパスを収容していない波長パスを削除することが可能になり、また複数の波長パスに跨って上位レイヤパスが設定される場合は、トランスポンダを削減することが可能となる。さらに、図４４に示すように、使用波長領域数（通信網全体で使用されている波長領域の波長数）を削減することが可能になる。
【０２８１】
また、本発明の第８の実施形態の変形例に従って波長パス及び上位レイヤパスを再配置した場合と、再配置しなかった場合との比較結果を図４６に示す。想定するノードアーキテクチャとコストモデルは図４５に示す。ノードアーキテクチャは波長パスクロスコネクト装置に複数の上位レイヤパスクロスコネクト装置が結合しており、波長パスの最大転送レート内において上位レイヤパスをマルチホップグルーミング（複数の拠点から発生する上位レイヤパスを束ねて波長パスに収容。文献：「K. Zhu and B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Select. Areas Commun., vol. 20, no. 1, pp. 122-133, Jan. 2002.」参照）することが可能であるネットワークモデルを想定する。
【０２８２】
シミュレーション条件は、以下の通り。
【０２８３】
・物理トポロジ：２×３格子網
・波長多重数：４０
・上位レイヤパスのクロスコネクト装置のポート数：３２
・波長パス1本あたりの最大転送レート：４０[Gbps]
・上位レイヤパスの転送レート種別：2.5G、10G、40G
・上位レイヤパスの転送レート別存在比率：2.5Gパス:10Gパス:40Gパス＝5:2:3
・再配置タイミング：５０本の上位レイヤパスを収容毎
・トラフィック発生条件：始点と終点のノードペアはランダム
以上のモデルにおいて、本発明の方式とパス再配置を行わなかった場合を比較した結果が図４６である。図４６はトラフィック量に対する本発明方式の相対的なコスト削減効果を表しており、本発明を用いた場合には、用いない場合に比べて最大で１２％のコスト削減効果がある。
【０２８４】
更に、本発明の実施形態によれば、波長パスの再配置及び上位レイヤパスの再配置を無瞬断で行うことができる。
【０２８５】
説明の便宜上、本発明の実施形態に係る管理装置は機能的なブロック図を用いて説明しているが、本発明の管理装置は、ハードウェア、ソフトウェア又はそれらの組み合わせで実現されてもよい。また、２以上の実施形態及び実施形態の各構成要素が必要に応じて組み合わせて使用されてもよい。
【０２８６】
上記の実施形態では、主に集中制御方式について説明しているが、分散制御方式でも同様に実現可能である。また、図５及び図６に本発明の実施形態で用いられるノード装置を示しているが、ノード装置は波長パス及び上位レイヤパスを設定する装置であれば、如何なる構成になってもよい。また、パスの事前設計及び収容順序決定は、事前に計算されずに、逐次的に計算されてもよい。同様に、逐次的な計算も、事前に行われてもよい。
【０２８７】
また、本発明の実施形態では、空き波長を用いて再配置を行っているが、予め再配置専用に空き波長を通信網内に確保しておいてもよい。
【０２８８】
以上、本発明の実施形態について説明したが、本発明は、上記の実施形態に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【産業上の利用可能性】
【０２８９】
本発明は、通信網における波長パス及び上位レイヤパスの再配置に適用可能である。
【符号の説明】
【０２９０】
１０ 管理装置
１０１ 既存パス管理データベース
１０２ 波長パス事前設計機能部
１０３ 再配置対象パス管理データベース
１０４ 波長パス収容順序決定機能部
１０５ 収容順序管理データベース
１０６ パス設定機能部
１０７ 制御信号送受信インタフェース
２０ ノード装置
２０１ 制御信号送受信インタフェース
２０２ 上位レイヤ装置接続インタフェース
２０３ 信号複製機能部
２０４ 無瞬断切り替え機能部
２０５ 波長パス選択機能部
２０６ スイッチング機能部
２０７ データ転送用インタフェース
３０ 管理装置
３０１ 既存パス管理データベース
３０２ 上位レイヤパス事前設計機能部
３０３ 再配置対象パス管理データベース
３０６ パス設定機能部
３０７ 制御信号送受信インタフェース
【特許請求の範囲】
【請求項１】
通信網内に設定された波長パスを再配置するパス再配置装置における波長パス再配置方法であって、
波長パス設計部が、通信網内の使用波長領域数を再配置前の値より小さくする計算を行うことにより、再配置先の波長パスを設計する波長パス設計ステップと、
波長パス設定部が、空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更する波長パス設定ステップと、
を有する波長パス再配置方法。
【請求項２】
収容順序決定部が、空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更するための収容順序を決定する収容順序決定ステップを更に有し、
前記波長パス設定ステップは、決定された収容順序に基づいて、再配置対象の波長パスを再配置先の波長パスに無瞬断で変更する、請求項１に記載の波長パス再配置方法。
【請求項３】
前記収容順序決定ステップは、再配置対象の波長パスを再配置先の波長パスに変更する際に、再配置先に既に波長パスが存在するか否かを判別し、再配置先に既に波長パスが存在する場合に当該波長パスを空き波長に退避させることにより、再配置対象の波長パスを再配置先の波長パスに変更することができる収容順序を決定する、請求項２に記載の波長パス再配置方法。
【請求項４】
前記収容順序決定ステップは、再配置対象の波長パスを再配置先の波長パスに変更するためのオペレーション数を求め、複数の収容順序が決定された場合、オペレーション数の少ない収容順序を選択する、請求項３に記載の波長パス再配置方法。
【請求項５】
前記波長パス設計ステップは、再配置対象の波長パス数もしくは波長数が所定の閾値を超えないという制約の範囲内で計算する、請求項１乃至４のうちいずれか１項に記載の波長パス再配置方法。
【請求項６】
前記波長パス設計ステップは、再配置対象の波長パスと再配置先の波長パスとの遅延差若しくは経路差が所定の閾値を超えないという制約、又は再配置対象の波長パスと再配置先の波長パスとの経路が変わらないという制約の範囲内で計算する、請求項１乃至５のうちいずれか１項に記載の波長パス再配置方法。
【請求項７】
前記波長パス設定ステップは、
再配置対象の波長パスを再配置先の波長パスに変更する際に、再配置先に既に波長パスが存在するか否かを判別し、
再配置先に波長パスが存在しない場合、
再配置先の波長パスを設定し、
再配置対象の波長パスに収容されている上位レイヤパスを、前記再配置先の波長パスに収容し、
上位レイヤパスの収容が完了した場合に、前記再配置先の波長パスを削除し、
再配置先に既に波長パスが存在する場合、
空き波長を用いて、再配置先の波長パスと同じ経路の波長パスを設定し、
再配置対象の波長パスに収容されている上位レイヤパスを、前記再配置先の波長パスと同じ経路の波長パスに収容し、
上位レイヤパスの収容が完了した場合に、前記再配置対象の波長パスを削除し、
前記再配置先の波長パスと同じ経路の波長パスを再配置対象の波長パスとして、当該波長パス設定ステップを繰り返す、請求項１乃至６のうちいずれか１項に記載の波長パス再配置方法。
【請求項８】
前記波長パス設計ステップは、通信網内のいずれかのリンクで使用されている波長について、通信網内の使用波長領域数を再配置前の値より小さくする計算を行う、請求項１乃至７のうちいずれか１項に記載の波長パス再配置方法。
【請求項９】
前記波長パス設計ステップは、通信網内のいずれかのリンクに空きのある波長について、通信網内の使用波長領域数を再配置前の値より小さくする計算を行う、請求項１乃至８のうちいずれか１項に記載の波長パス再配置方法。
【請求項１０】
上位レイヤパス設計部が、通信網内で使用されている波長数もしくは通信装置数もしくは通信装置コストを再配置前の値より小さくする計算を行うことにより、再配置先の上位レイヤパスを設計する上位レイヤパス設計ステップと、
上位レイヤパス設定部が、再配置対象の上位レイヤパスを再配置先の上位レイヤパスに変更する上位レイヤパス設定ステップと、
前記波長パス設定部が、上位レイヤパスを収容していない波長パスが存在する場合に、当該波長パスを削除する波長パス削除ステップと、
を更に有する、請求項１乃至９のうちいずれか１項に記載の波長パス再配置方法。
【請求項１１】
前記上位レイヤパス設計ステップは、再配置対象の上位レイヤパスの数が所定の閾値を超えないという制約の範囲内で計算する、請求項１０に記載の波長パス再配置方法。
【請求項１２】
前記上位レイヤパス設計ステップは、再配置対象の上位レイヤパスと再配置先の上位レイヤパスとの遅延差若しくは経路差が所定の閾値を超えないという制約の範囲内で計算する、請求項１０又は１１に記載の波長パス再配置方法。
【請求項１３】
通信網内に設定された波長パス内の上位レイヤパスを再配置するパス再配置装置における上位レイヤパス再配置方法であって、
上位レイヤパス設計部が、通信網内で使用されている波長数もしくは通信装置数もしくは通信装置コストを再配置前の値より小さくする計算を行うことにより、再配置先の上位レイヤパスを設計する上位レイヤパス設計ステップと、
上位レイヤパス設定部が、再配置対象の上位レイヤパスを再配置先の上位レイヤパスに変更する上位レイヤパス設定ステップと、
を有する上位レイヤパス再配置方法。
【請求項１４】
前記収容順序決定ステップは、いずれかの波長パスの再配置先を順に辿ったときにループが生じる場合、ループ内のいずれかの波長パスを空き波長に退避させることにより、収容順序を決定する、請求項３に記載の波長パス再配置方法。
【請求項１５】
前記収容順序決定ステップは、
空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更するための順序を決定してオペレーション数を算出する収容順序演算ステップと、
オペレーション数が小さい、もしくはあらかじめ決められた数のオペレーション数の範囲内で、再配置波長と再配置順序を決定するステップを有する
ことを特徴とする請求項１に記載の波長パス再配置方法。
【請求項１６】
前記波長パス設計ステップは、複数の解を算出し、
前記収容順序決定ステップにおいて、
前記複数の解それぞれに対してオペレーション数を算出する
ことを特徴とする請求項１５に記載の波長パス再配置方法。
【請求項１７】
前記波長パス設計ステップは、整数線形計画法を用いて、目的関数を満たす複数の解を算出することを特徴とする請求項１６に記載の波長パス再配置方法。
【請求項１８】
前記使用波長領域数は、使用波長領域数に１波長あたりの使用コストを乗じた数、もしくはフラグメンテーションが発生している波長領域数、もしくはフラグメンテーションが発生している波長領域数に１波長あたりの使用コストを乗じた数、もしくはフラグメンテーションが発生している波長領域数に波長チャネル内の使用波長数に応じて重みをつけた数、で表すことを特徴とする請求項１，８，９のいずれか１項に記載の波長パス再配置方法。
【請求項１９】
前記目的関数は、波長数もしくは通信装置数もしくは通信装置コストと、使用波長領域数の合計を小さくする、もしくは、波長数もしくは通信装置数もしくは通信装置コストと、使用波長領域数と、波長パスもしくは上位レイヤパスもしくは波長パス及び上位レイヤパスを変更するコストの合計を小さくすることを特徴とする請求項１７に記載の波長パス再配置方法。
【請求項２０】
前記波長パス設計ステップは、
整数線形計画法を用いて、目的関数を変更することによって複数の解を算出する
ことを特徴とする請求項１７に記載の波長パス再配置方法。
【請求項２１】
前記収容順序決定ステップにおける前記オペレーション数は、
再配置するパスそれぞれに重みをつけて合計数を算出、もしくはパスのホップ数もしくは経路長に応じて重みをつけて算出する
ことを特徴とする請求項１５に記載の波長パス再配置方法。
【請求項２２】
前記収容順序決定ステップは、
再配置対象となる波長パスにおいて、再配置先を順に辿ったときのループ発生量の小さい順番に、ループ内のいずれかの波長パスを空き波長に退避させることにより、収容順序を決定する、
ことを特徴とする請求項３に記載の波長パス再配置方法。
【請求項１】
通信網内に設定された波長パスを再配置するパス再配置装置における波長パス再配置方法であって、
波長パス設計部が、通信網内の使用波長領域数を再配置前の値より小さくする計算を行うことにより、再配置先の波長パスを設計する波長パス設計ステップと、
波長パス設定部が、空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更する波長パス設定ステップと、
を有する波長パス再配置方法。
【請求項２】
収容順序決定部が、空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更するための収容順序を決定する収容順序決定ステップを更に有し、
前記波長パス設定ステップは、決定された収容順序に基づいて、再配置対象の波長パスを再配置先の波長パスに無瞬断で変更する、請求項１に記載の波長パス再配置方法。
【請求項３】
前記収容順序決定ステップは、再配置対象の波長パスを再配置先の波長パスに変更する際に、再配置先に既に波長パスが存在するか否かを判別し、再配置先に既に波長パスが存在する場合に当該波長パスを空き波長に退避させることにより、再配置対象の波長パスを再配置先の波長パスに変更することができる収容順序を決定する、請求項２に記載の波長パス再配置方法。
【請求項４】
前記収容順序決定ステップは、再配置対象の波長パスを再配置先の波長パスに変更するためのオペレーション数を求め、複数の収容順序が決定された場合、オペレーション数の少ない収容順序を選択する、請求項３に記載の波長パス再配置方法。
【請求項５】
前記波長パス設計ステップは、再配置対象の波長パス数もしくは波長数が所定の閾値を超えないという制約の範囲内で計算する、請求項１乃至４のうちいずれか１項に記載の波長パス再配置方法。
【請求項６】
前記波長パス設計ステップは、再配置対象の波長パスと再配置先の波長パスとの遅延差若しくは経路差が所定の閾値を超えないという制約、又は再配置対象の波長パスと再配置先の波長パスとの経路が変わらないという制約の範囲内で計算する、請求項１乃至５のうちいずれか１項に記載の波長パス再配置方法。
【請求項７】
前記波長パス設定ステップは、
再配置対象の波長パスを再配置先の波長パスに変更する際に、再配置先に既に波長パスが存在するか否かを判別し、
再配置先に波長パスが存在しない場合、
再配置先の波長パスを設定し、
再配置対象の波長パスに収容されている上位レイヤパスを、前記再配置先の波長パスに収容し、
上位レイヤパスの収容が完了した場合に、前記再配置先の波長パスを削除し、
再配置先に既に波長パスが存在する場合、
空き波長を用いて、再配置先の波長パスと同じ経路の波長パスを設定し、
再配置対象の波長パスに収容されている上位レイヤパスを、前記再配置先の波長パスと同じ経路の波長パスに収容し、
上位レイヤパスの収容が完了した場合に、前記再配置対象の波長パスを削除し、
前記再配置先の波長パスと同じ経路の波長パスを再配置対象の波長パスとして、当該波長パス設定ステップを繰り返す、請求項１乃至６のうちいずれか１項に記載の波長パス再配置方法。
【請求項８】
前記波長パス設計ステップは、通信網内のいずれかのリンクで使用されている波長について、通信網内の使用波長領域数を再配置前の値より小さくする計算を行う、請求項１乃至７のうちいずれか１項に記載の波長パス再配置方法。
【請求項９】
前記波長パス設計ステップは、通信網内のいずれかのリンクに空きのある波長について、通信網内の使用波長領域数を再配置前の値より小さくする計算を行う、請求項１乃至８のうちいずれか１項に記載の波長パス再配置方法。
【請求項１０】
上位レイヤパス設計部が、通信網内で使用されている波長数もしくは通信装置数もしくは通信装置コストを再配置前の値より小さくする計算を行うことにより、再配置先の上位レイヤパスを設計する上位レイヤパス設計ステップと、
上位レイヤパス設定部が、再配置対象の上位レイヤパスを再配置先の上位レイヤパスに変更する上位レイヤパス設定ステップと、
前記波長パス設定部が、上位レイヤパスを収容していない波長パスが存在する場合に、当該波長パスを削除する波長パス削除ステップと、
を更に有する、請求項１乃至９のうちいずれか１項に記載の波長パス再配置方法。
【請求項１１】
前記上位レイヤパス設計ステップは、再配置対象の上位レイヤパスの数が所定の閾値を超えないという制約の範囲内で計算する、請求項１０に記載の波長パス再配置方法。
【請求項１２】
前記上位レイヤパス設計ステップは、再配置対象の上位レイヤパスと再配置先の上位レイヤパスとの遅延差若しくは経路差が所定の閾値を超えないという制約の範囲内で計算する、請求項１０又は１１に記載の波長パス再配置方法。
【請求項１３】
通信網内に設定された波長パス内の上位レイヤパスを再配置するパス再配置装置における上位レイヤパス再配置方法であって、
上位レイヤパス設計部が、通信網内で使用されている波長数もしくは通信装置数もしくは通信装置コストを再配置前の値より小さくする計算を行うことにより、再配置先の上位レイヤパスを設計する上位レイヤパス設計ステップと、
上位レイヤパス設定部が、再配置対象の上位レイヤパスを再配置先の上位レイヤパスに変更する上位レイヤパス設定ステップと、
を有する上位レイヤパス再配置方法。
【請求項１４】
前記収容順序決定ステップは、いずれかの波長パスの再配置先を順に辿ったときにループが生じる場合、ループ内のいずれかの波長パスを空き波長に退避させることにより、収容順序を決定する、請求項３に記載の波長パス再配置方法。
【請求項１５】
前記収容順序決定ステップは、
空き波長を用いて、再配置対象の波長パスを再配置先の波長パスに変更するための順序を決定してオペレーション数を算出する収容順序演算ステップと、
オペレーション数が小さい、もしくはあらかじめ決められた数のオペレーション数の範囲内で、再配置波長と再配置順序を決定するステップを有する
ことを特徴とする請求項１に記載の波長パス再配置方法。
【請求項１６】
前記波長パス設計ステップは、複数の解を算出し、
前記収容順序決定ステップにおいて、
前記複数の解それぞれに対してオペレーション数を算出する
ことを特徴とする請求項１５に記載の波長パス再配置方法。
【請求項１７】
前記波長パス設計ステップは、整数線形計画法を用いて、目的関数を満たす複数の解を算出することを特徴とする請求項１６に記載の波長パス再配置方法。
【請求項１８】
前記使用波長領域数は、使用波長領域数に１波長あたりの使用コストを乗じた数、もしくはフラグメンテーションが発生している波長領域数、もしくはフラグメンテーションが発生している波長領域数に１波長あたりの使用コストを乗じた数、もしくはフラグメンテーションが発生している波長領域数に波長チャネル内の使用波長数に応じて重みをつけた数、で表すことを特徴とする請求項１，８，９のいずれか１項に記載の波長パス再配置方法。
【請求項１９】
前記目的関数は、波長数もしくは通信装置数もしくは通信装置コストと、使用波長領域数の合計を小さくする、もしくは、波長数もしくは通信装置数もしくは通信装置コストと、使用波長領域数と、波長パスもしくは上位レイヤパスもしくは波長パス及び上位レイヤパスを変更するコストの合計を小さくすることを特徴とする請求項１７に記載の波長パス再配置方法。
【請求項２０】
前記波長パス設計ステップは、
整数線形計画法を用いて、目的関数を変更することによって複数の解を算出する
ことを特徴とする請求項１７に記載の波長パス再配置方法。
【請求項２１】
前記収容順序決定ステップにおける前記オペレーション数は、
再配置するパスそれぞれに重みをつけて合計数を算出、もしくはパスのホップ数もしくは経路長に応じて重みをつけて算出する
ことを特徴とする請求項１５に記載の波長パス再配置方法。
【請求項２２】
前記収容順序決定ステップは、
再配置対象となる波長パスにおいて、再配置先を順に辿ったときのループ発生量の小さい順番に、ループ内のいずれかの波長パスを空き波長に退避させることにより、収容順序を決定する、
ことを特徴とする請求項３に記載の波長パス再配置方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【図４１】
【図４２】
【図４３】
【図４４】
【図４５】
【図４６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【図４１】
【図４２】
【図４３】
【図４４】
【図４５】
【図４６】
【公開番号】特開２０１２−１０９９２８（Ｐ２０１２−１０９９２８Ａ）
【公開日】平成２４年６月７日（２０１２．６．７）
【国際特許分類】
【出願番号】特願２０１１−１０５７１４（Ｐ２０１１−１０５７１４）
【出願日】平成２３年５月１０日（２０１１．５．１０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年６月７日（２０１２．６．７）
【国際特許分類】
【出願日】平成２３年５月１０日（２０１１．５．１０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]