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