(57)【要約】【課題】最適化問題の計算において転送装置のコストが勘案された最適なネットワーク構成を設計すること。【解決手段】ネットワーク設計装置、ネットワーク設計方法およびネットワーク設計処理プログラムは、複数の通信拠点ごとに転送装置が配置され、かつ、転送装置内のリンク部装置によってリンクを介して通信拠点間が接続されるネットワークに対し、ネットワーク構成を設計する。ネットワーク構成の設計では、経路候補集合、インターフェースの組合せ候補集合および転送装置の組合せ候補集合に基づいて、ネットワーク全体における総コスト値を最小にする回線ごとの最適な経路候補、リンクごとの最適なリンク部装置の組合せ候補および通信拠点ごとの最適な転送装置の組合せ候補を算出する。【選択図】図３
2019161274.tif 000002
【特許請求の範囲】
【請求項１】
複数の通信拠点ごとに転送装置が配置され、かつ、前記転送装置内のリンク部装置によってリンクを介して前記通信拠点間が接続されるネットワークに対し、ネットワーク構成を設計するネットワーク設計装置であって、
前記通信拠点間の接続状態に関するトポロジ情報、前記ネットワークに収容される複数の回線に関する回線情報、前記通信拠点に配置される前記転送装置および前記転送装置内の前記リンク部装置に関する装置情報、および、前記設計において用いるパラメータに関する設計パラメータ情報についての入力を受け付ける入力受付部と、
前記トポロジ情報、前記回線情報、および、前記設計パラメータ情報に基づいて、前記回線ごとに経路候補集合を算出する算出部を有する第１処理部と、
前記装置情報および前記設計パラメータ情報に基づいて前記リンク部装置の組合せ候補集合を算出する第１算出部と、
前記装置情報および前記設計パラメータ情報に基づいて前記転送装置の組合せ候補集合を算出する第２算出部と、を有する第２処理部と、
前記第１処理部の前記算出部による算出結果、前記第２処理部の前記第１算出部による算出結果、および、前記第２処理部の前記第２算出部による算出結果に基づいて、前記ネットワーク全体における総コスト値を最小にする前記回線ごとの最適な経路候補、前記リンクごとの最適なリンク部装置の組合せ候補、および、前記通信拠点ごとの最適な転送装置の組合せ候補を算出する算出部を有する第３処理部と、
前記第３処理部の前記算出部で算出された前記回線ごとの前記最適な経路候補、前記リンクごとの前記最適なリンク部装置の組合せ候補、および、前記通信拠点ごとの前記最適な転送装置の組合せ候補を反映させたネットワーク構成情報を生成する生成部と、
を備えるネットワーク設計装置。
【請求項２】
前記第３処理部の前記算出部は、前記ネットワーク全体における前記リンク部装置の総コスト値と、前記ネットワーク全体における前記転送装置の総コスト値との合計値を、前記ネットワーク全体における総コスト値とする、
請求項１に記載のネットワーク設計装置。
【請求項３】
前記第２処理部の前記第２算出部は、前記組合せ候補ごとに前記転送装置の総スロット数が異なる前記転送装置の前記組合せ候補集合を算出し、
前記第３処理部の前記算出部は、
選択された前記回線ごとの前記経路候補、および、選択された前記リンクごとの前記リンク部装置の組合せ候補に基づいて、前記通信拠点ごとの前記リンク部装置の総数を算出し、
前記通信拠点のそれぞれについて、導出される前記組合せ候補での前記転送装置の前記総スロット数が、算出した前記リンク部装置の総数以上になること、を条件として、前記通信拠点ごとの最適な転送装置の組合せ候補を算出する、
請求項２に記載のネットワーク設計装置。
【請求項４】
請求項１乃至３のいずれか１項に記載のネットワーク設計装置の前記各部としてプロセッサを機能させるネットワーク設計処理プログラム。
【請求項５】
複数の通信拠点ごとに転送装置が配置され、かつ、前記転送装置内のリンク部装置によってリンクを介して前記通信拠点間が接続されるネットワークに対し、ネットワーク構成を設計するネットワーク設計方法であって、
前記通信拠点間の接続状態に関するトポロジ情報、前記ネットワークに収容される複数の回線に関する回線情報、前記通信拠点に配置される前記転送装置および前記転送装置内の前記リンク部装置に関する装置情報、および、前記設計において用いるパラメータに関する設計パラメータ情報を取得することと、
前記トポロジ情報、前記回線情報、および、前記設計パラメータ情報に基づいて、前記回線ごとに経路候補集合を算出することと、
前記装置情報および前記設計パラメータ情報に基づいて、前記リンク部装置の組合せ候補集合を算出することと、
前記装置情報および前記設計パラメータ情報に基づいて、前記転送装置の組合せ候補集合を算出することと、
前記回線ごとの前記経路候補集合についての算出結果、前記リンク部装置の前記組合せ候補集合についての算出結果、および、前記転送装置の前記組合せ候補集合についての算出結果に基づいて、前記ネットワーク全体における総コスト値を最小にする前記回線ごとの最適な経路候補、前記リンクごとの最適なリンク部装置の組合せ候補、および、前記通信拠点ごとの最適な転送装置の組合せ候補を算出することと、
算出された前記回線ごとの前記最適な経路候補、前記リンクごとの前記最適なリンク部装置の組合せ候補、および、前記通信拠点ごとの前記最適な転送装置の組合せ候補を反映させたネットワーク構成情報を生成することと、
を備えるネットワーク設計方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、ネットワーク設計装置、ネットワーク設計方法およびネットワーク設計処理プログラムに関する。
【背景技術】
【０００２】
近年、ネットワークサービスの多様化に伴って、サービス数の増加、および、サービスがネットワークに求める要求条件の多様化が、進んでいる。ネットワークに求める条件としては、例えば、エンド間遅延、帯域保証、または、冗長性に関する条件等がある。サービス数の増加、または、要求条件の多様化に伴って、ネットワークの設備にかかるコストが増大する。
【０００３】
コストの増大を抑えるため、例えば、非特許文献１では、各ネットワークサービスが所有する複数の回線を、効率的に共通の基盤ネットワークに収容するネットワーク設計が行われる。これにより、ネットワークの経済性を、更に向上させる。非特許文献１の方法では、エンド間遅延についてそれぞれ異なる要求条件を持つ回線を収容する基盤ネットワークを、設計する。ここで、設計される基盤ネットワークでは、経路のトラヒックを処理する転送装置が配置されるとともに、転送装置のリンク部には、リンク部装置としてインターフェースが設置される。非特許文献１では、基盤ネットワークの設計において、基盤ネットワーク上の全転送装置のインターフェースにかかる総コスト値が最小になる転送装置の配置および容量を導出する。このため、基盤ネットワークの設計では、各回線を収容する経路の設計と、基盤ネットワーク上の転送装置の配置や容量を設計する設備設計と、を同時に行う。
【０００４】
非特許文献１で行われる処理における全体のフローを図１に示す。非特許文献１のようなネットワークの設計では、各回線を、エンド間遅延に関する要求条件を満たす経路に収容する必要がある。このため、図１に示すように、Ｓ´１において、回線ごとに、エンド間遅延に関する要求条件を満たす経路候補を算出し、前述の要求条件を満たす経路候補の集合を経路候補集合とする。経路候補集合は、前述の要求条件を満たす経路候補から構成され、指定された経路候補数の数以下の経路候補から構成される。ここで、経路候補数は、設計パラメータであり、設計者によって指定される。
【０００５】
そして、非特許文献１では、Ｓ´２において、インターフェースの組合せ候補を算出し、算出した組合せ候補の集合をインターフェースの組合せ候補集合とする。この際、基盤ネットワーク上の各通信拠点の転送装置のリンク部に設置可能なインターフェースの組合せ候補を、算出する。組合せ候補集合には、リンク部に設置可能なインターフェースの組合せ候補が、指定されたインターフェースの組合せ候補数の数だけ、含まれる。ここで、組合せ候補数は、設計パラメータであり、設計者によって指定される。また、インターフェースの組合せ候補のそれぞれは、０個以上のインターフェースの組合せから成る。また、インターフェースの組合せ候補の中のある組合せ候補には、同一の種類のインターフェースが含まれる場合もある。
【０００６】
そして、非特許文献１では、Ｓ´３において、基盤ネットワーク上の全インターフェースの総コスト値を目的関数とし、目的関数を最小化する最適なネットワーク構成を導出する最適化問題を解く。この最適化問題を定式化した数式を、以下に示す。
【０００７】
【数１】
2019161274.tif 000003
【０００８】
また、式（１）´〜（４）´に関連するパラメータ等が示す事項、以下の通りである。
【０００９】
【数２】
2019161274.tif 000004
【００１０】
Ｓ´３の最適化問題では、回線ごとに、１つの経路候補を経路候補集合から選択する。各回線について、経路候補を経路候補集合から選択する条件は、式（２）´で示される。ここで、式（１）´〜（４）´において、変数ｘは、最適化問題の決定変数である。各回線において、変数ｘは、経路候補集合からいずれの経路候補が選択されたかに対応して、変化する。また、最適化問題では、転送装置のリンク部ごとに、すなわち、各通信拠点を接続するリンクごとに、インターフェースの組合せについて１つの組合せ候補をインターフェースの組合せ候補集合から選択する。各リンク部について、インターフェースの組合せ候補を組合せ候補集合から選択する条件は、式（３）´で示される。ここで、式（１）´〜（４）´において、変数ｙは、最適化問題の決定変数である。各リンク部において、変数ｙは、組合せ候補集合からいずれのインターフェースの組合せ候補が選択されたかに対応して、変化する。
【００１１】
また、Ｓ´３の最適化問題では、式（４）´の容量条件が設けられる。すなわち、各リンク（各リンク部）において、総契約帯域が、組合せ候補を構成する全インターフェースの総容量以下となることが、容量条件として、設けられる。このため、最適化問題では、各リンクにおいて、インターフェースの組合せ候補集合から選択される組合せ候補は、前述の容量条件を満たす必要がある。
【００１２】
そして、Ｓ´３では、式（１）´に示す基盤ネットワーク上の全インターフェースの総コスト値を目的関数として、目的関数を最小化する最適化問題を解く。最適化問題を解くことにより、式（２）´〜（４）´の条件を満たす経路候補から最適の経路候補が決定され、式（２）´〜（４）´の条件を満たすインターフェースの組合せ候補から最適な組み合せ候補が決定される。
【００１３】
非特許文献１では、前述のように処理が行われるため、エンド間遅延についてそれぞれ異なる要求条件を持つ回線を収容する基盤ネットワークにおいて、最も総コスト値が低いネットワーク構成、すなわち、最適なネットワーク構成を導出可能になる。すなわち、回線を収容する経路、および、転送装置およびリンク部装置のそれぞれの配置および容量を含むネットワーク構成に関して、複数パターン中から、最適なネットワーク構成を導出可能になる。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】竹下絵莉奈,川田秀雄, “多様なパスを収容するネットワーク設計手法の提案” ２０１７年 電子情報通信学会総合大会 Ｂ−６−２９
【発明の概要】
【発明が解決しようとする課題】
【００１５】
前記非特許文献１では、転送装置のリンク部に設置する全インターフェースのコスト値を勘案して、インターフェースのコスト値の総和を最小にする最適なネットワーク構成を導出する。この際、回線ごとに選択された経路候補に基づいて、各リンクの総契約帯域が、算出される。そして、各リンクにおいて算出された最適なインターフェースの組合せ候補では、リンク部に設置する複数のインターフェースの総容量は、算出した総契約帯域以上となる。したがって、最適なネットワーク構成の導出では、転送装置のリンク部に配置するインターフェースの数には、制限がない。また、インターフェースを設置する転送装置の数および容量にも、制限がない。
【００１６】
しかし、基盤ネットワークにおけるネットワーク全体では、設置される転送装置によっても、コストが発生する。このため、導出された最適なネットワーク構成において、インターフェースの総コスト値が最小となる場合でも、転送装置の配置および配置する転送装置の容量によっては、基盤ネットワークにおけるネットワーク全体のコスト値が最小値とならないことがある。
【００１７】
本発明は、上記事情に着目してなされたものであり、最適化問題の計算において転送装置のコストが勘案された最適なネットワーク構成を設計することができる、ネットワーク設計装置、ネットワーク設計方法およびネットワーク設計処理プログラムを提供するものである。
【課題を解決するための手段】
【００１８】
上記目的を達成するために、本発明の第１の態様は、複数の通信拠点ごとに転送装置が配置され、かつ、前記転送装置内のリンク部装置によってリンクを介して前記通信拠点間が接続されるネットワークに対し、ネットワーク構成を設計するネットワーク設計装置であって、前記通信拠点間の接続状態に関するトポロジ情報、前記ネットワークに収容される複数の回線に関する回線情報、前記通信拠点に配置される前記転送装置および前記転送装置内の前記リンク部装置に関する装置情報、および、前記設計において用いるパラメータに関する設計パラメータ情報についての入力を受け付ける入力受付部と、前記トポロジ情報、前記回線情報、および、前記設計パラメータ情報に基づいて、前記回線ごとに経路候補集合を算出する算出部を有する第１処理部と、前記装置情報および前記設計パラメータ情報に基づいて前記リンク部装置の組合せ候補集合を算出する第１算出部と、前記装置情報および前記設計パラメータ情報に基づいて前記転送装置の組合せ候補集合を算出する第２算出部と、を有する第２処理部と、前記第１処理部の前記算出部による算出結果、前記第２処理部の前記第１算出部による算出結果、および、前記第２処理部の前記第２算出部による算出結果に基づいて、前記ネットワーク全体における総コスト値を最小にする前記回線ごとの最適な経路候補、前記リンクごとの最適なリンク部装置の組合せ候補、および、前記通信拠点ごとの最適な転送装置の組合せ候補を算出する算出部を有する第３処理部と、前記第３処理部の前記算出部で算出された前記回線ごとの前記最適な経路候補、前記リンクごとの前記最適なリンク部装置の組合せ候補、および、前記通信拠点ごとの前記最適な転送装置の組合せ候補を反映させたネットワーク構成情報を出力する生成部と、を備える。
【００１９】
本発明の第２の態様は、第１の態様の前記ネットワーク設計装置であって、前記第３処理部の前記算出部は、前記ネットワーク全体における前記リンク部装置の総コスト値と、前記ネットワーク全体における前記転送装置の総コスト値との合計値を、前記ネットワーク全体における総コスト値とする。
【００２０】
本発明の第３の態様は、第２の態様の前記ネットワーク設計装置であって、前記第２処理部の前記第２算出部は、前記組合せ候補ごとに前記転送装置の総スロット数が異なる前記転送装置の前記組合せ候補集合を算出し、前記第３処理部の前記算出部は、選択された前記回線ごとの前記経路候補、および、選択された前記リンクごとの前記リンク部装置の組合せ候補に基づいて、前記通信拠点ごとの前記リンク部装置の総数を算出し、前記通信拠点のそれぞれについて、導出される前記組合せ候補での前記転送装置の前記総スロット数が、算出した前記リンク部装置の総数以上になること、を条件として、前記通信拠点ごとの最適な転送装置の組合せ候補を算出する。
【００２１】
本発明の第４の態様は、第１の態様乃至第３の態様のいずれか１つの前記ネットワーク設計装置の前記各部として、プロセッサを機能させるネットワーク設計処理プログラムである。
【００２２】
本発明の第５の態様は、複数の通信拠点ごとに転送装置が配置され、かつ、前記転送装置内のリンク部装置によってリンクを介して前記通信拠点間が接続されるネットワークに対し、ネットワーク構成を設計するネットワーク設計方法であって、前記通信拠点間の接続状態に関するトポロジ情報、前記ネットワークに収容される複数の回線に関する回線情報、前記通信拠点に配置される前記転送装置および前記転送装置内の前記リンク部装置に関する装置情報、および、前記設計において用いるパラメータに関する設計パラメータ情報を取得することと、前記トポロジ情報、前記回線情報、および、前記設計パラメータ情報に基づいて、前記回線ごとに経路候補集合を算出することと、前記装置情報および前記設計パラメータ情報に基づいて、前記リンク部装置の組合せ候補集合を算出することと、前記装置情報および前記設計パラメータ情報に基づいて、前記転送装置の組合せ候補集合を算出することと、前記回線ごとの前記経路候補集合についての算出結果、前記リンク部装置の前記組合せ候補集合についての算出結果、および、前記転送装置の前記組合せ候補集合についての算出結果に基づいて、前記ネットワーク全体における総コスト値を最小にする前記回線ごとの最適な経路候補、前記リンクごとの最適なリンク部装置の組合せ候補、および、前記通信拠点ごとの最適な転送装置の組合せ候補を算出することと、算出された前記回線ごとの前記最適な経路候補、前記リンクごとの前記最適なリンク部装置の組合せ候補、および、前記通信拠点ごとの前記最適な転送装置の組合せを反映させたネットワーク構成情報を生成することと、を備える。
【発明の効果】
【００２３】
本発明の第１の態様乃至第５の態様によれば、ネットワーク全体における総コスト値を最小にする最適なネットワーク構成を算出する最適化問題において、回線ごとの経路候補集合と、リンクごとのリンク部装置の組合せ候補集合に加えて、通信拠点ごとの転送装置の組合せ候補集合に基づいて、最適な経路候補と、最適なリンク部装置の組合せ候補と、最適な転送装置の組合せ候補とが、算出される。これにより、最適化問題の計算において転送装置のコストを勘案することができ、最適なネットワーク構成を設計することができるネットワーク設計装置、ネットワーク設計方法、および、ネットワーク設計処理プログラムを提供することができる。
【００２４】
また、本発明の第２の態様及び第３の態様では、最適化問題の計算において、リンク部装置のコストに転送装置のコストを加えた合計値を、最適化問題の目的関数とする。このため、最適化問題では、転送装置のコストを勘案した最適な経路候補、最適なリンク部装置の組合せ候補および最適な転送装置の組合せ候補が、より適切に導出される。
【００２５】
また、本発明の第３の態様では、各転送装置のスロットの容量に関する条件を満たすように、通信拠点ごとの最適な転送装置の組合せが導出される。このため、最適化問題において、最適な経路候補、最適なリンク部装置の組合せ候補および最適な転送装置の組合せ候補が、より適切に導出される。
【図面の簡単な説明】
【００２６】
【図１】図１は、非特許文献１で行われる処理における全体のフローを示すフローチャートである。
【図２】図２は、本発明の第１の実施形態におけるネットワーク設計装置の例を示すブロック図である。
【図３】図３は、第１の実施形態におけるネットワーク設計装置の動作手順の一例を示すフローチャートである。
【図４】図４は、第１の実施形態において、任意の回線について経路候補集合を算出する手順の一例を示すフローチャートである。
【図５】図５は、第１の実施形態において、インターフェースの組合せ候補集合を算出する手順の一例を示すフローチャートである。
【図６】図６は、第１の実施形態において、スイッチの組合せ候補集合を算出する手順の一例を示すフローチャートである。
【図７】図７は、第１の実施形態の動作例において、トポロジの一例を示す概略図である。
【図８】図８は、図６のトポロジの一例に用いる凡例を示す概略図である。
【図９】図９は、第１の実施形態の動作例において、スイッチの一例を示す概略図である。
【図１０】図１０は、図７に示す基盤ネットワークにおけるスイッチの配置の一例を示す概略図である。
【図１１】図１１は、第１の実施形態の動作例において、ネットワークにおける最適な配置例の一例を示す概略図である。
【図１２】図１２は、比較例において、ネットワークにおける最適な配置例の一例を示す概略図である。
【発明を実施するための形態】
【００２７】
以下、図面を参照しながら、この発明に係わる一実施形態を説明する。各実施形態におけるネットワーク装置の例としてＬ２スイッチを用いる。このＬ２スイッチ以外にも、転送装置であって、ネットワーク装置内の設備としてインターフェース等のリンク部装置を設置できる装置であれば、任意のネットワーク装置を利用可能である。例えば、各実施形態において、ルータ等をネットワーク装置（転送装置）として利用可能である。
【００２８】
［第１の実施形態］  
第１の実施形態では、インターフェースのコストに加えて、転送装置のコストも基盤ネットワークのコストとして勘案する。これにより、コスト値がより低いネットワーク構成を導出することができる。
【００２９】
（装置）  
第１の実施形態のネットワーク設計装置の例を示す。図２は、本発明の第１の実施形態におけるネットワーク設計装置の例を示す図である。このネットワーク設計装置１０は、入力情報に基づいて最適な経路情報と、最適な設備情報と、を含む最適なネットワーク構成情報を出力する。ネットワーク設計装置１０は、入力部（入力受付部）１１、第１処理部１２、第２処理部１３、第３処理部１４、出力部（生成部）１５を備える。
【００３０】
第１処理部１２は、算出部１２ａを有する。第２処理部１３は、第１算出部１３ａ、第２算出部１３ｂを有する。第３処理部１４は、算出部１４ａを有する。
【００３１】
入力受付部である入力部１１は、ネットワーク設計者によって入力された入力情報を受け付け、入力情報を第１処理部１２および第２処理部１３に出力する機能を有する。入力情報は、トポロジ情報と、回線情報と、装置情報と、設計パラメータ情報と、を含む。トポロジ情報は、基盤ネットワーク上の通信拠点間の接続状態に関する情報である。回線情報は、ネットワークに収容される複数の回線に関する情報であり、複数の回線は、各ネットワークサービスが所有する。装置情報は、基盤ネットワーク上の各通信拠点に配置される転送装置に関する情報である。また、装置情報には、各転送装置に設置される、インターフェース等のリンク部装置の情報も含む。設計パラメータ情報は、ネットワークの設計において用いるパラメータに関する情報である。
【００３２】
算出部１２ａには、トポロジ情報と、回線情報と、設計パラメータ情報とを含む情報が、入力部１１から入力される。算出部１２ａは、入力部１１から入力される情報から、経路候補集合を算出する。算出部１２ａは、回線ごとに、経路候補集合を算出する。第１処理部１２は、算出部１２ａで求めた経路候補集合を含む経路候補情報を出力する。経路候補情報は、第３処理部１４に出力される。
【００３３】
第１算出部１３ａには、装置情報と、設計パラメータ情報とを含む情報が、入力部１１から入力される。第１算出部１３ａは、入力部１１から入力される情報から、インターフェースの組合せ候補集合を算出する。
【００３４】
第２算出部１３ｂには、装置情報と、設計パラメータ情報とを含む情報が、入力部１１から入力される。第２算出部１３ｂは、入力部１１から入力される情報から、スイッチの組合せ候補集合を算出する。
【００３５】
第２処理部１３は装置候補情報を出力する。装置候補情報は、第３処理部１４に出力される。装置候補集合は、第１算出部１３ａで求めたインターフェースの組合せ候補集合と、第２算出部１３ｂで求めたスイッチの組合せ候補集合と、を含む。
【００３６】
算出部１４ａには、第１処理部１２から経路候補情報が入力され、第２処理部１３から装置候補情報が入力される。算出部１４ａは、入力される経路候補情報および装置候補情報から、最適な経路候補と、最適な装置候補と、を算出する。最適な装置候補は、最適なスイッチの組合せ候補と、最適なインターフェースの組合せ候補と、を含む。第３処理部１４は、算出部１４ａで求めた最適な経路候補と、最適な装置候補と、を出力部１５に出力する。
【００３７】
生成部である出力部１５には、第３処理部１４から、最適な経路候補と、最適な装置候補と、が入力される。そして、出力部１５は、第３処理部１４から入力された情報に基づいて、最適な経路候補、および、最適な装置候補の両方を反映させたネットワーク構成情報を生成する。そして、出力部１５は、最適な経路候補および最適な装置候補を反映させたネットワーク構成情報を、最適なネットワーク構成情報として、ネットワーク設計者が操作する端末装置出力する。最適なネットワーク構成情報は、各回線を収容する最適な経路情報と、各通信拠点に配置されるスイッチおよびインターフェースに関する最適な設備情報と、を含む。スイッチに関する最適な設備情報は、スイッチの最適な配置、および、スイッチの最適な容量に関する情報を含む。インターフェースに関する最適な設備情報は、インターフェースの最適な配置、および、インターフェースの最適な容量に関する情報を含む。なお、出力部（生成部）１５は、生成した最適なネットワーク構成情報を、端末装置等に出力する代わりに、記録媒体等に保存してもよい。
【００３８】
（入力情報）  
第１の実施形態において、ネットワーク設計装置１０の入力部１１に入力される入力情報の例を示す。入力情報は、ネットワーク設計者が入力部１１に入力する情報である。ネットワーク設計者がネットワーク設計装置１０の入力部１１に入力する入力情報は、（１）トポロジ情報と、（２）回線情報と、（３）装置情報と、（４）設計パラメータ情報と、を含む。
【００３９】
（１）トポロジ情報は、（１−１）基盤ネットワークにおける通信拠点間の接続状態を表す接続行列と、（１−２）各通信拠点間のリンクにおける遅延時間と、を含む。
【００４０】
（２）回線情報は、（２−１）各回線における通信の起点および終点と、（２−２）各回線における契約帯域と、（２−３）各回線におけるエンド間遅延の許容度合と、を含む。（２−１）各回線における通信の起点および終点は、回線の端点となる通信拠点のペアを示す。
【００４１】
（３）装置情報は、各スイッチに関する情報と、各インターフェースに関する情報を含む。各インターフェースは、通信拠点に配置するスイッチにおいて、リンク部装置を構成する。装置情報は、（３−１）各スイッチのスロット数と、（３−２）各スイッチのコスト値と、（３−３）各インターフェースのトラヒック容量と、（３−４）各インターフェースのコスト値と、を含む。
【００４２】
（４）設計パラメータ情報は、（４−１）回線あたりの経路候補の数（経路候補数の上限値）と、（４−２）スイッチ組合せ候補の数（スイッチの組合せ候補数の設計値）と、（４−３）インターフェースの組合せ候補の数（インターフェースの組合せ候補数の設計値）と、を含む。
【００４３】
（全体の流れと各処理の概要）  
図３は、第１の実施形態におけるネットワーク設計装置の動作手順の一例を示すフローチャートである。
【００４４】
Ｓ１では、第１処理部１２の算出部１２ａが、回線ごとに、経路候補集合を算出する。Ｓ１では、算出部１２ａは、エンド間遅延に関する閾値である遅延上限値を、回線ごとに算出する。そして、算出部１２ａは、算出した遅延上限値に基づいて、経路候補集合を算出する。
【００４５】
Ｓ２−１では、第２処理部１３の第１算出部１３ａが、インターフェースの組合せ候補集合を算出する。
【００４６】
Ｓ２−２では、第２処理部１３の第２算出部１３ｂが、スイッチの組合せ候補集合を算出する。
【００４７】
Ｓ３は、Ｓ１、Ｓ２−１およびＳ−２の後に、Ｓ１、Ｓ２−１およびＳ２−２での算出結果に基づいて、行われる。Ｓ３では、第３処理部１４の算出部１４ａが、各回線を収容する最適な経路と、各通信拠点に配置される最適なスイッチの組合せ候補と、各通信拠点のスイッチに配置される最適なインターフェースの組合せ候補と、を算出する。そして、最適な経路候補、最適なスイッチの組合せ候補、および、最適なインターフェースの組合せ候補に基づいて、すなわち、Ｓ３での演算結果に基づいて、最適なネットワーク構成が算出される。
【００４８】
（各処理の詳細）
次にＳ１〜Ｓ３の詳細を説明する。  
<経路候補集合の算出（Ｓ１）>  
経路候補集合の算出（Ｓ１）では、第１処理部１２の算出部１２ａは、エンド間遅延に関する閾値である遅延上限値と、経路候補集合と、を回線ごとに算出する。遅延上限値および経路候補集合は、前述の（１−１）接続行列と、（１−２）各リンクの遅延時間と、（２−１）通信拠点ペアと、（２−３）エンド間遅延の許容度合いと、（４−１）回線あたりの経路候補の数とから、算出される。図４は、任意の回線について経路候補集合を算出する手順の一例を示すフローチャートである。
【００４９】
まず、Ｓ１−１において、第１処理部１２の算出部１２ａが、任意の回線を収容する経路について最小エンド間遅延を算出する。最小エンド間遅延は、その回線を収容する経路のエンド間遅延の中の、最小値である。算出部１２ａは、前述の（１−１）接続行列と、（１−２）各リンクの遅延時間と、（２−１）その回線の通信拠点ペアとから、最小エンド間遅延を算出する。例えば、算出部１２ａは、（１−１）接続行列と、（１−２）各リンクの遅延時間とから、重み付き無向グラフを作成する。そして、算出部１２ａは、作成した重み付き無向グラフにおいて、dijkstra法を用いて、最短経路と、その最短経路におけるリンクの重みの総和と、を算出する。この際、最短経路におけるリンクの重みの総和が、最小エンド間遅延として、算出される。
【００５０】
次に、Ｓ１−２において、第１処理部１２の算出部１２ａは、その回線の遅延上限値を算出する。算出部１２ａは、Ｓ１−１で算出した最小エンド間遅延と、（２−３）その回線のエンド間遅延の許容度合いとから、その回線の遅延上限値を算出する。例えば、最小エンド間遅延１、その回線のエンド間遅延の許容度合いを表す数値ｉを規定した場合、算出部１２ａは、遅延上限値の算出式を１×ｉとして、演算を行う。なお、前述のエンド間遅延の許容度合いを表す数値と、遅延上限値の算出式の設定とは一例であり、実施形態によって、任意の値や式を設定できる。したがって、エンド間遅延の許容度合いに応じた遅延上限値を、算出することができる。
【００５１】
次に、Ｓ１−３において、第１処理部１２の算出部１２ａは、（４−１）回線あたりの経路候補の数ｎから、判断を行う。すなわち、算出部１２ａは、経路候補集合内に既に含まれる経路候補の数がｎ未満であるか否かを、判定する。経路候補内に既に含まれる経路候補の数がｎ未満であれば（Ｓ１−３＿Ｙｅｓ）、処理はＳ１−４に進む。一方、経路候補集合に既に含まれる経路候補の数がｎ以上であれば（Ｓ１−３＿Ｎｏ）、第１処理部１２は、既に算出した経路候補を含む経路候補集合を出力する。そして、Ｓ１の処理を終了する。
【００５２】
Ｓ１−４では、第１処理部１２の算出部１２ａは、新しい経路ｒｉを算出する。この際、算出部１２ａは、（１−１）接続行列と、（１−２）各リンクの遅延時間と、（２−１）通信拠点のペアとから、新しい経路ｒｉを算出する。ここで、算出部１２ａは、Ｓ１−４の処理を繰り返すたびに、エンド間遅延の昇順に、新しい経路を算出する。この際、k-shortest path アルゴリズム（参考文献「Jin Y. Yen,“Finding the K Shortest Loopless Paths in a Network”, Management Science, vol.17, No.11, pp. 712-716, 1971」参照）を用いて、新しい経路が算出される。例えば、重み付きグラフＧ、始点ｓ、終点ｔが与えられたとする。k-shortest pathアルゴリズムでは、ｓからｔまでのループを含まないパスを、コストの小さい順にｋ本探索する。したがって、Ｓ１−４では、算出部１２ａは、k-shortest pathアルゴリズムによって、エンド間遅延が短い順に、新しい経路を算出する。
【００５３】
次に、Ｓ１−５では、第１処理部１２の算出部１２ａが、Ｓ１−４で算出した経路ｒｉのエンド間遅延を算出する。そして、算出部１２ａは、算出したエンド間遅延が、Ｓ１−２で算出した遅延上限値以下であるか否かを、判定する。新しい経路ｒｉのエンド間遅延が遅延上限値以下であれば（Ｓ１−５＿Ｙｅｓ）、処理は、Ｓ１−６に進む。一方、新しい経路ｒｉのエンド間遅延が遅延上限値より大きければ（Ｓ１−５＿Ｎｏ）、第１処理部１２は、既に算出した経路候補を含む経路候補集合を出力する。したがって、Ｓ１−４で算出した新しい経路ｒｉは、経路候補集合に含まれない。
【００５４】
次に、Ｓ１−６では、第１処理部１２の算出部１２ａが、Ｓ１−４で算出した経路ｒｉを１つの経路候補として、経路候補集合に追加する。そして、処理は、Ｓ１−３に戻る。
【００５５】
前述のようにＳ１−３〜Ｓ１−６が行われることにより、経路候補集合内の経路候補がｎ未満であり、かつ、新しい経路ｒｉのエンド間遅延が遅延上限値以下である限り、新しい経路ｒｉが、経路候補として経路候補集合に追加される。このため、Ｓ１で出力される任意の回線の経路候補集合では、経路候補の数が、ｎ以下であり、各経路候補のエンド間遅延は、その回線の遅延上限値以下となる。ここで、ｎは、前述のように、回線あたりの経路候補の数（経路候補数の上限値）であり、ネットワーク設計者によって入力される。
【００５６】
本実施形態では、各回線において、前述のＳ１の手順で経路候補集合を算出する。そして、Ｓ１で算出した各回線の経路候補集合は、Ｓ３の入力として用いる。
【００５７】
<インターフェースの組合せ候補集合の算出（Ｓ２−１）>
インターフェースの組合せ候補集合の算出（Ｓ２−１）では、第２処理部１３の第１算出部１３ａは、インターフェースの組合せ候補集合を算出する。第１算出部１３ａは、（３−３）各インターフェースのトラヒック容量と、（４−３）インターフェースの組合せ候補の数ｍとから、インターフェースの組合せ候補集合を算出する。算出されるインターフェースの組合せ候補集合は、インターフェースの組合せについてｍ個の組合せ候補を含む。各組合せ候補は、０個以上のインターフェースの組合せであり、各組合せ候補では、トラヒック容量が互いに対して同一の複数のインターフェースを重複して組合せてもよい。各組合せ候補は、使用されるインターフェースが０個である組合せも含む。図５は、インターフェースの組合せ候補集合を算出する手順の一例を示すフローチャートである。
【００５８】
まず、Ｓ２−１−１において、第２処理部１３の第１算出部１３ａは、（４−３）インターフェースの組合せ候補の数ｍから、判断を行う。すなわち、第１算出部１３ａは、インターフェースの組合せ候補集合内に既に含まれる組合せの候補の数がｍ未満であるか否かを、判定する。組合せ候補集合内に既に含まれる組合せ候補の数がｍ未満であれば（Ｓ２−１−１＿Ｙｅｓ）、処理はＳ２−１−２に進む。一方、組合せ候補集合内に既に含まれる候補の数がｍ以上であれば（Ｓ２−１−１＿Ｎｏ）、第２処理部１３は、既に算出した組わせ候補を含むインターフェースの組合せ候補集合を出力する。
【００５９】
次に、Ｓ２−１−２において、第２処理部１３の第１算出部１３ａは、インターフェースの新しい組合せＩを、１つ以上算出する。第１算出部１３ａは、（３−３）各インターフェースのトラフィック容量から、新しい組合せＩを算出する。この際、第１算出部１３ａは、複数の新しい組合せＩを算出してもよい。ただし、算出される複数の新しい組合せＩでは、インターフェースのトラフィック容量の合計値である総容量が、互いに対して同一である。また、算出される新しい各組合わせＩは、０個以上のインターフェースの組合せであり、各組合せＩでは、同一の種類の複数のインターフェースの重複を許容する。なお、トラヒック容量が互いに対して同一のインターフェースは、同一の種類のインターフェースに該当する。また、第１算出部１３ａは、Ｓ２−１−２の処理を繰り返すたびに、組合せに含まれるインターフェースの総容量の昇順に、新しい組合せＩを算出する。
【００６０】
次に、Ｓ２−１−３において、第２処理部１３の第１算出部１３ａは、（３−４）各インターフェースのコスト値から、Ｓ２−１−２で算出した新しい組合せＩの中の１つを選択する。この際、第１算出部１３ａは、組合せＩの中で、インターフェースのコスト値の合計値である総コスト値が最も低い１つの組合せを、選択する。そして、第１算出部１３ａは、組合せＩの中から選択した１つを、インターフェースの組合せ候補集合に追加する。
【００６１】
前述のようにＳ２−１−１〜Ｓ２−１−３が行われることにより、Ｓ２−１で出力されるインターフェースの組合せ候補集合では、組合せ候補が、ｍ個含まれ、各組合せ候補の総容量は互いに対して素である。すなわち、インターフェースの組合せ候補集合に含まれるｍ個の組合せ候補は、互いに対してインターフェースの総容量が異なる。また、各組合せ候補は、０個以上のインターフェースの組合せであり、各組合せ候補では、同一の種類の複数のインターフェースの重複を許容する。また、各組合せ候補は、候補番号を有する。候補番号は、１〜ｍの自然数で設定される。そして、候補番号が大きいほど、組合せに含まれるインターフェースの総容量が大きい。
【００６２】
本実施形態では、前述のＳ２−１の手順でインターフェースの組合せ候補集合を算出する。そして、Ｓ２−１で算出したインターフェースの組合せ候補集合は、Ｓ３の入力として用いる。
【００６３】
<スイッチの組合せ候補集合の算出（Ｓ２−２）>
スイッチの組合せ候補集合の算出（Ｓ２−２）では、第２処理部１３の第２算出部１３ｂは、スイッチの組合せ候補集合を算出する。第２算出部１３ｂは、（３−１）各スイッチのスロット数と、（４−２）スイッチの組合せ候補の数Ｍとから、スイッチの組合せ候補集合を算出する。算出されるスイッチの組合せ候補集合は、スイッチの組合せについてＭ個の組合せ候補を含む。各組合せ候補は、０個以上のスイッチの組合せであり、各組合せ候補では、スロット数が互いに対して同一の複数のスイッチを組合せてもよい。各組合せ候補は、使用されるスイッチが０個である組合せも含む。図６は、スイッチの組合せ候補集合を算出する手順の一例を示すフローチャートである。
【００６４】
まず、Ｓ２−２−１において、第２処理部１３の第２算出部１３ｂは、（４−２）スイッチの組合せ候補の数Ｍから、判断を行う。すなわち、第２算出部１３ｂは、スイッチの組合せ候補集合内に既に含まれる組合せ候補の数がＭ未満であるか否かを、判定する。組合せ候補集合内に既に含まれる組合せ候補の数がＭ未満であれば（Ｓ２−２−１＿Ｙｅｓ）、処理はＳ２−２−２に進む。一方、組合せ候補集合内に既に含まれる組合せ候補の数がＭ以上であれば（Ｓ２−２−１＿Ｎｏ）、第２処理部１３は、既に算出したインターフェースの組合せ候補集合を出力する。
【００６５】
次に、Ｓ２−２−２において、第２処理部１３の第２算出部１３ｂは、スイッチの新しい組合せＴを、１つ以上算出する。第２算出部１３ｂは、（３−１）各スイッチのスロット数から、新しい組合せＴを算出する。この際、第２算出部１３ｂは、複数の新しい組合せＴを算出してもよい。ただし、算出される複数の新しい組合せＴでは、スイッチのスロット数の合計値である総スロット数が、互いに対して同一である。また、算出される新しい各組合わせＴは、０個以上のスイッチの組合せであり、各組合せＴでは、同一の種類の複数のスイッチの重複を許容する。なお、スロット数が互いに対して同一のスイッチは、同一の種類のスイッチに該当する。また、第２算出部１３ｂは、Ｓ２−２−２の処理を繰り返すたびに、組合せに含まれるスイッチの総スロット数の昇順に、新しい組合せＴを算出する。
【００６６】
次に、Ｓ２−２−３において、第２処理部１３の第２算出部１３ｂは、（３−２）各スイッチのコスト値から、Ｓ２−２−２で算出した新しい組合せＴの中の１つを選択する。この際、第２算出部１３ｂは、組合せＴの中で、スイッチのコスト値の合計値である総コスト値が最も低い１つの組合せＴを、選択する。そして、第２算出部１３ｂは、組合せＴの中から選択した１つを、スイッチの組合せ候補集合に追加する。
【００６７】
前述のようにＳ２−２−１〜Ｓ２−２−３が行われることにより、Ｓ２−２で出力されるスイッチの組合せ候補集合では、組合せ候補が、Ｍ個含まれ、各組合せ候補の総スロット数は互いに対して素である。すなわち、スイッチの組合せ候補集合に含まれるＭ個の組合せ候補は、互いに対してスイッチの総スロット数が異なる。また、各組合せ候補は、０個以上のスイッチの組合せであり、各組合せ候補では、同一の種類の複数のスイッチの重複を許容する。また、各組合せ候補は、候補番号を有する。候補番号は、１〜Ｍの自然数で設定される。そして、候補番号が大きいほど、組合せに含まれるスイッチの総スロット数が大きい。
【００６８】
本実施形態では、前述のＳ２−２の手順でスイッチの組合せ候補集合を算出する。そして、Ｓ２−２で算出したスイッチの組合せ候補集合は、Ｓ３の入力として用いる。
【００６９】
<最適なネットワーク構成の算出（Ｓ３）>
最適なネットワーク構成の算出（Ｓ３）では、第３処理部１４の算出部１４ａは、目的関数を最小化する最適化問題を解く。この際、算出部１４ａは、経路候補集合からいずれの経路候補が選択されたかを表す変数と、各通信拠点に配置するスイッチの組合せ候補集合からいずれの組合せ候補が選択されたかを表す変数と、各スイッチの各リンク部に配置するインターフェースの候補集合からいずれの組合せ候補が選択されたかを表す変数と、を決定変数とする。経路候補集合からいずれの経路候補が選択されたかを表す変数は、回線ごとに設定される。また、スイッチの組合せ候補集合からいずれの組合せ候補が選択されたかを表す変数は、通信拠点ごとに設定される。また、インターフェースの組合せ候補集合からいずれの組合せ候補が選択されたかを表す変数は、リンクごとに設定される。また、算出部１４ａは、基盤ネットワークの総コスト値を導出する式を、目的関数とする。基盤ネットワークの総コスト値は、全スイッチの総コスト値と、全インターフェースの総コスト値の合計値である。前述の最適化問題を定式化した数式を以下に示す。
【００７０】
【数３】
2019161274.tif 000005
【００７１】
また、式（１）〜式（６）に関連するパラメータ等が示す事項は、以下の通りである。
【００７２】
【数４】
2019161274.tif 000006
【００７３】
Ｓ３の最適化問題では、各回線において、１つの経路候補を選択するための条件が制約条件として設けられる。この制約条件は、式（２）で示される。ここで、式（１）〜式（６）において、各回線について、経路候補集合Ｉから選択された組合せ候補の候補番号を、「ｉ」とする。変数ｘは、最適化問題の決定変数である。変数ｘは、回線ｖにおいて、経路候補集合Ｉから収容する経路として選択した経路候補ｉを示す。すなわち、各回線において、変数ｘは、経路候補集合Ｉからいずれの経路候補が選択されたかに対応して、変化する。
【００７４】
また、Ｓ３の最適化問題では、各リンクにおいて、１つのインターフェース組合せ候補を選択するための条件が制約条件として設けられる。この制約条件は、式（３）で示される。ここで、式（１）〜式（６）において、各リンクについて、インターフェースの組合せ候補集合Ｊから選択された組合せ候補の候補番号を、「ｊ」とする。変数ｙは、最適化問題の決定変数である。変数ｙは、リンクｅにおいて、インターフェース組合せ候補集合Ｊから選択した組合せ候補ｊを示す。すなわち、各リンクにおいて、変数ｙは、インターフェースの候補集合Ｊからいずれの組合せ候補が選択されたかに対応して、変化する。
【００７５】
また、Ｓ３の最適化問題では、各通信拠点において、１つのスイッチ組合せ候補を選択するための条件が制約条件として設けられる。この制約条件は、式（４）で示される。ここで、式（１）〜式（６）において、各通信拠点について、スイッチの組合せ候補集合Ｋから選択された組合せ候補の候補番号を、「ｋ」とする。変数ｚは、最適化問題の決定変数である。変数ｚは、通信拠点ｌにおいて、スイッチの組合せ候補集合Ｋから選択した組合せ候補ｋを示す。すなわち、各通信拠点において、変数ｚは、スイッチの組合せ候補集合Ｋからいずれの組合せ候補が選択されたかに対応して、変化する。
【００７６】
また、Ｓ３の最適化問題では、各リンクにおいて、容量条件が、制約条件として設けられる。容量条件は、総契約帯域がインターフェースの総容量を超えないための条件である。この制約条件は、式（５）で示される。ここで、式（１）〜式（６）において、変数ΨｊＩＦは、候補番号「ｊ」のインターフェースの組合せ候補が選択された際の、リンクｅあたりのインターフェースの総容量を示す。また、変数ｄは、回線ｖの契約帯域を示す。また、変数ｔｅは、リンクｅあたりの契約帯域の総和を示す。変数ｔｅは、変数ｘ、変数ｄおよび接続行列Ｍに基づいて、算出される。
【００７７】
また、Ｓ３の最適化問題では、各通信拠点において、スロット条件が、制約条件として設けられる。スロット条件は、全インターフェースを収容するために必要なスロット数が、スイッチの総スロット数を超えないための条件である。例えば、１スロットにつき１つが収容されるインターフェースのみが使用される場合、配置される全インターフェースを収容するために必要なスロット数は、配置されるインターフェースの総数となる。この制約条件は、式（６）で示される。ここで、式（１）〜式（６）において、変数ΨｋＴＥは、候補番号「ｋ」のスイッチの組合せ候補が選択された際の、通信拠点ｌあたりのスイッチのスロット数を示す。また、変数ｎｌは、通信拠点ｌにおけるインターフェースの総数を示す。変数ｎｌは、変数ｙ、変数ΨｊＩＦおよび接続行列Ｍに基づいて、算出される。
【００７８】
また、Ｓ３の最適化問題では、目的関数を、基盤ネットワークにおけるネットワーク全体の総コスト値とする。基盤ネットワークにおけるネットワーク全体の総コスト値は、全インターフェースの総コスト値と、全スイッチの総コスト値の合計値である。目的関数は、式（１）で示される。式（１）の目的関数は、選択された経路候補、インターフェースの組合せ候補、および、スイッチの組合せ候補に基づいて、算出される。
【００７９】
式（１）の目的関数においてΩｊＩＦは、リンク番号「ｅ」において候補番号「ｊ」のインターフェースの組合せ候補が選択された際の、リンクｅあたりのインターフェースの総コスト値を示す。また、式（１）の目的関数においてΩｋＴＥは、通信拠点番号「ｌ」において候補番号「ｋ」のスイッチの組合せ候補が選択された際の通信拠点ｌあたりのスイッチの総コスト値を示す。
【００８０】
Ｓ３では、経路候補集合Ｉから、経路候補ｉを回線ごとに選択する。また、インターフェースの組合せ候補集合Ｊから、インターフェースの組合せ候補ｊをリンクごとに選択する。また、スイッチの組合せ候補集合Ｋから、スイッチの組合せ候補ｋを通信拠点ごとに選択する。
【００８１】
そして、Ｓ３では、式（１）に示すように、基盤ネットワークにおける全インターフェースの総コスト値の総和を算出する。全インターフェースの総コスト値ΩｊＩＦの総和の算出では、まず、インターフェースの組合せ候補の総コスト値ΩｊＩＦをリンクごとに算出する。そして、全リンクの総コスト値の合計値を算出し、算出した合計値を２倍する。ここで、合計値を２倍するのは、各リンクの両端のそれぞれに、選択されたインターフェースの組合せ候補に含まれる各インターフェースが接続されるためである。
【００８２】
また、Ｓ３では、式（１）に示すように、基盤ネットワークにおける全スイッチの総コスト値の総和を算出する。全スイッチの総コスト値の総和の算出では、まず、スイッチの組合せ候補に含まれる総コスト値ΩｋＴＥを通信拠点ごとに算出する。そして、全通信拠点の総コスト値の合計値を算出する。
【００８３】
そして、算出されたインターフェースの総コスト値ΩｊＩＦの総和と、算出されたスイッチの総コスト値ΩｋＴＥをの総和と、を含む基盤ネットワークの総コスト値を算出する。
【００８４】
そして、Ｓ３では、式（１）に示すように、基盤ネットワークの総コスト値を目的関数とする。そして、目的関数を最小化する最適化問題を解く。
【００８５】
前述の最適化問題を解くことにより、基盤ネットワークにおけるネットワーク全体のコスト値の総和を最小にする、各回線の経路候補、各リンクのインターフェースの組合せ候補、および、各通信拠点のスイッチの組合せ候補を、導出する。すなわち、各回線における最適な決定変数ｘ、各リンクにおける最適な決定変数ｙ、および、各通信拠点における最適な決定変数ｚが、導出される。そして、導出された各回線の経路候補を、各回線の最適な経路候補とする。また、導出された各リンクのインターフェースの組合せ候補を、各リンクの最適なインターフェースの組合せ候補とする。そして、導出された各通信拠点のスイッチの組合せ候補を、各通信拠点の最適なスイッチの組合せ候補とする。
【００８６】
前述のように、第３処理部１４の算出部１４ａは、最適化問題を解くことで、各回線の最適な経路候補と、各通信拠点のリンク部の最適なインターフェースの組合せ候補と、各通信拠点の最適なスイッチの組合せ候補と、を算出する。そして、第３処理部１４は、算出した最適な経路候補、最適なインターフェースの組合せ候補、および、最適なスイッチの組合せ候補を、出力部１５に出力する。
【００８７】
Ｓ３が行われることにより、基盤ネットワークにおけるネットワーク全体の総コスト値を最も小さくする、最適な経路候補、最適なインターフェースの組合せ候補および最適なスイッチの組合せ候補が決定される。このため、最適化問題において、スイッチの組合せ候補の選択を決定変数にすることができる。
【００８８】
また、Ｓ３では、最適化問題において、基盤ネットワークにおけるネットワーク全体の総コスト値を目的関数とする。そして、基盤ネットワークの総コスト値は、インターフェースの総コスト値の総和と、スイッチの総コスト値の総和との合計値である。このため、最適化問題において、スイッチのコストが勘案された目的関数を設定することができる。
【００８９】
また、Ｓ３では、 各回線の経路候補および各リンクのインターフェースの組合せ候補から、各通信拠点におけるインターフェースの総数が算出され、算出された各通信拠点のインターフェースの総数に基づいて、各通信拠点のスイッチの組合せ候補が導出される。この際、スイッチのスロットの容量に関する前述の条件を満たすように、各通信拠点のスイッチの組合せ候補が導出される。これにより、適切なネットワーク構成が導出される。
【００９０】
（動作例）  
第１の実施形態の動作例を、入力情報の一例と、各処理の動作の一例に区分して説明する。
【００９１】
<入力情報の一例>  
・トポロジ情報  
図７は、トポロジの一例を示す図である。図８は、図７のトポロジの一例に用いる凡例を示す図である。すなわち、図８は、図７の一例で使用する記号等を説明する図である。図８において、通信拠点「１」は、通信拠点番号が１である通信拠点を示す。また、図８において、リンク「１」は、リンク番号が１であるリンクを示し、通信拠点「１」に接続している。
【００９２】
図７は、通信拠点間の接続状態を示す。詳しくは、通信拠点「１」〜通信拠点「４」に対応する通信拠点の、リンク「１」〜リンク「５」を介した接続状態を表す。図７の一例での通信拠点間の接続状態を表す接続行列Ｍを、以下の式（Ａ）に示す。
【００９３】
【数５】
2019161274.tif 000007
【００９４】
接続行列Ｍでは、各行が通信拠点に対応し、各列がリンクに対応する。リンクが通信拠点に接続している場合、接続行列Ｍの対応する部分に「１」を格納する。一方、リンクが通信拠点に接続していない場合、接続行列Ｍの対応する部分に「０」を格納する。
【００９５】
また、トポロジ情報として、各リンクにおける遅延時間の一例を、以下の表１に示す。表１では、通信拠点間の遅延時間が示される。
【００９６】
【表１】
2019161274.tif 000008
【００９７】
・回線情報  
次に、ネットワークに収容する回線に関する情報の一例を、以下の表２に示す。
【００９８】
【表２】
2019161274.tif 000009
【００９９】
表２の一例では、回線番号「１」である回線「１」は、通信拠点「１」と通信拠点「３」との間で契約帯域「１０」の通信を行う。そして、回線「１」は、エンド間遅延の許容度合いが「０」である。ここで、表２の一例では、エンド間遅延の許容度合いは、０または１の値が設定される。この一例では、エンド間遅延の許容度合いが１の場合は、許容度合いが高いと判断し、最短経路のエンド間遅延の２倍の遅延時間を、遅延上限値とする。一方、エンド間遅延の許容度合いが０の場合は、許容度合いが低いと判断し、最短経路のエンド間遅延を遅延上限値とする。
【０１００】
・装置情報  
次に、通信拠点に配置する転送装置（ネットワーク装置）であるスイッチ、および、スイッチのリンク部に設置するインターフェース（リンク部装置）に関する情報の一例を説明する。
【０１０１】
図９は、スイッチの一例を示す。図９の一例のスイッチは、スイッチ番号が「１」のスイッチ「１」であり、スロット「１−１」と、スロット「１−２」と、スロット「１−３」と、スロット「１−４」と、を有する。スイッチ「１」は、宛先が示されたデータを受信する。そして、スイッチ「１」は、データに示された宛先に基づいて、データを出力するスロットを決定する。これにより、データを出力するリンクが、決定される。
【０１０２】
スロットは、通信拠点とリンクとの接続部（リンク接続部）に相当する。また、スロットには、インターフェースが収容される。
【０１０３】
図１０は、図７に示す基盤ネットワークにおけるスイッチの配置の一例を示す。このため、図１０では、図７のトポロジにおけるスイッチ間の接続方法の一例が、示される。図１０の一例では、通信拠点「１」〜通信拠点「４」に、スイッチが設置される。そして、各スイッチのスロット間がリンクを介してケーブルで接続され、各通信拠点間が接続される。
【０１０４】
次に、スイッチに関する情報の一例を、以下の表３に示す。
【０１０５】
【表３】
2019161274.tif 000010
【０１０６】
表３の一例では、スイッチ番号が「１」〜「３」のスイッチに関する情報が示される。表３の一例では、スイッチ番号が「１」であるスイッチ「１」は、４つのスロットを有する。また、スイッチ「１」では、スロットあたりのトラヒック容量が１００Ｇｂｉｔ/ｓであるため、処理可能なトラヒック容量の総量が４００Ｇｂｉｔ/ｓとなる。なお、トラヒック容量の総量は、スイッチに設けられるスロットのトラヒック容量の合計値である。そして、スイッチ「１」は、コスト値が１である。
【０１０７】
また、インターフェースに関する情報の一例を、以下の表４に示す。
【０１０８】
【表４】
2019161274.tif 000011
【０１０９】
表４の一例では、インターフェース番号が「１」〜「３」のインターフェースに関する情報が示される。表４の一例では、インターフェース番号が「１」であるインターフェース「１」では、処理可能なトラヒック容量が１０Ｇｂｉｔ/ｓである。そして、インターフェース「１」は、１つのスロットに１つ設置可能であり、コスト値が１である。
・設計パラメータ情報  
設計パラメータ情報の一例を、以下の表５に示す。表５の一例では、設計パラメータ情報には、回線あたりの経路候補の数（経路候補数の上限値）、スイッチの組合せ候補の数（スイッチの組合せ候補数の設計値）、および、インターフェースの組合せ候補の数（インターフェースの組合せ候補数の設計値）が含まれる。
【０１１０】
【表５】
2019161274.tif 000012
【０１１１】
<各処理の動作の一例>  
・経路候補集合の算出（Ｓ１）  
まず、Ｓ１−１において、各回線の最小エンド間遅延を算出する。以下の表６は、各回線の最小エンド間遅延の一例を示す。表６では、例えば、本動作例において前述した入力情報が入力された場合の、最小エンド間遅延を示す。
【０１１２】
【表６】
2019161274.tif 000013
【０１１３】
表６の一例では、通信拠点「１」と通信拠点「３」との通信拠点ペア間では、リンク「１」と、通信拠点「２」と、リンク「２」とを通る経路、および、リンク「４」と、通信拠点「４」と、リンク「３」とを通る経路で、エンド間遅延が最小値になる。このため、リンク「１」と、通信拠点「２」と、リンク「２」とを通る経路でのエンド間遅延、または、リンク「４」と、通信拠点「４」と、リンク「３」とを通る経路でのエンド間遅延が、最小エンド間遅延として設定される。なお、前述の表１から、リンク「１」の遅延時間は２であり、リンク「２」の遅延時間は１である。このため、リンク「１」と、通信拠点「２」と、リンク「２」とを通る経路のエンド間遅延は、「２＋１＝３」になる。各回線は、通信拠点「１」と通信拠点「３」との通信拠点ペアを有する。したがって、各回線では、最小エンド間遅延は、「３」になる。
【０１１４】
次に、Ｓ１−２において、各回線の遅延上限値を算出する。以下の表７は、各回線の遅延上限値の一例を示す。表７では、例えば、本動作例において前述した入力情報が入力され、かつ、本動作例の表６のように最小エンド間遅延が算出された場合の、遅延上限値を示す。
【０１１５】
【表７】
2019161274.tif 000014
【０１１６】
表７の一例では、エンド間遅延の許容度合いが１である回線「１」と回線「２」は、許容度合いが高いと判断する。このため、回線「１」と回線「２」では、最小エンド間遅延の２倍の遅延時間を遅延上限値とし、遅延上限値は６になる。一方、エンド間遅延の許容度合いが０である回線「３」と回線「４」は、許容度合いが低いと判断する。このため、回線「３」と回線「４」では、最小エンド間遅延を遅延上限値とし、遅延上限値は３になる。
【０１１７】
次に、Ｓ１−３からＳ１−６において、各回線での経路候補を算出する。入力情報の一例に示す入力情報が入力された場合、表５で設定される回線あたりの経路候補の数３に基づいて、経路候補を算出する。このため、各回線で、最大３つの経路候補が算出される。以下の表８は、算出される各回線の経路候補の一例を示し、経路候補集合の一例を示す。表８では、例えば、本動作例において前述した入力情報が入力され、かつ、本動作例の表７のように遅延上限値が算出された場合の、経路候補集合を示す。
【０１１８】
【表８】
2019161274.tif 000015
【０１１９】
表８の一例では、回線「１」は、遅延上限値が「６」である。このため、回線「１」では、エンド間遅延が「３」である経路「１−１」と「１−２」、および、エンド間遅延が「４」である経路「１−３」を、経路候補とする。一方、回線「３」は、遅延上限値「３」である。このため、回線「３」では、エンド間遅延が「３」である経路「３−１」と「３−２」のみを、経路候補とする。
【０１２０】
・インターフェースの組合せ候補集合の算出（Ｓ２−１）
以下の表９は、算出されるインターフェースの組合せ候補集合の一例を示す。表９では、例えば、本動作例で前述した入力情報が入力された場合の、インターフェースの組合せ候補集合を示す。
【０１２１】
【表９】
2019161274.tif 000016
【０１２２】
インターフェースの組合せ候補集合の算出では、Ｓ２−１−２を繰り返すごとに、インターフェースの新しい組合せを１つ以上算出する。Ｓ２−１−２では、算出される新しい組合せに含まれるインターフェースの総容量は、毎回異なり、Ｓ２−１−２の処理を繰り返すたびに、総容量の昇順に、新しい組合せが算出される。このため、Ｓ２−１−２では、算出される新しい組合せに含まれるインターフェースは、毎回異なる組合せになる。
【０１２３】
例えば、Ｓ２−１−２で、総容量が「４０Ｇｂｉｔ/ｓ」のインターフェースの組合せが算出される場合について、説明する。この場合、総容量が「４０Ｇｂｉｔ/ｓ」のインターフェースの組合せとして、容量が「１０Ｇｂｉｔ/ｓ」のインターフェースが４つ含まれる組合せと、容量が「４０Ｇｂｉｔ/ｓ」のインターフェースが１つ含まれる組合せと、が算出される。
【０１２４】
そして、Ｓ２−１−３において、Ｓ２−１−２で算出された組合せの総コスト値を算出する。ここで、容量が「１０Ｇｂｉｔ/ｓ」のインターフェースが４つ含まれる組合せの総コスト値は、「１＊４＝４」で、容量が「４０Ｇｂｉｔ/ｓ」のインターフェースが１つ含まれる組合せの総コスト値は「３＊１＝３」である。すなわち、Ｓ２−１−２で算出された組合せの中では、容量が「４０Ｇｂｉｔ/ｓ」のインターフェースが１つ含まれる組合せが、総コスト値が最も低い。このため、Ｓ２−１−３では、容量が「４０Ｇｂｉｔ/ｓ」のインターフェースが１つ含まれる組合せを、インターフェースの組合せ候補集合に、組合せ候補として追加する。
【０１２５】
そして、本動作例で前述した入力情報が入力された場合、表５で設定されるインターフェースの組合せ候補の数１０に基づいて、Ｓ２−１−１の処理が行われる。すなわち、Ｓ２−１−１で、算出した組合せ候補が１０個未満か否かを判定する。これにより、インターフェースの組合せについて、総容量が互いに異なる１０個の組合せ候補が、算出される。また、組合せ候補には、候補番号「１」〜「１０」が設定される。
【０１２６】
・スイッチの組合せ候補集合の算出（Ｓ２−２）
以下の表１０は、算出されるスイッチの組合せ候補集合の一例を示す。表１０では、例えば、本動作例で前述した入力情報が入力された場合の、スイッチの組合せ候補集合を示す。
【０１２７】
【表１０】
2019161274.tif 000017
【０１２８】
スイッチの組合せ候補集合の算出では、Ｓ２−２−２を繰り返すごとに、スイッチの新しい組合せを１つ以上算出する。Ｓ２−２−２では、算出される新しい組合せに含まれるスイッチの総スロット数は、毎回異なり、Ｓ２−２−２の処理を繰り返すたびに、総スロット数の昇順に、新しい組合せが算出される。このため、Ｓ２−２−２では、算出される新しい組合せに含まれるスイッチは、毎回異なる組合せになる。
【０１２９】
例えば、Ｓ２−２−２で、総スロット数が「１６」のスイッチの組合せが算出される場合について、説明する。この場合、総スロット数が「１６」のスイッチの組合せとして、スロット数が「４」のスイッチが４つ含まれる組合せと、スロット数が「４」のスイッチが２つとスロット数が「８」のスイッチが１つ含まれる組合せと、スロット数が「１６」のスイッチが１つ含まれる組合せと、が算出される。
【０１３０】
ここで、Ｓ２−２−２で算出された組合せの中では、スロット数が「１６」のスイッチが１つ含まれる組合せが、スイッチ数が最も少ない。このため、Ｓ２−２−３では、スロット数が「１６」のスイッチが１つ含まれる組合せを、スイッチの組合せ候補集合に、組合せ候補として追加する。
【０１３１】
そして、本動作例で前述した入力情報が入力された場合、表５で設定されるスイッチの組合せ候補の数１０に基づいて、Ｓ２−２−１の処理が行われる。すなわち、Ｓ２−２−１で、算出した組合せ候補が１０個未満か否かを判定する。これにより、スイッチの組合せについて、総スロット数が互いに異なる１０個の組合せ候補が、算出される。また、組合せ候補には、候補番号「１」〜「１０」が設定される。
【０１３２】
・最適なネットワーク構成の算出（Ｓ３）
Ｓ３では、前述の最適化問題を解く。表１１は、最適化問題において算出される各回線の最適な経路候補の一例を示す。例えば、本動作例で、前述したようにＳ１、Ｓ２が行われた場合は、表１１のように各回線の最適な経路候補が算出される。表１２は、最適化問題において算出される各リンクの最適なインターフェースの組合せ候補の一例を示す。例えば、本動作例で、前述したようにＳ１、Ｓ２が行われた場合は、表１２のように各リンクの最適なインターフェースの組合せ候補が算出される。表１３は、最適化問題において算出される各通信拠点の最適なスイッチの組合せ候補の一例を示す。例えば、本動作例で、前述したようにＳ１、Ｓ２が行われた場合は、表１３のように各通信拠点の最適なスイッチの組合せ候補が算出される。
【０１３３】
【表１１】
2019161274.tif 000018
【０１３４】
【表１２】
2019161274.tif 000019
【０１３５】
【表１３】
2019161274.tif 000020
【０１３６】
すなわち、本動作例で前述したようにＳ１、Ｓ２が行われた場合、回線「１」については経路「１−１」が、回線「２」については経路「２−１」が、回線「３」については経路「３−１」が、回線「４」について経路「４−１」が、最適な経路候補として算出される。
【０１３７】
また、Ｓ３では、選択された各回線の経路候補に基づいて、各リンクの総契約帯域ｔｅを算出する。表１１の一例では、回線「１」〜「４」では、リンク「１」とリンク「２」とを使用する経路候補が、最適な経路として算出されている。したがって、例えば、リンク「１」およびリンク「２」には、契約帯域が「１０Ｇｂｉｔ/ｓ」である回線が４つ収容される。このため、リンク「１」およびリンク「２」では、総契約帯域は、「１０＋１０＋１０＋１０＝４０Ｇｂｉｔ/ｓ」となる。また、リンク「３」と、リンク「４」と、リンク「５」には、回線は収容されない。このため、リンク「３」とリンク「４」とリンク「５」の総契約帯域は、「０」となる。
【０１３８】
また、表１２に示すように、本動作例で前述したようにＳ１、Ｓ２が行われた場合、リンク「１」〜「２」については候補番号「５」の組合せ候補が、リンク「３」〜「５」については組合せ候補「１」が、最適なインターフェースの組合せ候補として算出される。式（５）に示すように、各リンクでは、算出された組合せ候補でのインターフェースの総容量は、総契約帯域以上となる。
【０１３９】
リンク「１」では、候補番号「５」の組合せ候補が、最適なインターフェースの組合せ候補として算出されている。このため、リンク「１」が接続されるリンク部には、インターフェース「２」が１つずつ設置される。したがって、通信拠点「１」および通信拠点「２」では、リンク「１」に対応するリンク部には、インターフェース「２」が１つずつ設置される。
【０１４０】
同様に、リンク「２」では、候補番号「５」の組合せ候補が、最適なインターフェースの組合せ候補として算出されているため、通信拠点「２」および通信拠点「３」では、リンク「１」に対応するリンク部には、インターフェース「２」が１つずつ設置される。
【０１４１】
また、リンク「３」〜「５」では、候補番号「１」の組合せ候補が、最適なインターフェースの組合せ候補として算出されている。このため、リンク「３」〜「５」が接続されるリンク部には、インターフェースは設置されない。
【０１４２】
したがって、リンク「１」〜「５」を含む基盤ネットワーク上には、コスト値が３であるインターフェース「２」が、合わせて４つ設置されている。このため、基盤ネットワーク上における、全インターフェースのコスト値の総和は、「２＊（３＋３＋０＋０＋０）＝１２」となる。
【０１４３】
また、Ｓ３では、選択された各回線の経路候補、および、選択された各リンクのインターフェースの組合せ候補に基づいて、各通信拠点についてインターフェースの総数を算出する。
【０１４４】
表１１および表１２の一例では、例えば、通信拠点「１」では、リンク「１」に対応するリンク部に、インターフェース「２」が１つ設置される。インターフェース「２」は、スイッチの１スロットにつき１つ収容される。このため、通信拠点「１」では、設置されるインターフェースの総数は「１」となり、設置されるインターフェースを収容するために必要なスロット数は、「１」となる。
【０１４５】
また、例えば、通信拠点「２」では、リンク「１」に対応するリンク部に、インターフェース「２」が１つ設置され、リンク「２」に対応するリンク部に、インターフェース「２」が１つ設置される。インターフェース「２」は、スイッチの１スロットにつき１つ収容される。このため、通信拠点「２」では、設置されるインターフェースの総数は「２」となり、設置されるインターフェースを収容するために必要なスロット数は、「２」となる。
【０１４６】
同様に、通信拠点「３」〜「４」においても、対応するリンク部に設置されるインターフェースに基づいて、設置されるインターフェースの総数が、算出される。
【０１４７】
また、表１３に示すように、本動作例で前述したようにＳ１、Ｓ２が行われた場合、通信拠点「１」〜「３」については組合せ候補「２」が、通信拠点「４」については組合せ候補「１」が、最適なスイッチの組合せ候補として算出される。  通信拠点「１」〜「３」では、候補番号「２」の組合せが算出されたため、スロット数が「４」であるスイッチ「１」が、１つ配置されている。このため、通信拠点「１」〜「３」では、配置されるスイッチの総スロット数は「４」となり、設置されるインターフェースの総数以上である。すなわち、通信拠点「１」〜「３」では、配置されるスイッチの総スロット数は、設置されるインターフェースを収容するために必要なスロット数以上である。
【０１４８】
また、通信拠点「４」では、候補番号「１」の組合せが選択されたため、スイッチは配置されない。通信拠点「４」においても、配置されるスイッチの総スロット数は、設置されるインターフェースの総数、すなわち、設置されるインターフェースを収容するために必要なスロット数以上である。
【０１４９】
通信拠点「１」〜「３」では、コスト値が「１」であるスイッチ「１」が１つ配置されているため、設置されるスイッチの総コスト値は１となる。通信拠点「４」では、スイッチが配置されないため、設置されるスイッチの総コスト値は０となる。このため、通信拠点「１」〜「４」を含む基盤ネットワーク上における、全スイッチの総コスト値の総和は、「１＋１＋１+０=３」となる。
【０１５０】
前述のように、本動作例では、基盤ネットワークにおけるネットワーク全体において、全インターフェースの総コスト値の総和は「１２」となり、全スイッチの総コスト値の総和は「３」となる。このため、基盤ネットワークにおけるネットワーク全体の総コスト値は、「１２＋３＝１５」となり、最小値になる。
【０１５１】
そして、前述のように導出された各回線の最適な経路候補、各リンクの最適なインターフェースの組合せ候補、および、各通信拠点の最適なスイッチの組合せ候補に基づいて、最適なネットワーク構成、すなわち、ネットワークにおける最適な配置例が生成および出力される。図１１は、ネットワークにおける最適な配置例の一例を示す。図１１は、表１１のように各回線の最適な経路候補が算出され、かつ、表１２のように各リンクの最適なインターフェースの組合せ候補が算出され、かつ、表１３のように各通信拠点の最適なスイッチの組合せ候補が算出された場合の配置例を示す。
【０１５２】
図１１に示す最適な配置例では、通信拠点「１」〜「３」にのみスイッチ（転送装置）が配置され、通信拠点「４」には、スイッチ（転送装置）が配置されない。そして、通信拠点「１」〜「３」のそれぞれでは、リンク「１」およびリンク「２」のリンク部にのみ、インターフェース「２」の種類のインターフェースが設置される。そして、リンク「３」〜「５」のリンク部には、インターフェースは設置されない。
【０１５３】
（作用及び効果）  
本実施形態では、インターフェースの総コスト値に加えて、スイッチの総コスト値を勘案している。このため、インターフェースの総コスト値のみを勘案した場合に比べて、基盤ネットワークにおけるネットワーク全体の総コスト値を低減できる、最適なネットワーク構成を導くことができる。
【０１５４】
ここで、最適なネットワーク構成の算出において、基盤ネットワークにおけるネットワーク全体の総コスト値として、インターフェースのコスト値のみを勘案した比較例を考える。前述の動作例のように、ネットワーク基盤において、４つ回線と、５つのリンクが存在するとする。
【０１５５】
比較例では、最適なネットワーク構成の算出において、各回線において選択された経路候補を示す変数、および、各リンクにおいて選択されたインターフェースの組合せ候補を示す変数のみを、最適化問題の決定変数とする。また、全インターフェースの総コスト値の総和のみを、目的関数とする。このため、比較例では、各通信拠点において選択されたスイッチ組合せ候補を示す変数は、決定変数として用いない。また、全スイッチの総コスト値の総和は、目的関数に含まれず、スイッチのスロット条件は、制約条件として設けられない。なお、比較例では、非特許文献１のＳ´３と同様にして、最適化問題を解く。
【０１５６】
表１４は、比較例において、最適化問題において算出される各回線の最適な経路候補の一例を示す。表１５は、比較例において、最適化問題において算出される各リンクの最適なインターフェースの組合せ候補の一例を示す。表１６は、比較例において、最適化問題において算出される各通信拠点の最適なスイッチの組合せ候補の一例を示す。図１２は、表１４のように各回線の最適な経路候補が算出され、かつ、表１５のように各リンクの最適なインターフェースの組合せ候補が算出され、かつ、表１６のように各通信拠点の最適なスイッチの組合せ候補が算出された場合の配置例を示す。
【０１５７】
【表１４】
2019161274.tif 000021
【０１５８】
【表１５】
2019161274.tif 000022
【０１５９】
【表１６】
2019161274.tif 000023
【０１６０】
表１４に示すように、比較例では、回線「１」については経路「１−３」が、回線「２」については経路「２−３」が、回線「３」については経路「３−１」が、回線「４」について経路「４−２」が、最適な経路候補として算出される。
【０１６１】
したがって、例えば、リンク「１」〜「４」には、契約帯域が「１０Ｇｂｉｔ/ｓ」である回線が１つ収容される。このため、リンク「１」〜「４」では、総契約帯域は、「１０Ｇｂｉｔ/ｓ」となる。また、リンク「５」には、契約帯域が「１０Ｇｂｉｔ/ｓ」である回線が２つ収容される。このため、リンク「５」の総契約帯域は、「１０＋１０＝２０Ｇｂｉｔ/ｓ」となる。
【０１６２】
また表１５に示すように、比較例では、リンク「１」〜「４」については候補番号「２」の組合せ候補が、リンク「５」については候補番号「３」の組合せ候補が、最適なインターフェースの組合せ候補として算出される。式（４）´に示すように、各リンクでは、算出された組合せ候補でのインターフェースの総容量は、総契約帯域以上となる。
【０１６３】
リンク「１」では、候補番号「２」の組合せ候補が、最適なインターフェースの組合せ候補として算出されている。このため、リンク「１」が接続されるリンク部には、インターフェース「１」が１つずつ設置される。したがって、通信拠点「１」と通信拠点「２」においてリンク「１」対応するリンク部には、インターフェース「１」が１つずつ設置される。
【０１６４】
同様に、リンク「２」〜「５」においても、最適なインターフェース組合せ候補として算出された組合せ候補に基づいて、対応する通信拠点のリンク部のそれぞれに、インターフェースが設置される。
【０１６５】
比較例では、リンク「１」〜「５」を含む基盤ネットワーク上には、コスト値が１であるインターフェース「１」が、合わせて１２個設置されている。このため、基盤ネットワーク上における、全インターフェースのコスト値の総和は、「１＊１２＝１２」となる。
【０１６６】
また、表１６に示すように、本変形例では、通信拠点「１」〜「４」について、組合せ候補番号「２」の組合せ候補が、最適なスイッチの組合せ候補として算出されている。通信拠点「１」〜「４」では、候補番号「２」の組合せが算出されたため、コスト値が「１」であるスイッチ「１」が１つ配置されている。したがって、通信拠点「１」〜「４」では、設置されるスイッチの総コスト値は「１」となる。このため、通信拠点「１」〜「４」を含む基盤ネットワークにおける、全スイッチの総コスト値の総和は、「１＋１＋１＋１＝４」となる。
【０１６７】
前述のように、比較例では、全インターフェースの総コスト値は「１２」となり、全スイッチの総コスト値の総和は「４」となる。このため、基盤ネットワークにおけるネットワーク全体の総コスト値は、「１２＋４＝１６」となる。
【０１６８】
比較例において算出された最適なネットワーク構成では、基盤ネットワークにおけるネットワーク全体の総コスト値は、本実施形態の動作例において算出されたネットワーク構成における基盤ネットワークにおけるネットワーク全体の総コスト値よりも大きく、最小値ではない。すなわち、比較例のように、インターフェースのコスト値のみを最適化問題の目的関数として用いた場合、基盤ネットワークにおけるネットワーク全体の総コスト値が最小値とならないネットワーク構成が、最適なネットワーク構成として導出されることがある。
【０１６９】
一方、本実施形態では、基盤ネットワークにおけるネットワーク全体の総コスト値として、インターフェースの総コスト値に加えて、スイッチの総コスト値を勘案している。このため、比較例で算出されたネットワーク構成は、本実施形態の動作例で算出されたネットワーク構成よりも総コスト値が大きいため、最適なネットワーク構成として導出されない。このように、本実施形態では、リンク部装置のコスト値に加えて、転送装置の総コスト値を勘案することにより、基盤ネットワークにおけるネットワーク全体の総コスト値が低減される最適なネットワーク構成を、導くことができる。
【０１７０】
なお、各実施形態に記載した手法は、計算機（コンピュータ）に実行させることができるプログラム（ソフトウエア手段）として、例えば磁気ディスク（フロッピー（登録商標）ディスク、ハードディスク等）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤ、ＭＯ等）、半導体メモリ（ＲＯＭ、ＲＡＭ、フラッシュメモリ等）等の記録媒体に格納し、また通信媒体により伝送して頒布することもできる。なお、媒体側に格納されるプログラムには、計算機に実行させるソフトウエア手段（実行プログラムのみならずテーブルやデータ構造も含む）を計算機内に構成させる設定プログラムをも含む。本装置を実現する計算機は、記録媒体に記録されたプログラムを読み込み、また場合により設定プログラムによりソフトウエア手段を構築し、このソフトウエア手段によって動作が制御されることにより上述した処理を実行する。なお、本明細書でいう記録媒体は、頒布用に限らず、計算機内部あるいはネットワークを介して接続される機器に設けられた磁気ディスクや半導体メモリ等の記憶媒体を含むものである。
【０１７１】
また、本発明は、上記実施形態に限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。また、各実施形態は適宜組み合わせて実施してもよく、その場合組み合わせた効果が得られる。更に、上記実施形態には種々の発明が含まれており、開示される複数の構成要件から選択された組み合わせにより種々の発明が抽出され得る。例えば、実施形態に示される全構成要件からいくつかの構成要件が削除されても、課題が解決でき、効果が得られる場合には、この構成要件が削除された構成が発明として抽出され得る。
【符号の説明】
【０１７２】
１０…ネットワーク設計装置、１１…入力部、１２…第１処理部、１２ａ…算出部、１３…第２処理部、１３ａ…第１算出部、１３ｂ…第２算出部、１４…第３処理部、１４ａ…算出部、１５…出力部。
【図１】
2019161274.tif 000024
【図２】
2019161274.tif 000025
【図３】
2019161274.tif 000026
【図４】
2019161274.tif 000027
【図５】
2019161274.tif 000028
【図６】
2019161274.tif 000029
【図７】
2019161274.tif 000030
【図８】
2019161274.tif 000031
【図９】
2019161274.tif 000032
【図１０】
2019161274.tif 000033
【図１１】
2019161274.tif 000034
【図１２】
2019161274.tif 000035