(57)【特許請求の範囲】
【請求項１】
波長多重技術によって複数の波長を用いてＴＤＭ（Time Divisional Multiplexing）伝送路を収容するネットワークのネットワーク設計装置において、
少なくともデマンドの情報と、各リンクの利用可能な波長数の上限と、ＴＤＭ伝送路情報とが与えられ、リンクごとに利用可能な波長数を超えないようにデマンドを全て収容するために必要なＴＤＭ伝送路の本数をリンク毎に求める収容設計問題処理部と、
求めたＴＤＭ伝送路の本数と収容するデマンドから各ＴＤＭ伝送路に収容するデマンドを決定する詰め込み問題処理部と、
該詰め込み問題処理部の処理により、ＴＤＭ伝送路の本数がデマンドを収容する際に利用可能な波長数を超過したリンクの内、超過波長数が最も多い第１のリンクと、該第１のリンクから最も遠い第２のリンクについて利用可能な波長数を削減した制約条件を設定する処理を繰り返し、変更された制約条件の下に該収容設計問題処理部と詰め込み問題処理部により再度設計を行わせる繰り返し処理部と、
を備えることを特徴とするネットワーク設計装置。
【請求項２】
前記収容設計問題処理部には、更に、ネットワークトポロジ情報と、ＴＤＭ伝送路の区間と速度ごとのＴＤＭ伝送路のコストとが与えられ、コストの合計が最小となるようにＴＤＭ伝送路の本数を求めることを特徴する請求項１に記載のネットワーク設計装置。
【請求項３】
前記繰り返し処理部は、
波長数を超過したリンクのリストを作成する手段と、
前記リストに含まれるリンクを最も多く通るＴＤＭ伝送路を選択する手段と、
選択したＴＤＭ伝送路上で最も超過波長数の多いリンクを前記第１のリンクとして選択する手段と、
選択したＴＤＭ伝送路上にある波長数を超過しているリンクであって、前記第１のリンクから最も距離が遠いリンクを前記第２のリンクとして選択する手段と、
前記第１のリンクと前記第２のリンクの波長数の制約条件を変更する手段と、
そのＴＤＭ伝送路に含まれるリンクを前記リストから削除する手段と、
前記リストが空になるまで制約条件の変更を繰り返す手段と、
を備えることを特徴とする請求項１に記載のネットワーク設計装置。
【請求項４】
選択したＴＤＭ伝送路上にある波長数を超過しているリンクであって、前記第１のリンクから最も距離が遠いリンクを第２のリンクとして選択する手段のかわりに、選択したＴＤＭ伝送路上にある波長数を超過しているリンクであって、前記第１のリンクから最も多くのホップ数だけ離れているリンクを第２のリンクとして選択する手段を備えることを特徴とする請求項３に記載のネットワーク設計装置。
【請求項５】
波長数を超過したリンクのリストに含まれるリンクを最も多く通るＴＤＭ伝送路を選択する手段のかわりに、前記リストに含まれるリンクを最も多く通り、かつ、同一始終点のＴＤＭ伝送路が２本以上ある場合に、そのＴＤＭ伝送路を選択する手段を備えることを特徴とする請求項３に記載のネットワーク設計装置。
【請求項６】
波長数を超過したリンクのリストに含まれるリンクを最も多く通るＴＤＭ伝送路を選択する手段のかわりに、前記リストに含まれるリンクを最も多く通り、かつ、同一始終点のＴＤＭ伝送路が最も多いＴＤＭ伝送路を選択する手段を備えることを特徴とする請求項３に記載のネットワーク設計装置。
【請求項７】
波長数を超過したリンクのリストに含まれるリンクを最も多く通るＴＤＭ伝送路を選択する手段のかわりに、前記リストに含まれるリンクを最も多く通り、かつ、前記リストに含まれるリンクの中で通過するリンクが全て同じＴＤＭ伝送路の合計本数の最も多いＴＤＭ伝送路を選択する手段を備えることを特徴とする請求項３に記載のネットワーク設計装置。
【請求項８】
波長数を超過したリンクのリストに含まれるリンクを最も多く通るＴＤＭ伝送路を選択する手段のかわりに、前記リストに含まれるリンクを最も多く通り、かつ、前記リストに含まれるリンクの中で通過するリンクが全て同じで、かつ、該リンクのどちらか一端が同一のＴＤＭ伝送路の合計本数の最も多いＴＤＭ伝送路を選択する手段を備えることを特徴とする請求項３に記載のネットワーク設計装置。
【請求項９】
波長数を超過したリンクのリストに含まれるリンクを最も多く通るＴＤＭ伝送路を選択する手段のかわりに、前記リストに含まれるリンクを最も多く通り、かつ、前記リストから削除されたリンクの中で通過するリンクの数が最も少ないＴＤＭ伝送路を選択する手段を備えることを特徴とする請求項３に記載のネットワーク設計装置。
【請求項１０】
第１のリンクを選択する手段と第２のリンクを選択する手段のかわりに、第１のリンク、第２のリンクとも選択されたＴＤＭ伝送路上にあり、かつ、第１のリンクと第２のリンクを共に通るＴＤＭ伝送路の始終点対の数が最も少なくなるように第１のリンクと第２のリンクを選択する手段を備えることを特徴とする請求項３に記載のネットワーク設計装置。
【請求項１１】
第１のリンクを選択する手段と第２のリンクを選択する手段のかわりに、第１のリンク、第２のリンクとも選択されたＴＤＭ伝送路上にあり、かつ、第１のリンクと第２のリンクを共に通るＴＤＭ伝送路の本数が最も少なくなるように第１のリンクと第２のリンクを選択する手段を備えることを特徴とする請求項３に記載のネットワーク設計装置。
【請求項１２】
選択したＴＤＭ伝送路上にある波長数を超過しているリンクであって、前記第１のリンクから最も距離が遠いリンクを第２のリンクとして選択する手段のかわりに、選択したＴＤＭ伝送路上で第１のリンクを除いた残りの中で最も超過波長数の多いリンクを第２のリンクとして選択する手段を備えることを特徴とする請求項３に記載のネットワーク設計装置。
【請求項１３】
速度ごとのＴＤＭ伝送路のコストをＴＤＭ伝送路の区間ごとに入力し、ＴＤＭ伝送路を選択する際に、低速の伝送路のコストと高速の伝送路のコストの比率が所定の値を超える場合にはそのＴＤＭ伝送路を選択肢から除外する手段を備えることを特徴とする請求項２に記載のネットワーク設計装置。
【請求項１４】
波長多重技術によって複数の波長を用いてＴＤＭ（Time Divisional Multiplexing）伝送路を収容するネットワークのネットワーク設計方法において、
少なくともデマンドの情報と、各リンクの利用可能な波長数の上限と、ＴＤＭ伝送路情報とが与えられ、リンクごとに利用可能な波長数を超えないようにデマンドを全て収容するために必要なＴＤＭ伝送路の本数をリンク毎に求め、
求めたＴＤＭ伝送路の本数と収容するデマンドから各ＴＤＭ伝送路に収容するデマンドを決定し、
該デマンド決定ステップにより、ＴＤＭ伝送路の本数がデマンドを収容する際に利用可能な波長数を超過したリンクの内、超過波長数が最も多い第１のリンクと、該第１のリンクから最も遠い第２のリンクについて利用可能な波長数を削減した制約条件を設定する処理を繰り返し、変更された制約条件の下に該ＴＤＭ伝送路本数を求めるステップと該デマンド決定ステップを行わせる、
ことを特徴とするネットワーク設計方法。
【請求項１５】
波長多重技術によって複数の波長を用いてＴＤＭ（Time Divisional Multiplexing）伝送路を収容するネットワークのネットワーク設計方法をコンピュータに実行させるプログラムであって、
コンピュータに、
少なくともデマンドの情報と、各リンクの利用可能な波長数の上限と、ＴＤＭ伝送路情報とが与えられ、リンクごとに利用可能な波長数を超えないようにデマンドを全て収容するために必要なＴＤＭ伝送路の本数をリンク毎に求めさせ、
求めたＴＤＭ伝送路の本数と収容するデマンドから各ＴＤＭ伝送路に収容するデマンドを決定させ、
該デマンド決定ステップにより、ＴＤＭ伝送路の本数がデマンドを収容する際に利用可能な波長数を超過したリンクの内、超過波長数が最も多い第１のリンクと、該第１のリンクから最も遠い第２のリンクについて利用可能な波長数を削減した制約条件を設定する処理を繰り返させ、変更された制約条件の下に該ＴＤＭ伝送路本数を求めるステップと該デマンド決定ステップを行わせる、
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
以下の実施形態は、ネットワーク設計装置に関する。
【背景技術】
【０００２】
ＴＤＭ(Time Division Multiplexing: 時分割多重)技術を用いて加入者回線を収容する場合に、その回線をどのＴＤＭ伝送路を用いて収容するかを決定する技術がある。その技術を、ＴＤＭ伝送路をＷＤＭ(Wavelength Division Multiplexing: 波長多重)技術を用いて伝送するようなネットワークに対して用いることが必要とされている。
【０００３】
ＴＤＭ伝送路に収容される加入者回線の信号は、トラフィックデマンドまたはデマンドと呼ばれるため、以降の説明では、ＴＤＭ伝送路に収容する加入者回線をデマンドと呼ぶ。
【０００４】
電話局間に敷設したファイバを用いて加入者の回線の信号(デマンド)を伝送する場合、同じファイバを使って伝送することのできるデマンド同士をＴＤＭ伝送路に多重して伝送する。このとき、どのデマンドを、どのＴＤＭ伝送路に多重するかを決定する必要がある。このように、収容するデマンドとネットワークトポロジが与えられたときに、どこからどこまでの区間に、どんな速度のＴＤＭ伝送路を設置するかを決定する問題を解く必要があるが、以降、この問題を収容設計問題という。
【０００５】
近年の通信は、全てデジタル化されており、ＴＤＭ伝送路にはタイムスロットと呼ばれる信号をのせる場所が複数用意されている。デマンドをＴＤＭ伝送路にのせる場合、のせるデマンドの帯域によって使うタイムスロットの数が決まる。従って、どのデマンドをどのＴＤＭ伝送路に収容するかを決定する際には、収容しようとするデマンドが必要とするタイムスロットの数の合計が、ＴＤＭ伝送路に用意されているタイムスロットの数を超えないようにする必要がある。また、１本のＴＤＭ伝送路はＷＤＭの１つの波長を占有し、１本のファイバに収容できる波長の数はシステムによって決まっている。したがって、ファイバごとに収容できる波長数を越えない数のＴＤＭ伝送路を設定するように、設計を行う必要がある。
【０００６】
ＴＤＭ伝送路として、従来、ＳＤＨ (Synchronous Digital Hierarchy)伝送路が主に用いられてきた。ＳＤＨは、ＳＴＭ１などタイムスロットの最小単位が決まっており、デマンドのタイムスロットの数は、１,４,１６など互いに整数倍の関係にある。また、それらは、ＴＤＭ伝送路の総タイムスロット数を割り切ることのできる値に設定されていた。一部では、割り切れない数のタイムスロットを使うデマンドも扱われていた。その多くの場合には、そのデマンドを収容できて、かつ、タイムスロット数が整数倍になる回線に一度収容し、その収容した回線をデマンドとしてＴＤＭ伝送路に多重するような方法をとっていた。
【０００７】
近年、ＯＴＮ (Optical Transport Network)技術が標準化された。ＯＴＮの中では、収容するデマンドが最小速度の任意の整数倍の速度をとることができる、すなわち、ＴＤＭ伝送路の総タイムスロット数や他のデマンドのタイムスロット数と互いに整数倍の関係にならないタイムスロット数を持つデマンドを自由に多重することができるようになった。
【０００８】
これらの条件における収容設計問題を数理計画法によって解く方法がある。数理計画法を用いる場合、個々のＴＤＭ伝送路をあらかじめ用意し、それらを使うか使わないかの０／１計画問題として解く方法が知られている。また、他の方法として、始点と終点およびその間の経路で定義されるＴＤＭ伝送路の区間をあらかじめ用意し、その区間にＴＤＭ伝送路が速度ごとに何本必要かを決める。そして、その後で、得られたＴＤＭ伝送路の本数と収容するデマンドの一覧から、それぞれのＴＤＭ伝送路にどのデマンドを入れるかを決定する方法がある。すなわち、問題を２段階に分けて解く方法である。前者は用意したＴＤＭ伝送路ごとに変数を割り当て、後者はＴＤＭ伝送路の区間ごとに変数を割り当てる。このため、前者は現実的に解くことのできるネットワークの規模やデマンドの数などが計算を行う機器の能力によって著しく制限されてしまう。したがって、近年のような大規模なネットワークでは、問題を解くための演算時間が非常に長くなってしまい、現実的ではない。一方、後者は、ＴＤＭ伝送路の本数を決めた上で、元の問題の一部分を別の問題として解き、個々のＴＤＭ伝送路に収容するデマンドを決定する問題を解いている。このとき、ＳＤＨのときのようにデマンドが必要とするタイムスロットの数とＴＤＭ伝送路に用意されているタイムスロットの数が整数倍の関係になっていれば、タイムスロット数から計算した本数のＴＤＭ伝送路に必ず全てのデマンドを収容できる解が存在する。しかし、ＯＴＮ技術が用いられるようになって、整数倍の関係にないデマンドが発生することで、タイムスロット数から計算したＴＤＭ伝送路の本数では収容できないケースが発生し始めた。
【０００９】
以下の説明では、信号を収容するのに必要なタイムスロットの数をデマンドの帯域、ＴＤＭ伝送路の総タイムスロット数をＴＤＭ伝送路の容量と記す。例えば、収容するデマンドが５本あり、それぞれ帯域を６とし、ＴＤＭ伝送路の容量が８の場合を考える。帯域が６のデマンドが５本なので、必要なタイムスロットの数の合計、すなわち、合計帯域は３０で、容量が８のＴＤＭ伝送路が４本あれば、合計タイムスロット数、すなわち、合計容量は３２となり、収容できる計算になる。しかし、現実には１つのデマンドを２つのＴＤＭ伝送路に分割して収容することはできないため、１つのＴＤＭ伝送路に帯域６のデマンドは１つしかのせることができず、結果としてＴＤＭ伝送路は５本必要になってしまう。このように、デマンドの帯域が整数倍の関係になるとは限らなくなったことで、問題を解いて、必要なＴＤＭ伝送路の数を決定した後、それぞれのＴＤＭ伝送路に収容するデマンドを決定する際に、ＴＤＭ伝送路の本数が増えてしまう場合が生じるようになってしまった。
【００１０】
前述の２段階で解く方法では、一般に、１段目のＴＤＭ伝送路を設定する区間ごとに、ＴＤＭ伝送路が何本必要かを決定する際に、ＴＤＭ伝送路の本数がＷＤＭで利用できる波長の数を超えないようにしている。このため、２段目の個々のＴＤＭ伝送路に収容するデマンドを決定する際に、ＴＤＭ伝送路の本数が増えてしまうと、ＷＤＭで利用できる波長の数を超えてしまい、無効な設計結果となってしまう場合が生じてしまうようになった。例えば、前述の例の場合、ＷＤＭに収容できるＴＤＭ伝送路の本数が４本であるとすると、必要なＴＤＭ伝送路の本数を求めたときには４本という結果になり、ＷＤＭに収容できる解であった。しかし、２段目の個々のＴＤＭ伝送路に収容する信号を決定する際に、ＴＤＭ伝送路の本数が５本になってしまい、結果としてＷＤＭのネットワークに収容できなくなってしまう。
【００１１】
この問題を回避する方法として、より容量の大きいＴＤＭ伝送路を用いる方法がある。従来は、２段目の個々のＴＤＭ伝送路に収容するデマンドを決定する際に、ＴＤＭ伝送路の本数が増えてしまう場合には、より容量の大きい伝送路を用いるようにしていた。前述の例の場合、容量が８のＴＤＭ伝送路を３本用意し、さらに容量が２倍の１６のＴＤＭ伝送路を１本用意すれば、容量が１６のＴＤＭ伝送路には帯域６のデマンドが２本入るため、合計４本のＴＤＭ伝送路で収容することができる。この方法は、より容量の大きいＴＤＭ伝送路がある場合には、ほとんどの場合で解が存在する。したがって、２段階で問題を解く際の２段階目だけで処理できる非常に簡易な方法である。従来のようにＴＤＭ伝送路の本数が利用可能な波長数を超過してしまうケースが非常に少ない場合は有効である。しかし、ＴＤＭ伝送路の本数がＷＤＭで利用可能な波長数を超過する箇所が多い場合には、より容量の大きいＴＤＭ伝送路を必要以上に多く使ってしまうことがある。一般には、容量の大きいＴＤＭ伝送路は高価な場合が多く、結果としてコストの高いネットワークを設計してしまうという問題点があった。
【００１２】
図１〜図６は、従来技術を説明する図である。
図１のようにA, B, C, D, Eの５つのノードで構成されるネットワークがあり、ファイバあたり、波長を８波まで使えるＷＤＭの伝送路がA-B, B-C, C-D, D-Eのそれぞれに使用されているとする。また、ＷＤＭ伝送路の１波は、１つのＴＤＭ伝送路であり、容量が８であるとする。この場合、図１のA-B, B-C, C-D, D-E間を通るＴＤＭ伝送路の本数は８本、合計容量６４までということになる。以降の説明では、ノードとノードの間を接続する部分をリンクと呼ぶ。図１のA-B, B-C, C-D, D-Eがそれぞれリンクである。
【００１３】
次に、収容するデマンドを図２に示す。それぞれ始点と終点、帯域、本数を記載している。また、ＴＤＭ伝送路は図３に示すようにA-B間、B-C間、C-D間、D-E間、A-E間に設定されると仮定する。図３中で、矢印で示した区間が、ＴＤＭ伝送路の設定される区間である。ここでは簡単のため、A-B間のデマンドはA-B間のＴＤＭ伝送路に、B-C間のデマンドはB-C間のＴＤＭ伝送路に、C-D間のデマンドはC-D間のＴＤＭ伝送路に、D-E間のデマンドはD-E間のＴＤＭ伝送路に、A-E間のデマンドはA-E間のＴＤＭ伝送路に収容されるとする。A-B間とD-E間のデマンドの合計帯域は、図２より、帯域６×５本で、３０であり、計算上必要なＴＤＭ伝送路の本数は４本となる。また、B-C間のデマンドの合計帯域は、帯域４×４本で、１６であり、計算上必要なＴＤＭ伝送路の本数は２、C-D間のデマンドの合計帯域は、帯域２×８本で、１６であり、計算上必要なＴＤＭ伝送路の本数は２である。A-E間のデマンドの合計帯域は、帯域４×８本で、３２であり、計算上必要なＴＤＭ伝送路の本数は４である。図４にA-B, B-C, C-D, D-E間の、デマンドの帯域合計から求めたＴＤＭ伝送路の合計本数を示す。例えば、A-B間の場合は、A-B間のＴＤＭ伝送路が４本と、A-E間のＴＤＭ伝送路が４本の合計８本が通っているという意味である。この時点では、いずれのリンクもＷＤＭで使える波長数を超過していない。
【００１４】
次に、個々のＴＤＭ伝送路に収容するデマンドを決定する。まず、B-C間は帯域４のデマンドを２本ずつ、２本の容量８のＴＤＭ伝送路に収容することができるため、個々のＴＤＭ伝送路に収容する際にも計算どおり２本のＴＤＭ伝送路で収容することができる。また、C-D間も帯域２のデマンドを４本ずつ２本の容量８のＴＤＭ伝送路に収容することができるため、計算通り２本のＴＤＭ伝送路で収容できる。同様に、A-E間についても帯域が４のデマンドを２本ずつ４本の容量８のＴＤＭ伝送路で収容することができる。しかし、A-B間とD-E間は、合計帯域から計算されるＴＤＭ伝送路の本数は４本だが、実際に個々のＴＤＭ伝送路に収容する際には５本必要になる場合である。すなわち、A-B間とD-E間では、デマンドの帯域が６であるため、容量８のＴＤＭ伝送路には、１本ずつしか収容できない。したがって、ＴＤＭ伝送路は、デマンドの数５だけ必要となる。このため、実際に必要なＴＤＭ伝送路の本数を図５に示すが、本数の欄に太字で示したように、A-B間とD-E間についてＷＤＭで使うことのできる波長数を越えてしまっている。
【００１５】
そこで、従来の技術では、ＴＤＭ伝送路の数がＷＤＭで使える波長数を越えてしまったリンクを通るＴＤＭ伝送路のうち、ＴＤＭ伝送路の数が増えてしまった区間について、より容量の大きいＴＤＭ伝送路を用いて、必要なＴＤＭ伝送路の数を元の数まで減らす。
【００１６】
図６に従来技術のフローを示す。
トポロジや収容するデマンド、ＴＤＭ伝送路を設定する区間などのネットワーク情報を入力する（ステップＳ１０）。次に、収容設計問題を解いて、各区間のＴＤＭ伝送路の本数を求める（ステップＳ１１）。そして、個々のＴＤＭ伝送路に収容するデマンドを決定する(ステップＳ１２)。その後、各リンクについてＴＤＭ伝送路の数がＷＤＭで使える波長数を越えていないかを確認し（ステップＳ１３）、超えているリンクがない場合には、処理を終了する。超えているリンクがある場合は、ＴＤＭ伝送路の数が使える波長数を超過したリンクを通るＴＤＭ伝送路の区間をリストアップする(ステップＳ１４)。そして、それらを順に取り出して（ステップＳ１５）、区間ごとのＴＤＭ伝送路の本数を決めたときの本数から、個々のＴＤＭ伝送路に収容するデマンドを決めた際にＴＤＭ伝送路の本数が増えたかどうかを調べる（ステップＳ１６）。増えていない場合には、ステップＳ１８に進む。増えている場合には、その区間について、ＴＤＭ伝送路の数が元の値以下になるように、より容量の大きいＴＤＭ伝送路を適用する（ステップＳ１７）。ステップＳ１８では、波長数を超過した全区間について処理を終了したか否かを判断し、Ｎｏの場合にはステップＳ１５に戻って処理を続ける。Ｙｅｓの場合には、処理を終了する。
【００１７】
図５の場合はA-B間とD-E間のリンクについてＴＤＭ伝送路の本数が増えているため、例えば容量が１６のＴＤＭ伝送路を用いる。容量が８のＴＤＭ伝送路を３本のほかに、容量が１６のＴＤＭ伝送路を１本使えば全てのデマンドを収容でき、かつ合計本数も４本となり、元の値に戻る。
【００１８】
従来技術では、A-B間とD-E間の２箇所に容量が１６のＴＤＭ伝送路を用いたが、別の解として、A-E間のＴＤＭ伝送路について、容量が１６のＴＤＭ伝送路を１本使用する解がある。この場合、A-E間のＴＤＭ伝送路の合計本数は３本になる。ここでA-B間とD-E間のＴＤＭ伝送路の本数が合計５本に増えたとしても、A-E間のＴＤＭ伝送路の本数が３本になっているので、A-B間もD-E間もＴＤＭ伝送路の合計は８本となる。したがって、ＷＤＭで使える波長数を超過することはなく、かつ、使用した容量が１６のＴＤＭ伝送路の本数も１本で済む。このように、従来の技術では、より容量の大きいＴＤＭ伝送路をできるだけ使わずにコストの安い設計結果を得るという観点での最適解を得ることはできないという問題点があった。
従ってこのような場合でも最適解を得られるような技術が必要となってきた。
【００１９】
従来技術には、設備設計を行なった結果からリソースを一定割合削減し、光パスの迂回量、もしくは収容不可能パス数の許容値を満たす中で削減量が最大の光ネットワーク設備を解として得るものがある。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】特開２００５−８６６７５号
【発明の概要】
【発明が解決しようとする課題】
【００２１】
従来技術では、リンクにおけるＷＤＭで使える波長数よりもＴＤＭ伝送路の本数のほうが多くなってしまった場合に、個々のＴＤＭ伝送路ごとにより容量の大きいＴＤＭ伝送路を適用していた。このため、より容量の大きいＴＤＭ伝送路を使用する箇所が必要以上に多くなってしまい、コストの高い設計結果となってしまうことがあった。
【００２２】
以下の実施形態においては、より容量の大きいＴＤＭ伝送路を使用する箇所の数を最小にすることのできるネットワーク設計装置を提供する。
【課題を解決するための手段】
【００２３】
以下の実施形態の一側面におけるネットワーク設計装置は、波長多重技術によって複数の波長を用いてＴＤＭ（Time Divisional Multiplexing）伝送路を収容するネットワークのネットワーク設計装置において、少なくともデマンドの情報と、各リンクの利用可能な波長数の上限と、ＴＤＭ伝送路情報とが与えられ、リンクごとに利用可能な波長数を超えないようにデマンドを全て収容するために必要なＴＤＭ伝送路の本数をリンク毎に求める収容設計問題処理部と、求めたＴＤＭ伝送路の本数と収容するデマンドから各ＴＤＭ伝送路に収容するデマンドを決定する詰め込み問題処理部と、該詰め込み問題処理部の処理により、ＴＤＭ伝送路の本数がデマンドを収容する際に利用可能な波長数を超過したリンクの内、超過波長数が最も多い第１のリンクと、該第１のリンクから最も遠い第２のリンクついて利用可能な波長数を削減した制約条件を設定する処理を繰り返し、変更された制約条件の下に該収容設計問題処理部と詰め込み問題処理部により再度設計を行わせる繰り返し処理部とを備える。
【発明の効果】
【００２４】
以下の実施形態によれば、より容量の大きいＴＤＭ伝送路を使用する箇所の数を最小にすることのできるネットワーク設計装置を提供することができる。
【図面の簡単な説明】
【００２５】
【図１】従来技術を説明する図（その１）である。
【図２】従来技術を説明する図（その２）である。
【図３】従来技術を説明する図（その３）である。
【図４】従来技術を説明する図（その４）である。
【図５】従来技術を説明する図（その５）である。
【図６】従来技術を説明する図（その６）である。
【図７】本実施形態の第１の構成例を説明する図（その１）である。
【図８】本実施形態の第１の構成例を説明する図（その２）である。
【図９】本実施形態の第１の構成例を説明する図（その３）である。
【図１０】本実施形態の第１の構成例を説明する図（その４）である。
【図１１】本実施形態の第１の構成例を説明する図（その５）である。
【図１２】本実施形態の第１の構成例を説明する図（その６）である。
【図１３】本実施形態の第１の構成例を説明する図（その７）である。
【図１４】本実施形態の第１の構成例を説明する図（その８）である。
【図１５】本実施形態の第１の構成例を説明する図（その９）である。
【図１６】本実施形態の第１の構成例を説明する図（その１０）である。
【図１７】本実施形態の第１の構成例を説明する図（その１１）である。
【図１８】本実施形態の第１の構成例を説明する図（その１２）である。
【図１９】本実施形態の第１の構成例を説明する図（その１３）である。
【図２０】本実施形態の第１の構成例を説明する図（その１４）である。
【図２１】本実施形態の第１の構成例を説明する図（その１５）である。
【図２２】本実施形態の第１の構成例を説明する図（その１６）である。
【図２３】本実施形態の第１の構成例を説明する図（その１７）である。
【図２４】本実施形態の第１の構成例を説明する図（その１８）である。
【図２５】本実施形態の第１の構成例を説明する図（その１９）である。
【図２６】本実施形態の第１の構成例を説明する図（その２０）である。
【図２７】第２の構成例における第２のリンクを選択するフローの例である。
【図２８】第３の構成例におけるＴＤＭ伝送路を選択するフローの例である。
【図２９】第４の構成例におけるＴＤＭ伝送路を選択するフローの例である。
【図３０】第５の構成例におけるＴＤＭ伝送路を選択するフローの例である。
【図３１】第６の構成例におけるＴＤＭ伝送路を選択するフローの例である。
【図３２】第７の構成例におけるＴＤＭ伝送路を選択するフローの例である。
【図３３】波長数超過リンクを削除する部分のフローの例である。
【図３４】第８の構成例に対応する第１のリンクおよび第２のリンクを選択する部分のフローの例である。
【図３５】第９の構成例に対応する第１のリンクおよび第２のリンクを選択する部分のフローの例である。
【図３６】第１０の構成例に対応する第２のリンクを選択する部分のフローの例である。
【図３７】第１１の構成例に対応するフローである。
【図３８】ＴＤＭ伝送路の区間ごと・容量ごとのコストの例（その１）である。
【図３９】ＴＤＭ伝送路の区間ごと・容量ごとのコストの例（その２）である。
【図４０】高コストＴＤＭ伝送路を除外するフローである。
【図４１】ＴＤＭ伝送路を選択する際の候補から除外する方法の例である。
【図４２】本実施形態のネットワーク設計装置の機能ブロック図である。
【図４３】本実施形態の処理をプログラムで実現する場合の、プログラムを実行するコンピュータのハードウェア環境図である。
【発明を実施するための形態】
【００２６】
図７〜図２６は、本実施形態の第１の構成例を説明する図である。
第１の構成例では、リンクで使える波長数よりもＴＤＭ伝送路の本数が多くなってしまった場合に、リンクで使える波長数よりもＴＤＭ伝送路の本数が多いリンクをリストアップする。そのリストに含まれるリンクを最も多く含むＴＤＭ伝送路を選択する。そして、そのＴＤＭ伝送路の経路に含まれる、リンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクの中でＴＤＭ伝送路の本数がリンクで使える波長数を超過した量の最も大きいリンクを第１のリンクとして選択する。さらに、選択した第１のリンクから最も遠く、かつ選択したＴＤＭ伝送路の経路上にあり、かつ、リンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクを第２のリンクとして選択する。そして、選択した第１のリンクと第２のリンクについて、それぞれＴＤＭ伝送路の本数がリンクで使える波長数を超過した量だけリンクで使える波長数を減らした値を、そのリンクで使える波長数として再度設計を行う。これにより、より容量の大きいＴＤＭ伝送路を使う箇所ができるだけ少ない設計結果を得ることができる。
【００２７】
ＴＤＭ伝送路の数がリンクで使える波長数を超過しているリンクが複数あっても、より容量の大きいＴＤＭ伝送路をできるだけ少なく使用した設計結果を得ることができるようになる。
【００２８】
図７では、まず、トポロジ情報、デマンド情報、ＴＤＭ伝送路情報を入力する（ステップＳ２０）。図８にトポロジの例を示す。図８のトポロジについて、トポロジ情報の例を図９と図１０に示す。トポロジは、ノードとリンクの情報で、図９は、ノードのリストの例、図１０は、リンクのリストで、始終点のノード、距離（局舎間のファイバの長さ）、利用可能な波長数の情報が含まれている。
【００２９】
図１１にデマンドの例を示す。デマンド情報は、始終点と帯域、本数、経路の情報で構成される。経路の情報の表現方法はいくつかあるが、ここでは、経路上を通るノードを始点から終点まで順に書き並べた形で表現している。そのほかに、通るリンクの名称を始点から終点に順にリストする方法や、通る順にノードとリンクの名称を書き並べる方法もある。
【００３０】
ＴＤＭ伝送路情報は、ＴＤＭ伝送路を設定する区間を入力する。図１２はＴＤＭ伝送路の情報の例で、始点と終点と経路の情報で構成される。どのＴＤＭ伝送路を何本使うかは設計によって決まるため、設計の結果使われない、すなわち本数が０本になるＴＤＭ伝送路も含まれている。なお、図１２では後の説明のためにＴＤＭ伝送路の区間の番号の欄を付加してあるが、入力する情報としては特に必要はない。そのほかに収容設計問題処理のために、容量の異なるＴＤＭ伝送路として利用可能なものと、それらのコストを示す情報を入力する。ＴＤＭ伝送路の容量とコストの情報の例を図１３に示す。
【００３１】
次に、収容設計問題処理（図７のステップＳ２１）では、各ＴＤＭ伝送路の区間について、デマンドを収容するのに必要なＴＤＭ伝送路の本数を計算する。収容設計問題処理では、発見的手法によるアルゴリズムや数理計画法を使った方法などが利用可能である。最も簡単な方法は、デマンドを区間ごとに分けて、デマンドと同じ区間のＴＤＭ伝送路にそれぞれ収容する方法で、フローの例を図１４に示す。
【００３２】
まず、同一始終点かつ同一経路のデマンドを取り出し（ステップＳ４０）、デマンドの合計帯域を計算する(ステップＳ４１)。同一始終点かつ同一経路であれば帯域の異なるデマンドが混在してもよい。合計帯域はデマンドの帯域と本数の積で求めることができる。
【００３３】
例えば、図１１のN１からN２のデマンドの場合、帯域が６のデマンドが５本あるので、６×５で３０となる。次に、合計帯域をＴＤＭ伝送路の容量で割った値を整数に切り上げて、必要なＴＤＭ伝送路の本数を算出する（ステップＳ４２）。例えば、N１からN２のデマンドの場合、合計帯域は３０で、ＴＤＭ伝送路の容量は、図１３から８と３２で、８の場合は４、３２の場合は１である。次にコストを計算する（ステップＳ４３）。例えばN１からN２のデマンドで、ＴＤＭ伝送路の容量が８の場合は１本あたりのコストは１で、本数が４本なので、コストは４、容量が３２のＴＤＭ伝送路の場合は１本あたりのコストが４.１で、本数が１本なので、コストは４.１となる。次に、コストの最も安いＴＤＭ伝送路を選択する（ステップＳ４４）。例えば、N１からN２のデマンドの場合は、コストは、容量が８のＴＤＭ伝送路のほうが安いので、容量が８のＴＤＭ伝送路を選択する。
【００３４】
ステップＳ４５で、全てのデマンドを収容したか否かを判断する。全てのデマンドを収容していない場合は、ステップＳ４０に戻って処理を繰り返す。全てのデマンドを収容したら、次に、リンクごとに利用可能な波長数を超えているかどうかを確認する（ステップＳ４６）。超えていない場合は、それぞれのＴＤＭ伝送路がコスト最小の収容になっているため、設計終了となる。もし超えてしまっている場合は、次にコストの安いＴＤＭ伝送路を順に選択していく（ステップＳ４７）。この場合は、とり得る組合せを順に試し、リンクごとの利用可能な波長数を超えていないもので、かつ、コストのより安いほうを保持していく。すなわち、ステップＳ４８において、波長数超過リンクがある場合には、ステップＳ４７で再選択し、ない場合には、ステップＳ４９において、コストが安いか否かを判断する。ステップＳ４９で、コストが安くない場合には、ステップＳ５１に進む。コストが安い場合には、その結果を保持し、ステップｓ５１に進む。ステップＳ５１で、全組み合わせについて処理が終了したか否かを判断し、終了していない場合にはステップＳ４８に戻って処理を繰り返す。全組合せが終わった時点で設計は終了となる。
【００３５】
必要なＴＤＭ伝送路を求めた結果を図１５に示す。番号が５と８のＴＤＭ伝送路の本数は０になっているが、これはデマンドを収容するのに、この区間のＴＤＭ伝送路を使う必要がなかったため、使用されなかったことを示している。また、図１６に、リンクごとの、通っているＴＤＭ伝送路の本数を示す。例えば、リンクN１-N２の場合、N１-N２間のＴＤＭ伝送路１、N１-N３間のＴＤＭ伝送路４、N１-N５間のＴＤＭ伝送路６が通っていて、それぞれ４本、２本、３本であるため、合計９本の容量８のＴＤＭ伝送路が通っている。
【００３６】
このほかに、混合整数計画法を使って解く方法がある。混合整数計画法を使った方法の例を以下に説明する。ＴＤＭ伝送路の容量メニューをmとする。例えば、m=１は容量が８、m=２は容量３２、といったように決める。また、ＴＤＭ伝送路の番号をhとし、xm(h)を容量メニューmのＴＤＭ伝送路hの本数とする。例えば、容量８でN２とN３の間のＴＤＭ伝送路２は、x１(２)のように書ける。costmは容量メニューmのＴＤＭ伝送路のコストで、図１３のコストの欄の値である。この表記を使って、ＴＤＭ伝送路のコスト最小解を求めるための目的関数は、以下のようになる。
【数１】
0005794170.tif 000002
【００３７】
次にデマンドについての制約条件を示す。
【数２】
0005794170.tif 000003
【００３８】
ここで、Ｔ(l,t)をデマンド収容パターンtでデマンドlを収容できる場合は１、そうでない場合は０をとる変数とする。
【００３９】
発見的手法による方法で説明したような、どのデマンドをどのＴＤＭ伝送路に収容するかあらかじめ決めている場合と異なり、この場合はデマンドを収容する方法が何通りか存在することを前提にしている。そのため、例えばN１からN３のデマンドの場合、N１-N３というＴＤＭ伝送路を使って収容する方法とN１-N２とN２-N３の２つのＴＤＭ伝送路を使って収容する方法がある。tはその収容の仕方のパターンを全デマンドについて集めたものである。d(t)は、デマンド収容パターンtで収容するデマンドの本数を示している。例えばN１-N３のＴＤＭ伝送路を使う場合をt=１、N１-N２とN２-N３の２つのＴＤＭ伝送路を使う場合をt=２とし、N１からN３のデマンドをl=１として、４本ある場合、T(１,１)d(１)+T(１,２)d(２)=４のように書ける。T(１,１)とT(１,２)はともに１であるため、d(１)+d(２)=４で、t=１のパターンで収容するデマンドとt=２のパターンで収容するデマンドが合計で４本である。つまり、４本のデマンドはt=１か２のいずれかのパターンで収容されることを意味している。
【００４０】
次に、ＴＤＭ伝送路ごとの容量の制約条件を示す
【数３】
0005794170.tif 000004
【００４１】
Demand_Cap(t)は、デマンド収容パターンtについてのデマンド帯域、I(h,t)はＴＤＭ伝送路hがデマンド収容パターンtに含まれる場合は１、含まれない場合は０をとる。デマンド収容パターンは、N１からN３のデマンドについては前述の２通りだが、そのほかのデマンドについても同様にデマンド収容パターンがあり、例えばN１からN５のデマンドの場合、N１-N２,N２-N３,N３-N５やN１-N３,N３-N５やN１-N５がある。その中で、あるＴＤＭ伝送路は複数のデマンド収容パターンに出てくる。このため、例えば、N１-N３のＴＤＭ伝送路はN１からN３のデマンドのデマンド収容パターンN１-N３で収容されるデマンドと、N１からN５のデマンドのデマンド収容パターンN１-N３,N３-N５で収容されるデマンドの両方を収容することになる。このため、数３の式の第１項はＴＤＭ伝送路hが出てくるデマンド収容パターンtについて、デマンドの帯域とデマンド収容パターンtに収容されるデマンドの本数の合計したもの、つまり、ＴＤＭ伝送路hに収容するデマンドの合計帯域を示している。ＴＤＭ_CAP(m)は、容量メニューmのＴＤＭ伝送路の容量を示しており、前述の場合m=１は８、m=２は３２になる。第２項は容量メニューmのＴＤＭ伝送路hの合計容量で、式全体としてはＴＤＭ伝送路に収容するデマンドの合計帯域がＴＤＭ伝送路の合計容量を上回らないという意味になっている。
【００４２】
次に、リンクの波長数制限の制約式を示す。
【数４】
0005794170.tif 000005
【００４３】
Link(s,h)は、ＴＤＭ伝送路hがリンクsを通るとき１、通らないとき０となるもので、数４の式の左辺はリンクsを通るＴＤＭ伝送路の合計本数を示している。Wavelength(s)は、リンクsで利用可能な波長数を示しており、本実施形態では再設計の際に、このWavelength(s)の値を変更する。
【００４４】
以上の目的関数と３つの制約条件式を混合整数計画法によって解くことにより、各ＴＤＭ伝送路の本数xm(h)が求められる。混合整数計画法の解法は一般に知られており、例えば下記の参考文献に記載される方法などで解くことができる。
坂和正敏著、「離散システムの最適化」、森北出版、２０００年５月発行
【００４５】
また、混合整数計画法などの数理計画法のソルバはたくさんあり、機能を限定した特殊用途専用のものを除けばいずれも利用可能である。例えば、以下のようなフリーソフトや市販のソルバが使える。
GLPK: フリーソフト(http://www.gnu.org/s/glpk/)
CPLEX: 市販ソフト (旧ILOG、ILOGがIBMに買収されたため、現在IBMが販売)
【００４６】
次に、詰め込み問題処理（図７のステップＳ２２）では、個々のＴＤＭ伝送路に収容するデマンドを決定する。必要なＴＤＭ伝送路の本数が図１５に示してある。収容するデマンドを、ここでは例として、ＴＤＭ伝送路と始終点と経路が同一のものとしているため、例えば、１番のＴＤＭ伝送路の場合は、N１からN２のデマンド５本（図１１参照）ということになる。個々のＴＤＭ伝送路に収容するデマンドを決定する方法は、発見的手法や数理計画法におけるビンパッキング問題などを用いる方法などがある。
【００４７】
ビンパッキング問題の解法のアルゴリズムは、例えば、以下の文献に記載がある。
V.V.Vazirani著, 浅野孝夫訳, "近似アルゴリズム (Approximation Algorithm)", 
pp.７６-８０, シュプリンガージャパン, ２００２.１１
【００４８】
図１７に発見的手法による個々のＴＤＭ伝送路に収容するデマンドを決定するフローの例を示す。
新しいＴＤＭ伝送路を用意し（ステップＳ６０、新しいＴＤＭ伝送路を示すデータを初期化する）、帯域の多い順にデマンドを取り出し（ステップＳ６１）、ＴＤＭ伝送路の容量に空きがあれば収容していく（ステップＳ６２、Ｓ６３）。ステップＳ６４で、全デマンドについて処理が終了したか否かを判断する。終わっていない場合には、ステップＳ６１に戻って処理を繰り返す。全デマンドについて終わった時点で、ステップＳ６５で未収容のデマンドがあるか否かを判断する。未収容のデマンドが残っていれば、新しいＴＤＭ伝送路を用意して、再度繰り返す。未収容のデマンドがなければ終了となる。
【００４９】
図１８に、個々のＴＤＭ伝送路にデマンドを割り当てた後のＴＤＭ伝送路の本数を示す。例えば、N１-N２の場合は、帯域６のデマンドが５本ある場合で、前述のように１本のデマンドを複数のＴＤＭ伝送路に分割して収容することができないため、実際には帯域６のデマンドを１本ずつ容量８のＴＤＭ伝送路に入れて、合計５本のＴＤＭ伝送路が必要となる。N２-N３のＴＤＭ伝送路やN６-N３のＴＤＭ伝送路も同様である。N４-N５のＴＤＭ伝送路の場合は、帯域６のデマンドが８本あるため、帯域としては容量が８のＴＤＭ伝送路が６本で足りる。しかし、前述のようにデマンドを複数のＴＤＭ伝送路に分割して収容することができないため、実際には２本多い８本のＴＤＭ伝送路が必要となる。
【００５０】
図１９に個々のＴＤＭ伝送路に収容するデマンドを決定した後のリンクごとの通っているＴＤＭ伝送路の本数を示す。図１９で、本数の欄に太文字で下線のついているものは、ＴＤＭ伝送路の本数がリンクで使える波長数９を超えているものを示している。
【００５１】
次に、本実施形態では、リンクごとの波長数の制限を確認する（図７のステップＳ２３）。図７のステップＳ２４において、波長数が超過したリンクがあるか否かを判断する。そして、全てのリンクについて、リンクを通っているＴＤＭ伝送路の本数がリンクで使える波長数以下であれば、図７のステップＳ３２で結果を出力して設計を終了する。１箇所でもＴＤＭ伝送路の本数がリンクで使える波長数を超過しているリンクがあれば、波長数超過リンクリストを生成する（図７のステップＳ２５）。例えば、図１９のような結果になった場合、リンクN１-N２、N２-N３、N４-N５、N６-N３について、通っているＴＤＭ伝送路の本数がリンクで使える波長数を超過しているため、図２０に示すような波長数超過リンクリストを生成する。図２０では、リンクをリンクの始終点で記載しているが、リンクに識別子や識別番号がついている場合は、その識別子や識別番号などを代わりに入れても良い。
【００５２】
次に、本実施形態では、ＴＤＭ伝送路の選択を行う（図７のステップＳ２６）。ＴＤＭ伝送路の選択は、ＴＤＭ伝送路の経路上に、波長数超過リンクリストに含まれるリンクを最も多く含むＴＤＭ伝送路を選択するもので、図２１にフローの例を示す。
【００５３】
図２１では、まず順にＴＤＭ伝送路を取り出し(ステップＳ７０)、経路に含まれるリンクが波長数超過リンクに含まれる場合には、一時リストにそのリンクを入れる（ステップＳ７１）。例えば、図１２のＴＤＭ伝送路の情報から、ＴＤＭ伝送路の番号順にＴＤＭ伝送路の経路を取り出す。図１２の場合は、経路情報が通るノードのリストになっているため、隣接する２つのノード間がリンクである。
【００５４】
例えば、ＴＤＭ伝送路１の経路情報はN１,N２であるため、リンクN１-N２が通るリンクになる。取り出したリンクを図２０の波長数超過リンクリストの内容と比較すると、N１-N２は波長数超過リンクリストにあるため、リンクN１-N２を一時リストに入れる。次に、保存リストと一時リストのエントリ数を比較する（ステップＳ７２）。保存リストは、最初は空であるため、この場合は、エントリ数は、０、一時リストはリンクN１-N２の１つのエントリがあるため、エントリ数は１になる。従って、一時リストのほうがエントリ数が多いため、保存リストの内容を一時リストの内容に置き換える（ステップＳ７３）。すなわち、保存リストの内容は{N１-N２}になる。このとき、保存リストに入れてあるリンクが、どのＴＤＭ伝送路のものかわかるよう、ＴＤＭ伝送路の番号などをメモリに記憶しておく。例えば、図２１のフローでは、Indxという変数に格納している。このメモリは、保存リストを置き換える時に書き換えていく。次に、ＴＤＭ伝送路２を取り出して同様に処理を行うと、一時リストにはリンクN２-N３が入る。このとき、保存リストのエントリ数は１で、一時リストのエントリ数も１であるため、保存リストはそのままとなる。次にＴＤＭ伝送路３についても同様で、この場合も保存リストはそのままである。次にＴＤＭ伝送路４の場合は、経路がN１,N２,N３であるため、リンクはN１-N２とN２-N３の２つあり、いずれも波長数超過リンクリストにあるため、一時リストにはリンクN１-N２とN２-N３の２つが入る。この場合は保存リストのエントリ数が１で一時リストのエントリ数が２であるため、保存リストの内容は一時リストと置き換えられて、{N１-N２, N２-N３}となる。同様にＴＤＭ伝送路６の場合は経路がN１,N２,N３,N４,N５でN１-N２, N２-N３, N３-N４, N４-N５の４つのリンクを通り、そのうちN１-N２, N２-N３, N４-N５の３つのリンクが波長数超過リンクリストにあるため、一時リストにはリンクN１-N２, N２-N３, N４-N５が入る。したがって、保存リストのエントリ数が２で一時リストのエントリ数が３であるため、保存リストは{ N１-N２, N２-N３, N４-N５}となる。そして、ステップＳ７４で、全ＴＤＭ伝送路について処理が終わったか否かを判断する。終わってない場合には、ステップＳ７０に戻って処理を繰り返す。全てのＴＤＭ伝送路について調べ終わると、保存リストには、最も波長数超過リンクを多く含むＴＤＭ伝送路の波長数超過リンクが、メモリには、そのＴＤＭ伝送路の番号が残る。このメモリに残っているＴＤＭ伝送路が選択されたＴＤＭ伝送路となる。この場合はＴＤＭ伝送路６である。
【００５５】
次に、図７で、第１のリンクを選択する（ステップＳ２７）。第１のリンクは、保存リストに入っているリンクの中で、最もＴＤＭ伝送路の本数がリンクで使える波長数を超過した量の多いものを選択する。
【００５６】
第１のリンクを選択するフローを図２２に示す。ステップＳ８０において、maxLinkという変数に保存リストの最初のリンクを格納する。次に、保存リストからリンクを順に取り出して（ステップＳ８１）、maxLinkという変数に入れてあるリンクの超過波長数と取り出したリンクの超過波長数を比較し（ステップＳ８２）、多いほうをmaxLinkに入れておくステップＳ８３）。これを全リンクについて行う（ステップＳ８４）。
【００５７】
超過波長数の求め方は、例えばN１-N２の場合、保存リストと図１９から、N１-N２のＴＤＭ伝送路の本数は１０で、使える波長数は図１０から９であるため、ＴＤＭ伝送路の本数が使える波長数を超過した量、すなわち、超過波長数は１となる。N２-N３についても同様に超過波長数は１、N４-N５については、超過波長数は２となる。この中で超過波長数の最も多いのはN４-N５であるため、第１のリンクにはN４-N５が選ばれる。
【００５８】
次に第２のリンクを選択する（図７のステップＳ２８）。第２のリンクは、保存リストに含まれるリンクの中で、第１のリンクから最も距離の遠いものを選ぶ。
第２のリンクを選択するフローを図２３に示す。距離を計算する際の経路は、ＴＤＭ伝送路の選択（図７のステップＳ２６）で選択されたＴＤＭ伝送路の経路を用いる。リンク間の距離は、例えば、第１のリンクの両端のノードのうち、処理対象となるリンクに近いほうのノードから、処理対象となるリンクの両端のノードのうち、第１のリンクに近いほうのノードまでの距離とすることができる。ここで、距離はファイバ長である。フローは、保存リストのリンクを順に取り出し、第１のリンクからの距離の長いほうをmaxLink２という変数に入れていくというものである。ただし、保存リストのエントリ数が１の場合、すなわち、波長数超過リンクが１つしかない場合は、第２のリンクを選択することはできないため、第２のリンクなしで終了する。ステップＳ９０で、保存リストのエントリ数が１か否かを判断する。Ｙｅｓの場合には、第２のリンクなしで終了する。Ｎｏの場合には、ステップＳ９６において、maxLink２に、保存リストの最初のリンクを格納する。たとえば、maxLink２には、最初、N１-N２が設定される。ステップＳ９１において、保存リストの次のリンクを順に選択し（たとえば、N２-N３が選択される）、ステップＳ９２において、第１のリンクの両端のうち近いほうのノードからの距離を計算する。ステップＳ９３において、選択したリンクの距離がmaxLink２に格納されているリンクの距離より大きいか否かを判断する。ステップＳ９３の判断がＮｏの場合には、ステップＳ９５に進む。ステップＳ９３の判断がＹｅｓの場合には、maxLink２に選択したリンクを格納し、ステップＳ９５に進む。ステップＳ９５では、全リンクについて選択したか否かが判断され、Ｎｏの場合にはステップＳ９１に戻り、Ｙｅｓの場合には処理を終了する。
【００５９】
保存リストにはN４-N５以外にN１-N２とN２-N３のリンクがあり、例えば、N１-N２の場合は、N４,N５のうちN１-N２に近いほうのノードN４と、N１,N２のうちN４-N５に近いN２との間の距離で、この場合は図１０から１０kmとなる。同様にN２-N３の場合は４kmとなる。この２つの中で距離の長いほうを第２のリンクとして選択する。この場合はN１-N２が第２のリンクとして選択される。
【００６０】
次に、選択した第１のリンクと第２のリンクについて、新しい利用可能波長数を決定する（図７のステップＳ２９）。新しい波長数は、元の利用可能な波長数から、超過波長数を引いた値で定義される。例えば、第１のリンクN４-N５の場合は元の利用可能波長数が９で超過波長数が２であるため、新しい利用可能波長数は７となる。同様に第２のリンクN１-N２の場合は８になる。
【００６１】
次に波長数超過リンクの削除を行う（図７のステップＳ３０）。ここでは、保存リストにあるリンクを波長数超過リンクリストから削除する処理を行う。従って、N１-N２, N２-N３, N４-N５が削除される。図７のステップＳ３１で、波長数超過リンクリストが空か否かを判断する。削除した時点で波長数超過リンクリストにはN６-N３が残っているため、再度、上記処理（図７のステップＳ２６〜Ｓ３０）を繰り返す。この場合は、波長数超過リンクが１つしかないため、第２のリンクを選ぶことはできないので、第１のリンクの選択のみを行い、第１のリンクについてのみ新しい利用可能波長数を求める。この場合、第１のリンクはN６-N３で、新しい利用可能波長数は８となる。
【００６２】
N６-N３を波長数超過リンクリストから削除すると、波長数超過リンクリストは空になるため、図１０のリンクのリストを新しい利用可能波長数に置き換えたものを作成し、それに基づいて再度設計を行う。新しいリンクのリストを図２４に示す。図２４では、利用可能波長数を置き換えた箇所を太線に下線をつけて示している。
【００６３】
次に再設計を行う（図７で、ステップＳ２１に戻って、ステップS２１〜S２４を行う）。再設計では、全て容量８のＴＤＭ伝送路で設計することはできないので、どこかに容量３２のＴＤＭ伝送路を用い、容量３２のＴＤＭ伝送路の本数が最小となるものがコスト最小解となる。
【００６４】
まずN１-N２, N４-N５の各リンクを通るデマンドの収容に容量３２のＴＤＭ伝送路を適用する場合、N１-N２とN４-N５のデマンドに適用する方法、N１-N３とN４-N５のデマンドに適用する方法、N１-N５のデマンドに適用する方法がある。N１-N２のデマンドは帯域が６で本数が５なので、容量３２のＴＤＭ伝送路であれば１本で全て収容できる。また、N４-N５のデマンドは帯域が６で本数が８なので、容量３２のＴＤＭ伝送路が１本と容量８のＴＤＭ伝送路が３本あれば収容できる。N１-N５のデマンドの場合は帯域が４で本数が６なので、容量３２のＴＤＭ伝送路が１本あれば収容できる。この中で容量３２のＴＤＭ伝送路の本数が最も少ないのはN１-N５のデマンドに適用する場合なので、この解が選ばれる（容量３２のＴＤＭ伝送路は、本数が多いほどよりコストが多くなるので、本数の最も少ないものがコスト最小として選ばれる）。
【００６５】
N６-N３については、容量３２のＴＤＭ伝送路をN６-N３のデマンドの収容に適用する場合とN６-N７のデマンドの収容に適用する場合がある。N６-N３のデマンドは帯域が６で本数が５なので、容量３２のＴＤＭ伝送路であれば１本で全て収容できる。一方、N６-N７のデマンドは帯域が４で本数が１０であるため、容量３２のＴＤＭ伝送路が１本と容量８のＴＤＭ伝送路が１本必要になる。合計帯域から計算すると（図１１のリンクに収容するデマンドの合計帯域から、デマンドが分割できないことを無視して計算すると）、N６-N３に適用した場合は、合計で容量３２のＴＤＭ伝送路が１本か、容量８のＴＤＭ伝送路が５本となる。またN６-N７に適用した場合は、容量３２のＴＤＭ伝送路１本か容量８のＴＤＭ伝送路が５本となる。容量８のＴＤＭ伝送路の本数の内訳は、N６-N３が合計帯域から計算しているため４本で、N６-N７の容量３２のＴＤＭ伝送路に収容しきれない分を収容する１本である。コストとしては同じになるため実装によって結果は異なるが、ここではN６-N３に適用されるとする。
【００６６】
個々のＴＤＭ伝送路へ収容するデマンドを決定した後の設計結果のＴＤＭ伝送路の本数を図２５に、リンクごとの通っているＴＤＭ伝送路の本数を図２６に示す。図２６で、本数が太線の下線で示してあるところは、最初の設計でＴＤＭ伝送路の本数がリンクで使える波長数を超過したところである。以上のようにしてリンクで使える波長数の制限を満たしながら、コスト最小の設計結果を得ることができる。
【００６７】
第２の構成例における第２のリンクを選択するフローの例を図２７に示す。
図２７において、図２３と同じステップには、同じステップ番号を付して、これらの説明を省略する。
【００６８】
図２３に示す、第１の構成例における第２のリンクを選択するフローとの違いは、第１のリンクからの距離のかわりに第１のリンクからのホップ数（リンク数）を用いている点である（ステップＳ１００、Ｓ１０１）。ホップ数は、第１のリンクの両端のノードのうち、第２のリンクに近いほうのノードから、第２のリンクの両端のノードのうち、第１のリンクに近いノードまでの間にあるリンクの数である。例えば、ＴＤＭ伝送路としてＴＤＭ伝送路６（図１２参照）が選ばれたとする。第１のリンクにN４-N５が選ばれた場合に、例えば、N１-N２のリンクとN４-N５のリンクの間のホップ数は、図１２のＴＤＭ伝送路６の経路から、N２とN４の間にあるリンクの数となり、この場合はN２-N３とN３-N４の２つであるため、ホップ数は２となる。それ以外の部分の動作は第１の構成例と同じである。
【００６９】
本実施形態の第２の構成例では、第２のリンクを選択する際に、先に選択した第１のリンクからのホップ数が最も多く、かつ、選択したＴＤＭ伝送路の経路上にあり、かつ、リンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクを第２のリンクとして選択する。より容量の大きいＴＤＭ伝送路を使う箇所のできるだけ少ない設計結果を得ることができる。
【００７０】
これにより、ＴＤＭ伝送路の経路上に極端に距離の長い（ホップ数が多い）リンクが含まれていても、より容量の大きいＴＤＭ伝送路をできるだけ少なく使用した設計結果を得ることができるようになる。
【００７１】
第３の構成例におけるＴＤＭ伝送路を選択するフローの例を図２８に示す。
図２８において、図２１と同じステップには、同じステップ番号を付し、これらの説明を省略する。
【００７２】
ＴＤＭ伝送路を順に取り出す際に、同一始終点のＴＤＭ伝送路の数が２本以上ないと、より容量の大きいＴＤＭ伝送路を適用してもＴＤＭ伝送路の本数を減らすことができない。このため、第１の構成例におけるＴＤＭ伝送路の選択処理とは違い、取り出したＴＤＭ伝送路と同一始終点のＴＤＭ伝送路が２本以上あるかどうかを調べ（ステップＳ１０５）、１本しかない場合には、次のＴＤＭ伝送路を取り出すようにする点である。始終点が同一のＴＤＭ伝送路が２本以上ある場合の処理は第１の構成例の場合と同じである。また、ＴＤＭ伝送路を選択するステップ以外の部分は第１の構成例と同じである。
【００７３】
本実施形態の第３の構成例では、ＴＤＭ伝送路を選択する際に、リンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクを最も多く含み、かつ、同じ区間のＴＤＭ伝送路の本数が２本以上あるＴＤＭ伝送路を選択する。これにより、より容量の大きいＴＤＭ伝送路を使う箇所のできるだけ少ない設計結果を得ることができる。
【００７４】
より容量の大きいＴＤＭ伝送路を適用してもＴＤＭ伝送路の本数が削減できないＴＤＭ伝送路が混在している場合でも、より容量の大きいＴＤＭ伝送路をできるだけ少なく使用した設計結果を得ることができるようになる。
【００７５】
第４の構成例におけるＴＤＭ伝送路を選択するフローの例を図２９に示す。
図２９において、図２１と同じステップには、同じステップ番号を付し、これらの説明を省略する。
【００７６】
第１の構成例におけるＴＤＭ伝送路の選択処理との違いは、波長数超過リンクリストにあるリンクを最も多く含むものが複数あった場合に、同一始終点のＴＤＭ伝送路の本数の最も多いものを選択する点である。これによると、同一始終点のＴＤＭ伝送路が多いと、より容量の大きいＴＤＭ伝送路を用いた際に、そのＴＤＭ伝送路の空き部分がより小さくなることが期待できるからである。フローでは、まず、ステップＳ７０、Ｓ７１を行う。そして、一時リストと保存リストのエントリ数を比較し、一時リストのエントリ数が保存リストのエントリ数以上の場合（ステップＳ１１１）、さらに一時リストと保存リストのエントリ数が同じかどうかを調べ（ステップＳ１１０）、同じ場合にはさらに今選択したＴＤＭ伝送路と始終点の同じＴＤＭ伝送路の本数と、Indxに入っているＴＤＭ伝送路と始終点が同じＴＤＭ伝送路の本数とを比較する（ステップＳ１１２）。前者のほうが大きい場合は保存リストを更新し、そうでない場合は保存リストを更新しない。一時リストのエントリ数が保存リストのエントリ数と同じでない場合の動作は第１の構成例の場合と同じである。また、ＴＤＭ伝送路を選択する処理以外の部分は第１の構成例と同じである。
【００７７】
保存リストと一時リストのエントリ数を比較する（ステップＳ１１０）。保存リストは、最初は空であるため、この場合は、エントリ数は、０、一時リストはリンクN１-N２の１つのエントリがあるため、エントリ数は１になる。従って、一時リストのほうがエントリ数が多いため、ステップＳ１１１に進む。ステップＳ１１１では、保存リストのエントリ数と一時リストのエントリ数が等しいか否かを判断する。今の場合、等しくないので、保存リストの内容を一時リストの内容に置き換える（ステップＳ７３）。すなわち、保存リストの内容は{N１-N２}になる。このとき、保存リストに入れてあるリンクが、どのＴＤＭ伝送路のものかわかるよう、ＴＤＭ伝送路の番号などをメモリに記憶しておく。例えば、図２９のフローでは、Indxという変数に格納している。このメモリは、保存リストを置き換える時に書き換えていく。次に、ＴＤＭ伝送路２を取り出して同様に処理を行うと、一時リストにはリンクN２-N３が入る。このとき、保存リストのエントリ数は１で、一時リストのエントリ数も１であるため、ステップＳ１１２において、IndxのＴＤＭ伝送路と同一始終点のＴＤＭ伝送路の本数よりも選択したＴＤＭ伝送路と同一始終点のＴＤＭ伝送路の本数が多いか否かを判断する。ステップＳ１１２の判断がＮｏの場合には、ステップＳ７４に進み、保存リストはそのままとなる。ステップＳ１１２の判断がＹｅｓの場合には、保存リストの内容を一時リストと置き換え、Indxに今選んだＴＤＭ伝送路の番号を設定する。次にＴＤＭ伝送路３についても同様で、この場合も保存リストはそのままである。次にＴＤＭ伝送路４の場合は、経路がN１,N２,N３であるため、リンクはN１-N２とN２-N３の２つあり、いずれも波長数超過リンクリストにあるため、一時リストにはリンクN１-N２とN２-N３の２つが入る。この場合は保存リストのエントリ数が１で一時リストのエントリ数が２であるため、ステップＳ７３で、保存リストの内容は一時リストと置き換えられて、{N１-N２, N２-N３}となる。同様にＴＤＭ伝送路６の場合は経路がN１,N２,N３,N４,N５でN１-N２, N２-N３, N３-N４, N４-N５の４つのリンクを通り、そのうちN１-N２, N２-N３, N４-N５の３つのリンクが波長数超過リンクリストにあるため、一時リストにはリンクN１-N２, N２-N３, N４-N５が入る。したがって、保存リストのエントリ数が２で一時リストのエントリ数が３であるため、保存リストは{ N１-N２, N２-N３, N４-N５}となる。そして、ステップＳ７４で、全ＴＤＭ伝送路について処理が終わったか否かを判断する。終わってない場合には、ステップＳ７０に戻って処理を繰り返す。全てのＴＤＭ伝送路について調べ終わると、保存リストには、最も波長数超過リンクを多く含むＴＤＭ伝送路の波長数超過リンクが、メモリには、そのＴＤＭ伝送路の番号が残る。このメモリに残っているＴＤＭ伝送路が選択されたＴＤＭ伝送路となる。この場合はＴＤＭ伝送路６である。
【００７８】
本実施形態の第４の構成例では、ＴＤＭ伝送路を選択する際に、リンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクを最も多く含み、かつ、同じ区間（始終点が同一）のＴＤＭ伝送路の本数が最も多いＴＤＭ伝送路を選択する。これにより、より容量の大きいＴＤＭ伝送路を使う箇所のできるだけ少ない設計結果を得ることができる。
【００７９】
より容量の大きいＴＤＭ伝送路を適用することでより確実にＴＤＭ伝送路の数を削減できるＴＤＭ伝送路を選択することで、より確実に少ない繰り返し回数で、より容量の大きいＴＤＭ伝送路をできるだけ少なく使用した設計結果を得ることができるようになる。
【００８０】
第５の構成例では、ＴＤＭ伝送路を選択する処理が第１の構成例と異なる。第５の構成例におけるＴＤＭ伝送路を選択するフローの例を図３０に示す。
図３０において、図２９と同じステップには、同じステップ番号を付し、これらの説明を省略する。
【００８１】
第１の構成例におけるＴＤＭ伝送路の選択処理との違いは、波長数超過リンクリストにあるリンクを最も多く含むものが複数あった場合に、一時リストに含まれるリンクを全て通るＴＤＭ伝送路の本数の最も多いものを選択する点である。例えば、図８のようなトポロジの場合で、N１-N２リンクを通るＴＤＭ伝送路として、N１からN２のＴＤＭ伝送路のほかに、N１からN３のＴＤＭ伝送路もN１-N２リンクを通る。ここで、例えばN１-N２リンクが波長数超過リンクとすると、N１からN２のＴＤＭ伝送路により容量の大きいＴＤＭ伝送路を適用し、N１からN３のＴＤＭ伝送路に元々収容されていたデマンドも一緒に収容する。そうすると、N１-N２リンクについてはN１からN２のＴＤＭ伝送路の分とN１からN３のＴＤＭ伝送路の分がより容量の大きいＴＤＭ伝送路に収容され、N１-N２リンクのＴＤＭ伝送路の本数を大きく減らすことができる。このとき、N２からN３にＴＤＭ伝送路を新たに設置し、N１からN３へのデマンドは、N１からN２まではN１からN２のＴＤＭ伝送路を用いて収容され、N２からN３まではN２からN３のＴＤＭ伝送路を用いて収容される。N２ではスイッチやクロスコネクト装置などを用いて接続される。
【００８２】
図３０では、変数T０cntを０に初期化する。そして、ステップＳ７０、Ｓ７１を行う。そして、一時リストと保存リストのエントリ数を比較し、一時リストのエントリ数が保存リストのエントリ数以上の場合（ステップＳ１１０）、さらに、一時リストと保存リストのエントリ数が同じ（ステップＳ１１１）かどうかを調べる。同じ場合には、さらに一時リストに含まれるリンクを全て通るＴＤＭ伝送路の本数をTcntという変数に入れる（ステップＳ１２０）。順にＴＤＭ伝送路を取り出して、経路に含まれるリンクの中に一時リストに含まれるリンクが全て含まれるかを調べ、全て含まれる場合にはそのＴＤＭ伝送路の本数を積算すればよい。この本数には、今選択しているＴＤＭ伝送路の本数も含まれる。次に、変数T０cntと比較する（ステップＳ１２１）。Tcntのほうが大きい場合には、保存リストを更新し、T０cnt=Tcntとする（ステップＳ１２３）。従って、T０cntには、保存リストに含まれるリンクを全て通るＴＤＭ伝送路の本数の合計が入っていることになる。一時リストのエントリ数が保存リストのエントリ数と同じでない場合の動作は第１の構成例の場合と同じである。また、ＴＤＭ伝送路を選択する処理以外の部分は第１の構成例と同じである。
【００８３】
本実施形態の第５の構成例では、ＴＤＭ伝送路を選択する際に、リンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクを最も多く含み、かつ、このＴＤＭ伝送路に含まれるリンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクを全て通るＴＤＭ伝送路の本数の合計が最も多いＴＤＭ伝送路を選択する。これにより、より容量の大きいＴＤＭ伝送路を使う箇所のできるだけ少ない設計結果を得ることができる。
【００８４】
より容量の大きいＴＤＭ伝送路を適用することでより確実にＴＤＭ伝送路の数を削減できるＴＤＭ伝送路を選択することで、より確実に少ない繰り返し回数で、より容量の大きいＴＤＭ伝送路をできるだけ少なく使用した設計結果を得ることができるようになる。
【００８５】
第６の構成例では、ＴＤＭ伝送路を選択する処理が第１の構成例と異なる。第６の構成例におけるＴＤＭ伝送路を選択するフローの例を図３１に示す。
図３１において、図３０と同じステップには、同じステップ番号を付し、これらの説明を省略する。
【００８６】
第１の構成例におけるＴＤＭ伝送路の選択処理との違いは、波長数超過リンクリストにあるリンクを最も多く含むものが複数あった場合に、一時リストに含まれるリンクを全て通り、かつ、端点のいずれかが今選択しているＴＤＭ伝送路の始点と一致するＴＤＭ伝送路の本数か、または、端点のいずれかが今選択しているＴＤＭ伝送路の終点と一致するＴＤＭ伝送路の本数のうち多いほうの値が最も多いものを選択する点である。
【００８７】
図３１のフローでは、まず、ステップＳ１２４で、変数Thcnt、Ttcnt、Tcnt２を０に初期化する。そして、ステップＳ７０、Ｓ７１を行う。そして、一時リストと保存リストのエントリ数を比較し、一時リストのエントリ数が保存リストのエントリ数以上の場合（ステップＳ１１０）は、さらに、一時リストと保存リストのエントリ数が同じかどうかを調べる（ステップＳ１１１）。同じ場合には、まず一時リストに含まれるリンクを全て通り、かつ、今選択しているＴＤＭ伝送路の始点と端点のいずれかが一致するＴＤＭ伝送路の本数を数え、Thcntに入れる（ステップＳ１２５）。次に、一時リストに含まれるリンクを全て通り、かつ、今選択しているＴＤＭ伝送路の始点と端点のいずれかが一致するＴＤＭ伝送路の本数を数え、Ttcntに入れる(ステップＳ１２６)。そしてThcntとTtcntのうち、大きいほうをTcnt２に入れる（ステップＳ１２７、Ｓ１２８、Ｓ１２９）。図３１の例では、値が同じ場合はThcntを入れるようにしている。Tcnt２をT０cnt２と比較する（ステップＳ１３０）。Tcnt２のほうが大きい場合には保存リストの内容を一時リストの内容と入れ替え、Indxを今選んだＴＤＭ伝送路の番号にし、T０cnt２=Tcnt２とする。一時リストのエントリ数が保存リストのエントリ数と同じでない場合の動作は第１の構成例の場合と同じである。また、ＴＤＭ伝送路を選択する処理以外の部分は第１の構成例と同じである。
【００８８】
本実施形態の第６の構成例では、ＴＤＭ伝送路を選択する際に、リンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクを最も多く含み、かつ、このＴＤＭ伝送路に含まれるリンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクを全て通り、かつ、選択したＴＤＭ伝送路の始点か終点のいずれかが一致するＴＤＭ伝送路の本数の合計が最も多いＴＤＭ伝送路を選択する。これにより、より容量の大きいＴＤＭ伝送路を使う箇所のできるだけ少ない設計結果を得ることができる。
【００８９】
より容量の大きいＴＤＭ伝送路を適用することでより確実にＴＤＭ伝送路の数を削減できるＴＤＭ伝送路を選択することで、より確実に少ない繰り返し回数で、より容量の大きいＴＤＭ伝送路をできるだけ少なく使用した設計結果を得ることができるようになる。
【００９０】
第７の構成例では、ＴＤＭ伝送路を選択する処理と波長数超過リンクを削除する処理の部分が第１の構成例と異なる。第７の構成例におけるＴＤＭ伝送路を選択するフローの例を図３２に、波長数超過リンクを削除する部分のフローの例を図３３に示す。
【００９１】
図３２において、図３１と同じステップには、同じステップ番号を付し、これらの説明を省略する。
まず、図３３において、第１の構成例における波長数超過リンクを削除する部分との違いは、保存リストにあるリンクを波長数超過リンクリストから削除する手順（ステップＳ１３９）に加えて、保存リストのリンクを削除済みリストに加える手順（ステップＳ１３８）が加わっていることである。２つの手順の間には特に順序関係はなく、図３３と逆の順序でもよい。
【００９２】
削除済みリストは、最初に波長数超過リンクリストにあったリンクのうち、波長数超過リンクリストから削除されたリンクが入っているものである。ＴＤＭ伝送路の選択処理の違いは、波長数超過リンクリストにあるリンクを最も多く含むものが複数あった場合に、ＴＤＭ伝送路の経路に含まれるリンクで、削除済みリストにあるリンクの数が最も少ないものを選択する点である。
【００９３】
図３２のフローでは、まず、ステップＳ１３４で、Tdel、T０delを０に初期化する。そして、ステップＳ７０、Ｓ７１を行う。そして、一時リストと保存リストのエントリ数を比較し、一時リストのエントリ数が保存リストのエントリ数以上の場合（ステップＳ１１０）は、さらに、一時リストと保存リストのエントリ数が同じかどうかを調べる（ステップＳ１１１）。同じ場合には、今選択しているＴＤＭ伝送路の経路に含まれるリンクのうち、削除済みリストに含まれるリンクの数をカウントし、Tdelに入れる（ステップＳ１３５）。次に、TdelとT０delを比較し(ステップＳ１３６)、Tdelのほうが小さければ保存リストの内容を一時リストの内容と入れ替え、T０del=Tdelとする(ステップＳ１３７)。一時リストのエントリ数が保存リストのエントリ数と同じでない場合の動作は第１の構成例の場合と同じである。また、ＴＤＭ伝送路を選択する処理および波長数超過リンクを削除する部分以外の部分は第１の構成例と同じである。
【００９４】
本実施形態の第７の構成例では、ＴＤＭ伝送路を選択する際に、リンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクを最も多く含み、かつ、先にリンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクのリストから削除されたリンクを含む数が最も少ないＴＤＭ伝送路を選択する。これにより、より容量の大きいＴＤＭ伝送路を使う箇所のできるだけ少ない設計結果を得ることができる。
【００９５】
より容量の大きいＴＤＭ伝送路を適用することでより確実にＴＤＭ伝送路の数を削減できるＴＤＭ伝送路を選択することで、より確実に少ない繰り返し回数で、より容量の大きいＴＤＭ伝送路をできるだけ少なく使用した設計結果を得ることができるようになる。
【００９６】
第８の構成例では、第１のリンクと第２のリンクを選択する部分が第１の構成例と異なる。第８の構成例に対応する第１のリンクおよび第２のリンクを選択する部分のフローの例を図３４に示す。
【００９７】
第８の構成例では、第１のリンクを選択する部分と第２のリンクを選択する部分はひとつになっていて、２つのリンクを同時に選択する。図３４のフローは、図７において、第１のリンクと第２のリンクを選択する部分のみを取り出した図である。図３４のフローでは、まず、ステップＳ１４４で、変数Lindx１、Lindx２、Tc０１２、Tc１２を初期化する。そして、保存リストのリンクを順に第１のリンクとして取り出す（ステップＳ１４５）。次に、第１のリンク以外で保存リストから第２のリンクを取り出す（ステップＳ１４６）。保存リストにリンクが、例えば、番号iがi=１,２,...,nのようについていた場合、第１のリンクはi=１,２,...,n-１の順に取り出す。第２のリンクは、例えば、第２のリンクの番号をjとすると、j=i+１,i+２,...,nのように取り出せばよい。そして、第１のリンクと第２のリンクを共に経路に含むＴＤＭ伝送路の区間の数を数える（ステップＳ１４７）。
【００９８】
ＴＤＭ伝送路の区間とは、例えば、図１２で、N１からN２などを指し、N１からN２までのＴＤＭ伝送路が何本あっても、１区間として数える。例えばN１-N２リンクを通るＴＤＭ伝送路の区間の数は、N１からN２、N１からN３、N１からN５の３つとなる。ただし、カウントする対象は実際にその区間に１本以上のＴＤＭ伝送路が設定されているもののみである。例えば、図１５でN３からN５やN３からN７などはＴＤＭ伝送路の本数が０であるため、カウントの対象としない。そして、カウントした区間数をTc１２に入れる。そしてTc０１２と比較し（ステップＳ１４８）、Tc１２のほうが小さい場合は、Lindx１に第１のリンクを、Lindx２に第２のリンクを入れ、Tc０１２=Tc１２とする（ステップＳ１４９）。ステップＳ１５０で、第２のリンクの選択が終了したか、ステップＳ１５１で、第１のリンクの選択が終了したかを判断し、終了していない場合には、それぞれ、ステップＳ１４５、ステップＳ１４６に戻って処理を繰り返す。これを繰り返していくと、選択した２つのリンクを通るＴＤＭ伝送路の区間の数が最も少ないリンクの組合せがLindx１とLindx２から得られる。得られたLindx１に入っているリンクが第１のリンクで、Lindx２に入っているリンクが第２のリンクである。それ以外の部分の動作は第１の構成例と同じである。
【００９９】
本実施形態の第８の構成例では、第１のリンクおよび第２のリンクを選択する際に、リンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクの中で、２つのリンクの両方を通るＴＤＭ伝送路の始終点対の数が最も少なくなるような２つのリンクを第１のリンクおよび第２のリンクとして選択する。これにより、より容量の大きいＴＤＭ伝送路を使う箇所のできるだけ少ない設計結果を得ることができる。
【０１００】
できるだけ確実に長いＴＤＭ伝送路に、より容量の大きいＴＤＭ伝送路が適用されるように、適切なリンクを選択することで、より確実に少ない繰り返し回数で、より容量の大きいＴＤＭ伝送路をできるだけ少なく使用した設計結果を得ることができるようになる。
【０１０１】
第９の構成例では、第１のリンクと第２のリンクを選択する部分が第１の構成例と異なる。第９の構成例に対応する第１のリンクおよび第２のリンクを選択する部分のフローの例を図３５に示す。
図３５において、図３４と同じステップには、同じステップ番号を付して、それらの説明を省略する。
【０１０２】
第８の構成例との違いは、第８の構成例では選択した２つのリンクを通るＴＤＭ伝送路の区間の数を数えたのに対し、第９の構成例では選択した２つのリンクを通るＴＤＭ伝送路の本数を数えている点である。例えば、図１２の場合のＴＤＭ伝送路の区間の数は全て入れても９個であるが、図１５の場合のＴＤＭ伝送路は全部で２８本ある。第８の構成例のほうが処理時間は短くて済むが、実際に選択した２つのリンクを通るＴＤＭ伝送路が少ないかどうかは正確ではなく、概算的な見積もりとなる。一方、第９の構成例では、処理時間はかかるものの、両方のリンクを通るＴＤＭ伝送路の数の小さいものが確実に得られる。
【０１０３】
図３５において、ステップＳ１５５で、Lindx１、Lindx２、Tnc０１２、Tnc１２を初期化する。そして、ステップＳ１４５、Ｓ１４６で、第１、第２のリンクを選択した後、第１のリンクと第２のリンクを共通に通るＴＤＭ伝送路の本数をカウントし、Tnc１２に入れる（ステップＳ１５６）。Tnc１２とTnc０１２とを比較し（ステップＳ１５７）、Tnc１２が小さい場合は、Lindx１に第１のリンクを、Lindx２に第２のリンクを入れ、Tnc０１２=Tnc１２とする（ステップＳ１５８）。それ以外の部分の動作は第１の構成例と同じである。
【０１０４】
本実施形態の第９の構成例では、第１のリンクおよび第２のリンクを選択する際に、リンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクの中で、２つのリンクの両方を通るＴＤＭ伝送路の合計本数が最も少なくなるような２つのリンクを第１のリンクおよび第２のリンクとして選択する。これにより、より容量の大きいＴＤＭ伝送路を使う箇所のできるだけ少ない設計結果を得ることができる。
【０１０５】
できるだけ確実に長いＴＤＭ伝送路に、より容量の大きいＴＤＭ伝送路が適用されるように、適切なリンクを選択することで、より確実に少ない繰り返し回数で、より容量の大きいＴＤＭ伝送路をできるだけ少なく使用した設計結果を得ることができるようになる。
【０１０６】
第１０の構成例では、第２のリンクを選択する部分が第１の構成例と異なる。第１０の構成例に対応する第２のリンクを選択する部分のフローの例を図３６に示す。
第１の構成例との違いは、第２のリンクとしてリンクを通るＴＤＭ伝送路の本数がリンクで使える波長数から超過している量の最も大きいリンクを第２のリンクとして選択する点である。
【０１０７】
図３６のフローでは、ステップＳ１５９で、変数Lov、L０ov、Lindx２を初期化する。そして、保存リストから第１のリンク以外のリンクを順に取り出し（ステップＳ１６０）、超過波長数をLovに入れる（ステップＳ１６１）。超過波長数は、ここではリンクを通るＴＤＭ伝送路の本数とリンクで使える波長数の差を指している。そして、LovとL０ovを比較し（ステップＳ１６２）、Lovのほうが大きい場合はLindx２を更新し、L０ov=Lovとする（ステップＳ１６３）。ステップＳ１６４で、リンクの選択が終了したか否かを判断し、終了していない場合には、ステップＳ１６０に戻って、処理を繰り返す。これを繰り返すと、保存リストの中で最も超過波長数の多いリンクがLindx２に残る。このLindx２に入っているリンクを第２のリンクとして選択する。それ以外の部分の動作は第１の構成例と同じである。
【０１０８】
本実施形態の第１０の構成例では、第２のリンクを選択する際に、選択したＴＤＭ伝送路の経路上にあり、かつ、リンクで使える波長数よりもＴＤＭ伝送路の本数の多いリンクで、かつ、第１のリンクを除いてＴＤＭ伝送路の本数がリンクで使える波長数を超過した量の最も多いものを第２のリンクとして選択する。これにより、より容量の大きいＴＤＭ伝送路を使う箇所のできるだけ少ない設計結果を得ることができる。
【０１０９】
ＴＤＭ伝送路に、ＴＤＭ伝送路の本数がリンクで使える波長数よりも多いリンクで、かつ、その超過量が多いリンクが多く含まれる場合でも、より確実に少ない繰り返し回数で、より容量の大きいＴＤＭ伝送路をできるだけ少なく使用した設計結果を得ることができるようになる。
【０１１０】
図３７に第１１の構成例に対応するフローを示す。
図３７において、図７と同じステップには、同じステップ番号を付し、これらの説明を省略する。
【０１１１】
図７との違いは、入力時に図７の入力のほかに、ＴＤＭ伝送路の区間ごと・容量ごとのコストを入力している点（ステップＳ１７０）と、波長数超過リンクリストを作成する前に高コストＴＤＭ伝送路の除外を行っている点（ステップＳ１７１）である。ＴＤＭ伝送路の区間ごと・容量ごとのコストの例を図３８と図３９に示す。図３８は、例えば、容量８のＴＤＭ伝送路に使うトランスポンダの値段を１としたときの容量３２のＴＤＭ伝送路に使うトランスポンダの価格を示す。例えば、番号１のＴＤＭ伝送路の区間の場合、容量３２のトランスポンダは容量８のトランスポンダの４.１倍の価格になっていることを示している。また、番号６のＴＤＭ伝送路の区間の場合は、容量が３２のＴＤＭ伝送路だと、途中に再生中継器が１つ必要になる場合を示しており、ここでは再生中継器はトランスポンダと同じ価格と仮定し、２倍の８.２にしている。ここでは、再生中継器を例としているが、トランスポンダだけでは伝送できず、途中に機器が必要になる場合は、それらのコストを入れることもできる。図３９は伝送に必要な再生中継器の数をそのままコストとして入れている例である。番号６の欄の容量３２のところが１になっているのは、途中に再生中継器が１つ必要になることを示している。
【０１１２】
次に、高コストＴＤＭ伝送路を除外するフローを図４０に示す。図４０では、ＴＤＭ伝送路を区間毎に選択し（ステップＳ１７５）、容量の大きいものと小さいもののコストの比をとった結果（ステップＳ１７６）がある閾値を越えていたら（ステップＳ１７７）、そのＴＤＭ伝送路の区間のＴＤＭ伝送路を後でＴＤＭ伝送路を選択する際の候補から除外する（ステップＳ１７８）。ステップＳ１７９は、ＴＤＭ伝送路の区間を全て選択したか判断し、選択していない場合には、処理を繰り返すための判断処理である。
【０１１３】
容量の大きいものと小さいものは、例えば、容量８のＴＤＭ伝送路と容量３２のＴＤＭ伝送路がある場合は、容量８のほうが容量の小さいＴＤＭ伝送路、容量３２のほうが容量の大きいＴＤＭ伝送路となる。最初の設計で容量の小さいＴＤＭ伝送路を使ったためにＴＤＭ伝送路の本数がＷＤＭシステムで利用可能な波長数を超えてしまう場合を想定している。したがって、実質的には容量の小さいＴＤＭ伝送路は、最初の設計で選択されたＴＤＭ伝送路で、容量の大きいＴＤＭ伝送路はそれよりも大きい容量をもつＴＤＭ伝送路全てを指す。
【０１１４】
閾値は、例えば４.１にすることができ、この場合は再生中継器などが必要になるためにコストの値が４.１を越えるＴＤＭ伝送路を除外することになる。ＴＤＭ伝送路を選択する際の候補から除外する方法は、ＴＤＭ伝送路のリストから該当するＴＤＭ伝送路の情報を削除する方法がある。あるいは、図４１のように、ＴＤＭ伝送路のリストに選択可否の欄を追加してそこに除外の場合はfalse、それ以外の場合はtrueを記入しておき、ＴＤＭ伝送路を選択する際に欄の中が例えばtrueの場合は選択し、falseの場合にはその伝送路は選択しない、というように処理をすることもできる。また、図３９のように、容量の小さいほうのコストが０の場合は除算ができないため、容量の大きい方のコストから容量の小さいほうのコストを引いた値を閾値と比較し、判定することができる。この場合の閾値は、例えば０で、０より大きい、すなわち再生中継器が１つ以上必要になる場合は選択しない、とすることができる。それ以外の部分の動作は第１の構成例と同じである。
【０１１５】
本実施形態の第１１の構成例では、ネットワークの情報を入力する際に、ＴＤＭ伝送路の速度ごとのコスト情報をＴＤＭ伝送路の区間ごとに入力する。そして、同一のＴＤＭ伝送路の区間で、低速の伝送路のコストと高速の伝送路のコストの比率が所定の値を超える場合は、ＴＤＭ伝送路を選択する前に、そのＴＤＭ伝送路の区間のＴＤＭ伝送路を除外するようにする。これにより、高速の伝送路を選択することでコストが大きく上がるようなＴＤＭ伝送路を選択するのを防止することができる。
【０１１６】
再設計の際に、より高速の伝送路を選択するとコストが大きく上がってしまうようなＴＤＭ伝送路が選択されないようにすることで、コストが不必要に大きく上がることを防止することができる。
【０１１７】
第１１の構成例では、ＴＤＭ伝送路を選択する部分で、例えば、容量が８のＴＤＭ伝送路の場合は、始点から終点まで光のまま伝送できるが、容量３２の場合は始点から終点までの間に再生中継器が必要になる、という場合がある。そのようなＴＤＭ伝送路を選択すると、容量３２のＴＤＭ伝送路に変えたときのコストが大きく増えてしまう。そこで第１１の構成例では、第１の構成例の構成に、このように容量の大きいＴＤＭ伝送路にするとコストが大きく増加してしまうようなＴＤＭ伝送路を選択肢から除外する処理を追加している。
【０１１８】
図４２は、本実施形態のネットワーク設計装置の機能ブロック図である。
各機能は、ネットワーク設計装置のメモリに展開される。設計情報入力部１０では、図７のトポロジ情報、デマンド情報、ＴＤＭ伝送路情報等を入力する。収容設計問題処理部１１１では、収容設計問題を解く処理を行う。詰め込み問題処理部１２は、収容設計問題を解いた結果から、各デマンドをＴＤＭ伝送路に割り当てる処理を行う。波長数制限確認部１３は、リンクごとの波長数の制限を確認する。制約条件生成部１４は、収容設計問題や詰め込み問題における制約条件を生成したり、図７のステップＳ２４〜ステップＳ３１の処理を行う。結果出力部１５は、設計結果を出力する。テーブル格納部１６は、上記の各構成例の説明で示した各テーブルを格納する。
【０１１９】
図４３は、本実施形態の処理をプログラムで実現する場合の、プログラムを実行するコンピュータのハードウェア環境図である。
ＣＰＵ２１は、バス２０によって、ＲＯＭ２２、ＲＡＭ２３、ネットワークインタフェース２４、記憶装置２７、媒体ドライブ２８、入出力装置３０と接続される。
【０１２０】
ＲＯＭ２２は、ＢＩＯＳなどの、コンピュータを機能させるための基本プログラムを格納し、ＣＰＵ２１が実行することにより、コンピュータの基本機能を実現する。
記憶装置２７は、ハードディスクなどの外部記憶装置で、本実施形態の処理を行うプログラムを格納する。記憶装置２７に格納されたプログラムは、ＲＡＭ２３に展開されて、ＣＰＵ２１により実行される。
【０１２１】
本実施形態の処理を行うプログラムは、可搬記録媒体２９に格納されていてもよく、媒体ドライブ２８を使って可搬記録媒体２９からプログラムを読み込み、ＲＡＭ２３に展開することによって、ＣＰＵ２１が実行することができる。
【０１２２】
可搬記録媒体２９は、ＣＤ−ＲＯＭ、ＤＶＤ、ＩＣメモリ、Ｂｌｕ−ｒａｙ、フレキシブルディスクなどの記録媒体である。
入出力装置３０は、ディスプレイ、プリンタ、キーボード、マウスなどで、ユーザからの入力を行ったり、ユーザへの出力の提示を行う。
【０１２３】
ネットワークインタフェース２４は、ネットワーク２５を介して、情報提供者が有するデータベース２６等にアクセスする。本実施形態の処理を行うプログラムは、データベース２６に格納されていてもよく、テータベース２６からプログラムを記憶装置２７や可搬記録媒体２９にダウンロードして、実行可能とすることができる。また、データベース２６からプログラムをダウンロードせず、データベース２６から直接ネットワーク２５を介して実行するようにしてもよい。
【符号の説明】
【０１２４】
１０      設計情報入力部
１１      収容設計問題処理部
１２      詰め込み問題処理部
１３      波長数制限確認部
１４      制約条件生成部
１５      結果出力部
１６      テーブル格納部
２０      バス
２１      ＣＰＵ
２２      ＲＯＭ
２３      ＲＡＭ
２４      ネットワークインタフェース
２５      ネットワーク
２６      データベース
２７      記憶装置
２８      媒体ドライブ
２９      可搬記録媒体
３０      入出力装置
【図１】
0005794170.tif 000006
【図２】
0005794170.tif 000007
【図３】
0005794170.tif 000008
【図４】
0005794170.tif 000009
【図５】
0005794170.tif 000010
【図６】
0005794170.tif 000011
【図７】
0005794170.tif 000012
【図８】
0005794170.tif 000013
【図９】
0005794170.tif 000014
【図１０】
0005794170.tif 000015
【図１１】
0005794170.tif 000016
【図１２】
0005794170.tif 000017
【図１３】
0005794170.tif 000018
【図１４】
0005794170.tif 000019
【図１５】
0005794170.tif 000020
【図１６】
0005794170.tif 000021
【図１７】
0005794170.tif 000022
【図１８】
0005794170.tif 000023
【図１９】
0005794170.tif 000024
【図２０】
0005794170.tif 000025
【図２１】
0005794170.tif 000026
【図２２】
0005794170.tif 000027
【図２３】
0005794170.tif 000028
【図２４】
0005794170.tif 000029
【図２５】
0005794170.tif 000030
【図２６】
0005794170.tif 000031
【図２７】
0005794170.tif 000032
【図２８】
0005794170.tif 000033
【図２９】
0005794170.tif 000034
【図３０】
0005794170.tif 000035
【図３１】
0005794170.tif 000036
【図３２】
0005794170.tif 000037
【図３３】
0005794170.tif 000038
【図３４】
0005794170.tif 000039
【図３５】
0005794170.tif 000040
【図３６】
0005794170.tif 000041
【図３７】
0005794170.tif 000042
【図３８】
0005794170.tif 000043
【図３９】
0005794170.tif 000044
【図４０】
0005794170.tif 000045
【図４１】
0005794170.tif 000046
【図４２】
0005794170.tif 000047
【図４３】
0005794170.tif 000048