パス再配置方法及び装置
【課題】 波長パス及びマルチ粒度の上位レイヤパスの再配置設計、並びに既設パスの再配置頻度を低減して再配置するための再配置順序を算出するための計算量を低減する。
【解決手段】 本発明は、波長パスと波長パスに収容する上位レイヤパスをそれぞれ個別に収容設計するものであり、対地間ごとに波長パスの最大容量もしくはあらかじめ設定した容量まで1つ以上の複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計し、波長パスの最大容量もしくはあらかじめ設定した容量に収容することができなかった残りの上位レイヤパス需要に関して論理経路を設計し、設計情報記憶手段に格納し、当該設計された論理経路に基づいて波長パスを設計する。
【解決手段】 本発明は、波長パスと波長パスに収容する上位レイヤパスをそれぞれ個別に収容設計するものであり、対地間ごとに波長パスの最大容量もしくはあらかじめ設定した容量まで1つ以上の複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計し、波長パスの最大容量もしくはあらかじめ設定した容量に収容することができなかった残りの上位レイヤパス需要に関して論理経路を設計し、設計情報記憶手段に格納し、当該設計された論理経路に基づいて波長パスを設計する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、パス再配置方法及び装置に係り、特に、通信網における波長パス並びに波長レイヤパスを再配置するためのパス再配置方法及び装置に関する。
【背景技術】
【0002】
近年、映像系トラフィックやクラウドサービス等によるデータセンタ間のトラフィックによって、バックボーンネットワークにおいて、準動的なトラフィックが増大することが予想される。これによって、インターネットブラウジングや電子メール(e-mail)のような小粒度から、データセンタ間通信、LTE-A (Long Term Evolution-Advanced)のような大粒度のマルチ粒度のトラフィックが存在することになる。また、波長レイヤにおいては、波長連続制約(通過ノードで波長変換を行わない場合に同一の波長を割り当てるための制約)によって、波長パスの設定・削除を繰り返すことによって波長を効率よく使用することができなくなり、設備増設が早まることが懸念される。
【0003】
ネットワークリソースを有効に使うためには、波長パス及び波長パスに収容するマルチ粒度の上位レイヤパスを再配置することが重要なスキームとなる。
【0004】
考えられる最適な再配置設計方法としては、例えば非特許文献1で記載された整数線形計画法の目的関数を、「ネットワーク全体で使用するトランスポンダ数(もしくは装置数、もしくは装置コスト)の最小化」という数式にすることでマルチレイヤ・マルチ粒度上位レイヤパスの装置コスト最小の設計を得ることはできる。例えば、図12に整数線形計画法(ILP-Integer Linear Programming)を用いた従来の再配置フローを示す。物理トポロジ、対地間毎のパス需要と粒度情報、波長多重数や最大転送帯域等の情報をもつネットワークパラメータを入力として、後述するILPを用いた設計方法の数式を計算することで波長パス及び上位レイヤパスの収容設計状況を得る。ここで収容設計状況とは、上位レイヤパスの論理リンク経路、収容先の波長パス、波長パスの経路・波長を指す。前記計算結果に基づいて既存のパスから移設を行う。
【0005】
非特許文献1で示されている静的なトラフィックにおけるマルチレイヤ・マルチ粒度設計に関する数式を再配置設計に応用した例を以下に示す。
【0006】
目的関数を
【0007】
【数1】
とする。
制約は下記に示す。
【0008】
【数2】
がある。
【0009】
以下に数式の説明を示す。
【0010】
・目的関数、式(1): 通信網内のトランスポンダ数の最小化
以下制約の説明。
【0011】
・式(2)、(3):それぞれノード(i, j)間の波長パス数がノードiにおけるトランスミッタ数、ノードjにおけるレシーバ数以下とする制約;
・式(4):ノード(i, j)間の波長パス数の合計が、同一ノード間の全波長を足し合わせたものと同等とする制約;
・式(6)〜(10):波長パスのフロー保存方程式を表す(フロー保存方程式は非特許文献2を参照)。
【0012】
・式(11)、(12):リンク(m, n)における波長wが論理トポロジ(上位レイヤパスの接続関係を表したトポロジ)に1つの波長パスが存在することを表す;
・式(13)〜(17):上位レイヤパスのフロー保存式;
・式(18):グルーミングした上位レイヤパスの合計帯域が波長パスの帯域以下とする制約を表す。
【0013】
これらにより波長パスの経路・波長、及び上位レイヤパスの論理経路が決定される。
【0014】
上記の計算式おける記号、定数、変数は以下の通りである。
【0015】
●記号
・m,n:波長パスの始点及び終点
・s,d:上位レイヤパスの始点及び終点
・y:上位レイヤパスの粒度
・t:上位レイヤパスID
●定数
・N:ネットワークのノード数
・W:波長多重数
・P(mn):m,nにおけるファイバ設定状況(=1:設定、=0:未設定)
・P(mnw):m,nにおける波長wのファイバ使用状況 P(mnw)=P(mn)
・C:波長1本当りの帯域
・Λ={Λy}:トラフィックマトリックス
●変数
・V(ij):対地間i,jにおける波長パス数
・V(ijw):対地間i,j、波長wの使用状況(≧1:使用、=0:未使用)
・λ(sdtijy):(i,j)間の波長パスに収容されている(s,d)間の粒度y、ID tの上位レイヤパス数
・TR(i):ノードiにおけるtransmitter数
・RR(i):ノードiにおけるresiver数
上記の式を解くことによって、コスト最小のマルチレイヤ・マルチ粒度の設計が可能である。
【先行技術文献】
【非特許文献】
【0016】
【非特許文献1】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.
【非特許文献2】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.
【発明の概要】
【発明が解決しようとする課題】
【0017】
しかしながら、上記非特許文献1の方式を用いた場合は、ネットワーク(NW)規模の増大に伴って計算時間が指数関数的に増大することが懸念される。このため、再配置前の既設の波長パスの設定状態及び波長パスへの上位レイヤパスの収容状態を考慮せずに、パスが全く設定していない初期状態から設計し、既設パスも再配置演算の対象とする。更に、初期状態からの設計であるので再配置順序も当然記載されていない。
【0018】
また、非特許文献1で示されている静的なトラフィックにおけるマルチレイヤ・マルチ粒度設計に関する数式を再配置設計に適用した場合、物理経路と論理経路に関してそれぞれ制約式が必要となり計算量が膨大となる。さらに、既存の波長パス及び上位レイヤパスの収容設計状況を考慮していないため無駄な再配置を行わなければならないという問題もある。
本発明は、上記の点に鑑みなされたものであり、波長パス及びマルチ粒度の上位レイヤパスの再配置設計方法、並びに既設パスの再配置頻度を低減して再配置するための再配置順序を示すとともに計算時間を少なくするためパス再配置方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【0019】
上記の課題を解決するため、本発明(請求項1)は、マルチレイヤノードを有する通信網において、波長パス及び上位レイヤパスを再配置するパス再配置方法であって、
論理経路設計手段が、上位レイヤパスの論理経路を設計し、設計情報記憶手段に格納する論理経路設計ステップと、
波長パス設計手段が、前記設計情報記憶手段に格納された前記論理経路に基づいて波長パスを設計する波長パス設計ステップと、を有する。
【0020】
また、本発明(請求項2)は、前記論理経路設計ステップにおいて、
対地間ごとに波長パスの最大容量もしくはあらかじめ設定した容量まで1つ以上の複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計する第1ステップと、
波長パスの最大容量もしくは予め設定した容量に収容することができなかった残りの上位レイヤパス需要に関して論理経路を設計する第2ステップを、含む。
【0021】
また、本発明(請求項3)は、前記論理経路設計ステップにおいて、
既存の波長パスと対応する論理リンクがあった場合は、再配置を行わない。
【0022】
また、本発明(請求項4)は、前記波長パス設計ステップにおいて、
前記論理経路設計ステップで再配置を行わない波長パスで使用されている波長と同じ波長を優先的に使用する。
【0023】
また、本発明(請求項5)は、前記波長パス設計ステップにおいて、
論理リンクに基づいて波長パスの経路・波長を、整数線形計画法を用いて設計する。
【発明の効果】
【0024】
本発明では、波長パスと波長パスに収容する上位レイヤパスをそれぞれ個別に収容設計することで、計算量を低減し、更に、上位レイヤパスを収容する余地のある既設の波長パスに上位レイヤパスを収容した後に、新規の波長パスを設定することとしたため、波長パスの設計の計算量を低減することが可能となる。
【図面の簡単な説明】
【0025】
【図1】本発明の効果を示す図である。
【図2】本発明におけるマルチレイヤノード装置例である。
【図3】本発明における概要動作のフローチャートである。
【図4】本発明の第1の実施の形態におけるパス再配置装置の構成図である。
【図5】本発明の第1の実施の形態におけるステップ1の詳細フローチャートである。
【図6】本発明の第1の実施の形態におけるステップ2の詳細フローチャートである。
【図7】本発明の第1の実施の形態におけるステップ3の詳細フローチャートである。
【図8】本発明の第1の実施の形態におけるネットワーク条件(例)である。
【図9】本発明の第1の実施の形態におけるステップ1の概要説明図(例)である。
【図10】本発明の第1の実施の形態におけるステップ2の概要説明図(例)である。
【図11】本発明の第1の実施の形態におけるステップ3の概要説明図(例)である。
【図12】従来の再配置のフローチャートである。
【発明を実施するための形態】
【0026】
以下図面と共に、本発明の実施の形態を説明する。
【0027】
図1に本発明の効果について概要を説明する。図2に示したような波長スイッチ機能部と上位レイヤパスの電気スイッチ機能部で構成されたマルチレイヤノード装置が、各ノードに配備されていた場合に、再配置前は(図1(A))のaのように複数の上位レイヤパスが上位レイヤパスイッチ機能部で複数の拠点からのトラフィックをグルーミング(波長パスに複数の上位レイヤパスを収容)して所望のノードへ伝送される。一方波長レイヤにおいては、パスの設定・削除を繰り返すことにより、図1の再配置前(A)に示すように、物理リンク毎に異なる波長チャネルを使用することで通信網全体として使用する波長チャネル数が増大する。まず、波長パスに収容する上位レイヤパスを再グルーミングすることで電気スイッチを経由しないでカットスルーをする効果によりトランスポンダを削減できる(図1(B,a))。また波長レイヤに関しては、通信網全体での使用波長チャネル数を低減することが可能となり(図1(B,b))、将来の設備コスト増設を抑えることができる。
【0028】
本発明では、計算時間が整数線形計画法を用いた場合に比べて大幅に削減することができ、かつ既存の波長パスと上位レイヤパスからの変更を考慮した再配置方法であることが特徴である。
【0029】
次に、本発明の概要について説明する。本発明の処理は図3に示すように、3つのステップからなる:
ステップ1)対地間ごとに波長パス1本あたりの最大伝送容量もしくは予め設定した容量まで、複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計する。
【0030】
ステップ2)ステップ1において収容できなかった残りの上位レイヤパスを、各物理リンクの未使用の波長に収容するように整数線形計画法もしくは発見的アルゴリズムで論理リンクを設計する。
【0031】
ステップ3)ステップ1とステップ2で設計した論理リンクに基づいて波長パスの経路・波長を設計する。
【0032】
次に、本発明の実施形態で用いる用語について説明する。
【0033】
「使用波長チャネル数」とは、通信網内の少なくともいずれかの物理リンクで使用されている波長領域の空き波長を含めた波長数、すなわち、使用中の最小の波長番号から使用中の最大の波長番号までの波長数(通信網内で使用されていない波長番号を除く)のことである。
【0034】
「上位レイヤパススイッチ機能部」とは、ODU-XC(Optical-channel Data Unit (ODU) を転送するためのスイッチ)、SDH-XC(Synchronous Digital Hierarchy(SDH)を転送するためのスイッチ))、MPLS-TPルータ(Multiprotocol Label Switching-Transport Profile(MPLS-TP)を転送するためのルータ)等の電気スイッチ機能部のことである。
【0035】
「上位レイヤパス」とは、ODU、SDH、MPLS-TP等である。
【0036】
「波長レイヤパス」とは物理レイヤのパスであり、光パスともいい、光の通信路のことである。
【0037】
「グルーミング」とは、複数の上位レイヤパスを単一の波長パスに束ねることである。
【0038】
「カットスルー」とは、電気のノードを経由しないで光のまま転送することである。「マルチレイヤノード」とは、波長スイッチと上位レイヤの電気スイッチを含んだ複数のレイヤスイッチを持つノード装置のことである。
【0039】
「直結論理リンク」とは、始点と終点ノード間において途中で電気処理を行うノードを通過しないで光信号のまま伝送する場合のリンクのことである。
【0040】
「直結でない論理リンク」とは、途中で電気処理を行うノードを通過するため、複数の論理リンクを通過する場合のリンクのことである。
【0041】
「収容率」とは、(収容している全上位レイヤパスの粒度の合計)/(最大容量×波長数)のことである。
【0042】
「波長チャネル」とは波長番号のことである。
【0043】
「波長パスの経路・波長を設計」とは、光信号を伝送するための経路探索と波長を選択することである。
【0044】
「ダイクストラアルゴリズム」とは最短ホップもしくは最短経路長を探索するためのアルゴリズムのことである。
【0045】
「First Fit (FF) アルゴリズム」とは、波長番号の若番から波長割り当てを行うアルゴリズムのことである。
【0046】
「論理経路」とは、上位レイヤパスが終端されるまでに、通過する電気処理ノード間の論理的(仮想的)な経路のことを指す。例えば始点と終点がそれぞれノード番号0、5であり、論理経路が0−3−2−5であった場合は、ノード番号3、ノード番号2それぞれで電気処理ノードを通過していることを表す。また論理リンクそれぞれに波長パスが対応し、この例の場合は対地間ペアがそれぞれ0−3、3−2、2−5に対応する波長パスが存在する。
【0047】
[第1の実施の形態]
図4は、本発明の第1の実施の形態におけるパス再配置装置の構成を示す。
【0048】
同図に示す、パス再配置装置1は、入力部10、論理経路設計部20、波長パス設計部30から構成される。論理経路設計部20は、収容論理経路設計部21、収容外論理経路設計部22、設計情報記憶部23から構成される。
【0049】
入力部10は、外部から物理トポロジの接続行列、既存の波長パスの経路、波長、及び上位レイヤパスの論理リンク経路、粒度、収容先波長パスを取得して、論理経路設計部20に渡す。
【0050】
論理経路設計部20の収容論理経路設計部21は、対地間ごとに波長パスの最大容量もしくは予め設定した容量まで1つ以上の複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計し、その設計情報を設計情報記憶部23に格納する。
【0051】
論理経路設計部20の収容外論理経路設計部22は、波長パスの最大容量もしくは予め設定した容量に収容することができなかった残りの上位レイヤパス需要に関して論理経路を設計し、その設計情報を設計情報記憶部23に格納する。
【0052】
波長パス設計部30は、設計情報記憶部23に格納された論理経路に基づいて、再配置後波長パスの経路、波長、再配置後上位レイヤパスの論理リンク経路、粒度、収容先波長パス、波長/上位レイヤパス設定順序を設計する。
【0053】
本発明における第1の実施の形態を、図3、5〜7を用いて説明する。パス再配置装置1は、図3に示すとおり、以下のアルゴリズムフローで実施する。
●入力情報:
・物理トポロジの接続行列
・既存の波長パスの経路、波長
・上位レイヤパスの論理リンク経路、粒度、収容先波長パス
●出力情報:
・再配置後波長パスの経路、波長
・再配置後上位レイヤパスの論理リンク経路、粒度、収容先波長パス
・波長/上位レイヤパス設定順序
●動作概要:
次に、本発明のパス再配置装置1の動作概要について説明する。本発明は図3に示すように、3つのステップからなる:
ステップ1) 上記の入力情報が入力されると、論理経路設計部20の収容論理経路設計部21は、上記の入力情報に基づいて、対地間ごとに波長パス1本あたりの最大伝送容量もしくは予め設定した容量まで、複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計し、その設計情報を設計情報記憶部23に格納する。
【0054】
ステップ2) 論理経路設計部20の収容外論理経路設計部22は、ステップ1において収容できなかった残りの上位レイヤパスを、各物理リンクの未使用の波長に収容するように整数線形計画法もしくは発見的アルゴリズムで論理リンクを設計し、その設計情報を設計情報記憶部23に格納する。
【0055】
ステップ3) ステップ1とステップ2で設計した論理リンクに基づいて波長パスの経路・波長を設計する。
【0056】
本願と従来例との違いは、ステップ1とステップ3を備えるところにある。ステップ1とステップ3を備えるために、ステップ3で計算に用いる制約式を削減することが出来る。
【0057】
図3のステップ1の詳細な動作のフローチャートを図5に示す。図5に示すように、ステップ1は以下の5つのステップからなる。
【0058】
ステップ101) 収容論理経路設計部21は、直結の論理リンクである既存上位レイヤパスを選択。
【0059】
ステップ102) 上位レイヤパスの粒度の合計値が大きい順番にソートする。
【0060】
ステップ103) 収容論理経路設計部21は、老番から若番へ順番に移設計算をし、波長の最大粒度もしくは予め設定された帯域までグルーミング可能なパスを算出し、直結論理リンクとなる上位レイヤパスIDと収容先の波長パスの経路・波長を設計情報記憶部23に保存する。
【0061】
ステップ104) 収容論理経路設計部21は、ステップ103でグルーミング不可能だった上位レイヤパスと、直結論理リンク以外の上位レイヤパスを直結論理リンクとして、同様にステップ102とステップ103の計算を行う。ただし、ステップ103で既存の波長パス以外に収容する場合は、波長パスの経路・波長は未決定波長パスとして識別子(ID)及び収容した上位レイヤパスの合計帯域から残帯域を保存。IDの振り方は例えば数字の若い順番に振るといった方法でよい。
【0062】
ステップ105) 収容論理経路設計部21は、直結リンクに収容できなかった上位レイヤパスの対地と需要数を算出し、設計情報記憶部23に格納する。直結論理リンクの設計処理を終了し、ステップ201に移行する。
【0063】
次に、収容外経路設計部22における、図3のステップ2の詳細な動作のフローチャートを図6に示す。図6に示すように、ステップ2は9つのステップからなる。
【0064】
ステップ201) 収容外経路設計部22は、設計情報記憶部23に格納された設計情報を読み出して、前述のステップ105で算出した上位レイヤパス需要に対して、物理リンクの最短ホップ数及び候補経路を算出する。
【0065】
ステップ202) 物理経路のホップ数が小さくかつ物理経路パターンが小さい順番から論理経路を設計する。
【0066】
ステップ203) 条件分岐:グルーミング可能(波長パスの空き帯域≧対象の上位レイヤパスの粒度)な既存波長パスもしくは現ステップまでに設計した論理リンクが、対象の上位レイヤパスの論理経路候補に一つ以上存在するか、それとも一つも存在しないか?一つ以上存在する場合はステップ204へ、一つも存在しない場合はステップ205へ移行する。
【0067】
ステップ204) 論理経路ホップ数が小さい経路パターンを選択し、ステップ206に移行する。
【0068】
ステップ205) 直結論理リンクを決定し(ホップ数が小さいリンクを優先)、ステップ208に移行する。
【0069】
ステップ206) 条件分岐:同一ホップ数の複数の論理経路候補が存在する場合は、ステップ207に移行し、存在しない場合はステップ208に移行する。
【0070】
ステップ207) グルーミング可能な候補論理リンク全てに対して平均収容率を算出し、平均収容率が大きい経路を選択する。
【0071】
ステップ208) 論理リンクに対応する既存波長パスが存在すればその経路・波長を設計情報記憶部23に保存し、存在しない場合は、経路・波長が未決定波長パスとしてIDを振り、収容設計した上位レイヤパスの粒度から波長パスの残帯域を設計情報記憶部23に保存する。
【0072】
ステップ209) 条件分岐:全ての上位レイヤパス需要に関して論理経路の設計が完了した場合は当該処理を終了し、ステップ301に移行する。
【0073】
次に、波長パス設計部30における、図3のステップ3の詳細な動作のフローチャートを図7に示す。
【0074】
図7に示すように、図3のステップ3は3つのステップからなり、未割当波長パスを割り当てる。
【0075】
ステップ301) 波長パス設計部30は、ステップ1、ステップ2で経路・波長が決定している波長パスを設計情報記憶部23から読み出して、波長チャネル内の使用波長数が多い順番にソートする。
【0076】
ステップ302) ソートした波長チャネルの若番の波長を用いて順番に、経路・波長が未決定の波長パスIDの収容可能な経路を探索する。このとき経路数が小さいものから順番に設計する。
【0077】
ステップ303)使用可能な波長が無い場合は例えばFirst-Fitアルゴリズム(波長チャネルの若番から割り当て‐文献1「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]経路は例えばダイクストラアルゴリズムを用いて最短経路で設計する。
【0078】
以上のステップから波長パス及び上位レイヤパスの再配置設計が可能となる。
【0079】
無瞬断で再配置を行う順序については以下の2つの場合分けによって決定される。
【0080】
(1)上位レイヤパスを、既存の波長パスに再グルーミングするときは、対象となる上位レイヤパスを波長パスに設定し冗長路を決定した後に、対象となっている既存の上位レイヤパスを削除することで移設が可能となる。
【0081】
(2)上位レイヤパスを、変更した波長パスに再グルーミングするときは、先に波長パスを変更先の波長パスに設定する。次に、上位レイヤパスを変更先波長パスに設定し冗長路を決定し、その後対象となっている既存の上位レイヤパスを削除することで移設が可能となる。最後に既存の波長パスに収容されている上位レイヤパスを全て移設後に波長パスを削除する。
【0082】
上記の(1)、(2)において上位レイヤパスがSDHパスやODUパスのようなタイムスロット単位でパスを構成しているものであった場合は、遅延調整が必要となる。
【0083】
上記の動作の具体例を図8のネットワーク条件で適用したときについて説明する。
【0084】
ステップ1において、収容論理経路設計部21は、始点と終点が同一対地で波長パス1本あたりの最大容量40Gまで詰めることができるパスに関しては始点と終点で直結の論理リンクを設計する。図9の例では、ノード0⇔5間の波長パス2本、40Gの上位レイヤパス2本と10Gの上位レイヤパス4本、ノード1⇔2間の波長パス1本、2.5Gの上位レイヤパス4本と10Gの上位レイヤパス4本、ノード3⇔5間の波長パス1本、10Gの上位レイヤパス4本の論理リンクが設計される。例えば、図9のノード1−ノード2のパス需要においては、直結リンクである既存の上位レイヤパスがあるため、収容粒度の大きい順番にソートし、老番から順番に最大粒度までグルーミング設計を行う。この例の場合、既存波長パスのλ7に粒度2.5のパス4本(ID:9、10、11、12)を移設する。次に、収容できなかった上位レイヤパス需要を算出し、ステップ2に進む。
【0085】
ステップ2では、収容外論例経路設計部22において、図10に示すように[2-1]においては図9の[1](直結論理リンクの決定)で算出した対地間パスそれぞれにおいて物理リンクにおける最短ホップ数と経路候補数を算出する。[2-1]から、物理リンクのホップ数が小さくかつ物理経路パターンが小さい順番に直結論理リンクを決定する。この例の場合、
<1> 2.5G上位レイヤパス2本は「1―2」、
<2>10G上位レイヤパス1本は「4―5」となる。
【0086】
<3>ノード3⇔5に関しては論理リンク「3−4」を設定することで「3−4−5」の経路を用いてパスを収容することができる。
【0087】
<4>ノード1⇔5に関しては候補経路が「1−2−5」と「1−4−5」の2パターンあるが、既存波長パスは1-4及び4-5で存在しているため1−4−5を選択する。
【0088】
<5>同様にノード「0−5」は「0−3−4−5」の経路を用いてパスを収容することができる。以上の作業を全パスに関して繰り返すことで論理リンク(波長パス)を決定することができる。
【0089】
ステップ3では、波長パス設計部30において、ステップ1、2で決定した論理リンクに基づいて波長パスを設定する。図11に示すようにステップ1、ステップ2において再配置を行わない波長が決定されており、波長チャネル毎の波長数を算出し波長数が大きい順番にソートする。その後若番から物理リンクのホップ数が小さいパスから順番に波長を割り当てていく。
【0090】
従来例を再配置設計に応用した場合ではこれらを全てILPで解くことにより膨大な時間がかかる。
【0091】
従来例だと本発明の実施の形態におけるステップ1〜3全てをILPで計算することになり、ネットワーク規模の増大に従って指数関数的に増大する。それに対して本発明は、全ステップで発見的アルゴリズムを用いることで計算量を抑えることができる。(ILPは考えられる値をしらみつぶしに調べるため(ILPの計算アルゴリズムにもよるが)計算量が膨大となる。ILPを使用しないで「発見的アルゴリズム」を用いるだけで計算量が削減できることは自明となる。)
[第2の実施の形態]
本発明における第2の実施の形態について説明をする。本発明は第1の実施の形態においてステップ1で決定した論理リンクに基づいて、ステップ3で整数線形計画法を用いて波長及び経路を決定する方法である。
【0092】
前述の従来例を応用した数式においてはVijを決定することができていないため計算式を省くことができない。本実施の形態においては、ステップ1で論理リンクの設計を終了しているため、変数Vij及びλijysdtは定数として決定している。また再配置を行わない波長パスの経路・波長も決定しているため、一部のPmnijwも定数として決定している。前述のILPの数式において式(13)〜(18)の計算式は解が得られており、また式(6)〜(11)における計算式も一部解が得られている。これにより計算するのに必要な数式を半分未満に減らすことができ、計算量を削減することが可能となる。
【0093】
[第3の実施の形態]
本発明における第3の実施の形態について説明をする。本発明は第1及び第2の実施の形態において上位レイヤパスを再グルーミングするときの遅延差制約について考慮した形態である。
【0094】
入力に、既存上位レイヤパスの物理経路及び論理リンク経路、各リンクの経路長、最大許容遅延量、距離あたりの遅延量、電気スイッチの処理遅延量(例えば上位レイヤパスのAdd/Dropによる処理遅延のことを指す。)、を加え再グルーミングする際に遅延差制約内での再グルーミングを行うことを特徴とする。
【0095】
ステップ1(収容論理経路設計部21)とステップ2(収容外論理経路設計部22)において既存波長パスにグルーミングする場合は、論理経路のホップ数差に電気スイッチの処理遅延量を乗じたものの合計が、最大許容遅延量以下とする制約内での設計となる。
【0096】
また、ステップ3(波長パス設計部30)において、未決定波長パスの経路選択時に前記電気スイッチ部分の処理遅延量に経路長差の絶対値に距離あたりの遅延量を乗じたものの合計が最大許容遅延量以下とする制約を考慮したパス設計となる。
【0097】
第1の実施の形態において、遅延差制約を考慮した実施の形態について説明する。
【0098】
第1の実施の形態のステップ1では図5のステップ104にて、論理経路のホップ数差に電気スイッチの処理遅延量を乗じたものの合計(以下電気処理の遅延差)が、最大許容遅延量以下のものを選択する。遅延差制約外で選択可能なパスが無い場合は、ステップ105で直結リンクに収容できないものとして算出する。
【0099】
ステップ2では図6のステップ205にて、論理経路ホップ数が小さくかつ電気処理の遅延差制約を満たす経路パターンを選択し、制約外のものがあれば既存パスからの再配置が不可能なパスとして保存する。同様に、ステップ205にて電気処理の遅延差制約があれば再配置が不可能なパスとして保存する。以上ステップ1、ステップ2において算出した再配置時の遅延差を設計情報記憶部23に保存しておく。
【0100】
次に、ステップ3の図7のステップ302及びステップ303にて再配置前後の経路差に距離あたりの遅延量を乗じた距離遅延差に、設計情報記憶部23に保存した電気処理の遅延差を足し合わせた合計値が最大許容遅延差制約以下とする制約内での経路を選択する。制約内の物理経路がないパスは再配置を行わないものとする。以上から第1の実施の形態において遅延差制約を考慮した再配置が可能となる。
【0101】
第2の実施の形態において遅延差制約を考慮した場合は、ステップ1とステップ2において、遅延差を考慮した第1の実施の形態と同様に論理経路を決定する。ステップ3においては、経路遅延差は電気処理の遅延差よりも影響は小さいとして、第2の実施の形態のステップ3と同様に再配置演算を行う。
【0102】
上記の図4に示すパス再配置装置の構成要素の動作をプログラムとして構築し、パス再配置装置として利用するコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【0103】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【0104】
1 パス再配置装置
10 入力部
20 論理経路設計部
21 収容論理経路設計部
22 収容外論理経路設計部
23 設計情報記憶部
30 波長パス設計部
【技術分野】
【0001】
本発明は、パス再配置方法及び装置に係り、特に、通信網における波長パス並びに波長レイヤパスを再配置するためのパス再配置方法及び装置に関する。
【背景技術】
【0002】
近年、映像系トラフィックやクラウドサービス等によるデータセンタ間のトラフィックによって、バックボーンネットワークにおいて、準動的なトラフィックが増大することが予想される。これによって、インターネットブラウジングや電子メール(e-mail)のような小粒度から、データセンタ間通信、LTE-A (Long Term Evolution-Advanced)のような大粒度のマルチ粒度のトラフィックが存在することになる。また、波長レイヤにおいては、波長連続制約(通過ノードで波長変換を行わない場合に同一の波長を割り当てるための制約)によって、波長パスの設定・削除を繰り返すことによって波長を効率よく使用することができなくなり、設備増設が早まることが懸念される。
【0003】
ネットワークリソースを有効に使うためには、波長パス及び波長パスに収容するマルチ粒度の上位レイヤパスを再配置することが重要なスキームとなる。
【0004】
考えられる最適な再配置設計方法としては、例えば非特許文献1で記載された整数線形計画法の目的関数を、「ネットワーク全体で使用するトランスポンダ数(もしくは装置数、もしくは装置コスト)の最小化」という数式にすることでマルチレイヤ・マルチ粒度上位レイヤパスの装置コスト最小の設計を得ることはできる。例えば、図12に整数線形計画法(ILP-Integer Linear Programming)を用いた従来の再配置フローを示す。物理トポロジ、対地間毎のパス需要と粒度情報、波長多重数や最大転送帯域等の情報をもつネットワークパラメータを入力として、後述するILPを用いた設計方法の数式を計算することで波長パス及び上位レイヤパスの収容設計状況を得る。ここで収容設計状況とは、上位レイヤパスの論理リンク経路、収容先の波長パス、波長パスの経路・波長を指す。前記計算結果に基づいて既存のパスから移設を行う。
【0005】
非特許文献1で示されている静的なトラフィックにおけるマルチレイヤ・マルチ粒度設計に関する数式を再配置設計に応用した例を以下に示す。
【0006】
目的関数を
【0007】
【数1】
とする。
制約は下記に示す。
【0008】
【数2】
がある。
【0009】
以下に数式の説明を示す。
【0010】
・目的関数、式(1): 通信網内のトランスポンダ数の最小化
以下制約の説明。
【0011】
・式(2)、(3):それぞれノード(i, j)間の波長パス数がノードiにおけるトランスミッタ数、ノードjにおけるレシーバ数以下とする制約;
・式(4):ノード(i, j)間の波長パス数の合計が、同一ノード間の全波長を足し合わせたものと同等とする制約;
・式(6)〜(10):波長パスのフロー保存方程式を表す(フロー保存方程式は非特許文献2を参照)。
【0012】
・式(11)、(12):リンク(m, n)における波長wが論理トポロジ(上位レイヤパスの接続関係を表したトポロジ)に1つの波長パスが存在することを表す;
・式(13)〜(17):上位レイヤパスのフロー保存式;
・式(18):グルーミングした上位レイヤパスの合計帯域が波長パスの帯域以下とする制約を表す。
【0013】
これらにより波長パスの経路・波長、及び上位レイヤパスの論理経路が決定される。
【0014】
上記の計算式おける記号、定数、変数は以下の通りである。
【0015】
●記号
・m,n:波長パスの始点及び終点
・s,d:上位レイヤパスの始点及び終点
・y:上位レイヤパスの粒度
・t:上位レイヤパスID
●定数
・N:ネットワークのノード数
・W:波長多重数
・P(mn):m,nにおけるファイバ設定状況(=1:設定、=0:未設定)
・P(mnw):m,nにおける波長wのファイバ使用状況 P(mnw)=P(mn)
・C:波長1本当りの帯域
・Λ={Λy}:トラフィックマトリックス
●変数
・V(ij):対地間i,jにおける波長パス数
・V(ijw):対地間i,j、波長wの使用状況(≧1:使用、=0:未使用)
・λ(sdtijy):(i,j)間の波長パスに収容されている(s,d)間の粒度y、ID tの上位レイヤパス数
・TR(i):ノードiにおけるtransmitter数
・RR(i):ノードiにおけるresiver数
上記の式を解くことによって、コスト最小のマルチレイヤ・マルチ粒度の設計が可能である。
【先行技術文献】
【非特許文献】
【0016】
【非特許文献1】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.
【非特許文献2】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.
【発明の概要】
【発明が解決しようとする課題】
【0017】
しかしながら、上記非特許文献1の方式を用いた場合は、ネットワーク(NW)規模の増大に伴って計算時間が指数関数的に増大することが懸念される。このため、再配置前の既設の波長パスの設定状態及び波長パスへの上位レイヤパスの収容状態を考慮せずに、パスが全く設定していない初期状態から設計し、既設パスも再配置演算の対象とする。更に、初期状態からの設計であるので再配置順序も当然記載されていない。
【0018】
また、非特許文献1で示されている静的なトラフィックにおけるマルチレイヤ・マルチ粒度設計に関する数式を再配置設計に適用した場合、物理経路と論理経路に関してそれぞれ制約式が必要となり計算量が膨大となる。さらに、既存の波長パス及び上位レイヤパスの収容設計状況を考慮していないため無駄な再配置を行わなければならないという問題もある。
本発明は、上記の点に鑑みなされたものであり、波長パス及びマルチ粒度の上位レイヤパスの再配置設計方法、並びに既設パスの再配置頻度を低減して再配置するための再配置順序を示すとともに計算時間を少なくするためパス再配置方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【0019】
上記の課題を解決するため、本発明(請求項1)は、マルチレイヤノードを有する通信網において、波長パス及び上位レイヤパスを再配置するパス再配置方法であって、
論理経路設計手段が、上位レイヤパスの論理経路を設計し、設計情報記憶手段に格納する論理経路設計ステップと、
波長パス設計手段が、前記設計情報記憶手段に格納された前記論理経路に基づいて波長パスを設計する波長パス設計ステップと、を有する。
【0020】
また、本発明(請求項2)は、前記論理経路設計ステップにおいて、
対地間ごとに波長パスの最大容量もしくはあらかじめ設定した容量まで1つ以上の複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計する第1ステップと、
波長パスの最大容量もしくは予め設定した容量に収容することができなかった残りの上位レイヤパス需要に関して論理経路を設計する第2ステップを、含む。
【0021】
また、本発明(請求項3)は、前記論理経路設計ステップにおいて、
既存の波長パスと対応する論理リンクがあった場合は、再配置を行わない。
【0022】
また、本発明(請求項4)は、前記波長パス設計ステップにおいて、
前記論理経路設計ステップで再配置を行わない波長パスで使用されている波長と同じ波長を優先的に使用する。
【0023】
また、本発明(請求項5)は、前記波長パス設計ステップにおいて、
論理リンクに基づいて波長パスの経路・波長を、整数線形計画法を用いて設計する。
【発明の効果】
【0024】
本発明では、波長パスと波長パスに収容する上位レイヤパスをそれぞれ個別に収容設計することで、計算量を低減し、更に、上位レイヤパスを収容する余地のある既設の波長パスに上位レイヤパスを収容した後に、新規の波長パスを設定することとしたため、波長パスの設計の計算量を低減することが可能となる。
【図面の簡単な説明】
【0025】
【図1】本発明の効果を示す図である。
【図2】本発明におけるマルチレイヤノード装置例である。
【図3】本発明における概要動作のフローチャートである。
【図4】本発明の第1の実施の形態におけるパス再配置装置の構成図である。
【図5】本発明の第1の実施の形態におけるステップ1の詳細フローチャートである。
【図6】本発明の第1の実施の形態におけるステップ2の詳細フローチャートである。
【図7】本発明の第1の実施の形態におけるステップ3の詳細フローチャートである。
【図8】本発明の第1の実施の形態におけるネットワーク条件(例)である。
【図9】本発明の第1の実施の形態におけるステップ1の概要説明図(例)である。
【図10】本発明の第1の実施の形態におけるステップ2の概要説明図(例)である。
【図11】本発明の第1の実施の形態におけるステップ3の概要説明図(例)である。
【図12】従来の再配置のフローチャートである。
【発明を実施するための形態】
【0026】
以下図面と共に、本発明の実施の形態を説明する。
【0027】
図1に本発明の効果について概要を説明する。図2に示したような波長スイッチ機能部と上位レイヤパスの電気スイッチ機能部で構成されたマルチレイヤノード装置が、各ノードに配備されていた場合に、再配置前は(図1(A))のaのように複数の上位レイヤパスが上位レイヤパスイッチ機能部で複数の拠点からのトラフィックをグルーミング(波長パスに複数の上位レイヤパスを収容)して所望のノードへ伝送される。一方波長レイヤにおいては、パスの設定・削除を繰り返すことにより、図1の再配置前(A)に示すように、物理リンク毎に異なる波長チャネルを使用することで通信網全体として使用する波長チャネル数が増大する。まず、波長パスに収容する上位レイヤパスを再グルーミングすることで電気スイッチを経由しないでカットスルーをする効果によりトランスポンダを削減できる(図1(B,a))。また波長レイヤに関しては、通信網全体での使用波長チャネル数を低減することが可能となり(図1(B,b))、将来の設備コスト増設を抑えることができる。
【0028】
本発明では、計算時間が整数線形計画法を用いた場合に比べて大幅に削減することができ、かつ既存の波長パスと上位レイヤパスからの変更を考慮した再配置方法であることが特徴である。
【0029】
次に、本発明の概要について説明する。本発明の処理は図3に示すように、3つのステップからなる:
ステップ1)対地間ごとに波長パス1本あたりの最大伝送容量もしくは予め設定した容量まで、複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計する。
【0030】
ステップ2)ステップ1において収容できなかった残りの上位レイヤパスを、各物理リンクの未使用の波長に収容するように整数線形計画法もしくは発見的アルゴリズムで論理リンクを設計する。
【0031】
ステップ3)ステップ1とステップ2で設計した論理リンクに基づいて波長パスの経路・波長を設計する。
【0032】
次に、本発明の実施形態で用いる用語について説明する。
【0033】
「使用波長チャネル数」とは、通信網内の少なくともいずれかの物理リンクで使用されている波長領域の空き波長を含めた波長数、すなわち、使用中の最小の波長番号から使用中の最大の波長番号までの波長数(通信網内で使用されていない波長番号を除く)のことである。
【0034】
「上位レイヤパススイッチ機能部」とは、ODU-XC(Optical-channel Data Unit (ODU) を転送するためのスイッチ)、SDH-XC(Synchronous Digital Hierarchy(SDH)を転送するためのスイッチ))、MPLS-TPルータ(Multiprotocol Label Switching-Transport Profile(MPLS-TP)を転送するためのルータ)等の電気スイッチ機能部のことである。
【0035】
「上位レイヤパス」とは、ODU、SDH、MPLS-TP等である。
【0036】
「波長レイヤパス」とは物理レイヤのパスであり、光パスともいい、光の通信路のことである。
【0037】
「グルーミング」とは、複数の上位レイヤパスを単一の波長パスに束ねることである。
【0038】
「カットスルー」とは、電気のノードを経由しないで光のまま転送することである。「マルチレイヤノード」とは、波長スイッチと上位レイヤの電気スイッチを含んだ複数のレイヤスイッチを持つノード装置のことである。
【0039】
「直結論理リンク」とは、始点と終点ノード間において途中で電気処理を行うノードを通過しないで光信号のまま伝送する場合のリンクのことである。
【0040】
「直結でない論理リンク」とは、途中で電気処理を行うノードを通過するため、複数の論理リンクを通過する場合のリンクのことである。
【0041】
「収容率」とは、(収容している全上位レイヤパスの粒度の合計)/(最大容量×波長数)のことである。
【0042】
「波長チャネル」とは波長番号のことである。
【0043】
「波長パスの経路・波長を設計」とは、光信号を伝送するための経路探索と波長を選択することである。
【0044】
「ダイクストラアルゴリズム」とは最短ホップもしくは最短経路長を探索するためのアルゴリズムのことである。
【0045】
「First Fit (FF) アルゴリズム」とは、波長番号の若番から波長割り当てを行うアルゴリズムのことである。
【0046】
「論理経路」とは、上位レイヤパスが終端されるまでに、通過する電気処理ノード間の論理的(仮想的)な経路のことを指す。例えば始点と終点がそれぞれノード番号0、5であり、論理経路が0−3−2−5であった場合は、ノード番号3、ノード番号2それぞれで電気処理ノードを通過していることを表す。また論理リンクそれぞれに波長パスが対応し、この例の場合は対地間ペアがそれぞれ0−3、3−2、2−5に対応する波長パスが存在する。
【0047】
[第1の実施の形態]
図4は、本発明の第1の実施の形態におけるパス再配置装置の構成を示す。
【0048】
同図に示す、パス再配置装置1は、入力部10、論理経路設計部20、波長パス設計部30から構成される。論理経路設計部20は、収容論理経路設計部21、収容外論理経路設計部22、設計情報記憶部23から構成される。
【0049】
入力部10は、外部から物理トポロジの接続行列、既存の波長パスの経路、波長、及び上位レイヤパスの論理リンク経路、粒度、収容先波長パスを取得して、論理経路設計部20に渡す。
【0050】
論理経路設計部20の収容論理経路設計部21は、対地間ごとに波長パスの最大容量もしくは予め設定した容量まで1つ以上の複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計し、その設計情報を設計情報記憶部23に格納する。
【0051】
論理経路設計部20の収容外論理経路設計部22は、波長パスの最大容量もしくは予め設定した容量に収容することができなかった残りの上位レイヤパス需要に関して論理経路を設計し、その設計情報を設計情報記憶部23に格納する。
【0052】
波長パス設計部30は、設計情報記憶部23に格納された論理経路に基づいて、再配置後波長パスの経路、波長、再配置後上位レイヤパスの論理リンク経路、粒度、収容先波長パス、波長/上位レイヤパス設定順序を設計する。
【0053】
本発明における第1の実施の形態を、図3、5〜7を用いて説明する。パス再配置装置1は、図3に示すとおり、以下のアルゴリズムフローで実施する。
●入力情報:
・物理トポロジの接続行列
・既存の波長パスの経路、波長
・上位レイヤパスの論理リンク経路、粒度、収容先波長パス
●出力情報:
・再配置後波長パスの経路、波長
・再配置後上位レイヤパスの論理リンク経路、粒度、収容先波長パス
・波長/上位レイヤパス設定順序
●動作概要:
次に、本発明のパス再配置装置1の動作概要について説明する。本発明は図3に示すように、3つのステップからなる:
ステップ1) 上記の入力情報が入力されると、論理経路設計部20の収容論理経路設計部21は、上記の入力情報に基づいて、対地間ごとに波長パス1本あたりの最大伝送容量もしくは予め設定した容量まで、複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計し、その設計情報を設計情報記憶部23に格納する。
【0054】
ステップ2) 論理経路設計部20の収容外論理経路設計部22は、ステップ1において収容できなかった残りの上位レイヤパスを、各物理リンクの未使用の波長に収容するように整数線形計画法もしくは発見的アルゴリズムで論理リンクを設計し、その設計情報を設計情報記憶部23に格納する。
【0055】
ステップ3) ステップ1とステップ2で設計した論理リンクに基づいて波長パスの経路・波長を設計する。
【0056】
本願と従来例との違いは、ステップ1とステップ3を備えるところにある。ステップ1とステップ3を備えるために、ステップ3で計算に用いる制約式を削減することが出来る。
【0057】
図3のステップ1の詳細な動作のフローチャートを図5に示す。図5に示すように、ステップ1は以下の5つのステップからなる。
【0058】
ステップ101) 収容論理経路設計部21は、直結の論理リンクである既存上位レイヤパスを選択。
【0059】
ステップ102) 上位レイヤパスの粒度の合計値が大きい順番にソートする。
【0060】
ステップ103) 収容論理経路設計部21は、老番から若番へ順番に移設計算をし、波長の最大粒度もしくは予め設定された帯域までグルーミング可能なパスを算出し、直結論理リンクとなる上位レイヤパスIDと収容先の波長パスの経路・波長を設計情報記憶部23に保存する。
【0061】
ステップ104) 収容論理経路設計部21は、ステップ103でグルーミング不可能だった上位レイヤパスと、直結論理リンク以外の上位レイヤパスを直結論理リンクとして、同様にステップ102とステップ103の計算を行う。ただし、ステップ103で既存の波長パス以外に収容する場合は、波長パスの経路・波長は未決定波長パスとして識別子(ID)及び収容した上位レイヤパスの合計帯域から残帯域を保存。IDの振り方は例えば数字の若い順番に振るといった方法でよい。
【0062】
ステップ105) 収容論理経路設計部21は、直結リンクに収容できなかった上位レイヤパスの対地と需要数を算出し、設計情報記憶部23に格納する。直結論理リンクの設計処理を終了し、ステップ201に移行する。
【0063】
次に、収容外経路設計部22における、図3のステップ2の詳細な動作のフローチャートを図6に示す。図6に示すように、ステップ2は9つのステップからなる。
【0064】
ステップ201) 収容外経路設計部22は、設計情報記憶部23に格納された設計情報を読み出して、前述のステップ105で算出した上位レイヤパス需要に対して、物理リンクの最短ホップ数及び候補経路を算出する。
【0065】
ステップ202) 物理経路のホップ数が小さくかつ物理経路パターンが小さい順番から論理経路を設計する。
【0066】
ステップ203) 条件分岐:グルーミング可能(波長パスの空き帯域≧対象の上位レイヤパスの粒度)な既存波長パスもしくは現ステップまでに設計した論理リンクが、対象の上位レイヤパスの論理経路候補に一つ以上存在するか、それとも一つも存在しないか?一つ以上存在する場合はステップ204へ、一つも存在しない場合はステップ205へ移行する。
【0067】
ステップ204) 論理経路ホップ数が小さい経路パターンを選択し、ステップ206に移行する。
【0068】
ステップ205) 直結論理リンクを決定し(ホップ数が小さいリンクを優先)、ステップ208に移行する。
【0069】
ステップ206) 条件分岐:同一ホップ数の複数の論理経路候補が存在する場合は、ステップ207に移行し、存在しない場合はステップ208に移行する。
【0070】
ステップ207) グルーミング可能な候補論理リンク全てに対して平均収容率を算出し、平均収容率が大きい経路を選択する。
【0071】
ステップ208) 論理リンクに対応する既存波長パスが存在すればその経路・波長を設計情報記憶部23に保存し、存在しない場合は、経路・波長が未決定波長パスとしてIDを振り、収容設計した上位レイヤパスの粒度から波長パスの残帯域を設計情報記憶部23に保存する。
【0072】
ステップ209) 条件分岐:全ての上位レイヤパス需要に関して論理経路の設計が完了した場合は当該処理を終了し、ステップ301に移行する。
【0073】
次に、波長パス設計部30における、図3のステップ3の詳細な動作のフローチャートを図7に示す。
【0074】
図7に示すように、図3のステップ3は3つのステップからなり、未割当波長パスを割り当てる。
【0075】
ステップ301) 波長パス設計部30は、ステップ1、ステップ2で経路・波長が決定している波長パスを設計情報記憶部23から読み出して、波長チャネル内の使用波長数が多い順番にソートする。
【0076】
ステップ302) ソートした波長チャネルの若番の波長を用いて順番に、経路・波長が未決定の波長パスIDの収容可能な経路を探索する。このとき経路数が小さいものから順番に設計する。
【0077】
ステップ303)使用可能な波長が無い場合は例えばFirst-Fitアルゴリズム(波長チャネルの若番から割り当て‐文献1「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]経路は例えばダイクストラアルゴリズムを用いて最短経路で設計する。
【0078】
以上のステップから波長パス及び上位レイヤパスの再配置設計が可能となる。
【0079】
無瞬断で再配置を行う順序については以下の2つの場合分けによって決定される。
【0080】
(1)上位レイヤパスを、既存の波長パスに再グルーミングするときは、対象となる上位レイヤパスを波長パスに設定し冗長路を決定した後に、対象となっている既存の上位レイヤパスを削除することで移設が可能となる。
【0081】
(2)上位レイヤパスを、変更した波長パスに再グルーミングするときは、先に波長パスを変更先の波長パスに設定する。次に、上位レイヤパスを変更先波長パスに設定し冗長路を決定し、その後対象となっている既存の上位レイヤパスを削除することで移設が可能となる。最後に既存の波長パスに収容されている上位レイヤパスを全て移設後に波長パスを削除する。
【0082】
上記の(1)、(2)において上位レイヤパスがSDHパスやODUパスのようなタイムスロット単位でパスを構成しているものであった場合は、遅延調整が必要となる。
【0083】
上記の動作の具体例を図8のネットワーク条件で適用したときについて説明する。
【0084】
ステップ1において、収容論理経路設計部21は、始点と終点が同一対地で波長パス1本あたりの最大容量40Gまで詰めることができるパスに関しては始点と終点で直結の論理リンクを設計する。図9の例では、ノード0⇔5間の波長パス2本、40Gの上位レイヤパス2本と10Gの上位レイヤパス4本、ノード1⇔2間の波長パス1本、2.5Gの上位レイヤパス4本と10Gの上位レイヤパス4本、ノード3⇔5間の波長パス1本、10Gの上位レイヤパス4本の論理リンクが設計される。例えば、図9のノード1−ノード2のパス需要においては、直結リンクである既存の上位レイヤパスがあるため、収容粒度の大きい順番にソートし、老番から順番に最大粒度までグルーミング設計を行う。この例の場合、既存波長パスのλ7に粒度2.5のパス4本(ID:9、10、11、12)を移設する。次に、収容できなかった上位レイヤパス需要を算出し、ステップ2に進む。
【0085】
ステップ2では、収容外論例経路設計部22において、図10に示すように[2-1]においては図9の[1](直結論理リンクの決定)で算出した対地間パスそれぞれにおいて物理リンクにおける最短ホップ数と経路候補数を算出する。[2-1]から、物理リンクのホップ数が小さくかつ物理経路パターンが小さい順番に直結論理リンクを決定する。この例の場合、
<1> 2.5G上位レイヤパス2本は「1―2」、
<2>10G上位レイヤパス1本は「4―5」となる。
【0086】
<3>ノード3⇔5に関しては論理リンク「3−4」を設定することで「3−4−5」の経路を用いてパスを収容することができる。
【0087】
<4>ノード1⇔5に関しては候補経路が「1−2−5」と「1−4−5」の2パターンあるが、既存波長パスは1-4及び4-5で存在しているため1−4−5を選択する。
【0088】
<5>同様にノード「0−5」は「0−3−4−5」の経路を用いてパスを収容することができる。以上の作業を全パスに関して繰り返すことで論理リンク(波長パス)を決定することができる。
【0089】
ステップ3では、波長パス設計部30において、ステップ1、2で決定した論理リンクに基づいて波長パスを設定する。図11に示すようにステップ1、ステップ2において再配置を行わない波長が決定されており、波長チャネル毎の波長数を算出し波長数が大きい順番にソートする。その後若番から物理リンクのホップ数が小さいパスから順番に波長を割り当てていく。
【0090】
従来例を再配置設計に応用した場合ではこれらを全てILPで解くことにより膨大な時間がかかる。
【0091】
従来例だと本発明の実施の形態におけるステップ1〜3全てをILPで計算することになり、ネットワーク規模の増大に従って指数関数的に増大する。それに対して本発明は、全ステップで発見的アルゴリズムを用いることで計算量を抑えることができる。(ILPは考えられる値をしらみつぶしに調べるため(ILPの計算アルゴリズムにもよるが)計算量が膨大となる。ILPを使用しないで「発見的アルゴリズム」を用いるだけで計算量が削減できることは自明となる。)
[第2の実施の形態]
本発明における第2の実施の形態について説明をする。本発明は第1の実施の形態においてステップ1で決定した論理リンクに基づいて、ステップ3で整数線形計画法を用いて波長及び経路を決定する方法である。
【0092】
前述の従来例を応用した数式においてはVijを決定することができていないため計算式を省くことができない。本実施の形態においては、ステップ1で論理リンクの設計を終了しているため、変数Vij及びλijysdtは定数として決定している。また再配置を行わない波長パスの経路・波長も決定しているため、一部のPmnijwも定数として決定している。前述のILPの数式において式(13)〜(18)の計算式は解が得られており、また式(6)〜(11)における計算式も一部解が得られている。これにより計算するのに必要な数式を半分未満に減らすことができ、計算量を削減することが可能となる。
【0093】
[第3の実施の形態]
本発明における第3の実施の形態について説明をする。本発明は第1及び第2の実施の形態において上位レイヤパスを再グルーミングするときの遅延差制約について考慮した形態である。
【0094】
入力に、既存上位レイヤパスの物理経路及び論理リンク経路、各リンクの経路長、最大許容遅延量、距離あたりの遅延量、電気スイッチの処理遅延量(例えば上位レイヤパスのAdd/Dropによる処理遅延のことを指す。)、を加え再グルーミングする際に遅延差制約内での再グルーミングを行うことを特徴とする。
【0095】
ステップ1(収容論理経路設計部21)とステップ2(収容外論理経路設計部22)において既存波長パスにグルーミングする場合は、論理経路のホップ数差に電気スイッチの処理遅延量を乗じたものの合計が、最大許容遅延量以下とする制約内での設計となる。
【0096】
また、ステップ3(波長パス設計部30)において、未決定波長パスの経路選択時に前記電気スイッチ部分の処理遅延量に経路長差の絶対値に距離あたりの遅延量を乗じたものの合計が最大許容遅延量以下とする制約を考慮したパス設計となる。
【0097】
第1の実施の形態において、遅延差制約を考慮した実施の形態について説明する。
【0098】
第1の実施の形態のステップ1では図5のステップ104にて、論理経路のホップ数差に電気スイッチの処理遅延量を乗じたものの合計(以下電気処理の遅延差)が、最大許容遅延量以下のものを選択する。遅延差制約外で選択可能なパスが無い場合は、ステップ105で直結リンクに収容できないものとして算出する。
【0099】
ステップ2では図6のステップ205にて、論理経路ホップ数が小さくかつ電気処理の遅延差制約を満たす経路パターンを選択し、制約外のものがあれば既存パスからの再配置が不可能なパスとして保存する。同様に、ステップ205にて電気処理の遅延差制約があれば再配置が不可能なパスとして保存する。以上ステップ1、ステップ2において算出した再配置時の遅延差を設計情報記憶部23に保存しておく。
【0100】
次に、ステップ3の図7のステップ302及びステップ303にて再配置前後の経路差に距離あたりの遅延量を乗じた距離遅延差に、設計情報記憶部23に保存した電気処理の遅延差を足し合わせた合計値が最大許容遅延差制約以下とする制約内での経路を選択する。制約内の物理経路がないパスは再配置を行わないものとする。以上から第1の実施の形態において遅延差制約を考慮した再配置が可能となる。
【0101】
第2の実施の形態において遅延差制約を考慮した場合は、ステップ1とステップ2において、遅延差を考慮した第1の実施の形態と同様に論理経路を決定する。ステップ3においては、経路遅延差は電気処理の遅延差よりも影響は小さいとして、第2の実施の形態のステップ3と同様に再配置演算を行う。
【0102】
上記の図4に示すパス再配置装置の構成要素の動作をプログラムとして構築し、パス再配置装置として利用するコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【0103】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【0104】
1 パス再配置装置
10 入力部
20 論理経路設計部
21 収容論理経路設計部
22 収容外論理経路設計部
23 設計情報記憶部
30 波長パス設計部
【特許請求の範囲】
【請求項1】
マルチレイヤノードを有する通信網において、波長パス及び上位レイヤパスを再配置するパス再配置方法であって、
論理経路設計手段が、上位レイヤパスの論理経路を設計し、設計情報記憶手段に格納する論理経路設計ステップと、
波長パス設計手段が、前記設計情報記憶手段に格納された前記論理経路に基づいて波長パスを設計する波長パス設計ステップと、
を有することを特徴としたパス再配置方法。
【請求項2】
前記論理経路設計ステップにおいて、
対地間ごとに波長パスの最大容量もしくはあらかじめ設定した容量まで1つ以上の複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計する第1ステップと、
波長パスの最大容量もしくは予め設定した容量に収容することができなかった残りの上位レイヤパス需要に関して論理経路を設計する第2ステップを、
含む請求項1記載のパス再配置方法。
【請求項3】
前記論理経路設計ステップにおいて、
既存の波長パスと対応する論理リンクがあった場合は、再配置を行わない
請求項1記載のパス再配置方法。
【請求項4】
前記波長パス設計ステップにおいて、
前記論理経路設計ステップで再配置を行わない波長パスで使用されている波長と同じ波長を優先的に用いる
請求項3記載のパス再配置方法。
【請求項5】
前記波長パス設計ステップにおいて、
論理リンクに基づいて波長パスの経路・波長を、整数線形計画法を用いて設計する
請求項1記載のパス再配置方法。
【請求項6】
マルチレイヤノードを有する通信網において、波長パス及び上位レイヤパスを再配置するパス再配置装置であって、
上位レイヤパスの論理経路を設計し、設計情報記憶手段に格納する論理経路設計手段と、
前記設計情報記憶手段に格納された前記論理経路に基づいて波長パスを設計する波長パス設計手段と、を有し、
前記論理経路設計手段は、
対地間ごとに波長パスの最大容量もしくはあらかじめ設定した容量まで1つ以上の複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計する第1の設計手段と、
波長パスの最大容量もしくはあらかじめ設定した容量に収容することができなかった残りの上位レイヤパス需要に関して論理経路を設計する第2の設計手段と、
を含むことを特徴としたパス再配置装置。
【請求項7】
前記論理経路設計手段は、
既存の波長パスと対応する論理リンクがあった場合は、再配置を行わない手段を含み、
前記波長パス設計手段は、
前記論理経路設計手段で再配置を行わない波長パスで使用されている波長と同じ波長を優先的に用いて波長の割当を行う手段を含む
請求項6記載のパス再配置装置。
【請求項8】
前記波長パス設計手段は、
論理リンクに基づいて波長パスの経路・波長を、整数線形計画法を用いて設計する手段を含む請求項6記載のパス再配置装置。
【請求項1】
マルチレイヤノードを有する通信網において、波長パス及び上位レイヤパスを再配置するパス再配置方法であって、
論理経路設計手段が、上位レイヤパスの論理経路を設計し、設計情報記憶手段に格納する論理経路設計ステップと、
波長パス設計手段が、前記設計情報記憶手段に格納された前記論理経路に基づいて波長パスを設計する波長パス設計ステップと、
を有することを特徴としたパス再配置方法。
【請求項2】
前記論理経路設計ステップにおいて、
対地間ごとに波長パスの最大容量もしくはあらかじめ設定した容量まで1つ以上の複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計する第1ステップと、
波長パスの最大容量もしくは予め設定した容量に収容することができなかった残りの上位レイヤパス需要に関して論理経路を設計する第2ステップを、
含む請求項1記載のパス再配置方法。
【請求項3】
前記論理経路設計ステップにおいて、
既存の波長パスと対応する論理リンクがあった場合は、再配置を行わない
請求項1記載のパス再配置方法。
【請求項4】
前記波長パス設計ステップにおいて、
前記論理経路設計ステップで再配置を行わない波長パスで使用されている波長と同じ波長を優先的に用いる
請求項3記載のパス再配置方法。
【請求項5】
前記波長パス設計ステップにおいて、
論理リンクに基づいて波長パスの経路・波長を、整数線形計画法を用いて設計する
請求項1記載のパス再配置方法。
【請求項6】
マルチレイヤノードを有する通信網において、波長パス及び上位レイヤパスを再配置するパス再配置装置であって、
上位レイヤパスの論理経路を設計し、設計情報記憶手段に格納する論理経路設計手段と、
前記設計情報記憶手段に格納された前記論理経路に基づいて波長パスを設計する波長パス設計手段と、を有し、
前記論理経路設計手段は、
対地間ごとに波長パスの最大容量もしくはあらかじめ設定した容量まで1つ以上の複数の上位レイヤパスを収容して、始点と終点ノードを直結の論理リンクを設計する第1の設計手段と、
波長パスの最大容量もしくはあらかじめ設定した容量に収容することができなかった残りの上位レイヤパス需要に関して論理経路を設計する第2の設計手段と、
を含むことを特徴としたパス再配置装置。
【請求項7】
前記論理経路設計手段は、
既存の波長パスと対応する論理リンクがあった場合は、再配置を行わない手段を含み、
前記波長パス設計手段は、
前記論理経路設計手段で再配置を行わない波長パスで使用されている波長と同じ波長を優先的に用いて波長の割当を行う手段を含む
請求項6記載のパス再配置装置。
【請求項8】
前記波長パス設計手段は、
論理リンクに基づいて波長パスの経路・波長を、整数線形計画法を用いて設計する手段を含む請求項6記載のパス再配置装置。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【公開番号】特開2013−62628(P2013−62628A)
【公開日】平成25年4月4日(2013.4.4)
【国際特許分類】
【出願番号】特願2011−198882(P2011−198882)
【出願日】平成23年9月12日(2011.9.12)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
【公開日】平成25年4月4日(2013.4.4)
【国際特許分類】
【出願日】平成23年9月12日(2011.9.12)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
[ Back to top ]