ネットワーク設計装置、ネットワーク設計プログラム及びネットワーク設計方法

【課題】各波長パスに要する光再生中継器の数を考慮しながら光伝送装置や光再生中継器の配置に要する総コストを低減できるネットワーク設計方法を提供する。
【解決手段】ネットワーク設計装置１００は、光ネットワーク情報を取得する情報取得部１２０と、光ネットワークを線形区間に分割する区間分割部１２１と、各線形区間内に配置する光伝送装置の組み合わせ候補を決定する組み合わせ候補決定部１２５、１２７、１２８と、各波長パス上で許される雑音量上限値を決定する雑音量上限値決定部１２３と、光伝送装置及び各波長パスに対する光再生中継器のコストの合計を最小にする目的関数、組み合わせ候補から線形区間毎に光伝送装置の組み合わせを１つ選択する制約条件、並びに各波長パスに必要な光再生中継器数の条件をこの波長パスの累積雑音量と雑音量上限値とにより定める制約条件を有する整数計画問題を解く装置配置部１２９と、を備える。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、光ネットワークシステムを構成する各光伝送装置を局舎に配置するネットワーク設計装置、ネットワーク設計プログラム及びネットワーク設計方法に関する。
【背景技術】
【０００２】
近年、ＷＤＭ（Wavelength Division Multiplexing：波長分割多重）ネットワークの分野においては、光信号のまま波長単位でトラフィックを分岐及び挿入し、及び経路の切り替えができるＯＡＤＭ（Optical Add Drop Multiplexer:光分岐挿入）装置や、たとえばＷＸＣ（Wavelength Cross Connect: 波長クロスコネクト）装置といった光ハブ装置が実現された。
これらの装置の実現によって、相互接続リングネットワークやメッシュネットワーク等の複雑なネットワークが構成可能となった。このように複雑化したネットワークにて伝送される光信号の雑音値やペナルティ値の設計及び光伝送装置の配置の最適化設計に対する要求が高まっている。
【０００３】
ＷＤＭネットワークを設計する場合には、一般に、ＷＤＭシステムを構成する装置を配置可能な局舎に関する情報と局舎間を接続する光ファイバに関する情報とを含む光ネットワーク情報、およびＷＤＭネットワークで伝送される波長パスに関する波長パス情報が与えられる。以下、ＷＤＭシステムを構成する光伝送装置のことを「ＷＤＭ装置」と記載することがある。ＷＤＭ装置は、たとえばＯＡＤＭ装置やＩＬＡ（In-Line Amplifier：光増幅中継器）又は後述のバイパスなどを含む。
【０００４】
波長パスの始点及び終点になる局舎にはＯＡＤＭ装置が配置され、その一方で他の局舎である中継局舎には、中継装置として使用するＯＡＤＭ装置や、ＩＬＡを配置することができる。ＯＡＤＭ装置を中継装置として使用することにより、中継局舎において任意の波長パスを再生中継したり、ＷＤＭ信号のチルト補償を行うことが可能となる。
また、中継局舎にＯＡＤＭ装置やＩＬＡを配置せずに光ファイバを単純接続するだけという運用も可能である。このように光ファイバが単純接続される局舎を、以下の説明において「バイパス局舎」と示すことがあり、また光ファイバを単純接続する中継手段のことを「バイパス」と示すことがある。
【０００５】
一般に、局舎に配置するＷＤＭ装置のコストとこの局舎を経由するＷＤＭ信号の伝送品質とはトレードオフの関係にある。すなわちコストの高いＷＤＭ装置が配置されるとＷＤＭ信号の伝送品質が向上する。このため光ネットワーク上を伝送される各波長パスに必要な光再生中継器の数が減少する。一方で、コストが低いＷＤＭ装置の配置数を増やすと光再生中継器の数が増加する。
したがって、ＷＤＭ装置と光再生中継器のコストの総和、すなわちネットワークを敷設する際の所要コストを最小化するネットワーク設計が必要とされる。
【０００６】
従来のＷＤＭ装置の配置方法における具体的な手順は以下の通りである。
（１）ネットワークを、直線状或いはリング状のトポロジーを有する複数のサブネットワークへ分割する。
（２）各サブネットワーク毎にＷＤＭ装置のコストが最小となる配置を決定する。
【０００７】
上述のとおり設計されたＷＤＭネットワークではＷＤＭ装置の総コストが最小となる。
【０００８】
なお、専用の迂回用光パスを設けず、障害が発生した光パスに流れていたトラヒックを他の現用光パスを用いて迂回させるように、整数計画法を用いて光ネットワークを設計する光ネットワークの設計法が提案されている。
また、複数の光伝送リンクが１つの光伝送装置を共用する光ネットワークにおいて、ネットワークコストを最小化する現用光パスと予備光パスの配備を、整数計画法を用いて決定する光ネットワーク設計法が提案されている。
【０００９】
【特許文献１】特開２００２−３７４２８３号公報
【特許文献２】特開２００６−６７０６７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかし、上述した従来のＷＤＭ装置の配置方法によると、複数のサブネットワークにわたって経路が存在する波長パスが存在するとき、このような波長パスに対しても常にＷＤＭ装置が最適に配置されるわけではなく、ＷＤＭ信号の品質劣化を補償するために光再生中継器の数を増やす必要がある。すなわち、従来のＷＤＭ装置の配置方法により決定した配置は、波長パスの分布状況によっては、ネットワーク全体の所要コストを最小にする配置にならない場合がある。
【００１１】
ネットワーク全体の所要コストを最小にするように各局舎へ配置されるＷＤＭ装置の組み合わせを決定するには、各組み合わせについて、各波長パス毎に光再生中継器の必要数を適切に見積もる必要がある。しかし、この見積もりを適切に行うためには、ＯＳＮＲ（Optical Signal Noise Ratio：光信号対雑音比）に加え、ＰＭＤ（Polarization Mode Dispersion：偏波モード分散）値やクロストーク値の影響といった伝送ペナルティが必要となる場合がある。ＯＳＮＲや伝送ペナルティの値も、ＷＤＭ装置の上記の組み合わせに依存するため、従来は、正確な光再生中継器数の見積もりが困難であった。
なお、ネットワーク中の各局舎へそれぞれ配置されるＷＤＭ装置の組み合わせ、すなわち各局舎へそれぞれＷＤＭ装置が配置された配置状態を「ＷＤＭ装置構成」と示すことがある。
【００１２】
一般に、ある局舎で受信した光信号について以下の式で与えられる受信ＯＳＮＲが、光信号の信号種類に応じて定まる所定のＯＳＮＲ耐力以上のときには、その光信号をその局舎へ伝送すること若しくはその局舎で受信することが可能である。
受信ＯＳＮＲ＝ＯＳＮＲ−伝送ペナルティ
一方で、受信ＯＳＮＲがＯＳＮＲ耐力よりも小さいときは、伝送もしくは受信することができなくなるため、その光信号を伝送する前に光再生中継器により再生する必要がある。なお、ＯＳＮＲの逆数である単位光パワー当たりの雑音量ＮＯＩＳＥは線形値であり、あるＯＳＮＲ［dB］が与えられると、
ＮＯＩＳＥ＝１０^-(OSNR/10)
により表される。
【００１３】
伝送ペナルティを考慮しない場合には、比較的容易に雑音量から光再生中継器の所要数を見積もることが可能であるが、伝送ペナルティを考慮したより精度が高い光再生中継器の所要数の見積もりは従来困難であった。
開示のネットワーク設計装置、ネットワーク設計プログラム及びネットワーク設計方法は、上記の問題点を解消するものであり、光ネットワークにおいて、光伝送装置と各波長パスに必要となる光再生中継器とを合わせた設置コストの総額を最適化したネットワーク設計を実現することを目的とする。
または、開示のネットワーク設計装置、ネットワーク設計プログラム及びネットワーク設計方法は、各波長パス毎に必要な光再生中継器の数を考慮しつつ、光伝送装置の配置を決定することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するために、開示のネットワーク設計装置、ネットワーク設計プログラム及びネットワーク設計方法は、光ネットワークを線形区間に分割し、各線形区間内に配置される光伝送装置の種類の組み合わせ候補を決定し、各波長パス上で許される雑音量上限値を決定し、光ネットワークに配置される光伝送装置のコスト及び各波長パス毎に必要な数の光再生中継器に要するコストの合計を最小にする目的関数、線形区間毎に組み合わせ候補から光伝送装置の種類の組み合わせを１つずつ選択する制約条件、並びに各波長パスに必要な光再生中継器数の条件をその波長パス上で生じる累積雑音量とその波長パスの雑音量上限値とにより定める制約条件を有する整数計画問題を解くことにより、各線形区間内に配置される光伝送装置を決定する。
【発明の効果】
【００１５】
開示のネットワーク設計装置、ネットワーク設計プログラム及びネットワーク設計方法により、光伝送装置と光再生中継器の配置に要する総コストを低減できるネットワーク設計が可能となる。また、各波長パスに要する光再生中継器の数を考慮したネットワーク設計が可能となる。
【発明を実施するための最良の形態】
【００１６】
以下、添付する図面を参照して実施例を説明する。図１は、設計対象となる光ネットワークを示す図である。図１に示す光ネットワーク２００は、ＷＤＭシステムを構成するメッシュネットワークである。四角印は、光挿入分岐装置が配置される局舎を示している。光分岐挿入装置が配置される局舎は、たとえば波長パスの終端がある局舎である。丸印は、四角印にて示される局舎間でＷＤＭ光信号を中継する局舎を示している。点線両矢印は、光ネットワーク２００における線形区間を示している。
【００１７】
開示のネットワーク設計装置は、ネットワーク２００における各線形区間を単位設計区間として、各単位設計区間の線形ネットワーク中の各局舎に配置される光伝送装置の組み合わせを決定する。
ネットワーク中の各局舎へそれぞれ配置される光伝送装置の組み合わせ、すなわち、これら各局舎への光伝送装置の配置のあり方やあり様のことを「光伝送装置構成」と示すことがある。
【００１８】
点線矢印に示すように、線形区間は２つ以上の局舎が縦続に接続されることによって形成される区間であり、物理的に線形ではなく曲線的に接続されてもかまわない。たとえば線形区間２０２は局舎１〜４が縦続に接続されることによって形成され、線形区間２０３は局舎４〜６が縦続に接続されることによって形成され、線形区間２０４は局舎１１〜１８が縦続に接続されることによって形成されている。
線形区間２０２の始点及び終点である局舎１及び４、線形区間２０３の始点及び終点である局舎４及び６、線形区間２０４の始点及び終点である局舎１１及び１８には、光再生中継器を配置することができる光伝送装置が配置される。
【００１９】
一点鎖線の矢印２０１で示される区間は、ネットワーク２００上で伝送されるある波長パスの経路ｄが通過する区間を示す。波長パスｄの始点及び終点はそれぞれ局舎１及び６であり、波長パスｄの経路は、複数の線形区間２０２及び２０３に亘っている。
【００２０】
図２は、各局舎に配置可能な光伝送装置の種類の一例を示す図である。図２の表３００に示すように、各局舎に配置可能な光伝送装置の種類には、たとえばＯＡＤＭ３１０と、ＩＬＡ３２０と、バイパス３３０と、がある。ＯＡＤＭ３１０は、任意の波長信号に対して光再生中継器を配置可能な光伝送装置である。光再生中継器は、リアンプリフィケーション（Re Amplification）、リシェイピング（Re Shaping）及びリタイミング（Re Timing）を意味する３Ｒを行うことができる。
【００２１】
ＩＬＡ３２０およびバイパス３３０は、光再生中継器を配置することができない光伝送装置である。ＩＬＡ３２０は、光信号を増幅するリアンプリフィケーションを意味する１Ｒのみを行うことができる。バイパス３３０は、光信号を通過させるのみの構成である。一般に、これら光伝送装置の設置に要するコストは、ＯＡＤＭ３１０を配置するコストが最も高く、バイパス３３０を配置するコストが最も低く、ＩＬＡ３２０を配置するコストは前二者の間である。
【００２２】
一方、伝送品質については、バイパス３３０を配置した場合の伝送品質が最も悪く、ＯＡＤＭ３１０を配置した場合の伝送品質が最も良く、ＩＬＡ３２０を配置した場合の伝送品質は前二者の間である。したがって、原則として光伝送装置の設置に要するコストと伝送品質の間にはトレードオフの関係がある。
【００２３】
図３は、図２に示すＯＡＤＭの一例を示すブロック図である。図３に示すようにＯＡＤＭ４００は、増幅器４０１と、分岐部４０２と、多重分離部４０３と、光再生中継器４０４及び４０５と、多重化部４０６と、ＷＳＳ４０７と、増幅器４０８を備えている。増幅器４０１は、ＯＡＤＭ４００の外部から入力されたＷＤＭ光信号を増幅して分岐部４０２へ出力する。光再生中継器４０４は、必要に応じて、入力されたＷＤＭ光信号に含まれる波長パスのうち再生中継が必要な波長パスに対して設けられる。
【００２４】
分岐部４０２は、増幅器４０１から出力されたＷＤＭ光信号を分岐して、分岐した各ＷＤＭ光信号を多重分離部４０３及びＷＳＳ４０７へ出力する。多重分離部４０３は、分岐部４０２から出力されたＷＤＭ光信号を波長多重分離して、波長多重分離した各光信号をそれぞれ光再生中継器４０４及び４０５へ出力する。
【００２５】
光再生中継器４０４及び４０５は、多重分離部４０３から出力された光信号を再生して多重化部４０６へ出力する。多重化部４０６は、光再生中継器４０４及び４０５からそれぞれ出力された各光信号を波長多重して、波長多重されたＷＤＭ光信号をＷＳＳ４０７へ出力する。
【００２６】
ＷＳＳ４０７（Wavelength Selective Switch:波長選択スイッチ）は、分岐部４０２から出力されたＷＤＭ光信号に含まれる各光信号と、多重化部４０６から出力されたＷＤＭ光信号に含まれる各光信号と、を選択及び合波して、選択及び合波により得られたＷＤＭ光信号を増幅器４０８へ出力する。またＷＳＳ４０７は、増幅器４０８へ出力するＷＤＭ光信号のレベル等化を行う機能も有する。増幅器４０８は、ＷＳＳ４０７から出力されたＷＤＭ光信号を増幅してＯＡＤＭ４００の外部へ出力する。
【００２７】
図４は、図２に示すＩＬＡの一例を示すブロック図である。図４に示すようにＩＬＡ５００は、増幅器５０１と、ＶＡＴ５０２と、増幅器５０３を、を備えている。ＩＬＡ５００は、入力されたＷＤＭ光信号に含まれる各光信号をまとめて増幅する。増幅器５０１には、ＩＬＡ５００の外部からＷＤＭ光信号が入力される。増幅器５０１は、外部から入力されたＷＤＭ光信号を増幅してＶＡＴ５０２へ出力する。
【００２８】
ＶＡＴ５０２（Variable Attenuator：光可変減衰器）は、増幅器５０１から出力されたＷＤＭ光信号を可変の減衰量によって減衰させることで、増幅器５０１から出力されたＷＤＭ光信号のパワーを制御する。ＶＡＴ５０２は、パワーを制御したＷＤＭ光信号を増幅器５０３へ出力する。増幅器５０３は、ＶＡＴ５０２から出力されたＷＤＭ光信号を増幅してＩＬＡ５００の外部へ出力する。
【００２９】
図５は、図２に示すバイパスの一例を示すブロック図である。図５に示すように、バイパス６００には、外部からＷＤＭ光信号が入力される。バイパス６００は、ＷＤＭ光信号が入力された光ファイバの出力端を、出力用の光ファイバの入力端に接続するコネクタ部６０１を備えている。これにより、バイパス６００へ入力されたＷＤＭ光信号は、コネクタ部６０１を介して、そのままバイパス６００の外部へ出力される。
なお、図３から図５では、図中左から右への１方路のみ示しているが、実際には同じ装置内に反対方向の方路のための同一の系がもう１つ存在する。
【００３０】
図６は、ＣＰＵを用いて開示のネットワーク設計装置を実現した場合のハードウエア構成図である。ネットワーク設計装置１００は、ＣＰＵ１０１と、メモリ１０２と、ユーザからの操作やデータ入力を受け付けるキーボードやマウスなどであるユーザインタフェース１０３と、ディスプレイ装置などである表示部１０４と、ハードディスク１０５と、データ入力部１０６と、データ出力部１０７を備える。
【００３１】
データ入力部１０６は、たとえばＣＤ−ＲＯＭドライブ装置やＤＶＤ−ＲＯＭドライブ装置であってよい。またデータ入力部１０６及びデータ出力部１０７は、フレキシブルディスクドライブ装置、たとえばＣＤ−Ｒドライブ装置や、ＤＶＤ−Ｒドライブ装置、ＭＯドライブ装置のようなリムーバブルディスクドライブ装置や、フラッシュメモリ装置へのアクセス装置又はネットワークインタフェース装置であってよい。
【００３２】
データ入力部１０６は、後述する、ネットワーク設計装置１００による光ネットワークの設計の処理に必要なＷＤＭ光ネットワーク情報を、ネットワーク設計装置１００に入力するために使用される。
データ出力部１０７は、ネットワーク設計装置１００による光ネットワークの設計の処理によって生成された設計データを出力するために使用される。
【００３３】
ハードディスク１０５には、オペレーティングシステム（ＯＳ）１１０と、データ入力部１０６を介してインストールされたネットワーク設計プログラム１１２と、データ入力部１０６を介して入力されたＷＤＭ光ネットワーク情報１１３、各単位設計区間について後述するように生成された光伝送装置構成の候補を示すデータである装置構成候補データ１１４が格納される。
【００３４】
図７は、図６に示すＣＰＵ１０１がネットワーク設計プログラム１１２を実行することにより実現されるネットワーク設計装置１００のブロック図である。
図示するとおりネットワーク設計装置１００は、情報取得部１２０、区間分割部１２１、パラメータ決定部１２３、装置構成決定部１２４、記憶部１２６、光再生中継器配置決定部１１５及び設計データ出力部１１６を備える。
なお、本実施例では、ＣＰＵ１０１によるソフトウエア処理によってネットワーク設計装置１００が実現される。しかし、ネットワーク設計装置１００は、専用のハードウエア回路によって実現されてもよい。すなわち上記の情報取得部１２０、区間分割部１２１、パラメータ決定部１２３、装置構成決定部１２４、光再生中継器配置決定部１１５及び設計データ出力部１１６の一部又は全部は、それぞれ専用のハードウエア回路によって実現されてもよい。
【００３５】
情報取得部１２０は、ＷＤＭ光ネットワーク情報を取得する。ＷＤＭ光ネットワーク情報は、ネットワークトポロジ情報、光伝送装置情報、スパン情報、波長パス情報を含む。
ネットワークトポロジ情報は、設計対象の光ネットワークを構成する局舎に関する情報や、各局舎間の接続の有無に関する情報を含む接続情報を含む。以下の説明において、ネットワーク設計装置１００は、図１に示す光ネットワーク２００を設計対象とすることとする。
光伝送装置情報は、各局舎に配置することができる光伝送装置の種類や機種に関する情報や、これらの光伝送装置の伝送路条件に関する情報や、各波長パスに用いる光再生中継器の機種に関する情報や、それらの装置の設置に要するコストに関する情報を含む。
光伝送装置の種類には、たとえばＯＡＤＭ装置やＩＬＡ装置、バイパスを含む。また、伝送条件は、各光伝送装置を経由する光信号に生じる雑音量や伝送ペナルティ値を含む。伝送ペナルティ値には、たとえばＰＭＤ値やクロストーク値を含む。
【００３６】
スパン情報は、隣接する局舎間を接続するファイバに依存する伝送路条件に関する情報を含む。伝送路条件は、たとえば隣接する局舎間を接続するファイバにより生じる雑音量や伝送ペナルティ値を含む。
波長パス情報は、光ネットワーク２００を経由する波長パスに関する情報である。波長パス情報は、各波長パスの本数や、信号種類、始点及び終点となる局舎を指定する始点情報及び終点情報、経由する局舎を指定する経路情報を含む。各波長パスの信号種類は、たとえばビットレートである。
【００３７】
区間分割部１２１は、ネットワークトポロジ情報によって与えられた光ネットワーク２００を、線形区間である単位設計区間に分割する。
パラメータ決定部１２３は、開示のネットワーク設計方法で使用される各パラメータを決定する。このようなパラメータには、たとえば光ネットワーク２００を経由する各波長パスに許容される雑音量上限値や伝送ペナルティ値の上限値が含まれる。これらパラメータの決定方法については後に説明する。
パラメータ決定部１２３は、特許請求の範囲に記載された雑音量上限値決定部に相当する。
【００３８】
装置構成決定部１２４は、区間分割部１２１によって生成された各単位設計区間における光伝送装置構成の候補を決定する。装置構成決定部１２４は、光伝送装置構成の候補のうちから各単位設計区間毎に光伝送装置構成を１つずつ選択することによって、光ネットワーク２００の光伝送装置構成を決定する。
【００３９】
光再生中継器配置決定部１１５は、装置構成決定部１２４によって決定された光伝送装置構成内への光再生中継器の配置を決定する。光再生中継器配置決定部１１５は、装置構成決定部１２４によって決定された光伝送装置構成のうちの、光再生中継器を配置可能な光伝送装置のそれぞれに対して、必要な光再生中継器の配置を決定することによって、光ネットワーク２００の光伝送装置構成及び光再生中継器の配置を定めた設計データを生成する。
設計データ出力部１１６は、装置構成決定部１２４によって決定された光伝送装置構成に関する情報と光再生中継器配置決定部１１５により決定された光再生中継器の配置に関する情報とを含む設計データを出力する。
【００４０】
第１の実施例において装置構成決定部１２４は、光ネットワーク２００の光伝送装置構成を決定する際に、光ネットワーク２００に配置される光伝送装置のコスト及び光ネットワーク２００上の波長パス毎に必要な数の光再生中継器に要するコストの合計を最小にする目的関数と、光伝送装置構成の候補の中から単位設計区間毎に１つずつ候補を選択するという制約条件と、並びに各波長パスに必要な光再生中継器数の条件を波長パス上で生じる累積雑音量と波長パスについて定めた雑音量上限値とにより定める制約条件と、を有する整数計画問題を解くことによって、光ネットワーク２００の光伝送装置構成を決定する。
【００４１】
すなわち装置構成決定部１２４は、次の式（１）により与えられる整数計画問題を解くことによって光ネットワーク２００の光伝送装置構成を決定する。
【００４２】
【数１】

【００４３】
整数計画問題（１）の式（１−１）は、光ネットワーク２００に配置される光伝送装置のコスト及び光ネットワーク２００上の波長パス毎に必要な数の光再生中継器に要するコストの合計を最小にする目的関数に相当する。
また、式（１−２）は、光伝送装置構成の候補の中から単位設計区間毎に１つずつ候補を選択するという制約条件に相当する。
式（１−３）は、各波長パスに必要な光再生中継器数の条件を、波長パス上で生じる累積雑音量と波長パスについて定めた雑音量上限値とにより定める制約条件に相当する。
【００４４】
式（１）において使用される各記号の意味は次のとおりである。
ｇ_h（ｈ＝１〜Ｐ）は、光ネットワーク２００を分割して得られたＰ個の単位設計区間を示す。
【００４５】
ｔ_iは、単位設計区間ｇ_hのいずれかについて決定された光伝送装置構成の候補を示す。光伝送装置構成の候補がＭ個決定されたとき、添字ｉは１、２…Ｍの値を有する。
ｓ_i（ｉ＝１〜Ｍ）は、光伝送装置構成ｔ_i（ｉ＝１〜Ｍ）が光ネットワーク２００の光伝送装置構成として選択されているか否かを示す２値変数である。光伝送装置構成ｔ_iが光ネットワーク２００の光伝送装置構成として選択されているときｓ_i＝１であり、それ以外の場合にはｓ_i＝０である。
【００４６】
ｄ_j（ｊ＝１〜Ｎ）は、光ネットワーク２００上に構成される各波長パスを示す。ｊは、１、２…Ｎの値を有する。すなわち光ネットワーク２００上に構成される波長パスｄ_jは全部でＮ個である。
ｘ_j（ｊ＝１〜Ｎ）は、各波長パスｄ_jに必要な光再生中継器の数を示す整数変数である。
【００４７】
ｃ（ｔ_i）は、光伝送装置構成ｔ_iの配置に要するコストを示す。
λ（ｄ_j）は、波長パスｄ_jの本数を示す。
ｒ（ｄ_j）は、波長パスｄ_jの光再生中継器の配置に要する中継器１個当たりのコストを示す。
【００４８】
Ｔ（ｇ_h，ｔ_i）は２値パラメータであり、光伝送装置構成ｔ_iが単位設計区間ｇ_hについて決定された光伝送装置構成の候補であるときＴ（ｇ_h，ｔ_i）＝１であり，それ以外のときはＴ（ｇ_h，ｔ_i）＝０である。
Ｎｔｈ（ｄ_j）は、波長パスｄ_jについてパラメータ決定部１２３が定めた、雑音量上限値である。Ｎｔｈ（ｄ_j）は、波長パス情報によって与えられた各波長パスｄ_jの信号種類に応じて定まるＯＳＮＲ耐力に相当する雑音量である。
【００４９】
ｎ（ｄ_j，ｓ₁，ｓ₂，…ｓ_M）は、２値変数ベクトル（ｓ₁，ｓ₂，…ｓ_M）によって指定される各単位設計区間内の光伝送装置構成の選択状態に応じて、波長パスｄ_jが経由する経路上に生じる累積雑音量であり、次の式（２）にて与えられる。
【００５０】
【数２】

【００５１】
式（２）において使用される各記号の意味は次のとおりである。
Ｒｅ（ｄ_j，ｔ_i）は２値パラメータであり、光伝送装置構成ｔ_iを候補とする単位設計区間ｇ_hを波長パスｄ_jが経由し、かつ単位設計区間ｇ_hについて予め定めた基準方向と波長パスｄ_jの伝送方向が同じである場合にＲｅ（ｄ_j，ｔ_i）＝０となり、それ以外の場合にＲｅ（ｄ_j，ｔ_i）＝１となる。
Ｉ（ｄ_j，ｔ_i）は２値パラメータであり、光伝送装置構成ｔ_iを候補とする単位設計区間ｇ_hを波長パスｄ_jが経由する場合にＩ（ｄ_j，ｔ_i）＝１となり、それ以外の場合にＩ（ｄ_j，ｔ_i）＝０となる。
【００５２】
ｎｆ（ｔ_i）は、光伝送装置構成ｔ_iを候補とする単位設計区間ｇ_hの光伝送装置構成としてｔ_iが選択された場合に、この単位設計区間ｇ_hを上記の基準方向と同じ方向に伝送する際に波長パスに生じる雑音量を示す。
ｎｒ（ｔ_i）は、光伝送装置構成ｔ_iを候補とする単位設計区間ｇ_hの光伝送装置構成としてｔ_iが選択された場合に、この単位設計区間ｇ_hを上記の基準方向と反対方向に伝送する際に波長パスに生じる雑音量を示す。
ｎｆ（ｔ_i）及びｎｒ（ｔ_i）の値は、スパン情報によって与えられた、隣接局舎間に生じる光信号強度の伝送損失量と、光伝送装置情報によって与えられた、光伝送装置構成ｔ_iを構成する各光伝送装置を経由する光信号に生じる雑音量と、によって決定される。
【００５３】
第２の実施例において装置構成決定部１２４は、光ネットワーク２００の光伝送装置構成を決定する際に、式（１）によって与えられる整数計画問題に、各波長パスに必要な光再生中継器数の条件を、波長パス上で生じる伝送ペナルティの累積値と波長パスについて定めた伝送ペナルティの上限値とにより定める制約条件を加えた、以下の整数計画問題（３）を解くことによって、光ネットワーク２００の光伝送装置構成を決定する。
また、整数計画問題（１）において使用される雑音量上限値Ｎｔｈ（ｄ_j）の代わりに、伝送ペナルティを考慮した雑音量上限値Ｎｔｈ’（ｄ_j）を使用する。
【００５４】
【数３】

【００５５】
整数計画問題（３）の式（３−１）は、光ネットワーク２００に配置される光伝送装置のコスト及び光ネットワーク２００上の波長パス毎に必要な数の光再生中継器に要するコストの合計を最小にする目的関数に相当する。
また、式（３−２）は、光伝送装置構成の候補の中から単位設計区間毎に１つずつ候補を選択するという制約条件に相当する。
式（３−３）は、各波長パスに必要な光再生中継器数の条件を、波長パス上で生じる累積雑音量と波長パスについて定めた雑音量上限値とにより定める制約条件に相当する。
【００５６】
式（３−４１）、（３−４２）〜（３−４Ｒ）は、各波長パスに必要な光再生中継器数の条件を、波長パス上で生じる伝送ペナルティの累積値と波長パスについて定めた伝送ペナルティの上限値とにより定める制約条件に相当する。
考慮すべき伝送ペナルティの種類は複数であってもよい。たとえば伝送ペナルティとして、ＰＭＤ値とクロストーク値とからなる２種類の伝送ペナルティを考慮してもよい。制約条件（３−４１）、（３−４２）〜（３−４Ｒ）のうちｋ番目の制約条件（３−４ｋ）は、Ｒ個ある考慮すべき伝送ペナルティの種類のうちの、第ｋ番目の種類の伝送ペナルティついて定めた制約条件である。
【００５７】
式（３）において使用される各記号の意味を以下に説明する。なお、式（１）及び（２）に現れる項と同じ項には同じ記号を使用している。式（１）及び（２）に現れる記号と同じ記号については説明を省略する。
【００５８】
Ｐｔｈ_k（ｄ_j）は、波長パスｄ_jについてパラメータ決定部１２３が定めた、第ｋ番目の種類の伝送ペナルティの上限値である。Ｐｔｈ_k（ｄ_j）は、波長パス情報によって与えられた各波長パスｄ_jの信号種類に応じて一意に定まる値である。
ｐ_k（ｄ_j，ｓ₁，ｓ₂，…ｓ_M）は、２値変数ベクトル（ｓ₁，ｓ₂，…ｓ_M）によって指定される各単位設計区間内の光伝送装置構成の選択状態に応じて、波長パスｄ_jが経由する経路上に生じる、第ｋ番目の種類の伝送ペナルティの累積値であり、次の式（４）にて与えられる。
【００５９】
【数４】

【００６０】
ｐｆ_kj（ｔ_i）は、光伝送装置構成ｔ_iを候補とする単位設計区間ｇ_hの光伝送装置構成としてｔ_iが選択された場合に、この単位設計区間ｇ_hを上記の基準方向と同じ方向に伝送する際に、波長パスｄ_jの信号種類と同じ種類の波長パスに生じる、第ｋ番目の種類の伝送ペナルティ量を示す。
ｐｒ_kj（ｔ_i）は、光伝送装置構成ｔ_iを候補とする単位設計区間ｇ_hの光伝送装置構成としてｔ_iが選択された場合に、この単位設計区間ｇ_hを上記の基準方向と反対方向に伝送する際に、波長パスｄ_jの信号種類と同じ種類の波長パスに生じる、第ｋ番目の種類の伝送ペナルティ量を示す。
ｐｆ_kj（ｔ_i）及びｐｒ_kj（ｔ_i）の値は、波長パス情報によって与えられた各波長パスｄ_jの信号種類と、スパン情報によって与えられた、波長パスｄ_jの信号種類に対して隣接局舎間に生じる伝送ペナルティ量と、光伝送装置情報によって与えられた、光伝送装置構成ｔ_iを構成する各光伝送装置を経由する波長パスｄ_jの信号種類の光信号に生じる伝送ペナルティ量と、によって決定される、単位設計区間ごとに線形加算可能な値である。たとえば、偏波モード分散ＰＭＤの場合、経路上で発生するＴｏｔａｌＰＭＤ［ｐｓ］の２乗が線形加算可能なパラメータである。
【００６１】
Ｎｔｈ’（ｄ_j）は、波長パスｄ_jについての雑音量上限値である。パラメータ決定部１２３は、以下の３種類の決定方法のうちいずれか１つによって雑音量上限値Ｎｔｈ’（ｄ_j）を決定する。
【００６２】
（雑音量上限値Ｎｔｈ’（ｄ_j）の決定方法の第１例）
本決定方法では、パラメータ決定部１２３は、各種類毎の伝送ペナルティの上限値Ｐｔｈ_k（ｄ_j）と、各波長パスｄ_jの信号種類に応じて定まるＯＳＮＲ耐力とに基づいて雑音量上限値Ｎｔｈ’（ｄ_j）を決定する。
パラメータ決定部１２３は、ＯＳＮＲ耐力に、伝送ペナルティの上限値Ｐｔｈ_k（ｄ_j）から算出されるＯＳＮＲに対する劣化成分を加えて得られる次式（５）に示すＯＳＮＲ下限値を決定し、ＯＳＮＲ下限値に相当する雑音量を、雑音量上限値Ｎｔｈ’（ｄ_j）として決定する。式（５）において、f_kj(Ｐｔｈ_k（ｄ_j）)は、波長パスd_jに対する第ｋ番目の伝送ペナルティの上限値Ｐｔｈ_k（ｄ_j）から、第ｋ番目の種類の伝送ペナルティによる、ＯＳＮＲに対する劣化成分を算出する関数である。
【００６３】
【数５】

【００６４】
（雑音量上限値Ｎｔｈ’（ｄ_j）の決定方法の第２例）
本決定方法では、パラメータ決定部１２３は、ＯＳＮＲ耐力と、各種類毎の伝送ペナルティの上限値Ｐｔｈ_k（ｄ_j）と、各波長パスｄ_j上において取りうる各種類毎の伝送ペナルティの累積値の最大値Ｐｍａｘ_k（ｄ_j）とに基づいて雑音量上限値Ｎｔｈ’（ｄ_j）を決定する。
パラメータ決定部１２３は、上限値Ｐｔｈ_k（ｄ_j）及び最大値Ｐｍａｘ_k（ｄ_j）のうち小さい方から算出されるＯＮＳＲに対する劣化成分を、ＯＳＮＲ耐力に加えて得られる次式（６）に示すＯＳＮＲ下限値を決定し、ＯＳＮＲ下限値に相当する雑音量を雑音量上限値Ｎｔｈ’（ｄ_j）として決定する。
【００６５】
【数６】

【００６６】
（雑音量上限値Ｎｔｈ’（ｄ_j）の決定方法の第３例）
本決定方法では、パラメータ決定部１２３は、ＯＳＮＲ耐力と、各波長パスｄ_jについて見積もられた光再生中継器の必要最小数ＲＥＧｍｉｎ（ｄ_j）と、各種類毎の伝送ペナルティの上限値Ｐｔｈ_k（ｄ_j）と、各波長パスｄ_j上において取りうる各種類毎の伝送ペナルティの累積値の最大値Ｐｍａｘ_k（ｄ_j）とに基づいて雑音量上限値Ｎｔｈ’（ｄ_j）を決定する。
【００６７】
パラメータ決定部１２３は、各波長パスｄ_j上において取りうる伝送ペナルティの累積値の最小値Ｐｍｉｎ_k（ｄ_j）を伝送ペナルティの上限値Ｐｔｈ_k（ｄ_j）で除した数より小さく、かつ最大の整数値
【００６８】
【数７】

【００６９】
のうち、Ｒ種類ある伝送ペナルティの間で最大の値
【００７０】
【数８】

【００７１】
を各波長パスｄ_jについて見積もられた光再生中継器の必要最小数ＲＥＧｍｉｎ（ｄ_j）と、して決定する。
パラメータ決定部１２３は、光再生中継器の必要最小数ＲＥＧｍｉｎ（ｄ_j）に１を加えた値を、必要最小数の光再生中継器によって波長パスｄ_jを分割した区間数（ＲＥＧｍｉｎ（ｄ_j）＋１）と決定する。
【００７２】
パラメータ決定部１２３は、次の式（７）に示すように、各波長パスｄ_j上において取りうる伝送ペナルティの累積値の最大値Ｐｍａｘ_k（ｄ_j）を区間数（ＲＥＧｍｉｎ（ｄ_j）＋１）で除した値と、伝送ペナルティの上限値Ｐｔｈ_k（ｄ_j）のうち小さい方から算出されるＯＮＳＲに対する劣化成分を、ＯＳＮＲ耐力に加えることにより、ＯＳＮＲ下限値を決定する。パラメータ決定部１２３は、このＯＳＮＲ下限値に相当する雑音量を雑音量上限値Ｎｔｈ’（ｄ_j）として決定する。
【００７３】
【数９】

【００７４】
本決定方法によれば、光再生中継器で分割される最小数の区間に分配されたときの伝送ペナルティの各区間内の最大値が見積もられるため、より適切な雑音量上限値を見積もることができる。
【００７５】
たとえば、伝送ペナルティとして、偏波モード分散による伝送ペナルティＰＭＤと、クロストークによる伝送ペナルティＸＴとからなる２種類の伝送ペナルティを考慮すると仮定する。また、簡単のため、各伝送ペナルティ量［ｄＢ］が線形加算可能であり、f_kj(Ｐｔｈ_k（ｄ_j）)=Ｐｔｈ_k（ｄ_j）であると仮定する。
また、ある波長パスｄ_j上におけるＰＭＤの上限値が３［ｄＢ］であり、累積値の最大値が１［ｄＢ］であり、累積値の最小値が０［ｄＢ］であると仮定する。同様にこの波長パスｄ_j上におけるＸＴの上限値が２［ｄＢ］であり、累積値の最大値が５［ｄＢ］であり、累積値の最小値が４．５［ｄＢ］であると仮定する。
そして、波長パスｄ_jのＯＳＮＲ耐力が１６［ｄＢ］であると仮定する。
【００７６】
雑音量上限値Ｎｔｈ’（ｄ_j）の決定方法の第１例によれば、ＯＳＮＲ下限値は１６＋３＋２＝２１［ｄＢ］となり、２１［ｄＢ］であるＯＳＮＲ下限値に相当する雑音量が、雑音量上限値Ｎｔｈ’（ｄ_j）として決定される。
【００７７】
雑音量上限値Ｎｔｈ’（ｄ_j）の決定方法の第２例によれば、ＯＳＮＲ下限値は１６＋１＋２＝１９［ｄＢ］となり、１９［ｄＢ］であるＯＳＮＲ下限値に相当する雑音量が、雑音量上限値Ｎｔｈ’（ｄ_j）として決定される。
【００７８】
雑音量上限値Ｎｔｈ’（ｄ_j）の決定方法の第３例によれば、光再生中継器の必要最小数ＲＥＧｍｉｎ（ｄ_j）は、最小値の値がより大きいＸＴの最小値４．５［ｄＢ］と上限値２［ｄＢ］によって、ｉｎｔ（４．５／２）＝２個となる。これによって波長パスｄ_jは、再生中継器によって少なくとも３つの区間に分割される。
ＰＭＤ及びＸＴの最大値を３で除した値１／３及び５／３は、いずれもそれぞれの上限値よりも小さいため、ＯＳＮＲ下限値は１６＋１／３＋５／３＝１８［ｄＢ］となり、１８［ｄＢ］であるＯＳＮＲ下限値に相当する雑音量が、雑音量上限値Ｎｔｈ’（ｄ_j）として決定される。
【００７９】
なお、第１の実施例においても、上記のとおり第２の実施例の制約式（３−３）にて使用した雑音量上限値Ｎｔｈ’（ｄ_j）を、制約式（１−３）の雑音量上限値Ｎｔｈ（ｄ_j）の代わりに使用して、上記の制約式（１−３）を定めてもよい。
また、第２の実施例においても、上記のとおり第１の実施例の制約式（１−３）にて使用した雑音量上限値Ｎｔｈ（ｄ_j）を、制約式（３−３）の雑音量上限値Ｎｔｈ’（ｄ_j）の代わりに使用して、上記の制約式（３−３）を定めてもよい。
【００８０】
図７に示す装置構成決定部１２４は、次の手順により式（１）又は（３）により与えられる整数計画問題を解く。
（手順１）
式（１）又は（３）における２値変数ｓ_i（ｉ＝１〜Ｍ）及び整数変数ｘ_j（ｊ＝１〜Ｎ）を実数変数とした緩和問題を解くことによって、制約条件（１−２）及び（１−３）、又は制約条件（３−２）、（３−３）及び（３−４１）から（３−４Ｒ）に関する双対価格ベクトルを求める。
【００８１】
制約条件（１−２）及び（３−２）に関する双対価格ベクトルをπ_g＝（π_g1，π_g2…π_gP）と記す。
制約条件（１−３）及び（３−３）に関する双対価格ベクトルをπｎ＝（πｎ₁，πｎ₂…πｎ_N）と記す。
制約条件（３−４ｋ）に関する双対価格ベクトルをπｐ_k＝（πｐ_k1，πｐ_k2…πｐ_kN）と記す（ｋ＝１〜Ｒ）。
【００８２】
（手順２）
装置構成決定部１２４は、双対価格ベクトルの値に基づいて決定された被約費用の算出式にしたがって、各単位設計区間について、被約費用の値が負となる新たな光伝送装置構成の候補ｔ’を探索する。
式（１）により与えられる整数計画問題を解く場合には、光伝送装置構成の候補ｔ’についての被約費用ＲＣ（ｔ’）は、次の式（８）により与えられる。
【００８３】
【数１０】

【００８４】
なおπ_g'は、双対価格ベクトルπ_gにおける、光伝送装置構成ｔ’を光伝送装置構成の候補とする単位設計区間ｇ’に対する成分である。
また、式（３）により与えられる整数計画問題を解く場合には、光伝送装置構成の候補ｔ’についての被約費用ＲＣ（ｔ’）は、次の式（９）により与えられる。
【００８５】
【数１１】

【００８６】
（手順３）
装置構成決定部１２４は、被約費用の値が負となる新たな光伝送装置構成の候補ｔ’が見つからなくなったとき、それまでに発見された光伝送装置構成の候補について定めた式（１）又は（３）に示す整数計画問題を緩和しないで解決し、発見された光伝送装置構成の候補のうちから、各単位設計区間毎に１つずつ光伝送装置構成を選択することによって、光ネットワーク２００の光伝送装置構成を決定する。
【００８７】
図７に示す装置構成決定部１２４は、初期候補生成部１２５と、緩和問題解決部１２７と、追加候補探索部１２８と、整数計画問題解決部１２９を備える。
初期候補生成部１２５、緩和問題解決部１２７及び追加候補探索部１２８は、特許請求の範囲に記載される組み合わせ候補決定部に相当する。
整数計画問題解決部１２９は、特許請求の範囲に記載される装置配置部に相当する。
【００８８】
緩和問題解決部１２７は、記憶部１２６に格納された装置構成候補データ１１４を読み込み、装置構成候補データ１１４が示す光伝送装置構成の候補について定めた式（１）又は（３）に示す整数計画問題の緩和問題を解決して、双対価格ベクトルを決定する。
【００８９】
初期候補生成部１２５は、緩和問題解決部１２７による処理に先立って、各単位設計区間について、制約条件（１−３）又は（３−３）、（３−４１）〜（３−４Ｒ）を満たす光伝送装置構成の候補を少なくとも１つ生成し、記憶部１２６に格納する。
追加候補探索部１２８は、緩和問題解決部１２７が決定した双対価格ベクトルの値に基づいて決定された被約費用の算出式にしたがって、各単位設計区間について、被約費用の値が負となる新たな光伝送装置構成の候補ｔ’を探索する。追加候補探索部１２８は、発見した新たな候補ｔ’を装置構成候補データ１１４に追加する。
整数計画問題解決部１２９は、記憶部１２６に格納された、初期候補生成部１２５及び追加候補探索部１２８により決定された候補を含む装置構成候補データ１１４を読み込み、装置構成候補データ１１４が示す光伝送装置構成の候補について定めた式（１）又は（３）に示す整数計画問題を緩和しないで解決することにより、光ネットワーク２００の光伝送装置構成を決定する。
【００９０】
以下、図７に示す各部の構成及び各部が行う処理について説明する。図８は、図７に示すパラメータ決定部１２３のブロック図である。
パラメータ決定部１２３は、ペナルティ上限値決定部１３０と、単位設計区間内ペナルティ上限値決定部１３１と、累積ペナルティ決定部１３２と、雑音量上限値決定部１３３と、単位設計区間内雑音量上限値決定部１３４を備える。
【００９１】
ペナルティ上限値決定部１３０は、波長パス情報によって与えられる各波長パスｄ_jの信号種類に応じて、各波長パスｄ_j毎かつ各伝送ペナルティの種類ｋ毎に、伝送ペナルティ上限値Ｐｔｈ_k（ｄ_j）を決定する。
【００９２】
単位設計区間内ペナルティ上限値決定部１３１は、ペナルティ上限値決定部１３０から伝送ペナルティ上限値Ｐｔｈ_k（ｄ_j）を入力する。単位設計区間内ペナルティ上限値決定部１３１は、それぞれの単位設計区間を経由する波長パスｄ_jについて決定された伝送ペナルティ上限値Ｐｔｈ_k（ｄ_j）（ｊ＝１〜Ｎ）のうち、最も小さな値を、単位設計区間内ペナルティ上限値として、各単位設計区間毎かつＲ種類の伝送ペナルティ毎に選択する。
【００９３】
単位設計区間内ペナルティ上限値決定部１３１は、単位区間の経路の伝送方向のそれぞれについて単位設計区間内ペナルティ上限値を決定する。すなわち局舎Ａから局舎Ｂまで亘る単位区間に対して、単位設計区間内ペナルティ上限値決定部１３１は、局舎Ａから局舎Ｂへの伝送路における単位設計区間内ペナルティ上限値と、局舎Ｂから局舎Ａへの伝送路における単位設計区間内ペナルティ上限値とをそれぞれ決定する。
ｋ番目の種類の伝送ペナルティについて、単位設計区間ｇ_hのそれぞれの伝送方向について決定された単位設計区間内ペナルティ上限値をＰｔｈ１_k（ｇ_h）及びＰｔｈ２_k（ｇ_h）（ｋ＝１〜Ｒ，ｈ＝１〜Ｐ）と記す。
【００９４】
累積ペナルティ決定部１３２は、各波長パスｄ_j上において取りうる伝送ペナルティの累積値の最大値Ｐｍａｘ_k（ｄ_j）、又は各波長パスｄ_j上において取りうる伝送ペナルティの累積値の最大値Ｐｍａｘ_k（ｄ_j）及び最小値Ｐｍｉｎ_k（ｄ_j）を決定する。累積ペナルティ決定部１３２による処理の内容は後述する。
【００９５】
雑音量上限値決定部１３３は、上述の雑音量上限値Ｎｔｈ（ｄ_j）又はＮｔｈ’を決定する。
雑音量上限値Ｎｔｈ（ｄ_j）を決定するときは、雑音量上限値決定部１３３は、波長パス情報によって与えられた各波長パスｄ_jの信号種類に応じて定まるＯＳＮＲ耐力に相当する雑音量を雑音量上限値Ｎｔｈ（ｄ_j）として決定する。
【００９６】
上式（５）に従って、雑音量上限値Ｎｔｈ’（ｄ_j）を決定するときは、雑音量上限値決定部１３３は、波長パス情報によって与えられた各波長パスｄ_jの信号種類に応じて定まるＯＳＮＲ耐力と、ペナルティ上限値決定部１３０が決定した伝送ペナルティ上限値Ｐｔｈ_k（ｄ_j）に応じて雑音量上限値Ｎｔｈ’（ｄ_j）を決定する。
【００９７】
上式（６）に従って、雑音量上限値Ｎｔｈ’（ｄ_j）を決定するときは、雑音量上限値決定部１３３は、波長パス情報によって与えられた各波長パスｄ_jの信号種類に応じて定まるＯＳＮＲ耐力と、ペナルティ上限値決定部１３０が決定した伝送ペナルティ上限値Ｐｔｈ_k（ｄ_j）と、累積ペナルティ決定部１３２が決定した伝送ペナルティの累積値の最大値Ｐｍａｘ_k（ｄ_j）と、に応じて雑音量上限値Ｎｔｈ’（ｄ_j）を決定する。
【００９８】
上式（７）に従って、雑音量上限値Ｎｔｈ’（ｄ_j）を決定するときは、雑音量上限値決定部１３３は、波長パス情報によって与えられた各波長パスｄ_jの信号種類に応じて定まるＯＳＮＲ耐力と、ペナルティ上限値決定部１３０が決定した伝送ペナルティ上限値Ｐｔｈ_k（ｄ_j）と、累積ペナルティ決定部１３２が決定した伝送ペナルティの累積値の最大値Ｐｍａｘ_k（ｄ_j）及び最小値Ｐｍｉｎ_k（ｄ_j）と、に応じて雑音量上限値Ｎｔｈ’（ｄ_j）を決定する。
【００９９】
単位設計区間内雑音量上限値決定部１３４は、雑音量上限値決定部１３３から出力される雑音量上限値Ｎｔｈ（ｄ_j）又はＮｔｈ’（ｄ_j）を入力する。単位設計区間内雑音量上限値決定部１３４は、各単位設計区間毎に、それぞれの単位設計区間を経由する波長パスｄ_jについて決定された雑音量上限値のうち、最も小さな値を、単位設計区間内雑音両上限値として選択する。
【０１００】
単位設計区間内雑音量上限値決定部１３４は、単位区間の経路の伝送方向のそれぞれについて単位設計区間内雑音量上限値を決定する。すなわち局舎Ａから局舎Ｂまで亘る単位区間に対して、単位設計区間内雑音量上限値決定部１３４は、局舎Ａから局舎Ｂへの伝送路における単位設計区間内雑音量上限値と、局舎Ｂから局舎Ａへの伝送路における単位設計区間内雑音量上限値とをそれぞれ決定する。
単位設計区間ｇ_hのそれぞれの伝送方向について決定された単位設計区間内雑音量上限値をＮｔｈ１（ｇ_h）及びＮｔｈ２（ｇ_h）（ｈ＝１〜Ｐ）と記す。
【０１０１】
累積ペナルティ決定部１３２は、パス内グラフ生成部１４０と、パス内ノード探索部１４１と、累積値計算部１４２を備える。パス内グラフ生成部１４０は、情報所得部１２０から得た情報に基づいて、波長パスｄ_jが経由する各局舎に配置される各種の光伝送装置の候補にそれぞれ対応する各ノードと、伝送ペナルティに対応付けられ各ノードを接続する各リンクと、からなるループのない有向のグラフ情報を生成する。
【０１０２】
パス内グラフ生成部１４０は、第１ノード候補生成部１４３と、第１リンク生成部１４４と、ペナルティ決定部１４５を備えている。第１ノード候補生成部１４３は、光伝送装置情報に基づいて、各局舎について、配置可能な各種の光伝送装置に対応する１つ以上のノードを生成する。
【０１０３】
たとえば、波長パスｄ_jが経由する区間に局舎１及び局舎２が含まれていたとする。局舎１に光伝送装置Ａまたは光伝送装置Ｂが配置可能な場合は、第１ノード候補生成部１４３は、局舎１に光伝送装置Ａを配置する場合に対応するノード１Ａと、局舎１に光伝送装置Ｂを配置する場合に対応するノード１Ｂと、を生成する。
【０１０４】
また、局舎２に光伝送装置Ａのみが配置可能な場合は、第１ノード候補生成部１４３は、局舎２に光伝送装置Ａを配置する場合に対応するノード２Ａを生成する。第１ノード候補生成部１４３は、生成した各ノードを第１リンク生成部１４４へ出力する。このように第１ノード候補生成部１４３は、波長パスｄ_jが経由する区間内の各局舎にそれぞれ対応する１つ以上のノードを生成する。
【０１０５】
第１リンク生成部１４４は、第１ノード候補生成部１４３から出力された各ノードについて、当該ノードに対応する局舎よりも前段の局舎に対応するノードからの入力リンクを生成する。たとえば局舎１に対応するノード１Ａ及びノード１Ｂと、局舎１の後段の局舎２に対するノード２Ａと、があった場合には、第１リンク生成部１４４は、ノード１Ａからノード２Ａへの入力リンクと、ノード１Ｂからノード２Ａへの入力リンクとを生成する。
【０１０６】
第１リンク生成部１４４は、第１ノード候補生成部１４３から出力された各ノードと、生成した各入力リンクと、をペナルティ決定部１４５へ出力する。
ペナルティ決定部１４５は、波長パス情報によって与えられた各波長パスｄ_jの信号種類と、スパン情報によって与えられた、波長パスｄ_jの信号種類に対して隣接局舎間に生じる伝送ペナルティ量と、光伝送装置情報によって与えられた、各種の光伝送装置を経由する波長パスｄ_jの信号種類の光信号に生じる伝送ペナルティ量と、に基づいて、第１リンク生成部１４４から出力された各入力リンクについて、それぞれの入力リンクを選択した場合に波長パスｄ_jに生じる伝送ペナルティ量を、伝送ペナルティの種類毎に決定する。
【０１０７】
ペナルティ決定部１４５は、たとえば、ノード１Ａからノード２Ａへの入力リンクについて、この入力リンクを選択した場合に波長パスｄ_jに生じる伝送ペナルティ量を算出する。
また、ペナルティ決定部１４５は、ノード１Ｂからノード２Ａへの入力リンクについて、この入力リンクを選択した場合に波長パスｄ_jに生じる伝送ペナルティ量を算出する。
ペナルティ決定部１４５は、第１ノード候補生成部１４３から出力された各ノードと、第１リンク生成部１４４から出力された各入力リンクと、算出した各伝送ペナルティ量を、パス内ノード探索部１４１へ出力する。
【０１０８】
累積ペナルティ決定部１３２が伝送ペナルティの累積値の最大値Ｐｍａｘ_k（ｄ_j）を決定するとき、パス内ノード探索部１４１は、パス内グラフ生成部１４０から出力されたグラフ情報において、伝送ペナルティの累積値が最大となる配置に対応する経路を、伝送ペナルティの種類毎に探索する。
また、累積ペナルティ決定部１３２が伝送ペナルティの累積値の最小値Ｐｍｉｎ_k（ｄ_j）、を決定するとき、パス内ノード探索部１４１は、パス内グラフ生成部１４０から出力されたグラフ情報において、伝送ペナルティの累積値が最小となる配置に対応する経路を、伝送ペナルティの種類毎に探索する。
【０１０９】
パス内ノード探索部１４１は、第１リンク選択部１４６と、第１ノード決定部１４７を備える。第１リンク選択部１４６は、パス内グラフ生成部１４０から出力された各ノードについての入力リンクを選択する。第１リンク選択部１４６は、第１ノード候補生成部１４３によって生成された各ノードについて、当該ノードに対して第１リンク生成部１４４によって生成された各入力リンクのうちのいずれかを選択する。
【０１１０】
累積ペナルティ決定部１３２が伝送ペナルティの累積値の最大値Ｐｍａｘ_k（ｄ_j）、を決定する場合には、第１リンク選択部１４６は、その入力リンクを選択した場合に対象ノードまでに累積される伝送ペナルティが最大となる入力リンクを選択する。
一方で、累積ペナルティ決定部１３２が伝送ペナルティの累積値の最小Ｐｍｉｎ_k（ｄ_j）を決定する場合には、第１リンク選択部１４６は、その入力リンクを選択した場合に当該ノードまでに累積される伝送ペナルティが最小となる入力リンクを選択する。
【０１１１】
たとえば、当該ノード２Ａへの入力リンクが、ノード１Ａからの入力リンク（１Ａ，２Ａ）及びノード１Ｂからの入力リンク（１Ｂ，２Ａ）であり、ノード１Ａ及びノード１Ｂまでに累積される伝送ペナルティが、それぞれＰＮａｃｃ（１Ａ）及びＰＮａｃｃ（１Ｂ）であり、入力リンク（１Ａ，２Ａ）及び入力リンク（１Ｂ，２Ａ）を選択した場合に生じる伝送ペナルティがＰＮ（１Ａ，２Ａ）、ＰＮ（１Ｂ，２Ａ）であったとする。
【０１１２】
この場合は、第１リンク選択部１４６は、当該ノード２Ａについて、入力リンク（１Ａ，２Ａ）を選択した場合にノード２Ａまでに累積されるＰＮａｃｃ（１Ａ）＋ＰＮ（１Ａ，２Ａ）と、入力リンク（１Ｂ，２Ａ）を選択した場合にノード２Ａまでに累積されるＰＮａｃｃ（１Ｂ）＋ＰＮ（１Ｂ，２Ａ）を比較する。
累積ペナルティ決定部１３２が最大値Ｐｍａｘ_k（ｄ_j）を決定する場合には、第１リンク選択部１４６は、前者が大きければ入力リンク（１Ａ，２Ａ）を選択し、後者が大きければ入力リンク（１Ｂ，２Ａ）を選択する。
一方で、累積ペナルティ決定部１３２が最小Ｐｍｉｎ_k（ｄ_j）を決定する場合には、第１リンク選択部１４６は、前者が小さければ入力リンク（１Ａ，２Ａ）を選択し、後者が小さければ入力リンク（１Ｂ，２Ａ）を選択する。
【０１１３】
第１リンク選択部１４６は、ペナルティ決定部１４５が算出した各伝送ペナルティ量と、各ノードについて選択した入力リンクを第１ノード決定部１４７に出力する。
【０１１４】
第１ノード決定部１４７は、第１リンク選択部１４６から出力された各入力リンクの始点ノードに基づいて、波長パスｄ_jが経由する区間内の各局舎に対する各種の光伝送装置の配置を決定する。たとえば、第１リンク選択部１４６から出力された各入力リンクのそれぞれの始点ノードがノード１Ａ，ノード２Ｂ，ノード３Ａ…であった場合は、第１ノード決定部１４７は、各局舎に対する各種の光伝送装置の配置を、ノード１Ａ，ノード２Ｂ，ノード３Ａ…に対応する光伝送装置の配置に決定する。
【０１１５】
第１ノード決定部１４７は、決定した各ノードと、ペナルティ決定部１４５が算出した各伝送ペナルティ量とを累積値計算部１４２へ出力する。
累積値計算部１４２は、第１ノード決定部１４７が決定した各ノードを通過する経路に沿って累積する伝送ペナルティを、伝送ペナルティの種類毎に決定し、雑音量上限値決定部１３３に出力する。
【０１１６】
図９は、図７に示す初期候補生成部１２５のブロック図である。初期候補生成部１２５は、第１単位設計区間内グラフ生成部１５０と、第１単位設計区間内ノード探索部１５１とを備える。
第１単位設計区間内グラフ生成部１５０は、情報所得部１２０から得た情報と、区間分割部１２１がネットワーク２００を分割して生成した各単位設計区間ｇ_hに関する情報に基づいて、各単位設計区間ｇ_hに配置される各種の光伝送装置の候補にそれぞれ対応する各ノードと、伝送ペナルティに対応付けられ各ノードを接続する各リンクと、からなるループのない有向のグラフ情報を生成する。
【０１１７】
第１単位設計区間内グラフ生成部１５０は、第２ノード候補生成部１５２と、第２リンク生成部１５３と、コスト決定部１５４と、伝送劣化量決定部１５５、を備えている。
第２ノード候補生成部１５２は、光伝送装置情報に基づいて、各単位設計区間ｇ_hの各局舎について、配置可能な各種の光伝送装置に対応する１つ以上のノードを生成する。
【０１１８】
たとえば、単位設計区間ｇ_hに局舎１および局舎２が含まれているとする。局舎１に光伝送装置Ａまたは光伝送装置Ｂが配置可能な場合は、第２ノード候補生成部１５２は、局舎１に光伝送装置Ａを配置する場合に対応するノード１Ａと、局舎Ａに光伝送装置Ｂを配置する場合に対応するノード１Ｂと、を生成する。
【０１１９】
また、局舎２に光伝送装置Ａのみが配置可能な場合は、第２ノード候補生成部１５２は、局舎２に光伝送装置Ａを配置する場合に対応するノード２Ａを生成する。第２ノード候補生成部１５２は、生成した各ノードを第２リンク生成部１５３へ出力する。
【０１２０】
第２リンク生成部１５３は、第２ノード候補生成部１５２から出力された各ノードについて、当該ノードに対応する局舎よりも前段の局舎に対応するノードからの入力リンクを生成する。たとえば局舎１に対応するノード１Ａ及びノード１Ｂと、局舎１の後段の局舎２に対するノード２Ａと、があった場合には、第２リンク生成部１５３は、ノード１Ａからノード２Ａへの入力リンクと、ノード１Ｂからノード２Ａへの入力リンクとを生成する。
第２リンク生成部１５３は、第２ノード候補生成部１５２から出力された各ノードと、生成した各入力リンクと、をコスト決定部１５４及び伝送劣化量決定部１５５へ出力する。
【０１２１】
コスト決定部１５４は、光伝送装置情報によって与えられた各種の光伝送装置のコストに基づいて、第２リンク生成部１５３から出力された各入力リンクについて、各入力リンクを選択した場合のコストを算出する。たとえば算出されるコストは、各局舎に配置する光伝送装置のコストとしてよい。
【０１２２】
コスト決定部１５４は、たとえば、ノード１Ａからノード２Ａへの入力リンクについて、この入力リンクを選択した場合に生じるコストを算出する。またコスト決定部１５４は、ノード１Ｂからノード２Ａへの入力リンクについて、この入力リンクを選択した場合に生じるコストを算出する。
【０１２３】
伝送劣化量決定部１５５は、スパン情報によって与えられた隣接局舎間に生じる雑音量及び伝送ペナルティ量と、光伝送装置情報によって与えられた、各種の光伝送装置を経由する光信号に生じる雑音量及び伝送ペナルティ量に基づいて、第２リンク生成部１５３から出力された各入力リンクについて、それぞれの入力リンクを選択した場合に生じる、伝送劣化量、すなわち、雑音量と伝送ペナルティの種類毎の伝送ペナルティ量を決定する。
【０１２４】
伝送劣化量決定部１５５は、たとえば、ノード１Ａからノード２Ａへの入力リンクについて、この入力リンクを選択した場合に生じる雑音量及び伝送ペナルティをそれぞれ算出する。また伝送劣化量決定部１５５は、ノード１Ｂからノード２Ａへの入力リンクについて、この入力リンクを選択した場合に生じる雑音量及び伝送ペナルティをそれぞれ算出する。
【０１２５】
伝送劣化量決定部１５５は、入力リンクの入力方向の順方向と逆方向のそれぞれについて雑音量と伝送ペナルティ量を決定する。局舎Ａから局舎Ｂへ入力する入力リンクに対して、伝送劣化量決定部１５５は、局舎Ａから局舎Ｂへの経路上で生じる雑音量及び伝送ペナルティ量と、局舎Ｂから局舎Ａへの経路上で生じる雑音量及び伝送ペナルティ量とをそれぞれ決定する。
【０１２６】
伝送劣化量決定部１５５は、第２ノード候補生成部１５２から出力された各ノードと、第２リンク生成部１５３から出力された各入力リンクと、算出した伝送劣化量を、第１単位設計区間内ノード探索部１５１へ出力する。
またコスト決定部１５４は、算出したコストを第１単位設計区間内ノード探索部１５１へ出力する。
【０１２７】
第１単位設計区間内ノード探索部１５１は、第１単位設計区間内グラフ生成部１５０から出力されたグラフ情報において、光再生中継器を配置可能な装置が配置された隣接局者間の伝送劣化量がそれぞれの上限値以下となり、コストが最小となる配置に対応する経路を探索する。第１単位設計区間内ノード探索部１５１は、第２リンク選択部１５６と、第２ノード決定部１５７を有する。第２リンク選択部１５６は、第１単位設計区間内グラフ生成部１５０から出力された各ノードについて入力リンクを選択する。
【０１２８】
第２リンク選択部１５６は、第２ノード候補生成部１５２によって生成された各ノードについて、対象のノードに対応して第２リンク生成部１５３によって生成された各入力リンクのうちのいずれかを選択する。このとき、第２リンク選択部１５６は、その入力リンクを選択した場合に対象のノードまでに累積されるコストが最小となる入力リンクを選択する。
【０１２９】
たとえば、対象のノード２Ａへの入力リンクがノード１Ａからの入力リンク（１Ａ，２Ａ）およびノード１Ｂからの入力リンク（１Ｂ，２Ａ）であり、ノード１Ａおよびノード１Ｂまでに累積される各コストがＣＯＳＴａｃｃ（１Ａ）およびＣＯＳＴａｃｃ（１Ｂ）であり、入力リンク（１Ａ，２Ａ）および入力リンク（１Ｂ，２Ａ）を選択した場合の各コストがＣＯＳＴ（１Ａ，２Ａ）およびＣＯＳＴ（１Ｂ，２Ａ）であるとする。
【０１３０】
この場合は、第２リンク選択部１５６は、対象のノード２Ａについて、入力リンク（１Ａ，２Ａ）を選択した場合にノード２Ａまでに累積されるＣＯＳＴａｃｃ（１Ａ）＋ＣＯＳＴ（１Ａ，２Ａ）と、入力リンク（１Ｂ，２Ａ）を選択した場合にノード２Ａまでに累積されるＣＯＳＴａｃｃ（１Ｂ）＋ＣＯＳＴ（１Ｂ，２Ａ）と、を比較し、前者が小さければ入力リンク（１Ａ，２Ａ）を選択し、後者が小さければ入力リンク（１Ｂ，２Ａ）を選択する。
【０１３１】
また、第２リンク選択部１５６は、対象のノードについて第１単位設計区間内グラフ生成部１５０から出力された各入力リンクのうちの、その入力リンクを選択した場合に、対象のノードに対応する局舎より後段の局舎に対応する各ノードのうちの光再生中継器を配置可能な光伝送装置に対応するノード（以下、「後段光再生ノード」という）までに累積される各伝送劣化量がすべて閾値以下となる入力リンクから、コストが最小となる入力リンクを選択する。
【０１３２】
たとえば、ノード２Ａに対応する局舎２の後段に局舎３があり、局舎３に対応するノード３Ａおよびノード３Ｂのうちの、ノード３Ａが光再生中継器を配置可能な光伝送装置である場合は、第２リンク選択部１５６は、ノード３Ａを後段光再生ノードとする。そして、第２リンク選択部１５６は、ノード３Ａまでに累積される伝送劣化量が閾値以下となる入力リンクから、コストが最小となる入力リンクを選択する。
【０１３３】
また、ノード２Ａについて後段光再生ノードが複数ある場合は、複数の後段光再生ノードのうちのノード２Ａからの伝送劣化量が最小となるノードまでに累積される伝送劣化量が閾値以下となる入力リンクから、コストが最小となる入力リンクを選択する。
【０１３４】
また、第２リンク選択部１５６は、対象のノードの後段光再生ノードまでに累積される伝送劣化量として、その入力リンクの始点ノードまでに累積される伝送劣化量と、その入力リンクを選択したときの伝送劣化量と、対象のノードから対象のノードの後段光再生ノードまでの伝送劣化量の最小値と、の合計値を用いる。
【０１３５】
たとえば、伝送劣化量として順方向の雑音量に関する処理を説明すると、ノード１Ａおよびノード１Ｂまでに累積される伝送劣化量をそれぞれＮＯＩＳＥａｃｃ（１Ａ）およびＮＯＩＳＥａｃｃ（１Ｂ）とし、入力リンク（１Ａ，２Ａ）および入力リンク（１Ｂ，２Ａ）について伝送劣化量決定部１５５によって決定された雑音量をそれぞれＮＯＩＳＥ（１Ａ，２Ａ）およびＮＯＩＳＥ（１Ｂ，２Ａ）とし、ノード２Ａから後段光再生ノード（ノード３Ａ）までの伝送劣化量の最小値をＮＯＩＳＥｍｉｎとし、単位設計区間内雑音量上限値決定部１３４が決定した順方向の単位設計区間内雑音量上限値を雑音量の閾値ＮＯＩＳＥｔｈとする。
【０１３６】
この場合は、第２リンク選択部１５６は、ノード２Ａについて、入力リンク（１Ａ，２Ａ）に対応するＮＯＩＳＥａｃｃ（１Ａ）＋ＮＯＩＳＥ（１Ａ，２Ａ）＋ＮＯＩＳＥｍｉｎと、入力リンク（１Ｂ，２Ａ）に対応するＮＯＩＳＥａｃｃ（１Ｂ）＋ＮＯＩＳＥ（１Ｂ，２Ａ）＋ＮＯＩＳＥｍｉｎと、をそれぞれ算出し、各算出結果とＮＯＩＳＥｔｈと、をそれぞれ比較する。第２リンク選択部１５６は、算出結果がＮＯＩＳＥｔｈより大きくなる入力リンクを除外し、残った入力リンクのうちのコストが最小となる入力リンクを選択する。
【０１３７】
また、第２リンク選択部１５６は、対象のノードが光再生中継器を配置可能な光伝送装置に対応するノードである場合は、対象のノードから後段光再生ノードまでの伝送劣化量の最小値ＮＯＩＳＥｍｉｎ０とする。また、この場合、入力リンク選択後、第２リンク選択部１５６は、対象のノードが光再生中継器を配置可能な光伝送装置に対応するノードである場合は、対象のノードまでに累積される伝送劣化量を０とする。
【０１３８】
たとえば、ノード２Ａが光再生中継器を配置可能な光伝送装置に対応するノードである場合は、第２リンク選択部１５６は、ノード２Ａについて、ＮＯＩＳＥａｃｃ（１Ａ）＋ＮＯＩＳＥ（１Ａ，２Ａ）＋０と、ＮＯＩＳＥａｃｃ（１Ｂ）＋ＮＯＩＳＥ（１Ｂ，２Ａ）＋０と、をそれぞれ算出する。また、入力リンク選択後、第２リンク選択部１５６は、ノード２Ａまでに累積される伝送劣化量ＮＯＩＳＥａｃｃ（２Ａ）を０とする。なお、ノード２Ａまでに累積される伝送劣化量は、局舎２の直後の局舎３に対応する各ノードの入力リンクの選択に用いられる。
【０１３９】
第２リンク選択部１５６は、伝送劣化量が逆方向の雑音量である場合についても、同様の処理によって、累積される雑音量を決定して、算出結果が閾値より大きくなる入力リンクを除外する。
また第２リンク選択部１５６は、伝送劣化量が各方向の各伝送ペナルティである場合についても、同様の処理によって、累積される伝送ペナルティを決定して、算出結果が閾値より大きくなる入力リンクを除外する。伝送劣化量を各伝送ペナルティとするときは、第２リンク選択部１５６は、単位設計区間内ペナルティ上限値決定部１３１が決定した各伝送方向の伝送ペナルティ上限値を、伝送ペナルティの閾値として使用する。
【０１４０】
第２ノード決定部１５７は、第２リンク選択部１５６から出力された各入力リンクの始点ノードに基づいて、線形区間内の各局舎に対する各種の光伝送装置の配置、すなわち光伝送装置構成の１つの候補を決定する。たとえば、第２リンク選択部１５６から出力された各入力リンクのそれぞれの始点ノードがノード１Ａ，ノード２Ｂ，ノード３Ａ…であった場合は、第２ノード決定部１５７は、各局舎に対する各種の光伝送装置の配置を、ノード１Ａ，ノード２Ｂ，ノード３Ａ…に対応する光伝送装置の配置に決定する。第２ノード決定部１５７は、決定した光伝送装置構成の候補を記憶部１２６に格納する。
【０１４１】
以上のとおり構成された初期候補生成部１２５によって光伝送装置構成が選択された単位設計区間では、光再生中継器を配置可能な装置が配置された隣接局舎間の雑音量が、その単位設計区間を経由する各波長パスについて決定された雑音上限値の最小値よりも小さくなる。
【０１４２】
また、以上のとおり構成された初期候補生成部１２５によって光伝送装置構成が選択された単位設計区間では、光再生中継器を配置可能な装置が配置された隣接局舎間の伝送ペナルティが、当該単位設計区間を経由する各波長パスについて決定された伝送ペナルティの上限値の最小値よりも小さくなる。
【０１４３】
図１０は、図７に示す追加候補探索部１２８のブロック図である。追加候補探索部１２８は、図７に示す緩和問題解決部１２７が決定した双対価格ベクトルの値に基づいて決定された被約費用の算出式にしたがって、各単位設計区間について、被約費用の値が負となる新たな光伝送装置構成の候補ｔ’を探索する。
【０１４４】
追加候補探索部１２８は、第２単位設計区間内グラフ生成部１６０と、第２単位設計区間内ノード探索部１６１と、被約費用決定部１６８と、追加可否判定部１６９を備える。
第２単位設計区間内グラフ生成部１６０及び第２単位設計区間内ノード探索部１６１は、図９に示す初期候補生成部１２５の第１単位設計区間内グラフ生成部１５０及び第１単位設計区間内ノード探索部１５１と類似する構成を有する。
【０１４５】
第２単位設計区間内グラフ生成部１６０が有する第３ノード候補生成部１６２、第３リンク生成部１６３及び伝送劣化量決定部１６５は、第１単位設計区間内グラフ生成部１５０が有する第２ノード候補生成部１５２、第２リンク生成部１５３及び伝送劣化量決定部１５５と同様の機能を有する。
第２単位設計区間内ノード探索部１６１が有する第３リンク選択部１６６及び第３ノード決定部１６７は、第１単位設計区間内ノード探索部１５１が有する第２リンク選択部１５６及び第２ノード決定部１５７と同様の機能を有する。
【０１４６】
ただし、第２単位設計区間内グラフ生成部１６０は、第１単位設計区間内グラフ生成部１５０がコスト決定部１５４を有するのに代えて、被約費用変化決定部１６４を備える。
被約費用変化決定部１６４は、コスト決定部１５４が各入力リンクを選択した場合のコストを決定するのに代えて、各入力リンクを選択した場合における当該単位設計区間の被約費用の変化量ΔＲＣを決定する。
また、第１単位設計区間内ノード探索部１５１の第２リンク選択部１５６が、その入力リンクを選択した場合に対象のノードまでに累積されるコストが最小となる入力リンクを選択するのに代えて、第３リンク選択部１６６は、その入力リンクを選択した場合に対象のノードまでに累積される被約費用の変化量ΔＲＣが最小となる入力リンクを選択する。
また、上述したように第２リンク選択部１５６により選択された入力リンクにより接続される光再生中継器を配置可能な局舎の間に生じる雑音量及び各ペナルティ値が上記の各閾値以下となるのと同様に、第３リンク選択部１６６により選択された入力リンクにより接続される光再生中継器を配置可能な局舎の間に生じる雑音量及び各ペナルティ値もまた上記の閾値以下となる。
【０１４７】
装置構成決定部１２４が、式（１）により与えられる整数計画問題を解く場合には、被約費用変化決定部１６４は、光伝送装置情報によって与えられた各種の光伝送装置のコストと各種の光伝送装置を経由する光信号に生じる雑音量、及びスパン情報によって与えられた隣接局舎間に生じる雑音量に基づいて、各入力リンクを選択した場合に増加する装置コストΔｃ並びに雑音量Δｎｆ及びΔｎｒを決定する。
【０１４８】
Δｎｆは、当該入力リンクを選択した場合に、当該単位設計区間をその基準方向と同じ方向に伝送する波長パスに生じる雑音量の変化量であり、Δｎｒは、当該入力リンクを選択した場合に、当該単位設計区間をその基準方向と反対方向に伝送する波長パスに生じる雑音量の変化量である。
【０１４９】
被約費用変化決定部１６４は、緩和問題解決部１２７が決定した双対価格ベクトルの値に基づいて決定された被約費用の算出式（１０）に従って、各入力リンクを選択した場合における当該単位設計区間の被約費用の変化量ΔＲＣを決定する。
【０１５０】
【数１２】

【０１５１】
装置構成決定部１２４が、式（３）により与えられる整数計画問題を解く場合には、被約費用変化決定部１６４は、光伝送装置情報によって与えられた各種の光伝送装置のコストと各種の光伝送装置を経由する光信号に生じる雑音量及び伝送ペナルティ量、及びスパン情報によって与えられた隣接局舎間に生じる雑音量及び伝送ペナルティ量に基づいて、各入力リンクを選択した場合に増加する装置コストΔｃ、雑音量Δｎｆ及びΔｎｒ、並びに伝送ペナルティ量Δｐｆ_kj及びΔｐｒ_kjを決定する。
【０１５２】
Δｐｆ_kjは、当該入力リンクを選択した場合に、当該単位設計区間をその基準方向と同じ方向に伝送する波長パスｄ_jに生じる、第ｋ番目の種類の伝送ペナルティ量の変化量である。またΔｐｒ_kjは、当該入力リンクを選択した場合に、当該単位設計区間をその基準方向と反対方向に伝送する波長パスｄ_jに生じる、第ｋ番目の種類の伝送ペナルティ量の変化量である。
【０１５３】
被約費用変化決定部１６４は、緩和問題解決部１２７が決定した双対価格ベクトルの値に基づいて決定される、以下の被約費用の算出式（１１）に従って、各入力リンクを選択した場合における当該単位設計区間の被約費用の変化量ΔＲＣを決定する。
【０１５４】
【数１３】

【０１５５】
以上のとおり構成された第２単位設計区間内グラフ生成部１６０及び第２単位設計区間内ノード探索部１６１によって選択された光伝送装置構成は、当該単位設計区間において最小の被約費用を生じる光伝送装置構成となる。
【０１５６】
被約費用決定部１６８は、第２単位設計区間内グラフ生成部１６０及び第２単位設計区間内ノード探索部１６１によって選択された光伝送装置構成により生じる被約費用ＲＣを決定する。被約費用決定部１６８は、たとえば、選択された光伝送装置構成において単位設計区間に亘って累積する被約費用の変化量ΔＲＣの累積値に、緩和問題解決部１２７が決定した双対価格ベクトルπ_gのうち当該単位設計区間に対する成分を減じることによって被約費用ＲＣを決定する。
【０１５７】
追加可否決定部１６９は、被約費用決定部１６８により決定された被約費用ＲＣが０より小さいか否かを判定し、判定結果を緩和問題解決部１２７及び整数計画問題解決部１２９へ通知する。追加可否決定部１６９は、被約費用ＲＣが０より小さい場合には、決定した光伝送装置構成の候補を記憶部１２６に格納する。
【０１５８】
緩和問題解決部１２７は、追加可否決定部１６９による判定結果に従って、追加候補探索部１２８が被約費用ＲＣが負である構成を発見できるか否かを判定する。緩和問題解決部１２７は、追加候補探索部１２８が被約費用ＲＣが負である構成を発見できなくなるまで、追加候補探索部１２８により新たに候補が追加された装置構成候補データ１１４を読み込み、整数計画問題の緩和問題を解決して双対価格ベクトルを更新する。
【０１５９】
整数計画問題解決部１２９は、追加可否決定部１６９による判定結果に従って、追加候補探索部１２８が被約費用ＲＣが負である構成を発見できるか否かを判定する。追加候補探索部１２８が、被約費用ＲＣが負である構成を発見できなくなったとき、その時点で装置構成候補データ１１４を読み込み、整数計画問題を緩和しないで解決することにより、光ネットワーク２００の光伝送装置構成を決定する。
【０１６０】
図１１は、開示のネットワーク設計方法の全体フローチャートである。
ステップＳ１において、図７に示す情報取得部１２０は、ＷＤＭ光ネットワーク情報を取得する。
ステップＳ２において、区間分割部１２１は、ＷＤＭ光ネットワーク情報中のネットワークトポロジ情報によって与えられた光ネットワーク２００を、線形区間である単位設計区間に分割する。
【０１６１】
ステップＳ３において、図８に示すパラメータ決定部１２３は、雑音量上限値Ｎｔｈ又はＮｔｈ’、及び伝送ペナルティの上限値Ｐｔｈ_k（ｄ_j）を決定する。
さらに、パラメータ決定部１２３は、単位設計区間内雑音量上限値Ｎｔｈ１（ｇ_h）及びＮｔｈ２（ｇ_h）並びに単位設計区間内ペナルティ上限値Ｐｔｈ１_k（ｇ_h）及びＰｔｈ２_k（ｇ_h）を決定する。
【０１６２】
上述のとおり、パラメータ決定部１２３が、上述の決定方法の第２例又は第３例によって雑音量上限値Ｎｔｈ’を決定する場合、図８に示す累積ペナルティ決定部１３２は、各波長パスｄ_j上において取りうる伝送ペナルティの累積値の最小値Ｐｍｉｎ_k（ｄ_j）及び／又は最大値Ｐｍａｘ_k（ｄ_j）を決定する。以下、累積ペナルティ決定部１３２による、伝送ペナルティの累積値の最小値Ｐｍｉｎ_k（ｄ_j）及び最大値Ｐｍａｘ_kの決定方法を説明する。
【０１６３】
図１２は、図８に示すパス内グラフ生成部１４０が生成するグラフ情報の例を示す図（その１）である。図１２に示す局舎１〜６は、図１において波長パスｄが経由する単位設計区間２０２及び２０３における局舎１〜６である。ノード１Ａ〜６Ａおよびノード２Ｂ、３Ｂ及び５Ｂは、第１ノード候補生成部１４３が生成した各ノードを示している。局舎１〜局舎６に配置可能な光伝送装置のうちの光再生中継器を配置可能な光伝送装置としてＯＡＤＭ（たとえば図３のＯＡＤＭ４００）を用いる。
【０１６４】
また、局舎１〜局舎６に配置可能な光伝送装置のうちの光再生中継器を配置できない光伝送装置としてＩＬＡ（たとえば、図４のＩＬＡ５００）を用いる。局舎１〜局舎６のうちの、始端局舎である局舎１と、終端局舎である局舎６には、光再生中継器を配置可能なＯＡＤＭのみが配置可能である。局舎２と局舎３、局舎５にはＯＡＤＭ、ＩＬＡまたはバイパス（たとえば、図５のバイパス６００）が配置可能である。また、局舎４にはＩＬＡを配置不可としている。
【０１６５】
第１ノード候補生成部１４３は、局舎１〜６について、各局舎に配置可能なＯＡＤＭを示すノード１Ａ〜ノード６Ａをそれぞれ生成する。また、第１ノード候補生成部１４３は、局舎２、３及び５について、各局舎に配置可能なＩＬＡを示すノード２Ｂ、３Ｂ及びノード５Ｂをそれぞれ生成する。図１２において、矢印は、第１リンク生成部１４４によって生成された各ノード間の各入力リンクを示している。以下の説明において、ノードＹのノードＸからの入力リンクを入力リンク（Ｘ，Ｙ）と表記する。
【０１６６】
第１ノード候補生成部１４３によって生成されたノード１Ａは始端局舎に対応するノードであるため、第１リンク生成部１４４はノード１Ａへの入力リンクは生成しない。第１リンク生成部１４４は、ノード２Ａについて、ノード２Ａに対応する局舎２より前段の局舎１に対応するノード１Ａからの入力リンク（１Ａ，２Ａ）を生成する。また、第１リンク生成部１４４は、ノード２Ｂについて、ノード２Ｂに対応する局舎２より前段の局舎１に対応するノード１Ａからの入力リンク（１Ａ，２Ｂ）を生成する。
【０１６７】
また、第１リンク生成部１４４は、ノード３Ａについて、ノード３Ａに対応する局舎３より前段の局舎２に対応するノード２Ａからの入力リンク（２Ａ，３Ａ）およびノード２Ｂからの入力リンク（２Ｂ，３Ａ）を生成する。また、第１リンク生成部１４４は、ノード３Ｂについて、ノード３Ｂに対応する局舎３より前段の局舎２に対応するノード２Ａからの入力リンク（２Ａ，３Ｂ）およびノード２Ｂからの入力リンク（２Ｂ，３Ｂ）を生成する。
【０１６８】
また、第１リンク生成部１４４は、ノード４Ａについて、ノード４Ａに対応する局舎４より前段の局舎３に対応するノード３Ａからの入力リンク（３Ａ，４Ａ）およびノード３Ｂからの入力リンク（３Ｂ，４Ａ）を生成する。
【０１６９】
また、第１リンク生成部１４４は、ノード５Ａについて、ノード５Ａに対応する局舎５より前段の局舎４に対応するノード４Ａからの入力リンク（４Ａ，５Ａ）を生成する。また、第１リンク生成部１４４は、ノード５Ｂについて、ノード５Ｂに対応する局舎５より前段の局舎４に対応するノード４Ａからの入力リンク（４Ａ，５Ｂ）を生成する。
【０１７０】
また、第１リンク生成部１４４は、ノード６Ａについて、ノード６Ａに対応する局舎６より前段の局舎５に対応するノード５Ａからの入力リンク（５Ａ，６Ａ）およびノード５Ｂからの入力リンク（５Ｂ、６Ａ）を生成する。
【０１７１】
以下、ペナルティ決定部１４５が決定した伝送ペナルティ量の例を示す。図１２において、各入力リンクに隣接して表示される数字は、各入力リンクについてペナルティ決定部１４５によって算出された伝送ペナルティを示す。ペナルティ決定部１４５は、第１リンク生成部１４４によって生成された入力リンク（１Ａ，２Ａ）を選択した場合の伝送ペナルティを「１」と決定する。また、ペナルティ決定部１４５は、入力リンク（１Ａ，２Ｂ）を選択した場合の伝送ペナルティを「２」と決定する。
【０１７２】
ペナルティ決定部１４５は、入力リンク（２Ａ，３Ａ）を選択した場合の伝送ペナルティを「１」と決定する。また、ペナルティ決定部１４５は、入力リンク（２Ｂ，３Ａ）を選択した場合の伝送ペナルティを「２」と決定する。また、ペナルティ決定部１４５は、入力リンク（２Ａ，３Ｂ）を選択した場合の伝送ペナルティを「２」と決定する。また、ペナルティ決定部１４５は、入力リンク（２Ｂ，３Ｂ）を選択した場合の伝送ペナルティを「３」と決定する。
【０１７３】
ペナルティ決定部１４５は、入力リンク（３Ａ，４Ａ）を選択した場合の伝送ペナルティを「１」と決定する。また、ペナルティ決定部１４５は、入力リンク（３Ｂ，４Ａ）を選択した場合の伝送ペナルティを「２」と決定する。
ペナルティ決定部１４５は、入力リンク（４Ａ，５Ａ）を選択した場合の伝送ペナルティを「１」と決定する。ペナルティ決定部１４５は、入力リンク（４Ａ，５Ｂ）を選択した場合の伝送ペナルティを「２」と決定する。
【０１７４】
ペナルティ決定部１４５は、入力リンク（５Ａ，６Ａ）を選択した場合の伝送ペナルティを「１」と決定する。また、ペナルティ決定部１４５は、入力リンク（５Ｂ，６Ａ）を選択した場合の伝送ペナルティを「２」と決定する。これにより、局舎１〜６に配置するＯＡＤＭ，ＩＬＡに対応する各ノードと、伝送ペナルティ量に対応付けられかつ各ノードを接続する各リンクと、からなるグラフ情報が生成される。
【０１７５】
図１３は、図８に示すパス内グラフ生成部１４０が生成するグラフ情報の例を示す図（その２）である。図１３において、図１２に示した伝送ペナルティ量は図示を省略している。図１２においては、第１リンク生成部１４４が、各ノードについて、各ノードの直前のノードからの入力リンクのみを生成する場合について説明したが、第１リンク生成部１４４は、各ノードの直前のノードからの入力リンクに加えて、各ノードの２つ以上前のノードからの入力リンクを生成してもよい。
【０１７６】
ここでは、第１リンク生成部１４４は、ノード３Ｂについて、入力リンク（２Ａ，３Ｂ）および入力リンク（２Ｂ，３Ｂ）に加えて、ノード３Ａに対応する局舎３より前段の局舎１に対応するノード１Ａからの入力リンク（１Ａ，３Ｂ）を生成する。ノード３Ｂにおいて、入力リンク（１Ａ，３Ｂ）を選択した場合は、局舎２にはバイパスを配置する。
【０１７７】
また、第１リンク生成部１４４は、ノード４Ａについて、入力リンク（３Ａ，４Ａ）および入力リンク（３Ｂ，４Ａ）に加えて、ノード４Ａに対応する局舎４より前段の局舎１に対応するノード１Ａからの入力リンク（１Ａ，４Ａ）を生成する。ノード４Ａにおいて、入力リンク（１Ａ，４Ａ）を選択した場合は、局舎２及び３にはバイパスを配置する。
【０１７８】
このように、入力リンク（１Ａ，３Ｂ）及び入力リンク（１Ａ，４Ａ）をバイパスリンクとして生成する。ペナルティ決定部１４５は、入力リンク（１Ａ，３Ｂ）を選択した場合の伝送ペナルティ量を「７」と決定する。また、ペナルティ決定部１４５は、入力リンク（１Ａ，４Ａ）を選択した場合の伝送ペナルティ量を「２」と決定する。
以下の説明では、簡単のため、図１２に示した各入力リンクと、これらのバイパスリンクのみを生成する場合について説明する。
【０１７９】
図１４は、図８に示す第１リンク選択部１４６による入力リンクの選択処理の説明図である。図１４において、図１２および図１３に示した部分と同様の部分については同一の符号を付して説明を省略する。ここでは、ノード３Ｂへの入力リンクの選択について説明する。ノード３Ｂへの各入力リンクを太矢印で示し、他の入力リンクは細矢印で示している。第１リンク選択部１４６は、第１リンク生成部１４４によって生成されたノード３Ｂへの３つの入力リンク（２Ａ，３Ｂ）、入力リンク（２Ｂ，３Ｂ）および入力リンク（１Ａ，３Ｂ）から一つの入力リンクを選択する。
【０１８０】
ノード３Ｂへの入力リンク（２Ａ，３Ｂ）、入力リンク（２Ｂ，３Ｂ）および入力リンク（１Ａ，３Ｂ）から一つの入力リンクを選択することで、局舎３にＩＬＡを配置する場合の、局舎３の直前にＯＡＤＭまたはＩＬＡが配置される局舎までの各配置が第１ノード決定部１４７によって決定される。第１リンク選択部１４６によって入力リンク（２Ａ，３Ｂ）が選択されたときは、局舎３にＩＬＡを配置する場合に、局舎２にはＯＡＤＭが配置されることが第１ノード決定部１４７によって決定される。
【０１８１】
また、第１リンク選択部１４６によって入力リンク（２Ｂ，３Ｂ）が選択されたときは、局舎３にＩＬＡを配置する場合に、局舎２にはＩＬＡが配置されることが第１ノード決定部１４７によって決定される。また、第１リンク選択部１４６によって入力リンク（１Ａ，３Ｂ）が選択されたときは、局舎３にＩＬＡを配置する場合に、局舎２にはバイパスが配置され、局舎１にはＯＡＤＭが配置されることが第１ノード決定部１４７によって決定される。
【０１８２】
ここでは、第１リンク選択部１４６がノード３Ｂへの各入力リンクから一つの入力リンクを選択する場合について説明したが、第１リンク選択部１４６は、各ノード２Ａ〜６Ａ，２Ｂ及び５Ｂについても同様に、各入力リンクから一つの入力リンクを選択することによって、局舎１〜６を経由する波長パスに生じる伝送ペナルティの累積値が最小又は最大となる配置に対応する経路を探索する。
【０１８３】
図１５は、図８に示す第１リンク選択部１４６による選択処理の例を示すフローチャートである。図１５は、累積ペナルティ決定部１３２が、各波長パスｄｊ上において取りうる伝送ペナルティの累積値の最大値Ｐｍａｘ_k（ｄ_j）を決定する場合の処理を示す。
ステップＳ１０では、第１リンク選択部１４６は、第１ノード候補生成部１４３によって生成された各ノードＮｘ（ｘ＝１〜ｑ）を取得する。
ステップＳ１１では、第１リンク選択部１４６は、取得した各ノードＮｘのいずれかを参照するノード番号ｘを１に設定する。
【０１８４】
ステップＳ１２では、第１リンク選択部１４６は、ノードＮｘへの各入力リンクｌｉ（ｉ＝１〜ｒ）を取得する。
ステップＳ１３では、第１リンク選択部１４６は、ノードＮｘへの各入力リンクｌｉ（ｉ＝１〜ｒ）のうち、各入力リンクｌｉの始点ノードＮｉまでの累積される伝送ペナルティ量ＰＮａｃｃ（Ｎｉ）と、入力リンクｌｉの伝送ペナルティ量ＰＮ（ｌｉ）と、の合計値が最大となる入力リンクｌｉを、ノードＮｘへの入力リンクＬとして選択する。
【０１８５】
なお、累積ペナルティ決定部１３２が最小値Ｐｍｉｎ_k（ｄ_j）を決定する場合には、ステップＳ１３において、第１リンク選択部１４６は、ノードＮｘへの各入力リンクｌｉ（ｉ＝１〜ｍ）のうち、各入力リンクｌｉの始点ノードＮｉまでの累積される伝送ペナルティ量ＰＮａｃｃ（Ｎｉ）と、入力リンクｌｉの伝送ペナルティ量ＰＮ（ｌｉ）と、の合計値が最小となる入力リンクｌｉを、ノードＮｘへの入力リンクＬとして選択する。
【０１８６】
ステップＳ１４において第１リンク選択部１４６は、ノードＮｘまでの累積された伝送ペナルティ量ＰＮａｃｃ（Ｎｘ）＝ＰＮＴａｃｃ（Ｎｐｒｅ）＋ＰＮ（Ｌ）を算出する。ＰＮａｃｃ（Ｎｐｒｅ）は、ステップＳ１３によって選択された入力リンクＬの始点ノードＮｐｒｅまでの累積された伝送ペナルティ量である。また、ＰＮ（Ｌ）は、入力リンクＬを選択したときの伝送ペナルティ量である。
【０１８７】
ステップＳ１５において第１リンク選択部１４６は、ノード番号ｘが最後の番号ｑであるか否かを判断する。ノード番号ｘが最後の番号ｑでない場合には、第１リンク選択部１４６はノード番号ｘをｘ＋１に変更し（ステップＳ１６）、ステップＳ１２へ戻って処理を続行する。ノード番号ｘが最後の番号ｑである場合は、第１リンク選択部１４６は入力リンクの選択処理を終了する。
【０１８８】
図１２〜図１４に示した例において図１５の各ステップを適用した場合について説明する。図１６は、図８に示す第１リンク選択部１４６による入力リンクの選択処理の結果を示す図である。図１６において、図１２〜図１４に示した部分と同様の部分については同一の符号を付して説明を省略する。
【０１８９】
また、図１６において、矢印は、図１５に示した各ステップによって選択された入力リンクＬを示している。また、各ノードとともに、ステップＳ１２〜Ｓ１６によって算出される累積された伝送ペナルティを図示している。
【０１９０】
ノード２Ａへの入力リンクＬの決定について説明する。入力リンク（１Ａ，２Ａ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（１Ａ）＋ＰＮ（１Ａ，２Ａ）＝０＋１＝１となる。ここでは、残っている入力リンクが入力リンク（１Ａ，２Ａ）のみであるので、入力リンク（１Ａ，２Ａ）がノード２Ａへの入力リンクＬとして選択される。
【０１９１】
ノード２Ｂへの入力リンクＬの決定について説明する。入力リンク（１Ａ，２Ｂ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（１Ａ）＋ＰＮ（１Ａ，２Ｂ）＝０＋２＝２となる。ここでは、残っている入力リンクが入力リンク（１Ａ，２Ｂ）のみであるので、入力リンク（１Ａ，２Ｂ）がノード２Ｂへの入力リンクＬとして選択される。
【０１９２】
ノード３Ａへの入力リンクＬの決定について説明する。入力リンク（２Ａ，３Ａ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（２Ａ）＋ＰＮ（２Ａ，３Ａ）＝１＋１＝２となる。入力リンク（２Ｂ，３Ａ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（２Ｂ）＋ＰＮ（２Ｂ，３Ａ）＝２＋２＝４となる。したがって、伝送ペナルティ量の合計値が最大となる入力リンク（２Ｂ，３Ａ）がノード３Ａへの入力リンクＬとして選択される。
【０１９３】
ノード３Ｂへの入力リンクＬの決定について説明する。入力リンク（２Ａ，３Ｂ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（２Ａ）＋ＰＮ（２Ａ，３Ｂ）＝１＋２＝３となる。入力リンク（２Ｂ，３Ｂ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（２Ｂ）＋ＰＮ（２Ｂ，３Ｂ）＝２＋３＝５となる。入力リンク（１Ａ，３Ｂ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（１Ａ）＋ＰＮ（１Ａ，３Ｂ）＝０＋７＝７となる。したがって、伝送ペナルティ量の合計値が最大となる入力リンク（１Ａ，３Ｂ）がノード３Ｂへの入力リンクＬとして選択される。
【０１９４】
ノード４Ａへの入力リンクＬの決定について説明する。入力リンク（３Ａ，４Ａ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（３Ａ）＋ＰＮ（３Ａ，４Ａ）＝４＋１＝５となる。入力リンク（３Ｂ，４Ａ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（３Ｂ）＋ＰＮ（３Ｂ，４Ａ）＝７＋２＝９となる。入力リンク（１Ａ，４Ａ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（１Ａ）＋ＰＮ（１Ａ，４Ａ）＝０＋２＝２となる。したがって、伝送ペナルティ量の合計値が最大となる入力リンク（３Ｂ，４Ａ）がノード４Ａへの入力リンクＬとして選択される。
【０１９５】
ノード５Ａへの入力リンクＬの決定について説明する。入力リンク（４Ａ，５Ａ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（４Ａ）＋ＰＮ（４Ａ，５Ａ）＝９＋１＝１０となる。ここでは、残っている入力リンクが入力リンク（４Ａ，５Ａ）のみであるので、入力リンク（４Ａ，５Ａ）がノード５Ａへの入力リンクＬとして選択される。
【０１９６】
ノード５Ｂへの入力リンクＬの決定について説明する。入力リンク（４Ａ，５Ｂ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（４Ａ）＋ＰＮ（４Ａ，５Ｂ）＝９＋２＝１１となる。ここでは、残っている入力リンクが入力リンク（４Ａ，５Ｂ）のみであるので、入力リンク（４Ａ，５Ｂ）がノード５Ｂへの入力リンクＬとして選択される。
【０１９７】
ノード６Ａへの入力リンクＬの決定について説明する。入力リンク（５Ａ，６Ａ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（５Ａ）＋ＰＮ（５Ａ，６Ａ）＝１０＋１＝１１となる。入力リンク（５Ｂ，６Ａ）を選択したときの伝送ペナルティ量の合計値は、ＰＮａｃｃ（５Ｂ）＋ＰＮ（５Ｂ，６Ａ）＝１１＋２＝１３となる。したがって、伝送ペナルティ量の合計値が最大となる入力リンク（５Ｂ，６Ａ）がノード６Ａへの入力リンクＬとして選択される。これにより、各ノードへの入力リンクＬがそれぞれ選択される。
【０１９８】
図１７は、図８に示す第１ノード決定部１４７による経由ノードの決定処理の例を示すフローチャートである。
ステップＳ２０において第１ノード決定部１４７は、第１ノード候補生成部１４３によって生成された各ノードＮｘ（ｘ＝１〜ｑ）を取得する。
ステップＳ２１において第１ノード決定部１４７は、ステップＳ２０によって取得された各ノードＮｘのいずれかを参照するノード番号ｘをｑに設定する。ここで、ノード番号ｑは、設計対象の単位設計区間における終端局舎に配置する光伝送装置のノードを示す。
【０１９９】
ステップＳ２２において第１ノード決定部１４７は、ノードＮｑを経由ノードとして保持する。
ステップＳ２３において第１ノード決定部１４７は、図１５におけるステップＳ１３によって選択された各入力リンクＬのうちの、ノードＮｘへの入力リンクＬを取得する。
ステップＳ２４において第１ノード決定部１４７は、ステップＳ２３によって取得された入力リンクＬの始点ノードＮｐｒｅを取得する。
【０２００】
ステップＳ２５において第１ノード決定部１４７は、始点ノードＮｐｒｅを経由ノードとして保持する。
ステップＳ２６において第１ノード決定部１４７は、ステップＳ２５にて取得された始点ノードＮｐｒｅの番号ｐｒｅが番号１であるか否かを判断する。ここで、番号１は、設計対象の単位設計区間における始端局舎に配置する光伝送装置のノードの番号である。
【０２０１】
始点ノードＮｐｒｅの番号ｐｒｅが番号１でない場合に第１ノード決定部１４７は、ステップＳ２７においてノードＮｘの番号ｘを始点ノードＮｐｒｅの番号ｐｒｅに変更し、ステップＳ２３へ戻って処理を続行する。始点ノードＮｐｒｅの番号ｐｒｅが番号１である場合に第１ノード決定部１４７は、一連の経由ノード決定動作を終了する。
【０２０２】
以上の各ステップにおいて、ステップＳ２２およびステップＳ２５によって保持された各経由ノードが、設計対象の線形区間内の各局舎に対する各種の光伝送装置の配置を示す情報となる。つぎに、図１２〜図１４，図１６に示した例において、図１７に示した各ステップを適用した場合について説明する。
【０２０３】
図１８は、図８に示す第１ノード決定部１４７による経由ノードの決定処理の結果を示す図である。図１８において、図１２〜図１４，図１６に示した部分と同様の部分については同一の符号を付して説明を省略する。また、図１８において、太矢印は、図１７に示した各ステップによって遷移したノードの経路を示している。また、グラフの下段に、各ステップによって決定された光伝送装置の種類を図示している。黒丸印はバイパスを示している。
【０２０４】
まず、ノード６Ａの番号が設定され（ステップＳ２１）、ノード６Ａが経由ノードの一つとして保持される（ステップＳ２２）。また、ノード６Ａへの入力リンクＬとして入力リンク（５Ｂ，６Ａ）が取得される（ステップＳ２３）。また、入力リンク（５Ｂ，６Ａ）の始点ノードＮｐｒｅとしてノード５Ｂが取得され（ステップＳ２４）、ノード５Ｂが経由ノードの一つとして保持される（ステップＳ２５）。
つぎに、ノード５Ｂの番号が設定され（ステップＳ２７）、ノード５Ｂへの入力リンクＬとして入力リンク（４Ａ，５Ｂ）が取得される（ステップＳ２３）。また、入力リンク（４Ａ，５Ｂ）の始点ノードＮｐｒｅとしてノード４Ａが取得され（ステップＳ２４）、ノード４Ａが経由ノードの一つとして保持される（ステップＳ２５）。
【０２０５】
つぎに、ノード４Ａの番号が設定され（ステップＳ２７）、ノード４Ａへの入力リンクＬとして入力リンク（３Ｂ，４Ａ）が取得される（ステップＳ２３）。また、入力リンク（３Ｂ，４Ａ）の始点ノードＮｐｒｅとしてノード３Ｂが取得され（ステップＳ２４）、ノード３Ｂが経由ノードの一つとして保持される（ステップＳ２５）。
【０２０６】
つぎに、ノード３Ｂの番号が設定され（ステップＳ２７）、ノード３Ｂへの入力リンクＬとして入力リンク（１Ａ，３Ｂ）が取得される（ステップＳ２３）。また、入力リンク（１Ａ，３Ｂ）の始点ノードＮｐｒｅとしてノード１Ａが取得され（ステップＳ２４）、ノード１Ａが経由ノードの一つとして保持される（ステップＳ２５）。
【０２０７】
ノード１Ａのノード番号は、設計対象の線形区間２０１における始端局舎である局舎１に配置する光伝送装置のノードの番号であるため、ここで経由ノード決定動作が終了する。このように、ノード６Ａからノード１Ａまで入力リンクＬをたどりながら遡ることで、第１ノード決定部１４７は、ノード６Ａ、ノード５Ｂ、ノード４Ａ、ノード３Ｂ、ノード１Ａの順に経由ノードが保持される。
【０２０８】
累積値計算部１４２は、第１ノード決定部１４７によって保持された経由ノードを通過する経路に沿って累積する伝送ペナルティを、各経由ノードを接続する入力リンクの伝送ペナルティに基づいて決定し、雑音量上限値決定部１３３に出力する。
【０２０９】
図１１のステップＳ４において、図７に示す装置構成決定部１２４は、区間分割部１２１によって生成された各単位設計区間における光伝送装置構成の候補を決定する。図１９は、装置構成決定部１２４が各単位設計区間の光伝送装置構成を決定する決定方法の一例を示すフローチャートである。
【０２１０】
ステップＳ３０において初期候補生成部１２５は、緩和問題解決部１２７による処理に先立って、各単位設計区間について、制約条件（１−３）、又は（３−３）及び（３−４１）〜（３−４Ｒ）を満たす光伝送装置構成の候補を少なくとも１つ生成し、記憶部１２６に格納する。
【０２１１】
ステップＳ３１において緩和問題解決部１２７は、記憶部１２６に格納された装置構成候補データ１１４を読み込み、装置構成候補データ１１４が示す光伝送装置構成の候補について定めた式（１）又は（３）に示す整数計画問題の緩和問題を解決して、双対価格ベクトルを決定する。
【０２１２】
ステップＳ３２において追加候補探索部１２８は、緩和問題解決部１２７が決定した双対価格ベクトルの値に基づいて決定された被約費用の算出式にしたがって、各単位設計区間について、被約費用の値が負となる新たな光伝送装置構成の候補ｔ’を探索する。
ステップＳ３３において追加候補探索部１２８は、新たな光伝送装置構成の候補ｔ’が発見されるか否かを判定する。
新たな光伝送装置構成の候補ｔ’が発見された場合には装置構成候補データ１１４に追加して、処理をＳ３１に戻す。
新たな光伝送装置構成の候補ｔ’が発見されない場合には、ステップＳ３４において整数計画問題解決部１２９は、記憶部１２６に格納された、初期候補生成部１２５及び追加候補探索部１２８により決定された候補を含む装置構成候補データ１１４を読み込み、装置構成候補データ１１４が示す光伝送装置構成の候補について定めた式（１）又は（３）に示す整数計画問題を緩和しないで解決することにより、光ネットワーク２００の光伝送装置構成を決定する。
【０２１３】
以下、ステップＳ３０において初期候補生成部１２５が、光伝送装置構成の候補を決定する処理を説明する。図２０は、図９に示す初期候補生成部１２５の第１単位設計区間内グラフ生成部１５０が生成するグラフ情報の例を示す図（その１）である。
図２０に示す局舎１１〜１８は、図２の線形区間２０４における局舎１１〜１８である。ノード１１Ａ〜１８Ａおよびノード１２Ｂ〜１７Ｂは、第２ノード候補生成部１５２が生成した各ノードを示している。
【０２１４】
ここでは、説明の簡単のため、伝送劣化量として順方向の雑音量のみを例示して説明するが、実際には逆方向の雑音量も同様の処理によって考慮される。また、各種の伝送ペナルティも、雑音量と同様の処理によって考慮される。
雑音量の閾値ＮＯＩＳＥｔｈを７とする。局舎１１〜局舎１８に配置可能な光伝送装置のうちの光再生中継器を配置可能な光伝送装置としてＯＡＤＭ（たとえば図３のＯＡＤＭ４００）を用いる。
【０２１５】
また、局舎１１〜局舎１８に配置可能な光伝送装置のうちの光再生中継器を配置できない光伝送装置としてＩＬＡ（たとえば、図４のＩＬＡ５００）を用いる。局舎１１〜局舎１８のうちの、始端局舎である局舎１１と、終端局舎である局舎１８には、光再生中継器を配置可能なＯＡＤＭのみが配置可能である。局舎１２〜局舎１７にはＯＡＤＭ、ＩＬＡまたはバイパス（たとえば、図５のバイパス６００）が配置可能である。
【０２１６】
第２ノード候補生成部１５２は、局舎１１〜１８について、各局舎に配置可能なＯＡＤＭを示すノード１１Ａ〜ノード１８Ａをそれぞれ生成する。また、第２ノード候補生成部１５２は、局舎１２〜１７について、各局舎に配置可能なＩＬＡを示すノード１２Ｂ〜ノード１７Ｂをそれぞれ生成する。図２０において、矢印は、第２リンク生成部１５３によって生成されたノード１１Ａ〜１８Ａ，１２Ｂ〜１７Ｂ間の各入力リンクを示している。以下の説明において、ノードＹのノードＸからの入力リンクを入力リンク（Ｘ，Ｙ）と表記する。
【０２１７】
第２リンク生成部１５３は、第２ノード候補生成部１５２によって生成されたノード１１Ａは始端局舎に対応するノードであるため、ノード１１Ａへの入力リンクは生成しない。また、第２リンク生成部１５３は、ノード１２Ａについて、ノード１２Ａに対応する局舎１２より前段の局舎１１に対応するノード１１Ａからの入力リンク（１１Ａ，１２Ａ）を生成する。また、第２リンク生成部１５３は、ノード１２Ｂについて、ノード１２Ｂに対応する局舎１２より前段の局舎１１に対応するノード１１Ａからの入力リンク（１１Ａ，１２Ｂ）を生成する。
【０２１８】
また、第２リンク生成部１５３は、ノード１３Ａについて、ノード１３Ａに対応する局舎１３より前段の局舎１２に対応するノード１２Ａからの入力リンク（１２Ａ，１３Ａ）およびノード１２Ｂからの入力リンク（１２Ｂ，１３Ａ）を生成する。また、第２リンク生成部１５３は、ノード１３Ｂについて、ノード１３Ｂに対応する局舎１３より前段の局舎１２に対応するノード１２Ａからの入力リンク（１２Ａ，１３Ｂ）およびノード１２Ｂからの入力リンク（１２Ｂ，１３Ｂ）を生成する。
【０２１９】
また、第２リンク生成部１５３は、ノード１４Ａについて、ノード１４Ａに対応する局舎１４より前段の局舎１３に対応するノード１３Ａからの入力リンク（１３Ａ，１４Ａ）およびノード１３Ｂからの入力リンク（１３Ｂ，１４Ａ）を生成する。また、第２リンク生成部１５３は、ノード１４Ｂについて、ノード１４Ｂに対応する局舎１４より前段の局舎１３に対応するノード１３Ａからの入力リンク（１３Ａ，１４Ｂ）およびノード１３Ｂからの入力リンク（１３Ｂ，１４Ｂ）を生成する。
【０２２０】
また、第２リンク生成部１５３は、ノード１５Ａについて、ノード１５Ａに対応する局舎１５より前段の局舎１４に対応するノード１４Ａからの入力リンク（１４Ａ，１５Ａ）およびノード１４Ｂからの入力リンク（１４Ｂ，１５Ａ）を生成する。また、第２リンク生成部１５３は、ノード１５Ｂについて、ノード１５Ｂに対応する局舎１５より前段の局舎１４に対応するノード１４Ａからの入力リンク（１４Ａ，１５Ｂ）およびノード１４Ｂからの入力リンク（１４Ｂ，１５Ｂ）を生成する。
【０２２１】
また、第２リンク生成部１５３は、ノード１６Ａについて、ノード１６Ａに対応する局舎１６より前段の局舎１５に対応するノード１５Ａからの入力リンク（１５Ａ，１６Ａ）およびノード１５Ｂからの入力リンク（１５Ｂ，１６Ａ）を生成する。また、第２リンク生成部１５３は、ノード１６Ｂについて、ノード１６Ｂに対応する局舎１６より前段の局舎１５に対応するノード１５Ａからの入力リンク（１５Ａ，１６Ｂ）およびノード１５Ｂからの入力リンク（１５Ｂ，１６Ｂ）を生成する。
【０２２２】
また、第２リンク生成部１５３は、ノード１７Ａについて、ノード１７Ａに対応する局舎１７より前段の局舎１６に対応するノード１６Ａからの入力リンク（１６Ａ，１７Ａ）およびノード１６Ｂからの入力リンク（１６Ｂ，１７Ａ）を生成する。また、第２リンク生成部１５３は、ノード１７Ｂについて、ノード１７Ｂに対応する局舎１７より前段の局舎１６に対応するノード１６Ａからの入力リンク（１６Ａ，１７Ｂ）およびノード１６Ｂからの入力リンク（１６Ｂ，１７Ｂ）を生成する。
【０２２３】
また、第２リンク生成部１５３は、ノード１８Ａについて、ノード１８Ａに対応する局舎１８より前段の局舎１７に対応するノード１７Ａからの入力リンク（１７Ａ，１８Ａ）およびノード１７Ｂからの入力リンク（１７Ｂ，１８Ａ）を生成する。
【０２２４】
以下、図９に示すコスト決定部１５４及び伝送劣化量決定部１５５が決定するコストおよび雑音量の例を示す。図２０において、各入力リンクとともに、各入力リンクについてコスト決定部１５４及び伝送劣化量決定部１５５によって算出されたコストおよび雑音量を（コスト，雑音量）として図示している。コスト決定部１５４及び伝送劣化量決定部１５５は、第２リンク生成部１５３によって生成された入力リンク（１１Ａ，１２Ａ）を選択した場合のコストおよび雑音量を（２，１）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１１Ａ，１２Ｂ）を選択した場合のコストおよび雑音量を（１，２）と決定する。
【０２２５】
コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１２Ａ，１３Ａ）を選択した場合のコストおよび雑音量を（２，１）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１２Ｂ，１３Ａ）を選択した場合のコストおよび雑音量を（４，２）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１２Ａ，１３Ｂ）を選択した場合のコストおよび雑音量を（２，２）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１２Ｂ，１３Ｂ）を選択した場合のコストおよび雑音量を（２，３）と決定する。
【０２２６】
コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１３Ａ，１４Ａ）を選択した場合のコストおよび雑音量を（２，１）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１３Ｂ，１４Ａ）を選択した場合のコストおよび雑音量を（２，２）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１３Ａ，１４Ｂ）を選択した場合のコストおよび雑音量を（１，２）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１３Ｂ，１４Ｂ）を選択した場合のコストおよび雑音量を（２，３）と決定する。
【０２２７】
コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１４Ａ，１５Ａ）を選択した場合のコストおよび雑音量を（２，１０）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１４Ｂ，１５Ａ）を選択した場合のコストおよび雑音量を（３，１０）と決定する。ここで、入力リンク（１４Ａ，１５Ａ）および入力リンク（１４Ｂ，１５Ａ）を選択したときの雑音量は、これだけで閾値ＮＯＩＳＥｔｈの７を超えるため、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１４Ａ，１５Ａ）、入力リンク（１４Ｂ，１５Ａ）、入力リンク（１５Ａ，１６Ａ）および入力リンク（１５Ａ，１６Ｂ）を削除する。
【０２２８】
コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１４Ａ，１５Ｂ）を選択した場合のコストおよび雑音量を（２，２）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１４Ｂ，１５Ｂ）を選択した場合のコストおよび雑音量を（２，３）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１５Ｂ，１６Ａ）を選択した場合のコストおよび雑音量を（３，２）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１５Ｂ，１６Ｂ）を選択した場合のコストおよび雑音量を（２，３）と決定する。
【０２２９】
コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１６Ａ，１７Ａ）を選択した場合のコストおよび雑音量を（２，１）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１６Ｂ，１７Ａ）を選択した場合のコストおよび雑音量を（３，２）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１６Ａ，１７Ｂ）を選択した場合のコストおよび雑音量を（１，２）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１６Ｂ，１７Ｂ）を選択した場合のコストおよび雑音量を（２，３）と決定する。
【０２３０】
コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１７Ａ，１８Ａ）を選択した場合のコストおよび雑音量を（２，１）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１７Ｂ，１８Ａ）を選択した場合のコストおよび雑音量を（２，２）と決定する。これにより、局舎１１〜１８に配置するＯＡＤＭ，ＩＬＡに対応する各ノードと、伝送劣化量および雑音量と対応付けられ、各ノードを接続する各リンクと、からなるグラフ情報が生成される。
【０２３１】
図２１は、図９に示す第１単位設計区間内グラフ生成部１５０が生成するグラフ情報の例を示す図（その２）である。図２１において、図２０に示したコスト決定部１５４及び伝送劣化量決定部１５５によって算出されたコストおよび雑音量は図示を省略している。図２０においては、第２リンク生成部１５３が、各ノードについて、各ノードの直前のノードからの入力リンクのみを生成する場合について説明したが、第２リンク生成部１５３は、各ノードの直前のノードからの入力リンクに加えて、各ノードの２つ以上前のノードからの入力リンクを生成してもよい。
【０２３２】
ここでは、第２リンク生成部１５３は、ノード１３Ａについて、入力リンク（１２Ａ，１３Ａ）および入力リンク（１２Ｂ，１３Ａ）に加えて、ノード１３Ａに対応する局舎１３より前段の局舎１１に対応するノード１１Ａからの入力リンク（１１Ａ，１３Ａ）を生成する。ノード１３Ａにおいて、入力リンク（１１Ａ，１３Ａ）を選択した場合は、局舎１２にはバイパスを配置する。
【０２３３】
また、第２リンク生成部１５３は、ノード１３Ｂについて、入力リンク（１２Ａ，１３Ｂ）および入力リンク（１２Ｂ，１３Ｂ）に加えて、ノード１３Ｂに対応する局舎１３より前段の局舎１１に対応するノード１１Ａからの入力リンク（１１Ａ，１３Ｂ）を生成する。ノード１３Ｂにおいて、入力リンク（１１Ａ，１３Ｂ）を選択した場合は、局舎１２にはバイパスを配置する。
【０２３４】
また、第２リンク生成部１５３は、ノード１４Ａについて、入力リンク（１３Ａ，１４Ａ）および入力リンク（１３Ｂ，１４Ａ）に加えて、ノード１４Ａに対応する局舎１４より前段の局舎１１に対応するノード１１Ａからの入力リンク（１１Ａ，１４Ａ）を生成する。ノード１４Ａにおいて、入力リンク（１１Ａ，１４Ａ）を選択した場合は局舎１２および局舎１３にはバイパスを配置する。
【０２３５】
また、第２リンク生成部１５３は、ノード１４Ｂについて、入力リンク（１３Ａ，１４Ｂ）および入力リンク（１３Ｂ，１４Ｂ）に加えて、ノード１４Ｂに対応する局舎１４より前段の局舎１１に対応するノード１１Ａからの入力リンク（１１Ａ，１４Ｂ）と、局舎１４より前段の局舎１２に対応するノード２Ａからの入力リンク（１２Ａ，１４Ｂ）と、を生成する。
【０２３６】
ノード１４Ｂにおいて、入力リンク（１１Ａ，１４Ｂ）を選択した場合は、局舎１２および局舎１３にはバイパスを配置する。また、入力リンク（１２Ａ，１４Ｂ）を選択した場合は、局舎１３にはバイパスを配置する。このように、入力リンク（１１Ａ，１３Ａ）、入力リンク（１１Ａ，１３Ｂ）、入力リンク（１１Ａ，１４Ａ）、入力リンク（１１Ａ，１４Ｂ）および入力リンク（１２Ａ，１４Ｂ）をバイパスリンクとして生成する。
【０２３７】
コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１１Ａ，１３Ａ）を選択した場合のコストおよび雑音量を（１０，４）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１１Ａ，１３Ｂ）を選択した場合のコストおよび雑音量を（１０，５）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１１Ａ，１４Ａ）を選択した場合のコストおよび雑音量を（１０，５）と決定する。
【０２３８】
また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１１Ａ，１４Ｂ）を選択した場合のコストおよび雑音量を（１０，６）と決定する。また、コスト決定部１５４及び伝送劣化量決定部１５５は、入力リンク（１２Ａ，１４Ｂ）を選択した場合のコストおよび雑音量を（２，２）と決定する。なお、バイパスリンクは他にも生成し得るが、以下の説明では、簡単のため、図２０に示した各入力リンクと、これらのバイパスリンクのみを生成する場合について説明する。また、グラフを生成した結果、ノード１５Ａに対する入力リンクは存在しないため、コスト決定部１５４及び伝送劣化量決定部１５５はノード１５Ａを削除する。
【０２３９】
図２２は、図９に示す第２リンク選択部１５６による入力リンクの選択処理の説明図である。図２２において、図２０および図２１に示した部分と同様の部分については同一の符号を付して説明を省略する。ここでは、ノード１３Ａへの入力リンクの選択について説明する。ノード１３Ａへの各入力リンクを太矢印で示し、他の入力リンクは細矢印で示している。第２リンク選択部１５６は、第２リンク生成部１５３によって生成されたノード１３Ａへの３つの入力リンク（１２Ａ，１３Ａ）、入力リンク（１２Ｂ，１３Ａ）および入力リンク（１１Ａ，１３Ａ）から一つの入力リンクを選択する。
【０２４０】
ノード１３Ａへの入力リンク（１２Ａ，１３Ａ）、入力リンク（１２Ｂ，１３Ａ）および入力リンク（１１Ａ，１３Ａ）から一つの入力リンクを選択することで、局舎１３にＯＡＤＭを配置する場合の、局舎１３の直前にＯＡＤＭまたはＩＬＡが配置される局舎までの各配置が第２ノード決定部１５７によって決定される。第２リンク選択部１５６によって入力リンク（１２Ａ，１３Ａ）が選択されたときは、局舎１３にＯＡＤＭを配置する場合に、局舎１２にはＯＡＤＭが配置されることが第２ノード決定部１５７によって決定される。
【０２４１】
また、第２リンク選択部１５６によって入力リンク（１２Ｂ，１３Ａ）が選択されたときは、局舎１３にＯＡＤＭを配置する場合に、局舎１２にはＩＬＡが配置されることが第２ノード決定部１５７によって決定される。また、第２リンク選択部１５６によって入力リンク（１１Ａ，１３Ａ）が選択されたときは、局舎１３にＯＡＤＭを配置する場合に、局舎１２にはバイパスが配置され、局舎１１にはＯＡＤＭが配置されることが第２ノード決定部１５７によって決定される。
【０２４２】
ここでは、第２リンク選択部１５６がノード１３Ａへの各入力リンクから一つの入力リンクを選択する場合について説明したが、第２リンク選択部１５６は、各ノード１２Ａ〜１４Ａ，１６Ａ〜１８Ａ，１２Ｂ〜１７Ｂについても同様に、各入力リンクから一つの入力リンクを選択することで、伝送劣化量が閾値以下となり、コストが最小となる配置に対応する経路を探索する。
【０２４３】
図２３および図２４は、図９に示す第２リンク選択部１５６による選択処理の例を示すフローチャートである。図２３および図２４においては、伝送劣化量として、雑音量及び各種の伝送ペナルティのそれぞれの順方向成分及び逆方向成分を用いる場合について説明する。
【０２４４】
ステップＳ４０において第２リンク選択部１５６は、第２ノード候補生成部１５２によって生成された各ノードＮｘ（ｘ＝１〜ｑ）を取得する。
ステップＳ４１において第２リンク選択部１５６は、ステップＳ４０で取得された各ノードＮｘのいずれかを参照するノード番号ｘを１に設定する。
ステップＳ４２において第２リンク選択部１５６は、ノードＮｘが光再生中継器を配置可能なノードであるか否かを判断する。
【０２４５】
ステップＳ４２においてノードＮｘが光再生中継器を配置可能なノードである場合は、ステップＳ４３において第２リンク選択部１５６は、雑音量の最小値ＮＯＩＳＥｍｉｎを０に設定する。最小値ＮＯＩＳＥｍｉｎは、ノードＮｘから後段光再生ノードまでの雑音量の最小値である。またステップＳ４４において第２リンク選択部１５６は、伝送ペナルティの最小値ＰＥＮＡＬＴＹｍｉｎを０に設定にし、ステップＳ４８へ処理を移行する。最小値ＰＥＮＡＬＴＹｍｉｎは、ノードＮｘから後段光再生ノードまでの伝送ペナルティ量の最小値である。
【０２４６】
最小値ＮＯＩＳＥｍｉｎの値は、雑音量の順方向成分及び反対方向成分のそれぞれについて設定される。
また、最小値ＰＥＮＡＬＴＹｍｉｎの値は、各伝送ペナルティの種類毎に、伝送ペナルティ量の順方向成分及び反対方向成分のそれぞれについて設定される。
【０２４７】
ステップＳ４２においてノードＮｘが光再生中継器を適用可能なノードでない場合は、ステップＳ４５において第２リンク選択部１５６は、ノードＮｘのつぎの後段光再生ノードまでの雑音最小経路を探索する。ノードＮｘのつぎの後段光再生ノードまでの雑音最小経路とは、ノードＮｘの後段光再生ノードのうちの、ノードＮｘまでの入力リンクの雑音量の合計が最小となる後段光再生ノードまでの経路である。
【０２４８】
ステップＳ４６において第２リンク選択部１５６は、順方向成分及び反対方向成分のそれぞれについて雑音量の最小値ＮＯＩＳＥｍｉｎを、ステップＳ４５によって探索した雑音最小経路の雑音量に設定する。
ステップＳ４７において第２リンク選択部１５６は、各伝送ペナルティの種類毎かつ順方向成分及び反対方向成分のそれぞれについて、伝送ペナルティの最小値ＰＥＮＡＬＴＹｍｉｎを、ステップＳ４５によって探索した雑音最小経路の伝送ペナルティに設定する。
【０２４９】
ステップＳ４８において第２リンク選択部１５６は、ノードＮｘへの各入力リンクｌｉ（ｉ＝１〜ｒ）を取得する。ここでは、ＰＥＮＡＬＴＹｍｉｎを雑音最小経路上の値としているが、別途伝送ペナルティの最小経路を探索し、その経路上の値としてもよい。
【０２５０】
ステップＳ４９において第２リンク選択部１５６は、ステップＳ４８によって取得した各入力リンクｌｉを参照する入力リンク番号ｉを１に設定する。
ステップＳ５０において第２リンク選択部１５６は、順方向成分及び反対方向成分のそれぞれについて、入力リンクｌｉの始点ノードＮｉまでの累積雑音ＮＯＩＳＥａｃｃ（Ｎｉ）と、入力リンクｌｉを選択したときの雑音ＮＯＩＳＥ（ｌｉ）と、ステップＳ４３またはステップＳ４６によって設定した雑音量の最小値ＮＯＩＳＥｍｉｎと、の合計値が雑音閾値ＮＯＩＳＥｔｈ以下か否かを判断する。
第２リンク選択部１５６は、雑音閾値ＮＯＩＳＥｔｈとして、単位設計区間内雑音量上限値決定部１３４が決定した単位設計区間内雑音量上限値Ｎｔｈ１（ｇ_h）及びＮｔｈ２（ｇ_h）を使用する。
【０２５１】
ステップＳ５０において順方向成分及び反対方向成分の双方について、合計値が雑音閾値ＮＯＩＳＥｔｈ以下である場合は、処理はステップＳ５１へ進む。
ステップＳ５１において第２リンク選択部１５６は、各伝送ペナルティの種類毎に、かつ順方向成分及び反対方向成分のそれぞれについて、入力リンクｌｉの始点ノードＮｉまでの累積伝送ペナルティＰＥＮＡＬＴＹａｃｃ（Ｎｉ）と、入力リンクｌｉを選択したときの伝送ペナルティＰＥＮＡＬＴＹ（ｌｉ）と、ステップＳ４４またはステップＳ４７によって設定した伝送ペナルティの最小値ＰＥＮＡＬＴＹｍｉｎと、の合計値が伝送ペナルティ閾値ＰＥＮＡＬＴＹｔｈ以下か否かを判断する。
第２リンク選択部１５６は、伝送ペナルティ閾値ＰＥＮＡＬＴＹｔｈとして、単位設計区間内ペナルティ上限値決定部１３１が決定した単位設計区間内ペナルティ上限値Ｐｔｈ１_k（ｇ_h）及びＰｔｈ２_k（ｇ_h）を使用する。
【０２５２】
ステップＳ５０において、順方向成分及び反対方向成分のいずれかについて、合計値が雑音閾値ＮＯＩＳＥｔｈより大きい場合には、処理はステップＳ５２へ進む。
また、ステップＳ５１において、各種類の伝送ペナルティのいずれかについて、順方向成分及び反対方向成分のいずれかの合計値が伝送ペナルティ閾値ＰＥＮＡＬＴＹｔｈより大きい場合には、処理はステップＳ５２へ進む。
ステップＳ５２において第２リンク選択部１５６は、ステップＳ４８によって取得した各入力リンクから入力リンクｌｉを削除し、処理をステップＳ５３へ進める。
【０２５３】
ステップＳ５１において、各種類の伝送ペナルティのいずれかについても、順方向成分及び反対方向成分の合計値の双方が、伝送ペナルティ閾値ＰＥＮＡＬＴＹｔｈ以下である場合は、ステップＳ５３において第２リンク選択部１５６は、入力リンク番号ｉが最後の番号ｒであるか否かを判断する。
入力リンク番号ｉが最後の番号ｒでない場合は、ステップＳ５４において第２リンク選択部１５６は、入力リンク番号ｉをｉ＋１に変更し、ステップＳ５０へ戻って処理を続行する。
【０２５４】
ステップＳ５３において入力リンク番号ｉが最後の番号ｒである場合は、処理は図２４のステップＳ５５へ進む（符号Ａ）。
ステップＳ５５において第２リンク選択部１５６は、ステップＳ４８によって取得され、ステップＳ５２によって削除されていない入力リンクｌｉのうちの、始点ノードＮｉまでの累積コストＣＯＳＴａｃｃ（Ｎｉ）と、入力リンクｌｉのコストＣＯＳＴ（ｌｉ）と、の合計値が最小となる入力リンクｌｉを、ノードＮｘへの入力リンクＬとして選択する。
【０２５５】
ステップＳ５６において第２リンク選択部１５６は、ノードＮｘまでの累積コストＣＯＳＴａｃｃ（Ｎｘ）＝ＣＯＳＴａｃｃ（Ｎｐｒｅ）＋ＣＯＳＴ（Ｌ）を算出する。ＣＯＳＴａｃｃ（Ｎｐｒｅ）は、ステップＳ５５によって選択された入力リンクＬの始点ノードＮｐｒｅまでの累積コストである。また、ＣＯＳＴ（Ｌ）は、入力リンクＬを選択したときのコストである。
【０２５６】
ステップＳ５７において第２リンク選択部１５６は、ノードＮｘが光再生中継器を配置可能なノードであるか否かを判断する（ステップＳ５７）。光再生中継器を適用可能なノードである場合、ステップＳ５８において第２リンク選択部１５６は、順方向成分及び反対方向成分の双方についてノードＮｘまでの累積雑音ＮＯＩＳＥａｃｃ（Ｎｘ）を０に設定する。続くステップＳ５９において第２リンク選択部１５６は、各伝送ペナルティの種類毎かつ順方向成分及び反対方向成分のそれぞれについて、ノードＮｘまでの累積伝送ペナルティＰＥＮＡＬＴＹａｃｃ（Ｎｘ）を０に設定する。その後、処理はステップＳ６２へ進む。
【０２５７】
ステップＳ５７の判定においてノードＮｘが光再生中継器を配置可能なノードでない場合は、ステップＳ６０において第２リンク選択部１５６は、順方向成分及び反対方向成分の双方について、ノードＮｘまでの累積雑音ＮＯＩＳＥａｃｃ（Ｎｘ）を、ノードＮｐｒｅまでの累積雑音ＮＯＩＳＥａｃｃ（Ｎｐｒｅ）と、入力リンクＬの雑音ＮＯＩＳＥ（Ｌ）と、の合計値に設定する。
【０２５８】
続くステップＳ６１において第２リンク選択部１５６は、各伝送ペナルティの種類毎かつ順方向成分及び反対方向成分のそれぞれについて、ノードＮｘまでの累積伝送ペナルティＰＥＮＡＬＴＹａｃｃ（Ｎｘ）を、ＰＥＮＡＬＴＹａｃｃ（Ｎｐｒｅ）＋ＰＥＮＡＬＴＹ（Ｌ）に設定する。ＰＥＮＡＬＴＹａｃｃ（Ｎｐｒｅ）は、ノードＮｐｒｅまでの累積伝送ペナルティである。ＰＥＮＡＬＴＹ（Ｌ）は、入力リンクＬの伝送ペナルティである。
【０２５９】
ステップＳ６２において第２リンク選択部１５６は、ノード番号ｘが最後の番号ｑであるか否かを判断する。ステップＳ６２においてノード番号ｘが最後の番号ｑでない場合は、ノード番号ｘをｘ＋１に変更し、図２３のステップＳ４２へ戻って（符号Ｂ）処理を続行する。ノード番号ｘが最後の番号ｑである場合は、入力リンク選択動作を終了する。
【０２６０】
以上の各ステップによって、第２ノード候補生成部１５２によって生成された各ノードＮｘへの入力リンクＬがそれぞれ選択される。つぎに、図２０〜図２２に示した例において図２３および図２４の各ステップを適用した場合について説明する。簡単のため、伝送劣化量の代表として順方向の雑音量のみを用いて説明する。したがって、図２３及び図２４のステップＳ４４、Ｓ４７、Ｓ５１、Ｓ５９及びＳ６１については説明を省略する。
【０２６１】
図２５は、図９に示す第２リンク選択部１５６による入力リンクの選択処理の結果を示す図である。図２５において、図２０〜図２２に示した部分と同様の部分については同一の符号を付して説明を省略する。また、図２５において、矢印は、図２３及び図２４に示した各ステップによって選択された入力リンクＬを示している。また、各ノードとともに、ステップＳ５５〜Ｓ６１によって算出される累積コストＣＯＳＴａｃｃおよび累積雑音ＮＯＩＳＥａｃｃを（累積コスト，累積雑音量）として図示している。
【０２６２】
ノード１２Ａへの入力リンクＬの決定について説明する。ノード１２ＡはＯＡＤＭに対応するノードであるため、雑音量の最小値ＮＯＩＳＥｍｉｎは０となる（ステップＳ４３）。また、ノード１２Ａへの各入力リンクとして入力リンク（１１Ａ，１２Ａ）のみが取得される（ステップＳ４８）。
【０２６３】
入力リンク（１１Ａ，１２Ａ）を選択したときの雑音量の合計値はＮＯＩＳＥａｃｃ（１１Ａ）＋ＮＯＩＳＥ（１１Ａ，１２Ａ）＋ＮＯＩＳＥｍｉｎ＝０＋１＋０＝１となる（ステップＳ５０）。この合計値は雑音閾値ＮＯＩＳＥｔｈの７以下であるため、入力リンク（１１Ａ，１２Ａ）は削除されない（ステップＳ５２）。
【０２６４】
入力リンク（１１Ａ，１２Ａ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１１Ａ）＋ＣＯＳＴ（１１Ａ，１２Ａ）＝０＋２＝２となる（ステップＳ５５）。ここでは、残っている入力リンクが入力リンク（１１Ａ，１２Ａ）のみであるので、入力リンク（１１Ａ，１２Ａ）がノード１２Ａへの入力リンクＬとして選択される（ステップＳ５５）。
【０２６５】
ノード１２Ａまでの累積コストＣＯＳＴａｃｃ（１２Ａ）は、ＣＯＳＴａｃｃ（１１Ａ）＋ＣＯＳＴ（１１Ａ，１２Ａ）＝０＋２＝２となる（ステップＳ５６）。ノード１２ＡはＯＡＤＭに対応するノードであるため、ノード１２Ａまでの累積雑音ＮＯＩＳＥａｃｃ（１２Ａ）は０となる（ステップＳ５８）。
【０２６６】
ノード１２Ｂへの入力リンクＬの決定について説明する。ノード１２ＢはＩＬＡに対応するノードであるため、ノード１２Ｂの後段光再生ノードまでの雑音最小経路としてノード１２Ｂからノード１３Ａまでの経路が探索され（ステップＳ４５）、雑音量の最小値ＮＯＩＳＥｍｉｎは２となる（ステップＳ４６）。また、ノード１２Ｂへの各入力リンクとして、入力リンク（１１Ａ，１２Ｂ）のみが取得される（ステップＳ４８）。
【０２６７】
入力リンク（１１Ａ，１２Ｂ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１１Ａ）＋ＮＯＩＳＥ（１１Ａ，１２Ｂ）＋ＮＯＩＳＥｍｉｎ＝０＋２＋２＝４となる（ステップＳ５０）。この入力リンク（１１Ａ，１２Ｂ）を選択したときの雑音量の合計値は雑音閾値ＮＯＩＳＥｔｈの７以下であるため、入力リンク（１１Ａ，１２Ｂ）は削除されない（ステップＳ５２）。
【０２６８】
入力リンク（１１Ａ，１２Ｂ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１１Ａ）＋ＣＯＳＴ（１１Ａ，１２Ｂ）＝０＋１＝１となる（ステップＳ５５）。ここでは、残っている入力リンクが入力リンク（１１Ａ，１２Ｂ）のみであるので、入力リンク（１１Ａ，１２Ｂ）がノード１２Ｂへの入力リンクＬとして選択される（ステップＳ５５）。
【０２６９】
ノード１２Ｂまでの累積コストＣＯＳＴａｃｃ（１２Ｂ）は、ＣＯＳＴａｃｃ（１１Ａ）＋ＣＯＳＴ（１１Ａ，１２Ｂ）＝０＋１＝１となる（ステップＳ５６）。ノード１２ＢはＩＬＡに対応するノードであるため、ノード１２Ｂまでの累積雑音ＮＯＩＳＥａｃｃ（１２Ｂ）は、ＮＯＩＳＥａｃｃ（１１Ａ）＋ＮＯＩＳＥ（１１Ａ，１２Ｂ）＝０＋２＝２となる（ステップＳ６０）。
【０２７０】
つぎに、ノード１３Ａへの入力リンクＬの決定について説明する。ノード１３ＡはＯＡＤＭに対応するノードであるため、雑音量の最小値ＮＯＩＳＥｍｉｎは０となる（ステップＳ４３）。また、ノード１３Ａへの各入力リンクとして、入力リンク（１２Ａ，１３Ａ）と、入力リンク（１２Ｂ，１３Ａ）と、入力リンク（１１Ａ，１３Ａ）と、が取得される（ステップＳ４８）。
【０２７１】
入力リンク（１２Ａ，１３Ａ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１２Ａ）＋ＮＯＩＳＥ（１２Ａ，１３Ａ）＋ＮＯＩＳＥｍｉｎ＝０＋１＋０＝１となる（ステップＳ５０）。また、入力リンク（１２Ｂ，１３Ａ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１２Ｂ）＋ＮＯＩＳＥ（１２Ｂ，１３Ａ）＋ＮＯＩＳＥｍｉｎ＝２＋２＋０＝４となる（ステップＳ５０）。
【０２７２】
また、入力リンク（１１Ａ，１３Ａ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１１Ａ）＋ＮＯＩＳＥ（１１Ａ，１３Ａ）＋ＮＯＩＳＥｍｉｎ＝０＋４＋０＝４となる（ステップＳ５０）。これらの合計値は雑音閾値ＮＯＩＳＥｔｈの７以下であるため、入力リンク（１２Ａ，１３Ａ）、入力リンク（１２Ｂ，１３Ａ）および入力リンク（１１Ａ，１３Ａ）はいずれも削除されない（ステップＳ５２）。
【０２７３】
入力リンク（１２Ａ，１３Ａ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１２Ａ）＋ＣＯＳＴ（１２Ａ，１３Ａ）＝２＋２＝４となる。また、入力リンク（１２Ｂ，１３Ａ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１２Ｂ）＋ＣＯＳＴ（１２Ｂ，１３Ａ）＝１＋４＝５となる。また、入力リンク（１１Ａ，１３Ａ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１１Ａ）＋ＣＯＳＴ（１１Ａ，１３Ａ）＝０＋１０＝１０となる。したがって、コストの合計値が最小となる入力リンク（１２Ａ，１３Ａ）がノード１３Ａへの入力リンクＬとして選択される（ステップＳ５５）。
【０２７４】
ノード１３Ａまでの累積コストＣＯＳＴａｃｃ（１３Ａ）は、ＣＯＳＴａｃｃ（１２Ａ）＋ＣＯＳＴ（１２Ａ，１３Ａ）＝２＋２＝４となる（ステップＳ５６）。ノード１３ＡはＯＡＤＭに対応するノードであるため、ノード１３Ａまでの累積雑音ＮＯＩＳＥａｃｃ（１３Ａ）は０となる（ステップＳ５８）。
【０２７５】
ノード１３Ｂへの入力リンクＬの決定について説明する。ノード１３ＢはＩＬＡに対応するノードであるため、雑音最小経路としてノード１３Ｂからノード１４Ａまでの経路が探索され（ステップＳ４５）、雑音量の最小値ＮＯＩＳＥｍｉｎは２となる（ステップＳ４６）。また、ノード１３Ｂへの各入力リンクとして、入力リンク（１２Ａ，１３Ｂ）と、入力リンク（１２Ｂ，１３Ｂ）と、入力リンク（１１Ａ，１３Ｂ）と、が取得される（ステップＳ４８）。
【０２７６】
入力リンク（１２Ａ，１３Ｂ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１２Ａ）＋ＮＯＩＳＥ（１２Ａ，１３Ｂ）＋ＮＯＩＳＥｍｉｎ＝０＋２＋２＝４となる（ステップＳ５０）。また、入力リンク（１２Ｂ，１３Ｂ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１２Ｂ）＋ＮＯＩＳＥ（１２Ｂ，１３Ｂ）＋ＮＯＩＳＥｍｉｎ＝２＋３＋２＝７となる（ステップＳ５０）。
【０２７７】
また、入力リンク（１１Ａ，１３Ｂ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１１Ａ）＋ＮＯＩＳＥ（１１Ａ，１３Ｂ）＋ＮＯＩＳＥｍｉｎ＝０＋５＋２＝７となる（ステップＳ５０）。これらの合計値は雑音閾値ＮＯＩＳＥｔｈの７以下であるため、入力リンク（１２Ａ，１３Ｂ）、入力リンク（１２Ｂ，１３Ｂ）および入力リンク（１１Ａ，１３Ｂ）はいずれも削除されない（ステップＳ５２）。
【０２７８】
入力リンク（１２Ａ，１３Ｂ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１２Ａ）＋ＣＯＳＴ（１２Ａ，１３Ｂ）＝２＋２＝４となる。また、入力リンク（１２Ｂ，１３Ｂ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１２Ｂ）＋ＣＯＳＴ（１２Ｂ，１３Ｂ）＝１＋２＝３となる。また、入力リンク（１１Ａ，１３Ｂ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１１Ａ）＋ＣＯＳＴ（１１Ａ，１３Ｂ）＝０＋１０＝１０となる。したがって、コストの合計値が最小となる入力リンク（１２Ｂ，１３Ｂ）がノード１３Ｂへの入力リンクＬとして選択される（ステップＳ５５）。
【０２７９】
ノード１３Ｂまでの累積コストＣＯＳＴａｃｃ（１３Ｂ）は、ＣＯＳＴａｃｃ（１２Ｂ）＋ＣＯＳＴ（１２Ｂ，１３Ｂ）＝１＋２＝３となる（ステップＳ５６）。ノード１３ＢはＩＬＡに対応するノードであるため、ノード１３Ｂまでの累積雑音ＮＯＩＳＥａｃｃ（１３Ｂ）は、ＮＯＩＳＥａｃｃ（１２Ｂ）＋ＮＯＩＳＥ（１２Ｂ，１３Ｂ）＝２＋３＝５となる（ステップＳ６０）。
【０２８０】
つぎに、ノード１４Ａへの入力リンクＬの決定について説明する。ノード１４ＡはＯＡＤＭに対応するノードであるため、雑音量の最小値ＮＯＩＳＥｍｉｎは０となる（ステップＳ４３）。また、ノード１４Ａへの各入力リンクとして、入力リンク（１３Ａ，１４Ａ）と、入力リンク（１３Ｂ，１４Ａ）と、入力リンク（１１Ａ，１４Ａ）と、が取得される（ステップＳ４８）。
【０２８１】
入力リンク（１３Ａ，１４Ａ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１３Ａ）＋ＮＯＩＳＥ（１３Ａ，１４Ａ）＋ＮＯＩＳＥｍｉｎ＝０＋１＋０＝１となる（ステップＳ５０）。また、入力リンク（１３Ｂ，１４Ａ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１３Ｂ）＋ＮＯＩＳＥ（１３Ｂ，１４Ａ）＋ＮＯＩＳＥｍｉｎ＝５＋２＋０＝７となる（ステップＳ５０）。
【０２８２】
また、入力リンク（１１Ａ，１４Ａ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１１Ａ）＋ＮＯＩＳＥ（１１Ａ，１４Ａ）＋ＮＯＩＳＥｍｉｎ＝０＋５＋０＝５となる（ステップＳ５０）。これらの雑音量の合計値はいずれも雑音閾値ＮＯＩＳＥｔｈの７以下であるため、入力リンク（１３Ａ，１４Ａ）、入力リンク（１３Ｂ，１４Ａ）および入力リンク（１１Ａ，１４Ａ）はいずれも削除されない（ステップＳ５２）。
【０２８３】
入力リンク（１３Ａ，１４Ａ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１３Ａ）＋ＣＯＳＴ（１３Ａ，１４Ａ）＝４＋２＝６となる。また、入力リンク（１３Ｂ，１４Ａ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１３Ｂ）＋ＣＯＳＴ（１３Ｂ，１４Ａ）＝３＋２＝５となる。また、入力リンク（１１Ａ，１４Ａ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１１Ａ）＋ＣＯＳＴ（１１Ａ，１４Ａ）＝０＋１０＝１０となる。したがって、コストの合計値が最小となる入力リンク（１３Ｂ，１４Ａ）がノード１４Ａへの入力リンクＬとして選択される（ステップＳ５５）。
【０２８４】
ノード１４Ａまでの累積コストＣＯＳＴａｃｃ（１４Ａ）は、ＣＯＳＴａｃｃ（１３Ｂ）＋ＣＯＳＴ（１３Ｂ，１４Ａ）＝３＋２＝５となる（ステップＳ５６）。ノード１４ＡはＯＡＤＭに対応するノードであるため、ノード１４Ａまでの累積雑音ＮＯＩＳＥａｃｃ（１４Ａ）は０となる（ステップＳ５８）。
【０２８５】
ノード１４Ｂへの入力リンクＬの決定について説明する。ノード１４ＢはＩＬＡに対応するノードであるため、ノード１４Ｂの後段光再生ノードまでの雑音最小経路としてノード１４Ｂからノード６Ａまでの経路が探索され（ステップＳ４５）、雑音量の最小値ＮＯＩＳＥｍｉｎは３＋２＝５となる（ステップＳ４６）。また、ノード１４Ｂへの各入力リンクとして、入力リンク（１３Ａ，１４Ｂ）と、入力リンク（１３Ｂ，１４Ｂ）と、入力リンク（１１Ａ，１４Ｂ）と、入力リンク（１２Ａ，１４Ｂ）と、が取得される（ステップＳ４８）。
【０２８６】
入力リンク（１３Ａ，１４Ｂ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１３Ａ）＋ＮＯＩＳＥ（１３Ａ，１４Ｂ）＋ＮＯＩＳＥｍｉｎ＝０＋２＋５＝７となる（ステップＳ５０）。また、入力リンク（１３Ｂ，１４Ｂ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１３Ｂ）＋ＮＯＩＳＥ（１３Ｂ，１４Ｂ）＋ＮＯＩＳＥｍｉｎ＝５＋３＋５＝１３となる（ステップＳ５０）。また、入力リンク（１１Ａ，１４Ｂ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１１Ａ）＋ＮＯＩＳＥ（１１Ａ，１４Ｂ）＋ＮＯＩＳＥｍｉｎ＝０＋６＋５＝１１となる（ステップＳ５０）。
【０２８７】
また、入力リンク（１２Ａ，１４Ｂ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１２Ａ）＋ＮＯＩＳＥ（１２Ａ，１４Ｂ）＋ＮＯＩＳＥｍｉｎ＝０＋２＋５＝７となる（ステップＳ５０）。雑音量の合計値が、雑音閾値ＮＯＩＳＥｔｈの７よりも大きい入力リンク（１３Ｂ，１４Ｂ）および入力リンク（１１Ａ，１４Ｂ）は削除される（ステップＳ５２）。
【０２８８】
入力リンク（１３Ａ，１４Ｂ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１３Ａ）＋ＣＯＳＴ（１３Ａ，１４Ｂ）＝４＋１＝５となる（ステップＳ５５）。また、入力リンク（１２Ａ，１４Ｂ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１２Ａ）＋ＣＯＳＴ（１２Ａ，１４Ｂ）＝２＋２＝４となる。したがって、コストの合計値が最小となる入力リンク（１２Ａ，１４Ｂ）がノード１４Ｂへの入力リンクＬとして選択される（ステップＳ５５）。
【０２８９】
ノード１４Ｂまでの累積コストＣＯＳＴａｃｃ（１４Ｂ）は、ＣＯＳＴａｃｃ（１２Ａ）＋ＣＯＳＴ（１２Ａ，１４Ｂ）＝２＋２＝４となる（ステップＳ５６）。ノード１４ＢはＩＬＡに対応するノードであるため、ノード１４Ｂまでの累積雑音ＮＯＩＳＥａｃｃ（１４Ｂ）は、ＮＯＩＳＥａｃｃ（１２Ａ）＋ＮＯＩＳＥ（１２Ａ，１４Ｂ）＝０＋２＝２となる（ステップＳ６０）。
【０２９０】
つぎに、ノード１５Ｂへの入力リンクＬの決定について説明する。ノード１５ＢはＩＬＡに対応するノードであるため、ノード１５Ｂの後段光再生ノードまでの雑音最小経路としてノード１５Ｂからノード６Ａまでの経路が探索され（ステップＳ４５）、雑音量の最小値ＮＯＩＳＥｍｉｎが２となる（ステップＳ４６）。また、ノード１５Ｂへの各入力リンクとして、入力リンク（１４Ａ，１５Ｂ）と、入力リンク（１４Ｂ，１５Ｂ）と、が取得される（ステップＳ４８）。
【０２９１】
入力リンク（１４Ａ，１５Ｂ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１４Ａ）＋ＮＯＩＳＥ（１４Ａ，１５Ｂ）＋ＮＯＩＳＥｍｉｎ＝０＋２＋２＝４となる（ステップＳ５０）。また、入力リンク（１４Ｂ，１５Ｂ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１４Ｂ）＋ＮＯＩＳＥ（１４Ｂ，１５Ｂ）＋ＮＯＩＳＥｍｉｎ＝２＋３＋２＝７となる。これらの合計値はいずれも雑音閾値ＮＯＩＳＥｔｈの７以下であるため、入力リンク（１４Ａ，１５Ｂ）および入力リンク（１４Ｂ，１５Ｂ）は削除されない（ステップＳ５２）。
【０２９２】
入力リンク（１４Ａ，１５Ｂ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１４Ａ）＋ＣＯＳＴ（１４Ａ，１５Ｂ）＝５＋２＝７となる（ステップＳ５５）。また、入力リンク（１４Ｂ，１５Ｂ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１４Ｂ）＋ＣＯＳＴ（１４Ｂ，１５Ｂ）＝４＋２＝６となる。したがって、コストの合計値が最小となる入力リンク（１４Ｂ，１５Ｂ）がノード１５Ｂへの入力リンクＬとして選択される（ステップＳ５５）。
【０２９３】
ノード１５Ｂまでの累積コストＣＯＳＴａｃｃ（１５Ｂ）は、ＣＯＳＴａｃｃ（１４Ｂ）＋ＣＯＳＴ（１４Ｂ，１５Ｂ）＝４＋２＝６となる（ステップＳ５６）。ノード１５ＢはＩＬＡに対応するノードであるため、ノード１５Ｂまでの累積雑音ＮＯＩＳＥａｃｃ（１５Ｂ）は、ＮＯＩＳＥａｃｃ（１４Ｂ）＋ＮＯＩＳＥ（１４Ｂ，１５Ｂ）＝２＋３＝５となる（ステップＳ６０）。
【０２９４】
つぎに、ノード１６Ａへの入力リンクＬの決定について説明する。ノード１６ＡはＯＡＤＭに対応するノードであるため、雑音量の最小値ＮＯＩＳＥｍｉｎは０となる（ステップＳ４３）。また、ノード１６Ａへの各入力リンクとして、入力リンク（１５Ｂ，１６Ａ）のみが取得される（ステップＳ４８）。
【０２９５】
入力リンク（１５Ｂ，１６Ａ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１５Ｂ）＋ＮＯＩＳＥ（１５Ｂ，１６Ａ）＋ＮＯＩＳＥｍｉｎ＝５＋２＋０＝７となる（ステップＳ５０）。この入力リンク（１５Ｂ，１６Ａ）を選択したときの雑音量の合計値は雑音閾値ＮＯＩＳＥｔｈの７以下であるため、入力リンク（１５Ｂ，１６Ａ）は削除されない（ステップＳ５２）。
【０２９６】
入力リンク（１５Ｂ，１６Ａ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１５Ｂ）＋ＣＯＳＴ（１５Ｂ，１６Ａ）＝６＋３＝９となる（ステップＳ５５）。ここでは、残っている入力リンクが入力リンク（１５Ｂ，１６Ａ）のみであるので、入力リンク（１５Ｂ，１６Ａ）がノード１６Ａへの入力リンクＬとして選択される（ステップＳ５５）。
【０２９７】
ノード１６Ａまでの累積コストＣＯＳＴａｃｃ（１６Ａ）は、ＣＯＳＴａｃｃ（１５Ｂ）＋ＣＯＳＴ（１５Ｂ，１６Ａ）＝６＋３＝９となる（ステップＳ５６）。ノード１６ＡはＯＡＤＭに対応するノードであるため、ノード１６Ａまでの累積雑音ＮＯＩＳＥａｃｃ（１６Ａ）は０となる（ステップＳ５８）。
【０２９８】
つぎに、ノード１６Ｂへの入力リンクＬの決定について説明する。ステップＳ４２において、ノード１６ＢはＩＬＡに対応するノードであるため、ノード１７Ａまでの経路が探索され（ステップＳ４５）、雑音量の最小値ＮＯＩＳＥｍｉｎが２となる（ステップＳ４６）。また、ノード１６Ｂへの各入力リンクとして、入力リンク（１５Ｂ，１６Ｂ）のみが取得される（ステップＳ４８）。
【０２９９】
入力リンク（１５Ｂ，１６Ｂ）を選択したときの雑音量の合計値はＮＯＩＳＥａｃｃ（１５Ｂ）＋ＮＯＩＳＥ（１５Ｂ，１６Ｂ）＋ＮＯＩＳＥｍｉｎ＝５＋３＋２＝１０となる（ステップＳ５０）。この合計値は雑音閾値ＮＯＩＳＥｔｈの７よりも大きいため、入力リンク（１５Ｂ，１６Ｂ）は削除される（ステップＳ５２）。
【０３００】
ここでは、ステップＳ４８によって取得した各入力リンクのすべてが削除されたため、ノード１６ＢについてはステップＳ５５以降の処理を行わない。また、第２リンク生成部１５３によって生成された各入力リンクから、ノード１６Ｂを始点ノードとする入力リンク（１６Ｂ，１７Ａ）および入力リンク（１６Ｂ，１７Ｂ）を削除する。
【０３０１】
つぎに、ノード１７Ａへの入力リンクＬの決定について説明する。ノード１７ＡはＯＡＤＭに対応するノードであるため、雑音量の最小値ＮＯＩＳＥｍｉｎは０となる（ステップＳ４３）。また、ノード１７Ａへの各入力リンクとして、入力リンク（１６Ａ，１７Ａ）のみが取得される（ステップＳ４８）。
【０３０２】
入力リンク（１６Ａ，１７Ａ）を選択したときの雑音量の合計値はＮＯＩＳＥａｃｃ（１６Ａ）＋ＮＯＩＳＥ（１６Ａ，１７Ａ）＋ＮＯＩＳＥｍｉｎ＝０＋１＋０＝１となる（ステップＳ５０）。この合計値は雑音閾値ＮＯＩＳＥｔｈの７以下であるため、入力リンク（１６Ａ，１７Ａ）は削除されない（ステップＳ５２）。
【０３０３】
入力リンク（１６Ａ，１７Ａ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１６Ａ）＋ＣＯＳＴ（１６Ａ，１７Ａ）＝９＋２＝１１となる（ステップＳ５５）。ここでは、残っている入力リンクが入力リンク（１６Ａ，１７Ａ）のみであるので、入力リンク（１６Ａ，１７Ａ）がノード１７Ａへの入力リンクＬとして選択される（ステップＳ５５）。
【０３０４】
ノード１７Ａまでの累積コストＣＯＳＴａｃｃ（１７Ａ）は、ＣＯＳＴａｃｃ（１６Ａ）＋ＣＯＳＴ（１６Ａ，１７Ａ）＝９＋２＝１１となる（ステップＳ５６）。ノード１７ＡはＯＡＤＭに対応するノードであるため、ノード１７Ａまでの累積雑音ＮＯＩＳＥａｃｃ（１７Ａ）は０となる（ステップＳ５８）。
【０３０５】
つぎに、ノード１７Ｂへの入力リンクＬの決定について説明する。ノード１７ＢはＩＬＡに対応するノードであるため、ノード１７Ｂの後段で光再生中継器を適用可能なノードまでの雑音最小経路としてノード１７Ｂからノード８Ａまでの経路が探索され（ステップＳ４５）、雑音量の最小値ＮＯＩＳＥｍｉｎが２となる（ステップＳ４６）。また、ノード１７Ｂへの各入力リンクとして、入力リンク（１６Ａ，１７Ｂ）のみが取得される（ステップＳ４８）。
【０３０６】
入力リンク（１６Ａ，１７Ｂ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１６Ａ）＋ＮＯＩＳＥ（１６Ａ，１７Ｂ）＋ＮＯＩＳＥｍｉｎ＝０＋２＋２＝４となる（ステップＳ５０）。この入力リンク（１６Ａ，１７Ｂ）を選択したときの雑音量の合計値は雑音閾値ＮＯＩＳＥｔｈの７以下であるため、入力リンク（１６Ａ，１７Ｂ）は削除されない（ステップＳ５２）。
【０３０７】
入力リンク（１６Ａ，１７Ｂ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１６Ａ）＋ＣＯＳＴ（１６Ａ，１７Ｂ）＝９＋１＝１０となる（ステップＳ５５）。ここでは、残っている入力リンクが入力リンク（１６Ａ，１７Ｂ）のみであるので、入力リンク（１６Ａ，１７Ｂ）がノード１７Ｂへの入力リンクＬとして選択される（ステップＳ５５）。
【０３０８】
ノード１７Ｂまでの累積コストＣＯＳＴａｃｃ（１７Ｂ）は、ＣＯＳＴａｃｃ（１６Ａ）＋ＣＯＳＴ（１６Ａ，１７Ｂ）＝９＋１＝１０となる（ステップＳ５６）。ノード１７ＢはＩＬＡに対応するノードであるため、ノード１７Ｂまでの累積雑音ＮＯＩＳＥａｃｃ（１７Ｂ）は、ＮＯＩＳＥａｃｃ（１６Ａ）＋ＮＯＩＳＥ（１６Ａ，１７Ｂ）＝０＋２＝２となる（ステップＳ６０）。
【０３０９】
ノード１８Ａへの入力リンクＬの決定について説明する。ノード１８Ａは光再生中継器を適用可能なＯＡＤＭであるため、雑音量の最小値ＮＯＩＳＥｍｉｎは０となる（ステップＳ４３）。また、ノード１８Ａへの各入力リンクとして、入力リンク（１７Ａ，１８Ａ）と、入力リンク（１７Ｂ，１８Ａ）と、が取得される（ステップＳ４８）。
【０３１０】
入力リンク（１７Ａ，１８Ａ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１７Ａ）＋ＮＯＩＳＥ（１７Ａ，１８Ａ）＋ＮＯＩＳＥｍｉｎ＝０＋１＋０＝１となる（ステップＳ５０）。また、入力リンク（１７Ｂ，１８Ａ）を選択したときの雑音量の合計値は、ＮＯＩＳＥａｃｃ（１７Ｂ）＋ＮＯＩＳＥ（１７Ｂ，１８Ａ）＋ＮＯＩＳＥｍｉｎ＝２＋２＋０＝４となる（ステップＳ５０）。これらの合計値は雑音閾値ＮＯＩＳＥｔｈの７以下であるため、入力リンク（１７Ａ，１８Ａ）および入力リンク（１７Ｂ，１８Ａ）は削除されない（ステップＳ５２）。
【０３１１】
入力リンク（１７Ａ，１８Ａ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１７Ａ）＋ＣＯＳＴ（１７Ａ，１８Ａ）＝１１＋２＝１３となる（ステップＳ５５）。入力リンク（１７Ｂ，１８Ａ）を選択したときのコストの合計値は、ＣＯＳＴａｃｃ（１７Ｂ）＋ＣＯＳＴ（１７Ｂ，１８Ａ）＝１０＋２＝１２となる（ステップＳ５５）。したがって、コストの合計値が最小となる入力リンク（１７Ｂ，１８Ａ）がノード１８Ａへの入力リンクＬとして選択される（ステップＳ５５）。
【０３１２】
ノード１８Ａまでの累積コストＣＯＳＴａｃｃ（１８Ａ）は、ＣＯＳＴａｃｃ（１７Ｂ）＋ＣＯＳＴ（１７Ｂ，１８Ａ）＝１０＋２＝１２となる（ステップＳ５６）。ノード１８ＡはＯＡＤＭに対応するノードであるため、ノード１８Ａまでの累積雑音ＮＯＩＳＥａｃｃ（１８Ａ）は０となる（ステップＳ５８）。これにより、各ノードへの入力リンクＬがそれぞれ選択される。
【０３１３】
図９に示す第２ノード決定部１５７は、第２リンク選択部１５６から出力された各入力リンクの始点ノードに基づいて、第２ノード候補生成部１５２が生成したノードのいずれかを選択することによって設計単位区間内の各局舎に対する各種の光伝送装置の配置の１つの候補を決定する。第２ノード決定部１５７によるノードの選択処理は、図１７に示したフローチャートと同様である。
【０３１４】
図２６は、図９に示す第２ノード決定部１５７による経由ノードの決定処理の結果を示す図である。図２６において図２０〜図２２，図２５に示した部分と同様の部分については同一の符号を付して説明を省略する。また、図２６において、太矢印は、図１７に示した各ステップによって遷移したノードの経路を示している。また、グラフの下段に、各ステップによって決定された光伝送装置の種類を図示している。黒丸印はバイパスを示している。
【０３１５】
まず、単位設計区間２０４の終端局舎１８に対応するノード１８Ａの番号が設定され（ステップＳ２１）、ノード１８Ａが経由ノードの一つとして保持される（ステップＳ２２）。また、ノード１８Ａへの入力リンクＬとして入力リンク（１７Ｂ，１８Ａ）が取得される（ステップＳ２３）。また、入力リンク（１７Ｂ，１８Ａ）の始点ノードＮｐｒｅとしてノード１７Ｂが取得され（ステップＳ２４）、ノード１７Ｂが経由ノードの一つとして保持される（ステップＳ２５）。
【０３１６】
つぎに、ノード１７Ｂの番号が設定され（ステップＳ２７）、ノード１７Ｂへの入力リンクＬとして入力リンク（１６Ａ，１７Ｂ）が取得される（ステップＳ２３）。また、入力リンク（１６Ａ，１７Ｂ）の始点ノードＮｐｒｅとしてノード１６Ａが取得され（ステップＳ２４）、ノード１６Ａが経由ノードの一つとして保持される（ステップＳ２５）。
【０３１７】
つぎに、ノード１６Ａの番号が設定され（ステップＳ２７）、ノード１６Ａへの入力リンクＬとして入力リンク（１５Ｂ，１６Ａ）が取得される（ステップＳ２３）。また、入力リンク（１５Ｂ，１６Ａ）の始点ノードＮｐｒｅとしてノード１５Ｂが取得され（ステップＳ２４）、ノード１５Ｂが経由ノードの一つとして保持される（ステップＳ２５）。
【０３１８】
つぎに、ノード１５Ｂの番号が設定され（ステップＳ２７）、ノード１５Ｂへの入力リンクＬとして入力リンク（１４Ｂ，１５Ｂ）が取得される（ステップＳ２３）。また、入力リンク（１４Ｂ，１５Ｂ）の始点ノードＮｐｒｅとしてノード１４Ｂが取得され（ステップＳ２４）、ノード１４Ｂが経由ノードの一つとして保持される（ステップＳ２５）。
【０３１９】
つぎに、ノード１４Ｂの番号が設定され（ステップＳ２７）、ノード１４Ｂへの入力リンクＬとして入力リンク（１２Ａ，１４Ｂ）が取得される（ステップＳ２３）。また、入力リンク（１２Ａ，１４Ｂ）の始点ノードＮｐｒｅとしてノード１２Ａが取得され（ステップＳ２４）、ノード１２Ａが経由ノードの一つとして保持される（ステップＳ２５）。
【０３２０】
つぎに、ノード１２Ａの番号が設定され（ステップＳ２７）、ノード１２Ａへの入力リンクＬとして入力リンク（１Ａ，１２Ａ）が取得される（ステップＳ２３）。また、入力リンク（１１Ａ，１２Ａ）の始点ノードＮｐｒｅとしてノード１１Ａが取得され（ステップＳ２４）、ノード１１Ａが経由ノードの一つとして保持される（ステップＳ２５）。
【０３２１】
ノード１１Ａのノード番号は、単位設計区間２０４における始端局舎である局舎１１に配置する光伝送装置のノードの番号であるため、ここで経由ノード決定動作が終了する。このように、ノード１８Ａからノード１１Ａまで入力リンクＬをたどりながら遡ることで、ノード１８Ａ→ノード１７Ｂ→ノード１６Ａ→ノード１５Ｂ→ノード１４Ｂ→ノード１２Ａ→ノード１１Ａの順に経由ノードが保持される。
【０３２２】
第２ノード決定部１５７は、図１７に示す処理によって決定した各経由ノードの種類に従って各局舎１１〜１８に配置する各光伝送装置を決定する。第２ノード決定部１５７は、ノード１１Ａに基づいて局舎１１にＯＡＤＭを配置する。また第２ノード決定部１５７は、ノード１２Ａに基づいて局舎１２にＯＡＤＭを配置する。
【０３２３】
また、第２ノード決定部１５７は、局舎１２に対応するノードが存在しないため、局舎１２にバイパスを配置する。第２ノード決定部１５７は、ノード１４Ｂに基づいて局舎１４にＩＬＡを配置する。第２ノード決定部１５７は、ノード１５Ｂに基づいて局舎１５にＩＬＡを配置する。第２ノード決定部１５７は、ノード１６Ａに基づいて局舎１６にＯＡＤＭを配置する。第２ノード決定部１５７は、ノード１７Ｂに基づいて局舎１７にＩＬＡを配置する。第２ノード決定部１５７は、決定した光伝送装置構成を、単位設計区間２０４の光伝送装置構成の候補として記憶部１２６に記憶する。
【０３２４】
図１９に示すステップＳ３２では、追加候補探索部１２８は、新たな光伝送装置構成の候補ｔ’を探索する。追加候補探索部１２８が光伝送装置構成の候補ｔ’の探索する処理は、図２０〜２６を参照して説明した初期候補生成部１２５が光伝送装置構成を決定する処理と同様である。
ただし、追加候補探索部１２８の第３リンク選択部１６６は、ステップＳ５５において、始点ノードＮｉまで累積された被約費用の変化量ΔＲＣと、入力リンクの被約費用の変化量ΔＲＣとの合計値が最小となる入力リンクを、ノードＮｘへの入力リンクＬとして選択する。
【０３２５】
また第３リンク選択部１６６は、ステップＳ５６において、ノードＮｘまでの累積された被約費用の変化量ΔＲＣａｃｃ（Ｎｘ）を、ΔＲＣａｃｃ（Ｎｘ）＝ΔＲＣａｃｃ（Ｎｐｒｅ）＋ΔＲＣ（Ｌ）によって算出する。ΔＲＣａｃｃ（Ｎｐｒｅ）は、ステップＳ５５によって選択された入力リンクＬの始点ノードＮｐｒｅまでの累積された被約費用の変化量ΔＲＣである。また、ΔＲＣ（Ｌ）は、入力リンクＬを選択したときの被約費用の変化量ΔＲＣである。
【０３２６】
図１１のステップＳ５において、図７に示す光再生中継器配置決定部１１５は、装置構成決定部１２４によって決定された光伝送装置構成内への光再生中継器の配置を決定する。設計データ出力部１１６は、装置構成決定部１２４によって決定された光伝送装置構成に関する情報と光再生中継器配置決定部１１５により決定された光再生中継器の配置に関する情報とを含む設計データを出力する。
【０３２７】
以上の実施例を含む実施形態に関し、更に以下の付記を開示する。
【０３２８】
（付記１）
光ネットワークのトポロジー情報、前記光ネットワーク上の各前記局舎に配置可能な光伝送装置の種類に関する装置情報、前記トポロジー情報上で互いに隣接する局舎間における伝送路条件を示すスパン情報、及び前記光ファイバネットワーク上を伝送する各波長パスに関する波長パス情報を取得する情報取得部と、
前記トポロジー情報により表されるネットワークを線形区間に分割する区間分割部と、
各前記線形区間内に配置される光伝送装置の種類の組み合わせ候補を決定する組み合わせ候補決定部と、
前記波長パス情報において指定される、各前記波長パス上で許される雑音量上限値に対応する所定条件に応じて該雑音量上限値を決定する雑音量上限値決定部と、
前記光ネットワークに配置される光伝送装置のコスト及び各前記波長パス毎に必要な数の光再生中継器に要するコストの合計を最小にする目的関数、前記線形区間毎に前記組み合わせ候補から光伝送装置の種類の組み合わせを１つずつ選択する制約条件、並びに各前記波長パスに必要な光再生中継器数の条件を前記スパン情報において指定される前記伝送路条件に応じて決定される該波長パス上で生じる前記累積雑音量と該波長パスの前記雑音量上限値とにより定める制約条件を有する整数計画問題を解くことにより、各前記線形区間内に配置される光伝送装置を決定する装置配置部と、
を備えるネットワーク設計装置。
【０３２９】
（付記２）
前記整数計画問題は、各前記波長パスに必要な光再生中継器数の条件を、前記スパン情報において指定される前記伝送路条件に応じて決定される該波長パス上で生じる伝送ペナルティの累積値と、該波長パスの信号種類に応じて定まる伝送ペナルティの上限値と、により定める制約条件をさらに有する付記１に記載のネットワーク設計装置。
【０３３０】
（付記３）
前記雑音量上限値決定部は、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力に応じて前記雑音量上限値を定める付記１又は２に記載のネットワーク設計装置。
【０３３１】
（付記４）
前記雑音量上限値決定部は、前記波長パスの信号種類に応じて定まる伝送ペナルティの上限値と、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力と、に応じて前記雑音量上限値を定める付記１又は２に記載のネットワーク設計装置。
【０３３２】
（付記５）
前記波長パス上で生じうる伝送ペナルティの累積値の最大値を決定する累積ペナルティ最大値決定部を備え、
前記雑音量上限値決定部は、前記波長パスの信号種類に応じて定まる伝送ペナルティの上限値及び前記最大値のうち小さい方と、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力と、に応じて前記雑音量上限値を定める付記１又は２に記載のネットワーク設計装置。
【０３３３】
（付記６）
前記波長パス上で生じうる伝送ペナルティの累積値の最大値及び最小値を決定する累積ペナルティ決定部と、
前記最小値の伝送ペナルティが累積する波長パスにおいて信号の再生に要する光再生中継器の最小数を決定する最小光再生中継器数決定部と、を備え、
前記雑音量上限値決定部は、前記最小数の光再生中継器により分割された該波長パス上に生じ得る伝送ペナルティの最大値及び前記波長パスの信号種類に応じて定まる伝送ペナルティの上限値のうち小さい方と、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力とに応じて前記雑音量上限値を定める付記１又は２に記載のネットワーク設計装置。
【０３３４】
（付記７）
コンピュータを、
光ネットワークのトポロジー情報、前記光ネットワーク上の各前記局舎に配置可能な光伝送装置の種類に関する装置情報、前記トポロジー情報上で互いに隣接する局舎間における伝送路条件を示すスパン情報、及び前記光ファイバネットワーク上を伝送する各波長パスに関する波長パス情報を取得する情報取得手段、
前記トポロジー情報により表されるネットワークを線形区間に分割する区間分割手段、
各前記線形区間内に配置される光伝送装置の種類の組み合わせ候補を決定する組み合わせ候補決定手段、
前記波長パス情報において指定される、各前記波長パス上で許される雑音量上限値に対応する所定条件に応じて該雑音量上限値を決定する雑音量上限値決定手段、
前記光ネットワークに配置される光伝送装置のコスト及び各前記波長パス毎に必要な数の光再生中継器に要するコストの合計を最小にする目的関数、前記線形区間毎に前記組み合わせ候補から光伝送装置の種類の組み合わせを１つずつ選択する制約条件、並びに各前記波長パスに必要な光再生中継器数の条件を前記スパン情報において指定される前記伝送路条件に応じて決定される該波長パス上で生じる前記累積雑音量と該波長パスの前記雑音量上限値とにより定める制約条件を有する整数計画問題を解くことにより、各前記線形区間内に配置される光伝送装置を決定する装置配置手段、として機能させるネットワーク設計プログラム。
【０３３５】
（付記８）
前記整数計画問題は、各前記波長パスに必要な光再生中継器数の条件を、前記スパン情報において指定される前記伝送路条件に応じて決定される該波長パス上で生じる伝送ペナルティの累積値と、該波長パスの信号種類に応じて定まる伝送ペナルティの上限値と、により定める制約条件をさらに有する付記７に記載のネットワーク設計プログラム。
【０３３６】
（付記９）
前記雑音量上限値決定手段は、前記波長パス情報において指定される前記所定条件に応じて定まる前記波長パスのＯＳＮＲ耐力に応じて前記雑音量上限値を定める付記７又は８に記載のネットワーク設計プログラム。
【０３３７】
（付記１０）
前記雑音量上限値決定手段は、前記波長パスの信号種類に応じて定まる伝送ペナルティの上限値と、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力と、に応じて前記雑音量上限値を定める付記７又は８に記載のネットワーク設計プログラム。
【０３３８】
（付記１１）
前記ネットワーク設計プログラムは、前記コンピュータを、前記波長パス上で生じうる伝送ペナルティの累積値の最大値を決定する累積ペナルティ最大値決定手段として機能させ、
前記雑音量上限値決定手段は、前記波長パスの信号種類に応じて定まる伝送ペナルティの上限値及び前記最大値のうち小さい方と、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力と、に応じて前記雑音量上限値を定める付記７又は８に記載のネットワーク設計プログラム。
【０３３９】
（付記１２）
前記ネットワーク設計プログラムは、前記コンピュータを、
前記波長パス上で生じうる伝送ペナルティの累積値の最大値及び最小値を決定する累積ペナルティ決定手段、及び
前記最小値の伝送ペナルティが累積する波長パスにおいて信号の再生に要する光再生中継器の最小数を決定する最小光再生中継器数決定手段、として機能させ、
前記雑音量上限値決定手段は、前記最小数の光再生中継器により分割された該波長パス上に生じ得る伝送ペナルティの最大値、及び前記波長パスの信号種類に応じて定まる伝送ペナルティの上限値のうち小さい方と、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力と、に応じて前記雑音量上限値を定める付記７又は８に記載のネットワーク設計プログラム。
【０３４０】
（付記１３）
光ネットワークのトポロジー情報、前記光ネットワーク上の各前記局舎に配置可能な光伝送装置の種類に関する装置情報、前記トポロジー情報上で互いに隣接する局舎間における伝送路条件を示すスパン情報、及び前記光ファイバネットワーク上を伝送する各波長パスに関する波長パス情報が、コンピュータに入力され、
前記コンピュータは、
前記トポロジー情報により表されるネットワークを線形区間に分割し、
各前記線形区間内に配置される光伝送装置の種類の組み合わせ候補を決定し、
前記波長パス情報において指定される、各前記波長パス上で許される雑音量上限値に対応する所定条件に応じて該雑音量上限値を決定し、
前記光ネットワークに配置される光伝送装置のコスト及び各前記波長パス毎に必要な数の光再生中継器に要するコストの合計を最小にする目的関数、前記線形区間毎に前記組み合わせ候補から光伝送装置の種類の組み合わせを１つずつ選択する制約条件、並びに各前記波長パスに必要な光再生中継器数の条件を前記スパン情報において指定される前記伝送路条件に応じて決定される該波長パス上で生じる前記累積雑音量と該波長パスの前記雑音量上限値とにより定める制約条件を有する整数計画問題を解くことにより、各前記線形区間内に配置される光伝送装置を決定する、ネットワーク設計方法。
【０３４１】
（付記１４）
前記整数計画問題は、前記整数計画問題は、各前記波長パスに必要な光再生中継器数の条件を、前記スパン情報において指定される前記伝送路条件に応じて決定される該波長パス上で生じる伝送ペナルティの累積値と、該波長パスの信号種類に応じて定まる伝送ペナルティの上限値と、により定める制約条件をさらに有する付記１３に記載のネットワーク設計方法。
【０３４２】
（付記１５）
前記コンピュータは、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力に応じて前記雑音量上限値を定める付記１３又は１４に記載のネットワーク設計方法。
【０３４３】
（付記１６）
前記コンピュータは、前記波長パスの信号種類に応じて定まる伝送ペナルティの上限値と、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力と、に応じて前記雑音量上限値を定める付記１３又は１４に記載のネットワーク設計方法。
【０３４４】
（付記１７）
前記コンピュータは、
前記波長パス上で生じうる伝送ペナルティの累積値の最大値を決定し、
前記波長パスの信号種類に応じて定まる伝送ペナルティの上限値及び前記最大値のうち小さい方と、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力に応じて前記雑音量上限値を定める付記１３又は１４に記載のネットワーク設計方法。
【０３４５】
（付記１８）
前記コンピュータは、
前記波長パス上で生じうる伝送ペナルティの累積値の最大値及び最小値を決定し、
前記最小値の伝送ペナルティが累積する波長パスにおいて信号の再生に要する光再生中継器の最小数を決定し、
前記最小数の光再生中継器により分割された該波長パス上に生じ得る伝送ペナルティの最大値、及び前記波長パスの信号種類に応じて定まる伝送ペナルティの上限値のうち小さい方と、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力と、に応じて前記雑音量上限値を定める付記１３又は１４に記載のネットワーク設計方法。
【図面の簡単な説明】
【０３４６】
【図１】設計対象となる光ネットワークを示す図である。
【図２】各局舎に配置可能な光伝送装置の種類の一例を示す図である。
【図３】図２に示すＯＡＤＭの一例を示すブロック図である。
【図４】図２に示すＩＬＡの一例を示すブロック図である。
【図５】図２に示すバイパスの一例を示すブロック図である。
【図６】ＣＰＵを用いて開示のネットワーク設計装置を実現した場合のハードウエア構成図である。
【図７】図６に示すＣＰＵがネットワーク設計プログラムを実行することにより実現されるネットワーク設計装置のブロック図である。
【図８】図７に示すパラメータ決定部のブロック図である。
【図９】図７に示す初期候補生成部のブロック図である。
【図１０】図７に示す追加候補探索部のブロック図である。
【図１１】開示のネットワーク設計方法の全体フローチャートである。
【図１２】図８に示すパス内グラフ生成部が生成するグラフ情報の例を示す図（その１）である。
【図１３】図８に示すパス内グラフ生成部が生成するグラフ情報の例を示す図（その２）である。
【図１４】図８に示す第１リンク選択部による入力リンクの選択処理の説明図である。
【図１５】図８に示す第１リンク選択部による選択処理の例を示すフローチャートである。
【図１６】図８に示す第１リンク選択部による入力リンクの選択処理の結果を示す図である。
【図１７】図８に示す第１ノード決定部による経由ノードの決定処理の例を示すフローチャートである。
【図１８】図８に示す第１ノード決定部による経由ノードの決定処理の結果を示す図である。
【図１９】各単位設計区間の光伝送装置構成を決定する決定方法の一例を示すフローチャートである。
【図２０】図９に示す第１単位設計区間内グラフ生成部が生成するグラフ情報の例を示す図（その１）である。
【図２１】図９に示す第１単位設計区間内グラフ生成部が生成するグラフ情報の例を示す図（その２）である。
【図２２】図９に示す第２リンク選択部による入力リンクの選択処理の説明図である。
【図２３】図９に示す第２リンク選択部による選択処理の例を示すフローチャート（その１）である。
【図２４】図９に示す第２リンク選択部による選択処理の例を示すフローチャート（その２）である。
【図２５】図９に示す第２リンク選択部による入力リンクの選択処理の結果を示す図である。
【図２６】図９に示す第２ノード決定部による経由ノードの決定処理の結果を示す図である。
【符号の説明】
【０３４７】
１、４、６、１１、２８ＯＡＤＭ装置が配置される局舎
２、３、５、１２〜１７中継局舎
１００ネットワーク設計装置
１２０情報取得部
１２１区間分割部
１２３パラメータ決定部
１２４装置構成決定部
２００光ネットワーク
２０１波長パスの区間
２０２〜２０４線形区間

【特許請求の範囲】
【請求項１】
光ネットワークのトポロジー情報、前記光ネットワーク上の各前記局舎に配置可能な光伝送装置の種類に関する装置情報、前記トポロジー情報上で互いに隣接する局舎間における伝送路条件を示すスパン情報、及び前記光ファイバネットワーク上を伝送する各波長パスに関する波長パス情報を取得する情報取得部と、
前記トポロジー情報により表されるネットワークを線形区間に分割する区間分割部と、
各前記線形区間内に配置される光伝送装置の種類の組み合わせ候補を決定する組み合わせ候補決定部と、
前記波長パス情報において指定される、各前記波長パス上で許される雑音量上限値に対応する所定条件に応じて該雑音量上限値を決定する雑音量上限値決定部と、
前記光ネットワークに配置される光伝送装置のコスト及び各前記波長パス毎に必要な数の光再生中継器に要するコストの合計を最小にする目的関数、前記線形区間毎に前記組み合わせ候補から光伝送装置の種類の組み合わせを１つずつ選択する制約条件、並びに各前記波長パスに必要な光再生中継器数の条件を前記スパン情報において指定される前記伝送路条件に応じて決定される該波長パス上で生じる前記累積雑音量と該波長パスの前記雑音量上限値とにより定める制約条件を有する整数計画問題を解くことにより、各前記線形区間内に配置される光伝送装置を決定する装置配置部と、
を備えるネットワーク設計装置。
【請求項２】
前記整数計画問題は、各前記波長パスに必要な光再生中継器数の条件を、前記スパン情報において指定される前記伝送路条件に応じて決定される該波長パス上で生じる伝送ペナルティの累積値と、該波長パスの信号種類に応じて定まる伝送ペナルティの上限値と、により定める制約条件をさらに有する請求項１に記載のネットワーク設計装置。
【請求項３】
前記雑音量上限値決定部は、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力に応じて前記雑音量上限値を定める請求項１又は２に記載のネットワーク設計装置。
【請求項４】
前記雑音量上限値決定部は、前記波長パスの信号種類に応じて定まる伝送ペナルティの上限値と、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力と、に応じて前記雑音量上限値を定める請求項１又は２に記載のネットワーク設計装置。
【請求項５】
前記波長パス上で生じうる伝送ペナルティの累積値の最大値を決定する累積ペナルティ最大値決定部を備え、
前記雑音量上限値決定部は、前記波長パスの信号種類に応じて定まる伝送ペナルティの上限値及び前記最大値のうち小さい方と、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力と、に応じて前記雑音量上限値を定める請求項１又は２に記載のネットワーク設計装置。
【請求項６】
前記波長パス上で生じうる伝送ペナルティの累積値の最大値及び最小値を決定する累積ペナルティ決定部と、
前記最小値の伝送ペナルティが累積する波長パスにおいて信号の再生に要する光再生中継器の最小数を決定する最小光再生中継器数決定部と、を備え、
前記雑音量上限値決定部は、前記最小数の光再生中継器により分割された該波長パス上に生じ得る伝送ペナルティの最大値及び前記波長パスの信号種類に応じて定まる伝送ペナルティの上限値のうち小さい方と、前記波長パス情報において指定される前記所定条件に応じて定まる該波長パスのＯＳＮＲ耐力とに応じて前記雑音量上限値を定める請求項１又は２に記載のネットワーク設計装置。
【請求項７】
コンピュータを、
光ネットワークのトポロジー情報、前記光ネットワーク上の各前記局舎に配置可能な光伝送装置の種類に関する装置情報、前記トポロジー情報上で互いに隣接する局舎間における伝送路条件を示すスパン情報、及び前記光ファイバネットワーク上を伝送する各波長パスに関する波長パス情報を取得する情報取得手段、
前記トポロジー情報により表されるネットワークを線形区間に分割する区間分割手段、
各前記線形区間内に配置される光伝送装置の種類の組み合わせ候補を決定する組み合わせ候補決定手段、
前記波長パス情報において指定される、各前記波長パス上で許される雑音量上限値に対応する所定条件に応じて該雑音量上限値を決定する雑音量上限値決定手段、
前記光ネットワークに配置される光伝送装置のコスト及び各前記波長パス毎に必要な数の光再生中継器に要するコストの合計を最小にする目的関数、前記線形区間毎に前記組み合わせ候補から光伝送装置の種類の組み合わせを１つずつ選択する制約条件、並びに各前記波長パスに必要な光再生中継器数の条件を前記スパン情報において指定される前記伝送路条件に応じて決定される該波長パス上で生じる前記累積雑音量と該波長パスの前記雑音量上限値とにより定める制約条件を有する整数計画問題を解くことにより、各前記線形区間内に配置される光伝送装置を決定する装置配置手段、として機能させるネットワーク設計プログラム。
【請求項８】
光ネットワークのトポロジー情報、前記光ネットワーク上の各前記局舎に配置可能な光伝送装置の種類に関する装置情報、前記トポロジー情報上で互いに隣接する局舎間における伝送路条件を示すスパン情報、及び前記光ファイバネットワーク上を伝送する各波長パスに関する波長パス情報が、コンピュータに入力され、
前記コンピュータは、
前記トポロジー情報により表されるネットワークを線形区間に分割し、
各前記線形区間内に配置される光伝送装置の種類の組み合わせ候補を決定し、
前記波長パス情報において指定される、各前記波長パス上で許される雑音量上限値に対応する所定条件に応じて該雑音量上限値を決定し、
前記光ネットワークに配置される光伝送装置のコスト及び各前記波長パス毎に必要な数の光再生中継器に要するコストの合計を最小にする目的関数、前記線形区間毎に前記組み合わせ候補から光伝送装置の種類の組み合わせを１つずつ選択する制約条件、並びに各前記波長パスに必要な光再生中継器数の条件を前記スパン情報において指定される前記伝送路条件に応じて決定される該波長パス上で生じる前記累積雑音量と該波長パスの前記雑音量上限値とにより定める制約条件を有する整数計画問題を解くことにより、各前記線形区間内に配置される光伝送装置を決定する、ネットワーク設計方法。

【図１】