(57)【特許請求の範囲】
【請求項１】
複数のノード装置がリング状に接続されたリングを、複数備えたマルチリング網上に設定されるパスの経路を決定する機能を備えたパス収容設計装置が実行するパス収容設計方法であって、
経路を決定する対象となるパスの始点ノードを示す情報と終点ノードを示す情報の入力を受けて、当該パスが通過するリングから構成される通過リング網を決定する通過リング網決定ステップと、
前記通過リング網決定ステップにより決定された通過リング網の範囲内で、前記パスの経路の探索を行うパス経路決定ステップと、を備え、
前記パスの経路は第１の経路と第２の経路の２つの経路であり、
前記パス経路決定ステップにおいて、前記パス収容設計装置は、
前記パスの始点ノードと、当該始点ノードが属するリング上のリング間接続点ノードとの間の最短経路を選択し、以降、終点ノードが属するリングまでの各リングにおいて、リング間接続点ノードを結ぶ最長経路と最短経路を、交互に順番に選択することにより、始点ノードから終点ノードまでの前記第１の経路を決定し、
前記第１の経路と各リング内において逆方向で重ならない経路を前記第２の経路として決定する
ことを特徴とするパス収容設計方法。
【請求項２】
複数のノード装置がリング状に接続されたリングを、複数備えたマルチリング網上に設定されるパスの経路を決定する機能を備えたパス収容設計装置が実行するパス収容設計方法であって、
経路を決定する対象となるパスの始点ノードを示す情報と終点ノードを示す情報の入力を受けて、当該パスが通過するリングから構成される通過リング網を決定する通過リング網決定ステップと、
前記通過リング網決定ステップにより決定された通過リング網の範囲内で、前記パスの経路の探索を行うパス経路決定ステップと、を備え、
前記パスの経路は第１の経路と第２の経路の２つの経路であり、
前記パス経路決定ステップにおいて、前記パス収容設計装置は、
前記パスの始点ノードと、当該始点ノードが属するリング上のリング間接続点ノードとの間の最長経路を選択し、以降、終点ノードが属するリングまでの各リングにおいて、リング間接続点ノードを結ぶ最短経路と最長経路を、交互に順番に選択することにより、始点ノードから終点ノードまでの前記第１の経路を決定し、
前記第１の経路と各リング内において逆方向で重ならない経路を前記第２の経路として決定する
ことを特徴とするパス収容設計方法。
【請求項３】
前記パス収容設計装置は、リング間の接続関係情報を格納したリング間接続情報格納手段を備え、
前記始点ノードを示す情報は、当該始点ノードが属するリングの識別情報を含み、前記終点ノードを示す情報は、当該終点ノードが属するリングの識別情報を含み、
前記通過リング網決定ステップにおいて、前記パス収容設計装置は、
前記始点ノードを示す情報から、当該始点ノードが属するリングの識別情報を取得し、前記終点ノードを示す情報から、当該終点ノードが属するリングの識別情報を取得し、
前記リング間接続情報格納手段に格納されたリング間の接続関係情報を用いて、前記識別情報で識別されるリング間の最短経路探索を行うことにより、前記通過リング網を決定する
ことを特徴とする請求項１又は２に記載のパス収容設計方法。
【請求項４】
前記始点ノードが属するリングの識別情報、又は前記終点ノードが属するリングの識別情報が、複数のリングを示す情報である場合には、前記パス収容設計装置は、当該識別情報で識別される複数のリングのそれぞれと、他方のリングとの間で最短経路探索を行う
ことを特徴とする請求項３に記載のパス収容設計方法。
【請求項５】
前記通過リング網決定ステップにおいて、前記最短経路探索の結果、複数の経路が得られた場合に、前記パス収容設計装置は、
前記複数の経路の各々について、経路上の各リングの空きリソース量の合計、もしくは経路上の各リングのノード数の合計を算出し、
空きリソース量の合計が最大の経路、もしくは、ノード数の合計が最小の経路を前記複数の経路から選択することにより、当該経路からなる前記通過リング網を決定する
ことを特徴とする請求項３又は４に記載のパス収容設計方法。
【請求項６】
前記パス収容設計装置は、ノード間の接続関係情報を格納したノード間接続情報格納手段を備え、前記パス収容設計装置は、
前記通過リング網決定ステップにおいて、前記ノード間接続情報格納手段に格納されたノード間の接続関係情報から、前記通過リング網を構成するリング上に存在しないノードの接続関係情報を削除し、
前記パス経路決定ステップにおいて、前記削除後のノード間接続情報格納手段に格納された情報を用いて、前記パスの経路の探索を行う
ことを特徴とする請求項１ないし５のうちいずれか１項に記載のパス収容設計方法。
【請求項７】
前記パス経路決定ステップにおいて、前記パス収容設計装置は、
前記第１の経路の伝送距離もしくはホップ数が、予め算出した伝送可能距離もしくは予め算出した伝送可能ホップ数を越えるか否かの判定を行い、越える場合に、前記第１の経路を、前記始点ノードと前記終点ノード間の最短経路とし、
前記第１の経路と各リング内において逆方向で重ならない経路を前記第２の経路として決定する
ことを特徴とする請求項１ないし６のうちいずれか１項に記載のパス収容設計方法。
【請求項８】
前記パス収容設計装置は、
伝送品質と、信頼性のどちらかもしくは両方によって定められたサービスクラスのそれぞれに対応する処理手段を備え、
サービスクラスの入力を受け、当該サービスクラスに対応した処理手段により、当該サービスクラスに対応した処理を行う
ことを特徴とする請求項１ないし７のうちいずれか１項に記載のパス収容設計方法。
【請求項９】
複数のノード装置がリング状に接続されたリングを、複数備えたマルチリング網上に設定されるパスの経路を決定する機能を備えたパス収容設計装置が実行するパス収容設計方法であって、
経路を決定する対象となるパスの始点ノードを示す情報と終点ノードを示す情報の入力を受けて、当該パスが通過するリングから構成される通過リング網を決定する通過リング網決定ステップと、
前記通過リング網決定ステップにより決定された通過リング網の範囲内で、前記パスの経路の探索を行うパス経路決定ステップと、を備え、
前記パス収容設計装置は、伝送品質と、信頼性のどちらかもしくは両方によって定められたサービスクラスのそれぞれに対応する処理手段を備え、サービスクラスの入力を受け、当該サービスクラスに対応した処理手段により、当該サービスクラスに対応した処理を行う装置であり、
前記パス収容設計装置に第１のサービスクラスが入力された場合に、当該パス収容設計装置は、前記通過リング網上で、第１の経路を決定し、当該第１の経路と各リング内において逆方向で重ならない経路として第２の経路を決定し、前記第１の経路上で信号伝送が行われるパスの故障時に、当該パスを前記第２の経路に切り替える処理を行い、
前記パス収容設計装置に第２のサービスクラスが入力された場合に、当該パス収容設計装置は、前記通過リング網上で、第１の経路を決定し、当該第１の経路と各リング内において逆方向で重ならない経路として第２の経路を決定し、前記第１の経路上で信号伝送が行われるパスの故障時に、当該パスを前記第２の経路に切り替える処理を行い、
第２のサービスクラスにおける前記第２の経路は、第２のサービスクラスの別のパスの第２の経路として共有される経路である
ことを特徴とするパス収容設計方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノード装置がリング状に接続されたリング網を、複数備えたマルチリング網におけるパスの収容設計方法に関するものである。
【背景技術】
【０００２】
光ファイバ等の物理的な伝送路により接続される複数のノード装置から構成される通信網においては、始点となるノード装置と終点となるノード装置との間で、信号伝送を行うための論理的なパスが設定される。
【０００３】
また、通信網においては、パスが経由する複数のノード装置を結ぶ経路として、例えば、現用系と予備系のように、少なくとも２つの経路を設けることが行われている。そして、現用系と予備系の両方の伝送路に障害が発生することを避けるために、２つの経路は、伝送路（リンク）が互いに重ならないように設定することが望ましい。以下、２つの経路を第１の経路及び第２の経路と呼ぶ。
【０００４】
さて、近年、大規模な中継系ネットワーク等を構成するために、複数のリング網を互いに接続したマルチリング網が使用されている。ここで、特許文献１と特許文献２には、マルチリング網におけるパスの第１の経路と第２の経路を、互いに重ならないように設計することが記載されている。また、非特許文献１には、マルチリング網の種々の構成例が記載されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平１０−２２４３８９号公報
【特許文献２】特開平１０−７９７５７号公報
【非特許文献】
【０００６】
【非特許文献１】J. Wang et al., "Multiring Techniques for Scalable Battlespace Group Communications", IEEE Com. Mag., November, 2005.
【非特許文献２】H. Zang, et al., "A Review of Routing and Wavelength Assignment Approaches for Wavelength-Routed Optical WDM Networks", OPTICAL NETWORKS MAGAZINE, Vol. 47-60, January 2000.
【非特許文献３】Y. Huang, J.P. Heritage, and B. Mukherjee, "Connection provisioning with transmission impairment consideration in optical WDM networks with high-speed channels," IEEE J. Lightw. Technol., Vol. 23, No. 3, pp. 982-993, March 2005.
【非特許文献４】"Transmission media and optical systems characteristics -  Characteristics of optical systems," ITU-T Recommendation G.680.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
マルチリング網の構成例として、図２３に示すようなHierarchical網と、図２４に示すようなHSHR (Hierarchical Self-Healing Ring) 網とがある。
【０００８】
図２３に示すHierarchical網において、最短経路探索が可能なダイクストラアルゴリズム等に基づいて、第１の経路と第２の経路とを互いに重ならないように設計した場合、各リング内に第１経路と第２経路が存在するとは限らず、通信網全体に２つの経路が分散され、ネットワークの保守・管理面において困難が生じる場合がある。
【０００９】
また、図２４に示すHSHR 網において、２つの経路をそれぞれ最短経路探索で設計する場合は、需要発生パスのノードペアによっては、第１の経路もしくは第２の経路が伝送制約内に収まる距離にならず、再生中継器の配備が必要となる場合が発生し得る。また、第１の経路と第２の経路の経路長に大きな差が生じる可能性もあり、伝送遅延が大きくなる場合も生じる。
【００１０】
本発明は上記の点に鑑みてなされたものであり、２つの経路を分散させることなく、更に、２つの経路長に大きな差を生じさせずに、マルチリング網におけるパスの２つの経路を決定する技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、本発明は、複数のノード装置がリング状に接続されたリングを、複数備えたマルチリング網上に設定されるパスの経路を決定する機能を備えたパス収容設計装置が実行するパス収容設計方法であって、経路を決定する対象となるパスの始点ノードを示す情報と終点ノードを示す情報の入力を受けて、当該パスが通過するリングから構成される通過リング網を決定する通過リング網決定ステップと、前記通過リング網決定ステップにより決定された通過リング網の範囲内で、前記パスの経路の探索を行うパス経路決定ステップと、を備えたことを特徴とするパス収容設計方法として構成される。
【００１２】
また、本発明は、複数のノード装置がリング状に接続されたリングを、複数備えたマルチリング網上に設定されるパスの経路を決定する機能を備えたパス収容設計装置が実行するパス収容設計方法であって、前記パスの経路は第１の経路と第２の経路の２つの経路であり、前記第１の経路を全経路探索により探索し、前記第２の経路を、前記第１の経路と重ならない経路として決定するステップと、前記探索により求められる第１の経路と第２の経路の組み合わせ群の中で、第１の経路と第２の経路のホップ数の差、及び第１の経路と第２の経路距離の差のうちのいずれか一方又は両方が最小となる第１の経路と第２の経路の組み合わせを、前記パスの２つの経路として決定するステップと、を有することを特徴とするパス収容設計方法として構成してもよい。
【００１３】
また、本発明は、複数のノード装置がリング状に接続されたリングを、複数備えたマルチリング網上に設定されるパスの経路を決定する機能を備えたパス収容設計装置が実行するパス収容設計方法であって、前記パスの経路は第１の経路と第２の経路の２つの経路であり、前記パスの始点ノードと、当該始点ノードが属するリング上のリング間接続点ノードとの間の最短経路を選択し、以降、終点ノードが属するリングまでの各リングにおいて、リング間接続点ノードを結ぶ最長経路と最短経路を、交互に順番に選択することにより、始点ノードから終点ノードまでの前記第１の経路を決定するステップと、前記第１の経路と各リング内において逆方向で重ならない経路を前記第２の経路として決定するステップと、を有することを特徴とするパス収容設計方法として構成してもよい。
【００１４】
また、本発明は、複数のノード装置がリング状に接続されたリングを、複数備えたマルチリング網上に設定されるパスの経路を決定する機能を備えたパス収容設計装置が実行するパス収容設計方法であって、前記パスの経路は第１の経路と第２の経路の２つの経路であり、前記パスの始点ノードと、当該始点ノードが属するリング上のリング間接続点ノードとの間の最長経路を選択し、以降、終点ノードが属するリングまでの各リングにおいて、リング間接続点ノードを結ぶ最短経路と最長経路を、交互に順番に選択することにより、始点ノードから終点ノードまでの前記第１の経路を決定するステップと、前記第１の経路と各リング内において逆方向で重ならない経路を前記第２の経路として決定するステップと、を有することを特徴とするパス収容設計方法として構成することもできる。
【発明の効果】
【００１５】
本発明によれば、複雑な形のマルチリング網であっても、各リング内に第１の経路と第２の経路を閉じた収容設計が可能となる。これにより、探索経路数が少なくなり保守・運用の困難性が削減される。この効果は、マルチリング網が複雑化するほど大きくなる。また、第1の経路と第２の経路の経路長差を減らすことが可能となり、これにより、一方の経路のみ伝送設計可能な場合を減らすことが可能となる。従って、再生中継器を余分に配備する必要がなくなることから設備コストの削減が可能となる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施の形態におけるパス収容設計装置１の機能構成図である。
【図２】マルチリング網の構成を示す図である。
【図３】マルチリング網の構成を示す図である。
【図４】ノード間接続情報格納部１７に格納されるテーブル情報の例を示す図である。
【図５】リング間接続情報格納部１６に格納されるテーブル情報の例を示す図である。
【図６】第１の実施の形態における処理手順を示すフローチャートである。
【図７】リソース情報格納部１８に格納されるリソース情報の例を示す図である。
【図８】ノード数情報格納部１９に格納される情報の例を示す図である。
【図９】第１の実施の形態における別の処理手順を示すフローチャートである。
【図１０】第１の実施の形態において選択されたリングの経路を示す図である。
【図１１】一部のノード間接続関係を削除した後のノード間接続情報格納部１７に格納された情報を示す図である。
【図１２】リング間接続の物理トポロジを示す図である。
【図１３】ノード間接続の物理トポロジを示す図である。
【図１４】第２の実施の形態における処理手順を示すフローチャートである。
【図１５】第２の実施の形態においてノード間接続情報格納部１７に格納されるテーブル情報の例を示す図である。
【図１６】第２の実施の形態において決定された第１の経路と第２の経路を示す図である。
【図１７】第３の実施の形態における処理手順を示すフローチャートである。
【図１８】第４及び第５の実施の形態における処理手順を示すフローチャートである。
【図１９】第６の実施の形態における処理手順を示すフローチャートである。
【図２０】第７の実施の形態における処理手順を示すフローチャートである。
【図２１】第９〜第１２の実施の形態において適用される網構成の例を示す図である。
【図２２】第９〜第１２の実施の形態において適用される網構成の例を示す図である。
【図２３】従来技術の問題点を説明するための図である。
【図２４】従来技術の問題点を説明するための図である。
【発明を実施するための形態】
【００１７】
本発明の実施の形態を説明するにあたり、まず、「パス」の用語について説明する。本明細書及び特許請求の範囲における「パス」は、光ファイバ等の物理的な伝送路媒体上に設定される論理的な伝送路であり、始点となるノード装置と、終点となるノード装置との間を結ぶ信号の伝送路である。本発明の実施の形態では、パスとして波長パスを用いることを想定しているが、本発明は、波長パスに限らず、他の種類のパスにも適用できることはいうまでもない。このようなパスとしては、例えば、TDMパス、Ethernet（登録商標）のパス、MPLSのLabel Switched Path、または、それらをグループ化したVCAT(Virtual Concatenation)、Link Aggregation等がある。
【００１８】
以下、図面を参照して本発明の実施の形態を説明する。以下の本発明の実施の形態の第１〜第８までは図２３に示したHierarchical網のような縦横にリングが広がっていくマルチリング網への適用に適しており、本発明の実施の形態の第９〜第１２は、図２４に示したHSHR網のように１つのリングに複数のリングが繋がっているマルチリング網への適用に適している。
【００１９】
[装置構成]
まず、本発明の実施の形態におけるパス収容設計装置１について説明する。図１に、パス収容設計装置１の機能構成図を示す。図１に示すように、パス収容設計装置１は、入出力部１１、パス通過リング網決定部１２、パス経路決定部１３、波長設計部１４、パス制御部１５、リング間接続情報格納部１６、ノード間接続情報格納部１７、リソース情報格納部１８、ノード数情報格納部１９、波長情報格納部２０を備えている。以下、各機能部の概要を説明する。
【００２０】
入出力部１１は、外部からの情報をパス収容設計装置１内に入力し、パス収容設計装置１から外部に情報（計算結果、制御情報等）を出力する機能部であり、オペレータが用いるユーザインタフェースや、通信ネットワークとデータ通信を行うための通信機能等を含む機能部である。
【００２１】
パス通過リング網決定部１２は、設計対象パスの始点ノードと終点ノードの入力を受けて、パスの経路が通過するリング群で構成される通過リング網（リングの接続経路）を決定する機能等を有する。パス経路決定部１３は、設計対象パスの始点ノードと終点ノードとを結ぶパスの経路（経由するノードの経路）を決定する機能等を有する。波長設計部１４は、決定された経路において、パスが使用する波長を割り当てる機能を有する。パス制御部１５は、例えば、パスの経路上の各ノード装置に対して、信号を伝送できるように波長の確保や設定を行う機能を有する。各情報格納部については、以下で説明する各実施の形態において説明する。
【００２２】
パス収容設計装置１は、以下の各実施の形態で使用されるものである。ただし、上記の全ての機能部が必要なわけではなく、各実施の形態の処理に必要な機能部が備えられていればよい。例えば、パス収容設計装置１はパスの設計だけを行い、パスの実際の設定制御は他の装置が行うこととする場合は、パス制御部１５は不要である。
【００２３】
パス収容設計装置１は、信号の伝送を行うマルチリング網の外部に備えられ、制御ネットワークで各伝送装置（ノード装置）と通信可能な装置でもよいし、パス収容設計のみを行う場合には、マルチリング網に接続されない装置でもよい。また、パス収容設計装置１は、ノード装置の中に組み込まれた装置であってもよい。
【００２４】
パス収容設計装置１は、ロジック回路等のハードウェアで実現することもできるし、ＣＰＵとメモリを備えたコンピュータ装置に、各実施の形態で説明する処理に対応したプログラムを搭載することにより実現することもできる。当該コンピュータ装置は、サーバ等であってもよいし、伝送装置の中の制御装置であってもよい。また、上記プログラムは、可搬メモリ等の記録媒体から、コンピュータ装置にインストールしてもよいし、ネットワーク上のサーバからプログラムをダウンロードしてコンピュータ装置にインストールしてもよい。
［第１の実施の形態］
以下、本発明の第１の実施の形態について説明する。図２及び図３に、本実施の形態において例として用いるマルチリング網の構成を示す。図２は、リング間接続関係のみを示しており、図３は、各リングにおける各ノードまで示している。
【００２５】
図２、図３に示すように、当該マルチリング網のリング数は６であり、各リング内のノード数は５である。
【００２６】
本実施の形態では、リングを識別するための番号を各リングに付与する。図２の例では、１から６までの番号が、それぞれ各リングに付与されている。
【００２７】
また、リングを構成する各ノードには、リングの番号を加味した番号を付与する。図３に示す例では、各ノードに２桁の番号を付与しており、２桁のうち、１桁目をリングの番号とし、２桁目を、当該リング内のノードの番号としている。本例では２桁の番号を付与しているが、もちろん、リングの数、及び１ノード内のリングの数に応じて桁数は変わる。例えば、リング内のノード数が２桁以上の数の場合は、ノード番号は３桁以上の数となる。
【００２８】
図３に示す例において、例えば、ノード番号が１５のノード（"ノード１５"と表記する場合がある）は、リング番号が１のリング（"リング１"と表記する場合がある）におけるノード番号が５のノードを指す。
【００２９】
リングとリングの接続点においては２つのリング番号とノード番号が付与される。例えば２３３５はリング番号が２のリングと、リング番号が３のノードとの間の境界ノードを表している。これらの番号付けによってノードとリングの対応関係を識別することが可能になる。なお、本実施の形態では、ノードやリングを識別する識別情報として番号を用いているが、識別情報として番号を用いることは必須でなく、情報を区別することができるものであればどのような識別情報を用いてもよい。
【００３０】
パス収容設計装置１におけるノード間接続情報格納部１７には、上記のような番号付けをしたノード間の接続関係を表すテーブル情報が格納される。図４に、ノード間接続情報格納部１７に格納されるテーブル情報の例を示す。
【００３１】
図４に示す例では、各ノードの番号に対応付けて、当該ノードに隣接するノードの番号を記録した隣接リスト形式を用いている。また、図４の例において、"−１"は、接続されるノードがないことを示している。例えば、図４の例では、図３に示す構成のとおり、ノード１１に隣接する各ノードの番号１５と１２２５が、１１に対応付けて記録されている。
【００３２】
また、パス収容設計装置１におけるリング間接続情報格納部１６には、上記のような番号付けをしたリング間の接続関係を表すテーブル情報が格納される。図５に、リング間接続情報格納部１６に格納されるテーブル情報の例を示す。
【００３３】
図５に示す例でも、ノード間接続の場合と同様に、各リングの番号に対応付けて、当該リングに隣接するリングの番号を記録した隣接リスト形式を用いている。図５の例において、"−１"は、接続されるリングがないことを示している。例えば、図５の例では、図２に示す構成のとおり、リング１に隣接する各リングの番号２と４が、１に対応付けて記録されている。
【００３４】
次に、パス収容設計装置１により実行されるパス収容設計処理の流れを、図６のフローチャートを参照して説明する。
【００３５】
まず、例えば、オペレータが、クライアント等から、設計対象パスの始点ノード及び終点ノードを特定する情報を含むパス収容設計要求を受けて、始点ノード番号及び終点ノード番号をパス収容設計装置１に入力する（ステップ０）。ここでは、始点ノードが１５番、終点ノードが６３番であったものとする。
【００３６】
入出力部１１から始点ノード番号及び終点ノード番号を受信したパス通過リング網決定部１２は、まず、始点リング及び終点リングの抽出を行う（ステップ１）。ここでは、パス通過リング網決定部１２は、始点ノード番号１５から、１桁目の数字１を始点リングの番号として抽出し、終点ノード番号６３から、１桁目の数字６を終点リングの番号として抽出する。
【００３７】
なお、上記の例は、始点ノードと終点ノードがともに、リングとリングの接続点でない場合である。始点ノードと終点ノードのいずれか又は両方がリングとリングの接続点である場合、当該ノードに隣接する複数のリングを始点（又は終点）リングとし、以下で説明する最短経路探索を行って通過リング網を求める。
【００３８】
例えば、図３において、仮に、１３４１が始点ノードであり、３４６１が終点ノードであった場合、パス通過リング網決定部１２は、ノード番号から、始点リングとしてリング１及びリング４を抽出し、終点リングとしてリング３及びリング６を抽出し、リング１−リング３、リング１−リング６、リング４−リング３、リング４−リング６の区間のそれぞれで最短経路探索を行うことになる。この場合は、経路探索ステップで、必ず複数経路が選択されることになる。
【００３９】
続いて、パス通過リング網決定部１２は、リング間接続情報格納部１６に格納された情報（図５）を用いて、始点リングから終点リングまでのリング間の最短経路探索を行う（ステップ２）。最短経路探索には、例えば、ダイクストラアルゴリズムを用いる。
【００４０】
本実施の形態では、最短経路探索を行った結果、１番目の経路（リング間接続の経路）として１−２−３−６、２番目の経路として１−４−５−６、３番目の経路として１−２−５−６の３つの最短経路が検出される。より具体的には、リング１に接続されるリング２、４を抽出し、リング２、リング４それぞれについて、接続されているリングを探し、リング６がみつかるまで、接続関係を探すことにより、上記の経路が検出される。
【００４１】
続いて、パス通過リング網決定部１２は、最短経路探索の結果、複数の経路が検出されたかどうかの判定を行う（ステップ３）。ステップ３の判定の結果、複数の経路が検出されなかった場合は、ステップ５に進み、複数の経路が検出された場合は、ステップ４に進む。
【００４２】
ステップ４において、パス通過リング網決定部１２は、ステップ２で検出された複数の経路の中から、１つの経路を選択する処理を行う。本実施の形態では、パス通過リング網決定部１２は、リソース情報格納部１８に格納されているリソース情報を参照し、リソース情報に基づき、１つの経路を選択している。
【００４３】
図７に、リソース情報格納部１８に格納されるリソース情報の例を示す。図７に示す例では、当該リソース情報は、各リングについて、そのリングで使用されていない空き波長（リソース）の数を記録した情報である。
【００４４】
ステップ４では、パス通過リング網決定部１２は、図７に示すリソース情報を用いて、複数の経路のそれぞれについて、経路上のリングの空きリソースの合計を計算し、合計が最も大きい経路を選択する。
【００４５】
図７の例では、１番目の経路（１−２−３−６）は空き波長合計が６５本、２番目の経路（１−４−５−６）は８０本、３番目の経路（１−２−５−６）は７５本と計算されるので、一番空きリソースの多い２番目の経路１−４−５−６が選択され、ステップ５に進む。なお、複数の経路の中から、１つの経路を選択する方法として、上記の方法は一例に過ぎず、この他の種々の方法を用いることができる。
【００４６】
例えば、図２、図３の例においては、リング内のノード数が全てのリングで同じであったが、各リングでノード数が異なり得る場合は、各リング内のノード数を格納しているノード数情報格納部１９を参照して、最小ノード数の経路を、複数経路から選択することも可能である。
【００４７】
図８に、ノード数情報格納部１９に格納される情報の例を示す。図８の例では、１番目の経路（１−２−３−６）はリング毎のノード数の合計が３４、２番目の経路（１−４−５−６）は３９、３番目の経路（１−２−５−６）は３７と計算されるので、一番ノード数の小さい１番目の経路１−２−３−６が選択されることになる。
【００４８】
また、リソース情報格納部１８に格納される情報（図７）と、ノード数情報格納部１９に格納される情報（図８）の両方を用いることにより、複数経路から１つの経路を選択することとしてもよい。
【００４９】
この場合の処理を、図９を参照して説明する。図９に示すフローチャートは、図６のフローチャートにおけるステップ３とステップ４を、ステップ３−１〜ステップ４−２に置き換えたものであり、他の部分は、図６と同じである。
【００５０】
図９のステップ３−１で、複数の経路があると判定された場合、パス通過リング網決定部１２は、ステップ４−１として、まず、前述したように経路上のリング毎の合計ノード数を用いて経路選択を行い、ここで経路が一意に定まったら（ステップ３−２のNo)、ステップ５へ進む。複数経路が存在した場合（ステップ３−２のYes）、ステップ４−２として、前述したように空きリソース量の多い経路を選択し、ステップ５に進む。
【００５１】
上記のように空きリソースやノード数によって通過リング経路を選択するのではなく、クライアントの要望等、意図的に選択したい経路を選択し、ステップ５に進むようにしてもよい。
【００５２】
以下では、パスの通過リング網として２番目の経路１−４−５−６が選択されたものとして説明を行う。すなわち、図１０に示す経路が選択されたものとする。
【００５３】
次に、パス通過リング網決定部１２は、ノード間接続情報格納部１７に格納された情報に対するノード接続関係の変更処理を行う（図６、図９のステップ５）。つまり、パス通過リング網決定部１２は、通過リング網として選択された経路上のリング以外のリングに関わるノード接続関係(通過リング網を構成するリング上に存在しないノードの接続関係)を、ノード間接続情報格納部１７に格納された情報から削除する。
【００５４】
上記ノード接続関係を削除した後のノード間接続情報格納部１７に格納された情報を図１１に示す。本例では、経路１−４−５−６が、通過リング網の経路として選択されたので、図１１に示す例において、（１、４、５、６）以外のリング番号２及び３を含むノード番号の隣接リストの行の全てが−１に置き換えられる。
【００５５】
ただし、リングとリングとの間の接続点においては、２つのリングの番号のうちの両方が削除対象のリング番号である場合のみ、行の全てを−１と置き換え、どちらか一方のリング番号のみが削除対象のリング番号である場合は、削除対象のリング番号を含むノード番号のみを−１に置き換える。
【００５６】
例えば、ノード番号２３３５は、削除対象のリング番号２及びリング番号３の両方が含まれているため、この番号の行の全てのノード番号は−１に置き換えられる。一方、３４６１については、削除対象のリング番号として、３のみが含まれているので、この行においては、リング番号として３を含む２３３５と３３のみが−１に変更される。
【００５７】
ステップ５の変更処理後のリング間接続情報（図１１）に対応するリング間接続及びノード間接続の物理トポロジは、それぞれ図１２及び図１３に示すものとなる。図１２、図１３に示すように、始点を含むリング、及び終点を含むリングは、それぞれ他の一つのリングにだけ接続され、途中のリングは、２つのリングにだけ挟まれるので、リング接続経路は１つだけであり、この後のパス経路探索においては、当該１つのリング経路内に閉じたノードの経路探索が行われることになる。従って、パスの２つの経路（ノード間接続の経路）を決定するにあたって、２つの経路は、同一のリングを通過することになり、経路が分散されてしまうという問題が解決される。
【００５８】
その後、パス経路決定部１３が、始点ノードと終点ノードを結ぶパスの第１の経路と第２の経路を決定し、波長設計部１４が、各経路に割り当てる波長を決定する（ステップ６）。第１の実施の形態では、パスの経路の決定方法、及び波長設計方法は特定の方法に限定されないが、例えば、後述する各実施の形態で説明する方法を用いることができる。
［第２の実施の形態］
次に、本発明の第２の実施の形態を、図１４に示すフローチャートに沿って説明する。第２の実施の形態においては、まず、第１の実施の形態と同様にして、パス通過リング網決定部１２が、通過リング網の経路の決定、及びノード接続関係の変更処理を行う（図６、図９のステップ５までの処理）。以下では、第１の実施の形態で用いた具体例に基づき説明を行う。つまり、以下で説明するステップ２１の処理の前の時点で、ノード間接続情報格納部１７には、図１１〜図１３に示した情報が格納されている。
【００５９】
図１４のステップ２１において、パス経路決定部１３は、まず、パスの第１の経路（ノード間接続の経路）の探索を行う。
【００６０】
ここでは、パス経路決定部１３は、通過ノード数が小さい経路を選択することにより、第１の経路を決定する。例えば、リング１においては、１５を始点として、リング間接続ノードの１３４１までの経路で通過ノード数が小さい方を選択する。
【００６１】
つまり、パス経路決定部１３は、図１１に示す情報に基づき、ノード１５からノード１３４１までの経路としては、１５−１４−１３４１の経路と１５−１１−１２２５−１３４１の2種類があることを識別し、通過ノード数が小さいほうの経路である１５−１４−１３４１の経路を選択する。このようにして、ステップ２１における経路探索で、第１の経路は１５−１４−１３４１−４２５５−２４５１−５２６５−６４−６３と定まる。
【００６２】
次に、図１４のステップ２２において、パス経路決定部１３は、第２の経路の探索を行う。ここでは、図１５に示すように、パス経路決定部１３は、ノード間接続情報格納部１７に格納された情報に対し、ステップ２１で決定された第１の経路の各リンクに該当するノード番号の欄に−１を記入することで、第１の経路の接続関係を削除する。パス経路決定部１３は、書き換えた後の図１５に示す情報に基づき、第２の経路を一意に求めることが可能である。すなわち、本例では、第２の経路は、１５−１１−１２２５−１３４１−４５−４４−４３−４２５５−５４−５３−５２６５−３４６１−６２−６３に決まる。第１の経路と第２の経路を図示すると、図１６に示すとおりとなる。
【００６３】
続いて、図１４におけるステップ２３にて、波長設計部１４が、第１の経路、第２の経路それぞれに対して波長の割り当てを行う。波長の割り当ては、波長情報格納部２０に格納された波長割当情報を参照することにより、既存技術を用いて行うことができる。既存技術として、例えば、非特許文献２に記載されたFirst-Fitアルゴリズムを適用できる。
【００６４】
上記のように、本実施の形態では、始点ノードと終点ノードとの間の最短経路を第１の経路として決定し、第２の経路を、第１の経路と各リング内において逆方向で重ならない経路として決定している。つまり、本実施の形態では、各リング内で、時計周り方向及び反時計回り方向に２つの経路が選択されている。
［第３の実施の形態］
次に、本発明の第３の実施の形態を、図１７に示すフローチャートに沿って説明する。第３の実施の形態においては、まず、第１の実施の形態と同様にして、パス通過リング網決定部１２が、通過リング網の経路の決定、及びノード接続関係の変更処理を行う（図６、図９のステップ５までの処理）。以下では、第１の実施の形態で用いた具体例に基づき説明を行う。つまり、以下で説明するステップ３１の処理の前の時点で、ノード間接続情報格納部１７には、図１１〜図１３に示した情報が格納されている。
【００６５】
図１７のステップ３１において、パス経路決定部１３は、まず、パスの第１の経路の探索を行う。ここでは、パス経路決定部１３は、全経路探索アルゴリズムを用いた経路探索を行うことにより、１つの第１の経路を選択する。全経路探索アルゴリズムとしては、例えば、幅優先探索アルゴリズム、深さ優先探索アルゴリズム等がある。
【００６６】
次に、パス経路決定部１３は、第２の経路の探索を行う（ステップ３２）。ここでは、パス経路決定部１３は、第２の実施の形態におけるステップ２２と同様にして、ノード間接続情報格納部１７に格納された情報に対して、ステップ３１で選択された経路の各リンクの接続関係を削除する処理を行う。これにより第２の経路は一意に定まる。
【００６７】
続いて、パス経路決定部１３は、ステップ３１で決定した第１の経路のホップ数（リンク数でもある）と、ステップ３２で決定した第２の経路のホップ数との差の絶対値を、第１の経路及び第２の経路を示す情報とともにメモリ等の記憶手段に保存する（ステップ３３）。ここで、ホップ数の差を用いる代わりに、パスの経路長の差を用いてもよい。その場合、パス収容設計装置１は、各リンクの経路長を格納する経路長格納手段を備え、パス経路決定部１３は、当該経路長格納手段を参照することにより、経路長を算出する。
【００６８】
ステップ３４にて、パス経路決定部１３は、全経路を探索したかどうかの判定を行う。ここでの判定は、第１の経路と第２の経路を合わせて全経路の抽出が完了したかどうかの判定としてよい。つまり、第１の経路が決定すれば、第２の経路は一意に決まるので、第１の経路の選択において、既に第２の経路として選択した経路は選択しないこととしてよい。
【００６９】
ステップ３４において、全経路の探索が終了していないと判定されれば、パス経路決定部１３は、ノード間接続情報格納部１７において、ステップ３２で削除した接続関係を元に戻して、ステップ３１に戻り、別経路の探索を行う。この作業を全経路に対して行う。
【００７０】
全経路の探索が終了した後、パス経路決定部１３は、第１の経路のホップ数と、第２の経路のホップ数との差の絶対値が最小となる経路の組（第１の経路と第２の経路）を選択し、それを第１の経路及び第２の経路として決定する（ステップ３５）。これにより、一方の経路が、他方の経路よりも大幅に長距離となってしまうといった問題を解消でき、両方の経路を再生中継器なしで伝送できる可能性を高めることができる。
【００７１】
続いて、第２の実施の形態と同様にして波長設計がなされる（ステップ３６）。
【００７２】
上記のように、本実施の形態では、第１の経路を全経路探索により探索し、第２の経路を、第１の経路と重ならない経路として決定し、探索により求められる第１の経路と第２の経路の組み合わせ群の中で、第１の経路と第２の経路のホップ数の差、及び第１の経路と第２の経路距離の差のうちのいずれか一方又は両方が最小となる第１の経路と第２の経路の組み合わせを、パスの２つの経路として決定している。本実施の形態でも、各リング内で、時計周り方向及び反時計回り方向に２つの経路が選択される。
［第４の実施の形態］
次に、本発明の第４の実施の形態を、図１８に示すフローチャートに沿って説明する。第４の実施の形態においては、まず、第１の実施の形態と同様にして、パス通過リング網決定部１２が、通過リング網の経路の決定、及びノード接続関係の変更処理を行う（図６、図９のステップ５までの処理）。以下で説明する処理の前の時点で、ノード間接続情報格納部１７には、図１１〜図１３に示した情報が格納されている。
【００７３】
図１８のステップ４１において、パス経路決定部１３は、ノード間接続情報格納部１７に格納された通過リング網のノード情報から、リング間を接続する各接続ノードの情報を取得する。第１の実施の形態で決定された通過リング網は１−４−５−６であるので、リング間接続ノードは１３４１、４２５５、５２６５となり（図１６参照）、パス経路決定部１３は、これらの情報を取得し、メモリ等の記憶手段に保持しておく。
【００７４】
続いて、パス経路決定部１３は、第１の経路の探索を行う（ステップ４２）。ステップ４２の中の処理においては、経路探索回数の識別子として変数Kが定義されており、第１の経路の探索が終了しているか否かの識別子として変数Lが定義されている。まず、パス経路決定部１３は、KとLをそれぞれ初期化し、０にする（ステップ１０１）。
【００７５】
続いて、パス経路決定部１３は、Kが偶数（０を含む）であれば、現在の着目ノード（最初は始点ノード）から、当該着目ノードが属するリング（探索が未実施のリング）のリング接続点ノードまでの最短経路（最短ホップ経路もしくは最短距離経路）を求める（ステップ１０２、１０３）。Kが奇数であれば、現在の着目ノードから、当該着目ノードが属するリングのリング接続点ノードまでの最長経路（最長ホップ経路もしくは最長距離経路）を求める（ステップ１０２、１０４）。
【００７６】
その後、パス経路決定部１３は、経路探索の対象となったリングの次のリング内に終点ノードがあるか否かの判定を行い（ステップ１０５）、終点ノードがあればステップ１０７に進み、終点ノードがなければステップ１０６に進む。ステップ１０６では、Kに１が加算され、ステップ１０２〜１０４において、前回のリング接続点ノードを着目ノードにして、次のリング接続点ノードまでの経路計算を行う。
【００７７】
ステップ１０７では、Kが偶数であれば、現在の着目ノードから、終点ノードまでの最長経路を求め（ステップ１０７、１０８）、Kが奇数であれば、現在の着目ノードから、終点ノードまでの最短経路を求める（ステップ１０７、１０９）。
【００７８】
つまり、ステップ４２の処理では、始点ノードから順番に接続点ノードまでの経路探索を行い、リング内の経路探索をするたびにK→K+1とし、K=2n(nは０以上の整数)の場合は最短経路探索を行い、K=2n+1のときは最長経路探索を行うように条件分岐を行う。終点ノードまでの経路探索においては、その前でKに１を加算せずに、K=2nの場合は最長経路探索を行い、K=2n+1のときは最短経路探索を行う。
【００７９】
上記の処理は、リングをまたぐ度に、最短と最長の経路探索を切り替えることに相当する。これにより、第1及び第2の経路の一方だけが長くなり伝送不可能となる場合を減らすことが可能となる。
【００８０】
具体的には、図１３に示す例において、まず、１５から１３４１までの最短経路探索を行い、次に１３４１から４２５５までの最長経路探索を行う。同様に４２５５から５２６５までの最短経路探索を行い、最後に５２６５から終点ノードの６３までの最長経路探索を行う。これによって第１の経路が決定する。
【００８１】
次に、パス経路決定部１３は、第２の経路の探索処理を行う（図１８のステップ４３）。ここでは、パス経路決定部１３は、Lが０か１かを判定し（ステップ１１０）、最初はL=０であることから、ステップ１１１に進み、LとKのそれぞれを１とする。その後は、Kの初期値を１としたステップ１０２からの処理が行われる。Kが１から始まるので、第２の経路の探索において、最短経路探索及び最長経路探索を交互に行う順番は、第１の経路探索のときと異なるものとなり、第２の経路として、第１の経路と重ならない経路を選択することが可能となる。ここで、パス経路決定部１３は、Lの値を参照することで、第１の経路か第２の経路のうちのどちらを計算しているのかを判断できる。
【００８２】
続いて、第２の実施の形態と同様にして波長設計がなされる（ステップ４４）。
【００８３】
上記のように、本実施の形態では、パスの始点ノードと、当該始点ノードが属するリング上のリング間接続点ノードとの間の最短経路を選択し、以降、終点ノードが属するリングまでの各リングにおいて、リング間接続点ノードを結ぶ最長経路と最短経路を、交互に順番に選択することにより、始点ノードから終点ノードまでの第１の経路を決定し、第１の経路と各リング内において逆方向で重ならない経路を第２の経路として決定している。本実施の形態でも、各リング内で、時計周り方向及び反時計回り方向に２つの経路が選択されている。
［第５の実施の形態］
次に、第５の実施の形態について説明する。本実施の形態は、第４の実施の形態で説明した図１８のステップ４２におけるステップ１０１において、Kの初期設定を１（K→1）とし、ステップ４３のステップ１１１においてＫ＝０とするものであり、他の処理は、図１８に示す処理と同じである。
【００８４】
つまり、第５の実施の形態は、第４の実施の形態で説明した第２の経路の探索手順を用いて第１の経路探索を行い、第４の実施の形態で説明した第１の経路の探索手順を用いて第２の経路探索を行うものである。これにより、第４の実施の形態と同様の効果を得ることが可能となる。
【００８５】
上記のように、本実施の形態では、パスの始点ノードと、当該始点ノードが属するリング上のリング間接続点ノードとの間の最長経路を選択し、以降、終点ノードが属するリングまでの各リングにおいて、リング間接続点ノードを結ぶ最短経路と最長経路を、交互に順番に選択することにより、始点ノードから終点ノードまでの第１の経路を決定し、第１の経路と各リング内において逆方向で重ならない経路を第２の経路として決定している。本実施の形態でも、各リング内で、時計周り方向及び反時計回り方向に２つの経路が選択されている。
［第６の実施の形態］
次に、本発明の第６の実施の形態を、図１９に示すフローチャートに沿って説明する。第６の実施の形態でも、まず、第１の実施の形態と同様にして、パス通過リング網決定部１２が、通過リング網の決定、及びノード接続関係の変更処理を行う（図６、図９のステップ５までの処理）。その後のステップ６１〜６５までの処理は、第３の実施の形態で説明した図１７のステップ３１〜３５までの処理と同じである。
【００８６】
本実施の形態では、以降の処理の前提として、予めパスの伝送可能距離と、伝送可能ホップ数（信号伝送に使用できる最大ホップ数）が計算され、その値がメモリ等の記憶手段に保持されているものとする。また、各リンクの伝送距離についても記憶手段に格納されているものとする。なお、伝送可能距離と伝送可能ホップ数の算出は既存技術を用いて行うことができ、例えば、非特許文献３や非特許文献４に記載された技術を用いて算出することができる。
【００８７】
ステップ６５における最小ホップ数差（もしくは経路数）の経路選択が終わった後、パス経路決定部１３は、選択された第１の経路のホップ数が最大ホップ数以下であるか否かを判断する（ステップ６６）。つまり、第１の経路が、最大ホップ数制約内に収まっているか否かの判断を行う。
【００８８】
ステップ６６において、制約内であると判定されればステップ６７に進み、そうでなければステップ６８へ進む。
【００８９】
ステップ６７において、パス経路決定部１３は、第１の経路の伝送距離が、予め算出した伝送可能距離以下であるか、すなわち、伝送可能距離範囲内に収まっているかの否かの判定を行う。ステップ６７で伝送可能距離の範囲内に収まっていると判定されればステップ７０へ進み、そうでなければステップ６８へ進む。
【００９０】
ステップ６８では、パス経路決定部１３は、第２の実施の形態において図１４を参照して説明した処理手順を用いて、第１の経路の最短経路を探索する（図１４のステップ２１）。そして、パス経路決定部１３は、ステップ６９にて、第２の実施の形態と同様にして第２の経路を決定する（図１４のステップ２２）。つまり、第１の経路と各リング内において逆方向で重ならない経路を第２の経路として決定する。
【００９１】
その後、ステップ７０において、第２の実施の形態のステップ２３と同様にして波長設計が実行される。
［第７の実施の形態］
次に、第７の実施の形態について、図２０を参照して説明する。第７の実施の形態は、まず、図１８を参照して説明した第４の実施の形態と同様にして、第１の経路と第２の経路を決定し、その後、第６の実施の形態の図１９におけるステップ６６〜ステップ７０と同様にして、伝送制約を考慮した経路決定を行う形態である。
【００９２】
図２０に示す第７の実施の形態の処理フローにおいて、ステップ７１〜７３にて、第４の実施の形態における図１８のステップ４１〜４３と同じ処理が行われ、ステップ７４〜７８にて、第６の実施の形態の図１９におけるステップ６６〜ステップ７０と同じ処理が行われる。
［第８の実施の形態］
次に、第８の実施の形態について説明する。
【００９３】
本実施の形態においては、８つのサービスクラスを考慮した場合のパス収容設計方法を示す。サービスクラスは、伝送品質と、信頼性のどちらかもしくは両方によって定められるものであり、例えばクライアントの要望によって決められる。サービスクラスに応じて、パスの経路決定やパス設定のための処理方法が決定される。一般に、上位のサービスクラスになるほど伝送品質及び信頼性が高くなる。
【００９４】
このような処理を実現するには、例えば、各サービスクラスに対応した処理を実行するためのプログラムを、サービスクラスに対応付けてパス収容設計装置１の記憶手段に格納しておき、あるサービスクラスがパス収容設計装置１に入力された場合に、パス収容設計装置１が、入力されたサービスクラスに対応するプログラムを実行するようにすればよい。また、パス収容設計装置１が、サービスクラスのそれぞれに対応する処理手段を備え、サービスクラスの入力を受け、当該サービスクラスに対応した処理手段により、当該当該サービスクラスに対応した処理を行うようにしてもよい。
【００９５】
本実施の形態における１番目のサービスクラスでは、第１の経路を最短経路で設計し、第２の経路はそれと重ならないように設計する。このサービスクラスに対しては、第２の実施の形態におけるアルゴリズムを用いることができる。また、このサービスクラスでは、２つの経路で信号伝送を行うこととしてよい。つまり、２つの経路にパスが収容してよい。
【００９６】
２番目のサービスクラスに対しては、第３〜第６の実施の形態で説明したアルゴリズムのうちのいずれかのアルゴリズムが適用される。
【００９７】
３番目のサービスクラスでは、第１の経路を最短経路で設計し、第２の経路に関しては第１経路と重ならないように設計して経路を確保しておき、第１の経路の故障時に、第２の経路にパスを収容する（信号伝送を行えるようにする）方法を適用するものである。３番目のサービスクラスに対しては、パス収容設計において、第２の実施の形態におけるアルゴリズムを用いることができる。ただし、第２の経路へのパスの収容は、第１の経路の故障時のみとし、当該サービスクラスのクライアントのパスの経路及び波長の情報（第２の経路へのパスの収容のために用いる情報等）はパス収容設計装置１、もしくはその他の管理装置に保存しておく。
【００９８】
第２の経路へのパスの収容に当たっては、第２の経路上の各ノード装置に対して、パスの信号の伝送を行えるようにするための設定が必要であるが、このような設定は、例えば、パス収容設計装置１のパス制御部１５が行う。もしくは、上記の管理装置が行ってもよい。ここでの設定に、上記の経路及び波長の情報が用いられる。上記管理装置は、波長と経路を選択し設定する装置であり、例えば、NMS(Network Management System)、NRM(Network Resource Manager)、PCE(Path computation Element)、EMS(Element Management System)等が該当する。また、パス収容設計装置１の機能を、当該管理装置の中に備えてもよい。
【００９９】
４番目のサービスクラスでは、第３〜６の実施の形態におけるパス収容設計アルゴリズムを適用することにより、第１の経路を設計し、第２の経路に関しては第１の経路と重ならないように設計し経路を確保しておき、第１の経路の故障時に第２の経路にパスを収容する。ただし、第２の経路へのパス収容は第１の経路の故障時のみとし、こちらのサービスクラスのクライアントの経路及び波長は管理装置に保存しておく。
【０１００】
５番目のサービスクラスでは、第２の実施の形態におけるパス収容設計アルゴリズムを用いることにより、第１の経路を最短経路で設計し、第２の経路に関しては第１の経路と重ならないように設計し経路を確保しておき、確保した第２の経路は、本サービスクラスと次の６番目のサービスクラスの第２の経路としても使用するものとし、第１の経路の故障時に当該第２の経路にパスを収容する。第２の経路へのパス収容は第１の経路の故障時のみとし、こちらのサービスクラスのクライアントの経路及び波長は管理装置に保存しておく。
【０１０１】
６番目のサービスクラスでは、第３〜６の実施の形態におけるパス収容設計アルゴリズムを適用して、第１の経路を設計し、第２の経路に関しては第１の経路と重ならないように設計し経路を確保しておき、確保した第２の経路は、本サービスクラスと前の５番目のサービスクラスの第２の経路としても使用するものとし、第１の経路の故障時に当該第２の経路にパスを収容する。第２の経路へのパス収容は第１の経路の故障時のみとし、こちらのサービスクラスのクライアントの経路及び波長は管理装置に保存しておく。
【０１０２】
７番目のサービスクラスでは、第１の経路を最短経路で設計し、第２の経路は第１の経路の故障時に設計を行ない、当該第２の経路にパスを収容する。ここでは第２の実施の形態における第２の経路の探索を省いたパス収容設計アルゴリズムを用いる。
【０１０３】
８番目のサービスクラスは、第１の経路を最短経路で設計し、第２の経路の設計を行わない方法であって、ここでは、第２の実施の形態における第２の経路の探索を省いたパス収容設計アルゴリズムを用いる。
【０１０４】
すなわち、本実施の形態では、パス収容設計装置１に第１のサービスクラスが入力された場合に、当該パス収容設計装置１は、通過リング網上で、第１の経路を決定し、当該第１の経路と各リング内において逆方向で重ならない経路として第２の経路を決定し、第１の経路上で信号伝送が行われるパスの故障時に、当該パスを第２の経路に切り替える処理を行い、パス収容設計装置１に第２のサービスクラスが入力された場合に、当該パス収容設計装置１は、通過リング網上で、第１の経路を決定し、当該第１の経路と各リング内において逆方向で重ならない経路として第２の経路を決定し、第１の経路上で信号伝送が行われるパスの故障時に、当該パスを前記第２の経路に切り替える処理を行うが、この第２のサービスクラスにおける第２の経路は、第２のサービスクラスの別のパスの第２の経路として共有される経路である。
［第９の実施の形態］
次に、本発明の第９の実施の形態について説明する。本実施の形態は、図２１に示すように、始点ノードを有するリングと、終点ノードを有するリングとが、同一のリングに、それぞれ１つの接続点ノードを介して接続された網に適した形態である。このような網は、例えば、図２４を参照して説明したHierarchical self-healing ring網に相当する。
【０１０５】
図２１に示す網の形態では、始点ノードを有するリングＡと、終点ノードを有するリングＣとを接続する通過リング網はＡ−Ｂ−Ｃの１つだけなので、第１の実施の形態で説明した通過リング網を決定する処理を行う必要がない。
【０１０６】
よって、本実施の形態では、図１７を参照して説明した第３の実施の形態において、通過リング網の決定処理を除いた処理を行うことにより、第１の経路及び第２の経路の決定、及び波長設計を行う。すなわち、本実施の形態では、図１７に示すステップ３１〜ステップ３６の処理を行う。ステップ３１〜ステップ３６の処理を行うことにより、図２１に示す網において、第１の経路と第２の経路の経路長差を小さくすることができる。
【０１０７】
また、本実施の形態を適用できる網構成は、図２１に示すものに限られない。本実施の形態は、図２２に示す網構成にも適用できる。図２２の網構成では、始点ノードから終点ノードを結ぶ経路は、リング６、７、９を必ず経由する。従って、リング網６、７、９に関しては、通過リング網の決定を行う必要がないので、図２１で説明した場合と同様に、本実施の形態を適用できる。ただし、図２２に示すような例では、一般に、始点ノードと、リング６の接続点ノードとの間の経路、及び、終点ノードと、リング９の接続点ノードとの間の経路は、例えば他の実施の形態で説明した方法で求めておく必要がある。
【０１０８】
上記のように、本実施の形態では、第１の経路を全経路探索により探索し、第２の経路を、第１の経路と重ならない経路として決定するステップと、前記探索により求められる第１の経路と第２の経路の組み合わせ群の中で、第１の経路と第２の経路のホップ数の差、及び第１の経路と第２の経路距離の差のうちのいずれか一方又は両方が最小となる第１の経路と第２の経路の組み合わせを、パスの２つの経路として決定するステップと、を有するパス収容設計方法が提供される。
［第１０の実施の形態］
第１０の実施の形態は、第９の実施の形態と同様に、図２１や図２２に示した網構成に適した形態である。
【０１０９】
本実施の形態では、図１８を参照して説明した第４の実施の形態において、通過リング網の決定処理を除いた処理を行うことにより、第１の経路及び第２の経路の決定、及び波長設計を行う。すなわち、本実施の形態では、図１８に示すステップ４１〜ステップ４４の処理を行う。ステップ４１〜ステップ４４の処理を行うことにより、第１の経路と第２の経路の経路長差を小さくすることができる。
【０１１０】
つまり、本実施の形態では、パスの始点ノードと、当該始点ノードが属するリング上のリング間接続点ノードとの間の最短経路を選択し、以降、終点ノードが属するリングまでの各リングにおいて、リング間接続点ノードを結ぶ最長経路と最短経路を、交互に順番に選択することにより、始点ノードから終点ノードまでの前記第１の経路を決定するステップと、第１の経路と各リング内において逆方向で重ならない経路を前記第２の経路として決定するステップと、を有するパス収容設計方法が提供される。
［第１１の実施の形態］
第１１の実施の形態も、第９の実施の形態と同様に、図２１や図２２に示した網構成に適した形態である。
【０１１１】
本実施の形態では、図１８を参照して説明した第５の実施の形態において、通過リング網の決定処理を除いた処理を行うことにより、第１の経路及び第２の経路の決定、及び波長設計を行う。すなわち、本実施の形態では、図１８に示すステップ４１〜ステップ４４の処理を行う。ただし、第５の実施の形態で説明したように、Ｋの値が第１０の実施の形態と異なる。本実施の形態でも、第１の経路と第２の経路の経路長差を小さくすることができる。
【０１１２】
すなわち、本実施の形態によれば、パスの始点ノードと、当該始点ノードが属するリング上のリング間接続点ノードとの間の最長経路を選択し、以降、終点ノードが属するリングまでの各リングにおいて、リング間接続点ノードを結ぶ最短経路と最長経路を、交互に順番に選択することにより、始点ノードから終点ノードまでの前記第１の経路を決定するステップと、第１の経路と各リング内において逆方向で重ならない経路を前記第２の経路として決定するステップと、を有するパス収容設計方法が提供される。
［第１２の実施の形態］
第１２の実施の形態も、第９の実施の形態と同様に、図２１や図２２に示した網構成に適した形態である。
【０１１３】
本実施の形態では、図１９、図２０を参照して説明した第６及び第７の実施の形態において、通過リング網の決定処理を除いた処理を行うことにより、第１の経路及び第２の経路の決定、及び波長設計を行う。すなわち、本実施の形態では、図１９に示すステップ６１〜ステップ７０、もしくは、図２０に示すステップ７１〜７８の処理を行う。これらの処理を行うことにより、第１の経路と第２の経路の経路長差を小さくすることができるとともに、ホップ数や伝送距離の制約を満たした経路を決定できる。
【０１１４】
すなわち、本実施の形態では、第１の経路の伝送距離もしくはホップ数が、予め算出した伝送可能距離もしくは予め算出した伝送可能ホップ数を越えるか否かの判定を行い、越える場合に、第１の経路を、始点ノードと終点ノード間の最短経路とするステップと、第１の経路と各リング内において逆方向で重ならない経路を第２の経路として決定するステップと、を有するパス収容設計方法が提供される。
【０１１５】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１１６】
１  パス収容設計装置
１１  入出力部
１２  パス通過リング網決定部
１３  パス経路決定部
１４  波長設計部
１５  パス制御部
１６  リング間接続情報格納部
１７  ノード間接続情報格納部
１８  リソース情報格納部
１９  ノード数情報格納部
２０  波長情報格納部
【図１】
0005419740.tif 000002
【図２】
0005419740.tif 000003
【図３】
0005419740.tif 000004
【図４】
0005419740.tif 000005
【図５】
0005419740.tif 000006
【図６】
0005419740.tif 000007
【図７】
0005419740.tif 000008
【図８】
0005419740.tif 000009
【図９】
0005419740.tif 000010
【図１０】
0005419740.tif 000011
【図１１】
0005419740.tif 000012
【図１２】
0005419740.tif 000013
【図１３】
0005419740.tif 000014
【図１４】
0005419740.tif 000015
【図１５】
0005419740.tif 000016
【図１６】
0005419740.tif 000017
【図１７】
0005419740.tif 000018
【図１８】
0005419740.tif 000019
【図１９】
0005419740.tif 000020
【図２０】
0005419740.tif 000021
【図２１】
0005419740.tif 000022
【図２２】
0005419740.tif 000023
【図２３】
0005419740.tif 000024
【図２４】
0005419740.tif 000025