(57)【要約】【課題】トラヒックデマンドが時刻変動する場合であっても、運用コストの増加を抑制した上で最適なネットワーク設計を実行することができる、ネットワーク設計装置およびネットワーク設計プログラムを提供する。【解決手段】ネットワーク設計装置１は、物理リンクのトポロジ情報、時刻毎の対地間のトラヒックデマンド情報、物理リンクおよび物理網上に波長パスを設定する波長ノードの設備に関する定数情報、論理網を構成するＩＰルータおよび論理リンクの設備に関する定数情報、ネットワーク設計の対象となる時刻情報を取得し、数理計画法を用いて、ネットワーク設計を実行する各時刻に共通のＩＰトラヒック経路、各時刻の波長パス経路および波長パスの本数、並びに、ネットワーク設計の対象期間において必要となる必要設備量を計算する。【選択図】図３
2014165690.tif 000002
【特許請求の範囲】
【請求項１】
波長ノード間の波長パスが物理リンクにより構成される物理網上に設定され、前記設定された波長パスが論理網においてＩＰルータ間の論理リンクを構成し、前記論理網にＩＰトラヒック経路が設定されるＩＰネットワークのネットワーク設計を行うネットワーク設計装置であって、
前記物理リンクのトポロジ情報、各時刻の前記ＩＰルータ間のトラヒックデマンド情報、前記物理リンクおよび前記波長ノードの設備に関する定数情報、前記ＩＰルータおよび前記論理リンクの設備に関する定数情報、並びに、ネットワーク設計を実行する前記各時刻の時刻情報を含む初期情報が記憶される記憶部と、
前記初期情報を入出力部を介して外部から取得し、前記記憶部に記憶する初期情報取得部と、
前記初期情報を参照し、数理計画法を用いて、前記数理計画法の目的関数において、前記ＩＰネットワークの設備量を最小化させるようにして、前記各時刻において共通のＩＰトラヒック経路、前記各時刻毎の、前記波長パスの経路および前記波長パスの本数、並びに、前記ネットワーク設計の設計期間内において必要となる必要設備量を計算する経路設備量計算部と、
を備えることを特徴とするネットワーク設計装置。
【請求項２】
前記経路設備量計算部は、
前記ネットワーク設計の設計期間内の初期時刻（τ＝０）において、前記初期時刻における第１の前記数理計画法を用いて、前記初期時刻の次の時刻（τ＝１）において設定すべき、前記ＩＰトラヒック経路、前記波長パスの経路および前記波長パスの本数、並びに、前記必要設備量を計算する初期時刻計算部と、
前記初期時刻計算部が計算した初期時刻（τ＝０）における前記ＩＰトラヒック経路を前記次の時刻以降（τ≧１）に計算する前記各時刻において共通のＩＰトラヒック経路とし、前記次の時刻以降の各時刻において、当該各時刻における第２の前記数理計画法を用いて、当該各時刻の次の時刻において設定すべき、前記波長パスの経路および前記波長パスの本数、並びに、前記必要設備量を計算する各時刻計算部と、
前記初期時刻および前記次の時刻以降の各時刻において計算された前記必要設備量を総計し、前記ネットワーク設計の設計期間内において必要となる総設備量を計算する総設備量計算部と、
を備えることを特徴とする請求項１に記載のネットワーク設計装置。
【請求項３】
前記初期情報取得部は、以下の（定義の表１）に示す第１の定数情報を前記初期情報として取得し、
前記初期時刻計算部は、以下の(定義の表１)に示す第１の変数情報について、第１の前記数理計画法による、以下の目的関数（Ａ１）および制約式（Ｂ１）を用いて、前記初期時刻における、前記ＩＰトラヒック経路、前記波長パスの経路および前記波長パスの本数、並びに、前記必要設備量を計算すること、
を特徴とする請求項２に記載のネットワーク設計装置。
【表１】
2014165690.tif 000027
【数１７】
2014165690.tif 000028
【数１８】
2014165690.tif 000029
【請求項４】
前記初期情報取得部は、以下の（定義の表２）に示す第２の定数情報を前記初期情報として取得し、
前記各時刻計算部は、以下の（定義の表２）に示す第２の変数情報について、第２の前記数理計画法による、以下の目的関数（Ａ２）および制約式（Ｂ２）を用いて、前記次の時刻以降の各時刻における、前記波長パスの経路および前記波長パスの本数、並びに、前記必要設備量を計算すること、
を特徴とする請求項３に記載のネットワーク設計装置。
【表２】
2014165690.tif 000030
【数１９】
2014165690.tif 000031
【数２０】
2014165690.tif 000032
【請求項５】
前記経路設備量計算部は、
前記ネットワーク設計を実行する前記各時刻の全てをまとめて処理対象とし、全時刻における第３の前記数理計画法を用いて、前記各時刻において共通のＩＰトラヒック経路、前記各時刻における、前記波長パスの経路および前記波長パスの本数、並びに、前記ネットワーク設計の設計期間内において必要となる総設備量を計算する全時刻計算部を備えること、
を特徴とする請求項１に記載のネットワーク装置。
【請求項６】
前記初期情報取得部は、以下の（定義の表３）に示す第３の定数情報を前記初期情報として取得し、
前記全時刻計算部は、以下の（定義の表３）に示す第３の変数情報について、第３の前記数理計画法による、以下の目的関数（Ａ３）および制約式（Ｂ３）を用いて、前記各時刻において共通のＩＰトラヒック経路、前記各時刻における、前記波長パスの経路および前記波長パスの本数、並びに、前記総設備量を計算すること、
を特徴とする請求項５に記載のネットワーク装置。
【表３】
2014165690.tif 000033
【数２２】
2014165690.tif 000034
【数２３】
2014165690.tif 000035
2014165690.tif 000036
【請求項７】
波長ノード間の波長パスが物理リンクにより構成される物理網上に設定され、前記設定された波長パスが論理網においてＩＰルータ間の論理リンクを構成し、前記論理網にＩＰトラヒック経路が設定されるＩＰネットワークのネットワーク設計を行うためのコンピュータを、
前記物理リンクのトポロジ情報、各時刻の前記ＩＰルータ間のトラヒックデマンド情報、前記物理リンクおよび前記波長ノードの設備に関する定数情報、前記ＩＰルータおよび前記論理リンクの設備に関する定数情報、並びに、ネットワーク設計を実行する前記各時刻の時刻情報を含む初期情報が記憶される記憶手段、
前記初期情報を入出力手段を介して外部から取得し、前記記憶手段に記憶する初期情報取得手段、
前記初期情報を参照し、数理計画法を用いて、前記数理計画法の目的関数において、前記ＩＰネットワークの設備量を最小化させるようにして、前記各時刻において共通のＩＰトラヒック経路、前記各時刻毎の、前記波長パスの経路および前記波長パスの本数、並びに、前記ネットワーク設計の設計期間内において必要となる必要設備量を計算する経路設備量計算手段、
として機能させるためのネットワーク設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、波長パスが物理トポロジ上に設定され、ＩＰ（Internet Protocol）トラヒックが波長パスにより構成された論理トポロジ上に設定された光ＩＰネットワークにおける、ネットワーク設計装置およびネットワーク設計プログラムに関する。
【背景技術】
【０００２】
光ＩＰネットワークは、波長パスが物理トポロジ（物理網）上に設定され、ＩＰトラヒックが波長パスで構成された論理トポロジ（論理網）上に設定される。
図１に示すように、光ＩＰネットワーク１００では、物理レイヤ上の波長レイヤに、波長パスが設定されたＷＤＭ（Wavelength Division Multiplexing）ネットワークを構成する。物理網は、転送ノード、伝送ノードおよびそれらを結ぶ物理リンクから構成される。ここで、転送ノードは、例えばＩＰルータ等である。伝送ノード（波長ノード）は、例えば、ＯＸＣ（Optical Cross Connect：光クロスコネクト）等である。また、物理リンクは、例えば、光ファイバ等である。そして、伝送ノード（ＯＸＣ等）を始終点とした波長パスが物理網上に設定され、その波長パスがＩＰレイヤでは転送ノード（ＩＰルータ）間における論理的なリンク（論理リンク）を構成する。
【０００３】
この光ＩＰネットワーク１００では、波長パス経路およびＩＰトラヒック経路を最適化することにより、ネットワーク全体の資源を有効活用し、転送品質を維持し、ネットワークコストを低減することが求められる。
そして、この波長パス経路およびＩＰトラヒック経路等を最適化するためには、波長パス経路とＩＰトラヒック経路とをそれぞれ独立に設定するのではなく、両者を同時に考慮して最適化することが重要となる。
【０００４】
具体的には、物理トポロジ上の波長パスの経路を表す変数とＩＰトラヒックの経路を表す各変数に対して、設備量をこれらの変数を用いた式で表した目的関数を設定し、各変数に関する制約式のもとで設備量を最小化させるようにして目的関数を解く数理計画法を適用する。そして、この数理計画法に基づき、物理トポロジ上の波長パスの経路を表す変数と、ＩＰトラヒックの経路を表す変数とを同時に解くことで最適解を得る手法が開示されている（非特許文献１参照）。この数理計画法における目的関数は、以下の（式１５）で表される。また、各変数の制約式は、以下の（式１）〜（式１４）で表される。
【０００５】
（数理計画法の制約式）
以下、まず、非特許文献１に記載の手法による、数理計画法の制約式（式１）〜（式１４）について説明する。
【０００６】
以下の（式１）は、ルータｓを始点とし、ルータｄを終点とする交流トラヒックにおいて、ルータｉ，ｊを端点とする論理リンクの少なくとも１つを通る交流トラヒック量の割合ｒｓ，ｄｉ，ｊが、０から１のいずれかの値をとることを示している。なお、このｒｓ，ｄｉ，ｊは、ＩＰトラヒック経路を表すこととなる。
【数１】
2014165690.tif 000003
【０００７】
以下の（式２）は、ルータｓを始点とし、ルータｄを終点とする交流トラヒックにおいて、ルータｓを端点とする全ての論理リンクを通る交流トラヒック量の割合の合計が、１となることを示している。
【数２】
2014165690.tif 000004
【０００８】
以下の（式３）は、ルータｓを始点とし、ルータｄを終点とする交流トラヒックにおいて、ルータｄを端点とする全ての論理リンクを通る交流トラヒック量の割合の合計が、１となることを示している。
【数３】
2014165690.tif 000005
【０００９】
以下の（式４）は、ルータｓを始点とし、ルータｄを終点とする交流トラヒックにおいて、ルータｋを一方の端点とする全ての論理リンクを通る交流トラヒック量の割合の合計と、ルータｋを他方の端点とする全ての論理リンクを通る交流トラヒック量の割合の合計とが同一となることを示している。すなわち、（式４）は、中間ルータｋにおいて、入力される交流トラヒック量と、出力される交流トラヒック量とが同一になることを示している。
【数４】
2014165690.tif 000006
【００１０】
以下の（式５）の左辺によって、ルータｉ，ｊを端点とする論理リンクを通る交流トラヒック量が算出される。ここで、ｔｓ，ｄは、ルータｓを始点とし、ルータｄを終点とするトラヒックデマンド（交流トラヒック量）を示している。
（式５）の右辺は、光クロスコネクトｉ，ｊを端点とする物理リンクを通る交流トラヒック帯域制約量を示している。ここでは、論理リンクの最大帯域をＢとし、ルータｉの論理リンクの最大入力／出力ポート数Ｒｉが与えられているときに、ルータｉを始点とし、ルータｊを終点とする論理リンクの数をλｉ，ｊとする。なお、この論理リンクの数λｉ，ｊは、光クロスコネクトｉを始点とし、光クロスコネクトｊを終点とする波長パスの数（本数）と等しいものである。
よって、（式５）は、ルータｉ，ｊを端点とする論理リンクを通る交流トラヒック量（トラヒックデマンド）が、ルータｉを始点とし、ルータｊを終点とする論理リンクを通る交流トラヒック帯域制約量以下となることを示している。
【数５】
2014165690.tif 000007
【００１１】
以下の（式６）は、左辺に示すルータｊを流れる交流トラヒック量の総和が、右辺に示すルータｊのルーチング容量Ｇｊ以下になることを示している。
【数６】
2014165690.tif 000008
【００１２】
以下の（式７）は、左辺に示すルータｉを始点とする論理リンクの数の総和が、右辺に示すルータｉの論理リンクの最大入力／出力ポート数Ｒｉ以下であることを示している。
【数７】
2014165690.tif 000009
【００１３】
以下の（式８）は、左辺に示すルータｊを終点とする論理リンクの数の総和が、右辺に示すルータｊの論理リンクの最大入力／出力ポート数Ｒｊ以下であることを示している。
【数８】
2014165690.tif 000010
【００１４】
以下の（式９）の第１式は、ルータｉを始点とし、ルータｊを終点とする論理リンクの数λｉ，ｊが０以上であることを示している。また、（式９）の第２式は、光クロスコネクトｉを始点とし、光クロスコネクトｊを終点とする波長パスの中で、光クロスコネクトｍ，ｎを端点とする物理リンクを通る波長パスの数λｉ，ｊｍ，ｎが０以上であることを示している。
【数９】
2014165690.tif 000011
【００１５】
以下の（式１０）は、左辺に示す光クロスコネクトｉを始点とする波長パスの数（本数）の総和が、右辺に示すルータｉを始点としルータｊを終点とする論理リンクの数λｉ，ｊに等しいことを示している。
【数１０】
2014165690.tif 000012
【００１６】
以下の（式１１）は、左辺に示す光クロスコネクトｊを終点とする波長パスの数の総和が、右辺に示すルータｉを始点としルータｊを終点とする論理リンクの数λｉ，ｊに等しいことを示している。
【数１１】
2014165690.tif 000013
【００１７】
以下の（式１２）は、左辺に示す光クロスコネクトｉを始点とし、光クロスコネクトｊを終点とする波長パスの中で、中間の光クロスコネクトｌに入力される波長パスの数の総和が、右辺に示す当該光クロスコネクトｌから出力される波長パスの数の総和に等しいことを示している。
【数１２】
2014165690.tif 000014
【００１８】
以下の（式１３）は、光クロスコネクトｍ，ｎを端点とする物理リンクを通る波長パスの数についての、光クロスコネクトｉ，ｊを始点・終点とする全ての波長パスにおける総和（左辺）が、光クロスコネクトｍ，ｎを端点とする物理リンクの最大波長多重数Ｐｍ，ｎ以下であることを示している。なお、このλi,jm,nは、波長パス経路を表すこととなる。
【数１３】
2014165690.tif 000015
【００１９】
以下の（式１４）は、光クロスコネクトｎを端点とする物理リンクを通る波長パスの数についての、光クロスコネクトｉ，ｊを始点・終点とする全ての波長パスにおける総和（左辺）が、光クロスコネクトｎの最大波長スイッチ数Ｏｎ以下であることを示している。
【数１４】
2014165690.tif 000016
【００２０】
（数理計画法の目的関数）
以下の（式１５）は、必要設備量を算出する目的関数を示している。ここで、（式１５）の第１項は、ルータｉ，ｊを始点・終点とする論理リンクの数の総和、つまり、ＩＰインタフェースの設備の総和を示している。（式１５）の第２項は、光クロスコネクトｍ，ｎを端点とする物理リンクを通る波長パスの数の総和、つまり、波長パスのインタフェース（ポート）の設備の総和を示している。ここで、αは、ルータのインタフェース（ポート）と光クロスコネクトのインタフェース（ポート）との価格比を示している。
【数１５】
2014165690.tif 000017
【００２１】
非特許文献１に記載の手法では、（式１）〜（式１４）の制約式を満たす変数λｉ，ｊ，λｉ，ｊｍ，ｎ，ｒｓ，ｄｉ，ｊに対して、目的関数Σi,jλi,j + αΣi,j,m,nλi,jm,n（式１５）を最小化させる変数を数理計画法によって求めることにより、最適なＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量が求まる。
【００２２】
この非特許文献１の手法により、計算されたＩＰトラヒック経路、波長パス経路および波長パスの本数の一例を図２に示す。
図２の物理網上において、波長ノードであるＯＸＣ「１」「２」間に波長パスが１本（λ1,21,2）設定され、また、ＯＸＣ「１」「３」間に、波長パスが１本（λ3,13,1）と、ＯＸＣ「２」経由でさらに１本（λ1,31,2，λ1,32,3）の計２本が設定され、合計で物理網上に３本の波長パスが設定されている。これに対応し、論理網において、ＩＰルータ「１」「２」間に、論理リンクが１本（λ1,2＝１）設定され、ＩＰルータ「１」「３」間に論理リンクが２本（λ3,1＝２）設定され、合計で論理網上に３本の論理リンクが設定されている。そして、この論理リンクを通るトラヒックデマンドとして、ＩＰルータ「１」「２」間にＩＰトラヒック経路（ｒ1,21,2）が設定され、ＩＰルータ「３」「１」間に、ＩＰトラヒック経路（ｒ3,13,1）が設定され、ＩＰルータ「３」「２」間に、ＩＰトラヒック経路（ｒ3,23,1，ｒ3,21,2）が設定されていることを示している。
【００２３】
上記説明した非特許文献１に記載の手法は、ある時刻におけるトラヒックデマンドに対して、その時刻でトラヒックデマンドを収容するためのＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を算出するものであるが、トラヒックデマンドが時刻変動する場合には、各時刻においてそのトラヒックデマンドに対して上記計算を実行することにより、各時刻における、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を算出することが可能となる。
【００２４】
この場合、上記した数理計画法の制約式（式１）〜（式１４）の中で、（式５）および（式６）を、以下の（式５ａ），（式６ａ）に変更する。なお、（式５ａ），（式６ａ）において、rs,d（τ）は、ネットワーク設計の対象となる時刻τにおけるルータｓ，ｄを始点・終点とするトラヒックデマンド（交流トラヒック量）を示している。
【００２５】
【数１６】
2014165690.tif 000018
【先行技術文献】
【非特許文献】
【００２６】
【非特許文献１】F. Ricciato, S. Salsano, Angelo Belmonte, and M. Listanti, “Off-line Configuration of a MPLS over WDM Network under Time-Varying Offered Traffic”, INFOCOM2002，IEEE
【発明の概要】
【発明が解決しようとする課題】
【００２７】
しかしながら、トラヒックデマンドが時刻変動する場合に、各時刻で上記数理計画法による計算を実行し、各時刻における、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を算出するということは、その結果として、各時刻において、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を変動させてネットワークを管理することを意味する。しかし、このような運用では、経路変更に伴い、運用コストが増加してしまう。特に、ＩＰトラヒックの経路変更は、コスト設計やルータコンフィグの再設定および検証作業等の作業が必要となり運用コストが増大することとなる。
【００２８】
このような背景を鑑みて本発明がなされたのであり、本発明は、トラヒックデマンドが時刻変動する場合であっても、運用コストの増加を抑制した上で最適なＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を算出することができる、ネットワーク設計装置およびネットワーク設計プログラムを提供することを課題とする。
【課題を解決するための手段】
【００２９】
前記した課題を解決するため、本発明は、波長ノード間の波長パスが物理リンクにより構成される物理網上に設定され、前記設定された波長パスが論理網においてＩＰルータ間の論理リンクを構成し、前記論理網にＩＰトラヒック経路が設定されるＩＰネットワークのネットワーク設計を行うネットワーク設計装置であって、前記物理リンクのトポロジ情報、各時刻の前記ＩＰルータ間のトラヒックデマンド情報、前記物理リンクおよび前記波長ノードの設備に関する定数情報、前記ＩＰルータおよび前記論理リンクの設備に関する定数情報、並びに、ネットワーク設計を実行する前記各時刻の時刻情報を含む初期情報が記憶される記憶部と、前記初期情報を入出力部を介して外部から取得し、前記記憶部に記憶する初期情報取得部と、前記初期情報を参照し、数理計画法を用いて、前記数理計画法の目的関数において、前記ＩＰネットワークの設備量を最小化させるようにして、前記各時刻において共通のＩＰトラヒック経路、前記各時刻毎の、前記波長パスの経路および前記波長パスの本数、並びに、前記ネットワーク設計の設計期間内において必要となる必要設備量を計算する経路設備量計算部と、を備えることを特徴とするネットワーク設計装置とした。
【００３０】
このように、本発明によれば、ネットワーク設計装置の経路設備量計算部が、各時刻において共通のＩＰトラヒック経路を計算することができるため、ＩＰルータ間のトラヒックデマンドが時刻変動する場合であっても、ＩＰトラヒック経路を変更する必要をなくすことができる。よって、運用コストの増加を抑制した上で最適なネットワーク設計を実行することができる。
【００３１】
また、本発明は、前記経路設備量計算部が、前記ネットワーク設計の設計期間内の初期時刻（τ＝０）において、前記初期時刻における第１の前記数理計画法を用いて、前記初期時刻の次の時刻（τ＝１）において設定すべき、前記ＩＰトラヒック経路、前記波長パスの経路および前記波長パスの本数、並びに、前記必要設備量を計算する初期時刻計算部と、前記初期時刻計算部が計算した初期時刻（τ＝０）における前記ＩＰトラヒック経路を前記次の時刻以降（τ≧１）に計算する前記各時刻において共通のＩＰトラヒック経路とし、前記次の時刻以降の各時刻において、当該各時刻における第２の前記数理計画法を用いて、当該各時刻の次の時刻において設定すべき、前記波長パスの経路および前記波長パスの本数、並びに、前記必要設備量を計算する各時刻計算部と、前記初期時刻および前記次の時刻以降の各時刻において計算された前記必要設備量を総計し、前記ネットワーク設計の設計期間内において必要となる総設備量を計算する総設備量計算部と、を備えることを特徴とするものとした。
【００３２】
このように、ネットワーク設計装置は、初期時刻計算部が計算した初期時刻におけるＩＰトラヒック経路を、各時刻計算部が実行する次の時刻以降の各時刻の計算処理において、共通のＩＰトラヒック経路、つまり、定数情報として扱うことができる。よって、ネットワーク設計装置の処理負荷を低減させた上で、ＩＰトラヒック経路を変更する必要がなく、運用コストの増加を抑制した最適なネットワーク設計を実行することができる。
【００３３】
また、本発明は、前記経路設備量計算部が、前記ネットワーク設計を実行する前記各時刻の全てをまとめて処理対象とし、全時刻における第３の前記数理計画法を用いて、前記各時刻において共通のＩＰトラヒック経路、前記各時刻における、前記波長パスの経路および前記波長パスの本数、並びに、前記ネットワーク設計の設計期間内において必要となる総設備量を計算する全時刻計算部を備えること、を特徴とするものとした。
【００３４】
このように、ネットワーク設計装置は、初期時刻において、各時刻のＩＰルータ間のトラヒックデマンドを取得できる場合に、各時刻において共通のＩＰトラヒック経路を、全時刻を考慮して最適に設定することができる。よって、ネットワーク設計装置は、ＩＰトラヒック経路を変更する必要がなく、運用コストの増加を抑制した上で、さらに最適なネットワーク設計を実行することができる。
【００３５】
また、本発明は、波長ノード間の波長パスが物理リンクにより構成される物理網上に設定され、前記設定された波長パスが論理網においてＩＰルータ間の論理リンクを構成し、前記論理網にＩＰトラヒック経路が設定されるＩＰネットワークのネットワーク設計を行うためのコンピュータを、前記物理リンクのトポロジ情報、各時刻の前記ＩＰルータ間のトラヒックデマンド情報、前記物理リンクおよび前記波長ノードの設備に関する定数情報、前記ＩＰルータおよび前記論理リンクの設備に関する定数情報、並びに、ネットワーク設計を実行する前記各時刻の時刻情報を含む初期情報が記憶される記憶手段、前記初期情報を入出力手段を介して外部から取得し、前記記憶手段に記憶する初期情報取得手段、前記初期情報を参照し、数理計画法を用いて、前記数理計画法の目的関数において、前記ＩＰネットワークの設備量を最小化させるようにして、前記各時刻において共通のＩＰトラヒック経路、前記各時刻毎の、前記波長パスの経路および前記波長パスの本数、並びに、前記ネットワーク設計の設計期間内において必要となる必要設備量を計算する経路設備量計算手段、として機能させるためのネットワーク設計プログラムとした。
【００３６】
このように、本発明によれば、ネットワーク設計プログラムの経路設備量計算手段により、各時刻において共通のＩＰトラヒック経路を計算することができるため、ＩＰルータ間のトラヒックデマンドが時刻変動する場合であっても、ＩＰトラヒック経路を変更する必要がなくなる。よって、運用コストの増加を抑制した上で最適なネットワーク設計を実行することができる。
【発明の効果】
【００３７】
本発明によれば、トラヒックデマンドが時刻変動する場合であっても、運用コストの増加を抑制した上で最適なＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を算出することができる、ネットワーク設計装置およびネットワーク設計プログラムを提供することが可能となる。
【図面の簡単な説明】
【００３８】
【図１】光ＩＰネットワークの構成例を説明するための図である。
【図２】従来技術により計算されたネットワーク設計の一例を説明するための図である。
【図３】第１の実施形態に係るネットワーク設計装置の構成例を示す機能ブロック図である。
【図４】第１の実施形態に係るネットワーク設計装置が実行するネットワーク設計処理の流れを示すフローチャートである。
【図５】第２の実施形態に係るネットワーク設計装置の構成例を示す機能ブロック図である。
【図６】第２の実施形態に係るネットワーク設計装置が実行するネットワーク設計処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００３９】
次に、発明を実施するための形態（以下、「実施形態」という）について、適宜図面を参照しながら詳細に説明する。
【００４０】
＜概要＞
本実施形態に係るネットワーク設計装置１等の概要について説明する。
本発明は、前記した課題を解決するため、特に運用コストが増大する要因となると考えられる各時刻におけるＩＰトラヒックの経路変更を避けてネットワーク設計することを実現するため、前記した数理計画法を用いた非特許文献１に記載の手法を改良した。具体的には、「ＩＰトラヒック経路の時刻変動なし、波長パス経路、波長パスの本数、および、必要設備量の時刻変動あり」として、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算するネットワーク設計装置１等とした。なお、本実施形態において、ネットワーク設計装置１が実行する、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量の計算処理を、ネットワーク設計と称し、以下において説明することがある。
【００４１】
ネットワーク設計装置１は、非特許文献１に記載の数理計画法を用いた計算アルゴリズムにおいて変数となる、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量について、ＩＰトラヒック経路を時刻に対して不変な変数（定数）とする。一方、ネットワーク設計装置１は、波長パス経路、波長パスの本数および必要設備量に対しては、各時刻毎に変数を与えるものとする。
【００４２】
具体的には、本発明の第１の実施形態として、ネットワーク設計装置１（１Ａ）（後記する図３参照）は、数理計画法を用いて、ＩＰトラヒック経路を初期時刻において算出し、それ以降の時刻では、初期時刻において算出したＩＰトラヒック経路を定数として与えた上で、各時刻毎の波長パス経路、波長パスの本数および必要設備量を計算する。
このようにすることで、運用コストが増大する要因である、ＩＰトラヒックの経路変更を行わず、最適なネットワーク設計を行うことができる。
【００４３】
また、本発明の第２の実施形態として、ネットワーク設計装置１（１Ｂ）（後記する図５参照）は、数理計画法を用いて、ネットワーク設計の設定期間の全時刻をまとめて（一度に）、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算する。その際、ＩＰトラヒック経路は、各時刻において共通の情報となるようにして計算する。
このようにすることによっても、運用コストが増大する要因である、ＩＰトラヒックの経路変更を行わないようにした、最適なネットワーク設計を行うことができる。
【００４４】
＜第１の実施形態＞
まず、本発明の第１の実施形態に係るネットワーク設計装置１（１Ａ）について説明する。
ネットワーク設計装置１は、図１に示す光ＩＰネットワーク１００におけるネットワーク設計、具体的には、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算する装置である。このネットワーク設計装置１は、このネットワーク設計に必要な初期情報（物理リンクのトポロジ情報４１１や、対地間のトラヒックデマンド情報４１２等）を、各ノードや、光ＩＰネットワーク１００を管理するネットワーク管理装置（不図示）等から取得する。そして、ネットワーク設計装置１は、数理計画法を用いて、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算する。
その際、第１の実施形態に係るネットワーク設計装置１（１Ａ）は、数理計画法を用いて、まず、初期時刻（τ＝０）においてＩＰトラヒック経路の算出を含めたネットワーク設計を実行する。それ以降の時刻では、初期時刻（τ＝０）で算出したＩＰトラヒック経路を定数として与えた上で、各時刻毎の波長パス経路、波長パスの本数および必要設備量を計算する。
【００４５】
図３は、第１の実施形態に係るネットワーク設計装置１（１Ａ）の構成例を示す機能ブロック図である。図３に示すように、ネットワーク設計装置１（１Ａ）は、制御部１０、入出力部２０、メモリ部３０および記憶部４０を備える。
【００４６】
入出力部２０（入出力手段）は、通信回線を介して情報の送受信を行う通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で情報の入出力を行う入出力インタフェースとから構成される。
【００４７】
制御部１０は、ネットワーク設計装置１（１Ａ）全体の制御を司り、入出力情報処理部１１と、初期情報取得部１２と、経路設備量計算部１３とを含んで構成される。
【００４８】
入出力情報処理部１１は、入出力部２０を介して、物理リンクのトポロジ情報４１１や各時刻毎の対地間のトラヒックデマンド情報４１２等を含む初期情報を取得し、初期情報取得部１２に引き渡す。この初期情報は、経路設備量計算部１３が、数理計画法を用いてネットワーク設計を実行するために必要となる、物理リンクのトポロジ情報４１１や、対地間のトラヒックデマンド情報４１２、ネットワーク内の装置やリンクに関する各初期値の情報であり、詳細は後記する。
また、入出力情報処理部１１は、経路設備量計算部１３が計算した結果である、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を、入出力部２０を介して外部へ出力する。
【００４９】
初期情報取得部１２（初期情報取得手段）は、入出力情報処理部１１を介して、初期情報を取得し、記憶部４０内の初期情報ＤＢ（DataBase）４１に記憶する。
【００５０】
経路設備量計算部１３（経路設備量計算手段）は、数理計画法を用いて、対象となる光ＩＰネットワーク１００についての、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算する。この経路設備量計算部１３は、初期時刻計算部１３１、各時刻計算部１３２および総設備量計算部１３３を備える。
【００５１】
≪初期時刻計算部≫
まず、初期時刻計算部１３１が実行する、数理計画法を用いた初期時刻（τ＝０）での、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量の計算処理（以下、「初期時刻計算処理」と称する。）について説明する。
【００５２】
初期時刻計算部１３１は、数理計画法（第１の数理計画法）を用いて、後記する目的関数（Ａ１）を、設備量を最小化させるようにして、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算し最適解を得る。その際の各変数の制約式（Ｂ１）は、後記するものである。なお、初期時刻計算部１３１は、初期時刻τ＝０において、次の時刻であるτ＝１において必要となる、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算するものとする。
【００５３】
まず、この目的関数（Ａ１）および制約式（Ｂ１）において用いる、符号の定義等をまとめて説明する。
【００５４】
（文字の説明）
・Ｆ：＝｛Router_IF, OXC_IF, OXC_Transponder, Router, OXC｝；設備ｆの種類の集合
・Ａ：＝｛intro（導入），mainte（維持）｝；コストの種類の集合
【００５５】
（第１の定数情報）
・ΔＣ(０)：時刻０における全設備の（導入＋維持）コスト
・ΔＣintro(０)：時刻０における全設備の導入コスト
・ΔＣmainte(０)：時刻０から時刻１までの全設備の維持コスト
・ReqＮfi(１)：時刻１における設備ｆ（∈Ｆ）の地点i（= 1,…,N）での必要設備数
・αaf(０)：時刻０での設備ｆのａ（導入／維持）コストの単価比（維持コストの場合は単位時間あたり）
・Ｌ（ｍ,ｎ）：メトリック（ノードｍ,ｎ間のネットワークコスト）
・Ｎ：地点数（ノードの設置場所、例えば、東京や大阪）
・ｔs,d(１)  （s,d = 0,…,N-1）  ：ルータｓ,ｄ間の交流トラヒックにおける、時刻１でのトラヒック量（トラヒックデマンド）
・Ｂ：論理リンクの最大帯域
・Ｇｊ  （j = 0,…,N-1）  ：ルータｊのルーチング容量
・Ｒｉ  （i = 0,…,N-1）  ：ルータiの論理リンクの最大入力／出力ポート数
・Ｐm,n  （m,n = 0,…,N-1）  ：光クロスコネクトｍ,ｎを端点とする物理リンクの最大波長多重数
・Ｏn  （n = 0,…,N-1） ：光クロスコネクトｎの最大波長スイッチ数
【００５６】
（第１の変数情報）
・ｒs,di,j  （s,d,i,j = 1,…,N）  ：時刻０における、ルータｓ,ｄを始点・終点とする交流トラヒックにおいて、ルータｉ,ｄ間の論理リンクを通る交流トラヒック量の割合（＝ＩＰトラヒック経路）
・λi,j(０)  （i,j = 1,…,N）  ：時刻０における、ルータｉ,ｊ間の論理リンクの数（＝光クロスコネクトｉ,ｊ間の物理リンクを通る波長パスの数）
・λi,jm,n(０)  （i,j,m,n = 1,…,N）  ：時刻０において、光クロスコネクトｉ,ｊを始点・終点とする波長パスの中で、光クロスコネクトｍ,ｎ間の物理リンクを通る波長パスの数（＝波長パス経路）
・ｕi(０) ≧ ０  （i = 0,…,N-1）  ：時刻０における、地点ｉでのルータの台数
・ｖn(０) ≧ ０  （n = 0,…,N-1）  ：時刻０における、地点ｎでの光クロスコネクトの台数
【００５７】
次に、初期時刻計算部１３１が、数理計画法の計算アルゴリズムとして用いる目的関数（Ａ１）を示す。
【００５８】
【数１７】
2014165690.tif 000019
【００５９】
続いて、初期時刻計算部１３１が、数理計画法の計算アルゴリズムとして用いる制約式（Ｂ１）を示す。
【００６０】
【数１８】
2014165690.tif 000020
【００６１】
ここで、目的関数（Ａ１）の（式Ａ１−１）〜（式Ａ１−８）について説明する。
【００６２】
（式Ａ１−１）は、時刻０における全設備の（導入＋維持）コストが、時刻０における全設備の導入コストと、時刻０から時刻１までの全設備の維持コストとの和であることを示している。
【００６３】
（式Ａ１−２）は、時刻０における全設備の導入コストが、時刻０での設備ｆの導入コストの単価比に、時刻１における設備ｆの必要設備数の全ての地点における総和を乗算し、その値を全ての設備について総計したものであることを示している。
【００６４】
（式Ａ１−３）は、時刻０から時刻１までの全設備の維持コストが、時刻０での設備ｆの単位時間あたりの維持コストの単価比に、時刻１における設備ｆの必要設備数の全ての地点における総和を乗算し、その値を全ての設備について総計したものであることを示している。
【００６５】
（式Ａ１−４）は、時刻１における設備Router_IF（ルータインタフェース）の地点ｉにおける必要設備数が、時刻０におけるルータｉ（地点ｉに存在する全てのルータ）を通る論理リンクの数の総和であることを示している。
【００６６】
（式Ａ１−５）は、時刻１における設備OXC_IF（ＯＸＣインタフェース）の地点ｉにおける必要設備数が、時刻０における光クロスコネクトｉ,ｊ間の波長パスの中で、光クロスコネクトｍを端点とする物理リンクを通る全ての波長パスの数と、時刻０における光クロスコネクトｉ（地点ｉに存在する全ての光クロスコネクト）を端点とする全ての波長パスの数との和であることを示している。
【００６７】
（式Ａ１−６）は、時刻１における設備OXC_Transponder（ＯＸＣトランスポンダ）の地点ｉにおける必要設備数が、時刻０における光クロスコネクトｉ,ｊ間の波長パスの中で、光クロスコネクトｍを端点とする物理リンクを通る波長パスの数に、光クロスコネクトｍを端点とする各物理リンクのノードｍ,ｎ間におけるメトリック（ネットワークコスト）を乗算したものの総和であることを示している。なお、ここでの光クロスコネクトｉ,ｊは、地点ｉ,ｊそれぞれに存在する全ての光クロスコネクトを意味する。
【００６８】
（式Ａ１−７）は、時刻１における設備Router（ルータ）の地点ｉにおける必要設備数を、時刻０における地点ｉのルータの台数とすることを示している。
【００６９】
（式Ａ１−８）は、時刻１における設備OXC（光クロスコネクト）の地点ｉにおける必要設備数を、時刻０における地点ｉの光クロスコネクトの台数とすることを示している。
【００７０】
次に、制約式（Ｂ１）について説明する。なお、従来技術において説明した非特許文献１における制約式と、初期時刻τ＝０において、同じ内容の制約式についての説明は適宜省略する。
【００７１】
制約式 λi,j(0) ≧0（式Ｂ１−２）は、時刻０におけるλi,jが０以上であることを示している。つまり、時刻０における、ルータｉ,ｊ間の論理リンクの数（光クロスコネクトｉ,ｊ間の物理リンクを通る波長パスの数）が０以上であることを示している。
【００７２】
制約式 λi,jm,n(0) ≧0（式Ｂ１−３）は、時刻０において、光クロスコネクトｉ,ｊを始点・終点とする波長パスの中で、光クロスコネクトｍ,ｎ間の物理リンクを通る波長パスの数が０以上であることを示している。
【００７３】
制約式 ui(0) ≧0（式Ｂ１−４）は、時刻０における地点ｉでのルータの台数が０以上であることを示している。
【００７４】
制約式 vm(0) ≧0（式Ｂ１−５）は、時刻０における地点ｍでの光クロスコネクトの台数が０以上であることを示している。
【００７５】
制約式 Σs,dts,d(1)rs,di,j≦ Bλi,j(0)（式Ｂ１−９）は、時刻１における、ルータｉ，ｊを端点とする論理リンクを通る交流トラヒック量（トラヒックデマンド）が、時刻０における、ルータｉを始点とし、ルータｊを終点とする論理リンクを通る交流トラヒック帯域制約量以下となることを示している。
なお、（式Ｂ１−９）は、従来技術の数理計画法の制約式（式５）に対応している。
【００７６】
制約式 Σs,d,its,d(1)rs,di,j≦ Gjuj(0)（式Ｂ１−１０）は、左辺に示す、時刻１においてルータｊ（地点ｊに存在する全てのルータ）を流れる交流トラヒック量の総和が、右辺に示す、ルータｊのルーチング容量Ｇｊに、時刻０における地点ｊでのルータの台数を乗算した値以下になることを示している。
なお、（式Ｂ１−１０）は、従来技術の数理計画法の制約式（式６）に対応している。
【００７７】
制約式 Σjλi,j(0) ≦ Riui(0)（式Ｂ１−１１）は、左辺に示す、時刻０におけるルータｉ（地点ｉに存在する全てのルータ）を始点とする論理リンクの数の総和が、右辺に示す、ルータｉの論理リンクの最大入力／出力ポート数Ｒｉに、時刻０における地点ｉでのルータ台数を乗算した値以下になることを示している。
なお、（式Ｂ１−１１）は、従来技術の数理計画法の制約式（式７）に対応している。
【００７８】
制約式 Σiλi,j(0) ≦ Rjuj(0)（式Ｂ１−１２）は、左辺に示す、時刻０におけるルータｊ（地点ｊに存在する全てのルータ）を終点とする論理リンクの数の総和が、右辺に示すルータｊの論理リンクの最大入力／出力ポート数Ｒｊに、時刻０における地点ｊでのルータ台数を乗算した値以下になることを示している。
なお、（式Ｂ１−１２）は、従来技術の数理計画法の制約式（式８）に対応している。
【００７９】
制約式 Σi,j,mλi,jm,n(0) ≦ Onvn(0)（式Ｂ１−１７）は、時刻０における、光クロスコネクトｎ（地点ｎに存在する全ての光クロスコネクト）を端点とする物理リンクを通る波長パスの数についての、光クロスコネクトｉ，ｊを始点・終点とする全ての波長パスにおける総和（左辺）が、光クロスコネクトｎの最大波長スイッチ数Ｏｎに、時刻０における地点ｎでの光クロスコネクトの台数を乗算した値以下になることを示している。
なお、（式Ｂ１−１７）は、従来技術の数理計画法の制約式（式１４）に対応している。
【００８０】
初期時刻計算部１３１は、目的関数（Ａ１）および制約式（Ｂ１）を用いた数理計画法を、設備量を最小化させるようにして解くことにより、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算し最適解を得る。
そして、初期時刻計算部１３１は、計算した初期時刻（τ＝０）におけるＩＰトラヒック経路（rs,di,j）を含む処理結果を、記憶部４０に記憶する。
【００８１】
≪各時刻計算部≫
次に、各時刻計算部１３２が実行する、数理計画法を用いたネットワーク設計の最終時刻Ｔまでの各時刻における計算処理について説明する。
各時刻計算部１３２は、初期時刻計算部１３１が計算し記憶部４０に記憶された初期時刻（τ＝０）におけるＩＰトラヒック経路（rs,di,j）を定数とし、ネットワーク設計の対象となる最終時刻Ｔまでの各時刻τ（τ≧２）における、波長パス経路、波長パスの本数、および、必要設備量を計算する。なお、この各時刻計算部１３２が実行する計算処理を、「各時刻計算処理」と称する。
【００８２】
各時刻計算部１３２は、数理計画法（第２の数理計画法）を用いて、後記する目的関数（Ａ２）を、設備量を最小化させるようにして、波長パス経路、波長パスの本数、および、必要設備量を計算し最適解を得る。その際の各変数の制約式（Ｂ２）は、後記するものである。
【００８３】
まず、この目的関数（Ａ２）および制約式（Ｂ２）において用いる、符号の定義等をまとめて説明する。なお、ＩＰトラヒック経路を示すｒs,di,jが、（変数情報）ではなく（定数情報）に含まれることに注意を要する。
【００８４】
（文字の説明）
・Ｆ：＝｛Router_IF, OXC_IF, OXC_Transponder, Router, OXC｝；設備ｆの種類の集合
・Ａ：＝｛intro（導入），mainte（維持）｝；コストの種類の集合
・Ｔ：ネットワーク設計の対象となる最終時刻
【００８５】
（第２の定数情報）
・ΔＣ(τ)：時刻τ (=0,…,T-1)における全設備の（導入＋維持）コスト
・ΔＣintro(τ)：時刻τ (=0,…,T-1)における全設備の導入コスト
・ΔＣmainte(τ)：時刻τから時刻τ+1まで(=0,…,T-1) の全設備の維持コスト
・SetNfi (τ)：時刻τ(=0,…,T-1)における設備 f (∈F) の 地点i(=1,…,N)での設置設備数
・ReqＮfi(τ)：時刻τ (=1,…,T)における設備 f (∈F) の 地点i(=1,…,N) での必要設備数
・αaf(τ)：時刻τでの設備 f のa（導入／維持）コストの単価比（維持コストの場合は単位時間あたり）
・Ｌ（ｍ,ｎ）：メトリック（ノードｍ,ｎ間のネットワークコスト）
・Ｎ：地点数
・ｔs,d(τ)  （s,d = 0,…,N-1）  ：ルータｓ,ｄ間の交流トラヒックにおける、時刻τ (=1，…，T)でのトラヒック量（トラヒックデマンド）
・Ｂ：論理リンクの最大帯域
・Ｇｊ  （j = 0,…,N-1）  ：ルータｊのルーチング容量
・Ｒｉ  （i = 0,…,N-1）  ：ルータiの論理リンクの最大入力／出力ポート数
・Ｐm,n  （m,n = 0,…,N-1）  ：光クロスコネクトｍ,ｎを端点とする物理リンクの最大波長多重数
・Ｏn  （n = 0,…,N-1） ：光クロスコネクトｎの最大波長スイッチ数
・ｒs,di,j  （s,d,i,j = 1,…,N）  ：時刻０において算出された、ルータｓ,ｄを始点・終点とする交流トラヒックにおいて、ルータｉ,ｄ間の論理リンクを通る交流トラヒック量の割合（＝ＩＰトラヒック経路）
【００８６】
（第２の変数情報）
・λi,j(τ)  （i,j = 1,…,N）  ：時刻τにおける、ルータｉ,ｊ間の論理リンクの数（＝光クロスコネクトｉ,ｊ間の物理リンクを通る波長パスの数）
・λi,jm,n(τ)  （i,j,m,n = 1,…,N）  ：時刻τにおいて、光クロスコネクトｉ,ｊを始点・終点とする波長パスの中で、光クロスコネクトｍ,ｎ間の物理リンクを通る波長パスの数（＝波長パス経路）
・ｕi(τ) ≧ ０  （i = 0,…,N-1）  ：時刻τにおける、地点ｉでのルータの台数
・ｖｎ(τ) ≧ ０  （n = 0,…,N-1）  ：時刻τにおける、地点ｎでの光クロスコネクトの台数
【００８７】
次に、各時刻計算部１３２が、数理計画法の計算アルゴリズムとして用いる目的関数（Ａ２）を示す。
【００８８】
【数１９】
2014165690.tif 000021
【００８９】
目的関数（Ａ２）の（式Ａ２−１）〜（式Ａ２−３）について説明する。
なお、（式Ａ２−４）〜（式Ａ２−８）は、前記した初期時刻計算処理における（式Ａ１−４）〜（式Ａ１−８）において、ｔ＝０をｔ＝τに置き換え、ｔ＝１をｔ＝τ＋１に置き換えたものであり、その説明を省略する。
【００９０】
（式Ａ２−１）は、時刻τにおける全設備の（導入＋維持）コストが、時刻τにおける全設備の導入コストと、時刻τから時刻τ＋１までの全設備の維持コストとの和であることを示している。
【００９１】
（式Ａ２−２）は、時刻τにおける全設備の導入コストが、時刻τ―１における設備ｆの設置設備数と時刻τ＋１における設備ｆの必要設備数とのうちの大きい方から、時刻τ―１における設備ｆの設置設備数を減算して得た値を全ての地点について合計した値に、時刻τでの設備ｆの導入コストの単価比を乗算した値を、全ての設備について総計したものであることを示している。
【００９２】
（式Ａ２−３）は、時刻τから時刻τ＋１までの全設備の維持コストが、時刻τ―１における設備ｆの設置設備数と時刻τ＋１における設備ｆの必要設備数とのうち大きい方の値を全ての地点について合計した値に、時刻τでの設備ｆの単位時間あたりの維持コストの単価比を乗算した値を、全ての設備について総計したものであることを示している。
【００９３】
続いて、各時刻計算部１３２が、数理計画法の計算アルゴリズムとして用いる制約式（Ｂ２）を示す。
【００９４】
【数２０】
2014165690.tif 000022
【００９５】
この制約式（式Ｂ２−１）〜（式Ｂ２−１３）は、前記した初期時刻計算処理における制約式（式Ｂ１−１）〜（式Ｂ１−１７）のうち、定数として与えられるため不要となったＩＰトラヒック経路（rs,di,j）に関連する制約式（式Ｂ１−１），（式Ｂ１−６）〜（式Ｂ１−８）の４つを削除した上で、ｔ＝０をｔ＝τに置き換え、ｔ＝１をｔ＝τ＋１に置き換えたものであり、その説明を省略する。
【００９６】
上記のように、各時刻計算部１３２は、初期時刻（τ＝０）におけるＩＰトラヒック経路（rs,di,j）を定数として固定した上で、目的関数（Ａ２）および制約式（Ｂ２）を用いた数理計画法について設備量を最小化させるように解くことにより、各時刻τにおける、波長パス経路、波長パスの本数、および、必要設備量を計算し最適解を得ることができる。
【００９７】
≪総設備量計算部≫
次に、総設備量計算部１３３（図３参照）が実行する、総設備量計算処理について説明する。
【００９８】
総設備量計算部１３３は、初期時刻計算部１３１および各時刻計算部１３２が、各時刻τ (=0，…，T-1)について計算した全設備の（導入＋維持）コストΔC(τ)を用いて、以下の（式Ｃ−１）に基づき、ネットワーク設計の最終時刻Ｔまでに必要となる総コストを計算する。なお、総設備量計算部１３３による、この総コストの計算処理を「総設備量計算処理」と称する。
【００９９】
【数２１】
2014165690.tif 000023
【０１００】
ここで、（式Ｃ−１）は、最終時刻Ｔにおける総コストＣ(Ｔ)が、時刻τ (=0，…，T-1)それぞれにおける全設備の（導入＋維持）コストの総和であることを示している。
【０１０１】
図３に戻り、メモリ部（記憶手段）３０は、ＲＡＭ（Random Access Memory）等の一次記憶手段からなり、制御部１０によるデータ処理に必要な情報を一時的に記憶する。
【０１０２】
記憶部（記憶手段）４０は、ハードディスクやフラッシュメモリ等の記憶手段からなり、前記物理リンクのトポロジ情報４１１や、各時刻τ (=1，…，T)における対地間のトラヒックデマンド情報４１２、初期時刻計算部１３１および各時刻計算部１３２が実行する数理計画法を用いた処理において初期情報として必要となる各種の定数情報（Ｎ，Ｂ，Ｇｊ，Ｒｉ，Ｐm,n，Ｏn，α）等が記憶される。
【０１０３】
なお、この制御部１０は、例えば、記憶部４０に格納されたプログラム（ネットワーク設計プログラム）をＣＰＵ（Central Processing Unit）がメモリ部３０であるＲＡＭに展開し実行することで実現される。
【０１０４】
（第１の実施形態におけるネットワーク設計処理の流れ）
次に、ネットワーク設計装置１（１Ａ）が実行するネットワーク設計処理の全体の流れを説明する。図４は、本発明の第１の実施形態に係るネットワーク設計装置１（１Ａ）が実行するネットワーク設計処理の流れを示すフローチャートである。
【０１０５】
まず、ネットワーク設計装置１（１Ａ）の初期情報取得部１２が、入出力情報処理部１１および入出力部２０を介して、物理リンクのトポロジ情報４１１や、ネットワーク設計に対象となる各時刻τ (=1，…，T)における対地間のトラヒックデマンド情報４１２、初期情報として必要となる各種の定数情報（Ｎ，Ｂ，Ｇｊ，Ｒｉ，Ｐm,n，Ｏn，α等）の初期情報を取得する（ステップＳ１０）。
なお、初期情報取得部１２は、各時刻τ (=1，…，T)における対地間のトラヒックデマンド情報４１２をまとめて取得してもよい。また、初期情報取得部１２は、初期時刻（τ＝０）においては、ネットワーク設計の対象となるτ＝１における対地間のトラヒックデマンド情報のみを取得し、後記する各時刻計算処理（ステップＳ１２）において、ネットワーク設計の対象となる時刻τ（τ≧２）毎に、最新のトラヒックデマンド情報をネットワーク管理装置（不図示）等から取得して、記憶部４０に記憶するようにしてもよい。
【０１０６】
次に、初期時刻計算部１３１は、目的関数（Ａ１）および制約式（Ｂ１）を用いた数理計画法による、初期時刻（τ＝０）での初期時刻計算処理を実行する（ステップＳ１１）。そして、初期時刻計算部１３１は、初期時刻（τ＝０）における（つまり、ネットワーク設計の対象となるτ＝１において必要となる）ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量についての最適解を得る。
【０１０７】
次に、各時刻計算部１３２は、τに１を加算して、各時刻計算処理を実行する（ステップＳ１２）。
ここで、各時刻計算部１３２は、初期時刻計算部１３１が計算した初期時刻（τ＝０）において計算したＩＰトラヒック経路（rs,di,j）を定数とし、目的関数（Ａ２）および制約式（Ｂ２）を用いた数理計画法により、各時刻τにおける、波長パス経路、波長パスの本数、および、必要設備量を計算する。
【０１０８】
続いて、各時刻計算部１３２は、時刻τがネットワーク設計の最終時刻Ｔにおけるネットワーク設計を実行する時刻Ｔ−１より前の時刻であるか否かを判定する（ステップＳ１３）、そして、各時刻計算部１３２は、時刻τが時刻Ｔ−１より前の時刻であれば（ステップＳ１３→Ｙｅｓ）、ステップＳ１２に戻り、τに１を加算して計算処理を実行する。一方、各時刻計算部１３２は、時刻τが時刻Ｔ−１となった場合（ステップＳ１３→Ｎｏ）には、最終時刻Ｔに設定すべき経路等の計算処理が終了したものとして、次のステップＳ１４に進む。
【０１０９】
ステップＳ１４において、総設備量計算部１３３は、各時刻において計算された全設備の（導入＋維持）コストΔC(τ)を用いて、（式Ｃ−１）に基づき、ネットワーク設計の最終時刻Ｔまでに必要となる総コストを計算し（総設備量計算処理）、処理を終える。
【０１１０】
このように、本発明の第１の実施形態に係るネットワーク設計装置１（１Ａ）によれば、初期時刻（τ＝０）において計算したＩＰトラヒック経路を用いて、各時刻における波長パス経路、波長パスの本数および必要設備量を計算するため、運用コストが増大する要因となるＩＰトラヒックの経路変更を行わず、最適なネットワーク設計を行うことができる。
【０１１１】
＜第２の実施形態＞
次に、本発明の第２の実施形態に係るネットワーク設計装置１（１Ｂ）について説明する。
【０１１２】
ネットワーク設計装置１（１Ｂ）は、第１の実施形態に係るネットワーク設計装置１（１Ａ）と異なり、初期時刻（τ＝０）において計算したＩＰトラヒック経路を各時刻τにおける定数として利用するのではなく、初期時刻０からネットワーク設計の最終時刻Ｔにおけるネットワーク設計を実行する時刻Ｔ−１までの全時刻をまとめて（一度に）、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算する。その際、ネットワーク設計装置１（１Ｂ）は、ＩＰトラヒック経路については、各時刻で共通の情報となるように計算することを特徴とする。
このようにすることにより、ネットワーク設計装置１（１Ｂ）は、運用コストが増大する要因である、ＩＰトラヒックの経路変更を行わないようにした、最適なネットワーク設計を行うことができる。
【０１１３】
図５は、第２の実施形態に係るネットワーク設計装置１（１Ｂ）の構成例を示す機能ブロック図である。
図３において示した第１の実施形態に係るネットワーク設計装置１（１Ａ）との違いは、経路設備量計算部１３において、初期時刻計算部１３１、各時刻計算部１３２および総設備量計算部１３３を備えておらず、その代わりに、全時刻計算部１３４を備えていることである。
なお、図５のネットワーク設計装置１（１Ｂ）において、図３において示したネットワーク設計装置１（１Ａ）と同じ機能については、同一の名称と符号を付し、その説明を省略する。
【０１１４】
≪全時刻計算部≫
全時刻計算部１３４は、時刻０からネットワーク設計の最終時刻Ｔにおけるネットワーク設計を実行する時刻Ｔ−１までの全時刻をまとめて（一度に）、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算する。その際、全時刻計算部１３４は、ＩＰトラヒック経路については、各時刻において共通の情報となるように計算する。なお、この全時刻計算部１３４が実行する計算処理を、「全時刻計算処理」と称する。
【０１１５】
全時刻計算部１３４は、数理計画法（第３の数理計画法）を用いて、後記する目的関数（Ａ３）を、設備量を最小化させるようにして、各時刻において共通のＩＰトラヒック経路、各時刻τ(=0，…，T-1)それぞれにおける、波長パス経路および波長パスの本数、全設備の（導入＋維持）コストの最終時刻Ｔまでの総和（総コスト）を計算する。その際の各変数の制約式（Ｂ３）は、後記するものである。
【０１１６】
まず、この目的関数（Ａ３）および制約式（Ｂ３）において用いる、符号の定義等をまとめて説明する。
【０１１７】
（文字の説明）
・Ｆ：＝｛Router_IF, OXC_IF, OXC_Transponder, Router, OXC｝；設備ｆの種類の集合
・Ａ：＝｛intro（導入），mainte（維持）｝；コストの種類の集合
・Ｔ：ネットワーク設計の対象となる最終時刻
【０１１８】
（第３の定数情報）
・Ｃ(Ｔ) :全設備の（導入＋維持）コストのネットワーク設計の最終時刻Ｔまでの総和
・Ｃa(Ｔ) :全設備のa ∈Ａ コストの最終時刻Ｔまでの総和
・Ｃaf (Ｔ) :設備 f ∈F のa ∈A コストの最終時刻Ｔでの総和
・ReqNfi (τ) :時刻τ (= 1,…,T)における設備 f (∈F) の 地点i (= 1,…,N)での必要設備数
・αaf(τ) :時刻τでの設備 f のa（導入／維持）コストの単価比（維持コストの場合は単位時間あたり）
・Ｌ（ｍ,ｎ）：メトリック（ノードｍ,ｎ間のネットワークコスト）
・Ｎ：地点数
・ｔs,d(τ)  （s,d = 0,…,N-1，τ= 1,…,T）：ルータｓ,ｄ間の交流トラヒックにおける、時刻τでのトラヒック量（トラヒックデマンド）
・Ｂ：論理リンクの最大帯域
・Ｇｊ  （j = 0,…,N-1）  ：ルータｊのルーチング容量
・Ｒｉ  （i = 0,…,N-1）  ：ルータiの論理リンクの最大入力／出力ポート数
・Ｐm,n  （m,n = 0,…,N-1）  ：光クロスコネクトｍ,ｎを端点とする物理リンクの最大波長多重数
・Ｏn   （n = 0,…,N-1） ：光クロスコネクトｎの最大波長スイッチ数
【０１１９】
（第３の変数情報）
・ｒs,di,j  （s,d,i,j = 1,…,N）  ：各時刻で共通な、ルータｓ,ｄを始点・終点とする交流トラヒックにおいて、ルータｉ,ｊ間の論理リンクを通る交流トラヒック量の割合（＝ＩＰトラヒック経路）
・λi,j(τ)  （i,j = 1,…,N，τ = 0,…,T-1）  ：時刻τにおける、ルータｉ,ｊ間の論理リンクの数（＝光クロスコネクトｉ,ｊ間の物理リンクを通る波長パスの数）
・λi,jm,n(τ)  （i,j,m,n = 1,…,N，τ = 0,…,T-1）  ：時刻τにおいて、光クロスコネクトｉ,ｊを始点・終点とする波長パスの中で、光クロスコネクトｍ,ｎ間の物理リンクを通る波長パスの数（＝波長パス経路）
・ｕi(τ) ≧ ０  （i = 0,…,N-1，τ = 0,…,T-1）  ：時刻τにおける、地点ｉでのルータの台数
・ｖn(τ) ≧ ０  （n = 0,…,N-1，τ = 0,…,T-1）  ：時刻τにおける、地点ｎでの光クロスコネクトの台数
【０１２０】
次に、全時刻計算部１３４が、数理計画法の計算アルゴリズムとして用いる目的関数（Ａ３）を示す。
【０１２１】
【数２２】
2014165690.tif 000024
【０１２２】
目的関数（Ａ３）の（式Ａ３−１）〜（式Ａ３−３）について説明する。
なお、（式Ａ３−４）〜（式Ａ３−８）は、前記した第１の実施形態における目的関数（Ａ２）の（式Ａ２−４）〜（式Ａ２−８）と同じであるので、その説明を省略する。
【０１２３】
（式Ａ３−１）は、全設備の（導入＋維持）コストの最終時刻Ｔまでの総和（総コスト）が、全設備の導入コストの最終時刻Ｔまでの総和と、全設備の維持コストの最終時刻Ｔまでの総和との和であることを示している。
【０１２４】
（式Ａ３−２）は、全設備の導入コストの最終時刻Ｔまでの総和が、時刻０〜τにおける設備ｆの地点ｉでの最大の必要設備数の全ての地点についての合計から、時刻０〜τ−１における設備ｆの地点ｉでの最大の必要設備数の全ての地点についての合計を減算して得た値に、時刻τでの設備ｆの導入コストの単価比を乗算した値を、全ての地点の全ての設備について総計したものについて、τを０〜Ｔ−１として総計したものであることを示している。
【０１２５】
（式Ａ３−３）は、全設備の維持コストの最終時刻Ｔまでの総和が、時刻０〜τにおける設備ｆの地点ｉでの最大の必要設備数の全ての地点についての合計に、時刻τでの設備ｆの単位時間あたりの維持コストの単価比を乗算した値を、全ての地点の全ての設備について総計したものについて、τを０〜Ｔ−１として総計したものであることを示している。
【０１２６】
続いて、全時刻計算部１３４が、数理計画法の計算アルゴリズムとして用いる制約式（Ｂ３）を示す。
【０１２７】
【数２３】
2014165690.tif 000025
2014165690.tif 000026
【０１２８】
この制約式（式Ｂ３−１）〜（式Ｂ３−１７）において、（式Ｂ３−６）〜（式Ｂ３−８）については、各時刻で共通のＩＰトラヒック経路（ｒs,di,j）となるため、他の制約式において付された、τ＝０，…，Ｔ−１（下線で示す）の条件が含まれていない点に注意する。
【０１２９】
このように、全時刻計算部１３４は、各時刻で共通のＩＰトラヒック経路（ｒs,di,j）を求めるように設定した上で、目的関数（Ａ３）および制約式（Ｂ３）を用いた数理計画法において設備量を最小化させるように解くことにより、各時刻において共通のＩＰトラヒック経路、各時刻τ(=0，…，T-1)それぞれにおける、波長パス経路および波長パスの本数、全設備の（導入＋維持）コストの最終時刻Ｔまでの総和（総コスト）を計算することができる。
【０１３０】
（第２の実施形態にネットワーク設計処理の流れ）
次に、ネットワーク設計装置１（１Ｂ）が実行するネットワーク設計処理の全体の流れを説明する。図６は、本発明の第２の実施形態に係るネットワーク設計装置１（１Ｂ）が実行するネットワーク設計処理の流れを示すフローチャートである。
【０１３１】
まず、ネットワーク設計装置１（１Ｂ）の初期情報取得部１２が、入出力情報処理部１１および入出力部２０を介して、物理リンクのトポロジ情報４１１や、各時刻τ (=1，…，T)における対地間のトラヒックデマンド情報４１２、初期情報として必要となる各種の定数情報（Ｎ，Ｂ，Ｇｊ，Ｒｉ，Ｐm,n，Ｏn，α等）の初期情報を取得する（ステップＳ２０）。
【０１３２】
次に、全時刻計算部１３４は、全時刻計算処理を実行する（ステップＳ２１）。
ここで、全時刻計算部１３４は、目的関数（Ａ３）および制約式（Ｂ３）を用いた数理計画法により、各時刻において共通のＩＰトラヒック経路、各時刻τ(=0，…，T-1)それぞれにおける、波長パス経路および波長パスの本数、全設備の（導入＋維持）コストの最終時刻Ｔまでの総和（総コスト）を計算し、処理を終える。
【０１３３】
このように、本発明の第２の実施形態に係るネットワーク設計装置１（１Ｂ）によれば、各時刻において共通のＩＰトラヒック経路を計算できると共に、各時刻τ(=0，…，T-1)それぞれにおける、波長パス経路および波長パスの本数、全設備の（導入＋維持）コストの最終時刻Ｔまでの総和（総コスト）を一度に計算することができる。よって、ネットワーク設計装置１（１Ｂ）は、運用コストが増大する要因となるＩＰトラヒックの経路変更を行わないようにする、最適なネットワーク設計を行うことができる。
【０１３４】
以上説明した、本発明の第１の実施形態に係るネットワーク設計装置１（１Ａ）と第２の実施形態に係るネットワーク設計装置１（１Ｂ）とは、上記のように、運用コストの増大を抑制するという共通の効果を奏するが、さらに、その作用効果において以下のような相異がある。
【０１３５】
まず、ネットワーク設計装置１（１Ａ）は、初期時刻（τ＝０）において、ネットワーク設計の最終時刻Ｔまでの全てのトラヒックデマンドを予め取得していなくても、その時刻τ毎に、時刻τ＋１において、予測されるトラヒックデマンドのより確かな情報を取得した上で、ネットワーク設計の計算（各時刻計算処理）を実行することができる。一方、ネットワーク設計装置１（１Ｂ）は、初期時刻（τ＝０）において、ネットワーク設計の最終時刻Ｔまでのトラヒックデマンドが取得できる場合に有効である。
【０１３６】
ネットワーク設計装置１（１Ａ）は、初期時刻（τ＝０）において計算したＩＰトラヒック経路を定数とし、それ以降の時刻τにおいてネットワーク設計を実行するため、ＩＰトラヒック経路に関係する変数を減らし、計算処理を実行することができる。よって、ネットワーク設計装置１（１Ａ）の処理負荷を低減させることができる。
一方、ネットワーク設計装置１（１Ｂ）は、ネットワーク設計の最終時刻Ｔまでの各時刻を考慮して、各時刻に共通のＩＰトラヒック経路を決定するため、全時刻を考慮してより最適なＩＰトラヒック経路を決定することができる。ネットワーク設計装置１（１Ｂ）は、ネットワーク設計装置１（１Ａ）に比べ、変数の数が増加するため、ネットワーク設計装置１（１Ａ）に比べ、ネットワーク設計装置１（１Ｂ）の処理性能の高い場合に有効となる。
【符号の説明】
【０１３７】
１      ネットワーク設計装置
１０    制御部
１１    入出力情報処理部
１２    初期情報取得部（初期情報取得手段）
１３    経路設備量計算部（経路設備量計算手段）
２０    入出力部（入出力手段）
３０    メモリ部（記憶手段）
４０    記憶部（記憶手段）
４１    初期情報ＤＢ
１００  光ＩＰネットワーク
１３１  初期時刻計算部
１３２  各時刻計算部
１３３  総設備量計算部
１３４  全時刻計算部
４１１  物理リンクのトポロジ情報
４１２  対地間のトラヒックデマンド情報
【図１】
2014165690.tif 000037
【図２】
2014165690.tif 000038
【図３】
2014165690.tif 000039
【図４】
2014165690.tif 000040
【図５】
2014165690.tif 000041
【図６】
2014165690.tif 000042