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