帯域算出方法及び帯域算出装置
【課題】迂回用パスに必要な帯域を算出する際の計算量を削減することを目的とする。
【解決手段】現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置における帯域算出方法は、通信リンクを流れるトラヒック量を取得するステップと、現用パス上で障害の発生を想定する第１の通信リンクを選択するステップと、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、線形計画化法によって、前記トラヒック量を制約条件に用いる関数の最大値として算出するステップと、前記選択するステップと前記算出するステップとを繰り返すステップと、を有し、前記算出するステップは、前記関数が既に算出した算出結果を上回るという制約条件を加えて、帯域上限値を算出する。
【解決手段】現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置における帯域算出方法は、通信リンクを流れるトラヒック量を取得するステップと、現用パス上で障害の発生を想定する第１の通信リンクを選択するステップと、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、線形計画化法によって、前記トラヒック量を制約条件に用いる関数の最大値として算出するステップと、前記選択するステップと前記算出するステップとを繰り返すステップと、を有し、前記算出するステップは、前記関数が既に算出した算出結果を上回るという制約条件を加えて、帯域上限値を算出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、帯域算出方法及び帯域算出装置に関する。より具体的には、本発明は、障害時に選択される迂回用パスに必要な通信リンクの帯域上限値を算出する帯域算出方法及び帯域算出装置に関する。
【背景技術】
【０００２】
通信リンクには、耐障害性を高めるために、現用パスに対して迂回用パスが設定される。迂回用パスに必要な帯域を算出する方法として、以下の方法が検討されている。
【０００３】
通信リンクを流れるトラヒックの情報より、送信元・宛先（ＳＤ：Source-Destination）ペア間の交流トラヒックを推定するNetwork-Tomographyという方法がある（非特許文献１参照）。このNetwork-Tomographyにより推定された交流トラヒックより迂回用パスに必要な帯域を求めることも可能である。しかし、Network-Tomographyでは、交流トラヒックは、ポアソン分布又は正規分布を仮定して、最尤法等を用いて平均値を算出するものであり、迂回用パスに必要な帯域上限値を保証するものではないという問題がある。
【０００４】
上記の問題を解決するため、通信リンクを流れるトラヒックや端点ノードにおける流出入トラヒックの観測データを制約式に組み込み、通信リンクを流れる迂回用パスに必要な帯域を線形計画法によって最大化する帯域算出手法を既に提案している（特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】A. Medina et al. "Traffic Matrix Estimation: Existing Techniques and New Directions," Proceedings of the 2002 SIGCOMM conference, 2002.
【特許文献】
【０００６】
【特許文献１】特願2009-49110「通信帯域算出方法および装置」松村龍太郎、辻野雅之、岩下基
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記のように、特許文献１では、ＳＤペア間のトラヒックが分からないが、通信リンクを流れるトラヒックが観測されている場合に、迂回用パスに必要な通信リンクでの帯域上限値を算出することができる。しかし、特許文献１では、全ての通信リンクについて障害が発生したことを想定して最大化問題を解く必要がある。このため、ネットワークの規模が大きくなるにつれて、計算量が増大するという問題がある。特に、大規模なネットワークでは求解に時間がかかる。
【０００８】
そこで、本発明は、迂回用パスに必要な帯域を算出する際の計算量を削減することができる帯域算出方法及び帯域算出装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するため、本発明の帯域算出方法は、
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置における帯域算出方法であって、
通信リンクを流れるトラヒック量を取得するステップと、
現用パス上で障害の発生を想定する第１の通信リンクを選択するステップと、
前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、線形計画化法によって、前記トラヒック量を制約条件に用いる関数の最大値として算出するステップと、
前記選択するステップと前記算出するステップとを繰り返すステップと、
を有し、
前記算出するステップは、前記関数が既に算出した算出結果を上回るという制約条件を加えて、帯域上限値を算出することを特徴とする。
【００１０】
また、本発明の帯域算出装置は、
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置であって、
通信リンクを流れるトラヒック量を取得するトラヒック取得部と、
現用パス及び迂回用パスの情報を格納するパス情報格納部と、
前記パス情報格納部から、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、線形計画化法によって、前記トラヒック量を制約条件に用いる関数の最大値として算出する帯域算出部と、
を有し、
前記帯域算出部は、前記第１の通信リンクを選択し直し、前記関数が既に算出した算出結果を上回るという制約条件を加えて、帯域上限値を算出することを特徴とする。
【発明の効果】
【００１１】
本発明の実施例によれば、迂回用パスに必要な帯域を算出する際の計算量を削減することができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施例に係る通信網を示す図
【図２】本発明の実施例に係る通信システムを示す図
【図３】帯域下限値を利用した帯域算出方法の概念図
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施例について説明する。
【００１４】
図１は、本発明の実施例に係る通信網を示す図である。通信網は、複数のノードＡ〜Ｄと、ノード間を接続する通信リンク１〜４とから構成される。通信網には、単数又は複数の送信元ノード及び宛先ノードのペア（ＳＤペア：Source-Destinationペア）が存在する。図１では、ノードＡが送信元ノードであり、ノードＣが宛先ノードである。図示しないが、他のＳＤペアも存在し得る。ＳＤペア間には、現用パスと迂回用パスとが予め設定されているものとする。現用パスとは、障害が発生しない通常時に利用するパスであり、迂回用パスとは、現用パス上で障害が発生した障害時に利用するパスである。なお、迂回用パスの帯域は、複数の現用パスにより共用可能である。図１では、通信リンク１及び２に現用パスが設定されており、通信リンク３及び４に迂回用パスが設定されている。
【００１５】
現用パスが設定されている通信リンク１に障害が発生した場合、ＳＤペア間のトラヒックは、迂回用パスに流れる。この場合、迂回用パスに必要な帯域が予め設定されていなければ、通信品質が低下する。このため、本発明では、障害が発生していないときに通信網上の通信リンクを流れるトラヒック量を観測しておき、観測されたトラヒック量から、迂回用パスの特定の通信リンクに必要な帯域上限値を算出する。ここで、迂回用パスに必要な帯域上限値を算出する通信リンクを「設計対象リンク」と呼ぶ。障害は、同時に単一の通信リンクで発生することを想定する。
【００１６】
この帯域上限値を算出するために、設計対象リンクに設定されている迂回用パスに対応する現用パスが経由する通信リンクで障害が発生したことを想定し、その際の設計対象リンクでの影響を考える。ここで、障害の発生を想定する通信リンクを「障害想定リンク」と呼ぶ。この障害想定リンクの障害に伴う迂回用パスが設計対象リンクで必要とする帯域上限値を算出する問題は、最大化問題として定式化できる。全ての障害想定リンクについて、最大化問題を線形計画化法によって算出することで、設計対象リンクの帯域上限値が算出される。
【００１７】
例えば、図１において、通信リンク１（障害想定リンク）で障害が発生したことを想定して、通信リンク４（設計対象リンク）で迂回用パスに必要な帯域上限値を算出する。なお、通信リンク１で障害が発生した場合と、通信リンク２で障害が発生した場合とでは、通信リンク４で迂回用パスに必要な帯域上限値が異なるため、次に、通信リンク２を障害想定リンクとして、設計対象リンクで迂回用パスに必要な帯域上限値を算出する必要がある。本発明の実施例では、通信リンク１で既に算出した算出結果を上回る値を対象として、通信リンク２で障害が発生した場合の帯域上限値を算出する。このように、線形計画化法によって帯域上限値を求めるための目的関数が、既に算出した算出結果を上回るという制約条件を加えることで、計算量を削減する。
【００１８】
＜通信システムの構成＞
図２は、本発明の実施例に係る通信システムを示す図である。本発明の実施例に係る通信システムは、図１に示すような通信網と、オペレーションシステム１０と、帯域算出装置２０と、帯域表示装置３０とを有する。
【００１９】
オペレーションシステム１０は、通信網上のノード及び通信リンクを運用管理する装置である。オペレーションシステム１０は、機能部としてのネットワークデータ収集部１０１と、データベースとしてのネットワーク情報データベース１１１とを有する。
【００２０】
ネットワークデータ収集部１０１は、オペレーションシステム１０が管理する通信網上のノードに接続する通信リンクを流れるトラヒック量を収集し、トラヒック情報としてネットワーク情報データベース１１１に蓄積する。また、通信網の運用者等により設定された現用パス及び迂回用パスに関する情報は、パス情報としてネットワーク情報データベース１１１に蓄積される。
【００２１】
帯域算出装置２０は、オペレーションシステム１０に接続されており、オペレーションシステム１０からトラヒック情報及びパス情報を取得し、取得したデータを用いて迂回用パスの設計対象リンクに必要な帯域を算出する。帯域算出装置２０は、通信網の運用者又は設計者が直接操作する帯域算出装置２０からの要求を受け付け、算出した必要な帯域に関する情報を帯域表示装置３０に送信する。
【００２２】
帯域算出装置２０は、機能部としてのデータ取得部２０１及び帯域算出部２０２を有し、データベースとしてのパス情報データベース２１１及びトラヒック情報データベース２１２を有する。
【００２３】
データ取得部２０１は、オペレーションシステム１０がネットワーク情報データベース１１１で管理する情報のうち、帯域の算出に必要な情報として、パス情報及びトラヒック情報を取得し、それぞれ、パス情報データベース２１１及びトラヒック情報データベース２１２に蓄積する。
【００２４】
帯域算出部２０２は、パス情報データベース２１１及びトラヒック情報データベース２１２に蓄積されたパス情報及びトラヒック情報を用いて、迂回用パスの設計対象リンクに必要な帯域上界値及び帯域上限値を計算する。帯域上限値を算出するための帯域算出アルゴリズムについては、後述する。
【００２５】
帯域表示装置３０は、帯域算出装置２０に接続されており、算出された帯域上限値を表示する。
【００２６】
帯域表示装置３０は、機能部としての帯域表示部３０１を有する。
【００２７】
帯域表示部３０１は、通信網の運用者又は設計者による操作を受け付け、帯域算出装置２０に対して、設計対象リンクについて算出された帯域上限値の取得要求を実施し、帯域算出装置２０から取得した値を表示する。
【００２８】
＜帯域算出アルゴリズム＞
次に、帯域算出部２０２で用いられる帯域算出アルゴリズムについて説明する。
【００２９】
対象とする通信網を有向グラフG={N,E}とする。但し、N及びEは、それぞれ通信網に属するノード及び通信リンクの集合とする。
【００３０】
Fij≧0をノードiからノードjへのトラヒック量とする。
【００３１】
rije∈{0,1}によってノードi及びj間の現用パスの経路を示す。具体的には、ノードi及びj間の現用パスがリンクeを通る場合、rije=1とし、通らない場合、rije=0とする。なお、現用パスの経路は、パス情報データベース２１１に格納されている。
【００３２】
【数１】
によってノードi及びj間の迂回用パスの経路を示す。具体的には、リンクf（障害想定リンク）が故障したときにノードi及びj間の迂回用パスがリンクe（設計対象リンク）を通る場合、
【００３３】
【数２】
とし、通らない場合、
【００３４】
【数３】
とする。なお、迂回用パスの経路は、パス情報データベース２１１に格納される。
【００３５】
traf(e)によって、リンクe上のトラヒックの観測値を示す。extin(i)によって、ノードiに流入するトラヒックの観測値を示す。extout(j)によって、ノードjから流出するトラヒックの観測値を示す。これらのトラヒックの観測値は、トラヒック情報データベース２１２に格納されている。
【００３６】
線形計画法によって、通信リンクfが故障したときに通信リンクeにおいて必要になる迂回用パスの帯域を求める式は、次の式(1)で表される。
【００３７】
【数４】
すなわち、次の目的関数
【００３８】
【数５】
の最大値が、リンクfが故障した場合の迂回用パスのリンクeで必要となる帯域上限値を表す。また、式(2)〜式(5)は、式(1)を算出するときの制約式である。
【００３９】
従って、迂回用パスのリンクeで必要となる帯域上限値を算出するためには、式(1)〜式(5)を全ての障害想定リンクfについて計算し、その最大値を算出する必要がある。しかし、線形計画法を繰り返し単純に計算するのでは時間がかかる。本発明の実施例では、以下に説明するように、帯域下限値を利用した帯域算出法を利用する。
【００４０】
＜帯域下限値を利用した帯域算出法＞
特定の障害想定リンクf'について式(1)〜式(5)を解き、その結果を他の障害想定リンクfについての帯域下限値c(e)とする。この場合、次の制約式(6)を式(1)〜(5)に追加する。
【００４１】
【数６】
これは、線形計画化法によって帯域上限値を求めるための目的関数が、既に求解を終えている最大化問題の最大値を上回ることを制約条件に加えることに相当する。既に求解を終えている最大化問題の最大値を超えられない場合には、実行可能解が得られず、算出結果が無駄になる。従って、既に目的関数で算出された算出結果を上回る値を対象として算出することにより、計算量を削減することができる。
【００４２】
式(1)〜式(6)を繰り返し計算し、その結果から帯域下限値c(e)を設定して、式(6)の制約条件を厳しくする。
【００４３】
なお、障害想定リンクf'は無作為に選択されてもよいが、故障の影響の大きいリンクが故障したと仮定して線形計画法を解く方が目的関数の値、すなわち、迂回用パスの帯域上限値を大きくすると考えられる。例えば、発見的手法として疎通トラヒックtraf(e)が最も大きなリンクから順に、障害想定リンクf'を選択して計算すれば、更に計算量が削減され、計算の高速化が期待できる。
【００４４】
以上の帯域下限値を利用した帯域算出法について、図３を参照して説明する。図３は、６ノードＡ、Ｂ、Ｃ、Ｄ、Ｅ及びＦで構成される通信網を示す。発信元ノードＥと宛先ノードＢとの間に、現用パスＥＤＣＢ及び迂回用パスＥＡＢが設定されているものとする。現用パスＥＤＣＢは、故障時に迂回用パスＥＡＢに切り替えられる。
【００４５】
ノードＡ及びＢの間の通信リンクeを、迂回用パスの帯域を求めたい通信リンク（設計対象リンク）とする。現用パスＥＤＣＢの各リンク上のトラヒック量を観測すると、通信リンクＥＤ上では10Mbps、通信リンクＤＣ上では100Mbps、通信リンクＣＢ上では10Mbpsである。現用パスのなかで最もトラヒック量の多い通信リンクは通信リンクＤＣであるため、まずこのリンクＤＣが故障したと考えて迂回用パスのトラヒック量を算出すると、計算の効率化が期待できる。このように、トラヒック量の降順に障害想定リンクを選択し、式(1)〜式(6)を用いて迂回用パスの帯域上限値を求めることができる。
【００４６】
＜実施例の効果＞
本発明の実施例によれば、通信網においてトラヒックを転送する現用パス及び迂回用パスの情報が与えられており、障害がなく現用パスを流れるトラヒックが、通信リンクにおいて観測されているが、個々のＳＤペア間を流れる交流トラヒックが分からない状況において、迂回用パスに必要な設計対象リンクの帯域を算出することができる。なお、迂回用パスの帯域は、複数の現用パスにより共用可能である。
【００４７】
帯域の算出に際して、単純に設計対象リンクでの帯域上限値を算出しようとすると障害想定リンクに対して最大化問題を繰り返して解かなくてはならないが、本発明の実施例では、各障害想定リンクで最大化問題を解く際に、その制約条件に目的関数が既に求解を終えている最大化問題の最大値を上回ることを新たに条件として加える。各障害想定リンクで解く本来の最大化問題の最大値が、既に求解を終えている最大化問題の最大値を超えられない際には、この新たな条件により実行可能解が得られず、その結果、高速に解を得ることが可能となる。
障害想定リンクを無作為に選択する場合の手法は、設計対象リンクに対して必要な帯域上限値を与える障害想定リンクがより早い時点で見つけられた場合に、効果的である。
【００４８】
一方、観測したトラヒック量の大きい通信リンクは、障害を想定した場合に、その通信リンク上の現用パスの障害が迂回用パスに切り替わることにより通信網全体に与える影響が大きいことが想定できる。従って、トラヒック量の大きい通信リンクから障害想定リンクを選択することで、計算の高速化が期待できる。
【００４９】
以上、本発明の実施例について説明したが、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【００５０】
説明の便宜上、本発明の実施例に係るシステムは機能的なブロック図を用いて説明しているが、本発明のシステムは、ハードウエア、ソフトウェア又はそれらの組み合わせで実現されてもよい。例えば、帯域算出装置２０の各機能部がソフトウェアで実現され、オペレーションシステム１０内にインストールされてもよい。また、２以上の実施例が必要に応じて組み合わせて使用されてもよい。
【符号の説明】
【００５１】
１０ オペレーションシステム
２０ 帯域算出装置
３０ 帯域表示装置
１０１ ネットワークデータ収集部
１１１ ネットワーク情報データベース
２０１ データ取得部
２０２ 帯域算出部
２１１ パス情報データベース
２１２ トラヒック情報データベース
３０１ 帯域表示部
【技術分野】
【０００１】
本発明は、帯域算出方法及び帯域算出装置に関する。より具体的には、本発明は、障害時に選択される迂回用パスに必要な通信リンクの帯域上限値を算出する帯域算出方法及び帯域算出装置に関する。
【背景技術】
【０００２】
通信リンクには、耐障害性を高めるために、現用パスに対して迂回用パスが設定される。迂回用パスに必要な帯域を算出する方法として、以下の方法が検討されている。
【０００３】
通信リンクを流れるトラヒックの情報より、送信元・宛先（ＳＤ：Source-Destination）ペア間の交流トラヒックを推定するNetwork-Tomographyという方法がある（非特許文献１参照）。このNetwork-Tomographyにより推定された交流トラヒックより迂回用パスに必要な帯域を求めることも可能である。しかし、Network-Tomographyでは、交流トラヒックは、ポアソン分布又は正規分布を仮定して、最尤法等を用いて平均値を算出するものであり、迂回用パスに必要な帯域上限値を保証するものではないという問題がある。
【０００４】
上記の問題を解決するため、通信リンクを流れるトラヒックや端点ノードにおける流出入トラヒックの観測データを制約式に組み込み、通信リンクを流れる迂回用パスに必要な帯域を線形計画法によって最大化する帯域算出手法を既に提案している（特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】A. Medina et al. "Traffic Matrix Estimation: Existing Techniques and New Directions," Proceedings of the 2002 SIGCOMM conference, 2002.
【特許文献】
【０００６】
【特許文献１】特願2009-49110「通信帯域算出方法および装置」松村龍太郎、辻野雅之、岩下基
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記のように、特許文献１では、ＳＤペア間のトラヒックが分からないが、通信リンクを流れるトラヒックが観測されている場合に、迂回用パスに必要な通信リンクでの帯域上限値を算出することができる。しかし、特許文献１では、全ての通信リンクについて障害が発生したことを想定して最大化問題を解く必要がある。このため、ネットワークの規模が大きくなるにつれて、計算量が増大するという問題がある。特に、大規模なネットワークでは求解に時間がかかる。
【０００８】
そこで、本発明は、迂回用パスに必要な帯域を算出する際の計算量を削減することができる帯域算出方法及び帯域算出装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するため、本発明の帯域算出方法は、
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置における帯域算出方法であって、
通信リンクを流れるトラヒック量を取得するステップと、
現用パス上で障害の発生を想定する第１の通信リンクを選択するステップと、
前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、線形計画化法によって、前記トラヒック量を制約条件に用いる関数の最大値として算出するステップと、
前記選択するステップと前記算出するステップとを繰り返すステップと、
を有し、
前記算出するステップは、前記関数が既に算出した算出結果を上回るという制約条件を加えて、帯域上限値を算出することを特徴とする。
【００１０】
また、本発明の帯域算出装置は、
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置であって、
通信リンクを流れるトラヒック量を取得するトラヒック取得部と、
現用パス及び迂回用パスの情報を格納するパス情報格納部と、
前記パス情報格納部から、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、線形計画化法によって、前記トラヒック量を制約条件に用いる関数の最大値として算出する帯域算出部と、
を有し、
前記帯域算出部は、前記第１の通信リンクを選択し直し、前記関数が既に算出した算出結果を上回るという制約条件を加えて、帯域上限値を算出することを特徴とする。
【発明の効果】
【００１１】
本発明の実施例によれば、迂回用パスに必要な帯域を算出する際の計算量を削減することができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施例に係る通信網を示す図
【図２】本発明の実施例に係る通信システムを示す図
【図３】帯域下限値を利用した帯域算出方法の概念図
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施例について説明する。
【００１４】
図１は、本発明の実施例に係る通信網を示す図である。通信網は、複数のノードＡ〜Ｄと、ノード間を接続する通信リンク１〜４とから構成される。通信網には、単数又は複数の送信元ノード及び宛先ノードのペア（ＳＤペア：Source-Destinationペア）が存在する。図１では、ノードＡが送信元ノードであり、ノードＣが宛先ノードである。図示しないが、他のＳＤペアも存在し得る。ＳＤペア間には、現用パスと迂回用パスとが予め設定されているものとする。現用パスとは、障害が発生しない通常時に利用するパスであり、迂回用パスとは、現用パス上で障害が発生した障害時に利用するパスである。なお、迂回用パスの帯域は、複数の現用パスにより共用可能である。図１では、通信リンク１及び２に現用パスが設定されており、通信リンク３及び４に迂回用パスが設定されている。
【００１５】
現用パスが設定されている通信リンク１に障害が発生した場合、ＳＤペア間のトラヒックは、迂回用パスに流れる。この場合、迂回用パスに必要な帯域が予め設定されていなければ、通信品質が低下する。このため、本発明では、障害が発生していないときに通信網上の通信リンクを流れるトラヒック量を観測しておき、観測されたトラヒック量から、迂回用パスの特定の通信リンクに必要な帯域上限値を算出する。ここで、迂回用パスに必要な帯域上限値を算出する通信リンクを「設計対象リンク」と呼ぶ。障害は、同時に単一の通信リンクで発生することを想定する。
【００１６】
この帯域上限値を算出するために、設計対象リンクに設定されている迂回用パスに対応する現用パスが経由する通信リンクで障害が発生したことを想定し、その際の設計対象リンクでの影響を考える。ここで、障害の発生を想定する通信リンクを「障害想定リンク」と呼ぶ。この障害想定リンクの障害に伴う迂回用パスが設計対象リンクで必要とする帯域上限値を算出する問題は、最大化問題として定式化できる。全ての障害想定リンクについて、最大化問題を線形計画化法によって算出することで、設計対象リンクの帯域上限値が算出される。
【００１７】
例えば、図１において、通信リンク１（障害想定リンク）で障害が発生したことを想定して、通信リンク４（設計対象リンク）で迂回用パスに必要な帯域上限値を算出する。なお、通信リンク１で障害が発生した場合と、通信リンク２で障害が発生した場合とでは、通信リンク４で迂回用パスに必要な帯域上限値が異なるため、次に、通信リンク２を障害想定リンクとして、設計対象リンクで迂回用パスに必要な帯域上限値を算出する必要がある。本発明の実施例では、通信リンク１で既に算出した算出結果を上回る値を対象として、通信リンク２で障害が発生した場合の帯域上限値を算出する。このように、線形計画化法によって帯域上限値を求めるための目的関数が、既に算出した算出結果を上回るという制約条件を加えることで、計算量を削減する。
【００１８】
＜通信システムの構成＞
図２は、本発明の実施例に係る通信システムを示す図である。本発明の実施例に係る通信システムは、図１に示すような通信網と、オペレーションシステム１０と、帯域算出装置２０と、帯域表示装置３０とを有する。
【００１９】
オペレーションシステム１０は、通信網上のノード及び通信リンクを運用管理する装置である。オペレーションシステム１０は、機能部としてのネットワークデータ収集部１０１と、データベースとしてのネットワーク情報データベース１１１とを有する。
【００２０】
ネットワークデータ収集部１０１は、オペレーションシステム１０が管理する通信網上のノードに接続する通信リンクを流れるトラヒック量を収集し、トラヒック情報としてネットワーク情報データベース１１１に蓄積する。また、通信網の運用者等により設定された現用パス及び迂回用パスに関する情報は、パス情報としてネットワーク情報データベース１１１に蓄積される。
【００２１】
帯域算出装置２０は、オペレーションシステム１０に接続されており、オペレーションシステム１０からトラヒック情報及びパス情報を取得し、取得したデータを用いて迂回用パスの設計対象リンクに必要な帯域を算出する。帯域算出装置２０は、通信網の運用者又は設計者が直接操作する帯域算出装置２０からの要求を受け付け、算出した必要な帯域に関する情報を帯域表示装置３０に送信する。
【００２２】
帯域算出装置２０は、機能部としてのデータ取得部２０１及び帯域算出部２０２を有し、データベースとしてのパス情報データベース２１１及びトラヒック情報データベース２１２を有する。
【００２３】
データ取得部２０１は、オペレーションシステム１０がネットワーク情報データベース１１１で管理する情報のうち、帯域の算出に必要な情報として、パス情報及びトラヒック情報を取得し、それぞれ、パス情報データベース２１１及びトラヒック情報データベース２１２に蓄積する。
【００２４】
帯域算出部２０２は、パス情報データベース２１１及びトラヒック情報データベース２１２に蓄積されたパス情報及びトラヒック情報を用いて、迂回用パスの設計対象リンクに必要な帯域上界値及び帯域上限値を計算する。帯域上限値を算出するための帯域算出アルゴリズムについては、後述する。
【００２５】
帯域表示装置３０は、帯域算出装置２０に接続されており、算出された帯域上限値を表示する。
【００２６】
帯域表示装置３０は、機能部としての帯域表示部３０１を有する。
【００２７】
帯域表示部３０１は、通信網の運用者又は設計者による操作を受け付け、帯域算出装置２０に対して、設計対象リンクについて算出された帯域上限値の取得要求を実施し、帯域算出装置２０から取得した値を表示する。
【００２８】
＜帯域算出アルゴリズム＞
次に、帯域算出部２０２で用いられる帯域算出アルゴリズムについて説明する。
【００２９】
対象とする通信網を有向グラフG={N,E}とする。但し、N及びEは、それぞれ通信網に属するノード及び通信リンクの集合とする。
【００３０】
Fij≧0をノードiからノードjへのトラヒック量とする。
【００３１】
rije∈{0,1}によってノードi及びj間の現用パスの経路を示す。具体的には、ノードi及びj間の現用パスがリンクeを通る場合、rije=1とし、通らない場合、rije=0とする。なお、現用パスの経路は、パス情報データベース２１１に格納されている。
【００３２】
【数１】
によってノードi及びj間の迂回用パスの経路を示す。具体的には、リンクf（障害想定リンク）が故障したときにノードi及びj間の迂回用パスがリンクe（設計対象リンク）を通る場合、
【００３３】
【数２】
とし、通らない場合、
【００３４】
【数３】
とする。なお、迂回用パスの経路は、パス情報データベース２１１に格納される。
【００３５】
traf(e)によって、リンクe上のトラヒックの観測値を示す。extin(i)によって、ノードiに流入するトラヒックの観測値を示す。extout(j)によって、ノードjから流出するトラヒックの観測値を示す。これらのトラヒックの観測値は、トラヒック情報データベース２１２に格納されている。
【００３６】
線形計画法によって、通信リンクfが故障したときに通信リンクeにおいて必要になる迂回用パスの帯域を求める式は、次の式(1)で表される。
【００３７】
【数４】
すなわち、次の目的関数
【００３８】
【数５】
の最大値が、リンクfが故障した場合の迂回用パスのリンクeで必要となる帯域上限値を表す。また、式(2)〜式(5)は、式(1)を算出するときの制約式である。
【００３９】
従って、迂回用パスのリンクeで必要となる帯域上限値を算出するためには、式(1)〜式(5)を全ての障害想定リンクfについて計算し、その最大値を算出する必要がある。しかし、線形計画法を繰り返し単純に計算するのでは時間がかかる。本発明の実施例では、以下に説明するように、帯域下限値を利用した帯域算出法を利用する。
【００４０】
＜帯域下限値を利用した帯域算出法＞
特定の障害想定リンクf'について式(1)〜式(5)を解き、その結果を他の障害想定リンクfについての帯域下限値c(e)とする。この場合、次の制約式(6)を式(1)〜(5)に追加する。
【００４１】
【数６】
これは、線形計画化法によって帯域上限値を求めるための目的関数が、既に求解を終えている最大化問題の最大値を上回ることを制約条件に加えることに相当する。既に求解を終えている最大化問題の最大値を超えられない場合には、実行可能解が得られず、算出結果が無駄になる。従って、既に目的関数で算出された算出結果を上回る値を対象として算出することにより、計算量を削減することができる。
【００４２】
式(1)〜式(6)を繰り返し計算し、その結果から帯域下限値c(e)を設定して、式(6)の制約条件を厳しくする。
【００４３】
なお、障害想定リンクf'は無作為に選択されてもよいが、故障の影響の大きいリンクが故障したと仮定して線形計画法を解く方が目的関数の値、すなわち、迂回用パスの帯域上限値を大きくすると考えられる。例えば、発見的手法として疎通トラヒックtraf(e)が最も大きなリンクから順に、障害想定リンクf'を選択して計算すれば、更に計算量が削減され、計算の高速化が期待できる。
【００４４】
以上の帯域下限値を利用した帯域算出法について、図３を参照して説明する。図３は、６ノードＡ、Ｂ、Ｃ、Ｄ、Ｅ及びＦで構成される通信網を示す。発信元ノードＥと宛先ノードＢとの間に、現用パスＥＤＣＢ及び迂回用パスＥＡＢが設定されているものとする。現用パスＥＤＣＢは、故障時に迂回用パスＥＡＢに切り替えられる。
【００４５】
ノードＡ及びＢの間の通信リンクeを、迂回用パスの帯域を求めたい通信リンク（設計対象リンク）とする。現用パスＥＤＣＢの各リンク上のトラヒック量を観測すると、通信リンクＥＤ上では10Mbps、通信リンクＤＣ上では100Mbps、通信リンクＣＢ上では10Mbpsである。現用パスのなかで最もトラヒック量の多い通信リンクは通信リンクＤＣであるため、まずこのリンクＤＣが故障したと考えて迂回用パスのトラヒック量を算出すると、計算の効率化が期待できる。このように、トラヒック量の降順に障害想定リンクを選択し、式(1)〜式(6)を用いて迂回用パスの帯域上限値を求めることができる。
【００４６】
＜実施例の効果＞
本発明の実施例によれば、通信網においてトラヒックを転送する現用パス及び迂回用パスの情報が与えられており、障害がなく現用パスを流れるトラヒックが、通信リンクにおいて観測されているが、個々のＳＤペア間を流れる交流トラヒックが分からない状況において、迂回用パスに必要な設計対象リンクの帯域を算出することができる。なお、迂回用パスの帯域は、複数の現用パスにより共用可能である。
【００４７】
帯域の算出に際して、単純に設計対象リンクでの帯域上限値を算出しようとすると障害想定リンクに対して最大化問題を繰り返して解かなくてはならないが、本発明の実施例では、各障害想定リンクで最大化問題を解く際に、その制約条件に目的関数が既に求解を終えている最大化問題の最大値を上回ることを新たに条件として加える。各障害想定リンクで解く本来の最大化問題の最大値が、既に求解を終えている最大化問題の最大値を超えられない際には、この新たな条件により実行可能解が得られず、その結果、高速に解を得ることが可能となる。
障害想定リンクを無作為に選択する場合の手法は、設計対象リンクに対して必要な帯域上限値を与える障害想定リンクがより早い時点で見つけられた場合に、効果的である。
【００４８】
一方、観測したトラヒック量の大きい通信リンクは、障害を想定した場合に、その通信リンク上の現用パスの障害が迂回用パスに切り替わることにより通信網全体に与える影響が大きいことが想定できる。従って、トラヒック量の大きい通信リンクから障害想定リンクを選択することで、計算の高速化が期待できる。
【００４９】
以上、本発明の実施例について説明したが、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【００５０】
説明の便宜上、本発明の実施例に係るシステムは機能的なブロック図を用いて説明しているが、本発明のシステムは、ハードウエア、ソフトウェア又はそれらの組み合わせで実現されてもよい。例えば、帯域算出装置２０の各機能部がソフトウェアで実現され、オペレーションシステム１０内にインストールされてもよい。また、２以上の実施例が必要に応じて組み合わせて使用されてもよい。
【符号の説明】
【００５１】
１０ オペレーションシステム
２０ 帯域算出装置
３０ 帯域表示装置
１０１ ネットワークデータ収集部
１１１ ネットワーク情報データベース
２０１ データ取得部
２０２ 帯域算出部
２１１ パス情報データベース
２１２ トラヒック情報データベース
３０１ 帯域表示部
【特許請求の範囲】
【請求項１】
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置における帯域算出方法であって、
通信リンクを流れるトラヒック量を取得するステップと、
現用パス上で障害の発生を想定する第１の通信リンクを選択するステップと、
前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、線形計画化法によって、前記トラヒック量を制約条件に用いる関数の最大値として算出するステップと、
前記選択するステップと前記算出するステップとを繰り返すステップと、
を有し、
前記算出するステップは、前記関数が既に算出した算出結果を上回るという制約条件を加えて、帯域上限値を算出する帯域算出方法。
【請求項２】
前記選択するステップは、トラヒック量の降順に、前記第１の通信リンクを選択する、請求項１に記載の帯域算出方法。
【請求項３】
前記算出するステップは、前記第１の通信リンクをfとし、前記第２の通信リンクをeとした場合、
【数７】
を算出し、
更に、既に算出した算出結果をc(e)とした場合、以下の制約条件：
【数８】
を加えて、帯域上限値を算出する、請求項１又は２に記載の帯域算出方法。
【請求項４】
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置であって、
通信リンクを流れるトラヒック量を取得するトラヒック取得部と、
現用パス及び迂回用パスの情報を格納するパス情報格納部と、
前記パス情報格納部から、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、線形計画化法によって、前記トラヒック量を制約条件に用いる関数の最大値として算出する帯域算出部と、
を有し、
前記帯域算出部は、前記第１の通信リンクを選択し直し、前記関数が既に算出した算出結果を上回るという制約条件を加えて、帯域上限値を算出する帯域算出装置。
【請求項１】
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置における帯域算出方法であって、
通信リンクを流れるトラヒック量を取得するステップと、
現用パス上で障害の発生を想定する第１の通信リンクを選択するステップと、
前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、線形計画化法によって、前記トラヒック量を制約条件に用いる関数の最大値として算出するステップと、
前記選択するステップと前記算出するステップとを繰り返すステップと、
を有し、
前記算出するステップは、前記関数が既に算出した算出結果を上回るという制約条件を加えて、帯域上限値を算出する帯域算出方法。
【請求項２】
前記選択するステップは、トラヒック量の降順に、前記第１の通信リンクを選択する、請求項１に記載の帯域算出方法。
【請求項３】
前記算出するステップは、前記第１の通信リンクをfとし、前記第２の通信リンクをeとした場合、
【数７】
を算出し、
更に、既に算出した算出結果をc(e)とした場合、以下の制約条件：
【数８】
を加えて、帯域上限値を算出する、請求項１又は２に記載の帯域算出方法。
【請求項４】
現用パス及び迂回用パスが設定されている通信網上で障害が発生した場合に、迂回用パスで必要となる通信リンクの帯域上限値を算出する帯域算出装置であって、
通信リンクを流れるトラヒック量を取得するトラヒック取得部と、
現用パス及び迂回用パスの情報を格納するパス情報格納部と、
前記パス情報格納部から、現用パス上で障害の発生を想定する第１の通信リンクを選択し、前記第１の通信リンクに障害が発生した場合に迂回用パスの第２の通信リンクで必要となる帯域上限値を、線形計画化法によって、前記トラヒック量を制約条件に用いる関数の最大値として算出する帯域算出部と、
を有し、
前記帯域算出部は、前記第１の通信リンクを選択し直し、前記関数が既に算出した算出結果を上回るという制約条件を加えて、帯域上限値を算出する帯域算出装置。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２０１１−１７２０３５（Ｐ２０１１−１７２０３５Ａ）
【公開日】平成２３年９月１日（２０１１．９．１）
【国際特許分類】
【出願番号】特願２０１０−３４２７３（Ｐ２０１０−３４２７３）
【出願日】平成２２年２月１９日（２０１０．２．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年９月１日（２０１１．９．１）
【国際特許分類】
【出願日】平成２２年２月１９日（２０１０．２．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]