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