(57)【特許請求の範囲】
【請求項１】
通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶手段と、
この設計情報記憶手段に記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計手段と、
この経路候補設計手段によって設計されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出手段と、
この配置コスト総和算出手段が順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶手段と、
前記配置コスト総和算出手段がそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を前記最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カット手段
とを具備することを特徴とする通信網設計装置。
【請求項２】
通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶手段と、
この設計情報記憶手段に記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計手段と、
この経路候補設計手段によって設計された前記予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置する横方向再配置手段と、
この横方向再配置手段によって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出手段と、
この配置コスト総和算出手段が順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶手段と、
前記配置コスト総和算出手段がそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を前記最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カット手段
とを具備することを特徴とする通信網設計装置。
【請求項３】
通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶手段と、
この設計情報記憶手段に記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計手段と、
この経路候補設計手段によって設計された前記予測デマンドを配置コストの小さい順に再配置する縦方向再配置手段と、
この縦方向再配置手段によって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまで入力装置の経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出手段と、
この配置コスト総和算出手段が順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶手段と、
前記配置コスト総和算出手段がそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を前記最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カット手段
とを具備することを特徴とする通信網設計装置。
【請求項４】
通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶手段と、
この設計情報記憶手段に記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計手段と、
この経路候補設計手段によって設計された前記予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置する横方向再配置手段と、
前記経路候補設計手段によって設計された各経路のそれぞれの予測デマンドを配置コストの小さい順に再配置する縦方向再配置手段と、
これら横方向再配置手段および縦方向再配置手段によって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出手段と、
この配置コスト総和算出手段が順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶手段と、
前記配置コスト総和算出手段がそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を前記最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カット手段
とを具備することを特徴とする通信網設計装置。
【請求項５】
前記算出カット手段で算出をカットして次の経路についての配置コストの総和を求める処理に移行するとき、対象となる各経路候補を配置コストの小さい順に再配置する経路候補選択時再配置手段を具備することを特徴とする請求項１または請求項３記載の通信網設計装置。
【請求項６】
通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶ステップと、
この設計情報記憶ステップで記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計ステップと、
この経路候補設計ステップによって設計されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出ステップと、
この配置コスト総和算出ステップで順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶ステップと、
前記配置コスト総和算出ステップでそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を前記最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カットステップ
とを具備することを特徴とする通信網設計方法。
【請求項７】
通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶ステップと、
この設計情報記憶ステップで記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計ステップと、
この経路候補設計ステップによって設計された前記予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置する横方向再配置ステップと、
この横方向再配置ステップによって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出ステップと、
この配置コスト総和算出ステップで順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶ステップと、
前記配置コスト総和算出ステップでそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を前記最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カットステップ
とを具備することを特徴とする通信網設計方法。
【請求項８】
通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶ステップと、
この設計情報記憶ステップで記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計ステップと、
この経路候補設計ステップによって設計された前記予測デマンドを配置コストの小さい順に再配置する縦方向再配置ステップと、
この縦方向再配置ステップによって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまで入力装置の経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出ステップと、
この配置コスト総和算出ステップで順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶ステップと、
前記配置コスト総和算出ステップでそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を前記最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カットステップ
とを具備することを特徴とする通信網設計方法。
【請求項９】
通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶ステップと、
この設計情報記憶ステップで記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計ステップと、
この経路候補設計ステップによって設計された前記予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置する横方向再配置ステップと、
前記経路候補設計ステップによって設計された各経路のそれぞれの予測デマンドを配置コストの小さい順に再配置する縦方向再配置ステップと、
これら横方向再配置ステップおよび縦方向再配置ステップによって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出ステップと、
この配置コスト総和算出ステップで順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶ステップと、
前記配置コスト総和算出ステップでそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を前記最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カットステップ
とを具備することを特徴とする通信網設計方法。
【請求項１０】
前記算出カットステップで算出をカットして次の経路についての配置コストの総和を求める処理に移行するとき、対象となる各経路候補を配置コストの小さい順に再配置する経路候補選択時再配置ステップを具備することを特徴とする請求項６または請求項８記載の通信網設計方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は通信網を設計するための通信網設計装置および通信網設計方法に係わり、特に多重化された光通信網のような新規のあるいは新規に追加する通信網を経済的に設計するために好適な通信網設計装置および通信網設計方法に関する。
【０００２】
【従来の技術】
新たに通信網を設計したり、既存の通信網に新たな通信網を追加するような場合には、その通信網の利用される実態を考慮して、経済的な通信網を作成することが必要である。
【０００３】
図２１は、簡略化された例として、通信網の設計の対象となる４つのノードを示したものである。ある設計対象地域１００に第１〜第４の合計４つのノード１０１〜１０４が配置される。
【０００４】
図２２は、２組のノード間で通信が行われる場合の通信網の設計例を示したものである。第１のノード１０１と第２のノード１０２の間、および第３のノード１０３と第４のノード１０４の間でのみ通信が行われるものとする。この場合、単位時間当たりの通信量に応じた太さの通信路を通信が行われるノード間に接続すると、最もコストの低い通信網を実現することができる。
【０００５】
この例では第１のノード１０１と第２のノード１０２の間の通信量が低いものとし、この間に１番細い通信路１０６を接続する。第３のノード１０３と第４のノード１０４の間は通信量が普通であるとし、中程度の通信路１０７を接続する。コストについての単純な例を挙げる。一番細い通信路１０６を１万円とし、中程度の通信路１０７を３万円とすると、このように通信量に合わせた通信路を設計することで、この例では合計４万円のコストで通信網が成立する。
【０００６】
図２３はこれら４つのノード間を最も不経済に通信路を接続した例を示したものである。すべてのノード１０１〜１０４がそれぞれ直接接続されるように６通りの通信路を配置している。これらにコストの中程度の通信路１０７を使用する設計を行ったとする。それぞれの距離によるコストの違いがないとした単純計算の場合に、１つの通信路１０７当たり３万円で、その６倍のコストがかかるので、合計で１８万円となる。このように通信の予定のない第１のノード１０１と第４のノード１０４の間や第２のノード１０２と第３のノード１０３間等に通信路を設けることは不経済である。また、それぞれのノード１０１〜１０４の間の通信量に合った太さの通信路を設定しないと、通信ケーブル、光ファイバ等の線路およびノード１０１〜１０４の設備が必要以上に高価なものとなり、これも経済性に反する結果を招くことになる。
【０００７】
図２４は、通信網設計の設計の他の態様を表わしたものである。この例では、第１のノード１０１と第２のノード１０２の間である系統の通信が行われ、第２のノード１０２と第４のノード１０４の間で他の系統の通信が行われるものとする。第２のノード１０２と第４のノード１０４を直接結ぶ通信路を配置することも可能であるが、ここでは第１のノード１０１を経由した設計例が示されており、このために、第１のノード１０１と第２のノード１０２の間には２種類の通信路１０６、１０７が配置されている。この例では信号が多重化されていない場合を示しているが、多重化されると第１のノード１０１と第２のノード１０２の間をたとえばＷＤＭ（Wavelength Division Multiplexing：波長分割多重伝送方式）によって伝送することができる。このようにどのような種類の通信路を配置するかによってコストの計算が異なることになる。更に、以上の説明では二重化された通信網について触れなかったが、比較的重要な通信網では現用経路と予備経路の２系等の通信網が設定される場合があるので、これを考慮して通信網の設計を行う必要がある。
【０００８】
ところで通信網設計装置あるいは通信網設計方法については各種の提案が行われている。たとえば特開平７−２５０３５６号公報に記載された技術では、光伝送路に収容される光パスの収容数が最小となる経路を現用の経路として設定するようにしている。そして、各伝送路に１箇所ずつ故障が発生したものと想定した場合の、現用経路に対する迂回経路の収容数が最小となる迂回経路を予備経路として設定するようにしている。そして、現用および予備の経路を構成するのに必要とする波長数が少なくなるように経路を再度設定するようにしている。
【０００９】
また、特開平７−２０２８４４号公報に記載された技術では、その第１のステップで、設定すべきすべての経路について２つのノード間では利用波長が全長にわたってそれぞれ同一となるように現用および予備の経路を作成している。第２のステップでは、第１のステップで作成された現用および予備の経路を、必要とする波長数が少なくなるように再度作成するようにしている。第２のステップの処理は規定回数繰り返される。これにより、光パス網における経路探索と波長の割り当てを同時に行うことができると共に、波長数を少なくした光パス網が構成される。
【００１０】
【発明が解決しようとする課題】
このうち前者の特開平７−２５０３５６号公報に記載された技術では、経路収容数が最小となる経路設定を行っている。このため、パスが１箇所に偏ることなく分散して収容されるような設計が行われることになる。したがって、既存の通信網を利用して新たなパスを収容しようとするような場合には、全体としての経路の数が削減されるので、効率的な通信網を実現することができる。しかしながら、新規に設備を投入して全く新しいネットワークを構築しようとするような場合、あるいは既存の設備はそのままにして新しい需要に対してネットワークを追加的に構築するような場合には、この技術を使用することができない。パスを分散するので、投入する設備が分散して配備されることになり、より多くの設備が必要となる（図２３参照）からである。
【００１１】
一方、後者の特開平７−２０２８４４号公報に開示された技術では、経路をランダムに組み合わせるようにしている。したがって、繰り返しを行う回数をかなりの数に設定しなければ最適に近い解を求めることができない。このため、設計に要する時間が長時間化するという問題がある。
【００１２】
また、近時、光通信を初めとして信号の多重化技術が進展しており、多重化により得られたチャネルの効率的な活用も図られるべきである。したがって、これら２つの先行する技術に示されたような波長数あるいはチャネル数の低減の考え方も重要であるが、特に新規の通信網あるいは新規に追加する通信網を設計する際には波長やチャネルを有効に活用しながら通信網全体のコストの低減を考慮すべきである。
【００１３】
そこで本発明の目的は、ノード間の通信路を必要に応じて多重化しながら、新たな通信網を経済的に作成することのできる通信網設計装置および通信網設計方法を提供することにある。
【００１４】
【課題を解決するための手段】
請求項１記載の発明では、（イ）通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶手段と、（ロ）この設計情報記憶手段に記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計手段と、（ハ）この経路候補設計手段によって設計されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出手段と、（ニ）この配置コスト総和算出手段が順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶手段と、（ホ）配置コスト総和算出手段がそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カット手段とを通信網設計装置に具備させる。
【００１５】
すなわち請求項１記載の発明では、設計情報記憶手段に、通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶するようにしている。そして、経路候補設計手段で設計情報記憶手段に記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行うようにしている。このようにして設計された各経路すなわち各要求コマンドに対して１つずつ経路候補を選択したことによるあらゆる組み合わせに対しては、配置コスト総和算出手段が経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めていくことになる。そして、出力候補記憶手段が配置コスト総和算出手段の順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶することにより、より経済的な経路が出現するとこれが出力候補として置き換えられていくことになる。ここで請求項１記載の発明は、算出カット手段を備えており、配置コスト総和算出手段がそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行するようにしている。すなわち、ある経路についての今まで行った経路候補の配置コストの積算値が現在の最小配置コストよりも大きくなっているときには、その経路の残りの経路候補についての配置コストを更に積算してもその最小配置コストよりも大きくなるのは明らかであり、その算出中の経路が最も経済的な経路として選択されることはないので、その算出処理をカットして次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行することで、処理の迅速化を図っている。
【００１６】
請求項２記載の発明では、（イ）通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶手段と、（ロ）この設計情報記憶手段に記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計手段と、（ハ）この経路候補設計手段によって設計された予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置する横方向再配置手段と、（ニ）この横方向再配置手段によって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出手段と、（ホ）この配置コスト総和算出手段が順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶手段と、（へ）配置コスト総和算出手段がそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カット手段とを通信網設計装置に具備させる。
【００１７】
すなわち請求項２記載の発明では、設計情報記憶手段に、通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶するようにしている。そして、経路候補設計手段で設計情報記憶手段に記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行うようにしている。このようにして設計された各経路すなわち各要求コマンドに対して１つずつ経路候補を選択したことによるあらゆる組み合わせに対しては、配置コスト総和算出手段が経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めていくことになる。そして、出力候補記憶手段が配置コスト総和算出手段の順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶することにより、より経済的な経路が出現するとこれが出力候補として置き換えられていくことになる。ここで請求項２記載の発明は、算出カット手段を備えており、配置コスト総和算出手段がそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行するようにしている。すなわち、ある経路についての今まで行った経路候補の配置コストの積算値が現在の最小配置コストよりも大きくなっているときには、その経路の残りの経路候補についての配置コストを更に積算してもその最小配置コストよりも大きくなるのは明らかであり、その算出中の経路が最も経済的な経路として選択されることはないので、その算出処理をカットして次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行することで、処理の迅速化を図っている。
【００１８】
更に請求項２記載の発明は、経路候補設計手段によって設計された予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置する横方向再配置手段を備えている。そして、配置コスト総和算出手段は横方向再配置手段によって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めることにしている。このように各予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置した後に、それぞれの経路についての配置コストの総和を求め、かつ算出カット手段で経路の途中でも積算の中止を行うようにしているので、比較的早期に最も経済的な経路が出力候補記憶手段に記憶される可能性が高くなる。このため、処理が迅速化されるだけでなく、通信網設計装置の処理時間に制限がある場合でも比較的経済的な経路を求めやすいという効果がある。
【００１９】
請求項３記載の発明では、（イ）通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶手段と、（ロ）この設計情報記憶手段に記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計手段と、（ハ）この経路候補設計手段によって設計された予測デマンドを配置コストの小さい順に再配置する縦方向再配置手段と、（ニ）この縦方向再配置手段によって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまで入力装置の経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出手段と、（ホ）この配置コスト総和算出手段が順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶手段と、（へ）配置コスト総和算出手段がそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カット手段とを通信網設計装置に具備させる。
【００２０】
すなわち請求項３記載の発明では、設計情報記憶手段に、通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶するようにしている。そして、経路候補設計手段で設計情報記憶手段に記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行うようにしている。このようにして設計された各経路すなわち各要求コマンドに対して１つずつ経路候補を選択したことによるあらゆる組み合わせに対しては、配置コスト総和算出手段が経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めていくことになる。そして、出力候補記憶手段が配置コスト総和算出手段の順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶することにより、より経済的な経路が出現するとこれが出力候補として置き換えられていくことになる。ここで請求項３記載の発明は、算出カット手段を備えており、配置コスト総和算出手段がそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行するようにしている。すなわち、ある経路についての今まで行った経路候補の配置コストの積算値が現在の最小配置コストよりも大きくなっているときには、その経路の残りの経路候補についての配置コストを更に積算してもその最小配置コストよりも大きくなるのは明らかであり、その算出中の経路が最も経済的な経路として選択されることはないので、その算出処理をカットして次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行することで、処理の迅速化を図っている。
【００２１】
更に請求項３記載の発明は、縦方向再配置手段が経路候補設計手段によって設計された予測デマンドを配置コストの小さい順に再配置するようにしている。そして、配置コスト総和算出手段は縦方向再配置手段によって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまで入力装置の経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めることにしている。このように各予測デマンドを配置コストの小さい順に再配置した後に、それぞれの経路についての配置コストの総和を求め、かつ算出カット手段で経路の途中でも積算の中止を行うようにしているので、比較的早期に最も経済的な経路が出力候補記憶手段に記憶される可能性が高くなる。このため、処理が迅速化されるだけでなく、通信網設計装置の処理時間に制限がある場合でも比較的経済的な経路を求めやすいという効果がある。
【００２２】
請求項４記載の発明では、（イ）通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶手段と、（ロ）この設計情報記憶手段に記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計手段と、（ハ）この経路候補設計手段によって設計された予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置する横方向再配置手段と、（ニ）経路候補設計手段によって設計された各経路のそれぞれの予測デマンドを配置コストの小さい順に再配置する縦方向再配置手段と、（ホ）これら横方向再配置手段および縦方向再配置手段によって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出手段と、（へ）この配置コスト総和算出手段が順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶手段と、（ト）配置コスト総和算出手段がそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カット手段とを通信網設計装置に具備させる。
【００２３】
すなわち請求項４記載の発明では、設計情報記憶手段に、通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶するようにしている。そして、経路候補設計手段で設計情報記憶手段に記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行うようにしている。このようにして設計された各経路すなわち各要求コマンドに対して１つずつ経路候補を選択したことによるあらゆる組み合わせに対しては、配置コスト総和算出手段が経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めていくことになる。そして、出力候補記憶手段が配置コスト総和算出手段の順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶することにより、より経済的な経路が出現するとこれが出力候補として置き換えられていくことになる。ここで請求項４記載の発明は、算出カット手段を備えており、配置コスト総和算出手段がそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行するようにしている。すなわち、ある経路についての今まで行った経路候補の配置コストの積算値が現在の最小配置コストよりも大きくなっているときには、その経路の残りの経路候補についての配置コストを更に積算してもその最小配置コストよりも大きくなるのは明らかであり、その算出中の経路が最も経済的な経路として選択されることはないので、その算出処理をカットして次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行することで、処理の迅速化を図っている。
【００２４】
更に請求項４記載の発明は、横方向再配置手段が経路候補設計手段によって設計された予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置するとともに、縦方向再配置手段が経路候補設計手段によって設計された予測デマンドを配置コストの小さい順に再配置するようにしている。そして、配置コスト総和算出手段は横方向再配置手段および縦方向再配置手段によって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまで入力装置の経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めることにしている。このように縦横両方向に配置コストの小さい順に再配置した後に、それぞれの経路についての配置コストの総和を求め、かつ算出カット手段で経路の途中でも積算の中止を行うようにしているので、比較的早期に最も経済的な経路が出力候補記憶手段に記憶される可能性が高くなる。このため、処理が迅速化されるだけでなく、通信網設計装置の処理時間に制限がある場合でも比較的経済的な経路を求めやすいという効果がある。
【００２５】
請求項５記載の発明では、請求項１または請求項３記載の通信網設計装置で、算出カット手段で算出をカットして次の経路についての配置コストの総和を求める処理に移行するとき、対象となる各経路候補を配置コストの小さい順に再配置する経路候補選択時再配置手段を具備することを特徴としている。
【００２６】
すなわち請求項５記載の発明では、横方向のソートが行われなかったものについて次の経路を選択するときに横方向で配置コストの小さい順に経路を選ぶことで、最小配置コストが低い可能性の高い経路から各経路候補の配置コストの総和を求めることにし、算出カット手段の効果と併せて処理の迅速化を図っている。
【００２７】
請求項６記載の発明では、（イ）通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶ステップと、（ロ）この設計情報記憶ステップで記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計ステップと、（ハ）この経路候補設計ステップによって設計されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出ステップと、（ニ）この配置コスト総和算出ステップで順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶ステップと、（ホ）配置コスト総和算出ステップでそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カットステップとを通信網設計方法に具備させる。
【００２８】
すなわち請求項６記載の発明では、設計情報記憶ステップで、通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶するようにしている。そして、経路候補設計ステップで設計情報記憶ステップにおいて記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行うようにしている。このようにして設計された各経路すなわち各要求コマンドに対して１つずつ経路候補を選択したことによるあらゆる組み合わせに対しては、配置コスト総和算出ステップで経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めていくことになる。そして、出力候補記憶ステップにおいて配置コスト総和算出ステップで順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶することにより、より経済的な経路が出現するとこれが出力候補として置き換えられていくことになる。ここで請求項６記載の発明は、算出カットステップを備えており、配置コスト総和算出ステップでそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行するようにしている。すなわち、ある経路についての今まで行った経路候補の配置コストの積算値が現在の最小配置コストよりも大きくなっているときには、その経路の残りの経路候補についての配置コストを更に積算してもその最小配置コストよりも大きくなるのは明らかであり、その算出中の経路が最も経済的な経路として選択されることはないので、その算出処理をカットして次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行することで、処理の迅速化を図っている。
【００２９】
請求項７記載の発明では、（イ）通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶ステップと、（ロ）この設計情報記憶ステップで記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計ステップと、（ハ）この経路候補設計ステップによって設計された予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置する横方向再配置ステップと、（ニ）この横方向再配置ステップによって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出ステップと、（ホ）この配置コスト総和算出ステップで順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶ステップと、（へ）配置コスト総和算出ステップでそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カットステップとを通信網設計方法に具備させる。
【００３０】
すなわち請求項７記載の発明では、設計情報記憶ステップで、通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶するようにしている。そして、経路候補設計ステップで設計情報記憶ステップにおいて記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行うようにしている。このようにして設計された各経路すなわち各要求コマンドに対して１つずつ経路候補を選択したことによるあらゆる組み合わせに対しては、配置コスト総和算出ステップで経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めていくことになる。そして、出力候補記憶ステップにおいて配置コスト総和算出ステップで順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶することにより、より経済的な経路が出現するとこれが出力候補として置き換えられていくことになる。ここで請求項７記載の発明は、算出カットステップを備えており、配置コスト総和算出ステップでそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行するようにしている。すなわち、ある経路についての今まで行った経路候補の配置コストの積算値が現在の最小配置コストよりも大きくなっているときには、その経路の残りの経路候補についての配置コストを更に積算してもその最小配置コストよりも大きくなるのは明らかであり、その算出中の経路が最も経済的な経路として選択されることはないので、その算出処理をカットして次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行することで、処理の迅速化を図っている。
【００３１】
更に請求項７記載の発明は、経路候補設計ステップによって設計された予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置する横方向再配置ステップを備えている。そして、配置コスト総和算出ステップでは横方向再配置ステップによって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めることにしている。このように各予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置した後に、それぞれの経路についての配置コストの総和を求め、かつ算出カットステップで経路の途中でも積算の中止を行うようにしているので、比較的早期に最も経済的な経路が出力候補記憶ステップで記憶される可能性が高くなる。このため、処理が迅速化されるだけでなく、通信網設計装置の処理時間に制限がある場合でも比較的経済的な経路を求めやすいという効果がある。
【００３２】
請求項８記載の発明では、（イ）通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶ステップと、（ロ）この設計情報記憶ステップで記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計ステップと、（ハ）この経路候補設計ステップによって設計された予測デマンドを配置コストの小さい順に再配置する縦方向再配置ステップと、（ニ）この縦方向再配置ステップによって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまで入力装置の経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出ステップと、（ホ）この配置コスト総和算出ステップで順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶ステップと、（へ）配置コスト総和算出ステップでそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カットステップとを通信網設計方法に具備させる。
【００３３】
すなわち請求項８記載の発明では、設計情報記憶ステップで、通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶するようにしている。そして、経路候補設計ステップで設計情報記憶ステップにおいて記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行うようにしている。このようにして設計された各経路すなわち各要求コマンドに対して１つずつ経路候補を選択したことによるあらゆる組み合わせに対しては、配置コスト総和算出ステップで経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めていくことになる。そして、出力候補記憶ステップにおいて配置コスト総和算出ステップで順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶することにより、より経済的な経路が出現するとこれが出力候補として置き換えられていくことになる。ここで請求項８記載の発明は、算出カットステップを備えており、配置コスト総和算出ステップでそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行するようにしている。すなわち、ある経路についての今まで行った経路候補の配置コストの積算値が現在の最小配置コストよりも大きくなっているときには、その経路の残りの経路候補についての配置コストを更に積算してもその最小配置コストよりも大きくなるのは明らかであり、その算出中の経路が最も経済的な経路として選択されることはないので、その算出処理をカットして次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行することで、処理の迅速化を図っている。
【００３４】
更に請求項８記載の発明は、縦方向再配置ステップにおいて、経路候補設計ステップによって設計された予測デマンドを配置コストの小さい順に再配置するようにしている。そして、配置コスト総和算出ステップでは縦方向再配置ステップによって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまで入力装置の経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めることにしている。このように各予測デマンドを配置コストの小さい順に再配置した後に、それぞれの経路についての配置コストの総和を求め、かつ算出カットステップで経路の途中でも積算の中止を行うようにしているので、比較的早期に最も経済的な経路が出力候補記憶ステップで記憶される可能性が高くなる。このため、処理が迅速化されるだけでなく、通信網設計装置の処理時間に制限がある場合でも比較的経済的な経路を求めやすいという効果がある。
【００３５】
請求項９記載の発明では、（イ）通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶する設計情報記憶ステップと、（ロ）この設計情報記憶ステップで記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行う経路候補設計ステップと、（ハ）この経路候補設計ステップによって設計された予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置する横方向再配置ステップと、（ニ）経路候補設計ステップによって設計された各経路のそれぞれの予測デマンドを配置コストの小さい順に再配置する縦方向再配置ステップと、（ホ）これら横方向再配置ステップおよび縦方向再配置ステップによって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求める配置コスト総和算出ステップと、（へ）この配置コスト総和算出ステップで順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶する出力候補記憶ステップと、（ト）配置コスト総和算出ステップでそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行する算出カットステップとを通信網設計方法に具備させる。
【００３６】
すなわち請求項９記載の発明では、設計情報記憶ステップで、通信網を構成する各ノード間の通信路の多重できる最大数としての最大多重数と各ノード間に通信路を設ける費用としての配置コストとを設計情報として記憶するようにしている。そして、経路候補設計ステップで設計情報記憶ステップにおいて記憶された設計情報を基にして、ノード間の通信路の設定要求としてのそれぞれの予測デマンドに対して採りうる経路候補を選択することで各経路の設計を行うようにしている。このようにして設計された各経路すなわち各要求コマンドに対して１つずつ経路候補を選択したことによるあらゆる組み合わせに対しては、配置コスト総和算出ステップで経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めていくことになる。そして、出力候補記憶ステップにおいて配置コスト総和算出ステップで順次求める各経路候補の配置コストの総和について過去に求めた値よりも小さな値が出現したときその値を最小配置コストとして、その最小配置コストとそのときの経路候補を現時点で採りうる通信網の最も経済的な配置コストおよびその経路として記憶することにより、より経済的な経路が出現するとこれが出力候補として置き換えられていくことになる。ここで請求項９記載の発明は、算出カットステップを備えており、配置コスト総和算出ステップでそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行するようにしている。すなわち、ある経路についての今まで行った経路候補の配置コストの積算値が現在の最小配置コストよりも大きくなっているときには、その経路の残りの経路候補についての配置コストを更に積算してもその最小配置コストよりも大きくなるのは明らかであり、その算出中の経路が最も経済的な経路として選択されることはないので、その算出処理をカットして次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行することで、処理の迅速化を図っている。
【００３７】
更に請求項９記載の発明は、横方向再配置ステップにおいて経路候補設計ステップによって設計された予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置するとともに、縦方向再配置ステップで経路候補設計ステップによって設計された予測デマンドを配置コストの小さい順に再配置するようにしている。そして、配置コスト総和算出ステップでは横方向再配置ステップおよび縦方向再配置ステップによって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまで入力装置の経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めることにしている。このように縦横両方向に配置コストの小さい順に再配置した後に、それぞれの経路についての配置コストの総和を求め、かつ算出カットステップで経路の途中でも積算の中止を行うようにしているので、比較的早期に最も経済的な経路が出力候補記憶ステップで記憶される可能性が高くなる。このため、処理が迅速化されるだけでなく、通信網設計装置の処理時間に制限がある場合でも比較的経済的な経路を求めやすいという効果がある。
【００３８】
請求項１０記載の発明では、請求項６または請求項８記載の通信網設計方法で、算出カットステップで算出をカットして次の経路についての配置コストの総和を求める処理に移行するとき、対象となる各経路候補を配置コストの小さい順に再配置する経路候補選択時再配置ステップを具備することを特徴としている。
【００３９】
すなわち請求項１０記載の発明では、横方向のソートが行われなかったものについて次の経路を選択するときに横方向で配置コストの小さい順に経路を選ぶことで、最小配置コストが低い可能性の高い経路から各経路候補の配置コストの総和を求めることにし、算出カットステップの効果と併せて処理の迅速化を図っている。
【００４０】
【発明の実施の形態】
【００４１】
【実施例】
以下実施例につき本発明を詳細に説明する。
【００４２】
図１は本発明の一実施例における通信網設計装置の構成の概要を表わしたものである。通信網設計装置２０１は、設計情報入力部２０２から入力される設計情報２０３を記憶する設計情報記憶部２０４を備えている。設計情報記憶部２０４から適宜読み出された設計情報２０５は経路候補設計部２０６に送られて経路候補の設計が行われる。経路候補設計部２０６から出力される経路候補データ２０７は第１のソート部２０８に送られて、ソーティングが行われる。ソーティング結果としての経路候補データ２０９は、経路候補記憶部２１０に送られて記憶される。経路候補記憶部２１０から読み出された経路候補データ２１１は、経路候補組み合わせ設計部２１２に送られる。経路候補組み合わせ設計部２１２はカット部２１４および経路候補リスト記憶部２１７と接続されている。経路候補組み合わせ設計部２１２から読み出された経路候補の組み合わせデータ２１５は経路候補リスト記憶部２１７に入力され記憶されるようになっている。カット部２１４は経路候補リスト記憶部２１７に記憶された経路候補リストデータ２１８を読み出して所定の条件で比較し、以後の経路の探索を必要に応じてカットする。カット部２１４によって処理された処理データ２１９は再び経路候補組み合わせ設計部２１２に入力される。経路候補組み合わせ設計部２１２は、カット部２１４および経路候補リスト記憶部２１７を使用した処理を繰り返し、その結果得られた設備配置データ２２１を設備配置出力部２２２に出力することになる。
【００４３】
このような構成の通信網設計装置２０１は、たとえばパーソナルコンピュータを使用して構成することができる。この場合、図示しないＣＰＵ（中央処理装置）が同じく図示しない制御手順格納部に格納された制御手順（制御プログラム）を実行して通信網の設計を行うことになる。設計情報記憶部２０４、経路候補記憶部２１０および経路候補リスト記憶部２１７は、制御手順格納部と共にハードディスク、光ディスク等の記憶媒体上の所定の記憶領域にそれぞれ割り当てることができる。また、設計情報入力部２０２は図示しないキーボード等の入力機器で構成されていてもよいし、ＬＡＮ（ローカルエリアネットワーク）等の通信手段（図示せず）等の入力手段を介して入力されるものであってもよい。設備配置出力部２２２は図示しないプリンタやディスプレイであってもよいし、前記した通信手段を介して設備配置の結果を出力するものであってもよい。通信網設計装置２０１内の各部については順次具体的に説明することにする。
【００４４】
図２は、この通信網設計装置で設計の対象とするノードの配置を示したものである。ここでは、簡略化されたノード配置としての、４つのノードＡ〜ノードＤを有するネットワークトポロジ（ネットワークの接続形態。以下単にトポロジと称する。）を構築しようとしている。ノードＡ〜ノードＤの間にはＷＤＭ（Wavelength Division Multiplexing：波長分割多重伝送方式）で通信路（リンク）を設定するが、まだどのノード間を接続するかは定まっていない。そこでこれらのリンクの部分は、未確定部分として破線で表わしている。
【００４５】
図３は、設計情報記憶部に記憶された設計情報のうちの配置コスト情報の一例を示したものである。配置コスト情報２０３Ａとは、各ノードＡ〜ノードＤにおける配置の可能性のあるリンクと、それぞれのリンクの最大多重度（最大チャネル数）およびそれぞれのリンクの配置コストを表わしている。配置コスト情報２０３Ａは、たとえば敷設する光ファイバの長さに応じて定まる光ファイバの敷設費用やノードに配備される中継等のための設備費用が合算されたものである。ここではそれぞれの配置コストを簡略化して “１”から“４”までの数値で表わしている。たとえばノードＡとノードＢの間に最大多重数が“４”のリンクを配置すると、そのための配置コストは“１”となり、これはノードＡとノードＣ間のリンクの配置コスト“３”の３分の１のコストとなっている。
【００４６】
図４は、設計情報記憶部に記憶された設計情報のうちの予測デマンドリストを示したものである。予測デマンドリスト２０３Ｂは、図２に示したトポロジ上で予測される各予測デマンドのリストを示したもので、これらの予測デマンドに対する経路候補の記入欄はまだ空欄となっている。この空欄部分に記入される経路候補は経路候補設計部２０６で設計されるようになっている。図１に示した第１のソート部２０８は経路候補設計部２０６で設計された各予測デマンドごとの経路候補をリンク配置コストの和の小さい順にソーティングする部分である。
【００４７】
図５は、第１のソート部におけるソーティングの様子を示したものである。図１に示す第１のソート部２０８には、同じく図１に示す経路候補設計部２０６で設計された各予測デマンドごとの経路候補が送られてくる。たとえばノードＡとノードＢの間の予測デマンド“Ａ−Ｂ”については、▲１▼ノードＡとノードＢを直接結ぶ経路“Ａ−Ｂ”と、▲２▼途中でノードＣを経由する経路“Ａ−Ｃ−Ｂ”と、▲３▼途中でノードＤを経由する経路“Ａ−Ｄ−Ｂ”と、▲４▼途中でノードＤとノードＣを順に経由する経路“Ａ−Ｄ−Ｃ−Ｂ”の４通りの経路候補が存在している（図２参照）。ノードＡとノードＣの間の予測デマンド“Ａ−Ｃ”については、▲１▼ノードＡとノードＣを直接結ぶ経路“Ａ−Ｃ”と、▲２▼途中でノードＢを経由する経路“Ａ−Ｂ−Ｃ”と、▲３▼途中でノードＤを経由する経路“Ａ−Ｄ−Ｃ”の３通りの経路候補が存在している。以下、他の予測デマンドについても同様に経路候補が設計され、これらのデータが経路候補データ２０７として送られてくる。
【００４８】
第１のソート部２０８は、経路候補設計部２０６で設計された各予測デマンドごとの経路候補を予測デマンドごとに配置コストの和の小さな順序に並べ変える。このとき、図３に示した配置コスト情報２０３Ａが使用される。
【００４９】
たとえばノードＡとノードＢの間の予測デマンド“Ａ−Ｂ”におけるノードＡとノードＢを直接結ぶ経路“Ａ−Ｂ”については、配置コスト情報２０３Ａにおける「Ａ−Ｂ間リンク」の配置コストが“１”なので、コストの和（図５で括弧内の数値として表示）は、“１”となる。また、経路“Ａ−Ｃ−Ｂ”については、「Ａ−Ｃ間リンク」の配置コストが“３”で「Ｂ−Ｃ間リンク」の配置コストが“２”なので、コストの和は“５”となる。更に、経路“Ａ−Ｄ−Ｂ”については、「Ａ−Ｄ間リンク」の配置コストが“３”で「Ｂ−Ｄ間リンク」の配置コストが“４”なので、コストの和は“７”となる。以下同様にして各経路候補について、それらのコストの和が求められ、予測デマンドごとに、これらの和が小さい順に並べられる。図５はこのようにして並べ替えが行われた後の状態を、括弧書きによるそれぞれのコストの和と共に示したものである。
【００５０】
図６は、経路候補設計部および第１のソート部のこのような制御の流れを表わしたものである。経路候補設計部２０６は予測デマンドを１つ選択する（ステップＳ２３１）。たとえば最初は予測デマンド“Ａ−Ｂ”を選択する。次に、選択したその予測デマンドについて経路候補設計を行う（ステップＳ２３２）。そして前記したようにこれらの和を小さい順に並べる（ステップＳ２３３）。次のステップ２３４ではすべての予測デマンドの処理が終了したかどうかをチェックして、終了していなければステップＳ２３１に戻って次の予測デマンドについての同様の処理を行う。このようにしてすべての予測デマンドについての処理が終了すれば（ステップＳ２３４：Ｙ）、一連の処理が終了する（エンド）。
【００５１】
図７は、第１のソート部による横方向のソーティングが行われた結果として経路候補記憶部に記憶された経路候補データを示したものである。図６で説明した処理によって得られた予測デマンドと経路候補の関係を示したリストは、経路候補データ２４１として経路候補記憶部２１０（図１）に記憶されることになる。
【００５２】
ところで、図８は本実施例の通信網設計装置における通信網の設計処理の大まかな流れを表わしたものである。まず図１の設計情報入力部２０２によって設計情報２０３が通信網設計装置２０１に入力される（ステップＳ３０１）。これを基にして通信網設計装置２０１は経路候補設計を行う（ステップＳ３０２）。本実施例では図１の経路候補記憶部２１０に記憶された経路候補データ２４１が経路候補設計の結果である。次のステップＳ３０３では経路候補組み合わせ設計を行う。これは次に説明するように図１に示した経路候補組み合わせ設計部２１２の行う処理である。経路候補組み合わせ設計の結果は、設備配置出力部２２２から出力される（ステップＳ３０４）ことになる。
【００５３】
図９は、図８のステップＳ３０３に相当する経路候補組み合わせ設計部の設計処理を具体的に表わしたものである。図１に示した経路候補組み合わせ設計部２１２では、まず利用する変数の初期値として、コスト上限値をとりあえず、制限なしを示す無限大“∞”に設定すると共に、経路候補リストを空欄の状態を表わす括弧記号“{  }”に設定する（ステップＳ３２１）。次のステップＳ３２２では、予測デマンドを１つ選択する。この最初の時点では経路候補リストが空である。したがって、予測デマンドの選択に特に制限はなく、本来はどの予測デマンドの選択も可能である。しかしながら、本実施例では第１のソート部２０８でソーティングした結果から図７に示す経路候補データ２４１の最上覧における予測デマンド“Ａ−Ｂ”を先ず最初に選択し、順に１つずつ下方向にこれを選択するものとする。
【００５４】
図１０は、予測デマンドと経路候補の関係の一部を経路候補リストとして表わしたものである。縦方向が図７に示した各予測デマンドを下層に向かって順次配置したものであり、横方向が第１のソート部２０８のソーティング結果を各階層ごとにコストの順に示したものである。このような経路候補リストは、経路候補リスト記憶部２１７に格納されている。この図１０に示す経路候補リストを基にして、最初に予測デマンド“Ａ−Ｂ”の選択が行われる。予測デマンド“Ａ−Ｂ”を選択したとき、取り得る経路としての経路候補は、“Ａ−Ｂ”、“Ａ−Ｃ−Ｂ”、“Ａ−Ｄ−Ｂ”および“Ａ−Ｄ−Ｃ−Ｂ”の４つである。
【００５５】
この例の場合、最上層としての予測デマンド“Ａ−Ｂ”を選択できたので（図９ステップＳ３２３：Ｙ）、次のステップＳ３２４では、選択した予測デマンドに対して各経路候補を追加した場合の配置コストを算出する。この時点では、まだ予測デマンドに対する経路候補が１つも選択されていない。そこで、「選択した予測デマンドに対して各経路候補を追加した場合の配置コスト」は、予測デマンド“Ａ−Ｂ”における各経路候補の配置コストと算出結果が等しい。具体的には、図１０に示すように経路候補“Ａ−Ｂ”については“１”であり、経路候補“Ａ−Ｃ−Ｂ”については“５”であり、経路候補“Ａ−Ｄ−Ｂ”および“Ａ−Ｄ−Ｃ−Ｂ”については“７”である。図１０ではこれらの配置コストを括弧（
）内に数字で示している。
【００５６】
ステップＳ３２５では、これらの経路候補のリストとこれらの設備コストを所定のスタックに収容する。第１のソート部２０８ですでにソーティングが行われているので、このソーティング結果を使用して、配置コストが大きなものから順にスタックに収容する。なお、この最初の場合には設備コストとそれぞれの経路候補の配置コストの値が等しくなる。このスタック（以下、第１階層のスタックという。）はファースト・イン・ラストアウトのメモリで構成されており、後に入れたもの、すなわち配置コストが小さなものから順に読み出されるようになっている。これは、なるべく早い時点で基も経済的な経路を算出できるようにするためである。
【００５７】
次のステップＳ３２６では、第１階層のスタックから経路候補を１つ取り出す。この場合の経路候補は経路候補“Ａ−Ｂ”であり、その配置コストは“１”である。次のステップＳ３２７ではこの配置コストが上限値よりも小さい値であるかどうかの判別が行われる。この場合は問題なく小さい（Ｙ）。そこで、ステップＳ３２２に戻って、図１０に示す１つ下の予測デマンドを選択する。予測デマンド“Ａ−Ｃ”が選択できたので（ステップＳ３２３：Ｙ）、ステップＳ３２４では、経路候補“Ａ−Ｂ”が選択された場合における予測デマンド“Ａ−Ｃ”での各経路候補“Ａ−Ｂ−Ｃ”、“Ａ−Ｃ”、“Ａ−Ｄ−Ｃ”を追加した場合の配置コストを算出する。
【００５８】
経路候補“Ａ−Ｂ−Ｃ”については、すでに経路候補“Ａ−Ｂ”が選択されているので、これに経路“Ｂ−Ｃ”を追加することになる。そこでこの場合の配置コストは、“１”と経路候補“Ｂ−Ｃ”の配置コストの“２”を加算した“３”となる。経路候補“Ａ−Ｃ”については、共通する経路が存在しない。そこで経路候補“Ａ−Ｂ”の配置コスト“１”に経路候補“Ａ−Ｃ”の配置コスト“３”を加えた値“４”となる。
【００５９】
最後に経路候補“Ａ−Ｄ−Ｃ”については、同様に共通する経路が存在しない。そこで経路候補“Ａ−Ｄ”の配置コスト“３”に経路候補“Ｄ−Ｃ”の配置コスト“２”の和としての値“５”に、その直前の階層までの配置コスト（経路候補“Ａ−Ｂ”の配置コスト）“１”を加えた値“６”となる。これらの配置コストは、同様に大きなものから順番にファースト・イン・ラストアウトのメモリで構成された他のスタック（第２階層のスタックという。）に収容される（ステップＳ３２５）。
【００６０】
次のステップＳ３２６では、この第２階層のスタックから経路候補を１つ取り出す。この場合の経路候補は経路候補“Ａ−Ｂ−Ｃ”であり、その配置コストは“３”である。次のステップＳ３２７ではこの配置コストが上限値よりも小さい値であるかどうかの判別が行われる。この場合も問題なく小さい（Ｙ）。そこで、ステップＳ３２２に戻って、図１０に示す１つ下の予測デマンドを選択する。予測デマンド“Ａ−Ｄ”が選択できたので（ステップＳ３２３：Ｙ）、ステップＳ３２４では、経路候補“Ａ−Ｂ−Ｃ”が選択された場合における予測デマンド“Ａ−Ｄ”での各経路候補“Ａ−Ｂ−Ｃ−Ｄ”、“Ａ−Ｄ”、“Ａ−Ｂ−Ｄ”、“Ａ−Ｃ−Ｄ”を追加した場合の配置コストを算出する。
【００６１】
経路候補“Ａ−Ｂ−Ｃ−Ｄ”については、すでに経路候補“Ａ−Ｂ−Ｃ”が選択されているので、これに経路“Ｃ−Ｄ”を追加することになる。そこでこの場合の配置コストは、“３”と経路候補“Ｃ−Ｄ”の配置コストの“２”を加算した“５”となる。経路候補“Ａ−Ｄ”については、共通する経路が存在しない。そこで経路候補“Ａ−Ｂ−Ｃ”の配置コスト“３”に経路候補“Ａ−Ｄ”の配置コスト“３”を加えた値“６”となる。以下、同様にして図１０に示すように経路候補“Ａ−Ｂ−Ｄ”を選択した場合の配置コストは“７”であり、経路候補“Ａ−Ｃ−Ｄ”を選択した場合の配置コストは“８”となる。これらの配置コストは、同様に大きなものから順番にファースト・イン・ラストアウトのメモリで構成された更に他のスタック（第３階層のスタックという。）に収容される（ステップＳ３２５）。
【００６２】
次のステップＳ３２６では、この第３階層のスタックから経路候補を１つ取り出す。この場合の経路候補は経路候補“Ａ−Ｂ−Ｃ−Ｄ”であり、その配置コストは“５”である。次のステップＳ３２７ではこの配置コストが上限値よりも小さい値であるかどうかの判別が行われる。この場合も問題なく小さい（Ｙ）。そこで、ステップＳ３２２に戻って、図１０に示す１つ下の予測デマンドを選択する。予測デマンド“Ｂ−Ｃ”が選択できたので（ステップＳ３２３：Ｙ）、ステップＳ３２４では、経路候補“Ａ−Ｂ−Ｃ−Ｄ”が選択された場合における予測デマンド“Ｂ−Ｃ”での各経路候補“Ｂ−Ｃ”、“Ｂ−Ａ−Ｄ−Ｃ”、“Ｂ−Ａ−Ｃ”、“Ｂ−Ｄ−Ｃ”を追加した場合の配置コストを算出する。
【００６３】
これらの各経路候補“Ｂ−Ｃ”、“Ｂ−Ａ−Ｄ−Ｃ”、“Ｂ−Ａ−Ｃ”、“Ｂ−Ｄ−Ｃ”を追加した場合の配置コストは、図１０に示したようにそれぞれ値“５”、“８”、“８”、“９”となる。経路候補“Ｂ−Ｃ”を追加した場合の配置コストが増加しなかったのは、経路“Ｂ−Ｃ”間が共通するからである。これらの配置コストは、同様に大きなものから順番にファースト・イン・ラストアウトのメモリで構成された更に他のスタック（第４階層のスタックという。）に収容される（ステップＳ３２５）。
【００６４】
次のステップＳ３２６では、この第４階層のスタックから経路候補を１つ取り出す。以下、同ようにして第５階層および第６階層のスタックに経路候補が収容されていく。第６階層のスタックに経路候補が収容された後にその中から最初の１つの経路候補が取り出され（ステップＳ３２６）、そのときの設備コストが上限値と比較されたとする（ステップＳ３２７）。この場合も問題なく設備コストが上限値よりも小さい（Ｙ）。そこでステップＳ３２２に戻って、図１０に示す１つ下の予測デマンドを選択しようとする。ところが、予測デマンド“Ｃ−Ｄ”はこの例で最下層（第６階層）なので、更にその下の予測デマンドを選択することができない（ステップＳ３２３：Ｎ）。
【００６５】
そこで、この場合にはステップＳ３２８に進んで、今まで∞（無限大）に設定していた配置コストの上限値が現在の配置コストよりも大きいかどうかを判別する。大きい場合には（Ｙ）、配置コストの上限値を、今までの暫定的な値としての無限大（∞）から現在の配置コストの最小値である値“５”に置き換える（ステップＳ３２９）。これは、以上説明した第１回目の探索により得られた配置コストよりもコストの高い配置コストが最下層（この例では第６階層）に至る前に出現したら、その時点でそれ以降の経路の配置の可能性やそれらの配置コストの検討を行わないようにするためである。それ以後の処理を行っても、配置コストが減少していくことはあり得ないことによる。そして、更に次の経路探索を開始することで、最も経済的な経路をより短時間に探し当てるようにしている。
【００６６】
また、ステップＳ３２９では、現在の第１階層（最上層）から第６階層まで検討した経路としての設備配置を最終的な出力候補にとりあえず設定する。ただし、本実施例では第１のソート部２０８が各階層ごとに配置コストが小さい順にソーティングを行い、かつファースト・イン・ラストアウトのスタックから配置コストの小さな順に経路候補を取り出して配置コストを算出している。したがって、最初から比較的経済的な設備配置を見つけることができる。このようにして１つの設備配置が求められたら、ステップＳ３２６に処理が戻され、次の設備配置についての検討が開始される。
【００６７】
ステップＳ３２６では、第１階層のスタックの経路候補“Ａ−Ｂ”から派生した各経路候補“Ａ−Ｂ−Ｃ”、“Ａ−Ｃ”、“Ａ−Ｄ−Ｃ”のうちの配置コストが最小の経路候補“Ａ−Ｂ−Ｃ”についての処理が終了したので、次にコストの低い経路候補“Ａ−Ｃ”が取り出される。この配置コストはすでに説明したように値“４”である。ステップＳ３２７ではこの配置コストの値“４”を上限値“５”と比較する。この場合、上限値“５”よりも小さいので（Ｙ）、こちらの経路の方が最小値を更に更新する可能性がある。そこでステップＳ３２２に戻って経路候補“Ａ−Ｃ”よりも１階層低い予測デマンドを選択する。
【００６８】
図１０より明らかなようにこれは、第３階層の各予測デマンド“Ａ−Ｃ−Ｄ”、“Ａ−Ｄ”、“Ａ−Ｂ−Ｃ−Ｄ”、“Ａ−Ｂ−Ｄ”である。この場合もこのように選択ができたので（ステップＳ３２３：Ｙ）、ステップＳ３２４では各経路候補“Ａ−Ｃ−Ｄ”、“Ａ−Ｄ”、“Ａ−Ｂ−Ｃ−Ｄ”、“Ａ−Ｂ−Ｄ”を追加した場合の配置コストを算出する。図１０に示すようにこれらは順に値“６”、“７”、“８”、“８”となる。したがって、ステップＳ３２７に進んで現在の上限値“５”とこれらの値の最小値“６”を比較した時点で配置コストの方が大きくなる（Ｎ）。すなわち、ステップＳ３２５で配置コストをコスト順に配置してそのうちの最小値を比較しても今までの配置コストの値よりも大きいので、第１階層のスタックの経路候補“Ａ−Ｂ”から派生した経路候補“Ａ−Ｃ”のルートでは配置コストが更に低くなる可能性がないことになる。そこで、終了条件に合致するかどうかの判別が行われる（ステップＳ３３０）。まだ検討すべき設備配置が存在するので（Ｎ）、ステップＳ３２６に再び処理が戻ることになる。このようにステップＳ３２７を中心とする処理は無駄な探索をカットする処理であり、これは図１に示すカット部２１４が行う処理である。
【００６９】
ステップＳ３２６で、今度は第１階層のスタックの経路候補“Ａ−Ｂ”から派生した経路候補“Ａ−Ｄ−Ｃ”が選択される。ところがその配置コストは値“６”であり、上限値“５”よりも大きい。このため、この経路候補“Ａ−Ｂ”に対する予測デマンドを選択するまでもなく処理は再びステップＳ３３０に進む。
【００７０】
次のステップＳ３２６では第１階層の予測デマンド“Ａ−Ｂ”に関連するすべての処理が終了したので、第１階層の次の予測デマンド“Ａ−Ｃ−Ｂ”に関する処理が開始される。以下同様にして処理が進行していくと、ステップＳ３２７でそのときの上限値よりも配置コストの方が大きい場合に他の比較すべき経路が存在しなくする時点が到来する。これが終了条件に合致した時点であり（ステップＳ３３０：Ｙ）、この時点で経路が確定することになる（エンド）。すなわち、この時点で出力候補として挙げられている経路（ステップＳ３２９参照）が、最も経済的な経路であり、これが設備配置出力部２２２に出力されることになる。
【００７１】
発明の第１の変形例
【００７２】
図１１は、本発明の第１の変形例における通信網設計装置の構成の概要を表わしたものである。この通信網設計装置２０１Ａで図１と同一部分には同一の符号を付しており、これらの説明を適宜省略する。この第１の変形例で第１のソート部２０８Ａは、先の実施例の第１のソート部２０８と同様に経路候補設計部２０６で設計された各予測デマンドごとの経路候補をリンク配置コストの和の小さい順にソーティングする部分である。実施例と相違する点は、実施例の場合には同一階層の間でのソーティングすなわち横方向のソーティングを行ったが、第１の変形例ではこれに加えて縦方向のソーティングを行う点である。
【００７３】
図１２は、この第１の変形例における経路候補設計部および第１のソート部の制御の流れを表わしたものであり、先の実施例の図６と対応するものである。そこで、図１２で図６と同一部分には同一の符号を付している。この第１の変形例で経路候補設計部２０６は予測デマンドを１つ選択する（ステップＳ２３１）。たとえば最初は予測デマンド“Ａ−Ｂ”を選択する。次に、選択したその予測デマンドについて経路候補設計を行う（ステップＳ２３２）。そして前記したようにこれらの和を小さい順に並べる（ステップＳ２３３）。次のステップ２３４ではすべての予測デマンドの処理が終了したかどうかをチェックして、終了していなければ（Ｎ）、ステップＳ２３１に戻って次の予測デマンドについての同様の処理を行う。このようにしてすべての予測デマンドについての処理が終了すれば（ステップＳ２３４：Ｙ）、今度は最小配置コスト順に予測デマンドをソートする（ステップＳ２３５）。これが階層の深さ方向としての縦方向のソーティングである。
【００７４】
図１３は、第１のソート部による横方向および縦方向のソーティングが行われた結果として経路候補記憶部に記憶された経路候補データを示したものである。図１２で説明した処理によって得られた予測デマンドと経路候補の関係を示したリストは、経路候補データ２４１Ａとして経路候補記憶部２１０（図１１）に記憶されることになる。
【００７５】
先の実施例で示した図８は、通信網設計装置における通信網の設計処理の大まかな流れを表わしたものであり、この第１の変形例でもこの処理は同様に行われる。そこでこの説明は省略する。同様に先の実施例で示した図９は図８のステップＳ３０３に相当する経路候補組み合わせ設計部の設計処理を具体的に表わしたものであるが、この第１の変形例でも同様の処理が行われる。ただし、ステップＳ３２２で予測デマンドの選択を行うときに、図１３で示した経路候補データ２４１Ａで示される予測デマンドの順に選択が行われる点が相違する。
【００７６】
すなわち、このような第１の変形例によれば、各予測デマンドごとの経路候補をリンク配置コストの和の小さい順にソーティングする横方向のソーティングを行うだけでなく、最小配置コスト順に予測デマンドをソートする縦方向のソーティングを行っているので、コストが低減される通信網の多くを比較的初期的な段階で検討することができる。したがって、この結果としてたとえば図９のステップＳ３２９で、コスト上限値をより早い段階でより低下させることが可能になり、やむを得ない事情等で比較的早い段階で途中で処理を中止するような場合でも比較的良好な通信網を設計することができる。
【００７７】
発明の第２の変形例
【００７８】
図１４は、本発明の第２の変形例における通信網設計装置の構成の概要を表わしたものである。この通信網設計装置２０１Ｂで図１と同一部分には同一の符号を付しており、これらの説明を適宜省略する。この第２の変形例で第１のソート部２０８Ｂは、先の第１の変形例における第１のソート部２０８Ａにおける縦方向のソーティング（最小配置コスト順に予測デマンドをソーティング）のみを行っており、実施例の第１のソート部２０８のような横方向のソーティング（同一階層の間でのソーティング）は行わない。また、第２の変形例の通信網設計装置２０１Ｂで、経路候補組み合わせ設計部２１２は第２のソート部２１３を介して経路候補リスト記憶部２１７と接続されている。第２のソート部２１３は、経路候補組み合わせ設計部２１２から経路候補の組み合わせデータ２１５を読み出して、配置コストが小さい順に取り出せるように大きい順に、後に説明するスタックに追加する処理を行うようになっている。
【００７９】
図１５は、この第２の変形例における経路候補設計部および第１のソート部の制御の流れを表わしたものであり、先の実施例の図６および第１の変形例の図１２と対応するものである。そこで、図１５で図６あるいは図１２と同一部分には同一の符号を付している。この第２の変形例で経路候補設計部２０６は予測デマンドを１つ選択する（ステップＳ２３１）。たとえば最初は予測デマンド“Ａ−Ｂ”を選択する。次に、選択したその予測デマンドについて経路候補設計を行う（ステップＳ２３２）。そして次のステップ２３４ではすべての予測デマンドの処理が終了したかどうかをチェックして、終了していなければ（Ｎ）、ステップＳ２３１に戻って次の予測デマンドについての同様の処理を行う。このようにしてすべての予測デマンドについての処理が終了すれば（ステップＳ２３４：Ｙ）、今度は最小配置コスト順に予測デマンドをソートする（ステップＳ２３５）。これが階層の深さ方向としての縦方向のソーティングである。
【００８０】
図１６は、第１のソート部による縦方向のソーティングが行われた結果として経路候補記憶部に記憶された経路候補データを示したものである。この図に示すように横方向のソーティングが行われていないので、横方向については配置コストの順番となっていない。図１５で説明した処理によって得られた予測デマンドと経路候補の関係を示したリストは、経路候補データ２４１Ｂとして経路候補記憶部２１０（図１４）に記憶されることになる。
【００８１】
先の実施例で示した図８は、通信網設計装置における通信網の設計処理の大まかな流れを表わしたものであり、この第２の変形例でもこの処理は同様に行われる。そこでこの説明は省略する。
【００８２】
図１７は、ステップＳ３０３に相当する経路候補組み合わせ設計部の設計処理を具体的に表わしたものである。この図で先の実施例の図９と同一部分には同一の符号を付している。この第２の変形例ではステップＳ３２１からステップＳ３２４までの処理は実施例と全く同一である。実施例における図９に示したステップＳ３２５では、経路候補のリストと設備コストを所定のスタックに収容するとき、第１のソート部２０８ですでに横方向のソーティングが行われているので、このソーティング結果を使用して、配置コストが大きなものから順にスタックに収容するようにしている。
【００８３】
一方、第２の変形例の通信網設計装置２０１Ｂでは、図１６に示したように経路候補は予測デマンドごとに見てみると、配置コストとは無関係に配置されている。たとえば予測デマンド“Ａ−Ｂ”について見てみると、経路候補“Ａ−Ｂ”、“Ａ−Ｃ−Ｂ”、“Ａ−Ｄ−Ｂ”および“Ａ−Ｄ−Ｃ−Ｂ”はこの順に配置されれば配置コスト順となる（図１３参照）が、経路候補データ２４１Ｂでは経路候補“Ａ−Ｄ−Ｂ”が先頭となっており、続いて経路候補“Ａ−Ｃ−Ｂ”、“Ａ−Ｂ”、“Ａ−Ｄ−Ｃ−Ｂ”の順となっている。
【００８４】
そこで、図１４に示す第２のソート部２１３は、これを配置コストでソーティングして、配置コストが大きなものから順にスタックに収容することになる。このスタック（第１階層のスタック）はファースト・イン・ラストアウトのメモリで構成されており、後に入れたもの、すなわち配置コストが小さなものから順に読み出されるようになっている。これは、なるべく早い時点で基も経済的な経路を算出できるようにするためである。なお、ステップＳ３２６以降の処理は実施例と全く同一であるので、この説明も省略することにする。
【００８５】
その他の変形可能性
【００８６】
図１８は、第１のソート部、第２のソート部およびカット部の組み合わせの態様を表わしたものである。たとえば実施例では第１のソート部２０８が横方向のソーティングのみを行い、第２のソート部２１３は存在していない。カット部２１４は存在している。そこでこの図の態様“ｅ”が実施例の通信網設計装置２０１に相当する。第１の変形例では第１のソート部２０８Ａが横方向のソーティングと縦方向のソーティングを行っている。カット部２１４は存在している。そこで態様“ｆ”が第１の変形例の通信網設計装置２０１Ａに相当する。第２の変形例では第１のソート部２０８Ａが縦方向のソーティングのみを行い、第２のソート部２１３もソーティングを行っている。カット部２１４は存在している。そこで態様“ｄ”が第２の変形例の通信網設計装置２０１Ｂに相当する。
【００８７】
カット部２１４は経路候補の組み合わせによる配置コストを上限値と比較する（図１７ステップＳ３２７参照）ことで、経済的な経路としての可能性のない計算処理を省略するものであり、本発明にとって必須の要素である。一方、第１および第２のソート部については、以上説明した実施例および変形例以外にも更に別の態様“ａ”〜“ｃ”で通信網設計装置を構成することができる。もちろん、態様“ａ”は態様“ｆ”と比べると通信網の設計の効率が低いが、装置自体を簡易に構成することができる。
【００８８】
図１９は、第１および第２のソート部によるソーティングの効果を示したものである。この図で縦軸は現在の配置コストを示しており、横軸は最下層まで探索が行われた回数を示している。図で折れ線４０１は態様“ａ”の場合を示している。この場合にはコスト上限値としての配置コストがなかなか低下せず、４０回目に近いところで配置コストが値“５”の経路の探索に成功している。
【００８９】
一方、折れ線４０２は態様“ｅ”の場合を示している。この場合には第１のソート部２０８Ａが横方向のソーティングを行っている。これにより、同一予測デマンドでは配置コストの低い順に経路の検討が行われ、カット部２１４のカットの効率も高くなるので実施例では十数回目で配置コストが値“５”の経路の探索に成功している。直線４０３は、態様“ｄ”の場合を示しており、第１および第２のソート部２０８Ｂ、２１３を使用した例である。予測デマンドも配置コストの順にそろえた結果として更に効率的な通信網の設計が可能になり、この例では１回目で配置コストが値“５”の経路の探索に成功している。
【００９０】
図２０は、本実施例におけるカット部の働きを示したものである。カット部２１４が存在しない場合には、本実施例では２３０４通りの組み合わせを調べてみないと配置コストの総和が最も小さくなる経路を結論付けることができない。折れ線４１１はカット部２１４が存在しない場合で本実施例の場合の最小の配置コスト“５”を得ることができる場合を、探索をランダムに行った場合の結果として示したものである。時間を十分かけて最適な経路の探索を行うものとした場合には、前記したようにすべての組み合わせ（本実施例で２３０４通りの組み合わせ）を調べれば最適の経路を求めることができる。しかしながら、ノードの数が多く採りうる経路が膨大となると、最適の経路を求めるための作業をある時点で打ち切る必要性が生じる場合もある。このような場合でも有限な作業時間の経過した時点で、最適あるいは最適に近い経路を選択できるようにすることが重要となる。
【００９１】
この図２０で、それぞれ折れ線で示した第１〜第３の系列４１１〜４１３は、カット部２１４を設けることなく幾つかの組み合わせで最小配置コストが更新される状態を表わしたものである。ここで第１の系列４１１は、図１９に示した態様“ａ”の折れ線４０１に対応するもので、配置コストに対するソーティングを一切行わずに、かつ途中で今までの配置コストの総和の最小値よりも大きな値の総和が出現しても算出を継続した場合の一例を示している。第２の系列４１２は図１９に示した態様“ｅ”の折れ線４０２に対応するものであり、第３の系列４１３は態様“ｄ”の折れ線（直線）４０３に対応するものである。
【００９２】
【発明の効果】
以上説明したように請求項１〜請求項５記載の発明によれば、算出カット手段を備えており、配置コスト総和算出手段がそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行するようにした。これにより、採りうる経路が膨大であってもその処理の迅速化を図ることができる。
【００９３】
また請求項２記載の発明によれば、経路候補設計手段によって設計された予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置する横方向再配置手段を備えており、配置コスト総和算出手段は横方向再配置手段によって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求め、かつ算出カット手段で経路の途中でも積算の中止を行うようにしているので、比較的早期に最も経済的な経路が出力候補記憶手段に記憶される可能性が高くなる。このため、処理が迅速化されるだけでなく、通信網設計装置の処理時間に制限がある場合でも比較的経済的な通信網を求めやすいという効果がある。
【００９４】
更に請求項３記載の発明によれば、縦方向再配置手段が経路候補設計手段によって設計された予測デマンドを配置コストの小さい順に再配置するようにし、配置コスト総和算出手段は縦方向再配置手段によって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまで入力装置の経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めることにするとともに、算出カット手段で経路の途中でも積算の中止を行うようにしているので、処理が迅速化されるだけでなく、通信網設計装置の処理時間に制限がある場合でも比較的経済的な通信網を求めやすいという効果がある。
【００９５】
また請求項４記載の発明によれば、横方向再配置手段が経路候補設計手段によって設計された予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置するとともに、縦方向再配置手段が経路候補設計手段によって設計された予測デマンドを配置コストの小さい順に再配置するようにし、配置コスト総和算出手段は横方向再配置手段および縦方向再配置手段によって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまで入力装置の経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めることにするとともに、算出カット手段で経路の途中でも積算の中止を行うようにしているので、比較的早期に最も経済的な経路が出力候補記憶手段に記憶される可能性が高くなる。このため、処理が迅速化されるだけでなく、通信網設計装置の処理時間に制限がある場合でも比較的経済的な通信網を求めやすいという効果がある。
【００９６】
更に請求項５記載の発明によれば、請求項１または請求項３記載の通信網設計装置で、横方向のソートが行われなかったものについて次の経路を選択するときに横方向で配置コストの小さい順に経路を選ぶことで、最小配置コストが低い可能性の高い経路から各経路候補の配置コストの総和を求めることにし、算出カット手段の効果と併せて処理の迅速化を図ることができる。
【００９７】
また求項６〜請求項１０記載の発明によれば、算出カットステップを備えており、配置コスト総和算出ステップでそれぞれ経路を構成する各経路候補の配置コストを順に積算するたびにその積算後の値を最小配置コストと比較して積算後の値が最小配置コストよりも大きくなったときその経路の残りの経路候補の配置コストの算出を省略して次の算出すべき経路が存在する場合にはその経路についての配置コストの総和を求める処理に移行するようにした。これにより、採りうる経路が膨大であってもその処理の迅速化を図ることができる。
【００９８】
更に請求項７記載の発明によれば、経路候補設計ステップによって設計された予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置する横方向再配置ステップを備えており、配置コスト総和算出ステップでは横方向再配置ステップによって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまでの経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求め、かつ算出カットステップで経路の途中でも積算の中止を行うようにしているので、比較的早期に最も経済的な経路が出力候補記憶ステップで記憶される可能性が高くなる。このため、処理が迅速化されるだけでなく、通信網設計装置の処理時間に制限がある場合でも比較的経済的な通信網を求めやすいという効果がある。
【００９９】
また請求項８記載の発明によれば、縦方向再配置ステップで経路候補設計ステップによって設計された予測デマンドを配置コストの小さい順に再配置するようにし、配置コスト総和算出ステップでは縦方向再配置ステップによって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまで入力装置の経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めることにするとともに、算出カットステップで経路の途中でも積算の中止を行うようにしているので、処理が迅速化されるだけでなく、通信網設計装置の処理時間に制限がある場合でも比較的経済的な通信網を求めやすいという効果がある。
【０１００】
更に請求項９記載の発明によれば、横方向再配置ステップで経路候補設計ステップによって設計された予測デマンドに対して採りうる各経路候補を配置コストの小さい順に再配置するとともに、縦方向再配置ステップで経路候補設計ステップによって設計された予測デマンドを配置コストの小さい順に再配置するようにし、配置コスト総和算出ステップは横方向再配置ステップおよび縦方向再配置ステップによって再配置されたそれぞれの経路についてこれらを構成する経路候補を順に選択してそれまで入力装置の経路で必要とされた配置コストを順に積算することで経路ごとの配置コストの総和を求めることにするとともに、算出カットステップで経路の途中でも積算の中止を行うようにしているので、比較的早期に最も経済的な経路が出力候補記憶ステップで記憶される可能性が高くなる。このため、処理が迅速化されるだけでなく、通信網設計装置の処理時間に制限がある場合でも比較的経済的な通信網を求めやすいという効果がある。
【０１０１】
また請求項１０記載の発明によれば、請求項６または請求項８記載の通信網設計方法で、横方向のソートが行われなかったものについて次の経路を選択するときに横方向で配置コストの小さい順に経路を選ぶことで、最小配置コストが低い可能性の高い経路から各経路候補の配置コストの総和を求めることにし、算出カットステップの効果と併せて処理の迅速化を図ることができる。
【図面の簡単な説明】
【図１】本発明の一実施例における通信網設計装置の構成の概要を表わした概略構成図である。
【図２】本実施例で設計の対象とする簡易化された通信網における各ノードの配置を示した説明図である。
【図３】本実施例の設計情報記憶部に記憶された設計情報のうちの配置コスト情報の一例を示した説明図である。
【図４】本実施例で設計情報記憶部に記憶された設計情報のうちの予測デマンド・経路候補組み合わせ表データを示した説明図である。
【図５】本実施例で第１のソート部のソーティングの様子を示した説明図である。
【図６】本実施例で経路候補設計部および第１のソート部の処理を示した流れ図である。
【図７】本実施例で第１のソート部による横方向のソーティングが行われた結果として経路候補記憶部に記憶された経路候補データを示した説明図である。
【図８】本実施例の通信網設計装置における通信網の設計処理の概要を表わした流れ図である。
【図９】図８のステップＳ３０３に相当する経路候補組み合わせ設計部の設計処理を具体的に表わした流れ図である。
【図１０】本実施例で経路候補リスト記憶部に記憶される経路候補リストの一例を表わした説明図である。
【図１１】本発明の第１の変形例における通信網設計装置の構成の概要を表わしたブロック図である。
【図１２】第１の変形例における経路候補設計部および第１のソート部の制御の流れを表わした流れ図である。
【図１３】本発明の第１の変形例で、第１のソート部による横方向および縦方向のソーティングが行われた結果として経路候補記憶部に記憶された経路候補データを示した説明図である。
【図１４】本発明の第２の変形例における通信網設計装置の構成の概要を表わしたブロック図である。
【図１５】第２の変形例における経路候補設計部および第１のソート部の制御の流れを表わした流れ図である。
【図１６】第２の変形例で第１のソート部による縦方向のソーティングが行われた結果として経路候補記憶部に記憶された経路候補データを示した説明図である。
【図１７】第２の変形例で図８のステップＳ３０３に相当する経路候補組み合わせ設計部の設計処理を具体的に表わした流れ図である。
【図１８】第１のソート部、第２のソート部およびカット部の組み合わせの態様を表わした説明図である。
【図１９】本実施例で第１および第２のソート部によるソーティングの効果を示した特性図である。
【図２０】本実施例でカット部の働きを示した特性図である。
【図２１】通信網の設計の対象となる４つのノードを示した説明図である。
【図２２】図２１に示す例で、２組のノード間で通信が行われる場合の通信網の設計例を示した説明図である。
【図２３】図２１に示す例で、４つのノード間を最も不経済に通信路を接続した例を示した説明図である。
【図２４】図２１に示す例で、通信網設計の設計の他の態様を表わした説明図である。
【符号の説明】
２０１、２０１Ａ、２０１Ｂ  通信網設計装置
２０３  設計情報
２０４  設計情報記憶部
２０６  経路候補設計部
２０８、２０８Ａ、２０８Ｂ  第１のソート部
２１０  経路候補記憶部
２１２  経路候補組み合わせ設計部
２１３  第２のソート部
２１４  カット部
２１７  経路候補リスト記憶部
２２２  設備配置出力部
２４１  経路候補データ
【図１】
0003711897.tif 000002
【図２】
0003711897.tif 000003
【図３】
0003711897.tif 000004
【図４】
0003711897.tif 000005
【図５】
0003711897.tif 000006
【図６】
0003711897.tif 000007
【図７】
0003711897.tif 000008
【図８】
0003711897.tif 000009
【図９】
0003711897.tif 000010
【図１０】
0003711897.tif 000011
【図１１】
0003711897.tif 000012
【図１２】
0003711897.tif 000013
【図１３】
0003711897.tif 000014
【図１４】
0003711897.tif 000015
【図１５】
0003711897.tif 000016
【図１６】
0003711897.tif 000017
【図１７】
0003711897.tif 000018
【図１８】
0003711897.tif 000019
【図１９】
0003711897.tif 000020
【図２０】
0003711897.tif 000021
【図２１】
0003711897.tif 000022
【図２２】
0003711897.tif 000023
【図２３】
0003711897.tif 000024
【図２４】
0003711897.tif 000025