(57)【要約】【課題】  短時間で波長変換器の配置設計を実行することのできる波長変換器配置設計方法およびその装置を提供する。【解決手段】  設計パラメータ入力部２と、波長変換器を配置するための初期値を入力する波長変換器配置初期値入力部３と、入力された設計パラメータと前記波長変換器配置初期値とに基づいてＲＷＡシミュレーションを実行するＲＷＡシミュレータ部４と、ＲＷＡシミュレーションの結果から波長変換器再配置指標を抽出する波長変換器再配置指標抽出部５と、得られた波長変換器再配置指標に基づいて、波長変換器を再配置する波長変換器再配置部６と、再配置前の波長変換器の配置と再配置後の波長変換器の配置とを比較して、波長変換器配置変動値を求めることにより、配置の変動を判定する波長変換器配置変動判定部７と、前記波長変換器配置変動値が収束するとき、その波長変換器配置を出力する波長変換器配置出力部８とを備えた。【選択図】      図１
2006005693.tif 000002
【特許請求の範囲】
【請求項１】
設計パラメータ入力部から入力された設計パラメータを用いて、ＲＷＡシミュレータ部においてＲＷＡシミュレーションを実行することにより、トランク型で波長変換器を備えた光クロスコネクトノードから構成される波長パスネットワークの波長変換器配置設計を行う波長変換器配置設計方法において、
波長変換器配置初期値入力部において、波長変換器配置初期値を入力する手順と、
前記ＲＷＡシミュレータ部が、入力された設計パラメータと波長変換器配置初期値とに基づいて、ＲＷＡシミュレーションを実行し、ＲＷＡ問題を解く手順と、
波長変換器再配置指標抽出部が、ＲＷＡシミュレーションの結果に基づいて、波長変換器再配置指標を抽出する手順と、
波長変換器再配置部が、抽出された波長変換器再配置指標に基づいて、波長変換器の再配置を実行する手順と、
波長変換器配置変動判定部が、再配置前の波長変換器の配置と再配置後の波長変換器の配置とを比較して、波長変換器配置変動値を求めることにより、配置の変動を判定する手順と、
前記波長変換器配置変動値が収束するとき、波長変換器配置出力部が、その波長変換器配置を出力する手順と、を備えた
ことを特徴とする波長変換器配置設計方法。
【請求項２】
前記波長変換器再配置指標とは、各ノードにおいて設置されている波長変換器に対して、波長変換器が使用されている割合である
ことを特徴とする請求項１に記載の波長変換器配置設計方法。
【請求項３】
前記波長変換器再配置指標とは、各ノードにおいて使用されている波長変換器の個数の平均である
ことを特徴とする請求項１に記載の波長変換器配置設計方法。
【請求項４】
前記波長変換器再配置指標とは、各ノードにおいて波長連続制約条件が満たされないときに、波長変換器を使用することを試みる場合に、当該ノードで利用可能な波長変換器がないために生じる波長パス設定のブロッキング確率である
ことを特徴とする請求項１に記載の波長変換器配置設計方法。
【請求項５】
前記波長変換器再配置指標に基づいて波長変換器を再配置するとき、波長変換器再配置指標に波長変換器の個数を比例させて、波長変換器を配置する
ことを特徴とする請求項１ないし請求項４のいずれか１項に記載の波長変換器配置設計方法。
【請求項６】
前記波長変換器再配置指標に基づいて波長変換器を再配置するとき、波長変換器再配置指標の対数に波長変換器の個数を比例させて、波長変換器を配置する
ことを特徴とする請求項１ないし請求項４のいずれか１項に記載の波長変換器配置設計方法。
【請求項７】
前記収束の判定とは、波長変換器を再配置する前のｘ(before)（下線はベクトルを表す。以下、同じ。）と再配置後のｘ(after)の差分をとり、波長変換器配置変動値Ｖを算出して、波長変換器配置変動値Ｖ＝Σi｜ｘi(before)−ｘi(after)｜が、閾値Ｖth以下
であることを判定する
ことを特徴とする請求項１ないし請求項６のいずれか１項に記載の波長変換器配置設計方法。
【請求項８】
前記収束の判定とは、波長変換器を再配置する前のｘ(before)と再配置後のｘ(after)の差分をとり、波長変換器配置変動値Ｖを算出して、波長変換器配置変動値Ｖ＝Σi｜ｘi
(before)−ｘi(after)｜2が、閾値Ｖth以下であることを判定する
ことを特徴とする請求項１ないし請求項６のいずれか１項に記載の波長変換器配置設計方法。
【請求項９】
設計パラメータ入力部と、ＲＷＡシミュレータ部とを備え、入力された設計パラメータを用いてＲＷＡシミュレーションを実行することにより、波長変換器を備えた光クロスコネクトノードから構成される波長パスネットワークの波長変換器配置設計を行う波長変換器配置設計装置において、
波長変換器を配置するための初期値を入力する波長変換器配置初期値入力部と、
ＲＷＡシミュレーションの結果から波長変換器再配置指標を抽出する波長変換器再配置指標抽出部と、
得られた波長変換器再配置指標に基づいて、波長変換器を再配置する波長変換器再配置部と、
再配置前の波長変換器の配置と再配置後の波長変換器の配置とを比較して、波長変換器配置変動値を求めることにより、配置の変動を判定する波長変換器配置変動判定部と、
前記波長変換器配置変動値が収束するとき、その波長変換器配置を出力する波長変換器配置出力部とを備え、
前記ＲＷＡシミュレータ部は、入力された前記設計パラメータと前記波長変換器配置初期値とに基づいてＲＷＡシミュレーションを実行するようにした
ことを特徴とする波長変換器配置設計装置。
【請求項１０】
前記波長変換器再配置指標とは、各ノードにおいて設置されている波長変換器に対して、波長変換器が使用されている割合である
ことを特徴とする請求項９に記載の波長変換器配置設計装置。
【請求項１１】
前記波長変換器再配置指標とは、各ノードにおいて使用されている波長変換器の個数の平均である
ことを特徴とする請求項９に記載の波長変換器配置設計装置。
【請求項１２】
前記波長変換器再配置指標とは、各ノードにおいて波長連続制約条件が満たされないときに、波長変換器を使用することを試みる場合に、当該ノードで利用可能な波長変換器がないために生じる波長パス設定のブロッキング確率である
ことを特徴とする請求項９に記載の波長変換器配置設計装置。
【請求項１３】
前記波長変換器再配置指標に基づいて波長変換器を再配置するとき、波長変換器再配置指標に波長変換器の個数を比例させて、波長変換器を配置する
ことを特徴とする請求項９ないし請求項１２のいずれか１項に記載の波長変換器配置設計装置。
【請求項１４】
前記波長変換器再配置指標に基づいて波長変換器を再配置するとき、波長変換器再配置指標の対数に波長変換器の個数を比例させて、波長変換器を配置する
ことを特徴とする請求項９ないし請求項１２のいずれか１項に記載の波長変換器配置設計装置。
【請求項１５】
前記収束の判定とは、波長変換器を再配置する前のｘ(before)と再配置後のｘ(after)の差分をとり、波長変換器配置変動値Ｖを算出して、波長変換器配置変動値Ｖ＝Σi｜ｘ
i(before)−ｘi(after)｜が、閾値Ｖth以下であることを判定する
ことを特徴とする請求項９ないし請求項１４のいずれか１項に記載の波長変換器配置設計装置。
【請求項１６】
前記収束の判定とは、波長変換器を再配置する前のｘ(before)と再配置後のｘ(after)の差分をとり、波長変換器配置変動値Ｖを算出して、波長変換器配置変動値Ｖ＝Σi｜ｘ
i(before)−ｘi(after)｜2が、閾値Ｖth以下であることを判定する
ことを特徴とする請求項９ないし請求項１４のいずれか１項に記載の波長変換器配置設計装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、波長多重ネットワークにおける波長変換器配置設計方法およびその装置に関するものである。
【背景技術】
【０００２】
図３は、従来例を示す波長変換器配置設計装置の機能ブロック図である。従来、この種の波長変換器配置設計装置としては、例えば、図３に示すような波長変換器配置設計装置１０が知られている。これは、設計パラメータを入力する設計パラメータ入力部２と、ＲＷＡシミュレータ部４（ＲＷＡについては後に詳述する）と、すべての波長変換器の配置候補を生成する波長変換器配置候補生成部１１と、波長変換器配置指標（後に詳述する）を抽出する波長変換器配置指標抽出部１２と、最適の波長変換器配置を波長変換器配置指標から判定する最適波長変換器配置判定部１３と、選択された波長変換器配置を出力する波長変換器配置出力部８とからなる。
【０００３】
ここで、ＲＷＡ（Routing and Wavelength Assignment）について説明する。例えば、非特許文献１および非特許文献２に記載されているようなトランク型の光クロスコネクトノードにおいて、波長パスの保留時間が有限時間であるとする。波長パスの設定要求が生じて、波長パスが任意の波長を収容可能であれば、波長パスが設定され、保留時間後に波長パスが解除される。また、波長パスが任意の波長を収容不可能であれば、波長パス設定要求が拒絶される。そこで、波長パスを設定するためには、波長パスの経路、各リンクで使用すべき波長を決定する問題を解くことになる。これをＲＷＡ問題という。ＲＷＡ問題を解くということは、波長変換器を各ノードで使用するか否かを決定することになる。
【０００４】
次に、波長変換器配置指標について説明する。波長変換器配置指標とは、例えば、波長パスの設定要求が拒絶される確率、すなわち、呼損率である。波長変換器配置指標を最小にするとは、ネットワーク全体の呼損率を最小にすると定義することであり、また、波長変換器配置指標を最小にするとは、発着ノードごとの呼損率を計測して、呼損率の最大値を最小にすると定義することである。
【０００５】
図４は、従来例を示す波長変換器配置設計方法のフローチャートである。従来の波長変換器の配置設計方法を図４を用いて説明する。ここでは、ネットワーク全体で配置できる波長変換器数をＹとする。ネットワーク内のノード数をｎ、ノードｉに配置する波長変換器ｘi、波長変換器の配置をｘ（下線はベクトルを表す。）とする。ｘ、Ｙは、｛ｘ0、ｘ1、…、ｘn-1｝、Ｙ＝Σiｘiとなる。Ｙ＝Σiｘiの制約の下で、波長変換器配置
指標が最小となるｘを求める。
【０００６】
設計パラメータが設計パラメータ入力部２から入力される（Ｓ１１）。設計パラメータとしては、物理トポロジ、波長の数、リンクコスト、ノード間のトラヒック需要などがある。トラヒック需要は、例えば、波長パスの発着ノードにおいて、波長パス設定要求の到着率分布、保留時間分布で表現される。
【０００７】
次に、波長変換器配置候補生成部１１が、Ｙ＝Σiｘiを満足するｘ＝｛ｘ0、ｘ1、…、ｘn-1｝のすべての候補を列挙する（Ｓ１２）。
【０００８】
そして、波長変換器配置候補生成部１１が、ステップＳ１２で列挙された中から、試行する波長変換器配置候補ｘを選択する（Ｓ１３）。
【０００９】
続いて、ステップＳ１１で取得した設計パラメータとステップＳ１３で選択されたｘに対して、ＲＷＡシミュレータ部４において、ＲＷＡを行うシミュレータを実行させて、ＲＷＡ問題を解く（Ｓ１４）。
【００１０】
次に、波長変換器配置指標抽出部１２が、ＲＷＡシミュレータ部４から、得られた波長変換器配信指標を取得する（Ｓ１５）。
【００１１】
波長変換器配置候補生成部１１が、波長変換器配置候補ｘのすべてを確かめたか否かを確認する（Ｓ１６）。すべてを確かめた（Ｓ１６のＹｅｓ）ならば、ステップＳ１７へ進み、すべてを確かめていない（Ｓ１６のＮｏ）ならば、ステップＳ１３に戻る。
【００１２】
次に、最適波長変換器配置判定部１３が、波長変換器配置指標が最適となる波長変換器配置ｘを選択する（Ｓ１７）。
【００１３】
最後に、波長変換器配置出力部８が最適の波長変換器配置ｘを出力する（Ｓ１８）。図５に波長変換器の配置例を示す。
【非特許文献１】E. Oki, D. Shimazaki, K. Shiomoto, N. Matsuura, W. Imajuku, and N. Yamanaka, “Performance of Distributed-Controlled Dynamic Wavelength-Conversion GMPLS Networks”,International Conference on Optical Communications and Networks(ICOCN 2002), Singapore, Nov. 2002
【非特許文献２】K. Sato, N. Yamanaka, Y. Takigawa, M. Koga, S. Okamoto, K. Shiomoto, E. Oki, and W. Imajuku, “GMPLS-based Photonic Multilayer Router (Hikari Router)  Architecture: An Overview of Traffic Engineering and Signaling Technology”,IEEE Community Magazine, vol. 40, no.3, p.96-101, Mar. 2002.
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、従来の波長変換器配置設計方法およびその装置では、前記した図４のステップＳ１２で列挙する組み合わせの数は、ノード数に対して指数関数的に増加する。そのため、ステップＳ１３からステップＳ１６までの繰り返し回数が膨大な数になる。特に、ステップＳ１４でのシミュレーションに時間を要するので、繰り返し回数が膨大になると、最適な波長変換器配置ｘを求めるために、膨大な時間を要することになり、最適な波長変換器配置を求めることが困難であるという問題点があった。
【００１５】
本発明は、前記問題点に鑑みてなされたものであり、その目的とするところは、短時間で波長変換器の配置設計を実行することのできる波長変換器配置設計方法およびその装置を提供することにある。
【課題を解決するための手段】
【００１６】
本発明は、前記目的を達成するために、設計パラメータ入力部と、ＲＷＡシミュレータ部とを備え、入力された設計パラメータを用いてＲＷＡシミュレーションを実行することにより、波長変換器を備えた光クロスコネクトノードから構成される波長パスネットワークの波長変換器配置設計を行う波長変換器配置設計装置において、波長変換器を配置するための初期値を入力する波長変換器配置初期値入力部と、ＲＷＡシミュレーションの結果から波長変換器再配置指標を抽出する波長変換器再配置指標抽出部と、得られた波長変換器再配置指標に基づいて、波長変換器を再配置する波長変換器再配置部と、再配置前の波長変換器の配置と再配置後の波長変換器の配置とを比較して、波長変換器配置変動値を求めることにより、配置の変動を判定する波長変換器配置変動判定部と、前記波長変換器配置変動値が収束するとき、その波長変換器配置を出力する波長変換器配置出力部とを備え、前記ＲＷＡシミュレータ部は、入力された前記設計パラメータと前記波長変換器配置初期値とに基づいてＲＷＡシミュレーションを実行するようにしている。これにより、初期値と設計パラメータとに基づいてＲＷＡシミュレーションを実行し、波長変換器の再配置を実行し、再配置前の波長変換器の配置と再配置後の波長変換器の配置とを比較して、波長変換器配置変動値を求め、この値が収束すれば、当該波長変換器の配置を出力する。
【発明の効果】
【００１７】
本発明によれば、初期値と設計パラメータとに基づいてＲＷＡシミュレーションを実行し、波長変換器の再配置を実行し、再配置前の波長変換器の配置と再配置後の波長変換器の配置とを比較して、波長変換器配置変動値を求め、この値が収束すれば、当該波長変換器の配置を出力するので、効率よく短時間で波長変換器の配置を求めることができる。
【発明を実施するための最良の形態】
【００１８】
図１および図２は、本発明の一実施形態を示すもので、図１は波長変換器配置設計装置の機能ブロック図である。図２は、本発明の一実施形態を示す波長変換器配置設計方法のフローチャートである。
【００１９】
この波長変換器配置設計装置１は、設計パラメータを入力する設計パラメータ入力部２と、波長変換器を配置するための初期値を入力する波長変換器配置初期値入力部３と、入力された設計パラメータと波長変換器配置初期値を用いてＲＷＡシミュレーションを実行するＲＷＡシミュレータ部４と、ＲＷＡシミュレーションの結果から波長変換器再配置指標（後に詳述する）を抽出する波長変換器再配置指標抽出部５と、得られた波長変換器再配置指標に基づいて波長変換器を再配置する波長変換器再配置部６と、波長変換器の配置のＲＷＡシミュレーション前の配置と比較して、ＲＷＡシミュレーション後の配置の変動を判定する配置波長変換器配置変動判定部７と、決定した波長変換器の配置を出力する波長変換器配置出力部８とから構成されている。
【００２０】
以上のように構成された波長変換器配置設計装置１を用いて実行する波長変換器配置設計方法について、図２を用いて説明する。ここでは、ネットワーク全体で配置できる波長変換器数をＹとする。ネットワーク内のノード数をｎ、ノードｉに配置する波長変換器をｘi、波長変換器の配置をｘとする。ｘ、Ｙは、ｘ＝｛ｘ0、ｘ1、…、ｘn-1｝、Ｙ＝Σiｘiとなる。Ｙ＝Σiｘiの制約の下で、波長変換器再配置指標が最小となるｘを求
める。
【００２１】
初めに、設計パラメータ入力部２において、設計パラメータを入力する（Ｓ１）。設計パラメータとしては、物理トポロジ、波長の数、リンクコスト、ノード間のトラヒック需要がある。トラヒック需要は、例えば、波長パスの発着ノードにおいて、波長パス設定要求の到着率分布、保留時間分布で表される。
【００２２】
次に、波長変換器配置初期値入力部３において、波長変換器配置初期値を入力する（Ｓ２）。ここで、初期値は、Ｙ＝Σiｘiを満足するｘ＝｛ｘ0、ｘ1、…、ｘn-1｝を設定する。初期値としては、例えば、ｘi＝Ｙ／（ｎ−１）と設定することができる。ｘiは整数である必要があるので、必要に応じて、小数点以下を切り上げたり、切り下げたりする。
【００２３】
次に、ＲＷＡシミュレータ部４において、ＲＷＡシミュレータを起動し、入力された設計パラメータと波長変換器配置初期値に基づいて、ＲＷＡシミュレーションを実行し、ＲＷＡ問題を解く（Ｓ３）。
【００２４】
続いて、波長変換器再配置指標抽出部５が、ＲＷＡシミュレーションの結果に基づいて、波長変換器再配置指標を算出する（Ｓ４）。波長変換器再配置指標には次のような指標が考えられる。各ノードにおいて設置されている波長変換器に対して、波長変換器が使用されている割合、すなわち、波長変換器使用率や、各ノードにおいて使用されている波長変換器の個数の平均、すなわち、波長変換器平均使用個数や、波長連続制約条件が満足されない場合に、波長変換器を使用することを試みるとき、当該ノードで利用可能な波長変換器がないために生じる波長パス設定のブロッキング確率、すなわち、波長変換器ブロッキング率（ファイバ内の利用可能な波長が無いために生じるブロッキングは、利用可能な波長変換器の個数に依存しないので、波長変換器ブロッキングとして数えない）などが考えられる。
【００２５】
そして、波長変換器再配置部６において、得られた波長変換器再配置指標に基づいて、波長変換器再配置を実施する（Ｓ５）。例えば、Ｙ＝Σiｘiを満足するｘ＝｛ｘ0、ｘ1、…、ｘn-1｝を、波長変換器再配置指標に波長変換器の個数を比例させて、波長変換器を配置する、または、波長変換器再配置指標の対数に個数を比例させて、波長変換器を配置する。
【００２６】
次に、波長変換器配置変動判定部７において、波長変換器を再配置する前のｘ(before)と再配置後のｘ(after)との差分をとり、波長変換器配置変動値Ｖを算出する。波長変換器変動値Ｖを、例えば、
Ｖ＝Σi｜ｘi(before)−ｘi(after)｜
または、
Ｖ＝Σi｜ｘi(before)−ｘi(after)｜2
と定義する。この波長変換器変動値Ｖが、閾値Ｖth以下であれば、収束と判定し、ステップＳ７に進む。閾値Ｖthより大きければ、収束していないと判断して、ステップＳ３に戻る（Ｓ６）。ステップＳ３ではｘ(after)を用いて、ＲＷＡシミュレーションを行う。
【００２７】
最後に、ステップＳ６で波長変換器変動値Ｖが収束した波長変換器配置ｘを、波長変換器配置出力部８において出力する。
【図面の簡単な説明】
【００２８】
【図１】本発明の一実施形態を示す波長変換器配置設計装置の機能ブロック図である。
【図２】本発明の一実施形態を示す波長変換器配置設計方法のフローチャートである。
【図３】従来例を示す波長変換器配置設計装置の機能ブロック図である。
【図４】従来例を示す波長変換器配置設計方法のフローチャートである。
【図５】波長変換器の配置例を示す図である。
【符号の説明】
【００２９】
１      波長変換器配置設計装置
２      設計パラメータ入力部
３      波長変換器配置初期値入力部
４      ＲＷＡシミュレータ部
５      波長変換器再配置指標抽出部
６      波長変換器再配置部
７      波長変換器配置変動判定部
８      波長変換器配置出力部
【図１】
2006005693.tif 000003
【図２】
2006005693.tif 000004
【図３】
2006005693.tif 000005
【図４】
2006005693.tif 000006
【図５】
2006005693.tif 000007