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