(57)【特許請求の範囲】
【請求項１】
通信網上において、単数、または、複数のソースノードと宛先ノードの間でトラヒック要求が発生する場合において、障害が発生しない通常時には「現用パス」として予め設定されたパス、現用パス上に障害が発生した時には「迂回用パス」として予め設定されたパスを選定する状況において、ノードペア間のトラヒック測定による帯域削減効果を評価する帯域削減効果評価装置における帯域削減効果評価方法であって、
障害が発生せず、現用パスが選択されており、全通信ノードペア間を流れるトラヒックが、通信網における通信リンクを流れるトラヒック量として観測されている場合に、そのトラヒック観測を行っている通信リンクで観測されるトラヒック量及び現用パス、迂回用パスの経路情報を取得するデータ取得ステップと、
前記通信網を有向グラフと見做して、前記トラヒック量及び前記経路情報を用いて最大流問題を解くことにより、通信リンクにおいて必要となる迂回用パスの帯域上限値を求める帯域上限値算出ステップと、
前記帯域上限値及び一定の危険率αの下で迂回用パスに必要な通信リンクでの必要帯域を算出する必要帯域算出ステップと、
前記帯域上限値と前記必要帯域の差分を求め、前記ノードペア間のトラヒック情報を入手したときに削減できる帯域とする差分算出ステップと、
を有することを特徴とする帯域削減効果評価方法。
【請求項２】
前記帯域上限値算出ステップにおいて、
リンクaを疎通する迂回用パスのトラヒックの絶対安全側の帯域Caを、対応する現用パスのトラヒックの総和を最大化するようにして最大流問題を解くことにより求めるステップと、
現用パスのトラヒックの分布関数を重力モデルから求めるステップと、
ノードペア間のトラヒック情報が分かっているときの前記リンクaを疎通する現用パスの上限値c1(a)を、対応する現用パスのトラヒックの総和計算から求めるステップと、
を含み、
前記必要帯域算出ステップにおいて、
前記危険率αの下でのノードペア間のトラヒック情報が分かっているときの当該リンクを疎通する安全側の迂回用パスのトラヒックc2(a)を、対応する現用パスのトラヒックのたたみこみ計算から求めるステップと、
前記リンクaにおける実測現用トラヒック上限値をtrafsup(a)とし、該リンクaにおける危険率αの下でのノードペア間のトラヒック情報が分かっているときの迂回用パス必要帯域Maをc2(a)/c1(a)*trafsup(a)とするステップと、
を含み、
前記差分算出ステップにおいて、
前記リンクaを疎通する迂回用パスのトラヒックの絶対安全側の帯域（Ca）と前記迂回用パス必要帯域（Ma）の差分を、測定装置によってトラヒック情報が得られたときのリンクaにおける削減帯域とするステップを含む
請求項１記載の帯域削減効果評価方法。
【請求項３】
前記帯域上限値算出ステップにおいて、
通信リンクbが故障したときに通信リンクaを疎通する迂回用パスのトラヒックの絶対安全側の帯域C’abを、対応する現用パスのトラヒックの総和を最大化するようにして最大流問題を解いて求めるステップと、
前記通信リンクbを変化させたときの前記絶対安全側の帯域C’abの最大値C’aを前記通信リンクaを疎通する迂回用パスのトラヒックの絶対安全側の帯域とするステップと、
現用パスのトラヒックの分布関数を重力モデルから求めるステップと、
ノードペア間のトラヒック情報が分かっているときの当該リンクaを疎通する現用パスの上限値c1(a)を、対応する現用パスのトラヒックの総和計算から求めるステップと、
を含み、
前記必要帯域算出ステップにおいて、
前記危険率αの下でのノードペア間のトラヒック情報が分かっているときの通信リンクbが故障したときの当該リンクaを疎通する安全側の迂回用パスのトラヒックc3(a、b)を、対応する現用パスのトラヒックのたたみこみ計算から求めるステップと、
前記通信リンクbを変化させたときのc3(a、b)の最大値c4(a)を、前記危険率αの下でのノードペア間のトラヒック情報が分かっているときの迂回用パスの通信リンクaにおける安全側の帯域とするステップと、
前記通信リンクaにおける実測現用トラヒック上限値をtrafsup(a)とし、該通信リンクaにおける危険率αの下でのノードペア間のトラヒック情報が分かっているときの迂回用パス必要帯域M’aをc4(a)/c1(a)*trafsup(a)とするステップと、
を含み、
前記差分算出ステップにおいて、
前記通信リンクaを疎通する迂回用パスのトラヒックの絶対安全側の帯域（C’a）と前記迂回用パス必要帯域（M’a）の差分を測定装置によってトラヒック情報が得られたときの前記通信リンクaにおける削減帯域とするステップを含む
請求項１記載の帯域削減効果評価方法。
【請求項４】
通信網上において、単数、または、複数のソースノードと宛先ノードの間でトラヒック要求が発生する場合において、障害が発生しない通常時には「現用パス」として予め設定されたパス、現用パス上に障害が発生した時には「迂回用パス」として予め設定されたパスを選定する状況において、ノードペア間のトラヒック測定による帯域削減効果を評価する帯域削減効果評価装置であって、
障害が発生せず、現用パスが選択されており、全通信ノードペア間を流れるトラヒックが、通信網における通信リンクを流れるトラヒック量として観測されている場合に、そのトラヒック観測を行っている通信リンクで観測されるトラヒック量及び現用パス、迂回用パスの経路情報を取得し、それぞれトラヒック情報記憶手段、パス情報記憶手段に格納するデータ取得手段と、
前記通信網を有向グラフと見做して、前記トラヒック情報記憶手段及び前記パス情報記憶手段の前記トラヒック量及び前記経路情報を用いて最大流問題を解くことにより、通信リンクにおいて必要となる迂回用パスの帯域上限値を求める帯域上限値算出手段と、
前記帯域上限値及び一定の危険率αの下で迂回用パスに必要な通信リンクでの必要帯域を算出する必要帯域算出手段と、
前記帯域上限値と前記必要帯域の差分を求め、前記ノードペア間のトラヒック情報を入手したときに削減できる帯域とする差分算出手段と、
を有することを特徴とする帯域削減効果評価装置。
【請求項５】
前記帯域上限値算出手段は、
リンクaを疎通する迂回用パスのトラヒックの絶対安全側の帯域Caを、対応する現用パスのトラヒックの総和を最大化するようにして最大流問題を解くことにより求める手段と、
現用パスのトラヒックの分布関数を重力モデルから求める手段と、
ノードペア間のトラヒック情報が分かっているときの前記リンクaを疎通する現用パスの上限値c1(a)を、対応する現用パスのトラヒックの総和計算から求める手段と、
を含み、
前記必要帯域算出手段は、
前記危険率αの下でのノードペア間のトラヒック情報が分かっているときの当該リンクを疎通する安全側の迂回用パスのトラヒックc2(a)を、対応する現用パスのトラヒックのたたみこみ計算から求める手段と、
前記リンクaにおける実測現用トラヒック上限値をtrafsup(a)とし、該リンクaにおける危険率αの下でのノードペア間のトラヒック情報が分かっているときの迂回用パス必要帯域Maをc2(a)/c1(a)*trafsup(a)とする手段と、
を含み、
前記差分算出手段は、
前記リンクaを疎通する迂回用パスのトラヒックの絶対安全側の帯域（Ca）と前記迂回用パス必要帯域（Ma）の差分を、測定装置によってトラヒック情報が得られたときのリンクaにおける削減帯域とする手段を含む
請求項４記載の帯域削減効果評価装置。
【請求項６】
前記帯域上限値算出手段は、
通信リンクbが故障したときに通信リンクaを疎通する迂回用パスのトラヒックの絶対安全側の帯域C’abを、対応する現用パスのトラヒックの総和を最大化するようにして最大流問題を解いて求める手段と、
前記通信リンクbを変化させたときの前記絶対安全側の帯域C’abの最大値C’aを前記通信リンクaを疎通する迂回用パスのトラヒックの絶対安全側の帯域とする手段と、
現用パスのトラヒックの分布関数を重力モデルから求める手段と、
ノードペア間のトラヒック情報が分かっているときの当該リンクaを疎通する現用パスの上限値c1(a)を、対応する現用パスのトラヒックの総和計算から求める手段と、
を含み、
前記必要帯域算出手段は、
前記危険率αの下でのノードペア間のトラヒック情報が分かっているときの通信リンクbが故障したときの当該リンクaを疎通する安全側の迂回用パスのトラヒックc3(a、b)を、対応する現用パスのトラヒックのたたみこみ計算から求める手段と、
前記通信リンクbを変化させたときのc3(a、b)の最大値c4(a)を、前記危険率αの下でのノードペア間のトラヒック情報が分かっているときの迂回用パスの通信リンクaにおける安全側の帯域とする手段と、
前記通信リンクaにおける実測現用トラヒック上限値をtrafsup(a)とし、該通信リンクaにおける危険率αの下でのノードペア間のトラヒック情報が分かっているときの迂回用パス必要帯域M’aをc4(a)/c1(a)*trafsup(a)とする手段と、
を含み、
前記差分算出手段は、
前記通信リンクaを疎通する迂回用パスのトラヒックの絶対安全側の帯域（C’a）と前記迂回用パス必要帯域（M’a）の差分を測定装置によってトラヒック情報が得られたときの前記通信リンクaにおける削減帯域とする手段を含む
請求項４記載の帯域削減効果評価装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、削減帯域算出装置及び方法及び帯域削減効果評価装置及び方法に係り、特に、障害がなく現用パスが選択され通信リンクを流れるトラヒックが観測されている状況において、障害時に選択される迂回用パスに必要な通信リンクでの帯域上限値と一定の危険率の下での必要帯域量との差分から、ノードペア間のトラヒック測定装置による帯域削減効果を評価するための削減帯域算出装置及び方法及び帯域削減効果評価装置及び方法に関する。
【背景技術】
【０００２】
迂回用パスに必要な帯域上限値を算出するものとして、通信リンクを流れるトラヒックや端点ノードにおける流出入トラヒックの観測データを制約式に組み込み、通信リンクを流れる迂回用パスに必要な帯域を線形計画法によって最大化する帯域算出手法がConstraint Programmingとして考案された(例えば、非特許文献1参照)。この手法は、迂回用パスに必要な通信リンクでの帯域上限値を導出する目的としては、理想的な結果を算出するが、shared protection制約の下で適用しようとすると、各故障通信リンク毎に、それぞれ大規模な線形計画法を繰り返し解かなければならず計算時間がかかるという問題があった(例えば、特許文献1参照)。
【０００３】
この計算時間を削減するために、この線形計画法を最大流問題として解くことにより、抜本的な高速化を図る方法も提案されている。当該方法は、最大流問題によって帯域上限値を算出するために、通信網に仮の送信元ノードｓ及び仮の宛先ノードｄを追加する。仮の送信元ノードｓ及び仮の宛先ノードｄを通信網の各通信リンクに接続した仮の通信網において、リンクａに障害が発生した場合に、仮の送信元ノードｓから出る最大の流量φを算出する。そして、障害想定リンクａを変化させて、トラヒックの最大値を求めることで、設計対象リンクｂの迂回用パスで必要となる帯域上限値が求められる。
【０００４】
以上は絶対安全側の帯域算出法であるが、限られたトラヒック情報の下で、一定の危険率の下では、迂回用パスにどの程度の帯域が必要になるかという問題は、トラヒックモデルを仮定しその下で解くことによって近似的にではあるが解決できる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】H. Simonis, "Constraint Based Resilience Analysis", LNCS Vol. 4204,16-28, 2006.
【特許文献】
【０００６】
【特許文献１】特開2011-172035号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記の手法において、一定の危険率の下での安全側帯域をあるトラヒックモデルの下で評価した値と、トラヒックモデルを仮定しないで求めた絶対安全側の帯域を比較し、その差分から、いったん測定装置によって完全なトラヒック情報が分かったときに、必要帯域は一定の危険率の下にどの程度まで削減できるようになるのかを事前に把握するという検討は未検討であった。
【０００８】
本発明は、上記の点に鑑みなされたもので、通信網においてトラヒックを転送する現用パス・迂回用パスの情報が与えられており、障害がなく現用パスを流れるトラヒックが、通信リンクにおいて観測されているが、個々のソース・宛先ノードペアに流れるトラヒックが分からない状況において、障害時に選択される迂回用パスに必要な通信リンクでの帯域上限値と一定の危険率の下での必要帯域量との差分情報から、ノードペア間のトラヒック測定装置の導入により、どれだけの帯域削減効果を見込めるかを把握し、トラヒック測定装置の導入コストに見合うかどうかの評価を行うための削減帯域算出装置及び方法及び帯域削減効果評価装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明（請求項１）の帯域削減効果評価方法は、通信網上において、単数、または、複数のソースノードと宛先ノードの間でトラヒック要求が発生する場合において、障害が発生しない通常時には「現用パス」として予め設定されたパス、現用パス上に障害が発生した時には「迂回用パス」として予め設定されたパスを選定する状況において、ノードペア間のトラヒック測定による帯域削減効果を評価する帯域削減効果評価装置における帯域削減効果評価方法であって、
障害が発生せず、現用パスが選択されており、全通信ノードペア間を流れるトラヒックが、通信網における通信リンクを流れるトラヒック量として観測されている場合に、そのトラヒック観測を行っている通信リンクで観測されるトラヒック量及び現用パス、迂回用パスの経路情報を取得するデータ取得ステップと、
前記通信網を有向グラフと見做して、前記トラヒック量及び前記経路情報を用いて最大流問題を解くことにより、通信リンクにおいて必要となる迂回用パスの帯域上限値を求める帯域上限値算出ステップと、
前記帯域上限値及び一定の危険率αの下で迂回用パスに必要な通信リンクでの必要帯域を算出する必要帯域算出ステップと、
前記帯域上限値と前記必要帯域の差分を求め、前記ノードペア間のトラヒック情報を入手したときに削減できる帯域とする差分算出ステップを有する。
また、本発明（請求項２）の帯域削減効果評価方法は、
前記帯域上限値算出ステップにおいて、
リンクaを疎通する迂回用パスのトラヒックの絶対安全側の帯域Caを、対応する現用パスのトラヒックの総和を最大化するようにして最大流問題を解くことにより求めるステップと、
現用パスのトラヒックの分布関数を重力モデルから求めるステップと、
ノードペア間のトラヒック情報が分かっているときの前記リンクaを疎通する現用パスの上限値c1(a)を、対応する現用パスのトラヒックの総和計算から求めるステップと、を含み、
前記必要帯域算出ステップにおいて、
前記危険率αの下でのノードペア間のトラヒック情報が分かっているときの当該リンクを疎通する安全側の迂回用パスのトラヒックc2(a)を、対応する現用パスのトラヒックのたたみこみ計算から求めるステップと、
前記リンクaにおける実測現用トラヒック上限値をtrafsup(a)とし、該リンクａにおける危険率αの下でのノードペア間のトラヒック情報が分かっているときの迂回用パス必要帯域Ｍａをc2(a)/c1(a)*  trafsup(a)とするステップと、を含み、
前記差分算出ステップにおいて、
前記リンクａを疎通する迂回用パスのトラヒックの絶対安全側の帯域（Ca）と前記迂回用パス必要帯域(Ｍａ)の差分を、測定装置によってトラヒック情報が得られたときのリンクaにおける削減帯域とするステップを含む。
【００１１】
また、本発明（請求項３）の帯域削減効果評価方法は、
前記帯域上限値算出ステップにおいて、
通信リンクｂが故障したときに通信リンクａを疎通する迂回用パスのトラヒックの絶対安全側の帯域C’abを、対応する現用パスのトラヒックの総和を最大化するようにして最大流問題を解いて求めるステップと、
前記通信リンクｂを変化させたときの前記絶対安全側の帯域C’abの最大値C’aを前記通信リンクａを疎通する迂回用パスのトラヒックの絶対安全側の帯域とするステップと、
現用パスのトラヒックの分布関数を重力モデルから求めるステップと、
ノードペア間のトラヒック情報が分かっているときの当該リンクaを疎通する現用パスの上限値c1(a)を、対応する現用パスのトラヒックの総和計算から求めるステップと、を含み、
前記必要帯域算出ステップにおいて、
前記危険率αの下でのノードペア間のトラヒック情報が分かっているときの通信リンクbが故障したときの当該リンクaを疎通する安全側の迂回用パスのトラヒックc3(a,b)を、対応する現用パスのトラヒックのたたみこみ計算から求めるステップと、
前記通信リンクbを変化させたときのc3(a,b)の最大値c4(a)を、前記危険率αの下でのノードペア間のトラヒック情報が分かっているときの迂回用パスの通信リンクａにおける安全側の帯域とするステップと、
前記通信リンクａにおける実測現用トラヒック上限値をtrafsup(a)とし、該通信リンクaにおける危険率αの下でのノードペア間のトラヒック情報が分かっているときの迂回用パス必要帯域Ｍ’ａをc4(a)/c1(a)*  trafsup(a)とするステップと、を含み、
前記差分算出ステップにおいて、
前記通信リンクａを疎通する迂回用パスのトラヒックの絶対安全側の帯域（C’a）と前記迂回用パス必要帯域(Ｍ’ａ)の差分を測定装置によってトラヒック情報が得られたときの前記通信リンクaにおける削減帯域とするステップを含む。
【発明の効果】
【００１２】
従来技術は、不完全なトラヒック情報下での絶対安全側の帯域評価手法しか存在せず、一定の危険率の下でどの程度の帯域が必要になるかについては考慮されていなかったが、本発明によれば、同じくトラヒックモデルを仮定したときの不完全なトラヒック情報下での一定の危険率の下の必要帯域評価手法と組み合わせることによって、トラヒック測定装置の導入によって、迂回用パスの必要帯域がどれだけ削減できるかという課題を解決することが可能となる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施の形態におけるシステムを構成する機能構成を示す図である。
【図２】本発明の一実施の形態における削減帯域計算例のための現用パス例（ノードペア間トラヒック上限値＝１）である。
【図３】本発明の一実施の形態におけるdedicated protection 方式における削減帯域計算例のための当該リンクａを通る迂回用パス（図２と対応）を表す図である。
【図４】本発明の一実施の形態におけるdedicated protection方式における削減帯域計算例のための当該リンクａを通る迂回用パスに対応する現用パス（図３に対応）を表す図である。
【図５】本発明の一実施の形態におけるdedicated protection方式における削減帯域計算例のための最大流問題を解くネットワーク（図４と対応）を表す図である。
【図６】本発明の一実施の形態におけるshared protection方式における削減帯域計算例のための通信リンクＡＢが故障したときの当該リンクａを通る迂回用パス（図２と対応）を表す図である。
【図７】本発明の一実施の形態におけるshared protection方式における削減帯域計算例のための通信リンクＡＢが故障したときの当該リンクａを通る迂回用パスに対応する現用パス（図６に対応）を表す図である。
【図８】本発明の一実施の形態におけるshared protection方式における削減帯域計算例のための通信リンクＡＢが故障したときの最大流問題を解くネットワーク（図７と対応）を表す図である。
【図９】本発明の一実施の形態におけるshared protection方式における削減帯域計算例のための通信リンクＢＣが故障したときの当該リンクａを通る迂回用パス（図２と対応）を表す図である。
【図１０】本発明の一実施の形態におけるshared protection方式における削減帯域計算例のための通信リンクＢＣが故障したときの当該リンクａを通る迂回用パスに対応する現用パスを表す図である。
【図１１】本発明の一実施の形態におけるshared protection方式における削減帯域計算例のための通信リンクＢＣが故障したときの最大流問題を解くネットワーク（図１０と対応）を表す図である。
【図１２】本発明の一実施の形態におけるshared protection方式における削減帯域計算例のための通信リンクＣＤが故障したときの当該リンクａを通る迂回用パス（図２と対応）を表す図である。
【図１３】本発明の一実施の形態におけるshared protection方式における削減帯域計算例のための通信リンクＣＤが故障したときの当該リンクａを通る迂回用パスに対応する現用パス（図１２に対応）を表す図である。
【図１４】本発明の一実施の形態におけるshared protection方式における削減帯域計算例のための通信リンクＣＤが故障したときの最大流問題を解くネットワーク（図１３と対応）を表す図である。
【図１５】本発明の一実施の形態におけるアルゴリズムの表による整理を表す図である。
【発明を実施するための形態】
【００１４】
以下図面と共に、本発明の実施の形態を説明する。
【００１５】
図１は、本発明の一実施の形態におけるシステム構成を示す。
【００１６】
同図に示すシステムは、削減帯域算出装置１００、オペレーションシステム２００、削減帯域表示装置３００、通信網１から構成される。
【００１７】
本発明の核となる装置である削減帯域算出装置１００は、通信網１上のノード・通信網を管理運用するオペレーションシステム２００に接続され、必要なデータの取得と取得データを用いた削減帯域の算出を実施する。削減帯域算出装置１００は、通信網１の運用者、または、設計者が直接操作する削減帯域表示装置３００からの要求を受け、算出した削減帯域に関する情報を削減帯域表示装置３００に送信する。
【００１８】
以下で本発明を実現するオペレーションシステム２００，削減帯域算出装置１００、削減帯域表示装置３００の機能について示す。
【００１９】
［１］オペレーションシステム２００：
オペレーションシステム２００は、機能部としてのネットワークデータ収集部２１０とデータベースとしてのネットワーク情報データベース２２０から構成される。
【００２０】
ネットワークデータ収集部２１０は，オペレーションシステム２００が管理する通信網１上のノードに接続する通信リンク上を流れるトラヒック量を収集し、トラヒック情報としてネットワーク情報データベース２２０に蓄積する。また，通信網の運用者が設定するなどした現用パス・迂回用パスに関する情報はパス情報としてネットワーク情報データベース２２０に蓄積する。
【００２１】
［２］削減帯域算出装置１００：
削減帯域算出装置１００は、機能部としてのデータ取得部１１０、帯域算出部１２０，及び、データベースとしてのトラヒック情報データベース１４０、パス情報データベース１３０から構成される。
【００２２】
データ取得部１１０は、オペレーションシステム２００がネットワーク情報データベース２２０で管理する情報のうち、削減帯域算出に必要な情報として、トラヒック情報、パス情報を取得し、それぞれ、トラヒック情報データベース１４０、パス情報データベース１３０に蓄積する。
【００２３】
帯域算出部１２０は、トラヒック情報データベース１４０、パス情報データベース１３０に蓄積されたトラヒック情報、パス情報を用いて次に示すような計算を実施することで通信リンクに必要な帯域上限値および一定の危険率の下での必要帯域を計算する。ここで、『危険率αの下での必要帯域』とは、トラヒックを確率変数とみたとき、その値が必要帯域Ｃを超えるトラヒック確率密度をＣから無限大まで積分した値がαになることをいう。つまり、危険率αは、トラヒックが必要帯域Ｃを超えてしまい、溢れてしまう確率を指す。
【００２４】
対象とする通信網を有向グラフG={N, E}とする。但し、N, Eは、それぞれ通信網１に属するノード、リンクの集合とする。Fij ≧ 0をノードiからノードjへのトラヒックフローとする。
【００２５】
後述する式に用いる要素を以下に示す。
【００２６】
【数１】
0005718797.tif 000002
は、ノードi, j間の現用パスの経路を示す (ノードi, j間の現用パスがリンクeを通るならば、
【００２７】
【数２】
0005718797.tif 000003
通らないならば、
【００２８】
【数３】
0005718797.tif 000004
とする）。
【００２９】
【数４】
0005718797.tif 000005
は、ノードi, j間の迂回用パスの経路を示す (ノードi, j間の迂回用パスがリンクeを通るならば、
【００３０】
【数５】
0005718797.tif 000006
通らないならば、
【００３１】
【数６】
0005718797.tif 000007
とする）。
【００３２】
【数７】
0005718797.tif 000008
は、リンクe上の観測トラヒック上限値を示す。
【００３３】
【数８】
0005718797.tif 000009
は、ノードiに流入するトラヒックの観測上限値を示す。
【００３４】
【数９】
0005718797.tif 000010
は、ノードjから流出するトラヒックの観測上限値を示す。
【００３５】
【数１０】
0005718797.tif 000011
は、ノードiに流入するトラヒックの観測平均値を示す。
【００３６】
【数１１】
0005718797.tif 000012
によって、ノードjから流出するトラヒックの観測平均値を示す。
【００３７】
【数１２】
0005718797.tif 000013
は、ノードjから流出するトラヒックの確率変数を示す。
【００３８】
迂回用パスに割り当てる帯域をそれぞれの現用パスの故障に対応して独立に割り当てていくdedicated protection方式と、異なるリンク故障に対応する迂回用パスに割り当てる帯域は共有して経済的に節約していくshared protection方式では、迂回用パスの帯域上限値と一定の危険率の下での必要帯域の算出法が異なるので、それぞれの手法について説明する。
【００３９】
＜dedicated protection方式＞
●dedicated protection方式における迂回用パス帯域上限値：
迂回用パスに割り当てる帯域をそれぞれの現用パスの故障に対応して独立に割り当てていくdedicated protection方式の場合、線形計画法によって、通信リンクaにおいて必要になる迂回用パスの帯域上限値を求める手続きを定式化すると次のようになる。
【００４０】
【数１３】
0005718797.tif 000014
この線形計画法の最大値が、通信リンクaにおいて必要となる迂回用パスの帯域上限値となる。この線形計画法は、次のようなグラフの最大流問題を解くことによって、より高速に導出することができる。
【００４１】
ステップ１：帯域を求めたい通信リンクaを選択する。
【００４２】
ステップ２：
【００４３】
【数１４】
0005718797.tif 000015
を算出する。
【００４４】
ステップ３： ノードs,ノードｄをNに加えてN'を作る。
【００４５】
N':=N∪{s}∪{d}  
リンクsi:=(s,i), i∈Ｎ，  dj:=(j,d), j∈NをＥに加えてE'を作る。
【００４６】
E':=E∪[si|ｉ∈Ｎ｝∪{dj|ｊ∈N}.
【００４７】
【数１５】
0005718797.tif 000016
とおき、
【００４８】
【数１６】
0005718797.tif 000017
をtraf'(e), e∈E'に拡張する。
【００４９】
【数１７】
0005718797.tif 000018
とおく。
【００５０】
ステップ４： ネットワークGa={Na，Ea}と各リンクの正の容量traf':Ea→R+を入力として、各リンクの流量φ；Ea→R+のなかでノードsから出る流量が最大となるφを求める。流量φは、
【００５１】
【数１８】
0005718797.tif 000019
を満たす。
【００５２】
【数１９】
0005718797.tif 000020
がdedicated protection方式において、通信リンクaが取り得る迂回用パス帯域の上限値になる。
【００５３】
［証明］ 
dedicated protection方式における、通信リンクaを疎通する迂回用パス帯域は、(i，j) ∈Uaをソース・デスティネーションとする現用パスの流量の総和である。この現用パス流量は、入出力トラヒックの制約からソースノードi，デスティネーションノードjにおいて、それぞれ、
【００５４】
【数２０】
0005718797.tif 000021
よりも小さくなければならず、各リンクにおいては、trafsup(e), e∈Eより小さくなければならない。これを整理すると、流量φは
【００５５】
【数２１】
0005718797.tif 000022
を満たす。この下で、ノードsから出る流量φを最大化した値が、dedicated protection方式における迂回用パスが通信リンクaを疎通する最大トラヒックとなる。（証明終わり）
この最大流問題はDinicの増加道法により高速に解くことができる(例えば、文献１「応用数理計画ハンドブック」，朝倉書店，2002年，pp. 379-381.参照)。
【００５６】
●dedicated protection方式における危険率αの下での迂回用パス必要帯域：
ノードペア間のトラヒックはそれぞれ独立であるという仮定を置く。またトラヒック分布は一様分布トラヒックモデルを仮定する。このトラヒックモデルでは、ノードにおける総発信トラヒックと総着信トラヒック、及び発信ノード着信ノード間距離から重力モデルによりノードペア間トラヒックを算出する。このケースにおける各リンクにおける現用パスと迂回用パスの帯域比率を求め、当該リンクの実測上限トラヒックを乗ずることにより、危険率αの下での迂回用パス必要帯域を求める。以下、次のような表記法を用いる。
・K ：ノードペア（ディマンド）の集合；
・ｋ(i,j)：ノードi,jからなるディマンド；
・ｒ(k)（ｋ∈K）：ディマンドk(i,j)に対応するノードペア間距離；
・ｔｍ（ｋ）（ｋ∈K）：ディマンドk(i,j)，平均発信トラヒックextoutm(i)，平均着信トラヒックextoutm(j)，距離ｒ((i，j)のとき、重力モデルを適用して求めたノードペア間平均トラヒック；
・ｔ(k)(k∈K)：ディマンドk(i,j)におけるノードペア間トラヒック（一様分布に従う確率変数）；
・ｇk(t)(t≧０)（ｋ≧Ｋ）：一様分布に従う確率変数t(k)(k∈Ｋ)の確率密度関数；
・α：危険率；
・path1k(k∈K)：{1，…，hop1(k)} →Eディマンドkに対応する現用パス（現用パスを、始点から終点に至るリンクの列として表現する）；
・path2k(k∈K)：{1，…，hop2(k)} →Eディマンドkに対応する迂回用パス（迂回用パスを，始点から終点に至るリンクの列として表現する）；
・hop1(k)(k∈Ｋ)：ディマンドkに対応する現用パスpath1kのホップ数；
・hop2(k)(k∈K)：ディマンドkに対応する迂回用パスpath2kのホップ数；
今、ノードiにおける発信トラヒック平均値extoutm(i)，ノードjにおける着信トラヒック平均値extinm(j)，ノードペア(i,j)に対応するディマンドk(i,j)，ノードi,j間の距離r(k(i,j))とする。この時、重力モデルに従うと、ノードペア間平均トラヒックｔｍ(k)(k∈Ｋ)は、
【００５７】
【数２２】
0005718797.tif 000023
となる。
【００５８】
ノードペア間トラヒックの確率変数ｔ(k)(k∈Ｋ)は、
【００５９】
【数２３】
0005718797.tif 000024
と近似できる。ノードｉにおける発信トラヒックextout(i)を
【００６０】
【数２４】
0005718797.tif 000025
における一様分布確率変数と考えると、ｔ(k(i，j))も一様分布確率変数となる。ｇｋ(t)(t≧０)をその確率密度関数とする。ｔsup(k(i，j))をt(k(i，j))の上限値とする。
【００６１】
リンクaにおける現用パス必要帯域の上限値は、
【００６２】
【数２５】
0005718797.tif 000026
【００６３】
【数２６】
0005718797.tif 000027
（ただし，＊はたたみこみ演算とする）とおくと、
【００６４】
【数２７】
0005718797.tif 000028
を満たすc2(a)となる。
【００６５】
両者の比率は、c2(a)／c1(a)となる。これは、リンクa上の現用パス帯域は上限値で評価し、迂回用パスは安全側で評価したことになる。リンクaにおける実測現用トラヒック上限値trafsup(a)をこの比率に乗ずることにより、dedicated protection方式におけるリンクaにおける危険率αの下での迂回用パス必要帯域Maは,
Ma:=c2(a)/c1(a)・trafsup(a)
となる。
【００６６】
●dedicated protection方式における迂回用パス削減帯域：
dedicated protection方式においては、ノードペア間のトラヒックが分かっていない状況でも、各リンクaにおいてCaの迂回用パス帯域を設定すれば絶対安全側の設計ができ、このCaはその安全側設計の最小値でもある。他方、この時、実際にノードペア間のトラヒックがどのような値であるかは、一意に決められないが、重力モデルを仮定すると危険率αの下での安全側の値としてMaが考えられる。トラヒック測定装置によってノードペア間のトラヒックを測定することを重力モデルによってトラヒックを算出することに置き換えて考えると、測定装置によってトラヒック情報が得られたとき、危険率αを考慮したとき帯域Maで安全側帯域設計ができると考えられる。したがって、トラヒック測定装置によるノードペア間トラヒック測定による帯域削減効果は重力モデルの下で通信リンクａにおいてＣa−Ｍaと考えられる。この削減帯域からネットワーク削減コストを試算し、トラヒック測定装置にかかるコストと比較することにより、ノードペア間のトラヒックが分かっていない時点で、トラヒック測定の効果を具体的に把握することができる。
【００６７】
＜shared protection方式＞
●shared protection方式における迂回用パス帯域上限値：
異なるリンク故障に対応する迂回用パスに割り当てる帯域は共有して経済的に節約していくshared protection方式の場合、線形計画法によって、通信リンクbが故障したとき、通信リンクaにおいて必要になる迂回用パスの帯域を求める手続きを定式化すると次のようになる。
【００６８】
【数２８】
0005718797.tif 000029
これをすべての通信リンクbについて計算し、その最大値を求めると、通信リンクaにおいて必要となる迂回用パスの帯域を求めることができる。通信リンクbが故障したとき、通信リンクaにおいて必要になる迂回用パスの帯域は、次のようなグラフの最大流問題を解くことによって、より高速に導出することができる。
【００６９】
ステップ１：故障通信リンクb，帯域を求めたい通信リンクa (a≠b)を選択する。
【００７０】
ステップ２：
【００７１】
【数２９】
0005718797.tif 000030
を算出する。
【００７２】
ステップ３： ノードs,ノードｄをNに加えてN'を作る。
【００７３】
N':=N∪{s}∪{d}  
リンクsi:=(s,i), i∈Ｎ，dj:=(j,d), j∈NをＥに加えてE'を作る。
【００７４】
E':=E∪[si|ｉ∈Ｎ｝∪{dj|ｊ∈N}.
【００７５】
【数３０】
0005718797.tif 000031
とおき、trafsup(e)， e∈Eをtraf'(e)，e∈E'に拡張する。
【００７６】
【数３１】
0005718797.tif 000032
とおく。
【００７７】
ステップ４：  ネットワークＧab={Nab，Eab}と各リンクの正の容量traf':Eab→Ｒ+を入力として、各リンクの流量φ：Eab→Ｒ+のなかでsから出る流量が最大となるφを求める。φは、
【００７８】
【数３２】
0005718797.tif 000033
を満たす。
【００７９】
【数３３】
0005718797.tif 000034
が通信リンクbが故障したときに，通信リンクaが取り得るトラヒックの上限値になる。
【００８０】
ステップ5：
【００８１】
【数３４】
0005718797.tif 000035
を計算する。C'aが求める通信リンクaの迂回用パス帯域の上限値になる。
【００８２】
［証明］
通信リンクbが故障したときに、通信リンクaを疎通するトラヒックは、(i,j) ∈Ｕabをソース、デスティネーションとする現用パスの流量の総和である。この現用パスの流量は、入出力トラヒックの制約からソースノードｉ、デスティネーションノードjにおいて、それぞれ、
【００８３】
【数３５】
0005718797.tif 000036
よりも小さくなければならず、各リンクにおいては、trafsup(e), e∈Ｅより小さくなければならない。これを整理すると、流量φは、
【００８４】
【数３６】
0005718797.tif 000037
を満たす。この下で、sから出るφを最大化した値が、通信リンクｂが故障したときに、迂回用パスが通信リンクaを疎通する最大トラヒックとなる。あとは通信リンクｂを変化させて、最大トラヒックの最大値を求めればよい。（証明終わり）
この最大流問題はDinicの増加道法により高速に解くことができる(文献１参照)。
【００８５】
●shared protection方式における迂回用パス帯域平均値：
ノードペア間のトラヒックはそれぞれ独立であるという仮定を置く。またトラヒック分布は一様分布トラヒックモデルを仮定する。このトラヒックモデルでは、ノードにおける総発信トラヒックと総着信トラヒック、及び発信ノード着信ノード間距離から重力モデルによりノードペア間トラヒックを算出する。このケースにおける各リンクにおける現用パスと迂回用パスの帯域比率を求め、当該リンクの実測上限トラヒックを乗ずることにより、危険率αの下での迂回用パス必要帯域を求める。 
この時、トラヒックモデルに従うと、通信リンクaにおける現用パス帯域上限値は、
【００８６】
【数３７】
0005718797.tif 000038
となる。
【００８７】
通信リンクｂが故障したとき、通信リンクaにおける一定の危険率αの下での迂回用パス必要帯域の安全側評価は、
【００８８】
【数３８】
0005718797.tif 000039
（ただし，＊はたたみこみ演算とする）とおくと、
【００８９】
【数３９】
0005718797.tif 000040
を満たすc3(a，b)となる。
【００９０】
shared protection方式における、通信リンクaにおける迂回用パス帯域は、
【００９１】
【数４０】
0005718797.tif 000041
したがって現用パス帯域上限値と一定の危険率αの下での迂回用パス必要帯域の比率は、c4(a)/c1(a)となる。リンクaにおける実測現用トラヒック上限値trafsup(a)を比率に乗ずることにより、shared protection方式におけるリンクaにおける危険率αの下での迂回用パス必要帯域M'aは、安全側評価として
Ｍ'ａ:=c4(a)/c1(a)・trafsup(a)
となる。
【００９２】
●shared protection方式における迂回用パス削減帯域：
shared protection方式においては、ノードペア間のトラヒックが分かっていない状況でも、各リンクaにおいてC'aの迂回用パス帯域を設定すれば絶対安全側の設計ができ、このC'aはその絶対安全側設計の最小値でもある。他方、この時、実際にノードペア間のトラヒックがどのような値であるかは、一意に決められないが、危険率αの下での安全側の値としてM'aが考えられる。トラヒック測定装置によってノードペア間のトラヒックを測定することによって、危険率αを考慮したときこのM'aに近い帯域設計ができると考えられる。したがって、トラヒック測定装置によるノードペア間トラヒック測定による帯域削減効果は通信リンクaにおいてC'a−M'aと考えられる。この削減帯域からネットワーク削減コストを試算し、トラヒック測定装置にかかるコストと比較することにより、ノードペア間のトラヒックが分かっていない時点で、トラヒック測定の効果を具体的に把握することができる。 
＜アルゴリズムの計算例＞
以上のアルゴリズムを図２〜５によってdedicated protection方式の場合について説明する。図２は4ノードA, B, C, Dからなるリング型通信網を示す。今通信リンクa=ADを迂回用パスの帯域上限値と帯域平均値を求めたい通信リンクとする。ここで図２の矢印の示すように現用パスのトラヒックが流れていたものとする。各矢印のトラヒックは、すべて１とする。ここで図示されている情報はノードペアのトラヒック情報をすべて見ている状況を示している。実際には、各矢印のトラヒックがすべて１であることは隠されていて、実際に分かっているトラヒック情報は、
trafsup(AD)=trafsup(DC)=trafsup(CB)=trafsup(BA)=3,
extinsup(A)=extinsup(D)=extinsup(C)=extinsup(B)=2,
extoutsup(A)=extoutsup(D)=extoutsup(C)=extoutsup(B)=2
がすべてである。図２の当該リンクaを通る現用パスの本数は3本である。今、重力モデルよりもさらにシンプルなモデルを考えてノードペア間のトラヒックはすべて同一の分布に従うとし、トラヒックの上限値は関与するパスの本数と一致するものとする。そのとき、
c1(a)=3
となる。
【００９３】
図３に迂回用パスで当該リンクaを通るものを示す。当該リンクaにおける迂回用パスの本数を数えて全部で5本あることが分かる。この5本のトラヒック上でたたみこみ計算を行い、危険率αの下での安全側のノードペア間トラヒックが仮に上限値の0.8倍に相当するとする。このとき、
c2(a)=5*0.8=4
となる。当該リンクaにおける危険率αの下での安全側の迂回用パスの帯域は、これから次のように求めることができる。
【００９４】
Ma=c2(a)/c1(a)・trafsup(a)=4/3・3=4
当該リンクaにおける迂回用パスの帯域上限値は、最大流問題を解くことによって求めることができる。
【００９５】
図４に図３の迂回用パスに対応する現用パスを示す。これらの現用パスが通過するリンクにソースノードS0と宛先ノード D0を付け加えた最大流問題を解くネットワークを図５に示す。このネットワークの最小カットは、{S0}か、N-{D0}で、その容量は、
extin(B)+extin(C)+extin(D)=2+2+2=6({S0}の場合)．
または、
extout(A)+extout(B)+extout(C)=2+2+2=6(N-{D0}の場合)
となり、最大流は6、すなわち、
Ca=6
であることが分かる。ノードペア間のトラヒック測定をすることによって削減できる当該リンクaにおける迂回パス帯域は、
Ca-Ma=6-4=2
となり、平均して２トラヒックの迂回用パス帯域削減が当該リンクaに期待できることが、ノードペア間のトラヒック測定をする前に把握できる。
【００９６】
次に、図６〜１４を用いてshared protection方式における迂回用パス削減帯域アルゴリズムの説明を行う。Dedicated protection方式の場合との違いは故障リンクｂを変化させて繰り返し計算を行う点にある。対象とする網とトラヒックはdedicated protection方式の場合と同じく図２の通りとする。
【００９７】
今、故障リンクb=ABとしたときに、迂回用パスで通信リンクaを通るものを図６に示す。故障リンクb=ABを迂回する当該リンクaにおける迂回用パスの本数を数えて全部で２本あることが分かる。この２本のトラヒック上でたたみこみ計算を行い、危険率αの下での安全側のノードペア間トラヒックが仮に上限値の0.8倍に相当するとする。このとき、
c3(a, AB)=2*0.8=1.6
となる。故障リンクb=ABとしたときの当該リンクaにおける迂回用パスの帯域上限値は、最大流問題を解くことによって求めることができる。
【００９８】
図７に図６の迂回用パスに対応する現用パスを示す。これらの現用パスが通過するリンクにソースノードS0と宛先ノードD0を付け加えた最大流問題を解くネットワークを図８に示す。このネットワークの最小カットは、N-{D0}で、その容量は、
Extout(A) =2 (最小カット=N-{D0})
となり、最大流は2、すなわち、
C'aAB=2
であることが分かる。
【００９９】
次に故障リンクb=BCとしたときに、迂回用パスで通信リンクaを通るものを図９に示す。故障リンクb=BCを迂回する当該リンクaにおける迂回用パスの本数を数えて全部で3本あることが分かる。この３本のトラヒック上でたたみこみ計算を行い、危険率αの下での安全側のノードペア間トラヒックが仮に上限値の0.8倍に相当するとする。このとき、
c3(a, BC)=3*0.8=2.4
となる。故障リンクb=BCとしたときの当該リンクaにおける迂回用パスの帯域上限値は、最大流問題を解くことによって求めることができる。図１０に図９の迂回用パスに対応する現用パスを示す。これらの現用パスが通過するリンクにソースノードS0と宛先ノードD0を付け加えた最大流問題を解くネットワークを図１１に示す。このネットワークの最小カットは、{S0}か、N-{D0}で、その容量は、
extin(C)+extin(D)=2+2=4(最小カット={S0}の場合)．
または、
extout(A)+extout(B)=2+2=4(最小カット=N-{D0}の場合)
となり、最大流は４、すなわち、
C'aBC=4
であることが分かる。
【０１００】
同様にして故障リンクb=CDとしたときに，迂回用パスで通信リンクaを通るものを図１２に示す。故障リンクb=CDを迂回する当該リンクaにおける迂回用パスの本数を数えて全部で2本あることが分かる。この3本のトラヒック上でたたみこみ計算を行い、危険率αの下での安全側のノードペア間トラヒックが仮に上限値の0.8倍に相当するとする。このとき、
c3(a, CD)=2*0.8=1.6
となる。故障リンクb=CDとしたときの当該リンクaにおける迂回用パスの帯域上限値は，最大流問題を解くことによって求めることができる。図１３に図１２の迂回用パスに対応する現用パスを示す。これらの現用パスが通過するリンクにソースノードS0と宛先ノード D0を付け加えた最大流問題を解くネットワークを図１４に示す。このネットワークの最小カットは、{S0}で，その容量は、
extin(D)=2(最小カット={S0})
となり、最大流は2、すなわち、
C'aCD=2
であることが分かる。
【０１０１】
以上から、
c4(a)=max{1.6, 2.4, 1.6}=2.4,
M'a=c4(a)/c1(a)・trafsup(a)=2.4/3・3=2.4
C'a=max{2, 4, 2}=4
従って、ノードペア間のトラヒック測定をすることによって削減できる当該リンクaにおける迂回パス帯域は、
C'a-M'a=4-2.4=1.6
となり、平均して1.6トラヒックの迂回用パス帯域削減が当該リンクaに期待できることが、ノードペア間のトラヒック測定をする前に把握できる。
【０１０２】
図１５に本特許のアルゴリズムを表の形で整理した。同図に示すように、帯域算出部１２０では、絶対安全側設計の出力から危険率αの下での安全側設計の出力を、トラヒック情報を増やしたときに高精度設計により削減できる帯域量と見做し、トラヒック測定装置導入によるコスト削減量の装置導入前の評価尺度とする。なお、重力モデルがトラヒック測定値を模擬しているものと考える。
【０１０３】
［３］削減帯域表示装置３００：
削減帯域表示装置３００は、機能部としての帯域表示部３１０から構成される。
【０１０４】
帯域表示部３１０は、通信網の運用者、または，設計者による操作に基づき、削減帯域算出装置１００に対して、設計・運用・管理の対象である通信網１において対象とする通信リンクのものとして算出された帯域上限値、危険率αの下での安全側帯域の取得要求を実施し、削減帯域算出装置１００から受信した値を表示する。
【０１０５】
なお、上記の実施の形態におけるオペレーションシステム２００、削減帯域算出装置１００、削減帯域表示装置３００の各動作をプログラムとして構築し、コンピュータとして利用されるそれぞれの装置にインストールして実行させる、または、ネットワークを介して流通させることも可能である。例えば、削減帯域算出装置１００のデータ取得部１１０、帯域算出部１２０の各機能がソフトウェアで実現することが可能である。
【０１０６】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１０７】
１  通信網
１００  削減帯域算出装置
１１０  データ取得部
１２０  帯域算出部
１３０  パス情報データベース
１４０  トラヒック情報データベース
２００  オペレーションシステム
２１０  ネットワークデータ収集部
２２０  ネットワーク情報データベース
３００  削減帯域表示装置
３１０  帯域表示部
【図１】
0005718797.tif 000042
【図２】
0005718797.tif 000043
【図３】
0005718797.tif 000044
【図４】
0005718797.tif 000045
【図５】
0005718797.tif 000046
【図６】
0005718797.tif 000047
【図７】
0005718797.tif 000048
【図８】
0005718797.tif 000049
【図９】
0005718797.tif 000050
【図１０】
0005718797.tif 000051
【図１１】
0005718797.tif 000052
【図１２】
0005718797.tif 000053
【図１３】
0005718797.tif 000054
【図１４】
0005718797.tif 000055
【図１５】
0005718797.tif 000056