(57)【要約】【課題】  ネットワーク事業者が提供するネットワークサービスの品質を保証できる帯域でのパス設計を効率的に行う。【解決手段】  光ＶＰＮパス設定装置１０において、記憶処理部１８により、光ネットワークにおける波長、コスト、距離などの制約条件として、さらに、リンク帯域および要求帯域を新たに制約条件として追加し、光パスの設計を整数計画問題として定式化し、データ処理部１７において、その初期解を求め、その初期解に基づき、許容解空間から局所最適解を求め、さらに、その中から準最適解を求める構成とする。【選択図】        図１
2005260729.tif 000002
【特許請求の範囲】
【請求項１】
光ネットワークのパス設計における制約条件としての波長、リンクコスト、リンク距離等が定式化された制約条件情報を入力して記憶装置に記憶する記憶処理手段と、
記憶装置から上記制約条件情報を読み出して、各定式に対する近似解法により初期解を求め、求めた初期解に基づき許容解空間から局所最適解を求め、求めた局所最適解から準最適解を求めるデータ処理手段とを有し、プログラムに基づくコンピュータ処理を実行して、上記光ネットワークにおける光パスの設定を行うシステムであって、
上記記憶処理手段は、上記定式化された制約条件情報として、リンク帯域と要求帯域を新たに入力して上記記憶装置に記憶する機能を有し、
上記データ処理手段は、上記リンク帯域と上記要求帯域を含む上記制約条件情報を読み出して、上記初期解と上記局所最適解および上記準最適解を求める機能を有し、
要求帯域を保証する光ＶＰＮパスの設定を行うことを特徴とする帯域保証型光ＶＰＮパス設計システム。
【請求項２】
請求項１に記載の帯域保証型光ＶＰＮパス設計システムであって、
上記データ処理手段は、
ダイクストラム法によって各光パスの最短路である初期解を求める機能と、
求めた初期解で上記制約条件情報を満たさない初期解としてのリンクを抽出する機能と、
抽出したリンクを通過するパスを別のリンクを通過するように迂回させて、上記制約条件情報を全て満たす局所最適解を求める機能と
を有することを特徴とする帯域保証型光ＶＰＮパス設計システム。
【請求項３】
請求項１もしくは請求項２のいずれかに記載の帯域保証型光ＶＰＮパス設計システムであって、
上記制約条件情報として、以下のルータ番号ｉ，ｊ、パス番号ｋ、波長番号ｌ、ソースとしてのルータ番号ｓｋ、シンクとしてのルータ番号ｔｋ、波長の本数ｎｗ、ルータの総数ｎｖ、パス数ｎｐからなる定式を含むことを特徴とする帯域保証型光ＶＰＮパス設計方法。
（１）ソースとしてのルータにおける入力ｖｉｎと出力ｖｏｕｔの釣合がとれ、なおかつ、全てのパスが存在することを示す第１の制約条件式としての数１
【数１】
2005260729.tif 000021
（２）シンクとしてのルータにおける入力ｖｉｎと出力ｖｏｕｔの釣合がとれ、なおかつ、全てのパスが存在することを示す第２の制約条件式としての数２
【数２】
2005260729.tif 000022
（３）ソース、シンク以外としてのルータにおける入力ｖｉｎと出力ｖｏｕｔの釣合がとれ、なおかつ、全てのパスが存在することを示す第３の制約条件式としての数３
【数３】
2005260729.tif 000023
（４）同一パスかつ同一リンク上で波長が重複していないことを示す第４の制約条件式としての数４
【数４】
2005260729.tif 000024
（５）同一波長かつ同一リンク上でパスが重複していない制約条件を示す第５の制約条件式としての数５
【数５】
2005260729.tif 000025
（６）全てのリンク帯域Ｂｋがリンク容量ｆｉｊを満たすことを示す第５の制約条件式としての数６
【数６】
2005260729.tif 000026
（７）各パスの長さｄｉｊが設定値Ｄ以下となることを示す第６の制約条件式としての数７
【数７】
2005260729.tif 000027
【請求項４】
請求項１から請求項３のいずれかに記載の帯域保証型光ＶＰＮパス設計システムであって、
上記準最適解を求める際に用いる目的関数として、リンクコストＣｉｊを含む下記数８を用い、上記局所最適解の内、リンクコストＣｉｊが最小となるものを上記準最適解とすることを特徴とする帯域保証型光ＶＰＮパス設計システム。
【数８】
2005260729.tif 000028
【請求項５】
プログラムに基づくコンピュータ処理により、光ネットワークのパス設計における制約条件としての波長、リンクコスト、リンク距離等が定式化された制約条件情報を入力して記憶装置に記憶し、
記憶装置から上記制約条件情報を読み出して、各定式に対する近似解法により初期解を求め、求めた初期解に基づき許容解空間から局所最適解を求め、求めた局所最適解から準最適解を求め、上記光ネットワークにおける光パスの設定を行う方法であって、
コンピュータが実行する処理として、
上記定式化された制約条件情報にリンク帯域と要求帯域を新たに付加して入力し上記記憶装置に記憶する第１のステップと、
記憶装置から上記リンク帯域と上記要求帯域を含む上記制約条件情報を読み出して、上記初期解と上記局所最適解および上記準最適解を求める第２のステップとを有し、
要求帯域を保証する光ＶＰＮパスの設定を行うことを特徴とする帯域保証型光ＶＰＮパス設計方法。
【請求項６】
請求項５に記載の帯域保証型光ＶＰＮパス設計方法であって、
上記第１のステップでは、
ダイクストラム法によって各光パスの最短路である初期解を求めるステップと、
求めた初期解で上記制約条件情報を満たさない初期解としてのリンクを抽出するステップと、
抽出したリンクを通過するパスを別のリンクを通過するように迂回させて、上記制約条件情報を全て満たす局所最適解を求めるステップと
を有することを特徴とする帯域保証型光ＶＰＮパス設計方法。
【請求項７】
請求項５もしくは請求項６のいずれかに記載の帯域保証型光ＶＰＮパス設計方法であって、
上記制約条件情報として、以下のルータ番号ｉ，ｊ、パス番号ｋ、波長番号ｌ、ソースとしてのルータ番号ｓｋ、シンクとしてのルータ番号ｔｋ、波長の本数ｎｗ、ルータの総数ｎｖ、パス数ｎｐからなる定式を含むことを特徴とする帯域保証型光ＶＰＮパス設計方法。
（１）ソースとしてのルータにおける入力ｖｉｎと出力ｖｏｕｔの釣合がとれ、なおかつ、全てのパスが存在することを示す第１の制約条件式としての数９
【数９】
2005260729.tif 000029
（２）シンクとしてのルータにおける入力ｖｉｎと出力ｖｏｕｔの釣合がとれ、なおかつ、全てのパスが存在することを示す第２の制約条件式としての数１０
【数１０】
2005260729.tif 000030
（３）ソース、シンク以外としてのルータにおける入力ｖｉｎと出力ｖｏｕｔの釣合がとれ、なおかつ、全てのパスが存在することを示す第３の制約条件式としての数１１
【数１１】
2005260729.tif 000031
（４）同一パスかつ同一リンク上で波長が重複していないことを示す第４の制約条件式としての数１２
【数１２】
2005260729.tif 000032
（５）同一波長かつ同一リンク上でパスが重複していない制約条件を示す第５の制約条件式としての数１３
【数１３】
2005260729.tif 000033
（６）全てのリンク帯域Ｂｋがリンク容量ｆｉｊを満たすことを示す第５の制約条件式としての数１４
【数１４】
2005260729.tif 000034
（７）各パスの長さｄｉｊが設定値Ｄ以下となることを示す第６の制約条件式としての数１５
【数１５】
2005260729.tif 000035
【請求項８】
請求項５から請求項７のいずれかに記載の帯域保証型光ＶＰＮパス設計方法であって、
上記準最適解を求める際に用いる目的関数として下記数１６を用い、上記局所最適解の内、リンクコストＣｉｊが最小となるものを上記準最適解とすることを特徴とする帯域保証型光ＶＰＮパス設計方法。
【数１６】
2005260729.tif 000036
【請求項９】
コンピュータに、請求項５から請求項８のいずれかに記載の帯域保証型光ＶＰＮパス設計方法における各ステップでの処理を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、波長をラベルとした光ネットワークにおいて、効率よく光ＶＰＮ（ｖｉｒｔｕａｌ  Ｐｒｉｖａｔｅ  Ｎｅｔｗｏｒｋ）パスを設定するための技術に係わり、特に、光ネットワークにおける帯域保証型のＶＰＮサービスを提供する場合において、通信事業者が効率的にＶＰＮパスを設定するのに好適な技術に関するものである。
【背景技術】
【０００２】
現在、ネットワークの高速化に伴って光ネットワークが用いられる様になってきているが、そのルーティングの際に光信号を電気信号に変換してルーティングを行うのはオーバーヘッドが大きい為、光ネットワーク上の信号をルーティングするための技術として光ＭＰＬＳ（Ｏｐｔｉｃａｌ  Ｍｕｌｔｉ  Ｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ）を含むＧＭＰＬＳ（Ｇｅｎｅｒａｌｉｚｅｄ  ＭＰＬＳ）の仕様が検討されており、ＭＰＬＳのラベルの代わりに光信号の波長を割り当てて光信号のままルーティングを行うといった処理について検討が進められている。通常の電気式のルータではルーティング（パス選択）情報として、ヘッダを利用するが、ＭＰＬＳルータでは、「ラベル」と呼ばれる短い固定長の識別標識を利用する。光ネットワークにおいては、このラベルに波長（λ）が用いられている。
【０００３】
以下、光ＭＰＬＳ（フォトニックＭＰＬＳ）ネットワークの設計技術、および、光ＭＰＬＳネットワークにおけるパス（ＯＬＳＰ：Ｏｐｔｉｃａｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｅｄ  Ｐａｔｈ）設計技術について、非特許文献１の記載内容を用いて説明する。対象とするネットワークは波長多重（ＷＤＭ：Ｗａｖｅｌｅｎｇｔｈ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘｉｎｇ）をベースとする。
【０００４】
上述したように、光ＭＰＬＳなどを含むＧＭＰＬＳといわれる光伝送路におけるＭＰＬＳ技術の研究が進んでいる。ＭＰＬＳとはＩＰパケット内に「ラベル」という識別子を挿入し、ラベルと経路の対応を管理するＩＰネットワーク上のＭＰＬＳ対応ルータがラベルによってパケットを高速転送するものである。
【０００５】
ＧＭＰＬＳルータは、ＭＰＬＳルータと光クロスコネクト機能で構成されている。このルータは他のルータとＩＰベースの制御情報を交換し、それに基づいて光クロスコネクト機能により光信号を波長ベースでルーチングする仕組みとなっている。つまり、ＭＰＬＳでいう「ラベル」部分が「波長」に対応したもので、経由するルータは波長を基にルーチングを行う。
【０００６】
このＧＭＰＬＳネットワークのパス設計について以下説明する。ここでいうパスとは、始点となるルータと終点となるルータをつなぐものであり、パス設計とは、例えば、ネットワークトポロジーやルータ間に設定する要求パス本数が与えられたときに各パスの現用経路を決定すること、および、現用経路に故障が発生したときに切り替える予備経路を決定することである。その際の各パスの波長も同時に決定する。
【０００７】
このパス設計においては、光ＭＰＬＳルータを使用するために考慮しなければならない特有の制約および実装に依存する制約がある。例えば、光ＭＰＬＳルータには波長切り替え機能を有するものとそうでないものが混在しているため、既存のＷＤＭネットワークの設計技術は適用できない。そのため、既存のＷＤＭネットワーク設計技術をそのまま適用することはできない。このような光ＭＰＬＳネットワークにおけるパス設計は次のようにして行う。
【０００８】
まず、ネットワークトポロジーを無向多重グラフによってモデル化する。また、ルータ間をつなぐリンクにそれぞれ距離とコストを与える。対象ネットワークにおいては、各パスに固有の波長が与えられている。各ルータは、その波長によって経路をルーチングする。また、同一リンクには同一波長のパスは収容できないという制約がある。ただし、ルータには、パスの波長を切り替えできるものとできないものとがある。コストや実装の観点から、一般に、１つのＧＭＰＬＳネットワーク内にこれらが混在している。
【０００９】
従って、１つのパスに１つの波長しか与えられていない場合もあるし、１つのパスが複数の波長のパスが連結したもので構成されている場合もある。いずれの場合も、各リンクは、同一波長のパスを収容できない。既存のパス設計においては、各パスには１つの波長しか割り当てられいない場合か、もしくは全てのルータで波長が切り替えられる場合となる。
【００１０】
しかし、実際のＧＭＰＬＳネットワークにおけるパス設計においては、光ＭＰＬＳルータが混在している場合を考慮しなければならない。
【００１１】
現用経路の設計においては、入力情報として、「ルータの情報（ルータの数、各ルータの波長切り替え数の上限）」、「リンクの情報（リンクの数、各リンクのリンク容量、各リンクのコスト、各リンクの距離）」、「パスの情報（パスの両端のルータ番号）」、「波長の情報（ネットワーク全体で使用できる波長数）」、「故障シナリオ情報（故障パタン（故障ルータおよびリンクの集合）、シナリオの重み）」等が必要になる。
【００１２】
制約条件は、「全てのリンクがリンク容量を満たすこと」、「同一のパスが同一リンク上を重複していないこと」、「各パスの距離が設定した長さ以下となること」、「波長切り替え機能のあるルータが存在する場合、各ルータの波長切り替え数が上限を越えないこと」である。
【００１３】
目的関数として、パスのコストの総和を設定する。これは、制約条件を満たす経路の組の中で、パスのコストの総和が最小のものを出力するためである。最終的な出力情報は、各パスの経路ルータおよびリンクの列、それに各パスの経由リンク上での波長となる。
【００１４】
また、予備経路設計については、以下で述べるように経路を探索する。予備経路とは、現用経路（経由ルータおよびリンクの列、また経由リンクでの波長）に故障が発生した場合に用意しておく経路であり、故障発生時に、この経路にルーチングを変更することで、故障個所を回避することができる。
【００１５】
この予備経路を考える際、故障シナリオを想定しておく必要がある。故障シナリオとは、同時故障で使用不可能となるルータおよびリンクの集合である。どの故障シナリオが発生しても、それに応じて予備経路に切り替えることにより、継続して使用できるように、各シナリオに対して各パスの予備パスを決める。
【００１６】
予備経路設計における制約条件としては、「現用経路のいずれかが故障シナリオの対象となること」、「予備パスが故障した個所（ルータおよびリンクの集合）を経由しないこと」がある。
【００１７】
そして、目的関数を予備パスの総数とし、必要な予備パスが最小となるようにする。最終的な出力情報は、各パスに対して、現用経路と各シナリオに対する予備パスと経由リンク上での波長となる。
【００１８】
現用経路の設計問題は、ＮＰ困難（解答が与えられさえすれば、それが正答であるかどうかを多項式時間で判断できるような問題と同程度か、あるいはそれ以上に難しい問題のこと）のクラスに属しているため、効率的に解くことは不可能と予測されている。対象となるネットワークがかなり小規模な場合、分岐限定法や切除平面法などを用いて、厳密解を求めることは不可能ではないが、ネットワーク規模の増大に従って計算時間が激増するため、現実的な時間では解けなくなる。そこで、現実的な時間で最良の解を出力するための近似解法が必要となる。
【００１９】
近似解法としては、ランダム多スタート局所探索法（Ｒａｎｄｏｍ  Ｍｕｌｔｉ−ｓｔａｒｔ  Ｌｏｃａｌ  Ｓｅａｒｃｈ）を用いたものがある。この技術は、初期解をランダムに生成し、それぞれに局所探索を適用するものである。そこで得られた解の中で最良の解を出力する。つまり、探索する範囲を限定することで、短い時間で実行可能な解を得ることができる。近似解法をパス設計に用いた際の手順例は以下のようになる。
【００２０】
（１）まず、リンク容量制約を満たす解を探索する。ここでは波長は考慮せず、全てのリンクで辺容量を満たすパスを求める。
（２）次に、波長切り替え数制約を満たす解を探索する。すなわち、（１）で得られたパスに基づき、全ての節点で波長切り替え数を満たすパスを求める。
【００２１】
以上のような定式化やアルゴリズムを基にして、厳密解法で現用経路を求める場合と、近似解法で予備経路を求める場合を例として評価実験を行った結果では、厳密解法で経路設計を行うと、ネットワーク規模が拡大するのに従い制約条件が指数的に増大するので、現実的な時間では最適解が求められない場合があるが、近似解法では、解空間（解を探索する範囲）を制限することにより短時間での解の出力が可能になる。すなわち、大規模なネットワークにおいても、近似解法を用いることで解を得ることが可能である。
【００２２】
しかし、この非特許文献１を含め、従来、光ネットワークにおけるＶＰＮパスをｅｎｄ−ｔｏ−ｅｎｄの帯域保証をしつつ最適化を行う技術は開示されていない。
【００２３】
尚、ＶＰＮを対象とした従来技術としては、例えば、特許文献１に記載の技術があるが、この技術は、ＶＰＮのサービス条件をリアルタイムに変更するものであり、ＶＰＮのパス構成を設定するものではない。
【００２４】
【特許文献１】特開２００３−１２４９８６号公報
【非特許文献１】徳久  正樹・千葉  芳之・巳波  弘佳・能上  慎也「フォトニックＭＰＬＳネットワークにおけるパス設計」、ＮＴＴ技術ジャーナル  ２００２年６月号  ｐ．６９
【発明の開示】
【発明が解決しようとする課題】
【００２５】
解決しようとする問題点は、従来の技術では、光ネットワークにおけるＶＰＮパスをｅｎｄ−ｔｏ−ｅｎｄの帯域保証をしつつ最適化を行うことはできない点である。
【００２６】
本発明の目的は、このような問題を解決し、波長をラベルとした光ネットワークにおいて、効率よく光ＶＰＮパスを設定でき、特に、光ネットワークにおける帯域保証型光ＶＰＮサービスの提供を可能とすることである。
【課題を解決するための手段】
【００２７】
上記目的を達成するため、本発明では、光ネットワークにおける波長、コスト、距離などの制約条件として、さらに、リンク帯域および要求帯域を新たに制約条件として追加し、光パスの設計を整数計画問題として定式化し、その初期解を求め、その初期解に基づき、許容解空間から局所最適解を求め、さらに、その中から準最適解を求める。尚、この初期解から局所最適解を求める際、まず、例えばダイクストラ法によって各パスの最短路である初期解を得る。ただし、ここで得られる初期解は、全ての制約条件を満たすとは限らない。そこで、求めた初期解において制約条件を満たさないリンクがあれば、そのようなリンクをランダムに選択し、そこを通過するあるパスを別なリンクを通過するように迂回させる。これを繰り返し行うことによって、全ての制約条件を満たす局所最適解を求める。そして、求めた局所最適解から、さらに、目的（目的関数）に応じたパスを選択する。このことにより、ネットワーク事業者は、提供するネットワークサービスの品質を保証できる帯域でのパス設計を効率的に行うことができる。
【発明の効果】
【００２８】
本発明によれば、光ネットワークにおいてＶＰＮ事業を営む、または予定しているネットワーク事業者において、帯域保証型光ＶＰＮサービスを実施する場合に有効である。すなわち、現在、ネットワークサービスの提供者がサービス品質を示す指標を掲げて、その基準値を維持することをユーザに保証する契約であるＳＬＡ（Ｓｅｒｖｉｃｅ  Ｌｅｖｅｌ  Ａｇｒｅｅｍｅｎｔ）が提供され始めているが、このＳＬＡを守る上で重要な前提となる帯域保証を行うメカニズムとして活用することが可能である。
【発明を実施するための最良の形態】
【００２９】
以下、図を用いて本発明を実施するための最良の形態例を説明する。
【実施例】
【００３０】
図１は、本発明に係わる光ＶＰＮパス設定装置の構成例を示すブロック図であり、図２は、本発明に係わる光ＶＰＮパス設定方法の処理手順例を示すフローチャート、図３は、本発明を適用するネットワークのトポロジー例を示す説明図、図４は、数値条件例を示す説明図、図５は、１回目の候補解例を示す説明図、図６は、２回目の候補解例を示す説明図である。
【００３１】
図１における光ＶＰＮパス設定装置１０は、ＣＰＵ（Central Processing Unit）１１、メモリ１２、マウスやキーボード等からなる入力装置１３、ＬＣＤやＣＲＴ等からなる出力装置１４、本発明に係わるプログラムやデータ等を記憶したハードディスク等からなる外部記憶装置１５、ＬＡＮ（Local Area Network）カードやモデム等からなる通信装置１６等を有したハードウェア構成であり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置１５内にインストールした後、この外部記憶装置１５からメモリ１２に読み込みＣＰＵ１１で処理することにより、データ処理部１７におけるグラフ化処理部１７ａ、制約条件処理部１７ｂ、目的関数処理部１７ｃ、最適計算処理部１７ｄ、および、記憶処理部１８におけるグラフデータ記憶部１８ａ、制約条件記憶部１８ｂ、目的関数記憶部１８ｃの、本発明に係わる各機能を実行する。
【００３２】
このような構成からなる本例の光ＶＰＮパス設定装置１０では、グラフ化処理部１７ａと制約条件処理部１７ｂにより、光ネットワークにおける「波長」、「リンク帯域」、「要求帯域」、「コスト」、「距離」などを考慮し、光パスの設計を整数計画問題として定式化し、最適計算処理部１７ｄにより、まず、初期解に基づき、許容解空間から局所最適解を求め、その中から、目的関数処理部１７ｃで設定された目的関数を満足する準最適解を求めることにより、パス設定を行う。
【００３３】
尚、最適計算処理部１７ｄにおいて、初期解から局所最適解を求める際には、例えば、まず（１）：ダイクストラ法によって各パスの最短路である初期解を得る。ただし、ここで得られる初期解は、全ての制約条件を満たすとは限らない。次に（２）：（１）で得た初期解において制約条件を満たさないリンクがあれば、そのようなリンクをランダムに選択し、そこを通過するあるパスを別のリンクを通過するように迂回させる。これを繰り返し行うことによって、全ての制約条件を満たす局所最適解を構成する。
【００３４】
光パスの設計を整数計画問題として定式化する際、以下の制約条件が必要になる。
【００３５】
（Ａ）各ルータにおける入出力の釣合がとれ、なおかつ、全てのパスが存在することを示す制約条件。ここでは、「ｉ，ｊ：ルータ番号」、「ｋ：パス番号」、「ｌ：波長番号」、「ｓｋ：ソースのルータ番号」、「ｔｋ：シンクのルータ番号」とし、
（Ａ−１）対象ルータがソースの場合の制約条件式としての下記数１
【００３６】
【数１】
2005260729.tif 000003
（Ａ−２）対象ルータがシンクの場合の制約条件式としての下記数２
【００３７】
【数２】
2005260729.tif 000004
(Ａ−３)上記以外のルータの場合の制約条件式としての下記数３
【００３８】
【数３】
2005260729.tif 000005
【００３９】
（Ｂ）同一パスかつ同一リンク上で波長が重複していないことの制約条件式としての下記数４
【００４０】
【数４】
2005260729.tif 000006
【００４１】
（Ｃ）同一波長かつ同一リンク上でパスが重複していないことの制約条件式としての下記数５
【００４２】
【数５】
2005260729.tif 000007
【００４３】
（Ｄ）全てのリンクがリンク容量を満たすことの制約条件式としての下記数６
【００４４】
【数６】
2005260729.tif 000008
【００４５】
（Ｅ）各パスの長さが設定値Ｄ以下となること（尚、この設定値Ｄにより、同じ経路を繰り返し通るような冗長なパスを除外する）の制約条件式としての下記数７
【００４６】
【数７】
2005260729.tif 000009
【００４７】
そして、光パスの設計を整数計画問題として定式化する際、目的関数として、ルータ間のリンクのコストＣｉｊを考え、例えば下記数８が必要になり、上記制約条件Ａ〜Ｅを満たす解候補（局所最適解）のうち、さらに、この目的関数を満たすものを解（準最適解）とする。
【００４８】
【数８】
2005260729.tif 000010
【００４９】
尚、上記ルータに関しては、「ソース」と「シンク」のいずれにもなる（双方向）こととしても良いし、いずれか一方となる（片方向）こととしても良い。
【００５０】
本例の光ＶＰＮパス設定装置１０では、グラフ化処理部１７ａにおいて、光ネットワークをグラフ問題として扱うため、下記のような記述をする。
【００５１】
ネットワークを構成するルータに関しては、
「Ｖ＝｛ｖ１，ｖ２，・・・，Ｖｎｖ｝、    総ルータ数：ｎｖ」
とする。
【００５２】
要求するパスとそのソース（ｓ）とシンク（ｔ）に関しては、
「Ｐ−｛（ｓ１，ｔ１），（ｓ２，ｔ２），・・・，（ｓｎｐ，ｔｎｐ）｝、    パス数：ｎｐ」
とする。
【００５３】
使用できる波長数は、「ｎｗ」とする。
【００５４】
各リンクにおける容量は「ｆｉｊ（ｉ，ｊ＝１，２，・・・，ｎｖ、    ｉ＜ｊ）とする。
【００５５】
パスｋにおける使用帯域数は「Ｂｋ（ｋ＝１，２，・・・，ｎｐ）」とする。
【００５６】
各リンクにおけるコストは「Ｃｉｊ＝１，２，・・・，ｎｖ、    ｉ＜ｊ」とする。
【００５７】
パスの最大距離は「Ｄ」とする。
【００５８】
リンク間の距離は「ｄｉｊ（ｉ，ｊ＝１，２，・・・，ｎｖ、    ｉ＜ｊ）」とする。
【００５９】
また、パスとリンクを変数化し数式として扱うために、始点番号を「ｉ」、終点番号を「ｊ」、パス番号を「ｋ」、波長番号を「ｌ」として、次のような記述をする。
【００６０】
ｘ［ｊ，ｉ，ｋ，ｌ］∈｛０，１｝（ｉ，ｊ＝１，２，・・・，ｎｖ、ｋ＝１，２，・・・，ｎｐ、ｌ＝１，２，・・・，ｎｗ）」
ｘ［ｊ，ｉ，ｋ，ｌ］＝１の場合：パス（ｋ）有り
ｘ［ｊ，ｉ，ｋ，ｌ］＝０の場合：パス（ｋ）無し
【００６１】
例えば入力装置１２により、このような光ＶＰＮのネットワークトポロジー、光ＶＰＮパスを張るノード、所要帯域等の、光ＶＰＮパス設定のために必要な情報を入力し、記憶処理部１８におけるグラフデータ記憶部１８ａ、制約条件記憶部１８ｂ、目的関数記憶部１８ｃにより、これらの情報を、外部記憶装置１５等に記憶する。
【００６２】
このように外部記憶装置１５等に記憶された各種情報を用いて、データ処理部１７において、グラフ化処理部１７ａ、制約条件処理部１７ｂ、目的関数処理部１７ｃ、最適計算処理部１７ｄにより、光ＶＰＮパスの最適計算を行う。
【００６３】
データ処理部１７で算出された結果は、出力装置１４によりモニタ画面上等で表示しても良く、また、ファイルとして外部記憶装置１５等に記憶しても良い。
【００６４】
さらに、通信装置１６により、例えばイントラネットやＶＰＮ、専用回線等を介して、光ＶＰＮパス設定のための情報の受信や、パス計算結果を送信することで、他の光パス設定装置やネットワーク事業者の有するコンピュータ装置との通信を行う。
【００６５】
本例では、データ処理部１７は、グラフ化処理部１７ａにより、図３に示すようにして、ネットワークトポロジーを無向多重グラフによってモデル化する。図３において丸印はルータ１〜７を、丸印間の実線はリンク１ａ〜９ａを表しており、各ルータ１〜７には丸中に「１〜７」のルータ番号が、また、各リンクには「１〜９」のリンク番号が割り付けられている。制約条件処理部１７ｂは、例えば図４に示す例のようにして、数値条件を設定する。例えば、図４の「容量ｆｉｊ」の図では、各リンク容量が示され、図４の「コストＣ量ｆｉｊ」の図では、各リンクのコストが示され、図４の「距離ｄｉｊ」の図では、各リンクの距離が示されている。
【００６６】
図１に示す構成により本例の光ＶＰＮパス設定装置１０では、プログラムに基づくコンピュータ処理を実行することで、記憶処理部１８において、光ネットワークのパス設計における制約条件としての波長、リンクコスト、リンク距離等が定式化された制約条件情報を入力してメモリ１２に記憶し、データ処理部１７において、メモリ１２から制約条件情報を読み出して、各定式に対する近似解法により初期解を求め、求めた初期解に基づき許容解空間から局所最適解を求め、求めた局所最適解から準最適解を求め、光ネットワークにおける光パスの設定を行う際、さらに、記憶処理部１８においては、定式化された制約条件情報として、リンク帯域と要求帯域を新たに入力してメモリ１２に記憶し、データ処理部１７においては、リンク帯域と要求帯域を含む制約条件情報をメモリ１２から読み出して、初期解と局所最適解および準最適解を求めることで、要求帯域を保証する光ＶＰＮパスの設定を行う。
【００６７】
例えば、データ処理部１７は、ダイクストラム法によって各光パスの最短路である初期解を求め、求めた初期解で制約条件情報を満たさない初期解としてのリンクを抽出し、抽出したリンクを通過するパスを別のリンクを通過するように迂回させて、制約条件情報を全て満たす局所最適解を求める機能を有する。さらに、準最適解を求める際に用いる目的関数として、リンクコストを用い、局所最適解の内、リンクコストが最小となるものを準最適解とする。
【００６８】
以下、具体的な例として、ルータ１，３，７間のパス設計について、以下の制約条件で、本例の説明を行う。
【００６９】
（１）ルータ数が７つであるので、「総ルータ数Ｖ＝｛ｖ１，ｖ２，・・・，Ｖ７｝＝７」とする。
【００７０】
（２）求める光ＶＰＮパスは、「パス１：ルータ１，７間」、「パス２：ルータ１，３間」、「パス３：ルータ３，７間」の３種類とし、「Ｐ＝{（１，７），（１，３），（３，７）}」となる。
【００７１】
（３）光ＶＰＮパスの帯域は、「パス１が帯域３」、「パス２が帯域４」、「パス３が帯域５」の３種類とし、「Ｂ１＝３」、「Ｂ２＝４」、「Ｂ３＝５」とする。
【００７２】
（４）各パスにおいて使用できる波長は２種類とし、「ｎｗ＝２」とする。
【００７３】
（５）リンクにおける容量は、図４の「容量ｆｉｊ」において示すように、「ルータ３，４間」と「ルータ４，７間」を「１」とし、その他は「１０」とし、「ｆ３４＝１」、「Ｆ４７＝１」、その他のｆｉｊは「ｆｉｊ＝１０（ｉ，ｊ＝１，２，・・・，７、  ｉ＜ｊ）」とする。
【００７４】
（６）リンクにおけるコストは、図４の「コストＣｉｊ」において示すように、「ルータ２，６間」を「２」、「ルータ３，７間」を「１０」とし、その他は「１」とし、「Ｃ２６＝２」、「Ｃ３７＝１０」、その他のＣｉｊは「Ｃｉｊ＝１  （ｉ，ｊ＝１，２，・・・，７、  ｋ＜ｊ）」とする。
【００７５】
（７）リンク間の距離は，、図４の「距離ｄｉｊ」において示すように、全て「１」とし、「ｄｉｊ＝１  （ｉ，ｊ＝１，２，・・・，７、  ｋ＜ｊ）」とする。
【００７６】
（８）パスの最大距離は「１０」とし、「Ｄ＝１０」とする。
【００７７】
また、パスとリンクの変数化に関しては、ルータ１，２間に波長番号が４であるパス３が存在する場合は「ｘ[１，２，３，４]＝１とし、ルータ１，２間に波長番号が４であるパス３が存在しない場合は「ｘ[１，２，３，４]＝０」とする。
【００７８】
制約条件の定式化に関して、「総ルータ数ｎｖ＝７」、「使用できる波長数ｎｗ＝２」で、以下に例示する。
【００７９】
（１）各ルータにおける人出力の釣合がとれ、なおかつ、全てのパスが存在することに関しての定式化は、対象ルータがソースの場合、シンクの場合、その他の場合で以下のようになる。
【００８０】
（１ａ）対象ルータがソースの場合で、「ノード１（ｓｋ＝１）の「パス２（ｋ＝２）」について定式化すると、下記数９となる。
【００８１】
【数９】
2005260729.tif 000011
【００８２】
（１ｂ）対象ルータがシンクの場合で、「ノード３（ｔｋ＝３）」の「パス２（ｋ＝２）」について定式化すると、下記数１０となる。
【００８３】
【数１０】
2005260729.tif 000012
【００８４】
（１ｃ）その他の場合で、「ノード５（ｉ＝６）」の「パス１（ｋ＝１）」について定式化すると、下記数１１となる。
【００８５】
【数１１】
2005260729.tif 000013
【００８６】
（２）同一パスかつ同一リンク上で波長が重複していないことに関して、「パス１（ｋ＝１）」について、「ルータ１，５間（ｉ＝１，ｊ＝５）」で例示すると、制約条件は下記数１２のように定式化される。
【００８７】
【数１２】
2005260729.tif 000014
【００８８】
（３）同一波長かつ同一リンク上でパスが重複していないことに関して、「波長２（ｌ＝２）」について、「ルータ１，２間（ｉ＝１，ｊ＝２  、ｉ＜ｊ）で例示すると、パスは３つなので「ｋ＝３」より、制約条件は下記数１３のように定式化される。
【００８９】
【数１３】
2005260729.tif 000015
【００９０】
（４）全てのリンクがリンク容量を満たすことに関して、「ルータ６，７間（ｉ＝６，ｊ＝７）」で例示すると、「ルータ６，７間」は「リンク容量ｆ６７」が「１０」であるため、使用帯域数に関しての制約条件は下記数１４のように定式化される。
【００９１】
【数１４】
2005260729.tif 000016
【００９２】
実際、要求帯域は、「パス１」が「Ｂ１＝３」、「パス３」が「Ｂ３＝５」であるので、下記数１５となり、これは「パス１」と「パス３」の要求帯域の和となっている。つまり、制約条件が満たされているので、「パス１」と「パス３」は「ルータ６，７」間を通すことができる。
【００９３】
【数１５】
2005260729.tif 000017
【００９４】
（５）各パスの長さが設定値ｐ以下となることに関しては、「パス３（ｋ＝３）」について例示する。「ルータ数が７」、「パスの最大距離が１０（Ｄ＝１０）」であるので、制約条件は下記数１６のように定式化される。
【００９５】
【数１６】
2005260729.tif 000018
【００９６】
実際、「パス３」では、「波長は１（ｌ＝１）」である。よって、上記数１６から下記数１７となる。この数１７は「パス３」の距離を表している。
【００９７】
【数１７】
2005260729.tif 000019
【００９８】
目的関数の定式化に関しては以下のようになる。
「ルータ数ｎｗ＝７」、「パス数ｎｐ＝３」、「波長数ｎｗ＝２」とすると、目的関数（全パスにかかるコストの総和）は下記数３４となる。
【００９９】
【数１８】
2005260729.tif 000020
【０１００】
このようにして定式化（グラフ化）された各制約条件等の情報を用いて、データ処理部１７においては、最適計算処理部１７ｄにより、図２に示す手順で、光ＶＰＮにおける近似解法を用いたアルゴリズムを実行し、候補解を求める。
【０１０１】
すなわち、図２において、まず、制約条件としてのルータ数「Ｖ」、パス数「Ｐ」、波長数「ｎｗ」、リンク容量「ｆｉｊ」、パス帯域「Ｂｋ」、リンクのコスト「Ｃｉｊ」、パスの最大距離「Ｄ」、リンク間距離「ｄｉｊ」を入力してメモリ１２に記憶する（ステップ１０１）。
【０１０２】
次に、解候補の探索回数（「ｉｎｔｅｒａｔｉｏｎ」）を入力し（ステップ１０２）。カウンタにセット・保持する（ステップ１０３）。そして、全ての制約条件を満たす解候補を近似解法を用いて探索する（ステップ１０４）。
【０１０３】
この近似解法を用いた探索においては、上述したように、光ネットワークにおける、波長、リンク帯域、要求帯域、コスト、距離などを制約条件として、光パスの設計を整数計画問題として定式化し、その初期解に基づき、許容解空間から局所最適解を求める。この初期解から局所最適解を求める際、まず、例えばダイクストラ法によって各パスの最短路である初期解を得る。ここで得られる初期解は、全ての制約条件を満たすとは限らないので、次に、求めた初期解において制約条件を満たさないリンクがあれば、そのようなリンクをランダムに選択し、そこを通過するあるパスを別なリンクを通過するように迂回させる。これを繰り返し行うことによって、全ての制約条件を満たす局所最適解を得る。
【０１０４】
この解候補の探索を、カウンタにセットした探索回数分繰り返した後に（ステップ１０５，１０６）、さらに、目的関数を最小にする解を探索し（ステップ１０７）、この解のｘ［ｉ，ｊ，ｋ，ｌ］の組み合わせ、すなわち、「始点番号ｉ」、「終点番号ｊ」、「パス番号ｋ」、「波長番号ｌ」を出力する（ステップ１０８）。
【０１０５】
ステップ１０４における解候補の探索処理では、例えば、候補解を求める回数を「２」（「ｉｎｔｅｒａｔｉｏｎ＝２」）とした場合、図５および図６に示す「パス１」〜「パス３」が得られる。この図５および図６においては、ルータ（ノード）１，３，７間の光ＶＰＮパスの候補として、パスの長さｄｉｊ（最大距離Ｄ）、帯域Ｂｋ（容量ｆｉｊ）、波長ｎｗ、コストＣｉｊ等の制約条件を満たす近似解法で得られたパス候補が示されている。図５，６のいずれも「パス１」と「パス２」として同じものが得られているが、「パス３」に関しては、図５では、ルータ３，２，１，５，６，７間のリンクが、また、図６では、ルータ３，２，６，７間のリンクが選択されている。
【０１０６】
尚、ルータ３，４，７間のリンクに関しては、図４における容量ｆｉｊの図面で示されているように、容量が「１」であり、使用（要求）帯域条件が満たされないので候補としては得られない。また、ルータ３，７間のリンクに関しては、図４におけるコストＣｉｊの図面で示されているように、コストが「１０」であり、制約条件が満たされないので候補としては得られない。
【０１０７】
このようにして、図３に示す光ＶＰＮネットワーク構成において、候補解を求める回数を「２」とし、１回目の候補解、すなわち、全ての制約条件を満たす１回目の候補解が、図５（パス１〜３）に示すようにして得られたとする。この場合の目的関数の値は、図４のコストに関する図面から「（１＋１＋１）＋（１＋１）＋（１＋１＋１＋１＋１）」＝「１０」である。
【０１０８】
これに対して、全ての制約条件を満たす２回目の候補解が図６（パス１〜３）のように得られたとする。この場合の目的関数の値は、図４のコストに関する図面から「（１＋１＋１）＋（１＋１＋１）＋（１＋２＋１）」＝「９」である。その結果、解候補の探索回数（「ｉｎｔｅｒａｔｉｏｎ」）「＝２」が終了した時点での、求めた全ての候補解の中から最小の解を探索すると、目的関数の値は２回目の候補解の方が最小となるなので、図６を最終的な解とする。
【０１０９】
以上、各図を用いて説明したように、本例では、光ネットワークにおける、波長、リンク帯域、要求帯域、コスト、距離などを制約条件として、光パスの設計を整数計画問題として定式化し、その初期解を求め、求めた初期解に基づき、許容解空間から局所最適解を求め、さらに、その中から準最適解を求める。この初期解から局所最適解を求める際、まず、例えばダイクストラ法によって各パスの最短路である初期解を得る。ただし、ここで得られる初期解は、全ての制約条件を満たすとは限らない。そこで、求めた初期解において制約条件を満たさないリンクがあれば、そのようなリンクをランダムに選択し、そこを通過するあるパスを別なリンクを通過するように迂回させる。これを繰り返し行うことによって、全ての制約条件を満たす局所最適解を求める。そして、求めた局所最適解から、さらに、目的（目的関数）に応じたパスを選択する。このことにより、ネットワーク事業者は、提供するネットワークサービスの品質を保証できる帯域でのパス設計を効率的に行うことができる。
【０１１０】
尚、本発明は、各図を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、図３において、ルータ１，３，７間のパス設計について説明したが、ルータ１，４，６，７間のパス設計にも適用でき、また、このような図３に示すようなルータ構成への適用に限定されるものではなく、より大規模なネットワーク構成にも適用可能である。さらに、本例でのコンピュータ構成におけるプログラムのインストール形態に関しても、光ディスクを記録媒体として用いているが、ＦＤ（Flexible Disk）等を記録媒体として用いることでも良く、また、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【図面の簡単な説明】
【０１１１】
【図１】本発明に係わる光ＶＰＮパス設定装置の構成例を示すブロック図である。
【図２】本発明に係わる光ＶＰＮパス設定方法の処理手順例を示すフローチャートである。
【図３】本発明を適用するネットワークのトポロジー例を示す説明図である。
【図４】数値条件例を示す説明図である。
【図５】１回目の候補解例を示す説明図である。
【図６】２回目の候補解例を示す説明図である。
【符号の説明】
【０１１２】
１〜７：ルータ、１ａ〜９ａ：リンク、１０：光ＶＰＮパス設定装置、１１：ＣＰＵ、１２：メモリ、１３：入力装置、１４：出力装置、１５：外部記憶装置、１６：通信装置、１７：データ処理部、１７ａ：グラフ化処理部、１７ｂ：制約条件処理部、１７ｃ：目的関数処理部、１７ｄ：最適計算処理部、１８：記憶処理部、１８ａ：グラフデータ記憶部、１８ｂ：制約条件記憶部、１８ｃ：目的関数記憶部。
【図１】
2005260729.tif 000037
【図２】
2005260729.tif 000038
【図３】
2005260729.tif 000039
【図４】
2005260729.tif 000040
【図５】
2005260729.tif 000041
【図６】
2005260729.tif 000042