(57)【要約】【課題】時間帯によってトラヒックの分布が異なる状況で、トラヒックをリング網に経済的に疎通することを目的とする。【解決手段】本発明の一形態に係る波長切り替え最適化装置は、時間帯によってリング網のノード間を流れるトラヒックの分布が変動する場合に、ノードに配置された多重化・多重分離装置（ADM）の接続先波長の切り替えを最適化するための波長切り替え最適化装置であって、ADMの配置情報を取得するデータ取得部と、時間帯が変わったときにどちらの時間帯でも使えるようなADMを増やすように、ADMの接続先波長の切り替えを最適化する波長切り替え最適化部とを有する。【選択図】図２
2016136663.tif 000002
【特許請求の範囲】
【請求項１】
時間帯によってリング網のノード間を流れるトラヒックの分布が変動する場合に、ノードに配置された多重化・多重分離装置（ADM）の接続先波長の切り替えを最適化するための波長切り替え最適化装置であって、
ADMの配置情報を取得するデータ取得部と、
時間帯が変わったときにどちらの時間帯でも使えるようなADMを増やすように、ADMの接続先波長の切り替えを最適化する波長切り替え最適化部と、
を有する波長切り替え最適化装置。
【請求項２】
前記波長切り替え最適化部は、時間帯が第１の時間帯から第２の時間帯に変わったときに双方の時間帯に必要なADMの個数を減らすようなADMの接続先波長の切り替え解を０−１整数計画法によって求める、請求項１に記載の波長切り替え最適化装置。
【請求項３】
前記波長切り替え最適化部は、
対象とするリング網をnノードからなるリング網とし、第１の時間帯及び第２の時間帯における波長数はそれぞれm個あり、それぞれλ1i,λ2i（1≦i≦m）とし、波長λ1i,λ2iがそれぞれjノードのADMと接続するときa1(i,j)=1,a2(i,j)=1、接続しないときa1(i,j)=0,a2(i,j)=0（1≦i≦m,1≦j≦n）と置き、
時間帯が第１の時間帯から第２の時間帯に変わったときにADMの接続先波長をλ1iからλ2kに切り替えることを０−１変数x(i,p)（1≦i,p≦m）によって、接続先波長を切り替えるときx(i,k)=1、切り替えないときx(i,p)=0（p≠k）と表す場合、
変数x(i,k)（1≦i,k≦m）についての制約条件
【数８】
2016136663.tif 000010
【数９】
2016136663.tif 000011
【数１０】
2016136663.tif 000012
を満たしつつ、
双方の時間帯に必要なADMの個数
【数１１】
2016136663.tif 000013
を最小化させるADMの接続先波長の切り替え解x(i,k)を求める、請求項２に記載の波長切り替え最適化装置。
【請求項４】
前記波長切り替え最適化部は、時間帯が第１の時間帯から第２の時間帯に変わったときに双方の時間帯に必要なADMの個数に関する制約式を、必ずしも充足しなくてもよい制約式とした重みづけ制約充足問題の形にして、ADMの接続先波長の切り替え解を求める、請求項２に記載の波長切り替え最適化装置。
【請求項５】
前記波長切り替え最適化部は、
リング網のノード数がnであり、第１の時間帯及び第２の時間帯における波長数はそれぞれm個あり、それぞれλ1i,λ2i（1≦i≦m）とし、波長λ1i,λ2iがそれぞれjノードのADMと接続するときa1(i,j)=1,a2(i,j)=1、接続しないときa1(i,j)=0,a2(i,j)=0（1≦i≦m,1≦j≦n）と置き、
時間帯が第１の時間帯から第２の時間帯に変わったときにADMの接続先波長をλ1iからλ2kに切り替えることを０−１変数x(i,p)（1≦i,p≦m）によって、接続先波長を切り替えるときx(i,k)=1、切り替えないときx(i,p)=0（p≠k）と表す場合、
変数x(i,k)（1≦i,k≦m）についての制約条件
【数１２】
2016136663.tif 000014
【数１３】
2016136663.tif 000015
【数１４】
2016136663.tif 000016
を絶対に充足しつつ、
双方の時間帯に必要なADMの個数に関する制約式
【数１５】
2016136663.tif 000017
を必ずしも充足しなくてもよいが左辺の正値をできるだけ小さくするADMの接続先波長の切り替え解x(i,k)を求める、請求項４に記載の波長切り替え最適化装置。
【請求項６】
時間帯によってリング網のノード間を流れるトラヒックの分布が変動する場合に、ノードに配置された多重化・多重分離装置（ADM）の接続先波長の切り替えを最適化するための波長切り替え最適化装置における波長切り替え設計方法であって、
ADMの配置情報を取得するステップと、
時間帯が変わったときにどちらの時間帯でも使えるようなADMを増やすように、ADMの接続先波長の切り替えを最適化するステップと、
を有する波長切り替え設計方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、波長切り替え最適化装置及び波長切り替え設計方法に関する。
【背景技術】
【０００２】
複数波長を有するリング網に多重化・多重分離装置（ADM：Add Drop Multiplexer）を設置することにより、リング網を流れるトラヒックを収容することができる。
【０００３】
リング網におけるADM設置ノードを与えられたトラヒックのもとで、できる限り減らすトラヒックグルーミングの検討がなされてきた（非特許文献１参照）。従来のトラヒックグルーミングでは、２点間のトラヒックは変動していないため、ネットワークフロー問題として定式化して解決することが可能であった。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Rudra Dutta and George N. Rouskas, "Traffic Grooming in WDM Networks: Past and Future", IEEE Network, 2002
【非特許文献２】Randall Berry and Eytan Modiano, "Reducing Electronic Multiplexing Costs in SONET/WDM Rings with Dynamically Changing Traffic", Selected Areas in Communications, IEEE Journal, Vol. 18, pp1961-1971, 2000.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
時間帯によってトラヒックの分布が異なる状況では、トラヒックは、その分布に応じてリング網の各ノードに設置されたADMを介して流れる。ノード間を流れるトラヒックの量によっては、複数の波長に対してADMが必要となり、したがって、各ノードにおいて必要となるADM数は時間帯によって異なる。
【０００６】
上記のように、従来のトラヒックグルーミングでは、２点間のトラヒックは変動していないという条件があり、時間帯によってトラヒック量が変化する条件を加えると、波長数が増えたときうまく経済化できないという課題があった。
【０００７】
本発明は、時間帯によってトラヒックの分布が異なる状況で、時間帯が変わったときトラヒックの利用する波長を最適に切り替えて、トラヒックをリング網に経済的に疎通することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一形態に係る波長切り替え最適化装置は、
時間帯によってリング網のノード間を流れるトラヒックの分布が変動する場合に、ノードに配置された多重化・多重分離装置（ADM）の接続先波長の切り替えを最適化するための波長切り替え最適化装置であって、
ADMの配置情報を取得するデータ取得部と、
時間帯が変わったときにどちらの時間帯でも使えるようなADMを増やすように、ADMの接続先波長の切り替えを最適化する波長切り替え最適化部と、
を有することを特徴とする。
【０００９】
また、本発明の一形態に係る波長切り替え設計方法は、
時間帯によってリング網のノード間を流れるトラヒックの分布が変動する場合に、ノードに配置された多重化・多重分離装置（ADM）の接続先波長の切り替えを最適化するための波長切り替え最適化装置における波長切り替え設計方法であって、
ADMの配置情報を取得するステップと、
時間帯が変わったときにどちらの時間帯でも使えるようなADMを増やすように、ADMの接続先波長の切り替えを最適化するステップと、
を有することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、時間帯によってトラヒックの分布が異なる状況で、トラヒックをリング網に経済的に疎通することが可能になる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施例に係るシステムの全体構成図
【図２】本発明の実施例に係るシステムを構成する装置の機能ブロック図
【図３】本発明の実施例によるADM配置の例
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施例について説明する。
【００１３】
本発明の実施例では、時間帯によってリング網のノード間を流れるトラヒックの分布が変動し、そのトラヒックを、複数波長を有するリング網によって疎通する状況を想定する。トラヒック量は量子化されたものとして扱い、リング網の発着ノードの多重化・多重分離装置（ADM）を介して流れるものとする。１波長に対して最大g単位のトラヒックまで各リンクを疎通できるものとする。この容量制約gをグラニュラリティと呼ぶ。１波長を流れるトラヒックは、このグラニュラリティのために限定される。それらのトラヒックの発着ノードだけにADMを置けばよい。ADMは１台当たり１つの波長にのみ対応可能である。
【００１４】
また、時間帯を２分し、例えば昼夜間に分けることを考える。昼夜によって、トラヒックは変動する。必要なADMの個数は昼と夜で変わる可能性がある。ここで、リング網は時間帯が変わったとき、トラヒックを乗せる波長が変えられるものとする。そのためには、ADMの接続先の波長を切り替える。
【００１５】
本発明の実施例では、時間帯が変わったときにどちらの時間帯でも使えるようなADMを増やすように接続先の波長を切り替えることによって必要なADMの個数を減らしリング網を経済化する。具体的には、ADMの個数をできるだけ減らすような波長の切り替え法を０−１整数計画法によって定式化し、この波長切り替えによってリング網の経済化を図る。
【００１６】
更に、０−１整数計画法によって定式化した０−１整数計画法を、重みづけ制約充足問題の形にして、ヒューリスティックに可能解を求めることもできる。
【００１７】
図１は、本発明の実施例に係るシステムの全体構成図である。本発明の実施例に係るシステムは、オペレーションシステム１０、波長切り替え最適化装置２０及び波長切り替え表示装置３０で構成される。
【００１８】
オペレーションシステム１０は、複数波長を有するリング網上のノード及び通信網を運用管理する装置であり、リング網上の各波長と接続するADMのノード番号を時間帯及び波長毎に収集する。
【００１９】
波長切り替え最適化装置２０は、時間帯によってリング網のノード間を流れるトラヒックの分布が変動する場合に、ADMの接続先波長の切り替えを最適化するための装置である。波長切り替え最適化装置２０は、オペレーションシステム１０に接続し、ADMの配置情報のような必要なデータの取得と、取得データを用いた波長切り替えの最適化を実施する。波長切り替え最適化装置２０は、リング網の運用者又は設計者が直接操作する波長切り替え表示装置３０からの要求を受け、算出した波長切り替えに関する情報を波長切り替え表示装置３０に送信する。
【００２０】
オペレーションシステム１０、波長切り替え最適化装置２０及び波長切り替え表示装置３０のそれぞれは、プロセッサ等のＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）等のメモリ装置、ハードディスク等の記憶装置等から構成されたコンピュータでもよい。例えば、それぞれの装置の機能及び処理は、記憶装置又はメモリ装置に格納されているデータやプログラムをＣＰＵが実行することによって実現される。
【００２１】
図２は、本発明の実施例に係るシステムを構成する装置の機能ブロック図である。
【００２２】
オペレーションシステム１０は、機能部としてのネットワークデータ収集部１０１、及び、データベースとしてのネットワーク情報データベース１０３から構成される。
【００２３】
ネットワークデータ収集部１０１は、オペレーションシステム１０が管理するリング網上の各波長と接続するADMのノード番号を時間帯及び波長毎に収集し、ネットワーク情報としてネットワーク情報データベース１０３に蓄積する。また、リング網のノード数、波長数もネットワーク情報データベース１０３に蓄積する。
【００２４】
波長切り替え最適化装置２０は、機能部としてのデータ取得部２０１、波長切り替え最適化部２０３、及び、データベースとしてのADM配置情報データベース２０５から構成される。
【００２５】
データ取得部２０１は、オペレーションシステム１０がネットワーク情報データベース１０３で管理する情報のうち、波長切り替え最適化に必要な情報として、異なる時間帯の各波長につき、ADMが接続するノード番号群（ADMの配置情報）を取得し、ADM配置情報データベース２０５に蓄積する。
【００２６】
波長切り替え最適化部２０３は、このADM配置情報データベース２０５に蓄積されたADMの配置情報を用いて、以下に示すような計算を実施することで異なる時間帯において定められた１波長に割り当てたADM群の間で、時間帯の変わったときの波長の最適切り替えを求める。
【００２７】
波長切り替え表示装置３０は、機能部としての波長切り替え表示部３０１から構成される。波長切り替え表示部３０１は、通信網の運用者又は設計者による操作に基づき、波長切り替え最適化装置２０に対して、設計・運用・管理の対象である通信網の最適波長切り替え値の取得要求を実施し、波長切り替え最適化装置２０から受信した値を表示する。
【００２８】
以下に、波長切り替え最適化装置２０における波長切り替え最適化部２０３について詳細に説明する。
【００２９】
波長切り替え最適化部２０３は、時間帯が変わったときにどちらの時間帯でも使えるようなADMを増やすように、ADMの接続先波長の切り替えを最適化する。具体的には以下に説明するように、ADM接続先の波長切り替えの最適化問題を、まず、０−１整数計画法によって求める。また波長数が多くなったときには、そのうえで、この問題を重みづけ制約充足問題として解く。
【００３０】
対象とするリング網をnノードからなるリング網とし、異なる時間帯における波長数は、それぞれm個あり、それぞれλ1i,λ2i（1≦i≦m）とする。波長λ1i,λ2iがそれぞれjノードのADMと接続するときa1(i,j)=1,a2(i,j)=1、接続しないときa1(i,j)=0,a2(i,j)=0と置き、ADMの配置情報を表す（1≦i≦m,1≦j≦n）。今、リング網の各ノードにおいてADMの接続先波長を、時間帯が変わったときにλ1iからλ2kに切り替えることを０−１変数x(i,p)（1≦i,p≦m)によって、x(i,k)=1,x(i,p)=0（p≠k）と表す。ここで、接続先波長を切り替えるときx(i,k)=1、切り替えないときx(i,p)=0である。
【００３１】
このとき、λ1i,λ2kペアによる全時間帯におけるADMの個数は、
【００３２】
【数１】
2016136663.tif 000003
となる。
【００３３】
ここで、波長を切り替えたとき、できるかぎりADMを使い続けるようにすれば、ADMの個数を節約することができる。これは波長λ1i,λ2k間の距離d(λ1i,λ2k)を、
【００３４】
【数２】
2016136663.tif 000004
としたとき、d(λ1i,λ2k)が小さくなるように波長λ1i,λ2kの組み合わせを変えることに相当する。この組み合わせ最適化問題を０−１整数計画問題として定式化する。まず、目的関数として、全時間帯における必要ADMの個数
【００３５】
【数３】
2016136663.tif 000005
をとり、これをx(i,k)（1≦i,k≦m）を変化させて最小化する。変数x(i,k)についての制約条件は、
【００３６】
【数４】
2016136663.tif 000006
【００３７】
【数５】
2016136663.tif 000007
【００３８】
【数６】
2016136663.tif 000008
である。
【００３９】
x(i,k)に関する０−１整数計画法(3)〜(6)を解くことにより、ADMの接続先波長の最適切り替え解x(i,k)（1≦i,k≦m）を求めることができる。
【００４０】
mが大きくなったときは、この問題が難しくなって厳密解を求めることが困難になるが、以下に示すように問題全体を制約式群とみなし、重みづけ制約充足問題として捉えて、タブーサーチ等を用いた数理計画法ツールによってこの問題を現実的な時間内で近似的に解くことができる。
【００４１】
まず、絶対に充足しなくてはならない制約式群としてhardConstraintを(4),(5),(6)として定義する。このもとで、必ずしも充足しなくてもよいができるだけ充足させたい制約式としてsoftConstraintを(3)を変形して、次のように定義する。
【００４２】
【数７】
2016136663.tif 000009
左辺の値は正であって、この制約式を変数x(i,k)は充足しないけれども、重みづけ制約充足問題のツールでは、(7)をできるだけ充足させるように、(4),(5),(6)を厳密に満たしつつ、(7)式の左辺の正値をできるだけ小さくするようにタブーサーチ等を行ってx(i,k)の探索を行い、近似解を求める。これによって、mが大きくなったとき、総当たり法では算出が困難な本問題を実用的な時間内で解くことができる。
【００４３】
次に、図３を参照してADM接続先の波長の切り替えの例を示す。５ノードのリング網上に３つの波長を通し、１つの波長は複数のトラヒックを疎通するものとする。トラヒックは量子化されていて、１つの波長が収容できるトラヒック数（グラニュラリティ）g＝５とする。リング網上トラヒックはすべて同一方向に流れて、逆方向のパスは障害時のパスとして空けてあるものとする。トラヒックは発信ノードをi、着信ノードをjとしたとき、１トラヒック当たりi-jと記載する。発信ノード及び着信ノードにおいては、該当する波長に対してADM（多重化・多重分離装置）を設置して、トラヒックの光電気変換（多重化、多重分離）ができるようにする。トラヒックの需要に応じて必要なノードにだけADMを設置してコスト削減を図る。
【００４４】
ノードに１から５まで番号をつけて、昼間のトラヒックR1と夜間のトラヒックR2を次のように定義する。
R1={1-2,1-2,1-2,1-3,1-3,1-4,1-4,1-5,1-5,1-5,2-3,2-4,2-5}
R2={1-2,1-2,1-2,2-3,2-3,2-4,2-4,2-4,2-5,2-5,1-3,1-4,1-5}
昼間の波長をλ11,λ12,λ13、夜間の波長をλ21,λ22,λ23として、グラニュラリティg=5を考慮すると、例えば、λ11には、ノード１からノード２までの３トラヒックと、ノード１からノード３までの２トラヒックと、ノード２からノード３までの１トラヒックとを収容でき、λ12には、ノード１からノード４までの２トラヒックと、ノード１からノード５までの３トラヒックとを収容できる。以下同様にして、トラヒックR1,R2を収容する次のようなADM配置を考える。
a1(1,1)=a1(1,2)=a1(1,3)=1,a1(1,4)=a1(1,5)=0,
a1(2,1)=a1(2,4)=a1(2,5)=1,a1(2,2)=a1(2,3)=0,
a1(3,2)=a1(3,4)=a1(3,5)=1,a1(3,1)=a1(3,3)=0,
a2(1,2)=a2(1,4)=a2(1,5)=1,a2(1,1)=a2(1,3)=0,
a2(2,1)=a2(2,2)=a2(2,3)=1,a2(2,4)=a2(2,5)=0,
a2(3,1)=a2(3,4)=a2(3,5)=1,a2(3,2)=a2(3,3)=0.
上記のADM配置は図３に示すようになる。ここで、次の２通りの波長切り替えを考える。
1)  λ11←→λ21,λ12←→λ22,λ13←→λ23
2)  λ11←→λ22,λ12←→λ21,λ13←→λ23
波長切り替え1)で必要となるADM数は5+5+4=14であり、波長切り替え2)で必要になるADM数は3+4+4=11である。この場合では、うまく切り替えることにより、３つのADMを節約できる。この場合、波長数=3なので組み合わせの数は6であり、計算は容易であるが、波長数mが増えると組み合わせの数m!は急激に増えて計算が困難になる。そのような場合に本発明の実施例の手法が有用である。
【００４５】
＜本発明の実施例の効果＞
以上のように、本発明の実施例によれば、時間帯によってトラヒックの分布が異なる状況で、時間帯が変わったときにトラヒックの利用する波長を最適に切り替えて、必要なADMの個数を減らすことで、トラヒックをリング網に経済的に疎通することが可能になる。
【００４６】
時間帯によってリング網のノード間を流れるトラヒックの分布が変わる状況において、トラヒックを時間帯毎に最適な波長を通して必要となるADM数を削減するためには、総当たり法によって組み合わせ最適化問題を解かなければいけないような状況がある。
【００４７】
従来技術においては、総当たり法を行えば、異なる時間帯におけるトラヒック変動をできるだけ吸収するようなADMのノード配置を可能にするADM接続先の波長の切り替えを最適化できることが分かっていた（非特許文献２参照）。しかし、総当たり法では、波長の数が増えたとき計算時間が膨大となり実用的な時間内では解くことができなかった。本発明の実施例では、トラヒックが時間変動する場合においても、本来、総当たり法で解決するADM接続先の波長切り替えの最適化問題を、まず、０−１整数計画法に定式化し、そのうえで、この問題を重みづけ制約充足問題として解くことで、波長の数が増えた場合においても、実用的な精度で、実用的な時間内で解を求めることが可能になる。
【００４８】
説明の便宜上、本発明の実施例に係る波長切り替え最適化装置は機能的なブロック図を用いて説明しているが、本発明の実施例に係る波長切り替え最適化装置は、ハードウェア、ソフトウェアまたはそれらの組み合わせで実現されてもよい。例えば、本発明の実施例は、コンピュータに対して本発明の実施例に係る波長切り替え最適化装置の各機能を実現させるプログラム、コンピュータに対して本発明の実施例に係る方法の各手順を実行させるプログラム等により、実現されてもよい。また、各機能部が必要に応じて組み合わせて使用されてもよい。
【００４９】
以上、時間帯によってトラヒックの分布が異なる状況で、トラヒックをリング網に経済的に疎通するための手法について説明したが、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【符号の説明】
【００５０】
１０    オペレーションシステム
１０１  ネットワークデータ収集部
２０    波長切り替え最適化装置
２０１  データ取得部
２０３  波長切り替え最適化部
２０５  ADM配置情報データベース
３０    波長切り替え表示装置
３０１  波長切り替え表示部
【図１】
2016136663.tif 000018
【図２】
2016136663.tif 000019
【図３】
2016136663.tif 000020