(57)【特許請求の範囲】
【請求項１】
マルチレイヤノードを有する通信網において、波長パス及び上位レイヤパスを再配置するパス再配置方法であって、
論理経路設計手段が、上位レイヤパスの論理経路を設計し、設計情報記憶手段に格納する論理経路設計ステップと、
波長パス設計手段が、前記設計情報記憶手段に格納された前記論理経路に基づいて波長パスを設計する波長パス設計ステップと、
を有し、
前記論理経路設計ステップにおいて、
既存の波長パスと対応する論理リンクがあった場合は、再配置を行わず、
前記上位レイヤパスを再配置する際には、遅延量が最大許容遅延量以下とする遅延差制約を用いるものとし、
前記波長パス設計ステップにおいて、
前記論理経路設計ステップで再配置を行わない波長パスで使用されている波長と同じ波長を優先的に用いるものとし、
前記遅延差制約は、
既存波長パスに再配置する場合には、論理経路のホップ数差に電気スイッチの処理遅延量を乗じたものの合計が前記最大許容遅延量以下であれば再配置可能とし、
論理リンクを設計する場合には、再配置前後の経路差に距離あたりの遅延量を乗じた距離遅延差と電気処理の遅延差を足し合わせた合計が前記最大許容遅延量以下であれば再配置可能とする
ことを特徴としたパス再配置方法。
【請求項２】
マルチレイヤノードを有する通信網において、波長パス及び上位レイヤパスを再配置するパス再配置装置であって、
上位レイヤパスの論理経路を設計し、設計情報記憶手段に格納する論理経路設計手段と、
前記設計情報記憶手段に格納された前記論理経路に基づいて波長パスを設計する波長パス設計手段と、
を有し、
前記論理経路設計手段は、
既存の波長パスと対応する論理リンクがあった場合は、再配置を行わず、
前記上位レイヤパスを再配置する際には、遅延量が最大許容遅延量以下とする遅延差制約を用いるものとし、
前記波長パス設計手段は、
前記論理経路設計手段で再配置を行わない波長パスで使用されている波長と同じ波長を優先的に用いるものとし、
前記遅延差制約は、
既存波長パスに再配置する場合には、論理経路のホップ数差に電気スイッチの処理遅延量を乗じたものの合計が前記最大許容遅延量以下であれば再配置可能とし、
論理リンクを設計する場合には、再配置前後の経路差に距離あたりの遅延量を乗じた距離遅延差と電気処理の遅延差を足し合わせた合計が前記最大許容遅延量以下であれば再配置可能とする
ことを特徴としたパス再配置装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パス再配置方法及び装置に係り、特に、通信網における波長パス並びに波長レイヤパスを再配置するためのパス再配置方法及び装置に関する。
【背景技術】
【０００２】
近年、映像系トラフィックやクラウドサービス等によるデータセンタ間のトラフィックによって、バックボーンネットワークにおいて、準動的なトラフィックが増大することが予想される。これによって、インターネットブラウジングや電子メール（e-mail）のような小粒度から、データセンタ間通信、LTE-A (Long Term Evolution-Advanced)のような大粒度のマルチ粒度のトラフィックが存在することになる。また、波長レイヤにおいては、波長連続制約（通過ノードで波長変換を行わない場合に同一の波長を割り当てるための制約）によって、波長パスの設定・削除を繰り返すことによって波長を効率よく使用することができなくなり、設備増設が早まることが懸念される。
【０００３】
ネットワークリソースを有効に使うためには、波長パス及び波長パスに収容するマルチ粒度の上位レイヤパスを再配置することが重要なスキームとなる。
【０００４】
考えられる最適な再配置設計方法としては、例えば非特許文献１で記載された整数線形計画法の目的関数を、「ネットワーク全体で使用するトランスポンダ数（もしくは装置数、もしくは装置コスト）の最小化」という数式にすることでマルチレイヤ・マルチ粒度上位レイヤパスの装置コスト最小の設計を得ることはできる。例えば、図１２に整数線形計画法（ILP-Integer Linear Programming）を用いた従来の再配置フローを示す。物理トポロジ、対地間毎のパス需要と粒度情報、波長多重数や最大転送帯域等の情報をもつネットワークパラメータを入力として、後述するILPを用いた設計方法の数式を計算することで波長パス及び上位レイヤパスの収容設計状況を得る。ここで収容設計状況とは、上位レイヤパスの論理リンク経路、収容先の波長パス、波長パスの経路・波長を指す。前記計算結果に基づいて既存のパスから移設を行う。
【０００５】
非特許文献１で示されている静的なトラフィックにおけるマルチレイヤ・マルチ粒度設計に関する数式を再配置設計に応用した例を以下に示す。
【０００６】
目的関数を
【０００７】
【数１】
0005639550.tif 000002
とする。
制約は下記に示す。
【０００８】
【数２】
0005639550.tif 000003
がある。
【０００９】
以下に数式の説明を示す。
【００１０】
・目的関数、式（１）： 通信網内のトランスポンダ数の最小化
以下制約の説明。
【００１１】
・式（２）、（３）：それぞれノード(i, j)間の波長パス数がノードiにおけるトランスミッタ数、ノードjにおけるレシーバ数以下とする制約；
・式（４）：ノード(i, j)間の波長パス数の合計が、同一ノード間の全波長を足し合わせたものと同等とする制約；
・式（６）〜（１０）：波長パスのフロー保存方程式を表す（フロー保存方程式は非特許文献２を参照）。
【００１２】
・式（１１）、（１２）：リンク(m, n)における波長wが論理トポロジ（上位レイヤパスの接続関係を表したトポロジ）に１つの波長パスが存在することを表す；
・式（１３）〜（１７）：上位レイヤパスのフロー保存式；
・式（１８）：グルーミングした上位レイヤパスの合計帯域が波長パスの帯域以下とする制約を表す。
【００１３】
これらにより波長パスの経路・波長、及び上位レイヤパスの論理経路が決定される。
【００１４】
上記の計算式おける記号、定数、変数は以下の通りである。
【００１５】
●記号
・ｍ，n：波長パスの始点及び終点
・ｓ，ｄ：上位レイヤパスの始点及び終点
・ｙ：上位レイヤパスの粒度
・ｔ：上位レイヤパスＩＤ
●定数
・Ｎ：ネットワークのノード数
・Ｗ：波長多重数
・Ｐ（mn）：ｍ，ｎにおけるファイバ設定状況(＝１：設定、＝０：未設定)
・Ｐ（mnw)：ｍ，ｎにおける波長ｗのファイバ使用状況  Ｐ(mnw)＝Ｐ(mn）
・C：波長１本当りの帯域
・Λ＝{Λy}：トラフィックマトリックス
●変数
・V(ij):対地間i,jにおける波長パス数
・V(ijw):対地間i,j、波長ｗの使用状況(≧１：使用、＝０：未使用)
・λ(sdtijy)：(i,j)間の波長パスに収容されている(s,d)間の粒度y、ID tの上位レイヤパス数
・TR(i)：ノードｉにおけるtransmitter数
・RR(i)：ノードｉにおけるresiver数
上記の式を解くことによって、コスト最小のマルチレイヤ・マルチ粒度の設計が可能である。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】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.
【非特許文献２】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.
【発明の概要】
【発明が解決しようとする課題】
【００１７】
しかしながら、上記非特許文献１の方式を用いた場合は、ネットワーク（NW）規模の増大に伴って計算時間が指数関数的に増大することが懸念される。このため、再配置前の既設の波長パスの設定状態及び波長パスへの上位レイヤパスの収容状態を考慮せずに、パスが全く設定していない初期状態から設計し、既設パスも再配置演算の対象とする。更に、初期状態からの設計であるので再配置順序も当然記載されていない。
【００１８】
また、非特許文献１で示されている静的なトラフィックにおけるマルチレイヤ・マルチ粒度設計に関する数式を再配置設計に適用した場合、物理経路と論理経路に関してそれぞれ制約式が必要となり計算量が膨大となる。さらに、既存の波長パス及び上位レイヤパスの収容設計状況を考慮していないため無駄な再配置を行わなければならないという問題もある。
本発明は、上記の点に鑑みなされたものであり、波長パス及びマルチ粒度の上位レイヤパスの再配置設計方法、並びに既設パスの再配置頻度を低減して再配置するための再配置順序を示すとともに計算時間を少なくするためパス再配置方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【００１９】
上記の課題を解決するため、本発明（請求項１）は、マルチレイヤノードを有する通信網において、波長パス及び上位レイヤパスを再配置するパス再配置方法であって、
論理経路設計手段が、上位レイヤパスの論理経路を設計し、設計情報記憶手段に格納する論理経路設計ステップと、
波長パス設計手段が、前記設計情報記憶手段に格納された前記論理経路に基づいて波長パスを設計する波長パス設計ステップと、
を有し、
前記論理経路設計ステップにおいて、
既存の波長パスと対応する論理リンクがあった場合は、再配置を行わず、
前記上位レイヤパスを再配置する際には、遅延量が最大許容遅延量以下とする遅延差制約を用いるものとし、
前記波長パス設計ステップにおいて、
前記論理経路設計ステップで再配置を行わない波長パスで使用されている波長と同じ波長を優先的に用いるものとし、
前記遅延差制約は、
既存波長パスに再配置する場合には、論理経路のホップ数差に電気スイッチの処理遅延量を乗じたものの合計が前記最大許容遅延量以下であれば再配置可能とし、
論理リンクを設計する場合には、再配置前後の経路差に距離あたりの遅延量を乗じた距離遅延差と電気処理の遅延差を足し合わせた合計が前記最大許容遅延量以下であれば再配置可能とする。
【発明の効果】
【００２４】
本発明では、波長パスと波長パスに収容する上位レイヤパスをそれぞれ個別に収容設計することで、計算量を低減し、更に、上位レイヤパスを収容する余地のある既設の波長パスに上位レイヤパスを収容した後に、新規の波長パスを設定することとしたため、波長パスの設計の計算量を低減することが可能となる。
【図面の簡単な説明】
【００２５】
【図１】本発明の効果を示す図である。
【図２】本発明におけるマルチレイヤノード装置例である。
【図３】本発明における概要動作のフローチャートである。
【図４】本発明の第１の実施の形態におけるパス再配置装置の構成図である。
【図５】本発明の第１の実施の形態におけるステップ１の詳細フローチャートである。
【図６】本発明の第１の実施の形態におけるステップ２の詳細フローチャートである。
【図７】本発明の第１の実施の形態におけるステップ３の詳細フローチャートである。
【図８】本発明の第１の実施の形態におけるネットワーク条件(例)である。
【図９】本発明の第１の実施の形態におけるステップ１の概要説明図(例)である。
【図１０】本発明の第１の実施の形態におけるステップ２の概要説明図(例)である。
【図１１】本発明の第１の実施の形態におけるステップ３の概要説明図（例）である。
【図１２】従来の再配置のフローチャートである。
【発明を実施するための形態】
【００２６】
以下図面と共に、本発明の実施の形態を説明する。
【００２７】
図１に本発明の効果について概要を説明する。図２に示したような波長スイッチ機能部と上位レイヤパスの電気スイッチ機能部で構成されたマルチレイヤノード装置が、各ノードに配備されていた場合に、再配置前は(図１（Ａ）)のａのように複数の上位レイヤパスが上位レイヤパスイッチ機能部で複数の拠点からのトラフィックをグルーミング（波長パスに複数の上位レイヤパスを収容）して所望のノードへ伝送される。一方波長レイヤにおいては、パスの設定・削除を繰り返すことにより、図１の再配置前（Ａ）に示すように、物理リンク毎に異なる波長チャネルを使用することで通信網全体として使用する波長チャネル数が増大する。まず、波長パスに収容する上位レイヤパスを再グルーミングすることで電気スイッチを経由しないでカットスルーをする効果によりトランスポンダを削減できる（図１（Ｂ，ａ））。また波長レイヤに関しては、通信網全体での使用波長チャネル数を低減することが可能となり(図１（Ｂ，ｂ））、将来の設備コスト増設を抑えることができる。
【００２８】
本発明では、計算時間が整数線形計画法を用いた場合に比べて大幅に削減することができ、かつ既存の波長パスと上位レイヤパスからの変更を考慮した再配置方法であることが特徴である。
【００２９】
次に、本発明の概要について説明する。本発明の処理は図３に示すように、3つのステップからなる：
ステップ１）対地間ごとに波長パス1本あたりの最大伝送容量もしくは予め設定した容量まで、複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計する。
【００３０】
ステップ２）ステップ１において収容できなかった残りの上位レイヤパスを、各物理リンクの未使用の波長に収容するように整数線形計画法もしくは発見的アルゴリズムで論理リンクを設計する。
【００３１】
ステップ３）ステップ１とステップ２で設計した論理リンクに基づいて波長パスの経路・波長を設計する。
【００３２】
次に、本発明の実施形態で用いる用語について説明する。
【００３３】
「使用波長チャネル数」とは、通信網内の少なくともいずれかの物理リンクで使用されている波長領域の空き波長を含めた波長数、すなわち、使用中の最小の波長番号から使用中の最大の波長番号までの波長数（通信網内で使用されていない波長番号を除く）のことである。
【００３４】
「上位レイヤパススイッチ機能部」とは、ODU-XC（Optical-channel Data Unit (ODU) を転送するためのスイッチ）、SDH-XC（Synchronous Digital Hierarchy（SDH）を転送するためのスイッチ））、MPLS-TPルータ（Multiprotocol Label Switching-Transport Profile（MPLS-TP）を転送するためのルータ）等の電気スイッチ機能部のことである。
【００３５】
「上位レイヤパス」とは、ODU、SDH、MPLS-TP等である。
【００３６】
「波長レイヤパス」とは物理レイヤのパスであり、光パスともいい、光の通信路のことである。
【００３７】
「グルーミング」とは、複数の上位レイヤパスを単一の波長パスに束ねることである。
【００３８】
「カットスルー」とは、電気のノードを経由しないで光のまま転送することである。「マルチレイヤノード」とは、波長スイッチと上位レイヤの電気スイッチを含んだ複数のレイヤスイッチを持つノード装置のことである。
【００３９】
「直結論理リンク」とは、始点と終点ノード間において途中で電気処理を行うノードを通過しないで光信号のまま伝送する場合のリンクのことである。
【００４０】
「直結でない論理リンク」とは、途中で電気処理を行うノードを通過するため、複数の論理リンクを通過する場合のリンクのことである。
【００４１】
「収容率」とは、(収容している全上位レイヤパスの粒度の合計)/(最大容量×波長数)のことである。
【００４２】
「波長チャネル」とは波長番号のことである。
【００４３】
「波長パスの経路・波長を設計」とは、光信号を伝送するための経路探索と波長を選択することである。
【００４４】
「ダイクストラアルゴリズム」とは最短ホップもしくは最短経路長を探索するためのアルゴリズムのことである。
【００４５】
「First Fit (FF) アルゴリズム」とは、波長番号の若番から波長割り当てを行うアルゴリズムのことである。
【００４６】
「論理経路」とは、上位レイヤパスが終端されるまでに、通過する電気処理ノード間の論理的（仮想的）な経路のことを指す。例えば始点と終点がそれぞれノード番号０、５であり、論理経路が０−３−２−５であった場合は、ノード番号３、ノード番号２それぞれで電気処理ノードを通過していることを表す。また論理リンクそれぞれに波長パスが対応し、この例の場合は対地間ペアがそれぞれ０−３、３−２、２−５に対応する波長パスが存在する。
【００４７】
[第１の実施の形態] 
図４は、本発明の第１の実施の形態におけるパス再配置装置の構成を示す。
【００４８】
同図に示す、パス再配置装置１は、入力部１０、論理経路設計部２０、波長パス設計部３０から構成される。論理経路設計部２０は、収容論理経路設計部２１、収容外論理経路設計部２２、設計情報記憶部２３から構成される。
【００４９】
入力部１０は、外部から物理トポロジの接続行列、既存の波長パスの経路、波長、及び上位レイヤパスの論理リンク経路、粒度、収容先波長パスを取得して、論理経路設計部２０に渡す。
【００５０】
論理経路設計部２０の収容論理経路設計部２１は、対地間ごとに波長パスの最大容量もしくは予め設定した容量まで1つ以上の複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計し、その設計情報を設計情報記憶部２３に格納する。
【００５１】
論理経路設計部２０の収容外論理経路設計部２２は、波長パスの最大容量もしくは予め設定した容量に収容することができなかった残りの上位レイヤパス需要に関して論理経路を設計し、その設計情報を設計情報記憶部２３に格納する。
【００５２】
波長パス設計部３０は、設計情報記憶部２３に格納された論理経路に基づいて、再配置後波長パスの経路、波長、再配置後上位レイヤパスの論理リンク経路、粒度、収容先波長パス、波長／上位レイヤパス設定順序を設計する。
【００５３】
本発明における第１の実施の形態を、図３、５〜７を用いて説明する。パス再配置装置１は、図３に示すとおり、以下のアルゴリズムフローで実施する。
●入力情報：
・物理トポロジの接続行列
・既存の波長パスの経路、波長
・上位レイヤパスの論理リンク経路、粒度、収容先波長パス
●出力情報：
・再配置後波長パスの経路、波長
・再配置後上位レイヤパスの論理リンク経路、粒度、収容先波長パス
・波長／上位レイヤパス設定順序
●動作概要：
次に、本発明のパス再配置装置１の動作概要について説明する。本発明は図３に示すように、3つのステップからなる：
ステップ１）  上記の入力情報が入力されると、論理経路設計部２０の収容論理経路設計部２１は、上記の入力情報に基づいて、対地間ごとに波長パス1本あたりの最大伝送容量もしくは予め設定した容量まで、複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計し、その設計情報を設計情報記憶部２３に格納する。
【００５４】
ステップ２）  論理経路設計部２０の収容外論理経路設計部２２は、ステップ１において収容できなかった残りの上位レイヤパスを、各物理リンクの未使用の波長に収容するように整数線形計画法もしくは発見的アルゴリズムで論理リンクを設計し、その設計情報を設計情報記憶部２３に格納する。
【００５５】
ステップ３）  ステップ１とステップ２で設計した論理リンクに基づいて波長パスの経路・波長を設計する。
【００５６】
本願と従来例との違いは、ステップ１とステップ３を備えるところにある。ステップ１とステップ３を備えるために、ステップ３で計算に用いる制約式を削減することが出来る。
【００５７】
図３のステップ１の詳細な動作のフローチャートを図５に示す。図５に示すように、ステップ１は以下の５つのステップからなる。
【００５８】
ステップ１０１）  収容論理経路設計部２１は、直結の論理リンクである既存上位レイヤパスを選択。
【００５９】
ステップ１０２）  上位レイヤパスの粒度の合計値が大きい順番にソートする。
【００６０】
ステップ１０３）  収容論理経路設計部２１は、老番から若番へ順番に移設計算をし、波長の最大粒度もしくは予め設定された帯域までグルーミング可能なパスを算出し、直結論理リンクとなる上位レイヤパスIDと収容先の波長パスの経路・波長を設計情報記憶部２３に保存する。
【００６１】
ステップ１０４）  収容論理経路設計部２１は、ステップ１０３でグルーミング不可能だった上位レイヤパスと、直結論理リンク以外の上位レイヤパスを直結論理リンクとして、同様にステップ１０２とステップ１０３の計算を行う。ただし、ステップ１０３で既存の波長パス以外に収容する場合は、波長パスの経路・波長は未決定波長パスとして識別子（ID）及び収容した上位レイヤパスの合計帯域から残帯域を保存。IDの振り方は例えば数字の若い順番に振るといった方法でよい。
【００６２】
ステップ１０５）  収容論理経路設計部２１は、直結リンクに収容できなかった上位レイヤパスの対地と需要数を算出し、設計情報記憶部２３に格納する。直結論理リンクの設計処理を終了し、ステップ２０１に移行する。
【００６３】
次に、収容外経路設計部２２における、図３のステップ２の詳細な動作のフローチャートを図６に示す。図６に示すように、ステップ２は９つのステップからなる。
【００６４】
ステップ２０１）  収容外経路設計部２２は、設計情報記憶部２３に格納された設計情報を読み出して、前述のステップ１０５で算出した上位レイヤパス需要に対して、物理リンクの最短ホップ数及び候補経路を算出する。
【００６５】
ステップ２０２）  物理経路のホップ数が小さくかつ物理経路パターンが小さい順番から論理経路を設計する。
【００６６】
ステップ２０３）  条件分岐：グルーミング可能（波長パスの空き帯域≧対象の上位レイヤパスの粒度）な既存波長パスもしくは現ステップまでに設計した論理リンクが、対象の上位レイヤパスの論理経路候補に一つ以上存在するか、それとも一つも存在しないか？一つ以上存在する場合はステップ２０４へ、一つも存在しない場合はステップ２０５へ移行する。
【００６７】
ステップ２０４）  論理経路ホップ数が小さい経路パターンを選択し、ステップ２０６に移行する。
【００６８】
ステップ２０５）  直結論理リンクを決定し（ホップ数が小さいリンクを優先）、ステップ２０８に移行する。
【００６９】
ステップ２０６）  条件分岐：同一ホップ数の複数の論理経路候補が存在する場合は、ステップ２０７に移行し、存在しない場合はステップ２０８に移行する。
【００７０】
ステップ２０７）  グルーミング可能な候補論理リンク全てに対して平均収容率を算出し、平均収容率が大きい経路を選択する。
【００７１】
ステップ２０８）  論理リンクに対応する既存波長パスが存在すればその経路・波長を設計情報記憶部２３に保存し、存在しない場合は、経路・波長が未決定波長パスとしてIDを振り、収容設計した上位レイヤパスの粒度から波長パスの残帯域を設計情報記憶部２３に保存する。
【００７２】
ステップ２０９）  条件分岐：全ての上位レイヤパス需要に関して論理経路の設計が完了した場合は当該処理を終了し、ステップ３０１に移行する。
【００７３】
次に、波長パス設計部３０における、図３のステップ３の詳細な動作のフローチャートを図７に示す。
【００７４】
図７に示すように、図３のステップ３は３つのステップからなり、未割当波長パスを割り当てる。
【００７５】
ステップ３０１）  波長パス設計部３０は、ステップ１、ステップ２で経路・波長が決定している波長パスを設計情報記憶部２３から読み出して、波長チャネル内の使用波長数が多い順番にソートする。
【００７６】
ステップ３０２）  ソートした波長チャネルの若番の波長を用いて順番に、経路・波長が未決定の波長パスIDの収容可能な経路を探索する。このとき経路数が小さいものから順番に設計する。
【００７７】
ステップ３０３）使用可能な波長が無い場合は例えばFirst-Fitアルゴリズム（波長チャネルの若番から割り当て‐文献１「H. Chang, et al., "A Review of Routing and Wavelength Assignment Approaches for Wavelength-Routed Optical WDM Networks", OPTICAL NETWORKS MAGAZINE, Vol. 47-60, January 2000.」）を用いて設計する。[0]経路は例えばダイクストラアルゴリズムを用いて最短経路で設計する。
【００７８】
以上のステップから波長パス及び上位レイヤパスの再配置設計が可能となる。
【００７９】
無瞬断で再配置を行う順序については以下の２つの場合分けによって決定される。
【００８０】
（１）上位レイヤパスを、既存の波長パスに再グルーミングするときは、対象となる上位レイヤパスを波長パスに設定し冗長路を決定した後に、対象となっている既存の上位レイヤパスを削除することで移設が可能となる。
【００８１】
（２）上位レイヤパスを、変更した波長パスに再グルーミングするときは、先に波長パスを変更先の波長パスに設定する。次に、上位レイヤパスを変更先波長パスに設定し冗長路を決定し、その後対象となっている既存の上位レイヤパスを削除することで移設が可能となる。最後に既存の波長パスに収容されている上位レイヤパスを全て移設後に波長パスを削除する。
【００８２】
上記の（１）、（２）において上位レイヤパスがSDHパスやODUパスのようなタイムスロット単位でパスを構成しているものであった場合は、遅延調整が必要となる。
【００８３】
上記の動作の具体例を図８のネットワーク条件で適用したときについて説明する。
【００８４】
ステップ1において、収容論理経路設計部２１は、始点と終点が同一対地で波長パス1本あたりの最大容量40Gまで詰めることができるパスに関しては始点と終点で直結の論理リンクを設計する。図９の例では、ノード０⇔５間の波長パス2本、40Gの上位レイヤパス2本と10Gの上位レイヤパス4本、ノード１⇔２間の波長パス１本、2.5Gの上位レイヤパス4本と10Gの上位レイヤパス4本、ノード３⇔５間の波長パス１本、10Gの上位レイヤパス4本の論理リンクが設計される。例えば、図９のノード1−ノード2のパス需要においては、直結リンクである既存の上位レイヤパスがあるため、収容粒度の大きい順番にソートし、老番から順番に最大粒度までグルーミング設計を行う。この例の場合、既存波長パスのλ７に粒度2.5のパス4本（ID：9、10、11、12）を移設する。次に、収容できなかった上位レイヤパス需要を算出し、ステップ２に進む。
【００８５】
ステップ２では、収容外論例経路設計部２２において、図１０に示すように［2-1］においては図９の［1］(直結論理リンクの決定)で算出した対地間パスそれぞれにおいて物理リンクにおける最短ホップ数と経路候補数を算出する。［2-1］から、物理リンクのホップ数が小さくかつ物理経路パターンが小さい順番に直結論理リンクを決定する。この例の場合、
<1> 2.5G上位レイヤパス2本は「1―２」、
<2>10G上位レイヤパス1本は「４―５」となる。
【００８６】
<3>ノード３⇔５に関しては論理リンク「３−４」を設定することで「３−４−５」の経路を用いてパスを収容することができる。
【００８７】
<4>ノード１⇔５に関しては候補経路が「１−２−５」と「１−４−５」の２パターンあるが、既存波長パスは1-4及び4-5で存在しているため１−４−５を選択する。
【００８８】
<5>同様にノード「０−５」は「０−３−４−５」の経路を用いてパスを収容することができる。以上の作業を全パスに関して繰り返すことで論理リンク（波長パス）を決定することができる。
【００８９】
ステップ３では、波長パス設計部３０において、ステップ１、２で決定した論理リンクに基づいて波長パスを設定する。図１１に示すようにステップ１、ステップ２において再配置を行わない波長が決定されており、波長チャネル毎の波長数を算出し波長数が大きい順番にソートする。その後若番から物理リンクのホップ数が小さいパスから順番に波長を割り当てていく。
【００９０】
従来例を再配置設計に応用した場合ではこれらを全てILPで解くことにより膨大な時間がかかる。
【００９１】
従来例だと本発明の実施の形態におけるステップ１〜３全てをILPで計算することになり、ネットワーク規模の増大に従って指数関数的に増大する。それに対して本発明は、全ステップで発見的アルゴリズムを用いることで計算量を抑えることができる。（ILPは考えられる値をしらみつぶしに調べるため（ILPの計算アルゴリズムにもよるが）計算量が膨大となる。ILPを使用しないで「発見的アルゴリズム」を用いるだけで計算量が削減できることは自明となる。）
[第２の実施の形態]
本発明における第２の実施の形態について説明をする。本発明は第1の実施の形態においてステップ１で決定した論理リンクに基づいて、ステップ３で整数線形計画法を用いて波長及び経路を決定する方法である。
【００９２】
前述の従来例を応用した数式においてはVijを決定することができていないため計算式を省くことができない。本実施の形態においては、ステップ１で論理リンクの設計を終了しているため、変数Vij及びλijysdtは定数として決定している。また再配置を行わない波長パスの経路・波長も決定しているため、一部のPmnijwも定数として決定している。前述のILPの数式において式（１３）〜（１８）の計算式は解が得られており、また式（６）〜（１１）における計算式も一部解が得られている。これにより計算するのに必要な数式を半分未満に減らすことができ、計算量を削減することが可能となる。
【００９３】
[第３の実施の形態]
本発明における第３の実施の形態について説明をする。本発明は第1及び第２の実施の形態において上位レイヤパスを再グルーミングするときの遅延差制約について考慮した形態である。
【００９４】
入力に、既存上位レイヤパスの物理経路及び論理リンク経路、各リンクの経路長、最大許容遅延量、距離あたりの遅延量、電気スイッチの処理遅延量（例えば上位レイヤパスのAdd/Dropによる処理遅延のことを指す。）、を加え再グルーミングする際に遅延差制約内での再グルーミングを行うことを特徴とする。
【００９５】
ステップ１（収容論理経路設計部２１）とステップ２(収容外論理経路設計部２２)において既存波長パスにグルーミングする場合は、論理経路のホップ数差に電気スイッチの処理遅延量を乗じたものの合計が、最大許容遅延量以下とする制約内での設計となる。
【００９６】
また、ステップ３(波長パス設計部３０)において、未決定波長パスの経路選択時に前記電気スイッチ部分の処理遅延量に経路長差の絶対値に距離あたりの遅延量を乗じたものの合計が最大許容遅延量以下とする制約を考慮したパス設計となる。
【００９７】
第１の実施の形態において、遅延差制約を考慮した実施の形態について説明する。
【００９８】
第１の実施の形態のステップ１では図５のステップ１０４にて、論理経路のホップ数差に電気スイッチの処理遅延量を乗じたものの合計（以下電気処理の遅延差）が、最大許容遅延量以下のものを選択する。遅延差制約外で選択可能なパスが無い場合は、ステップ１０５で直結リンクに収容できないものとして算出する。
【００９９】
ステップ２では図６のステップ２０５にて、論理経路ホップ数が小さくかつ電気処理の遅延差制約を満たす経路パターンを選択し、制約外のものがあれば既存パスからの再配置が不可能なパスとして保存する。同様に、ステップ２０５にて電気処理の遅延差制約があれば再配置が不可能なパスとして保存する。以上ステップ１、ステップ２において算出した再配置時の遅延差を設計情報記憶部２３に保存しておく。
【０１００】
次に、ステップ３の図７のステップ３０２及びステップ３０３にて再配置前後の経路差に距離あたりの遅延量を乗じた距離遅延差に、設計情報記憶部２３に保存した電気処理の遅延差を足し合わせた合計値が最大許容遅延差制約以下とする制約内での経路を選択する。制約内の物理経路がないパスは再配置を行わないものとする。以上から第１の実施の形態において遅延差制約を考慮した再配置が可能となる。
【０１０１】
第２の実施の形態において遅延差制約を考慮した場合は、ステップ１とステップ２において、遅延差を考慮した第１の実施の形態と同様に論理経路を決定する。ステップ３においては、経路遅延差は電気処理の遅延差よりも影響は小さいとして、第２の実施の形態のステップ３と同様に再配置演算を行う。
【０１０２】
上記の図４に示すパス再配置装置の構成要素の動作をプログラムとして構築し、パス再配置装置として利用するコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１０３】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【０１０４】
１  パス再配置装置
１０  入力部
２０  論理経路設計部
２１  収容論理経路設計部
２２  収容外論理経路設計部
２３  設計情報記憶部
３０  波長パス設計部
【図１】
0005639550.tif 000004
【図２】
0005639550.tif 000005
【図３】
0005639550.tif 000006
【図４】
0005639550.tif 000007
【図５】
0005639550.tif 000008
【図６】
0005639550.tif 000009
【図７】
0005639550.tif 000010
【図８】
0005639550.tif 000011
【図９】
0005639550.tif 000012
【図１０】
0005639550.tif 000013
【図１１】
0005639550.tif 000014
【図１２】
0005639550.tif 000015