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