(57)【要約】【課題】  リンク設計技術において、障害が無く現用パスが選択され通信リンクを流れるトラヒックが観測されている状況において、実際に必要な迂回用パス帯域を精度よく求める。【解決手段】  本発明は、観測されたトラヒック量を取得してトラヒック情報記憶手段に格納し、現用パスの経路情報を取得してトラヒック情報記憶手段に格納し、トラヒック情報記憶手段から観測されたトラヒック量を、パス情報記憶手段から現用パスの経路情報を取得して、発着信のノードペア間の通信トラヒックが直接測定できないとき、該重力モデルにおける距離依存係数の分布が大きく、かつ、該分布が該ノードペアを増やしていったとき増やし方によらず一定の形に近づく場合に対して、各リンクにおける現用パス帯域と迂回用パス帯域の比率を求め、該比率と各リンクにおける現用パス帯域によって各リンクにおける迂回用パス帯域を再計算する。【選択図】  図１
2014150450.tif 000002
【特許請求の範囲】
【請求項１】
全通信ノードペア間を流れるトラヒックが、通信網における各通信リンクを流れるトラヒック量として観測されている場合に、実際に必要な迂回用パス帯域を求める迂回用パス帯域評価装置であって、
観測されたトラヒック量を取得してトラヒック情報記憶手段に格納し、現用パスの経路情報を取得してトラヒック情報記憶手段に格納するデータ取得手段と、
前記トラヒック情報記憶手段から前記観測されたトラヒック量を、前記パス情報記憶手段から前記現用パスの経路情報を取得して、発着信ノードの組み合わせであるノードペア間の通信トラヒックが直接測定できないとき、該重力モデルにおける距離依存係数の分布が大きく、かつ、該分布が該ノードペアを増やしていったとき、増やし方によらず一定の形に近づく場合に対して、各リンクにおける現用パス帯域と迂回用パス帯域の比率を求め、該比率と測定済みの各リンクにおける現用パス帯域によって各リンクにおける迂回用パス帯域を再計算する帯域算出手段と、
を有することを特徴とする迂回用パス帯域評価装置。
【請求項２】
全通信ノードペア間を流れるトラヒックが、通信網における各通信リンクを流れるトラヒック量として観測されている場合に、実際に必要な迂回用パス帯域を求める迂回用パス帯域評価方法であって、
データ取得手段、トラヒック情報記憶手段、トラヒック情報記憶手段、帯域算出手段を有する装置において、
前記データ取得手段が、観測されたトラヒック量を取得して前記トラヒック情報記憶手段に格納し、現用パスの経路情報を取得して前記トラヒック情報記憶手段に格納するデータ取得ステップと、
前記帯域算出手段が、前記トラヒック情報記憶手段から前記観測されたトラヒック量を、前記パス情報記憶手段から前記現用パスの経路情報を取得して、発着信ノードの組み合わせであるノードペア間の通信トラヒックが直接測定できないとき、該重力モデルにおける距離依存係数の分布が大きく、かつ、該分布が該ノードペアを増やしていったとき、増やし方によらず一定の形に近づく場合に対して、各リンクにおける現用パス帯域と迂回用パス帯域の比率を求め、該比率と測定済みの各リンクにおける現用パス帯域によって各リンクにおける迂回用パス帯域を再計算する帯域算出ステップと、
を行うことを特徴とする迂回用パス帯域評価方法。
【請求項３】
コンピュータを、
請求項１記載の迂回用パス帯域評価装置の各手段として機能させるための迂回用パス帯域評価プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、迂回用パス帯域評価装置及び方法に係り、特に、障害が無く現用パスが選択され通信リンクを流れるトラヒックが観測されている状況において、ノードペア間通信トラヒックを重力モデルにあてはめたとき、距離依存係数の散らばりが大きく、しかもその分布が選択するノードペアの数を増やしていくと、増やし方によらず一定の形に近づくとき、各リンクに必要な迂回用パス帯域を評価する手法に関するものである。
【０００２】
技術分野としては、リンク帯域の設計に属する。その概要は以下のようなものである。まず、複数の通信ノード間を結ぶ通信リンクからなるネットワークを想定する。通信ノードは、トラヒックの発信、受信、中継を行う。あるノード（以下、発信ノード）から発信されたトラヒックが別のノード（以下、着信ノード）に着信するとき、発着信ノード間を結ぶ通信リンクが存在しない場合には、１つ以上の他のノード（以下、中継ノード）がトラヒックを中継する。ネットワークに障害が無いという条件の下で、発着信ノードの組み合わせ（以下、ノードペア）に対し、トラヒックが流れる経路（通信リンクと中継ノードの列）をノードペアの現用パスと呼ぶ。ネットワークに障害が無い場合には、各通信リンクを流れるトラヒック量は、当該通信リンクを経路に含む現用パスに対応するノードペア間トラヒック量の総和に等しい。ネットワークに障害が発生した場合、具体的には通信リンクが故障した場合、当該通信リンクを含む現用パスが利用できなくなる。このとき、利用できなくなる現用パスに対応するノードペアのトラヒックを、故障した通信リンクを通らない経路で流通させれば、ネットワークの障害によるトラヒック非疎通を抑えられる。この新しい経路を迂回用パスと呼ぶ。一般に、ネットワーク障害時に迂回用パスへ流れるトラヒック量も考慮したリンク帯域を設計することで、ネットワークの耐障害性を向上させることが可能になる。
【背景技術】
【０００３】
迂回用パスに必要な通信リンクの帯域上限値を算出するものとして、通信リンクを流れるトラヒックや端点ノードにおける流出入トラヒックの観測データを容量制約式に組み込み、通信リンクを流れる迂回用パスに必要な帯域を線形計画法によって最大化する帯域算出手法がConstraint Programmingとして考案された（例えば、非特許文献１参照）。この手法は、迂回用パスに必要な通信リンクでの帯域上限値を導出する目的としては、所期の結果を算出するが、通信リンクでの帯域上限値を達成するノードペア間トラヒック想定値は通信リンクが異なるとその都度変わってしまうため、実際にこの手法を適用しようとすると帯域上限値が実際に必要な値よりも大きな値になってしまうことがある。ノードペア間トラヒックを求めてそれから通信リンクでの帯域を算出すればこの問題は解決するが、与えられた制約式からはノードペア間トラヒックが一意に決まらないため、何らかの方法で推定したノードペア間トラヒック値が実際に疎通するトラヒックに等しいかどうかが分からないという問題があった。
【０００４】
実際に疎通するノードペア間トラヒックに近い値を算出するために、複数の時点における制約式も同時に考慮して、それによって特定の時点のノードペア間トラヒックを推定する手法が提案されている（例えば、非特許文献２参照）。しかし、共分散の計算が基礎になっていてその値が安定しないため、ノードペア間トラヒックの推定値も安定しないという欠点があった。
【０００５】
そこで、ノードペア間トラヒックが重力モデルに従うという仮定と、重力モデルの距離依存係数をノードペアを変化させたとき散らばりが少ないようにして、ノードペア間トラヒックが容量制約式を満たすというモデルのもとで、ノードペア間トラヒックを算出することで、特定の１時点でのトラヒック情報をもとに、障害時に選択される迂回用パスに必要な通信リンク帯域算出という課題を解決する手法が提案されている（例えば、非特許文献３参照）。この手法はノードペアを変化させたとき距離依存係数の散らばりの小さい重力モデルに従うトラヒックに対しては非常に精度の高いトラヒック推定を可能にする。例えば、日本の大都市と地方都市を結ぶネットワークにおけるノードペア間トラヒックは、各都市の人口に比例する形で値が定まってくるため、この手法が非常に有効と考えられる。しかし、逆にノードペアを変化させたとき距離依存係数の散らばりの大きいトラヒックについては精度が低くなってしまうという難点があった。例えば、首都圏内の小都市間を結ぶネットワークでは、各小都市の人口はほぼ等しく、ノードペア間トラヒックの値の小都市の違いによる変動は、各小都市の人口以外の要因から決まってくると考えられる。そのような場合には、距離依存係数の散らばりの小さい重力モデルに基づいた手法を用いるとノードペア間トラヒック算出の精度が落ちてしまう。 
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Simonis, H.: 'Constraint Based Resilience Analysis', LNCS, 2006, 4204, pp. 16-28
【非特許文献２】Cao, J., Davis, D., Wiel, S. V., and Yu, B.: 'Time-varying Network Tomography', Journal of the American Statistical Association, 2000, 95, pp. 1063-1075
【非特許文献３】松村龍太郎，佐々木正明，長谷川治久，"二次計画法を用いた重力モデル型トラヒック推定法"信学会ソサイエティ大会，B-14-6, 2012
【発明の概要】
【発明が解決しようとする課題】
【０００７】
障害の発生するリンクがどこにあるかにより、影響を受ける現用パス／ノードペアは異なる。すべての障害に対応できる設備量は膨大なものとなり、現実的な解ではない。実際、大規模障害時には、ネットワークの接続性自体が損なわれるので、救済そのものができなくなってしまう。そこで、本発明のターゲットとしては、どこか１つのリンクが故障したときに対応できるリンク帯域を設計することを考える。ネットワークを流れるトラヒック量の情報として取得可能なものは、一般に通信リンク単位のトラヒックに限られるが、上記リンク帯域設計を実施しようとすると、現用パス／ノードペア単位のトラヒック量が必要になる。
【０００８】
従来は、ここで、ノードペア間トラヒックが発信トラヒックと着信トラヒックに比例するという重力モデルを想定し、また重力モデルにおける距離依存係数はあまり値が変動しないというモデルを用いて、大都市と地方都市を結ぶような大きなネットワークのノードペア間トラヒックの推定を行い、精度の高い結果を得た。これは、日本における大都市と地方都市を結ぶノードペア間トラヒックが発着信ノードの人口に比例する重力モデルに従っていることが理由である。ところが、比較的狭い首都圏における小都市を結ぶノードペア間トラヒックを推定しようとすると、各小都市の人口がほぼ等しく、距離依存係数の散らばりの小さい重力モデルではノードペア間トラヒックのノードペア毎の違いを記述できなくなる。このような場合に、距離依存係数の散らばりの小さい重力モデルに従う手法を用いて通信リンク単位のトラヒックからノードペア間トラヒックを推定しようとすると推定精度が悪くなってしまう。
【０００９】
本発明は上記の点に鑑みなされたもので、実際に必要な迂回用パス帯域を精度よく求めることが可能な迂回用パス帯域評価装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するため、本発明は、全通信ノードペア間を流れるトラヒックが、通信網における各通信リンクを流れるトラヒック量として観測されている場合に、実際に必要な迂回用パス帯域を求める迂回用パス帯域評価装置であって、
観測されたトラヒック量を取得してトラヒック情報記憶手段に格納し、現用パスの経路情報を取得してトラヒック情報記憶手段に格納するデータ取得手段と、
前記トラヒック情報記憶手段から前記観測されたトラヒック量を、前記パス情報記憶手段から前記現用パスの経路情報を取得して、発着信ノードの組み合わせであるノードペア間の通信トラヒックを重力モデルに当てはめて現用パス帯域及び迂回用パスを推定したとき、該重力モデルにおける距離依存係数の分布が大きく、かつ、該分布が該ノードペアを増やしていったとき、増やし方によらず一定の形に近づく場合に対して、各リンクにおける現用パス帯域と迂回用パス帯域の比率を求め、該比率によって各リンクにおける迂回用パス帯域を再計算する帯域算出手段と、を有する。
【発明の効果】
【００１１】
従来技術においては、距離依存係数の散らばりの大きい重力モデルに従うトラヒック情報下でのノードペア間トラヒックを評価しようとすると推定誤差が大きくなってしまうという難点があった。これはノードペア間トラヒックを一意に決めるために距離依存係数の散らばりを小さくする最適化をノードペア間トラヒック算出アルゴリズムに組み込んでいたことが主要因である。本発明では、距離依存係数の散らばりの大きな重力モデルに従うトラヒック情報下でも、その分布がノードペア数の増やし方によらず一定の形に近づくことをもとに求めたノードペア間トラヒックを対応する故障リンクに関する迂回用パス帯域として和をとり、故障リンクを変化させたときの、これらの和の最大値を迂回用パス帯域として評価することで、推定精度を上げるようにした。この迂回用パス帯域を用いて通信リンク帯域を設計すれば、たとえば人口分布のほぼ均一な都市圏においても、都市間の迂回用パス帯域を精度よく推定できるようになる。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施の形態における迂回用パス帯域評価システムの構成例である。
【図２】本発明の一実施の形態における帯域算出部における４ノードリング網モデルの例である。
【発明を実施するための形態】
【００１３】
以下、図面と共に本発明の実施の形態を説明する。
【００１４】
本当に求めたいリンク上の迂回用パス帯域については、それぞれの故障リンクに対応する距離依存係数の散らばりの大きいノードペア間トラヒック和の最大値を求めることで、推定精度を上げることができる。本発明では、具体的にはノードペア間のトラヒックが同一の分布（たとえば一様分布）に従う場合のように、ノードペア間トラヒックの平均値を各ノード毎にとると等しくなるような通信網を想定している。比較的狭い都市圏の都市間のトラヒック等が想定例である。このとき、観測されたトラヒック量及び現用パスの経路情報を入力として、ノードペア間トラヒックが同一の分布に従う距離依存係数の散らばりの大きい重力モデルを前提として、各リンクにおける現用パス帯域と迂回用パス帯域の比率を推定することによって各リンクにおける迂回用パス帯域を評価するという課題を解決する。
【００１５】
図１は、本発明の一実施の形態における迂回用パス帯域評価システムの構成例である。
【００１６】
本発明の主要部である帯域算出装置１０は、通信網上のノードＡ，Ｂ，Ｃ、通信網４０を管理運用するオペレーションシステム３０に接続し、必要なデータの取得と取得データを用いた帯域の算出を実施する。帯域算出装置１０は、通信網の運用者、または、設計者が直接操作する帯域表示装置２０からの要求を受け、算出した帯域に関する情報を帯域表示装置２０に送信する。
【００１７】
以下に本発明の実施の形態を実現するオペレーションシステム３０、帯域算出装置１０、帯域表示装置２０の機能について示す。
【００１８】
１．オペレーションシステム３０：
オペレーションシステム３０は、機能部としてのネットワークデータ収集部３１とデータベースとしてのネットワーク情報データベース３２から構成される。
【００１９】
ネットワークデータ収集部３１は、オペレーションシステム３０が管理する通信網４０上のノード（ノードＡ，Ｂ，Ｃ）に接続する通信リンク（通信リンク１，２，３）上を流れるトラヒック量を収集し、トラヒック情報としてネットワーク情報データベース３２に蓄積する。また、通信網４０の運用者が設定するなどした現用パス・迂回用パスに関する情報はパス情報としてネットワーク情報データベース３２に蓄積する。
【００２０】
２．帯域算出装置１０：
帯域算出装置１０は、機能部としてのデータ取得部１１、帯域算出部１２、及び、データベースとしてのトラヒック情報データベース１３、パス情報データベース１４から構成される。
【００２１】
データ取得部１１は、オペレーションシステム３０がネットワーク情報データベース３２で管理する情報のうち、帯域算出に必要な情報として、トラヒック情報・パス情報を取得し、それぞれ、トラヒック情報データベース１３、パス情報データベース１４に蓄積する。
【００２２】
帯域算出部１２は、トラヒック情報データベース１３、パス情報データベース１４に蓄積されたトラヒック情報とパス情報を用いて次に示すような計算を実施することで通信リンクに必要な帯域を計算する。
【００２３】
対象とする通信網を有向グラフG={N, E}とする。但し、N, Eは、それぞれ通信網に属するノード、リンクの集合とする。ノード数#N = n,リンク数#E=mとする。ノード、リンクには通し番号を付ける。最初に、異なるリンクが故障した場合には、それぞれの場合に引き起こされる迂回用パスの帯域を各リンクにおいて共有することによって節約するShared Protection構成の迂回用パス帯域算出について述べる。リンクfを通る現用パスの本数をc1(f)，f∈Ｅとし、リンクeが故障したときにリンクfに迂回される迂回用パスの本数をc2(e,f)，e,f∈Ｅとする。今、故障リンクeを変化させたとき、リンクfを通る迂回用パスの本数の最大値を
【００２４】
【数１】
2014150450.tif 000003
とおく。
【００２５】
リンクfを通る現用バスと迂回用パスの本数の比率は、
【００２６】
【数２】
2014150450.tif 000004
となる。ここで、各現用パス及び迂回用パスの帯域の平均値がどの対地間にわたっても十分束ねれば等しくなると仮定する。このとき、(1)式はそのまま、リンクfを通る現用パスと迂回用パスの総帯域の比率に近くなる。したがって、リンクfにおいて測定した現用パスの総帯域をP(f)，f∈E、リンクfにおいて必要なShared Protection構成の迂回用パスの総帯域をBs(f)，f∈Ｅとおくと、
【００２７】
【数３】
2014150450.tif 000005
により、Bs(f)を求めることができる。
【００２８】
次に、どのリンクが故障した場合にも、それぞれのリンクが故障した場合の迂回用パス帯域をすべて加算した帯域を、各リンクに割り当てるDedicated Protection構成の迂回用パス帯域算出について述べる。Dedicated Protection構成の場合のリンクfを通る迂回用パスの本数をcf(f)，f∈Eとおく。この値は迂回用パスの経路情報から容易に求めることができる。このとき、リンクfを通る現用バスと迂回用パスの本数の比率は、
【００２９】
【数４】
2014150450.tif 000006
となる。ここで、各現用パス及び迂回用パスの帯域平均値がどの対地間にわたっても十分束ねれば等しくなると仮定する。このとき、(3)式はそのまま、リンクfを通る現用パスと迂回用パスの総帯域の比率に近くなる。したがって、リンクfにおいて測定した現用パスの総帯域をP(f)，f∈E、リンクfにおいて必要なDedicated Protection構成の迂回用パスの総帯域をBd(f)，f∈Ｅとおくと、
【００３０】
【数５】
2014150450.tif 000007
により、Bd(f)を求めることができる。
【００３１】
以上のようにして、故障時に迂回用パスを疎通させるのに必要なリンク帯域を設計することが可能になる。
【００３２】
次に、計算例を示す。図２に示すように4ノードからなるリング網を考える。リング網の周囲に実線矢印を用いて現用パス経路、破線矢印を用いて迂回用パス経路を示した。現用パスと迂回用パスは始点と終点を共有するが、距離が短い方、距離が同じ場合には左回りにみて始点が若番号の方を現用パスとした。同図の実線矢印は現用パスを、破線矢印は迂回用パスを示す。
【００３３】
図２の現用パスを数えることにより、各リンクfを通る現用パスの本数c1(f)は次のようになる。
【００３４】
c1(1)=2                                (5)
c1(2)=3                                (6)
c1(3)=2                                (7)
c1(4)=1                                (8)
また、リンクeが故障したときに、リンクfを通る迂回用パスの本数2(e,f)，e,f∈Ｅは、図２の現用パスと迂回用パスを比較しながら数えることにより次のようになる。
【００３５】
c2(2,1)=2                            (9)
c2(3,1)=2                            (10)
c2(4,1)=1                            (11)
c2(3,2)=1                            (12)
c2(4,2)=1                            (13)
c2(1,2)=1                            (14)
c2(4,3)=1                            (15)
c2(1,3)=2                            (16)
c2(2,3)=2                            (17)
c2(1,4)=2                            (18)
c2(2,4)=3                            (19)
c2(3,4)=2                            (20)
これらのc2の値を用いて、Shared Protection構成の場合について、故障リンクeを変化させたときのリンクfを通る迂回用パスの本数の最大値
【００３６】
【数６】
2014150450.tif 000008
を求めると次のようになる。
【００３７】
c3(1)=max{c2(2,1),c2(3,1),c2(4,1)}=max{2,2,1}=2      (21)
c3(2)=max{c2(3,2),c2(4,2),c2(1,2)}=max{1,1,1}=1      (22)
c3(3)=max{c2(4,3),c2(1,3),c2(2,3)}=max{1,2,2}=2      (23)
c3(4)=max{c2(1,4),c2(2,4),c2(3,4)}=max{2,3,2}=3      (24)
リンクfを通る現用パスと迂回用パスの総帯域(総本数）の比率
【００３８】
【数７】
2014150450.tif 000009
は次のようになる。
【００３９】
【数８】
2014150450.tif 000010
これらの値とリンクfにおいて測定した現用パスの総帯域P(f)，f∈[{1,2,3,4}からリンクfにおいて必要なShared Protection構成の迂回用パスの総帯域Bs(f), f∈{1,2,3,4}は、
【００４０】
【数９】
2014150450.tif 000011
より概算値を求めることができる。
【００４１】
Dedicated Protection構成の場合のリンクfを通る迂回用パスの本数c4(f), f∈{1,2,3,4}は、図２の迂回用パスを数えることにより次のようになる。
【００４２】
c4(1)=4                                (30)
c4(2)=3                            (31)
c4(3)=4                            (32)
c4(4)=5                            (33)
Dedicated Protection構成の場合のリンクfを通る現用パスと迂回用パスの総帯域(総本数）の比率
【００４３】
【数１０】
2014150450.tif 000012
は次のようになる。
【００４４】
【数１１】
2014150450.tif 000013
これらの値とリンクfにおいて測定した現用パスの総帯域P(f), f∈{1,2,3,4}からリンクfにおいて必要なDedicated Protection構成の迂回用パスの総帯域Bd(f), f∈{1,2,3,4}は、
【００４５】
【数１２】
2014150450.tif 000014
により概算値を求めることができる。
【００４６】
３．帯域表示装置２０：
帯域表示装置２０は、機能部としての帯域表示部２１から構成される。
【００４７】
帯域表示部２１は、通信網４０の運用者、または、設計者による操作に基づき、帯域算出装置１０に対して、設計・運用・管理の対象である通信網の通信リンク帯域値の取得要求を実施し、帯域算出装置１０から受信した値を表示する。
【００４８】
なお、上記の図１の帯域算出装置の構成要素をプログラムとして構築し、帯域算出装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００４９】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００５０】
１，２，３  通信リンク
１０  帯域算出装置
１１  データ取得部
１２  帯域算出部
１３  トラヒック情報データベース
１４  パス情報データベース
２０  帯域表示装置
２１  帯域表示部
３０  オペレーションシステム
３１  ネットワークデータ収集部
３２  ネットワーク情報データベース
【図１】
2014150450.tif 000015
【図２】
2014150450.tif 000016