帯域算出方法、帯域算出装置及びプログラム
【課題】迂回用パスに必要な帯域を算出する際の計算量を削減することを目的とする。
【解決手段】現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置における帯域算出方法は、通信リンクを流れるトラヒック量を取得するステップと、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出するステップと、前記第１の通信リンクを選択し直して前記算出するステップを繰り返すことにより、迂回用パスで必要となる通信リンクの帯域上限値を算出するステップとを有する。
【解決手段】現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置における帯域算出方法は、通信リンクを流れるトラヒック量を取得するステップと、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出するステップと、前記第１の通信リンクを選択し直して前記算出するステップを繰り返すことにより、迂回用パスで必要となる通信リンクの帯域上限値を算出するステップとを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、帯域算出方法、帯域算出装置及びプログラムに関する。より具体的には、本発明は、障害時に選択される迂回用パスに必要な通信リンクの帯域上限値を算出する帯域算出方法、帯域算出装置及びプログラムに関する。
【背景技術】
【０００２】
通信リンクには、耐障害性を高めるために、現用パスに対して迂回用パスが設定される。迂回用パスに必要な帯域を算出する方法として、以下の方法が検討されている。
【０００３】
詳細に迂回用パスで利用されている必要帯域上限値を計算せず、Ringネットワークにおいて逆方向に流れるトラヒックの通信リンクでの最大量を想定するなど自明な解を用いて上限値を導出する方法がある。この方法は高速ではあるが、この方法で得られる解は、必要帯域の上界を求めるものであり、ケースによっては過剰な量の帯域を算出するという問題がある。
【０００４】
通信リンクを流れるトラヒックの情報より、送信元・宛先（ＳＤ：Source-Destination）ペア間の交流トラヒックを推定するNetwork-Tomographyという方法がある（非特許文献１参照）。このNetwork-Tomographyにより推定された交流トラヒックより迂回用パスに必要な帯域を求めることも可能である。しかし、Network-Tomographyでは、交流トラヒックは、ポアソン分布又は正規分布を仮定して、最尤法等を用いて平均値を算出するものであり、迂回用パスに必要な帯域上限値を保証するものではないという問題がある。
【０００５】
これらの問題を解決するものとして、通信リンクを流れるトラヒックや端点ノードにおける流出入トラヒックの観測データを制約式に組み込み、通信リンクを流れる迂回用パスに必要な帯域を線形計画法によって最大化する帯域算出手法がConstraint Programmingとして考案されている（非特許文献２参照）。この手法は、迂回用パスに必要な通信リンクでの帯域上限値を導出する目的としては、理想的な結果を算出する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】A. Medina et al. "Traffic Matrix Estimation: Existing Techniques and New Directions," Proceedings of the 2002 SIGCOMM conference, 2002.
【非特許文献２】H. Simonis, "Constraint Based Resilience Analysis," LNCS, Vol. 4204, 16-28, 2006.
【非特許文献３】久保幹雄，田村明久，松井知己．応用数理計画ハンドブック．朝倉書店，379-380,2002.
【非特許文献４】Komei Fukuda, Tamas Terlaky, "On the existence of a short admissible pivot sequence for feasibility and linear optimization problems," Elsevier, 1999.
【特許文献】
【０００７】
【特許文献１】特願2010-34273
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記のように、Constraint Programmingは、迂回用パスに必要な通信リンクでの帯域上限値を導出できるが、迂回用パスが複数の現用パスにより共用されるshared protection制約の下で適用しようとすると、故障通信リンク毎に、それぞれ大規模な線形計画法を繰り返し解かなければならず計算時間がかかるという問題がある。
【０００９】
この計算時間を削減するために、線形計画法の制約式の中に目的関数の下限値を繰りこむことも可能である（特許文献１参照）。しかし、線形計画法を用いているため、抜本的な高速化には到らない。
【００１０】
そこで、本発明は、迂回用パスに必要な帯域を算出する際の計算量を削減することができる帯域算出方法、帯域算出装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の帯域算出方法は、
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置における帯域算出方法であって、
通信リンクを流れるトラヒック量を取得するステップと、
現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出するステップと、
前記第１の通信リンクを選択し直して前記算出するステップを繰り返すことにより、迂回用パスで必要となる通信リンクの帯域上限値を算出するステップと、
を有することを特徴とする。
【００１２】
また、本発明の帯域算出装置は、
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置であって、
通信リンクを流れるトラヒック量を取得するトラヒック取得部と、
現用パス及び迂回用パスの情報を格納するパス情報格納部と、
前記パス情報格納部から、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出する帯域算出部と、
を有し、
前記帯域算出部は、前記第１の通信リンクを選択し直し、迂回用パスで必要となる通信リンクの帯域上限値を算出することを特徴とする。
【００１３】
また、本発明のプログラムは、
現用パス及び迂回用パスの情報を格納するパス情報格納部を有する帯域算出装置であり、現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置を、
通信リンクを流れるトラヒック量を取得するトラヒック取得手段、
前記パス情報格納部から、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出する帯域算出手段、
として機能させ、
前記帯域算出手段は、前記第１の通信リンクを選択し直し、迂回用パスで必要となる通信リンクの帯域上限値を算出することを特徴とする。
【発明の効果】
【００１４】
本発明の実施例によれば、迂回用パスに必要な帯域を算出する際の計算量を削減することができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施例に係る故障前後の通信網を示す図
【図２】本発明の実施例に係る通信システムを示す図
【図３】本発明の実施例に係る帯域算出方法の概念図
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施例について説明する。
【００１７】
図１は、本発明の実施例に係る通信網を示す図である。通信網は、複数のノードA〜Dと、ノード間を接続する通信リンクとから構成される。通信網には、単数又は複数の送信元ノード及び宛先ノードのペア（ＳＤペア：Source-Destinationペア）が存在する。ＳＤペア間には、現用パスと迂回用パスとが予め設定されているものとする。現用パスとは、障害が発生しない通常時に利用するパスであり、迂回用パスとは、現用パス上で障害が発生した障害時に利用するパスである。なお、迂回用パスの帯域は、複数の現用パスにより共用可能である。
【００１８】
図１（Ａ）は、故障前の現用パスの例を示しており、現用パスAD、DC、DB、BA、BAD、DCB、CBAが設定されている。現用パスが設定されているノードAとノードBの間の通信リンクａに障害が発生した場合、ＳＤペア間のトラヒックは、迂回用パスに流れる。現用パスBAは迂回用パスBCDAに流れ、現用パスBADは迂回用パスBCDに流れ、現用パスCBAは迂回用パスCDAに流れる。
【００１９】
図１（Ｂ）は、故障後の迂回用パスで、ノードAとノードDとの間のリンクbを疎通するものを示している。具体的には、現用パスBAの迂回用パスBCDAと、現用パスCBAの迂回用パスCDAとが、リンクbを疎通する。この場合、迂回用パスに必要な帯域が予め設定されていなければ、通信品質が低下する。このため、本発明の実施例では、障害が発生していないときに通信網上の通信リンクを流れるトラヒック量を観測しておき、観測されたトラヒック量から、迂回用パスの特定の通信リンクに必要な帯域上限値を算出する。ここで、迂回用パスに必要な帯域上限値を算出する通信リンクを「設計対象リンク」と呼ぶ。障害は、同時に単一の通信リンクで発生することを想定する。
【００２０】
この帯域上限値を算出するために、設計対象リンクに設定されている迂回用パスに対応する現用パスが経由する通信リンクで障害が発生したことを想定し、その際の設計対象リンクでの影響を考える。ここで、障害の発生を想定する通信リンクを「障害想定リンク」と呼ぶ。この障害想定リンクの障害に伴う迂回用パスが設計対象リンクで必要とする帯域上限値を算出する問題は、最大化問題として定式化できる。本発明の実施例では、最大化問題を線形計画法を用いて解くのではなく、通信網を有向グラフとみなした最大流問題によって帯域上限値を算出する。そして、全体の通信網上での必要帯域の算出を行う。
【００２１】
＜通信システムの構成＞
図２は、本発明の実施例に係る通信システムを示す図である。本発明の実施例に係る通信システムは、図１に示すような通信網と、オペレーションシステム１０と、帯域算出装置２０と、帯域表示装置３０とを有する。
【００２２】
オペレーションシステム１０は、通信網上のノード及び通信リンクを運用管理する装置である。オペレーションシステム１０は、機能部としてのネットワークデータ収集部１０１と、データベースとしてのネットワーク情報データベース１１１とを有する。
【００２３】
ネットワークデータ収集部１０１は、オペレーションシステム１０が管理する通信網上のノードに接続する通信リンクを流れるトラヒック量を収集し、トラヒック情報としてネットワーク情報データベース１１１に蓄積する。また、通信網の運用者等により設定された現用パス及び迂回用パスに関する情報は、パス情報としてネットワーク情報データベース１１１に蓄積される。
【００２４】
帯域算出装置２０は、オペレーションシステム１０に接続されており、オペレーションシステム１０からトラヒック情報及びパス情報を取得し、取得したデータを用いて迂回用パスの設計対象リンクに必要な帯域を算出する。帯域算出装置２０は、通信網の運用者又は設計者が直接操作する帯域算出装置２０からの要求を受け付け、算出した必要な帯域に関する情報を帯域表示装置３０に送信する。
【００２５】
帯域算出装置２０は、機能部としてのデータ取得部２０１及び帯域算出部２０２を有し、データベースとしてのパス情報データベース２１１及びトラヒック情報データベース２１２を有する。
【００２６】
データ取得部２０１は、オペレーションシステム１０がネットワーク情報データベース１１１で管理する情報のうち、帯域の算出に必要な情報として、パス情報及びトラヒック情報を取得し、それぞれ、パス情報データベース２１１及びトラヒック情報データベース２１２に蓄積する。
【００２７】
帯域算出部２０２は、パス情報データベース２１１及びトラヒック情報データベース２１２に蓄積されたパス情報及びトラヒック情報を用いて、迂回用パスの設計対象リンクに必要な帯域上界値及び帯域上限値を計算する。帯域上限値を算出するための帯域算出アルゴリズムについては、後述する。
【００２８】
帯域表示装置３０は、帯域算出装置２０に接続されており、算出された帯域上限値を表示する。
【００２９】
帯域表示装置３０は、機能部としての帯域表示部３０１を有する。
【００３０】
帯域表示部３０１は、通信網の運用者又は設計者による操作を受け付け、帯域算出装置２０に対して、設計対象リンクについて算出された帯域上限値の取得要求を実施し、帯域算出装置２０から取得した値を表示する。
【００３１】
＜線形計画法による帯域算出アルゴリズム＞
次に、帯域算出部２０２で用いられる帯域算出アルゴリズムについて説明する。本発明の実施例では、通信網を有向グラフとみなした最大流問題によって帯域上限値を算出するが、比較のため、線形計画法による帯域算出アルゴリズムについて説明する。
【００３２】
対象とする通信網を有向グラフG={N,E}とする。但し、N及びEは、それぞれ通信網に属するノード及び通信リンクの集合とする。
【００３３】
Fij≧0をノードiからノードjへのトラヒック量とする。
【００３４】
rije∈{0,1}によってノードi及びj間の現用パスの経路を示す。具体的には、ノードi及びj間の現用パスがリンクeを通る場合、rije=1とし、通らない場合、rije=0とする。なお、現用パスの経路は、パス情報データベース２１１に格納されている。
【００３５】
【数１】
によってノードi及びj間の迂回用パスの経路を示す。具体的には、ノードi及びj間の迂回用パスがリンクe（設計対象リンク）を通る場合、
【００３６】
【数２】
とし、通らない場合、
【００３７】
【数３】
とする。なお、迂回用パスの経路は、パス情報データベース２１１に格納される。
【００３８】
traf(e)によって、リンクe上のトラヒックの観測値を示す。extin(i)によって、ノードiに流入するトラヒックの観測値を示す。extout(j)によって、ノードjから流出するトラヒックの観測値を示す。これらのトラヒックの観測値は、トラヒック情報データベース２１２に格納されている。
【００３９】
線形計画法によって、通信リンクaが故障したときに通信リンクbにおいて必要になる迂回用パスの帯域を求める式は、次の式(1)で表される。
【００４０】
【数４】
すなわち、次の目的関数
【００４１】
【数５】
の最大値が、リンクaが故障した場合の迂回用パスのリンクbで必要となる帯域上限値を表す。また、式(2)〜式(5)は、式(1)を算出するときの制約式である。
【００４２】
従って、迂回用パスのリンクbで必要となる帯域上限値を算出するためには、式(1)〜式(5)を全ての障害想定リンクaについて計算し、その最大値を算出する必要がある。しかし、線形計画法を繰り返し単純に計算するのでは時間がかかる。本発明の実施例では、以下に説明するように、通信網を有向グラフとみなした最大流問題によって帯域上限値を算出する。
【００４３】
＜最大流問題による帯域算出アルゴリズム＞
次に、帯域算出部２０２で用いられる帯域算出アルゴリズムについて説明する。帯域算出部２０２は、通信網を有向グラフとみなした最大流問題によって帯域上限値を算出する。
【００４４】
最大流問題によって帯域上限値を算出するために、通信網に仮の送信元ノードs及び仮の宛先ノードdを追加する。仮の送信元ノードs及び仮の宛先ノードdを通信網の各通信リンクに接続した仮の通信網において、リンクaに障害が発生した場合に、仮の送信元ノードsから出る最大の流量φを算出する。そして、障害想定リンクaを変化させて、トラヒックの最大値を求めることで、設計対象リンクbの迂回用パスで必要となる帯域上限値が求められる。
【００４５】
具体的には、以下のステップで求める。
【００４６】
ステップ１：障害想定リンクa及び設計対象リンクb（a≠b）を選択する。
【００４７】
ステップ２：
【００４８】
【数６】
を算出する。なお、現用パスの経路は、パス情報データベース２１１に格納されている。また、迂回用パスの経路は、パス情報データベース２１１に格納される。
【００４９】
ステップ３：通信網に属するノードの集合Nに、仮の送信元ノードs及仮の宛先ノードdを追加して以下のN'を作る。
【００５０】
N':=N∪{s}∪{d}
更に、通信網に属するリンクの集合Eに、リンクsi:=(s,i), i∈N及びdi:=(j,d), j∈Nを追加して以下のE'を作る。
【００５１】
E':=E∪{si|i∈N}∪{dj|j∈N}
更に、traf(e)をリンクe上のトラヒックの観測値とし、extin(i)をノードiに流入するトラヒックの観測値とし、extout(j)をノードjから流出するトラヒックの観測値とする。これらのトラヒックの観測値は、トラヒック情報データベース２１２に格納されている。この場合、traf'(si):=extin(i), i∈N、traf'(dj):=extout(j), j∈N及びtraf'(e):=traf(e), e∈Eとし、traf'(e), e∈Eをtraf'(e), e∈E'に拡張して以下のEab及びNabを算出する。
【００５２】
Eab:={e∈E|rije=1, (i,j)∈Uab}∪{si|(i,*)∈Uab}∪{dj|(*,j)∈Uab}⊂E'
Nab:={i∈N'|(i,*)∈Eab}∪{j∈N'|(*,j)∈Eab}
traf'(e)は、トラヒック情報データベース２１２に格納される。
【００５３】
ステップ４：ネットワークGab={Nab,Eab}と各リンクの正の容量traf':Eab→R+を入力として、各リンクの流量φ:Eab→R+の中で仮の送信元ノードsから出る流量が最大となるφを求める。φは、以下の制約条件を満たす。
【００５４】
【数７】
この制約条件について説明する。通信リンクaが故障したときに、通信リンクbを疎通するトラヒックは、(i,j)∈Uabを送信元、宛先とする現用パスの流量の総和である。この現用パスの流量は、入出力トラヒックの制約から送信元ノードi、宛先ノードjにおいて、それぞれextin(i)、extout(j)よりも小さくなければならず、各リンクにおいては、traf(e), e∈Eより小さくなければならない。これを整理すると、流量φは、上記の容量制約及び流量保存則を満たすことになる。
【００５５】
これらの制約条件の下で、sから出るφを最大化した値が、通信リンクaが故障したときに、迂回用パスが通信リンクbを疎通する最大トラヒックとなる。より具体的には、リンクaに障害が発生した場合にリンクbで必要となる帯域上限値Cabを以下の式：
【００５６】
【数８】
に従って算出する。
【００５７】
ステップ５：通信リンクaを変化させて、トラヒックの最大値を求める。より具体的には、以下の式：
【００５８】
【数９】
を計算する。計算されたCbが、設計対象リンクbの迂回用パスで必要となる帯域上限値になる。
【００５９】
上記の最大流問題は、Dinicの増加道法により高速に解くことができる（非特許文献３参照）。
【００６０】
＜計算量の比較＞
線形計画法による解法と最大流問題による解法の計算量を比較すると、次のようになる。
【００６１】
線形計画法はシンプレックス法と内点法があるが、ここではシンプレックス法を取り扱う。シンプレックス法は多項式オーダーで解けることが証明されていないが、通常は高速に解くことができる。制約式の個数をp、変数の個数をqとおくと、１回のピボット演算にかかる計算量は、改訂シンプレックス法を用いれば、たかだかO(p2q)程度の計算量ですんでしまう。シンプレックス法が収束するまでの総ピボット数は、現存するほとんどのピボット規則が採用しているアドミッシブルピボット（admissible pivot）という枠組みにおいて、任意の基底解から最適基底解へ、たかだか(p+q)回のアドミッシブルピボットで到達可能であることが証明されている（非特許文献４参照）。これを通常に解かれている状況であると解釈すれば、シンプレックス法では、通常p2(p+q)qで解けることになる。これ以上の計算が必要なことも当然あるが、これを速く計算できた場合の計算量ととらえて、最大流問題を用いた場合にはこれよりも速いことを示せばよい。
【００６２】
|N|=n,|E|=mとおく。上記の線形計画問題では、p=n(n-1),q=2n+m、線形計画法の繰り返し数：m(m-1)より、トータルの計算量のオーダはn2(n-1)2(n(n-1)+l+2n)(2n+m)m(m-1)となる。
【００６３】
一方、上記の最大流問題では、ステップ２:n(n-1)、ステップ４:n2m、最大流問題の繰り返し数：m(m-1)となる。なお、ステップ４はDinicの増加道法による。トータルの計算量のオーダはn3(n-1)m2(m-1)となる。この式自体が線形計画法の計算量のオーダよりも小さいが、ステップ２は実際には、|Uab|(<<n(n-1))のオーダなので計算はもっと速くなる。
【００６４】
＜帯域算出アルゴリズムの具体例＞
以上のアルゴリズムを図１及び図３によって説明する。図１はノードA〜Dからなるリング型通信網を示す。通信リンクb=ADを迂回用パスの帯域を求めたい通信リンクとする。このときリンクa=BAが故障していて使えないとする。ここで図１（Ａ）の矢印の示すように故障前に現用パスのトラヒックが流れていたものとする。各矢印のトラヒックは、すべて１とする。通信リンクaの故障後、迂回用パスで通信リンクbを疎通するものは、図１（Ｂ）右図の実線矢印となる。この２つの迂回用パスを流れるトラヒックは、対応する点線の矢印で示した現用パスを流れるトラヒックと量的に等しい。したがって、この２つの迂回用パスを流れる最大のトラヒックは、対応する現用パスのトラヒックを最大化した値に等しい。現用パスBAを流れるトラヒックをt(BA)、現用パスCBAを流れるトラヒックをt(CBA)とする。以下同様の表記法を用いる。線形計画法によるモデルは以下のようになる。
【００６５】
目的関数：
Max t(BA)+t(CBA) (6)
制約条件：
t(BA)+t(CBA)+t(BAD)≦3 (7)
t(CB)+t(CBA)+t(DCB)≦3 (8)
t(DC)+t(DCB)≦2 (9)
t(AD)+t(BAD)≦2 (10)
t(AD)≦1 (11)
t(DC)+t(DCB)≦2 (12)
t(CB)+t(CBA)≦2 (13)
t(BA)+t(BAD)≦2 (14)
t(BA)+t(CBA)≦2 (15)
t(AD)+t(BAD)≦2 (16)
t(DC)≦1 (17)
t(CB)+t(DCB)≦2 (18)
但し、各変数の値は0以上である。
【００６６】
このモデルを解いたとき、目的関数の最大値が通信リンクaが故障したときに、故障リンクbを疎通する迂回用パスが取りうるトラヒックの最大値となる。
【００６７】
このモデルを、先に述べた最大流問題に変換すると、計算が簡単化し、高速計算が可能になる。目的関数は同じくt(BA)+t(CBA)に相当し、これを最大化させるが、最大流問題では、この２つの現用パスを拡張したネットワークの中で最大流問題を解くことに帰着させる。
【００６８】
図３に示すように仮の送信元ノードs及び宛先ノードdを設け、現用パスBAとCBAの始点と終点を延長する。図１（Ａ）と比べ合わせて、リンクsB,sCでは流量は2以下、リンクCBでは流量は3以下、リンクBAでは流量は3以下、リンクAdでは流量は2以下となる。これは各リンクまたはノードで観測されたトラヒック以上のトラヒックは流れていないという制約である。このとき、流量のボトルネックとなるのはリンクAdの流量制約2なので、最大流は2であることが分かる。この最大流の値が通信リンクaが故障したときに通信リンクbを疎通する迂回用パスの最大トラヒックとなる。実際には最大流はDinicの増加道法を用いて求めることができる。
【００６９】
＜実施例の効果＞
本発明の実施例によれば、通信網においてトラヒックを転送する現用パス及び迂回用パスの情報が与えられており、障害がなく現用パスを流れるトラヒックが、通信リンクにおいて観測されているが、個々のＳＤペア間を流れる交流トラヒックが分からない状況において、迂回用パスに必要な設計対象リンクの帯域を算出することができる。なお、迂回用パスの帯域は、複数の現用パスにより共用可能である。
【００７０】
帯域の算出に際して、本発明の実施例では、通信網を有向グラフとみなした最大流問題によって帯域上限値を算出する。線形計画法では、帯域の算出に時間がかかるが、本発明の実施例によれば、最大流問題を解くことで迂回用パスの必要最低限の帯域を高速に算出することができる。
【００７１】
説明の便宜上、本発明の実施例に係るシステムは機能的なブロック図を用いて説明しているが、本発明のシステムは、ハードウエア、ソフトウェア又はそれらの組み合わせで実現されてもよい。例えば、帯域算出装置２０の各機能部がソフトウェアで実現され、オペレーションシステム１０内にインストールされてもよい。また、２以上の実施例が必要に応じて組み合わせて使用されてもよい。
【００７２】
以上、本発明の実施例について説明したが、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【符号の説明】
【００７３】
１０ オペレーションシステム
２０ 帯域算出装置
３０ 帯域表示装置
１０１ ネットワークデータ収集部
１１１ ネットワーク情報データベース
２０１ データ取得部
２０２ 帯域算出部
２１１ パス情報データベース
２１２ トラヒック情報データベース
３０１ 帯域表示部
【技術分野】
【０００１】
本発明は、帯域算出方法、帯域算出装置及びプログラムに関する。より具体的には、本発明は、障害時に選択される迂回用パスに必要な通信リンクの帯域上限値を算出する帯域算出方法、帯域算出装置及びプログラムに関する。
【背景技術】
【０００２】
通信リンクには、耐障害性を高めるために、現用パスに対して迂回用パスが設定される。迂回用パスに必要な帯域を算出する方法として、以下の方法が検討されている。
【０００３】
詳細に迂回用パスで利用されている必要帯域上限値を計算せず、Ringネットワークにおいて逆方向に流れるトラヒックの通信リンクでの最大量を想定するなど自明な解を用いて上限値を導出する方法がある。この方法は高速ではあるが、この方法で得られる解は、必要帯域の上界を求めるものであり、ケースによっては過剰な量の帯域を算出するという問題がある。
【０００４】
通信リンクを流れるトラヒックの情報より、送信元・宛先（ＳＤ：Source-Destination）ペア間の交流トラヒックを推定するNetwork-Tomographyという方法がある（非特許文献１参照）。このNetwork-Tomographyにより推定された交流トラヒックより迂回用パスに必要な帯域を求めることも可能である。しかし、Network-Tomographyでは、交流トラヒックは、ポアソン分布又は正規分布を仮定して、最尤法等を用いて平均値を算出するものであり、迂回用パスに必要な帯域上限値を保証するものではないという問題がある。
【０００５】
これらの問題を解決するものとして、通信リンクを流れるトラヒックや端点ノードにおける流出入トラヒックの観測データを制約式に組み込み、通信リンクを流れる迂回用パスに必要な帯域を線形計画法によって最大化する帯域算出手法がConstraint Programmingとして考案されている（非特許文献２参照）。この手法は、迂回用パスに必要な通信リンクでの帯域上限値を導出する目的としては、理想的な結果を算出する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】A. Medina et al. "Traffic Matrix Estimation: Existing Techniques and New Directions," Proceedings of the 2002 SIGCOMM conference, 2002.
【非特許文献２】H. Simonis, "Constraint Based Resilience Analysis," LNCS, Vol. 4204, 16-28, 2006.
【非特許文献３】久保幹雄，田村明久，松井知己．応用数理計画ハンドブック．朝倉書店，379-380,2002.
【非特許文献４】Komei Fukuda, Tamas Terlaky, "On the existence of a short admissible pivot sequence for feasibility and linear optimization problems," Elsevier, 1999.
【特許文献】
【０００７】
【特許文献１】特願2010-34273
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記のように、Constraint Programmingは、迂回用パスに必要な通信リンクでの帯域上限値を導出できるが、迂回用パスが複数の現用パスにより共用されるshared protection制約の下で適用しようとすると、故障通信リンク毎に、それぞれ大規模な線形計画法を繰り返し解かなければならず計算時間がかかるという問題がある。
【０００９】
この計算時間を削減するために、線形計画法の制約式の中に目的関数の下限値を繰りこむことも可能である（特許文献１参照）。しかし、線形計画法を用いているため、抜本的な高速化には到らない。
【００１０】
そこで、本発明は、迂回用パスに必要な帯域を算出する際の計算量を削減することができる帯域算出方法、帯域算出装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の帯域算出方法は、
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置における帯域算出方法であって、
通信リンクを流れるトラヒック量を取得するステップと、
現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出するステップと、
前記第１の通信リンクを選択し直して前記算出するステップを繰り返すことにより、迂回用パスで必要となる通信リンクの帯域上限値を算出するステップと、
を有することを特徴とする。
【００１２】
また、本発明の帯域算出装置は、
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置であって、
通信リンクを流れるトラヒック量を取得するトラヒック取得部と、
現用パス及び迂回用パスの情報を格納するパス情報格納部と、
前記パス情報格納部から、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出する帯域算出部と、
を有し、
前記帯域算出部は、前記第１の通信リンクを選択し直し、迂回用パスで必要となる通信リンクの帯域上限値を算出することを特徴とする。
【００１３】
また、本発明のプログラムは、
現用パス及び迂回用パスの情報を格納するパス情報格納部を有する帯域算出装置であり、現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置を、
通信リンクを流れるトラヒック量を取得するトラヒック取得手段、
前記パス情報格納部から、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出する帯域算出手段、
として機能させ、
前記帯域算出手段は、前記第１の通信リンクを選択し直し、迂回用パスで必要となる通信リンクの帯域上限値を算出することを特徴とする。
【発明の効果】
【００１４】
本発明の実施例によれば、迂回用パスに必要な帯域を算出する際の計算量を削減することができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施例に係る故障前後の通信網を示す図
【図２】本発明の実施例に係る通信システムを示す図
【図３】本発明の実施例に係る帯域算出方法の概念図
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施例について説明する。
【００１７】
図１は、本発明の実施例に係る通信網を示す図である。通信網は、複数のノードA〜Dと、ノード間を接続する通信リンクとから構成される。通信網には、単数又は複数の送信元ノード及び宛先ノードのペア（ＳＤペア：Source-Destinationペア）が存在する。ＳＤペア間には、現用パスと迂回用パスとが予め設定されているものとする。現用パスとは、障害が発生しない通常時に利用するパスであり、迂回用パスとは、現用パス上で障害が発生した障害時に利用するパスである。なお、迂回用パスの帯域は、複数の現用パスにより共用可能である。
【００１８】
図１（Ａ）は、故障前の現用パスの例を示しており、現用パスAD、DC、DB、BA、BAD、DCB、CBAが設定されている。現用パスが設定されているノードAとノードBの間の通信リンクａに障害が発生した場合、ＳＤペア間のトラヒックは、迂回用パスに流れる。現用パスBAは迂回用パスBCDAに流れ、現用パスBADは迂回用パスBCDに流れ、現用パスCBAは迂回用パスCDAに流れる。
【００１９】
図１（Ｂ）は、故障後の迂回用パスで、ノードAとノードDとの間のリンクbを疎通するものを示している。具体的には、現用パスBAの迂回用パスBCDAと、現用パスCBAの迂回用パスCDAとが、リンクbを疎通する。この場合、迂回用パスに必要な帯域が予め設定されていなければ、通信品質が低下する。このため、本発明の実施例では、障害が発生していないときに通信網上の通信リンクを流れるトラヒック量を観測しておき、観測されたトラヒック量から、迂回用パスの特定の通信リンクに必要な帯域上限値を算出する。ここで、迂回用パスに必要な帯域上限値を算出する通信リンクを「設計対象リンク」と呼ぶ。障害は、同時に単一の通信リンクで発生することを想定する。
【００２０】
この帯域上限値を算出するために、設計対象リンクに設定されている迂回用パスに対応する現用パスが経由する通信リンクで障害が発生したことを想定し、その際の設計対象リンクでの影響を考える。ここで、障害の発生を想定する通信リンクを「障害想定リンク」と呼ぶ。この障害想定リンクの障害に伴う迂回用パスが設計対象リンクで必要とする帯域上限値を算出する問題は、最大化問題として定式化できる。本発明の実施例では、最大化問題を線形計画法を用いて解くのではなく、通信網を有向グラフとみなした最大流問題によって帯域上限値を算出する。そして、全体の通信網上での必要帯域の算出を行う。
【００２１】
＜通信システムの構成＞
図２は、本発明の実施例に係る通信システムを示す図である。本発明の実施例に係る通信システムは、図１に示すような通信網と、オペレーションシステム１０と、帯域算出装置２０と、帯域表示装置３０とを有する。
【００２２】
オペレーションシステム１０は、通信網上のノード及び通信リンクを運用管理する装置である。オペレーションシステム１０は、機能部としてのネットワークデータ収集部１０１と、データベースとしてのネットワーク情報データベース１１１とを有する。
【００２３】
ネットワークデータ収集部１０１は、オペレーションシステム１０が管理する通信網上のノードに接続する通信リンクを流れるトラヒック量を収集し、トラヒック情報としてネットワーク情報データベース１１１に蓄積する。また、通信網の運用者等により設定された現用パス及び迂回用パスに関する情報は、パス情報としてネットワーク情報データベース１１１に蓄積される。
【００２４】
帯域算出装置２０は、オペレーションシステム１０に接続されており、オペレーションシステム１０からトラヒック情報及びパス情報を取得し、取得したデータを用いて迂回用パスの設計対象リンクに必要な帯域を算出する。帯域算出装置２０は、通信網の運用者又は設計者が直接操作する帯域算出装置２０からの要求を受け付け、算出した必要な帯域に関する情報を帯域表示装置３０に送信する。
【００２５】
帯域算出装置２０は、機能部としてのデータ取得部２０１及び帯域算出部２０２を有し、データベースとしてのパス情報データベース２１１及びトラヒック情報データベース２１２を有する。
【００２６】
データ取得部２０１は、オペレーションシステム１０がネットワーク情報データベース１１１で管理する情報のうち、帯域の算出に必要な情報として、パス情報及びトラヒック情報を取得し、それぞれ、パス情報データベース２１１及びトラヒック情報データベース２１２に蓄積する。
【００２７】
帯域算出部２０２は、パス情報データベース２１１及びトラヒック情報データベース２１２に蓄積されたパス情報及びトラヒック情報を用いて、迂回用パスの設計対象リンクに必要な帯域上界値及び帯域上限値を計算する。帯域上限値を算出するための帯域算出アルゴリズムについては、後述する。
【００２８】
帯域表示装置３０は、帯域算出装置２０に接続されており、算出された帯域上限値を表示する。
【００２９】
帯域表示装置３０は、機能部としての帯域表示部３０１を有する。
【００３０】
帯域表示部３０１は、通信網の運用者又は設計者による操作を受け付け、帯域算出装置２０に対して、設計対象リンクについて算出された帯域上限値の取得要求を実施し、帯域算出装置２０から取得した値を表示する。
【００３１】
＜線形計画法による帯域算出アルゴリズム＞
次に、帯域算出部２０２で用いられる帯域算出アルゴリズムについて説明する。本発明の実施例では、通信網を有向グラフとみなした最大流問題によって帯域上限値を算出するが、比較のため、線形計画法による帯域算出アルゴリズムについて説明する。
【００３２】
対象とする通信網を有向グラフG={N,E}とする。但し、N及びEは、それぞれ通信網に属するノード及び通信リンクの集合とする。
【００３３】
Fij≧0をノードiからノードjへのトラヒック量とする。
【００３４】
rije∈{0,1}によってノードi及びj間の現用パスの経路を示す。具体的には、ノードi及びj間の現用パスがリンクeを通る場合、rije=1とし、通らない場合、rije=0とする。なお、現用パスの経路は、パス情報データベース２１１に格納されている。
【００３５】
【数１】
によってノードi及びj間の迂回用パスの経路を示す。具体的には、ノードi及びj間の迂回用パスがリンクe（設計対象リンク）を通る場合、
【００３６】
【数２】
とし、通らない場合、
【００３７】
【数３】
とする。なお、迂回用パスの経路は、パス情報データベース２１１に格納される。
【００３８】
traf(e)によって、リンクe上のトラヒックの観測値を示す。extin(i)によって、ノードiに流入するトラヒックの観測値を示す。extout(j)によって、ノードjから流出するトラヒックの観測値を示す。これらのトラヒックの観測値は、トラヒック情報データベース２１２に格納されている。
【００３９】
線形計画法によって、通信リンクaが故障したときに通信リンクbにおいて必要になる迂回用パスの帯域を求める式は、次の式(1)で表される。
【００４０】
【数４】
すなわち、次の目的関数
【００４１】
【数５】
の最大値が、リンクaが故障した場合の迂回用パスのリンクbで必要となる帯域上限値を表す。また、式(2)〜式(5)は、式(1)を算出するときの制約式である。
【００４２】
従って、迂回用パスのリンクbで必要となる帯域上限値を算出するためには、式(1)〜式(5)を全ての障害想定リンクaについて計算し、その最大値を算出する必要がある。しかし、線形計画法を繰り返し単純に計算するのでは時間がかかる。本発明の実施例では、以下に説明するように、通信網を有向グラフとみなした最大流問題によって帯域上限値を算出する。
【００４３】
＜最大流問題による帯域算出アルゴリズム＞
次に、帯域算出部２０２で用いられる帯域算出アルゴリズムについて説明する。帯域算出部２０２は、通信網を有向グラフとみなした最大流問題によって帯域上限値を算出する。
【００４４】
最大流問題によって帯域上限値を算出するために、通信網に仮の送信元ノードs及び仮の宛先ノードdを追加する。仮の送信元ノードs及び仮の宛先ノードdを通信網の各通信リンクに接続した仮の通信網において、リンクaに障害が発生した場合に、仮の送信元ノードsから出る最大の流量φを算出する。そして、障害想定リンクaを変化させて、トラヒックの最大値を求めることで、設計対象リンクbの迂回用パスで必要となる帯域上限値が求められる。
【００４５】
具体的には、以下のステップで求める。
【００４６】
ステップ１：障害想定リンクa及び設計対象リンクb（a≠b）を選択する。
【００４７】
ステップ２：
【００４８】
【数６】
を算出する。なお、現用パスの経路は、パス情報データベース２１１に格納されている。また、迂回用パスの経路は、パス情報データベース２１１に格納される。
【００４９】
ステップ３：通信網に属するノードの集合Nに、仮の送信元ノードs及仮の宛先ノードdを追加して以下のN'を作る。
【００５０】
N':=N∪{s}∪{d}
更に、通信網に属するリンクの集合Eに、リンクsi:=(s,i), i∈N及びdi:=(j,d), j∈Nを追加して以下のE'を作る。
【００５１】
E':=E∪{si|i∈N}∪{dj|j∈N}
更に、traf(e)をリンクe上のトラヒックの観測値とし、extin(i)をノードiに流入するトラヒックの観測値とし、extout(j)をノードjから流出するトラヒックの観測値とする。これらのトラヒックの観測値は、トラヒック情報データベース２１２に格納されている。この場合、traf'(si):=extin(i), i∈N、traf'(dj):=extout(j), j∈N及びtraf'(e):=traf(e), e∈Eとし、traf'(e), e∈Eをtraf'(e), e∈E'に拡張して以下のEab及びNabを算出する。
【００５２】
Eab:={e∈E|rije=1, (i,j)∈Uab}∪{si|(i,*)∈Uab}∪{dj|(*,j)∈Uab}⊂E'
Nab:={i∈N'|(i,*)∈Eab}∪{j∈N'|(*,j)∈Eab}
traf'(e)は、トラヒック情報データベース２１２に格納される。
【００５３】
ステップ４：ネットワークGab={Nab,Eab}と各リンクの正の容量traf':Eab→R+を入力として、各リンクの流量φ:Eab→R+の中で仮の送信元ノードsから出る流量が最大となるφを求める。φは、以下の制約条件を満たす。
【００５４】
【数７】
この制約条件について説明する。通信リンクaが故障したときに、通信リンクbを疎通するトラヒックは、(i,j)∈Uabを送信元、宛先とする現用パスの流量の総和である。この現用パスの流量は、入出力トラヒックの制約から送信元ノードi、宛先ノードjにおいて、それぞれextin(i)、extout(j)よりも小さくなければならず、各リンクにおいては、traf(e), e∈Eより小さくなければならない。これを整理すると、流量φは、上記の容量制約及び流量保存則を満たすことになる。
【００５５】
これらの制約条件の下で、sから出るφを最大化した値が、通信リンクaが故障したときに、迂回用パスが通信リンクbを疎通する最大トラヒックとなる。より具体的には、リンクaに障害が発生した場合にリンクbで必要となる帯域上限値Cabを以下の式：
【００５６】
【数８】
に従って算出する。
【００５７】
ステップ５：通信リンクaを変化させて、トラヒックの最大値を求める。より具体的には、以下の式：
【００５８】
【数９】
を計算する。計算されたCbが、設計対象リンクbの迂回用パスで必要となる帯域上限値になる。
【００５９】
上記の最大流問題は、Dinicの増加道法により高速に解くことができる（非特許文献３参照）。
【００６０】
＜計算量の比較＞
線形計画法による解法と最大流問題による解法の計算量を比較すると、次のようになる。
【００６１】
線形計画法はシンプレックス法と内点法があるが、ここではシンプレックス法を取り扱う。シンプレックス法は多項式オーダーで解けることが証明されていないが、通常は高速に解くことができる。制約式の個数をp、変数の個数をqとおくと、１回のピボット演算にかかる計算量は、改訂シンプレックス法を用いれば、たかだかO(p2q)程度の計算量ですんでしまう。シンプレックス法が収束するまでの総ピボット数は、現存するほとんどのピボット規則が採用しているアドミッシブルピボット（admissible pivot）という枠組みにおいて、任意の基底解から最適基底解へ、たかだか(p+q)回のアドミッシブルピボットで到達可能であることが証明されている（非特許文献４参照）。これを通常に解かれている状況であると解釈すれば、シンプレックス法では、通常p2(p+q)qで解けることになる。これ以上の計算が必要なことも当然あるが、これを速く計算できた場合の計算量ととらえて、最大流問題を用いた場合にはこれよりも速いことを示せばよい。
【００６２】
|N|=n,|E|=mとおく。上記の線形計画問題では、p=n(n-1),q=2n+m、線形計画法の繰り返し数：m(m-1)より、トータルの計算量のオーダはn2(n-1)2(n(n-1)+l+2n)(2n+m)m(m-1)となる。
【００６３】
一方、上記の最大流問題では、ステップ２:n(n-1)、ステップ４:n2m、最大流問題の繰り返し数：m(m-1)となる。なお、ステップ４はDinicの増加道法による。トータルの計算量のオーダはn3(n-1)m2(m-1)となる。この式自体が線形計画法の計算量のオーダよりも小さいが、ステップ２は実際には、|Uab|(<<n(n-1))のオーダなので計算はもっと速くなる。
【００６４】
＜帯域算出アルゴリズムの具体例＞
以上のアルゴリズムを図１及び図３によって説明する。図１はノードA〜Dからなるリング型通信網を示す。通信リンクb=ADを迂回用パスの帯域を求めたい通信リンクとする。このときリンクa=BAが故障していて使えないとする。ここで図１（Ａ）の矢印の示すように故障前に現用パスのトラヒックが流れていたものとする。各矢印のトラヒックは、すべて１とする。通信リンクaの故障後、迂回用パスで通信リンクbを疎通するものは、図１（Ｂ）右図の実線矢印となる。この２つの迂回用パスを流れるトラヒックは、対応する点線の矢印で示した現用パスを流れるトラヒックと量的に等しい。したがって、この２つの迂回用パスを流れる最大のトラヒックは、対応する現用パスのトラヒックを最大化した値に等しい。現用パスBAを流れるトラヒックをt(BA)、現用パスCBAを流れるトラヒックをt(CBA)とする。以下同様の表記法を用いる。線形計画法によるモデルは以下のようになる。
【００６５】
目的関数：
Max t(BA)+t(CBA) (6)
制約条件：
t(BA)+t(CBA)+t(BAD)≦3 (7)
t(CB)+t(CBA)+t(DCB)≦3 (8)
t(DC)+t(DCB)≦2 (9)
t(AD)+t(BAD)≦2 (10)
t(AD)≦1 (11)
t(DC)+t(DCB)≦2 (12)
t(CB)+t(CBA)≦2 (13)
t(BA)+t(BAD)≦2 (14)
t(BA)+t(CBA)≦2 (15)
t(AD)+t(BAD)≦2 (16)
t(DC)≦1 (17)
t(CB)+t(DCB)≦2 (18)
但し、各変数の値は0以上である。
【００６６】
このモデルを解いたとき、目的関数の最大値が通信リンクaが故障したときに、故障リンクbを疎通する迂回用パスが取りうるトラヒックの最大値となる。
【００６７】
このモデルを、先に述べた最大流問題に変換すると、計算が簡単化し、高速計算が可能になる。目的関数は同じくt(BA)+t(CBA)に相当し、これを最大化させるが、最大流問題では、この２つの現用パスを拡張したネットワークの中で最大流問題を解くことに帰着させる。
【００６８】
図３に示すように仮の送信元ノードs及び宛先ノードdを設け、現用パスBAとCBAの始点と終点を延長する。図１（Ａ）と比べ合わせて、リンクsB,sCでは流量は2以下、リンクCBでは流量は3以下、リンクBAでは流量は3以下、リンクAdでは流量は2以下となる。これは各リンクまたはノードで観測されたトラヒック以上のトラヒックは流れていないという制約である。このとき、流量のボトルネックとなるのはリンクAdの流量制約2なので、最大流は2であることが分かる。この最大流の値が通信リンクaが故障したときに通信リンクbを疎通する迂回用パスの最大トラヒックとなる。実際には最大流はDinicの増加道法を用いて求めることができる。
【００６９】
＜実施例の効果＞
本発明の実施例によれば、通信網においてトラヒックを転送する現用パス及び迂回用パスの情報が与えられており、障害がなく現用パスを流れるトラヒックが、通信リンクにおいて観測されているが、個々のＳＤペア間を流れる交流トラヒックが分からない状況において、迂回用パスに必要な設計対象リンクの帯域を算出することができる。なお、迂回用パスの帯域は、複数の現用パスにより共用可能である。
【００７０】
帯域の算出に際して、本発明の実施例では、通信網を有向グラフとみなした最大流問題によって帯域上限値を算出する。線形計画法では、帯域の算出に時間がかかるが、本発明の実施例によれば、最大流問題を解くことで迂回用パスの必要最低限の帯域を高速に算出することができる。
【００７１】
説明の便宜上、本発明の実施例に係るシステムは機能的なブロック図を用いて説明しているが、本発明のシステムは、ハードウエア、ソフトウェア又はそれらの組み合わせで実現されてもよい。例えば、帯域算出装置２０の各機能部がソフトウェアで実現され、オペレーションシステム１０内にインストールされてもよい。また、２以上の実施例が必要に応じて組み合わせて使用されてもよい。
【００７２】
以上、本発明の実施例について説明したが、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【符号の説明】
【００７３】
１０ オペレーションシステム
２０ 帯域算出装置
３０ 帯域表示装置
１０１ ネットワークデータ収集部
１１１ ネットワーク情報データベース
２０１ データ取得部
２０２ 帯域算出部
２１１ パス情報データベース
２１２ トラヒック情報データベース
３０１ 帯域表示部
【特許請求の範囲】
【請求項１】
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置における帯域算出方法であって、
通信リンクを流れるトラヒック量を取得するステップと、
現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出するステップと、
前記第１の通信リンクを選択し直して前記算出するステップを繰り返すことにより、迂回用パスで必要となる通信リンクの帯域上限値を算出するステップと、
を有する帯域算出方法。
【請求項２】
前記算出するステップは、通信網に仮の送信元ノード及び仮の宛先ノードを追加し、前記仮の送信元ノード及び前記仮の宛先ノードを通信網の各通信リンクに接続した仮の通信網において、前記第１の通信リンクに障害が発生した場合に、前記仮の送信元ノードから出る最大の流量を算出する、請求項１に記載の帯域算出方法。
【請求項３】
前記算出するステップは、前記第１の通信リンクをaとし、前記第２の通信リンクをbとした場合、
【数１０】
を算出し、
通信網に属するノードの集合Nに、仮の送信元ノードs及仮の宛先ノードdを追加して以下のN'を作り、
N':=N∪{s}∪{d}
更に、通信網に属するリンクの集合Eに、リンクsi:=(s,i), i∈N及びdi:=(j,d), j∈Nを追加して以下のE'を作り、
E':=E∪{si|i∈N}∪{dj|j∈N}
更に、traf(e)をリンクe上のトラヒックの観測値とし、extin(i)をノードiに流入するトラヒックの観測値とし、extout(j)をノードjから流出するトラヒックの観測値とした場合、traf'(si):=extin(i), i∈N、traf'(dj):=extout(j), j∈N及びtraf'(e):=traf(e), e∈Eとし、traf'(e), e∈Eをtraf'(e), e∈E'に拡張して以下のEab及びNabを算出し、
Eab:={e∈E|rije=1, (i,j)∈Uab}∪{si|(i,*)∈Uab}∪{dj|(*,j)∈Uab}⊂E'
Nab:={i∈N'|(i,*)∈Eab}∪{j∈N'|(*,j)∈Eab}
仮の通信網Gab={Nab,Eab}と各リンクの正の容量traf':Eab→R+を入力として、各リンクの流量φ:Eab→R+の中で仮の送信元ノードsから出る流量が最大となるφを、以下の制約条件：
【数１１】
を加えて算出し、
前記第１の通信リンクaに障害が発生した場合に前記第２の通信リンクbで必要となる帯域上限値Cabを以下の式：
【数１２】
に従って算出し、
前記繰り返すステップは、前記第２の通信リンクbで必要となる帯域上限値を以下の式：
【数１３】
に従って算出する、請求項１又は２に記載の帯域算出方法。
【請求項４】
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置であって、
通信リンクを流れるトラヒック量を取得するトラヒック取得部と、
現用パス及び迂回用パスの情報を格納するパス情報格納部と、
前記パス情報格納部から、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出する帯域算出部と、
を有し、
前記帯域算出部は、前記第１の通信リンクを選択し直し、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置。
【請求項５】
現用パス及び迂回用パスの情報を格納するパス情報格納部を有する帯域算出装置であり、現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置を、
通信リンクを流れるトラヒック量を取得するトラヒック取得手段、
前記パス情報格納部から、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出する帯域算出手段、
として機能させ、
前記帯域算出手段は、前記第１の通信リンクを選択し直し、迂回用パスで必要となる通信リンクの帯域上限値を算出するプログラム。
【請求項１】
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置における帯域算出方法であって、
通信リンクを流れるトラヒック量を取得するステップと、
現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出するステップと、
前記第１の通信リンクを選択し直して前記算出するステップを繰り返すことにより、迂回用パスで必要となる通信リンクの帯域上限値を算出するステップと、
を有する帯域算出方法。
【請求項２】
前記算出するステップは、通信網に仮の送信元ノード及び仮の宛先ノードを追加し、前記仮の送信元ノード及び前記仮の宛先ノードを通信網の各通信リンクに接続した仮の通信網において、前記第１の通信リンクに障害が発生した場合に、前記仮の送信元ノードから出る最大の流量を算出する、請求項１に記載の帯域算出方法。
【請求項３】
前記算出するステップは、前記第１の通信リンクをaとし、前記第２の通信リンクをbとした場合、
【数１０】
を算出し、
通信網に属するノードの集合Nに、仮の送信元ノードs及仮の宛先ノードdを追加して以下のN'を作り、
N':=N∪{s}∪{d}
更に、通信網に属するリンクの集合Eに、リンクsi:=(s,i), i∈N及びdi:=(j,d), j∈Nを追加して以下のE'を作り、
E':=E∪{si|i∈N}∪{dj|j∈N}
更に、traf(e)をリンクe上のトラヒックの観測値とし、extin(i)をノードiに流入するトラヒックの観測値とし、extout(j)をノードjから流出するトラヒックの観測値とした場合、traf'(si):=extin(i), i∈N、traf'(dj):=extout(j), j∈N及びtraf'(e):=traf(e), e∈Eとし、traf'(e), e∈Eをtraf'(e), e∈E'に拡張して以下のEab及びNabを算出し、
Eab:={e∈E|rije=1, (i,j)∈Uab}∪{si|(i,*)∈Uab}∪{dj|(*,j)∈Uab}⊂E'
Nab:={i∈N'|(i,*)∈Eab}∪{j∈N'|(*,j)∈Eab}
仮の通信網Gab={Nab,Eab}と各リンクの正の容量traf':Eab→R+を入力として、各リンクの流量φ:Eab→R+の中で仮の送信元ノードsから出る流量が最大となるφを、以下の制約条件：
【数１１】
を加えて算出し、
前記第１の通信リンクaに障害が発生した場合に前記第２の通信リンクbで必要となる帯域上限値Cabを以下の式：
【数１２】
に従って算出し、
前記繰り返すステップは、前記第２の通信リンクbで必要となる帯域上限値を以下の式：
【数１３】
に従って算出する、請求項１又は２に記載の帯域算出方法。
【請求項４】
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置であって、
通信リンクを流れるトラヒック量を取得するトラヒック取得部と、
現用パス及び迂回用パスの情報を格納するパス情報格納部と、
前記パス情報格納部から、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出する帯域算出部と、
を有し、
前記帯域算出部は、前記第１の通信リンクを選択し直し、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置。
【請求項５】
現用パス及び迂回用パスの情報を格納するパス情報格納部を有する帯域算出装置であり、現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置を、
通信リンクを流れるトラヒック量を取得するトラヒック取得手段、
前記パス情報格納部から、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、通信網を有向グラフとみなした最大流問題を解くことによって算出する帯域算出手段、
として機能させ、
前記帯域算出手段は、前記第１の通信リンクを選択し直し、迂回用パスで必要となる通信リンクの帯域上限値を算出するプログラム。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２０１２−１７５３９０（Ｐ２０１２−１７５３９０Ａ）
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願番号】特願２０１１−３５２０２（Ｐ２０１１−３５２０２）
【出願日】平成２３年２月２１日（２０１１．２．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願日】平成２３年２月２１日（２０１１．２．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]