JP2014078790A - ネットワーク設計装置、ネットワーク設計方法、ネットワーク設計プログラム - Google Patents

Abstract

【課題】簡易に適切な伝送路の組み合わせ候補を求める。
【解決手段】各ノードにおいて終端されるデマンドの本数と各ノードを通過するデマンドの本数との合計値を算出し、リンクによって接続される他のノードの数を示すノードの次数を算出し、複数のノードを、ノードの次数が大きいノードが上位になるように、ノードの次数が同じ場合には合計値が大きいノードが上位になるように、さらに、終端されるデマンドがないノードが下位になるように、並べる順序リストを作成し、各デマンドにおいて始点ノードと終点ノードとの間に通過するノードについて順序リストに従ってソートし、各デマンドについてソートされたノードの上位のノードから所定数のノードを取り出し、始点ノード、終点ノード及び所定数のノードを端点とする伝送路の組み合わせ候補を生成し、伝送路の組み合わせ候補からデマンドを収容する伝送路の組み合わせを決定するネットワーク設計装置とする。
【選択図】図５

Description

本発明は、ネットワーク設計装置、ネットワーク設計方法、ネットワーク設計プログラムに関する。

電話局（局舎）間の大量の加入者回線の信号を収容するＴＤＭ（Time Division Multiplexing：時分割多重）技術がある。ＴＤＭ技術により加入者回線の信号を収容する伝送路は、ＴＤＭ伝送路と呼ばれる。また、ＴＤＭ伝送路に収容される加入者回線の信号は、トラフィックデマンド又はデマンドと呼ばれる。デマンドは、始点ノードから終点ノードまでの信号伝送の経路を指定する。ＴＤＭ伝送路として、例えば、ＳＤＨ（Synchronous Digital Hierarchy）伝送路や、近年標準化されたＯＴＮ（Optical Transport Network）伝送路などが挙げられる。

ノードとしての電話局間に敷設した光ファイバを用いてデマンドを伝送するとき、同じ光ファイバによって伝送することができる複数の加入者回線の信号は、ＴＤＭ伝送路に多重化されて伝送される。従来、隣接する電話局（ノード）間に光ファイバを敷設し、光ファイバの一端の電話局（ノード）から他端の電話局（ノード）までの間にＴＤＭ伝送路が設定されていた。このとき、１本の光ファイバに１つのＴＤＭ伝送路が通る形態が一般的であった。

図１は、ノード、光ファイバ、及び、ＴＤＭ伝送路の例を示す図である。図１の例では、ノードＡ、ノードＢ、ノードＣ、ノードＤ、ノードＥがあり、Ａ−Ｂ間、Ｂ−Ｃ間、Ｃ−Ｄ間、Ｄ−Ｅ間に光ファイバが敷設されている。ＴＤＭ伝送路は、Ａ−Ｂ間（＃１）、Ｂ−Ｃ間（＃２）、Ｃ−Ｄ間（＃３）、Ｄ−Ｅ間（＃４）の４区間に設定されるとする。このとき、例えば、Ａ−Ｅ間のデマンドのうち、Ａ−Ｂ間はＡ−Ｂ間のＴＤＭ伝送路に、Ｂ−Ｃ間はＢ−Ｃ間のＴＤＭ伝送路に、Ｃ−Ｄ間はＣ−Ｄ間のＴＤＭ伝送路に、Ｄ−Ｅ間はＤ−Ｅ間のＴＤＭ伝送路に、それぞれ、収容される。この例では、Ａ−Ｅ間のデマンドは、この１通りの収容方法で収容される。

近年、ＷＤＭ（Wavelength Division Multiplexing：波長多重）技術が導入され、ノードにはＯＡＤＭ（Optical Add/Drop Multiplexer）と呼ばれる機器が置かれるようになっている。ＯＡＤＭは、光信号のまま波長単位で光信号の分岐挿入や経路切替を行う光分岐挿入装置である。ＷＤＭ技術では、従来のように、隣接するノード間にＴＤＭ伝送路が設定されるだけでなく、途中のノードで光のままノードを通過することによって、隣接しないノード間にもＴＤＭ伝送路が設定され得る。

図２は、ＯＡＤＭの構成例を示す図である。図２のＯＡＤＭは、一方の光ファイバから波長多重された光信号が入力されると、光信号を波長毎に分離し、光スイッチ（光ＳＷ）によって、そのまま通過するものと、分岐または挿入するものとに分ける。さらに、ＯＡＤＭは、光信号を波長毎に多重して、他方の光ファイバに出力する。また、他方の光ファイバから波長多重された光信号が入力されることもある。

図３は、ＴＤＭ伝送路の例を示す図である。図３の例では、図１の例と同様に、ノードＡ、ノードＢ、ノードＣ、ノードＤ、ノードＥがあり、Ａ−Ｂ間、Ｂ−Ｃ間、Ｃ−Ｄ間、Ｄ−Ｅ間に光ファイバ（リンク）が敷設されている。ここで、図２のＯＡＤＭが図１（図３）のノードＢ、ノードＣ、ノードＤに置かれたとする。このとき、ＴＤＭ伝送路は、図
１に示すような＃１−＃４の区間の他に、図３に示すＡ−Ｃ間（＃５）、Ｃ−Ｅ間（＃６）、Ｂ−Ｄ間（＃７）、Ａ−Ｄ間（＃８）、Ｂ−Ｅ間（＃９）、Ａ−Ｅ間（＃１０）の６区間にも、設定され得る。これによって、Ａ−Ｅ間のデマンドを収容する方法は、上記のような１通りの収容方法ではなくなる。

図４は、デマンドの収容方法の例を示す図である。図２のＯＡＤＭが図１のノードＢ、ノードＣ、ノードＤに置かれたとすると、Ａ−Ｅ間のデマンドを収容する方法は、図４のように８通りになる。具体的には、＃１、＃２、＃３、＃４のＴＤＭ伝送路を用いるもの（図１の例と同一）、＃５、＃３、＃４のＴＤＭ伝送路を用いるもの、＃１、＃２、＃６のＴＤＭ伝送路を用いるもの、＃５、＃６のＴＤＭ伝送路を用いるものがある。さらに、＃１、＃７、＃４のＴＤＭ伝送路を用いるもの、＃８、＃４のＴＤＭ伝送路を用いるもの、＃１、＃９のＴＤＭ伝送路を用いるもの、＃１０のＴＤＭ伝送路を用いるものがある。このように、ＷＤＭ技術の導入によって、１つのデマンドを収容するために用いる複数のＴＤＭ伝送路の組み合わせが存在するようになる。それぞれのデマンドに対して、他のデマンドの収容などを考慮した上で、適切なＴＤＭ伝送路の組み合わせを選択することが求められる。

例えば、あるネットワーク上で、すべてのノードにＯＡＤＭが置かれている場合に、デマンドがＫ本あり、デマンドｊ（ｊ＝１,・・・,Ｋ）が始点から終点までに通過するノードの数が、始点および終点を含めてｎ_j個あるとする。このとき、デマンドｊを収容する
ＴＤＭ伝送路の組み合わせの数は、次のようになる。

各デマンドは、他のデマンドとは独立に、収容するＴＤＭ伝送路の組み合わせを選択できるので、すべてのデマンドの取り得る組み合わせの数は、次のようになる。

各デマンドについて選択されたＴＤＭ伝送路の組み合わせの中で、同じ区間のＴＤＭ伝送路を選択しているデマンド同士は、ＴＤＭ伝送路の容量の範囲内で同じＴＤＭ伝送路に多重化され得る。従って、すべてのデマンドを収容するためのＴＤＭ伝送路の本数を最小にする組み合わせが存在する。この組み合わせを求める方法として、混合整数計画法がある。

ＴＤＭ伝送路の容量メニューをｍとし、例えば、ｍ＝１は容量８であり、ｍ＝２は容量３２であるとする。容量は、例えば、回線速度、ビットレートに相当する。また、ＴＤＭ伝送路の番号をｈとし、ｘ_m（ｈ）を容量メニューｍのＴＤＭ伝送路ｈの本数とする。ｃ
ｏｓｔ_mは、容量メニューｍのＴＤＭ伝送路のコストである。この表記を使用して、ＴＤ
Ｍ伝送路のコストの最小解を求めるための目的関数は、次のようになる。

次に、デマンドについての制約条件を示す。

ここで、ＴＤＭ伝送路の組み合わせ候補ｔでデマンドｌを収容できるときは、Ｔ（ｌ，ｔ）＝１、収容できないときは、Ｔ（ｌ，ｔ）＝０とする。ＴＤＭ伝送路の組み合わせ候補は、例えば、図４の＃１、＃２、＃３、＃４のＴＤＭ伝送路を用いるものは、ｌ＝１というように、同一始終点のデマンド毎に番号を割り当てられる。ｄ（ｔ）は、ＴＤＭ伝送路の組み合わせ候補ｔで収容するデマンドの本数である。ｎｕｍｂｅｒＯｆＤｅｍａｎｄｓ（ｌ）は、デマンドｌの本数である。従って、上記の制約条件は、各デマンドがいずれかのＴＤＭ伝送路の組み合わせによって必ず収容されるという制約を意味している。

次に、ＴＤＭ伝送路毎の容量の制約条件を示す。

Ｄｅｍａｎｄ＿Ｃａｐ（ｔ）は、デマンド収容パターンｔについてのデマンド帯域である。デマンド帯域は、例えば、デマンド１本あたりのビットレートである。ＴＤＭ伝送路ｈがＴＤＭ伝送路の組み合わせ候補ｔに含まれる場合、Ｉ（ｈ，ｔ）＝１、含まれない場合、Ｉ（ｈ，ｔ）＝０とする。このため、式の第１項は、ＴＤＭ伝送路ｈが含まれるデマンド収容パターンｔについて、デマンド帯域とデマンド収容パターンｔに収容されるデマンドの本数とを乗算したもの、つまり、ＴＤＭ伝送路ｈに収容するデマンドの合計帯域を示している。ＴＤＭ＿ＣＡＰ（ｍ）は容量メニューｍのＴＤＭ伝送路の容量を示しており、上述の場合、ＴＤＭ＿ＣＡＰ（１）＝８、ＴＤＭ＿ＣＡＰ（２）＝３２である。式の第２項は、容量メニューｍのＴＤＭ伝送路ｈの合計容量である。即ち、上記の式は、ＴＤＭ伝送路に収容するデマンドの合計帯域がＴＤＭ伝送路の合計容量を上回らないという条件を示している。

次に、リンクの波長数制限の制約条件を示す。リンクは、隣接ノード間の光ファイバに対応する。

ここで、ＴＤＭ伝送路ｈがリンクｓを通るときをＬｉｎｋ（ｓ，ｈ）＝１、通らないときをＬｉｎｋ（ｓ，ｈ）＝０とする。式の左辺は、リンクｓを通るＴＤＭ伝送路の合計本
数を示している。Ｗａｖｅｌｅｎｇｔｈ（ｓ）はリンクｓで利用可能な波長数を示している。

以上の目的関数と３つの制約条件式を混合整数計画法によって解くことにより、各ＴＤＭ伝送路の本数ｘ_m（ｈ）が求められる。混合整数計画法の解法は一般に知られている（
例えば、非特許文献１）。ＴＤＭ伝送路のコストの最小解（最適解）を求めることで、好適なネットワーク設計が可能となる。

特開２００８−３０１２２５号公報

坂和正敏、「離散システムの最適化」、森北出版、ｐｐ．３３−５９、ｐｐ．６１−８３、２０００年５月

デマンドを収容するＴＤＭ伝送路の組み合わせ候補の数が多いと、デマンド収容パターンｔの値の取り得る範囲が非常に大きくなるため、混合整数計画問題の式そのものが非常に大きくなることがある。式が大きくなると、計算時間が膨大になり、また、非常に膨大な記憶領域を使用するので、パーソナルコンピュータ（ＰＣ）などの一般的な計算設備では解けないといった問題がある。また、混合整数計画法のような数理計画法を使用せずに取り得るすべてのＴＤＭ伝送路の組み合わせの探索を行う場合、ＴＤＭ伝送路の組み合わせ候補の数が多くなると現実的な時間で解くことは困難である。従って、現実的な時間で解けるように、ＴＤＭ伝送路の組み合わせ候補を最適解となる可能性が高いものに絞ることが求められる。

本件開示の技術は、簡易に適切な伝送路の組み合わせ候補を求めることを課題とする。

開示の技術は、上記課題を解決するために、以下の手段を採用する。

即ち、第１の態様は、
複数のノードがリンクによって接続されるネットワークにおける前記複数のノード間の接続関係を示すネットワークトポロジ情報と、始点ノード、終点ノード、経路、本数を含むデマンドを示すデマンド情報とを格納する記憶部と、
前記ネットワークトポロジ情報及び前記デマンド情報に基づいて、
各ノードにおいて終端されるデマンドの本数と各ノードを通過するデマンドの本数との合計値を算出し、
リンクによって接続される他のノードの数を示すノードの次数を算出し、
前記複数のノードを、前記ノードの次数が大きいノードが上位になるように、前記ノードの次数が同じ場合には前記合計値が大きいノードが上位になるように、さらに、終端されるデマンドがないノードが下位になるように、並べる順序リストを作成し、
各デマンドにおいて、始点ノード及び終点ノードを除く始点ノードと終点ノードとの間に通過するノードについて、前記順序リストに従って、ソートし、
各デマンドについて、前記ソートされたノードの上位のノードから、所定数のノードを取り出し、前記始点ノード、前記終点ノード、及び、前記所定数のノードを端点とする伝送路の組み合わせ候補を生成し、
前記伝送路の組み合わせ候補から、前記デマンドを収容する伝送路の組み合わせを決定
する制御部とを、
備えるネットワーク設計装置である。

開示の態様は、プログラムが情報処理装置によって実行されることによって実現されてもよい。即ち、開示の構成は、上記した態様における各手段が実行する処理を、情報処理装置に対して実行させるためのプログラム、或いは当該プログラムを記録したコンピュータ読み取り可能な記録媒体として特定することができる。また、開示の構成は、上記した各手段が実行する処理を情報処理装置が実行する方法をもって特定されてもよい。

開示の技術によれば、簡易に適切な伝送路の組み合わせ候補を求めることができる。

図１は、ノード、光ファイバ、及び、ＴＤＭ伝送路の例を示す図である。 図２は、ＯＡＤＭの構成例を示す図である。 図３は、ＴＤＭ伝送路の例を示す図である。 図４は、デマンドの収容方法の例を示す図である。 図５は、ネットワーク設計装置の構成例を示す図である。 図６は、本実施形態のネットワーク設計装置の全体の動作フローの例を示す図である。 図７は、ネットワーク設計装置によって経路設計される対象のネットワークトポロジの例を示す図である。 図８は、ノード情報の例を示す図である。 図９は、リンク情報の例を示す図である。 図１０は、図７のようなネットワークトポロジにおけるデマンドの例を示す図である。 図１１は、デマンド情報の例を示す図である。 図１２は、ネットワーク設計装置におけるＴＤＭ伝送路の組み合わせ候補の作成の動作フローの例（１）を示す図である。 図１３は、ネットワーク設計装置におけるＴＤＭ伝送路の組み合わせ候補の作成の動作フローの例（２）を示す図である。 図１４は、ノード毎の、終端デマンド本数、通過デマンド本数、スコアの例を示す図である。 図１５は、図７のネットワークトポロジにおけるノードの次数の例を示す図である。 図１６は、ノード順序リスト生成部１２４が生成するノードの順序リストの例（１）を示す図である。 図１７は、ノード順序リスト生成部１２４が生成するノードの順序リストの例（２）を示す図である。 図１８は、途中ノードリストの例を示す図である。 図１９は、ソート済の途中ノードリストの例を示す図である。 図２０は、ｋ値リストの例を示す図である。 図２１は、Ｎ１−Ｎ６間のデマンドの４つのＴＤＭ伝送路の組み合わせ候補の例を示す図である。 図２２は、生成されるＴＤＭ伝送路組み合わせ候補の例を示す図である。 図２３は、変形例１のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（１）を示す図である。 図２４は、変形例１のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（２）を示す図である。 図２５は、変形例１のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（３）を示す図である。 図２６は、ノードの選択不可のフラグの例を示す図である。 図２７は、変形例２のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例を示す図である。 図２８は、変形例２のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（１）を示す図である。 図２９は、変形例２のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（２）を示す図である。 図３０は、上記の動作例におけるノードの順序リスト作成の際の並べ替えの動作フローの例を示す図である。 図３１は、変形例３におけるノードの順序リスト作成の際の並べ替えの動作フローの例を示す図である。 図３２は、変形例４におけるノードの順序リスト作成の際の並べ替えの動作フローの例（１）を示す図である。 図３３は、変形例４におけるノードの順序リスト作成の際の並べ替えの動作フローの例（２）を示す図である。 図３４は、変形例５におけるノードの順序リスト作成の際の並べ替えの動作フローの例（１）を示す図である。 図３５は、変形例５におけるノードの順序リスト作成の際の並べ替えの動作フローの例（２）を示す図である。 図３６は、変形例６におけるノードの順序リスト作成の際の並べ替えの動作フローの例（１）を示す図である。 図３７は、変形例６におけるノードの順序リスト作成の際の並べ替えの動作フローの例（２）を示す図である。 図３８は、変形例７におけるノードの順序リスト作成の際の並べ替えの動作フローの例（１）を示す図である。 図３９は、変形例７におけるノードの順序リスト作成の際の並べ替えの動作フローの例（２）を示す図である。 図４０は、変形例８のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（１）を示す図である。 図４１は、変形例８のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（２）を示す図である。 図４２は、変形例９のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（１）を示す図である。 図４３は、変形例９のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（２）を示す図である。 図４４は、変形例１０のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（１）を示す図である。 図４５は、変形例１０のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（２）を示す図である。 図４６は、変形例１０のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（３）を示す図である。 図４７は、変形例１１のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（１）を示す図である。 図４８は、変形例１１のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（２）を示す図である。 図４９は、変形例１１のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例（３）を示す図である。

以下、図面を参照して実施形態について説明する。実施形態の構成は例示であり、開示の構成は、開示の実施形態の具体的構成に限定されない。開示の構成の実施にあたって、実施形態に応じた具体的構成が適宜採用されてもよい。

〔実施形態〕
（構成例）
図５は、ネットワーク設計装置の構成例を示す図である。ネットワーク設計装置１００は、ネットワークの経路設計を行う。

ネットワーク設計装置１００は、制御部１１０、メモリ１４０、外部記憶装置１５０、入力装置１６０、出力装置１７０を含む。制御部１１０は、設計情報入力部１１２、ＴＤＭ伝送路組み合わせ候補生成部１１４、ＴＤＭ伝送路選択部１１６、結果出力部１１８を含む。ＴＤＭ伝送路組み合わせ候補生成部１１４は、ノード次数スコア計算部１２２、ノード順序リスト生成部１２４、途中ノードリスト生成部１２６、ＴＤＭ伝送路組み合わせ候補作成部１２８を含む。

制御部１１０は、ネットワーク設計装置１００の全体を制御する。制御部１１０には、バスを介して、メモリ１４０、外部記憶装置１５０、入力装置１６０、出力装置１７０などが接続される。

設計情報入力部１１２は、トポロジ情報、デマンド情報などの設計情報の入力を受け付ける。

ＴＤＭ伝送路組み合わせ候補生成部１１４は、ＴＤＭ伝送路の組み合わせ候補の生成を行う。

ノード次数スコア計算部１２２は、トポロジ情報、デマンド情報などに基づいて、ノードの次数やスコアを計算する。

ノード順序リスト生成部１２４は、ノードの次数とスコアからノードをソートしてノードの順序リストを生成する。

途中ノードリスト生成部１２６は、デマンド毎に途中ノードリストを生成する。

ＴＤＭ伝送路組み合わせ候補作成部１２８は、デマンド毎にデマンド経路の途中にあるノードを抽出し、ノードの順序リストに従ってソートしてＴＤＭ伝送路の組み合わせ候補を生成する。

ＴＤＭ伝送路選択部１１６は、数理計画法などにより、ＴＤＭ伝送路の組み合わせ候補から、デマンドを収容するＴＤＭ伝送路の組み合わせを決定する。

結果出力部１１８は、設計結果を出力する。

メモリ１４０は、ネットワーク設計装置１００の主記憶装置として使用される。メモリ１４０には、制御部１１０で実行されるＯＳ（Operating System）のプログラムやアプリケーショプログラムが格納される。メモリ１４０には、制御部１１０で実行されるプログラムが使用する各種データが格納される。メモリ１４０は、記憶部の一例である。

外部記憶装置１５０は、ネットワーク設計装置１００の二次記憶装置として使用される。外部記憶装置１５０には、ＯＳのプログラム、アプリケーションプログラム、各種デー
タ等が格納される。メモリ１４０に格納される各種データ、リスト、テーブル等は、外部記憶装置１５０に格納されてもよい。外部記憶装置１５０は、記憶部の一例である。

入力されたトポロジ情報や、デマンド情報、ＴＤＭ伝送路組み合わせ候補生成部１１４で生成されるノードの順序リストなどのテーブルは、メモリ１４０、外部記憶装置１５０などに格納され得る。

入力装置１６０は、オペレータ等からのトポロジ情報等の入力を受け付ける。入力装置１６０は、キーボードやポインティングデバイスなどである。

出力装置１７０は、制御部１１０により生成されたデータ等を出力する。出力装置１７０は、ディスプレイ装置やプリンタなどである。

ネットワーク設計装置１００は、パーソナルコンピュータ（ＰＣ、Personal Computer
）のような汎用のコンピュータまたはサーバマシンのような専用のコンピュータを使用して実現可能である。

コンピュータ、すなわち、情報処理装置は、プロセッサ、主記憶装置、及び、二次記憶装置や、通信インタフェース装置のような周辺装置とのインタフェース装置を含む。主記憶装置及び二次記憶装置は、コンピュータ読み取り可能な記録媒体である。

コンピュータは、プロセッサが記録媒体に記憶されたプログラムを主記憶装置の作業領域にロードして実行し、プログラムの実行を通じて周辺機器が制御されることによって、所定の目的に合致した機能を実現することができる。

プロセッサは、例えば、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）である。主記憶装置は、例えば、ＲＡＭ（Random Access Memory）やＲＯ
Ｍ（Read Only Memory）を含む。

二次記憶装置は、例えば、ＥＰＲＯＭ（Erasable Programmable ROM）、ハードディス
クドライブ（ＨＤＤ、Hard Disk Drive）である。また、二次記憶装置は、リムーバブル
メディア、即ち可搬記録媒体を含むことができる。リムーバブルメディアは、例えば、ＵＳＢ（Universal Serial Bus）メモリ、あるいは、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）のようなディスク記録媒体である。

通信インタフェース装置は、例えば、ＬＡＮ（Local Area Network）インタフェースボードや、無線通信のための無線通信回路である。

周辺装置は、上記の二次記憶装置や通信インタフェース装置の他、キーボードやポインティングデバイスのような入力装置や、ディスプレイ装置やプリンタのような出力装置を含む。また、入力装置は、カメラのような映像や画像の入力装置や、マイクロフォンのような音声の入力装置を含むことができる。また、出力装置は、スピーカのような音声の出力装置を含むことができる。

ネットワーク設計装置１００を実現するコンピュータは、プロセッサが二次記憶装置に記憶されているプログラムを主記憶装置にロードして実行することによって、設計情報入力部１１２、ＴＤＭ伝送路組み合わせ候補生成部１１４等としての機能を実現する。

一連の処理は、ハードウェアにより実行させることもできるが、ソフトウェアにより実行させることもできる。

プログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくても、並列的または個別に実行される処理を含む。

ネットワーク設計装置１００の各ユニットは、ハードウェアの構成要素、ソフトウェアの構成要素、又は、これらの組み合わせとして、それぞれ実現され得る。

ハードウェアの構成要素は、ハードウェア回路であり、例えば、ＦＰＧＡ（Field Programmable Gate Array）、特定用途向け集積回路（ＡＳＩＣ）、ゲートアレイ、論理ゲー
トの組み合わせ、アナログ回路等がある。

ソフトウェアの構成要素は、ソフトウェアとして所定の処理を実現する部品である。ソフトウェアの構成要素は、ソフトウェアを実現する言語、開発環境等を限定する概念ではない。

（動作例）
〈全体の動作〉
図６は、本実施形態のネットワーク設計装置の全体の動作フローの例を示す図である。

ステップＳ１０１では、ネットワーク設計装置１００の制御部１１０の設計情報入力部１１２は、入力装置１６０を介して、オペレータ等からのトポロジ情報及びデマンド情報の入力を受け付け、トポロジ情報及びデマンド情報を取得する。設計情報入力部１１２は、外部記憶装置１５０等にあらかじめ格納されるトポロジ情報及びデマンド情報を、外部記憶装置１５０等から取得してもよい。

図７は、ネットワーク設計装置によって経路設計される対象のネットワークトポロジの例を示す図である。ネットワークトポロジ（トポロジ）は、ネットワーク上のノードの接続形態である。トポロジは、例えば、ノード及びノードとノードとを接続するリンクによって表現される。ノード及びリンクは、例えば、それぞれ、電話局（局舎）及びファイバに対応する。トポロジ情報（ネットワークトポロジ情報）は、ネットワークトポロジを表現する情報である。トポロジ情報は、例えば、ノード情報及びリンク情報を含む。

図７の例では、ノードＮ１は、ノードＮ２と接続する。ノードＮ２は、ノードＮ１及びノードＮ３と接続する。ノードＮ３は、ノードＮ２、ノードＮ４及びノードＮ７と接続する。ノードＮ４は、ノードＮ３及びノードＮ５と接続する。ノードＮ５は、ノードＮ４、ノードＮ６及びノードＮ８と接続する。ノードＮ６は、ノードＮ５と接続する。ノードＮ７は、ノードＮ３と接続する。ノードＮ８は、ノードＮ５と接続する。

図８は、ノード情報の例を示す図である。ノード情報は、例えば、ノード名の一覧である。ノード情報は、メモリ１４０に格納される。

図９は、リンク情報の例を示す図である。リンク情報は、ノード間を接続するリンクの始点ノード及び終点ノードを含む。リンク情報には、リンク毎の光ファイバの距離が含まれてもよい。リンク情報には、ＷＤＭで利用可能な波長数が含まれてもよい。ネットワーク全体で同じＷＤＭ機器が導入される場合、リンク毎の利用可能な波長数の代わりに、ネットワーク全体で共通の１つの波長数が適用されてもよい。リンク情報は、メモリ１４０に格納される。

図１０は、図７のようなネットワークトポロジにおけるデマンドの例を示す図である。
図１０の例では、ノードＮ１とノードＮ３と間、ノードＮ１とノードＮ６と間、ノードＮ１とノードＮ７と間、ノードＮ３とノードＮ４と間、ノードＮ４とノードＮ７と間、ノードＮ４とノードＮ８と間などに、それぞれ、デマンドが存在する。デマンド情報は、デマンドを表現する情報である。

図１１は、デマンド情報の例を示す図である。デマンド情報は、例えば、始点ノード、終点ノード、帯域、本数、経路を含む。経路は、例えば、始点ノード、終点ノード、始点ノードから終点までに経由するノードによって、表される。デマンドの経路は、最短経路探索等で決定されてもよい。デマンド情報は、メモリ１４０に格納される。

デマンドの経路は、デマンドが経由するすべてのリンクによって表現されてもよい。例えば、ノードＮ１とノードＮ３との間のデマンドの経路は、Ｎ１−Ｎ２間のリンク及びＮ２−Ｎ３間のリンクとして表現されうる。

また、デマンドの経路は、デマンドが経由するすべてのノード（始点ノード及び終点ノードを含む）及びすべてのリンクによって表現されてもよい。例えば、ノードＮ１とノードＮ３との間のデマンドの経路は、ノードＮ１、Ｎ１−Ｎ２間のリンク、ノードＮ２、Ｎ２−Ｎ３間のリンク、ノードＮ３として表現されうる。

図６に戻って、ステップＳ１０２では、ネットワーク設計装置１００のＴＤＭ伝送路組み合わせ候補生成部１１４は、デマンドを収容するＴＤＭ伝送路の組み合わせの候補を生成する。デマンドを収容するＴＤＭ伝送路の組み合わせ候補の生成については、後に詳述する。

ステップＳ１０３では、ＴＤＭ伝送路選択部１１６は、ＴＤＭ伝送路組み合わせ候補生成部１１４が生成したＴＤＭ伝送路組み合わせ候補から各デマンドを収容するＴＤＭ伝送路の組み合わせを選択する。各デマンドを収容するＴＤＭ伝送路の組み合わせの選択には、例えば、混合整数計画法などが使用されうる。

ステップＳ１０４では、ＴＤＭ伝送路選択部１１６は、すべてのデマンドがいずれかのＴＤＭ伝送路の組み合わせに収容されたかを確認する。すべてのデマンドがいずれかのＴＤＭ伝送路の組み合わせに収容された場合（Ｓ１０４；ＹＥＳ）、結果出力部１１８は、すべてのデマンドについて、それぞれのデマンドが収容されるＴＤＭ伝送路の組み合わせを出力し（Ｓ１０５）、処理が終了する。

少なくとも１つのデマンドがいずれのＴＤＭ伝送路の組み合わせにも収容できなかった場合（Ｓ１０４；ＮＯ）、結果出力部１１８は、ネットワーク設計の失敗を出力し（Ｓ１０６）、処理が終了する。ネットワーク設計の失敗が出力された場合、オペレータは他の方法によりネットワーク設計を試みることになる。

〈ＴＤＭ伝送路の組み合わせ候補の生成の動作〉
図１２及び図１３は、ネットワーク設計装置におけるＴＤＭ伝送路の組み合わせ候補の作成の動作フローの例を示す図である。図１２の「Ａ１」、「Ａ２」は、それぞれ、図１３の「Ａ１」、「Ａ２」と接続する。

ステップＳ２０１では、ノード次数スコア計算部１２２は、ノード毎に、終端されるデマンドの本数および通過するデマンドの本数をカウントする。ノード次数スコア計算部１２２は、メモリ１４０から、ノード情報に含まれるノード及びデマンド情報に含まれるデマンドを抽出する。ノード次数スコア計算部１２２は、ノード情報に含まれる各ノードについて、当該ノードで終端されるデマンドの本数、及び、当該ノードを通過するデマンド
の本数を数える。終端されるデマンドの本数は、図８のノード情報に含まれる各ノードについて、図１１に含まれるデマンドの始点ノード又は終点ノードに当該ノードが含まれるデマンドの本数の和を求めればよい。例えば、ノードＮ１で終端されるデマンドの本数は、Ｎ１−Ｎ３間のデマンドが１本、Ｎ１−Ｎ６間のデマンドが１本、Ｎ１−Ｎ７間のデマンドが２本であるので、合計４本である。通過するデマンドの本数は、図８のノード情報に含まれる各ノードについて、図１１に含まれるデマンドの経路に含まれるノードのうち、始点ノード及び終点ノードを除く途中の箇所に当該ノードが出現するデマンドの本数の和を求めればよい。例えば、Ｎ１−Ｎ６間のデマンドの場合、経路は、Ｎ１、Ｎ２、Ｎ３、Ｎ４、Ｎ５、Ｎ６であり、始点ノードであるノードＮ１及び終点ノードであるノードＮ６を除くと、通過するノードは、Ｎ２、Ｎ３、Ｎ４、Ｎ５である。即ち、例えば、Ｎ１−Ｎ６間のデマンドは、ノードＮ２を通過するデマンドである。ノードＮ２を通過するデマンドの本数は、Ｎ１−Ｎ３間のデマンドが１本、Ｎ１−Ｎ６間のデマンドが１本、Ｎ１−Ｎ７間のデマンドが２本であるので、合計４本である。

ステップＳ２０２では、ノード次数スコア計算部１２２は、ノード毎に、ノードのスコアを計算する。ノードのスコアは、当該ノードで終端されるデマンドの本数（終端デマンド本数）と当該ノードを通過するデマンドの本数（通過デマンド本数）との和である。

図１４は、ノード毎の、終端デマンド本数、通過デマンド本数、スコアの例を示す図である。ノード毎の、終端デマンド本数、通過デマンド本数、スコアは、メモリ１４０に格納される。

ステップＳ２０３では、ノード次数スコア計算部１２２は、ノード毎に、ノードの次数を求める。ノードの次数は、当該ノードから出ているリンクの本数である。例えば、図７のネットワークトポロジでは、ノードＮ２から、Ｎ１−Ｎ２間のリンク、Ｎ２−Ｎ３間のリンクの２本のリンクが出ている。従って、ノードＮ２の次数は、２である。同様にして、ノードＮ３の次数は、３である。

図１５は、図７のネットワークトポロジにおけるノードの次数の例を示す図である。図１５では、例えば、ノードＮ１の次数は、１である。

ステップＳ２０４では、ノード順序リスト生成部１２４は、ノードの次数及びノードのスコアに基づいて、ノードの順序リストを生成する。ノード順序リスト生成部１２４は、ノードをノードの次数の高い順に並べる。図１５のようにノードの次数が求められているとすると、ノードの順序は、ノードの次数が高いものから、Ｎ３、Ｎ５、Ｎ２、Ｎ４、Ｎ１、Ｎ６、Ｎ７、Ｎ８となる。ここで、ノードの次数が同じものについては、ノードのスコアが高いものを上位とする。ノードＮ３及びノードＮ５は、ノードの次数が３で同じであるが、ノードＮ３のスコアは７であり、ノードＮ５のスコアは５であるので、ノードＮ３が上位となる。同様に、ノードＮ２及びノードＮ４は、ノードの次数が２で同じであるが、ノードＮ２及びノードＮ４のスコアは、それぞれ、４、５であるので、ノードＮ４が上位となる。さらに、ノードＮ１、ノードＮ６、ノードＮ７及びノードＮ８は、ノードの次数が１で同じであるが、ノードＮ１、ノードＮ６、ノードＮ７及びノードＮ８のスコアは、それぞれ、４、２、３、４であるから、順序は、Ｎ１、Ｎ８、Ｎ７、Ｎ６になる。従って、ノードの順序は、Ｎ３、Ｎ５、Ｎ４、Ｎ２、Ｎ１、Ｎ８、Ｎ７、Ｎ６となる。

ステップＳ２０５では、さらに、ノード順序リスト生成部１２４は、ステップＳ２０４で生成したノードの順序リストにおいて、終端デマンド本数が０本であるノードを、順序の最後に移動する。図１４の例では、ノードＮ２の終端デマンド本数が０本であるため、ノードＮ２をノードの順序リストの最後に移動する。従って、ノードの順序は、Ｎ３、Ｎ５、Ｎ４、Ｎ１、Ｎ８、Ｎ７、Ｎ６、Ｎ２となる。終端するデマンドの無いノードは、当
該ノードを端点とするＴＤＭ伝送路を作る可能性が低い。そのため、ステップＳ２０５の処理は、終端するデマンドの無いノードがＴＤＭ伝送路の端点になりにくくするための処理である。上述のように、図１４の例では、ノードＮ２の終端デマンド本数は０本である。例えば、ノードＮ２を通るデマンドの中で最も短いデマンドは、Ｎ１−Ｎ３間のデマンドである。Ｎ１−Ｎ３間のデマンドは、Ｎ１−Ｎ２間のＴＤＭ伝送路とＮ２−Ｎ３間のＴＤＭ伝送路との２本に分けて伝送されるよりも、Ｎ１−Ｎ３間のＴＤＭ伝送路１本で伝送されたほうが、ＴＤＭ伝送路の本数は少なくなる。ＴＤＭ伝送路の本数が少ないほど最適解に近いと考えられるため、最適解になりにくいＴＤＭ伝送路の組み合わせをできるだけ除外するため、ノードＮ２が順序の最後に移動される。

図１６は、ノード順序リスト生成部１２４が生成するノードの順序リストの例（１）を示す図である。図１６の例では、順位が高いものから順に、ノードが並べられている。

図１７は、ノード順序リスト生成部１２４が生成するノードの順序リストの例（２）を示す図である。図１７の例では、ノード毎に、当該ノードの順位が示されている。図１６の順序リストの代わりに、図１７の順序リストが使用されてもよい。

ステップＳ２０６では、途中ノードリスト生成部１２６は、デマンド毎に途中ノードリストを生成する。途中ノードリスト生成部１２６は、デマンド情報から１つのデマンド（処理中のデマンドとする）を取り出し、当該デマンドの経路の途中のノードを取り出す。デマンドの経路の途中のノードは、当該デマンドに通過されるノードである。例えば、途中ノードリスト生成部１２６は、Ｎ１−Ｎ６間のデマンドに対して、当該デマンドの経路の途中のノードである、ノードＮ２、ノードＮ３、ノードＮ４、ノードＮ５を取り出す。途中ノードリスト生成部１２６は、取り出したノードを、途中ノードリストとして、メモリ１４０に格納する。途中ノードリストは、デマンド毎に生成される。

図１８は、途中ノードリストの例を示す図である。図１８の例は、Ｎ１−Ｎ６間のデマンドの途中ノードリストの例である。Ｎ１−Ｎ６間のデマンドの途中ノードは、ノードＮ２、ノードＮ３、ノードＮ４、ノードＮ５である。途中ノードリストは、メモリ１４０に格納される。

ステップＳ２０７では、途中ノードリスト生成部１２６は、処理中のデマンドについて、途中ノードリストのノードを、順序リストに従って、ソートする。途中ノードリスト生成部１２６は、Ｎ１−Ｎ６間のデマンドの途中ノードを、Ｎ３、Ｎ５、Ｎ４、Ｎ２の順にソートする。

図１９は、ソート済の途中ノードリストの例を示す図である。図１９の例は、Ｎ１−Ｎ６間のデマンドのソート済の途中ノードリストの例である。Ｎ１−Ｎ６間のデマンドの途中ノードは、Ｎ３、Ｎ５、Ｎ４、Ｎ２の順にソートされている。ソート済の途中ノードリストは、デマンド毎に生成される。ソート済の途中ノードリストは、メモリ１４０に格納される。

ステップＳ２０８では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、処理中のデマンドについて、ｋ値リストから１つのｋの値を取り出し、ソート済の途中ノードリストの上位からｋ個のノードを取り出す。ＴＤＭ伝送路組み合わせ候補作成部１２８は、ｋの値が０であるときは、ソート済の途中ノードリストからノードを取り出さない。ｋ値リストは、デマンド毎に取り得るｋの値を示すリストである。例えば、Ｎ１−Ｎ６のデマンドについてｋの値が２である場合、取り出されるノードは、図１９の上位２つである、ノードＮ３及びノードＮ５である。

図２０は、ｋ値リストの例を示す図である。ｋ値リストでは、デマンド毎に取り得るｋの値が示される。例えば、Ｎ１−Ｎ６間のデマンドでは、取り得るｋの値は、０，１，２，３である。デマンド毎のｋの値は、あらかじめ決められている。ｋ値リストは、メモリ１４０に格納される。

ステップＳ２０９では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、処理中のデマンドについて、始点ノード、終点ノード、及び、ステップＳ２０８で取り出したノードを端点として、ＴＤＭ伝送路の組み合わせを生成する。ＴＤＭ伝送路組み合わせ候補作成部１２８は、ステップＳ２０８でノードを取り出さなかった場合、始点ノード及び終点ノードを端点とするＴＤＭ伝送路をＴＤＭ伝送路の組み合わせとして生成する。

例えば、Ｎ１−Ｎ６間のデマンドでｋの値が２である場合、取り出されているノードはノードＮ３及びノードＮ５である。このとき、ＴＤＭ伝送路組み合わせ候補作成部１２８は、始点ノードであるノードＮ１、終点ノードであるノードＮ６、取り出されたノードＮ３及びノードＮ５を端点とするＴＤＭ伝送路の組み合わせを作成する。ＴＤＭ伝送路組み合わせ候補作成部１２８は、始点ノードであるノードＮ１、終点ノードであるノードＮ６、取り出されたノードＮ３及びノードＮ５を、デマンドの経路の始点から終点までの順にソートする。ここでは、ソート後の順は、Ｎ１、Ｎ３、Ｎ５、Ｎ６である。ＴＤＭ伝送路組み合わせ候補作成部１２８は、ソートしたノードの隣り合う２つのノード間にＴＤＭ伝送路を設定する。つまり、ＴＤＭ伝送路組み合わせ候補作成部１２８は、Ｎ１−Ｎ３間のＴＤＭ伝送路、Ｎ３−Ｎ５間のＴＤＭ伝送路、Ｎ５−Ｎ６間のＴＤＭ伝送路を設定する。即ち、ＴＤＭ伝送路組み合わせ候補作成部１２８は、｛Ｎ１−Ｎ３、Ｎ３−Ｎ５、Ｎ５−Ｎ６｝というＴＤＭ伝送路の組み合わせ候補を作成する。

ここで、ＴＤＭ伝送路の組み合わせに含まれるＴＤＭ伝送路の一部または全部は、互いに重複しない。つまり、例えば、ＴＤＭ伝送路組み合わせ候補作成部１２８が、Ｎ１−Ｎ５間のＴＤＭ伝送路、Ｎ５−Ｎ３間のＴＤＭ伝送路、Ｎ３−Ｎ６間のＴＤＭ伝送路の組み合わせを作成することはない。

例えば、Ｎ１−Ｎ６間のデマンドでｋの値が３である場合、取り出されているノードはノードＮ３、ノードＮ４及びノードＮ５である。このとき、ＴＤＭ伝送路組み合わせ候補作成部１２８は、始点ノードであるノードＮ１、終点ノードであるノードＮ６、取り出されたノードＮ３、ノードＮ４及びノードＮ５を端点とするＴＤＭ伝送路の組み合わせを作成する。ＴＤＭ伝送路組み合わせ候補作成部１２８は、始点ノードであるノードＮ１、終点ノードであるノードＮ６、取り出されたノードＮ３、ノードＮ４及びノードＮ５を、デマンドの経路の始点から終点までの順にソートする。ここでは、ソート後の順は、Ｎ１、Ｎ３、Ｎ４、Ｎ５、Ｎ６である。ＴＤＭ伝送路組み合わせ候補作成部１２８は、ソートしたノードの隣り合う２つのノード間にＴＤＭ伝送路を設定する。つまり、ＴＤＭ伝送路組み合わせ候補作成部１２８は、Ｎ１−Ｎ３間のＴＤＭ伝送路、Ｎ３−Ｎ４間のＴＤＭ伝送路、Ｎ４−Ｎ５間のＴＤＭ伝送路、Ｎ５−Ｎ６間のＴＤＭ伝送路を設定する。即ち、ＴＤＭ伝送路組み合わせ候補作成部１２８は、というＴＤＭ伝送路の組み合わせ候補を作成する。

Ｎ１−Ｎ６間のデマンドでｋの値が１である場合、取り出されているノードはノードＮ３である。このとき、ＴＤＭ伝送路組み合わせ候補作成部１２８は、始点ノードであるノードＮ１、終点ノードであるノードＮ６、取り出されたノードＮ３を端点とするＴＤＭ伝送路の組み合わせを作成する。ＴＤＭ伝送路組み合わせ候補作成部１２８は、始点ノードであるノードＮ１、終点ノードであるノードＮ６、取り出されたノードＮ３を、デマンドの経路の始点から終点までの順にソートする。ここでは、ソート後の順は、Ｎ１、Ｎ３、Ｎ６である。ＴＤＭ伝送路組み合わせ候補作成部１２８は、ソートしたノードの隣り合う
２つのノード間にＴＤＭ伝送路を設定する。つまり、ＴＤＭ伝送路組み合わせ候補作成部１２８は、Ｎ１−Ｎ３間のＴＤＭ伝送路、Ｎ３−Ｎ６間のＴＤＭ伝送路を設定する。即ち、ＴＤＭ伝送路組み合わせ候補作成部１２８は、｛Ｎ１−Ｎ３、Ｎ３−Ｎ６｝というＴＤＭ伝送路の組み合わせ候補を作成する。

Ｎ１−Ｎ６間のデマンドでｋの値が０である場合、取り出されているノードはない。このとき、ＴＤＭ伝送路組み合わせ候補作成部１２８は、始点ノードであるノードＮ１、終点ノードであるノードＮ６を端点とするＴＤＭ伝送路の組み合わせを作成する。ＴＤＭ伝送路組み合わせ候補作成部１２８は、Ｎ１−Ｎ６間のＴＤＭ伝送路を設定する。即ち、ＴＤＭ伝送路組み合わせ候補作成部１２８は、｛Ｎ１−Ｎ６｝というＴＤＭ伝送路の組み合わせ候補を作成する。

図２１は、Ｎ１−Ｎ６間のデマンドの４つのＴＤＭ伝送路の組み合わせ候補の例を示す図である。図２１の例では、Ｎ１−Ｎ６間に、｛Ｎ１−Ｎ６｝、｛Ｎ１−Ｎ３、Ｎ３−Ｎ６｝、｛Ｎ１−Ｎ３、Ｎ３−Ｎ５、Ｎ５−Ｎ６｝、｛Ｎ１−Ｎ３、Ｎ３−Ｎ４、Ｎ４−Ｎ５、Ｎ５−Ｎ６｝という４つのＴＤＭ伝送路の組み合わせ候補が設定されている。

始点ノード及び終点ノードが同一であり、かつ、ｋの値が同一である２つのデマンドについては、生成されるＴＤＭ伝送路の組み合わせ候補が同一であるので、これらのデマンドのＴＤＭ伝送路の組み合わせ候補は、まとめて作成されてもよい。

ステップＳ２１０では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、処理中のデマンドについて、ｋ値リストからすべてのｋの値を取り出して、ＴＤＭ伝送路組み合わせ候補を作成したか否かを確認する。処理中のデマンドについてｋ値リストからすべてのｋの値を取り出した場合（Ｓ２１０；ＹＥＳ）、処理がステップＳ２１１に進む。処理中のデマンドについてｋ値リストからすべてのｋの値を取り出していない場合（Ｓ２１０；ＮＯ）、処理がステップＳ２０８に戻る。

ステップＳ２１１では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、すべてのデマンドを取り出して一連の処理を行ったかを確認する。まだ未処理のデマンドが残っている場合（Ｓ２１１；ＮＯ）、処理がステップＳ２０６に戻る。すべてのデマンドを取り出して一連の処理を行った場合（Ｓ２１１；ＹＥＳ）、処理が終了する。

ネットワーク設計装置１００は、取得したトポロジ（図７）におけるデマンド（図１１）について、ＴＤＭ伝送路の組み合わせ候補を生成し、生成されたＴＤＭ伝送路の組み合わせ候補に基づいて、各デマンドを収容するＴＤＭ伝送路の組み合わせを選択する。

図２２は、生成されるＴＤＭ伝送路組み合わせ候補の例を示す図である。図２２のように、デマンド毎にＴＤＭ伝送路の組み合わせ候補が生成される。ＴＤＭ伝送路の組み合わせ候補の数は、各デマンドのｋの値の数と同じである。例えば、Ｎ１−Ｎ６間のデマンドでは、ｋの値の数はｋ＝０，１，２，３の４つであるから、ＴＤＭ伝送路の組み合わせ候補の数は４つである。

上記の動作例に基づくネットワーク設計装置１００によれば、ノードの次数、ノードで終端されるデマンドの本数、ノードを通過するデマンドの本数を用いて最適解になる可能性が高いＴＤＭ伝送路の組み合わせに絞ってネットワーク設計を行うことができる。

（変形例１）
次に変形例１について説明する。変形例１は、上記の動作例との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。

上記の動作例では、デマンド毎にデマンドの始点ノード及び終点ノードを除く経路上の途中のノードの中からあらかじめ指定された数のノードが取り出された。変形例１では、取り出す途中のノードの個数を順次増加させながら、経路上の途中のノードの数を超えるか選択不可のノードが含まれた時点で処理が終了する。

図２３、図２４、図２５は、変形例１のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例を示す図である。図２３の「Ｂ１」、「Ｂ２」は、それぞれ、図２４の「Ｂ１」、「Ｂ２」と接続する。図２４の「Ｂ３」、「Ｂ４」、「Ｂ５」、「Ｂ６」は、それぞれ、図２５の「Ｂ３」、「Ｂ４」、「Ｂ５」、「Ｂ６」と接続する。

図２３のステップＳ３０１からステップＳ３０４の動作は、上記の動作例の図１２のステップＳ２０１からステップＳ２０４の動作と同様である。

ステップＳ３０５では、ノード順序リスト生成部１２４は、ステップＳ３０４で生成したノードの順序リストにおいて、終端デマンド本数が０本であるノードを、順序の最後に移動する。さらに、ノード順序リスト生成部１２４は、最後に移動したノードに選択不可のフラグを付与する。

図２６は、ノードの選択不可のフラグの例を示す図である。図２６の例では、ノードごとに「true」又は「false」が付与される。ここでは、「true」が選択可能を意味し、「false」が選択不可を意味する。

ステップＳ３０６からステップＳ３０７の動作は、上記の動作例のステップＳ２０６からステップＳ２０７の動作と同様である。

ステップＳ３０８では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、変数ｋを用意し、変数ｋに初期値０を代入する。

ステップＳ３０９では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、処理中のデマンドについて、ソート済の途中ノードリストの上位からｋ個のノードを取り出す。ＴＤＭ伝送路組み合わせ候補作成部１２８は、ｋの値が０であるときは、ソート済の途中ノードリストからノードを取り出さない。ｋ値リストは、デマンド毎に取り得るｋの値を示すリストである。例えば、Ｎ１−Ｎ６のデマンドについてｋの値が２である場合、取り出されるノードは、図１９の上位２つである、ノードＮ３及びノードＮ５である。

ステップＳ３１０では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、ステップＳ３０９で取り出したノードの中に選択不可のフラグが付与されているノードが含まれているか否かを確認する。選択不可のフラグが付与されているノードが含まれている場合（Ｓ３１０；ＹＥＳ）、処理がステップＳ３１４に進む。選択不可のフラグが付与されているノードが含まれていない場合（Ｓ３１０；ＮＯ）、処理がステップＳ３１１に進む。

ステップＳ３１１では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、処理中のデマンドについて、始点ノード、終点ノード、及び、ステップＳ３０９で取り出したノードを端点として、ＴＤＭ伝送路の組み合わせを生成する。ＴＤＭ伝送路組み合わせ候補作成部１２８は、ステップＳ３０９でノードを取り出さなかった場合、始点ノード及び終点ノードを端点とするＴＤＭ伝送路をＴＤＭ伝送路の組み合わせとして生成する。

ステップＳ３１２では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、変数ｋにｋ＋１を代入する。

ステップＳ３１３では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、処理中のデマンドについて、変数ｋが経路の途中のノード数を超えているか否かを確認する。処理中のデマンドについて、変数ｋが経路の途中のノード数を超えている場合（Ｓ３１３；ＹＥＳ）、処理がステップＳ３１４に進む。処理中のデマンドについて、変数ｋが経路の途中のノード数を超えていない場合（Ｓ３１３；ＮＯ）、処理がステップＳ３０９に戻る。

ステップＳ３１４では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、すべてのデマンドを取り出して一連の処理を行ったかを確認する。まだ未処理のデマンドが残っている場合（Ｓ３１４；ＮＯ）、処理がステップＳ３０６に戻る。すべてのデマンドを取り出して一連の処理を行った場合（Ｓ３１４；ＹＥＳ）、処理が終了する。

上記の変形例１に基づくネットワーク設計装置１００によれば、選択するノードの個数を自動的に増加して選択できるようにすることで、あらかじめ取り出すノードの数を決めなくてもよい。

（変形例２）
次に変形例２について説明する。変形例２は、上記の動作例、変形例１との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。

変形例２では、ノードの次数および終端するデマンドの本数と通過するデマンドの本数との合計がともに等しいノードが存在する場合の処理が、上記の動作例に追加される。

図２７、図２８、図２９は、変形例２のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例を示す図である。図２７の「Ｃ１」、「Ｃ２」は、それぞれ、図２８の「Ｃ１」、「Ｃ２」と接続する。図２８の「Ｃ３」、「Ｃ４」、「Ｃ５」は、それぞれ、図２９の「Ｃ３」、「Ｃ４」、「Ｃ５」と接続する。

図２７のステップＳ４０１からステップＳ４０７までの動作は、上記の動作例の図１２のステップＳ２０１からステップＳ２０７までの動作と同様である。

ステップＳ４０８では、途中ノードリスト生成部１２６は、同位のノードをグループ化する。ここで、同位のノードとは、ノードの次数及びスコアが共に等しいノードである。グループ化する方法として、例えば、order[i][j]のような二次元配列を用意する。そし
て、order[0][m]には順に並べた１番目のノードと、そのノードと同位のものが入れられ
る。order[1][n]には順に並べた１番目のノードと同位のものを除いた２番目のノードと
、そのノードと同位のものが入れられる。例えば、あるデマンドの始点ノード及び終点ノードを除いた経路の途中のノードがＮ１、Ｎ２、Ｎ３、Ｎ４、Ｎ５、Ｎ６、Ｎ７とあり、次数とスコアで並べた順序もこの順として、Ｎ２とＮ３、Ｎ５とＮ６とＮ７が同位の場合、次のようにする。

order[0][0] = N1
order[1][0] = N2、order[1][1] = N3
order[2][0] = N4
order[3][0] = N5、order[3][1] = N6、order[3][2] = N7
このようにすると、ある数iについてorder[i][j]という配列の要素の数が１であれば、order[i][0]と同位のものはなく、２以上であればorder[i][j]の配列の要素を参照することで、order[i][0]と同位のノードのグループを得ることができる。

ステップＳ４０９では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、処理中のデマン
ドについて、ｋ値リストから１つのｋの値を取り出し、ソート済の途中ノードリストの上位からｋ個のノードを取り出す。ＴＤＭ伝送路組み合わせ候補作成部１２８は、ｋ番目のノードが、同位のノードを有するか否かを確認する。例えば、前述の例でｋ＝２の場合、順序に従ってとればＮ１、Ｎ２が取り出される。ノードＮ２には、二次元配列変数order
を調べると同位のノードとしてノードＮ３があることがわかる。ノードをｋ（＝２）個取り出した中にノードＮ２と同位のノード、すなわちorder[1][j]という配列に含まれるも
のは１つであるため、ｋ番目のノードと同位のノードの数ｍは1となる。そこで、ＴＤＭ
伝送路組み合わせ候補作成部１２８は、order[1][j]から１個のノードの取り出し方を順
に行い、それに、上位のｋ−ｍ個のノード（ここではノードＮ１）を加えたものを、ｋ個のノードとして取り出す。この場合は、[N2, N3]の中から１つとる取り出し方なので、[N2]と[N3]があり、ｋ（＝２）個取り出す取り出し方は[N1, N2]と[N1, N3]の２つの組み合わせになる。例えば、ｋ＝３の場合は、ノードＮ３と同位のノードとしてノードＮ２があるが、[N2, N3]の中から２つとる取り出し方は[N2, N3]である。よって、ｋ＝３の場合に取り出されるノードは[N1, N2, N3]となる。同様に、ｋ＝４の場合は[N1, N2, N3, N4]である。ｋ＝５の場合は、ノードＮ５と同位のノードとしてノードＮ６及びノードＮ７があるため、ｋ＝５で取り出されるノードは[N1, N2, N3, N4, N5]、[N1, N2, N3, N4, N6]、[N1, N2, N3, N4, N7]の３通りとなる。ｋ＝６の場合、ノードＮ６と同位のノードはｋ＝６で選択した中にノードＮ５とノードＮ６の２つが含まれるため、[N5, N6, N7]の中から２つを選ぶ組み合わせになる。この場合ｍ＝２で、ｋ−ｍ個のノード、すなわち[N1, N2,
N3, N4]に、[N5, N6, N7]の中から２つを選ぶ組み合わせを加えたものが取り出されるノードになる。この場合は[N1, N2, N3, N4, N5, N6]、[N1, N2, N3, N4, N5, N7]、[N1, N2, N3, N4, N6, N7]の３通りである。

ステップＳ４１０では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、処理中のデマンドについて、始点ノード、終点ノード、及び、ステップＳ４０９で取り出したノードを端点として、ＴＤＭ伝送路の組み合わせを生成する。ＴＤＭ伝送路組み合わせ候補作成部１２８は、ステップＳ４０９でノードを取り出さなかった場合、始点ノード及び終点ノードを端点とするＴＤＭ伝送路をＴＤＭ伝送路の組み合わせとして生成する。ステップＳ４０９で、複数の組み合わせのノードが取り出されている場合、ＴＤＭ伝送路組み合わせ候補作成部１２８は、取り出されたすべての組み合わせについて、ＴＤＭ伝送路の組み合わせを生成する。

ステップＳ４１１では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、処理中のデマンドについて、ｋ値リストからすべてのｋの値を取り出して、ＴＤＭ伝送路組み合わせ候補を作成したか否かを確認する。処理中のデマンドについてｋ値リストからすべてのｋの値を取り出した場合（Ｓ４１１；ＹＥＳ）、処理がステップＳ４１２に進む。処理中のデマンドについてｋ値リストからすべてのｋの値を取り出していない場合（Ｓ４１１；ＮＯ）、処理がステップＳ４０９に戻る。

ステップＳ４１２では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、すべてのデマンドを取り出して一連の処理を行ったかを確認する。まだ未処理のデマンドが残っている場合（Ｓ４１２；ＮＯ）、処理がステップＳ４０６に戻る。すべてのデマンドを取り出して一連の処理を行った場合（Ｓ４１２；ＹＥＳ）、処理が終了する。

変形例２に基づくネットワーク設計装置１００によれば、ノードの次数、終端されるデマンドの本数、通過するデマンドの本数が同一のノードであった場合、これらを適切に組み合わせたＴＤＭ伝送路組み合わせ候補を生成することができる。

（変形例３）
次に変形例３について説明する。変形例３は、上記の動作例、変形例１、２との共通点
を有する。従って、主として相違点について説明し、共通点については、説明を省略する。

変形例３では、上記の動作例のノードの次数とスコアとからノードの順序リストを作成する部分が異なる。変形例３では、ノードの次数とスコアがともに等しいノードが複数あった場合に、さらに終端されるデマンドの本数によって順序がつけられる。スコアは、終端されるデマンドの本数と通過するデマンドの本数の合計である。そのため、スコアが同じであれば、終端されるデマンドが多いほど通過するデマンドは少なくなる。この場合、終端されるデマンドが多いノードほど、当該ノードを端点とするＴＤＭ伝送路が多く必要になり、さらに通過するデマンドが少ないので、そのノードで終端されるデマンドとともにそのノードに端点のあるＴＤＭ伝送路に収容される確率が高くなる。このため終端されるデマンドが多いノードほど順序をより上位に置くことで、当該ノードを端点とするＴＤＭ伝送路を含むＴＤＭ伝送路の組み合わせが生成されるようにする。

図３０は、上記の動作例におけるノードの順序リスト作成の際の並べ替えの動作フローの例を示す図である。図３０の動作フローは、２つのノード（ノードＮａ及びノードＮｂ）について条件を比較して、順序を入れ替えるか否かを判定する動作フローである。最初の段階で、ノードＮａは、ノードＮｂより上位のノードである。また、deg[N]はノードＮの次数、score[N]はノードＮのスコアである。

ステップＳ１００１では、ノード順序リスト生成部１２４は、deg[Na]とdeg[Nb]とを比較する。deg[Na]がdeg[Nb]より小さい場合（Ｓ１００１；ＹＥＳ）、処理がステップＳ１００４に進む。deg[Na]がdeg[Nb]以上である場合（Ｓ１００１；ＮＯ）、処理がステップＳ１００２に進む。

ステップＳ１００２では、ノード順序リスト生成部１２４は、deg[Na]とdeg[Nb]とが等しいか否かを判定する。deg[Na]がdeg[Nb]と等しい場合（Ｓ１００２；ＹＥＳ）、処理がステップＳ１００３に進む。deg[Na]がdeg[Nb]と等しくない場合（Ｓ１００２；ＮＯ）、すなわち、deg[Na]がdeg[Nb]より大きい場合、ノード順序リスト生成部１２４は、ノードＮａ及びノードＮｂの順序を入れ替えずに処理を終了する。

ステップＳ１００３では、ノード順序リスト生成部１２４は、score[Na]とscore[Nb]とを比較する。score[Na]がscore[Nb]より小さい場合（Ｓ１００３；ＹＥＳ）、処理がステップＳ１００４に進む。score[Na]がscore[Nb]以上である場合（Ｓ１００３；ＮＯ）、ノードＮａ及びノードＮｂの順序を入れ替えずに処理が終了する。

ステップＳ１００４では、ノード順序リスト生成部１２４は、ノード順序リスト生成部１２４は、ノードＮａ及びノードＮｂの順序を入れ替えて処理を終了する。

図３１は、変形例３におけるノードの順序リスト作成の際の並べ替えの動作フローの例を示す図である。図３１の動作フローは、２つのノード（ノードＮａ及びノードＮｂ）について条件を比較して、順序を入れ替えるか否かを判定する動作フローである。最初の段階で、ノードＮａは、ノードＮｂより上位のノードである。また、deg[N]はノードＮの次数、score[N]はノードＮのスコア、Nterm[N]はノードＮで終端されるデマンドの本数である。

ステップＳ２００１では、ノード順序リスト生成部１２４は、deg[Na]とdeg[Nb]とを比較する。deg[Na]がdeg[Nb]より小さい場合（Ｓ２００１；ＹＥＳ）、処理がステップＳ２００６に進む。deg[Na]がdeg[Nb]以上である場合（Ｓ２００１；ＮＯ）、処理がステップＳ２００２に進む。

ステップＳ２００２では、ノード順序リスト生成部１２４は、deg[Na]とdeg[Nb]とが等しいか否かを判定する。deg[Na]がdeg[Nb]と等しい場合（Ｓ２００２；ＹＥＳ）、処理がステップＳ２００３に進む。deg[Na]がdeg[Nb]と等しくない場合（Ｓ２００２；ＮＯ）、すなわち、deg[Na]がdeg[Nb]より大きい場合、ノード順序リスト生成部１２４は、ノードＮａ及びノードＮｂの順序を入れ替えずに処理を終了する。

ステップＳ２００３では、ノード順序リスト生成部１２４は、score[Na]とscore[Nb]とを比較する。score[Na]がscore[Nb]より小さい場合（Ｓ２００３；ＹＥＳ）、処理がステップＳ２００６に進む。score[Na]がscore[Nb]以上である場合（Ｓ２００３；ＮＯ）、処理がステップＳ２００４に進む。

ステップＳ２００４では、ノード順序リスト生成部１２４は、score[Na]とscore[Nb]とが等しいか否かを判定する。score[Na]がscore[Nb]と等しい場合（Ｓ２００４；ＹＥＳ）、処理がステップＳ２００５に進む。score[Na]がscore[Nb]と等しくない場合（Ｓ２００４；ＮＯ）、すなわち、score [Na]がscore[Nb]より大きい場合、ノード順序リスト生成
部１２４は、ノードＮａ及びノードＮｂの順序を入れ替えずに処理を終了する。

ステップＳ２００５では、ノード順序リスト生成部１２４は、Nterm[Na]とNterm[Nb]とを比較する。Nterm[Na]がNterm[Nb]より小さい場合（Ｓ２００５；ＹＥＳ）、処理がステップＳ２００６に進む。Nterm[Na]がNterm[Nb]以上である場合（Ｓ２００５；ＮＯ）、ノードＮａ及びノードＮｂの順序を入れ替えずに処理が終了する。

ステップＳ２００６では、ノード順序リスト生成部１２４は、ノード順序リスト生成部１２４は、ノードＮａ及びノードＮｂの順序を入れ替えて処理を終了する。

変形例３に基づくネットワーク設計装置１００によれば、ノードの次数及び終端されるデマンドの本数と通過するデマンドの本数との合計が同一のノードでも、終端されるデマンドの本数が多いものを優先することで、より適切な組み合わせ候補を選択できる。

（変形例４）
次に変形例４について説明する。変形例４は、上記の動作例、変形例１−３との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。

変形例４では、上記の動作例のノードの次数とスコアとからノードの順序リストを作成する部分が異なる。変形例４では、ノードの次数とスコアとノードで終端されるデマンドの本数が同じ場合に、さらに通過するデマンドの始点ノード及び終点ノードの組み合わせの数によって順序が決定される。極端な場合として、通過するすべてのデマンドが同一の始点ノード及び終点ノードを有する場合、通過するデマンドの始点ノードと終点ノードとの間にＴＤＭ伝送路を設定して収容する場合が最適解になる可能性が高くなる。この場合はそのノードを端点とするＴＤＭ伝送路を生成しても意味がないため、順序を下げる。例えば、あるノードを通過するデマンドとして、Ｎ１−Ｎ５のデマンドが４本、Ｎ２−Ｎ６のデマンドが８本、Ｎ１−Ｎ６のデマンドが４本あった場合、始点ノード及び終点ノード対の数は、Ｎ１−Ｎ５、Ｎ２−Ｎ６、Ｎ１−Ｎ６の３つというように数えられる。通過するデマンドの本数が同じであれば、この始点ノード及び終点ノード対の数が多いほど始点ノード及び終点ノードがともに同じデマンドの本数の平均値は低くなり、デマンドの始点ノードと終点ノードと間にＴＤＭ伝送路を設定して収容する確率は低くなる。

図３２及び図３３は、変形例４におけるノードの順序リスト作成の際の並べ替えの動作
フローの例を示す図である。図３２の「Ｗ１」、「Ｗ２」、「Ｗ３」は、それぞれ、図３３の「Ｗ１」、「Ｗ２」、「Ｗ３」と接続する。図３２及び図３３の動作フローは、２つのノード（ノードＮａ及びノードＮｂ）について条件を比較して、順序を入れ替えるか否かを判定する動作フローである。最初の段階で、ノードＮａは、ノードＮｂより上位のノードである。また、deg[N]はノードＮの次数、score[N]はノードＮのスコア、Nterm[N]はノードＮで終端されるデマンドの本数、Ntp[N]はノードＮを通過するデマンドの始点ノード及び終点ノード対の数である。

図３２のステップＳ３００１からステップＳ３００４の動作は、上記の変形例３の図３１のステップＳ２００１からステップＳ２００４の動作と同様である。

ステップＳ３００５では、ノード順序リスト生成部１２４は、Nterm[Na]とNterm[Nb]とを比較する。Nterm[Na]がNterm [Nb]より小さい場合（Ｓ３００５；ＹＥＳ）、処理がス
テップＳ３００８に進む。Nterm [Na]がNterm [Nb]以上である場合（Ｓ３００５；ＮＯ）、ノードＮａ及びノードＮｂの順序を入れ替えずに処理が終了する。

ステップＳ３００６では、ノード順序リスト生成部１２４は、Nterm[Na]とNterm[Nb]とが等しいか否かを判定する。Nterm[Na]がNterm[Nb]と等しい場合（Ｓ３００６；ＹＥＳ）、処理がステップＳ３００７に進む。Nterm[Na]がNterm[Nb]と等しくない場合（Ｓ２００６；ＮＯ）、すなわち、Nterm[Na]がNterm[Nb]より大きい場合、ノード順序リスト生成部１２４は、ノードＮａ及びノードＮｂの順序を入れ替えずに処理を終了する。

ステップＳ３００７では、ノード順序リスト生成部１２４は、Ntp[Na]とNtp[Nb]とを比較する。Ntp[Na]がNtp[Nb]より小さい場合（Ｓ３００７；ＹＥＳ）、処理がステップＳ３００８に進む。Ntp[Na]がNtp[Nb]以上である場合（Ｓ３００７；ＮＯ）、ノードＮａ及びノードＮｂの順序を入れ替えずに処理が終了する。

ステップＳ３００８では、ノード順序リスト生成部１２４は、ノード順序リスト生成部１２４は、ノードＮａ及びノードＮｂの順序を入れ替えて処理を終了する。

変形例４に基づくネットワーク設計装置１００によれば、ノードの次数及び終端されるデマンドの本数と通過するデマンドの本数との合計が同一のノードでも、始点ノード及び終点ノード対が多いものを優先することで、より適切な組み合わせ候補を選択できる。

（変形例５）
次に変形例５について説明する。変形例５は、上記の動作例、変形例１−４との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。

変形例５では、上記の動作例のノードの次数とスコアからノードの順序リストを作成する部分が異なる。変形例５では、ノードの次数とスコアとノードで終端されるデマンドの本数が同じ場合に、さらに通過するデマンドの中で始点ノード及び終点ノードが同一のデマンドの本数の最も大きいものの値によって順序が決定される。変形例５は変形例４と同様の考え方で、通過するデマンドの中に同一の始点ノード及び終点ノードを有するデマンドが多く入っているものほど順位を下位に設定する。

図３４及び図３５は、変形例５におけるノードの順序リスト作成の際の並べ替えの動作フローの例を示す図である。図３４の「Ｘ１」、「Ｘ２」、「Ｘ３」は、それぞれ、図３５の「Ｘ１」、「Ｘ２」、「Ｘ３」と接続する。図３４及び図３５の動作フローは、２つのノード（ノードＮａ及びノードＮｂ）について条件を比較して、順序を入れ替えるか否
かを判定する動作フローである。最初の段階で、ノードＮａは、ノードＮｂより上位のノードである。また、deg[N]はノードＮの次数、score[N]はノードＮのスコア、Nterm[N]はノードＮで終端されるデマンドの本数、Nmaxst[N]はノードＮを通過するデマンドについ
て、始点ノード及び終点ノードがともに同じデマンドの本数の最も多いものの値である。例えば、ノードＮを通過するデマンドとしてＮ１−Ｎ５のデマンドが４本、Ｎ２−Ｎ６のデマンドが８本、Ｎ１−Ｎ６のデマンドが４本あった場合、始点ノード及び終点ノードが同じデマンドの本数が最も多いのはＮ２−Ｎ６のデマンドであるため、Nmaxst[N]=8とな
る。

図３４及び図３５のステップＳ４００１からステップＳ４００６の動作は、上記の変形例４の図３２及び図３３のステップＳ３００１からステップＳ３００６の動作と同様である。

ステップＳ４００７では、ノード順序リスト生成部１２４は、Nmaxst[Na]とNmaxst[Nb]とを比較する。Nmaxst[Na]がNmaxst[Nb]より大きい場合（Ｓ４００７；ＹＥＳ）、処理がステップＳ４００８に進む。Nmaxst[Na]がNmaxst[Nb]以下である場合（Ｓ４００７；ＮＯ）、ノードＮａ及びノードＮｂの順序を入れ替えずに処理が終了する。

ステップＳ４００８では、ノード順序リスト生成部１２４は、ノード順序リスト生成部１２４は、ノードＮａ及びノードＮｂの順序を入れ替えて処理を終了する。

変形例５に基づくネットワーク設計装置１００によれば、ノードの次数及びスコアが同一のノードでも、通過するデマンドの始点ノード及び終点ノードが一致するデマンドが少ないものを優先することで、より適切なＴＤＭ伝送路の組み合わせ候補を選択できる。

（変形例６）
次に変形例６について説明する。変形例６は、上記の動作例、変形例１−５との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。

変形例６では、上記の動作例のノードの次数とスコアからノードの順序リストを作成する部分が異なる。変形例６では、ノードの次数とスコアとノードで終端されるデマンドの本数が同じ場合に、さらに通過するデマンドの中で始点ノード及び終点ノードが同一のデマンドの本数の平均値によって順序が決定される。変形例６は変形例４、５と同様の考え方で、通過するデマンドの中に同一の始点ノード及び終点ノードを有するデマンドが多く入っているものほど順位を下位に設定する。

図３６及び図３７は、変形例６におけるノードの順序リスト作成の際の並べ替えの動作フローの例を示す図である。図３６の「Ｙ１」、「Ｙ２」、「Ｙ３」は、それぞれ、図３７の「Ｙ１」、「Ｙ２」、「Ｙ３」と接続する。図３６及び図３７の動作フローは、２つのノード（ノードＮａ及びノードＮｂ）について条件を比較して、順序を入れ替えるか否かを判定する動作フローである。最初の段階で、ノードＮａは、ノードＮｂより上位のノードである。また、deg[N]はノードＮの次数、score[N]はノードＮのスコア、Nterm[N]はノードＮで終端されるデマンドの本数、Nmeanst[N]はノードＮを通過するデマンドについて、始点ノード及び終点ノードがともに同じデマンドの本数の平均値である。例えば、ノードＮを通過するデマンドとしてＮ１−Ｎ５のデマンドが４本、Ｎ２−Ｎ６のデマンドが８本、Ｎ１−Ｎ６のデマンドが４本あった場合、始点ノード及び終点ノードが同じデマンドの本数の平均値が５．３であるため、Nmaxst[N]=5.3となる。

図３６及び図３７のステップＳ５００１からステップＳ５００６の動作は、上記の変形
例４の図３２及び図３３のステップＳ３００１からステップＳ３００６の動作と同様である。

ステップＳ５００７では、ノード順序リスト生成部１２４は、Nmeanst[Na]とNmeanst[Nb]とを比較する。Nmeanst[Na]がNmeanst[Nb]より大きい場合（Ｓ５００７；ＹＥＳ）、処理がステップＳ４００８に進む。Nmeanst[Na]がNmeanst[Nb]以下である場合（Ｓ５００７；ＮＯ）、ノードＮａ及びノードＮｂの順序を入れ替えずに処理が終了する。

ステップＳ５００８では、ノード順序リスト生成部１２４は、ノード順序リスト生成部１２４は、ノードＮａ及びノードＮｂの順序を入れ替えて処理を終了する。

変形例６に基づくネットワーク設計装置１００によれば、ノードの次数及びスコアが同一のノードでも、通過するデマンドの始点ノード及び終点ノードが一致するデマンドの数の平均値が小さいものを優先することで、適切なＴＤＭ伝送路の組み合わせ候補を選択できる。

（変形例７）
次に変形例７について説明する。変形例７は、上記の動作例、変形例１−６との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。

変形例７では、上記の動作例のノードの次数とスコアからノードの順序リストを作成する部分が異なる。変形例７では、ノードの次数とスコアとノードで終端されるデマンドの本数が同じ場合に、さらに通過するデマンドの中で始点ノード及び終点ノードが同一のデマンドの本数の合計値と、通過するデマンドの合計値との比によって順序が決定される。変形例６は変形例４−６と同様の考え方で、通過するデマンドの中に同一の始点ノード及び終点ノードを有するデマンドが多く入っているものほど順位を下位に設定する。

図３８及び図３９は、変形例７におけるノードの順序リスト作成の際の並べ替えの動作フローの例を示す図である。図３８の「Ｚ１」、「Ｚ２」、「Ｚ３」は、それぞれ、図３９の「Ｚ１」、「Ｚ２」、「Ｚ３」と接続する。図３８及び図３９の動作フローは、２つのノード（ノードＮａ及びノードＮｂ）について条件を比較して、順序を入れ替えるか否かを判定する動作フローである。最初の段階で、ノードＮａは、ノードＮｂより上位のノードである。また、deg[N]はノードＮの次数、score[N]はノードＮのスコア、Nterm[N]はノードＮで終端されるデマンドの本数である。Ntotst[N]はノードＮを通過するデマンド
について、始点ノード及び終点ノードがともに同じデマンドの本数の合計値である。例えば、ノードＮを通過するデマンドとして、Ｎ１−Ｎ４のデマンドが１本、Ｎ１−Ｎ５のデマンドが４本、Ｎ２−Ｎ６のデマンドが１本、Ｎ１−Ｎ６のデマンドが２本あった場合、始点ノード及び終点ノードが同じデマンドの本数の合計値が６であるため、Ntotst[N]=6
となる。また、Nthru[N]はノードＮを通過するデマンドの本数の合計値で、前述の例の場合はNthru[N]=8となる。そして、Ntotst[N]とNthru[N]の比はNtotst[N]／Nthru[N]であり、前述の例の場合は6/8=0.75となる。

図３８及び図３９のステップＳ６００１からステップＳ６００６の動作は、上記の変形例４の図３２及び図３３のステップＳ３００１からステップＳ３００６の動作と同様である。

ステップＳ６００７では、ノード順序リスト生成部１２４は、Ntotst[Na]／Nthru[Na]
とNtotst[Nb]／Nthru[Nb]とを比較する。Ntotst[Na]／Nthru[Na]がNtotst[Nb]／Nthru[Nb]より小さい場合（Ｓ６００７；ＹＥＳ）、処理がステップＳ６００８に進む。Ntotst[Na
]／Nthru[Na]がNtotst[Nb]／Nthru[Nb]以上である場合（Ｓ６００７；ＮＯ）、ノードＮ
ａ及びノードＮｂの順序を入れ替えずに処理が終了する。

ステップＳ６００８では、ノード順序リスト生成部１２４は、ノード順序リスト生成部１２４は、ノードＮａ及びノードＮｂの順序を入れ替えて処理を終了する。

変形例７に基づくネットワーク設計装置１００によれば、ノードの次数及びスコアが同一のノードでも、所定の比が大きいものを優先することで、より適切なＴＤＭ伝送路の組み合わせ候補を選択できる。

（変形例８）
次に変形例８について説明する。変形例８は、上記の動作例、変形例１−７との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。

上記の動作例では、最初にネットワークの全ノードについてノードの次数及びスコアを計算していた。変形例８では、デマンド毎に始点ノード及び終点ノードを除く経路の途中のノードについてノードの次数とスコアを計算する。デマンドがネットワーク内の一部のノードしか通らない場合、すべてのノードについて次数とスコアを計算することは計算リソースを無駄に使用することになる。このため、変形例８では、デマンドが通らないノードについて計算がされないようにする。また、デマンドがネットワーク全体に存在し、デマンドの本数が多い場合、上記の動作例のように、最初にすべてのノードについて次数とスコアを計算することは効率がよい。即ち、変形例８は、ネットワークの大きさに対して、デマンドの本数が少ない場合に有効である。

図４０、図４１は、変形例８のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例を示す図である。図４０の「Ｄ１」、「Ｄ２」は、それぞれ、図４１の「Ｄ１」、「Ｄ２」と接続する。

ステップＳ５０１では、途中ノードリスト生成部１２６は、デマンド毎に途中ノードリストを生成する。途中ノードリスト生成部１２６は、デマンド情報から１つのデマンド（処理中のデマンドとする）を取り出し、当該デマンドの経路の途中のノードを取り出す。デマンドの経路の途中のノードは、当該デマンドに通過されるノードである。例えば、途中ノードリスト生成部１２６は、Ｎ１−Ｎ６間のデマンドに対して、当該デマンドの経路の途中のノードである、ノードＮ２、ノードＮ３、ノードＮ４、ノードＮ５を取り出す。途中ノードリスト生成部１２６は、取り出したノードを、途中ノードリストとして、メモリ１４０に格納する。途中ノードリストは、デマンド毎に生成される。

ステップＳ５０２では、ノード次数スコア計算部１２２は、ステップＳ５０１で生成した途中ノードリストに含まれるノードに対して、ノード毎に、終端されるデマンドの本数および通過するデマンドの本数をカウントする。ノード次数スコア計算部１２２は、メモリ１４０から、途中ノードリストに含まれるノード及びデマンド情報に含まれるデマンドを抽出する。ノード次数スコア計算部１２２は、途中ノードリストに含まれる各ノードについて、当該ノードで終端されるデマンドの本数、及び、当該ノードを通過するデマンドの本数を数える。終端されるデマンドの本数は、途中ノードリストに含まれる各ノードについて、図１１に含まれるデマンドの始点ノード又は終点ノードに当該ノードが含まれるデマンドの本数の和を求めればよい。

ステップＳ５０３からステップＳ５０６までの動作は、図１２のステップＳ２０２からステップＳ２０５までの動作と同様である。

また、ステップＳ５０７からステップＳ５１０までの動作は、図１３のステップＳ２０８からステップＳ２１１までの動作と同様である。ただし、ステップＳ５１０において、まだ未処理のデマンドが残っている場合（Ｓ５１０；ＮＯ）、処理がステップＳ５０１に戻る。

変形例８に基づくネットワーク設計装置１００によれば、各デマンドの始点ノードと終点ノードとを除く経路上の途中ノードについて、ノードの次数及びスコアを求めることで、より適切でより少ないＴＤＭ伝送路の組み合わせ候補を選択することができる。

（変形例９）
次に変形例９について説明する。変形例９は、上記の動作例、変形例１−８との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。

上記の動作例では、最初にネットワークの全ノードについてノードの次数及びスコアを計算していた。変形例９では、通過するデマンドが１本以上あるノードを選び、それらについて、ノードの次数とスコアを計算し、次数とスコアによるノードの順序リストを作成する。例えば、図１０のノードＮ１、ノードＮ６、ノードＮ７、ノードＮ８のような次数が１のノードを通過するデマンドは存在しないため、これらのノードは経路の途中のノードになることはない。したがって、これらのノードについては、スコアなどが計算されなくてもよい。変形例９では、これらのノードについて、スコアが計算されないようにする。

図４２、図４３は、変形例９のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例を示す図である。図４２の「Ｅ１」は、図４３の「Ｅ１」と接続する。

ステップＳ６０１では、ノード次数スコア計算部１２２は、ノード情報に含まれるノードについて、デマンド情報を参照して、通過するデマンドが１本以上あるノードを抽出し、通過するデマンドが１本以上あるノードのリストを作成する。

ステップＳ６０２では、ノード次数スコア計算部１２２は、ステップＳ６０１で生成したリストに含まれるノードに対して、ノード毎に、終端されるデマンドの本数および通過するデマンドの本数をカウントする。ノード次数スコア計算部１２２は、メモリ１４０から、ステップＳ６０１で作成したリストに含まれるノード及びデマンド情報に含まれるデマンドを抽出する。ノード次数スコア計算部１２２は、ステップＳ６０１で作成したリストに含まれる各ノードについて、当該ノードで終端されるデマンドの本数、及び、当該ノードを通過するデマンドの本数を数える。終端されるデマンドの本数は、ステップＳ６０１で作成したリストに含まれる各ノードについて、図１１に含まれるデマンドの始点ノード又は終点ノードに当該ノードが含まれるデマンドの本数の和を求めればよい。

ステップＳ６０３からステップＳ６１２までの動作は、図１２及び図１３のステップＳ２０２からステップＳ２１１までの動作と同様である。

変形例９に基づくネットワーク設計装置１００によれば、通過するデマンドのあるノードについてノードの次数及びスコアを求めることで、より適切でより少ないＴＤＭ伝送路の組み合わせ候補を選択することができる。

（変形例１０）
次に変形例１０について説明する。変形例１０は、上記の動作例、変形例１−９との共
通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。

上記の動作例では、最初にネットワークの全ノードについてノードの次数及びスコアを計算していた。変形例１０では、通過するデマンドが１本以上あり、かつ、終端されるデマンドが一本以上あるノードが選択され、選択されたノードについてノードの次数とスコアが計算され、次数とスコアによるノードの順序リストが作成される。変形例９では終端されるデマンドが０本のノードが順序リストの最後尾に移動されるのに対し、変形例１０では、終端されるデマンドが０本のノードが順序リストに入れられない。この差異によって、変形例１０では、終端されるデマンドが１本もないノードはＴＤＭ伝送路の端点として選択されないようになる。

図４４、図４５、図４６は、変形例１０のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例を示す図である。図４４の「Ｆ１」は、図４５の「Ｆ１」と接続する。図４５の「Ｆ２」、「Ｆ３」、「Ｆ４」、「Ｆ５」は、それぞれ、図４６の「Ｆ２」、「Ｆ３」、「Ｆ４」、「Ｆ５」と接続する。

ステップＳ７０１では、ノード次数スコア計算部１２２は、ノード情報に含まれるノードについて、デマンド情報を参照して、通過するデマンドが１本以上あり、かつ、終端されるデマンドが１本以上あるノードを抽出する。ノード次数スコア計算部１２２は、抽出したノードによる、ノードのリストを作成する。

ステップＳ７０２では、ノード次数スコア計算部１２２は、ステップＳ７０１で生成したリストに含まれるノードに対して、ノード毎に、終端されるデマンドの本数および通過するデマンドの本数をカウントする。ノード次数スコア計算部１２２は、メモリ１４０から、ステップＳ７０１で作成したリストに含まれるノード及びデマンド情報に含まれるデマンドを抽出する。ノード次数スコア計算部１２２は、ステップＳ７０１で作成したリストに含まれる各ノードについて、当該ノードで終端されるデマンドの本数、及び、当該ノードを通過するデマンドの本数を数える。終端されるデマンドの本数は、ステップＳ７０１で作成したリストに含まれる各ノードについて、図１１に含まれるデマンドの始点ノード又は終点ノードに当該ノードが含まれるデマンドの本数の和を求めればよい。

ステップＳ７０３からステップＳ７０５までの動作は、図１２のステップＳ２０２からステップＳ２０４までの動作と同様である。また、ステップＳ７０６の動作は、図１２のステップＳ２０６の動作と同様である。

ステップＳ７０７では、途中ノードリスト作成部１２６は、ステップＳ７０５で作成したノード順序リストにないノードを、途中ノードリストから削除する。

ステップＳ７０８からステップＳ７０９までの動作は、図１３のステップＳ２０７からステップＳ２０８までの動作と同様である。

ステップＳ７１０では、ＴＤＭ伝送路組み合わせ候補作成部１２８は、ステップＳ７０９で取り出したｋの値が途中ノードリストのノードの数より大きいか否かを確認する。ｋの値が途中ノードリストのノードの数より大きい場合（Ｓ７１０；ＹＥＳ）、処理がＳ７１３に進む。ｋの値が途中ノードリストのノードの数より以下である場合（Ｓ７１０；ＮＯ）、処理がＳ７１１に進む。

ステップＳ７１１からステップＳ７１３までの動作は、図１３のステップＳ２０９からステップＳ２１１までの動作と同様である。

変形例１０に基づくネットワーク設計装置１００によれば、通過するデマンド及び終端されるデマンドを有するノードについてノードの次数及びスコアを求めることで、より適切でより少ないＴＤＭ伝送路の組み合わせ候補を選択することができる。

（変形例１１）
次に変形例１１について説明する。変形例１１は、上記の動作例、変形例１−１０との共通点を有する。従って、主として相違点について説明し、共通点については、説明を省略する。

変形例１１では、変形例１０の構成に追加して、スコアの値が所定値より小さいノードが除外される。スコアは、ノードで終端されるデマンドの本数とノードを通過するデマンドの本数との合計である。よって、ノードのスコアが小さい場合、当該ノードのトラフィック量は小さい。このようなノードを通過するデマンドは、あるＴＤＭ伝送路から別のＴＤＭ伝送路に乗り換えるよりも、そのノードを通過するＴＤＭ伝送路に収容されたほうがいい場合がある。このとき、そのノードに端点のあるＴＤＭ伝送路にはそのノードで終端されるデマンドだけを入れたほうがよい場合がある。変形例１１は、このような場合に、そのノードにＴＤＭ伝送路の端点がくるようなＴＤＭ伝送路の組み合わせ候補を生成しないようにするものである。

図４７、図４８、図４９は、変形例１１のＴＤＭ伝送路の組み合わせ候補の生成の動作フローの例を示す図である。図４７の「Ｇ１」は、図４８の「Ｇ１」と接続する。図４８の「Ｇ２」、「Ｇ３」、「Ｇ４」、「Ｇ５」は、それぞれ、図４９の「Ｇ２」、「Ｇ３」、「Ｇ４」、「Ｇ５」と接続する。

ステップＳ８０１からステップＳ８０３までの動作は、図４４のステップＳ７０１からステップＳ７０３までの動作と同様である。

ステップＳ８０４では、ノード次数スコア計算部１２２は、ステップＳ８０３で計算したノードのスコアが所定値未満であるノードを、ステップＳ８０１で作成したリストから削除する。ノード次数スコア計算部１２２は、ステップＳ８０１で作成したリストのノードについて、ノードのスコアと所定値とを比較し、スコアが所定値未満であるノードを、リストから削除する。

ステップＳ８０５からステップＳ８１４までの動作は、図４４、図４５及び図４６のステップＳ７０４からステップＳ７１３までの動作と同様である。

変形例１１に基づくネットワーク設計装置１００によれば、通過するデマンド及び終端されるデマンドを有するノードについて、スコアが所定値以上のものに対して、ノードの次数及びスコアを求めることで、より適切でより少ないＴＤＭ伝送路の組み合わせ候補を選択することができる。

（本実施形態の作用、効果）
ネットワーク設計装置１００は、所定の条件に基づいて、最適解となりうる可能性が高いＴＤＭ伝送路の組み合わせ候補を選択する。

ネットワーク設計装置１００は、デマンドを収容するＴＤＭ伝送路の組み合わせ候補の数が全パターンを網羅すると非常に多くなる場合でも、できるだけ解になりうるＴＤＭ伝送路の組み合わせ候補に絞ることができる。ネットワーク設計装置１００は、ＴＤＭ伝送路の組み合わせ候補を絞ることで、混合整数計画問題の解空間を小さくすることができ、
結果として混合整数計画問題の計算時間の短縮を図れ、また、少ないメモリ量で混合整数計画問題を計算できる。

以上の各構成は、可能な限りこれらを組み合わせて実施され得る。

１００ ネットワーク設計装置
１１０ 制御部
１１２ 設計情報入力部
１１４ ＴＤＭ伝送路組み合わせ候補生成部
１１６ ＴＤＭ伝送路選択部
１１８ 結果出力部
１２２ ノード次数スコア計算部
１２４ ノード順序リスト生成部
１２６ 途中ノードリスト生成部
１２８ ＴＤＭ伝送路組み合わせ候補作成部
１４０ メモリ
１５０ 外部記憶装置
１６０ 入力装置
１７０ 出力装置

Claims (10)

1. 複数のノードがリンクによって接続されるネットワークにおける前記複数のノード間の接続関係を示すネットワークトポロジ情報と、始点ノード、終点ノード、経路、本数を含むデマンドを示すデマンド情報とを格納する記憶部と、
   前記ネットワークトポロジ情報及び前記デマンド情報に基づいて、
   各ノードにおいて終端されるデマンドの本数と各ノードを通過するデマンドの本数との合計値を算出し、
   リンクによって接続される他のノードの数を示すノードの次数を算出し、
   前記複数のノードを、前記ノードの次数が大きいノードが上位になるように、前記ノードの次数が同じ場合には前記合計値が大きいノードが上位になるように、さらに、終端されるデマンドがないノードが下位になるように、並べる順序リストを作成し、
   各デマンドにおいて、始点ノード及び終点ノードを除く始点ノードと終点ノードとの間に通過するノードについて、前記順序リストに従って、ソートし、
   各デマンドについて、前記ソートされたノードの上位のノードから、所定数のノードを取り出し、前記始点ノード、前記終点ノード、及び、前記所定数のノードを端点とする伝送路の組み合わせ候補を生成し、
   前記伝送路の組み合わせ候補から、前記デマンドを収容する伝送路の組み合わせを決定する制御部とを、
   備えるネットワーク設計装置。
2. 前記複数のノードのうち少なくとも１つのノードに選択不可フラグが付加されて、前記記憶部に格納され、
   前記制御部は、各デマンドについて、前記ソートされたノードの上位のノードから、０から所定数までのノードを順次取り出し、それぞれについての、前記始点ノード、前記終点ノード、及び、前記取り出したノードを端点とする伝送路の組み合わせ候補を生成し、取り出したノードに選択不可フラグが付加されている場合には、当該デマンドについての伝送路の組み合わせ候補の生成を終了する
   請求項１に記載のネットワーク設計装置。
3. 前記制御部は、前記ノードの次数及び前記合計値が同じノードが複数存在する場合に、当該ノードの中から任意のノードの組み合わせを取り出し、当該ノードの組み合わせを含むノードを端点とする伝送路の組み合わせ候補を生成する、
   請求項１に記載のネットワーク設計装置。
4. 前記制御部は、前記ノードの次数及び前記合計値が同じノードが複数存在する場合に、終端されるデマンドの本数が多いノードを上位のノードとする
   請求項１に記載のネットワーク設計装置。
5. 前記制御部は、前記ノードの次数、前記合計値、前記終端されるデマンドの本数が同じノードが複数存在する場合に、通過するデマンドの始点ノード及び終点ノードの対の数が多いノードを上位のノードとする
   請求項４に記載のネットワーク設計装置。
6. 前記制御部は、前記ノードの次数、前記合計値、前記終端されるデマンドの本数が同じノードが複数存在する場合に、通過するデマンドの始点ノード及び終点ノードの対の中で同一の対の数が多いノードを下位のノードとする
   請求項４に記載のネットワーク設計装置。
7. 前記制御部は、前記ノードの次数、前記合計値、前記終端されるデマンドの本数が同じ
   ノードが複数存在する場合に、通過するデマンドの始点ノード及び終点ノードの対の中で同一の対の数の平均値が大きいノードを下位のノードとする
   請求項４に記載のネットワーク設計装置。
8. 前記制御部は、前記ノードの次数、前記合計値、前記終端されるデマンドの本数が同じノードが複数存在する場合に、通過するデマンドの数に対する、通過するデマンドのうち始点ノード及び終点ノードが共に同じデマンドの数の比が小さいノードを下位のノードとする
   請求項４に記載のネットワーク設計装置。
9. 複数のノードがリンクによって接続されるネットワークにおける前記複数のノード間の接続関係を示すネットワークトポロジ情報と、始点ノード、終点ノード、経路、本数を含むデマンドを示すデマンド情報とに基づいて、
   各ノードにおいて終端されるデマンドの本数と各ノードを通過するデマンドの本数との合計値を算出し、
   リンクによって接続される他のノードの数を示すノードの次数を算出し、
   前記複数のノードを、前記ノードの次数が大きいノードが上位になるように、前記ノードの次数が同じ場合には前記合計値が大きいノードが上位になるように、さらに、終端されるデマンドがないノードが下位になるように、並べる順序リストを作成し、
   各デマンドにおいて、始点ノード及び終点ノードを除く始点ノードと終点ノードとの間に通過するノードについて、前記順序リストに従って、ソートし、
   各デマンドについて、前記ソートされたノードの上位のノードから、所定数のノードを取り出し、前記始点ノード、前記終点ノード、及び、前記所定数のノードを端点とする伝送路の組み合わせ候補を生成し、
   前記伝送路の組み合わせ候補から、前記デマンドを収容する伝送路の組み合わせを決定する
   ネットワーク設計方法。
10. コンピュータに、
    複数のノードがリンクによって接続されるネットワークにおける前記複数のノード間の接続関係を示すネットワークトポロジ情報と、始点ノード、終点ノード、経路、本数を含むデマンドを示すデマンド情報とに基づいて、
    各ノードにおいて終端されるデマンドの本数と各ノードを通過するデマンドの本数との合計値を算出し、
    リンクによって接続される他のノードの数を示すノードの次数を算出し、
    前記複数のノードを、前記ノードの次数が大きいノードが上位になるように、前記ノードの次数が同じ場合には前記合計値が大きいノードが上位になるように、さらに、終端されるデマンドがないノードが下位になるように、並べる順序リストを作成し、
    各デマンドにおいて、始点ノード及び終点ノードを除く始点ノードと終点ノードとの間に通過するノードについて、前記順序リストに従って、ソートし、
    各デマンドについて、前記ソートされたノードの上位のノードから、所定数のノードを取り出し、前記始点ノード、前記終点ノード、及び、前記所定数のノードを端点とする伝送路の組み合わせ候補を生成し、
    前記伝送路の組み合わせ候補から、前記デマンドを収容する伝送路の組み合わせを決定する
    ことを実行させるネットワーク設計プログラム。

Images