"ネットワークに要求されるパスおよび装置構成の設計を行うネットワーク設計システムであって、要求されるパスの始点拠点および終点拠点間に要求されるパスの帯域の情報と、各拠点に設置可能な装置候補の種類と、各装置におけるポートの種類およびポート数の情報を用いて、装置コストを表す目的関数と、該目的関数を最小化する際に考慮すべき制約条件とを設定する設定部と、該制約条件の下に、該目的関数を最小とする数理計画問題の解を求めることにより、パスの配置の仕方、装置の配置の仕方、および、使用するポートの種類およびポート数を導出する導出手段と、を備えることを特徴とするネットワーク設計システム。既にパスが配置されている前記ネットワークに対し、新たに要求されるパスを順次追加する際に、該新たに要求されるパスを追加するための装置コストを最小化するように、パス、装置及びポート数を導出することを特徴とする請求項1に記載のネットワーク設計システム。予め配置するパスを決定しておき、装置コストを最小化する装置の配置の仕方を導出することを特徴とする請求項1に記載のネットワーク設計システム。パスの敷設にかかるコストを装置コストに含めることを特徴とする請求項1に記載のネットワーク設計システム。予め使用する装置を決定しておき、パスの配置の仕方と使用するポート数を導出することを特徴とする請求項4に記載のネットワーク設計システム。予めどのようにトラフィックを割り振るかを決定しておき、装置の配置の仕方と使用するポートの種類およびポート数を導出することを特徴とする請求項1に記載のネットワーク設計システム。前記装置においてポートの種類が異なるネットワークカードを取り付け可能な場合、装置の配置の仕方の代わりにネットワークカードの配置の仕方を導出することを特徴とする請求項1に記載のネットワーク設計システム。ネットワークに要求されるパスおよび装置構成の設計を、コンピュータを使って行うネットワーク設計方法であって、コンピュータに、要求されるパスの始点拠点および終点拠点間に新規に要求されるパスの要求帯域の情報と、各拠点に設置可能な装置候補の種類と、各装置のポート数の情報を用いて、装置コストを表す目的関数と、該目的関数を最小化する際に考慮すべき制約条件とが設定された数理計画問題について、該制約条件の下に、該目的関数を最小とする該数理計画問題の解を求めることにより、パスの配置の仕方、装置の配置の仕方、および、使用するポートの種類およびポート数を導出させる、ことを特徴とするネットワーク設計方法。ネットワークに要求されるパスおよび装置構成の設計を行なうネットワーク設計方法をコンピュータに実現させるプログラムであって、コンピュータに、要求されるパスの始点拠点および終点拠点間に新規に要求されるパスの要求帯域の情報と、各拠点に設置可能な装置候補の種類と、各装置のポート数の情報を用いて、装置コストを表す目的関数と、該目的関数を最小化する際に考慮すべき制約条件とが設定された数理計画問題について、該制約条件の下に、該目的関数を最小とする該数理計画問題の解を求めることにより、パスの配置の仕方、装置の配置の仕方、および、使用するポートの種類およびポート数を導出させる、ことを特徴とするプログラム。以下の実施形態においては、装置候補から、各装置のポート数上限とコストの関係を考慮しながら、パス収容に伴うコスト増が最小となる経路、装置、ポート利用数等を設計可能なネットワーク設計システムを提供する。本実施形態の一側面に従ったネットワーク設計システムは、ネットワークに要求されるパスおよび装置構成の設計を行うネットワーク設計システムであって、要求されるパスの始点拠点および終点拠点間に新規に要求されるパスの要求帯域の情報と、各拠点に設置可能な装置候補の種類と、各装置のポート数の情報を用いて、装置コストを表す目的関数と、該目的関数を最小化する際に考慮すべき制約条件とを設定する設定部と、該制約条件の下に、該目的関数を最小とする数理計画問題の解を求めることにより、パスの配置の仕方、装置の配置の仕方、および、使用するポート数を導出する導出手段とを備える。以下の実施形態によれば、装置候補から、各装置のポート数上限とコストの関係を考慮しながら、パス収容に伴うコスト増が最小となる経路、装置、ポート利用数等を設計可能なネットワーク設計システムが提供される。本実施形態では、各拠点に配置される装置のコストが最小となるように、パスを順次決定していく手段を提供し、あるパスデマンド各拠点間に要求されるトラフィック帯域を収容する上で、配置すべき装置コスト電力あるいは金額が最小になるようにパスを特定する。これは、以下の動作からなる。1.コスト変化が発生しない設計パスデマンドに対し、現在考えられている装置の変更が発生しないように、パス経路を設定する。2.コスト変化が発生せざるを得ない場合は、コスト変化が最小となるように設計する。パスデマンドに対し、利用ポート数が不足しないような装置を選定し、装置コスト電力あるいは金額の和が最小になるようにパスを設定する。図3及び図4は、コスト増が発生する場合の本実施形態の動作を説明する図である。図3では、ネットワーク上で配置可能な装置Aと装置Bがあるという条件下で、2つのパスデマンド6Gbpsと5Gbpsを順番に収容設計していく例を示す。ここで、最初のパス16Gbpsが既に上側経路に収容され、装置Aを使うことが設計解として与えられている。また、パスデマンド1を収容する装置Aでは1Gbps回線を用いて6ポートのリンクアグリゲーション1つのパスに6対のポートをつなぐ6つのリンクをまとめたもので入力ポートを設計し、同様に6ポート利用で出力ポートが設計されるような計12本のポートが既に配置決定されている。このとき、次のパス25Gbps収容を設計しようとした際、パス2の収容の選択肢としては、上側経路に入出力ポートとして各5ポートを利用したリンクアグリゲーションで収容した場合は、装置Aのポート数12本では不足するため、装置Aを装置Bへ変更すればよいコスト増=5、下側経路に、入出力ポートとして各5ポートを利用したリンクアグリゲーションで収容した場合、装置未設計箇所にコストがより小さい装置Aを配置すればよいコスト増=10、ケースが考えられる。この結果、最小コストを実現する設計解としては、上側経路にパス2を収容し、装置Aから装置Bへ変更すればよいことが分かる。一方で、図4では、図3の場合と設計条件は同じで、ネットワーク上で配置可能な装置候補だけ異なる場合を示す。このときのパス経路の選択肢としては、上側経路に、入出力ポートとして各5ポートを利用したリンクアグリゲーションで収容した場合、装置Aのポート数12本では不足するため、装置Aを装置Bへ変更すればよいコスト増=10、下側経路に、入出力ポートとして各5ポートを利用したリンクアグリゲーションで収容した場合、装置未設計箇所に装置Cを配置すればよいコスト増=5、ケースが考えられる。この結果、最小コストを実現する設計解としては、下側経路にパス2を収容し、未設計箇所に装置Cを配置すればよいことが分かる。このように、実装置の候補から、装置配置に伴うコスト電力あるいは金額を最小化するように、経路と装置を特定していく。図5は、本実施形態で用いられる問題設定について説明する図である。本実施形態では、パスデマンドを収容可能な装置の選定問題として、トラフィック経路、回線レート、利用ポート数の関係と、装置毎に搭載されるポート数上限の制約条件を定式化し、各拠点に配置される装置のコストの総和が最小となるネットワーク構成を、経路リンク集合装置の選定有無を示す0、1変数で定義した01整数計画問題に帰着して数理演算で設計する。本実施形態の問題設定を要約すると、目的関数:min各拠点に配置される装置コストの和、制約条件:接続関係を考慮したトラフィック流量保存条件、各装置が持つポート利用数の上限条件、各拠点に配置される装置条件装置は各拠点に一つのみ存在、という条件式を立て、制約条件の下に目的関数を最小化する問題と記述することが出来る。上記問題における設計変数は、パスデマンドの経路が経由するリンク利用有無:X∈{0,1}装置利用有無::Z∈{0,1}が定義され、これらの設計変数の線形結合で、目的関数と制約条件を定式化することで、数理演算をベースとして、目的関数を最適化する経路解X=0,1、装置選定解Z=0,1を特定することが可能になる。なお、本問題で定義されるリンク変数は、転送方向を含めた経路を設計する意図で、1つの物理リンクに対して2つの片方向リンク変数が定義されるものである図6は、本実施形態の処理の流れを示すフローチャートである。まず、ステップS10において、これから設計するパスデマンドを取得する。ステップS9において、現時点で収容設計されているパスと装置の情報を取得しステップS15、各拠点間の接続関係トポロジと各拠点場所で設置可能な装置候補の定義情報10に基づき、設計モデルを構築する。ステップS9は、ステップS11及びS12からなる。ステップS11において、装置選定および経路を決定するための目的関数を設定する。ステップS12において、拠点接続関係からトラフィック流量保存制約や各装置のポート数制約条件や装置選択条件を設定する。ステップS13において、ステップS9、S10で定式化した設計モデルから装置およびパスを算出する。ステップS14において、設計結果を格納し、ステップS15に戻る。ステップS13の装置及びパスの算出には、0-1整数計画問題を解くことの出来る既存のソルバを使用する。数理計画問題を解くソルバには、フリーソフトや商用ソフトが存在する.これらのソルバでは、線形計画問題や整数計画問題の構造を各ソルバで指定されるフォーマットに変換した入力を与えると、目的関数を最適化最大化or最小化する設計解を自動計算することが可能である.なお、フリーのソルバには以下のようなソフトがある.GLPKhttpwwwgnuorgsoftwareglpkSCIPhttpscipzibdelpsolvehttplpsolvesourceforgenet55ClphttpsprojectscoinororgClpOpenOpthttpopenoptorgWelcome以下、Rという統計計算ソフト上で、lpsolveを実行する例題を説明する。R:httpwwwokadajporgRWikiRA4C7BFF4CDFDB7D7B2E8h57b4eda目的関数制約条件という01整数計画問題を解く場合、結果、111のベクトルが出力され、x1y1z1の解を示す。一方で、同じ問題を整数計画問題として解く場合は、と与えられ、結果140のベクトルが出力され、x1y4z0の解を示す。このように、目的関数の係数をベクトル化したfobjと、設計変数を含む項を左辺に移行した制約条件式に対して、係数を行列化したfcon,制約条件式の等号不等号をベクトル化したfdir,制約条件式の定数項をベクトル化したfrhsを生成し、lp関数に引数として与えることで、目的関数を最適化最大化or最小化する設計変数の解をベクトルとして得ることが可能になる。図7は、本実施形態のネットワーク設計システムのシステム構成図である。オペレータ設定部20は、ネットワークの状態構成を設計管理するネットワーク設計管理部21からオペレータへのネットワーク状態の表示を受け取り、対象ネットワーク26への装置変更の指示、あるいは、ネットワーク設計管理部21に対してオペレータによるパス設定指示、ネットワーク装置の設定条件を与えるインタフェースを提供する。ネットワーク設計管理部21は、ネットワークの状態パス情報や装置情報を管理しパス管理部22、装置管理部23、ネットワーク状態の変化やオペレータ設定部20より与えられるネットワーク装置の設定条件に従い、最適なネットワーク状態構成を導出し、設計結果をオペレータ設定部20に提示する。あるいは、最適な経路への自動設定を行う。ネットワーク状態収集部24では、ネットワーク上の装置やパス状態を収集する。装置管理部23は、装置情報を管理する。パス管理部22は、パスの経路状態やトラフィック量を管理する。パス設定部25は、オペレータから提示された、あるいは、自動的に設計された経路をネットワーク26上に設定する。条件入力部27は、ネットワーク構成を設計する際の条件設定を行う。パス要求設定部28は、設計対象とするパスデマンド情報をモデル構築部29に与える。装置候補設定部30は、ネットワークに配置可能な装置情報コスト、ポート数などをモデル構築部29に与える。モデル構築部29は、ネットワーク構成を設計する際の、設計モデルを自動構築する。目的関数設定部31は、ネットワーク構成を設計する際の、目的関数の定式化を行う。制約条件設定部32は、ネットワーク構成を設計する際の、制約条件の定式化を行う。NWネットワーク設計部33では、モデル構築部29で、定式化されたモデルに基づき、最適な経路、装置選定を演算する。NW設計部33には、前述の数理計画問題を解くソルバを用いる。本実施形態によると、与えられる装置候補から、各装置のポート数とコスト電力あるいは金額の関係を考慮しながら、装置コストが最小となるような経路装置選定回線ポート数を同時に設計することが可能になる。図8~図10は、本実施形態に従った設計手法について説明する図である。3拠点が接続されているトポロジ上で、パス16Gが拠点2→1→3と収容設計され、拠点1には現在装置Cが設計されている。この条件下で、パス25Gを追加収容する際の装置選定および経路設計を行うものとし、ネットワークに配置可能な装置は以下の3種類あるものとする。装置Aは、コスト10で1Gポートが12本装置Bは、コスト20で1Gポートが24本装置Cは、コスト5で1Gポートが10本ここで、拠点1には、装置A,B,Cが配置可能であることから、装置設計変数Z1A,Z1B,Z1Cを定義し、パス2が経由する経路を構成するリンク変数X1、2X2、1,X1、3,X3、1を定義する。なお、説明の都合、拠点2、3の装置選定を含めていないが、実際の設計問題では、各拠点にも装置変数が定義される。この問題は、図9及び図10のような定式化が行われる。目的関数配置される装置コストの和を最小化する上記目的関数において、Zki=0は、拠点kに装置iを配置しないことを意味し、Zki=1は、拠点kに装置iを配置することを意味する。また、Xi、j=1は、リンクi->jを利用することを意味し、Xi、j=0は、リンクi->jを利用しないことを意味する。なお、ここで、δは、経験的に得られる小さな値である。数理計画問題として、装置コストのみを記述した目的関数を最小化すると、リンクの張り方として、一方向に向かうトラフィックのみならず、Uターンしてからその方向に向かうトラフィックも許容されてしまう。したがって、δを設けることは、リンク自体に小さなコストを設け、Uターンするとコストが余計にかかるようにし、数理計画問題の解として、Uターンするようなトラフィックを排除する意味がある。制約条件フロー保存則ノードに入力されるトラフィック量は、出力されるトラフィック量に等しい装置ポート数制約経路収容で利用されるポート数は、配置される装置が持つポート数よりも少なくてはならない。上記制約式において、X1,2の前の係数は0であるが、これは、リンク1->2X1,2に5Gのトラフィックを収容した場合のポートの増加数を示す。この場合、既に、リンク2->1に6Gのリンクがあり、リンクは一方向と逆方向の双方向の伝送路を含んでいるとしており、5Gのトラフィックをリンクを増やすことなく収容可能であるので、ポート数は増えないから0となっている。X2,1の前の係数は5となっている。これは、リンク2->1X2,1に5G収容した場合のポート数の増加数を示す。今の場合、リンク2->1には、既に6Gのトラフィックが収容されており、これ以上収容できないので、新たに5Gのトラフィックを収容するリンクが必要なことを示している。X1,3の前の係数は5となっている。これは、リンク1->3X1,3に5Gのトラフィックを収容した場合のポート数の増加数である。X3,1の前の係数は0となっている。これは、リンク3->1X3,1に5Gのトラフィックを収容した場合のポートの増加数を示す。Z1Aの前の係数は12であるが、これは、装置Aのポート数である。Z1Bの前の係数は、24であるが、これは、装置Bのポート数である。Z1Cの前の係数は、10であるが、これは、装置Cのポート数である。右辺で最後に減算されている12は、パス1で利用されるポート数である。すなわち、装置ポート数の制約式は、{パス2収容に伴う追加ポート数}≦{各機器選択時の総ポート数}-{パス1の利用ポート数}となっている。装置選択制約各拠点で配置される装置は一つ以下でなければならない。Z変数は、0か1しか取らないので、上記装置選択制約式は、いずれかのZ変数が1か、全てのZ変数が0となる場合しか許容しないことを示している。図11~図12は、本実施形態に従った、経路装置選定、回線設計を行なう場合の設計方法を説明する図であり、図13~図14は、これらを大域最適化問題として解く場合の設計方法を説明する図である。拠点間の接続関係対象トポロジ,各区間のトラフィックデマンドリスト,各拠点に配置可能な装置機器候補リストを与えた条件下で、最小コストとなるように、各デマンドに対する転送経路,各拠点に配置する装置の選定,および、各リンクの回線種別及びポート多重度を同時設計する。なお、本問題は、物理リンクに対して各方向を持つ2つの論理リンクで表現される有向グラフG={V,E}Vは、拠点を表す点の集合で、Eは、リンクを表すエッジの集合である上で定義され、非線形整数計画問題に属する。以降では,本問題を解くための設計モデルについて説明する。目的関数与えられたすべてのデマンドを収容し,ネットワーク全体で配置される装置コスト消費電力量を最小化する。ここで、は、拠点mで配置可能な装置kのコスト消費電力量である。また、は、無駄なリンク利用経路折り返しを回避するための係数であり、回線選定時に回線種別r毎の優先度付けを行うためにリンクに付与される微小係数である。図13にあるように、拠点Aから拠点Bを介してDに向かう経路を考えた場合、回線リンクに何もコストがないと、拠点Aから拠点Bを通り、拠点Cで折り返して拠点Bに戻り、Dに向かう経路が選択されてしまう可能性がある。しかし、図12に示すように、リンクにδrという微小な係数をコストとして与えておくことにより、拠点Cで折り返す経路は、そうでない経路よりコストが大きくなるため、目的関数を最小化する際に自動的に排除されるようになる。この微小係数の値は、経験的に設定される。設計変数は、拠点m∈Vに対する装置kの配置有無を表す変数である。また、は、回線種別rのi―>jリンクに対する、s、d区間デマンドのトラフィック経由の有無を表す変数である各拠点間において、回線種別r毎に各方向i->j/j->iを示す2つの論理リンクが定義される。上記設計変数の設定例を図13に示す。本例では、各拠点に3種類の装置が配置可能であるものとして、装置設計変数Zm、kを与えている。さらに、拠点間のリンクでは、1Gと10Gの2種類を想定し、すべてのデマンド1,2に対して、リンク設計変数Xs、dr,ijを定義している。制約条件フロー保存則:拠点mで入力されるトラフィック量と出力されるトラフィック量は等しい。ホップ数制約:デマンドに対するホップ数の上限値ここで、は、s、d区間デマンドに対するホップ数上限値装置選択制約:拠点mで選択される装置は1つ以下である。装置ポート数制約:トラフィック転送に利用するポート数は、各装置で搭載されるポート数以下でなければならない。ここで、は、s、d区間デマンドに対する要求帯域である。は、双方向リンクに対して転送量が多い方のリンクトラフィック量を用いて、回線種別rの利用ポート数を算出する関数である。ceilという関数は、xより小さくない整数で最小のものを与える関数である。pr、kは、装置kで搭載される回線種別rのポート数である。Er、mは、拠点mでトラフィックの入出力元Source/Destinationとして利用される回線種別rのポート数である。リンクアグリゲーション数制約:各リンクに対するポート多重数を指定数以下に制限する。ここで、LAr、i,jは、拠点i,j間リンクに対する回線種別rのポート多重可能数である。以上で定式化された問題をまとめると、以下のようになる。また、以下の式と、変数の意味は、図14にまとめて記載されている。図15~図18は、図11に示す本実施形態に従った経路装置選定回線設計方法に係り、インクリメンタルアプローチを採用した方法を示す図である。図13~図14で説明した大域最適化問題では、変数サイズが大きくなるために、設計処理に多くの計算量を要する。特に、実際のネットワークにおいては、デマンド毎に定義されるリンク変数Xijのサイズが大きくなる。現実的な演算量に落とし込むためには、すべてのデマンドに対してリンク変数を定義し、一度に全デマンドに対する経路を設計するのではなく、各デマンド共通のリンク変数を定義し、デマンドを一つずつ収容設計する方法が有効である。このようにデマンドを一つずつ収容設計するインクリメンタルアプローチIncrementalApproachは、デマンド収容順によって大域最適な設計解を導出できない可能性はあるものの、局所最適解近似解を導出することが可能であることが知られている。また、本アプローチは、新たなサービスデマンド収容時の増設設計にも応用できることから、ネットワーク設計方法として使用可能なアプローチである。インクリメンタルアプローチとして、拠点間の接続関係対象トポロジ、各拠点間のデマンドリスト、各拠点で配置可能な装置機器候補リストを付与した条件下で、最小コスト消費電力量となるように、各デマンドに対する転送経路、各拠点に配置する装置選定、および、回線種別を逐次設計する方法を示す。図13~図14の場合と同様、本問題は有向グラフG={V,E}上で定義することができ、制約条件を{0,1}の設計変数を持つ線形式として扱うことが可能で、01整数計画問題に帰着して解くことできる。なお、以下では、装置選定を含めた設計モデルを記述しているが、各拠点mに1台のみ配置される条件を設定すれば、装置固定条件下での経路、回線設計問題としても使用できる。目的関数特定のsdのトラフィックデマンドを追加収容する際に、ネットワーク上に配備すべき装置のコスト電力を最小化する。ここで、Cm、k:は、拠点mで配置可能な装置kのコスト消費電力量である。δr:は、無駄なリンク利用経路折り返しを回避する図12で説明した通りための係数であり、回線選定時に回線種別r毎の優先度付けを行うため、リンクに付与される微小係数である。設計変数Zm、k∈{0,1}:は、拠点m∈Vに対する装置kの配置有無を表す変数である。Xr,ij∈{0,1}:は、回線種別rのi->jリンクに対する、各デマンドのトラフィック経由有無回線種別r毎に各方向i->j/j->iを示す2つの論理リンクが定義されるを表す変数である。上記設計変数の設定例を図15に示す。本例では、各拠点に3種類の装置が配置可能であるものとし、装置設計変数Zm、kを与えている。さらに、拠点間のリンクでは、1Gと10Gの2種類を想定し、各デマンド共通のリンク設計変数Xr,ijを定義している。制約条件フロー保存則拠点mで入力されるトラフィック量と出力されるトラフィック量は等しい。ホップ数制約:ここで、H:は、設計デマンドに対するホップ数上限値である。装置選択制約:拠点mで選択される装置は1つ以下である。装置ポート数制約:トラフィック転送に利用するポート数は、各装置で搭載されるポート数以下でなければならない。ここで、やの項は、同一拠点間リンクで、現時点の回線種別rとは異なる他の回線種別qが選択された場合に、回線種別rのポートが利用されなくなることを意味する。B:は、設計対象となるデマンドの要求帯域である。Rij:は、i->jリンクに対し、既に転送されているトラフィック量を表す。urij:は、拠点i-j間の物理リンクに対し、既に利用されている回線種別rのポート数を表す。は、双方向リンクに対して転送量が多い方のリンクトラフィック量を用いて、回線種別rの利用ポート数を算出する関数である。ceilxという関数は、前述したものと同じ関数である。pr、k:は、装置kで搭載される回線種別rのポート数である。Er、mは、拠点mでトラフィックの入出力元Source/Destinationとして利用される回線種別rのポート数である。リンクアグリゲーション数制約:各リンクに対するポート多重数を指定値以下に制限する。LAr、i,j:は、拠点i,j間リンクに対する回線種別rのポート多重可能数を表す。以下に、上記方法による設定式をまとめて示す。各式と各変数の意味は、図16にまとめて示されている。<設計例>図17に示す設計問題に対し、デマンド1,2を順番に設計する例を以下に示す。ここで、装置候補はA/B/Cの3種類が存在し、各拠点で3種類の装置を配置可能であるとする。さらに,回線種別としては、1Gと10Gの2種類を想定し、リンクアグリゲーションは実施しないものとするLAr、i,j=1。1.デマンド1拠点1→拠点2の収容設計モデルデマンド1は、拠点1で配置される装置の1Gポートを利用して流入し、拠点2の1Gポートを利用して流出する場合を考える。ここで、U1は1Gの回線を前提にポート数を求める関数、U2は10Gの回線を前提にポート数を求める関数となることから、例えば、U12=2、U22=1という係数になる。デマンド1に対する設計解上記の式を、前述のソルバRlpsolveで演算すると、その結果として、X1、12=1、Z1、C=1、Z2、C=1、その他の設計変数=0となり、拠点1、拠点2には、装置Cが選定され、デマンド1は、拠点1-2間の1G回線を経由する経路が設計される。ソルバR適用時のデータ構造例上記モデルをRに適用した際のデータ構造イメージを図18に示す。ソルバでは、内部で、入力データの何番目の係数がどの変数の係数となるかが予め決められている。したがって、ソルバを利用する場合には、その決められた係数を問題の式に対応させて、順番どおりに係数の値を配列した構造のデータを生成する。これを入力することにより、ソルバ内部で係数が与えられた式が生成され、内部のアルゴリズムに従って、解が求められる。なお、fdirは、等号、不等号を入力するが、これも、何番目の式のどの部分の等号あるいは不等号となるかが、配列の位置によって決定されている。出力も、0-1整数計画問題のソルバの場合には、0と1の配列が得られるが、何番目の0あるいは1がどの変数の値かが与えられており、入力データを生成する際に解くべき問題の係数を配列の位置に対応付けた順番に解が得られる。他デマンドの収容設計の処理も、同様のデータ構造の下、ソルバによる演算が実施される。2.デマンド2拠点2→拠点3の収容設計モデル次に、この状態からデマンド2を収容するための問題を以下に示す。デマンド2は、3Gbpsのデマンドであり、拠点2で配置される装置の10Gポート1本で流入し、拠点3の10Gポート1本で流出する場合を考える。デマンド2に対する設計解ソルバによる演算の結果、X2、23=1、Z1、C=1、Z2、A=1、Z3、A=1、その他の設計変数=0となり、拠点1に装置C、拠点2に10Gポートをサポートする装置Aがアップグレードされ、拠点3には、装置Aが選定される。さらに、デマンド2は、拠点2-3間の10G回線を経由する経路が設計される。なお、上記の設計条件は、リンクアグリゲーションを許容しない設定のため、3Gのデマンドを収容するために、10G回線での転送経路が設計され、合わせて10G回線をサポートする装置が選定される結果となる。なお、上記のような装置コストだけではなく、回線施設コストを考慮した設計をすることも可能である。この場合には、リンクコストを、前述のδ以外に与えればよい。また、各拠点の装置配置を明示的に与えた場合の経路回線設計を行なうこともできる。この場合には、各拠点の設定装置候補を一つにすればよい。図19~図23は、トラフィック状態を明示的に与えた場合の回線装置設計方法を説明する図である。図11~図18で説明した最適ネットワーク設計問題では、デマンドに対する転送経路、装置選定、回線設計を総合的に行っているが、オペレータによっては、トラフィック転送経路は明示的に指定したい場合もある。したがって、以下の図19~図23では、ネットワーク上で流れるトラフィック転送状態が指定された条件下で、最小コスト電力となる装置選定回線設計を行う設計モデルを構築し、拠点間の接続関係対象トポロジ、各拠点間のトラフィック転送経路、各拠点で配置可能な装置機器候補リストを付与した条件下で、最小コストとなるように各拠点に配置する装置選定、および、回線種別を決定する方法を示す。本問題は、物理リンクの接続関係を示す無向グラフG={V,E}上で定義される。また、目的関数および制約条件を{0,1}の変数を持つ線形式として扱うことが可能であり、0-1整数計画問題に帰着して解くことができる。なお、前述の設計モデルとは異なり、経路を特定するために双方向で定義されるリンク変数Xijは不要になるため、問題規模を大きく削減できることが期待できる。目的関数与えられたトラフィック転送状態を収容保証する上で、ネットワークに配備すべき装置のコスト電力を最小化する。ここで、Cm、k:は、拠点mで配置可能な装置kのコスト消費電力量である。δr:は、回線選定時に回線種別r毎の優先度付けを行うため、リンクに付与される微小係数である。設計変数Zm、k∈{0,1}:は、拠点m∈Vに対する装置kの配置有無を表す変数である。Lr、i,j∈{0,1}:は、i,j∈E間で定義される回線種別rのリンク利用有無を表す変数である。上記設計変数の設定例を図19に示す。本例では、各拠点に3種類の装置が配置可能であるものとし、装置設計変数Zm、kを与えている。さらに、拠点間のリンクでは、1Gと10Gの2種類を想定し、無向リンク設計変数Lr、i,jを定義している。制約条件装置選択制約:拠点mで選択される装置は1つ以下である。回線種別制約:トラフィックが流れている拠点i,j間リンクで選択される回線種別rは1つである。装置ポート数制約:トラフィック転送に利用するポート数は、各装置で搭載されるポート数以下でなければならない。ここで、Rij:は、i->jリンクで転送されるトラフィック量である。は、双方向リンクに対して転送量が多い方のリンクトラフィック量を用いて、回線種別rの利用ポート数を算出する関数である。ここで、ceilという関数は、前述したとおりである。pr、k:は、装置kで搭載される回線種別rのポート数である。Er、mは、拠点mでトラフィックの入出力元Source/Destinationとして利用される回線種別rのポート数である。リンクアグリゲーション数制約:各リンクに対するポート多重数を指定値以下に制限する。ここで、LAr、i,j:は、拠点i,j間リンクに対する回線種別rのポート多重可能数である。以下に、上記で説明された設計手法の問題設定をまとめて記載する。各式と各変数は図21にまとめて示されている。<設計例>図20に示す設計問題に対し、図22のようなトラフィック状態を与えた際の0-1整数計画問題を以下に示す。ここで、装置候補はA/B/Cの3種類が存在し、各拠点で3種類の装置を配置可能であるとする。さらに、回線種別としては、1Gと10Gの2種類を想定し、リンクアグリゲーションは実施しないものとするLAr、i,j=1。1.設計モデルここで、U1は1Gの回線を前提にポート数を求める関数、U2は10Gの回線を前提にポート数を求める関数となることから、例えば、U16=6、U26=1という係数になる。2.設計解ソルバによる演算の結果、L2、1,2=1、L2、1,3=1、L2、2,3=1、Z1、B=1、Z2、A=1、Z3、A=1、その他の設計変数=0となり、拠点1には装置B、拠点2と拠点3には、装置Aが選定され、各拠点間の回線はすべて10Gとなる。3.R適用時のデータ構造例上記モデルをRを用いた際のデータ構造イメージを図23に示す。図23の出力データにおいては、Z1、B、Z2、A、Z3、A、L2、1,2、L2、1,3、L2、2,3が1となり、他の設計変数が0となった出力が得られている。前述の設計モデルの目的関数では、リンク設計変数Xr,i,jやLr,i,jに対して、微小値δr=0.001、0.002の係数を付与して、数理演算を実施していたが、本係数は、拠点間のリンクを敷設する際に必要となる金額などの値を付与してもよい。例えば、拠点1から拠点2までの回線敷設コストが1000かかる場合は、該当するリンクの係数を1000δrXr,1,2、1000δrXr,2,1や1000δrLr,1,2と置けばよい。また、前述の設計では、拠点に1つの装置のみを配置しなければならないという条件を与えていたが、トラフィック収容を実施する上で、拠点に複数装置を配置できる条件で設計することも可能である。このような条件で設計する際は、拠点mに配置可能な装置設計変数Zm、kは、0か1の整数値で与えるのではなく、装置kを複数個配置する結果を許容する整数値∈Zとして定義し、以下、、式等の制約式以下の式を削除した設計モデルを整数計画問題として計算する。更に、上記の設計では、各拠点mに配置可能な装置候補を複数設定した例,低速NWカードp=1、高速NWカードp=2の部品で構成されるものとする。ここで、Cpm、k:は、拠点mで配置可能な、装置部品pにおけるカード種別kのコスト消費電力量である。設計変数の変更制約条件の変更式の拡張変更パッケージ選択制約:拠点mで選択される共通部は1つ以下である。新規追加共通部のスロット数制約p=0:装置内に搭載可能なNWカード数は各共通部で保有するスロット数以下でなければならない。ここで、sm、k:は、拠点mに配置可能な共通部kに備わるスロット数である。式の、低速NWカードを考慮に入れた拡張低速NWカードp=1のポート数制約:トラフィックの入出力元Source/Destinationとして利用される回線種別rのポート数は、低速NWカードkの搭載ポート数以下でなければならない。ここで、pr、kは、低速NWカードに搭載される回線種別rのポート数を表す。Er、mは、拠点mでトラフィックの入出力元Source/Destinationとして利用される回線種別rのポート数を表す。式の、高速NWカードを考慮に入れた拡張高速NWカードp=2のポート数制約上記の手法によって設定された問題を以下にまとめて示す。各式と変数の意味は、図26にまとめて示されている。図27~図29は、図15~図18の手法にパッケージ型装置を想定した設計手法を適用した手法を説明する図である。本手法では、図24~図26の手法をインクリメンタルアプローチで処理する場合を扱う。目的関数の変更与えられたトラフィック転送状態を収容保証する上で、ネットワークに配備すべき装置パッケージのコスト電力消費量を最小化する。なお、1つの装置は、共通部、低速NWカードp=1、高速NWカードp=2の部品で構成されるものとする。Cpm、k:は、拠点mで配置可能な装置部品pにおけるカード種別kのコスト消費電力量を表す。設計変数の変更制約条件の変更式の拡張変更パッケージ選択制約:拠点mで選択される共通部は1つ以下である。新規追加共通部のスロット数制約:p=0装置内に搭載可能なNWカード数は各共通部で保有するスロット数以下でなければならない。sm、k:は、拠点mに配置可能な共通部kに備わるスロット数を表す。式の、低速NWカードを考慮に入れた拡張低速NWカードp=1のポート数制約:トラフィックが入出力Source/Destinationされる回線種別rのポート数は、低速NWカードkの搭載ポート数以下でなければならない。pr、kは、低速NWカードに搭載される回線種別rのポート数を表す。Er、mは、拠点mでトラフィックの入出力元Source/Destinationとして利用される回線種別rのポート数を表す。式の高速NWカード拡張高速NWカードp=2のポート数制約以下に、上記手法の問題設定をまとめて示す。各式と変数の意味は、図27にまとめて示されている。<設計例>図28を例に、デマンド1に対する経路装置構成回線種別を設計する。拠点1-2間の回線では、10Gと40Gの2種類を想定し、リンクアグリゲーションは実施しないものとするLAr1,2=1。また、拠点1->2には30Gbps、拠点2->1には10Gbpsのバックグラウンドトラフィックが既に発生している状況を想定する。1.設計モデルここで、U1は10Gの回線を前提にポート数を求める関数、U2は40Gの回線を前提にポート数を求める関数となることから、例えば、U140=4、U240=1という係数になる。2.デマンド1に対する設計解ソルバによる演算の結果、X2、1,2=1、Z01、A=1、Z11、D=2、Z21、F=1、Z02、A=1、Z12、D=2、Z22、F=1、その他の設計変数=0となり、拠点1,拠点2には低速カードDが2枚、高速カードFが1枚、共通部Aが選定され、デマンド1は、拠点1-2間の40G回線を経由する経路が設計される。3.R適用時のデータ構造例上記モデルをRを用いた際のデータ構造イメージを図29に示す。図29の出力データでは、X2、1,2=1、Z01、A=1、Z11、D=2、Z21、F=1、Z02、A=1、Z12、D=2、Z22、F=1、その他の設計変数=0となって出力されることが理解される。図30~図32は、図19~図23の手法にパッケージ型装置を想定した設計手法を適用した手法を説明する図である。目的関数の変更与えられたトラフィック状態を収容する上で、ネットワークに配備すべき装置パッケージのコスト電力消費量を最小化する。なお、1つの装置は、共通部、低速NWカードp=1、高速NWカードp=2の部品で構成されるものとする。ここで、Cpm、k:は、拠点mで配置可能な装置部品pにおけるカード種別kのコスト消費電力量を表す。設計変数の変更制約条件の変更式の拡張変更パッケージ選択制約:拠点mで選択される共通部は1つ以下である。新規追加共通部のスロット数制約p=0:装置内に搭載可能なNWカード数は各共通部で保有するスロット数以下でなければならない。sm、k:は、拠点mに配置可能な共通部kに備わるスロット数を表す。式の低速NWカード拡張低速NWカードp=1のポート数制約:トラフィックの入出力元Source/Destinationとして利用される回線種別rのポート数は、低速NWカードkの搭載ポート数以下でなければならない。pr、kは、低速NWカードに搭載される回線種別rポート数を表す。Er、mは、拠点mでトラフィックの入出力元Source/Destinationとして利用される回線種別rのポート数を表す。式の高速NWカード拡張高速NWカードp=2のポート数制約以下に、上記手法で得られた問題設定をまとめて示す。各式と変数の意味は、図30にまとめて示されている。<設計例>図31を例に、与えられたトラフィック状態に対し、装置構成回線種別を設計する。拠点1-2間の回線では、10Gと40Gの2種類を想定し、リンクアグリゲーションは実施しないものとするLAr,1,2=1。また、拠点1->2には15Gbps、拠点2->1には20Gbpsのトラフィックが発生する状況を想定する。1.設計モデル2.設計解ソルバによる演算の結果、L2、1,2=1、Z01、A=1、Z11、D=4、Z21、F=1、Z02、A=1、Z12、D=3、Z22、F=1、その他の設計変数=0となり、拠点1には低速カードDが4枚、高速カードFが1枚、拠点2には低速カードDが3枚、高速カードFが1枚、共通部Aが選定され、デマンド1に対しては、拠点1-2間の40G回線を経由する経路が設計される。3.R適用時のデータ構造例上記モデルに対し、Rを用いた際のデータ構造イメージを図32に示す。出力データにおいては、L2、1,2=1、Z01、A=1、Z11、D=4、Z21、F=1、Z02、A=1、Z12、D=3、Z22、F=1、その他の設計変数=0となることが示されている。図33は、本実施形態の設計手法をプログラムで実行する場合に必要とされるコンピュータのハードウェア構成例である。本実施形態の設計手法は、プログラムで実行可能である。プログラムを実行するコンピュータ39は、スタンドアロンのマシンでも、対象ネットワーク50に通信インタフェース44を介して接続され、対象ネットワーク50のネットワーク装置の設定を自動で行なうネットワーク装置であっても良い。コンピュータ39は、プログラムを実行するCPU41を備える。また、プログラムを格納するハードディスクなどの記憶装置45、プログラムを展開して実行するためのワークエリアとしてRAM42、コンピュータ39の基本機能を制御するプログラムを格納するROM43、キーボードやディスプレイ、マウス等の入出力装置48、外部と通信するための通信インタフェース44を備える。また、記録媒体読み取り装置46は、プログラムを格納する、DVD,CD,フレキシブルディスク,ICメモリ等の可搬記録媒体47からプログラムを読み込む。これらは相互にバス40によって接続される。本実施形態の手法を実行するプログラムは、記憶装置45に格納されているか、可搬記録媒体47に記録されている。プログラムを実行する場合には、記憶装置45あるいは可搬記録媒体47から読み取り、RAM42に展開して実行する。ユーザは、本実施形態の設計手法を実行するにおいて、設計モデルを生成し、これをプログラムとして与えられるソルバへの入力データとして構築する。この入力データを入出力装置48から入力し、CPUにプログラムを実行させ、設計結果をディスプレイ等に表示させる。これにより、ユーザは、どのようにネットワークを構築すればよいかをディスプレイの表示から知ることが出来る。プログラムは、通信インタフェース44に接続されたネットワークを介して、他所にある情報提供者49の保持するデータベースからダウンロードして実行したり、ネットワーク環境で実行することも可能である。また、コンピュータ39が通信インタフェース44を介して、設計対象のネットワーク50に接続されたネットワーク管理装置の場合、プログラムを実行するための設計モデルの構築に用いる必要なデータを対象ネットワークから収集することが可能である。また、プログラム実行後に得られた設計情報を通信インタフェース44からコマンドとして対象ネットワーク50に送信し、自動的に設計内容が対象ネットワーク50に反映されるようにしても良い。"