JP5898112B2 - ネットワーク設計装置およびネットワーク設計プログラム - Google Patents

Description

本発明は、波長パスが物理トポロジ上に設定され、ＩＰ（Internet Protocol）トラヒックが波長パスにより構成された論理トポロジ上に設定された光ＩＰネットワークを設計する、ネットワーク設計装置およびネットワーク設計プログラムに関する。

光ＩＰネットワークは、波長パスが物理トポロジ（物理網）上に設定され、ＩＰトラヒックが波長パスで構成された論理トポロジ（論理網）上に設定される。
図１に示すように、光ＩＰネットワーク１００では、物理レイヤ上の波長レイヤに、波長パスが設定されたＷＤＭ（Wavelength Division Multiplexing）ネットワークを構成する。物理網は、転送ノード、伝送ノードおよびそれらを結ぶ物理リンクから構成される。ここで、転送ノードは、例えばＩＰルータ等である。伝送ノード（波長ノード）は、例えば、ＯＸＣ（Optical Cross Connect：光クロスコネクト）等である。また、物理リンクは、例えば、光ファイバ等である。そして、波長ノード（ＯＸＣ等）を始終点とした波長パスが物理網上に設定され、その波長パスがＩＰレイヤでは転送ノード（ＩＰルータ）間における論理的なリンク（論理リンク）を構成する。なお、以下において、ＩＰルータを単に「ルータ」と称することがある。

この光ＩＰネットワーク１００では、波長パス経路およびＩＰトラヒック経路を最適化することにより、ネットワーク全体の資源を有効活用し、転送品質を維持し、ネットワークコストを低減することが求められる。
そして、この波長パス経路およびＩＰトラヒック経路等を最適化するためには、波長パス経路とＩＰトラヒック経路とをそれぞれ独立に設定するのではなく、両者を同時に考慮して最適化することが重要となる。

具体的には、物理トポロジ上の波長パスの経路を表す変数とＩＰトラヒックの経路を表す各変数に対して、設備量をこれらの変数を用いた式で表した目的関数を設定し、各変数に関する制約式のもとで設備量を最小化させるようにして目的関数を解く数理計画法を適用する。そして、この数理計画法に基づき、物理トポロジ上の波長パスの経路を表す変数と、ＩＰトラヒックの経路を表す変数とを同時に解くことで最適解を得る手法が開示されている（非特許文献１参照）。この数理計画法における目的関数は、以下の（式１５）で表される。また、各変数の制約式は、以下の（式１）〜（式１４）で表される。

（数理計画法の制約式）
以下、まず、非特許文献１に記載の手法による、数理計画法の制約式（式１）〜（式１４）について説明する。

以下の（式１）は、ルータｓを始点とし、ルータｄを終点とする交流トラヒックにおいて、ルータｉ，ｊを端点とする論理リンクの少なくとも１つを通る交流トラヒック量の割合ｒ^s,d _i,jが、０から１のいずれかの値をとることを示している。なお、このｒ^s,d _i,jは、ＩＰトラヒック経路を表すこととなる。

以下の（式２）は、ルータｓを始点とし、ルータｄを終点とする交流トラヒックにおいて、ルータｓを端点とする全ての論理リンクを通る交流トラヒック量の割合の合計が、１となることを示している。

以下の（式３）は、ルータｓを始点とし、ルータｄを終点とする交流トラヒックにおいて、ルータｄを端点とする全ての論理リンクを通る交流トラヒック量の割合の合計が、１となることを示している。

以下の（式４）は、ルータｓを始点とし、ルータｄを終点とする交流トラヒックにおいて、ルータｋを一方の端点とする全ての論理リンクを通る交流トラヒック量の割合の合計と、ルータｋを他方の端点とする全ての論理リンクを通る交流トラヒック量の割合の合計とが同一となることを示している。すなわち、（式４）は、中間ルータｋにおいて、入力される交流トラヒック量と、出力される交流トラヒック量とが同一になることを示している。

以下の（式５）の左辺によって、ルータｉ，ｊを端点とする論理リンクを通る交流トラヒック量が算出される。ここで、ｔ^s,dは、ルータｓを始点とし、ルータｄを終点とするトラヒックデマンド（交流トラヒック量）を示している。
（式５）の右辺は、光クロスコネクトｉ，ｊを端点とする物理リンクを通る交流トラヒック帯域制約量を示している。ここでは、論理リンクの最大帯域をＢとし、ルータｉの論理リンクの最大入力／出力ポート数Ｒ_ｉが与えられているときに、ルータｉを始点とし、ルータｊを終点とする論理リンクの数をλ^i,jとする。なお、この論理リンクの数λ^i,jは、光クロスコネクトｉを始点とし、光クロスコネクトｊを終点とする波長パスの数（本数）と等しいものである。
よって、（式５）は、ルータｉ，ｊを端点とする論理リンクを通る交流トラヒック量（トラヒックデマンド）が、ルータｉを始点とし、ルータｊを終点とする論理リンクを通る交流トラヒック帯域制約量以下となることを示している。

以下の（式６）は、左辺に示すルータｊを流れる交流トラヒック量の総和が、右辺に示すルータｊのルーチング容量Ｇ_ｊ以下になることを示している。

以下の（式７）は、左辺に示すルータｉを始点とする論理リンクの数の総和が、右辺に示すルータｉの論理リンクの最大入力／出力ポート数Ｒ_ｉ以下であることを示している。

以下の（式８）は、左辺に示すルータｊを終点とする論理リンクの数の総和が、右辺に示すルータｊの論理リンクの最大入力／出力ポート数Ｒ_ｊ以下であることを示している。

以下の（式９）の第１式は、ルータｉを始点とし、ルータｊを終点とする論理リンクの数λ^i,jが０以上であることを示している。また、（式９）の第２式は、光クロスコネクトｉを始点とし、光クロスコネクトｊを終点とする波長パスの中で、光クロスコネクトｍ，ｎを端点とする物理リンクを通る波長パスの数λ^i,j _m,nが０以上であることを示している。

以下の（式１０）は、左辺に示す光クロスコネクトｉを始点とする波長パスの数（本数）の総和が、右辺に示すルータｉを始点としルータｊを終点とする論理リンクの数λ^i,jに等しいことを示している。

以下の（式１１）は、左辺に示す光クロスコネクトｊを終点とする波長パスの数の総和が、右辺に示すルータｉを始点としルータｊを終点とする論理リンクの数λ^i,jに等しいことを示している。

以下の（式１２）は、左辺に示す光クロスコネクトｉを始点とし、光クロスコネクトｊを終点とする波長パスの中で、中間の光クロスコネクトｌに入力される波長パスの数の総和が、右辺に示す当該光クロスコネクトｌから出力される波長パスの数の総和に等しいことを示している。

以下の（式１３）は、光クロスコネクトｍ，ｎを端点とする物理リンクを通る波長パスの数についての、光クロスコネクトｉ，ｊを始点・終点とする全ての波長パスにおける総和（左辺）が、光クロスコネクトｍ，ｎを端点とする物理リンクの最大波長多重数Ｐ_ｍ，ｎ以下であることを示している。なお、このλ^i,j _m,nは、波長パス経路を表すこととなる。

以下の（式１４）は、光クロスコネクトｎを端点とする物理リンクを通る波長パスの数についての、光クロスコネクトｉ，ｊを始点・終点とする全ての波長パスにおける総和（左辺）が、光クロスコネクトｎの最大波長スイッチ数Ｏ_ｎ以下であることを示している。

（数理計画法の目的関数）
以下の（式１５）は、必要設備量を算出する目的関数を示している。ここで、（式１５）の第１項は、ルータｉ，ｊを始点・終点とする論理リンクの数の総和、つまり、ＩＰインタフェースの設備の総和を示している。（式１５）の第２項は、光クロスコネクトｍ，ｎを端点とする物理リンクを通る波長パスの数の総和、つまり、波長パスのインタフェース（ポート）の設備の総和を示している。ここで、αは、ルータのインタフェース（ポート）と光クロスコネクトのインタフェース（ポート）との価格比を示している。

非特許文献１に記載の手法では、（式１）〜（式１４）の制約式を満たす変数λ^i,j，λ^i,j _m,n，ｒ^s,d _i,jに対して、目的関数Σ_i,jλ^i,j + αΣ_i,j,m,nλ^i,j _m,n（式１５）を最小化させる変数を数理計画法によって求めることにより、最適なＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量が求まる。

この非特許文献１の手法により、計算されたＩＰトラヒック経路、波長パス経路および波長パスの本数の一例を図２に示す。
図２の物理網上において、波長ノードであるＯＸＣ「１」「２」間に波長パスが１本（λ^1,2 _1,2）設定され、また、ＯＸＣ「１」「３」間に、波長パスが１本（λ^3,1 _3,1）と、ＯＸＣ「２」経由でさらに１本（λ^1,3 _1,2，λ^1,3 _2,3）の計２本が設定され、合計で物理網上に３本の波長パスが設定されている。これに対応し、論理網において、ＩＰルータ「１」「２」間に、論理リンクが１本（λ^1,2＝１）設定され、ＩＰルータ「１」「３」間に論理リンクが２本（λ^3,1＝２）設定され、合計で論理網上に３本の論理リンクが設定されている。そして、この論理リンクを通るトラヒックデマンドとして、ＩＰルータ「１」「２」間にＩＰトラヒック経路（ｒ^1,2 _1,2）が設定され、ＩＰルータ「３」「１」間に、ＩＰトラヒック経路（ｒ^3,1 _3,1）が設定され、ＩＰルータ「３」「２」間に、ＩＰトラヒック経路（ｒ^3,2 _3,1，ｒ^3,2 _1,2）が設定されていることを示している。

上記説明した非特許文献１に記載の手法を用いて、この最適化問題を数理計画法により解く処理を実行しようとすると、変数λ^i,j _m,n，ｒ^s,d _i,jの数は、ノード数のおよそ４乗となり、大規模網では変数の数が莫大となって計算時間が長時間かかってしまう。そのため、非特許文献１に記載の手法において、数理計画法における変数を削減することにより計算時間を短縮する技術として、SpaceReducton法とDecomposition法とが提案されている（非特許文献２参照）。

SpaceReducton法は、各２点間の波長パス経路について、複数の経路候補の中から、最短経路に比べて長すぎる経路の候補を事前に削除して変数であるλ^i,j _m,nの一部を定数化し、変数の数を削減するものである。

具体的には、SpaceReducton法では、変数λ^i,j _m,nについて、各対地間（ｉ，ｊ）毎に波長パスのホップ数の上限となる閾値Ｌmax(i,j)を設け、上限を超える波長パス経路に対して、その経路上の各物理リンク（ｍ，ｎ）の波長の本数としてλ^i,j _m,n＝０とする。
図３を参照して説明すると、光クロスコネクト（ｉ，ｊ）間の波長パス経路として、例えば、波長パス「１」や波長パス「２」等が波長パス経路の候補となるが、最短の波長パス経路である波長パス「１」（最短ホップ数＝４）に比べ、長すぎる経路、つまり、ホップ数の上限となる閾値Ｌmax(i,j)（例えば、Ｌmax(i,j)＝６）を超える波長パス「２」（ホップ数＝７）については、波長パス経路の候補としないように削除する。
このように、SpaceReducton法では、波長パス経路の変数の数を削減した上で、数理計画法を実行することにより、計算速度を高速化することができる。

Decomposition法は、最適化問題（線形計画問題）を小さな部分問題に分割し、部分問題を繰り返し解くことにより、計算の高速化を図るものである。

具体的には、図４に示すように、Decomposition法では、部分に分割する方法として、ＩＰトラヒックをトラヒック量の多い順にソートし（ステップＳ１）、上位Ｘ個のＩＰトラヒックを選択し、その選択したＩＰトラヒックの経路を最適化するように部分問題を解く（ステップＳ２）。その際、選択したＩＰトラヒック以外のＩＰトラヒックの経路を変数から除外、つまり一時的に、そのＩＰトラヒックの経路の変数を０に設定する。続いて、次にトラヒック量の多いＸ個のＩＰトラヒックを選択し、その選択したＩＰトラヒックの経路を最適化するように部分問題を解く（ステップＳ３）。そして、全てのＩＰトラヒックに対する経路が最適化されるまでこの処理を繰り返す（ステップＳ４）。

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 Taiju MIKOSHI, Toyofumi TAKENAKA, Ryuta SUGIYAMA, Akeo MASUDA, Kohei SHIOMOTO, "Multi-layer network topology design for large-scale network," Proceedings of the 2011 23rd International Teletraffic Congress(ITC), pp. 306-307, Sept. 2011.

このSpaceReducton法は、物理トポロジが確定して、各対地間ノードのホップ数が分かっていることが前提であるため、物理トポロジが確定している波長レイヤにおける波長パス経路候補を削減することが可能である。しかしながら、波長パスに対応する論理リンクによって構成される論理トポロジ上のＩＰトラヒックは、各対地間の波長パスの有無が確定されていないため、論理リンクが確定されない、そのため、SpaceReducton法により、ＩＰトラヒック経路候補を削減することはできない。
また、Decomposition法は、ＩＰレイヤにも適用可能であり、計算時間を高速化することができるが、トラヒック特性によって、例えば、トラヒック量の差が小さい場合等では、精度が大幅に低下してしまうという問題がある。

このような背景を鑑みて本発明がなされたのであり、本発明は、精度を低下させることなく、計算時間を低減させてネットワーク設計を実行する、ネットワーク設計装置およびネットワーク設計プログラムを提供することを課題とする。

前記した課題を解決するため、請求項１に記載の発明は、波長ノード間の波長パスが物理リンクにより構成される物理網上に設定され、前記設定された波長パスが論理網においてＩＰルータ間の論理リンクを構成し、前記論理網にＩＰトラヒック経路が設定されるＩＰネットワークのネットワーク設計を行うネットワーク設計装置であって、前記物理リンクのトポロジ情報を含む前記ネットワーク設計のための初期情報を記憶すると共に、前記ＩＰルータ間に設定されるＩＰトラヒック経路候補の最短経路のホップ数に比べホップ数が大きすぎるＩＰトラヒック経路を削除する閾値を設定するための上積みホップ数、および、前記波長ノード間の波長パス候補の最短経路のホップ数についての、当該波長パス候補を削除するための閾値である最大ホップ数を示す最短ホップ数の最大値、が記憶される記憶部と、前記初期情報、前記上積みホップ数および前記最短ホップ数の最大値を取得し、前記記憶部に記憶する初期情報取得部と、前記物理リンクのトポロジ情報を参照し、全ての波長ノード間のパスを前記波長パス候補として抽出する波長パス候補抽出部と、前記波長ノード間の前記波長パス候補の最短経路を算出して当該最短経路のホップ数を示す最短ホップ数を算出し、前記算出した最短ホップ数が前記最短ホップ数の最大値を超える波長パス候補を、前記波長パス候補抽出部が抽出した全ての波長パス候補の中から削除する波長パス候補削減部と、前記全ての波長パス候補の中から前記波長パス候補削減部が削除した波長パス候補を除いた波長パス候補に対応する論理リンクによって構成される論理トポロジを用いて、前記ＩＰルータ間に設定される前記ＩＰトラヒック経路候補の最短経路を算出し、当該最短経路のホップ数に前記上積みホップ数を加えた値を超えるホップ数の前記ＩＰトラヒック経路候補を削除するＩＰトラヒック経路候補削減処理部と、前記ＩＰトラヒック経路候補削減処理部により当該削除されたＩＰトラヒック経路候補および前記波長パス候補削減部により削除された波長パス候補を通る波長パス経路候補を変数から除外した上で、前記初期情報を参照し、数理計画法を用いて、前記数理計画法の目的関数において、前記ＩＰネットワークの設備量を最小化させるようにして、前記ＩＰトラヒック経路、前記波長パスの経路および前記波長パスの本数、並びに、前記ＩＰネットワークにおいて必要となる必要設備量の最適解を計算する経路設備量計算部と、を備えることを特徴とするネットワーク設計装置とした。

また、請求項２に記載の発明は、波長ノード間の波長パスが物理リンクにより構成される物理網上に設定され、前記設定された波長パスが論理網においてＩＰルータ間の論理リンクを構成し、前記論理網にＩＰトラヒック経路が設定されるＩＰネットワークのネットワーク設計を行うためのコンピュータを、前記物理リンクのトポロジ情報を含む前記ネットワーク設計のための初期情報を記憶すると共に、前記ＩＰルータ間に設定されるＩＰトラヒック経路候補の最短経路のホップ数に比べホップ数が大きすぎるＩＰトラヒック経路を削除する閾値を設定するための上積みホップ数、および、前記波長ノード間の波長パス候補の最短経路のホップ数についての、当該波長パス候補を削除するための閾値である最大ホップ数を示す最短ホップ数の最大値、が記憶される記憶手段、前記初期情報、前記上積みホップ数および前記最短ホップ数の最大値を取得し、前記記憶手段に記憶する初期情報取得手段、前記物理リンクのトポロジ情報を参照し、全ての波長ノード間のパスを前記波長パス候補として抽出する波長パス候補抽出手段、前記波長ノード間の前記波長パス候補の最短経路を算出して当該最短経路のホップ数を示す最短ホップ数を算出し、前記算出した最短ホップ数が前記最短ホップ数の最大値を超える波長パス候補を、前記波長パス候補抽出手段が抽出した全ての波長パス候補の中から削除する波長パス候補削減手段、前記全ての波長パス候補の中から前記波長パス候補削減手段が削除した波長パス候補を除いた波長パス候補に対応する論理リンクによって構成される論理トポロジを用いて、前記ＩＰルータ間に設定される前記ＩＰトラヒック経路候補の最短経路を算出し、当該最短経路のホップ数に前記上積みホップ数を加えた値を超えるホップ数の前記ＩＰトラヒック経路候補を削除するＩＰトラヒック経路候補削減処理手段、前記ＩＰトラヒック経路候補削減処理手段により当該削除されたＩＰトラヒック経路候補および前記波長パス候補削減手段により削除された波長パス候補を通る波長パス経路候補を変数から除外した上で、前記初期情報を参照し、数理計画法を用いて、前記数理計画法の目的関数において、前記ＩＰネットワークの設備量を最小化させるようにして、前記ＩＰトラヒック経路、前記波長パスの経路および前記波長パスの本数、並びに、前記ＩＰネットワークにおいて必要となる必要設備量の最適解を計算する経路設備量計算手段、として機能させるためのネットワーク設計プログラムとした。

このように、ネットワーク設計装置（ネットワーク設計プログラム）は、波長パス候補を抽出し、その波長パス候補に対応する論理リンクによって構成される論理トポロジを用いて、ＩＰルータ間のＩＰトラヒック経路候補を算出し、そのＩＰトラヒック経路候補の最短経路のホップ数に所定値（上積みホップ数）を加えた値を超える（長すぎる）ホップ数のＩＰトラヒック経路候補を削減することができる。
よって、数理計画法を用いた計算処理において、最適解として計算される可能性が低いＩＰトラヒック経路候補を変数から除外することができるため、精度を低下させることなく、計算時間を低減させて、ＩＰトラヒック経路、波長パスの経路および波長パスの本数、並びに、必要設備量を計算することができる。
また、ネットワーク設計装置は、抽出された波長パス候補のうち、波長ノード間の最短経路のホップ数が所定値（最短ホップ数の最大値）を超える波長パスを波長パス候補から削除することができる。
よって、数理計画法を用いた計算処理において、削除された波長パス候補を通る波長パス経路候補を変数から除外することができるため、さらに計算時間を低減させて、ＩＰトラヒック経路、波長パスの経路および波長パスの本数、並びに、必要設備量を計算することができる。

本発明によれば、精度を低下させることなく、計算時間を低減させてネットワーク設計を実行する、ネットワーク設計装置およびネットワーク設計プログラムを提供することができる。

光ＩＰネットワークの構成例を説明するための図である。 従来技術により計算されたネットワーク設計の一例を説明するための図である。 従来技術のSpaceReducton法を説明するための図である。 従来技術のDecomposition法を説明するための図である。 本実施形態に係るネットワーク設計装置の構成例を示す機能ブロック図である。 本実施形態に係るネットワーク設計装置の波長パス候補削減部による、波長パス候補削減処理を説明するための図である。 本実施形態に係るネットワーク設計装置が実行するネットワーク設計処理の全体の流れを示すフローチャートである。 実験に用いた評価対象の物理トポロジと定数情報を説明するための図である。 実験結果を示す図である。図９（ａ）は、計算時間の評価結果を示し、図９（ｂ）は、目的関数の値の評価結果を示す。

次に、発明を実施するための形態（以下、「実施形態」という）について、適宜図面を参照しながら詳細に説明する。

＜概要＞
本実施形態に係るネットワーク設計装置１等の概要について説明する。
なお、以下に記載する波長ノードとは、図１に示した波長レイヤにおける具体例として、光クロスコネクト（ＯＸＣ）を意味するものである。
本実施形態に係るネットワーク設計装置１は、精度を低下させることなく、計算時間を低減させてネットワーク設計を実行するため、前記した数理計画法を用いた非特許文献１に記載の手法を改良し、波長パス経路に加えて、ＩＰトラヒック経路においても変数の数を削減できるものとした。

具体的には、ネットワーク設計装置１は、一時的に波長パス候補を抽出し、その波長パス候補に基づき論理リンクを仮決めすることにより、ＩＰトポロジ（論理トポロジ）を固定できるようにする。
ネットワーク設計装置１は、まず、全ての波長ノードｉ，ｊ間のパスを波長パス候補として抽出し、抽出した波長パスに基づき、波長ノードｉ，ｊ間の波長パスの最短経路を算出する。そして、ネットワーク設計装置１は、波長ノードｉ，ｊ間の波長パスの最短経路のホップ数（以下、「最短ホップ数Ｌ^P _sp(i,j)」という。）の最大値（以下、「最短ホップ数の最大値ＭＬ_SP(i,j)」という。）に基づき、その最短ホップ数の最大値ＭＬ_SP(i,j)以内のホップ数の波長パスを波長パス候補として出力する。つまり、ネットワーク設計装置１は、最短ホップ数の最大値ＭＬ_SP(i,j)を超えるホップ数の波長パスを削除して、波長パス候補を仮決めする。
また、ネットワーク設計装置１は、仮決めされた波長パス候補に対応する論理リンクよって構成される論理トポロジを用いて、ルータｉ，ｊ間のＩＰトラヒックの最短経路を算出し、その最短経路のホップ数（以下、「最短ホップ数Ｌ^R _SP(i,j)」という。）に所定数（後記する、「上積みホップ数ｋ(i,j)」）を加えたホップ数を閾値としてその閾値を超えるＩＰトラヒック経路を削除する。

このようにすることで、本実施形態に係るネットワーク設計装置１は、波長パス候補を削減して波長パス候補を仮決めし、さらに、その仮決めされた波長パス候補に対応する論理リンクにより構成される論理トポロジに基づいて設定されるＩＰトラヒック経路候補をさらに削減して、数理計画法を実行することができる。つまり、波長パス候補およびＩＰトラヒック経路候補に関する変数を削減して数理計画法を実行することができる。これにより、ネットワーク設計装置１は、精度を低下させることなく、計算時間を低減させてネットワーク設計を実行することが可能となる。

＜ネットワーク設計装置＞
まず、本実施形態に係るネットワーク設計装置１について説明する。
ネットワーク設計装置１は、図１に示す光ＩＰネットワーク１００におけるネットワーク設計を実行する。このネットワーク設計装置１は、ネットワーク設計に必要な初期情報（物理リンクのトポロジ情報４１１や、対地間のトラヒックデマンド情報４１２等）を、各ノードや、光ＩＰネットワーク１００を管理するネットワーク管理装置（不図示）等から取得する。そして、ネットワーク設計装置１は、数理計画法を用いて、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算する。なお、本実施形態において、数理計画法を用いて、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算する処理を、「ネットワーク設計」、または、より詳細な処理内容を示す「経路設備量計算処理」と称して説明する。
その際、ネットワーク設計装置１は、全ての波長パス候補を抽出してその中から、最短ホップ数Ｌ^P _sp(i,j)が最短ホップ数の最大値ＭＬ_SP(i,j)を超える波長パスを波長パス候補から削除して、波長パス候補を決定し、その決定した波長パス候補に基づき論理トポロジを仮決めする。さらに、ネットワーク設計装置１は、その仮決めされた論理トポロジに基づいて設定されるＩＰトラヒック経路候補について、最短ホップ数Ｌ^R _SP(i,j)に所定数（上積みホップ数ｋ(i,j)）を加えたホップ数を超えるＩＰトラヒック経路を削除した上、ネットワーク設計を実行する。

図５は、本実施形態に係るネットワーク設計装置１の構成例を示す機能ブロック図である。図５に示すように、ネットワーク設計装置１は、制御部１０、入出力部２０、メモリ部３０および記憶部４０を備える。

入出力部２０（入出力手段）は、通信回線を介して情報の送受信を行う通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で情報の入出力を行う入出力インタフェースとから構成される。

制御部１０は、ネットワーク設計装置１全体の制御を司り、入出力情報処理部１１と、初期情報取得部１２と、ＩＰトラヒック経路候補削減部１３と、経路設備量計算部１４とを含んで構成される。

入出力情報処理部１１は、入出力部２０を介して、物理リンクのトポロジ情報４１１や対地間のトラヒックデマンド情報４１２等を含む初期情報を取得し、初期情報取得部１２に引き渡す。この初期情報は、経路設備量計算部１４が、数理計画法を用いてネットワーク設計を実行するために必要となる、物理リンクのトポロジ情報４１１や、対地間のトラヒックデマンド情報４１２、ネットワーク内の装置やリンクに関する各初期値の情報であり、詳細は後記する。
また、入出力情報処理部１１は、ＩＰトラヒック経路候補削減部１３が参照する、最短ホップ数の最大値ＭＬ_SP(i,j)および上積みホップ数ｋ(i,j)を取得し、初期情報取得部１２に引き渡す。この最短ホップ数の最大値ＭＬ_SP(i,j)および上積みホップ数ｋ(i,j)の詳細については後記する。
この入出力情報処理部１１は、経路設備量計算部１４が計算した結果である、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を、入出力部２０を介して外部へ出力する。

初期情報取得部１２（初期情報取得手段）は、入出力情報処理部１１を介して、初期情報を取得し、記憶部４０内の初期情報ＤＢ（DataBase）４１に記憶する。また、初期情報取得部１２は、入出力情報処理部１１を介して、最短ホップ数の最大値ＭＬ_SP(i,j)および上積みホップ数ｋ(i,j)を取得し、記憶部４０に記憶する。

ＩＰトラヒック経路候補削減部１３は、経路設備量計算部１４が数理計画法を用いて、ネットワーク設計を実行する際の、波長パス候補やＩＰトラヒック経路候補を削減することにより、ネットワーク設計を実行する際の変数の数を削減する。このＩＰトラヒック経路候補削減部１３は、波長パス候補抽出部１３１と、波長パス候補削減部１３２と、ＩＰトラヒック経路候補削減処理部１３３とを備える。

波長パス候補抽出部１３１（波長パス候補抽出手段）は、記憶部４０内の物理リンクのトポロジ情報４１１を参照し、波長パス候補を抽出する。ここでは、波長パス候補抽出部１３１は、全ての波長ノードｉ，ｊ間のパスを波長パス候補として抽出するものとする。

波長パス候補削減部１３２（波長パス候補削減手段）は、波長パス候補抽出部１３１が抽出した全ての波長パス候補の中から、最短ホップ数Ｌ^P _sp(i,j)が最短ホップ数の最大値ＭＬ_sp(i,j)を超える波長パスを波長パス候補から削除して、波長パス候補を決定する。なお、波長パス候補削減部１３２は、削除した波長パス候補の情報を、経路設備量計算部１４に出力する。
具体的は、波長パス候補削減部１３２は、波長ノードｉ，ｊ間の波長パスの最短経路を算出し、その最短経路のホップ数である最短ホップ数Ｌ^P _sp(i,j)を算出する。そして、波長パス候補削減部１３２は、記憶部４０に記憶された最短ホップ数の最大値ＭＬ_sp(i,j)を参照し、以下の（式１６）を満たす、つまり、波長ノードｉ，ｊ間の最短ホップ数Ｌ^P _sp(i,j)が、最短ホップ数の最大値ＭＬ_SP(i,j)以下の波長パスを波長パス候補として決定する。
Ｌ^P _sp(i,j)≦ＭＬ_sp(i,j) … （式１６）

なお、最短ホップ数の最大値ＭＬ_SP(i,j)は、波長ノードｉ，ｊ間の波長パス候補の最短経路のホップ数（最短ホップ数Ｌ^P _sp(i,j)）についての、当該波長パス候補を削除するための閾値である最大のホップ数を意味する。また、この波長パス候補削減部１３２による処理を、以下において、「波長パス候補削減処理」と称して説明する。この波長パス候補削減処理の具体例を、図６を参照して説明する。

図６は、波長パス候補削減部１３２による、波長パス候補削減処理を説明するための図である。
図６に示すように、波長ノードｉ，ｊ間に、最短ホップ数Ｌ^P _sp(i,j)が「４」の波長パス（波長パス候補）「３」が、波長パス候補削減部１３２により算出されたものとする。このとき、最短ホップ数の最大値ＭＬ_SP(i,j)＝３と設定されていた場合、波長パス候補削減部１３２は、波長ノードｉ，ｊ間の最短ホップ数Ｌ^P _sp(i,j)が、最短ホップ数の最大値ＭＬ_SP(i,j)以下とならず(式１６)を満たさないため、その波長パス（波長パス候補）「３」を削除する。なお、波長ノードｉ，ｊ間を通るＩＰトラヒックは、例えば、波長パス「４」と波長パス「５」といった、最短ホップ数Ｌ^P _sp(i,j)が最短ホップ数の最大値ＭＬ_SP(i,j)以下であり（式１６）の条件を満たす複数の波長パスを繋げることで、通信が可能となるため、ＩＰトラヒック経路の設定においては、特に支障とならず、ネットワーク設計の精度に影響を与えるものではない。

図５に戻り、ＩＰトラヒック経路候補削減処理部１３３（ＩＰトラヒック経路候補削減処理手段）は、波長パス候補削減部１３２により決定された波長パス候補に対応する論理リンクによって構成される論理トポロジを用いて、ルータｉ，ｊ間のＩＰトラヒック経路の最短経路を算出し、その最短経路のホップ数である最短ホップ数Ｌ^R _SP(i,j)を算出する。そして、ＩＰトラヒック経路候補削減処理部１３３は、記憶部４０に記憶された上積みホップ数ｋ(i,j)を参照し、Ｌ^R _SP(i,j)＋ｋ(i,j)を算出し、その算出した値よりホップ数が大きいルータｉ，ｊ間のＩＰトラヒック経路候補を削除する。つまり、ＩＰトラヒック経路候補削減処理部１３３は、最短ホップ数Ｌ^R _SP(i,j)のＩＰトラヒック経路候補に比べ、長すぎる（迂回する）経路（上積みホップ数ｋ(i,j)を加えた値よりもさらにホップ数が大きい経路）のＩＰトラヒック経路候補を削除する。ここで、上積みホップ数ｋ(i,j)は、ルータｉ，ｊ間に設定されるＩＰトラヒック経路候補の最短経路のホップ数（最短ホップ数Ｌ^R _SP(i,j)）に比べホップ数が大きすぎるＩＰトラヒック経路を削除する閾値を設定するための値である。なお、ＩＰトラヒック経路候補削減処理部１３３は、削除したＩＰトラヒック経路候補の情報を、経路設備量計算部１４に出力する。また、このＩＰトラヒック経路候補削減処理部１３３による処理を、以下において、「ＩＰトラヒック経路候補削減処理」と称して説明する。

なお、このＩＰトラヒック経路候補削減処理により、最短ホップ数Ｌ^R _SP(i,j)に比べホップ数の大きい（長すぎる）ＩＰトラヒック経路候補を削除した場合でも、経路設備量計算部１４の数理計画法を用いたネットワーク設計により、その長すぎるＩＰトラヒック経路が最適解として計算される可能性は低いため、ネットワーク設計の精度に影響を与えるものではない。

経路設備量計算部１４（経路設備量計算手段）は、ＩＰトラヒック経路候補削減部１３により、波長パス候補およびＩＰトラヒック経路候補が削減されたことにより、その波長パス候補を通る波長パス経路候補およびＩＰトラヒック経路候補を変数から除外してネットワーク設計を実行する。
具体的には、経路設備量計算部１４は、ＩＰトラヒック経路候補削減部１３が削除した波長パス候補を通る波長パス経路候補については、λ^i,j _m,n＝０とし、削除したＩＰトラヒック経路候補については、ｒ^s,d _i,j＝０とした上で、数理計画法を用いて、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算し最適解を得る。この数理計画法は、前記した非特許文献１に記載の数理計画法を適用することができる。具体的には、経路設備量計算部１４は、前記した（式１）〜（式１４）の制約式を満たす変数λ^i,j，λ^i,j _m,n，ｒ^s,d _i,jに対して、目的関数Σ_i,jλ^i,j + αΣ_i,j,m,nλ^i,j _m,n（式１５）を最小化させる変数を数理計画法によって求めることにより、最適なＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を求める。なお、この経路設備量計算部１４による処理を、以下において、「経路設備量計算処理」と称する場合がある。

ここで、数理計画法で用いる目的関数（式１５）および制約式（式１）〜（式１４）において用いる、符号の定義等をまとめて説明する。

（定数情報）
・ｔ^s,d（対地間のトラヒックデマンド情報４１２）：ルータｓ,ｄ間の交流トラヒックにおけるトラヒック量（トラヒックデマンド）
・Ｂ：論理リンクの最大帯域
・Ｇ_ｊ：ルータｊのルーチング容量
・Ｒ_ｉ：ルータiの論理リンクの最大入力／出力ポート数
・Ｐ_m,n：光クロスコネクト（波長ノード）ｍ,ｎを端点とする物理リンクの最大波長多重数
・Ｏ_n：光クロスコネクト（波長ノード）ｎの最大波長スイッチ数
・α：ルータのインタフェース（ポート）と光クロスコネクト（波長ノード）のインタフェース（ポート）との価格比

（変数情報）
・ｒ^s,d _i,j：ルータｓ,ｄを始点・終点とする交流トラヒックにおいて、ルータｉ,ｊ間の論理リンクを通る交流トラヒック量の割合（＝ＩＰトラヒック経路）
・λ^i,j：ルータｉ,ｊ間の論理リンクの数（＝光クロスコネクト（波長ノード）ｉ,ｊ間の物理リンクを通る波長パスの数）
・λ^i,j _m,n：光クロスコネクト（波長ノード）ｉ,ｊを始点・終点とする波長パスの中で、光クロスコネクト（波長ノード）ｍ,ｎ間の物理リンクを通る波長パスの数（＝波長パス経路）

この数理計画法によるネットワーク設計を実行する際に、経路設備量計算部１４は、変数である波長パス経路（λ^i,j _m,n）のうち、ＩＰトラヒック経路候補削減部１３が削減した波長パス候補を通る波長パス経路ついては、λ^i,j _m,n＝０とし、変数であるＩＰトラヒック経路候補（ｒ^s,d _i,j）のうち、ＩＰトラヒック経路候補削減部１３が削減したＩＰトラヒック経路については、ｒ^s,d _i,j＝０として計算する。
このように、ネットワーク設計装置１は、波長パス経路（λ^i,j _m,n）およびＩＰトラヒック経路（ｒ^s,d _i,j）の変数の数を削減することにより計算時間を低減させて、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算することができる。

図５に戻り、メモリ部（記憶手段）３０は、ＲＡＭ（Random Access Memory）等の一次記憶手段からなり、制御部１０によるデータ処理に必要な情報を一時的に記憶する。

記憶部（記憶手段）４０は、ハードディスクやフラッシュメモリ等の記憶手段からなり、物理リンクのトポロジ情報４１１や、対地間のトラヒックデマンド情報４１２、経路設備量計算部１４が実行する数理計画法を用いた処理において初期情報として必要となる各種の定数情報（Ｂ，Ｇ_ｊ，Ｒ_ｉ，Ｐ_m,n，Ｏ_n，α）等が初期情報ＤＢ４１に記憶される。
また、この記憶部（記憶手段）４０には、最短ホップ数の最大値ＭＬ_SP(i,j)および上積みホップ数ｋ(i,j)が記憶される。

なお、この制御部１０は、例えば、記憶部４０に格納されたプログラム（ネットワーク設計プログラム）をＣＰＵ（Central Processing Unit）がメモリ部３０であるＲＡＭに展開し実行することで実現される。

（処理の流れ）
次に、ネットワーク設計装置１が実行するネットワーク設計処理の全体の流れを説明する。図７は、本実施形態に係るネットワーク設計装置１が実行するネットワーク設計処理の全体の流れを示すフローチャートである。

まず、ネットワーク設計装置１の初期情報取得部１２が、入出力情報処理部１１および入出力部２０を介して、物理リンクのトポロジ情報４１１や、対地間のトラヒックデマンド情報４１２、初期情報として必要となる各種の定数情報（Ｂ，Ｇ_ｊ，Ｒ_ｉ，Ｐ_m,n，Ｏ_n，α等）を取得する（ステップＳ１０）。

次に、ネットワーク設計装置１の初期情報取得部１２は、ネットワーク設計の変数削減のために必要となる情報である、最短ホップ数の最大値ＭＬ_sp(i,j)および上積みホップ数ｋ(i,j)を、入出力情報処理部１１および入出力部２０を介して取得する（ステップＳ１１）。
この最短ホップ数の最大値ＭＬ_sp(i,j)および上積みホップ数ｋ(i,j)の情報や、ステップＳ１０で取得する初期情報を初期情報取得部１２は、光ＩＰネットワーク１００（図１参照）の全体を管理するネットワーク管理装置（不図示）から通信回線を介して取得したり、入力手段により入出力部２０を介して入力された情報として取得することができる。

続いて、波長パス候補抽出部１３１は、記憶部４０内の物理リンクのトポロジ情報４１１を参照し、全ての波長ノードｉ，ｊ間のパスを波長パス候補として抽出する（波長パス候補抽出処理：ステップＳ１２）。

そして、波長パス候補削減部１３２は、波長パス候補を削減するための波長パス候補削減処理を実行する（ステップＳ１３）。
具体的には、波長パス候補削減部１３２は、波長パス候補抽出部１３１が抽出した全ての波長パス候補について、その波長ノードｉ，ｊ間の波長パスの最短経路を算出し、その最短経路のホップ数である最短ホップ数Ｌ^P _sp(i,j)を算出する。そして、波長パス候補削減部１３２は、記憶部４０に記憶された最短ホップ数の最大値ＭＬ_sp(i,j)を参照し、波長ノードｉ，ｊ間の最短ホップ数Ｌ^P _sp(i,j)が、最短ホップ数の最大値ＭＬ_sp(i,j)以下の波長パスを波長パス候補として決定する。つまり、波長パス候補削減部１３２は、波長ノードｉ，ｊ間の最短ホップ数Ｌ^P _sp(i,j)が、最短ホップ数の最大値ＭＬ_sp(i,j)を超える波長パスを波長パス候補から削除するものと決定する。ここで、波長パス候補削減部１３２は、削除した波長パス候補の情報を、経路設備量計算部１４に出力する。

次に、ＩＰトラヒック経路候補削減処理部１３３は、ＩＰトラヒック経路候補を削減するためのＩＰトラヒック経路候補削減処理を実行する（ステップＳ１４）。
具体的には、ＩＰトラヒック経路候補削減処理部１３３は、波長パス候補削減部１３２により決定された波長パス候補に対応する論理リンクによって構成される論理トポロジを用いて、ルータｉ，ｊ間のＩＰトラヒック経路の最短経路を算出し、その最短経路のホップ数である最短ホップ数Ｌ^R _SP(i,j)を算出する。そして、ＩＰトラヒック経路候補削減処理部１３３は、記憶部４０に記憶された上積みホップ数ｋ(i,j)を参照し、Ｌ^R _SP(i,j)＋ｋ(i,j)を算出し、その算出した値よりホップ数が大きいルータｉ，ｊ間のＩＰトラヒック経路候補を削除する。ここで、ＩＰトラヒック経路候補削減処理部１３３は、削除したＩＰトラヒック経路候補の情報を、経路設備量計算部１４に出力する。

続いて、経路設備量計算部１４は、波長パス経路（λ^i,j _m,n）およびＩＰトラヒック経路（ｒ^s,d _i,j）に関する変数を削減した上で、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算する経路設備量計算処理を実行する（ステップＳ１５）。
具体的には、経路設備量計算部１４は、波長パス候補削減部１３２が削減した波長パス候補を通る波長パス経路についてはλ^i,j _m,n＝０とし、ＩＰトラヒック経路候補削減処理部１３３が削減したＩＰトラヒック経路候補については、ｒ^s,d _i,j＝０として変数の数を削減した上で、数理計画法を用いて、ＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を計算し最適解を得る。より詳細には、前記した（式１）〜（式１４）の制約式を満たす変数λ^i,j，λ^i,j _m,n，ｒ^s,d _i,jに対して、目的関数Σ_i,jλ^i,j + αΣ_i,j,m,nλ^i,j _m,n（式１５）を最小化させる変数を数理計画法によって求めることにより、最適なＩＰトラヒック経路、波長パス経路および波長パスの本数、並びに、必要設備量を求める。
このように、ネットワーク設計装置１は、λ^i,j _m,n，ｒ^s,d _i,jの変数の数を削減した上で、数理計画法を用いたネットワーク設計を実行することができる。

（実験結果）
次に、本実施形態に係るネットワーク設計装置１による、ネットワーク設計の実験結果を、従来技術と比較して説明する。

実験では、従来技術として、非特許文献２に記載の、SpaceReduction法を用いた場合、Decomposition法を用いた場合、この両者を用いずに非特許文献１に記載の数理計画法を用いた場合（図９において「高速化手法なし」と記載）について実行し、本実施形態に係るネットワーク設計装置１による処理結果と比較検討した。

実験の概要は、評価対象の物理トポロジとして、ノード数「１３」〜「１６」を設定し（図８には、ノード数「１６」の場合について例示）、定数情報として図８に示す情報（Ｂ，Ｇ_ｊ，Ｒ_ｉ，Ｐ_m,n，Ｏ_n，α，ｔ^s,d（トラヒックデマンド））を初期情報とて設定した。
また、SpaceReduction法においては、ホップ数の上限となる閾値Ｌmax(i,j)＝３とし、Decomposition法においては、部分に分割する数Ｘ＝４０とした。本実施形態に係るネットワーク設計装置１においては、最短ホップ数の最大値ＭＬ_sp(i,j)＝３、上積みホップ数ｋ(i,j)＝３とした。

実験結果を図９に示す。図９（ａ）は、計算時間の評価結果を示し、図９（ｂ）は、目的関数の値の評価結果を示す。

図９（ａ）に示すように、計算時間の実験結果は、ノード数が「１３」〜「１５」において、本実施形態に係るネットワーク設計装置１が最も短時間に処理を終えることができた。なお、ノード数「１６」では、「高速化手法なし」およびSpaceReduction法を用いた場合において、処理開始から５時間を経過しても計算を完了することができなかった。

また、図９（ｂ）に示すように、目的関数の値の評価結果は、ノード数「１３」〜「１５」の場合において、「高速化手法なし」、SpaceReduction法および本実施形態に係るネットワーク設計装置１では、精度の高い値を算出した。これに対し、Decomposition法では、目的関数の値に関する精度が、ノード数「１３」〜「１５」のいずれの場合においても他の方法に比べ低くなることが示された。
以上の実験結果から、本実施形態に係るネットワーク設計装置１によるネットワーク設計は、従来技術に比べ計算時間を低減でき、かつ、計算精度も高いことが示された。

以上説明したように、本実施形態に係るネットワーク設計装置１によれば、数理計画法に用いる、波長パス経路およびＩＰトラヒック経路に関する変数を削減した上で、精度を低下させることなく、計算時間を低減させてネットワーク設計を実行することができる。

（変形例）
なお、本実施形態においては、図５に示したネットワーク設計装置１のＩＰトラヒック経路候補削減部１３において、波長パス候補削減部１３２およびＩＰトラヒック経路候補削減処理部１３３の両方により、数理計画法に用いる変数（λ^i,j _m,n，ｒ^s,d _i,j）の数を削減するものとした。しかしながら、本実施形態はこれに限定されず、例えば、ネットワーク設計装置１のＩＰトラヒック経路候補削減部１３に、波長パス候補削減部１３２を備えない構成としてもよい。この場合、ＩＰトラヒック経路候補削減処理部１３３は、波長パス候補抽出部１３１が抽出した、全ての波長ノードｉ，ｊ間のパスを波長パス候補とした上で、その波長パス候補を用いて、ルータｉ，ｊ間のＩＰトラヒック経路の最短ホップ数Ｌ^R _SP(i,j)を算出する。そして、ＩＰトラヒック経路候補削減処理部１３３は、記憶部４０に記憶された上積みホップ数ｋ(i,j)を参照し、Ｌ^R _SP(i,j)＋ｋ(i,j)よりホップ数が大きいルータｉ，ｊ間のＩＰトラヒック経路候補を削除するようにする。その際、図７に示した全体の処理の流れにおいては、初期情報取得部１２が、ステップＳ１１において、最短ホップ数の最大値ＭＬ_sp(i,j)の情報を取得せず、ステップＳ１３の波長パス候補削減処理がなくなるものとなる。

このような、本実施形態の変形例に係るネットワーク設計装置１においても、数理計画法に用いるＩＰトラヒック経路（ｒ^s,d _i,j）の変数を削減し、精度を低下させることなく、計算時間を低減させてネットワーク設計を実行することができる。

１ ネットワーク設計装置
１０ 制御部
１１ 入出力情報処理部
１２ 初期情報取得部（初期情報取得手段）
１３ ＩＰトラヒック経路候補削減部
１４ 経路設備量計算部（経路設備量計算手段）
２０ 入出力部（入出力手段）
３０ メモリ部（記憶手段）
４０ 記憶部（記憶手段）
４１ 初期情報ＤＢ
１００ 光ＩＰネットワーク
１３１ 波長パス候補抽出部（波長パス候補抽出手段）
１３２ 波長パス候補削減部（波長パス候補削減手段）
１３３ ＩＰトラヒック経路候補削減処理部（ＩＰトラヒック経路候補削減処理手段）
４１１ 物理リンクのトポロジ情報
４１２ 対地間のトラヒックデマンド情報

Claims (2)

1. 波長ノード間の波長パスが物理リンクにより構成される物理網上に設定され、前記設定された波長パスが論理網においてＩＰルータ間の論理リンクを構成し、前記論理網にＩＰトラヒック経路が設定されるＩＰネットワークのネットワーク設計を行うネットワーク設計装置であって、
   前記物理リンクのトポロジ情報を含む前記ネットワーク設計のための初期情報を記憶すると共に、前記ＩＰルータ間に設定されるＩＰトラヒック経路候補の最短経路のホップ数に比べホップ数が大きすぎるＩＰトラヒック経路を削除する閾値を設定するための上積みホップ数、および、前記波長ノード間の波長パス候補の最短経路のホップ数についての、当該波長パス候補を削除するための閾値である最大ホップ数を示す最短ホップ数の最大値、が記憶される記憶部と、
   前記初期情報、前記上積みホップ数および前記最短ホップ数の最大値を取得し、前記記憶部に記憶する初期情報取得部と、
   前記物理リンクのトポロジ情報を参照し、全ての波長ノード間のパスを前記波長パス候補として抽出する波長パス候補抽出部と、
   前記波長ノード間の前記波長パス候補の最短経路を算出して当該最短経路のホップ数を示す最短ホップ数を算出し、前記算出した最短ホップ数が前記最短ホップ数の最大値を超える波長パス候補を、前記波長パス候補抽出部が抽出した全ての波長パス候補の中から削除する波長パス候補削減部と、
   前記全ての波長パス候補の中から前記波長パス候補削減部が削除した波長パス候補を除いた波長パス候補に対応する論理リンクによって構成される論理トポロジを用いて、前記ＩＰルータ間に設定される前記ＩＰトラヒック経路候補の最短経路を算出し、当該最短経路のホップ数に前記上積みホップ数を加えた値を超えるホップ数の前記ＩＰトラヒック経路候補を削除するＩＰトラヒック経路候補削減処理部と、
   前記ＩＰトラヒック経路候補削減処理部により当該削除されたＩＰトラヒック経路候補および前記波長パス候補削減部により削除された波長パス候補を通る波長パス経路候補を変数から除外した上で、前記初期情報を参照し、数理計画法を用いて、前記数理計画法の目的関数において、前記ＩＰネットワークの設備量を最小化させるようにして、前記ＩＰトラヒック経路、前記波長パスの経路および前記波長パスの本数、並びに、前記ＩＰネットワークにおいて必要となる必要設備量の最適解を計算する経路設備量計算部と、
   を備えることを特徴とするネットワーク設計装置。
2. 波長ノード間の波長パスが物理リンクにより構成される物理網上に設定され、前記設定された波長パスが論理網においてＩＰルータ間の論理リンクを構成し、前記論理網にＩＰトラヒック経路が設定されるＩＰネットワークのネットワーク設計を行うためのコンピュータを、
   前記物理リンクのトポロジ情報を含む前記ネットワーク設計のための初期情報を記憶すると共に、前記ＩＰルータ間に設定されるＩＰトラヒック経路候補の最短経路のホップ数に比べホップ数が大きすぎるＩＰトラヒック経路を削除する閾値を設定するための上積みホップ数、および、前記波長ノード間の波長パス候補の最短経路のホップ数についての、当該波長パス候補を削除するための閾値である最大ホップ数を示す最短ホップ数の最大値、が記憶される記憶手段、
   前記初期情報、前記上積みホップ数および前記最短ホップ数の最大値を取得し、前記記憶手段に記憶する初期情報取得手段、
   前記物理リンクのトポロジ情報を参照し、全ての波長ノード間のパスを前記波長パス候補として抽出する波長パス候補抽出手段、
   前記波長ノード間の前記波長パス候補の最短経路を算出して当該最短経路のホップ数を示す最短ホップ数を算出し、前記算出した最短ホップ数が前記最短ホップ数の最大値を超える波長パス候補を、前記波長パス候補抽出手段が抽出した全ての波長パス候補の中から削除する波長パス候補削減手段、
   前記全ての波長パス候補の中から前記波長パス候補削減手段が削除した波長パス候補を除いた波長パス候補に対応する論理リンクによって構成される論理トポロジを用いて、前記ＩＰルータ間に設定される前記ＩＰトラヒック経路候補の最短経路を算出し、当該最短経路のホップ数に前記上積みホップ数を加えた値を超えるホップ数の前記ＩＰトラヒック経路候補を削除するＩＰトラヒック経路候補削減処理手段、
   前記ＩＰトラヒック経路候補削減処理手段により当該削除されたＩＰトラヒック経路候補および前記波長パス候補削減手段により削除された波長パス候補を通る波長パス経路候補を変数から除外した上で、前記初期情報を参照し、数理計画法を用いて、前記数理計画法の目的関数において、前記ＩＰネットワークの設備量を最小化させるようにして、前記ＩＰトラヒック経路、前記波長パスの経路および前記波長パスの本数、並びに、前記ＩＰネットワークにおいて必要となる必要設備量の最適解を計算する経路設備量計算手段、
   として機能させるためのネットワーク設計プログラム。

Images