(57)【要約】【課題】大規模な波長分割多重光ネットワークにおいて光回線の切断を抑制しながら波長再配置を実現する。【解決手段】ネットワーク設計装置は、波長分割多重光ネットワークに設定されている複数の光回線に対する波長割当てを表す第１の波長配置に基づいて第２の波長配置を決定する波長再配置部と、第１の波長配置から第２の波長配置への遷移を実現するために切断が必要となる切断対象光回線を複数の光回線の中から探索する探索部と、第１の波長配置と第２の波長配置との差分および切断回線探索部による探索結果に基づいて、第１の波長配置から第２の波長配置への遷移の手順を表す手順情報を生成する手順情報生成部と、を備える。【選択図】図７
2018014565.tif 000002
【特許請求の範囲】
【請求項１】
波長分割多重光ネットワークに設定されている複数の光回線に対する波長割当てを表す第１の波長配置に基づいて第２の波長配置を決定する波長再配置部と、
前記第１の波長配置から前記第２の波長配置への遷移を実現するために切断が必要となる切断対象光回線を前記複数の光回線の中から探索する探索部と、
前記第１の波長配置と前記第２の波長配置との差分および前記切断回線探索部による探索結果に基づいて、前記第１の波長配置から前記第２の波長配置への遷移の手順を表す手順情報を生成する手順情報生成部と、
を備えるネットワーク設計装置。
【請求項２】
前記波長再配置部は、前記第１の波長配置において予め指定された規則を満足する光回線に対する波長割当てを変更することにより前記第２の波長配置を決定する
ことを特徴とする請求項１に記載のネットワーク設計装置。
【請求項３】
前記波長再配置部は、
前記波長分割多重光ネットワークの各スパンについて、前記第１の波長配置においていずれかの光回線に割り当てられている波長スロットの帯域の合計を表す個別使用帯域を計算し、
各スパンについて計算された個別使用帯域の中の最大値を表す最大帯域を計算し、
光回線に対して割当て可能な複数の波長スロットの中で最も波長の短い波長スロットまたは最も波長の長い波長スロットを基準として、前記最大帯域を越える波長領域に属する波長スロットが割り当てられている光回線に対する波長割当てを変更する
ことを特徴とする請求項１に記載のネットワーク設計装置。
【請求項４】
前記手順情報生成部は、前記探索部により検出された切断対象光回線を切断する指示を含む手順情報を生成する
ことを特徴とする請求項１に記載のネットワーク設計装置。
【請求項５】
前記第２の波長配置において前記探索部により検出された切断対象光回線に割り当てられる波長を変更することにより前記第２の波長配置を調整する波長配置調整部をさらに備える
ことを特徴とする請求項１に記載のネットワーク設計装置。
【請求項６】
前記波長配置調整部は、前記探索部により特定された切断対象光回線の中から１つの切断対象光回線を抽出する第１の処理、および抽出した切断対象光回線に割り当てられる波長を変更する第２の処理を、前記第１の波長配置から前記第２の波長配置への遷移を実現するために切断が必要となる光回線が存在しなくなるまで実行する
ことを特徴とする請求項５に記載のネットワーク設計装置。
【請求項７】
前記波長配置調整部は、前記探索部により特定された切断対象光回線の中から前記第２の波長配置において最も長い波長が割り当てられる光回線を選択し、選択した光回線に割り当てられる波長を変更する
ことを特徴とする請求項５に記載のネットワーク設計装置。
【請求項８】
前記波長配置調整部は、
前記探索部により特定された切断対象光回線の中から、前記第２の波長配置において最も長い波長が割り当てられる光回線を第１位の優先順位で選択し、
前記探索部により特定された切断対象光回線の中から、スパン数が所定の閾値よりも少ない光回線を第２の優先順位で選択し、
前記探索部により特定された切断対象光回線の中から、割り当てられる波長スロットの数が所定の閾値よりも少ない光回線を第３の優先順位で選択し、
前記第２の波長配置において前記選択した光回線に割り当てられる波長を変更する
ことを特徴とする請求項５に記載のネットワーク設計装置。
【請求項９】
ネットワーク設計を行うネットワーク設計装置で実行される処理方法において、
波長分割多重光ネットワークに設定されている複数の光回線に対する波長割当てを表す第１の波長配置に基づいて第２の波長配置を決定し、
前記第１の波長配置から前記第２の波長配置への遷移を実現するために切断が必要となる切断対象光回線を前記複数の光回線の中から探索し、
前記第１の波長配置と前記第２の波長配置との差分および前記切断対象光回線の探索結果に基づいて、前記第１の波長配置から前記第２の波長配置への遷移の手順を表す手順情報を生成する
ことを特徴とする処理方法。
【請求項１０】
前記第２の波長配置において前記切断対象光回線に割り当てられる波長を変更することにより前記第２の波長配置が調整される
ことを特徴とする請求項９に記載の処理方法。
【請求項１１】
波長分割多重光ネットワークに設定されている複数の光回線に対する波長割当てを表す第１の波長配置に基づいて第２の波長配置を決定し、
前記第１の波長配置から前記第２の波長配置への遷移を実現するために切断が必要となる切断対象光回線を前記複数の光回線の中から探索し、
前記第１の波長配置と前記第２の波長配置との差分および前記切断対象光回線の探索結果に基づいて、前記第１の波長配置から前記第２の波長配置への遷移の手順を表す手順情報を生成する
処理をコンピュータに実行させるネットワーク設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、波長分割多重光ネットワークを設計する装置、方法、およびプログラムに係わる。
【背景技術】
【０００２】
波長分割多重（ＷＤＭ：Wavelength Division Multiplexing）技術を用いて光回線を収容する場合、ネットワーク管理システムは、各光回線に対して波長を割り当てる。収容すべき光回線に対して波長を割り当てる処理は、波長割当て設計と呼ばれることがある。なお、以下の記載において「光回線」は、２つのノード間に設定される光パス（又は、波長パス）に相当する。
【０００３】
波長割当て設計においては、各光ファイバ上に設定される光回線の波長が互いに異なるように、各光回線に対して波長が割り当てられる。また、ネットワークのコストを抑制するために、多くのケースにおいて、光回線の始点ノードから終点ノードまでの経路上で同じ波長が使用される。
【０００４】
近年では、例えば、ＳＤＮ（Software Defined Networking）技術により、必要なときに必要な帯域の光回線を設定する運用形態が普及しつつある。即ち、光回線の追加または削除が頻繁に行われることがある。このため、ある時点において波長利用効率が高くなるように各光回線に波長が割り当てられていても、その後、光回線が追加または削除されると、波長利用効率が低下することがある。よって、波長利用効率をモニタし、波長利用効率が低下したときに波長配置を変更する運用が求められている。運用中に波長配置を変更する動作は、波長再配置またはデフラグメンテーション（又は、単に「デフラグ」）と呼ばれることがある。
【０００５】
図１（ａ）に示す例では、ノードＡ〜Ｆを含むＷＤＭ光ネットワークにおいて、波長スロット１〜１１を利用して１３本の光回線が設定されている。但し、この波長配置では、波長利用効率が高いとはいえない。例えば、波長スロット１は、ノードＥ、Ｆ間のリンクで使用されているが、ノードＡ、Ｅ間では使用されていない。また、波長スロット２は、ノードＡ、Ｄ間の各リンクで使用されているが、ノードＤ、Ｆ間では使用されていない。なお、波長スロットは、光回線に対して割り当てられる波長資源の最小単位に相当する。
【０００６】
図１（ｂ）は、図１（ａ）に示すＷＤＭ光ネットワークに対して波長再配置を実行した結果の一例を示す。この例では、波長スロット８〜１１は、いずれの光回線にも割り当てられていない。すなわち、波長スロット８〜１１は、任意のリンクにおいて、新たな光回線に割り当てることができる。このように、波長再配置により、ＷＤＭ光ネットワークの波長利用効率を改善することができる。
【０００７】
関連技術として、再配置の前と比較して使用周波数領域が小さくなるように波長パスを設計する波長パス再配置方法が提案されている（例えば、特許文献１）。スロットに割り当てられたデマンドの解消数を抑えながらネットワークを再最適化する方法が提案されている（例えば、特許文献２）。さらに、光回線への影響を抑制しながら波長再配置を行う方法が提案されている（例えば、非特許文献１）。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許出願公開２０１３／０１９５４６０号
【特許文献２】特開２０１４−２２９９３８号公報
【非特許文献】
【０００９】
【非特許文献１】Y.Takita et al., Wavelength Defragmentation with Minimum Optical Path Disruptions for Seamless Service Migration, OFC2016, M2J.3
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述のように、波長再配置によりＷＤＭ光ネットワークの波長資源の利用効率を改善することができる。ところが、波長再配置に従って波長スロットを変更する最適な手順を決定することは容易ではない。例えば、光回線を切断することなく各光回線に割り当てる波長スロットを変更する手順を決定することは容易ではない。
【００１１】
なお、上述の論文Y.Takita et al.によれば、光回線の切断を最小化しながら各光回線に割り当てる波長スロットを変更する手順を決定することができる。ただし、光ネットワーク内のノード数が多く、そのトポロジが複雑であるときには、最適な波長配置および波長スロットの変更手順を決定するために長い時間を要する。このため、従来技術においては、大規模なＷＤＭ光ネットワークの波長配置を動的に変更することは困難である。
【００１２】
本発明の１つの側面に係わる目的は、大規模な波長分割多重光ネットワークにおいて光回線の切断を抑制しながら波長再配置を実現することである。
【課題を解決するための手段】
【００１３】
本発明の１つの態様のネットワーク設計装置は、波長分割多重光ネットワークに設定されている複数の光回線に対する波長割当てを表す第１の波長配置に基づいて第２の波長配置を決定する波長再配置部と、前記第１の波長配置から前記第２の波長配置への遷移を実現するために切断が必要となる切断対象光回線を前記複数の光回線の中から探索する探索部と、前記第１の波長配置と前記第２の波長配置との差分および前記切断回線探索部による探索結果に基づいて、前記第１の波長配置から前記第２の波長配置への遷移の手順を表す手順情報を生成する手順情報生成部と、を備える。
【発明の効果】
【００１４】
上述の態様によれば、大規模な波長分割多重光ネットワークにおいて光回線の切断を抑制しながら波長再配置を実現することができる。
【図面の簡単な説明】
【００１５】
【図１】波長デフラグによる波長利用効率の改善の例を示す図である。
【図２】ネットワーク設計装置が使用される光ネットワークシステムの一例を示す図である。
【図３】波長デフラグの一例を示す図である。
【図４】図３（ｂ）に示す波長配置への遷移の手順の一例を示す図である。
【図５】図３（ｃ）に示す波長配置への遷移の手順の一例を示す図である。
【図６】ＷＤＭ光ネットワークにおいて使用される波長スロットの一例を示す図である。
【図７】第１の実施形態のネットワーク設計装置の一例を示す図である。
【図８】波長スロットの利用状況に応じて光回線を選択する方法の一例を示す図である。
【図９】切断回線探索部の処理の一例を示すフローチャートである。
【図１０】切断回線探索部の処理の一例を示す図である。
【図１１】第２の実施形態のネットワーク設計装置の一例を示す図である。
【図１２】波長配置調整部の処理の一例を示すフローチャートである。
【図１３】波長配置調整部による波長変更の一例を示す図である。
【図１４】波長配置調整部による調整処理の一例を示す図である。
【図１５】波長デフラグのシミュレーション結果の一例を示す図である。
【図１６】第１の実施形態による波長デフラグの後の波長配置を示す図である。
【図１７】第２の実施形態による波長デフラグの後の波長配置を示す図である。
【図１８】第１の実施形態および第２の実施形態による効果を示す表である。
【図１９】ネットワーク設計装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１６】
図２は、本発明の実施形態に係わるネットワーク設計装置が使用される光ネットワークシステムの一例を示す。図２に示す例では、ノードＡとノードＢとの間、ノードＢとノードＣとの間は、それぞれ光ファイバリンクで接続されている。
【００１７】
光ネットワークシステムは、ノード間で波長分割多重光信号（以下、ＷＤＭ信号）を伝送する。よって、各ノードに設けられるノード装置は、例えば、光分岐挿入装置（ＲＯＡＤＭ：Reconfigurable Optical Add-Drop Multiplexer）により実現される。
【００１８】
ネットワーク設計装置１は、光回線の設定、削除、変更に係わる回線デマンドを受信すると、その回線デマンドに応じて波長配置を決定する。波長配置は、各光回線に対する波長の割当てを表す情報を含む。ネットワーク制御装置２は、各ノードに接続されている。そして、ネットワーク制御装置２は、ネットワーク設計装置１により決定される波長配置に従って、各ノード装置に対して、光回線の設定、削除、変更を指示する。この結果、回線デマンドに応じた光ネットワークが構築される。
【００１９】
ネットワーク設計装置１は、定期的にまたはネットワーク管理者からの指示に応じて、光ネットワークの波長利用効率をモニタする。そして、光ネットワークの波長利用効率が所定の基準レベルよりも低いときは、ネットワーク設計装置１は波長再配置を実行する。波長再配置は、光ネットワーク上に設定されている１または複数の光回線に割り当てられている波長を変更する処理を含む。そして、ネットワーク設計装置１は、新たな波長配置を表す配置情報をネットワーク制御装置２に与える。そうすると、ネットワーク制御装置２は、その配置情報に従って光ネットワークを再構成する。この結果、光ネットワークの波長利用効率が改善される。
【００２０】
図３は、波長デフラグの一例を示す。この実施例では、図３（ａ）に示すように、ノードＡ〜Ｃを含む光ネットワーク上に光回線Ｐ１〜Ｐ４が設定されている。光回線Ｐ１、Ｐ３は、それぞれ、ノードＡからノードＢを経由してノードＣへ至る経路上に設定されている。光回線Ｐ２は、ノードＡ、Ｂ間に設定されている。光回線Ｐ４は、ノードＢ、Ｃ間に設定されている。さらに、光回線Ｐ１、Ｐ２、Ｐ３、Ｐ４に対してそれぞれ波長スロット４、３、２、１が割り当てられている。すなわち、光回線Ｐ１〜Ｐ４を設定するために４個の波長スロットが使用されている。なお、波長スロットは、光回線に対して割り当てられる波長資源の最小単位に相当する。
【００２１】
図３（ａ）に示す波長配置においては、ノードＡ、Ｂ間で波長スロット１が使用されていない。また、ノードＢ、Ｃ間で波長スロット３が使用されていない。即ち、図３（ａ）に示す波長配置では、光ネットワークの波長利用効率が高いとはいえない。この場合、ネットワーク設計装置１は波長デフラグを実行する。
【００２２】
図３（ｂ）および図３（ｃ）は、波長デフラグにより得られる新たな波長配置の例を示す。いずれのケースにおいても、波長スロット１〜３を使用して光回線Ｐ１〜Ｐ４が設定され、波長スロット４が解放されている。ここで、解放された波長スロット４は、他の光回線に割り当てることができる。すなわち、波長デフラグにより光ネットワークの波長利用効率が改善している。
【００２３】
このように、波長利用効率の改善効果は、図３（ｂ）に示す配置パターン１および図３（ｃ）に示す配置パターン２において互いに同じである。ただし、波長デフラグにおいて各光回線の波長割当てを変更する手順は、配置パターン１と配置パターン２とで互いに異なっている。
【００２４】
図４は、現在の波長配置から図３（ｂ）に示す配置パターン１への遷移の手順の一例を示す。ここでは、Make before brake方式で各光回線に対する波長割当てが変更されるものとする。この場合、以下のステップ１〜ステップ４が実行される。
ステップ１：波長スロット１を使用して新光回線Ｐ２を設定する。
ステップ２：旧光回線Ｐ２を削除する（この結果、波長スロット３が解放される）。
ステップ３：波長スロット３を使用して新光回線Ｐ１を設定する。
ステップ４：旧光回線Ｐ１を削除する（この結果、波長スロット４が解放される）。
【００２５】
このように、Make before brake方式で波長デフラグを実行すれば、光回線が切断されることはない。例えば、光回線Ｐ２の波長スロットを変更する際には、光回線Ｐ２が削除される前に新光回線Ｐ２が設定される。続いて、光回線Ｐ２のデータが新光回線Ｐ２を介して伝送されるように各ノード装置が制御される。この後、旧光回線Ｐ２が削除される。よって、光回線Ｐ２のデータ伝送は、途切れることはない。
【００２６】
ただし、図３（ａ）に示す波長配置から図３（ｂ）に示す配置パターン１への遷移において、光回線Ｐ１に波長スロット３を割り当てるためには、その前に、波長スロット３が解放されていなければならない。すなわち、光回線Ｐ１の波長割当てを変更する前に、光回線Ｐ２の波長割当ての変更が終了していなければならない。
【００２７】
このように、波長デフラグにおいて複数の光回線の波長割当てを変更する場合、光回線間で依存関係が存在することがある。この依存関係は、たとえば、資源依存グラフ（ＲＤＤ：Resource Dependency Digraph）で表される。資源依存グラフでは、波長デフラグ前に光回線ｘに割り当てられていた波長スロットが、デフラグ後に光回線ｙに割り当てられるとき、この依存関係は、有向グラフを用いて「ｘ←ｙ」で表される。「ｘ←ｙ」は、光回線ｙが光回線ｘに依存しており、「光回線ｘの波長割当ての変更が完了しなければ、光回線ｙの波長割当ての変更を実行できない」という状態を表す。
【００２８】
現在の波長配置から配置パターン１へ遷移するケースでは、図３（ｂ）に示す資源依存グラフが生成される。この資源依存グラフは、光回線Ｐ１から光回線Ｐ２へ向かう有向グラフを含む。この有向グラフは、光回線Ｐ１が光回線Ｐ２に依存する状態を表す。なお、光回線Ｐ３、Ｐ４には、有向グラフは接続されていない。
【００２９】
現在の波長配置から配置パターン２へ遷移するケースでは、図３（ｃ）に示す資源依存グラフが生成される。すなわち、この波長デフラグにおいては、以下の依存関係が存在する。
（１）光回線Ｐ１の波長スロットを変更する前に、光回線Ｐ２の波長スロットを変更して波長スロット３を解放する必要がある。
（２）光回線Ｐ２の波長スロットを変更する前に、光回線Ｐ３の波長スロットを変更して波長スロット２を解放する必要がある。
（３）光回線Ｐ３の波長スロットを変更する前に、光回線Ｐ４の波長スロットを変更して波長スロット１を解放する必要がある。
（４）光回線Ｐ４の波長スロットを変更する前に、光回線Ｐ３の波長スロットを変更して波長スロット２を解放する必要がある。
【００３０】
ここで、光回線Ｐ３および光回線Ｐ４は、相互に依存している。この場合、光回線Ｐ３または光回線Ｐ４の一方をいったん切断しなければ、波長割当ての変更を実行することはできない。以下の記載では、この状態を「ループ」と呼ぶことがある。
【００３１】
図５は、現在の波長配置から図３（ｃ）に示す波長配置への遷移の手順の一例を示す。この場合、例えば、以下のステップ１〜ステップ８が実行される。
ステップ１：光回線Ｐ３を切断する。
ステップ２：波長スロット２を使用して新光回線Ｐ４を設定する。
ステップ３：旧光回線Ｐ４を削除する（この結果、波長スロット１が解放される）。
ステップ４：光回線Ｐ３を再設定する。
ステップ５：波長スロット２を使用して新光回線Ｐ２を設定する。
ステップ６：旧光回線Ｐ２を削除する（この結果、波長スロット３が解放される）。
ステップ７：波長スロット３を使用して新光回線Ｐ１を設定する。
ステップ８：旧光回線Ｐ１を削除する（この結果、波長スロット４が解放される）。
【００３２】
このように、資源依存グラフがループを含む波長デフラグにおいては、少なくとも１つの光回線をいったん切断する必要がある。よって、ネットワーク制御装置２は、配置パターン２ではなく、配置パターン１で波長デフラグを行うことが好ましい。
【００３３】
ただし、ノード数の多い大規模な光ネットワークに対して、光回線を切断することなく波長利用効率が改善する最適な波長配置を決定するためには、長い計算時間を要する。そこで、本発明の実施形態に係わるネットワーク設計装置１は、短い計算時間で最適に近い波長配置を決定する機能を備える。
【００３４】
図６は、ＷＤＭ光ネットワークにおいて使用される波長スロットの一例を示す。波長スロットは、光回線に割り当てられる波長資源の最小単位に相当する。よって、ＷＤＭ波長帯は、複数の波長スロットに分割される。図６に示す例では、ＷＤＭ波長帯は、４０個の波長スロットに分割されている。また、各波長スロットの帯域幅は、互いに同じである。波長スロットの帯域幅は、例えば、光周波数で定義される。一例としては、波長スロットの帯域幅は12.5GHzである。
【００３５】
ＷＤＭ光ネットワークにおいて光回線が設定されるときは、その光回線に対して１または複数の波長スロットが割り当てられる。光回線に対して割り当てられる波長スロットの個数は、その光回線を介して伝送される光信号のシンボルレートおよび変調方式などに依存する。図６に示す実施例では、光回線＃１に対して１個の波長スロット（波長スロット１）が割り当てられ、光回線＃２に対して２個の波長スロット（波長スロット２、３）が割り当てられ、光回線＃３に対して１個の波長スロット（波長スロット４）が割り当てられている。
【００３６】
この実施例では、各波長スロットの優先順位が予め決められている。優先順位は、光回線に対して割り当てられる順番を表す。図６に示す実施例では、スロット番号が小さい波長スロットの優先度が高く、スロット番号が大きい波長スロットの優先度が低い。すなわち、要求された光回線に対して複数の波長スロットを割り当てることができる場合には、それら複数の波長スロットの中で最もスロット番号の小さい波長スロットがその光回線に割り当てられる。したがって、初期状態においては、要求された光回線に対して波長スロット１が割り当てられる。また、図６に示す状態において新たな光回線が設定されるときは、その光回線に対して波長スロット５が割り当てられる。なお、以下の記載では、波長スロットを単に「スロット」と呼ぶことがある。
【００３７】
＜第１の実施形態＞
図７は、本発明の第１の実施形態に係わるネットワーク設計装置の一例を示す。第１の実施形態では、ネットワーク設計装置１は、波長再配置部１１、切断回線探索部１３、手順情報生成部１７を備える。ネットワーク情報データベース３０は、ネットワーク設計装置１に内蔵されていてもよいし、ネットワーク設計装置１に接続されていてもよい。
【００３８】
ネットワーク情報データベース３０は、光ネットワークのトポロジを表すトポロジ情報を格納する。トポロジ情報は、ノードを識別するノード情報、隣接ノード間のリンク（または、スパン）を識別するリンク情報を含む。また、ネットワーク情報データベース３０は、光ネットワーク上に設定されている各光回線を表す光回線情報を格納する。光回線情報は、各光回線に対する波長割当てを表す波長配置情報を含む。すなわち、光ネットワークの現在の波長配置を表す情報がネットワーク情報データベース３０に格納されている。
【００３９】
波長再配置部１１は、波長デフラグの実行を指示する再配置指示を受信すると、現在の波長配置よりも波長利用効率の高い新たな波長配置を決定する。現在の波長配置を表す波長配置情報は、上述したように、ネットワーク情報データベース３０に格納されている。再配置指示は、例えば、ネットワーク管理者から与えられる。或いは、再配置指示は、光ネットワークを管理するネットワーク管理システムにより自動的に生成される。
【００４０】
現在の波長配置から新たな波長配置を決定する方法は、特に限定されるものではない。例えば、波長の短い空きスロットから優先的に光回線に割り当てるアルゴリズムにおいては、波長再配置部１１は、各光回線について、現在割り当てられているスロットよりも波長の短いスロットが空いているか否かを判定する。図３（ａ）に示す例では、光回線Ｐ２の波長スロットを「スロット３」から「スロット１」へ変更することができる。さらに、光回線Ｐ２の波長スロットを変更した後は、光回線Ｐ１の波長スロットを「スロット４」から「スロット３」へ変更することができる。この結果、図３（ｂ）に示す波長配置が得られる。或いは、波長再配置部１１は、ファイバスパン数が大きい光回線に対して優先的に波長の短いスロットを割り当てるようにしてもよい。また、波長再配置部１１は、波長の長い空きスロットから優先的に光回線に割り当てるアルゴリズムを使用して波長再配置を実行してもよい。
【００４１】
ただし、ノード数が多く、且つ波長スロット数の多い大規模な光ネットワークにおいては、現在の波長配置から新たな波長配置を決定するために要する時間が長くなるおそれがある。そこで、波長再配置部１１は、光回線選択部１２を利用して、波長割当てを変更することができる光回線を制限する。
【００４２】
光回線選択部１２は、光ネットワーク上に設定されている光回線の中から、波長割当てを変更することができる光回線を選択する。このとき、光回線選択部１２は、例えば、波長スロットの利用状況に応じて光回線を選択してもよい。
【００４３】
図８は、波長スロットの利用状況に応じて光回線を選択する方法の一例を示す。ノードＡ〜Ｄを含む光ネットワーク上に光回線Ｐ１〜Ｐ７が設定されている。具体的には、光回線Ｐ１はノードＡ、Ｂ間に設定され、光回線Ｐ２はノードＢ、Ｃ間に設定され、光回線Ｐ３はノードＣ、Ｄ間に設定され、光回線Ｐ４はノードＡ、Ｃ間に設定され、光回線Ｐ５はノードＢ、Ｄ間に設定され、光回線Ｐ６はノードＡ、Ｂ間に設定され、光回線Ｐ７はノードＢ、Ｃ間に設定されている。なお、光回線Ｐ１、Ｐ２、Ｐ３、Ｐ５、Ｐ６、Ｐ７には、それぞれ各スパンにおいて１個の波長スロットが割り当てられている。光回線Ｐ４には、各スパンにおいて２個の波長スロットが割り当てられている。
【００４４】
光回線選択部１２は、各スパンについて、いずれかの光回線に割り当てられている波長スロットの帯域の合計を表す個別使用帯域を計算する。図８に示す例では、ノードＡ、Ｂ間のスパンにおいて、光回線Ｐ１にスロット１が割り当てられ、光回線Ｐ４にスロット３、４が割り当てられ、光回線Ｐ６にスロット６が割り当てられている。即ち、ノードＡ、Ｂ間のスパンにおいては、４個の波長スロットが使用されている。同様に、ノードＢ、Ｃ間のスパンにおいては、５個の波長スロットが使用されている。ノードＣ、Ｄ間のスパンにおいては、２個の波長スロットが使用されている。
【００４５】
光回線選択部１２は、各スパンについて計算された個別使用帯域の中の最大値を表す最大帯域を計算する。図８に示す例では、最大帯域として「スロット数：５」が得られる。そして、光回線選択部１２は、最も波長の短いスロットを基準として、最大帯域を越える波長領域に属する光回線を選択する。図８に示す例では、スロット１が基準スロットである。よって、スロット５よりも波長の長いスロットが割り当てられている光回線が選択される。具体的には、光回線選択部１２は、スロット６が割り当てられている光回線Ｐ６、Ｐ７を選択する。なお、波長の短い空きスロットから優先的に光回線に割り当てるアルゴリズムにおいては、光回線選択部１２は、最も波長の長いスロットを基準として、最大帯域を越える波長領域に属する光回線を選択する。
【００４６】
波長再配置部１１は、新たな波長配置を決定する際に、光回線選択部１２により選択された光回線の波長割当てを変更することができる。換言すれば、波長再配置部１１は、新たな波長配置を決定する際に、光回線選択部１２により選択されていない光回線の波長割当てを変更しない。図８に示す例では、光回線Ｐ６、Ｐ７についてだけ、波長割当ての変更が許可される。この場合、波長再配置部１１は、例えば、光回線Ｐ６に割り当てる波長スロットをスロット６からスロット２へ変更し、光回線Ｐ７に割り当てる波長スロットをスロット６からスロット１へ変更する。これにより、新たな波長配置が決定される。
【００４７】
なお、光回線選択部１２は、他のポリシに基づいて光回線を選択してもよい。例えば、光回線選択部１２は、ファイバスパン数が所定値よりも少ない光回線を選択してもよい。
【００４８】
上述のように、波長再配置部１１は、波長デフラグの実行を指示する再配置指示を受信すると、現在の波長配置よりも波長利用効率の高い新たな波長配置を決定する。そして、新たな波長配置を表す波長配置情報は、切断回線探索部１３に与えられる。
【００４９】
切断回線探索部１３は、光ネットワーク上に設定されている複数の光回線の中から、現在の波長配置から新たな波長配置への遷移を実現するために切断が必要となる切断対象光回線を探索する。現在の波長配置を表す波長配置情報は、上述したように、ネットワーク情報データベース３０に格納されている。また、新たな波長配置を表す波長配置情報は、波長再配置部１１により生成される。
【００５０】
切断回線探索部１３は、ＲＤＤ作成部１４を利用して、現在の波長配置から新たな波長配置への波長デフラグを表す資源依存グラフ（ＲＤＤ）を作成する。資源依存グラフは、各光回線について、波長デフラグ後の波長配置において割り当てられる波長スロットを特定し、波長デフラグ前の波長配置においてその特定された波長スロットが割り当てられている光回線と検出することで生成される。たとえば、図３（ａ）〜図３（ｂ）に示す例では、波長デフラグ後の波長配置において光回線Ｐ１に波長スロット３が割り当てられている。そして、波長デフラグ前の波長配置においては、波長スロット３は、光回線Ｐ２に割り当てられている。この場合、光回線Ｐ１は、光回線Ｐ２に依存すると判定される。尚、資源依存グラフを作成する方法は、特に限定されるものではなく、公知の技術により作成され得る。
【００５１】
図９は、切断回線探索部１３の処理の一例を示すフローチャートである。このフローチャートの処理は、新たな波長配置を表す波長配置情報が波長再配置部１１から切断回線探索部１３に与えられたときに実行される。
【００５２】
Ｓ１において、ＲＤＤ作成部１４は、現在の波長配置から新たな波長配置への波長デフラグを表す資源依存グラフを作成する。Ｓ２〜Ｓ３において、切断回線探索部１３は、資源依存グラフ内でループを探索する。そして、切断回線探索部１３は、検出したループをループリスト１５に登録する。なお、資源依存グラフ内にループが存在しないときは、切断回線探索部１３の処理は終了する。
【００５３】
Ｓ４において、切断回線探索部１３は、検出したループ内に含まれる光回線を１つ抽出する。このとき、切断回線探索部１３は、属するループの数が最も多い光回線を抽出してもよい。この場合、光回線は、属するループの数の多い順にソートされていることが好ましい。Ｓ５において、切断回線探索部１３は、抽出した光回線を切断回線リスト１６に登録する。
【００５４】
Ｓ６において、切断回線探索部１３は、Ｓ４で抽出した光回線が切断されたときの波長配置に基づいて資源依存グラフを作成する。すなわち、Ｓ４で抽出した光回線が切断されたときの波長配置に基づいて資源依存グラフが更新される。さらに、切断回線探索部１３は、更新された資源依存グラフ内でループを探索する。そして、この探索結果に応じて、切断回線探索部１３は、ループリスト１５を更新する。
【００５５】
Ｓ７において、切断回線探索部１３は、更新されたループリスト１５にループが残っているか否か判定する。更新されたループリスト１５にループが残っているときは、切断回線探索部１３の処理はＳ４に戻る。すなわち、切断回線探索部１３は、資源依存グラフからループがなくなるまでＳ４〜Ｓ６の処理を繰り返し実行する。そして、資源依存グラフからループがなくなると、切断回線探索部１３の処理は終了する。
【００５６】
図１０は、切断回線探索部１３の処理の一例を示す。この実施例では、フローチャートのＳ１において、現在の波長配置および新たな波長配置に基づいて図１０（ａ）に示す資源依存グラフが作成されているものとする。
【００５７】
この場合、Ｓ２〜Ｓ３において、下記の３つのループが検出され、ループリスト１５に登録される。
ループ１：Ｐ１、Ｐ２、Ｐ３、Ｐ４
ループ２：Ｐ１、Ｐ５、Ｐ６、Ｐ７
ループ３：Ｐ８、Ｐ９、Ｐ１０
【００５８】
Ｓ４〜Ｓ５において、切断回線探索部１３は、検出したループ内に属する光回線を１つ抽出する。ここで、光回線Ｐ１は、２つのループ（ループ１、２）に属している。一方、光回線Ｐ２〜Ｐ１０は、それぞれ１つのループに属している。この場合、切断回線探索部１３は、光回線Ｐ１〜Ｐ１０の中から光回線Ｐ１を抽出する。そして、切断回線探索部１３は、抽出した光回線Ｐ１を切断対象光回線として切断回線リスト１６に登録する。
【００５９】
Ｓ６において、切断回線探索部１３は、光回線Ｐ１が切断されたときの波長配置に基づいて新たな資源依存グラフを作成する。この場合、光回線Ｐ１、Ｐ２間の依存関係、光回線Ｐ１、Ｐ４間の依存関係、光回線Ｐ１、Ｐ５間の依存関係、光回線Ｐ１、Ｐ７間の依存関係がそれぞれ消滅する。この結果、図１０（ｂ）に示す資源依存グラフが作成される。この資源依存グラフにおいては、ループ１およびループ２が消滅している。したがって、ループリスト１５は、下記の状態に更新される。
ループ３：Ｐ８、Ｐ９、Ｐ１０
【００６０】
Ｓ７において、切断回線探索部１３は、更新されたループリスト１５にループが残っているか否か判定する。この例では、ループリスト１５にループ３が残っているので、切断回線探索部１３の処理はＳ４に戻る。すなわち、図１０（ｂ）に示す資源依存グラフに対してＳ４〜Ｓ６の処理がもう一度実行される。
【００６１】
Ｓ４〜Ｓ５において、切断回線探索部１３は、ループ３に属する光回線の１つを抽出する。このとき、ループ３に属する光回線Ｐ８、Ｐ９、Ｐ１０は、いずれも１つのループに属している。よって、切断回線探索部１３は、光回線Ｐ８、Ｐ９、Ｐ１０の中の任意の１つを抽出する。ここでは、光回線Ｐ８が抽出されるものとする。そして、切断回線探索部１３は、抽出した光回線Ｐ８を切断対象光回線として切断回線リスト１６に登録する。
【００６２】
Ｓ６において、切断回線探索部１３は、光回線Ｐ８が切断されたときの波長配置に基づいて新たな資源依存グラフを作成する。この場合、光回線Ｐ８、Ｐ６間の依存関係、光回線Ｐ８、Ｐ９間の依存関係、光回線Ｐ８、Ｐ１０間の依存関係がそれぞれ消滅する。この結果、図１０（ｃ）に示す資源依存グラフが作成される。
【００６３】
Ｓ７において、切断回線探索部１３は、更新されたループリスト１５にループが残っているか否か判定する。この例では、ループリスト１５にループは残っていない。したがって、切断回線探索部１３の処理は終了する。そして、上述の処理が終了したとき、切断回線リスト１６には、切断対象光回線として、光回線Ｐ１および光回線Ｐ８が登録されている。
【００６４】
手順情報生成部１７は、現在の波長配置と新たな波長配置との差分、および切断回線探索部１３による探索結果に基づいて、現在の波長配置から新たな波長配置への遷移の手順を表す手順情報を生成する。すなわち、手順情報生成部１７は、現在の波長配置を表す配置情報、新たな波長配置を表す配置情報、更新された資源依存グラフ、および切断回線リスト１６に基づいて、波長デフラグの手順を表す手順情報を生成する。
【００６５】
現在の波長配置を表す配置情報は、ネットワーク情報データベース３０に格納されている。新たな波長配置を表す配置情報は、波長再配置部１１により生成される。資源依存グラフは、ＲＤＤ作成部１４により作成され、切断回線探索部１３により更新される。切断回線リスト１６は、切断回線探索部１３により作成される。ここで、資源依存グラフの初期状態においてループが存在する場合には、切断回線リスト１６に１または複数の光回線が登録されている。そして、切断回線リスト１６に光回線が登録されているときは、手順情報は、切断回線リスト１６に登録されている光回線を切断する指示を含む。
【００６６】
例えば、図３（ａ）に示す波長配置から図３（ｂ）に示す波長配置への波長デフラグを実行する際には、図４を参照しながら説明したステップ１〜ステップ４を指示する手順情報が生成される。また、図３（ａ）に示す波長配置から図３（ｃ）に示す波長配置への波長デフラグを実行する際には、図５を参照しながら説明したステップ１〜ステップ８を指示する手順情報が生成される。
【００６７】
ネットワーク設計装置１により生成される手順情報は、ネットワーク制御装置２へ通知される。そうすると、ネットワーク制御装置２は、その手順情報に従って波長デフラグを実行する。
【００６８】
このように、第１の実施形態のネットワーク設計方法においては、新たな波長配置を決定するプロセスと波長割当ての変更手順を決定するプロセスが分離されている。よって、大規模な光ネットワークであっても、波長デフラグの手順を決定するために要する時間は短い。加えて、波長再配置において波長割当てを変更できる光回線が制限されるので、波長配置を決定するために要する時間も短縮される。
【００６９】
＜第２の実施形態＞
第１の実施形態では、資源依存グラフ内にループが存在するときは、波長デフラグにおいて１または複数の光回線がいったん切断される。これに対して、第２の実施形態では、資源依存グラフ内にループが存在するときは、光回線を切断することなく波長デフラグを実行できるように、波長デフラグ後の波長配置を表す新たな波長配置が調整される。そして、現在の波長配置から調整された新たな波長配置への波長デフラグが実行される。
【００７０】
図１１は、本発明の第２の実施形態に係わるネットワーク設計装置の一例を示す。第２の実施形態では、ネットワーク設計装置１は、波長再配置部１１、切断回線探索部１３、手順情報生成部１７に加えて、波長配置調整部２１を備える。なお、波長再配置部１１、切断回線探索部１３、手順情報生成部１７は、第１の実施形態および第２の実施形態において実質的に同じである。ただし、切断回線探索部１３は、第１の実施形態の機能に加えて、波長配置調整部２１による波長配置の調整に応じて資源依存グラフ、ループリスト１５、切断回線リスト１６を更新する機能を備えていてもよい。
【００７１】
波長配置調整部２１は、切断回線リスト１６に切断対象光回線が登録されているときには、波長再配置部１１により生成された新たな波長配置を調整する。このとき、波長配置調整部２１は、波長デフラグにおいて光回線の切断が回避されるように、新たな波長配置を調整する。具体的には、波長配置調整部２１は、新たな波長配置において、切断回線リスト１６に登録されている切断対象光回線に対して割り当てるべき波長スロットを変更する。
【００７２】
図１２は、波長配置調整部２１の処理の一例を示すフローチャートである。このフローチャートの処理は、切断回線探索部１３において切断対象光回線が特定されたときに実行される。切断対象光回線は、切断回線リスト１６に登録されている。例えば、図１０に示す実施例では、切断対象光回線として、切断回線リスト１６に光回線Ｐ１および光回線Ｐ８が登録されている。そして、このフローチャートの処理は、切断対象光回線が属するループに対して実行される。
【００７３】
Ｓ１１〜Ｓ１２において、波長配置調整部２１は、切断対象光回線が属するループを検出する。そして、切断対象光回線が１つのループのみに属するのか、複数のループに属するのかを判定する。例えば、図１０に示す例では、光回線Ｐ１は、２個のループに属している。また、光回線Ｐ８は、１個のループに属している。
【００７４】
切断対象光回線が１つのループのみに属するときは、Ｓ１３において、波長配置調整部２１は、そのループ内の光回線に対して波長変更処理Ｘを実行する。波長配置調整部２１は、まず、下記の優先順位に従って、そのループに属する光回線の中から波長割当てを変更すべき変更候補光回線を探索する。
第１優先：波長デフラグ後の波長配置において割り当てられる波長が最も長い
第２優先：スパン数が所定数よりも少ない
第３優先：帯域幅が所定の閾値よりも狭い
【００７５】
続いて、波長配置調整部２１は、変更候補光回線に対して下記の２つの条件を満足する波長スロットを探索する。
条件１：ループが解消する
条件２：目標最長波長よりも短い波長のスロット
目標最長波長は、例えば、図８に示す閾値を使用する。但し、波長の長い空きスロットから優先的に光回線に割り当てるアルゴリズムを使用して波長配置が行われるケースでは、条件２では、目標最短波長よりも長い波長のスロットが探索される。
【００７６】
図１３は、波長配置調整部２１による波長変更の一例を示す。図１３（ａ）は、現在の波長配置を表し、図１３（ｂ）は、波長デフラグ後の波長配置を表す。波長デフラグ後の波長配置は、波長再配置部１１により決定される。そして、この波長デフラグの資源依存グラフは、図１３（ｂ）に示すように、ループを含んでいる。すなわち、図１３（ａ）および図１３（ｂ）に示す波長デフラグを実現するためには、少なくとも１つの光回線を切断する必要がある。
【００７７】
波長配置調整部２１は、まず、上述の優先順位に従って、このループに属する光回線Ｐ１〜Ｐ５の中から変更候補光下線を抽出する。すなわち、波長配置調整部２１は、まず、第１優先に対応する光回線を特定する。図１３（ｂ）に示す例では、波長デフラグ後の波長配置において最も波長の長いスロットは、波長スロット５である。そして、波長スロット５は、光回線＃３に割り当てられている。よって、波長配置調整部２１は、光回線＃３に対して波長変更処理Ｘを実行する。ここで、光回線＃３が上述の条件１、２を満足するものとする。この場合、波長配置調整部２１は、波長デフラグ後に光回線＃３に割り当てる波長スロットを変更する。この例では、図１３（ｃ）に示すように、波長デフラグ後の波長配置において、光回線＃３に割り当てる波長スロットがスロット５からスロット６へ変更される。この結果、光回線＃３と光回線＃５との間の依存関係が消滅し、ループが解消される。したがって、いずれの光回線も切断することなく、図１３（ａ）に示す波長配置から図１３（ｃ）に示す波長配置への波長デフラグを実行することができる。
【００７８】
なお、第１優先で選択された光回線が上述の条件１、２を満足しなかったときは、波長配置調整部２１は、第２優先または第３優先で選択される光回線に対して波長変更処理Ｘを実行してもよい。
【００７９】
Ｓ１４において、波長配置調整部２１は、資源依存グラフのループか解消したか否かを判定する。そして、ループが解消していれば、波長配置調整部２１の処理は終了する。一方、ループが解消していなければ、波長配置調整部２１の処理はＳ１８へ移動する。
【００８０】
切断対象光回線が複数のループに属するときは（Ｓ１２：Ｙｅｓ）、Ｓ１５において、波長配置調整部２１は、その切断対象光回線に対して波長変更処理Ｘを実行する。すなわち、切断対象光回線が上述の条件１、２を満足するときには、波長配置調整部２１は、波長デフラグ後の波長配置において、その光回線に割り当てる波長スロットを変更する。
【００８１】
Ｓ１６において、波長配置調整部２１は、資源依存グラフのループが解消したか否かを判定する。ループが解消していれば、波長配置調整部２１の処理は終了する。一方、ループが解消していなければ、波長配置調整部２１の処理はＳ１７へ移動する。
【００８２】
Ｓ１７において、波長配置調整部２１は、残っている各ループに属する光回線に対して波長変更処理Ｘを実行する。この結果、ループがさらに残っている場合には、波長配置調整部２１の処理はＳ１８へ移動する。
【００８３】
Ｓ１８において、波長配置調整部２１は、残っている各ループに属する光回線に対して波長変更処理Ｙを実行する。波長変更処理Ｙにおいては、上述の優先順位に従って抽出される変更候補光回線に対して、下記の条件１を満足する波長スロットが探索される。
条件１：ループが解消する
【００８４】
このように、Ｓ１８では、上述の条件２を使用することなく、条件１のみに基づいて波長スロットが探索される。すなわち、波長変更処理Ｘと比較して、波長変更処理Ｙにおいては、目的スロットを容易に得ることができる。この結果、ループが解消すれば、波長配置調整部２１の処理は終了する。一方、Ｓ１８の処理を実行してもループが解消しないときは、波長変更が失敗したと判定される。この場合、波長デフラグにおいて光回線の切断が必要である。
【００８５】
図１４は、波長配置調整部２１による調整処理の一例を示す。図１４（ａ）は、現在の波長配置を表す。すなわち、ノードＡ〜Ｄを含む光ネットワーク上に光回線Ｐ１〜Ｐ７が設定されている。光回線Ｐ１〜Ｐ７を設定するために６個の波長スロットが使用されている。なお、斜線領域は、未使用の波長スロットを表す。
【００８６】
図１４（ｂ）は、波長再配置部１１により決定された新たな波長配置（すなわち、波長デフラグ後の波長配置）を表す。新たな波長配置では、光回線Ｐ１〜Ｐ７に対して可能な限り短い波長を割り当てることにより、波長スロット５、６が解放されている。ただし、資源依存グラフで示すように、２つのループが発生している。すなわち、現在の波長配置から図１４（ｂ）に示す波長配置への波長デフラグを行う場合、光回線Ｐ１または光回線Ｐ４の一方を切断する必要があり、また、光回線Ｐ２または光回線Ｐ５の一方を切断する必要がある。
【００８７】
そこで、波長配置調整部２１は、図１２に示すフローチャートに従って、ループ内の光回線の波長を変更する。光回線Ｐ１、Ｐ４が属するループを解消する場合、波長配置調整部２１は、Ｓ１３の波長変更処理を実行する。ここで、図１４（ｂ）に示す波長配置において、光回線Ｐ１、Ｐ４に対して割り当てられているスロットの波長は、光回線Ｐ７に対して割り当てられているスロットの波長よりも短い。したがって、光回線Ｐ１、Ｐ４は、第１優先では選択されない。ただし、光回線Ｐ１のスパン数は「１」である。よって、第２優先で光回線Ｐ１が選択される。
【００８８】
そうすると、波長配置調整部２１は、図１４（ｃ）に示すように、波長デフラグ後の波長配置において光回線Ｐ１に割り当てる波長スロットをスロット３からスロット５へ変更する。この結果、光回線Ｐ１、Ｐ４が属するループは解消する。
【００８９】
光回線Ｐ２、Ｐ５が属するループを解消する場合も、波長配置調整部２１は、Ｓ１３の波長変更処理を実行する。ここで、図１４（ｃ）に示す波長配置において、光回線Ｐ２に割り当てられているスロットの波長は、他のいずれの光回線に割り当てられているスロットの波長よりも長い。したがって、第１優先で光回線Ｐ２が選択される。この場合、波長配置調整部２１は、図１４（ｄ）に示すように、波長デフラグ後の波長配置において光回線Ｐ２に割り当てる波長スロットをスロット４からスロット５に変更する。この結果、光回線Ｐ２、Ｐ５が属するループは解消する。
【００９０】
この後、手順情報生成部１７は、図１４（ａ）に示す現在の波長配置から図１４（ｄ）に示す新たな波長配置への波長デフラグの手順を表す手順情報を生成する。手順情報は、例えば、資源依存グラフに基づいて生成される。この場合、資源依存グラフを終点から始点に向かって探索することにより手順情報を生成することができる。図１４（ｄ）に示す例では、以下の手順情報が生成される。
ステップ１：スロット５を使用して新光回線Ｐ１を設定する。
ステップ２：旧光回線Ｐ１を削除する（この結果、ノードＡ、Ｂ間でスロット１が解放される）。
ステップ３：波長スロット１を使用して新光回線Ｐ４を設定する。
ステップ４：旧光回線Ｐ４を削除する（この結果、スロット３が解放される）。
ステップ５：スロット３を使用して新光回線Ｐ６を設定する。
ステップ６：旧光回線Ｐ６を削除する（この結果、スロット５が解放される）。
ステップ７：スロット５を使用して新光回線Ｐ２を設定する。
ステップ８：旧光回線Ｐ２を削除する（この結果、スロット２が解放される）。
ステップ９：スロット２を使用して新光回線Ｐ５を設定する。
ステップ１０：旧光回線Ｐ５を削除する（この結果、スロット４が解放される）。
ステップ１１：スロット４を使用して新光回線Ｐ７を設定する。
ステップ１２：旧光回線Ｐ７を削除する（この結果、スロット６が解放される）。
【００９１】
手順情報生成部１７により生成された手順情報は、ネットワーク制御装置２へ送信される。そして、ネットワーク制御装置２は、与えられた手順情報に従って波長デフラグを実行する。
【００９２】
このように、第２の実施形態のネットワーク設計方法によれば、光回線を切断することなく波長デフラグを実現することができる。或いは、波長デフラグ中に切断される光回線の数を削減することができる。したがって、サービスの品質を下げることなく、波長利用効率が改善される。
【００９３】
なお、図１４（ｂ）に示す波長配置では、波長スロット５、６が解放される。これに対して、第２の実施形態のネットワーク設計方法では、図１４（ｄ）に示すように、波長スロット６のみが解放される。すなわち、最適な波長配置と比較すると、第２の実施形態のネットワーク設計方法では、波長利用効率がやや劣るかも知れない。しかしながら、図１４（ａ）に示す現在の波長配置と比較すれば、第２の実施形態のネットワーク設計方法により波長利用効率は改善している。
【００９４】
図１５は、波長デフラグのシミュレーション結果の一例を示す。横軸方向は、光ネットワーク内のノードを表す。縦軸方向は、波長（または、波長スロット）を表す。
【００９５】
図１５（ａ）は、波長デフラグ前の波長配置を示す。図１５（ｂ）および図１５（ｃ）は、それぞれ第１および第２の実施形態のネットワーク設計方法による波長デフラグの結果を表す。図１５（ｄ）は、波長利用効率を最適化する波長デフラグの結果を表す。この波長デフラグは、例えば、論文Y.Takita et al.に記載されているように、数理計画手法（ＩＬＰ：Integer Linear Programming）を利用して実現される。
【００９６】
第１または第２の実施形態のネットワーク設計方法で波長デフラグを行えば、ＷＤＭ光ネットワークの波長利用効率が十分に改善される。ここで、図１５（ｄ）に示す最適な波長デフラグと比較すると、第１または第２の実施形態の波長デフラグでは、波長利用効率が少しだけ劣っている。しかし、大規模な光ネットワークに対しては、数理計画手法等を利用する方法では、波長デフラグ後の波長配置および波長変更手順を決定するために要する時間が非常に長くなってしまう。これに対して、第１または第２の実施形態のネットワーク設計方法では、波長配置および波長変更手順を決定するために要する時間は大幅に短縮される。すなわち、第１または第２の実施形態のネットワーク設計方法によれば、短い処理時間で、最適状態に近い波長利用効率が得られる。
【００９７】
図１６〜図１７は、第１の実施形態と第２の実施形態との差異を示す。なお、図１６および図１７は、それぞれ、図１５（ｂ）および図１５（ｃ）を拡大して示している。
【００９８】
第１の実施形態による波長再配置では、図１６に示すように、２箇所でループが発生している。ループに属する光回線は、白抜きの矩形で表されている。第２の実施形態では、これらのループを解消するために、図１７に示すように、ループに属する光回線のうちの少なくとも１つに対する波長割当てが変更される。なお、このシミュレーションでは、第１の実施形態と第２の実施形態との間で、ＷＤＭ光ネットワークの波長利用効率の改善に係わる効果は実質的に同じである。
【００９９】
図１８は、第１の実施形態および第２の実施形態による効果を示す。ここでは、数理計画法により最適な波長再配置を決定する方法と第１および第２の実施形態とを比較する。
【０１００】
波長デフラグによる資源利用効率の改善は、数理計画法および第１の実施形態において実質的に同じである。一方、数理計画法（または、第１の実施形態）と比較すると、第２の実施形態による資源利用効率の改善はやや小さい。ただし、図１５に示すように、数理計画法と第２の実施形態との差異は僅かである。
【０１０１】
光回線の変更インパクトは、波長デフラグ中の光回線の切断の頻度を表す。数理計画法および第２の実施形態では、波長デフラグ中の光回線の切断の回数は、ゼロまたはほぼゼロである。これに対して、第１の実施形態では、波長デフラグ中に光回線の切断が発生することがある。
【０１０２】
スケーラビリティは、処理可能な光ネットワークの規模を表す。数理計画法では、波長配置および手順を決定するために要する時間が長いので、大規模な光ネットワークにおいて動的に波長デフラグを実行することは困難である。これに対して、第１および第２の実施形態では、波長配置および手順を決定するために要する時間は短い。光ネットワークの構成にもよるが、数理計画法と比較して、第１および第２の実施形態による処理時間は、１０分の１以下である。
【０１０３】
＜ハードウェア構成＞
図１９は、ネットワーク設計装置１のハードウェア構成の一例を示す図である。ネットワーク設計装置１は、例えば、図１９に示すコンピュータシステム１００により実現される。コンピュータシステム１００は、ＣＰＵ１０１、メモリ１０２、記憶装置１０３、読み取り装置１０４、通信インタフェース１０６、入出力装置１０７を備える。ＣＰＵ１０１、メモリ１０２、記憶装置１０３、読み取り装置１０４、通信インタフェース１０６、入出力装置１０７は、例えば、バス１０８に接続される。
【０１０４】
ＣＰＵ１０１は、メモリ１０２を利用して、図９または図１２に示すフローチャートの処理を記述したネットワーク設計プログラムを実行する。これにより、上述したネットワーク設計方法が実現される。すなわち、ＣＰＵ１０１は、波長再配置部１１、切断回線探索部１３、手順情報生成部１７、波長配置調整部２１の機能を提供することができる。
【０１０５】
メモリ１０２は、例えば半導体メモリであり、ＲＡＭ領域およびＲＯＭ領域を含んで構成される。なお、各フローチャートの処理で使用される変数は、メモリ１０２に一時的に格納される。また、ループリスト１５および切断回線リスト１６は、メモリ１０２を利用して実現される。記憶装置１０３は、例えばハードディスク装置であり、上述のネットワーク設計プログラムを格納する。また、記憶装置１０３は、各フローチャートの処理の結果を格納する。なお、記憶装置１０３は、フラッシュメモリ等の半導体メモリであってもよい。また、記憶装置１０３は、外部記憶装置であってもよい。
【０１０６】
読み取り装置１０４は、ＣＰＵ１０１の指示に従って着脱可能記録媒体１０５にアクセスする。着脱可能記録媒体１０５は、例えば、半導体デバイス（ＵＳＢメモリなど）、磁気的作用により情報が入出力される媒体（磁気ディスク等）、光学的作用により情報が入出力される媒体（ＣＤ−ＲＯＭ、ＤＶＤ等）などにより実現される。
【０１０７】
通信インタフェース１０６は、ＣＰＵ１０１の指示に従ってネットワークを介してデータを送信および受信することができる。すなわち、通信インタフェース１０６は、ネットワーク上に存在するサーバ１１０にアクセスすることができる。入出力装置１０７は、ユーザにより操作されるキーボード、マウス、タッチパネル等に相当する。また、入出力装置１０７は、ＣＰＵ１０１による処理結果を出力する。
【０１０８】
実施形態に係わるネットワーク設計プログラムは、例えば、下記の形態でコンピュータシステム１００に与えられる。
（１）記憶装置１０３に予めインストールされている。
（２）着脱可能記録媒体１０５により提供される。
（３）サーバ１１０から提供される。
【符号の説明】
【０１０９】
１  ネットワーク設計部
１１  波長再配置部
１２  光回線選択部
１３  切断回線探索部
１４  ＲＤＤ作成部
１５  ループリスト
１６  切断回線リスト
１７  手順情報生成部
２１  波長配置調整部
【図１】
2018014565.tif 000003
【図２】
2018014565.tif 000004
【図３】
2018014565.tif 000005
【図４】
2018014565.tif 000006
【図５】
2018014565.tif 000007
【図６】
2018014565.tif 000008
【図７】
2018014565.tif 000009
【図８】
2018014565.tif 000010
【図９】
2018014565.tif 000011
【図１０】
2018014565.tif 000012
【図１１】
2018014565.tif 000013
【図１２】
2018014565.tif 000014
【図１３】
2018014565.tif 000015
【図１４】
2018014565.tif 000016
【図１５】
2018014565.tif 000017
【図１６】
2018014565.tif 000018
【図１７】
2018014565.tif 000019
【図１８】
2018014565.tif 000020
【図１９】
2018014565.tif 000021