(57)【特許請求の範囲】
【請求項１】
複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークを対象として、経路変更後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置であって、
前記ネットワークに関する情報の送受信を行う入出力部と、
前記入出力部が受信した前記ネットワークに関する情報を、（１）前記各リンクの帯域の情報を示すリンク帯域ベクトル、（２）各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列、および（３）経路変更された後の前記交流トラヒックの経路を示す経路変更後交流トラヒック経路行列として、記憶部に記憶する情報収集部と、
前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック行列が記憶される前記記憶部と、
以下に示す線形計画法による計算式に基づき、目的関数（式１）において経路が変更された前記交流トラヒックの交流トラヒック帯域ｔｊを抽出し、その抽出した前記交流トラヒック帯域ｔｊを含む等号条件式の集合を、制約条件式（式２）を構成する式の中から、制約条件式（式２−１）として選択する制約条件選択部と、
前記制約条件式（式２−１）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−１）として選択する変数選択部と、
前記変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔｊを変数として用いる前記目的関数（式１）を目的関数（式１−１）とし、前記目的関数（式１−１）、前記制約条件式（式２−１）および制約条件式（式３）による線形計画法による計算式を、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列を用いて解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するリンク帯域変動量上限ベクトル計算部と、
前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力する情報出力部と、
を備えることを特徴とするリンク帯域変動量上限計算装置。
ただし、前記線形計画法による計算式は、
【数１】
0005325167.tif 000012
【請求項２】
前記情報収集部は、前記入出力部を介して、前記線形計画法による計算式で用いる変数の数に関し、数値が増えるほど前記変数の数の増加を示す指標である高速化レベルの目標値である目標高速化レベルｎ（ｎは正の整数）をさらに取得して、前記記憶部に記憶し、
前記制約条件選択部は、
前記制約条件式（式２−１）を選択した後の次の前記高速化レベルにおいて、前記制約条件式（式２）を構成する式の中から、前記変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔｊを含む等号条件式の集合を、制約条件式（式２−２）として選択し、
前記変数選択部は、
前記制約条件式（式２−２）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−２）として選択し、
前記制約条件選択部および前記変数選択部は、前記制約条件式（式２）からの等号条件式の集合の選択と、前記変数の集合の選択とを、前記記憶部に記憶された目標高速化レベルｎで示される回数まで繰り返すことにより、前記制約条件選択部が、制約条件式（式２−ｎ）を選択し、前記変数選択部が、前記制約条件式（式２−ｎ）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−ｎ）として選択し、
前記リンク帯域変動量上限ベクトル計算部は、
前記変数の集合（Ｖ−ｎ）に含まれる交流トラヒック帯域ｔｊを変数として用いる前記目的関数（式１）を目的関数（式１−ｎ）とし、前記目的関数（式１−ｎ）、前記制約条件式（式２−ｎ）および制約条件式（式３）による線形計画法による計算式を、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列を用いて解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成すること
を特徴とする請求項１に記載のリンク帯域変動量上限計算装置。
【請求項３】
前記リンク帯域変動量上限計算装置は、さらに変数数出力部および変数数判定部を備えており、
前記制約条件選択部は、
前記制約条件式（式２−１）を選択した後の次の高速化レベルにおいて、前記制約条件式（式２）を構成する式の中から、前記変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔｊを含む等号条件式の集合を、制約条件式（式２−２）として選択し、
前記変数選択部は、
前記制約条件式（式２−２）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−２）として選択し、
前記制約条件選択部および前記変数選択部は、前記制約条件式（式２）からの等号条件式の集合の選択と、前記変数の集合の選択とを、前記線形計画法による計算式で用いる変数の数に関し、数値が増えるほど前記変数の数の増加を示す指標である前記高速化レベルｋ（ｋは正の整数）で示される回数まで繰り返すことにより、前記制約条件選択部が、制約条件式（式２−ｋ）を選択し、前記変数選択部が、前記制約条件式（式２−ｋ）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−ｋ）として選択し、
前記変数数出力部は、
前記変数選択部が選択した変数の集合（Ｖ−ｋ）に含まれる交流トラヒック帯域ｔｊの数であるＮ（Ｖ−ｋ）を計算し、
前記変数数判定部は、
前記変数数出力部が計算した高速化レベルｋにおけるＮ（Ｖ−ｋ）と、前記高速化レベルｋの１つ前の高速化レベル（ｋ−１）において前記変数数出力部が計算した変数の集合（Ｖ−（ｋ−１））に含まれる交流トラヒック帯域ｔｊの数であるＮ（Ｖ−（ｋ−１））とが同じか否かを判定し、
前記変数数判定部が、前記高速化レベルｋにおけるＮ（Ｖ−ｋ）と、前記高速化レベル（ｋ−１）におけるＮ（Ｖ−（ｋ−１））とが同じ数であると判定した場合に、
前記リンク帯域変動量上限ベクトル計算部は、
前記変数の集合（Ｖ−ｋ）に含まれる交流トラヒック帯域ｔｊを変数として用いる前記目的関数（式１）を目的関数（式１−ｋ）とし、前記目的関数（式１−ｋ）、前記制約条件式（式２−ｋ）および制約条件式（式３）による線形計画法による計算式を、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列を用いて解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成すること
を特徴とする請求項１に記載のリンク帯域変動量上限計算装置。
【請求項４】
複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークを対象として、経路変更後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置に用いられるリンク帯域変動量上限計算方法であって、
前記リンク帯域変動量上限計算装置は、
前記ネットワークに関する情報の送受信を行う入出力部と、
前記入出力部が受信した前記ネットワークに関する情報を、（１）前記各リンクの帯域の情報を示すリンク帯域ベクトル、（２）各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列、および（３）経路変更された後の前記交流トラヒックの経路を示す経路変更後交流トラヒック経路行列として記憶させる記憶部とを備え、
前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック行列を示す情報を、前記入出力部を介して取得するステップと、
以下に示す線形計画法による計算式に基づき、目的関数（式１）において経路が変更された前記交流トラヒックの交流トラヒック帯域ｔｊを抽出し、その抽出した前記交流トラヒック帯域ｔｊを含む等号条件式の集合を、制約条件式（式２）を構成する式の中から、制約条件式（式２−１）として選択するステップと、
前記制約条件式（式２−１）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−１）として選択するステップと、
前記変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔｊを変数として用いる前記目的関数（式１）を目的関数（式１−１）とし、前記目的関数（式１−１）、前記制約条件式（式２−１）および制約条件式（式３）による線形計画法による計算式を、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列を用いて解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するステップと、
前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力するステップと、
を実行することを特徴とするリンク帯域変動量上限計算方法。
ただし、前記線形計画法による計算式は、
【数２】
0005325167.tif 000013
【請求項５】
前記入出力部を介して、前記線形計画法による計算式で用いる変数の数に関し、数値が増えるほど前記変数の数の増加を示す指標である高速化レベルの目標値である目標高速化レベルｎ（ｎは正の整数）をさらに取得して、前記記憶部に記憶するステップと、
前記制約条件式（式２−１）を選択した後の次の前記高速化レベルにおいて、前記制約条件式（式２）を構成する式の中から、前記変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔｊを含む等号条件式の集合を、制約条件式（式２−２）として選択するステップと、
前記制約条件式（式２−２）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−２）として選択するステップと、
前記制約条件式（式２）から等号条件式の集合を選択するステップと、前記変数の集合を選択するステップとを、前記記憶部に記憶された目標高速化レベルｎで示される回数まで繰り返すことにより、制約条件式（式２−ｎ）を選択し、前記選択した前記制約条件式（式２−ｎ）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−ｎ）として選択するステップと、
前記変数の集合（Ｖ−ｎ）に含まれる交流トラヒック帯域ｔｊを変数として用いる前記目的関数（式１）を目的関数（式１−ｎ）とし、前記目的関数（式１−ｎ）、前記制約条件式（式２−ｎ）および制約条件式（式３）による線形計画法による計算式を、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列を用いて解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するステップと、
を実行することを特徴とする請求項４に記載のリンク帯域変動量上限計算方法。
【請求項６】
前記制約条件式（式２−１）を選択した後の次の高速化レベルにおいて、前記制約条件式（式２）を構成する式の中から、前記変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔｊを含む等号条件式の集合を、制約条件式（式２−２）として選択するステップと、
前記制約条件式（式２−２）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−２）として選択するステップと、
前記制約条件式（式２）から等号条件式の集合を選択するステップと、前記変数の集合を選択するステップとを、前記線形計画法による計算式で用いる変数の数に関し、数値が増えるほど前記変数の数の増加を示す指標である前記高速化レベルｋ（ｋは正の整数）で示される回数まで繰り返すことにより、制約条件式（式２−ｋ）を選択し、前記選択した制約条件式（式２−ｋ）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−ｋ）として選択するステップと、
前記選択した変数の集合（Ｖ−ｋ）に含まれる交流トラヒック帯域ｔｊの数であるＮ（Ｖ−ｋ）を計算するステップと、
前記計算した高速化レベルｋにおけるＮ（Ｖ−ｋ）と、前記高速化レベルｋの１つ前の高速化レベル（ｋ−１）において前記計算された変数の集合（Ｖ−（ｋ−１））に含まれる交流トラヒック帯域ｔｊの数であるＮ（Ｖ−（ｋ−１））とが同じか否かを判定するステップと、
前記高速化レベルｋにおけるＮ（Ｖ−ｋ）と、前記高速化レベル（ｋ−１）におけるＮ（Ｖ−（ｋ−１））とが同じ数であると判定された場合に、
前記変数の集合（Ｖ−ｋ）に含まれる交流トラヒック帯域ｔｊを変数として用いる前記目的関数（式１）を目的関数（式１−ｋ）とし、前記目的関数（式１−ｋ）、前記制約条件式（式２−ｋ）および制約条件式（式３）による線形計画法による計算式を、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列を用いて解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するステップと、
を実行することを特徴とする請求項４に記載のリンク帯域変動量上限計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク上の各リンクの帯域設計に用いる、リンク帯域変動量上限計算装置およびリンク帯域変動量上限計算方法に関する。
【背景技術】
【０００２】
品質保証を特徴とするネットワークサービスにおいては、安全かつ高品質なＩＰ（Internet Protocol）網の設計・運用が求められており、障害発生時のサービス継続に加えて、迂回トラヒックによる輻輳発生を考慮したネットワーク設計が必要となる。従来の一般的な設備設計においては、リンク単位の帯域を定期的に計測し、帯域が予め定めた閾値を超えたら、リンクを増設する方法をとっていた（非特許文献１参照）。
【０００３】
しかし、非特許文献１に記載されたリンク単位の帯域を計測する技術では、エッジルータ間の交流トラヒックを考慮しておらず、以下に説明するように、厳密なリンク帯域設計が困難であった。
【０００４】
各リンク帯域と障害発生前後の各交流トラヒックの経路を事前に把握している場合、各交流トラヒックの帯域が特定できれば、障害発生による各リンクの帯域変動値を求めることができる。例えば、図１２において、交流トラヒックＡ（帯域：ａ），Ｂ（帯域：ｂ），Ｃ（帯域：ｃ）が流れるリンク＃１で障害が発生した場合、リンク＃４，＃５，＃６の増加量はａ＋ｂであり、リンク＃７，＃８，＃９，＃１０の増加量はｃである。しかし、従来技術においては、交流トラヒックの帯域の特定が困難であるため、各交流トラヒックの帯域を考慮しないリンク帯域変動範囲として、障害発生前の障害リンクの帯域値を変動範囲の上限とする。つまり、従来技術によれば、図１２において、リンク＃４，＃５，＃６、およびリンク＃７，＃８，＃９，＃１０の帯域変動の上限を障害発生前のリンク＃１の帯域であり、交流トラヒックＡ，Ｂ，Ｃの帯域の和であるａ＋ｂ＋ｃとして帯域設計を行う。しかし、実際の帯域変動量と比べると、リンク＃４，＃５，＃６ではｃ、リンク＃７，＃８，＃９，＃１０ではａ＋ｂの帯域が無駄になってしまう。
【０００５】
そこで、迂回トラヒックによる輻輳発生の回避を考慮したリンク帯域設計法として、交流トラヒック帯域を変数として扱い、リンク帯域情報から線形計画法により、各交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値を算出する方法を提案した（非特許文献２参照）。
【０００６】
この線形計画法により帯域変動量の上限値を算出する方法は、経路変更あるいは障害発生等により、各交流トラヒックの経路が変更されたときのリンク帯域変動量の上限値（最大値）を線形計画法によって求め、その上限値に基づいて、各リンクの帯域設計を行うものである。ここで、線形計画法による計算式は、以下の（式１）〜（式３）で表される。
【０００７】
【数１】
0005325167.tif 000002
【０００８】
この（式１）〜（式３）に示す線形計画法による計算式は、この制約条件式（式２）および（式３）を満たす範囲内で、各ｔｊを変動させて目的式（式１）を満たすリンク帯域変動量の上限値を最大化させるものである。
【０００９】
この線形計画法による計算式を解くことにより得られた各リンクの帯域変動量の上限値は、経路変更後に必要と見積もられる帯域増設量の中で最小値となるため、リンク帯域設計において、実際に必要な帯域増設量からの余剰帯域、つまり無駄となる帯域設計量を低減することが可能となる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】小島久史，他、「交流トラヒックを用いたネットワーク設計・運用方式の提案」、電子情報通信学会総合大会、B-6-9  2009年3月
【非特許文献２】杉山隆太，他、「ＩＰ網における障害発生時のリンク帯域変動量上限値計算方法」、電子情報通信学会総合大会、B-6-12  2009年9月
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、この（式１）〜（式３）の線形計画法による計算式を用いた帯域変動量の上限値算出方法では、この線形計画法で用いる変数（交流トラヒック帯域ｔｊ）の数、制約条件式の数が、それぞれ対象とするネットワークの交流トラヒック数、リンク数となるため、ネットワークの規模が大きくなると、変数の数および制約条件式の数が大きくなり、線形計画法による計算時間が長大となってしまう。
【００１２】
このような背景に鑑みて本発明がなされたのであり、本発明は、ネットワークの規模が大きくても、線形計画法によるリンク帯域変動量の上限値の計算時間を低減することができる、リンク帯域変動量上限計算装置およびリンク帯域変動量上限計算方法を提供することを課題とする。
【課題を解決するための手段】
【００１３】
前記した課題を解決するため、請求項１に記載の発明は、複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークを対象として、経路変更後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置であって、前記ネットワークに関する情報の送受信を行う入出力部と、前記入出力部が受信した前記ネットワークに関する情報を、（１）前記各リンクの帯域の情報を示すリンク帯域ベクトル、（２）各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列、および（３）経路変更された後の前記交流トラヒックの経路を示す経路変更後交流トラヒック経路行列として、記憶部に記憶する情報収集部と、前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック行列が記憶される前記記憶部と、以下に示す線形計画法による計算式に基づき、目的関数（式１）において経路が変更された前記交流トラヒックの交流トラヒック帯域ｔｊを抽出し、その抽出した前記交流トラヒック帯域ｔｊを含む等号条件式の集合を、制約条件式（式２）を構成する式の中から、制約条件式（式２−１）として選択する制約条件選択部と、前記制約条件式（式２−１）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−１）として選択する変数選択部と、前記変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔｊを変数として用いる前記目的関数（式１）を目的関数（式１−１）とし、前記目的関数（式１−１）、前記制約条件式（式２−１）および制約条件式（式３）による線形計画法による計算式を、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列を用いて解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するリンク帯域変動量上限ベクトル計算部と、前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力する情報出力部と、を備えることを特徴とするリンク帯域変動量上限計算装置とした。ただし、前記線形計画法による計算式は、請求項１に記載の計算式である。
【００１４】
また、請求項４に記載の発明は、複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークを対象として、経路変更後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置に用いられるリンク帯域変動量上限計算方法であって、前記リンク帯域変動量上限計算装置が、前記ネットワークに関する情報の送受信を行う入出力部と、前記入出力部が受信した前記ネットワークに関する情報を、（１）前記各リンクの帯域の情報を示すリンク帯域ベクトル、（２）各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列、および（３）経路変更された後の前記交流トラヒックの経路を示す経路変更後交流トラヒック経路行列として記憶させる記憶部とを備え、前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック行列を示す情報を、前記入出力部を介して取得するステップと、以下に示す線形計画法による計算式に基づき、目的関数（式１）において経路が変更された前記交流トラヒックの交流トラヒック帯域ｔｊを抽出し、その抽出した前記交流トラヒック帯域ｔｊを含む等号条件式の集合を、制約条件式（式２）を構成する式の中から、制約条件式（式２−１）として選択するステップと、前記制約条件式（式２−１）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−１）として選択するステップと、前記変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔｊを変数として用いる前記目的関数（式１）を目的関数（式１−１）とし、前記目的関数（式１−１）、前記制約条件式（式２−１）および制約条件式（式３）による線形計画法による計算式を、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列を用いて解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するステップと、前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力するステップと、を実行することを特徴とするリンク帯域変動量上限計算方法とした。ただし、前記線形計画法による計算式は、請求項４に記載の計算式である。
【００１５】
よって、本発明によれば、線形計画法で用いる変数の数、制約条件式の数を低減させた上で、線形計画法による計算を行うため、計算時間が長大になることを防ぐことができる。つまり、本リンク帯域変動量上限計算装置の計算処理を高速化することができる。
【００１６】
請求項２に記載の発明は、前記情報収集部は、前記入出力部を介して、前記線形計画法による計算式で用いる変数の数に関し、数値が増えるほど前記変数の数の増加を示す指標である高速化レベルの目標値である目標高速化レベルｎ（ｎは正の整数）をさらに取得して、前記記憶部に記憶し、前記制約条件選択部が、前記制約条件式（式２−１）を選択した後の次の前記高速化レベルにおいて、前記制約条件式（式２）を構成する式の中から、前記変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔｊを含む等号条件式の集合を、制約条件式（式２−２）として選択し、前記変数選択部が、前記制約条件式（式２−２）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−２）として選択し、前記制約条件選択部および前記変数選択部が、前記制約条件式（式２）からの等号条件式の集合の選択と、前記変数の集合の選択とを、前記記憶部に記憶された目標高速化レベルｎで示される回数まで繰り返すことにより、前記制約条件選択部が、制約条件式（式２−ｎ）を選択し、前記変数選択部が、前記制約条件式（式２−ｎ）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−ｎ）として選択し、前記リンク帯域変動量上限ベクトル計算部が、前記変数の集合（Ｖ−ｎ）に含まれる交流トラヒック帯域ｔｊを変数として用いる前記目的関数（式１）を目的関数（式１−ｎ）とし、前記目的関数（式１−ｎ）、前記制約条件式（式２−ｎ）および制約条件式（式３）による線形計画法による計算式を、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列を用いて解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成することを特徴とする請求項１に記載のリンク帯域変動量上限計算装置とした。
【００１７】
また、請求項５に記載の発明は、前記入出力部を介して、前記線形計画法による計算式で用いる変数の数に関し、数値が増えるほど前記変数の数の増加を示す指標である高速化レベルの目標値である目標高速化レベルｎ（ｎは正の整数）をさらに取得して、前記記憶部に記憶するステップと、前記制約条件式（式２−１）を選択した後の次の前記高速化レベルにおいて、前記制約条件式（式２）を構成する式の中から、前記変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔｊを含む等号条件式の集合を、制約条件式（式２−２）として選択するステップと、前記制約条件式（式２−２）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−２）として選択するステップと、前記制約条件式（式２）から等号条件式の集合を選択するステップと、前記変数の集合を選択するステップとを、前記記憶部に記憶された目標高速化レベルｎで示される回数まで繰り返すことにより、制約条件式（式２−ｎ）を選択し、前記選択した前記制約条件式（式２−ｎ）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−ｎ）として選択するステップと、前記変数の集合（Ｖ−ｎ）に含まれる交流トラヒック帯域ｔｊを変数として用いる前記目的関数（式１）を目的関数（式１−ｎ）とし、前記目的関数（式１−ｎ）、前記制約条件式（式２−ｎ）および制約条件式（式３）による線形計画法による計算式を、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列を用いて解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するステップと、を実行することを特徴とする請求項４に記載のリンク帯域変動量上限計算方法とした。
【００１８】
よって、本発明によれば、目標高速化レベルｎを設定した上で、線形計画法で用いる変数の数、制約式の数を低減させて、線形計画法による計算処理を行うことができる。
【００１９】
請求項３に記載の発明は、前記リンク帯域変動量上限計算装置は、さらに変数数出力部および変数数判定部を備えており、前記制約条件選択部が、前記制約条件式（式２−１）を選択した後の次の高速化レベルにおいて、前記制約条件式（式２）を構成する式の中から、前記変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔｊを含む等号条件式の集合を、制約条件式（式２−２）として選択し、前記変数選択部が、前記制約条件式（式２−２）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−２）として選択し、前記制約条件選択部および前記変数選択部が、前記制約条件式（式２）からの等号条件式の集合の選択と、前記変数の集合の選択とを、前記線形計画法による計算式で用いる変数の数に関し、数値が増えるほど前記変数の数の増加を示す指標である前記高速化レベルｋ（ｋは正の整数）で示される回数まで繰り返すことにより、前記制約条件選択部が、制約条件式（式２−ｋ）を選択し、前記変数選択部が、前記制約条件式（式２−ｋ）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−ｋ）として選択し、前記変数数出力部が、前記変数選択部が選択した変数の集合（Ｖ−ｋ）に含まれる交流トラヒック帯域ｔｊの数であるＮ（Ｖ−ｋ）を計算し、前記変数数判定部が、前記変数数出力部が計算した高速化レベルｋにおけるＮ（Ｖ−ｋ）と、前記高速化レベルｋの１つ前の高速化レベル（ｋ−１）において前記変数数出力部が計算した変数の集合（Ｖ−（ｋ−１））に含まれる交流トラヒック帯域ｔｊの数であるＮ（Ｖ−（ｋ−１））とが同じか否かを判定し、前記変数数判定部が、前記高速化レベルｋにおけるＮ（Ｖ−ｋ）と、前記高速化レベル（ｋ−１）におけるＮ（Ｖ−（ｋ−１））とが同じ数であると判定した場合に、前記リンク帯域変動量上限ベクトル計算部が、前記変数の集合（Ｖ−ｋ）に含まれる交流トラヒック帯域ｔｊを変数として用いる前記目的関数（式１）を目的関数（式１−ｋ）とし、前記目的関数（式１−ｋ）、前記制約条件式（式２−ｋ）および制約条件式（式３）による線形計画法による計算式を、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列を用いて解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成することを特徴とする請求項１に記載のリンク帯域変動量上限計算装置とした。
【００２０】
また、請求項６に記載の発明は、前記制約条件式（式２−１）を選択した後の次の高速化レベルにおいて、前記制約条件式（式２）を構成する式の中から、前記変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔｊを含む等号条件式の集合を、制約条件式（式２−２）として選択するステップと、前記制約条件式（式２−２）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−２）として選択するステップと、前記制約条件式（式２）から等号条件式の集合を選択するステップと、前記変数の集合を選択するステップとを、前記線形計画法による計算式で用いる変数の数に関し、数値が増えるほど前記変数の数の増加を示す指標である前記高速化レベルｋ（ｋは正の整数）で示される回数まで繰り返すことにより、制約条件式（式２−ｋ）を選択し、前記選択した制約条件式（式２−ｋ）で示される各等号条件式で用いられる交流トラヒック帯域ｔｊを、当該等号条件式で用いられる変数の集合（Ｖ−ｋ）として選択するステップと、前記選択した変数の集合（Ｖ−ｋ）に含まれる交流トラヒック帯域ｔｊの数であるＮ（Ｖ−ｋ）を計算するステップと、前記計算した高速化レベルｋにおけるＮ（Ｖ−ｋ）と、前記高速化レベルｋの１つ前の高速化レベル（ｋ−１）において前記計算された変数の集合（Ｖ−（ｋ−１））に含まれる交流トラヒック帯域ｔｊの数であるＮ（Ｖ−（ｋ−１））とが同じか否かを判定するステップと、前記高速化レベルｋにおけるＮ（Ｖ−ｋ）と、前記高速化レベル（ｋ−１）におけるＮ（Ｖ−（ｋ−１））とが同じ数であると判定された場合に、前記変数の集合（Ｖ−ｋ）に含まれる交流トラヒック帯域ｔｊを変数として用いる前記目的関数（式１）を目的関数（式１−ｋ）とし、前記目的関数（式１−ｋ）、前記制約条件式（式２−ｋ）および制約条件式（式３）による線形計画法による計算式を、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列を用いて解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するステップと、を実行することを特徴とする請求項４に記載のリンク帯域変動量上限計算方法とした。
【００２１】
よって、本発明によれば、計算精度を最優先して、線形計画法で用いる変数の数、制約式の数を低減させた上で、計算を行うことができる。
【発明の効果】
【００２２】
本発明によれば、線形計画法によるリンク帯域変動量の上限値の計算時間を低減することができる、リンク帯域変動量上限計算装置およびリンク帯域変動量上限計算方法を提供することが可能となる。
【図面の簡単な説明】
【００２３】
【図１】本実施形態に係るリンク帯域変動量上限計算装置が、リンク帯域変動量の上限計算処理を行うネットワークの一例を示す図である。
【図２】本実施形態に係るリンク帯域ベクトルを説明するための図である。
【図３】本実施形態に係る交流トラヒック帯域ベクトルを説明するための図である。
【図４】本実施形態に係る交流トラヒック経路行列を説明するための図である。
【図５】本発明の第１の実施形態に係るリンク帯域変動量上限計算装置の構成例を示す機能ブロック図である。
【図６】本発明の第１の実施形態に係るリンク帯域変動量上限計算処理の流れを示すフローチャートである。
【図７】本発明の第２の実施形態に係るリンク帯域変動量上限計算装置の構成例を示す機能ブロック図である。
【図８】本発明の第２の実施形態に係るリンク帯域変動量上限計算処理の流れを示すフローチャートである。
【図９】本発明の第３の実施形態に係るリンク帯域変動量上限計算装置の構成例を示す機能ブロック図である。
【図１０】本発明の第３の実施形態に係るリンク帯域変動量上限計算処理の流れを示すフローチャートである。
【図１１】本発明の実施形態に係るリンク帯域変動量上限計算方法と従来法を比較した実験結果を示す図である。
【図１２】従来技術における帯域変動値の決定方法を説明するための図である。
【発明を実施するための形態】
【００２４】
次に、発明を実施するための形態（以下、「実施形態」という）について、適宜図面を参照しながら詳細に説明する。まず、本実施形態に係るリンク帯域変動量上限計算処理において取り扱うネットワークの各情報について説明する。
【００２５】
図１は、本実施形態に係るリンク帯域変動量上限計算装置１が、リンク帯域変動量の上限計算処理を行うネットワークの一例を示す図である。図１に示すネットワークにおいて、ノードの障害やリンクの障害の発生を想定したときの経路変更後の各リンクのリンク帯域変動量の上限を、リンク帯域変動量上限計算装置１が計算する処理を例として説明する。
【００２６】
図１に示すように、例えば、ノード「０」，ノード「１」，ノード「２」，ノード「３」の４つのノードが、それぞれリンクにより接続される。リンクは、送信元のノードと送信先のノードとを接続し、ノード間でトラヒックの流れる方向により、例えば、ノード「０」からノード「１」へのリンクはリンク＃０、ノード「１」からノード「０」へのリンクはリンク＃５、のようにトラヒックの流れる方向により別々に設定される。
【００２７】
本実施形態に係るリンク帯域変動量上限計算装置１は、各リンクの現時点（経路変更前）の帯域の情報を示すリンク帯域ベクトル１００、現時点（経路変更前）のトラヒックの経路を示す交流トラヒック経路行列２００、および障害発生等により各交流トラヒックの経路が変更されたと想定したときの経路変更後の交流トラヒック経路行列３００を用いて、以下に説明する線形計画法による計算式を解くことによって、各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトル１０００を生成する。
【００２８】
ここで、リンク帯域ベクトル１００、交流トラヒック帯域ベクトル、および交流トラヒック経路行列２００について説明する。
【００２９】
図２は、本実施形態に係るリンク帯域ベクトル１００を説明するための図である。リンク帯域ベクトル１００は、各リンクで測定されるトラヒック帯域をリンク番号順にベクトル表示したものである。例えば、図２（ａ）に示すネットワークにおいて、リンク帯域ベクトル１００は、図２（ｂ）に示すように、リンク＃０からリンク＃９で測定される帯域をリンク番号順にベクトル表示する。ここでは、例えば、リンク＃０で測定された帯域が「１５（Ｍｂｐｓ）」であり、リンク＃１で測定された帯域が「９（Ｍｂｐｓ）」であることを示す。
【００３０】
なお、リンク帯域ベクトル１００は、
リンク帯域ベクトルＸ＝（ｘ０，ｘ１，…，ｘＬ−１）ｔｒ
と表記でき、ここで  tr は、行列（ベクトル）の転置（行と列の入れ替え）を意味する。
【００３１】
図３は、本実施形態に係る交流トラヒック帯域ベクトルを説明するための図である。交流トラヒックは、ネットワーク内の２つのノード間のトラヒックの流れを意味する。また、交流トラヒック帯域とは、交流トラヒックの帯域値を意味する。図３（ａ）は、ノード「０」からノード「３」までの４つのノードにおける、各交流トラヒックを示し、図３（ｂ）は、各交流トラヒックで測定される交流トラヒック量（交流トラヒック帯域）を交流トラヒック番号順にベクトル表示した交流トラヒック帯域ベクトルである。例えば、交流トラヒック「０」（ノード「０」からノード「１」）の交流トラヒック量（交流トラヒック帯域）は「４（Ｍｂｐｓ）」であることを示す。
【００３２】
なお、この交流トラヒック帯域ベクトルは、
交流トラヒック帯域ベクトルＴ＝（ｔ０，ｔ１，…，ｔＴ−１）ｔｒ
と表記できる。
【００３３】
図４は、本実施形態に係る交流トラヒック経路行列２００を説明するための図である。交流トラヒック経路行列２００は、各交流トラヒックが各リンクを経由しているか否かを、経由する場合は「１」、経由しない場合は「０」で表すことにより、各交流トラヒックの経路を示す行列である。各交流トラヒックが図４（ａ）のように、各リンクを経由している場合において、交流トラヒック経路行列は、図４（ｂ）に示すように、各リンクと各交流トラヒックとの関係を行列で表示する。例えば、交流トラヒック「１」（ノード「０」からノード「２」へのトラヒック）は、図４（ｂ）の交流トラヒック経路行列２００において、リンク＃０とリンク＃１との値が「１」になっていることから、リンク＃０とリンク＃１とを経由することが示される。
【００３４】
次に、本発明の第１〜３の実施形態について説明する。第１の実施形態は、リンク帯域変動量上限計算装置１が、予め経路変更後の交流トラヒック経路行列３００を取得して経路変更前の交流トラヒック経路行列２００と比較することにより、経路が変更された交流トラヒックの交流トラヒック帯域ｔｊ（つまり、
0005325167.tif 000003
となる交流トラヒック帯域ｔｊ）を抽出する。そして、その抽出した交流トラヒック帯域ｔｊを用いて、線形計画法による計算式における、変数（交流トラヒック帯域ｔｊ）の数と、制約条件式の数とを削減し、線形計画法による計算時間を短縮して、経路変更後の各リンクの帯域変動量の上限値を計算するものである。第２の実施形態は、第１の実施形態の線形計画法による計算処理に比べ、計算速度が低下しても計算精度を向上させることを目的に、計算精度を上げるための処理を所定回数繰り返し行った上で、経路変更後の各リンクの帯域変動量の上限値を計算するものである。この計算精度を上げるための処理は、第１の実施形態においては、計算処理の対象外とした変数（交流トラヒック帯域ｔｊ）および制約条件式のうちの一部を、新たに計算処理の対象に加えることで、計算制度を向上させる。また、この計算精度を上げるため繰り返される処理回数は、高速化レベルｋとして入力される。そして、第３の実施形態は、従来技術における線形計画法による計算処理に比べ、計算精度を低下させないように、変数（交流トラヒック帯域ｔｊ）の数および制約条件式の数を削減し、経路変更後の各リンクの帯域変動量の上限値を計算するものである。
【００３５】
≪第１の実施形態≫
まず、本発明の第１の実施形態に係るリンク帯域変動量上限計算装置１（１ａ）について説明する。
【００３６】
（処理概要）
第１の実施形態に係るリンク帯域変動量上限計算装置１（１ａ）は、従来技術において用いた（式１）〜(式３)の線形計画法による計算式における、変数（交流トラヒック帯域ｔｊ）の数と、制約条件式の数を削減した上で、線形計画法による計算処理を行うものである。以下に示す具体例を用いて処理概要を説明する。
【００３７】
【数２】
0005325167.tif 000004
【００３８】
この〔数２〕に示す線形計画法による計算式において、（式１）は、各リンクの帯域変動量の上限値を求めるための目的関数ｓを表わす。ここでは、経路変更後の交流トラヒック経路行列３００と経路変更前の交流トラヒック経路行列２００とを比較することにより、経路が変更された交流トラヒックの交流トラヒック帯域ｔｊ（つまり、
0005325167.tif 000005
となる交流トラヒック帯域ｔｊ）が、ｔ０とｔ１であるものとしている。また、（式２）および（式３）は、（式１）を計算する際の制約条件式である。（式２）は、リンク毎の等号条件式で表わすことができ、その具体例を、等号条件式（２−ａ）,（２−ｂ），（２−ｃ），（２−ｄ）であるとする。
【００３９】
本発明の第１の実施形態に係るリンク帯域変動量上限計算装置１（１ａ）は、（式１）に用いられる交流トラヒック帯域ｔ０，ｔ１を抽出する。そして、リンク帯域変動量上限計算装置１（１ａ）は、等号条件式（２−ａ）〜（２−ｄ）の中から、抽出した交流トラヒック帯域ｔ０，ｔ１を含む等号条件式（２−ａ），（２−ｂ）を選択し、この２つの式の集合を制約条件式（式２−１）とする（後記する〔数３〕参照）。
【００４０】
次に、リンク帯域変動量上限計算装置１（１ａ）は、この選択した等号条件式（２−ａ），（２−ｂ）において用いられている交流トラヒック帯域ｔ０，ｔ１，ｔ３，ｔ４を、制約条件式（式２−１）に用いられる変数の集合（Ｖ−１）として抽出する。
そして、リンク帯域変動量上限計算装置１（１ａ）は、この変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔ０，ｔ１，ｔ３，ｔ４を変数として用いる（式１）を、目的関数（式１−１）として生成する（後記する〔数３〕参照）。
【００４１】
このようにして生成した、以下の〔数３〕に示す、目的関数（式１−１）、制約条件式（式２−１）および制約条件式（式３）を用いてリンク帯域変動量上限計算装置１（１ａ）は、線形計画法による計算処理を行う。
【００４２】
【数３】
0005325167.tif 000006
【００４３】
この〔数３〕に示す線形計画法による計算式は、〔数２〕に示した従来の線形計画法による計算式と比べ、変数となる交流トラヒック帯域ｔｊの数がｔ０〜ｔ５までの６個であったものを、ｔ０，ｔ１，ｔ３，ｔ４の４個に削減し、制約条件式（式２）を４つの等号条件式から２つの等号条件式（式２−１）に削減したものである。したがって、本発明の第１の実施形態に係るリンク帯域変動量上限計算装置１（１ａ）は、従来技術に比べ、変数の数と制約条件式の数を減らすことができ、処理時間の短縮を図ることができる。
【００４４】
（第１の実施形態におけるリンク帯域変動量上限計算装置の構成）
次に、本発明の第１の実施形態に係るリンク帯域変動量上限計算装置１（１ａ）の構成を説明する。
図５は、本発明の第１の実施形態に係るリンク帯域変動量上限計算装置１（１ａ）の構成例を示す機能ブロック図である。図５に示すように、リンク帯域変動量上限計算装置１ａは、入出力部１０と、処理部２０と、記憶部３０とを含んで構成される。
【００４５】
入出力部１０は、例えば、ネットワークに設けられたネットワーク管理装置（不図示）から、リンク帯域ベクトル１００（図２参照）、交流トラヒック経路行列２００（図４参照）、および経路変更後交流トラヒック経路行列３００、といった対象となるネットワークのトラヒックに関する情報を取得する。ここで、経路変更後交流トラヒック経路行列３００は、ネットワーク設計者が、ネットワークの点検や、あるノードやリンクに障害が発生したと想定した場合に、使用不可とするノードやリンクを経由させずに設計した経路変更後の交流トラヒックの経路を表わす。
【００４６】
なお、交流トラヒック経路行列２００は、ネットワーク内の各ノードと各リンクとの接続関係を示すトポロジ情報を用いて、例えば、ＯＳＰＦ（Open Shortest Path First）であれば、ダイクストラ法を用いて算出される。また、経路変更後交流トラヒック経路行列３００も、トポロジ情報と、ノードやリンクの障害発生等の障害発生箇所情報とに基づき、障害発生後の迂回経路を示す経路変更後交流トラヒック行列３００として、ダイクストラ法等を用いて算出することができる。これらの情報がネットワーク管理装置（不図示）により算出され、リンク帯域変動量上限計算装置１に入力される。
【００４７】
また、入出力部１０は、処理部２０が生成した、後記するリンク帯域変動量上限ベクトル１０００を出力する。なお、この入出力部１０は、入出力インタフェースや通信インタフェース等で構成される。
【００４８】
処理部２０は、リンク帯域変動量上限計算装置１ａの全体の制御を司り、情報収集部２１と、制約条件選択部２２と、変数選択部２３と、リンク帯域変動量上限ベクトル計算部２８と、情報出力部２９とを備える。なお、この処理部２０および入出力部１０は、例えば、リンク帯域変動量上限計算装置１（１ａ）の記憶部３０に格納されたプログラムを、ＣＰＵ（Central Processing Unit）がＲＡＭ（Random Access Memory）に展開し実行することで実現される。
【００４９】
情報収集部２１は、入出力部１０を介して、各リンクの帯域や、交流トラヒックの経路に関する情報を取得し、リンク帯域ベクトル１００、交流トラヒック経路行列２００、および経路変更後交流トラヒック経路行列３００として、記憶部３０に記憶させる。
【００５０】
制約条件選択部２２は、リンク帯域変動量上限ベクトル計算部２８が用いる、〔数１〕において示した線形計画法による計算式のうち制約条件式（式２）を示すリンク毎の等号条件式の中から、計算に用いる等号条件式を選択する処理を行う。
【００５１】
具体的には、制約条件選択部２２は、記憶部３０に記憶されたリンク帯域ベクトル１００および経路変更前の交流トラヒック経路行列２００を用いて、リンク帯域変動量上限ベクトル計算部２８が用いる線形計画法による計算式のうち制約条件式（式２）を示すリンク毎の等号条件式を生成し、記憶部３０内の制約条件情報４００に記憶する。また、制約条件選択部２２は、記憶部３０に記憶された交流トラヒック経路行列２００および経路変更後交流トラヒック経路行列３００を用いて、線形計画法による計算式の目的関数（式１）において、
0005325167.tif 000007
となる１つ以上の交流トラヒック帯域ｔｊ、つまり、交流トラヒックの経路変更前と経路変更後において経路の変更がある１つ以上の交流トラヒックの交流トラヒック帯域ｔｊを抽出する。そして、制約条件選択部２２は、記憶部３０内の制約条件情報４００に記憶した制約条件式（式２）を示すリンク毎の等号条件式の中から、抽出した１以上の交流トラヒック帯域ｔｊを含む等号条件式の集合を制約条件式（式２−１）として選択し、制約条件情報４００に記憶する。
【００５２】
変数選択部２３は、制約条件選択部２２が選択した制約条件式（式２−１）の各等号条件式で用いられる交流トラヒック帯域ｔｊを、制約条件式（式２−１）に用いられる変数の集合（Ｖ−１）として選択し、記憶部３０内の変数情報５００に記憶する。
【００５３】
リンク帯域変動量上限ベクトル計算部２８は、経路変更後におけるリンク毎の帯域変動量の上限値を、線形計画法による計算式を用いて計算する。
具体的には、リンク帯域変動量上限ベクトル計算部２８は、変数選択部２３が選択した変数の集合（Ｖ−１）に含まれる各交流トラヒック帯域ｔｊを抽出し、その抽出した交流トラヒック帯域ｔｊを変数として用いる目的関数（式１）を、目的関数（式１−１）として生成する。そして、リンク帯域変動量上限ベクトル計算部２８は、生成した目的関数（式１−１）、制約条件選択部２２が選択した制約条件式（式２−１）および制約条件式（式３）を用いて線形計画法による計算式を解くことにより、リンク帯域変動量上限ベクトル１０００を生成する。そして、リンク帯域変動量上限ベクトル計算部２８は、生成したリンク帯域変動量上限ベクトル１０００を記憶部３０に記憶する。
【００５４】
情報出力部２９は、記憶部３０に記憶されたリンク帯域変動量上限ベクトル１０００を、入出力部１０を介して、ネットワーク管理装置（不図示）等に出力する。
【００５５】
次に、記憶部３０は、ハードディスクやフラッシュメモリ等で構成される記憶手段であり、リンク帯域ベクトル１００、交流トラヒック経路行列２００、経路変更後交流トラヒック経路行列３００、制約条件情報４００、変数情報５００、およびリンク帯域変動量上限ベクトル１０００が記憶される。
【００５６】
制約条件情報４００には、制約条件選択部２２が生成した、線形計画法による計算式の制約条件式（式２）を示すリンク毎の等号条件式が記憶される。また、制約条件選択部２２が、制約条件式（式２）を示すリング毎の等号条件式の中から選択した等号条件式の集合である制約条件式（式２−１）が記憶される。
【００５７】
変数情報５００には、制約条件式（式２−１）に用いられる変数（交流トラヒック帯域ｔｊ）の集合（Ｖ−１）が記憶される。
【００５８】
（第１の実施形態のリンク帯域変動量上限計算処理）
次に、リンク帯域変動量上限計算装置１ａのリンク帯域変動量上限計算処理の流れを説明する。図６は、本発明の第１の実施形態に係るリンク帯域変動量上限計算処理の流れを示すフローチャートである。
【００５９】
まず、リンク帯域変動量上限計算装置１ａの情報収集部２１は、入出力部１０を介して、リンク帯域ベクトル１００、交流トラヒック経路行列２００、および経路変更後交流トラヒック経路行列３００の情報を取得し（ステップＳ１０１）、記憶部３０に記憶する。
【００６０】
次に、制約条件選択部２２は、制約条件式（式２−１）を選択する処理を行う(ステップＳ１０２)。
具体的には、制約条件選択部２２は、記憶部３０に記憶されたリンク帯域ベクトル１００および経路変更前の交流トラヒック経路行列２００を用いて、線形計画法による計算式の制約条件式（式２）を示すリンク毎の等号条件式を生成し、記憶部３０内の制約条件情報４００に記憶する。続いて、制約条件選択部２２は、記憶部３０に記憶された交流トラヒック経路行列２００および経路変更後交流トラヒック経路行列３００を用いて、線形計画法による計算式の目的関数（式１）において、
0005325167.tif 000008
となる１つ以上の交流トラヒック帯域ｔｊ、つまり、交流トラヒックの経路変更前と経路変更後において経路の変更がある１つ以上の交流トラヒックの交流トラヒック帯域ｔｊを抽出する。そして、制約条件選択部２２は、記憶部３０内の制約条件情報４００に記憶した制約条件式（式２）を示すリンク毎の等号条件式の中から、抽出した１以上の交流トラヒック帯域ｔｊを含む等号条件式の集合を制約条件式（式２−１）として選択し、制約条件情報４００に記憶する。
【００６１】
続いて、変数選択部２３は、ステップＳ１０２において、制約条件選択部２２が選択した制約条件式（式２−１）の各等号条件式で用いられる交流トラヒック帯域ｔｊを、制約条件式（式２−１）に用いられる変数の集合（Ｖ−１）として選択し（ステップＳ１０３）、記憶部３０内の変数情報５００に記憶する。
【００６２】
次に、リンク帯域変動量上限ベクトル計算部２８は、変数の集合（Ｖ−１）に含まれる交流トラヒック帯域ｔｊを変数として用いる目的関数（式１）を、目的関数（式１−１）として生成する（ステップＳ１０４）。そして、リンク帯域変動量上限ベクトル計算部２８は、生成した目的関数（式１−１）、ステップＳ１０２で選択した制約条件式（式２−１）および制約条件式（式３）による線形計画法による計算式を、記憶部３０に記憶されたリンク帯域ベクトル１００、交流トラヒック経路行列２００および経路変更後交流トラヒック経路行列３００を用いて解くことにより、リンク帯域変動量上限ベクトル１０００を生成する（ステップＳ１０５）。そして、リンク帯域変動量上限ベクトル計算部２８は、生成したリンク帯域変動量上限ベクトル１０００を記憶部３０に記憶する。
【００６３】
次に、情報出力部２９は、記憶部３０に記憶されたリンク帯域変動量上限ベクトル１０００を、入出力部１０を介して出力する（ステップＳ１０６）。
【００６４】
このようにすることで、本発明の第１の実施形態に係るリンク帯域変動量上限計算装置１（１ａ）によれば、線形計画法による計算式で用いる変数（交流トラヒック帯域ｔｊ）の数、制約条件式（式２）における等号条件式の数を低減させた上で、線形計画法のよる計算を行うため、計算時間が長大になることを防ぐことができる。つまり、本リンク帯域変動量上限計算装置１（１ａ）の計算処理を高速化することができる。
そして、本リンク帯域変動量上限計算装置１（１ａ）により計算された各リンクの帯域変動量の上限値は、経路変更後に必要な各リンクの帯域増設量の最小値となるため、リンク帯域設計において、無駄となる帯域を抑えることができる。
【００６５】
≪第２の実施形態≫
次に、本発明の第２の実施形態に係るリンク帯域変動量上限計算装置１（１ｂ）について説明する。
【００６６】
（処理概要）
まず、本発明の第２の実施形態の処理概要について説明する。
本発明の第２の実施形態に係るリンク帯域変動量上限計算装置１（１ｂ）は、以下に示す計算精度を上げるための処理を所定回数繰り返し行うことで、第１の実施形態に係るリンク帯域変動量の上限計算処理に比べ、変数（交流トラヒック帯域ｔｊ）の数および制約条件式（式２）に用いる等号条件式の数を低減させ過ぎずに（つまり、第１の実施形態に係る線形計画法の計算処理よりも、変数の数と等号条件式の数を増加させて）、経路変更後の各リンクの帯域変動量の上限値を計算するものである。
【００６７】
具体例を用いて説明すると、第２の実施形態に係るリンク帯域変動量上限計算装置１（１ｂ）は、〔数３〕で示した制約条件式（式２−１）に用いられる変数の集合（Ｖ−１）である交流トラヒック帯域ｔ０，ｔ１，ｔ３，ｔ４を含む等号条件式を、記憶部３０内の制約条件情報４００に記憶された制約条件式（式２）を示すリンク毎の等号条件式の中から選択する。その結果、等号条件式（２−ａ），（２−ｂ），（２−ｄ）が選択され、この３つの式の集合を制約条件式（２−２）とする（後記する〔数４〕参照）。
【００６８】
次に、リンク帯域変動量上限計算装置１（１ｂ）は、この選択した等号条件式（２−ａ），（２−ｂ），（２−ｄ）において用いられている交流トラヒック帯域ｔ０，ｔ１，ｔ２，ｔ３，ｔ４を、制約条件式（式２−２）に用いられる変数の集合（Ｖ−２）として抽出する。
そして、リンク帯域変動量上限計算装置１（１ｂ）は、この変数の集合（Ｖ−２）に含まれる交流トラヒック帯域ｔ０，ｔ１，ｔ２，ｔ３，ｔ４を変数として用いる（式１）を、目的関数（式１−２）として生成する（後記する〔数４〕参照）。
【００６９】
このようにして生成した、以下の〔数４〕に示す、目的関数（式１−２）、制約条件式（式２−２）および制約条件式（式３）を用いてリンク帯域変動量上限計算装置１（１ｂ）は、線形計画法による計算処理を行う。
【００７０】
【数４】
0005325167.tif 000009
【００７１】
そして、第２の実施形態に係るリンク帯域変動量上限計算装置１（１ｂ）は、この変数の数および等号条件式の数を増加させ、計算精度を上げるための処理を、入力された目標高速化レベル「ｎ」まで繰り返し行う。なお「ｎ」は正の整数であり、計算精度を上げるために、変数の数を増加させる処理が繰り返される回数（ｎ回）を表す。
このようにすることで、第２の実施形態に係るリンク帯域変動量上限計算装置１（１ｂ）は、計算速度を従来技術よりも向上させつつ、計算精度も考慮した上で、目標となる高速化レベルを設定し、経路変更後の各リンクの帯域変動量の上限値を計算することができる。
【００７２】
（第２の実施形態におけるリンク帯域変動量上限計算装置の構成）
次に、本発明の第２の実施形態に係るリンク帯域変動量上限計算装置１（１ｂ）の構成を説明する。
図７は、本発明の第２の実施形態に係るリンク帯域変動量上限計算装置１（１ｂ）の構成例を示す機能ブロック図である。図７に示すように、リンク帯域変動量上限計算装置１ｂは、図５に示したリンク帯域変動量上限計算装置１ａと同様に、入出力部１０と、処理部２０と、記憶部３０とを含んで構成される。なお、第２の実施形態においては、図５に示すリンク帯域変動量上限計算装置１ａと同様の機能を備える構成は、同一の符号を付し説明を省略する。
【００７３】
第２の実施形態における入出力部１０は、例えば、ネットワークに設けられたネットワーク管理装置（不図示）から、リンク帯域ベクトル１００、交流トラヒック経路行列２００、経路変更後交流トラヒック経路行列３００、および目標高速化レベル「ｎ」に関する情報を取得する。そして、情報収集部２１が、これらの情報を記憶部３０に記憶する。なお、目標高速化レベル「ｎ」に関する情報は、情報収集部２１により、記憶部３０内の後記する目標高速化レベル情報６００に記憶される。
【００７４】
ここで、目標高速化レベル「ｎ」は、高速化レベル「ｋ（正の整数）」の目標値である。そしてこの高速化レベル「ｋ」において高速化レベル「１」の場合は、本第２の実施形態に係るリンク帯域変動量上限計算装置１（１ｂ）は、第１の実施形態に係る処理と同様の処理を行い、変数（交流トラヒック帯域ｔｊ）の数と、制約条件式（式２）における等号条件式の数とを最も低減させる。その結果、計算処理速度が最も速くなるものである。また、高速化レベル「ｋ」の数値が上がるほど、変数（交流トラヒック帯域ｔｊ）の数および等号条件式の数が増えることになり、その結果、計算速度よりも精度の向上を優先させた処理を行うことができる。
【００７５】
また、本発明の第２の実施形態における処理部２０は、図５に示すリンク帯域変動量上限計算装置１ａの処理部２０の構成に加え、高速化レベル処理部２４と、高速化レベル判定部２５とを備えている。
【００７６】
高速化レベル処理部２４は、記憶部３０内の後記する高速化レベル情報７００に記憶される高速化レベル「ｋ」を「０」に初期化する。そして、高速化レベル処理部２４は、制約条件選択部２２および変数選択部２３による処理（計算精度を上げるために変数の数および等号条件式の数を増加させる処理）を繰り返す度に、高速化レベル情報７００に記憶された高速化レベル「ｋ」に「＋１」を加え更新する。
【００７７】
高速化レベル判定部２５は、高速化レベル情報７００に記憶される高速化レベル「ｋ」と、目標高速化レベル情報６００に記憶される目標高速化レベル「ｎ」の値が一致するか否かを判定する。
【００７８】
また、第２の実施形態における制約条件選択部２２は、高速化レベル「ｋ」の値が「１」であるときは、第１の実施形態における制約条件選択部２２の処理と同様の処理を行う。そして、高速化レベル「ｋ」の値が「２」以上の値であるとき、制約条件選択部２２は、制約条件情報４００に記憶された、制約条件式（式２）を示すリンク毎の等号条件式の中から、変数選択部２３により選択された変数の集合（Ｖ−（ｋ−１））で用いられる交流トラヒック帯域ｔｊを含む等号条件式を、制約条件式（式２−ｋ）として選択し、制約条件情報４００に記憶する。
【００７９】
第２の実施形態における変数選択部２３は、制約条件選択部２２が選択した高速化レベル「ｋ」における制約条件式（式２−ｋ）の各等号条件式で用いられる交流トラヒック帯域ｔｊを、制約条件式（式２−ｋ）に用いられる変数の集合（Ｖ−ｋ）として選択し、記憶部３０内の変数情報５００に記憶する。
【００８０】
第２の実施形態におけるリンク帯域変動量上限ベクトル計算部２８は、高速化レベル判定部２５が、高速化レベル「ｋ」と目標高速化レベル「ｎ」の値が一致すると判定した場合に、変数選択部２３が選択した変数の集合（Ｖ−ｎ）に含まれる交流トラヒック帯域ｔｊを変数として用いる目的関数（式１）を、目的関数（式１−ｎ）として生成する。そして、リンク帯域変動量上限ベクトル計算部２８は、生成した目的関数（式１−ｎ）、制約条件選択部２２が選択した制約条件式（式２−ｎ）および制約条件式（式３）による線形計画法による計算式を解くことにより、リンク帯域変動量上限ベクトル１０００を生成する。
【００８１】
また、第２の実施形態における記憶部３０には、第１の実施形態における記憶部３０の構成に加えて、目標高速化レベル情報６００および高速化レベル情報７００が記憶される。目標高速化レベル情報６００には、情報収集部２１が入出力部１０を介して取得した目標高速化レベル「ｎ」の情報が記憶される。また、高速化レベル情報７００には、高速化レベル処理部２４により設定や更新がされる高速化レベル「ｋ」が記憶される。
【００８２】
（第２の実施形態のリンク帯域変動量上限計算処理）
次に、リンク帯域変動量上限計算装置１ｂのリンク帯域変動量上限計算処理の流れを説明する。図８は、本発明の第２の実施形態に係るリンク帯域変動量上限計算処理の流れを示すフローチャートである。
【００８３】
まず、リンク帯域変動量上限計算装置１ｂの高速化レベル処理部２４は、記憶部３０内の高速化レベル情報７００に記憶される高速化レベル「ｋ」を「０」に初期化する（ステップＳ２０１）。
【００８４】
次に、情報収集部２１は、入出力部１０を介して、リンク帯域ベクトル１００、交流トラヒック経路行列２００、経路変更後交流トラヒック経路行列３００、および目標高速化レベル「ｎ」の情報を取得し（ステップＳ２０２）、記憶部３０に記憶する。なお、情報収集部２１により、高速化レベル「ｎ」が記憶部３０内の目標高速化レベル情報６００に記憶される。
【００８５】
以下、ステップＳ２０３〜Ｓ２０６までの処理が、後記するように、目標高速化レベルｎに達するまで繰り返されるが、ステップＳ２０３〜Ｓ２０６の１回目の処理が、高速化レベル「１」における処理であり、ステップＳ２０３〜Ｓ２０６の２回目の処理が、高速化レベル「２」における処理であり、同様に、ステップＳ２０３〜Ｓ２０６のｋ回目の処理が、高速化レベル「ｋ」における処理である。
【００８６】
〔高速化レベル「１」の処理〕
まず、高速化レベル処理部２４は、記憶部３０内の高速化レベル情報７００に記憶される高速化レベル「ｋ」に「＋１」を加える（ステップＳ２０３）。よって、ここでは、高速化レベル情報７００に記憶された高速化レベル「０」に「＋１」が加えられ、高速化レベル「１」が設定される。
【００８７】
次に、制約条件選択部２２は、図６のステップＳ１０２と同様の制約条件式（式２−１）の選択処理を行う（ステップＳ２０４）。具体的には、制約条件選択部２２は、記憶部３０に記憶されたリンク帯域ベクトル１００および経路変更前の交流トラヒック経路行列２００を用いて、線形計画法による計算式の制約条件式（式２）を示すリンク毎の等号条件式を生成し、記憶部３０内の制約条件情報４００に記憶する。そして、制約条件選択部２２は、線形計画法による計算式の目的関数（式１）において、
0005325167.tif 000010
となる１つ以上の交流トラヒック帯域ｔｊを抽出する。続いて、制約条件選択部２２は、記憶部３０内の制約条件情報４００に記憶した制約条件式（式２）を示すリンク毎の等号条件式の中から、抽出した１以上の交流トラヒック帯域ｔｊを含む等号条件式の集合を制約条件式（式２−１）として選択し、制約条件情報４００に記憶する。
【００８８】
そして、変数選択部２３は、ステップＳ２０４において、制約条件選択部２２が選択した制約条件式（式２−１）の各等号条件式で用いられる交流トラヒック帯域ｔｊを、制約条件式（式２−１）に用いられる変数の集合（Ｖ−１）として選択し（ステップＳ２０５）、記憶部３０内の変数情報５００に記憶する。
【００８９】
続いて、高速化レベル判定部２５は、高速化レベル情報７００に記憶されている高速化レベル「ｋ」と、目標高速化レベル情報６００に記憶されている目標高速化レベル「ｎ」の値が一致しているか否かを判定する（ステップＳ２０６）。よって、ここでは、高速化レベル「１」と目標高速化レベル「ｎ」とが一致しているか否かが判定される。
【００９０】
ここで、高速化レベル判定部２５が、高速化レベル「１」と目標高速化レベル「ｎ」とが一致すると判定した場合には（ステップＳ２０６→Ｙｅｓ）、ステップＳ２０７〜Ｓ２０９の処理に進む。このステップＳ２０７〜Ｓ２０９の処理は、図６に示したステップＳ１０４〜Ｓ１０６と同様の処理となる。つまり、リンク帯域変動量上限ベクトル計算部２８は、ステップＳ２０７で、変数の集合（Ｖ−１）を用いて目的関数（式１−１）を生成した上で、その目的関数（式１−１）と、ステップＳ２０４で選択した制約条件式（式２−１）と、制約条件式（式３）を用いて線形計画法のよる計算式を解き、リンク帯域変動量上限ベクトル１０００を生成し（ステップＳ２０８）、情報出力部２９が入出力部１０を介して出力する（ステップＳ２０９）。
このようにすることで、高速化レベル「１」のリンク帯域変動量上限ベクトル１０００を生成することができる。
【００９１】
一方、ステップＳ２０６において、高速化レベル「１」と目標高速化レベル「ｎ」とが一致しないと判定された場合には（ステップＳ２０６→Ｎｏ）、ステップＳ２０３に戻る。
【００９２】
〔高速化レベル「２」の処理〕
次に、ステップＳ２０３において、高速化レベル処理部２４は、記憶部３０内の高速化レベル情報７００に記憶される高速化レベル「ｋ」に「＋１」を加える。よって、ここでは、高速化レベル情報７００に記憶された高速化レベル「１」に「＋１」が加えられ、高速化レベル「２」が設定される。
【００９３】
続いて、制約条件選択部２２は、制約条件情報４００に記憶された、制約条件式（式２）を示すリンク毎の等号条件式の中から、ステップＳ２０５で変数選択部２３により選択された変数の集合（Ｖ−１）で用いられる交流トラヒック帯域ｔｊを含む等号条件式を、制約条件式（式２−２）として選択し（ステップＳ２０４）、制約条件情報４００に記憶する。
【００９４】
そして、変数選択部２３は、ステップＳ２０４において制約条件選択部２２が選択した制約条件式（式２−２）の各等号条件式で用いられる交流トラヒック帯域ｔｊを、制約条件式（式２−２）に用いられる変数の集合（Ｖ−２）として選択し（ステップＳ２０５）、記憶部３０内の変数情報５００に記憶する。
【００９５】
続いて、高速化レベル判定部２５は、高速化レベル情報７００に記憶されている高速化レベル「２」と、目標高速化レベル情報６００に記憶されている目標高速化レベル「ｎ」の値が一致しているか否かを判定する（ステップＳ２０６）。
【００９６】
ここで、高速化レベル判定部２５が、高速化レベル「２」と目標高速化レベル「ｎ」とが一致すると判定した場合には（ステップＳ２０６→Ｙｅｓ）、次のステップＳ２０７に進む。
【００９７】
ステップＳ２０７において、リンク帯域変動量上限ベクトル計算部２８は、変数の集合（Ｖ−２）に含まれる交流トラヒック帯域ｔｊを変数として用いる目的関数（式１）を、目的関数（式１−２）として生成する。そして、リンク帯域変動量上限ベクトル計算部２８は、生成した目的関数（式１−２）、ステップＳ２０４で選択した制約条件式（式２−２）および制約条件式（式３）による線形計画法による計算式を解くことにより、リンク帯域変動量上限ベクトル１０００を生成し（ステップＳ２０８）、情報出力部２９が入出力部１０を介して出力する（ステップＳ２０９）。
このようにすることで、高速化レベル「２」のリンク帯域変動量上限ベクトル１０００を生成することができる。
【００９８】
一方、ステップＳ２０６において、高速化レベル「２」と目標高速化レベル「ｎ」とが一致しないと判定された場合には（ステップＳ２０６→Ｎｏ）、ステップＳ２０３に戻る。
そして、高速化レベル判定部２５が、高速化レベル情報７００に記憶されている高速化レベル「ｋ」の値と、目標高速化レベル情報６００に記憶されている目標高速化レベル「ｎ」の値が一致するとステップＳ２０６において判定するまで、ステップＳ２０３〜Ｓ２０５の処理を繰り返す。そして、高速化レベル判定部２５が、高速化レベル「ｋ」が目標高速化レベル「ｎ」と一致すると判定すると、リンク帯域変動量上限ベクトル計算部２８が、変数の集合（Ｖ−ｎ）に含まれる交流トラヒック帯域ｔｊを変数として用いる目的関数（式１）を、目的関数（式１−ｎ）として生成する。そして、リンク帯域変動量上限ベクトル計算部２８は、生成した目的関数（式１−ｎ）、ステップＳ２０４で選択した制約条件式（式２−ｎ）および制約条件式（式３）による線形計画法による計算式を解くことにより、リンク帯域変動量上限ベクトル１０００を生成し（ステップＳ２０８）、情報出力部２９が入出力部１０を介して出力する（ステップＳ２０９）。このようにすることで、目標高速化レベル「ｎ」のリンク帯域変動量上限ベクトル１０００を生成することができる。
【００９９】
よって、本発明の第２の実施形態に係るリンク帯域変動量上限計算装置１ｂによれば、目標高速化レベル「ｎ」を設定した上で、線形計画法による計算式で用いる変数（交流トラヒック帯域ｔｊ）の数、制約条件式（式２）における等号条件式の数を低減させて、線形計画法による計算処理を行うことができる。
なお、目標高速化レベル「ｎ」を「１」に設定した場合は、第１の実施形態の同様の処理を行うことになり、高速化レベル「２」以降に比べ、変数の数、制約条件の数を最も減らし処理時間を低減できる。一方、高速化レベル「ｋ」を上げるごとに、変数の数および等号条件式の数が増えることになり、処理速度は低下するが、計算精度を向上させることができる。
【０１００】
≪第３の実施形態≫
次に、本発明の第３の実施形態に係るリンク帯域変動量上限計算装置１（１ｃ）について説明する。
【０１０１】
（処理概要）
まず、第３の実施形態の処理概要について説明する。
本発明の第３の実施形態に係るリンク帯域変動量上限計算装置１（１ｃ）は、第２の実施形態に係るリンク帯域変動量上限計算装置１（１ｂ）と同様の計算精度を上げるための処理を行う。第３の実施形態と第２の実施形態との違いは、第２の実施形態においては、入力された目標高速化レベル「ｎ」と、高速化レベル「ｋ」とが一致するまで処理を行うようにしている。これに対し、第３の実施形態に係るリンク帯域変動量上限計算装置１（１ｃ）は、変数選択部２３が選択した変数の集合（Ｖ−ｋ）における変数（交流トラヒック帯域ｔｊ）の数をＮ（Ｖ−ｋ）として計算し、この変数の数を、１つ前の高速化レベル「ｋ−１」での変数の数Ｎ（Ｖ−（ｋ−１））と比較し、変数の数が一致するまで処理を行う。つまり、線形計画法による計算式を用いる場合に、変数の数が変わらなければ（変数の数が増加しなければ）、本実施形態における計算精度を上げるための処理を繰り返しても、計算精度は上がらなくなる。そのため、本第３の実施形態に係るリンク帯域変動量上限計算装置１（１ｃ）は、１つ前の高速化レベルでの変数（交流トラヒック帯域ｔｊ）の数と、処理中の高速化レベルでの変数（交流トラヒック帯域ｔｊ）の数とが同じになった場合は、その高速化レベルで処理を終了し、線形計画法による計算処理を行う。
【０１０２】
このようにすることで、第３の実施形態に係るリンク帯域変動量上限計算装置１（１ｃ）は、従来のリンク帯域変動量上限計算装置に比べ、変数の数および制約条件式の数を低減させ計算速度を向上させた上で、さらに、計算精度を低下させることなく、経路変更後の各リンクの帯域変動量の上限値を計算することができる。
【０１０３】
（第３の実施形態におけるリンク帯域変動量上限計算処理の構成）
次に、本発明の第３の実施形態に係るリンク帯域変動量上限計算装置１（１ｃ）の構成を説明する。
図９は、本発明の第３の実施形態に係るリンク帯域変動量上限計算装置１（１ｃ）の構成例を示す機能ブロック図である。図９に示すように、リンク帯域変動量上限計算装置１ｃは、図５および図７に示したリンク帯域変動量上限計算装置１ａ，１ｂと同様に、入出力部１０と、処理部２０と、記憶部３０とを含んで構成される。なお、第３の実施形態においては、図５および図７に示すリンク帯域変動量上限計算装置１ａ，１ｂと同様の機能を備える構成は、同一の符号を付し説明を省略する。
【０１０４】
第３の実施形態における入出力部１０は、例えば、ネットワークに設けられたネットワーク管理装置（不図示）から、第１の実施形態における入出力部１０と同様に、リンク帯域ベクトル１００、交流トラヒック経路行列２００、および経路変更後交流トラヒック経路行列３００に関する情報を取得する。そして、情報収集部２１が、これらの情報を記憶部３０に記憶する。
【０１０５】
また、本発明の第３の実施形態における処理部２０は、図７に示すリンク帯域変動量上限計算装置１ｂの処理部２０の構成と比べ、高速化レベル判定部２５を備えていない。その一方で、変数数出力部２６と、変数数判定部２７とを備えている。
【０１０６】
変数数出力部２６は、記憶部３０に記憶された交流トラヒック経路行列２００の情報から、線形計画法による計算式の目的関数（式１）に用いられる変数（交流トラヒック帯域ｔｊ）の数を計算し、記憶部３０内の後記する変数数情報８００に、その変数の数をＮ（Ｖ−０）として記憶する。
また、変数数出力部２６は、高速化レベル処理部２４により、高速化レベルの値が「ｋ」と設定された場合に、制約条件選択部２２が選択した制約条件式（式２−ｋ）に含まれる変数（交流トラヒック帯域ｔｊ）の数を計算し、記憶部３０内の後記する変数数情報８００に、その変数の数をＮ（Ｖ−ｋ）として記憶する。
【０１０７】
変数数判定部２７は、変数数情報８００に記憶された変数（交流トラヒック帯域ｔｊ）の数であるＮ（Ｖ−ｋ）と、その１つ前の高速化レベル「ｋ−１」における変数の数であるＮ（Ｖ−（ｋ−１））とが一致するか否かを判定する。つまり、高速化レベル「ｋ」の数値が「＋１」された場合に、線形計画法による計算式における変数（交流トラヒック帯域ｔｊ）の数が増えるか否かを判定する。変数数判定部２７が、変数の数Ｎ（Ｖ−ｋ）とＮ（Ｖ−（ｋ−１））とが一致しないと判定した場合には、その情報を高速化レベル処理部２４に出力し、高速化レベル「ｋ」に「＋１」を加えて処理を続けさせる。一方、変数数判定部２７が、Ｎ（Ｖ−ｋ）とＮ（Ｖ−（ｋ−１））とが一致すると判定した場合には、さらに高速化レベル「ｋ」の値を増やしても、変数の数が変わらず、精度の向上がなされないため処理を終了し、その高速化レベル「ｋ」の情報を、リンク帯域変動量上限ベクトル計算部２８に出力する。
【０１０８】
第３の実施形態におけるリンク帯域変動量上限ベクトル計算部２８は、変数数判定部２７が、変数の数Ｎ（Ｖ−ｋ）とＮ（Ｖ−（ｋ−１））とが一致すると判定した場合に、変数選択部２３が選択した変数の集合（Ｖ−ｋ）に含まれる交流トラヒック帯域ｔｊを変数として用いる目的関数（式１）を、目的関数（式１−ｋ）として生成する。そして、リンク帯域変動量上限ベクトル計算部２８は、生成した目的関数（式１−ｋ）、制約条件選択部２２が選択した制約条件式（式２−ｋ）および制約条件式（式３）による線形計画法による計算式を解くことにより、リンク帯域変動量上限ベクトル１０００を生成する。
【０１０９】
また、第３の実施形態における記憶部３０は、図７に示すリンク帯域変動量上限計算装置１ｂの構成と比べて、目標高速化レベル情報６００を備えていない。その一方で、変数数情報８００を備えている。
【０１１０】
変数数情報８００には、変数数出力部２６が計算した、目的関数（式１）に用いられる変数（交流トラヒック帯域ｔｊ）の数がＮ（Ｖ−０）として記憶される。また、制約条件選択部２２が選択した制約条件式（式２−ｋ）に含まれ、変数数出力部２６が計算した変数（交流トラヒック帯域ｔｊ）の数がＮ（Ｖ−ｋ）として記憶される。
【０１１１】
（第３の実施形態のリンク帯域変動量上限計算処理）
次に、リンク帯域変動量上限計算装置１ｃのリンク帯域変動量上限計算処理の流れを説明する。図１０は、本発明の第３の実施形態に係るリンク帯域変動量上限計算処理の流れを示すフローチャートである。
【０１１２】
まず、リンク帯域変動量上限計算装置１ｃの高速化レベル処理部２４は、記憶部３０内の高速化レベル情報７００に記憶される高速化レベル「ｋ」を「０」に初期化する（ステップＳ３０１）。
【０１１３】
次に、情報収集部２１は、入出力部１０を介して、リンク帯域ベクトル１００、交流トラヒック経路行列２００、および経路変更後交流トラヒック経路行列３００の情報を取得し（ステップＳ３０２）、記憶部３０に記憶する。
【０１１４】
続いて、変数数出力部２６は、記憶部３０に記憶された交流トラヒック経路行列２００の情報から、線形計画法による計算式の目的関数（式１）に用いられる変数（交流トラヒック帯域ｔｊ）の数を計算し、記憶部３０内の変数数情報８００に、その変数の数をＮ（Ｖ−０）として記憶する（ステップＳ３０３）。
【０１１５】
以下、ステップＳ３０４〜Ｓ３０８までの処理を、後記するように、高速化レベル「ｋ」の値を上げても、変数数情報８００に記憶される変数（交流トラヒック帯域ｔｊ）の数が変わらなくなるまで繰り返す。
【０１１６】
〔高速化レベル「１」の処理〕
まず、高速化レベル処理部２４は、記憶部３０内の高速化レベル情報７００に記憶される高速化レベル「ｋ」に「＋１」を加える（ステップＳ３０４）。よって、ここでは、高速化レベル情報７００に記憶された高速化レベル「０」に「＋１」が加えられ、高速化レベル「１」が設定される。
【０１１７】
次に、制約条件選択部２２は、図６のステップＳ１０２と同様の制約条件式（式２−１）の選択処理を行う（ステップＳ３０５）。具体的には、制約条件選択部２２は、記憶部３０に記憶されたリンク帯域ベクトル１００および経路変更前の交流トラヒック経路行列２００を用いて、線形計画法による計算式の制約条件式（式２）を示すリンク毎の等号条件式を生成し、記憶部３０内の制約条件情報４００に記憶する。そして、制約条件選択部２２は、線形計画法による計算式の目的関数（式１）において、
0005325167.tif 000011
となる１つ以上の交流トラヒック帯域ｔｊを抽出する。続いて、制約条件選択部２２は、記憶部３０内の制約条件情報４００に記憶した制約条件式（式２）を示すリンク毎の等号条件式の中から、抽出した１以上の交流トラヒック帯域ｔｊを含む等号条件式の集合を制約条件式（式２−１）として選択し、制約条件情報４００に記憶する。
【０１１８】
そして、変数選択部２３は、ステップＳ３０５において、制約条件選択部２２が選択した制約条件式（式２−１）の各等号条件式で用いられる交流トラヒック帯域ｔｊを、制約条件式（式２−１）に用いられる変数の集合（Ｖ−１）として選択し（ステップＳ３０６）、記憶部３０内の変数情報５００に記憶する。
【０１１９】
続いて、変数数出力部２６は、制約条件式（式２−１）に用いられる変数の集合（Ｖ−１）の変数（交流トラヒック帯域ｔｊ）の数を計算し、記憶部３０内の変数数情報８００に、その変数の数をＮ（Ｖ−１）として記憶する（ステップＳ３０７）。
【０１２０】
次に、変数数判定部２７は、変数数情報８００に記憶された、変数の集合（Ｖ−ｋ）の変数の数Ｎ（Ｖ−ｋ）と、その１つ前の高速化レベルで選択される変数の集合（Ｖ−（ｋ−１））の変数の数Ｎ（Ｖ−（ｋ−１））とが一致するか否かを判定する（ステップＳ３０８）。よって、ここでは、変数数情報８００に記憶された変数の数であるＮ（Ｖ−１）とＮ（Ｖ−０）とが一致するか否かを、変数数判定部２７が判定する。
【０１２１】
ここで、変数数判定部２７が、Ｎ（Ｖ−１）とＮ（Ｖ−０）とが一致すると判定した場合には（ステップＳ３０８→Ｙｅｓ）、ステップＳ３０９〜Ｓ３１１の処理に進む。このステップＳ３０９〜Ｓ３１１の処理は、図６に示したステップＳ１０４〜Ｓ１０６と同様の処理となる。つまり、リンク帯域変動量上限ベクトル計算部２８は、ステップＳ３０９で、変数の集合（Ｖ−１）を用いて目的関数（式１−１）を生成した上で、その目的関数（式１−１）と、ステップＳ３０５で選択した制約条件式（式２−１）と、制約条件式（式３）を用いて線形計画法のよる計算式を解き、リンク帯域変動量上限ベクトル１０００を生成し（ステップＳ３１０）、情報出力部２９が入出力部１０を介して出力する（ステップＳ３１１）。
【０１２２】
一方、ステップＳ３０８において、変数数判定部２７が、Ｎ（Ｖ−１）とＮ（Ｖ−０）とが一致しないと判定した場合には（ステップＳ３０８→Ｎｏ）、ステップＳ３０４に戻る。
【０１２３】
〔高速化レベル「２」の処理〕
次に、ステップＳ３０４において、高速化レベル処理部２４は、記憶部３０内の高速化レベル情報７００に記憶される高速化レベル「ｋ」に「＋１」を加える。よって、ここでは、高速化レベル情報７００に記憶された高速化レベル「１」に「＋１」が加えられ、高速化レベル「２」が設定される。
【０１２４】
続いて、制約条件選択部２２は、制約条件情報４００に記憶された、制約条件式（式２）を示すリンク毎の等号条件式の中から、ステップＳ３０６で変数選択部２３により選択された変数の集合（Ｖ−１）で用いられる交流トラヒック帯域ｔｊを含む等号条件式を、制約条件式（式２−２）として選択し（ステップＳ３０５）、制約条件情報４００に記憶する。
【０１２５】
そして、変数選択部２３は、ステップＳ３０５において制約条件選択部２２が選択した制約条件式（式２−２）の各等号条件式で用いられる交流トラヒック帯域ｔｊを、制約条件式（式２−２）に用いられる変数の集合（Ｖ−２）として選択し（ステップＳ３０６）、記憶部３０内の変数情報５００に記憶する。
【０１２６】
次に、変数数出力部２６は、制約条件式（式２−２）に用いられる変数の集合（Ｖ−２）の変数（交流トラヒック帯域ｔｊ）の数を計算し、記憶部３０内の変数数情報８００に、その変数の数をＮ（Ｖ−２）として記憶する（ステップＳ３０７）。
【０１２７】
続いて、変数数判定部２７は、変数数情報８００に記憶された変数の数であるＮ（Ｖ−２）とＮ（Ｖ−１）とが一致するか否かを判定する（ステップＳ３０８）。
【０１２８】
ここで、変数数判定部２７が、Ｎ（Ｖ−２）とＮ（Ｖ−１）とが一致すると判定した場合には（ステップＳ３０８→Ｙｅｓ）、次にステップＳ３０９に進む。
【０１２９】
ステップＳ３０９において、リンク帯域変動量上限ベクトル計算部２８は、変数の集合（Ｖ−２）に含まれる交流トラヒック帯域ｔｊを変数として用いる目的関数（式１）を、目的関数（式１−２）として生成する。そして、リンク帯域変動量上限ベクトル計算部２８は、生成した目的関数（式１−２）、ステップＳ３０５で選択した制約条件式（式２−２）および制約条件式（式３）による線形計画法による計算式を解くことにより、リンク帯域変動量上限ベクトル１０００を生成し（ステップＳ３１０）、情報出力部２９が入出力部１０を介して出力する（ステップＳ３１１）。
【０１３０】
一方、ステップＳ３０８において、変数数判定部２７が、Ｎ（Ｖ−２）とＮ（Ｖ−１）とが一致しないと判定された場合には（ステップＳ３０８→Ｎｏ）、ステップＳ３０４に戻る。
【０１３１】
そして、ステップＳ３０８において、変数数判定部２７が、Ｎ（Ｖ−ｋ）とＮ（Ｖ−（ｋ−１））とが一致すると判定するまで、ステップＳ３０４〜Ｓ３０８までの処理を繰り返すことで、リンク帯域変動量上限ベクトル１０００を生成する。
なお、Ｎ（Ｖ−ｋ）とＮ（Ｖ−（ｋ−１））とが一致した後に、さらに高速化レベル「ｋ」の値を上げても、線形計画法による計算式で用いる変数（交流トラヒック帯域ｔｊ）の数、および制約条件式（式２）における等号条件式の数は変わらないため、計算精度は変わらないものとなる。
【０１３２】
このようにすることで、本発明の第３の実施形態に係るリンク帯域変動量上限計算装置１（１ｃ）によれば、線形計画法による計算式で用いる変数（交流トラヒック帯域ｔｊ）の数、制約条件式（式２）における等号条件式の数を低減させた上で、計算精度を低下させることなく、リンク帯域変動量上限ベクトル１０００を生成することができる。
【０１３３】
≪実験例≫
次に、本発明の実施形態に係るリンク帯域変動量上限計算方法と、従来のリンク帯域変動量上限計算方法を比較した実験例について説明する。
【０１３４】
実験は、２つのネットワークトポロジを想定して行った。１つは、図１１（ａ）に示すＮＳＦ（全米科学財団ネットワーク）であり、ノード数１４、リンク数２１の比較的小さなネットワークトポロジで構成される。もう１つは、図１１（ｂ）に示すＣＯＳＴ２６６（全ヨーロッパネットワーク）であり、ノード数２６、リンク数５６でありＮＳＦに比べ大きなネットワークトポロジで構成される。この２つのネットワークについて、本実施形態における高速化レベル「ｋ」が「１」〜「４」の場合と、従来のリンク帯域変動量上限方法（従来法）とについて、リンク帯域変動量上限ベクトル１０００を生成する計算時間および計算精度を比較した。なお、本実施形態における高速化レベルｋにおける左側の棒グラフは、線形計画法による計算式を選択する処理時間と線形計画法による計算式の処理時間とを合計したトータルの処理時間を表わし、右側の棒グラフは、線形計画法による計算式の処理時間のみを表わす。
【０１３５】
このグラフから、図１１（ａ）に示すＮＦＳ、図１１（ｂ）に示すＣＯＳＴ２６６のいずれの場合においても、本実施形態におけるリンク帯域変動量上限計算方法の方が、計算時間が短縮されていることがわかる。特に、高速化レベル「１」において、変数の数と制約条件式の数をより多く削減した場合においては、処理速度が従来法と比べ、１０分の１かそれ以上短縮される。また、この高速化レベル「１」における計算精度（折れ線グラフ）をみると、ＮＳＦでは５％以内、ＣＯＳＴ２６６では２％以内の誤差に収まっている。さらに、高速化レベルを「３」や「４」にした場合でも、変数の数および制約条件式の数が変わらなくなるため、従来法と比べ計算精度は変わらず、かつ、不要な変数および制約条件式を削減した分、計算時間が短縮されることが示された。
【符号の説明】
【０１３６】
１      リンク帯域変動量上限計算装置
１０    入出力部
２０    処理部
２１    情報収集部
２２    制約条件選択部
２３    変数選択部
２４    高速化レベル処理部
２５    高速化レベル判定部
２６    変数数出力部
２７    変数数判定部
２８    リンク帯域変動量上限ベクトル計算部
２９    情報出力部
３０    記憶部
１００  リンク帯域ベクトル
２００  交流トラヒック経路行列
３００  経路変更後交流トラヒック経路行列
４００  制約条件情報
５００  変数情報
６００  目標高速化レベル情報
７００  高速化レベル情報
８００  変数数情報
１０００  リンク帯域変動量上限ベクトル
【図１】
0005325167.tif 000014
【図２】
0005325167.tif 000015
【図３】
0005325167.tif 000016
【図４】
0005325167.tif 000017
【図５】
0005325167.tif 000018
【図６】
0005325167.tif 000019
【図７】
0005325167.tif 000020
【図８】
0005325167.tif 000021
【図９】
0005325167.tif 000022
【図１０】
0005325167.tif 000023
【図１１】
0005325167.tif 000024
【図１２】
0005325167.tif 000025