(57)【要約】【課題】リンクの帯域測定に測定誤差が存在する場合であっても、経路変更による各リンク帯域の増設量を低減するリンク帯域設計を行うことができる、リンク帯域変動量上限計算装置、リンク帯域変動量上限計算方法およびプログラムを提供する。【解決手段】リンク帯域変動量上限計算装置１は、リンク帯域設計を行うネットワークのリンク数、交流トラヒック数、リンク帯域ベクトル２００、交流トラヒック経路行列４００、経路変更後交流トラヒック経路行列６００、および誤差処理パラメータ８００を用いて、線形計画法による演算式を解くことによって、経路変更により各交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトル１０００を生成する。【選択図】図６
2011166584.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークについて、経路変更後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置であって、
前記ネットワークに関する情報の送受信を行う入出力部と、
前記入出力部が受信した情報が記憶される記憶部と、
（１）前記各リンクにおいて測定される帯域の情報を示すリンク帯域ベクトル、（２）各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列、（３）経路変更された後の前記交流トラヒックの経路を示す経路変更後交流トラヒック経路行列、および（４）前記各リンクにおいて測定される帯域に含まれる測定誤差を修正するための所定の誤差処理パラメータを、前記入出力部を介して取得し、前記記憶部に記憶する情報収集部と、
前記リンク帯域ベクトルから前記ネットワーク内のリンク数を計算し、前記交流トラヒック経路行列から交流トラヒック数を計算し、前記計算したリンク数および交流トラヒック数、ならびに、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列、前記経路変更後交流トラヒック経路行列および前記所定の誤差処理パラメータを用いて線形計画法による計算式（式１）を解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するリンク帯域変動量上限ベクトル計算部と、
前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力する情報出力部と、を備え、
前記線形計画法による計算式（式１）は、
【数１】
2011166584.tif 000012
ことを特徴とするリンク帯域変動量上限計算装置。
【請求項２】
複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークについて、経路変更後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置であって、
前記ネットワークに関する情報の送受信を行う入出力部と、
前記入出力部が受信した情報が記憶される記憶部と、
（１）前記各リンクにおいて測定される帯域の情報を示すリンク帯域ベクトル、（２）各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列、および（３）経路変更された後の前記交流トラヒックの経路を示す経路変更後交流トラヒック経路行列を、前記入出力部を介して取得し、前記記憶部に記憶する情報収集部と、
前記記憶部に記憶した前記リンク帯域ベクトル、および前記交流トラヒック経路行列を用いて、以下に示す（式２−２）および（式２−３）を満たす経路変更前の交流トラヒック帯域ベクトルＴ０の解が存在する中で、前記各リンクにおいて測定される帯域に含まれる測定誤差を修正するための誤差処理パラメータのうち、最小の誤差処理パラメータαｍｉｎを、所定の探索アルゴリズムにより計算する誤差処理パラメータ計算部と、
前記リンク帯域ベクトルから前記ネットワーク内のリンク数を計算し、前記交流トラヒック経路行列から交流トラヒック数を計算し、前記計算したリンク数および交流トラヒック数、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列、ならびに、前記誤差処理パラメータ計算部が計算した前記最小の誤差処理パラメータαｍｉｎを用いて線形計画法による計算式（式２）を解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するリンク帯域変動量上限ベクトル計算部と、
前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力する情報出力部と、を備え、
前記線形計画法による計算式（式２）は、
【数２】
2011166584.tif 000013
ことを特徴とするリンク帯域変動量上限計算装置。
【請求項３】
前記誤差処理パラメータ計算部は、前記所定の探索アルゴリズムとして、以下に示す線形計画法による計算式（式３）を用いて、
【数３】
2011166584.tif 000014
（式３）に示す線形計画法による計算式を解くことによって、前記最小の誤差処理パラメータαｍｉｎを計算することを特徴とする請求項２に記載のリンク帯域変動量上限計算装置。
【請求項４】
前記誤差処理パラメータ計算部は、前記所定の探索アルゴリズムとして、以下に示す２次計画法による計算式（式４）を用いて、
【数４】
2011166584.tif 000015
（式４）に示す２次計画法による計算式を解くことにより、誤差処理パラメータベクトルεのうち、｜ε｜２を最小化させる誤差処理パラメータベクトルεｍｉｎを計算し、
前記リンク帯域変動量上限ベクトル計算部は、前記リンク数、前記交流トラヒック数、前記リンク帯域ベクトル、前記交流トラヒック経路行列、前記経路変更後交流トラヒック経路行列、および前記誤差処理パラメータ計算部が計算した誤差処理パラメータベクトルεｍｉｎを用いて、前記線形計画法による計算式（式２）の代わりに、以下に示す線形計画法による計算式（式５）を解くことにより、前記リンク帯域変動量上限ベクトルを生成し、
前記線形計画法による計算式（式５）は、
【数５】
2011166584.tif 000016
ことを特徴とする請求項２に記載のリンク帯域変動量上限計算装置。
【請求項５】
複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークについて、障害発生後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置であって、
前記ネットワークに関する情報の送受信を行う入出力部と、
前記入出力部が受信した情報が記憶される記憶部と、
（１）前記ネットワーク内における各ノードと各リンクとの接続関係を示すトポロジ情報、（２）前記各リンクにおいて測定される帯域の情報を示すリンク帯域ベクトル、（３）前記各ノードおよび前記各リンクの少なくとも一つにおいて障害が発生する箇所を示す障害発生箇所情報、および（４）前記各リンクにおいて測定される帯域に含まれる測定誤差を修正するための所定の誤差処理パラメータを、前記入出力部を介して取得し、前記記憶部に記憶する情報収集部と、
前記トポロジ情報を用いて、前記各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列を生成し、前記トポロジ情報および前記障害発生箇所情報を用いて、障害発生後の前記交流トラヒックの経路を示す障害発生後交流トラヒック経路行列を生成する交流トラヒック経路行列生成部と、
前記リンク帯域ベクトルから前記ネットワーク内のリンク数を計算し、前記トポロジ情報により示されるノード数から交流トラヒック数を計算し、前記計算したリンク数および交流トラヒック数、前記記憶部に記憶した前記リンク帯域ベクトルおよび前記所定の誤差処理パラメータ、ならびに、前記交流トラヒック経路行列生成部が生成した前記交流トラヒック経路行列および前記障害発生後交流トラヒック経路行列を用いて線形計画法による計算式（式１ａ）を解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するリンク帯域変動量上限ベクトル計算部と、
前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力する情報出力部と、を備え、
前記線形計画法による計算式（式１ａ）は、
【数６】
2011166584.tif 000017
ことを特徴とするリンク帯域変動量上限計算装置。
【請求項６】
複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークについて、障害発生後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置であって、
前記ネットワークに関する情報の送受信を行う入出力部と、
前記入出力部が受信した情報が記憶される記憶部と、
（１）前記ネットワーク内における各ノードと各リンクとの接続関係を示すトポロジ情報、（２）前記各リンクにおいて測定される帯域の情報を示すリンク帯域ベクトル、および（３）前記各ノードおよび前記各リンクの少なくとも一つにおいて障害が発生する箇所を示す障害発生箇所情報を、前記入出力部を介して取得し、前記記憶部に記憶する情報収集部と、
前記トポロジ情報を用いて、前記各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列を生成し、前記トポロジ情報および前記障害発生箇所情報を用いて、障害発生後の前記交流トラヒックの経路を示す障害発生後交流トラヒック経路行列を生成する交流トラヒック経路行列生成部と、
前記記憶部に記憶した前記リンク帯域ベクトル、および前記交流トラヒック経路行列を用いて、以下に示す（式２−２）および（式２−３）を満たす経路変更前の交流トラヒック帯域ベクトルＴ０の解が存在する中で、前記各リンクにおいて測定される帯域に含まれる測定誤差を修正するための誤差処理パラメータのうち、最小の誤差処理パラメータαｍｉｎを、所定の探索アルゴリズムにより計算する誤差処理パラメータ計算部と、
前記リンク帯域ベクトルから前記ネットワーク内のリンク数を計算し、前記トポロジ情報により示されるノード数から交流トラヒック数を計算し、前記計算したリンク数および交流トラヒック数、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列生成部が生成した前記交流トラヒック経路行列および前記障害発生後交流トラヒック経路行列、ならびに、前記誤差処理パラメータ計算部が計算した前記最小の誤差処理パラメータαｍｉｎを用いて線形計画法による計算式（式２ａ）を解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するリンク帯域変動量上限ベクトル計算部と、
前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力する情報出力部と、を備え、
前記線形計画法による計算式（式２ａ）は、
【数７】
2011166584.tif 000018
ことを特徴とするリンク帯域変動量上限計算装置。
【請求項７】
前記誤差処理パラメータ計算部は、前記所定の探索アルゴリズムとして、以下に示す線形計画法による計算式（式３）を用いて、
【数８】
2011166584.tif 000019
（式３）に示す線形計画法による計算式を解くことによって、前記最小の誤差処理パラメータαｍｉｎを計算することを特徴とする請求項６に記載のリンク帯域変動量上限計算装置。
【請求項８】
前記誤差処理パラメータ計算部は、前記所定の探索アルゴリズムとして、以下に示す２次計画法による計算式（式４）を用いて、
【数９】
2011166584.tif 000020
（式４）に示す２次計画法による計算式を解くことにより、誤差処理パラメータベクトルεのうち、｜ε｜２を最小化させる誤差処理パラメータベクトルεｍｉｎを計算し、
前記リンク帯域変動量上限ベクトル計算部は、前記リンク数、前記交流トラヒック数、前記リンク帯域ベクトル、前記交流トラヒック経路行列、前記障害発生後交流トラヒック経路行列、および前記誤差処理パラメータ計算部が計算した誤差処理パラメータベクトルεｍｉｎを用いて、前記線形計画法による計算式（式２ａ）の代わりに、以下に示す線形計画法による計算式（式５ａ）を解くことにより、前記リンク帯域変動量上限ベクトルを生成し、
前記線形計画法による計算式（式５ａ）は、
【数１０】
2011166584.tif 000021
ことを特徴とする請求項６に記載のリンク帯域変動量上限計算装置。
【請求項９】
前記情報収集部が、前記障害発生箇所情報の代わりに、前記各ノードおよび前記各リンクの少なくとも一つにおいて発生する障害の障害発生パターンを制約する障害発生パターン制約情報を取得し、
前記交流トラヒック経路行列生成部が、前記トポロジ情報および前記障害発生パターン制約情報を用いて、前記障害発生パターン制約情報の制約に基づく障害発生パターンごとに、その障害発生後の各障害発生後交流トラヒック経路行列を生成し、
前記リンク帯域変動量上限ベクトル計算部が、前記障害発生パターン制約情報の制約に基づく障害発生パターンごとに、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値である前記リンク帯域変動量上限ベクトルを生成すること、
を特徴とする請求項５ないし請求項８のいずれか１項に記載のリンク帯域変動量上限計算装置。
【請求項１０】
複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークについて、経路変更後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置に用いられるリンク帯域変動量上限計算方法であって、
前記リンク帯域変動量上限計算装置は、
前記ネットワークに関する情報の送受信を行う入出力部と、
前記入出力部が受信した情報が記憶される記憶部と、を備え、
（１）前記各リンクにおいて測定される帯域の情報を示すリンク帯域ベクトル、（２）各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列、（３）経路変更された後の前記交流トラヒックの経路を示す経路変更後交流トラヒック経路行列、および（４）前記各リンクにおいて測定される帯域に含まれる測定誤差を修正するための所定の誤差処理パラメータを、前記入出力部を介して取得し、前記記憶部に記憶するステップと、
前記リンク帯域ベクトルから前記ネットワーク内のリンク数を計算し、前記交流トラヒック経路行列から交流トラヒック数を計算し、前記計算したリンク数および交流トラヒック数、ならびに、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列、前記経路変更後交流トラヒック経路行列および前記所定の誤差処理パラメータを用いて線形計画法による計算式（式１）を解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するステップと、
前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力するステップと、を実行し、
前記線形計画法による計算式（式１）は、
【数１１】
2011166584.tif 000022
ことを特徴とするリンク帯域変動量上限計算方法。
【請求項１１】
複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークについて、経路変更後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置に用いられるリンク帯域変動量上限計算方法であって、
前記リンク帯域変動量上限計算装置は、
前記ネットワークに関する情報の送受信を行う入出力部と、
前記入出力部が受信した情報が記憶される記憶部と、を備え、
（１）前記各リンクにおいて測定される帯域の情報を示すリンク帯域ベクトル、（２）各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列、および（３）経路変更された後の前記交流トラヒックの経路を示す経路変更後交流トラヒック経路行列を、前記入出力部を介して取得し、前記記憶部に記憶するステップと、
前記記憶部に記憶した前記リンク帯域ベクトル、および前記交流トラヒック経路行列を用いて、以下に示す（式２−２）および（式２−３）を満たす経路変更前の交流トラヒック帯域ベクトルＴ０の解が存在する中で、前記各リンクにおいて測定される帯域に含まれる測定誤差を修正するための誤差処理パラメータのうち、最小の誤差処理パラメータαｍｉｎを、所定の探索アルゴリズムにより計算するステップと、
前記リンク帯域ベクトルから前記ネットワーク内のリンク数を計算し、前記交流トラヒック経路行列から交流トラヒック数を計算し、前記計算したリンク数および交流トラヒック数、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列、ならびに、前記計算した最小の誤差処理パラメータαｍｉｎを用いて線形計画法による計算式（式２）を解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するステップと、
前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力するステップと、を実行し、
前記線形計画法による計算式（式２）は、
【数１２】
2011166584.tif 000023
ことを特徴とするリンク帯域変動量上限計算方法。
【請求項１２】
複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークについて、障害発生後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置に用いられるリンク帯域変動量上限計算方法であって、
前記リンク帯域変動量上限計算装置は、
前記ネットワークに関する情報の送受信を行う入出力部と、
前記入出力部が受信した情報が記憶される記憶部と、を備え、
（１）前記ネットワーク内における各ノードと各リンクとの接続関係を示すトポロジ情報、（２）前記各リンクにおいて測定される帯域の情報を示すリンク帯域ベクトル、（３）前記各ノードおよび前記各リンクの少なくとも一つにおいて障害が発生する箇所を示す障害発生箇所情報、および（４）前記各リンクにおいて測定される帯域に含まれる測定誤差を修正するための所定の誤差処理パラメータを、前記入出力部を介して取得し、前記記憶部に記憶するステップと、
前記トポロジ情報を用いて、前記各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列を生成し、前記トポロジ情報および前記障害発生箇所情報を用いて、障害発生後の前記交流トラヒックの経路を示す障害発生後交流トラヒック経路行列を生成するステップと、
前記リンク帯域ベクトルから前記ネットワーク内のリンク数を計算し、前記トポロジ情報により示されるノード数から交流トラヒック数を計算し、前記計算したリンク数および交流トラヒック数、前記記憶部に記憶した前記リンク帯域ベクトルおよび前記所定の誤差処理パラメータ、ならびに、前記生成した前記交流トラヒック経路行列および前記障害発生後交流トラヒック経路行列を用いて線形計画法による計算式（式１ａ）を解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するステップと、
前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力するステップと、を実行し、
前記線形計画法による計算式（式１ａ）は、
【数１３】
2011166584.tif 000024
ことを特徴とするリンク帯域変動量上限計算方法。
【請求項１３】
複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークについて、障害発生後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置に用いられるリンク帯域変動量上限計算方法であって、
前記リンク帯域変動量上限計算装置は、
前記ネットワークに関する情報の送受信を行う入出力部と、
前記入出力部が受信した情報が記憶される記憶部と、を備え、
（１）前記ネットワーク内における各ノードと各リンクとの接続関係を示すトポロジ情報、（２）前記各リンクにおいて測定される帯域の情報を示すリンク帯域ベクトル、および（３）前記各ノードおよび前記各リンクの少なくとも一つにおいて障害が発生する箇所を示す障害発生箇所情報を、前記入出力部を介して取得し、前記記憶部に記憶するステップと、
前記トポロジ情報を用いて、前記各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列を生成し、前記トポロジ情報および前記障害発生箇所情報を用いて、障害発生後の前記交流トラヒックの経路を示す障害発生後交流トラヒック経路行列を生成するステップと、
前記記憶部に記憶した前記リンク帯域ベクトル、および前記交流トラヒック経路行列を用いて、以下に示す（式２−２）および（式２−３）を満たす経路変更前の交流トラヒック帯域ベクトルＴ０の解が存在する中で、前記各リンクにおいて測定される帯域に含まれる測定誤差を修正するための誤差処理パラメータのうち、最小の誤差処理パラメータαｍｉｎを、所定の探索アルゴリズムにより計算するステップと、
前記リンク帯域ベクトルから前記ネットワーク内のリンク数を計算し、前記トポロジ情報により示されるノード数から交流トラヒック数を計算し、前記計算したリンク数および交流トラヒック数、前記記憶部に記憶した前記リンク帯域ベクトル、前記生成した前記交流トラヒック経路行列および前記障害発生後交流トラヒック経路行列、ならびに、前記計算した前記最小の誤差処理パラメータαｍｉｎを用いて線形計画法による計算式（式２ａ）を解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するステップと、
前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力するステップと、を備え、
前記線形計画法による計算式（式２ａ）は、
【数１４】
2011166584.tif 000025
ことを特徴とするリンク帯域変動量上限計算方法。
【請求項１４】
前記障害発生箇所情報の代わりに、前記各ノードおよび前記各リンクの少なくとも一つにおいて発生する障害の障害発生パターンを制約する障害発生パターン制約情報を取得ステップと、
前記トポロジ情報および前記障害発生パターン制約情報を用いて、前記障害発生パターン制約情報の制約に基づく障害発生パターンごとに、その障害発生後の各障害発生後交流トラヒック経路行列を生成するステップと、
前記障害発生パターン制約情報の制約に基づく障害発生パターンごとに、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値である前記リンク帯域変動量上限ベクトルを生成するステップと、
を実行することを特徴とする請求項１２または請求項１３に記載のリンク帯域変動量上限計算方法。
【請求項１５】
請求項１０ないし請求項１４のいずれか１項に記載のリンク帯域変動量上限計算方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク上の各リンクの帯域設計に用いられ、リンク帯域の測定誤差に対応した、リンク帯域変動量上限計算装置、リンク帯域変動量上限計算方法およびプログラムに関する。
【背景技術】
【０００２】
品質保証を特徴とするネットワークサービスにおいては、安全かつ高品質なＩＰ（Internet Protocol）網の設計・運用が求められており、障害発生時のサービス継続に加えて、迂回トラヒックによる輻輳発生を考慮したネットワーク設計が必要となる。従来の一般的な設備設計においては、リンク単位の帯域を定期的に計測し、帯域が予め定めた閾値を超えたら、リンクを増設する方法をとっていた（非特許文献１参照）。
【０００３】
しかし、非特許文献１に記載されたリンク単位の帯域を計測する技術では、エッジルータ間の交流トラヒックを考慮しておらず、以下に説明するように、厳密なリンク帯域設計が困難であった。
【０００４】
各リンク帯域と障害発生前後の各交流トラヒックの経路を事前に把握している場合、各交流トラヒックの帯域が特定できれば、障害発生による各リンクの帯域変動値を求めることができる。例えば、図１６において、交流トラヒックＡ（帯域：ａ），Ｂ（帯域：ｂ），Ｃ（帯域：ｃ）が流れるリンク＃１で障害が発生した場合、リンク＃４，＃５，＃６の増加量はａ＋ｂであり、リンク＃７，＃８，＃９，＃１０の増加量はｃである。しかし、従来技術においては、交流トラヒックの帯域の特定が困難であるため、各交流トラヒックの帯域を考慮しないリンク帯域変動範囲として、障害発生前の障害リンクの帯域値を変動範囲の上限とする。つまり、従来技術によれば、図１６において、リンク＃４，＃５，＃６、およびリンク＃７，＃８，＃９，＃１０の帯域変動の上限を障害発生前リンク＃１の帯域であり、交流トラヒックＡ，Ｂ，Ｃの帯域の和であるａ＋ｂ＋ｃとして帯域設計を行う。しかし、実際の帯域変動量と比べると、リンク＃４，＃５，＃６ではｃ、リンク＃７，＃８，＃９，＃１０ではａ＋ｂの帯域が無駄になってしまう。
【０００５】
そこで、迂回トラヒックによる輻輳発生の回避を考慮したリンク帯域設計法として、交流トラヒック帯域を変数として扱い、リンク帯域情報から線形計画法により、各交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値を算出する方法が考えられる。
【０００６】
この線形計画法により帯域変動量の上限値を算出する方法とは、経路変更あるいは障害発生等により、各交流トラヒックの経路が変更されたときのリンク帯域の上限値（最大値）を線形計画法によって求め、その上限値に基づいて、各リンクの帯域設計を行うものである。ここで、線形計画問題は、以下の（式６）で表される。
【０００７】
【数１】
2011166584.tif 000003
【０００８】
この（式６）に示す線形計画問題は、この制約式（式６−２）および（式６−３）を満たす範囲内で、各ｔｊを変動させて目的式（式６−１）を満たすリンク帯域変動量の上限値を最大化させるものである。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】小島久史，他，「交流トラヒックを用いたネットワーク設計・運用方式の提案」，電子情報通信学会総合大会，B-6-9，2009年3月
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、リンク帯域の測定を、各ノードが実行する際に、測定誤差が生じる場合がある。リンク帯域測定では、一般的に各ルータ（ノード）が所定時間のリンク使用トラヒック量の測定を行い、各ルータ（ノード）に備わるＭＩＢ（Manegement Information Base）にその情報を格納する。本発明に係るリンク帯域変動量上限計算装置は、このＭＩＢに格納された各リンクのリンク帯域の情報を取得する。よって、取得した各リンクのリンク帯域の情報に測定誤差を含む場合、前記した線形計画問題が解けない状況が発生するときがある。つまり、制約式（式６−２）および（式６−３）を満たす交流トラヒック帯域ｔｊが存在しない状況が存在する。この測定誤差は、例えば、各リンクにおけるトラヒック測定時刻が同期していない場合等に生じる。
【００１１】
このような背景に鑑みて本発明がなされたのであり、本発明は、リンクの帯域測定に測定誤差が存在する場合であっても、経路変更による各リンク帯域の増設量を低減するリンク帯域設計を行うことができる、リンク帯域変動量上限計算装置、リンク帯域変動量上限計算方法およびプログラムを提供することを課題とする。
【課題を解決するための手段】
【００１２】
前記した課題を解決するため、請求項１に記載の発明は、複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークについて、経路変更後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置であって、前記ネットワークに関する情報の送受信を行う入出力部と、前記入出力部が受信した情報が記憶される記憶部と、（１）前記各リンクにおいて測定される帯域の情報を示すリンク帯域ベクトル、（２）各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列、（３）経路変更された後の前記交流トラヒックの経路を示す経路変更後交流トラヒック経路行列、および（４）前記各リンクにおいて測定される帯域に含まれる測定誤差を修正するための所定の誤差処理パラメータを、前記入出力部を介して取得し、前記記憶部に記憶する情報収集部と、前記リンク帯域ベクトルから前記ネットワーク内のリンク数を計算し、前記交流トラヒック経路行列から交流トラヒック数を計算し、前記計算したリンク数および交流トラヒック数、ならびに、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列、前記経路変更後交流トラヒック経路行列および前記所定の誤差処理パラメータを用いて線形計画法による計算式（式１）を解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するリンク帯域変動量上限ベクトル計算部と、前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力する情報出力部と、を備え、前記線形計画法による計算式（式１）は、請求項１に記載の線形計画法による計算式（式１）であることを特徴とする。
【００１３】
また、請求項１０に記載の発明は、複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークについて、経路変更後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置に用いられるリンク帯域変動量上限計算方法であって、前記リンク帯域変動量上限計算装置が、前記ネットワークに関する情報の送受信を行う入出力部と、前記入出力部が受信した情報が記憶される記憶部と、を備え、（１）前記各リンクにおいて測定される帯域の情報を示すリンク帯域ベクトル、（２）各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列、（３）経路変更された後の前記交流トラヒックの経路を示す経路変更後交流トラヒック経路行列、および（４）前記各リンクにおいて測定される帯域に含まれる測定誤差を修正するための所定の誤差処理パラメータを、前記入出力部を介して取得し、前記記憶部に記憶するステップと、前記リンク帯域ベクトルから前記ネットワーク内のリンク数を計算し、前記交流トラヒック経路行列から交流トラヒック数を計算し、前記計算したリンク数および交流トラヒック数、ならびに、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列、前記経路変更後交流トラヒック経路行列および前記所定の誤差処理パラメータを用いて線形計画法による計算式（式１）を解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するステップと、前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力するステップと、を実行し、前記線形計画法による計算式（式１）は、請求項１０に記載の線形計画法による計算式（式１）であることを特徴とする。
【００１４】
このようにすることで、リンク帯域変動量上限計算装置は、リンク帯域ベクトルと、交流トラヒック経路行列と、経路変更後交流トラヒック経路行列と、誤差処理パラメータとを取得し、リンク帯域ベクトルからリンク数を計算し、交流トラヒック経路行列から交流トラヒック数を計算する。そして、リンク帯域変動量上限計算装置は、請求項１に示す線形計画法による計算式（式１）を解くことにより、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成する。また、リンク帯域変動量上限計算装置は、入力された誤差処理パラメータαの値が、請求項１に示す線形計画法による計算式（式１−２）および（式１−３）を満たす解が存在しない値の場合に、リンク帯域変動量上限ベクトルを線形計画法による計算式（式１）によりリンク帯域変動量上限ベクトルを生成できず、空集合ベクトルを生成する。
【００１５】
よって、本発明によれば、予め設定した誤差処理パラメータを用いて、リンク帯域の測定に測定誤差が存在する場合であっても、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成することができる。そして、各リンクの帯域変動量の上限値は、経路変更後に必要な帯域増設量の最小値となるため、リンク帯域設計において、実際に必要な帯域増設量からの余剰帯域、つまり無駄となる帯域設計量を低減することが可能となる。また、請求項１に示す線形計画法による計算式（式１）の解が存在しない場合に、空集合ベクトルを生成することで、予め設定する誤差処理パラメータの変更が必要なことを示すことができる。
【００１６】
請求項２に記載の発明は、複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークについて、経路変更後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置であって、前記ネットワークに関する情報の送受信を行う入出力部と、前記入出力部が受信した情報が記憶される記憶部と、（１）前記各リンクにおいて測定される帯域の情報を示すリンク帯域ベクトル、（２）各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列、および（３）経路変更された後の前記交流トラヒックの経路を示す経路変更後交流トラヒック経路行列を、前記入出力部を介して取得し、前記記憶部に記憶する情報収集部と、前記記憶部に記憶した前記リンク帯域ベクトル、および前記交流トラヒック経路行列を用いて、請求項２に記載の（式２−２）および（式２−３）を満たす経路変更前の交流トラヒック帯域ベクトルＴ０の解が存在する中で、前記各リンクにおいて測定される帯域に含まれる測定誤差を修正するための誤差処理パラメータのうち、最小の誤差処理パラメータαｍｉｎを、所定の探索アルゴリズムにより計算する誤差処理パラメータ計算部と、前記リンク帯域ベクトルから前記ネットワーク内のリンク数を計算し、前記交流トラヒック経路行列から交流トラヒック数を計算し、前記計算したリンク数および交流トラヒック数、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列、ならびに、前記誤差処理パラメータ計算部が計算した前記最小の誤差処理パラメータαｍｉｎを用いて線形計画法による計算式（式２）を解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するリンク帯域変動量上限ベクトル計算部と、前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力する情報出力部と、を備え、前記線形計画法による計算式（式２）は、請求項２に記載の線形計画法による計算式（式２）であることを特徴とする。
【００１７】
また、請求項１１に記載の発明は、複数のノードと前記複数のノード間を接続する複数のリンクとを備えるネットワークについて、経路変更後の各リンクの帯域変動量の上限値を計算するリンク帯域変動量上限計算装置に用いられるリンク帯域変動量上限計算方法であって、前記リンク帯域変動量上限計算装置が、前記ネットワークに関する情報の送受信を行う入出力部と、前記入出力部が受信した情報が記憶される記憶部と、を備え、（１）前記各リンクにおいて測定される帯域の情報を示すリンク帯域ベクトル、（２）各ノード間のトラヒックである交流トラヒックの経路を示す交流トラヒック経路行列、および（３）経路変更された後の前記交流トラヒックの経路を示す経路変更後交流トラヒック経路行列を、前記入出力部を介して取得し、前記記憶部に記憶するステップと、前記記憶部に記憶した前記リンク帯域ベクトル、および前記交流トラヒック経路行列を用いて、請求項１１に示す（式２−２）および（式２−３）を満たす経路変更前の交流トラヒック帯域ベクトルＴ０の解が存在する中で、前記各リンクにおいて測定される帯域に含まれる測定誤差を修正するための誤差処理パラメータのうち、最小の誤差処理パラメータαｍｉｎを、所定の探索アルゴリズムにより計算するステップと、前記リンク帯域ベクトルから前記ネットワーク内のリンク数を計算し、前記交流トラヒック経路行列から交流トラヒック数を計算し、前記計算したリンク数および交流トラヒック数、前記記憶部に記憶した前記リンク帯域ベクトル、前記交流トラヒック経路行列および前記経路変更後交流トラヒック経路行列、ならびに、前記計算した最小の誤差処理パラメータαｍｉｎを用いて線形計画法による計算式（式２）を解くことにより、前記交流トラヒックの経路が変更されたときの前記各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成するステップと、前記生成したリンク帯域変動量上限ベクトルを、前記入出力部を介して出力するステップと、を実行し、前記線形計画法による計算式（式２）は、請求項１１に記載の線形計画法による計算式（式２）であることを特徴とする。
【００１８】
このようにすることで、リンク帯域変動量上限計算装置は、リンク帯域ベクトルと、交流トラヒック経路行列と、経路変更後交流トラヒック経路行列とを取得し、リンク帯域ベクトルからリンク数を計算し、交流トラヒック経路行列から交流トラヒック数を計算する。そして、リンク帯域変動量上限計算装置は、請求項２に示す線形計画法による計算式（式２）を解くことにより、所定の探索アルゴリズムを用いて、最小の誤差処理パラメータαｍｉｎを算出し、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成する。
【００１９】
よって、本発明によれば、最小の誤差処理パラメータαｍｉｎを用いて線形計画法による計算式（式２）を計算することにより、リンク帯域の測定誤差による影響を最も小さくした上で、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成することができる。そして、各リンクの帯域変動量の上限値は、経路変更後に必要な帯域増設量の最小値となるため、リンク帯域設計において、実際に必要な帯域増設量からの余剰帯域、つまり無駄となる帯域設計量を低減することが可能となる。
【００２０】
請求項５および請求項１２に記載の発明によれば、リンク帯域変動量上限計算装置が、各リンクと各ノードとの接続関係を示すトポロジ情報と、リンク帯域ベクトルと、ノードやリンクに発生した障害箇所を示す障害発生箇所情報と、誤差処理パラメータとを取得し、トポロジ情報から交流トラヒック経路行列を生成し、トポロジ情報および障害発生箇所情報から障害発生後交流トラヒック経路行列を生成し、リンク帯域ベクトルからリンク数を計算し、トポロジ情報に示されるノード数から交流トラヒック数を計算する。そして、リンク帯域変動量上限計算装置は、請求項５（請求項１２）に示す線形計画法による計算式（式１ａ）を解くことにより、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成する。
【００２１】
よって、本発明によれば、経路変更後交流トラヒック経路行列を取得することなく、予めネットワーク設計者が設定した誤差処理パラメータと障害発生箇所情報とを用いて、リンク帯域の測定に測定誤差が存在する場合であっても、障害発生により交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値を求めることができる。
【００２２】
請求項６および請求項１３に記載の発明によれば、リンク帯域変動量上限計算装置が、トポロジ情報と、リンク帯域ベクトルと、障害発生箇所情報とを取得し、トポロジ情報から交流トラヒック経路行列を生成し、トポロジ情報および障害発生箇所情報から障害発生後交流トラヒック経路行列を生成し、リンク帯域ベクトルからリンク数を計算し、トポロジ情報に示されるノード数から交流トラヒック数を計算する。また、リンク帯域ベクトルおよび交流トラヒック経路行列を用いて、最小の誤差処理パラメータαｍｉｎを計算する。そして、リンク帯域変動量上限計算装置は、請求項６（請求項１３）に示す線形計画法による計算式（式２ａ）を解くことにより、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成する。
【００２３】
よって、本発明によれば、誤差処理パラメータが入力されない場合であっても、所定の探索アルゴリズムを用いて、最小の誤差処理パラメータαｍｉｎを算出することができる。そして、最小の誤差処理パラメータαｍｉｎを用いて線形計画法による計算式（式２ａ）を計算することにより、リンク帯域の測定誤差による影響を最も小さくした上で、障害発生により交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値を求めることができる。
【００２４】
請求項３および請求項７に記載の発明によれば、リンク帯域変動量上限計算装置は、所定の探索アルゴリズムとして、請求項３（請求項７）に示す線形計画法による計算式（式３）を解くことによって、前記最小の誤差処理パラメータαｍｉｎを計算することができる。
【００２５】
よって、本発明によれば、所定の誤差処理パラメータのうち、最小の誤差処理パラメータαｍｉｎを、線形計画法による計算式（式３）を用いて求めることができる。
【００２６】
請求項４および請求項８に記載の発明によれば、リンク帯域変動量上限計算装置は、所定の探索アルゴリズムとして、請求項４（請求項８）に示す２次計画法による計算式（式４）を解くことにより、誤差処理パラメータベクトルεのうち、｜ε｜２を最小化させる誤差処理パラメータベクトルεｍｉｎを計算する。そして、リンク帯域変動量上限計算装置は、リンク数、交流トラヒック数、リンク帯域ベクトル、交流トラヒック経路行列、経路変更後交流トラヒック経路行列、および計算した誤差処理パラメータベクトルεｍｉｎを用いて、請求項４（請求項８）に示す線形計画法による計算式（式５（式５ａ））を解くことにより、前記リンク帯域変動量上限ベクトルを生成する。
【００２７】
よって、本発明によれば、誤差処理パラメータが入力されない場合であっても、２次計画法による計算式（式４）を用いて、誤差処理パラメータベクトルεｍｉｎを算出し、線形計画法による計算式（式５（式５ａ））を用いて、リンク帯域変動量上限ベクトルを生成することができる。
【００２８】
請求項９および請求項１４に記載の発明によれば、リンク帯域変動量上限計算装置は、各ノードおよび各リンクの少なくとも一つにおいて発生する障害の障害発生パターンを制約する障害発生パターン制約情報を取得し、トポロジ情報および障害発生パターン制約情報を用いて、障害発生パターン制約情報の制約に基づく障害発生パターンごとに、その障害発生後の各障害発生後交流トラヒック経路行列を生成する。そして、リンク帯域変動量上限計算装置は、障害発生パターン制約情報の制約に基づく障害発生パターンごとに、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値である前記リンク帯域変動量上限ベクトルを生成する。
【００２９】
よって、本発明によれば、リンク帯域の測定に測定誤差が存在する場合であっても、障害発生パターン制約情報を用いて、障害発生パターン制約情報の制約に基づく障害発生パターンごとに、障害発生後の交流トラヒックの経路変更による各リンク帯域の変動量の上限値を求めることができる。
【００３０】
請求項１５に記載に発明は、請求項１０ないし請求項１４のいずれか１項に記載のリンク帯域変動量上限計算方法をコンピュータに実行させるためのプログラムとした。
【００３１】
このようなプログラムによれば、請求項１０ないし請求項１４のいずれか１項に記載のリンク帯域変動量上限計算方法を一般的なコンピュータに実行させることができる。
【発明の効果】
【００３２】
本発明によれば、リンクの帯域測定に測定誤差が存在する場合であっても、経路変更による各リンク帯域の増設量を低減するリンク帯域設計を行うことができる、リンク帯域変動量上限計算装置、リンク帯域変動量上限計算方法およびプログラムを提供することが可能となる。
【図面の簡単な説明】
【００３３】
【図１】本実施形態に係るリンク帯域変動量上限計算装置が、リンク帯域変動量の上限計算処理を行うネットワークの一例を示す図である。
【図２】本実施形態に係るトポロジ情報を説明するための図である。
【図３】本実施形態に係るリンク帯域ベクトルを説明するための図である。
【図４】本実施形態に係る交流トラヒック帯域ベクトルを説明するための図である。
【図５】本実施形態に係る交流トラヒック経路行列を説明するための図である。
【図６】本実施形態１に係るリンク帯域変動量上限計算装置の構成例を示す機能ブロック図である。
【図７】本実施形態１に係るリンク帯域変動量上限計算処理の流れを示すフローチャートである。
【図８】本実施形態２に係るリンク帯域変動量上限計算装置の構成例を示す機能ブロック図である。
【図９】本実施形態２に係るリンク帯域変動量上限計算処理の流れを示すフローチャートである。
【図１０】本実施形態３に係るリンク帯域変動量上限計算装置の構成例を示す機能ブロック図である。
【図１１】本実施形態３に係る障害発生箇所情報のデータ構造の一例を説明するための図である。
【図１２】本実施形態３に係るリンク帯域変動量上限計算処理の流れを示すフローチャートである。
【図１３】本実施形態４に係るリンク帯域変動量上限計算装置の構成例を示す機能ブロック図である。
【図１４】本実施形態５に係るリンク帯域変動量上限計算装置の構成例を示す機能ブロック図である。
【図１５】本実施形態６に係るリンク帯域変動量上限計算装置の構成例を示す機能ブロック図である。
【図１６】従来技術における帯域変動値の決定方法を説明するための図である。
【発明を実施するための形態】
【００３４】
次に、発明を実施するための形態（以下、「実施形態」という）について、適宜図面を参照しながら詳細に説明する。まず、本実施形態に係るリンク帯域変動量上限計算装置による、リンク帯域の測定誤差を考慮したリンク帯域変動量上限計算処理の概要と、そのリンク帯域変動量上限計算処理において取り扱うネットワークの各情報について説明する。
【００３５】
図１は、本実施形態に係るリンク帯域変動量上限計算装置が、リンク帯域変動量の上限計算処理を行うネットワークの一例を示す図である。図１に示すネットワークにおいて、経路変更後もしくはノードの障害やリンクの障害が発生したときの障害発生後の各リンクのリンク帯域変動量の上限を、リンク帯域変動量上限計算装置が計算する処理を例として説明する。
【００３６】
図１に示すように、例えば、ノード「０」，ノード「１」，ノード「２」，ノード「３」の４つのノードが、それぞれリンクにより接続される。リンクは、送信元のノードと送信先のノードとを接続し、ノード間でトラヒックの流れる方向により、例えば、ノード「０」からノード「１」へのリンクはリンク＃０、ノード「１」からノード「０」へのリンクはリンク＃５、のようにトラヒックの流れる方向により別々に設定される。
【００３７】
本実施形態に係るリンク帯域変動量上限計算装置は、後記するネットワーク内のトラヒックに関する情報を受け付けることにより得られた、当該ネットワークのリンク数、交流トラヒック数、各リンクの現時点（経路変更前もしくは障害発生前）での帯域の情報を示すリンク帯域ベクトル、現時点のトラヒックの経路を示す交流トラヒック経路行列、経路変更後もしくは障害発生後の交流トラヒック経路行列、および誤差処理パラメータを用いて、以下に説明する線形計画法による計算式を解くことによって、経路変更もしくは障害発生により各交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトルを生成する。
【００３８】
ここで、トポロジ情報、リンク帯域ベクトル、交流トラヒック帯域ベクトル、および交流トラヒック経路行列について説明する。
【００３９】
図２は、本実施形態に係るトポロジ情報１００を説明するための図である。トポロジ情報１００は、ネットワーク内の各ノードと各リンクとの接続関係を示し、例えば、図２（ａ）に示すように、各ノードが各リンクで接続されているものとする。このトポロジ情報１００は、図２（ｂ）に示すような行列で表すことができ、ｍ行ｎ列に対応する各ノードの接続関係を「０」「１」の値で示している。ここで、「１」は、ノードｍとノードｎが隣接ノードであることを意味する。また、「０」は、ノードｍとノードｎが隣接ノードではないこと、つまり、ノードｍとノードｎが同じノードであるか、または、隣接しないノードであることを意味する。例えば、ｍ行のノード「０」と対応するｎ行のノード「１」をみると、「１」の値を示しているので、ノード「０」とノード「１」は隣接ノードであることがわかる。一方、ｍ行のノード「０」とｎ行のノード「２」をみると、「０」の値を示しているので、ノード「０」とノード「２」が隣接しないノードであることがわかる。このようにトポロジ情報１００は、各ノード間の隣接関係を行列で表すことができる。
【００４０】
図３は、本実施形態に係るリンク帯域ベクトル２００を説明するための図である。リンク帯域ベクトル２００は、各リンクで測定されるトラヒック帯域をリンク番号順にベクトル表示したものである。例えば、図３（ａ）に示すネットワークにおいて、リンク帯域ベクトルは、図３（ｂ）に示すように、リンク＃０からリンク＃９で測定される帯域をリンク番号順にベクトル表示する。ここでは、例えば、リンク＃０で測定された帯域が「１５（Ｍｂｐｓ）」であり、リンク＃１で測定された帯域が「９（Ｍｂｐｓ）」であることを示す。なお、ここで測定された各リンクの測定帯域の値には、例えば、各ノードにおいてトラヒック測定時刻が同期していない場合等に測定誤差が生じる。このリンク帯域の測定に測定誤差が生じている場合、リンク帯域変動量上限計算装置により、後記する線形計画問題が解けない状況が発生する。
【００４１】
また、リンク帯域ベクトル２００は、
リンク帯域ベクトルＸ＝（ｘ０，ｘ１，…，ｘＬ−１）ｔｒ
と表記でき、ここで  tr は、行列（ベクトル）の転置（行と列の入れ替え）を意味する。
【００４２】
図４は、本実施形態に係る交流トラヒック帯域ベクトルを説明するための図である。交流トラヒックは、ネットワーク内の２つのノード間のトラヒックの流れを意味する。また、交流トラヒック帯域とは、交流トラヒックの帯域値を意味する。また、ネットワーク内のノード数がｎのとき、交流トラヒック数は、ｎ（ｎ−１）となる。図４（ａ）は、ノード「０」からノード「３」までの４つのノードにおける、各交流トラヒックを示し、図４（ｂ）は、各交流トラヒックで測定される交流トラヒック量を交流トラヒック番号順にベクトル表示した交流トラヒック帯域ベクトルである。例えば、交流トラヒック「０」（ノード「０」からノード「１」）の交流トラヒック量は「４（Ｍｂｐｓ）」であることを示す。
【００４３】
なお、この交流トラヒック帯域ベクトルは、
交流トラヒック帯域ベクトルＴ＝（ｔ０，ｔ１，…，ｔＴ−１）ｔｒ
と表記できる。
【００４４】
図５は、本実施形態に係る交流トラヒック経路行列４００を説明するための図である。交流トラヒック経路行列４００は、各交流トラヒックが各リンクを経由しているか否かを、経由する場合は「１」、経由しない場合は「０」で表すことにより、各交流トラヒックの経路を示す行列である。各交流トラヒックが図５（ａ）のように、各リンクを経由している場合において、交流トラヒック経路行列は、図５（ｂ）に示すように、各リンクと各交流トラヒックとの関係を行列で表示する。例えば、交流トラヒック「１」（ノード「０」からノード「２」へのトラヒック）は、図５（ｂ）の交流トラヒック経路行列４００において、リンク＃０とリンク＃１との値が「１」になっていることから、リンク＃０とリンク＃１とを経由することが示される。
【００４５】
次に、本実施形態１−６について説明する。実施形態１，２は、リンク帯域変動量上限計算装置１に、経路変更後の交流トラヒック経路行列が入力情報として入力される場合に、経路変更後の各リンクの帯域変動量の上限値を計算するものである。実施形態１は、入力情報として誤差処理パラメータ８００を含み、実施形態２は、入力情報として誤差処理パラメータ８００を含まないものである。また、実施形態３−６は、ネットワーク内のノードやリンクに障害が発生したと想定し、障害発生により交流トラヒックの経路が変更された後において各リンクの帯域変動量の上限値を計算するものである。実施形態３は、入力情報として障害発生箇所情報３００と誤差処理パラメータ８００とを含み、実施形態４は、入力情報として、障害発生箇所情報３００は含むが、誤差処理パラメータ８００は含まないものである。実施形態５は、入力情報として、ノードやリンクの障害発生箇所を制約する条件としての障害発生パターン制約情報７００と誤差処理パラメータ８００とを含み、実施形態６は、入力情報として、障害発生パターン制約情報７００は含むが、誤差処理パラメータ８００は含まないものである。
【００４６】
≪実施形態１≫
まず、本実施形態１に係るリンク帯域変動量上限計算装置１（１ａ）について説明する。
【００４７】
（実施形態１のリンク帯域変動量上限計算装置の構成）
図６は、本実施形態１に係るリンク帯域変動量上限計算装置１（１ａ）の構成例を示す機能ブロック図である。図６に示すように、リンク帯域変動量上限計算装置１ａは、入出力部１０と、処理部２０と、記憶部３０とを含んで構成される。
【００４８】
入出力部１０は、例えば、ネットワークに設けられたネットワーク管理装置（不図示）から、リンク帯域ベクトル２００（図３参照）、交流トラヒック経路行列４００（図５参照）、経路変更後交流トラヒック経路行列６００、および誤差処理パラメータ８００等の対象となるネットワークのトラヒックに関する情報を取得する。ここで、経路変更後交流トラヒック経路行列６００は、ネットワーク設計者が、ネットワークの点検や、所定の計画にそって、使用不可とするノードやリンクを経由させずにネットワークを設計した場合に、予め経路変更後の交流トラヒックの経路を決定し、リンク帯域変動量上限計算装置１ａに入力する情報である。また、誤差処理パラメータ８００は、各リンクにおいて測定される帯域（リンク帯域）に測定誤差が含まれている場合であっても、リンク帯域変動量の上限値を計算できるようにするためのパラメータである。本実施形態１においては、ネットワーク設計者により、予め所定の誤差処理パラメータ８００が設定されて入出力部１０に入力される。
【００４９】
また、入出力部１０は、処理部２０が生成した、後記するリンク帯域変動量上限ベクトル１０００を出力する。なお、この入出力部１０は、入出力インタフェースや通信インタフェース等で構成される。
【００５０】
処理部２０は、リンク帯域変動量上限計算装置１ａの全体の制御を司り、情報収集部２１と、リンク帯域変動量上限ベクトル計算部２３と、情報出力部２５とを備える。なお、この処理部２０および入出力部１０は、例えば、リンク帯域変動量上限計算装置１ａの記憶部３０に格納されたプログラムを、ＣＰＵ（Central Processing Unit）がＲＡＭ（Random Access Memory）に展開し実行することで実現される。
【００５１】
情報収集部２１は、入出力部１０を介して、リンク帯域ベクトル２００、交流トラヒック経路行列４００、経路変更後交流トラヒック経路行列６００、および誤差処理パラメータ８００を取得し、各情報を記憶部３０に記憶させる。
【００５２】
リンク帯域変動量上限ベクトル計算部２３は、リンク数と、交流トラヒック数と、リンク帯域ベクトル２００と、交流トラヒック経路行列４００と、経路変更後交流トラヒック経路行列６００と、誤差処理パラメータ８００と、を用いて以下に示す線形計画法による計算式（式１）により、各交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトル１０００を生成する。そして、リンク帯域変動量上限ベクトル計算部２３は、生成したリンク帯域変動量上限ベクトル１０００を記憶部３０に記憶する。
【００５３】
なお、リンク帯域変動量上限ベクトル計算部２３は、リンク数Ｌを記憶部３０に記憶されたリンク帯域ベクトル２００（図３参照）から計算し、また、交流トラヒック数Ｔを記憶部３０に記憶された交流トラヒック経路行列４００（図５参照）から計算する。そして、リンク帯域変動量上限ベクトル計算部２３は、以下に示す線形計画法による計算式（式１）を用いて、リンク帯域変動量上限ベクトル１０００を生成する。
【００５４】
【数２】
2011166584.tif 000004
【００５５】
このリンク帯域変動量上限ベクトル計算部２３により計算されるリンク帯域変動量上限ベクトルＸｓは、
Ｘｓ＝（ｘｓ０，ｘｓ１，…，ｘｓＬ−１）ｔｒ
として求められ、ここで、ｘｓ０，ｘｓ１，…，ｘｓＬ−１は、各リンク＃０，＃１，＃２，…，＃（Ｌ−１）の順にベクトル表示された帯域変動量の上限値を意味する。
【００５６】
次に、情報出力部２５は、記憶部３０に記憶されたリンク帯域変動量上限ベクトル１０００を、入出力部１０を介して出力する。
【００５７】
記憶部３０は、リンク帯域ベクトル２００、交流トラヒック経路行列４００、経路変更後交流トラヒック経路行列６００、誤差処理パラメータ８００、およびリンク帯域変動量上限ベクトル１０００が記憶される記憶手段であり、ハードディスク、フラッシュメモリ等で構成される。
【００５８】
（実施形態１のリンク帯域変動量上限計算処理）
次に、リンク帯域変動量上限計算装置１ａのリンク帯域変動量上限計算処理の流れを説明する。図７は、本実施形態１に係るリンク帯域変動量上限計算処理の流れを示すフローチャートである。
【００５９】
まず、リンク帯域変動量上限計算装置１ａの情報収集部２１は、入出力部１０を介して、リンク帯域ベクトル２００、交流トラヒック経路行列４００、経路変更後交流トラヒック経路行列６００、および誤差処理パラメータ８００を取得し（ステップＳ１０１）、記憶部３０に記憶させる。
【００６０】
次に、リンク帯域変動量上限ベクトル計算部２３は、記憶部３０に記憶されたリンク帯域ベクトル２００から対象となるネットワークのリンク数を計算し、交流トラヒック経路行列４００から対象となるネットワークの交流トラヒック数を計算する（ステップＳ１０２）。
【００６１】
続いて、リンク帯域変動量上限ベクトル計算部２３は、ステップＳ１０２で計算したリンク数および交流トラヒック数、ならびにステップＳ１０１で取得した、リンク帯域ベクトル２００、交流トラヒック経路行列４００、経路変更後交流トラヒック経路行列６００、および誤差処理パラメータ８００を用いて、前記した線形計画法による計算式（式１）を解くことによって、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトル１０００を生成する（ステップＳ１０３）。そして、リンク帯域変動量上限ベクトル計算部２３は、生成したリンク帯域変動量上限ベクトル１０００を記憶部３０に記憶する。
【００６２】
次に、情報出力部２５は、記憶部３０に記憶されたリンク帯域変動量上限ベクトル１０００を、入出力部１０を介して出力する（ステップＳ１０４）。
【００６３】
このようにすることで、本実施形態１に係るリンク帯域変動量上限計算装置１ａによれば、予めネットワーク設計者が設定した誤差処理パラメータ８００を用いて、リンク帯域の測定に測定誤差が存在する場合であっても、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトル１０００を生成することができる。そして、各リンクの帯域変動量の上限値は、経路変更後に必要な帯域増設量の最小値となるため、リンク帯域設計において、実際に必要な帯域増設量からの余剰帯域、つまり無駄となる帯域設計量を低減することが可能となる。
【００６４】
なお、リンク帯域変動量上限計算装置１ａは、ネットワーク設計者により入力される誤差処理パラメータαが、線形計画法による計算式（式１−２）および（式１−３）を満たす解が存在しない値である場合、線形計画法による計算式（式１）によりリンク帯域変動量上限ベクトルを生成できないため、空集合ベクトルを生成する。そして、リンク帯域変動量上限計算装置１ａが、空集合ベクトルを入出力部１０を介して出力することで、入力された誤差処理パラメータ８００が不適当な値であることをネットワーク設計者に対して示し、誤差処理パラメータ８００の変更を促すことができる。
【００６５】
≪実施形態２≫
次に、本実施形態２に係るリンク帯域変動量上限計算装置１について説明する。本実施形態２に係るリンク帯域変動量上限計算装置１は、実施形態１において入力された誤差処理パラメータ８００を取得せず、所定の探索アルゴリズムにより、誤差処理パラメータ８００のうちの、最小の誤差処理パラメータを計算して、リンク帯域変動量上限ベクトルを生成することを特徴とする。
【００６６】
（実施形態２のリンク帯域変動量上限計算装置の構成）
図８は、本実施形態２に係るリンク帯域変動量上限計算装置１（１ｂ）の構成例を示す機能ブロック図である。図８に示すように、リンク帯域変動量上限計算装置１ｂは、図６に示したリンク帯域変動量上限計算装置１ａと同様に、入出力部１０と、処理部２０と、記憶部３０とを含んで構成される。なお、実施形態２−６においては、図６に示す実施形態１に係るリンク帯域変動量上限計算装置１ａと同様の機能を備える構成は、同一の符号を付し説明を省略する。本実施形態２に係るリンク帯域変動量上限計算装置１ｂと、図６に示したリンク帯域変動量上限計算装置１ａとの違いは、入出力部１０が取得する情報に、誤差処理パラメータ８００がなく、その一方で、処理部２０に誤差処理パラメータ計算部２６が含まれていることである。
【００６７】
誤差処理パラメータ計算部２６は、入力されたリンク帯域ベクトル２００（図３参照）および交流トラヒック経路行列４００（図５参照）を用いて、以下の〔数３〕に示す（式２−２）および（式２−３）を満たす経路変更前の交流トラヒック帯域ベクトルＴ０の解が存在する中で、誤差処理パラメータ８００のうち、最小の誤差処理パラメータαｍｉｎを、所定の探索アルゴリズムにより計算する。そして、誤差処理パラメータ計算部２６は、計算した最小の誤差処理パラメータαｍｉｎを、記憶部３０に記憶する。なお、誤差処理パラメータ計算部２６が実行する探索アルゴリズムは、例えば、二分探索法や、後記する線形計画法、２次計画法等を用いることができる。
【００６８】
そして、リンク帯域変動量上限ベクトル計算部２３は、リンク帯域ベクトル２００からネットワーク内のリンク数を計算し、交流トラヒック経路行列４００から交流トラヒック数を計算し、記憶部３０に記憶されたリンク帯域ベクトル２００、交流トラヒック経路行列４００、経路変更後交流トラヒック経路行列６００、および誤差処理パラメータ計算部２６が計算した最小の誤差処理パラメータαｍｉｎを用いて、以下に示す線形計画法による計算式（式２）を解くことにより、リンク帯域変動量上限ベクトル１０００を生成する。
【００６９】
【数３】
2011166584.tif 000005
【００７０】
（実施形態２のリンク帯域変動量上限計算処理）
次に、リンク帯域変動量上限計算装置１ｂのリンク帯域変動量上限計算処理の流れを説明する。図９は、本実施形態２に係るリンク帯域変動量上限計算処理の流れを示すフローチャートである。
【００７１】
まず、リンク帯域変動量上限計算装置１ｂの情報収集部２１は、入出力部１０を介して、リンク帯域ベクトル２００、交流トラヒック経路行列４００、および経路変更後交流トラヒック経路行列６００を取得し（ステップＳ２０１）、記憶部３０に記憶させる。
【００７２】
次に、リンク帯域変動量上限ベクトル計算部２３は、記憶部３０に記憶されたリンク帯域ベクトル２００から対象となるネットワークのリンク数を計算し、交流トラヒック経路行列４００から対象となるネットワークの交流トラヒック数を計算する（ステップＳ２０２）。
【００７３】
続いて、誤差処理パラメータ計算部２６は、リンク帯域ベクトル２００および交流トラヒック経路行列４００を用いて、誤差処理パラメータ８００のうち、（式２−２）および（式２−３）を満たす最小の誤差処理パラメータαｍｉｎを、所定の探索アルゴリズムにより計算する（ステップＳ２０３）。なお、最小の誤差処理パラメータαｍｉｎの計算処理については、後記において詳細に説明する。
【００７４】
そして、リンク帯域変動量上限ベクトル計算部２３は、ステップＳ２０１で取得した、リンク帯域ベクトル２００、交流トラヒック経路行列４００、および経路変更後交流トラヒック経路行列６００、ステップＳ２０２で計算したリンク数および交流トラヒック数、ならびに、ステップＳ２０３で計算した最小の誤差処理パラメータαｍｉｎを用いて、前記した線形計画法による計算式（式２）を解くことによって、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトル１０００を生成する（ステップＳ２０４）。そして、リンク帯域変動量上限ベクトル計算部２３は、生成したリンク帯域変動量上限ベクトル１０００を記憶部３０に記憶する。
【００７５】
次に、情報出力部２５は、記憶部３０に記憶されたリンク帯域変動量上限ベクトル１０００を、入出力部１０を介して出力する（ステップＳ２０５）。
【００７６】
（最小の誤差処理パラメータαｍｉｎの計算処理）
次に、図９のステップＳ２０３において、誤差処理パラメータ計算部２６が行う最小の誤差処理パラメータαｍｉｎの計算処理の具体例について説明する。ここでは、所定のアルゴリズムとして、線形計画法による計算式を用いて、最小の誤差処理パラメータαｍｉｎを求める方法について説明する。
【００７７】
誤差処理パラメータ計算部２６は、図９のステップＳ２０１で取得した、リンク帯域ベクトル２００および交流トラヒック経路行列４００、そして、ステップＳ２０２で計算したリンク数および交流トラヒック数を用いて、以下に示す線形計画法により計算式（式３）を解くことにより、誤差処理パラメータ８００のうち、最小の誤差処理パラメータαｍｉｎを計算する。
【００７８】
【数４】
2011166584.tif 000006
【００７９】
誤差処理パラメータ計算部２６は、図９のステップＳ２０３において、この線形計画法による計算式（式３）を解くことによって、最小の誤差処理パラメータαｍｉｎを計算する。そして、次のステップＳ２０４において、リンク帯域変動量上限ベクトル計算部２３が、線形計画法による計算式（式２）において、誤差処理パラメータ計算部２６により計算された最小の誤差処理パラメータαｍｉｎを用いて、リンク帯域変動量上限ベクトル１０００を生成する。
【００８０】
このようにすることで、本実施形態２に係るリンク帯域変動量上限計算装置１ｂによれば、誤差処理パラメータ８００が入力されない場合であっても、所定の探索アルゴリズムを用いて、最小の誤差処理パラメータαｍｉｎを算出することができる。そして、最小の誤差処理パラメータαｍｉｎを用いて線形計画法による計算式（式２）を計算することにより、リンク帯域の測定誤差による影響を最も小さくした上で、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトル１０００を生成することができる。そして、各リンクの帯域変動量の上限値は、経路変更後に必要な帯域増設量の最小値となるため、リンク帯域設計において、実際に必要な帯域増設量からの余剰帯域、つまり無駄となる帯域設計量を低減することが可能となる。
【００８１】
＜実施形態２の変形例＞
次に、本実施形態２に係るリンク帯域変動量上限計算装置１ｂの変形例について説明する。本実施形態２に係るリンク帯域変動量上限計算装置１ｂと、リンク帯域変動量上限計算装置１ｂの変形例との違いは、誤差処理パラメータ計算部２６が用いる探索アルゴリズムについて、線形計画法による計算式（式３）の代わりに、以下に示す２次計画法による計算式（式４）を用いることである。そして、リンク帯域変動量上限ベクトル計算部２３が、線形計画法による計算式（式２）の代わりに、以下に示す線形計画法による計算式（式５）を用いて、リンク帯域変動量上限ベクトル１０００を生成する。なお、この変形例の構成および処理手順は、図８に示したリンク帯域変動量上限計算装置１ｂの構成、および、図９に示したリンク帯域変動量上限計算処理の流れと同様であるので記載を省略する。
【００８２】
図９のステップＳ２０３において、誤差処理パラメータ計算部２６は、誤差処理パラメータ８００をベクトル表示した誤差処理パラメータベクトルεを用いて、以下に示す２次計画法による計算式（式４）を解くことにより、誤差処理パラメータベクトルεのうち、｜ε｜２を最小化させる誤差処理パラメータベクトルεｍｉｎを計算する。
【００８３】
【数５】
2011166584.tif 000007
【００８４】
そして、リンク帯域変動量上限ベクトル計算部２３は、図９のステップＳ２０４において、線形計画法による計算式（式２）の代わりに、以下に示す線形計画法による計算式（式５）において、誤差処理パラメータ計算部２６により計算された誤差処理パラメータベクトルεｍｉｎを用いて、リンク帯域変動量上限ベクトル１０００を生成する。
【００８５】
【数６】
2011166584.tif 000008
【００８６】
このようにすることで、本実施形態２に係るリンク帯域変動量上限計算装置１ｂの変形例によれば、誤差処理パラメータ８００が入力されない場合であっても、２次計画法による計算式（式４）を用いて、誤差処理パラメータベクトルεｍｉｎを算出し、線形計画法による計算式（式５）を用いて、リンク帯域変動量上限ベクトル１０００を生成することができる。
【００８７】
≪実施形態３≫
次に、本実施形態３に係るリンク帯域変動量上限計算装置１（１ｃ）について説明する。本実施形態３に係るリンク帯域変動量上限計算装置１（１ｃ）は、入力情報として、ノードやリンクに発生した障害箇所を示す障害発生箇所情報３００と誤差処理パラメータ８００とを取得して、障害発生により各交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値を求めることを特徴とする。つまり、実施形態１に係る経路変更後交流トラヒック経路行列６００（図６参照）の入力を必要とせず、各リンクの帯域変動量の上限値を求めることができるものである。
【００８８】
（実施形態３のリンク帯域変動量上限計算装置の構成）
図１０は、本実施形態３に係るリンク帯域変動量上限計算装置１（１ｃ）の構成例を示す機能ブロック図である。図１０に示すように、リンク帯域変動量上限計算装置１ｃは、図６に示したリンク帯域変動量上限計算装置１ａと同様に、入出力部１０と、処理部２０と、記憶部３０とを含んで構成される。
【００８９】
本実施形態３に係る入出力部１０は、例えば、ネットワークに設けられたネットワーク管理装置（不図示）から、トポロジ情報１００（図２参照）と、リンク帯域ベクトル２００（図３参照）と、ネットワーク内での障害が発生した箇所を示す障害発生箇所情報３００と、誤差処理パラメータ８００とを取得する。そして、情報収集部２１は、入出力部１０が取得したこれらの情報を記憶部３０に記憶する。
【００９０】
ここで、障害発生箇所情報３００は、障害が発生したネットワーク上の箇所を示す情報である。障害には、ノードに発生するノード障害と、リンクに発生するリンク障害があり、この障害発生箇所情報３００には、どのノードに障害が発生したかを示すノード障害箇所表示ベクトルと、どのリンクに障害が発生したかを示すリンク障害箇所表示ベクトルが含まれる。
【００９１】
図１１は、本実施形態３に係る障害発生箇所情報３００のデータ構造の一例を説明するための図である。図１１（ａ）に示すように、例えば、リンク＃１とリンク＃６とに障害が発生した場合（ノードには障害の発生なしの場合）には、ノード障害箇所表示ベクトル（図１１（ｂ）参照）は、各ノードに障害が発生していないことを示す「０」が入力され、障害が発生したことを示す「１」は入力されない。一方、リンク障害箇所表示ベクトル（図１１（ｃ）参照）には、障害が発生したリンク＃１とリンク＃６には、「１」が入力され、その他の障害が発生していないリンクには「０」が入力される。このようにして、ノードもしくはリンクのどの箇所に障害が発生したのかを示すことができる。
【００９２】
図１０に戻り、本実施形態３に係る処理部２０は、図６に示すリンク帯域変動量上限計算装置１ａの処理部２０の構成に加え、交流トラヒック経路行列計算部２２を備えている。
【００９３】
この交流トラヒック経路行列計算部２２は、記憶部３０内に記憶されたトポロジ情報１００から各交流トラヒックの経路を示す交流トラヒック経路行列４００（図５参照）を生成する。この経路情報の算出処理は、例えば、ＯＳＰＦ（Open Shortest Path First）であれば、ダイクストラ法を用いて算出される。また、交流トラヒック経路行列計算部２２は、トポロジ情報１００と障害発生箇所情報３００とを用いて、障害が発生したノードやリンクを経由しない経路情報として、障害発生後の迂回経路を示す障害発生後交流トラヒック経路行列５００を生成する。そして、交流トラヒック経路行列計算部２２は、生成した交流トラヒック経路行列４００と障害発生後交流トラヒック経路行列５００とを記憶部３０に記憶する。
【００９４】
リンク帯域変動量上限ベクトル計算部２３は、リンク数と、交流トラヒック数と、リンク帯域ベクトル２００と、交流トラヒック経路行列４００と、障害発生後交流トラヒック経路行列５００と、誤差処理パラメータ８００とを用いて以下に示す線形計画法の計算式（式１ａ）を用いて、障害発生により各交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトル１０００を生成する。そして、リンク帯域変動量上限ベクトル計算部２３は、生成したリンク帯域変動量上限ベクトル１０００を記憶部３０に記憶する。
【００９５】
なお、ここで、リンク帯域変動量上限ベクトル計算部２３は、リンク数Ｌを記憶部３０に記憶されたリンク帯域ベクトル２００から計算する。また、リンク帯域変動量上限ベクトル計算部２３は、トポロジ情報１００により示されるノード数がｎのとき、交流トラヒック数Ｔを、Ｔ＝ｎ（ｎ−１）の計算式により算出する。
【００９６】
そして、リンク帯域変動量上限ベクトル計算部２３は、以下に示す線形計画法による計算式（式１ａ）を用いて、リンク帯域変動量上限ベクトル１０００を生成する。
【００９７】
【数７】
2011166584.tif 000009
【００９８】
なお、〔数２〕で示した（式１）と、この〔数７〕で示す（式１ａ）の線形計画法による計算式とは、基本的に同一の計算式であるが、（式１）において交流トラヒック経路行列Ａ１は、予め設定された経路変更後交流トラヒック経路行列６００を表し、（式１ａ）における交流トラヒック経路行列Ａ１は、交流トラヒック経路行列計算部２２が生成した障害発生後交流トラヒック経路行列５００を表す。
【００９９】
このリンク帯域変動量上限ベクトル計算部２３の計算により、障害発生後の各リンクごとの帯域変動量の上限値を示す、リンク帯域変動量上限ベクトルＸｓ＝（ｘｓ０，ｘｓ１，…，ｘｓＬ−１）ｔｒが求められる。
【０１００】
（実施形態３のリンク帯域変動量上限計算処理）
次に、リンク帯域変動量上限計算装置１ｃのリンク帯域変動量上限計算処理の流れを説明する。図１２は、本実施形態３に係るリンク帯域変動量上限計算処理の流れを示すフローチャートである。
【０１０１】
まず、リンク帯域変動量上限計算装置１ｃの情報収集部２１は、入出力部１０を介して、トポロジ情報１００、リンク帯域ベクトル２００、障害発生箇所情報３００、および誤差処理パラメータ８００を取得し（ステップＳ３０１）、記憶部３０に記憶させる。
【０１０２】
次に、交流トラヒック経路行列計算部２２は、記憶部３０に記憶されたトポロジ情報１００を用いて、交流トラヒック経路行列４００を生成する（ステップＳ３０２）。
【０１０３】
続いて、交流トラヒック経路行列計算部２２は、トポロジ情報１００と障害発生箇所情報３００とを用いて、障害発生後交流トラヒック経路行列５００を生成する（ステップＳ３０３）。
【０１０４】
そして、リンク帯域変動量上限ベクトル計算部２３は、記憶部３０に記憶されたリンク帯域ベクトル２００を用いて、対象となるネットワークのリンク数を計算し、同じく記憶部３０に記憶されたトポロジ情報１００に示されるノード数から交流トラヒック数を計算する（ステップＳ３０４）。
【０１０５】
次に、リンク帯域変動量上限ベクトル計算部２３は、ステップＳ３０４で計算したリンク数および交流トラヒック数と、ステップＳ３０１で記憶部３０に記憶したリンク帯域ベクトル２００および誤差処理パラメータ８００と、ステップＳ３０２で生成した交流トラヒック経路行列４００と、ステップＳ３０３で生成した障害発生後交流トラヒック経路行列５００とを用いて、前記した線形計画法による計算式（式１ａ）を解くことによって、障害発生により各交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトル１０００を生成する（ステップＳ３０５）。そして、リンク帯域変動量上限ベクトル計算部２３は、生成したリンク帯域変動量上限ベクトル１０００を記憶部３０に記憶する。
【０１０６】
続いて、情報出力部２５は、記憶部３０に記憶されたリンク帯域変動量上限ベクトル１０００を、入出力部１０を介して出力する（ステップＳ３０６）。
【０１０７】
このようにすることで、本実施形態３に係るリンク帯域変動量上限計算装置１ｃによれば、予めネットワーク設計者が設定した誤差処理パラメータ８００と障害発生箇所情報３００とを用いて、リンク帯域の測定に測定誤差が存在する場合であっても、障害発生により交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値を求めることができる。つまり、実施形態１に係るリンク帯域変動量上限計算装置１ａのように、経路変更後の交流トラヒック経路行列を取得することなく、各リンクの帯域変動量の上限値を求めることができる。
【０１０８】
なお、リンク帯域変動量上限計算装置１ｃは、ネットワーク設計者により入力される誤差処理パラメータαが、線形計画法による計算式（式１−２）および（式１−３）を満たす解が存在しない値である場合、線形計画法による計算式（式１ａ）によりリンク帯域変動量上限ベクトルを生成できないため、空集合ベクトルを生成する。そして、リンク帯域変動量上限計算装置１ｃが、空集合ベクトルを入出力部１０を介して出力することで、入力された誤差処理パラメータ８００が不適当な値であることをネットワーク設計者に対して示し、誤差処理パラメータ８００の変更を促すことができる。
【０１０９】
≪実施形態４≫
次に、本実施形態４に係るリンク帯域変動量上限計算装置１（１ｄ）について説明する。本実施形態４に係るリンク帯域変動量上限計算装置１（１ｄ）は、実施形態３において入力された誤差処理パラメータ８００を取得せず、所定の探索アルゴリズムにより、誤差処理パラメータ８００のうちの最小の誤差処理パラメータαｍｉｎを計算して、リンク帯域変動量上限ベクトルを生成することを特徴とする。
【０１１０】
図１３は、本実施形態４に係るリンク帯域変動量上限計算装置１（１ｄ）の構成例を示す機能ブロック図である。図１３に示すように、リンク帯域変動量上限計算装置１ｄは、図１０に示したリンク帯域変動量上限計算装置１ｃと同様に、入出力部１０と、処理部２０と、記憶部３０とを含んで構成される。本実施形態４に係るリンク帯域変動量上限計算装置１ｄと、図１０に示したリンク帯域変動量上限計算装置１ｃとの違いは、入出力部１０が取得する情報に、誤差処理パラメータ８００がなく、その一方で、処理部２０に誤差処理パラメータ計算部２６が含まれていることである。
【０１１１】
誤差処理パラメータ計算部２６は、入力されたリンク帯域ベクトル２００および交流トラヒック経路行列計算部２２により生成された交流トラヒック経路行列４００を用いて、以下の〔数８〕に示す（式２−２）および（式２−３）を満たす経路変更前の交流トラヒック帯域ベクトルＴ０の解が存在する中で、誤差処理パラメータ８００のうち、最小の誤差処理パラメータαｍｉｎを、所定の探索アルゴリズムにより計算する。なお、誤差処理パラメータ計算部２６が実行する探索アルゴリズムは、例えば、二分探索法や、後記する線形計画法、２次計画法等を用いることができる。
【０１１２】
交流トラヒック経路行列計算部２２は、交流トラヒック経路行列４００および障害発生後交流トラヒック経路行列５００を生成する。そして、リンク帯域変動量上限ベクトル計算部２３は、リンク数と、交流トラヒック数と、リンク帯域ベクトル２００と、交流トラヒック経路行列４００と、障害発生後交流トラヒック経路行列５００と、誤差処理パラメータ計算部２６が計算した最小の誤差処理パラメータαｍｉｎとを用いて、以下に示す線形計画法による計算式（式２ａ）を解くことにより、リンク帯域変動量上限ベクトル１０００を生成する。
【０１１３】
【数８】
2011166584.tif 000010
【０１１４】
このようにすることで、本実施形態４に係るリンク帯域変動量上限計算装置１ｄによれば、誤差処理パラメータ８００が入力されない場合であっても、所定の探索アルゴリズムを用いて、最小の誤差処理パラメータαｍｉｎを算出することができる。そして、最小の誤差処理パラメータαｍｉｎを用いて線形計画法による計算式（式２ａ）を計算することにより、リンク帯域の測定誤差による影響を最も小さくした上で、障害発生により交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値を求めることができる。つまり、実施形態３に係るリンク帯域変動量上限計算装置１ｃのように、誤差処理パラメータ８００を取得することなく、各リンクの帯域変動量の上限値を求めることができる。
【０１１５】
ここで、誤差処理パラメータ計算部２６は、最小の誤差処理パラメータαｍｉｎの計算処理を、前記した〔数４〕に示す線形計画法による計算式（式３）により求めるようにしてもよい。
【０１１６】
また、実施形態４の変形例として、誤差処理パラメータ計算部２６が用いる探索アルゴリズムについて、線形計画法による計算式（式３）の代わりに、前記した〔数５〕に示す２次計画法による計算式（式４）を用いるようにしてもよい。この場合、誤差処理パラメータ計算部２６は、誤差処理パラメータ８００をベクトル表示した誤差処理パラメータベクトルεを用いて、２次計画法による計算式（式４）を解くことにより、誤差処理パラメータベクトルεのうち、｜ε｜２を最小化させる誤差処理パラメータベクトルεｍｉｎを計算する。
【０１１７】
そして、リンク帯域変動量上限ベクトル計算部２３が、線形計画法による計算式（式２ａ）の代わりに、以下に示す線形計画法による計算式（式５ａ）を用いて、リンク帯域変動量上限ベクトル１０００を生成する。
【０１１８】
【数９】
2011166584.tif 000011
【０１１９】
なお、〔数６〕で示した（式５）と、この〔数９〕で示す（式５ａ）の線形計画法による計算式とは、基本的に同一の計算式であるが、（式５）において交流トラヒック経路行列Ａ１は、予め設定された経路変更後交流トラヒック経路行列６００を表し、（式５ａ）における交流トラヒック経路行列Ａ１は、交流トラヒック経路行列計算部２２が生成した障害発生後交流トラヒック経路行列５００を表す。
【０１２０】
このようにすることで、本実施形態４に係るリンク帯域変動量上限計算装置１ｄによれば、誤差処理パラメータ８００が入力されない場合であっても、２次計画法による計算式（式４）を用いて、誤差処理パラメータベクトルεｍｉｎを算出し、線形計画法による計算式（式５ａ）を用いて、リンク帯域変動量上限ベクトル１０００を生成することができる。
【０１２１】
≪実施形態５≫
次に、本実施形態５に係るリンク帯域変動量上限計算装置１（１ｅ）について説明する。本実施形態５に係るリンク帯域変動量上限計算装置１（１ｅ）は、実施形態３において入力された障害発生箇所情報３００（図１１参照）を取得せず、その代わりに、ノードやリンクにおいて発生する障害の障害発生パターンを制約する障害発生パターン制約情報７００を取得し、その障害発生パターン制約情報７００の制約に基づく障害発生パターンごとに、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値を求めることを特徴とする。
【０１２２】
図１４は、本実施形態５に係るリンク帯域変動量上限計算装置１（１ｅ）の構成例を示す機能ブロック図である。図１４に示すように、リンク帯域変動量上限計算装置１ｅと、図１０に示した実施形態３に係るリンク帯域変動量上限計算装置１ｃとの違いは、入出力部１０が取得する情報に、障害発生箇所情報３００がなく、その一方で、障害発生パターン制約情報７００が含まれることである。このため、記憶部３０内に、障害発生箇所情報３００が記憶されておらず、その代わり、障害発生パターン制約情報７００が記憶される。本実施形態５に係るリンク帯域変動量上限計算装置１ｅは、入出力部１０が取得した障害発生パターン制約情報７００と誤差処理パラメータ８００とを用いて、障害発生パターン制約情報７００の制約条件に合致する障害発生パターンについて、リンク帯域変動量上限計算処理を実行する。
【０１２３】
ここで、障害発生パターン制約情報７００とは、ノードに発生する障害（ノード障害）と、リンクに発生する障害（リンク障害）とについて、各ノードまたは各リンクに発生する障害箇所が１箇所である場合には単障害とし、各ノードまたは各リンクに発生する障害箇所が２箇所である場合には二重障害、以下三重障害等、とするものである。そして、ノード障害とリンク障害の少なくとも１つの障害発生パターンを設定することで、ネットワークに発生する障害発生パターンを制約する情報である。
【０１２４】
この障害発生パターン制約情報７００は、例えば、
・リンク単障害のみの場合：「０」
・ノード単障害のみの場合：「１」
・リンク単障害とノード単障害による二重障害の場合：「２」
・リンク二重障害のみの場合：「３」
・ノード二重障害のみの場合：「４」
というように、予め設定された制約情報を示す。
【０１２５】
そして、本実施形態５に係る交流トラヒック経路行列計算部２２は、記憶部３０に記憶されたトポロジ情報１００および障害発生パターン制約情報７００を用いて、障害発生パターン制約情報７００の制約に基づく障害発生パターンごとに、その障害発生後の各障害発生後交流トラヒック経路行列５００を生成する。
【０１２６】
また、リンク帯域変動量上限ベクトル計算部２３は、リンク数と、交流トラヒック数と、リンク帯域ベクトル２００と、交流トラヒック経路行列４００と、障害発生パターン制約情報７００の制約に基づく障害発生パターンごとに生成された各障害発生後交流トラヒック経路行列５００と、誤差処理パラメータ８００とを用いて、〔数７〕に示した線形計画法による計算式（式１ａ）を解く。そして、リンク帯域変動量上限ベクトル計算部２３は、障害発生パターン制約情報７００の制約に基づく障害発生パターンについて、障害発生により各交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトル１０００を生成する。
【０１２７】
このようにすることで、本実施形態５に係るリンク帯域変動量上限計算装置１ｅによれば、予めネットワーク設計者が設定した誤差処理パラメータ８００と障害発生パターン制約情報７００とを用いて、リンク帯域の測定に測定誤差が存在する場合であっても、障害発生パターン制約情報７００の制約に基づく障害発生パターンごとに、障害発生後の交流トラヒックの経路変更による各リンク帯域の変動量の上限値を求めることができる。
【０１２８】
≪実施形態６≫
次に、本実施形態６に係るリンク帯域変動量上限計算装置１（１ｆ）について説明する。本実施形態６に係るリンク帯域変動量上限計算装置１（１ｆ）は、実施形態５において入力された誤差処理パラメータ８００を取得せず、所定の探索アルゴリズムにより、誤差処理パラメータ８００のうちの最小の誤差処理パラメータαｍｉｎを計算して、障害発生パターン制約情報７００の制約に基づく障害発生パターンごとに、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値を求めることを特徴とする。
【０１２９】
図１５は、本実施形態６に係るリンク帯域変動量上限計算装置１（１ｆ）の構成例を示す機能ブロック図である。図１５に示すように、リンク帯域変動量上限計算装置１ｆは、図１４に示したリンク帯域変動量上限計算装置１ｅと同様に、入出力部１０と、処理部２０と、記憶部３０とを含んで構成される。本実施形態６に係るリンク帯域変動量上限計算装置１ｆと、図１４に示したリンク帯域変動量上限計算装置１ｅとの違いは、入出力部１０が取得する情報に、誤差処理パラメータ８００がなく、その一方で、処理部２０に誤差処理パラメータ計算部２６が含まれていることである。本実施形態６に係るリンク帯域変動量上限計算装置１ｆは、入出力部１０が取得した障害発生パターン制約情報７００と、誤差処理パラメータ計算部２６が計算した最小の誤差処理パラメータαｍｉｎとを用いて、障害発生パターン制約情報７００の制約条件に合致する障害発生パターンについて、リンク帯域変動量上限計算処理を実行する。
【０１３０】
誤差処理パラメータ計算部２６は、入力されたリンク帯域ベクトル２００および交流トラヒック経路行列計算部２２により生成された交流トラヒック経路行列４００を用いて、前記した〔数８〕示す（式２−２）および（式２−３）を満たす経路変更前の交流トラヒック帯域ベクトルＴ０の解が存在する中で、誤差処理パラメータ８００のうち、最小の誤差処理パラメータαｍｉｎを、所定の探索アルゴリズムにより計算する。
【０１３１】
交流トラヒック経路行列計算部２２は、記憶部３０に記憶されたトポロジ情報１００および障害発生パターン制約情報７００を用いて、障害発生パターン制約情報７００の制約に基づく障害発生パターンごとに、その障害発生後の各障害発生後交流トラヒック経路行列５００を生成する。
【０１３２】
そして、リンク帯域変動量上限ベクトル計算部２３は、リンク数と、交流トラヒック数と、リンク帯域ベクトル２００と、交流トラヒック経路行列４００と、障害発生後交流トラヒック経路行列５００と、誤差処理パラメータ計算部２６が計算した最小の誤差処理パラメータαｍｉｎとを用いて、前記した〔数８〕に示す線形計画法による計算式（式２ａ）を解く。そして、リンク帯域変動量上限ベクトル計算部２３は、障害発生パターン制約情報７００の制約に基づく障害発生パターンについて、障害発生により各交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値であるリンク帯域変動量上限ベクトル１０００を生成する。
【０１３３】
このようにすることで、本実施形態６に係るリンク帯域変動量上限計算装置１ｆによれば、誤差処理パラメータ８００が入力されない場合であっても、所定の探索アルゴリズムを用いて、最小の誤差処理パラメータαｍｉｎを算出することができる。また、最小の誤差処理パラメータαｍｉｎを用いて（式２ａ）を計算することにより、リンク帯域の測定誤差による影響を最も小さくした上で、障害発生パターン制約情報７００の制約に基づく障害発生パターンごとに、交流トラヒックの経路が変更されたときの各リンクの帯域変動量の上限値を求めることができる。
【０１３４】
ここで、誤差処理パラメータ計算部２６は、最小の誤差処理パラメータαｍｉｎの計算処理を、前記した〔数４〕に示す線形計画法による計算式（式３）により求めるようにしてもよい。
【０１３５】
また、実施形態６の変形例として、誤差処理パラメータ計算部２６が用いる探索アルゴリズムについて、線形計画法による計算式（式３）の代わりに、前記した〔数５〕に示す２次計画法による計算式（式４）を用いて、誤差処理パラメータベクトルεのうち、｜ε｜２を最小化させる誤差処理パラメータベクトルεｍｉｎを計算するようにしてもよい。そして、リンク帯域変動量上限ベクトル計算部２３が、前記した〔数９〕に示す線形計画法による計算式（式５ａ）を用いて、リンク帯域変動量上限ベクトル１０００を生成する。
【０１３６】
このようにすることで、本実施形態６に係るリンク帯域変動量上限計算装置１ｆによれば、誤差処理パラメータ８００が入力されない場合であっても、２次計画法による計算式（式４）を用いて、誤差処理パラメータベクトルεｍｉｎを算出し、線形計画法による計算式（式５ａ）を用いて、障害発生パターン制約情報７００の制約に基づく障害発生パターンごとに、障害発生後の交流トラヒックの経路変更による各リンク帯域の変動量の上限値を求めることができる。
【０１３７】
以上のように、本発明に係るリンク帯域変動量上限計算装置、リンク帯域変動量上限計算方法およびプログラムによれば、リンクの帯域測定に測定誤差が存在する場合であっても、経路変更による各リンク帯域の増設量を低減するリンク帯域設計を行うことができる。
【符号の説明】
【０１３８】
１      リンク帯域変動量上限計算装置
１０    入出力部
２０    処理部
２１    情報収集部
２２    交流トラヒック経路行列計算部
２３    リンク帯域変動量上限ベクトル計算部
２５    情報出力部
２６    誤差処理パラメータ計算部
３０    記憶部
１００  トポロジ情報
２００  リンク帯域ベクトル
３００  障害発生箇所情報
４００  交流トラヒック経路行列
５００  障害発生後交流トラヒック経路行列
６００  経路変更後交流トラヒック経路行列
７００  障害発生パターン制約情報
８００  誤差処理パラメータ
１０００  リンク帯域変動量上限ベクトル
【図１】
2011166584.tif 000026
【図２】
2011166584.tif 000027
【図３】
2011166584.tif 000028
【図４】
2011166584.tif 000029
【図５】
2011166584.tif 000030
【図６】
2011166584.tif 000031
【図７】
2011166584.tif 000032
【図８】
2011166584.tif 000033
【図９】
2011166584.tif 000034
【図１０】
2011166584.tif 000035
【図１１】
2011166584.tif 000036
【図１２】
2011166584.tif 000037
【図１３】
2011166584.tif 000038
【図１４】
2011166584.tif 000039
【図１５】
2011166584.tif 000040
【図１６】
2011166584.tif 000041