(57)【要約】【課題】ネットワーク内に部分波長変換機能を有するルータが混在している場合でも最適な光パスの経路設計を行うことが可能な技術を提供する。【解決手段】各ノードで切替え可能な波長数を示す波長切替数と各ノードで変換可能な波長を示す波長群の情報をパラメータとして入力するステップと、各ノードで使用されている波長切替数が前記入力された波長切替数以下であり、同一波長かつ同一ノード間上で経路が重複していないことを示す制約条件を定式化するステップと、ソースとシンクとの間のコストを示す関数を目的関数として設定するステップと、前記波長群に含まれる波長を探索して波長変換時の波長の割り当てを行い、前記定式化された制約条件を満たすと共に前記設定された目的関数を最小化または最大化する解を求めて、ソースとシンクとの間の経路を決定するステップとを有するものである。【選択図】        図１
2004282281.tif 000002
【特許請求の範囲】
【請求項１】
光ネットワークの光パスの経路を設計する光パス設計方法において、
各ノードで切替え可能な波長数を示す波長切替数と各ノードで変換可能な波長を示す波長群の情報をパラメータとして入力するステップと、各ノードで使用されている波長切替数が前記入力された波長切替数以下であり、同一波長かつ同一ノード間上で経路が重複していないことを示す制約条件を定式化するステップと、ソースとシンクとの間のコストを示す関数を目的関数として設定するステップと、前記波長群に含まれる波長を探索して波長変換時の波長の割り当てを行い、前記定式化された制約条件を満たすと共に前記設定された目的関数を最小化または最大化する解を求めて、ソースとシンクとの間の経路を決定するステップとを有することを特徴とする光パス設計方法。
【請求項２】
その経路の各リンクで使用できる波長数の上限を満たす解候補を求めた後、前記波長群に含まれる波長の探索による波長変換時の波長の割り当てを前記解候補の経路に対して行い、その解候補の中から最終的な解を求めることを特徴とする請求項１に記載された光パス設計方法。
【請求項３】
前記経路の各リンクで使用できる波長数の上限を満たす解候補を求める際に、その目的関数に対する条件を緩和して前記解候補を求めることを特徴とする請求項１または請求項２のいずれかに記載された光パス設計方法。
【請求項４】
あるノードの前後に位置する２つのリンクに仮に割り当てられた変換波長の組み合わせが前記波長群に含まれていないものである場合に、一方のリンクの波長を他方のリンクの波長と同一の波長に変更する波長の割り当てと、一方のリンクの波長を前記波長群に含まれる波長の探索により得られた波長に変更する波長の割り当てとを行って、それぞれの場合について前記解を求めることを特徴とする請求項１乃至請求項３のいずれか１項に記載された光パス設計方法。
【請求項５】
光ネットワークの光パスの経路を設計する光パス設計装置において、
各ノードで切替え可能な波長数を示す波長切替数と各ノードで変換可能な波長を示す波長群の情報をパラメータとして入力するパラメータ入力処理部と、各ノードで使用されている波長切替数が前記入力された波長切替数以下であり、同一波長かつ同一ノード間上で経路が重複していないことを示す制約条件を定式化する定式化処理部と、ソースとシンクとの間のコストを示す関数を目的関数として設定する目的関数設定処理部と、前記波長群に含まれる波長を探索して波長変換時の波長の割り当てを行い、前記定式化された制約条件を満たすと共に、前記設定された目的関数を最小化または最大化する解を求めてソースとシンクとの間の経路を決定する経路決定処理部とを備えることを特徴とする光パス設計装置。
【請求項６】
前記経路決定処理部は、その経路の各リンクで使用できる波長数の上限を満たす解候補を求めた後、前記波長群に含まれる波長の探索による波長変換時の波長の割り当てを前記解候補の経路に対して行い、その解候補の中から最終的な解を求めるものであることを特徴とする請求項５に記載された光パス設計装置。
【請求項７】
前記経路決定処理部は、前記経路の各リンクで使用できる波長数の上限を満たす解候補を求める際に、その目的関数に対する条件を緩和して前記解候補を求めるものであることを特徴とする請求項５または請求項６のいずれかに記載された光パス設計装置。
【請求項８】
前記経路決定処理部は、あるノードの前後に位置する２つのリンクに仮に割り当てられた変換波長の組み合わせが前記波長群に含まれていないものである場合に、一方のリンクの波長を他方のリンクの波長と同一の波長に変更する波長の割り当てと、一方のリンクの波長を前記波長群に含まれる波長の探索により得られた波長に変更する波長の割り当てとを行って、それぞれの場合について前記解を求めるものであることを特徴とする請求項５乃至請求項７のいずれか１項に記載された光パス設計装置。
【請求項９】
光ネットワークの光パスの経路を設計する光パス設計装置としてコンピュータを機能させる為のプログラムにおいて、
各ノードで切替え可能な波長数を示す波長切替数と各ノードで変換可能な波長を示す波長群の情報をパラメータとして入力するパラメータ入力処理部と、各ノードで使用されている波長切替数が前記入力された波長切替数以下であり、同一波長かつ同一ノード間上で経路が重複していないことを示す制約条件を定式化する定式化処理部と、ソースとシンクとの間のコストを示す関数を目的関数として設定する目的関数設定処理部と、前記波長群に含まれる波長を探索して波長変換時の波長の割り当てを行い、前記定式化された制約条件を満たすと共に、前記設定された目的関数を最小化または最大化する解を求めてソースとシンクとの間の経路を決定する経路決定処理部としてコンピュータを機能させることを特徴とするプログラム。
【請求項１０】
前記経路決定処理部は、その経路の各リンクで使用できる波長数の上限を満たす解候補を求めた後、前記波長群に含まれる波長の探索による波長変換時の波長の割り当てを前記解候補の経路に対して行い、その解候補の中から最終的な解を求めるものであることを特徴とする請求項９に記載されたプログラム。
【請求項１１】
前記経路決定処理部は、前記経路の各リンクで使用できる波長数の上限を満たす解候補を求める際に、その目的関数に対する条件を緩和して前記解候補を求めるものであることを特徴とする請求項９または請求項１０のいずれかに記載されたプログラム。
【請求項１２】
前記経路決定処理部は、あるノードの前後に位置する２つのリンクに仮に割り当てられた変換波長の組み合わせが前記波長群に含まれていないものである場合に、一方のリンクの波長を他方のリンクの波長と同一の波長に変更する波長の割り当てと、一方のリンクの波長を前記波長群に含まれる波長の探索により得られた波長に変更する波長の割り当てとを行って、それぞれの場合について前記解を求めるものであることを特徴とする請求項９乃至請求項１１のいずれか１項に記載されたプログラム。
【請求項１３】
前記請求項９乃至１２のいずれかに記載されたプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は波長多重ネットワークにおけるネットワーク設計で活用できる光パス設計装置に関し、特に部分波長変換機能を具備するルータが混在している場合にも対応している光パス設計装置に適用して有効な技術に関するものである。
【０００２】
【従来の技術】
従来、ネットワークを構築する際には通信の行われる始点（ソース）のノードと終点（シンク）のノードについて、それらとそれらの間にある中継ノードとの間の帯域、遅延、パケット損失率等の品質や、トラヒック量をネットワーク情報として収集し、ノード間の各リンクでそれぞれのリンク容量（収容可能な最大パス本数）を満たす様に、通信で用いられる現用経路や故障シナリオを含む予備経路の設計を行っている。
【０００３】
この様にして設計されたネットワークで通信を行う際には、パケットの高速転送可能にするレイヤ３スイッチングの技術としてＭＰＬＳが多く用いられている。ＭＰＬＳではソースとシンクとの経路情報に対して「ラベル」と呼ばれる短い固定長の情報を割り当てておき、ＭＰＬＳ対応のスイッチやルータであるＬＳＲが最初のパケットを受信すると、そのパケットの送信経路に対応したラベルを付けて次のホップ先に転送する。この様にＭＰＬＳでは、ラベルの付加されたパケットを受信したルータがそのラベルを参照して次のホップ先へ転送するので、ＩＰアドレスを逐一参照した通常のルーティング処理よりも高速な転送処理を行うことができる。
【０００４】
また、ネットワークの高速化に伴って光ネットワークが用いられる様になってきているが、そのルーティングの際に光信号を電気信号に変換してルーティングを行うのはオーバーヘッドが大きい為、光ネットワーク上の信号をルーティングするための技術としてフォトニックＭＰＬＳを含むＧＭＰＬＳ（Ｇｅｎｅｒａｌｉｚｅｄ  ＭＰＬＳ）の仕様が検討されており、ＭＰＬＳのラベルの代わりに光信号の波長を割り当てて光信号のままルーティングを行うといった処理について検討が進められている。
【０００５】
なお、ＭＰＬＳネットワーク内に、ＩＰの経路制御プロトコル依存しない自由度の高いＭＰＬＳ経路を設定するＭＰＬＳ経路設定装置については、ＭＰＬＳ技術を用いてパケットを交換するＭＰＬＳネットワーク上にＭＰＬＳ経路を設定するＭＰＬＳ経路設定装置において、ＭＰＬＳネットワーク上の各ルータからネットワーク情報を収集するネットワーク、情報収集手段と、前記ネットワーク情報に基づいて、ＭＰＬＳネットワークのネットワーク構成を認識するネットワーク構成認識手段と、ＭＰＬＳ経路が満足すべき経路条件を設定する経路条件設定手段と、前記ネットワーク構成に基づいて、所定のルータ間で、前記経路条件を満足するＭＰＬＳ経路を探索するＭＰＬＳ網路探索手段と、前記探索されたＭＰＬＳ経路に応答したラベルを前記ＭＰＬＳネットワーク上の各ノードに配置してＭＰＬＳ経路を設定するＭＰＬＳ経路設定手段とを含むものが提案されている（例えば特許文献１参照）。
【０００６】
【特許文献１】
特開２００２−２２３２３５号公報
【０００７】
【発明が解決しようとする課題】
従来の技術では、ソースとシンクとの間の網路設計を行う際に、各リンクでそれぞれのリンク容量を満たしさえすれば良いという条件での経路設計を行っており、光信号の波長という概念の導入に対する効果的な経路設計法が確立されていない為、対象となるネットワークがフォトニックＭＰＬＳネットワークをはじめ、ＧＭＰＬＳと言われるネットワークへとなっていった場合に、光ネットワークを考慮した効果的な経路設計を行うことができないという問題がある。例えば、前記従来の技術では、ネットワーク全体で使用できる波長数に制約がある場合やネットワーク内に波長切替え機能を有するルータが混在している場合に、その波長数の制約を満たす経路設計や、波長切替え機能を利用して途中で波長を切り替える様な経路設計を行うことができないという問題がある。また、波長変換機能を有するルータの中には、変換できる波長に制限がある場合があり、この様に波長変換に制限がある部分波長変換機能を持つルータが混在する場合に従来の技術では経路設計を行うことができないという問題がある。
【０００８】
本発明の目的は上記問題を解決し、ネットワーク内に部分波長変換機能を有するルータが混在している場合でも、そのネットワークにおける最適な光パスの経路設計を行うことが可能な技術を提供することにある。
【０００９】
【課題を解決するための手段】
本発明は、光ネットワークの光パスの経路を設計する光パス設計装置において、ネットワーク内の各ノードで変換可能な波長を示す波長群の情報に応じて現用経路や予備経路の経路設計を行うものである。
【００１０】
本発明の光パス設計装置では、まず、求める経路設計が現用経路設計であるか或いは現用経路及び故障シナリオを含んだ予備経路の設計であるかの選択をユーザから受け付けて経路設計の種別を設定する。
【００１１】
次に前記設定した経路設計の種別に応じてパラメータを入力する。例えば現用経路設計の入力パラメータとしては、ネットワーク全体で使用できる波長数や、各ノードで切替え可能な波長数を示す波長切替数及び、各ノードで変換可能な波長を示す波長群の情報等を入力し、故障シナリオを含んだ予備経路設計も行う場合には、ある故障が発生した場合にどのノードが使用できなくなるか等を示す故障シナリオの情報も入力する。
【００１２】
次に前記入力したパラメータを基に変数を生成して入力パラメータの変数化を行った後、前記設定した経路設計の種別に応じて前記変数を用いた各種制約条件を定式化する。例えば、前記入力された波長数の範囲内で、各ノードで使用されている波長切替数が前記入力された波長切替数以下であることを示す制約条件を定式化する。
【００１３】
そしてソースとシンクとの間のパスのコストを示す関数を目的関数として設定した後、前記波長群の情報に含まれる波長を探索して各ノードにおける波長変換時の波長の割り当てを行う。例えば、ある第１のノードの前後に位置する２つのリンクに仮に割り当てられた変換波長の組み合わせλ１及びλ１１が、その第１のノードで変換可能な波長群λ１〜λ１０に含まれていないものである場合に、前記第１のノードと隣接する第２のノードで変換可能な波長群λ１０〜λ１９の中から前記第１のノードで変換可能な波長を探索し、一方のリンクの波長、例えばλ１１を前記探索により得られた波長、例えばλ１０に変更する波長の割り当てを行う。
【００１４】
そして、前記定式化された制約条件を満たすと共に、前記設定された目的関数を最大化または最小化する解を求めてソースとシンクとの間の経路を決定する。例えば、現用経路設計では現用パスの総コストを目的関数と定め、予備経路設計も行う場合では、現用パスの総コストに加え予備パスの数も目的関数に含めて目的関数を定めた後、その最小化を行う。
【００１５】
前記の様に本発明では、光ネットワークでの波長数の制約や波長切替え機能に関する入力パラメータからそれらの制約条件を生成し、部分波長変換機能を考慮して経路設計を行うので、フォトニックＭＰＬＳを含むＧＭＰＬＳネットワーク等における経路設計において、波長数の制約や波長変換機能のあるルータを利用したネットワークならではの特性を考慮した経路設計が必要となった場合に、それらを考慮した光パスの経路設計を行うことが可能であり、また、この考え方は次世代高速ネットワークの中核技術として採用されているＷＤＭ（波長分割多重）網の設計法にも適用することができる。
【００１６】
以上の様に本発明の光パス設計装置によれば、ネットワーク内の各ノードで変換可能な波長を示す波長群の情報に応じて現用経路や予備経路の経路設計を行うので、ネットワーク内に部分波長変換機能を有するルータが混在している場合でも、そのネットワークにおける最適な光パスの経路設計を行うことが可能である。
【００１７】
【発明の実施の形態】
以下に部分波長変換機能を有するノードを含む光ネットワークでの光パスの経路を設計する一実施形態の光パス設計装置について説明する。
【００１８】
図１は本実施形態の光パス設計装置の概略構成とネットワーク設計の処理手順を示すフローチャートである。図１に示す様に本実施形態の光パス設計装置１００は、ＣＰＵ１０１と、メモリ１０２と、磁気ディスク装置１０３と、入力装置１０４と、出力装置１０５と、ＣＤ−ＲＯＭ装置１０６と、通信装置１０７と、制約条件テーブル１０８とを有している。
【００１９】
ＣＰＵ１０１は、光パス設計装置１００全体の動作を制御する装置である。メモリ１０２は、光パス設計装置１００全体の動作を制御する際にその為の各種処理プログラムやデータをロードする記憶装置である。
【００２０】
磁気ディスク装置１０３は、前記各種処理プログラムやデータを格納しておく記憶装置である。入力装置１０４は、経路設計の種別やパラメータを入力する為の各種入力を行う装置である。出力装置１０５は、経路設計の種別やパラメータの入力支援を行う為の出力、決定された経路の表示等、光パスの経路設計に伴う各種出力を行う装置である。
【００２１】
ＣＤ−ＲＯＭ装置１０６は、前記各種処理プログラムを記録したＣＤ−ＲＯＭの内容を読み出す装置である。通信装置１０７は、ネットワークを介して他の処理装置との通信を行う装置である。制約条件テーブル１０８は、波長数制限、波長切替機能、予備経路設計の有無に応じた各場合について、その入力パラメータの表記法、各場合の制約条件の式中で用いられる変数の定義内容、各場合の制約条件の式及び目的関数を示す情報を格納したテーブルである。
【００２２】
また光パス設計装置１００は、経路設計選択処理部１１１と、パラメータ入力処理部１１２と、変数化処理部１１３と、定式化処理部１１４と、目的関数設定処理部１１５と、解法選択処理部１１６と、解法オプション選択処理部１１７と、経路決定処理部１１８とを有している。
【００２３】
経路設計選択処理部１１１は、求める経路設計が、現用経路設計であるか或いは現用経路及び故障シナリオを含んだ予備経路の設計であるかの選択をユーザから受け付けて経路設計の種別を設定する処理部である。
【００２４】
パラメータ入力処理部１１２は、ネットワーク全体で使用できる波長数や、各ノードで切替え可能な波長数を示す波長切替数、各ノードで変換可能な波長を示す波長群の情報、ある故障がどの様に発生するかを示す故障シナリオ等の情報をパラメータとして入力する処理部である。
【００２５】
変数化処理部１１３は、前記入力されたパラメータを基に変数を生成して入力パラメータの変数化を行う処理部である。定式化処理部１１４は、前記入力された波長数の範囲内で、同一波長かつ同一ノード間上で経路が重複していないことを示す制約条件や、各ノードで使用されている波長切替数が前記入力された波長切替数以下であり、同一波長かつ同一ノード間上で経路が重複していないことを示す制約条件、前記入力された故障シナリオの影響で予備パスを使用した場合の各ノードで使用されている波長切替数が前記入力された波長切替数以下となることを含む制約条件等を前記生成した変数を用いて定式化する処理部である。
【００２６】
目的関数設定処理部１１５は、ソースとシンクとの間のパスのコストを示す関数や、必要予備パスの重みを示す関数を目的関数として設定する処理部である。解法選択処理部１１６は、前記経路設計を整数計画問題として解く際の解法として、厳密解法で解くか或いは近似解法で解くかの選択をユーザから受け付けて解法の種別を設定する処理部である。
【００２７】
解法オプション選択処理部１１７は、前記経路設計を整数計画問題として解く際の解法のオプションとして、制約条件を満たす解の中で最小波長数を求める等の各種オプションの選択をユーザから受け付けて設定する処理部である。
【００２８】
経路決定処理部１１８は、前記制約条件、目的関数、解法、解法オプションを受け付け、前記波長群に含まれる波長を探索して波長変換時の波長の割り当てを行い、整数計画問題を解いて、前記定式化された制約条件を満たすと共に前記設定された目的関数を最大化または最小化する解を求めることにより、ソースとシンクとの間の経路を決定する処理部である。
【００２９】
光パス設計装置１００を経路設計選択処理部１１１、パラメータ入力処理部１１２、変数化処理部１１３、定式化処理部１１４、目的関数設定処理部１１５、解法選択処理部１１６、解法オプション選択処理部１１７及び経路決定処理部１１８として機能させる為のプログラムは、ＣＤ−ＲＯＭ等の記録媒体に記録され磁気ディスク等に格納された後、メモリにロードされて実行されるものとする。なお前記プログラムを記録する記録媒体はＣＤ−ＲＯＭ以外の他の記録媒体でも良い。また前記プログラムを当該記録媒体から情報処理装置にインストールして使用しても良いし、ネットワークを通じて当該記録媒体にアクセスして前記プログラムを使用するものとしても良い。
【００３０】
図１に示す様に光パス設計装置１００で経路設計処理が開始されると、ステップ１２１で経路設計選択処理部１１１は、求める経路設計が、現用経路設計であるか或いは現用経路及び故障シナリオを含んだ予備経路の設計であるかの選択をユーザから受け付けて経路設計の種別を設定する処理を行う。
【００３１】
次にステップ１２２でパラメータ入力処理部１１２は、ネットワーク全体で使用できる波長数や、各ノードで切替え可能な波長数を示す波長切替数、各ノードで変換可能な波長を示す波長群の情報、ある故障がどの様に発生するかを示す故障シナリオ等の情報をパラメータとして入力した後、その入力したパラメータの値を予め定められた表記の変数へ代入する処理を行う。
【００３２】
図２は本実施形態の必要パラメータの例を示す図である。図２に示す様に本実施形態では、波長の情報として、ネットワーク全体で使用できる波長数や、各ノードで変換可能な波長を示す波長群の情報を入力し、その他、ルータ、リンク、パス、確定パス及び故障シナリオに関する情報の入力を行う。
【００３３】
本実施形態において、ノードは、ネットワークをグラフで表した場合のグラフ上の頂点を示すものとし、例えばルータを表しているものとする。節点によっては、波長を切替えることが可能であり、部分波長変換機能を持つ節点では波長群で示された波長での変換を行うものとする。
【００３４】
また本実施形態において、辺またはリンクはルータ間のファイバを表すものとし、２ルータ間に複数のファイバがある場合は多重辺となる。辺容量は１つのファイバに収容できる異なる波長の上限数を示し、ペアはパスの両端に位置する節点の対、パスはペアを構成する両端の節点を結ぶ通信経路、故障シナリオは節点や辺が故障すると仮定したシナリオ、現用経路は実際に用いられるパス、予備経路は故障時に現用経路の代わりに用いられるパスを表し、波長切替上限数を全ての節点で「０」とした場合を強い制約と呼び、「０」以外を認める場合を弱い制約と呼ぶものとする。
【００３５】
また厳密解法とは、最適解を求める解法であり、解となる可能性のある全ての組み合わせの中から最適解を求める為、非常に時間のかかる解法であり、近似解法とは、準最適解を求める解法で、限られた範囲を探索するので処理が速い解法である。
【００３６】
次にステップ１２３で光パス設計装置１００の変数化処理部１１３は、前記入力されたパラメータを基に変数を生成して入力パラメータの変数化を行う。
そしてステップ１２４で定式化処理部１１４は、前記入力された波長数の範囲内で、同一波長かつ同一ノード間上で経路が重複していないことを示す制約条件や、各ノードで使用されている波長切替数が前記入力された波長切替数以下であり、同一波長かつ同一ノード間上で経路が重複していないことを示す制約条件、前記入力された故障シナリオの影響で予備パスを使用した場合の各ノードで使用されている波長切替数が前記入力された波長切替数以下となることを含む制約条件等を定式化する処理を行う。この様な定式化により、以後、この経路設計をグラフの問題（整数計画問題）として扱うことができる。
【００３７】
次にステップ１２５で目的関数設定処理部１１５は、ソースとシンクとの間のパスのコストを示す関数や、必要予備パスの重みを示す関数を目的関数として設定する処理を行う。この様に本実施形態では、経路を決定する為の目的関数を決め、目的に即した最適値を見つける。ここでいう最適値とは、例えば目的関数の最大化や最小化、またはそれに準ずる操作により、ある指標において最適となる値を指すものとする。一例としては、現用経路設計では、パスの総コストを目的関数と定め、その関数を最小化することで最適値を求める。また予備経路設計では、パスの総コストに加え予備パスの数も目的関数に含め、その関数を最小化することで最適値を求める。
【００３８】
次にステップ１２６で解法選択処理部１１６は、前記経路設計を整数計画問題として解く際の解法として、厳密解法で解くか或いは近似解法で解くかの選択をユーザから受け付けて解法の種別を設定する処理を行う。整数計画問題を解く際に、厳密解法では全空間を調べるのに対して、近似解法では解空間を限定してその空間における最適解（準最適解と呼ぶ）を見つける。解空間の絞り方の一例としては、始点・終点となるルータの最短経路を見つけ、解空間を「最短経路＋α」として解空間の大きさを調整する方法がある。
【００３９】
そしてステップ１２７で解法オプション選択処理部１１７は、前記経路設計を整数計画問題として解く際の解法のオプションとして、制約条件を満たす解の中で最小波長数を求める等のオプションの選択をユーザから受け付けて設定する処理を行う。
【００４０】
図３は本実施形態の解法オプションの例を示す図である。図３に示す様に本実施形態では、ステップ１２６で厳密解法が選択され、ステップ１２７でオプションの選択が無い場合には引数として「−ｃ」を指定し、ステップ１２７で最小波長数を求めるオプションが選択された場合には引数の「−ｃｍ」の後に探索する最小波長数の下限の指定を行う。
【００４１】
またステップ１２６で近似解法が選択され、ステップ１２７でオプションの選択が無い場合には引数の指定無しとし、その他、最小波長数を求める場合や、繰り返し回数の指定を行う場合、そして実行可能解が得られたらすぐに終了する場合等のオプションが選択された場合には、図３の様な「−ｍ」「−ｉ」「−ｆ」等の引数の指定を行う。
【００４２】
本実施形態では、前記の様に解法として厳密解法と近似解法を選択できるものとするが、厳密解法では変数や制約条件式の増大に伴って計算時間が指数関数的に激増する為、現実的な時間での解の出力が困難となる場合がある。このとき、近似解法を選択すれば、解空間を限定した中での準最適解を出力することができる。
【００４３】
前記の様にして解法やオプションの設定が行われた後、光パス設計装置１００の経路決定処理部１１８は、前記制約条件、目的関数、解法、解法オプションを受け付け、前記波長群に含まれる波長を探索して波長変換時の波長の割り当てを行って、整数計画問題を解く処理を実行し、前記定式化された制約条件を満たすと共に前記設定された目的関数を最小化または最大化する解を求めることにより、ソースとシンクとの間の経路を決定する処理を行う。なお整数計画問題を解く際の処理手順については市販のソフトウェア等、公知技術と同様の処理によるものとする。また図３の「ＣａｌｃＭＰＬＳ．ｅｘｅ」は、本実施形態の経路設計選択処理部１１１〜経路決定処理部１１８としてコンピュータを機能させるプログラムを表しており、図３の「最適経路探索」は、経路決定処理部１１８内の整数計画問題を解く処理部分により行われる処理であるものとする。
【００４４】
以下に、本実施形態の光パス設計装置１００において、ネットワーク全体で使用可能な波長数に制約があり、ネットワーク内に波長変換機能を有しているルータを含む場合の前記ステップ１２２〜ステップ１２５の具体例について図４〜図８を参照して説明する。
【００４５】
図４は本実施形態の波長数制限がありノードの波長切替えを有している場合の入力パラメータの表記法の例を示す図である。本実施形態の光パス設計装置１００において経路設計を行う際に、ステップ１２２でパラメータ入力処理部１１２は、節点、ソース及びシンク、波長数、辺容量、距離、コスト等の、波長数の情報を含むネットワーク情報や、各ノードで変換可能な波長を示す波長群の情報をパラメータとして入力した後、その入力したネットワーク情報の値を図４の様に予め定められた表記の変数へ代入する処理や、波長群の情報をメモリ１０２内の所定の領域に格納しておく処理を行う。
【００４６】
図４に示す様に本実施形態の光パス設計装置１００では、節点であるルータをＶで表し、総ルータ数をｎν、総辺数である総ファイバ数をｎａで表している。またソースとシンクをそれぞれｓとｔで示し、ｓとｔのペアでパスＰを、また総パス数をｎｐで示しており、予備パスが必要であるかどうかをＱｋで示している。
【００４７】
さらにネットワーク全体で使用可能な波長数をｎｗ、節点や辺が故障すると仮定したシナリオの数をｎｓ、ｉ及びｊで識別されるノード間の辺容量であるファイバ容量をｆｉｊ、コストをＣｉｊ、距離をｄｉｊで表し、各ルータでの波長切替回数の上限をｐｉ、ある故障シナリオｈに対してｉｊ間のファイバの利用が実行可能であるかをＦｈｉｊで表している。
【００４８】
図５は本実施形態の波長数制限がありノードの波長切替えを有している場合の変数化の例を示す図である。図５に示す様にステップ１２３で光パス設計装置１００の変数化処理部１１３は、前記入力されたパラメータを基に変数を生成して入力パラメータの変数化を行う。
【００４９】
すなわち、図４の様に入力パラメータとしてネットワーク全体で使用できる波長数ｎｗと、ノードの波長切替回数の上限ｐｉが入力されている場合には、波長数制限がありノードの波長切替えを有している場合に用いられる変数の定義を制約条件テーブル１０８から読み出し、節点νｉとνｊとの間に波長ｌのパスｋがあるかどうかを示すファイバマトリクスｘ（添字数が４の場合）、予備パスのファイバマトリクスｙ、予備パスが必要であるかどうかを示すマトリクスｚ、前記ｘ、ｙ、ｚを用いるｗの各変数の定義内容を図５の様に出力する。またパスｋがファイバｉｊを通るかどうかを示すファイバマトリクスｘ（添字数が３の場合）や、パスｋがルータｉを通るかどうかを示すファイバマトリクスｘ（添字数が２の場合）、シナリオｈにおけるルータｉでの波長切替数を示すマトリクスｕの各変数の定義内容を図５の様に出力する。
【００５０】
図６は本実施形態の波長数制限がありノードの波長切替えを有している場合の定式化における制約条件の例を示す図である。図７は本実施形態の図６の続きを示す図である。図６及び図７に示す様にステップ１２４で定式化処理部１１４は、波長数制限がありノードの波長切替えを有している場合に用いられる制約条件の式を制約条件テーブル１０８から読み出し、前記生成した変数を用いて定式化された制約条件の式を出力する処理を行う。
【００５１】
例えば図６及び図７では、各ルータにおける入出力の釣合がとれ、なおかつ、全てのパスが存在すること、全てのファイバがファイバ容量を満たすこと、同一パスかつ同一ファイバ上でパスが重複していないこと、同一波長かつ同一ファイバ上でパスが重複していないこと、各パスの長さが設定値Ｄ以下となること、各ルータの波長切替回数がｐｉ以下となること、予備パスが必要であること、予備パスが故障ファイバを通らないことを示す制約条件を出力している。
【００５２】
図８は本実施形態の波長数制限がありノードの波長切替えを有している場合の定式化における目的関数の例を示す図である。図８に示す様にステップ１２５で目的関数設定処理部１１５は、ソースとシンクとの間のパスのコストを示す関数を目的関数として出力する処理を行う。
【００５３】
例えば図８では、現用パス及び予備パスの各ファイバ毎にかかるコスト、予備パスの本数に相当するコスト、波長切替回数に相当するコストの総和を最小化することを示す目的関数を出力している。
【００５４】
以下に、本実施形態の光パス設計装置１００において、ネットワーク内に部分波長変換機能を有するノードが含まれている場合の経路決定処理部１１８での近似解法による処理内容について説明する。
【００５５】
図９は本実施形態の経路決定処理部１１８での近似解法の流れを示す図である。図９に示す様に光パス設計装置１００の経路決定処理部１１８は、そのパスのファイバ容量を満たす解候補を求め、各ノードで変換可能な波長群に応じて波長の割り当てを行った後、各ノードでの波長変換数がその上限数を超えないパスを求める処理を行う。
【００５６】
まずステップ９０１で経路決定処理部１１８は、全故障シナリオについて、それぞれ全てのペアに対してパスが存在することを前提条件とし、ソースｓ及びシンクｔの各ペアのパスをパス候補の中からランダムに選択して初期解を設定した後、数１の目的関数を設定して整数計画問題の処理部へ入力し、数１の目的関数が最小となる解候補を求める。その際、あるファイバでファイバ容量を越えている場合には、ただ１つのリンクだけを変更する等の条件により近傍のパスを探索する処理を行うものとする。
【００５７】
【数１】
2004282281.tif 000003
【００５８】
数１の本数はそのファイバを通過するパスの数を表すものとする。また、仮予備パス数とは、乱数等で決定される変数の値を予備パス数から引いた値であり、αは、予備パスに対して現用パスの重み付けを行う為の係数で、ここではα＝１０００としている。
【００５９】
次にステップ９０２で経路決定処理部１１８は、前記求められた解候補の各ペアのパスに対する仮の波長として、そのパスに波長をランダムに割り当てた後、その仮に割り当てた波長をパスに従って順に読み出すことにより、ノードの前後のリンクにおいて波長の異なるものを検索して、各ノードの前後に位置する２つのリンクに割り当てられた変換波長の組み合わせを読み出す。
【００６０】
ステップ９０３では、前記読み出した変換波長の組み合わせと、ステップ１２２でパラメータ入力処理部１１２によってメモリ１０２に格納しておいた当該ノードの波長群の情報とを比較して、前記変換波長の組み合わせがそのノードの波長群の情報に含まれているかどうかを調べ、当該変換波長の組み合わせがそのノードの波長群の情報に含まれていない場合には、その組み合わせの波長変換が当該ノードで許されていないものと判定してステップ９０４へ進む。
【００６１】
ステップ９０４では、当該ノードの前方または後方に位置するリンクの波長を他方のリンクの波長と同一の波長に変更する波長の割り当てを行い、当該ノードにおける波長変換を伴わないパスを生成する。
【００６２】
ステップ９０５では、当該ノードの前方または後方に位置する次ノードの波長群の情報をメモリ１０２から読み出し、当該ノードの波長群の情報と次ノードの波長群の情報とを比較して、両方のノードの波長群の情報に含まれている波長を探索し、当該ノードと次ノードとの間のリンクの波長を前記探索により得られた波長に変更する波長の割り当てを行って、当該ノードで変換可能な波長の割り当てられたパスを生成する。
【００６３】
次にステップ９０６で経路決定処理部１１８は、全故障シナリオについて、それぞれ予備パスを含めた全ファイバで波長の重なりがないことを前提条件とし、前記波長の割り当ての行われたパスを初期解とし、数２の目的関数を設定して整数計画問題の処理部へ入力し、数２の目的関数が「０」となる解を求める。その際、あるルータに関して波長切替数の上限を越えている時は、そのルータに接続しているファイバから、そのパスの始ルータ、終ルータ、波長切替ルータのいずれかの最も近いルータまでのファイバの波長を反対側のファイバの波長に変更する等の条件により近傍のパスを探索する処理を行うものとする。
【００６４】
【数２】
2004282281.tif 000004
【００６５】
そして、ステップ９０６で求められた解を初期解とし、定式化処理部１１４で設定された図６及び図７の制約条件を満たすと共に目的関数設定処理部１１５で設定された図８の目的関数が最小となるパスを求めて最終的な近似解とする。ここで「予備パス有り」または「予備パス無し」共に最終的な目的関数は図８に示したものであり、「予備パス無し」の場合の最終的な目的関数の第２項「予備パスのコスト」及び第３項「予備パス本数」は「０」となる。
【００６６】
前記のステップ９０１の時点で解候補を厳密に求めた場合、ステップ９０５の時点での解探索の幅が狭くなってしまう為、本実施形態ではステップ９０１の目的関数に対する条件を緩和し、ステップ９０５における解探索の幅を広くしている。すなわち、この条件の緩和の為にステップ９０１では乱数を導入しており、具体的には、実際の予備パス数をその乱数に相当する値だけ減じることにより、そのコストを無視するものとしている。例えば予備パス数が「４」である場合にそこから「１」減じた「３」を仮予備パス数とすることにより、予備パス数「４」の場合と予備パス数「３」の場合が同様に探索されることとなる為、解探索の幅を広くすることができる。また、その上で得られた解については、条件を緩和しない目的関数に基づいて最終的な近似解を導いている。
【００６７】
図１０は本実施形態の波長変換を伴わない割り当てへの変更の例を示す図である。図１０ではステップ９０４での割り当て変更例を表しており、印「●」は波長が切替わっているルータ、印「○」は波長が切替わっていないルータを示し、左から順番にルータ番号０、１…５であるものとする。また全ルータで波長切替数の上限は「０」であるものとし、始ルータ番号は０、終ルータ番号は５であるものとする。
【００６８】
図１０の状態１では、ルータ番号２、３で波長が切替わっている（このときの目的関数の値は２）。印「●」のルータで波長の切替わらない様に、印「●」のルータの片側をもう一方と同じ波長に変更する。ここでは、ルータ番号２で波長が切替わらない様にする。ルータ番号２の右側から波長が切替わっているルータ（ルータ番号３）までの波長を、ルータ番号２の左側から始ルータ（ルータ番号０）までの波長と同一の波長にしている（状態２）
状態２では、ルータ番号３で波長が切替わっている（このときの目的関数の値は１）。前回と同様の作業を行い、ここでは、ルータ番号３で波長が切替わらない様に、ルータ番号３の左側から始ルータまでの波長を、右側から終ルータまでの波長を同一の波長にしている（状態３）
状態３では、全てのルータで波長切替が無い状態となっている（目的関数の値は０）。
【００６９】
図１１は本実施形態の変換可能な波長への割り当ての変更例を示す図である。図１１において、ルータ１１０１で変換可能な波長群の波長番号は１〜１０、ルータ１１０２で変換可能な波長群の波長番号は１０〜１９であるものとすると、ルータ１１０１では、波長番号１から波長番号１１への波長の変換は許されない。
【００７０】
この様な場合、ノード１１０１の次ノード１１０２の波長群の情報をメモリ１０２から読み出し、ノード１１０１の波長群の情報である波長番号１〜１０と次ノード１１０２の波長群の情報である波長番号１０〜１９とを比較して、両方のノードの波長群の情報に含まれている波長番号１０を探索し、ノード１１０１と次ノード１１０２との間のリンクの波長番号１１を前記探索により得られた波長番号１０に変更する波長の割り当てを行って、ノード１１０１で変換可能な波長の割り当てられたパスを生成する。
【００７１】
以上説明した様に本実施形態の光パス設計装置によれば、ネットワーク内の各ノードで変換可能な波長を示す波長群の情報に応じて現用経路や予備経路の経路設計を行うので、ネットワーク内に部分波長変換機能を有するルータが混在している場合でも、そのネットワークにおける最適な光パスの経路設計を行うことが可能である。
【００７２】
【発明の効果】
本発明によればネットワーク内の各ノードで変換可能な波長を示す波長群の情報に応じて現用経路や予備経路の経路設計を行うので、ネットワーク内に部分波長変換機能を有するルータが混在している場合でも、そのネットワークにおける最適な光パスの経路設計を行うことが可能である。
【図面の簡単な説明】
【図１】本実施形態の光パス設計装置の概略構成とネットワーク設計の処理手順を示すフローチャートである。
【図２】本実施形態の必要パラメータの例を示す図である。
【図３】本実施形態の解法オプションの例を示す図である。
【図４】本実施形態の波長数制限がありノードの波長切替えを有している場合の入力パラメータの表記法の例を示す図である。
【図５】本実施形態の波長数制限がありノードの波長切替えを有している場合の変数化の例を示す図である。
【図６】本実施形態の波長数制限がありノードの波長切替えを有している場合の定式化における制約条件の例を示す図である。
【図７】本実施形態の図６の続きを示す図である。
【図８】本実施形態の波長数制限がありノードの波長切替えを有している場合の定式化における目的関数の例を示す図である。
【図９】本実施形態の経路決定処理部１１８での近似解法の流れを示す図である。
【図１０】本実施形態の波長変換を伴わない割り当てへの変更の例を示す図である。
【図１１】本実施形態の変換可能な波長への割り当ての変更例を示す図である。
【符号の説明】
１００…光パス設計装置、１０１…ＣＰＵ、１０２…メモリ、１０３…磁気ディスク装置、１０４…入力装置、１０５…出力装置、１０６…ＣＤ−ＲＯＭ装置、１０７…通信装置、１０８…制約条件テーブル、１１１…経路設計選択処理部、１１２…パラメータ入力処理部、１１３…変数化処理部、１１４…定式化処理部、１１５…目的関数設定処理部、１１６…解法選択処理部、１１７…解法オプション選択処理部、１１８…経路決定処理部。
【図１】
2004282281.tif 000005
【図２】
2004282281.tif 000006
【図３】
2004282281.tif 000007
【図４】
2004282281.tif 000008
【図５】
2004282281.tif 000009
【図６】
2004282281.tif 000010
【図７】
2004282281.tif 000011
【図８】
2004282281.tif 000012
【図９】
2004282281.tif 000013
【図１０】
2004282281.tif 000014
【図１１】
2004282281.tif 000015